GraphDancer: Training LLMs to Explore and Reason over Graphs via Curriculum Reinforcement Learning

Yuyang Bai; Zhuofeng Li; Ping Nie; Jianwen Xie; Yu Wang; Yu Zhang

cs.LGJan 24, 2026

GraphDancer: Training LLMs to Explore and Reason over Graphs via Curriculum Reinforcement Learning

Authors: Yuyang Bai, Zhuofeng Li, Ping Nie, Jianwen Xie, Yu Wang, Yu Zhang

Organizations: Texas A&M University · University of Waterloo · Lambda · University of Oregon

Abstract

Large language models (LLMs) increasingly rely on external knowledge to improve factuality, yet many knowledge sources on the Web, such as scholarly indexes and product catalogs, are organized as heterogeneous graphs. Reasoning over such graph-structured knowledge poses two key challenges: (1) navigating structured, schema-defined relations requires precise function calls beyond similarity-based retrieval, and (2) answering complex questions often demands multi-hop evidence aggregation through iterative information seeking. We study how LLMs can learn these interaction capabilities and transfer them to unseen domains. We propose GraphDancer, a reinforcement learning (RL) framework that teaches LLMs to navigate graphs by interleaving reasoning and function execution. To improve RL for moderate-sized LLMs, we introduce a graph-aware curriculum that schedules training by the structural difficulty of questions using an easy-to-hard biased sampler. We evaluate GraphDancer on the multi-domain GRBench benchmark, training only on Academic and Biomedical graphs. Testing covers held-out questions from these domains as well as unseen E-commerce, Literature, and Legal graphs. With either Qwen2.5-3B-Instruct or Qwen3-14B as the backbone, GraphDancer outperforms graph-agent baselines using the same backbone across all evaluation domains. These results indicate that the learned graph exploration and reasoning capabilities transfer across domains. On average across unseen domains, GraphDancer with a 14B backbone also outperforms baselines powered by the closed-source models GPT-4.1-mini and GPT-5-nano. Trajectory analyses further show that GraphDancer retrieves answer-bearing evidence more often and achieves higher accuracy when such evidence is found, while substantially reducing invalid-protocol outcomes.

Figures & tables

Figure 1. Overview of the GraphDancer framework. (a) The graph-aware curriculum shifts question sampling from easy to hard with a biased mixture. (b) Graph functions with example inputs and outputs. (c) In each round, the policy LLM reasons, calls one graph function, and receives the observation, until it answers or reaches the interaction limit. (d) An outcome and format reward on the transcript drives the PPO update. Four-panel overview. (a) The graph-aware curriculum (Easy, Medium, Hard, biased sampler) supplies the training question. (b) The four graph functions with an example input and output each. (c) One interaction round, in which the policy LLM reasons, issues a graph function call, and receives the observation from a heterogeneous graph environment, repeating until it answers or reaches the interaction limit. (d) The transcript receives an outcome and format reward, from which the advantage is estimated for the PPO update.

Difficulty	Train	Val.	Test	E-com.	Lit.	Legal	All test
	In-domain			Unseen-domain test
Easy	234	40	66	80	130	80	356
Medium	273	33	77	10	30	50	167
Hard	242	34	71	70	70	30	241
OOD	0	0	0	40	10	20	70
Total	749	107	214	200	240	180	834

Table 1. GRBench questions by difficulty group and partition. In-domain columns pool Academic and Biomedical .

In-domain

E-commerce

Literature

Legal

AVG

\Delta

Method

Backbone

R-L

TextRAG ( Jin et al., 2024 )

GPT-3.5-turbo

–

14.06

20.00

10.04

20.83

18.14

23.89

–

+304.9

+166.3

GraphRAG ( Jin et al., 2024 )

GPT-3.5-turbo

–

17.52

28.00

14.94

24.17

18.66

22.22

–

+219.9

+134.9

Graph-MCTS ( Liu, 2025b )

Mixtral-8x7B-Instruct

–

33.71

37.22

37.52

45.83

26.23

27.78

–

