CREDO: Evidence-Conditioned Credit Assignment for Temporal Reasoning Agents
Organizations: Nanjing University of Aeronautics and Astronautics · Tsinghua University · Security Capability Center, Qihoo 360
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.
Figures & tables
| 1 | for each do |
|---|---|
| 2 | Sample trajectories with ; compute original rewards and GRPO advantages . |
| 3 | Extract evidence and stage masks; determine token availability . |
| 4 | Compute , , , and using Eqs. ( 1 )–( 2 ). |
| 5 | Determine comparison validity ; set and . |
| 6 | for each stage do |
| 7 | Compute peer comparisons and local advantages (Eqs. ( 4 )–( 5 )). |
| Model | Overall | Question Type | Answer Type | ||
|---|---|---|---|---|---|
| Multiple | Single | Entity | Time | ||
| TKG Embedding-based methods | |||||
| EmbedKGQA | 0.206 | 0.134 | 0.235 | 0.290 | 0.001 |
| CronKGQA | 0.279 | 0.134 | 0.337 | 0.328 | 0.156 |
| MultiQA | 0.293 | 0.159 | 0.347 | 0.349 | 0.157 |
| Prompt-based LLMs | |||||
| Model | CronQuestion KG (In Domain) | ICEWS Actor (Out of Domain) | ||||||
|---|---|---|---|---|---|---|---|---|
| Overall | Simple | Medium | Complex | Overall | Simple | Medium | Complex | |
| RAG Baseline | 0.235 | 0.704 | 0.092 | 0.009 | 0.265 | 0.660 | 0.128 | 0.011 |
| LLaMA2-7B | 0.169 | 0.049 | 0.143 | 0.282 | 0.111 | 0.035 | 0.066 | 0.322 |
| GPT-4o | 0.206 | 0.069 | 0.130 | 0.376 | 0.113 | 0.051 | 0.035 | 0.353 |
| RTQA | 0.298 | 0.608 | 0.218 | 0.135 | – | – | – | – |
| Temp-R1 ∗ | 0.508 | 0.844 | 0.241 | 0.446 | 0.309 | 0.447 | 0.123 | 0.324 |
| Multiple (%) | ||
|---|---|---|
| 0.03 | 0.04 | 45.00 |
| 0.01 | 0.04 | 43.75 |
| 0.05 | 0.04 | 45.00 |
| 0.03 | 0.02 | 45.00 |
| 0.03 | 0.06 | 45.62 |
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
| Setting | Stage 1 | Stage 2 |
| Scheduled updates | 80 | 500 |
| Questions per update rollouts | ||
| PPO minibatch trajectories | 30 | 2 |
| Data / sequence parallelism | 1 / 8 | 2 / 4 |
| Learning rate | ||
| Gradient clipping | 5 | 1 |
| Category | GRPO | CWO | CREDO | |
|---|---|---|---|---|
| Equal | 174 | 156 (89.66) | 151 (86.78) | 152 (87.36) |
| Before/After | 94 | 81 (86.17) | 89 (94.68) | 87 (92.55) |
| First/Last | 72 | 65 (90.28) | 62 (86.11) | 68 (94.44) |
| Equal Multi | 33 | 22 (66.67) | 28 (84.85) | 28 (84.85) |
| Before Last | 69 | 34 (49.28) | 38 (55.07) | 41 (59.42) |
| After First | 58 | 27 (46.55) | 33 (56.90) | 36 (62.07) |
| Comparator / subset | Corrected | Regressed | Difference | 95% CI | |
|---|---|---|---|---|---|
| GRPO / Overall | 500 | 50 | 23 | ||
| CWO / Overall | 500 | 34 | 23 | ||
| GRPO / Multiple | 160 | 33 | 11 | ||
| CWO / Multiple | 160 | 19 | 13 |
| Evidence condition | GRPO | CWO | CREDO |
|---|---|---|---|
| Supporting facts only | 178 (88.56) | 195 (97.01) | 194 (96.52) |
| Generic, | 164 (81.59) | 184 (91.54) | 196 (97.51) |
| Generic, | 170 (84.58) | 184 (91.54) | 198 (98.51) |
| Generic, | 154 (76.62) | 181 (90.05) | 196 (97.51) |
| Temporal, | 157 (78.11) | 180 (89.55) | 196 (97.51) |
| Temporal, | 152 (75.62) | 178 (88.56) | 197 (98.01) |
| Evidence condition | GRPO | CWO | CREDO |
|---|---|---|---|
| Complete evidence | 60 (33.33) | 114 (63.33) | 125 (69.44) |
| Generic, | 58 (32.22) | 96 (53.33) | 119 (66.11) |
| Temporal, | 62 (34.44) | 97 (53.89) | 100 (55.56) |
RL for Language Model Reasoning
Reinforcement learning for language model reasoning uses reward-driven training to improve multi-step problem solving, tool use, and reliable answers.
See all 1,162 papers