論文の概要: Sparse Attention as a Range Searching Problem: Towards an Inference-Efficient Index for KV Cache

• arxiv url: http://arxiv.org/abs/2605.06763v2
• Date: Mon, 11 May 2026 02:30:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-12 16:21:29.405902
• Title: Sparse Attention as a Range Searching Problem: Towards an Inference-Efficient Index for KV Cache
• Title（参考訳）: 範囲探索問題としてのスパース注意:KVキャッシュの推論効率指標を目指して
• Authors: Mohsen Dehghankar, Abolfazl Asudeh,
• Abstract要約: 臨界KVエントリの省略は、モデル出力に重大なエラーを引き起こす可能性がある。 既存の方法は通常、固定または適応的なトークン予算の下で機能する。 本稿では,効率的なKVキャッシュ検索に適した新しいインデックス構造であるLouverを紹介する。
• 参考スコア（独自算出の注目度）: 11.676571773958145
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Sparse attention improves LLM inference efficiency by selecting a subset of key-value entries, but at the cost of potential accuracy degradation. In particular, omitting critical KV entries can induce substantial errors in model outputs. Existing methods typically operate under fixed or adaptive token budgets and provide empirical robustness or partial theoretical guarantees, yet they do not ensure zero false negatives in decoding steps, particularly since the set of relevant tokens is both query- and step-dependent. Our empirical observations confirm that missing even one critical key can lead to sharp error spikes, especially in long reasoning tasks where the set of important tokens varies throughout decoding. This observation motivates the need for indexing methods that dynamically adapt to these variations across decoding steps while guaranteeing a full recall of the relevant keys above a certain threshold. We address this challenge by reformulating sparse attention as the halfspace range searching problem. However, existing range searching indices are not suitable for modern LLM inference due to their computational and implementation overheads. To overcome this, we introduce Louver, a novel index structure tailored for efficient KV cache retrieval. Louver (i) guarantees zero false negatives with respect to a specified threshold in both theory and practice, (ii) is lightweight to integrate into existing LLM pipelines, and (iii) incorporates hardware-aware optimizations for both CPU and GPU executions. Our experiments demonstrate that Louver outperforms prior sparse attention methods in both accuracy and runtime, and is faster than highly optimized dense attentions such as FlashAttention. These results highlight that recall guarantees are a critical and overlooked dimension of sparse attention, and open a new direction for building theoretically grounded, efficient KV cache indices.
• Abstract（参考訳）: スパースアテンションは、キー値エントリのサブセットを選択することでLLM推論効率を向上するが、潜在的な精度劣化のコストがかかる。 特に、臨界KVエントリを省略すると、モデル出力にかなりの誤差が生じる。 既存のメソッドは通常、固定または適応トークンの予算の下で動作し、経験的な堅牢性や部分的な理論的保証を提供するが、デコードステップにおいて、特に関連するトークンのセットがクエリとステップに依存しているため、偽陰性は保証されない。 私たちの経験的観察では、1つの重要なキーが欠落しても、特に重要なトークンセットがデコードを通して変化する長い推論タスクにおいて、急激なエラースパイクを引き起こす可能性があることが確認されています。 この観察は、特定のしきい値以上の関連するキーの完全なリコールを保証しながら、デコードステップ間でこれらのバリエーションに動的に適応するインデクシング方法の必要性を動機付けている。 ハーフスペース範囲探索問題としてスパースアテンションを再構成することで,この問題に対処する。 しかし、既存の範囲探索指標は計算と実装のオーバーヘッドのため、現代のLLM推論には適していない。 これを解決するために,効率的なKVキャッシュ検索に適した新しいインデックス構造であるLouverを導入する。 ルーバー (i)理論と実践の双方において、特定のしきい値に対してゼロ偽陰性を保証する。 (ii)既存のLLMパイプラインに統合する軽量で、 (iii)CPUとGPUの両方の実行にハードウェアを意識した最適化が組み込まれている。 我々の実験では、Louverは精度と実行時の両方で事前の疎度な注意法よりも優れており、FlashAttentionのような高度に最適化された注意法よりも高速であることを示した。 これらの結果から,リコール保証は重要で見落とされがちな注意の次元であり,理論上は基礎的かつ効率的なKVキャッシュ指標を構築するための新たな方向を開くことが示唆された。

関連論文リスト

• Where Matters More Than What: Decoding-aligned KV Cache Compression via Position-aware Pseudo Queries [39.38028687042293]
  キーバリュー(KV)キャッシュは、効率的なLarge Language Models(LLM)推論に不可欠である。 既存のKVキャッシュ圧縮手法は、プリフィル段階でトークンの重要性を推定するために入力側注意パターンに依存している。 位置認識型擬似クエリ(DapQ)を提案し,位置認識型擬似クエリによるKVキャッシュ圧縮を近似する。
  論文  参考訳（メタデータ） (2026-03-12T05:36:32Z)
