acceptodds
Under review as a conference paper at ICLR 2027

Can Accurate Prediction Tell Sparse Attention What to Keep in LLMs?

Abstract

Sparse attention reduces long-document cost by passing only a few blocks to later computation. We ask whether accurate next-token prediction from one source identifies what a router should retain under distribution shift. In general, it cannot because labels from one source and unlabeled target documents can leave several deployment worlds compatible with the observations. Repeated facts and visible route positions also prevent a unique mask from being the right target. We characterize the resulting possible and necessary selector sets under a fixed retention budget and declared source, selector, predictor, and loss classes. Labeled source variation recovers the optimal set when suboptimal rules are uniformly separated in worst-source risk, and source mixtures give exact population certificates under convex predictor classes. Label-preserving masking gives a second route with multi-view and adaptive guarantees, whose cost is controlled by informative-example rates and squared performance gaps. Matching lower bounds clarify what extra data are needed before pruning long context and why predictive success alone does not establish causal evidence or computational savings.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large Language Models, Sparse Attention, Long-Context Modeling, Machine Learning Theory, Distribution Shift and Robustness

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_NiTSOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

A purely theoretical paper asking whether accurate next-token prediction on one source tells a sparse-attention router which blocks to keep under distribution shift. In general it does not. Recovery is possible when at least one labeled source breaks the shortcut and a clear gap holds, or when masking preserves the answer, and the paper gives the sample costs. There are no experiments.

Critical strengths
  1. A clear framing of a question that is usually assumed away, and a useful distinction between refitting the predictor and auditing a frozen one.
Critical weaknesses
  1. No experiments at all, and this is the main problem. The paper asks a question about LLMs but argues that experiments on a concrete LLM would only test whether an implementation fits its interface; the only figure plots theorem bounds, and the appendix examples are explicitly not empirical evidence. For this question, experiments are not optional. Without a single one we cannot tell whether the failure it proves actually happens in real sparse-attention models, whether key assumptions such as a clear gap between good and bad rules hold, or whether the sample costs are realistic.
  2. Little guidance for improving models. The results do not tell designers which blocks to keep or how to build a better router, so they offer little help in optimizing sparse-attention models.
Questions for authors
  1. Can you add some experiments: map an existing sparse-attention method onto your framework and measure the gap on a real model?
  2. Does the main conclusion hold for a frozen LLM in practice?
  3. How could your results be used to improve a new sparse-attention model, for example to decide which blocks a router should keep?
Reviewer_WMzBOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper asks: in large language models, can we tell which tokens sparse attention should keep by checking whether predictions are accurate? The authors treat token selection as an identification problem. They introduce the idea of compatible worlds to explain when a model's predictive behavior is enough to determine which tokens are necessary for keeping the model's output the same. They also use a minimax setup to choose sparse attention masks, and they work out the theoretical conditions under which accurate prediction can guarantee good mask selection. The paper also talks about the limits of this prediction-based identification: being accurate does not by itself tell you about evidence, causal importance, or computational efficiency. Finally, they run experiments on language modeling and downstream tasks to show the link between prediction quality and sparse attention performance.

Critical strengths
  1. This paper gives a useful new way to think about sparse attention: as an identification problem. It draws an important line between knowing that a prediction stays the same and knowing which tokens are actually responsible for that prediction. The idea of “compatible worlds” gives a clean way to make this distinction formal. This framework also helps explain why choosing tokens based on prediction can be fundamentally ambiguous.

  2. The theory also points out a key limitation of using prediction to guide sparsification. The minimax setup and its guarantees show exactly what extra assumptions are needed before prediction behavior can identify a reliable sparse mask. This matters because many sparse attention methods assume that if the prediction is preserved, then the kept tokens must be the right ones. The paper shows that these are logically different claims.

