llama: adiciona amostragem baseada em gramática

 (github.com/ggerganov)
1 pontos por GN⁺ 2023-07-23 | 1 comentários | Compartilhar no WhatsApp
  • O PR #1773 do llama.cpp adiciona uma API para restringir candidatos de amostragem com uma gramática livre de contexto, permitindo que a saída gerada não fuja do formato especificado
  • A API recebe uma estrutura de gramática baseada em pontos de código de 32 bits, filtra os tokens candidatos com llama_sample_grammar e depois reflete o token escolhido no estado da gramática com llama_grammar_accept_token
  • Foram adicionados ao main os argumentos --grammar e --grammar-file, que permitem informar gramáticas em formato BNF estendido, com exemplos de xadrez, expressões aritméticas, JSON e geração dentro de intervalos de caracteres japoneses
  • Os testes foram executados com M2 Max e o modelo 30B Q4_0, e com a gramática aplicada a saída fica restrita a notação de xadrez, expressões aritméticas, JSON e intervalos de caracteres japoneses, enquanto sem gramática são gerados texto genérico ou código sem relação com o prompt
  • A discussão se concentrou em limitações de uso real, como suporte a arquivos de gramática, tratamento de linhas em branco e comentários, inclusão ou não do parser na API, mascaramento de logits via GPU, processamento em lote de tokens fixos e overhead de desempenho

Principais mudanças do PR

  • Este PR adiciona amostragem baseada em gramática ao llama.cpp
  • Como base, ele faz referência ao trabalho anterior em #1397 e ao trabalho de CFG de grantslatton
  • A nova API recebe uma gramática livre de contexto serializada para orientar e restringir a amostragem
  • Também foram adicionados ao main exemplos de uma gramática parecida com BNF para especificar a gramática de geração

Estrutura da API de gramática

  • A API de llama recebe uma estrutura de gramática livre de contexto sobre pontos de código de 32 bits
  • Os tipos de elementos da gramática representam fim de regra, início de alternativa, referência de regra, caractere, limite superior de intervalo de caracteres e adição de caractere alternativo
  • A função de inicialização recebe as seguintes informações
    • array de regras
    • número de regras
    • índice da regra inicial
  • llama_grammar_element possui type e value, e value é usado como ponto de código Unicode ou ID de regra

Como a amostragem funciona

  • O código de amostragem por gramática modela um autômato de pilha não determinístico
  • Ele mantém N pilhas para representar possíveis estados de parsing
  • A amostragem de tokens funciona em duas etapas
    • llama_sample_grammar mantém apenas os candidatos compatíveis com ao menos uma pilha de parsing
    • llama_grammar_accept_token adiciona o token selecionado ao estado da gramática

Entrada de gramática no main

  • Foram adicionados ao main os argumentos --grammar e --grammar-file
  • Os dois argumentos aceitam uma gramática simples em BNF estendido para restringir o resultado gerado
  • O parser de gramática foi implementado em examples/grammar-parser.{h,cpp}
  • Os recursos suportados incluem intervalos de caracteres, agrupamento e operadores de repetição
  • A regra root identifica o ponto de início da gramática
  • Em atualizações posteriores foram adicionados suporte a arquivo de gramática, mais exemplos, comentários no estilo shell, linhas em branco entre regras e quebras de linha permitidas dentro de grupos entre parênteses

Exemplos de teste

  • O ambiente de teste foi descrito como M2 Max, modelo 30B
  • Exemplo de xadrez
    • Com --grammar-file grammars/chess.gbnf, são gerados formatos de notação de xadrez como 1. e4 e5 e 2. Nf3 Nc6
    • Sem gramática, o mesmo prompt gera frases genéricas sobre Sir Thomas Gresham
  • Exemplo de expressão aritmética
    • Uma gramática inline força o formato expr "=" ws num "\n"
    • O resultado fica limitado a expressões aritméticas como 10 *a*1 +b*2 =640
    • Sem gramática, o modelo gera um trecho de código Go
  • Exemplo de JSON
    • Com grammars/json.gbnf, é gerada uma estrutura JSON no formato { "fullName": ..., "address": ... }
    • Sem gramática, o modelo gera prosa em tom de autoapresentação
  • Exemplo de japonês
    • grammars/japanese.gbnf permite hiragana, katakana, pontuação e intervalos CJK
    • Com a gramática, é gerada uma lista baseada em caracteres japoneses
    • Sem gramática, é gerada uma lista em inglês por etapas