+71.7

+61.6

Graph-O1 ( Liu, 2025a )

Mixtral-8x7B-Instruct

–

34.61

38.76

38.42

45.83

27.36

32.20

–

+66.2

+50.0

Graph-CoT ( Jin et al., 2024 )

GPT-3.5-turbo

–

42.40

44.50

41.59

46.25

30.52

28.33

–

+46.3

+52.4

Table 2. Main GRBench results, grouped by method. Results for TextRAG, GraphRAG, and Graph-CoT (GPT-3.5-turbo) are taken from ( Jin et al., 2024 ) , and those for Graph-MCTS and Graph-O1 from ( Liu, 2025a ) . R-L: ROUGE-L (%). GS: GPTScore (%). AVG: equal-weight mean across the four evaluation settings. Bold: best score per column.

\Delta

% reports the relative gain of GraphDancer over each baseline, averaged across the evaluation settings reported for that baseline. Each gain is computed as

100(s^{\ast}-s)/s

, where

s^{\ast}

is the GraphDancer score and

s

is the baseline score. R-L and GS gains are averaged separately. –: unreported or inapplicable.

Figure 2. AVG R-L and GS with each Qwen backbone. Graph-CoT and Graph Counselor use the models before our RL training. Grouped bar chart of AVG R-L and GS (%) for Graph-CoT, Graph Counselor, and GraphDancer. With Qwen2.5-3B-Instruct, R-L is 36.22, 31.74, and 45.02, and GS is 39.28, 35.15, and 48.59. With Qwen3-14B, R-L is 48.54, 40.72, and 55.96, and GS is 52.71, 45.40, and 58.64.

Method	In-domain	E-commerce	Literature	Legal	AVG
Vanilla PPO	42.81	44.86	45.65	34.97	42.07
Static Mixture	37.83	41.99	43.19	28.37	37.85
Hard-to-Easy	42.31	45.85	44.14	29.50	40.45
Fast Pacing	39.09	44.90	45.89	36.77	41.66
Pure E2H	39.48	46.59	48.25	35.04	42.34
GraphDancer	45.65	48.92	46.89	38.62	45.02

Table 3. R-L (%) on the test partition for the question-sampling schedules of Section 3.3 , each trained with PPO on Qwen2.5-3B-Instruct. In-domain: pooled. AVG: equal-weight mean. Bold: best per column.

	In-domain			E-commerce				Literature				Legal
Method	Easy	Medium	Hard	Easy	Medium	Hard	OOD	Easy	Medium	Hard	OOD	Easy	Medium	Hard	OOD
Graph-CoT (3B)	59.26	23.88	7.49	82.50	3.90	27.10	4.94	60.51	4.81	22.38	2.22	65.58	6.32	1.42	6.43
Graph Counselor (3B)	57.24	22.83	5.74	77.59	1.17	28.73	4.66	61.73	2.15	27.70	3.45	32.92	0.00	0.00	3.92
GraphDancer (3B)	72.57	39.05	27.77	87.16	2.74	37.23	4.42	64.11	1.62	40.82	1.33	71.13	19.88	6.17	4.11
Graph-CoT (14B)	71.00	54.00	28.97	83.75	0.00	37.94	4.49	66.90	6.38	43.07	0.87	71.83	37.98	3.85	25.04
Graph Counselor (14B)	71.53	57.95	31.65	65.13	0.00	32.08	4.88	66.58	17.60	38.77	2.03	47.50	0.00	0.67	2.00

Table 4. Difficulty-wise R-L (%) on the test partition. OOD keeps GRBench’s original hard question types, all in the unseen domains, separate from our Easy/Medium/Hard levels. All cells average unstemmed per-question ROUGE-L. Bold: best per column within each backbone. Counts: Table 1 .

