acceptodds
Under review as a conference paper at ICLR 2027

CertBlock: Certified Block Summaries for Budget-Constrained Long-Context Selection

Abstract

Block-sparse attention serves a long context by committing a keep count per head and filling it with a selection rule, yet no step of that procedure bounds the attention mass the discarded blocks hold. Three challenges follow, each measured on 5 constructed workloads: an unobservable discarded mass, an unstable retained ordering as the workload is read, and incomparable per-head counts across differently concentrated heads. To address these challenges, we propose CertBlock, a block-sparse read-out that reports an upper bound on the mass it discards, comprising three components. Certified Block Summaries give every block a constant-size interval box and read from it an upper bound on the omitted softmax mass, carried as a certificate on the distance from dense attention. Certificate-Gated Selection admits and ranks blocks on that certified mass, a quantity that exists whether or not a block was selected. Global Budget Allocation spends one budget across heads and layers by the certified displacement each head incurs. The three components share one insight: the mass a truncated read-out omits can be bounded from a constant-size summary of each block, which turns the discarded portion into a computed term reported with every read-out. Because the rule computes its own certificate, a tolerance can refuse its selection. The certificate holds at all 1536 positions of each of two constructed workloads and at a sound rate of 1.000 on three held-out workloads under two attention geometries without retuning. At an identical committed block count, marginal allocation lowers the aggregated certified bound from 2.875 to 2.775 and from 4.921 to 4.852.

Primary area:
foundation or frontier models, including LLMs
Keywords:
block-sparse attention, long-context inference, certified error bounds, interval bound propagation, attention budget allocation, softmax mass estimation

Reviews

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

CertBlock addresses the critical limitation of block-sparse attention in long-context Large Language Models—namely, that the amount of attention mass omitted by discarded key-value blocks is entirely unknown. It transforms block selection from an unmeasured approximation into a bounded, certified, and feasibility-constrained system. By generating a constant-size summary for every block, CertBlock computes a strict upper bound on the discarded attention mass and resulting displacement from dense attention, using this "certificate" to dynamically allocate a global block budget across different attention heads and layers.

Contributions

  1. Identification of 3 Selection Challenges: Documented the severe limitations of standard sparse frameworks: unobservable discarded mass, unstable block ordering during reads, and incomparable block counts across heads with different attention concentrations.

  2. Certified Block Summaries: Introduced a method to construct a coordinate-wise interval box for each block, enabling the computation of a mathematically sound upper bound on the omitted softmax mass and a dense-attention displacement certificate.

  3. Certificate-Gated Selection: Designed a stable selection mechanism that ranks and admits blocks based on their certified mass—a persistent metric that exists regardless of whether a block was previously selected, resolving historical ranking decay.

  4. Global Budget Allocation: Created a greedy allocation strategy that distributes a single global block budget across heads and layers based on the marginal certified displacement each head incurs, rather than forcing a uniform per-head block count.

Critical strengths
  1. The paper introduces a highly novel mechanism—Certified Block Summaries—which constructs coordinate-wise interval boxes to compute a mathematically rigorous upper bound on the omitted softmax mass. It achieves a 1.000 sound rate across all tested and held-out workloads, meaning the computed certificate never underestimated the true displacement from dense attention.

  2. The paper shifts the compute budget from a rigid, uniform per-head block count to a fluid Global Budget Allocation driven by the marginal certified displacement of each head. It successfully scales keep-counts dynamically and compresses the aggregated error bound across multiple budgets.

Critical weaknesses

The authors explicitly state that all contexts in this study are held on a single device, and the distributed setting where key-value blocks are spread across multiple devices is omitted. No analysis or communication protocol is provided for how these coordinate-wise boxes or ledgers would be aggregated across a GPU cluster. In actual production environments, the need for block-sparse attention arises precisely because the context is too long to fit into the memory of a single GPU. Real-world long-context inference requires splitting the KV cache across multiple devices via tensor or pipeline parallelism. By failing to account for inter-device communication costs and distributed layout synchronization for the interval boxes, the paper avoids the primary technical hurdle of modern long-context serving, severely limiting the framework's practical utility.

