Exploration and Exploitation Errors Are Measurable for Language Model Agents

이 논문은 언어 모델 에이전트의 탐색과 활용 오류를 내부 정책 없이도 측정할 수 있는 새로운 평가 환경과 지표를 제안하고, 최신 모델들의 한계를 규명하며 추론 모델과 간단한 엔지니어링을 통해 성능을 크게 향상시킬 수 있음을 보여줍니다.

핵심

🗺️ 핵심 비유: 보물 사냥 게임

상상해 보세요. AI 에이전트는 눈을 가린 채 거대한 미로 (2D 그리드 지도) 에 던져졌습니다. 목표는 지도 어딘가에 숨겨진 **'보물 (목표 작업)'**을 찾는 것입니다. 하지만 보물이 어디 있는지, 어떤 순서로 찾아야 하는지 (예: 먼저 열쇠를 찾아야 문이 열린다) 는 전혀 모릅니다.

이때 AI 는 두 가지 전략을 써야 합니다.

1. 탐색 (Exploration): "어디에 보물이 있을까?"라며 알 수 없는 곳을 쏘다니며 새로운 정보를 찾는 것.
2. 활용 (Exploitation): "아, 열쇠는 이미 찾았네! 그럼 이제 문이 있는 곳으로 가자."라며 이미 알고 있는 정보를 이용해 목표를 달성하는 것.

🚨 문제: AI 는 왜 실패할까?

기존에는 AI 가 미로를 성공적으로 통과했는지 여부 (성공률) 만 봤습니다. 하지만 이 논문은 **"성공했더라도, AI 가 얼마나 비효율적으로 헤맸는지"**를 측정해야 한다고 말합니다.

저자들은 AI 의 행동을 분석해서 두 가지 실수를 찾아냈습니다.

• 탐색 실수: 이미 다 본 길을 다시 돌아다니거나, 보물이 있을 리 없는 구석구석을 무작정 헤매는 것.
• 활용 실수: 이미 찾은 보물 (정보) 을 가지고 목표에 도달할 수 있는데도, 다시 헤매거나 엉뚱한 방향으로 가는 것.

🛠️ 연구의 방법: "지능형 지도" 만들기

이 실수를 측정하기 위해 연구진은 다음과 같은 환경을 만들었습니다.

• 상징적인 미로: 실제 사물 (예: 사과, 책상) 이 아니라, 'A, B, C' 같은 기호로만 된 미로를 만들었습니다. AI 가 이미 알고 있는 지식 (예: "사과는 빨갛다") 으로 추측하지 못하게 하기 위함입니다. 오직 미로 자체의 정보만 보고 판단하게 한 거죠.
• 작업 지도 (DAG): 보물을 얻기 위한 순서 (예: A 를 먼저 찾으면 B 가 열린다) 를 미리 정해두었습니다.
• 실수 측정기: AI 가 이동할 때마다 "이 행동은 새로운 정보를 얻는 걸까, 아니면 이미 아는 정보를 이용하는 걸까?"를 계산합니다. 만약 AI 가 같은 길을 3 번 이상 반복하거나, 새로운 정보를 얻지 못하는 데만 시간을 쓴다면 '실수'로 기록합니다.

🔍 주요 발견: AI 의 특징

수많은 최신 AI 모델 (GPT-4, Claude, Gemini 등) 을 이 미로 게임에 투입한 결과, 놀라운 사실들이 드러났습니다.

1. 성공의 열쇠는 '탐색'에 있다:

   • AI 가 미로를 성공적으로 통과하려면, 탐색 실수를 적게 하는 것이 가장 중요합니다. (성공률과 탐색 실수는 반비례합니다.)
   • 반면, 활용 실수가 적다고 해서 무조건 성공하는 것은 아닙니다. 보물 (정보) 을 찾지 못하면, 아무리 잘 활용해도 소용없기 때문입니다.

2. 성공률이 같아도 행동은 다릅니다:

   • 두 AI 가 모두 100% 성공했다고 해도, 그 과정은 완전히 달랐습니다.
   • 어떤 AI 는 이미 본 길을 빠르게 지나쳐 갔고 (활용 위주), 어떤 AI 는 끝까지 미지의 영역을 샅샅이 뒤졌습니다 (탐색 위주). 성공률만 보면 둘 다 똑같아 보이지만, 어떤 AI 가 더 똑똑한지는 이 '실수 측정기'를 봐야 알 수 있습니다.

3. 약간의 조정이 큰 효과를 냈다:

   • AI 에게 "지금부터는 새로운 곳을 찾아봐"라고 말해주거나 (프롬프트), AI 가 기억해둔 정보를 정리해서 보여주기만 해도 (하네스 엔지니어링), 실수가 확 줄고 성공률이 급상승했습니다. 마치 운전자에게 "내비게이션을 잘 봐"라고 알려주는 것과 같습니다.

