LongTraceRL: Learning Long-Context Reasoning from Search Agent Trajectories with Rubric Rewards

> Paper: LongTraceRL: Learning Long-Context Reasoning from Search Agent Trajectories with Rubric Rewards > Authors: Nianyi Lin, Jiajie Zhang, Lei Hou, Juanzi Li (Tsinghua University) > arXiv: 2605.31584 > Area: NLP / Long-Context Reasoning / Reinforcement Learning > Code: GitHub - THU-KEG/LongTraceRL

The Long-Context Reasoning Problem

Long-context reasoning requires an LLM to do three things simultaneously:

1. Locate relevant fragments in an ocean of text 2. Integrate evidence scattered across distant positions into a logical chain 3. Discriminate real clues from distractors

The post uses a detective analogy: reading 200 mostly irrelevant documents while trying to remember a timeline from document #37.

Weaknesses of Existing RLVR Approaches

Reinforcement Learning with Verifiable Rewards (RLVR) suffers from two flaws:

1. Weak distractors — random unrelated documents are trivially separable from relevant ones. Real-world distractors are documents that are *task-relevant but not part of the answer* (e.g., papers you read but did not cite). 2. Sparse rewards — reward is given only on the final answer (+1/-1), with no supervision on the reasoning process, like grading a chess game by win/loss alone.

Innovation 1: Tiered Distractors from Search Agent Trajectories

The team first builds multi-hop questions from a knowledge graph (e.g., "Who was the Swiss federal president when Einstein won his Nobel Prize?" → Einstein → 1921 Nobel Prize → 1921 → Swiss president → Edmund Schulthess). A search agent then attempts each question, producing three document tiers:

| Type | Description | Distractor strength | |------|-------------|---------------------| | Gold Docs | Documents the agent cited | Non-distractor | | Tier-1 Distractors | Documents the agent read but did not cite | High confusion | | Tier-2 Distractors | Documents seen in search results but never opened | Low confusion |

Tier-1 distractors are the hardest: highly relevant, deliberately read, yet excluded from the answer. Compared to random sampling, this tiered construction makes tasks far harder — model performance gaps of 20-30% are reported.

Innovation 2: Rubric Rewards

Instead of outcome-only rewards, LongTraceRL scores each key entity in the reference reasoning chain (e.g., +1/3 for each of entities A, B, C) plus a bonus for the correct final answer — like grading an essay on structure, evidence, and language rather than a single total score.

A key design choice is the positive-only strategy: reward only high-quality correct answers, never penalize wrong ones. This avoids reward hacking, where the model learns shortcuts that produce superficially correct but incomplete reasoning.

Experimental Results

Evaluated on five long-context benchmarks with models from 4B to 30B:

| Benchmark | Improvement | |-----------|-------------| | HotpotQA | +8.3% | | 2WikiMultihopQA | +12.1% | | MuSiQue | +15.7% | | IIRC | +6.9% | | StrategyQA | +5.4% |

Additional findings:

• Reasoning becomes more evidence-grounded: more supporting documents cited, more complete reasoning chains, stronger resistance to Tier-1 distractors.
• Relative gains are larger on smaller models (4B) than on 30B, suggesting that high-quality data and reward design can partially compensate for scale.
• Ablations show the model still outperforms when tested with novel, harder distractors unseen during training — evidence that it learns a generalizable retrieval-and-integration strategy rather than keyword matching.

Why "Traces" Matter

The paper encodes the educational principle of "show your work" into AI training: a correct answer may come from guessing, so the reasoning process itself must be rewarded. It also represents an evolution of RAG:

| Stage | Approach | Limitation | |-------|----------|------------| | RAG 1.0 | Single retrieval + generation | One retrieval is not enough | | RAG 2.0 | Iterative retrieval + multi-step reasoning | Doesn't know *what* to retrieve | | LongTraceRL | Learning from search trajectories + process rewards | Learns how to search and how to use evidence |

Open Question

Does rewarding "mentions of entities A, B, C" reward formal completeness or genuine understanding? The out-of-distribution distractor experiments suggest generalizable strategies, but the authors acknowledge this remains an open philosophical question.

References

• Lin, N., et al. (2026). *LongTraceRL: Learning Long-Context Reasoning from Search Agent Trajectories with Rubric Rewards*. arXiv:2605.31584.
• Yang, K., et al. (2024). *Rejection Sampling for Language Model Alignment*. ICLR.
• Guu, K., et al. (2020). *REALM: Retrieval-Augmented Language Model Pre-Training*. ICML.
• Yao, S., et al. (2023). *ReAct: Synergizing Reasoning and Acting in Language Models*. ICLR.

*Collected 2026-06-02 from zhichai.net.*