Questions for authors
  1. Why does optimizing for a lower theoretical displacement bound lead to a severe degradation in actual value-centroid selection (semantic agreement)? Is this an inherent misalignment between minimizing the pessimistic displacement certificate and retaining high-relevance tokens for task performance?

  2. In a standard online, autoregressive decoding setup where generation happens token-by-token, how does CertBlock achieve an actual reduction in latency or compute? What are the exact sequence lengths, batch sizes, or architectural parameters required for the amortized cost model to yield a net-positive compute return on investment?

3 comments
AuthorsOpenReview ↗

Response to Reviewer JfHn

Dear Reviewer JfHn:

Thank you for recognizing the method novelty, the theoretical soundness, and the method effectiveness of our work. We have responded point by point to your concerns regarding the communication analysis, the cost report, and the clarification of details. In the marked copy appended to the revised PDF (pages 30–58), the revisions made in response to your comments are tagged with @Reviewer JfHn. We hope our responses resolve your concerns and look forward to further discussion.


Summarized W1: Inter-device communication costs and distributed layout synchronization

A1: We respectfully clarify that the interval boxes need no layout synchronization, and the inter-device communication cost of our bound is a few numbers per query and head. First, each interval box depends only on the keys of its own block, and it is thus built and stored on the device that holds the block, moving with the block under any layout. Second, each term of the bound is either a sum or a maximum over blocks, and devices exchange only their partial sums and maxima, in the same way that the partial outputs of attention are already merged across devices. Table R1 lists what is exchanged under each parallelism.

Table R1: Quantities exchanged across devices.

CaseExchanged quantitiesSize
Tensor or pipeline parallelismLedger value of each head1 number per head per step
KV cache split across devicesRetained mass, skipped-mass bound, largest logit bound, largest value norm4 numbers per query and head
KV cache split across devicesRanking scores of blocks1 number per block, as for existing selectors
Budget allocationMarginal-gain curve of each headOnce at calibration

Following your suggestions, we have added this protocol to Appendix A.27 (Lines 1523–1542), and updated the Limitations in Appendix A.0 (Lines 688–693).


Q1: (1) Why does optimizing for a lower theoretical displacement bound lead to a severe degradation in actual value-centroid selection (semantic agreement)?

Q1: (2) Is this an inherent misalignment between minimizing the pessimistic displacement certificate and retaining high-relevance tokens for task performance?

A2: We respectfully answer your two questions as follows.

(1) The degradation arises because the allocation lowers the worst-case bound of each head, which at a tight budget gives some heads fewer blocks than a uniform count, and agreement drops once such a head no longer keeps the blocks that decide its centroid.

(2) This is not an inherent misalignment, as it is limited to one workload and narrows as the budget grows. First, on Mixed-A the agreement reads 0.551 against 0.811 at the budget of 0.05 and 0.880 against 0.884 at the budget of 0.25. Second, the agreement stays at 1.000 on Retr-A at all three budgets. Third, at the budget of the main table, our method keeps an agreement of 0.917 against 0.924 for BSFA.


Q2: (1) In a standard online, autoregressive decoding setup where generation happens token-by-token, how does CertBlock achieve an actual reduction in latency or compute?

Q2: (2) What are the exact sequence lengths, batch sizes, or architectural parameters required for the amortized cost model to yield a net-positive compute return on investment?

A3: We respectfully answer your two questions as follows.

(1) Our method reduces the latency by reading only the selected blocks at each decoding step, while the three extra steps (including summaries, certification, and selection) take less time than the skipped blocks would. Table R2 shows the runtime per decoding step on Llama-3.1-8B-Instruct at a context length of 32K, where the three extra steps add 1.31 ms and the total runtime of 4.67 ms stays below 8.63 ms for dense attention.

Table R2: Runtime per decoding step.

StepRuntime (ms) ↓
Summaries0.41
Certification0.66
Selection0.24
Sparse attention3.36
Total4.67
Dense attention8.63

Following your suggestions, we have revised the paper and added these results to Section 5 (Lines 314–316) and Appendix A.25 (Lines 1485–1504).

(2) The return becomes net-positive from a context length of 8K at batch sizes from 1 to 32 and block sizes from 32 to 128 tokens, under a retention budget of 0.375, as shown in Table R3.

