acceptodds
Under review as a conference paper at ICLR 2027

Latency-Aware Adaptive Best-of-N

Abstract

Best-of- sampling is a widely deployed inference-time compute method for language models, but it can be computationally inefficient when applied uniformly across prompts without adjusting for problem difficulty. Recent adaptive variants allocate compute based on prompt-level signals such as observed rewards, curtailing generation when additional generations or tokens are unlikely to improve the final response. These methods, however, assume that the cost of additional compute is a fixed constant – an assumption violated in real serving systems, where the wall-clock time to generate a batch varies, growing with current server load, so a method using a single fixed parameter spends too little compute when generation is fast and too much when it is slow. We propose a two-stage adaptive Best-of- algorithm that adapts jointly to prompt difficulty and to generation latency: it draws an initial batch of completions in parallel, then uses the observed rewards and the time taken to generate them to decide whether to draw a second batch and at what size by weighing expected improvement in reward against predicted cost. Concretely, the algorithm is less likely to draw a second batch when the first batch was slow, and more likely when it was fast. We use a CDF-based reward transformation – mapping each observed reward to its estimated quantile under the prompt's reward distribution – to obtain a closed-form expression for the expected improvement that requires no Monte Carlo estimation. Because reward distributions have arbitrarily different scales across prompts, language models, and reward models, the CDF transformation also allows the same tradeoff parameters to be reused across tasks without retuning. We evaluate the method on a preference-based alignment benchmark and show that, under fixed latency, it improves over parallel Best-of- on the reward–compute Pareto frontier, and that, under variable latency, conditioning on the measured first-batch latency gives a higher *user reward* – the reward minus the cost of latency – than fixed-threshold (latency-unaware) baselines at matched numbers of generations, with the advantage growing as latency variability increases.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM inference-time compute, Efficient LLM inference-time compute, LLM serving

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_WnZEOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a latency-aware adaptive Best-of-N algorithm for allocating inference-time computation in large language models. The method adopts a two-stage framework that first generates a batch of candidate responses and then uses their observed rewards and generation latency to determine whether an additional batch should be generated. By applying a prompt-conditional CDF transformation to reward scores, the authors derive a closed-form expression for expected reward improvement and formulate a decision rule that balances response quality, generation cost, and latency. The method is evaluated through simulations involving four language models, three reward models, and two datasets, resulting in 24 experimental configurations. The results demonstrate improved reward–compute trade-offs compared with parallel Best-of-N under deterministic latency, while latency-aware adaptation achieves higher latency-adjusted user reward than latency-unaware alternatives under variable latency. Additional analyses investigate CDF estimation, latency correlation, batch-size effects, and adaptive second-batch sizing.

Critical strengths
  1. The paper identifies an important limitation of existing adaptive Best-of-N approaches that assume fixed additional sampling costs. By incorporating the observed first-batch latency into the stopping decision, the proposed method adapts computation allocation to changing latency conditions without requiring direct access to server-load information. This provides a meaningful extension to existing reward-based adaptive sampling strategies.

  2. The CDF transformation provides a unified reward scale and enables a closed-form expression for expected reward improvement under the stated assumptions. The evaluation covers 24 model–reward–dataset configurations and includes comparisons with parallel Best-of-N, latency-unaware variants, and oracle CDF policies. Additional sensitivity analyses help characterize the conditions under which the proposed approach is effective.

