기술 요약: 다중 에이전트 코드 생성을 위한 검색 기반 토폴로지 선택 및 증명 가능한 예산 보존

문제 정의

코드 생성을 위한 다중 에이전트 대규모 언어 모델 (LLM) 시스템은 근본적인 라우팅 과제를 직면합니다: 수정 중인 코드의 구조적 복잡성에 기반하여 최적의 오케스트레이션 토폴로지 (예: 단일 모듈, 단일 전문가, 파이프라인/스웜, 또는 검색 중심) 를 결정하는 것입니다. 기존 시스템은 일반적으로 실제 코드베이스 구조를 참조하지 않고 표면적 쿼리 특징 (예: 정규식 분류기) 이나 작업 의존성 그래프를 사용하여 토폴로지를 선택합니다. 이로 인해 단순한 편집이 복잡한 파이프라인을 경유하거나 그 반대의 경우가 발생하는 "오라우팅 (misrouting)"이 발생하여 불필요한 효율성 패널티를 초래합니다. 또한, 에이전트 예산을 관리하기 위한 형식적 자원 대수 (formal resource algebras) 가 존재하지만, 이는 종종 동적 토폴로지 선택과 통합되지 않으며, 자원 보장은 주로 런타임이 아닌 정적 (static) 으로 강제되지 않습니다.

방법론: CODE-AGENT 및 RGAO

본 논문은 **검색 기반 적응형 오케스트레이션 (Retrieval-Guided Adaptive Orchestration, RGAO)**을 중심으로 한 다중 에이전트 프레임워크인 CODE-AGENT를 소개합니다. 이 시스템은 검색 신호가 오케스트레이션 결정에 직접적으로 반영되고, 자원 보존을 보장하는 형식적 예산 대수와 결합된 폐쇄 루프를 통해 작동합니다.

1. 계층적 코드 검색 및 복잡도 추출

라우팅 전에 시스템은 코드 저장소의 계층적 트리 인덱스 (루트 $\to$ 디렉토리 $\to$ 파일 $\to$ 심볼) 에 대해 검색 패스를 수행합니다.

• 검색 전략: 쿼리는 5 가지 유형 (식별자, 정확, 개념적, 의존성, 구조적) 으로 분류됩니다. 개념적 쿼리는 LATTICE(경로 점수 보정), KohakuRAG(다중 쿼리 재형성), PageIndex(LLM 기반 빔 서치) 를 결합한 다중 경로 융합 전략을 트리거하며, 상호 순위 융합 (Reciprocal Rank Fusion, RRF) 을 통해 융합됩니다.
• 복잡도 벡터 ($c$): 검색된 서브그래프에서 RGAO 는 1 밀리초 미만의 시간 내에 5 차원 구조적 복잡도 벡터를 추출합니다:
  $$c = (d_{dep}, n_f, n_s, h_t, \rho_x)$$
  여기서 $d_{dep}$는 최대 의존성 깊이, $n_f$는 파일 수, $n_s$는 심볼 수, $h_t$는 트리 깊이, $\rho_x$는 모듈 간 결합 비율입니다.

2. 검색 기반 적응형 오케스트레이션 (RGAO)

토폴로지 라우터는 복잡도 벡터 $c$와 사용자 쿼리를 4 가지 토폴로지 중 하나로 매핑하는 결정론적 임계값 분류기입니다:

• FASTPATH: 사소한 단일 파일 편집을 위한 단일 모듈 실행.
• SUBAGENT: 중간 범위 ($n_f \le 3$) 를 위한 단일 전문가 계약.
• MULTIAGENT: 복잡한 다중 파일 작업 ($n_f > 3$) 을 위한 선형 파이프라인 또는 병렬 스웜.
• DEEPRESEARCH: 모호한 쿼리를 위한 다단계, 검색 중심 실행.

3. 형식적 예산 대수 및 정적 검증

서브 에이전트는 형식적 계약 $\langle I, C, T, M \rangle$에 의해 관리되며, 여기서 $C$는 6 차원 예산 벡터 (반복 횟수, 호출, 토큰, 초, 재시도, 인수인계) 를 포함합니다.

• 예산 보존 정리 (Theorem 1): 이 논문은 특정 가정 (결정론적 도구 비용, 유한한 검색 깊이, 유한한 행동 공간) 하에서 위임 숲 (delegation forest) 의 총 자원 소비가 루트 예산에 의해 상한이 결정됨을 증명합니다.
• 정적 검증: VERIFYCONSERVATION 알고리즘은 모든 LLM 호출이 이루어지기 전에 $O(|V| + |E|)$ 시간 내에 예산 대수를 검증합니다. 이는 반응적이지 않고 정적으로 자원 초과를 방지하기 위해 자식 예산의 합과 직접 비용의 합이 부모 예산을 초과하지 않도록 보장합니다.