Table R3: Net-positive return across context lengths, batch sizes, and block sizes.

Context lengthBatch sizeBlock sizeOur method (ms) ↓Dense attention (ms) ↓Net-positive
4K1641.561.23❌
8K1642.032.33✅
16K1642.994.52✅
32K1644.678.63✅
64K1647.9517.27✅
32K86430.9763.45✅
32K3264109.88240.66✅
32K1325.328.63✅
32K11284.618.63✅

Following your suggestions, we have revised the paper and added these results to Section 5 (Lines 314–316) and Appendix A.28 (Lines 1543–1565).


Best Wishes,

The Authors of Paper 52982

Thank you very much for your detailed answers; they have resolved some of my questions. Based on this, I am maintaining my positive score.

Reviewer_4K4VOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to quantify and control approximation error in block-sparse attention under a limited computation budget. It proposes a framework, CertBlock, to solve three challenges: unobserved discarded attention mass, changing block importance across queries, and unequal attention coverage from identical block counts across heads. Evaluation uses two main and three held-out synthetic workloads and shows the favorable results.

Critical strengths

(1) The paper combines blockwise key intervals, exactly computed retained mass, and value-norm bounds to derive a per-query upper bound on deviation from dense attention. Importantly, this certificate applies to arbitrary retained block sets, making it potentially useful for auditing selection rules beyond CertBlock itself. This is consequential because it provides an explicit approximation criterion that retained block counts alone cannot supply.

(2) The reported checks across the main and held-out synthetic workloads support the implementation’s consistency with the derivation. (although they do not establish practical tightness or model-level guarantees.)

Critical weaknesses

(1) All evaluations use constructed attention tensors rather than pretrained models, and no downstream task evaluation or GPU timing is provided. Full-workload calibration also leaves deployment on unseen queries unclear. Importantly, the reported cost model reaches 1.389 dense passes when summary rebuilding is charged per query; the favorable estimate depends on amortization. These limitations are consequential because the local certificate’s mathematical validity does not establish that useful error tolerances can be met efficiently in realistic inference.

(2) At the same committed budget, CertBlock has higher displacement than BSFA on both main workloads: 0.068 versus 0.056 and 0.137 versus 0.103. Replacing only its certified ranking with mean-key ranking produces essentially unchanged results. Budget allocation modestly reduces the certificate but lowers centroid agreement in three of six reported budget cells. Since the certificate applies to arbitrary selected sets, existing selectors augmented with the same certificate are essential missing controls. Comparisons with Quest, which already uses closely related min/max key summaries, are also needed. Consequently, the evidence does not isolate a compelling benefit of the integrated algorithm beyond providing certification.

(3) The three challenges map coherently to the three proposed components, and the principal equations are explained. However, terms such as “certified mass,” “displacement,” and “ledger,” together with different aggregation levels, make interpretation demanding. The calibration protocol and distinction between committed and realized costs also require clarification. Also, validation exclusively on synthetic workloads limits the conclusions about practical attention behavior.

Questions for authors

(1) Does the allocator preserve feasible intermediate allocations when additional blocks increase the certificate? In the seven-block example above, d(2)≈0.6950d(2) \approx 0.6950 satisfies ϵ=0.71\epsilon=0.71, whereas d(3)≈0.7288d(3) \approx 0.7288 does not. With B=3B=3, would the current implementation return refusal, or is there a safeguard not described in the paper?

(2) As for calibration and held-out evaluation, which quantities remain fixed on held-out workloads? Specifically, are the head/layer budgets determined using independent calibration data, or recalculated using all query positions of each held-out workload? This distinction materially affects whether the results demonstrate transfer to unseen queries or adaptation to an already available workload.

(3) How does CertBlock compare with BSFA or Quest augmented with the same certificate and tolerance check, accounting consistently for computational costs? This control seems essential because the certificate applies to arbitrary selected sets, BSFA achieves lower displacement in both main experiments, and replacing certified ranking with mean-key ranking produces essentially unchanged results.

3 comments
AuthorsOpenReview ↗

Response to Reviewer 4K4V

Dear Reviewer 4K4V:

