acceptodds
Withdrawn from ICLR 2027

Certified Best-First Sparse Attention: Provable Early Termination via Admissible Block Bounds

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Sparse attention makes long-context decoding affordable, but most methods silently discard KV blocks: they do not report how much attention mass was dropped. Fixed-budget selectors commit to a budget independently of the query, dynamic heuristics adapt but provide no bound, and probabilistic verifiers offer only high-probability guarantees at a fixed configuration budget. We recast sparse attention as best-first search with provable early termination. BNB-Attention reads KV blocks in decreasing order of an admissible upper bound on the attention scores inside each block, and stops once the unread blocks can contain at most an fraction of the attention mass accumulated so far. This yields a deterministic, per-query, per-head certificate bounding the output error relative to dense attention; in the worst case, the method falls back to dense attention. The practicality of the certificate hinges on bound tightness: on real activations, min/max and ball bounds are 22-24 nats loose, forcing near-dense visits, whereas per-block quantized bounds with explicit rounding radii are roughly tighter, making certified early termination viable. Across more than 19 million evaluations on seven checkpoints from four base model families, we observe zero certificate violations. At , BNB-Attention matches dense performance on RULER32K-HARD using only 3.1% KV density, remains within sampling noise of dense on AIME 2024 where certificate-free SnapKV collapses, and matches the strongest probabilistic verifier on its own LongBench protocol at roughly one-third the KV budget. It also achieves attention-kernel speedup over FlashAttention at 128K context under the quality-verified setting .

Primary area:
foundation or frontier models, including LLMs
Keywords:
sparse attention, long-context inference, KV cache, efficient attention kernels, certified approximation / provable guarantees, branch and bound

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_hhtaOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes BNB, a branch-and-bound-based sparse attention method that provides deterministic error bounds for KV block selection at the query and attention-head level. It constructs upper bounds for candidate blocks, prioritizes block access based on these bounds, and terminates once the accumulated attention mass and remaining upper bound satisfy the stopping criterion. The method is training-free and uses quantized key indices to reduce the cost of bound estimation while retaining full-precision K/V data for selected blocks.

The main contribution is the combination of deterministic error guarantees with an adaptive sparse attention kernel. However, the extent to which these guarantees translate into practical LLM serving benefits remains insufficiently established.

Critical strengths

Principled error control: BNB provides deterministic error bounds for individual queries and heads, offering a principled alternative to fixed-budget selection and probabilistic verification approaches.

Adaptive computation: The branch-and-bound procedure can terminate early based on the remaining upper bound, avoiding unnecessary exact attention computations.

Practical kernel design: The quantized key-index design reduces the cost of bound estimation while retaining full-precision K/V data for selected blocks. The reported attention-kernel speedup also demonstrates the potential of the proposed approach.

Critical weaknesses

Insufficient evidence of practical serving benefits: The paper does not provide a direct comparison with existing sparse attention methods under matched hardware, quality, and total VRAM budgets. Consequently, it remains unclear whether BNB's deterministic guarantees translate into competitive end-to-end latency or throughput improvements over existing approaches.

Inconsistent sparsity and performance evidence: At 32K context length, the reported access ratio differs substantially between the quality evaluation (3.1%) and the timing harness (26-32%). This discrepancy makes it difficult to connect the reported sparsity to actual performance. The 2.68× attention-kernel speedup reported for Llama-3.1-8B at 128K context length also contrasts with the 1.20× full-model speedup reported for another model. Since these results use different models and settings, they do not establish a consistent end-to-end benefit.

Limited evaluation of realistic serving workloads: The evaluation does not cover continuous batching or paged KV caches, which limits the evidence for the method's applicability to practical LLM serving systems. In addition, the descriptions of whether prefill is included appear inconsistent, and the timing-harness workload is insufficiently specified.