4. 실행 계층

이 시스템은 작업의 방향 비순환 그래프 (DAG) 를 구축하기 위해 SwarmSupervisor를 활용합니다. 이는 계약 존재 여부, 예산 가능성, 인수인계 무결성이라는 3 단계 사전 실행 프로토콜을 강제하며, 에이전트 간 통신을 위해 타입화된 SwarmArtifact 객체를 사용하여 조정 오버헤드를 $O(n^2)$에서 $O(k)$로 줄입니다.

주요 기여

1. 복잡도 조건부 토폴로지 라우터: 검색에서 파생된 코드 구조 신호를 오케스트레이션 결정에 매핑하는 라우터로, 정규식 기반 베이스라인에 비해 오라우팅률을 현저히 감소시킵니다.
2. 증명 가능한 예산 보존: 위임된 계약이 부모 한계를 초과하지 않도록 보장하는 구조적 귀납 정리 (Theorem 1) 로, DAG 크기에 비례하는 선형 시간으로 정적으로 검증됩니다.
3. 계층적 검색 엔진: 트리 구조 인덱스 위에 LATTICE, KohakuRAG, RepoGraph 스타일 의존성 확장을 결합한 새로운 조합으로, 라우팅 신호로서 특별히 사용됩니다.
4. 시스템 구성: 검색 조건부 라우팅과 정적 예산 검증을 통합한 것으로, 이는 어느 단일 구성 요소만으로는 달성할 수 없는 특성입니다.

실증 결과

평가 는 샌드박스화된 상호작용을 추상화하는 프록시 하네스 (evals/swebench_proxy.py) 를 사용하여 수행되었으며, 오염 우려 및 자원 제약으로 인해 전체 SWE-bench 실행은 후속 단계로 이월되었습니다.

• 라우팅 정확도: 250 개 인스턴스로 레이블이 지정된 데이터셋에서 RGAO 는 오라우팅을 30.1% (정규식 베이스라인) 에서 8.2% (95% 윌슨 신뢰구간 [6.1, 10.9]) 로 감소시켰으며, 이는 통계적으로 유의미한 개선입니다 (쌍체 맥네마 검정, $p < 10^{-6}$).
• 성능 오버헤드:
  • DAG 구축: 1 밀리초 미만 (< 0.01 ms).
  • 트리 인덱스 구축 (200 개 파일, 2,002 개 노드): 11.1 ms.
  • 계약 팩토리 인스턴스화: 약 1.1 $\mu$s.
  • 예산 확인 오버헤드: 약 0.65 $\mu$s.
• 파이프라인 정확도: 시스템은 개입 복구 시나리오를 포함한 5 가지 복합 다중 에이전트 파이프라인의 100% 를 완료했으며, 파이프라인당 평균 토큰 비용은 약 6,000 토큰이었습니다.
• 프록시 벤치마크: CODE-AGENT 는 합성 SWE-bench 세트의 40% 를 pass@1 로 해결하여, 제약이 없는 단일 모듈 에이전트 (8~20 배 토큰 감소) 에 비해 효율성을 입증했습니다.

중요성 및 주장

이 논문은 그 주요 중요성이 복잡도 조건부 LLM 라우팅과 형식적 자원 대수라는 두 개의 이전에는 분리된 연구 흐름의 **구성 (composition)**에 있다고 주장합니다.

• 신규성: 복잡도 조건부 라우팅이나 형식적 예산 대수 중 어느 하나만으로는 "검색 조건부 동적 토폴로지 선택 하의 증명 가능한 예산 보존"이라는 특성을 산출하지 못합니다.
• 안전성 및 효율성: 정적 검증 메커니즘은 실행 전에 실행 불가능한 구성을 거부하여 에이전트 오류의 "파괴 반경 (blast radius)"을 제한하고, 자원 제약 환경에서 에이전트 기반 코드 생성의 비용 장벽을 낮춥니다.
• 해석 가능성: 학습된 라우팅 정책과 달리 RGAO 라우터는 구조적 신호에 기반한 해석 가능하고 수동으로 조정된 임계값을 사용하여 계약 기반 안전성 스토리와 일치합니다.

저자들은 엄격한 보존 정리를 위한 결정론적 비용 가정의 의존성 (확률적 비용에 대한 기대 상한은 제공됨) 과 학습된 후속자가 아닌 수동 조정 임계값의 현재 사용과 같은 한계를 인정합니다. 또한, 트리-시터 (tree-sitter) 문법이 복잡도 벡터를 저하시킬 수 있는 미숙한 언어와 같은 분포 변화 (distribution shifts) 하에서는 라우팅 이점이 축소된다고 지적합니다.