🤖 machine learning

Greedy Multi-Path Block Verification for Faster Decoding in Speculative Sampling

Este trabalho demonstra que a verificação de blocos é ótima mesmo considerando probabilidades fora do caminho e propõe o método Greedy Multi-Path Block Verification (GBV), que generaliza essa abordagem para múltiplos caminhos candidatos, alcançando ganhos de eficiência e redução de tempo de decodificação superiores aos métodos existentes.

Autores originais: Rahul Thomas, Arka Pal

Publicado 2026-02-20

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Rahul Thomas, Arka Pal

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está tentando escrever um livro muito longo e complexo (como uma história de ficção científica) com a ajuda de um Mestre Escriba (o modelo de IA grande e inteligente, mas lento) e um Aprendiz Rápido (um modelo menor, mais simples e veloz).

O objetivo é escrever o livro o mais rápido possível sem perder a qualidade da história.

O Problema: O Gargalo do Mestre

O Mestre Escriba é brilhante, mas demora muito para escrever cada palavra porque ele precisa pensar profundamente antes de colocar a pena no papel. O Aprendiz, por outro lado, escreve super rápido, mas às vezes faz erros ou inventa coisas que não combinam com a história.

A técnica antiga (chamada Speculative Sampling) funcionava assim:

O Aprendiz escrevia uma frase inteira de uma vez (digamos, 8 palavras).
O Mestre lia essa frase palavra por palavra para ver se estava correta.
Se a primeira palavra estivesse errada, o Mestre dizia: "Não, comece de novo!". E tudo o que o Aprendiz escreveu depois era jogado fora.
Se a primeira estivesse certa, o Mestre aceitava a segunda, e assim por diante, até encontrar um erro.

O problema: Se o Aprendiz errar logo no início, o Mestre perde tempo verificando palavras que já foram descartadas. É como se você estivesse dirigindo um carro de corrida, mas o mecânico tivesse que checar cada parafuso do motor antes de você sair do posto. Se o primeiro parafuso estiver solto, você não sai, e todo o tempo gasto nos outros parafusos foi desperdiçado.

A Solução Antiga: Verificação em Blocos (Block Verification)

Os pesquisadores criaram uma melhoria chamada "Verificação em Blocos". Em vez de checar palavra por palavra de forma isolada, eles passaram a checar a frase inteira como um bloco. Isso ajudou a aceitar mais palavras, mesmo que as primeiras não fossem perfeitas, mas ainda havia um limite.

A Nova Solução: A "Verificação Múltipla e Gananciosa" (GBV)

Este artigo apresenta uma ideia genial para resolver o problema de forma definitiva. Vamos usar uma analogia de corrida de revezamento com múltiplos times.

1. O Cenário: Múltipos Caminhos (Multi-Path)

Em vez de pedir ao Aprendiz para escrever uma frase de 8 palavras, o sistema pede para ele escrever várias frases diferentes ao mesmo tempo (por exemplo, 3 ou 4 versões da mesma frase).

Analogia: Imagine que você tem 3 corredores rápidos. Em vez de correrem um atrás do outro, eles correm lado a lado, cada um propondo uma rota diferente para chegar ao destino.

2. O Problema da Escolha

Agora você tem 4 caminhos possíveis. O Mestre Escriba precisa escolher qual deles é o melhor. Se ele escolher o caminho errado, perde tempo. Se ele tentar verificar todos de uma vez, gasta muita energia.

3. A Estratégia "Gananciosa" (Greedy)

Aqui entra a parte inteligente do artigo. O sistema usa uma regra simples e "gananciosa" (no bom sentido):

Ele olha para todas as 4 frases propostas.
Ele não tenta calcular a probabilidade perfeita de cada uma (o que seria muito lento).
Em vez disso, ele usa uma "bússola" rápida para classificar as frases do melhor para o pior instantaneamente.
Ele pega a melhor frase dessa lista e diz ao Mestre: "Verifique apenas esta!".

4. A Mágica da "Distribuição Distorcida"

O grande segredo matemático do artigo é que, ao escolher a melhor frase entre várias opções, o sistema muda a "probabilidade" de como essa frase foi gerada. É como se, ao escolher a melhor rota entre 4 opções, o sistema dissesse: "Essa rota é tão boa que parece que foi a única que o Aprendiz tinha em mente".

Isso permite que o sistema use uma verificação mais agressiva e eficiente. O Mestre Escriba aceita mais palavras porque a "sorte" de ter múltiplas opções aumenta a chance de ter pelo menos uma frase quase perfeita.

Os Resultados na Vida Real

