# Measuring the Unmeasurable: Markov Chain Reliability for LLM Agents

arXiv: https://arxiv.org/abs/2604.24579 · HTML: https://mlsanity.com/paper/2604.24579/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Software engineering coding agents, one of 16 directions in LLM agents and tool use.
- Builds on 18 of its 41 references that are in the map.
- First posted on arXiv 27 Apr 2026.

## Placed in

- LLM agents and tool use / [Software engineering coding agents](https://mlsanity.com/agents/software-engineering-coding-agents/)

## Builds on (most cited first, 18 of 18)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [A Survey on Large Language Model based Autonomous Agents](https://mlsanity.com/paper/2308.11432/) (2023)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [WebArena: A Realistic Web Environment for Building Autonomous Agents](https://mlsanity.com/paper/2307.13854/) (2023)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains](https://mlsanity.com/paper/2406.12045/) (2024)
- [AgentBench: Evaluating LLMs as Agents](https://mlsanity.com/paper/2308.03688/) (2023)
- [ALFWorld: Aligning Text and Embodied Environments for Interactive Learning](https://mlsanity.com/paper/2010.03768/) (2020)
- [Why Do Multi-Agent LLM Systems Fail?](https://mlsanity.com/paper/2503.13657/) (2025)
- [A storm is Coming: A Modern Probabilistic Model Checker](https://mlsanity.com/paper/1702.04311/) (2017)
- [ProbGuard: Proactive Runtime Monitoring for LLM Agent Safety via Probabilistic Prediction](https://mlsanity.com/paper/2508.00500/) (2025)
- [Beyond pass@1: A Reliability Science Framework for Long-Horizon LLM Agents](https://mlsanity.com/paper/2603.29231/) (2026)
- [ULTRA-MC: A Unified Approach to Learning Mixtures of Markov Chains via Hitting Times](https://mlsanity.com/paper/2405.15094/) (2024)
- [TriCEGAR: A Trace-Driven Abstraction Mechanism for Agentic AI](https://mlsanity.com/paper/2601.22997/) (2026)

## Built on by (most cited first, 2 of 2)

- [Why Retrying Fails: Context Contamination in LLM Agent Pipelines](https://mlsanity.com/paper/2605.08563/) (2026)
- [Uncertainty Quantification for LLM Agents: A Taxonomy, an Evaluation Protocol, and an Empirical Study](https://mlsanity.com/paper/2609.07395/) (2026)

## Abstract (arXiv)

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, passk, 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 textscTraceToChain, a reproducible pipeline that fits agent execution traces to an absorbing discrete-time Markov chain (DTMC), 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~citekemenysnell, Cheung~citecheung1980, Goel--Okumoto~citegoelokt) to agent traces. The resulting first-passage view reconciles metrics usually reported separately: pass@k, passk, 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 (median 0.048). A two-sample KS test on the first-passage cumulative distribution function (CDF) accepts the fitted chain with p>0.05 on 7/7 frameworks (min p = 0.78), and per-entry 95% posterior and bootstrap intervals agree to ≈!0.01 at the median.