PaperlayerView exact revision on arXiv

Source-linked AI summary

OpenAttention: One Percent Is Enough with Tail Proxies

Hyunwoo Yu, Jongbeom Lee, Hyunbin Kim, Sungjun Park, Jaemin Choi, Jincheol Yang, Seunghun Moon, Bongjoon Hyun, Kyomin Sohn, Kyeongbo Kong, Suk-Ju Kang

arXiv:2610.30951v1cs.LGcs.AI

TL;DR

Sparse attention must account for the unread tail, which top-k truncation omits and sampling estimates poorly at low density. OpenAttention builds query-aware tail proxies and allocates reads by estimated weight error. It retains 99% of dense accuracy at a 1% read and achieves state-of-the-art accuracy across benchmarks and models.

  • Problem

    Sparse attention must preserve tail information, but top-k methods discard it and sampling-based tail estimates grow sharply in error as density falls.

    Source: §1 · p. 2

  • Method

    OpenAttention clusters unread keys under query geometry, selects clusters and tokens using estimated weight error, and represents the remaining tail with count-aware mean proxies.

    Source: §1 · pp. 2–3

  • Results

    OpenAttention retains 99% of dense accuracy at a 1% read and achieves state-of-the-art accuracy across benchmarks and models.

    Source: §6 · p. 9

  • Takeaways & Limitations

    The findings support representing unread tails with constructed proxies rather than relying on sampling or truncation.

    Source: §1 · p. 2

    ErrorGate estimates within-cluster variance using diagonal terms for efficiency, so it cannot recover the exact error.

    Source: §6 · p. 9

Abstract

from arXiv · show

Sparse attention reads only a small subset of the key-value cache, and how to treat the unread tail remains a key challenge. Discarding the tail biases the output, and sampling it as previous approaches do fails at reads of 5% and below, where the tail likely holds heavy hitters the selector missed. Our key observation is that the simplest possible proxy, one token that folds the entire tail into its count-aware mean, already yields lower output error than a sample at every read behind a practical selector. We further show in closed form that at low reads sampling nearly doubles the weight error of discarding while a single proxy stays below it. Building on these findings, we explore approximating the dense attention distribution with a few proxies that target the tail. We propose OpenAttention, a pipeline of clustering, ErrorGate and top-k selection followed by a count-aware mean proxy. To implement clustering and selection both efficiently and effectively, we design training-free Query-Geometry Clustering (QGC) and a Query-Geometry Selector (QGS), which compress the keys while respecting the query directions. Additionally, unlike prior methods that rank clusters by centroid alone, ErrorGate allocates the exact read by the estimated weight error of each cluster. On RULER-32K HARD with Llama-3.1-8B, OpenAttention retains 99% of dense accuracy at a 1% read. It also achieves state-of-the-art accuracy across models, context lengths and datasets. Our customized attention kernel, OpenAttention.flash, runs the decode attention stage 10$\times$ faster than dense attention at a 1% read.

1 INTRODUCTION

Sparse attention reduces KV-cache reads, but truncating or sampling the unread tail can lose information needed to approximate dense attention. OpenAttention represents the tail with count-aware proxies, using query-aware clustering and error-based selection.

1 INTRODUCTION

  • A single count-aware mean proxy keeps output error low across examined distributions and densities, while sampling performs worse than top-k alone at low density.The empirical finding holds behind both HashAttention and oracle top-k; the proxy yields the lowest error at every density behind HashAttention and at low density behind oracle top-k.Source: §1 · p. 2, Figure 3 · p. 3
  • At a 1% read, OpenAttention scores 86.30 versus 87.04 for full attention and 48.2 for the best baseline on RULER-32K HARD with Llama-3.1-8B.It also achieves state-of-the-art accuracy across models and context lengths from 16K to 96K.Source: §1 · pp. 2–3
  • At a 1% read, OpenAttention.flash runs the decode attention stage 10× faster than dense attention in one online softmax pass.The customized Triton-based kernel processes exact tokens and proxies together.Source: §1 · pp. 2–3
  • OpenAttention represents the tail with proxies built through clustering, ErrorGate, top-k selection, and a count-aware mean.The framework approximates the full softmax distribution rather than truncating or sampling the tail.Source: §1 · p. 2, Figure 2 · p. 2
  • QGC and QGS compress keys under query geometry so clustering and top-k selection follow attention scores while remaining efficient.ErrorGate allocates the read budget using approximated weight error rather than cluster mass alone.Source: §1 · pp. 2–3

