論文の概要: Constrained Decoding of Diffusion LLMs with Context-Free Grammars

• arxiv url: http://arxiv.org/abs/2508.10111v1
• Date: Wed, 13 Aug 2025 18:09:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-15 22:24:48.079786
• Title: Constrained Decoding of Diffusion LLMs with Context-Free Grammars
• Title（参考訳）: 文脈自由文法を用いた拡散LDMの制約デコード
• Authors: Niels Mündler, Jasper Dekoninck, Martin Vechev,
• Abstract要約: 大規模言語モデル(LLM)は、様々な領域で有望なパフォーマンスを示している。 本稿では拡散モデルに対する最初の制約付き復号法を提案する。 本手法は,機能的正当性を維持しつつ,ほぼ完全な統語的正当性を達成できることを示す。
• 参考スコア（独自算出の注目度）: 1.0923877073891446
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large language models (LLMs) have shown promising performance across diverse domains. Many practical applications of LLMs, such as code completion and structured data extraction, require adherence to syntactic constraints specified by a formal language. Yet, due to their probabilistic nature, LLM output is not guaranteed to adhere to such formal languages. Prior work has proposed constrained decoding as a means to restrict LLM generation to particular formal languages. However, existing works are not applicable to the emerging paradigm of diffusion LLMs, when used in practical scenarios such as the generation of formally correct C++ or JSON output. In this paper we address this challenge and present the first constrained decoding method for diffusion models, one that can handle formal languages captured by context-free grammars. We begin by reducing constrained decoding to the more general additive infilling problem, which asks whether a partial output can be completed to a valid word in the target language. This problem also naturally subsumes the previously unaddressed multi-region infilling constrained decoding. We then reduce this problem to the task of deciding whether the intersection of the target language and a regular language is empty and present an efficient algorithm to solve it for context-free languages. Empirical results on various applications, such as C++ code infilling and structured data extraction in JSON, demonstrate that our method achieves near-perfect syntactic correctness while consistently preserving or improving functional correctness. Importantly, our efficiency optimizations ensure that the computational overhead remains practical.
• Abstract（参考訳）: 大規模言語モデル(LLM)は、様々な領域で有望なパフォーマンスを示している。 コード補完や構造化データ抽出といったLLMの実践的応用の多くは、形式言語で指定された構文制約に固執する必要がある。 しかし、その確率的性質のため、LLMの出力はそのような形式言語に従属することが保証されない。 これまでの研究では、LLM生成を特定の形式言語に制限する手段として、制約付き復号法が提案されてきた。 しかしながら、既存の作業は、正式に正しいC++やJSON出力を生成するような実践的なシナリオで使用されるような、拡散LDMの新たなパラダイムには適用できない。 本稿では,この課題に対処し,文脈自由文法で獲得した形式言語を扱える拡散モデルの最初の制約付き復号法を提案する。 まず、より一般的な加法的補充問題に対する制約付き復号法を減らし、対象言語の有効な単語に部分的な出力が完了できるかを問う。 この問題は、制約付き復号化を制約しない、未修正のマルチリージョンを自然に仮定する。 そして,この問題を,対象言語と正規言語との交点が空であるかどうかを判断するタスクに還元し,文脈自由言語に対して効率的な解法を提案する。 C++コードの埋め込みやJSONの構造化データ抽出など,さまざまなアプリケーションにおける実証的な結果から,提案手法がほぼ完全な構文的正当性を実現し,機能的正当性を維持したり改善したりすることを示す。 重要なことは、我々の効率最適化は、計算オーバーヘッドが実用的であることを保証します。

関連論文リスト

• The Unreasonable Effectiveness of Model Merging for Cross-Lingual Transfer in LLMs [54.59207567677249]
  大規模言語モデル(LLM)は、ハイソース言語以外のタスクで依然として苦戦している。 本研究では,タスク固有のポストトレーニングデータが不足している低リソース言語への言語間移動について検討する。
  論文  参考訳（メタデータ） (2025-05-23T20:28:31Z)
• Type-Constrained Code Generation with Language Models [51.03439021895432]
  本稿では,型システムを利用してコード生成を誘導する型制約デコード手法を提案する。 そこで本研究では,新しい接頭辞オートマトンと,在来型を探索する手法を開発し,LLM生成コードに適切な型付けを強制するための健全なアプローチを構築した。 提案手法は,コード合成,翻訳,修復作業において,コンパイルエラーを半分以上削減し,機能的正しさを著しく向上させる。
  論文  参考訳（メタデータ） (2025-04-12T15:03:00Z)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  トークンの制約を評価するのは 違法にコストがかかる LCDは文字列上のグローバル分布を歪め、ローカル情報のみに基づいてトークンをサンプリングすることができる。 我々のアプローチは最先端のベースラインよりも優れていることを示す。
  論文  参考訳（メタデータ） (2025-04-07T18:30:18Z)
• Automata-based constraints for language model decoding [9.137697105669142]
  言語モデル(LM)は、いくつかの形式言語で文字列を生成することがしばしば期待されている。 チューニングにはかなりのリソースが必要で、一般的でない、あるいはタスク固有のフォーマットでは実用的ではない。 我々はこれらの問題をオートマトン理論を適用して解決する。 我々のシステムは、7000倍高速に制約をコンパイルし、確実に正確であり、モジュール方式で拡張することができる。
  論文  参考訳（メタデータ） (2024-07-11T00:25:01Z)
• Decoding at the Speed of Thought: Harnessing Parallel Decoding of Lexical Units for LLMs [57.27982780697922]
  大規模言語モデルは、自然言語の理解と生成において例外的な能力を示した。 しかし、それらの生成速度は、その復号過程の本質的にシーケンシャルな性質によって制限される。 本稿では,データ駆動方式で実装された新しいデコーディング手法であるLexical Unit Decodingを紹介する。
  論文  参考訳（メタデータ） (2024-05-24T04:35:13Z)
• The Ups and Downs of Large Language Model Inference with Vocabulary Trimming by Language Heuristics [74.99898531299148]
  本研究は,興味のある言語への埋め込みエントリを制限し,時間と記憶効率を高めることによる語彙トリミング(VT)について検討する。 Unicodeベースのスクリプトフィルタリングとコーパスベースの選択という2つの言語を異なる言語ファミリやサイズに適用する。 その結果、VTは小型モデルのメモリ使用量を50%近く削減し、生成速度が25%向上した。
  論文  参考訳（メタデータ） (2023-11-16T09:35:50Z)
• Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning [27.59524153097858]
  文法制約付き復号法(GCD)は、大言語モデル(LM)の生成を制御するために用いられる。 GCDは一般に構造化NLPタスクの統一フレームワークとして機能する。 文法制約付きLMは、制約なしLMよりも大幅に優れるか、タスク固有の微調整モデルよりも優れていることを示す。
  論文  参考訳（メタデータ） (2023-05-23T11:54:37Z)
• LEVER: Learning to Verify Language-to-Code Generation with Execution [64.36459105535]
  本稿では,プログラムの実行結果の検証を学習することで,言語からコードへの生成を改善するシンプルな手法であるLEVERを提案する。 具体的には、LLMからサンプリングされたプログラムが、自然言語入力、プログラム自体とその実行結果に基づいて正しいか否かを判定するために、検証者を訓練する。 LEVER はベースコード LLMs (4.6% から 10.9% まで) を継続的に改善し、それらすべてに対して新しい最先端の結果を得る。
  論文  参考訳（メタデータ） (2023-02-16T18:23:22Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。