SpecTr-GBV: Multi-Draft Block Verification Accelerating Speculative Decoding

1. Formulação do Problema

Os Modelos de Linguagem de Grande Escala (LLMs) autoregressivos sofrem com alta latência de inferência devido à sua natureza de geração sequencial de tokens, onde cada token exige uma passagem frontal completa. A Decodificação Especulativa (SD) mitiga isso utilizando um modelo "rascunho" menor para propor tokens candidatos, que são então verificados por um modelo "alvo" maior.

No entanto, os métodos existentes de SD enfrentam duas limitações distintas quando tratados isoladamente:

• Limitações de Rascunho Único: A SD padrão utiliza apenas uma sequência de rascunho, levando a baixas taxas de aceitação.
• Compromisso entre Múltiplos Rascunhos e Verificação de Bloco:
  • Métodos de Múltiplos Rascunhos (ex: SpecTr): Geram múltiplas sequências de rascunho independentes para aumentar o pool de candidatos. No entanto, eles tipicamente verificam tokens posição por posição (coluna a coluna). Essa verificação sequencial para assim que um token é rejeitado em uma posição específica, falhando em maximizar o número total de tokens aceitos em uma iteração.
  • Métodos de Verificação de Bloco (ex: GBV): Verificam blocos inteiros de tokens conjuntamente, em vez de token por token, alcançando aceitação ótima para um único rascunho. Contudo, não aproveitam os benefícios de múltiplas sequências de rascunho.

A Questão Central: Os benefícios da geração de múltiplos rascunhos (aumentando a diversidade de candidatos) e da verificação de bloco gulosa (otimizando a aceitação dentro de um bloco) podem ser unificados para alcançar o comprimento de aceitação máximo teórico?

2. Metodologia: SpecTr-GBV

Os autores propõem o SpecTr-GBV, um framework que unifica a geração de múltiplos rascunhos com a Verificação de Bloco Gulosa (GBV).

Conceito Central

Em vez de verificar tokens posição por posição (como no SpecTr) ou verificar um único bloco (como no GBV), o SpecTr-GBV:

1. Gera $K$ sequências de rascunho independentes e identicamente distribuídas (i.i.d.) de comprimento $L$.
2. Formula o passo de verificação como um problema de Transporte Ótimo (OT) entre o conjunto de $K$ blocos de tokens de rascunho e o bloco de tokens alvo.
3. Itera através das $K$ sequências de rascunho para encontrar o sub-bloco aceito mais longo entre todos os rascunhos.

Procedimento Algorítmico

O processo de verificação (Algoritmo 1) opera da seguinte forma:

1. Inicialização: Começa com um comprimento de aceitação $\tau = 0$. Mantém um conjunto $H$ de sub-blocos rejeitados para evitar amostragem redundante.
2. Iteração Sequencial: Itera através de cada uma das $K$ sequências de rascunho ($x^L_1, \dots, x^L_K$).
3. Verificação de Sub-bloco: Para uma sequência atual, verifica sub-blocos começando da posição $\tau + 1$.
   • Calcula a probabilidade de aceitação $h_{ik}$ para um sub-bloco $x^i_k$ usando uma fórmula derivada (Eq. 2) que leva em conta a probabilidade conjunta do sub-bloco através de todos os $K$ rascunhos.
   • Se aceito, atualiza $\tau$ para o novo comprimento e registra o índice da sequência.
   • Se rejeitado, adiciona o sub-bloco ao conjunto $H$ e o ignora em iterações futuras.
4. Terminação:
   • Se todo o bloco de um rascunho for aceito, amostra um token de correção do modelo alvo.
   • Se o processo parar no comprimento $\tau < L$, amostra um token de correção de uma distribuição residual (Eq. 4) para garantir fidelidade distribucional.
5. Modificação da Distribuição: Antes da próxima iteração de SD, a distribuição alvo é modificada para posições não aceitas (Algoritmo 2) para manter consistência com a distribuição original do modelo alvo.

Fundamentação Teórica