Panel of Figure 3 — Figure 3. Case study. Vanilla PPO calls NeighbourCheck on the product name, while GraphDancer first resolves the name to a node ID with RetrieveNode . Red marks the round with the failed call and teal the decisive calls. Complete trajectories appear in Appendix B.4 . A rounded box shows an unseen E-commerce question and two tagged trajectories with the Qwen2.5-3B-Instruct backbone. Vanilla PPO calls NeighbourCheck with the product name, receives an error that the node or neighbor type does not exist, and answers that the price cannot be determined. GraphDancer retrieves the item node, finds its bought-together neighbor, reads that neighbor's price, and answers 44.99, the gold answer.

Figure 4. Outcomes on all 834 test questions. Graph-CoT uses the model before our RL training. Vanilla PPO and GraphDancer apply uniform and curriculum training, respectively. Each episode takes the first matching category, checked from the bottom of each bar upward. Percentages label the segments. Five vertical stacked bars in two groups. In the Qwen2.5-3B-Instruct group, Graph-CoT has correct, unfinished-at-limit, invalid-protocol, and other-wrong counts of 261, 157, 229, and 187, Vanilla PPO has 309, 79, 179, and 267, and GraphDancer has 334, 88, 46, and 366. In the Qwen3-14B group, Graph-CoT has 370, 202, 160, and 102, and GraphDancer has 426, 189, 59, and 160, out of 834 questions each.

Qwen2.5-3B-Instruct
Method	In-domain	E-commerce	Literature	Legal
Graph-CoT	32.24	60.00	46.25	47.22
Vanilla PPO	49.53	69.00	67.08	70.00
GraphDancer	86.92	90.50	88.33	77.78
Qwen3-14B
Graph-CoT	32.71	30.50	39.17	27.78

Table 5. Valid-format rates (VF, %) for single-agent protocols. Bold: best per column within each backbone.

Qwen2.5-3B-Instruct
Method	EH	EM $\land$ EH	$\mathrm{P}(\mathrm{EM}\mid\mathrm{EH})$	$\mathrm{P}(\mathrm{EM}\mid\neg\mathrm{EH})$	EM
Graph-CoT	47.12	29.02	61.58	4.31	31.29
Graph Counselor	48.68	23.62	48.52	1.87	24.58
GraphDancer	53.36	37.41	70.11	5.66	40.05
Qwen3-14B
Graph-CoT	60.31	42.21	69.98	5.44	44.36

Table 6. Evidence-grounded accuracy (%) pooled over 834 test questions. EH: evidence hit. EM: strict exact match. EM

\land

EH measures how often an answer is correct and has a hit. The two conditional columns give EM after a hit and after a miss. Bold: best per column within each backbone.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Setting	Qwen2.5-3B	Qwen3-14B
Training / validation / in-domain test	749 / 107 / 214
Unseen-domain test questions	620
Training updates	200
Trajectories / minibatch	128 / 128
Rollouts per question / epochs	1 / 1
Actor / critic learning rate	$10^{-6}$ / $10^{-5}$

Appendix

Table 7. Training and rollout settings (Qwen2.5-3B: Qwen2.5-3B-Instruct). Each context limit caps the tokens of its component separately.

Task	Solve a question answering task by repeating bundled steps that contain reasoning (<think>...</think>) followed by exactly one graph interaction (<graph>...</graph>). After each <graph> call, the environment returns feedback inside <information>...</information>. You may take as many steps as necessary.
Protocol	Output protocol (bundled steps): - Intermediate step (must include BOTH in a single output, in this order): <think>...</think><graph>Function[...]</graph> (Then the environment responds with <information>...</information>.) - Final step (no more graph calls): <think>...</think><answer>...</answer>
Functions	Available graph interaction functions (use exactly these names and signatures INSIDE <graph>...): - RetrieveNode[keyword] # retrieves the related node from the graph according to the query - NodeFeature[Node, feature] # returns detailed attribute information of Node for the given "feature" key - NodeDegree[Node, neighbor_type] # returns the number of "neighbor_type" neighbors of Node - NeighbourCheck[Node, neighbor_type] # lists the "neighbor_type" neighbors of Node and returns them
Rules	Rules and format: 1) You MUST conduct reasoning inside <think>...</think> before every graph call and after every <information> you receive. 2) Inside <graph>...</graph>, issue EXACTLY ONE function from the list below per step. Do NOT include any other text in <graph>. 3) Do NOT fabricate <information>; it is ONLY produced by the environment immediately after your <graph> step. 4) Keep thoughts concise and ONLY inside <think>. Do NOT put a graph call inside <think>, and do NOT put thoughts inside <graph>. 5) The final output MUST contain ONLY one <answer>...</answer> block with the requested node main features (e.g., names), not node IDs.
Examples	Here are some examples: {examples} (END OF EXAMPLES)
Graph schema	Definition of the graph: {graph_definition}
Question	Question: {question}

