Fugu-MT 論文翻訳(概要): Circuit Complexity From Physical Constraints: Scaling Limitations of Attention

論文の概要: Circuit Complexity From Physical Constraints: Scaling Limitations of Attention

arxiv url: http://arxiv.org/abs/2509.19161v1
Date: Tue, 23 Sep 2025 15:40:36 GMT
ステータス: 翻訳完了
システム内更新日: 2025-09-24 20:41:27.929772
Title: Circuit Complexity From Physical Constraints: Scaling Limitations of Attention
Title（参考訳）: 物理的制約からの回路複雑度:注意のスケーリング限界
Authors: Benjamin Prada, Ankur Mali,
Abstract要約: 我々は、より複雑なデータセットのエントロピーに対応するために、$omega(n3/2)$のアテンション機構はスケールできないことを示した。この結果は変換器の表現性に意味のある境界を定義するための方法論を同時に提供する。
参考スコア（独自算出の注目度）: 0.2750124853532831
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We argue that the standard circuit complexity measures derived from $NC, AC, TC$ provide limited practical information and are now insufficient to further differentiate model expressivity. To address these new limitations, we define a novel notion of local uniformity and a family of circuit complexity classes $RC(\cdot)$ that capture the fundamental constraints of scaling physical circuits. Through the lens of $RC(\cdot)$, we show that attention mechanisms with $\omega(n^{3/2})$ runtime cannot scale to accommodate the entropy of increasingly complex datasets. Our results simultaneously provide a methodology for defining meaningful bounds on transformer expressivity and naturally expose the restricted viability of attention.
Abstract（参考訳）: 我々は、NC, AC, TC$から導かれる標準回路複雑性尺度は、限られた実用的な情報を提供しており、モデル表現性をさらに区別するには不十分であると主張している。これらの新たな制約に対処するために、局所均一性の新たな概念と、物理回路のスケーリングの基本的制約を捉える回路複雑性クラス$RC(\cdot)$の族を定義する。 RC(\cdot)$のレンズを通して、$\omega(n^{3/2})$ランタイムによる注意機構は、ますます複雑なデータセットのエントロピーに対応するためにスケールできないことを示す。本研究は,トランスフォーマー表現性に有意な境界を定義する方法論を同時に提供し,注意力の制限を自然に露呈する。

関連論文リスト

