💬 NLP

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

The paper proposes Search-on-Graph (SoG), an iterative "observe-think-navigate" framework that empowers large language models to directly select and traverse reasoning paths within knowledge graphs based on complete reasoning history, thereby outperforming existing methods on KGQA benchmarks without requiring task-specific fine-tuning.

Original authors: Jia Ao Sun, Hao Yu, Fabrizio Gotti, Fengran Mo, Yihong Wu, Yuchen Hui, Zhan Su, Lingfeng Xiao, Jian-Yun Nie

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jia Ao Sun, Hao Yu, Fabrizio Gotti, Fengran Mo, Yihong Wu, Yuchen Hui, Zhan Su, Lingfeng Xiao, Jian-Yun Nie

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Hallucinating" Librarian

Imagine you have a super-smart librarian (a Large Language Model, or LLM) who has read almost every book in the world. This librarian is great at writing stories and answering general questions. But, when you ask a tricky question that requires checking specific facts—like "What is the capital of the country where Vincent van Gogh was born?"—the librarian sometimes gets confident but wrong. They might invent a country or a capital city because they are trying to guess the answer based on patterns rather than facts. This is called "hallucinating."

To fix this, researchers gave the librarian a massive, structured map of facts called a Knowledge Graph (KG). Think of this map as a giant subway system where every station is a fact (like "Van Gogh") and every track is a connection (like "Place of Birth").

The Old Way: The "Guess-and-Check" Tour Guide

Before this new paper, most methods tried to help the librarian navigate this subway map by using a separate "Tour Guide" module.

The Flaw: This Tour Guide would look at the question and the map, then try to guess which tracks to take based on how similar the words sounded.
The Mistake: If the Tour Guide heard "Van Gogh" and "Country," they might jump to a track labeled "Nationality" just because the words sounded similar, even if the map actually had a track called "Place of Birth."
The Result: The librarian would get sent down the wrong path, prune (cut off) the right paths too early, or get lost in a maze of irrelevant tracks. It was like trying to navigate a city by only looking at street names that sounded like your destination, rather than looking at the actual map.

The New Way: "Search-on-Graph" (SoG)

The authors propose a new method called Search-on-Graph (SoG). Instead of hiring a separate Tour Guide, they let the Librarian drive the car themselves, but with a very specific set of rules.

The "Observe-Think-Navigate" Strategy

SoG changes the game by giving the librarian a simple, three-step routine at every single stop on the subway:

Observe: The librarian stops at a station (e.g., "Van Gogh") and looks at the signboard. The signboard lists all the tracks leaving that station (e.g., "Profession," "Date of Birth," "Place of Birth").
Think: The librarian looks at the original question ("Where was he born?") and the history of where they've been. They say to themselves, "I know I'm at Van Gogh. I need to find his birth country. Looking at the signboard, 'Place of Birth' is the only track that makes sense right now."
Navigate: The librarian picks that specific track and moves to the next station (e.g., "Zundert").

The Magic: The librarian doesn't guess based on word similarity. They look at the actual connections available right in front of them and use their reasoning skills to pick the right one.

Handling the "Crowded Stations"