Appendix

Table 8. Shared instruction template, with domain-specific content shown as placeholders.

Method	R-L	GS	R-L	GS	R-L	GS	R-L	GS	R-L	GS	R-L	GS
	In-domain		E-commerce		Literature		Legal		AVG		$\Delta$ %
Graph-CoT ( Jin et al., 2024 )	29.36	32.24	43.67	45.00	40.00	45.42	31.85	34.44	36.22	39.28	$+26.5$	$+25.2$
Graph Counselor ( Gao et al., 2025 )	27.77	28.50	42.19	41.00	41.93	48.33	15.06	22.78	31.74	35.15	$+62.2$	$+47.3$
GraphDancer	45.65	45.33	48.92	50.00	46.89	54.58	38.62	44.44	45.02	48.59	–	–

Appendix

Table 9. Results with Qwen2.5-3B-Instruct. Both baselines run the original backbone. Columns follow Table 2 . Bold: best per column.

\Delta

%: per-column gain

100\,(s^{\ast}-s)/s

of GraphDancer (3B,

s^{\ast}

) over the row (

s

), averaged over the four domain columns, for R-L and GS separately.

Domain	Method	VF	VC	EH
	Graph-CoT (3B)	32.24	97.59	39.72
	Graph Counselor (3B)	–	–	47.66
	Vanilla PPO (3B)	49.53	95.02	48.60
	GraphDancer (3B)	86.92	96.89	53.27
	Graph-CoT (14B)	32.71	99.74	61.68
In-domain	GraphDancer (14B)	67.29	100.00	66.82

Appendix

Table 10. Behavioral analysis (%). VF (valid format) measures complete protocol conformity over questions, VC (valid calls) basic syntax validity over proposed calls, and EH lexical evidence hit over questions. – denotes an inapplicable metric.

	In-domain			E-commerce			Literature			Legal
Method	VF	VC	EH	VF	VC	EH	VF	VC	EH	VF	VC	EH
Easy
Graph-CoT (3B)	57.58	100.00	48.48	90.00	100.00	87.50	69.23	100.00	70.77	68.75	96.03	71.25
Graph Counselor (3B)	–	–	53.03	–	–	82.50	–	–	77.69	–	–	53.75
Vanilla PPO (3B)	72.73	99.58	56.06	88.75	99.50	87.50	90.00	100.00	72.31	78.75	89.02	71.25
GraphDancer (3B)	95.45	98.01	56.06	100.00	99.45	93.75	94.62	98.14	75.38	90.00	91.30	77.50

Appendix

Table 11. Behavior by analysis group (%). VF, VC, and EH follow Table 10 , and Table 1 gives counts. – marks an inapplicable protocol metric or an empty subset. The four panels are mutually exclusive. OOD retains the original question-type subset.

		Vanilla PPO (3B)			GraphDancer (3B)			Graph-CoT (14B)			GraphDancer (14B)
Group	$n$	Calls	EH	Limit	Calls	EH	Limit	Calls	EH	Limit	Calls	EH	Limit
Easy	356	2.87	72.47	2.53	2.92	76.40	2.53	2.45	81.18	8.15	2.61	83.99	3.93
Medium	167	5.92	28.74	20.36	6.43	37.72	25.15	5.83	49.10	38.32	5.96	57.49	28.74
Hard	241	5.10	39.00	11.62	5.49	41.91	13.28	5.89	51.04	33.61	6.44	53.53	40.66
OOD	70	4.09	12.86	11.43	4.60	12.86	7.14	6.16	12.86	40.00	7.47	12.86	41.43

