Automata from Agent Traces: Failure and Next-Step Prediction
Seonglae Cho, Franklin Cardenoso Fernandez, Umar Mohammed, Zekun Wu, Kleyton Da Costa, Ilham Wicaksono, Adriano Koshiyama
cs.AI, cs.CL, cs.LG
2026-08-25
A last-activity merge turns LLM-agent traces into 7–43-state FSMs that replay held-out data at >=0.997 fitness, beat AWM on next-step, and reach 0.94 AUROC on failure.
LLM-agent traces are long and unstructured. Safety auditing, runtime monitoring, and next-step prediction all need a topology shared across runs. Existing tools work per-trace or harvest linear workflows from successes only. Agent Workflow Memory (AWM) is the latter: failed runs, with their loops and detours, never enter the memory.
Gold's theorem says you cannot identify a target language from positive examples alone. Agent action alphabets are small, 6–42 symbols across twelve public datasets. On tau2-bench, one automaton built from four chat models replays each model at fitness 1.000. The topology looks more like the harness (system prompt, tool set, task mix) than like a particular LLM. That bound is what makes inverse construction tractable.
Three steps, no learning hyperparameters.
Merging only adds outgoing edges, so every training trace the trie accepts remains accepted. The object recovered is the directly-follows automaton of the corpus, not the generating language.
From there, next-step probabilities are smoothed transition counts at the current state. Failure prediction replays each trace and extracts per-state visit frequency, message length, error rate, plus cross-entropy anomaly features, then fits a gradient-boosted classifier. The online monitor is thinner still: a cycle-rate threshold of 0.778 plus a minimum unique-state count after warmup. Replay costs 0.006 ms per step and trains nothing.
Across twelve datasets the automata have 7–43 states, held-out replay fitness at least 0.997, and build in 1–110 ms. Compression versus RPNI is 15–3,036×. Alergia matches fitness with 1.0–6.0× more states. RPNI accepts 75% of permuted traces on WebArena; this construction rejects every random trace and at least 99.9% of permuted traces.
| Method | Mean cross-entropy (bits, lower is better) |
| Unigram | 2.44 |
| RPNI | 3.40 |
| Order-1 FSM | 0.93 |
| FSM + logistic regression | 0.73 |
As LLM context, dumping the full graph loses to AWM. A minimal format with next-action probabilities plus the top-15 multi-step continuations from the current state wins on all eight datasets, six of them at p < 10^{-8}. The gap is larger on low-success datasets, where AWM never sees failure workflows.
Raw fitness is uninformative for failure (AUROC near 0.50). Per-state features reach held-out AUROC 0.941 on tau2-bench telecom, 0.903 on WebArena, 0.894 on ATBench, 0.799 on SWE-agent. On SWE-agent, successes use 9 of 25 states; failures visit all 25. Length alone scores 0.659. At 50% completion the features already hold 92% of full-trace AUROC.
The monitor fires at 32% mean completion on SWE-agent (precision 85.9%, recall 95.5%, F1 0.904) and saves 68% of remaining compute. At cycle-rate > 0.957 it reaches 100% precision and 11.3% recall. SWE-agent's 84.3% failure rate means a flag-everything baseline already has F1 0.914; the monitor's value is when to stop. On smaller alphabets (retail, SWE-smith) it over-triggers.
If you already log traces, this is a millisecond-scale structural substrate, not a new agent. Compact states pool enough observations for positive-only estimates to be well-conditioned; RPNI splits the same counts across thousands of sparse states and underperforms a unigram. One automaton serves as workflow memory, next-step prior, failure features, and a runtime monitor. Topology tracks the harness more than the model, so reuse across models is plausible.
The construction is classical. The claim is that bounded agent alphabets make it statistically useful.
The automaton accepts the directly-follows closure of observed traces. Adversarial traces that keep activity bigrams can still replay. The extraction function is dataset-specific. Cross-model transfer is measured only on three tau2-bench suites (mean cross-AUROC 0.786 versus 0.877 self). Workflow memory is compared only to AWM, not to methods such as ReasoningBank that ingest failures. The monitor needs enough state diversity; small alphabets need retuning. High base-rate tasks inflate F1, so precision and trigger timing matter more than the headline F1.