- 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
-
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.
-
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
-
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.
-
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.
-
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.
-
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
-
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?
-
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?
-
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?
-
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.
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 (mean generations plus mean latency; γ=λlat/λgen is the number of generations one second is worth) saved relative to Best-of-N at equal mean reward. With the estimated CDF, not the oracle:
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-N method we know of measures one, and none we ran saves more than ours at γ=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 and β=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 with γ≥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 1 to 320) is our main policy, and mean latency grows with batch size, T(N)=5 s⋅(1−β+βN/80) (Section 4.1). For β>0, T2(s1,N2) depends on both T1 and N2, so T1 changes which N2 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 T1, the adaptive one also N2. The adaptive batch size policies save slightly more than the fixed ones, mainly when γ≤10 or β=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 T1.
The main experiments simulate latency, varying its variability (cv), how well T1 predicts T2 (ρ) and its growth with batch size (β). 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 T1 is 0.62 and 0.83, and the correlation of logT1 and logT2 0.99 and 0.94 (Table 16). Fitting the latency predictor and choosing N1 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-N 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), by up to 9.4 percentage points.