Memory and scanning overhead: BNB trades approximately 25% additional KV storage for reduced exact K/V reads, while still requiring a scan of the full INT8 key index. The practical trade-off between index-scanning overhead, additional memory consumption, and saved attention computation deserves more thorough evaluation.

Reproducibility: The GPU hardware specifications and workload configurations are insufficiently documented, making it difficult to reproduce the reported performance and assess its generalizability.

Questions for authors

Q1. Can the authors provide a controlled comparison against representative sparse attention baselines under the same hardware, attention-quality target, and total VRAM budget, including end-to-end latency and throughput?

Q2. What explains the discrepancy between the reported access ratios in the quality evaluation and timing harness at 32K context length? Are the two measurements based on different workloads or configurations?

Q3. Could the authors clarify the timing methodology, including prefill inclusion, GPU specifications, and the exact workload used by the timing harness?

1 comment

Thank you for the review. The inconsistency you pointed out between the 3.1% density and the 26-32% measured by the timing harness was real, and tracing it led us to errors that require withdrawing the submission.

Q2 (3.1% vs. 26-32%). The 3.1% figure came from a logging error: the decode path divided the visited-block count by the number of query heads a second time, capping the reported value at 1/32. Independently, the stopping rule in the kernel used for generation benchmarks stopped far too late and visited about 99.5% of blocks. The timing harness uses a separate kernel without these errors, and a different workload (described under Q3), which is why its numbers disagreed. With both fixed, the method at eps = 1e-2 visits 46% of blocks on RULER32K-HARD and 52% on LongBench with Llama-3.1-8B-Instruct, and 14% and 17% at eps = 1e-1 for a loss of about 1 and 1.4 points.

2.68x vs. 1.20x. Neither number stands. The 1.20x came from a script that times one request per condition, prefill included, with the dense condition run first and no warm-up run. The kernel in that run was visiting nearly the whole cache, so the difference cannot come from sparsity. In a second run of the same script on Llama-3.1 that generated only 4 tokens, the gap was 14 s. The prefill is the same dense computation in both conditions, so that gap is a measurement artefact, not a decode speedup. The kernel-level speedups were measured against a dense baseline that materialises K and V with each KV head repeated once per query head, so it moves 4x more memory than a native grouped-query kernel would on the 7-8B models; against such a baseline we estimate no speedup at eps = 1e-2. We have not re-measured either.

Q1 (controlled comparison). We do not have the comparison you ask for. The only controlled result we now have is accuracy against density with vAttention on the same model and GPU. Our original vAttention baseline was misconfigured and ran dense attention. Configured as in its reference example (which includes an oracle top-k component), it matches its own dense baseline at 14-21% density on both benchmarks, so the claim that our method is sparser is incorrect. We have no latency, throughput or memory comparison against any sparse baseline.

Q3 (timing methodology). On prefill, Section 4.2 is correct that the dense 32K prefill is inside the full-model measurement; the statement in Section 5 that it is excluded is wrong. That measurement is a single request built from one RULER item truncated to 32K tokens, with 128 generated tokens. The kernel timing harness captures the KV cache of one middle layer on an 8K-token FineWeb-Edu context and times a single last-token query under CUDA graphs. Contexts of 16K to 128K are built by repeating that 8K cache, so they are not natural text at those lengths; the paper does not say this and should have. The 7-8B models and all benchmark runs used a single NVIDIA A40 (48 GB); the small models (Qwen2.5-0.5B, Qwen3-0.6B) used an RTX 4070 Ti.

Serving and memory. The paper does not evaluate continuous batching or paged KV caches. It states the index cost (about +25% of KV storage, roughly 20% smaller batch at fixed memory) but does not evaluate the trade-off: there is no matched-memory comparison, and the scan cost is not measured separately. In the exact-score mode used for our benchmarks, the first pass reads the full fp16 key cache, not the INT8 index, so only the output stage is sparse. The serving claims were not supported and need experiments we have not run.

