💻 computer science

Measuring the Unmeasurable: Markov Chain Reliability for LLM Agents

This paper introduces \textsc{TraceToChain}, a reproducible pipeline that models LLM agent execution traces as absorbing discrete-time Markov chains to unify disparate reliability metrics into a single success-time distribution while providing rigorous statistical diagnostics, uncertainty quantification, and high-fidelity empirical validation across multiple frameworks.

Original authors: Phat T. Tran-Truong, Xuan-Bach Le

Published 2026-04-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Phat T. Tran-Truong, Xuan-Bach Le

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are hiring a very smart, but sometimes confused, robot assistant to solve a complex puzzle. You give it a task, and it starts thinking, trying tools, making mistakes, and trying again. Sometimes it solves the puzzle; sometimes it gives up or crashes.

Currently, when we evaluate these AI agents, we usually just give them a single grade, like "72% success rate." It's like saying a car is "reliable" without knowing if it breaks down after 10 miles or 10,000 miles, or if a small change in the engine would make it crash.

This paper introduces a new way to measure these AI agents called TRACETOCHAIN. Instead of a single grade, it builds a detailed "map" of the agent's behavior to predict exactly how reliable it is under different conditions.

Here is how the paper explains it, using simple analogies:

1. The Problem: The "One-Number" Trap

Right now, we measure AI agents with simple numbers like "pass@k" (did it succeed if we let it try 5 times?) or "reliability decay" (does it get worse the longer it runs?).

The Analogy: Imagine you are a pilot. If someone tells you, "This plane has a 90% success rate," you don't know if that means it crashes every 10th flight, or if it only crashes when the weather is stormy. You can't answer questions like, "What happens if I add a new navigation tool?" or "How likely is it to succeed if I give it 20 minutes instead of 10?" just by looking at that one number.

2. The Solution: The "Absorbing Map"

The authors turn the agent's history (its "traces") into a Markov Chain.

The Analogy: Think of the agent's journey as a board game.
- Transient States: These are the "middle" squares where the agent is still working (e.g., "Planning," "Calling a Tool," "Reading an Error").
- Absorbing States: These are the "End Game" squares. Once you land here, the game stops. There are only two: Success (You win!) and Failure (Game Over).
- The Map: The authors create a map showing the probability of moving from one square to another. For example, if the agent is in the "Error" square, there is a 30% chance it goes back to "Planning," a 10% chance it goes to "Success," and a 60% chance it crashes to "Failure."

3. The "Audit" (Checking the Map)

You can't just draw a map and trust it. The paper introduces a strict audit process to make sure the map actually matches reality.

