Automata from Agent Traces: Failure and Next-Step Prediction

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.

한 줄 요약

LLM 에이전트의 실행 트레이스를 기반으로 생성된 FSM이 다음 단계 예측과 실패 예측 성능을 동시에 향상시킨다.

핵심 기여도

12개 공개 데이터셋에서 FSM이 7–43개의 상태로 구성되며, 재현 정확도는 0.997 이상이다.
다음 단계 예측에서 FSM 상태 정보가 Agent Workflow Memory를 모든 8개 데이터셋에서 상회한다.
실패 예측에서 AUROC 최대 0.94 달성, 25% 트레이스 시점에서 0.66의 rank-AUROC를 기록하며 조기 중단 가능.
기존 RPNI 기반 자동기계 대비 15–3,036배 더 적은 상태로 동일한 정확도를 달성.

핵심 아이디어

LLM 기반 에이전트는 복잡한 다단계 작업을 수행하지만, 그 행동 구조는 불투명하다. 기존 방법은 개별 트레이스 또는 성공 사례만을 기반으로 하여, 다음 단계와 실패 예측 간의 공통 구조를 포착하지 못한다. 본 연구는 전체 트레이스 코퍼스를 단일 FSM으로 압축하여, 에이전트의 예측 불가능한 행동에 구조적 기반을 제공한다. 이 FSM은 각 상태에서 행동 특성을 기반으로 실패 예측 모델을 학습하고, 다음 단계 예측을 위한 문맥 정보를 제공한다. 특히, FSM은 학습 하이퍼파라미터 없이 결정론적 알고리즘으로 생성되며, 동일한 FSM이 4개의 LLM 모델에서 모두 완벽한 정확도를 보인다.

기술적 접근법

**모델**: FSM (Deterministic Finite Automaton, DFA)
**알고리즘**: Prefix Tree를 마지막 활동으로 병합하여 직접적으로 연결된 FSM을 생성 (linear time)
**데이터**: 12개 공개 데이터셋 (Table 5 참조)
**하이퍼파라미터**: 없음. 유일한 설계 선택은 활동 추출 함수 (activity extraction function)
**비교 대상**: RPNI, EDSM, Alergia, k-Tails, HMM, 프로세스 마이닝, 워크플로우 추출 등 9개 baseline

주요 결과

**다음 단계 예측**: FSM 상태 정보가 Agent Workflow Memory를 모든 8개 데이터셋에서 상회 (p < 10⁻⁸)
**실패 예측**: AUROC 최대 0.94 달성, 25% 트레이스 시점에서 rank-AUROC 0.66 (기준선 0.5)
**압축 성능**: RPNI 대비 15–3,036배 적은 상태 수로 0.997 이상의 정확도 유지
**재현 정확도**: 0.997 이상, train/test 분할 간 구조 변동이 거의 없음

의의 및 한계

**의의**: FSM은 LLM 에이전트의 행동 구조를 모델에 독립적인 방식으로 추출하여, 안전 감사와 런타임 모니터링에 활용 가능하다.
**한계**: 실패 예측은 특정 상태의 행동 특성에 의존하며, 복잡한 다중 에이전트 상호작용 환경에서는 제한적일 수 있다. 또한, FSM은 긍정적 예시만을 기반으로 생성되므로, 부정적 예시를 통한 정밀도 향상이 필요할 수 있다.

실용적 활용

소프트웨어 개발 에이전트(SWE-agent)의 런타임 모니터링 및 조기 실패 탐지
고객 서비스, 웹 탐색, 데스크탑 환경 조작 등 복잡한 작업 수행 시 안전 감사 도구로 활용 가능
모델 독립적 구조 추출을 통해 다양한 LLM 기반 시스템에 적용 가능