acceptodds
Under review as a conference paper at ICLR 2027

LISA: Head-Fused Linear Indexing for Efficient Sparse Attention

Abstract

Sparse attention reduces the cost of long-context inference by restricting attention to a small subset of tokens for each query. However, identifying this subset can still be expensive: the indexer in DeepSeek Sparse Attention (DSA) scores every visible token with multiple query heads, leaving substantial indexing overhead during long-context prefilling. We introduce LISA, a training-free indexer based on an exact decomposition of the weighted-ReLU score into a linear term and a nonlinear correction. Shared keys allow the linear contributions of all heads to be fused exactly into one dot product per token. LISA directly selects tokens using this linear term, omitting the nonlinear correction and removing the head-count factor from full-context scoring while preserving token-level granularity. LISA adds candidate refinement with the original multi-head scorer, while LISA shares candidate pools across layers with layer-specific refinement. Across 4K–128K contexts, LISA maintains RULER scores close to the respective native baselines on DeepSeek-V3.2 and GLM-5.2. On DeepSeek-V3.2 with a 1M-token input, LISA achieves a speedup over DSA in single-request offline time to first token, while LISA with four-layer groups achieves . These results support head-fused linear scoring as an efficient approximation to multi-head indexing for long-context prefilling.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Sparse Attention, Efficient LLM Inference, Long-Context Modeling, Attention Indexing, Head Fusion

Reviews

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

This paper proposes LISA, a training-free acceleration method for the token-level indexer in DeepSeek Sparse Attention. It decomposes the weighted-ReLU score into a linear term and a nonlinear correction, and exploits the shared-key structure to fuse the weighted queries from all indexer heads into a single query for full-context scoring. The paper further introduces candidate refinement and cross-layer candidate sharing, and reports substantial indexer and end-to-end TTFT improvements while maintaining similar RULER performance.

Critical strengths
  1. The core head-fusion idea is simple but practically meaningful. By exploiting the shared-key structure of the DSA indexer, LISA changes the cost of full-context token scoring itself rather than only reducing how often the original scorer is applied. This gives the method a clear distinction from several recent sparse-indexing approaches.

  2. The reported efficiency gains are substantial and translate to end-to-end inference. LISA reports a 6.12×6.12\times selector speedup and a 4.13×4.13\times TTFT speedup at 1M tokens on DeepSeek-V3.2, while LISA‡^{\ddagger} reaches 5.20×5.20\times. These are large enough to make the method practically relevant rather than only a kernel-level optimization.

Critical weaknesses
  1. The main novelty is concentrated in the head-fused linear scorer, while the refinement and cross-layer sharing extensions largely follow existing design patterns. Although LISA‡ reduces 1M-token TTFT from 113.49s to 73.67s compared with LISA† (Table 2), the paper does not report an end-to-end IndexCache comparison on DeepSeek-V3.2, despite including IndexCache in the quality evaluation. This makes it difficult to assess the advantage of shared candidate refinement over simpler cross-layer index reuse.

  2. The practical benefits of the refined variants are not fully established: at 128K on DeepSeek-V3.2, LISA† improves attention-mass recall from 86.26% to 89.41%, but RULER decreases from 94.82 to 94.37 and TTFT increases from 7.49s to 8.89s (Tables 2–4). LISA‡ further reduces recall to 87.24%, while the effects of the fixed candidate budget and layer-group size are not sufficiently analyzed. Moreover, quality evaluation stops at 128K, whereas the largest speedups are reported at 256K–1M.

Questions for authors
  1. Could the authors report the end-to-end TTFT of IndexCache on DeepSeek-V3.2 using the same four-layer grouping as LISA‡? This comparison would clarify the additional benefit of shared candidate refinement over direct index reuse.

  2. What is the practical motivation for LISA† when its higher recall does not translate into better RULER performance at 128K on DeepSeek-V3.2 (94.37 vs. 94.82), despite higher TTFT (8.89s vs. 7.49s)? Are there tasks or candidate-budget settings where the refinement produces a clear downstream benefit?

  3. Can the authors provide quality results beyond 128K, especially at 256K–1M where the efficiency gains are largest? This would help establish whether the approximation remains reliable at the context lengths central to the paper's motivation.

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

