PaperlayerView exact revision on arXiv

Source-linked AI summary

Prefix Sliding for efficient test-time scaling

Niklas Muennighoff, Zhengyang Wang, Zeyi Chen, Weijia Shi, Binyuan Hui, John Yang, Dapeng Jiang, Mika Senghaas, Fares Obeid, Johannes Hagemann, Sami Jaghouar, Ludwig Schmidt, Percy Liang, Jason Wei, Andrew Y. Ng, Luke Zettlemoyer, Yejin Choi, Mike Lewis

arXiv:2608.26070v1cs.CLcs.AIcs.LG

TL;DR

Full-attention test-time scaling retains entire reasoning traces, making long-context reasoning prohibitively expensive. Prefix Sliding retains the prefix and recent tokens; it matches full-attention performance while running 3× faster and enables reinforcement-learning rollouts beyond 100,000 tokens.

  • Problem

    Full-attention test-time scaling retains entire reasoning traces, making long-context reasoning prohibitively expensive.

    Source: §1 · p. 2

  • Method

    Prefix Sliding keeps the prefix and a sliding window in memory, evicting older intermediate tokens as the window advances.

    Source: §1 · p. 2

  • Results

    3× faster while matching full-attention performance, Prefix Sliding also enables reinforcement-learning rollouts beyond 100,000 tokens.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Prefix Sliding provides a route to very long-horizon test-time scaling with constant cost for each additional token.

    Source: §1 · p. 2

    Without training, some tasks such as LiveCodeBench require a larger window to match full attention because relevant earlier code can fall outside it.

    Source: Limitations · p. 9

Abstract

from arXiv · show

Test-time scaling uses extra test-time compute to improve performance, such as letting language models reason longer when solving a problem. As models keep the entire reasoning trace in memory via full attention, hard tasks that need long thinking can be prohibitively expensive. However, we find most intermediate reasoning tokens lose importance as the model continues reasoning. This calls into question whether retaining them is worth the cost. Based on this insight, we propose Prefix Sliding, which discards tokens during reasoning that are not part of the prefix or the window of the last few thousand tokens. The prefix has key instructions and tools available to the model, while the most recent tokens are the current reasoning the model is working on. This caps the total memory requirement regardless of how long the model reasons, allowing for efficient long-horizon test-time scaling. Without training, Prefix Sliding can make existing models 3x faster while maintaining performance. Training with Prefix Sliding using reinforcement learning can achieve better performance by enabling scaling to reasoning traces beyond a hundred thousand tokens. Ablations show Prefix Sliding outperforms summarizing intermediate tokens or vanilla sliding window. Our code is at https://github.com/Muennighoff/prefix-sliding

1 Introduction

Prefix Sliding retains the prefix and a recent-token window to bound memory and keep generation cost constant with trace length; it matches full-attention performance while running 3× faster without training and enables reinforcement-learning rollouts beyond 100,000 tokens.

1 Introduction

  • Full attention makes long reasoning prohibitively costly because each new token's cost grows with trace length; long contexts can also distract, poison context, loop, or lose knowledge.Source: §1 · p. 2
  • Intermediate reasoning tokens lose importance, whereas the prefix carries task and tool instructions and recent tokens capture current reasoning; the prefix also acts as an attention sink.Source: §1 · p. 2
  • Prefix Sliding retains the prefix and an advancing window, evicting older intermediate tokens and making next-token cost constant regardless of generated length.A 100-token prefix and 4096-token window keep at most 4196 tokens in memory.Source: §1 · p. 2
  • Prefix Sliding matches full-attention performance while running 3× faster without training, and enables reinforcement-learning rollouts beyond 100,000 tokens.Source: §1 · p. 2

2 Prefix Sliding

Prefix Sliding retains the prompt prefix and a recent-token window instead of all intermediate reasoning. The section explains its inference-time position-embedding choice, long-rollout training with truncated backpropagation, and attention-kernel implementation.

Prefix Sliding kernel implementation

  • Prefix Sliding retains the prefix and recent window, which receive more attention than intermediate tokens, while masking partial tiles and skipping irrelevant ones keeps per-step attention cost constant.The kernel applies an elementwise mask to tiles that partially overlap the allowed region and skips tiles entirely outside it.Source: §2 · pp. 2–4, Figure 3 · p. 3

Prefix Sliding without training

  • Without training, Prefix Sliding applies to generative models out of the box; Continue PE reuses cached representations more efficiently than Reset PE, with insignificant observed performance differences.The authors use Continue PE; Reset PE requires reapplying position embeddings to tokens.Source: §2 · p. 3, Figure 4 · p. 3