The Analogy: Imagine you are a cartographer drawing a map of a forest. Before you let hikers use it, you check two things:
1. Does the path make sense? (The paper uses a test called AIC to see if the agent's memory is short enough to be modeled simply, or if it needs a more complex map).
2. Does the map match the terrain? (The paper uses a test called KS to see if the predicted path matches the actual paths the agent took).
If the map fails these tests, the authors say: "Stop! Do not use this map for predictions." This prevents false confidence.

4. What This Map Lets You Do

Once the map is built and audited, it becomes a powerful tool for answering questions that the old "one-number" system couldn't handle:

The "Time Budget" Question: "If I give the agent 50 steps instead of 10, how much more likely is it to succeed?"
- The Paper's Claim: The map calculates this instantly without needing to run the agent 1,000 more times.
The "What-If" Question: "What if we add a 'fallback' tool that helps when the agent gets stuck?"
- The Paper's Claim: You can tweak the map (change the probabilities on the board game) and instantly see how much the success rate improves, without re-running the whole benchmark.
The "Unification" Question: "Are 'pass@5' and 'reliability decay' different things?"
- The Paper's Claim: No! They are just different views of the same map. The paper shows mathematically that all these different metrics are just looking at the same "First-Passage" distribution (the path from Start to Success) from different angles.

5. The Proof: Did it Work?

The authors tested this on seven different types of AI agent frameworks (like ReAct, Reflexion, and ToolFormer).

The Result: They split the data in half: they built the map on one half and tested it on the other half (which the map had never seen).
The Outcome: The map predicted the agent's success rate with very high accuracy (within about 5% error). The "audit" tests correctly accepted the good maps and rejected the bad ones.

Summary

The paper argues that we should stop treating AI agents like a coin flip (Heads/Tails) and start treating them like a journey with a map.

By turning raw data into a verified "Absorbing Markov Chain," we can:

Predict success over time.
Test changes (like new tools) without expensive re-runs.
Unify confusing metrics into one clear picture.
Audit the results to ensure we aren't fooling ourselves.

The authors emphasize that this is a conditional tool: it only works if the "map" passes the audit. If the agent's behavior is too chaotic to fit the map, the system correctly says, "We cannot predict this yet," rather than giving a misleading number.

1. Problem Statement

Large Language Model (LLM) agents are increasingly deployed as sequential software systems that plan, call tools, observe results, and retry. However, their reliability is currently evaluated using scalar benchmark metrics (e.g., pass@k, passk, and Reliability Decay Curves or RDC). These metrics suffer from three critical limitations:

Lack of Distributional Insight: They summarize outcomes into single numbers without identifying the underlying success-time distribution.
No Goodness-of-Fit: They do not verify whether the observed execution traces actually support the assumed distribution.
Ignored Uncertainty: They fail to quantify uncertainty arising from finite trace lengths, making it difficult to answer counterfactual questions (e.g., "What happens if we add a fallback tool?" or "How does reliability change with a larger step budget?").

The authors argue that reliability for LLM agents should be treated as a first-passage problem (how soon a run reaches success before failure) with explicit uncertainty and model validation, rather than a terminal pass rate.

2. Methodology: TRACETOCHAIN

The paper introduces TRACETOCHAIN, a reproducible pipeline that transforms raw agent execution traces into an audited Absorbing Discrete-Time Markov Chain (DTMC). The methodology consists of four main stages:

A. State Construction (Featurization & Clustering)

Input: Raw traces consisting of reasoning steps, tool calls, and observations.
Process:
1. Featurization: Steps are mapped to vector representations using rule-based features (e.g., tool type, error codes) or learned encoders.
2. Clustering: Agglomerative Ward linkage clusters these vectors into discrete transient states ( $S_T$ ). The number of clusters is selected via silhouette score.
3. Outcome Mapping: Traces terminate in either Success ( $\oplus$ ) or Fatal Failure ( $\ominus$ ), which serve as absorbing states.

B. Transition Estimation

Model: The system fits a DTMC $\hat{M} = (\hat{Q}, \hat{R}^\oplus, \hat{R}^\ominus)$ , where $\hat{Q}$ represents transitions between transient states, and $\hat{R}^\oplus, \hat{R}^\ominus$ represent probabilities of exiting to success or failure.
Estimation: Parameters are estimated using Laplace-smoothed Maximum Likelihood Estimation (MLE) to prevent zero probabilities for unobserved but plausible transitions.

C. Goodness-of-Fit (GoF) Protocol

To ensure the Markov abstraction is valid, the pipeline employs a composite diagnostic test:

Kolmogorov–Smirnov (KS) Test: Compares the empirical cumulative distribution function (CDF) of first-passage times (time to success) against the analytic CDF derived from the fitted chain.
Akaike Information Criterion (AIC): Compares the first-order Markov model against a second-order alternative to ensure memory requirements are met.

Decision: The chain is accepted only if $p_{KS} > 0.05$ and $\Delta AIC > 0$ . If rejected, the trace corpus must be segmented or re-featurized.

D. Uncertainty Quantification

The pipeline provides confidence intervals for all reliability metrics using:

Dirichlet Posterior Intervals: Derived from the Laplace-smoothed MLE to quantify parameter uncertainty.
Non-parametric Bootstrap: Resampling traces to estimate variability in the fitted chain.

3. Key Contributions & Theoretical Framework

A. Unification of Metrics

The paper proves that pass@k, passk, and the Reliability Decay Curve (RDC) are not competing metrics but projections of a single success-first-passage distribution:

RDC ( $R(d)$ ): Probability of success within $d$ steps.
$pass_k$ : Probability that $k$ independent trials all succeed ( $R_\infty^k$ ).
$pass@k$: Probability that at least one of $k$ trials succeeds ( $1 - (1-R_\infty)^k$ ).
Theorem: These relationships hold under i.i.d. assumptions; deviations indicate hidden correlations between trials.

B. Analytic Tools for Deployment

Using the fundamental matrix $N = (I - \hat{Q})^{-1}$ , the authors derive closed-form solutions for:

Horizon Reliability: Calculating $R(d)$ for any step budget without re-running benchmarks.
Perturbation Sensitivity: Estimating the impact of local changes (e.g., adding a fallback tool) on global reliability using first-order sensitivity analysis.
NHPP Limit: Showing that in rare-failure regimes, the fitted agent chain converges to the classical Goel–Okumoto Non-Homogeneous Poisson Process (NHPP) model, bridging modern agent reliability with classical software reliability theory.

4. Results & Validation

The authors validated TRACETOCHAIN through simulation studies and empirical case studies:

Simulation Study SS1 (Numerical): Verified that the closed-form reliability calculations match Monte Carlo simulations across various chain sizes.
Simulation Study SS7 (GoF Diagnostics):
- Correctly accepted 100% of traces generated from true 1st-order Markov chains.
- Correctly rejected 100% of traces generated from 2nd-order chains (where the AIC layer detected the dependency).
Simulation Study SS9 (Held-Out Validation):
- Tested on 7 controlled MAST-style frameworks with a strict 50/50 fit/test split.
- Results: The fitted chains accurately predicted the held-out Reliability Decay Curves.
  - Maximum $L_{RDC}^\infty$ error: 0.053 (Median: 0.048).
  - KS test p-values: All frameworks passed ( $p > 0.05$ ), with a minimum $p = 0.78$ .
- This demonstrates that the pipeline recovers the underlying success-time distribution without overfitting the training data.
Empirical Case Studies (SS6): Applied to 7 real-world agent frameworks (e.g., ReAct, Reflexion, ToolFormer). The pipeline successfully ranked frameworks by asymptotic reliability ( $R_\infty$ ) and visualized their specific RDC shapes.

5. Significance and Impact

From Scalar to Structural: Moves LLM agent evaluation from static scalar scores to a dynamic, auditable reliability model that captures the process of execution, not just the outcome.
Auditable Reliability: Provides a "certificate" (GoF tests + uncertainty intervals) for reliability claims, addressing the "black box" nature of agent evaluation.
Counterfactual Reasoning: Enables engineers to answer "what-if" questions (e.g., "How does adding a retry mechanism affect reliability?") using perturbation analysis on the fitted chain, avoiding the cost of re-running full benchmarks.
Metric Reconciliation: Resolves confusion between different benchmark metrics by showing they are mathematically linked projections of the same underlying distribution.
Practical Utility: The pipeline is ready for use with controlled trace data (like MAST), with future work planned for complex benchmarks like SWE-bench and $\tau$ -bench once stable step-level features are available.

In summary, TRACETOCHAIN provides a rigorous, mathematically grounded framework to transform raw LLM agent traces into a reliable, diagnostic, and predictive model of system dependability.