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.
Figures & tables
Figure 1: Agent exploration of a 10x10 maze mid-traversal at node 24, after calling get_next_possible_cells . Yellow cells (*): tool output, blue (o): visited nodes, black (#): walls, white (.): unvisited path cells, green (s): start, and red (G): goal.
Model
Tools
Correct
Accuracy
Avg IT
Avg TC
gpt-4o-mini
True
8/10
80.00
144.971
22.125
False
0/10
0.00
27.541
-
gpt-4o
True
6/10
60.00
135.196
15.1
False
1/10
10.00
14.159
-
gpt-4.1
True
10/10
100.00
127.299
21.4
False
1/10
10.00
13.060
-
Table 1: Performance of LLM agents in maze traversal (10 mazes × 10 runs). "Tools" = tool use; "Avg IT" = average inference time (s); "Avg TC" = average tool calls. Reasoning models run without tools as a baseline. Best results for non-reasoning and reasoning models in boldface.
Figure 2: An overview of the agentic framework.
Model
T
C
A
P
R
F1
FP
TC
gpt-4o-mini
True
18
15.00
0.23
0.25
0.23
170
7362
False
6
5.00
0.35
0.24
0.26
350
-
gpt-4o
True
34
28.33
0.42
0.39
0.39
235
2548
False
18
15.00
0.50
0.44
0.44
300
-
gpt-4.1
True
35
29.17
0.47
0.41
0.43
232
2483
False
21
17.50
0.52
0.49
0.48
1006
-
Table 2: Performance of LLMs on the query set (120 runs: 12 questions × 10 runs). "T" = tool use; "C" = correct answers; "A", "P", "R", "F1" = average Accuracy, Precision, Recall, F1; "FP" = false positives; "TC" = total tool calls. Reasoning models run without tools as a baseline. Best results for non-reasoning and reasoning models highlighted in boldface.
Category
Total
gpt-4o-mini
gpt-4o
gpt-4.1-nano
gpt-4.1-mini
gpt-4.1
o3-mini
o4-mini
T
NT
T
NT
T
NT
T
NT
T
NT
NT
NT
Node Count
1
0
0
0
0
0
1
0
0
0
0
0
0
Relationship Count
2
0
0
0
0
0
1
0
1
0
0
0
0
Node with Most Relationships
26
3
0
3
0
0
1
3
2
3
2
1
8
Node by Property
85
10
0
10
6
7
0
10
5
10
7
10
10
Relationship by Property
9
0
0
0
0
0
0
1
0
0
0
0
8
Table 3: Performance by question category across both settings. "T"=tool use, "NT"= no-tools.
Figure 3: Effect of graph size on model performance. The number of correct answers (out of 120 total) decreases as graph complexity increases for all models. Tool-equipped models demonstrate better robustness to increasing graph size compared to models without tool access.
Model
Metric
100
150
200
500
gpt-4.1 (w.t)
Acc.
29.17
28.33
28.33
26.67
P.
0.47
0.39
0.40
0.39
R.
0.41
0.37
0.38
0.35
F1
0.43
0.37
0.38
0.35
F.P.
232
149
170
151
gpt-4.1 (w.o.t)
Acc.
17.5
29.17
23.33
10.83
Table 4: Effect of graph size on model performance across node counts. "w.t" = with tools, "w.o.t" = without tools. Acc., P., R., F1, F.P. = average Accuracy, Precision, Recall, F1, and False Positives. Best results at 500 nodes in boldface.
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
#
Entity Type
Entity Name
Cypher Pattern
Property
0
Node
Cevaz
(:Cevaz)
bexame
1
Node
Cevaz
(:Cevaz)
key
2
Node
Cevaz
(:Cevaz)
tanu
…
…
…
…
…
18
Relation-ship
EPUQOSS
(:Cevaz)-[:EPUQOSS]-> (:Egodpw)
ukog
19
Relation-ship
EPUQOSS
(:Cevaz)-[:EPUQOSS]-> (:Egodpw)
uqpc
Appendix
Table 5: A truncated example of the schema provided to the agent for a 100-node graph. The schema lists all node types, relationship types, and their respective properties.
Category
Question Class
Instruction Template
Output Schema
Ground Truth (Cypher)
Retrieval & Aggre-gation
Node Count
Count the number of "{source_label}" nodes that are connected to any "{target_label}" node. Return ONLY the output with the count in JSON format: {{output_schema}}.
[{"count": "number"}]
MATCH (a:{source_label}) --> (b:{target_label}) RETURN count(DISTINCT a) AS count
Relation-ship Count
How many relationships of type "{rel_type_name}" exist? Return ONLY the output with the count in JSON format: {{output_schema}}.
[{"count": "number"}]
MATCH ()-[r:{rel_type_name}]->() RETURN count(DISTINCT r) AS count
Node with Most Relationships
Which "{source_node_label}" node has the most outgoing "{rel_type_name}" relationships? Return ONLY ONE answer in JSON format as per the schema: {{output_schema}}.
[{"node_key": "string", "rel_count": "number"}]
MATCH (n:{source_node_label}) -[r:{rel_type_name}] ->() WITH n, count(r) AS rel_count RETURN n.key AS node_key, rel_count ORDER BY rel_count DESC LIMIT 1
Node by Property
Find all "{node_label}" nodes where "{prop_name}" is "{prop_value}". Return results in JSON format according to the schema: {{output_schema}}.
[{"node_key": "string"}]
MATCH (n:{node_label} { {prop_name}: {query_prop_value} }) RETURN DISTINCT n.key AS node_key
Relation-ship by Property
Find all "{rel_type_name}" relationships where "{prop_name}" is "{prop_value}". Return results in JSON format based on the schema: {{output_schema}}.
Knowledge graphs provide structured and reliable information for many real-world applications, motivating increasing interest in combining large language models (LLMs) with graph-based retrieval to improve factual grounding. Recent Graph-based Retrieval-Augmented Generation (GraphRAG) methods therefore introduce iterative interaction between LLMs and knowledge graphs to enhance reasoning capability. However, existing approaches typically depend on manually designed guidance and interact with knowledge graphs through a limited set of predefined tools, which substantially constrains graph exploration. To address these limitations, we propose GraphScout, a training-centric agentic graph reasoning framework equipped with more flexible graph exploration tools. GraphScout enables models to autonomously interact with knowledge graphs to synthesize structured training data which are then used to post-train LLMs, thereby internalizing agentic graph reasoning ability without laborious manual annotation or task curation. Extensive experiments across five knowledge-graph domains show that a small model (e.g., Qwen3-4B) augmented with GraphScout outperforms baseline methods built on leading LLMs (e.g., Qwen-Max) by an average of 16.7% while requiring significantly fewer inference tokens. Moreover, GraphScout exhibits robust cross-domain transfer performance. Our code will be made publicly available~\footnote{https://github.com/Ying-Yuchen/_GraphScout_}.
Yuchen Ying, Weiqi Jiang, Tongya Zheng +4
Zhejiang University, Hangzhou, China · Hangzhou City University, Hangzhou, China · Nanyang Technological University, Singapore, Singapore
Large Language Models (LLMs) exhibit strong abilities in natural language understanding and generation, yet they struggle with knowledge-intensive reasoning. Structured Knowledge Graphs (KGs) provide an effective form of external knowledge representation and have been widely used to enhance performance in classical Knowledge Base Question Answering (KBQA) tasks. However, performing precise multi-hop reasoning over KGs for complex queries remains highly challenging. Most existing approaches decompose the reasoning process into a sequence of isolated steps executed through a fixed pipeline. While effective to some extent, such designs constrain reasoning flexibility and fragment the overall decision process, often leading to incoherence and the loss of critical intermediate information from earlier steps. In this paper, we introduce KG-Reasoner, an end-to-end framework that integrates multi-step reasoning into a unified "thinking" phase of a Reasoning LLM. Through Reinforcement Learning (RL), the LLM is trained to internalize the KG traversal process, enabling it to dynamically explore reasoning paths, and perform backtracking when necessary. Experiments on eight multi-hop and knowledge-intensive reasoning benchmarks demonstrate that KG-Reasoner achieves competitive or superior performance compared to the state-of-the-art methods. Codes are available at the repository: https://github.com/Wangshuaiia/KG-Reasoner.
Shuai Wang, Yinan Yu
Department of Computer Science and Engineering, Chalmers University of Technology and University of Gothenburg, SE-41296 Gothenburg, Sweden
Knowledge graph question answering (KGQA) requires navigating from topic entities to an answer several relations away. Recent methods prompt a frontier LLM to explore the graph through a retrieval tool, but their reliance on frontier-scale inference makes them costly to deploy. We present Search-on-Graph-R1 (\sogrone{}), which internalizes this navigation into a compact 8B model through supervised fine-tuning (SFT) followed by reinforcement learning (RL). Our central idea is to scaffold a frontier teacher with each question's gold SPARQL query, so the teacher traverses a known answer-bearing path with a live Search tool rather than having to discover the path itself. Since every call executes against a live Freebase server, the resulting trajectories are grounded in the knowledge graph by construction. On WebQSP, CWQ, and GrailQA, \sogrone{} at 8B surpasses every frozen frontier-LLM system in our comparison and posts the strongest results on CWQ of any system we compare against. It does so using no auxiliary module at inference and no LLM judge during training. Isolating each training stage shows that SFT and RL contribute complementary gains, our approach transfers across model families, and RL learns to reach answers in fewer Search calls than its SFT initialization.
Jia Ao Sun, Hao Yu, Fengran Mo +4
Université de Montréal · Mila – Québec AI Institute · McGill University +2