The remaining tables were produced with the affected kernel and have not been rerun. We appreciate the questions; they were the right ones.

Reviewer_4GSSOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper proposes BnB-Attention, a training-free sparse-attention method that visits blocks in decreasing order of admissible score bounds and stops when the remaining attention mass is sufficiently small (§3, Algorithm 1). It develops a local error certificate (§3.1), compares three bound constructions (Table 1), and evaluates approximation quality, downstream performance, and decoding speed (§4).

Critical strengths

S1. The central residual-mass certificate is useful and appears sound (§3.1, Theorem 1; Appendix H). It provides an explicit bound on the error of an individual attention computation and falls back to dense attention when necessary (Theorem 2).

S2. The implementation and experiments suggest practical value. Table 1 shows tighter bounds from quantization, Table 3 reports performance close to dense attention on standard LongBench, and Tables 25–29 show kernel speedups of approximately 1.77–2.74× at 128K with ε = 0.01.

Critical weaknesses

W1. The writing does not adequately guide the reader, and inconsistencies make the argument difficult to assess.

A few examples

  1. The opening paragraph of §1 moves quickly across several method families and failure claims before developing a clear explanation of the problem.
  2. Section 3.1 then presents a succession of theorems and propositions without sufficiently explaining their dependencies, relative importance, or limitations. I frequently had to reconstruct how the method, guarantees, and experiments fit together. This is compounded by contradictions between the prose and results.
  3. The intro claims agreement with the oracle’s median error (§1, lines 94–96), but Table 2 shows substantial gaps. For example, 2.3e−4 versus 2.9e−7 on Llama LM@8K. Conversely, §5 says certification adds no accuracy over the heuristic, contradicting Table 2 and §4.1. Section 4.2 states that SnapKV preserves perplexity within ±0.01, whereas Table 6 reports 17.367/16.753 against dense 14.117. Sections 4.2 and 5 also disagree on whether the full-model timing includes prefill

W2. The theoretical novelty and scope of the guarantees are not established convincingly. Section 2 characterizes reference [14] as post-hoc analysis that does not determine when to stop reading keys. However, that work explicitly presents MC-Search (§7.2, Algorithm 2), which explores cells using score upper bounds and stops using a mass certificate. The paper needs to explain precisely what BnB adds beyond this closely related algorithm. Several additional claims also need qualification:

  1. Proposition 1 establishes optimality of the residual bound under specified conditions, not minimum stopping time.
  2. Proposition 5 compares worst-case upper bounds and does not establish pointwise quantization superiority.
Questions for authors

Q1. What are the precise algorithmic and theoretical advances over MC-Search in reference [14, §7.2, Algorithm 2]? How should the characterization of that work in §2 be corrected?

Q2. Can you provide the assumptions and missing proof details for Propositions 6–7, specify the floating-point guard’s constant, and clarify whether this guard was used in the evaluated kernels? This matters given the FP32 exceedances reported in Appendices C and N.

Q3. How were the hit rates and confidence intervals in Table 31 computed? Its stated 25 binary trials cannot directly produce the reported 90%, 86%, or 83% rates. Where are the 200-sample RULER results referenced in §4.4 and attributed to Appendix O?

1 comment

Thank you for the careful review. While addressing the reviews we found implementation errors that invalidate the paper's sparsity and speed claims, and we are withdrawing the submission. We still want to answer your points directly.

Errors found. The decode density was logged as the true density divided by the number of query heads (hence the 3.1% figure), and the stopping rule in the kernel used for generation benchmarks stopped far too late, visiting about 99.5% of blocks. After fixing both, the method at eps = 1e-2 visits 46% of blocks on RULER32K-HARD and 52% on LongBench with Llama-3.1-8B-Instruct, matching dense accuracy on the former and within 0.6 points on the latter. Our vAttention baseline was also misconfigured and ran dense attention; configured as in its reference example (which includes an oracle top-k component), it matches its own dense baseline at 14-21% density. The kernel speedups you cite from Tables 25-29 were measured against a dense baseline that reads 4x more memory than a native grouped-query implementation would, and we do not expect them to hold at eps = 1e-2.

