Learning to Recommend Multi-Agent Subgraphs from Calling Trees

기술 요약: 호출 트리(Calling Trees)로부터 멀티 에이전트 서브그래프 추천 학습

문제 정의
본 논문은 에이전트 마켓플레이스가 수천 개의 이질적인 에이전트를 포함할 정도로 확장됨에 따라 발생하는 멀티 에이전트 시스템(MAS)의 결정적인 공백을 다룹니다. 기존의 추천 시스템은 평면적인 유저-아이템 로그(예: 이커머스)를 기반으로 개별 아이템의 순위를 매기는 데는 뛰어나지만, 에이전트 오케스트레이션의 구조적, 순차적, 상호작용 의존적 특성을 해결하는 데는 실패합니다. MAS에서 에이전트를 선택하는 것은 단순한 종단적 결정이 아니라, 시스템 상태를 변화시키고 의존성을 유발하며 후속 선택의 호환성에 영향을 미치는 개입입니다. 핵심 과제는 많은 에이전트가 기능적으로 중첩되어 있다는 점이며, 따라서 선택을 순수한 검색 문제로 취급할 수 없습니다. 오케스트레이터는 단순히 관련성이 있는 것뿐만 아니라, 신뢰할 수 있고, 현재 실행 컨텍스트와 호환되며, 선택된 다른 에이전트들과 협력할 수 있는 에이전트를 선택해야 합니다. 본 논문은 이를 하나의 서브태스크를 실행하기 위해 단일 에이전트(에이전트 수준) 또는 연결된 에이전트 팀(시스템 수준/서브그래프)을 추천하는 **제약된 결정 문제(constrained decision problem)**로 정식화합니다.

방법론
저자들은 평면적인 로그가 아닌, 역사적인 호출 트리(calling trees)(부모-자식 호출, 분기 의존성 및 로컬 협력 패턴을 캡처하는 실행 트레이스)에 기반한 일반적인 2단계 제약 추천 프레임워크를 제안합니다. 이 프레임워크는 두 단계로 작동합니다:

1. 가용성 구축 (Retrieval, 검색): 검색 모듈은 방대한 에이전트 풀을 필터링하여 현재 서브태스크와 컨텍스트에 조건화된 압축적이고 의미론적으로 관련 있는 후보 집합($A_{feasible}$은 에이전트용, $G_{feasible}$은 에이전트 시스템용)을 구축합니다. 이 단계는 검색 공간을 줄이기 위해 기성(off-the-shelf) 검색 메커니즘(예: 임베딩 유사도 또는 LLM 기반 도구 호출)에 의존합니다.
2. 유틸리티 최적화 (Reranking, 재순위화): 가용 집합 내에서 학습된 스코어링 모델은 유틸리티 최적화를 수행하여 최적의 옵션을 선택합니다. 이 단계는 관련성, 신뢰성 및 상호작용 효과를 고려합니다.

본 논문은 이 프레임워크의 두 가지 구체적인 인스턴스를 정의합니다:

• SARL (Single-Agent Recommendation Learning): 다음 단일 에이전트/도구를 선택합니다. 이는 태스크 쿼리 인코딩, 에이전트 역량, 그래프 구조적 관계, 역사적 신뢰성 및 리스트 인식 컨텍스트 효과를 통합하는 파라미터 스코어링 함수 $s_\theta(t, a)$를 사용합니다.
• ASRL (Agent-System Recommendation Learning): 작고 연결된 에이전트 팀(서브그래프)을 선택합니다. 이는 결정 단위를 그룹으로 일반화하여, 집합적 역량, 내부 협력 패턴 및 글로벌 그래프 내의 구조적 적합성을 집계하는 스코어링 함수 $s_\theta(t, g)$를 사용합니다.

두 모델 모두 관찰된 실행 결과에 대해 손실 함수(예: 소프트맥스 교차 엔트로피)를 최소화하며 역사적인 오케스트레이터 트레이스를 사용하여 학습되며, 선택된 에이전트나 시스템이 가용 집합에 속하도록 하는 제약 조건을 포함합니다.

