論文の概要: Constrained Adaptive Rejection Sampling

• arxiv url: http://arxiv.org/abs/2510.01902v1
• Date: Thu, 02 Oct 2025 11:17:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-03 16:59:21.100347
• Title: Constrained Adaptive Rejection Sampling
• Title（参考訳）: 制約付き適応型リジェクションサンプリング
• Authors: Paweł Parys, Sairam Vaidya, Taylor Berg-Kirkpatrick, Loris D'Antoni,
• Abstract要約: 言語モデル(LM)は、生成した出力が厳密な意味的制約や構文的制約を満たす必要があるアプリケーションでますます使われている。 既存の制約付き生成へのアプローチは、スペクトルに沿って低下する: 欲求的制約付き復号法は、復号時の有効性を強制するが、LMの分布を歪ませる。 本稿では、分布歪みを伴わないRSの試料効率を厳密に改善するアプローチである、適応型サンプリング(CARS)を提案する。
• 参考スコア（独自算出の注目度）: 27.579645342312674
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Language Models (LMs) are increasingly used in applications where generated outputs must satisfy strict semantic or syntactic constraints. Existing approaches to constrained generation fall along a spectrum: greedy constrained decoding methods enforce validity during decoding but distort the LM's distribution, while rejection sampling (RS) preserves fidelity but wastes computation by discarding invalid outputs. Both extremes are problematic in domains such as program fuzzing, where both validity and diversity of samples are essential. We present Constrained Adaptive Rejection Sampling (CARS), an approach that strictly improves the sample-efficiency of RS without distributional distortion. CARS begins with unconstrained LM sampling and adaptively rules out constraint-violating continuations by recording them in a trie and subtracting their probability mass from future draws. This adaptive pruning ensures that prefixes proven invalid are never revisited, acceptance rates improve monotonically, and the resulting samples exactly follow the constrained distribution. In experiments on a variety of domains -- e.g., program fuzzing and molecular generation -- CARS consistently achieves higher efficiency -- measured in the number of LM forward passes per valid sample -- while also producing stronger sample diversity than both GCD and methods that approximate the LM's distribution.
• Abstract（参考訳）: 言語モデル(LM)は、生成した出力が厳密な意味的制約や構文的制約を満たす必要があるアプリケーションでますます使われている。 reedy 制約付き復号法は復号時に有効性を強制するが、LMの分布を歪ませる一方、Rejection sample (RS) は不確定な出力を破棄して計算を無駄にする。 プログラムファジィング(英語版)のような、サンプルの妥当性と多様性の両方が不可欠である領域では、両極端が問題となる。 本稿では、分布歪みを伴わないRSの試料効率を厳密に改善するアプローチである、適応型サンプリング(CARS)を提案する。 CARSは制約のないLMサンプリングから始まり、トリエに記録し、将来のドローから確率質量を減じることで制約違反継続を適応的に規制する。 この適応的なプルーニングにより、証明された接頭辞は再検討されず、受容率は単調に改善され、結果として得られたサンプルは制約された分布に正確に従うことが保証される。 プログラムファジィングや分子生成など、さまざまな領域の実験において、CARSは、有効サンプル当たりのLMフォワードパス数で測定された高い効率を達成すると同時に、GCDやLMの分布を近似する手法よりも強力なサンプル多様性を生み出す。

関連論文リスト

• Chance-constrained Flow Matching for High-Fidelity Constraint-aware Generation [46.932479632530764]
  Chance-Constrained Flow Matchingは、最適化をサンプリングプロセスに統合し、ハード制約の効果的な適用を可能にする。 実験により、CCFMは複雑な物理系のモデリングにおいて、現在の最先端の制約付き生成モデルよりも優れていることが示された。
  論文  参考訳（メタデータ） (2025-09-29T17:56:52Z)
• Flipping Against All Odds: Reducing LLM Coin Flip Bias via Verbalized Rejection Sampling [59.133428586090226]
  大規模言語モデル(LLM)は、しばしば自然言語を用いて確率分布を正確に記述することができる。 このミスマッチはモンテカルロ法、エージェントベースのシミュレーション、ランダム化された意思決定などの信頼性を必要とするタスクでの使用を制限する。 本稿では,古典的リジェクションサンプリングの自然言語適応であるVerbalized Rejection Smpling (VRS)を紹介する。
  論文  参考訳（メタデータ） (2025-06-11T17:59:58Z)
• Towards Optimal Multi-draft Speculative Decoding [102.67837141152232]
  MDSD(Multi-Draft Speculative Decoding)は、各トークンを生成する際に、小さなドラフトモデルで複数のドラフトを生成する手法である。 本稿では、最適輸送問題の双対性について論じ、最適受容率を効率的に計算する方法を提供する。
  論文  参考訳（メタデータ） (2025-02-26T03:22:44Z)
• Contrastive CFG: Improving CFG in Diffusion Models by Contrasting Positive and Negative Concepts [55.298031232672734]
  As-Free Guidance (CFG) は条件拡散モデルサンプリングに有効であることが証明された。 対照的な損失を用いた負のCFG誘導を強化する新しい手法を提案する。
  論文  参考訳（メタデータ） (2024-11-26T03:29:27Z)
• REAL Sampling: Boosting Factuality and Diversity of Open-Ended Generation via Asymptotic Entropy [93.8400683020273]
  大規模言語モデル(LLM)の復号法は通常、事実性の確保と多様性の維持のトレードオフに苦慮する。 核サンプリングにおける事実性および多様性を向上させる復号法であるREALサンプリングを提案する。
  論文  参考訳（メタデータ） (2024-06-11T21:44:49Z)
• Amortizing intractable inference in large language models [56.92471123778389]
  難治性後部分布のサンプルとして, 償却ベイズ推定を用いる。 我々は,LLMファインチューニングの分散マッチングパラダイムが,最大習熟の代替となることを実証的に実証した。 重要な応用として、チェーン・オブ・ソート推論を潜在変数モデリング問題として解釈する。
  論文  参考訳（メタデータ） (2023-10-06T16:36:08Z)
• Conditional Sampling of Variational Autoencoders via Iterated Approximate Ancestral Sampling [7.357511266926065]
  変分オートエンコーダ(VAE)の条件付きサンプリングは、データ計算の欠如など、様々なアプリケーションで必要とされるが、計算上は難解である。 基本的条件付きサンプリングはMetropolis-within-Gibbs (MWG)である
  論文  参考訳（メタデータ） (2023-08-17T16:08:18Z)
• Selectively increasing the diversity of GAN-generated samples [8.980453507536017]
  本稿では,GAN生成サンプルの多様性を選択的に向上する手法を提案する。 本研究では,CERN における ALICE 実験のZero Degree Calorimeter から得られたデータをシミュレーションする実生活シナリオとともに,本手法の優位性を示す。
  論文  参考訳（メタデータ） (2022-07-04T16:27:06Z)

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

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