LLM‑based agents generate long, unstructured traces when carrying out multi‑step tasks, which hampers safety auditing and runtime monitoring. Existing methods typically operate on single traces or only on successful runs, missing the cross‑run topology that can support both next‑step and failure prediction. To address this gap, we collapse an entire trace corpus into a compact finite‑state machine (FSM) that serves as a structural substrate for the otherwise unpredictable behavior of LLM agents.
Across twelve public datasets, the resulting FSMs contain only 7–43 states, replay held‑out data with a fitness of 0.997, exhibit near‑identical topology across splits, and are built in milliseconds. This substrate serves two prediction goals. For next‑step prediction, using FSM‑state context outperforms Agent Workflow Memory on every ground‑truth‑matched dataset. For failure prediction, per‑state behavioral features achieve held‑out AUROC up to 0.94, and an online monitor ranks failing runs above passing ones from a partial trace, enabling early stopping well before completion.
The results suggest that behavioral topology is shaped more by the deployment harness than by the LLM itself, offering a model‑agnostic structural primitive for safety auditing and runtime monitoring.
Blogger's Review: This study convincingly shows that FSM abstraction can capture cross‑run behavior patterns, providing a practical tool for improving the interpretability and safety of LLM agents, and merits further exploration in real‑world deployments.