SPIN: Shadow Predictive Indexer for Sparse Attention

1. Introduction

• Because the indexer scores each context token and scales linearly with context length, it remains a major contributor to decode latency at very long contexts.The passage gives 512K–1M tokens as examples; DeepSeek-V4’s token-level compressor reduces DSA context length by 4× but does not change that scaling.Source: §1 · p. 1
• Previous-iteration indexer scores correlate more strongly with current scores than previous-layer signals, motivating SPIN’s history-based block predictions.SPIN uses per-request statistics from prior decoding iterations; random exploration refreshes skipped blocks, which otherwise receive no score updates.Source: §1 · p. 1
• At 30–40% block sparsity, SPIN preserves comparable task quality; vLLM output throughput improves by up to 14.9% and median inter-token latency falls by up to 13.2%.Evaluations cover long-context benchmarks and the tau2-airline agentic benchmark.Source: §1 · p. 1
• The contributions include comparing prediction and exploration methods, evaluating native multi-token prediction verification, and testing whether exploration recovers task quality at the same block budget.SPIN is training-free and adds no auxiliary layers or networks.Source: §1 · pp. 1–2

2. DSA Indexer Patterns and Prediction

• The selection masks show vertical lines and diagonal bands in DeepSeek-V3.2, while DeepSeek-V4 exhibits mostly vertical patterns.Vertical lines indicate repeated selection of the same tokens across iterations; diagonal bands resemble RoPE-associated slash patterns.Source: §2 · p. 2, Figure 1 · p. 2
• The comparison tests predictors using scores from previous layers in the same iteration or from the same layer in a previous iteration.The profiling evaluates score correlation and top-K recall, averaging results over layers and decode iterations.Source: §2 · pp. 2–3, Table 1 · p. 3
• Across contexts from summscreenfd to AA-LCR, whose length increases by a factor of 9.7, previous-iteration prediction is most accurate and largely maintains top-K recall while random-baseline recall drops proportionally.Previous-layer prediction works better on DeepSeek-V4 than on DeepSeek-V3.2 but lags previous-iteration prediction on both models.Source: §2 · p. 3
• SPIN is motivated by the prediction results and uses per-layer statistics accumulated across prior decode iterations to predict block importance.Source: §2 · p. 3

3.1. Overview

• SPIN uses vertical and diagonal exponential moving averages, max-pools predicted token scores into KV-block scores, and reserves part of the block budget for random exploration.These three extensions capture longer-term patterns, enable block-level selection, and refresh observations of skipped blocks.Source: §3.1 · p. 3

3.2. Spin Algorithm

• For DeepSeek-V4, each slot is a compressed token; SPIN max-pools its two EMA predictions within each block, then scores selected blocks before the original top-K selection.The selected-block count is at least ⌈K/b⌉ to provide capacity for K slots, and the post-indexer top-K operator still selects slots for core attention.Source: §3.2 · pp. 3–4

3.2.1. Staleness Mitigation

• Skipped blocks receive no EMA updates, so an important slot in one may have stale statistics; random exploration refreshes skipped blocks without increasing the selected-block budget.Exploration reserves part of the existing budget, with the explored blocks receiving fresh indexer scores and EMA updates.Source: §3.2 · p. 4, §3.2.1 · p. 4

3.2. Spin Algorithm

• SPIN resets its EMA state after prefill and at each new turn, runs the first decode iteration without pruning, retains sink and newest active blocks, and can overlap prediction with other layers.The reset and initialization details are practical steps omitted from Algorithm 1.Source: §3.2 · p. 4

3.2.2. Speculative Decoding

• For speculative decoding, SPIN predicts a block mask for each verifier query and uses their union as the shared indexer-input mask because adjacent-query masks overlap substantially.A speculative draft of length d produces d + 1 verifier queries, sharing the context KV cache but using different query positions and hidden states.Source: §3.2.2 · p. 5
• After verification, SPIN replays EMA observations for rows 0 through the number of accepted draft tokens and discards observations from the remaining rows.The design is evaluated with DeepSeek-V4’s native MTP implementation.Source: §3.2.2 · p. 5

4.2. Long-context Benchmarks

