Measuring the Unmeasurable: Markov Chain Reliability for LLM Agents Phat T. Tran-Truong
, Xuan-Bach Le(
)
arXiv:2604.24579v1 [cs.SE] 27 Apr 2026
Faculty of Computer Science and Engineering Ho Chi Minh City University of Technology (HCMUT), VNU-HCM Ho Chi Minh City, Vietnam {phatttt, lexuanbach}@hcmut.edu.vn
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, 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 T RACE T O C HAIN, a reproducible pipeline that fits agent execution traces to an absorbing discrete-time Markov chain (DTMC), M̂ = (Q̂, R̂⊕ , R̂⊖ ), 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 [1], Cheung [2], Goel–Okumoto [3]) 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, heldout empirical RDCs overlay their analytic counterparts with max LRDC = 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. Index Terms—software reliability, large language models, agent systems, absorbing Markov chains, fundamental matrix, pass@k, NHPP, reliability decay curve
I. I NTRODUCTION 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 [4], [5]. This shift toward autonomous interactive systems is increasingly visible across agent surveys [6]. 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 [7], [8], but current LLM-agent benchmark summaries rarely state the reliability distribution being estimated or audit whether it fits the traces. (
) Corresponding Author: Xuan-Bach Le ([email protected])
Question
Scalar metric
Fitted chain M̂
Q1. If d=8 → 16, what reliability?
Re-run at each d. No interval or extrapolation.
R(d) on any grid (Prop. 1) + 95% interval.
Q2. Add fallback search: ∆R∞ ?
Re-run full benchmark for one new point.
Bound ∆R∞ locally (Prop. 2).
Q3. pass5 vs. SRE-MTBF: which is right?
Two denominators and ad hoc reconciliation.
Both are marginals of one successtime distribution (Prop. 3).
Fig. 1. Motivating example: a fitted absorbing chain turns one trace corpus into horizon, perturbation, and metric-reconciliation queries.
This gap appears immediately in deployment. A fintech team may ship a ReAct-style refund agent [4] after measuring pass@1 = 0.72 on τ -bench [9], 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 pass5 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, passk , and the reliability decay curve (RDC) as projections of one successtime distribution, where k denotes repeated trials. 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 M̂ = (Q̂, R̂⊕ , R̂⊖ ) records intermediate transitions in
Q̂ and state-specific exits in R̂⊕ and R̂⊖ . Reliability at a step a) Classical SRE.: Classical software reliability gives horizon, local perturbation analysis, and metric reconciliation this paper its vocabulary and analytic tools. The dependability then become first-passage queries on the same model (Props. 1, taxonomy of Avižienis et al. separates reliability, availability, 2, and 3). safety, and failure semantics [7], while SRE practice [8] The main challenge is auditing: the chain must be fit from turns such concepts into measurable service objectives. Stateempirical traces, tested for goodness-of-fit, assigned finite- based reliability modeling is equally central: Cheung [2] used sample uncertainty, and connected to established metrics. We Markov chains for program-level software reliability, Trivedi therefore adapt classical reliability mathematics to agent traces and Bobbio [12] give a broader engineering treatment of rather than adding another benchmark-specific score. Absorbing reliability and availability modeling, and Kemeny and Snell [1] chains and the fundamental matrix N = (I − Q)−1 are developed the absorbing-chain framework and fundamental due to Kemeny and Snell [1] and were used in software matrix N = (I − Q)−1 used by our closed-form reliability reliability by Cheung [2]. Perturbation analysis [10], [11] quantities. Reliability-growth models provide a complementary and quantitative reliability modeling [12] provide the broader aggregate view through the Goel–Okumoto NHPP model [3] engineering context. The Goel–Okumoto and Musa–Okumoto and the Musa–Okumoto formulation [13]. These tools are not, models connect to reliability growth models [3], [13], while by themselves, a trace-level evaluation method for LLM agents; stochastic-monotone chains explain RDC shape [14], [15]. In Proposition 7 connects them by recovering the NHPP form as the rare-failure regime, the fitted agent chain recovers the a rare-failure scaling limit of the fitted agent chain. b) Agent benchmarks.: Agent benchmarks show why Goel–Okumoto limit (Proposition 7). We instantiate this view as T RACE T O C HAIN, an audited trace-level reliability semantics are needed. ReAct [4], Toolpipeline that fits an absorbing DTMC, attaches diagnostics and former [5], and Reflexion [22] established agent trajectouncertainty, and reports common LLM-agent metrics as views ries that interleave reasoning, tool use, and revision steps; of one success first-passage distribution. Our contributions are: ToolBench [23] and τ -bench [9] make API choice, tool (1) Trace-to-chain modeling. T RACE T O C HAIN (§IV, Algo- errors, and tool-agent-user interaction part of the evaluation rithms 1–2) maps traces to a fitted absorbing DTMC surface. SWE-bench [24], WebArena [25], ALFWorld [26], with a composite Akaike information criterion (AIC) and and Voyager [27] move evaluation further toward software, web, embodied, and open-ended environments where success Kolmogorov–Smirnov (KS) goodness-of-fit certificate. (2) Uncertainty and diagnostics. §IV-E gives Dirichlet- is long-horizon and context-dependent. MAST [28] diagnoses posterior and trace-level bootstrap intervals for the fitted multi-agent failure modes, and AgentBench [29] broadens the interactive evaluation space beyond one task family. Together, chain and derived reliability quantities. (3) Held-out validation. A strict held-out validation on seven these benchmarks expose the trace setting; they do not by controlled MAST-style frameworks (simulation study SS9, themselves unify the reported metrics. pass@k [16] originated §VIII-B) obtains maximum RDC error LRDC = 0.053 as a repeated-sampling success metric for code generation, and ∞ (median 0.048) and held-out KS p > 0.05 on 7/7 agent evaluation later adapted it alongside the reliability decay curve (RDC) [17]. In our formalism, the RDC is exactly the frameworks (min p = 0.78). k (4) Metric unification. pass@k, pass , and the RDC become d-step reliability R(d) from Definition 2. c) Formal methods for agents.: Formal methods supply projections of one success first-passage distribution, making the model-based reasoning layer. Probabilistic computation their denominators explicit. tree logic (PCTL) [30] supports reasoning about probabilistic Raw SWE-bench and τ -bench trajectories require step-level time and reliability properties, and model-checking texts [31] feature data and remain future validation targets. place such logics in a broader verification framework. Given The paper proceeds as follows. Related Work (§II) positions a probabilistic model, PRISM [18] and Storm [19] can the problem, and Formalism (§III) and State Construction verify PCTL properties. More recent trace-driven frameworks, (§IV) define and fit the absorbing-chain model. Analytic Tools including TriCEGAR [20] and ProbGuard [21], learn DTMC (§V) and Extensions (§VI) derive the main reliability results. or Markov decision process (MDP) abstractions from empirical Simulation Validation (§VII) and Empirical Case Studies traces. We therefore do not claim trace-to-DTMC abstraction (§VIII) evaluate the machinery, and the final sections discuss as the main theoretical novelty. Our focus is its reliabilitylimits and implications (§IX–§XI). engineering use for LLM agents: T RACE T O C HAIN fits an absorbing DTMC with a composite AIC ∧ KS goodness-of-fit II. R ELATED W ORK certificate and uncertainty quantification. Simulation study SS9 Prior work provides many of the ingredients for deployment (§VIII-B) evaluates controlled held-out recovery on a held-out reliability decisions, but not yet their combination. Reliability half of controlled MAST-style trace corpora using KS distance engineering contributes the vocabulary, agent benchmarks and LRDC error. The first-passage view explains why pass@k, ∞ provide the trace setting, and probabilistic verification supplies passk , and the RDC are restrictions of a single distribution model-based reasoning. The missing piece is an audited fit (Proposition 3), while the Goel–Okumoto NHPP appears as a from LLM-agent traces: a model with uncertainty, diagnostics, rare-failure scaling limit of the fitted chain (Proposition 7). This and shared semantics for common metrics. positions the work as reliability evaluation for LLM agents,
TABLE I C OMPARISON OF T RACE T O C HAIN WITH RELATED EVALUATION AND VERIFICATION FRAMEWORKS . Approach
Input
Reliability semantics
Diagnostics / uncertainty
LLM-agent fit
Classical SRE / NHPP [2], [3] Agent benchmark metrics [16], [17] PRISM / Storm [18], [19] TriCEGAR / ProbGuard [20], [21] T RACE T O C HAIN (this work)
Aggregate failures Outcomes / traces User model Empirical traces LLM-agent traces
Growth / failure intensity Success, pass@k, passk , RDC PCTL queries Learned Markov abstraction First-passage DTMC reliability
Aggregate intervals, no trace states Metric-specific, limited fit checks Verification, no trace fitting Refinement diagnostics AIC/KS diagnostics, posterior/bootstrap intervals
Indirect Direct / split Indirect Related Direct
not new Markov-chain theory. Positioning summary. Table I summarizes how these traditions align with T RACE T O C HAIN. The comparison is taxonomic rather than competitive: classical reliability models provide semantics, agent benchmarks provide traces, and probabilisticverification tools provide model-based queries. T RACE T O C HAIN’s distinction is the audited combination: traces define the estimate, diagnostics test the abstraction, uncertainty bounds the reported quantities, and first-passage semantics connect horizon reliability, perturbations, and common LLM-agent metrics. The result is a reliability argument from trace data rather than another scalar score.
Transient States Loop (ST ) execute
Reason / Plan
Call Tool API result
revise
Observe Output
crash
wrong correct timeout
Fatal Error (⊖)
Task Solved (⊕)
III. F ORMALISM Fig. 2. Conceptual translation from an agent’s interactive loop to a DTMC.
Deployment questions require probabilities that can be Reasoning phases become transient states, and each run eventually absorbs interpreted from traces. The operational question is simple: after into success or failure. an agent has spent several steps reasoning, calling tools, and observing outputs, what is the probability that it reaches success Q̂ ∈ [0, 1]|ST |×|ST | gives transitions among those states. The before failure? We represent that “think-act-observe” loop vectors R̂⊕ , R̂⊖ ∈ [0, 1]|ST | give absorption probabilities with a fitted absorbing discrete-time Markov chain (DTMC), into task-complete state ⊕ and fatal-failure state ⊖. Mass is following classical absorbing-chain and software-reliability conserved: Q̂1 + R̂⊕ + R̂⊖ = 1. Finally, s0 ∈ ST is the initial models [1], [2]. Intermediate agent behavior becomes transient state, or more generally an initial distribution π0 . Figure 3 execution states, and the two terminal outcomes are task visualizes a small AMC. success ⊕ and fatal failure ⊖. Reliability is then a first-passage question: how soon a run reaches the success absorber, and Definition 2 (Reliability). The d-step reliability is R(d; M̂ ) = whether failure arrives first. Pr[τ⊕ ≤ d | X0 = s0 ], where τ⊕ is the first time the chain This view also gives benchmark metrics a common semantics. reaches the success absorber. The asymptotic reliability is pass@k [16], passk , and the reliability decay curve (RDC) [17] R∞ = limd→∞ R(d; M̂ ). The Kemeny–Snell fundamental are all restrictions of one success first-passage distribution. matrix [1] is N = (I − Q̂)−1 . It counts expected visits to Figure 2 shows the trace-to-state interpretation used by the transient states before absorption and yields the closed form formal model. We write ST for the transient state set: the in Prop. 1. discrete labels used for intermediate reasoning, tool-use, and This first-passage view also connects the fitted chain to observation behavior before a run reaches one of the two classical reliability growth. A central software-reliability model absorbing outcomes. is the non-homogeneous Poisson process (NHPP), a countingThe fitted absorbing DTMC is a finite state-space summary process model for failure discovery over time, especially the of trace dynamics. We denote it by M̂ = (ST , Q̂, R̂⊕ , R̂⊖ , s0 ), Goel–Okumoto model [3]. Musa–Okumoto gives a related where Q̂ contains estimated transitions among transient states, reliability-growth formulation [13]. Under rare-failure scaling, R̂⊕ and R̂⊖ contain estimated exits to success and failure, and the fitted agent chain recovers this NHPP form as a limit s0 is the initial state. Later sections estimate these quantities (Proposition 7), which explains when classical reliabilityfrom traces and test whether the abstraction is adequate before growth estimators are meaningful for agent traces. using it for reliability claims. Model assumptions. The model makes four assumptions Definition 1 (Agent Markov chain). An agent Markov chain explicit. Transience means eventual absorption and gives the (AMC) is a tuple M̂ = (ST , Q̂, R̂⊕ , R̂⊖ , s0 ) with the follow- fundamental matrix. Invertibility is the algebraic condition ing components. ST is the finite set of transient execution needed for the closed forms. The initial condition fixes where states obtained from trace featurization (§IV). The matrix traces start, and i.i.d. replications are required when interpreting
A. Featurization and Discretization
Transient states ST
The first step is to turn heterogeneous trace events into countable states. In the running example, reasoning steps, tool calls, and observations are featurized and then clustered into labels such as “plan” or “tool result.” Let T = {τ (i) }ni=1 be ⊕ 0.3 0.2 (i) (i) (i) the trace corpus. A run is τ (i) = (σ1 , σ2 , . . . , σLi , y (i) ), (i) 0.1 where each σt is one observed step and y (i) ∈ {⊕, ⊖} is the s1 0.4 0.3 terminal outcome. A featurizer ϕ : σ 7→ Rp maps each step to 0.1 a vector representation, either: ⊖ 0.3 • rule-based (tool type, retry flag, error code, used in our simulation study SS7 and MAST experiments), or s2 0.1 0.6 • learned (a pretrained sentence encoder applied to the agent’s chain-of-thought and interchangeable in Algorithm 1). Fig. 3. Illustration of a fitted absorbing DTMC. Transitions among transient (i) states (matrix Q) model agent logic, while success and failure exit vectors We cluster the feature vectors {ϕ(σt )} using agglomerative R⊕ and R⊖ lead to absorbing states ⊕ and ⊖. Ward linkage [32]. The number of clusters m ∈ [kmin , kmax ] is selected by silhouette score [33]. Each step is assigned to the (i) (i) k pass@k and pass across repeated trials. The first-order Markov selected cluster, yielding s1 , . . . , sLi ∈ {1, . . . , m} followed property is not taken on faith: the order-selection and goodness- by the terminal outcome. of-fit tests in §IV-B and §IV-C report when the trace corpus B. Transition Estimation and Order Selection does not support the fitted absorbing DTMC. Once traces have state labels, estimating the fitted chain is Assumption 1 (Transience). ρ(Q̂) < 1. a counting problem with a direct operational interpretation. A row of Q̂ answers: after the agent is in this state, where does it Assumption 2 (Invertibility). (I − Q̂) is invertible. go next if it has not terminated? The corresponding entries of Assumption 3 (Initial condition). s0 is deterministic (exten- R̂⊕ and R̂⊖ answer how often the same state exits to success ⊤ sions replace e⊤ or fatal failure. We fit these quantities by Laplace-smoothed s0 by π0 ). k Assumption 4 (I.i.d. replications). For pass and pass@k, maximum-likelihood estimation (MLE) with α = 1, so Q̂ij = (cij + α)/(ci + α(m + 2)) where cij is the count of transitions trials are i.i.d. unless noted. from state i to state P j, ci,⊕ and ci,⊖ count terminal exits from Definition 3 (Local perturbation family). For sensitivity state i, and ci = j cij + ci,⊕ + ci,⊖ . The same denominator analysis, let Q(ε) = Q0 + ε∆ for 0 ≤ ε ≤ εmax , where rows normalizes the success and failure exits. Smoothing prevents remain substochastic and ρ(Q(ε)) < 1. The success-exit vector sparse rows from assigning zero probability to unobserved but R⊕,0 is held fixed, and any removed transient mass is assigned plausible exits. to the failure absorber so that Q(ε)1 + R⊕,0 + R⊖ (ε) = 1. We also test whether first-order memory is sufficient. The Operationally, this represents a local design change, such as comparison uses a first-vs-second-order Markov Akaike inforadding a fallback tool, without re-running the full benchmark. mation criterion (AIC) test [34]: ∆AIC = AIC2 − AIC1 = Remark. The fitted absorbing DTMC is not intended to recover −2(ℓ2 −ℓ1 )+2(k2 −k1 ), where ℓo and ko are the log-likelihood every hidden state of the agent or its environment. It is a and free-parameter count under order o. The first-order model is compact reliability model estimated from observable traces, preferred iff ∆AIC > 0. Simulation study SS7 (§VII-B) shows and its outputs are meaningful only when the state construction that this test has high power against second-order ground truth. a) Time-homogeneity as a testable assumption.: When and goodness-of-fit checks support the first-order absorbingwe pool transition counts, we assume a time-homogeneous DTMC approximation. kernel Pr[st+1 = j | st = i] that does not vary with t. The IV. S TATE C ONSTRUCTION FROM T RACES composite AIC ∧ KS protocol (Algorithm 2) tests whether that The formalism is useful only if traces can produce the simplification is defensible. AIC checks whether recent history fitted chain reproducibly and with checks that expose when still matters after conditioning on the current state, while the the abstraction fails. Trace tokens, tool calls, observations, Kolmogorov–Smirnov (KS) first-passage test can reveal drift in and context become state labels, transition counts, and exit exit hazards. If either test fails, the corpus should be segmented probabilities that can be inspected. A fitted Markov model is before counts are pooled. therefore an estimate plus evidence: the trace representation, b) Variable horizons, early termination, and censoring.: order test, first-passage fit, and uncertainty analysis must all sup- Runs can have different lengths and may end in success port its use. Algorithm 1 implements the construction pipeline, (⊕), failure (⊖), or right-censoring. Algorithm 1 counts each and Algorithm 2 gives the goodness-of-fit (GoF) protocol that observed transient transition once. Completed runs add one simulation study SS7 (§VII-B) checks on controlled corpora. absorber count, while censored runs contribute only the 0.5
s0
0.1
Algorithm 1: T RACE T O C HAIN: construct and audit an absorbing DTMC from agent execution traces.
Algorithm 2: Composite KS/AIC goodness-of-fit test for the agent-DTMC assumption.
Input: Traces T , featurizer ϕ, cluster range [kmin , kmax ], Laplace α. Output: Q̂, R̂⊕ , R̂⊖ , labels π, AIC order verdict.
Input: Traces T , fitted chain M̂ , threshold αKS = 0.05. Output: ACCEPT / R EJECT, (pKS , ∆AIC ). M̂ 1 Compute conditional analytic CDF Fτ |τ <τ ⊕ ⊕ ⊖ 2 Collect empirical FPTs from T⊕ (success traces) M̂ ) 3 pKS ← two-sample KS(F̂ , F 4 ∆AIC ← (Algorithm 1, step 4) 5 if pKS > αKS and ∆AIC > 0 then 6 return ACCEPT, (pKS , ∆AIC ) 7 else 8 return R EJECT, (pKS , ∆AIC ) 9 end
/* 1. Featurize and vector-stack 1
*/
(i)
X ← [ϕ(σt )]i,t /* 2. Ward clustering with silhouette-selected k
*/
for k = kmin to kmax do 3 Lk ← AgglomerativeWard(X, k) 4 silk ← silhouette(X, Lk ) 5 end ⋆ 6 m ← arg maxk silk ; π ← Lm⋆ 2
/* 3. Laplace-smoothed MLE (i)
*/ (i)
for each transition st → st+1 do 8 cst ,st+1 += 1 9 end (i) (i) 10 for each terminal exit sL → y do i 11 csL ,y(i) += 1 i 12 end ⋆ 13 Q̂ij ← (cij + α)/(ci + α(m + 2)) 14 R̂⊕,i , R̂⊖,i : same normalization against terminal counts. 7
D. Deterministic Guarantees and Sources of Nondeterminism Given ϕ, the cluster range, α, and a silhouette tie-breaking rule, Algorithm 1 is deterministic in the trace corpus. Algorithm 2 uses no simulation. The trace-generator seeds are included in the artifact submission.
E. Uncertainty Quantification on Q̂, R̂⊕ , R̂⊖ Algorithm 1 returns point estimates, but reliability quantities inherit uncertainty from the fitted chain. A small trace corpus may estimate a row of Q̂ or an exit probability poorly, and that uncertainty should be visible before a reviewer or operator transitions observed before censoring. This keeps Q̂ tied to interprets R(d), R∞ , or a perturbation result. We attach observed movement among transient states, but it can make intervals to Q̂, R̂⊕ , and R̂⊖ and propagate them to downstream the exit estimates R̂⊕ and R̂⊖ conservative when censoring is quantities (results 1–8). a) (i) Closed-form Dirichlet posterior.: Dirichlet insubstantial. In §VIII-A, we observe censoring below 10%, so tervals quantify row-wise probability uncertainty. The this correction is a small source of conservatism rather than a Laplace-smoothed MLE is the posterior mean under dominant driver of the fitted exits. a symmetric Dirichlet(α) prior over {s1 , . . . , sm , ⊕, ⊖}. The row-i posterior is Dir(ci,· + α1) and the marginal for any single entry Xi,j (including absorber columns) C. Goodness-of-Fit Protocol is P Beta(ci,j + α, ci + α(m + 2) − ci,j − α), where ci = ′ j ′ ci,j includes both transient and absorber outcomes. EqualFitting helps only if the abstraction matches the traces. A tailed (1 − αCI ) credible intervals (CIs) are the corresponding rejection is an engineering result, not a nuisance: it says the Beta quantiles. current state labels should not be used for reliability queries b) (ii) Non-parametric trace-level bootstrap.: Bootstrap without segmentation, new features, or a richer model. Given intervals quantify trace-sampling variability. We resample traces M̂ = (Q̂, R̂⊕ , R̂⊖ ), we use two checks that address different with replacement B times, assign each step to its nearest failure modes: target centroid to keep labels aligned, and recompute the MLE. Layer 1 (KS on first-passage). We compute the analytic The implemented full re-clustering path (fast=False) gives success first-passage-time (FPT) cumulative distribution funccomparable but wider intervals. tion FτM̂ , conditional on eventual success, and compare ⊕ |τ⊕ <τ⊖ c) Empirical ranges.: Table II reports representative it with the empirical distribution of success FPTs among MAST-derived state taxonomies. Cluster names come from successful traces using a two-sample KS test [35]. The null is dominant rule-based features (§IV-A), and posterior intervals retained iff pKS > 0.05. show which success exits are well estimated or sparse. The Layer 2 (AIC). The AIC layer asks whether the first-order differences are descriptive rather than causal, but they expose chain is adequate compared with a second-order alternative. state-level variation hidden by aggregate pass/fail rates. We reject the first-order model if ∆AIC < 0. Table III summarizes uncertainty on entries of Q̂. Posterior Composite rule. The chain is accepted iff both pKS > 0.05 and bootstrap median CI widths are close across frameworks, and ∆AIC > 0. This rule catches second-order dependence that while larger maximum widths identify sparse or unstable rows. the FPT-marginal KS test can miss (see §VII-B). If either layer All downstream R(d), mean time to absorption (MTTA), and fails, later reliability quantities should be treated as unsupported passk quantities inherit these CIs by propagation (Lipschitzby the current trace abstraction. continuous in (Q̂, R̂⊕ ) by Theorem 2). /* 4. Markov-order check
*/
Compute ℓ1 , ℓ2 , k1 , k2 ; ∆AIC ← −2(ℓ2 − ℓ1 ) + 2(k2 − k1 ) 16 return (Q̂, R̂⊕ , R̂⊖ , π, 1st-orderif∆AIC > 0) 15
TABLE II MAST- DERIVED STATE TAXONOMY AND 95% POSTERIOR INTERVALS FOR SUCCESS - EXIT PROBABILITIES . Cluster
react [4]
tool call (100%) 0.064 plan (100%) 0.076 retry (100%) 0.034 reflect (100%) 0.081 error parse (100%) 0.082 wait (100%) 0.057
[0.039,0.094] [0.048,0.109] [0.004,0.092] [0.038,0.138] [0.028,0.162] [0.007,0.153]
0.067 0.072 0.085 0.081 0.082 0.057
reflexion [22] plan (100%) 0.121 error parse (100%) 0.083 retry (100%) 0.054 reflect (100%) 0.104 0.097 tool call (100%) wait (100%) 0.128
[0.074,0.178] [0.041,0.138] [0.020,0.103] [0.056,0.166] [0.066,0.133] [0.049,0.236]
0.027 0.033 0.045 0.043 0.064 0.064
toolformer [5] retry (100%) 0.105 error parse (100%) 0.046 tool call (100%) 0.078 wait (100%) 0.073 plan (100%) 0.092 reflect (100%) 0.085
[0.057,0.164] [0.015,0.093] [0.053,0.108] [0.021,0.154] [0.050,0.145] [0.042,0.142]
0.048 0.028 0.062 0.036 0.050 0.068
Framework
Bootstrap CI width
min median max
min median max
react [4] 0.037 reflexion [22] 0.048 cot agent [6] 0.029 toolformer [5] 0.041 babyagi [6] 0.040 autogpt [6] 0.044 agentbench [29] 0.034
0.110 0.109 0.111 0.108 0.113 0.112 0.116
0.313 0.017 0.238 0.040 0.337 0.008 0.241 0.034 0.286 0.035 0.283 0.012 0.265 0.032
0.097 0.098 0.084 0.101 0.100 0.100 0.103
d→∞
(2)
B. Perturbation Sensitivity The second question is counterfactual: if a local transition changes, how much can end-to-end reliability move? For example, a new fallback tool may change one row of Q by redirecting failed tool calls back to planning. The fitted chain gives a first-order sensitivity calculation before a full benchmark rerun is available.
TABLE III P ER - FRAMEWORK 95% UNCERTAINTY WIDTHS FOR ENTRIES OF Q̂. Posterior CI width
R∞ = lim R(d) = e⊤ s0 N R⊕ .
Proof idea. The finite-horizon probability sums all paths that spend t = 0, . . . , d − 1 stepsP in transient states and then d−1 t exit to success: R(d) = e⊤ Q R⊕ . The geometric Pd−1 t s0 t=0 d −1 matrix identity gives (1), t=0 Q = (I − Q )(I − Q) d and transience gives Q → 0, yielding (2). Nij is the expected number of visits to state j before absorption. Thus the closed form separates two effects an operator can inspect: how often the agent visits each state and how likely success is after those visits.
R̂⊕,i 95% post. CI R̂⊖,i
Framework
and
Proposition 2 (Perturbation sensitivity; Stewart [10]). Let Q(ε) = Q0 + ε∆ be the perturbation family from Definition 3. Write N0 = (I − Q0 )−1 and let R⊕,0 be the fixed success-exit vector. Assume εmax ∥N0 ∥∞ ∥∆∥∞ < 1. For every 0 ≤ ε ≤ εmax ,
0.287 0.253 0.288 0.208 0.291 0.268 0.250
R∞ (ε) − R∞ (0) ≤ ε∥N0 ∥2∞ ∥∆∥∞ ∥R⊕,0 ∥∞ + Cε2 , (3) where C=
The output is the audited model used for reliability analysis: a fitted chain plus uncertainty and fit diagnostics. If AIC or KS rejects the fit, the corpus should be segmented, re-featurized, or treated as outside the absorbing-DTMC approximation. When both checks pass, the fitted chain can be used for reliability queries with the reported uncertainty intervals.
∥N0 ∥3∞ ∥∆∥2∞ ∥R⊕,0 ∥∞ . 1 − εmax ∥N0 ∥∞ ∥∆∥∞
Moreover, 2 R∞ (ε) − R∞ (0) = εe⊤ s0 N0 ∆N0 R⊕,0 + O(ε ).
(4)
Once a trace corpus has produced an accepted fitted chain, the next question is what the chain can answer without another full benchmark run. Three absorbing-chain tools address the deployment questions from the introduction: reliability at a horizon, sensitivity to a local change, and compatibility among common benchmark metrics.
Proof idea. Expand (I − Q(ε))−1 with the Neumann series around Q0 . The smallness condition makes the remainder bounded by the displayed constant. The first-order term is N0 ∆N0 . The left factor counts how often execution reaches the changed row, and the right factor measures success value after the perturbed transition. If ∥N0 ∥∞ is large, small local changes can have large global effects and should be checked empirically. The bound is best read as a screening calculation: it helps identify local changes that merit a new benchmark run. As stated, the bound applies to perturbations of Q with R⊕ fixed. Changes to success exits require the corresponding linear term for the exit vector.
A. Closed-Form Reliability
C. Metric Unification
The first deployment question is reliability under a step budget: starting at s0 , what is the chance of reaching ⊕ by step d? In the running loop, this asks whether the agent reaches a correct final answer within d reasoning/tool/observation steps.
The third question is semantic. pass@k, passk , and the RDC often appear to be competing summaries, but under the fitted chain they are different views of one first-passage distribution. The disagreement is usually about which projection to report, not about the underlying reliability event. We keep the benchmark name reliability decay curve (RDC), but the quantity modeled here is the cumulative success probability by horizon d.
V. A NALYTIC T OOLS
Proposition 1 (Closed-form reliability; Kemeny–Snell [1]). Under Assumptions 1–3, for every d ∈ N≥0 , d R(d) = e⊤ s0 (I − Q ) N R⊕ ,
N = (I − Q)−1 ,
(1)
Theorem 3 (Metric unification). Let R∞ = e⊤ s0 N R⊕ . Under the i.i.d. replication assumption A4, k passk = R∞ ,
(5) k
pass@k = 1 − (1 − R∞ ) ,
(6)
d RDC(d) = R(d) = e⊤ s0 (I − Q )N R⊕ .
(7)
Thus the three metrics are restrictions or transformations of the same first-passage distribution. Proof idea. The passk identity is the probability that all k independent trials succeed. pass@k is one minus the probability that all k trials fail, and the RDC is exactly the finite-horizon reliability from Proposition 1. The i.i.d. assumption is useful, but repeated agent runs can share latent conditions such as a common prompt template, cache state, or task difficulty. The following result makes that caveat measurable: it shows how shared variation changes the two repeated-trial metrics even when the marginal reliability remains R∞ . Theorem 4 (Correlated-trial inequalities). Suppose the k trials share a latent state ξ with Pr[Xi = 1 | ξ] = p(ξ) and Eξ [p(ξ)] = R∞ . Conditional on ξ, the trials are independent. Then
A convex window suggests a barrier, such as needing a tool response before the agent can make progress. The following condition captures the common early-gains/saturation pattern. Assumption 5 (Stochastic monotonicity of Q). Fix an order ⪯ on the transient states. The matrix Q is stochastically monotone if every non-increasing function f : ST → R≥0 remains nonincreasing after one step, i.e., Qf is non-increasing whenever f is. Equivalently, later rows of Q place stochastically more mass on later states in the order [36], [15]. Reliability cannot decrease with more steps, and concavity follows when success increments shrink over time. Proposition 6 (RDC shape; Keilson–Kester [15], Karlin–Rinott [37]). Let v = e⊤ s0 and w = R⊕ . For R(d) = v(I − Qd )N R⊕ , ∆R(d) = R(d + 1) − R(d) = vQd w ≥ 0,
(10)
and, for d ≥ 1, ∆2 R(d) = R(d+1)−2R(d)+R(d−1) = −vQd−1 (I −Q)w. (11) If A5 holds, w is non-increasing in the state order, and Qw ≤ w componentwise, then R(d) is globally concave.
Proof idea. The first difference is the probability of exiting to success exactly after d transient steps. The second difference pass@k = 1 − Eξ [(1 − p(ξ))k ] ≤ 1 − (1 − R∞ )k . (9) compares successive exit probabilities. Because vQd−1 is nonnegative, the displayed identity shows that Qw ≤ w is For k ≥ 2, equality holds iff p(ξ) is almost surely constant. enough to make the second difference nonpositive. Stochastic The inequalities show how hidden heterogeneity raises all- monotonicity and the ordering of w provide the structural success estimates and lowers at-least-one-success estimates condition under which this shrinkage is expected. A convex empirical window instead signals an early barrier or branch relative to the i.i.d. formulas. where more steps initially increase eventual success. k \k − R d Corollary 5 (Diagnostic). The gap pass is a ∞ lightweight diagnostic for hidden cross-trial correlation. Large B. NHPP Rare-Failure Limit positive gaps indicate that repeated trials are not behaving as The absorbing-chain view also explains when aggregate i.i.d. samples from one fixed chain. reliability-growth curves appear from step-level behavior. This Large gaps should trigger inspection before repeated samples is not a separate modeling story: it is a limiting case of the are treated as independent trials. For reliability evaluation, the fitted-chain view. The limit isolates the rare-failure regime point is practical: an assumption behind pass@k and passk where a one-state chain reduces to Goel–Okumoto. k passk = Eξ [p(ξ)k ] ≥ R∞ ,
(8)
becomes a diagnostic rather than a hidden convention. Proof idea. Condition on the latent variable and apply Jensen’s inequality to the convex functions pk and (1 − p)k . For an accepted fitted chain, these results give horizon, perturbation, and metric-reconciliation answers.
Proposition 7 (NHPP rare-failure limit; Goel–Okumoto [3]). Consider a sequence of one-transient-state agent chains with per-step success probability µn , per-step failure probability εn , and Qn = 1 − µn − εn . Suppose
VI. E XTENSIONS
εn /µn → 0.
µn → 0,
εn → 0,
dn µn → Λ ∈ (0, ∞),
The core tools answer immediate deployment questions. For any fixed c > 0 and d = cd , the cumulative first-passage n Three extensions help interpret the answers: why an RDC may CDF converges to saturate, when a classical reliability-growth curve emerges, and Rn (d) → 1 − e−cΛ . (12) how many steps are needed before R(d) is close to R∞ . A. RDC Shape
This is the Goel–Okumoto NHPP mean-value form m(t) = a(1 − e−bt ) with normalized a = 1.
An RDC is more useful when its shape has an explanation. In agent traces, a concave curve suggests that early steps resolve Proof idea. For the one-state chain, Rn (d) = d n 1 − (1 − µ − ε ) the easier cases and later steps add less new success probability. µnµ+ε . Under rare-failure scaling, n n n
the prefactor tends to one and the geometric term tends to e−cΛ . Outside this low-error regime, the exact closed form from Proposition 1 should be used.
10
50 Chain size m
100
Max absolute error
0.02
500
101
102 Chain size m (log scale)
1.00 0.50
0.005
0.25
0.000 0.00
0.05
0.10
0.15
0.20
0.25
0.00
1.0
passk gap
SS3 Correlation effect SS3 Correlation pass@k gap effect pass@k gap: mixture i.i.d.
1.25 0.75
0.010
q=0.7 q=0.9
pass@k gap: mixture i.i.d.
Count
0.015
q=0.1 q=0.3 q=0.5
passk gap: mixture i.i.d.
passk gap: mixture i.i.d.
1.50
0.020
Ratio=1 (tight) 0.020
0.020
1.75
0.025
q=0.1 0.000 q=0.7 q=0.3 q=0.9 q=0.5 0.025
0.050 0.015 0.015 0.075 0.100 0.010 0.010 0.125 0.150 0.005 0.005 0.175 0.200 0.000 0.000 1.5 2.0 2.5 2.5 5.0 7.5 3.010.0 2.5 12.5 5.0 15.0 7.5 17.5 10.0 20.0 12.5 15.0 17.5 20.02.5 Bound / true gap at = 0.1 k k
(a) Perturbation
pass@k gap
q=0.1 q=0.7 q=0.1 q=0.7 0.000 q=0.3 q=0.9 q=0.3 q=0.9 q=0.5 q=0.5 0.025 0.050 0.075 0.100 0.125 0.150 0.175 0.200 5.0 7.5 10.0 2.5 12.5 5.0 15.0 7.5 17.5 10.0 20.0 12.5 15.0 17.5 20.0 k k
(c) passk
(b) Agreement
Fig. 5. Additional theorem checks retained in the artifact: (a) perturbation bound behavior, (b) correlated-trial agreement lift, and (c) passk gap. SS4: NHPP Rare-Failure Limit = 0.2, = 0.0200, dn = 10
1.0
0.2
0.8
0.6
Exact R(d) = Pr[T d] (CDF, ) Goel--Okumoto 1 e c Survival S(d) = (1 )d ( )
0.4 0.2
0.0
0.2
0.4 0.6 c = d/dn
0.8
0.0
1.0
= 0.02, = 0.0020, dn = 100
1.0
0.2
0.4 0.6 c = d/dn
0.8
= 0.01, = 0.0010, dn = 200
0.2 0.2
0.4 0.6 c = d/dn
0.8
1.0
Exact R(d) = Pr[T d] (CDF, ) Goel--Okumoto 1 e c Survival S(d) = (1 )d ( )
0.4
0.0
0.2
0.4 0.6 c = d/dn
0.8
1.0
= 0.005, = 0.0005, dn = 400
0.8
0.6
0.2 0.0
0.0
1.0
probability
Exact R(d) = Pr[T d] (CDF, ) Goel--Okumoto 1 e c Survival S(d) = (1 )d ( )
0.4
Exact R(d) = Pr[T d] (CDF, ) Goel--Okumoto 1 e c Survival S(d) = (1 )d ( )
0.4
0.0
1.0
0.8
0.6
0.6
0.2 0.0
1.0
0.8
= 0.05, = 0.0050, dn = 40
1.0
probability
Exact R(d) = Pr[T d] (CDF, ) Goel--Okumoto 1 e c Survival S(d) = (1 )d ( )
0.4
0.0
= 0.1, = 0.0100, dn = 20
0.8
0.6
0.0
cumulative first-passage CDF R(d) converges to Goel--Okumoto.
1.0
0.8 probability
the gap is the same as bounding ∥Q ∥. Diagonalization gives ∥Qd ∥∞ ≤ κ∞ (V )ρd . Jordan blocks add a polynomial multiplier. Large ρ(Q) or ill-conditioned eigenvectors then imply longer step budgets. These checks connect finite-horizon reliability, classical reliability growth, and conservative step budgets within one fitted-chain view.
5% gate
Tightness of T2 boundSS3 (100 chains) effect Correlation SS3 Correlation passk gapeffect
2.00
0.030
probability
d Proof idea. The gap is R∞ −R(d) = e⊤ s0 Q N R⊕ , so bounding d
0.03
cf − R̂MC | between Fig. 4. SS1 closed-form validation: absolute error |R∞ ∞ analytic eventual-success reliability and Monte Carlo estimates across 500 chains per size. All errors are below the 5% G2 threshold.
True gap (blue) vs. T2 bound (red dashed)
For non-diagonalizable Q, the same exponential term is multiplied by a polynomial factor determined by the largest Jordan block.
VII. S IMULATION VALIDATION
5
(13)
where κ∞ (V ) = ∥V ∥∞ ∥V −1 ∥∞ . Therefore a sufficient horizon for error at most δ is log(κ∞ (V )∥N R⊕ ∥∞ /δ) ⋆ ddiag (δ) = max 0, . (14) − log ρ
0.04
0.01
0.00
|R ( ) R (0)|
R∞ − R(d) ≤ κ∞ (V )ρd ∥N R⊕ ∥∞ ,
0.01
probability
Proposition 8 (Approach-rate bound; Horn–Johnson [11], Stewart [10], Levin–Peres [38]). Let ρ = ρ(Q) < 1 and N = (I − Q)−1 . If Q = V ΛV −1 is diagonalizable, then
5% gate
0.02
probability
Even when R∞ is known, a practitioner still needs a step budget. The next result converts spectral decay of Q into a conservative horizon rule: how many more agent steps are needed before the remaining reliability gap is at most δ?
0.03
Max error across 500 chains
0.05
0.04 |R cf RMC|
C. Approach-Rate Bound
SS1: Closed-form vs. Monte Carlo (all sizes)
0.05
0.6
Exact R(d) = Pr[T d] (CDF, ) Goel--Okumoto 1 e c Survival S(d) = (1 )d ( )
0.4 0.2
0.0
0.2
0.4 0.6 c = d/dn
0.8
1.0
0.0
0.0
0.2
0.4 0.6 c = d/dn
0.8
1.0
Fig. 6. Goel–Okumoto rare-failure limit check: the cumulative first-passage distribution of the fitted-chain model approaches the NHPP mean-value form across six scaling regimes.
Before applying the fitted chain to benchmark-shaped data, we check the mechanics in controlled settings. Simulation study SS1 compares the closed-form reliability formula with The agreement stays within threshold across all tested stateMonte Carlo simulation. Figure 5 tests the perturbation and space sizes. SS1 is a narrow but necessary check: it supports correlated-trial claims, Figure 6 tests the Goel–Okumoto rarethe closed-form reliability computations used later in SS6 and failure limit, and simulation study SS7 checks that the GoF SS9, while leaving the Markov-fit question to the GoF protocol safeguard accepts and rejects controlled corpora for the right and held-out validation. reasons. These simulations do not validate unseen operational Figure 5 checks how the fitted chain should be used. Panel traces by themselves. They show that the computation, analytic (a) supports the intended use of Proposition 2: the perturbation claims, and diagnostics behave as intended on controlled inputs. bound screens local changes by their direction and scale before A. SS1: Closed-Form vs. Monte Carlo a full rerun. Panels (b) and (c) show that repeated attempts k SS1 isolates the numerical calculation behind the reliability require an explicit dependence assumption. Agreement, pass , estimates. Before fitting traces, choosing clusters, or applying and the independent-trial calculation are different projections the GoF protocol, we check whether the closed-form absorbing- of first-passage behavior, not interchangeable scalars. chain expression for eventual success agrees with direct Figure 6 keeps the Goel–Okumoto check separate because simulation. the source plot contains six scaling regimes. The insight is We generate 500 random substochastic chains per size m ∈ conceptual as much as numerical: when per-step absorption {5, 10, 50, 100, 500} and compare R∞ (Proposition 1) with probabilities become small and the horizon is rescaled, the Monte Carlo estimates from 105 trajectories per chain. Monte first-passage curve of the fitted chain approaches the classical Carlo is used as an independent simulation baseline for the NHPP mean-value form. Thus Goel–Okumoto appears as a same fitted chain, not as a competing estimator for agent limiting case of the agent-chain model, not as an unrelated reliability. historical baseline.
15 10 5 0
0.2
0.4 0.6 KS p-value
0.8
1.0
3.0 2.5 2.0 1.5 1.0 0.5 0.0
1st-order threshold
0
SS6: MAST Case Study
(C) MAST frameworks: per-framework GoF
agentbench autogpt babyagi toolformer cot_agent reflexion react
250 500 750 1000 1250 1500 AIC = AIC1 - AIC2
RDC per Framework toolformer (R =0.450) autogpt (R =0.387) agentbench (R =0.326) babyagi (R =0.285) reflexion (R =0.069) cot_agent (R =0.068) react (R =0.058)
0.4
0.0
0.2
0.4 0.6 KS p-value
0.8
(a) Markov ground truth:
(b) 2nd-order ground truth:
(c) MAST-derived:
KS p-values
AIC rejection
self-consistency KS
1.0
Fig. 7. SS7 tests the GoF safeguard across Markov ground truth, 2nd-order ground truth, and MAST-derived self-consistency conditions.
Reliability Decay Curve
count
(B) Non-Markov ground truth (mem=0.6) composite reject rate = 1.00
=0.05
R(d)
(A) Markov ground truth retain-null rate = 1.00 20
0.3 0.2 0.1 0.0 0
10
B. SS7: Goodness-of-Fit of the Agent-DTMC Assumption SS7 tests the goodness-of-fit protocol of §IV-C (Algorithm 2) on three controlled conditions. The goal is not to make every trace Markov, but to separate corpora where the fitted-chain abstraction is credible from those where it is not: (A) Markov ground truth. On 30 corpora of 300 traces from a known 1st-order absorbing chain (m = 5), the composite test retains the null in 100% of corpora at α = 0.05, confirming Type-I control. (B) 2nd-order ground truth. On 15 corpora from a 2ndorder chain with mixture weight 0.6, the FPT-KS layer alone rejects 0%, while the AIC layer rejects 100% with ∆AIC ∈ [−1540, −1310]. The composite accept-if-both-pass rule rejects 100%. (C) MAST-derived self-consistency. We sample 500 synthetic traces from each of the 7 MAST-derived chains used in §VIII-A. The composite test accepts all 7 frameworks (KS p-values ∈ {0.520, 0.583, 0.852, 0.944, 0.947, 0.957, 0.966}, ∆AIC small-positive). Because these traces are sampled from the fitted chain, this checks internal consistency, not whether real agent traces are Markov. The held-out study then checks whether the full trace-to-chain pipeline recovers first-passage behavior on controlled MAST-style traces it did not fit. As a validation ladder, SS1 checks numerical computation, Figures 5 and 6 check analytic claims about perturbations, correlated trials, and rare-failure limits, and Figure 7 checks the GoF safeguard. The validation ladder separates numerical correctness, analytic behavior, diagnostic behavior, and full held-out recovery of MAST-style first-passage behavior.
20
30 Horizon d (steps)
40
50
60
Fig. 8. SS6 illustrates finite-horizon reliability on MAST-derived summaries: reliability decay curves for 7 frameworks ranked by R∞ . TABLE IV C LOSED -F ORM R ELIABILITY OF MAST F RAMEWORKS . Framework toolformer [5] autogpt [6] agentbench [29] babyagi [6] reflexion [22] cot agent [6] react [4]
R∞
ρ(Q)
Horizon (δ = 0.01)
m
0.4497 0.3866 0.3262 0.2853 0.0695 0.0684 0.0581
0.442 0.370 0.654 0.656 0.636 0.526 0.509
5 4 9 8 5 3 3
10 5 10 12 12 10 9
illustrative: it does not claim that raw MAST traces are Markov, but it shows what the reliability vocabulary reports once a chain is available. Figure 8 shows each RDC. Table IV summarizes the closed-form reliability features. Toolformer has the highest asymptotic reliability in this illustrative MAST-derived summary, while react and reflexion have lower overall success. B. SS9: Held-Out Empirical Validation
Simulation study SS7(C) is an in-sample self-consistency check. SS9 instead evaluates controlled held-out recovery on MAST-style traces with a strict fit/test protocol. The test set is not used to choose features, clusters, transition estimates, or tuning, so the reported KS and RDC errors measure held-out recovery rather than reuse of the training corpus. VIII. E MPIRICAL C ASE S TUDIES a) Protocol.: For each of the 7 MAST-style frameworks The empirical evidence serves two different purposes. we generate n = 400 trajectories from a ground-truth absorbing Simulation study SS6 illustrates the reliability quantities on chain whose transient structure mimics the MAST taxonomy MAST-derived framework summaries, so its role is descriptive. and emits noisy one-hot features (Gaussian noise σ = 0.08 and Simulation study SS9 uses a strict held-out split on controlled ≈ 5% censored traces). The corpus is split before featurization MAST-style traces to test whether T RACE T O C HAIN recovers into n = 200 and n fit test = 200. We run T RACE T O C HAIN on the RDC and success-time distribution on unseen traces. This the fit half only. separation matters: SS6 shows what the reliability vocabulary Table V reports recovered state count m, KS agreement bereports, while SS9 tests recovery under a known data-generating tween the model success-time cumulative distribution function process. (CDF) FτM̂ , conditional on eventual success and sampled ⊕ |τ⊕ <τ⊖ A. MAST Benchmark Formulation with N =8,000 trajectories, and the held-out success-time CDF SS6 uses transition matrices derived from public MAST F̂τ⊕ among successful traces. The table also reports the supsummaries for seven frameworks, applies the fitted-chain norm discrepancy LRDC = supd∈[0,50] |R(d; M̂ ) − R̂emp (d)|. ∞ quantities, and ranks frameworks by R∞ . The exercise is These metrics are all first-passage checks: they ask whether
TABLE V H ELD - OUT VALIDATION ON SEVEN MAST- STYLE TRACE CORPORA .
nfit
Framework react [4] reflexion [22] cot agent [6] toolformer [5] babyagi [6] autogpt [6] agentbench [29]
ntest
200 200 200 200 200 200 200
m
200 200 200 200 200 200 200
DKS
5 5 5 5 6 6 5
pKS
0.017 0.031 0.024 0.024 0.047 0.032 0.032
1.000 0.992 1.000 1.000 0.776 0.987 0.988
TABLE VI TAXONOMY M APPING FOR C ROSS -B ENCHMARK A RCHETYPES .
LRDC ∞
Benchmark
State Taxonomy (ST )
0.048 0.052 0.018 0.052 0.053 0.039 0.021
SWE-bench [24]
repo_setup, issue_read, search, edit_file, test_run user_intent, api_call, api_resp, user_clarify, confirm think, act, observe
τ -bench [9] AgentBench [29]
SS7: Cross-Benchmark Generality (Archetype RDC)
react L =0.048, p=1.00
1.0 0.8 0.6 0.4 0.2 0.0 1.0 0.8 0.6 0.4 0.2 0.0
cot_agent L =0.018, p=1.00
reflexion L =0.052, p=0.99
toolformer L =0.052, p=1.00
(d) (analytic) emp(d)
babyagi L =0.053, p=0.78
0
10
20
30
budget d
autogpt L =0.039, p=0.99
40
50
0
10
20
30
budget d
40
agentbench L =0.021, p=0.99
50
0
10
20
30
budget d
40
50
SWE_bench (R = 0.395) tau_bench (R = 0.195) AgentBench (R = 0.170)
0.35 Trajectory Reliability R(d) (RDC)
reliability
0.40
0.30 0.25 0.20 0.15 0.10 0.05
Fig. 9. SS9 tests held-out recovery on controlled MAST-style traces: empirical RDC R̂emp (d) (dashed) over analytic R(d) from the fitted chain (solid). Per-panel titles report LRDC and pKS . ∞
0.00 0
5
10
15 20 Execution Steps d
25
30
the fitted chain predicts when success occurs on traces it did Fig. 10. Cross-benchmark archetypes show vocabulary portability: RDCs for not fit. synthetic state spaces modeling SWE-bench, τ -bench, and AgentBench. b) Empirical baseline.: The held-out empirical RDC R̂emp (d) is the non-parametric baseline for observed horizons. Table VI formalizes the mapping from benchmark-specific The fitted chain is useful only when it tracks that curve and behaviors to the Markov state space ST . passes GoF, and it adds state-level interpretation, uncertainty Using representative transition properties, we compute the propagation, perturbation analysis, metric reconciliation, and same analytic quantities. Figure 10 shows characteristic RDC horizon queries beyond the observed grid. behavior across the three archetypes. c) Findings.: Across all 7 frameworks, the composite These case studies support a narrower claim: when the diagnostic passes on held-out data at α = 0.05. KS distances diagnostics accept the trace-to-chain abstraction, the fitted are small (DKS ∈ [0.017, 0.047]), the minimum KS p-value is RDC chain provides a coherent reliability vocabulary for horizons, 0.776, and max L∞ = 0.053 with median 0.048. BabyAGI frameworks, and benchmark shapes, with the limits set by the has the largest RDC discrepancy yet still passes KS. This available trace representation and the GoF diagnostics. supports recovery of the success first-passage distribution and RDC for these controlled MAST-style traces. IX. T HREATS TO VALIDITY d) Scope.: SS9 uses synthetic traces from a genuine The main threat is overinterpreting the fitted abstraction. absorbing chain with noisy emissions, so the held-out KS Diagnostics and uncertainty reduce this risk, but the chain test probes controlled recovery by the trace-to-chain pipeline: remains a reliability model for specified trace features under featurization, clustering, Markov-order testing, and MLE. It specified diagnostics, not a universal model of agent behavior. does not prove that operational agent traces are Markov. The The estimates should therefore be read conditionally: they MAST release lacks the step-level features required by ϕ, and depend on the state construction, the empirical scope of the SWE-bench / τ -bench trajectories require stable step-feature traces, the independence of repeated trials, the population definitions before the same held-out split can be applied. covered by the case studies, and the regime in which the C. Cross-Benchmark Generalization NHPP limit is used. Agent evaluation spans diverse environments. To show that a) Construct validity (state construction).: Mapping trathe first-passage vocabulary is not tied to one taxonomy, we con- jectories to a DTMC necessarily aggregates over memory, tool struct synthetic archetypes for three benchmark shapes: SWE- state, and context, and no single mapping is canonical. §IV bench (software engineering) [24], τ -bench (conversational gives a reproducible construction whose output is tested by tool-use) [9], and AgentBench (multi-environment step-based Algorithm 2. Simulation study SS7 checks the protocol on reasoning) [29]. This is a portability exercise for the vocabulary, known synthetic chains, and SS9 checks controlled fit/test not empirical validation on raw benchmark trajectories. recovery. These studies establish statistical adequacy for the
chosen features, not uniqueness of ϕ, independence of repeated XI. C ONCLUSION trials, or coverage of all raw benchmark distributions. If GoF LLM-agent teams already collect traces, but scalar metrics rejects, first-passage interpretation should stop until traces are alone do not answer deployment reliability questions. T RACE segmented, re-featurized, or modeled with a richer process. We T O C HAIN turns those traces into an audited absorbing-chain therefore recommend reporting (ϕ, m, pKS , ∆AIC ) with each model with goodness-of-fit diagnostics and uncertainty. When estimate. Semi-Markov or hidden Markov models (HMMs) are the diagnostics accept the trace abstraction, the fitted chain supnatural next steps when the DTMC abstraction is rejected. ports horizon reliability, local perturbation analysis, and metric b) Empirical scope of SS9.: Simulation study SS9 uses reconciliation. The method combines a composite AIC ∧ KS synthetic traces from a true absorbing chain with noisy one-hot certificate, posterior and bootstrap intervals, and controlled emissions. The held-out KS test therefore evaluates controlled MAST-style held-out validation. On seven controlled MASTrecovery by the trace-to-chain pipeline (featurizer + clustering style frameworks, analytic and held-out empirical RDCs agree + MLE), rather than the full modeling class on unprocessed within max LRDC = 0.053, and pass@k, passk , and the RDC ∞ benchmark data. Applying the same split to SWE-bench [24] become projections of one distribution. The reliability claim is and τ -bench [9] requires step-level execution traces with stable therefore conditional but auditable: accepted trace abstractions feature definitions. give deployment-facing first-passage answers, while rejected c) Independence assumption.: The passk and pass@k abstractions should not be used for such conclusions. The main identities require i.i.d. trials (A4). This assumption can fail remaining step is to apply the same split to SWE-bench and under temperature-0 sampling or shared prefixes. Theorem 4 τ -bench trajectories once stable step-feature data are available. and Corollary 5 quantify the resulting bias and provide a diagnostic. R EFERENCES d) External validity.: The MAST case study covers 7 frameworks, so its conclusions may not generalize to other [1] J. G. Kemeny and J. L. Snell, Finite Markov Chains. Princeton, NJ: Van Nostrand, 1960. agents, tasks, or trace distributions. For this reason, SS6 is [2] R. C. Cheung, “A user-oriented software reliability model,” IEEE framed as illustrative rather than confirmatory. Transactions on Software Engineering, vol. SE-6, no. 2, pp. 118–125, 1980. e) NHPP-limit scope.: The NHPP limit applies under [3] A. L. Goel and K. Okumoto, “Time-dependent error-detection rate rare-failure scaling (ε → 0, d → ∞). In high-failure regimes model for software reliability and other performance measures,” IEEE (ε > 0.1), the exact closed form from Proposition 1 should be Transactions on Reliability, vol. R-28, no. 3, pp. 206–211, 1979. used instead. [4] S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y. Cao, “ReAct: Synergizing reasoning and acting in language models,” in Overall, the claims are conditional. The fitted chain is useful International Conference on Learning Representations, 2023. when the trace representation is appropriate, diagnostics pass, [5] T. Schick, J. Dwivedi-Yu, R. Dessı̀, R. Raileanu, M. Lomeli, L. Zettlemoyer, N. Cancedda, and T. Scialom, “Toolformer: Language models and uncertainty is acceptable for the deployment question. can teach themselves to use tools,” arXiv preprint arXiv:2302.04761, Otherwise, the fit should be rejected or replaced by a richer 2023. model. [6] L. Wang, C. Ma, X. Feng, Z. Zhang, H. Yang, J. Zhang, Z. Chen, J. Tang, X. D ISCUSSION For benchmark authors, SRE teams, and method developers, the fitted chain provides a shared reliability object at the trace level. It supports first-passage metrics with uncertainty, horizon and perturbation queries, and diagnostics that can reject an inadequate abstraction. Simulation study SS9 (Table V) shows that, once the trace-to-chain step is specified and checked, M̂ tracks held-out first-passage behavior to within LRDC ≤ 0.053 ∞ on controlled MAST-style trace corpora for seven frameworks. This evidence does not replace benchmarks or incident analysis. Rather, it shows how benchmark-style trace corpora can support auditable reliability answers while also identifying when the trace abstraction is too weak for those answers. The practical requirement is to fit the chain, report uncertainty, run GoF, and withhold first-passage conclusions when the checks fail. Future work will extend the same audited first-passage view to semi-Markov durations, HMM reliability under partial observability, and online estimation of Q. We will also study integration with PRISM and Storm and mixture-chain models for cross-trial correlation [39].
X. Chen, Y. Lin, W. X. Zhao, Z. Wei, and J.-R. Wen, “A survey on large language model based autonomous agents,” Frontiers of Computer Science, vol. 18, no. 6, p. 186345, 2024. [7] A. Avižienis, J.-C. Laprie, B. Randell, and C. Landwehr, “Basic concepts and taxonomy of dependable and secure computing,” IEEE Transactions on Dependable and Secure Computing, vol. 1, no. 1, pp. 11–33, 2004. [8] B. Beyer, C. Jones, J. Petoff, and N. R. Murphy, Site Reliability Engineering: How Google Runs Production Systems. Sebastopol, CA: O’Reilly Media, 2016. [9] S. Yao, N. Shinn, P. Razavi, and K. Narasimhan, “τ -bench: A benchmark for tool-agent-user interaction in real-world domains,” in Advances in Neural Information Processing Systems, 2024. [10] G. W. Stewart, Matrix Algorithms, Volume I: Basic Decompositions. Philadelphia, PA: SIAM, 1998, neumann-series perturbation bound on (I − Q)−1 . [11] R. A. Horn and C. R. Johnson, Matrix Analysis, 2nd ed. Cambridge, UK: Cambridge University Press, 2013, jordan-form norm bounds on ∥Qd ∥; see Thms. 3.1.12 and 5.6.12. [12] K. S. Trivedi and A. Bobbio, Reliability and Availability Engineering: Modeling, Analysis, and Applications. Cambridge, UK: Cambridge University Press, 2017. [13] J. D. Musa, A. Iannino, and K. Okumoto, Software Reliability: Measurement, Prediction, Application. New York, NY: McGraw-Hill, 1987. [14] S. Karlin, Total Positivity, Volume I. Stanford, CA: Stanford University Press, 1968, proves that TP2 kernels are stochastically monotone. [15] J. Keilson and A. Kester, “Monotone matrices and monotone Markov processes,” Stochastic Processes and their Applications, vol. 5, no. 3, pp. 231–241, 1977, formal definition of stochastic monotonicity for transition kernels.
[16] M. Chen, J. Tworek, H. Jun, Q. Yuan, H. P. d. O. Pinto, J. Kaplan, H. Edwards, Y. Burda, N. Joseph, G. Brockman, A. Ray, R. Puri, G. Krueger, M. Petrov, H. Khlaaf, G. Sastry, P. Mishkin, B. Chan, S. Gray, N. Ryder, M. Pavlov, A. Power, L. Kaiser, M. Bavarian, C. Winter, P. Tillet, F. P. Such, D. Cummings, M. Plappert, F. Chantzis, E. Barnes, A. Herbert-Voss, W. H. Guss, A. Nichol, A. Paino, N. Tezak, J. Tang, I. Babuschkin, S. Balaji, S. Jain, W. Saunders, C. Hesse, A. N. Carr, J. Leike, J. Achiam, V. Misra, E. Morikawa, A. Radford, M. Knight, M. Brundage, M. Murati, K. Mayer, P. Welinder, B. McGrew, D. Amodei, S. McCandlish, I. Sutskever, and W. Zaremba, “Evaluating large language models trained on code,” arXiv preprint arXiv:2107.03374, 2021. [17] A. Khanal, Y. Tao, and J. Zhou, “Beyond pass@1: A reliability science framework for long-horizon LLM agents,” arXiv preprint arXiv:2603.29231, 2026. [18] M. Kwiatkowska, G. Norman, and D. Parker, “PRISM 4.0: Verification of probabilistic real-time systems,” in Computer Aided Verification. Springer, 2011, pp. 585–591. [19] C. Dehnert, S. Junges, J.-P. Katoen, and M. Volk, “A storm is coming: A modern probabilistic model checker,” in Computer Aided Verification. Springer, 2017, pp. 592–600. [20] R. Koohestani, A. Görpelioğlu, E. Klimov, B. K. Ozkan, and M. Izadi, “TriCEGAR: A trace-driven abstraction mechanism for agentic AI,” arXiv preprint arXiv:2601.22997, 2026. [21] H. Wang, C. M. Poskitt, J. Wei, and J. Sun, “ProbGuard: Probabilistic runtime monitoring for LLM agent safety,” arXiv preprint arXiv:2508.00500, 2025. [22] N. Shinn, F. Cassano, E. Berman, A. Gopinath, K. Narasimhan, and S. Yao, “Reflexion: Language agents with verbal reinforcement learning,” in Advances in Neural Information Processing Systems, 2023. [23] Y. Qin, S. Liang, Y. Ye, K. Zhu, L. Yan, Y. Lu, Y. Lin, X. Cong, X. Tang, B. Qian, S. Zhao, L. Hong, R. Tian, R. Xie, J. Zhou, M. Gerstein, D. Li, Z. Liu, and M. Sun, “ToolLLM: Facilitating large language models to master 16000+ real-world APIs,” arXiv preprint arXiv:2307.16789, 2023. [24] C. E. Jimenez, J. Yang, A. Wettig, S. Yao, K. Pei, O. Press, and K. Narasimhan, “SWE-bench: Can language models resolve real-world GitHub issues?” in International Conference on Learning Representations, 2024. [25] S. Zhou, F. F. Xu, H. Zhu, X. Zhou, R. Lo, A. Sridhar, X. Cheng, T. Ou, Y. Bisk, D. Fried, U. Alon, and G. Neubig, “WebArena: A realistic web environment for building autonomous agents,” in International Conference on Learning Representations, 2024. [26] M. Shridhar, X. Yuan, M.-A. Côté, Y. Bisk, A. Trischler, and M. Hausknecht, “ALFWorld: Aligning text and embodied environments for interactive learning,” in International Conference on Learning Representations, 2021. [27] G. Wang, Y. Xie, Y. Jiang, A. Mandlekar, C. Xiao, Y. Zhu, L. Fan, and A. Anandkumar, “Voyager: An open-ended embodied agent with large language models,” arXiv preprint arXiv:2305.16291, 2023. [28] M. Cemri, M. Z. Pan, S. Yang, L. A. Agrawal, B. Chopra, R. Tiwari, K. Keutzer, A. Parameswaran, D. Klein, K. Ramchandran, M. Zaharia, J. E. Gonzalez, and I. Stoica, “Why do multi-agent LLM systems fail?” arXiv preprint arXiv:2503.13657, 2025. [29] X. Liu, H. Yu, H. Zhang, Y. Xu, X. Lei, H. Lai, Y. Gu, H. Ding, K. Men, K. Yang, S. Zhang, X. Deng, A. Zeng, Z. Du, C. Zhang, S. Shen, T. Zhang, Y. Su, H. Sun, M. Huang, Y. Dong, and J. Tang, “AgentBench: Evaluating LLMs as agents,” in International Conference on Learning Representations, 2024. [30] H. Hansson and B. Jonsson, “A logic for reasoning about time and reliability,” Formal Aspects of Computing, vol. 6, no. 5, pp. 512–535, 1994. [31] C. Baier and J.-P. Katoen, Principles of Model Checking. Cambridge, MA: MIT Press, 2008. [32] J. H. Ward, “Hierarchical grouping to optimize an objective function,” Journal of the American Statistical Association, vol. 58, no. 301, pp. 236–244, 1963. [33] P. J. Rousseeuw, “Silhouettes: A graphical aid to the interpretation and validation of cluster analysis,” Journal of Computational and Applied Mathematics, vol. 20, pp. 53–65, 1987. [34] H. Akaike, “A new look at the statistical model identification,” IEEE Transactions on Automatic Control, vol. 19, no. 6, pp. 716–723, 1974. [35] N. Smirnov, “Table for estimating the goodness of fit of empirical distributions,” Annals of Mathematical Statistics, vol. 19, no. 2, pp. 279–281, 1948.
[36] D. J. Daley, “Stochastically monotone Markov chains,” Z. Wahrscheinlichkeitstheorie verw. Gebiete, vol. 10, pp. 305–317, 1968, foundational paper on the stochastic-monotonicity notion used in A4. [Online]. Available: https://link.springer.com/journal/440/volumes-and-issues/10-4 [37] S. Karlin and Y. Rinott, “Classes of orderings of measures and related correlation inequalities. I. multivariate totally positive distributions,” Journal of Multivariate Analysis, vol. 10, no. 4, pp. 467–498, 1980, log-concavity of CDFs under TP2 kernels. [38] D. A. Levin and Y. Peres, Markov Chains and Mixing Times, 2nd ed. American Mathematical Society, 2017, pre-mixing constants in nonreversible chains (Thm. 12.3). [39] F. Spaeh, K. Sotiropoulos, and C. E. Tsourakakis, “ULTRA-MC: A unified approach to learning mixtures of markov chains via hitting times,” arXiv preprint arXiv:2405.15094, 2024.