Reformer

Reformer (Kitaev, Kaiser and Levskaya, 2020) hashes shared query-keys with random rotations, sorts and chunks them so each token attends only within its hash bucket, cutting attention from O(L²) to O(L log L). Reversible residual layers and a chunked feed-forward cut activation memory.

14 min read1005 wordsadvanced0 viewsupdated 2026-10-12

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 nbn_b 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 l×dffl\times d_{ff} 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 q⋅kq\cdot k matter. Full attention still computes all l2l^2 scores. At l=65,536l=65{,}536 (64K) tokens, one l×ll\times l matrix in 32-bit floats is 1616 GiB, for one head of one layer. Memory is the other limit. A model with nln_l layers stores nln_l sets of activations for backpropagation, and each feed-forward layer holds an l×dffl\times d_{ff} hidden tensor, often 4×4\times 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

h(x)=arg⁡max⁡([ xR ; −xR ]),R∈Rdk×nb/2 random,kj=qj∥qj∥h(x)=\arg\max\big([\,xR\,;\,-xR\,]\big),\qquad R\in\mathbb R^{d_k\times n_b/2}\ \text{random},\qquad k_j=\frac{q_j}{\lVert q_j\rVert}
RR
a random Gaussian matrix, a "random rotation" (angular LSH of Andoni et al., 2015); a fresh RR per hash round
[ xR; −xR ][\,xR;\,-xR\,]
nbn_b numbers; the argmax picks the closest of nbn_b random directions ±rk\pm r_k, so nearby vectors land in the same bucket with high probability
nbn_b
number of buckets, even
kj=qj/∥qj∥k_j=q_j/\lVert q_j\rVert
shared-QK: one projection gives queries, and keys are the normalised queries. A query and its best keys then hash identically

Why share QQ and KK? 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 kj=qj/∥qj∥k_j=q_j/\lVert q_j\rVert the bucket of a query is also the bucket of its key. The cost is that qi⋅kiq_i\cdot k_i 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

oi=∑j∈P~iexp⁡ ⁣(qi⋅kj−m(j,Pi)−z(i,Pi)) vj,Pi={j:h(qi)=h(kj)},P~i={j:⌊sim⌋−1≤⌊sjm⌋≤⌊sim⌋}o_i=\sum_{j\in\tilde{\mathcal P}_i}\exp\!\big(q_i\cdot k_j-m(j,\mathcal P_i)-z(i,\mathcal P_i)\big)\,v_j,\qquad \mathcal P_i=\{j: h(q_i)=h(k_j)\},\qquad \tilde{\mathcal P}_i=\Big\{j:\Big\lfloor\tfrac{s_i}{m}\Big\rfloor-1\le\Big\lfloor\tfrac{s_j}{m}\Big\rfloor\le\Big\lfloor\tfrac{s_i}{m}\Big\rfloor\Big\}
sis_i
slot of token ii after sorting by (bucket, position)
mm
chunk length; chunks of mm consecutive sorted tokens attend to themselves and to the chunk before
m(j,Pi)m(j,\mathcal P_i)
∞\infty if j∉Pij\notin\mathcal P_i (another bucket) and 0 otherwise; the chunk is the batched superset, the bucket is the real set
z(i,Pi)z(i,\mathcal P_i)
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 m×2mm\times2m 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 mm is not: tokens at its start cannot see keys more than one chunk ahead. Chunks are sized near the average bucket size l/nbl/n_b (the code below uses m=2l/nbm=2l/n_b). For causal language modelling, the original positions are kept with the sorted tokens and j>ij>i is masked as usual.

Hashing is random, so similar vectors sometimes fall into different buckets. Multi-round LSH repeats the hash with nrn_r independent rotations and lets each query use the union Pi=⋃rPi(r)\mathcal P_i=\bigcup_r\mathcal P_i^{(r)}. In practice each round is computed separately and the outputs are mixed with weights from their softmax normalisers. The cost grows linearly in nrn_r, and in the paper the gap to full attention shrinks as rounds are added. Per head, a round costs l⋅2ml\cdot2m scores plus an O(llog⁡l)O(l\log l) sort, instead of l2l^2.

