From Sequence to Structure: Relational Uncertainty Propagation for LLM Agents

Reliable uncertainty quantification (UQ) is essential for deploying large language model (LLM) agents in complex interactive environments. Existing UQ methods largely rely on local signals, such as token probabilities, predictive entropy, or per-step confidence, and therefore overlook the long-range dependencies through which errors accumulate across an execution trajectory. As a result, they may fail to identify agent failures whose causes originate several reasoning or interaction steps before the final answer. We propose RUPA (Relational Uncertainty Propagation for Agents), a trajectory-level UQ framework for LLM agents. RUPA represents an execution history as a directed trajectory graph in which reasoning states, tool interactions, and environment feedback are nodes connected by temporal and semantic dependency edges. It then propagates uncertainty over this graph to capture how execution risk accumulates and transfers across interaction steps. The propagated signal is combined with trajectory-level behavioral features and goal-alignment information to produce a confidence estimate for the full agent trajectory. We evaluate RUPA on representative agent benchmarks, including τ-2, Terminal-Bench-2, and GAIA, using 6 open-source LLMs spanning multiple model families. Experimental results show that RUPA consistently outperforms existing UQ methods by providing more accurate uncertainty estimates, enabling earlier failure detection, and improving uncertainty-guided agent execution across diverse agent tasks. These results demonstrate that explicitly modeling relational dependency is crucial to reliable UQ for long-horizon LLM agents, providing a practical foundation for trustworthy agent execution.

한 줄 요약

RUPA는 LLM 에이전트의 실행 트래잭토리에 기반한 관계 기반 불확실성 전파를 통해 신뢰도 높은 UQ를 구현한다.

핵심 기여도

RUPA는 실행 히스토리를 **의존성 그래프**로 모델링하고, 불확실성을 **의존 관계**를 따라 전파함으로써 오류 누적을 포착한다.
τ-2, Terminal-Bench-2, GAIA 벤치마크에서 MiniMax-M2.7 모델 기준 AUROC 0.694 → 0.718로 **+0.024 개선**.
**의존성 그래프 제거 시 AUROC 0.678**, 불확실성 전파 제거 시 AUROC 0.696로 성능 저하를 통해 구조적 의존성 모델링의 중요성을 입증.
**초기 실패 탐지 능력 향상**으로, prefix 기반 평가에서 기존 방법 대비 **더 빠른 실패 예측** 가능.

핵심 아이디어

기존 UQ 방법은 토큰 확률, 예측 엔트로피, 단계별 신뢰도 등 **로컬 신호**에만 의존하여, 실행 트래잭토리 내 **장거리 의존성**을 무시한다. 이는 초기 단계의 오류가 후속 단계에 영향을 미치며 누적되는 실패를 감지하지 못하게 한다. RUPA는 실행 히스토리를 **지향된 의존성 그래프**로 표현하고, 각 노드(추론 상태, 도구 사용, 환경 피드백) 간의 **시간적·의미적 의존 관계**를 고려하여 불확실성을 전파한다. 이는 단순히 시간 순서가 아닌, **의존 관계가 강한 경로**를 따라 불확실성이 전파됨으로써, 실행 위험의 진정한 누적 경로를 포착한다.

기술적 접근법

**RUPA 프레임워크**: 실행 히스토리를 **지향된 의존성 그래프**로 변환. 노드는 추론 상태, 도구 호출, 환경 피드백 등을 포함.
**의존성 그래프 구성**: 노드 간 **시간적 전이, 반복 행동, 추론 연속성, 피드백 의존성, 목표 정렬** 등을 기반으로 엣지 생성.
**불확실성 전파 알고리즘**: 노드의 **로컬 불확실성**과 **그래프를 따라 전파된 역사적 불확실성**을 결합.
**엣지 가중치**: 통계적 중요도에 따라 **관계 인식 가중치**를 자동 결정하여, 영향력 있는 경로를 따라 불확실성이 우선 전파됨.
**실험 환경**: τ-2, Terminal-Bench-2, GAIA 3개 벤치마크, 6개 오픈소스 LLM(26B~230B 파라미터) 사용.

주요 결과

**MiniMax-M2.7 모델 기준**: AUROC 0.694 → 0.718 (+0.024), AUPRC 0.805 → 0.812 (+0.007)
**의존성 그래프 제거 시**: AUROC 0.678, AUPRC 0.642 → **성능 저하**
**불확실성 전파 제거 시**: AUROC 0.696, AUPRC 0.725 → **성능 저하**
**랜덤 그래프 사용 시**: AUROC 0.678 → **의존성 구조가 핵심**
**다운스트림 성능 개선**: **저위험 후보 행동 선택**을 통해 **실행 성공률 향상**

의의 및 한계

RUPA는 LLM 에이전트의 실행 과정에서 **의존성 구조를 명시적으로 모델링**함으로써, 기존 UQ 방법이 무시했던 장거리 오류 누적을 포착할 수 있다. 이는 **신뢰성 있는 자율 에이전트 실행**을 위한 실용적 기반을 제공한다. 특히, 실패 원인이 여러 단계 전에 발생한 경우에도 **정확한 예측과 조기 감지**가 가능하다는 점에서 학술적·실용적 가치가 있다. 그러나 RUPA는 **의존성 그래프 생성 과정의 복잡성**과 **추가 계산 비용**을 수반하며, **모든 에이전트 시나리오에 일반화하기 어려운 한계**가 있다.

실용적 활용

RUPA는 **복잡한 다단계 추론**, **도구 사용**, **환경 상호작용**이 필요한 LLM 에이전트에서 활용 가능하다. 예를 들어, **소프트웨어 엔지니어링**, **웹 자동화**, **과학적 발견** 분야에서 **실행 위험 감지 및 자동 수정**을 지원할 수 있다. 특히, **실행 과정에서 실시간으로 실패를 예측하고 개입**하는 시스템 설계에 유용하다.