# Optimal Stopping vs Best-of-N for Inference Time Optimization

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in LLM preference optimization methods, one of 10 directions in LLM alignment / RLHF / preference optimisation.
- Builds on 37 of its 46 references that are in the map.
- First posted on arXiv 1 Oct 2025.

## Placed in

- LLM alignment / RLHF / preference optimisation / [LLM preference optimization methods](https://mlsanity.com/alignment/llm-preference-optimization-methods/)

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

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [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)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022)
- [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)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [RAFT: Reward rAnked FineTuning for Generative Foundation Model Alignment](https://mlsanity.com/paper/2304.06767/) (2023)
- [Adaptive Computation Time for Recurrent Neural Networks](https://mlsanity.com/paper/1603.08983/) (2016)
- [Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint](https://mlsanity.com/paper/2312.11456/) (2023)
- [Confident Adaptive Language Modeling](https://mlsanity.com/paper/2207.07061/) (2022)
- [Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training](https://mlsanity.com/paper/2309.17179/) (2023)
- [Large Language Model Cascades with Mixture of Thoughts Representations for Cost-efficient Reasoning](https://mlsanity.com/paper/2310.03094/) (2023)
- [From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models](https://mlsanity.com/paper/2406.16838/) (2024)
- [Theoretical guarantees on the best-of-n alignment policy](https://mlsanity.com/paper/2401.01879/) (2024)
- [Fast Best-of-N Decoding via Speculative Rejection](https://mlsanity.com/paper/2410.20290/) (2024)
- [Escape Sky-high Cost: Early-stopping Self-Consistency for Multi-step Reasoning](https://mlsanity.com/paper/2401.10480/) (2024)
- [Efficient Test-Time Scaling via Self-Calibration](https://mlsanity.com/paper/2503.00031/) (2025)
- [Adaptive Inference-Time Compute: LLMs Can Predict if They Can Do Better, Even Mid-Generation](https://mlsanity.com/paper/2410.02725/) (2024)
- [Sampling-Efficient Test-Time Scaling: Self-Estimating the Best-of-N Sampling in Early Decoding](https://mlsanity.com/paper/2503.01422/) (2025)
- [Asymptotics of Language Model Alignment](https://mlsanity.com/paper/2404.01730/) (2024)
- [Routoo: Learning to Route to Large Language Models Effectively](https://mlsanity.com/paper/2401.13979/) (2024)
- [AdaEDL: Early Draft Stopping for Speculative Decoding of Large Language Models via an Entropy-based Lower Bound on Token Acceptance Probability](https://mlsanity.com/paper/2410.18351/) (2024)
- [Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index](https://mlsanity.com/paper/2406.20062/) (2024)
- [The Energy Cost of Reasoning: Analyzing Energy Usage in LLMs with Test-time Compute](https://mlsanity.com/paper/2505.14733/) (2025)

## Built on by (most cited first, 7 of 7)

- [Test-Time Compute Games](https://mlsanity.com/paper/2601.21839/) (2026)
- [ATLAS: Agentic Test-time Learning-to-Allocate Scaling](https://mlsanity.com/paper/2606.01667/) (2026)
- [Best-of-Tails: Bridging Optimism and Pessimism in Inference-Time Alignment](https://mlsanity.com/paper/2603.06797/) (2026)
- [Adaptive Generate-Rank-Verify: Inference-Time Search with Costly Verification](https://mlsanity.com/paper/2605.17609/) (2026)
- [Knowing When to Stop: Bayesian Optimal Stopping for LLM Evaluations](https://mlsanity.com/paper/2608.14425/) (2026)
- [When does a scaling result justify a different allocation? A critical review of resource-allocation evidence for AI systems](https://mlsanity.com/paper/2609.14500/) (2026)
- [Tail Competition Explains Scaling in Best-of-N Sampling for Verifiable Problems](https://mlsanity.com/paper/2610.19362/) (2026)

## Abstract (arXiv)

Large language model (LLM) generation often requires balancing output quality against inference cost, especially when using multiple generations. We introduce a new framework for inference-time optimization based on the classical Pandora's Box problem. Viewing each generation as opening a costly "box" with random reward, we develop algorithms that decide when to stop generating without knowing the underlying reward distribution. Our first contribution is a UCB-style Pandora's Box algorithm, which achieves performance that is provably close to Weitzman's algorithm, the optimal strategy when the distribution is known. We further adapt this method to practical LLM settings by addressing reward scaling across prompts via a Bradley-Terry inspired transformation. This leads to an adaptive inference-time optimization method that normalizes rewards and learns stopping thresholds on the fly. Experiments on the AlpacaFarm and HH-RLHF datasets, using multiple LLM-reward model pairs, show that our adaptive strategy can obtain the same performance as non-adaptive Best-of-N sampling while requiring 15-35 percent fewer generations on average. Our results establish a principled bridge between optimal stopping theory and inference-time scaling, providing both theoretical performance bounds and practical efficiency gains for LLM deployment.