Automata from concurrent structural substrate for LLM agents

The Problem

LLM-based agents today tackle everything from software engineering to customer service, yet their internal behavioral structure remains frustratingly opaque. As these agents grow more autonomous—resolving GitHub issues, navigating websites, managing customer interactions—the risk of undetected failures scales with their autonomy. The core problem is that execution traces are long, unstructured sequences that resist the safety auditing and runtime monitoring required for real-world deployment.

Existing approaches operate at the individual trace level, focusing either on success-only patterns or per-trace analysis. This means they miss the cross-run topology—the shared structural patterns that link next-step predictions and failure detection across multiple runs. Without recovering this shared structure, auditors and operators are left working with fragmented, unpredictable views of agent behavior.

How It Works (The Technical Mechanics)

The paper's central innovation collapses an entire corpus of agent traces into a single, compact finite-state machine (FSM). Think of this as building a "behavioral map" that captures the essential topology of how an agent moves through different activities during task execution.

The construction follows three deterministic, hyperparameter-free steps:

1. Prefix tree construction: All activity sequences are inserted into a trie (tree structure), where each unique prefix becomes a distinct state. This step alone creates a structure with perfect training fitness but potentially thousands of states.

2. Merge by last activity: States reached by the same "last activity" are merged together. This uses what the authors call "last-activity right congruence"—essentially grouping states that see the same activity as their most recent step. This collapses the potentially massive trie into a much smaller directly-follows automaton.

3. Rare-transition filtering: Transitions observed only once in the corpus are dropped (unless they're the only continuation from a state). This cleanup step removes idiosyncratic digressions while preserving the core behavioral topology.

The result: across twelve public datasets, the resulting FSMs contain only 7–43 states (compared to hundreds or thousands for baseline methods), replay held-out data with ≥0.997 fitness, and construct in milliseconds. The method requires no learning hyperparameters—the only design choice is the activity extraction function, which maps raw trace messages to activity symbols via rules like "if a message contains a tool call, the activity is the function name."

A crucial insight: behavioral topology appears shaped more by the deployment harness (the system prompt, available tools, task distribution) than by the specific LLM model. This makes the FSM model-agnostic—a single automaton built from traces of four different LLM models achieved perfect fitness on each individual model.

Key Results & Benchmarks

Compression and Efficiency

The FSM achieves extraordinary compression ratios: 15–3,036× fewer states than RPNI (a baseline automata learning method) while maintaining ≥0.997 test fitness. On the largest dataset (GUI-Odyssey with 7,735 traces), the FSM has only 7 states versus RPNI's 21,255. Construction completes in 1–110 ms across all datasets, versus 7,000–36,000 ms for RPNI—a speedup of 328–10,611×. Per-trace replay is nearly instantaneous (0.003–0.015 ms), enabling real-time monitoring.

Next-Step Prediction

The FSM serves as an effective context predictor. Without any learned parameters, the order-1 FSM conditioning achieves an average cross-entropy of 0.93 bits across five datasets—a 62% reduction from the Unigram baseline (2.44 bits). Conditioning on the FSM state rather than just activity frequencies accounts for 83–99% of the total improvement from uniform activity frequencies to the best method on each dataset. Even when combined with learned models (MLP, GRU, Transformer), FSM state conditioning provides consistent lifts: the best combined approach achieves 0.73 bits average cross-entropy.

Critically, FSM-state context outperforms Agent Workflow Memory (AWM) on every dataset. AWM extracts linear workflows from successful traces only, while the FSM captures the full behavioral topology including failures and branching. The FSM's minimal context format (natural-language next-action probabilities plus top-15 multi-step continuations) achieves 65.1% top-1 accuracy on tau2-bench retail versus AWM's 52.9%.

Failure Prediction

For failure prediction, per-state behavioral features reach held-out AUROC up to 0.94. Key results include:

• On tau2-bench telecom (43 states), features achieve 0.941 held-out AUROC
• On WebArena (24 states): 0.903
• On AgentNet (24 states): 0.890
• On ATBench (safety benchmark, 14 states): 0.894

An online monitor that ranks failing runs above passing ones from partial triggers early stopping well before completion. At the 25% trace checkpoint, the monitor achieves rank-AUROC 0.66 versus 0.5 for a "flag-everything" baseline. On SWE-agent, it triggers early stopping at 32% mean trace completion, saving 68% of remaining compute while maintaining 85.9% precision and 95.5% recall. At a high-precision operating point (cycle-rate >0.957), the monitor achieves 100% precision (zero false alarms) while catching 11.3% of failures.

The paper demonstrates that FSM features outperform raw trace statistics: structural features reach AUROC 0.790 on SWE-agent versus 0.659 for length alone, confirming that the predictive signal is structural rather than a simple length proxy. The discriminative quotient (FSM-D) variant, which uses training-free KL divergence between success and failure outgoing transition distributions, lifts AUROC by +0.06 to +0.15 on five of nine datasets.

Why It Matters (Key Takeaways)

1. One substrate for multiple safety tasks: The same compact FSM underpins workflow memory, next-step prediction, failure prediction, and runtime monitoring. This replaces four bespoke learned pipelines with one structural primitive, significantly reducing engineering overhead and improving consistency across safety tools.

2. Early failure detection before completion: The runtime monitor can identify failing runs at just 32% trace completion on SWE-agent, saving 68% of compute. At high precision (0.957 threshold), it achieves 100% precision (zero false alarms), making it suitable for automated intervention like agent reset. This early-stopping capability could significantly reduce costs for expensive LLM inference.

3. Model-agnostic structural primitives: The FSM's topology is shaped by the deployment harness rather than the specific LLM. A single FSM built across four different LLM models achieved perfect fitness on each individually, and per-state failure prediction features transfer across models with 0.786 mean cross-AUROC (vs. 0.877 self-AUROC). This means the same behavioral substrate works across model versions and families without retraining.

4. Behavioral regularity beneath apparent complexity: Despite the apparent complexity of multi-step LLM agent tasks, the traces exhibit strong sequential regularity—conditioning on the immediately preceding action reduces entropy by 51–80%. This regularity makes compact FSMs possible: even on datasets with 42 activity symbols, the FSM converges to just 43 states with near-perfect fitness.

What to watch for: The FSM captures the directly-follows closure of observed traces, not the agent's full generating language. Adversarial traces preserving activity bigram statistics can replay through the FSM. The activity-extraction function requires minimal domain knowledge but is dataset-specific. On smaller-alphabet datasets (|A| ≤ 4), the FSM becomes too coarse for effective monitoring, suggesting an optimal range of activity granularity for practical deployment.

The paper concludes that despite LLM agents' apparent complexity, they admit compact structural abstractions—a deployable substrate for safety auditing, runtime monitoring, and behavioral analysis that works across model families and task domains.