Efficient Sequence ModelingIssue 13Oct 31 – Nov 7, 2026

Hierarchical Sparse Attention Reduces Selection Cost to Logarithmic

Highlights of This Issue

The most prominent signal this issue is that hierarchical sparse attention reduces the selection cost from O(L) to O(log L), and for the first time achieves million-scale extrapolation under a fixed training length. Recursive Sparse Attention builds a tree over the KV cache, selecting only k candidates per query per layer, with both selection and reading costs growing logarithmically with length; its candidate-local RoPE ensures that relative distances at each level always fall within the training range, fundamentally eliminating the need for extrapolation, and the summaries of unselected candidates share a softmax with exact tokens to maintain normalization consistency. Trained on Qwen3-4B with 0.62B tokens, it achieves 60.5 on RULER 1M (the strongest baseline Dense+DCA is 40.0), and provides a complete degradation curve from 32K to 2M with compute-matched comparisons—this is a direct convergence of the two existing routes from Issue 5: HiLS's level-wise scoring and PISA's discarding of unselected blocks. Concurrently, Subquadratic Attention with a Hierarchical Tree-Structured Indexer follows the same hierarchical tree direction, using learned reference queries for top-p routing, but its long-context performance is only extrapolated via roofline models without empirical validation, and should be treated as a comparison to RecSA rather than a replacement.

Mixed linear attention and inference-side state representation each have substantial advances. Muir is the first to systematically prove the sensitivity asymmetry between erase and write gates in the gated delta rule for state updates, advancing gate rank allocation from heuristics to sensitivity-analysis-guided, and derives a closed-form scaling law for state row energy, designing matched-filter readout gains to dynamically balance state rows with different decay rates—this is a direct increment over the fixed gate designs of Multi-State Linear Attention and GDN-2 from Issue 12, with 4K training extrapolating to 10M tokens without perplexity drift and near-100% passkey retrieval. Shallow Encoding Emits Deep Memories is the first to reveal the "state sink" structure of recurrent states (a rank-one term along the per-head mean direction accounts for most energy) and the property that "writing is easier than reading," proposing shallow prefill plus storing decoding states as a sink plus low-rank factors, and proving that GDN/KDA/Mamba-2 updates are exactly closed under this form, with periodic compression error not accumulating with compression count—this is a further convergence with ReplaySSM from Issue 12 (which caches inputs rather than states): the low-rank structure of the recurrent state itself is a provably exact storage form.

There are two negative results worth reading on long-context evaluation validity and learnable eviction gates. Length Is Cheap, Competition Is Not proves over 126,473 trials that length itself is nearly free in retrieval, with competing content being the main cause of degradation: log(1/a*) explains 35–58% of loss variance while log length explains only 2–8%, and systematically refutes the masked-filler protocol as evidence for pure length effects—this is an attribution advance over the phase-blind-spot diagnosis of Periodic Weak Spots from Issue 11. The Gating Mechanism of KV Cache Eviction identifies a structural failure mode of learnable eviction gates: softmax normalization absorbs per-query constants, making constant gates a no-op, and the LM loss of a frozen backbone happens to prefer this no-op—optimization succeeds but scores have no ranking ability; it proposes fixed quality constraints and reverse KL distillation as two fixes, and proves that for recovering evicted information, "whether the readout position is inside or outside softmax" matters more than memory capacity. On the inference-side quantization front, Quantizing Recurrent Language Models Is Easier Than You Think separates recurrent model quantization into extra-state and intra-state objectives, proposing the LoReS recipe, which is a direct complement to LinQuant from Issue 12 on the accumulation of repeated requantization errors during decoding.

Community and Developments

  • vLLM's Day-0 support for Kimi K3.1 Pro provides production deployment details for a Gated-DSA indexer: FP8 index keys with per-token scales, and optional MXFP4 quantization yielding 10–20% long-context indexing speedups—this is engineering optimization rather than a new method, but offers a reference for low-precision deployment of block-sparse indexers.
  • Hybrid attention: why new LLMs keep full attention in only a few layers proves under a fixed 3:1 hybrid ratio that the placement of attention layers (second layer vs. top layer) is as critical as the ratio itself; a 1-in-4 hybrid with attention in the second layer recovers full-Transformer associative recall—this is a complementary design axis to the inter-layer ratio discussion of Competing Learning from Issue 12, but lacks long-context degradation curves.
  • Ling-3.1-flash reports a 560B open-weights model with a 7:1 KDA-to-Gated-MLA layer ratio, empirically showing that mixed linear attention architectures can deviate significantly from the common 3:1 ratio while remaining competitive—as existence evidence for layer-ratio diversity, not a conclusion that overturns existing design heuristics.
  • LoopVQ and Multi-layer Indexer is a community survey juxtaposing cross-layer index reuse (MLI) and KV quantization (LoopVQ), but only notes that MLI's accuracy is compared against IndexCache rather than Gated DSA, with no new methods or comparisons—a pointer for the indexer direction rather than evidence.

