Can query-time logic graphs match the efficiency of pre-built knowledge graph indexing?
This explores whether building a reasoning graph on-the-fly from each query can be as efficient as graphs pre-computed over the whole corpus — and what each approach trades away.
This explores whether building a reasoning graph on-the-fly from each query can be as efficient as graphs pre-computed over the whole corpus. The corpus suggests the comparison isn't really efficiency-vs-efficiency — it's about which cost you'd rather pay and when. Query-time construction, as in LogicRAG, skips the upfront expense of building and maintaining a corpus-wide graph entirely; it assembles a small directed acyclic graph from the query at inference time, which sidesteps staleness (a pre-built index goes out of date the moment the corpus changes) and lets the retrieval logic be tailored to the specific question rather than locked into one frozen topology Can query-time graph construction replace pre-built knowledge graphs?. The catch is that you pay a little more per query in exchange for paying nothing upfront and never re-indexing.
The strongest counter-argument comes from HippoRAG, which is the case for pre-building done well: convert the corpus into a knowledge graph once, then run Personalized PageRank seeded from the query's concepts to traverse multi-hop paths in a single retrieval step. It reports being 10–20x cheaper and 6–13x faster than iterative retrieval, with 20% better multi-hop accuracy Can knowledge graphs enable multi-hop reasoning in one retrieval step?. So the pre-built side's efficiency claim is real — but notice it's measured against *iterative* retrieval at query time, not against a lean query-time graph. The amortization logic is the key: pre-building wins when the same graph gets reused across many queries and the corpus is stable; query-time wins when the corpus shifts or each question wants its own reasoning shape.
What's interesting is that the field is increasingly refusing to read the whole graph at all, which erodes the efficiency advantage of having pre-built one. Graph-O1 replaces whole-graph ingestion with learned, step-by-step traversal using Monte Carlo Tree Search and reinforcement learning, so it fits inside an LLM's context window and only walks the paths it needs Can learned traversal policies beat exhaustive graph reading?. SymAgent goes further by deriving symbolic navigation rules from the graph's structure to plan routes through it Can symbolic rules from knowledge graphs guide complex reasoning?. Once you accept that you'll only ever traverse a fraction of a pre-built graph anyway, the question becomes whether you needed to build the whole thing in the first place — which is exactly LogicRAG's bet.
The most useful reframing in the corpus is that 'pre-built vs. query-time' may be a false binary. StructRAG argues the real lever is matching the *structure type* to the query: a DPO-trained router picks among tables, graphs, algorithms, catalogues, or plain chunks depending on what the question demands, grounded in cognitive-fit theory Can routing queries to task-matched structures improve RAG reasoning?. Hierarchical designs that separate query planning from answer synthesis point the same way — the efficiency win often comes from architectural separation, not from when the graph was built Do hierarchical retrieval architectures outperform flat ones on complex queries?. And richer representations like hypergraph memory, which binds three-or-more entities into single relations, show the structure choice is also about expressiveness, not just speed Can hypergraphs capture multi-hop reasoning better than graphs?.
The thing you might not have expected to want to know: pre-built knowledge graphs increasingly justify themselves not by retrieval efficiency but by what they *generate* — curricula that teach 32B models domain superintelligence from graph paths Can knowledge graphs teach models deep domain expertise?, and random-walk syntheses that produce hard multi-hop training data for search agents Can knowledge graphs generate training data for search agents?. So query-time logic graphs can plausibly match pre-built indexing on retrieval efficiency for a single shifting corpus — but a pre-built graph is an asset you can mine for far more than answers, and that's a value query-time construction throws away by design.
Sources 9 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.
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.
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.
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.
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.
Fine-tuning a 32B model on 24,000 reasoning tasks derived from medical knowledge graph paths produces state-of-the-art performance across 15 medical domains, demonstrating that structured knowledge composition matters more than scale.
KG-based random walks with selective entity obscuring create verifiable, multi-hop questions that train deep search agents effectively. DeepDive-32B trained on this data achieves 14.8% on BrowseComp, outperforming larger models through end-to-end multi-turn RL.