🤖 AI

Automata from Agent Traces: Failure and Next-Step Prediction

This paper proposes a method to collapse LLM agent execution traces into compact, model-agnostic finite-state machines that effectively capture shared behavioral topology, enabling superior next-step prediction and early failure detection for safety auditing and runtime monitoring.

Original authors: Seonglae Cho, Franklin Cardenoso Fernandez, Umar Mohammed, Zekun Wu, Kleyton Da Costa, Ilham Wicaksono, Adriano Koshiyama

Published 2026-08-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Seonglae Cho, Franklin Cardenoso Fernandez, Umar Mohammed, Zekun Wu, Kleyton Da Costa, Ilham Wicaksono, Adriano Koshiyama

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where artificial intelligence agents are no longer just chatbots that answer questions, but autonomous workers capable of solving complex problems on their own. These digital employees can browse the web, write and debug computer code, manage customer service inquiries, and even control desktop software. They operate by breaking down a large goal into a long chain of smaller steps, thinking through each one and taking action. However, as these agents become more capable, they also become harder to understand. Their internal decision-making processes are often a black box, and when they fail, it is difficult to tell if they are stuck in a loop, making a simple mistake, or wandering off into a chaotic path that leads nowhere. For companies and researchers deploying these systems, this opacity is a major safety risk. Without a clear map of how these agents behave, it is nearly impossible to catch errors before they cause damage or to predict when an agent is about to fail.

A team of researchers has developed a new way to map the behavior of these autonomous agents, turning their messy, unstructured actions into a clear, compact blueprint. Instead of trying to understand the complex reasoning inside the agent's brain, the researchers focused on the external trail of actions the agent leaves behind. They treated thousands of these action trails as a single dataset and asked a simple question: can we find a hidden structure that explains how these agents move from one step to the next? By analyzing the sequence of actions—such as searching for information, editing a file, or talking to a user—they discovered that despite the apparent randomness of the agents' choices, their behavior follows a surprisingly rigid and predictable pattern. The researchers built a finite-state machine, which is essentially a flowchart that captures every possible path an agent can take. This flowchart is not a guess; it is a mathematical reconstruction of the agent's actual behavior, distilled from real-world data.

The most striking discovery is how small and efficient these flowcharts are. Even for agents that perform thousands of different tasks, the researchers found that their behavior could be compressed into a map with only a handful of states, ranging from seven to forty-three distinct steps. This is a massive reduction in complexity. To put this in perspective, imagine trying to describe the entire layout of a sprawling city by listing every single street and building; the researchers instead found a way to describe the city's traffic flow using just a few major intersections and the rules for how cars move between them. In their tests, these compact maps were able to replay the agents' past actions with an AUC of 0.997. This high level of accuracy suggests that the structure of an agent's work is determined less by the specific language model powering it and more by the tools it is allowed to use and the tasks it is given.

This structural map does more than just describe the past; it serves as a powerful tool for predicting the future. Because the map captures the logical flow of the agent's work, it can be used to spot when an agent is going off the rails. The researchers showed that by watching an agent move through this map, they could predict whether a task would succeed or fail long before the task was finished. In some cases, the system could identify a failing run when the agent was only a quarter of the way through its work, allowing for early intervention. This is a significant improvement over previous methods that often waited until the end to judge success or failure. The map also proved better at predicting the next step an agent would take than other existing techniques, providing a clearer picture of what the agent is likely to do next based on where it currently is in its workflow.

The researchers tested their method on twelve different datasets covering a wide range of activities, from coding and web navigation to customer service and desktop management. In every case, the method produced a compact, reliable map that outperformed other approaches. Unlike older techniques that often created overly complex models with thousands of unnecessary states, or models that were too simple to be useful, this approach found the sweet spot. It created a model that was small enough to be fast and easy to analyze, yet detailed enough to capture the nuances of the agent's behavior. The construction of these maps was incredibly fast, taking only milliseconds to build, which means they could be used in real-time to monitor agents as they work.

The implications of this work extend beyond just making agents safer. By revealing that the behavior of these complex systems is governed by a simple, underlying structure, the researchers have provided a new way to audit and understand artificial intelligence. This structure is not dependent on the specific type of AI model being used; it holds true across different models and different types of tasks. This suggests that the constraints of the environment and the tools available to the agent are the primary drivers of its behavior, rather than the internal logic of the AI itself. For developers and safety auditors, this offers a practical, model-agnostic way to monitor agents, detect failures early, and ensure that these autonomous systems operate within safe and predictable boundaries. The work demonstrates that even the most complex and seemingly chaotic behaviors of modern AI agents can be reduced to a clear, understandable, and manageable set of rules.

Technical Summary: Automata from Agent Traces

Problem Statement

LLM-based agents execute complex, multi-step tasks by interleaving reasoning with tool calls, generating execution traces that are often long and unstructured. This opacity hinders safety auditing, debugging, and runtime monitoring. Existing approaches to behavioral analysis typically operate on a per-trace basis, rely on success-only filters, or require manual specification of workflows. Consequently, they fail to capture the shared cross-run topology that links next-step prediction with failure prediction. Furthermore, learning finite automata from positive examples alone is theoretically impossible in the limit (Gold, 1967; Angluin, 1980), and existing automata learning algorithms (e.g., RPNI, EDSM) often produce massive, overfitted state spaces when negative examples are unavailable.

The core challenge is to recover a compact, structural representation of agent behavior from a corpus of execution traces using only positive examples, enabling both predictive modeling and runtime safety monitoring without manual intervention.

Methodology

