Geração guiada eficiente para modelos de linguagem grande: processamento e indexação FSM iterativo

Tabela de links

• Resumo e introdução
• Amostragem LLM e Geração Guiada
• Processamento e indexação iterativo de FSM
• Extensões para análise iterativa
• Discussão, Referências e Agradecimentos

3. Processamento e indexação iterativo de FSM

Para ser mais preciso, consideramos expressões regulares na forma de autômato finito de 5 tuplas [Sipser, 1996, Definição 1.5]:

Definição 1 (Autômato Finito). Um autômato finito, ou máquina de estados finitos, é dado por (Q, Σ, δ, q0, F), onde Q é um conjunto finito de estados, Σ um alfabeto finito, δ : Q × Σ → Q a função de transição, q0 ∈ Q o estado inicial, e F ⊆ Q o conjunto de estados aceitos.

Os caracteres que compõem as strings em V são extraídos de Σ: ou seja, V ⊂ P(Σ). Ao longo do processo, os estados do FSM, Q, serão representados por valores inteiros para simplificar.

Exemplo 1. Ilustramos o processo de amostragem FSM na Figura 1 para a expressão regular ([0-9]*)?\.?[0-9]*, que pode ser usada para gerar números de ponto flutuante. Para simplificar, deixe o vocabulário, V, consistir apenas nas strings: "A", ".", "42", ".2" e "1".

Quando a geração começa, o FSM está no estado 0, então nosso algoritmo mascara a string “A”, pois ela não seria aceita pelo FSM. Só podemos amostrar ".", "42", ".2" e "1" neste caso.

Se amostrarmos ".2", avançamos o FSM para o estado 3. Neste caso, apenas "42" e "1" são conclusões válidas, por isso mascaramos os outros valores antes da amostragem. Se, em vez disso, amostrarmos "1", avançamos o FSM para o estado 1, caso em que ".", ".42", ".2" e "1" são conclusões válidas e a máscara permanece inalterada.

Percorrer o vocabulário para determinar os próximos tokens válidos ainda é o maior problema. Para isso, pré-processamos o vocabulário utilizando o FSM da expressão regular e construímos um índice. A parte importante é que consideramos começar em todos os estados FSM viáveis, porque as strings no vocabulário podem corresponder a partes arbitrárias de uma expressão regular, e essas partes são implicitamente os estados FSM.

Um procedimento para produzir correspondências começando em qualquer ponto do FSM é fornecido no Algoritmo 3. O resultado é uma lista de subsequências detalhando os estados pelos quais o FSM passaria ao aceitar a string fornecida.

Ao combinar os estados iniciais dessas subsequências com o último estado FSM alcançado em uma única etapa do loop no Algoritmo 2, podemos indexar eficientemente o vocabulário com um mapa, σ: Q → P (V), conectando os estados FSM e conjuntos de elementos do vocabulário que serão aceitos pelo FSM nesses estados.

O Algoritmo 4 descreve a construção de σ.

Usar um mapa hash para σ pode fazer com que o passo m no Algoritmo 2 custe apenas O(1) em média. Além disso, como σ é construído fora do procedimento de amostragem de tokens, seu custo em tempo de execução é efetivamente irrelevante, embora teoricamente exija memória igual ao número de estados no FSM (ou seja, |Q|). Felizmente, para combinações não patológicas de expressões regulares e vocabulários, nem todas as strings do vocabulário serão aceitas pelo FSM, e nem todos os estados do FSM serão representados por uma string em V.

3.1 Exemplos

Nesta seção, usamos meio GPT2 (parâmetros 355M) para ilustrar como a geração guiada por expressões regulares funciona na prática. Usamos a biblioteca Outlines para gerá-los:

Listagem 3.1 – continuação

Listagem 3.3 – continuação

3.2 Comparação com métodos atuais

Para ilustrar a eficiência da abordagem de indexação descrita aqui e implementada no Outlines, realizamos uma comparação simples com a biblioteca Guidance. No momento em que este livro foi escrito, a biblioteca Guidance usa correspondência parcial de expressões regulares – aplicada sempre desde o início da sequência amostrada – e deve iterar sobre o vocabulário do LLM (N = 50, 257) em cada etapa.

O código de orientação e o prompt usados para esta comparação são os seguintes:

Listagem 3.4 – continuação

O código Outlines correspondente é o seguinte:

Listagem 3.5 – continuação

O valor de max_tokens é variado e os tempos são registrados com timeit para um único loop e um único valor de repetição (ou seja, apenas uma amostra é coletada para cada valor de max_tokens). Os resultados são apresentados na Seção 3.2.

Salvo quaisquer descuidos de configuração que possam estar criando uma grande discrepância no tempo de execução, o escalonamento observado no número máximo de tokens amostrados é impressionante e é indicativo do crescente problema computacional implícito na abordagem.