Llama: se agrega muestreo basado en gramática

 (github.com/ggerganov)
1 puntos por GN⁺ 2023-07-23 | 1 comentarios | Compartir por WhatsApp
  • El PR #1773 de llama.cpp agrega una API para restringir los candidatos de muestreo con una gramática libre de contexto, con el fin de evitar que la salida generada se salga del formato especificado
  • La API recibe una estructura de gramática basada en puntos de código de 32 bits, filtra los tokens candidatos con llama_sample_grammar y luego refleja el token elegido en el estado de la gramática con llama_grammar_accept_token
  • En main se agregan los argumentos --grammar y --grammar-file para aceptar gramáticas en formato BNF extendido, con ejemplos como Chess, expresiones aritméticas, JSON y generación de rangos de caracteres japoneses
  • Las pruebas se realizaron con un M2 Max y el modelo 30B Q4_0; al aplicar gramática, la salida queda restringida a notación ajedrecística, expresiones aritméticas, JSON y rangos de caracteres japoneses, mientras que sin gramática se genera texto general o código no relacionado con el prompt
  • En la discusión se trataron sobre todo las limitaciones de uso real, como soporte para archivos de gramática, manejo de líneas vacías y comentarios, inclusión del parser en la API, enmascaramiento de logits en GPU, procesamiento por lotes de tokens fijos y sobrecarga de rendimiento

Cambios clave del PR

  • Es un PR que agrega muestreo basado en gramática a llama.cpp
  • Toma como referencia trabajos previos como #1397 y el trabajo de CFG de grantslatton
  • La nueva API recibe una gramática libre de contexto serializada para guiar y restringir el muestreo
  • En main se agregan ejemplos de una gramática tipo BNF para especificar la gramática de generación

Estructura de la API de gramática

  • La API de llama recibe una estructura de gramática libre de contexto sobre puntos de código de 32 bits
  • Los tipos de elementos gramaticales representan fin de regla, inicio de alternativa, referencia a regla, carácter, límite superior de rango de caracteres y adición de carácter alternativo
  • La función de inicialización recibe la siguiente información
    • arreglo de reglas
    • número de reglas
    • índice de la regla inicial
  • llama_grammar_element tiene type y value, donde value se usa como punto de código Unicode o como ID de regla

Método de muestreo

  • El código de muestreo gramatical modela un autómata de pila no determinista
  • Mantiene N pilas para representar los posibles estados de análisis
  • El muestreo de tokens funciona en dos etapas
    • llama_sample_grammar deja solo los candidatos que coinciden con alguna pila de análisis entre los tokens candidatos
    • llama_grammar_accept_token agrega el token seleccionado al estado de la gramática

Funcionalidad de entrada de gramática en main

  • En main se agregan los argumentos --grammar y --grammar-file
  • Ambos aceptan una gramática simple de BNF extendido para restringir los resultados generados
  • El parser de gramática está implementado en examples/grammar-parser.{h,cpp}
  • Las funciones gramaticales compatibles son rangos de caracteres, agrupación y operadores de repetición
  • La regla root identifica el punto de inicio de la gramática
  • En actualizaciones posteriores se agregaron soporte para archivos de gramática, más ejemplos, comentarios estilo shell, líneas vacías entre reglas y saltos de línea dentro de grupos entre paréntesis

Ejemplos de prueba

  • El entorno de prueba indicado es M2 Max, 30B
  • Ejemplo de Chess
    • Con --grammar-file grammars/chess.gbnf se generan formatos de notación ajedrecística como 1. e4 e5, 2. Nf3 Nc6
    • Al ejecutar el mismo prompt sin gramática, se genera una oración general relacionada con Sir Thomas Gresham
  • Ejemplo de expresiones aritméticas
    • Se fuerza en línea una gramática con la forma expr "=" ws num "\n"
    • El resultado queda restringido a formas de expresión aritmética como 10 *a*1 +b*2 =640
    • Sin gramática, se genera un fragmento de código Go
  • Ejemplo de JSON
    • Con grammars/json.gbnf se genera una estructura JSON con forma { "fullName": ..., "address": ... }
    • Sin gramática, se genera prosa tipo presentación personal
  • Ejemplo de japonés
    • grammars/japanese.gbnf permite hiragana, katakana, signos de puntuación y rangos CJK
    • Al aplicar la gramática, se genera una lista basada en caracteres japoneses
    • Sin gramática, se genera una lista de pasos en inglés

