論文の概要: A Mathematical Theory of Top-$k$ Sparse Attention via Total Variation Distance

• arxiv url: http://arxiv.org/abs/2512.07647v1
• Date: Mon, 08 Dec 2025 15:36:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-09 22:03:54.945728
• Title: A Mathematical Theory of Top-$k$ Sparse Attention via Total Variation Distance
• Title（参考訳）: 総変分距離によるトップ$k$スパース注意の数学的理論
• Authors: Georgios Tzachristas, Lei Deng, Ioannis Tzachristas, Gong Zhang, Renhai Chen,
• Abstract要約: 我々は,分散レベルと出力レベルの両方でエラーを定量化する,Top-$$ attention truncationという統一フレームワークを開発した。 総偏差距離は捨てられたソフトマックスのテール質量と一致し,$mathrmTV(P,hat P)=1-e-mathrmTV(P,hat P)=1-e-mathrmTV(P,hat P)$を満たすことを示す。
• 参考スコア（独自算出の注目度）: 7.014801584517052
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We develop a unified mathematical framework for certified Top-$k$ attention truncation that quantifies approximation error at both the distribution and output levels. For a single attention distribution $P$ and its Top-$k$ truncation $\hat P$, we show that the total-variation distance coincides with the discarded softmax tail mass and satisfies $\mathrm{TV}(P,\hat P)=1-e^{-\mathrm{KL}(\hat P\Vert P)}$, yielding sharp Top-$k$-specific bounds in place of generic inequalities. From this we derive non-asymptotic deterministic bounds -- from a single boundary gap through multi-gap and blockwise variants -- that control $\mathrm{TV}(P,\hat P)$ using only the ordered logits. Using an exact head-tail decomposition, we prove that the output error factorizes as $\|\mathrm{Attn}(q,K,V)-\mathrm{Attn}_k(q,K,V)\|_2=τ\|μ_{\mathrm{tail}}-μ_{\mathrm{head}}\|_2$ with $τ=\mathrm{TV}(P,\hat P)$, yielding a new head-tail diameter bound $\|\mathrm{Attn}(q,K,V)-\mathrm{Attn}_k(q,K,V)\|_2\leτ\,\mathrm{diam}_{H,T}$ and refinements linking the error to $\mathrm{Var}_P(V)$. Under an i.i.d. Gaussian score model $s_i\sim\mathcal N(μ,σ^2)$ we derive closed-form tail masses and an asymptotic rule for the minimal $k_\varepsilon$ ensuring $\mathrm{TV}(P,\hat P)\le\varepsilon$, namely $k_\varepsilon/n\approxΦ_c(σ+Φ^{-1}(\varepsilon))$. Experiments on bert-base-uncased and synthetic logits confirm the predicted scaling of $k_\varepsilon/n$ and show that certified Top-$k$ can reduce scored keys by 2-4$\times$ on average while meeting the prescribed total-variation budget.
• Abstract（参考訳）: 我々は、分布レベルと出力レベルの両方で近似誤差を定量化する、Top-$$ attention truncationの統一的な数学的フレームワークを開発する。 単一の注意分布に対して、$P$とそのTop-$k$ truncation$\hat P$に対して、全変分距離は捨てられたソフトマックスの尾の質量と一致し、$\mathrm{TV}(P,\hat P)=1-e^{-\mathrm{KL}(\hat P\Vert P)}$を満たすことを示す。 このことから、非漸近的決定論的境界 (non-asymptotic deterministic bounds) を、単一境界ギャップからマルチギャップおよびブロックワイド変種 (multi-gap and blockwise variants) を導出し、順序付きロジットのみを使用して$\mathrm{TV}(P,\hat P)$を制御する。 正確なヘッドテール分解を用いて、出力誤差は$\|\mathrm{Attn}(q,K,V)-\mathrm{Attn}_k(q,K,V)-\mathrm{Attn}_k(q,K,V)\|_2=τ\|μ_{\mathrm{tail}}-μ_{\mathrm{head}}\|_2$ with $τ=\mathrm{TV}(P,\hat P)$として分解され、新しいヘッドテール直径が$\|\mathrm{Attn}(q,K,V)-\mathrm{Attn}_k(q,K,V)\|_2\leτ,\mathrm{diam}_{H}$T} となる。 i.d.d. ガウスのスコアモデル $s_i\sim\mathcal N(μ,σ^2)$ では、最小の$k_\varepsilon$ が$\mathrm{TV}(P,\hat P)\le\varepsilon$、すなわち $k_\varepsilon/n\approx\_c(σ+\^{-1}(\varepsilon))$ に対して閉形式尾質量と漸近規則を導出する。 bert-base-uncasedおよびsynthetic logitsの実験は、予測スケーリングが$k_\varepsilon/n$であることを確認し、認定されたTop-$k$が、所定の全変量予算を満たしながら平均2-4$\times$を削減可能であることを示す。

