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

• URL: http://arxiv.org/abs/2503.01422v2
• Date: Wed, 15 Oct 2025 05:14:57 GMT
• Title: Sampling-Efficient Test-Time Scaling: Self-Estimating the Best-of-N Sampling in Early Decoding
• Authors: Yiming Wang, Pei Zhang, Siyuan Huang, Baosong Yang, Zhuosheng Zhang, Fei Huang, Rui Wang,
• Abstract summary: Test-time scaling enhances large language model performance by allocating additional compute resources during inference.<n>Best-of-N (BoN) sampling serves as a common sampling-based scaling technique.<n>We propose Self-Truncation Best-of-N (ST-BoN), a decoding method that avoids fully generating all N samples.<n>In terms of cost, 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.
• Score: 48.55176091771745
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• CarBoN: Calibrated Best-of-N Sampling Improves Test-time Reasoning [62.56541355300587]
  We introduce a general test-time calibration framework that adaptively modifies the model toward high-reward reasoning paths.<n>Within this framework, we propose CarBoN, a two-phase method that first explores the solution space and then learns a calibration of the logits.<n>Experiments on MATH-500 and AIME-2024 show that CarBoN improves efficiency, with up to $4times$ fewer rollouts to reach the same accuracy.
  arXiv  Detail & Related papers  (2025-10-17T14:04:37Z)
• $\ exttt{SPECS}$: Faster Test-Time Scaling through Speculative Drafts [55.231201692232894]
  $textttSPECS$ is a latency-aware test-time scaling method inspired by speculative decoding.<n>Our results show that $textttSPECS$matches or surpasses beam search accuracy while reducing latency by up to $sim$19.1%.
  arXiv  Detail & Related papers  (2025-06-15T05:50:05Z)
• Accelerated Test-Time Scaling with Model-Free Speculative Sampling [58.69141724095398]
  We introduce STAND (STochastic Adaptive N-gram Drafting), a novel model-free speculative decoding approach.<n>We show that STAND reduces inference latency by 60-65% compared to standard autoregressive decoding.<n>As a model-free approach, STAND can be applied to any existing language model without additional training.
  arXiv  Detail & Related papers  (2025-06-05T07:31:18Z)
• Satori-SWE: Evolutionary Test-Time Scaling for Sample-Efficient Software Engineering [51.7496756448709]
  Language models (LMs) perform well on coding benchmarks but struggle with real-world software engineering tasks.<n>Existing approaches rely on supervised fine-tuning with high-quality data, which is expensive to curate at scale.<n>We propose Test-Time Scaling (EvoScale), a sample-efficient method that treats generation as an evolutionary process.
  arXiv  Detail & Related papers  (2025-05-29T16:15:36Z)
• Sample, Don't Search: Rethinking Test-Time Alignment for Language Models [55.2480439325792]
  We introduce QAlign, a new test-time alignment approach. As we scale test-time compute, QAlign converges to sampling from the optimal aligned distribution for each individual prompt. By adopting recent advances in Markov chain Monte Carlo for text generation, our method enables better-aligned outputs without modifying the underlying model or even requiring logit access.
  arXiv  Detail & Related papers  (2025-04-04T00:41:40Z)
• Evaluation of Best-of-N Sampling Strategies for Language Model Alignment [6.4706370001155955]
  Best-of-N (BoN) sampling with a reward model has been shown to be an effective strategy for aligning Large Language Models (LLMs) with human preferences at the time of decoding.<n>Previous work proposes Regularized BoN sampling (RBoN), a BoN sampling with regularization to the objective, and shows that it outperforms BoN sampling.<n>This paper proposes an extension of the RBoN framework, called RBoN sampling (SRBoN), which is a theoretically guaranteed approach to worst-case RBoN proxy reward.
  arXiv  Detail & Related papers  (2025-02-18T09:18:02Z)
