Sub-Quadratic Sparse Attention

Abstract

Every modern language model rests on an attention mechanism whose cost grows with the square of the input — the wall that long made million-token context economically impossible. This paper traces how sparse and sub-quadratic attention breached that ceiling, walks the architecture's evolution from the 2017 transformer through today's native-sparse and hybrid state-space models, and argues that raw capacity has now been won while genuine long-range comprehension remains the open frontier.