💻 computer science

GRID: Grammar-Railed Decoding for Enterprise SQL Generation

Le document présente GRID, un moteur de décodage contraint par la grammaire qui exploite les états d'analyse syntaxique LALR(1) et les parcours de tries au niveau de l'octet pour générer du SQL syntaxiquement valide et conforme aux politiques, avec des garanties prouvables, des coûts de décodage quasi constants et des pistes d'audit infalsifiables, améliorant considérablement la précision d'exécution dans les contextes d'entreprise.

Auteurs originaux : Mohsen Arjmandi

Publié 2026-07-15

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Mohsen Arjmandi

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous avez un ami robot super intelligent (un grand modèle de langage) qui adore écrire des instructions informatiques appelées SQL. Ce robot est excellent pour deviner le mot suivant dans une phrase, mais c'est aussi un rêveur un peu chaotique. Dans une conversation normale, si le robot dit quelque chose de stupide comme « SUPPRIMEZ TOUTES LES TABLES » alors qu'il était seulement censé faire un « SELECT », personne n'est blessé. Mais dans une banque ou un hôpital, cette erreur est un désastre.

Entrez en scène GRID (Grammar-Railed Decoding - Décodage Guidé par la Grammaire). Considérez GRID non pas comme un professeur qui crie « Non ! » après qu'un robot a fait une erreur, mais comme une magique voie ferrée sur laquelle le robot doit rouler. Le robot peut toujours être créatif, mais il lui est physiquement impossible de faire dérailler le train. Si la voie n'existe pas, le robot ne peut même pas penser à ce mot.

La Magique Voie Ferrée

Habituellement, quand vous demandez à un robot d'écrire du code, vous le laissez deviner le mot suivant, puis vous vérifiez si la phrase entière a du sens. Si elle ne va pas, vous la supprimez et vous réessayez. C'est lent et risqué.

GRID change la donne. Au lieu de vérifier la phrase entière à la fin, il vérifie chaque étape avant même que le robot ne soit autorisé à choisir un mot. Il fait cela en regardant une « carte » de la grammaire (les règles du langage) et la position actuelle du robot sur cette carte.

Le problème avec les anciennes cartes : Les méthodes précédentes essayaient de mémoriser chaque phrase possible que le robot pourrait écrire. Le papier explique que c'est impossible. Si vous essayiez de lister chaque phrase valide, même de longueur modérée, cette liste serait plus grande que le nombre d'atomes dans l'univers entier.
La solution GRID : Au lieu de mémoriser des phrases, GRID mémorise des configurations. Imaginez le robot comme un randonneur. Les anciennes méthodes essayaient de mémoriser chaque sentier possible que le randonneur pourrait prendre. GRID vérifie simplement : « Le randonneur se trouve-t-il actuellement sur une partie valide du sentier ? » Si oui, le robot peut continuer à marcher. Si non, le chemin est bloqué. Cela permet de garder le système rapide, même pour des phrases très longues.

Les zones d'interdiction (Politique et Règles)

Dans une grande entreprise, différentes personnes ont des règles différentes. Un employé junior n'est peut-être autorisé qu'à consulter les données (SELECT), tandis qu'un manager peut les supprimer.

GRID intègre ces règles directement dans les rails du train.

Des voies basées sur les rôles : Si le robot agit en tant qu'« Employé Junior », les voies pour « DELETE » ou « UPDATE » n'existent tout simplement pas. Le robot ne peut même pas les imaginer. Ce n'est pas que le robot se voit dire « Non, ne fais pas ça » ; c'est que le mot « DELETE » est invisible pour lui dans ce mode.
Des voies de Schéma : Le robot connaît également exactement quelles tables et colonnes existent dans la base de données. Si une table n'existe pas, la voie menant à elle est supprimée. Le robot ne peut pas taper accidentellement un faux nom de table.

Le papier est très honnête sur ce que cette voie magique ne peut pas faire. Il prouve que la voie ne peut pas empêcher le robot de choisir la mauvaise colonne pour une ligne spécifique (comme choisir « salaire » au lieu de « nom ») car cette décision dépend d'un contexte qui n'apparaît qu'après la fin de la phrase. Pour ces cas délicats, GRID utilise un « vérificateur » qui examine la phrase terminée et la corrige si nécessaire.

Vitesse et Sécurité : Le coût « plat »

L'une des plus grandes inquiétudes concernant ces vérifications de sécurité est la vitesse. Généralement, plus la phrase est longue, plus la vérification de sécurité devient lente. Le papier appelle cela « l'Exigence R ».

GRID promet quelque chose de spécial : le coût de la vérification reste plat.

