Research map / Architectures and efficiency / RNNs and normalization
Sampling-Efficient Test-Time Scaling: Self-Estimating the Best-of-N Sampling in Early Decoding
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes ST-BoN, a best-of-N decoding method that uses early hidden-state (chain-of-embedding) consistency to truncate suboptimal samples without a reward model, cutting memory and latency while matching Full-BoN accuracy at lower cost.
Problem
Best-of-N sampling is costly in GPU memory (N full KV caches) and latency, and reward-model-based selection adds memory, latency, and training-data costs; no prior method addresses both at once.
Approach
Estimate the most promising sample in early decoding by measuring internal consistency of hidden-state trajectories (chain-of-embedding curvature features) across the N samples, truncate the rest, and use a buffer window of length proportional to the earliest pairwise-divergence time before choosing the final sample by majority vote over per-step picks.
Key results
- ST-BoN reduces dynamic GPU memory usage by over 80% and inference latency by up to 50% relative to Full-BoN.
- ST-BoN matches Full-BoN performance while saving 70-80% computational cost; under equal cost it improves accuracy by 3-4 points.
- Under equal cost, ST-BoN scales to about N=80 where Full-BoN w/ RM only reaches N=3.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace majority-voting selection with CoE-based selection in Full-BoN | Full-BoN w/o RM · MATH and MMLU | Accuracy: mostly higher at N>=10 (e.g., MATH N=80 74.9 vs 74.5) | Helped |
| Remove buffer window (single self-estimation at time c) (ablation) | ST-BoN · MATH and MMLU, early-final consistency | Early-final consistency | Hurt |
| Replace CoE measure with semantic or string similarity for early consistency (ablation) | ST-BoN · MATH and MMLU, early-final consistency | Early-final consistency | Hurt |
| Increase sampling-time temperature T (from 0.7 upward) (ablation) | ST-BoN · MMLU | Accuracy and computational cost | Mixed |
| Vary top-k and top-p sampling parameters (ablation) | ST-BoN · MMLU | Accuracy and computational cost | No clear effect |
| Extend buffer window beyond tau = c (ablation) | ST-BoN · MATH, MMLU, TheoremQA (N=10) | Accuracy vs cost | Mixed |
| Use ST-BoN (CoE early truncation with buffer window) instead of Full-BoN w/o RM at equal cost | Qwen2.5-7B-Instruct · objective tasks | Accuracy: 3-4 points higher accuracy at same cost | Helped |
| Use ST-BoN instead of Full-BoN at equal performance | Qwen2.5-7B-Instruct · objective tasks | Computational cost: 70-80% lower cost for matching accuracy | Helped |
Surprising findings
- Using chain-of-embedding consistency under full generation outperforms majority voting self-consistency in most cases.
- Semantic (Rouge-L) and string-based early consistency perform near random, while hidden-state CoE is markedly better.
Limitations
- Requires access to hidden states, so it does not apply to closed-source models such as GPT-4 series.
- Buffer window length tau is fixed to c and not adaptive to task complexity.
- Full-BoN w/o RM with self-consistency remains slightly stronger than ST-BoN at equal N in absolute accuracy.
Experimental setup
Datasets: MATH TheoremQA GPQA MMLU CNNDM AlpacaFarm
Benchmarks: MATH TheoremQA GPQA MMLU CNNDM AlpacaFarm
Metrics: accuracy peak GPU memory cost wall-clock time cost Rouge-L human score win rate
Baselines: Full-BoN w/o RM (self-consistency) Full-BoN w/ RM (Skywork-o1-Open-PRM-7B) SBoN CARDS TreeBoN ASC ESC Qwen2.5-Math-PRM-7B RLHFlow-PRM-Mistral-8B ArmoRM-Llama-3-8B
Builds on: self-consistency chain-of-embedding best-of-n sampling zero-shot chain-of-thought
Closest papers by meaning
- ATTS: Asynchronous Test-Time Scaling via Conformal Prediction (ICLR 2026 · similarity 0.89)
- Inference-Aware Fine-Tuning for Best-of-N Sampling in Large Language Models (ICLR 2025 · similarity 0.88)
- XTC: Head-Aware Sampling by Excluding Top Choices (NeurIPS 2026 · similarity 0.88)
- Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment (ICML 2025 · similarity 0.88)
- Tail Competition Explains Scaling in Best-of-N Sampling for Verifiable Problems (NeurIPS 2026 · similarity 0.88)
- Test-Time Scaling in the Wild: Why Exploitation, Not Exploration, Is the Bottleneck (NeurIPS 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.