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

CoEvoKG: Co-Evolving Knowledge Graphs with Self-Evolving Search Agents
Aug 3, 2026Zhaoyang Li, Zenghuang Fu, Qiuyuan Ai +6Knowledge Graph Question Answering Knowledge Graphs
Peking University · Institute of Automation, Chinese Academy of Sciences · Mininglamp Technology
Explore-on-Graph: Incentivizing Autonomous Exploration of Large Language Models on Knowledge Graphs with Path-refined Reward Modeling
Feb 25, 2026Shiqi Yan, Yubo Chen, Ruiqi Zhou +8LLM Reasoning with Graphs Knowledge Graph Question Answering
Zhongguancun Laboratory, Beijing, China · Department of Electronic Engineering, Tsinghua University, Beijing, China · Ant International, Ant Group, Hangzhou, Zhejiang, China +1
GraphEvoResearcher: Graph-Aware Training-Free Self-Reflective Reasoning for Cost-Bounded Multi-Hop Question Answering
Oct 19, 2026Suxing LiuMulti-Hop QA LLM Self-Refinement
Department of Computing, Universiti Sains Malaysia

Aug 3, 2026J/K move · Enter open · S save

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

Zhaoyang Li, Zenghuang Fu, Qiuyuan Ai, Ping Jiang+5

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

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

Open paper AskPDF arXiv

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.

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