Reversible layers and chunked feed-forward

Y1=X1+Attention(X2)X2=Y2−FeedForward(Y1)Y2=X2+FeedForward(Y1)X1=Y1−Attention(X2)\begin{aligned}Y_1&=X_1+\mathrm{Attention}(X_2) & \qquad X_2&=Y_2-\mathrm{FeedForward}(Y_1)\\ Y_2&=X_2+\mathrm{FeedForward}(Y_1) & X_1&=Y_1-\mathrm{Attention}(X_2)\end{aligned}
(X1,X2)(X_1,X_2)
two activation streams; the RevNet construction of Gomez et al. (2017), with LayerNorm moved inside the residual blocks
left\text{left}
the forward pass of one layer
right\text{right}
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 nln_l times the memory of one layer. A reversible stack keeps only the last layer's outputs, then walks back, reconstructing X1,X2X_1,X_2 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 cc slices of the sequence, Y2=[X2(1)+FF(Y1(1));… ;X2(c)+FF(Y1(c))]Y_2=\big[X_2^{(1)}+\mathrm{FF}(Y_1^{(1)});\dots;X_2^{(c)}+\mathrm{FF}(Y_1^{(c)})\big]. Only an (l/c)×dff(l/c)\times d_{ff} 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
O(llog⁡l)O(l\log l) per head: nr⋅l⋅2mn_r\cdot l\cdot2m scores plus sorting, instead of l2l^2
Hash
h(x)=arg⁡max⁡[xR;−xR]h(x)=\arg\max[xR;-xR], nbn_b buckets, nrn_r independent rounds
Shared-QK
kj=qj/∥qj∥k_j=q_j/\lVert q_j\rVert; 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
h(x) = argmax([xR; −xR]) · sort by (bucket, pos) · attend own + previous chunk427063ring: bucket of each direction, round 1grey lines: ±columns of R · click a pointfull softmax, sorted by round 1■ kept · ■ missed · opacity = weightrows = queries (click), columns = keysquery 5: bucket 7, sorted slot 23, chunk 2its full mass kept 0.000mean mass kept 0.584strongest key kept 26/32 queriespairs kept 157 of 992same-bucket, too far 19largest bucket 9 (chunk m = 8)dots/head 1·l·2m = 512 vs l² = 1024at l = 65,536, m = 64: LSH 8.39e6 dots vs full 4.29e9 (512× fewer)
buckets
matrix order
fig.32 shared query-key vectors in 2-D (five semantic clusters) and the 32 × 32 full-softmax attention, with self-attention excluded. The ring shows which bucket each direction hashes to. Blue cells are weights LSH keeps, rose cells are weights it misses. Defaults: 8 buckets, chunk m = 8, one round. Only 6 of the 8 buckets are used, and 157 of 992 pairs survive. They carry a mean 0.584 of each query's full attention, and the strongest key survives for 26 of 32 queries. Query 5 is the failure case. Its two near neighbours share its bucket 7, but that bucket has 9 members, more than m, and the neighbours sit in the next chunk, so the query keeps 0.000 of its attention. A second round gives 0.002, a third 0.879. Mean kept mass is 0.840 with 2 rounds and 0.931 with 4, and the strongest key then survives for all 32 queries. With m = 16 and one round the mean is 0.634. At 64K tokens, m = 64 and one round, LSH computes 8.39e6 scores per head against 4.29e9 for full attention (512× fewer).

Worked example: hash, sort, chunk

Take dk=2d_k=2, nb=4n_b=4 and R=(0.6−0.80.80.6)R=\begin{pmatrix}0.6&-0.8\\0.8&0.6\end{pmatrix}, so xRxR has two entries and [xR;−xR][xR;-xR] has four.

