Bilevel Coordinated Reflection: A Game-Theoretic Approach to Multi-Agent LLM Systems

Multi-agent LLM systems commonly use an orchestrator to decompose a task for a team of workers and then improve through textual reflection. Despite strong empirical results, these systems lack a unified account of coordination, memory improvement, and the role of external verification. We model orchestrator-worker interaction as a bilevel coordination game: under bounded coupling, the workers' local-update game is an approximate potential game whose equilibrium slack is controlled by decomposition quality. We then analyse reflection as stochastic movement over semantic memory states. For free-form reflection, we derive a finite-time upper bound, prove worst-case tightness, and give a positive lower bound under a falsifiable persistent-harm condition. We further prove an information-theoretic impossibility result: no gate that observes only the generated transcript can improve uniformly over text-indistinguishable environments, whereas an environment-grounded gate can. Motivated by this separation, we introduce Stochastic Reflective Memory Ascent (SRMA), which accepts a candidate memory only after a grounded evaluation risk strictly decreases. Under calibration and non-degenerate corrective mass, SRMA converges exactly, geometrically or polynomially; matching constructions show that both rate regimes are order-tight. We also provide confidence gating for stochastic evaluation and re-anchoring guarantees for piecewise-stationary environments. Experiments instantiate these objects with environment-grounded metrics and test the predicted coordination and drift laws. On 500 SWE-bench instances, the complete Kimi-based system resolves 72.2% versus a 70.8% public mini-SWE-agent reference. Code: https://github.com/YihangChen9/Bilevel-Coordinated-Reflection

한 줄 요약

다중 에이전트 LLM 시스템에서 SRMA 알고리즘을 도입하여 반영 과정을 게임 이론적 구조로 모델링하고, 72.2%의 SWE-bench 성능 달성.

핵심 기여도

Orchestrator-Worker 상호작용을 **bilevel coordination game**으로 모델링하여, 분해 품질이 균형 편차를 제어함을 증명.
**SRMA (Stochastic Reflective Memory Ascent)** 알고리즘 제안: grounded evaluation risk 감소 후에만 메모리 업데이트를 허용.
**72.2%**의 SWE-bench 성능 달성 (기존 mini-SWE-agent 대비 +1.4% 개선).
**Information-theoretic impossibility theorem** 증명: transcript-only 게이트는 text-indistinguishable 환경에서 개선 불가.

핵심 아이디어

기존 다중 에이전트 LLM 시스템은 반영(textual reflection)을 통해 성능을 향상시키지만, 이 과정의 전략적 근거와 메모리 향상 메커니즘에 대한 이론적 설명이 부족했다. 본 연구는 orchestrator-worker 상호작용을 **bilevel coordination game**으로 모델링하여, **bounded coupling** 하에서 worker들의 local-update 게임이 **approximate potential game**이 되고, 그 균형 편차가 **분해 품질**에 의해 제어됨을 수학적으로 증명했다. 또한, 반영 과정을 **semantic memory state** 상의 확률적 이동으로 모델링하고, **free-form reflection**에 대해 **finite-time upper bound**와 **positive lower bound**를 유도했다. 이는 반영이 무한히 반복되더라도 수렴하지 않을 수 있음을 시사한다.

기술적 접근법

**Bilevel coordination game** 모델: orchestrator의 분해 품질이 worker들의 균형 편차를 제어.
**SRMA 알고리즘**: grounded evaluation risk가 감소할 때만 메모리 업데이트를 허용.
**Confidence gating**: 확률적 평가를 위한 신뢰 기반 메커니즘.
**Re-anchoring**: piecewise-stationary 환경에서의 수렴 보장.
**Kimi-based system** 사용, **SWE-bench** 데이터셋에서 실험.

주요 결과

**SWE-bench** 데이터셋에서 **Kimi-based system**이 500개 인스턴스 중 **361개 (72.2%)** 해결.
기존 **mini-SWE-agent v2** 대비 **+1.4%** 개선 (70.8% → 72.2%).
**Resource Contest**, **Overcooked** 환경에서 이론적 예측과 일치하는 **coordination**, **drift**, **grounding** 메커니즘 검증.

의의 및 한계

**SRMA**는 반영 과정을 정보 기반의 정량적 메커니즘으로 정의하여, 기존 텍스트 기반 반영의 한계를 극복.
**Information-theoretic impossibility theorem**은 텍스트만으로는 외부 상태에 의존하는 반영을 평가할 수 없음을 이론적으로 입증.
한계로는 **SRMA의 grounded evaluation**이 외부 환경에 의존하므로, 환경이 제공되지 않는 경우 적용이 어려울 수 있음.

실용적 활용

SRMA는 **소프트웨어 엔지니어링**, **자동화된 시스템 디버깅**, **복합적 문제 해결** 등에서 다중 에이전트 LLM 시스템의 반영 과정을 구조화하고 성능을 향상시키는 데 활용 가능. 특히 **SWE-bench**와 같은 실제 코드 기반 작업에서 실질적 개선을 보여주며, 산업 현장에서의 적용 가능성이 높음.