acceptodds
Under review as a conference paper at ICLR 2027

Sequential Bayesian Evaluation of Large Language Model Behavior

Abstract

It is increasingly important to evaluate the characteristics of systems based on large language models (LLMs). Evaluations in this context often rely on a curated benchmark set of input prompts provided to the LLM, where the output for each prompt may be assigned a binary or ordinal score and the aggregation of scores across prompts is then used as a summary evaluation. In this paper, we develop a Bayesian approach for quantifying the uncertainty that arises in such evaluation metrics as a result of the stochasticity of the LLM-based systems; the same prompt may exhibit different outcomes on repeated runs. Our framework leads naturally to a sequential evaluation, in which we leverage the Bayesian model to preferentially select which prompts in the benchmark to use next, enabling more cost-effective LLM evaluations. We demonstrate this approach through four case studies: pairwise LLM preferences in interactive dialogue (MT-Bench), refusal rates on adversarial inputs (JailbreakBench), embodied agentic reasoning (ALFWorld), and agentic web-search Q&A (GAIA). Our results illustrate how a Bayesian approach can provide insightful uncertainty quantification about the behavior of blackbox LLM-based systems in a manner that is not accessible via deterministic or single-run evaluations.

Primary area:
datasets and benchmarks
Keywords:
Large Language Models, Evaluation, Agentic, Bayesian Methods, Uncertainty Quantification

Reviews

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

This work presents a Bayesian sequential evaluation method to address uncertainty caused by stochastic LLM-system behavior when the same benchmark prompt is evaluated repeatedly. It estimates each prompt's success probability with an independent Beta-Bernoulli posterior, propagates those posteriors to W_mean, W_min, and W>ν, and formulates prompt selection as a bandit problem whose reward is expected reduction in the variance of W>ν. Experiments show that a single greedy run can overstate reliable behavior; greedy and Thompson sampling generally reduce posterior variance and MAE faster than round-robin; and JailbreakBench at the 0.95 threshold is an exception because most harmful prompts are almost always refused.

Critical strengths
  • The paper makes within-prompt stochasticity directly useful for evaluation decisions. Instead of only attaching an interval to a benchmark mean, it estimates a posterior for each prompt and propagates it to W_mean, W_min, and W>ν. This supports reliability questions that a single mean cannot answer, such as whether a behavior is consistently above a threshold or whether the worst prompt rarely produces the desired behavior.

  • The adaptive design is supported by useful evidence and honest negative results. Across four behavior domains, greedy and Thompson sampling generally reduce posterior variance and MAE faster than round-robin; JailbreakBench at the 0.95 threshold is correctly identified as a case with little benefit. Threshold/prior sweeps, coverage checks, a two-system comparison, ordinal extensions, and released generations make the practical scope substantially easier to assess.

Critical weaknesses
  • The main experiments do not test whether the credible intervals are actually reliable. The sequential results show that adaptive sampling approaches the posterior computed from all stored generations, but that full-data posterior is not the true value of W. For the four main binary case studies, the paper does not report coverage or another ground-truth/held-out check showing that intervals for W_mean, W_min, or W>ν contain the true aggregate at their nominal rates. A synthetic calibration study or a larger held-out validation pool would make the uncertainty claims much stronger.

  • The efficiency claim is demonstrated in a narrow replay setting. Each benchmark evaluates essentially one system or pair. The agentic case studies use only 15 and 27 prompts, and the sequential experiments replay a fixed pool of 100 precomputed generations per prompt. The main comparison is with round-robin and uses the full stored-generation posterior as the primary MAE reference. Appendix C.3’s alternative references and Appendix D’s threshold sweeps are useful, but a smaller online study with additional systems and stronger adaptive or uncertainty-aware baselines would better establish practical robustness.

Questions for authors
  • How should the threshold ν and aggregate W be chosen before observing the data? The concern is that Section 3 derives the sequential reward specifically for W>ν, while Appendix D evaluates several thresholds; post-hoc inspection may require multiplicity control.

  • Can the main efficiency claim be tested in a smaller online study with additional systems and stronger baselines such as bootstrap, hierarchical Bayesian, or stratified allocation? This would address the replay setting in Appendix C.1, the full-data posterior reference in Appendix C.3, and the current one-system-per-domain scope more directly.

3 comments

We sincerely thank Reviewer aDKB for the positive feedback. We are especially glad you highlighted that our framework makes within-prompt stochasticity directly useful for evaluation decisions, and that our inclusion of various experiments makes the practical scope substantially easier to assess.

W1. The main experiments do not test whether the credible intervals are actually reliable

