Automata from Agent Traces: Failure and Next-Step Prediction
06:00 · August 26, 2026 · arXiv cs.AI RSS
LLM-based agents execute multi-step tasks, but their behavioral structure remains opaque: long unstructured traces resist the safety auditing and runtime monitoring that deployment requires. Existing approaches operate per-trace or success-only, so they miss the cross-run topology that links next-step and failure prediction. To recover that shared structure, we collapse an entire trace corpus into a single, compact finite-state machine (FSM) that serves as a structural substrate for the otherwise unpredictable behavior of LLM agents. Across twelve public datasets, the FSMs are compact (7-43 states), replay held-out data at >=0.997 fitness with near-identical topology across splits, and build in milliseconds. This substrate addresses both prediction goals. For next-step prediction, FSM-state context outperforms Agent Workflow Memory on every ground-truth-matched dataset. For failure prediction, per-state behavioral features reach held-out AUROC up to 0.94, and an online monitor ranks failing runs above passing ones from a partial trace, triggering early stopping well before completion. Behavioral topology thus appears shaped more by the deployment harness than by the LLM, providing a model-agnostic structural primitive for safety auditing and runtime monitoring.
Summary
LLM-based agents generate extended execution traces that interleave reasoning steps with tool calls, yet the underlying behavioral patterns remain difficult to inspect for safety auditing or runtime oversight. Existing techniques typically analyze traces individually or restrict attention to successful runs, overlooking the shared structure across multiple executions that could support both next-step forecasting and failure detection.
The proposed approach addresses this by distilling an entire corpus of traces into a single compact deterministic finite-state machine. An activity extraction function first maps each message to a symbol from a small alphabet of observed actions. A prefix tree is then constructed and merged according to the last activity, yielding a directly-follows automaton. Across twelve public datasets the resulting machines contain between 7 and 43 states, achieve fitness scores of at least 0.997 on held-out traces, and are produced in milliseconds. The same automaton remains stable across different training splits and across multiple underlying language models when the deployment harness is held constant.
This finite-state representation supplies a unified substrate for downstream tasks. Conditioning next-step predictions on the current FSM state improves cross-entropy over strong workflow-memory baselines on every matched dataset. For failure detection, simple per-state behavioral statistics reach held-out AUROC values up to 0.94 and enable an online monitor that ranks failing trajectories above successful ones from partial traces, permitting early termination well before task completion. The work indicates that the recovered topology is shaped primarily by the system prompt, tool set, and task distribution rather than by the choice of language model, offering a lightweight, model-agnostic primitive for monitoring autonomous agents.
Why it matters
This research is highly relevant for Dutch AI researchers and practitioners focusing on AI safety and compliance with the EU AI Act. The proposed FSM-based monitoring offers a transparent, model-agnostic tool for auditing LLM agents and ensuring reliable deployment in enterprise environments.
