論文の概要: ZETA: Leveraging Z-order Curves for Efficient Top-k Attention

• arxiv url: http://arxiv.org/abs/2501.14577v2
• Date: Thu, 13 Feb 2025 03:43:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-14 13:46:09.723993
• Title: ZETA: Leveraging Z-order Curves for Efficient Top-k Attention
• Title（参考訳）: ZETA: 効率的なトップkアテンションのためのZオーダー曲線の活用
• Authors: Qiuhao Zeng, Jerry Huang, Peng Lu, Gezheng Xu, Boxing Chen, Charles Ling, Boyu Wang,
• Abstract要約: 本稿では,全シーケンスに対する過去のトークンの並列クエリを可能にするZETAを提案する。 ZETA は合成textscMulti-Query Associative Recall タスクにおける標準注意性能と一致する。
• 参考スコア（独自算出の注目度）: 22.90397380324185
• License:
• Abstract: Over recent years, the Transformer has become a fundamental building block for sequence modeling architectures. Yet at its core is the use of self-attention, whose memory and computational cost grow quadratically with the sequence length $N$, rendering it prohibitively expensive for long sequences. A promising approach is top-$k$ attention, which selects only the $k$ most relevant tokens and achieves performance comparable to vanilla self-attention while significantly reducing space and computational demands. However, causal masks require the current query token to only attend to past tokens, preventing the existing top-$k$ attention method from efficiently searching for the most relevant tokens in parallel, thereby limiting training efficiency. In this work, we propose ZETA, leveraging \textbf{Z}-Order Curves for \textbf{E}fficient \textbf{T}op-$k$ \textbf{A}ttention, to enable parallel querying of past tokens for entire sequences. % in both space and time complexity of $\mathcal{O}(N \log N)$. We first theoretically show that the choice of key and query dimensions involves a trade-off between the curse of dimensionality and the preservation of relative distances after projection. In light of this insight, we propose reducing the dimensionality of keys and queries in contrast to values and further leverage $Z$-order curves to map low-dimensional keys and queries into \emph{one}-dimensional space, which permits parallel sorting, thereby largely improving the efficiency for top-$k$ token selection. Experimental results demonstrate that ZETA matches the performance of standard attention on the synthetic \textsc{Multi-Query Associative Recall} task and outperforms attention and its variants on \textsc{Long Range Arena} and \textsc{WikiText-103} language modeling.
• Abstract（参考訳）: 近年、Transformerはシーケンスモデリングアーキテクチャの基本的なビルディングブロックとなっている。 しかし、その中核となるのは自己注意の使用であり、そのメモリと計算コストは、シーケンスの長さが$N$で2倍に増加するため、長いシーケンスでは極めて高価である。 有望なアプローチは、最も高額なトークンのみを選択し、バニラの自己注意に匹敵するパフォーマンスを達成し、空間と計算の要求を大幅に削減する、トップ・ドル・アテンションである。 しかし、因果マスクは、現在のクエリトークンが過去のトークンにのみ参加することを要求し、既存のトップ$k$アテンションメソッドが最も関連性の高いトークンを効率的に検索することを防止し、トレーニング効率を制限している。 本研究では,過去トークンのシーケンス全体に対する並列クエリを可能にするために,ZETAを提案する。 % の空間および時間的複雑さは$\mathcal{O}(N \log N)$である。 まず、鍵次元と問合せ次元の選択は、次元の呪いと射影後の相対距離の保存とのトレードオフを伴うことを理論的に示す。 この知見を踏まえて、キーとクエリの次元を値と対照的に減少させ、さらに$Z$の曲線を利用して低次元キーとクエリを \emph{one}-次元空間にマッピングし、並列ソートを可能にすることにより、上位$k$トークン選択の効率を大幅に改善する。 実験結果から,ZETA は合成 \textsc{Multi-Query Associative Recall} タスクにおける標準の注意力と一致し,その性能は \textsc{Long Range Arena} および \textsc{WikiText-103} 言語モデリングにおける注意力と変動性を上回ることがわかった。

関連論文リスト

• Linear Transformer Topological Masking with Graph Random Features [52.717865653036796]
  重み付き隣接行列の学習可能な関数としてトポロジカルマスクをパラメータ化する方法を示す。 私たちの効率的なマスキングアルゴリズムは、画像およびポイントクラウドデータのタスクに対して、強力なパフォーマンス向上を提供します。
  論文  参考訳（メタデータ） (2024-10-04T14:24:06Z)
