PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yucheng Li, Mingyuan Li, Xiaxia Wang, Gong Cheng

arXiv:2610.21345v1cs.CL

TL;DR

Agentic KGQA assigns rewards to whole trajectories even though individual operations can be useful or ineffective. OpCredit combines matched-context outcome comparisons with immediate answer-conditioned frontier changes; experiments report improved performance across three benchmarks and three backbones.

  • Problem

    Trajectory-level rewards evaluate whole KGQA rollouts, obscuring whether individual operations were useful or ineffective.

    Source: §1 · pp. 1–2

  • Method

    OpCredit combines matched-context comparisons of terminal rewards with immediate answer-conditioned frontier changes to supervise operation decision spans.

    Source: §1 · p. 2, §3.2 · p. 4, §3.3 · p. 5

  • Results

    Across three benchmarks and three backbones, OpCredit improves KGQA performance; controlled ablations support both signals, and an audit finds closer credit alignment than GRPO.

    Source: §1 · p. 2, §5 · p. 8

  • Takeaways & Limitations

    The two credit signals jointly supervise one policy during training, while inference uses only the learned policy and standard KG interface.

    Source: §1 · p. 2, §5 · p. 8

    Evaluation covers three Freebase-based KGQA benchmarks with a fixed executable-operation interface; other graph schemas and tool environments remain unevaluated.

    Source: Limitations · p. 8

Abstract

from arXiv · show

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.

1 Introduction

Agentic KGQA must choose operations individually, although trajectory-level rewards can obscure which operations advance reasoning. OpCredit combines downstream outcome and immediate frontier-transition credit to supervise operation decisions, with reported gains across benchmarks and backbones.

1 Introduction

  • Agentic KGQA operations determine which graph evidence becomes available to later decisions.The paper situates its approach among prior methods for local credit and intermediate KGQA guidance.Source: §1 · pp. 1–2
  • Trajectory-level rewards can miscredit operations because successful rollouts may include diversions while failed rollouts may contain useful navigation.The resulting mismatch is between trajectory-level outcomes and individually selected operations.Source: §1 · pp. 1–2
  • OpCredit shows consistent KGQA gains; controlled comparisons favor combining BOC and FTC, and an operation-level audit finds closer credit alignment than GRPO.Experiments cover ComplexWebQuestions, WebQSP, and GrailQA with three LLM backbones.Source: §1 · p. 2
  • OpCredit addresses this mismatch with complementary downstream outcome and immediate transition credit for individual KG operations.The two signals jointly supervise corresponding decision spans during training; inference uses the learned policy and standard KG interface.Source: §1 · p. 2
  • BOC compares terminal rewards after different operations under matched navigation contexts, while FTC measures immediate changes in answer-conditioned frontier proximity.BOC reuses ordinary rollouts; FTC addresses how later decisions can obscure an operation’s immediate frontier effect.Source: §1 · p. 2

2 Related Work

Prior agentic KGQA work uses LLM-based exploration or learned interaction, with supervision ranging from outcomes and feedback to references and graph progress. Agentic RL methods also derive local credit from shared rollout structure; OpCredit combines rollout outcome evidence with KG-grounded transition credit.

2.1 LLM-Based KGQA

  • LLM-based KGQA includes training-free exploration methods such as ToG and PoG, alongside learning-based path-planning, evidence-use, and graph-interaction methods.The paper focuses on agents selecting executable operations during multi-turn KG interaction.Source: §2.1 · p. 2

2.2 Supervision for KGQA

  • KGQA supervision spans trajectory outcomes, turn-wise validity, reference paths, learned evaluators, and graph-progress signals, each with attribution or coverage constraints.Terminal rewards need further attribution; interaction validity alone does not establish an operation’s reasoning contribution, while other approaches depend on references or evaluator generalization.Source: §2.2 · pp. 2–3

2.3 Credit Assignment in Agentic RL

  • Agentic RL methods derive local credit from grouped states, rollout trees, or sampled experience graphs; OpCredit adds KG-grounded transition credit aligned with the same operation span.Its distinction is the alignment of rollout-based outcome credit and KG-grounded transition credit with an operation’s decision span.Source: §2.3 · p. 3

3 Method

OpCredit assigns operation-level supervision using downstream outcome comparisons and immediate answer-conditioned frontier changes. BOC and FTC supervise the same decision spans during training, while inference uses the learned policy and standard KG interface.