Revisión y discusión de diseño

  • Hubo una propuesta para recibir la gramática desde un archivo, y luego se agregaron soporte de grammar file y ejemplos
  • Entre los problemas detectados en el uso inicial se reportaron conflictos con --prompt-cache y crashes causados por líneas vacías dentro de la gramática
  • El soporte para líneas vacías y comentarios, así como permitir saltos de línea dentro de grupos entre paréntesis, se incluyó en commits posteriores
  • También hubo discusión sobre si el parser debía incluirse en la API de llama.cpp
    • Si el parser queda fuera de la API, existe la preocupación de que los usuarios downstream tengan que copiarlo para poder soportar esta función
    • El autor buscaba minimizar los cambios en llama.cpp, aunque coincidió en que incluir el parser en la API sería más conveniente
  • Se propuso que llama_grammar conserve una copia binaria de la gramática para que el usuario no tenga que mantener viva la copia entregada

Rendimiento y discusión de optimización

  • Se entiende que, incluso cuando los siguientes N > 1 tokens quedan determinados de forma única por la gramática, actualmente se siguen muestreando uno por uno
  • Se discutió que evaluar por lotes varios tokens fijos podría aumentar mucho la velocidad de inferencia en esos casos
  • El autor respondió que los tokens igual deben evaluarse y que el cuello de botella parece estar del lado de la evaluación, aunque considera que la evaluación por lotes a nivel de cadena podría ser un punto de optimización
  • También se propusieron ideas como compilar la gramática en GPU como un tensor de transición de estados o hacer enmascaramiento de logits en GPU sobre el conjunto completo de tokens
  • Se mencionó torch-grammar como un enfoque similar que realiza en GPU el enmascaramiento de logits forzado por gramática sobre el conjunto completo de tokens

Observaciones de rendimiento

  • El autor indicó que solo probó inferencia en CPU y que, en el rango que evaluó, el impacto en rendimiento no fue grande
  • Cifras observadas en M2 Max
    • El muestreo sin restricciones es de alrededor de 0.5ms/token
    • El muestreo con gramática es de alrededor de 6ms/token
    • La evaluación de tokens en 13B Q4_K es de alrededor de 70ms/token
  • Otro usuario reportó un caso en 13B donde cayó de cerca de 20T/s a 13T/s
  • El autor dijo que normalmente ve una sobrecarga gramatical de alrededor de 5ms/token, aunque en ciertas gramáticas el impacto fue mayor y podría haber casos patológicos

