Search-on-Graph: Iterative Informed Navigation for Large Language Model Reasoning on Knowledge Graphs
Problem Statement
LLMs are unreliable on knowledge-intensive multi-hop questions: they miss long-tail facts, hallucinate, and rely on stale parametric knowledge. Existing KGQA methods each have a weakness. Generating full SPARQL queries without knowing the schema is brittle. Retrieving large subgraphs floods the context with noise. Multi-agent or parallel-exploration frameworks blow up the search space. A grounded, schema-agnostic, low-overhead way to navigate KGs is needed.
Key Novelty
- An 'observe-then-navigate' paradigm: the LLM inspects the real outgoing relations of the current entity before choosing each hop, replacing pre-planned paths or full query compilation.
- A single, carefully designed Search function as the only tool interface. This shows that a minimal tool can beat complex agent frameworks with parallel exploration.
- Adaptive filtering for high-degree nodes plus schema-agnostic design, so the same framework transfers across Freebase and Wikidata without fine-tuning.
Evaluation Highlights
- State-of-the-art results across six KGQA benchmarks spanning Freebase and Wikidata, with no model fine-tuning.
- Roughly +16% improvement over the previous best methods on Wikidata benchmarks, with consistent but smaller gains on Freebase benchmarks.
Signal Assessment
Methodology
- Start from a topic entity linked from the question. Call the Search function to list the actual relations (and neighbors) available from that entity in the KG.
- Have the LLM reason over the observed relations and choose the next hop. When the entity has a very large neighborhood, adaptive filtering narrows the candidates.
- Repeat observe-then-navigate hop by hop, sequentially rather than in parallel, until the LLM judges it has gathered enough evidence. Then produce the final answer grounded in the traversed path.
System Components
The single tool interface to the KG. It returns the relations and connected entities available from a given entity, exposing the real schema to the LLM at each step.
An iterative LLM agent loop. The model looks at available relations before committing to each hop, which avoids brittle pre-planned queries and hallucinated relations.
Handles high-degree nodes by filtering or condensing large relation and neighbor sets, keeping context manageable and reducing noise.
Lets the same navigation procedure work across different KG schemas (Freebase, Wikidata) without retraining or schema-specific engineering.
Results
| Metric/Benchmark | Baseline | This Paper | Delta |
|---|---|---|---|
| Wikidata KGQA benchmarks (accuracy) | Previous best methods | SoG (SOTA) | ~+16% |
| Freebase KGQA benchmarks (accuracy) | Previous best methods | SoG (SOTA) | Consistent improvements (magnitude not specified in abstract) |
| Overall (6 benchmarks) | Prior KGQA methods (SPARQL generation, subgraph retrieval, agent frameworks) | SOTA without fine-tuning | Gains across all six benchmarks |
Key Takeaways
- For tool-using agents over structured data, letting the model observe the actual available options before acting is more robust than having it generate full queries blind. Ground each decision in the environment's real state.
- A minimal, well-designed tool interface with sequential reasoning can beat complex multi-agent or parallel-exploration frameworks. Simplicity also lowers cost and search-space blowup.
- Handling high-degree nodes through adaptive filtering is essential for practical KG agents. Budget context carefully when exposing graph neighborhoods to LLMs, especially on large, heterogeneous KGs like Wikidata.
Abstract
Large language models (LLMs) have demonstrated impressive reasoning abilities yet remain unreliable on knowledge-intensive, multi-hop questions -- they miss long-tail facts, hallucinate when uncertain, and their internal knowledge lags behind real-world change. Knowledge graphs (KGs) offer a structured source of relational evidence, but existing KGQA methods face fundamental trade-offs: compiling complete SPARQL queries without knowing available relations proves brittle, retrieving large subgraphs introduces noise, and complex agent frameworks with parallel exploration exponentially expand search spaces. To address these limitations, we propose Search-on-Graph (SoG), a simple yet effective framework that enables LLMs to perform iterative informed graph navigation using a single, carefully designed \textsc{Search} function. Rather than pre-planning paths or retrieving large subgraphs, SoG follows an ``observe-then-navigate''principle: at each step, the LLM examines actual available relations from the current entity before deciding on the next hop. This approach further adapts seamlessly to different KG schemas and handles high-degree nodes through adaptive filtering. Across six KGQA benchmarks spanning Freebase and Wikidata, SoG achieves state-of-the-art performance without fine-tuning. We demonstrate particularly strong gains on Wikidata benchmarks (+16\% improvement over previous best methods) alongside consistent improvements on Freebase benchmarks.