Why O(n log n) Matters

Transformer attention is O(n²). For every token, you compare it against every other token. At 1,000 tokens, that's 1,000,000 comparisons. At 100,000 tokens, it's 10,000,000,000.

This is not a bug — it's a property of the attention mechanism. But it means that long contexts are expensive. GPT-4's 128K context window costs a fortune to run.

HSS replaces attention with a recurrent scan. The scan is O(n log n) — linear in the sequence length with a logarithmic factor for the state dimension. At 100,000 tokens, that's roughly 100,000·log(100,000) ≈ 1,700,000 operations instead of 10,000,000,000.

The memory story is even better. Attention stores the full n×n attention matrix. HSS stores a fixed-size state vector. For a 4,096-dimensional state, that's 4,096 floats regardless of sequence length.

The tradeoff: expressiveness. Attention can look at any pair of tokens directly. HSS compresses the past into a state vector. Some information is lost. But for many tasks — language modeling, audio, time series — the state is sufficient.

In v0.1.0, the HSS scan runs on CPU and is slower than attention for short sequences (below 1,000 tokens). The crossover point depends on implementation quality. CUDA kernels in v0.5.0 will change this.