Automata from Agent Traces: Failure and Next-Step Prediction
cs.AI, cs.CL, cs.LG
Submitted: 2026-08-24
Updated: 2026-08-24
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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.
Terminology
Abstract
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.
Sources
- Process Mining for Python (PM4Py): Bridging the Gap Between Process- and Data Science
- SentinelAgent: Graph-based Anomaly Detection in Multi-Agent Systems
- AgentMonitor: A Plug-and-Play Framework for Predictive and Secure Multi-Agent Systems
- PrefixGuard: Online Failure Warning and Trace-Grounded Diagnosis for LLM Agents
- ATBench: A Diverse and Realistic Agent Trajectory Benchmark for Safety Evaluation and Diagnosis
- TraceAegis: Securing LLM-Based Agents via Hierarchical and Behavioral Anomaly Detection
- ReasoningBank: Scaling Agent Self-Evolving with Reasoning Memory
- AgentSpec: Customizable Runtime Enforcement for Safe and Reliable LLM Agents
- ProbGuard: Proactive Runtime Monitoring for LLM Agent Safety via Probabilistic Prediction
Related papers
- MAVEN-T: Reinforced Heterogeneous Distillation for Real-Time Multi-Agent Trajectory Prediction
- Model Discovery Agent: LLM-assisted Bayesian experiment design for data-efficient discovery of mechanistic world models
- The Clinician's Veto: Navigating Trust, Liability, and Uncertainty in Autonomous AI Prescribing
- MindHelper: Closed-Loop Embodied Mental-State Reasoning for Precision Intervention
- Incumbent Advantage: Brand Bias and Cognitive Manipulation Dynamics in LLM Recommendation Systems
- VSAL: A Vision Solver with Adaptive Layouts for Graph Property Detection