Resumo Técnico: DPBench – Determinantes Estruturais da Coordenação de Multi-Agentes de LLM sob Contenção Simultânea de Recursos

1. Declaração do Problema

Os benchmarks existentes para sistemas de modelos de linguagem de grande escala (LLM) multi-agente avaliam primariamente o sucesso ao nível da tarefa sob um protocolo fixo. Eles medem se os agentes conseguem realizar um objetivo, mas não caracterizam as condições estruturais sob as quais a coordenação ocorre ou falha inteiramente. Este artigo aborda o modo de falha específico conhecido como deadlock (impasse): um estado onde múltiplos agentes reivindicam recursos compartilhados simultaneamente, resultando em uma espera circular que impede qualquer progresso.

Os autores adaptam o clássico problema dos Filósofos Comilões (Dijkstra, 1965) para um ambiente de teste controlado, o DPBench. A hipótese central é que a falha de LLMs multi-agentes em coordenar-se não é necessariamente um déficit nas capacidades de raciocínio dos modelos, mas sim um descompasso entre os agentes e o protocolo (as regras, a estrutura de comunicação e o tamanho do grupo que governa sua interação). O artigo investiga se a variação de variáveis de nível de protocolo pode resolver o deadlock em modelos que, de outra forma, falhariam.

2. Metodologia

O Ambiente (DPBench)

O ambiente é formalizado como um Processo de Decisão de Markov Parcialmente Observável Descentralizado (Dec-POMDP).

• Agentes: $N$ filósofos sentados em uma mesa circular, cada um precisando de dois garfos adjacentes para comer.
• Ações: GRAB_LEFT (Pegar Esquerda), GRAB_RIGHT (Pegar Direita), RELEASE (Liberar), WAIT (Esperar).
• Modos:
  • Simultâneo: Todos os agentes agem no mesmo passo de tempo (timestep). Conflitos (dois agentes solicitando o mesmo garfo) são resolvidos deterministicamente (o de menor índice vence). Este modo cria o potencial para um deadlock simétrico.
  • Sequencial: Os agentes agem em uma ordem fixa de round-robin dentro de um passo de tempo, quebrando a simetria naturalmente.
• Condições de Comunicação:
  • Nenhuma: Agentes agem baseados apenas no estado local.
  • Rodada única (Single-round): Agentes transmitem uma mensagem antes de se comprometerem com uma ação.
  • Múltiplas rodadas (k rodadas): Agentes envolvem-se em $k$ rodadas de negociação antes de se comprometerem.
• Métricas: Taxa de deadlock (binária), vazão (throughput - refeições por passo de tempo), equidade (fairness - baseada em Gini) e consistência entre mensagem e ação.

Configuração Experimental

• Modelos Avaliados: Cinco LLMs de fronteira (GPT-5.2, Claude Opus 4.5, Grok 4.1, Gemini 2.5 Flash, Llama 4 Maverick) e uma linha de base de escolha aleatória uniforme.
• Tamanho das Amostras: $n=30$ episódios para comparações entre modelos; $n=20$ para estudos de ablação.
• Variáveis de Protocolo: O estudo varia independentemente:
  1. Modo de Ação: Simultâneo vs. Sequencial.
  2. Comunicação: 0, 1, 3 ou 5 rodadas.
  3. Estratégia de Prompt: Mínimo, Padrão, Teoria da Mente, Quebra de Simetria, Ordenação de Recursos.
  4. Tamanho do Grupo ($N$): 5 vs. 10.

Variantes de Prompt

O estudo testa intervenções específicas de prompt correspondentes a soluções clássicas de concorrência:

• Ordenação de Recursos (Resource-Ordering): Impõe uma ordem global (ex: filósofos de índice par pegam a direita primeiro, filósofos de índice ímpar pegam a esquerda primeiro) para evitar esperas circulares.
• Quebra de Simetria (Symmetry-Breaking): Instrui os agentes a randomizarem o tempo de compromisso para evitar a captura sincronizada.
• Teoria da Mente (Theory-of-Mind): Incentiva o raciocínio sobre as intenções dos vizinhos sem especificar uma regra rígida.

3. Resultados Principais

Desempenho de Linha de Base (Protocolo Padrão)

Sob o prompt padrão sem comunicação e ação simultânea em $N=5$:

• Taxas de Deadlock: Variam significativamente por modelo, mas são altas no geral.
  • Gemini 2.5 Flash: 90,0% (IC 95% [74,4, 96,5])
  • Llama 4 Maverick: 76,7%
  • Grok 4.1: 70,0%
  • Claude Opus 4.5: 55,0%
  • GPT-5.2: 25,0% (O IC sobrepõe-se à linha de base aleatória de 13,3%)
