論文の概要: Dense Language Generation Made Simple: Deterministic, Randomized, and Multi-Order Algorithms
- arxiv url: http://arxiv.org/abs/2608.01320v1
- Date: Sun, 02 Aug 2026 15:41:31 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-04 15:07:25.16356
- Title: Dense Language Generation Made Simple: Deterministic, Randomized, and Multi-Order Algorithms
- Title（参考訳）: Dense Language Generation made Simple: Deterministic, Randomized, Multi-Order Algorithms
- Abstract要約: 限界における言語生成は、肯定的な例のストリームから、ジェネレータが新しい有効な文字列を生成する方法を学ぶための理論的フレームワークである。
このモデルでは、敵は可算族から未知の言語を選択し、その要素を任意の順序で列挙する。
信頼性生成は、観測データに対する妥当性と新規性という2つの最終的な保証によって形式化される。
- 参考スコア（独自算出の注目度）: 6.204831354195728
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Language generation in the limit is a theoretical framework for studying how a generator can learn to produce new valid strings from a stream of positive examples. In this model, an adversary chooses an unknown language from a countable family and enumerates its elements in an arbitrary order, while the generator must eventually output only elements of the language that have not yet appeared in the enumeration. Reliable generation is thus formalized through two eventual guarantees: validity and novelty relative to the observed data. To further quantify the breadth of the generator's outputs, Kleinberg and Wei (FOCS 2025, STOC 2026) introduced lower density as a measure of output coverage. Given an order representing the importance or relevance of possible outputs, lower density is the asymptotic lower bound, as $n$ grows, on the fraction of the first $n$ elements of the target language that the generator outputs before they appear in the data. Kleinberg and Wei showed that $1/2$ is the optimal lower-density guarantee for deterministic algorithms. We develop a simple and unified framework for obtaining optimal lower-density guarantees. We first give a deterministic algorithm that recovers the optimal guarantee of $1/2$ with a significantly simpler analysis than prior work. We then demonstrate the flexibility of our framework through two extensions. First, against an oblivious adversary, randomization raises the optimal guarantee to $1-1/e$. Second, for any finite collection of orders, the optimal deterministic and randomized guarantees can be achieved simultaneously with respect to every order, so accommodating multiple notions of importance or relevance entails no loss in the optimal guarantee.
- Abstract（参考訳）: 限界における言語生成は、肯定的な例のストリームから、ジェネレータが新しい有効な文字列を生成する方法を学ぶための理論的フレームワークである。
このモデルでは、敵は可算族から未知の言語を選択し、その要素を任意の順序で列挙する。
これにより、信頼性生成は、観測データに対する妥当性と新規性という、2つの最終的な保証によって形式化される。
さらに出力の幅を定量化するため、Kleinberg と Wei (FOCS 2025, STOC 2026) は出力カバレッジの尺度として低密度を導入した。
可能な出力の重要性や関連性を表す順序が与えられた場合、低密度は、データに現れる前に生成者が出力するターゲット言語の最初の$n$要素の分数である$n$が増加するにつれて、漸近的な下界となる。
Kleinberg と Wei は 1/2$ が決定論的アルゴリズムの最適低密度保証であることを示した。
我々は、最適な低密度保証を得るために、シンプルで統一されたフレームワークを開発する。
まず、決定論的アルゴリズムを用いて、1/2$の最適保証を、従来よりもはるかに単純な分析で回収する。
次に、2つの拡張を通じてフレームワークの柔軟性を示します。
まず、難解な敵に対して、ランダム化は最適な保証を1-1/e$に上げる。
第二に、任意の有限個の順序の集合に対して、最適決定論的かつランダム化された保証は、すべての順序に関して同時に達成できるので、重要性や関連性の複数の概念を調節することは、最適保証の損失を伴わない。
関連論文リスト
- Mistake-Bounded Language Generation [6.034531760235531]
言語生成の限界における学習課題について検討する。
我々は、伝統的なラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・ラスト・
我々のフレームワークは、ノイズの多い敵に適応できるように拡張可能であることを示す。
論文 参考訳（メタデータ） (2026-05-11T16:32:01Z) - Speculative Decoding Speed-of-Light: Optimal Lower Bounds via Branching Random Walks [39.54576236079211]
投機生成は、大規模言語モデルにおける推論を加速する有望な手法として登場した。
本研究では,任意の決定論的投機生成アルゴリズムのランタイム上での最初のタイトな下限を確立する。
論文 参考訳（メタデータ） (2025-12-12T16:54:33Z) - Pareto-optimal Non-uniform Language Generation [11.279808969568252]
ある言語に対する生成時間$L$が$tstar(L)$より厳密に小さいアルゴリズムは、他の言語に対する生成時間$L’$が$tstar(L')$より厳密に悪いことを満たさなければならない。
提案手法は,非一様生成アルゴリズムを,雑音や代表生成といった現実的に動機付けられた設定に適応させるのに便利である。
論文 参考訳（メタデータ） (2025-10-03T08:08:20Z) - Online Fair Division for Personalized $2$-Value Instances [51.278096593080456]
オンラインフェアディビジョン(オンラインフェアディビジョン)では,商品が一度に1つずつ到着し,定額のエージェントが配置されている。
善が現れると、各エージェントの持つ値が明らかになり、エージェントの1つに即時かつ不可逆的に割り当てられなければならない。
我々は、よく知られた公平性の概念に関して、最悪の場合の保証を得る方法を示す。
論文 参考訳（メタデータ） (2025-05-28T09:48:16Z) - On Characterizations for Language Generation: Interplay of Hallucinations, Breadth, and Stability [16.30681257128492]
[KM24] は、その極限における任意の可算言語コレクションから生成するアルゴリズムである。
近年の研究では、広さの異なる概念を導入し、広さの世代が可能であるかを探求している。
以上の結果から,安定性が要求される場合には,多くの既存概念による生成が等しく困難になることが示唆された。
論文 参考訳（メタデータ） (2024-12-24T16:24:43Z) - Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。
1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
論文 参考訳（メタデータ） (2024-11-29T05:29:47Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - SpecTr: Fast Speculative Decoding via Optimal Transport [30.18181671899423]
このアルゴリズムはデコーディングの高速化を図り、デコードされた出力に品質劣化がないことを保証します。
提案手法は,最先端の大規模言語モデルに対して,標準的なベンチマーク上での投機的復号化よりもさらに1.37倍の高速化である2.13Xのウォールクロック高速化を実現することを実験的に実証した。
論文 参考訳（メタデータ） (2023-10-23T17:47:34Z) - Best-$k$ Search Algorithm for Neural Text Generation [118.02691398555781]
本稿では,品質と多様性のバランスをとる決定論的探索アルゴリズムを提案する。
提案アルゴリズムはパラメータフリーで、軽量で、効率的で、使いやすくなっている。
論文 参考訳（メタデータ） (2022-11-22T00:26:13Z) - A Non-monotonic Self-terminating Language Model [62.93465126911921]
本稿では,不完全復号アルゴリズムによる非終端列の問題に焦点をあてる。
まず、グリーディ探索、トップ$kのサンプリング、核サンプリングを含む不完全確率復号アルゴリズムを定義する。
次に,単調な終端確率の制約を緩和する非単調な自己終端言語モデルを提案する。
論文 参考訳（メタデータ） (2022-10-03T00:28:44Z) - Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy
Amplification by Shuffling [49.43288037509783]
ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。
私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
論文 参考訳（メタデータ） (2020-12-23T17:07:26Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。