Prefix Sliding for efficient test-time scaling

Niklas Muennighoff; Zhengyang Wang; Zeyi Chen; Weijia Shi; Binyuan Hui; John Yang; Dapeng Jiang; Mika Senghaas

cs.CLAug 26, 2026

Prefix Sliding for efficient test-time scaling

Authors: Niklas Muennighoff, Zhengyang Wang, Zeyi Chen, Weijia Shi, Binyuan Hui, John Yang, Dapeng Jiang, Mika Senghaas, +10 more

Organizations: Stanford University · University of California at Santa Barbara · University of Washington · Prime Intellect

Abstract

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

Figures & tables

Figure 1: Prefix Sliding without any training is more efficient than full attention. Prefix Sliding performs better as it can generate more tokens in the same thinking time than full attention, not because each token it generates is better. Both use the same Qwen3 model ( section 3 ). Here, Prefix Sliding uses a window size of 4096; see Appendix B for other sizes, and Appendix C for the results in tabular form.

Figure 2: The first and last few tokens receive most attention during reasoning with full attention. We plot post-softmax attention probabilities averaged across layers and attention heads in Qwen3-1.7B for an AIME25 reasoning trace. Probabilities are Gaussian smoothed.

Figure 3: Prefix Sliding enables efficient long-horizon test-time scaling while full attention inevitably becomes prohibitively expensive. For Prefix Sliding, the cost at each generation step is constant as attention is only paid to the prefix and sliding window tokens. For full attention, the cost grows at each step due to more tokens in the attention window.

Figure 4: Position embeddings (PE) with Prefix Sliding.

Figure 5: Backpropagating long reasoning traces with Prefix Sliding. Yellow marks backpropagated tokens.

Figure 6: Prefix Sliding faster than full attention. We generate 1024 sequences of the respective sequence length with vLLM using its auto batch size, FlashAttention, one 80GB Nvidia H100 GPU, and a window size of 4096 tokens for sliding methods.

Figure 7: Prefix Sliding can improve performance. We restrict both to near-equal memory budgets: 8,192 max tokens for full attention and an 8,192 sliding window size for Prefix Sliding.

Figure 9: Prefix Sliding outperforms test-time scaling alternatives. See Figure 3 for visual explanations of Prefix Sliding and full attention. For benchmarking on AIME25, we use a maximum generation length of 262144 and a local window of 4096 for all methods except full attention. Thus, after generating 4096 tokens, the window either slides or is restarted with the last k tokens or summary. We set k and the maximum summary length to 256 tokens. See section 3 and Appendix G for additional hyperparameters.

Figure 10: Prefix Sliding has constant cost per new token in the limit. “L” is where the sequence length reaches the size of the sliding window + the prefix. Last k and summary follow a sawtooth pattern with a cost spike at each chunk end, as the last k tokens need to be passed over or the entire chunk summarized.

Figure 11: LiveCodeBench (LCB) requires Prefix Sliding with a window of at least 16384 to match full attention. Max tokens are 262144.

Figure 12: Fast tasks benefit less from Prefix Sliding. The sliding window size is 2048 for Prefix Sliding.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 13: Figure 1 with sliding window size 8192 (top) and 16384 (bottom).

Window	AIME25		GPQA		MATH500		Tok/s at
size	avg@64	avglen	avg@64	avglen	avg@64	avglen	32K	128K
2048	27.7	47643	35.9	30107	89.8	9310	8973	8737
4096	33.9	29943	37.0	16707	91.5	7069	5479	5224
8192	35.8	19373	38.0	13605	91.4	6229	3291	2788
16384	35.3	19872	38.2	14378	91.5	6160	2441	1420
Full	34.2	19158	37.6	11403	91.7	6056	1477	448

Appendix

Table 1: Prefix Sliding achieves performance comparable to full attention at significantly higher speeds . These performance numbers are used for figures throughout the paper.

Figure 14: Continue PE performs similarly to reset PE. The benchmark is AIME25 and the shaded area represents the standard error. The sliding window size is 2048.

Figure 15: Prefix Sliding with truncated backpropagation can match full attention.

$k$ tokens	MATH500	AIME25
64	58.2	3.2
128	59.7	3.5
256	60.8	4.2
512	60.3	4.2
1024	54.6	2.4

Appendix

