Génération guidée efficace pour les grands modèles de langage : extensions à l'analyse itérative

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

4. Extensions à l'analyse itérative

Dans cette section, nous nous concentrons sur la génération générale guidée par l'analyseur et commençons par une simple présentation d'une grammaire de type Python fournie sous forme de CFG.

Considérons un vocabulaire composé de chaînes comme « d » et « ef » qui peuvent être combinées pour produire une syntaxe de type Python selon un CFG implicite, et supposons que ces chaînes sont séquentiellement échantillonnées et concaténées selon un processus comme l'algorithme 1.

De plus, considérons un symbole terminal DEF dans le CFG qui correspond à la chaîne « def » et est donné par l'expression régulière triviale def. Considérez également un symbole NAME donné par l'expression régulière [^\W\d]\w* (par exemple les identifiants Python). Nous souhaitons analyser séquentiellement les chaînes échantillonnées à partir du vocabulaire susmentionné d'une manière qui respecte la syntaxe Python.

Par exemple, ce qui suit pourrait être une de ces séquences : ["d", "ef", " f", "oo(", "):", " ", "pass"]. Tous les éléments de la séquence sont par définition des éléments du vocabulaire. La concaténation de la séquence produit "def foo(): pass", qui est une séquence valide de jetons définissant une fonction. Dans la situation que nous envisageons, nous aurons observé tous les jetons jusqu'à un certain point et ne saurons rien de ceux après ce point.

Par exemple, à la troisième observation de la séquence d'exemple, nous avons la chaîne concaténée "def f". Si nous devions lexifier/analyser cette chaîne, une approche traditionnelle renverrait la séquence de symboles DEF NAME, qui identifie à tort le « f » comme un jeton NAME complet. Comme nous pouvons le voir sur le reste de la séquence, le jeton NAME correct sera "foo".

En général, les prochaines chaînes valides qui peuvent être échantillonnées à partir du vocabulaire sont celles qui :

1. continuer à développer/avancer le NOM commençant actuellement par "f" (comme le fait la séquence complète dans notre exemple), et/ou

   
   

2. tout ce qui commence par "("–c'est-à-dire un symbole LPAR avec une expression régulière (–et continue à spécifier une signature d'argument valide.

