Generación guiada eficiente para modelos de lenguaje grandes: indexación y procesamiento FSM iterativo

Tabla de enlaces

• Resumen e introducción
• Muestreo LLM y generación guiada
• Procesamiento e indexación iterativos de FSM
• Extensiones al análisis iterativo
• Discusión, referencias y agradecimientos

3. Procesamiento e indexación iterativos de FSM

Para ser precisos, consideramos expresiones regulares en forma de autómata finito de 5 tuplas [Sipser, 1996, Definición 1.5]:

Definición 1 (Autómata finito). Un autómata finito, o máquina de estados finitos, está dado por (Q, Σ, δ, q0, F), donde Q es un conjunto finito de estados, Σ un alfabeto finito, δ : Q × Σ → Q la función de transición, q0 ∈ Q el estado inicial y F ⊆ Q el conjunto de estados de aceptación.

Los caracteres que componen las cadenas en V se extraen de Σ: es decir, V ⊂ P(Σ). En todo momento, los estados FSM, Q, se representarán mediante valores enteros para simplificar.

Ejemplo 1. Ilustramos el proceso de muestreo FSM en la Figura 1 para la expresión regular ([0-9]*)?\.?[0-9]*, que se puede utilizar para generar números de punto flotante. Para simplificar, supongamos que el vocabulario V consta únicamente de las cadenas: "A", ".", "42", ".2" y "1".

Cuando comienza la generación, el FSM está en estado 0, por lo que nuestro algoritmo enmascara la cadena "A", ya que no sería aceptada por el FSM. En este caso, solo podemos muestrear ".", "42", ".2" y "1".

Si tomamos una muestra de ".2", avanzamos el FSM al estado 3. En este caso, sólo "42" y "1" son terminaciones válidas, por lo que enmascaramos los otros valores antes de tomar la muestra. Si en su lugar tomamos la muestra "1", avanzamos el FSM al estado 1, en cuyo caso ".", ".42", ".2" y "1" son terminaciones válidas y la máscara permanece sin cambios.

Recorrer el vocabulario para determinar los siguientes tokens válidos sigue siendo el mayor problema. Para eso, preprocesamos el vocabulario usando el FSM de la expresión regular y creamos un índice. La parte importante es que consideramos comenzar en cada estado FSM viable, porque las cadenas del vocabulario podrían coincidir con partes arbitrarias de una expresión regular, y esas partes son implícitamente los estados FSM.

En el algoritmo 3 se proporciona un procedimiento para producir coincidencias que comienzan en cualquier punto de la FSM. El resultado es una lista de subsecuencias que detallan los estados por los que atravesaría la FSM al aceptar la cadena proporcionada.

Al hacer coincidir los estados iniciales de estas subsecuencias con el último estado FSM al que se llegó en un solo paso del ciclo en el Algoritmo 2, podemos indexar eficientemente el vocabulario con un mapa, σ : Q → P(V), conectando estados FSM y conjuntos de elementos del vocabulario que serán aceptados por los Estados Federados de Micronesia en esos estados.

El algoritmo 4 describe la construcción de σ.

El uso de un mapa hash para σ puede hacer que el paso m en el algoritmo 2 cueste solo O(1) en promedio. Además, dado que σ se construye fuera del procedimiento de muestreo de tokens, su costo de tiempo de ejecución es efectivamente irrelevante, aunque teóricamente requiere una memoria igual al número de estados en el FSM (es decir, |Q|). Afortunadamente, para combinaciones no patológicas de expresiones regulares y vocabularios, el FSM no aceptará todas las cadenas del vocabulario y no todos los estados de la FSM estarán representados por una cadena en V.

3.1 Ejemplos

En esta sección utilizamos GPT2-medium (parámetros 355M) para ilustrar cómo funciona en la práctica la generación guiada de expresiones regulares. Usamos la biblioteca Outlines para generarlos:

Listado 3.1 – continuación

Listado 3.3 – continuación

3.2 Comparación con los métodos actuales

Para ilustrar la eficiencia del enfoque de indexación descrito aquí e implementado en Esquemas, realizamos una comparación simple con la biblioteca de Orientación. Al momento de escribir este artículo, la biblioteca de Orientación utiliza una coincidencia parcial de expresiones regulares, que se aplica desde el inicio de la secuencia muestreada cada vez, y debe iterar sobre el vocabulario del LLM (N = 50, 257) en cada paso.

El código de orientación y el mensaje utilizados para esta comparación son los siguientes:

Listado 3.4 – continuación

El código de esquemas correspondiente es el siguiente:

Listado 3.5 – continuación

El valor de max_tokens varía y los tiempos se registran con timeit para un único bucle y un único valor de repetición (es decir, sólo se recoge una muestra para cada valor de max_tokens). Los resultados se representan en la Sección 3.2.

Salvo cualquier descuido de configuración que pueda estar creando una gran discrepancia en el tiempo de ejecución, el escalamiento observado en el número máximo de tokens muestreados es sorprendente y es indicativo del creciente problema computacional que implica este enfoque.