XGrammar : un moteur de génération structuré révolutionnaire pour les grands modèles de langage

Des chercheurs de l'Université Carnegie Mellon, de NVIDIA, de l'Université Jiao Tong de Shanghai et de l'Université de Californie à Berkeley ont développé XGrammar, un moteur de génération structuré révolutionnaire pour répondre à ces limitations.

As LLMs continue to advance, structured generation has become increasingly important. These models are now tasked with generating outputs that follow rigid formats, such as JSON, SQL, or other domain-specific languages. This capability is crucial for applications like code generation, robotic control, or structured querying. However, ensuring that outputs conform to specific structures without compromising speed or efficiency remains a significant challenge. While structured outputs enable seamless downstream processing, achieving these results requires innovative solutions due to the inherent complexity.

À mesure que les LLM continuent de progresser, la génération structurée est devenue de plus en plus importante. Ces modèles sont désormais chargés de générer des sorties qui suivent des formats rigides, tels que JSON, SQL ou d'autres langages spécifiques à un domaine. Cette fonctionnalité est cruciale pour des applications telles que la génération de code, le contrôle robotique ou les requêtes structurées. Cependant, garantir que les résultats soient conformes à des structures spécifiques sans compromettre la rapidité ou l’efficacité reste un défi de taille. Même si les résultats structurés permettent un traitement transparent en aval, l’obtention de ces résultats nécessite des solutions innovantes en raison de la complexité inhérente.

Despite the recent advances in LLMs, there are still inefficiencies in structured output generation. One major challenge is handling the computational demands of adhering to grammatical constraints during output generation. Traditional methods, like context-free grammar (CFG) interpretation, require processing each possible token in the model’s vocabulary, which can exceed 128,000 tokens. Moreover, maintaining stack states to track recursive grammar rules adds to runtime delays. As a result, existing systems often experience high latency and increased resource usage, making them unsuitable for real-time or large-scale applications.

Malgré les progrès récents des LLM, il existe encore des inefficacités dans la génération de résultats structurés. L’un des défis majeurs consiste à gérer les exigences informatiques liées au respect des contraintes grammaticales lors de la génération du résultat. Les méthodes traditionnelles, comme l'interprétation de la grammaire sans contexte (CFG), nécessitent le traitement de chaque jeton possible dans le vocabulaire du modèle, qui peut dépasser 128 000 jetons. De plus, le maintien des états de la pile pour suivre les règles de grammaire récursives ajoute aux retards d'exécution. En conséquence, les systèmes existants connaissent souvent une latence élevée et une utilisation accrue des ressources, ce qui les rend inadaptés aux applications en temps réel ou à grande échelle.

Current tools for structured generation utilize constrained decoding methods to ensure outputs align with predefined rules. These approaches filter out invalid tokens by setting their probabilities to zero at each decoding step. While effective, constrained decoding often needs to improve its efficiency due to evaluating each token against the entire stack state. Also, the recursive nature of CFGs further complicates these runtime processes. These challenges have limited the scalability and practicality of existing systems, particularly when handling complex structures or large vocabularies.

Les outils actuels de génération structurée utilisent des méthodes de décodage contraintes pour garantir que les sorties s'alignent sur des règles prédéfinies. Ces approches filtrent les jetons invalides en définissant leurs probabilités à zéro à chaque étape de décodage. Bien qu'efficace, le décodage contraint doit souvent améliorer son efficacité en raison de l'évaluation de chaque jeton par rapport à l'état complet de la pile. De plus, la nature récursive des CFG complique encore davantage ces processus d'exécution. Ces défis ont limité l'évolutivité et la praticité des systèmes existants, en particulier lors de la gestion de structures complexes ou de vocabulaires volumineux.

To address these limitations, researchers from Carnegie Mellon University, NVIDIA, Shanghai Jiao Tong University, and the University of California Berkeley developed XGrammar, a groundbreaking structured generation engine. XGrammar introduces a novel approach by dividing tokens into two categories: context-independent tokens that can be prevalidated and context-dependent tokens requiring runtime evaluation. This separation significantly reduces the computational burden during output generation. Also, the system incorporates a co-designed grammar and inference engine, enabling it to overlap grammar computations with GPU-based LLM operations, thereby minimizing overhead.

Pour remédier à ces limitations, des chercheurs de l'Université Carnegie Mellon, de NVIDIA, de l'Université Jiao Tong de Shanghai et de l'Université de Californie à Berkeley ont développé XGrammar, un moteur de génération structuré révolutionnaire. XGrammar introduit une nouvelle approche en divisant les jetons en deux catégories : les jetons indépendants du contexte qui peuvent être prévalidés et les jetons dépendants du contexte nécessitant une évaluation à l'exécution. Cette séparation réduit considérablement la charge de calcul lors de la génération de sortie. En outre, le système intègre un moteur de grammaire et d'inférence co-conçu, lui permettant de chevaucher les calculs de grammaire avec les opérations LLM basées sur GPU, minimisant ainsi les frais généraux.