Prefix Sliding with training

  • Training supports very long RL rollouts, and experiments use truncated backpropagation, which can match full attention with full backpropagation in Appendix E.For a 100,000-token trace with a 2048-token window, the example sends the last 8192 tokens to the trainer, using 6144 as context and computing RL loss on the final 2048; asynchronous RL avoids idle GPUs, though synchronous RL also works.Source: §2 · pp. 3–4

3 Setup

Experiments use Qwen3-1.7B with custom Prefix Sliding support, GRPO training, and standard reasoning benchmarks evaluated under fixed sampling and verification settings.

Modeling

  • Modeling uses Qwen3-1.7B unless otherwise specified, with vLLM, FlashAttention, and custom Nvidia Hopper kernels for Prefix Sliding.Sliding-window sizes range from 512 to 16384 tokens; for summary ablations, the model writes the summary as a tool call rather than using an external model.Source: §3 · p. 4

Training

  • Reinforcement learning uses GRPO through synchronous trl or asynchronous prime-rl implementations, with other hyperparameters fixed across comparisons.Training uses a custom math dataset filtered for guessability, verifiability, and difficulty; gradients use either the full generation or only the last sliding window, passing four times as many last tokens to the trainer in the latter case.Source: §3 · p. 4

Evaluation

  • Evaluation covers GPQA, MATH500, and AIME25, averaging 64 runs and measuring efficiency by average thinking time per sample.Generations use temperature 0.6, top p 0.95, simpleverify answer checking, and budget forcing without “Wait” tokens; FLOPs and generated tokens are proxies that miss memory differences.Source: §3 · p. 4

4 Results

Prefix Sliding improves efficiency without training and enables reinforcement learning with longer reasoning traces and higher rewards at near-equal memory budgets. Training uses a 4× window multiplier to reduce log-probability mismatch, with comparable performance to full attention reported for a 7B model when sequence length is controlled.

Prefix Sliding without training

  • Prefix Sliding is faster than full attention and approaches regular sliding-window speed, while its throughput stabilizes around 5,000 tokens as full attention keeps slowing.The initial throughput drop occurs before the generated sequence reaches the window; after that, each new token costs the same to generate.Source: Figure 6 · p. 5, §4 · p. 5

Prefix Sliding with training

  • At near-equal memory budgets, reinforcement learning with Prefix Sliding enables longer reasoning traces and higher rewards.Figure 7 compares 8,192-token limits for full attention and Prefix Sliding; the prose attributes the higher rewards to longer traces.Source: Figure 7 · p. 5, §4 · p. 5
  • Passing only the final 2K-token window yields KL above 0.1; passing 4K lowers mismatch, while 8K is slightly lower and roughly on par with 16K.Most runs use 8K, or 4× the 2K window; residual mismatch is attributed to numerical differences between generator and trainer attention kernels.Source: §4 · p. 5, Figure 8 · p. 5
  • With an 8,192-token window and a 4× multiplier, a trained 7B model performs comparably to full attention when sequence length is controlled.The paper reports this result in Appendix E.Source: §4 · p. 5

5 Ablations

Across the alternatives, Prefix Sliding provides the best performance-efficiency tradeoff and adds only one hyperparameter: sliding-window size. The alternatives have distinct costs or limitations, including loss of task-critical prefix information, token reprocessing, and summary overhead.

5 Ablations

  • The ablations compare Prefix Sliding with three key alternatives in Figure 9, with an additional cache-eviction comparison detailed in Appendix G.Appendix G also describes hyperparameter selection.Source: §5 · p. 6

Last k

  • Last k deletes all but the most recent k tokens at threshold n, but large k causes reprocessing while small k can drop useful tokens and require regeneration.Its memory use also drops drastically when context is cleared, making compute use harder to optimize.Source: Last k · p. 6

Summary

  • Summarization restarts reasoning with a summary at threshold n, but adds hyperparameters, summary-generation overhead, repeated processing, and volatile memory use.Although the summary can draw on the current context, models struggle to retain important information over many turns.Source: Summary · p. 7

Sliding window

  • Prefix Sliding provides the best performance-efficiency tradeoff with only sliding-window size as a hyperparameter; pure sliding window flattens as it loses task-critical prefix tokens.Last k and summary approaches can reach good performance, but token reprocessing and the extra summary step constrain them and add complexity.Source: Sliding window · p. 7

6 Related Work

Related work frames long-horizon reasoning as a test-time scaling problem: parallel methods face diminishing returns, while sequential scaling is constrained by growing attention costs. Prefix Sliding bounds per-token cost after the prefix and window are full, while working with existing pretrained models.

Test-time scaling

  • Parallel test-time scaling has diminishing returns, while sequential scaling can scale better but remains limited by transformers’ quadratic complexity on long reasoning traces.Prefix Sliding is presented as a simple method that improves reasoning efficiency and enables long-horizon scaling at constant cost.Source: §6 · p. 7

