Full attention compares every query token with every key token, so prompt processing grows quadratically with context length. Sparse attention reduces the final attention workload by selecting a small set of keys, but common learned indexers still score every query-key pair. Researchers at Prefrontal AI and ETH Zurich report that this selection step consumes about 98% of an attention layer’s runtime at 10 million tokens in GLM-5.3-Flash.

The team proposes Latent Sparse Attention (LSA), which clusters keys in a learned latent space and lets queries search those clusters. Its hierarchical D-LSA variant reduces prefill indexing from quadratic growth to roughly O(T log T), where T is the sequence length. The approach supports both retrofitting existing checkpoints and training new models from scratch.

At 10 million tokens, indexing takes over

During prefill, a model processes the initial prompt and builds its key-value cache. During decoding, each generated token searches that cache. A conventional sparse indexer may select only a few keys for attention, yet it first evaluates every available key to decide which ones to keep. Prefill therefore retains a quadratic indexing cost, while each decoding step remains linear in the existing context length.

Chart showing the indexer dominating sparse-attention runtime as context length increases
The authors report that indexing accounts for about 98% of GLM-5.3-Flash attention-layer runtime at 10 million tokens.

Block-sparse methods lower indexing costs by selecting fixed regions, but relevant tokens can fall outside those regions. Other hierarchical designs rely on streaming constraints or shared indexes across layers. LSA instead organizes keys by their learned content representation, allowing each query to retrieve semantically related regions from across the context.