論文の概要: Constraints Are Graphs, Not Chains: Exact Decoding for Diffusion Language Models

• arxiv url: http://arxiv.org/abs/2609.32900v1
• Date: Sat, 26 Sep 2026 19:40:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 12:08:25.523088
• Title: Constraints Are Graphs, Not Chains: Exact Decoding for Diffusion Language Models
• Title（参考訳）: 制約はグラフであり,チェーンではない - 拡散言語モデルのデコード
• Abstract要約: 拡散言語モデル(dLLM)は任意の順序でマスキング位置を予測するが、厳密な制約付きデコーダは制約を逐次言語としてエンコードする。 有限領域関係を因子グラフとして表現する学習自由デコーダであるFacterDLMを紹介する。
• 参考スコア（独自算出の注目度）: 3.449257598670055
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Diffusion language models (dLLMs) predict masked positions in arbitrary order, but their exact constrained decoders still encode constraints as sequential languages, whose state must track every unresolved dependency between positions. For relational constraints this encoding grows exponentially: for same-order copy, every finite automaton needs $4^k$ states, deterministic or nondeterministic, and every context-free grammar has size $2^{Ω(k)}$, while the factor graph of the same relation has size $O(k)$ and a 16-entry peak table. We introduce FactorDLM, a training-free decoder that represents finite-domain relations as a factor graph and, at each denoising step, conditions the model's mean-field prediction on that graph exactly by variable elimination. Decoding cost then grows exponentially with the induced width of the constraint graph, which replaces automaton size as the governing parameter. Because a finite automaton is a chain-shaped factor graph, one compiler enforces syntax and nonlocal relations together: on JSON records with cross-field references, a schema automaton alone leaves references dangling, relational factors alone produce malformed JSON, and the combined plan is valid on both counts, including on records of variable length. Across nine relational benchmarks and three backbones, every output satisfies every declared constraint at 0.4-6.9% projection overhead, where unconstrained decoding is 0-79% valid, and compiled projection answers repeated queries 13.6x faster than CP-SAT with eight parallel workers. Because model-free rules solve three of five standard benchmarks, we construct benchmarks with exact chance and fixed-template floors, on which selecting among exact constrained samples beats greedy projection. Which encoding is cheaper, sequential state or direct factors, depends on the constraint and is computable before decoding begins.
• Abstract（参考訳）: 拡散言語モデル(dLLM)は、任意の順序でマスクされた位置を予測するが、厳密な制約付きデコーダは依然として制約を逐次言語としてエンコードする。 同階複写の場合、すべての有限オートマトンには4^k$状態が必要であり、決定論的あるいは非決定論的であり、すべての文脈自由文法は2^{Ω(k)}$であり、同じ関係の因子グラフは$O(k)$と16エントロピーのピークテーブルを持つ。 有限領域関係を因子グラフとして表現する学習自由デコーダであるFacterDLMを導入する。 復号化コストは制約グラフの誘導された幅とともに指数関数的に増加し、オートマトンサイズを支配パラメータとして置き換える。 有限オートマトンはチェーン型の因子グラフであるため、ひとつのコンパイラは構文と非局所的な関係を一緒に強制する: クロスフィールド参照を持つJSONレコードでは、スキーマオートマトンだけが参照をダングリングに残し、リレーショナルファクタだけで不正なJSONを生成する。 9つのリレーショナルベンチマークと3つのバックボーンで、すべての出力は宣言された制約を0.4-6.9%のプロジェクションオーバーヘッドで満たしている。 モデルフリーなルールは5つの標準ベンチマークのうち3つを解くので、正確な確率と固定時間のフロアを持つベンチマークを構築します。 どの符号化が安価でシーケンシャルな状態か直接的な要因かは制約に依存し、復号開始前に計算可能である。

関連論文リスト