We now report coverage against known truths (Appendix C.5). The figures below are the share of runs in which the 90% credible interval contains the true value, over 1,000 runs.

  1. With θm\theta_m drawn from the prior, the intervals cover the truth in 91–97% of runs for W>νW_{>\nu}, 87–92% for WmeanW_{\text{mean}} and 88–92% for Wmin⁡W_{\min}. These ranges hold for greedy, Thompson sampling and round-robin, at every budget, and for the (M,ν)(M, \nu) of all four benchmarks. This is expected: our allocation depends only on outcomes already observed, so it does not enter the likelihood and the posterior is unaffected by it.

  2. The 90% intervals for W>νW_{>\nu} and Wmin⁡W_{\min} stay at or close to nominal coverage on truths matched to each benchmark. With θ∗_m\theta^*\_m drawn as in our response to i4CJ, coverage of W>νW_{>\nu} (%, range over the three algorithms) is:

Benchmark (model)5×M10×M20×M
MT-Bench85–8988–9291–94
JailbreakBench (Qwen2.5-7B)99–10097–10097–99
ALFWorld (gpt-5.4-mini)95–9696–9897–98
ALFWorld, M = 140 (Qwen2.5-7B)96–9995–9896–98
GAIA90–9593–9694–96

MT-Bench is the only case below nominal (85–89% at 5×M, 91–94% by 20×M). The Wmin⁡W_{\min} intervals cover the truth in 88–93% of runs on MT-Bench, ALFWorld, GAIA, and ALFWorld with Qwen2.5-7B at every budget from 2×M. The exception is JBB with gpt-4o-mini at ν=0.95\nu = 0.95, where 94 of 100 prompts are refused in every stored generation. There, the W>νW_{>\nu} intervals cover the truth in no run up to 20×M (they under-count the prompts that clear 0.95).

  1. The intervals also hold on held-out real generations, with no simulation. In each run, we split every prompt's stored generations in half, run greedy on one half, and check the posterior predictive 90% interval against the other half. From 2×M onward, it contains each prompt's held-out count in 92–97% of cases, and the held-out number of prompts above ν\nu in 87–100% of runs (MT-Bench, JailbreakBench with Qwen2.5-7B, and ALFWorld with Qwen2.5-7B, whose pools are large enough to split).

Together, these checks show that the W>νW_{>\nu} intervals cover the truth at the nominal rate under adaptive allocation, against known truths and against held-out generations.

W2.The efficiency claim is demonstrated in a narrow replay setting

Q2. Can the main efficiency claim be tested in a smaller online study with additional systems and stronger baselines

Please see our response to Reviewer i4CJ. In a new experiment with fresh draws from a known truth, with no stored pool and no WpostW_{\text{post}}, greedy saves 40–74% of the round-robin budget on five benchmark–model pairs, in line with the replay results (Appendix C.5, Table 3).

On an online study. In the known-truth experiment, each pull is a fresh draw from the prompt's true success probability, which is what a live query to the system returns. The true probabilities are drawn from the posterior given each prompt's stored generations, so the truth is known and realistic. This reproduces the conditions of an online study (fresh draws and an unlimited pool) while keeping the true answer known, on six benchmark–model pairs (the five in the table and JailbreakBench with gpt-4o-mini). Our ordinal LLM-as-judge study (Appendix G) already uses this design with the system's own probabilities, where we show that adaptive allocation saves 81–88% of the budget with 98–100% coverage (Dirichlet model).

On additional systems. The revision evaluates four systems on JailbreakBench (gpt-4o-mini, gpt-5.4-nano, Qwen2.5-7B, Qwen3.5-4B; Appendix B.2.1), adds a second model on all 140 ALFWorld valid_seen tasks (Appendix B.3.1), and extends GAIA from 27 questions to all 53 Level 1 questions.

On stronger baselines. We thank the reviewer for these suggestions. We ran all three suggested comparisons in the known-truth setting (Appendix C.5, Table 4). All rules are scored with the same posterior, so only the allocation differs. Budget to match round-robin's accuracy at the full budget:

