Unifying Temporal and Structural Credit Assignment in LLM-Based Multi-Agent Prompt Optimization | AI Paper Digest

TL;DR Highlight

여러 AI 에이전트가 협력할 때 '어느 라운드의 어느 에이전트'가 실패했는지 정확히 짚어내서 그 프롬프트만 고치는 최적화 프레임워크

Who Should Read

여러 LLM 에이전트를 조합해 복잡한 추론 태스크를 처리하는 시스템을 개발 중인 AI 엔지니어. 특히 에이전트별 프롬프트 튜닝 전략을 고민하거나 멀티에이전트 파이프라인 성능이 기대에 못 미치는 상황에 처한 개발자.

Core Mechanics

멀티에이전트 시스템에서 마지막에 스코어 하나만 주는 '희소 보상' 문제를 해결하려면, 각 라운드와 각 에이전트의 기여도를 분리해서 봐야 한다는 게 핵심 전제.
각 라운드 끝에 Aggregation Module(에이전트 발화를 하나의 공유 상태로 요약하는 모듈)을 두면, 중간 상태가 명시적으로 생겨서 '언제 추론이 망가졌는지' 시간축으로 추적할 수 있다.
같은 역할(예: 비평가, 계획자)의 프롬프트를 모든 라운드에서 공유(Stationary Policy)하면 파라미터 수가 줄고, 역할별로 체계적 약점을 집계할 수 있어 Structural Credit 계산이 가능해진다.
Block Coordinate Descent(블록 좌표 하강법) 방식으로 역할 프롬프트와 집계 프롬프트를 번갈아 최적화한다. 한쪽을 고정한 채 다른 쪽만 수정하므로 동시 업데이트보다 훨씬 안정적.
LLM 기반 비평가(critic)가 '텍스트 gradient(자연어 피드백)'를 생성해서, 크레딧이 낮은 특정 에이전트나 특정 라운드의 프롬프트만 타겟 수정한다. 전체를 다 바꾸지 않는다.
Qwen2.5-7B-Instruct, LLaMA3-8B-Instruct, Gemma-7B-Instruct 세 모델에서 AQuA, MedMCQA, GPQA, MMLU 벤치마크 전반에 걸쳐 기존 블랙박스 최적화(DSPy MIPRO) 대비 일관된 성능 향상을 보였다.

Evidence

MedMCQA에서 LLaMA3-8B 기준 Debate 프레임워크: 베이스라인 55.13% → 크레딧 최적화 후 64.63%로 +9.50%p 향상.
MMLU에서 LLaMA3-8B Debate: 베이스라인 68.78% → 최적화 후 74.77%로 +6.00%p, DSPy MIPRO(+0.55%p)를 크게 앞섬.
예측 변화 분포 비교: DSPy MIPRO는 오답→정답 수정 7.00%, 정답→오답 퇴행 7.00%인 반면, 본 방법은 수정 11.00% / 퇴행 5.00%로 순이익이 확연히 높음.
수렴 속도: 크레딧 가이드 최적화는 수 번의 반복 내에 빠르게 수렴하고 분산이 낮은 반면, DSPy MIPRO는 수렴이 느리고 분산이 높아 탐색 비효율이 명확하게 드러남.

How to Apply

멀티에이전트 파이프라인을 구성할 때, 각 라운드 끝에 에이전트 출력을 하나의 공유 상태로 합치는 Aggregation 단계를 명시적으로 추가하라. 이 상태를 LLM 비평가로 채점하면 '몇 라운드에서 추론이 망가졌는지' 바로 파악할 수 있다.
에이전트 역할(예: Planner, Critic, Solver)마다 하나의 시스템 프롬프트를 공유하도록 설계하고, 여러 라운드에 걸친 채점 결과를 누적해 '최약체 역할 2개'만 선별해서 그 프롬프트를 교체하라. 전체를 동시에 바꾸면 오히려 성능이 불안정해진다.
블랙박스 프롬프트 최적화 도구(예: DSPy MIPRO)를 초기화 단계에만 쓰고, 이후 반복 최적화는 크레딧 기반 타겟 업데이트로 대체하면 쿼리 비용을 줄이면서도 정확도를 더 올릴 수 있다.

Code Example

snippet

Terminology

Credit Assignment Problem팀 게임에서 팀이 졌을 때 누구 탓인지 가려내기 어려운 것처럼, 여러 에이전트가 협력한 결과에서 각 에이전트의 기여/책임을 파악하는 문제.

Block Coordinate Descent산 정상을 찾을 때 x방향만 먼저 움직이고, 그다음 y방향만 움직이는 식으로 번갈아 최적화하는 방법. 동시에 모든 방향을 바꾸는 것보다 안정적.

Stationary Policy에이전트가 1라운드든 5라운드든 동일한 행동 원칙(프롬프트)을 유지하는 것. 라운드마다 다른 규칙을 쓰면 원인 분석이 불가능해지므로 고정.

Aggregation Module여러 에이전트의 발언을 받아 하나의 '현재 상태 요약'으로 압축하는 모듈. 회의 서기가 토론 내용을 요약하는 역할과 비슷.

Proxy Gradient수학적 미분이 불가능한 텍스트 공간에서 LLM 비평가가 대신 '이 방향으로 바꿔라'라는 자연어 피드백을 주는 것. 실제 gradient 대신 쓰는 대리 신호.

MDP (Markov Decision Process)현재 상태만 알면 미래를 결정할 수 있다는 가정 하에 순차적 의사결정을 모델링하는 수학적 틀. 체스처럼 현재 판세만 보고 다음 수를 결정하는 것과 유사.

Temporal Credit여러 라운드 중 '어느 라운드'가 최종 실패에 가장 큰 영향을 미쳤는지를 나타내는 점수. 시간축 책임 분배.

Structural Credit여러 에이전트 중 '어느 에이전트(역할)'가 성과에 얼마나 기여했는지를 나타내는 점수. 구조적(역할별) 책임 분배.

Related Papers

Related Resources

Original Abstract (Expand)

While Multi-Agent Systems (MAS) empower Large Language Models to tackle complex reasoning tasks through collaborative interaction, optimizing their dynamics remains a formidable challenge due to the discrete, non-differentiable nature of the computation graph and the sparsity of global supervisory signals. Existing black-box optimizers struggle to attribute trajectory-level failure to specific local components, resulting in inefficient, high-variance exploration. We argue that tractable MAS optimization needs structural inductive biases to disentangle error signals. We propose temporal and structural credit assignment, which decomposes the objective along two axes: (i) temporal credit, using state-space bottlenecks to identify critical rounds, and (ii) structural credit, using stationary role policies to isolate agent contributions. Leveraging these decomposed signals, we introduce a discrete, verbalized block coordinate descent algorithm for iterative refinement. Rather than indiscriminate global updates, it alternates between optimizing role prompts and aggregation protocols, using LLM-generated "proxy gradients" to target only the identified weak links. Across diverse reasoning benchmarks, our approach substantially reduces query complexity while improving performance, providing a principled and interpretable path toward self-improving MAS.