• Formulação de Transporte Ótimo: O método é enquadrado como a minimização de uma função de custo sobre Acoplamentos Condicionalmente Independentes (CIC).
• Optimalidade: Os autores provam que o SpecTr-GBV alcança o comprimento de aceitação esperado ótimo fisicamente alcançável dentro do framework de geração de rascunhos i.i.d.
• Monotonicidade: O limite superior teórico no comprimento de aceitação esperado aumenta estritamente à medida que o número de rascunhos ($K$) aumenta.

3. Contribuições Principais

1. Framework Unificado: O SpecTr-GBV é o primeiro método a unificar estratégias de múltiplos rascunhos e verificação de bloco em um único framework, estendendo o GBV de configurações de rascunho único para configurações de múltiplos rascunhos.
2. Garantias Teóricas:
   • Prova que o método preserva a distribuição de saída do modelo alvo.
   • Prova que alcança o comprimento de aceitação esperado máximo possível para um número fixo de rascunhos.
   • Demonstra que esse limite ótimo melhora à medida que o número de rascunhos aumenta.
3. Eficiência:
   • Reduz a complexidade computacional por passo de seleção para $O(|\Omega|)$ (onde $|\Omega|$ é o tamanho do vocabulário), o que é mais eficiente que a busca binária $O(|\Omega| \log K)$ do SpecTr para fatores de escala.
   • Elimina a necessidade de soluções caras de programação linear para o problema de OT.

4. Resultados Experimentais

Os autores avaliaram o SpecTr-GBV em cinco conjuntos de dados (HumanEval, GSM8K, MGSM, LM1B, Alpaca) usando quatro baselines (Autoregressivo, SD Padrão, SpecTr, GBV) com os modelos DeepSeek, CodeLlama e Vicuna.

Principais Descobertas:

• Desempenho: O SpecTr-GBV supera consistentemente todas as baselines.
  • Comparado à SD Padrão: ~12,4% de melhoria na Eficiência de Bloco (BE) e ~29,3% de melhoria na Taxa de Aceleração (SR) (configuração DeepSeek-33B).
  • Comparado ao SpecTr: ~2,3% de melhoria na BE e ~8,2% de melhoria na SR.
  • Comparado ao GBV: ~9,7% de melhoria na BE e ~27,0% de melhoria na SR.
• Eficiência Temporal:
  • O número de iterações de decodificação diminuiu em 2,6% em média.
  • A sobrecarga de verificação foi reduzida em >50% comparado ao SpecTr devido à remoção da busca binária para $\rho$.
  • O tempo total de relógio (wall-clock time) diminuiu entre 6,3% e 11,8%, dependendo do conjunto de dados e do tamanho do modelo.
• Estudos de Ablação:
  • Número de Rascunhos ($K$): As taxas de aceitação aumentam monotonicamente com $K$, confirmando previsões teóricas. O SpecTr-GBV mantém taxas de aceitação mais altas que o SpecTr em todos os $K$.
  • Comprimento do Rascunho ($L$): A BE melhora com $L$ maior, mas a SR eventualmente declina devido ao custo computacional de gerar rascunhos longos.
  • Temperatura ($T$): O método é robusto em diferentes temperaturas de amostragem (0,1, 0,4, 0,7).

5. Significado

O SpecTr-GBV representa um avanço significativo na aceleração de inferência de LLMs. Ao provar teoricamente que combinar a geração de múltiplos rascunhos com verificação em nível de bloco produz o comprimento de aceitação ótimo, o artigo estabelece um novo padrão para decodificação especulativa.

• Impacto Prático: Oferece uma melhoria "plug-and-play" para pipelines de SD existentes, reduzindo significativamente a latência sem comprometer a qualidade da saída (fidelidade distribucional).
• Escalabilidade: O método escala efetivamente com o número de modelos de rascunho, sugerindo que hardware futuro capaz de paralelizar múltiplos modelos pequenos pode gerar acelerações ainda maiores.
• Insight Teórico: Resolve a questão em aberto sobre se múltiplos rascunhos e verificação de bloco podem ser combinados de forma ótima, fornecendo uma base matemática rigorosa para pesquisas futuras em decodificação eficiente.