Dans le premier cas, le "f" peut être vu comme un symbole NOM partiellement correspondant en Python, et – en rappelant que son expression régulière est [^\W\d]\w* – nous pouvons dire qu'il correspond aux deux sous-modèles (c'est-à-dire [^\W\d] et \w*) dans l'expression régulière. Notre utilisation des FSM formalise la notion de sous-modèles au moyen des états d'un FSM. Dans ce cas, l'expression régulière pour NAME peut être représentée par un FSM, M, avec trois états : 0 (c'est-à-dire l'état initial q0), 1 (c'est-à-dire [^\W\d]) et 2 (c'est-à-dire \w*) , où 1, 2 ∈ F.

En utilisant l'algorithme 3, nous obtiendrions les séquences d'états FSM (0, 1), (1, 2), (2, 2) pour "f" et le FSM, M, correspondant au symbole NOM. Ces séquences FSM pour "f" nous indiquent que la correspondance peut commencer pour cette chaîne de vocabulaire dans les états 0, 1 ou 2, et qu'elle peut se terminer dans les états 1 ou 2.

Selon le cas 1. ci-dessus, l'analyse peut être poursuivie – pour le symbole NAME – après s'être terminée précédemment par les états 1 ou 2. Selon le cas 2., la chaîne suivante pourrait également commencer par ou contenir une partition logique, ce qui implique que M se serait terminé , ce qui est possible étant donné que 1 et 2 sont des états finaux dans M auxquels l'analyse se serait arrêtée après la lecture de "f". La fin M indique également qu'un symbole NOM a été complété et qu'une transition vers un état acceptant la partition logique a été autorisée par la grammaire.

Dans cette illustration, les prochaines chaînes de vocabulaire valides sont au moins "d", "ef", "pass", " ", "oo(", car toutes ces chaînes développeraient le NOM partiellement correspondant, et la dernière serait également faire progresser l'état d'analyse vers un état qui lit une partition logique. La chaîne restante, "):", du sous-ensemble du vocabulaire que nous avons considéré entraînerait une séquence avec une syntaxe non valide.

En ce qui concerne l'approche d'indexation FSM, cela signifie que l'algorithme 4 mapperait les états FSM 0, 1 et 2 au sous-ensemble "d", "ef", "pass", " ", "oo(" pour le symbole NAME et son FSM, M.

Cette illustration omet les états sous-jacents de l’analyseur qui déterminent les symboles grammaticaux et les transitions autorisés. Nous utilisons des automates pushdown (PDA) comme moyen d'étendre l'approche FSM et de traiter les détails restants.

4.1 Formulation d'automates pushdown

Nous définissons les automates pushdown en utilisant la représentation à 6 tuples suivante [Sipser, 1996, Définition 2.13] :

Afin de construire une approche d'indexation pour un analyseur piloté par PDA, nous devons utiliser la connexion entre les symboles d'un CFG - via l'alphabet correspondant d'un PDA - et les étapes de lexage et de numérisation qui produisent les symboles lus par un PDA.

Plus spécifiquement, les analyseurs sont pris en charge par des lexers et des scanners qui identifient les symboles à partir d'une séquence de saisies de caractères, comme nous l'avons implicitement illustré dans la section 4. Des listes ordonnées de symboles terminaux peuvent être construites pour chaque état d'analyse/PDA en fonction des transitions de symboles et de pile autorisées. par l'application δ dans chaque état. Cela signifie que nous pouvons construire un FSM pour chaque état d'analyse qui est l'union de chaque FSM correspondant à un symbole terminal lu par l'état.

Une étape d'analyse identifiera ensuite un ensemble de symboles terminaux possibles V ⊂ Σ pour les caractères lus depuis le dernier symbole entièrement identifié dans le processus d'analyse. Par exemple, dans l'état initial q0 d'un PDA pour le CFG Pythonlike dans la section 4, scanner et lexer la chaîne "de" donnera V = {DEF, NAME} : c'est-à-dire DEF pour toute chaîne de vocabulaire complétant la chaîne "def" –suivi d'une chaîne non également lue par le NAME FSM (par exemple "def")– et NAME pour toute autre chaîne lue par son FSM (par exemple "default"). Notez que les étapes du scanner – et les étapes d'échantillonnage du LLM – finiront par réduire l'ensemble V jusqu'à ce qu'un seul symbole terminal v ∈ V soit déterminé.

En appliquant l'algorithme 3 à chaque chaîne de V en utilisant les FSM combinés pour chaque état d'analyse, nous pouvons déterminer les configurations d'analyseur composées des états PDA, des états FSM correspondants et des symboles terminaux potentiels.

Par analogie avec les étapes de l'algorithme 3, nous pouvons utiliser la pré-image de la carte de transition du PDA pour déterminer les valeurs de la pile du PDA qui liront les états du PDA q ∈ Q et les jeux de symboles terminaux V d'une configuration d'analyseur :

Les valeurs de pile fournies par cette carte sont nécessaires pour trouver des chemins – le cas échéant – à travers le PDA qui permettent des analyses complètes et réussies de chaque chaîne dans V à partir de leurs configurations d'analyseur possibles. Pour les combinaisons d'état et de terminal de l'analyseur qui correspondent aux opérations REDUCE d'un analyseur LALR(1), ces configurations d'analyseur comprendront plus que les valeurs du haut de la pile dans Γ ; ils seront constitués de sous-piles correspondant à tous les préfixes valides pour les opérations REDUCE impliquées par une chaîne de vocabulaire. En fin de compte, chaque configuration d'analyseur qui permet une analyse complète d'une chaîne de vocabulaire est ajoutée en tant qu'entrée dans l'index du PDA et, dans ce cas, l'index devra être une structure de données trie afin de permettre des requêtes sur l'analyseur. valeurs de pile.