A inferência LLM é uma questão de bilhões de dólares. O nosso novo artigo apresenta um algoritmo SOTA em amostragem especulativa de múltiplos rascunhos, Global Resolution, que faz avanços significativos neste problema. Desempacotando abaixo 🧵👇

Uma abordagem para inferência eficiente é chamada de amostragem especulativa. Isto utiliza um modelo ‘rascunho’ barato para produzir ‘palpites’ sobre o que o modelo maior e alvo teria gerado.

Ao explorar as eficiências de paralelismo das GPUs modernas, isso pode acabar reduzindo o número de passagens de avanço do modelo alvo em mais de 5x.

A amostragem especulativa pode ser generalizada para incluir múltiplos palpites de vários modelos de rascunho. Mas não está claro qual é o melhor algoritmo para combinar esses múltiplos palpites.

No caso de um único passo, trabalhos anteriores mostraram que a solução ótima pode ser encontrada resolvendo um programa linear de transporte ótimo, o OTLP.

No entanto, o OTLP é extremamente difícil de resolver quase exatamente à medida que cresce exponencialmente em tamanho de vocabulário. Então, como podemos resolvê-lo?

A chave é explorar uma estrutura adicional na construção da árvore de rascunho.

Trabalhos anteriores [Hu et. al.] mostraram que, quando a árvore de rascunho é formada por amostragem i.i.d., ao dualizar o OTLP, o valor objetivo ótimo pode ser calculado em tempo quase linear através da minimização submodular.

No entanto, até ao nosso trabalho, nenhum método foi capaz de resolver a solução que alcançou este valor objetivo ótimo. Sem esta peça que falta, todo o trabalho anterior apenas nos fornece a eficiência do bloco, a velocidade máxima teórica de aceleração. Não nos diz como alcançar esta aceleração.

O nosso trabalho é o primeiro a reduzir significativamente a dimensionalidade do OTLP, utilizando três percepções.

Revertemos a dualização do OTLP no trabalho anterior [Hu et. al.] com a folga complementar, para formular o OTLP como um problema de viabilidade de fluxo.

Muitas das restrições de desigualdade de fluxo são redundantes. Usando um algoritmo guloso da teoria dos polimatroides, podemos coalescer estas.

Este problema de fluxo reduzido tem uma solução que pode ser parametrizada como o softmax de um vetor de baixa dimensão, e este vetor pode ser calculado através da minimização convexa. Isto reduz o OTLP em V^{n+1} variáveis para um problema de minimização convexa em V variáveis.

V ainda pode ser bastante grande, no entanto, por isso no nosso artigo aplicamos aproximações adicionais com uma taxa de erro do modelo alvo limitada para reduzir ainda mais o tempo de computação.

Para muitos casos com V restrito ao top-k e n modelos de rascunho, como mostrado acima, a Resolução Global é o _único_ solucionador capaz de resolver o OTLP em um tempo razoável.

Além disso, ao usar a Resolução Global, podemos melhorar as taxas de aceitação no Llama e Gemma em até 6%: Em resumo, a Resolução Global é SOTA para verificação multi-rascunho ótima em decodificação especulativa.

Ainda há muito trabalho a ser feito aqui, seja relaxando a configuração iid, ou estendendo para múltiplos passos.