titleAutomata from Agent Traces: Failure and Next-Step Prediction
authorsSeonglae Cho, Franklin Cardenoso Fernandez, Umar Mohammed, Zekun Wu, Kleyton Da Costa, Ilham Wicaksono, Adriano Koshiyama
date2026-08-24
venuearXiv (preprint, not peer reviewed)
idarXiv:2608.23670
affiliationHolistic AI
upvotes6 (Hugging Face Daily Papers, 2026-11-01)
linksabs pdf hf
abstractLLM-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.

cite

@misc{cho2026automata,
  title={Automata from Agent Traces: Failure and Next-Step Prediction},
  author={Seonglae Cho and Franklin Cardenoso Fernandez and Umar Mohammed and Zekun Wu and Kleyton Da Costa and Ilham Wicaksono and Adriano Koshiyama},
  year={2026},
  eprint={2608.23670},
  archivePrefix={arXiv},
  url={https://arxiv.org/abs/2608.23670}
}