XGrammar: Eine bahnbrechende strukturierte Generierungs-Engine für große Sprachmodelle

Forscher der Carnegie Mellon University, NVIDIA, der Shanghai Jiao Tong University und der University of California Berkeley haben XGrammar entwickelt, eine bahnbrechende Engine zur strukturierten Generierung, um diese Einschränkungen zu beseitigen.

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.

Da LLMs immer weiter voranschreiten, wird die strukturierte Generierung immer wichtiger. Diese Modelle haben nun die Aufgabe, Ausgaben zu generieren, die starren Formaten wie JSON, SQL oder anderen domänenspezifischen Sprachen folgen. Diese Fähigkeit ist für Anwendungen wie Codegenerierung, Robotersteuerung oder strukturierte Abfragen von entscheidender Bedeutung. Es bleibt jedoch eine große Herausforderung, sicherzustellen, dass die Ergebnisse bestimmten Strukturen entsprechen, ohne dass Geschwindigkeit oder Effizienz beeinträchtigt werden. Während strukturierte Ausgaben eine nahtlose Weiterverarbeitung ermöglichen, erfordert das Erreichen dieser Ergebnisse aufgrund der inhärenten Komplexität innovative Lösungen.

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.

Trotz der jüngsten Fortschritte bei LLMs gibt es immer noch Ineffizienzen bei der strukturierten Ausgabegenerierung. Eine große Herausforderung besteht darin, den Rechenaufwand zu bewältigen, der sich aus der Einhaltung grammatikalischer Einschränkungen bei der Ausgabegenerierung ergibt. Herkömmliche Methoden wie die Interpretation der kontextfreien Grammatik (CFG) erfordern die Verarbeitung jedes möglichen Tokens im Vokabular des Modells, das 128.000 Token überschreiten kann. Darüber hinaus führt die Aufrechterhaltung von Stapelzuständen zur Verfolgung rekursiver Grammatikregeln zu Laufzeitverzögerungen. Dadurch kommt es bei bestehenden Systemen häufig zu hohen Latenzzeiten und erhöhtem Ressourcenverbrauch, sodass sie für Echtzeit- oder Großanwendungen ungeeignet sind.

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.

Aktuelle Tools zur strukturierten Generierung nutzen eingeschränkte Decodierungsmethoden, um sicherzustellen, dass die Ausgaben mit vordefinierten Regeln übereinstimmen. Diese Ansätze filtern ungültige Token heraus, indem sie ihre Wahrscheinlichkeiten bei jedem Decodierungsschritt auf Null setzen. Die eingeschränkte Dekodierung ist zwar effektiv, muss jedoch häufig ihre Effizienz verbessern, da jedes Token anhand des gesamten Stapelstatus bewertet wird. Darüber hinaus verkompliziert die rekursive Natur von CFGs diese Laufzeitprozesse zusätzlich. Diese Herausforderungen haben die Skalierbarkeit und Praktikabilität bestehender Systeme eingeschränkt, insbesondere bei der Handhabung komplexer Strukturen oder großer Vokabulare.

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.

Um diese Einschränkungen zu beseitigen, haben Forscher der Carnegie Mellon University, NVIDIA, der Shanghai Jiao Tong University und der University of California Berkeley XGrammar entwickelt, eine bahnbrechende Engine zur strukturierten Generierung. XGrammar führt einen neuartigen Ansatz ein, indem es Token in zwei Kategorien unterteilt: kontextunabhängige Token, die vorab validiert werden können, und kontextabhängige Token, die eine Laufzeitbewertung erfordern. Diese Trennung reduziert den Rechenaufwand bei der Ausgabegenerierung erheblich. Darüber hinaus verfügt das System über eine gemeinsam entwickelte Grammatik- und Inferenz-Engine, die es ermöglicht, Grammatikberechnungen mit GPU-basierten LLM-Operationen zu überlappen und so den Overhead zu minimieren.

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.

