subquadratic-attention-reformer-bigbird

IN premise — entries/2026/06/21/wiki-Transformer_deep_learning_architecture-chunk-4.md

Created 2026-06-21T09:50:11+00:00

Sub-quadratic attention methods: Reformer uses locality-sensitive hashing for O(N log N), BigBird uses sparse random graphs for O(N), Random Feature Attention uses kernel approximation for O(N).

Summary

Three well-known tricks let you process long sequences in near-linear time instead of quadratic: Reformer groups similar tokens with hashing to cut cost to O(N log N), while BigBird and Random Feature Attention push it down to O(N) using sparse random connections and kernel approximations, respectively. In practice this means the system can handle much longer contexts without the compute bill exploding, and these are established, implementable techniques rather than theoretical curiosities.

Dependents

These beliefs depend on this one:

IN hardware-aware-optimization-displaced-algorithmic-attention-alternatives — Hardware-aware optimization of standard quadratic attention offers substantial practical efficiency gains: FlashAttention-2 achieves up to 230 TFLOPs/s on A100 GPUs via SRAM-tiled computation, and PagedAttention reduces GPU memory waste through virtual-memory-style KV cache paging. Meanwhile, sub-quadratic algorithmic alternatives exist — Reformer (O(N log N) via LSH), BigBird (O(N) via sparse attention), and Random Feature Attention (O(N) via kernel approximation) — though the antecedents do not establish their relative production adoption rates. The evidence suggests that implementation engineering targeting hardware constraints can yield large efficiency improvements independent of theoretical complexity reduction.