PaperlayerView exact revision on arXiv

Source-linked AI summary

e3: Learning to Explore Enables Extrapolation of Test-Time Compute for LLMs

Amrith Setlur, Matthew Y. R. Yang, Charlie Snell, Jeremy Greer, Ian Wu, Virginia Smith, Max Simchowitz, Aviral Kumar

arXiv:2506.09026v2cs.LGcs.CL

TL;DR

Existing reasoning models often fail to improve when test-time compute exceeds their training budget, limiting the promise of test-time scaling. The paper introduces e3, which trains in-context exploration through asymmetric skill chaining, negative RL gradients, and a coupled curriculum. Applied to Qwen3-1.7B, e3 reaches strong AIME’25 and HMMT’25 performance, extrapolates to twice its training budget, and improves pass@k.

  • Problem

    The paper studies whether post-trained reasoning models can improve when test-time compute exceeds their maximum training budget.

  • Method

    Recipe e3 trains in-context exploration by combining asymmetric skill chaining, negative RL gradients, and a coupled curriculum over task difficulty and token budget.

  • Results

    Qwen3-1.7B trained with e3 achieves the best known sub-2B performance on AIME’25 and HMMT’25, extrapolates to 32k tokens from a 16k training budget, and improves pass@32.

  • Takeaways & Limitations

    In-context exploration is a core capability for enabling extrapolation of test-time compute.

  • Takeaways & Limitations

    The study is limited in model scale and domain, and future work must test e3 on larger models and other reasoning domains.

Abstract

from arXiv · show

Test-time scaling offers a promising path to improve LLM reasoning by utilizing more compute at inference time; however, the true promise of this paradigm lies in extrapolation (i.e., improvement in performance on hard problems as LLMs keep "thinking" for longer, beyond the maximum token budget they were trained on). Surprisingly, we find that most existing reasoning models do not extrapolate well. We show that one way to enable extrapolation is by training the LLM to perform in-context exploration: training the LLM to effectively spend its test time budget by chaining operations (such as generation, verification, refinement, etc.), or testing multiple hypotheses before it commits to an answer. To enable in-context exploration, we identify three key ingredients as part of our recipe e3: (1) chaining skills that the base LLM has asymmetric competence in, e.g., chaining verification (easy) with generation (hard), as a way to implement in-context search; (2) leveraging "negative" gradients from incorrect traces to amplify exploration during RL, resulting in longer search traces that chains additional asymmetries; and (3) coupling task difficulty with training token budget during training via a specifically-designed curriculum to structure in-context exploration. Our recipe e3 produces the best known 1.7B model according to AIME'25 and HMMT'25 scores, and extrapolates to 2x the training token budget. Our e3-1.7B model not only attains high pass@1 scores, but also improves pass@k over the base model.

1. Introduction

The paper asks whether test-time scaling can extrapolate beyond training budgets and argues that in-context exploration is the key. Recipe e3 combines asymmetric skill chaining, negative RL gradients, and a coupled curriculum, achieving strong benchmark performance and 2× budget extrapolation.

  • Motivation: Test-time scaling aims to improve reasoning by extending inference, but it remains unclear whether models improve beyond their maximum training budget.The paper motivates algorithmic procedures such as planning, self-reflection, backtracking, and search as possible mechanisms.
  • Core idea: In-context exploration guides search toward correct answers by searching multiple reasoning paths or implementing procedures as more test compute becomes available.The paper expects this capability to improve both extrapolation and generalization to unseen problems.
  • Recipe e3: Asymmetric skill chaining enables exploration, especially when verification is easier than generation, forming a verification-generation gap.The paper argues that these asymmetries are essential for RL to increase response length and attain extrapolation.
  • Recipe e3: Negative gradients from incorrect traces shift probability from short failed traces toward longer traces that chain additional asymmetries.Unlike SFT, this mechanism amplifies both response length and the exploration parameter during RL.
  • Recipe e3: A coupled curriculum links task difficulty and training token budgets to structure exploration while avoiding poor convergence at very long RL horizons.Training hard problems at short budgets can force premature commitment and harm extrapolation.
  • Results: Qwen3-1.7B trained with e3 achieves the best known sub-2B results on AIME’25 and HMMT’25 and improves consistently when deployment compute reaches 32k tokens, twice its 16k training budget.It also improves pass@32 on both benchmarks over the base model.

