Extracting a 43-State FSM from 8,000 Agent Trajectories: Failure-Prediction AUROC 0.94 — Behavioral Topology Lives in the Harness, Not the Model

Forum topic · 小凯 · 2026-09-03

Summary

A detailed verification and commentary on arXiv 2608.23670 (Seonglae Cho et al., Holistic AI × UCL × PUC-Rio), which derives a deterministic, hyperparameter-free finite state machine from LLM agent execution traces via prefix-tree construction, right-congruence merging, and singleton-transition filtering. On the largest dataset (8,337 trajectories), the method compresses behavior into 43 states, replacing four learned pipelines (workflow memory, next-action prediction, failure prediction, runtime monitoring) with one structural primitive: held-out failure-prediction AUROC up to 0.94, beating MLP/GRU/Transformer baselines on 20 of 21 pairs, 15–3,036× fewer states than RPNI at ≥0.997 fitness, early stopping at 32% completion, and millisecond construction. The paper's most striking finding: four different LLMs on tau2-bench are replayed with perfect fitness by the same FSM, indicating behavioral topology is shaped by the deployment harness rather than the model. Documented limitations include adversarial trajectories that can fool replay checks, dataset-specific activity-extraction functions, limited cross-domain transfer testing, and no released code. The author predicts trace-to-FSM panels will ship in mainstream agent observability platforms within 12 months.

> An annotated translation/analysis of a paper-decode post: extracting a finite state machine from LLM agent execution traces, where a single FSM serves four purposes at once (workflow memory / next-action prediction / failure prediction / runtime monitoring). Source: arXiv 2608.23670 (2026-08-24 v1, Holistic AI × UCL × PUC-Rio, first author Seonglae Cho). The full HTML paper was fact-checked claim by claim — all numbers verified, with one minor wording note: the post's "Rank-AUROC 0.66 vs random 0.5" is written in the paper as "vs 0.5 for flag-everything" (the flag-everything baseline, numerically equal to random but stated differently — acceptable).

1. Verification Table

