Resumo Técnico: Reset and Discard (ReD) para Inferência de LLM

Declaração do Problema

Grandes Modelos de Linguagem (LLMs) são cada vez mais avaliados em tarefas verificáveis (ex: codificação, matemática, provas formais) usando a métrica pass@k, que mede a probabilidade de resolver uma única instância corretamente dentro de $k$ tentativas. Observações empíricas indicam que, para muitas tarefas, a taxa de falha ($1 - \text{pass@k}$) decai seguindo uma lei de potência em relação a $k$ (ou seja, $1 - \text{pass@k} \propto k^{-\alpha}$).

No entanto, em cenários de inferência prática com um orçamento global fixo (medido em tentativas, tokens ou USD), o objetivo relevante não é a taxa de sucesso em um único problema, mas sim a coverage@cost (cobertura por custo): o número esperado de problemas únicos resolvidos dado um recurso total restrito. A política de alocação padrão, solve-to-completion (tentar repetidamente um único problema até que seja resolvido antes de passar para o próximo), é ineficiente sob distribuições de dificuldade de lei de potência. Problemas difíceis consomem um número desproporcional de tentativas, o que leva esta política a um crescimento sublinear na coverage@cost quando o expoente da lei de potência $\alpha < 1$ (um achado empírico comum). Isso resulta em retornos decrescentes, onde o orçamento adicional gera cada vez menos problemas resolvidos.

Metodologia: Reset-and-Discard (ReD)

Os autores propõem o Reset-and-Discard (ReD), uma política de alocação que otimiza o throughput global ao tratar o processo de inferência como uma busca em largura (breadth-first search) através de um conjunto de problemas.

O Protocolo ReD

1. Reset (Reiniciar): Em vez de persistir em um único problema até resolvê-lo, o sistema tenta cada problema por um número fixo de tentativas $\tau$ (no caso ótimo, $\tau=1$, ou seja, cada tentativa é uma nova tentativa).
2. Discard (Descartar): Se um problema for resolvido dentro de $\tau$ tentativas, ele é imediatamente removido da fila.
3. Rotation (Rotação): Se um problema não for resolvido após $\tau$ tentativas, ele é movido para o final da fila, e o sistema procede imediatamente para o próximo problema disponível.

Estrutura Teórica

O artigo estabelece um mapeamento matemático entre pass@k e coverage@cost usando a teoria de renovação.

• Política Padrão: Para uma distribuição de dificuldade onde $P(p) \sim p^{\alpha-1}$ (levando ao pass@k de lei de potência), o número esperado de tentativas para resolver um problema, $E[T]$, diverge se $\alpha < 1$. Consequentemente, a cobertura por custo cresce de forma sublinear ($\propto t^\alpha$).
• Política ReD: Ao reiniciar a cada $\tau$ tentativas, o número efetivo de tentativas para resolver um problema, $E[T_\tau]$, torna-se finito, independentemente da distribuição de dificuldade subjacente.
  • Se $0 < \alpha < 1$, o ReD transforma o crescimento da coverage@cost de sublinear para linear ($\propto t$).
  • Se $\alpha > 1$, o ReD mantém o crescimento linear, mas com uma inclinação mais acentuada (maior eficiência) do que a política padrão.
• Otimalidade: Os autores provam que reiniciar a cada tentativa ($\tau=1$) é a estratégia ótima para minimizar o número esperado de tentativas por problema resolvido para qualquer distribuição de dificuldade. Isso se mantém mesmo com verificadores imperfeitos, desde que a soma das taxas de Falso Negativo e Falso Positivo seja menor que 1.

Inferência de Leis de Escala

O artigo também demonstra que as trajetórias de ReD podem ser usadas para inferir o expoente da lei de potência $\alpha$ sem exigir avaliações caras de grande-$k$. À medida que o ReD avança pelas rodadas, a distribuição dos problemas restantes não resolvidos converge para uma distribuição Beta. Ao analisar a razão entre os problemas restantes entre as rodadas, $\langle R_n \rangle / \langle R_{n+1} - R_n \rangle$, é possível estimar linearmente $\alpha$.

Principais Contribuições

1. Conexão de Métricas: Derivou um mapeamento exato de pass@k para coverage@cost, caracterizando como o comportamento de pass@k de lei de potência ($0 < \alpha < 1$) induz o crescimento sublinear em esquemas de alocação padrão.
2. Algoritmo ReD: Propôs e provou a otimalidade da estratégia de Reset-and-Discard. Ele garante o crescimento linear na coverage@cost para $\alpha < 1$ e melhora a eficiência para $\alpha > 1$.
3. Garantias Teóricas: Provou que o ReD maximiza estritamente a recompensa esperada por tentativa para qualquer distribuição de dificuldade e permanece robusto contra ruído de verificador.
4. Inferência de Expoente: Desenvolveu um método para estimar expoentes de escala de inferência diretamente de execuções de ReD, evitando a necessidade de amostragem custosa de grande-$k$.
5. Validação Empírica: Demonstrou melhorias substanciais em três LLMs (Llama-3.1-8b, Llama-3.3-70b, GPT-oss-20b) e três benchmarks (HumanEval, GSM8K, MMLU-Pro).

Resultados Experimentais

Os experimentos foram conduzidos no dataset HumanEval (codificação), GSM8K (matemática) e MMLU-Pro (raciocínio).

• Eficiência: O ReD reduziu significativamente o número de tentativas, tokens e custo em USD necessários para atingir uma cobertura alvo em comparação ao solve-to-completion.
• Comparação de Modelos: No benchmark HumanEval, o ReD aplicado a um modelo menor (Llama-3.1-8b) superou a alocação padrão de um modelo muito maior (Llama-3.3-70b) em termos de tentativas e tokens até aproximadamente 90% de cobertura. Em termos de custo em USD, o ReD no modelo 8b foi a estratégia mais econômica em todos os níveis de cobertura.
• Inferência de Lei de Escala: Usando ReD no modelo 8b, os autores inferiram com sucesso um expoente de lei de potência de $\alpha \approx 0,34$, que coincidiu com o expoente derivado de medições de pass@k de alto-$k$.
• Robustez: A vantagem do ReD foi mantida mesmo ao simular verificadores ruidosos.

Significância e Alegações

O artigo afirma que o ReD oferece uma mudança fundamental na forma como o computacional de inferência é alocado para tarefas verificáveis.

• De "Pagamento por Token" para "Resultado como Serviço": O ReD permite que os sistemas foquem recursos computacionais na "fronteira de aprendizado" (problemas que são solucionáveis em poucas tentativas) em vez de desperdiçar recursos em instâncias difíceis que exigem retornos decrescentes.
• Roteamento Hierárquico: A metodologia suporta estratégias híbridas eficientes, onde modelos menores lidam com a maior parte dos problemas via ReD, e apenas os problemas não resolvidos são roteados para modelos maiores e mais caros.
• Aplicabilidade Geral: A abordagem é aplicável a qualquer pipeline que suporte amostragem repetida e verificação, proporcionando uma melhoria comprovável no throughput sem exigir mudanças na arquitetura ou treinamento do modelo.

Os autores mantêm a modéstia quanto ao escopo, observando que o ReD é projetado especificamente para tarefas verificáveis, onde a correção da solução pode ser avaliada automaticamente. Eles não alegam aplicabilidade a tarefas de geração não verificáveis nem propõem a integração de preditores de dificuldade aprendidos como parte deste trabalho.