Context extension

  • Prefix Sliding’s per-token cost becomes bounded once the sequence reaches the combined size of its prefix and sliding window, a condition needed for infinite test-time scaling.Full attention is unbounded because each generated token becomes more expensive; Figure 10 illustrates Prefix Sliding’s bounded cost.Source: §6 · p. 8
  • Unlike bounded RNN, SSM, and transformer approaches that require model adaptation, Prefix Sliding works with pretrained models out of the box and can also be used in training.Examples include RWKV (Peng et al., 2023; 2024), Mamba (Gu & Dao, 2024; Dao & Gu, 2024; Gu et al., 2022), and transformer-based approaches (Dai et al., 2019; Chevalier et al., 2023; Tandon et al., 2025).Source: §6 · p. 8
  • Last-k and summary methods are bounded and work out of the box, but deleting and refilling context causes irregular costs and duplicate-token latency that Prefix Sliding bypasses.Figure 10 shows the irregular costs; section 5 details the latency overhead.Source: §6 · p. 8
  • Prefix Sliding resembles sliding-window attention with global tokens, using a consecutive prefix to preserve task instructions and context; StreamingLLM instead retains only a few fixed initial tokens, such as 4.The related comparison is with sliding-window attention with global tokens and StreamingLLM.Source: §6 · p. 8

7 Conclusion

The conclusion presents Prefix Sliding as a way to support extremely long reasoning horizons while improving efficiency even at short horizons. It can be used without further training or during reinforcement-learning training, and outperforms alternatives that also support infinite test-time scaling.

7 Conclusion

  • Prefix Sliding is more efficient than full attention even for reasoning horizons of only thousands of tokens.It is proposed to enable language models to reason for extremely long horizons.Source: §7 · p. 8
  • Prefix Sliding can be applied to language models without further training or used during reinforcement-learning training.Source: §7 · p. 8
  • Prefix Sliding outperforms alternatives that could also support infinite test-time scaling.The conclusion frames longer reasoning as a way to inspire work on solving harder problems with language models.Source: §7 · p. 8

Limitations

Prefix Sliding’s limitations include narrow comparison scope, cases that require larger windows or gain little from sliding, and challenges with bulky system outputs and multi-turn instructions. The paper evaluates scaling only up to hundreds of thousands of thinking tokens and 7B-parameter models.

Limited comparisons

  • Comparisons are limited to methods that work out of the box on pretrained transformers and have bounded per-token cost, excluding alternative architectures, subquadratic methods, and mixed sliding windows.Comparing bounded-cost alternatives such as RNNs is left to future work because controlling compute and hyperparameters may require pretraining from scratch (Tay et al., 2020; Bulatov et al., 2022; He et al., 2025b; Li et al., 2025c).Source: Limitations · p. 8

Information loss

  • LiveCodeBench needs a Prefix Sliding window of at least 16384 tokens to match full attention, as code may move outside the window while the model reasons in comments.The authors suggest RL training could adapt commenting behavior, or a mechanism to append sliding tokens to the prefix or another knowledge store could help.Source: Figure 11 · p. 9, Limitations · p. 9

Limited benefit for short generations

  • HealthBench requires 2086 tokens on average, so with a 2048-token window Prefix Sliding rarely evicts tokens and offers little speed-up over full attention.Generations shorter than the window remain in the warm-up phase, during which attention is effectively full.Source: Figure 12 · p. 9, Limitations · p. 9

System outputs and multi-turn

  • Website or file outputs can exceed the window and obscure important content, while future user instructions also raise questions about what belongs in the prefix.Proposed mitigations include careful behavior learned through RL, step-by-step reading, and guardrails that limit excessive outputs; similar issues affect summarization and last-k methods with the same window size.Source: Limitations · p. 9

Scale

  • The study scales Prefix Sliding to hundreds of thousands of thinking tokens and 7B-parameter models, but further scaling and trend analysis remain for future work.These experiments cover both training-free and reinforcement-learning training setups.Source: Limitations · p. 9

Reproducibility Statement · A Extended Related Work · B Other sliding window sizes

The appendices describe Prefix Sliding’s reproducibility, place it among KV-cache and efficient-thinking methods, and show results for two additional sliding-window sizes. They note that Prefix Sliding can be used during RL and on already-trained models, but does not reduce pre-fill KV-cache cost.

Reproducibility Statement

  • Prefix Sliding is described in Section 2, and the authors say its simplicity and public code make reproducing the key results likely straightforward.The code is available at the project’s GitHub repository.Source: Reproducibility Statement · p. 10

