Evolve on Graph: Self-Evolving Knowledge Graph Reasoning without Question Annotations

Zongyuan Sun; Shuai Zhao; Ke Shu; Ziyue Zhu; Shangyang Wu; Yuanlin Lin; Tao Wang; Shiyue Li

cs.AIOct 26, 2026

Evolve on Graph: Self-Evolving Knowledge Graph Reasoning without Question Annotations

Authors: Zongyuan Sun, Shuai Zhao, Ke Shu, Ziyue Zhu, Shangyang Wu, Yuanlin Lin, Tao Wang, Shiyue Li,

Organizations: Beijing University of Posts and Telecommunications, Beijing, China · University of Helsinki, Helsinki, Finland · University of Amsterdam, Amsterdam, Netherlands · Nanyang Technological University, Singapore

Abstract

Knowledge graphs (KGs) provide reliable external knowledge for multi-hop factual reasoning with large language models (LLMs), yet most KGs in real-world domains such as finance and industry lack question--answer (QA) annotations. Without such annotations, existing methods struggle to improve LLM graph reasoning: training-free agents cannot improve their exploration through interaction; reinforcement learning (RL) agents depend on QA data annotated by humans or synthesized by closed-source models; and training data is typically built offline, so its topology mix is fixed and cannot follow the agent's ability. We propose Evolve on Graph (EoG), a framework that lets an LLM self-evolve its graph reasoning without any QA annotations. Through Graph Self-Play, a single LLM alternates between a Proposer that poses questions and a Solver that answers them. To make questions verifiable, Symbolically Verifiable Topology Synthesis (SVTS) samples reasoning topologies on the KG and executes the corresponding first-order logic queries, yielding topology skeletons with correct and complete answer sets; guided by a skeleton, the Proposer explores the graph to pose a multi-hop question. To let task topologies follow the Solver, a Boundary-Aware Graph Curriculum rewards the Proposer by the Solver's score variance, keeping questions at the Solver's capability boundary so that complex topologies enter training as the Solver improves. On six benchmarks over Freebase, Wikidata, and an industrial KG, EoG consistently outperforms prompting-, retrieval-, and agent-based methods, showing that LLM graph reasoning can improve through self-play without QA annotations. Our code is available at https://github.com/Szy5/EoG

Figures & tables

Figure 1. With only a KG and no question annotations, EoG lets an LLM self-evolve by proposing questions verified on the graph and then learning to solve them.

Figure 2. Comparison of KG reasoning paradigms. Prompt-based agents explore with a frozen LLM and RL-based agents learn from fixed QA written by humans or closed-source models, whereas EoG proposes and solves KG-verified tasks of adaptive difficulty. With Qwen-2.5-7B-Instruct, EoG outperforms all shown baselines on three Freebase benchmarks.

Method	Exploration (§ 3.2 )	Training Tasks and Answers (§ 3.3 )	Task Difficulty (§ 3.4 )
	$a_{t}\sim\pi_{\theta_{0}}(\cdot\mid s_{t})$	$\theta=\theta_{0}$
ReAct ( Yao et al., 2022 )	Frozen LLM calls the graph tools.	No training.	No training tasks.
	$\mathcal{B}_{t+1}=\mathrm{top}\text{-}k\;\pi_{\theta_{0}}(\cdot\mid q,\mathcal{B}_{t})$	$\theta=\theta_{0}$
ToG / PoG ( Sun et al., 2024 ; Chen et al., 2024 )	Prompted beam search or sub-goal planning.	No training.	No training tasks.
	$o=\mathrm{top}\text{-}k\;s\bigl(q,\mathcal{T}_{L}(\mathcal{E}_{Q})\bigr)$	$\theta=\theta_{0}$
Graph Reranker	Reranks triples near the anchors once.	No training.	No training tasks.

Table 1. Comparison with representative methods. Training-free methods keep

\theta_{0}

, RL agents learn from fixed tasks written by humans or closed-source models, and EoG learns from KG-verified tasks that adapt to the Solver.

Figure 3. Overview of EoG. One LLM self-plays as the Proposer and the Solver, synthesizes verifiable tasks with SVTS, and forms a boundary-aware curriculum by rewarding the Proposer for questions on the Solver’s capability boundary.