• Predicting Future Utility: Global Combinatorial Optimization for Task-Agnostic KV Cache Eviction [19.14455067106419]
  現在のKVキャッシュ消去法は、すべての頭において重要な指標としてスコアが一貫したプロキシであることを暗黙的に仮定して、瞬時メトリクスに依存している。 本稿では,長期的セマンティック情報を保存する上で,最適予算配分は限界効用によって管理されるべきであることを示す。 LU-KVの実践的展開を容易にするために,データ駆動型オフラインプロファイリングプロトコルを実装した。
  論文  参考訳（メタデータ） (2026-02-09T12:23:38Z)
• Fast KVzip: Efficient and Accurate LLM Inference with Gated KV Eviction [50.99402504483692]
  凍結重み付き言語モデルのための新しいゲーティングベースのKVキャッシュ消去手法を提案する。 私たちのアプローチは、プリフィルとデコードの両方の段階にシームレスに統合されます。 実験の結果,KVキャッシュの最大70%を除去しながら,ほぼ無作為な性能を維持していることがわかった。
  論文  参考訳（メタデータ） (2026-01-25T03:07:54Z)
• Training-free Context-adaptive Attention for Efficient Long Context Modeling [57.703159205740185]
  トレーニングフリーコンテキスト適応注意(TCA-Attention)は、学習不要なスパースアテンション機構であり、効率的な長文推論のための情報トークンのみに選択的に参画する。 TCA-Attentionは2.8$times$のスピードアップを実現し、128Kのコンテキスト長でKVキャッシュを61%削減し、フルアテンションに匹敵するパフォーマンスを維持している。
  論文  参考訳（メタデータ） (2025-12-10T01:54:57Z)
• SpecAttn: Speculating Sparse Attention [1.6921396880325779]
  SpecAttnは、投機的復号化技術とシームレスに統合する、新しいトレーニング不要のアプローチである。 私たちの重要な洞察は、投機的復号中にドラフトモデルによって既に計算されている注意重みを利用して、ターゲットモデルの重要なトークンを特定することです。 SpecAttnは、PG-19データセットのパープレキシティをわずか15.29%増加させ、キー値キャッシュアクセスを75%以上削減する。
  論文  参考訳（メタデータ） (2025-10-31T17:12:34Z)
• Judge Q: Trainable Queries for Optimized Information Retention in KV Cache Eviction [53.83828564664595]
  大規模言語モデル(LLM)は、キー値(KV)キャッシュを使用して、シーケンス処理中に履歴情報を格納する。 KVキャッシュ消去の現在の方法は、通常、プレフィルフェーズからの最後のウィンドウをクエリとして利用し、消去のためのKV重要度スコアを計算する。 ソフトトークンリストを組み込んだ新しいトレーニング手法であるジャッジQを提案する。
  論文  参考訳（メタデータ） (2025-09-13T03:34:12Z)
• AttentionPredictor: Temporal Patterns Matter for KV Cache Compression [64.75459635661562]
  我々は,KVキャッシュ圧縮とクリティカルトークン識別のための注意パターンを直接予測する,学習に基づく最初の手法であるAttentionPredictorを提案する。 AttentionPredictorは、注意スコアを正確に予測し、無視可能なメモリを消費する統一予測モデルを共有する。 注意情報の大半を保持することで、AttentionPredictorは、キャッシュオフロードシナリオで13$times$KVキャッシュ圧縮と5.6$times$スピードアップを達成する。
  論文  参考訳（メタデータ） (2025-02-06T13:41:46Z)
• Squeezed Attention: Accelerating Long Context Length LLM Inference [61.787865959140994]
  本稿では,入力コンテキストの大部分を固定したアプリケーションを高速化するために,Squeezed Attentionを提案する。 推論中、ユーザ入力からのクエリトークンとセントロイドを比較し、固定されたコンテキストからどのキーが意味論的に関連しているかを予測する。 また,線形から対数的への注意の複雑さを,固定した文脈長に対して低減できる階層型アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-14T18:54:19Z)
• ZipVL: Efficient Large Vision-Language Models with Dynamic Token Sparsification [29.163757099307553]
  大規模視覚言語モデル(LVLM)の効率は、プリフィルフェーズにおける注意機構の計算ボトルネックによって制約される。 本稿では,重要なトークンの動的比割り当て戦略を通じて,LVLM向けに設計された効率的な推論フレームワークZipVLを提案する。
  論文  参考訳（メタデータ） (2024-10-11T07:24:21Z)
• Ada-KV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference [37.94892570127548]
  大規模言語モデルは様々なドメインで優れていますが、キーバリュー(KV)キャッシュの増加によって効率上の課題に直面しています。 最近の取り組みは、実行中に大量の非クリティカルキャッシュ要素を排除し、KVキャッシュサイズを削減することを目的としている。 本稿では,Ada-KVを提案する。
  論文  参考訳（メタデータ） (2024-07-16T09:53:32Z)

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

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