A Hierarchical Statistical Framework for Evaluating Agent Reliability

Mirco Milletarì, Tuhin KunduarXiv 2026 · arXiv

TL;DR

This paper introduces a hierarchical statistical framework to evaluate LLM agents, moving beyond simple "pass rate" scores to distinguish between execution noise and task difficulty. By providing exact variance formulas for metrics like $pass@k$ and $\widehat{pass}^k$, the authors offer a principled way to quantify agent reliability and determine if performance gains are statistically significant or just sampling noise.

What Problem Does This Paper Address?

Evaluating AI agents is notoriously difficult because they are inherently stochastic. If you run the same agent on the same task twice, you might get two different results due to the randomness of the underlying Large Language Model (LLM) or the environment.

Current benchmarks often report a single "state-of-the-art" (SOTA) number without quantifying uncertainty. This leads to two major issues:

  1. The Noise Problem: When one model beats another by 2%, is it actually better, or did it just get lucky during the evaluation run?
  2. The Aggregation Problem: A single average score hides the difference between an agent that fails because a task is fundamentally too hard (task heterogeneity) and an agent that fails because it is inconsistent (execution noise).

The authors argue that for agents to be production-ready, we need to know not just how often they succeed, but how reliably they succeed.

Methods

The authors propose a hierarchical structure for evaluation:

  • Scenario: A broad context (e.g., "Banking Support") with specific tools.
  • Instance: A specific task within that scenario (e.g., "Transfer $50 from account A to B").
  • Sample: A single attempt to solve an instance.

To analyze this, they borrow the concept of coarse-graining from statistical physics. As you move up the hierarchy (from samples to instances to scenarios), you average out the "microscopic" details. While this gives a clear "macroscopic" view of performance, it can hide critical failures at the task level.

The core mathematical contribution is the application of the Law of Total Variance to decompose uncertainty into two parts:

  1. Within-instance variability: Noise from repeated attempts at the same task.
  2. Between-instance variability: Differences in difficulty across different tasks.

Crucially, the paper derives exact finite-sample expressions for the sampling variances of unbiased estimators for $pass@k$ (the probability of succeeding at least once in $k$ tries) and $\widehat{pass}^k$ (the probability of succeeding $k$ times in a row).

Datasets

The framework was tested using:

  • Thinkingbox: A recently introduced benchmark designed for agents in stateful business workflows (e.g., retail, healthcare, finance).
  • Qwen-3.8-27b: The authors compared a "base" version of this model against a version improved via Reinforcement Learning from Feedback (RLFT).

Key Insights and Ideas

  • Repeated attempts are not new tasks: A common mistake in evaluation is treating 100 attempts at one task as equivalent to 1 attempt at 100 different tasks. The authors show that this "pooled" approach severely underestimates uncertainty—in their toy model, by a factor of nearly 3x.
  • Coverage vs. Reliability: The paper distinguishes between these two concepts. $pass@k$ (for large $k$) measures coverage—can the model solve this at all if given enough tries? $\widehat{pass}^k$ measures reliability—will it solve it consistently every time?
  • The "Goldilocks Zone": By looking at the distribution of pass rates, the authors found that RLFT training primarily helps models become more reliable on tasks of moderate difficulty (the Goldilocks Zone) rather than expanding the frontier to solve fundamentally harder tasks.

Key Results

  • RLFT Impact: In the Banking Support scenario, the RLFT model showed a significant improvement in the mean pass rate (+14.5%). However, when looking at $pass@20$ (coverage), the difference between the base and RLFT models was statistically insignificant. This proves the fine-tuning made the model more consistent on tasks it could already solve, rather than making it smarter at solving new ones.
  • Localized Regressions: The hierarchical view revealed that even when a model's overall score improved, it actually got worse on specific individual tasks. These "regressions" are completely invisible in standard aggregate reporting but are vital for developers to catch before deployment.

Limitations and Future Work

  • Binary Outcomes: The current framework focuses on binary success/failure. The authors note that extending this to continuous rewards (like partial credit) is a natural next step.
  • Execution Independence: The model assumes that repeated attempts at a task are independent. In some real-world scenarios, agents might have "memory" or state persistence that violates this assumption.
  • Budget Allocation: A major open question is how to best spend a compute budget: is it better to test more unique tasks once, or fewer tasks many times? The authors suggest their variance formulas could help optimize this trade-off in the future.

Summary updated

Abstract

Agents operating in complex scenarios often face uncertainty due to incomplete information about the environment they operate in, ambiguous user queries, complex business rules and the inherently stochastic dynamics of the governing policy. Several new benchmarks have been proposed to evaluate LLM-based agents on complex tasks in multi-tool environments, including settings with policy constraints and varying levels of intent ambiguity. These conditions make it important to evaluate agentic systems systematically and quantify their performance under different conditions to assess their reliability in production. This need is evident in the recently introduced Thinkingbox benchmark, where even the strongest models struggle to perform consistently across diverse business scenarios. This paper presents a statistical framework for evaluating uncertainty and reliability in agentic systems. We define a hierarchy of scenarios, instances, and samples to assess model performance and variability systematically. We apply this framework to common metrics found in the literature: mean pass rate, $pass@k$, and $passhat^k$, with uncertainty estimates for each metric. Aggregating metrics at different levels of the hierarchy reveals different structures and properties of the policy model; we connect this hierarchical aggregation with the known process of \emph{coarse-graining} as intended in the physics and statistical literature. We independently derive exact finite-sample expressions for the sampling variances of the unbiased $pass@k$ and $passhatk$ estimators; related results also appear in recent submissions. Our central contribution is a constructive derivation of hierarchical uncertainty propagation, making explicit its correspondence with coarse-graining and separating execution noise from task heterogeneity.
BibTeX
@misc{milletari2026hierarchical,
  author = {Mirco Milletarì and Tuhin Kundu},
  title = {{A Hierarchical Statistical Framework for Evaluating Agent Reliability}},
  year = {2026},
  eprint = {2611.19614},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.19614},
}
Figure