Technical Summary: Consistency as a Testable Property

Problem Statement

While Large Language Model (LLM) agents have demonstrated remarkable capabilities in domains ranging from software engineering to complex reasoning, their deployment in high-stakes environments is hindered by a lack of behavioral consistency. Unlike deterministic software, LLM-based agents exhibit significant output variance when faced with semantically equivalent inputs due to sampling stochasticity and sensitivity to superficial prompt variations. Current evaluation methodologies primarily focus on task completion rates (e.g., pass@1) and accuracy on specific benchmarks. However, these metrics fail to capture whether agents produce coherent and reliable outputs when faced with variations in input formulation, context, or execution environments.

The paper highlights several critical limitations in current agent reliability:

• Fragility to Perturbations: Minor typographical errors or paraphrasing can cause significant drops in chain-of-thought reasoning accuracy.
• Tool Sensitivity: Agents with access to multiple tools exhibit erratic behavior when tool descriptions are modified or irrelevant tools are added, with accuracy dropping near zero under adversarial conditions.
• Contradictory Responses: Agents often produce contradictory responses across conversation turns, particularly under context length limitations or underspecified queries.
• Benchmark Contamination: Performance on static benchmarks (e.g., SWE-bench) often does not translate to continuously updated variants (e.g., SWE-bench-Live), suggesting a lack of true robustness.

Existing work lacks a standardized, rigorous framework to decompose and measure consistency at the level of agent execution trajectories, often focusing only on final outputs.

Methodology

The authors propose a rigorous measurement science for AI agent reliability based on statistical hypothesis testing. The framework decomposes reliability into two dimensions: observable (output-level) and internal (trajectory-level).

1. Output Consistency via U-Statistics

To measure consistency at the output level, the authors formalize the problem using U-statistics.

• Setup: Given a base prompt $x_0$ and a set of semantically equivalent perturbed variants $x_1, \dots, x_n$, the agent produces outputs $y_0, \dots, y_n$.
• Metric: A symmetric kernel function $k(y_i, y_j)$ measures the similarity between pairs of outputs (e.g., BLEU, ROUGE, entailment, or LLM-based judges).
• Estimator: The consistency is estimated by the U-statistic $U_n$, which is an unbiased estimator of the population parameter $\theta = E[k(Y, Y')]$.
• Hypothesis Testing: The framework tests the null hypothesis $H_0: \theta = 1$ (perfect consistency) against $H_1: \theta < 1$ (inconsistency). Theorem 1 and 2 establish that under specific assumptions (distributional invariance and homogeneous task distribution), the test statistic follows a normal distribution asymptotically, providing guarantees on size (false positive control) and power (detection sensitivity).

2. Trajectory Consistency via Kernel Methods

Recognizing that agents execute sequential decision-making processes, the framework extends to execution trajectories $\tau = (a_1, \dots, a_T)$.

• Stochastic Processes: Trajectories are treated as stochastic processes with variable lengths and temporal dependencies.
• Metric: The authors use Maximum Mean Discrepancy (MMD) in a Reproducing Kernel Hilbert Space (RKHS) to measure the distance between the distribution of base trajectories and perturbed trajectories.
• Kernels: To handle variable-length action sequences, the paper employs:
  • Jensen-Shannon Distance (JSD): Measures composition drift (proportions of tools used).
  • Levenshtein Distance (LD): Measures ordering drift (sequence stability).
  • Global Alignment Kernel (GAK): A positive-definite kernel that resolves the issue of non-negative definiteness in edit distances, providing a statistically valid analogue for MMD.
• Weighted Metrics: To capture the asymmetry of errors (where late-stage deviations are more consequential than early exploration), the authors introduce weighted Levenshtein distances, scaling edit costs by position.

3. Handling Multimodality

The framework addresses the issue where multiple valid solution strategies exist for a single task. It proposes a two-step approach: (i) identifying solution modes via spectral clustering on the GAK matrix, and (ii) measuring consistency within each mode to distinguish between legitimate strategy diversity and genuine instability.

Key Contributions

1. Foundational Framework: The paper establishes a principled statistical framework for quantifying agent consistency, distinguishing between core capability and execution robustness.
2. Theoretical Rigor: It provides formal proofs for the asymptotic normality of the proposed test statistics (Theorems 1–3), ensuring conservative false positive rates and high power for detecting true inconsistencies.
3. Diagnostic Granularity: By decomposing inconsistency into composition drift (what actions are taken) and ordering drift (how they are sequenced), the framework reveals architectural weaknesses invisible to output-only metrics.
4. Temporal Diagnostics: The introduction of weighted trajectory metrics allows for the identification of when agents deviate (front-loaded vs. back-loaded errors), offering specific guidance for architectural fixes.

Experimental Results

The framework was validated on three agentic benchmarks: SWE-bench Verified (software engineering), Spider2-DBT (data transformation), and BFCL (function calling). Experiments involved applying prompt-level (paraphrasing, back-translation, noise) and task-level (environment changes, schema shifts, decoy tools) perturbations.

• High Accuracy Masks Consistency Failures: Agents maintained relatively high output consistency (0.75–0.90) under prompt-level perturbations but exhibited significant degradation under task-level perturbations.
• Trajectory Metrics Reveal Hidden Failures:
  • SWE-bench: Under a "linear MCP" perturbation (changing information retrieval mechanisms), OpenHands+Kimi-K2 accuracy collapsed to ~25%, yet output consistency remained at 60%. Trajectory analysis revealed that while tool selection remained consistent (high JSD), the ordering of actions degraded significantly (low Levenshtein), indicating a failure in execution sequencing.
  • BFCL: Under an XML-format perturbation, OpenHands+Kimi-K2 accuracy dropped to near zero. Trajectory metrics showed a complete breakdown in both composition and ordering, revealing a hard-coded reliance on JSON parsing and an inability to generate valid XML.
  • Spider2-DBT: Codex showed high composition consistency but moderate ordering consistency under schema perturbations, suggesting the agent consistently produced the wrong answer for perturbed inputs.
• Perturbation Strength: Ablation studies showed that increasing perturbation strength (e.g., multiple paraphrasing passes) led to gradual declines in accuracy, while specific structural changes (e.g., dead-code injection) showed saturation effects, suggesting agents can ignore clearly unused code.

Significance and Claims

The paper claims to provide the "mathematical tools to isolate where and why agents deviate." Its significance lies in shifting the evaluation paradigm from "does the agent solve the task?" to "does the agent solve the task reliably under variation?"

• Diagnostic Sensitivity: The authors demonstrate that trajectory-level consistency metrics provide far greater diagnostic sensitivity than traditional pass@1 rates, exposing architectural brittleness that accuracy metrics obscure.
• Deployment Readiness: By identifying specific failure modes (e.g., sequencing errors vs. tool selection errors), the framework enables the identification and rectification of architectural concerns, which is a prerequisite for deploying agents in high-stakes, real-world environments.
• Limitations: The authors acknowledge that their approach relies on the assumption of semantic equivalence in perturbations, which is difficult to validate empirically. Furthermore, current trajectory analysis treats action sequences as the unit of consistency, ignoring intermediate reasoning states or belief updates, which would require access to internal model states not currently exposed by standard agent frameworks.

In conclusion, this work offers a rigorous, testable definition of agent reliability, moving beyond simple success rates to a nuanced understanding of how agents behave under stress, thereby providing a foundation for building more robust AI systems.