Skip to content

Long Document Reconstruction Unlocks Scalable Long-Context RLVR

Conference: EMNLP 2026
Paper: ACL Anthology
Area: Reinforcement Learning
Keywords: Reinforcement Learning, Long-Context Understanding, Document Reconstruction, Verifiable Rewards, GRPO

TL;DR

This paper introduces an unsupervised Reinforcement Learning with Verifiable Rewards (RLVR) framework that masks paragraphs in raw long documents and trains LLMs via GRPO to reconstruct their original order, deriving objective, automated verifiable rewards and complexity curricula directly from intrinsic text structures without any human QA annotation or teacher model distillation.

Background & Motivation

Reinforcement Learning with Verifiable Rewards (RLVR) has achieved remarkable breakthroughs in enhancing the complex reasoning capabilities of large language models (LLMs), particularly across mathematical derivation and program synthesis. By anchoring policy optimization on verifiable ground-truth outcomes, models like DeepSeek-R1 can autonomously discover structured, multi-step problem-solving trajectories. However, as LLMs increasingly transition into autonomous agents tasked with processing expansive codebases, technical reports, and extensive multi-document corpora, the cognitive bottleneck rapidly shifts from localized deduction to holistic global context comprehension. Across tens of thousands of tokens, models frequently succumb to the well-documented "lost in the middle" pitfall, losing track of narrative consistency and failing to retrieve distributed facts.

Existing efforts to enhance long-context capabilities via RLVR or supervised fine-tuning (SFT) suffer from a crippling scalability bottleneck. State-of-the-art pipelines rely almost exclusively on high-quality long-context question-answering pairs, which demand expensive human expert annotations or complex rubric prompting from proprietary frontier teacher models (e.g., GPT-4 or Claude). This dependency is prohibitively costly when scaling to the hundreds of thousands of rollouts required by reinforcement learning algorithms, and risks transferring the intrinsic biases and performance ceilings of the teacher supervisor to the student model.

The core tension lies in the stark contrast between the ubiquitous demand for scalable long-context training and the extreme scarcity of objective, scalable reward signals in long-form generation. This paper overcomes the bottleneck by recognizing that raw, unannotated long documents inherently possess rich structural organizationโ€”their natural discourse progression, chronological narrative, and causal transitions provide deterministic internal signals. Core idea: formulate long-context understanding as a sequential paragraph reconstruction task where missing segments must be identified and ordered from a shuffled candidate set, deriving fully automated verifiable rewards directly from original documents to guide policy optimization under GRPO.

Method

Overall Architecture

The proposed framework converts arbitrary unannotated long documents into self-verifiable reinforcement learning environments without requiring external teacher guidance. The overall workflow comprises three primary phases: long-form task curation, structured verifiable reward calculation, and group-relative policy optimization.

During task curation, raw long texts sourced from books, arXiv papers, and code repositories are corrupted by masking \(K\) non-overlapping paragraphs with numbered placeholder tokens, while the masked text chunks are shuffled to construct an option candidate pool. During execution, the policy model ingests the corrupted long document along with the candidate options, performs chain-of-thought structural reasoning, and outputs a formatted sequence of option identifiers. Finally, an automated rule-based verifier checks permutation validity and exact position alignment to distribute dense partial-credit rewards, driving group-relative policy updates via GRPO implemented on the Verl framework.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Raw Unannotated Long Documents<br/>Books ยท arXiv Papers ยท Code Corpora"] --> B["Document Corruption & Task Formulation<br/>Mask K paragraphs with placeholders & shuffle options"]
    B --> C["Curriculum Learning via Complexity Scaling<br/>Progressively scale K from 2 to 8 across search space"]
    C --> D["LLM Structural Reasoning & Rollout Generation<br/>Predict ordered permutation sequence o"]
    D --> E["Validity-Constrained Dense Reward Computation<br/>Evaluate permutation validity V(o) & compute matches"]
    E --> F["Group Relative Policy Optimization (GRPO)<br/>Surrogate policy update via group-normalized advantages"]
    F -->|Iterative Policy Updates| D

Key Designs

1. Document Corruption and Sequential Reconstruction Formulation: Transforming Long Contexts into Objective Combinatorial Decisions