Benchmark (model)Greedy (ours)Stratified (Neyman)Hierarchical (EB)BootstrapRound-robin
MT-Bench22×M>50×M>50×M>50×M50×M
JailbreakBench (Qwen2.5-7B)13×M>50×M>50×M>50×M50×M
ALFWorld (gpt-5.4-mini)12×M>20×M>20×M>20×M20×M
ALFWorld, M = 140 (Qwen2.5-7B)10×M17×M>20×M>20×M20×M
GAIA8×M20×M>20×M>20×M20×M
  • Stratified allocation saves budget on one of the five pairs (ALFWorld-Qwen, 17×M vs 20×M). Neyman allocation is designed to minimize the variance of the mean, not of a threshold count, which is why our reward is defined on the aggregate.

  • The bootstrap does not fit this problem. A prompt whose generations so far all agree has zero bootstrap uncertainty, so it is never sampled again, and its interval has zero width. Bootstrap intervals are also unreliable for a minimum (Wmin⁡W_{\min}) and are not justified when sample sizes depend on the data. Its MAE at 10×M is 2.1–3.1 times greedy's (MT-Bench, ALFWorld, GAIA). We may be misreading the suggestion. We would be glad to evaluate a specific bootstrap procedure if the reviewer has one in mind.

  • We read "hierarchical Bayesian" as partial pooling across prompts, i.e., relaxing our independence assumption, which we list in Section 5 as future work. A hierarchical prior extends our method rather than competing with it as a baseline. It changes the prior, not the method: our allocation rule and Monte Carlo aggregates apply under a hierarchical prior, with the reward computed by Monte Carlo. As a first check, allocating with a shared empirical-Bayes prior was less accurate than independent priors at 10×M on all six pairs (GAIA 1.89 vs 1.14, ALFWorld 0.96 vs 0.71). If the reviewer had a different model in mind, we would be glad to add it.

  • APT (Locatelli et al., 2016), which also targets W>νW_{>\nu}, is within 3×M of greedy on every pair (Appendix C.5; See our response to Reviewer i4CJ for more on this).

Q1. How should the threshold ν and aggregate W be chosen before observing the data?

We agree that ν\nu and WW should be fixed before data collection. They were fixed for all our experiments, and we have now stated this explicitly in Section 3.

Choosing ν\nu and WW: These are not tuning parameters; they define the evaluator’s specific question. For example, a safety team wanting to ensure harmful prompts are refused 95% of the time uses W>νW_{>\nu} with ν=0.95\nu = 0.95. Appendix D is strictly a sensitivity analysis, and not a selection step. We report all 25 benchmark and threshold configurations without cherry-picking. In fact, our main-paper values are not the most favorable: as reported in Section 4.3, ν=0.95\nu = 0.95 on JailbreakBench yields no sequential gain at all, while selecting ν=0.80\nu = 0.80 for JBB would result in 54% budget reduction (Appendix D). In a new JBB study (Appendix B.2.1) with Qwen2.5-7B-Instruct, which refuses far less often, greedy saves more than 68% of the round-robin budget at the same ν=0.95\nu = 0.95.

Multiplicity: Because the allocation rule depends only on the outcomes observed so far, the design is ignorable. The target ν\nu only dictates sampling efficiency, not inference validity. The posterior over θ\theta is the exact same function of the data regardless of the sampling target, meaning every aggregate (W>νW_{>\nu}, WmeanW_{\text{mean}}, WminW_{\text{min}}) is derived from that single valid posterior. An evaluator with several thresholds in mind can therefore report the joint posterior of ν↦W>ν\nu \mapsto W_{>\nu}, computed from the same posterior draws, as a simultaneous credible band, with no post-hoc correction. Because each Var(W>ν)\mathrm{Var}(W_{>\nu}) is a sum over prompts, a reward summed over several values of ν\nu would remain a per-prompt score;

We thank Reviewer aDKB for your constructive feedback, which has helped us substantially improve the paper.

As the author–reviewer discussion period ends soon, we wanted to ask whether you have any remaining questions or concerns. We would be happy to provide further clarification.

We hope our responses have addressed your concerns. If so, we would be grateful if you would consider updating your rating.

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

The paper models each prompt’s pass rate, (\theta_m), independently using a Beta–Binomial model and propagates per-prompt posterior uncertainty to three aggregate metrics: the threshold count (W_{>\nu}), whose posterior follows a Poisson binomial distribution; the mean; and the minimum. It then formulates evaluation-budget allocation as a multi-armed bandit problem, using the expected reduction in the posterior variance of (W_{>\nu}) as the reward, and compares greedy allocation, Thompson sampling, and round-robin sampling.

The problem is practically relevant, and the framework is transparent and reproducible. However, the technical contribution appears to be largely an application of established Bayesian estimation and adaptive sampling methods to LLM evaluation. The paper also leaves the inferential target unclear and does not adequately address several issues concerning cost, experimental design, and the interpretation of its results.

Critical strengths
  1. Practical relevance. LLM evaluations often overlook within-prompt stochasticity. Reducing the number of calls required for reliable evaluation addresses a genuine bottleneck, particularly for expensive agentic systems.

  2. Simplicity, transparency, and reproducibility. The conjugate model yields closed-form posterior updates. The public release of the code and all generated outputs allows the figures to be reproduced without additional API calls.

  3. Informative aggregate metrics. The MT-Bench example convincingly illustrates how (W_{\mathrm{mean}}\approx 0.5) can conceal a meaningful structure: the two models may each consistently outperform the other on different subsets of prompts.

