Optimal Stopping vs Best-Of-$N$ for Inference Time Optimization

## Abstract

Abstract 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 N sampling while requiring 15-35% 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.

## 1 Introduction

Large language models (LLMs) are increasingly deployed in applications where both quality and efficiency are critical (Achiam et al., 2023; Hoffmann et al., 2022). A widely used approach to improve generation quality is Best-of-$N$ sampling: generate $N$ candidate responses, score them with a reward model, and select the best (Nakano et al., 2021; Touvron et al., 2023). While effective, this approach wastes compute: the number of generations is fixed in advance, even if an acceptable output is found early or if a prompt is inherently easy (Wang et al., 2025; Sun et al., 2024; Manvi et al., 2024). As models scale and inference costs rise, the need for adaptive inference-time strategies that dynamically balance quality and compute has become urgent (Snell et al., 2025; Jin et al., 2025).

Several recent methods have sought to improve inference-time efficiency. More efficient reranking strategies (e.g., Best-of-$N$, rejection sampling, majority-vote) improve quality but can still over-generate (Wang et al., 2025; Manvi et al., 2024; Jain et al., 2023; Wang et al., 2022). Speculative decoding accelerates sampling by offloading work to a smaller draft model, but it does not address how many generations to produce (Leviathan et al., 2023; Chen et al., 2023). Early stopping heuristics exist in practice, yet they lack theoretical guarantees and often underperform on difficult prompts (Agrawal et al., 2024; He et al., 2025; Wei et al., 2025). Overall, there lacks a principled framework for deciding when to stop generating while maintaining near-optimal reward.

In this paper, we introduce a new perspective by connecting LLM inference with the classical Pandora’s Box problem from optimal stopping theory (Weitzman, 1978). In our view, each generation corresponds to opening a costly “box” that yields a random reward. The task is to decide whether to stop and accept the best reward so far or continue generating, *without knowing the underlying reward distribution*. This abstraction provides a rigorous foundation for inference-time optimization, subsuming heuristics like Best-of-$N$ as special cases.

#### Our Contributions.

We develop both theoretical and practical foundations for adaptive LLM inference on the following three fronts:

- 1.
A UCB-style Pandora’s Box algorithm.
We propose the first stopping strategy for the Pandora’s Box problem that adapts to *unknown reward distributions*. By maintaining anytime-valid confidence bounds on the optimal stopping threshold, our algorithm guarantees vanishing regret relative to Weitzman’s optimal policy, which assumes full distributional knowledge. (^1^11We note, however, that Weitzman’s algorithm applies to multiple box types. Our results are concerned with the i.i.d. special case, though we expect effective the natural generalization of our approach to multiple boxes will apply to generation from LLM ensembles)
- 2.
A practical adaptive meta-generation framework.
To handle cross-prompt reward scaling issues, we introduce a Bradley–Terry inspired transformation that normalizes rewards. This yields a general-purpose meta-generation procedure that dynamically learns stopping thresholds.
- 3.
Empirical validation.
On the AlpacaFarm and HH-RLHF dataset, across multiple LLM–reward model pairs, our adaptive strategy achieves the same reward as non-adaptive Best-of-$N$ sampling while requiring 15-35% fewer generations on average. This establishes that principled stopping rules yield concrete efficiency gains in realistic settings.

### 1.1 Related Works

Inference-Time Optimization.
A growing body of work studies how to allocate inference-time compute more effectively. Beyond Best-of-$N$, (Nakano et al., 2021; Touvron et al., 2023; Wang et al., 2025; Sun et al., 2024; Manvi et al., 2024), recent methods frame test-time scaling as adaptive self-calibration (Huang et al., 2025). Chain-of-thought prompting and self-consistency (Wei et al., 2022; Wang et al., 2022) also improve reliability by generating multiple reasoning paths, though at the cost of substantial extra compute. Lastly, Snell et al. (2025) show that prompt-adaptive compute allocation can outperform model scaling, while Jin et al. (2025) analyze energy–accuracy tradeoffs. See the survey by Welleck et al. (2024) for a comprehensive review.

Early Stopping, Confidence, and Adaptive Decoding.
Several works address the question of *when to stop* allocating further computation. Classic approaches include adaptive computation time (Graves, 2016) and confident adaptive decoding (Schuster et al., 2022). Agrawal et al. (2024) propose an entropy-based stopping rule during speculative decoding, adaptively halting draft expansion when confidence is sufficient. He et al. (2025) introduce an uncertainty-guided mechanism for code generation, pausing and reranking when uncertainty is high. Similarly, Wei et al. (2025) leverage adaptive layerwise exits to accelerate decoding without sacrificing accuracy. Li et al. (2024) introduce early stopping in self-consistency for chain of thought reasoning. These approaches share our motivation of minimizing unnecessary compute while preserving output quality.

Pandora’s Box and Optimal Stopping.
Our approach draws inspiration from the *Pandora’s Box problem*, a classic framework in optimal stopping (Weitzman, 1978). Recent advances have expanded this framework into online and learning-theoretic domains Esfandiari et al. (2019); Gergatsouli & Tzamos (2022); Atsidakou et al. (2024), establishing important connections with prophet inequalities and multi-armed bandit formulations (Gatmiry et al., 2024; Xie et al., 2024). While this problem has generated substantial theoretical insights across various domains, its application to LLM inference remains unexplored. Our work brings this perspective to test-time optimization by framing candidate generation as opening costly boxes.

