GraphWalk: Enabling Reasoning in Large Language Models through Tool-Based Graph Navigation

• URL: http://arxiv.org/abs/2604.01610v1
• Date: Thu, 02 Apr 2026 04:43:01 GMT
• Title: GraphWalk: Enabling Reasoning in Large Language Models through Tool-Based Graph Navigation
• Abstract summary: We present GraphWalk, a problem-agnostic, training-free, tool-based framework that allows off-the-shelf LLMs to reason through sequential graph navigation.<n>We evaluate whether models equipped with GraphWalk can compose these operations into correct multi-step reasoning chains.
• Score: 0.2999888908665658
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The use of knowledge graphs for grounding agents in real-world Q&A applications has become increasingly common. Answering complex queries often requires multi-hop reasoning and the ability to navigate vast relational structures. Standard approaches rely on prompting techniques that steer large language models to reason over raw graph context, or retrieval-augmented generation pipelines where relevant subgraphs are injected into the context. These, however, face severe limitations with enterprise-scale KGs that cannot fit in even the largest context windows available today. We present GraphWalk, a problem-agnostic, training-free, tool-based framework that allows off-the-shelf LLMs to reason through sequential graph navigation, dramatically increasing performance across different tasks. Unlike task-specific agent frameworks that encode domain knowledge into specialized tools, GraphWalk equips the LLM with a minimal set of orthogonal graph operations sufficient to traverse any graph structure. We evaluate whether models equipped with GraphWalk can compose these operations into correct multi-step reasoning chains, where each tool call represents a verifiable step creating a transparent execution trace. We first demonstrate our approach on maze traversal, a problem non-reasoning models are completely unable to solve, then present results on graphs resembling real-world enterprise knowledge graphs. To isolate structural reasoning from world knowledge, we evaluate on entirely synthetic graphs with random, non-semantic labels. Our benchmark spans 12 query templates from basic retrieval to compound first-order logic queries. Results show that tool-based traversal yields substantial and consistent gains over in-context baselines across all model families tested, with gains becoming more pronounced as scale increases, precisely where in-context approaches fail catastrophically.

Related papers

• GraphARC: A Comprehensive Benchmark for Graph-Based Abstract Reasoning [28.844098517315228]
  We introduce GraphARC, a benchmark for abstract reasoning on graph-structured data.<n>Each task requires inferring a transformation rule from few input-output pairs applying it to a new test graph.<n>We evaluate state-of-the-art language models on GraphARC and observe clear limitations.
  arXiv  Detail & Related papers  (2026-05-29T09:03:30Z)
• GraphScout: Empowering Large Language Models with Intrinsic Exploration Ability for Agentic Graph Reasoning [46.699075133532595]
  Recent Graph-based Retrieval-Augmented Generation (GraphRAG) methods introduce iterative interaction between knowledge graphs and large language models (LLMs) to enhance reasoning capability.<n>We propose GraphScout, a training-centric agentic graph reasoning framework equipped with more flexible graph exploration tools.
  arXiv  Detail & Related papers  (2026-03-02T03:25:40Z)
• GILT: An LLM-Free, Tuning-Free Graph Foundational Model for In-Context Learning [50.40400074353263]
  Graph Neural Networks (GNNs) are powerful tools for precessing relational data but often struggle to generalize to unseen graphs.<n>We introduce textbfGraph textbfIn-context textbfL textbfTransformer (GILT), a framework built on an LLM-free and tuning-free architecture.
  arXiv  Detail & Related papers  (2025-10-06T08:09:15Z)
• G-reasoner: Foundation Models for Unified Reasoning over Graph-structured Knowledge [88.82814893945077]
  Large language models (LLMs) excel at complex reasoning but remain limited by static and incomplete parametric knowledge.<n>Recent graph-enhanced RAG (GraphRAG) attempts to bridge this gap by constructing tailored graphs and enabling LLMs to reason on them.<n>G-reasoner is a unified framework that integrates graph and language foundation models for reasoning over diverse graph-structured knowledge.
  arXiv  Detail & Related papers  (2025-09-29T04:38:12Z)
