기술 요약: 에이전트 트레이스(Agent Traces)로부터의 오토마타 추출

문제 정의

LLM 기반 에이전트는 추론과 도구 호출을 교차하며 복잡한 다단계 작업을 수행하며, 이 과정에서 생성되는 실행 트레이스는 종종 길고 구조화되지 않은 형태를 띱니다. 이러한 불투명성은 안전성 감사, 디버깅 및 런타임 모니터링을 저해합니다. 기존의 행동 분석 방식은 대개 개별 트레이스 단위로 작동하거나, 성공 사례만을 필터링하거나, 수동으로 워크플로우를 지정해야 하는 한계가 있습니다. 결과적으로, 다음 단계 예측과 실패 예측을 연결하는 공유된 크로스 런(cross-run) 토폴로지를 포착하지 못합니다. 또한, 양의 예시(positive examples)만으로는 유한 오토마타를 학습하는 것이 이론적으로 불가능하며(Gold, 1967; Angluin, 1980), 기존의 오토마타 학습 알고리즘(예: RPNI, EDSM)은 음의 예시가 없을 경우 거대하고 과적합된 상태 공간을 생성하는 경우가 많습니다.

핵심 과제는 수동 개입 없이도 예측 모델링과 런타임 안전 모니터링을 가능하게 하기 위해, 실행 트레이스 코퍼스로부터 에이전트 행동의 압축된 구조적 표현을 복구하는 것입니다.

방법론

저자들은 에이전트 트레이스로부터 유한 상태 머신(FSM)을 구축하는 결정론적이고 하이퍼파라미터가 없는 방법을 제안합니다. 이 방법은 LLM 에이전트가 제한된 도구 및 액션 집합 내에서 작동하여 작은 활동 알파벳(6~42개 심볼)과 강력한 순차적 규칙성을 가진다는 관찰에 기반합니다.

1. 활동 추출 (Activity Extraction)

트레이스는 결정론적 추출 함수 $\phi$를 사용하여 유한 알파벳 $\mathcal{A}$의 심볼 시퀀스로 변환됩니다. 이 함수는 다음 사항을 우선시합니다:

1. 도구 호출(Tool calls): 함수 이름을 추출합니다.
2. 액션 태그(Action tags): 액션 레이블(예: [ACTION])을 추출합니다.
3. 명령어 추출(Command extraction): 코드 블록에서 첫 번째 명령어 토큰을 추출합니다.
   일치하는 규칙이 없는 경우, 활동은 역할-콘텐츠 유형(예: assistant:text)으로 기본 설정됩니다.

2. FSM 구축 (FSM Construction)

구축은 세 단계(알고리즘 A.1)로 진행됩니다:

• 접두 트리(Prefix Tree): 모든 활동 시퀀스가 트라이(trie)에 삽입됩니다. 각 고유한 접두사는 별개의 상태를 나타냅니다. 이는 완벽한 훈련 적합도(training fitness)를 제공하지만, 상태 수가 $O(\sum T_i)$에 달합니다.
• 마지막 활동 병합(Last-Activity Merge): "마지막 활동 우측 동형성(last-activity right congruence)"을 기준으로 상태가 병합됩니다. 두 상태 $q$와 $q'$는 진입하는 엣지의 활동이 동일할 때($\kappa(q) = \kappa(q')$) 병합됩니다. 이를 통해 상태 공간을 $|\mathcal{A}| + 1$개(각 활동당 하나와 초기 상태)로 줄여 결정론적인 직접 따름 오토마타(directly-follows automaton)를 생성합니다.
• 희소 전이 필터링(Rare-Transition Filtering): 단 한 번만 관찰된 전이는 해당 소스 상태로부터의 유일한 연속이 아닌 한 제거됩니다. 이는 핵심적인 행동 토폴로지는 보존하면서 일회성 일탈을 필터링합니다.

3. 이론적 보장 (Theoretical Guarantees)

• 적합도 보존(Fitness Preservation): 정리 2는 병합 연산이 훈련 적합도를 보존함을 증명합니다. 즉, 접두 트리에 의해 수용되는 모든 트레이스는 병합된 FSM에 의해서도 수용됩니다.
• 결정론 및 압축성(Determinism and Compactness): 정리 3은 결과 FSM이 $|\mathcal{A}| + 1$개의 상태를 가진 결정론적 모델임을 확립합니다. 이 구축 방식은 코퍼스의 결정론적 함수이며 재현성을 보장합니다.
• 수렴성(Convergence): 명제 5는 수렴 보장을 제공합니다. $N$개의 트레이스가 주어졌을 때, 전이가 최소 빈도로 나타난다는 조건 하에 추출된 FsM은 높은 확률로 모집단 직접 따름 오토마타와 일치합니다.

4. 예측 및 모니터링 (Prediction and Monitoring)