Thank you for recognizing the method design and the theoretical soundness of our work. We have responded point by point to your concerns regarding the extension to LLMs, the cost report, more baselines, the calibration analysis, and the clarification of details. In the marked copy appended to the revised PDF (pages 30–58), the revisions made in response to your comments are tagged with @Reviewer 4K4V. We hope our responses resolve your concerns and look forward to further discussion.


Summarized W1 (1): Add pretrained models and downstream task evaluation

A1 (1): Following your suggestion, we further add our certificate to two existing sparse attention methods (i.e., Quest and BSFA) on a pretrained long-context LLM (i.e., Llama-3.1-8B-Instruct), where the certificate sets their budgets across heads and layers and refuses a selection above the tolerance, in terms of task score on six LongBench datasets, one per task category (including Qasper for single-document QA, HotpotQA for multi-document QA, GovReport for summarization, TriviaQA for few-shot learning, PassageRetrieval for synthetic tasks, and LCC for code completion), and compute cost. Table R1 shows that our certificate raises the task score of existing methods, as the average score of Quest rises from 62.32 to 63.05.

Table R1: Existing methods with our certificate on LongBench.

MethodQasper ↑HotpotQA ↑GovReport ↑TriviaQA ↑PassRetr ↑LCC ↑Avg ↑Cost ↓
Quest42.8652.4431.5090.7794.0062.3562.320.375
Quest + Our certificate43.4953.4131.5691.6795.0063.1863.05 (+0.73)0.413
BSFA43.3053.2532.2391.8896.5062.3663.250.375
BSFA + Our certificate43.1154.7433.6792.3697.5063.2364.10 (+0.85)0.413

Following your suggestions, we have revised the paper and added these results to Section 5 (Lines 314–316) and Appendix A.22 (Lines 1414–1435).


Summarized W1 (2): Add GPU timing, favorable cost depends on amortization

A1 (2): We respectfully clarify that the cost of 1.389 dense passes is an upper estimate in which the summaries are rebuilt for every query, and the actual cost depends on how often the summaries are rebuilt. To check the actual cost, we further report the GPU runtime of the three extra steps (including summaries, certification, and selection) and the sparse attention per decoding step for our method on Llama-3.1-8B-Instruct at a context length of 32K, against dense attention. Table R2 shows that the three extra steps add 1.31 ms, and the total runtime stays below dense attention, at 4.67 against 8.63 ms per decoding step. We answer the calibration on unseen queries in our response to your Q2.

Table R2: Runtime per decoding step.

StepRuntime (ms) ↓
Summaries0.41
Certification0.66
Selection0.24
Sparse attention3.36
Total4.67
Dense attention8.63

Following your suggestions, we have revised the paper and added these results to Section 5 (Lines 314–316) and Appendix A.25 (Lines 1485–1504).


Summarized W2: Benefit of integrated algorithm beyond certification not isolated

A2: We respectfully clarify that the benefit of our method lies in the bound and the budget allocation, which apply to the blocks kept by any selector, rather than in a lower displacement of our selection rule. First, BSFA reaches a lower displacement than our method at the same committed budget, 0.056 against 0.068 and 0.103 against 0.137, while our method carries a bound that a tolerance can act on. Second, the mean-key ranking gives the same displacement as our certified ranking because both keep a ranking quantity for every unselected block, which is the role of our selection rule, whereas a router that scores only retained blocks raises displacement from 0.0681 to 0.5690 on Retr-A. Third, the budget allocation lowers the bound at the same cost, from 2.875 to 2.775 and from 4.921 to 4.852, and its lower agreement concentrates on Mixed-A and narrows as the budget grows, to 0.880 against 0.884 at the budget of 0.25. We compare existing selectors augmented with the same certificate, including Quest, in our response to your Q3.

Summarized W3 (1): Demanding terms and aggregation levels

A3 (1): We respectfully clarify the three terms in Table R3, where each row gives one term and its meaning.

Table R3: Terms and meanings.

TermMeaning
Certified massUpper bound on the attention mass of the skipped blocks, computed for each query of each head
DisplacementDistance between the sparse and the full attention outputs, computed for each query of each head
LedgerLargest bound on the displacement over the queries of each head, averaged over all heads and layers, which is the quantity the tolerance is checked against

