언어 모델 에이전트의 탐색 및 활용 오류 측정 가능성 연구

LLM 에이전트가 복잡한 의사결정 작업에서 왜 실패하는지 정량적으로 분석할 수 있는 새로운 프레임워크를 제시합니다. 특히 탐색 오류가 성공률과 강력한 상관관계가 있음을 밝혀내어, 에이전트의 성능 향상을 위한 구체적인 설계 방향을 제공합니다.

강화학습의 핵심인 탐색과 활용은 보통 에이전트의 내부 가치 함수를 통해 정의되지만, 블랙박스인 LLM 에이전트에서는 이를 측정하기 어렵다. 이 논문은 에이전트의 행동을 그래프 이론의 중복성 개념과 연결하여, 아무리 합리적인 전략이라도 하지 않았을 '명백한 오류'를 정의함으로써 이 문제를 해결한다.

에이전트가 이전에 방문했던 경로를 불필요하게 반복하거나, 목표 달성에 도움이 되지 않는 루프를 형성할 때 이를 'stale score'라는 지표로 계산한다. 이는 마치 미로를 찾을 때 이미 막다른 길임을 확인한 곳을 다시 들어가는 행동을 수학적으로 포착하는 것과 같다.

결과적으로 에이전트가 새로운 정보를 얻지 못하면서(탐색 실패) 동시에 기존 지식을 목표 달성에 연결하지 못하는(활용 실패) 지점을 정확히 짚어낼 수 있다. 이는 단순한 성공/실패 여부를 넘어 에이전트의 지능적 한계가 어디에 있는지 구체적인 진단을 가능하게 한다.

부분 관찰 가능한 2D 그리드 맵 M과 작업 의존성을 나타내는 DAG G=(N, E)를 결합한 환경을 사용한다. 에이전트는 맵을 이동하며 노드를 발견하고, 선행 조건을 만족시켜 최종 목표 노드에 도달해야 한다. 모든 노드 이름은 의미가 없는 무작위 기호로 설정되어 LLM의 사전 지식 활용을 차단한다.

오류 측정은 '타겟 세트 T(t)'를 정의하는 것에서 시작한다. T(t)는 현재 상태에서 방문해야 할 미관찰 셀(탐색 대상)과 선행 조건이 만족된 기발견 노드(활용 대상)의 집합이다. 에이전트의 행동이 T(t)와의 거리를 줄이지 못하면(Gain=0) 오류 후보로 간주한다.

최종 오류 판정은 stale score S_t = c_t + e_t + n_t를 통해 이루어진다. 여기서 c_t는 사이클 형성 횟수, e_t는 엣지 재사용 횟수, n_t는 노드 재방문 횟수를 의미한다. Gain이 없으면서 S_t가 증가하는 행동을 구조적 오류로 정의하며, 이는 [현재 맵 상태 → 행동 분석 → 중복성 계산 → 오류 판정]의 과정을 거친다.

최신 LLM 에이전트들을 대상으로 실험한 결과, 탐색 오류의 로그 값과 성공률 사이에 매우 강력한 음의 상관관계(R² = 0.947)가 나타났다. 반면 활용 오류와 성공률 사이의 상관관계는 매우 낮았다(R² = 0.006). 이는 에이전트의 성패가 효율적인 탐색 능력에 달려 있음을 시사한다.

Claude 4.6과 Gemini 3.1 Pro는 모두 100%의 성공률을 기록했으나, 질적인 행동 패턴은 달랐다. Claude는 알려진 정보를 바탕으로 목표로 직진하는 경향(활용 중심)을 보인 반면, Gemini는 목표로 가는 도중에도 미지의 영역을 추가로 탐색하는 특성을 보였다.

하네스 엔지니어링(구조화된 메모리 제공)을 적용했을 때 GPT-4.1의 성공률은 63.0%에서 92.6%로 급증했으며, 탐색 오류는 0.297에서 0.053으로 대폭 감소했다. 이는 LLM의 내부 추론에만 의존하기보다 외부 시스템이 정보를 정리해 줄 때 에이전트 성능이 극대화됨을 보여준다.

본 연구는 에이전트의 행동 궤적 τ에서 '진전(progress)'이 없는 구간인 τ_np를 분석한다. 진전은 새로운 셀 관찰 또는 대기 중인 작업 완수로 정의된다. 이 구간 내에서의 중복 행동을 측정하기 위해 그래프 이론의 사이클로매틱 수(cyclomatic number)를 차용하여 구조적 중복성을 수치화한다.

작업 DAG는 AND/OR 논리 구조를 포함하여 생성되며, 노드 밀도와 복도 너비를 조절함으로써 탐색과 활용의 난이도를 독립적으로 제어한다. 이는 에이전트의 특정 실패 모드를 분리하여 관찰할 수 있게 하는 핵심적인 벤치마크 설계 특징이다.

실험에 사용된 '하네스 엔지니어링'은 에이전트에게 (1) 학습된 좌표계, (2) 알려진 목표 상태, (3) 방문한 셀 목록, (4) 탐색 가능한 경계선(frontier), (5) 장애물 정보, (6) 활성화 가능한 상태 등을 명시적으로 제공한다. 이는 LLM이 긴 컨텍스트에서 정보를 인출해야 하는 부담을 줄여 순수 의사결정 성능을 높인다.

제안된 오류 지표는 에이전트가 선택한 경로에 따라 정규화 방식이 달라지므로 궤적 의존적(trajectory-dependent)인 특성을 가집니다. 또한 2D 그리드 맵이라는 단순화된 환경을 사용하므로, 실제 세계의 복잡한 의미론적 정보가 포함된 환경으로의 확장이 필요합니다.