We review other related works in Appendix [B](https://arxiv.org/html/2510.01394v1#A2).

## 2 Preliminaries

### 2.1 Notation

Let $\mathcal{X}$ denote the space of prompts and $\mathcal{Y}$ be the space of responses. A Large Language Model (LLM) $\pi:\mathcal{X}\rightarrow\Delta\mathcal{Y}$ maps a prompt to a distribution over responses, where we let $\Delta\mathcal{Y}$ denote the set of all distributions on $\mathcal{Y}$. A reward model is a function $r:\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$ that maps a prompt and a response to a real-value. Given a prompt $x\in\mathcal{X}$, LLM $\pi$, and reward model $r$, we use $D_{r,\pi(x)}$ to denote the distribution over rewards induced by passing $x$ to $\pi$, sampling $y\sim\pi(x)$, and then computing $r(x,y).$ We will often just use $D$ as shorthand and use $F$ to denote its CDF and $f$ to denote its PDF, omitting dependence on $\pi$, $x$ and $r$ when those are clear from context.

### 2.2 Test-time Steering and Best-of- N N sampling

After the pre-training stage, the focus often shifts from learning general language ability to steering a model’s outputs toward more desirable responses. One way to formalize this is through a reward model $r:\mathcal{X}\times\mathcal{Y}\to\mathbb{R}$, which assigns higher scores to responses $y$ for a given prompt $x$ when they exhibit preferred properties. The objective is then to generate outputs that achieve high reward under $r$ at test time. There are two broad ways to influence the outputs of a pre-trained model:

(i) Fine-tuning. Techniques such as reinforcement learning from human feedback (RLHF) fine-tune the weights of the model so that high-reward responses are more likely (Christiano et al., 2017; Ouyang et al., 2022).

(ii) Test-time steering. Instead of additional training, these methods rely purely on how inference is conducted. Test-time steering treats compute at generation time as the resource to be allocated, biasing outputs toward higher-reward responses by modifying the decoding process (Welleck et al., 2024).

A simple and widely studied test-time approach is Best-of-$N$ sampling (Nakano et al., 2021; Touvron et al., 2023). For a given prompt $x$, we generate $N$ candidate responses $y_{1},\dots,y_{N}\sim\pi(x)$, evaluate each with $r(x,y_{i})$, and select the response with the highest score. Best-of-$N$ has been shown to substantially improve output quality across tasks, both empirically and theoretically, (Wang et al., 2025; Sun et al., 2024; Beirami et al., 2024; Yang et al., 2024), but it can be computationally expensive since it requires $N$ forward passes per prompt, with $N$ fixed in advance. Moreover, in practice, $N$ is typically fixed. However, some prompts may yield strong candidates after only a few samples, while others require more, making a uniform budget potentially wasteful. This motivates the design of adaptive test-time strategies that allocate compute more efficiently across prompts.

### 2.3 Optimal Stopping, Pandora’s Box, and Weitzman’s Algorithm

The Pandora’s Box problem (Weitzman, 1978) is a classical optimal stopping problem: a decision-maker faces $k$ boxes, each box $i\in[k]$ containing a reward drawn from a known distribution $D_{i}$ and requiring an opening cost $c_{i}>0$. The objective is to adaptively decide which boxes to open and when to stop, maximizing the best observed reward minus total costs. Once opened, a box’s reward can be claimed at any time.

This framework maps naturally to LLM generation. For a prompt $x$, an LLM $\pi$ samples responses from $\pi(x)$, with rewards assigned by a deterministic model $r$, inducing a reward distribution $D_{r,\pi(x)}$. Each generation incurs a computational cost $c$ that depends on the prompt, model, and reward function. Thus, generating responses mirrors opening boxes: each sample reveals a reward at cost $c$, and the decision-maker must trade off computation against reward.

A particularly relevant special case is when all boxes share the same distribution $D$ and cost $c$, modeling repeated queries to a single LLM. We focus on this setting throughout, though extensions to multiple LLMs are natural directions for future work.

A fundamental concept in solving this problem is the fair-cap value, the threshold where expected excess reward exactly covers the opening cost.

###### Definition 1 (Fair-cap value) .

Let $D$ be a distribution and $c>0$ be the cost value for each sample. The fair-cap value $\tau\in\mathbb{R}$ associated with $(D,c)$, denoted $\tau(D,c)$, is the number satisfying the equality $\mathbb{E}_{v\sim D}\left[[v-\tau]_{+}\right]=c,$ where $[\cdot]_{+}=\mathop{max}(0,\cdot).$

Weitzman’s celebrated algorithm provides the optimal stopping strategy using fair-cap values when distributions are known. Though Weitzman’s algorithm is defined for an arbitrary collection of not-necessarily-identical distributions in general, we describe its special case for infinitely-many boxes with identical distributions below. This corresponds to our focus on a single LLM which can be queried an unbounded number of times.

###### Definition 2 (Weitzman’s Algorithm for infinitely-many identical boxes) .

Let $D$ be a *known* distribution, $c>0$ be the cost value for each sample, and $\tau:=\tau(D,c)$ be the fair-cap value. The algorithm samples from $D$ until it observes a report exceeding $\tau$. More formally: Letting $v_{1},v_{2},\dots\sim D^{\infty}$ be a countably infinite sequence of i.i.d. rewards, the stopping time of Weitzman’s algorithm is the random variable $T_{W}:=\inf\{n\geq 1:\mathop{max}_{i\leq n}v_{i}\geq\tau\}.$

In practice, reward distributions are effectively unknown. While implicitly encoded in the model weights, they lack compact representation and are only accessible through sampling. The meta-generation problem thus becomes a Pandora’s Box problem with an *unknown* single distribution but known cost value. To evaluate algorithms in the *unknown* distribution setting, we compare against an oracle that knows the true distribution and executes Weitzman’s algorithm optimally.

###### Definition 3 (Additive Sub-optimality Gap) .

Consider distribution $D$ with cost $c$. Let $W$ denote Weitzman’s optimal policy with full knowledge of $D$, achieving net payoff $R_{W}$ (maximum reward minus total costs). For any policy $S$ that learns $D$ only through sampling, with payoff $R_{S}$, the additive sub-optimality gap is
$\mathbb{E}_{D}[R_{W}-R_{S}].$

In general, if the reward distribution is allowed to be picked completely adversarially, then there is no hope for designing a single, minimax optimal stopping policy $S$ whose additive sub-optimality gap is uniformly bounded across all distributions. As a result, we will assume that we have a *known* distribution family $\mathcal{F}$ such that the *unknown* $D\in\mathcal{F}$.

###### Definition 1 (Fair-cap value) .

###### Definition 2 (Weitzman’s Algorithm for infinitely-many identical boxes) .

###### Definition 3 (Additive Sub-optimality Gap) .

## 3 Pandora’s Box with Unknown Reward Distributions

When the distribution $D$ is unknown, the fair-cap value $\tau$ must be learned from data. Our main algorithm, *UCB Pandora’s Box*, adapts the upper confidence bound (UCB) principle from multi-armed-bandit theory (Auer et al., 2002). The algorithm iteratively samples rewards and uses them along with the family $\mathcal{F}$ to construct an upper confidence bound $\tau^{+}$ on the fair-cap value $\tau$. It stops once the maximum observed reward $M$ exceeds the UCB on $\tau$. Pseudo-code is given in Algorithm [2](https://arxiv.org/html/2510.01394v1#alg2).

The specific update for the UCB $\tau^{+}$ depends on $\mathcal{F}$ and the method for constructing confidence bounds for $\tau$. In particular, $\mathcal{F}$ must be “nice” enough to admit an *anytime-valid confidence sequence* for $\tau$. We define this rigorously and provide one such example in Section [3.1](https://arxiv.org/html/2510.01394v1#S3.SS1). In practice, the confidence parameter is a hyperparameter that influences the exploration-exploitation balance.

### 3.1 Main Theoretical Result

As previously highlighted, UCB Pandora’s Box requires an anytime-valid upper confidence bound on the fair-cap value $\tau$. Definition [4](https://arxiv.org/html/2510.01394v1#Thmtheorem4) makes this precise.

###### Definition 4 (Anytime Valid Upper Confidence Bound on the Fair-cap Value) .

Let $\mathcal{F}$ be a family of distributions and $c>0$ be the cost value for each sample. A function
$\tau^{+}:\mathbb{N}\times(0,1)\times\mathbb{R}^{\star}\rightarrow\mathbb{R}$
is an *anytime valid upper confidence bound* of the fair-cap value with *width function* $\sigma:\mathbb{N}\times(0,1)\times\mathbb{R}$
for $\mathcal{F}$ if for every $\delta\in(0,1)$ and $D\in\mathcal{F}$, we have

$$ $\mathbb{P}_{v_{1:\infty}\sim D^{\infty}}\left[\forall n\in\mathbb{N}:\tau\in[\tau^{+}_{\delta}(n,v_{1:n})-\sigma_{\delta,\tau}(n),\tau^{+}_{\delta}(n,v_{1:n})]\right]\geq 1-\delta.$ $$

where $\tau=\tau(D,c)$ is the fair-cap value.

If $\mathcal{F}$ is a parametric family of distributions, the fair-cap value often admits a simple monotonic dependence on the distribution’s parameters. This observation allows us to obtain an upper confidence bound on the fair-cap value by applying the same monotonic transformation to an upper confidence bound on the parameters themselves. For example, in Section [6](https://arxiv.org/html/2510.01394v1#Thmtheorem6) we show that when $\mathcal{F}$ is the class of Exponential distributions, an upper confidence bound on the mean directly yields an upper confidence bound on the fair-cap value. More generally, constructing a confidence sequence for $\tau$ can be reduced to two steps: (1) build a confidence sequence for the distribution’s parameters, and (2) propagate it through the monotonic mapping to obtain a confidence sequence for the fair-cap value.

We now present Theorem [5](https://arxiv.org/html/2510.01394v1#Thmtheorem5), our main theoretical result of this section, which upper bounds the additive sub-optimality gap of UCB Pandora’s Box algorithm.

###### Theorem 5 (Upper bound on Additive Sub-optimality) .

Let $\mathcal{F}$ be a family of distributions and $c>0$ be the cost value for each sample. Let $\tau^{+}_{\delta}(n,v_{1:n})$ be an anytime upper confidence bound with
deterministic width $\sigma_{\delta,\tau}(n)$ for $\mathcal{F}$ according to Definition [4](https://arxiv.org/html/2510.01394v1#Thmtheorem4).
i.e., for every distribution $D\in\mathcal{F}$, on the event $E_{\delta}:=\Big\{\forall n\geq 1:\ \tau\leq\tau^{+}_{\delta}(n,v_{1:n})\leq\tau+\sigma_{\delta,\tau}(n)\Big\}$ we have that $\mathbb{P}_{v_{1},v_{2},\dots\sim D}(E_{\delta})\geq 1-\delta.$
Consider the two stopping policies:

- •
Weitzman policy: $T_{W}:=\inf\{n\geq 1:\mathop{max}_{i\leq n}v_{i}\geq\tau\}$ w/
$R_{W}:=\mathop{max}_{i\leq T_{W}}v_{i}-c\,T_{W}$.
- •
UCB policy: $T_{U}:=\inf\{n\geq 1:\mathop{max}_{i\leq n}v_{i}\geq\tau^{+}_{\delta}(n,v_{1:n})\}$ w/
$R_{U}:=\mathop{max}_{i\leq T_{U}}v_{i}-c\,T_{U}$.

Then for every $D\in\mathcal{F}$ and $\delta\in(0,1)$, we have that

$$ $\mathbb{E}_{D}\left[(R_{W}-R_{U})\mathbf{1}_{E_{\delta}}\right]\leq\sum_{n=1}^{\infty}\sigma_{\delta,\tau}(n)\,(1-F_{D}(\tau))\Big(F_{D}^{\,n-1}\!\big(\tau+\sigma_{\delta,\tau}(n)\big)-F_{D}^{\,n-1}(\tau)\Big),$ $$

where $F_{D}$ is the *CDF* of $D$ and $\tau=\tau(D,c)$ is the fair-cap value of $D.$

The proof of Theorem [5](https://arxiv.org/html/2510.01394v1#Thmtheorem5) can be found in Appendix [E](https://arxiv.org/html/2510.01394v1#A5).

###### Definition 4 (Anytime Valid Upper Confidence Bound on the Fair-cap Value) .

###### Theorem 5 (Upper bound on Additive Sub-optimality) .

### 3.2 Example: Exponential distribution with unknown parameter λ \lambda

The upper bound in Theorem [5](https://arxiv.org/html/2510.01394v1#Thmtheorem5) is abstract and instance-dependent. To obtain a more concrete result, we instantiate it with the family $\mathcal{F}$ of Exponential distributions parametrized by $\lambda\in(0,1/(ce)]$.

For $\lambda$ in this range, let $D_{\lambda}\in\mathcal{F}$ denote the Exponential distribution with rate $\lambda$, with CDF $F_{\lambda}(x)=1-e^{-\lambda x}$ and PDF $f_{\lambda}(x)=\lambda e^{-\lambda x}$. The restriction $\frac{1}{\lambda}\geq ec$ ensures that the sampling cost $c$ is at most $1/e$ of the expected reward. Indeed, if $c>1/\lambda$, not even a single sample would be worthwhile.

Theorem [6](https://arxiv.org/html/2510.01394v1#Thmtheorem6) provides an any-time valid UCB on the fair-cap value for distributions in $\mathcal{F}.$

###### Theorem 6 (Anytime-valid Upper Confidence Bound for Exponential Fair-cap value) .

Let $c>0$ be the sampling cost and $\mathcal{F}$ be the class of Exponential distributions with parameter $\lambda\in(0,\frac{1}{c\cdot e}].$ Then, the function
$\tau^{+}_{\delta}(n,v_{1:n})=\widehat{\mu}_{n}(1+r_{\delta}(n))\log\left(\frac{\widehat{\mu}_{n}(1+r_{\delta}(n))}{c}\right)$
with width function $\sigma_{\delta,\tau}(n)=16\tau\cdot r_{\delta}(n)$
is an *anytime valid upper confidence bound* on the fair-cap value, where $\widehat{\mu}_{n}=\frac{1}{n}\sum_{i=1}^{n}v_{i},$
and
$r_{\delta}(n):=\mathop{min}\Biggl\{\frac{1}{2},\sqrt{\frac{6}{n}\log\left(\frac{2n(n+1)}{\delta}\right)}\Biggl\}.$

The proof of Theorem [6](https://arxiv.org/html/2510.01394v1#Thmtheorem6) (Appendix [E.2](https://arxiv.org/html/2510.01394v1#A5.SS2)) proceeds by expressing the fair-cap value of an Exponential distribution as a monotonic function of its mean, constructing an anytime-valid UCB for the mean, and then transferring this bound to the fair-cap value.
With Theorem [6](https://arxiv.org/html/2510.01394v1#Thmtheorem6) in hand, we can now explicitly compute the right-hand side of the expected sub-optimality gap in Theorem [5](https://arxiv.org/html/2510.01394v1#Thmtheorem5).

###### Corollary 7 (Sub-optimality gap upper bound for Exponential distribution) .

Let $c>0$ be the sampling cost and $\mathcal{F}$ be the class of Exponential distribution with parameter $\lambda\in(0,\frac{1}{c\cdot e}].$ Then, for every $\delta\in(0,1)$ and $D_{\lambda}\in\mathcal{F}$ we have that

$$ $\sum_{n=1}^{\infty}\sigma_{\delta,\tau}(n)\cdot(1-F_{\lambda}(\tau))\cdot(F_{\lambda}^{n-1}(\tau+\sigma_{\delta,\tau}(n))-F_{\lambda}^{n-1}(\tau))\leq\widetilde{O}_{\delta}\left(\frac{1}{\lambda}\right),$ $$

where $\sigma_{\delta,\tau}(n)$ is defined as in Theorem [6](https://arxiv.org/html/2510.01394v1#Thmtheorem6), $\tau=\tau(D_{\lambda},c)$ is the fair-cap value, and $\widetilde{O}_{\delta}(\cdot)$ hides polylog terms of $\frac{1}{\delta}.$ As a result, we have that for every $\delta\in(0,1)$ and $D_{\lambda}\in\mathcal{F}$ the additive sub-optimality gap for *UCB* Pandora’s Algorithm satisfies
$\mathbb{E}_{D_{\lambda}}\left[(R_{W}-R_{U})\mathbf{1}_{E_{\delta}}\right]\leq\widetilde{O}_{\delta}\left(\frac{1}{\lambda}\right).$

At a high level, Corollary [7](https://arxiv.org/html/2510.01394v1#Thmtheorem7) (proved in Appendix [E.2](https://arxiv.org/html/2510.01394v1#A5.SS2)) shows that under event $E_{\delta}$ (see Theorem [5](https://arxiv.org/html/2510.01394v1#Thmtheorem5)), the expected sub-optimality gap of UCB Pandora’s Box is bounded by the mean $1/\lambda$ (up to logarithmic factors in $\delta$). In Section [4](https://arxiv.org/html/2510.01394v1#S4), we leverage these results to develop prompt-adaptive inference-time optimization methods.

###### Theorem 6 (Anytime-valid Upper Confidence Bound for Exponential Fair-cap value) .

###### Corollary 7 (Sub-optimality gap upper bound for Exponential distribution) .

## 4 Applying UCB Pandora’s Box to Inference-time Optimization

Building on the connection between test-time steering and the Pandora’s Box problem established in Section [2.3](https://arxiv.org/html/2510.01394v1#S2.SS3), we now cast inference-time optimization as an instance of the Pandora’s Box problem. Each generation from the base LLM can be viewed as opening a costly box whose payoff is the reward assigned by $r$. The challenge is to decide when to stop sampling: too early risks missing high-reward outputs, while too late wastes computation. In what follows, we develop adaptive stopping rules that navigate this tradeoff without prior knowledge of the underlying reward distribution.

### 4.1 The Reward Scaling Challenge

A key subtlety in framing inference-time optimization as a Pandora’s Box problem is deciding what makes a response “high quality.” Using a fixed reward threshold is inadequate because reward scales vary dramatically across prompts. For example, Figure [4](https://arxiv.org/html/2510.01394v1#A4.F4) in Appendix [D](https://arxiv.org/html/2510.01394v1#A4) shows large variance in median rewards across 100 prompts, even when evaluated with the same model.

To enable cost-shared semantics across prompts with different reward scales, we first select a gold-standard percentile $\alpha$ of the reward distribution as our quality benchmark. This choice naturally adapts to each prompt’s reward scale while maintaining consistent quality standards. Throughout our work, we set $\alpha=0.99$ to compete with Best-of-$N$ sampling (where typically $\alpha\approx 1-\frac{1}{N}$), though practitioners may adjust this parameter based on quality requirements. We formalize this benchmark below.

###### Definition 8 (Benchmark Reward) .

The *benchmark reward* with respect to the *LM*-reward model pair $(\pi,r)$ is the $\alpha$-percentile of the reward distribution $D_{r,\pi(x)}$, denoted $D^{\alpha}_{r,\pi(x)}$.

Note that larger $\alpha$’s result in a more stringent benchmark. By fixing a benchmark reward, we can now define the acceptance rate of a response $y$ in terms of how “close” its reward $v$ is to the benchmark. To do this, we adopt the Bradley-Terry model which models the probability of preferring response $A$ over $B$ as $\frac{e^{r_{A}}}{e^{r_{A}}+e^{r_{B}}}$, where $r_{A}$ and $r_{B}$ are their rewards (Bradley & Terry, 1952). Definition [9](https://arxiv.org/html/2510.01394v1#Thmtheorem9) makes this precise in terms of an arbitrary reward threshold $\kappa$, although we will always take $\kappa=D^{\alpha}_{r,\pi(x)}$ to be the reward benchmark in this work.

###### Definition 9 (Acceptance Rate) .

The *acceptance rate* of a response $y$ with reward $v_{y}=r(x,y)$ with respect to threshold $\kappa$ is defined as $\operatorname{AR}_{\kappa}(v)=\mathop{min}\left\{2\cdot\frac{e^{v}}{e^{v}+e^{\kappa}},\,1\right\}.$

This transformation maps rewards into $[0,1]$. The Bradley–Terry term $\tfrac{e^{v}}{e^{v}+e^{\kappa}}$ represents the probability of preferring a response with reward $v$ over one with reward $\kappa$. Intuitively, the acceptance rate approximates the probability that an end-user accepts the response: below-threshold responses are accepted in proportion to their quality relative to $\kappa$, while at- or above-threshold responses are accepted with certainty. By setting $\kappa=D^{\alpha}_{r,\pi(x)}$, we make acceptance rates prompt-, model-, and reward-dependent, which allows us to compare them across prompts with different reward scales. However, as the true reward distribution is unknown, $D^{\alpha}_{r,\pi(x)}$ is unknown. Hence, we will also estimate $D^{\alpha}_{r,\pi(x)}$ from samples, which empirically proves sufficient for accurately computing the true acceptance rate.

Lastly, we define a utility function from the acceptance rate by assigning a maximum achievable utility to an accepted response.

###### Definition 10 (Utility Function) .

For an acceptance threshold $\kappa$, the utility function $u_{\kappa}:\mathbb{R}\rightarrow[0,B]$ maps rewards to *utilities* via $u_{\kappa}(v)=B\cdot\operatorname{AR}_{\kappa}(v),$
where $B>0$ is the maximum achievable utility.

Now, the reward for responses below the threshold map to utilities in $[0,B)$, while responses with reward larger than $\kappa$ map exactly to $B$. Since $\operatorname{AR}_{\kappa}(v)$ is the probability that a response with reward $v$ is accepted and $B$ is the utility of an accepted response, we can view $u_{\kappa}(v)$ as the *expected* utility of a response with reward $v$ (assuming rejected responses get no utility). Pushing the reward distribution $D_{r,\pi(x)}$ through $u_{\kappa}$ yields the utility distribution $U_{\kappa,r,\pi(x)}:=u_{\kappa}(D_{r,\pi(x)})$ supported on $[0,B]$. Setting cost $c\in[0,B]$ then allows direct comparison of generation costs with achievable utilities.

###### Remark 11 .

We note that it is without loss of generality to fix $B=1$ and take $c\in[0,1].$ This is because the fair-cap value of a utility distribution $U$ is only a function of the cost-utility ratio $c/B.$

###### Definition 8 (Benchmark Reward) .

###### Definition 9 (Acceptance Rate) .

###### Definition 10 (Utility Function) .

###### Remark 11 .

### 4.2 The Adaptive Algorithm

We are now ready to adapt the UCB Pandora’s Box Algorithm from Section [3.1](https://arxiv.org/html/2510.01394v1#S3.SS1) to the Best-of-$N$ inference-time optimization setting. Given a prompt $x\in\mathcal{X}$, LLM $\pi$, and reward model $r$, our algorithm sequentially generates responses and adaptively decides when to stop. After collecting a minimum number of samples, it estimates the reward distribution’s tail. To do so, we exponentiate the rewards and fit a shifted exponential distribution to the right-tail values (those above the median). From this fit, we construct both upper and lower confidence bounds (UCB/LCB) on the scale of the exponential distribution. The LCB on the scale is then used to derive a conservative estimate of the $\alpha$ percentile of the exponentiated rewards, while the UCB is used to bound the tail distribution itself. This combination yields an upper confidence bound on the fair-cap value of the true utility distribution. If the utility of the best reward observed so far exceeds this fair cap, the algorithm terminates; otherwise, it continues sampling. Pseudocode is given in Algorithm [1](https://arxiv.org/html/2510.01394v1#alg1).

Figure: Algorithm 1 Adaptive Best-of-N Sampling via UCB Pandora’s Box

Implementation Efficiency.
The algorithm can be implemented with negligible overhead relative to generation costs. A priority queue maintains the median and tail statistics with $O(\log n)$ updates and $O(1)$ queries, while streaming updates eliminate redundant computation.
Key distributional operations are closed-form. For example, the $\alpha$-percentile of the shifted exponential distribution is computed in $O(1)$ time from an analytical formula.
Fair-cap computation requires solving $\mathbb{E}[\mathop{max}(v-\tau,0)]=c$ for the threshold $\tau$. We approximate the expectation via a Riemann sum with $\sim$5000 intervals. Empirically, this achieves under 1% relative error. The subroutine executes over 100 times per second(^2^22Measured on a single core of an AMD EPYC 7513 32-Core Processor.), enabling real-time adaptation during generation.
In practice, the overhead of adaptive stopping is negligible as LLM and reward model forward passes dominate runtime.

### 4.3 Target Acceptance Rate Variant

Algorithm [1](https://arxiv.org/html/2510.01394v1#alg1) requires specifying the utility $B$ and cost $c$, which may be difficult to estimate in practice. To address this, we provide an alternative formulation that instead targets a desired acceptance rate.
Rather than computing the fair-cap value from utility–cost tradeoffs, this variant sets a target acceptance rate $\tau_{\text{target}}\in[0,1]$ that encodes the desired quality level relative to the acceptance threshold. For example, $\tau_{\text{target}}=0.9$ seeks responses nearly as good as benchmark ones, while $\tau_{\text{target}}=1$ requires fully benchmark responses.
The algorithm proceeds identically to Algorithm [1](https://arxiv.org/html/2510.01394v1#alg1) except that the stopping condition is now fixed: it halts when $\operatorname{AR}_{\widehat{D}^{\alpha}_{r,\pi(x)}}(M)\geq\tau_{\text{target}}$(^3^33In this variant, we estimate $\widehat{D}^{\alpha}_{r,\pi}(x)$ using $\widehat{D}^{\text{ucb}}$. Otherwise, the algorithm tends to stop prematurely by overestimating the acceptance rate of the maximum sample.). This formulation is useful in settings where quality requirements are clear but utilities are hard to quantify, for instance, when “good enough” responses are well-defined but the value of marginal improvements is ambiguous.

## 5 Experimental Results

### 5.1 Experimental Setup

We evaluate our adaptive Best-of-$N$ algorithm on 100 prompts from AlpacaFarm (Dubois et al., 2023) and 100 from HH-RLHF (Bai et al., 2022). We use four LLM (Google-Gemma-2 (9B), Meta-Llama-3.1 (8B), Mistral-Instruct-v0.3 (7B), Qwen-2.5 (7B)) and two reward models (FsfairX-LLaMA3-RM-v0.1, RM-Mistral-7B; Dong et al., 2023; Xiong et al., 2024). This yields 1,600 generation profiles ($2$ datasets $\times$ $100$ prompts $\times$ $4$ LLMs $\times$ $2$ reward models). For each profile, we generate 960 responses, compute rewards, and randomize response–reward orderings 100 times to remove ordering effects. We always fix the max utility $B=1$, and only vary the cost $c.$

We benchmark against non-adaptive Best-of-$N$ across three tasks: (1) *profit optimization*, comparing utility–cost tradeoffs; (2) *win rate analysis*, under fixed compute budgets; and (3) *efficiency gains*, measuring compute savings at target quality levels. More experimental results are in Appendix [F](https://arxiv.org/html/2510.01394v1#A6).

### 5.2 Experiment 1: Profit Optimization

We evaluate how well our adaptive algorithm maximizes profit (utility minus total cost) relative to the best non-adaptive strategy. We consider four cost-to-utility ratios: ${0.002,0.001,0.0004,0.0002}$.
Figure [1](https://arxiv.org/html/2510.01394v1#S5.F1) reports results for Mistral-Instruct-v0.3 (7B) with the RM-Mistral-7B reward model. The adaptive algorithm (red) either closely approximates or outperforms the profit envelope defined by the best non-adaptive strategies (blue/green), automatically achieving this performance without knowing the optimal $N$ in advance. Across all 1,600 generation profiles, the adaptive method outperforms the generator-dependent best non-adaptive algorithm in nearly all cases, demonstrating clear superiority (Figure [5](https://arxiv.org/html/2510.01394v1#A6.F5)).

Figure: Figure 1: Our algorithm (red) matches optimal non-adaptive performance across varying cost ratios.
Refer to caption: cost_analysis.png

### 5.3 Experiment 2: Win Rate Under Fixed Budget

We compare our adaptive algorithm with non-adaptive Best-of-$N$ under equal computation budgets. For each prompt $x$, LLM $\pi$, and cost $c\in[10^{-5},10^{-3}]$, we: (1) run the adaptive algorithm on 100 random orderings and record the average sample count $\overline{n}_{\pi,x,c}$, (2) run non-adaptive Best-of-$N$ with $N=\overline{n}_{\pi,x,c}$ on the same orderings, and (3) compare maximum rewards, awarding half credit for ties.
Figure [2](https://arxiv.org/html/2510.01394v1#S5.F2) shows the results. The adaptive algorithm consistently outperforms non-adaptive Best-of-$N$, with win rates exceeding 54% across most cost settings. Gains are largest when costs are low (permitting more samples) or budgets are higher, where adaptive stopping better exploits variation across prompts. Figure [6](https://arxiv.org/html/2510.01394v1#A6.F6) confirms these results across different datasets and reward models.

Figure: Figure 2: Win rate of the adaptive algorithm compared to non-adaptive Best-of-$N$. Adaptive stopping leverages computation more effectively, particularly at lower costs.
Refer to caption: win_rate.png

### 5.4 Experiment 3: Efficiency at Target Quality Levels

We next evaluate the target acceptance rate variant, which allows users to directly specify a desired quality level. For target rates $\tau\in[0.60,1]$ and each configuration (LLM $\pi$, prompt $x$, target $\tau$), we: (1) measure the adaptive algorithm’s average acceptance rate $\overline{a}_{\pi,x,\tau}$ and sample count $\overline{n}_{\pi,x,\tau}$; (2) identify the non-adaptive $N^{\star}$ that achieves the same $\overline{a}_{\pi,x,\tau}$; and (3) compute the efficiency gain

$$ $\text{SaveRatio}_{\pi,x,\tau}=\frac{N^{\star}-\overline{n}_{\pi,x,\tau}}{N^{\star}}.$ $$

Figure [3](https://arxiv.org/html/2510.01394v1#S5.F3) shows that the adaptive algorithm both tracks the target quality (right) and yields substantial savings in sample counts (left). For acceptance rates $0.75+$, it consistently reduces sampling by $15$–$35\%$ relative to non-adaptive methods. Savings increase monotonically with stricter targets, from $\sim$15% up to $\sim$35%, reflecting more effective use of learned tail information at higher quality levels.

Figure: Figure 3: Adaptive algorithm achieves specified target acceptance rates while saving 15–35% of samples compared to non-adaptive Best-of-$N$.
Refer to caption: acceptance_rate.png

## 6 Discussion

We highlight several directions for future investigation. (1) Multi-model inference: Although we consider a single LLM in this work, the Pandora’s Box framework extends naturally to ensembles of models, where each model corresponds to a box type with its own cost–quality profile. An open question is whether adaptive algorithms can automatically route queries across models, reducing the need for hand-designed cascades (Yue et al., 2023). (2) Tree search and reasoning: Approaches such as tree-of-thought (Yao et al., 2023) and Monte Carlo tree search (Feng et al., 2023) also involve sequential explore–exploit trade-offs at each decision point. Optimal stopping may help formalize when to expand or backtrack in such settings, potentially improving efficiency relative to existing heuristics.

## References

- Achiam et al. (2023)
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al.
Gpt-4 technical report.
*arXiv preprint arXiv:2303.08774*, 2023.
- Agrawal et al. (2024)
Sudhanshu Agrawal, Wonseok Jeon, and Mingu Lee.
Adaedl: Early draft stopping for speculative decoding of large language models via an entropy-based lower bound on token acceptance probability.
*arXiv preprint arXiv:2410.18351*, 2024.
- Atsidakou et al. (2024)
Alexia Atsidakou, Constantine Caramanis, Evangelia Gergatsouli, Orestis Papadigenopoulos, and Christos Tzamos.
Contextual pandora’s box.
*Proceedings of the AAAI Conference on Artificial Intelligence*, 38(10):10944–10952, Mar. 2024.
doi: 10.1609/aaai.v38i10.28969.
URL [https://ojs.aaai.org/index.php/AAAI/article/view/28969](https://ojs.aaai.org/index.php/AAAI/article/view/28969).
- Auer et al. (2002)
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.
Finite-time analysis of the multiarmed bandit problem.
*Machine learning*, 47(2):235–256, 2002.
- Bai et al. (2022)
Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, Nicholas Joseph, Saurav Kadavath, Jackson Kernion, Tom Conerly, Sheer El Showk, Nelson Elhage, Zac Hatfield-Dodds, Danny Hernandez, Tristan Hume, Scott Johnston, Shauna Kravec, Liane Lovitt, Neel Nanda, Catherine Olsson, Dario Amodei, Tom B. Brown, Jack Clark, Sam McCandlish, Chris Olah, Benjamin Mann, and Jared Kaplan.
Training a helpful and harmless assistant with reinforcement learning from human feedback.
*CoRR*, abs/2204.05862, 2022.
doi: 10.48550/ARXIV.2204.05862.
URL [https://doi.org/10.48550/arXiv.2204.05862](https://doi.org/10.48550/arXiv.2204.05862).
- Beirami et al. (2024)
Ahmad Beirami, Alekh Agarwal, Jonathan Berant, Alexander D’Amour, Jacob Eisenstein, Chirag Nagpal, and Ananda Theertha Suresh.
Theoretical guarantees on the best-of-n alignment policy.
*arXiv preprint arXiv:2401.01879*, 2024.
- Bhatt et al. (2021)
Sujay Bhatt, Ping Li, and Gennady Samorodnitsky.
Extreme Bandits using Robust Statistics, September 2021.
URL [http://arxiv.org/abs/2109.04433](http://arxiv.org/abs/2109.04433).
arXiv:2109.04433 [stat].
- Bradley & Terry (1952)
Ralph Allan Bradley and Milton E Terry.
Rank analysis of incomplete block designs: I. the method of paired comparisons.
*Biometrika*, 39(3/4):324–345, 1952.
- Chen et al. (2024)
Boyuan Chen, Mingzhi Zhu, Brendan Dolan-Gavitt, Muhammad Shafique, and Siddharth Garg.
Model cascading for code: A cascaded black-box multi-model framework for cost-efficient code completion with self-testing.
*arXiv preprint arXiv:2405.15842*, 2024.
- Chen et al. (2023)
Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, Jean-Baptiste Lespiau, Laurent Sifre, and John Jumper.
Accelerating large language model decoding with speculative sampling.
*arXiv preprint arXiv:2302.01318*, 2023.
- Christiano et al. (2017)
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei.
Deep reinforcement learning from human preferences.
*Advances in neural information processing systems*, 30, 2017.
- (12)
Vincent A Cicirello and Stephen F Smith.
The Max K-Armed Bandit: A New Model of Exploration Applied to Search Heuristic Selection.
- Dong et al. (2023)
Hanze Dong, Wei Xiong, Deepanshu Goyal, Rui Pan, Shizhe Diao, Jipeng Zhang, Kashun Shum, and Tong Zhang.
Raft: Reward ranked finetuning for generative foundation model alignment.
*arXiv preprint arXiv:2304.06767*, 2023.
- Dubois et al. (2023)
Yann Dubois, Xuechen Li, Rohan Taori, Tianyi Zhang, Ishaan Gulrajani, Jimmy Ba, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto.
Alpacafarm: A simulation framework for methods that learn from human feedback, 2023.
- Esfandiari et al. (2019)
Hossein Esfandiari, Mohammad Taghi Haji Aghayi, Brendan Lucier, and Michael Mitzenmacher.
Online pandora’s boxes and bandits.
In *Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence*, AAAI’19/IAAI’19/EAAI’19. AAAI Press, 2019.
ISBN 978-1-57735-809-1.
doi: 10.1609/aaai.v33i01.33011885.
URL [https://doi.org/10.1609/aaai.v33i01.33011885](https://doi.org/10.1609/aaai.v33i01.33011885).
- Feng et al. (2023)
Xidong Feng, Ziyu Wan, Muning Wen, Stephen Marcus McAleer, Ying Wen, Weinan Zhang, and Jun Wang.
Alphazero-like tree-search can guide large language model decoding and training.
*arXiv preprint arXiv:2309.17179*, 2023.
- Gatmiry et al. (2024)
Khashayar Gatmiry, Thomas Kesselheim, Sahil Singla, and Yifan Wang.
Bandit algorithms for prophet inequality and pandora’s box.
In *SODA*, pp. 462–500, 2024.
URL [https://doi.org/10.1137/1.9781611977912.18](https://doi.org/10.1137/1.9781611977912.18).
- Gergatsouli & Tzamos (2022)
Evangelia Gergatsouli and Christos Tzamos.
Online learning for min sum set cover and pandora’s box.
In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), *Proceedings of the 39th International Conference on Machine Learning*, volume 162 of *Proceedings of Machine Learning Research*, pp. 7382–7403. PMLR, 17–23 Jul 2022.
URL [https://proceedings.mlr.press/v162/gergatsouli22a.html](https://proceedings.mlr.press/v162/gergatsouli22a.html).
- Graves (2016)
Alex Graves.
Adaptive computation time for recurrent neural networks.
*arXiv preprint arXiv:1603.08983*, 2016.
- He et al. (2025)
Kaifeng He, Mingwei Liu, Chong Wang, Zike Li, Yanlin Wang, Xin Peng, and Zibin Zheng.
Adadec: Uncertainty-guided adaptive decoding for llm-based code generation.
*arXiv preprint arXiv:2506.08980*, 2025.
- Hoffmann et al. (2022)
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al.
Training compute-optimal large language models.
*arXiv preprint arXiv:2203.15556*, 2022.
- Huang et al. (2025)
Chengsong Huang, Langlin Huang, Jixuan Leng, Jiacheng Liu, and Jiaxin Huang.
Efficient Test-Time Scaling via Self-Calibration, February 2025.
URL [http://arxiv.org/abs/2503.00031](http://arxiv.org/abs/2503.00031).
arXiv:2503.00031 [cs].
- Jain et al. (2023)
Siddhartha Jain, Xiaofei Ma, Anoop Deoras, and Bing Xiang.
Lightweight reranking for language model generations.
*arXiv preprint arXiv:2307.06857*, 2023.
- Jin et al. (2025)
Yunho Jin, Gu-Yeon Wei, and David Brooks.
The energy cost of reasoning: Analyzing energy usage in llms with test-time compute.
*arXiv preprint arXiv:2505.14733*, 2025.
- Leviathan et al. (2023)
Yaniv Leviathan, Matan Kalman, and Yossi Matias.
Fast inference from transformers via speculative decoding.
In *International Conference on Machine Learning*, pp. 19274–19286. PMLR, 2023.
- Li et al. (2024)
Yiwei Li, Peiwen Yuan, Shaoxiong Feng, Boyuan Pan, Xinglin Wang, Bin Sun, Heda Wang, and Kan Li.
Escape sky-high cost: Early-stopping self-consistency for multi-step reasoning.
*arXiv preprint arXiv:2401.10480*, 2024.
- Manvi et al. (2024)
Rohin Manvi, Anikait Singh, and Stefano Ermon.
Adaptive Inference-Time Compute: LLMs Can Predict if They Can Do Better, Even Mid-Generation, October 2024.
URL [http://arxiv.org/abs/2410.02725](http://arxiv.org/abs/2410.02725).
arXiv:2410.02725 [cs].
- Mohammadshahi et al. (2024)
Alireza Mohammadshahi, Arshad Rafiq Shaikh, and Majid Yazdani.
Routoo: Learning to route to large language models effectively.
*arXiv preprint arXiv:2401.13979*, 2024.
- Nakano et al. (2021)
Reiichiro Nakano, Jacob Hilton, Suchir Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christopher Hesse, Shantanu Jain, Vineet Kosaraju, William Saunders, et al.
Webgpt: Browser-assisted question-answering with human feedback.
*arXiv preprint arXiv:2112.09332*, 2021.
- Ouyang et al. (2022)
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al.
Training language models to follow instructions with human feedback.
*Advances in neural information processing systems*, 35:27730–27744, 2022.
- Schuster et al. (2022)
Tal Schuster, Adam Fisch, Jai Gupta, Mostafa Dehghani, Dara Bahri, Vinh Tran, Yi Tay, and Donald Metzler.
Confident adaptive language modeling.
*Advances in Neural Information Processing Systems*, 35:17456–17472, 2022.
- Snell et al. (2025)
Charlie Victor Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar.
Scaling llm test-time compute optimally can be more effective than scaling parameters for reasoning.
In *The Thirteenth International Conference on Learning Representations*, 2025.
- (33)
Matthew J Streeter and Stephen F Smith.
An Asymptotically Optimal Algorithm for the Max k-Armed Bandit Problem.
- Sun et al. (2024)
Hanshi Sun, Momin Haider, Ruiqi Zhang, Huitao Yang, Jiahao Qiu, Ming Yin, Mengdi Wang, Peter Bartlett, and Andrea Zanette.
Fast Best-of-N Decoding via Speculative Rejection, October 2024.
URL [http://arxiv.org/abs/2410.20290](http://arxiv.org/abs/2410.20290).
arXiv:2410.20290 [cs].
- Touvron et al. (2023)
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al.
Llama 2: Open foundation and fine-tuned chat models.
*arXiv preprint arXiv:2307.09288*, 2023.
- Wang et al. (2022)
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou.
Self-consistency improves chain of thought reasoning in language models.
*arXiv preprint arXiv:2203.11171*, 2022.
- Wang et al. (2025)
Yiming Wang, Pei Zhang, Siyuan Huang, Baosong Yang, Zhuosheng Zhang, Fei Huang, and Rui Wang.
Sampling-Efficient Test-Time Scaling: Self-Estimating the Best-of-N Sampling in Early Decoding, March 2025.
URL [http://arxiv.org/abs/2503.01422](http://arxiv.org/abs/2503.01422).
arXiv:2503.01422 [cs].
- Wei et al. (2022)
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al.
Chain-of-thought prompting elicits reasoning in large language models.
*Advances in neural information processing systems*, 35:24824–24837, 2022.
- Wei et al. (2025)
Zhepei Wei, Wei-Lin Chen, Xinyu Zhu, and Yu Meng.
Adadecode: Accelerating llm decoding with adaptive layer parallelism.
*arXiv preprint arXiv:2506.03700*, 2025.
- Weitzman (1978)
Martin Weitzman.
*Optimal search for the best alternative*, volume 78.
Department of Energy, 1978.
- Welleck et al. (2024)
Sean Welleck, Amanda Bertsch, Matthew Finlayson, Hailey Schoelkopf, Alex Xie, Graham Neubig, Ilia Kulikov, and Zaid Harchaoui.
From decoding to meta-generation: Inference-time algorithms for large language models.
*Transactions on Machine Learning Research*, October 2024.
URL [https://arxiv.org/abs/2406.16838](https://arxiv.org/abs/2406.16838).
- Xie et al. (2024)
Qian Xie, Raul Astudillo, Peter I. Frazier, Ziv Scully, and Alexander Terenin.
Cost-aware bayesian optimization via the pandora’s box gittins index.
In *The Thirty-eighth Annual Conference on Neural Information Processing Systems*, 2024.
URL [https://openreview.net/forum?id=Ouc1F0Sfb7](https://openreview.net/forum?id=Ouc1F0Sfb7).
- Xiong et al. (2024)
Wei Xiong, Hanze Dong, Chenlu Ye, Ziqi Wang, Han Zhong, Heng Ji, Nan Jiang, and Tong Zhang.
Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint, 2024.
- Yang et al. (2024)
Joy Qiping Yang, Salman Salamatian, Ziteng Sun, Ananda Theertha Suresh, and Ahmad Beirami.
Asymptotics of language model alignment.
In *2024 IEEE International Symposium on Information Theory (ISIT)*, pp. 2027–2032. IEEE, 2024.
- Yao et al. (2023)
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan.
Tree of thoughts: Deliberate problem solving with large language models.
*Advances in neural information processing systems*, 36:11809–11822, 2023.
- Yue et al. (2023)
Murong Yue, Jie Zhao, Min Zhang, Liang Du, and Ziyu Yao.
Large language model cascades with mixture of thoughts representations for cost-efficient reasoning.
*arXiv preprint arXiv:2310.03094*, 2023.

## Appendix A Disclosure of LLM Usage

LLMs were used to aid and polish the writing throughout the paper. In addition, LLMs were used for retrieval and discovery to help write the Related Works section.

## Appendix B Other Related Works

Extreme Bandits.
Another related line of work is the *extreme bandit problem*, which optimizes the maximum observed reward rather than cumulative reward (Streeter & Smith,; Cicirello & Smith,; Bhatt et al., 2021). This is closely aligned with best-of-$N$ sampling, where one selects the highest-quality output among multiple candidates. However, most extreme bandit formulations assume repeated rounds of play, while inference requires efficient decision-making in a single prompt. Our framework adapts these insights to one-shot inference with explicit cost–quality tradeoffs.

Cascading, Routing, and Hybrid Strategies.
Beyond stopping and sampling, researchers have explored *cascaded or routed inference* to reduce cost. Chen et al. (2024) escalate from cheaper to larger models only when necessary, using self-testing to decide. Mohammadshahi et al. (2024) learn to route prompts among multiple models, balancing cost and performance. These strategies complement our focus by showing that adaptive allocation can occur across models as well as within a single model’s sampling process.

## Appendix C UCB Pandora’s Box Algorithm

Algorithm [2](https://arxiv.org/html/2510.01394v1#alg2) provides the exact pseudo-code for the algorithm outlined in Section [3](https://arxiv.org/html/2510.01394v1#S3).

Figure: Algorithm 2 UCB Pandora’s Box Algorithm

## Appendix D Missing Figures

Figure: Figure 4: Median rewards across $960$ generations for $100$ prompts from the AlpacaEval dataset.
Refer to caption: frequency.png

We find that the median reward across 960 generations can vary significantly across prompts.

## Appendix E Missing Proofs and Theoretical Results

### E.1 Proof of Theorem 5

In this section, we include all missing proofs and helper lemmas needed to prove Theorem [5](https://arxiv.org/html/2510.01394v1#Thmtheorem5). The following helper lemmas will be useful.

###### Lemma 12 .

Let $D$ be any distribution, $c>0$ be the cost value for each sample, and $\tau=\tau(D,c)$ be the fair-cap value according to Definition [1](https://arxiv.org/html/2510.01394v1#Thmtheorem1). For every $\sigma>0$, we have that

$$ $\mathbb{E}_{v\sim D}\left[[v-(\tau+\sigma)]_{+}\right]\geq c-\sigma\cdot(1-F(\tau)),$ $$

where $F$ denotes the *CDF* of $D.$

###### Proof.

Observe the following sequence of inequalities.

$$ $\displaystyle\mathbb{E}_{v\sim D}\left[[v-(\tau+\sigma)]_{+}\right]-c$ $\displaystyle=\mathbb{E}_{v\sim D}\left[[v-(\tau+\sigma)]_{+}\right]-\mathbb{E}_{v\sim D}\left[[v-\tau]_{+}\right]$ $\displaystyle=\mathbb{P}_{v\sim D}\left[v\geq\tau\right]\mathbb{E}_{v\sim D}\left[[v-\tau-\sigma]_{+}-(v-\tau)|v\geq\tau\right]$ $\displaystyle\geq\mathbb{P}_{v\sim D}\left[v\geq\tau\right]\mathbb{E}_{v\sim D}\left[v-\tau-\sigma-(v-\tau)|v\geq\tau\right]$ $\displaystyle=(1-F(\tau))\cdot(-\sigma).$ $$

Rearranging completes the proof.
∎

###### Lemma 13 .

Let $D$ be any distribution, $c>0$ be the cost value for each sample and $\tau=\tau(D,c)$ be the fair-cap value according to Definition [1](https://arxiv.org/html/2510.01394v1#Thmtheorem1). Then, for every $n\in\mathbb{N}$ and $\sigma>0$ we have that

$$ $\mathbb{P}_{v_{1:n-1}\sim D^{n-1}}\left[\mathop{max}\{v_{1},\dots,v_{n-1}\}\in[\tau,\tau+\sigma]\right]\leq F^{n-1}(\tau+\sigma)-F^{n-1}(\tau).$ $$

###### Proof.

Fix $n\geq 1$ and let $M_{n-1}=\mathop{max}\{v_{1},\dots,v_{n-1}\}.$ Observe that $\mathbb{P}\left[M_{n-1}\leq x\right]=F^{n-1}(x)$ where $F$ is the CDF of $D$ because $v_{1:n-1}$ are iid draws. Noting that

$$ $\mathbb{P}\left[M_{n-1}\in[\tau,\tau+\sigma]\right]=\mathbb{P}\left[M_{n-1}\leq\tau+\sigma\right]-\mathbb{P}\left[M_{n-1}\leq\tau\right]$ $$

completes the proof.
∎

###### Lemma 14 .

Let $D$ be any distribution, $c>0$ be the cost value for each sample, and $\tau=\tau(D,c)$ be the fair-cap value according to Definition [1](https://arxiv.org/html/2510.01394v1#Thmtheorem1). Then, for every $n\in\mathbb{N}$ and $\sigma>0$, we have that

$$ $\mathbb{E}_{v_{1:n}\sim D^{n}}\left[\Delta_{n}\mathbf{1}_{B_{n}}\right]\geq-\sigma(1-F(\tau))\mathbb{P}\left[B_{n}\right]$ $$

where

$$ $\Delta_{n}:=[v_{n}-\mathop{max}\{v_{1:n-1}\}]_{+}-c,$ $$

and $B_{n}$ is the event that

$$ $\mathop{max}\{v_{1:n-1}\}\in[\tau,\tau+\sigma].$ $$

###### Proof.

(of Lemma [14](https://arxiv.org/html/2510.01394v1#Thmtheorem14))
It suffices to prove the lower bound

$$ $\mathbb{E}\left[\Delta_{n}|v_{1:n-1}\right]\geq-\sigma(1-F(\tau))$ $$

on the event that $B_{n}$ occurs. Since $v_{n}$ is independent of $v_{1:n-1}$, we have that

$$ $\mathbb{E}\left[\Delta_{n}|v_{1:n-1}\right]\geq\mathbb{E}\left[[v_{n}-(\tau+\sigma)]_{+}\right]-c\geq-\sigma\cdot(1-F(\tau)),$ $$

where the last inequality follows by Lemma [12](https://arxiv.org/html/2510.01394v1#Thmtheorem12).
∎

We are now ready to prove Theorem [5](https://arxiv.org/html/2510.01394v1#Thmtheorem5).

###### Proof.

(of Theorem [5](https://arxiv.org/html/2510.01394v1#Thmtheorem5)) Let $c>0$ be the sampling cost and $\mathcal{F}$ be any family of distributions that admits an anytime-valid upper confidence bound $\tau^{+}_{\delta}(n,v_{1:n})$ with width function $\sigma_{\delta,\tau}(n)$. Fix some $D\in\mathcal{F}$ and consider the iid sequence $v_{1},v_{2}\dots\sim D.$ let $\tau=\tau(D,c)$ be the fair-cap value of $(D,c)$ and $F$ denote the CDF of $D.$ For every $\delta\in(0,1)$, let $E_{\delta}$ denote the event in Definition [4](https://arxiv.org/html/2510.01394v1#Thmtheorem4).

For $n\geq 1$, write $M_{n-1}=\mathop{max}\{v_{1:n-1}\}$ and define

$$ $\Delta_{n}:=[v_{n}-M_{n-1}]_{+}-c$ $$

and

$$ $B_{n}:=\{M_{n-1}\in[\tau,\tau+\sigma_{\delta,\tau}(n)]\}.$ $$

On the event $E_{\delta}$, the two policies disagree only when event $B_{n}$ occurs. Hence,

$$ $\mathbb{E}\left((R_{W}-R_{U})\mathbf{1}_{E_{\delta}}\right]\leq\mathbb{E}\left[\sum_{n=1}^{\infty}-\Delta_{n}\mathbf{1}_{B_{n}}\mathbf{1}_{E_{\delta}}\right].$ $$

We aim to use Fubini’s theorem to swap the expectation with the sum. To do so, we need to show that

$$ $\sum_{n=1}^{\infty}\mathbb{E}\left[|-\Delta_{n}\mathbf{1}_{B_{n}}\mathbf{1}_{E_{\delta}}|\right]<\infty.$ $$

To see this, note that

$$ $|-\Delta_{n}\mathbf{1}_{B_{n}}\mathbf{1}_{E_{\delta}}|\leq(c+[v_{n}-M_{n-1}]_{+})\mathbf{1}_{B_{n}}\leq(c+[v_{n}-\tau]_{+})\mathbf{1}_{B_{n}},$ $$

where the last inequality follows from the fact that on $B_{n}$, we have that $M_{n-1}\geq\tau.$ Thus, it suffices to upper bound

$$ $\mathbb{E}\left[(c+[v_{n}-\tau]_{+})\mathbf{1}_{B_{n}}\right].$ $$

By conditioning on $M_{n-1}$ and using the tower law, we can write

$$ $\displaystyle\mathbb{E}\left[(c+[v_{n}-\tau]_{+})\mathbf{1}_{B_{n}}\right]$ $\displaystyle=\mathbb{E}\left[\mathbb{E}\left[(c+[v_{n}-\tau]_{+})\mathbf{1}_{B_{n}}|M_{n-1}\right]\right]$ $\displaystyle=\mathbb{E}\left[\mathbb{E}\left[c+[v_{n}-\tau]_{+}|M_{n-1}\right]\mathbf{1}_{B_{n}}\right]$ $\displaystyle=\mathbb{E}\left[\mathbb{E}\left[c+[v_{n}-\tau]_{+}\right]\mathbf{1}_{B_{n}}\right]$ $\displaystyle=\mathbb{E}\left[2c\mathbf{1}_{B_{n}}\right]$ $\displaystyle=2c\cdot\mathbb{P}\left[B_{n}\right]$ $\displaystyle=2c\cdot\left(F^{n-1}(\tau+\sigma_{\delta,\tau}(n))-F^{n-1}(\tau)\right)$ $\displaystyle\leq 2c\cdot F^{n-1}(\tau+\sigma_{\delta,\tau}(n)),$ $$

where the third equality is by independence of $v_{n}$ and $M_{n-1}$, the fourth equality is by definition of $\tau$, and the sixth equality by Lemma [13](https://arxiv.org/html/2510.01394v1#Thmtheorem13). Hence,

$$ $\sum_{n=1}^{\infty}\mathbb{E}\left[|-\Delta_{n}\mathbf{1}_{B_{n}}\mathbf{1}_{E_{\delta}}|\right]\leq 2c\sum_{n=1}^{\infty}F^{n-1}(\tau+\sigma_{\delta,\tau}(n))<\infty,$ $$

since $\sigma_{\delta,\tau}(n)\rightarrow 0$ as $n\rightarrow\infty.$ Accordingly, by Fubini’s, theorem, we have that

$$ $\mathbb{E}\left((R_{W}-R_{U})\mathbf{1}_{E_{\delta}}\right]\leq\sum_{n=1}^{\infty}\mathbb{E}\left[-\Delta_{n}\mathbf{1}_{B_{n}}\mathbf{1}_{E_{\delta}}\right].$ $$

By Lemma [14](https://arxiv.org/html/2510.01394v1#Thmtheorem14) we have that

$$ $\sum_{n=1}^{\infty}\mathbb{E}\left[-\Delta_{n}\mathbf{1}_{B_{n}}\mathbf{1}_{E_{\delta}}\right]\leq\sum_{n=1}^{\infty}\sigma_{\delta,\tau}(n)(1-F(\tau))\mathbb{P}\left[B_{n}\right].$ $$

Finally, by Lemma [13](https://arxiv.org/html/2510.01394v1#Thmtheorem13), we have that

$$ $\mathbb{P}\left[B_{n}\right]=F^{n-1}(\tau+\sigma_{\delta,\tau}(n))-F^{n-1}(\tau),$ $$

which completes the proof.
∎

###### Lemma 12 .

###### Proof.

###### Lemma 13 .

###### Proof.

###### Lemma 14 .

###### Proof.

###### Proof.

### E.2 Proof of Corollary 7

In this section, we include all missing proofs and helper lemmas needed to prove Corollary [7](https://arxiv.org/html/2510.01394v1#Thmtheorem7).

In order to use Theorem [5](https://arxiv.org/html/2510.01394v1#Thmtheorem5), we need to specify several things. First, Lemma[15](https://arxiv.org/html/2510.01394v1#Thmtheorem15) computes the fair cap value for an Exponential distribution with parameter $\lambda.$

###### Lemma 15 (Fair-cap value for Exponential distribution) .

Let $D_{\lambda}$ be the exponential distribution with parameter $\lambda>0.$ Then, for every $c>0$, the fair cap value $\tau$ associated with $(D,c)$ is $\frac{\log\left(\frac{1}{\lambda c}\right)}{\lambda}$

###### Proof.

For $v\sim\operatorname{Exp}(\lambda)$, we have

$$ $\mathbb{E}\left[[v-\tau]_{+}\right]=\int_{\tau}^{\infty}(x-\tau)\lambda e^{-\lambda x}=\frac{e^{-\lambda\tau}}{\lambda}.$ $$

Setting this equal to $c>0$ and solving for $\tau$ completes the proof.
∎

Next, we need to derive an anytime valid upper confidence bound on the fair-cap value for the Exponential distribution with parameter $\lambda.$ Note that an upper confidence bound on $1/\lambda$ gives an upper confidence bound on $\tau$ when $D_{\lambda}$ is an exponential distribution with parameter $\lambda$. Hence, as a first step, Lemma [16](https://arxiv.org/html/2510.01394v1#Thmtheorem16) derives an anytime-valid confidence sequence for the mean of the Exponential distribution.

###### Lemma 16 (Anytime-valid Confidence Sequence for Exponential distribution) .

Fix $\lambda>0$ and let $D_{\lambda}$ be an Exponential distribution with parameter $\lambda.$ Define

$$ $r_{\delta}(n):=\mathop{min}\Biggl\{\frac{1}{2},\sqrt{\frac{6}{n}\log\left(\frac{2n(n+1)}{\delta}\right)}\Biggl\}.$ $$

Then, for every $\delta\in(0,1)$, we have that

$$ $\mathbb{P}_{v_{1:\infty}\sim D^{\infty}}\left[\forall n\geq 1:\mu\in[\widehat{\mu}_{n}(1-r_{\delta}(n)),\widehat{\mu}_{n}(1+r_{\delta}(n))]\right]\geq 1-\delta$ $$

where $\mu=\frac{1}{\lambda}$ and $\widehat{\mu}_{n}=\frac{1}{n}\sum_{i=1}^{n}v_{i}.$

###### Proof.

Let $\lambda>0$ and $D_{\lambda}$ be an exponential distribution with parameter $\lambda.$ Let $v_{1},v_{2},\dots$ denote a sequence of iid draws from $D_{\lambda}.$ Define $w_{i}=v_{i}/\mu$, where $\mu=1/\lambda.$ Note that $w_{i}\sim\operatorname{Exp}(1).$ Fix some $n\geq 1$ and define $S_{n}:=\sum_{i=1}^{n}w_{i}\sim\operatorname{Gamma}(n,1)$. Note that $\frac{\widehat{\mu}_{n}}{\mu}=\frac{S_{n}}{n}.$ For any $s\in(0,1)$ we will show that

$$ $\mathbb{P}\left[\frac{\widehat{\mu}_{n}}{\mu}\geq\frac{1}{1-s}\right]\leq e^{-n\psi_{+}(s)}$ $$

and

$$ $\mathbb{P}\left[\frac{\widehat{\mu}_{n}}{\mu}\leq\frac{1}{1+s}\right]\leq e^{-n\psi_{-}(s)},$ $$

where

$$ $\psi_{+}(s):=\frac{s}{1-s}+\log(1-s),$ $$

and

$$ $\psi_{-}(s):=\log(1+s)-\frac{s}{1+s}.$ $$

Starting with the upper tail, by Markov’s inequality and the MGF of the $\operatorname{Gamma}(n,1)$, we have that

$$ $\mathbb{P}\left[S_{n}\geq a\right]=\mathbb{P}\left[e^{sS_{n}}\geq e^{sa}\right]\leq\frac{\mathbb{E}\left[e^{sS_{n}}\right]}{e^{sa}}=(1-s)^{-n}e^{-sa}.$ $$

With $a=\frac{n}{1-s}$, we have that

$$ $\mathbb{P}\left[\frac{\widehat{\mu}_{n}}{\mu}\geq\frac{1}{1-s}\right]=\mathbb{P}\left[S_{n}\geq a\right]\leq\exp\left(-n\left(\frac{s}{1-s}+\log(1-s)\right)\right)=e^{-n\psi_{+}(s)}.$ $$

For the lower tail, we use the fact that $x\rightarrow e^{-sx}$ is decreasing to get that

$$ $\mathbb{P}\left[S_{n}\leq a\right]=\mathbb{P}\left[e^{-sS_{n}}\geq e^{-sa}\right]\leq\frac{\mathbb{E}\left[e^{-sS_{n}}\right]}{e^{-sa}}=(1+s)^{-n}e^{sa}.$ $$

Using $a=\frac{n}{1+s}$, gives that

$$ $\mathbb{P}\left[\frac{\widehat{\mu}_{n}}{\mu}\leq\frac{1}{1+s}\right]\leq e^{-n\psi_{-}(s)}.$ $$

Now, we show that for any $s\in(0,1/2)$, we have that $\psi_{+}(s)\geq\frac{s^{2}}{6}$ and $\psi_{-}(s)\geq\frac{s^{2}}{6}.$ For $\psi_{+}$, define $h_{+}(s)=\psi_{+}(s)-s^{2}/6.$ Then, note that

$$ $h^{\prime}_{+}(s)=\frac{s}{(1-s)^{2}}-\frac{s}{3}=s\left(\frac{1}{(1-s)^{2}}-\frac{1}{3}\right)\geq\frac{2s}{3}\geq 0.$ $$

Since $h_{+}(0)=0$ and $h^{\prime}_{+}\geq 0$ we have that $h_{+}(s)\geq 0.$
For $\psi_{-}$, we have that

$$ $\psi_{-}(s)=\log(1+s)-\frac{s}{1+s}\geq\left(s-\frac{s^{2}}{2}\right)-\left(s-\frac{s^{2}}{1+s}\right)=s^{2}\left(\frac{1}{1+s}-\frac{1}{2}\right)=\frac{s^{2}(1-s)}{2(1+s)}\geq\frac{s^{2}}{6},$ $$

where the first inequality is due to the fact that $\log(1+s)\geq s-\frac{s^{2}}{2}$ for $s\in(0,1)$ and the last inequality uses the fact that $s\leq 1/2.$ We now complete the proof by picking a summable sequence $\delta_{n}.$ Namely, pick $\delta_{n}=\frac{\delta}{n(n+1)}$ and note that $\sum_{n\geq 1}\delta_{n}=\delta.$ At time $n\geq 1$, pick

$$ $r_{\delta}(n):=\mathop{min}\Biggl\{\frac{1}{2},\sqrt{\frac{6}{n}\log\left(\frac{2}{\delta_{n}}\right)}\Biggl\}=\mathop{min}\Biggl\{\frac{1}{2},\sqrt{\frac{6}{n}\log\left(\frac{2n(n+1)}{\delta}\right)}\Biggl\}.$ $$

Our previous analysis, then gives that

$$ $\mathbb{P}\left[\mu\notin[\widehat{\mu}_{n}(1-r_{\delta}(n)),\widehat{\mu}_{n}(1+r_{\delta}(n))]\right]\leq\delta_{n}.$ $$

Hence, by the union bound, we have that

$$ $\mathbb{P}\left[\exists n\geq 1:\mu\notin[\widehat{\mu}_{n}(1-r_{\delta}(n)),\widehat{\mu}_{n}(1+r_{\delta}(n))]\right]\leq\sum_{n=1}^{\infty}\delta_{n}=\delta,$ $$

which completes the proof.
∎

Note that the anytime-valid upper confidence bound on the mean $1/\lambda$ given by Theorem [16](https://arxiv.org/html/2510.01394v1#Thmtheorem16) can be computed just from the observed rewards. Hence, it applies to *every* distribution in our distribution family $\mathcal{F}.$ With Lemma [16](https://arxiv.org/html/2510.01394v1#Thmtheorem16) in hand, we can now prove Theorem [6](https://arxiv.org/html/2510.01394v1#Thmtheorem6), which gives an anytime-valid upper confidence bound on the fair-cap value for the family of Exponential distributions.

###### Proof.

(of Theorem [6](https://arxiv.org/html/2510.01394v1#Thmtheorem6)) Let $c>0$ be the sampling cost and $\mathcal{F}$ be the class of Exponential distribution with parameter $\lambda\in(0,\frac{1}{c\cdot e}].$ Fix a distribution $D_{\lambda}\in\mathcal{F}.$ Let $\tau=\tau(D,c)$ be the fair-cap value and $\mu=\frac{1}{\lambda}$ be the mean of $D_{\lambda}$. Finally, let $\delta\in(0,1)$ and consider the iid sequence $v_{1},v_{2},\dots\sim D_{\lambda}.$

By Lemma [16](https://arxiv.org/html/2510.01394v1#Thmtheorem16), we have that

$$ $\mathbb{P}\left[\forall n\geq 1:\mu\in[\widehat{\mu}_{n}(1-r_{\delta}(n)),\widehat{\mu}_{n}(1+r_{\delta}(n))\right]\geq 1-\delta.$ $$

From Lemma[15](https://arxiv.org/html/2510.01394v1#Thmtheorem15), we know that for the exponential distribution, its cap value is a monotonic in $\frac{1}{\lambda}$. Hence, with probability $1-\delta$, we have that

$$ $\mathbb{P}\left[\forall n\geq 1:\tau\in\left[\widehat{\mu}_{n}(1-r_{\delta}(n))\log\left(\frac{\widehat{\mu}_{n}(1-r_{\delta}(n))}{c}\right),\widehat{\mu}_{n}(1+r_{\delta}(n))\log\left(\frac{\widehat{\mu}_{n}(1+r_{\delta}(n))}{c}\right)\right]\right]\geq 1-\delta.$ $$

Take $\tau^{+}_{\delta}(n,v_{1:n}):=\widehat{\mu}_{n}(1+r_{\delta}(n))\log\left(\frac{\widehat{\mu}_{n}(1+r_{\delta}(n))}{c}\right).$ To complete the proof, it suffices to upper bound the difference

$$ $\widehat{\mu}_{n}(1+r_{\delta}(n))\log\left(\frac{\widehat{\mu}_{n}(1+r_{\delta}(n))}{c}\right)-\widehat{\mu}_{n}(1-r_{\delta}(n))\log\left(\frac{\widehat{\mu}_{n}(1-r_{\delta}(n))}{c}\right).$ $$

Consider the function $g(\mu)=\mu\log(\mu/c).$ Then, by the Mean Value Theorem and the fact that $g^{\prime}(\mu)=1+\log\left(\frac{\mu}{c}\right)$, we have that

$$ $\displaystyle g(\widehat{\mu}_{n}(1+r_{\delta}(n)))-g(\widehat{\mu}_{n}(1-r_{\delta}(n)))$ $\displaystyle\leq\left(1+\log\left(\frac{\widehat{\mu}_{n}(1+r_{\delta}(n))}{c}\right)\right)(2\widehat{\mu}_{n}r_{\delta}(n))$ $\displaystyle\leq\left(1+\log\left(\frac{\widehat{\mu}_{n}(1+r_{\delta}(n))}{c}\right)\right)\left(\frac{2r_{\delta}(n)\mu}{1-r_{\delta}(n)}\right)$ $\displaystyle\leq\left(1+\log\left(\frac{\mu(1+r_{\delta}(n))}{c(1-r_{\delta}(n))}\right)\right)\left(\frac{2r_{\delta}(n)\mu}{1-r_{\delta}(n)}\right).$ $$

Recall that $r_{\delta}(n)\leq\frac{1}{2}$ by definition. Hence,

$$ $\displaystyle\left(1+\log\left(\frac{\mu(1+r_{\delta}(n))}{c(1-r_{\delta}(n))}\right)\right)\left(\frac{2r_{\delta}(n)\mu}{1-r_{\delta}(n)}\right)$ $\displaystyle\leq\left(3+\log\left(\frac{\mu}{c}\right)\right)\left(4r_{\delta}(n)\mu\right)$ $\displaystyle=4r_{\delta}(n)\cdot\tau\cdot\left(1+\frac{3}{\log\left(\frac{\mu}{c}\right)}\right)$ $\displaystyle\leq 16r_{\delta}(n)\cdot\tau,$ $$

where the last inequality follows from the assumption that $\mu\geq e\cdot c.$ Hence, altogether, we can take

$$ $\sigma_{\delta,\tau}(n)=16r_{\delta}(n)\cdot\tau,$ $$

which completes the proof.
∎

Finally, we use Theorem [5](https://arxiv.org/html/2510.01394v1#Thmtheorem5) to bound the sub-optimality gap for UCB Pandora’s Box algorithm for the family $\mathcal{F}$ of Exponential distributions.

###### Proof.

(of Corollary [7](https://arxiv.org/html/2510.01394v1#Thmtheorem7)) Let $\mathcal{F}$ be the class of Exponential distribution with parameter $\lambda\in(0,\frac{1}{c\cdot e}].$ Fix a distribution $D_{\lambda}\in\mathcal{F}.$ Let $\tau=\tau(D,c)$ be the fair-cap value and let $\delta\in(0,1).$

Define

$$ $S:=\sum_{n=1}^{\infty}\sigma_{\delta,\tau}(n)(1-F_{\lambda}(\tau))\cdot(F^{n-1}_{\lambda}(\tau+\sigma_{\delta,\tau}(n))-F_{\lambda}^{n-1}(\tau))$ $$

By the Mean Value Theorem and the fact that the PDF $f$ is monotonically decreasing, we have that for some $b\in(\tau,\tau+\sigma_{\delta,\tau}(n))$,

$$ $\displaystyle F_{\lambda}^{n-1}(\tau+\sigma_{\delta,\tau}(n))-F_{\lambda}^{n-1}(\tau)$ $\displaystyle=\sigma_{\delta,\tau}(n)\cdot(n-1)\cdot F_{\lambda}^{n-2}(b)\cdot f_{\lambda}(b)$ $\displaystyle\leq\sigma_{\delta,\tau}(n)\cdot(n-1)\cdot F_{\lambda}^{n-2}(\tau+\sigma_{\delta,\tau}(n))\cdot f_{\lambda}(\tau).$ $$

Plugging this back in gives that

$$ $\displaystyle S$ $\displaystyle\leq\sum_{n=1}^{\infty}\sigma_{\delta,\tau}(n)\cdot(1-F_{\lambda}(\tau))\cdot\sigma_{\delta,\tau}(n)\cdot(n-1)\cdot F_{\lambda}^{n-2}(\tau+\sigma_{\delta,\tau}(n))\cdot f(\tau)$ $\displaystyle=\sum_{n=1}^{\infty}\sigma_{\delta,\tau}(n)^{2}\cdot(1-F_{\lambda}(\tau))\cdot(n-1)\cdot F_{\lambda}^{n-2}(\tau+\sigma_{\delta,\tau}(n))\cdot f_{\lambda}(\tau)$ $\displaystyle=\sum_{n=1}^{\infty}256\cdot\tau^{2}r_{\delta}(n)^{2}\cdot e^{-\lambda\tau}\cdot(n-1)\cdot(1-e^{-\lambda(\tau+\sigma_{\delta,\tau}(n))})^{n-2}\cdot\lambda\cdot e^{-\lambda\tau}$ $$

Now, observe that $r_{\delta}(n)^{2}\leq C\frac{\log(n/\delta)}{n}$ for some universal constant $C$. Hence,

$$ $S\leq\frac{256\cdot C\tau^{2}\lambda}{e^{2\lambda\tau}}\sum_{n=1}^{\infty}\log(n/\delta)\cdot(1-e^{-\lambda(\tau+16\tau\cdot r_{\delta}(n))})^{n-2}.$ $$

It suffices to upper bound

$$ $\sum_{n=1}^{\infty}\log(n/\delta)\cdot(1-e^{-\lambda(\tau+16\tau\cdot r_{\delta}(n))})^{n-2}.$ $$

Define $A:=e^{-\lambda\tau}$ and $q_{n}:=1-e^{-\lambda(\tau+16\tau\cdot r_{\delta}(n))}.$ Then, observe that

$$ $q_{n}=1-Ae^{-16\lambda\tau\cdot r_{\delta}(n)}.$ $$

We want to find the smallest $N$ such that for all $n\geq N$, we get

$$ $16\lambda\tau\cdot r_{\delta}(n)\leq\log 2.$ $$

Substituting the definition of $r_{\delta}(n)$ and solving for $n$ gives that we need to set

$$ $N\geq\Theta\left(\lambda^{2}\tau^{2}\log(1/\delta)\right).$ $$

For this choice of $N$, we have that for all $n\geq N$,

$$ $e^{-16\lambda\tau\cdot r_{\delta}(n)}\geq\frac{1}{2}\implies q_{n}\leq 1-\frac{A}{2}.$ $$

Thus, for all $n\geq N$, we have that

$$ $q^{n-2}_{n}\leq\left(1-\frac{A}{2}\right)^{n-2}.$ $$

Now, split the infinite sum

$$ $\sum_{n=1}^{\infty}\log(n/\delta)\cdot(1-e^{-\lambda(\tau+16\tau\cdot r_{\delta}(n))})^{n-2}=\sum_{n=1}^{\infty}\log(n/\delta)\cdot q_{n}^{n-2}=\sum_{n<N}\log(n/\delta)\cdot q_{n}^{n-2}+\sum_{n>N}\log(n/\delta)\cdot q_{n}^{n-2}.$ $$

We can trivially bound

$$ $\sum_{n<N}\log(n/\delta)\cdot q_{n}^{n-2}\leq N\log(N/\delta).$ $$

As for the second sum, we claim that

$$ $\sum_{n>N}\log(n/\delta)\cdot q_{n}^{n-2}\leq\sum_{n=1}^{\infty}\log(n/\delta)\left(1-\frac{A}{2}\right)^{n-2}\leq O\left(\frac{\log(2/\delta A)}{A}\right)=O\left(\lambda\tau\cdot e^{\lambda\tau}\cdot\log(1/\delta)\right)$ $$

To see why the second inequality is true, let $q:=1-\frac{A}{2}.$ Then,

$$ $\sum_{n=1}^{\infty}\log(n/\delta)\left(1-\frac{A}{2}\right)^{n-2}=\frac{1}{q^{2}}\sum_{n=1}^{\infty}\log(n/\delta)q^{n}.$ $$

We will focus on bounding $\sum_{n}\log(n/\delta)q^{n}.$ Define $p_{n}=(1-q)q^{n-1}.$ Note that $p_{n}$ is the PMF of a geometric distribution $p$ with parameter $1-q$. Then,

$$ $\sum_{n=1}^{\infty}\log(n/\delta)q^{n}=\frac{q}{1-q}\sum_{n\geq 1}p_{n}\log(n/\delta)=\frac{q}{1-q}\mathbb{E}_{n\sim p}\left[\log(n/\delta)\right].$ $$

By Jensen’s inequality and the fact that $\log(x/\delta)$ is concave, we have that

$$ $\mathbb{E}_{n\sim p}\left[\log(n/\delta)\right]\leq\log\left(\mathbb{E}_{n\sim p}\left[n/\delta\right]\right)=\log\left(\frac{1}{\delta(1-q)}\right).$ $$

Hence, we have that

$$ $\sum_{n=1}^{\infty}\log(n/\delta)q^{n}\leq\frac{q}{1-q}\log\left(\frac{1}{\delta(1-q)}\right)$ $$

and

$$ $\frac{1}{q^{2}}\sum_{n=1}^{\infty}\log(n/\delta)q^{n}\leq\frac{1}{q(1-q)}\log\left(\frac{1}{\delta(1-q)}\right).$ $$

Since $A\leq 1$, we have that $q\geq\frac{1}{2}$, thus,

$$ $\frac{1}{q^{2}}\sum_{n=1}^{\infty}\log(n/\delta)q^{n}\leq\frac{2}{(1-q)}\log\left(\frac{1}{\delta(1-q)}\right).$ $$

Plugging in $q=1-\frac{A}{2}$ completes the claim that

$$ $\sum_{n=1}^{\infty}\log(n/\delta)\left(1-\frac{A}{2}\right)^{n-2}\leq O\left(\frac{\log(2/\delta A)}{A}\right)=O\left(\lambda\tau\cdot e^{\lambda\tau}\cdot\log(1/\delta)\right),$ $$

where the last equality follows from the definition of $A.$ Now, returning to the original proof, we have that

$$ $\sum_{n=1}^{\infty}\log(n/\delta)\cdot(1-e^{-\lambda(\tau+16\tau\cdot r_{\delta}(n))})^{n-2}\leq\widetilde{O}_{\delta,\tau,\lambda}(\lambda^{2}\tau^{2})+\widetilde{O}_{\delta}\left(\lambda\tau\cdot e^{\lambda\tau}\right).$ $$

Multiplying by the outer factor gives that

$$ $\displaystyle S$ $\displaystyle\leq\frac{256\cdot C\tau^{2}\lambda}{e^{2\lambda\tau}}\left(\widetilde{O}_{\delta,\tau,\lambda}(\lambda^{2}\tau^{2})+O\left(\lambda\tau\cdot e^{\lambda\tau}\right)\right)$ $\displaystyle=\widetilde{O}_{\delta}\left(\frac{\lambda^{3}\tau^{4}}{e^{2\lambda\tau}}+\frac{\lambda^{2}\tau^{3}}{e^{\lambda\tau}}\right)$ $\displaystyle=\widetilde{O}_{\delta}\left(\frac{\lambda^{2}\tau^{3}}{e^{\lambda\tau}}\left(1+\frac{\lambda\tau}{e^{\lambda\tau}}\right)\right)$ $\displaystyle=\widetilde{O}_{\delta}\left(\frac{\lambda^{2}\tau^{3}}{e^{\lambda\tau}}\right)$ $\displaystyle=\widetilde{O}_{\delta}\left(\frac{(\lambda\tau)^{3}}{\lambda\cdot e^{\lambda\tau}}\right)$ $\displaystyle=\widetilde{O}_{\delta}\left(\frac{1}{\lambda}\right)$ $$

The third fifth equality follows from the fact that $\frac{x}{e^{x}}=O(1)$ and $\frac{x^{4}}{e^{x}}=O(1)$ respectively. This completes the proof.
∎

###### Lemma 15 (Fair-cap value for Exponential distribution) .

###### Proof.

###### Lemma 16 (Anytime-valid Confidence Sequence for Exponential distribution) .

###### Proof.

###### Proof.

###### Proof.

## Appendix F Additional Experimental Results

This appendix provides comprehensive experimental results across all datasets, language models, and reward models. While Section [5](https://arxiv.org/html/2510.01394v1#S5) focused on representative examples, here we present the complete evaluation demonstrating the consistency and robustness of our adaptive approach.

### F.1 Experiment 1: Profit Performance Across All Configurations

We evaluate how consistently our adaptive algorithm matches optimal non-adaptive performance across diverse settings. The profit performance ratio is defined as:

$$ $\text{Profit Performance Ratio}=\frac{\text{Profit of Adaptive Best-of-N}}{\text{Profit of Best Non-adaptive Best-of-N}}$ $$

where profit equals utility minus total generation cost. A ratio near 1.0 indicates the adaptive algorithm matches the best possible non-adaptive strategy without requiring hyperparameter tuning.

The results, shown in Figure [5](https://arxiv.org/html/2510.01394v1#A6.F5) for the AlpacaFarm and HH-RLHF datasets with RM-Mistral-7B and FsfairX-LLaMA3-RM-v0.1, confirm the adaptive algorithm’s strength.

The adaptive algorithm outperforms most of the time even the best-tuned generator dependent non-adaptive strategy. This implies that its dynamic behavior is more profitable than any fixed, one-size-fits-all approach.

Figure: Figure 5: Profit performance ratios for four LLM generators across varying cost/utility ratios. Each panel represents a different dataset-reward model combination, with four cost/utility scenarios per panel. Higher ratios indicate better profit efficiency relative to best non-adaptive algorithm.
Refer to caption: cost_alpaca_mistral.png

### F.2 Experiment 2: Win Rate Analysis Across Configurations

We compare head-to-head performance when adaptive and non-adaptive algorithms use identical computation budgets.

Figure: Figure 6: Performance evaluation of adaptive versus non-adaptive generation under matched computational budgets. Each row corresponds to a unique reward model-dataset configuration. Left panels present win rates computed from 100 sample permutations where adaptive algorithms compete against non-adaptive baselines. Right panels show mean sample counts (identical for both strategies due to budget matching) averaged over the same 100 permutations. Both metrics are plotted against cost (log scale, $10^{-5}$ to $10^{-2}$) and represent median values across all evaluation prompts.
Refer to caption: win_rate_alpaca_mistral.png

Figure [6](https://arxiv.org/html/2510.01394v1#A6.F6) reveals consistent patterns across all settings:

- •
Budget scaling: The adaptive algorithm’s advantage grows with the available budget. Its win rate increases from around 50% (at chance) with minimal resources to over 54% when the budget exceeds 100 samples.
- •
Model consistency: The win rate trends are remarkably consistent across different models. This demonstrates that the algorithm’s effectiveness is not tied to a specific model.
- •
Dataset effects: Similarly, the performance curves hold steady across different datasets, proving the algorithm is robust to variations in input data and prompt styles.

This consistent advantage across diverse models, datasets, and budgets validates our central hypothesis: the adaptive algorithm succeeds by exploiting the unique reward distribution of each prompt, rather than relying on a specific setup.

### F.3 Experiment 3: Efficiency Gains at Target Quality Levels

This experiment quantifies the computational efficiency of our adaptive algorithm. We measure how many fewer samples it needs than a non-adaptive approach to reach the same quality, defined by the acceptance rate.

Figure: Figure 7: Computational savings from adaptive generation while maintaining acceptance rate equivalence. Each row presents a unique reward model-dataset pairing. Left panels quantify the save ratio—the fraction of samples eliminated by adaptive algorithms compared to non-adaptive methods when both achieve identical average acceptance rates. Specifically, for each target acceptance rate, the adaptive algorithm yields an actual acceptance rate, and the non-adaptive sample count is calibrated to match this actual rate. Right panels show the relationship between target and actual acceptance rates for the adaptive algorithm, illustrating calibration behavior. Save ratios are averaged over 100 generation stream permutations, with all metrics indexed by target acceptance rate (0.6–1.0) and aggregated via median across 100 test prompts.
Refer to caption: save_ratio_alpaca_mistral.png

Figure [7](https://arxiv.org/html/2510.01394v1#A6.F7) demonstrates two critical findings:

Right panels (Target vs Achieved Rates): The adaptive algorithm effectively follows the desired quality targets. While a small gap exists between the target and achieved acceptance rates, the graphs confirm that our algorithm reliably adjusts its behavior to closely approximate the specified quality level across all configurations.

Left panels (Compute Savings): The algorithm delivers significant efficiency gains, with savings that peak when targeting high levels of quality. The trend is as follows:

- •
Savings increase from 10% at a moderate quality target (0.70 acceptance rate) to a peak of $\sim 30$% for near-optimal targets (0.90+ acceptance rate).
- •
However, savings decrease as the target approaches 100%. This is because the extreme quality requirement forces the adaptive algorithm to use its maximum sample budget, causing its behavior to converge with the non-adaptive baseline. Importantly, even in this scenario, it never performs worse.

This peak in savings at high (but not perfect) quality levels demonstrates the algorithm’s core strength: its ability to recognize when a near-optimal response has been found and stop generation early. In contrast, non-adaptive methods must always continue sampling to maintain the same quality guarantee.

Efficiency gains increase monotonically with target quality:

- •
Roughly 10% savings at 0.70 acceptance rate (moderate quality)
- •
Roughly 20% savings at 0.80 acceptance rate (good quality)
- •
Roughly 30% savings at 0.90+ acceptance rate (near-optimal quality)
- •
When 100% acceptance rate is targeted, our experimental setup suffers from maximum sample size leading that adaptive algorithm becomes closer to non-adaptive one. This explains decrease on save ratio as we get close to 100% target acceptance rate though it never performs worse than non-adaptive algorithm with same computation budget.

The increasing savings at higher quality levels reflect the adaptive algorithm’s ability to recognize when it has likely found a near-optimal response, while non-adaptive methods must continue sampling to maintain guarantees.

### F.4 Cross-Dataset and Cross-Model Insights

A cross-experimental analysis of our results reveals three consistent and noteworthy findings:

- •
Robustness Across Configurations: The performance metrics and advantages of the adaptive algorithm remained consistent across all 1,600 unique generation profiles. This demonstrates that the approach generalizes effectively and is not over-fit to specific model-dataset pairings.
- •
Positive Scaling with Budget: The superiority of the prompt-adaptive algorithm becomes more pronounced as the number of candidate generations increases, indicating that its advantages scale positively with a larger computational budget.
- •
Reward Model Independence: The performance trends were congruent for both the RM-Mistral-7B and FsfairX-LLaMA3-RM-v0.1 reward models. This suggests that the benefits of the adaptive strategy are independent of the specific reward function employed.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 2
presentation: 3
questions: 1. Could the authors compare against recent adaptive test-time compute allocation methods (e.g., Wang et al. 2025, Sun et al. 2024, Manvi et al. 2024, etc.)?
2. Does the adaptive stopping decision depend on sequential generation, or could rewards be computed in parallel after sampling a batch?
3. How sensitive is the algorithm to the chosen percentile α (e.g., 0.99)? Would smaller values degrade performance significantly?
soundness: 2
strengths: 1. Novel framing: Establishes a principled connection between inference-time optimization and the Pandora’s Box optimal stopping problem which is an original theoretical perspective.
2. Theoretical grounding: Provides regret bounds relative to Weitzman’s optimal stopping policy and extends these results to exponential families.
3. Empirical consistency: Results are coherent across models, showing that adaptive inference can yield similar reward quality with reduced sampling.
summary: * Problem: Large language model (LLM) generation requires balancing output quality against inference-time cost. Current strategies like Best-of-N sampling fix the number of generations in advance, leading to inefficiency.
* Solution: The paper reframes LLM inference as a Pandora’s Box optimal stopping problem. It introduces (1) a UCB-style Pandora’s Box algorithm that learns when to stop sampling without knowing the underlying reward distribution, and (2) a Bradley–Terry–based reward normalization to address cross-prompt scaling.
* Evaluation: Experiments on AlpacaFarm and HH-RLHF datasets across four LLMs and two reward models demonstrate that the adaptive method achieves comparable reward to Best-of-N sampling while using 15–35% fewer generations, supported by theoretical regret bounds relative to Weitzman’s optimal policy.
weaknesses: 1. A single basic baseline: The paper only compares against basic non-adaptive Best-of-N, omitting adaptive or GenRM/self-evaluation Best-of-N methods (e.g., speculative rejection, self-consistency, GenRM, self-evaluation, and many other approaches) that have surfaced in the past year or two. This limits the empirical significance of the reported 15–35% improvement which is relatively modest compared to what other works claim.
2. Lack of real compute and latency measurement: Efficiency is measured purely in terms of sample count, ignoring the additional cost of reward model inference or the sequential sampling latency. Parallel Best-of-N can often amortize cost, whereas the proposed adaptive approach incurs sequential latency. FLOPs or wall-clock time should be measured for fairness.

---

confidence: 3
contribution: 2
initial_rating: 4
presentation: 2
questions: **[L106]** "We note, however, that Weitzman's algorithm applies to multiple box types."

Could you please spell out the multiple-box setting (heterogeneous boxes) explicitly: assume different reward distributions ($D_1,\dots,D_k$) and opening costs ($c_1,\dots,c_k$)? Are draws independent across boxes?

**[L153]** "Weitzman's celebrated algorithm provides the optimal stopping strategy using fair-cap values when distributions are known."

Please add 2-3 sentences summarizing Weitzman's policy and its assumptions (known $D_i$ and $c_i$, independence, objective). Include a citation to Weitzman (1978) already in your references, plus a general optimal-stopping reference.

**[L173]** "no hope for designing a single, minimax optimal stopping policy S whose additive sub-optimality gap is uniformly bounded across all distributions."

Please define minimax precisely: is this $\inf_S \sup_{D} \mathbb{E}_D[R_W-R_S]$? If so, say so, and clarify that the impossibility is distribution-free over all $D$, motivating restriction to a family $\mathcal{F}$.

**[L174]** "we will assume that we have a known distribution family $\mathcal{F}$ such that the unknown $D\in\mathcal{F}$."

Please list the concrete assumptions on $\mathcal{F}$: identifiability, i.i.d. draws, existence/monotonicity of the fair-cap map $\tau(D,c)$, and that $\mathcal{F}$ admits an anytime-valid confidence sequence for $\tau$ (Def. 4). If you assume parametric (e.g., exponential tail), say so here, not only in §3.2/Alg. 1.

**[L198]** "the confidence parameter is a hyperparameter that influences the exploration-exploitation balance."

Could you please be explicit here? Something like: smaller $\delta$ ⇒ wider UCB on $\tau$ ⇒ more samples (conservative stopping). Is that what you meant? A short sentence quantifying how $\sigma_{\delta,\tau}(n)$ scales with $\delta$ (via $r_\delta(n)$ in Thm. 6) would also be nice.

**[L200–205]** "the fair-cap value often admits a simple monotonic dependence on the distribution's parameters…constructing a confidence sequence for $\tau$ can be reduced to…(1) CB for parameters…(2) propagate through the monotonic mapping."

Please clarify which parameters and the direction of monotonicity. Does monotonicity hold for every parameter or only for a specific scalar (e.g., mean/rate in the exponential)? How about the multi-parametric case?

**[L205 and L243]** The "confidence bounds for parameters → monotone map → confidence bounds for $\tau$" idea appears twice (around L205 and again near the statement/proof of Thm. 5).

Please keep it once and forward-reference the other to reduce redundancy.

**[L229]** You use "family" and later "Exponential distribution family."

Add a remark that *"exponential" here means the Exponential distribution (with rate/scale), not the general exponential family of distributions*. A footnote with a link to a standard reference should be fine.

**[L280]** "practitioners may adjust this parameter based on quality requirements."

What is your take on that? What is your opinion on how this is usually done? Please offer guidance.

**[L300]** "This transformation maps rewards into $[0,1]$."

Can $\mathrm{AR}_\kappa$ ever be exactly 0? Only in the limit $v\to-\infty$; for finite $v$ it's $>0$. Also, please explain the factor 2: it makes $\mathrm{AR}=1$ since the Bradley–Terry term equals 1/2 at $v=\kappa$.

**[L302]** "acceptance rate approximates the probability that an end-user accepts the response"

Confirm this refers to the particular sample with reward $v$. A small rephrase like "a response with reward $v$" would remove ambiguity.

**[L324]** "we exponentiate the rewards and fit a shifted exponential to the right-tail (above median)."

How many tail samples do you require before fitting? Please specify the minimum $t$ (Alg. 1), report sensitivity to $t$, and add a sanity check like a QQ-plot. Could you specify a rule-of-thumb to help practitioners?

**[L362–363]** "Streaming updates eliminate redundant computation"

Could be clarified with one sentence on what you cache.

**[L364]** "$\alpha$-percentile … computed in $O(1)$ from an analytical formula."

Please add the formula for the percentile.

**[L366]** "Riemann sum with $\sim 5000$ intervals."

Please justify accuracy (e.g., relative error $<1\%$ across all runs) and note the integrand's regularity. Did you try an adaptive quadrature (e.g., Simpson/Gauss–Legendre)?

**[L390]** "This formulation is useful in settings where quality requirements are clear but utilities are hard to quantify, for instance, when "good enough" responses are well-defined but the value of marginal improvements is ambiguous."

I find this hard to parse. Could you give an example?

**[L401]** "we use … FsfairX-LLaMA3-RM-v0.1 and RM-Mistral-7B."

Why these two reward models? Is there any reason for that?

**[L405]** "We always fix the max utility $B=1$."

Add one line that explains it. Something like: "by linearity, scaling utilities by $s>0$ and costs by $s$ leaves the threshold unchanged (since $\mathbb{E}[(U-\tau)_+]=c$ scales on both sides), so $B$ can be set to 1 w.l.o.g."

**Secretary problem mention**

Briefly mention the secretary problem as a classical optimal-stopping foil (unknown distributions, no recall), to position Pandora/Weitzman relative to other classics.

**Add general optimal-stopping references**

Like "Chow, Robbins, Siegmund (1971) *Great Expectations: The Theory of Optimal Stopping*" and maybe a modern set of lecture notes such as https://www.math.ucla.edu/~tom/Stopping/Contents.html. These will help readers new to the area.

**Fair-cap intuition**

Consider adding a one-line intuition to the fair-cap definition, something like: "$\tau$ is the reward level at which I'm indifferent between stopping now and paying cost $c$ for one more draw; i.e., the expected improvement from one more sample equals $c$."
soundness: 3
strengths: The paper is original in recasting prompt‑level sampling as a Pandora’s Box optimal‑stopping problem, importing fair‑cap thresholds and Weitzman‑style reasoning to yield an adaptive stopping rule that subsumes fixed-N heuristics and turns test‑time compute into a principled decision problem. It then formalizes the fair‑cap objective, an anytime‑valid UCB construction for the unknown threshold, a general additive‑gap template (Theorem 5) with an explicit exponential‑tail instantiation (Theorem 6, Corollary 7), and a practical algorithm with closed‑form components and small overhead (Algorithm 1). The empirical significance is demonstrated empirically across ~1,600 profiles (100 prompts × 2 datasets × 4 LLMs × 2 reward models): the adaptive policy matches non‑adaptive Best‑of‑(N) while saving roughly 15–35% of generations on average and winning under matched budgets, indicating a relevant method for practitioners seeking an inference‑time alternative to best-of-N.
summary: The authors introduce an inference‑time optimization framework grounded in the classical Pandora’s Box optimal‑stopping problem, treating each generation as opening a costly “box” with a random reward, and show that an adaptive stopping strategy can match the performance of non‑adaptive Best‑of‑N sampling while using roughly 15–35% fewer generations on average.
weaknesses: **Corollary 7 and "vanishing regret" need reconciliation**

Corollary 7 upper-bounds the sub-optimality by $O_\delta(1/\lambda)$, i.e., a distribution-dependent constant, not a term that vanishes with samples $n$ or confidence $\delta$. Please clarify whether any "vanishing" behavior is intended (e.g., in a different asymptotic or under additional assumptions), and align the abstract/claims ("guarantees vanishing regret relative to Weitzman's optimal policy") with the explicit bound you prove.

**Heavy reliance on modeling assumptions; robustness is unclear**

Guarantees assume (i) i.i.d. draws per prompt, (ii) known per-sample cost $c$, and (iii) a well-specified distribution family $\mathcal{F}$; the worked-out theory and the practical estimator both hinge on a (shifted) exponential tail fit. Could you provide any robustness results (or diagnostics) under tail mis-specification, e.g., when the right tail is heavier/lighter than exponential or multi-modal? Even a lemma or experiment quantifying degradation under controlled mis-fit would help.

**Discussion/conclusion are thin**

I understand the size limitation but the discussion section is not great. The paper doesn't have a proper conclusion and the discussion section reads as brief future-work notes; the paper lacks a proper Conclusion that synthesizes contributions, caveats, and takeaways for practitioners. Adding a short, explicit conclusion would improve readability.

**Related-work coverage is incomplete (see list below)**

Important recent work on inference-time alignment and adaptive compute is missing. Please add and discuss the listed papers; position your method theoretically and empirically relative to them.

- **Adaptive inference-time compute strategies:** (e.g., arXiv:2410.02725, arXiv:2503.01422, arXiv:2412.15287). Please compare assumptions, decision rules, and metrics. If possible, add a small head-to-head on a shared setup.

- **Inference-time alignment variants of Best-of-N:** soft-Best-of-N, Best-of-Poisson (e.g., arXiv:2506.19248, arXiv:2505.03156, arXiv:2507.05913). Ask: Where does your adaptive stopping dominate these stochastic Best-of-N variants at equal compute? Could your UCB fair-cap be combined with soft-aggregation?

**[L127]** "with N fixed in advance. Moreover, in practice, N is typically fixed."

Please rephrase to avoid repetition.

---

confidence: 2
contribution: 4
initial_rating: 6
presentation: 4
questions: * Can you elaborate on 1) if the Bradley-Terry Transformation is uniquely necessary to your results (and conversely, whether the PIT could be used to get the same insights) and 2) the tradeoffs between the two? One benefit I see of this transformation is that you don't need to estimate a CDF.
* Can you also clarify the choice of $\mathcal{F}$? What happens if the true distribution of rewards is vastly different than $\mathcal{F}$? Is there some sort of approximation error or tradeoff to choosing a specific (e.g., Exponential) distribution? All of your results begin with assuming a distributional family and then demonstrate that the anytime UCB policy has a low optimality gap on Weitzman's optimal policy. Can you say anything about using the wrong choice of distributional family in your Algorithm?
soundness: 3
strengths: * The framing of the problem is novel and highlights an area of improvement for the design of inference time algorithms
* The authors provide theoretical insights into the optimality gap of their approach.
* Through experiments, the method is demonstrated to have significant savings in terms of number of samples compared to Best-of-N.
summary: In this work, the authors model inference time sampling with early stopping as a "Pandora's Box Algorithm", where the goal is to develop an algorithm that decides when to stop generating inference samples and select the best one out of the existing set. The goal of this approach is to get efficiency speedups over having a fixed number of generations N a priori which might be wasteful if the reward-maximizing generation occurs early. 

They propose a UCB-Style Pandoras Box algorithm to handle settings where the underlying reward distribution is unknown and use this to create an on-the-fly inference time algorithm that determines when to stop adaptively.
weaknesses: * I'm not convinced that the Bradley-Terry Transformation is an important contribution beyond what allows you to prove about your algorithm. Prior works have used the Probability Integral Transform to normalize rewards, both theoretically and empirically, with success [1]. However, this is framed (in the abstract especially) as a core contribution of this work. I would like to see more commentary on the importance of this framework for future research.
* Additionally, it may be worth addressing [1] because they propose a randomized stopping method, which seems (slightly) relevant to your discussion on the limitations of stopping at a fixed N.


Small Notation Comments:
* Line 128: "with N fixed in advance. Moreover, in practice, N is typically fixed" is repetitive
* In the Algorithm, line 8, should the $\mu$s be $\hat{\mu}$s?

[1] Khalaf, H., Verdun, C. M., Oesterling, A., Lakkaraju, H., & Calmon, F. D. P. (2025). Inference-Time Reward Hacking in Large Language Models. NeurIPS 2025

---

confidence: 4
contribution: 2
initial_rating: 4
presentation: 3
questions: Q1: Qualitatively or quantitatively, can you discuss the tradeoffs between parallel BoN and sequential inference?

Q2: using the data collected for Figure 4, can you show how well the shifted exponential fit is on average per prompt? 

Q3: You set κ to the prompt-wise α-percentile and then map via AR_κ(v). This ties the utility to a quantile that itself is estimated online. This is confusing to me. This seems to say that the utility function is itself non-stationary. How does this reconcile with the theoretical analysis in Section 3, which assumes a fixed, albeit unknown, reward distribution?

Suggestion 1: Aside from fixed N, you could consider a baseline that stops after the reward has not improved by a meaningful amount for k consecutive steps, or one that stops after crossing a fixed reward threshold. Including such baselines would better isolate the specific benefits of the optimal stopping framework, which I do not exactly see. I would also test the impact of uncalibrated rewards to convince the readers of the usefulness of your BT-normalization compared to other standard techniques.

Suggestion 2: The current experiments evaluate the algorithm's end-to-end performance, but it is difficult to assess the accuracy of the underlying estimation of the fair-cap value τ, as the ground truth is unknown. Have you considered a setup with a verifiable reward (such as math)? I believe the usefulness of optimal stopping might be more apparent there.

Suggestion 3: I believe the paper is missing a few important references. One is AdaBoN [1] which is similar in spirit to your paper (posted on arxiv on May 2025). They also estimate the reward distribution online and then adaptively allocate the budget. Also, [2] train a model that predicts the expected marginal gain in reward from allocating additional responses to a prompt. I appreciate if you would discuss how your work compares to them. Moreover, [3] give a way to find the an optimal $N$ offline for BoN (posted on arxiv on June 2025)..However, they require access to a true reward calibration dataset.

[1] Raman, V., Asi, H., & Kale, S. (2025). AdaBoN: Adaptive Best-of-N Alignment. arXiv preprint arXiv:2505.12050.

[2] Damani, M., Shenfeld, I., Peng, A., Bobu, A., & Andreas, J. (2024). Learning how hard to think: Input-adaptive allocation of lm computation. COLM 2025.

[3] Khalaf, H., Verdun, C. M., Oesterling, A., Lakkaraju, H., & du Pin Calmon, F. (2025). Inference-Time Reward Hacking in Large Language Models. NeurIPS 2025.
soundness: 2
strengths: - Casting BoN as a fair-cap stopping problem is intuitive and principled. It introduces a formal decision-theoretic framework for inference-time alignment by providing  a concrete “when to stop” rule instead of grid-searching for N.
- I appreciate the thoughtfulness in considering practical challenges like cross-prompt reward miscalibration, as well as setting an acceptance-rate target.
- The empirical experiments are extensive, illustrative, and useful.
summary: The paper reframes Best-of-N as an optimal-stopping problem. The goal is to learn a fair-cap threshold online for a given prompt and stop once the running best reward crosses it. They estimate this threshold with a UCB-style rule and use a Bradley–Terry–style transform centered at a per-prompt quantile to normalize rewards across prompts. This adaptive policy is shown to achieve the same performance as a non-adaptive Best-of-N policy while requiring 15-35% fewer generations on average.
weaknesses: - My main concern is that best of $N$ is not run sequentially in practice. Modern inference systems are heavily optimized for parallel, batched decoding to maximize hardware utilization. An adaptive, sequential approach trades total compute for potentially higher latency and lower system throughput. This is why BoN is very attractive as an inference-time method, aside from its simplicity and effectiveness. The optimal stopping method adds more complexity because of the uncertainty in $N$, potentially making inference much less efficient.

- The sample counts (the $N$ in BoN) are large and unrealistic (> 50 in Figures 1 and 2). This may suggest (if I understand correctly) that the cost the authors fix to show the efficiency of their algoirthm may be unrealistic.

- There is a significant gap between the theory presented and the practical version of the algorithm. I appreciate the author's discussion of their algorithm that uses an explicit cost c and max utility B, which are acknowledged to be difficult to specify. However, what is actually deployable in practice is the target-acceptance variant. I believe this aspect was not discussed sufficiently, as it underpins the performance of their algorithm. This disconnect weakens the claim that the practical algorithm is principled and provably near-optimal.

- The practical algorithm's performance hinges on a strong, unmotivated parametric assumption: that the right tail of the (exponentiated) reward distribution can be modeled by a shifted exponential. The paper does not provide an empirical validation (e.g., goodness-of-fit tests) for this assumption. If there is a model mismatch, the UCB estimates for the fair-cap value could be invalid.

- The paper's novelty claims should be framed more precisely. I do not believe that the first contribution (claiming that you present the "the first stopping strategy that adapts to unknown reward distributions") is factual. The novelty is better framed as first application to LLM inference-time alignment, not the learning-theoretic idea itself.


Decision: Reject