2 KEY OBSERVATION ON ONE SIMPLE PROXY

The section compares sampling and a single proxy for representing unread attention tails, then examines their weight discrepancies and how those findings motivate multi-cluster proxies.

2.1 RELATIVE OUTPUT ERROR ACROSS DENSITIES.

  • Behind HashAttention, a single proxy yields the lowest relative output error at every tested density; behind oracle top-k, it does so at low density.Sampling improves on its top-k selector at high density but performs worse than the selector alone at low density.Source: §2.1 · p. 3

2.2 ATTENTION WEIGHTS AND TAIL APPROXIMATION ERROR

  • The single proxy is equivalent to one virtual token with logit z̄_T + log N and mean value v̄_T.Here, N is the number of unread tail tokens.Source: §2.2 · pp. 3–4
  • For fixed unnormalized-weight discrepancy, sampling approaches twice the discard discrepancy when m ≪ N; this is not a factor-of-two claim for normalized attention or output error.The passage distinguishes exact fixed-tail discrepancies from the Gaussian-population prediction.Source: §2.2 · p. 4
  • Weight discrepancy E alone does not explain sampling’s density-dependent output failure; normalizer uncertainty grows as the sample shrinks, and missed high-weight tokens can perturb the value direction.The exact output identity explains why similar weight discrepancies need not imply similar output errors.Source: §2.2 · p. 4
  • For residual clusters, each proxy’s discrepancy contribution is proxy mass times weight spread, and it vanishes for equal logits.The Gaussian model estimates the spread as approximately 0.8σ_b at small within-cluster logit standard deviation; Section 3 builds on this decomposition with QGC, ErrorGate, and QGS.Source: §2.2 · p. 4

3 OPENATTENTION: APPROXIMATE TAIL DISTRIBUTION BY PROXIES

OpenAttention clusters the cache under query geometry, selects exact tokens from high-error clusters, and represents each residual cluster with a count-aware mean proxy. QGC, QGS, and ErrorGate support this pipeline, while OpenAttention.flash processes exact tokens and proxies in one online softmax pass.

3.1 OVERALL PROCESS OF OPENATTENTION

  • Each cluster caches its size, mean key-value token, and diagonal key-variance token; ErrorGate allocates the expansion budget, and QGS selects exact tokens within clusters.The remaining members act as one virtual softmax token with mean value and logit equal to the residual mean logit plus log cluster size.Source: §3.1 · p. 4

3.2 QUERY GEOMETRY CLUSTERING AND SELECTION

  • The query geometry is computed at prefill and reused for clustering and decoding; the median absolute cosine similarity between a decode query and M’s leading eigenvector is 0.82.Clustering runs once after prefill, while selection reuses the eigenvectors at each decoding step.Source: §3.2 · p. 5

3.2.1 QUERY GEOMETRY CLUSTERING

  • QGC clusters projected keys under the query-geometry metric, which makes within-cluster logit similarity the clustering objective.Keys are projected onto the query eigenvectors before clustering.Source: §3.2.1 · p. 5

3.2.2 QUERY GEOMETRY SELECTOR

  • QGS projects keys and queries onto the same query subspace, using low-bit key codes to score candidates for exact top-k reads.Keys are coded once, and selection reuses the projections during decoding.Source: §3.2.2 · p. 6

3.3 ERRORGATE

  • At a 1% read, ErrorGate’s estimated-error ranking yields 86.30 mean accuracy, versus 85.99 for centroid-mass ranking on RULER-32K HARD.The comparison varies only the ErrorGate ranking statistic.Source: Table 3 · p. 6, §3.3 · p. 6

