Bayesian Social Deduction with Graph-Informed Language Models

1. 문제 정의 (Problem)

대형 언어 모델 (LLM) 은 다양한 추론 작업에서 뛰어난 성능을 보이지만, 사회적 추론 (Social Reasoning), 특히 다른 에이전트의 숨겨진 신념과 의도 (기만적 의도 포함) 를 부분적인 관찰을 통해 추론하는 능력에는 한계가 있습니다.

• 배경: Avalon 과 같은 사회적 추론 게임은 은밀한 역할 (선/악), 불확실성 관리, 기만 및 설득이 필요한 복잡한 환경입니다.
• 현황: 최신 대형 추론 모델 (LRM, 예: DeepSeek-R1) 은 단순한 확률 추론은 가능하나, 게임이 길어지고 사회적 상호작용이 복잡해지면 성능이 급격히 저하됩니다. 또한, 이러한 고성능을 내기 위해서는 긴 추론 체인 (Chain-of-Thought) 이 필요하여 실시간 상호작용에 비효율적이고 계산 비용이 매우 높습니다.
• 핵심 과제: 작은 모델로도 실시간으로 작동 가능하면서, 인간 플레이어와 경쟁할 수 있을 만큼 강력한 사회적 추론 능력을 갖춘 에이전트를 만드는 것.

2. 방법론 (Methodology): GRAIL

저자들은 GRAIL (Graph Reasoning Agent Informed through Language) 이라는 하이브리드 추론 프레임워크를 제안합니다. 이는 언어 이해를 위한 LLM 과 구조화된 확률적 추론을 위한 그래프 모델을 결합한 접근법입니다.

2.1 아키텍처 구성

1. 팩터 그래프 (Factor Graph) 기반 베이지안 추론:

   • 플레이어의 숨겨진 역할 (Good/Evil) 을 확률 변수로 모델링합니다.
   • 게임 상태 (파티 구성, 투표 결과, 퀘스트 성패) 를 관측 가능한 데이터로 활용합니다.
   • 제약 조건 만족: 고정된 악당 수 (예: 6 명 중 2 명) 와 같은 '하드 제약'과 퀘스트 실패 시 악당이 포함되었을 것이라는 '소프트 제약'을 그래프에 인코딩합니다.
   • 추론 알고리즘: 최대곱 (Max-Product) 베이지안 전파를 사용하여 관측된 게임 상태 하에서 가장 가능성 높은 역할 배치를 추정합니다. 이는 LLM 의 토큰 기반 추론보다 결정론적 제약 처리에 효율적입니다.
   • 함수 근사: 고차원 상태 공간에서의 조건부 확률 $P(r|state)$를 계산하기 위해 간단한 신경망 (Feedforward NN) 을 사용하여 팩터 함수를 근사화합니다.

2. 언어 모델 (LLM) 의 역할:

   • 언어 이해 및 생성: 채팅 로그를 분석하고, 자연어 대화 (의견 제시, 설득, 방어) 를 생성합니다.
   • 사전 확률 (Prior) 제공: LLM 은 대화의 맥락과 플레이어의 행동을 분석하여 각 플레이어가 '악당'일 가능성에 대한 정성적 판단 (증가/감소/유지) 을 내립니다. 이는 베이지안 추론의 사전 확률 (Prior) 로 변환되어 팩터 그래프에 주입됩니다.
   • 해석 가능성: 추론 과정이 LLM 내부가 아닌 외부 그래프에 분리되어 있어, 에이전트의 신념 변화를 해석하기 쉽습니다.

3. 행동 휴리스틱:

   • 그래프에서 추론된 '악당일 확률'을 기반으로 파티 제안 및 투표 결정을 내립니다 (예: 악당일 확률이 낮은 멤버만 포함된 파티만 승인).

3. 주요 기여 (Key Contributions)

