Definition
Reformer is a Transformer variant for long sequences from Kitaev, Kaiser and Levskaya, "Reformer: The Efficient Transformer" (ICLR 2020). It combines three changes. (1) LSH attention: queries and keys are the same vectors, each is hashed into one of buckets by a random rotation, the sequence is sorted by bucket, and attention is computed only inside fixed-size chunks of the sorted order. (2) Reversible residual layers: each layer's input can be recomputed from its output, so activations are stored once instead of once per layer. (3) Chunked feed-forward: the position-wise MLP is applied to slices of the sequence, so the hidden activation never exists at once.
Softmax attention is usually dominated by a few large weights: for each query only the keys with the largest matter. Full attention still computes all scores. At (64K) tokens, one matrix in 32-bit floats is GiB, for one head of one layer. Memory is the other limit. A model with layers stores sets of activations for backpropagation, and each feed-forward layer holds an hidden tensor, often wider than the model. Reformer attacks all three costs, so long sequences fit on one accelerator. The paper evaluates on enwik8 with 64K-token sequences, on imagenet64 generation (sequences of 12K), and on a synthetic copy task.
Locality-sensitive hashing of shared query-keys
- a random Gaussian matrix, a "random rotation" (angular LSH of Andoni et al., 2015); a fresh per hash round
- numbers; the argmax picks the closest of random directions , so nearby vectors land in the same bucket with high probability
- number of buckets, even
- shared-QK: one projection gives queries, and keys are the normalised queries. A query and its best keys then hash identically
Why share and ? With separate projections, a query and the key it should attend to could hash to different buckets, and buckets would hold unequal numbers of queries and keys. With the bucket of a query is also the bucket of its key. The cost is that is the largest score a token can get, so a token is not allowed to attend to itself unless it has no other target. The paper reports that shared-QK attention trains about as well as standard attention.
Sort, chunk, attend
- slot of token after sorting by (bucket, position)
- chunk length; chunks of consecutive sorted tokens attend to themselves and to the chunk before
- if (another bucket) and 0 otherwise; the chunk is the batched superset, the bucket is the real set
- the log-normaliser of the softmax over the kept keys
Sorting makes each bucket a contiguous run, so the attention matrix becomes block-diagonal in the sorted order. Chunking turns the ragged buckets into equal blocks of scores that batch well on accelerators. A bucket that straddles a chunk boundary is still covered by the one-chunk look-back. A bucket longer than is not: tokens at its start cannot see keys more than one chunk ahead. Chunks are sized near the average bucket size (the code below uses ). For causal language modelling, the original positions are kept with the sorted tokens and is masked as usual.
Hashing is random, so similar vectors sometimes fall into different buckets. Multi-round LSH repeats the hash with independent rotations and lets each query use the union . In practice each round is computed separately and the outputs are mixed with weights from their softmax normalisers. The cost grows linearly in , and in the paper the gap to full attention shrinks as rounds are added. Per head, a round costs scores plus an sort, instead of .
Reversible layers and chunked feed-forward
- two activation streams; the RevNet construction of Gomez et al. (2017), with LayerNorm moved inside the residual blocks
- the forward pass of one layer
- the exact inverse: the backward pass recomputes each layer's input from its output, so intermediate activations need not be stored
A standard network keeps every layer's activations until the backward pass, about times the memory of one layer. A reversible stack keeps only the last layer's outputs, then walks back, reconstructing and backpropagating one layer at a time. The price is recomputation, roughly one more forward pass. The feed-forward layer acts on each position independently, so it can also be run on slices of the sequence, . Only an hidden tensor exists at any time. Chunking trades memory for sequential work and changes nothing in the result.
Reformer at a glance
- Authors / venue
- Nikita Kitaev, Łukasz Kaiser, Anselm Levskaya (UC Berkeley and Google Research), ICLR 2020; released in Trax (JAX)
- Attention cost
- per head: scores plus sorting, instead of
- Hash
- , buckets, independent rounds
- Shared-QK
- ; a token attends to itself only if nothing else is available
- Activation memory
- stored once for the whole stack (reversible layers) instead of once per layer
- Experiments
- enwik8 with 64K-token sequences, imagenet64 generation, a synthetic sequence-duplication task
- Finding
- shared-QK and reversible layers match the standard Transformer's curves; LSH attention approaches full attention as hash rounds increase
Worked example: hash, sort, chunk
Take , and , so has two entries and has four.
Hashing four unit vectors
- 1: , , bucket 0.
- 2: , bucket 1.
- 3: , , bucket 2. : , bucket 3.
- 4A nearby vector (37° from the first, since their dot product is 0.8): , bucket 0 again. Angular LSH keeps small angles together.
| token i | bucket | sorted slot sᵢ | chunk | keys it attends to |
|---|---|---|---|---|
| 0 | 2 | 4 | 2 | 5 |
| 1 | 0 | 0 | 0 | 3 |
| 2 | 3 | 6 | 3 | 7 |
| 3 | 0 | 1 | 0 | 1 |
| 4 | 1 | 3 | 1 | none (itself only) |
| 5 | 2 | 5 | 2 | 0 |
| 6 | 0 | 2 | 1 | 1, 3 |
| 7 | 3 | 7 | 3 | 2 |
The sorted order is , giving chunks . Token 6 sits in chunk 1 and looks back to chunk 0, so it sees both other bucket-0 tokens. Token 3 is in chunk 0 and does not look forward, so it misses token 6. That is the overflow effect the figure shows for query 5. Token 4 is alone in bucket 1 and falls back to attending to itself.
1import torch, torch.nn as nn, torch.nn.functional as F23def lsh_attention(qk, v, n_buckets=8, chunk=32, n_rounds=1):4 # qk, v (B, l, dh): shared query/key projection and values of one head; l divisible by chunk5 B, l, dh = qk.shape6 k = F.normalize(qk, dim=-1) # keys = unit-norm queries7 pos = torch.arange(l).expand(B, l)8 outs, lses = [], []9 for _ in range(n_rounds):10 R = torch.randn(dh, n_buckets // 2) # random rotation for this round11 proj = k @ R12 bucket = torch.cat([proj, -proj], -1).argmax(-1) # (B, l): h(x) = argmax([xR; -xR])13 idx = (bucket * l + pos).argsort(-1) # sort by (bucket, position)14 undo = idx.argsort(-1)15 take = lambda t: t.gather(1, idx[..., None].expand(-1, -1, t.size(-1)))16 n = l // chunk17 sq, sk, sv = (take(t).view(B, n, chunk, dh) for t in (qk, k, v))18 sb, sp = bucket.gather(1, idx).view(B, n, chunk), idx.view(B, n, chunk)19 back = lambda t: torch.cat([t, t.roll(1, dims=1)], 2) # own chunk + previous (chunk 0 wraps)20 kk, vv, kb, kp = back(sk), back(sv), back(sb), back(sp) # keys: (B, n, 2*chunk, dh)21 s = sq @ kk.transpose(-1, -2) / dh ** 0.5 # (B, n, chunk, 2*chunk)22 s = s.masked_fill(sb[..., None] != kb[..., None, :], float("-inf")) # only the same bucket23 s = s.masked_fill(sp[..., None] == kp[..., None, :], -1e5) # self only if nothing else24 lse = s.logsumexp(-1, keepdim=True)25 o = ((s - lse).exp() @ vv).view(B, l, dh)26 outs.append(o.gather(1, undo[..., None].expand(-1, -1, dh))) # back to original order27 lses.append(lse.view(B, l, 1).gather(1, undo[..., None]))28 w = torch.cat(lses, -1).softmax(-1) # weight rounds by their mass29 return sum(w[..., r : r + 1] * outs[r] for r in range(n_rounds)) # (duplicates are not removed)3031class RevBlock(nn.Module):32 # y1 = x1 + F(x2), y2 = x2 + G(y1); F = attention, G = feed-forward33 def __init__(self, d, dff, ff_chunks=4):34 super().__init__()35 self.f = nn.Sequential(nn.LayerNorm(d), nn.Linear(d, d), nn.Tanh()) # stand-in for attention36 self.ff = nn.Sequential(nn.LayerNorm(d), nn.Linear(d, dff), nn.GELU(), nn.Linear(dff, d))37 self.ff_chunks = ff_chunks38 def g(self, x): # chunked FFN: never holds (l, dff) at once39 return torch.cat([self.ff(c) for c in x.chunk(self.ff_chunks, dim=1)], 1)40 def forward(self, x1, x2):41 y1 = x1 + self.f(x2)42 return y1, x2 + self.g(y1)4344class RevStack(torch.autograd.Function):45 @staticmethod46 def forward(ctx, x1, x2, blocks):47 with torch.no_grad():48 for b in blocks:49 x1, x2 = b(x1, x2)50 ctx.blocks = blocks51 ctx.save_for_backward(x1, x2) # only the last layer's outputs52 return x1, x25354 @staticmethod55 def backward(ctx, dy1, dy2):56 y1, y2 = ctx.saved_tensors57 for b in reversed(ctx.blocks):58 with torch.enable_grad():59 y1 = y1.detach().requires_grad_()60 gy = b.g(y1)61 gy.backward(dy2) # G's weight grads and y1.grad62 with torch.no_grad():63 x2 = y2 - gy # reconstruct x264 dy1 = dy1 + y1.grad65 with torch.enable_grad():66 x2 = x2.detach().requires_grad_()67 fx = b.f(x2)68 fx.backward(dy1) # F's weight grads and x2.grad69 with torch.no_grad():70 x1 = y1 - fx # reconstruct x171 dy2 = dy2 + x2.grad72 y1, y2 = x1, x273 return dy1, dy2, None7475torch.manual_seed(0)76B, l, dh = 2, 1024, 6477centers = F.normalize(torch.randn(64, dh), dim=-1)78qk = 64 * centers[torch.randint(0, 64, (B, l))] + 0.3 * torch.randn(B, l, dh) # 64 clusters79v = torch.randn(B, l, dh)80full = F.scaled_dot_product_attention(qk, F.normalize(qk, dim=-1), v,81 attn_mask=~torch.eye(l, dtype=torch.bool))82for r in (1, 2, 4, 8):83 out = lsh_attention(qk, v, n_buckets=16, chunk=128, n_rounds=r)84 print(r, out.shape, round(((out - full).norm() / full.norm()).item(), 3))85# 1 torch.Size([2, 1024, 64]) 0.578 relative error to full attention falls with more rounds:86# 2 ... 0.319, 4 ... 0.23, 8 ... 0.186 (CPU, seed 0)8788blocks = nn.ModuleList(RevBlock(64, 256) for _ in range(6))89x = torch.randn(2, 128, 64, requires_grad=True)90y1, y2 = RevStack.apply(x, x, blocks)91(y1 + y2).pow(2).mean().backward()92g_rev = [p.grad.clone() for p in blocks.parameters()]; gx_rev = x.grad.clone()93blocks.zero_grad(); x.grad = None # reference: ordinary backprop94a, b2 = x, x95for blk in blocks:96 a, b2 = blk(a, b2)97(a + b2).pow(2).mean().backward()98print(max((p.grad - g).abs().max().item() for p, g in zip(blocks.parameters(), g_rev)),99 (x.grad - gx_rev).abs().max().item()) # ~1e-08 ~5e-10: same gradients, only the last outputs storedUse when
- +Attention cost plus a sort instead of ; 64K-token sequences become practical
- +Reversible layers make activation memory independent of depth
- +Chunked feed-forward removes the l × d_ff peak with no change to the result
- +Content-based sparsity: no hand-designed attention pattern
Avoid when
- −Approximate: pairs in different buckets, or more than one chunk apart, are lost; several rounds are needed
- −Sorting, gathering and scattering are irregular memory operations, slow on accelerators for moderate l
- −Shared-QK forces keys to be normalised queries and forbids attending to oneself
- −Recomputation adds about one extra forward pass, and random hashing complicates reproducibility
Check yourself
Why does Reformer use the same projection for queries and keys?
Check yourself
In a 12-layer reversible Reformer, what does training store for the backward pass?
Remember
- ✓LSH attention: with shared ; sort by bucket, attend within chunks of plus one chunk back: scores plus an sort.
- ✓Reversible layer: , , inverted exactly in the backward pass, so activations are stored once, not times.
- ✓Multi-round hashing takes the union of buckets over n_r random rotations; quality rises with rounds at linear cost.
- ✓Chunked feed-forward processes the sequence in slices, so the l × d_ff hidden tensor never exists at once.
- ✓Kitaev, Kaiser and Levskaya, ICLR 2020: evaluated on enwik8 with 64K-token sequences and imagenet64; shared-QK and reversibility do not hurt quality.