acceptodds
Under review as a conference paper at ICLR 2027

Ranking Is Not Support Selection: Exact Marginals and Certified Headroom for Sparse Attention in LLMs

Abstract

Long-context large language model (LLM) inference often reduces attention memory or bandwidth by retaining or fetching only a limited subset of cached tokens. A common abstraction is to score candidates independently, keep the Top-, and renormalize attention over the retained set. We ask a basic question: if those per-token scores were exact, would Top- recover the best -token support? In general, it does not. Even when every candidate is scored by its exact downstream singleton-deletion Kullback–Leibler (KL) divergence under the same next-token objective used to evaluate the retained set, an explicit Top-2 example incurs the KL of the optimal pair. The reason is structural: softmax renormalization makes the value of adding or replacing a token depend on which other tokens are retained. We derive the exact exchange identity and prove support-conditioned preference reversals for every . We then test this distinction by exhaustive support enumeration in softmax-attention heads of SmolLM2, Gemma-2-2B, and Qwen3.5-4B. At the primary budget, exact-singleton Top- leaves at least 10% relative headroom to the exact optimum within the same candidate universe in 55/60, 49/60, and 60/60 prompt–head cells, respectively. The effect persists across alternative candidate-universe constructions, while its magnitude varies substantially across models. Direct mechanism analysis observes the predicted support-conditioned reversals in nearly every substantial-headroom case. Finally, \SwapCert searches the same-budget one-swap neighborhood for a concrete witness of remaining headroom and detects 52/55, 48/49, and 57/60 exact positives at . These results separate two questions that can be conflated in sparse LLM inference: which tokens are important individually, and which fixed-budget set best preserves the downstream next-token distribution.

Primary area:
foundation or frontier models, including LLMs
Keywords:
large language models, sparse attention, KV cache, support selection, attention pruning, long-context inference, combinatorial optimization, softmax renormalization, exact marginal effects, risk of Top-K ranking

Reviews

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