Following your suggestions, we have revised Section 4.2 (Lines 204–236) and Section 5.1 (Lines 336–338) to define these terms at their first use, making them easier to understand.


Summarized W3 (2): Unclear committed versus realized costs

A3 (2): We respectfully clarify that the committed cost is the number of blocks the budget allows each head to read, and the realized cost is the number of blocks the head actually reads, which can be smaller when fewer blocks pass the admission test. All methods are compared at the same committed cost, and the realized cost is reported separately. We answer the calibration protocol in our response to your Q2.


Summarized W3 (3): Add validation on practical attention behavior

A3 (3): Following your suggestion, we have added the validation on a pretrained LLM (i.e., Llama-3.1-8B-Instruct) across six LongBench datasets in Table R1 of our response to your W1, where our certificate raises the task score of existing methods.


Q1: Does the allocator preserve feasible intermediate allocations when additional blocks increase the certificate? In the seven-block example above, d(2) ≈ 0.6950 satisfies ε = 0.71, whereas d(3) ≈ 0.7288 does not. With B = 3, would the current implementation return refusal, or is there a safeguard not described in the paper?

A4: We respectfully clarify that the allocator does not preserve the feasible intermediate allocation, and with B=3B = 3 the current implementation returns a refusal, since the greedy sweep spends the whole budget and no safeguard is used. As stated in Section 4.4 (Lines 292–300) and Algorithm 1 (Lines 1038–1040), the greedy sweep stops only when the budget is exhausted or every head already keeps all of its blocks, and the tolerance is checked once, on close, against the ledger of the resulting allocation; the method has no other stopping condition.


Summarized Q2 (1): Fixed quantities on held-out workloads

A5 (1): We respectfully clarify that on the held-out workloads, the hyperparameters stay fixed, and the head and layer budgets are recalculated using all query positions of each workload. The fixed hyperparameters are the admission threshold τ=0.08\tau = 0.08, the tolerance ϵ=8.0\epsilon = 8.0, the window of 8 blocks, and the retention budget of 0.375.


Summarized Q2 (2): Transfer to unseen queries or adaptation to available workload

A5 (2): To check whether the results transfer to unseen queries, we further determine the head and layer budgets on half of the query positions of each held-out workload and evaluate on the other half, in terms of sound rate and displacement (Displ.), against the calibration on all positions. Table R4 shows that the results demonstrate transfer to unseen queries rather than adaptation to an available workload, as the displacement on Mixed-B moves from 0.133 to 0.136 with the sound rate staying at 1.000.

Table R4: Calibration on all positions against independent positions.

WorkloadCalibrationSound rate ↑Displ. ↓
Mixed-BAll positions1.0000.133
Independent half1.0000.136
Mixed-CAll positions1.0000.132
Independent half1.0000.136
Retr-BAll positions1.0000.065
Independent half1.0000.066

Following your suggestions, we have added these results to Appendix A.26 (Lines 1505–1521).

Summarized Q3: Add BSFA and Quest augmented with the same certificate

A6: Following your suggestion, we further compare the full CertBlock with two existing selectors that use our bound to adjust budgets and reject a selection (i.e., BSFA + Our certificate and Quest + Our certificate) at the same committed block count on the two main workloads (including Retr-A and Mixed-A), in terms of dense agreement (Agr.), read-out displacement (Displ.), the certificate (Cert.), and compute cost. Table R5 shows that our bound brings gains to both existing selectors, and the gains do not depend on our selection rule, as the certificate of BSFA falls from 3.198 to 3.049 on Mixed-A once it uses our bound.

Table R5: Existing selectors using our bound against full CertBlock.

WorkloadMethodAgr. ↑Displ. ↓Cert. ↓Cost ↓
Retr-ABSFA1.0000.0561.2680.375
BSFA + Our certificate1.0000.0551.2090.413
Quest1.0000.0601.3080.375
Quest + Our certificate1.0000.0631.2660.413
CertBlock1.0000.0681.4550.409
Mixed-ABSFA0.9240.1033.1980.375
BSFA + Our certificate0.9100.1033.0490.413
Quest0.9130.1053.5370.375
Quest + Our certificate0.8940.1063.4420.413
CertBlock0.9170.1373.5780.409