3.4 OPENATTENTION.FLASH: OPENATTENTION ON FLASHATTENTION-2.

  • OpenAttention.flash gathers selected tokens and cluster proxies in tiles of 64 and processes them in one online softmax pass without data-dependent loop bounds or host synchronization.Cached pooled sums make removing query-read tokens cost one subtraction per token the kernel already loads.Source: §3.4 · p. 7

4 EXPERIMENTS

Across read densities, OpenAttention stays close to dense attention while the compared sparse baselines lose accuracy as density falls. Results also show gains from its components and accuracy close to dense across models, cache-compression settings, and context lengths.

4 EXPERIMENTS

  • The RULER-32K HARD setup uses 200 samples per task, dense prefill, sparse question and generation attention, and charges all query-read KV rows, including cluster statistics, to the budget.Index scans are excluded from the budget for every method.Source: §4 · p. 7

4.1 COMPARISON WITH OTHER METHODS ACROSS READ DENSITIES

  • OpenAttention stays close to dense attention across 10% to 1% reads, while HashAttention, MagicPIG, and vAttention degrade sharply as density decreases.vAttention slightly exceeds HashAttention at 10% density but falls below it at lower densities despite sharing its selector.Source: §4.1 · p. 7

4.2 ABLATION STUDY

  • At a 5% total-read budget, proxies raise mean accuracy from 67.35 to 77.91; adding ErrorGate and QGS yields 85.90 and 86.73 individually, or 86.82 together.The configuration without these components corresponds to vAttention on the HashAttention selector.Source: Table 4 · p. 8, §4.2 · p. 8

4.3 EVALUATION ON VARIOUS MODELS

  • At a 3% density, OpenAttention stays within 0.7 points of dense on all three evaluated models, while baselines lose up to 29.9 points.The evaluation includes Llama-3.1-8B-Instruct, DeepSeek-R1-Distill-Llama-8B, and Mistral-7B-Instruct-v0.3.Source: Table 5 · p. 8, §4.3 · p. 8

4.4 ORTHOGONALITY TO KV CACHE COMPRESSION

  • Adding OpenAttention to three KV-cache compressors changes mean accuracy by only -0.14 points on average when it reads 10% of retained entries.The compressors are PyramidKV, SnapKV, and StreamingLLM.Source: §4.4 · p. 8

4.5 CONTEXT LENGTH

  • At a matched 3% read, OpenAttention remains within 0.7 points of dense accuracy across 16K–96K contexts; at 96K, HashAttention scores 27.99, vAttention 40.20, and MagicPIG 33.19.OpenAttention is numerically higher than dense at 16K and 96K.Source: §4.5 · p. 8

5 RELATED WORK

Prior sparse-attention work develops top-k selection, tail sampling, and cluster-based approaches. OpenAttention differs by using query geometry for clustering and selecting clusters according to estimated weight error.

Top-k selectors

  • Top-k selectors use coarse bounds, hashes, key-only representations, or query-informed projections; QGS projects keys and queries onto eigenvectors of the query second moment [2024; 2025a; 2024; 2024; 2025; 2025a; 2024; 2024].The same eigenvectors define QGC’s metric, so selection and clustering share query geometry.Source: §5 · pp. 8–9

Sampling the tail

  • Tail-sampling methods include LSH importance sampling, top-k followed by random tail sampling, and post-softmax value sampling [2025; 2026; 2026]; SparQ instead weights a mean value by leftover approximate score mass [2024].OpenAttention instead summarizes every tail token with proxies because low-read samples can miss heavy hitters left in the tail.Source: §5 · p. 9

Clustering and centroid proxies

  • Prior cluster methods use key similarity or centroid mass for grouping and selection [2026; 2025b; 2025; 2026], whereas QGC uses query geometry and ErrorGate estimates cluster weight error.The cited methods include cache compression and sparse-attention approaches.Source: §5 · p. 9

6 CONCLUSION AND LIMITATIONS