• Efficient NeRF Optimization -- Not All Samples Remain Equally Hard [9.404889815088161]
  We propose an application of online hard sample mining for efficient training of Neural Radiance Fields (NeRF) NeRF models produce state-of-the-art quality for many 3D reconstruction and rendering tasks but require substantial computational resources.
  arXiv  Detail & Related papers  (2024-08-06T13:49:01Z)
• Variational Best-of-N Alignment [57.617866305771756]
  Best-of-N (BoN) is a popular and effective algorithm for aligning language models to human preferences.<n>We propose to fine-tune the language model to mimic what BoN does during inference.<n>Our approach is analogous to mean-field variational inference and, thus, we term it variational BoN (vBoN)
  arXiv  Detail & Related papers  (2024-07-08T15:59:44Z)
• It's all about PR -- Smart Benchmarking AI Accelerators using Performance Representatives [40.197673152937256]
  Training of statistical performance models often requires vast amounts of data, leading to a significant time investment and can be difficult in case of limited hardware availability. We propose a novel performance modeling methodology that significantly reduces the number of training samples while maintaining good accuracy. We achieve a Mean Absolute Percentage Error (MAPE) of as low as 0.02% for single-layer estimations and 0.68% for whole estimations with less than 10000 training samples.
  arXiv  Detail & Related papers  (2024-06-12T15:34:28Z)
• An Efficient Rehearsal Scheme for Catastrophic Forgetting Mitigation during Multi-stage Fine-tuning [55.467047686093025]
  A common approach to alleviate such forgetting is to rehearse samples from prior tasks during fine-tuning.<n>We propose a sampling scheme, textttbf mix-cd, that prioritizes rehearsal of collateral damage'' samples.<n>Our approach is computationally efficient, easy to implement, and outperforms several leading continual learning methods in compute-constrained settings.
  arXiv  Detail & Related papers  (2024-02-12T22:32:12Z)
• Decreasing the Computing Time of Bayesian Optimization using Generalizable Memory Pruning [56.334116591082896]
  We show a wrapper of memory pruning and bounded optimization capable of being used with any surrogate model and acquisition function. Running BO on high-dimensional or massive data sets becomes intractable due to this time complexity. All model implementations are run on the MIT Supercloud state-of-the-art computing hardware.
  arXiv  Detail & Related papers  (2023-09-08T14:05:56Z)
• Infor-Coef: Information Bottleneck-based Dynamic Token Downsampling for Compact and Efficient language model [0.0]
  Excessive overhead leads to large latency and computational costs. We propose a model accelaration approaches for large language models. Our model achieves an 18x FLOPs speedup with an accuracy degradation of less than 8% compared to BERT.
  arXiv  Detail & Related papers  (2023-05-21T13:30:56Z)
• Tensor Slicing and Optimization for Multicore NPUs [2.670309629218727]
  This paper proposes a compiler optimization pass for Multicore NPUs, called Slicing Optimization (TSO) TSO identifies the best tensor slicing that minimizes execution time for a set of CNN models. Results show that TSO is capable of identifying the best tensor slicing that minimizes execution time for a set of CNN models.
  arXiv  Detail & Related papers  (2023-04-06T12:03:03Z)
• Fast Bayesian Optimization of Needle-in-a-Haystack Problems using Zooming Memory-Based Initialization [73.96101108943986]
  A Needle-in-a-Haystack problem arises when there is an extreme imbalance of optimum conditions relative to the size of the dataset. We present a Zooming Memory-Based Initialization algorithm that builds on conventional Bayesian optimization principles.
  arXiv  Detail & Related papers  (2022-08-26T23:57:41Z)
• Effective Model Sparsification by Scheduled Grow-and-Prune Methods [73.03533268740605]
  We propose a novel scheduled grow-and-prune (GaP) methodology without pre-training the dense models. Experiments have shown that such models can match or beat the quality of highly optimized dense models at 80% sparsity on a variety of tasks.
  arXiv  Detail & Related papers  (2021-06-18T01:03:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.