To eliminate reliance on artificially curated question-answering pairs, the method converts long-context representation learning into a discrete combinatorial reconstruction problem. Given an uncorrupted document \(D = \{p_1, p_2, \dots, p_n\}\) composed of \(n\) paragraphs, the system randomly selects a subset of \(K\) non-overlapping paragraphs to mask. The original document is transformed into a corrupted context where the selected segments are replaced by explicit positional tags <CHUNK_i>MISSING</CHUNK_i> for \(i \in \{1, \dots, K\}\). The true paragraphs are shuffled, assigned letter labels (e.g., A, B, C, D), and presented at the end of the input prompt.

This formulation effectively eliminates the ambiguity and evaluation challenges inherent in open-ended generative tasks. To succeed, the model must read and synthesize long narrative arcs across tens of thousands of tokens, discerning thematic transitions, cross-referencing code variable definitions, and following logical arguments to position each segment correctly. Restricting the target output to a compact list of options (e.g., {B, A, D, C}) dramatically reduces generation token overhead during training rollouts while directly penalizing structural misunderstanding through an exact ground-truth sequence.

2. Permutation-Validity Constraints and Piecewise Dense Rewards: Balancing Strict Format Compliance with Progressive Credit Assignment

A naive binary sparse reward that awards points only for an entirely correct sequence causes catastrophic reward sparsity in combinatorial search spaces (\(K!\) possible permutations), stalling early policy exploration. To counter this, the authors introduce a piecewise dense reward function \(R(o, g)\) with an explicit permutation-validity condition \(\mathcal{V}(o)\):

\[R(o, g) = \begin{cases} 1, & \text{if } o = g \\ \frac{1}{K}\sum_{i=1}^K \mathbb{I}[o_i = g_i], & \text{if } \mathcal{V}(o) \land o \neq g \\ 0, & \text{otherwise} \end{cases}\]

Here, \(o = (o_1, \dots, o_K)\) and \(g = (g_1, \dots, g_K)\) denote the predicted and ground-truth option sequences, and \(\mathbb{I}[\cdot]\) is the indicator function. The validity condition \(\mathcal{V}(o)\) requires the set of predicted options in the response to be strictly identical to the set of ground-truth candidate optionsโ€”no options may be omitted, hallucinated, or duplicated. If the model outputs degenerate sequences (such as repeating a single option to game partial scores) or violates formatting constraints, the reward immediately drops to 0.

By incorporating fractional credit proportional to the number of correctly ordered placeholders for structurally valid outputs, this reward design provides informative feedback gradients even when the overall sequence is not yet fully solved. This partial credit guides the model through intermediate steps, steering the policy steadily toward global narrative coherence.

3. Curriculum Learning via Complexity Scaling: Calibrating Exploration across Factorial Permutation Spaces

The reconstruction task possesses an intrinsic difficulty throttle governed by the number of masked segments \(K\), as the candidate permutation space expands factorially as \(K!\). For \(K=2\), the model chooses between only 2 permutations, focusing on local pairwise coherence; for \(K=8\), the search space broadens to \(8! = 40,320\) candidates, requiring sophisticated global contextual modeling across long spans.

Rather than sampling difficulty randomly, the training pipeline arranges samples into a progressive curriculum, scaling \(K\) from 2 through 8. The standard training distribution adopts an option mixture ratio of 3:3:3:5 for \(K \in \{2, 4, 6, 8\}\), initially familiarizing the policy with basic paragraph alignment before challenging it with complex multi-segment reordering. Empirical ablations confirm that this progressive curriculum prevents optimization instability and yields consistent downstream performance advantages over randomly shuffled difficulty schedules.