Table 2: Ablating last

k

. Results are avg@64 with a 2048-token context and one pass. We select

k=256

, which performs best while keeping the carried context small.

Prompt	AIME25
	Accuracy	Coverage
1: Tool only ( Figure 16 , Figure 17 )	23.2	33.3
2: Tool/context examples ( Figure 18 , Figure 17 )	26.4	53.3
3: Tool/context examples with info ( Figure 18 , Figure 19 )	25.8	46.7

Appendix

Table 3: Summary prompt ablations. The first figure in the brackets is the system prompt; the second is the user prompt after a summary is produced (the first turn is unmodified). cov@64 is coverage across 64 samples, i.e., if any of the 64 are correct, it is counted as correct.

Panel of Figure 16 — Figure 16: System prompt framing summary as a tool.

Panel of Figure 17 — Figure 17: User prompt inserting context simply.

Panel of Figure 18 — Figure 18: System prompt with tool-usage and context-usage examples.

Panel of Figure 19 — Figure 19: User prompt inserting context with extra info.

Panel of Figure 20 — Figure 20: Summary duplicate processing problem on AIME sample. The model ignores its prior derivations and starts the task anew.

Panel of Figure 21 — Figure 21: Last k duplicate processing issue on AIME sample. We mark the repetition and where the carried-over 256 tokens end .

Panel of Figure 22 — Figure 22: Reasoning in comments issue on LiveCodeBench sample.

Explore similar work

Beyond the Frontier: Stochastic Backtracking for Efficient Test-Time Scaling
May 24, 2026Dao Tran, Duc Anh Le, Ngoc Luu +3Inference-Time Scaling Efficient Language Model Reasoning
Qualcomm AI Research†
Efficient Test-Time Scaling via Temporal Reasoning Aggregation
Apr 19, 2026Jiakun Li, Xingwei He, Kefan Li +3Test-Time Scaling Efficient Language Model Inference
School of Computer Science and Engineering, Beihang University · 3Hangzhou Innovation Institute, Beihang University · 2Qingdao Research Institute, Beihang University
ThinkRetrieve: Retrieval-Augmented Reasoning Traces for Test-Time Scaling
Aug 11, 2026Vaibhav Singh, Soumya Suvra Ghosal, Sarvesh Gharat +3Numerical Reasoning in Language Models Test-Time Scaling
IIT Bombay · University of Maryland, College Park · Adobe Research

May 24, 2026J/K move · Enter open · S save

Beyond the Frontier: Stochastic Backtracking for Efficient Test-Time Scaling

Dao Tran, Duc Anh Le, Ngoc Luu, Quan Pham+2

Qualcomm AI Research†

Inference-Time Scaling Efficient Language Model Reasoning

Open paper AskPDF arXiv

Test-time scaling improves language model reasoning by spending additional compute to explore multiple solution trajectories. The key challenge is to maximize accuracy while minimizing the total number of generated tokens during reasoning. Recent PRM-guided methods score intermediate prefixes to steer this search, but most are frontier-only: they keep only the current active prefixes and irreversibly prune or resample away the rest using noisy PRM scores. This can cause premature commitment, diversity collapse, and the loss of prefixes that still admit correct continuations. We introduce stochastic backtracking over a persistent pool of historical prefixes, allowing test-time compute to revisit previously generated states instead of only expanding the current frontier. To make this efficient, we propose two complementary mechanisms. Subpool Selection strengthens greedy PRM-guided search by applying Top-N selection within random subpools, giving historical prefixes a chance to bypass over-scored frontier candidates. Power Backtrack Sequential Monte Carlo extends SMC-style resampling to the persistent pool using powered PRM scores and mixture-corrected weights. Across mathematical reasoning benchmarks and model scales, our methods consistently achieve higher accuracy per token count, and the same level of accuracy using only a fraction of the token count in comparison to strong PRM-guided baselines, demonstrating that persistent-pool stochastic backtracking provides a simple and effective way to improve the accuracy-token trade-off in test-time scaling.

Abstract

Explore similar work

Beyond the Frontier: Stochastic Backtracking for Efficient Test-Time Scaling

Efficient Test-Time Scaling via Temporal Reasoning Aggregation

ThinkRetrieve: Retrieval-Augmented Reasoning Traces for Test-Time Scaling