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

arXiv: https://arxiv.org/abs/2609.38914 · HTML: https://mlsanity.com/paper/2609.38914/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 33 references that are in the map.
- First posted on arXiv 30 Sep 2026.

## Builds on (most cited first, 19 of 19)

- [WebArena: A Realistic Web Environment for Building Autonomous Agents](https://mlsanity.com/paper/2307.13854/) (2023)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains](https://mlsanity.com/paper/2406.12045/) (2024)
- [AgentBench: Evaluating LLMs as Agents](https://mlsanity.com/paper/2308.03688/) (2023)
- [τ2-Bench: Evaluating Conversational Agents in a Dual-Control Environment](https://mlsanity.com/paper/2506.07982/) (2025)
- [Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling](https://mlsanity.com/paper/1802.09127/) (2018)
- [Neural Thompson Sampling](https://mlsanity.com/paper/2010.00827/) (2020)
- [MCP-Bench: Benchmarking Tool-Using LLM Agents with Complex Real-World Tasks via MCP Servers](https://mlsanity.com/paper/2508.20453/) (2025)
- [Mostly Exploration-Free Algorithms for Contextual Bandits](https://mlsanity.com/paper/1704.09011/) (2017)
- [TRAJECT-Bench:A Trajectory-Aware Benchmark for Evaluating Agentic Tool Use](https://mlsanity.com/paper/2510.04550/) (2025)
- [Parallelizing Thompson Sampling](https://mlsanity.com/paper/2106.01420/) (2021)
- [Beyond Task Completion: Revealing Corrupt Success in LLM Agents through Procedure-Aware Evaluation](https://mlsanity.com/paper/2603.03116/) (2026)
- [PG-TS: Improved Thompson Sampling for Logistic Contextual Bandits](https://mlsanity.com/paper/1805.07458/) (2018)
- [On Randomness in Agentic Evals](https://mlsanity.com/paper/2602.07150/) (2026)
- [Stochasticity in Agentic Evaluations: Quantifying Inconsistency with Intraclass Correlation](https://mlsanity.com/paper/2512.06710/) (2025)
- [On the Reliability of Computer Use Agents](https://mlsanity.com/paper/2604.17849/) (2026)
- [Thompson Sampling in Partially Observable Contextual Bandits](https://mlsanity.com/paper/2402.10289/) (2024)
- [How Many Tasks Are Enough for Agent Benchmark Decisions? A Replay Analysis of Public LLM Agent Benchmarks](https://mlsanity.com/paper/2607.12338/) (2026)
- [An adaptive importance sampling algorithm for risk-averse optimization](https://mlsanity.com/paper/2502.10084/) (2025)

## Abstract (arXiv)

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× more impact-weighted failures (215.4 vs. 62.2) with the same number of trials, delivers 5× 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.