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

Nianyi Lin; Jiajie Zhang; Lei Hou; Juanzi Li

Source-linked AI summary

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

Nianyi Lin, Jiajie Zhang, Lei Hou, Juanzi Li

arXiv:2605.31584v1May 29, 2026cs.CLcs.AIcs.LG

TL;DR

Long-context reasoning is difficult because models must find and integrate relevant evidence amid distracting information, while existing RL methods offer weak distractors and sparse intermediate supervision. LONGTRACERL uses knowledge-graph-generated multi-hop questions, search-trajectory tiered distractors, and an entity-level rubric reward applied only to correct answers. Across five benchmarks and three reasoning-model families, it consistently improves over existing methods and promotes comprehensive, evidence-grounded reasoning.

Problem
Long-context models struggle with relevant evidence integration amid distractors, while existing RL methods use low-confusability data and outcome-only rewards without intermediate supervision.
Method
LONGTRACERL generates multi-hop questions from knowledge-graph random walks, builds tiered distractors from search-agent trajectories, and applies entity-level rubric rewards only to correct responses.
Results
LONGTRACERL consistently outperforms existing long-context RL methods across five benchmarks and three reasoning-model families and scales.
Takeaways & Limitations
The framework encourages comprehensive, evidence-grounded reasoning while reducing reward hacking from shortcut answers.
Takeaways & Limitations
Training data relies on the KILT Wikipedia snapshot and search-agent trajectories, which may limit reasoning diversity and make distractor quality agent-dependent.

Abstract

from arXiv · show

