Paper deep dive
Risk-Aware Adaptive Evaluation: Finding High-Impact Failures Under Limited Budgets
Priyanath Maji, Spandan Ghose Chowdhury
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 10/4/2026, 3:33:36 AM
Summary
This paper addresses the high cost of evaluating stochastic interactive agents by formulating evaluation as a sequential resource allocation problem. The authors propose a risk-aware contextual Thompson Sampling policy that prioritizes scenarios based on pre-execution context vectors and fixed impact scores to maximize the discovery of high-impact failures under limited trial budgets. Using offline replay on 70 airline scenarios from τ-bench, the method significantly outperforms uniform allocation, recovering 86% of impact-weighted failures at a small budget (50 trials) compared to 25% for uniform sampling.
Entities (6)
Relation Signals (5)
Contextual Thompson Sampling → evaluatedon → τ-Bench
confidence 98% · test it by offline replay over 70 τ-bench airline scenarios
Contextual Thompson Sampling → achieves → 86% of Oracle Performance
confidence 95% · recovers 86% of the impact-weighted failures an oracle could find
Contextual Thompson Sampling → outperforms → Uniform Allocation
confidence 95% · with only 50 trials... the policy recovers 86% of the impact-weighted failures an oracle could find, compared to 25% for uniform allocation.
Contextual Thompson Sampling → uses → Impact Score
confidence 95% · combines a pre-execution scenario context vector and a fixed impact score with the failure outcomes observed during evaluation
τ-bench → generatedby → GPT-4o
confidence 90% · Trial outcomes are generated with a GPT-4o tool-calling agent
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Evaluating interactive agents is expensive. Agent behavior is stochastic, so reliability must be measured over repeated trials, but failures are rare and differ widely in how much they matter. Standard benchmarks spend this budget uniformly: a read-only lookup is sampled as often as an irreversible payment action. We instead formulate evaluation as a sequential allocation problem. Given a fixed trial budget and a set of scenarios whose failure behavior is unknown, which scenarios should be run, and run again? We propose a risk-aware contextual Thompson Sampling policy that combines a pre-execution scenario context vector and a fixed impact score with the failure outcomes observed during evaluation, and we test it by offline replay over 70 $\tau$-bench airline scenarios and 824 recorded trials. Our main result is at the smallest budget: with only 50 trials ($6\%$ of the corpus), the policy recovers $86\%$ of the impact-weighted failures an oracle could find, compared to $25\%$ for uniform allocation. It discovers $3.5\times$ more impact-weighted failures (215.4 vs. 62.2) with the same number of trials, delivers $5\times$ the discovery per dollar, and cuts the budget wasted on scenarios that never fail from $34\%$ to $2.8\%$. The rest of our analysis demonstrates and qualifies this result: a budget sweep shows the advantage shrinks as the budget approaches the corpus size, and paired significance tests show that scenario context helps mainly at small budgets while posterior-based exploration helps at moderate ones. Risk-aware adaptive allocation therefore helps most exactly where evaluation budget is scarcest.
Tags
Links
- Source: https://arxiv.org/abs/2609.38914v1
- Canonical: https://arxiv.org/abs/2609.38914v1
Trouble viewing inline? Open PDF directly →
Full Text
76,710 characters extracted from source content.
Expand or collapse full text
Risk-Aware Adaptive Evaluation: Finding High-Impact Failures Under Limited Budgets Priyanath Maji Affiliation: Georgia Institute of Technology Affiliation: Atlanta, GA 30332 Email: pmaji3@gatech.edu Spandan Ghose Chowdhury Affiliation: Georgia Institute of Technology Affiliation: Atlanta, GA 30332 Email: spandan_gc@gatech.edu Abstract Evaluating interactive agents is expensive. Agent behavior is stochastic, so reliability must be measured over repeated trials, but failures are rare and differ widely in how much they matter. Standard benchmarks spend this budget uniformly: a read-only lookup is sampled as often as an irreversible payment action. We instead formulate evaluation as a sequential allocation problem. Given a fixed trial budget and a set of scenarios whose failure behavior is unknown, which scenarios should be run, and run again? We propose a risk-aware contextual Thompson Sampling policy that combines a pre-execution scenario context vector and a fixed impact score with the failure outcomes observed during evaluation, and we test it by offline replay over 70 τ-bench airline scenarios and 824 recorded trials. Our main result is at the smallest budget: with only 50 trials (6%6\% of the corpus), the policy recovers 86%86\% of the impact-weighted failures an oracle could find, compared to 25%25\% for uniform allocation. It discovers 3.5×3.5× more impact-weighted failures (215.4 vs. 62.2) with the same number of trials, delivers 5×5× the discovery per dollar, and cuts the budget wasted on scenarios that never fail from 34%34\% to 2.8%2.8\%. The rest of our analysis demonstrates and qualifies this result: a budget sweep shows the advantage shrinks as the budget approaches the corpus size, and paired significance tests show that scenario context helps mainly at small budgets while posterior-based exploration helps at moderate ones. Risk-aware adaptive allocation therefore helps most exactly where evaluation budget is scarcest. 1 Introduction Large language model (LLM) agents increasingly perform multi-step interactive tasks that involve tool use, changes to environment state, domain policy constraints, and direct interaction with users. Benchmarks such as τ-bench Yao et al. (2025) and τ2τ^2-bench Barres et al. (2026) have shown that evaluating these agents requires more than checking a final answer: behavior must be judged over full trajectories, including tool execution, policy adherence, and state consistency. τ-bench also shows that state-of-the-art function-calling agents are substantially inconsistent across repeated runs of the same scenario. Reliability, not single-run success, is the right object of measurement. This view has a direct consequence for cost. If behavior is stochastic, one trial per scenario is a poor estimate of failure, so a benchmark must repeat trials. But repeating trials uniformly wastes budget, because scenarios differ along two independent axes. They differ in how often they fail: in our corpus, 24 of 70 scenarios never fail in any observed trial. They also differ in what a failure means: a failed read-only lookup and a failed irreversible payment action are not equally important, yet uniform sampling treats them identically. As evaluation increasingly relies on repeated, costly trials against live tool-calling environments and LLM-based user simulators, this waste turns directly into evaluation cost. Prior work on efficiency in agentic systems has mostly optimized the agent’s computation rather than the evaluator’s allocation of trials, for example by optimizing multi-agent execution graphs Zhuge et al. (2024) or pruning redundant agents and communication Wang et al. (2025b). These methods reduce the cost of a single execution. We explore a complementary question: how many executions of which scenarios are worth running at all? This work. We frame interactive-agent evaluation as a sequential resource-allocation problem. Given a fixed budget and a corpus of scenarios with unknown failure behavior, we examine which scenarios should be executed, and re-executed, to uncover as many consequential failures as possible. We build on Thompson Sampling Thompson (1933), a Bayesian bandit strategy with well-understood regret behavior Agrawal and Goyal (2012); Russo et al. (2018), extended with scenario-level context Agrawal and Goyal (2013). Allocation is then informed both by properties known before a scenario is ever executed (whether it involves payment, irreversible actions, or policy constraints) and by outcomes observed during evaluation. Unlike a standard bandit, the goal is not reward from an environment but the discovery of impact-weighted failures under a resource constraint: each scenario is a source of information about agent reliability. Main result. Our central finding concerns the small-budget regime: the setting where an agent is re-evaluated after every model, prompt, or policy change, so each decision can afford only a small slice of the corpus rather than many full passes Huang (2026). At a budget of 50 trials (6%6\% of the corpus), contextual Thompson Sampling recovers 86.1%86.1\% of the impact-weighted failure discovery an oracle could achieve, against 24.9%24.9\% for uniform allocation. Paired, Holm-corrected tests over 30 shared-seed replicates decompose where this advantage comes from: pre-execution scenario context is what wins the cold start (beating the arm-only variant at B≤100B≤ 100, pHolm<0.005p_Holm<0.005), while posterior-based exploration takes over at moderate budgets (beating the static risk-aware heuristic at B=300B=300–500500, pHolm<10−8p_Holm<10^-8). Both effects, and the advantage itself, shrink as the budget grows toward the corpus size. Contributions. (1) Formulation: we cast interactive-agent evaluation as a risk-aware sequential allocation problem that separates fixed, pre-execution quantities (context vector ix_i, impact score IiI_i) from stochastic per-trial observations (failure outcome Fi,tF_i,t, resource use i,tR_i,t), with impact-weighted failure discovery as the objective. (2) Method: we instantiate this as a contextual, risk-aware Thompson Sampling policy and compare it against uniform, random, failure-rate, and static risk-aware baselines and an oracle upper bound. (3) Analysis: with paired, Holm-corrected tests we identify where context and posterior-based exploration each help, not just whether they help. (4) Cost accounting: we report discovery per dollar of measured evaluation cost, not just per trial. Hypotheses. We test four claims. H1 (Adaptivity): under a fixed budget, adaptive allocation discovers more impact-weighted failures than uniform allocation. H2 (Context, budget-dependent): Thompson Sampling using observed outcomes, impact, and (in its contextual variant) pre-execution features ix_i allocates more efficiently than non-adaptive allocation, though not necessarily at every budget. H3 (Concentration): as trials accumulate, adaptive allocation increasingly avoids scenarios that show no evidence of failure while still exploring uncertain ones. H4 (Cost efficiency): adaptive allocation discovers more impact-weighted failures per unit of measured cost, especially at small budgets. 2 Related Work Interactive agent benchmarks and reliability. AgentBench Liu et al. (2024) established the need to evaluate language models as agents in interactive environments rather than through static question answering. Later benchmarks extended this to web-based multi-step tasks Zhou et al. (2024), large-scale tool use over real APIs Qin et al. (2024), and complex multi-step tool use over live MCP servers Wang et al. (2025a). τ-bench Yao et al. (2025) is closest to our setting: it evaluates tool-agent-user interaction under policy constraints and stateful environments, and its PasskPass^k metric measures reliability across repeated trials rather than single-run correctness; τ2τ^2-bench Barres et al. (2026) extends this to dual-control environments. Follow-up studies confirm this variance is real and large: Mustahsan et al. Mustahsan et al. (2025) quantify within-task inconsistency with intraclass correlation, Bjarnason et al. Bjarnason et al. (2026) show by replay that single-run pass@1 on SWE-Bench-Verified moves by 2 to 6 points depending on which run is observed even at temperature 0, and Gonzalez-Pumariega et al. Gonzalez-Pumariega et al. (2026) reach the same conclusion for computer-use agents. Other work enriches what each trajectory is scored on: TRAJECT-Bench He et al. (2026) adds trajectory-level diagnostics beyond final success, and Cao et al. Cao et al. (2026) show agents can reach correct final states through flawed procedures, so failures differ in kind and severity; we likewise extract operational signals (tool calls, turns, trajectory length, cost) from each trajectory. All of these protocols, however, execute a predetermined, uniform trial schedule; even Huang Huang (2026), who asks how many tasks a benchmark needs for a stable decision, works under uniform allocation. We formulate the schedule itself as the thing to optimize. Sequential allocation and Thompson Sampling. Our problem is a multi-armed bandit: the evaluator picks a scenario, observes its outcome, and uses that to inform the next pick. Thompson Sampling Thompson (1933) keeps a posterior over each arm’s unknown parameter and samples from it, balancing exploration and exploitation; its finite-time regret is well understood Agrawal and Goyal (2012); Russo et al. (2018), and Agrawal and Goyal Agrawal and Goyal (2013) extend it to contextual bandits with linear payoffs, the mechanism we adapt for pre-execution features ix_i. Bastani et al. Bastani et al. (2021) show that informative context can remove much of the need for exploration, consistent with our finding that context matters most in the cold start, and Riquelme et al. Riquelme et al. (2018) show that practical performance depends on the quality of the posterior approximation. Because our failure outcome is binary, the contextual version is most closely related to generalized linear bandits Filippi et al. (2010), fully Bayesian logistic Thompson Sampling via Pólya-Gamma augmentation Dumitrascu et al. (2018), and neural variants Zhang et al. (2020); extensions handle partially observable context Park and Faradonbeh (2024) and parallel pulls Karbasi et al. (2021). We use a simpler empirical-Bayes approximation, a lightweight choice at our corpus scale (N=70N=70); a fully Bayesian generalized linear bandit is the natural choice at much larger scenario counts. Budget-constrained discovery elsewhere. The problem of splitting a finite execution budget to find rare, costly failures is well studied outside agent evaluation. In software security, greybox fuzzers allocate executions across candidate test inputs to maximize bug discovery: Woo et al. Woo et al. (2013) first cast seed scheduling as a multi-armed bandit, and EcoFuzz Yue et al. (2020) models it adversarially to reduce wasted effort on well-explored inputs. In rare-event simulation and structural reliability, adaptive importance sampling and adaptive stratified sampling concentrate simulation effort in high-risk regions and avoid empty strata Geyer et al. (2019); Song and Kawai (2022); Pieraccini and Vanzan (2025), and related work replaces uniform sampling with learned non-uniform sampling when many rare network threats must be simulated at once Liu et al. (2023). None of these methods study LLM agents, but they are the strongest precedent for our claim that rare, heterogeneous, high-impact failures call for adaptive allocation rather than uniform budgeting. The objective also matters: for estimating mean accuracy under a fixed budget, spreading budget across more items with fewer trials each can be the variance-optimal choice Mustahsan et al. (2025). Our objective is different, discovery of impact-weighted failures, and that is where concentration pays. Two further things separate our setting from this work. First, we maximize discovered failures weighted by consequence, not environmental reward, an objective closer to active testing than to online decision-making. Second, each scenario’s impact IiI_i is known before execution while its failure outcome Fi,tF_i,t is observed only after, so our formulation separates a fixed notion of consequence from an adaptively estimated notion of likelihood, a distinction that does not arise when an arm’s value is fully determined by its reward distribution. 3 Method 3.1 Problem Formulation Let =s1,…,sNS=\s_1,…,s_N\ be a set of evaluation scenarios. Each scenario is a complete interactive task specification: a user objective, an initial environment state, applicable policy constraints, and a ground-truth reference action sequence. Each scenario carries a fixed context vector i∈ℝdx_i ^d, d=17d=17, extracted statically from the task definition (its reference action sequence and natural-language instruction), never from an observed outcome. This separation is deliberate: ix_i must be available before a scenario’s first trial is selected, and conditioning it on execution results would leak outcome information into the allocation policy. The features are eight binary task-structure indicators (requires_search, requires_mutation, requires_confirmation, has_payment, date_change, cabin_change, multi_segment, optimization_required), a passenger count and single-passenger indicator, membership- and insurance-sensitivity indicators, a complexity score and expected interaction horizon, an irreversible-action indicator, a policy-constraint indicator, and a scalar ambiguity score derived from instruction keywords. Three features (membership_sensitive, complexity_score, expected_horizon) are constant in this corpus; we keep them for interface stability, and all variance-based analysis should be read against the 14 active features. Each trial t of scenario sis_i produces a trajectory τi,t=(s0,a1,o1,…,aT,oT) _i,t=(s_0,a_1,o_1,…,a_T,o_T), where a is an agent action or tool call and o the resulting observation. Because both the agent and the simulated user are stochastic, repeated trials of the same scenario give different trajectories and outcomes. From each trajectory we obtain a binary failure indicator Fi,t∈0,1F_i,t∈\0,1\, determined by comparing the realized outcome against the ground-truth reference, and a resource vector i,t=[Ri,ttools,Ri,tturns,Ri,ttraj,Ri,tcost]R_i,t=[R^tools_i,t,R^turns_i,t,R^traj_i,t,R^cost_i,t] recording tool calls, conversational turns, trajectory length, and measured monetary cost. Each scenario also carries a fixed impact score IiI_i, giving the observed failure-impact signal Yi,t=IiFi,tY_i,t=I_iF_i,t. Repeated trials share ix_i and IiI_i (both fixed and known before execution) while Fi,tF_i,t, i,tR_i,t, and Yi,tY_i,t vary from trial to trial. Given a trial budget B, the evaluator sequentially selects scenarios A1,…,ABA_1,…,A_B, observes (FAt,t,At,t)(F_A_t,t,R_A_t,t) after each selection, and uses the history ℋt−1H_t-1 to inform later choices, At∼π(∣ℋt−1)A_t π(S _t-1). The objective is maxππ[∑t=1BIAtFAt,t]. _π\ E_π\! [ _t=1^BI_A_tF_A_t,t ]. (1) 3.2 Impact Score The impact score is a fixed, rule-based function of a scenario’s context features. It reflects the consequence of a failure, not its likelihood: Ii=5,irreversible action expected,4,mutation and (payment or confirmation required),3,mutation, no payment or confirmation,1,informational / read-only.I_i= cases5,&irreversible action expected,\\ 4,&mutation and (payment or confirmation required),\\ 3,&mutation, no payment or confirmation,\\ 1,&informational / read-only. cases (2) IiI_i is computed once per scenario from ix_i and stays fixed throughout evaluation; it is never updated from observed outcomes. This is a deliberate simplification. A learned or trajectory-conditioned impact model is a natural extension, but we do not implement it here. For scenario i after nin_i trials we also track the empirical failure rate p^i=ni−1∑tFi,t p_i=n_i^-1 _tF_i,t and mean cost C^i=ni−1∑tRi,tcost C_i=n_i^-1 _tR^cost_i,t; C^i C_i is used only after the fact, for cost-normalized metrics. 3.3 Allocation Strategies We compare six policies plus an oracle upper bound. All adaptive policies use either an ε -greedy or a posterior-sampling selection rule. No policy normalizes its score by estimated cost C^i C_i, so cost enters only as a reported outcome. Any cost efficiency we observe is therefore a byproduct of failure-aware selection, not an explicitly optimized objective. Uniform visits scenarios in a fixed, once-shuffled round-robin order, cycling back to the start and skipping scenarios whose trials are exhausted. Random draws uniformly at random from scenarios with remaining trials, independent of history. Failure-rate selects argmaxip^i _i p_i with probability 1−ε1- (ε=0.1 =0.1), using an optimistic p^i=1 p_i=1 for ni=0n_i=0 so every scenario is tried at least once, and selects uniformly at random otherwise. Risk-aware has the same ε -greedy structure but ranks by Iip^iI_i p_i, so scenarios with higher known impact are preferred even before any evidence is observed. It is the natural static-impact heuristic that posterior-based exploration must beat. Thompson Sampling (arm-only) keeps each scenario as an independent Beta posterior θi∼Beta(αi,βi) _i ( _i, _i) over its failure probability, initialized αi=βi=1 _i= _i=1 and updated as (αi,βi)←(αi+Fi,t,βi+1−Fi,t)( _i, _i)←( _i+F_i,t,\ _i+1-F_i,t). At each step a sample θ~i θ_i is drawn for every available scenario and the maximizer of Vi=Iiθ~iV_i=I_i\, θ_i (3) is selected. This variant does not use ix_i. Thompson Sampling (contextual) is identical to the arm-only variant, except that the Beta parameters are informed by a population-level model of ix_i. After every pull a logistic regression is refit on all pooled (j,Fj,⋅)(x_j,F_j,·) observations seen so far, giving a predicted failure probability p^(i) p(x_i) for every scenario, including those never yet executed. This prediction is blended with a scenario’s own evidence as pseudo-counts, ai=1+λp^(i)+∑tFi,t,bi=1+λ(1−p^(i))+ni−∑tFi,t,a_i=1+λ\, p(x_i)+ _tF_i,t, b_i=1+λ\, (1- p(x_i) )+n_i- _tF_i,t, (4) with θ~i∼Beta(ai,bi) θ_i (a_i,b_i) and selection by Eq. 3. The context weight λ sets how strong the population-level prior is relative to a scenario’s own evidence; λ=0λ=0 recovers the arm-only variant exactly. We fixed λ=2λ=2 a priori as a weakly-informative default before running the sweep, and report it throughout, with an ablation over λ∈2,8,16,32λ∈\2,8,16,32\ in Appendix D. Both Thompson Sampling variants select the first trial of each replicate uniformly at random, since the flat prior at t=0t=0 makes the posterior-sampled choice indistinguishable from random selection. Oracle sorts all trials by Yi,tY_i,t in descending order and reports the cumulative sum of the top B values for a given replicate’s realized outcomes. This is the best any policy could achieve against that exact realized dataset at budget B, and it automatically respects each scenario’s finite trial count because it draws from the same already-collected outcomes. 3.4 Corpus and Offline Replay Protocol Scenarios come from the airline domain of τ-bench Yao et al. (2025): N=70N=70 scenarios covering reservation search, booking, cancellation, flight modification, passenger and baggage changes, and payment operations. Trial outcomes are generated with a GPT-4o OpenAI (2024) tool-calling agent (temperature 0.0) against a GPT-4o simulated user under τ-bench’s native harness; Fi,tF_i,t compares the agent’s realized action sequence and final environment state against the ground-truth reference. Trial counts per scenario are not perfectly uniform (6 to 17), a consequence of aggregating independently executed result batches; the corpus totals 824 trials. Rather than executing fresh trials for each policy, we evaluate all strategies by replaying them against this single collected corpus. For each of M=30M=30 replicates, a scenario’s observed trials are shuffled with a replicate-specific seed and served without replacement as a policy pulls that scenario. This is standard offline bandit evaluation, valid under the assumption that trial order does not affect a scenario’s underlying outcome distribution. Critically, every policy in a sweep uses the identical seed schedule (seed=10000s+rseed=10000s+r), so replicate r presents the exact same shuffled ordering to every policy; per-replicate outcomes are directly comparable, which is what licenses the paired tests. 3.5 Metrics and Statistical Procedure All metrics are computed over M=30M=30 replicates at budgets B∈50,100,150,200,300,500,700B∈\50,100,150,200,300,500,700\. We report mean cumulative Y and raw failure count F; oracle-normalized efficiency pct_of_oracle(π,B)=100Y¯π(B)/Y∗(B)pct\_of\_oracle(π,B)=100\, Y_π(B)/Y^*(B), with Y∗(B)Y^*(B) the oracle value computed per replicate and averaged; cost-normalized efficiency FDE$=Y¯π(B)/cost¯π(B)FDE_\$= Y_π(B)/ cost_π(B) and its raw-failure analogue; and trivial-scenario allocation, the fraction of a policy’s budget spent on scenarios with p^i=0 p_i=0 across all of their trials in the full corpus (not just those the policy pulled), a direct test of whether adaptive allocation avoids scenarios with no observed failure potential. Because replicate r presents an identical trial ordering to every policy, we compare policies pairwise with a paired t-test on per-replicate cumulative Y at each budget, correcting within each family of tests using the Holm step-down procedure Holm (1979). We apply this to compare ts-contextual against ts-arm-only and risk-aware (14 tests: 2 comparisons × 7 budgets), and to compare ts-contextual using its full 17-feature context against a 13-feature variant with the four features that directly determine IiI_i removed (7 tests). The second family isolates whether any contextual advantage is just information already captured by the impact score. 4 Results We evaluate all six strategies on the full corpus of N=70N=70 scenarios and 824 realized trials, replaying each policy against the same collected outcomes for 30 independent replicates. Unless noted, ts-contextual uses λ=2λ=2. Section 4.1 presents the main result of the paper, discovery at a small budget. The remaining subsections are supporting analyses: they show how the advantage changes with budget, which mechanism drives it and when, what it costs in dollars, and where the saved budget comes from. 4.1 Main Result: Discovery at a Small Budget Table 1: Mean cumulative impact-weighted failures (Y) and percentage of oracle-achievable Y recovered, at four representative budgets. The B=50B=50 column is the main result; larger budgets are shown for context. Bold marks the best strategy at each budget. B=50B=50 B=100B=100 B=300B=300 B=700B=700 Strategy Y %oracle Y %oracle Y %oracle Y %oracle Uniform 62.2 24.9 124.1 26.4 372.3 37.0 858.0 81.2 Random 59.9 23.9 123.7 26.3 367.2 36.5 870.5 82.4 Failure-rate 166.2 66.5 357.2 76.0 708.3 70.4 1056.2 99.9 Risk-aware 205.3 82.1 382.1 81.3 830.1 82.5 1056.2 99.9 TS (arm-only) 204.5 81.8 365.1 77.7 908.4 90.3 1054.0 99.7 TS (contextual) 215.4 86.1 374.7 79.7 906.2 90.1 1053.6 99.7 Oracle 250.0 100 470.0 100 1006.0 100 1057.0 100 00100100200200300300500500700700002002004004006006008008001,0001,000Budget B (trials)Impact-weighted failures Y(a) Cumulative discovery001001002002003003005005007007002020404060608080100100Budget B (trials)% of oracle-achievable Y(b) Fraction of oracle recovered 1 Figure 1: Impact-weighted failure discovery as a function of evaluation budget, for all six allocation strategies and the oracle upper bound. (a) raw cumulative Y; (b) the same result normalized by the oracle. The adaptive advantage is largest at the smallest budget and disappears as the budget approaches the size of the corpus. The main result of this paper is the B=50B=50 column of Table 1. At a budget of 50 trials, which is 6%6\% of the 824-trial corpus, ts-contextual recovers 86.1%86.1\% of the impact-weighted discovery an oracle could achieve. Uniform allocation recovers 24.9%24.9\% and random allocation 23.9%23.9\%. In raw terms, ts-contextual finds 3.46×3.46× more impact-weighted failures than uniform (215.4 vs. 62.2) with the exact same number of trials. All four adaptive strategies recover 6666–86%86\% at this budget, supporting H1: when the budget is tight, risk-aware adaptive allocation finds far more of what matters. We focus on the smallest budget because it is the realistic operating point. The rest of the sweep (Figure 1) bounds the claim: as the budget grows the advantage shrinks, and by B=700B=700 (85%85\% of the corpus) all four adaptive strategies converge to 99.799.7–99.9%99.9\% of the oracle. Uniform and random remain at 8181–82%82\% even at that generous budget, because they keep spending trials on scenarios that have already exhausted their contribution to Y. Adaptive allocation thus dominates at every budget short of exhausting the corpus, but the size of the advantage tracks how scarce the budget is. Nothing about the method is specific to small budgets; small budgets are simply where it pays. 4.2 Supporting Analysis: Which Mechanism Helps, and When Table 2: Paired comparison of ts-contextual against ts-arm-only (context vs. no context) and against risk-aware (posterior exploration vs. a static impact-only heuristic). ΔY Y is the mean per-replicate difference; pHolmp_Holm is corrected across all 14 tests in this family. ∗ marks pHolm<0.05p_Holm<0.05. vs. ts-arm-only vs. risk-aware Budget ΔY Y pHolmp_Holm ΔY Y pHolmp_Holm 50 +10.9+10.9 0.0001∗0.0001^* +10.1+10.1 0.0002∗0.0002^* 100 +9.7+9.7 0.0031∗0.0031^* −7.3-7.3 0.0750.075 150 +4.8+4.8 0.5430.543 −9.2-9.2 0.0610.061 200 +1.9+1.9 0.6140.614 +4.9+4.9 0.3980.398 300 −2.2-2.2 0.5430.543 +76.1+76.1 4.0×10−9∗4.0× 10^-9\,* 500 −0.8-0.8 0.6140.614 +45.8+45.8 8.2×10−10∗8.2× 10^-10\,* 700 −0.4-0.4 0.5430.543 −2.6-2.6 9.6×10−7∗9.6× 10^-7\,* The main result shows that adaptive allocation wins at a small budget, but not which ingredient of ts-contextual is responsible. Table 2 separates the two things it adds over blind allocation, scenario context ix_i and posterior-based exploration, using the paired tests licensed by the shared seed schedule. The comparison most relevant to the main result is the first row. Context is what wins the cold start. At B≤100B≤ 100, ts-contextual beats ts-arm-only, which is identical except that it ignores ix_i, with pHolm<0.005p_Holm<0.005. At no larger budget is the difference distinguishable from noise. The explanation is simple: when almost nothing has been tried, the population-level model over ix_i is the only useful signal for unobserved scenarios, and its value fades as arms accumulate their own evidence. A second effect appears at moderate budgets and is separate from context. ts-contextual beats the static heuristic risk-aware by a wide margin at B=300B=300 and B=500B=500 (ΔY=+76.1 Y=+76.1 and +45.8+45.8, pHolm<10−8p_Holm<10^-8), even though it is indistinguishable from ts-arm-only at those same budgets. Since the two Thompson variants differ from risk-aware only in how they explore, this mid-budget advantage comes from posterior-based exploration, not from ix_i. risk-aware keeps exploring at a fixed rate (ε=0.1 =0.1) no matter how much evidence it has, while the Thompson variants naturally explore less as their posteriors sharpen. We discover no advantage over either baseline at B=150B=150–200200. The nominally significant B=700B=700 result against risk-aware is a −2.6-2.6 difference on 1056.2, a 0.24%0.24\% relative gap at a budget where the corpus is 85%85\% exhausted, and we do not read it as practically meaningful. To summarize, the evidence for context is specific to the small-budget regime and the evidence for posterior exploration to the mid-budget regime; a blanket claim that contextual TS wins would be wrong in both directions. H2 is therefore partially supported and explicitly budget-dependent. Finally, we test whether the composition of ix_i matters, comparing the full 17-feature vector against a residual 13-feature variant with the four features that directly determine IiI_i removed (requires_mutation, requires_confirmation, has_payment, irreversible_actions_expected). No budget survives Holm correction (pHolm≥0.064p_Holm≥ 0.064 everywhere; Appendix A). The contextual advantage is therefore not an artifact of ix_i re-encoding information already in IiI_i. At the same time, the exact composition of the remaining features is not a first-order driver of performance at this corpus size. 4.3 Supporting Analysis: Cost in Dollars 001001002002003003005005007007005005001,0001,0001,5001,5002,0002,0002,5002,5003,0003,000Budget B (trials)FDE$FDE_\$: Y per dollar(a) Cost-normalized efficiency00100100200200300300500500700700001010202030304040Budget B (trials)% of pulls on trivial scenarios(b) Budget spent on never-failing scenarios 2 Figure 2: (a) Impact-weighted failures discovered per dollar of measured evaluation cost. (b) Fraction of budget spent on trivial scenarios, meaning those that never failed in any observed trial (24 of 70; the grey dashed line is the 34.3%34.3\% corpus base rate). Table 3: Mean measured user-simulator cost (USD) and cost-normalized efficiency at the smallest and largest budgets. Cost is the logged user_cost of the GPT-4o simulated user, the only component consistently recorded per trial; agent-side spend is not included. Y/$Y/\$ is FDE$FDE_\$; F/$F/\$ is its raw-failure analogue. B=50B=50 B=700B=700 Strategy Cost ($) Y/$Y/\$ F/$F/\$ Cost ($) Y/$Y/\$ F/$F/\$ Uniform 0.098 636 221 1.383 620 211 Random 0.099 605 208 1.392 625 211 Failure-rate 0.120 1388 347 1.502 703 233 Risk-aware 0.071 2897 591 1.503 703 233 TS (arm-only) 0.070 2925 591 1.468 718 237 TS (contextual) 0.067 3207 650 1.461 721 238 Trial count is a convenient proxy for budget, but the resource actually spent is money. Table 3 and Figure 2(a) restate the main result in dollars. At B=50B=50, ts-contextual finds 5.0×5.0× more impact-weighted failures per dollar than uniform allocation (3207 vs. 636) while spending less in total ($0.067 vs. $0.098). The gain is not bought with extra spend; it comes from putting the same or smaller outlay on more informative scenarios. Consistent with the budget-dependence above, the advantage narrows to 1.16×1.16× by B=700B=700, supporting H4 at small budgets with diminishing, but never negative, returns at large ones. This accounting uses directly logged user_cost. No policy selects on a cost-adjusted utility, so the observed cost efficiency is a byproduct of failure-aware selection and a conservative estimate of what cost-aware selection could achieve. 4.4 Supporting Analysis: Where the Saved Budget Comes From What does uniform allocation spend its budget on that ts-contextual does not? To answer this, and to test H3, we label a scenario trivial if it never failed in any of its trials in the full corpus (p^i=0 p_i=0). Of the 70 scenarios, 24 (34.3%34.3\%) are trivial, so a policy that ignores observed outcomes should spend about a third of its budget learning nothing. Figure 2(b) shows exactly that: uniform and random track the 34.3%34.3\% base rate at every budget, within a percentage point. At the main-result budget of B=50B=50, ts-contextual spends 2.8%2.8\% on trivial scenarios against uniform’s 34.2%34.2\%, a 91.8%91.8\% relative reduction. All four adaptive strategies hold trivial spend below 6%6\% through B=200B=200 (failure-rate rises to 9.6%9.6\% at B=300B=300; the other three stay at 22–5%5\%), and ts-contextual has the lowest trivial spend of all six strategies at every budget through B=300B=300. This is where the small-budget advantage comes from: the trials that uniform allocation wastes on scenarios that cannot fail are redirected to scenarios that can. Trivial spend rises again for all adaptive strategies beyond B=300B=300, reaching 2121–24%24\% by B=700B=700. This is not a policy failure; it is what a finite corpus forces. Once a strategy has used up the available trials in every scenario capable of producing Y>0Y>0, the only budget left to spend is on scenarios already known to be safe. That turning point is a useful diagnostic: it marks the budget at which a fixed corpus has been mined of its discoverable failures, beyond which extra budget buys confidence rather than discovery. 4.5 Synthesis Across the four hypotheses: H1 is supported (adaptive strategies recover 6666–86%86\% of oracle at B=50B=50 vs. 23.923.9–24.9%24.9\% for uniform/random); H2 is partially supported and budget-dependent, in the decomposed sense of Section 4.2; H3 is supported (trivial spend falls from a ∼ 34%34\% base rate to below 6%6\% through B=200B=200, and to 22–5%5\% through B=300B=300 for all but failure-rate); and H4 is supported at low budgets with diminishing returns at high ones (FDE$FDE_\$ improves 5.0×5.0× at B=50B=50, 1.16×1.16× at B=700B=700). The practical reading: with a budget small relative to the corpus, the common case, use contextual Thompson Sampling; with a budget near the corpus size, any adaptive policy will do, including the much simpler risk-aware heuristic. One caveat: three of our 17 features carry no variance in this corpus, so the residual-feature null speaks to the 14 active features, not to the full intended feature space. 5 Limitations Four limitations bound these conclusions. Scope: results come from a single interactive airline-agent environment with 70 scenarios. Failure patterns in other domains such as customer support, healthcare, finance, or software engineering may differ, and replication across benchmarks is the most important next step. Impact specification: IiI_i is rule-based and fixed; it cannot infer the severity of a new failure from its trajectory, and a learned impact model would be more principled. Arm independence: modeling each scenario as an independent arm ignores correlations. Scenarios sharing a policy or operation type likely share failure modes, which a hierarchical formulation would exploit. Relatedly, our contextual variant uses a plug-in empirical-Bayes approximation rather than a full posterior over the logistic link, a simplification more likely to matter at larger corpus sizes. Objective: we focus primarily on failure discovery under a fixed evaluation budget. Higher failure discovery does not necessarily imply greater failure diversity, severity, representativeness, or diagnostic value. Finally, our resource model uses directly measurable execution quantities (tool calls, turns, trajectory length, dollar cost); token-level consumption and wall-clock latency were not consistently available in these logs. These results are evidence that resource- and risk-aware evaluation is feasible and valuable, not a claim of universal optimality. 6 Conclusion We formulated interactive-agent evaluation as a sequential resource allocation problem in which the evaluator, not the benchmark designer, decides how many trials each scenario deserves. Separating a scenario’s fixed, pre-execution consequence (IiI_i, ix_i) from its observed likelihood of failure (Fi,tF_i,t) yields a risk-aware contextual Thompson Sampling policy whose value is concentrated where budgets are tight. With 6%6\% of the corpus’s trial budget, it recovers 86%86\% of what a perfectly informed oracle could find: 3.5×3.5× what uniform allocation finds with the same trials, at 5×5× the discovery per dollar, while cutting wasted effort on never-failing scenarios by an order of magnitude. Paired, Holm-corrected significance testing further shows that the benefit of scenario context specifically is concentrated in the cold-start regime and posterior exploration helps at moderate budgets. The broader point is simple: the trial schedule of an agent benchmark is a design variable worth optimizing, and treating it as fixed leaves a large share of a small evaluation budget on the table. Future directions. The most immediate extensions are a learned, trajectory-conditioned impact model in place of the rule-based IiI_i; a hierarchical or fully Bayesian generalized linear bandit that shares statistical strength across related scenarios; and cost-adjusted selection, since our policies achieve their cost efficiency without optimizing for it. Beyond these, replicating on more benchmarks and extending the objective toward failure diversity and calibrated reliability estimation would test how far the formulation generalizes. Broad impact statement. This work aims to make interactive-agent evaluation more efficient and more attentive to consequential failures under limited testing budgets. We see this as broadly beneficial for the safe deployment of agentic systems: prioritizing evaluation effort toward scenarios involving irreversible actions, payment, or policy-sensitive operations is intended to surface higher-stakes failures earlier and with less computational and monetary cost than uniform testing. However, an impact score that is misspecified or incomplete, could cause an adaptive policy to systematically under-sample consequential scenarios. Also, adaptive evaluation is a tool for finding failures faster, not a substitute for comprehensive evaluation coverage; a scenario that receives few trials because it currently shows no evidence of failure should not be interpreted as verified safe, only as unexamined by this allocation policy at this budget. References [1] S. Yao, N. Shinn, P. Razavi, and K. Narasimhan (2025) τ-Bench: a benchmark for tool-agent-user interaction in real-world domains. In International Conference on Learning Representations, Vol. 2025, p. 9965–10017. Cited by: Appendix F, NeurIPS Paper Checklist, §1, §2, §3.4. [2] V. Barres, H. Dong, S. Ray, X. Si, and K. R. Narasimhan (2026) τ2τ^2-Bench: evaluating conversational agents in a dual-control environment. In Forty-third International Conference on Machine Learning, External Links: Link Cited by: §1, §2. [3] M. Zhuge, W. Wang, L. Kirsch, F. Faccio, D. Khizbullin, and J. Schmidhuber (2024) GPTSwarm: language agents as optimizable graphs. In Proceedings of the 41st International Conference on Machine Learning, Vol. 235, p. 62743–62767. Cited by: §1. [4] Z. Wang, Y. Wang, X. Liu, L. Ding, M. Zhang, J. Liu, and M. Zhang (2025) AgentDropout: dynamic agent elimination for token-efficient and high-performance llm-based multi-agent collaboration. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics, p. 24013–24035. Cited by: §1. [5] W. R. Thompson (1933) On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25 (3–4), p. 285–294. Cited by: NeurIPS Paper Checklist, §1, §2. [6] S. Agrawal and N. Goyal (2012) Analysis of thompson sampling for the multi-armed bandit problem. arXiv preprint arXiv:1111.1797. Cited by: NeurIPS Paper Checklist, §1, §2. [7] D. Russo, B. Van Roy, A. Kazerouni, I. Osband, and Z. Wen (2018) A tutorial on thompson sampling. Vol. 11. Cited by: NeurIPS Paper Checklist, §1, §2. [8] S. Agrawal and N. Goyal (2013) Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning, p. 127–135. Cited by: NeurIPS Paper Checklist, §1, §2. [9] W. Huang (2026) How many tasks are enough for agent benchmark decisions? A replay analysis of public LLM agent benchmarks. arXiv preprint arXiv:2607.12338. Cited by: §1, §2. [10] X. Liu, H. Yu, H. Zhang, Y. Xu, X. Lei, H. Lai, Y. Gu, H. Ding, K. Men, K. Yang, S. Zhang, X. Deng, A. Zeng, Z. Du, C. Zhang, S. Shen, T. Su, H. Sun, M. Huang, Y. Dong, and J. Tang (2024) AgentBench: evaluating llms as agents. In International Conference on Learning Representations, Cited by: §2. [11] S. Zhou, F. F. Xu, H. Zhu, X. Zhou, R. Lo, A. Sridhar, X. Cheng, Y. Bisk, D. Fried, U. Alon, and D. Roth (2024) WebArena: a realistic web environment for building autonomous agents. In International Conference on Learning Representations, Cited by: §2. [12] Y. Qin, S. Liang, Y. Ye, K. Zhu, L. Yan, Y. Lu, Y. Lin, X. Cong, X. Tang, B. Qian, et al. (2024) ToolLLM: facilitating large language models to master 16000+ real-world apis. In International Conference on Learning Representations, Cited by: §2. [13] Z. Wang, Q. Chang, H. Patel, S. Biju, C. Wu, Q. Liu, A. Ding, A. Rezazadeh, A. Shah, Y. Bao, and E. Siow (2025) MCP-Bench: benchmarking tool-using LLM agents with complex real-world tasks via MCP servers. arXiv preprint arXiv:2508.20453. Cited by: §2. [14] Z. Mustahsan, A. Lim, M. Anand, S. Jain, and B. T. McCann (2025) Stochasticity in agentic evaluations: quantifying inconsistency with intraclass correlation. arXiv preprint arXiv:2512.06710. Cited by: §2, §2. [15] B. H. Bjarnason, A. Silva, and M. Monperrus (2026) On randomness in agentic evals. arXiv preprint arXiv:2602.07150. Cited by: §2. [16] G. Gonzalez-Pumariega, S. Agashe, J. Yang, A. Li, and X. Wang (2026) On the reliability of computer use agents. arXiv preprint arXiv:2604.17849. Cited by: §2. [17] P. He, Z. Dai, B. He, H. Liu, X. Tang, H. Lu, J. Li, J. Ding, S. Mukherjee, S. Wang, Y. Xing, J. Tang, and B. Dumoulin (2026) TRAJECT-bench:a trajectory-aware benchmark for evaluating agentic tool use. In The Fourteenth International Conference on Learning Representations, External Links: Link Cited by: §2. [18] H. Cao, I. Driouich, and E. Thomas (2026) Beyond task completion: revealing corrupt success in LLM agents through procedure-aware evaluation. arXiv preprint arXiv:2603.03116. Cited by: §2. [19] H. Bastani, M. Bayati, and K. Khosravi (2021) Mostly exploration-free algorithms for contextual bandits. Management Science 67, p. 1329–1349. Cited by: §2. [20] C. Riquelme, G. Tucker, and J. Snoek (2018) Deep Bayesian bandits showdown: an empirical comparison of Bayesian deep networks for Thompson sampling. arXiv preprint arXiv:1802.09127. Cited by: §2. [21] S. Filippi, O. Cappe, A. Garivier, and C. Szepesvári (2010) Parametric bandits: the generalized linear case. In Advances in Neural Information Processing Systems, J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta (Eds.), Vol. 23, p. . External Links: Link Cited by: §2. [22] B. Dumitrascu, K. Feng, and B. Engelhardt (2018) PG-ts: improved thompson sampling for logistic contextual bandits. In Advances in Neural Information Processing Systems, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cuester-Blanchet, and R. Garnett (Eds.), Vol. 31, p. 7713–7723. External Links: Link Cited by: §2. [23] W. Zhang, D. Zhou, L. Li, and Q. Gu (2020) Neural Thompson sampling. arXiv preprint arXiv:2010.00827. Cited by: §2. [24] H. Park and M. K. S. Faradonbeh (2024) Thompson sampling in partially observable contextual bandits. arXiv preprint arXiv:2402.10289. Cited by: §2. [25] A. Karbasi, V. Mirrokni, and M. Shadravan (2021) Parallelizing Thompson sampling. In Advances in Neural Information Processing Systems, p. 10535–10548. Cited by: §2. [26] M. Woo, S. K. Cha, S. Gottlieb, and D. Brumley (2013) Scheduling black-box mutational fuzzing. In Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security, CCS ’13, New York, NY, USA, p. 511–522. External Links: ISBN 9781450324779, Link, Document Cited by: §2. [27] T. Yue, P. Wang, Y. Tang, E. Wang, B. Yu, K. Lu, and X. Zhou (2020) EcoFuzz: adaptive energy-saving greybox fuzzing as a variant of the adversarial multi-armed bandit. SEC’20, USA. External Links: ISBN 978-1-939133-17-5 Cited by: §2. [28] S. Geyer, I. Papaioannou, and D. Straub (2019) Cross entropy-based importance sampling using Gaussian densities revisited. Structural Safety 76, p. 15–27. Cited by: §2. [29] C. Song and R. Kawai (2022) Adaptive stratified sampling for structural reliability analysis. Structural Safety 101, p. 102292. Cited by: §2. [30] S. Pieraccini and T. Vanzan (2025) An adaptive importance sampling algorithm for risk-averse optimization. arXiv preprint arXiv:2502.10084. Cited by: §2. [31] T. Liu, H. Xie, and J. C.S. Lui (2023) Online zero-cost learning: optimizing large scale network rare threats simulation. IEEE Transactions on Mobile Computing 22, p. 356–373. Cited by: §2. [32] OpenAI (2024) ChatGPT (GPT-4o version). Note: Large language model Accessed: 2026-07-29 - 2026-08-29Computer software External Links: Link Cited by: §3.4. [33] S. Holm (1979) A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics 6 (2), p. 65–70. Cited by: §3.5. Appendix Appendix A Feature-Composition Ablation Table 4 compares ts-contextual using the full 17-feature context vector against a residual 13-feature variant with the four features that directly determine IiI_i removed. No budget survives Holm correction across this 7-test family, so the contextual advantage reported in Section 4.2 is not explained by redundancy with the impact score. Table 4: ts-contextual with the full 17-feature ix_i versus a 13-feature residual vector with impact-determining features removed. Δ is computed on unrounded per-replicate values, so it can differ from the difference of the rounded columns by 0.10.1. pHolmp_Holm is corrected across all 7 tests. Budget YfullY_full YresidualY_residual Δ sd(Δ)sd( ) pHolmp_Holm 50 215.4 213.9 +1.4+1.4 7.58 1.000 100 374.7 375.6 −0.9-0.9 12.62 1.000 150 533.8 534.5 −0.7-0.7 12.46 1.000 200 681.2 676.0 +5.3+5.3 10.16 0.064 300 906.2 906.7 −0.5-0.5 6.30 1.000 500 1012.5 1011.3 +1.2+1.2 3.10 0.242 700 1053.6 1054.2 −0.6-0.6 1.64 0.242 Appendix B Full Trivial-Scenario Allocation Sweep Table 5: Fraction (%) of evaluation budget spent on trivial (never-failing) scenarios, by strategy and budget. 24 of 70 scenarios (34.3%34.3\%) are trivial by this definition. Strategy B=50B=50 100 150 200 300 500 700 Uniform 34.2 34.5 34.3 34.4 34.3 34.3 34.3 Random 35.5 34.4 35.1 34.9 34.4 34.2 33.7 Failure-rate 5.5 5.1 4.8 5.0 9.6 10.3 21.9 Risk-aware 5.5 5.0 4.4 4.4 5.0 10.1 21.9 TS (arm-only) 3.0 2.4 1.9 1.7 2.6 11.6 23.0 TS (contextual) 2.8 2.3 1.7 1.6 2.2 12.2 23.4 Appendix C Per-Scenario Allocation Figure 3 shows how each strategy distributes its pulls across individual scenarios at maximum budget. It makes the concentration effect of Section 4.4 visible at the level of single scenarios rather than aggregate fractions. Figure 3: Mean number of pulls allocated to each scenario at maximum budget, by strategy, with scenarios sorted by empirical failure rate (low to high). The red strip marks the 24 scenarios that never failed in the corpus. Uniform and random allocate flatly across the sort order; the adaptive strategies visibly withdraw from the never-failing block on the left. Appendix D Context-Weight Ablation Figures 4 and 5 sweep the context weight λ∈2,8,16,32λ∈\2,8,16,32\ of Eq. 4. The choice of λ matters only at the smallest budget, where the population-level prior carries the most weight relative to per-arm evidence. By B≥100B≥ 100 the four settings are indistinguishable. We report λ=2λ=2 throughout the main text. Figure 4: Cost-normalized efficiency (Y per dollar) for ts-contextual across context weights λ∈2,8,16,32λ∈\2,8,16,32\. Figure 5: Cumulative impact-weighted discovery for ts-contextual across context weights λ∈2,8,16,32λ∈\2,8,16,32\. Appendix E Compute Resources Corpus collection. The 824 trials of Section 3.4 were collected by running a GPT-4o tool-calling agent against a GPT-4o simulated user through the τ-bench harness. Replay experiments. Every result in Sections 4.1 through 4.4 and in Appendices A and D is produced by offline replay against the fixed corpus and involves no model inference. The full sweep including six policies plus the oracle, seven budgets, 30 replicates, plus the residual-feature and λ ablations runs in approximately 15 minutes on NVIDIA H200, 80 GB of memory. Appendix F Assets and Licenses τ-bench. Scenarios, the environment, the reference action sequences, and the user simulator come from the airline domain of τ-bench Yao et al. (2025) (version 59a200c6d575d595120f1cb70fea53cef0632f6b), released by its authors under the MIT License. We use the 50 scenarios from the benchmark unmodified for trial execution and added 20 custom scenarios for outcome scoring; the allocation layer studied here sits above it and changes only which scenarios are run and how often. GPT-4o. Both the evaluated agent and the simulated user are GPT-4o (gpt-4o-2025-03-01), accessed through the OpenAI API under the OpenAI Terms of Use and API data-usage policy. No model weights were obtained or redistributed. Software. Analysis and replay use Python 3.12 with NumPy, SciPy, scikit-learn (logistic regression for the contextual prior), pandas, and Matplotlib, tau-bench, each under its own permissive open-source license (BSD-3-Clause or equivalent). Released artifacts. The replay corpus and the allocation and replay code released with this paper are made available under the MIT License. The corpus is a derived record of agent behavior on τ-bench and contains no data beyond per-trial outcomes, resource counts, and measured cost; it is redistributed in a form consistent with the upstream MIT license, which is reproduced in the repository. NeurIPS Paper Checklist 1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope? Answer: [Yes] Justification: The abstract and Section 1 state exactly what the paper delivers: a risk-aware sequential-allocation formulation of interactive-agent evaluation, a contextual Thompson Sampling policy, and the headline small-budget result (86.1%86.1\% of oracle-achievable impact-weighted discovery at B=50B=50 versus 24.9%24.9\% for uniform allocation). Both also state the scope limits we verify in Sections 4.2 and 4.5: the advantage is budget-dependent and vanishes as the budget approaches the corpus size, and hypothesis H2 is reported as only partially supported. Guidelines: • The answer [N/A] means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A [No] or [N/A] answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 2. Limitations Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: Section 5 is a dedicated Limitations section covering the single-domain scope (70 airline scenarios from one benchmark), the fixed rule-based impact score, the independent-arm assumption together with the plug-in empirical-Bayes approximation used in place of a full posterior over the logistic link, the discovery-only objective, and the incomplete resource model. Section 4.5 additionally flags that three of the seventeen context features carry no variance in this corpus, so the residual-feature null of Appendix A speaks to the fourteen active features. Guidelines: • The answer [N/A] means that the paper has no limitation while the answer [No] means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate “Limitations” section in their paper. • The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren’t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 3. Theory assumptions and proofs Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [N/A] Justification: The paper contains no theorems, lemmas, or formal claims requiring proof; the contribution is a problem formulation together with an empirical study. The regret properties of Thompson Sampling that motivate the method are cited Thompson (1933); Agrawal and Goyal (2012); Russo et al. (2018); Agrawal and Goyal (2013) rather than re-derived here. Guidelines: • The answer [N/A] means that the paper does not include theoretical results. • All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 4. Experimental result reproducibility Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: Section 3.1 specifies the 17-dimensional context vector feature by feature, Equation 2 gives the impact rule in full, and Section 3.3 defines all six allocation policies and the oracle with every hyperparameter stated (ε=0.1 =0.1, λ=2λ=2, Beta(1,1)Beta(1,1) initialization, and the pseudo-count blending of Equation 4). Section 3.4 gives the corpus and the offline replay protocol including the exact seed schedule (seed=10000s+rseed=10000s+r over M=30M=30 replicates) that makes every reported number regenerable, and Section 3.5 defines each metric and the paired-testing procedure. Guidelines: • The answer [N/A] means that the paper does not include experiments. • If the paper includes experiments, a [No] answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 5. Open access to data and code Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: An repository containing the allocation policies, the offline replay harness, the 824-trial corpus, and scripts that regenerate every table and figure in the paper is provided with the submission (https://github.com/priyanathmaji/risk-aware-eval/); its README gives the exact commands and the Python environment. Because all reported results come from replay against a fixed collected corpus rather than fresh model calls, reproducing them requires no API credentials or paid inference. Guidelines: • The answer [N/A] means that paper does not include experiments requiring code. • Please see the NeurIPS code and data submission guidelines (https://neurips.c/public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so [No] is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark). • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://neurips.c/public/guides/CodeSubmissionPolicy) for more details. • The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc. • The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 6. Experimental setting/details Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer) necessary to understand the results? Answer: [Yes] Justification: Section 3.3 states every policy hyperparameter, Section 3.4 describes the corpus and the replay protocol (including that per-scenario trial counts are non-uniform, 6 to 17, as a consequence of aggregating independently executed batches), and Section 3.5 lists the budgets B∈50,100,150,200,300,500,700B∈\50,100,150,200,300,500,700\ and the M=30M=30 replicates. There is no model training; the only free parameter is the context weight λ, fixed a priori at 22 and swept over 2,8,16,32\2,8,16,32\ in Appendix D. Guidelines: • The answer [N/A] means that the paper does not include experiments. • The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 7. Experiment statistical significance Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: Every reported number is a mean over M=30M=30 replicates that differ only in the seed controlling trial-order shuffling, which is the sole source of randomness under replay. Because all policies are served an identical seed schedule, we compare them with paired t-tests on per-replicate cumulative Y at each budget and correct with the Holm step-down procedure within each family of tests (14 tests in Table 2, 7 in Table 4, which also reports sd(Δ)sd( )); the procedure is specified in Section 3.5. Guidelines: • The answer [N/A] means that the paper does not include experiments. • The authors should answer [Yes] if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates). • If error bars are reported in tables or plots, the authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 8. Experiments compute resources Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [Yes] Justification: Appendix E reports the hardware used, the wall-clock time and total OpenAI API spend required to collect the 824-trial corpus (including preliminary and discarded runs), and the negligible CPU cost of the replay sweeps themselves. Table 3 additionally reports the logged per-trial user-simulator cost that enters the cost-normalized metric. Guidelines: • The answer [N/A] means that the paper does not include experiments. • The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn’t make it into the paper). 9. Code of ethics Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.c/public/EthicsGuidelines? Answer: [Yes] Justification: We have reviewed the NeurIPS Code of Ethics and the research conforms to it in every respect. The study involves no human subjects and no personal or sensitive data, since both the agent and the user are language models acting in the synthetic τ-bench airline environment; the submission is anonymized and the released artifacts carry no dual-use risk. Guidelines: • The answer [N/A] means that the authors have not reviewed the NeurIPS Code of Ethics. • If the authors answer [No] , they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [Yes] Justification: The Broad Impact Statement in Section 6 discusses both directions. Cheaper evaluation lowers the barrier to testing deployed agents thoroughly and weighting discovery by consequence directs scarce effort toward high-stakes failures; against that, concentrating budget on high-impact scenarios under-samples the rest and weakens reliability estimates for low-priority scenarios, and the impact score IiI_i encodes a value judgement about which failures count. We state the mitigation explicitly: adaptive allocation is not a substitute for uniform coverage when the goal is an unbiased reliability estimate, and the two objectives should be budgeted separately. Guidelines: • The answer [N/A] means that there is no societal impact of the work performed. • If the authors answer [N/A] or [No] , they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate Deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 11. Safeguards Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pre-trained language models, image generators, or scraped datasets)? Answer: [N/A] Justification: The paper releases no pretrained models, generative systems, or scraped data. The released artifacts are evaluation code and replay logs of agent outcomes on a public synthetic benchmark, which carry no meaningful risk of misuse. Guidelines: • The answer [N/A] means that the paper poses no such risks. • Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: Appendix F credits every external asset and states its version and license: the τ-bench airline domain Yao et al. (2025) under its MIT license, GPT-4o accessed through the OpenAI API under the OpenAI terms of use, and the open-source Python libraries used for the analysis. All assets are used within their stated terms. Guidelines: • The answer [N/A] means that the paper does not use existing assets. • The authors should cite the original paper that produced the code package or dataset. • The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., C-BY 4.0) should be included for each asset. • For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset’s creators. 13. New assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [Yes] Justification: The submission introduces two assets, both in the anonymized repository referenced in item 5: the 824-trial replay corpus (per-trial failure indicator, resource vector, and measured cost for each of the 70 scenarios) and the allocation and replay implementation. Both ship with a README documenting the record schema, the collection procedure of Section 3.4, and the license. Guidelines: • The answer [N/A] means that the paper does not release new assets. • Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 14. Crowdsourcing and research with human subjects Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)? Answer: [N/A] Justification: The study involves no human participants. The “user” in every trial is a GPT-4o simulator supplied by the τ-bench harness, as described in Section 3.4. Guidelines: • The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 15. Institutional review board (IRB) approvals or equivalent for research with human subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained? Answer: [N/A] Justification: No human subjects were involved in this research, so no IRB review or equivalent approval was required. Guidelines: • The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 16. Declaration of LLM usage Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigor, or originality of the research, declaration is not required. Answer: [Yes] Justification: GPT-4o is a core component of the experimental pipeline rather than a writing aid: it serves both as the tool-calling agent under evaluation (temperature 0.00.0) and as the simulated user that drives each interaction, and the 824 trial outcomes replayed throughout the paper are its output (Section 3.4). The allocation method itself including the impact rule, the Beta posteriors, and the contextual prior uses no LLM. Guidelines: • The answer [N/A] means that the core method development in this research does not involve LLMs as any important, original, or non-standard components. • Please refer to our LLM policy in the NeurIPS handbook for what should or should not be described.