주요 기여

1. 문제 정식화: 본 논문은 에이전트 추천을 MAS에서의 제약된 결정 문제로 식별하고 정식화하여, 멀티 에이전트 환경에서의 기존 아이템 수준 독립성 가정의 한계를 강조합니다.
2. 통합 프레임워크: 가용성 구축과 유틸리티 최적화를 분리하여 에이전트 수준 및 시스템 수준(서브그래프) 추천을 모두 지원하는 2단계 "분할 정복(divide-and-conquer)" 프레임워크를 도입합니다.
3. 구조화된 데이터 벤치마크: 저자들은 8개의 이질적인 멀티 에이전트 코퍼스(Agent-data-protocol, GTA, MCPToolBench++ 등 포함)의 호출 로그를 공유된 구조적 표현으로 정규화하여 일관된 평가가 가능한 통합 호출 트리 벤치마크를 구축했습니다.
4. 실증적 검증: 광범적인 실험을 통해 제안된 접근 방식이 Top-1 정확도, 안정성 및 실행 일관성 측면에서 강력한 베이스라인 전략(직접 검색, 코사인 유사도 랭킹 및 단일 패스 LLM 선택)보다 일관되게 우수한 성능을 보임을 입증했습니다.

결과

• 단일 에이전트 (SARL): 6개의 중규모 데이터셋에서 SARL(LLM 검색 + 재순위화)은 직접 검색 및 코사인 유사도 베이스라인(예: Agent-data-protocol에서 79.85% 대 40.0%)보다 우수한 Top-1 정확도를 달성했습니다. 결과는 검색이 강력한 후보 집합을 제공하지만, 모호성을 해결하고 가장 신뢰할 수 있는 에이전트를 선택하는 데는 지도 학습 기반의 재순위화가 필수적임을 나타냅니다.
• 시스템 수준 (ASRL): ASRL 접근 방식은 모든 벤치마크에서 거의 완벽한 Top-1 정확도(대부분의 데이터셋에서 100%)를 달성했습니다. 논문은 그래프 수준의 검색이 단일 에이전트 선택보다 높은 재현율(recall)을 제공하고 의미론적 모호성을 줄여, 학습된 랭커가 올바른 서브그래프를 더 신뢰성 있게 식별할 수 있게 한다고 언급합니다.
• 확장성: 토큰 복잡도 분석에 따르면, 2단계 설계는 직접 검색과 동일한 빅오(big-O) 토큰 비용을 가지면서도 상당한 성능 향상을 제공하므로, 직접적인 LLM 스코어링이 계산적으로 불가능한 대규모 에이전트 풀에서도 실행 가능합니다.

의의 및 주장
본 논문은 효과적인 멀티 에이전트 오케스트레이션을 위해서는 고립된 에이전트 선택을 넘어 전체 서브그래프에 대한 추론과 **호출 트리 감독(call-tree supervision)**을 활용하는 방향으로 나아가야 한다고 주장합니다. 추천을 역사적 실행 구조에 기반함으로써, 제안된 프레임워크는 단순히 호환 가능한 도구 목록이 아닌 일관되고 실행 가능한 에이전트 팀을 구축할 수 있게 합니다. 저자들은 이 접근 방식이 대규모 MAS의 신뢰성, 조정 능력 및 엔드 투 엔드 실행 품질을 크게 향-상시킨다고 단언합니다.

또한 본 논문은 역사적 로그에 존재하는 편향(예: 인기 편향)의 증폭 및 마켓플레이스 다양성 감소 가능성과 같은 잠재적 위험을 인정하는 영향 성명서를 포함하고 있습니다. 이를 완화하기 위해 실제 배포 시 가용 집합 내에 명시적인 안전, 예산 및 정책 제약 조건을 포함해야 한다고 제안합니다.