AI news and explainers at 7 AM weekdays, plus a Sunday weekly at 8Get it in your inbox›
Automata from Agent Traces: Failure and Next-Step Prediction
arXiv:2608.236702026-08-26
Researchers compress massive LLM-agent execution logs into one small finite-state machine that predicts both the next action and eventual failure
LLM-based agents leave behind long, messy execution traces that are hard for humans to audit for safety. The authors compress an entire corpus of traces from 12 public datasets into a single compact finite-state machine (FSM) with only 7-43 states, and show it serves both next-step prediction and failure prediction. The FSM is built in milliseconds and replays held-out traces with at least 0.997 fitness.
METAL LAB explanatory visual
From traces to one FSM to two predictions
Evidence statusMeasured results reported
Collect tracesConvert tool calls, action tags, and messages from twelve public agent datasets into activity symbols
Merge into a compact FSMInsert all traces into a prefix tree, then merge states sharing the same last activity to get a deterministic FSM with 7-43 states
Next-step predictionUsing the current FSM state as context beats AWM's top-1 accuracy on every ground-truth-matched dataset
Failure predictionPer-state visit frequency, error rate, and related features reach held-out AUROC up to 0.94
Runtime monitoringWatching just 32% of a trace lets the monitor stop likely failures early, saving 68% of remaining compute on SWE-agent
An explanatory diagram made by METAL LAB, not a figure supplied by the paper's authors.
What they did
Each agent message (tool call, action tag, or command) is mapped to a symbol; all traces are merged into a prefix tree and then collapsed by grouping states that share the same last incoming activity, producing a deterministic finite-state machine with no learning hyperparameters.
Across all twelve datasets the resulting FSMs stayed compact at 7-43 states, replayed held-out traces with at least 0.997 fitness, and were constructed in milliseconds using a linear-time algorithm.
Using the FSM's current state as context for next-action prediction beat Agent Workflow Memory (AWM), a prior method that extracts linear workflows only from successful traces, on every dataset where ground truth could be matched.
For failure prediction, features computed per FSM state (visit frequency, message length, error rate, etc.) reached held-out AUROC (a 0.5-to-1.0 discrimination score, 0.5 being random guessing) up to 0.94, and an online monitor watching only 32% of a trace could flag likely failures early enough to stop them before completion.
The behavioral structure captured by the FSM appeared to depend more on the deployment system (tools, harness) than on which LLM generated the traces: a single FSM built from four different LLMs' traces still fit each model's traces almost perfectly.
Figure 1: FSM evolution on SWE-agent. State count |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 at 240 traces, 15% of training); construction completes in milliseconds.
Table 1: FSM extraction results on eight labeled real-trace datasets (excluding SWE-smith synthetic). |Q|: states. Fit: test replay fitness. †RPNI timeout at 120 s. Full baselines in Table 8; SWE-smith and the unlabeled datasets appear in Appendix D.1.
Ours
RPNI
Alergia
Dataset
|Q|
Fit
|Q|
Fit
|Q|
Fit
Compr.
SWE-agent
25
0.999
59,510†
0.646
35
0.999
2,380×
WebArena
25
1.000
382
1.000
149
1.000
15×
AgentNet
25
1.000
62,495†
0.742
45
1.000
2,500×
tau2-bench (air)
18
1.000
6,506†
0.844
23
0.999
361×
tau2-bench (ret)
19
1.000
14,249†
0.837
25
1.000
750×
tau2-bench (tel)
43
1.000
63,897†
0.491
75
0.999
1,486×
ATBench
15
1.000
899†
0.984
15
1.000
60×
OSWorld
27
0.997
38,232†
0.706
31
0.999
1,416×
Figure 2: Next-step prediction cross-entropy (bits, ↓). (a) Per-dataset: FSM-conditioned methods (red) achieve 3–5× lower 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.
Table 2: Next-step prediction cross-entropy (bits, ↓). 5×5-fold CV across all datasets. Best per dataset in bold. The “FSM” columns use the FSM-state context format (ASG-minimal) selected on validation in Section 4.3.
Method
SWE-sm
SWE-ag
W&W
M2W
ATB
Avg
Uniform
3.170
4.585
3.000
2.807
3.807
3.474
Unigram
2.461
2.850
2.229
1.856
2.799
2.439
RPNI
3.851
4.284
2.855
3.549
2.448
3.397
Our FSM
0.638
1.071
0.963
0.756
1.243
0.934
FSM-PPM-AD
0.463
0.741
0.624
0.782
1.309
0.784
Ens(D0/3/5/7)
0.465
0.700
0.621
0.736
1.262
0.757
NGram-LR-K7
0.464
0.687
0.610
0.796
1.181
0.748
ESN-H64
0.476
0.691
0.580
0.746
1.184
0.735
FSM-LR-K7
0.460
0.686
0.582
0.755
1.162
0.729
FSM-ESN-H64
0.474
0.700
0.546
0.753
1.185
0.732
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.
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.
Table 4: FSM vs. AWM as context for an LLM next-action predictor (gpt-4.1-mini, top-1 %). 6/8 gaps statsig at p<10−8. †tau2-retail used for FSM-context-format selection (§4.2); other 7 held out.
Dataset
N
AWM
FSM
Δ
WebArena
4,800
65.5
81.2
+15.7
SWE-smith
300
74.7
100.0
+25.3
SWE-agent
1,200
67.7
70.5
+2.8
tau2-bench (tel)
1,095
28.5
45.6
+17.1
tau2-bench (ret)†
1,095
52.9
65.1
+12.2
tau2-bench (air)
480
56.5
57.3
+0.8
ATBench
600
47.8
62.5
+14.7
OSWorld
1,286
55.0
70.7
+15.7
Figure 10: Per-dataset test fitness across all methods including Alergia. Our FSM achieves ≥0.997 fitness on all panels. Process mining baselines (Heur., Ind.) achieve competitive fitness but with low precision (Table 18).
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.
Table 6: Cross-model failure-prediction AUROC across three tau2-bench suites. Self-AUROC (diagonal) and mean cross-AUROC (off-diagonal); σ over the 4 self-AUROCs and 12 cross-pair AUROCs. Mean cross-AUROC across all 36 pairs is 0.786 vs. self mean 0.877 (0.091 gap). Self/cross fitness on airline 1.000/0.962, retail 1.000/0.972, telecom 1.000/0.990.
Self-AUROC (diagonal)
Cross-AUROC (off-diagonal)
Suite
mean
σ
range
mean
σ
range
gap
τ2 airline
0.926
0.051
0.84–0.97
0.773
0.102
0.56–0.92
0.154
τ2 retail
0.749
0.052
0.68–0.82
0.681
0.075
0.54–0.79
0.068
τ2 telecom
0.956
0.028
0.92–0.99
0.905
0.045
0.82–0.99
0.051
Mean (3 suites)
0.877
–
–
0.786
–
–
0.091
Figure 13: Random and permuted trace rejection rates. Our FSM achieves near-100% rejection across most datasets, while RPNI shows poor permuted rejection on WebArena.
Table 7: Compression results on unlabeled datasets. Same methodology as Table 1.
Ours
RPNI
Alergia
Dataset
|Q|
Fit
|Q|
Fit
|Q|
Fit
Compr.
Who_and_When
9
1.000
971
0.984
12
1.000
108×
Mind2Web
8
1.000
476
0.970
8
1.000
60×
GUI-Odyssey
7
1.000
21,255†
0.929
24
0.999
3,036×
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.
Table 12: k-Tails results. |Q|: states. Fit: test fitness. TO: timeout (300s). Our method requires no hyperparameter.
Ours
k-Tails (k=1)
k-Tails (k=2)
Dataset
|Q|
Fit
|Q|
Fit
|Q|
Fit
SWE-smith
10
1.000
22
1.000
53
1.000
SWE-agent
25
0.999
74
0.996
332
0.993
WebArena
25
1.000
30
0.743
172
0.743
AgentNet
25
1.000
33
0.806
TO
tau2-bench (air)
18
1.000
37
0.973
731
0.773
tau2-bench (ret)
19
1.000
46
0.997
874
0.888
tau2-bench (tel)
43
1.000
210
0.930
TO
Who_and_When
9
1.000
14
0.541
20
0.541
Mind2Web
8
1.000
34
0.965
95
0.905
GUI-Odyssey
7
1.000
73
0.964
759
0.939
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↔retail (near-1.0).
Table 15: Failure prediction with Alergia FSMs under matched pipeline. Identical features, classifier, and CV protocol; FSM source varies. CV: 10×5-fold; Holdout: held-out test AUROC.
CV AUROC
Holdout AUROC
Dataset
Ours
Alergia
Ours
Alergia
tau2-bench (tel)
0.923
0.748
0.915
0.752
WebArena
0.864
0.844
0.888
0.868
AgentNet
0.871
0.871
0.872
0.872
SWE-agent
0.790
0.709
0.805
0.714
tau2-bench (air)
0.792
0.664
0.826
0.764
tau-bench (ret)
0.789
0.606
0.666
0.498
tau-bench (air)
0.758
0.651
0.841
0.810
tau2-bench (ret)
0.713
0.576
0.743
0.575
SWE-smith
0.685
0.653
0.673
0.683
Table 17: Failure prediction: neural models on sequence vs. FSM features. CV AUROC (10×5-fold). Bold: FSM>Seq for same model.
MLP
GRU
Transformer
Dataset
Seq
FSM
Seq
FSM
Seq
FSM
SWE-smith
0.663
0.699
0.683
0.700
0.649
0.665
SWE-agent
0.782
0.790
0.762
0.793
0.779
0.751
tau2-tel
0.962
0.969
0.958
0.970
0.964
0.967
tau2-air
0.816
0.839
0.793
0.815
0.819
0.845
tau2-ret
0.747
0.800
0.698
0.789
0.755
0.798
WebArena
0.848
0.861
0.818
0.835
0.860
0.868
AgentNet
0.878
0.920
0.877
0.917
0.876
0.917
FSM wins
7/7
7/7
6/7
Table 18: Precision analysis. Rand./Perm.: acceptance rate (lower is better).
Ours
RPNI
Dataset
Rand.
Perm.
Rand.
Perm.
SWE-smith
0.0%
0.1%
0.0%
0.0%
SWE-agent
0.0%
0.05%
0.0%
1.6%
WebArena
0.0%
0.02%
0.2%
75.3%
AgentNet
0.0%
0.02%
0.2%
0.9%
tau2-bench (air)
0.0%
0.0%
0.0%
11.5%
tau2-bench (ret)
0.0%
0.0%
0.0%
3.1%
tau2-bench (tel)
0.0%
0.0%
0.0%
0.0%
Table 19: Adversarial trace rejection rate (%, ↑). Five mutations per trace.
Dataset
Subst.
Insert
Delete
Swap
Suffix
SWE-smith
81
100
98
100
100
SWE-agent
87
100
97
100
97
tau2-tel
77
96
61
93
100
tau2-air
78
90
77
93
97
tau2-ret
79
92
80
95
100
WebArena
100
96
84
100
68
AgentNet
100
100
97
100
99
Table 20: PM4Py miner results. Fit: replay fitness. Prec: precision from conformance checking. p/t: Petri net places/transitions.
Alpha Miner
Heuristic Miner
Inductive Miner
Dataset
p/t
Fit
Prec
p/t
Fit
Prec
p/t
Fit
Prec
Who_and_When
3/8
0.37
0.19
10/23
1.00
0.31
16/24
1.00
0.27
SWE-smith
7/9
0.15
0.20
13/22
1.00
0.36
25/33
1.00
0.23
Mind2Web
2/7
0.63
0.29
15/29
0.96
0.45
23/30
1.00
0.32
SWE-agent
12/24
0.05
0.00
21/59
1.00
0.20
44/70
1.00
0.13
tau2-bench (air)
3/17
0.45
0.24
15/37
0.95
0.20
63/93
1.00
0.17
tau2-bench (ret)
3/18
0.46
0.23
12/32
0.95
0.21
36/58
1.00
0.14
tau2-bench (tel)
4/4
0.46
0.25
10/13
0.95
0.80
15/19
1.00
0.42
GUI-Odyssey
2/6
0.58
0.33
12/22
0.98
0.64
21/27
1.00
0.46
WebArena
23/24
0.24
0.11
35/71
0.98
0.55
17/42
1.00
0.10
AgentNet
174/24
0.30
0.00
35/84
0.99
0.45
18/39
1.00
0.13
Table 21: Convergence and generalization. Left: fraction at which fitness reaches 0.99. Right: train−test fitness gap at increasing fractions (all within ±0.003). Convergence behavior is similar across extraction levels (Appendix G.2).
Convergence
Gen. gap (train−test)
Dataset
Train
0.99 at
Frac
|Q|
10%
30%
60%
100%
Who_and_When
147
8
5%
9
+0.002
+0.001
0
0
SWE-smith
400
40
10%
10
−0.002
−0.001
0
−0.001
Mind2Web
400
20
5%
8
−0.003
−0.001
0
0
SWE-agent
1,600
240
15%
25
−0.002
−0.001
−0.001
+0.001
Table 22: Conditional entropy (bits) by context order. The large drop from order 0→1 and convergence by order 2–3 shows strong sequential regularity.
Dataset
k=0
k=1
k=2
k=3
Drop 0→1
SWE-agent
2.16
1.06
0.80
0.79
51%
SWE-smith
1.98
0.63
0.55
0.55
68%
Mind2Web
1.69
0.74
0.79
0.68
56%
Table 23: Early prediction AUROC (holdout) by trace completion fraction. FSM vs. raw-statistic baseline.
Table 25: Best monitoring rules by F1 score. All rules use a single FSM-derived feature with a fixed threshold.
Dataset
Rule
Prec.
Recall
F1
SWE-agent
cycle-rate >0.885
0.956
0.451
0.613
SWE-smith
cycle-rate >0.878
0.267
0.750
0.393
Table 26: Failure prediction: FSM features vs. probabilistic baselines (holdout AUROC).
Dataset
FSM feat.
Trans. CE
Likelihood
N-gram
SWE-agent
0.813
0.452
0.626
0.317
SWE-smith
0.718
0.719
0.711
0.622
Table 27: ProbGuard (Wang et al., 2025b) vs. our FSM features for failure prediction. ProbGuard column = best AUROC over 20 configurations (Kunsafe× horizon, polarity-aware); FSM column = holdout AUROC from Table 14. Our FSM wins on every shared dataset by mean +17.6pp.
Dataset
ProbGuard (Wang et al., 2025b)
FSM features (ours)
Δ
τ2-bench (tel)
0.709
0.941
+0.232
τ2-bench (air)
0.723
0.864
+0.141
τ2-bench (ret)
0.566
0.779
+0.213
SWE-agent
0.683
0.799
+0.116
SWE-smith
0.525
0.703
+0.178
Mean (5 shared datasets)
0.641
0.817
+0.176
Table 28: Fitness under 10% perturbation intensity. Baseline fitness shown for reference.
Dataset
Subst.
Insert.
Swap
Trunc.
Base
SWE-smith
0.658
0.825
0.892
1.000
1.000
SWE-agent
0.818
0.885
0.938
0.999
0.999
Mind2Web
0.881
0.985
0.999
1.000
1.000
Who&When
0.828
0.865
1.000
1.000
1.000
Table 29: Statistical next-step prediction: top-1 accuracy (%, ↑) on full validation sets.
Dataset
Steps
Unigram
FSM
AWM
AWM cov.
SWE-smith
5,500
50.0
100.0
34.5
34.5%
WebArena
17,146
26.2
81.1
81.0
92.9%
SWE-agent
22,288
49.1
65.7
26.6
57.0%
tau2 (tel)
23,055
33.0
61.8
19.8
59.0%
tau2 (air)
4,020
30.8
69.2
55.9
91.3%
tau2 (ret)
10,207
27.4
72.6
63.5
91.4%
Mind2Web
886
80.2
80.2
0.0
0.0%
Table 30: Cross-dataset transfer: FSM vs. raw feature AUROC. Bold: FSM advantage > 3pp.
Test dataset
Train
Features
SWE-sm
SWE-ag
SWE-smith
FSM
0.681
0.715
Raw
0.694
0.683
SWE-agent
FSM
0.648
0.780
Raw
0.682
0.720
Findings
Across all twelve public datasets, the extracted FSMs stayed compact at 7-43 states, replayed held-out data with at least 0.997 fitness, and were built in milliseconds.
For next-step prediction, FSM-state context beat AWM's top-1 accuracy on every ground-truth-matched dataset (e.g., SWE-smith 100% vs. 34.5%, tau2-telecom 61.8% vs. 19.8%), and a controlled comparison showed FSM conditioning improved cross-entropy by an average of 0.155 bits (21%) over using raw context alone.
For failure prediction, per-state features reached held-out AUROC up to 0.94 (tau2-bench telecom), outperformed raw trace statistics by +7.9 percentage points on SWE-agent, while fitness alone gave AUROC around only 0.50.
Using only 50% of a trace, FSM features reached 92% of the AUROC achievable with the full trace, and on SWE-agent the monitor triggered early stopping at 32% completion, saving 68% of remaining compute with 85.9% precision and 95.5% recall.
Compared to the automata-learning baseline RPNI, the FSM used 15-3,036x fewer states while matching or exceeding replay fitness, and was constructed up to tens of thousands of times faster (1-110 ms vs. 7,000-36,000 ms).
Where it can be used
Automatically compressing an agent's execution history into a small structure for safety audits or for pinpointing which behavioral states cause bugs
Running a lightweight runtime monitor alongside a deployed agent that flags and stops likely-failing runs before they finish
Using the FSM-derived context, which draws on both successful and failed traces, as a lighter alternative or complement to workflow-memory systems that only learn from successes
Limits and open work
Evaluation was limited to twelve public datasets across coding, web-navigation, and customer-service agent domains with relatively small activity alphabets of 6-42 symbols.
The runtime monitor's rules (e.g., cycle-rate threshold) worked well on datasets with rich state diversity but under-discriminated on smaller-alphabet domains like tau2-bench retail and SWE-smith, requiring per-dataset tuning according to the authors.
The authors note the FSM recovers only the observed surface-level flow of activities (a directly-follows automaton), not the true underlying generating process, which is provably impossible to identify from positive examples alone.
Cross-model transfer of failure-prediction features was imperfect: mean cross-model AUROC was 0.786 versus 0.877 within the same model, showing a measurable gap.
Structurally similar domains that share a schema, such as tau2-bench's airline and retail suites, were an exception where the FSM could not clearly distinguish out-of-distribution traces from in-distribution ones.
Why it matters
If long, opaque agent execution logs can be summarized into a small, inspectable structure, teams can audit and monitor deployed agents for safety without reading every trace by hand. Because the method does not depend on any specific LLM, it offers a reusable building block that could apply across many different agent systems.
Terms in this paper
유한 상태 기계 (FSM) · A mathematical model that represents a system's behavior as a set of possible situations (states) and rules for moving between them
재현 적합도 (replay fitness) · The fraction of a real execution trace that the FSM can successfully follow step by step; closer to 1.0 means the FSM explains the behavior well
AUROC · A score measuring how well a model separates two outcomes (e.g., success vs. failure); 0.5 is random guessing, 1.0 is perfect separation
Agent Workflow Memory (AWM) · A prior method that extracts linear sequences of steps only from successful execution traces, used here as a comparison baseline
cross-entropy · A measure in bits of how far a model's predicted probability of the next action is from what actually happened; lower means better prediction
Original abstract (English)
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 >=0.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.
Authors · Seonglae Cho, Franklin Cardenoso Fernandez, Umar Mohammed, Zekun Wu, Kleyton Da Costa, Ilham Wicaksono, Adriano Koshiyam