Open Questions

  1. RecSA's candidate-local RoPE keeps relative distances at each level within the training range, thus "extrapolation-free"—but as the hierarchy deepens dynamically with prefix growth, will the semantics of deep summaries continue to hold beyond 2M? Does its shared pooler distillation alter the timing of retrieval head formation, as Competing Learning from Issue 12 did?
  2. Muir's dynamic readout gain and SEED's state sink structure both point to "the energy distribution of state rows determining the memory horizon"—can matched-filter readout be stacked with sink+low-rank storage without breaking the latter's exact closed updates? The joint benefit of both on the same GDN backbone has not been tested.
  3. SEED's periodic compression error bound is open-loop (error does not accumulate with compression count), but under closed-loop, compression errors change subsequent keys/values—beyond its 16K decoding drift evidence, does the sink+content decomposition still hold for longer generation trajectories (e.g., long CoT)?
  4. The Gating Mechanism's no-op diagnosis targets learnable eviction gates—does the same "softmax normalization absorbing constants" failure lurk in the scorers of trainable sparse attention indexers? Can fixed quality constraints and reverse KL distillation be directly transferred to indexer training pipelines like HyScale from Issue 12?

Papers in this issue

  1. Recursive Sparse Attention: Million-Token Length Extrapolation at Logarithmic Cost

    RecSA's hierarchical sparse attention with candidate-local RoPE extrapolates to 2M tokens at logarithmic cost, trained only on 32K-length data, outperforming all baselines on RULER.

    Editor's note

    First to reduce the selection cost of block sparse attention to O(log L) and achieve 2M extrapolation under a fixed 32K training length: candidate-local RoPE keeps relative distances at each level within the training range, fundamentally eliminating the need for extrapolation; summaries of unselected candidates share a softmax with exact tokens to maintain normalization consistency, and a shared pooler is used for both selection and summary keys. Relative to HiLS's level-wise scoring and PISA's discarding of unselected blocks from Issue 5, the increment is a complete solution with logarithmic selection cost plus extrapolation-free, RULER 1M 60.5 vs DSA+DCA 36.8, with a full 32K→2M degradation curve and compute-matched comparisons. Anyone working on trainable block-sparse indexers or long-context extrapolation should read.

  2. Muir: Linear Attention with Sensitivity-Allocated Gating and Matched-Filter Readout

    Muir fuses all gating into a sensitivity-allocated low-rank projection with a matched-filter readout, improving perplexity by 2% and enabling 2560x length extrapolation over Gated DeltaNet-2.

    Editor's note

    First to systematically prove the sensitivity asymmetry between erase and write gates in the gated delta rule for state updates, advancing gate rank allocation from heuristics to sensitivity-analysis-guided: erase gates can be safely low-rank, write gates need higher rank; also derives a closed-form scaling law for state row energy, designing matched-filter readout gains to dynamically balance state rows with different decay rates and extend the memory horizon. Relative to the fixed gate designs of Multi-State Linear Attention and GDN-2 from Issue 12, the increment is establishing "gate rank allocation" and "dynamic readout gain" as two new design axes, with 4K training extrapolating to 10M tokens without perplexity drift and near-100% passkey retrieval. Anyone working on mixed linear attention architectures should read.

  3. Shallow Encoding Emits Deep Memories

    SEED exploits write-read asymmetry and state sinks in hybrid LLMs to prefill with 63-89% of layers and compress recurrent states by 2-4x, nearly losslessly improving throughput 1.2-1.4x.

    Editor's note

    First to systematically reveal two structural properties of recurrent states in hybrid models: the "state sink" (a rank-one term along the per-head mean direction accounts for most energy) and "writing is easier than reading," proposing shallow prefill plus storing decoding states as a sink plus low-rank factors, and proving that GDN/KDA/Mamba-2 updates are exactly closed under this form, with periodic compression error not accumulating with compression count. Relative to ReplaySSM's "caching inputs rather than states" from Issue 12 and sparse anchor replay from Issue 8's Just Let Linear States Forget, the increment is treating the low-rank structure of the recurrent state itself as a provably exact storage form, validated across five production model classes. Limitation: long-context degradation curves only cover 16K decoding drift.

  4. The Gating Mechanism of KV Cache Eviction

    Naive learned gates for KV cache eviction fail because softmax normalizers absorb per-query constants, making dense attention the loss-preferred no-op, but IndexMem++ fixes this with distillation and mass-based budgets, achieving near-full-cache accuracy at 75% compression.

    Editor's note

    First to identify a structural failure mode of learnable KV eviction gates: softmax normalization absorbs per-query constants, making constant gates a no-op, and the LM loss of a frozen backbone happens to prefer this no-op—optimization succeeds but scores have no ranking ability. It proposes fixed quality constraints (placing dense attention where gates cannot reach) and reverse KL distillation (using dense model predictions as targets), and proves that for recovering evicted information, "whether the readout position is inside or outside softmax" matters more than memory capacity. Relative to existing learnable eviction gates and recovery methods, the increment is an explicit diagnosis of the no-op and two actionable fixes, with RULER 8K 90.14 at 75% compression, only 3.72 points below full cache.

  5. Length Is Cheap, Competition Is Not: Attention Predicts Context Rot in Retrieval

    Context length is nearly free in retrieval; accuracy collapses only when competing statements steal attention from the evidence, not from token count alone.

    Editor's note

    First to directly link "attention quality on evidence a*" to retrieval loss at the per-trial level, and provide visible neutral filler controls proving that length itself is nearly free in retrieval, with competing content being the main cause of degradation: over 126,473 trials, log(1/a*) explains 35–58% of loss variance, while log length explains only 2–8%. Relative to the phase-blind-spot diagnosis of Periodic Weak Spots from Issue 11, the increment is advancing degradation attribution from position/length to attention competition as a single measurable quantity, and systematically refuting the masked-filler protocol as evidence for pure length effects—any work claiming "lossless" based on average NIAH should cite this as a caution at the evaluation protocol level.

  6. Quantizing Recurrent Language Models Is Easier Than You Think

    Decayed linear recurrent mixers develop weaker activation outliers than softmax attention, making them inherently easier to quantize, and the LoReS recipe enables robust 8-bit recurrent states.

    Editor's note

    First to systematically separate recurrent model quantization into extra-state (W/A) and intra-state (the recurrent state itself) objectives, proving that recurrent models develop weaker residual outlier channels than softmax attention (W/A are easier to quantize), and proposing LoReS (value-axis grouping + decay-based mixed precision + stochastic rounding). Relative to LinQuant's prefill function invariance from Issue 12, the increment is a formal analysis of repeated requantization error accumulation during decoding, including a proof that stochastic rounding eliminates cross-step error reinforcement under RTN and a failure mode where rotation fails under repeated requantization. Supports robust 8-bit state quantization on Qwen-3.5 9B, Nemotron-H 8B, and Kimi-Linear 48B, with end-to-end vLLM speedups.

  7. Who Asks, Who Answers: Linear Attention Builds the Query in Hybrid Language Models

    Hybrid language models divide retrieval labor: linear attention builds the softmax reader's query, not just compressing context.

    Editor's note

    First to use causal transplantation to prove that in hybrid architectures, linear attention layers directly construct the query for a softmax reader (Encode–Address circuit), rather than merely compressing context, and show that the computation of this Address block can be transferred across architectures between GDN and Mamba-2. Relative to the channel-level causal separation of What Attention Recalls from Issue 5 and the competition dynamics of Competing Learning from Issue 12, the increment is localizing to a specific linear layer block and proving its output/recurrent state is sufficient to redirect retrieval (0.97–0.99 transplantation success). This is a direct negative-result-type work on efficient attention as an optimization prior affecting retrieval head formation, a must-read for those working on inter-layer ratios in hybrid architectures; limitation: only synthetic KV retrieval tasks.

  8. Head Dimension Matters in Language Models for Long-Context Retrieval

    Wider attention heads with larger QK dimensions significantly improve long-context retrieval, with gains of up to 15 points, independent of training loss.

    Editor's note

    First to systematically study the impact of head dimension on long-context retrieval ability under a fixed attention parameter budget, and provide mechanistic causal evidence: wider heads achieve larger CPT retrieval gains even with frozen attention projection weights, indicating the gains mainly come from embedding and MLP adaptation rather than the plasticity of the attention module itself. Relative to the channel-level functional separation of What Attention Recalls from Issue 5, the increment is establishing head dimension itself as an architectural axis affecting retrieval head formation and long-context adaptation efficiency, with a frozen-projection control experiment. Anyone working on inter-layer ratios in hybrid architectures or long-context CPT should read; limitation: only RULER-100 and no agentic long-context benchmarks.