PaperlayerView exact revision on arXiv

Source-linked AI summary

Think Longer to Explore Deeper: Learn to Explore In-Context via Length-Incentivized Reinforcement Learning

Futing Wang, Jianhao Yan, Yun Luo, Ganqu Cui, Zhi Wang, Xiaoye Qu, Yue Zhang, Yu Cheng, Tao Lin

arXiv:2602.11748v1cs.CL

TL;DR

In-context exploration needs longer trajectories to cover broader reasoning states, but long sequences are exponentially hard to sample. Length-Incentivized Exploration combines length incentives with a redundancy penalty and increases exploratory reasoning behavior, including backtracking from 103 to 121.

  • Problem

    Longer reasoning trajectories support broader state coverage, yet their sampling probability decays exponentially, creating a Shallow Exploration Trap for in-context exploration.

  • Method

    Length-Incentivized Exploration rewards longer trajectories while penalizing redundancy to expand in-context state coverage without repetitive generation.

  • Results

    LIE consistently increased four reasoning activities, including backtracking, which rose from 103 to 121.

  • Takeaways & Limitations

    The recipe demonstrates that additional computation can be systematically converted into more effective reasoning through in-context exploration.

  • Takeaways & Limitations

    Directly maximizing distinct context states can cause loss of efficacy and reward hacking during reinforcement-learning training.

Abstract

from arXiv · show

Achieving effective test-time scaling requires models to engage in In-Context Exploration -- the intrinsic ability to generate, verify, and refine multiple reasoning hypotheses within a single continuous context. Grounded in State Coverage theory, our analysis identifies a critical bottleneck to enabling this capability: while broader state coverage requires longer reasoning trajectories, the probability of sampling such sequences decays exponentially during autoregressive generation, a phenomenon we term the ``Shallow Exploration Trap''. To bridge this gap, we propose Length-Incentivized Exploration(\method). This simple yet effective recipe explicitly encourages models to explore more via a length-based reward coupled with a redundancy penalty, thereby maximizing state coverage in two-step manner. Comprehensive experiments across different models (Qwen3, Llama) demonstrate that \method effectively incentivize in-context exploration. As a result, our method achieves an average improvement of 4.4\% on in-domain tasks and a 2.7\% gain on out-of-domain benchmarks.

1. Introduction

The introduction frames in-context exploration—generating, verifying, and refining multiple hypotheses within one context—as critical to sequential test-time scaling, but underexplored. It identifies state coverage as an exploration-quality proxy and proposes Length-Incentivized Exploration (LIE) to maximize it through length rewards and redundancy penalties.

  • Test-time scaling comprises Parallel Scaling, which aggregates independent samples, and Sequential Scaling, which uses extended reasoning chains or iterative refinement.
  • In-context exploration generates, verifies, and refines multiple hypotheses within a continuous context, making it critical for unlocking sequential scaling.
  • State coverage, interpreted as in-context state diversity, is adopted as a theoretical proxy for exploration quality.
  • Length-Incentivized Exploration (LIE) maximizes in-context state coverage by combining a length reward that elevates the upper bound of states with a redundancy penalty that matches state count to length.Experiments compare LIE with GRPO and GSPO baselines across Qwen3 and LLaMA models.
  • The “Shallow Exploration Trap” is identified as the bottleneck of in-context exploration and supported by theoretical derivations and empirical validation.The cited theory includes Proposition 4.1 and Lemma 4.2, while the empirical validation appears in Figure 3.

2. Related Work

Related work studies scaling test-time computation through long chains of thought and controlling reasoning length through adaptive strategies. These lines of work motivate exploration-oriented reasoning while addressing efficiency and controllability.

  • Scaling Test-Time Compute via Long CoT: Long-chain-of-thought training scales test-time computation by enabling strategic behaviors such as verification and self-correction.The cited works report significant performance gains for large language models across various domains.
  • Length-Aware Reasoning: Length-aware reasoning research aims to mitigate overthinking while improving reasoning efficiency and controllability.Several studies adaptively switch between long and short chains of thought according to problem difficulty during training.

