GraphPlanner: 다중 에이전트 LLM 을 위한 그래프 메모리 증강 에이전트 라우팅 기술 요약

본 논문은 ICLR 2026 에 게재된 **"GraphPlanner: Graph Memory-Augmented Agentic Routing for Multi-Agent LLMs"**로, 대규모 언어 모델 (LLM) 라우팅을 단순한 모델 선택을 넘어 다중 에이전트 협업 워크플로우 생성 문제로 확장한 혁신적인 접근법을 제시합니다.

1. 문제 정의 (Problem)

기존의 LLM 라우팅 연구는 주로 단일 회로 (Single-round) 또는 다중 회로 (Multi-round) 라우팅에 집중되어 왔습니다.

• 단일 회로 라우팅: 쿼리 임베딩이나 분류기를 기반으로 한 번의 모델 선택을 수행합니다. 복잡한 태스크를 분해하거나 여러 모델을 협업시키는 능력이 부족합니다.
• 다중 회로 라우팅: 컨텍스트를 누적하여 순차적으로 모델을 선택하지만, 각 호출을 독립적인 사건으로 취급하여 에이전트 간의 명시적인 협업 (Collaboration) 과 역할 분담 (Specialization) 을 모델링하지 못합니다. 이로 인해 불필요한 호출, 컨텍스트 충돌, 그리고 상호 보완적 강점의 활용 부족이 발생합니다.

실제 복잡한 현실 세계 태스크에서는 이질적인 에이전트 (Heterogeneous Agents) 간의 계획 (Planning), 실행 (Execution), 요약 (Summarization) 이 필요한 에이전트 라우팅 (Agentic Routing) 환경이 필수적입니다. 그러나 기존 방법들은 이러한 동적이고 복잡한 에이전트 협업 상황을 처리할 수 있는 체계적인 라우팅 프레임워크가 부재했습니다.

2. 방법론 (Methodology)

저자들은 GraphPlanner를 제안하며, 이를 통해 각 쿼리에 대해 최적의 다중 에이전트 라우팅 워크플로우를 동적으로 생성합니다.

2.1 마르코프 의사결정 과정 (MDP) 으로서의 워크플로우 생성

에이전트 라우팅 워크플로우 생성을 **마르코프 의사결정 과정 (MDP)**으로 형식화합니다.

• 상태 (State): 현재 해결 중인 쿼리와 evolving 되는 워크플로우 메모리 그래프.
• 행동 (Action): 각 단계에서 에이전트 역할 (Planner, Executor, Summarizer) 과 LLM 백본을 동시에 선택하는 쌍 $(a_t, m_t)$.
• 전환 (Transition): Planner 는 쿼리를 하위 쿼리로 분해하고, Executor 는 답변을 생성하며, Summarizer 는 결과를 통합합니다.
• 보상 (Reward): 최종 답변의 정확도 (Task Utility) 와 계산 비용 (Computational Cost) 의 균형을 고려한 보상 함수를 설계합니다.

2.2 이질적 그래프 메모리 증강 (GARNet)

GraphPlanner 의 핵심은 **GARNet (Graph Memory-Augmented Router Network)**이라는 이질적 그래프 신경망을 사용하는 것입니다.

• 이질적 그래프 구조: 쿼리 (Query), 응답 (Response), 에이전트 역할 (LLM-Role) 노드와 이들 간의 관계를 표현합니다.
• 메모리 통합:
  • 워크플로우 메모리 ($G_{workflow}$): 현재 쿼리 해결 과정에서의 상호작용을 기록합니다.
  • 역사적 메모리 ($G_{history}$): 과거의 성공적인 협업 패턴, 오류 모드, 효율적인 역할 분담 정보를 저장합니다.
• 공유 역할 허브 (Shared Role Hub Nodes): 모든 쿼리와 응답은 동일한 역할 (Planner, Executor 등) 노드에 연결됩니다. 이를 통해 현재 워크플로우와 과거의 역사적 상호작용이 자연스럽게 통합되며, 다중 라운드 라우팅 시 맥락이 유지됩니다.