関連論文リスト

• $\mathsf{P} \neq \mathsf{NP}$: A Non-Relativizing Proof via Quantale Weakness and Geometric Complexity [0.0]
  We work in the weak Quantale $w_Q=K_mathrmpoly(cdotmidcdot)$. ランダムな3ドルCNFをマスキングした効率よくサンプリング可能なアンサンブル$D_m$に対して、スイッチング・バイ・ウェイクネスの正規形式を証明する。
  論文  参考訳（メタデータ） (2025-10-09T21:01:17Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  複素ヒルベルト空間上で作用するエルミート作用素 $A$ を 2n$ とする。 A$ がパウリ拡大において小さな次数を持つとき、あるいは言い換えれば、$A$ は局所 $n$-量子ハミルトニアンである。 A$ が $d$-local, textiti.e., $deg(A)le d$ であるときは常に、次の離散化型不等式を持つことを示す。
  論文  参考訳（メタデータ） (2025-09-15T14:26:11Z)
• Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs [54.28273395444243]
  我々は,モノトニック値 Omega (MVP) アルゴリズムが,差分を考慮した差分依存残差境界を$tildeOleft(left(sum_Delta_h(s,a)>0 fracH2 log K land MathttVar_maxtextc$。
  論文  参考訳（メタデータ） (2025-06-06T20:33:57Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Estimation and Inference in Distributional Reinforcement Learning [28.253677740976197]
  サイズ$widetilde Oleft(frac|mathcalS||mathcalA|epsilon2 (1-gamma)4right)$ suffices to ensure the Kolmogorov metric and total variation metric between $hatetapi$ and $etapi$ is below $epsilon$ with high probability。 以上の結果から,多種多様な統計的汎関数の統計的推測への統一的アプローチがもたらされた。
  論文  参考訳（メタデータ） (2023-09-29T14:14:53Z)
• Perturbation Analysis of Randomized SVD and its Applications to Statistics [8.731676546744353]
  RSVD(英: RSVD)は、大規模データ行列の切り詰められたSVDを計算するための計算効率のよいアルゴリズムのクラスである。 本稿では、$ell$ と $ell_2,infty$ の正則特異ベクトル $widehatmathbfU$ と $widehatmathbfM$ の上限を導出する。 理論結果を、$widehatmathbfM$ が観測されていない信号行列 $mathbfM$ の加法摂動であるような設定に適用する。
  論文  参考訳（メタデータ） (2022-03-19T07:26:45Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
  ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。 任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
  論文  参考訳（メタデータ） (2021-03-17T00:59:33Z)
• From Smooth Wasserstein Distance to Dual Sobolev Norm: Empirical Approximation and Statistical Applications [18.618590805279187]
  我々は$mathsfW_p(sigma)$が$pth次スムーズな双対ソボレフ$mathsfd_p(sigma)$で制御されていることを示す。 我々は、すべての次元において$sqrtnmathsfd_p(sigma)(hatmu_n,mu)$の極限分布を導出する。
  論文  参考訳（メタデータ） (2021-01-11T17:23:24Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。 我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
  論文  参考訳（メタデータ） (2020-06-29T17:10:10Z)

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

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