Show HN: Possibilidade de dobrar a velocidade de inferência de LLM (Speeding up LLM inference 2x times (possibly))

O que é Effort?

• Effort se refere à energia, ao tempo e aos recursos investidos para realizar uma tarefa ou alcançar um objetivo
• Isso significa o esforço e a dedicação necessários para superar obstáculos ou obter o resultado desejado
• Effort pode ser físico ou mental
  • esforço físico, como a energia usada para levantar objetos pesados ou correr uma maratona
  • esforço mental, como a concentração e a força mental necessárias para resolver problemas complexos ou aprender novas habilidades
• É um elemento essencial para alcançar o sucesso em diversas áreas da vida, como crescimento pessoal, trabalho e educação

Opinião do GN⁺

• Effort não é apenas a quantidade de tempo ou energia investida, mas um conceito em que diversos fatores atuam em conjunto, como persistência, foco e motivação. Portanto, mesmo se esforçando bastante, o sucesso não é necessariamente garantido
• Especialmente em tarefas que exigem Effort mental, é preciso tomar cuidado para não cair em burnout. É importante encontrar formas de sustentar o Effort por meio de descanso adequado e recompensas
• A forma de aplicar Effort pode variar de pessoa para pessoa. Alguns conseguem se concentrar intensamente por curtos períodos, enquanto outros conseguem manter o Effort de forma constante no longo prazo. Encontrar o método que funciona melhor para você é o mais eficaz

[GN⁺]

Comentários do Hacker News

• O cerne do algoritmo parece ser podar parâmetros durante a execução e, dentro de cada grupo, determinar os pesos menos importantes pela ordem do valor absoluto dos pesos candidatos à poda e zerá-los para tornar a matriz de pesos esparsa
  Se você pesquisar poda de modelos, aparecem muitos resultados, e https://arxiv.org/abs/2305.11627 também trata “poda baseada em magnitude” como baseline e cita https://arxiv.org/pdf/2301.00774.pdf
  Não gosto muito quando artigos implementam o baseline de forma relaxada e depois exaltam o próprio método, ou quando embrulham tudo com um monte de termos matemáticos. O post original do blog transmite o método com muito mais facilidade até para quem quase não tem conhecimento prévio

  • Passei o último mês tentando tornar a pesquisa o mais reproduzível e confiável possível. A implementação original era muito ineficiente e, mesmo depois de acelerar a multiplicação de matrizes em Metal/GPU, gastei bastante tempo ajustando o restante da implementação para ficar o mais próximo possível do Llama.cpp, para que os benchmarks também ficassem mais fáceis
    A abordagem dos artigos mencionados parece ser estática, e não me parece que eles tenham apresentado um algoritmo que realmente acelere o cálculo com resultados de 20~50%. Isso foi uma grande parte do lado difícil. Quando tiver tempo, pretendo revisar a literatura relacionada com mais cuidado
    No fim, quero adicionar uma página de referências junto com os artigos que as pessoas postaram nos comentários. Acho que em breve alguém pode acabar encontrando um texto que já organizou esse algoritmo
    Durante o desenvolvimento, também perguntei ao gpt-4 e pesquisei no Google, mas o que encontrei em geral era estático ou removia dimensões/camadas inteiras de forma arbitrária e depois fazia retreinamento. Não encontrei nada que correspondesse exatamente a esta ideia
  • “Encher o texto de termos matemáticos para embrulhar o próprio método e implementar mal o baseline” parece um sinal de artigo ruim
    Quanto mais denso e difícil de entender for o texto, maior a chance de ele estar escondendo ciência fraca lá dentro

• Gostei desta frase da parte sobre implementação em GPU
  “Quem está vendo programação de GPU pela primeira vez talvez pergunte agora - como isso funciona?
  Quem já tem experiência com programação de GPU talvez pergunte - como diabos isso funciona?”

  • Pelo que entendi, foi preciso implementar a leitura de memória e algumas outras coisas ao contrário do que normalmente é considerado a abordagem correta
    Seria ótimo se alguém que realmente entende de Metal pudesse revisar este código. Foi minha primeira tentativa de programação em GPU