• A Training-free Sub-quadratic Cost Transformer Model Serving Framework With Hierarchically Pruned Attention [43.211427581302715]
  大規模言語モデルにおける文脈長を増大させるため,HiP(Hierarchically Pruned Attention)を提案する。 HiPは注意機構の時間的複雑さを$O(T log T)$に減らし、空間的複雑さを$O(T)$に減らし、$T$はシーケンス長である。 HiPは, 劣化を最小限に抑えつつ, プリフィルとデコードの両方のレイテンシとメモリ使用率を著しく低減することを示す。
  論文  参考訳（メタデータ） (2024-06-14T08:32:45Z)
• Hierarchical Context Merging: Better Long Context Understanding for Pre-trained LLMs [61.40047491337793]
  本稿では,大規模言語モデルの制約を克服する新しいトレーニングフリースキームである階層型cOntext MERging(HOMER)を提案する。 HomeRは、長いインプットを管理可能なチャンクに分割する、分別/対数アルゴリズムを使用する。 トークン削減技術がマージ毎に先行し、メモリ使用効率が保証される。
  論文  参考訳（メタデータ） (2024-04-16T06:34:08Z)
• One Pass Streaming Algorithm for Super Long Token Attention Approximation in Sublinear Space [11.735802740426294]
  注意計算は、$O(n2)$の時間複雑性と$O(n2)$の空間複雑性を同時に行う。 ストリーミング方式で1パスのデータのみを読み取る新しいアルゴリズムを導入する。 特に,本アルゴリズムは,超長期トークンを用いたメモリ効率の優れた性能を示す。
  論文  参考訳（メタデータ） (2023-11-24T18:35:00Z)
• Tree Cross Attention [59.8891512435847]
  Tree Cross Attention (TCA) は、Cross Attentionに基づくモジュールで、パラメータ $mathcalO(log(N))$ のトークン数からのみ情報を取得する。 さまざまな分類や不確実性回帰タスクに対して,TCAはクロスアテンションに匹敵する性能を示し,トークン効率は著しく向上した。
  論文  参考訳（メタデータ） (2023-09-29T16:50:23Z)
• Recasting Self-Attention with Holographic Reduced Representations [31.89878931813593]
  マルウェア検出の問題に触発された我々は,ホログラフィックリダクション(HRR)のニューロシンボリックアプローチを用いて,自己アテンションを再キャストする。 我々は、 $mathcalO(T H log H)$ time complexity, $mathcalO(T H)$ space complexity, and convergence in 10times$ less epochs などの利点を得る。 我々のHrrformerはLRAベンチマークでほぼ最先端の精度を実現しています。
  論文  参考訳（メタデータ） (2023-05-31T03:42:38Z)
• Vcc: Scaling Transformers to 128K Tokens or More by Prioritizing Important Tokens [65.4435926060951]
  本稿では,超長周期の変換器の効率を,各層でより小さな表現に圧縮することで向上することを提案する。 我々のアルゴリズムは効率的であるだけでなく(4Kと16Kのベースラインに比べて3倍以上の効率向上を達成する)、多数のタスクで競合/ベターパフォーマンスを提供する。
  論文  参考訳（メタデータ） (2023-05-07T10:32:18Z)
• Simplifying and Understanding State Space Models with Diagonal Linear RNNs [56.33053691749856]
  本研究は、離散化ステップを解消し、バニラ対角線形RNNに基づくモデルを提案する。 概念的にはるかに単純であるにもかかわらず、$mathrmDLR$は以前提案したSSMと同じくらいのパフォーマンスを示す。 また、合成シーケンス・ツー・シーケンス・タスクのスイートによって、SSMとアテンションベースモデルの表現性も特徴付ける。
  論文  参考訳（メタデータ） (2022-12-01T18:53:06Z)
• Pyramid-BERT: Reducing Complexity via Successive Core-set based Token Selection [23.39962989492527]
  BERTのようなトランスフォーマーベースの言語モデルは、様々なNLPタスクで最先端を達成しているが、計算的に禁止されている。 本稿では,従来の使用法を,理論的な結果によって正当化されたemコアセットベースのトークン選択法で置き換えるピラミッド-BERTを提案する。 コアセットベースのトークン選択技術により、高価な事前トレーニングを回避でき、空間効率の良い微調整が可能となり、長いシーケンス長を扱うのに適している。
  論文  参考訳（メタデータ） (2022-03-27T19:52:01Z)
• Combiner: Full Attention Transformer with Sparse Computation Cost [142.10203598824964]
  計算の複雑さを低く保ちつつ、各注目ヘッドにフルアテンション機能を提供するコンバインダを提案する。 既存のスパース変圧器で使用されるスパースアテンションパターンのほとんどは、そのような分解設計をフルアテンションに刺激することができることを示す。 自己回帰的タスクと双方向シーケンスタスクの両方に関する実験的評価は、このアプローチの有効性を示す。
  論文  参考訳（メタデータ） (2021-07-12T22:43:11Z)

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

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