• Modo Sequencial: Quatro dos seis agentes (incluindo a linha de base aleatória) alcançam 0,0% de deadlock. As duas anomalias (Claude Opus 4.5 com 60,0% e Grok 4.1 com 25,0%) exibem uma dependência excessiva da ação WAIT, levando a deadlocks de tempo limite (timeout) em vez de esperas circulares.
• Conclusão: Sob condições padrão, a maioria dos LLMs de fronteira não performa melhor do que o acaso na prevenção de deadlock simultâneo.

Intervenções de Protocolo (Modelo Fixo: Gemini 2.5 Flash)

Mantendo o modelo constante (Gemini 2.5 Flash, o pior executor), três variáveis estruturais reduziram independentemente o deadlock de ~90% para dentro do intervalo de confiança de zero:

1. Rodadas de Comunicação:

   • 0 Rodadas (Linha de Base): 90,0% de deadlock.
   • 1 Rodada: 86,7% de deadlock (estatisticamente indistinguível da linha de base).
   • 3 Rodadas: 0,0% de deadlock.
   • 5 Rodadas: 5,0% de deadlock.
   • Descoberta: Uma única rodada de mensagens é insuficiente; a negociação de múltiplas rodadas é necessária para convergir em intenções assimétricas.

2. Estratégia de Prompt:

   • Prompt Mínimo (Sem objetivo): 100% de deadlock.
   • Prompt Padrão: 90,0% de deadlock.
   • Prompt de Ordenação de Recursos: 0,0% de deadlock.
   • Prompt de Quebra de Simetria: 0,0% de deadlock.
   • Prompt de Teoria da Mente: 5,0% de deadlock.
   • Descoberta: Codificar primitivos de concorrência clássicos (ordenação de recursos ou quebra de simetria) no prompt elimina o deadlock inteiramente.

3. Tamanho do Grupo ($N$):

   • Aumentar $N$ de 5 para 10 reduziu o deadlock para o Gemini de 90,0% para 10,0%.
   • Descoberta: A configuração canônica de deadlock (cada agente segurando um garfo) é um dos muitos estados globais em $N$ maiores, tornando-a menos provável de ocorrer por acaso.

Resultados Nulos

• Memória: Fornecer aos agentes uma janela de memória de passos de tempo passados (3 ou 5 passos) sem comunicação de múltiplas rodadas não reduziu as taxas de deadlock.
• Mensagens de Rodada Única: Como observado, uma rodada de comunicação antes do compromisso não melhorou estatisticamente o desempenho em relação à linha de base.

4. Contribuições e Significância

O artigo afirma que a capacidade de coordenação de LLMs multi-agentes é determinada pelo protocolo, não pela capacidade inerente do modelo.

• Protocolo sobre Capacidade: O mesmo modelo (Gemini 2.5 Flash) que sofre deadlock 90,0% das vezes sob um protocolo padrão atinge 0,0% de deadlock quando o protocolo é alterado (via comunicação de múltiplas rodadas, estratégias de prompt específicas ou tamanho do grupo).
• Determinantes Estruturais: O estudo identifica três variáveis específicas de nível de protocolo que determinam o sucesso da coordenação:
  1. O número de rodadas de comunicação pré-compromisso (exigindo $\ge 3$).
  2. A estratégia de prompt de nível de coordenação (especificamente a codificação de primitivos de concorrência).
  3. O tamanho do grupo (grupos maiores reduzem a probabilidade de deadlock simétrico).
• Reenquadramento do Problema: Os autores argumentam que as falhas de LLMs multi-agentes neste domínio não são evidência de "fragilidade de raciocínio" no sentido tradicional, mas sim uma falha em seguir um protocolo que é simétrico e força o compromisso prematuro. Quando o protocolo é tornado livre de deadlock (como na teoria clássica da concorrência), os LLMs o seguem.
• Implicação de Design: Para profissionais que implantam sistemas multi-agentes, o esforço de engenharia deve focar no design do protocolo de coordenação (ex: forçar a ordenação de recursos ou permitir negociação de múltiplas rodadas) em vez de apenas selecionar um modelo mais capaz.

O artigo conclui que as condições estruturais para a ausência de deadlock estabelecidas na literatura de sistemas distribuídos clássicos (Dijkstra, 1965; Lamport, 1978) permanecem o nível correto de análise para a coordenação de LLMs multi-agentes.