PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Priyanath Maji, Spandan Ghose Chowdhury

arXiv:2609.38914v1cs.AIcs.LGcs.MA

TL;DR

Repeated trials are needed to evaluate stochastic agents, but uniform sampling treats scenarios with different failure rates and consequences alike. The paper uses risk-aware contextual Thompson Sampling to allocate trials; at 50 trials, it recovers 86.1% of oracle impact-weighted failure discovery, versus 24.9% for uniform allocation.

  • Problem

    Repeated trials are needed to measure stochastic agent reliability, yet uniform evaluation allocates trials equally across scenarios that differ in failure frequency and consequence.

    Source: §1 · p. 1

  • Method

    The paper frames evaluation as sequential allocation, combining pre-execution scenario context and fixed impact with observed failure outcomes in a risk-aware contextual Thompson Sampling policy.

    Source: §1 · p. 2

  • Results

    At 50 trials, contextual Thompson Sampling recovers 86.1% of oracle impact-weighted failure discovery, versus 24.9% for uniform allocation.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The allocation advantage is strongest at small budgets and shrinks as the budget grows toward the corpus size.

    Source: §1 · p. 2

    The results come from one interactive airline-agent environment with 70 scenarios, and replication across benchmarks is identified as the most important next step.

    Source: §5 · p. 9

Abstract

from arXiv · show

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.

1 Introduction

Repeated trials are needed to measure stochastic agent reliability, but uniform allocation spends equally on scenarios that differ in failure frequency and impact. The paper formulates evaluation as risk-aware sequential allocation and finds its largest advantage at small budgets.

1 Introduction

  • Uniform repetition wastes budget because scenarios vary in failure frequency and consequence; 24 of 70 scenarios never fail in the observed corpus.A read-only lookup and an irreversible payment action are not equally consequential, despite uniform sampling treating them alike.Source: §1 · p. 1
  • Prior agent-efficiency work reduces the cost of individual executions, while this work asks which scenarios merit execution or repetition.The paper tests adaptivity, context, concentration away from scenarios with no observed failures, and discovery per unit cost.Source: §1 · p. 2
  • The paper frames evaluation as sequential resource allocation, combining pre-execution scenario context and fixed impact with failure outcomes observed during evaluation.Its objective is discovering impact-weighted failures under a fixed resource constraint, rather than maximizing environmental reward.Source: §1 · p. 2
  • At 50 trials, contextual Thompson Sampling recovers 86.1% of oracle impact-weighted failure discovery, versus 24.9% for uniform allocation.The advantage shrinks as the budget grows toward the corpus size.Source: §1 · p. 2
  • Paired, Holm-corrected tests find context helps most in the cold start, while posterior-based exploration helps at moderate budgets.Context beats the arm-only variant at B ≤ 100; posterior exploration beats the static risk-aware heuristic at B = 300–500.Source: §1 · p. 2

2 Related Work

Prior work establishes the need to evaluate interactive agents across repeated trials and full trajectories, but generally uses predetermined schedules. Related allocation methods offer precedents, while this paper focuses on impact-weighted failure discovery for LLM agents.

2 Related Work

  • τ-bench measures reliability across repeated trials, and follow-up studies document substantial within-task variation across agent runs.Other benchmarks extend evaluation to web tasks, real APIs, and live MCP servers [11] [12] [13].Source: §2 · p. 2
  • Trajectory-level evaluation shows that correct final states can arise from flawed procedures [17] [18], but prior protocols use predetermined, uniform trial schedules.The paper instead treats the evaluation schedule itself as something to optimize.Source: §2 · p. 3
  • Thompson Sampling balances exploration and exploitation using posterior samples, and contextual extensions use pre-execution features [8].The paper uses an empirical-Bayes approximation; a fully Bayesian generalized linear bandit is described as a natural option at larger scenario counts.Source: §2 · p. 3
  • Unlike allocation for mean-accuracy estimation, this work targets discovery of failures weighted by consequence, separating known scenario impact from observed failure likelihood.Adaptive allocation in fuzzing and rare-event simulation provides precedent for concentrating effort on high-risk cases [30].Source: §2 · p. 3

3 Method

The method allocates a fixed trial budget across scenarios using pre-execution context and impact alongside observed failures. It evaluates allocation policies through paired offline replay on a collected airline-agent corpus.

3.1 Problem Formulation

  • Each scenario has a static context vector and impact score, while repeated trials yield failure outcomes, resource use, and an impact-weighted failure signal.The context is extracted from the task definition before trial selection; observed outcomes and resource use vary across trials.Source: §3.1 · pp. 3–4

3.2 Impact Score

  • Impact is assigned by a fixed, rule-based score from scenario context and is not updated from observed outcomes.The listed levels range from 1 for informational or read-only tasks to 5 for an expected irreversible action.Source: §3.2 · p. 4

3.3 Allocation Strategies

  • Baselines include uniform, random, failure-rate, and static risk-aware allocation; Thompson Sampling samples scenario failure probabilities, with a contextual variant informed by pooled logistic predictions.The contextual prediction is blended with each scenario’s own evidence, and the oracle ranks realized impact-weighted outcomes.Source: §3.3 · pp. 4–5