• 다음 단계 예측(Next-Step Prediction): FSM 상태 내 전이 횟수를 통해 확률 $P(a_t | q_t)$를 추정하며, Laplace 또는 절대 차감(absolute discounting)을 통해 평활화합니다.
• 실패 예측(Failure Prediction): 시스템은 상태별 특징(방문 빈도, 메시지 길이, 에러율)과 트레이스 수준의 이상 특징(교차 엔트로피, 놀람 정도)을 추출합니다. 경사 부스팅 분류기(gradient-boosted classifier)는 이러한 특징들을 사용하여 성공/실패를 예측합니다.
• 런타임 모니터(Runtime Monitor): 온라인 모니터는 FSM을 통해 트레이스를 재생하며 "사이클 비율(cycle rate)"(상태 재방문 빈도)과 같은 메트릭을 계산합니다. 이는 트레이스가 구조적으로 성공 패턴에서 벗어날 때(예: 좁은 루프에 진입) 조기 종료를 트리거합니다. 이때 모니터링 로직 자체를 위해 훈련된 ML 모델을 필요로 하지 않습니다.

주요 결과

본 방법론은 8개의 에이전트 도메인(코딩, 웹 네비게이션, GUI, 고객 서비스, 안전)에 걸친 12개의 공개 데이터셋을 대상으로 평가되었으며, 알파벳 크기는 6개에서 42개 사이였습니다.

• 압축성 및 적합도: 추출된 FSM은 매우 압축적이며 7~43개의 상태만을 포함합니다. 이들은 모든 데이터셋에서 테스트 재생 적합도(test replay fitness) $\ge 0.997$을 달고합니다. RPNI 베이스라인과 비교했을 때, 본 방법은 15배에서 3,036배에 달하는 압축비를 달와냅니다(예: SWE-agent에서 59,510개의 RPNI 상태를 25개의 FSM 상태로 축소).
• 다음 단계 예측: FSM 상태 컨텍스트는 평가된 8개 데이터셋 모두에서 AWM(Agent Workflow Memory)보다 우수한 성능을 보였으며, top-1 정확도 개선 폭은 +0.8pp에서 +25.3pp 사이였습니다. FSM 상태를 조건화하면 원시 컨텍스트만 사용할 때보다 교차 엔트로피가 0.155 비트(21%) 감소합니다.
• 실패 예측: 상태별 행동 특징은 held-out AUROC 최대 0.94(tau2-bench telecom)를 달성했습니다. 이 방법은 21개의 데이터셋-아키텍처 쌍 중 20개에서 MLP, GRU, Transformer 베이스라인을 능가했습니다.
• 런타임 효율성: FSM 구축은 1110ms 내에 완료됩니다(RPNI의 7,00036,000ms 대비). 트레이스당 재생 시간은 0.003~0.015ms로, 실시간 모니터링을 가능하게 합니다.
• 조기 종료: 온라인 모니터는 25% 트레이스 체크포인트에서 실패하는 실행을 성공하는 실행보다 높게 순위 매길 수 있으며(rank-AUROC 0.66), SWE-agent에서 32% 완료 시점에서 조기 종료를 트리거하여 남은 컴퓨팅 자원의 68%를 절약할 수 있습니다.
• 일반화: 4개의 서로 다른 LLM 트레이스로 구축된 단일 FSM은 각 모델에 대해 1.000의 적합도를 달려, 행동 토폴로지가 특정 LLM보다는 배포 하네스(deployment harness)와 도구 제약에 의해 형성됨을 보여줍니다.

의의 및 주장

본 논문은 LLM 에이전트가 겉보기에는 복잡해 보이지만, 압축된 구조적 추상화를 허용한다는 점을 주장합니다. 주요 의의는 워크플로우 메모리, 다음 단계 예측, 실패 예측, 런타임 모니터링이라는 네 가지 서로 다른 작업을 하나의 하이퍼파라미터가 없는 구축 방식으로 통합하는 **모델 불가지론적 구조적 프리미티브(model-agnostic structural primitive)**를 제공한다는 데 있습니다.

주요 주장:

1. 구조적 우선순위(Structural Primacy): 행동 토폴로지는 LLM보다 시스템(도구, 프롬프트, 작업 분포)에 의해 형성되므로, 모델 불변 모니터링이 가능합니다.
2. 다루기 쉬움(Tractability): 에이전트의 제한된 활동 알파벳 덕분에 양의 예시로부터 학습하는 문제가 용이하며, 통계적으로 유의미하고 해석 가능한 압축된 FSM을 생성합니다.
3. 효율성: 이 방법은 네 개의 별도 학습 파이프라인을 밀리초 단위로 작동하는 하나의 구조적 프리미티브로 대체하여, 안전 감사 및 런타임 모니터링에 적합하게 만듭니다.
4. 해석 가능성: HMM이나 대규모 오토마타 학습기와 달리, 이 FSM의 상태는 마지막 활동에 직접 대응하므로 상태별 분해 및 해석 가능한 실패 모드 분석(예: 실패가 새로운 상태를 탐색하기보다 특정 루프에 갇히는 것으로 나타난다는 점 등)이 가능합니다.

저자들은 추출된 FSM이 관찰된 트레이스의 직접 따름 폐쇄(directly-follows closure)를 수용할 뿐(생성 언어 자체가 아님)이라는 점과 활동 추출 함수에 최소한의 도메인 지식이 필요하다는 한계를 언급했습니다. 그러나 이들은 구조적 제약이 추출 정밀도에 관계없이 견고하며, 이 접근 방식이 안전 및 행동 분석을 위한 배포 가능한 기질(substrate)을 제공한다고 강조합니다.