Million-token context has become standard for large models. However, as we move toward the tens-of-millions-token scale, the indexer overhead for filtering relevant tokens in traditional sparse attention schemes grows linearly with sequence length, and overall prefill still exhibits quadratic complexity—making it the performance bottleneck for ultra-long contexts. A London-based startup, together with ETH Zurich, has jointly proposed Latent Sparse Attention (LSA), a method that clusters keys into groups by semantics and, through flat search or hierarchical tree beam search, reduces indexer complexity to sub-quadratic. The method supports two implementation forms: D-LSA, which can be grafted onto existing models, and N-LSA, used natively during pretraining. In tens-of-millions-token scenarios, it achieves prefill speedups ranging from several-fold to tens-fold while maintaining accuracy close to that of the original model, greatly reducing the runtime and index memory usage of ultra-long contexts.
