論文の概要: Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance
- arxiv url: http://arxiv.org/abs/2608.28229v1
- Date: Fri, 28 Aug 2026 11:44:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-31 17:16:04.304429
- Title: Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance
- Title（参考訳）: コンテキストなしの文法準拠を保証するための距離誘導デコーディング
- Abstract要約: 本稿では,プッシュダウンオートマトンに基づく文脈自由文法のためのルックアヘッド誘導型デコーディングフレームワークを提案する。
結果として得られるデコーダは構文的に健全であり、全ての出力はターゲット文法によって受け入れられる。
- 参考スコア（独自算出の注目度）: 18.38520405734125
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Grammar-constrained decoding helps large language models produce syntactically valid structured outputs, such as code, JSON, and SQL. For context-free grammars, many practical decoders enforce local prefix feasibility: each token must keep the current prefix extendable to some valid completion. Yet, under tokenizer-grammar mismatch and finite token budgets, feasible prefixes may still fail to reach acceptance. We propose a lookahead-guided decoding framework for context-free grammars based on pushdown automata. Offline, we compute bounded pushdown summaries with reachability labels and upper-bound distances to acceptance. Online, these estimates guide horizon-aware pruning and beam search. The resulting decoder is syntactically sound: every output is accepted by the target grammar. Experiments on JSON, SQL, and Linear Temporal Logic (LTL) show both consistent syntactic validity and improved completion quality over existing baselines.
- Abstract（参考訳）: 文法に制約のあるデコーディングは、大規模な言語モデルが、コード、JSON、SQLなどの構文的に有効な構造化された出力を生成するのに役立つ。
文脈のない文法では、多くの実用的なデコーダが局所的な接頭辞を強制する: 各トークンは、有効な完了まで現在の接頭辞を拡張できなければならない。
しかし、トークンライザと文法のミスマッチと有限トークンの予算の下では、実現可能なプレフィックスはまだ受け入れられないかもしれない。
本稿では,プッシュダウンオートマトンに基づく文脈自由文法のためのルックアヘッド誘導型デコーディングフレームワークを提案する。
オフラインでは、到達可能性ラベルと受容までの上限距離を持つ有界プッシュダウンサマリーを計算します。
オンラインでは、これらの推定は地平線対応プルーニングとビームサーチを導く。
結果として得られるデコーダは構文的に健全であり、全ての出力はターゲット文法によって受け入れられる。
JSON、SQL、LTL(Linear Temporal Logic)の実験は、一貫性のある構文的妥当性と、既存のベースラインよりも優れた補完品質の両方を示している。
関連論文リスト
- Efficient Grammar-Constrained Decoding via Parser Stack Classification [27.415578917916054]
GCD(Grammar-Constrained Decoding)は、文脈自由文法で規定された規則に違反したトークンをマスキングすることで、生成された出力の構文的妥当性を保証する。
本稿では,新しい文法制約付き復号法であるPSCを提案する。
PSCは、デコードステップ毎にスタックを正確に1回チェックすることで、完全なマスクを計算できる。
論文 参考訳（メタデータ） (2026-08-04T03:26:54Z) - 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) - Attention Meets Reachability: Structural Equivalence and Efficiency in Grammar-Constrained LLM Decoding [0.2864713389096699]
我々は、文脈自由文法(CFG)からコンパイルされたプッシュダウンシステム上での自己回帰的次トーケン分布と到達可能性との結合として文法制約デコーディング(GCD)を研究する。
文法の復号コスト等価クラスを定義し、有界書き直し科における最小SAC代表者の存在を証明した。
論文 参考訳（メタデータ） (2026-03-04T11:49:55Z) - Token-Oriented Object Notation vs JSON: A Benchmark of Plain and Constrained Decoding Generation [0.0]
Token-Oriented Object Notation (TOON) は、構造化データを LLM に転送するためのシリアライズフォーマットとして、トークンの使用量を大幅に削減することを目的としている。
これをテストするために,構造的複雑性,検証,および平文生成と構造的出力の比較に関して,いくつかのテストケースを作成するベンチマークを行った。
論文 参考訳（メタデータ） (2026-02-08T11:58:03Z) - Are you going to finish that? A Practical Study of the Partial Token Problem [85.49816027251013]
言語モデル(LM)はトークンのシーケンスによって訓練されるが、ユーザはテキストを介してLMと対話する。
このミスマッチは、ユーザーが期待する次のトークンの途中でプロンプトを終了したときに発生する部分トークン問題を引き起こす。
この研究では、トークンと"ワード"境界がしばしば並んでいない3つのドメインを特定します。
論文 参考訳（メタデータ） (2026-01-30T17:47:16Z) - Correctness-Guaranteed Code Generation via Constrained Decoding [11.531496728670746]
本稿では,意味論的に正しいプログラムを生成するための制約付き実行時復号アルゴリズムを提案する。
提案手法は,任意の所定のスクリプティングAPIに従って,意味的に正しいプログラムを生成することができることを示す。
さらに、慎重に設計することで、我々のセマンティック保証が正当性にまで拡張され、ローグライクなビデオゲームにゲームメカニクスを発生させることで検証されることを示す。
論文 参考訳（メタデータ） (2025-08-20T20:48:18Z) - $\texttt{SEM-CTRL}$: Semantically Controlled Decoding [53.86639808659575]
$texttSEM-CTRL$は、LLMデコーダに直接、リッチなコンテキスト依存制約とタスクおよびインスタンス固有のセマンティクスを強制する統一的なアプローチである。
texttSEM-CTRL$は、小さな訓練済みのLLMがより大きな変種や最先端の推論モデルよりも効率的に性能を向上することを可能にする。
論文 参考訳（メタデータ） (2025-03-03T18:33:46Z) - Tokenization as Finite-State Transduction [24.19959327497118]
正規言語の全てのトークン化を効率的にエンコードできる有限状態フレームワークを導入する。
そのByte-Pairを示します。
Match(BPE)とMaxPiece(WordPiece)がこのフレームワークに適合する。
これの応用は、あるパターンにマッチするように言語モデルの出力を制約するガイド付き生成である。
論文 参考訳（メタデータ） (2024-10-21T07:10:07Z) - Linear-Time Modeling of Linguistic Structure: An Order-Theoretic
Perspective [97.57162770792182]
文字列内のトークンのペア間の関係をモデル化するタスクは、自然言語を理解する上で不可欠な部分である。
これらの徹底的な比較は避けられ、さらに、トークン間の関係を文字列上の部分順序としてキャストすることで、複雑さを線形に減らすことができる。
提案手法は,文字列中の各トークンの実際の数を並列に予測し,それに従ってトークンをソートすることで,文字列内のトークンの総順序を決定する。
論文 参考訳（メタデータ） (2023-05-24T11:47:35Z) - Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning [27.59524153097858]
文法制約付き復号法(GCD)は、大言語モデル(LM)の生成を制御するために用いられる。
GCDは一般に構造化NLPタスクの統一フレームワークとして機能する。
文法制約付きLMは、制約なしLMよりも大幅に優れるか、タスク固有の微調整モデルよりも優れていることを示す。
論文 参考訳（メタデータ） (2023-05-23T11:54:37Z) - On Parsing as Tagging [66.31276017088477]
そこで我々は,現在最先端の選挙区タグであるテトラタグを減らして,シフト-リデュース解析を行う方法を示す。
我々は、線形化器、学習者、復号器の異なる選択でタグ付けパイプラインの分類を実証的に評価する。
論文 参考訳（メタデータ） (2022-11-14T13:37:07Z) - Lexically-constrained Text Generation through Commonsense Knowledge
Extraction and Injection [62.071938098215085]
我々は、ある入力概念のセットに対して妥当な文を生成することを目的としているcommongenベンチマークに焦点を当てる。
生成したテキストの意味的正しさを高めるための戦略を提案する。
論文 参考訳（メタデータ） (2020-12-19T23:23:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。