# Sampling-Efficient Test-Time Scaling: Self-Estimating the Best-of-N Sampling in Early Decoding

arXiv: https://arxiv.org/abs/2503.01422 · HTML: https://mlsanity.com/paper/2503.01422/

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 57 of its 66 references that are in the map.
- First posted on arXiv 3 Mar 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)
- LLM alignment / RLHF / preference optimisation / [LLM preference optimization methods](https://mlsanity.com/alignment/llm-preference-optimization-methods/)

## Builds on (most cited first, 30 of 57)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [WebGPT: Browser-assisted question-answering with human feedback](https://mlsanity.com/paper/2112.09332/) (2021)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [s1: Simple test-time scaling](https://mlsanity.com/paper/2501.19393/) (2025)
- [Hierarchical Neural Story Generation](https://mlsanity.com/paper/1805.04833/) (2018)
- [Scaling Laws for Reward Model Overoptimization](https://mlsanity.com/paper/2210.10760/) (2022)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations](https://mlsanity.com/paper/2312.08935/) (2023)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Abstractive Text Summarization Using Sequence-to-Sequence RNNs and Beyond](https://mlsanity.com/paper/1602.06023/) (2016)
- [AlpacaFarm: A Simulation Framework for Methods that Learn from Human Feedback](https://mlsanity.com/paper/2305.14387/) (2023)

## Built on by (most cited first, 30 of 63)

- [Stop Overthinking: A Survey on Efficient Reasoning for Large Language Models](https://mlsanity.com/paper/2503.16419/) (2025)
- [Reasoning Models Can Be Effective Without Thinking](https://mlsanity.com/paper/2504.09858/) (2025)
- [A Survey of Efficient Reasoning for Large Reasoning Models: Language, Multimodality, and Beyond](https://mlsanity.com/paper/2503.21614/) (2025)
- [Efficient Reasoning Models: A Survey](https://mlsanity.com/paper/2504.10903/) (2025)
- [PolyMath: Evaluating Mathematical Reasoning in Multilingual Contexts](https://mlsanity.com/paper/2504.18428/) (2025)
- [Harnessing the Reasoning Economy: A Survey of Efficient Reasoning for Large Language Models](https://mlsanity.com/paper/2503.24377/) (2025)
- [Reasoning on a Budget: A Survey of Adaptive and Controllable Test-Time Compute in LLMs](https://mlsanity.com/paper/2507.02076/) (2025)
- [A Comprehensive Survey on Trustworthiness in Reasoning with Large Language Models](https://mlsanity.com/paper/2509.03871/) (2025)
- [MUR: Momentum Uncertainty guided Reasoning for Large Language Models](https://mlsanity.com/paper/2507.14958/) (2025)
- [Generative AI Act II: Test Time Scaling Drives Cognition Engineering](https://mlsanity.com/paper/2504.13828/) (2025)
- [TrimR: Verifier-based Training-Free Thinking Compression for Efficient Test-Time Scaling](https://mlsanity.com/paper/2505.17155/) (2025)
- [Parallel-Probe: Towards Efficient Parallel Thinking via 2D Probing](https://mlsanity.com/paper/2602.03845/) (2026)
- [Slim-SC: Thought Pruning for Efficient Scaling with Self-Consistency](https://mlsanity.com/paper/2509.13990/) (2025)
- [Certified Self-Consistency: Statistical Guarantees and Test-Time Training for Reliable Reasoning in LLMs](https://mlsanity.com/paper/2510.17472/) (2025)
- [From Efficiency to Adaptivity: A Deeper Look at Adaptive Reasoning in Large Language Models](https://mlsanity.com/paper/2511.10788/) (2025)
- [Exploring the System 1 Thinking Capability of Large Reasoning Models](https://mlsanity.com/paper/2504.10368/) (2025)
- [Revisiting Model Interpolation for Efficient Reasoning](https://mlsanity.com/paper/2510.10977/) (2025)
- [LLMs Improving LLMs: Agentic Discovery for Test-Time Scaling](https://mlsanity.com/paper/2605.08083/) (2026)
- [AdaBoN: Adaptive Best-of-N Alignment](https://mlsanity.com/paper/2505.12050/) (2025)
- [Diversity-Enhanced Reasoning for Subjective Questions](https://mlsanity.com/paper/2507.20187/) (2025)
- [VLA-ATTC: Adaptive Test-Time Compute for VLA Models with Relative Action Critic Model](https://mlsanity.com/paper/2605.01194/) (2026)
- [Neural Chain-of-Thought Search: Searching the Optimal Reasoning Path to Enhance Large Language Models](https://mlsanity.com/paper/2601.11340/) (2026)
- [FoE: Forest of Errors Makes the First Solution the Best in Large Reasoning Models](https://mlsanity.com/paper/2604.02967/) (2026)
- [Fractured Chain-of-Thought Reasoning](https://mlsanity.com/paper/2505.12992/) (2025)
- [Optimal Stopping vs Best-of-N for Inference Time Optimization](https://mlsanity.com/paper/2510.01394/) (2025)
- [CtrlCoT: Dual-Granularity Chain-of-Thought Compression for Controllable Reasoning](https://mlsanity.com/paper/2601.20467/) (2026)
- [Reward Modeling for Reinforcement Learning-Based LLM Reasoning: Design, Challenges, and Evaluation](https://mlsanity.com/paper/2602.09305/) (2026)
- [Measuring Reasoning Utility in LLMs via Conditional Entropy Reduction](https://mlsanity.com/paper/2508.20395/) (2025)
- [Mitigating Overthinking in Large Reasoning Language Models via Reasoning Path Deviation Monitoring](https://mlsanity.com/paper/2603.14251/) (2026)
- [PREMISE: Scalable and Strategic Prompt Optimization for Efficient Mathematical Reasoning in Large Models](https://mlsanity.com/paper/2506.10716/) (2025)

## Abstract (arXiv)

Test-time scaling enhances large language model performance by allocating additional compute resources during inference. Best-of-N (BoN) sampling serves as a common sampling-based scaling technique, broadening the search space in parallel to find better solutions from the model distribution. However, its cost-performance trade-off is still underexplored. Two main challenges limit the efficiency of BoN sampling: (1) Generating N full samples consumes substantial GPU memory, reducing inference capacity under limited resources. (2) Reward models add extra memory and latency overhead, and training strong reward models introduces potential training data costs. Although some studies have explored efficiency improvements, none have addressed both challenges at once. To address this gap, we propose Self-Truncation Best-of-N (ST-BoN), a decoding method that avoids fully generating all N samples and eliminates the need for reward models. It leverages early sampling consistency in the model's internal states to identify the most promising path and truncate suboptimal ones. In terms of cost, ST-BoN reduces dynamic GPU memory usage by over 80% and inference latency by 50%. In terms of cost-performance trade-off, ST-BoN achieves the same performance as Full-BoN while saving computational cost by 70%-80%, and under the same cost, it can improve accuracy by 3-4 points.