論文の概要: The Condensate Theorem: Transformers are O(n), Not $O(n^2)$

• arxiv url: http://arxiv.org/abs/2602.06317v1
• Date: Fri, 06 Feb 2026 02:32:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-09 22:18:26.190921
• Title: The Condensate Theorem: Transformers are O(n), Not $O(n^2)$
• Title（参考訳）: The Condensate Theorem: Transformer are O(n), Not $O(n^2)$
• Authors: Jorge L. Ruiz Williams,
• Abstract要約: 注意空間は学習されたトポロジカルな性質であり、建築上の制約ではないことを示す。 任意のクエリに対して、トポロジカル多様体に注意を投射すると、完全な$O(n2)$の注意で100%の出力等価性が得られることを証明します。 二次的ボトルネックは、インテリジェンスではなく、ナイーブな実装の成果である、と結論付けている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present the Condensate Theorem: attention sparsity is a learned topological property, not an architectural constraint. Through empirical analysis of trained language models, we find that attention mass concentrates on a distinct topological manifold -- and this manifold can be identified dynamically without checking every position. We prove a general result: for any query, projecting attention onto the Condensate Manifold (Anchor + Window + Dynamic Top-k) achieves 100% output equivalence with full $O(n^2)$ attention. This is not an approximation -- it is lossless parity. We validate this across GPT-2, Pythia, Qwen2, TinyLlama, and Mistral, demonstrating bit-exact token matching on 1,500+ generated tokens. By mapping this topology to hardware, our Topological Attention kernel achieves a 159x measured speedup at 131K tokens (3.94ms vs 628ms) and a projected >1,200x speedup at 1M tokens, reducing inference costs by >99.9% compared to Flash Attention. We conclude that the quadratic bottleneck is an artifact of naive implementation, not intelligence.
• Abstract（参考訳）: 注意空間は、アーキテクチャ上の制約ではなく、学習されたトポロジカルな性質である。 訓練された言語モデルの経験的解析により、注意質量は異なる位相多様体に集中しており、この多様体はすべての位置をチェックすることなく動的に識別できる。 任意のクエリに対して、Condensate Manifold (Anchor + Window + Dynamic Top-k) に注意を向けると、完全に$O(n^2)$の注意で100%の出力等価性が得られる。 これは近似ではなく、損失のないパリティです。 我々はこれをGPT-2、Pythia、Qwen2、TinyLlama、Mistralで検証し、1500以上の生成トークン上でビットエクサクトトークンマッチングを示す。 このトポロジをハードウェアにマッピングすることで、トポロジカルアテンションカーネルは131Kトークン(3.94ms vs 628ms)で159倍のスピードアップを実現し、1Mトークンで1200倍のスピードアップを実現し、Flashアテンションと比較して推論コストを99.9%削減した。 二次的ボトルネックは、インテリジェンスではなく、ナイーブな実装の成果である、と結論付けている。

関連論文リスト

• Power-based Partial Attention: Bridging Linear-Complexity and Full Attention [8.782622621289251]
  注意が必要である」が、必要な注意の量は体系的に定量化されていない。 本稿では、O(L1+p)$のアテンション機構であるPPA(Power-based partial attention)を導入する。 0p1$が存在して、$O(L1+p)$の注意が、$O(L2)$の注意と同じ結果を達成するのに十分であることを示す。
  論文  参考訳（メタデータ） (2026-01-24T06:30:53Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Delta Attention: Fast and Accurate Sparse Attention Inference by Delta Correction [52.14200610448542]
  変圧器は二次的な複雑さを持ち、長いシーケンスに対して高い推論コストとレイテンシをもたらす。 本稿では、この分布シフトを修正するためのシンプルで斬新で効果的な手順を提案する。 1Mトークンのプリフィル処理では,Flash Attention 2の32倍の速度で,約98.5%の間隔を維持することができる。
  論文  参考訳（メタデータ） (2025-05-16T13:48:33Z)
• Topological quantum compilation of metaplectic anyons based on the genetic optimized algorithms [0.0]
  我々は、textitF-matrices, textitR-symbols, and fusion rules of metaplectic anyonを用いて、合計6つのエノンモデルを得る。 1ビットの場合、古典的 textitH- と textitT-gate は遺伝的アルゴリズムを改良した Solovay-Kitaev アルゴリズムを用いてうまく構築できる。
  論文  参考訳（メタデータ） (2025-01-03T10:18:16Z)
• HashAttention: Semantic Sparsity for Faster Inference [95.31739930718116]
  本稿では,HashAttention,framing pivotal token Identificationを推薦問題として紹介する。 トークン1個あたり32ビットの補助メモリしか必要とせず、最小品質の損失を最小限に抑えられるため、最大16タイムで使用されるトークンを削減できる。 A100 GPUでは、HashAttentionを組み込むことで、GPT-FASTで4.3times$、FlashDecodeで2.54times$、GPT-FASTで最大3.12times$高スループットを実現している。
  論文  参考訳（メタデータ） (2024-12-19T02:34:15Z)
• How Sparse Attention Approximates Exact Attention? Your Attention is Naturally $n^C$-Sparse [9.552839922307587]
  スパース注意(英: Sparse Attention)とは、標準的な注意計算と準四分法的な複雑性を近似する手法である。 KVキャッシュのプルーニング、スパースベースの高速注意、スパーストランスフォーマーといったテクニックのバリエーションは、効率的なLLM(Large Language Models)デプロイメントに広く利用されている。
  論文  参考訳（メタデータ） (2024-04-03T12:37:34Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• Random quantum circuits anti-concentrate in log depth [118.18170052022323]
  本研究では,典型的な回路インスタンスにおける測定結果の分布に要するゲート数について検討する。 我々の反集中の定義は、予測衝突確率が分布が均一である場合よりも大きい定数因子に過ぎないということである。 ゲートが1D環上で最寄りである場合と、ゲートが長距離である場合の両方において、$O(n log(n))ゲートも十分であることを示す。
  論文  参考訳（メタデータ） (2020-11-24T18:44:57Z)

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

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