The authors propose a deterministic, hyperparameter-free construction of a Finite State Machine (FSM) from agent traces. The method leverages the observation that LLM agents operate within a bounded set of tools and actions, resulting in small activity alphabets (6–42 symbols) and strong sequential regularity.

1. Activity Extraction

Traces are converted into sequences of symbols from a finite alphabet $\mathcal{A}$ using a deterministic extraction function $\phi$ . The function prioritizes:

Tool calls: Extracting the function name.
Action tags: Extracting action labels (e.g., [ACTION]).
Command extraction: Extracting the first command token from code blocks.
If no rule matches, the activity defaults to a role-content type (e.g., assistant:text).

2. FSM Construction

The construction proceeds in three steps (Algorithm A.1):

Prefix Tree: All activity sequences are inserted into a trie. Each unique prefix represents a distinct state. This yields perfect training fitness but an $O(\sum T_i)$ state count.
Last-Activity Merge: States are merged based on a "last-activity right congruence." Two states $q$ and $q'$ are merged if the activity on the edge entering them is identical ( $\kappa(q) = \kappa(q')$ ). This reduces the state space to $|\mathcal{A}| + 1$ states (one per activity plus the initial state), creating a deterministic directly-follows automaton.
Rare-Transition Filtering: Transitions observed exactly once are removed unless they are the only continuation from their source state. This filters one-off digressions while preserving the core behavioral topology.

3. Theoretical Guarantees

Fitness Preservation: Theorem 2 proves that the merge operation preserves training fitness; any trace accepted by the prefix tree is accepted by the merged FSM.
Determinism and Compactness: Theorem 3 establishes that the resulting FSM is deterministic with $|\mathcal{A}| + 1$ states. The construction is a deterministic function of the corpus, ensuring reproducibility.
Convergence: Proposition 5 provides a convergence guarantee: given $N$ traces, the extracted FSM equals the population directly-follows automaton with high probability, provided transitions appear with a minimum frequency.

4. Prediction and Monitoring

Next-Step Prediction: Probabilities $P(a_t | q_t)$ are estimated from transition counts within the FSM states, smoothed via Laplace or absolute discounting.
Failure Prediction: The system extracts per-state features (visit frequency, message length, error rates) and trace-level anomaly features (cross-entropy, surprise). A gradient-boosted classifier uses these features to predict success/failure.
Runtime Monitor: An online monitor replays traces through the FSM, calculating metrics like "cycle rate" (frequency of revisiting states). It triggers early stopping when a trace deviates structurally from successful patterns (e.g., entering a tight loop), without requiring a trained ML model for the monitoring logic itself.

Key Results

The method was evaluated on twelve public datasets across eight agent domains (coding, web navigation, GUI, customer service, safety), with alphabet sizes ranging from 6 to 42 symbols.

Compactness and Fitness: The extracted FSMs are highly compact, containing only 7–43 states. They achieve test replay fitness $\ge 0.997$ on all datasets. Compared to the RPNI baseline, the method achieves compression ratios of 15 $\times$ to 3,036 $\times$ (e.g., reducing 59,510 RPNI states to 25 FSM states on SWE-agent).
Next-Step Prediction: FSM-state context outperforms Agent Workflow Memory (AWM) on all eight datasets where AWM was evaluated, with top-1 accuracy improvements ranging from +0.8pp to +25.3pp. Conditioning on FSM state reduces cross-entropy by 0.155 bits (21%) compared to raw context alone.
Failure Prediction: Per-state behavioral features achieve held-out AUROC up to 0.94 (tau2-bench telecom). The method lifts MLP, GRU, and Transformer baselines on 20 of 21 dataset-architecture pairs.
Runtime Efficiency: FSM construction completes in 1–110 ms (vs. 7,000–36,000 ms for RPNI). Per-trace replay takes 0.003–0.015 ms, enabling real-time monitoring.
Early Stopping: The online monitor can rank failing runs above passing ones at the 25% trace checkpoint (rank-AUROC 0.66) and trigger early stopping at 32% completion on SWE-agent, saving 68% of remaining compute.
Generalization: A single FSM built from traces of four different LLMs achieves 1.000 fitness on each model individually, indicating that the behavioral topology is shaped more by the deployment harness and tool constraints than by the specific LLM.

Significance and Claims

The paper claims that LLM agents, despite their apparent complexity, admit compact structural abstractions. The primary significance lies in providing a model-agnostic structural primitive that unifies four distinct tasks—workflow memory, next-step prediction, failure prediction, and runtime monitoring—into a single, hyperparameter-free construction.

Key claims include:

Structural Primacy: The behavioral topology is shaped more by the system (tools, prompts, task distribution) than by the LLM, allowing for model-invariant monitoring.
Tractability: The bounded activity alphabet of agents makes the problem of learning from positive examples tractable, yielding compact, interpretable FSMs that are statistically informative.
Efficiency: The method replaces four bespoke learned pipelines with one structural primitive that operates in milliseconds, making it suitable for deployment in safety auditing and runtime monitoring.
Interpretability: Unlike HMMs or large automata learners, the states in this FSM correspond directly to the last activity, allowing for per-state decomposition and interpretable failure mode analysis (e.g., identifying that failures often manifest as getting stuck in specific loops rather than exploring new states).

The authors note limitations, including that the FSM accepts the directly-follows closure of observed traces (not the generating language) and that the activity extraction function requires minimal domain knowledge. However, they emphasize that the structural constraints are robust across extraction granularities and that the approach offers a deployable substrate for safety and behavioral analysis.