Revisão e discussões de design

  • Houve proposta para aceitar gramática por arquivo, e depois foram adicionados suporte a grammar file e exemplos
  • Durante o uso inicial, foram relatados problemas como conflito com --prompt-cache e crash causado por linhas em branco na gramática
  • Suporte a linhas em branco e comentários, além de quebras de linha dentro de grupos entre parênteses, foi incluído em commits posteriores
  • Também houve discussão sobre incluir o parser na API do llama.cpp
    • Se o parser ficar fora da API, usuários downstream teriam de copiar o parser para oferecer suporte ao recurso
    • O autor queria minimizar mudanças no próprio llama.cpp, mas concordou que colocar o parser na API seria mais conveniente
  • Foi sugerido que llama_grammar mantenha uma cópia binária da gramática, para que o usuário não precise preservar a vida útil da cópia passada

Discussões sobre desempenho e otimização

  • Entende-se que, mesmo quando os próximos N > 1 tokens são determinados de forma única pela gramática, a implementação atual ainda amostra um por um
  • Foi discutido que avaliar em lote vários tokens fixos poderia aumentar bastante a velocidade de inferência nesses casos
  • O autor respondeu que os tokens ainda precisam ser avaliados e que o gargalo parece estar nessa etapa, embora a avaliação em lote por string possa ser um ponto de otimização
  • Também foi sugerida a ideia de compilar a gramática na GPU como um tensor de transição de estados ou aplicar mascaramento de logits na GPU sobre todo o conjunto de tokens
  • torch-grammar foi citado como uma abordagem semelhante que faz mascaramento de logits forçado por gramática na GPU sobre todo o conjunto de tokens

Observações de desempenho

  • O autor afirmou que só testou inferência em CPU e, dentro do que experimentou, o impacto no desempenho não foi grande
  • Números observados no M2 Max
    • amostragem sem restrições: cerca de 0.5ms/token
    • amostragem com gramática: cerca de 6ms/token
    • avaliação de tokens em 13B Q4_K: cerca de 70ms/token
  • Outro usuário relatou um caso de queda de aproximadamente 20T/s para 13T/s em 13B
  • O autor disse que normalmente vê overhead de gramática em torno de 5ms/token, mas que em certas gramáticas o impacto foi maior e pode haver casos patológicos

Discussões relacionadas a extensões

  • Foi mencionada a possibilidade de usar entrada em JSON Schema convertida para BNF
  • O autor disse ter uma branch local que funciona com o exemplo do README do jsonformer e gera BNF JSON compatível com JSON Schema via script Python
  • Depois, examples : generate JSON according to schema #1887 foi mencionado em conexão com este PR
  • Foi respondido que essa abordagem é independente de modificações no modelo e também pode ser usada junto com modelos fine-tuned
  • Também foi citado separadamente um PR que adiciona amostragem baseada em gramática ao whisper.cpp

Leituras relacionadas