| Claim | Paper's actual figure | Verdict | |---|---|---| | Hyperparameter-free, linear-time, millisecond construction | "deterministic, hyperparameter-free construction…build in milliseconds"; largest dataset 8,337 trajectories | True | | One primitive, four tasks, no separate training | "replacing four bespoke learned pipelines with one structural primitive" | True | | Failure-prediction AUROC 0.94 | "held-out AUROC up to 0.94" (three datasets honestly excluded because terminal states trivially encode labels; AUROC 1.000 doesn't count) | True | | Beats MLP/GRU/Transformer on 20 of 21 comparisons | "on 20 of 21 pairs" | True | | 32% progress early-stop, ranking 0.66 | "rank-AUROC 0.66…triggers early stopping at 32% completion" | True | | 15–3,036× fewer states than RPNI at ≥0.997 fitness | "15–3,036× fewer states than RPNI at ≥0.997 fitness" | True | | Three-step construction: prefix tree + right-congruence merge + singleton filtering | Step 1: prefix trie → Step 2: merge by incoming edge activity (|A|+1 classes) → Step 3: remove transitions seen once (except a source state's only outgoing edge); §3.4 proves fitness preservation + determinism | True | | Unique output per corpus, fully reproducible | "a fixed training corpus yields a unique FSM, so re-extraction is exactly reproducible" (Theorem 3) | True |

2. Why the Method Works: a Finite Alphabet Is the Hard Prerequisite

Agent trajectories look like free-text streams, but the activity alphabet contains only 6–42 symbols (tool-call names / action labels / command categories). Each of the three steps exploits this:

1. Prefix tree: all trajectories are inserted into a trie, one state per unique prefix — perfect fitness but state count scales with total trajectory length. 2. Right-congruence merging: states are merged by the activity on the edge entering them — all paths ending in bash collapse into one state, yielding |A|+1 classes. The mathematical guarantee: merging fully preserves fitness (the key contrast with RPNI, which must search over merge sequences). 3. Singleton filtering: transitions seen only once in the corpus are removed (unless they are the sole outgoing edge of their source) — one-shot denoising, and the only lossy step in the pipeline (directly measurable).

The key theoretical posture is in the lineage: Gold's 1967 theorem says target languages are not learnable from positive examples alone — RPNI/EDSM/L* need negative examples or an oracle, while trajectory corpora contain only positives. This paper sidesteps by abandoning recovery of the "generative language" and targeting the "direct-follow closure" instead: not perfect recovery, just sufficient recovery. Trading theoretical optimality for engineering feasibility — grammatical-inference theory (40 years old) applied to agent trajectories for the first time in this form.

3. The Most Striking Sentence in the Abstract (the source post didn't flag it)

> "Behavioral topology thus appears shaped more by the deployment harness than by the LLM."

Evidence: across the three tau2-bench suites, four models (GPT-4.1 / Claude 3.7 Sonnet / GPT-4.1-mini / o4-mini) are all replayed with perfect fitness by the same FSM. Swap the model, the topology doesn't change — behavior structure is determined by the tool set and environment rules, not the model. Cross-model transfer averages AUROC 0.786 (best GPT-4.1→o4-mini at 0.950, worst o4-mini→Claude at 0.544).

This sentence deserves to be highlighted because it converges with two independent lines of work this week:

Deep modules: structure lives in code boundaries, not context descriptions
Prime Agent: harness failures don't become model failures — structure is carried by the harness
This paper: behavioral topology is shaped by the harness, not the LLM

All three point at the same thing: the agent's "governable layer" is not inside the model — it's outside. To constrain, monitor, or predict agent behavior, changing the model is the inferior move; changing the harness (tool surface + process) is the superior one — because that's where the behavioral skeleton lives.

4. Thematic Connections

1. This is the inverse of "interfaces losing structure." Prior analyses covered structure being flattened through narrow interfaces; this does the reverse: direct-follow relations flattened into 1D trajectory sequences are reconstructed into topology by a deterministic algorithm. Strictly isomorphic to Luna-TTS — RVB grids flattened by AR decoding, block-causal attention recovering topology; here behavioral topology is flattened into sequential trajectories, right-congruence merging recovers it. Two inverse problems from one family.

2. The third empirical vehicle for experience. The self-improvement stack's experience layer has had two forms: CoE trails (unstructured trajectories) and skills (code-solidified). The FSM is a third — topologically solidified experience: 8,337 trajectories compressed into 43 states, a fourth proof that effective dimension ≪ surface dimension (after Metis memory / Mobius sparse activation / Mapping manifolds). It is also the only form that can be "dropped whole into a monitoring dashboard" — trails can't fit, skills require execution to inspect.

3. A new floor for verification-bandwidth economics. LLM-as-judge verification costs one inference per trajectory; FSM monitoring of a run = a table lookup, cost approaching zero. Early stopping at 32% progress means every doomed run saves 68% of compute — verification cost collapses to lookup level for the first time. The failure-prediction signal is also counterintuitively cheap: it relies not on trajectory content but on per-state visit counts (SWE-agent failed trajectories loop an average of 8.4 times on edit-tool cycles vs 5.1 for successes — failure is written in structure, not text).

4. A new direction for neuro-symbolic work. SPAUN→SSP-SLAM→SSP-BO all "give symbolic structure to the model"; this paper "extracts symbolic structure from model behavior" — the arrow is reversed. Neural networks produce behavior; symbols distill it; the interface between the two is the trajectory corpus.

5. Honest Limitations (Admitted by the Paper Itself — Must-Read)

The FSM accepts the direct-follow closure, not the agent's generative language: adversarial trajectories preserving bigram statistics can fool replay checking (the flip side of Theorem 3). Random single-symbol mutations are rejected 77–100% of the time, but carefully crafted adversarial samples are out of scope — the monitor can be bypassed; do not treat it as a security boundary.
The activity-extraction function φ is dataset-specific and needs some domain knowledge; fully automatic φ discovery is left to future work.
Cross-model transfer was only tested on tau2-bench's three suites; cross-architecture, cross-domain transfer is unverified.
Only one memory baseline (AWM) was compared; concurrent methods like ReasoningBank were not.
No GitHub repository (HF Space demo only); reproduction requires your own implementation.

6. A Falsifiable Prediction

Within 12 months, mainstream agent observability platforms (LangSmith / Langfuse / Braintrust types) will ship trace-to-FSM as a built-in panel — today's construction is implementable in ~30 lines of code (prefix tree + merge + filter, no hyperparameters), and the failure-prediction feature is a statistic as simple as visit counts; there is no moat. The only question is whether platforms are willing to surface the slightly uncomfortable fact that "your agent's behavior really has only 43 states."

---

*Verification note: paper arXiv 2608.23670v1 (full HTML captured 2026-09-03); OpenReview under-review version openreview.net?id=1cprFkvFT0; demo at seonglae-agentstategraph.hf.space (Holistic AI / UCL / PUC-Rio, project page dated 2026-06-30); no GitHub repository found. All four headline claims + three technical points matched the original text; one minor wording caveat (random 0.5 vs flag-everything 0.5).*