Discusiones relacionadas sobre extensiones

  • Se mencionó la posibilidad de convertir entrada JSON Schema a BNF para usarla de esa manera
  • El autor comentó que tiene una rama local que funciona con el ejemplo del README de jsonformer, y que un script en Python genera BNF de JSON ajustado a un JSON Schema
  • Más adelante se mencionó en relación con este PR examples : generate JSON according to schema #1887
  • Se respondió que este enfoque es independiente de las modificaciones del modelo y que también puede usarse junto con modelos fine-tuned
  • También se mencionó por separado un PR que agrega muestreo basado en gramática a whisper.cpp

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-07-23
Comentarios en Hacker News

  • Así es como entiendo que funciona. El modelo de lenguaje va emitiendo un token a la vez a partir del prompt como punto de partida, y una conversación con un LLM también puede verse como una secuencia donde el usuario da una secuencia de tokens, el modelo genera una parte y luego el usuario la continúa agregando más tokens
    Esta técnica de gramática permite controlar los tokens de forma mucho más fina. Por ejemplo, si le das Give me the address of the White House as JSON: {"street": ", el LLM devuelve 1600 Pennsylvania Ave NW", y en el momento en que ves la comilla de cierre, el usuario inyecta ", "City": " para recibir Washington, DC"
    Pero como esto está basado en gramáticas, puede hacer mucho más que solo JSON. También me gustó una propuesta que vi antes en Twitter: que OpenAI aceptara una gramática libre de contexto determinista como parámetro del API, o mejor aún, que recibiera un pequeño binario WASM que fuera el sampler mismo, de unos pocos KB y ejecutado con unos pocos MB de memoria, lo cual podría ampliar bastante las capacidades del LLM
    https://twitter.com/grantslatton/status/1637692033115762688

    • Además, un LLM no emite directamente cada token individual, sino una lista de sugerencias con pesos. El token más plausible tiene el peso más alto, pero puede haber varias alternativas, incluyendo símbolos JSON como comillas
      La configuración de temperature ajusta la probabilidad de que se elija un token que no sea el de mayor rango para reducir salidas repetitivas. Obligar al LLM a seguir una gramática suele consistir en filtrar esa lista antes de elegir el token, y aun así puede quedar la aleatoriedad controlada por temperature
      Una función más avanzada sería permitir retroceder cuando la IA se atasca y no puede producir una salida válida
    • El funcionamiento real consiste en validar con la gramática la salida actual y los posibles siguientes tokens candidatos durante el muestreo, y eliminar todos los tokens candidatos que no encajen. Luego se aplica la estrategia de muestreo normal sobre la lista restante de tokens válidos
    • Creo que esta explicación no es correcta. Antes ya se podía controlar la salida en los LLM leyendo los tokens uno por uno y deteniéndose al encontrar un carácter de parada
      Creo que el punto clave del PR de muestreo basado en gramática es que llama.cpp usa la gramática para reducir el siguiente token de salida a un conjunto restringido de tokens posibles
    • También hay una explicación más detallada de cómo implementar esto: https://github.com/normal-computing/outlines/pull/131
      La escribió uno de los desarrolladores de la librería Outlines, y Outlines también es una buena librería de flujos de trabajo con LLM
    • No termino de entender de qué está hablando. Desde “passing up” en adelante, me da la impresión de que esta persona inventó términos nuevos. Lo único que puedes meter en un LLM es un prompt que será tokenizado
      Aunque envíes reglas DCFG o una versión compilada como parte de la solicitud, no veo cómo eso cambiaría de forma fundamental la manera en que predice tokens el modelo. Si el modelo predice algo que no coincide con la gramática requerida, ¿la idea es volver a meter el prompt hasta que acierte?

  • Hay que señalar que esto solo impone restricciones gramaticales sobre el texto que genera el modelo, no que vaya a resolver bien la alineación del contenido. Es útil cuando necesitas garantizar que el servidor emita JSON bien formateado, pero no parece que vaya a resolver muchos de los problemas actuales de alineación en generación de lenguaje
    Por ejemplo, hoy Llama o GPT suelen etiquetar mal los bloques de código Markdown. Con muestreo basado en gramática puedes obligarlos a poner una etiqueta, pero no puedes forzar que sea la etiqueta correcta, porque eso depende del contexto. También es difícil esperar buenas salidas tras crear un nuevo lenguaje específico de dominio sin alinear el modelo con ese lenguaje

    • También es importante que, cuando aparece una cadena de formato libre, eso se vuelve una invitación abierta para que el LLM se vaya por completo a cualquier lado. Por eso conviene usar este tipo de método junto con otras heurísticas que sesguen el muestreo, como una penalización por repetición, cuando entra en zonas de texto libre
    • Aun así, con Llama podrías entrenar algunos ejemplos en una LoRA
      Por ejemplo, se puede imaginar un sistema que haga hot-swap entre una LoRA para Markdown y un archivo de gramática Markdown según sea necesario

  • Esto realmente me encanta. Hace tiempo intenté crear Constrained Text Generation Studio (https://github.com/Hellisotherpeople/Constrained-Text-Genera...), y hasta salió en COLING 2022 con un paper relacionado (https://paperswithcode.com/paper/most-language-models-can-be...)
    Aun así, siempre he pensado que este enfoque y las ideas relacionadas que enumera este paper son el camino a seguir: https://arxiv.org/abs/2306.03081
    Ahora habría que pensar cómo crear gramáticas que hagan cumplir cosas como el número de sílabas o reglas sintácticas. Los LLM actuales son muy malos en ese tipo de tareas por la forma en que tokenizan

    • Me sorprendió, pero Nous Hermes escribe haikus bastante decentes

  • También implementé esto para PyTorch: https://github.com/Shopify/torch-grammar. También tengo una versión hackeada de text-generation-inference que usa esto, y puedo compartirla si hace falta

    • Estaría bueno que la compartieras. Estaba intentando volcar el vector de probabilidades de tokens en una de las interfaces de LLM, así que tener otro punto de partida podría ayudar bastante

  • En el caso de enumeraciones de cadenas de opción múltiple, básicamente como un dropdown, me pregunto si al hacer la selección final funcionaría mejor considerar la probabilidad conjunta total dado el estado de los logits, en vez de usar un algoritmo codicioso
    Cuando varias opciones de la lista comparten el token inicial, eso podría hacer que se favorezca la opción correcta y no la que solo contiene el token inicial más común. Claro, una vez que parte de los logits se ha puesto en 0, habría que reajustar las probabilidades para que realmente tenga sentido

  • Esta “biblioteca” de gramáticas fue citada como ejemplo de formatos: https://github.com/antlr/grammars-v4
    Aquí hay de todo, desde ensamblador y C++ hasta GLSL, lenguajes de scripting, aritmética, juegos, accesos directos de freedesktop, LLVM IR y formatos raros como Verilog

    • Sería conveniente poder especificar accesos directos a gramáticas estándar como HTML, JSON o Python en la API de inferencia. Pensando en el esfuerzo que OpenAI invirtió en ajustar finamente el modelo de Code Interpreter, sinceramente es raro que todavía no hayan hecho algo así
    • Estaría muy bien que soportara la sintaxis de gramáticas de ANTLR4. Es una gran herramienta

  • ¿Alguien puede explicarlo de forma simple? Entiendo más o menos los LLM, pero no me queda claro qué está haciendo Georgi aquí ni por qué algunos están tan emocionados

    • Un LLM no genera directamente el “siguiente token”. Produce un vector de probabilidades donde cada posición del texto de entrada corresponde a un token, y cada valor puede verse como la probabilidad de que ese token aparezca después
      Programas como ChatGPT “interpretan” ese vector de probabilidades para elegir uno de los tokens con mayor probabilidad, es decir, hacen sampling, y así generan texto. Pero este método a veces es demasiado flexible, así que aunque quieras una salida en JSON, puede elegir tokens que no cumplen la gramática de JSON y terminar produciendo un JSON inválido
      La forma de “forzar” al LLM a generar algo como JSON es cambiar el proceso de sampling. En vez de elegir cualquier token probable, primero se dejan solo los tokens válidos según la gramática de JSON, y luego se hace sampling entre ese subconjunto
    • Cuando le pides a un LLM que genere JSON u otro lenguaje con gramática, a veces produce sintaxis incorrecta. Este PR modifica el procedimiento de sampling para restringir al LLM a que solo emita sintaxis válida según la gramática proporcionada por el usuario
      El LLM genera texto token por token. Primero, una red neuronal enorme asigna probabilidades a todos los tokens posibles, y el procedimiento de sampling usa esas probabilidades para elegir un token, tras lo cual repite el proceso
      El procedimiento de sampling no es la red neuronal, así que puede modificarse de muchas maneras. Se puede usar sampling codicioso, eligiendo siempre el token con mayor probabilidad, pero normalmente una selección aleatoria ponderada por probabilidad funciona mejor. Aporta diversidad y también reduce la posibilidad de caer en bucles. Pero cualquier token con probabilidad distinta de cero puede salir, así que puede producir JSON inválido. Este PR pone en 0 la probabilidad de todos los tokens gramaticalmente inválidos para que no puedan ser elegidos
      También se pueden hacer otras modificaciones interesantes al proceso de sampling. Como al muestrear token por token puedes terminar en un callejón sin salida sin opciones válidas, se podría permitir retroceder. Más aún, en cada paso podrían considerarse varias opciones para construir un árbol de salidas posibles, y al final elegir la ruta con mayor probabilidad total. Si se consideran todas las opciones, se obtiene un árbol completo con una rama por cada token posible, que crece exponencialmente, así que se puede podar y dejar, por ejemplo, solo las 5 mejores rutas en cada paso. Eso es beam search. Como ejecutar la red neuronal que genera las probabilidades es muy costoso, multiplicar el costo por 5 suele ser pesado y por eso normalmente no se usa en LLM, pero se puede hacer y mejora algo los resultados. También podría pensarse en usar búsqueda de árbol Monte Carlo, como en los motores de ajedrez
    • Un LLM genera con gusto cadenas arbitrarias. Tú querías algo como “Alice: 42”, pero podría devolverte algo como “Hola, soy un modelo útil y, por lo que veo, Alice es exactamente forty two, aunque solo soy un modelo de lenguaje”
      Entonces le das una gramática que diga que la respuesta debe consistir en una letra mayúscula seguida de letras minúsculas, dos puntos, un espacio, números, y luego terminar. Así, al buscar el primer token solo se consideran los que sean compatibles con ese patrón, y después solo se siguen considerando los tokens compatibles con el patrón siguiente
      Ese tipo de gramática permite hacer eso de una forma flexible y útil
    • Mira mi comentario aquí: https://news.ycombinator.com/item?id=36820884

  • Esto me parece interesante, así que voy a intentar incorporarlo en lo que hago. Aunque siento que, desde la perspectiva de la Bitter Lesson, quizá no sea el mejor enfoque más que a muy corto plazo: http://www.incompleteideas.net/IncIdeas/BitterLesson.html

    • Puede ser un parche temporal, pero es un parche temporal importante. No está claro que, en los próximos años, los LLM vayan a resolver “de forma natural” los problemas de generación de texto con restricciones
    • No soy experto en absoluto, pero entiendo que OpenAI usa este tipo de enfoque en algunas API de GPT para programación. También he visto la hipótesis de que, si delegas el manejo simple de gramáticas a un proceso sencillo adecuado para eso, el LLM puede usar sus recursos computacionales de forma más eficiente en tareas complejas. No sé si sea cierto

  • También hay un proyecto que usa un método parecido: https://github.com/automorphic-ai/trex
    Playground: https://automorphic.ai/playground

  • Me gustaría que me recomendaran algún artículo o resumen que explique cómo se hace el muestreo/decodificación en la era de las redes neuronales de extremo a extremo. Sé cómo se hacía la decodificación en traducción automática y reconocimiento de voz en la época de los HMM, por ejemplo cosas como https://en.wikipedia.org/wiki/Viterbi_algorithm o https://en.wikipedia.org/wiki/Beam_search
    Últimamente me da la impresión de que la gente simplemente usa un enfoque “codicioso”, pero no estoy seguro. Me vendría bien cualquier recomendación de material sobre este tema.

    • Es codicioso y aleatorio al mismo tiempo :) Más que artículos, recomiendo mirar los algoritmos de la mayoría de las implementaciones de LLM. rwkv.cpp tiene una implementación en Python relativamente limpia: https://github.com/saharNooby/rwkv.cpp/blob/master/rwkv/samp...
    • Si lees la documentación de GPT-4, no parece haber una gran diferencia con las cosas que mencionaste
      https://platform.openai.com/docs/api-reference/completions/c...
      Claro, ahora sabemos que GPT-4 tiene una arquitectura de mezcla de expertos, así que internamente está paralelizando el cómputo. También incluye la forma de modificar los logits con términos de penalización por presencia/frecuencia.