3.4 Corpus and Offline Replay Protocol

  • The offline replay uses 70 τ-bench airline scenarios and 824 trials generated with a GPT-4o agent and simulated user.Thirty replicates shuffle each scenario’s trials without replacement; identical seed schedules make per-replicate policy outcomes directly comparable, assuming trial order does not alter outcome distributions.Source: §3.4 · p. 5

3.5 Metrics and Statistical Procedure

  • The evaluation reports cumulative impact-weighted failures, raw failures, oracle-normalized and cost-normalized efficiency, and allocation to scenarios with no observed failures.Paired t-tests on per-replicate cumulative impact-weighted outcomes use Holm correction for comparisons across budgets and context variants.Source: §3.5 · p. 5

4 Results

Across 70 scenarios and 824 recorded trials, adaptive allocation finds more impact-weighted failures than uniform allocation when evaluation budgets are small. Its advantage narrows with larger budgets; analyses show how context, posterior exploration, cost, and avoidance of scenarios that never fail contribute to the results.

4.1 Main Result: Discovery at a Small Budget

  • At B = 50, TS-CONTEXTUAL recovers 86.1% of oracle-achievable discovery versus 24.9% for uniform, finding 3.46× more impact-weighted failures (215.4 vs. 62.2).The comparison uses the same 50 trials for each strategy.Source: §4.1 · p. 6, Table 1 · p. 6
  • By B = 700, adaptive strategies converge to 99.7–99.9% of the oracle, while uniform and random remain at 81–82%.The adaptive advantage shrinks as budget approaches corpus size; Figure 1 plots raw and oracle-normalized discovery across budgets.Source: §4.1 · p. 6, Figure 1 · p. 6

4.2 Supporting Analysis: Which Mechanism Helps, and When

  • At B ≤100, TS-CONTEXTUAL beats TS-ARM-ONLY (pHolm < 0.005); at B = 300 and 500, it beats RISK-AWARE by ∆Y = +76.1 and +45.8 (pHolm < 10^-8).The authors attribute the small-budget difference to context and the moderate-budget difference to posterior-based exploration; they report no advantage over either baseline at B=150–200.Source: §4.2 · p. 7, Table 2 · p. 7

4.3 Supporting Analysis: Cost in Dollars

  • At B = 50, TS-CONTEXTUAL finds 5.0× more impact-weighted failures per dollar than uniform (3207 vs. 636), while spending less ($0.067 vs. $0.098).The measured cost is logged user-simulator cost; agent-side spend is not included.Source: Table 3 · p. 7, §4.3 · p. 8

4.4 Supporting Analysis: Where the Saved Budget Comes From

  • At B = 50, TS-CONTEXTUAL spends 2.8% of its budget on trivial scenarios versus 34.2% for uniform; adaptive strategies’ trivial spend rises to 21–24% by B = 700.Trivial scenarios are those that never failed in any observed trial; the corpus base rate is 34.3%. Beyond B = 300, the authors say this rise reflects exhaustion of scenarios capable of producing discovery.Source: §4.4 · p. 8, Figure 2 · p. 8

4.5 Synthesis

  • The authors recommend contextual Thompson Sampling when budgets are small relative to the corpus and note that three features have no variance in this corpus.Thus, the residual-feature null concerns the 14 active features, not the full intended feature space.Source: §4.5 · pp. 8–9

5 Limitations

The conclusions are bounded by a single airline-agent benchmark, a fixed rule-based impact score, and modeling and measurement choices. The objective focuses on failure discovery, not every dimension of evaluation quality.

Scope

  • Results come from one interactive airline-agent environment with 70 scenarios, so failure patterns in other domains remain untested.The authors identify replication across benchmarks as the most important next step.Source: §5 · p. 9

Impact specification

  • The impact score Ii is rule-based and fixed, so it cannot infer a new failure’s severity from its trajectory.The authors identify a learned impact model as a more principled alternative.Source: §5 · p. 9

Modeling and resources

  • Independent-arm modeling ignores correlations between scenarios, while the contextual variant uses a plug-in empirical-Bayes approximation rather than a full posterior.The approximation may matter more at larger corpus sizes; the resource model also omits token use and wall-clock latency because these were not consistently logged.Source: §5 · p. 9

Objective

  • Higher failure discovery does not necessarily mean greater failure diversity, severity, representativeness, or diagnostic value.The study primarily optimizes discovery under a fixed evaluation budget.Source: §5 · p. 9

6 Conclusion

The paper treats trial scheduling as an evaluator-controlled resource-allocation problem and proposes risk-aware contextual Thompson Sampling. Its value is concentrated at tight budgets, while the authors identify extensions and cautions for broader use.

