← Back to Paper Radar

Search-on-Graph: Iterative Informed Navigation for Large Language Model Reasoning on Knowledge Graphs

Jia Ao Sun, Hao Yu, Fabrizio Gotti, Fengran Mo, Yihong Wu, Yuchen Hui, Jian-Yun Nie
arXiv.org | 2025
Search-on-Graph (SoG) lets an LLM answer multi-hop knowledge-graph questions by walking the graph one hop at a time through a single Search function. At each step the model first observes the relations actually available at the current entity, then decides where to go next. This simple observe-then-navigate loop reaches state-of-the-art KGQA performance without fine-tuning.

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

5/10 This is a solid, practical contribution: a simpler sequential tool-use design beats more elaborate KGQA agents, with notable Wikidata gains. Conceptually, though, it refines existing iterative KG-exploration ideas (e.g., Think-on-Graph, ReAct-style agents) rather than introducing a new paradigm.

Methodology

  1. 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.
  2. 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.
  3. 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

Search function

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.

Observe-then-navigate reasoning loop

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.

Adaptive filtering

Handles high-degree nodes by filtering or condensing large relation and neighbor sets, keeping context manageable and reducing noise.

Schema-agnostic adapter

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.

Generated automatically from available metadata and abstract on 2026-11-09.