OpenAttention approximates tail information with proxies built through clustering, ErrorGate, top-k selection, and a count-aware mean. The paper reports accuracy close to dense at a 1% read and identifies diagonal variance approximation as a limitation.

6 CONCLUSION AND LIMITATIONS

  • OpenAttention approximates tail logits with clustering, ErrorGate, top-k selection, and a count-aware mean, using query geometry and estimated weight error.The method aims to preserve information from the tail rather than lose it through truncation.Source: §6 · p. 9
  • OpenAttention preserves 99% of dense accuracy at a 1% read and achieves state-of-the-art accuracy across benchmarks and models.Source: §6 · p. 9
  • ErrorGate approximates within-cluster variance with diagonal terms for efficiency, but this approximation cannot recover the exact error.Its agreement with the full-variance estimate is reported as Spearman correlation 0.92.Source: §6 · p. 9

AI USE STATEMENT

The authors used generative AI for editorial, translation, literature-search, and LaTeX tasks, but not to develop the research or interpret its results. They report checking suggested edits and references and accepting responsibility for the final content.

AI USE STATEMENT

  • AI tools edited the paper for clarity and readability and helped translate parts of the draft into English.Source: AI USE STATEMENT · p. 10
  • The tools also helped search related literature and write and format the LaTeX source, including tables, captions, and references.Source: AI USE STATEMENT · p. 10
  • The authors say AI tools did not develop the method, theory, hypotheses, experiments, implementation, or results interpretation, and they checked suggested edits and references.They take responsibility for the final content, including AI-assisted artifacts.Source: AI USE STATEMENT · p. 10

ETHICS STATEMENT

The work uses public models and benchmarks and synthetic RULER sets, without human subjects or personal data. The authors caution that approximate attention can change outputs and should be validated on the target task.

ETHICS STATEMENT

  • The work does not involve human subjects or personal data.Source: ETHICS STATEMENT · p. 10
  • The models and benchmarks are publicly available and used under their licenses, while the generated 64K and 96K RULER sets are synthetic.Source: ETHICS STATEMENT · p. 10
  • Because approximate attention can change model outputs, the authors say accuracy should be validated on the target task before deployment.Source: ETHICS STATEMENT · p. 10

REPRODUCIBILITY STATEMENT

The statement directs readers to the paper’s method, proofs, evaluation protocol, hyperparameters, per-task results, baselines, kernel, and synthetic-set generation details. It also specifies fixed-prompt greedy decoding and provides a code repository.

REPRODUCIBILITY STATEMENT

  • The statement locates QGC, QGS, ErrorGate, budget allocation, read accounting, and the evaluation protocol in the paper’s method and evaluation sections.Source: REPRODUCIBILITY STATEMENT · p. 10
  • It points to proofs and assumptions, deployed hyperparameters, per-budget and per-task results, baseline configurations, kernel details, and RULER-set generation.Source: REPRODUCIBILITY STATEMENT · p. 10
  • All accuracy numbers use greedy decoding with fixed prompts, and code is available in the OpenAttention repository.Source: REPRODUCIBILITY STATEMENT · p. 10

A ERROR BOUND OF CLUSTER AGGREGATION AND THE RANKING RULE

The appendix distinguishes exact finite-cluster discrepancies from estimates and allocation heuristics, then relates these quantities to normalized attention and output error. It describes ErrorGate’s estimated-error allocation and gives closed forms and qualifications for tail sampling and proxying.