A Extended Related Work

  • The related-work section groups KV-cache methods by whether they target pre-fill, post-fill, or both, distinguishing prompt-cache reduction from management after prompt processing.Source: A Extended Related Work · p. 21
  • Post-fill approaches often evict older cache entries by recency, while other methods address memory through hardware-aware optimization or quantization.Source: A Extended Related Work · p. 21
  • Prefix Sliding does not reduce pre-fill KV-cache cost, which can cause high memory use with extremely long prefixes; prompt-information pruning or context management are suggested options.For long inputs such as a relevant book, the passage suggests providing a file path so the model can read it step by step.Source: A Extended Related Work · p. 21
  • The related-work section distinguishes train-time efficient-thinking methods, which often target RL algorithms or infrastructure, from test-time methods designed for existing models.Source: A Extended Related Work · p. 21
  • Prefix Sliding is both a train-time and test-time method: it can be used during RL and applied to already-trained models for improved efficiency and performance.Source: A Extended Related Work · p. 21

B Other sliding window sizes

  • Figure 13 shows Figure 1 with sliding-window sizes of 8192 tokens at the top and 16384 tokens at the bottom.Source: Figure 13 · p. 21

C Tabular results · D Continue vs Reset PE · E Truncated backpropagation validation

Prefix Sliding is reported to match full attention’s performance at higher speeds; the additional evaluations find similar results for Continue and Reset PE and comparable performance with truncated backpropagation under the tested setup.

C Tabular results

  • Prefix Sliding achieves performance comparable to full attention at significantly higher speeds.The table’s performance numbers are used for figures throughout the paper.Source: Table 1 · p. 22

D Continue vs Reset PE

  • Continue PE performs similarly to Reset PE on AIME25 with a sliding window size of 2048.The shaded area represents standard error.Source: Figure 14 · p. 22

E Truncated backpropagation validation

  • With truncated backpropagation, Prefix Sliding can match full attention in the reported experiment.Figure 15 depicts a short experiment with DeepSeek-R1-Distill-Qwen-7B using prime-rl for asynchronous reinforcement learning.Source: Figure 15 · p. 22, E Truncated backpropagation validation · p. 22
  • Both models passed 32,768 tokens to the trainer, while Prefix Sliding backpropagated 8,192 tokens with a multiplier of 4 and used an 8,192-token window.The experiment used truncated backpropagation.Source: E Truncated backpropagation validation · p. 22
  • The authors characterize the truncated-backpropagation comparison as preliminary and say that larger-scale experiments are needed.The reported performance was comparable.Source: E Truncated backpropagation validation · p. 22
  • The authors use truncated backpropagation in their experiments, while noting that much longer chains may require chunked backpropagation.They cite Figure 7 as an example of their experiments using truncated backpropagation.Source: E Truncated backpropagation validation · p. 22

F Training Dataset … H Analyzing outputs

The appendices describe the reinforcement-learning dataset and filtering criteria, choices for last-k and summary baselines, and observed limitations of alternative methods and generated outputs.

F Training Dataset

  • The training set combines SkyWork and s1 sources and is decontaminated against test data using the s1 setup.The s1 sources include math, science, and benchmark datasets.Source: F Training Dataset · p. 23
  • Problems are filtered for guessability, verifiability, and difficulty, removing easily guessed, hard-to-verify, always-solved, and never-solved samples.Guessability is tested with small models on eight attempts; difficulty is assessed across repeated model scoring.Source: F Training Dataset · p. 23

H Analyzing outputs

G.1 Last k hyperparameters

  • k = 256 is selected for last-k runs because it performs best while keeping carried context small.At context exhaustion, 256 tokens are prepended to the next generation; subsequent generation is shortened by 256 tokens to keep total thinking tokens constant.Source: Table 2 · p. 23, §G.1 · p. 23

G.2 Summary hyperparameters

  • The summary baseline uses a forced tool call at 256 remaining context tokens; prompt 2 raises performance, while prompt 3 does not help.The model itself generates the summary, and the summary length is not deducted from later generation, leaving it slightly more tokens in memory than Prefix Sliding or last k.Source: §G.2 · p. 23

G.3 H2O

  • H2O (Zhang et al., 2023) retains recent tokens and high-attention “heavy hitters,” but may discard prefix tokens and lacks FlashAttention/vLLM integration.Combining it with Prefix Sliding could preserve both future-useful prefix tokens and important intermediates, though reinforcement-learning integration may be challenging.Source: §G.3 · p. 26

H Analyzing outputs

  • Figure 20 shows a summary duplicate-processing issue in which the model ignores prior derivations and starts the task anew.The paper notes it may instead use the summary without mentioning it in its reasoning.Source: §G.2 · p. 23, Figure 20 · p. 26
  • Figure 22 identifies a “reasoning in comments” issue in a LiveCodeBench sample.Source: Figure 22 · p. 28

Related papers

Loading 2608.26070v1…