3.1 Preliminaries

  • A trajectory contains navigation operations and a terminal answer decision; training begins with supervised fine-tuning and same-question rollouts scored by final-answer outcomes.GRPO assigns a question-group trajectory advantage to all generated tokens.Source: §3.1 · p. 3

3.2 Branch Outcome Credit (BOC)

  • BOC compares terminal rewards for operations under matched contexts, grouping decisions by active entity, visited entities, remaining navigation budget, and decision phase.Each rollout contributes once per support set, and matching pools outcome evidence without additional environment interaction.Source: §3.2 · p. 4

3.3 Frontier Transition Credit (FTC)

  • FTC compares operation-local frontier potentials before and after execution, scoring a nonempty frontier by its best available answer-proximity opportunity.The coarse proximity labels distinguish gold answers, their constructed one-hop neighborhood, and other entities; they are not exact graph distances.Source: §3.3 · p. 5

3.4 Unified Operation-Aware Policy Learning

  • BOC outcome credit and eligible FTC transition credit supervise the same reasoning-and-operation decision span in a joint policy update.FTC reinforces decisions with positive credit and suppresses those with negative credit; inference requires only the learned policy and standard KG interface.Source: §3.4 · pp. 5–6

4 Experiments

Across three datasets and three backbones, OpCredit improves over SFT, and controlled ablations support complementary contributions from BOC and FTC. The experiments also examine context matching, operation-level credit alignment, and the composition of remaining errors.

4.1 Experimental Setup

  • Experiments use CWQ and WebQSP test splits and the full GrailQA development split, reporting F1 and Hit@1 across three SFT-initialized backbones.Baselines include training-free and training-based KGQA methods.Source: §4.1 · p. 6

4.4 Analysis of Navigation Context Matching

  • Matching BOC comparisons by decision phase creates type-consistent outcome baselines for relation choices and entity-and-direction choices.Without phase matching, 46–48% of decision occurrences across checkpoints belong to groups mixing both operation types.Source: §4.4 · p. 6

4.2 Main Results

  • OpCredit improves Hit@1 and F1 over SFT in all nine dataset–backbone settings, including GrailQA with Qwen2.5-3B.The comparison covers CWQ, WebQSP, and GrailQA.Source: §4.2 · p. 6, Table 2 · p. 7

4.3 Ablation Study

  • On Qwen2.5-7B, BOC and FTC each improve on GRPO, and their combination performs best across all three datasets.The ablation holds SFT initialization and training and evaluation protocols fixed; FTC alone yields larger gains than BOC alone in this setting.Source: §4.3 · p. 6, Table 3 · p. 7

4.5 Reference-Blinded Credit Audit

  • OpCredit reaches usefulness-discrimination AUC 0.718, versus GRPO 0.606 and RTMC 0.492, on the common SFT rollout pool.The reference-blinded audit uses an LLM judge that cannot see gold answers, terminal rewards, or assigned credit.Source: §4.5 · p. 7, Figure 3 · p. 8

4.6 Error Analysis

  • OpCredit has fewer answer-selection errors than GRPO on all three datasets, while navigation remains a prominent source of its remaining errors.Answer-selection errors dominate CWQ, first-hop deviations dominate GrailQA, and WebQSP has a more mixed profile; CWQ diagnostics also find higher late-training recovery after backward operations than BOC-only.Source: Figure 4 · p. 8, §4.6 · p. 8

5 Conclusion

OpCredit combines downstream outcome and immediate frontier-transition credit to supervise operation decisions during training. Results across three benchmarks and three backbones show improved KGQA performance, with ablations supporting complementary signal contributions.

5 Conclusion

  • BOC compares terminal task rewards under matched navigation contexts, while FTC measures immediate answer-conditioned frontier changes.Both signals supervise the same decision span during training.Source: §5 · p. 8
  • Inference uses the learned policy with the standard KG interface, without training-time signals or an auxiliary evaluator.Source: §5 · p. 8
  • Results across three benchmarks and three backbones show improved KGQA performance, with controlled ablations supporting complementary contributions from both signals.The credit audit also finds closer alignment with assessed operation usefulness on a shared rollout pool.Source: §5 · p. 8

Limitations

The evaluation is bounded to three Freebase-based benchmarks and a fixed executable-operation interface; it also omits multilingual KGQA and graph updates. The appendix reports the hardware and software used.