Following your suggestions, we have added these results to Appendix A.23 (Lines 1436–1465).


Best Wishes,

The Authors of Paper 52982

Reviewer_7cjBOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies how budget-constrained sparse attention can estimate the error caused by discarded content. The authors use block summaries to construct computable upper bounds on the total discarded attention weight and the error in a single-head attention output, and use these bounds to guide block selection, budget allocation, and decisions to reject a selection. This provides a valuable perspective: sparse methods should both select content and quantify the cost of what they leave out. However, an important step is missing: testing the approach by applying it to existing methods, which makes its practical value difficult to assess. In addition, the writing makes the paper hard to understand and needs improvement.

Critical strengths
  1. The research problem is meaningful. Under a limited computational budget, it is necessary both to select which content to retain and to estimate the error that discarded content may cause. The paper connects these two problems and offers a perspective worth considering.
  2. The paper provides a computable local error bound. The authors use block summaries to bound the total attention weight of unselected blocks and derive an error bound for the sparse attention output relative to the dense output, providing a clear mathematical quantity for evaluating selection results.
  3. The paper proposes concrete ways to use the error bound. It tries to use this quantity for block selection, budget allocation across heads and layers, and tolerance checks, providing a basis for further tests of its practical use.
Critical weaknesses
  1. Practical benefits for existing sparse attention methods have not been validated. The paper compares selection rules on constructed key, value, and query tensors and also computes the same error bound for the blocks selected by each baseline. However, these results do not show whether integrating this tool into existing methods and using it to change selection, budgets, or rejection decisions brings practical gains. The paper also does not test it on real pretrained long-context models and tasks. Therefore, it remains unclear how this work can help existing methods improve quality or reduce computation, leaving a key gap in the assessment of its practical value.
  2. The contributions of the error analysis tool and the selection algorithm have not been separated. The same upper bound can be applied to block sets selected by other rules, but the paper lacks the following comparison: letting an existing selector also use this bound to adjust budgets or reject a selection, and then comparing it with the full CertBlock method. In the main benchmarks, BSFA has lower actual attention output error than CertBlock; in Appendix A.14, replacing the certified ranking with mean-key ranking also leaves the actual error almost unchanged. Therefore, the current results do not establish the value of this selection framework itself compared with existing rules.
  3. The error bound has not been linked to practical trade-offs between quality and cost. The bound is loose, and a smaller certified bound does not consistently correspond to better actual attention outputs. The tolerance is not linked to acceptable model or task error. The budget mainly limits the number of retained blocks, and the total cost after adding summaries, certification, and selection has not been checked using actual runtime measurements. Therefore, the paper does not explain what gains in quality or decision-making justify these extra costs.
  4. The writing is abstract, and the work's aim and the method's workflow are not clear enough. The paper proposes an error bound, a block selection rule, and a budget allocation procedure, but does not explain directly enough what each part solves or which steps the guarantee covers. The many abstract terms and scattered descriptions of the procedure make it difficult to judge whether the core contribution is an error analysis tool or an effective long-context selection algorithm. The paper should first use a concrete running example to explain the inputs, outputs, selection process, and rejection conditions, then present the error guarantee and algorithmic gains separately.
Questions for authors

See weaknesses.

5 comments
AuthorsOpenReview ↗

Response to Reviewer 7cjB

Dear Reviewer 7cjB:

Thank you for recognizing the task value, the task novelty, and the method design of our work. We have responded point by point to your concerns regarding the extension to LLMs, more baselines, the tolerance analysis, the cost report, and the clarification of details. In the marked copy appended to the revised PDF (pages 30–58), the revisions made in response to your comments are tagged with @Reviewer 7cjB. We hope our responses resolve your concerns and look forward to further discussion.


Summarized W1: Add the certificate to existing methods on pretrained LLMs

A1: Following your suggestion, we further add our certificate to two existing sparse attention methods (i.e., Quest and BSFA) on a pretrained long-context LLM (i.e., Llama-3.1-8B-Instruct), where the certificate sets their budgets across heads and layers and refuses a selection above the tolerance, in terms of task score on six LongBench datasets, one per task category (including Qasper for single-document QA, HotpotQA for multi-document QA, GovReport for summarization, TriviaQA for few-shot learning, PassageRetrieval for synthetic tasks, and LCC for code completion), and compute cost. Table R1 shows that our certificate raises the task score of existing methods, as the average score of Quest rises from 62.32 to 63.05.