Critical weaknesses
  1. The paper’s main assumptions about identification may be much stronger than what we can actually verify in practice. The theory relies on the structure of the compatible-world set and on assumptions that predictive behavior is informative enough to identify which tokens matter. But if a model gives the same prediction under several different masks, that alone does not prove the removed tokens are unimportant. Different masks can lead to the same prediction while relying on different internal evidence or representations. So the theory may describe when identification is possible under the assumed world model, but it does not show that these conditions hold for real LLMs.

  2. The link from preserving predictions to real sparse-attention efficiency is still not well established. Preserving the final prediction is only one goal of sparse attention. A mask can keep output accuracy high but still cause large routing overhead, irregular memory access, or extra computation elsewhere in the network. Also, tokens that look unnecessary for one output may still matter for intermediate-layer computation or for robustness to perturbations. So evidence that predictions stay accurate under a mask does not by itself show that the mask is computationally efficient or generally safe.

Questions for authors
  1. The paper’s main guarantees depend on how the compatible-world set is defined. Which assumptions about compatible worlds can actually be tested on real LLMs? Can the authors run an experiment showing that these assumptions roughly hold for the models and tasks they evaluate? In particular, how often do very different token masks still give the same prediction?

  2. How does the framework separate predictive sufficiency from causal importance? If two masks give the same prediction, what stops the framework from calling both sufficient, even when one mask removes tokens that are causally important but simply redundant for that particular input and output? This distinction seems central to how the paper interprets “what to keep.”

  3. The paper argues that accurate prediction can help choose sparse-attention masks. What is the quantitative link between the proposed prediction criterion and real end-to-end efficiency? When masks have similar prediction accuracy, do they also have similar FLOPs, memory traffic, routing overhead, and wall-clock latency? If not, how should the minimax objective include computational cost?

  4. Are the prediction-based guarantees only about the final model output? Or do they also cover prediction changes under distribution shift, adversarial token removal, or different decoding paths? If the guarantee is instance-specific, what does it mean for autoregressive generation, where one early masking mistake can change all later predictions?

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

This paper investigates whether accurate next-token prediction can identify what sparse attention should retain under distribution shift. It characterizes possible and necessary selector sets and provides theoretical guarantees for recovering optimal selectors through labeled source variation and label-preserving masking.

Critical strengths

The paper provides rich theoretical insights into sparse attention, including partial identification of optimal selector sets, revealing source mixtures through labeled variation, and sample complexity bounds for masking.

Critical weaknesses
  1. The setting in Section 2, Eq. (2), allows each router to be paired with a separately optimized predictor, which differs from practical LLM settings where routers often operate with a fixed predictor. It remains unclear how well the theoretical results extend to such settings.

  2. The paper provides no empirical experiments, leaving it unclear whether the theoretical insights hold in practical LLM sparse attention settings.

Questions for authors

Could the authors empirically validate the theoretical results in a simplified setting, perhaps using a toy model, to demonstrate whether the theoretical insights hold in practice? For example, it would be interesting to examine whether the sample complexity empirically follows the dependence on the informative-example rate and performance gap predicted by Theorem 12.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Revisions and New Empirical Results

Dear Area Chair and Reviewers,

Thank you for your careful reading and constructive feedback. We appreciate the positive feedback on framing sparse attention as an identification problem, the theoretical results on compatible worlds, revealing source mixtures, and masking sample complexity, and the distinction between auditing a frozen predictor and refitting one.

In response to your feedback, we have made the following revisions.

  • Frozen predictors and identification. We have clarified how the guarantees apply to frozen predictors, when a selector chosen with a frozen predictor remains optimal after refitting, and which conditions can be checked in a labeled audit. In a controlled two-record experiment with frozen Qwen, changing only the target label rule reverses the preferred mask.
  • KV pruning and router selection. We have added a frozen-Qwen evaluation on RACE with actual KV pruning. At the same 64-position budget, the query-guided rule selected on separate validation data reduces held-out worst-source error by 2.78 percentage points relative to the recent window and 4.79 points relative to the first window. The comparison between the two positional windows remains unresolved on both sources.
  • Sample complexity. We have added bounded-loss simulations at a 5% sign-recovery error threshold. In these simulations, halving the informative-example rate roughly doubles the estimated sample requirement, and halving the conditional loss gap roughly quadruples it.
  • Efficiency and robustness. We have added end-to-end profiling, interventions on redundant evidence, and audits of KV deletion and eight-step decoding. On the profiled workload, pruning reduces estimated readout FLOPs and increases measured end-to-end latency.

Please refer to the latest PDF for the full set of revisions, experimental protocols, and results.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.