XGrammar’s technical implementation includes several key innovations. It uses a byte-level pushdown automaton to process CFGs efficiently, enabling it to handle irregular token boundaries and nested structures. The adaptive token mask cache precomputes and stores validity for context-independent tokens, covering over 99% of tokens in most cases. Context-dependent tokens, representing less than 1% of the total, are processed using a persistent execution stack that allows for rapid branching and rollback operations. XGrammar’s preprocessing phase overlaps with the LLM’s initial prompt processing, ensuring near-zero latency for structured generation.

La mise en œuvre technique de XGrammar comprend plusieurs innovations clés. Il utilise un automate de refoulement au niveau des octets pour traiter efficacement les CFG, ce qui lui permet de gérer les limites irrégulières des jetons et les structures imbriquées. Le cache adaptatif du masque de jetons précalcule et stocke la validité des jetons indépendants du contexte, couvrant plus de 99 % des jetons dans la plupart des cas. Les jetons dépendants du contexte, représentant moins de 1 % du total, sont traités à l'aide d'une pile d'exécution persistante qui permet des opérations de branchement et de restauration rapides. La phase de prétraitement de XGrammar chevauche le traitement initial des invites du LLM, garantissant une latence proche de zéro pour la génération structurée.

Performance evaluations reveal the significant advantages of XGrammar. For JSON grammar tasks, the system achieves a token mask generation time of less than 40 microseconds, delivering up to a 100x speedup compared to traditional methods. Integrated with the Llama 3.1 model, XGrammar enables an 80x improvement in end-to-end structured output generation on the NVIDIA H100 GPU. Moreover, memory optimization techniques reduce storage requirements to just 0.2% of the original size, from 160 MB to 0.46 MB. These results demonstrate XGrammar’s ability to handle large-scale tasks with unprecedented efficiency.

Les évaluations de performances révèlent les avantages significatifs de XGrammar. Pour les tâches de grammaire JSON, le système atteint un temps de génération de masque de jeton inférieur à 40 microsecondes, offrant une accélération jusqu'à 100 fois supérieure à celle des méthodes traditionnelles. Intégré au modèle Llama 3.1, XGrammar permet une amélioration de 80 fois de la génération de sortie structurée de bout en bout sur le GPU NVIDIA H100. De plus, les techniques d'optimisation de la mémoire réduisent les besoins de stockage à seulement 0,2 % de la taille d'origine, de 160 Mo à 0,46 Mo. Ces résultats démontrent la capacité de XGrammar à gérer des tâches à grande échelle avec une efficacité sans précédent.

The researchers’ efforts have several key takeaways:

Les efforts des chercheurs ont plusieurs points à retenir :

In conclusion, XGrammar represents a transformative step in structured generation for large language models. Addressing inefficiencies in traditional CFG processing and constrained decoding offers a scalable, high-performance solution for generating structured outputs. Its innovative techniques, such as token categorization, memory optimization, and platform compatibility, make it an essential tool for advancing AI applications. With results up to 100x speedup and reduced latency, XGrammar sets a new standard for structured generation, enabling LLMs to meet modern AI systems’ demands effectively.

En conclusion, XGrammar représente une étape transformatrice dans la génération structurée pour les grands modèles de langage. La résolution des inefficacités du traitement CFG traditionnel et du décodage contraint offre une solution évolutive et hautes performances pour générer des sorties structurées. Ses techniques innovantes, telles que la catégorisation des jetons, l'optimisation de la mémoire et la compatibilité des plateformes, en font un outil essentiel pour faire progresser les applications d'IA. Avec des résultats jusqu'à 100 fois plus rapides et une latence réduite, XGrammar établit une nouvelle norme en matière de génération structurée, permettant aux LLM de répondre efficacement aux demandes des systèmes d'IA modernes.

Check out the Paper and GitHub Page. All credit for this research goes to the researchers of this project. Also, don’t forget to follow us on Twitter and join our Telegram Channel and LinkedIn Group. If you like our work, you will love our newsletter.. Don’t Forget to join our 55k+ ML SubReddit.

Consultez la page Paper et GitHub. Tout le mérite de cette recherche revient aux chercheurs de ce projet. N'oubliez pas non plus de nous suivre sur Twitter et de rejoindre notre chaîne Telegram et notre groupe LinkedIn. Si vous aimez notre travail, vous adorerez notre newsletter. N'oubliez pas de rejoindre notre SubReddit de plus de 55 000 ML.

[FREE AI VIRTUAL CONFERENCE] SmallCon: Free Virtual GenAI Conference ft. Meta, Mistral, Salesforce, Harvey AI & more. Join us on Dec 11th for this free virtual event to learn what it takes to build big with small models from AI trailblazers like Meta, Mistral AI, Salesforce, Harvey AI, Upstage, Nubank, Nvidia, Hugging Face, and more.

[CONFÉRENCE VIRTUELLE SUR L'IA GRATUITE] SmallCon : Conférence virtuelle GenAI gratuite avec Meta, Mistral, Salesforce, Harvey AI et plus. Rejoignez-nous le 11 décembre pour cet événement virtuel gratuit pour découvrir ce qu'il faut pour construire en grand avec de petits modèles de pionniers de l'IA comme Meta, Mistral AI, Salesforce, Harvey AI, Upstage, Nubank, Nvidia, Hugging Face, et plus encore.