LISA addresses the cost of token selection in DeepSeek Sparse Attention. It decomposes the weighted-ReLU index score into a linear term and a nonlinear correction. Because indexer heads share keys, the weighted queries can be fused before scoring, so each token is scanned once. The decomposition and fusion are exact, but LISA approximates the original score by dropping the correction. It reuses pretrained parameters with a 2048-token selection budget. LISA† rescores a larger candidate pool with the original scorer. LISA‡ shares candidate positions across layers and keeps layer-specific rescoring.

Validation covers selector kernel latency on synthetic FP8 inputs, single-request offline TTFT, RULER (4K–128K), and attention-mass recall on DeepSeek-V3.2 and GLM-5.2. LISA‡ is evaluated only on DeepSeek. At 1M tokens on DeepSeek, TTFT drops from 383.16 s (DSA) to 92.72 s (LISA, 4.13×) and 73.67 s (LISA‡, 5.20×). GLM goes from 131.15 s to 67.67 s (1.94×). Average RULER scores barely change: 96.55 → 96.53 on DeepSeek and 97.56 → 97.42 on GLM. Quality is not evaluated at the lengths where the largest speedups are reported.

Critical strengths
  1. The method targets a real bottleneck without retraining the indexer. Eqs. (2)–(6) correctly exploit shared keys, including with signed head weights. The paper is careful to separate exact fusion of the linear term from the approximate selection that results from dropping the correction. This makes the speed/accuracy tradeoff easy to reason about, and the 1M-token TTFT gains (4.13× / 5.20× on DeepSeek) are large enough to matter in practice. The per-query scan is still linear in context, so prefill remains quadratic overall.
  2. The evaluation links kernel measurements to full-model TTFT and task scores on two models, and GLM keeps its native IndexCache schedule. The diagnostics are useful. Figure 2 shows that fusing all heads beats fixed and query-dependent single-head controls (86.26% vs. 49.89% / 54.72% recall at 128K). The authors also acknowledge that higher recall from refinement does not consistently improve RULER.
Critical weaknesses
  1. Speed and quality are reported at different context lengths. The headline gains are at 1M tokens, but RULER stops at 128K, where LISA’s speedup is only about 1.41× (DeepSeek) and 1.07× (GLM). The abstract states both ranges accurately. However, the paper’s main practical claim depends on quality holding at 256K–1M, and that is not shown. This is the main reason for my score.
  2. LISA lacks a matched baseline. Table 3 reports DeepSeek IndexCache (RULER 96.52, essentially equal to LISA’s 96.53), but Table 2 omits its TTFT. LISA combines head fusion with cross-layer candidate reuse. Its 5.20× gain over DSA therefore cannot be separated from what IndexCache alone would give. Since LISA† and LISA‡ largely reuse refinement and cross-layer rescoring ideas from prior work, this comparison matters for judging the contribution beyond the fused scorer.
Questions for authors

Could change my assessment:

  1. Can you report RULER (or another long-context task) at 256K–1M, using the same YaRN/context-extension settings as the TTFT runs?
  2. What is DeepSeek IndexCache’s TTFT with grouping matched to LISA‡ (G = 4)? Please report it alongside quality.
  3. Timing setup: which GPU model and software versions did you use, what was the warm-up procedure, how many runs underlie each median, and what is the variability? Please also give the actual YaRN settings and checkpoint revisions, and explain how the synthetic inputs for Table 1 were generated. Will code be released?
  4. How often is the recovery path in Appendix B.3 triggered, and what does it cost (iterations, actual candidate-count distribution, extra workspace)? How sensitive are speed and quality to M, C, and G?

Clarification: 5. Figure 4 uses a single 32K example with smoothed layer means. Across examples and layers, how large is the dropped correction, and how often does it change selection near the top-k boundary and the candidate-budget rank? With signed weights, the correction can go either way.