Loss & Training

  • Policy Optimization: Optimized using Group Relative Policy Optimization (GRPO), eliminating the memory footprint of a learned critic network. For each corrupted document query \(q\), a group of \(G=8\) rollout responses \(\{\tau^{(i)}\}_{i=1}^G\) is sampled from the behavioral policy \(\pi_{\theta_{\text{old}}}\), with group-normalized scalar advantages computed as: $\(A(\tau^{(i)}) = \frac{R_{\tau^{(i)}} - \text{mean}(\{R_{\tau^{(j)}}\}_{j=1}^G)}{\text{std}(\{R_{\tau^{(j)}}\}_{j=1}^G)}\)$ The policy is updated via the clipped surrogate objective: $\(\mathcal{L}_{\text{GRPO}}(\theta) = \mathbb{E}_{\tau}\left[\min\left(r_\theta A, \text{clip}(r_\theta, 1-\epsilon, 1+\epsilon)A\right)\right], \quad r_\theta = \frac{\pi_\theta(\tau \mid q)}{\pi_{\theta_{\text{old}}}(\tau \mid q)}\)$
  • Dataset and Hyperparameters: The training corpus comprises 14,000 long documents (8,000 books, 3,000 arXiv papers, and 3,000 code repositories) with an average length of 49,000 tokens; 500 samples are held out for validation tracking. Optimization uses AdamW with a constant learning rate of \(1\times 10^{-6}\) and a 5-step linear warmup. The prompt batch size is 128 with 8 sampled rollouts per prompt, a maximum context length of 64K, and a maximum response length of 4096 tokens, implemented on the open-source Verl RL framework.

Key Experimental Results

Main Results

Evaluation was conducted on two demanding long-context benchmarks: the synthetic reasoning benchmark RULER across Variable Tracking (VT), Common Words Extraction (CWE), Frequent Words Extraction (FWE), and Question Answering (QA) at 32K, 64K, and 128K context lengths; and the realistic multi-choice benchmark LongBench v2 at 32K, 64K, and 128K context lengths. Backbones evaluated are Qwen2.5-7B-Instruct-1M and LLaMA-3.1-8B-Instruct.

The table below summarizes performance across context lengths (RULER reports the 4-task average; LongBench v2 reports the overall score):

Model Backbone Benchmark Sequence Length Base Ours Gain
Qwen2.5-7B-Instruct-1M RULER 32K 73.83 78.38 +4.55
Qwen2.5-7B-Instruct-1M RULER 64K 68.43 72.57 +4.14
Qwen2.5-7B-Instruct-1M RULER 128K 64.35 65.65 +1.30
Qwen2.5-7B-Instruct-1M LongBench v2 Overall Score 33.20 33.80 +0.60
LLaMA-3.1-8B-Instruct RULER 32K 74.16 78.78 +4.62
LLaMA-3.1-8B-Instruct RULER 64K 61.17 71.43 +10.26
LLaMA-3.1-8B-Instruct RULER 128K 40.94 51.22 +10.28
LLaMA-3.1-8B-Instruct LongBench v2 Overall Score 30.10 30.40 +0.30

In direct comparison against supervised fine-tuning with 46K teacher-generated QA pairs (LongRLVR), the unsupervised reconstruction paradigm achieves superior or comparable performance while using zero human/teacher QA annotations:

Model Backbone Training Paradigm QA Pairs RULER-QA Avg LongBench v2 Overall
Qwen2.5-7B-Instruct-1M (SFT) Teacher-curated QA 46K 64.50 33.20
Qwen2.5-7B-Instruct-1M (Ours) Unsupervised Reconstruction 0K (14K docs) 68.30 33.80
LLaMA-3.1-8B-Instruct (SFT) Teacher-curated QA 46K 64.70 31.20
LLaMA-3.1-8B-Instruct (Ours) Unsupervised Reconstruction 0K (14K docs) 61.20 30.40

Ablation Study

The table below illustrates the impact of curriculum scheduling and individual option lengths (\(K\)) on average RULER performance across both backbones:

Investigation Experimental Setting Qwen2.5-7B Score LLaMA-3.1-8B Score Empirical Observation
Unfine-tuned Baseline Base model without RLVR 68.86 58.76 Baseline instruction-tuned performance
Training Schedule Shuffled Samples (Shuffle=True) 69.82 65.00 Mixed difficulty induces variance and lower gains
Training Schedule Curriculum Schedule (Shuffle=False) 72.20 67.12 Progressive difficulty yields highest scores
Option Length \(K\) Ablation Fixed \(K=2\) (5,000 samples) 64.79 63.96 Limited complexity fails to activate deep context
Option Length \(K\) Ablation Fixed \(K=4\) (5,000 samples) 65.83 64.27 Balanced complexity aids weaker backbones
Option Length \(K\) Ablation Fixed \(K=6\) (5,000 samples) 64.69 64.19 Stable mid-range performance
Option Length \(K\) Ablation Fixed \(K=8\) (5,000 samples) 64.83 63.53 Large combinatorial space elevates training difficulty

