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.
Figures & tables
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.
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 ×
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 .
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
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 .
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.
Context format
Top-1 (%)
No memory (trace prefix only)
27.6
AWM (linear success workflows) ( Wang et al., 2025d )
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.
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.
Appendix figures & tables39 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Extracted FSM for a customer service agent at role-level granularity (tau2-bench airline, 6 states, ∣A∣=5 ). The tool-level FSM (18 states, ∣A∣=17 , Table 1 ) further decomposes a:tc / tool into per-tool states. The tool-call loop (a:tc ↔ tool) captures repeated API invocations; the conversational loop (a:txt → usr) captures dialogue turns.
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.
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 ×
Appendix
Table 7: Compression results on unlabeled datasets. Same methodology as Table 1 .
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
Appendix
Table 12: k-Tails results. ∣Q∣ : states. Fit: test fitness. TO: timeout (300s). Our method requires no hyperparameter.
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.
Figure 12: SWE-smith FSM (10 states, 17 transitions). The core cycle is bash → tool → edit → tool → bash : agents execute commands, inspect results, make edits, and repeat. The submit state is a terminal action reached after successful editing.
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.
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
Appendix
Table 17: Failure prediction: neural models on sequence vs. FSM features. CV AUROC (10 × 5-fold). Bold: FSM > Seq for same model.
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%
Appendix
Table 18: Precision analysis. Rand./Perm.: acceptance rate (lower is better).
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
Appendix
Table 19: Adversarial trace rejection rate (%, ↑ ). Five mutations per trace.
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
Appendix
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 rejection rates. Our FSM achieves near-100% rejection across most datasets, while RPNI shows poor permuted rejection on WebArena.
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
Appendix
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 ).
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.
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%
Appendix
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.
Fraction
SWE-agent
SWE-smith
FSM
Base
FSM
Base
10%
0.657
0.400
0.722
0.416
25%
0.656
0.456
0.687
0.693
50%
0.726
0.677
0.681
0.668
75%
0.726
0.672
0.688
0.685
100%
0.773
0.753
0.682
0.692
Appendix
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
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
Appendix
Table 26: Failure prediction: FSM features vs. probabilistic baselines (holdout AUROC).
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
Appendix
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
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
Appendix
Table 28: Fitness under 10% perturbation intensity. Baseline fitness shown for reference.
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%
Appendix
Table 29: Statistical next-step prediction: top-1 accuracy (%, ↑ ) on full validation sets.
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
Appendix
Table 30: Cross-dataset transfer: FSM vs. raw feature AUROC. Bold: FSM advantage > 3pp.
Dataset
10%
20%
30%
50%
100%
SWE-smith
0.502
0.662
0.703
0.660
0.685
SWE-agent
0.806
0.791
0.812
0.818
0.795
Appendix
Table 31: Learning curves: failure prediction AUROC at increasing training fractions. Bold: first fraction reaching 95% of final AUROC.
Dataset
DecPts
Succ paths
Fail paths
Overlap
Top JSD
SWE-agent
7
275
1,496
41
0.014
SWE-smith
5
330
123
11
0.021
Appendix
Table 32: Counterfactual path analysis. Decision points: states with JSD >0.001 between success/failure transitions.
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).
Dataset
∣A∣
∣Q∣
FSM bits
Raw bits
MDL
Gzip
SWE-smith
9
10
108
107,704
0.001
0.012
SWE-agent
27
25
340
556,450
0.001
0.018
Mind2Web
7
8
87
12,786
0.007
0.026
Who&When
8
9
99
12,276
0.008
0.019
Appendix
Table 33: Information-theoretic compression analysis. MDL: minimum description length ratio (FSM bits / raw trace bits): gzip: compression ratio of raw sequences.
Path diversity
RQA (AUROC)
Dataset
Traces
Unique
Sing.%
Top-5%
RR
DET
maxDiag
diagEnt
SWE-smith
500
442
82.0
5.8
0.662
0.643
0.631
0.599
SWE-agent
2,000
1,730
82.0
5.1
0.695
0.694
0.695
0.704
tau2-tel
1,824
5
0.0
100.0
0.562
0.563
0.562
0.566
tau2-air
800
624
67.5
6.4
0.511
0.338
0.566
0.612
tau2-ret
1,824
1,521
73.2
2.0
0.574
0.471
0.520
0.521
Appendix
Table 34: Path diversity and RQA metrics. 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 (–).
Dataset
State
Visit%
Fitness drop
SWE-smith
system:text
1.9
1.000
user:text
1.9
0.979
asst:tool:bash
21.3
0.958
SWE-agent
user:text
49.9
0.999
edit:text
16.6
0.344
search:text
11.5
0.208
Appendix
Table 35: State importance: fitness drop upon state removal. Top 3 most critical states per dataset.
Loops (backedges)
Graph motifs
Dataset
Succ
Fail
Ratio
AUROC
Self
Bidir
Tri
Hub deg
SWE-agent
25.3
54.8
2.17 ×
0.665
0
11
0
15
SWE-smith
43.6
60.7
1.39 ×
0.654
0
6
0
7
tau2-tel
1.9
1.9
1.00 ×
0.562
1
2
2
4
tau2-air
17.1
21.5
1.26 ×
0.664
1
14
0
15
tau2-ret
20.3
21.0
1.03 ×
0.537
1
15
0
16
Appendix
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 (–).
Table 38: Temporal dynamics: entropy by execution phase and entropy drift (early − late). Who&When and Mind2Web lack success/failure labels (–).
Anomaly detection
Suffix (last k )
Dataset
Rej
Occ
Term
Cyc
Comp
P@10
k=2
k=3
k=5
k=10
SWE-agent
0.563
0.707
0.711
0.697
0.747
1.00
0.693
0.746
0.771
0.825
SWE-smith
0.406
0.605
0.429
0.679
0.653
0.20
0.540
0.546
0.550
0.590
Appendix
Table 39: Unsupervised monitoring. Left: anomaly detection components and composite AUROC. Right: suffix monitoring AUROC at window size k .
Dataset
Prec
Recall
F1
Latency
Saved
Steps saved
Lift
SWE-agent
85.9%
95.5%
0.904
32%
68%
16,711
1.02 ×
tau2-bench (air)
76.0%
79.2%
0.776
56%
44%
325
1.27 ×
tau2-bench (ret)
31.0%
60.0%
0.409
63%
37%
247
0.95 ×
SWE-smith
16.0%
100.0%
0.276
17%
83%
936
1.00 ×
Appendix
Table 40: Runtime monitor results. Latency: mean % of trace at intervention. Saved: mean % of remaining computation avoided.
Threshold
Precision
Recall
F1
Mean latency
> 0.750 (p30)
86.4%
85.2%
0.858
39%
> 0.842 (p50)
90.5%
65.3%
0.759
47%
> 0.917 (p70)
95.6%
38.9%
0.553
63%
> 0.957 (p90)
100.0%
11.3%
0.203
59%
Appendix
Table 41: Multi-threshold analysis (cycle-rate only) on SWE-agent. Higher thresholds yield higher precision at the cost of recall.
Dataset
Features
d
CV AUROC
Holdout
SWE-agent
bag (freq.)
24
0.702 ± 0.030
0.694
bigram (trans.)
62
0.699 ± 0.029
0.698
stats (seq.)
6
0.757 ± 0.027
0.782
all-seq (LR)
92
0.771 ± 0.027
0.793
all-seq (MLP)
92
0.711 ± 0.044
0.764
FSM per-state
34
0.790 ± 0.021
0.813
Appendix
Table 42: Failure prediction: sequence-level features (bag, bigram, stats, all-seq) vs. FSM per-state features, L1-regularized LR. d : feature dimensionality. FSM wins on every dataset.
LLM agents increasingly operate through multi-turn tool use and environment interaction, where safety risks often emerge from intermediate steps long before they surface in the final outcome. Reactive auditing is therefore insufficient: post-hoc diagnosis frequently misses the chance to flag risks while they are unfolding. We propose TRACES, a representation-based proactive auditor that learns prefix-level trajectory risk states from the hidden representations of an observer LLM. TRACES induces latent mechanism features from step representations and models their temporal evolution to estimate whether a partial trajectory is drifting toward unsafe behavior. To sidestep the cost and ambiguity of step-level risk annotation, TRACES is trained with weak trajectory-level supervision while still producing dense prefix-level risk estimates. Across multiple agent safety benchmarks, TRACES improves both full-trajectory safety prediction and proactive risk discrimination. Our analyses further suggest that these risk states can help train a safer agent, highlighting the broader potential of proactive auditing for long-horizon agent safety.
Jiaqian Li, Yanshu Li, Boxuan Zhang +2
Brown University · The University of Texas at Austin · Rutgers University +1
An LLM agent using tools can fail silently. It stops before the task is done, raises no error, and answers fluently. Two kinds of monitor address this, one deciding whether a run failed and the other naming the step where failure became unavoidable. Much of the reported performance on both tasks comes from regularities that need no model. Failing runs are longer, and the step labelled decisive is usually the last. A rule that always names the last step is correct 67% to 96% of the time here, without reading the run at all. That ceiling reflects how the labels were written, not how agents break. On failures whose decisive step replay can confirm, it falls to near chance. Reporting gain over that rule therefore changes what a score means. Under that correction, methods tested here gain nothing on give-up failures, while several published systems keep a clear advantage on other splits. For detection, the agent's internal states beat transcript length and text similarity on the agent benchmark, and hold up where the text baseline does not. Precision stays low when failures are rare, so such a monitor should rank runs for review, not replace it.
Ramesh Arvind Naagarajan, Stefan Streif
Professorship for Automatic Control and System Dynamics Chemnitz University of Technology, Chemnitz, Germany · Department of Bioresources Fraunhofer Institute for Molecular Biology and Applied Ecology Giessen, Germany
LLM agents fail mid-episode -- they loop, cascade tool errors, drift off goal, fabricate results, or silently absorb corrupted content -- and the standard remedy, judging every step with a second LLM, costs more than the agent itself. We ask how much detection is achievable from observable step telemetry alone, using monitors costing microseconds per step and trained only on healthy runs. On 2,823 committed agent episodes across three frameworks, three local models (qwen2.5 7b/3b, llama3.1 8b) and a commercial API (gemini-2.5-flash), a one-class echo-state-network ensemble with CUSUM alarms detects 0.71 of failures at a 5% false-alarm budget (AUROC 0.872). Its advantage over a memoryless baseline is a monotone function of post-onset horizon (+0.09 at <=3 steps, +0.40 at >=9), predicting its own failure region out of sample on AFTraj-2K. Ranking transfers with no retraining to two corpora from other groups (AFTraj-2K 0.745, ATBench 0.779). Monitors carry two burdens: a per-deployment healthy null (they do not transfer -- AUROC 0.527 cold against 0.885 recalibrated) and a residual false-alarm rate. We add a layer carrying neither: deterministic verification, which recomputes a run's stated total from the tool results it actually received and confirms every required call was made. Head-to-head it catches 60% of failures (96% with the coverage check) at 0 of 63 false positives against the monitor's 54% at 17%, transfers unchanged to llama3.1:8b (110 of 110 at 0 of 10), and trips on 0 of 1825 healthy episodes. Detection is then closed into repair: each flagged run is rolled back and re-run live, recovering 45% of failures against a 16% resampling control (p=0.0005) and lifting task success from 52% to 73% for about one extra model call per run. The system runs at ~200 microseconds per step, three orders of magnitude below a judge call. Code, traces and results are released.