Suggestions (not affecting score): task-level RULER results with paired confidence intervals, a benchmark beyond RULER (document or code tasks), and recall at query positions other than the first question token.

7 comments

Thank you for the constructive review. We have revised the manuscript with 256K–1M evaluations, matched baselines, and diagnostic analyses, and address your questions below. Thank you also for the constructive suggestions on task-level uncertainty, broader benchmarks, and alternative query positions, which we address in A1 and A3. In the revised PDF, added or revised sentences and reference entries are marked in blue, and new or updated table entries are highlighted.

A1. Quality at 256K–1M (W1, Q1)

Our initial quality suite stopped at 128K because DeepSeek-V3.2 has a native 160K context window. Because the original 256K–1M timing runs used length-converted RoPE scaling factors (64/128/256) and beyond-native evaluation requires quality calibration, we selected fixed-length YaRN factors using Native DSA—choosing 98, 184, and 322 as the best-performing tested settings—froze them across all methods at 256K, 512K, and 1M, and re-measured offline TTFT under the identical factors (A2). GLM-5.2 natively supports 1M tokens without RoPE overrides; thus, 256K–1M quality conclusions primarily rely on native-1M GLM-5.2, while DeepSeek provides supplementary extrapolation evidence with residual calibration uncertainty.

The tables below report RULER accuracy (13 × 100 = 1,300 examples per cell, except DeepSeek 1M, which uses a fixed shared 13 × 20 = 260-example subset due to evaluation cost). All entries are complete and included in revised Table 3.

GLM-5.2 RULER accuracy (%, 13-task mean)

Method256K512K1M
Native96.2795.2681.12
LISA95.7891.8877.53
LISA†96.5894.8580.00

DeepSeek-V3.2 RULER accuracy (%, 13-task mean)

Method256K512K1M
Native DSA94.2692.4684.99
IndexCache-G483.1931.0124.10
LISA93.5288.1079.16
LISA†94.0890.6582.42
LISA‡85.5574.0566.62

Refinement improves RULER over plain LISA at all three 256K–1M lengths on both models; at 1M, scores rise from 79.16% to 82.42% on DeepSeek and from 77.53% to 80.00% on GLM.

Beyond RULER, we evaluated LongBench v2 on GLM-5.2 (503 shared inputs): Native scores 51.49%, LISA scores 51.09%, and LISA† reaches 53.28% (+2.19 pp over LISA); DeepSeek-V3.2 is omitted because variable prompt lengths lack a single calibrated YaRN factor. Revised Table 4 reports LongBench v2; Appendix C.2 includes task-level RULER scores at 128K and paired 95% bootstrap confidence intervals for the 4K–128K mean.

A2. Matched IndexCache comparison (W2, Q2)

We benchmarked DeepSeek IndexCache with the exact grouping of LISA‡ (G=4: layer 0 independent, remaining layers grouped in fours, k=2048). IndexCache reuses the donor layer’s final top-2048 indices directly, whereas LISA‡ shares the donor’s candidate pool (target M=8192) and applies each layer’s own exact scorer.

DeepSeek-V3.2 offline TTFT (s, median [min, max] across 3 runs)

Method256K512K1M
Native DSA30.82 [30.72, 33.18]105.18 [104.92, 108.56]374.79 [374.77, 374.80]
IndexCache-G416.01 [16.01, 16.05]43.50 [43.21, 47.70]130.44 [130.42, 130.48]
LISA16.78 [16.78, 16.79]37.31 [37.31, 37.33]92.66 [92.66, 92.70]
LISA†19.13 [19.13, 19.14]43.91 [43.90, 47.94]113.29 [113.27, 113.29]
LISA‡16.00 [16.00, 16.00]33.53 [33.53, 33.55]74.02 [73.90, 74.20]

Without cross-layer sharing (G=1), plain LISA achieves a 4.04× speedup over Native DSA at 1M and outperforms IndexCache-G4 at 512K and 1M. Under matched G=4 grouping, LISA‡ is 1.30× faster than IndexCache-G4 at 512K while improving RULER accuracy by +43.04 pp (74.05% vs. 31.01%), and is 1.76× faster at 1M while raising RULER from 24.10% to 66.62% on the shared 260-example subset (revised Tables 2–3; timing ranges in Appendix C.4, Table 10).