• Codebook Agent: Amortized Topology Design for LLM Multi-Agent Systems [67.04448659688579]
  クエリ非依存の16エントリのコードブックを開発し、上位のデコード候補を1回のバッチフォワードパスでランク付けする。 反復検索がなく、テスト時にメッセージパッシングがないため、Codebook Agentは6つのベンチマークでもっとも正確な方法である。
  論文  参考訳（メタデータ） (2026-09-02T08:10:22Z)
• Generating Workflow DAGs from Natural Language with Non-Reasoning LLMs [0.08537603362277842]
  ニューロシンボリックな分解により、より低コストで非合理的な大規模言語モデルにより複雑なワークフローDAGを生成することができることを示す。 本手法は,判定精度を24ポイント向上し,推論モデルのアウト・オブ・ザ・ボックス品質に対する統計的等価性を実現する。
  論文  参考訳（メタデータ） (2026-08-31T05:01:29Z)
• IndicQE-APE: A Benchmark for Quality Estimation and Automatic Post-Editing for Indic Languages [77.88427845181154]
  我々はWMT 2020-2024の共有タスクの系統を、英語のリソースを拡張してインディクシーに集約する:9つの方向対に対して126,754ドルのインスタンス。 セグメントレベルのQEでは,LSMが6つ,COMETが3つ,APEでは3つのシステムをベンチマークした。
  論文  参考訳（メタデータ） (2026-08-17T09:50:52Z)
• Spaghetti Architect: A Contamination-Resistant, By-Construction-Labelled, Multi-Language Code Dataset Generator [4.010371060637209]
  Spaghetti Architectはクリーンで言語に依存しない中間表現を、意図的に冗長で完全にフラットなプログラムにマップする。 各プログラムは、参照するオラクルに対してコンパイル、実行、チェックされるので、各インスタンスは、構成によって正しい。 4モデルオープンラグのレポートベースライン: 正確な一致はスケールとともに上昇し、本質的なノブは最強モデルの算術的集約精度をゼロに崩壊させる。
  論文  参考訳（メタデータ） (2026-07-21T02:23:22Z)
• Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata [57.27430779838529]
  有限オートマトンとして表現可能な任意の制約の下で,制約付き平均場後部からサンプリングする,正確かつトラクタブルなアルゴリズムを提案する。 このアプローチは、構築による制約満足度を保証し、欲求とサンプリングベースのデコーディングの両方をサポートし、並列およびブロックワイドデコーディングと互換性がある。 Dream-7B と LLaDA-8 の実証的な評価は、様々なタスクにおいてかなりの精度の向上を示した。
  論文  参考訳（メタデータ） (2026-07-08T05:48:57Z)
• Exact Regular-Constrained Variable-Order Markov Generation via Sparse Context-State Belief Propagation [0.0]
  我々は、一階マルコフ連鎖に対する信念の伝播を伴う規則的制約を扱うために、既存の正確な手法を拡張した。 可変順序拡張は、ジェネレータが可変順序/バックオフモデルであるときに既存のBP規則機械を走らせる必要がある状態空間を特定する。 固定化された文脈グラフとオートマトン推論は、順序において線型であり、一般には到達可能な積のエッジの数でスパースである。
  論文  参考訳（メタデータ） (2026-05-08T15:05:58Z)
• Programming over Thinking: Efficient and Robust Multi-Constraint Planning [54.77940831026738]
  SCOPEは、クエリ固有の推論をジェネリックコード実行から切り離すフレームワークである。 SCOPEは、コストとレイテンシを下げながら最先端のパフォーマンスを達成する。
  論文  参考訳（メタデータ） (2026-01-14T02:58:07Z)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  トークンの制約を評価するのは 違法にコストがかかる LCDは文字列上のグローバル分布を歪め、ローカル情報のみに基づいてトークンをサンプリングすることができる。 我々のアプローチは最先端のベースラインよりも優れていることを示す。
  論文  参考訳（メタデータ） (2025-04-07T18:30:18Z)

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

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