論文の概要: Attention Meets Reachability: Structural Equivalence and Efficiency in Grammar-Constrained LLM Decoding

• arxiv url: http://arxiv.org/abs/2603.05540v1
• Date: Wed, 04 Mar 2026 11:49:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-09 13:17:44.18023
• Title: Attention Meets Reachability: Structural Equivalence and Efficiency in Grammar-Constrained LLM Decoding
• Title（参考訳）: Atention Meets Reachability: Structure Equivalence and efficiency in Grammar-Constrained LLM Decoding (特集:情報通信)
• Authors: Faruk Alpay, Bilge Senturk,
• Abstract要約: 我々は、文脈自由文法(CFG)からコンパイルされたプッシュダウンシステム上での自己回帰的次トーケン分布と到達可能性との結合として文法制約デコーディング(GCD)を研究する。 文法の復号コスト等価クラスを定義し、有界書き直し科における最小SAC代表者の存在を証明した。
• 参考スコア（独自算出の注目度）: 0.2864713389096699
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study grammar-constrained decoding (GCD) as a coupling between an autoregressive next-token distribution and a reachability oracle over a pushdown system compiled from a context-free grammar (CFG). We prove an oracle invariance theorem: language-equivalent grammars induce identical admissible next-token sets for every prefix, hence identical logit masks, yet can yield provably different compiled state spaces and online ambiguity costs. We give exact control-state blowup counts for the canonical $a^n b^n$ language under redundant nonterminal delegation, and introduce a left-to-right structural ambiguity cost (SAC) measuring incremental packed-parse-forest growth per token. For two equivalent grammars over all finite strings, SAC is $O(1)$ per token under right-recursion but $Θ(t^2)$ per token and $Θ(n^3)$ cumulatively under concatenation. We establish engine-independent lower bounds: any sound, retrieval-efficient, parse-preserving online masking engine must incur $Ω(t^2)$ work per token on a specific constant-size CFG family, unconditionally within this model. We define decoding-cost equivalence classes of grammars and prove existence of minimal-SAC representatives within bounded rewrite families. Finally, we characterize the true conditional sampler via a Doob $h$-transform and derive sharp one-step KL and total-variation distortion bounds for hard-masked decoding in terms of survival-probability spread among admissible next tokens. We integrate these results with Transformer and Mixture-of-Experts architectures, derive latency envelopes in terms of vocabulary size, active state sets, and beam width, and connect SAC to instrumentation-based predictive performance models and automated grammar optimization.
• Abstract（参考訳）: 本研究では、文脈自由文法(CFG)からコンパイルされたプッシュダウンシステム上で、自己回帰的次トーケン分布と到達性オラクルとの結合として文法制約デコーディング(GCD)について検討する。 言語等価文法はすべての接頭辞に対して同一の許容可能な次トーケン集合を誘導し、したがって同一のロジットマスクを誘導するが、証明可能な異なるコンパイルされた状態空間とオンライン曖昧性コストが得られる。 余剰な非終端デリゲートの下での標準の$a^n b^n$言語に対して正確な制御状態の爆発数を与え,トークンごとの増減を計測する左右構造的曖昧性コスト(SAC)を導入する。 すべての有限文字列上の2つの等価文法に対して、SACは右再帰の下ではトークン当たり$O(1)$だが、トークン当たり$(t^2)$と$(n^3)$は連結で累積的に$O(1)$である。 任意の音, 検索効率, パース保存型オンラインマスキングエンジンは, 特定の定数サイズのCFGファミリー上のトークン当たり$Ω(t^2)$の処理を, このモデルでは無条件で行う必要がある。 文法の復号コスト等価クラスを定義し、有界書き直し科における最小SAC代表者の存在を証明した。 最後に、Doob $h$-transform を用いて真の条件付きサンプルを特徴付けるとともに、許容可能な次のトークン間での生存確率の広がりの観点から、シャープな1ステップKLおよび全変分歪み境界を導出する。 これらの結果をTransformerとMixture-of-Expertsアーキテクチャと統合し、語彙サイズ、アクティブ状態セット、ビーム幅の遅延エンベロープを導出し、SACをインスツルメンテーションベースの予測性能モデルと自動文法最適化に接続する。

