From 8,000 Agent Trajectories to 43 States: An FSM That Predicts Failures at 0.94 AUROC — and Shows Behavioral Topology Lives in the Harness, Not the Model

Forum topic · 小凯 · 2026-09-03

Summary

A Chinese tech forum post reviews a paper (arXiv 2608.23670, Holistic AI / UCL / PUC-Rio, first author Seonglae Cho) that extracts finite state machines from LLM agent execution traces with a deterministic, hyperparameter-free, linear-time construction. One FSM simultaneously serves as workflow memory, next-step predictor, failure predictor, and runtime monitor: 8,337 trajectories compress into as few as 43 states, held-out failure-prediction AUROC reaches 0.94, rank-AUROC hits 0.66 with early stopping at 32% completion, and the method beats MLP/GRU/Transformer baselines on 20 of 21 pairs while using 15–3,036× fewer states than RPNI at ≥0.997 fitness. The paper's boldest finding: across tau2-bench, four different models (GPT-4.1, Claude 3.7 Sonnet, GPT-4.1-mini, o4-mini) are replayed by the same FSM at perfect fitness — behavioral topology is shaped by the deployment harness, not the LLM. The post fact-checks all claims against the paper (all verified), discusses honest limitations (replay checkers are not security boundaries; no GitHub repo), and predicts trace-to-FSM will become a built-in feature of agent observability platforms within 12 months.

This post is a Chinese forum author's verified deep-read of a paper on extracting finite state machines (FSMs) from LLM agent trajectories. The source article fact-checked every claim against the paper's full text — all numbers below were confirmed verbatim against arXiv 2608.23670 (Holistic AI × UCL × PUC-Rio, first author Seonglae Cho). Below is a full English rendering of the analysis.

The Core Result

The paper extracts an FSM from agent execution traces with a deterministic, hyperparameter-free construction that builds in milliseconds (largest dataset: 8,337 trajectories). One structural primitive replaces four bespoke learned pipelines:

Workflow memory
Next-step prediction
Failure prediction — held-out AUROC up to 0.94 (three datasets were honestly excluded because terminal states directly encoded labels; an AUROC of 1.000 doesn't count)
Runtime monitoring — rank-AUROC 0.66, enabling early stopping at 32% completion

It beats MLP/GRU/Transformer baselines on 20 of 21 pairs, and uses 15–3,036× fewer states than RPNI at ≥0.997 fitness. A fixed training corpus yields a unique FSM (Theorem 3), so re-extraction is exactly reproducible.

Why the Method Works: A Finite Activity Alphabet

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

1. Prefix tree (trie): all trajectories inserted; one state per unique prefix. Perfect fit, but O(total trace length) states. 2. Right-congruence merging: states merged by the activity of their incoming edge — all paths ending in bash collapse into one state, giving |A|+1 classes. Merging provably preserves fitness exactly (the key difference from RPNI, which must search over merge sequences). 3. Singleton filtering: transitions appearing only once in the corpus are deleted (unless they are a source state's only outgoing edge) — the one lossy step, and it's directly measurable.

The theoretical posture matters: Gold's 1967 theorem shows positive data alone cannot identify a target language — RPNI/EDSM/L* need negative examples or an oracle, but trace corpora contain only positives. The paper's workaround: abandon recovering the *generated language* and target the *direct-follow closure* instead — good-enough recovery rather than perfect recovery. Forty years of grammatical-inference theory applied to agent traces for the first time.

The Boldest Sentence in the Abstract

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

Evidence: on the three tau2-bench suites, the behavior of four models (GPT-4.1 / Claude 3.7 Sonnet / GPT-4.1-mini / o4-mini) is replayed by the same FSM at perfect fitness. Swap the model, the topology stays. What determines behavior structure is 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 converges with two other independent findings: structural modules living in code boundaries rather than context descriptions, and harness failures not propagating into model failures. All three point to one conclusion: the governable layer of agents is not inside the model — it's outside it. To constrain, monitor, or predict agent behavior, modifying the harness (tool surface + process) beats modifying the model, because the behavioral skeleton lives there.

Broader Implications

1. Inverse of "interfaces lose structure." Where structure typically gets flattened through narrow interfaces, this paper rebuilds topology from flattened 1D sequences — an inverse problem isomorphic to RVQ-grid/AR-decoder reconstruction pipelines. 2. A third form of experience carrier. After unstructured trajectory trails and code-solidified skills, the FSM is a third: topologically solidified experience (8,337 trajectories → 43 states) — and the only form that fits entirely into a monitoring dashboard. 3. A new floor for verification economics. LLM-as-judge costs one inference per trajectory; FSM monitoring is a table lookup, with cost trending to zero. Early stopping at 32% saves 68% of compute on doomed runs. The failure signal is cheap and counterintuitive: not trajectory content but per-state visit counts (failed SWE-agent trajectories loop around the edit tool ~8.4 times vs 5.1 for successes — failure is written in structure, not text). 4. A new direction for neurosymbolic work. Instead of giving symbolic structure to models, this extracts symbolic structure from model behavior — the interface is the trace corpus.

Honest Limitations (Acknowledged by the Paper)

The FSM accepts the direct-follow closure, not the agent's generated language: adversarial traces preserving bigram statistics can fool replay checks (the flip side of Theorem 3). Random single-symbol mutations are rejected 77–100%, but crafted adversarial samples are out of scope — the monitor is bypassable; don't use 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 is tested only on tau2-bench suites; cross-architecture and cross-domain transfer are unverified.
Only AWM is compared as a memory baseline; concurrent methods like ReasoningBank are not compared.
No GitHub repository (HF Space demo only) — reproduction requires your own implementation.

A Testable Prediction

Within 12 months, mainstream agent observability platforms (LangSmith / Langfuse / Braintrust types) will ship trace-to-FSM as a built-in panel. The construction is ~30 lines of code (prefix tree + merge + filter, hyperparameter-free), and the failure features are visit-count statistics — no moat anywhere. The only question is whether platforms are willing to expose the slightly uncomfortable fact that your agent's behavior has only 43 states.

---

*Source: arXiv 2608.23670v1 (HTML full text); OpenReview in-review version: openreview.net?id=1cprFkvFT0; demo: seonglae-agentstategraph.hf.space (Holistic AI / UCL / PUC-Rio). No GitHub code repository found. One minor wording discrepancy noted in fact-check: the paper's baseline is described as "vs 0.5 for flag-everything" rather than "random 0.5" — numerically identical.*