Weekly Paper Notes — one of the top picks from the 2026-06-06 CS paper digest. Area: NLP / Systems-for-ML.

Authors: Yutao Sun, Yanqi Zhang, Li Dong, et al. (Microsoft Research Asia) arXiv: 2606.06467 · PDF

TL;DR

Long-context LLM inference is bottlenecked by attention cost, and sparse attention is the obvious lever. The two existing families both disappoint in practice: block-sparse patterns (sliding window, dilated, etc.) give clean speedups but lose quality, while token-sparse patterns (top-k over the KV cache) preserve quality but spend most of the budget deciding which tokens to attend to — the routing itself becomes the bottleneck. Cross-Layer Sparse Attention (CLSA) breaks the tie by observing that in YOCO-style architectures (where many cross-decoder layers share a single KV cache), you can also share the routing index: one indexer computes top-k once, and every cross-decoder layer reuses that selection. This keeps fine-grained token-level selectivity while amortizing routing across L layers. The reported numbers are 7.6× decoding speedup and 17.1× end-to-end throughput at 128K context with quality maintained on both short- and long-context benchmarks.

What problem is the paper actually attacking?

Modern reasoning LLMs spend a huge fraction of their wall-clock on decoding, and the decoding cost is dominated by attention over a long KV cache. Two pre-existing approaches each give up something important:

  • Block-sparse attention (Longformer, BigBird, sliding-window variants) restricts attention to a fixed structured pattern. The pattern is cheap because the GPU loads contiguous blocks, but the structure is content-agnostic — important distant tokens get dropped because they fell outside the window. Reasoning chains, which depend on selectively pulling in earlier sub-conclusions, are exactly the workload where this hurts.
  • Token-sparse / top-k attention scores every token in the cache and attends to the top k. Quality is preserved because routing is content-aware. But the scoring step itself requires a pass over the entire cache, and it has to happen at every layer of every decoding step. Empirically the savings on attention compute are largely eaten by the routing pass, so the end-to-end speedup is modest.

CLSA targets the second failure mode head-on: the routing pass is the bottleneck, so amortize it.

The mechanism: shared top-k routing on top of YOCO

YOCO (You Only Cache Once) splits a Transformer into a self-decoder prefix that builds the KV cache, and a long stack of cross-decoder layers that all attend to that same KV cache. CLSA adds a second sharing axis: a single indexer computes the top-k selection over the cache for each query token, and all cross-decoder layers reuse that same index. Concretely:

  1. The self-decoder runs as in YOCO and produces one shared KV cache.
  2. A lightweight indexer takes the current query and produces per-token top-k scores against the shared cache.
  3. Cross-decoder layers L_1, L_2, …, L_n all attend to the same selected k tokens rather than re-scoring independently.

This is exactly the design point that token-sparse attention couldn’t reach by itself: per-token selectivity is preserved (so quality holds), but the O(cache_size) routing cost is paid once per decoding step rather than once per layer per decoding step. The savings scale with the number of cross-decoder layers, which is large in modern architectures.

A second consequence is that the routing decision is structurally consistent across layers, which has a nice side effect on KV-cache management: the union of selected tokens across layers is just the single selected set, so you can imagine cache-tiering and streaming policies that move only the actually-needed tokens to fast memory.

Why training/inference stays fast

The paper argues CLSA improves all three of the major inference bottlenecks together:

  • Pre-filling — the indexer is cheap, and YOCO already amortizes KV computation across layers.
  • KV-cache storage — YOCO’s single shared cache already reduces memory; CLSA’s selectivity further reduces the bandwidth pulled per decode step.
  • Decoding — the headline result. Each layer now does sparse attention over k tokens rather than over the full cache, and doesn’t pay its own routing cost.

The architecture is also friendly to existing inference stacks: it does not require custom kernels for content-dependent block layout, because the selected set is the same at every layer and can be materialized once per step.

Results

The reported numbers are at 128K context: up to 7.6× decoding speedup and 17.1× overall throughput improvement, while matching baselines on short-context benchmarks and remaining competitive on long-context ones. The interesting comparison is not against dense attention (where any sparse method will win) but against (a) block-sparse baselines, which CLSA beats on quality, and (b) per-layer token-sparse baselines, which CLSA beats on end-to-end throughput by amortizing the routing cost. That’s the trade-off the paper is built to dominate.

A reasonable skeptical question is whether the shared index loses quality compared to per-layer routing, since different layers attend to different things. The empirical results suggest the loss is small enough to be a clean win at long context, where the speedup is most needed. The deeper read is that the routing decision in long-context reasoning is mostly about which prior tokens are relevant, and that determination is fairly layer-invariant — different layers want to use those tokens differently, but they want to look at the same tokens.

Why this matters

Long-context inference economics are the binding constraint on the current generation of reasoning models. Every percentage point of decode speedup at 128K+ context translates directly into either lower serving cost or longer reasoning traces at fixed budget. CLSA’s contribution is to find a second sharing axis on top of YOCO — sharing the routing decision, not just the cache — and to show that this combination joints with the strengths of both block-sparse (cheap) and token-sparse (selective) attention. The architectural pattern is general: any place where you have a stack of layers all doing content-dependent selection over a shared substrate is a candidate for shared-routing amortization.

Read alongside

  • YOCO: You Only Cache Once (Sun et al., 2024) — the KV-sharing substrate CLSA is built on.
  • Native Sparse Attention / NSA (DeepSeek, 2025) — the closest token-sparse contemporary; CLSA reuses the routing idea but kills its per-layer cost.
  • Longformer / BigBird (Beltagy 2020, Zaheer 2020) — the canonical block-sparse baselines.
  • H2O: Heavy-Hitter Oracle (Zhang et al., 2023) — KV-eviction as a different angle on the same long-context cost problem.
  • FlashAttention / FlashDecoding (Dao et al.) — the dense-attention efficiency baselines that anything claiming a long-context speedup must beat.

📄 arXiv abstract · 📄 PDF

Part of the Weekly CS Paper Digest series. Summary written from a close read of the preprint abstract; the architectural commentary and contemporaries comparison are the author’s synthesis.