2. Problem Statement: Optimizing & Extrapolating Test-Time Compute

The section frames test-time scaling as post-training models to use longer reasoning traces under a fixed training budget, then asks whether performance extrapolates beyond that budget. It distinguishes RL's positive and negative gradients from SFT and motivates the extrapolation problem through diminishing gains at larger budgets.

  • Post-training setup: RL and SFT post-train base LLMs to produce longer reasoning traces under an implicitly or explicitly fixed training budget B_tr.RL optimizes outcome rewards, whereas SFT distills long traces from capable models or humans.
  • Empirical motivation: Figure 2 shows diminishing AIME 2025 gains as test-time budgets increase, with virtually no improvement from 16k to 32k.
  • RL versus SFT: RL combines positive gradients that increase likelihood for correct responses with negative gradients that decrease likelihood for incorrect responses.The displayed policy-gradient form represents both contributions through the advantage A(x,y).
  • RL versus SFT: Negative gradients drive longer responses and in-context exploration during RL, giving RL-trained models better extrapolation than SFT-based models.SFT acts as a purely positive-gradient method focused on correct traces.

3. Asymmetries in the Base Model: A Prerequisite for In-Context Exploration

The section argues that in-context exploration depends on chaining asymmetric skills, particularly easier verification with harder generation. Experiments and didactic analysis show that these asymmetries support longer traces, higher pass@k, and extrapolation, whereas their absence limits scaling gains.

  • In-context exploration: Longer traces can interleave verification and generation, allowing models to make multiple attempts and explore in context.
  • Asymmetry: Chaining asymmetries means composing skills such as generation and verification so that the combined trace outperforms generation alone.Definition 3.1 formalizes this as higher expected reward when q(p(·)) appears in a trace than when only p(·) appears.
  • Asymmetry: RL on domains with a verification-generation gap encourages asymmetric skill chaining, in-context exploration, discovery of solutions, and extrapolation to larger budgets.
  • Experimental findings: On Cdown, traces with more chained asymmetries achieve higher pass@k, and models trained at 0.5–1k tokens make steady progress at test budgets 8–16× larger.
  • RL exploration: Negative gradients increase response length, verification attempts, entropy, and response diversity, improving performance both at the training budget and under extrapolation.The reported effects occur when the base model admits asymmetries.
  • Experimental findings: Without verification-generation asymmetry, Mult gains plateau and extrapolation is weak; with the asymmetry, longer training budgets substantially improve extrapolation.The no-asymmetry base model improves by merely ≤2% despite 16× test-time compute scaling.

4. Negative Gradients Incentivize Exploration that Chains Asymmetries

Negative gradients promote both classical and structured exploration during RL by increasing response diversity and encouraging models to chain asymmetries into longer searches. These effects improve performance and test-time extrapolation, especially when the base model has a verification-generation asymmetry.

  • Mechanisms: Negative gradients drive exploration by sampling unseen token sequences and chaining asymmetries such as repeated verification attempts.This structured exploration differs from merely trying novel tokens because it exploits strategies already present in the model.
  • Empirical evidence: Figure 6 compares cumulative unique attempts on Cdown and repetitive-token endings on DMath with and without negative-gradient masking.The figure reports more unique attempts and fewer repetitive endings when negative gradients are retained.
  • Diversity: Negative gradients promote within-rollout and across-rollout diversity, whereas masking them causes entropy collapse and repetitive-token responses at larger budgets.The comparison uses standard GRPO and GRPOMask on Cdown and DMath reasoning tasks.
  • Chained exploration: Negative-gradient masking causes attempts and response length to plateau, accompanied by decreased performance; the same relative trend appears on DMath.The absolute number of chained asymmetries also declines without negative gradients, while models without asymmetries benefit less.
  • Extrapolation: Longer responses that chain asymmetries are more likely to yield correct answers, so successful chains receive positive reward and are reinforced during RL.The resulting process produces progressively more in-context exploration as training continues.

5. Analyzing Negative Gradient Dynamics in the 𝑝𝑘Model