1 comentários

 
GN⁺ 2023-07-23
Opiniões do Hacker News

  • Pelo que entendi, o funcionamento é este: o modelo de linguagem emite um token por vez a partir do prompt como ponto de partida, e uma conversa com um LLM também pode ser vista como o usuário fornecendo uma sequência de tokens, o modelo gerando uma parte e então o usuário anexando mais conteúdo
    Essa técnica de gramática permite controlar os tokens com muito mais granularidade. Por exemplo, se você fornecer até Give me the address of the White House as JSON: {"street": ", o LLM retorna 1600 Pennsylvania Ave NW"; assim que vê as aspas de fechamento, o usuário injeta ", "City": " e recebe Washington, DC"
    Só que, por ser baseada em gramática, ela permite fazer muito mais do que apenas JSON. Vi uma boa sugestão no Twitter tempos atrás: a ideia era que a OpenAI aceitasse uma gramática livre de contexto determinística como argumento da API ou, indo além, recebesse alguns KB de um pequeno binário WASM que fosse o próprio sampler e o executasse com alguns MB de memória; isso poderia ampliar muito as capacidades dos LLMs
    https://twitter.com/grantslatton/status/1637692033115762688

    • Além disso, um LLM não emite diretamente tokens individuais, mas sim uma lista ponderada de recomendações. O token mais plausível tem o maior peso, mas pode haver várias alternativas, incluindo símbolos de JSON como aspas
      A configuração de temperature ajusta a chance de tokens que não estão no topo do ranking serem escolhidos, reduzindo saídas repetitivas. Forçar o LLM a seguir uma gramática, em geral, consiste em filtrar a lista antes da escolha do token; ainda assim, a aleatoriedade controlada pela temperature pode permanecer
      Um recurso mais avançado seria permitir retroceder quando a IA ficar travada e não conseguir produzir uma saída válida
    • Na prática, o funcionamento é verificar, pela gramática, a saída atual e os próximos tokens candidatos para amostragem, removendo todos os tokens candidatos que não batem. Em seguida, aplica-se a estratégia de amostragem normal à lista restante de tokens válidos
    • Acho que essa explicação não está correta. Antes, já era possível controlar a saída em LLMs lendo os tokens um a um e parando ao encontrar um caractere de parada
      Vejo o ponto central do PR de amostragem baseada em gramática como fazer o llama.cpp usar uma gramática para restringir o próximo token de saída a um conjunto limitado de tokens possíveis
    • Também há uma explicação mais detalhada de como implementar isso: https://github.com/normal-computing/outlines/pull/131
      Foi escrita por um dos desenvolvedores da biblioteca Outlines, que também é uma boa biblioteca de workflow para LLMs
    • Não estou entendendo muito bem do que se trata. A começar por “passing up”, parece que essa pessoa está inventando terminologia. A única entrada que pode ser passada para um LLM é um prompt que será tokenizado
      Mesmo que você envie regras DCFG, ou uma versão compilada delas, como parte da requisição, não vejo como isso mudaria fundamentalmente a forma de previsão de tokens. Se o modelo prevê algo que não está de acordo com a gramática solicitada, a ideia é reenviar o prompt até dar certo?

  • Vale destacar que isso apenas impõe restrições gramaticais ao texto gerado pelo modelo; não faz um alinhamento adequado do conteúdo. É útil quando você precisa garantir que o servidor emita JSON bem formatado, mas não acho que resolva muitos dos problemas atuais de alinhamento na geração de linguagem
    Por exemplo, hoje Llama ou GPT frequentemente rotulam blocos de código Markdown de forma errada. Com amostragem baseada em gramática, dá para forçar que um rótulo seja colocado, mas não dá para forçar que ele seja o rótulo correto, pois isso depende do contexto. Também é difícil criar uma nova linguagem específica de domínio e esperar uma boa saída sem alinhar o modelo a essa linguagem

    • Também é importante notar que, quando aparece uma string em formato livre, ela vira um convite aberto para o LLM sair totalmente pela tangente. Por isso, esse tipo de método funciona melhor junto com outras heurísticas que enviesam a amostragem ao entrar em áreas de texto livre, como penalidade de repetição
    • Ainda assim, no caso do Llama, dá para treinar alguns exemplos em uma LoRA
      Por exemplo, dá para imaginar um sistema que faça hot swap de uma LoRA para Markdown e de um arquivo de gramática Markdown conforme necessário

  • Gostei muito disso. Já tinha criado o Constrained Text Generation Studio (https://github.com/Hellisotherpeople/Constrained-Text-Genera...) e também publiquei um artigo relacionado na COLING 2022 (https://paperswithcode.com/paper/most-language-models-can-be...)
    Mesmo assim, sempre achei que esse tipo de abordagem, ou as ideias relacionadas listadas neste artigo, era o caminho: https://arxiv.org/abs/2306.03081
    Agora preciso pensar em como criar gramáticas que imponham coisas como número de sílabas ou regras sintáticas. Os LLMs atuais são muito ruins nesse tipo de tarefa por causa da forma de tokenização

    • Para minha surpresa, o Nous Hermes escreve haicais de forma bastante convincente

  • Também implementei isso para PyTorch: https://github.com/Shopify/torch-grammar. Também tenho uma versão hackeada do text-generation-inference que usa isso; posso compartilhar se houver interesse

    • Seria ótimo se você compartilhasse. Tentei fazer dump do vetor de probabilidades dos tokens em uma das UIs de LLM, e ter outro ponto de partida ajudaria bastante

  • Em casos de enumeração de strings de múltipla escolha, basicamente como um dropdown, fico pensando se funcionaria melhor considerar a probabilidade conjunta total no estado dado pelos logits ao fazer a escolha final, em vez de usar um algoritmo guloso
    Quando o token inicial é compartilhado por vários itens da lista, isso poderia levar a preferir a opção correta em vez da opção que contém o token inicial mais comum. Claro que, depois que parte dos logits vira 0, é preciso ajustar as probabilidades para que isso faça sentido de fato

  • Esta “biblioteca” de gramáticas foi citada como exemplo de formatos: https://github.com/antlr/grammars-v4
    Ela tem de tudo, de Assembly e C++ a GLSL, linguagens de script, aritmética, jogos, atalhos do freedesktop, LLVM IR e até formatos incomuns como Verilog

    • Seria conveniente se a API de inferência permitisse especificar atalhos de gramáticas padrão como HTML, JSON e Python. Considerando o esforço que a OpenAI dedicou ao ajuste fino do modelo Code Interpreter, sinceramente é estranho que ainda não tenham feito algo assim
    • Seria muito bom se houvesse suporte à sintaxe de gramáticas ANTLR4. É uma ferramenta excelente

  • Alguém consegue explicar de forma simples? Eu entendo LLMs até certo ponto, mas não estou conseguindo captar o que Georgi está fazendo aqui e por que alguns estão tão empolgados

    • Um LLM não gera diretamente o “próximo token”. A partir do texto de entrada, ele cria um vetor de probabilidades em que cada posição corresponde a um token, e cada valor pode ser visto como algo próximo da probabilidade de aquele token vir em seguida
      Programas como o ChatGPT “interpretam” esse vetor de probabilidades e escolhem, ou seja, amostram, um dos tokens do topo para produzir texto. Mas esse método às vezes é flexível demais: mesmo quando você quer saída em JSON, ele pode escolher um token que não se encaixa na gramática do JSON e produzir JSON inválido
      A forma de “forçar” um LLM a gerar algo como JSON é mudar o processo de amostragem. Em vez de escolher qualquer token entre os principais, primeiro ficam apenas os tokens que se encaixam na gramática do JSON e então se amostra um token do topo dentro desse subconjunto
    • Quando você pede a um LLM para gerar JSON ou outra linguagem com gramática, às vezes ele produz sintaxe inválida. Este PR restringe o LLM para que ele produza apenas sintaxe válida de acordo com uma gramática fornecida pelo usuário, modificando o procedimento de amostragem
      LLMs geram texto token por token. Primeiro, uma enorme rede neural atribui probabilidades a todos os tokens possíveis; depois, o procedimento de amostragem usa essas probabilidades para escolher um token e repete o processo
      O procedimento de amostragem não é uma rede neural, então pode ser alterado de várias maneiras. É possível usar amostragem gananciosa, que sempre escolhe o token de maior probabilidade, mas normalmente uma escolha aleatória ponderada por probabilidade funciona melhor. Ela traz diversidade e também reduz a chance de cair em loops. Porém, qualquer token com probabilidade diferente de zero pode ser escolhido, o que pode resultar em JSON inválido. Este PR zera a probabilidade de todos os tokens que não são válidos pela gramática, impedindo que sejam selecionados
      Outras modificações interessantes também são possíveis no processo de amostragem. Ao amostrar tokens um a um, você pode entrar em um beco sem saída e ficar sem opções; então poderia permitir voltar atrás. Indo além, em cada etapa você pode considerar várias escolhas e construir uma árvore de saídas possíveis, escolhendo no final o caminho com maior probabilidade total. Se considerar todas as escolhas, isso vira uma árvore completa que se ramifica pelo número de tokens possíveis, crescendo exponencialmente; por isso, dá para podar mantendo em cada etapa apenas, digamos, os 5 melhores caminhos. Isso é beam search. Como o custo de executar a rede neural que gera as probabilidades é muito alto, um aumento de custo de 5x é pesado, então isso normalmente não é usado em LLMs, mas é possível e melhora os resultados em certa medida. Também dá para imaginar o uso de busca em árvore de Monte Carlo, como em motores de xadrez
    • LLMs geram de bom grado strings arbitrárias. Você queria algo como “Alice: 42”, mas ele pode responder algo como “Olá, eu sou um modelo prestativo e, na minha opinião, Alice é exatamente forty two, mas sou apenas um modelo de linguagem”
      Então você fornece uma gramática dizendo que a resposta deve terminar depois de uma letra maiúscula seguida de letras minúsculas, dois-pontos, espaço e números. Assim, ao procurar o primeiro token, ele considera apenas tokens compatíveis com esse padrão; depois, continua considerando apenas tokens compatíveis com o padrão seguinte
      Esse tipo de gramática torna esse trabalho flexível e útil
    • Veja meu comentário aqui: https://news.ycombinator.com/item?id=36820884

  • Achei isso interessante e estou tentando incorporar no meu trabalho. Ainda assim, do ponto de vista da Bitter Lesson, tenho a impressão de que talvez esta não seja a melhor abordagem fora do curtíssimo prazo: http://www.incompleteideas.net/IncIdeas/BitterLesson.html

    • Pode ser uma solução provisória, mas é uma solução provisória importante. Não está claro se, nos próximos anos, os LLMs vão resolver “naturalmente” o problema de geração de texto com restrições
    • Não sou nem de longe especialista, mas pelo que sei a OpenAI usa uma abordagem assim em algumas APIs GPT para programação. Também vi a especulação de que, se o processamento simples de gramática for delegado a um processo simples apropriado para isso, o LLM consegue usar seus recursos computacionais de forma mais eficaz em tarefas complexas. Não sei se isso é verdade

  • Há também um projeto que usa um método semelhante: https://github.com/automorphic-ai/trex
    Playground: https://automorphic.ai/playground

  • Gostaria de receber recomendações de artigos ou visões gerais que expliquem como amostragem/decodificação funciona na era das redes neurais ponta a ponta. Sei como a decodificação era feita em tradução automática e reconhecimento de fala na época dos HMMs, por exemplo coisas como https://en.wikipedia.org/wiki/Viterbi_algorithm ou https://en.wikipedia.org/wiki/Beam_search
    Hoje em dia, tenho a impressão de que as pessoas simplesmente usam o método “guloso”, mas não tenho certeza. Seria bom receber recomendações de materiais sobre esse tema

    • É guloso e aleatório :) Em vez de artigos, recomendo mais olhar os algoritmos das implementações de LLMs. O rwkv.cpp tem uma implementação em Python relativamente limpa: https://github.com/saharNooby/rwkv.cpp/blob/master/rwkv/samp...
    • Lendo a documentação do GPT-4, parece que não há muitas diferenças grandes em relação ao que você mencionou
      https://platform.openai.com/docs/api-reference/completions/c...
      Claro que agora sabemos que o GPT-4 tem uma arquitetura de mistura de especialistas, então internamente ele paraleliza a computação. Também inclui formas de modificar os logits com termos de penalidade de presença/frequência.