論文の概要: Block Sparse Attention with Log-Linear Complexity

• arxiv url: http://arxiv.org/abs/2609.31093v1
• Date: Fri, 25 Sep 2026 10:28:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-28 18:27:51.338094
• Title: Block Sparse Attention with Log-Linear Complexity
• Title（参考訳）: Log-Linear Complexity によるブロックスパース注意
• Abstract要約: ピラミッドTop-K$選択戦略を用いたブロックスパースアテンション機構であるPISAを提案する。 具体的には、キーの粗い階層を構築し、粗いレベルから選択する。 プーリングにより、$O(log N)$レベルのキーを構築し、$O(Nlog N)$の全体的な複雑さをもたらす。
• 参考スコア（独自算出の注目度）: 26.432462497801083
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Scaling language models to long contexts is limited by the quadratic cost of self-attention. Block sparse attention offers an efficient alternative, but selecting the retained blocks remains a bottleneck. Conventional block selection requires scoring all query-block pairs and therefore remains quadratic in sequence length. To address this issue, we propose PISA, a block-sparse attention mechanism that employs a pyramid Top-$K$ selection strategy. The main idea is to gradually narrow down the candidates across different levels, making it more efficient to find the most relevant keys. Specifically, we construct a coarse-to-fine hierarchy of keys and perform selection from the coarsest level. At each level, LogSumExp scoring is applied to a bounded candidate set to select candidates for the next finer level, continuing until the finest level is reached. Through pooling, we construct $O(\log N)$ levels of keys, yielding an overall complexity of $O(N\log N)$, where $N$ denotes the sequence length. We develop hardware-aware Triton kernels for both training and inference, fusing hierarchical routing and LogSumExp scoring without materializing the query-key score matrix. We further evaluate our method on language modeling tasks. Compared with the baseline, our method achieves comparable performance on benchmarks such as commonsense reasoning while delivering better results on retrieval tasks.
• Abstract（参考訳）: 言語モデルを長いコンテキストにスケールすることは、自己注意の二次的なコストによって制限される。 ブロックスパースアテンションは効率的な代替手段を提供するが、保持されたブロックを選択することはボトルネックのままである。 従来のブロック選択では、全てのクエリブロック対をスコアリングする必要があるため、シーケンス長は2次である。 この問題に対処するために,ピラミッドTop-$K$選択戦略を用いたブロックスパースアテンション機構であるPISAを提案する。 主なアイデアは、候補をさまざまなレベルに絞り込み、最も関連性の高いキーを見つけるのをより効率的にすることだ。 具体的には、キーの粗い階層を構築し、粗いレベルから選択する。 各レベルにおいて、LogSumExpスコアは、境界付き候補セットに適用され、次に細かいレベルの候補を選択し、最も細かいレベルに達するまで続く。 プーリングにより、$O(\log N)$のキーのレベルを構築し、$O(N\log N)$の全体的な複雑さをもたらす。 我々は,クエリキースコア行列を具体化せずに,階層的ルーティングとLogSumExpスコアを融合させ,トレーニングと推論の両方のためのハードウェア対応トリトンカーネルを開発した。 言語モデリングタスクにおける手法をさらに評価する。 本手法は,ベースラインと比較して,コモンセンス推論などのベンチマークにおいて同等の性能を達成し,検索タスクにおいてより良い結果を提供する。

関連論文リスト

• Sparser Block-Sparse Attention via Token Permutation [46.22204775916057]
  本稿では,ブロックレベルの空間性を高めるために,注目の置換特性を活用するプラグイン・アンド・プレイ方式であるPermuted Block-Sparse Attention (textbfPBS-Attn)を提案する。 PBS-Attnは、カスタムのpermuted-FlashAttentionカーネルをベースとして、長文プリフィルで最大2.75タイムのエンドツーエンドのスピードアップを実現しています。
  論文  参考訳（メタデータ） (2025-10-24T09:11:50Z)
• ZETA: Leveraging Z-order Curves for Efficient Top-k Attention [22.90397380324185]
  本稿では,全シーケンスに対する過去のトークンの並列クエリを可能にするZETAを提案する。 ZETA は合成textscMulti-Query Associative Recall タスクにおける標準注意性能と一致する。
  論文  参考訳（メタデータ） (2025-01-24T15:33:05Z)
• FLARE: Faithful Logic-Aided Reasoning and Exploration [47.46564769245296]
  タスク分解を用いて問題空間をトラバースする新しい手法を提案する。 我々はLarge Language Modelsを使ってソリューションを計画し、クエリを事実に軟式化し、論理プログラミングコードを使って述語する。 提案手法は,生成したコードに対する推論プロセスの忠実度を計算し,外部の解法に頼らずにマルチホップ探索のステップを解析する。
  論文  参考訳（メタデータ） (2024-10-14T19:39:11Z)
• Hierarchical Context Merging: Better Long Context Understanding for Pre-trained LLMs [61.40047491337793]
  本稿では,大規模言語モデルの制約を克服する新しいトレーニングフリースキームである階層型cOntext MERging(HOMER)を提案する。 HomeRは、長いインプットを管理可能なチャンクに分割する、分別/対数アルゴリズムを使用する。 トークン削減技術がマージ毎に先行し、メモリ使用効率が保証される。
  論文  参考訳（メタデータ） (2024-04-16T06:34:08Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Pyramid-BERT: Reducing Complexity via Successive Core-set based Token Selection [23.39962989492527]
  BERTのようなトランスフォーマーベースの言語モデルは、様々なNLPタスクで最先端を達成しているが、計算的に禁止されている。 本稿では,従来の使用法を,理論的な結果によって正当化されたemコアセットベースのトークン選択法で置き換えるピラミッド-BERTを提案する。 コアセットベースのトークン選択技術により、高価な事前トレーニングを回避でき、空間効率の良い微調整が可能となり、長いシーケンス長を扱うのに適している。
  論文  参考訳（メタデータ） (2022-03-27T19:52:01Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。 最小クラスタ回復誤差率のアルゴリズムを考案する。 適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2019-10-14T09:18:26Z)

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

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