The didactic p_k model isolates how negative gradients alter stopping, length, and action diversity when verification is perfect. They increase exploration until the correct action becomes sufficiently likely, while the LLM setting has a more gradual length response.

  • Model setup: The p_k model samples k independent actions sequentially, verifies each with perfect accuracy, and stops immediately after producing the correct action.The setup formalizes negative-gradient dynamics under a large verification-generation gap.
  • Exploration definitions: In-context exploration means avoiding stop until the correct action appears, whereas classical exploration increases the correct-action probability without reducing p(stop).Thus, the two forms of exploration differ in whether they extend the trace or only reweight actions.
  • Length dynamics: Average response length rises from 15 to 45 at training budget B_tr = 100 under standard GRPO as negative gradients reduce early stopping.After enough attempts, the correct action is sampled with non-trivial probability and reward can increase while length later drops.
  • LLM comparison: The LLM benchmarks do not show the didactic model’s rapid phase transition because discovering shortcuts to correct responses is considerably harder.The full-history conditioning of LLMs also makes rapid length reduction less likely after a transition.
  • Entropy dynamics: Negative gradients increase entropy by moving probability mass from highly likely incorrect actions toward less-seen modes, including the correct action.Theorem 5.1 states that entropy increases with probability at least π(a_1|s), while masking preserves entropy with probability 1 − π(a⋆|s).

6. Coupled Curriculum Training Structures Exploration in Long Length RL

The coupled curriculum balances optimization difficulty against in-context exploration by pairing task difficulty with training token budgets. This design enables e3 to extrapolate beyond its training budget and achieve strong benchmark and pass@k results.

  • 6.1. Training on Static Budgets or Data Mixtures is Insufficient: Training at 4k tokens achieves the best 4k performance but suppresses longer exploratory traces, while 16k training creates long-horizon optimization challenges.An 8k training budget provides the best extrapolation among the compared fixed budgets.
  • 6.1. Training on Static Budgets or Data Mixtures is Insufficient: Training only on easy problems yields the best OOD AIME’25 performance when extrapolating to 32k tokens, despite AIME’25 resembling harder problems.Matching training and test difficulty improves in-distribution performance at the training budget but not necessarily OOD extrapolation.
  • 6.2. Our Recipe e3: Coupled Curriculum for In-Context Exploration: e3 couples progressively harder datasets with selected budgets so RL rewards longer traces that chain asymmetries while keeping training budgets as small as practical.The curriculum chooses each stage’s budget to support valid exploratory completions and provide initialization for the next, harder stage.
  • 6.2. Our Recipe e3: Coupled Curriculum for In-Context Exploration: 1024 tokens produces nearly the best extrapolation to 4096 tokens on harder 7-number problems, and coupled curriculum outperforms budget-only or no-curriculum training.The 1024-token budget is selected using the curriculum heuristic with κ=1.2.
  • 6.3. Final Results with e3: State-of-the-art <2B Model on AIME/HMMT’25: At 32k test-time tokens, e3 achieves state-of-the-art performance among models under 2B on AIME’25 and HMMT’25.The Qwen3-1.7B model was trained only to 16k tokens and outperforms some larger models when extrapolated to 32k.
  • 6.3. Final Results with e3: State-of-the-art <2B Model on AIME/HMMT’25: e3 improves higher-k pass performance on AIME and HMMT’25 compared with similarly sized models, while using at most 32 rollouts per problem during GRPO training.The reported pass@k estimates use 128 rollouts per prompt for k=1 through 32.

7. Related Work

Related work studies long-chain test-time scaling, extrapolation beyond training budgets, exploration, and curricula. This paper distinguishes e3 by explaining how training choices produce extrapolation through chained exploration.

  • Scaling test-time compute via long CoT reasoning: Prior test-time scaling methods include majority voting, best-of-n sampling, beam search, and sequential self-correction, while newer work uses long free-form chains combining verification, search, and correction.The paper situates e3 within long-CoT reasoning.
  • Test-time extrapolation: Prior extrapolation studies test budgets longer than training budgets but do not explain how the training recipe relates to extrapolation.Other approaches explicitly prompt models to continue generating after termination, whereas this work studies learned extrapolation.
  • Exploration in test-time scaling: Earlier work highlights base-model exploration, while this paper reports that RL negative gradients incentivize chaining asymmetries and that SFT alone lacks these exploration benefits.The paper presents this analysis as complementary to theoretical work.
  • Data and length curricula: Prior curricula target problem difficulty or output length mainly for efficiency, whereas e3 couples data and budget curricula to structure exploration.The paper identifies coupling the two curricula as its distinct finding.