W1 (writing and inconsistencies). You are right on each example. The introduction says the method matches the exact-score oracle "on the median" while Table 2 shows otherwise. Section 5 says certification adds no accuracy over the uncertified heuristic, which contradicts Section 4.1 and Table 2. The SnapKV statement in Section 4.2 contradicts Table 6. On prefill, Section 4.2 is correct that the dense 32K prefill is inside the full-model measurement, and the statement in Section 5 that it is excluded is wrong. We also accept that Section 1 and Section 3.1 do not explain how the results depend on each other or which ones matter.

W2 and Q1 (MC-Search). You are right that the statements "none of it decides when to stop reading keys" and "no prior training-free method" are wrong. MC-Search is a best-first, upper-bound method with a mass-certificate stopping rule. What we add is narrower: a termination proof, quantized block bounds, a floating-point analysis, GPU kernels, and evaluation at LLM scale. The paper should be positioned as building on MC-Search.

W2 (Propositions 1 and 5). We agree with both qualifications. Proposition 1 shows that, for fixed bounds and equal-size blocks, the descending order minimises the residual bound at each visited count; it does not show that the stopping time is minimal. Proposition 5 compares two upper bounds on looseness, so it does not show that the quantized bound is tighter pointwise; the "domination" title overstates it.

Q2 (Propositions 6-7). Proposition 6 assumes i.i.d. Gaussian keys and is asymptotic; the statement does not say in which limit, and the proof takes both the block size and the head dimension to be large. It is a model, not a guarantee about real keys. Proposition 7 has only a proof sketch and its constant c' is not specified. The guard is not implemented: the evaluated kernels apply the unguarded test, so Proposition 7 does not cover them. The FP32 exceedances in Appendices C and N (678 of 1,638,400 instances, up to 2.9e-4) are what the unguarded test produces. The "0 violations" counts are fp64 audits of captured activations, not checks of the fp16 kernels.

Q3 (Table 31 and the 200-sample RULER run). You are right that those rates cannot come from 25 trials. Table 31 prints the midpoint of the Wilson interval where it should print the hit rate. The actual rates are 24/25 = 96% (printed as 90 +/- 9), 23/25 = 92% (printed as 86 +/- 11) and 22/25 = 88% (printed as 83 +/- 13); the Mistral rows use 15 trials and are 15/15 = 100% (printed as 90 +/- 10). The 200-sample rerun cited in Section 4.4 and attributed to Appendix O is not in the submission; that reference is an error.

Thank you for the time you put into this.

Reviewer_PoCxOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes BNB-Attention, a training-free sparse attention method with a deterministic error guarantee. The authors model Sparse Attention as a Best-First Search: first, a permissible upper bound on the Attention Score is constructed for each KV block; then, the blocks are visited in descending order of this upper bound; and early termination is determined by estimating the maximum Softmax Mass of the remaining unvisited blocks. The authors further compare Min/Max, Ball and Quantised Bounds, finding that the former two are overly lenient, whilst the INT8 Bound—with an explicit quantisation error radius—significantly improves the efficiency of early termination.

Critical strengths

Existing sparse attention methods typically rely on heuristics to select a fixed number of KV blocks, making it difficult to guarantee that the skipped attention mass is sufficiently small. This paper adopts a permissible upper bound and adaptive termination criteria, providing deterministic error certificates on a per-query and per-head basis, whilst automatically degenerating to Dense Attention in the worst case.

The paper compares the tightness of different block bounds, demonstrating that Min/Max and Ball bounds are too lenient on real activations, whilst Quantised Bounds can significantly enhance the practicality of certified early termination. The experiments cover multiple models and long-context tasks, and include certificate-on/off comparisons and extensive appendix analyses.

