Risk-Aware Adaptive Evaluation: Finding High-Impact Failures Under Limited Budgets

Priyanath Maji; Spandan Ghose Chowdhury

cs.AISep 30, 2026

Risk-Aware Adaptive Evaluation: Finding High-Impact Failures Under Limited Budgets

Authors: Priyanath Maji, Spandan Ghose Chowdhury

Organizations: Georgia Institute of Technology Atlanta, GA 30332

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\%$ 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.

Figures & tables

	$B=50$		$B=100$		$B=300$		$B=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

Table 1: Mean cumulative impact-weighted failures (

Y

) and percentage of oracle-achievable

Y

recovered, at four representative budgets. The

B{=}50

column is the main result; larger budgets are shown for context. Bold marks the best strategy at each budget.

Panel of Figure 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.

	vs. ts-arm-only		vs. risk-aware
Budget	$\Delta Y$	$p_{\mathrm{Holm}}$	$\Delta Y$	$p_{\mathrm{Holm}}$
50	$+10.9$	$0.0001^{*}$	$+10.1$	$0.0002^{*}$
100	$+9.7$	$0.0031^{*}$	$-7.3$	$0.075$
150	$+4.8$	$0.543$	$-9.2$	$0.061$
200	$+1.9$	$0.614$	$+4.9$	$0.398$
300	$-2.2$	$0.543$	$+76.1$	$4.0\times 10^{-9\,*}$

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).

\Delta Y

is the mean per-replicate difference;

p_{\mathrm{Holm}}

is corrected across all 14 tests in this family. ∗ marks

p_{\mathrm{Holm}}<0.05

Panel of Figure 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\%$ corpus base rate).

Strategy	Cost ($)	$Y/$$	$F/$$	Cost ($)	$Y/$$	$F/$$
	$B=50$			$B=700$
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

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/\$$ is

\mathrm{FDE}_{$}

;

F/$$ is its raw-failure analogue.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Budget	$Y_{\mathrm{full}}$	$Y_{\mathrm{residual}}$	$\Delta$	$\mathrm{sd}(\Delta)$	$p_{\mathrm{Holm}}$
50	215.4	213.9	$+1.4$	7.58	1.000
100	374.7	375.6	$-0.9$	12.62	1.000
150	533.8	534.5	$-0.7$	12.46	1.000
200	681.2	676.0	$+5.3$	10.16	0.064
300	906.2	906.7	$-0.5$	6.30	1.000
500	1012.5	1011.3	$+1.2$	3.10	0.242

Appendix

Table 4: ts-contextual with the full 17-feature

\mathbf{x}_{i}

versus a 13-feature residual vector with impact-determining features removed.

\Delta

is computed on unrounded per-replicate values, so it can differ from the difference of the rounded columns by

0.1

p_{\mathrm{Holm}}

is corrected across all 7 tests.

Strategy	$B{=}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

Table 5: Fraction (%) of evaluation budget spent on trivial (never-failing) scenarios, by strategy and budget. 24 of 70 scenarios (

34.3\%

) are trivial by this definition.

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.

Figure 4: Cost-normalized efficiency ( $Y$ per dollar) for ts-contextual across context weights $\lambda\in\{2,8,16,32\}$ .

Figure 5: Cumulative impact-weighted discovery for ts-contextual across context weights $\lambda\in\{2,8,16,32\}$ .

Explore similar work

Aug 1, 2026cs.AI

AgentSLABench: Evaluating and Benchmarking Agentic Systems Under Resource Constraints