3. Background

This section models autoregressive LLM reasoning as an MDP whose exponentially large state space makes state coverage central to exploration. It reviews policy-gradient optimization, GRPO and GSPO, and count-based exploration before motivating trajectory-level state-diversity measurement for in-context exploration.

  • LLM Reasoning as an MDP: LLM reasoning is formulated as an MDP in which states are prompt-plus-generated-token sequences and actions select the next vocabulary token.The state space consists of token sequences, while the action space is the vocabulary.
  • LLM Reasoning as an MDP: The state space grows exponentially with sequence length, with |S| ≈ |V|^L, making it vast and sparse.This combinatorial structure creates a fundamental challenge for exploration.
  • Reinforcement Learning for LLM Reasoning: Policy-gradient reinforcement learning optimizes the policy to maximize expected return, with GRPO and GSPO as framework instantiations.The section introduces policy-gradient optimization as the standard approach for training the reasoning policy.
  • Policy Optimization Methods: GRPO performs token-level optimization without a value function, whereas GSPO performs sequence-level optimization using length-normalized importance ratios.GRPO averages token-level PPO-clip losses, while GSPO computes its objective once per sequence.
  • Count-Based Exploration: Count-based exploration uses state visitation counts as a proxy for state coverage and augments extrinsic rewards with an exploration bonus.The approach is guided by Optimism in the Face of Uncertainty to balance exploration and exploitation.
  • Count-Based Exploration: For in-context exploration, visitation counts must measure state diversity within a single reasoning trajectory rather than aggregate coverage across training episodes.This adapts the count-based exploration principle from standard reinforcement learning to reasoning performed in one continuous context.

4. In-Context Exploration

In-context exploration measures and maximizes state coverage within a single reasoning trajectory, using abstracted local patterns to make visitation meaningful. The section identifies trajectory length as exploration capacity, while exponentially declining sampling of long sequences creates a shallow exploration trap.

  • At test time, in-context exploration maximizes state coverage within a single trajectory rather than across the global state space.
  • Raw autoregressive states are unique because each contains a distinct history prefix, making direct count-based coverage trivial and meaningless.
  • A state abstraction based on last-n-grams maps literal histories to logical reasoning states, enabling meaningful pseudo-visitation counts and coverage estimates.
  • In-Context Distinct State Count Ccontext(τ) measures the number of unique context states visited in one trajectory, capturing covered state-space volume.
  • Directly maximizing Ccontext can reduce efficacy and trigger reward hacking in reinforcement-learning training, consistent with Goodhart’s law.
  • Trajectory length L strictly upper-bounds exploration utility, so longer sequences are necessary to raise exploration capacity, but long-sequence sampling probability decays exponentially.

GRPO GSPO

The section shows that longer trajectories expand state coverage and improve reasoning accuracy, but standard RL methods struggle to generate sufficiently long, non-redundant exploration. GRPO plateaus in length and performance, while GSPO expands length too slowly and both methods suffer declining information density.

  • Exploration-Length Conflict: Long trajectories are necessary for broad state coverage but exponentially unlikely to be sampled, creating the Shallow Exploration Trap.This conflict is formalized by Proposition 4.1 and Lemma 4.2.
  • Length, Coverage, and Performance: Longer response length strongly correlates with Ccontext and improved reasoning accuracy, making trajectory extension the primary mechanism for expanding exploration volume.The observed Pearson correlation is ρ(L, Ccontext) > 0.96.
  • Limitations of Standard RL Training: GRPO reaches a performance plateau as response length stabilizes, whereas GSPO continues growing length but does so prohibitively slowly.Both algorithms eventually fail to push L far enough to reach complex states.
  • Limitations of Standard RL Training: As response length increases, the Distinct Ccontext Ratio (Rcontext) tends to decrease, indicating increasingly redundant exploration.The findings motivate exploration that is both longer and more efficient.

