The Opacity Problem

LLM-based agents execute multi-step tasks, but their behavioral structure remains opaque. Existing approaches operate per-trace or success-only, so they miss the cross-run topology (what one run shares with the next) that links next-step and failure prediction. Watch one agent work and you get a wall of text; watch a thousand and you get a machine, a search, edit, execute loop the agent never declares and the system prompt never specifies.

Yang and colleagues put LLM-based agents to work resolving GitHub issues (Yang et al., 2024, 2025). Others have them navigating websites (Zhou et al., 2024), operating desktops (Xie et al., 2024), driving mobile interfaces (Lu et al., 2025), managing customer service interactions (Yao et al., 2024), orchestrating multi-agent pipelines (Hong et al., 2024; Wu et al., 2023), and attributing the blame when one of those pipelines breaks down (Zhang et al., 2025). Following the ReAct pattern (Yao et al., 2023), they interleave chain-of-thought reasoning (Wei et al., 2022) with tool calls — and every run produces an execution trace of tool calls, natural language, and environment feedback.

This article recovers that machine. From nothing but the agent’s own execution traces — no labels, no task descriptions — we extract a compact finite-state machine, or FSM, of 7 to 43 states. That machine does the two things an operator actually needs: predict what the agent will do next, and catch a failing run before it wastes the compute.

The whole article follows one thread: heterogeneous agent traces pass through one deterministic abstraction $\phi$, pile up into a prefix tree, and collapse in a single classical merge into one automaton. That one object — not four bespoke pipelines — is then read four different ways: as workflow memory, a next-step predictor, a failure detector, and a runtime monitor.

A coding agent cycles through search, edit, execute. A customer service agent alternates between database queries and user communication. This structure emerges from the interaction between the system prompt, the available tools, and the task distribution — yet it’s nowhere written down.

Understanding this latent structure matters the moment you deploy: safety auditing has to verify that an agent visits the right states and avoids the attack chains that agent security benchmarks enumerate (H. Zhang et al., 2025), debugging means locating the bottleneck states where agents get stuck, and production monitoring flags behavioral drift before it costs anything.

Yet current agent analysis works at the level of a single trace (Z. Wu et al., 2025). Benchmarks such as AgentBench and AgentBoard score whether a run succeeded (Liu et al., 2024; Ma et al., 2024), and sandboxes such as ToolEmu probe what a run risks (Ruan et al., 2024). Neither offers a structural model of the behavior that links one run to the next.

The Inverse Problem

We frame behavioral recovery as an inverse problem: given a corpus of execution traces, reconstruct a finite-state machine that explains the observed behavior. Gold posed this as grammatical inference (Gold, 1967), Oncina and García later gave it a working algorithm (Oncina & Garcı́a, 1992), and de la Higuera surveys what the field settled on (de la Higuera, 2010). The classical setting assumes both positive and negative examples. Angluin’s alternative replaces the negatives with an oracle that answers membership queries (Angluin, 1987), and an execution log answers nothing. Agent traces give us positive examples only (the runs that happened) with no labeled counter-examples. Gold also proved that identifying the target language from positive examples alone is impossible in the limit (Gold, 1967).

A property specific to agents rescues the problem: unlike arbitrary regular languages, agent behavior is generated by a bounded set of tools and actions, so traces draw from a small activity alphabet, 6 to 42 symbols across our twelve datasets.

Twelve Datasets, Eight Domains

We evaluate on twelve public datasets spanning coding, web navigation, desktop GUI, desktop OS, mobile GUI, customer service, safety, and multi-agent coordination. The trace counts below are the trajectories we use in our experiments (from 184 to 8,337 each), not the size of each source corpus: for the largest sources we draw a fixed slice rather than the whole set.

Every dataset replays held-out traces at fitness of at least 0.997.

