liveBook · Manning

Quadratic time complexity

As explained in Building Specialized AI Systems

Quadratic complexity is computational growth proportional to the square of sequence length.

Quadratic growth means that full self-attention costs increase proportionally to the square of sequence length, making very long contexts a computational bottleneck. section 3.1.1

Common responses to quadratic attention costs include:

  • Use sparse or local attention patterns to restrict which tokens interact. section 3.1.1
  • Apply low-rank or kernel approximations, memory layers, or retrieval-augmented approaches. section 3.1.1
  • Consider recurrent or state-space architectures such as RWKV, Mamba, or RetNet, while recognizing their reported performance trade-offs. section 3.1.1
  • Reduce runtime or memory pressure with gradient checkpointing and mixed-precision training. section 3.1.1

How Building Specialized AI Systems covers it

How deep it goes
Defines the square-length scaling and names mitigations, but does not derive the complexity mathematically.
Examples
Uses long-context attention, sparse and local patterns, RWKV, Mamba, RetNet, checkpointing, and mixed precision as examples.
What you can do after
Evaluate architecture and optimization choices when sequence length makes full self-attention costly.
How it connects
Connects quadratic growth to self-attention, Transformers, sparse attention, recurrence, state-space mechanisms, and retrieval augmentation.

Also explained in

Compare how 7 books explain quadratic time complexity →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Building Specialized AI Systems. The section links point to the parts of the book it draws on.