論文の概要: Characterizing Local Breadth in Language Generation
- arxiv url: http://arxiv.org/abs/2611.14887v1
- Date: Wed, 11 Nov 2026 01:26:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:32.973603
- Title: Characterizing Local Breadth in Language Generation
- Title(参考訳): 言語生成におけるローカルブレッドスの特徴付け
- Abstract要約: Kleinberg-Mullainathanモデルにおける未知の対象の正の例から生成する。
ブレッドスオブジェクティブはバナッハ密度を低くすることで測定され、任意の大きさのスパースホールを除外する。
- 参考スコア(独自算出の注目度): 1.6203023551115867
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Large language models sharpen the validity--breadth trade-off: a generator should avoid hallucinations without collapsing onto a narrow set of valid outputs. We study generation from positive examples of an unknown target in the Kleinberg--Mullainathan model, with arbitrary, possibly adversarial order and no distributional or computational assumptions. Breadth is measured by lower Banach density, which rules out arbitrarily large sparse holes, unlike prefix-based lower asymptotic density. 1. Exact optima in one dimension: For each target $K$ in a countable family, we characterize its optimal lower Banach density $b(K)$ via equivalent combinatorial and topological formulations. One eventually valid generator attains all $b(K)$ simultaneously. Every $α\in[0,1/2]$ occurs as $b(K)$ in some countable family; finite Cantor--Bendixson point rank guarantees $b(K)=1/2$, even without a uniform rank bound. 2. Unavoidable trade-offs in higher dimensions: For $d\ge2$, there need not be a single best generator: optimizing density for one target may worsen the guarantee for another. An explicit family quantifies this intrinsically multi-objective trade-off. 3. Complete characterization of density profiles: We characterize the full region of simultaneously achievable guarantees, with equivalent combinatorial and topological formulations, after excluding geometrically degenerate rectangles. Every prescribed product $\prod_i[0,α_i]$, $α_i\in[0,1/2]$ can occur as an exact achievable region for some language collection. 4. Near-half guarantees and the sharp endpoint: Under a near-logarithmic nondegeneracy condition, one generator achieves filtered density at least $1/2-\varepsilon$ at all finite-point-rank targets, for every $\varepsilon>0$, improving the previous polylogarithmic threshold. The exact $1/2$ endpoint can fail even for a rank-zero singleton family.
- Abstract(参考訳): ジェネレータは、有効な出力の狭いセットに衝突することなく幻覚を避けるべきです。
我々は、Kleinberg--Mullainathanモデルにおける未知の対象の正の例から生成する。
ブレッドスは、プレフィックスベースの低漸近密度とは異なり、任意の大きさのスパースホールを規制するバナッハ密度によって測定される。
1. 1次元の厳密な最適性:可算族の各対象$K$に対して、同値な組合せおよび位相的定式化により、最適なバナッハ密度$b(K)$を特徴付ける。
最終的に有効なジェネレータは、すべての$b(K)$を同時に達成する。
すべての$α\in[0,1/2]$は、ある可算族において$b(K)$として生じる。
2. 高次元における避けられないトレードオフ:$d\ge2$の場合、1つの最高のジェネレータは必要ない。
明示的な族は、本質的な多目的トレードオフを定量化する。
密度プロファイルの完全な特徴付け: 幾何的に退化した矩形を除いた後、同値な組合せおよび位相的定式化を同時に達成可能な保証の完全な領域を特徴付ける。
すべての所定の積 $\prod_i[0,α_i]$, $α_i\in[0,1/2]$ は、ある言語コレクションの正確な達成可能な領域として発生する。
4. ほぼ半減期保証と鋭い終点: ほぼ対数的非退化条件の下で、1つの発生器は、全ての有限点ランクの目標に対して、少なくとも1/2-\varepsilon$のフィルタ密度を達成し、以前の多対数しきい値を改善する。
正確に1/2$のエンドポイントは、ランクゼロのシングルトンファミリーでもフェールすることができる。
関連論文リスト
- Exact Minimax One-Bit Unbiased Compression: Heavy-Tail Necessity and Finite-Randomness Approximation [7.764443932311498]
ポイントワイズな1ビット圧縮機は、1ビットを送信しながら期待する全ての実際の入力を再構成する。
我々は、$mathbb R$でバイアスのないすべての公開コイン1ビット符号に対して、ソース平均再構成の2番目のモーメントが$m2+mathcal J(P)2$であることを証明する。
論文 参考訳(メタデータ) (2026-08-20T07:29:09Z) - The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。
我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
論文 参考訳(メタデータ) (2026-08-03T17:57:01Z) - Dense Language Generation Made Simple: Deterministic, Randomized, and Multi-Order Algorithms [6.204831354195728]
限界における言語生成は、肯定的な例のストリームから、ジェネレータが新しい有効な文字列を生成する方法を学ぶための理論的フレームワークである。
このモデルでは、敵は可算族から未知の言語を選択し、その要素を任意の順序で列挙する。
信頼性生成は、観測データに対する妥当性と新規性という2つの最終的な保証によって形式化される。
論文 参考訳(メタデータ) (2026-08-02T15:41:31Z) - Sharp Optimal Algorithm for Derivative-Free Stochastic Convex Optimization in One Dimension [80.40589035328607]
我々は、ガウス雑音の零次オラクルを用いて凸関数 $f : [0,1] から [0,1] への最小化の問題を研究する。
計算効率のよいO(1/sqrtT)$収束率を求めるアルゴリズムを提案する。
論文 参考訳(メタデータ) (2026-07-14T16:10:33Z) - Intrinsic Wasserstein Rates for Score-Based Generative Models on Smooth Manifolds [61.14405512940818]
Scoreベースの生成モデルは高次元空間で訓練されていることを示す。
有限固有アンカーとガウス・ニュートンによる最も近い射影座標のReLU実装を用いる。
論文 参考訳(メタデータ) (2026-05-15T10:20:05Z) - Ratio Covers of Convex Sets and Optimal Mixture Density Estimation [16.547739992791197]
Kullback-Leibler分散系の密度推定について検討する。
我々は,辞書サイズ,サンプルサイズ,信頼度の観点から,可能な限りの高確率保証を同定する。
論文 参考訳(メタデータ) (2026-02-18T02:25:18Z) - Power Homotopy for Zeroth-Order Non-Convex Optimizations [5.737648067191245]
GS-Powerは非次元最適化問題に対する新しいゼロ階法である。
競合するアルゴリズムの上位3位に一貫してランクインしている。
ImageNetの画像に対するブラックボックス攻撃で、少なくとも1位を獲得した。
論文 参考訳(メタデータ) (2025-11-17T16:54:30Z) - Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations [1.6203023551115867]
敵が未知の言語から文字列を列挙する極限における言語生成の枠組みについて検討する。
C$が$K$でより低い密度$alpha$を持つなら、アルゴリズムの出力は少なくとも$alpha/2$を達成する。
M_t$を仮定すると、最終的に$Cサブセットeq Mサブセットeq K$が満たされる。
論文 参考訳(メタデータ) (2025-11-07T14:56:04Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳(メタデータ) (2022-08-19T18:00:34Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。