• Across 20–50% target sparsity, LongBench-v2 exact-match scores on DeepSeek-V4 Flash and Pro differ from all-keep by at most 2.6% in relative terms.The evaluation increases the maximum output length from 128 to 1,024 tokens to reduce output truncation.Source: §4.2 · p. 6, Table 2 · p. 6
• At 50% sparsity, RULER task-score degradation is 1.24 points (1.4% relative) despite a 48.83% p99 miss; AA-LCR scores differ by at most 2.4 points (3.7% relative) across 20–50% sparsity.AA-LCR scores show no monotonic decrease, while RULER scores decrease slightly and monotonically as miss rates increase.Source: §4.2 · p. 6, Table 3 · p. 6
• On MRCRv2, random exploration substantially narrows a reported gap up to 50% target sparsity, despite variation across runs; Table 4 compares task scores with 5% random exploration against no exploration.Table 4 scores average 40 repeats over 100 fixed prompts per context bin.Source: Table 4 · p. 6, §4.2 · p. 7

4.3. Agentic Benchmarks

• On tau2-airline, SPIN has no task-score degradation at 30% target sparsity; at 50%, the score falls 4.1% relative to all-keep despite 25.7% mean miss.On Terminal-Bench 2.1, SPIN at 40% target sparsity matches the all-keep score, 62.5%, though a few tasks produce substantially longer agent trajectories.Source: §4.3 · p. 7, Table 5 · p. 7

4.4. End-to-End vLLM Performance

• Output throughput rises 10.6–14.9% and median ITL falls 9.2–13.2% with SPIN in the reported vLLM serving workload.Increasing target block sparsity from 40% to 50% increases the output TPS gain by 40.7%, as SPIN’s overhead is largely fixed.Source: Table 6 · p. 7, §4.4 · p. 7

4.5. Speculative Decoding

• Prefix-valid EMA updating reduces p99 miss by 5.9–11.0% relative to row-0 updating; row-local union has a smaller effect, so SPIN adopts row-local union with prefix-valid updating.Online, the selected strategy shows no visible change in MTP acceptance behavior on 1,499 matched requests while retaining 39.51% realized block sparsity.Source: §4.5 · p. 8, Table 7 · p. 8

4.6. Spin Design Ablations

• A2-Max produces consistently higher p99 miss than A0 and A1-Max; SPIN uses A1 because it directly controls target block sparsity, and Max avoids Top-4’s low-sparsity regression.Mean pooling consistently increases p99 miss; Top-4 remains close to Max but is not uniformly better.Source: Figure 3 · p. 9, §4.6 · pp. 9–10
• At 30–50% target sparsity, all three exploration methods yield higher mean task scores than no exploration, but none consistently leads across context lengths and sparsities.SPIN uses random exploration for its simpler implementation, which requires no age tracking or age-based selection.Source: Figure 4 · p. 9, §4.6 · p. 10

• Prior attention methods exploit historical scores through heavy-hitter retention [27], sink-plus-window retention [21], learned prediction [23], or speculative execution with repair [20].Source: §5 · p. 10
• Indexer optimizations include cross-layer reuse, hierarchical filtering, block-level selection, and amortized scans; TISA refreshes fixed groups, whereas SPIN predicts block importance from temporal patterns.Source: §5 · p. 10
• Guess-Verify-Refine accelerates post-indexer top-K, whereas SPIN predicts before the indexer and prunes its input, motivating exploration to address partial observations.Source: §5 · p. 10

• Historical-score prediction has limited ability to anticipate sudden attention shifts, and skipped blocks go unobserved, potentially reinforcing prediction errors.Random exploration offers skipped blocks another observation opportunity but does not guarantee timely discovery or full task-score recovery.Source: §6 · p. 10
• The evaluation covers DeepSeek-V4 and its native MTP, not other indexer-based sparse-attention models or speculative-decoding methods.Broader applicability is expected but has not been demonstrated.Source: §6 · p. 11

• Up to 40% of indexer input blocks are skipped while comparable task quality is preserved across evaluated long-context and agentic benchmarks.Random exploration mitigates stale observations within the same block budget.Source: §7 · p. 11
• The integrated vLLM implementation improves output throughput by up to 14.9% and reduces median inter-token latency by up to 13.2%.Source: §7 · p. 11
• Under DeepSeek-V4’s native MTP, the core predictor retains block sparsity without a visible change in acceptance behavior.Source: §7 · p. 11
• Sudden attention shifts and feedback between predictions and future observations limit SPIN; combining temporal history with current-query or cross-layer signals is proposed for future work.Source: §7 · p. 11