Automata from Agent Traces: Failure and Next-Step Prediction

3줄 요약

1. Holistic AI와 UCL 연구진이 2026년 8월 24일 arXiv에 올린 논문이다. LLM 에이전트가 남긴 실행 로그 뭉치를 통째로 하나의 유한 상태 기계(FSM)로 접어, 에이전트 행동의 구조를 복원할 수 있는지 확인한다.
2. 열두 개 공개 데이터셋에서 뽑아낸 FSM은 상태가 7개에서 43개뿐이고, 학습에 쓰지 않은 로그를 0.997 이상의 재현 적합도로 다시 돌린다. 만드는 데 밀리초가 걸리며 조정할 하이퍼파라미터가 없다.
3. 이 한 대의 기계가 워크플로우 메모리, 다음 행동 예측, 실패 예측, 실시간 감시를 모두 떠맡는다. 그리고 만들어진 상태 위상은 LLM을 바꿔도 거의 그대로여서, 구조를 정하는 쪽은 모델이 아니라 배포 하네스라는 결론이 따라 나온다.

문제 설정

LLM 에이전트는 여러 단계를 밟아 일을 처리하지만, 그 행동이 어떤 구조를 따르는지는 어디에도 적혀 있지 않다. 코딩 에이전트는 검색에서 편집으로, 편집에서 실행으로 돈다. 고객 응대 에이전트는 데이터베이스 조회와 사용자 대화를 번갈아 한다. 이 패턴은 시스템 프롬프트, 주어진 도구, 과제 분포의 상호작용에서 저절로 생겨나는 것이고 명세로 존재하지 않는다.

기존 접근은 로그 한 건 단위로 보거나 성공한 로그만 걸러 본다. 그래서 여러 실행에 걸쳐 공유되는 위상, 즉 다음 행동 예측과 실패 예측을 하나로 잇는 그 구조를 놓친다는 것이 저자들의 진단이다.

저자들은 이것을 역문제로 다시 쓴다. 실행 로그 뭉치가 주어졌을 때, 관측된 행동을 설명하는 유한 상태 기계를 되찾는 문제다. 골드의 정리에 따르면 긍정 예시만으로 목표 언어를 식별하는 일은 원리적으로 불가능하다. 로그는 전부 긍정 예시다. 여기서 저자들이 붙잡은 관찰은 이렇다. 에이전트의 행동은 정해진 도구 집합에서 나오므로, 로그를 기호로 바꾸면 알파벳이 작다. 열두 데이터셋 모두 6개에서 42개 사이였다.

상태 기계를 만드는 법

세 단계로 끝난다.

1. 접두사 트리: 모든 활동 열을 트라이에 넣는다. 학습 데이터에 대한 적합도는 완벽하지만 상태 수가 로그 길이의 합만큼 늘어난다.
2. 마지막 활동으로 병합: 들어오는 간선의 활동이 같은 상태를 전부 하나로 합친다. 이 합동 관계가 만드는 동치류는 알파벳 크기 더하기 1개뿐이다. 그래서 상태 수가 곧바로 알파벳 크기로 떨어진다.
3. 희귀 전이 제거: 전체 로그에서 딱 한 번 관측된 전이를 지운다. 단 그 상태의 유일한 후속이면 남긴다. 상태는 하나도 줄지 않고 일회성 곁길만 사라진다.

활동 추출은 도구 호출 이름, 액션 태그, 명령어 토큰 순으로 규칙을 적용하고, 어느 것도 걸리지 않으면 역할과 내용 유형을 붙여 기호로 삼는다.

저자들은 두 정리를 붙여 둔다. 병합은 학습 적합도를 보존하고(정리 2), 결과 FSM은 결정적이며 상태 수가 알파벳 크기에 1을 더한 값이고 같은 데이터에서 다시 뽑으면 정확히 같은 기계가 나온다(정리 3). 되찾는 것은 관측된 로그의 directly-follows 오토마타이지 에이전트를 생성한 오토마타가 아니라는 점도 분명히 밝힌다.

수렴 보장도 있다. 각 전이가 최소 확률 p로 등장한다면, 로그 N개면 전체 전이를 다 보게 될 확률이 원하는 만큼 높아진다. SWE-agent의 전이 51개 기준으로 690개면 충분하다는 계산인데, 실제로는 학습 데이터의 5%에서 15%만 써도 적합도 0.99에 닿았다.

얼마나 작아지는가

라벨이 붙은 실제 로그 데이터셋 여덟 개의 결과다. RPNI는 고전적인 오토마타 학습 알고리즘이고, Alergia는 긍정 예시만 쓰는 경쟁자 중 가장 강했다.

RPNI는 여덟 중 일곱에서 120초 예산을 넘겼다. 라벨 없는 데이터셋까지 포함하면 압축비는 GUI-Odyssey에서 3,036배까지 올라간다.

