Long-Horizon Plan Execution in Large Tool Spaces through Entropy-Guided Branching

Título: Execução de Planos de Longo Alcance em Grandes Espaços de Ferramentas Através de Ramificação Guiada por Entropia

1. O Problema

Os Modelos de Linguagem de Grande Escala (LLMs) têm avançado significativamente na criação de agentes autônomos capazes de interagir com ferramentas e APIs externas. No entanto, a execução de tarefas complexas que exigem planejamento de longo alcance (long-horizon) dentro de bibliotecas massivas de ferramentas enfrenta dois gargalos críticos:

1. Falta de Frameworks de Avaliação Rigorosos: As benchmarks existentes são inadequadas. Muitas usam conjuntos de ferramentas limitados que não refletem a escala real, enquanto outras focam apenas em chamadas de ferramentas de um único passo, ignorando dependências sequenciais. Além disso, a avaliação de nível de plano frequentemente depende de juízes subjetivos (LLM-as-a-judge), que penalizam trajetórias válidas, mas alternativas, falhando em medir a capacidade real de conclusão de tarefas.
2. Ineficiência Computacional na Exploração: Os métodos atuais de agentes (como ReAct ou Reflexão) lutam para navegar em espaços de decisão vastos. Abordagens baseadas em busca, como a Busca em Árvore de Monte Carlo (MCTS), tornam-se computacionalmente proibitivas em cenários com muitas ferramentas e muitos passos, devido ao custo de explorar exaustivamente todas as possibilidades.

2. Metodologia

Os autores propõem uma solução dupla composta por um novo benchmark de avaliação e um novo algoritmo de busca.

A. SLATE (Synthetic Large-scale API Toolkit for E-commerce)

Para superar as limitações das benchmarks atuais, os autores introduzem o SLATE, um benchmark sintético de grande escala focado em cenários de comércio eletrônico.

• Estrutura: Cada instância consiste em uma consulta complexa do usuário, um plano de execução hierárquico e um conjunto de ferramentas.
• Simulação Determinística: Diferente de benchmarks que dependem de julgamento subjetivo, o SLATE utiliza um Simulador de Execução de Ferramentas. Este simulador gera saídas determinísticas baseadas em contextos reais, permitindo uma avaliação automática e objetiva do sucesso do plano final (correspondência exata com o estado desejado), independentemente da trajetória intermediária.
• Escala: O dataset contém 1.000 ferramentas e tarefas com mais de 10 passos, cobrindo 12 categorias de domínio (ex: gerenciamento de pedidos, logística, promoções).

B. Ramificação Guiada por Entropia (EGB - Entropy-Guided Branching)

Motivados pelas falhas observadas nos agentes atuais ao usar o SLATE, os autores propõem o EGB, um algoritmo de busca que equilibra exploração e exploração de forma adaptativa.

• Princípio Central: O algoritmo utiliza a entropia preditiva (incerteza) do modelo como um sinal para decidir onde buscar alternativas.
• Fase 1 (Exploração Inicial): O agente executa o plano passo a passo. Em cada subetapa, ele gera múltiplas amostras de ações candidatas (ou usa logits, se disponível) para calcular a distribuição de probabilidade das ferramentas. A ação majoritária é executada, e a entropia dessa distribuição é registrada.
• Fase 2 (Ramificação Seletiva): Se o plano inicial falhar, o EGB não reinicia do zero nem explora aleatoriamente. Em vez disso:
  1. Classifica os passos falhos por entropia decrescente (os passos onde o modelo estava mais inseguro).
  2. Ramifica (cria novos ramos de execução) apenas a partir dos passos de maior incerteza, substituindo a ferramenta escolhida por alternativas plausíveis da distribuição amostrada.
  3. Reexecuta o restante do plano a partir desse novo ponto, mantendo o histórico de observações atualizado.
• Vantagem: Ao contrário do MCTS, que constrói árvores completas e caras, o EGB foca a computação apenas nos pontos de decisão críticos onde a incerteza é alta, evitando buscas exaustivas desnecessárias.

3. Principais Contribuições

1. SLATE: A primeira benchmark que combina simultaneamente: (a) Espaços de ferramentas grandes (>1.000), (b) Execução de longo alcance (>10 passos), (c) Resultados determinísticos passo a passo e (d) Avaliação de plano baseada em estado final.
2. Algoritmo EGB: Uma estratégia de busca que é "consciente da incerteza". Ela demonstra que ramificar apenas quando a entropia é alta é mais eficiente do que buscar cegamente ou usar árvores completas.
3. Análise Empírica: O estudo revela que agentes atuais falham principalmente na auto-correção em espaços de ação grandes e que a história de execução ajuda na seleção de ferramentas, mas pouco na decisão de se chamar uma ferramenta.

4. Resultados Experimentais

Os experimentos foram conduzidos no SLATE usando modelos como o Claude-4-Sonnet (caixa preta) e Qwen2.5-7B (caixa branca).

• Desempenho em Nível de Plano:
  • O EGB-Sampling alcançou uma taxa de sucesso de execução de 54,0%, superando significativamente o ReAct (29,3%) e o Reflexion (44,7%).
  • O EGB-Logits (usando logits internos para calcular entropia) atingiu 67,8% de sucesso, superando todos os baselines.
  • O EGB superou o método baseado em MCTS (LATS) em 17,5% no nível de plano, apesar de usar um orçamento computacional comparável ou menor.
• Eficiência Computacional:
  • O EGB é mais eficiente que o Reflexion e o LATS. Por exemplo, o EGB-Logits foi 2,8 vezes mais rápido que o Reflexion e reduziu o uso de tokens de saída em 73%.
  • O uso de ramificação seletiva evita o custo proibitivo de reexecutar todo o plano para cada tentativa de correção.
• Correlação Entropia-Erro: A análise mostrou uma forte correlação: passos com alta entropia têm taxas de erro significativamente maiores (até 95% em faixas de alta entropia), validando a entropia como um sinal confiável para direcionar a busca.
• Validação Cruzada: Testes em outras benchmarks (UltraTool) confirmaram que o EGB mantém o desempenho superior com custos de tokens muito menores que o LATS.

5. Significado e Impacto

Este trabalho estabelece uma nova fundação para o desenvolvimento de agentes LLM robustos em ambientes ricos em ferramentas:

• Padrão de Avaliação: O SLATE oferece um protocolo de avaliação rigoroso e automatizado, essencial para medir o progresso real em tarefas complexas, eliminando a dependência de juízes subjetivos.
• Eficiência Prática: O EGB demonstra que é possível alcançar alta precisão em tarefas de longo alcance sem o custo computacional exorbitante de buscas exaustivas. Isso torna a implantação de agentes autônomos em cenários do mundo real (como e-commerce, desenvolvimento de software e descoberta científica) mais viável e escalável.
• Mecanismo de Auto-Correção: A abordagem valida que a incerteza do modelo (entropia) é um indicador superior para guiar a correção de erros do que simplesmente tentar novamente ou buscar aleatoriamente.

Em resumo, o artigo resolve o dilema entre a necessidade de explorar grandes espaços de decisão e a limitação de recursos computacionais, propondo uma solução inteligente que foca os esforços de busca exatamente onde o modelo está mais confuso.