論文の概要: The Head Complexity of Boolean Functions in Single-Layer Attention
- arxiv url: http://arxiv.org/abs/2609.04046v1
- Date: Thu, 03 Sep 2026 16:22:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-04 18:28:39.152348
- Title: The Head Complexity of Boolean Functions in Single-Layer Attention
- Title（参考訳）: 単層アテンションにおけるブール関数の頭部複雑度
- Authors: Rajmohan Rajaraman, Ravi Sundaram, Amanuel Tesfaye,
- Abstract要約: 単層アテンションのみのモデルで関数を計算するのに必要なアテンションヘッドの最小数について検討する。
k$headは$k$-bitパリティを計算するが、$(k+1)$-bitパリティを計算できない。
また、埋め込み次元と数値精度のためのコンパクト性境界を確立する。
- 参考スコア（独自算出の注目度）: 2.2727733134290813
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: What can a single layer of self-attention compute? We study head complexity: the minimum number of attention heads required to compute a function in a one-layer attention-only model. We establish an exact hierarchy under this measure: $k$ heads compute $k$-bit parity but cannot compute $(k+1)$-bit parity. The lower bound is unconditional in the two resources a transformer might otherwise exploit; it holds at unbounded embedding dimension and unbounded numerical precision. The proof rests on an alternating-sum obstruction: after clearing the softmax denominators, every monomial in the resulting decision polynomial omits at least one of the $k+1$ input bits, forcing its correlation with parity to vanish. The same obstruction yields lower bounds for related tasks, including the well-studied multi-hop induction-head task. We also establish compactness bounds for embedding dimension and numerical precision. Specifically, a compactness theorem shows that any function computable at all can be computed with embedding dimension and precision bounded by the discrete data of the task, namely, head count, alphabet size, and length. Thus, potentially unbounded dimension or precision provably cannot substitute for heads. Finally, we derive nearly matching universal bounds for general binary functions: $2^n$ heads suffice to compute every $n$-bit binary function, with one head per monomial in its multilinear expansion, while a counting argument shows almost all such functions require $Ω(2^n/n^2)$ heads. This lower bound matches the upper bound to within a $\operatorname{poly}(n)$ factor, even when dimension and precision are unbounded. Together, these results characterize head requirements for Boolean computation in this model.
- Abstract（参考訳）: 自己注意計算の単一レイヤには何ができるのか?
頭部の複雑さについて検討する: 1層の注意のみのモデルで関数を計算するのに必要な最小の注意ヘッド数。
k$headは$k$-bitパリティを計算するが、$(k+1)$-bitパリティを計算できない。
下界は変圧器が悪用する可能性のある2つの資源において無条件であり、非有界な埋め込み次元と非有界な数値精度で保持する。
ソフトマックス分母をクリアした後、決定多項式のすべての単項は$k+1$入力ビットの少なくとも1つを省略し、パリティとの相関は消滅する。
同じ障害は、よく研究されたマルチホップ誘導ヘッドタスクを含む、関連するタスクの低い境界をもたらす。
また、埋め込み次元と数値精度のためのコンパクト性境界を確立する。
具体的には、コンパクト性定理は、計算可能な任意の関数は、そのタスクの離散データ、すなわち、頭数、アルファベットサイズ、長さで有界な埋め込み次元と精度で計算できることを示している。
したがって、潜在的に非有界な次元や精度は、確実に頭の代わりにはならない。
最後に、2^n$ヘッドはすべての$n$ビットのバイナリ関数を計算するのに十分であり、その多重線型展開において単項ごとに1つのヘッドを持つ。
この下界は、次元と精度が非有界である場合でも、$\operatorname{poly}(n)$ factor内の上界と一致する。
これらの結果は、このモデルにおけるブール計算のヘッド要件を特徴付ける。
関連論文リスト
- Attention-based representations for multi-task computation [8.34204538904959]
2つの単純かつ具体的なマルチタスクシナリオで要求されるヘッド数に境界を定めている。
第1のシナリオでは、線形予測器が与えられたリストの最小と最大の両方を計算できるようにベクトル表現を求める。
第2のシナリオでは、しきい値関数が与えられた$n$ビットの文字列のXORを計算することができるようにベクトル表現を求める。
論文 参考訳（メタデータ） (2026-08-04T21:52:04Z) - Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
シングルトンクエリでは、Chamferは最大内部積類似度(MAX-IP)になる。
すべての固定$in(0,1)$に対して、定数は$A_,c_>0$である。
単位球MAX-IPマトリクスは、DNFパターンマトリクスの正確な2値アフィンイメージであり、少なくとも8ドルのギャップがある。
論文 参考訳（メタデータ） (2026-07-22T17:27:20Z) - Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - On the Computational Hardness of Transformers [14.73362105392153]
この結果から, トランスフォーマーの効率は, 独立評価値のLH$よりも高いことがわかった。
小さな埋め込み方式では、$LH$アテンションヘッドは別々に$LHN2 + o(1)$時間を必要とする。
大規模な埋め込み方式では、$LHN+ o(1)$算術演算を使用して別々に$LH$アテンションヘッドを計算することができる。
論文 参考訳（メタデータ） (2026-03-11T21:48:43Z) - An Efficient Computational Framework for Discrete Fuzzy Numbers Based on Total Orders [41.99844472131922]
我々は、$textitpos$関数を計算するために、合計(許容可能な)順序の構造を利用するアルゴリズムを導入する。
提案手法は、下層の鎖の大きさの2乗である$mathcalO(n2 m log n)$の複雑さを実現する。
その結果、この定式化は計算コストを大幅に削減することを示した。
論文 参考訳（メタデータ） (2025-11-21T09:35:07Z) - Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
本稿では、よく知られたトランスフォーマーアーキテクチャを基盤とした、ランクの新たな特徴付けについて述べる。
関数 $f$ のランクは、単一層変換器が要求する思考ステップの EmphChain の最小値に対応していることを示す。
また、マルチヘッド単一層トランスをキャプチャするマルチヘッドランクの概念を導入し、有界なマルチヘッドランクを持つ関数クラスのPAC学習性の解析を行う。
論文 参考訳（メタデータ） (2025-01-22T16:30:58Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - Localization in 1D non-parametric latent space models from pairwise
affinities [6.982738885923206]
対の親和性から一次元トーラスにおける潜伏位置を推定する問題を考察する。
高確率でsqrtlog(n)/n$の順序の最大誤差で全ての潜伏位置を確実にローカライズする推定手順を導入する。
論文 参考訳（メタデータ） (2021-08-06T13:05:30Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - On the Modularity of Hypernetworks [103.1147622394852]
構造化対象関数の場合、ハイパーネットワークにおけるトレーニング可能なパラメータの総数は、標準ニューラルネットワークのトレーニング可能なパラメータの数や埋め込み法よりも桁違いに小さいことを示す。
論文 参考訳（メタデータ） (2020-02-23T22:51:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。