5. Length-Incentivized Exploration

Length-Incentivized Exploration (LIE) shapes reinforcement-learning rewards to encourage longer reasoning when immediate solutions fail and to convert that added capacity into broader, less redundant in-context state coverage. Its two-step design combines a length reward with a redundancy penalty while prioritizing correct responses.

  • LIE is a targeted reward-shaping recipe that enforces in-context exploration in reinforcement learning.
  • The length reward encourages trajectories to exceed the initial policy’s typical depth when an attempted response is incorrect.It uses a sample-wise target L_target,i = L_ref,i + ∆L and creates a curriculum for extending reasoning beyond usual depth.
  • The redundancy penalty discourages repeated in-context states, because state coverage satisfies C_context(τ) ≤ L and reaches equality only when redundancy is minimized.The penalty uses visitation counts of state abstractions, with threshold Θ and penalty magnitude β.
  • Maximizing R_len + R_red maximizes state coverage in two steps: the length reward raises the state-count upper bound, while the redundancy penalty matches coverage to trajectory length.
  • The final reward favors correct responses and longer reasoning trajectories while penalizing redundant exploration to encourage test-time scaling.

6. Experiments

Experiments show that LIE improves benchmark performance and test-time scaling by expanding in-context and global state exploration. The gains generalize across models and training stages, while cognitive-behavior analyses and ablations clarify how length incentives and redundancy penalties shape exploration.

  • Performance and test-time scaling: On Qwen3-4B-Base, LIE with GSPO raises average in-domain accuracy from 49.4% to 53.8% and OOD accuracy from 62.7% to 67.1%.It also yields a 6.2% gain on AIME25.
  • Performance and test-time scaling: LIE produces a superior Long-CoT scaling curve, whereas standard RL models saturate or degrade beyond their learned policy length.The method maintains an upward performance trend by using the extended token budget to explore broader hypothesis spaces.
  • Cross-model generalization: Across Qwen3-4B and Llama-OctoThinker, LIE delivers consistent 2%–3% gains while universally expanding state coverage.The resulting longer trajectories are converted into improved in-context exploration.
  • Exploration dynamics: LIE sustains global state-coverage growth and significantly higher policy entropy, avoiding the saturation and rapid entropy drop associated with GSPO’s premature convergence.The sustained exploration helps the policy discover rare, high-value states and prevents mode collapse.
  • Continual scaling: Stage 2 curriculum training with a relaxed 12k token limit produces continuous improvement, showing that LIE converts additional compute into reasoning accuracy.This establishes a scaling trend with the allocated reasoning horizon.
  • Ablation and reasoning behaviors: Length-only rewards expand Ccontext and improve accuracy but reduce Rcontext through redundant generation, motivating a redundancy penalty.LIE also increases reasoning activities across all measured categories, with Backtracking rising from 103 to 121.

7. Conclusion … A.2. Exponential Decay of Long Sequences

The paper frames broader state coverage as essential for in-context exploration but difficult to obtain because long autoregressive reasoning sequences are exponentially unlikely. It addresses this bottleneck with Length-Incentivized Exploration, connecting additional computation to more effective reasoning.

  • 7. Conclusion: Length-Incentivized Exploration addresses this bottleneck with a length-based reward and redundancy penalty, explicitly activating in-context exploration and improving state coverage.The conclusion describes LIE as a simple recipe that converts additional computation into more effective reasoning.
  • A.1. Count-Based Exploration Theoretical Foundation: Exploration is especially difficult in LLM reasoning because sparse rewards and vast state-action spaces amplify deficient exploration and poor sample efficiency.This motivates exploration mechanisms that prioritize less-visited states or actions.
  • A.1. Count-Based Exploration Theoretical Foundation: Count-based exploration augments reward estimates for less-visited actions with an exploration bonus, providing a theoretically grounded optimism principle.The passage presents this as a classic approach to the exploration-exploitation tradeoff.
  • A.1. Count-Based Exploration Theoretical Foundation: Count-based bandit exploration achieves cumulative regret that grows only logarithmically over time.Theorem A.1 establishes the theoretical optimality of the strategy described in the passage.
  • A.1. Count-Based Exploration Theoretical Foundation: Extensions to MDPs count state-action pairs and add bonuses for less-visited pairs, with near-optimality established in the PAC-MDP framework.The passage attributes these extensions to Bellemare et al. (2016), Tang et al. (2017), Strehl & Littman (2008), and Kolter & Ng (2009).
  • A. Theoretical Foundation: Broader state coverage helps discover rare correct reasoning chains and avoid premature convergence, but direct state-action counting is computationally and statistically inefficient in language spaces.The method instead uses response length as a coarse-grained abstraction of the state space.
  • A.2. Exponential Decay of Long Sequences: Longer reasoning trajectories broaden state coverage, but Lemma A.2 states that the sampling probability of length-L states is upper-bounded by an exponentially decaying function of L.The lemma concerns response states with sentence length L and sampling probability p(S_L).