A ERROR BOUND OF CLUSTER AGGREGATION AND THE RANKING RULE

  • For a finite residual partition, each cluster contributes a nonnegative exact discrepancy that vanishes for equal logits and is removed by reading the whole cluster.Partial reads change the residual mean, so the discrepancy must be recomputed.Source: A ERROR BOUND OF CLUSTER AGGREGATION… · p. 13
  • The normalized-attention distance is bounded using the unnormalised discrepancy and normalizer error, with an upper bound of 2E.The relation applies to nonnegative implied weights with a positive estimated normalizer.Source: A ERROR BOUND OF CLUSTER AGGREGATION… · pp. 13–14
  • The output-bound factorization depends on proxy mass, value radius, and within-cluster weight dispersion; a small-dispersion bound requires an additional moment condition.That condition is not implied by empirical variance and can fail with rare positive-logit outliers.Source: A ERROR BOUND OF CLUSTER AGGREGATION… · pp. 14–15
  • The Gaussian population estimate substitutes a dispersion model for finite-cluster quantities, while the query-metric k-means objective minimizes a token-count-weighted surrogate rather than the mass- and value-weighted output bound.Source: A ERROR BOUND OF CLUSTER AGGREGATION… · p. 15

A.1 ERRORGATE: THE ESTIMATE AND THE HIERARCHICAL BUDGET

  • At a 1% read, the signed Jensen-gap alternative scores 86.28 versus 86.30 for the deployed absolute-discrepancy score.The signed deficit is second-order in small dispersion, whereas the deployed estimate is first-order.Source: §A.1 · p. 16
  • ErrorGate allocates reads in proportion to estimated discrepancy, then QGS selects the highest-scoring tokens within each cluster and residual statistics are recomputed after reads.The partial-token allocation is a deployment choice, not a proven optimum.Source: A ERROR BOUND OF CLUSTER AGGREGATION… · p. 15, §A.1 · p. 17

A.2 CLOSED FORMS OF THE SAMPLING AND PROXY ERRORS

  • For fixed tail statistics, sampling approaches twice the discard discrepancy when m is much smaller than N, but this comparison concerns unnormalised weight error, not normalized attention or output error.The appendix cautions that aggregate plug-in predictions and rowwise measurements are descriptive rather than rowwise-matched validation.Source: §A.2 · pp. 17, 19

B.1 QUALITY AND ERROR ACROSS READ DENSITIES

Across the plotted tasks, OpenAttention stays near dense-attention quality and has the lowest sparse-method error, especially at low read densities. The grouped diagnostics describe how the decode-row comparisons are constructed, how cluster errors are assessed, and how the fused kernel handles proxy tokens.

B.1 QUALITY AND ERROR ACROSS READ DENSITIES

  • Across three tasks and read densities from 1% to 10%, OpenAttention stays close to dense-attention quality and has the lowest sparse-method error, with the clearest separation at low density.The curves show baseline errors rising and task quality falling as density drops.Source: §B.1 · p. 19

B.2 PROTOCOL OF THE DECODE-ROW DIAGNOSTIC

  • The decode-row diagnostic compares four residual treatments at equal total read on the same cache and query, including top-k only, sampling, cluster proxies, and deployed OpenAttention.It records 137,216 rows across RULER-32K HARD tasks, layers, heads, and generated tokens.Source: §B.2 · p. 19, Figure 10 · p. 20

B.3 PROTOCOL OF THE SELECTOR AND AGGREGATION DIAGNOSTICS

  • At C=64, QGC’s attention-weighted within-cluster logit standard deviation is 1.05 and weight error is 0.030, versus 1.67 and 0.040 for key-only k-means.The eight clusters with the largest estimated errors contain 84% of aggregation error and 95% of exact top-1% tokens left in the tail; estimated and true cluster errors have Spearman 0.92.Source: §B.3 · p. 20

C OPENATTENTION.FLASH: OPENATTENTION ON FLASHATTENTION-2

  • OpenAttention.flash keeps FlashAttention-2’s tiled online-softmax loop, gathering selected tokens and then streaming unread-cluster means as virtual tokens with occupancy added to logits.Unread-member statistics are prepared before launch by subtracting selected tokens from cached pooled sums.Source: C OPENATTENTION.FLASH: OPENATTENTION… · p. 20
  • At 5%, OpenAttention.flash is 1.9× faster than dense attention, while the unfused implementation is 2.7× slower; median and maximum relative errors against fp32 are 1.6 × 10−3 and 2.1 × 10−3.The kernel scores 85.45 against PyTorch’s 85.35 on RULER-32K HARD at 5%.Source: C OPENATTENTION.FLASH: OPENATTENTION… · p. 21, Figure 11 · p. 22
  • The reported 10× speedup covers the attention stage, not the full decode step, because selection cost is excluded and remains unmeasured.The scan and top-k are common to sparse methods in the comparison, but their method-specific cost is not included.Source: C OPENATTENTION.FLASH: OPENATTENTION… · p. 21, Table 9 · p. 22

