CREDO: Evidence-Conditioned Credit Assignment for Temporal Reasoning Agents

Yue Leng, Shengtao Wen, Xiang Chen, Xinyi Zeng, Yu Tian, Sheng-Jun HuangarXiv 2026 · arXiv

Abstract

Temporal Knowledge Graph Question Answering (TKGQA) requires language model agents to retrieve evidence, select relevant facts, and perform multi-step temporal reasoning. However, the trajectory-level outcome signal in GRPO does not explicitly distinguish the quality of intermediate decisions: downstream failures can penalize useful evidence acquisition, while identical rewards in all-failed groups eliminate the relative outcome signal despite differences in intermediate progress. We propose Credit Redistribution with Evidence-Driven Opportunities (CREDO), which uses intermediate evidence to recover local supervision, including in all-failed groups, and determine where outcome supervision acts. CREDO assigns positive stage-level credit through comparisons among rollouts of the same question and uses retained answer overlap as an opportunity proxy to shift part of the outcome-policy weight toward reasoning and answering. The framework preserves terminal rewards and trajectory-level advantages, while redistribution conserves total outcome-policy weight per trajectory. Following the public evaluation protocol of prior work, CREDO raises Overall accuracy from 78.0% to 82.4% and Multiple accuracy from 55.0% to 65.6% on MultiTQ relative to the strongest published baseline in our comparison. On TimelineKGQA, it raises cross-KG accuracy from 30.9% to 36.4% relative to our reproduced baseline via direct transfer to ICEWS Actor under matched training and evaluation settings.
BibTeX
@misc{leng2026credo,
  author = {Yue Leng and Shengtao Wen and Xiang Chen and Xinyi Zeng and Yu Tian and Sheng-Jun Huang},
  title = {{CREDO: Evidence-Conditioned Credit Assignment for Temporal Reasoning Agents}},
  year = {2026},
  eprint = {2611.01643},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.01643},
}

Loading related content...

Figure