関連論文リスト

• Adaptation to Intrinsic Dependence in Diffusion Language Models [5.185131234265025]
  拡散言語モデル(DLM)は自己回帰(AR)アプローチに代わる有望な代替手段として登場した。 対象データ分布の(未知の)依存構造に適応するDLMの分布に依存しないアンマスキングスケジュールを提案する。 この結果は, 先行収束理論を著しく改善し, 低複雑さ分布に対する相当なサンプリング加速を得た。
  論文  参考訳（メタデータ） (2026-02-23T18:41:34Z)
• Dynamic Large Concept Models: Latent Reasoning in an Adaptive Semantic Space [56.37266873329401]
  大規模言語モデル (LLM) は、高度に一様でない情報密度を示す言語にもかかわらず、全てのトークンに一様計算を適用する。 我々は,潜在表現から意味境界を学習し,トークンから推論がより効率的である圧縮概念空間へ移行する階層型言語モデリングフレームワークである$textbfDynamic Large Concept Models (DLCM)$を提案する。
  論文  参考訳（メタデータ） (2025-12-31T04:19:33Z)
• Low-Complexity Semantic Packet Aggregation for Token Communication via Lookahead Search [32.63323958382152]
  本稿では,トークンのパケット化に着目し,平均トークン類似度(ATS)を最大化する。 これを解決するために,ルックアヘッド検索(SemPA-Look)を用いたセマンティックアグリゲーションの新しいフレームワークを提案する。 SemPA-Lookは、リプレースせずにパケット内のトークン候補をサンプリングするルックアヘッド検索インスパイアされたアルゴリズムを適用している。
  論文  参考訳（メタデータ） (2025-06-24T09:25:44Z)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  トークンの制約を評価するのは 違法にコストがかかる LCDは文字列上のグローバル分布を歪め、ローカル情報のみに基づいてトークンをサンプリングすることができる。 我々のアプローチは最先端のベースラインよりも優れていることを示す。
  論文  参考訳（メタデータ） (2025-04-07T18:30:18Z)
• $\texttt{SEM-CTRL}$: Semantically Controlled Decoding [53.86639808659575]
  $texttSEM-CTRL$は、LLMデコーダに直接、リッチなコンテキスト依存制約とタスクおよびインスタンス固有のセマンティクスを強制する統一的なアプローチである。 texttSEM-CTRL$は、小さな訓練済みのLLMがより大きな変種や最先端の推論モデルよりも効率的に性能を向上することを可能にする。
  論文  参考訳（メタデータ） (2025-03-03T18:33:46Z)
• A Partition Cover Approach to Tokenization [24.595558878756787]
  トークン化とは、文字列を一定の語彙サイズのトークンに符号化するプロセスである。 Byte-Pair corpora (BPE) は、トークン化問題を圧縮問題として定式化し、マージのシーケンスを実行することでそれに取り組む。 GreedTokは圧縮においてBPEやUnigramよりも優れており、GreedWMCに匹敵するカバースコアが得られることを示す。
  論文  参考訳（メタデータ） (2025-01-08T17:07:07Z)
• Tokenization as Finite-State Transduction [24.19959327497118]
  正規言語の全てのトークン化を効率的にエンコードできる有限状態フレームワークを導入する。 そのByte-Pairを示します。 Match(BPE)とMaxPiece(WordPiece)がこのフレームワークに適合する。 これの応用は、あるパターンにマッチするように言語モデルの出力を制約するガイド付き生成である。
  論文  参考訳（メタデータ） (2024-10-21T07:10:07Z)
• Exact Byte-Level Probabilities from Tokenized Language Models for FIM-Tasks and Model Ensembles [23.134664392314264]
  トークン化は、言語モデル(LM)における多くの未理解の欠点と関連している。 本研究は, トークン化がモデルとバイトレベルのモデルを比較し比較することによって, モデル性能に与える影響について検討する。 本稿では,学習トークン分布と等価バイトレベル分布とのマッピングを確立するフレームワークであるByte-Token Representation Lemmaを紹介する。
  論文  参考訳（メタデータ） (2024-10-11T23:30:42Z)

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

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