# Automata from Agent Traces: Failure and Next-Step Prediction

DevFeed: [Automata from Agent Traces: Failure and Next-Step Prediction](<https://devfeed.tech/articles/automata-from-agent-traces-failure-and-next-step-prediction-131960.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2608.23670>)

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

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>)

Topics: [Finite-state machine](<https://devfeed.tech/topics/finite-state-machine.md>), [agent observability](<https://devfeed.tech/topics/agent-observability.md>), [LLM observability](<https://devfeed.tech/topics/llm-observability.md>), [Multi-step AI processes](<https://devfeed.tech/topics/multi-step-ai-processes.md>)

Tags: [agent](<https://devfeed.tech/tags/agent.md>), [auditing](<https://devfeed.tech/tags/auditing.md>), [behavior](<https://devfeed.tech/tags/behavior.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-cl](<https://devfeed.tech/tags/cs-cl.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [datasets](<https://devfeed.tech/tags/datasets.md>), [deployment](<https://devfeed.tech/tags/deployment.md>), [failure](<https://devfeed.tech/tags/failure.md>), [finite-state](<https://devfeed.tech/tags/finite-state.md>), [finite-state-machine](<https://devfeed.tech/tags/finite-state-machine.md>), [model-agnostic](<https://devfeed.tech/tags/model-agnostic.md>), [monitor](<https://devfeed.tech/tags/monitor.md>), [monitoring](<https://devfeed.tech/tags/monitoring.md>), [next](<https://devfeed.tech/tags/next.md>), [prediction](<https://devfeed.tech/tags/prediction.md>), [runtime-monitoring](<https://devfeed.tech/tags/runtime-monitoring.md>), [safety](<https://devfeed.tech/tags/safety.md>), [structure](<https://devfeed.tech/tags/structure.md>), [topology](<https://devfeed.tech/tags/topology.md>), [traces](<https://devfeed.tech/tags/traces.md>)

## AI overview

The paper compresses agent trace corpora into compact finite-state machines (FSMs) to support both next-step and failure prediction. Across twelve public datasets, the FSMs had 7-43 states, replayed held-out traces with at least 0.997 fitness, showed near-identical topology across splits, and built in milliseconds. FSM-state context outperformed Agent Workflow Memory on every dataset with matched ground truth. Per-state behavioral features reached held-out AUROC up to 0.94; an online monitor ranked failing runs above passing ones using partial traces and could trigger early stopping. The authors report that behavioral topology appears more shaped by the deployment harness than by the LLM. These findings suggest a model-agnostic structure for auditing and runtime monitoring; the supplied abstract does not provide implementation details or broader evaluation limits.

## Source excerpt

arXiv:2608.23670v2 Announce Type: replace 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.