Die technische Implementierung von XGrammar umfasst mehrere wichtige Neuerungen. Es verwendet einen Pushdown-Automaten auf Byte-Ebene, um CFGs effizient zu verarbeiten, sodass unregelmäßige Token-Grenzen und verschachtelte Strukturen verarbeitet werden können. Der adaptive Token-Masken-Cache berechnet und speichert die Gültigkeit kontextunabhängiger Token und deckt in den meisten Fällen über 99 % der Token ab. Kontextabhängige Token, die weniger als 1 % der Gesamtmenge ausmachen, werden mithilfe eines persistenten Ausführungsstapels verarbeitet, der schnelle Verzweigungs- und Rollback-Vorgänge ermöglicht. Die Vorverarbeitungsphase von XGrammar überschneidet sich mit der anfänglichen Eingabeaufforderungsverarbeitung des LLM und gewährleistet so eine Latenz von nahezu Null für die strukturierte Generierung.

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.

Leistungsbewertungen zeigen die wesentlichen Vorteile von XGrammar. Für JSON-Grammatikaufgaben erreicht das System eine Token-Masken-Generierungszeit von weniger als 40 Mikrosekunden, was eine bis zu 100-fache Geschwindigkeitssteigerung im Vergleich zu herkömmlichen Methoden ermöglicht. Durch die Integration in das Llama 3.1-Modell ermöglicht XGrammar eine 80-fache Verbesserung der durchgängig strukturierten Ausgabegenerierung auf der NVIDIA H100-GPU. Darüber hinaus reduzieren Speicheroptimierungstechniken den Speicherbedarf auf nur 0,2 % der ursprünglichen Größe, von 160 MB auf 0,46 MB. Diese Ergebnisse zeigen die Fähigkeit von XGrammar, umfangreiche Aufgaben mit beispielloser Effizienz zu bewältigen.

The researchers’ efforts have several key takeaways:

Die Bemühungen der Forscher haben mehrere wichtige Erkenntnisse gebracht:

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.

Zusammenfassend stellt XGrammar einen transformativen Schritt in der strukturierten Generierung großer Sprachmodelle dar. Die Beseitigung von Ineffizienzen bei der herkömmlichen CFG-Verarbeitung und der eingeschränkten Dekodierung bietet eine skalierbare, leistungsstarke Lösung für die Generierung strukturierter Ausgaben. Seine innovativen Techniken wie Token-Kategorisierung, Speicheroptimierung und Plattformkompatibilität machen es zu einem unverzichtbaren Werkzeug für die Weiterentwicklung von KI-Anwendungen. Mit bis zu 100-fach schnelleren Ergebnissen und reduzierter Latenz setzt XGrammar einen neuen Standard für die strukturierte Generierung und ermöglicht es LLMs, die Anforderungen moderner KI-Systeme effektiv zu erfüllen.

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.

Schauen Sie sich die Paper- und GitHub-Seite an. Alle Anerkennung für diese Forschung gebührt den Forschern dieses Projekts. Vergessen Sie auch nicht, uns auf Twitter zu folgen und unserem Telegram-Kanal und unserer LinkedIn-Gruppe beizutreten. Wenn Ihnen unsere Arbeit gefällt, werden Sie unseren Newsletter lieben. Vergessen Sie nicht, unserem 55k+ ML SubReddit beizutreten.

[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.

[KOSTENLOSE VIRTUELLE KI-KONFERENZ] SmallCon: Kostenlose virtuelle GenAI-Konferenz mit Meta, Mistral, Salesforce, Harvey AI und mehr. Nehmen Sie am 11. Dezember an dieser kostenlosen virtuellen Veranstaltung teil, um zu erfahren, was es braucht, um mit kleinen Modellen von KI-Vorreitern wie Meta, Mistral AI, Salesforce, Harvey AI, Upstage, Nubank, Nvidia, Hugging Face und anderen Großes zu schaffen.