Appendix

Table 12. Search behavior across all 834 test questions in four mutually exclusive groups.

n

: questions per group. Calls: mean proposed graph calls per question. EH: evidence hit (%). Limit: episodes unfinished at the interaction limit (%).

	Simple lookup ( $n{=}37$ )		Aggregation ( $n{=}29$ )		Multi-hop ( $n{=}21$ )		Set operations ( $n{=}5$ )
Method	EM	R-L	EM	R-L	EM	R-L	EM	R-L
Graph-CoT (3B)	45.95	55.62	55.17	55.17	33.33	34.38	0.00	27.43
Graph Counselor (3B)	48.65	55.87	48.28	48.28	28.57	29.32	0.00	16.26
Vanilla PPO (3B)	51.35	56.80	58.62	58.62	33.33	39.11	20.00	58.14
GraphDancer (3B)	51.35	56.35	65.52	65.52	38.10	43.24	20.00	70.22
Graph-CoT (14B)	51.35	58.76	72.41	72.41	42.86	42.86	60.00	61.50

Appendix

Table 13. Question-type breakdown on 92 of the 240 Literature questions (%). EM: normalized exact match. R-L: stemmed ROUGE-L.

n

: questions per type, assigned by ordered matching of question text.

Panel of Figure 5 — Figure 5. Complete trajectories of Vanilla PPO (upper) and GraphDancer (lower) for Figure 3 . Vanilla PPO makes one graph call and GraphDancer makes three, answering “Not possible to determine” and 44.99 (gold), respectively. Tag colors follow Figure 1 . Two stacked boxes contain all recorded rounds for Vanilla PPO (two) and GraphDancer (four), including reasoning, graph calls, observations, and the final answers ``Not possible to determine'' and 44.99, respectively.

LLM Reasoning with Graphs

Large language model reasoning with graphs uses structured relationships to support multi-step inference, evidence retrieval, and planning.

See all 210 papers

GraphScout: Empowering Large Language Models with Intrinsic Exploration Ability for Agentic Graph Reasoning
Mar 2, 2026Yuchen Ying, Weiqi Jiang, Tongya Zheng +4LLM Reasoning with Graphs Agentic RAG
Zhejiang University, Hangzhou, China · Hangzhou City University, Hangzhou, China · Nanyang Technological University, Singapore, Singapore
Position: How can Graphs Help Large Language Models?
May 4, 2026Xiyuan Wang, Yi Hu, Yanbo Wang +2LLM Grounding Knowledge Augmentation for Language Models
Institute for Artificial Intelligence, Peking University, Beijing 100871, China · School of Computer Sciences, Beijing University of Posts and Telecommunications, Beijing 100876, China
GraphWalk: Enabling Reasoning in Large Language Models through Tool-Based Graph Navigation
Apr 2, 2026Taraneh Ghandi, Hamidreza Mahyar, Shachar KlaimanLLM Reasoning with Graphs LLM Tool Use
Faculty of Science, McMaster University · BASF Digital Solutions

Mar 2, 2026J/K move · Enter open · S save

GraphScout: Empowering Large Language Models with Intrinsic Exploration Ability for Agentic Graph Reasoning

Yuchen Ying, Weiqi Jiang, Tongya Zheng, Yu Wang+3

Zhejiang University, Hangzhou, China · Hangzhou City University, Hangzhou, China · Nanyang Technological University, Singapore, Singapore

LLM Reasoning with Graphs Agentic RAG Graph Retrieval-Augmented Generation LLM Post-Training Synthetic Data Generation for Language Models

Open paper AskPDF arXiv

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_}.

Abstract

LLM Reasoning with Graphs

Explore similar work

GraphScout: Empowering Large Language Models with Intrinsic Exploration Ability for Agentic Graph Reasoning

Position: How can Graphs Help Large Language Models?

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