A3. Recovery cost and M/C/G sensitivity (Q4)

Recovery Path Overhead: We profiled recovery on ten selected 512K LongBench v2 inputs (five domains, two inputs each), using the same prompt IDs across DeepSeek LISA†, DeepSeek LISA‡ (G=4), and GLM LISA† under the archived diagnostic setup. A row is one query token at a candidate-building layer on TP rank 0. Aggregate trigger rates are 0.001294%–0.006061%; recovery-graph intervals occupy 0.102%–0.272% of selector CUDA time. Pooled candidate counts for visible prefixes > M have P50 8,280–8,293 and P95 9,746–9,839; triggered-row iteration P50/P95 are 11–12 / 12–13. Each workspace allocates a 256 MiB FP32 score cache per TP rank, with the number of workspace instances varying by input shape. Configuration details and per-method results are in Appendix D.4, Table 13.

Sensitivity to M, C, G: At 512K context, we evaluated 42-setting M/C grids (M ∈ {4096, 6144, 8192, 10240, 12288, 14336, 16384}, C/M ∈ {1.5, 2, 2.5, 3, 3.5, 4}) for DeepSeek-V3.2 (DS; fixed G=1, YaRN 184) and GLM-5.2 (GLM; native layer schedule), plus a 56-setting DS G/M grid (G ∈ {1, 2, 3, 4, 5, 6, 7, 8}, same seven M, C=2M, YaRN 184). Recall is attention-mass recall: selected-2048 attention mass divided by exact Top-2048 mass at the last real prefill query token, averaged equally over heads, layers, and 10 LongBench-v2 inputs per model. Timings are median offline TTFT from our dedicated ablation harness. The M/C and G/M sweeps are measured separately, so results at overlapping configurations may differ slightly.

512K M/C ablation (DS: G=1; GLM: native layer schedule; bold: default)

MC/MDS TTFT (s)DS recall (%)GLM TTFT (s)GLM recall (%)
4096245.0389.9531.3790.80
81921.547.7690.6132.1891.09
8192246.8790.6231.9891.09
8192446.7990.6231.9991.09
16384253.0091.0033.4591.29

512K DS G/M ablation slice (fixed M=8192, C=16384)

GTTFT (s)Recall (%)
146.8090.67
239.0588.56
336.5088.45
435.1786.63
534.4287.78
633.9586.43
733.6485.17
833.4384.42

Increasing M improves recall at higher TTFT, while increasing G trades recall for lower TTFT; recall is not strictly monotonic in G. Because C is a buffer cap, varying C/M ∈ [1.5, 4] at fixed M across the full 42-setting grids changes recall by at most 0.0431 pp on DS and 0.0062 pp on GLM. Appendices D.1–D.2 include the full grids, Pareto plots, and 128K GLM results (Figures 6–8 and Table 11).

A4. Correction magnitude and ranking changes (Figure 4)

Across eight independent 32K LongBench v2 documents and seven sampled layers (56 observations), the mean per-observation L2 norm ratio of the dropped correction to the full score is 34.50%, and the correction itself takes both positive and negative values. Comparing cross-boundary token pairs drawn from 128 ranks on each side of the linear-score cutoff (excluding linear-score ties), full scores reverse 46.78% of pairs near the top-k boundary (k=2048) and 48.63% near the candidate-budget rank (M=8192).

Candidate expansion and full-score refinement directly accommodate these rank changes. Whereas linear-only Top-2048 selection achieves 75.17% mean set overlap with the exact Top-2048, our threshold candidate constructor (target M=8192) achieves 99.32% mean coverage of the exact Top-2048 tokens, and subsequent full-score refinement within this pool recovers 99.32% mean Top-2048 set overlap (Appendix D.3, Table 12).