The three largest source datasets are subsampled to a fixed slice: SWE-agent uses 2,000 of the 80,036 available trajectories, Mind2Web (Deng et al., 2023) 500 of 2,350, and AgentNet 5,000 from the OpenCUA Ubuntu subset (Wang et al., 2025) — the other nine datasets are used in full.

From Traces to Symbols

An agent execution trace is a sequence of messages $\tau = (m_1, m_2, \ldots, m_T)$, where each message has a role (system, user, assistant, tool) and content. Step one maps each message to a symbolic activity from a finite alphabet.

Activity Extraction

An activity extraction function $\phi: m_t \mapsto a_t \in \mathcal{A}$ maps each message to a symbol, and it applies three rules in priority order: a message carrying a tool_call field takes the function name as its activity (bash, search_flight, click); content carrying an [ACTION] description tag takes the action label; and for agents that act through code blocks we take the first command token and map it to a semantic category (edit, search, navigate, execute). If no rule matches, the activity defaults to role:content_type, and assistant:text is the common case.

An Example

Consider a coding agent trace from SWE-agent (Yang et al., 2024) with 47 messages. The raw trace contains system prompts, file contents, error messages, and tool invocations. After extraction, the activity sequence is:

init → user → search → user → edit → user → execute → user → edit → user → submit

From 47 messages and thousands of tokens, we get the 11 symbols the FSM will model — drawn from an alphabet of 24 possible activities.

Replay any real trace symbol by symbol in the trace view.

Why This Works

These alphabets are small by construction, against the tens of thousands of symbols in natural language — that’s what keeps FSM extraction tractable.

Even a 42-tool telecom customer service agent (tau2-bench telecom (Barres et al., 2025)) needs only 43 states to capture its behavioral structure — the agent can only call the tools we gave it. So its capabilities stay bounded and so does its alphabet.

Building the Machine

Given a corpus of activity sequences, FSM construction is two steps and nothing else: build a prefix tree, then merge structurally equivalent states. There are no thresholds, no number of clusters, no learning rate.

Step 1: Prefix Tree

Insert all activity sequences into a trie — each unique prefix becomes a distinct state. The prefix tree has perfect training fitness, replaying every training trace exactly. But it can have tens of thousands of states.

For SWE-agent (2,000 traces), the prefix tree has 59,510 states. Most are visited once and represent memorized suffixes rather than reusable transition patterns.

Step 2: Structural Merging

