- 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?
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.