# 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.

Source: https://www.mlfoundry.in/learn/reformer  
Section: Deep Learning › Attention and Transformer Architectures  
Level: advanced · 14 min read · updated 2026-10-12

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

- $R$: a random Gaussian matrix, a "random rotation" (angular LSH of Andoni et al., 2015); a fresh $R$ per hash round
- $[\,xR;\,-xR\,]$: $n_b$ numbers; the argmax picks the closest of $n_b$ random directions $\pm r_k$, so nearby vectors land in the same bucket with high probability
- $n_b$: number of buckets, even
- $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 $Q$ and $K$? 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 $k_j=q_j/\lVert q_j\rVert$ the bucket of a query is also the bucket of its key. The cost is that $q_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

$$
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\}
$$

- $s_i$: slot of token $i$ after sorting by (bucket, position)
- $m$: chunk length; chunks of $m$ consecutive sorted tokens attend to themselves and to the chunk before
- $m(j,\mathcal P_i)$: $\infty$ if $j\notin\mathcal P_i$ (another bucket) and 0 otherwise; the chunk is the batched superset, the bucket is the real set
- $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\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 $m$ is not: tokens at its start cannot see keys more than one chunk ahead. Chunks are sized near the average bucket size $l/n_b$ (the code below uses $m=2l/n_b$). For causal language modelling, the original positions are kept with the sorted tokens and $j>i$ is masked as usual.

Hashing is random, so similar vectors sometimes fall into different buckets. **Multi-round LSH** repeats the hash with $n_r$ independent rotations and lets each query use the union $\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 $n_r$, and in the paper the gap to full attention shrinks as rounds are added. Per head, a round costs $l\cdot2m$ scores plus an $O(l\log l)$ sort, instead of $l^2$.

## Reversible layers and chunked feed-forward

$$
\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}
$$

- $(X_1,X_2)$: two activation streams; the RevNet construction of Gomez et al. (2017), with LayerNorm moved inside the residual blocks
- $\text{left}$: the forward pass of one layer
- $\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 $n_l$ times the memory of one layer. A reversible stack keeps only the last layer's outputs, then walks back, reconstructing $X_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 $c$ slices of the sequence, $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)\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(l\log l)$ per head: $n_r\cdot l\cdot2m$ scores plus sorting, instead of $l^2$
- **Hash:** $h(x)=\arg\max[xR;-xR]$, $n_b$ buckets, $n_r$ independent rounds
- **Shared-QK:** $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

> Figure: 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 $d_k=2$, $n_b=4$ and $R=\begin{pmatrix}0.6&-0.8\\0.8&0.6\end{pmatrix}$, so $xR$ has two entries and $[xR;-xR]$ has four.

**Hashing four unit vectors**

1. $x=(0.6,0.8)$: $xR=(1.00,\,0.00)$, $[xR;-xR]=(1,0,-1,0)$, bucket **0**.
2. $x=(-0.8,0.6)$: $xR=(0.00,\,1.00)$, bucket **1**.
3. $x=(-0.6,-0.8)$: $xR=(-1.00,\,0.00)$, $[xR;-xR]=(-1,0,1,0)$, bucket **2**. $x=(0.8,-0.6)$: $xR=(0,-1)$, bucket **3**.
4. A nearby vector $x=(0.96,0.28)$ (37° from the first, since their dot product is 0.8): $xR=(0.80,\,-0.60)$, bucket **0** again. Angular LSH keeps small angles together.

Eight tokens with buckets (2, 0, 3, 0, 1, 2, 0, 3), sorted and cut into chunks of m = 2 (checked in Node)