Two states are structurally equivalent if for every activity $a \in \mathcal{A}$: (i) $\delta(q, a)$ is defined exactly when $\delta(q', a)$ is defined, and (ii) the targets are themselves equivalent — this recursion is computed bottom-up in a single pass.

The SWE-agent prefix tree with 59,510 states collapses to just 25 states — a 2,380$\times$ compression — and the resulting FSM still replays held-out traces at 0.999 fitness.

The Resulting FSM

The FSM $\mathcal{M} = (Q, \mathcal{A}, \delta, q_0)$ encodes the agent’s behavioral topology. Recurring patterns become loops. And the state count tracks the number of distinct behavioral modes.

In the tau2-bench retail and telecom customer service agents, a tool-call loop (assistant:tool_call to tool:text) dominates execution, with the conversational path through assistant:text as a separate branch. We find that in a coding agent the search, edit, execute cycle accounts for most of the trace.

Open the FSM explorer for any of the twelve datasets in the live dashboard.

Theoretical Properties

The construction guarantees three properties.

Fitness preservation. Structural merging preserves training fitness: if a trace is accepted by the prefix tree, it’s accepted by the merged FSM, because merging only adds out-edges — each state carries the union of its merged transitions.

Compactness. We find the merged FSM is a compact directly-follows automaton: one state per activity, deterministic, accepting every observed trace. We recover this — not the generating automaton, which is impossible to identify from positive examples alone (Gold, 1967). But it’s enough for faithful replay and prediction.

Linear runtime. Prefix tree construction is $O(\sum_i T_i)$, and structural merging is a partition refinement (Hopcroft et al., 2006) in $O(|Q_\mathcal{P}| \cdot |\mathcal{A}|)$. In practice all twelve datasets complete in under one second on a single CPU core.

Why the Machine Stays Small

A small state count alone doesn’t make a machine useful; an automaton can still be huge if the language is complex. And a huge automaton spreads its observations thinly (leaving every per-state statistic noisy). The FSM works as a substrate because it’s small, stable, and converges fast, so each state pools enough traces to estimate from. The prediction and monitoring chapters depend on that property, not the exact count.

It converges on a few percent of the data

Across five random train/test splits the extracted state count is identical every time, so the topology is a property of the agent, not of which traces you happened to sample. Replay fitness plateaus just as fast: within the first 1 to 10% of the training traces every dataset clears 0.95 fitness, and SWE-smith holds 0.9996 from the first 1%.

Three different methods agree

The compactness isn’t an artifact of our particular merge rule: three fundamentally different algorithms converge to nearly the same state count on every dataset: structural merging, ours, a structural partition; Alergia (Carrasco & Oncina, 1994), a statistical merge that lands within 1.0 to 6.0$\times$ of our own state count; and a hidden Markov model (HMM) (Rabiner, 1989), a probabilistic latent-state model that matches the count, though its states aren’t interpretable.

A structural, a statistical, and a probabilistic method all agree — which rules out an algorithmic coincidence.

Compression and Comparison

We compare against nine baselines: RPNI (Oncina & Garcı́a, 1992), EDSM (Lang et al., 1998), Alergia (Carrasco & Oncina, 1994) and k-Tails (Biermann & Feldman, 1972) from automata learning, run through AALpy (Muškardin et al., 2022); the HMM (Rabiner, 1989); the Alpha, Inductive and Heuristic miners from process mining (van der Aalst, 2016), run through PM4Py (Berti et al., 2019); and AWM, agent workflow extraction (Wang et al., 2024). All receive only the same positive training sequences, no failure labels.

How Much Smaller

Our FSMs achieve 15 to 3,036$\times$ compression over RPNI while replaying held-out traces at fitness of at least 0.997. The ratio grows with trace length and branching: 15$\times$ on WebArena (short web traces, where RPNI succeeds) up to 3,036$\times$ on GUI-Odyssey (Lu et al., 2025) (long, repetitive mobile-GUI traces, where RPNI’s prefix tree explodes to 21,255 states against our 7).

Compare all eight methods interactively in the baselines view, or watch structure stabilize in the convergence view.

Convergence and Stability

Replay fitness reaches its plateau well before the training set is exhausted: on SWE-agent it’s already at 0.985 within 1% of the training traces and settles at 0.996 by 10%, and the state count keeps inching up as rare command patterns appear. Structured tool-call domains converge fastest: SWE-smith holds 0.9996 from the first 1% of data. Open web and delegation traces take longer, with Mind2Web (Deng et al., 2023) needing 5% and Who&When (Zhang et al., 2025) 10% of their traces to clear 0.95 fitness.

Baselines at a Glance

• RPNI (Oncina & Garcı́a, 1992) without negative examples keeps large portions of the prefix tree (382 to 63,897 states) at degraded fitness.
• Alergia (Carrasco & Oncina, 1994), the strongest competitor, matches our fitness but uses 1.0 to 6.0$\times$ more states.
• HMM (Rabiner, 1989) matches our state count but produces non-interpretable latent states.
• EDSM (evidence-driven state merging) (Lang et al., 1998) without negatives collapses to a trivial 1-state acceptor.
• k-Tails made us pick $k$ ourselves, and at $k=1$ it produced 1.4 to 10$\times$ more states than ours (with state counts exploding past $k=2$).
• Process mining (van der Aalst, 2016) miners reach high fitness but precision 0.00 to 0.80, the “flower model” problem where every activity is reachable from every state.

Precision

The FSM is more than a vocabulary: it rejects every random trace, and at least 99.9% of permuted traces that keep the activity set but scramble the order. Even single-symbol mutations — a substitution or an insertion or an adjacent swap — are blocked 77 to 100% of the time. RPNI — with its thousands of states — accepts 75% of those same permuted traces on WebArena.

Prediction: Next Step and Failure

We find the same FSM state answers both questions an operator asks: what the agent will do next, and whether this run is heading for failure. Both read off the per-state transition distribution, which compactness makes reliable.

Next-Step Prediction

At each step the predictor estimates $P(a_t \mid \text{context})$, scored by cross-entropy in bits via 5$\times$5-fold cross-validation (CV). Conditioning on FSM state alone, with no learning beyond an order-1 Markov model, accounts for 83 to 99% of the total cross-entropy improvement on each dataset. We find the average drops to 0.93 bits, a 62% cut from the unigram baseline at 2.44 bits.

The cleanest test holds the predictor fixed and adds FSM state as a feature: under absolute discounting, FSM state conditioning adds +0.155 bits on average (0.580 vs 0.735) and helps on every one of six datasets, from +0.016 on SWE-agent to +0.364 on Mind2Web, whose branching web-action vocabulary gains most from knowing where in the workflow it is. We find that combining FSM state with a small learned model gives the best predictor in the study, at 0.73 bits.

Workflow Memory

The gain generalizes to the agent’s own LLM: feeding the current FSM state as context for choosing the next action beats Agent Workflow Memory (AWM) (Wang et al., 2024) on all eight ground-truth datasets, with six gaps significant at $p < 10^{-8}$.

The margin runs from +0.8 points on tau2-bench airline to +25.3 on SWE-smith — and it never reverses: on none of the eight does AWM come out ahead. Three of the eight gaps clear 15 points, and the two narrowest — airline at +0.8 and SWE-agent at +2.8 — are the two datasets where the agent already succeeds most often.

AWM extracts workflows from successful traces only, so on low-success datasets it has little to say — that’s exactly where the gap is widest.

Step through the workflow-memory comparison per dataset in the memory view.

Predicting Failure

Failure has mostly been studied after the fact: Who&When asks which agent and which step were to blame once a multi-agent run has already gone wrong (Zhang et al., 2025), and Trace treats the whole workflow as a differentiable graph to be optimised offline (Cheng et al., 2024). Ours is the earlier and cheaper question: with the run still going, does the machine already know?

Replay a trace through the FSM and read off per-state behavioral features (visit frequency, message-length statistics, error rate, early/late entropy drift) plus five cross-entropy anomaly features. A single gradient-boosted classifier on a fixed 80/20 split reaches held-out AUROC up to 0.94.

Failure prediction scales with machine size: more states give a finer map of where a run can go wrong. The 43-state telecom agent tops out at 0.941; WebArena (Zhou et al., 2024) (0.903) and AgentNet (X. Wang et al., 2025) (0.890) follow; SWE-agent (Yang et al., 2024) — with 25 states — reaches 0.799. ATBench, the only safety-labeled benchmark, reaches 0.894 (0.864 ± 0.024 under repeated CV). We see across all eight real-trace datasets the CV standard deviation stays in 0.012 to 0.031 — so these aren’t single-split artifacts.

Inspect per-state feature importances and failure modes in the failure view.

And the predictors are interpretable. On SWE-agent the single strongest feature is whether the trace reaches the submit state: 94.8% of successes get there, only 55.7% of failures do. And we find this isn’t a length proxy — structural features score 0.790 against 0.659 for trace length alone. Successful runs touch only 9 of 25 states along a focused search, edit, submit path — and failures spread across all 25 (Jaccard overlap 0.206).

Runtime Monitor

Deployed online (H. Wang et al., 2026; G. Zhang et al., 2026), a two-rule monitor fires when the cycle-rate exceeds 0.778 and the unique-state count clears a warm-up floor. On all four evaluated datasets it reaches rank-AUROC 0.66 at the 25% trace checkpoint, against 0.5 for a flag-everything baseline by construction. On SWE-agent it fires at 32% of trace completion, stopping the run before two-thirds of its remaining compute is spent, at precision 85.9% and recall 95.5%. By the halfway checkpoint, FSM features alone already recover 92% of the full-trace signal.

Watch the monitor flag a failing run in real time in the monitor view.

Discussion

When Does It Work?

A system’s action vocabulary is bounded, so its behavioral topology is bounded too, and a compact, stable automaton is the natural summary; beating four bespoke pipelines with it is a consequence, not a design goal.

The topology is also model-invariant: a single FSM achieves perfect fitness across four large language models on the same task, so what shapes it is the system, the tools and prompts and task distribution, more than the model driving it. It stays stable across extraction granularities too, shifting failure-prediction AUROC by less than 0.03 over four levels of $\phi$.

Related Work

Three lines of work touch this one.

State machines placed around agents. StateFlow runs an agent through a state machine somebody wrote by hand (Wu et al., 2024), a definite finite automaton can be bolted onto a chatbot pipeline the same way (Sun et al., 2024), FlowMind builds a workflow from an API surface (Zeng et al., 2024), and AFlow and ADAS search over agentic workflow designs (Hu et al., 2024; Zhang et al., 2025), while MetaAgent assembles a whole multi-agent system out of one (Chen et al., 2025). In every one of them the machine is an input — here it is an output, recovered from traces the agent had already produced. Experience kept as memory. Agent Workflow Memory induces reusable routines from past trajectories (Wang et al., 2024), Experience-to-Strategy trains a graph of them (Xia et al., 2025), ExpeL distils insights out of them (Zhao et al., 2024), and Voyager accumulates a skill library (G. Wang et al., 2023). Each of those keeps fragments of behavior. The automaton keeps the topology instead.

Automata learned from observation. Model learning turns a black-box system into a state machine (Vaandrager, 2017), Weiss and colleagues pull one out of a recurrent network with membership and equivalence queries (Weiss et al., 2018), DeepDFA learns one by gradient (Umili & Capobianco, 2024), prompt chaining extracts one from a flow description (Wael et al., 2025), and AALpy packages the classical algorithms (Muškardin et al., 2022). Process mining, which discovers process models from event logs, is the closest classical neighbour: van der Aalst’s textbook treatment (van der Aalst, 2016), its re-thinking for the agent era (Berti et al., 2024), an evaluation of large language models at the task (Berti, Kourani, et al., 2024), and skill learning from mined processes (Redis et al., 2024). This one works from a different input: positive traces only, no oracle to query, and an alphabet small enough that one merge suffices.

Limitations

The FSM accepts the observed prefix language, not the agent’s true generating language: like any trace-replay method, it can’t tell a trace that stays within the observed transition patterns from a legitimate one. The extraction function $\phi$ needs a small amount of per-domain knowledge — and fully automatic discovery of it is future work — failure prediction degrades on simpler machines: AUROC falls to 0.799 on SWE-agent and 0.70 on the 10-state SWE-smith — both are smaller task spaces, with less structure to exploit. Extending the workflow-memory comparison beyond AWM to other memory-injection methods is future work.

For agents with much larger action spaces or weaker sequential structure, the construction stays minimal but stops being compact — and the per-state observation density that drives every result above would degrade with it.

Broader Impact

Compact FSM representations make agent behavioral structure inspectable — and that supports safety auditing. The same analysis could be misused to find exploitable behavioral patterns, so deployment should restrict FSM analysis to authorized auditing.

Conclusion

A finite-state machine — built in milliseconds from positive examples with one classical merge — does the work of four bespoke learned pipelines. The same 7-to-43-state object serves all four.