• “Vamos inverter a matriz, ordenar os elementos por linha e olhar para a multiplicação de novo nessa direção. Os espertos chamam isso de formato compressed sparse row (CSR). Agora, para multiplicar, você pega o 1 do vetor, multiplica por 256 e soma na 3ª linha do vetor de saída, e assim por diante. Agora vamos ver o que acontece se cortarmos a última coluna, onde estão os menores valores.”
  Fico curioso sobre como isso se encaixa com a forma como o CSR reduz o número de multiplicações

  • Você pode reformular a pergunta? Não entendi muito bem

• Isso parece semelhante à esparsidade semiestruturada, a chamada esparsidade 2:4, então vale a pena comparar explicitamente. Pelo que vi por cima, esta técnica é otimizada para Apple Silicon, tem cerca de 2x de velocidade com 75% de esparsidade, é dinâmica e aplicada em tempo de execução conforme a entrada, e permite escolher o grau de esparsidade
  Já a esparsidade semiestruturada 2:4 é otimizada para GPUs com sparse tensor cores, ou seja, Nvidia Ampere em diante, tem cerca de 2x de velocidade com 50% de esparsidade, é estática e aplicada no estado salvo do modelo, e em 50% de esparsidade provavelmente pode ter resultados piores do que esta técnica
  A comparação que eu gostaria de ver é entre o resultado de 50% de esparsidade com ganho de 2x da esparsidade semiestruturada e o resultado de 75% de esparsidade com ganho de 2x desta técnica

  • Obrigado por conferir. Eu também espero que saiam mais testes em breve
    Escolhi Apple Silicon porque era mais fácil de desenvolver. Existe a possibilidade de este algoritmo ter bom desempenho em outras arquiteturas também

• Para quem já usou CSR, isso não é surpreendente. Entre formatos mais recentes, talvez haja coisas como block ELL que se ajustem melhor às características do hardware
  Esses formatos evitam leituras não coalescidas ou gather, mas o código fica mais complicado

  • Que bom finalmente encontrar alguém com experiência em CSR
    O bucketMul quase não faz leituras não coalescidas e usa uma estrutura de dados diferente do CSR comum. Está explicado aqui: https://kolinko.github.io/effort/bucketmul.html
    Cada linha da matriz é dividida em 16 partes, e escolhe-se quais partes precisam ser lidas. As escritas são totalmente lineares
    Dito isso, não sei se estou falando algo que faz sentido agora. Já está tarde hoje e foi um dia longo

• Boa ideia e bom texto. Eu também trabalho com esparsidade em inferência de redes neurais, e me ocorreram alguns pontos que vale a pena ter em mente
  Em comparação com uma implementação densa de multiplicação matriz-vetor, esse algoritmo adiciona complexidade algorítmica, mas reduz o tráfego de memória. Multiplicação matriz-vetor normalmente é limitada por memória, então reduzir acessos à memória aumenta a vazão. Mas, quando o tamanho do lote passa de 1, o acesso à memória deixa de ser o gargalo, então há uma grande chance de o ganho de velocidade desaparecer muito rapidamente
  Como comparação, eu gostaria de ver não só o mesmo modelo, mas também outros modelos com arquitetura 2x mais rápida. Por exemplo, ao aplicar esse método com 50% de esparsidade a um LLM de 13B de parâmetros, como ele se compara a um LLM de 7B de parâmetros, ou ao mesmo LLM quantizado para metade da largura de bits de referência? Se ele conseguir mostrar saídas de maior fidelidade no mesmo tempo do que os frameworks de inferência existentes, isso parece material para um artigo interessante
  Como as multiplicações são omitidas, é bastante provável que o erro de aproximação fique sistematicamente enviesado para reduzir o valor absoluto em relação ao resultado real. Se fosse possível adicionar um termo de correção para compensar esse erro sistemático, talvez o desempenho melhorasse um pouco mais

  • A complexidade algorítmica na prática não aumenta. As multiplicações são O(effrt * inDim * outDim), o cálculo de dispatch é O(inDim), e encontrar o ponto de corte é O(~inDim * log inDim)
    A notação big-O não é ideal para trabalho em GPU, mas neste caso ela é aproximadamente correta
    O principal problema são os limites arquiteturais da GPU. Esse algoritmo precisa de mais registradores/grupos de threads/memória de cache do que a abordagem tradicional, e isso vira o gargalo principal. Além disso, como todas as multiplicações usam buckets diferentes, não é simples paralelizar o trabalho como em modelos MoE
    Para arquiteturas maiores, eu na prática testei bastante no Mixtral, que é efetivamente um modelo 13B, e minha impressão é que ele se sustenta muito melhor ali. A velocidade de inferência em relação ao effort se mantém, e a qualidade em relação ao effort mantém resultados utilizáveis até 12~16%, em vez de 20~25%. Os testes foram limitados, e eu quebrei a implementação do Mixtral enquanto colocava a implementação do Mistral, então não tenho dados sólidos, mas devo corrigir isso em breve
    Intuitivamente, acho que quanto maior o modelo, mais dá para cortar o effort
    Eu também supus no começo que omitir multiplicações criaria viés, mas, contra a intuição, não foi o que aconteceu. Tenho alguns gráficos, mas ainda não consegui prepará-los para publicação
    Como os valores da matriz estão distribuídos de forma equilibrada entre positivos e negativos, depois de certo limiar o drift no valor de saída não é grande

