LLM 에이전트가 남긴 대량의 실행 기록을 하나의 작은 유한 상태 기계로 압축해, 다음 행동 예측과 실패 조기 탐지에 함께 쓸 수 있게 했다
arXiv:2608.236702026-08-26
Automata from Agent Traces: Failure and Next-Step Prediction
LLM 에이전트가 남긴 대량의 실행 기록을 하나의 작은 유한 상태 기계로 압축해, 다음 행동 예측과 실패 조기 탐지에 함께 쓸 수 있게 했다
LLM 에이전트가 작업을 수행하며 남기는 길고 복잡한 실행 기록은 사람이 읽고 안전을 점검하기 어렵다. 연구팀은 12개 공개 데이터셋의 실행 기록 전체를 7~43개 상태로 이루어진 작은 유한 상태 기계(FSM) 하나로 압축하는 방법을 제안하고, 이 FSM이 다음 행동 예측, 실패 예측, 실시간 모니터링에 모두 쓰일 수 있음을 측정했다. 압축된 상태 기계는 밀리초 단위로 만들어지며 검증 데이터를 0.997 이상의 정확도로 재현했다.
METAL LAB 해설 도표
METAL LAB이 원문을 바탕으로 재구성한 해설 도표이며, 논문 저자의 원문 figure가 아닙니다.
무엇을 했나
에이전트가 남긴 메시지(도구 호출, 행동 태그, 명령어 등)를 하나의 기호로 바꾼 뒤, 여러 실행 기록을 접두사 트리로 합치고 마지막 활동 기준으로 상태를 병합해 결정적(같은 상황에서 항상 같은 다음 상태로 가는) 유한 상태 기계를 만든다.
이 구성 방식은 학습에 필요한 하이퍼파라미터가 전혀 없고 선형 시간에 끝나며, 12개 데이터셋 모두에서 7~43개의 작은 상태 수로 압축됐고 검증 데이터 재현율(fitness)이 0.997 이상이었다.
이렇게 만든 FSM을 다음 행동 예측에 문맥 정보로 넣었더니, 기존 성공 사례 기반 방법인 Agent Workflow Memory(AWM)보다 실제 정답과 대조 가능한 모든 데이터셋에서 더 높은 정확도를 보였다.
실패 예측에서는 각 상태별 행동 특징(방문 빈도, 메시지 길이, 오류율 등)을 뽑아 학습시킨 결과 held-out AUROC(무작위 추측이 0.5, 완벽 예측이 1.0인 판별력 지표) 최대 0.94를 기록했고, 실행 기록의 32%만 보고도 실패할 실행을 온라인 모니터가 먼저 걸러내 조기 중단시켰다.
행동의 구조가 사용된 LLM 종류보다 시스템(도구 구성, 배포 환경)에 더 크게 좌우된다는 것을 관찰했다. 즉 4개의 서로 다른 LLM으로 만든 실행 기록도 하나의 FSM으로 거의 완벽하게 설명됐다.
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
실제로 확인된 결과
12개 공개 데이터셋 모두에서 FSM은 7~43개 상태로 압축되었고, 검증 데이터 재현 적합도 0.997 이상, 구성 시간은 밀리초 단위였다.
다음 행동 예측에서 FSM 상태를 문맥으로 쓴 방법이 정답이 확인된 모든 데이터셋에서 AWM보다 높은 top-1 정확도를 보였고(예: SWE-smith 100% vs 34.5%, tau2-telecom 61.8% vs 19.8%), 통제된 비교에서는 원문 문맥만 쓴 경우보다 평균 0.155비트(21%) 크로스 엔트로피가 개선됐다.
실패 예측에서 상태별 특징으로 held-out AUROC 최대 0.94(tau2-bench telecom)를 기록했고, 원시 통계량 대비 SWE-agent에서 +7.9%p 높았으며, 원시 fitness만 쓴 경우는 AUROC 약 0.50에 그쳤다.
실행 기록의 50%만 보고도 전체 완료 시 AUROC의 92% 수준을 달성했고, SWE-agent에서는 32% 지점에서 실패 실행을 조기 종료시켜 남은 연산의 68%를 절약했다(정밀도 85.9%, 재현율 95.5%).
RPNI 등 기존 오토마타 학습 기법 대비 15~3,036배 적은 상태 수로 동등하거나 더 높은 재현 적합도를 달성했고, 구성 속도도 RPNI(7,000~36,000ms) 대비 최대 수만 배 빨랐다(1~110ms).
어디에 쓸 수 있나
에이전트 배포 전후로 실행 기록을 자동 압축해 안전성 감사나 버그 원인 상태를 찾는 용도
실시간 서비스 중인 에이전트의 진행 상황을 모니터링하다가 실패 징후가 보이면 조기에 중단시키는 런타임 감시 장치
성공 사례뿐 아니라 실패 사례까지 포함한 실행 이력을 바탕으로 다음 행동을 추천하는 보조 시스템(AWM 대체 또는 보완)
한계와 남은 검증
평가는 12개 공개 데이터셋(코딩 에이전트, 웹 탐색, 고객 서비스 등)에 한정되며, 활동 기호 집합이 6~42개로 비교적 작은 환경에서 검증됐다.
모니터 규칙(주기율 임계값 등)은 데이터셋별 특성에 따라 성능 차이가 크며, tau2-bench retail이나 SWE-smith처럼 상태 다양성이 낮은 도메인에서는 규칙이 실패를 잘 구분하지 못해 데이터셋별 조정이 필요하다고 저자들이 밝혔다.
FSM은 관측된 데이터의 표면적 흐름(directly-follows automaton)을 복원할 뿐 실제 에이전트를 생성한 근본 규칙을 복원하는 것은 원리적으로 불가능하다고 명시했다.
교차 모델 실패 예측 전이 성능은 자기 자신 평균 AUROC 0.877 대비 다른 모델 간 평균 0.786으로 차이가 있어, 모델 간 완전한 전이는 보장되지 않는다.
동일 스키마를 공유하는 tau2-bench 항공-소매 쌍처럼 구조가 비슷한 도메인 간에는 서로 다른 데이터셋임에도 FSM이 구분하지 못하는 예외가 있었다.
왜 중요한가
실행 기록을 사람이 일일이 읽지 않고도 안전 점검·이상 탐지·조기 중단이 가능한 작은 구조로 요약할 수 있다면, 실서비스에 배포된 에이전트를 실시간으로 감시하는 비용과 난이도를 크게 낮출 수 있다. 이 방법은 특정 LLM에 종속되지 않는 구조적 도구이므로 다양한 에이전트 시스템에 재사용할 수 있는 기반을 제공한다.
이 논문의 용어
유한 상태 기계(FSM) · 가능한 상황(상태)들과 그 사이를 오가는 규칙(전이)으로 시스템의 행동을 표현하는 수학적 모델
리플레이 적합도(fitness) · 실제 실행 기록을 FSM에 재생시켰을 때 FSM이 끝까지 따라갈 수 있는 비율. 1.0에 가까울수록 FSM이 실제 행동을 잘 설명한다는 뜻
AUROC · 성공과 실패를 얼마나 잘 구분하는지 나타내는 지표. 0.5는 무작위 추측 수준, 1.0은 완벽한 구분
Agent Workflow Memory(AWM) · 성공한 실행 기록에서 순차적 작업 흐름 패턴을 뽑아내는 기존 비교 대상 방법
크로스 엔트로피 · 다음에 어떤 행동이 나올지 예측한 확률이 실제와 얼마나 어긋나는지를 비트 단위로 측정한 값. 낮을수록 예측이 정확하다
저자 · Seonglae Cho, Franklin Cardenoso Fernandez, Umar Mohammed, Zekun Wu, Kleyton Da Costa, Ilham Wicaksono, Adriano Koshiyam