| 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 $1,3,6,4,0,5,2,7$, giving chunks $\{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
import torch, torch.nn as nn, torch.nn.functional as F

def lsh_attention(qk, v, n_buckets=8, chunk=32, n_rounds=1):
    # qk, v (B, l, dh): shared query/key projection and values of one head; l divisible by chunk
    B, l, dh = qk.shape
    k = F.normalize(qk, dim=-1)                                       # keys = unit-norm queries
    pos = torch.arange(l).expand(B, l)
    outs, lses = [], []
    for _ in range(n_rounds):
        R = torch.randn(dh, n_buckets // 2)                           # random rotation for this round
        proj = k @ R
        bucket = torch.cat([proj, -proj], -1).argmax(-1)              # (B, l): h(x) = argmax([xR; -xR])
        idx = (bucket * l + pos).argsort(-1)                          # sort by (bucket, position)
        undo = idx.argsort(-1)
        take = lambda t: t.gather(1, idx[..., None].expand(-1, -1, t.size(-1)))
        n = l // chunk
        sq, sk, sv = (take(t).view(B, n, chunk, dh) for t in (qk, k, v))
        sb, sp = bucket.gather(1, idx).view(B, n, chunk), idx.view(B, n, chunk)
        back = lambda t: torch.cat([t, t.roll(1, dims=1)], 2)        # own chunk + previous (chunk 0 wraps)
        kk, vv, kb, kp = back(sk), back(sv), back(sb), back(sp)       # keys: (B, n, 2*chunk, dh)
        s = sq @ kk.transpose(-1, -2) / dh ** 0.5                     # (B, n, chunk, 2*chunk)
        s = s.masked_fill(sb[..., None] != kb[..., None, :], float("-inf"))  # only the same bucket
        s = s.masked_fill(sp[..., None] == kp[..., None, :], -1e5)          # self only if nothing else
        lse = s.logsumexp(-1, keepdim=True)
        o = ((s - lse).exp() @ vv).view(B, l, dh)
        outs.append(o.gather(1, undo[..., None].expand(-1, -1, dh)))   # back to original order
        lses.append(lse.view(B, l, 1).gather(1, undo[..., None]))
    w = torch.cat(lses, -1).softmax(-1)                               # weight rounds by their mass
    return sum(w[..., r : r + 1] * outs[r] for r in range(n_rounds))  # (duplicates are not removed)

class RevBlock(nn.Module):
    # y1 = x1 + F(x2), y2 = x2 + G(y1); F = attention, G = feed-forward
    def __init__(self, d, dff, ff_chunks=4):
        super().__init__()
        self.f = nn.Sequential(nn.LayerNorm(d), nn.Linear(d, d), nn.Tanh())   # stand-in for attention
        self.ff = nn.Sequential(nn.LayerNorm(d), nn.Linear(d, dff), nn.GELU(), nn.Linear(dff, d))
        self.ff_chunks = ff_chunks
    def g(self, x):                                                   # chunked FFN: never holds (l, dff) at once
        return torch.cat([self.ff(c) for c in x.chunk(self.ff_chunks, dim=1)], 1)
    def forward(self, x1, x2):
        y1 = x1 + self.f(x2)
        return y1, x2 + self.g(y1)

class RevStack(torch.autograd.Function):
    @staticmethod
    def forward(ctx, x1, x2, blocks):
        with torch.no_grad():
            for b in blocks:
                x1, x2 = b(x1, x2)
        ctx.blocks = blocks
        ctx.save_for_backward(x1, x2)                                 # only the last layer's outputs
        return x1, x2

    @staticmethod
    def backward(ctx, dy1, dy2):
        y1, y2 = ctx.saved_tensors
        for b in reversed(ctx.blocks):
            with torch.enable_grad():
                y1 = y1.detach().requires_grad_()
                gy = b.g(y1)
                gy.backward(dy2)                                      # G's weight grads and y1.grad
            with torch.no_grad():
                x2 = y2 - gy                                          # reconstruct x2
                dy1 = dy1 + y1.grad
            with torch.enable_grad():
                x2 = x2.detach().requires_grad_()
                fx = b.f(x2)
                fx.backward(dy1)                                      # F's weight grads and x2.grad
            with torch.no_grad():
                x1 = y1 - fx                                          # reconstruct x1
                dy2 = dy2 + x2.grad
            y1, y2 = x1, x2
        return dy1, dy2, None

torch.manual_seed(0)
B, l, dh = 2, 1024, 64
centers = F.normalize(torch.randn(64, dh), dim=-1)
qk = 64 * centers[torch.randint(0, 64, (B, l))] + 0.3 * torch.randn(B, l, dh)  # 64 clusters
v = torch.randn(B, l, dh)
full = F.scaled_dot_product_attention(qk, F.normalize(qk, dim=-1), v,
                                      attn_mask=~torch.eye(l, dtype=torch.bool))
for r in (1, 2, 4, 8):
    out = lsh_attention(qk, v, n_buckets=16, chunk=128, n_rounds=r)
    print(r, out.shape, round(((out - full).norm() / full.norm()).item(), 3))
# 1 torch.Size([2, 1024, 64]) 0.578   relative error to full attention falls with more rounds:
# 2 ... 0.319,  4 ... 0.23,  8 ... 0.186   (CPU, seed 0)

blocks = nn.ModuleList(RevBlock(64, 256) for _ in range(6))
x = torch.randn(2, 128, 64, requires_grad=True)
y1, y2 = RevStack.apply(x, x, blocks)
(y1 + y2).pow(2).mean().backward()
g_rev = [p.grad.clone() for p in blocks.parameters()]; gx_rev = x.grad.clone()
blocks.zero_grad(); x.grad = None                                     # reference: ordinary backprop
a, b2 = x, x
for blk in blocks:
    a, b2 = blk(a, b2)
(a + b2).pow(2).mean().backward()
print(max((p.grad - g).abs().max().item() for p, g in zip(blocks.parameters(), g_rev)),
      (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

> **Recomputation must see the same hashes:** The reversible backward pass runs attention a second time. If the random rotations are re-drawn, the recomputed $X_2$ is not the input of the forward pass, and the gradients are wrong without any error being raised. Implementations fix the hash seed per layer and step (or cache the bucket ids) so the recomputation is exact. The code above uses a deterministic stand-in for attention inside the reversible stack for that reason.

> **Buckets are a content-based sparsity pattern:** **Sparse attention**, **Longformer** and **BigBird** fix which pairs are scored by position. Reformer chooses them by **content**: the pairs with large $q\cdot k$ are exactly the ones that tend to share a bucket. The pattern changes with every input and every layer. **Linformer** and **Performer** instead approximate the whole softmax with low-rank or kernel features, and **FlashAttention** computes it exactly but without storing the $l\times l$ matrix.

> **When LSH attention pays off:** At the scale of the figure ($l=32$) LSH scores 512 pairs per round, half of the 1024 full ones, plus sorting overhead. The savings appear only when $l\gg m$: at $l=65{,}536$ and $m=64$ a round costs 512 times fewer scores. For sequences of a few thousand tokens, exact attention with a fused kernel is usually faster.

**Strengths**

- Attention cost $O(n_r\,l\,m)$ plus a sort instead of $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

**Limitations**

- 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

**Question:** Why does Reformer use the same projection for queries and keys?

- A. To halve the number of attention heads
- B. So a query and the keys most similar to it are hashed with the same function and land in the same bucket, with balanced query/key counts per bucket
- C. Because reversible layers require it
- D. To make the attention matrix symmetric, so only half of it is computed

**Answer:** B. So a query and the keys most similar to it are hashed with the same function and land in the same bucket, with balanced query/key counts per bucket — Bucketing only helps if $q_i$ and the keys it should attend to share a bucket. With $k_j=q_j/\lVert q_j\rVert$ they are hashed as one set of vectors. The side effect is that $q_i\cdot k_i$ is maximal, so self-attention is masked unless no other key is available.

**Question:** In a 12-layer reversible Reformer, what does training store for the backward pass?

- A. All 12 layers' activations, as in a standard Transformer
- B. Only the attention matrices
- C. Only the final layer's outputs (Y₁, Y₂); each layer's input is recomputed from its output during the backward pass
- D. Nothing; gradients are estimated by finite differences

**Answer:** C. Only the final layer's outputs (Y₁, Y₂); each layer's input is recomputed from its output during the backward pass — $X_2=Y_2-\mathrm{FF}(Y_1)$ and $X_1=Y_1-\mathrm{Attn}(X_2)$ rebuild the inputs exactly. Memory for activations is that of one layer instead of 12, and the cost is roughly one extra forward pass. The code block checks that the gradients match ordinary backprop to about $10^{-8}$.

**Key points**

- LSH attention: $h(x)=\arg\max[xR;-xR]$ with shared $k_j=q_j/\lVert q_j\rVert$; sort by bucket, attend within chunks of $m$ plus one chunk back: $O(n_r\,l\,m)$ scores plus an $O(l\log l)$ sort.
- Reversible layer: $Y_1=X_1+\mathrm{Attn}(X_2)$, $Y_2=X_2+\mathrm{FF}(Y_1)$, inverted exactly in the backward pass, so activations are stored once, not $n_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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
