Can inference-time query decomposition replace pre-built knowledge graph structures?
This explores whether building retrieval logic on the fly from each query (LogicRAG-style) can do away with the expensive, static knowledge graphs that RAG systems pre-construct over a whole corpus — and where the corpus says that trade actually holds.
This explores whether building retrieval logic on the fly from each query can replace the expensive, static graphs that RAG systems normally build over an entire corpus ahead of time. The most direct answer in the collection is yes, at least for one whole class of cost: Can query-time graph construction replace pre-built knowledge graphs? shows LogicRAG building a small directed acyclic graph from the query itself at inference time, skipping corpus-wide construction entirely. The payoff is concrete — no upfront build cost, nothing to go stale, and retrieval logic shaped to the specific question — and it keeps multi-hop reasoning intact. So the 'replacement' is real for the part of the problem that's about the graph being big, fixed, and expensive to maintain.
But the corpus quietly reframes the question: what a pre-built graph gives you isn't just structure, it's *speed and structure already paid for*. Can knowledge graphs enable multi-hop reasoning in one retrieval step? is the sharpest counterweight — HippoRAG pre-builds the graph once and then answers multi-hop queries in a single Personalized PageRank step, 10–20x cheaper and faster per query than iterative retrieval. That's the inverted economics: query-time construction moves the cost from build-time to every-single-query, which is a win if your corpus churns and a loss if you're answering millions of stable questions. Decomposition doesn't delete the cost, it relocates it.
The more interesting middle ground is that several notes treat the structure as something you *choose per query* rather than build-or-not-build. Can routing queries to task-matched structures improve RAG reasoning? (StructRAG) trains a router to pick tables, graphs, algorithms, or plain chunks based on what the query demands — so the graph stops being a default and becomes one option among several. Do hierarchical retrieval architectures outperform flat ones on complex queries? makes the related point that simply separating query planning from answer synthesis improves multi-hop performance — which is itself a kind of inference-time decomposition that doesn't require a standing graph at all.
Where pre-built structure earns its keep is when the graph carries reasoning *patterns*, not just facts. Can symbolic rules from knowledge graphs guide complex reasoning? derives navigational rules from a graph's topology — structural signal you can't reconstruct from a single query's vocabulary. Can learned traversal policies beat exhaustive graph reading? (Graph-O1) splits the difference yet again: keep the big graph, but learn to traverse it selectively at inference time instead of reading the whole thing — decomposition applied to *navigation* rather than *construction*. And Can hypergraphs capture multi-hop reasoning better than graphs? argues some relations bind three-or-more entities at once and shouldn't be decomposed into pairwise hops at all — a constraint query-time DAGs may flatten away.
The thing you might not have known you wanted to know: the graph and the decomposition aren't really competitors — they're the same operation done at different times. Can structuring reasoning as knowledge graphs help smaller models solve complex tasks? (KGoT) builds graph structure *during* inference, iteratively, as the reasoning unfolds — proving the dichotomy is false. The real axis isn't 'graph vs. no graph' but *when do you pay for structure, and how stable is the corpus you're paying for*. If knowledge changes faster than you can rebuild, decompose at query time; if it's stable and queried at volume, pre-build and traverse smartly. Replacement is the wrong frame — placement of the cost is the decision.
Sources 8 notes
LogicRAG constructs directed acyclic graphs from queries at inference time rather than pre-building corpus-wide graphs, eliminating construction overhead, avoiding staleness, and enabling query-specific retrieval logic without sacrificing multi-hop reasoning capability.
HippoRAG converts corpus into a knowledge graph, then uses Personalized PageRank seeded from query concepts to traverse multi-hop paths in one step. It matches iterative retrieval while being 10-20x cheaper and 6-13x faster, with 20% better accuracy on multi-hop QA.
StructRAG demonstrates that selecting knowledge structure type based on query demands—via DPO-trained router choosing among tables, graphs, algorithms, catalogues, and chunks—improves knowledge-intensive reasoning over standard retrieval. The approach grounds this in cognitive load and cognitive fit theory from cognitive science.
Separating query planning from answer synthesis into distinct components reduces interference and improves multi-hop query performance. This architectural principle mirrors documented benefits of separating planning from execution in agent design.
SymAgent derives symbolic rules from KG structure using LLM reasoning to create navigational plans that align natural language with graph topology. This approach captures structural reasoning patterns explicitly, outperforming retrieval methods that rely on semantic similarity alone.
Graph-O1 replaces whole-graph ingestion with step-by-step agentic navigation using Monte Carlo Tree Search and reinforcement learning. This approach fits within LLM context windows while learning domain-specific traversal policies, though it trades certainty about the full graph for decision-making under uncertainty.
HGMem organizes retrieved evidence as hyperedges rather than flat lists or binary graphs, allowing three or more entities to bind into single relations without decomposition. This structure accumulates coherent knowledge across retrieval steps, trading representational complexity for constraint expressiveness.
Knowledge Graph of Thoughts (KGoT) achieves 29% improvement on GAIA Level 3 tasks using GPT-4o mini by externalizing reasoning into iteratively constructed KG triples. The approach improves transparency, reduces bias, and enables quality control over reasoning steps.