mlsanityData to 7 Oct 2026

ExpBoN: Exponential-Noise Best-of-n for Efficient Test-Time LLM Alignment

arXiv 2609.21899 ↗First posted 18 Sep 2026cs.LG cs.IT math.ITcited by 0

On the map: LLM alignment / RLHF / preference optimisation → LLM preference optimization methods also fits: Process reward models for reasoning

Abstract (arXiv)

Best-of-n (BoN) sampling is a simple yet effective inference-time alignment method, but hard maximization provides only coarse control over the trade-off between reward and distribution shift. Soft Best-of-n (Verdun et al. 2025) provides smoother control and converges to the optimal distribution associated with KL-regularized reward maximization. In this paper, we introduce ExpBoN, an alternative soft BoN method based on the exponential-noise report-noisy-max mechanism. It admits an exact finite-n decomposition, which yields exponentially fast convergence in total variation, expected reward, and both directions of KL divergence. We provide comprehensive theoretical analyses of its convergence and regret behavior. We further integrate ExpBoN into the guided speculative inference (GSI) framework (Geuter, Mroueh, and AlvarezMelis 2025), resulting in ExpGSI, for efficient reward-guided LLM alignment. ExpGSI yields substantial reductions in computational cost while maintaining comparable accuracy. Experiments on MATH500, MMLU-STEM, and Minerva Math with the Qwen2.5-Math and Qwen3 model families show that ExpGSI reduces estimated computation by 14%-39% across candidate budgets for Qwen2.5-Math and by up to 45% at n=16 for Qwen3. Overall, our results provide a theoretical and algorithmic foundation for exponential-noise BoN and efficient test-time LLM alignment.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Placed in LLM preference optimization methods, one of 10 directions in LLM alignment / RLHF / preference optimisation. Builds on 35 of its 50 references that are in the map. First posted on arXiv 18 Sep 2026.

Builds on

35 of 50 references.

Closest ancestors · 11

Same direction, newest first

  1. 2026Best-of-Tails: Bridging Optimism and Pessimism in Inference-Time Alignment6 Mar
  2. 2026Revisiting the (Sub)Optimality of Best-of-N for Inference-Time Alignment5 Mar
  3. 2025Best-of-N through the Smoothing Lens: KL Divergence and Regret Analysis8 Jul
  4. 2025Guided Speculative Inference for Efficient Test-Time Alignment of LLMs4 Jun
  5. 2025AdaBoN: Adaptive Best-of-N Alignment17 May
  6. 2025Soft Best-of-n Sampling for Model Alignment6 May
  7. 2025Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment27 Mar
  8. 2025Evaluation of Best-of-N Sampling Strategies for Language Model Alignment18 Feb
  9. 2024BoNBoN Alignment for Large Language Models and the Sweetness of Best-of-n Sampling2 Jun
  10. 2024Regularized Best-of-N Sampling with Minimum Bayes Risk Objective for Language Model Alignment1 Apr
  11. 2022Training language models to follow instructions with human feedback4 Mar

Other references · 24

  1. 2025Qwen3 Technical Reportcited by 8,195
  2. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 7,916
  3. 2020Measuring Massive Multitask Language Understandingcited by 7,768
  4. 2023Efficient Memory Management for Large Language Model Serving with PagedAttentioncited by 5,767
  5. 2021On the Opportunities and Risks of Foundation Modelscited by 3,961
  6. 2017Deep reinforcement learning from human preferencescited by 3,846
  7. 2023Let's Verify Step by Stepcited by 3,598
  8. 2020Learning to summarize from human feedbackcited by 2,562
  9. 2022Solving Quantitative Reasoning Problems with Language Modelscited by 1,359
  10. 2024Qwen2.5-Math Technical Report: Toward Mathematical Expert Model via Self-Improvementcited by 1,057
  11. 2022Scaling Laws for Reward Model Overoptimizationcited by 1,056
  12. 2025Scalable Best-of-N Selection for Large Language Models via Self-Certaintycited by 182
12 more
  1. 2022Calibrating Sequence likelihood Improves Conditional Language Generationcited by 121
  2. 2024Theoretical guarantees on the best-of-n alignment policycited by 116
  3. 2024Fast Best-of-N Decoding via Speculative Rejectioncited by 112
  4. 2025Reward-Guided Speculative Decoding for Efficient LLM Reasoningcited by 106
  5. 2021A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learningcited by 82
  6. 2020Permute-and-Flip: A new mechanism for differentially private selectioncited by 22
  7. 2024Permute-and-Flip: An optimally stable and watermarkable decoder for LLMscited by 17
  8. 2021The Permute-and-Flip Mechanism is Identical to Report-Noisy-Max with Exponential Noisecited by 14
  9. 2024Universal Exact Compression of Differentially Private Mechanismscited by 8
  10. 2025Test-time Verification via Optimal Transport: Coverage, ROC, & Sub-optimalitycited by 3
  11. 2026Scalable Differentially Private Data Compression via Diffusion and Stochastic Codescited by 3
  12. 2026Flexible Empowerment at Reasoning with Extended Best-of-N Samplingcited by 2

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Reward-Shifted Speculative Sampling Is An Efficient Test-Time Weak-to-Strong Aligner
  2. 2025Aligning LLMs on a Budget: Inference-Time Alignment with Heuristic Reward Models
  3. 2024Variational Best-of-N Alignment
  4. 2026Efficient Best-of-N policy evaluation for inference-time alignment
  5. 2026Gradient-Guided Reward Optimization for Inference-time Alignment
  6. 2024Faster WIND: Accelerating Iterative Best-of-N Distillation for LLM Alignment
  7. 2025RoBoN: Routed Online Best-of-n for Test-Time Scaling with Multiple LLMs
  8. 2026Demystifying the unreasonable effectiveness of online alignment methods