Critical weaknesses
  1. Mainly based on existing work and missing baselines. The combination of independent Beta–Bernoulli posteriors and expected variance reduction closely resembles Ji et al. (2021), and the technical distinction beyond the LLM application is unclear. The paper also overlooks thresholding bandits (Locatelli et al., 2016) and active testing (Kossen et al., 2021). The authors should clarify the methodological contribution and include an appropriate baseline such as APT.

  2. Unclear practical cost advantage. Savings are measured against uniform repeated sampling rather than the common practice of one run per prompt. The reported budgets—approximately (8M) generations for GAIA and (35M) for MT-Bench—remain expensive, while independent priors prevent information sharing across prompts. Absolute API costs or runtime, and potential alternatives such as hierarchical models, should be discussed.

  3. Ambiguous inferential target. The model quantifies uncertainty on a fixed benchmark, but several claims imply generalization to a broader task population. For the former, novelty relative to existing methods is limited; for the latter, between-prompt sampling variability is omitted. Even infinitely many repetitions cannot eliminate uncertainty about unseen tasks. The authors should define the target explicitly and, if population-level inference is intended, account for both sources of variability and compare with Miller (2024).

  4. Overly broad characterization of frequentist methods. The claim that frequentist intervals require a fixed sample size overlooks anytime-valid confidence sequences, which accommodate data-dependent stopping and appropriately constructed adaptive sampling (e.g., Waudby-Smith & Ramdas, 2024). This claimed distinction should be revised.

  5. Mismatched estimands in Figure 1. A single-run success count and the number of prompts with (\theta_m>0.9) measure different quantities. Their discrepancy therefore does not establish that single-run evaluation overstates reliability. Comparing temperature-0 greedy decoding with temperature-1 sampling further conflates different policies. A fairer comparison would hold the policy and estimand fixed, such as comparing single-run and posterior estimates of (W_{\mathrm{mean}}).

  6. Evaluation against the same finite pool. Sequential sampling and the reference posterior (W_{\mathrm{post}}) use the same pre-generated outcomes, so convergence to zero MAE at pool exhaustion is built into the protocol. Figure 7 also suggests that some prompts reach the pool cap, potentially constraining greedy allocation. The authors should explain exhaustion handling, clarify the different sample counts across C.1, C.3, and Figure 1, and validate accuracy using an independent reference or known ground truth.

  7. Unclear justification for matched allocation. Appendix F suggests that unequal allocation contaminates system comparisons, despite the main text emphasizing valid Bayesian inference under adaptive allocation. Under a correctly specified model and ignorable allocation, matched allocation is not inherently required. Moreover, independent greedy outperforms joint greedy in selecting the better system ((91.8%) vs. (84.1%)). The authors should specify the intended benefit of matching, such as robustness to misspecification.

Minor concerns: In the expected-reward formula, (\gamma_k) appears to require correction to (\gamma_m). In (W=g(\theta_1,\ldots,\theta_m)) and the corresponding (r_1,\ldots,r_m) notation in Eq. (1), the final index should be (M). In Algorithm 1, line 9, (y_{m,j}) should apparently be (y_{\hat m,j}). The reference to “Section 5” in Appendix C.1 should be “Section 4.” The phrase “Figures 1 (bottom row) and 1 (middle row)” in Appendix G.2 is confusing and should be corrected. In the definition of (\gamma_{m,z}), (\alpha_m) and (\beta_m) denote current posterior parameters, whereas earlier they denote prior parameters. The notation should distinguish these explicitly. Figure 2 shows higher MAE for greedy allocation than for round-robin on GAIA at small budgets. This behavior deserves discussion.

Questions for authors

Please refer to the weakness.

6 comments

We thank Reviewer i4CJ for the detailed review. We are glad the reviewer found that our work addresses a genuine bottleneck in LLM evaluation, that the model is simple, transparent, and reproducible, and that our aggregate metrics are informative. In response, we clarified our contribution relative to prior work and added APT as a baseline, defined the inferential target, revised Figure 1 and our statement about frequentist methods, validated our results against a known ground truth, and reframed the two-system comparison. We address each point in detail below.

W1. Mainly based on existing work and missing baselines

We thank the reviewer for pointing us to these three works. Below we set our method against each one, report the requested APT baseline, and restate the contribution.

