OpCredit: Operation-Aware Policy Learning for Agentic Knowledge Graph Question Answering

Yucheng Li; Mingyuan Li; Xiaxia Wang; Gong Cheng

cs.CLOct 15, 2026

OpCredit: Operation-Aware Policy Learning for Agentic Knowledge Graph Question Answering

Authors: Yucheng Li, Mingyuan Li, Xiaxia Wang, Gong Cheng

Organizations: State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing, China · Department of Computer Science, University of Oxford

Abstract

Agentic knowledge graph question answering(KGQA) relies on sequences of executable operations, but trajectory-level rewards obscure their individual contributions. Successful trajectories may contain ineffective operations, while failed trajectories may contain useful ones. To assess individual operations, we propose OpCredit, an operationaware policy-learning framework that combines downstream outcome credit with immediate transition credit: Branch Outcome Credit (BOC) reuses ordinary rollouts to compare terminal task rewards observed after different operations under matched navigation contexts; Frontier Transition Credit (FTC) measures operation-induced changes in answer-conditioned frontier potential. The two complementary signals jointly supervise the corresponding decision spans during training, while inference uses only the learned policy and standard KG interface. Experiments on ComplexWebQuestions, WebQSP, and GrailQA across three backbones demonstrate consistent improvements in KGQA performance.

Figures & tables

Figure 1: Trajectory–operation granularity mismatch in KGQA. Progressive operations advance toward the gold answer. (a) Examples in successful and failed rollouts. (b) Operation proportions on CWQ with SFT-initialized Qwen2.5-7B.

Method	Outcome attribution	Process signal
Supervision for KGQA
KnowCoder-A1	Trajectory	–
KG-R1	Trajectory	Turn validity
GraphWalker	Trajectory	Trajectory SFT
EoG	Trajectory	Reference-path matching
GAPD	Trajectory	Gold-action distillation

Table 1: Comparison of outcome attribution and process signals across representative methods.

Figure 2: Overview of OpCredit. BOC compares terminal task rewards under matched navigation contexts; FTC measures answer-conditioned changes in frontier potential. Both signals supervise the same decision span during training. Inference uses the learned policy and standard KG interface.

Training-Free KGQA
Method	Backbone	CWQ		WebQSP		GrailQA
		Hit@1	F1	Hit@1	F1	Hit@1	F1
Direct prompting	Qwen2.5-3B	22.0	17.7	44.6	30.3	13.8	11.6
Direct prompting	Qwen2.5-7B	25.7	20.7	50.9	33.2	15.9	13.6
Direct prompting	Llama-3.1-8B	28.1	22.4	55.5	34.8	21.3	17.7
ToG ( Sun et al., 2024 )	GPT-4	68.5	–	82.6	–	81.4	–

Table 2: Overall Hit@1 and F1 on CWQ, WebQSP, and GrailQA. Bold highlights the best Hit@1 and F1 among methods using each OpCredit backbone. – denotes an unreported metric.

Configuration	BOC	FTC	CWQ		WebQSP		GrailQA
			Hit@1	F1	Hit@1	F1	Hit@1	F1
OpCredit SFT	–	–	72.15	66.06	86.28	76.38	83.73	76.77
OpCredit -BOC,-FTC	–	–	79.43	71.57	89.44	78.98	87.17	79.62
OpCredit -FTC	✓	–	80.65	72.15	90.27	79.09	88.03	81.49
OpCredit -BOC	–	✓	82.41	73.70	91.30	81.48	89.58	82.36
OpCredit	✓	✓	83.47	74.58	92.13	82.97	90.18	83.42

Table 3: Ablation of OpCredit with Qwen2.5-7B.

Figure 3: Credit alignment on a common SFT rollout pool. (a) Mean replay credit across four ordered usefulness levels (1 is least useful and 4 is most useful). (b) Usefulness-discrimination AUC; the dashed line marks random discrimination.

Figure 4: Error composition on matched diagnostic subsets. Labels show rounded percentages within each method’s error set.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Stage	Parameter	Setting
SFT	Effective batch size	256
SFT	Learning rate	$1\times 10^{-5}$
SFT	Epochs	8 (CWQ/WebQSP); 6 (GrailQA)
SFT	Maximum sequence length	5120
SFT	Precision and sharding	bf16; DeepSpeed ZeRO-2
RL	Optimizer learning rate	$1\times 10^{-6}$