Limitations

  • Evaluation covers three Freebase-based benchmarks under a fixed executable-operation interface; alternative agent interfaces remain uncompared.Performance on other graph schemas and tool environments remains to be evaluated.Source: Limitations · p. 8
  • The experiments omit multilingual and cross-lingual KGQA, including questions whose language differs from KG entity or relation labels.The authors identify these settings as directions for further evaluation.Source: Limitations · p. 9
  • Evaluation uses a fixed KG snapshot and does not assess policy responses to subsequent graph additions or updates.Evaluation on evolving KGs would complement these benchmark results.Source: Limitations · p. 9

A.1 Hardware and software

  • Experiments used one node with eight NVIDIA RTX 5880 Ada GPUs and approximately 2,500 GPU hours across SFT, RL training, ablations, and evaluation.The KG came from the final Freebase RDF dump dated 2015-08-09 and was accessed through a local SPARQL endpoint.Source: §A.1 · p. 11

A.2 Task, data, and metrics

The appendix specifies benchmark splits and metrics, data preparation, the agent interaction and rollout records, and the credit and optimization procedures used in training.

A.2 Task, data, and metrics

  • CWQ and WebQSP are evaluated on test splits, GrailQA on its full official development split, and formal evaluation uses one sampled trajectory per question.Hit@1 checks whether the predicted answer set contains a gold answer; F1 compares normalized predicted and gold answer sets.Source: §A.2 · p. 11

A.3 Training configurations

  • The three SFT-initialized backbones are Qwen2.5-3B, Qwen2.5-7B, and Llama-3.1-8B; the ablation holds initialization, rollout protocol, and optimization fixed while varying BOC and FTC.The configuration with neither signal is GRPO; final RL checkpoints are used unless training diverges, when the most recent stable checkpoint is selected.Source: §A.3 · p. 11

A.4 Hyperparameters

  • Training samples six rollouts per question; the Qwen2.5-3B batch uses 64 questions, while the two larger backbones use 16 each.These correspond to 384 and 96 trajectories, respectively; Table 4 also summarizes formal evaluation and diagnostic sampling.Source: §A.4 · p. 11, Table 4 · p. 12

B Dataset Statistics

  • The CWQ/WebQSP SFT–RL pool contains 27,237 deduplicated questions after excluding empty answers or topic entities and source-question overlap with evaluation examples.GrailQA is trained separately; CWQ records missing gold answers or topic entities are omitted from scoring.Source: B Dataset Statistics · p. 11

C.1 Agent interaction protocol

  • The interaction protocol alternates reasoning with executable entity-and-direction or relation-selection operations, returned graph observations, and either continued navigation or answer emission.Relation selection can expand unnamed intermediate nodes by one edge in either direction, counted as one navigation hop.Source: §C.1 · pp. 11–12

C.2 Recorded rollout information

  • SFT traces are built from benchmark gold reasoning paths using templates and serialize reasoning, operations, KG observations, and final answers.All three backbones share the same SFT data; rollout records align terminal rewards, navigation context, operations, decision spans, and before/after frontiers.Source: §C.1 · p. 12, §C.2 · p. 12

D.1 Branch Outcome Credit

  • In the illustrated matched-context example, the operation with terminal reward 1 receives positive BOC, while the two operations with reward 0 receive negative BOC.The three same-question rollouts share the active entity and context at that decision.Source: §D.1 · p. 14

D.2 Frontier Transition Credit

  • FTC compares operation-local frontiers before and after execution using answer proximity; unavailable frontiers or unmapped gold answers suppress the affected FTC.Gold-answer neighborhoods are constructed through bounded incoming and outgoing KG-neighbor lookup; the objective averages generated-token losses within trajectories, then weights trajectories equally.Source: §D.2 · p. 14, §D.3 · p. 15

D.4 Analysis of Navigation Context Matching

The appendix tests how navigation-context matching affects BOC, then describes the shared rollout pool and reference-blinded usefulness assessment used for the operation-level audit.

D.4 Analysis of Navigation Context Matching

  • The context-matching analysis uses diagnostic rollouts from two CWQ model configurations, holding terminal rewards fixed and making no parameter updates.It compares full-context matching with three alternatives after restricting comparisons to the same question and active entity.Source: §D.4 · p. 15
  • Without matching decision phase, nearly half of sampled decisions share an outcome baseline with a different operation type; matching phase aligns comparisons to the same type of decision.The visited entity set and remaining navigation budget remain among the matching constraints.Source: §D.4 · p. 15