Ji et al. (2021). We agree that our acquisition rule shares its template with Ji et al. (i.e., Beta–Bernoulli posteriors and maximizing an expected variance reduction). We will state this explicitly. Our contribution is to carry this template over to stochastic LLM systems, which changes both the source of uncertainty and the quantity we infer:

  • Arms and uncertainty. In Ji et al. an arm is a group of inputs (e.g., a predicted class), and a pull labels one randomly drawn input whose prediction is deterministic. θg\theta_g is accuracy over a population of inputs. In our setting θm\theta_m belongs to a single prompt: it is the probability that a stochastic LLM system shows a behavior on that prompt. A pull is a fresh generation from the same prompt. The uncertainty we model, within-prompt stochasticity, does not exist in a deterministic classifier.

  • Target. Ji et al. reduce ∑gpgVar(θ^g)\sum_g p_g \mathrm{Var}(\hat{\theta}_g) or identify the least accurate group. We infer benchmark-level aggregates of the per-prompt probabilities: W>νW_{>\nu} (the number of prompts on which the system behaves with probability above ν\nu), Wmin⁡W_{\min} and WmeanW_{\text{mean}}. WmeanW_{\text{mean}} is the usual benchmark average for e.g. accuracy. The other two are new to stochastic systems. With deterministic outputs every θm\theta_m is 0 or 1, so W>νW_{>\nu} reduces to the number of correct prompts for every ν\nu, and Wmin⁡W_{\min} only records whether any prompt fails. Our reward is the expected reduction in Var(W>ν)\mathrm{Var}(W_{>\nu}), computed from its Poisson-binomial posterior. Ji et al. do not consider threshold-count aggregates.

We see this extension as practically important because repeated generation is how LLM systems are actually deployed, and it is where evaluation cost is highest.

Thresholding bandits (Locatelli et al., 2016). For one of our aggregates, W>νW_{>\nu}, our problem has a boundary case that coincides with the thresholding bandit problem. Because Var(W>ν)=∑mγm(1−γm)\mathrm{Var}(W_{>\nu}) = \sum_m \gamma_m(1-\gamma_m) with γm=P(θm≤ν)\gamma_m = P(\theta_m \le \nu), reducing it amounts to resolving which side of ν\nu each prompt falls on, and APT solves exactly that problem. APT returns on that set. It is frequentist: it returns a point estimate of the set of prompts with θ^m≥ν\hat{\theta}_m \geq \nu, with no distribution or interval for the count. It has no analogue for Wmin⁡W_{\min}, WmeanW_{\text{mean}}, ordinal outcomes, or the comparison of two systems, all of which our acquisition rule covers.

APT therefore fits inside our framework as one possible selection step, and we ran it that way. APT chooses the next prompt and our posterior scores the result, as in Section 4.3 (MAE of E[W>ν]\mathbb{E}[W_{>\nu}] against WpostW_{\text{post}}). We also added JailbreakBench with Qwen2.5-7B-Instruct. It refuses 44% of the time, so many of its prompts lie near ν=0.95\nu = 0.95.

Generations to reach MAE ≤0.5\leq 0.5 (×M\times M)Budget saved
BenchmarkGreedy (ours)APT, ϵ=0\epsilon=0APT, ϵ=0.1\epsilon=0.1Round-robinGreedy vs. round-robin
MT-Bench232822>50>54%
JailbreakBench (Qwen2.5-7B)162918>50>68%
ALFWorld566944%
GAIA7771553%
JailbreakBench (GPT-4o-mini)>50>50>50>50—

Table R2. The smallest budget at which the MAE falls to 0.5 and stays there. >50: not reached within 50×M50 \times M, so the saving is a lower bound. With GPT-4o-mini, no rule reaches the target at ν=0.95\nu = 0.95, because nearly every prompt is refused with probability close to 1 (Section 4.3).

Our rule saves 44% to more than 68% of the round-robin budget. On this boundary case, it stays within 1×M1 \times M of APT's best setting on every benchmark. Greedy also does not need APT's precision parameter: without tuning (ϵ=0\epsilon = 0), APT needs nearly twice greedy's budget (29×M29 \times M against 16×M16 \times M on Qwen2.5-7B). This parity is what the boundary case predicts, since where the two problems coincide, both rules sample the prompts whose rate is near ν\nu. APT does not provide what our method adds: a posterior over the benchmark-level aggregate, and an acquisition rule that extends beyond threshold counts. Appendix C.4 gives the details.

Active testing (Kossen et al., 2021). Active testing chooses which test inputs to label, each at most once. It corrects the resulting selection bias with an importance-weighted estimator (LURE) of a mean loss. This does not transfer to our problem, for three reasons:

  1. We spend the budget on repeated generations from the same prompt, whereas active testing labels each input at most once
  2. W>νW_{>\nu} and Wmin⁡W_{\min} are nonlinear in θm\theta_m. Finitely many Bernoulli draws admit no unbiased estimator of I(θm>ν)\mathbb{I}(\theta_m > \nu), so LURE cannot target these aggregates.
  3. Its acquisition rule needs a surrogate model of the loss, whereas we treat the system as a black box.

The two methods are complementary: when MM is too large to run every prompt, active testing can select the prompts, and our method can allocate generations among them.