8. Discussion and Conclusion

The paper presents e3 as a recipe for enabling test-time compute extrapolation through in-context exploration, combining base-model asymmetries, negative RL gradients, and a coupled data–token curriculum. It reports strong benchmark performance and identifies limits and open questions around scale, domains, curricula, asymmetry design, and repetition.

  • e3 combines base-model asymmetries, negative gradients during RL, and a coupled curriculum over data and token budget to train in-context exploration.The recipe is designed to amplify exploration rather than merely sharpen the model distribution.
  • Applied to Qwen3-1.7B, e3 achieves state-of-the-art AIME/HMMT’25 performance, with particularly strong gains in the extrapolation regime.
  • Sharpening vs in-context exploration: RL with a coupled curriculum can chain new asymmetries and increase response length, unlike traditional sharpening that clones one or a few sampled base-model responses.The paper distinguishes an initial exploration phase from a later sharpening phase during RL.
  • Connection with dense progress rewards: The coupled curriculum is closely connected to dense progress rewards because it can be reparameterized as short-segment rewards within a single training round.
  • Introducing new asymmetries: The conceptual framework can use asymmetries beyond the verification-generation gap, motivating further study of alternative asymmetries and ways to imbue base models with them.
  • The study is limited by model scale and domain, leaving generalization to larger models and other reasoning domains for future work.

Appendices

The appendices document extrapolation evaluations, experimental procedures, auxiliary tasks, and additional evidence that chained asymmetries improve with training. They also report that reasoning-model performance generally rises with longer output budgets but often saturates near 16k tokens.

  • A. Testing Extrapolation of Open-Source Models: Figure 11 evaluates AIME 2025 pass@1 across test-time compute budgets for open-source models of different sizes trained with SFT or RL.
  • A. Testing Extrapolation of Open-Source Models: AIME 2025 is used because its challenging math problems allow meaningful reasoning beyond small context lengths, which is needed to evaluate extrapolation.
  • A. Testing Extrapolation of Open-Source Models: Inference uses approximately 32k maximum output tokens, with 16 responses per AIME problem and pass@1 computed from those responses.
  • A. Testing Extrapolation of Open-Source Models: Every reasoning-capable model generally improves pass@1 as the maximum output-token budget increases, but performance usually saturates at 16k with minor gains at 32k.
  • B.3. Additional Experiments with Mult: Mult and Mult-V compare multiplication traces with few versus multiple intermediate verification attempts, creating settings with and without a strong verification-generation asymmetry.
  • B.3. Additional Experiments with Mult: As training progresses, responses with more chained asymmetries improve more, and sequential chaining increasingly outperforms parallel rollouts at a fixed attempt budget.

B.3. In the Presence of Asymmetries, KL Divergence with Base LLM Reduces as Training Token Budget Increases

With a verification-generation asymmetry, higher training token budgets keep RL closer to the base model in token-level KL divergence while enabling chained verification and generation attempts. Additional analyses show that attempts become correlated, more predictable, and less repetitive over training.

  • Higher training token budgets produce lower token KL divergence from the base policy throughout countdown RL training when a verification-generation asymmetry is present.On multiplication without asymmetries, KL values are roughly similar across training budgets.
  • The lower divergence coexists with chaining multiple verification and generation attempts to improve accuracy.
  • New countdown attempts become increasingly correlated with past attempts rather than independent as training progresses.
  • The model becomes more certain about what to try next after more past attempts and learns not to repeat previous attempts.

C.2. Additional Experiments with Mult