D.1 CHOOSING (C, E, t) PER BUDGET

  • As the read shrinks, the budget grid favors spending a larger share on proxy statistics to identify where attention mass lies rather than on reading tokens.The grid varies C, E, and t while holding the selector, partition, ranking rule, and cap rule fixed.Source: §D.1 · p. 22

E RESULTS AT EVERY BUDGET

Across matched reads, OpenAttention remains close to dense accuracy down to 3% and within one point at 1%, while the baselines degrade more steeply. The appendix describes the baseline configurations and the vAttention parameter-selection protocol used for comparisons.

E RESULTS AT EVERY BUDGET

  • OpenAttention scores 87.08, 86.82, 86.83, and 86.30 at 10%, 5%, 3%, and 1% reads, respectively, staying within one point of dense at 1% while baselines degrade steeply.At 5%, 3%, and 1%, vAttention trails plain HashAttention by 2.7, 7.7, and 11.9 points, respectively, and overtakes it only at 10%.Source: E RESULTS AT EVERY BUDGET · p. 22, Table 11 · p. 23

F BASELINE CONFIGURATIONS

  • The component ablation is reported at a matched 5% total read on RULER-32K HARD, with 200 requests per task.The supplied table caption specifies the evaluation scope but not the ablation values.Source: Table 12 · p. 24

F.1 MAGICPIG CONFIGURATION

  • The MagicPIG comparison calibrates its number of hash tables to each target read and accepts configurations only when measured read matches the budget.For the 1%, 3%, 5%, and 10% targets, the reported configuration uses K=9 with L=8, 25, 46, and 100, respectively.Source: §F.1 · pp. 23–24

F.2 VATTENTION CONFIGURATION PROTOCOL

  • The vAttention protocol selects the lowest-error configuration among those meeting the target read, probing budget shares and adaptive-sampling tolerances on four requests before full-benchmark evaluation.At 0.5–5%, the selected setting uses the full nominal budget and a 50/50 split with ϵ=δ=0.3; tighter tolerances overshoot the target under this accounting.Source: §F.2 · p. 24

G QUESTION-FREE TASKS

The grouped sections cover question-free LongBench evaluations, composition with KV-cache compression, and a context-length sweep. The supplied passages specify these evaluation settings and a concrete caveat for the compression composition, but do not give the corresponding outcome values.

G QUESTION-FREE TASKS

  • The question-free evaluation includes LongBench summarisation at 3% read with no question chunk and LongBench-v2 on its first 60 requests, with scores described as indicative only.The LongBench-v2 setup uses 0-shot accuracy and contexts truncated to 32,000 tokens.Source: G QUESTION-FREE TASKS · pp. 24–25, Table 15 · p. 26

H COMPOSING WITH KV-CACHE COMPRESSION

  • In the eviction-compression comparison, evicted rows are hidden from attention, selection, tail clustering, and cluster statistics; charging 1.5 rows per cluster therefore upper-bounds actual reads when clusters lose members.The partition still covers all keys, making its k-means objective slightly mismatched and costing accuracy rather than improving it.Source: H COMPOSING WITH KV-CACHE COMPRESSION · p. 26

I CONTEXT-LENGTH SWEEP

  • The context-length sweep evaluates 16K, 32K, 64K, and 96K settings using 100 samples per task and a 3% target read for the compared methods.OpenAttention uses C=64 · L/32768 clusters and E=0 in this sweep.Source: I CONTEXT-LENGTH SWEEP · p. 27, Table 18 · p. 27

Related papers

Loading 2610.30951v1…