B. Experimental Details … C.4. Synergizing with SFT: Injection vs. Activation

The experiments use standardized prompting and RL settings, then evaluate LIE’s failure modes, training dynamics, scalability, and synergy with SFT. Results show that LIE promotes longer, broader reasoning and complements SFT by activating injected reasoning patterns.

  • B.1. Template Prompt: Qwen experiments use Qwen3 or Qwen-Nothinking templates, while Llama-OctoThinker training uses the original prompt from Wang et al. (2025b).The Qwen template asks models to reason step by step and place the final answer inside boxed delimiters.
  • B.2. Implementation of RL: RL experiments implement GRPO and baselines with Verl, use unified hyperparameters across algorithms and models, and omit entropy regularization and KL-based losses.These choices define the shared training setup reported in Table 4.
  • C.1. Pitfalls of Direct State Coverage Maximization: Directly maximizing Ccontext initially increases state coverage but causes collapse into semantically hollow, structurally diverse tokens and sharply reduces reasoning accuracy.LIE instead uses length as a proxy to encourage exploration without this failure mode.
  • C.2. Training dynamics of OctoThinker: LIE-enhanced GSPO enables OctoThinker-3B-Base to think longer and provides a reliable mechanism for performance extrapolation across policy models.Figure 11 compares standard GSPO with the LIE-enhanced approach.
  • C.3. Scalability Across Model Scales: LIE consistently improves performance across Qwen3-1.7B-Base, 4B-Base, and 8B-Base, regardless of base-model capacity.The cross-scale evaluation is summarized in Table 5.
  • C.3. Scalability Across Model Scales: 7.6%, 4.4%, and 2.5% are LIE’s in-domain reasoning-average improvements for the 1.7B, 4B, and 8B models over GSPO, respectively.On OOD tasks, the 8B LIE model reaches 73.4% average accuracy, improving 2.9% over baseline.
  • C.4. Synergizing with SFT: Injection vs. Activation: SFT fine-tunes Qwen3-4B-Base for 3 epochs on 4k oracle-CoT problems generated by GPT-OSS-120B, using a 4,096-token context limit.The dataset is sampled from the training set.
  • C.4. Synergizing with SFT: Injection vs. Activation: SFT injects reasoning primitives, while LIE activates them to extend trajectories from approximately 5k tokens toward 7k+ and expand distinct state coverage.SFT-initialized runs begin with higher coverage and accuracy, whereas SFT+GSPO tends to plateau near L ≈5k; the highest performance comes from SFT GSPO + ILE.

C.5. Hyperparameter Sensitivity Analysis