6 Conclusion

  • With 6% of the corpus’s trial budget, the policy recovers 86% of oracle discoveries, finds 3.5× what uniform allocation finds, and delivers 5× discovery per dollar.It also cuts effort on never-failing scenarios by an order of magnitude.Source: §6 · p. 9
  • Paired, Holm-corrected tests show that scenario context helps mainly in the cold-start regime, while posterior exploration helps at moderate budgets.The paper argues that benchmark trial schedules are worth optimizing, particularly when budgets are small.Source: §6 · p. 9
  • Future work includes trajectory-conditioned impact scoring, statistical sharing across related scenarios, cost-adjusted selection, more benchmarks, and objectives such as failure diversity and calibrated reliability.The current impact score is rule-based, and the contextual policy achieves cost efficiency without optimizing for it.Source: §6 · p. 9
  • An incomplete impact score could lead the policy to undersample consequential scenarios, and low allocation does not verify that a scenario is safe.The authors frame adaptive evaluation as a way to find failures faster, not a substitute for comprehensive coverage.Source: §6 · p. 9

A Feature-Composition Ablation

The ablation compares the full context vector with a version that removes features directly determining the impact score. No budget survives Holm correction, so the reported contextual advantage is not explained by redundancy with that score.

A Feature-Composition Ablation

  • No budget survives Holm correction across the seven-test family.This comparison tests whether the contextual advantage is explained by features that directly determine Ii.Source: A Feature-Composition Ablation · p. 12, Table 4 · p. 12
  • The contextual advantage reported in Section 4.2 is not explained by redundancy with the impact score.Source: A Feature-Composition Ablation · p. 12
  • Table 4 compares TS-CONTEXTUAL with the full 17-feature context against a 13-feature variant with impact-determining features removed.The table reports differences on unrounded per-replicate values and Holm-corrected p-values across seven tests.Source: Table 4 · p. 12

B Full Trivial-Scenario Allocation Sweep

Table 5 reports the fraction of evaluation budget spent on trivial, never-failing scenarios, by strategy and budget; 24 of 70 scenarios meet that definition.

B Full Trivial-Scenario Allocation Sweep

  • Table 5 organizes trivial-scenario budget fractions by strategy and budget.Source: Table 5 · p. 12
  • A trivial scenario is one that never fails; 24 of 70 scenarios (34.3%) are trivial by this definition.Source: Table 5 · p. 12
  • The sweep compares how much of each strategy’s evaluation budget goes to trivial scenarios at different budgets.Source: Table 5 · p. 12

C Per-Scenario Allocation

At maximum budget, adaptive strategies concentrate scenario pulls differently from uniform and random strategies, withdrawing from scenarios that never failed.

C Per-Scenario Allocation

  • At maximum budget, Figure 3 shows how each strategy distributes pulls across individual scenarios, making the concentration effect described in Section 4.4 visible at the scenario level rather than only through aggregate fractions.Source: C Per-Scenario Allocation · p. 12

D Context-Weight Ablation

The context-weight choice matters only at the smallest budget; at budgets of 100 or more, the tested settings are indistinguishable.

D Context-Weight Ablation

E Compute Resources

The compute appendix describes how trials were collected and replayed, while the assets appendix identifies the released artifacts and their licensing. The checklist reports the paper’s scope and headline result.

E Compute Resources

  • The 824 trials were collected using a GPT-4o tool-calling agent and GPT-4o simulated user through the τ-bench harness.All reported results use offline replay against the fixed corpus, with no model inference.Source: E Compute Resources · pp. 12, 14

F Assets and Licenses

  • The allocation layer changes which scenarios run and how often; it uses τ-bench’s 50 airline scenarios unmodified for execution plus 20 custom scenarios for outcome scoring.The benchmark is identified as τ-bench.Source: F Assets and Licenses · p. 14
  • The replay corpus and allocation and replay code are released under the MIT License.The corpus contains per-trial outcomes, resource counts, and measured cost.Source: F Assets and Licenses · p. 14

NeurIPS Paper Checklist

  • At 50 trials, the checklist reports 86.1% of oracle-achievable impact-weighted discovery for contextual Thompson Sampling versus 24.9% for uniform allocation.It also notes that the advantage is budget-dependent and vanishes as the budget approaches corpus size.Source: NeurIPS Paper Checklist · p. 15

2. Limitations

The paper identifies limits in its empirical scope, objective, assumptions, and impact framing. It presents an empirical study rather than formal theoretical results.

2. Limitations

  • The evaluation covers one domain—70 airline scenarios from one benchmark—and uses a fixed rule-based impact score and a discovery-only objective.The authors also note an independent-arm assumption, a plug-in empirical-Bayes approximation instead of a full posterior over the logistic link, and an incomplete resource model.Source: §2 · p. 15
  • The paper contains no theorems, lemmas, or formal claims requiring proof; it is a problem formulation and empirical study.The regret properties motivating Thompson Sampling are cited rather than re-derived.Source: §2 · p. 16
  • Concentrating evaluation on high-impact scenarios under-samples others and weakens reliability estimates for low-priority scenarios.The authors state that adaptive allocation is not a substitute for uniform coverage when the goal is an unbiased reliability estimate.Source: §2 · p. 19

Related papers

Loading 2609.38914v1…