We present AgentSLABench, a resource-aware evaluation framework for autonomous AI agents that measures correctness alongside latency, cost, compute, memory, and network usage under declared resource budgets. Unlike standard benchmarks that report only accuracy, AgentSLABench produces a multi-dimensional profile per agent per task - the same way systems profilers (perf, pprof, cProfile) measure resource consumption of code, but extended with task correctness as a first-class dimension. AgentSLABench provides 16 task environments across 6 categories (5 core: multi-hop QA, retail substitution, code generation, web shopping, travel planning; 11 extended) with isolated Docker containers, declared CPU/memory/time/network budgets, sealed test sets with SHA256 hashes, and a standardized profiling protocol. We profile 5 general-purpose baseline agents (ReAct, PlanAndSolve, Reflexion, CoT, Random) plus 4 task-specialized agents, finding that specialized agents achieve 100% success on 3/5 core tasks (fact_qa, web_shopping, travel_planning) and 66.7-83.3% on retail and code_gen, while general baselines fail entirely on 4/5 domain tasks. Crucially, we report the Efficiency-Adjusted Success Rate (EASR) - success weighted by resource consumption relative to declared budgets - revealing that high accuracy at unbounded cost is not production-viable. We release the full infrastructure, sealed test sets, and profiling results to enable reproducible, resource-aware agent evaluation.

Meher Bhaskar Madiraju, Meher Sai Preetam Madiraju

Agentic Benchmarks Agentic Evaluations Profiling Multi-Hop Reasoning

Ask PDF

May 29, 2026cs.LG

BAGEN: Are LLM Agents Budget-Aware?

While agents are increasingly spending more resources, today agent cost is mostly measured only after execution. A Budget-Aware Agent (BAGEN) should treat budget as an active control signal, rather than a passive cost metric. We first systematically define budget estimation as internal budgets (from agent computation) and external budgets (from agent actions). We then formalize budget-awareness as progressive interval estimation: at each step of a plan, an agent should predict an upper and lower bound on remaining budget, and alert when completion is unlikely. Scoring with a rollout-replay protocol, we find consistent failure patterns on four environments and five frontier agents: (1) strong agents do not necessarily have strong budget-awareness, with correlation r=0.35. (2) frontier models are consistently over-optimistic, continue spending on tasks that are unlikely to succeed, instead of alerting the user early. (3) budget-aware signal is actionable and trainable. Early stop saves 28-64% tokens on failed trajectories, and SFT+RL strengthens early stop and alert behavior. (4) precise interval calibration remains challenging, with interval coverage capping at 47% after SFT+RL. Project page: https://ragen-ai.github.io/bagen/

Yuxiang Lin, Zihan Wang, Mengyang Liu +9

1Northwestern University · 2O2 Lab · 3Independent +5

Token Budget Allocation Large Language Model Agents Passive

Ask PDF

May 11, 2026cs.AI

Can Agent Benchmarks Support Their Scores? Evidence-Supported Bounds for Interactive-Agent Evaluation

Interactive agent benchmarks map an agent run to a binary outcome through outcome checks. When these checks rely on surface level signals or fail to capture the agent's actual action path, they cannot reliably determine whether the run succeeded. For example, a benchmark task may ask whether Alice's shipping address was changed, while the outcome check only verifies that the agent clicked "Save." This does not guarantee that the intended state change occurred, since the agent may have modified the wrong record. Treating such a run as successful therefore makes the reported score misleading. Benchmark quality thus depends not only on task design, but also on the reliability of outcome detection. We address this problem by introducing an outcome evidence reporting layer for existing benchmarks, without modifying their tasks, agents, or evaluators. The layer performs three functions. First, before scoring, it specifies which stored artifacts are required to verify the claimed outcome for each case. Second, it applies a locked checklist to each completed run and assigns one of three evidence labels: Evidence Pass, Evidence Fail, or Unknown. Third, it reports evidence supported score bounds that quantify uncertainty arising from Unknown cases. Rather than silently counting, discarding, or hiding uncertain cases inside a single aggregate success rate, the framework keeps them explicitly visible. We evaluate the outcome evidence layer on five public benchmarks: ANDROIDWORLD, AGENTDOJO, APPWORLD, tau3 bench retail, and MINIWOB. The resulting reports separate several empirically distinct failure modes.

Shanshan Gao, Liyi Zhou

The University of Sydney

Agentic Benchmarks Device Upper Bounds

Ask PDF