A5. Reproducibility and code release (Q3)

  • Hardware & Software: Table 1 used 1× NVIDIA GPU; Table 2 used 8× NVIDIA GPUs (TP=8, EP=8). Both timing setups used vLLM 0.26.0+litetopk.ad8e581, PyTorch 2.11.0+cu130, and CUDA 13.0. Timing runs used FP8 weights and KV cache, whereas 256K–1M quality runs used BF16 core KV cache (environment details in Appendix B.1).

  • Table 1 Kernel Protocol: Benchmarks the last Q=8192 causal queries (H ∈ {32, 64}, D=128, k=2048) using fixed-seed synthetic inputs (Q∼N(0, 0.3²), K∼N(0, 1) cast to fp8_e4m3fn, unit key scales, weights U(0, 1)/H). CUDA-event timings use 3 warm-ups and the median of 20 trials, covering the selector pipeline while excluding model projections, KV gather, and communication. Representative trial ranges are included in Appendix C.4 (e.g., H=64 at 1M: DSA 83.14–88.12 ms; LISA† 16.10–17.97 ms).

  • Table 2 TTFT Protocol: Measures offline LLM.generate wall-clock time on one pre-tokenized WikiText request (max_tokens=1, chunk size 8192, prefix caching off) with 1 excluded warm-up and the median of 3 runs (ranges in A2), excluding startup, weight loading, and tokenization.

  • Checkpoints & RoPE: DeepSeek-V3.2 (a7e62ac0) uses YaRN (base 4096, rope_theta=10000, beta_fast=32, beta_slow=1, mscale=mscale_all_dim=1.0). GLM-5.2-FP8 (f33c6dc5) uses native 1M RoPE (rope_theta=8,000,000).

  • Code Release: Kernel code, vLLM integration, and benchmark scripts will be open-sourced after acceptance.

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

This paper proposes LISA, a training-free replacement for the lightning indexer in DeepSeek Sparse Attention (DSA). The DSA indexer scores every visible key with H weighted-ReLU heads, so the cost of the full-context scan grows with the head count. Because all heads share the same key, the authors use ReLU(x) = x + ReLU(-x) to split the score into a linear term and a nonlinear correction. The linear term can be computed exactly with one dot product between each key and a head-fused query, and LISA selects the top-k tokens with this term alone. Two variants add a candidate-refinement step with the original multi-head scorer (LISA†) and share candidate pools across adjacent layers (LISA‡). The authors test them on DeepSeek-V3.2 and GLM-5.2 with RULER (4K to 128K), indexer kernel latency, and TTFT up to 1M tokens, and report a 4.13x (LISA) and 5.20x (LISA‡) TTFT speedup at 1M with RULER scores within 0.5 points of the native indexers.

Critical strengths
  1. The idea is simple and the decomposition is exact: the only approximation is dropping the nonlinear term. It needs no training, reuses the pretrained indexer and keeps the token-level interface to Sparse MLA, so it is easy to adopt. The kernel results (Table 1, 6.12x over DSA at 1M keys with 64 heads) and TTFT results (Table 2) show a clear gain over DSA and LiteTopK at long contexts.
  2. The paper is honest about what the approximation loses. Section 4.4 and Table 4 report the attention-mass recall gap (86.26 vs 89.96 at 128K on DeepSeek-V3.2), and Section 4.5 uses the decomposition to explain why the linear score is still a reasonable proxy. The method is reasonable and the paper is easy to follow.
Critical weaknesses
  1. The quality evaluation is limited. All accuracy results come from RULER (Table 3), where the native models already score 94 to 98 at every length, and the difference between LISA and the native baselines is below 0.5 points. The base model's performance on this benchmark is too high to be representative, so it says little about whether the approximation hurts, and the conclusion could be biased by this choice. Section 4.4 even says that LISA† has higher recall than LISA but does not consistently do better on RULER, which suggests RULER is not sensitive to the selection quality the paper tries to preserve. I would like to see at least one benchmark where the native model is not near ceiling (e.g., LongBench v2, which the authors already use for Figure 4). Without it, "maintains quality" is only weakly supported.
  2. The headline speedups are reported at lengths where quality is never measured. The abstract highlights 1M tokens (Table 2, with YaRN for 256K and above), but accuracy is only evaluated up to 128K. Table 4 shows recall dropping with length for every method, with the gap between LISA and DSA getting larger (from 0.30 points at 4K to 3.70 at 128K), so it is unclear what happens at 1M. Efficiency is also only measured for single-request offline prefill, and the conclusion leaves decoding and concurrent serving to future work. These claims should be scoped accordingly, or supported with quality results at the lengths where the speedup is claimed.

