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.