Appendix

Table 4: Training and evaluation settings, including rollout sampling for the CWQ credit audit and behavioral diagnostic.

Dataset	Train	Eval.
WebQSP	3,071	1,639
CWQ	27,639	3,531
GrailQA	44,337	6,763

Appendix

Table 5: Source dataset split sizes. Eval. denotes the test split for CWQ/WebQSP and the full development split for GrailQA.

You are a KGQA agent that answers questions by navigating a knowledge graph. Explore the graph step by step: 1. Choose an entity and a direction to explore: <explore direction="outgoing">entity_name</explore> — follow outgoing edges from entity <explore direction="incoming">entity_name</explore> — follow incoming edges to entity Reason in <think > tags before each action. 2. After seeing the available relations, select the most relevant one by outputting its name exactly. 3. After seeing the resulting entities, either: - Answer: <answer>["name1", "name2"]</answer> — JSON list of entity names exactly as shown - Continue: <explore direction="outgoing/incoming">entity_name</explore> Important: - Check ALL entities before answering. Do not pick the first plausible one. - If multiple entities satisfy the question, list them all. - Do NOT fabricate facts. Only use information visible in names.

Appendix

Table 6: Fixed system prompt for the KGQA agent.

Question: {question} Current entity: {entity_name} Explore outgoing or incoming relations from this entity.

Appendix

Table 7: User-message templates for KG navigation and final answering.

Question	what 5 countries border Ethiopia?
Assistant	<think> I need to inspect outgoing relations for Ethiopia. </think>
	<explore direction="outgoing">Ethiopia</explore>
Observation	Outgoing relations: location.location.adjoin_s, ...
Assistant	<think> location.location.adjoin_s is relevant. </think>
	location.location.adjoin_s
Observation	<information> Ethiopia -> Eritrea, Djibouti, Somalia, Sudan, Kenya </information>

Appendix

Table 8: Serialized SFT examples from WebQSP and CWQ. The examples illustrate the operation and observation format.

Operation	Before frontier $F^{-}$	After frontier $F^{+}$
Entity-and-direction selection	{previous active entity}	{selected entity}
Relation selection	{active entity}	Returned entity set
Answer emission	{active entity}	Predicted answer entity set

Appendix

Table 9: Operation-local frontiers for FTC. Braces denote a singleton entity set.

Context	Decision- weighted	Group- weighted
Without decision phase	46–48%	30–31%
Full	0%	0%

Appendix

Table 10: Decision-phase mixing under different navigation context matching rules. Rates are consistent across the evaluated checkpoints.

Judge rating	Displayed level	AUC label
1	1	Unhelpful
2	2	Unhelpful
3	2	Excluded (neutral)
4	3	Useful
5	4	Useful

Appendix

Table 11: Annotation ratings, displayed usefulness levels, and AUC labels.

Message

Content

System

You are an expert evaluator for knowledge-graph navigation steps. Given a question and an agent’s navigation trajectory on a Freebase-style knowledge graph, rate one operation for how much it advances answering the question. You do not know the correct answer: judge purely from the semantics of the question, the operation description, and the entities involved. Use the following scale: 5 = clearly moves toward the answer; 4 = probably helpful; 3 = plausible exploration, neutral, or uncertain; 2 = probably unhelpful; 1 = clearly off-topic or counterproductive. Respond with only a JSON object of the form {"rating": <1--5>, "reason": "<one sentence>"} .

User

Question: {question}. Navigation path so far: {path-before-the-operation}. Operation to evaluate: {operation description}. Rate this single operation from 1 to 5.

Appendix

Table 12: Reference-blinded judge prompt.

Method	Level 1	Level 2	Level 3	Level 4	AUC
GRPO	$-0.134$	$-0.019$	$+0.005$	$+0.014$	0.606
GiGPO	$-0.556$	$-0.003$	$-0.056$	$+0.087$	0.592
RTMC	$-0.108$	$-0.031$	$-0.016$	$+0.003$	0.492
GraphGPO	$-0.471$	$+0.000$	$-0.020$	$+0.057$	0.595
OpCredit	$-0.347$	$+0.016$	$+0.050$	$+0.144$	0.718

Appendix

Table 13: Credit-assignment replay on the common SFT rollout pool. Mean credit is reported for the four ordered usefulness levels; AUC measures usefulness discrimination.

