Test-time compute (TTC) improves language model responses by spending additional computation at inference time, and the right amount of compute depends on the prompt. Adaptive TTC methods allocate compute based on signals of response quality such as observed rewards, often by stopping once the signal exceeds a fixed threshold, and generally measure cost by the number of generations or tokens. But in online serving, latency is also a cost: it grows with server load, so a method using a fixed threshold spends too little compute when generation is fast and too much when it is slow. For Best-of-N sampling, a widely used TTC method, we propose a two-stage adaptive algorithm that draws an initial batch, then uses the observed rewards and the batch's latency to decide whether to draw a second batch and at what size by comparing expected improvement against predicted cost: it draws one when the first batch's best reward is below a threshold that decreases with the first batch's latency, without explicitly measuring server load. We map each reward to its value under the cumulative distribution function (CDF) of the prompt's reward distribution, so the same tradeoff parameters can be reused across tasks; a regression fitted offline on other prompts predicts a distribution for the CDF value of the first batch's best reward, giving the expected improvement in closed form. We evaluate the method by simulation on a preference-based alignment benchmark, measuring generations-equivalent cost: generations plus latency, converted to generations. The method reaches Best-of-N's reward at lower generations-equivalent cost, and conditioning on the measured first-batch latency saves at least as much of that cost as fixed-threshold (latency-unaware) baselines, and more when latency is highly variable, when it grows with batch size, and when the second batch's latency is highly predictable from the first's.
Figures & tables
Figure 1: (a) Our policy draws a second batch after a fast first batch and stops after a slow one. (b) It draws a second batch, of adaptively chosen size, when the first batch’s CDF-transformed best reward Fx(R1) is below a threshold that falls with the first batch’s latency T1 ; the latency-unaware policy’s threshold is fixed ( Section B.2 ). Grey: the distribution of T1 . Settings ( Section 4.1 ): Fx known, β=0.5 , cv=2 , ρ=1 , λgen=10−3.5 , λlat=10−1.5 .
Figure 2: Top: mean normalized reward rank against generations-equivalent cost C=N+γT (mean generations N , mean latency T ). Bottom: proportion of generations-equivalent cost saved (CBoN−Cpolicy)/CBoN at equal mean normalized reward rank against Best-of- N ’s generations-equivalent cost CBoN . x -axis in log scale. Lines are along a ray λlat=γλgen for γ=0 , 10 , 102 and 103 (columns), all at β=0.5 , cv=2 , ρ=1 , batch sizes {1,…,320} , averaged over the 24 configurations. Colour is the policy (red: ours); dash-dot with plus signs: predicted Beta (ours); dashed with circles: oracle. Leftmost column shows γ=0 , where the latency-aware and latency-unaware policies coincide; Best-of- N ’s theoretical reward N/(N+1) in dashed gold, fully sequential bound ( Section B.1 ) in dashed green (mean reward 1−2N1 , proportion saved 21−2N1 ). Results for β∈{0,0.5,1} , γ∈{1,10,102,103} in Section F.1 ; per-configuration results in Section F.2 .
predicted Beta (ours)
oracle
β
γ
latency-unaware
latency-aware
latency-unaware
latency-aware
–
0
10.1
10.1
25.0
25.0
0
101
−0.3
0.5
1.8
4.1
0
102
0.0
0.0
0.0
0.1
0.5
101
−0.5
2.6
7.8
11.3
0.5
102
−0.1
2.6
1.3
6.5
Table 1: Proportion (%) of generations-equivalent cost saved at the reward of Best-of- N with N=40 , by the adaptive batch size policies with batch sizes {1,…,320} , at cv=2 and ρ=1 , averaged over the 24 configurations. At γ=0 the two latency rules are one policy and β does not apply.
Figure 3: The proportion of generations-equivalent cost C=N+γT (mean generations N , mean latency T ) saved, (CBoN−Cpolicy)/CBoN at equal mean normalized reward rank, against Best-of- N ’s generations-equivalent cost CBoN=N+γLh(N) (log scale), at γ=10 and 102 (rows) and β=0 , 0.5 and 1 (columns), adaptive batch sizes {1,…,320} , averaged over the 24 configurations. Our policy (red) is shown at cv=1 and 2 with ρ=1 , and at cv=2 with ρ=0.5 . Since it never sees T1 , the latency-unaware policy (purple) behaves the same at every cv and ρ so only needs one line.
Appendix figures & tables16 assets
Supplementary material from the paper’s appendix.
Appendix
RMSE of CDF, debiased ( ×10−2 )
N1=15
30
60
120
240
In-sample KDE
5.40
2.85
1.50
0.82
0.47
LOO KDE ( ×0.5 )
5.42
2.86
1.50
0.82
0.46
LOO KDE ( ×1.0 )
5.40
2.85
1.50
0.82
0.47
Normal
5.46
2.93
1.57
0.87
0.51
GMM-2
5.64
2.96
1.52
0.81
0.46
Shifted exponential (ours)
5.27
2.71
1.42
0.78
0.47
Appendix
Table 2: RMSE of each estimator of Fx(R1) after debiasing, and bias of the estimate itself, against the held-out empirical CDF value, for the six estimators considered, as a function of N1 , averaged over the 24 configurations of Section 4.1 . Held-out rewards tied with R1 count as half. Positive bias: the estimator overstates Fx(R1) . Averaged over 100 prompts, M=200 Monte Carlo trials, and the 24 configurations; lowest debiased RMSE per column in bold, both entries where two tie at the printed precision. Each estimator is debiased by binned means fitted on the other half of the configuration’s prompts. Per-configuration values are in Table 3 .
Figure 4: Six estimators of Fx(R1) against the Stage-1 batch size N1 (log scale), averaged over the 24 configurations of Section 4.1 : RMSE of the estimate (left), RMSE after debiasing divided by that of the debiased shifted exponential (middle), and bias of the estimate (right). Dashed black: the shifted exponential after debiasing. The in-sample KDE’s debiased curve coincides with the leave-one-out KDE’s ( ×1.0 ): with the same bandwidth, the former is an increasing affine function of the latter, which the debiasing map undoes. The in-sample KDE is the canonical KDE baseline of Raman et al. (2025) ; the predicted Beta takes the shifted-exponential estimate as its main input ( Appendix E ).
dataset
RM
LM
N1=15
30
60
120
240
AlpacaFarm
FsfairX
Llama
0.985
0.976
0.998
1.044
1.101
Gemma
0.977
0.962
0.965
0.999
1.104
Mistral
0.980
0.960
0.969
1.026
1.072
Qwen
0.968
0.936
0.928
0.959
1.008
RM-Mistral
Llama
0.972
0.946
0.948
0.979
1.002
Gemma
0.958
0.931
0.930
0.958
1.008
Appendix
Table 3: RMSE after debiasing of the shifted-exponential estimate of Fx(R1) divided by that of the best of the five competing estimators after the same debiasing, in each of the 24 configurations of Section 4.1 . Below one, ours is the most accurate; bold marks those entries. Averaged over 100 prompts and M=200 Monte Carlo trials. Debiased, our estimator has the lowest RMSE in 24, 24, 22, 16, 9 of the 24 configurations at N1=15,30,60,120,240 respectively.
N1=20
N1=80
dataset
RM
LM
s
est., r
est., r/s
deb., r
deb., r/s
est., r
est., r/s
deb., r
deb., r/s
AlpacaFarm
FsfairX
Llama
0.968
4.24
4.26
3.95
3.95
1.13
1.13
1.01
1.01
Gemma
0.627
4.51
4.75
4.35
4.25
1.30
1.41
1.22
1.21
Mistral
0.840
4.21
4.34
3.82
3.79
1.04
1.12
0.95
0.95
Qwen
0.818
4.27
4.37
3.98
3.95
1.18
1.20
1.04
1.04
RM-Mistral
Llama
0.938
4.20
4.25
3.81
3.80
1.08
1.11
0.95
0.95
Appendix
Table 4: The reward scale s of each of the 24 configurations of Section 4.1 , and the RMSE ( ×10−2 ) of the shifted-exponential estimate F^x(R1) fitted to the raw rewards r and to the rescaled rewards r/s , as the estimate itself (est.) and after debiasing (deb.), at first-batch sizes N1=20 and 80 , measured as in Table 5 . s is the median within-prompt standard deviation over the full pool of 100 prompts and 960 responses. Debiasing is by binned means, each half of a configuration’s prompts mapped by the map fitted on the other half.
RMSE of CDF ( ×10−2 )
κ
N1=10
20
40
80
160
240
0.5
8.27
4.04
2.05
1.23
0.92
0.81
0.7
8.37
4.12
2.04
1.11
0.74
0.62
0.85
8.45
4.21
2.09
1.11
0.69
0.56
1
8.53
4.31
2.17
1.15
0.69
0.54
1.2
8.65
4.45
2.30
1.23
0.72
0.55
Appendix
Table 5: RMSE of the shifted-exponential estimate F^x(R1) , and of the same estimate after debiasing, when rewards are scaled to κ times unit median within-prompt spread, averaged over the 24 configurations of Section 4.1 . The paper uses κ=1 . Averaged over 100 prompts and 300 Monte Carlo draws per prompt; best per column in bold. Stage-1 batches are drawn from the full pool and scored against the normalized reward rank of Appendix C , as in Table 7 , not against the held-out empirical CDF of Table 2 , so the values differ slightly from that table’s. Debiasing is by binned means, each half of a configuration’s prompts mapped by the map fitted on the other half.
prompts
n=5
n=10
n=20
n=50
m=10
0.83 [0.55, 1.30]
0.90 [0.64, 1.29]
0.94 [0.65, 1.34]
0.99 [0.71, 1.36]
m=25
0.82 [0.64, 1.06]
0.89 [0.72, 1.17]
0.92 [0.74, 1.21]
0.98 [0.78, 1.20]
m=50
0.83 [0.69, 0.99]
0.90 [0.75, 1.06]
0.95 [0.81, 1.10]
0.97 [0.84, 1.11]
Appendix
Table 6: Estimating s offline from m prompts with n scored responses each: the estimate as a ratio to its value on the full pool of 100 prompts and 960 responses, as median [5th, 95th percentile] over 400 resamples, for Llama on AlpacaFarm scored by FsfairX.
Figure 5: The estimated CDF value F^x(R1) of the best of N1=80 Stage-1 rewards (shifted exponential) against its normalized rank Fx(R1) , in each of the 24 configurations of Section 4.1 (columns: language models; rows: reward model and dataset). Both axes use a logit scale, p↦log(p/(1−p)) , which spreads out values near 1 . Grey points: 3000 Stage-1 batches sampled at random from all 100 of the configuration’s prompts. Orange: the binned-means map g(⋅,80) of the debiased estimate, fitted on one half of those prompts. Dotted: the identity. g(⋅,80) falls below the identity at a value between 0.96 and 0.99 , depending on the configuration: when F^x(R1) is high, it overestimates Fx(R1) .
RMSE ( ×10−2 )
relative bias (%)
N1
plug-in
debiased
debiased, more inputs
predicted Beta
plug-in
debiased
debiased, more inputs
predicted Beta
2
14.901
14.894
14.629
14.394
−26
−26
−22
+7
5
10.022
10.013
9.628
9.488
−27
−26
−22
+2
10
6.417
5.763
5.485
5.433
−65
−20
−17
+2
20
3.341
3.047
2.965
2.929
−58
−17
−19
−3
40
1.690
1.561
1.532
1.522
−49
−15
−13
+1
Appendix
Table 7: Accuracy of the four estimates of the expected improvement EI(Fx(R1),N2) , with N2=N1 , averaged over the 24 configurations of Section 4.1 . RMSE ( ×10−2 ) against EI(Fx(R1),N2) , with Fx(R1) the normalized rank of R1 , lowest in bold; and, for an estimate m^(s1,N2) , the relative bias \E[m^(s1,N2)]/\E[EI(Fx(R1),N2)]−1 , in %. The regression-based estimates are fitted on half of a configuration’s prompts and scored on the other half, both ways round; RMSE is the root of the mean squared error over the 24 configurations.
Figure 6: The adaptive batch size, latency-aware policy using each of the four estimates of the expected improvement, batch sizes in Z={1,…,320} , averaged over the 24 configurations of Section 4.1 . Left: no latency cost ( γ=0 ). Right: the ray λlat=10λgen , at β=0.5 , cv=2 , ρ=1 . Top: the proportion of generations-equivalent cost C=N+γT saved at matched mean normalized reward rank, (CBoN−Cpolicy)/CBoN , against Best-of- N ’s generations-equivalent cost CBoN in log scale. (Points are joined in order of λgen , so where a policy’s mean normalized reward rank is not monotone in λgen , its curve turns back.) Bottom: V−VBoN⋆ , with VBoN⋆ the value of V of Best-of- N with its V -maximizing N , against λgen along the ray (log scale). Light blue diamonds: plug-in; grey triangles: debiased; pink crosses: debiased, more inputs; orange plus signs: predicted Beta (ours); black circles: oracle; dotted black: Best-of- N .
debiased
debiased, more inputs
predicted Beta
N1
plug-in
own
other
own
other
own
other
2
14.901
14.894
14.894
14.629
14.758
14.394
14.495
5
10.022
10.013
10.013
9.628
9.680
9.488
9.525
10
6.417
5.763
5.772
5.485
5.543
5.433
5.497
20
3.341
3.047
3.074
2.965
3.021
2.929
2.990
40
1.690
1.561
1.595
1.532
1.598
1.522
1.592
Appendix
Table 8: RMSE ( ×10−2 ) against EI(Fx(R1),N2) , with N2=N1 , of the plug-in, which has no fit, and of the three regression-based estimates of the expected improvement, over the 24 configurations of Section 4.1 . “Own”: fitted on half of the configuration’s prompts and scored on the other half, both ways round. “Other”: fitted on half of the prompts of another configuration that shares none of the configuration’s language model, reward model and dataset, for each of the six such configurations, and scored on half of the configuration’s prompts. RMSE is the root of the mean squared error over the 24 configurations, both prompt halves and, for “other”, the six configurations fitted on.
Figure 7: The bottom row of Figure 2 at each β∈{0,0.5,1} , also with γ=1 : proportion of generations-equivalent cost C=N+γT saved at matched mean normalized reward rank, (CBoN−Cpolicy)/CBoN , against Best-of- N ’s generations-equivalent cost CBoN (log scale), at γ=1 , 10 , 102 and 103 (rows) and β=0 , 0.5 and 1 (columns). cv=2 , ρ=1 , batch sizes in Z={1,…,320} , averaged over the 24 configurations of Section 4.1 . Points are joined in order of λgen , so where a policy’s mean normalized reward rank is not monotone in λgen , its curve turns back. Colours and line styles as in Figure 2 .
Figure 8: The top row of Figure 2 at each β∈{0,0.5,1} , also with γ=1 : mean normalized reward rank against generations-equivalent cost C=N+γT ( N , T : mean number of generations and mean total latency in seconds) (log scale) for the policies and settings of Figure 7 . Dotted black: Best-of- N .
Figure 9: The bottom row of Figure 2 at γ=10 in each of the 24 configurations of Section 4.1 : the proportion of generations-equivalent cost saved against Best-of- N ’s generations-equivalent cost CBoN (log scale), at β=0.5 , cv=2 , ρ=1 , batch sizes in Z={1,…,320} , with the predicted Beta; each panel uses its configuration’s own Best-of- N . Columns: language models; rows: reward model and dataset.
β=0.5
β=1
γ=0
γ=10
γ=102
γ=10
γ=102
dataset
RM
LM
unaware
aware
unaware
aware
unaware
aware
unaware
aware
AlpacaFarm
FsfairX
Llama
8.8
−1.9
1.6
−0.2
2.1
8.8
12.8
8.4
27.5
Gemma
11.2
0.3
3.4
0.0
2.9
11.4
15.1
11.1
29.1
Mistral
11.0
−0.7
2.9
−0.3
2.7
11.0
14.9
10.8
28.8
Qwen
8.1
−1.5
1.5
−0.2
2.2
8.1
12.5
8.1
27.3
Appendix
Table 9: Per-configuration results of Table 1 : proportion (%) of generations-equivalent cost saved at the reward of Best-of- N with N=40 in each of the 24 configurations of Section 4.1 (adaptive batch size policies, Z={1,…,320} , predicted Beta, at cv=2 and ρ=1 ). At γ=0 the two latency rules are one policy and β does not apply.
Figure 10: Proportion (%) of generations-equivalent cost C=N+γT saved at the reward of Best-of- N with N=40 , against the correlation ρ of logT1 and logT2 , at γ=10 and 102 (rows) and β=0 , 0.5 and 1 (columns). All policies choose the second batch size adaptively in Z={1,…,320} . Performance is averaged over the 24 configurations of Section 4.1 . Predicting T2 at the true ρ in filled markers, predicting as if ρ=1 in hollow markers; line styles are otherwise the same as in Figure 3 .
Figure 11: Heatmaps over the grid of the 31 geometrically spaced values of λgen∈[10−5,10−2] of Section 4.1 and 81 geometrically spaced values of λlat∈[10−8,100] for the latency-aware policy with adaptive batch sizes Z={1,…,320} , at β=0.5 , cv=2 , ρ=1 , averaged over the 24 configurations of Section 4.1 . Top row: mean number of generations. Middle row: mean latency (s). Bottom row: mean normalized reward rank of the returned response. Left column: our method , with the predicted Beta. Middle column: oracle variant. Right column: ours minus oracle.
Inference-time compute allocation decides where, when, and how much computation models spend during prediction to improve quality under resource limits.