Critical weaknesses
  1. Although the proposed method consistently improves the simulated objective over the latency-unaware baseline in the reported settings, the absolute gains are small. Table 2 reports improvements of only +0.00025, +0.00070, and +0.00141 as the latency coefficient of variation increases from 0.5 to 2. Furthermore, Section 4.3 shows that parallel Best-of-N remains competitive under higher latency penalties when the estimated CDF is used. These findings suggest that the practical advantage of introducing latency-aware adaptation may be limited to particular operating conditions. A clearer characterization of when the additional adaptation is worthwhile would strengthen the paper's main contribution.

  2. The closed-form expected-improvement calculation relies on the prompt-conditional reward CDF, which is unknown in practice and must be estimated from the first batch. The experiments show a noticeable gap between the estimated-CDF and oracle policies, and Section 4.3 attributes part of the performance shortfall against parallel Best-of-N to CDF estimation error. Moreover, the shifted-exponential estimator requires offline reward rescaling, while Appendix F shows that additional calibration can improve performance. Although the theoretical CDF transformation is scale-free, the practical estimator therefore still depends on estimation and calibration choices. This weakens the claim of a broadly transferable decision rule without additional tuning.

  3. Although the framework allows the second-batch size to be selected adaptively, the main experiments use a fixed second-batch size of N2 = 80. Moreover, when the predicted latency cost is independent of the positive second-batch size, the latency term affects the stop-versus-continue decision but not the choice among different positive batch sizes. While Appendix M evaluates adaptive batch sizing and Appendix L considers batch-size-dependent latency, the paper does not clearly establish the additional benefit of jointly adapting batch size and stopping behavior to observed latency. Consequently, the empirical contribution of latency awareness is demonstrated more convincingly for stopping decisions than for adaptive batch-size selection.

  4. Section 3 relies primarily on mathematical equations to describe the proposed method, without providing an intuitive workflow diagram of the two-stage generation process, CDF estimation, latency prediction, and stopping decision. Such a diagram would improve the clarity of the proposed framework. Additionally, the evaluation relies on precomputed reward pools and simulated latency rather than a live inference-serving system. Although the appendices examine several latency assumptions, an end-to-end evaluation under realistic workloads would provide stronger evidence of the method's practical applicability.

Questions for authors
  1. Under what operating conditions does latency-aware adaptation provide a meaningful advantage over simpler alternatives? Table 2 reports relatively small improvements in the overall objective, while Section 4.3 shows that parallel Best-of-N remains competitive under higher latency penalties. Could the authors more explicitly characterize the ranges of latency cost, generation budget, and latency variability for which the proposed method outperforms both latency-unaware adaptation and parallel Best-of-N using the estimated CDF?

  2. How sensitive are the stopping decisions to CDF estimation errors? The paper reports a gap between estimated and oracle CDF policies, and Appendix F shows that calibration affects performance. Could the authors quantify how often CDF estimation changes the stop-versus-continue decision relative to the oracle policy, and how much of the resulting loss in the objective can be attributed to these incorrect decisions?

  3. What is the additional benefit of making second-batch size explicitly latency-aware? Under the main experimental latency model, the latency cost does not distinguish among positive second-batch sizes. Could the authors provide a controlled comparison under batch-size-dependent latency, separating the benefit of latency-aware stopping from the benefit of latency-aware batch-size selection?

  4. Could the authors provide preliminary validation using real serving latency traces or an online inference system? Such evidence would help establish whether the latency relationships assumed in the simulations are representative of realistic serving workloads.

1 comment
AuthorsOpenReview ↗

Response to Reviewer WnZE

Thank you for the review.

Weakness 1 and Question 1: Size of the gains and when latency awareness is worthwhile

