[Paper] 측정할 수 없는 것을 측정하기: LLM 에이전트를 위한 Markov Chain 신뢰성

Source: arXiv - 2604.24579v1

개요

이 논문은 TraceToChain이라는 재현 가능한 파이프라인을 소개합니다. 이 파이프라인은 대규모 언어 모델(LLM) 에이전트의 실행 추적을 흡수성 이산 시간 마코프 체인(DTMC)으로 변환합니다. 이를 통해 서로 다른 신뢰성 지표(예: pass@k, 신뢰성 감소 곡선)를 하나의 통계적으로 기반한 “성공‑시간” 분포로 통합하고, 현재 벤치마크 보고서에 부족한 진단 및 불확실성 추정도 제공한다.

Key Contributions

• Trace‑to‑DTMC 파이프라인은 트레이스 상태를 자동으로 클러스터링하고, Laplace‑스무딩된 MLE로 전이 확률을 추정하며, LLM 에이전트 행동에 흡수형 DTMC를 적합시킵니다.
• 통계 진단: 복합 Akaike Information Criterion (AIC) 및 Kolmogorov–Smirnov (KS) 적합도 검정을 사용하여 체인이 관측된 트레이스를 충실히 나타내는지 확인합니다.
• 불확실성 정량화: 각 전이 확률에 대해 Dirichlet‑사후 신뢰 구간 및 비모수 부트스트랩 구간을 제공합니다.
• 통합 신뢰성 관점: 일반적인 지표(pass@k, pass^k, 신뢰성 감소 곡선)가 DTMC에서 도출된 단일 최초 통과 시간 분포의 투영에 불과함을 보여줍니다.
• 실증 검증: 7개의 제어된 MAST‑스타일 프레임워크에서 적합된 DTMC는 최대 L∞ 오차 0.053으로 보류된 신뢰성 곡선을 재현하며, 모든 프레임워크에서 KS 검정(p > 0.05)을 통과합니다.

방법론

1. Trace Collection – LLM 에이전트를 다양한 작업에 실행하고 모든 중간 상태(예: 도구 호출, 프롬프트, 응답)를 기록합니다.
2. Automatic Clustering – 데이터 기반 클러스터링 알고리즘을 사용해 유사한 상태들을 “매크로‑스테이트”라는 분류 체계로 그룹화하여 의미를 보존하면서 트레이스 길이를 줄입니다.
3. Transition Estimation – 에이전트가 한 매크로‑스테이트에서 다른 매크로‑스테이트로 이동하는 빈도를 계산합니다. 제로 확률 에지를 방지하기 위해 라플라스 스무딩을 적용하고, 전이 행렬 Q(일시‑일시)와 흡수 행렬 R₊(성공으로) 및 R₋(실패로)에 대한 최대우도 추정치를 구합니다.
4. Model Fit Checks –
   • AIC는 모델의 간결성 대비 적합도를 평가합니다.
   • KS test는 트레이스가 처음으로 흡수 상태에 도달할 때의 경험적 첫 통과 시간 CDF를 DTMC에서 유도된 해석적 CDF와 비교합니다.
5. Uncertainty Reporting – 전이 횟수를 디리클레 분포에서 추출된 샘플로 간주하여 신뢰 구간을 얻고, 전체 트레이스 집합을 부트스트랩하여 비모수적 신뢰 구간을 생성합니다.
6. Reliability Extraction – 적합된 DTMC에 고전적인 신뢰도 공식(Kemeny–Snell, Goel–Okumoto 등)을 적용해 pass@k, pass^k 및 첫 통과 시간 분포를 기반으로 한 신뢰도 감소 곡선을 폐쇄형 함수 형태로 계산합니다.

결과 및 발견