Additional Mult experiments examine how negative gradients interact with verification-generation asymmetries, showing that they increase verification and accuracy primarily when the asymmetry is present. The section also relates this mechanism to in-context exploration and discusses curriculum-dependent extrapolation and implementation details.

  • C.2. Additional Experiments with Mult: Negative gradients increase verification calls in Mult-V, which has a large verification-generation gap, but not in Mult, where the gap is absent.
  • C.2. Additional Experiments with Mult: With negative gradients, accuracy is much higher in Mult-V, while chained asymmetries remain roughly unchanged in Mult.
  • C.3. Additional Details for the Didactic Setting in Sec. 4: The didactic analysis identifies negative-gradient-driven exploration with asymmetries as in-context exploration, represented by longer traces and more chained asymmetries.
  • C.3. Additional Details for the Didactic Setting in Sec. 4: In the didactic model, perfect verification means increased exploration directly appears as longer traces containing more chained asymmetries.
  • C.2. Additional Experiments with Mult: For best extrapolation, e3 varies task mixture and training budget together; the curriculum is mainly needed for extrapolation rather than fixed-budget in-distribution performance.

D.2. Fixed train budget, vary dataset curriculum on Cdown

On Cdown, varying problem difficulty while keeping the training budget fixed can produce over-exploratory traces, whereas coupling difficulty with a shorter initial budget improves later hard-problem performance.

  • Fixed train budget, vary dataset curriculum on Cdown: A fixed 1K-token budget across easy and hard Cdown problems can overfit models to over-exploratory traces.The data curriculum trains first on 3-candidate problems, then 6-candidate problems, while keeping the budget fixed.
  • Fixed train budget, vary dataset curriculum on Cdown: A coupled curriculum trains the first stage on easy problems with a 256-token budget before increasing difficulty, improving reward on hard problems.The coupled curriculum uses 256 tokens for the first 60 gradient steps, compared with 1K tokens for the fixed-budget curriculum.
  • Fixed train budget, vary dataset curriculum on Cdown: Correct-trace learning involves exploration from negative gradients followed by reinforcement from positive gradients after correct traces are discovered.This two-stage view explains why over-exploratory behavior can impair both discovery and reinforcement of correct traces.
  • Fixed train budget, vary dataset curriculum on Cdown: The coupled curriculum increases equations per attempt in the second stage, while the data curriculum plateaus, indicating first-stage overfitting to over-exploratory traces.For 3 candidates, complete attempts require two equations; for 6 candidates, they require five.
  • Fixed train budget, vary dataset curriculum on Cdown: The data curriculum converges more slowly when reinforcing correct traces on hard problems, with the authors hypothesizing noisy credit assignment on over-exploratory traces.The paper notes that it does not run many controlled experiments to identify the cause.

E. Omitted Proofs

The omitted proofs formalize how negative policy-gradient updates affect conditional entropy in a softmax policy, showing that incorrect high-probability actions can induce exploration under stated conditions.

  • Proof overview: The proof analyzes entropy changes for a softmax policy at a fixed state using a Taylor expansion around the current RL iterate.The proof overview studies correlation between the entropy gradient and the policy gradient, with sufficiently small learning rates controlling higher-order terms.
  • Policy-gradient derivation: The policy-gradient coordinate for action b is (1(b = a) − π(a|s)) · A(s,a), where 1(·) is an indicator function.The conditional policy gradient is derived for an action sampled from the policy at state s.
  • Negative-gradient entropy increase: When the most likely action is incorrect, a negative-gradient update increases conditional entropy with probability at least its sampling probability.This conclusion holds for sufficiently small learning rates and any policy in the stated softmax class.
  • Negative-gradient entropy increase: If the runner-up action is sufficiently probable, the entropy increase is lower-bounded by cη·Kε^2(1 − π̄_a) under the theorem’s conditions.The bound applies when π̄_a ≥ ε + e^−H(M^(i);s), with probability at least π̄_a.

H. Example Traces

The examples illustrate exploratory reasoning traces: one Countdown trace repeatedly tests arithmetic combinations, while another multiplication trace combines stepwise generation with verification.

  • Multiplication with verification: The multiplication example decomposes 347 × 583 digit by digit, sums partial products, and cross-verifies the result.The reported product is 202301.
  • Over-exploration in Countdown: A trained Countdown model can underthink after easy-problem training, producing at most three equations when five are needed for a complete six-candidate attempt.This example is labeled over-exploration after training only on easy problems with three candidates.
  • Chained Asymmetries in Countdown: The Countdown examples show models generating multiple candidate arithmetic paths when searching for a target number.The trace repeatedly proposes operations, rejects results as too large or invalid, and continues searching.
Loading 2506.09026v2…