Que le robot écrive le 5ème mot ou le 16 000ème mot, le temps nécessaire pour vérifier si le mot suivant est autorisé est à peu près le même.
Les auteurs ont mesuré cela sur des ordinateurs puissants (GPU H100). Ils ont constaté que pour chaque jeton (partie de mot), la vérification prend entre 3,6 et 6,7 microsecondes (c'est-à-dire des millionièmes de seconde) lorsque le système est chaud et prêt.
Même lorsque le robot rencontre une nouvelle base de données qu'il n'a jamais vue auparavant, le système gère la situation avec élégance. Les premiers mots peuvent prendre un peu plus de temps (environ 27,3 millisecondes pour la configuration initiale), mais une fois cela fait, il fonctionne à pleine vitesse. Crucialement, ce temps de configuration ne ralentit pas les autres robots travaillant en même temps.

Le reçu de la « Boîte Noire » (Piste d'audit)

Dans une banque, vous devez savoir exactement ce qui s'est passé. Si un robot a pris une décision, vous devez pouvoir la rejouer plus tard pour prouver qu'elle était sûre.

GRID conserve une piste d'audit à chaîne de hachage. Imaginez un reçu numérique pour chaque mot que le robot est autorisé à prononcer. Ce reçu est enchaîné comme une chaîne de trombones. Si quelqu'un tente de modifier un seul mot dans le passé, toute la chaîne se brise, et vous savez immédiatement que le registre a été falsifié. Le papier montre qu'ils peuvent rejouer 1 000 générations de ces décisions et obtenir exactement le même résultat à chaque fois, avec une détection de falsification de 100 %.

À quel point cela fonctionne-t-il ?

Le papier ne se contente pas de prétendre que cela fonctionne ; ils l'ont testé sur des données réelles (le jeu de données Spider, qui contient plus de 1 000 questions complexes).

Pour les petits robots (0,5 milliard de paramètres) : L'utilisation de GRID a amélioré le nombre de bonnes réponses de 13 points de pourcentage. La raison principale ? Le robot a cessé de faire des erreurs de grammaire stupides.
Pour les robots plus grands et plus intelligents (7 milliards de paramètres) : La vérification grammaticale seule a aidé un peu (environ +1 point), mais lorsqu'ils ont ajouté le « vérificateur » pour corriger les erreurs de colonnes délicates, le taux de réussite a bondi à 94,5 %.

La vérité honnête

Les auteurs sont très prudents pour ne pas faire de fausses promesses. Ils admettent certaines choses :

Ce n'est pas parfait pour toutes les langues : Cela fonctionne mieux pour les langues qui suivent des règles spécifiques (LALR(1)), comme le SQL. Il ne peut pas encore gérer tous les types de grammaires du monde.
Cela change la « saveur » : En forçant le robot à rester sur les rails, cela change légèrement la façon dont le robot choisit ses mots. Le papier a mesuré cela et a trouvé que pour les très petits robots, ce changement compte, mais pour les robots grands et intelligents, le bénéfice d'être correct l'emporte sur le léger changement de style.
Démarrages à froid : Lorsqu'une toute nouvelle base de données arrive, il y a un ralentissement temporaire et infime (environ 34 % pendant un instant) pendant que le système construit les nouvelles voies. Mais cela n'arrive qu'une seule fois par nouvelle base de données, et cela n'empêche pas les autres robots de travailler.

En résumé, GRID est comme la construction d'un système de train super sûr et à haute vitesse pour l'IA. Il ne se contente pas de dire à l'IA « ne vous écrasez pas » ; il construit les rails de manière à ce que l'écrasement soit physiquement impossible, tout en gardant le train assez rapide pour être utile dans le monde réel.

Résumé Technique : GRID (Grammar-Railed Decoding for Enterprise SQL)

1. Énoncé du Problème

Le document traite de l'écart entre la génération de texte « plausible » par les modèles de langage (LLM) et les exigences strictes de la génération SQL en entreprise. Dans les déploiements d'entreprise de type CRUD/RBAC (Contrôle d'accès basé sur les rôles), les sorties doivent être syntaxiquement valides, respecter les politiques par rôle et par schéma, et fournir des garanties prouvables plutôt que des résultats basés sur le « meilleur effort ». Les auteurs identifient six défis critiques que les solutions existantes ne parviennent pas à résoudre simultanément :

Validité et Politique Conjointes : Les sorties doivent être analysées selon le dialecte SQL spécifique tout en imposant strictement les restrictions de verbes par rôle et le vocabulaire spécifique au schéma (tables/colonnes réelles) par construction, et non via un filtrage post-hoc.
Garanties Prouvables : Les systèmes doivent offrir des théorèmes formels de correction (soundness — ne jamais émettre de tokens invalides), de complétude (ne jamais bloquer de continuations valides) et de terminaison, vérifiés par des tests spécifiques.
Coût par Token Plat (Exigence R) : Le coût du « garde-fou » (masquage) doit être amorti à $O(1)$ par token, indépendamment de la longueur de la génération $n$ . Les systèmes existants souffrent souvent de coûts qui croissent linéairement ou quadratiquement avec la longueur du contexte.
Piste d'Audit Rejouable : La conformité exige un enregistrement chaîné par hachage, bit à bit identique, de chaque décision d'autorisation ou de blocage pour répondre à la question « qu'a-t-on autorisé et pourquoi » a posteriori.
Service de la Réalité : Les environnements de production impliquent des requêtes hétérogènes et groupées (batched). Le système doit gérer les arrivées de « schémas à froid » (nouveaux schémas jamais vus auparavant) sans bloquer les requêtes « à chaud » co-groupées ou substituer des masques approximatifs.
Limites Honnêtes : Le système doit explicitement reconnaître ce qui ne peut être imposé par un masque contextuel sensible à la gauche (notamment le RBAC au niveau des colonnes) et fournir des mécanismes pour gérer ce résidu.

2. Méthodologie : Décodage à Garde-Fou Grammatical (Grammar-Railed Decoding)

GRID introduit une architecture novatrice où tout est indexé sur des configurations de l'analyseur (parser) plutôt que sur des séquences de tokens.

Idée Architecturale Centrale

Au lieu de précalculer des tables de validité sur des séquences de tokens (qui croissent de manière combinatoire), GRID indexe tous les masques, entrées de cache et enregistrements d'audit sur la configuration du parseur. Une configuration $\kappa$ est définie par la paire $(\sigma, \rho)$ :

$\sigma$ : La pile de l'analyseur LALR(1).
$\rho$ : L'état de balayage du lexer sur le lexème partiel actuel (octets restants).

Cette configuration détermine de manière unique l'ensemble des préfixes viables (continuations pouvant mener à une phrase valide).

Composants Clés

Oracle de Préfixe Viable : L'analyseur incrémental LALR(1) lui-même sert d'oracle. En simulant la chaîne de réduction sur une pile virtuelle, le système détermine l'ensemble des terminaux autorisés. Cela évite le « blocage de sémantique d'acceptation » où des préfixes à un seul token pourraient être rejetés si le système ne vérifiait que des phrases complètes.
Pont Token-Terminal : Puisque les tokens LLM (chaînes d'octets) ne s'alignent pas sur les lexèmes de la grammaire, GRID utilise une marche dans un trie au niveau des octets.
- Tokens Indépendants du Contexte (CI) : Tokens qui se résolvent dans le lexème actuel ou se terminent exactement à une frontière de terminal. Ils sont mémorisables (cacheables).
- Tokens Dépendants du Contexte (CD) : Tokens qui traversent une frontière de terminal (par exemple, complétant un mot-clé et commençant un nouveau). Ils ne sont jamais mis en cache ; ils sont vérifiés contre la pile active à chaque étape pour garantir la correction.
Compilation de la Politique :
- Projections de Rôles (L2) : Sous-ensemble des productions grammaticales (par exemple, supprimer les verbes DELETE) et élimination des symboles inutiles.
- Lexiques de Schémas (L3) : Restriction des terminaux d'identifiants pour permettre des listes d'autorisation dérivées du catalogue de la base de données.
- Règle de Composition d'Identifiant : Aux positions d'identifiants, le masque est dérivé strictement de l'intersection du trie des tokens et du trie du lexique du schéma, empêchant les entrées de cache génériques d'admettre des identifiants interdits.
Stratégie de Mise en Cache (OBL-KEY1) : Un cache à deux niveaux avec écriture différée (T1 pour les grammaires spécifiques, T2 pour les familles de grammaires partagées) utilise des clés dérivées de la configuration. Le système impose un « raffinement de type Myhill–Nerode » où deux configurations partageant une clé doivent produire des masques de CI bit à bit identiques.
Chaîne d'Audit : Chaque étape ajoute un enregistrement (étape, hachage de configuration, ID d'entrée de masque, token, compte de blocage) chaîné via BLAKE2b. Cela permet un rejeu bit à bit identique des générations contre les artefacts archivés.

Implémentation du Système

Noyaux Rust : Le chemin critique (marche dans le trie, verdicts CD, avancée LALR, remplissage du masque de bits) est implémenté en Rust pour minimiser la latence et libérer le GIL de Python.
Contrat de Service (vLLM) : Le système superpose le calcul du masque sur le CPU avec le passage forward sur le GPU. Si le masque d'une requête à schéma « froid » n'est pas prêt, il est différé d'un tour, garantissant que les requêtes « à chaud » co-groupées ne sont jamais bloquées.
Réparation Guidée par le Vérificateur : Pour le résidu que les masques ne peuvent imposer (RBAC au niveau des colonnes), le système utilise un vérificateur sémantique post-analyse. Si une violation est détectée, le système peut guider une passe de réparation pour corriger la requête.

3. Contributions Clés

Cadre Formel : Un cadre de décodage contraint indexé sur la configuration utilisant un analyseur incrémental LALR(1) comme oracle de préfixe viable, avec un pont jeton-terminal au niveau des octets et une distinction entre contexte indépendant et dépendant.
Garanties Prouvables : Quatre garanties (Correction, Complétude, Terminaison, Coût Plat) énoncées sous forme de propositions avec des préconditions explicites, accompagnées de tests spécifiques pour la vérification.
Réalisation Système : Un système prêt pour la production (noyaux v4–v7) comprenant un pipeline grammatical, des noyaux Rust, un cache à deux niveaux et un journal d'audit chaîné par hachage.
Record de Benchmark : Évaluation complète incluant la latence par token, les mesures de pente de l'exigence R, MaskBench (JSON Schema), la précision d'exécution Spider et les records de service vLLM de bout en bout.

4. Résultats

Latence : Sur un exécuteur H100 SXM5, GRID atteint une latence de masque médiane par token de 3,6–6,7 µs (p50) et 80–109 µs (p90), surpassant llguidance et XGrammar en p50 et p90 sur les tokenizer gpt2 et Qwen. lluidance conserve la queue p99 la plus plate.
Exigence R (Coût Plat) : À $n=16\,000$ tokens, la pente du coût par token est effectivement nulle ( $\approx 0$ ), confirmant un coût amorti de $O(1)$ . En revanche, les anciennes versions de guidage montraient une croissance quadratique.
Précision d'Exécution (Spider) :
- Modèle 0.5B : Le décodage contraint seul apporte +13 points de précision d'exécution (EX) par rapport à la génération non contrainte (29,0 % contre 16,0 %).
- Modèle 7B : Le masque seul apporte environ +1 point. Cependant, l'ajout d'une passe de réparation guidée par le vérificateur pour les violations au niveau des colonnes porte l'exécution à 94,5 % (EX +2,3 par rapport à l'incontraint).
Surcharge de Service : Sous vLLM avec une taille de batch de 32, la surcharge est de +1,51 % de temps par token de sortie.
Gestion du Démarrage à Froid : Un schéma frais subit un temps de spécialisation de 27,3 ms et une latence du premier token de ~0,7 ms. Bien que cela cause un ralentissement transitoire de **34 %** pour les requêtes co-groupées à chaud pendant la fenêtre de spécialisation (dû à la contention de la bande passante CPU/mémoire), les requêtes à chaud ne sont jamais bloquées, et la requête fraîche tourne ensuite à une vitesse de 1,00× par rapport aux requêtes à chaud.
Intégrité de l'Audit : 1 000 générations ont été rejouées de manière bit à bit identique avec une détection de falsification de 100 %.

5. Signification et Limites Honnêtes

Le papier affirme que GRID démontre qu'un décodage contraint de classe entreprise est réalisable en s'engageant sur un décodage indexé sur la configuration. Cet engagement unique permet la compilation de politiques, les garanties prouvables, les coûts plats et les audits rejouables.

Les auteurs sont explicites quant aux limites et aux frontières de leur système :

Fidélité de la Distribution : Le papier ne prétend pas que le masquage préserve la distribution de probabilité originale $P(x | x \in L)$ ; il renormalise localement. L'impact est mesuré via la précision d'exécution en aval, et non par la neutralité distributionnelle.
RBAC au Niveau des Colonnes : Le papier prouve (Proposition 11) que les restrictions au niveau des colonnes ne peuvent pas être imposées par un masque CFG de gauche à droite car le lien nécessaire entre l'alias et la table est inconnu au moment du masquage de la colonne. Cela est géré via une vérification et une réparation post-analyse, et non par le masque lui-même.
Portée du Langage : Le système est limité aux langages LALR(1). Bien qu'il gère les dialectes SQL standards, il déclare des erreurs de compilation pour les constructions non-LALR(1) (par exemple, certains motifs JSON Schema).
Contention de la Fenêtre à Froid : Le ralentissement transitoire des requêtes co-groupées lors de la spécialisation d'un nouveau schéma est reconnu comme un véritable problème de contention de la bande passante CPU/mémoire de l'hôte, et non comme un défaut logiciel, représentant un compromis d'isolement de calcul.
Terminaison : Les garanties de terminaison complète (arrêts réservés/complétés) ne tiennent que dans la boucle de décodage possédée par GRID ; les modes de service de type processeur peuvent tronquer.

En résumé, GRID fournit un cadre rigoureux et performant pour la génération SQL en entreprise qui privilégie la correction, l'application des politiques et l'auditabilité, tout en délimitant honnêtement les limites de ce qui peut être imposé via un masquage grammatical.