4. 지식의 양면성:

   • 미로에 실제 사물 이름 (예: '파스타', '토마토') 을 넣으면, 어떤 AI 는 그 지식을 이용해 빠르게 찾기도 했지만, 어떤 AI 는 오히려 "아마 파스타는 토마토 옆에 있겠지"라고 잘못 추측해서 더 헤매기도 했습니다. AI 가 지식을 어떻게 쓰느냐에 따라 결과가 달라진 것입니다.

💡 결론: 왜 이 연구가 중요할까요?

이 논문은 AI 를 평가할 때 **"결과 (성공/실패)"만 보지 말고, "과정 (어떻게 헤맸는지)"**을 자세히 봐야 한다고 말합니다.

• 비유하자면: 두 사람이 같은 목적지에 도착했다고 해서, 한 사람은 직선 도로를 타고 왔고 다른 사람은 10 번이나 길을 잃고 헤매고 왔다면, 우리는 전자를 더 똑똑하다고 평가해야 합니다.
• 이 연구는 AI 가 **어디서 길을 잃었는지 (탐색 실수)**와 **어디서 기회를 놓쳤는지 (활용 실수)**를 정확히 측정할 수 있는 도구와 기준을 제시했습니다.

이러한 분석을 통해 우리는 AI 가 더 효율적으로, 더 똑똑하게 미로 (복잡한 현실 문제) 를 헤쳐 나갈 수 있도록 도와줄 수 있게 됩니다.

기술 요약

1. 문제 정의 (Problem)

대규모 언어 모델 (LM) 에이전트는 AI 코딩, 워크플로우 자동화, 물리적 AI 등 복잡한 개방형 의사결정 작업에 널리 활용되고 있습니다. 이러한 작업의 핵심은 탐색 (Exploration) (미지의 문제 공간 탐색) 과 활용 (Exploitation) (획득한 지식의 효과적 활용) 사이의 균형을 잡는 능력입니다.

그러나 기존 연구에서는 다음과 같은 한계가 존재했습니다:

• 내부 정책 불가시성: 에이전트의 내부 정책 (Policy) 이나 가치 함수에 접근할 수 없기 때문에, 관찰된 행동 (Action Trajectories) 만으로 탐색과 활용을 체계적으로 구분하고 정량화하는 것이 어려웠습니다.
• 성공률의 한계: 기존 평가 지표는 주로 '작업 성공률 (Success Rate)'에 의존했습니다. 하지만 성공률만으로는 에이전트가 왜 실패했는지, 혹은 성공했더라도 어떤 방식 (탐색 부족인지, 활용 실수인지) 으로 실패했는지를 파악할 수 없습니다.
• 의미 정보의 혼동: 기존 환경은 의미론적 정보 (Semantic Information) 를 포함하여, 에이전트의 사전 지식 (Pretrained Knowledge) 과 환경 내 추론이 혼재되는 문제가 있었습니다.

2. 방법론 (Methodology)

저자들은 에이전트의 내부 정책에 의존하지 않는 (Policy-agnostic) 평가 프레임워크를 제안했습니다.

가. 제어 가능한 환경 설계

• 2D 그리드 맵: 부분적으로 관찰 가능한 (Partially Observable) 2D 그리드 맵을 사용합니다. 에이전트는 이동하며 주변 셀의 정보와 장애물을 점진적으로 파악합니다.
• 작업 DAG (Directed Acyclic Graph): 복잡한 작업은 전제 조건을 가진 하위 작업들의 집합으로 모델링됩니다.
  • 상징적 표현 (Symbolic Representation): 실제 의미 (예: '토마토 소스') 대신 무작위 4 자리 알파벳/숫자 토큰 (예: 'D7UX') 을 사용하여, 에이전트가 사전 지식을 활용하지 않고 오직 환경 관찰과 논리적 추론만으로 작업을 수행하도록 강제합니다.
  • 노드 상태: 미발견 (Undiscovered), 발견됨 (Discovered), 달성됨 (Achieved) 으로 구분되며, AND/OR 전제 조건을 가집니다.

나. 탐색 및 활용 오류 측정 지표 (Error Metric)

에이전트의 행동이 합리적인 전략 하에서 발생할 수 없는지 여부를 판단하는 지표를 정의했습니다.