With this in mind, we restate our contribution:

  1. A Bayesian model of within-prompt stochasticity in LLM and agentic systems, whose posterior carries through to benchmark-level aggregates (threshold counts, worst case, mean). Under the same sampling policy, a single temperature-1 run’s 90% range for W_mean is 3.6–6.7 times wider than the posterior’s 90% credible interval on all four benchmarks. Greedy decoding, the most common single-run practice, falls outside the 95% credible interval on three of four benchmarks (Section 4.2).
  2. An acquisition rule that targets the variance of the reported aggregate. It extends to comparing two systems under one shared budget with identical per-prompt pull counts (Appendix F), and to ordinal outcomes (Appendix G).
  3. Evidence from four benchmarks, two of them agentic, that this allocation saves 44% to more than 68% of the generation budget relative to round-robin, and performs as well as a dedicated thresholding bandit.

W2 Unclear practical cost advantage

Practical cost. We respectfully disagree with the premise. Our study exists to measure within-prompt uncertainty. One generation per prompt cannot measure it. With nm=1n_m = 1, each θm\theta_m is seen through a single Bernoulli draw. The data then cannot separate W>νW_{>\nu} from sampling noise, so they say nothing about how uncertain the estimate is. Single-run evaluation is therefore not a cheaper version of our method. It answers a different question, and the number it reports has unknown error. The fair baseline is one that estimates the same quantity, which is uniform repeated sampling. Against that baseline, greedy allocation reaches the same accuracy (MAE ≤ 0.5 prompts against WpostW_{\text{post}}) with 53% fewer generations on GAIA (7×M vs. 15×M) and 44% fewer on ALFWorld (5×M vs. 9×M). On MT-Bench, round-robin does not reach that accuracy within 50×M. See Table R2

Absolute budget. These budgets are the price of a stated accuracy target, not the price of using the framework. The posterior is defined at every budget, so a practitioner can stop at 1×M or 2×M and still report the remaining uncertainty. By 2×M, greedy has sampled every prompt on three of the four benchmarks (See Table 7 in the paper).

Independent priors. Independence is a stated limitation. The acquisition rule needs only a posterior for each prompt, so hierarchical or empirical-Bayes priors that share information across prompts work in the same framework, with the reward computed by Monte Carlo. They complement adaptive allocation rather than replace it.

W3 Ambiguous inferential target

Our target is the fixed benchmark. W=g(θ1,…,θM)W = g(\theta_1,\dots,\theta_M) is defined over the MM benchmark prompts, and every posterior, reward, and accuracy result in the paper refers to that set. We make no population-level claim. We now define the target explicitly in §2.

This is how benchmarks are used in practice. Leaderboards, safety audits on JailbreakBench, and regression tests all report a score on a fixed prompt set. In each case, the question is how much that score would change if the same system were run again. Between-prompt sampling does not enter that question. Within-prompt variability is the whole of the uncertainty, and repeated generation does reduce it.

Relation to Miller (2024). Miller targets a super-population of questions and splits the variance of the mean score into a between-question term and a within-question term: (Var(x)+E[σi2]/K)/n(\mathrm{Var}(x) + \mathbb{E}[\sigma_i^2]/K)/n. On a fixed benchmark, the questions are not resampled, so the between-question term does not contribute to the uncertainty, and only the within-question term remains. That remaining term is what we estimate. Miller reduces it by sampling every question the same number of times KK. We go beyond that in two ways:

  • We give posteriors for W>νW_{>\nu} (exactly, as a Poisson binomial) and Wmin⁡W_{\min}. Miller's standard errors cover means only.
  • We choose the number of generations per prompt, nmn_m, adaptively, so prompts get unequal budgets.

Population-level inference would add Miller's Var(x)\mathrm{Var}(x) term, which is outside our scope.

W4 Frequentist methods can handle adaptive sampling too.

Thanks for raising this and for the pointer to Waudby-Smith & Ramdas (2024) [1], which is relevant to our setting. Our statement wasn’t meant to say that frequentist intervals in general require a fixed sample size. It referred only to the two approaches we cite, Miller (2024) and Scholten et al. (2025), both of which use a fixed number of generations per prompt. We agree the wording could be read as a general Bayesian–frequentist contrast, and that anytime-valid confidence sequences remain valid under data-dependent stopping and suitably constructed adaptive sampling. Our work differs in focus: [1] constructs confidence sequences for a single bounded mean, whereas we model many prompts jointly, obtain the full distribution of aggregate metrics (e.g., worst-case probability, threshold counts) directly from the posterior, and use it to decide which prompt to sample next. We have revised the Introduction accordingly and now cite [1].

[1]: Waudby-Smith, I., & Ramdas, A. (2024). Estimating means of bounded random variables by betting. Journal of the Royal Statistical Society Series B: Statistical Methodology, 86(1), 1–27. https://doi.org/10.1093/jrsssb/qkad009

W5 Mismatched estimands in Figure 1.

We thank the reviewer for this careful comment. We agree that the original Figure 1 mixed two decoding policies, and we have revised the figure.