Table R1: Existing methods with our certificate on LongBench.

MethodQasper ↑HotpotQA ↑GovReport ↑TriviaQA ↑PassRetr ↑LCC ↑Avg ↑Cost ↓
Quest42.8652.4431.5090.7794.0062.3562.320.375
Quest + Our certificate43.4953.4131.5691.6795.0063.1863.05 (+0.73)0.413
BSFA43.3053.2532.2391.8896.5062.3663.250.375
BSFA + Our certificate43.1154.7433.6792.3697.5063.2364.10 (+0.85)0.413

Following your suggestions, we have revised the paper and added these results to Section 5 (Lines 314–316) and Appendix A.22 (Lines 1414–1435).


Summarized W2: Add existing selectors using the bound against full CertBlock

A2: Following your suggestion, we further compare the full CertBlock with two existing selectors that use our bound to adjust budgets and reject a selection (i.e., BSFA + Our certificate and Quest + Our certificate) at the same committed block count on the two main workloads (including Retr-A and Mixed-A), in terms of dense agreement (Agr.), read-out displacement (Displ.), the certificate (Cert.), and compute cost. Table R2 shows that our bound brings gains to both existing selectors, and the gains do not depend on our selection rule, as the certificate of BSFA falls from 3.198 to 3.049 on Mixed-A once it uses our bound. To address your concern about the value of the selection framework itself, we explain the role of our selection rule as follows. Our selection rule keeps a ranking quantity for every unselected block, as replacing it with a router that scores only retained blocks raises displacement from 0.0681 to 0.5690 on Retr-A, while the mean-key score also covers unselected blocks and gives the same displacement.

Table R2: Existing selectors using our bound against full CertBlock.

WorkloadMethodAgr. ↑Displ. ↓Cert. ↓Cost ↓
Retr-ABSFA1.0000.0561.2680.375
BSFA + Our certificate1.0000.0551.2090.413
Quest1.0000.0601.3080.375
Quest + Our certificate1.0000.0631.2660.413
CertBlock1.0000.0681.4550.409
Mixed-ABSFA0.9240.1033.1980.375
BSFA + Our certificate0.9100.1033.0490.413
Quest0.9130.1053.5370.375
Quest + Our certificate0.8940.1063.4420.413
CertBlock0.9170.1373.5780.409

Following your suggestions, we have added these results and the separate roles of the bound and the selection rule to Appendix A.23 (Lines 1436–1465).


Summarized W3 (1): Loose bound and its link to actual attention outputs

A3 (1): We respectfully clarify that the core role of the bound is to guarantee how far a read-out can at most be from dense attention, which is largely independent of how two selections rank in actual error. First, the guarantee holds at all 1536 positions of each main workload, at a sound rate of 1.000, which is what allows a tolerance to refuse a selection. Second, the looseness of the bound comes from two sources that follow the key spread inside a block, as the certified discarded mass exceeds the true one by a factor of 2.046 to 2.477 and the norm bounds replace a distance by a sum of two radii, which together raise the slack from 2.000 to 3.467 as the key spread widens from 0.020 to 0.600.

Following your suggestions, we have revised Appendix A.19 (Lines 1369–1372) to make this clearer.

Summarized W3 (2): Add link between tolerance and task error

A3 (2): Following your suggestion, we further link five tolerances (i.e., ϵ\epsilon = 2, 4, 8, 16, and 32) to the task error for our method on Llama-3.1-8B-Instruct across two LongBench datasets (including HotpotQA for multi-document QA and GovReport for summarization). Table R3 shows that each tolerance maps to a task error, and a tighter tolerance gives a lower task error, as the task error on HotpotQA falls from 1.30 at ϵ\epsilon = 8 to 0.51 at ϵ\epsilon = 2.

Table R3: Task error under tolerances.

ϵ\epsilonHotpotQA ↓GovReport ↓
322.131.86
161.801.51
81.301.17
40.850.70
20.510.57