A big problem with these maps is that some stations are incredibly crowded. For example, the station "Netherlands" might have 10,000 tracks leading out of it (people born there, cities inside it, languages spoken, etc.). If you show the librarian all 10,000 tracks at once, their brain (the computer's memory) would explode.

The Solution: The SoG system uses a clever filter.

Step 1: Instead of showing the librarian 10,000 tracks, it first shows them a list of just the types of tracks available (e.g., "Capital," "Language," "Population").
Step 2: The librarian says, "I need the Capital."
Step 3: The system then shows only the tracks related to "Capital."
This turns a chaotic, overwhelming crowd into a manageable, organized line.

Why It Works Better

The paper tested this method on six different "mazes" (datasets) using real-world knowledge graphs like Freebase and Wikidata.

The Result: SoG beat almost every other method, including those that used more powerful computers or complex planning.
The Reason: By letting the LLM look at the actual map and reason through the history of its journey, it avoided the "semantic drift" (getting lost because words sounded similar). It stayed on the logical path.
Efficiency: It was also faster and used fewer computer resources because it didn't waste time exploring dead-end paths or maintaining multiple parallel guesses (like the old "beam search" methods).

The Takeaway

Think of Search-on-Graph as teaching a smart AI to be a detective who checks the evidence at every step, rather than a guesser who relies on hunches. It doesn't need to be retrained for every new puzzle; it just needs to be told to "Look, Think, and Move" using the map provided. This simple, iterative approach proved to be the most reliable way to solve complex fact-based questions.

Technical Summary: Search-on-Graph (SoG)

Problem Statement

Large Language Models (LLMs) augmented with Knowledge Graphs (KGs) offer a promising avenue for knowledge-intensive reasoning. However, existing methods for selecting reasoning paths within KGs face a critical limitation: the selection process is often decoupled from the reasoning requirements. Current approaches typically rely on separate modules or independent criteria (such as semantic similarity to the original question) to prune or select relations. This disconnection leads to two primary failure modes:

Semantic Drift: Exploration diverges from the logical chain required to answer the question because selection is based on surface-level similarity rather than the reasoning history.
Premature Pruning: Logically correct but lexically dissimilar relations are eliminated early, causing the reasoning process to fail.

Furthermore, many existing agentic methods employ complex multi-component architectures (separate planning, retrieval, and reasoning modules) or maintain parallel exploration paths via beam search, which introduces significant memory overhead and computational complexity without guaranteeing reasoning validity.

Methodology: Search-on-Graph (SoG)

The authors propose Search-on-Graph (SoG), a framework that unifies path selection and reasoning within a single LLM. SoG operates on an observe-think-navigate paradigm, where the LLM iteratively traverses the KG by making informed decisions based on the complete reasoning history and the current local graph structure.

Core Components

Iterative 1-Hop Search:
SoG utilizes a single, carefully engineered Search function as the LLM's sole interface for KG exploration. This function retrieves 1-hop neighbors of a given entity in a specified direction (outgoing or incoming).
- Input: Entity ID, direction, and optional properties for filtering.
- Output: A space-efficient markdown table containing property IDs, labels, value IDs, and value labels.
Handling High-Degree Nodes:
To address the challenge of entities with thousands of connections (e.g., countries, celebrities), SoG employs a two-stage filtering mechanism:
- Property Discovery: If a node has more than $k$ neighbors (default $k=50$ ) and no specific properties are requested, the system returns only the unique property types rather than all instances.
- Targeted Retrieval: The LLM analyzes the available properties and makes a second, targeted Search call with specific properties to retrieve only relevant neighbors.
- Truncation: If results still exceed a threshold $p$ (default $p=1000$ ), the list is truncated to fit context limits.
Context-Aware Navigation:
Unlike beam search methods that maintain multiple parallel paths, SoG guides the LLM to select a single relation at each step based on the full reasoning history. The LLM observes the current entity's neighbors, reasons about which path advances the answer (e.g., "I am at Zundert, came from Van Gogh, need the country, so I look for 'Contained by'"), and navigates accordingly. This ensures logical coherence without the noise accumulation of parallel exploration.
Prompting Strategy:
The system uses a system prompt defining the agent's role and a set of few-shot exemplars (typically 5) demonstrating three phases: initial exploration, iterative traversal, and answer extraction. The LLM autonomously determines when sufficient information has been gathered to stop tool calls and provide a final answer.

Key Contributions

A Unified Framework: SoG proposes a simple yet effective KGQA framework where a single LLM orchestrates iterative KG traversal, eliminating the need for separate planning or retrieval modules.
Context-Aware Navigation: The method performs navigation based on the full reasoning history, avoiding the semantic drift common in context-free pruning methods like Think-on-Graph (ToG).
Schema Agnosticism: The approach generalizes across different KG schemas (Freebase and Wikidata) without modification or task-specific fine-tuning.
Efficiency: By selecting single relations per hop rather than maintaining parallel paths, SoG reduces the number of LLM calls and output tokens significantly compared to beam search baselines.

Experimental Results

The authors evaluated SoG on six KGQA benchmarks spanning Freebase (SimpleQA, WebQSP, CWQ, GrailQA) and Wikidata (QALD-9, QALD-10).

Performance: SoG achieved state-of-the-art (SOTA) results on five out of six datasets without any task-specific fine-tuning.
- On Wikidata benchmarks, it demonstrated substantial gains of over 11.3% compared to previous best methods.
- On Freebase datasets, it outperformed prior systems, trailing only by 0.1% on CWQ against Generate-on-Graph.
Backbone Robustness: The framework is compatible with various LLM backbones. It achieved SOTA performance using GPT-4o and also demonstrated strong results with open-source models (Qwen3 series). Notably, even the compact Qwen3-4B model surpassed previous methods on Wikidata benchmarks, proving the method's effectiveness across model sizes.
Efficiency: Compared to the Think-on-Graph baseline, SoG reduced LLM calls by at least 46.4% and output tokens by 69.9%, though it requires more input tokens to maintain the full reasoning context.
Ablation Studies:
- Few-Shot Learning: Performance improved dramatically with just one navigation exemplar, plateauing at 3-5 shots.
- Model Type: "Thinking" (reasoning-optimized) models consistently outperformed standard instruction-tuned models, particularly on multi-hop tasks.
- Output Format: The proposed "Markdown + Property Filter" format achieved the best balance of accuracy and token efficiency.

Significance and Claims

The paper claims that Search-on-Graph validates a new paradigm where LLM-driven navigation is a superior approach to knowledge graph reasoning compared to methods relying on separate selection modules or upfront planning.

The authors argue that the assumption that a single LLM is better equipped to select relevant relations at each step—based on actual reasoning requirements and full context—holds true. This approach simplifies the architecture, reduces computational overhead, and generalizes effectively across different KG schemas and model sizes. The results suggest that architectural simplicity, combined with careful context management, can outperform more elaborate, multi-component systems.