• 목표 집합 (Target Set, $T(t)$): 에이전트의 현재 상태에 따라 '탐색이 필요한 미관측 셀' 또는 '활용이 가능한 미달성 작업'을 목표 집합으로 정의합니다.
• 이득 (Gain): 에이전트가 목표 셀로 이동하거나 목표까지의 거리를 단축하면 '이득'이 있는 것으로 간주합니다.
• 진행 없는 궤적 (No-Progress Trajectory, $\tau_{np}$): 최근의 진전 (새로운 셀 발견 또는 작업 달성) 이후의 행동 시퀀스를 분석합니다.
• 부패 점수 (Stale Score, $S_t$): 그래프 이론의 순환성 (Cyclomatic number) 과 재사용 횟수를 기반으로 계산합니다.
  • $c_t$: 새로운 루프가 닫혔을 때 증가.
  • $e_t, n_t$: 엣지나 노드가 2 회 이상 불필요하게 재사용될 때 증가 (기본적인 백트래킹은 허용하되, 과도한 반복은 오류로 간주).
• 오류 분류: $S_t$가 증가하거나 이득이 없는 행동을 '오류'로 간주하며, 해당 시점의 목표 집합 상태 (Table 1) 에 따라 탐색 오류, 활용 오류, 또는 둘 다로 분류합니다.

3. 주요 기여 (Key Contributions)

1. 정책 무관성 (Policy-agnostic) 측정 지표: 에이전트의 내부 논리를 알지 못하더라도, 행동 궤적만으로 탐색과 활용 오류를 정량화하는 새로운 메트릭을 제안했습니다.
2. 체계적인 평가 환경: 부분 관찰 가능한 그리드 맵과 미지의 작업 DAG 를 결합하여, 탐색과 활용의 요구 사항을 프로그래밍적으로 조절할 수 있는 환경을 구축했습니다.
3. 포괄적인 실험 및 분석: 다양한 최첨단 LM 에이전트 (GPT-4.1, GPT-5, Claude, Gemini 등) 를 평가하여 실패 모드를 식별하고, 프롬프트 엔지니어링 및 하네스 (Harness) 공학의 영향을 분석했습니다.

4. 실험 결과 (Experimental Results)

• 탐색 오류와 성공률의 강한 상관관계: Figure 1 에서 보듯, 성공률과 탐색 오류 사이에는 강한 음의 상관관계 ($R^2 = 0.947$) 가 있었습니다. 즉, 탐색을 잘하는 에이전트일수록 성공 확률이 높습니다. 반면, 활용 오류와 성공률 사이에는 약한 상관관계 ($R^2 = 0.006$) 만 있었습니다.
• 동일 성공률, 다른 행동 양상: Claude Opus 4.6 과 Gemini 3.1 Pro 는 모두 100% 성공률을 보였지만, 행동 패턴은 달랐습니다. Gemini 는 목표 도달 중에도 미관측 셀을 계속 탐색하는 반면, Claude 는 알려진 정보를 바탕으로 직접 목표지로 이동했습니다.
• 프롬프트의 영향: '탐색 중심' 프롬프트는 탐색 오류를 줄이고 성공률을 높이는 반면, '활용 중심' 프롬프트는 활용 오류를 줄였습니다.
• 하네스 엔지니어링 (Harness Engineering) 의 효과: 에이전트에게 관찰된 정보를 구조화된 요약 (방문한 셀, 프런티어, 활성화된 상태 등) 으로 제공하는 '하네스'를 적용하면, 성공률과 오류율 모두에서 획기적인 개선이 있었습니다 (예: GPT-4.1 성공률 63% → 92.6%).
• 의미 정보의 재도입: 의미 있는 이름 (예: 요리 작업) 을 도입했을 때 모델들의 반응이 달랐습니다. GPT-4.1 은 사전 지식을 활용해 탐색을 유도했으나, Gemini 는 오히려 의미 정보에 편향되어 단기적 활용 (Myopic Exploitation) 에 치우치는 경향을 보였습니다.

5. 의의 및 결론 (Significance)

이 연구는 LM 에이전트의 성능 평가에 성공률 이상의 새로운 차원을 제시합니다.

• 정밀한 진단: 단순히 "실패했다"가 아니라, "탐색을 못해서 실패했는가, 아니면 탐색은 잘했으나 활용을 잘못했는가"를 구분하여 에이전트의 약점을 진단할 수 있습니다.
• 개선 방향 제시: 하네스 엔지니어링과 프롬프트 설계가 에이전트의 탐색/활용 균형을 조절하는 데 결정적인 역할을 함을 입증했습니다.
• 신뢰성 있는 벤치마크: 의미론적 편향을 제거한 상징적 환경을 통해, 에이전트의 순수한 추론 및 계획 능력을 평가할 수 있는 기반을 마련했습니다.

결론적으로, 본 논문은 복잡한 개방형 작업에서 LM 에이전트의 탐색과 활용 능력을 정량적으로 측정하고 개선하기 위한 필수적인 프레임워크와 지표를 제공합니다.