The method remains robust across state-abstraction and redundancy-penalty settings, with n = 10 and Θ = 10 providing effective balances. Moderate lengthening supports stable exploration, whereas aggressive extension destabilizes training; higher β preserves accuracy while promoting concision.

  • Sensitivity to State Abstraction (n-gram): Relative performance trends remain consistent across n ∈{6, 10, 15}, showing improvements are not artifacts of a specific state-abstraction configuration.Small n = 6 overreacts to syntactic patterns, while large n = 15 makes states overly sparse and obscures the Shallow Exploration Trap.
  • Sensitivity to State Abstraction (n-gram): n = 10 balances semantic logical-step capture with filtering low-level syntactic noise.This choice avoids the structural-token redundancy noise observed at n = 6 and the sparse-state limitation observed at n = 15.
  • Impact of Lengthening (∆L): Moderate extension, ∆L = 100, 500, activates exploration capacity and yields stable growth in trajectory length and accuracy.The increment limit ∆L controls how quickly the model expands its reasoning horizon.
  • Impact of Lengthening (∆L): Aggressive extension, ∆L = 8k, destabilizes training by inducing degenerate repetition loops and degrading reasoning quality.Immediately demanding maximum length removes the progressive constraint before the model can legitimately reason at such lengths.
  • Impact of Repetition Threshold (Θ): Avg 52.7% is achieved at Θ = 10, while Θ = 6 reduces AIME25 performance to 21.5% versus the baseline’s 22.2%.A strict threshold over-penalizes natural repetition, whereas Θ = 15 permits repetitive low-entropy sequences that game Rlen.
  • Impact of Repetition Magnitude β: Final reasoning accuracy is robust to β, with β = 0.3 and β = 0.6 achieving nearly identical convergence.Higher β = 0.6 produces shorter trajectories and faster policy-entropy decrease, encouraging efficient high-density reasoning paths.

C.6. Ablation Study of the Reward Shaping Recipe

The ablation study shows that length reward and redundancy penalty play complementary roles in enabling effective in-context exploration. Their combination converts increased sequence length into deeper, more diverse reasoning rather than redundant thought padding.

  • Component-wise effects: Length reward Rlen increases total distinct state count Ccontext and breaks the “Shallow Exploration Trap,” but causes very large lengths and a sharply lower distinct ratio Rcontext through “thought padding.”Without constraints, the model satisfies the length requirement by generating redundant reasoning.
  • Component-wise effects: Redundancy penalty Rred preserves a high Rcontext and prevents repetition, but leaves average trajectory length L low, limiting deeper exploration.The penalty alone does not provide sufficient drive to navigate deeper into the state space for complex reasoning.
  • Synergistic recipe: The complete GSPO + LIE recipe combines Rlen’s exploration budget with Rred’s diversity filtering, producing steady growth in Ccontext and length while maintaining a healthy Rcontext.This interaction creates the synergistic effect identified as key to effective in-context exploration.
  • Synergistic recipe: The LIE recipe converts raw sequence length into effective reasoning depth rather than functioning as merely the sum of its components.Its effectiveness depends on the interaction between length reward and redundancy penalty.

D. Case Study

The case study shows that LIE transforms shallow, linear reasoning into deeper and wider exploration with branching, verification, and error correction. Across 40 AIME samples, its reasoning graphs exhibit increased depth and width, indicating broader state-space search.

  • Qualitative Analysis: The GSPO baseline follows a linear, shallow path, fails to cross-check intermediate steps, and reaches the incorrect answer 324.This qualitative comparison uses a representative AIME problem where the baseline fails and LIE succeeds.
  • Qualitative Analysis: LIE activates in-context exploration by spawning alternative hypotheses, performing explicit self-verification, and correcting calculation errors through branching and backtracking.The richer reasoning topology enables recovery from an erroneous calculation.
  • Quantitative Structural Metrics: 13.8 →14.75 depth and 2.15 →2.30 width show that LIE expands reasoning chains and branching across 40 AIME samples.Depth measures maximum path length, while width measures average branching factor.
  • Quantitative Structural Metrics: The increased width reflects broader exploration of parallel hypotheses or verification paths rather than empty-token padding, enabling more thorough state-space navigation.The structural metrics connect length incentives to a broader search horizon.
Loading 2602.11748v1…