論文の概要: Efficient Grammar-Constrained Decoding via Parser Stack Classification
- arxiv url: http://arxiv.org/abs/2608.03065v1
- Date: Tue, 04 Aug 2026 03:26:54 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-06 07:04:20.692801
- Title: Efficient Grammar-Constrained Decoding via Parser Stack Classification
- Title（参考訳）: パーサスタック分類による効率よい文法制約付き復号法
- Abstract要約: GCD(Grammar-Constrained Decoding)は、文脈自由文法で規定された規則に違反したトークンをマスキングすることで、生成された出力の構文的妥当性を保証する。
本稿では,新しい文法制約付き復号法であるPSCを提案する。
PSCは、デコードステップ毎にスタックを正確に1回チェックすることで、完全なマスクを計算できる。
- 参考スコア（独自算出の注目度）: 27.415578917916054
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: LLMs are widely used to generate structured output like source code or JSON. Grammar-constrained decoding (GCD) can guarantee the syntactic validity of the generated output, by masking out tokens that violate rules specified by a context-free grammar. However, the online computational overhead of existing GCD methods, with latency typically scaling linearly with vocabulary size, limits the throughput of LLMs, especially for models with large vocabularies. To address this issue, we propose PSC, a novel grammar-constrained decoding method. By combining acceptance conditions of all vocabulary tokens into a single classifier of the parser stack during preprocessing, PSC can compute the complete vocabulary mask by checking the parser stack exactly once per decoding step, with time complexity independent of the vocabulary size. Experiments show that PSC computes masks up to 700$\times$ faster than baselines on complex programming language grammars, and up to 30$\times$ faster for schema-conformant JSON; end-to-end LLM throughput with PSC approaches that of unconstrained decoding. We analyze the preprocessing overhead for preprocessing providers and decoding users, and provide a break-even point analysis to help users decide whether to do preprocessing by themselves.
- Abstract（参考訳）: LLMは、ソースコードやJSONのような構造化出力を生成するために広く使用されている。
GCD(Grammar-Constrained Decoding)は、文脈自由文法で規定された規則に違反したトークンをマスキングすることで、生成された出力の構文的妥当性を保証する。
しかしながら、既存のGCD手法のオンライン計算オーバーヘッドは、特に大きな語彙を持つモデルにおいて、遅延は通常、語彙サイズで線形にスケーリングする。
この問題に対処するために,新しい文法制約付き復号法であるPSCを提案する。
プリプロセッシング中に全ての語彙トークンの受け入れ条件をパーサスタックの単一分類子に組み合わせることで、PSCはデコードステップ毎に正確に1回だけパーサスタックをチェックすることで完全な語彙マスクを計算できる。
実験によると、PSCは複雑なプログラミング言語文法のベースラインよりも700$\times$高速、スキーマ変換JSONでは最大30$\times$高速、PSCによるエンドツーエンドのLCMスループットは制約のないデコードにアプローチしている。
我々は,プリプロセスプロバイダとデコードユーザの事前処理オーバーヘッドを分析し,ユーザが自身でプリ処理を行うかどうかを判断するためのブレークスルーポイント分析を提供する。
関連論文リスト
- Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance [18.38520405734125]
本稿では,プッシュダウンオートマトンに基づく文脈自由文法のためのルックアヘッド誘導型デコーディングフレームワークを提案する。
結果として得られるデコーダは構文的に健全であり、全ての出力はターゲット文法によって受け入れられる。
論文 参考訳（メタデータ） (2026-08-28T11:44:53Z) - Weave of Formal Thought [51.56484100374058]
WoFT(Weave of Formal Thought)は、厳密な構文的検証と学習された構造的表現を結合したパラダイムである。
本稿では,非終端文法記号を直接生成にインターリーブするために,言語モデルを訓練する潜時可変微調整法を提案する。
Pythonでは、RWS目的のStarCoder2-3Bを微調整することで、テキストのみのSFTベースラインと比較して、トーケン毎のクロスエントロピーが14.3%削減される。
論文 参考訳（メタデータ） (2026-06-24T15:58:11Z) - Prefix Parsing is Just Parsing [53.010152712125766]
プレフィックスパーシングは、入力プレフィックスを与えられた文法によって生成された完全な文字列に拡張できるかどうかを問う。
そこで我々は,プレフィックス文法変換を導入し,プレフィックス解析を通常の構文解析に効率よく還元する。
また,次点重みベクトルを計算するためのアルゴリズム微分に基づく戦略も提案する。
論文 参考訳（メタデータ） (2026-04-23T01:20:40Z) - Sampling from Your Language Model One Byte at a Time [82.71473348639489]
トークン化は、PBP(Prompt Boundary Problem)として知られるモデル世代に歪みをもたらす可能性がある。
BPEトークン化器を用いて任意のオートレ LM を文字レベルまたはバイトレベル LM に変換する推論時間法を提案する。
提案手法は, PBPを効率的に解き, 異なるトークン化器で言語モデルの語彙を統一することができる。
論文 参考訳（メタデータ） (2025-06-17T02:37:04Z) - Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
トークンの制約を評価するのは 違法にコストがかかる
LCDは文字列上のグローバル分布を歪め、ローカル情報のみに基づいてトークンをサンプリングすることができる。
我々のアプローチは最先端のベースラインよりも優れていることを示す。
論文 参考訳（メタデータ） (2025-04-07T18:30:18Z) - $\ exttt{SEM-CTRL}$: Semantically Controlled Decoding [53.86639808659575]
$texttSEM-CTRL$は、LLMデコーダに直接、リッチなコンテキスト依存制約とタスクおよびインスタンス固有のセマンティクスを強制する統一的なアプローチである。
texttSEM-CTRL$は、小さな訓練済みのLLMがより大きな変種や最先端の推論モデルよりも効率的に性能を向上することを可能にする。
論文 参考訳（メタデータ） (2025-03-03T18:33:46Z) - Flexible and Efficient Grammar-Constrained Decoding [5.671312847528642]
文法制約付き復号法(GCD)は、LLM出力がそのような規則と一致することを保証できる。
既存のGCDアルゴリズムでは、共通文法を前処理するのに何分もかかる。
本稿では,既存の手法よりも17.71倍高速なオフライン前処理を実現するGCDアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-02-07T17:35:17Z) - Tokenization as Finite-State Transduction [24.19959327497118]
正規言語の全てのトークン化を効率的にエンコードできる有限状態フレームワークを導入する。
そのByte-Pairを示します。
Match(BPE)とMaxPiece(WordPiece)がこのフレームワークに適合する。
これの応用は、あるパターンにマッチするように言語モデルの出力を制約するガイド付き生成である。
論文 参考訳（メタデータ） (2024-10-21T07:10:07Z) - Using Grammar Masking to Ensure Syntactic Validity in LLM-based Modeling Tasks [0.996023506058745]
文法マスキング(Grammar masking)は、与えられた文脈自由文法に対して構文的に正しいモデルを生成するための大きな言語モデルを導くために用いられる。
文法マスキングは,複数の言語モデルのモデリング能力を劇的に向上させることができることを示す。
論文 参考訳（メタデータ） (2024-07-08T17:19:59Z) - Grammar-Aligned Decoding [30.972850034752884]
LLM(Large Language Models)は、プログラムコード、数学的公式、整形されたマークアップなどの高度に構造化された出力を確実に生成するのに苦労する。
制約付き復号法は、LLMが出力できるトークンを各ステップで厳格に制限し、出力が与えられた制約と一致することを保証することによってこの問題を軽減する。
本稿では,GCD技術がLLMの分布を歪め,文法的だがLLMに比例しない確率で現れる出力を導出することを示す。
論文 参考訳（メタデータ） (2024-05-31T17:39:15Z) - Decoding at the Speed of Thought: Harnessing Parallel Decoding of Lexical Units for LLMs [57.27982780697922]
大規模言語モデルは、自然言語の理解と生成において例外的な能力を示した。
しかし、それらの生成速度は、その復号過程の本質的にシーケンシャルな性質によって制限される。
本稿では,データ駆動方式で実装された新しいデコーディング手法であるLexical Unit Decodingを紹介する。
論文 参考訳（メタデータ） (2024-05-24T04:35:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。