論文の概要: Provably Tractable NFA-Constrained Language Generation via HMMs

• arxiv url: http://arxiv.org/abs/2609.40185v2
• Date: Tue, 06 Oct 2026 03:29:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 02:58:29.245792
• Title: Provably Tractable NFA-Constrained Language Generation via HMMs
• Title（参考訳）: HMMによる潜在的にトラクタブルなNFA制約言語生成
• Abstract要約: 非決定論的有限オートマトンに対する既存の制約付き生成技術は、分布や犠牲効率を歪ませる。 軽度の仮定で理論的保証を得たNFA制約生成のための非拘束時間エンジンであるNFA-LMを提案する。 実験により,NFA-LMは理論的に有界な近似誤差を持つ高品質な出力を効率よく生成することが示された。
• 参考スコア（独自算出の注目度）: 2.2574964618006663
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Constrained generation aims to sample from language models (LMs) conditioned on hard constraints. Existing constrained-generation techniques for nondeterministic finite automaton (NFA) constraints either distort the distribution or sacrifice efficiency. Theoretically, this task reduces to counting the length-$n$ sequences accepted by an NFA (#NFA), and the exact #NFA problem is #P-complete. Recent work has shown that #NFA admits a fully polynomial randomized approximation scheme (FPRAS). Inspired by this result, we propose NFA-LM, a polynomial-time engine for NFA-constrained generation with theoretical guarantees under mild assumptions. Experiments show that NFA-LM efficiently generates high-quality outputs with theoretically bounded approximation error.
• Abstract（参考訳）: 制約付き生成は、厳密な制約を条件とした言語モデル(LM)からサンプリングすることを目的としている。 非決定論的有限オートマトン(NFA)制約に対する既存の制約付き生成技術は、分布を歪ませるか、犠牲効率を犠牲にする。 理論的には、このタスクはNFA(#NFA)によって受け入れられる長さ$n$のシーケンスを数えることに還元され、正確な#NFA問題は#P完全である。 最近の研究は、#NFAが完全多項式ランダム化近似スキーム(FPRAS)を受け入れていることを示している。 この結果にインスパイアされたNFA-LMは,理論的保証付きNFA制約生成のための多項式時間エンジンである。 実験により,NFA-LMは理論的に有界な近似誤差を持つ高品質な出力を効率よく生成することが示された。

関連論文リスト

• Uncertainty Quantification for LLM-based Code Generation [18.240828221520257]
  コード生成のためのリスク制御予測を構築するために,複数の仮説テストを利用するRisCoSetを提案する。 同程度のリスクで,コード削除を最大24.5%削減することができる。
  論文  参考訳（メタデータ） (2026-05-12T14:40:29Z)
• Efficient Large Language Model Inference with Neural Block Linearization [51.619870789584525]
  本稿では,トランスフォーマーモデル推論を高速化する新しいフレームワークであるNeural Block Linearization (NBL)を紹介する。 NBLは、線形最小平均正方形誤差推定器から導かれる線形近似で自己アテンション層を置き換える。 実験では、NBLは競争精度を維持しながら、顕著な計算スピードアップを達成する。
  論文  参考訳（メタデータ） (2025-05-27T12:01:43Z)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  トークンの制約を評価するのは 違法にコストがかかる LCDは文字列上のグローバル分布を歪め、ローカル情報のみに基づいてトークンをサンプリングすることができる。 我々のアプローチは最先端のベースラインよりも優れていることを示す。
  論文  参考訳（メタデータ） (2025-04-07T18:30:18Z)
• Compilation and Fast Model Counting beyond CNF [31.620928650659586]
  本稿では,関数のクラスを効率的にd-DNNFに変換するか,あるいはコンパイルするかに関する理論的知識を強化する。 問題の制約は、すべての変数順序付けに対して、定数幅順序付きバイナリ決定図(OBDD)で表現可能なすべての関数である。 制約のサブファミリーに適用し,コンパイルを必要としないモデルカウントのためのより効率的なFPTアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-02-01T14:00:04Z)
• A Term-based Approach for Generating Finite Automata from Interaction Diagrams [0.4199844472131921]
  非決定論的有限オートマタは正規言語を表現し、単語認識などの応用に対する魅力を高めている。 本稿では,シーケンス図やメッセージシーケンスチャートなどの対話言語からNFAを生成するための新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-06-05T15:53:42Z)
• Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits [85.27420062094086]
  Implicitly Normalized Forecaster (INF) は、敵対的マルチアームバンディット(MAB)問題に対する最適解であると考えられている。 重み付き設定のMAB問題に対するクリッピング(INFclip)を用いたINFの新バージョン"Implicitly Normalized Forecaster"を提案する。 INFclipは線形重み付きMAB問題に対して最適であり、非線形問題に対して有効であることを示す。
  論文  参考訳（メタデータ） (2023-05-11T12:00:43Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)

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

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