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

Current large language models frequently stumble when tasked with long-context reasoning. While they can ingest massive amounts of text, they often fail to locate key information. This happens when information is buried within extensive, distracting content. Most existing training methods pad short questions with random, irrelevant documents. This creates a "toy" environment that lacks real-world complexity.

The gap lies in the quality of the distractors and the sparsity of the feedback. Current reinforcement learning (RL) approaches often rely on outcome-only rewards. These simply tell the model "right" or "wrong" at the end of a 100k-token reasoning chain. This is a blunt instrument. As shown in, a model can arrive at the correct answer through a flawed reasoning path.

It essentially "guesses" correctly due to coincidental retrieval. This lack of fine-grained supervision makes it hard to teach the model to navigate complex, multi-step evidentiary chains.

The Problem

The status quo for long-context RL suffers from two primary failure modes. First, it uses low-confusability distractors. Most practitioners use datasets where distractors are sampled randomly from unrelated corpora. These are "easy" negatives. They lack semantic relevance to the query. This makes them trivial for a model to filter out. Even advanced retrieval-based augmentation often fails to provide nuanced, topically related noise.

Second, existing Reinforcement Learning with Verifiable Rewards (RLVR) typically optimizes for the final answer. When the input context spans hundreds of thousands of tokens, this outcome-based reward becomes noisy. A model might successfully answer a question by hallucinating a connection. It might satisfy the binary reward while failing the underlying reasoning task. This leads to "reward hacking," where the model learns to optimize for a shortcut rather than the evidence-grounded path.

How It Works

The authors propose LONG-TRACERL. This framework attacks both data quality and reward granularity. The methodology is split into a specialized data pipeline and a composite reward structure.

1. Trajectory-Tiered Data Construction: Instead of random sampling, the authors use a search agent to generate realistic trajectories. They perform random walks over a Wikipedia knowledge graph to create multi-hop questions. Then, they observe an agent attempting to solve these questions. They categorize the documents into two tiers. Tier-1 distractors are documents the agent actually read but chose not to cite. Tier-2 distractors are documents that appeared in search results but were never opened .

This creates a hierarchy of "hard" versus "easy" distractors. It forces the model to distinguish between highly relevant but unnecessary information and superficial noise.

1. Entity-Level Rubric Rewards: To move beyond sparse outcome rewards, the authors implement a "rubric reward." Their pipeline tracks the gold entities (the specific correct facts) required at each reasoning hop. They use these to provide fine-grained process supervision. The rubric reward measures the recall of these gold entities within the model's response.

2. Positive-Only Strategy: To prevent the model from simply enumerating every entity in the context, the authors use a "positive-only" strategy. They apply the rubric reward exclusively to responses that have already achieved the correct final answer. This ensures the rubric acts as a tie-breaker. It distinguishes high-quality reasoning from lucky guesses. It prevents the model from gaining high scores by just listing entities without solving the problem.

Numbers

The experimental results suggest that this combination is effective. The authors tested three model scales (4B to 30B) across five benchmarks. On the Qwen3-4B backbone, the method achieves an average gain of 5.7 points over the base model. It also surpasses the strongest baseline, LongRLVR, by 2.5 points [Table 1].

The impact is most visible on difficult reasoning tasks. On the AA-LCR benchmark, the Qwen3-4B model improved from a base score of 33.2 to 41.8 [Table 1]. This represents a significant jump in accuracy for expert-crafted, 100k-token context questions. Ablation studies confirm that the rubric reward is the primary driver. Removing it (the LONGTRACERL-GRPO variant) causes the average score to drop from 59.0 to 53.7. Furthermore, the rubric reward encourages longer, more deliberate reasoning chains [Figure 3c].

What's Missing

There are gaps that a production engineer should consider. First, the training data is grounded solely in the KILT Wikipedia snapshot. While the authors claim transferability, they do not explicitly demonstrate performance on non-encyclopedic data. The reasoning patterns learned from Wikipedia may not perfectly translate to complex legal contracts or codebases.

Second, the quality of the training data depends on the search agent used during construction. If the agent is mediocre, the "Tier-1" distractors may not be sufficiently challenging. The paper acknowledges that the distractor distribution is a function of the agent's behavior.

Finally, the computational cost of this pipeline is not fully quantified. Generating multi-hop questions and collecting agent trajectories requires significant overhead. The RL training was performed on 32 $\times$ H800 GPUs. However, the total time required to build this tiered dataset is not reported.

Should You Prototype This

Yes, if you are building reasoning-heavy agents for long-context environments. The "positive-only" rubric reward is a practical pattern for anyone struggling with reward hacking. By gating process supervision behind outcome correctness, you get fine-grained feedback without risking model misalignment.

If you can simulate agent trajectories or access high-quality search logs, the tiered distractor strategy is a significant upgrade. Code and models are available at https://github.com/THU-KEG/LongTraceRL. Start with a small-scale prototype using a 4B model to validate the approach.

Figures from the paper