Hashing four unit vectors

  1. 1x=(0.6,0.8)x=(0.6,0.8): xR=(1.00, 0.00)xR=(1.00,\,0.00), [xR;−xR]=(1,0,−1,0)[xR;-xR]=(1,0,-1,0), bucket 0.
  2. 2x=(−0.8,0.6)x=(-0.8,0.6): xR=(0.00, 1.00)xR=(0.00,\,1.00), bucket 1.
  3. 3x=(−0.6,−0.8)x=(-0.6,-0.8): xR=(−1.00, 0.00)xR=(-1.00,\,0.00), [xR;−xR]=(−1,0,1,0)[xR;-xR]=(-1,0,1,0), bucket 2. x=(0.8,−0.6)x=(0.8,-0.6): xR=(0,−1)xR=(0,-1), bucket 3.
  4. 4A nearby vector x=(0.96,0.28)x=(0.96,0.28) (37° from the first, since their dot product is 0.8): xR=(0.80, −0.60)xR=(0.80,\,-0.60), bucket 0 again. Angular LSH keeps small angles together.
token ibucketsorted slot sᵢchunkkeys it attends to
02425
10003
23637
30101
4131none (itself only)
52520
60211, 3
73732
Eight tokens with buckets (2, 0, 3, 0, 1, 2, 0, 3), sorted and cut into chunks of m = 2 (checked in Node)

The sorted order is 1,3,6,4,0,5,2,71,3,6,4,0,5,2,7, giving chunks {1,3},{6,4},{0,5},{2,7}\{1,3\},\{6,4\},\{0,5\},\{2,7\}. 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.

python
1import torch, torch.nn as nn, torch.nn.functional as F
2
3def 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 chunk
5 B, l, dh = qk.shape
6 k = F.normalize(qk, dim=-1) # keys = unit-norm queries
7 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 round
11 proj = k @ R
12 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 // chunk
17 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 bucket
23 s = s.masked_fill(sp[..., None] == kp[..., None, :], -1e5) # self only if nothing else
24 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 order
27 lses.append(lse.view(B, l, 1).gather(1, undo[..., None]))
28 w = torch.cat(lses, -1).softmax(-1) # weight rounds by their mass
29 return sum(w[..., r : r + 1] * outs[r] for r in range(n_rounds)) # (duplicates are not removed)
30
31class RevBlock(nn.Module):
32 # y1 = x1 + F(x2), y2 = x2 + G(y1); F = attention, G = feed-forward
33 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 attention
36 self.ff = nn.Sequential(nn.LayerNorm(d), nn.Linear(d, dff), nn.GELU(), nn.Linear(dff, d))
37 self.ff_chunks = ff_chunks
38 def g(self, x): # chunked FFN: never holds (l, dff) at once
39 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)
43
44class RevStack(torch.autograd.Function):
45 @staticmethod
46 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 = blocks
51 ctx.save_for_backward(x1, x2) # only the last layer's outputs
52 return x1, x2
53
54 @staticmethod
55 def backward(ctx, dy1, dy2):
56 y1, y2 = ctx.saved_tensors
57 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.grad
62 with torch.no_grad():
63 x2 = y2 - gy # reconstruct x2
64 dy1 = dy1 + y1.grad
65 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.grad
69 with torch.no_grad():
70 x1 = y1 - fx # reconstruct x1
71 dy2 = dy2 + x2.grad
72 y1, y2 = x1, x2
73 return dy1, dy2, None
74
75torch.manual_seed(0)
76B, l, dh = 2, 1024, 64
77centers = 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 clusters
79v = 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)
87
88blocks = 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 backprop
94a, b2 = x, x
95for 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 stored
LSH attention (shared-QK, multi-round, sort/chunk/look-back) and a reversible stack with a chunked feed-forward, checked against full attention and ordinary backprop

Use when

  • +Attention cost O(nr l m)O(n_r\,l\,m) plus a sort instead of O(l2)O(l^2); 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: h(x)=arg⁡max⁡[xR;−xR]h(x)=\arg\max[xR;-xR] with shared kj=qj/∥qj∥k_j=q_j/\lVert q_j\rVert; sort by bucket, attend within chunks of mm plus one chunk back: O(nr l m)O(n_r\,l\,m) scores plus an O(llog⁡l)O(l\log l) sort.
  • ✓Reversible layer: Y1=X1+Attn(X2)Y_1=X_1+\mathrm{Attn}(X_2), Y2=X2+FF(Y1)Y_2=X_2+\mathrm{FF}(Y_1), inverted exactly in the backward pass, so activations are stored once, not nln_l 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.
← back to Deep Learning roadmap