Automata from Agent Traces: Failure and Next-Step Prediction

# Automata from Agent Traces:Failure and Next-Step Prediction
Source: [https://arxiv.org/html/2608.23670](https://arxiv.org/html/2608.23670)
Franklin Cardenoso FernandezAffiliation:Holistic AIAffiliation:PUC\-RioUmar MohammedAffiliation:Holistic AIZekun WuAffiliation:University College LondonKleyton Da CostaAffiliation:University College LondonIlham WicaksonoAffiliation:Holistic AIAdriano KoshiyamaAffiliation:University College London

###### Abstract

LLM\-based agents execute multi\-step tasks, but their behavioral structure remains opaque: long unstructured traces resist the safety auditing and runtime monitoring that deployment requires\. Existing approaches operate per\-trace or success\-only, so they miss the cross\-run topology that links*next\-step*and*failure*prediction\. To recover that shared structure, we collapse an entire trace corpus into a single, compact finite\-state machine \(FSM\) that serves as a structural substrate for the otherwise unpredictable behavior of LLM agents\. Across twelve public datasets, the FSMs are compact \(7–43 states\), replay held\-out data at≥\\geq0\.997 fitness with near\-identical topology across splits, and build in milliseconds\. This substrate addresses both prediction goals\. For*next\-step prediction*, FSM\-state context outperforms Agent Workflow Memory on every ground\-truth\-matched dataset\. For*failure prediction*, per\-state behavioral features reach held\-out AUROC up to 0\.94, and an online monitor ranks failing runs above passing ones from a partial trace, triggering early stopping well before completion\. Behavioral topology thus appears shaped more by the deployment harness than by the LLM, providing a model\-agnostic structural primitive for safety auditing and runtime monitoring\.

###### Keywords:

LLM agents, agent monitoring, failure prediction, finite state machines

## 1Introduction

As LLM\-based agents\([Wang et al\., 2024](https://arxiv.org/html/2608.23670#bib.bib35);[Sumers et al\., 2024](https://arxiv.org/html/2608.23670#bib.bib42)\)take on longer reasoning chains and broader action spaces, the risk of undetected failures scales with their autonomy\. These agents now resolve GitHub issues\([Yang et al\., 2024](https://arxiv.org/html/2608.23670#bib.bib16);[Yang et al\., 2025](https://arxiv.org/html/2608.23670#bib.bib10)\), navigate websites\([Deng et al\., 2023](https://arxiv.org/html/2608.23670#bib.bib17);[Zhou et al\., 2024](https://arxiv.org/html/2608.23670#bib.bib11);[Koh et al\., 2024](https://arxiv.org/html/2608.23670#bib.bib41)\), operate desktop environments\([Xie et al\., 2024](https://arxiv.org/html/2608.23670#bib.bib40);[Wang et al\., 2025c](https://arxiv.org/html/2608.23670#bib.bib30)\), manage customer service interactions\([Yao et al\., 2025](https://arxiv.org/html/2608.23670#bib.bib18)\), and orchestrate multi\-agent pipelines\([Wu et al\., 2024a](https://arxiv.org/html/2608.23670#bib.bib13);[Hong et al\., 2024](https://arxiv.org/html/2608.23670#bib.bib14)\)\. Following the ReAct paradigm\([Yao et al\., 2023](https://arxiv.org/html/2608.23670#bib.bib33)\), they interleave chain\-of\-thought reasoning\([Wei et al\., 2022](https://arxiv.org/html/2608.23670#bib.bib38)\)with tool calls\([Schick et al\., 2023](https://arxiv.org/html/2608.23670#bib.bib39)\), generating execution traces whose behavioral structure remains implicit\. A coding agent cycles throughsearch→\\toedit→\\toexecute; a customer service agent alternates between database queries and user communication\. This structure emerges from the interaction between the system prompt, available tools, and task distribution, but nowhere is it specified\.

Understanding this latent structure matters for safety auditing\([Zhang et al\., 2025a](https://arxiv.org/html/2608.23670#bib.bib23);[Ruan et al\., 2024](https://arxiv.org/html/2608.23670#bib.bib15);[Chen et al\., 2025](https://arxiv.org/html/2608.23670#bib.bib36)\), debugging bottleneck states\([Zhang et al\., 2025c](https://arxiv.org/html/2608.23670#bib.bib12);[Cemri et al\., 2025](https://arxiv.org/html/2608.23670#bib.bib37)\), and monitoring behavioral drift in production\([Wang et al\., 2025a](https://arxiv.org/html/2608.23670#bib.bib5)\)\. Yet current approaches operate at the individual trace level, requiring task descriptions, manual specification, or success filters\([Zhang et al\., 2025d](https://arxiv.org/html/2608.23670#bib.bib3);[Wu et al\., 2024b](https://arxiv.org/html/2608.23670#bib.bib4);[Wang et al\., 2025d](https://arxiv.org/html/2608.23670#bib.bib2)\)\.

Figure 1:FSM evolutionon SWE\-agent\. State count\|Q\|\|Q\|\(red, left\) and test fitness \(blue, right\) over training traces, with FSM snapshots at six milestones\. The state space grows incrementally as new behavioral modes appear, while fitness saturates early \(≥0\.99\\geq 0\.99at 240 traces, 15% of training\); construction completes in milliseconds\.We frame behavioral recovery as an inverse problem: given a corpus of execution traces, reconstruct a finite state machine \(FSM\) that explains the observed behavior\. Agent traces provide only positive examples in the Gold sense\([Gold, 1967](https://arxiv.org/html/2608.23670#bib.bib25);[Angluin, 1980](https://arxiv.org/html/2608.23670#bib.bib1)\), and identifying the target language from positive examples alone is impossible in the limit\. Our key observation is that agent behavior is generated by a bounded set of tools and actions, producing traces with small activity alphabets \(6–42 symbols\)\. The resulting behavioral topology appears shaped more by the*system*than by the LLM, across 4 chat models on tau2\-bench: a single FSM achieves perfect fitness on every model\. This structural constraint makes the problem tractable: a prefix tree merged by last activity produces a compact directly\-follows FSM in linear time, requiring no learning hyperparameters \(the only design choice is the activity extraction function, whose robustness we verify in Appendix[G\.2](https://arxiv.org/html/2608.23670#A7.SS2)\)\. We evaluate on twelve public datasets \(Table[5](https://arxiv.org/html/2608.23670#A2.T5)\) against nine baselines from automata learning \(RPNI, EDSM, Alergia, k\-Tails\), HMMs, process mining, and workflow extraction \(§[2](https://arxiv.org/html/2608.23670#S2)\):

- •Workflow memory\.FSM\-state context outperforms Agent Workflow Memory\([Wang et al\., 2025d](https://arxiv.org/html/2608.23670#bib.bib2)\)on 8/8 datasets \(6 statsig atp<10−8p\\\!<\\\!10^\{\-8\}; Table[4](https://arxiv.org/html/2608.23670#S4.T4)\)\.
- •Next\-step prediction\.FSM state conditioning improves cross\-entropy by 0\.155 bits \(21%\) over identical methods without state\.
- •Failure prediction\.Per\-state features reach held\-out AUROC up to 0\.94, lift MLP/GRU/Transformer baselines on 20 of 21 pairs, and power a prefix\-based monitor that ranks failing SWE\-agent runs above passing ones at the 25% checkpoint \(rank\-AUROC 0\.66 vs\. 0\.5 for flag\-everything\) and triggers early stopping at 32% completion\.
- •Compression\.15–3,036×\\timesfewer states than RPNI at≥\\geq0\.997 fitness from a deterministic, hyperparameter\-free construction\.

One object ties these results together: bounded LLM\-agent alphabets make the resulting compact deterministic finite automaton \(DFA\) both small and statistically informative, and the same FSM unifies workflow memory, next\-step prediction, failure prediction, and runtime monitoring \(Theorems and Propositions in §[3\.4](https://arxiv.org/html/2608.23670#S3.SS4)\)\.

## 2Related Work

##### Agent safety and monitoring\.

AgentSpec\([Wang et al\., 2025a](https://arxiv.org/html/2608.23670#bib.bib5)\)and ShieldAgent\([Chen et al\., 2025](https://arxiv.org/html/2608.23670#bib.bib36)\)enforce safety policies; AgentMonitor\([Chan et al\., 2024](https://arxiv.org/html/2608.23670#bib.bib43)\)predicts task performance from step\-level features using flat XGBoost models\. ProbGuard\([Wang et al\., 2025b](https://arxiv.org/html/2608.23670#bib.bib49)\)learns a DTMC from traces and applies bounded\-horizon PCTL reachability for runtime safety filtering; head\-to\-head on our datasets \(Appendix[G\.6](https://arxiv.org/html/2608.23670#A7.SS6)\) it trails our FSM features by mean\+0\.176\+0\.176AUROC because, without hand\-crafted unsafe predicates, its symbolic\-state abstraction degrades to per\-activity granularity\. Concurrent trajectory\-anomaly detectors\([Liu et al\., 2025](https://arxiv.org/html/2608.23670#bib.bib52);[Deshpande et al\., 2025](https://arxiv.org/html/2608.23670#bib.bib53);[He et al\., 2025](https://arxiv.org/html/2608.23670#bib.bib54)\)target the same problem with hierarchical, behavioral, or graph\-based pipelines; our FSM differs by providing a compact structural quotient that doubles as workflow memory and next\-step predictor, not solely an anomaly score\. Closest is the concurrent PrefixGuard\([Huang et al\., 2026](https://arxiv.org/html/2608.23670#bib.bib50)\), which also extracts a DFA from LLM\-agent traces for online failure\-warning monitors; we treat the same compact automaton as one substrate that additionally drives compression, next\-step prediction, and workflow memory, rather than a monitor\-only construction\.[Cemri et al\. \(2025\)](https://arxiv.org/html/2608.23670#bib.bib37)taxonomize multi\-agent failure modes from 1,600\+ traces, motivating automated detection\. These approaches either require hand\-crafted policies or lack structural behavioral models\. Our FSM provides a learned structural model that enables compositional queries and early failure prediction from partial traces\.

##### Behavioral abstractions for agents\.

Agent Workflow Memory\([Wang et al\., 2025d](https://arxiv.org/html/2608.23670#bib.bib2)\)extracts linear workflow patterns from successful traces, while Reflexion\([Shinn et al\., 2023](https://arxiv.org/html/2608.23670#bib.bib34)\)and ETO\([Song et al\., 2024](https://arxiv.org/html/2608.23670#bib.bib44)\)learn from failures via verbal reflection or contrastive pairs\. ReasoningBank\([Ouyang et al\., 2025](https://arxiv.org/html/2608.23670#bib.bib51)\)extends AWM with both successful and failed traces\. None of these produce structural models with state abstraction\. On the FSM side, AFlow\([Zhang et al\., 2025b](https://arxiv.org/html/2608.23670#bib.bib6)\)searches workflows via MCTS, MetaAgent\([Zhang et al\., 2025d](https://arxiv.org/html/2608.23670#bib.bib3)\)builds FSMs top\-down from task descriptions, and StateFlow\([Wu et al\., 2024b](https://arxiv.org/html/2608.23670#bib.bib4)\)relies on manual specification\. Our method recovers FSMs bottom\-up from raw traces with a compact structural quotient and per\-state decomposition for failure prediction\.

##### Process mining\.

Process discovery\([van der Aalst, 2016](https://arxiv.org/html/2608.23670#bib.bib7)\)recovers Petri nets from event logs\. Applied to agent traces, standard miners produce “flower models” with precision 0\.00–0\.80 \(Table[20](https://arxiv.org/html/2608.23670#A5.T20)\), with highest precision on constrained workflows\([Berti et al\., 2024a](https://arxiv.org/html/2608.23670#bib.bib8);[Berti et al\., 2024b](https://arxiv.org/html/2608.23670#bib.bib24)\)\. Our automaton is the directly\-follows graph\([van der Aalst, 2016](https://arxiv.org/html/2608.23670#bib.bib7)\)made deterministic by a last\-activity right congruence; the closest learning\-based variant is stochastic directly\-follows discovery via grammatical inference\([Alkhammash et al\., 2024](https://arxiv.org/html/2608.23670#bib.bib55)\), which tunes a soundness objective for business\-process event logs, whereas we use a single deterministic pass with a convergence guarantee and apply the result to LLM\-agent failure prediction, next\-step prediction, and monitoring\.

##### Grammatical inference\.

Learning finite automata from positive examples is impossible in the limit\([Gold, 1967](https://arxiv.org/html/2608.23670#bib.bib25);[Angluin, 1980](https://arxiv.org/html/2608.23670#bib.bib1)\)\. RPNI\([Oncina and García, 1992](https://arxiv.org/html/2608.23670#bib.bib20)\), EDSM\([Lang et al\., 1998](https://arxiv.org/html/2608.23670#bib.bib21)\), and L\*\([Angluin, 1987](https://arxiv.org/html/2608.23670#bib.bib9)\)require negative examples or oracles unavailable in trace analysis\. k\-Tails\([Biermann and Feldman, 1972](https://arxiv.org/html/2608.23670#bib.bib46)\)merges states with identicalkk\-length futures, but requires a hyperparameter and produces 1\.4–10×\\timesmore states than ours with lower fitness\. Among positive\-only methods, Alergia\([Carrasco and Oncina, 1994](https://arxiv.org/html/2608.23670#bib.bib27)\)is the strongest competitor: it matches our fitness with 1\.0–6\.0×\\timesmore states via statistical tests\. HMMs\([Rabiner, 1989](https://arxiv.org/html/2608.23670#bib.bib28)\)match state counts but yield non\-interpretable latent states\. Our approach exploits bounded activity alphabets \(6–42 symbols\) to produce compact, interpretable FSMs \(7–43 states\) without hyperparameters\.

## 3Method

### 3\.1Problem Formulation

An agent execution trace is a sequence of messagesτ=\(m1,m2,…,mT\)\\tau=\(m\_\{1\},m\_\{2\},\\ldots,m\_\{T\}\), where each messagemtm\_\{t\}has a role \(system, user, assistant, tool\) and content\. An activity extraction functionϕ:mt↦at∈𝒜\\phi:m\_\{t\}\\mapsto a\_\{t\}\\in\\mathcal\{A\}maps each message to a symbol from a finite alphabet𝒜\\mathcal\{A\}\. The activity sequence isσ⁡\(τ\)=\(ϕ⁡\(m1\),…,ϕ⁡\(mT\)\)\\sigma\(\\tau\)=\(\\phi\(m\_\{1\}\),\\ldots,\\phi\(m\_\{T\}\)\)\.

Given a corpus𝒟=\{τ1,…,τN\}\\mathcal\{D\}=\\\{\\tau\_\{1\},\\ldots,\\tau\_\{N\}\\\}, we construct a finite state machineℳ=\(Q,𝒜,δ,q0,Q\)\\mathcal\{M\}=\(Q,\\mathcal\{A\},\\delta,q\_\{0\},Q\)with statesQQ, partial transition functionδ:Q×𝒜→Q\\delta:Q\\times\\mathcal\{A\}\\to Q, and initial stateq0q\_\{0\}; all states are accepting\. The transition function is deterministic: each \(state, activity\) pair maps to at most one successor\.

###### Definition 1\(Replay fitness\)\.

For sequenceσ=\(a1,…,aT\)\\sigma=\(a\_\{1\},\\ldots,a\_\{T\}\), letkkbe the number of symbols consumed byℳ\\mathcal\{M\}when replayingσ\\sigmafromq0q\_\{0\}\(steps whereδ⁡\(q,at\)\\delta\(q,a\_\{t\}\)is defined\)\. The replay fitness isfit⁡\(σ,ℳ\)=k/T\\mathrm\{fit\}\(\\sigma,\\mathcal\{M\}\)=k/T\. Corpus fitness is

Fit⁡\(𝒟,ℳ\)=1\|𝒟\|​∑τ∈𝒟fit⁡\(σ⁡\(τ\),ℳ\)\.\\mathrm\{Fit\}\(\\mathcal\{D\},\\mathcal\{M\}\)=\\frac\{1\}\{\|\\mathcal\{D\}\|\}\\sum\_\{\\tau\\in\\mathcal\{D\}\}\\mathrm\{fit\}\(\\sigma\(\\tau\),\\mathcal\{M\}\)\.\(1\)

### 3\.2Activity Extraction

Agent traces come in heterogeneous formats\. We apply three extraction rules in priority: \(1\) tool calls: if a message contains atool\_callfield, the activity is the function name; \(2\) action tags: if the content contains\[ACTION\] description, the activity is the action label; \(3\) command extraction: for agents using code blocks, we extract the first command token and map it to a semantic category\. If no rule matches, the activity defaults torole:content\_type\(e\.g\.,assistant:text\)\. The extraction is deterministic and format\-specific; Appendix[B\.1](https://arxiv.org/html/2608.23670#A2.SS1)details it for each dataset\.

##### Robustness to the extraction choice\.

The downstream pipeline is robust to this choice: across extraction granularities, replay fitness stays≥0\.999\\geq\\\!0\.999on every dataset, and failure\-prediction AUROC is stable between meaningful levels: on all twelve datasets the default \(role\-type\) matches or exceeds the coarser role\-only level on ten, moving more only where role\-only collapses to a≤\\leq3\-symbol alphabet \(Appendix[G\.2](https://arxiv.org/html/2608.23670#A7.SS2)\), so the rules above are one valid setting rather than the only one\.

### 3\.3FSM Construction

Given activity sequences\{σ⁡\(τi\)\}i=1N\\\{\\sigma\(\\tau\_\{i\}\)\\\}\_\{i=1\}^\{N\}, construction proceeds in three steps \([AlgorithmA\.1](https://arxiv.org/html/2608.23670#A1.SS1),[AppendixA\.1](https://arxiv.org/html/2608.23670#A1.SS1)\)\.

##### Step 1: Prefix tree\.

Insert all activity sequences into a trie\. Each unique prefix is a distinct state\. The prefix tree has perfect training fitness butO⁡\(∑iTi\)O\(\\sum\_\{i\}T\_\{i\}\)states\.

##### Step 2: Merge by last activity\.

We merge all trie states reached by the same activity into one\. Writingκ⁡\(q\)\\kappa\(q\)for the activity on the edge intoqq\(andκ⁡\(qε\)=init\\kappa\(q\_\{\\varepsilon\}\)=\\mathrm\{init\}for the root\), we merge states by the last\-activity right congruence

q∼q′⇔κ⁡\(q\)=κ⁡\(q′\),q\\sim q^\{\\prime\}\\iff\\kappa\(q\)=\\kappa\(q^\{\\prime\}\),\(2\)which has\|𝒜\|\+1\|\\mathcal\{A\}\|\+1classes\. Adding up the trie’s traversal counts over each class pair gives the directly\-follows automaton in a single pass; cycles appear wherever an activity recurs\.

##### Step 3: Rare\-transition filtering\.

We drop a merged transition observed exactly once in the corpus unless it is its source state’s only continuation\. This removes one\-off digressions but never a state, and it is the only step that can cost fitness, and the replay\-fitness columns of Table[1](https://arxiv.org/html/2608.23670#S4.T1)measure that cost directly\.

Section[3\.4](https://arxiv.org/html/2608.23670#S3.SS4)proves this construction preserves fitness and yields a compact directly\-follows automaton; tool\-use patterns \(search–edit–execute\) collapse to loops and the state count tracks the number of distinct activities\. Figure[5](https://arxiv.org/html/2608.23670#A1.F5)\(Appendix[A\.1](https://arxiv.org/html/2608.23670#A1.SS1)\) shows the construction at role\-level granularity for a customer service agent \(6 states, 5 activities\)\.

### 3\.4Construction and Convergence Guarantees

We characterize the correctness and optimality of the extracted FSM\.

###### Theorem 2\(Fitness preservation\)\.

The last\-activity merge preserves training fitness: if traceσ\\sigmais accepted by the prefix tree, it is accepted by the merged FSM of Step 2\.

###### Proof sketch\.

Merging only adds out\-edges: each class carries the union of its members’ transitions, so every trie edge survives in the quotient\. For any traceσ=\(a1,…,aT\)\\sigma=\(a\_\{1\},\\ldots,a\_\{T\}\)accepted by the prefix tree with state sequenceq0,q1,…,qTq\_\{0\},q\_\{1\},\\ldots,q\_\{T\}, the merged FSM follows the quotient sequence\[q0\],\[q1\],…,\[qT\]\[q\_\{0\}\],\[q\_\{1\}\],\\ldots,\[q\_\{T\}\], sinceδ⁡\(qi,ai\+1\)=qi\+1\\delta\(q\_\{i\},a\_\{i\+1\}\)=q\_\{i\+1\}impliesδ⁡\(\[qi\],ai\+1\)=\[qi\+1\]\\delta\(\[q\_\{i\}\],a\_\{i\+1\}\)=\[q\_\{i\+1\}\]by the congruence \([2](https://arxiv.org/html/2608.23670#S3.E2)\); the full trace is accepted\. Step 3 filtering is the only source of fitness loss, and the replay\-fitness columns measure it directly \(full proof in Appendix[A\.2](https://arxiv.org/html/2608.23670#A1.SS2)\)\. ∎

###### Theorem 3\(Determinism and compactness\)\.

Merging the prefix tree by the last\-activity right congruence yields a deterministic FSM with\|Q\|=\|𝒜\|\+1\|Q\|=\|\\mathcal\{A\}\|\+1states—one per activity plus the initial state—whose transitions are the directly\-follows pairs retained from the corpus: the construction is a deterministic function of the corpus, so re\-extraction from the same data is exact\.

###### Proof sketch\.

The merge assigns each trie state to the class of its incoming activity, giving\|𝒜\|\+1\|\\mathcal\{A\}\|\+1classes; transitions are the retained directly\-follows pairs, deduplicated, so each\(q,a\)\(q,a\)has at most one target and the FSM is deterministic\. Step 3 removes transitions but never states, so determinism and the state count are unaffected: the class map and the transition set depend only on the multiset of observed \(activity, next\-activity\) pairs, hence are invariant to trace order and sampling, so the output is unique for a fixed corpus\. \(Full proof in Appendix[A\.2](https://arxiv.org/html/2608.23670#A1.SS2)\.\) ∎

We recover the directly\-follows automaton of the observed traces, not the generating automaton, which is impossible to identify from positive examples alone\([Gold, 1967](https://arxiv.org/html/2608.23670#bib.bib25)\)\.

Empirically, all twelve datasets yield 7–43 states \(Tables[1](https://arxiv.org/html/2608.23670#S4.T1),[8](https://arxiv.org/html/2608.23670#A4.T8)\), because agent activity sequences exhibit strong sequential regularity: conditioning on the previous symbol reduces entropy by 51–80% \(Appendix[F\.3](https://arxiv.org/html/2608.23670#A6.SS3)\)\. Compact state spaces aggregate sufficient observations per state for reliable probability estimation, unlike RPNI’s10310^\{3\}–10510^\{5\}states\.

###### Proposition 5\(Convergence guarantee\)\.

Letℳ∗\\mathcal\{M\}^\{\*\}be the population directly\-follows automaton, withrrtransitions: if traces are drawn i\.i\.d\. and each transition appears in a trace with probability at leastpminp\_\{\\min\}, then for anyδf\>0\\delta\_\{\\mathrm\{f\}\}\>0, the extracted FSM equalsℳ∗\\mathcal\{M\}^\{\*\}with probability≥1−δf\\geq 1\-\\delta\_\{\\mathrm\{f\}\}afterN≥1pmin​ln⁡\(r/δf\)N\\geq\\frac\{1\}\{p\_\{\\min\}\}\\ln\(r/\\delta\_\{\\mathrm\{f\}\}\)traces\.

A union bound overrrtransitions gives the failure\-probability chain

Pr⁡\[some transition unobserved\]\\displaystyle\\Pr\[\\text\{some transition unobserved\}\]≤r​\(1−pmin\)N\\displaystyle\\leq\\;r\(1\-p\_\{\\min\}\)^\{N\}\(3\)≤r​e−N​pmin≤δf,\\displaystyle\\leq\\;r\\,e^\{\-Np\_\{\\min\}\}\\;\\leq\\;\\delta\_\{\\mathrm\{f\}\},which yields the bound \(full proof in Appendix[A\.2](https://arxiv.org/html/2608.23670#A1.SS2)\)\. The i\.i\.d\. assumption is approximate: in practice, agent traces come from iterative deployment on fixed task distributions\. The bound stays useful because the requirement is weak \(N≤690N\\leq 690for SWE\-agent’sk=51k\\\!=\\\!51transitions atpmin≈0\.01p\_\{\\min\}\\\!\\approx\\\!0\.01,δ=0\.05\\delta\\\!=\\\!0\.05\), and empirical convergence at 5–15% of training data \(Figure[14](https://arxiv.org/html/2608.23670#A6.F14)\) suggests it is conservative even under mild distributional shift\.

### 3\.5Prediction via FSM State Conditioning

Given the current FSM stateqt=δ∗​\(q0,a1​…​at−1\)q\_\{t\}=\\delta^\{\*\}\(q\_\{0\},a\_\{1\}\\ldots a\_\{t\-1\}\), we estimateP⁡\(at∣qt\)P\(a\_\{t\}\\mid q\_\{t\}\)from transition counts:

P^​\(a∣q\)=C⁡\(q,a\)\+α∑a′∈𝒜C⁡\(q,a′\)\+α​\|𝒜\|\\hat\{P\}\(a\\mid q\)=\\frac\{C\(q,a\)\+\\alpha\}\{\\sum\_\{a^\{\\prime\}\\in\\mathcal\{A\}\}C\(q,a^\{\\prime\}\)\+\\alpha\|\\mathcal\{A\}\|\}\(4\)whereC⁡\(q,a\)C\(q,a\)counts how oftenaafollows stateqqin training data andα\\alphais a smoothing parameter\. Higher\-order context can be incorporated via prediction by partial matching \(PPM\) with absolute discounting, blending FSM predictions across context depths \(Appendix[G\.9](https://arxiv.org/html/2608.23670#A7.SS9)\)\. We evaluate predictive quality via cross\-entropy:

CE=−1T∑t=1Tlog2P^\(at∣context\)\.\\mathrm\{CE\}=\-\\frac\{1\}\{T\}\\sum\_\{t=1\}^\{T\}\\log\_\{2\}\\hat\{P\}\(a\_\{t\}\\mid\\text\{context\}\)\.\(5\)
Because the FSM has only\|Q\|=O⁡\(\|𝒜\|\)\|Q\|=O\(\|\\mathcal\{A\}\|\)states, each state aggregates many transitions, giving aO⁡\(1/nq\)O\(1/\\sqrt\{n\_\{q\}\}\)total\-variation concentration bound forP^\(⋅∣q\)\\hat\{P\}\(\\cdot\\mid q\)\(Proposition[6](https://arxiv.org/html/2608.23670#Thmtheorem6), Appendix[A\.2](https://arxiv.org/html/2608.23670#A1.SS2)\)\. RPNI’s\|QRPNI\|≫\|𝒜\|\|Q\_\{\\text\{RPNI\}\}\|\\\!\\gg\\\!\|\\mathcal\{A\}\|partitions the same observations into sparsely visited states, which degrades both the estimator and any anomaly signal derived from it\. Under success/failure FSM\-structured mixtures, the per\-trace surprise differenceCE−​\(τ\)−CE\+​\(τ\)\\mathrm\{CE\}^\{\-\}\(\\tau\)\-\\mathrm\{CE\}^\{\+\}\(\\tau\)is a Neyman–Pearson\-optimal statistic up toO⁡\(1/nq\)O\(1/\\sqrt\{n\_\{q\}\}\)error \(Corollary[7](https://arxiv.org/html/2608.23670#Thmtheorem7), Appendix[A\.2](https://arxiv.org/html/2608.23670#A1.SS2)\)\. The same compactness gives a sub\-linearO⁡\(T​log⁡\|Q\|\)O\(\\sqrt\{T\\log\|Q\|\}\)regret bound for an online thresholded log\-likelihood\-ratio monitor \(Proposition[8](https://arxiv.org/html/2608.23670#Thmtheorem8), Appendix[A\.2](https://arxiv.org/html/2608.23670#A1.SS2)\), matching the empiricalF1=0\.904F\_\{1\}\\\!=\\\!0\.904early\-stopping monitor\.

### 3\.6Evaluation Metrics

Beyond replay fitness and cross\-entropy, we evaluate along three axes\. Precision: the fraction of invalid traces the FSM rejects\. We generate random traces \(uniform over𝒜L\\mathcal\{A\}^\{L\}\) and permuted traces \(shuffled real sequences\); low acceptance shows meaningful sequential constraints\. Compression:\|Qbaseline\|/\|Qours\|\|Q\_\{\\text\{baseline\}\}\|/\|Q\_\{\\text\{ours\}\}\|, measuring compactness against baseline automata\. Stability: variance in FSM structure across random train/test splits\.

## 4Results

### 4\.1Setup

We evaluate on twelve datasets across eight agent domains \(Table[5](https://arxiv.org/html/2608.23670#A2.T5), Appendix[B\.1](https://arxiv.org/html/2608.23670#A2.SS1)\), with alphabets of 6–42 symbols and 80/20 train/test splits\. Nine datasets have outcome labels and are used for failure prediction \(eight real LLM\-trace datasets and SWE\-smith, the lone synthetic dataset\); three contribute compression and next\-step prediction results only because they lack outcome labels \(Appendix[D\.1](https://arxiv.org/html/2608.23670#A4.SS1)\)\. Baselines: RPNI, EDSM, Alergia, k\-Tails \(automata learning via AALpy\([Muškardin et al\., 2022](https://arxiv.org/html/2608.23670#bib.bib22)\)\); HMM; Alpha, Inductive, Heuristic Miners \(process mining via PM4Py\([Berti et al\., 2019](https://arxiv.org/html/2608.23670#bib.bib45)\)\); AWM \(workflow extraction\)\. All receive identical training sequences with positive examples only\.

### 4\.2Main Results

Our FSM \(7–43 states\) achieves 15–3,036×\\timescompression over RPNI at≥\\geq0\.997 test fitness on all datasets \(Table[1](https://arxiv.org/html/2608.23670#S4.T1)\)\. Among positive\-only methods, Alergia is the strongest competitor: it matches fitness but uses 1\.0–6\.0×\\timesmore states\. k\-Tails\([Biermann and Feldman, 1972](https://arxiv.org/html/2608.23670#bib.bib46)\), the classic software\-engineering baseline, produces 1\.4–10×\\timesmore states than ours atk=1k\{=\}1with lower fitness \(0\.54–1\.00\), and state counts explode atk≥2k\{\\geq\}2\(up to 1,085 states or timeout; Table[12](https://arxiv.org/html/2608.23670#A4.T12)\)\. HMM matches state count but is non\-interpretable; EDSM collapses to 1 state without negatives \(Appendix[D\.2](https://arxiv.org/html/2608.23670#A4.SS2)\)\. Compression scales with dataset complexity: 15×\\timeson WebArena to 2,500×\\timeson AgentNet, where RPNI exceeds its 120s budget; including the unlabeled datasets \(Appendix[D\.1](https://arxiv.org/html/2608.23670#A4.SS1)\) it reaches 3,036×\\timeson GUI\-Odyssey\.

Table 1:FSM extraction resultson eight labeled real\-trace datasets \(excluding SWE\-smith synthetic\)\.\|Q\|\|Q\|: states\. Fit: test replay fitness\.†RPNI timeout at 120 s\. Full baselines in Table[8](https://arxiv.org/html/2608.23670#A4.T8); SWE\-smith and the unlabeled datasets appear in Appendix[D\.1](https://arxiv.org/html/2608.23670#A4.SS1)\.Table 2:Next\-step predictioncross\-entropy \(bits,↓\\downarrow\)\. 5×\\times5\-fold CV across all datasets\. Best per dataset inbold\. The “FSM” columns use the FSM\-state context format \(*ASG\-minimal*\) selected on validation in Section[4\.3](https://arxiv.org/html/2608.23670#S4.SS3)\.Fitness converges rapidly: on all datasets,≥\\geq0\.99 fitness is reached using 5–15% of training data \(Figure[14](https://arxiv.org/html/2608.23670#A6.F14)\)\. On SWE\-agent \(2,000 traces\), fitness reaches 0\.99 at 240 traces \(15%\), though the state space continues growing to 25 as rare command patterns appear\. Because the construction is deterministic and hyperparameter\-free \(Theorem[3](https://arxiv.org/html/2608.23670#Thmtheorem3)\), a fixed corpus yields a unique FSM; across random splits our state counts stay within a few states of the full\-data value \(rare commands, as above, account for the residual\), whereas RPNI state counts vary by 2–10% \(hundreds to thousands of states; Appendix[F\.2](https://arxiv.org/html/2608.23670#A6.SS2)\)\.

Our FSM rejects 100% of random traces and≥\\geq99\.9% of permuted traces on all eight labeled real\-trace datasets, while RPNI accepts 75% of permuted traces on WebArena \(Table[18](https://arxiv.org/html/2608.23670#A5.T18), Appendix[E\.7](https://arxiv.org/html/2608.23670#A5.SS7)\)\. Even plausible single\-symbol mutations \(substitution, insertion, adjacent swap\) are rejected at 77–100% across datasets, because the FSM encodes turn\-taking and tool\-invocation constraints learned from data \(Table[19](https://arxiv.org/html/2608.23670#A5.T19)\)\. Process mining baselines achieve precision 0\.00–0\.80 \(Appendix[E\.8](https://arxiv.org/html/2608.23670#A5.SS8)\)\. State compression and cross\-dataset fitness are visualized in Appendix[16](https://arxiv.org/html/2608.23670#A8.F16)\.

##### Next\-step prediction\.

Beyond acceptance, we evaluate whether the FSM captures structure for prediction\. At each steptt, a predictor estimatesP⁡\(at∣context\)P\(a\_\{t\}\\mid\\text\{context\}\); we report cross\-entropy \(CE, bits\) via 5×\\times5\-fold CV\. Without any learning, our FSM \(order\-1 Markov\) achieves 0\.93 bits avg CE across the five\-dataset table, a 62% reduction from the Unigram baseline \(2\.44 bits; Table[2](https://arxiv.org/html/2608.23670#S4.T2)\)\. This single step of conditioning on FSM state rather than activity frequencies accounts for 83–99% of the total CE improvement from Uniform to the best method on each dataset\.

In a controlled ablation \(absolute discounting, depth 5\), FSM state conditioning provides \+0\.155 bits mean / \+0\.136 bits median \(21%21\\%\) over raw context alone \(FSM\-AD: 0\.580 vs\. Pure\-AD: 0\.735 CE\), positive on all 6 datasets, ranging from\+0\.016\+0\.016on SWE\-agent to\+0\.364\+0\.364on Mind2Web\. This controlled gap is8×8\\timeslarger than the \+0\.019 from adding FSM state to logistic regression \(FSM\-LR\-K7: 0\.729 vs\. NGram\-LR\-K7: 0\.748\), because learned models partially recover FSM\-like state from raw context\. The improvement is consistent: FSM state conditioning helps every prediction method on every dataset\. Combining FSM state with learned models yields 0\.73 bits avg CE \(FSM\-LR\-K7\), the best across all methods \(Table[2](https://arxiv.org/html/2608.23670#S4.T2)\); FSM\-LR\-K7 serves as our learned\-sequence baseline, and even high\-capacity MLP/GRU/Transformer classifiers see lift from FSM features on 20 of 21 dataset\-architecture pairs in failure prediction \(Appendix[E\.6](https://arxiv.org/html/2608.23670#A5.SS6)\)\. The FSM is thus a structural primitive that benefits rather than competes with learned sequence models\. RPNI overfits catastrophically: 3\.40 bits avg, worse than Unigram \(2\.44\), because its 382–59,510 states observe too few transitions each \(Figure[2](https://arxiv.org/html/2608.23670#S4.F2); Appendix[G\.9](https://arxiv.org/html/2608.23670#A7.SS9)\)\.

Figure 2:Next\-step predictioncross\-entropy \(bits,↓\\downarrow\)\. \(a\) Per\-dataset: FSM\-conditioned methods \(red\) achieve 3–5×\\timeslower CE than baselines\. \(b\) Average ranking: FSM\-conditioned variants outperform their non\-FSM counterparts on all four datasets\. RPNI overfits worse than Uniform due to sparse transitions across thousands of states\.
##### Context format ablation \(why minimal wins\)\.

The gain over AWM is not automatic: four natural FSM\-context formats produce widely different top\-1 accuracy on tau2\-bench retail \(N=1,095, Table[3](https://arxiv.org/html/2608.23670#S4.T3)\)\. The verbose “state \+ transitions \+ full structure” format \(ASG\-full, 52\.2%\) underperforms AWM \(52\.9%\) because listing every state and transition drowns the next\-step signal; adding multi\-step continuations only \(ASG\+\+, 49\.2%\) is worse, as does restricting to success\-only traces \(ASG\-success, 50\.3%\)\. The minimal format used in Table[4](https://arxiv.org/html/2608.23670#S4.T4)\(natural\-language next\-action probabilities plus top\-15 multi\-step continuations from the current state, with no “current state / full structure” headers\) wins at 65\.1% \(\+12\.9pp over AWM and \+12\.9pp over ASG\-full\)\. AWM here is its published default format from[Wang et al\. \(2025d\)](https://arxiv.org/html/2608.23670#bib.bib2); identifying the right minimal context for a structural model is part of the contribution, in the same way that AWM’s linear\-workflow format is part of its\. Tau2\-bench retail is used for format selection and also appears in Table[4](https://arxiv.org/html/2608.23670#S4.T4); the format generalises to held\-out data: mean FSM advantage over AWM is\+12\.2\+12\.2pp on the in\-distribution tau2\-bench retail row vs\.\+13\.1\+13\.1pp averaged over the 7 strictly held\-out datasets, so the tau2\-bench retail row is, if anything, slightly below the held\-out average rather than inflated\.

Table 3:FSM context format ablation\(tau2\-bench retail, N=1,095, gpt\-4\.1\-mini top\-1 %\)\.A representative prompt comparison at FSM stateget\_order\_details\(tau2\-bench retail\) is in Appendix[G\.8](https://arxiv.org/html/2608.23670#A7.SS8)\(Figure[15](https://arxiv.org/html/2608.23670#A7.F15)\): AWM presents a long enumeration of success\-only workflows that the LLM must align to the trace prefix, while the FSM\-minimal context surfaces the dominant next\-action and a few continuations, making the next\-step decision visible at a glance\.

##### Judge robustness\.

The advantage is not specific to the original judge: averaginggpt\-4\.1\-miniandgpt\-4o\-minion the most contested datasets \(ATBench, tau2\-bench airline\) keeps ASG ahead of AWM by a mean of8\.7pp\(range \+3\.6pp to \+13\.9pp\), with FSM winning under both judges on every dataset tested\.

##### FSM as context for LLM agents\.

We test whether providing the FSM as context improves an LLM’s next\-action prediction, comparing against Agent Workflow Memory \(AWM\)\([Wang et al\., 2025d](https://arxiv.org/html/2608.23670#bib.bib2)\)\. Transition counts and multi\-step continuations are computed on training data only; validation traces are replayed through the FSM to obtain the current state, and the LLM judge \(gpt\-4\.1\-mini\) is prompted with either AWM’s linear workflows or the FSM’s single\-step transition probabilities plus top\-15 multi\-step continuations from the current state\. Under LLM\-judged top\-1 evaluation, the FSM beats AWM on all eight datasets \(Table[4](https://arxiv.org/html/2608.23670#S4.T4)\), with gains ranging from \+0\.8pp \(tau2\-bench airline\) to \+25\.3pp \(SWE\-smith\)\. In parallel statistical evaluation on the full validation sets, the FSM also achieves higher top\-1 accuracy than AWM on every dataset \(e\.g\., SWE\-smith: 100% vs\. 34\.5%; tau2\-telecom: 61\.8% vs\. 19\.8%; Table[29](https://arxiv.org/html/2608.23670#A7.T29)\)\. AWM’s coverage limitation \(it extracts workflows only from successful traces\) explains the gap on low\-success\-rate datasets\.

Table 4:FSM vs\. AWM as context for an LLM next\-action predictor\(gpt\-4\.1\-mini, top\-1 %\)\. 6/8 gaps statsig atp<10−8p\\\!<\\\!10^\{\-8\}\.†tau2\-retail used for FSM\-context\-format selection \(§[4\.2](https://arxiv.org/html/2608.23670#S4.SS2)\); other 7 held out\.
##### Out\-of\-distribution detection\.

Cross\-dataset replay produces low fitness on structurally distinct dataset pairs \(AUROC 1\.000\); the schema\-sharing tau2\-bench airline↔\\leftrightarrowretail pair is the exception, replaying near\-1\.0\. Within\-alphabet perturbation yields AUROC≥\\geq0\.917 \(Appendix[G\.4](https://arxiv.org/html/2608.23670#A7.SS4)\)\. FSMs also transfer across models: a single FSM built from all four LLMs’ traces achieves1\.000fitness on each model individually \(per\-model FSMs share a near\-identical state vocabulary and a dominant 80–92% transition backbone, indicating largely model\-invariant topology\), and per\-model failure\-prediction features transfer at0\.786mean cross\-AUROC vs\.0\.877self across all three tau2\-bench suites \(36 off\-diagonal pairs; per\-suite breakdown in Appendix[C\.1](https://arxiv.org/html/2608.23670#A3.SS1)\)\.

##### Runtime\.

Our method constructs FSMs in 1–110 ms across all datasets, compared to 7,000–36,000 ms for RPNI \(328–10,611×\\timesspeedup\)\. Per\-trace replay completes in 0\.003–0\.015 ms, enabling real\-time monitoring of production agent systems \(Appendix[D\.4](https://arxiv.org/html/2608.23670#A4.SS4)\)\.

### 4\.3Failure Prediction from FSM Features

We predict task success/failure on nine labeled datasets, including ATBench\([Li et al\., 2026](https://arxiv.org/html/2608.23670#bib.bib47)\), a trajectory\-level safety benchmark with balanced safe/unsafe outcomes\. We replay each trace through the FSM and extract per\-state features \(visit frequency, message length, error rate, temporal\) alongside five FSM cross\-entropy anomaly features \(trace CE, max surprise, half\-to\-half drift, minimum transition probability, high\-surprise rate\); a single gradient\-boosted classifier \(200 trees, depth 3, class\-weighted\) with L1 selection produces held\-out AUROC on a fixed 80/20 split \(per\-dataset numbers in Figure[3](https://arxiv.org/html/2608.23670#S4.F3)a, with raw values in Appendix[E\.2](https://arxiv.org/html/2608.23670#A5.SS2), Table[14](https://arxiv.org/html/2608.23670#A5.T14)\)\.

Raw fitness is uninformative \(AUROC≈\\approx0\.50\); FSM cross\-entropy anomaly features reach up to 0\.941 held\-out AUROC \(tau2\-bench telecom, 43 states\), with larger FSMs predicting better \(telecom 0\.941, WebArena 0\.903, AgentNet 0\.890, ATBench 0\.894 vs\. SWE\-agent 0\.799; Figure[3](https://arxiv.org/html/2608.23670#S4.F3)a\)\. Failure traces show higher surprise under the FSM’s transition distribution; on SWE\-agent, reachingsubmitis the strongest predictor \(94\.8% of successes vs\. 55\.7% of failures\)\. On ATBench, the only safety\-labeled benchmark, AUROC reaches 0\.894 with the lowest CV variance in the suite \(0\.864 ± 0\.024\)\. Across all eight real\-trace datasets the 5\-fold×\\times10\-repeat CV std stays in 0\.012–0\.031 \(Appendix[E\.2](https://arxiv.org/html/2608.23670#A5.SS2)\), so the held\-out AUROCs are not single\-split artefacts\.

Figure 3:Failure prediction\.\(a\) AUROC: FSM features \(red\) vs\. raw trace statistics \(blue\) vs\. fitness alone \(gray\)\. FSM features outperform raw features on SWE\-agent \(\+7\.9pp\)\. \(b\) Early prediction: FSM features at 50% completion achieve 92% of final AUROC on SWE\-agent\. Solid: FSM; dashed: baseline\.FSM features at 50% completion reach 92% of full\-trace AUROC \(Figure[3](https://arxiv.org/html/2608.23670#S4.F3)b\)\. On SWE\-agent, successes use only 9 of 25 states along a focused search–edit–submit path while failures span all 25 \(Jaccard 0\.206\), and the signal is structural rather than a length proxy: AUROC 0\.790 vs\. 0\.659 for length alone \(Appendices[G\.1](https://arxiv.org/html/2608.23670#A7.SS1),[E\.1](https://arxiv.org/html/2608.23670#A5.SS1),[H\.3](https://arxiv.org/html/2608.23670#A8.SS3)\)\. Feature analysis surfaces interpretable failure modes: on tau2\-bench telecom, per\-state visit frequencies separate agents that skip diagnostic steps\. Applying the identical feature pipeline to Alergia\-extracted FSMs yields lower AUROC on 8 of 9 datasets \(Appendix[E\.4](https://arxiv.org/html/2608.23670#A5.SS4)\), so the gain comes from per\-state observation density rather than feature engineering\. A label\-aware variant \(*discriminative quotient*, FSM\-D; Appendix[E\.3](https://arxiv.org/html/2608.23670#A5.SS3)\) replaces the standard last\-activity merge with one that conditions on success/failure outgoing distributions, lifting AUROC over a length\+entropy baseline by up to\+\+0\.152 on tau2\-bench airline using only training\-free per\-state KL features\.

##### Agent integration: FSM as runtime monitor\.

Our online monitor applies two rules, cycle\-rate\>\>0\.778 and a minimum unique\-state count with warm\-up, and bounds its regret atO⁡\(T​log⁡\|Q\|\)O\(\\sqrt\{T\\log\|Q\|\}\)\(Proposition[8](https://arxiv.org/html/2608.23670#Thmtheorem8)\)\. It achieves rank\-AUROC0\.66at the nearest 25% trace checkpoint on 4/4 evaluated datasets \(Appendix[G\.1](https://arxiv.org/html/2608.23670#A7.SS1)\), versus AUROC==0\.5 by construction for the trivial flag\-everything baseline, and triggers early\-stopping at 32% mean trace completion on SWE\-agent \(precision 85\.9%, recall 95\.5%, saving 68% of remaining compute\) and at 56% on tau2\-bench airline\. The F1 metric is dominated by base\-rate effects when the failure rate is high \(SWE\-agent 84\.3% failure⇒\\Rightarrowflag\-everything F1 = 0\.914 vs\. monitor F1 = 0\.904; both agree on what to flag, but the monitor adds*when*\)\. At a high\-precision operating point \(cycle\-rate\>\>0\.957\) the monitor reaches 100% precision on SWE\-agent \(zero false alarms, 11\.3% recall\), making it usable as a confident early\-stop trigger\. The pipeline is FSM replay only \(0\.006 ms/step\), no ML model\. Figure[4](https://arxiv.org/html/2608.23670#S4.F4)visualises the cycle\-rate trajectory of one failing SWE\-agent run alongside a successful one: the failing run enters a tight loop between two states early, while the successful run continues to visit new states; the monitor exploits this divergence\.

Figure 4:FSM\-based runtime monitor\.Cycle\-rate over trace progress for one failing \(red\) vs\. one successful \(blue\) SWE\-agent run\. The failing trace exceeds the cycle\-rate threshold \(0\.778\) at 32% of trace completion \(vertical dashed line\), triggering early termination\. The successful trace stays below threshold and continues until natural completion\.Cross\-model transfer and sensitivity to extraction granularity are discussed in §[5](https://arxiv.org/html/2608.23670#S5); sample efficiency and failure\-mode characterization in Appendix[H\.2](https://arxiv.org/html/2608.23670#A8.SS2),[H\.4](https://arxiv.org/html/2608.23670#A8.SS4)\.

## 5Discussion

##### Baseline landscape\.

Gold’s theorem\([Gold, 1967](https://arxiv.org/html/2608.23670#bib.bib25)\)forces every positive\-only method onto a compression–fitness tradeoff: EDSM and GSM\+AIC over\-merge to universal acceptors, RPNI and k\-Tails \(k≥2k\{\\geq\}2\) under\-merge to10210^\{2\}–10510^\{5\}states, and Alergia matches our fitness with 1\.0–6\.0×\\timesmore states via stochastic merges\. Our deterministic merge gives the stable topology the downstream pipelines depend on\.*Compactness makes per\-state estimation reliable*: a small state set pools enough observations per state to make positive\-only learning well\-conditioned, and the same FSM serves workflow memory, next\-step prediction, failure prediction, and runtime monitoring without four bespoke pipelines\.

##### FSM state is structural\.

The stateqtq\_\{t\}summarizes the prefix; two traces with identical activity counts but different orderings land in distinct states\. Length alone yields AUROC 0\.659 on SWE\-agent while structural features reach 0\.790 \(Appendix[H\.3](https://arxiv.org/html/2608.23670#A8.SS3)\); AWM’s linear workflows collapse on low\-success datasets \(74\.7% on SWE\-smith, 28\.5% on tau2\-telecom\) where our FSM reaches 100% / 45\.6% \(Table[4](https://arxiv.org/html/2608.23670#S4.T4)\)\. This per\-state decomposition locates*where*a trace deviates and drives both the early\-stopping monitor at 32% completion and cross\-model transfer \(0\.786mean cross\-AUROC vs\. 0\.877 self; Appendix[C\.1](https://arxiv.org/html/2608.23670#A3.SS1)\)\. The same per\-state features lift MLP, GRU, and Transformer baselines on 20 of 21 dataset\-architecture pairs over matched sequence features \(Appendix[E\.6](https://arxiv.org/html/2608.23670#A5.SS6)\), so the FSM complements learned sequence models\.

##### When and how invariant?

The topology is invariant to model choice across all three tau2\-bench suites, and robust to extraction granularity: our default granularity matches or exceeds role\-only held\-out AUROC on 10 of 12 datasets, the exceptions being datasets whose role\-only alphabet degenerates to at most three symbols \(Appendix[G\.2](https://arxiv.org/html/2608.23670#A7.SS2)\)\. This is consistent with system\-level rather than model\-level structure\. For agents with much larger action spaces or weaker conditional structure the same construction still applies but the FSM is no longer compact, and the per\-state observation density that drives our downstream gains would degrade accordingly\.

The construction itself is classical\([Daciuk et al\., 2000](https://arxiv.org/html/2608.23670#bib.bib48);[Hopcroft et al\., 2006](https://arxiv.org/html/2608.23670#bib.bib26)\); the setting is new\. Bounded LLM\-agent alphabets leave enough observations per state for the per\-state estimates to be well\-conditioned \(Proposition[6](https://arxiv.org/html/2608.23670#Thmtheorem6), Corollary[7](https://arxiv.org/html/2608.23670#Thmtheorem7)\), which is what lets one automaton carry all four tasks instead of four bespoke pipelines\.

## 6Limitations

The FSM accepts the directly\-follows closure of the observed traces, not the agent’s generating language; adversarial traces preserving activity bigram statistics can replay \(Theorem[3](https://arxiv.org/html/2608.23670#Thmtheorem3), Appendix[E\.7](https://arxiv.org/html/2608.23670#A5.SS7)\)\. The activity\-extraction functionϕ\\phiis dataset\-specific and requires minimal but non\-zero domain knowledge; it is robust across granularities on the datasets tested in depth \(Appendix[G\.2](https://arxiv.org/html/2608.23670#A7.SS2)\), and fully automaticϕ\\phidiscovery is future work\. We measure cross\-model transfer \(0\.7860\.786mean cross\-AUROC\) on three tau2\-bench suites; broader cross\-architecture and cross\-domain transfer is future work\. We compare LLM\-context workflow memory against AWM\([Wang et al\., 2025d](https://arxiv.org/html/2608.23670#bib.bib2)\)only, leaving concurrent success\-and\-failure memory methods such as ReasoningBank\([Ouyang et al\., 2025](https://arxiv.org/html/2608.23670#bib.bib51)\)to future work\.

## 7Conclusion

We extract compact finite\-state machines from LLM agent traces using only positive examples: the resulting compact FSMs \(7–43 states\) support workflow memory \(beating AWM on all eight datasets\), next\-step prediction, failure prediction \(AUROC up to 0\.94\), and an early\-stopping runtime monitor\. A single hyperparameter\-free construction underwrites all four in milliseconds, replacing four bespoke learned pipelines with one structural primitive\. Despite their apparent complexity, LLM agents admit compact structural abstractions: a deployable substrate for safety auditing, runtime monitoring, and behavioral analysis\.

## References

- Alkhammashet al\.\(2024\)H\. Alkhammash, A\. Polyvyanyy, and A\. MoffatStochastic directly\-follows process discovery using grammatical inference\.InAdvanced Information Systems Engineering \(CAiSE\),Lecture Notes in Computer Science, Vol\.14663,pp\. 87–103\.Cited by:[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px3.p1.1)\.
- Angluin \(1980\)D\. AngluinInductive inference of formal languages from positive data\.Information and Control45\(2\),pp\. 117–135\.External Links:ISSN 0019\-9958,[Document](https://dx.doi.org/10.1016/S0019-9958%2880%2990285-5),[Link](https://www.sciencedirect.com/science/article/pii/S0019995880902855)Cited by:[§1](https://arxiv.org/html/2608.23670#S1.p3.1),[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px4.p1.1)\.
- Angluin \(1987\)D\. AngluinLearning regular sets from queries and counterexamples\.Information and Computation75\(2\),pp\. 87–106\.External Links:[Document](https://dx.doi.org/10.1016/0890-5401%2887%2990052-6)Cited by:[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px4.p1.1)\.
- Barreset al\.\(2025\)V\. Barres, H\. Dong, S\. Ray, X\. Si, and K\. Narasimhanτ2\\tau^\{2\}\-Bench: evaluating conversational agents in a dual\-control environment\.External Links:2506\.07982,[Link](https://arxiv.org/abs/2506.07982)Cited by:[§B\.1](https://arxiv.org/html/2608.23670#A2.SS1.SSS0.Px4.p1.1)\.
- Bertiet al\.\(2024a\)A\. Berti, H\. Kourani, H\. Häfke, C\. Li, and D\. SchusterEvaluating large language models in process mining: capabilities, benchmarks, and evaluation strategies\.InEnterprise, Business\-Process and Information Systems Modeling,pp\. 13–21\.External Links:ISBN 9783031610073,ISSN 1865\-1356,[Link](http://dx.doi.org/10.1007/978-3-031-61007-3_2),[Document](https://dx.doi.org/10.1007/978-3-031-61007-3%5F2)Cited by:[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px3.p1.1)\.
- Bertiet al\.\(2024b\)A\. Berti, M\. Maatallah, U\. Jessen, M\. Sroka, and S\. A\. GhannouchiRe\-thinking process mining in the ai\-based agents era\.External Links:2408\.07720,[Link](https://arxiv.org/abs/2408.07720)Cited by:[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px3.p1.1)\.
- Bertiet al\.\(2019\)A\. Berti, S\. J\. van Zelst, and W\. van der AalstProcess mining for python \(pm4py\): bridging the gap between process\- and data science\.External Links:1905\.06169,[Link](https://arxiv.org/abs/1905.06169)Cited by:[§4\.1](https://arxiv.org/html/2608.23670#S4.SS1.p1.1)\.
- Biermann and Feldman \(1972\)A\. W\. Biermann and J\. A\. FeldmanOn the synthesis of finite\-state machines from samples of their behavior\.IEEE Transactions on ComputersC\-21\(6\),pp\. 592–597\.Cited by:[§D\.2](https://arxiv.org/html/2608.23670#A4.SS2.SSS0.Px6.p1.1),[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px4.p1.1),[§4\.2](https://arxiv.org/html/2608.23670#S4.SS2.p1.1)\.
- Carrasco and Oncina \(1994\)R\. C\. Carrasco and J\. OncinaLearning stochastic regular grammars by means of a state merging method\.InGrammatical Inference and Applications,Lecture Notes in Computer Science, Vol\.862,pp\. 139–152\.External Links:[Document](https://dx.doi.org/10.1007/3-540-58473-0%5F214)Cited by:[§D\.2](https://arxiv.org/html/2608.23670#A4.SS2.SSS0.Px1.p1.1),[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px4.p1.1)\.
- Cemriet al\.\(2025\)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\. StoicaWhy do multi\-agent LLM systems fail?\.InThe Thirty\-ninth Annual Conference on Neural Information Processing Systems Datasets and Benchmarks Track,External Links:[Link](https://openreview.net/forum?id=fAjbYBmonr)Cited by:[§1](https://arxiv.org/html/2608.23670#S1.p2.1),[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px1.p1.1)\.
- Chanet al\.\(2024\)C\. Chan, J\. Yu, W\. Chen, C\. Jiang, X\. Liu, W\. Shi, Z\. Liu, W\. Xue, and Y\. GuoAgentMonitor: a plug\-and\-play framework for predictive and secure multi\-agent systems\.External Links:2408\.14972,[Link](https://arxiv.org/abs/2408.14972)Cited by:[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px1.p1.1)\.
- Chenet al\.\(2025\)Z\. Chen, M\. Kang, and B\. LiShieldAgent: shielding agents via verifiable safety policy reasoning\.InForty\-second International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=DkRYImuQA9)Cited by:[§1](https://arxiv.org/html/2608.23670#S1.p2.1),[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px1.p1.1)\.
- Choet al\.\(2014\)K\. Cho, B\. van Merriënboer, C\. Gulcehre, D\. Bahdanau, F\. Bougares, H\. Schwenk, and Y\. BengioLearning phrase representations using RNN encoder–decoder for statistical machine translation\.InProceedings of the 2014 Conference on Empirical Methods in Natural Language Processing \(EMNLP\),A\. Moschitti, B\. Pang, and W\. Daelemans \(Eds\.\),Doha, Qatar,pp\. 1724–1734\.External Links:[Link](https://aclanthology.org/D14-1179/),[Document](https://dx.doi.org/10.3115/v1/D14-1179)Cited by:[§E\.6](https://arxiv.org/html/2608.23670#A5.SS6.p1.1)\.
- Daciuket al\.\(2000\)J\. Daciuk, S\. Mihov, B\. W\. Watson, and R\. E\. WatsonIncremental construction of minimal acyclic finite\-state automata\.Computational Linguistics26\(1\),pp\. 3–16\.Cited by:[§5](https://arxiv.org/html/2608.23670#S5.SS0.SSS0.Px3.p2.1)\.
- Denget al\.\(2023\)X\. Deng, Y\. Gu, B\. Zheng, S\. Chen, S\. Stevens, B\. Wang, H\. Sun, and Y\. SuMind2Web: towards a generalist agent for the web\.InThirty\-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track,External Links:[Link](https://openreview.net/forum?id=kiYqbO3wqw)Cited by:[§B\.1](https://arxiv.org/html/2608.23670#A2.SS1.SSS0.Px3.p1.1),[§1](https://arxiv.org/html/2608.23670#S1.p1.1)\.
- Deshpandeet al\.\(2025\)D\. Deshpande, V\. Gangal, H\. Mehta, J\. Krishnan, A\. Kannappan, and R\. QianTRAIL: trace reasoning and agentic issue localization\.External Links:2505\.08638,[Link](https://arxiv.org/abs/2505.08638)Cited by:[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px1.p1.1)\.
- Gold \(1967\)E\. M\. GoldLanguage identification in the limit\.Information and Control10\(5\),pp\. 447–474\.External Links:[Document](https://dx.doi.org/10.1016/S0019-9958%2867%2991165-5)Cited by:[§1](https://arxiv.org/html/2608.23670#S1.p3.1),[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px4.p1.1),[§3\.4](https://arxiv.org/html/2608.23670#S3.SS4.p4.1),[§5](https://arxiv.org/html/2608.23670#S5.SS0.SSS0.Px1.p1.1)\.
- Heet al\.\(2025\)X\. He, D\. Wu, Y\. Zhai, and K\. SunSentinelAgent: graph\-based anomaly detection in multi\-agent systems\.External Links:2505\.24201,[Link](https://arxiv.org/abs/2505.24201)Cited by:[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px1.p1.1)\.
- Honget al\.\(2024\)S\. Hong, M\. Zhuge, J\. Chen, X\. Zheng, Y\. Cheng, J\. Wang, C\. Zhang, Z\. Wang, S\. K\. S\. Yau, Z\. Lin, L\. Zhou, C\. Ran, L\. Xiao, C\. Wu, and J\. SchmidhuberMetaGPT: meta programming for a multi\-agent collaborative framework\.InThe Twelfth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=VtmBAGCN7o)Cited by:[§1](https://arxiv.org/html/2608.23670#S1.p1.1)\.
- Hopcroftet al\.\(2006\)J\. E\. Hopcroft, R\. Motwani, and J\. D\. UllmanIntroduction to automata theory, languages, and computation\.3rd edition,Pearson\.External Links:ISBN 9780321455369Cited by:[§5](https://arxiv.org/html/2608.23670#S5.SS0.SSS0.Px3.p2.1)\.
- Huanget al\.\(2026\)X\. Huang, J\. Hu, R\. Roy, C\. Wu, Y\. Dong, and X\. HuangPrefixGuard: from llm\-agent traces to online failure\-warning monitors\.External Links:2605\.06455,[Link](https://arxiv.org/abs/2605.06455)Cited by:[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px1.p1.1)\.
- Kohet al\.\(2024\)J\. Y\. Koh, R\. Lo, L\. Jang, V\. Duvvur, M\. Lim, P\. Huang, G\. Neubig, S\. Zhou, R\. Salakhutdinov, and D\. FriedVisualWebArena: evaluating multimodal agents on realistic visual web tasks\.InProceedings of the 62nd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),L\. Ku, A\. Martins, and V\. Srikumar \(Eds\.\),Bangkok, Thailand,pp\. 881–905\.External Links:[Link](https://aclanthology.org/2024.acl-long.50/),[Document](https://dx.doi.org/10.18653/v1/2024.acl-long.50)Cited by:[§1](https://arxiv.org/html/2608.23670#S1.p1.1)\.
- Langet al\.\(1998\)K\. J\. Lang, B\. A\. Pearlmutter, and R\. A\. PriceResults of the Abbadingo one DFA learning competition and a new evidence\-driven state merging algorithm\.InProceedings of the 4th International Colloquium on Grammatical Inference \(ICGI\),Lecture Notes in Artificial Intelligence, Vol\.1433,pp\. 1–12\.Cited by:[§D\.2](https://arxiv.org/html/2608.23670#A4.SS2.SSS0.Px3.p1.1),[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px4.p1.1)\.
- Liet al\.\(2026\)Y\. Li, H\. Luo, Y\. Xie, Y\. Fu, Z\. Yang, S\. Shao, Q\. Ren, W\. Qu, Y\. Fu, Y\. Yang, J\. Shao, X\. Hu, and D\. LiuATBench: a diverse and realistic agent trajectory benchmark for safety evaluation and diagnosis\.arXiv preprint arXiv:2604\.02022\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2604.02022),[Link](https://arxiv.org/abs/2604.02022)Cited by:[§4\.3](https://arxiv.org/html/2608.23670#S4.SS3.p1.1)\.
- Liuet al\.\(2025\)J\. Liu, B\. Ruan, X\. Yang, Z\. Lin, Y\. Liu, Y\. Wang, T\. Wei, and Z\. LiangTraceAegis: securing llm\-based agents via hierarchical and behavioral anomaly detection\.External Links:2510\.11203,[Link](https://arxiv.org/abs/2510.11203)Cited by:[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px1.p1.1)\.
- Luet al\.\(2025\)Q\. Lu, W\. Shao, Z\. Liu, L\. Du, F\. Meng, B\. Li, B\. Chen, S\. Huang, K\. Zhang, and P\. LuoGUI\-Odyssey: a comprehensive dataset for cross\-app GUI navigation on mobile devices\.InProceedings of the IEEE/CVF International Conference on Computer Vision \(ICCV\),Cited by:[§B\.1](https://arxiv.org/html/2608.23670#A2.SS1.SSS0.Px8.p1.1)\.
- Muškardinet al\.\(2022\)E\. Muškardin, B\. K\. Aichernig, I\. Pill, A\. Pferscher, and M\. TapplerAALpy: an active automata learning library\.Innovations in Systems and Software Engineering18\(3\),pp\. 417–426\.External Links:[Document](https://dx.doi.org/10.1007/s11334-022-00449-3)Cited by:[§D\.3](https://arxiv.org/html/2608.23670#A4.SS3.SSS0.Px2.p1.1),[§4\.1](https://arxiv.org/html/2608.23670#S4.SS1.p1.1)\.
- Oncina and García \(1992\)J\. Oncina and P\. GarcíaInferring regular languages in polynomial time\.InPattern Recognition and Image Analysis,pp\. 49–61\.Cited by:[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px4.p1.1)\.
- Ouyanget al\.\(2025\)S\. Ouyang, J\. Yan, I\. Hsu, Y\. Chen, K\. Jiang, Z\. Wang, R\. Han, L\. T\. Le, S\. Daruki, X\. Tang, V\. Tirumalashetty, G\. Lee, M\. Rofouei, H\. Lin, J\. Han, C\. Lee, and T\. PfisterReasoningBank: scaling agent self\-evolving with reasoning memory\.External Links:2509\.25140,[Link](https://arxiv.org/abs/2509.25140)Cited by:[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px2.p1.1),[§6](https://arxiv.org/html/2608.23670#S6.p1.1)\.
- Rabiner \(1989\)L\. R\. RabinerA tutorial on hidden Markov models and selected applications in speech recognition\.Proceedings of the IEEE77\(2\),pp\. 257–286\.External Links:[Document](https://dx.doi.org/10.1109/5.18626)Cited by:[§D\.2](https://arxiv.org/html/2608.23670#A4.SS2.SSS0.Px2.p1.1),[§D\.3](https://arxiv.org/html/2608.23670#A4.SS3.SSS0.Px4.p1.1),[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px4.p1.1)\.
- Ruanet al\.\(2024\)Y\. Ruan, H\. Dong, A\. Wang, S\. Pitis, Y\. Zhou, J\. Ba, Y\. Dubois, C\. J\. Maddison, and T\. HashimotoIdentifying the risks of LM agents with an LM\-emulated sandbox\.InThe Twelfth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=GEcwtMk1uA)Cited by:[§1](https://arxiv.org/html/2608.23670#S1.p2.1)\.
- Schicket al\.\(2023\)T\. Schick, J\. Dwivedi\-Yu, R\. Dessi, R\. Raileanu, M\. Lomeli, E\. Hambro, L\. Zettlemoyer, N\. Cancedda, and T\. ScialomToolformer: language models can teach themselves to use tools\.InThirty\-seventh Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=Yacmpz84TH)Cited by:[§1](https://arxiv.org/html/2608.23670#S1.p1.1)\.
- Shinnet al\.\(2023\)N\. Shinn, F\. Cassano, A\. Gopinath, K\. R\. Narasimhan, and S\. YaoReflexion: language agents with verbal reinforcement learning\.InThirty\-seventh Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=vAElhFcKW6)Cited by:[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px2.p1.1)\.
- Songet al\.\(2024\)Y\. Song, D\. Yin, X\. Yue, J\. Huang, S\. Li, and B\. Y\. LinTrial and error: exploration\-based trajectory optimization of LLM agents\.InProceedings of the 62nd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),L\. Ku, A\. Martins, and V\. Srikumar \(Eds\.\),Bangkok, Thailand,pp\. 7584–7600\.External Links:[Link](https://aclanthology.org/2024.acl-long.409/),[Document](https://dx.doi.org/10.18653/v1/2024.acl-long.409)Cited by:[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px2.p1.1)\.
- Sumerset al\.\(2024\)T\. Sumers, S\. Yao, K\. R\. Narasimhan, and T\. L\. GriffithsCognitive architectures for language agents\.Transactions on Machine Learning Research\.External Links:ISSN 2835\-8856,[Link](https://openreview.net/forum?id=1i6ZCvflQJ)Cited by:[§1](https://arxiv.org/html/2608.23670#S1.p1.1)\.
- van der Aalst \(2016\)W\. M\. P\. van der AalstProcess mining: data science in action\.2 edition,Springer\.External Links:[Document](https://dx.doi.org/10.1007/978-3-662-49851-4)Cited by:[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px3.p1.1)\.
- Vaswaniet al\.\(2017\)A\. Vaswani, N\. Shazeer, N\. Parmar, J\. Uszkoreit, L\. Jones, A\. N\. Gomez, Ł\. Kaiser, and I\. PolosukhinAttention is all you need\.InAdvances in Neural Information Processing Systems,I\. Guyon, U\. V\. Luxburg, S\. Bengio, H\. Wallach, R\. Fergus, S\. Vishwanathan, and R\. Garnett \(Eds\.\),Vol\.30,pp\.\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf)Cited by:[§E\.6](https://arxiv.org/html/2608.23670#A5.SS6.p1.1)\.
- Wanget al\.\(2025a\)H\. Wang, C\. M\. Poskitt, and J\. SunAgentSpec: customizable runtime enforcement for safe and reliable llm agents\.External Links:2503\.18666,[Link](https://arxiv.org/abs/2503.18666)Cited by:[§1](https://arxiv.org/html/2608.23670#S1.p2.1),[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px1.p1.1)\.
- Wanget al\.\(2025b\)H\. Wang, C\. M\. Poskitt, J\. Wei, and J\. SunProbGuard: probabilistic runtime monitoring for llm agent safety\.External Links:2508\.00500,[Link](https://arxiv.org/abs/2508.00500)Cited by:[§G\.6](https://arxiv.org/html/2608.23670#A7.SS6.p1.1),[Table 27](https://arxiv.org/html/2608.23670#A7.T27),[Table 27](https://arxiv.org/html/2608.23670#A7.T27.4),[Table 27](https://arxiv.org/html/2608.23670#A7.T27.5.1.2.1),[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px1.p1.1)\.
- Wanget al\.\(2024\)L\. Wang, C\. Ma, X\. Feng, Z\. Zhang, H\. Yang, J\. Zhang, Z\. Chen, J\. Tang, X\. Chen, Y\. Lin, W\. X\. Zhao, Z\. Wei, and J\. WenA survey on large language model based autonomous agents\.Frontiers of Computer Science18\(6\)\.External Links:ISSN 2095\-2236,[Link](http://dx.doi.org/10.1007/s11704-024-40231-1),[Document](https://dx.doi.org/10.1007/s11704-024-40231-1)Cited by:[§1](https://arxiv.org/html/2608.23670#S1.p1.1)\.
- Wanget al\.\(2025c\)X\. Wang, B\. Wang, D\. Lu, J\. Yang, T\. Xie, J\. Wang, J\. Deng, X\. Guo, Y\. Xu, C\. H\. Wu, Z\. Shen, Z\. Li, R\. Li, X\. Li, J\. Chen, Z\. Boyuan, P\. Li, F\. Lei, R\. Cao, Y\. Fu, D\. Shin, M\. Shin, H\. Jiarui, Y\. Wang, J\. Chen, Y\. Ye, D\. Zhang, Y\. Wang, H\. Wang, D\. Yang, V\. Zhong, Y\. Charles, Z\. Yang, and T\. YuOpenCUA: open foundations for computer\-use agents\.InThe Thirty\-ninth Annual Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=6iRZvJiC9Q)Cited by:[§B\.1](https://arxiv.org/html/2608.23670#A2.SS1.SSS0.Px6.p1.1),[§1](https://arxiv.org/html/2608.23670#S1.p1.1)\.
- Wanget al\.\(2025d\)Z\. Z\. Wang, J\. Mao, D\. Fried, and G\. NeubigAgent workflow memory\.InForty\-second International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=NTAhi2JEEE)Cited by:[§D\.2](https://arxiv.org/html/2608.23670#A4.SS2.SSS0.Px4.p1.1),[§D\.3](https://arxiv.org/html/2608.23670#A4.SS3.SSS0.Px6.p1.1),[§G\.8](https://arxiv.org/html/2608.23670#A7.SS8.p1.1),[1st item](https://arxiv.org/html/2608.23670#S1.I1.i1.p1.1),[§1](https://arxiv.org/html/2608.23670#S1.p2.1),[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px2.p1.1),[§4\.2](https://arxiv.org/html/2608.23670#S4.SS2.SSS0.Px2.p1.1),[§4\.2](https://arxiv.org/html/2608.23670#S4.SS2.SSS0.Px4.p1.1),[Table 3](https://arxiv.org/html/2608.23670#S4.T3.6.3.1.1),[§6](https://arxiv.org/html/2608.23670#S6.p1.1)\.
- Weiet al\.\(2022\)J\. Wei, X\. Wang, D\. Schuurmans, M\. Bosma, brian ichter, F\. Xia, E\. H\. Chi, Q\. V\. Le, and D\. ZhouChain of thought prompting elicits reasoning in large language models\.InAdvances in Neural Information Processing Systems,A\. H\. Oh, A\. Agarwal, D\. Belgrave, and K\. Cho \(Eds\.\),External Links:[Link](https://openreview.net/forum?id=_VjQlMeSB_J)Cited by:[§1](https://arxiv.org/html/2608.23670#S1.p1.1)\.
- Wuet al\.\(2024a\)Q\. Wu, G\. Bansal, J\. Zhang, Y\. Wu, B\. Li, E\. Zhu, L\. Jiang, X\. Zhang, S\. Zhang, J\. Liu, A\. H\. Awadallah, R\. W\. White, D\. Burger, and C\. WangAutoGen: enabling next\-gen LLM applications via multi\-agent conversations\.InFirst Conference on Language Modeling,External Links:[Link](https://openreview.net/forum?id=BAakY1hNKS)Cited by:[§1](https://arxiv.org/html/2608.23670#S1.p1.1)\.
- Wuet al\.\(2024b\)Y\. Wu, T\. Yue, S\. Zhang, C\. Wang, and Q\. WuStateFlow: enhancing LLM task\-solving through state\-driven workflows\.InFirst Conference on Language Modeling,External Links:[Link](https://openreview.net/forum?id=3nTbuygoop)Cited by:[§1](https://arxiv.org/html/2608.23670#S1.p2.1),[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px2.p1.1)\.
- Xieet al\.\(2024\)T\. Xie, D\. Zhang, J\. Chen, X\. Li, S\. Zhao, R\. Cao, T\. J\. Hua, Z\. Cheng, D\. Shin, F\. Lei, Y\. Liu, Y\. Xu, S\. Zhou, S\. Savarese, C\. Xiong, V\. Zhong, and T\. YuOSWorld: benchmarking multimodal agents for open\-ended tasks in real computer environments\.InThe Thirty\-eight Conference on Neural Information Processing Systems Datasets and Benchmarks Track,External Links:[Link](https://openreview.net/forum?id=tN61DTr4Ed)Cited by:[§1](https://arxiv.org/html/2608.23670#S1.p1.1)\.
- Yanget al\.\(2024\)J\. Yang, C\. E\. Jimenez, A\. Wettig, K\. Lieret, S\. Yao, K\. R\. Narasimhan, and O\. PressSWE\-agent: agent\-computer interfaces enable automated software engineering\.InThe Thirty\-eighth Annual Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=mXpq6ut8J3)Cited by:[§B\.1](https://arxiv.org/html/2608.23670#A2.SS1.SSS0.Px7.p1.1),[§1](https://arxiv.org/html/2608.23670#S1.p1.1)\.
- Yanget al\.\(2025\)J\. Yang, K\. Lieret, C\. E\. Jimenez, A\. Wettig, K\. Khandpur, Y\. Zhang, B\. Hui, O\. Press, L\. Schmidt, and D\. YangSWE\-smith: scaling data for software engineering agents\.InThe Thirty\-ninth Annual Conference on Neural Information Processing Systems Datasets and Benchmarks Track,External Links:[Link](https://openreview.net/forum?id=63iVrXc8cC)Cited by:[§B\.1](https://arxiv.org/html/2608.23670#A2.SS1.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2608.23670#S1.p1.1)\.
- Yaoet al\.\(2025\)S\. Yao, N\. Shinn, P\. Razavi, and K\. R\. Narasimhan\{$\\tau$\}\-bench: a benchmark for \\underline\{t\}ool\-\\underline\{a\}gent\-\\underline\{u\}ser interaction in real\-world domains\.InThe Thirteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=roNSXZpUDN)Cited by:[§1](https://arxiv.org/html/2608.23670#S1.p1.1)\.
- Yaoet al\.\(2023\)S\. Yao, J\. Zhao, D\. Yu, N\. Du, I\. Shafran, K\. R\. Narasimhan, and Y\. CaoReAct: synergizing reasoning and acting in language models\.InThe Eleventh International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=WE_vluYUL-X)Cited by:[§1](https://arxiv.org/html/2608.23670#S1.p1.1)\.
- Zhanget al\.\(2025a\)H\. Zhang, J\. Huang, K\. Mei, Y\. Yao, Z\. Wang, C\. Zhan, H\. Wang, and Y\. ZhangAgent security bench \(ASB\): formalizing and benchmarking attacks and defenses in LLM\-based agents\.InThe Thirteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=V4y0CpX4hK)Cited by:[§1](https://arxiv.org/html/2608.23670#S1.p2.1)\.
- Zhanget al\.\(2025b\)J\. Zhang, J\. Xiang, Z\. Yu, F\. Teng, X\. Chen, J\. Chen, M\. Zhuge, X\. Cheng, S\. Hong, J\. Wang, B\. Zheng, B\. Liu, Y\. Luo, and C\. WuAFlow: automating agentic workflow generation\.InThe Thirteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=z5uVAKwmjf)Cited by:[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px2.p1.1)\.
- Zhanget al\.\(2025c\)S\. Zhang, M\. Yin, J\. Zhang, J\. Liu, Z\. Han, J\. Zhang, B\. Li, C\. Wang, H\. Wang, Y\. Chen, and Q\. WuWhich agent causes task failures and when? on automated failure attribution of LLM multi\-agent systems\.InForty\-second International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=GazlTYxZss)Cited by:[§B\.1](https://arxiv.org/html/2608.23670#A2.SS1.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2608.23670#S1.p2.1)\.
- Zhanget al\.\(2025d\)Y\. Zhang, X\. Liu, and C\. XiaoMetaAgent: automatically constructing multi\-agent systems based on finite state machines\.InForty\-second International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=vOxaD3hhPt)Cited by:[§1](https://arxiv.org/html/2608.23670#S1.p2.1),[§2](https://arxiv.org/html/2608.23670#S2.SS0.SSS0.Px2.p1.1)\.
- Zhouet al\.\(2024\)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\. NeubigWebArena: a realistic web environment for building autonomous agents\.InThe Twelfth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=oKn9c6ytLx)Cited by:[§B\.1](https://arxiv.org/html/2608.23670#A2.SS1.SSS0.Px5.p1.1),[§1](https://arxiv.org/html/2608.23670#S1.p1.1)\.

## Appendix ATheory and Proofs

### A\.1Extraction Algorithm

> Algorithm 1 \(FSM extraction\)\. Input:Traces𝒟=\{τ1,…,τN\}\\mathcal\{D\}=\\\{\\tau\_\{1\},\\ldots,\\tau\_\{N\}\\\}, extractionϕ\\phi\.Output:FSMℳ=\(Q,𝒜,δ,q0\)\\mathcal\{M\}=\(Q,\\mathcal\{A\},\\delta,q\_\{0\}\)\. 1. 1\.For eachτ∈𝒟\\tau\\in\\mathcal\{D\}: insertσ=\(ϕ⁡\(m1\),…,ϕ⁡\(mT\)\)\\sigma=\(\\phi\(m\_\{1\}\),\\dots,\\phi\(m\_\{T\}\)\)into the prefix tree, extending states and transitions\. 2. 2\.Assign each trie stateqqto the classκ⁡\(q\)\\kappa\(q\)of its incoming activity \(root↦init\\mapsto\\mathrm\{init\}\); for each trie edgeq→𝑎q′q\\xrightarrow\{a\}q^\{\\prime\}add the transitionκ⁡\(q\)→𝑎κ⁡\(q′\)\\kappa\(q\)\\xrightarrow\{a\}\\kappa\(q^\{\\prime\}\), aggregating counts\. 3. 3\.Remove each transition with aggregated count11unless it is the only transition leaving its source; return\(Q,𝒜,δ,q0\)\(Q,\\mathcal\{A\},\\delta,q\_\{0\}\)\.

initsysusra:tctoola:txtsysusra:tca:txttoola:tca:txtusrFigure 5:Extracted FSMfor a customer service agent at role\-level granularity \(tau2\-bench airline, 6 states,\|𝒜\|=5\|\\mathcal\{A\}\|\{=\}5\)\. The tool\-level FSM \(18 states,\|𝒜\|=17\|\\mathcal\{A\}\|\{=\}17, Table[1](https://arxiv.org/html/2608.23670#S4.T1)\) further decomposesa:tc/toolinto per\-tool states\. The tool\-call loop \(a:tc↔\\leftrightarrowtool\) captures repeated API invocations; the conversational loop \(a:txt→\\tousr\) captures dialogue turns\.
### A\.2Proofs

###### Proof of Theorem[2](https://arxiv.org/html/2608.23670#Thmtheorem2)\.

Letσ=\(a1,…,aT\)\\sigma=\(a\_\{1\},\\ldots,a\_\{T\}\)be accepted by prefix tree𝒫\\mathcal\{P\}, visiting statesq0,q1,…,qTq\_\{0\},q\_\{1\},\\ldots,q\_\{T\}withδ⁡\(qi,ai\+1\)=qi\+1\\delta\(q\_\{i\},a\_\{i\+1\}\)=q\_\{i\+1\}\. Let\[q\]=κ⁡\(q\)\[q\]=\\kappa\(q\)denote the class ofqqunder the last\-activity merge \(its incoming activity, with\[q0\]=init\[q\_\{0\}\]=\\mathrm\{init\}\)\.

*Step 1 \(Edges survive\)\.*The merged transition function collects every trie edge:δℳ​\(\[q\],a\)=\[a\]\\delta\_\{\\mathcal\{M\}\}\(\[q\],a\)=\[a\]whenever some trie edge labelledaaleaves a member of\[q\]\[q\]\. In particular the trie edgeδ⁡\(qi,ai\+1\)=qi\+1\\delta\(q\_\{i\},a\_\{i\+1\}\)=q\_\{i\+1\}givesδℳ​\(\[qi\],ai\+1\)=\[ai\+1\]=\[qi\+1\]\\delta\_\{\\mathcal\{M\}\}\(\[q\_\{i\}\],a\_\{i\+1\}\)=\[a\_\{i\+1\}\]=\[q\_\{i\+1\}\], since the incoming activity ofqi\+1q\_\{i\+1\}isai\+1a\_\{i\+1\}\.

*Step 2 \(Acceptance\)\.*Applyδℳ\\delta\_\{\\mathcal\{M\}\}alongσ\\sigma:

\[q0\]→a1\[q1\]→a2⋯→aT\[qT\]\.\[q\_\{0\}\]\\xrightarrow\{a\_\{1\}\}\[q\_\{1\}\]\\xrightarrow\{a\_\{2\}\}\\cdots\\xrightarrow\{a\_\{T\}\}\[q\_\{T\}\]\.Every transition exists by Step 1, soσ\\sigmais accepted byℳ\\mathcal\{M\}\.

Step 3 filtering may subsequently remove a transition whose aggregated count is one, unless it is its source’s only continuation; this is the only mechanism by which a trace fails to replay, and the replay\-fitness columns of Table[1](https://arxiv.org/html/2608.23670#S4.T1)measure exactly this cost\. ∎

###### Proof of Theorem[3](https://arxiv.org/html/2608.23670#Thmtheorem3)\.

Letκ⁡\(q\)\\kappa\(q\)denote the activity on the edge entering trie stateqq, withκ⁡\(qε\)=init\\kappa\(q\_\{\\varepsilon\}\)=\\mathrm\{init\}for the root: the congruence mergesq∼q′q\\sim q^\{\\prime\}iffκ⁡\(q\)=κ⁡\(q′\)\\kappa\(q\)=\\kappa\(q^\{\\prime\}\), so the classes are exactly the\|𝒜\|\+1\|\\mathcal\{A\}\|\+1values ofκ\\kappa\.

*Determinism\.*A quotient edge\[u\]→𝑎\[u​a\]\[u\]\\xrightarrow\{a\}\[ua\]exists iff some training trace contains the bigram\(κ⁡\(u\),a\)\(\\kappa\(u\),a\): the target class isκ⁡\(u​a\)=a\\kappa\(ua\)=a, which is determined by the input symbolaaalone, so each\(\[u\],a\)\(\[u\],a\)has at most one target and the FSM is deterministic\.

*Transitions\.*A class carries the union of its members’ out\-edges, so merging only adds transitions; every trie path survives the merge, and before filtering every training trace is accepted by Theorem[2](https://arxiv.org/html/2608.23670#Thmtheorem2)\. Step 3 then drops each transition whose aggregated count is one unless it is its source’s only continuation; this removes edges, never states\.

*Uniqueness\.*Both the class mapκ\\kappaand the edge set \(the retained observed bigrams; Step 3 thresholds on their counts\) are functions of the multiset of training transitions alone, hence invariant to trace order and to which traces are drawn from a fixed corpus\. The extracted FSM is therefore unique: this is the directly\-follows automaton of𝒟\\mathcal\{D\}; it is not the minimal DFA of the finite prefix languageL𝒫L\_\{\\mathcal\{P\}\}\(which is acyclic\), but it is the compact acceptor whose states track the most recent activity\. ∎

###### Proof of Proposition[5](https://arxiv.org/html/2608.23670#Thmtheorem5)\.

Lete1,…,eke\_\{1\},\\ldots,e\_\{k\}be thekktransitions ofℳ∗\\mathcal\{M\}^\{\*\}, withpj=Pr⁡\[ej​appears in a random trace\]≥pminp\_\{j\}=\\Pr\[e\_\{j\}\\text\{ appears in a random trace\}\]\\geq p\_\{\\min\}\. AfterNNi\.i\.d\. traces:

Pr⁡\[ej​not observed\]\\displaystyle\\Pr\[e\_\{j\}\\text\{ not observed\}\]=\(1−pj\)N≤e−N​pmin,\\displaystyle=\(1\-p\_\{j\}\)^\{N\}\\;\\leq\\;e^\{\-Np\_\{\\min\}\},\(6\)Pr\[∃j:ejnot observed\]\\displaystyle\\Pr\[\\exists\\,j:\\;e\_\{j\}\\text\{ not observed\}\]≤k⋅e−N​pmin\.\(union bound\)\\displaystyle\\leq k\\cdot e^\{\-Np\_\{\\min\}\}\.\\quad\\text\{\(union bound\)\}\(7\)Setting the right\-hand side≤δ\\leq\\deltaand solving:

N≥1pmin​ln⁡\(k/δ\)\.N\\;\\geq\\;\\frac\{1\}\{p\_\{\\min\}\}\\ln\\\!\\bigl\(k/\\delta\\bigr\)\.When all transitions are observed, the prefix tree contains every transition ofℳ∗\\mathcal\{M\}^\{\*\}, and the directly\-follows quotient \(Theorem[3](https://arxiv.org/html/2608.23670#Thmtheorem3)\) yieldsℳ∗\\mathcal\{M\}^\{\*\}\. ∎

###### Proposition 6\(Transition estimator consistency and concentration\)\.

LetP∗\(⋅∣q\)P^\{\*\}\(\\cdot\\mid q\)denote the true transition distribution at stateqqunder an i\.i\.d\. trace distribution, letnqn\_\{q\}be the number of state\-visit observations, and letα∈\(0,1\]\\alpha\\in\(0,1\]\. For anyϵ\>0\\epsilon\>0,

Pr\[∥P^\(⋅∣q\)−P∗\(⋅∣q\)∥TV≥ϵ\+α​\|𝒜\|nq\+α​\|𝒜\|\]≤2\|𝒜\|exp\(−nq​ϵ22\)\.\\Pr\\\!\\left\[\\,\\big\\\|\\hat\{P\}\(\\cdot\\mid q\)\-P^\{\*\}\(\\cdot\\mid q\)\\big\\\|\_\{\\mathrm\{TV\}\}\\geq\\epsilon\+\\tfrac\{\\alpha\|\\mathcal\{A\}\|\}\{n\_\{q\}\+\\alpha\|\\mathcal\{A\}\|\}\\,\\right\]\\leq 2\|\\mathcal\{A\}\|\\exp\\\!\\left\(\-\\tfrac\{n\_\{q\}\\epsilon^\{2\}\}\{2\}\\right\)\.\(8\)The smoothing bias vanishes asnq→∞n\_\{q\}\\to\\infty, and‖P^−P∗‖TV→0\\\|\\hat\{P\}\-P^\{\*\}\\\|\_\{\\mathrm\{TV\}\}\\to 0almost surely\. \(Proof: Bretagnolle–Huber \+ Bernstein argument applied to multinomial transition counts\.\)

###### Corollary 7\(Surprise as log\-likelihood ratio\)\.

Suppose success and failure traces are generated by FSM\-structured mixturesP\+\(⋅∣q\),P−\(⋅∣q\)P^\{\+\}\(\\cdot\\mid q\),P^\{\-\}\(\\cdot\\mid q\)on the same state space\. The trace cross\-entropy computed from a success\-only transition model,CE\+\(τ\)=1T∑t−log2P^\+\(at∣qt\)\\mathrm\{CE\}^\{\+\}\(\\tau\)=\\tfrac\{1\}\{T\}\\sum\_\{t\}\-\\log\_\{2\}\\hat\{P\}^\{\+\}\(a\_\{t\}\\mid q\_\{t\}\), is a consistent estimator \(innqn\_\{q\}\) of the expected per\-step negative log\-likelihood underP\+P^\{\+\}\. Consequently, the per\-trace surprise differenceCE−​\(τ\)−CE\+​\(τ\)\\mathrm\{CE\}^\{\-\}\(\\tau\)\-\\mathrm\{CE\}^\{\+\}\(\\tau\)is a Neyman–Pearson\-optimal statistic for distinguishing success from failure traces up toO⁡\(1/nq\)O\(1/\\sqrt\{n\_\{q\}\}\)error\.

###### Proposition 8\(Online monitoring regret\)\.

Consider the runtime monitor that replays a traceτ\\tauof lengthTTthrough the FSM, maintains the cumulative log\-likelihood ratioLt​\(τ\)=∑s≤t\[log⁡P^−​\(as∣qs\)−log⁡P^\+​\(as∣qs\)\]L\_\{t\}\(\\tau\)=\\sum\_\{s\\leq t\}\\bigl\[\\log\\hat\{P\}^\{\-\}\(a\_\{s\}\\mid q\_\{s\}\)\-\\log\\hat\{P\}^\{\+\}\(a\_\{s\}\\mid q\_\{s\}\)\\bigr\]computed fromnqn\_\{q\}per\-state training observations, and declares failure the first timeLt​\(τ\)\>ηL\_\{t\}\(\\tau\)\>\\eta\. Under the success/failure mixture model of Corollary[7](https://arxiv.org/html/2608.23670#Thmtheorem7)with per\-step log\-ratio bounded byBB, the online decision rule attains expected regret

Regret⁡\(T\)=𝔼⁡\[∑t=1Tℓ⁡\(y^t\)−∑t=1Tℓ⁡\(yt∗\)\]≤B​2​T​log⁡\|Q\|\+T​\|𝒜\|nq\\mathrm\{Regret\}\(T\)\\;=\\;\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}\\ell\(\\hat\{y\}\_\{t\}\)\-\\sum\_\{t=1\}^\{T\}\\ell\(y^\{\\ast\}\_\{t\}\)\\right\]\\;\\leq\\;B\\sqrt\{2T\\log\|Q\|\}\\;\+\\;\\frac\{T\\,\|\\mathcal\{A\}\|\}\{\\sqrt\{n\_\{q\}\}\}\(9\)against the best state\-dependent threshold policy in hindsight, whereℓ\\ellis anyBB\-Lipschitz loss \(e\.g\., cost\-weighted misclassification\)\. The first term is the multi\-armed\-bandit regret over\|Q\|\|Q\|candidate state\-specific thresholds \(Azuma–Hoeffding on the martingaleLtL\_\{t\}\); the second is the plug\-in estimation error from Proposition[6](https://arxiv.org/html/2608.23670#Thmtheorem6)\.

The bound has two practical consequences: \(i\) regret is sub\-linear inTT, so the monitor catches failures faster than repeatedly relearning per\-trace statistics\. \(ii\) Compact\|Q\|\|Q\|\(our FSMs use 7–43 states\) makeslog⁡\|Q\|\\sqrt\{\\log\|Q\|\}small, while RPNI’s\|Q\|∼103\|Q\|\\\!\\sim\\\!10^\{3\}–10510^\{5\}inflates both terms\. Empirically, this matches Section[4\.3](https://arxiv.org/html/2608.23670#S4.SS3): the combined cycle\-rate \+ unique\-state rule achievesF1=0\.904F\_\{1\}\\\!=\\\!0\.904on SWE\-agent and flags failures at 32% completion, consistent with the sub\-linear\-regret early\-stopping theO⁡\(T\)O\(\\sqrt\{T\}\)bound guarantees\.

### A\.3Complexity Analysis

We detail the runtime of the three steps\. Step 1 \(prefix tree\): insertingNNtraces of mean lengthT¯\\bar\{T\}costsO⁡\(N​T¯\)O\(N\\bar\{T\}\)time and space, since each symbol extends a trie node via hash\-map lookup\. Step 2 \(last\-activity merge\): we map each trie node to the class of its incoming activity in a single pass, aggregating trie\-edge counts into a\(class,symbol,class\)\(\\text\{class\},\\text\{symbol\},\\text\{class\}\)transition multiset\. The pass merges all nodes reached by the same activity, giving\|𝒜\|\+1\|\\mathcal\{A\}\|\+1classes\. Step 3 \(rare\-transition filtering\): one sweep over the aggregated transitions, at mostO⁡\(\|𝒜\|2\)O\(\|\\mathcal\{A\}\|^\{2\}\), negligible against the trie passes\. The construction visits every node once and inspects each outgoing edge, givingO⁡\(\|Q𝒫\|⋅\|𝒜\|\)O\(\|Q\_\{\\mathcal\{P\}\}\|\\cdot\|\\mathcal\{A\}\|\)worst\-case time, where\|Q𝒫\|\|Q\_\{\\mathcal\{P\}\}\|is the number of prefix\-tree states\. Because\|Q𝒫\|≤N​T¯\|Q\_\{\\mathcal\{P\}\}\|\\leq N\\bar\{T\}, the total construction time isO⁡\(N​T¯⋅\|𝒜\|\)O\(N\\bar\{T\}\\cdot\|\\mathcal\{A\}\|\)\. In practice,\|𝒜\|≤42\|\\mathcal\{A\}\|\\leq 42across all twelve datasets and the hash\-map constant is small; we build all FSMs in<<110 ms on a single CPU core \(Table[13](https://arxiv.org/html/2608.23670#A4.T13)\), compared to 7–36 s for RPNI\.

## Appendix BDatasets and Setup

### B\.1Dataset Details

Table 5:Evaluation datasets\.\|𝒜\|\|\\mathcal\{A\}\|: alphabet size\.∗7 primary \+ 17 rare\.‡4 LLMs\.aTrivially separable\.DatasetDomainTraces\|𝒜\|\|\\mathcal\{A\}\|LabelsLabeled \(main results\)SWE\-smithCoding5009✓SWE\-agentCoding2,00024∗✓WebArenaWeb nav\.8,33724✓AgentNetDesktop GUI5,00024✓tau2\-bench \(air\)Cust\. svc\.800‡17✓tau2\-bench \(ret\)Cust\. svc\.1,824‡18✓tau2\-bench \(tel\)Telecom1,824‡42✓ATBenchSafety1,00014✓OSWorldDesktop OS2,16626✓Unlabeled \(Appendix[D\.1](https://arxiv.org/html/2608.23670#A4.SS1)\)Who\_and\_WhenMulti\-agent1848✗Mind2WebWeb nav\.5007✗GUI\-OdysseyMobile GUI7,7356✓a##### Who\_and\_When

\([Zhang et al\., 2025c](https://arxiv.org/html/2608.23670#bib.bib12)\)contains 184 multi\-agent failure traces with 8 activity types \(Table[5](https://arxiv.org/html/2608.23670#A2.T5)\)\. All traces represent failures in agent delegation tasks\. Activity extraction uses the actor role and action type fields\.

##### SWE\-smith

\([Yang et al\., 2025](https://arxiv.org/html/2608.23670#bib.bib10)\)generates coding agent traces from SWE\-bench task instances; we use 500 \(377 success, 123 failure\)\. Activities are extracted fromtool\_calls\[\]\.function\.namefields, yielding 9 unique activities \(bash,str\_replace\_editor,submit, etc\.\)\.

##### Mind2Web

\([Deng et al\., 2023](https://arxiv.org/html/2608.23670#bib.bib17)\)provides 2,350 web navigation tasks across 137 websites; we use a 500\-trace sample\. Activities are extracted from action representation strings in the format\[element\] description→\\toACTION: value, yielding 7 activity types \(CLICK,TYPE,SELECT, etc\.\)\.

##### tau2\-bench

\([Barres et al\., 2025](https://arxiv.org/html/2608.23670#bib.bib19)\)extends tau\-bench with multi\-model evaluation across three domains: airline \(800 traces, 17 activities\), retail \(1,824 traces, 18 activities\), and telecom \(1,824 traces, 42 activities\)\. Each domain contains traces from 4 LLMs \(GPT\-4\.1, Claude 3\.7 Sonnet, GPT\-4\.1\-mini, o4\-mini\)\. Activities are extracted fromtool\_calls\[\]\.name\. The telecom domain introduces a richer tool vocabulary \(42 activities including network diagnostics, SIM operations, billing\) than any other dataset, producing our largest FSM \(43 states\)\.

##### WebArena

\([Zhou et al\., 2024](https://arxiv.org/html/2608.23670#bib.bib11)\)is a benchmark of realistic web tasks \(shopping, forums, maps, GitLab\); we use 8,337 agent traces \(rollouts\)\. Activities are 12 normalized action types \(click,type,scroll\_down, etc\.\) combined with role prefixes, yielding\|𝒜\|=24\|\\mathcal\{A\}\|\{=\}24activity symbols\. Labels derive from task completion status \(13\.4% success\)\. This is our largest labeled dataset by trace count and produces the lowest compression ratio \(15×\\times\) because short web interaction traces \(median 5 steps\) give RPNI limited opportunity to overfit\.

##### AgentNet

\([Wang et al\., 2025c](https://arxiv.org/html/2608.23670#bib.bib30)\)provides desktop computer\-use agent trajectories; we use a 5,000\-trace sample from the OpenCUA Ubuntu subset, covering GUI automation across diverse applications\. Activities are extracted frompyautoguiaction primitives \(click,typewrite,hotkey,screenshot,moveTo, etc\.\), yielding 24 activities\. Labels derive from task completion annotations \(36\.4% success\)\. This dataset produces the second\-highest compression ratio \(2,500×\\times\) due to its large training set \(4,000 traces\) and diverse action vocabulary\.

##### SWE\-agent

\([Yang et al\., 2024](https://arxiv.org/html/2608.23670#bib.bib16)\)provides coding agent trajectories in Parquet format \(80,036 available\); we use a 2,000\-trace sample\. Raw commands are extracted from code blocks in assistant messages and grouped into 7 actor categories:search,navigate,edit,execute,submit,user, andassistant\. Combined with message\-type suffixes, these yield\|𝒜\|=24\|\\mathcal\{A\}\|\{=\}24activity symbols \(Table[5](https://arxiv.org/html/2608.23670#A2.T5)\)\. Labels derive from thetargetboolean field\.

##### GUI\-Odyssey

\([Lu et al\., 2025](https://arxiv.org/html/2608.23670#bib.bib29)\)contains 7,735 cross\-app mobile GUI navigation episodes across 201 apps on 6 Android devices\. Each step records an action type \(CLICK,TEXT,SCROLL,LONG\_PRESS,COMPLETE,INCOMPLETE\), yielding 6 activities\. Labels derive from episode success:COMPLETE\(7,486 successes\) vs\.INCOMPLETE\(249 failures\)\. This is our largest mobile\-GUI dataset and produces the highest compression ratio \(3,036×\\times\)\.

## Appendix CExtended Results and Figures

### C\.1Cross\-Model Transfer

The tau2\-bench datasets contain traces from four LLMs executing identical tasks, enabling cross\-model FSM transferability analysis\. For each source\-target model pair, we build an FSM from the source model’s training traces and evaluate replay fitness and failure prediction AUROC on the target model’s test traces\.

##### Structural transfer\.

A single FSM built from all four models’ traces achieves 1\.000 replay fitness on every model individually\. The behavioral topology is model\-invariant: all models traverse the same tool\-call sequences, differing only in transition probabilities\.

##### Failure prediction transfer \(3 suites\)\.

Augmented with the FSM cross\-entropy anomaly features \(Section[4\.3](https://arxiv.org/html/2608.23670#S4.SS3)\), the feature set produces moderate transfer\. We measure on all three tau2\-bench suites with 4 LLMs each \(12 off\-diagonal pairs per suite, 36 pairs total\)\.

Table 6:Cross\-model failure\-prediction AUROC across three tau2\-bench suites\.Self\-AUROC \(diagonal\) and mean cross\-AUROC \(off\-diagonal\);σ\\sigmaover the 4 self\-AUROCs and 12 cross\-pair AUROCs\. Mean cross\-AUROC across all 36 pairs is0\.786vs\. self mean0\.877\(0\.091 gap\)\. Self/cross fitness on airline 1\.000/0\.962, retail 1\.000/0\.972, telecom 1\.000/0\.990\.The transfer gap is consistent across suites \(range 0\.05–0\.15\), and cross\-AUROC remains≥\\geq0\.68 in mean on every suite, meaningfully above chance\. GPT\-4\.1→\\too4\-mini is the strongest cross\-pair \(telecom 0\.950, airline 0\.890, retail 0\.792\); o4\-mini→\\toClaude 3\.7 is the weakest on airline and retail \(0\.560, 0\.544\), whereas on telecom every cross\-pair stays≥\\geq0\.82\. Per\-model FSMs reach 0\.999–1\.000 self\-fitness on all three suites \(40–41 states each on telecom, matching airline and retail\)\. The combined all\-model FSM in every suite reaches 1\.000 fitness on each model individually, monitoring heterogeneous deployments without per\-model retraining\. Transition probabilities under the source model’s FSM remain partially informative when the target model’s surface behavior differs, because the surprise signal−log2⁡P⁡\(at∣qt\)\-\\log\_\{2\}P\(a\_\{t\}\\mid q\_\{t\}\)tracks structural anomalies rather than model\-specific tokens; the residual gap reflects that per\-model failure modes are partly model\-specific\.

## Appendix DBaselines and Implementation

We compare against three categories of baselines, each representing a distinct approach to behavioral model extraction\.Automata learning\(RPNI, EDSM, Alergia\): classic algorithms that infer DFAs or probabilistic automata from traces\. RPNI and EDSM require negative examples for effective merging; without them, they produce near\-complete prefix trees \(10310^\{3\}–10510^\{5\}states\)\. Alergia uses statistical compatibility testing but still overestimates state counts by 1–6×\\times\.Process mining\(Heuristic, Inductive, Alpha Miner via PM4Py\): discover Petri nets from event logs\. The miners achieve high fitness by accepting all orderings of observed activities, but this permissiveness yields low precision \(0\.23–0\.69\)\.Workflow extraction\(AWM\): extracts linear workflows from successful traces via longest common subsequence alignment\. AWM cannot represent cycles or branching and requires success labels, so it applies only to labeled datasets\.

### D\.1Unlabeled Dataset Results

Table 7:Compression resultson unlabeled datasets\. Same methodology as Table[1](https://arxiv.org/html/2608.23670#S4.T1)\.Three datasets lack success/failure labels suitable for failure prediction and are reported here for compression analysis only\. Who\_and\_When contains only failure traces \(no success examples\), making failure prediction undefined\. Mind2Web provides ground\-truth demonstrations without outcome labels\. GUI\-Odyssey has labels, but failure prediction is trivially separable \(AUROC 1\.000\): the terminal stateCOMPLETE/INCOMPLETEdirectly encodes the label\. Including these three datasets, compression ranges from 15×\\timesto 3,036×\\timesacross all twelve datasets\.

### D\.2Extended Baseline Results

Table[8](https://arxiv.org/html/2608.23670#A4.T8)presents the complete baseline comparison including all process mining and workflow extraction methods\.

Table 8:Full baseline comparison\(1/4\)\. Fit: test replay fitness\.†: RPNI timeout at 120s\.
Figure 6:FSM evolution for Who\_and\_When, SWE\-smith, and Mind2Web\. State count \(red\), 1−\-fitness \(blue dashed, reverse\-log\), CE \(gray, scaled\)\.
Small\-alphabet datasets\(\|𝒜\|=7\|\\mathcal\{A\}\|\{=\}7–99\)\. All three converge within 5–10% of training data and stabilize at 8–10 states\. Alergia matches our state count exactly; HMM confirms the same structure\. RPNI produces 476–11,631 states with degraded fitness \(≤\\leq0\.984\), demonstrating that modest trace corpora cause catastrophic overfitting without structural merging\.

Figure 7:FSM evolution for SWE\-agent, ATBench \(safety\), and OSWorld \(desktop GUI\)\. Lines: states \(red\), 1−\-fitness \(blue dashed\), CE \(gray\)\.
Table 9:Full baseline comparison\(2/4\)\.DatasetMethod\|Q\|\|Q\|/SizeFitNotesSWE\-agentOurs25 st0\.9992,380×\\timesRPNI59,510†0\.646†EDSM1 st1\.000Degen\.Alergia35 st0\.9991\.4×\\timesHMM25 st1\.000LatentHeur\. M21p,59t0\.999PNInd\. M44p,70t0\.999PNAlpha M12p,24t0\.050PNAWM371 wf0\.978LCSATBenchOurs15 st1\.00060×\\timesRPNI8990\.984EDSM1 st1\.000Degen\.Alergia15 st1\.0001\.0×\\timesHMM15 st1\.000LatentOSWorldOurs27 st0\.9971,416×\\timesRPNI38,2320\.706EDSM1 st1\.000Degen\.Alergia31 st0\.9991\.1×\\timesHMM27 st1\.000Latent

Coding agent\(\|𝒜\|=25\|\\mathcal\{A\}\|\{=\}25\)\. SWE\-agent shows the most gradual evolution: core search\-edit\-execute structure emerges byn=80n\{=\}80, but rare commands \(e\.g\.,deactivate,cd\) continue appearing untiln=1,200n\{=\}1\{,\}200\.

Table 10:Full baseline comparison\(3/4\)\.DatasetMethod\|Q\|\|Q\|/SizeFitNotesGUI\-OdysseyOurs7 st1\.0003,036×\\timesRPNI21,255†0\.929†EDSM1 st1\.000Degen\.Alergia24 st0\.9993\.4×\\timesHMM7 st1\.000LatentInd\. M–1\.000AWM1,266 wf0\.996LCSWebArenaOurs25 st1\.00015×\\timesRPNI382 st1\.00015×\\timeslargerEDSM1 st1\.000Degen\.Alergia149 st1\.0006\.0×\\timesHMM25 st1\.000LatentAgentNetOurs25 st1\.0002,500×\\timesRPNI62,495†0\.743†EDSM1 st1\.000Degen\.Alergia45 st1\.0001\.8×\\timesHMM25 st1\.000LatentHeur\. M35p,84t0\.987PNInd\. M18p,39t1\.000PNAlpha M174p,–t0\.297PNAWM–0\.975LCS

Figure 8:FSM evolution for GUI\-Odyssey, WebArena, and AgentNet\. Lines: states \(red\), 1−\-fitness \(blue dashed\), CE \(gray\)\.
Figure 9:FSM evolution for tau2\-bench \(airline, retail, telecom\)\. Multi\-model \(4 LLMs\)\. Lines: states \(red\), 1−\-fitness \(blue dashed\), CE \(gray\)\.
Table 11:Full baseline comparison\(4/4\)\.
Large\-scale datasets\(5,000–8,337 traces\)\. Compression ratios peak here: GUI\-Odyssey at 3,036×\\timesand AgentNet at 2,500×\\times\. RPNI completely collapses on AgentNet \(62,495 states, 0\.743 fitness\)\. WebArena is the exception: short traces \(∼\\sim8 steps\) keep the prefix tree small \(382 states\), so RPNI achieves perfect fitness, though still 15×\\timeslarger\. Alergia diverges most on GUI\-Odyssey \(3\.4×\\timesour state count\), where the statistical merge criterion becomes overly conservative with 7,735 traces\.

Multi\-model benchmarks\(4 LLMs per dataset\)\. A single FSM achieves 1\.000 fitness on all four models’ traces, confirming model\-invariant behavioral topology\. tau2\-bench telecom has the largest FSM \(43 states, 42 tool types\), reflecting the complex diagnostic workflow\. The evolution figures show that all three tau2\-bench datasets reach structural convergence despite pooling traces from GPT\-4\.1, Claude 3\.7, GPT\-4\.1\-mini, and o4\-mini\.

##### Alergia behavior\.

Alergia\([Carrasco and Oncina, 1994](https://arxiv.org/html/2608.23670#bib.bib27)\)learns a probabilistic DFA \(PDFA\) from positive examples using a Hoeffding bound to decide state merges\. On smaller datasets \(≤\\leq500 traces\), Alergia produces state counts matching our method \(8–12 states\)\. On larger datasets, Alergia diverges: 35 states on SWE\-agent \(1\.4×\\timesours\) and 24 on GUI\-Odyssey \(3\.4×\\timesours\), because the statistical test becomes more conservative with more data, splitting states that share structure but differ in probability distributions\. Our structural merging is agnostic to transition frequencies, producing deterministic FSMs that are smaller and faster to construct\.

##### HMM behavior\.

HMM \(Baum\-Welch\([Rabiner, 1989](https://arxiv.org/html/2608.23670#bib.bib28)\)\) with the same number of hidden states as our FSM achieves comparable fitness on all twelve datasets\. However, HMM states are latent \(unlabeled\), making the model non\-interpretable: one cannot inspect which behavioral mode a state corresponds to or extract per\-state features for downstream analysis\. Our FSM states have explicit activity\-labeled transitions\.

##### EDSM behavior\.

EDSM\([Lang et al\., 1998](https://arxiv.org/html/2608.23670#bib.bib21)\)uses evidence\-driven scoring to rank candidate merges\. Without negative examples, the evidence score for every merge candidate is zero, so EDSM greedily merges all states into one\. The resulting 1\-state universal acceptor has perfect fitness \(it accepts everything\) but zero precision\. This validates that our approach, which also uses only positive examples, achieves meaningful structure \(7–43 states with high precision\) rather than collapsing\.

##### AWM behavior\.

AWM\([Wang et al\., 2025d](https://arxiv.org/html/2608.23670#bib.bib2)\)by default filters for successful traces only\. On Who\_and\_When \(all failures\) and Mind2Web \(no success labels\), we use AWM\-all which skips the success filter\. AWM extracts linear workflows via longest common subsequence alignment; it cannot represent cycles or branching\. Its coverage metric \(0\.887–1\.000\) is not directly comparable to replay fitness\.

Table 12:k\-Tails results\.\|Q\|\|Q\|: states\. Fit: test fitness\. TO: timeout \(300s\)\. Our method requires no hyperparameter\.
##### PM4Py precision\.

The “flower model” problem in process mining: miners that accept all possible orderings achieve high fitness but low precision\. Our precision analysis \(Table[18](https://arxiv.org/html/2608.23670#A5.T18)\) confirms this: PM4Py miners achieve precision of 0\.00–0\.80 across datasets, while our FSM achieves near\-zero random acceptance\.

##### k\-Tails behavior\.

k\-Tails\([Biermann and Feldman, 1972](https://arxiv.org/html/2608.23670#bib.bib46)\)merges states sharing identicalkk\-length futures\. Table[12](https://arxiv.org/html/2608.23670#A4.T12)reports results fork∈\{1,2,3\}k\\in\\\{1,2,3\\\}\. Atk=1k\{=\}1, k\-Tails produces 1\.4–10×\\timesmore states than our method with lower test fitness \(0\.54–1\.00 vs\.≥\\geq0\.997\)\. Atk≥2k\{\\geq\}2, state counts explode to hundreds or thousands, with timeouts on large datasets \(AgentNet, tau2\-bench telecom\)\. No value ofkksimultaneously matches our compression and fitness, illustrating why hyperparameter\-free structural merging is preferable\.

Figure 10:Per\-dataset test fitnessacross all methods including Alergia\. Our FSM achieves≥\\geq0\.997 fitness on all panels\. Process mining baselines \(Heur\., Ind\.\) achieve competitive fitness but with low precision \(Table[18](https://arxiv.org/html/2608.23670#A5.T18)\)\.

### D\.3Implementation Details

All experiments use a single fixed seed for train/test splitting via seeded Fisher\-Yates shuffle\. The 80/20 split is applied consistently across all datasets and baselines\.

##### RPNI\.

TypeScript implementation with a 120\-second timeout for the merge phase\. Without negative examples, RPNI cannot safely merge states, resulting in near\-complete prefix trees\. The timeout is necessary for SWE\-agent \(59,510 states\), GUI\-Odyssey \(21,255 states\), and SWE\-smith \(11,631 states\)\.

##### EDSM\.

AALpy\([Muškardin et al\., 2022](https://arxiv.org/html/2608.23670#bib.bib22)\)version 1\.3\.4\. Without negative examples, evidence\-driven scoring produces no merge candidates, collapsing to a 1\-state universal acceptor\.

##### Alergia\.

AALpy implementation with Markov Chain automaton type andε=0\.005\\varepsilon=0\.005\(Hoeffding bound parameter\)\. Lowerε\\varepsilonproduces more merging \(fewer states\)\. Alergia learns from positive examples only using statistical compatibility testing\.

##### HMM\.

Pure NumPy implementation of Baum\-Welch EM\([Rabiner, 1989](https://arxiv.org/html/2608.23670#bib.bib28)\)with 50 iterations and scaled forward\-backward to prevent numerical underflow\. Number of hidden states set to match our FSM’s state count for fair comparison\. Replay fitness is computed via Viterbi decoding: a symbol is consumed if the decoded state has nonzero emission probability \(\>10−6\>10^\{\-6\}\)\. Effective transitions are counted as entries in the transition matrix with probability\>0\.01\>0\.01\.

##### PM4Py\.

Traces are converted to XES event log format\. We run Alpha Miner, Inductive Miner, and Heuristic Miner with default parameters\. Fitness and precision are computed via PM4Py’s conformance checking\.

##### AWM\.

We re\-implement workflow extraction from[Wang et al\. \(2025d\)](https://arxiv.org/html/2608.23670#bib.bib2)\. Coverage is measured via longest common subsequence alignment\.

##### Failure prediction\.

Feature selection uses L1\-regularized logistic regression \(C=0\.1C=0\.1\) on the training set to select features with non\-zero weights\. Final models use class\-weighted loss \(inverse frequency\)\. Cross\-validation uses stratified 5\-fold with 10 repetitions, evaluated on training data only \(no test data in CV folds\)\.

##### Runtime\.

FSM construction completes in<<1 second for all datasets\. RPNI requires up to 120 seconds \(timeout\)\. PM4Py baselines complete in 5–30 seconds\.

### D\.4Runtime Details

Construction time scales linearly with corpus size \(Table[13](https://arxiv.org/html/2608.23670#A4.T13)\)\. RPNI’s quadratic merge loop \(O⁡\(n2\)O\(n^\{2\}\)state pairs\) causes timeouts at 120 s on most datasets \(only Mind2Web completes within the limit\): on SWE\-agent, RPNI produces 59,510 states vs\. our 25\. Per\-trace replay is nearly instantaneous \(<<0\.015 ms\), which makes FSM\-based monitoring practical for real\-time agent systems \(Figure[11](https://arxiv.org/html/2608.23670#A4.F11)\)\.

Table 13:Runtime comparison\.Build: FSM construction\. Replay/tr: per\-trace replay latency\.
Figure 11:Runtime comparison\.Left: FSM construction time \(1–110 ms\) vs\. RPNI \(7,000–36,000 ms\) with speedup ratios annotated\. Right: per\-trace replay latency \(0\.003–0\.015 ms\), enabling real\-time monitoring\.
### D\.5Case Study: FSM Visualizations

We visualize FSMs for representative datasets to show the behavioral structure our method recovers\.

#### D\.5\.1Customer Service Agent \(tau2\-bench airline\)

Figure[5](https://arxiv.org/html/2608.23670#A1.F5)illustrates the tau2\-bench airline FSM at role\-level granularity \(6 states,\|𝒜\|=5\|\\mathcal\{A\}\|\{=\}5\)\. The full tool\-level FSM \(18 states,\|𝒜\|=17\|\\mathcal\{A\}\|\{=\}17, Table[1](https://arxiv.org/html/2608.23670#S4.T1)\) decomposes further into per\-tool states\. At role level, the FSM reveals two distinct behavioral loops:

1. 1\.Tool\-call loop\(assistant:tool\_call↔\\leftrightarrowtool:text\): The agent queries customer databases \(get\_reservation, search\_flights\) and receives structured responses\. This loop executes 2–8 times per trace\.
2. 2\.Conversation loop\(assistant:text→\\touser:text\): The agent communicates results to the user and receives follow\-up requests\. Failed traces show more conversation turns \(mean 4\.2 vs 2\.8 for successes\), which suggests the agent struggles to complete the task\.

The FSM makes these patterns structurally visible: the tool\-call loop appears as a tight 2\-state cycle; the conversation loop passes through the user state\. This decomposition enables per\-state analysis \(e\.g\., error rates in the tool state, message lengths in the assistant state\) that raw trace analysis obscures\.

#### D\.5\.2Coding Agent \(SWE\-smith\)

initsysusrbashtooleditsuba:txtt:strt:tcFigure 12:SWE\-smith FSM\(10 states, 17 transitions\)\. The core cycle isbash→\\totool→\\toedit→\\totool→\\tobash: agents execute commands, inspect results, make edits, and repeat\. Thesubmitstate is a terminal action reached after successful editing\.The SWE\-smith FSM \(Figure[12](https://arxiv.org/html/2608.23670#A4.F12)\) captures the coding agent’s workflow across 10 states\. Thebash→\\totool→\\tostr\_replace\_editor→\\totoolcycle dominates: the agent executes bash commands, inspects output, applies code edits, and verifies results\. Failed traces \(123/500\) show higher visit counts in the edit\-tool loop \(mean 8\.4 vs 5\.1 for successes\) and elevated error rates in thestr\_replace\_editorstate \(0\.31 vs 0\.12\), which suggests repeated failed edit attempts\.

#### D\.5\.3Coding Agent at Scale \(SWE\-agent\)

The SWE\-agent FSM has 25 states derived from 2,000 traces with 175 raw commands grouped into 7 categories\. The larger state space \(compared to SWE\-smith’s 10\) reflects the richer command vocabulary and longer traces \(mean 87 steps vs 23\)\. Key structural features include:

- •Asearch\-navigate cycle\(search↔\\leftrightarrownavigate\): agents find relevant files and navigate to specific locations\.
- •Anedit\-execute cycle\(edit↔\\leftrightarrowexecute\): agents modify code and run tests\.
- •Asubmit terminal: successful traces reach thesubmitstate, the strongest failure\-prediction feature\.

The 2,380×\\timescompression \(59,510 RPNI states→\\to25 FSM states\) demonstrates that even agents with complex command vocabularies exhibit a small number of distinct behavioral modes when commands are grouped by semantic function\.

## Appendix EFailure Analysis

### E\.1Structural Divergence of Success vs\. Failure

Separate FSMs for successful and failed traces reveal qualitative structural differences: on SWE\-agent, the success FSM uses only 9 of 25 states with 16 transitions \(focused path: search\-edit\-execute\-submit\), while the failure FSM spans all 25 states with 60 transitions \(chaotic exploration\)\. The transition Jaccard similarity is 0\.206, indicating largely disjoint behavioral structures; all 16 failure\-only states correspond to rare tool output parsing variants \(e\.g\.,user:tool:of,user:versioneer\) that successful traces never encounter: on tau2\-bench, both classes produce structurally identical FSMs \(discrimination gap=0=0\), which confirms that failure on constrained API\-calling tasks manifests purely in transition frequencies rather than novel states\. Failed traces are consistently longer across all datasets \(\+29 steps on SWE\-agent, \+18 on SWE\-smith\) but visit the same or fewer unique states, suggesting that failure shows up as cycling through familiar states rather than exploring new ones\.

These structural differences enable simple monitoring rules without ML models: on SWE\-agent, “cycle rate\>0\.885\>0\.885” achieves 95\.6% precision \(§[G\.3](https://arxiv.org/html/2608.23670#A7.SS3)\)\.

### E\.2Failure Prediction Numerical Results

Table 14:Failure prediction AUROC\(held\-out\)\. Main: full GBT pipeline\. FSM\-D ablation: training\-free LR, Len\+Ent vs\.\+\+per\-state KL \(Δ\\Delta= gain\)\. SWE\-smith synthetic; tau2\-bench aggregates 4 models\.
### E\.3Discriminative Quotient \(FSM\-D\)

The standard construction \(Theorem[3](https://arxiv.org/html/2608.23670#Thmtheorem3)\) merges trie states by their incoming activity \(the last\-activity right congruence\)\. We additionally explore a*discriminative*variant that conditions on the trace label: at training time, partition traces into success and failure subsets, and for each activityaacompute the outgoing transition distributionsP\+\(⋅∣a\)P^\{\+\}\(\\cdot\\mid a\)andP−\(⋅∣a\)P^\{\-\}\(\\cdot\\mid a\)\. The Kullback–Leibler divergenceKL\(P\+∥P−\)\\mathrm\{KL\}\(P^\{\+\}\\\|P^\{\-\}\)at stateaameasures how much the success distribution deviates from the failure distribution; a large value marks the activity as a behavioral choke point separating the two classes\.

The discriminative features alone \(no learned classifier beyond logistic regression on 10 inputs\) lift held\-out AUROC over a length\+entropy baseline by\+\+0\.06 to\+\+0\.15 on five of nine datasets, with the largest gains on datasets whose activities have the most discriminative outgoing distributions \(mean KL on tau2\-bench airline: 0\.014; ATBench: 0\.020; OSWorld: 0\.136 with 3 of 26 activities at KL\>\>0\.3\)\. Datasets with near\-uniform outgoing distributions across success and failure \(SWE\-agent: mean KL 0\.001; AgentNet: 0\.000\) show no FSM\-D gain, consistent with the discriminative signal being a property of the agent’s behavioral divergence rather than a universal lift\. The FSM\-D variant is a complement to the cross\-entropy anomaly features used in the main results: where outgoing distributions diverge, FSM\-D contributes a training\-free signal; where they do not, the main pipeline’s per\-state visit features and the trace cross\-entropy carry the predictive load\.

### E\.4Alergia Features under Matched Pipeline

Table 15:Failure prediction with Alergia FSMs under matched pipeline\.Identical features, classifier, and CV protocol; FSM source varies\. CV: 10×\\times5\-fold; Holdout: held\-out test AUROC\.We apply the identical feature extraction and classifier pipeline to Alergia\-extracted FSMs \(1\.0–6\.0×\\timesmore states than ours; §[4\.2](https://arxiv.org/html/2608.23670#S4.SS2)\), to check that the downstream gain is not just an artefact of state\-count differences\. With logistic regression on 34–175 per\-state features \(visit frequency, mean/max message length, error rate, temporal entropy\), 10×\\times5\-fold CV on training data, our FSM beats Alergia on 8 of 9 labeled datasets at the time of this comparison \(tying on AgentNet; Table[15](https://arxiv.org/html/2608.23670#A5.T15)\), with the largest margin \(\+\+0\.18\) on tau\-bench retail\. The additional Alergia states from statistical merging dilute per\-state observation counts rather than improving them, consistent with theO⁡\(1/nq\)O\(1/\\sqrt\{n\_\{q\}\}\)estimator bound \(Proposition[6](https://arxiv.org/html/2608.23670#Thmtheorem6)\)\.

The current main\-text headline numbers \(§[4\.3](https://arxiv.org/html/2608.23670#S4.SS3); up to 0\.941 holdout\) use a richer cross\-entropy anomaly feature set with a gradient\-boosted classifier; we expect the same direction of comparison \(ours\>\>Alergia\) under that pipeline because the bottleneck for Alergia features is per\-state observation count, not feature engineering\.

### E\.5Failure Prediction Feature Analysis

Table[16](https://arxiv.org/html/2608.23670#A5.T16)presents the top 10 features by absolute L1\-regularized logistic regression weight for each labeled dataset\.

Table 16:Top failure prediction featuresby L1\-regularized weight\. Positive weight = associated with success; negative = associated with failure\.##### Interpretable patterns\.

The features reveal consistent failure signals across datasets:

- •Not reaching terminal states\(SWE\-agent: submit state weight \+0\.29\): failed agents get stuck in intermediate loops\.
- •Elevated error rates\(SWE\-smith: editor error rate−\-0\.20\): failed agents encounter more errors per state\.
- •Verbose responses\(tau2\-bench airline: avgMsgLen:assistant\): longer responses correlate with task difficulty and failure\.
- •Temporal entropy\(SWE\-smith: lateHalfEntropy−\-0\.19\): chaotic second\-half behavior shows the agent struggling\.

Table 17:Failure prediction: neural models on sequence vs\. FSM features\. CV AUROC \(10×\\times5\-fold\)\. Bold: FSM\>\>Seq for same model\.These patterns are only visible through the FSM’s state decomposition: raw trace\-level features \(total message length, total error count\) do not capture which behavioral mode produced the errors\. Notably, the two most discriminative feature families \(per\-state error rates and temporal entropy splits\) appear in the top 5 across labeled datasets despite their different domains \(coding, API\-calling\), suggesting that FSM\-conditioned features transfer well across agent architectures\.

### E\.6Neural Baselines: Sequence vs\. FSM Features

We compare in Table[17](https://arxiv.org/html/2608.23670#A5.T17)neural models \(MLP, GRU\([Cho et al\., 2014](https://arxiv.org/html/2608.23670#bib.bib31)\), Transformer\([Vaswani et al\., 2017](https://arxiv.org/html/2608.23670#bib.bib32)\)\) trained on sequence features \(bag\-of\-activities \+ length \+ entropy\) vs\. FSM per\-state features\. All models use embed/hidden=64/128, class weighting, early stopping \(patience 10\), and the same 10×\\times5\-fold CV protocol\. Across this appendix, we retain SWE\-smith’s numbers even when they are the weakest per\-dataset value: the dataset is synthetic and below the sample threshold of Proposition[6](https://arxiv.org/html/2608.23670#Thmtheorem6), so its weaker AUROCs \(0\.62–0\.72 across sub\-ablations\) are both expected and consistent with the main\-text framing that FSM features generalize more strongly to real LLM\-deployment traces\.

FSM features improve every neural model on every dataset for MLP and GRU \(7/7\), and 6/7 for Transformer: the largest gains appear on tau2\-bench retail \(\+5\.3pp MLP, \+9\.1pp GRU\) and AgentNet \(\+4\.2pp MLP, \+4\.0pp GRU\), where the FSM’s per\-state decomposition localizes behavioral differences that aggregate statistics miss\. The Transformer loss on SWE\-agent \(−2\.8\-2\.8pp\) occurs where the small alphabet \(24 symbols\) limits the FSM’s decomposition advantage\. The improvement is consistent regardless of dataset size \(500–8,337 traces\): even on WebArena \(8,337 traces\), FSM features provide \+1\.3pp \(MLP\), \+1\.7pp \(GRU\), and \+0\.8pp \(Transformer\), demonstrating that the FSM captures structural information beyond what large\-sample statistics recover\.

### E\.7Precision Analysis

Table 18:Precision analysis\.Rand\./Perm\.: acceptance rate \(lower is better\)\.Our FSM rejects 100% of random traces and≥\\geq99\.9% of permuted traces on all eight labeled real\-trace datasets \(Table[18](https://arxiv.org/html/2608.23670#A5.T18)\)\. RPNI, despite its large state space, accepts 75% of permuted traces on WebArena and 0–11\.5% on tau2\-bench, since its prefix tree memorizes observed prefixes but does not constrain orderings and thus admits structurally invalid permutations that our FSM rejects\.

##### Adversarial trace rejection\.

Table 19:Adversarial trace rejection rate \(%,↑\\uparrow\)\. Five mutations per trace\.Beyond random and permuted traces, we test whether the FSM rejectsplausiblemutations that preserve local structure: single\-symbol substitution \(replace one activity with another symbol\), insertion, deletion, adjacent swap, and suffix shuffle \(shuffle the last 30% of the trace\)\. Table[19](https://arxiv.org/html/2608.23670#A5.T19)reports rejection rates \(fitness<1\.0<1\.0\) across five mutations per test trace\.

The FSM rejects 90–100% of insertions and adjacent swaps on all datasets, confirming that it captures sequential ordering constraints beyond symbol membership\. Substitution rejection \(77–100%\) shows that most single\-activity changes violate the learned transition structure\. Deletion is weakest on tau2\-bench datasets \(61–80%\) because shorter traces are more likely to remain valid prefixes\. These results demonstrate that the compact FSM imposes tight structural constraints: even single\-symbol perturbations are detected, because the transition function encodes which activity can follow which, not merely which activities are valid\. For example, on tau2\-bench airline, swappinguser:text↔\\leftrightarrowassistant:tool:get\_reservation\_detailsat position 3 is immediately rejected: after stateassistant:text, the only valid transition isuser:text\(the user must respond before the agent can call a tool\)\. On SWE\-agent, swappingnavigate:text↔\\leftrightarrowuser:textfails because self\-transitions back touser:textare not in the FSM’s transition table\. These rejections reflect genuine turn\-taking and tool\-invocation constraints that the FSM learns from data\.

### E\.8Process Mining Precision Details

Table[20](https://arxiv.org/html/2608.23670#A5.T20)reports per\-miner fitness and precision for the three PM4Py baselines across all twelve datasets, which span coding, web, GUI, desktop, and API domains\. Alpha Miner fails on all datasets \(fitness 0\.05–0\.63\) because it cannot handle noise or skip patterns\. The Heuristic Miner achieves 0\.95–1\.00 fitness but precision 0\.20–0\.80 \(mean 0\.45\); the Inductive Miner achieves perfect fitness on 8/10 datasets but even lower precision \(0\.10–0\.46, mean 0\.25\)\. The highest precision \(0\.80, tau2\-bench telecom\) occurs on the most constrained workflow: fitness alone is misleading here; only precision separates genuine structure from over\-general acceptors\.

Table 20:PM4Py miner results\.Fit: replay fitness\. Prec: precision from conformance checking\. p/t: Petri net places/transitions\.Figure 13:Random and permuted trace rejectionrates\. Our FSM achieves near\-100% rejection across most datasets, while RPNI shows poor permuted rejection on WebArena\.See Appendix[H\.4](https://arxiv.org/html/2608.23670#A8.SS4)for additional failure mode characterization including cascade analysis and early divergence detection\.

## Appendix FConvergence and Structural Properties

### F\.1Convergence Details

Table 21:Convergence and generalization\.Left: fraction at which fitness reaches 0\.99\. Right: train−\-test fitness gap at increasing fractions \(all within±\\pm0\.003\)\. Convergence behavior is similar across extraction levels \(Appendix[G\.2](https://arxiv.org/html/2608.23670#A7.SS2)\)\.Fitness converges rapidly as training traces are added: on all datasets, fitness reaches 0\.99 with 5–15% of training data \(Figures[1](https://arxiv.org/html/2608.23670#S1.F1),[14](https://arxiv.org/html/2608.23670#A6.F14)\)\. On SWE\-agent \(2,000 traces\), fitness reaches 0\.99 at 240 traces \(15%\), though the state space grows to 25 as rare command patterns appear\. The construction is deterministic \(Theorem[3](https://arxiv.org/html/2608.23670#Thmtheorem3)\), so a fixed corpus yields a unique FSM; across random splits our state counts stay within a few states of the full\-data value \(rare activities present in only some samples account for the residual\), whereas RPNI state counts vary by 2–10% \(Appendix[F\.2](https://arxiv.org/html/2608.23670#A6.SS2)\)\.

Table[21](https://arxiv.org/html/2608.23670#A6.T21)reports the training fraction at which fitness first reaches 0\.99, the final state count, and the generalization gap \(train−\-test fitness\) at increasing training fractions\.

Smaller datasets converge at 5% of training data; SWE\-agent requires 15% to capture rare commands\. All generalization gaps are within±\\pm0\.003, confirming zero overfitting\. Slightly negative gaps arise because training sets include rare transitions that reduce average fitness\.

![Refer to caption](https://arxiv.org/html/2608.23670v1/fig4_convergence.png)Figure 14:FSM convergence:test fitness \(right axis\) and state count \(left axis\) as training traces are added\. Fitness converges rapidly; the state space stabilizes later as rare patterns appear\.
### F\.2Stability and SCC Structure

The construction is deterministic and hyperparameter\-free \(Theorem[3](https://arxiv.org/html/2608.23670#Thmtheorem3)\): a fixed training corpus yields a unique FSM, so re\-extraction is exactly reproducible\. Across random train/test splits our FSM state counts stay within a few states of the full\-data value; the residual reflects rare activities \(e\.g\. SWE\-agent’s late\-appearing commands\) that occur in only some 80% samples, whereas RPNI state counts vary by 2–10% \(hundreds to thousands of states\)\. Structurally, every FSM decomposes into one large strongly\-connected component \(the behavioral core\) and a short prefix; the condensation DAG is shallow \(depth 2–4\), and init→\\tosetup→\\tocore traces the universal agent lifecycle\. SCC\-based features achieve AUROC 0\.60–0\.66: failures tend to become trapped in the core loop rather than progressing to terminal states\.

### F\.3Entropy Rate Analysis

We estimate the conditional entropyH⁡\(Xn∣Xn−1,…,Xn−k\)H\(X\_\{n\}\\mid X\_\{n\-1\},\\ldots,X\_\{n\-k\}\)of the activity sequence at increasing orderskkto characterize the sequential structure of agent traces\. Table[22](https://arxiv.org/html/2608.23670#A6.T22)shows the entropy rate convergence across all datasets\.

Table 22:Conditional entropy\(bits\) by context order\. The large drop from order 0→\\to1 and convergence by order 2–3 shows strong sequential regularity\.On all datasets, entropy drops 51–68% from order 0 to 1 \(Table[22](https://arxiv.org/html/2608.23670#A6.T22)\), and order\-2 vs\. order\-3 estimates differ by<<0\.02 bits on 2/3 datasets: the drop shows that agent behavior is predominantly determined by the immediately preceding action, which explains why compact FSMs achieve near\-perfect fitness: SWE\-agent shows the most residual higher\-order structure \(0\.80→\\to0\.79 bits\)\. Success vs\. failure entropy rates are nearly identical \(within 0\.03 bits\), indicating shared behavioral topology with differences in transition frequencies\.

### F\.4Feature Redundancy Analysis

We compute pairwise Pearson correlations among 14 structural features to identify redundancy\. We group features with\|r\|\>0\.8\|r\|\>0\.8into clusters, and a greedy selection retains the feature with highest individual AUROC from each cluster\.

Across labeled datasets, 14 features consistently collapse into 5–8 non\-redundant clusters: the largest cluster \(5–7 features\) contains \{traceLen, logLength, entropy, transitionDiversity, maxConsecRatio, recurrenceRate\}; these are all manifestations of trace length and its correlates\. Removing all redundant features and retaining only one representative per cluster yields combined AUROC of 0\.655 \(SWE\-smith\) and 0\.713 \(SWE\-agent\): on SWE\-agent, the non\-redundant subset achieves 90% of the full\-feature AUROC, so the failure prediction signal is genuine and concentrated in a small number of independent behavioral dimensions: cycle structure, state entropy, and terminal state reachability\.

## Appendix GPrediction and Robustness

Table 23:Early predictionAUROC \(holdout\) by trace completion fraction\. FSM vs\. raw\-statistic baseline\.### G\.1Early Prediction Details

Table[23](https://arxiv.org/html/2608.23670#A7.T23)presents early prediction AUROC at each trace completion fraction: FSM features from partial traces at 50% completion already achieve 92% of full\-trace AUROC on SWE\-agent \(0\.722 vs\. 0\.784, CV; holdout values in Table[23](https://arxiv.org/html/2608.23670#A7.T23): 0\.726 vs\. 0\.773\), which shows the behavioral signal emerging early in execution\. The FSM advantage over aggregate baselines grows with behavioral complexity: on SWE\-agent, FSM features outperform by \+0\.026 to \+0\.257 at all stages beyond 25%, while on SWE\-smith the simpler FSM offers no advantage\.

On SWE\-agent, FSM features outperform baselines by \+0\.026 to \+0\.257 at all stages\. On SWE\-smith, the simpler FSM offers no consistent advantage, suggesting that the FSM benefit scales with behavioral complexity\.

### G\.2Activity Granularity Robustness

Table 24:Activity granularityrobustness\.\|𝒜\|\|\\mathcal\{A\}\|: alphabet size\. Fit: test fitness\. AUROC: failure prediction \(entropy\-based\)\.The extraction functionϕ\\phiis a design choice\. We test four granularity levels:role\-only\(\|𝒜\|=2\|\\mathcal\{A\}\|\{=\}2–44, distinguishing only message roles\),role\-type\(role \+ content type\),role\-action\(role \+ action label\), andtool\-only\(tool function names\): fitness remains≥\\geq0\.999 across all levels and datasets, so the FSM structure is robust to extraction granularity: failure prediction AUROC varies by less than 0\.03 between the coarsest \(role\-only\) and finest \(tool\-only\) levels: even a 2–4 symbol alphabet preserves the predictive signal, because the behavioral topology \(cycle structure, branching patterns\) is invariant to label granularity\.

### G\.3Monitoring Rules

Table 25:Best monitoring rules by F1 score\. All rules use a single FSM\-derived feature with a fixed threshold\.Table[25](https://arxiv.org/html/2608.23670#A7.T25)presents the best single\-feature monitoring rules per dataset\. These rules require only FSM replay \(0\.006 ms/trace\) with no model training\. On SWE\-agent, the cycle\-rate rule achieves 95\.6% precision \(near\-zero false alarm rate\) at the cost of lower recall \(45\.1%\)\. SWE\-smith shows weaker monitoring rules, consistent with its lower failure prediction AUROC in the ML\-based approach \(Table[14](https://arxiv.org/html/2608.23670#A5.T14)\)\.

### G\.4Out\-of\-Distribution Detection

Replaying traces from one dataset through another’s FSM produces low fitness for structurally distinct pairs \(0\.00–0\.51 vs\.≥\\geq0\.997 in\-distribution\) and yields AUROC 1\.000\. tau2\-bench airline↔\\leftrightarrowretail is the exception: the two share a schema and replay near\-1\.0, so cross\-dataset fitness spans 0\.00–1\.000 overall\. This detection is not an artifact of alphabet mismatch: applying 10% random activity substitution within the same alphabet drops fitness to 0\.63–0\.82 across datasets and yields AUROC≥\\geq0\.917 for distinguishing clean from perturbed traces\. Within a single dataset, success and failure traces exhibit structural divergence: on SWE\-agent, the success\-only FSM has 9 states \(focused: search\-edit\-submit\) while the failure\-only FSM spans all 25 states \(chaotic exploration with rare tool variants\)\. The FSM captures behavioral topology, not vocabulary\.

### G\.5Probabilistic Baseline Comparison

Table[26](https://arxiv.org/html/2608.23670#A7.T26)compares FSM per\-state features against probabilistic baselines for failure prediction: Markov chain cross\-entropy \(CE\) against success/failure transition matrices, likelihood ratio \(LR\) scoring, and discriminative n\-gram frequency analysis\.

Table 26:Failure prediction: FSM features vs\. probabilistic baselines \(holdout AUROC\)\.FSM features dominate on SWE\-agent \(\+0\.19 over the best probabilistic baseline\), where the per\-state decomposition captures structural information that aggregate transition statistics miss\. On SWE\-smith, transition cross\-entropy is competitive \(0\.719 vs\. 0\.718\): the simpler FSM \(10 states\) offers less decomposition advantage\. Probabilistic models capture*how often*transitions occur but not*what happens*at each state \(message lengths, error rates, temporal patterns\)\. The FSM provides both: its deterministic structure supports per\-state feature extraction, while probabilistic models reduce each trace to a single scalar score\.

### G\.6ProbGuard Head\-to\-Head Comparison

We implement ProbGuard\([Wang et al\., 2025b](https://arxiv.org/html/2608.23670#bib.bib49)\)on the same activity sequences, labels, and 80/20 splits for a like\-for\-like comparison, reproducing its pipeline \(Algorithms 1–2\): symbolic\-state abstraction, DTMC learning with Laplace smoothing \(α=1\\alpha\{=\}1\), bounded reachabilityP≤θ​\[F≤k​𝑢𝑛𝑠𝑎𝑓𝑒\]P\_\{\\leq\\theta\}\[\\,F^\{\\leq k\}\\,\\mathit\{unsafe\}\\,\]by finite\-horizon Bellman iteration, and a per\-trace risk score equal to the maximum reachability along the trajectory\. Its published evaluation uses hand\-crafted predicates \(fork\_in\_microwave∧\\wedgemicrowave\_on\); no such predicates exist for general LLM agent traces, so we follow its “extensible domain\-specific abstraction” interface and take the activity itself as the symbolic state\. To avoid handicapping the baseline we grant it every configuration advantage: log\-odds ranking of unsafe states, sweeps overKunsafe∈\{1,3,5,10\}K\_\{\\text\{unsafe\}\}\\\!\\in\\\!\\\{1,3,5,10\\\}and horizonk∈\{3,5,10,20,50\}k\\\!\\in\\\!\\\{3,5,10,20,50\\\}, and a polarity flipmax⁡\(AUROC,1−AUROC\)\\max\(\\mathrm\{AUROC\},1\{\-\}\\mathrm\{AUROC\}\); we report the best of the resulting 20 configurations per dataset\.

Table 27:ProbGuard\([Wang et al\., 2025b](https://arxiv.org/html/2608.23670#bib.bib49)\)vs\. our FSM features for failure prediction\. ProbGuard column = best AUROC over 20 configurations \(Kunsafe×K\_\{\\text\{unsafe\}\}\\\!\\timeshorizon, polarity\-aware\); FSM column = holdout AUROC from Table[14](https://arxiv.org/html/2608.23670#A5.T14)\. Our FSM wins on every shared dataset by mean \+17\.6pp\.Two factors drive the gap: without ProbGuard’s hand\-crafted predicates the symbolic\-state abstraction collapses to per\-activity granularity, which leaves each state with too few visits for reliable reachability estimation; and our cross\-entropy anomaly features \(−log2⁡P^\+​\(at∣qt\)\-\\log\_\{2\}\\hat\{P\}^\{\+\}\(a\_\{t\}\\\!\\mid\\\!q\_\{t\}\)\) give a continuous per\-step risk score, whereas ProbGuard’s PCTL\-thresholded reachability is binary at deployment\. ProbGuard’s strength on its own benchmarks \(autonomous driving, embodied agents\) comes from those domain predicates; on general agent traces the FSM cross\-entropy approach generalises further\. The methods are complementary: a PCTL specification could be layered on our compact FSM \(Theorem[3](https://arxiv.org/html/2608.23670#Thmtheorem3)\) to combine its structural constraints with formal reachability checking\.

### G\.7Perturbation Robustness

Table[28](https://arxiv.org/html/2608.23670#A7.T28)presents fitness degradation under four perturbation types at 10% intensity across all datasets\. Substitution \(replacing activities with random same\-alphabet symbols\) causes the largest fitness drop, which confirms that the FSM captures transition topology rather than vocabulary\.

Table 28:Fitness under 10% perturbation intensity\. Baseline fitness shown for reference\.Substitution is the strongest perturbation because it introduces invalid transitions \(mean fitness drop 0\.18\)\. Insertion is intermediate \(mean drop 0\.10\): the extra symbol breaks the current transition but the trace may recover\. Swap is weakest \(mean drop 0\.05\): reordering adjacent activities often preserves valid transitions if both orderings exist in the FSM\. Truncation has no effect because the FSM accepts all prefixes by construction\.

### G\.8FSM as Context

AWM context52\.9% top\-1 \#\# Extracted Workflow Patterns \- \[freq=208\] get\_order\_details →\\rightarrowtool:text→\\rightarrowtool:text →\\rightarrowassistant:text→\\rightarrowuser:text →\\rightarrow… \- \[freq=205\] get\_order\_details →\\rightarrowtool:text→\\rightarrow… \(10 patterns, 17\-\-20 steps\) Agent prefix: …→\\rightarrowget\_order\_details\. Next action? LLM:assistant:text\(actual:tool:text\)

FSM context \(minimal\)65\.1% top\-1 After the most recent action "get\_order\_details", past traces show these next actions: \- tool:text: 100\.0% Common multi\-step continuations: \- tool:text→\\rightarrowget\_order\_details \(1098x\) \- tool:text→\\rightarrowassistant:text \(926x\) \(top\-15 shown\) Agent prefix: …→\\rightarrowget\_order\_details\. Next action? LLM:tool:text\(actual:tool:text\)

Figure 15:Why minimal context wins\.Prompt excerpts at FSM stateget\_order\_details\(tau2\-bench retail\)\. AWM \(52\.9%\): linear success workflows\. ASG\-minimal \(65\.1%\): per\-state next\-action probabilities \+ top\-15 continuations\.Table 29:Statistical next\-step prediction: top\-1 accuracy \(%,↑\\uparrow\) on full validation sets\.Table[29](https://arxiv.org/html/2608.23670#A7.T29)evaluates the FSM as context for next\-step prediction on the eight datasets where AWM has been re\-implemented end\-to\-end against the same per\-step predictor, comparing against AWM\([Wang et al\., 2025d](https://arxiv.org/html/2608.23670#bib.bib2)\)\. Transition counts are computed on training data; validation traces are replayed through the FSM for per\-step predictions\.

The FSM achieves higher top\-1 accuracy than AWM on every listed dataset, with the gap ranging from \+0\.1pp to \+65\.5pp\. AWM coverage varies from 0% \(Mind2Web has no success labels\) to 92\.9%, explaining its performance variation\. The LLM\-judged variant of this comparison \(Table[4](https://arxiv.org/html/2608.23670#S4.T4)\) additionally covers ATBench\.

### G\.9Next\-Step Prediction

Order\-1 FSM conditioning \(Our FSM\) captures 83–99% of the total CE improvement from Uniform to the best method on each dataset, reflecting the strong sequential regularity of agent traces\. Higher\-order context via PPM smoothing or neural models captures the remaining second\- and higher\-order dependencies within each FSM state\. The FSM state benefit \(\+0\.019 bits avg, FSM\-LR vs\. NGram\-LR atK=7K\{=\}7\) is largest on Mind2Web \(\+0\.041\) and Who\_and\_When \(\+0\.028\), where the FSM groups behaviorally distinct states\. On SWE\-agent \(\+0\.001\), the FSM state is nearly redundant with the last activity due to simple sequential structure\.

RPNI produces worse\-than\-Unigram predictions on most datasets\. With 382–63,897 states, each state is visited by too few traces for reliable probability estimation\. This validates the compression advantage: our 10–43 state FSMs aggregate observations for well\-estimated transition probabilities\. MLPs diverge on larger alphabets \(\|𝒜\|≥9\|\\mathcal\{A\}\|\\geq 9; CE\>\>10 bits\) from gradient instability, while RNNs without BPTT fail uniformly \(CE\>\>1\.4\)\. Echo state networks avoid both issues through random frozen reservoirs with trained output layers, achieving competitive performance with minimal hyperparameter sensitivity\.

##### FSM state ablation\.

Holding the smoothing method fixed \(absolute discounting at depth 5\), FSM state conditioning provides \+0\.155 bits improvement on average over raw context alone \(FSM\-AD: 0\.580 vs\. Pure\-AD: 0\.735\)\. The advantage is largest on Mind2Web \(\+0\.36 bits, 30%\) where the FSM groups heterogeneous web actions, and smallest on SWE\-agent \(\+0\.016 bits, 2%\) where the simple sequential structure makes FSM state nearly redundant with the last activity\. This gap is larger than the \+0\.019 bits from FSM\-LR vs\. NGram\-LR \(Table[2](https://arxiv.org/html/2608.23670#S4.T2)\), because logistic regression partially learns FSM\-like state from raw context\.

## Appendix HAdditional Analysis

### H\.1Cross\-Dataset Transfer

Table 30:Cross\-datasettransfer: FSM vs\. raw feature AUROC\. Bold: FSM advantage\>\>3pp\.Table[30](https://arxiv.org/html/2608.23670#A8.T30)presents the full cross\-dataset transfer matrix: FSM features against raw trace statistics\. FSM features achieve higher transfer AUROC than raw features on most cross\-dataset pairs, with the largest improvements on transfers involving SWE\-agent\. The pattern indicates that the per\-state behavioral signal captures failure structure that generalizes beyond the training domain, whereas raw trace statistics overfit to dataset\-specific surface features\. Leave\-one\-out results \(train on 1 dataset, test on the other\): SWE\-smith 0\.682, SWE\-agent 0\.765\. The drop from in\-domain is modest on SWE\-agent \(0\.780→\\to0\.765\), a sign that FSM behavioral features capture domain\-invariant failure signatures\.

### H\.2Sample Efficiency and Learning Curves

Table 31:Learning curves: failure prediction AUROC at increasing training fractions\. Bold: first fraction reaching 95% of final AUROC\.Table[31](https://arxiv.org/html/2608.23670#A8.T31)presents failure prediction AUROC as a function of training set size: on 3 of 4 datasets, 10% of training data suffices to reach 95% of final performance\. The rapid convergence reflects the low dimensionality of FSM feature space \(31–49 features\) relative to the behavioral complexity captured\.

SWE\-agent shows the most stable learning curve, consistent with its larger sample size \(1,600 training traces\)\. In practice, FSM\-based failure prediction can be deployed with as few as 16–160 labeled traces, which makes it viable for new agent systems where labeled data is scarce\.

### H\.3Length vs\. Structure Ablation

On SWE\-agent, structural features alone reach AUROC0\.790, length alone only 0\.659, and the full model 0\.790: adding length to the structural features changes full\-model AUROC by<<0\.001, confirming that the predictive signal is structural rather than a length proxy\.

### H\.4Failure Mode Characterization

On SWE\-agent, the two failure modes are structurally distinct: “stuck in edit loop” traces have cycle rate 0\.924 and terminate inedit:text\(50%\), while “gave up early” traces have lower cycle rate \(0\.755\) and reachsubmit:text\(98\.7%\) but still fail\. The discriminating feature with highest F\-ratio is:visit:user:text\(7\.41 on SWE\-agent\)\.

#### H\.4\.1Failure Cascade Analysis

We analyze whether failures develop gradually \(progressive fitness degradation\) or suddenly \(abrupt state change\)\. Across all datasets, 97% of SWE\-agent failures are sudden \(1,292 of 1,329\), with no gradual degradation pattern\. This is consistent across datasets: SWE\-smith 100% sudden\. Failure monitoring should therefore focus on detecting specific state patterns \(e\.g\., cycle rate threshold\) rather than tracking gradual performance decline\.

#### H\.4\.2Failure Progression

Failure signatures emerge early in execution: on SWE\-agent, the first divergence between success and failure state distributions occurs at 8\.7% of trace length \(position 0\.087\)\. Divergence occurs at 15\.4% on SWE\-smith\.tool:text→\\toassistant:textis the highest\-lift failure transition on SWE\-smith \(fail rate 0\.90, lift 3\.66×\\timesover base rate\)\. Recovery from failure\-indicative states is possible: SWE\-agent has 8 recovery states where traces can return to successful trajectories, with 95\.7% recovery rate within 2 steps\.

### H\.5Counterfactual Path Analysis

We identify FSM decision points where success and failure paths diverge, measured by Jensen\-Shannon divergence of outgoing transition distributions\.

Table 32:Counterfactual path analysis\. Decision points: states with JSD\>0\.001\>0\.001between success/failure transitions\.On SWE\-agent, failures show 5\.4×\\timesmore unique paths than successes \(1,496 vs\. 275\), with only 41 shared paths\. Theuser:textstate is the primary decision point \(JSD 0\.014\): at this state, successful traces are more likely to transition tosubmit\(25\.3% success rate\) while failed traces loop back toedit\(9\.6% success rate\)\. On SWE\-smith, thetool:tool\_callstate shows the highest divergence \(JSD 0\.021\)\. Early divergence is common: 65\.3% of SWE\-agent traces diverge within the first 10% of execution\.

### H\.6Compression Theory

![Refer to caption](https://arxiv.org/html/2608.23670v1/fig_overview.png)Figure 16:\(a\) State compression across labeled datasets: our FSM \(10–43 states\) vs\. Alergia \(10–149\) and RPNI \(382–63,897\), with compression ratios annotated\. \(b\) Cross\-dataset fitness matrix: replaying traces from one dataset through another’s FSM\. Diagonal entries \(in\-distribution\) approach 1\.0; off\-diagonal entries \(OOD\) drop to near\-zero for structurally distinct pairs \(AUROC 1\.000\), except schema\-sharing tau2\-bench airline↔\\leftrightarrowretail \(near\-1\.0\)\.Table[33](https://arxiv.org/html/2608.23670#A8.T33)presents information\-theoretic analysis of FSM compression across all datasets\. FSM bits count the encoded transition table; raw bits countlog2⁡\|𝒜\|\\log\_\{2\}\|\\mathcal\{A\}\|per activity summed over all traces, so the MDL ratio measures how much of the raw description the FSM eliminates\.

Table 33:Information\-theoretic compression analysis\. MDL: minimum description length ratio \(FSM bits / raw trace bits\): gzip: compression ratio of raw sequences\.The FSM achieves MDL ratios of 0\.001–0\.008 across all datasets: the FSM description requires 0\.1–0\.8% of the bits needed to store raw traces\. That ratio is 5–46×\\timesbetter than gzip compression \(ratios 0\.012–0\.026\), confirming that the FSM captures genuine behavioral regularity beyond statistical redundancy: all FSMs are deterministic with\|Q\|=\|𝒜\|\+1\|Q\|=\|\\mathcal\{A\}\|\+1\(verified programmatically\) and 100% alphabet utilization on 3/4 datasets shown\. SWE\-agent has alphabet utilization 1\.13 \(3 states have transitions for symbols not in the core alphabet, reflecting rare command variants\)\. Conditional entropy analysis: unigram entropy ranges 1\.69–2\.16 bits; conditioning on the previous symbol \(bigram\) reduces entropy to 0\.63–1\.06 bits \(51–68% reduction\), confirming strong sequential regularity in agent traces\.

### H\.7Path Diversity and Recurrence Analysis

Table[34](https://arxiv.org/html/2608.23670#A8.T34)quantifies path diversity and recurrence quantification analysis \(RQA\) metrics across datasets: RQA treats activity sequences as symbolic time series\.

Table 34:Path diversity and RQAmetrics\. Singleton%: paths observed once\. Top\-5%: coverage of 5 most common paths\. RR/DET/diagEnt: recurrence rate, determinism, diagonal entropy \(AUROC for failure prediction\)\. Who&When and Mind2Web lack success/failure labels \(–\)\.82% of traces follow unique FSM paths on coding agent datasets, yet the FSM compresses all into 6–25 states with≥\\geq0\.999 fitness by capturing*transition topology*rather than memorizing paths\. API\-driven domains show opposite extremes: tau2\-bench telecom has only 5 unique paths across 1,824 traces \(highly constrained workflows\), while tau2\-bench retail has 1,521 unique paths \(73\.2% singletons\)\. RQA metrics achieve 0\.60–0\.70 AUROC on coding agents, with diagonal entropy strongest on SWE\-agent \(0\.704\), but are weaker on web/GUI benchmarks \(0\.31–0\.47 on GUI\-Odyssey and AgentNet\) where trace structures are less recurrent\.

### H\.8State Importance Analysis

Table 35:State importance: fitness drop upon state removal\. Top 3 most critical states per dataset\.We measure state importance by fitness drop when each state is removed from the FSM \(Table[35](https://arxiv.org/html/2608.23670#A8.T35)\): state importance is not proportional to visit frequency\. On SWE\-smith,system:textanduser:texteach receive only 1\.9% of visits but removing either causes complete fitness collapse \(1\.000 and 0\.979 drop\)\. Conversely,tool:textreceives 47\.2% of visits but its removal drops fitness by only 0\.937, because its behavioral role can be partially compensated by other states\. On SWE\-agent,user:textis the single critical bottleneck \(49\.9% visits, 0\.999 fitness drop\), reflecting its role as the central hub connecting all behavioral modes\.

### H\.9Loop and Graph Motif Analysis

Tables[36](https://arxiv.org/html/2608.23670#A8.T36)and[36](https://arxiv.org/html/2608.23670#A8.T36)analyze loop patterns \(backedge counts\) and graph motifs in the FSM\.

Table 36:Loop analysis and graph motifs\.Left: loop counts \(backedges\) per outcome and AUROC\. Right: structural motif counts\. Bidir: bidirectional edge pairs\. Hub degree: maximum out\-degree\. Who&When and Mind2Web lack success/failure labels \(–\)\.On coding agents, failed traces contain 1\.4–2\.2×\\timesmore loops, strongest on SWE\-agent \(2\.17×\\times, 54\.8 vs\. 25\.3 backedges, AUROC 0\.665\)\. Interestingly, on web/GUI benchmarks the pattern reverses: successful WebArena traces loop*more*\(9\.9 vs\. 6\.4, ratio 0\.65×\\times\), which reflects productive exploration in complex navigation tasks\. tau2\-bench airline shows the strongest signal among API agents \(1\.26×\\times, AUROC 0\.664\)\. Graph motif analysis reveals that tau2\-bench airline/retail have the densest bidirectional structure \(14–15 pairs\), while triangles appear only in Who&When \(6, multi\-agent delegation\), GUI\-Odyssey \(6, cross\-app navigation\), and tau2\-bench telecom \(2\)\.

### H\.10Critical Transitions and Error Localization

Table[37](https://arxiv.org/html/2608.23670#A8.T37)identifies structural bottlenecks \(transition criticality = frequency×\\timessuccess differential\) and per\-state error rate differentials between success and failure traces\.

Table 37:Critical transitions \(top: highest criticality scores\) and error localization \(bottom: per\-state error rate differential, failure−\-success\)\.The highest\-criticality transitions form tight cycles:str\_replace\_editor↔\\leftrightarrowtool:texton SWE\-smith \(1\.048\) anduser:text↔\\leftrightarrowedit:texton SWE\-agent \(0\.657\)\. Errors localize to specific states: on SWE\-smith,assistant:texthas zero errors in successes but 22\.2% in failures \(\+0\.222 differential\)\. The first significant divergence between success and failure distributions occurs at theedit:textvs\.search:textbranch on SWE\-agent \(position 2\)\.

### H\.11Temporal Dynamics

We analyze three\-phase \(early/mid/late\) behavioral dynamics to see how agent behavior evolves during execution\.

Table 38:Temporal dynamics:entropy by execution phase and entropy drift \(early−\-late\)\. Who&When and Mind2Web lack success/failure labels \(–\)\.Most datasets show negative entropy drift: agents narrow their behavioral repertoire over time\. The effect is strongest on Mind2Web \(−\-1\.03\) and weakest on GUI\-Odyssey \(−\-0\.04\)\. Two datasets show*positive*drift: WebArena \(\+\+0\.19\) and AgentNet \(\+\+0\.18\), where agents diversify behavior in later phases, possibly reflecting recovery or exploration after initial failures\.

### H\.12Anomaly Detection and Suffix Monitoring

We evaluate two unsupervised monitoring approaches: \(1\) a multi\-component anomaly score combining rejection rate, state occupancy deviation, terminal state anomaly, cycle excess, and length deviation; and \(2\) suffix\-based monitoring using only the lastkkFSM transitions \(Table[39](https://arxiv.org/html/2608.23670#A8.T39)\)\.

The composite anomaly score achieves 0\.653–0\.747 AUROC, strongest on SWE\-agent \(0\.747, P@10 = 1\.00\)\.

Terminal anomaly is the dominant component on SWE\-agent \(0\.711\)\. Suffix monitoring withk=10k\{=\}10transitions achieves comparable AUROC to the full predictor \(0\.825 on SWE\-agent\) and enables real\-time deployment with a fixed\-size sliding window\. Evenk=3k\{=\}3yields 0\.746 AUROC on SWE\-agent\.

Table 39:Unsupervised monitoring\.Left: anomaly detection components and composite AUROC\. Right: suffix monitoring AUROC at window sizekk\.
### H\.13Agent Integration: Runtime Monitor

Figure[4](https://arxiv.org/html/2608.23670#S4.F4)\(body\) shows the cycle\-rate trajectory contrast between a failing and a successful SWE\-agent run\. The failing trace enters a cycle betweenuserandeditstates; cycle\-rate exceeds 0\.778 at step 11 \(31% of this specific trace; mean across all interventions: 32%\), triggering early termination\. The successful trace visits 7 distinct states and reachessubmit; its cycle\-rate peaks at 0\.636 and never crosses the threshold\. MonitorF1=0\.904F\_\{1\}\\\!=\\\!0\.904on SWE\-agent without any trained model\.

We simulate deploying the FSM as a runtime monitor that replays agent actions step\-by\-step and triggers intervention when learned rules fire\. Rules are automatically derived from training traces: cycle\-rate thresholds \(percentile\-based\) and minimum unique\-state counts, with a warm\-up period \(10% of mean trace length\) before activation\. A “stuck” detector also fires when the agent remains in the same state for 5\+ consecutive steps\.

Table 40:Runtime monitor results\. Latency: mean % of trace at intervention\. Saved: mean % of remaining computation avoided\.The monitor is reliable on FSMs with high structural diversity \(\|Q\|≥6\|Q\|\\geq 6active states with distinct failure patterns\): SWE\-agent \(F1=0\.904F\_\{1\}\\\!=\\\!0\.904, lift 1\.02×\\times\) and tau2\-bench airline \(F1=0\.776F\_\{1\}\\\!=\\\!0\.776, lift 1\.27×\\times\)\. On the smaller\-alphabet datasets, the rule under\-discriminates: tau2\-bench retail and SWE\-smith FSMs are too coarse for cycle\-rate to separate failure modes, and the monitor over\-triggers\. The two\-datasetF1F\_\{1\}≥\\geq0\.776 result establishes a working operating regime; deploying on small\-alphabet domains requires per\-dataset rule tuning\.

##### Operating point analysis\.

Table[41](https://arxiv.org/html/2608.23670#A8.T41)shows precision–recall trade\-offs at different cycle\-rate thresholds on SWE\-agent\.

Table 41:Multi\-threshold analysis \(cycle\-rate only\) on SWE\-agent\. Higher thresholds yield higher precision at the cost of recall\.At the high\-precision operating point \(threshold 0\.957\), the monitor achieves 100% precision \(zero false alarms\) while catching 11\.3% of failures\. This is suitable for automated intervention \(e\.g\., resetting the agent\) where false positives are costly\. At the balanced operating point \(threshold 0\.750\), the monitor catches 85\.2% of failures with 86\.4% precision, suitable for alerting a human operator\. The entire monitoring pipeline requires only FSM replay at 0\.006 ms per step with no ML model training\.

### H\.14Sequence\-Level vs\. FSM Feature Comparison

Table 42:Failure prediction: sequence\-level features \(bag, bigram, stats, all\-seq\) vs\. FSM per\-state features, L1\-regularized LR\.dd: feature dimensionality\. FSM wins on every dataset\.Table[42](https://arxiv.org/html/2608.23670#A8.T42)compares sequence\-level feature representations against FSM per\-state features for failure prediction, all using the same L1\-regularized LR \(C=0\.1C\{=\}0\.1, class\-weighted\)\. Sequence features use only the activity symbols \(no message content\): bag \(frequency histogram,\|𝒜\|\|\\mathcal\{A\}\|feat\.\), bigram \(transition matrix,\|𝒜\|2\|\\mathcal\{A\}\|^\{2\}feat\.\), stats \(8 sequence statistics\), and all\-seq \(all three concatenated\)\. MLP uses a 2\-layer network \(64, 32 units\) with early stopping on all sequence features\.

FSM per\-state features outperform all sequence\-level representations on all datasets in both CV and holdout AUROC: the advantage is largest on SWE\-agent \(\+0\.088 CV, \+0\.020 holdout\), where per\-state features capture differences that flat counts cannot localize\. On SWE\-smith, the gap is minimal \(\+0\.002 CV\) because the 10\-state FSM with 9\-symbol alphabet provides limited decomposition advantage\. The MLP underperforms LR on all datasets, so the ceiling is data\-limited \(400–1,600 traces\) rather than model\-limited\.