Hybrid Verified Decoding: Learning to Allocate Verification in Speculative Decoding

Resumo Técnico: Decodificação Híbrida Verificada

Definição do Problema
A geração de Grandes Modelos de Linguagem (LLMs) é limitada pela natureza sequencial da decodificação autorregressiva, onde cada novo token requer uma passagem completa (forward pass) sobre o prefixo atual e o cache de Chave-Valor (KV). A decodificação especulativa aborda isso propondo tokens candidatos por meio de uma fonte de "rascunho" (draft) e verificando-os em um único passo com o modelo alvo. No entanto, a eficiência da decodificação especulativa depende da "taxa de aceitação" — o número de tokens propostos que o modelo alvo aceita.

Fontes de rascunho livres de parâmetros (ex: caches de sufixo, recuperação) oferecem propostas de baixo custo ao reutilizar continuações de prompts ou do histórico de geração, mas sofrem de uma limitação crítica: uma correspondência de cache que parece promissora em um passo de geração pode resultar em um prefixo aceito muito curto no passo seguinte devido a variações dependentes de estado (ex: argumentos diferentes para uma chamada de ferramenta similar). Verificar um rascunho de cache de baixo rendimento acarreta overhead sem ganho significativo de velocidade. Métodos adaptativos existentes frequentemente ajustam estruturas ou orçamentos de rascunho, mas não preveem explicitamente o rendimento (comprimento aceito) de um rascunho livre de parâmetros antes de comprometer a verificação.

Metodologia: Decodificação Híbrida Verificada
Os autores propõem a Decodificação Híbrida Verificada, um framework que trata a seleção de rascunho como um problema de alocação de verificação guiada pelo rendimento. Em vez de verificar cegamente cada rascunho de cache ou depender exclusivamente de um gerador baseado em modelo, o sistema prevê o comprimento aceito esperado de um rascunho de cache antes da verificação.

1. Rascunho de Dupla Fonte: O sistema mantém duas fontes de rascunho:
   • Gerador Baseado em Cache ($D_C$): Um mecanismo livre de parâmetros (instanciado como SuffixDecoding) que propõe continuações ao encontrar correspondências de sufixos no prompt de entrada e no histórico de geração.
   • Gerador Baseado em Modelo ($D_m$): Um gerador aprendido (especificamente o EAGLE3) usado como contingência (fallback).
2. Previsão de Rendimento: Antes da verificação, um preditor de rendimento leve ($g_\theta$), implementado como um MLP (perceptron de múltiplas camadas), estima o comprimento aceito ($\hat{y}_t$) do rascunho de cache atual.
   • Características: O preditor recebe um vetor de características de tempo de execução ($\phi_t$) que inclui a correspondência de sufixo, o comprimento do rascunho, a posição de decodificação atual, o histórico recente e indicadores de estrutura de tokens.
   • Regra de Decisão: Se o rendimento previsto $\hat{y}_t$ exceder um limiar $\tau$, o rascunho de cache é enviado para verificação. Caso contrário, o sistema recorre ao gerador baseado em modelo.
3. Treinamento via Replay de Traço: O preditor é treinado por meio de um procedimento de replay. Para cada posição de token em um traço de geração do modelo alvo, o sistema reconstrói o estado, gera um rascunho de cache e calcula o comprimento aceito "oracle" ($y_t$) comparando o rascunho contra a continuação real do modelo alvo. O modelo é treinado via regressão para minimizar o erro quadrático entre o rendimento previsto e o real.

Principais Contribuições

• Formulação: O artigo formula a seleção de rascunho dependente de estado como um problema de alocação de verificação guiada pelo rendimento, definindo o "comprimento aceito" como a variável principal de rendimento.
• Algoritmo: Introduz a Decodificação Híbrida Verificada, que alterna dinamicamente entre o rascunho baseado em cache e o baseado em modelo com base em uma estimativa de rendimento pré-verificação.
• Procedimento de Treinamento: Propõe um método de treinamento leve baseado em replay que deriva sinais de supervisão diretamente de traços de geração sem exigir treinamento adicional do modelo para o preditor.
• Avaliação Abrangente: O método é avaliado em três LLMs (Qwen3-8B, Qwen3-4B, Llama3.1-8B) e dezesseis conjuntos de dados abrangendo fluxos de trabalho de agentes, codificação, geração estruturada e chat aberto.
• Integração de Sistema: Os autores fornecem uma análise sistemática de oportunidades de cache, rendimentos de verificação e custos de execução, incluindo um protótipo de serviço vLLM para validação de implantação.

Resultados

• Desempenho: Em 48 pares de modelo-conjunto de dados, a Decodificação Híbrida Verificada supera a Decodificação Greedy em 47 casos e o SuffixDecoding em 46 casos.
• Aceleração (Speedup): O método alcança uma aceleração média de 2.73x sobre o EAGLE3 (um forte baseline baseado em modelo) em todas as configurações.
• Cargas de Trabalho Agênticas: A abordagem é particularmente eficaz em tarefas de agentes e edição de fluxo de trabalho (ex: Delegate-52, InstructEdit), onde supera consistentemente o EAGLE3 e outros baselines. Essas cargas de trabalho se beneficiam de padrões estruturais recorrentes que o cache explora, enquanto o preditor filtra discrepâncias dependentes de estado.
• Eficiência: A análise mostra que o método reduz significamente o número de ciclos de decodificação por 1.000 tokens (ex: de 571 para o EAGLE3 para 200 para a Decodificação Híbrida Verificada no Llama3.1-8B) mantendo custos por ciclo comparáveis ao rascunho baseado em modelo.
• Precisão do Preditor: O preditor de rendimento identifica com sucesso rascunhos de alto rendimento (definidos como comprimento aceito $\ge 6$) com precisão variando de 78,2% a 87,6% e recall de 61,4% a 79,8% entre diferentes modelos.

Significância e Alegações
O artigo argumenta que o principal gargalo na decodificação especulativa não é apenas a qualidade do rascunho, mas o momento da decisão de verificação. Ao prever o rendimento de um rascunho livre de parâmetros antes da verificação, a Decodificação Híbrida Verificada evita o overhead de verificar correspondências de cache de baixo valor.

Os autores alegam que esta abordagem aponta para a seleção de rascunho em tempo de execução como uma direção promissora para a decodificação especulativa. Eles demonstram que a estrutura do prompt cria oportunidades de cache, mas os rascunhos de alto rendimento estão concentrados em um subconjunto pequeno do espaço de rascunho. O preditor aprendido isola efetivamente essas oportunidades de alto valor, permitindo que o sistema amortize os custos de verificação sobre prefixos aceitos mais longos. Os resultados sugerem que, para cargas de trabalho estruturadas e agênticas, uma abordagem híbrida guiada pela estimativa de rendimento pode superar significativamente as estratégias puramente baseadas em modelo ou puramente baseadas em cache.