We removed the greedy-decoding line from Figure 1 and now report greedy values in the text only. Each panel instead shows a gray band: the 90% range of the estimate from a single temperature-1 run, drawn from the same nn generations per prompt that the posterior uses. We revised the appendix batch figures in the same way. We keep the greedy values in the text (Section 4.2) because greedy decoding is common evaluation practice, while deployed systems typically sample stochastically; the comparison shows how far that practice can be from deployed behavior.

As the reviewer suggests, the middle row now compares single-run and posterior estimates of WmeanW_{\text{mean}} under one policy. Although a single run is unbiased, on our four benchmarks, its 90% range is 3.6 to 6.7 times wider than the posterior's 90% credible interval. The advantage of our method is that a posterior reports this uncertainty explicitly, while a single run cannot.

We agree that the pass count and W>νW_{>\nu} are different quantities, and this difference is what the comparison shows. One run estimates each θm\theta_m as 0 or 1, so the pass count is the only estimate of W>νW_{>\nu} it can give. It cannot distinguish a prompt with θm=0.6\theta_m = 0.6 from one with θm=0.99\theta_m = 0.99. On GAIA, a temperature-1 run reports 22 to 30 of 53 questions passed, whereas the posterior mode of W>0.9W_{>0.9} is 12. Threshold and worst-case aggregates can only be estimated from repeated generations, which is what our framework provides.

Our sequential algorithm keeps these repeated generations affordable. On the agentic benchmarks (ALFWorld and GAIA), it reaches a mean absolute error of 0.5 in W>νW_{>\nu} with 44–53% fewer generations than uniform sampling (Table R2 and Section 4.3).

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

This paper proposes a Bayesian framework for quantifying within-prompt uncertainty in LLM evaluation that arises from stochastic generation. Each prompt's probability of exhibiting a binary behavior is given an independent Beta prior and updated from repeated runs. The resulting uncertainty is propagated to benchmark-level aggregates. The authors then cast evaluation as a sequential allocation problem, choosing the next prompt to query by maximizing the one-step expected reduction in posterior variance. Across four benchmarks, they demonstrate how their method can provide uncertainty quantification for the behavior of LLM-based systems.

Critical strengths
  1. Well-motivated and clearly presented. The paper targets a real and under-explored gap in LLM evaluation: the same prompt can yield different generations across repeated runs, and the naive method, repeating N times is costly. The methodology is clearly formulated.
  2. Extensive analysis. The experiments span four different benchmarks and are complemented by a broad set of supporting evidence.
Critical weaknesses
  1. Each benchmark evaluates a single OpenAI model and a different model is used for each benchmark. It is hard to separate the effect of the method from the particular model-benchmarking pairing. It would be good to test on more models per benchmark.
Questions for authors
  1. How were the 15 ALFWorld tasks and the 27 GAIA questions selected? How would the results change on the full split?
  2. GPT 4o mini refuses nearly all prompts, which may not be the best model to demonstrate the effectiveness. Have we tried other models with less safety alignment?
3 comments

We sincerely thank Reviewer 8oTn for the positive feedback and for highlighting that our methodology is clearly formulated and targets a real and under-explored gap regarding the cost of evaluating LLM stochasticity. We are also glad you found the presentation clear and the analysis across the four benchmarks extensive.

W1: It is hard to separate the effect of the method from the particular model-benchmarking pairing.

We thank the reviewer for this suggestion. Our paper presents a framework for quantifying uncertainty in LLM evaluation. We agree, though, that the effect of the method should be separated from any particular model–benchmark pairing. We have therefore added experiments with three new models on JailbreakBench (GPT-5.4-nano, Qwen3.5-4B and Qwen2.5-7B) and with Qwen2.5-7B on all 140 ALFWorld valid_seen tasks. We also extended GAIA to the full Level 1 validation split (see our next response).

Across these models, the gain from adaptive allocation depends on the model's behavior, not on the benchmark. On a single benchmark, JailbreakBench, adaptive allocation gives no gain for the three models that refuse almost every prompt. It gives a large gain for Qwen2.5-7B, whose refusal behavior varies within prompts (likely reflecting weaker safety alignment). Wherever prompts have uncertain behavior near the threshold ν\nu, greedy allocation reaches the target accuracy with much less budget than round-robin:

BenchmarkModelMMBehavior rateGreedyRound-robinBudget saved
JailbreakBenchGPT-4o-mini (paper)10097.3% refusal>50>50>50>50–
JailbreakBenchGPT-5.4-nano10098.2% refusal>50>50>50>50–
JailbreakBenchQwen3.5-4B10097.0% refusal>50>50>50>50–
JailbreakBenchQwen2.5-7B10044.3% refusal16>50>50>68%
ALFWorldGPT-5.4-mini (paper)155944%
ALFWorldQwen2.5-7B14036.5% success9>20>20>55%
GAIAGPT-5.4-nano (original)2781443%
GAIAGPT-5.4-nano5371553%

