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 three of the sources we draw a fixed slice rather than the whole set.

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

Three 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-activity 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 it was given. So its capabilities stay bounded and so does its alphabet.

Building the Machine

Given a corpus of activity sequences, construction is a prefix tree, a merge on the incoming activity, then a prune of transitions seen exactly once unless they are a state’s only exit. There are no thresholds to tune, 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.

The trie gives every distinct prefix its own state, so it grows with total trace length rather than with behavior. Most of those states are visited once and memorize a suffix instead of capturing a reusable transition.

Step 2: Structural Merging

Merge every state whose incoming edge carries the same activity. Writing $\mathrm{last}(x)$ for the activity on the edge into $x$, the relation is $x \equiv y \iff \mathrm{last}(x) = \mathrm{last}(y)$, with the empty prefix as its own class. One pass, no recursion, and at most $|\mathcal{A}|+1$ classes, so the state count is bounded by the alphabet.

SWE-agent collapses to 25 states, one per activity plus the initial state, and still replays held-out traces at 0.999 fitness. Alergia, the strongest method that also learns from positive examples alone, needs 35 for the same corpus.

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 activities.

In the tau2-bench airline customer service agent at role level, a tool-call loop (assistant:tool_call to tool:text) dominates execution, with the conversational path through assistant:text as a separate branch. 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. The merged FSM is a compact directly-follows automaton: one state per activity, deterministic. Pruning the single-observation transitions is the one step that can cost fitness, and the replay numbers measure that cost directly. 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 alphabet 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 random train/test splits the extracted state count stays within a few states of the full-data value, 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 with a convergence run clears 0.95 fitness, and SWE-smith holds 0.9996 from the first 1%.

Two other methods back the count

The compactness isn’t an artifact of our particular merge rule: Alergia (Carrasco & Oncina, 1994), a statistical merge, lands within 1.0 to 6.0$\times$ of our own state count on every dataset, and a hidden Markov model (HMM) (Rabiner, 1989) given the same number of states achieves comparable fitness, though its states aren’t interpretable.

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 but AWM receive only the same positive training sequences, with no failure labels; AWM needs success labels, so it runs on the labeled datasets only.

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 multi-agent 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.2 to 10$\times$ more states than ours, and the counts explode from $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 382 states — accepts 75% of those same permuted traces on WebArena.

Prediction: Next Step and Failure

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. 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. 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 four of the eight gaps clear 15 points. The retail row is the set the FSM context format was selected on; the other seven are held out, and the margin averaged over them is the larger of the two.

AWM extracts linear workflows from successful traces only, and it cannot represent cycles or branching.

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.

The largest machine predicts best and the smallest predicts worst: the 43-state telecom agent tops out at 0.941, and the 10-state SWE-smith sits lowest. In between, size stops explaining the order. WebArena (Zhou et al., 2024) (0.903), AgentNet (X. Wang et al., 2025) (0.890) and SWE-agent (Yang et al., 2024) (0.799) all have 25 states and span a tenth of AUROC, and ATBench, the only safety-labeled benchmark, reaches 0.894 on 15 (0.864 ± 0.024 under repeated CV). 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 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), 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 with about two-thirds of its compute unspent, 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 survives a coarser $\phi$ too: the default level matches or beats role-only on ten of the twelve datasets, moving more only where role-only collapses to three symbols or fewer.

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 directly-follows closure of the observed traces, not the agent’s generating language: like any trace-replay method, it cannot tell an adversarial trace that preserves the observed transition statistics 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. Only the extremes of machine size track prediction quality: the 10-state SWE-smith is lowest and the 43-state telecom highest, while three datasets at 25 states span a tenth of AUROC, so size does not order the middle. 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 still applies 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.