Outcome-based method improves multi-step question answering over knowledge graphs
Outcome-Anchored Credit Reallocation for Agentic Knowledge Graph Question Answering
Artificial IntelligenceComputation and LanguageMachine Learning
Summary
Answering complex questions with help from knowledge graphs involves many small steps. The usual way of training models to answer these questions treats all steps equally, even though some steps contribute more than others. The authors developed a new method called Outcome-Anchored Credit Reallocation (OACR), which better assigns credit to important steps by looking at how each step changes the answer's outcome. This approach helps models perform better while using fewer resources.
What this means in practice
- •For chatbot developers: Improve multi-turn conversational agents to answer complex questions by more accurately crediting key reasoning steps.
- •For search engine engineers: Enhance knowledge graph query systems to provide better answers using fewer computational resources through better credit allocation.
Authors
Mingyuan Li, Yucheng Li, Xiaxia Wang, Gong Cheng
Abstract
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.