GML5 IndexCache

IndexCache: Killing the Indexer's O(NL²) Bottleneck in DeepSeek Sparse Attention Notes from my notebook on GLM-5.2 / DeepSeek Sparse Attention (DSA), reconstructed from the IndexCache paper (Bai, Dong et al., Tsinghua + Z.ai, 2026) — the mechanism behind GLM-5.2's "IndexShare." 1. Why this exists — the bottleneck nobody talks about DSA's whole pitch is: don't do full O(L²) attention, instead let a cheap lightning indexer look at all preceding tokens and pick the top-k (k=2048) that actually matter, then do real attention only on those. That drops core attention from O(L²) → O(Lk). Great — except I missed this the first time I read DSA: the indexer itself is still O(L²) . It has to score every preceding token against the query to decide who's in the top-k. So across N layers you've traded one O(L²) cost for N separate O(L²) costs — total O(NL²). At long context this indexer becomes the dominant cost, not the attention it was supposed to fix. Adding the indexer is "DSA on steroids" because it kills DSA's one real bottleneck (full attention) — but in doing so, it grows its own. The indexer is cheap per-FLOP (few heads, low-rank, FP8) but it still runs at every single layer. The fix the paper proposes isn't a smarter indexer — it's don't run it every layer at all. 2. The core insight: adjacent layers pick almost the same tokens If you measure pairwise overlap between the top-k token sets selected by each layer's indexer, adjacent layers share 70–100% of their picks. The heatmap even shows block structure — clusters of layers (e.g. layers 3–5, 17–30, etc.) that all converge on roughly the same "important" tokens. So most of the O(NL²) indexer cost is redundant computation of the same answer. This motivates IndexCache : split the N layers into two roles — F (Full) layers — run their own indexer, compute fresh top-k, cache it. S (Shared) layers — skip the indexer entirely, just reuse the nearest preceding F layer's cached top-k. The first layer is always F (has to seed the