기술 요약: 멀티 에이전트 LLM은 서로를 탐색하는 데 실패한다

1. 문제 정의

본 논문은 현재 멀티 에이전트 시스템 내에서 작동하는 대규모 언어 모델(LLM) 에이전트의 근본적인 한계, 즉 동료의 역량을 추론하고 최적의 상호작용 전략을 식별하기 위해 동료를 효과적으로 **탐색(explore)**하지 못하는 문제를 다룹로다. 탐색은 강화 학습 및 내재적 동기 부여(intrinsic motivation) 문헌에서 신뢰할 수 있는 자율성의 초석이지만, 저자들은 현대의 LLM 에이전트가 근시안적이고 양극화된 상호작용 패턴을 보인다는 점을 관찰했습니다.

멀티 에이전트 환경은 역동성뿐만 아니라, 직접적인 상호작용을 통해서만 드러나는 이질적인 행동과 역량을 가진 다른 에이전트들에 의해 형성됩니다. 저자들은 이 과제를 **부분 관측 가능한 확률 게임(Partially Observable Stochastic Game, POSG)**으로 모델링하여 멀티 에이전트 탐색 문제로 정식화했습니다. 이 프레임워크에서:

• 에이전트는 동료의 역량(모델 패밀리나 컨텍스트에 따라 다름)을 추론하기 위해 선제적으로 동료를 조사해야 합니다.
• 에이전트는 부분적인 정보 하에서 작동하며, 동적으로 진화하는 상호작용 이력을 바탕으로 의사결정을 내립니다.
• 탐색에 실패하면 조기에 차선책인 동료에게 고착되어, 누적 후회(cumulative regret)가 증가하고 협업이 최적화되지 못하는 결과를 초ක합니다.

단순화된 두 팔 밴딧(two-armed bandit) 위임 작업으로부터 얻은 실증적 증거에 따르면, 최첨단 모델(GPT-4, GPT-5)조차 탐색과 활용(exploration and exploitation) 사이의 균듈을 맞추는 데 실패합니다. 에지(edge)에 있는 모델들은 우수한 동료로 수렴하기 위해 증거를 축적하는 대신, 정답 여부와 상관없이 처음 몇 라운드 안에 단 하나의 동료에게 고착되는 경향을 보입니다. 이러한 실패는 에이전트에게 탐색과 활용의 균형을 맞추도록 명시적으로 프롬프팅을 해도 지속됩니다.

2. 방법론: 멀티 에이전트 컨텍스트 탐색 (MACE)

전체 POSG를 정확하게 해결하는 것의 난해함(NEXP-hard)을 해결하기 위해, 저자들은 전체 결합 문제를 각 에이전트를 위한 독립적인 순차적 의사결정 문제로 분해하는 경량 프레임워크인 **멀티 에이전트 컨텍스트 탐색(Multi-Agent Contextual Exploration, MACE)**을 제안합니다.

핵심 메커니즘

MACE는 동료 선택을 컨텍스트 기반 멀티 암 밴딧(contextual multi-armed bandit) 문제로 프레임화합니다. 각 에이전트 $i$와 후보 동료 $a$에 대해, 기대 보상은 관계적 특징 벡터의 선형 함수로 모델링됩니다:
$$\mu_{i,a,t} \approx \mathbf{x}_{i,a,t}^\top \theta_{i,a}$$

주요 구성 요소

1. 관계적 특징 설계 (Relational Feature Design): 팔(arm)이 정적인 표준 밴딧과 달리, MACE는 멀티 에이전트 상호작용의 비정상성(non-stationarity)을 새로운 구조적 특징 표현으로 인코딩합니다. 특징에는 다음이 포함됩니다:

   • 응답 다양성 (Response Diversity): 에이전트의 현재 답변과 동료의 응답 사이의 발산 정도(n-gram 유사도 사용)를 측정하여 잠재적인 정보 이득을 포착합니다.
   • 동료 차별성 (Peer Distinctiveness): 특정 동료가 에이전트 네트워크의 나머지 부분으로부터 얼마나 떨어져 있는지 측정합니다.
   • 역사적 성능 (Historical Performance): 동료의 경험적 성공률입니다.
   • 상호작용 라운드 (Interaction Round): 탐색 강도를 조절하기 위해 현재 상호작용 단계를 인코딩합니다.

2. 낙관주의를 통한 탐색 (LinUCB): MACE는 동료를 선택하기 위해 LinUCB 알고리즘을 채택합니다. 선택 규칙은 상한값(upper confidence bound)을 최대화합니다:
   $$a_{i,t} = \arg\max_{a} \left[ \hat{\theta}_{i,a}^\top \mathbf{x}_{i,a,t} + \alpha \sqrt{\mathbf{x}_{i,a,t}^\top \mathbf{A}_{i,a}^{-1} \mathbf{x}_{i,a,t}} \right]$$
   두 번째 항은 불확실성 보너스(uncertainty bonus) 역할을 합니다. 결정적으로, 이 보너스는 단순 선택 횟수가 아닌 관계적 특징 공간 상에서 작동하기 때문에, MACE는 전역적으로 테스트가 부족한 동료와 특정 관계적 맥락에서 테스트가 부족한 동료를 구분할 수 있습니다.

