論文の概要: Towards Tight Bounds for Streaming Attention

• arxiv url: http://arxiv.org/abs/2606.07205v1
• Date: Fri, 05 Jun 2026 12:15:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-08 14:33:29.727847
• Title: Towards Tight Bounds for Streaming Attention
• Title（参考訳）: ストリーミング注意のためのタイトバウンドを目指して
• Authors: Justin Y. Chen, Ying Feng, Piotr Indyk, Michael Kapralov, Ekaterina Kochetkova, Boris Prokhorov,
• Abstract要約: 我々は,KVキャッシュ圧縮(KV cache compression)と呼ばれる,限られた空間で変圧器を実装する問題について検討する。 Haris et al, COLT'25, Kochetkova et al, NeurIPS'25の最近の研究は、ストリーミングアテンション近似問題としてKVキャッシュ圧縮を定式化した。 本研究では,ストリーミングアテンション近似問題を再検討し,その空間的複雑性にほぼ厳密な制約を与える。
• 参考スコア（独自算出の注目度）: 23.994623370320323
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The attention mechanism is a cornerstone of modern transformer architectures. However, its expressive power comes at the cost of quadratic runtime and linear space usage. In particular, the classical transformer architecture explicitly stores all previously seen input elements (tokens) in order to generate the next one. The problem of implementing a transformer in limited space, known as KV cache compression, has received much interest over the past few years, spurring the development of powerful heuristics. Recent works of Haris et al, COLT'25 and Kochetkova et al, NeurIPS'25, formalized KV cache compression as the streaming attention approximation problem, providing both upper bounds (based on discrepancy theory) and information theoretic lower bounds. However, those papers left open a significant gap between the upper and lower bounds. For example, the space usage of their algorithms increases with the precision parameter, but the lower bound does not get stronger. In this work, we revisit the streaming attention approximation problem and provide nearly tight bounds on its space complexity. On the algorithmic side, we achieve the result through a surprisingly tight interplay between three distinct methods for kernel density estimation: discrepancy-based coreset constructions (e.g., Charikar-Kapralov-Waingarten'24), the polynomial method (e.g., Greengard-Rokhlin'87, Alman-Song'23), and space partitioning (e.g., Andoni-Laarhoven-Razenshteyn-Waingarten'17, Charikar-Kapralov-Nouri-Siminelakis'20). On the lower bound side, our main technical contribution is a new technique for using the INDEX problem with a large amount of side information that we hope will prove useful in other high dimensional geometric estimation problems.
• Abstract（参考訳）: 注意機構は、現代のトランスフォーマーアーキテクチャの基盤となっている。 しかし、その表現力は二次的実行と線形空間利用のコストによってもたらされる。 特に、古典的なトランスフォーマーアーキテクチャは、前述した全ての入力要素(トークン)を明示的に格納し、次の要素を生成する。 KVキャッシュ圧縮として知られる限られた空間でトランスフォーマーを実装するという問題は、ここ数年で大きな関心を集め、強力なヒューリスティックスの開発に拍車をかけた。 Haris et al, COLT'25, Kochetkova et al, NeurIPS'25の最近の研究は、KVキャッシュ圧縮をストリーミングアテンション近似問題として定式化し、上界(離散性理論に基づく)と情報理論の下界の両方を提供する。 しかし、これらの論文は上境界と下限の間に大きなギャップを開いていた。 例えば、それらのアルゴリズムの空間使用量は精度パラメータによって増加するが、下限はより強くならない。 本研究では,ストリーミングアテンション近似問題を再検討し,その空間的複雑性にほぼ厳密な制約を与える。 アルゴリズム側では、カーネル密度推定の3つの異なる方法(例えば、Charikar-Kapralov-Waingarten'24)、多項式法(eg、Greengard-Rokhlin'87、Alman-Song'23)、空間分割(eg、Andoni-Laarhoven-Razenshteyn-Waingarten'17、Charikar-Kapralov-Nouri-Siminelakis'20)の間で驚くほど密な相互作用が達成される。 下限側では、他の高次元幾何推定問題において有用であることを期待する大量の側情報を持つINDEX問題を利用するための新しい手法が主な技術的貢献である。

関連論文リスト

• Cramming 1568 Tokens into a Single Vector and Back Again: Exploring the Limits of Embedding Space Capacity [5.087492669838185]
  圧縮比が最大で x1500 となるベクトルが存在することを示す。 得られた限界は、入力埋め込みの理論的能力とそれらの実用的利用の間の実質的なギャップを浮き彫りにする。
  論文  参考訳（メタデータ） (2025-02-18T17:08:45Z)
• Hadamard Attention Recurrent Transformer: A Strong Baseline for Stereo Matching Transformer [53.62241289871256]
  Adamard Attention Recurrent Stereo Transformer(HART)について紹介する。 HARTには、以下のコンポーネントを組み込んだ新しいアテンションメカニズムが含まれている。 反映的な領域では、HARTはKITTI 2012ベンチマークで1位にランクインした。
  論文  参考訳（メタデータ） (2025-01-02T02:51:16Z)
• Lower Bounds for Time-Varying Kernelized Bandits [43.62161925881489]
  ノイズの多い観測によるブラックボックス関数の最適化は、広く応用される基本的な問題である。 特定のアプリケーションに不可欠な非定常シナリオについて検討するが、現時点では十分に理解されていない。
  論文  参考訳（メタデータ） (2024-10-22T04:45:47Z)
• Decomposed Diffusion Sampler for Accelerating Large-Scale Inverse Problems [64.29491112653905]
  本稿では, 拡散サンプリング法とクリロフ部分空間法を相乗的に組み合わせた, 新規で効率的な拡散サンプリング手法を提案する。 具体的には、ツイーディの公式による分母化標本における接空間がクリロフ部分空間を成すならば、その分母化データによるCGは、接空間におけるデータの整合性更新を確実に維持する。 提案手法は,従来の最先端手法よりも80倍以上高速な推論時間を実現する。
  論文  参考訳（メタデータ） (2023-03-10T07:42:49Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。 第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
  論文  参考訳（メタデータ） (2023-02-02T08:33:36Z)
• Softmax-free Linear Transformers [90.83157268265654]
  視覚変換器(ViT)は、視覚知覚タスクの最先端を推し進めている。 既存の手法は理論的に欠陥があるか、視覚認識に経験的に効果がないかのいずれかである。 我々はSoftmax-Free Transformers (SOFT) のファミリーを提案する。
  論文  参考訳（メタデータ） (2022-07-05T03:08:27Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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