Figure 5: Behavioral diagnostic on CWQ for Qwen2.5-3B. The recovery rate is conditioned on trajectories containing a backward operation (

\Delta d_{\mathrm{diag}}>0

); the near-distance rate is conditioned on wrong final answers. Values are single-run percentages over the fixed diagnostic protocol. OpCredit rises to the highest late-training recovery rate, while the two methods have smaller, less consistent differences in near-distance errors.

Metric	SFT	100	200	300	400	500	600
Near-distance, OpCredit	7.9	8.4	8.8	8.8	9.8	12.2	10.7
Near-distance, BOC-only	7.9	8.0	9.3	8.9	10.3	9.6	9.8
Recovery, OpCredit	20.6	23.9	24.6	23.8	26.5	28.1	26.5
Recovery, BOC-only	20.6	25.4	24.8	23.1	22.9	21.0	18.3

Appendix

Table 14: Behavioral diagnostic on CWQ. Values are percentages; BOC-only denotes OpCredit without FTC.

CWQ
Method	Err.	Sel.	First	Late	Empty
GRPO	105	67	23	10	0
OpCredit	97	61	23	16	0
WebQSP
GRPO	55	27	22	35	16
OpCredit	49	20	24	33	22

Appendix

Table 15: Total error counts (Err.) and within-method category percentages on 492 diagnostic questions per dataset. Sel.: Answer selection; First: Path-first; Late: Path-late; Empty: Empty answer.

Knowledge Graph Question Answering

Knowledge Graph Question Answering answers natural-language questions by finding and reasoning over entities and relations in structured knowledge graphs.

See all 165 papers

Outcome-Anchored Credit Reallocation for Agentic Knowledge Graph Question Answering
Oct 18, 2026Mingyuan Li, Yucheng Li, Xiaxia Wang +1Knowledge Graph Question Answering RL for LLM Agents
State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing, China · Department of Computer Science, University of Oxford
GraphWalker: Agentic Knowledge Graph Question Answering via Synthetic Trajectory Curriculum
Mar 30, 2026Shuwen Xu, Yao Xu, Jiaxiang Liu +4Knowledge Graph Question Answering LLM Agent Training
School of Artificial Intelligence, University of Chinese Academy of Sciences · The Key Laboratory of Cognition and Decision Intelligence for Complex Systems, Institute of Automation, Chinese Academy of Sciences · Department of Electronic Engineering, Tsinghua University
Search-on-Graph-R1: Training Large Language Models to Search Knowledge Graphs with Reinforcement Learning
Jul 20, 2026Jia Ao Sun, Hao Yu, Fengran Mo +4LLM Reasoning with Graphs RL for Language Model Reasoning
Université de Montréal · Mila – Québec AI Institute · McGill University +2

Oct 18, 2026J/K move · Enter open · S save

Outcome-Anchored Credit Reallocation for Agentic Knowledge Graph Question Answering

Mingyuan Li, Yucheng Li, Xiaxia Wang, Gong Cheng

State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing, China · Department of Computer Science, University of Oxford

Knowledge Graph Question Answering RL for LLM Agents Token-Level Credit Assignment Reinforcement Learning Step-Level Credit Assignment in RL

Open paper AskPDF arXiv

Agentic knowledge graph question answering (KGQA) requires large language models (LLMs) to solve complex questions through multi-turn interactions with a knowledge graph (KG). Outcome-supervised reinforcement learning derives verifiable outcome rewards from final answers but uniformly assigns each rollout's outcome-level advantage to all policy-generated tokens, creating a trajectory-to-operation mismatch since KG operations within a rollout can have varying effects on the search process and final answer. To address this, we propose Outcome-Anchored Credit Reallocation (OACR), which employs a training-only KG-state outcome model to estimate outcome-reward changes between adjacent KG search states and converts them into operation credit, from which token-wise weights are derived. These multiplicative weights reallocate token-level update magnitudes while preserving the sign of the outcome-level advantage at every generated token. Across three benchmarks, OACR achieves stronger overall performance than existing KGQA methods while using fewer inference-time LLM calls and tokens.

Abstract

Knowledge Graph Question Answering

Explore similar work

Outcome-Anchored Credit Reallocation for Agentic Knowledge Graph Question Answering

GraphWalker: Agentic Knowledge Graph Question Answering via Synthetic Trajectory Curriculum

Search-on-Graph-R1: Training Large Language Models to Search Knowledge Graphs with Reinforcement Learning