Multi-Hop Reasoning Over Knowledge Graphs at Inference Time

Knowledge graphs store facts as triples: entity, relation, entity. "Berlin, capital-of, Germany" is one edge in a machine-readable, human-interpretable network of facts. Predicting a single missing piece, given two of the three parts of a triple, is a one-step lookup, and most benchmark leaderboards still reward systems for being good at exactly that. Multi-hop reasoning is a different animal. Answering a multi-hop question means walking across several edges in sequence, where each step depends on what the last one turned up, and at inference time the model faces a chain it has never seen before and has to plan its route through the graph as it goes.

A model that has memorized training paths hasn't learned to reason. It's learned to recall, and the field keeps confusing the two because recall scores well on the same benchmarks reasoning does. Real multi-hop reasoning becomes visible only when the graph, the question, and the path are all new to the system at once, which forces it to compose an answer from parts it has never encountered together before.

Core failure modes of multi-hop reasoning

Path counting is the first wall. Every additional hop multiplies the number of candidate routes through the graph, so search that works fine at two or three hops turns into a combinatorial mess at five or six. On a graph with even a modest branching factor, the space of possible paths explodes fast enough that exhaustive search stops being an option.

Scale compounds the problem, and this is where most published research quietly stacks the deck. Benchmarks tend to run on graphs with tens of thousands of entities, small enough to explore fully or close to it. Real-world graphs, the kind behind enterprise search or biomedical databases, run into the millions of entities. Brute-force neighbor expansion and exhaustive beam search work fine on a small dense graph and stop being computationally viable once the graph is a thousand times bigger. Call it what it is: a scale gap, not a size difference, and a model tuned against a small benchmark graph has no built-in reason to survive that jump.

Pipeline fragmentation does quieter damage, and it may be the more consequential failure of the three. Most multi-hop systems break the task into fixed stages: retrieve, then rank, then reason, then answer. Each stage hands off to the next, and the handoff loses context on the way. The reasoning step doesn't know why the retriever picked the facts it picked, so an error introduced early (a wrong intermediate entity, a mismatched relation) never gets corrected later, because later stages have no way to look back and reconsider. The system commits to its first guess and builds forward from it, wrong or not.

Then there's the graph itself. Knowledge graphs are incomplete, always, and reasoning across the missing edges is unavoidable if the system is going to answer anything non-trivial. Every triple a model infers to patch that gap carries uncertainty, and confirming that an inferred fact is actually true remains an open research question. Zhou et al.'s "What Breaks Knowledge Graph Based RAG?" benchmarks this failure mode directly, testing where retrieval-augmented systems break down once the underlying graph has holes in it. Gaps are the normal condition of any graph built from real-world data, and systems that pretend otherwise don't fail loudly. They fail quietly, producing confident answers built on shaky inferred links.

Retrieval-based approaches: offloading traversal to a graph retriever before the LLM reasons

One way around the combinatorial problem is to keep the LLM from ever seeing the whole graph. An external retriever does the traversal work first, pulling out a relevant subgraph or a set of candidate paths, and the LLM only has to reason over that trimmed set. The navigation happens before the language model gets involved at all, and that division of labor is the whole point.

GNN-RAG is a clean version of this. It trains a graph neural network to score how relevant each node is, both to the question directly and to its neighbors, reaching further into the graph than a keyword match ever could. It then retrieves the shortest paths connecting the entities named in the question to the answer candidates the GNN has flagged, and hands those paths to the LLM as context. On multi-hop and multi-entity questions, this setup beats LLM-based retrieval by 8.9 to 15.5 percentage points in answer F1, while feeding the LLM roughly nine times fewer tokens than a long-context approach would need. A 7B fine-tuned model running GNN-RAG matches or beats GPT-4 on the WebQSP and CWQ benchmarks. A smaller model with a better retriever out-argues a much larger one working from raw context. That result deserves more attention than it gets in a field still chasing parameter count as the main lever.

SubgraphRAG takes a related but distinct route, and it scales cleanly with the underlying LLM without needing that LLM fine-tuned for the task specifically. Smaller models reach competitive performance out of the box; larger ones just do better on top of that. Paired with GPT-4o, it hits 90.1 Hits@1 and 77.5 F1 on WebQSP; with the lighter GPT-4o-mini, it reaches 66.7 Hits@1 and 59.1 F1 on CWQ. It also holds up across datasets with different domains and structures, which is the real finding: when the subgraph construction step is designed well, retrieval quality stops being tied to how big the LLM is.