3. 보상 신호 (Reward Signal): 보상은 상호작용 후 에이전트의 작업 점수 개선 정도와 최종 응답의 절대적 품질을 결합한 혼합 지표이며, 이를 통해 고품질의 답변을 유지하는 것 또한 보상받도록 합니다.

3. 주요 기여

1. 멀티 에이전트 탐색의 정식화: 본 논문은 멀티 에이전트 탐색 문제를 POSG로 엄격하게 정의하며, 현재의 LLM 에이전트가 동료를 효과적으로 탐색하지 못해 조기 고착 및 높은 후회를 초래하는 구조적 한계를 강조합니다.
2. MACE 프레임워크: 구조화된 동료 선택을 촉진하기 위해 명시적인 탐색 인센티브를 갖춘 컨텍스트 밴딧을 사용하는 실행 가능한 프레임워크인 MACE를 도입합니다.
3. 이론적 특성 규명: 저자들은 탐색의 가치가 에이전트의 다양성에 직접적으로 비례함을 증명합니다. MACE가 하위 선형 누적 후회($O(\sqrt{T \log T})$)를 달하는 반면, 탐색하지 않는 탐욕적 정책은 선형 후회($\Omega(\delta T)$)를 유발함을 보여줍니다 (여기서 $\delta$는 에이전트 풀의 역량 다양성을 나타냄).

4. 실험 결과

저자들은 두 가지 유형의 이질성, 즉 컨텍스트 다양성(에이전트들이 동일한 모델을 공유하지만 서로 다른 컨텍스트/검색된 문서를 가짐)과 파라미터 다양성(에이전트들이 서로 다른 모델 패밀리/규모를 사용함)에 대해 MACE를 평가합니다.

• 탐색 행동: 두 설정 모두에서 MACE는 분산된 동료 선택 패턴을 유도합니다. 반면, "인-컨텍스트 탐색(In-Context Exploration, 탐색과 활용의 균형을 맞추도록 프롬프팅된 에이전트)"은 매우 양극화되고 이봉 분포(bimodal distribution)를 보이는 경향이 있으며, 종종 단일 동료에게 고착됩니다. 특히, 인-컨텍스트 탐색은 무작위 동료 선택보다 성능이 떨어지는 경우가 많은데, 이는 프롬프팅만으로는 탐색 실패를 해결할 수 없음을 시사합니다.
• 작업 성능: MACE는 HotpotQA, Math500, GPQA, 2WikiMultihopQA를 포함한 벤치마크에서 다운스트림 작업 성능(Exact Match, F1, Accuracy) 측면에서 베이스라인(Random, Pre-defined, In-Context Exploration)을 크게 상회합니다.
• 일반화: 한 벤치마크(HototaQA)에서 학습된 MACE의 상호작용 전략은 추가 학습 없이도 보지 못한 벤치마크(2WikiMultihopQA)로 효과적으로 전이되며, 이는 특정 작업의 부산물이 아닌 일반화 가능한 구조를 학습했음을 시사합니다.
• 다양성의 영향: 이론적 및 실증적 결과는 탐색의 이점이 에이전트의 다양성이 커질수록 증가함을 확인해 줍니다. 매우 동질적인 환경(예: 동일한 모델들)에서는 탐색의 후회 이점이 줄어들지만, 완만한 성능 향상은 지속됩니다.

5. 의의 및 주장

본 논문은 신뢰할 수 있는 멀티 에이전트 자율성은 탐색의 암묵적인 출현에 의존할 수 없으며, 명시적인 알고리즘적 가이드가 필요하다고 주장합니다. 저자들은 LLM 에이전트의 탐색 실패가 단순히 작은 모델의 능력 부족이 아니라, GPT-5조차 이러한 실패 모드를 보이는 근본적이고 구조적인 한계라고 주장합니다.

이 연구의 의의는 다음과 같습니다:

• 근본적인 격차 식별: 현재의 멀티 에이전트 시스템이 에이전트가 효과적인 협력자를 자율적으로 발견할 수 있다고 암묵적으로 가정하고 있으나, 실제로는 LLM이 그러한 능력이 부족하다는 점을 밝혀냈습니다.
• 솔루션 제공: MACE와 같은 경량화된 알고리즘적 탐색 메커니즘이 이질적인 에이전트 집단에서 조정 능력과 작업 성능을 크게 향상시킬 수 있음을 입증했습니다.
• 이론적 통찰: 탐색이 에이전트들이 전문화되고 서로 다를 때 가장 가치 있다는 직관을 정식화하고, 탐색하는 정책과 그렇지 않은 정책 사이의 후회 격차에 대한 이론적 경계를 제공했습니다.

저자들은 멀티 에이전트 AI 시스템이 오픈 월드 환경에서 사회적으로 신뢰할 수 있고 효과적이려면, 프롬프팅이나 창발적 행동에 의존하기보다 명시적인 탐색 전략을 갖추어야 한다고 결론짓습니다.