작다고 헐거운 것은 아니다. 무작위로 만든 로그는 100% 거부하고, 실제 로그의 순서만 섞은 로그도 99.9% 이상 거부한다. 기호 하나만 바꾼 변형도 77%에서 100% 사이로 거부한다. 반면 RPNI는 WebArena에서 순서를 섞은 로그의 75%를 받아들인다. 프로세스 마이닝 계열 기법의 정밀도는 0.00에서 0.80 사이에 흩어졌다.

구축 시간은 1밀리초에서 110밀리초. RPNI는 7초에서 36초가 걸렸다. 로그 하나를 다시 돌리는 데 0.003밀리초에서 0.015밀리초다.

다음 행동 예측

FSM의 현재 상태만 알면 다음 활동의 확률 분포가 전이 횟수에서 바로 나온다. 학습이라고 부를 것이 없는 1차 마르코프 추정인데, 교차 엔트로피 평균 0.93비트를 기록했다. 활동 빈도만 쓰는 유니그램(2.44비트) 대비 62% 감소다. 균등 분포에서 최고 성능까지 이르는 전체 개선폭의 83%에서 99%가 이 한 걸음에서 나왔다.

같은 조건을 맞춘 소거 실험에서, 원문 맥락에 FSM 상태를 더하면 0.155비트(21%)가 더 줄었다. 여섯 데이터셋 전부에서 개선됐다. 반대로 RPNI는 평균 3.40비트로 유니그램보다도 나빴다. 수만 개 상태로 쪼개 놓으니 상태마다 관측이 몇 건 없어 확률 추정이 무너진 것이다.

흥미로운 대목은 이 FSM을 LLM의 프롬프트 맥락으로 넣었을 때다. 비교 대상은 성공한 로그에서 선형 워크플로우를 뽑는 Agent Workflow Memory(AWM)다. gpt-4.1-mini를 판정자로 두고 top-1 정확도를 재면, 여덟 데이터셋 전부에서 FSM이 앞섰다.

성공률이 낮은 데이터셋에서 격차가 크게 벌어진다. AWM은 성공한 로그에서만 워크플로우를 뽑기 때문에 그런 데이터셋에서는 참고할 재료 자체가 모자란다.

여기에 저자들이 정직하게 덧붙인 조건이 하나 있다. 이 우위는 자동으로 얻어지지 않는다. 같은 FSM을 어떤 형식으로 프롬프트에 넣느냐에 따라 결과가 크게 갈렸다.

상태와 전이를 전부 나열한 형식은 AWM보다도 못했다. 현재 상태에서 이어질 행동의 확률과 후속 몇 개만 자연어로 보여 준 최소 형식이 이겼다. 구조 모델에 맞는 최소 맥락을 찾아내는 일 자체가 기여의 일부라고 저자들은 적어 두었다.

실패 예측과 조기 종료

로그를 FSM에 다시 흘려 보내면 상태별 특징이 나온다. 방문 빈도, 메시지 길이, 오류율, 시간 특징, 그리고 교차 엔트로피 기반 이상 신호 다섯 가지다. 이것을 경사 부스팅 분류기 하나에 넣은 결과가 홀드아웃 AUROC 최대 0.941(tau2 통신)이었다. WebArena 0.903, AgentNet 0.890, 안전 라벨이 붙은 ATBench 0.894, SWE-agent 0.799. 상태 수가 많은 FSM일수록 잘 맞혔다.

재현 적합도 자체는 아무 정보가 없다(AUROC 0.50 근처). 구조가 아니라 길이만 봐도 되는 것 아니냐는 의심에도 답을 준비해 두었다. SWE-agent에서 길이만 쓰면 0.659, 구조 특징을 쓰면 0.790이다.

실패 로그의 모양은 성공 로그와 눈에 띄게 다르다. SWE-agent에서 성공한 로그는 25개 상태 중 9개만 밟고 검색에서 편집을 거쳐 제출로 간다. 실패한 로그는 25개 전부를 헤맨다. 두 집합의 자카드 계수가 0.206이다. 제출 상태에 도달했는지 여부가 가장 강한 예측자였다(성공의 94.8%, 실패의 55.7%).

실패의 진행 방식도 조사했다. SWE-agent 실패 1,329건 중 1,292건, 즉 97%가 점진적 악화 없이 갑자기 발생한다. 성공과 실패의 상태 분포가 처음 갈라지는 지점은 로그 길이의 8.7% 지점이다. 그러니 감시는 성능이 서서히 떨어지는 것을 추적할 것이 아니라 특정 상태 패턴을 잡아야 한다는 결론이 나온다.

그래서 만든 것이 규칙 두 개짜리 온라인 감시기다. 순환률이 0.778을 넘는지, 방문한 고유 상태 수가 최소치에 못 미치는지. 학습된 모델은 하나도 쓰지 않고 FSM 재현만 한다(단계당 0.006밀리초).

아래 두 줄이 실패한 자리라는 것을 저자들도 그대로 적었다. 알파벳이 작은 데이터셋에서는 FSM이 너무 성겨서 순환률로 실패 유형을 가르지 못하고 감시기가 과하게 발동한다. 쓸 수 있는 구간은 상태가 충분히 다양한 경우이고, 그 밖에서는 데이터셋별 규칙 조정이 필요하다는 것이다.