$\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input) [0.9023122463034333]
$mathsfQAC0$は、任意の単一量子ビットゲートと一般化されたトフォリゲートから構成される定数深さ量子回路のクラスである。我々は、$mathsfQAC0$回路が従来の回路よりもはるかに強力であることを示す。
論文参考訳（メタデータ） (2026-01-06T18:40:44Z)
Spectral Small-Incremental-Entangling: Breaking Quasi-Polynomial Complexity Barriers in Long-Range Interacting Systems [2.911917667184046]
量子複雑性の鍵となる課題は、エンタングルメント構造が動的からどのように現れるかである。本稿では,作用素の構造エンタング力を測定するスペクトルエンタングリング強度について紹介する。我々はスペクトルSIE定理を証明し、R'enyi tanglement growth を$alpha ge 1/2$で普遍極限とし、絡み合いスペクトルの頑健な1/s2$tailを明らかにした。
論文参考訳（メタデータ） (2025-09-15T14:56:40Z)
A Quantum Computational Perspective on Spread Complexity [0.0]
我々は、時間進化と重ね合わせという2つの基本的な操作から構築された回路複雑性フレームワークの制限ケースとして、拡散複雑性が出現することを示すことによって、拡散複雑性と量子回路複雑性の直接的な接続を確立する。提案手法では,単位ゲートとビーム分割演算がターゲット状態を生成する計算装置を活用し,合成コストの最小化により,無限小時間進化限界における複雑性の拡散に収束する複雑性尺度が得られた。
論文参考訳（メタデータ） (2025-06-08T19:04:42Z)
Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding [30.769940410718558]
テンソルバージョンにおけるキー値キャッシュは、推論中に重大なボトルネックを示す。我々の研究は、テンソルアテンションバージョンによる空間複雑性障壁を一般化する。全体として、我々の研究は、テンソルアテンションデコーディングにおけるKVキャッシュ圧縮の時間メモリトレードオフを理解するための理論的基盤を提供する。
論文参考訳（メタデータ） (2025-03-14T06:01:42Z)
Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
$Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
論文参考訳（メタデータ） (2025-02-25T19:08:26Z)
The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective [55.15192437680943]
連続状態と行動空間を持つ非線形力学系の一般設定におけるオンライン強化学習のサンプル複雑性について検討した。我々のアルゴリズムは、$mathcalO(N epsilon2 + Mathrmln(m(epsilon)/epsilon2)$のポリシーを後悔する。力学がコンパクトで実数値のパラメータ集合によってパラメータ化される特別な場合、$mathcalO(sqrt)のポリシー後悔を証明する。
論文参考訳（メタデータ） (2025-01-27T10:01:28Z)
The Space Complexity of Approximating Logistic Loss [11.338399194998933]
a general $tildeOmega(dcdot mu_mathbfy(mathbfX))$ space lower bound if $epsilon$ is constant。また、$mu_mathbfy(mathbfX)$は計算が難しいという事前予想も否定する。
論文参考訳（メタデータ） (2024-12-03T18:11:37Z)
On the Computational Power of QAC0 with Barely Superlinear Ancillae [10.737102385599169]
深さ$$d$$mathrmQAC0$回路は、近似次数$ta(n)$の関数を計算するために$n1+3-d$アンシラを必要とする。これは超線形サイズの$mathrmQAC0$上の最初の超線形下界である。
論文参考訳（メタデータ） (2024-10-09T02:55:57Z)
Surrogate Constructed Scalable Circuits ADAPT-VQE in the Schwinger model [0.0]
我々は,量子コンピュータ上の周期システムのシミュレーションをさらに進めるため,新しいアプローチ (SC)$2$-ADAPT-VQE を開発した。我々の手法は、任意に大きいが、任意に小さくない体積に対して定義される座標不変作用素のプールからアンザッツを構築する。提案手法では,古典的にトラクタブルなサーロゲート構成法を用いて,無関係な演算子をプールから取り除き,拡張性のある回路を定義する最小サイズを小さくする。
論文参考訳（メタデータ） (2024-08-22T18:00:00Z)
Recurrent Complex-Weighted Autoencoders for Unsupervised Object Discovery [62.43562856605473]
複雑な重み付き再帰的アーキテクチャの計算上の優位性について論じる。本稿では,反復的制約満足度を実現する完全畳み込みオートエンコーダSynCxを提案する。
論文参考訳（メタデータ） (2024-05-27T15:47:03Z)
Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文参考訳（メタデータ） (2024-02-06T15:39:09Z)
Parity vs. AC0 with simple quantum preprocessing [0.0]
我々は、$mathsfAC0$が$mathsfQNC0$回路の測定結果に作用するハイブリッド回路モデルについて検討する。私たちは、$mathsfQNC0$が、タスクの検索とサンプリングに驚くほど強力なのに対して、その出力のグローバルな相関において、そのパワーは"ロックアウト"されていることに気付きました。
論文参考訳（メタデータ） (2023-11-22T20:27:05Z)
Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文参考訳（メタデータ） (2022-06-17T17:55:43Z)
Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文参考訳（メタデータ） (2021-08-19T16:16:48Z)
Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning [99.34907092347733]
本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
論文参考訳（メタデータ） (2021-06-28T00:38:54Z)
Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文参考訳（メタデータ） (2020-12-03T14:03:20Z)
An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文参考訳（メタデータ） (2020-08-24T06:50:57Z)
On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文参考訳（メタデータ） (2019-06-02T03:03:45Z)

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