The revised version replaces user reward with the proportion of generations-equivalent cost C=N‾+γT‾C = \overline N + \gamma \overline T (mean generations plus mean latency; γ=λlat/λgen\gamma = \lambda_{\text{lat}}/\lambda_{\text{gen}} is the number of generations one second is worth) saved relative to Best-of-NN at equal mean reward. With the estimated CDF, not the oracle:

  • Latency growth with batch size (β\beta) and latency cost (γ\gamma) (Table 1, Appendix F.1): the latency-aware policy saves at least as much as the latency-unaware one in every setting, most when latency grows with batch size (at β=1\beta = 1, γ=102\gamma = 10^2: 28.2% against 9.9% at Best-of-40's reward).
  • Variability and predictability of latency (Figure 3, Appendix F.4): the advantage over the latency-unaware policy is larger at higher latency coefficient of variation cvc_{\mathrm{v}} and log-latency correlation ρ\rho of the two batches.
  • Growth in savings with cost (Figure 2): the saving grows with Best-of-NN's cost CBoNC_{\text{BoN}} or is constant with it.

Weakness 2 and Question 2: CDF estimation and calibration

The calibration transfers across configurations: fitted on a configuration sharing none of the language model, reward model and dataset, the predicted Beta (Section 3.3) has an RMSE higher by at most a tenth (Table 8), and our policy saves at most one percentage point less than with its own fit (new Appendix E.1, Table 9). The tradeoff parameters, scale-free under the CDF transformation, need no retuning. In the revised version, the predicted Beta estimates the expected improvement in the main method: gradient-boosted trees, fitted once offline and fast online. The reward rescaling is one statistic, not tuned, and the regression removes most of its effect: without it, the debiased estimate's RMSE is within 8% in every configuration (Appendix D.2, Table 4).

We agree a gap to the oracle remains, but no prior adaptive Best-of-NN method we know of measures one, and none we ran saves more than ours at γ=0\gamma = 0 (new Appendix G). On Question 2 (new Appendix E.2, Table 10): on identical draws and tradeoff parameters, our policy decides differently from the oracle policy (whether to draw a second batch, or its size) in 1.7–93.2% of trials. At γ=0\gamma = 0 and β=1\beta = 1, in 32–43% of the differing trials ours draws a second batch where the oracle policy does not, and the reverse in at most 3%; these extra second batches cause 58–64% of the regret, and second batches of a different size about a third. At β≤0.5\beta \leq 0.5 with γ≥10\gamma \geq 10, the largest share of the regret comes from second batches the oracle draws and ours does not.

Weakness 3 and Question 3: Adaptive second-batch size

In the revised version, the adaptive batch size policy (batch sizes 11 to 320320) is our main policy, and mean latency grows with batch size, T‾(N)=5 s⋅(1−β+βN/80)\overline T(N) = 5\text{ s} \cdot (1 - \beta + \beta N/80) (Section 4.1). For β>0\beta > 0, T^2(s1,N2)\widehat T_2(s_1, N_2) depends on both T1T_1 and N2N_2, so T1T_1 changes which N2N_2 is chosen as well as whether to continue. Figure 2 and Appendix F.1 compare latency-aware and latency-unaware policies, each with adaptive or fixed batch sizes: the fixed batch size latency-aware policy adapts only its decision to continue to T1T_1, the adaptive one also N2N_2. The adaptive batch size policies save slightly more than the fixed ones, mainly when γ≤10\gamma \leq 10 or β=1\beta = 1.

Weakness 4 and Question 4: Workflow diagram and live evaluation

New Figure 1 is a workflow diagram of the two batches and the threshold on the first batch's best reward, which decreases with T1T_1.

The main experiments simulate latency, varying its variability (cvc_{\mathrm{v}}), how well T1T_1 predicts T2T_2 (ρ\rho) and its growth with batch size (β\beta). New Appendix H evaluates on measured latency. An unmodified vLLM server (one GPU, Llama, at most 16 sequences decoded at once) generates pool responses at their exact lengths, so rewards are known, and each batch's latency (generation plus scoring) is measured. In two settings, our requests alone and with other requests that vLLM's priority scheduling decodes first, latency grows nearly in proportion to batch size (Figure 12), the coefficient of variation of T1T_1 is 0.62 and 0.83, and the correlation of log⁡T1\log T_1 and log⁡T2\log T_2 0.99 and 0.94 (Table 16). Fitting the latency predictor and choosing N1N_1 on half the recorded sessions, evaluating on the rest, both policies reach Best-of-40's reward at 2–15% lower generations-equivalent cost than Best-of-NN with the predicted Beta (18–29% with the oracle), and ours saves more than the latency-unaware policy in 11 of the 12 rows of Table 18 (γ=1,10,100\gamma = 1, 10, 100), by up to 9.4 percentage points.

Reviewer_ZGc8OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a two-stage adaptive Best-of-N method that decides whether to draw a second batch of completions based on both the first batch’s rewards and how long the first batch took to generate, which it uses as a predictor of the second batch’s latency. In simulations over precomputed reward pools with synthetic latencies, the method slightly improves on parallel Best-of-N at matched numbers of generations.

Critical strengths

The paper has a good motivation that comes from the real-life serving of LLMs, and creates a new framework for the latency optimization during inference. The mathematical derivations are correct. The experiments are conducted over several different language models.

Critical weaknesses
  1. The problem setup is very artificial. It is unclear what is the meaning of λgen\lambda_{gen} and λlat\lambda_{lat}. The theoretical analysis is shallow.

  2. The motivation of the paper is to consider the real-life server load. However, no such experiments are conducted on real servers.

  3. The experiment setup does not reflect the inference process in real life. It evaluates the output on a given reward model, which can lead to the issue of reward hacking. Moreover, a higher reward score does not always mean better performance.

  4. The paper misses several closely related work.

    (1) Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment Huang et al. 2025

    (2) Best-of-Majority: Minimax-Optimal Strategy for Pass@ Inference Scaling Di et al. 2025

    (3) On the Limits of Test-Time Compute: Sequential Reward Filtering for Better Inference Yu et al. 2025

  5. (Minor) In figure 1, it is hard to see the correspondence of curves and algorithms.

Questions for authors

Can you design more realistic experiment setups, for example, using true evaluation labels or use the true latency?

3 comments
AuthorsOpenReview ↗

Response to Reviewer ZGc8

Thank you for the review.

Weakness 1: Problem setup, meaning of the tradeoff parameters, and theory

Meaning of λgen\lambda_{\text{gen}} and λlat\lambda_{\text{lat}}. Rewards enter the objective as CDF values Fx(r)F_x(r), i.e. win rates against a fresh response to the same prompt. So λgen\lambda_{\text{gen}} is the win rate one would give up to save one generation, λlat\lambda_{\text{lat}} to save one second of latency, and γ=λlat/λgen\gamma = \lambda_{\text{lat}}/\lambda_{\text{gen}} the number of generations one second is worth; mean generations plus γ\gamma times mean latency is the generations-equivalent cost. They are chosen once, offline, for a deployment target (Appendix I); the revised version states these units in Section 3.

Setup. Maximizing reward minus a cost of compute is the standard formulation of adaptive Best-of-NN: Kalayci et al., BEACON and LAND (a cost per response) and Dughmi et al. (a cost per batch) all use it, and Huang et al. (2025, "Latency and Token-Aware Test-Time Compute") maximize, as we do, a quality measure minus penalties on tokens and latency. Our setup adds a cost of the latency each batch actually takes.

Theory. The analysis consists of the closed-form expected improvement under the CDF transformation (Section 3.1), the threshold form of both policies with the latency-aware threshold decreasing in T1T_1 (Appendix B.2), an upper bound from the fully sequential policy (Appendix B.1), and the choice of N1N_1 (Appendix A). Our contribution is a method with an empirical evaluation; we claim no regret or optimality guarantees beyond these.

Weakness 2: No experiments on real servers

The main experiments simulate latency, varying what the policy's prediction of T2T_2 from T1T_1, its only use of the serving system, depends on: latency variability (cvc_{\mathrm{v}}), how well T1T_1 predicts T2T_2 (ρ\rho) and latency growth with batch size (β\beta). New Appendix H evaluates on measured latency. An unmodified vLLM server (one GPU, Llama, at most 16 sequences decoded at once) generates pool responses at their exact lengths, so rewards are known, and each batch's latency (generation plus scoring) is measured. In two settings, our requests alone and with other requests that vLLM's priority scheduling decodes first, latency grows nearly in proportion to batch size (Figure 12), the coefficient of variation of T1T_1 is 0.62 and 0.83, and the correlation of log⁡T1\log T_1 and log⁡T2\log T_2 0.99 and 0.94 (Table 16). Fitting the latency predictor and choosing N1N_1 on half the recorded sessions, evaluating on the rest, both policies reach Best-of-40's reward at 2–15% lower generations-equivalent cost than Best-of-NN with the predicted Beta (18–29% with the oracle), and ours saves more than the latency-unaware policy in 11 of the 12 rows of Table 18 (γ=1,10,100\gamma = 1, 10, 100), by up to 9.4 percentage points.

Weakness 3 and Question: Evaluation with the reward model, and true labels

We agree a reward model is an imperfect evaluator. Evaluating Best-of-NN with a reward model is standard on preference benchmarks, and our method applies to any scorer. New Appendix F.3 (Table 12) evaluates the responses each policy selects with the two other reward models, which did not select them. Measured by these, the proportion of generations-equivalent cost our policy saves relative to Best-of-NN at Best-of-40's reward is about the same as by the selecting one: e.g. 9.1% instead of 10.1% at γ=0\gamma = 0, and 31.2% instead of 28.2% at β=1\beta = 1, γ=102\gamma = 10^2. Our policy again saves more than the latency-unaware policy in every setting with a latency cost except one where neither saves anything. Ground-truth labels, such as pass/fail on coding tasks, need the outcome-reward variant of the method that the Conclusion names as future work.

Weakness 4: Missing related work

The revised version cites all three (Section 1.1). Huang et al. (2025, "Is Best-of-N the Best of Them?") show that Best-of-NN suffers from reward hacking at large NN and propose a rejection-sampling alternative; Di et al. (2025) select among NN samples by combining majority voting with reward for pass@kk; Yu et al. (2025) feed only high-reward generations back into the context. Each changes which response is returned from, or how to generate, a given number of samples, and none adapts that number to the prompt or to latency. They are complementary to our method, which decides how many responses to draw, and could be combined with it.

Weakness 5: Figure 1

That figure is removed in the revised version. The main results are now in Figures 2 and 3, where colour identifies the policy (red: ours), the marker and line style the estimate (plus signs: our predicted Beta; circles: oracle), and one legend covers all panels.

Thank you for your detailed response. However, I still find the problem setup not very convincing, which is my major concern. I will keep my original score.

AuthorsOpenReview ↗

Follow-up response to Reviewer ZGc8: new Appendix I.1 relating the objective to the budget-constrained problem

Thank you for following up. We read the concern about the problem setup as concerning the objective and its tradeoff parameters (Weakness 1), and answer it briefly.

The objective and budgets. A deployment target may be stated as budgets Bgen,Blat>0B_{\text{gen}}, B_{\text{lat}} > 0 on mean generations and mean latency rather than as tradeoff parameters. New Appendix I.1 proves that the two agree. For a policy π\pi, let Fx(R)‾π\overline{F_x(R)}_\pi, N‾π\overline N_\pi and T‾π\overline T_\pi be its mean reward, mean number of generations and mean latency. By linearity of expectation, the profit of Equation 1, our objective, is Vπ=Fx(R)‾π−λgenN‾π−λlatT‾πV_\pi = \overline{F_x(R)}_\pi - \lambda_{\text{gen}} \overline N_\pi - \lambda_{\text{lat}} \overline T_\pi. The expected budget-constrained problem is

max⁡πFx(R)‾πsubject toN‾π≤Bgen,T‾π≤Blat.\max_\pi \overline{F_x(R)}_\pi \quad \text{subject to} \quad \overline N_\pi \leq B_{\text{gen}}, \quad \overline T_\pi \leq B_{\text{lat}}.

A policy π⋆\pi^\star that maximizes VπV_\pi is optimal in the expected budget-constrained problem with Bgen=N‾π⋆B_{\text{gen}} = \overline N_{\pi^\star} and Blat=T‾π⋆B_{\text{lat}} = \overline T_{\pi^\star} (Proposition I.2). Conversely, our main result (Theorem I.7 of new Appendix I.1) is that for any budgets Bgen,BlatB_{\text{gen}}, B_{\text{lat}} such that N<BgenN < B_{\text{gen}} and T‾1(N)<Blat\overline T_1(N) < B_{\text{lat}} for some N∈Z1N \in \mathcal{Z}_1, there are λgen,λlat≥0\lambda_{\text{gen}}, \lambda_{\text{lat}} \geq 0 at which our latency-aware policy with the true reward CDF (Section 3.1) is optimal in the expected budget-constrained problem, with its ties broken in a suitable way, possibly at random: its first batch size is drawn among those that maximize its profit, and its action after the first batch among those that maximize its value. The proof combines the existence of an optimal policy within the budgets (Proposition I.4) with a Lagrangian duality argument (Proposition I.3). Raising λgen\lambda_{\text{gen}} lowers N‾π⋆\overline N_{\pi^\star} or leaves it unchanged, and likewise for λlat\lambda_{\text{lat}} and T‾π⋆\overline T_{\pi^\star} (Proposition I.1), so raising a tradeoff parameter lowers the corresponding budget or leaves it unchanged. So λgen\lambda_{\text{gen}} and λlat\lambda_{\text{lat}} are the Lagrange multipliers of the budgets, set once, offline, to keep the policy within them (Appendix I). Our conclusions do not depend on one choice: Figures 2–3 report the generations-equivalent cost saved relative to Best-of-NN at every λgen\lambda_{\text{gen}}, for γ=λlat/λgen\gamma = \lambda_{\text{lat}}/\lambda_{\text{gen}} from 00 to 10310^3, and Table 1 reports it at the reward of Best-of-40.

Realism of the evaluation. Appendix H evaluates the policies on latency measured on an unmodified vLLM server, and Appendix F.3 scores the selected responses with reward models that did not select them.

If the concern is about another part of the setup, such as the client deciding from its own measured latency or the limit of two batches, we would be glad to address it.

Reviewer_xchMOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The goal is to improve the computational efficiency of Best-of-N sampling using the first batch’s rewards and generation latency to decide whether to continue sampling or not. It first generates and scores a batch of responses and measures its latency. Using the reward of the responses, it estimates the prompt’s reward distribution and uses the best response’s quantile to calculate the expected improvement if we sample more. It then also uses the latency of the first batch to predict the next batch’s latency, assuming it remains the same. So, their method continues sampling if the expected improvement outweighs the generation and latency costs; otherwise, it returns the best response so far.

Critical strengths

The method is simple and intuitive: it draws batch of completions, observes their rewards and the latency , and only samples more if expected improvement outweighs latency cost. The simulation experiments are quite extensive. And they show not much in terms of latency gains but they show that it reduces generations, which would be useful for expensive API settings.

Critical weaknesses

The paper is based on the simple assumption that the second batch takes the same time as the first. But the gains of using this are small.

The comparisons mainly use plain Best-of-N and a latency-unaware variant of their method. They do not show the performance of other adaptive B-o-N methods.

Questions for authors

It makes sense that "whatever makes the first batch slow –server load, prompt length, output length, scheduling – largely persists over the short interval before the second batch is submitted," but do we have reports for this or can we determine factors that potentially drive the correlation, or experiments in real settings?

2 comments
AuthorsOpenReview ↗

Response to Reviewer xchM

Thank you for the review.

Weakness 1: The assumption T2=T1T_2 = T_1, and the size of the gains

The revised version does not assume T2=T1T_2 = T_1: the two batches' log-latencies have correlation ρ\rho, latency grows with batch size, and the policy predicts T2T_2 from T1T_1, ρ\rho and both batch sizes (Section 4.1). Sweeping ρ\rho from 00 to 11 (Appendix F.4), the latency-aware policy saves as much as the latency-unaware one at ρ=0\rho = 0 and more the higher ρ\rho is; predicting T2T_2 as if ρ=1\rho = 1 never saves more than using the true ρ\rho, and at ρ≤0.25\rho \leq 0.25 saves less than the latency-unaware policy.

Size of the gains. The revised version replaces user reward with the proportion of generations-equivalent cost C=N‾+γT‾C = \overline N + \gamma \overline T (mean generations plus mean latency; γ=λlat/λgen\gamma = \lambda_{\text{lat}}/\lambda_{\text{gen}} is the number of generations one second is worth) saved relative to Best-of-NN at equal mean reward. With the estimated CDF, not the oracle:

  • Latency growth with batch size (β\beta) and latency cost (γ\gamma) (Table 1, Appendix F.1): the latency-aware policy saves at least as much as the latency-unaware one in every setting, most when latency grows with batch size (at β=1\beta = 1, γ=102\gamma = 10^2: 28.2% against 9.9% at Best-of-40's reward).
  • Variability and predictability of latency (Figure 3, Appendix F.4): the advantage over the latency-unaware policy is larger at higher latency coefficient of variation cvc_{\mathrm{v}} and log-latency correlation ρ\rho of the two batches.
  • Growth in savings with cost (Figure 2): the saving grows with Best-of-NN's cost or is constant.

Weakness 2: Comparison with other adaptive Best-of-N methods

Our latency-unaware policy stands for adaptive Best-of-N methods that draw responses or batches until the expected reward improvement falls below a fixed cost, or equivalently the highest reward exceeds a fixed threshold (Section 1.1; new Appendix B.2), including Kalayci et al., BEACON, LAND, and Manvi et al. None conditions stopping on measured latency, our primary contribution; comparing our latency-aware and -unaware policies isolates it. Unlike these methods, our policies draw at most two batches, an advantage, we argue, in online serving, where each batch adds latency (Section 1). This is common: for Best-of-NN, Dynasor (Fu et al.), built for serving systems, is our latency-unaware fixed batch size policy, checking its threshold once since more checks mean more sequential batches, which they found substantially raises latency. AdaBoN also draws two batches but spreads a budget across prompts, so Best-of-NN strictly dominates it for one prompt; hence it is not among our baselines.

New Appendix G (Tables 13–15) adds Kalayci et al.'s method, BEACON, and Manvi et al.'s batch schedule, the last run with our debiased CDF estimate (the predicted Beta's mean) as their self-evaluation model is unreleased. Table 13 compares them with our adaptive batch size policies at Best-of-40's reward. At γ=0\gamma = 0 and at β=1\beta = 1 (latency proportional to batch size), our latency-unaware policy saves as much as the best of them (9.9–10.3% against at most 9.9%), so the two-batch limit costs nothing; at β=1\beta = 1 our latency-aware policy saves 14.0% and 28.2% (γ=10,102\gamma = 10, 10^2). At β≤0.5\beta \leq 0.5 and γ≥10\gamma \geq 10, although the latency-aware and -unaware policies perform similarly (saving −0.5% to 2.6%), they far outperform the other methods, the best of which costs 20.3–75.3% more than Best-of-NN: when latency depends less on batch size, limiting the number of batches to two is an advantage.

Question: What drives the correlation of T1T_1 and T2T_2

Section 2.2 (revised) names how these factors raise latency: load lengthens each decoding step and, on a full server, delays the start of decoding; a larger batch takes longer when the server cannot decode it all at once, and completes only with its longest response. The two batches also share the prompt, and so the distribution of their response lengths. Appendix H separates the two: with our requests alone, T1T_1 varies only through response lengths; other requests decoded first add varying load.

New Appendix H evaluates on measured latency. An unmodified vLLM server generates pool responses at their exact lengths, so rewards are known, and each batch's latency is measured. In two settings, our requests alone and with other requests decoded first, latency grows nearly in proportion to batch size (Figure 12), the coefficient of variation of T1T_1 is 0.62 and 0.83, and the correlation of log⁡T1\log T_1 and log⁡T2\log T_2 0.99 and 0.94 (Table 16). The adaptive batch size policies reach Best-of-40's reward at 2–15% lower generations-equivalent cost than Best-of-NN with the predicted Beta (18–29% with the oracle), and the latency-aware policy saves more than the latency-unaware one in 11 of the 12 rows of Table 18, by up to 9.4 percentage points.

Thank you for the additional experiments. The measured latency results and added adaptive baselines address my concerns about the original assumptions and comparisons. However, my overall assessment remains unchanged.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Description of changes since submission

We have uploaded a revised PDF. Below are its changes from the submitted version; each change that addresses a reviewer's concern is tagged with the reviewer and the weakness (W) or question (Q). Numbers refer to the revised PDF unless marked "submitted".

Changes addressing the reviewers' concerns

  • Results as cost saved relative to Best-of-NN (WnZE W1, Q1; xchM W1; ZGc8 W5). Sections 4.2–4.3 replace submitted Experiments 1–2 (Figures 1–2, Tables 1–2, Appendix K, user reward). Instead of plotting the "user reward" Fx(R)‾−λlatT‾\overline {F_x(R)} - \lambda_{\text{lat}} \overline T against the mean number of generations N‾\overline N, we measure the generations-equivalent cost C=N‾+γT‾C = \overline N + \gamma \overline T (mean generations plus mean latency, with γ=λlat/λgen\gamma = \lambda_{\text{lat}}/\lambda_{\text{gen}}), compared with Best-of-NN's at equal mean reward (Figures 2–3, Table 1, Appendix F.1), across the latency cost γ\gamma and the latency model. Our primary metric is the proportion of generations-equivalent cost saved.
  • Workflow diagram (WnZE W4). New Figure 1 shows the two batches and the threshold on the first batch's best CDF-transformed reward, which decreases with the first batch's latency T1T_1.
  • Adaptive second-batch size and batch-size-dependent latency (WnZE W3, Q3). The adaptive batch size policy (batch sizes 1 to 320) is our main policy, mean latency grows with batch size as 5 s⋅(1−β+βN/80)5\text{ s} \cdot (1 - \beta + \beta N/80) (Section 4.1), and Section 3.1 states that the chosen N2N_2 then depends on T1T_1. Figure 2 and Appendix F.1 compare the latency-aware and latency-unaware policies, each with adaptive and with fixed batch sizes. This replaces submitted Appendices L and M.
  • T2T_2 correlated with T1T_1 (xchM W1). The two batches' log-latencies have correlation ρ\rho, and the latency-aware policy predicts T2T_2 from T1T_1 and both batch sizes (Section 4.1). Figure 3 includes ρ=0.5\rho = 0.5; Appendix F.4 (submitted Appendix J) sweeps ρ\rho from 0 to 1 with a predictor that wrongly assumes ρ=1\rho = 1.
  • Estimating the expected improvement (WnZE W2, Q2). The method now uses the predicted Beta (Section 3.3): gradient-boosted trees, fitted offline on other prompts, predict a Beta distribution for Fx(R1)F_x(R_1), which corrects both the bias of the CDF estimate and the convexity of the expected improvement; submitted Appendix F corrected only the bias. New Appendix E.1 (Table 9) fits it on another configuration; new Appendix E.2 (Table 10) counts how often it changes the decision to draw a second batch relative to the oracle policy, and how much of the difference in VV each kind of change accounts for.
  • Meaning of the tradeoff parameters (ZGc8 W1). Section 3 states their units (transformed reward given up per generation and per second) and points to Appendix I for choosing them. New Appendix I.1 proves that they are the Lagrange multipliers of budgets on mean generations and mean latency.
  • Evaluation by reward models that did not select the response (ZGc8 W3, Q). New Appendix F.3 (Table 12).
  • Related work (ZGc8 W4; xchM W2). Section 1.1 cites Huang et al. (2025, "Is Best-of-N the Best of Them?"), Di et al. (2025) and Yu et al. (2025), adds LAND, and states which adaptive Best-of-NN methods stop once their signal exceeds a threshold, as our latency-unaware policy does. Appendix B.2 proves that both of our policies compare Fx(R1)F_x(R_1) with a threshold, fixed for the latency-unaware policy and, with the latency predictor of Section 4.1, decreasing in T1T_1 for ours.
  • Comparison with other adaptive Best-of-NN methods (xchM W2). New Appendix G (Tables 13–15) runs the methods of Kalayci et al., BEACON and Manvi et al. on our reward pools, draws and latency model.
  • Latency measured on a live server (WnZE W4, Q4; ZGc8 W2, Q; xchM Q). New Appendix H evaluates the policies on latency measured on an unmodified vLLM server, with our requests alone and with other requests decoded first. Section 2.2 describes how server load and batch size raise latency.

Further changes

  • The Introduction frames the problem for adaptive test-time compute in general, whose methods often stop at a fixed threshold, argues for two batches from the latency cost of drawing responses one at a time, and states the results above; the Abstract and Conclusion match.
  • Section 2.2: the assumption of a high-load regime, under which latency did not depend on batch size, is replaced by the assumption that requests from adaptive policies such as ours are a small share of the server's load.
  • Section 3 is reorganized: Section 3.1 derives the latency-aware policy and its choice of N1N_1 (details in Appendix A), Section 3.2 defines the baselines, and Section 3.3 the estimate of the expected improvement.
  • Appendix D compares the CDF estimators also after debiasing, as inputs to the predicted Beta; new Appendix E.3 shows how the predicted Beta's correction for convexity depends on N2/N1N_2/N_1.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.