XGrammar: 大規模言語モデル用の画期的な構造化生成エンジン

カーネギー メロン大学、NVIDIA、上海交通大学、カリフォルニア大学バークレー校の研究者は、これらの制限に対処する画期的な構造化生成エンジンである XGrammar を開発しました。

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.

LLM が進歩し続けるにつれて、構造化された生成の重要性がますます高まっています。これらのモデルは現在、JSON、SQL、またはその他のドメイン固有言語などの厳密な形式に従った出力を生成する役割を担っています。この機能は、コード生成、ロボット制御、構造化クエリなどのアプリケーションにとって非常に重要です。ただし、速度や効率を損なうことなく出力を特定の構造に確実に準拠させることは、依然として大きな課題です。構造化された出力によりシームレスなダウンストリーム処理が可能になりますが、これらの結果を達成するには、固有の複雑さのため革新的なソリューションが必要です。

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.

最近の LLM の進歩にも関わらず、構造化された出力生成には依然として非効率性があります。大きな課題の 1 つは、出力生成中に文法制約を遵守するという計算上の要求に対処することです。文脈自由文法 (CFG) 解釈などの従来の方法では、モデルの語彙内の考えられる各トークンを処理する必要があり、その数は 128,000 トークンを超える場合があります。さらに、再帰文法規則を追跡するためにスタック状態を維持すると、実行時の遅延が増加します。その結果、既存のシステムでは待ち時間が長くなり、リソース使用量が増加することが多く、リアルタイムまたは大規模なアプリケーションには不向きになります。

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.

構造化生成のための現在のツールは、出力が事前定義されたルールに確実に一致するように、制約付きのデコード方法を利用しています。これらのアプローチは、各デコード ステップで確率をゼロに設定することで無効なトークンを除外します。制約付きデコードは効果的ではありますが、スタック全体の状態に対して各トークンを評価するため、多くの場合、効率を向上させる必要があります。また、CFG の再帰的な性質により、これらのランタイム プロセスがさらに複雑になります。これらの課題により、特に複雑な構造や大規模な語彙を処理する場合、既存のシステムの拡張性と実用性が制限されています。

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.

これらの制限に対処するために、カーネギー メロン大学、NVIDIA、上海交通大学、カリフォルニア大学バークレー校の研究者は、画期的な構造化生成エンジンである XGrammar を開発しました。 XGrammar では、トークンを 2 つのカテゴリ (事前検証可能なコンテキストに依存しないトークン) と、実行時評価が必要なコンテキストに依存するトークン (コンテキストに依存するトークン) に分類することで、新しいアプローチが導入されています。この分離により、出力生成時の計算負荷が大幅に軽減されます。また、このシステムには、共同設計された文法および推論エンジンが組み込まれており、文法計算を GPU ベースの LLM 操作と重複させることができるため、オーバーヘッドを最小限に抑えることができます。

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.

XGrammar の技術的な実装には、いくつかの重要な革新が含まれています。バイトレベルのプッシュダウン オートマトンを使用して CFG を効率的に処理し、不規則なトークン境界や入れ子構造を処理できるようにします。アダプティブ トークン マスク キャッシュは、コンテキストに依存しないトークンの有効性を事前計算して保存し、ほとんどの場合、トークンの 99% 以上をカバーします。全体の 1% 未満に相当するコンテキスト依存トークンは、迅速な分岐およびロールバック操作を可能にする永続的な実行スタックを使用して処理されます。 XGrammar の前処理フェーズは LLM の最初のプロンプト処理と重なり、構造化された生成のレイテンシーがほぼゼロになることが保証されます。

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.

パフォーマンス評価により、XGrammar の重要な利点が明らかになります。 JSON 文法タスクの場合、システムは 40 マイクロ秒未満のトークン マスク生成時間を達成し、従来の方法と比較して最大 100 倍の高速化を実現します。 Llama 3.1 モデルと統合された XGrammar により、NVIDIA H100 GPU でのエンドツーエンドの構造化出力生成が 80 倍向上します。さらに、メモリ最適化技術により、ストレージ要件が元のサイズのわずか 0.2%、160 MB から 0.46 MB に削減されます。これらの結果は、XGrammar が前例のない効率で大規模なタスクを処理できる能力を示しています。

The researchers’ efforts have several key takeaways:

研究者らの取り組みには、いくつかの重要なポイントがあります。

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.

結論として、XGrammar は、大規模な言語モデルの構造化生成における変革的なステップを表します。従来の CFG 処理と制約付きデコードの非効率性に対処することで、構造化された出力を生成するためのスケーラブルで高性能なソリューションが提供されます。トークンの分類、メモリの最適化、プラットフォームの互換性などの革新的な技術により、AI アプリケーションを進化させるための不可欠なツールとなっています。 XGrammar は最大 100 倍の高速化と遅延の削減を実現し、構造化生成の新しい標準を確立し、LLM が最新の AI システムの要求に効果的に対応できるようにします。

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.

Paper と GitHub ページをチェックしてください。この研究の功績はすべて、このプロジェクトの研究者に与えられます。また、Twitter で私たちをフォローし、Telegram チャンネルと LinkedIn グループに参加することを忘れないでください。私たちの仕事が気に入ったら、ニュースレターも気に入っていただけるでしょう。55,000 以上の ML SubReddit に参加することを忘れないでください。

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

[無料の AI 仮想カンファレンス] SmallCon: Meta、Mistral、Salesforce、Harvey AI などをフィーチャーした無料の仮想 GenAI カンファレンス。 12 月 11 日に開催されるこの無料の仮想イベントに参加して、Meta、Mistral AI、Salesforce、Harvey AI、Upstage、Nubank、Nvidia、Hugging Face などの AI の先駆者による小規模モデルを使って大規模なものを構築するために何が必要かを学びましょう。