Overall, I think the method is useful and the main weakness is the evaluation, so I lean toward acceptance.

Questions for authors
  • Which GPUs (type, number) were used for Tables 1 and 2?
  • HISA in Table 3 drops to 60.87 at 128K on DeepSeek-V3.2, far below every other method. Was it run with the configuration recommended by its authors? If this is a reproduction problem, the comparison between token-level and block-level selection is less informative.
  • Are the RULER differences between methods distinguishable from run-to-run noise (100 examples per task)? Please report variance or confidence intervals.
  • Can you report any quality number at 256K or above (even recall, or a simple retrieval task)?
2 comments

Thanks the authors for the response. It has addressed most of my concerns, and I will keep my score as 3.

Thank you for your valuable feedback and for considering our responses. We are glad that our response has addressed most of your concerns. Your suggestions helped us strengthen the evaluation, and we believe the additional experiments and revisions have improved the paper. We appreciate your time and the constructive discussion.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of contributions and rebuttal updates

Dear Area Chair and Reviewers,

Thank you for your time and constructive feedback. We summarize our contributions and the three main areas addressed during the rebuttal below.

Core contributions

LISA is a training-free replacement for the DSA indexer that retains token-level granularity while removing the head-count factor from full-context scoring. LISA decomposes the weighted-ReLU score into a linear term and a nonlinear correction; shared keys allow all heads’ linear contributions to be fused exactly into a single dot product per token. Plain LISA omits the correction to approximate top-kk selection directly. For accuracy-sensitive settings, LISA† restores original multi-head scoring over a small candidate pool, while LISA‡ shares candidate pools across adjacent layers with per-layer rescoring.

Issues addressed during rebuttal

  1. Quality evaluation: To address concerns that quality evaluation was previously limited to RULER at up to 128K, we added 256K–1M RULER evaluations on both models, LongBench v2 evaluation on GLM-5.2, a controlled finer-block HiSA comparison, and uncertainty estimates. Native-1M GLM-5.2 serves as our primary long-context quality evidence, complemented by DeepSeek-V3.2 under calibrated YaRN extrapolation, with a shared 260-example subset at 1M. On GLM-5.2 LongBench v2, plain LISA closely tracks the native baseline (51.09% vs. 51.49%), while LISA† reaches 53.28%. Across 256K–1M RULER on both models, LISA† consistently improves over plain LISA.

  2. Efficiency and timing evaluation: To separate our algorithmic gains from layer reuse and extend evaluation beyond offline single-request settings, we added an IndexCache baseline with matched four-layer grouping (G=4G=4), online DeepSeek-V3.2 TTFT benchmarks across concurrencies 1–16, and detailed timing protocols. Under matched G=4G=4 grouping on DeepSeek-V3.2 at 1M, LISA‡ achieves a 1.76× offline TTFT speedup over IndexCache while achieving substantially higher RULER accuracy. The online measurements extend our latency evaluation to concurrent serving.

  3. Ablations and diagnostics: To clarify sensitivity to hyperparameters and approximation behavior, we added sweeps over candidate budget MM, workspace cap CC, and sharing group size GG, alongside analyses of the omitted nonlinear correction, rank perturbations, and recovery-path overhead. These diagnostics characterize the quality–latency trade-offs across LISA variants and clarify the roles of the main design choices.

These additions are included in the revised manuscript, with revised sentences and reference entries in blue and new or updated table entries highlighted. With approximately 24 hours remaining in the discussion period, we would greatly appreciate further feedback—including from reviewers we have not yet heard back from—and would be happy to clarify any remaining questions or concerns.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.