Goose: Anisotropic Speculation Trees for Training-Free Speculative Decoding

Título: Goose: Árvores de Especulação Anisotrópicas para Decodificação Especulativa sem Treinamento

1. O Problema

A decodificação especulativa acelera a inferência de Grandes Modelos de Linguagem (LLMs) propondo múltiplos tokens candidatos e verificando-os em uma única passagem de forward do modelo alvo. O desafio central reside na estrutura da árvore de candidatos:

• Dilema Profundidade vs. Largura: Sob um orçamento fixo de nós (número máximo de tokens candidatos), árvores mais profundas permitem aceitar mais tokens por passo, mas reduzem as opções de "fallback" (largura). Árvores mais largas oferecem mais alternativas, mas limitam o comprimento do caminho aceito.
• Limitação dos Métodos Atuais: As abordagens training-free (sem treinamento) existentes geralmente tratam todas as fontes de tokens como iguais ou usam uma única fonte.
  • Prompt Lookup Decoding (PLD): Copia n-gramas do contexto de entrada. Gera cadeias profundas com alta taxa de aceitação, mas falha completamente se o padrão não for encontrado (sem fallback).
  • Token Recycling (TR): Usa logits do próprio modelo para prever transições. Gera árvores largas, mas com taxas de aceitação geralmente baixas.
• Hipótese Central: O artigo observa que existe uma heterogeneidade de aceitação dramática entre essas fontes (PLD é aceito 2–18 vezes mais frequentemente que TR). Métodos existentes que ignoram essa diferença (assumindo uma taxa de aceitação isotrópica/uniforme) não otimizam a topologia da árvore, desperdiçando o potencial de aceleração.

2. Metodologia: GOOSE

O GOOSE (Anisotropic Speculation Trees) propõe uma estrutura de árvore anisotrópica (assimétrica) que adapta a topologia baseada na qualidade da fonte de tokens.

Conceito Chave: A Árvore "Spine" (Coluna Vertebral)

Em vez de uma árvore balanceada ou isotrópica, o GOOSE constrói uma árvore composta por:

1. Spine (Coluna Vertebral): Uma cadeia linear profunda de tokens obtidos via context matching (PLD), que possuem alta probabilidade de aceitação ($p_s$).
2. Branches (Ramos): Alternativas estatísticas (Token Recycling - TR) que se ramificam a partir de cada nó da spine. Como esses tokens têm baixa probabilidade de aceitação ($p_t$), eles são distribuídos em largura para fornecer fallbacks caso a spine falhe.

Algoritmo e Fluxo de Trabalho

O processo ocorre em três estágios por ciclo de decodificação:

1. Construção da Árvore Spine:
   • Um anchor token (último token aceito) inicia o processo.
   • O sistema busca uma continuação no contexto (PLD) para formar a spine.
   • Uma Tabela de Adjacência (uma extensão de bigrama da matriz de adjacência do TR) fornece candidatos alternativos para os ramos.
   • O orçamento de nós ($B$) é dividido dinamicamente: mais nós para a spine se a confiança for alta, e mais ramos se a confiança for baixa.
2. Verificação Unificada:
   • O modelo alvo verifica todos os candidatos (spine e ramos) em uma única passagem de forward usando uma máscara de atenção causal de árvore.
   • Um caminho guloso unificado (unified greedy walk) percorre a árvore, priorizando a spine. Se um nó da spine for rejeitado, o algoritmo tenta seguir para um ramo naquele ponto.
3. Seleção do Caminho:
   • O caminho mais longo aceito é selecionado.
   • Sinergia de Continuação (Spine Continuation): Se a spine falhar em um ponto, um ramo naquele nó pode continuar o caminho aceito. Isso recupera tokens que nem o PLD puro (que pararia) nem o TR puro (que não teria a profundidade inicial) conseguiriam encontrar sozinhos.

Adaptação de Confiança

O GOOSE ajusta a topologia em tempo real:

• Se a correspondência de contexto for longa e consensual (alta confiança), ele entra em Modo de Bypass, verificando a cadeia linearmente sem construir ramos, economizando overhead.
• Se não houver correspondência, a árvore degenera para uma árvore puramente TR.
• A proporção da spine é ajustada via uma média móvel exponencial (EMA) da taxa de aceitação observada.

3. Contribuições Principais

1. Prova Teórica de Topologia Ótima: Os autores formalizam matematicamente que, quando existem fontes com taxas de aceitação heterogêneas ($p_s > p_t$), a árvore ótima é anisotrópica. Eles provam que alocar profundidade para tokens confiáveis e largura para tokens não confiáveis supera estritamente qualquer árvore isotrópica (balanceada) ou de fonte única.
2. Garantia de Não-Degradação: O framework GOOSE garante que o rendimento esperado (número de tokens aceitos por ciclo) seja sempre pelo menos tão bom quanto o uso de qualquer uma das fontes isoladamente com o mesmo orçamento total.
3. Framework Training-Free: O método não requer treinamento de cabeças de draft (como EAGLE) ou modelos auxiliares, utilizando apenas dados disponíveis no momento da inferência (contexto e logits anteriores).

4. Resultados Experimentais

Os experimentos foram realizados em 5 modelos LLM (de 7B a 33B parâmetros) e 5 benchmarks (código, matemática e diálogo).

• Aceleração: O GOOSE alcançou um speedup de 1.9x a 4.3x em relação à decodificação autoregressiva padrão (AR), mantendo a saída idêntica (lossless).
• Comparação com Baselines:
  • Superou métodos training-free de estado da arte (PLD, TR, Lookahead, REST) em todos os cenários.
  • Superou árvores isotrópicas (balanceadas) em 12% a 33% sob o mesmo orçamento de nós.
  • Competiu ou superou métodos baseados em treinamento (como EAGLE-2) em termos de velocidade de parede (wall-clock speed), especialmente em modelos onde EAGLE não possui cabeças treinadas (ex: Qwen3-8B, Vicuna-33B).
• Sinergia: A análise mostrou que a topologia da árvore spine contribui com um ganho adicional de 16% a 45% sobre o melhor método de fonte única, devido à capacidade de recuperação de tokens em pontos de falha da spine.

5. Significado e Impacto

• Mudança de Paradigma: O trabalho demonstra que a otimização da topologia da árvore de especulação é tão crítica quanto a seleção dos tokens candidatos. Aproveitar a heterogeneidade das fontes de tokens é a chave para a aceleração máxima.
• Eficiência Operacional: Por ser training-free, o GOOSE é imediatamente aplicável a qualquer LLM existente sem a necessidade de retreinamento ou fine-tuning, tornando-o uma solução prática para implantação em produção.
• Generalização: A estrutura de "Spine Tree" pode ser generalizada para qualquer par de estratégias de draft com taxas de aceitação diferentes, abrindo caminho para futuras pesquisas em combinação de múltiplas fontes de especulação.

Em resumo, o GOOSE resolve o dilema profundidade-largura na decodificação especulativa ao criar árvores assimétricas que alinham a estrutura de verificação com a realidade estatística das fontes de tokens, resultando em acelerações significativas e robustas sem custo de treinamento.