Table R1: Budget (in multiples of MM) at which E[W>ν]\mathbb{E}[W_{>\nu}] reaches an MAE of 0.5 and stays there, using the criterion of Section 4.3, averaged over 1,000 runs.

The ALFWorld and GAIA results are now in the revised paper (Section 4 and Appendix B.3.1). We have added the additional JailbreakBench models to Appendix B.2.1.

Q1. How were the 15 ALFWorld tasks and the 27 GAIA questions selected?

We thank the reviewer for raising this. The revised paper now evaluates the full splits, and our conclusions still hold.

ALFWorld. We drew the 15 tasks from the valid_seen split so that all six ALFWorld task types are covered, with two or three tasks per type. To test the full split, we ran Qwen2.5-7B on all 140 tasks with 50 generations each (7,000 episodes). The results hold at this scale. At 10×M10 \times M, Var(W>ν)\mathrm{Var}(W_{>\nu}) is 1.96 under greedy against 5.08 under round-robin. Greedy reaches the target MAE by 9×M9 \times M, and round-robin does not reach it within 20×M20 \times M (Appendix B.3.1).

GAIA. The original 27 questions were a random subset of the 53 Level 1 validation questions. We have since evaluated the same model on the remaining 26, and the main paper now reports GAIA on all 53 Level 1 validation questions (Figure 1). On the full split, the budget saved by greedy rises from 43% to 53% (7×M7 \times M against 15×M15 \times M). Across thresholds ν∈[0.5,0.95]\nu \in [0.5, 0.95], greedy saves 47–60% (Appendix D). The original subset therefore did not inflate our results.

Q2. For JailbreakBench, GPT 4o mini refuses nearly all prompts…Have we tried other models with less safety alignment?

We agree that GPT-4o-mini is not the best model to show our method’s effect. GPT-4o-mini refuses 97.3% of generations, so at ν=0.95\nu = 0.95 almost every prompt behaves the same way, and we report this as a negative result in Section 4.3. Following the reviewer's suggestion, we added Qwen2.5-7B, a less safety-aligned model that refuses 44.3% of generations, with 26 of the 100 prompts having refusal rates in [0.7,1)[0.7, 1). On this model, greedy reaches the target MAE at 16×M16 \times M, while round-robin does not reach it within 50×M50 \times M (a saving above 68%), and Var(W>ν)\mathrm{Var}(W_{>\nu}) is 2.1× lower at 10×M10 \times M. GPT-5.4-nano (98.2%) and Qwen3.5-4B (97.0%) refuse about as consistently as GPT-4o-mini, and, like it, show no gain at ν=0.95\nu = 0.95 (Table R1).

These results indicate that the GPT-4o-mini JailbreakBench result comes from a strict threshold, not from the benchmark or the method. When there is little within-prompt uncertainty, there is little for adaptive allocation to reduce. We note that we chose ν=0.95\nu = 0.95 because practitioners typically need near-certain refusal on harmful prompts, but this strict threshold is the hardest case for our method: even for GPT-4o-mini, any ν≤0.8\nu \le 0.8 lets greedy save 54–84% of the round-robin budget (Appendix D).

Thanks the authors for the additional experiment results. My concerns have been addressed. I remain my positive score.

Comments on the paper

1 comment

We thank the reviewers for their constructive feedback and are glad they recognized the practical relevance of the problem (8oTn, i4CJ), the clear presentation (8oTn, i4CJ), the extensive and honest evaluation (8oTn, aDKB), and the informative aggregate metrics (i4CJ, aDKB). The main points we addressed are:

More models and full splits [8oTn, aDKB]

We added three JailbreakBench models, a second model on all 140 ALFWorld tasks, and all 53 GAIA Level 1 questions (App. B.2.1, B.3.1, Figure 2). Gains depend on whether prompts are uncertain near the threshold, and are independent of the choice of benchmark or model.

Positioning and baselines [i4CJ, aDKB]

We clarified our contribution relative to prior work and added Anytime Parameter-free Thresholding (APT), stratified, hierarchical, and bootstrap baselines (App. C.4, C.5). Greedy matches APT without tuning and outperforms the rest across benchmarks and models.

Known-truth validation [i4CJ, aDKB]

With fresh draws from known success rates, greedy saves 40–74% of the round-robin budget, and the credible intervals stay close to nominal coverage (App. C.5).

Clarifications [i4CJ, aDKB]

We defined the inferential target, revised our statement about frequentist methods and Figure 1, reframed the two-system comparison (App. F), and clarified how ν\nu is chosen.

Details are in the revised paper, with new content marked in blue.

We hope these revisions address the reviewers’ concerns and would be grateful if they are taken into account in the final assessment.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.