The authors examine the problem of fixed-budget support selection in long-context LLM inference. Sparse attention and KV-cache methods typically score cached tokens independently, keep the Top-K, and renormalize softmax attention over the retained set. The authors ask whether this ranking abstraction recovers the best K-token support even when every candidate is scored exactly. To do so, they consider a single softmax-attention head at one decoding step. The sparse head output is hS=∑i∈Saivi/ASh_S = \sum_{i \in S} a_i v_i / A_S, with AS=∑i∈SaiA_S = \sum_{i \in S} a_i. Support distortion is measured by the downstream next-token KL L(S)=DKL(pD∥pS)L(S) = D_{KL}(p_D \| p_S), and each candidate is scored by its exact singleton-deletion effect dj=DKL(pD∥pD∖{j})d_j = D_{KL}(p_D \| p_{D \setminus \{j\}}). They show that the answer is negative in general: in an explicit Top-2 example, exact-singleton Top-K incurs about 133× the KL of the optimal pair. From the identity hS′−hS=aj(vj−hS)−ai(vi−hS)AS−ai+ajh_{S'} - h_S = \frac{a_j(v_j - h_S) - a_i(v_i - h_S)}{A_S - a_i + a_j}, they show that the value of swapping ii for jj depends on the current retained support. They then prove support-conditioned preference reversals for every K≥2K \geq 2, meaning no context-independent scalar ordering can represent all fixed-budget exchange preferences.

Based on this idea, they propose:

  1. SwapCert, a one-sided headroom diagnostic. It searches the one-swap neighborhood of a support, which contains K(M−K)K(M-K) supports instead of (MK)\binom{M}{K}, for a lower-KL witness. The authors prove that whenever SwapCert fires, the support has at least that much headroom relative to the exact candidate-universe optimum.

  2. Exhaustive support enumeration on real models. The authors intervene on the first and last heads of the deepest softmax layer of SmolLM2-1.7B, Gemma-2-2B, and Qwen3.5-4B, using 30 LongBench-E prompts. They evaluate all size-4 supports within a 24-token candidate universe. Exact-singleton Top-4 leaves at least 10% relative headroom in 55/60, 49/60, and 60/60 cells, although absolute KL gaps are small (10−410^{-4} to 10−310^{-3}). The effect is robust to the candidate-universe construction but varies strongly across models and budgets $K \in $ {2,3,52, 3, 5}.

  3. Diagnostic and behavioral evaluation. At ε=0.10\varepsilon = 0.10, SwapCert detects about 95% of headroom-positive cells. Top-1 next-token agreement with the dense model changes only rarely, and the few observed flips are corrected by both the best one-swap support and the exact oracle.

Critical strengths
  1. Ranging problem is well-observed. The study tests the best case for any independent per-token scorer, not a particular heuristic. The verifiable 133× counterexample, the exact exchange identity, and the support-conditioned reversal result explain why the failure is structural.

  2. The empirical protocol is careful and the claims are honestly scoped. The ε threshold, models, heads, prompts, and candidate-universe constructions are all examined. The authors explicitly limit their claims: headroom is relative to an M = 24 candidate universe, not the full context; results show replication rather than architecture invariance; SwapCert is a one-sided diagnostic rather than a serving method.

Critical weaknesses
  1. Needs to be examined with related works more deeply. Current examination weaks from baselines.

  2. As far as I understood from the paper:

    a. Only four top-1 flips are observed across all models (Fig. 3, right) b. Median Δ\Delta KL is relatively small (Table 1).

This means (as far as I see) that the practical significance and external validity are quite limited.

Questions for authors
  1. Weakness 2. All results also come from perturbing a single head at one decoding step with K=4K = 4 and M=24M = 24. Can you show that the analysis matters in realistic settings? For example, you could apply sparse selection to all heads and layers at larger budgets (K in the hundreds) and report multi-step or task-level metrics such as LongBench accuracy or perplexity.
1 comment

We thank the reviewer for the careful technical reading and for recognizing the strength of the objective-matched counterexample, exchange identity, and preference-reversal construction.

We substantially revised the full manuscript in response to all three reviews: the Introduction and contribution summary have been refocused (Section 1), related-work positioning sharpened (Section 2), theoretical and computational roles distinguished (Sections 3–4), experimental scope extended (Sections 5–6), and interpretation consolidated (Sections 7–8). The revision contains five clear figures and fully documented expanded experiments in Appendices L–M.

W1 — Related methods and comparative baselines.

Revised Section 2 now compares rank-based KV retention (H2O, StreamingLLM, SparQ, SnapKV, Quest), output-aware or value-aware selection (CriticalKV, AnDPro, DropKV), and set-aware optimization or budget allocation (BumbleBee, Trust the Mass, Ada-KV).

The new closest-comparison table distinguishes their fidelity objectives and mathematical roles.

In particular, DropKV studies a renormalized head-output criterion under geometric conditions, and Trust the Mass examines forced-weight subset reconstruction; our Proposition 1 tests the sufficiency of exact singleton-deletion scores for the same downstream KL objective used to evaluate the whole retained set.

The original controlled exact-ranking comparison is now prominent in Section 6.1: replacing attention Top-K with exact downstream-singleton Top-K reduces the joint-support KL in 38/120 cells, ties in 34/120, and increases it in 48/120, separating the accuracy of marginal importance information from the quality of its selected support.

W2 — Larger budgets, multiple heads/layers, and predictive outcomes.

The new controlled protocol (Section 5; Appendix L) evaluates K=128K=128 and K=256K=256 on 2,048-token inputs across SmolLM2-1.7B, Gemma-2-2B, and Qwen3.5-4B.

Dense prefill is followed by cached decoding with sparse active supports in all heads of the last three eligible full-softmax layers, over the same frozen 30-prompt panel per model.

We compare four matched-budget selectors—attention Top-K, geometric head-output singleton Top-K, recent, and sink+recent—and report absolute dense-reference KL in Section 6.3.

Paired KL and gold-answer NLL differences use 20,000 prompt-bootstrap resamples and are reported for all six model/budget configurations, including their confidence intervals.

For Gemma, geometric selection reduces mean dense-reference KL relative to attention selection by 6.68% at K=128K=128 and 9.77% at K=256K=256 (absolute differences −4.52×10⁻⁵ and −3.07×10⁻⁵).

Both exploratory paired KL intervals exclude zero; at K=128K=128, the reference-answer NLL is also lower by 0.00411 with interval [−0.00696, −0.00157].

The full table reports model-dependent effects for SmolLM2 and Qwen as well.

Separate larger-budget exchange screens find positive same-budget improvements in 39/72 configurations, with matched randomized controls reported in Appendix L.

The K=128K=128, 24-token generation diagnostic records actual greedy continuations, which agree between geometric and attention selection in 90/90 matched cases.

These data provide a more realistic characterization of distributional fidelity and observed decoding outcomes, complementary to the exact-support oracle analysis.

Decision-level bridge and broader exact audits.

The new Section 6.4 and Appendix M directly apply Proposition 3 to 180 exact behavioral cells: dense top-1 decisions are mathematically certified in 152/180 ranked supports, 159/180 best-one-swap supports, and 161/180 candidate-universe optima; the four observed ranked-support flips are all repaired by a best one-swap.

Appendix J additionally reports the existing approximately 2K- and 4K-context exchange screens over 1,512 heads / 48,384 exchanges and 504 heads / 16,128 exchanges, respectively.

Thus the revised paper combines exact global comparison inside M=24M=24 candidate universes with broader-budget, multi-layer predictive evidence and clearly labeled behavioral tests.

We appreciate the concrete experimental suggestions: they motivated major additions to the main text and supplementary evidence.

We respectfully invite the reviewer to reconsider the rating based on the strengthened comparisons, larger-budget multi-layer protocol, paired NLL/KL evidence, and certified decision-level analysis.

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

The author proposed the SWAPCERT method to search the one-swap neighborhood and return a witness when one exists above a chosen threshold. The SWAPCERT method is claimed to solve the objective-matched impossibility etc., providing more explainable results in QA.

Critical strengths

The author presents an interesting direction of the LLM research. I believe the authors are working on a good XAI topic.

Critical weaknesses
  1. The introduction can be more concise and more focus on the topic. The second paragraph and the third paragraph come up with some interesting thoughts, but they would be far away from the main idea of the work.
  2. The related work section does not cover all the "five gaps" discussed in the paper. In other words, these could be relative works, but not organized in the way this paper presented.
  3. The paper discusses several behaviors of the LLM. However, it is not clear what is the original contributions of this work, in terms of techniques.
Questions for authors
  1. I am not convinced that the "support" selected by measuring eq.3 would be practical. The assumption would be too strong in the open question tasks. Please explain how to handle a open question.
  2. Please summarize the technical contribution.
1 comment

We thank the reviewer for the specific suggestions on focus, related-work organization, technical novelty, and open-ended questions.

We have rewritten and reorganized the manuscript throughout: the Abstract and Introduction now state one focused question and four contributions (Section 1); Related Work is organized by the fidelity object and the form of its guarantee (Section 2); theory and the constructive certificate are separated clearly (Sections 3–4); the experimental protocol and results are more accessible (Sections 5–6); and the Discussion and Conclusion emphasize the scientific implications (Sections 7–8).

Five restored and clarified figures accompany these changes, and Appendices A–M provide the verifiable details.

W1 — Technical contribution.

The paper asks whether a scalar ranking remains sufficient when singleton importance is evaluated exactly under the same downstream objective as the selected support.

Four concrete results answer that question.

(1) Objective-matched impossibility. Section 3.2, Proposition 1, provides a fully checkable four-token example in which exact downstream singleton-deletion KL selects a size-2 support with 133.2× the globally optimal size-2 downstream KL.

(2) Support-conditioned preference reversal. Section 3.3, Eqs. (6)–(7) and Proposition 2, derives the support-dependent renormalized exchange value and establishes preference reversal between the same two candidate tokens for every K≥2K\geq2. The worked exchange reduces the example's KL by 99.25%.

(3) Constructive improvement certification. Section 4 and Theorem 1 turn the observation into SwapCert, a verifiable positive improvement witness over K(M−K)K(M-K) equally sized neighbors; the M=24,K=4M=24,K=4 audit compares 80 local evaluations with 10,626 exhaustive supports.

(4) Exact-model verification and broader-budget evidence. Sections 5–6 and Appendices C–M provide exact three-model support enumeration and broader-budget multi-layer evidence.

At K=4K=4, exact singleton Top-K has at least 10% relative candidate-universe headroom in 55/60 SmolLM2, 49/60 Gemma, and 60/60 Qwen cells, and SwapCert detects 52/55, 48/49, and 57/60 of these cases.

This connects the formal separation, its mathematical mechanism, and an evaluated constructive diagnostic.

W2 — Meaning of Eq. (3) on open-ended tasks.

For any open-ended prompt and current decoding prefix, the frozen dense model defines a next-token predictive distribution pDp_D.

Replacing a specified attention-head output with its restricted-support output yields pSp_S.

Equation (3) computes DKL(pD∥pS)D_{\mathrm{KL}}(p_D\Vert p_S) directly from the two distributions; an annotated answer is unnecessary for this offline fidelity measurement.

Section 3.4 derives the exact identity between this KL and the expected log-score difference when outcomes are drawn from pDp_D.

Proposition 3 further yields a decision-level guarantee: if KL is below half the squared dense top-1 probability margin, the dense next-token choice is preserved.

Section 6.4 and Appendix M verify the condition on every one of the 180 exact behavioral cells, certifying 152 ranked, 159 best-swap, and 161 oracle support decisions.

The best same-budget exchange also corrects all four observed dense top-1 changes.

W3 — How the objective is used computationally.

The exact downstream-KL evaluator serves as an offline, frozen-model reference for testing the quality of retained supports; Section 4 specifies the evaluation cost of both exhaustive and one-swap audits.

Section 5 then studies a lower-cost head-output geometric singleton score at K=128/256K=128/256 in multi-layer cached decoding.

The direct comparison with attention, recent, and sink+recent selection in Section 6.3, combined with gold-answer NLL and generated-output measurements, makes the diagnostic and practical evaluation roles concrete.

Section 2 and its closest-comparison table now place these results directly alongside prior head-reconstruction and set-aware selection approaches.

We hope the new organization, sharply stated contribution, checkable example, and detailed treatment of open-ended predictive fidelity address the reviewer's questions.

We respectfully invite the reviewer to reconsider the overall assessment based on this substantially revised manuscript.

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

The main issue studied in this paper is that even if a Top-K ranking is conducted based on the precise importance of single-point deletion, it is still not guaranteed to obtain the optimal token retention combination. The article verifies this phenomenon through theoretical counterexamples and exhaustive experiments on three models, and proposes SwapCert, which searches for specific evidence of potential improvement in the current combination through a single swap.

Critical strengths

S1: The paper focuses on the differences between the ranking of single-point importance and the optimal retention set, providing a meaningful perspective for understanding and evaluating the token selection strategy in sparse attention. S2: The paper clearly explains the structural reasons why single-point ranking cannot generally guarantee the optimality of the set through precise counterexamples, exchange identities, and preference reversals.

Critical weaknesses

W1: The paper mainly measures the effect using the KL divergence of the next word in the relatively complete model. However, a distribution that is closer does not necessarily mean a more accurate answer. I wonder if the problems discovered by the paper can provide guidance on the performance of downstream tasks? W2: I think SwapCert's core is to search for the single substitution neighborhood, and the certification guarantee directly comes from finding a better set with the same budget. The theoretical increment is relatively limited. I'm not sure if I have missed some content, so I would like to know what substantive new contributions SwapCert has in terms of algorithms or theory?

Questions for authors

see critical weaknesses

2 comments

We thank the reviewer for recognizing the soundness of the paper and the significance of the exact counterexample and support-conditioned mechanism.

In response to the reviews, we have substantially revised the manuscript throughout. The Abstract and Introduction (Section 1) now foreground a single research question; Related Work (Section 2) directly compares the closest objectives and guarantees; Sections 3–4 clarify the mathematical contribution and the operational meaning of SwapCert; Sections 5–6 present the expanded experiments and decision-level analysis; Sections 7–8 synthesize their implications; and Appendices L–M provide complete larger-budget and KL–margin audits. The revision also restores and clarifies five figures.

W1 — Predictive and downstream significance of KL.

We agree that a smaller next-token KL and a better answer are distinct observations, and have made their relationship precise.

Section 3.4 derives the exact expected-log-score identity for the dense-reference KL of Eq. (3), which is defined at any open-ended decoding prefix.

Proposition 3 proves a decision-level sufficient condition: if the dense top-token probability margin is mm and KL is below m2/2m^2/2, the intervened support preserves the dense top-1 token.

We evaluated that condition on every cell in the exact M=24,K=4M=24,K=4 behavioral panel (Section 6.4, the KL–margin table, and Appendix M). It certifies dense top-1 preservation in 152/180 exact-singleton supports, 159/180 after the best same-budget exchange, and 161/180 under the exact candidate-universe optimum. Of the four observed dense top-1 changes caused by exact-singleton support selection, all four are corrected by the best one-swap support and by the exact optimum.

We also added realistic-budget predictive measurements (Sections 5 and 6.3; Appendix L): 2,048-token prompts, K=128/256K=128/256, all heads in three late eligible full-softmax layers, and cached multi-step decoding.

Paired dense-reference KL and reference-answer token NLL are reported together with uncertainty. For Gemma-2-2B, geometric singleton ranking improves mean KL relative to attention Top-K at both budgets (differences −4.52×10⁻⁵ and −3.07×10⁻⁵; exploratory paired 95% intervals exclude zero), and improves reference-answer NLL at K=128K=128 (−0.00411, 95% interval [−0.00696, −0.00157]).

The complete six-setting table, alternative selectors, and K=128K=128 24-token generation measurements show both the distributional effects and the observed decoding behavior: geometric and attention ranking yield identical short greedy continuations on all 90 paired cases.

The paper thereby connects support selection to certified token decisions and measured reference-token likelihood while reporting decoded outputs directly.

W2 — The technical contribution and SwapCert's role.

Sections 3–4 now distinguish the underlying structural discovery from the local diagnostic.

Proposition 1 provides an objective-matched impossibility example: even exact downstream singleton-deletion KL selects a Top-2 support whose loss is 133.2 times the optimal pair's loss.

Equations (6)–(7) give the exact equal-budget exchange displacement, and Proposition 2 establishes support-conditioned candidate-preference reversals for every K≥2K\geq2.

A worked exchange in Section 3.3 reduces the counterexample's joint-support KL by 99.25%.

SwapCert uses this structure as a transparent, verifiable audit. Theorem 1 proves one-sided witness soundness, while Section 4 distinguishes 80 equal-budget neighbors from 10,626 globally enumerated candidate-universe supports at M=24,K=4M=24,K=4, with explicit downstream-evaluation cost accounting.

In the exhaustive three-model audit, SwapCert detects 157/164 pooled oracle-positive cases (52/55, 48/49, 57/60).

Section 6.2 and Appendix G further classify the seven missed cases as six threshold-limited improvements and one neighborhood-limited case.

The revision thus makes the central result—the exact ranking/support non-equivalence—and its constructive, independently testable consequence explicit, while strengthening its connection to predictive behavior.

We respectfully invite the reviewer to reconsider the assessment in light of these theoretical clarifications and new measurements.

Reviewer_JBXxOpenReview ↗

Response to author

Thank you for your reply, but it did not address my concerns. For W1, the author did not demonstrate that the token combinations discovered in the paper can be translated into improvements in downstream actual task performance. For W2, I still believe that SwapCert is equivalent to simple local exhaustive search, so there is no significant innovation. In addition, I would like to point out that the revised version of the paper submitted by the author does not seem to have used the template provided by ICLR for the review stage.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.