Critical weaknesses

The paper repeatedly emphasises that, at ϵ=10−2\epsilon=10^{-2}, it is able to maintain performance close to that of Dense Attention with a KV Density of 3.1 per cent, and compares it with vAttention and fixed-budget methods on this basis. However, other experiments reveal markedly different actual access ratios. For example, in Table 8, the block sparsity for 7–8B models under the same ϵ\epsilon is only 22%–31%, whilst the actual access density is higher in certain Kernel Timing and NIAH settings.

Questions for authors

Could you please clarify the methodology used to calculate the 3.1% KV density, including the layers, heads, generation steps and KV ranges included in the calculation, and whether local or diagonal blocks are included?

Please clarify the specific implementation of the Dense Baseline, whether it supports native GQA, whether Split-KV is used, and the actual GPU memory bandwidth achieved.

1 comment

Thank you for the review. Your two questions led us to errors in both the density figure and the dense baseline, and we are withdrawing the submission to correct them.

Density (Q1). The 3.1% was produced by two errors. The decode path divided the per-head count of visited blocks by the number of query heads a second time, so the reported value was the true density divided by 32 for Llama-3.1 and could never exceed 1/32 = 3.1%. Separately, the stopping rule in the kernel used for all generation benchmarks accumulated per-block masses without a common normalisation and stopped far too late, visiting about 99.5% of blocks. Outputs remained correct, but those BnB columns were effectively dense runs.

The corrected figure is visited blocks over total blocks in the KV cache, pooled over all layers, query heads and decode steps. The diagonal block (the most recent block, containing the current token) is always visited and is counted. There is no fixed local window: all other blocks, including recent ones, are counted only when the search selects them. The prefill is computed densely and is not included. On Llama-3.1-8B-Instruct at eps = 1e-2 the figure is 46% on RULER32K-HARD (88.58 vs. 88.58 dense) and 52% on LongBench (42.75 vs. 43.32). At eps = 1e-1 it is 14% and 17% (87.63 and 41.89). This figure counts the blocks that enter the output. In the exact-score mode used for these runs, every key is additionally scored once per step, so it is not a measure of memory traffic.

Table 8 and the other settings. You were right that these disagreed with 3.1%. Table 8 is an offline audit on captured activations, and the kernel timing harness uses a different kernel; neither has the two errors. Its 22-31% block sparsity means 69-78% of blocks visited. The 0.995 visited fraction in the caption of Table 31 was the stopping-rule error showing directly.

Comparison with vAttention. Our vAttention baseline was also misconfigured and ran dense attention. Configured as in its reference example (which includes an oracle top-k component), it matches its own dense baseline at 14-21% density. The sparsity claims in the abstract and the comparison tables are therefore incorrect.

Dense baseline (Q2). It is stock PyTorch scaled_dot_product_attention with a single query in fp16 under CUDA graphs. It does not use split-KV, and in the kernel timing harness it is not native GQA: K and V are materialised with each KV head repeated once per query head (4x for the 7-8B models, 7x for Qwen2.5-0.5B), while our kernels read K and V in their native layout. From the recorded timings the baseline reads about 610 GB/s on the NVIDIA A40 for the 7-8B models and about 109 GB/s on the RTX 4070 Ti for Qwen2.5-0.5B, both measured on the expanded tensors.

The baseline therefore moves 4x more memory than a native-GQA kernel would. We estimate that such a kernel at the same throughput would take about 0.88 ms at 128K, against 1.3-1.7 ms for our kernel at eps = 1e-2, so the reported kernel speedups at that setting would not hold. We have not built that baseline, so this is an estimate. We also did not record which backend SDPA dispatched to, so the abstract's comparison to FlashAttention is not supported.

The remaining tables were produced with the affected kernel and have not been rerun. We are grateful that your questions exposed this.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.