TraceToChain: Auditing LLM-Agent Reliability with Absorbing Markov Chains

Abstract

Large language model (LLM) agents are sequential software systems, yet their reliability is reported as scalar benchmark scores — pass@k, pass k , and the reliability decay curve (RDC) — that neither identify the success-time distribution being estimated nor test whether traces support it, leaving horizon, counterfactual, and metric-reconciliation questions unanswerable. We present TraceToChain , a reproducible pipeline that fits agent traces to an absorbing discrete-time Markov chain (DTMC) by Laplace-smoothed maximum likelihood, gates every result behind a composite Akaike information criterion (AIC) and Kolmogorov–Smirnov (KS) certificate, and attaches Dirichlet-posterior and bootstrap intervals. Horizon reliability, local perturbation, and metric reconciliation become first-passage queries on one model, so pass@k, pass k , and the RDC stop competing and become projections of a single success-time distribution. We evaluate it under a strict 50/50 fit/test protocol on seven controlled MAST-style corpora and on 2,459 real episodes: 479 SWE-bench Verified SWE-agent trajectories and 1,980 τ-bench episodes over two models and two domains. On held-out controlled traces the fitted chain reproduces the RDC to a maximum L ∞ error of 0.053 and passes the first-passage KS test on 7/7 frameworks (minimum p = 0.83). On real traces the certified asymptotic reliability recovers the held-out pass rate to within 0.03 on SWE-bench and to a mean absolute error of 0.0075 across four τ-bench corpora, and one fitted chain yields pass@k, pass k , and closed-form perturbation answers (ΔR ∞ = +0.034 for a fallback tool) with no benchmark rerun. The certificate states exactly which outputs the evidence supports, and its verdict is invariant across 18 clustering configurations of the real corpus. LLM-agent reliability engineering can thus move from scalar scores to an audited model that identifies its own trustworthy outputs. Keywords: software reliability, large language models, agent systems, absorbing Markov chains, goodness-of-fit, model auditing, first-passage time, pass@k, reliability decay curve

Cite this paper

@inproceedings{tran2026tracetochain,
  author    = {Tran-Truong, Phat Tuan and Le, Xuan-Bach},
  title     = {TraceToChain: Auditing LLM-Agent Reliability with Absorbing Markov Chains},
  booktitle = {Proceedings of the 37th IEEE International Symposium on Software Reliability Engineering (ISSRE 2026)},
  year      = {2026},
  address   = {Limassol, Cyprus}
}