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

AI summary

Overview

Research area: Natural Language Processing / Knowledge Graph Question Answering (KGQA), specifically tool-augmented LLM agents that navigate structured knowledge graphs for multi-hop reasoning.

Technical level: Intermediate. The core idea is conceptually simple (one LLM, one search tool), but full appreciation requires familiarity with knowledge graphs, multi-hop reasoning, and agentic LLM tool-calling.

One-sentence scope: The paper introduces Search-on-Graph (SoG), a training-free framework in which a single LLM iteratively navigates a knowledge graph via 1-hop Search calls, choosing each relation itself based on the full reasoning history, and reports exact-match results on six Freebase and Wikidata benchmarks.

What This Paper Is About

Large language models hallucinate, carry outdated parametric knowledge, and lack domain expertise, which makes knowledge-intensive multi-hop reasoning unreliable. Augmenting LLMs with knowledge graphs helps, but existing KGQA systems select reasoning paths using separate modules whose criteria (mostly semantic similarity to the original question) are only weakly tied to what the reasoning actually requires — causing wrong relation choices and premature pruning of correct paths. SoG's goal is to close that gap by letting the LLM itself observe the KG's available relations at each entity and navigate using the complete reasoning history.

Key Contributions

1. The SoG framework: A simple KGQA method where a single LLM drives iterative 1-hop exploration through one Search function, exploiting the LLM's own reasoning rather than separate selection, planning, or pruning modules.
2. Context-aware navigation: Unlike beam-search methods with context-free pruning, SoG bases every relation selection on the full reasoning history and the currently available KG neighborhood, avoiding semantic drift and parallel exploration paths.
3. Extensive evaluation: Experiments on six KGQA benchmarks spanning Freebase and Wikidata show state-of-the-art results on five of six datasets with no task-specific fine-tuning, including gains of over 11.3% on Wikidata-based benchmarks.
4. Validation of a paradigm: The study argues that LLM-driven navigation is an effective and schema-generalizable approach to knowledge graph reasoning, and that it holds even with compact open-source models.

Main Findings

• State-of-the-art on five of six benchmarks: SoG + GPT-4o scores 84.8 (SimpleQA), 91.3 (WebQSP), 75.1 (CWQ), 86.9 (GrailQA), 79.4 (QALD-9) and 74.4 (QALD-10). It trails only Generate-on-Graph on CWQ, by 0.1% (75.2 vs. 75.1).
• Gains scale with KG type: Improvements over previous best methods are +0.3% on WebQSP, +2.2% on GrailQA, +8.3% on SimpleQA, and double-digit on Wikidata: +12.7% on QALD-9 and +11.3% on QALD-10.
• Backbone comparison favors open models on several datasets: With Qwen3 backbones, Qwen3-4B reaches 76.3/80.1/56.1/80.4/75.4/69.4; Qwen3-30B reaches 86.2/88.2/70.0/81.4/81.0/77.5; Qwen3-235B reaches 86.4/89.3/77.1/83.9/82.5/79.8 across SimpleQA, WebQSP, CWQ, GrailQA, QALD-9, QALD-10. Qwen3-235B leads on four of six datasets, while GPT-4o leads on WebQSP and GrailQA.
• Even a 4B model surpasses prior work on Wikidata: Qwen3-4B achieves 75.4% on QALD-9 (previous best 66.7%) and 69.4% on QALD-10 (previous best 63.1%).
• GPT-4o comparison is methodologically fair: Reproduced ToG with GPT-4o drops substantially versus ToG with GPT-4 (e.g., 80.2 vs. 82.6 on WebQSP; 48.9 vs. 69.5 on CWQ), so SoG's lead is attributed to method rather than a stronger backbone.
• Efficiency trade-off: SoG uses at least 46.4% fewer LLM calls and 69.9% fewer output tokens than ToG, but at least 2.6x more input tokens because it keeps the full search history. It is 2.0x faster on WebQSP and 3.1x faster on GrailQA, but 1.4x slower on CWQ.
• Question-type breakdown on CWQ: SoG improves on all types over ToG, with the largest gains on Comparative (+32.9%) and Composition (+27.7%). Both methods are weakest on Superlative questions, which require retrieving and comparing complete candidate lists from high-degree nodes.
• High-degree handling matters: The two-stage mechanism (property discovery when neighbors exceed k = 50, truncation at p = 1000) lets the LLM survey relations first, then do targeted retrieval. The "Markdown + Property Filter" format gives the best accuracy (78.0 EM) and lowest total tokens (5622.5) on the SimpleQA 20% sample, versus JSON (76.5 EM, 12047.3 tokens) and plain Markdown (74.5 EM, 7981.8 tokens).
• Few-shot behavior: Performance jumps from IO prompting to 0-shot with tool definitions, rises again with one navigation exemplar, and plateaus at 3-shot. The Thinking variant consistently beats the Instruct variant, with the largest gap on multi-hop datasets.

Methodology in Plain English

The researchers built a loop in which a single LLM answers a question by walking a knowledge graph one step at a time.