• Parece ótimo. Mas 15 ms de latência é parecido com os 16,7 ms do vsync de 60 Hz
  Se você estiver atualizando a tela a cada token, isso também pode ser uma causa de sincronização em algum ponto

  • Não é isso. Estou medindo separadamente o trabalho de CPU e GPU, e os 15 ms acontecem entre chamadas de kernel. Acontece mesmo sem imprimir texto
    Mesmo assim, obrigado pela ideia. Vou considerar isso como a primeira contribuição da comunidade :D

• Isso é realmente muito legal e uma contribuição aberta. Vou acompanhar de perto para ver se o llama.cpp implementa isso
  Eu estava procurando uma forma de acelerar inferência em CPU, e gostei muito da ideia de effort

  • Desenvolver isso foi como uma maratona, e fico feliz que tenha ido para a página principal
    O nome foi sugerido pelo chatgpt. Como ele disse não reconhecer essa abordagem, talvez exista a possibilidade de ser algo realmente novo
    Quero entrar em contato com o llama.cpp e outros projetos, e seria ótimo se fosse implementado. Até pensei em escrever eu mesmo um patch para o llama, mas C++ e a escala daquele projeto ficaram demais para mim
    A inferência em CPU também deve ficar mais rápida. Além disso, como dá para carregar apenas parte dos pesos, por exemplo pulando os menos importantes e carregando só 70%, deve ser possível rodar o modelo com menos VRAM do que antes. Mas ainda preciso de uma implementação de Q8
    Curiosamente, quando fui comparar benchmarks com o llama.cpp, não consegui encontrar velocidade para 7B/FP16 em um MB Air 16GB. Isso porque, da forma normal, ele simplesmente não consegue rodar. Com Effort, consegue
    De forma parecida, rodei um Mixtral em resolução completa, mas recortado, em um M2 de 96GB. Normalmente seriam necessários 114GB de RAM, mas carregando só 75% dos pesos ele rodou de forma suave. Agora eu quebrei um pouco a implementação e ela está produzindo saída lixo, então preciso corrigir isso

• Bom texto. Estou realmente curioso sobre o desempenho por VRAM em comparação com quantização simples
  Também queria saber se existe plano de implementar uma versão cross-platform

  • O desempenho por VRAM não é muito melhor. A estrutura ainda usa todos os pesos, só que nem sempre usa todos de uma vez
    Claro, também dá para carregar menos pesos, mas parece que, se você remove mais de 20~30% dos pesos, a qualidade piora rapidamente
    Em outras palavras, esse algoritmo desacopla o tempo de inferência do uso de VRAM
    Ainda assim, eu também tenho curiosidade de saber se um Q8 cortado em 75% com effort pode entregar resultados melhores do que Q6
    Mas acho que ainda vou precisar de algumas semanas para lapidar a implementação o suficiente e testar isso direito

• Isso não faz retreinamento, mas fico curioso se seria possível combinar esse tipo de abordagem com quantização e depois fazer treinamento adicional para recuperar parte da qualidade perdida
  É bom ver coisas assim, porque dá para imaginar até onde desempenho e custo ainda podem melhorar no futuro. Obrigado por desenvolver isso como open source

  • À primeira vista, parece possível. Pelo que li, há duas formas principais de recuperar parte da qualidade na quantização
    Uma é treinamento posterior, e a outra é treinamento com consciência de quantização, em que se quantiza durante o treinamento, mas se mantêm ativações e gradientes em precisão total