Automata from Agent Traces

LLM-based agents are being deployed into production workflows at an accelerating pace, yet their internal behavior during multi-step tasks remains stubbornly opaque. Long, unstructured traces are a nightmare for safety auditing and runtime monitoring — they resist pattern extraction, and existing approaches only look at individual traces or success cases. A new paper from Cho et al. proposes something refreshingly different: collapse the entire trace corpus into a single compact finite-state machine (FSM) and use that structural substrate for prediction and monitoring.

The Problem

Agent traces are the breadcrumbs left behind as an LLM reasons, calls tools, and iterates. But these breadcrumbs are scattered across long, high-cardinality sequences. Traditional per-trace analysis misses the cross-run topology — the recurring structural patterns that link next-step prediction to failure prediction. You can't audit what you can't abstract, and you can't monitor what you can't predict.

The Method

The authors treat the problem as one of structure recovery. They collapse every trace across a corpus into a single FSM using standard grammatical inference — the algorithm builds states and transitions that capture the behavioral skeleton shared across runs. The result: compact automata (7-43 states per dataset) that replay held-out traces with >0.997 fitness, build in milliseconds, and show near-identical topology across train/test splits. This isn't training a model on traces — it's extracting the latent automaton the traces were generated from.

flowchart LR
    A[Raw Agent Traces] --> B[Grammatical Inference]
    B --> C[Compact FSM
7-43 States]
    C --> D[Next-Step Prediction]
    C --> E[Failure Prediction]
    C --> F[Online Monitor]
    E --> G[Early Stopping
AUROC up to 0.94]
            

The Results

The paper evaluates across 12 public datasets spanning diverse agent tasks. The numbers speak for themselves:

• Next-step prediction: FSM-state context outperforms Agent Workflow Memory (AWM) on every ground-truth-matched dataset — a strong baseline from prior work. The FSM captures state-dependent behavior that AWM's memory-augmented approach misses.
• Failure prediction: Per-state behavioral features achieve held-out AUROC up to 0.94. The online monitor — which only sees a partial trace — consistently ranks failing runs above passing ones, triggering early stopping well before task completion.
• Model-agnostic: Behavioral topology appears shaped more by the deployment harness (the environment, tools, and prompts) than by the underlying LLM. This means the same FSM-based monitoring works across GPT, Claude, Llama, or whatever comes next — a critical property as the model landscape shifts.
• Speed: The FSM builds in milliseconds on standard hardware. No GPU required.

Limitations

The FSM captures structure present in the trace corpus — if the harness changes (new tools, new prompts), the automaton needs rebuilding. The approach also assumes the harness state is the dominant driver of agent behavior, which may not hold for highly creative or open-ended tasks where the LLM's stochasticity dominates. And while the online monitor is effective, the paper notes that per-state features are coarse — they may miss subtle failure modes that only manifest across long-range dependencies spanning many states.

Why It Matters

We're past the point where agent behavior can be treated as a black box. Regulation, insurance, and enterprise adoption all demand auditable, monitorable systems. This paper provides a concrete, lightweight toolchain: take your traces, build an FSM, run predictions. It works because it's simple — grammatical inference has been studied for decades, and the authors show it maps perfectly onto the agent trace problem.

The model-agnostic result is the sleeper hit here. If agent behavior is mostly harness-shaped, then safety tools built on top of harness structure transfer across model generations. That's not just efficient — it's a foundation for building assurance cases that survive model updates.

For anyone deploying agents at scale: this is the kind of infrastructure you want in your observability stack before you need it.