論文の概要: Three Tokens Force Exponential Feature Rank in Nonnegative Kernel Attention
- arxiv url: http://arxiv.org/abs/2608.11427v1
- Date: Tue, 11 Aug 2026 20:49:34 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-13 19:07:54.373242
- Title: Three Tokens Force Exponential Feature Rank in Nonnegative Kernel Attention
- Title（参考訳）: 非負のカーネル注意における3つのTokens Force Exponential Feature Rank
- Abstract要約: ランク1の正規化されたカーネルアテンションは、最大2つの長さの列を正確に解く。
決定論的マルチヘッド, 多層スケッチモデルに対して, 独立解の個数において, 書き起こしの少ない境界線を証明した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Full attention exposes every token pair, whereas kernel attention compresses a sequence into a fixed-dimensional sketch. We show that this distinction becomes exponential at the first context length containing two competing candidates. On Min-IP over Boolean inputs, rank-one normalized kernel attention solves every sequence of length at most two exactly. In contrast, any single normalized nonnegative kernel-attention head that succeeds on all three-token sequences with error strictly below $1/2$ requires $2^{Ω(m)}$ features, even with arbitrary finite-dimensional tokenwise values and an arbitrary query-dependent affine readout. Dense softmax solves the same task with $m$-dimensional scores and constant temperature. The conclusion survives position-dependent token maps and a causal final query. As context length grows, the lower bound approaches the exact $2^m$-feature realization. Separately, for deterministic multihead, multilayer sketch models whose cross-token channels have finite alphabets, we prove a transcript lower bound linear in the number of independent answers and logarithmic in their alphabet size.
- Abstract（参考訳）: フルアテンションはすべてのトークンペアを公開するが、カーネルアテンションはシーケンスを固定次元のスケッチに圧縮する。
この区別は、2つの競合する候補を含む最初の文脈長で指数関数となることを示す。
ブール入力上のMin-IPでは、ランク1の正規化されたカーネルアテンションは、ほとんどの2つの長さの列を正確に解く。
対照的に、誤差が1/2$未満の3つのトーケン列すべてで成功する1つの正規化非負のカーネルアテンションヘッドは、任意の有限次元のトークンの値と任意のクエリ依存のアフィンの読み出しであっても、2^{Ω(m)}$特徴を必要とする。
Dense Softmaxは、$m$Dのスコアと一定の温度で同じタスクを解く。
結論は、位置依存のトークンマップと因果的な最終クエリに残る。
文脈長が大きくなると、下界は正確に2^m$-feature realizationに近づく。
決定論的マルチヘッド多層スケッチモデルでは, クロストケンチャネルが有限個のアルファベットを持つ場合, 独立回答の個数とアルファベットサイズにおける対数関係において, 書き起こしの低い境界線が証明される。
関連論文リスト
- A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。
我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文 参考訳（メタデータ） (2026-09-09T10:13:43Z) - Parameterized Complexity of $L_p$-Lipschitz Constants for Input Convex Neural Networks and $L_p$-Norm Maximization over Zonotopes [10.97628500062133]
リプシッツはニューラルネットワークを入力するためのネットワークの感度に標準的手法を定めている。
この問題に対してブルートフォースが本質的に最適であることを示す。
論文 参考訳（メタデータ） (2026-08-25T17:47:37Z) - Exact certification of a positive-order Rényi additivity violation for an explicit channel pair [0.0]
いずれのチャネルの出力も、$301/100000$から$2/3$の固有値を持つ。
これは、この明示的なペアのための最初の印刷され、コンピュータで検証された正の順序のエンドポイントである。
論文 参考訳（メタデータ） (2026-08-18T05:09:21Z) - Higher-Order Token Interactions via Quantum Attention [30.903467721896487]
我々は、浅いハードウェアで実現可能な量子アテンションヘッドである textbfQuantum Higher-Order Attention (QHA) を導入する。
QHAは回路内で秩序$kのトークン相互作用を合成し、局所的な単一ビット読み出しを通じて公開する。
応用として、QHAは3つの領域にわたるコンパクトな高次相互作用検出器として機能する。
論文 参考訳（メタデータ） (2026-06-10T05:33:12Z) - Near-Optimal Regret in Adversarial Kernel Bandits [50.68324062892194]
本稿では,各ラウンドにおける損失が任意の有界要素によって誘導される逆カーネルバンドイット問題について検討する。
我々の主な結果は、$widetildeObig(sqrtT, d_*(),log|X|big)$, ここでは$d_*()$は有効次元の広く解釈された概念である。
論文 参考訳（メタデータ） (2026-05-26T06:10:24Z) - Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - Multiplex Thinking: Reasoning via Token-wise Branch-and-Merge [87.51901436392427]
大規模言語モデルは、しばしばChain-of-Thought (CoT)でより効果的に複雑な推論タスクを解決する。
対照的に、人間は、しばしば、もっともらしい次のステップに対して、引力のある確率分布を維持することによって、柔らかに理にかなっている。
我々は、K候補トークンをサンプリングし、それらの埋め込みを1つの連続多重化トークンに集約するソフトな推論機構である多重思考を提案する。
モデルは自信を持っていれば、多重化トークンはほぼ独立しており、標準のCoTのように振る舞う。
論文 参考訳（メタデータ） (2026-01-13T18:48:00Z) - Token Sample Complexity of Attention [20.89022639697809]
我々は、$n$トークンで計算された注意が無限のトーケン限界に収束する速度を推定する。
コンパクトに支持された分布に対して、最初の結果は、注意写像が半径$R$の球に一様収束することを示す。
また,注意パラメータが無限大に近づき,ソフトマックスがハードマックスに近づく傾向についても検討する。
論文 参考訳（メタデータ） (2025-12-11T14:02:34Z) - Attention with Trained Embeddings Provably Selects Important Tokens [73.77633297039097]
トーケン埋め込みは言語モデリングにおいて重要な役割を担っているが、この実践的関連性にもかかわらず、理論的な理解は限られている。
本論文は,勾配降下法により得られた埋め込み構造を特徴付けることにより,そのギャップを解消する。
実世界のデータセット(IMDB、Yelp)の実験では、我々の理論が明らかにしたものに近い現象が示されている。
論文 参考訳（メタデータ） (2025-05-22T21:00:09Z) - Deterministic identification over channels with finite output: a dimensional perspective on superlinear rates [49.126395046088014]
有限出力であるが任意の入力アルファベットを持つメモリレスチャネルに対する一般性の問題を考える。
主な発見は、メッセージの最大長が$R,nlog n$、ブロック長$n$と超直線的にスケールすることである。
出力分布のペアの信頼性を保証し、DIコードを構築するのに十分であることを示す。
論文 参考訳（メタデータ） (2024-02-14T11:59:30Z) - Sequence graphs realizations and ambiguity in language models [1.3108652488669736]
いくつかの人気のある言語モデルは、単語の袋として入力テキスト$x$でローカルコンテキストを表す。
いくつかは曖昧で、列としていくつかの実現を認めたり、あるものは実現を認めなかったりする。
本稿では,シーケンスグラフの実現可能性とあいまいさについて,アルゴリズムの観点から検討する。
論文 参考訳（メタデータ） (2024-02-13T22:22:51Z) - Tokenization and the Noiseless Channel [71.25796813073399]
優れたトークン化器は、ある入力がモデルに伝達される手段であるチャネルの使用率を高める。
機械翻訳では、複数のトークン化器において、$alpha = 2.5$のR'enyiエントロピーがtextscBleu: $0.78$と非常に強い相関を持つことがわかった。
論文 参考訳（メタデータ） (2023-06-29T10:32:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。