Full-Supervised Methods
Method	LLM	WebQSP W		CWQ C		GrailQA G		GTSQA T		WikiWebQuestions		Avg.
Method	LLM	Hit@1	F1	Hit@1	F1	Hit@1	F1	Hit@1	F1	Hit@1	F1	Hit@1	F1
KG-R1 † W	Qwen-2.5-7B	78.42	69.02	50.92	46.88	61.64	59.29	–	–	–	–	63.66	58.40
KG-R1 † C	Qwen-2.5-7B	80.71	68.57	58.03	53.93	67.81	65.52	–	–	–	–	68.85	62.67
KG-R1 † G	Qwen-2.5-7B	71.06	61.64	46.02	42.43	69.13	64.88	–	–	–	–	62.07	56.32
KG-R1 † T	Qwen-2.5-7B	–	–	–	–	–	–	48.03	49.23	75.39	66.28	61.71	57.76

Table 2. Main results on five public KGQA benchmarks (Hit@1 and F1, %; IndustryCarBench in Figure 5 ). Full-supervised methods are for reference, with icons marking training sets; bold marks the best annotation-free result; “–” means not evaluated.

Panel of Figure 5 — Figure 5. Training dynamics of role ablations. Proposer-only and Solver-only denote w/o Solver update and w/o Proposer update. (a) Validation Hit@1 on CWQ. (b) Question-extraction rate of the Proposer. (c–d) Proposer and Solver rewards.

Panel of Figure 7 — Figure 7. Evolution of task difficulty. Synthesis success rate of the Proposer over training steps (a) across three backbones, (b) on simple and complex topologies, and (c) per topology; complex topologies keep improving after simple ones plateau.

Variant	WebQSP		CWQ		GrailQA
Variant	Hit@1	F1	Hit@1	F1	Hit@1	F1
ReAct (untrained)	34.82	28.42	16.06	13.45	49.19	50.07
w/o Solver update	53.74	47.08	46.39	42.15	58.50	55.69
w/o Proposer update	63.14	56.91	36.22	35.83	55.67	55.18
w/o query exec. (Random Walk)	64.87	57.67	35.93	35.64	60.12	60.41
Adversarial reward	69.51	60.40	42.59	41.85	63.26	61.01

Table 3. Ablation study of EoG with Qwen-2.5-7B-Instruct on Freebase. Bold marks the best result in each column.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Pattern	Structure	Logical query
$1p$		$\phi(x)=r_{1}(v_{a},x)$
$2p$		$\phi(x)=\exists y:\ r_{1}(v_{a},y)\wedge r_{2}(y,x)$
$3p$		$\phi(x)=\exists y_{1},y_{2}:\ r_{1}(v_{a},y_{1})\wedge r_{2}(y_{1},y_{2})\wedge r_{3}(y_{2},x)$
$2i$		$\phi(x)=r_{1}(v_{a_{1}},x)\wedge r_{2}(v_{a_{2}},x)$
$ip$		$\phi(x)=\exists y:\ r_{1}(v_{a_{1}},y)\wedge r_{2}(v_{a_{2}},y)\wedge r_{3}(y,x)$
$pi$		$\phi(x)=\exists y:\ r_{1}(v_{a_{1}},y)\wedge r_{2}(y,x)\wedge r_{3}(v_{a_{2}},x)$

Appendix

Table 6. Basic logic query patterns.

v_{a}

: anchor entity;

x

: answer variable;

y_{i}

: intermediate variables;

r_{i}

: relations.

Panel of Figure 8 — Figure 8. Semantic contamination analysis. Max cosine similarity of synthesized questions to each test set.

Parameter	Value
Training data	SVTS tasks
Training steps	140
Train / PPO mini-batch size	256 / 128
Actor learning rate	$1\times 10^{-6}$
KL loss coefficient	0.01
Rollout samples ( $n$ )	5

Appendix

Table 7. Settings of EoG. Hyperparameters of self-play training with Qwen-2.5-7B-Instruct on Freebase.

LLM Reasoning with Graphs

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

See all 211 papers

Aug 3, 2026

CoEvoKG: Co-Evolving Knowledge Graphs with Self-Evolving Search Agents

Large language models can improve with reinforcement learning for search agents, yet existing self play agents repeatedly generate tasks while discarding the knowledge gained during successful searches. We introduce CoEvoKG, a framework that turns a knowledge graph into both a source of verifiable training tasks and a persistent evidence memory for agent evolution. CoEvoKG jointly trains a task generator and a search agent: the generator creates multihop questions from entity chains sampled from the knowledge graph, while the agent learns from rewards for answer correctness and search trajectories whose entity paths are supported by graph evidence. When a search succeeds, CoEvoKG verifies and deduplicates the retrieved evidence, then writes it back to the corresponding graph nodes and edges. Future rounds reuse this enriched graph for task generation and reward computation, closing the loop between model self evolution and knowledge accumulation. Experiments on six QA benchmarks (NQ, TriviaQA, PopQA, HotpotQA, 2WikiMultiHopQA, and Bamboogle) with three backbone models show that CoEvoKG improves macro average accuracy over the corresponding base models by +11.2, +10.1, and +11.6 points on Qwen2.5-3B-Instruct, Qwen2.5-7B-Instruct, and Llama-3.1-8B-Instruct, respectively. Under matched training budgets, CoEvoKG further improves over competitive self play baselines and RL baselines for search agents by +2.6 to +3.7 macro average points across the three backbones. Code is available at https://github.com/lazzy1225/CoEvoKG.