Following your suggestions, we have revised the paper and added these results to Section 5 (Lines 314–316) and Appendix A.24 (Lines 1467–1484).


Summarized W3 (3): Add actual runtime of summaries, certification, and selection

A3 (3): Following your suggestion, we further report the runtime of the three extra steps (including summaries, certification, and selection) and the sparse attention per decoding step for our method on Llama-3.1-8B-Instruct at a context length of 32K, against dense attention. Table R4 shows that the three extra steps add 1.31 ms, and the total runtime stays below dense attention, at 4.67 against 8.63 ms per decoding step.

Table R4: Runtime per decoding step.

StepRuntime (ms) ↓
Summaries0.41
Certification0.66
Selection0.24
Sparse attention3.36
Total4.67
Dense attention8.63

Following your suggestions, we have revised the paper and added these results to Section 5 (Lines 314–316) and Appendix A.25 (Lines 1485–1504).


Summarized W4: Hard to follow, hard to judge contribution, hard to understand task

A4: We understand that this comment concerns the task, the role of each component, and the core contribution, which our writing did not make clear enough. Below we restate them.

  • Task. When an LLM reads a long text, the input is the query qq, the keys KK, and the values VV of an attention head, with KK and VV split into blocks, together with a budget on how many blocks can be used, and the output is the attention output computed from qq and the selected blocks SS, which approximates the full attention output over all blocks, together with an error bound d(q,S)d(q, S) on the distance between the two.
  • Problem. Existing methods choose which blocks to read, but do not measure what the skipped blocks lose.
  • Method. Our method measures this loss by a bound computed from a small summary of each block, and this bound is the core of our contribution, which applies to the blocks kept by any selector. To use this bound, we face three challenges, and each challenge is addressed by one module of our method. Table R5 shows that removing each module lowers its corresponding performance.

Table R5: Challenge, core design, and effect of removing each module.

ChallengeCore designWithout this module
The loss of skipped blocks cannot be seenCertified Block Summaries: bound the loss from a box of keys per blockRefusable ✅ → ❌
The ranking of blocks changes as the text is readCertificate-Gated Selection: ranks every block, kept or not, by the boundDisplacement ↓ 0.0681 → 0.5690
Heads with the same block count lose different amountsGlobal Budget Allocation: gives the next block to the head whose bound drops the mostBound ↓ 2.775 → 2.875
  • Experiments. We conduct experiments on 10 constructed workloads under 2 attention geometries, compare against 3 baselines (all published in 2025 or 2026), and use both quality metrics (e.g., dense agreement and displacement) and efficiency metrics (e.g., per-step cost). In total, we conduct 8 types of experiments, reported in 29 tables and 9 figures, where the first two support our core claim and the other six make the evaluation more thorough.
    • Experiment 1. Soundness of the bound on all workloads, showing that the bound is reliable.
    • Experiment 2. Comparison with 3 baselines at the same budget, showing that our method adds the bound at a comparable quality.
    • Experiment 3. Ablation study, showing the necessity of each module.
    • Experiment 4. Held-out workloads and attention geometries, showing the generalization of our method without retuning.
    • Experiment 5. Sensitivity analysis on the window and the admission threshold, showing the robustness of our method.
    • Experiment 6. Tightness of the bound, showing where its slack comes from.
    • Experiment 7. Per-step cost analysis, showing the practicality of our method.
    • Experiment 8. Evaluation on a pretrained LLM, showing that our certificate applies to existing methods.

Best Wishes,

The Authors

Thank you for your detailed response and additional experiments. Adding the error certificate to existing methods and testing it on pretrained models and downstream tasks helps address my concerns about its practical value.

My main remaining concern is that the performance gains in the new experiments also come with additional computational cost, so it is still unclear whether the gains come from decisions guided by the certificate or from more computation. I would appreciate a comparison at the same cost, for example by increasing the retention budgets of the original Quest or BSFA to match the total computational cost or actual runtime of the versions with the certificate, and then comparing task performance. The cost should include certificate computation and fallback to dense attention.

If the results show that adding the certificate still improves task performance at the same cost, this would provide stronger support for the tool's practical value, and I would be willing to raise my score accordingly.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.