Key Findings

  • Substantial Long-Context Stability Gains on Weaker Baselines: The most pronounced gains appear at extreme lengths on LLaMA-3.1-8B, where RULER performance surges by over 10 points at 64K (61.17 โ†’ 71.43) and 128K (40.94 โ†’ 51.22), mitigating the severe attention collapse observed in the base model.
  • Criticality of Dense Reward Formulation: While sparse reward matching maintains performance on LLaMA-3.1-8B, it causes acute degradation on Qwen2.5-7B due to extreme gradient sparsity during initial training steps. Validation dynamics confirm that dense partial credit unlocks earlier and steadier optimization.
  • Document Length and Data Scaling Trends: Training on the longest available documents significantly outperforms random or short-document sampling. Furthermore, scaling training data from 0 to 14K and up to 30K samples produces consistent performance gains without reaching an observable saturation plateau, improving average RULER scores on Qwen2.5-7B by nearly 10 points.

Highlights & Insights

  • Deriving Supervision Directly from Intrinsic Text Structure: The framework circumvents the need for external LLM judges and costly human annotation pipelines by converting narrative sequence coherence into self-evident, verifiable reinforcement rewards.
  • Factorial Search Spaces Matched with Curriculum Schedules: Modulating the masked segment count \(K\) scales the combinatorial permutation space factorially (\(K!\)), providing a clean, mathematically grounded mechanism to calibrate sample difficulty for curriculum learning.
  • Cross-Task Representation Transfer: Despite training strictly on paragraph reordering, the emergent long-range contextual representations generalize directly to synthetic multi-hop reasoning, variable tracking, and realistic multi-choice document question answering.

Limitations & Future Work

  • Dependence on Well-Structured Documents: The approach requires access to lengthy, coherent documents (such as books or scientific papers); applying it to noisy, fragmented, or unorganized web crawls risks ambiguous ground-truth orderings.
  • Disparate Backbone Sensitivity to Single-Pattern Training: Fixing \(K\) to a single value benefited the weaker LLaMA model but degraded performance on Qwen2.5-7B, indicating that stronger models require heterogeneous task mixtures to prevent pattern overfitting.
  • Exploration at Frontier Scales: Experiments were conducted on 7Bโ€“8B models up to 30,000 documents; evaluating how unsupervised reconstruction RLVR scales to 70B+ architectures and millions of training steps remains an open frontier.
  • vs LongRLVR / LongReward: Prior long-context RLVR works rely on teacher models to synthesize question-answer pairs or evaluate rubrics, bounding student performance by supervisor quality. This work derives verifiable ground truth directly from uncorrupted document text, offering complete automation.
  • vs Continual Pretraining on Long Documents: As shown in the paper's appendix, standard continual pretraining with causal language modeling on long documents impairs instruction-following capabilities. In contrast, reconstruction RLVR frames long-context modeling as a goal-directed combinatorial decision problem, preserving conversational alignment while honing long-range retrieval.

Rating

  • Novelty: โ˜…โ˜…โ˜…โ˜…โ˜… Formulating unsupervised document reconstruction as a verifiable-reward RL task is an elegant, highly original paradigm shift.
  • Experimental Thoroughness: โ˜…โ˜…โ˜…โ˜…โ˜… Comprehensive evaluation across RULER, LongBench v2, multiple sequence lengths, reward formulations, and curriculum strategies.
  • Writing Quality: โ˜…โ˜…โ˜…โ˜…โ˜… Lucid motivation, crisp mathematical formulation, and well-structured empirical analyses.
  • Value: โ˜…โ˜…โ˜…โ˜…โ˜… Provides a scalable, low-cost training blueprint for advancing long-context foundation models without proprietary data dependencies.