Os autores testaram isso em computadores reais e descobriram:

Mais Velocidade: O sistema consegue gerar texto cerca de 15% mais rápido do que os métodos anteriores.
Mais Eficiência: Em vez de gerar 3 palavras por vez (média antiga), eles conseguem gerar mais de 4, às vezes chegando a 5 palavras por "batida" do Mestre.
O Pulo do Gato: Funciona melhor quando a temperatura (o "nível de criatividade" da IA) é baixa. Quando a IA precisa ser mais precisa e menos criativa, essa técnica de escolher o melhor entre várias opções brilha.

Resumo em uma Frase

Imagine que você tem um chefe lento que precisa aprovar seu trabalho. Em vez de entregar um único rascunho e esperar ele corrigir, você entrega vários rascunhos diferentes ao mesmo tempo. O sistema escolhe instantaneamente o melhor rascunho, "convence" o chefe de que aquele era o único que você tinha em mente, e o chefe aprova muito mais rápido, deixando você escrever o livro inteiro em tempo recorde.

Essa é a Verificação de Bloco Múltiplo Gananciosa (GBV): usar a força de múltiplas tentativas rápidas para enganar o sistema de verificação lento, tornando a escrita de IA muito mais eficiente.

Título: Verificação de Bloco Multi-Caminho Gulosa para Decodificação Mais Rápida em Amostragem Especulativa

1. O Problema

A decodificação autoregressiva em Grandes Modelos de Linguagem (LLMs) é frequentemente limitada pela largura de banda de memória, e não pela capacidade de computação. A Amostragem Especulativa (Speculative Sampling) é uma técnica que acelera esse processo utilizando um modelo "rascunho" (draft) mais barato para gerar uma sequência candidata de tokens, que é então verificada pelo modelo alvo (target).

No entanto, existem limitações nas abordagens atuais:

Amostragem Especulativa Padrão: Verifica tokens individualmente. Se o primeiro token for rejeitado (comum quando o modelo rascunho é impreciso), nenhum ganho de velocidade é obtido, pois o processo precisa parar e recomeçar.
Verificação de Bloco (Block Verification - BV): Uma melhoria recente que verifica prefixos inteiros em vez de tokens individuais, melhorando a eficiência. No entanto, a BV é provadamente ótima apenas para algoritmos que usam apenas informações "no-caminho" (on-path) e para um único caminho de rascunho.
Desafio Multi-Caminho: Quando múltiplos caminhos de rascunho são gerados em paralelo (K > 1), algoritmos existentes (como SpecTr, SpecInfer) muitas vezes não exploram totalmente as informações de distribuição "fora do caminho" (off-path) para otimizar a seleção do melhor caminho e a verificação subsequente.

O objetivo deste trabalho é superar a ineficiência da verificação de bloco padrão ao explorar múltiplos caminhos de rascunho e informações de distribuição completas, mantendo a correção estatística da saída.

2. Metodologia

Os autores propõem uma abordagem baseada em Programação Linear (LP) para modelar o problema de verificação ótima e, em seguida, desenvolver uma aproximação gulosa eficiente.

A. Formulação via Programação Linear (LP)

Os autores formalizam o problema de verificação como um problema de otimização:

LP de Informação Agnóstica (Single-Path): Eles definem um LP que considera não apenas as probabilidades no caminho gerado, mas toda a distribuição conjunta alvo e de rascunho.
- Descoberta Chave: Mesmo com acesso a informações "fora do caminho" (off-path), a Verificação de Bloco (BV) permanece ótima para um único caminho. Isso indica que o gargalo não é a falta de informação, mas a restrição de que a saída deve ser um prefixo do bloco de rascunho.
LP Multi-Caminho (Multi-Path): Estendem o LP para o cenário onde $K$ $K$ caminhos de rascunho são amostrados independentemente.
- Diferente do caso de um único caminho, aqui o conhecimento das distribuições "fora do caminho" pode melhorar a eficiência.
- O algoritmo ótimo teórico envolve selecionar probabilisticamente um dos $K$ caminhos com base em uma distribuição de rascunho "distorcida" (skewed draft distribution) e, em seguida, aplicar a verificação de bloco nesse caminho escolhido.
- Desafio: Resolver este LP exatamente é intratável computacionalmente, pois requer otimização não linear sobre distribuições conjuntas completas.

B. Greedy Multi-Path Block Verification (GBV)

Para contornar a intratabilidade do LP ótimo, os autores propõem uma classe de algoritmos de aproximação gulosa:

Conceito: Em vez de resolver o LP global, o algoritmo cria uma classificação global (ranking) de todos os caminhos candidatos possíveis.
Regra Árvore-Based (Tree-Based): Para evitar a necessidade de calcular probabilidades "fora do caminho" (o que seria caro), eles definem uma regra de classificação baseada em árvores. A ordem local em cada nó do prefixo é determinada pela razão $p/q$ (probabilidade alvo / probabilidade de rascunho).
Seleção: O algoritmo seleciona o caminho de rascunho com a maior classificação global (lexicográfica) entre os $K$ caminhos amostrados.
Verificação: Uma vez selecionado o melhor caminho, aplica-se a Verificação de Bloco (BV) padrão, mas utilizando uma distribuição de rascunho "distorcida" calculada explicitamente a partir da regra de seleção gulosa.

O algoritmo resultante, GBV, é eficiente, requer apenas probabilidades "no-caminho" para a classificação e mantém a propriedade de que a saída final segue a distribuição do modelo alvo.

3. Principais Contribuições

Prova de Otimalidade da BV (Single-Path): Demonstraram matematicamente, via um LP de informação agnóstica, que a Verificação de Bloco é ótima mesmo se o algoritmo tiver acesso a todas as distribuições conjuntas alvo/rascunho, desde que restrito a um único caminho.
LP Multi-Caminho e Decomposição: Estenderam a análise para múltiplos caminhos, provando que a informação "fora do caminho" é valiosa nesse contexto. Eles provaram que qualquer algoritmo válido de verificação multi-caminho pode ser decomposto em: (1) seleção aleatória de um caminho com uma distribuição de rascunho distorcida, seguida por (2) verificação de bloco padrão.
Algoritmo GBV: Desenvolveram o Greedy Multi-Path Block Verification, uma aproximação prática e eficiente que utiliza uma regra de classificação baseada em árvores para selecionar o melhor caminho entre $K$ opções, alcançando ganhos significativos sem a complexidade do LP ótimo.
Análise Empírica Abrangente: Testaram o método em diversos modelos (OPT, Qwen-3, Llama-3) e datasets, analisando o impacto do número de caminhos ( $K$ ), temperatura e comprimento do bloco ( $L$ ).

4. Resultados Experimentais

Os experimentos foram conduzidos em modelos como OPT 6.7B, Qwen-3 32B e Llama-3 70B.

Eficiência de Bloco (Block Efficiency):
- O GBV melhora a eficiência de bloco em mais de 30% em comparação com a Verificação de Bloco padrão (BV) em configurações ideais.
- Aumentar o número de caminhos ( $K$ ) de 1 para 3 ou 4 traz ganhos significativos, embora com retornos decrescentes para $K > 3$ .
Tempo de Decodificação (Walltime):
- Redução de mais de 15% no tempo de decodificação (ms/token) em relação à BV.
- No modelo Llama-3 70B, o GBV supera os métodos SOTA de verificação multi-caminho (como SpecTr e SpecInfer) em mais de 15% de throughput.
Impacto da Temperatura:
- Em temperaturas baixas (ex: 0.2), o GBV supera a BV e outros métodos, alcançando até 11.5 tokens/s no Llama-3 70B, enquanto outros métodos não passam de 10 tokens/s.
- Em temperaturas altas (1.0), a BV padrão pode ser competitiva ou superior em alguns modelos grandes (como Qwen-3), mas o GBV com $K=3$ é geralmente o melhor equilíbrio.
Configuração Ótima:
- Para a maioria dos cenários, $K=3$ e comprimento de bloco $L=8$ oferecem o melhor equilíbrio entre ganho de eficiência e custo computacional. $K=4$ muitas vezes introduz latência excessiva devido ao custo de forward pass em lote no modelo alvo.

5. Significado e Impacto

Este trabalho é significativo porque:

Teórico: Resolve a questão da otimalidade da verificação de bloco, mostrando que o limite de eficiência não é a falta de informação, mas a estrutura de saída (prefixo).
Prático: Oferece um método (GBV) que é fácil de implementar, computacionalmente eficiente e que supera os métodos de estado da arte (SOTA) em cenários de baixa temperatura e modelos grandes.
Sistêmico: Demonstra que a exploração inteligente de múltiplos caminhos de rascunho, combinada com uma verificação de bloco adaptada, é uma via promissora para reduzir a latência de inferência em LLMs sem comprometer a qualidade da geração.

Em resumo, o GBV representa um avanço na otimização de inferência de LLMs, transformando a verificação de múltiplos caminhos de um problema de seleção complexa em uma abordagem gulosa eficiente que entrega ganhos reais de velocidade em produção.