The standard self-attention mechanism that powers Transformers has a dirty secret: its time and memory costs balloon quadratically with sequence length. Feed it a long document or high-resolution image, and the compute bill gets ugly fast. Nyströmformer, developed as one of many efficient Transformer variants, attacks that problem directly by approximating the softmax matrix rather than computing it in full.
The trick borrows from the Nyström method, a classic matrix approximation technique. Instead of materializing the entire attention matrix, you sample a subset of rows and columns, work with those, and use the pseudoinverse to reconstruct an approximation. But there’s a catch the authors had to solve: you can’t directly sample columns from a softmax matrix, because computing any single entry requires the entire row for the softmax denominator. Their workaround is to sample landmarks from the queries and keys themselves, constructing three smaller matrices that stand in for the submatrices in the original Nyström formulation.
Those landmarks aren’t selected at random either. The paper uses segment means: tokens get grouped into segments, and each segment’s average becomes a landmark. With just 32 or 64 landmarks, Nyströmformer reportedly holds its own against full self-attention and other efficient attention schemes, even on sequences running to 4,096 tokens or beyond. A skip connection with a 1D depthwise convolution adds a bit of local context on top, which is a practical touch that shows up in the implementation.
What’s genuinely interesting here is the performance-per-landmark ratio. Most linear attention approximations trade away too much representational capacity to be useful beyond benchmarks. Hitting competitive results with 64 landmarks suggests the softmax matrix has more low-rank structure than the field tends to assume. The HuggingFace implementation is available for anyone who wants to stress-test that claim on their own data, and the original code is out there too. The segment-means approach also means landmark selection costs almost nothing, which keeps the constant factors low enough to matter in production settings where theoretical O(n) scaling isn’t enough on its own.