Long-context reasoning remains a central challenge for large language models, which often fail to locate and integrate key information in extensive distracting content. Reinforcement learning with verifiable rewards (RLVR) has shown promise for this task, yet existing methods are limited by low-confusability distractors and sparse, outcome-only reward signals that cannot supervise intermediate reasoning steps. To address these issues, we introduce \textsc{LongTraceRL}. For data construction, we generate multi-hop questions via knowledge graph random walks and leverage search agent trajectories to build \emph{tiered distractors}: documents the agent read but did not cite (high confusability) and documents that appeared in search results but were never opened (low confusability), producing training contexts that are far more challenging than those built by random sampling or one-shot search. For reward design, we propose a \emph{rubric reward} that uses the gold entities along each reasoning chain as fine-grained, entity-level process supervision. This rubric reward is applied only to responses with correct final answers (positive-only strategy), distinguishing the reasoning quality among correct responses and preventing reward hacking. Experiments on three reasoning LLMs (4B--30B) across five long-context benchmarks demonstrate that \textsc{LongTraceRL} consistently outperforms strong baselines and encourages comprehensive, evidence-grounded reasoning. Codes, datasets and models are available at \href{https://github.com/THU-KEG/LongTraceRL}{https://github.com/THU-KEG/LongTraceRL}.

1 Introduction

LONGTRACERL addresses long-context reasoning failures by pairing trajectory-based, high-confusability distractors with entity-level process supervision. Across three reasoning LLMs and five benchmarks, it consistently outperforms baselines while encouraging evidence-grounded reasoning.

Long-context LLMs struggle to extract and integrate relevant information amid distracting content, often hallucinating, retrieving fragments, or citing irrelevant passages.
Existing long-context RL methods use shallow questions, randomly sampled distractors, and outcome-only rewards that provide little supervision for intermediate reasoning.
LONGTRACERL generates complex multi-hop questions from knowledge-graph random walks and constructs realistic distractors from search-agent trajectories.
Its tiered distractors include read-but-uncited documents with high confusability and unopened search-result documents with lower confusability.
The entity-level rubric reward provides finer-grained intermediate supervision, while positive-only application to correct answers helps prevent reward hacking.
Experiments across five benchmarks show consistent gains; Qwen3-4B improves 5.7 points over the base model and surpasses the strongest baseline by 2.5 points.

2 Related Work

Prior long-context work constructs synthetic questions and contexts using shallow multi-hop datasets, scratch generation, or structured knowledge, while RL methods often provide limited intermediate supervision.

Long-context synthetic-data methods vary in question construction, including reuse of MuSiQue and HotpotQA, scratch generation, and structured knowledge for deeper chains.
Long-context RL remains limited because outcome-based rewards supervise final answers without directly signaling intermediate reasoning over large inputs.
Related process-supervision approaches use chunk-level context rewards or dense evidence-extraction supervision rather than entity-level rubric rewards.

3 Method

LONGTRACERL builds long-context training data from multi-hop knowledge-graph paths and search-agent trajectories, then combines answer correctness with entity-level rubric supervision in GRPO.

3 Method: The framework combines a trajectory-derived data-construction pipeline with reinforcement learning using outcome-based and process-based rewards.
3.1.1 Multi-Hop Question Generation: Knowledge-graph random walks over Wikipedia produce eight-hop entity paths, with an LLM selecting relevant unvisited hyperlink candidates.
3.1.1 Multi-Hop Question Generation: Question synthesis requires reasoning through every path entity, paraphrases identifying information to prevent keyword shortcuts, and outputs the answer plus gold intermediate entities.
3.1.2 Agent Search Trajectory Collection: The search agent records SEARCH, OPEN, and CITE actions across complete trajectories while attempting each generated question.
3.1.2 Agent Search Trajectory Collection: Correct trajectories are retained after sampling five attempts per question, and opened-but-uncited documents become Tier-1 distractors while unopened results become Tier-2 distractors.
3.1.2 Agent Search Trajectory Collection: The traj-tiered assembler prioritizes Tier-1 distractors before filling the target context with Tier-2 documents, then shuffles all documents.
3.2 RL with Rubric Reward: GRPO combines binary answer correctness with a rubric reward measuring recall of gold entities referenced in the response.
3.2 RL with Rubric Reward: Group-level normalization divides positive rubric scores by the group maximum, rescales them to [0, 1], and improves comparability across questions.

4 Experiments

Experiments evaluate LONGTRACERL across reasoning models, benchmarks, reward settings, and distractor strategies. Results show consistent gains, with rubric rewards and trajectory-tiered distractors contributing substantially to performance and reasoning quality.

Main Results: LONGTRACERL achieves the best average score on every backbone, reaching 59.0 on Qwen3-4B, +5.7 over the base model and +2.5 over LongRLVR.The gains remain positive on DeepSeek-R1-0528-Qwen3-8B and Qwen3-30B-A3B-Thinking-2507.
Main Results: On Qwen3-4B, ablating the rubric reward reduces the average score from 59.0 to 53.7 despite using the same training dataset.This identifies the rubric reward as the dominant driver of the improvement in the reported ablation.
Training Dynamics: Rubric rewards increase during training, coincide with longer rollouts, and require positive-only supervision plus a finite response budget to avoid reward hacking.When rollouts hit the 32K response limit, the positive-only strategy guides responses back toward shorter lengths before they increase again.
Reward Weight: With α = 0.3, LONGTRACERL obtains the best average score of 59.0 across the reported rubric-reward weight sweep.The weight controls the relative emphasis on grounding reasoning in gold entities; α values of 0.1 and 0.5 perform worse overall or on some benchmarks.
Distractor Strategies: Trajectory-tiered distractors achieve the best average score, 59.0, and reach 41.8 on AA-LCR versus at most 35.5 for alternative strategies.The comparison keeps questions and gold passages identical while varying only distractor documents.
Distractor Strategies: Harder distractors yield stronger downstream performance: macro entity overlap rises from 1.35% for random sampling to 15.00% for search, 42.16% for traj-random, and 50.03% for traj-tiered.Higher overlap with rubric entities indicates greater distractor difficulty.
Reward Strategies: Applying rubric rewards to incorrect as well as correct responses lowers the average score from 59.0 to 57.1 and biases training toward enumerating gold-like entities.The largest reported drops are 4.8 points on AA-LCR and 5.3 points on MRCR.

5 Conclusion

LONGTRACERL advances long-context reinforcement learning through trajectory-based distractors and entity-level rubric rewards, with consistent improvements across five benchmarks and three model families.

LONGTRACERL combines trajectory-based distractors with an entity-level rubric reward for fine-grained process supervision.
Experiments across five long-context benchmarks and three model families and scales show consistent improvements over existing long-context reinforcement learning methods.
The authors characterize LONGTRACERL as a practical and generalizable recipe for further long-context reinforcement learning research.

6 Limitations

The data construction pipeline is limited by its reliance on the KILT Wikipedia snapshot and by dependence on the deployed search agent's capabilities.

The data construction pipeline relies entirely on the KILT Wikipedia snapshot, grounding all generated questions in encyclopedic knowledge.
The single-source knowledge graph may limit the diversity of reasoning patterns represented in training data.
Search-agent capability affects trajectory distributions and may alter the quality and difficulty of resulting distractors.

7 Ethical Considerations

The paper reports that its models and datasets are publicly available under permissible licenses and that the work involves no human subjects, private data, or dual-use concerns.

All models and datasets used in the work are publicly available under permissible licenses.
The method does not involve human subjects, private data, or content that raises dual-use concerns.

A Dataset Comparison

Table 6 compares the training datasets used by evaluated long-context reinforcement learning methods, including their question sources and reasoning-hop structures.

DocQA contains 200 MuSiQue examples with four hops, 200 MultiHopRAG examples with two to four hops, and 1,191 math or logic questions without defined hop counts.
LoongRL reuses HotpotQA, MuSiQue, and 2WikiMQA, while its KeyChain mechanism adds UUID-tracing steps.
The comparison highlights differences in dataset sources and explicit reasoning-hop structure across long-context reinforcement learning methods.

B Case Studies

The case studies show LONGTRACERL-4B handling conflicting cues, ambiguous references, and inclusive qualifiers more reliably than the no-rubric-reward variant. Its rollouts follow gold reasoning paths and correctly identify answers across these traps.

Rollout Case: LONGTRACERL-4B visits all seven gold entities in order before answering “Genil,” without adding irrelevant entities to inflate rubric scores.The rollout spans Arab-Berbers, Banu Hilal, Zenata, Marinid dynasty, Emirate of Granada, Granada War, and Muhammad XII.
Conflicting Cues: 37.6%: Rubric-reward training resolves the conflict between the “medium-sized” label and 450 employees, unlike the shortcut that selects 18.0%.The trained model reclassifies firms by actual headcount before applying the appropriate rate.
Pronoun Reference: LONGTRACERL-4B separates the issuer from the customer in an ambiguous two-clause question and returns “Nasdaq.”It identifies the unique customer with an explicit exchange annotation rather than merging both clauses into one entity.
Subtle Qualifier: LONGTRACERL-4B recognizes that the ACEC forecast covers 2022 and returns it alongside Deloitte’s outlook with their organizations.The inclusive criterion accepts forecast periods covering 2022 even when the year is not in the document title.

C Prompts

The prompts support LONGTRACERL’s data-generation and reward-judgement pipeline, while the illustrated cases pair questions with successful and failed model outcomes. They include multi-hop synthesis, outcome correctness checks, and long-context reasoning traps.

Case Outcomes: The paired examples contrast failed shortcuts with rubric-reward successes that apply the correct rate, preserve clause distinctions, and return both qualifying documents.The successful outcomes are 211, Nasdaq, and the Deloitte and ACEC outlooks, respectively.
Question Generation: The training rollout prompt generates a multi-hop question whose answer is a specific attribute of the final entity in a knowledge-graph path.The question-generation constraints require step-by-step reasoning through all entities without shortcuts.
Outcome Reward Judgement: The outcome-reward prompt judges whether a response is correct against a precise question and correct answer.This prompt supplies the question, response, and unambiguous reference answer for the judgement.