Graph-Constrained Reasoning, or GCR, pairs two models: one specialized for staying inside the graph's actual structure while it reasons, and a second, more general LLM that handles inductive reasoning across the multiple paths the first one surfaces. GCR's traversal is constrained to edges that actually exist in the graph, so it can't invent a path that isn't there, which amounts to zero reasoning hallucination by construction. Paired with GPT-4o-mini, GCR hits 92.2 Hits@1 and 74.1 F1 on WebQSP; paired with ChatGPT, 92.6 Hits@1 and 73.2 F1. It also generalizes to graphs it has never seen during training, with no additional fine-tuning needed, which matters most for anyone deploying this against a graph that changes shape over time.

Agent-based and iterative traversal: letting the LLM navigate the graph step by step

Retrieval-first systems are efficient, but they commit early. Whatever the retriever hands over is what the LLM works with, for better or worse, with no mechanism to reconsider once the traversal is done. Agent-based approaches trade that efficiency for flexibility: instead of retrieving once and reasoning once, the LLM queries the live graph repeatedly, choosing the next relation or entity to explore at each step based on what it's learned so far. Each hop can mean another call to the model, which costs real money and latency, but the payoff is a system that can correct course mid-traversal instead of being locked into an early mistake.

Think-on-Graph, and its successor ToG 2.0, runs this as an LLM-guided beam search directly over the graph. ToG 2.0 extends the original approach with additional context beyond the graph structure alone. ToG paired with GPT-4 reaches 82.6 Hits@1 on WebQSP; ToG 2.0, running on the comparatively lighter GPT-3.5-turbo, reaches 81.1, nearly matching the GPT-4 run with a much cheaper model doing the work.

Paths-over-Graph (PoG) pushes further in a specific direction: it requires no training. Tested with both GPT-3.5-Turbo and GPT-4, it reaches 93.9 Hits@1 on WebQSP and 74.7 on CWQ, among the strongest results reported for a training-free method operating on a live graph rather than a static, pre-processed one. That distinction is not academic. A training-free method can be pointed at a new graph immediately, with no fine-tuning cycle standing between the system and its first real query.

KBQA-o1 swaps the search strategy out entirely, using Monte Carlo Tree Search to plan its traversal instead of beam search. Beam search keeps a fixed number of candidate paths alive at each step and prunes the rest; tree search builds out a broader exploration of branching possibilities before committing to one. It answers the combinatorial explosion more systematically than simply narrowing the beam width, though it comes at a real compute cost the beam-search methods don't pay, and that tradeoff is the one to weigh before reaching for it.

Reinforcement learning as a path through fragmented pipelines

Multi-hop traversal is a sequential decision problem: pick an edge, land on a node, pick the next edge. That maps directly onto reinforcement learning, where an agent picks actions to maximize a reward over a sequence of steps instead of optimizing each step in isolation. RL's real promise here is optimizing the whole path at once, rather than patching each hop independently, which goes straight at the pipeline fragmentation described earlier.

The trouble with classic RL for this task is the reward function, and it's a real trouble, not a footnote. Earlier work applying RL to multi-hop reasoning over temporal knowledge graphs improved interpretability, since the model's path became a legible trace of its reasoning. But manually designing a reward signal for "good path" turns out to be dataset-specific and brittle: small tweaks to how the reward is shaped produce large, often unpredictable swings in what strategy the model learns. Bai, Xiao, and Zhu's approach using Generative Adversarial Imitation Learning sidesteps hand-crafted rewards entirely, treating the reasoning strategy as a generator and the reward function as a discriminator, adversarially trained against each other. That removes the need for a human to guess at reward shaping and lets the system adapt to more complex temporal settings on its own. Their work also finds that encoding time relatively, rather than splicing in raw timestamp embeddings, captures temporal relationships more effectively, particularly for events in the future relative to the query.

KG-Reasoner folds retrieval and reasoning into a single LLM process instead of keeping them as separate pipeline stages, attacking the fragmentation caused by splitting retrieval and reasoning into separate stages head-on rather than working around it. It adds a graph-based backtracking mechanism, so the model can revisit and abandon an incorrect path mid-reasoning instead of being stuck with an early wrong turn. RL trains the model to internalize the graph traversal itself, so path exploration becomes something the model does dynamically rather than something an external pipeline stage does for it. The design draws a clear line back to extended-reasoning models like DeepSeek-R1, which prioritize a thinking phase before producing output, and KG-Reasoner applies that same principle to graph traversal specifically.

