Measuring the Unmeasurable: Markov Chain Reliability for LLM Agents

Phat T. Tran-Truong , Xuan-Bach Le (✉) {}^{\text{({\char 0\relax})}} · 2026

Read Measuring the Unmeasurable: Markov Chain Reliability for LLM Agents by Phat T. Tran-Truong , Xuan-Bach Le (✉) {}^{\text{({\char 0\relax})}} (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-24579.txt.

Introduction

Tran-Truong and Le argue that single benchmark scores hide how language-model agents actually succeed or fail over time. Their TraceToChain pipeline fits execution traces to an absorbing Markov chain, a model of step-by-step states ending in success or failure. It adds fit checks, credible intervals and bootstrap intervals to quantify uncertainty. Tests on seven controlled agent frameworks with a strict fit-test split show held-out reliability curves closely matching the model's predictions.

Catalog record

CREATORPhat T. Tran-Truong , Xuan-Bach Le (✉) {}^{\text{({\char 0\relax})}}
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE59064
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.24579

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Measuring the Unmeasurable: Markov Chain Reliability for LLM Agents Phat T. Tran-Truong , Xuan-Bach Le (✉) {}^{\text{({\char 0\relax})}} Abstract Large language model (LLM) agents increasingly operate as sequential software systems, but their reliability is often summarized by scalar benchmark metrics. Metrics such as pass @ ​ k @k , pass k , and the reliability decay curve (RDC) are useful summaries, but they do not identify the success-time distribution being estimated, test whether traces support that distribution, or quantify finite-trace uncertainty. We present TraceToChain , a reproducible pipeline that fits agent execution traces to an absorbing discrete-time Markov chain (DTMC), M ^ = ( Q ^ , R ^ ⊕ , R ^ ⊖ ) \hat{M}=(\hat{Q},\hat{R}_{\oplus},\hat{R}_{\ominus}) , with explicit diagnostics and uncertainty. The pipeline builds an automatic cluster taxonomy, estimates transitions with Laplace-smoothed maximum-likelihood estimation (MLE), checks fit with a composite Akaike information criterion (AIC) and Kolmogorov–Smirnov (KS) goodness-of-fit certificate, and reports Dirichlet-posterior credible intervals and non-parametric bootstrap intervals. We adapt classical reliability mathematics (Kemeny–Snell [ 17 ] , Cheung [ 7 ] , Goel–Okumoto [ 10 ] ) to agent traces. The resulting first-passage view reconciles metrics usually reported separately: pass @ ​ k @k , pass k , and the RDC are projections of one success-time distribution. On seven controlled MAST-style frameworks with a strict 50/50 fit/test protocol, held-out empirical RDCs overlay their analytic counterparts with max L ∞ RDC = 0.053 L_{\infty}^{\mathrm{RDC}}=0.053 (median 0.048 0.048 ). A two-sample KS test on the first-passage cumulative distribution function (CDF) accepts the fitted chain with p > 0.05 p>0.05 on 7 / 7 7/7 frameworks (min p = 0.78 p=0.78 ), and per-entry 95 % 95\% posterior and bootstrap intervals agree to ≈ 0.01 \approx\!0.01 at the median. † † footnotetext: {}^{\text{({\char 0\relax})}} Corresponding Author: Xuan-Bach Le ([email protected]) I Introduction Large language model (LLM) agents are deployed as sequential software systems, yet they are often evaluated by scalar outcomes. A deployed agent plans, calls tools, observes results, retries, and terminates in success or failure, as in ReAct-style and tool-using designs [ 38 , 26 ] . This shift toward autonomous interactive systems is increasingly visible across agent surveys [ 35 ] . Reliability for such systems is a question about first-passage behavior, finite-trace uncertainty, and model fit, not only a terminal pass rate. These are standard dependability and site reliability engineering (SRE) concerns [ 2 , 4 ] , but current LLM-agent benchmark summaries rarely state the reliability distribution being estimated or audit whether it fits the traces. This gap appears immediately in deployment. A fintech team may ship a ReAct-style refund agent [ 38 ] after measuring \mathrm{pass}@1=0.72 on \tau -bench [ 37 ] , then need to estimate reliability under a larger step budget, the end-to-end effect of a fallback search tool, or the relation between an internal \mathrm{pass}^{5} dashboard and SRE mean-time-between-failures (MTBF) language. These are ordinary questions for a sequential system, but a single pass rate does not answer them. We ask whether empirical agent traces can be turned into an audited reliability model for such queries without rerunning a benchmark for each horizon, local edit, or metric convention. Reliability question. Can empirical LLM-agent traces become an audited model for horizon queries, uncertainty, goodness-of-fit, and metric reconciliation? Figure 1 summarizes the gap. Scalar metrics leave horizon queries, local counterfactuals, and denominator choices outside the reported number. A fitted chain provides the shared object behind those questions by treating pass @k , pass k , and the reliability decay curve (RDC) as projections of one success-time distribution, where k denotes repeated trials. Question Scalar metric Fitted chain \hat{M} Q1. If d{=}8\!\to\!16 , what reliability? Re-run at each d . No interval or extrapolation. \mathcal{R}(d) on any grid (Prop. 1 ) + 95% interval. Q2. Add fallback search: \Delta R_{\infty} ? Re-run full benchmark for one new point. Bound \Delta R_{\infty} locally (Prop. 2 ). Q3. pass 5 vs. SRE-MTBF: which is right? Two denominators and ad hoc reconciliation. Both are marginals of one success-time distribution (Prop. 3 ). Fig. 1: Motivating example: a fitted absorbing chain turns one trace corpus into horizon, perturbation, and metric-reconciliation queries. We make this distribution explicit by modeling each execution as a trajectory in an absorbing discrete-time Markov chain (DTMC), with transient states for intermediate behavior and absorbing states for terminal success or failure. The fitted chain \hat{M}=(\hat{Q},\hat{R}_{\oplus},\hat{R}_{\ominus}) records intermediate transitions in \hat{Q} and state-specific exits in \hat{R}_{\oplus} and \hat{R}_{\ominus} . Reliability at a step horizon, local perturbation analysis, and metric reconciliation then become first-passage queries on the same model (Props. 1 , 2 , and 3 ). The main challenge is auditing: the chain must be fit from empirical traces, tested for goodness-of-fit, assigned finite-sample uncertainty, and connected to established metrics. We therefore adapt classical reliability mathematics to agent traces rather than adding another benchmark-specific score. Absorbing chains and the fundamental matrix N=(I-Q)^{-1} are due to Kemeny and Snell [ 17 ] and were used in software reliability by Cheung [ 7 ] . Perturbation analysis [ 31 , 12 ] and quantitative reliability modeling [ 32 ] provide the broader engineering context. The Goel–Okumoto and Musa–Okumoto models connect to reliability growth models [ 10 , 23 ] , while stochastic-monotone chains explain RDC shape [ 15 , 16 ] . In the rare-failure regime, the fitted agent chain recovers the Goel–Okumoto limit (Proposition 7 ). We instantiate this view as TraceToChain , an audited pipeline that fits an absorbing DTMC, attaches diagnostics and uncertainty, and reports common LLM-agent metrics as views of one success first-passage distribution. Our contributions are: (1) Trace-to-chain modeling. TraceToChain (§ IV , Algorithms 1 – 2 ) maps traces to a fitted absorbing DTMC with a composite Akaike information criterion (AIC) and Kolmogorov–Smirnov (KS) goodness-of-fit certificate. (2) Uncertainty and diagnostics. § IV-E gives Dirichlet-posterior and trace-level bootstrap intervals for the fitted chain and derived reliability quantities. (3) Held-out validation. A strict held-out validation on seven controlled MAST-style frameworks (simulation study SS9, § VIII-B ) obtains maximum RDC error L_{\infty}^{\mathrm{RDC}}=0.053 (median 0.048 ) and held-out KS p>0.05 on 7/7 frameworks (min p=0.78 ). (4) Metric unification. pass @k , pass k , and the RDC become projections of one success first-passage distribution, making their denominators explicit. Raw SWE-bench and \tau -bench trajectories require step-level feature data and remain future validation targets. The paper proceeds as follows. Related Work (§ II ) positions the problem, and Formalism (§ III ) and State Construction (§ IV ) define and fit the absorbing-chain model. Analytic Tools (§ V ) and Extensions (§ VI ) derive the main reliability results. Simulation Validation (§ VII ) and Empirical Case Studies (§ VIII ) evaluate the machinery, and the final sections discuss limits and implications (§ IX –§ XI ). II Related Work Prior work provides many of the ingredients for deployment reliability decisions, but not yet their combination. Reliability engineering contributes the vocabulary, agent benchmarks provide the trace setting, and probabilistic verification supplies model-based reasoning. The missing piece is an audited fit from LLM-agent traces: a model with uncertainty, diagnostics, and shared semantics for common metrics. TABLE I: Comparison of TraceToChain with related evaluation and verification frameworks. Approach Input Reliability semantics Diagnostics

Read the complete text