2.3 강화학습 기반 최적화 (PPO)

전체 파이프라인은 근접 정책 최적화 (Proximal Policy Optimization, PPO) 알고리즘을 통해 학습됩니다. 이는 라우팅 정책이 단기적인 효율성과 장기적인 태스크 성능을 동시에 최적화하도록 유도합니다.

3. 주요 기여 (Key Contributions)

1. 에이전트 라우팅 프레임워크의 확장: 라우팅을 단순한 모델 선택이 아닌, 역할과 모델을 동시에 결정하는 워크플로우 생성 문제로 재정의했습니다.
2. GARNet 도입: 이질적 그래프를 활용하여 쿼리, 에이전트, 응답 간의 복잡한 상호작용과 역사적 메모리를 통합한 새로운 라우팅 아키텍처를 제시했습니다.
3. 유연한 추론 모드 지원:
   • 귀납적 (Inductive): 학습 데이터 없이 새로운 쿼리에 대해 효율적으로 추론.
   • 연역적 (Transductive): 학습된 역사적 상호작용을 활용하여 더 높은 성능 달성 (비용 증가).
4. 강화학습을 통한 효율성 극대화: 정확도와 GPU 비용 간의 최적 균형 (Pareto Frontier) 을 달성하는 정책을 학습했습니다.

4. 실험 결과 (Results)

14 개의 다양한 태스크 (수학, 코드, 상식 추론 등) 와 6 개의 도메인에서 GraphPlanner 를 평가했습니다.

• 성능 향상:
  • Phase 1 (기존 워크플로우 내 최적화): 평균 정확도 3.8% 향상.
  • Phase 2 (최적 워크플로우 생성): 평균 정확도 9.3% 향상 (기존 최강 베이스라인 대비).
  • 특히 수학과 코드와 같은 복잡한 추론 태스크에서 성능 향상이 두드러졌습니다.
• 비용 효율성:
  • GPU 비용이 186.26 GiB에서 1.04 GiB로 획기적으로 감소했습니다.
  • 단일 회로 및 다중 회로 라우터들보다 Pareto Frontier 상에 위치하여 동일한 비용 대비 더 높은 정확도, 또는 동일한 정확도 대비 더 낮은 비용을 달성했습니다.
• 일반화 능력 (Generalization):
  • 미시작 (Zero-shot) 태스크: 학습되지 않은 새로운 태스크 (LogicGrid, MGSM 등) 에서 평균 **78%**의 정확도를 기록하여 기존 라우터들 (46~58%) 을 크게 앞섰습니다.
  • 미시작 LLM: 학습에 사용되지 않은 새로운 LLM 백본에 대해서도 추가 파인튜닝 없이 강력한 성능을 유지했습니다.
• 메모리 활용: 역사적 메모리를 활용하지 않은 변형 (w/o History) 대비 성능이 크게 저하됨을 확인하여, GARNet 을 통한 메모리 활용의 중요성을 입증했습니다.

5. 의의 및 결론 (Significance)

GraphPlanner 는 LLM 라우팅 연구의 패러다임을 **"단일 모델 선택"에서 "지능형 다중 에이전트 협업 워크플로우 생성"**으로 전환시켰다는 점에서 의의가 큽니다.

• 실용성: 복잡한 현실 세계 태스크를 해결하기 위해 이질적인 LLM 들을 효율적으로 조율할 수 있는 체계를 제공합니다.
• 확장성: 학습된 라우팅 정책이 새로운 에이전트 역할 (Thinker, Verifier 등) 과 새로운 LLM 모델에 대해 강력한 일반화 능력을 보여주어, 미래의 확장 가능한 다중 에이전트 시스템의 기반이 됩니다.
• 효율성: 높은 정확도를 유지하면서도 계산 비용을 대폭 절감하여, 실제 배포 환경에서의 적용 가능성을 높였습니다.

결론적으로, GraphPlanner 는 역사적 상호작용 메모리와 그래프 기반 추론을 결합하여, 다중 에이전트 LLM 시스템의 잠재력을 최대한 끌어올리는 새로운 표준을 제시합니다.