E.1 Audit setup

  • The audit compares five credit-assignment methods on the same rollout pool, terminal rewards, and assessed operations.The pool is generated by the Qwen2.5-3B SFT policy on 500 CWQ questions with eight rollouts per question; 1,200 occurrences are selected for usefulness assessment.Source: §E.1 · p. 15

E.2 Reference-blinded usefulness assessment

  • A temperature-zero reference-blinded judge rates operation usefulness from the question, preceding history, operation, and returned observations, without access to gold answers, rewards, assigned credits, or later steps.The assessment uses a five-point rubric, with ratings 2 and 3 combined for mean-credit visualization.Source: §E.2 · pp. 15–16

E.3 Credit metrics and results

The audit finds stronger usefulness discrimination for OpCredit than for the compared methods, and the behavioral diagnostics define answer-distance labels and measures of near-distance errors and recovery.

E.3 Credit metrics and results

  • The audit’s AUC ranks individual-operation credits against usefulness labels, treating ratings 4–5 as positive and 1–2 as negative while excluding rating 3.Mean credit describes supervision direction within a method; AUC compares discrimination without assuming a common credit scale.Source: §E.3 · p. 16
  • OpCredit achieves the highest usefulness-discrimination AUC among the compared methods on the shared rollout pool.OpCredit, GRPO, and RTMC all show increasing mean credit across usefulness levels.Source: §E.3 · p. 16

F.1 Diagnostic setup and metrics

  • The behavioral diagnostic labels answer proximity as 0 for a gold answer, 1 for its constructed one-hop neighborhood, 2 for a restricted second-level neighborhood, and 3 for more distant candidates.It evaluates OpCredit with and without FTC across SFT and six training checkpoints on 500 CWQ questions.Source: §F.1 · p. 16
  • A wrong-answer near-distance rate asks whether an incorrect predicted answer lies in the answer neighborhood, while recovery is conditional on trajectories containing a backward operation.The illustrative trajectory moves away from and then returns to the answer region before producing the correct answer.Source: §F.1 · p. 16

F.2 Seven-checkpoint results

On the CWQ diagnostic, OpCredit recovers more often than BOC-only after trajectories contain a backward operation. Their wrong-answer near-distance rates differ less consistently.

F.2 Seven-checkpoint results

  • Wrong-answer near-distance rates show smaller differences with no consistent direction across checkpoints.Near-distance rate is conditioned on wrong final answers.Source: §F.2 · p. 16, Figure 5 · p. 17
  • The diagnostic reports single-run percentages over a fixed protocol, with recovery and near-distance rates conditioned on different trajectory subsets.Recovery is conditioned on trajectories containing a backward operation; near-distance rate is conditioned on wrong final answers.Source: Figure 5 · p. 17
  • 26.5% versus 18.3% recovery at step 600 for OpCredit and BOC-only, respectively, on trajectories containing a backward operation.The comparison concerns recovery following backward operations; values are single-run percentages under the fixed diagnostic protocol.Source: §F.2 · p. 16, Table 14 · p. 17, Figure 5 · p. 17

G Error Analysis Details

The error analysis evaluates matched diagnostic questions, assigns unsuccessful answers to four categories using candidate availability and reference-path alignment, and reports counts and within-method shares.

G.1 Diagnostic protocol

  • 492 matched diagnostic questions per dataset are assessed at the question level, with Figure 4 showing category shares within each method’s error set.The comparison uses each agent’s executable KG interface.Source: §G.1 · p. 17

G.2 Error categories

  • The four labels are answer selection, first-hop path deviation, later or unaligned path deviation, and empty answer.Answer selection includes an incorrect answer when a gold-answer name occurs in the final frontier or the complete path aligns with a reference path; path deviations are defined relative to available reference paths.Source: §G.2 · pp. 17–18

G.3 Complete diagnostic statistics

  • Table 15 reports error counts and rounded within-method category shares, which may not sum to 100%; Figure 4 normalizes bar widths.The table covers 492 diagnostic questions per dataset.Source: Table 15 · p. 18, §G.3 · p. 18

Related papers

Loading 2610.21345v1…