임계값을 0.957까지 올리면 SWE-agent에서 정밀도 100%에 재현율 11.3%가 된다. 오경보가 한 건도 없으니 에이전트를 자동으로 되돌리는 용도로 쓸 수 있고, 임계값 0.750에서는 실패의 85.2%를 86.4% 정밀도로 잡아 사람에게 알리는 용도가 된다.

위상을 정하는 쪽은 모델이 아니다

tau2-bench에는 같은 과제를 GPT-4.1, Claude 3.7 Sonnet, GPT-4.1-mini, o4-mini 네 모델이 수행한 로그가 들어 있다. 네 모델 로그를 합쳐 만든 FSM 한 대가 각 모델의 로그를 적합도 1.000으로 재현했다. 모델별로 따로 만든 FSM들도 상태 어휘가 거의 같고 지배적인 전이 골격의 80%에서 92%를 공유한다. 실패 예측 특징의 교차 이전은 평균 AUROC 0.786으로, 자기 모델에서의 0.877에 크게 못 미치지는 않았다.

활동 추출 규칙을 바꿔도 결과가 거의 흔들리지 않는다. 열두 데이터셋 중 열 개에서 기본 세밀도가 더 거친 역할 단위와 같거나 나았고, 예외는 역할만 쓰면 기호가 세 개 이하로 무너지는 데이터셋들이었다.

여기서 논문의 표제 주장이 나온다. 에이전트 행동의 위상은 모델보다 시스템 쪽에서 온다. 어떤 도구를 주었고 시스템 프롬프트를 어떻게 썼는지가 상태 그래프의 모양을 정하고, 그 안에서 어떤 LLM이 돌아가는지는 위상을 바꾸지 않는다.

한계

FSM이 받아들이는 것은 관측된 로그의 directly-follows 폐포이지 에이전트의 생성 언어가 아니다. 활동 바이그램 통계를 유지하는 적대적 로그는 그대로 통과한다. 활동 추출 함수는 데이터셋마다 손으로 정해야 하고, 그 자동 발견은 향후 과제로 남겼다. 모델 간 이전은 tau2-bench 세 개 도메인에서만 측정했다. 워크플로우 메모리 비교 대상도 AWM 하나뿐이며, 성공과 실패를 함께 쓰는 ReasoningBank 같은 동시기 방법과는 비교하지 않았다.

행동 공간이 훨씬 크거나 조건부 구조가 약한 에이전트에서는 같은 구축법을 써도 FSM이 더 이상 작지 않고, 상태당 관측 밀도에서 나오던 이득도 함께 무너진다는 점을 저자들이 미리 밝혀 두었다.

가장 눈여겨본 것은

같은 구조물 하나가 네 가지 일을 동시에 한다는 대목이다. 워크플로우 메모리, 다음 행동 예측, 실패 예측, 런타임 감시. 보통은 각각 따로 학습한 파이프라인 네 개가 붙는 자리인데, 여기서는 하이퍼파라미터 없는 결정적 구축 하나가 밀리초 만에 그 넷을 모두 떠받친다.

그리고 그것이 가능했던 이유가 알고리즘의 새로움이 아니라는 점이 재미있다. 접두사 트리를 마지막 활동으로 병합하는 방법은 1970년대부터 있던 고전이다. 새로운 것은 대상이다. LLM 에이전트의 도구 목록이 유한하다는 사정 하나가 상태 공간을 작게 만들고, 작은 상태 공간이 상태마다 충분한 관측을 모아 주고, 그 밀도가 확률 추정을 안정시킨다. 저자들이 논문 곳곳에서 반복하는 말도 이것이다. 압축이 추정을 쓸 만하게 만든다.

내가 곱씹은 것은 감시기가 실패한 두 줄이다. tau2 리테일 F1 0.409, SWE-smith 0.276. 순환률 규칙이 통하려면 FSM이 실패 유형을 구별할 만큼 촘촘해야 하는데, 도구가 적은 에이전트에서는 그 조건이 안 선다. 도구를 적게 준 에이전트가 감시하기 더 쉬울 것 같지만, 이 결과는 반대를 말한다. 행동 어휘가 풍부해야 이상 행동이 어휘 안에서 구별되는 모양으로 드러난다. 관측 가능성을 나중에 붙이는 성질의 것으로 여기지 말고 도구 설계 단계에서 함께 생각해야 한다는 이야기로 읽힌다.

출처

Seonglae Cho, Franklin Cardenoso Fernandez, Umar Mohammed, Zekun Wu, Kleyton Da Costa, Ilham Wicaksono, Adriano Koshiyama (Holistic AI, University College London, PUC-Rio), “Automata from Agent Traces: Failure and Next-Step Prediction”, arXiv:2608.23670v1, 2026년 8월 24일.

원문: https://arxiv.org/abs/2608.23670

본문 그림은 논문 원문(arXiv:2608.23670v1)의 Figure 14와 Figure 16을 인용했다.