• 적합도: 7개의 테스트 프레임워크 전반에 걸쳐 DTMC에서 도출된 분석적 신뢰도 감소 곡선이 경험적 곡선 위에 겹쳐 median L∞ 오차가 0.048로, 매우 근접함을 나타냅니다.
• 통계적 수용: 첫 통과 CDF에 대한 두 표본 KS 검정은 모델을 절대 기각하지 않으며(p‑값은 0.78에서 1.0 사이) 일관된 적합성을 보여줍니다.
• 불확실성 타이트함: 각 전이 확률에 대한 사후 및 부트스트랩 구간이 median에서 약 0.01 이내로 일치하여, 적은 트레이스 데이터에서도 파이프라인이 안정적인 추정치를 제공함을 나타냅니다.
• 지표 통합: 저자들은 pass@k, pass^k, 그리고 신뢰도 감소 곡선이 모두 동일한 DTMC 기반 분포의 주변화임을 수학적으로 증명하여 벤치마크 결과 해석을 단순화합니다.

Practical Implications

• More Trustworthy Benchmarks: 개발자는 이제 스칼라 점수(예: pass@10 = 0.73)와 함께 전체 성공‑시간 분포 및 신뢰 구간을 제공할 수 있어, 다양한 지연 시간이나 단계‑예산 제약 하에서 에이전트를 비교하기가 쉬워집니다.
• Debugging & Optimization: 매크로‑상태 전이 행렬은 “병목” 상태(루프나 실패 확률이 높은)를 강조하여, 목표가 된 프롬프트 엔지니어링이나 도구‑통합 개선을 안내합니다.
• Service‑Level Agreements (SLAs): LLM 기반 에이전트를 제공하는 클라우드 업체는 DTMC 모델을 사용해 주어진 시간 예산 내에 작업이 완료될 확률을 예측함으로써, 보다 정밀한 SLA 정의가 가능합니다.
• Automated Monitoring: 새로운 추적 데이터를 지속적으로 TraceToChain에 입력함으로써, 프로덕션 시스템은 (예: 실패 상태로 전이되는 급증)와 같은 드리프트를 사용자에게 오류가 나타나기 전에 감지할 수 있습니다.
• Cross‑Task Generalization: 파이프라인이 데이터‑구동 방식이기 때문에, 코드 생성, 자율 웹‑브라우징, 다중 턴 추론 등 어떤 순차적 LLM 워크플로에도 손쉽게 적용할 수 있으며, 작업‑특정 신뢰성 공식들을 별도로 만들 필요가 없습니다.

제한 사항 및 향후 연구

• Controlled Benchmarks: 검증은 합성 MAST‑style 프레임워크에서 수행되었습니다; 실제 세계의 잡음이 많은 환경에서는 상태 폭발이나 비마코프 의존성이 발생하여 DTMC 가정에 도전할 수 있습니다.
• State Clustering Sensitivity: 매크로‑state 분류 체계의 품질은 클러스터링 알고리즘 및 하이퍼파라미터에 의존합니다; 부실한 클러스터링은 중요한 실패 모드를 가릴 수 있습니다.
• Scalability: 매우 긴 트레이스나 방대한 작업 스위트의 경우 전이 행렬이 커져 희소‑행렬이나 계층적 모델링 기법이 필요할 수 있습니다.
• Extension to Continuous Time: 현재 모델은 이산‑시간이며; 연속‑시간 마코프 프로세스로 확장하면 가변‑길이 동작(예: 지연 시간이 다른 API 호출)을 포착할 수 있습니다.
• Integration with Training Loops: 향후 연구에서는 신뢰성 진단을 LLM 파인‑튜닝이나 인간 피드백 기반 강화 학습 파이프라인에 다시 입력하여 원하는 첫‑통과 분포를 직접 최적화함으로써 루프를 닫을 수 있습니다.

저자

• Phat T. Tran‑Truong
• Xuan‑Bach Le

논문 정보

• arXiv ID: 2604.24579v1
• 분류: cs.SE
• 출판일: 2026년 4월 27일
• PDF: PDF 다운로드