Some approaches in this space start from the observation that early-hop errors propagate and compound downstream, motivating pre-processing steps that address data quality before any RL training begins. The underlying intuition is that a cleaner starting point yields more reliable multi-hop chains than tuning the reward signal alone can achieve, and that principle points toward where research effort in this space might most productively go.

Geometric embeddings as an alternative reasoning substrate

A different strategy skips symbolic search altogether and turns reasoning into geometry. Entities get mapped to regions in some geometric space (cones, boxes, balls, depending on the method), and logical operations like conjunction, existential quantification, or transitivity become geometric transformations applied to those regions. Reasoning, in this framing, is movement and intersection in continuous space, not traversal through a discrete graph.

The appeal is interpretability, and it's a real one. If a logical operation is literally a geometric transformation, someone can inspect the latent space and see, in principle, what the model did at each reasoning step. That's a meaningfully different kind of transparency than a neural black box offers. Most geometric methods only go halfway: they geometrize the entities, giving them clean spatial representations, while still handling the logical operations themselves with ordinary neural components. The part of the system doing the actual reasoning work stays an opaque network sitting inside an otherwise legible geometric structure, which undercuts the whole selling point.

GeometrE closes that gap by mapping every logical operation to a purely geometric transformation in the latent space, rather than leaning on a neural layer to handle the operation side. It also introduces a transitive loss function that enforces the logical transitivity rule (if a relates to b, and b relates to c, then a relates to c) across every triple of entities, for all a, b, and c. No prior geometric method enforced that property this completely. GeometrE beats other geometric methods on standard benchmarks and stays competitive with purely neural approaches, though purely neural methods still hold the overall accuracy ceiling. Geometric methods trade some raw performance for transparency that neural methods don't offer. For applications where an auditor needs to see the reasoning step rather than just the output, that's the correct trade to make, not a compromise to apologize for.

Neurosymbolic unification and inference-time KG construction

Neural methods and symbolic methods each have something the other lacks. Neural embeddings and LLMs handle ambiguity, incomplete information, and pattern-matching well. Symbolic logic rules and graph traversal offer exactness and auditability. The trouble is they don't speak the same language: a symbolic rule doesn't translate directly into a neural computation, and closing that representation gap is the actual project of neurosymbolic methods, not a side benefit tacked onto either approach.

Tunsr builds a reasoning graph on the fly, starting from the entity named in the query and expanding outward iteratively, combining symbolic logic rules with neural representations as it builds the reasoning graph, handling multiple applicable rules in a unified reasoning process. It's built for the messy middle ground of real-world tasks, where a purely neural system misses logical precision and a purely symbolic one can't handle ambiguity or noise well enough to be useful on its own.

A related line of work on explainable language reasoning folds in multiple modalities, text, images, and graph structure, all represented inside one shared graph. The architecture splits the work between a planner and an executor. The LLM generates a symbolic plan, constrained so it can't wander outside valid operations, and a separate deterministic graph engine executes that plan and returns an explanation subgraph that can be replayed and checked step by step. That system reaches 79.8% Hits@1 on WebQSP and 49.3 accuracy on OK-VQA, and the architecture's auditability is the actual contribution. That framing responds to a real and uncomfortable problem: chain-of-thought explanations generated by LLMs can look entirely coherent while having nothing to do with how the model actually arrived at its answer. Routing the computation through a deterministic graph engine, kept separate from the LLM's narration of what it's doing, closes the gap between explanation and mechanism instead of just asking the model to explain itself and hoping the explanation happens to be true.

Work on inference-time knowledge graph construction pushes the idea furthest, and it's the approach most likely to matter once static graphs stop being the default. Instead of querying a knowledge graph someone built in advance, the system builds and grows its own graph while it's answering the question, in three stages: iteratively build and refine a reasoning graph by combining the LLM's internal knowledge with external retrieval. Tested on CWQ, HotpotQA, and SimpleQA, this approach shows consistent gains in factual accuracy, answer precision, and interpretability over both plain prompting and methods that rely on a static, pre-built graph. The graph doesn't have to exist before the reasoning starts. It gets assembled at the moment the question is asked, purpose-built for that one query, and checked against the outside world only where the model's own confidence runs thin.