論文の概要: 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})$ランタイムによる注意機構は、ますます複雑なデータセットのエントロピーに対応するためにスケールできないことを示す。
本研究は,トランスフォーマー表現性に有意な境界を定義する方法論を同時に提供し,注意力の制限を自然に露呈する。
関連論文リスト
- 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) - 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) - 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) - Instance-optimality in optimal value estimation: Adaptivity via
variance-reduced Q-learning [99.34907092347733]
本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。
局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。
他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
論文 参考訳（メタデータ） (2021-06-28T00:38:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。