Zhaoyang Li, Zenghuang Fu, Qiuyuan Ai +6

Peking University · Institute of Automation, Chinese Academy of Sciences · Mininglamp Technology

Knowledge Graph Question Answering Knowledge Graphs RL for LLM Agents Self-Evolving Agents

Ask PDF

Feb 25, 2026

Explore-on-Graph: Incentivizing Autonomous Exploration of Large Language Models on Knowledge Graphs with Path-refined Reward Modeling

The reasoning process of Large Language Models (LLMs) is often plagued by hallucinations and missing facts in question-answering tasks. A promising solution is to ground LLMs' answers in verifiable knowledge sources, such as Knowledge Graphs (KGs). Prevailing KG-enhanced methods typically constrained LLM reasoning either by enforcing rules during generation or by imitating paths from a fixed set of demonstrations. However, they naturally confined the reasoning patterns of LLMs within the scope of prior experience or fine-tuning data, limiting their generalizability to out-of-distribution graph reasoning problems. To tackle this problem, in this paper, we propose Explore-on-Graph (EoG), a novel framework that encourages LLMs to autonomously explore a more diverse reasoning space on KGs. To incentivize exploration and discovery of novel reasoning paths, we propose to introduce reinforcement learning during training, whose reward is the correctness of the reasoning paths' final answers. To enhance the efficiency and meaningfulness of the exploration, we propose to incorporate path information as additional reward signals to refine the exploration process and reduce futile efforts. Extensive experiments on five KGQA benchmark datasets demonstrate that, to the best of our knowledge, our method achieves state-of-the-art performance, outperforming not only open-source but also even closed-source LLMs.

Shiqi Yan, Yubo Chen, Ruiqi Zhou +8

Zhongguancun Laboratory, Beijing, China · Department of Electronic Engineering, Tsinghua University, Beijing, China · Ant International, Ant Group, Hangzhou, Zhejiang, China +1

LLM Reasoning with Graphs Knowledge Graph Question Answering RL for Language Model Reasoning Reward Shaping

Ask PDF

Oct 19, 2026

GraphEvoResearcher: Graph-Aware Training-Free Self-Reflective Reasoning for Cost-Bounded Multi-Hop Question Answering

Multi-hop question answering (QA) requires models to chain intermediate conclusions while remaining cost-aware. Existing training-free self-reflective protocols (generate -> critique -> revise) improve accuracy but operate on a flat token stream: revisions cannot identify which prior step is unreliable, and early stopping cannot exploit structural convergence. We introduce GraphEvoResearcher, a training-free protocol that lifts EvoResearcher's self-reflective meta-reward onto an explicit reasoning graph - nodes are intermediate conclusions/evidence and edges encode support, contradict, and depends_on. A graph-aware meta-reward combines correctness, efficiency, reflection, diversity, and four structural signals (connectivity, acyclicity, branch coverage, path convergence) to decide whether to revise, backtrack, or stop. A graph-convergence early-stop terminates when evidence branches converge on a single conclusion. On a real LLM (DeepSeek), over GSM8K, MATH, and BBH (n=50 each), GraphEvoResearcher reaches 98%, 92%, and 82% respectively, the highest of all baselines, with the largest gains on the hardest set (MATH: +24 pp over single-shot, +12 pp over flat reflection), while keeping construction cost bounded at ~2 steps / 4.5-5 nodes. Our results indicate the structural signal of a reasoning graph is most valuable exactly where single-step reasoning is unreliable.

Suxing Liu

Department of Computing, Universiti Sains Malaysia

Multi-Hop QA LLM Self-Refinement Efficient Language Model Reasoning Adaptive Reasoning in Language Models LLM Reasoning with Graphs

Ask PDF

Abstract

LLM Reasoning with Graphs

Explore similar work

CoEvoKG: Co-Evolving Knowledge Graphs with Self-Evolving Search Agents

Explore-on-Graph: Incentivizing Autonomous Exploration of Large Language Models on Knowledge Graphs with Path-refined Reward Modeling

GraphEvoResearcher: Graph-Aware Training-Free Self-Reflective Reasoning for Cost-Bounded Multi-Hop Question Answering