• One tool only. The LLM can call Search(entity, direction, properties). direction is either outgoing (the entity is the subject) or incoming (the entity is the object), and properties optionally filters to specific relations. The tool returns a markdown table with a row count and four columns: property ID, property label, value ID, value label.
• Observe-think-navigate. At each step the LLM sees what relations are actually attached to the current entity, reasons about which one advances the question given where it came from and why, then navigates. When it decides it has enough evidence, it stops calling tools and answers — there is no external stopping rule.
• Handling huge nodes. Countries or celebrities can have thousands of edges. If an entity has more than k = 50 neighbors and no property filter is given, the tool returns only the distinct list of available properties; the LLM then makes a targeted second call. Results are also truncated to the first p = 1000 triples.
• Prompting. A system prompt defines the agent's role and tells it to keep searching until it can answer. Five hand-written exemplars demonstrate the three phases: initial exploration from the topic entity, iterative traversal, and final answer extraction.
• A worked example. For "What is the capital of Vincent van Gogh's birth country?", the LLM follows Van Gogh → Zundert (place of birth) → Netherlands (contained by) → Amsterdam (capital). The paper notes that if an alternative schema linked Van Gogh directly to Netherlands via a "country of birth" relation, the LLM would take the shorter path — this is the schema-agnosticism claim.
• Evaluation setup. Gold entity linking is taken from the datasets, so the work isolates the reasoning stage. The metric is exact match accuracy (Hits@1). Six benchmarks are used: SimpleQA (14,894 train / 1,000 test), WebQSP (3,098 / 1,639), CWQ (27,734 / 3,531) and GrailQA (44,337 / 1,000) on Freebase, and QALD-9 (371 / 136) and QALD-10 (412 / 394) on Wikidata. For SimpleQA and GrailQA, the 1,000-sample test subset from Sun et al. (2024) is used; other datasets use full test sets. Comparison is against 22 baselines, with semantic parsing methods excluded because they rely on task-specific fine-tuning.

Why This Matters

The paper argues that complex multi-module pipelines for KGQA may be unnecessary: a single LLM with one well-designed tool and good context management can outperform them, while being cheaper in calls and output tokens and transferable across KG schemas without training.

Real-world applications:

• Enterprise and domain assistants: answering questions over internal knowledge graphs (products, suppliers, compliance relations) where factual traceability matters.
• Open-web and encyclopedic question answering: multi-hop queries over Wikidata-style graphs, where the method showed its largest gains.
• Clinical and scientific knowledge bases: multi-hop reasoning over curated relations such as drug–gene–disease links, where hallucination and stale knowledge are costly.
• Cost-sensitive deployments: the results with Qwen3-4B suggest viable deployment on small open models rather than proprietary APIs.

Industry relevance: the reduction of at least 46.4% in LLM calls and 69.9% in output tokens directly lowers inference cost per query, and the training-free, schema-agnostic design lowers the engineering cost of adapting to a new graph. The stated limitation is higher input-token usage due to retained search history, which matters for long-reasoning datasets like CWQ.

Future Directions

• Cutting input-token cost: SoG needs at least 2.6x more input tokens than ToG and is 1.4x slower on CWQ; compressing or summarizing search history is an obvious next step.
• Improving Superlative questions: both SoG and ToG score lowest on this type, which requires enumerating and comparing complete candidate lists from high-degree nodes — a retrieval/aggregation problem the current design does not solve.
• Reducing dependence on model reasoning capacity: the Thinking variant outperforms the Instruct variant and the gap is widest on multi-hop datasets, so how far the approach scales down to weaker or smaller models remains open.
• Beyond gold entity linking: the experiments use dataset-provided gold entity links and evaluate only on Freebase and Wikidata; end-to-end performance with automatic entity linking and on other schemas is not reported.

Target Audience

Researchers and practitioners in natural language processing, knowledge graph reasoning, and LLM agent design; engineers building question-answering systems over structured knowledge bases; and readers interested in tool-augmented LLMs, multi-hop reasoning, and training-free methods. The paper is most useful to those who already understand KGQA pipelines and agentic tool-calling, and who want evidence on how much of that complexity is actually necessary.

Authors’ abstract

Large language models (LLMs) augmented with knowledge graphs (KGs) offer a promising approach for knowledge-intensive reasoning. Central to this approach is the selection of appropriate reasoning paths in the KG. Yet, existing methods face a common limitation: reasoning path selection is often performed by separate modules using criteria that are only weakly connected to the reasoning requirements. This often results in selecting incorrect relations or premature pruning of relevant paths. We propose Search-on-Graph (SoG), a method that strengthens the connection between path selection and reasoning by having the LLM itself select which relations to follow, informed by both the available KG structure and the complete reasoning history. SoG follows an \textit{observe-think-navigate} paradigm: at each step, the LLM observes the relational connections available at the current entity, reasons about which path best advances toward answering the question, and navigates accordingly. This context-aware navigation fully exploits the LLM's reasoning capabilities rather than relying on independent selection modules with surrogate criteria. Experiments on six knowledge graph question answering (KGQA) benchmarks demonstrate that SoG outperforms state-of-the-art methods while requiring no task-specific fine-tuning and generalizing across different KG schemas.