1. 하이브리드 추론 프레임워크 제안: LLM 의 언어 능력과 구조화된 베이지안 추론의 엄밀함을 결합하여, 작은 모델로도 강력한 사회적 추론이 가능함을 증명했습니다.
2. 인간 플레이어 대비 승리: 통제된 실험에서 GRAIL 은 인간 플레이어 (초보자) 와 대결하여 67% 의 승률을 기록했습니다. 이는 기존 추론 모델 기반 에이전트나 인간 팀메이트보다 높은 성과입니다.
3. 효율성 및 확장성:
   • 매우 작은 LLM (예: Llama 3.1 8B) 을 사용하더라도 대형 추론 모델 (DeepSeek-R1 671B) 과 경쟁하거나 능가하는 성능을 보였습니다.
   • 토큰 생성량이 기존 추론 에이전트보다 10 배 이상 적어 실시간 상호작용에 적합합니다.
4. 오픈 소스 및 데이터셋: 프레임워크, 에이전트 구현체, 새로운 벤치마크, 그리고 에이전트 간 및 인간 - 에이전트 Avalon 게임 데이터셋을 공개했습니다.

4. 실험 결과 (Results)

4.1 에이전트 간 평가 (Agent-Agent)

• 승률: GRAIL 은 다양한 크기의 LLM 기반 베이스라인 (DeepSeek-R1, GPT-o4-mini 등) 과 대결에서 평균 75% 의 승률을 기록하며 최상위 성능을 보였습니다.
• 모델 크기 민감도:
  • 기존 추론 모델 (LRM) 은 모델 크기가 작아질수록 (671B → 70B → 8B) 성능이 급격히 떨어졌습니다.
  • 반면, GRAIL 은 8B 모델 사용 시에도 75% 이상의 높은 승률을 유지하며 모델 크기에 둔감한 (Robust) 성능을 입증했습니다.
• 할루시네이션: GRAIL 은 게임 사실에 대한 할루시네이션 (거짓 정보 생성) 발생률이 추론 모델보다 현저히 낮았습니다.

4.2 인간 - 에이전트 평가 (Human Study)

• 승률: 인간 플레이어 44 명을 대상으로 한 실험에서 GRAIL 은 67% 승률을 기록했습니다 (추론 모델 베이스라인은 27%).
• 품질 평가:
  • 인간 참가자들은 GRAIL 이 팀의 성공에 기여한 정도와 제안의 유용성 측면에서 추론 모델 베이스라인보다 통계적으로 유의미하게 높은 점수를 매겼습니다.
  • 인간 플레이어와 비교했을 때도 GRAIL 의 제안 품질은 인간과 유사하거나 더 높은 수준으로 평가받았습니다.
• 신념 수렴: 게임이 진행될수록 GRAIL 은 인간 플레이어의 신념을 더 정확하게 추론했으나, 인간은 LLM 에이전트보다 기만 능력이 뛰어나 신념 수렴이 더 느린 경향을 보였습니다.

5. 의의 및 결론 (Significance & Conclusion)

이 연구는 LLM 기반 에이전트의 사회적 추론 한계를 극복하기 위해 구조화된 확률적 모델 (Graph) 을 외부화하여 도입한 것이 핵심입니다.

• 실용성: 고비용의 대형 추론 모델 없이도, 작은 LLM 과 효율적인 베이지안 추론을 결합하여 실시간 다중 에이전트 환경에서 인간과 경쟁 가능한 에이전트를 구현할 수 있음을 증명했습니다.
• 이론적 통찰: LLM 만으로는 복잡한 사회적 추론 (특히 기만 탐지) 에 한계가 있으며, 명시적인 확률적 추론 구조가 이를 보완할 수 있음을 보여줍니다.
• 미래 작업: 현재 GRAIL 은 '기만 탐지 (1 차 이론적 마음)'에 초점을 맞추고 있으며, 향후 '기만 생성 (2 차 이론적 마음, 예: Merlin 역할 수행)'을 위한 확장 가능성을 제시했습니다.

요약하자면, 이 논문은 LLM 의 언어 능력과 베이지안 그래프 모델의 추론 능력을 융합함으로써, 계산 효율성을 유지하면서 인간 수준의 사회적 추론 능력을 달성한 첫 번째 언어 에이전트를 제시했다는 점에서 중요한 의의를 가집니다.