• Enrich-on-Graph: Query-Graph Alignment for Complex Reasoning with LLM Enriching [61.824094419641575]
  Large Language Models (LLMs) struggle with hallucinations and factual errors in knowledge-intensive scenarios like knowledge graph question answering (KGQA)<n>We attribute this to the semantic gap between structured knowledge graphs (KGs) and unstructured queries, caused by inherent differences in their focuses and structures.<n>Existing methods usually employ resource-intensive, non-scalable reasoning on vanilla KGs, but overlook this gap.<n>We propose a flexible framework, Enrich-on-Graph (EoG), which leverages LLMs' prior knowledge to enrich KGs, bridge the semantic gap between graphs and queries.
  arXiv  Detail & Related papers  (2025-09-25T06:48:52Z)
• GraphCogent: Mitigating LLMs' Working Memory Constraints via Multi-Agent Collaboration in Complex Graph Understanding [13.356521655409422]
  Large language models (LLMs) show promising performance on small-scale graph reasoning tasks but fail when handling real-world graphs with complex queries.<n>We propose GraphCogent, a collaborative agent framework that decomposes graph reasoning into specialized cognitive processes: sense, buffer, and execute.
  arXiv  Detail & Related papers  (2025-08-17T14:28:38Z)
• GraphRunner: A Multi-Stage Framework for Efficient and Accurate Graph-Based Retrieval [3.792463570467098]
  GraphRunner is a novel graph-based retrieval framework that operates in three distinct stages: planning, verification, and execution.<n>It significantly reduces reasoning errors and detects hallucinations before execution.<n>Our evaluation using the GRBench dataset shows that GraphRunner consistently outperforms existing approaches.
  arXiv  Detail & Related papers  (2025-07-11T18:10:01Z)
• An Automatic Graph Construction Framework based on Large Language Models for Recommendation [49.51799417575638]
  We introduce AutoGraph, an automatic graph construction framework based on large language models for recommendation.<n>LLMs infer the user preference and item knowledge, which is encoded as semantic vectors.<n>Latent factors are incorporated as extra nodes to link the user/item nodes, resulting in a graph with in-depth global-view semantics.
  arXiv  Detail & Related papers  (2024-12-24T07:51:29Z)
• Towards Graph Foundation Models: Learning Generalities Across Graphs via Task-Trees [50.78679002846741]
  We propose a novel approach to cross-task generalization in graphs via task-trees.<n>We show that pretraining a graph neural network (GNN) on diverse task-trees with a reconstruction objective induces transferable knowledge.<n>This enables efficient adaptation to downstream tasks with minimal fine-tuning.
  arXiv  Detail & Related papers  (2024-12-21T02:07:43Z)
• Scalable and Accurate Graph Reasoning with LLM-based Multi-Agents [27.4884498301785]
  We introduce GraphAgent-Reasoner, a fine-tuning-free framework for explicit and precise graph reasoning. Inspired by distributed graph computation theory, our framework decomposes graph problems into smaller, node-centric tasks that are distributed among multiple agents. Our framework demonstrates the capability to handle real-world graph reasoning applications such as webpage importance analysis.
  arXiv  Detail & Related papers  (2024-10-07T15:34:14Z)
• G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering [61.93058781222079]
  We develop a flexible question-answering framework targeting real-world textual graphs. We introduce the first retrieval-augmented generation (RAG) approach for general textual graphs. G-Retriever performs RAG over a graph by formulating this task as a Prize-Collecting Steiner Tree optimization problem.
  arXiv  Detail & Related papers  (2024-02-12T13:13:04Z)
• GraphGPT: Graph Instruction Tuning for Large Language Models [27.036935149004726]
  Graph Neural Networks (GNNs) have evolved to understand graph structures. To enhance robustness, self-supervised learning (SSL) has become a vital tool for data augmentation. Our research tackles this by advancing graph model generalization in zero-shot learning environments.
  arXiv  Detail & Related papers  (2023-10-19T06:17:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.