Génération guidée efficace pour les grands modèles de langage : traitement et indexation itératifs FSM

Tableau des liens

• Résumé et introduction
• Échantillonnage LLM et génération guidée
• Traitement et indexation itératifs FSM
• Extensions à l'analyse itérative
• Discussion, références et remerciements

3. Traitement et indexation itératifs FSM

Pour être précis, nous considérons des expressions régulières sous forme d'automates finis à 5 tuples [Sipser, 1996, Définition 1.5] :

Définition 1 (Automate fini). Un automate fini, ou machine à états finis, est donné par (Q, Σ, δ, q0, F), où Q est un ensemble fini d'états, Σ un alphabet fini, δ : Q × Σ → Q la fonction de transition, q0 ∈ Q l'état de départ, et F ⊆ Q l'ensemble des états d'acceptation.

Les caractères composant les chaînes de V sont tirés de Σ : c'est-à-dire V ⊂ P(Σ). Tout au long, les états FSM, Q, seront représentés par des valeurs entières pour plus de simplicité.

Exemple 1. Nous illustrons le processus d'échantillonnage FSM dans la figure 1 pour l'expression régulière ([0-9]*)?\.?[0-9]*, qui peut être utilisée pour générer des nombres à virgule flottante. Pour plus de simplicité, laissez le vocabulaire V se composer uniquement des chaînes : "A", ".", "42", ".2" et "1".

Lorsque la génération commence, le FSM est à l'état 0, notre algorithme masque donc la chaîne "A", puisqu'elle ne serait pas acceptée par le FSM. Nous ne pouvons échantillonner que ".", "42", ".2" et "1" dans ce cas.

Si nous échantillonnons ".2", nous avançons le FSM à l'état 3. Dans ce cas, seuls "42" et "1" sont des complétions valides, nous masquons donc les autres valeurs avant l'échantillonnage. Si nous échantillonnons "1" à la place, nous faisons avancer le FSM à l'état 1, auquel cas ".", ".42", ".2" et "1" sont des complétions valides et le masque reste inchangé.

Parcourir le vocabulaire pour déterminer les prochains jetons valides reste le plus gros problème. Pour cela, nous prétraitons le vocabulaire en utilisant le FSM de l'expression régulière et construisons un index. La partie importante est que nous envisageons de commencer dans chaque état FSM viable, car les chaînes du vocabulaire peuvent correspondre à des parties arbitraires d'une expression régulière, et ces parties sont implicitement les états FSM.

Une procédure pour produire des correspondances commençant à n'importe quel point du FSM est donnée dans l'algorithme 3. Le résultat est une liste de sous-séquences détaillant les états par lesquels le FSM traverserait en acceptant la chaîne fournie.

En faisant correspondre les états de départ de ces sous-séquences au dernier état FSM atteint en une seule étape de la boucle dans l'algorithme 2, nous pouvons indexer efficacement le vocabulaire avec une carte, σ : Q → P(V), reliant les états FSM et des ensembles d'éléments du vocabulaire qui seront acceptés par les FSM dans ces États.

L'algorithme 4 décrit la construction de σ.

L'utilisation d'une carte de hachage pour σ peut faire en sorte que l'étape m dans l'algorithme 2 ne coûte que O(1) en moyenne. De plus, puisque σ est construit en dehors de la procédure d'échantillonnage de jetons, son coût d'exécution n'est effectivement pas pertinent, bien qu'il nécessite théoriquement une mémoire égale au nombre d'états dans le FSM (c'est-à-dire |Q|). Heureusement, pour les combinaisons non pathologiques d'expressions régulières et de vocabulaires, toutes les chaînes du vocabulaire ne seront pas acceptées par le FSM, et tous les états du FSM ne seront pas représentés par une chaîne dans V.

3.1 Exemples

Dans cette section, nous utilisons le support GPT2 (355 millions de paramètres) pour illustrer le fonctionnement pratique de la génération guidée par expressions régulières. Nous utilisons la bibliothèque Outlines pour les générer :

Listing 3.1 – suite

Liste 3.3 – suite

3.2 Comparaison avec les méthodes actuelles

Pour illustrer l'efficacité de l'approche d'indexation décrite ici et implémentée dans Outlines, nous effectuons une simple comparaison avec la bibliothèque Guidance. Au moment d'écrire ces lignes, la bibliothèque Guidance utilise une correspondance partielle d'expressions régulières - appliquée à chaque fois depuis le début de la séquence échantillonnée - et doit parcourir le vocabulaire du LLM (N = 50, 257) à chaque étape.

Le code de guidage et l'invite utilisés pour cette comparaison sont les suivants :

Liste 3.4 – suite

Le code Outlines correspondant est le suivant :

Inscription 3.5 – suite

La valeur de max_tokens varie et les timings sont enregistrés avec timeit pour une seule boucle et une seule valeur de répétition (c'est-à-dire qu'un seul échantillon est collecté pour chaque valeur de max_tokens). Les résultats sont présentés dans la section 3.2.

À moins d'oublis de configuration susceptibles de créer un écart d'exécution important, la mise à l'échelle observée du nombre maximum de jetons échantillonnés est frappante et indique le problème de calcul croissant impliqué par l'approche.