Paper · 2021-09-09 · cs.CV, cs.LG
Is Attention Better Than Matrix Decomposition?
Hamburger is a global context block whose core is an unrolled matrix decomposition (VQ, CD or NMF) solved with a few fixed iterations, between two linear maps. Only the last update is differentiated (one-step gradient). Author-reported: HamNet 85.9 mIoU on PASCAL VOC test, 55.2 on PASCAL-Context val; HamGAN-strong FID 14.77 on ImageNet 128x128, versus 18.28 for SAGAN.
Self-attentionNon-negative matrix factorizationBackpropagation through timeSemantic segmentationglobal-contextmatrix-decompositionself-attention-alternativeone-step-gradientsemantic-segmentationimage-generation
arXivPDFCodeMarkdown16 min read
AI-compiled by claude-haiku-5-5 on 2026-11-12, not yet reviewed by a human. Every claim cites its source; check it when a detail matters.
In plain words
Many vision networks need to know how distant parts of an image relate to each other, for example that a patch of road and a patch of sky belong to the same scene. The usual tool is attention, where every position looks at every other position. It works, but it is costly in time and memory, and it is built by hand.
This paper asks whether a classic tool from numerical methods can do the job instead. The tool is matrix decomposition: a large table of features is explained as a small set of shared building blocks plus the way each feature mixes them. Keeping only the blocks gives a cleaned-up, low-rank version of the features that drops noise and fills in gaps from context.
The authors wrap such a decomposition in a block called Hamburger. The decomposition is an iterative procedure, and the block runs a few fixed steps of it. Training through many iterative steps is unstable, so the block only passes gradients through the last step. The result is a small module that the paper reports as competitive with attention on semantic segmentation and on image generation, with lower memory and time cost in its own measurements.
TL;DR
Hamburger is a global context block whose middle layer is a few fixed iterations of a matrix decomposition (vector quantization, concept decomposition or non-negative matrix factorization), with linear maps on either side §2.2.1. Gradients flow through only the last iteration §2.3. Author-reported, it beats self-attention and its variants on PASCAL VOC and PASCAL-Context segmentation and on ImageNet 128x128 GAN training, at lower memory cost §3.3, §3.4, §3.5. Check the code-vs-paper section before reimplementing: the released default architecture differs from the equations.
Problem
Stacking convolutions gives a network only local receptive fields, so long-range dependencies must be learned by extra global blocks §1. The dominant block, self-attention, forms an n-by-n score matrix, which costs O(n^2 d) time and needs n-by-n memory §2.2.2. Designing new global blocks is largely manual §2.2. The authors also note that the gradient of an iterative inner solver is the main obstacle when such a solver is placed inside a network §2.3.
Method
Setup §2.1. Arrange the features as a matrix X of size d by n, with n positions. Assume X = D C + E, where D is a dictionary, C holds the codes, and E is noise, with rank(D C) at most r and r much smaller than d and n eq. 1 eq. 2. Matrix decomposition is the minimisation of a reconstruction loss plus regularisers on D and C eq. 4. Solving this objective with an optimiser defines a computation graph, and that graph is used as the global context module §2.2.
Hamburger block §2.2.1.
- Lower bread: a linear map W_l from the C input channels to d channels.
- Ham: the matrix-decomposition solver M, which returns a low-rank reconstruction of its input eq. 7.
- Upper bread: a linear map W_u from d back to C channels.
- Output: the block is H(Z) = W_u M(W_l Z) eq. 5, and the block output is Y = Z + BN(H(Z)) eq. 6, a skip connection with batch normalisation.
The paper calls M a global nonlinearity §2.2.1.
Ham variants §2.2.2. Three matrix-decomposition models are studied, each solved with a fixed number of iterations K alg. 1 alg. 2 alg. 3:
- Vector quantisation (VQ). The hard assignment and Euclidean distance are replaced by a softmax over cosine similarities with temperature T, so the step is differentiable eq. 8 alg. 1. The dictionary update divides each atom by the total code weight it receives. A one-hot assignment is the limit T goes to 0 §2.2.2.
- Non-negative matrix factorisation (NMF). The constraint is enforced by a ReLU on the lower-bread output before the solver eq. 9 §2.2.2. The solver uses multiplicative update (MU) rules, which keep values non-negative alg. 2.
- Concept decomposition (CD), in appendix B. The dictionary uses spherical k-means-style unit-norm atoms, and the codes have a closed form C = (D^T D + beta I)^{-1} D^T X eq. 14 eq. 15 alg. 3 app. B. The paper states beta of 0.01 or 0.1 makes no difference in practice app. B.
Complexity of each solver step is O(n d r), against O(n^2 d) for self-attention, since r is much smaller than n. None of the three forms an n-by-n matrix §2.2.2.
One-step gradient §2.3. Unrolling an iterative solver for t steps and back-propagating through all of them (BPTT) gives a gradient with a long product of Jacobians eq. 10 eq. 11 eq. 12. The paper shows, under Lipschitz assumptions with constant below 1 on the step map, that the intermediate states converge linearly, that the Jacobian of the output approaches a fixed-point expression, and that the gradient through the early steps vanishes §2.3 app. C, Propositions 1 to 3. The method keeps only the first term of the series, the one through the last step eq. 13. This needs no gradient through the earlier steps and reduces time and space cost from O(t) to O(1) in the number of steps §2.3. Adding more terms was reported as worse than one step §2.3.
Segmentation integration §3.4 app. E.3. The 2048-channel output of a dilated ResNet-101 with output stride 8 goes through a 3x3 convolution with batch norm and ReLU down to 512 channels. The Hamburger block is applied on top of this, with d = 512, r = 64, NMF as the default ham, and K = 6. The released code adds further head layers (see Paper vs code).
Image generation integration §3.5 app. E.4. Hamburger replaces the self-attention position in a SAGAN/YLG-style GAN, at feature resolution 32x32, in both generator and discriminator. It uses NMF, with d = 8r and K = 6.
# Hamburger block with NMF as the ham [eq. 5] [alg. 2]
# Input: features (B, C, H, W); K = number of MU steps
# Output: features (B, C, H, W)
def hamburger(features, K):
# Lower bread: 1x1 conv to d channels, then ReLU so NMF gets
# non-negative input [§2.2.2]
# [code: seg/HamNet/hamburger/burger.py#L78-L80]
tokens = relu(lower_bread(features)) # (B, d, N), N = H * W
# Random non-negative dictionary with unit-norm columns [app. F]
# [code: seg/HamNet/hamburger/ham.py#L232-L240]
bases = unit_columns(random_uniform(B, d, r)) # (B, d, r)
# Initial codes: softmax of inner products over the atoms [app. F]
# [code: seg/HamNet/hamburger/ham.py#L49-L52]
coef = softmax(transpose(tokens) @ bases) # (B, N, r)
# K multiplicative-update steps with no gradient [alg. 2]
# [code: seg/HamNet/hamburger/ham.py#L48-L58, #L243-L258]
for step in range(K):
# Update the codes with the current dictionary [alg. 2]
coef = coef * (transpose(tokens) @ bases) / (
coef @ (transpose(bases) @ bases) + eps) # eps = 1e-6
# Update the dictionary with the new codes [alg. 2]
bases = bases * (tokens @ coef) / (
bases @ (transpose(coef) @ coef) + eps)
# One more code update; only this step carries a gradient [§2.3]
# [code: seg/HamNet/hamburger/ham.py#L86-L89, #L260-L268]
coef = coef * (transpose(tokens) @ bases) / (
coef @ (transpose(bases) @ bases) + eps)
# Low-rank reconstruction [eq. 7]
# [code: seg/HamNet/hamburger/ham.py#L91-L92]
recon = bases @ transpose(coef) # (B, d, N)
recon = reshape(recon, (B, d, H, W))
# Upper bread, batch norm and skip connection [eq. 6]
# The released default (V2) differs; see Paper vs code.
return features + batch_norm(upper_bread(recon))Hyperparameters
Values for the paper's reported runs. Values from the paper's appendix are cited to appendix sections; released-code values are cited to the code.
| Name | Value | Where | Notes |
|---|---|---|---|
| backbone (segmentation) | ResNet-101, output stride 8 | §3.4 app. E.3 settings.py | ImageNet pre-trained |
| squeeze conv before ham | 3x3 conv, BN, ReLU, 2048 to 512 | app. E.3 network.py | |
| latent dim d, atoms r | d = 512, r = 64 | app. E.3 settings.py | |
| ham type (segmentation) | NMF | §3.4 settings.py | |
| MD iterations K (train) | 6 | app. E.3 settings.py | |
| MD iterations K (test) | not stated | app. F | Paper: same K recommended; code: 6 settings.py |
| temperature T (NMF init) | 1 | app. F settings.py | "1/T" in the cosine softmax |
| CD regulariser beta | 0.1 | app. B settings.py | paper: 0.01 or 0.1 equal |
| optimiser | SGD, momentum 0.9 | app. E.3 settings.py | |
| base learning rate | 0.009 | app. E.3 settings.py | |
| LR schedule | poly, power 0.9, per iteration | app. E.3 train.py | |
| weight decay | 0.0001 | app. E.3 settings.py | |
| batch size (VOC) | 16 | app. E.3 settings.py | |
| iterations (VOC) | 60k | app. E.3 settings.py | |
| input crop | 513 x 513 | app. E.3 settings.py | |
| training scale range | 0.5 to 2.0 | app. E.3 settings.py | random flip and crop also used |
| test scales | multi-scale and flip, values not stated | app. E.3 | code: 0.5 to 1.75 settings.py |
| VOC fine-tune on trainval | LR divided by 10 | app. E.3 run.py | iteration count not stated in paper; code 20k settings.py |
| PASCAL-Context LR, batch, iterations | 0.002, 16, 25k | app. E.3 | not found in the released segmentation settings |
| ablation backbone | dilated ResNet-50, output stride 16 | app. E.1 | |
| ablation schedule | batch 12, 30k iterations (about 35 epochs), LR 0.009 | app. E.1 | not located in the released code |
| GAN latent dim d, atoms r (G) | d = 256, r = 32 | ops.py | paper: d = 8r |
| GAN latent dim d, atoms r (D) | d = 128, r = 16 | ops.py | paper: d = 8r |
| GAN K | 6 | app. E.4 ops.py ops.py | |
| GAN learning rates | G 1e-4, D 4e-4 | train_on_tpu_hamgan_baby.sh | paper: "same as SAGAN and YLG" §3.5 |
| GAN training steps | 2,000,000 (baby), 1,000,000 (strong) | train_on_tpu_hamgan_baby.sh train_on_tpu_hamgan_strong.sh | |
| GAN G and D update steps | 1 and 1 | train_on_tpu_hamgan_baby.sh | paper: not stated |
| FID sample size and runs | 50k samples, best of 6 runs | app. E.4 | paper reports best, not mean |
Results
All numbers are author-reported. Setup is given in each row.
Ablations on PASCAL VOC, ResNet-50 backbone, mIoU, best(mean) over 5 runs §3.1 app. E.1. Here "basic" is the full Hamburger with NMF.
| Setting | mIoU best(mean) | Extra params | Source |
|---|---|---|---|
| baseline (no context block; 32.67M params in total) | 75.9(75.7) | — | tab. 2 |
| basic (lower bread, NMF ham, upper bread) | 78.3(77.8) | +0.50M | tab. 2 |
| without ham | 75.8(75.6) | +0.50M | tab. 2 |
| without upper bread | 77.0(76.8) | +0.25M | tab. 2 |
| without lower bread | 77.3(77.2) | +0.25M | tab. 2 |
| only ham (parameter-free) | 77.0(76.8) | +0M | tab. 2 |
One-step gradient versus BPTT, same ablation setting §2.3 tab. 1.
| Method | One-step, mIoU best(mean) | BPTT, mIoU best(mean) | Source |
|---|---|---|---|
| VQ | 77.7(77.4) | 76.6(76.3) | tab. 1 |
| CD | 78.1(77.5) | 75.0(74.6) | tab. 1 |
| NMF | 78.3(77.8) | 77.4(77.0) | tab. 1 |
Cost against attention modules, one input of 1 x 512 x 128 x 128 on a TITAN Xp §3.3 app. E.2 tab. 3. Inference times are averaged over 20 repeats of 100 runs. MACs follow the cited FLOPs profiler.
| Method | Params | MACs | GPU load train / infer | GPU time train / infer | Source |
|---|---|---|---|---|---|
| SA (self-attention) | 1.00M | 292G | 5253MB / 2148MB | 242.0ms / 82.2ms | tab. 3 |
| DA (DANet) | 4.82M | 79.5G | 2395MB / 2203MB | 72.6ms / 64.4ms | tab. 3 |
| A^2 | 1.01M | 25.7G | 326MB / 165MB | 22.9ms / 8.0ms | tab. 3 |
| APC | 2.03M | 17.6G | 458MB / 264MB | 26.5ms / 11.6ms | tab. 3 |
| DM | 3.00M | 35.1G | 557MB / 268MB | 65.7ms / 23.3ms | tab. 3 |
| ACF | 0.75M | 79.5G | 1380MB / 627MB | 71.0ms / 22.6ms | tab. 3 |
| Ham (CD) | 0.50M | 16.2G | 162MB / 102MB | 20.0ms / 13.0ms | tab. 3 |
| Ham (NMF) | 0.50M | 17.6G | 202MB / 98MB | 15.6ms / 7.7ms | tab. 3 |
Semantic segmentation, ResNet-101, output stride 8 §3.4. Attention-based heads are marked with an asterisk in the paper. HamNet is the Hamburger network. The VOC rows are on the test set without COCO pre-training.
| Method | PASCAL VOC test mIoU (%) | Source |
|---|---|---|
| PSPNet | 82.6 | tab. 4 |
| DFN* | 82.7 | tab. 4 |
| EncNet | 82.9 | tab. 4 |
| DANet* | 82.6 | tab. 4 |
| DMNet* | 84.4 | tab. 4 |
| APCNet* | 84.2 | tab. 4 |
| CFNet* | 84.2 | tab. 4 |
| SpyGR* | 84.2 | tab. 4 |
| SANet* | 83.2 | tab. 4 |
| OCR* | 84.3 | tab. 4 |
| HamNet | 85.9 | tab. 4 |
| Method | PASCAL-Context val mIoU (%) | Source |
|---|---|---|
| PSPNet | 47.8 | tab. 5 |
| SGR* | 50.8 | tab. 5 |
| EncNet | 51.7 | tab. 5 |
| DANet* | 52.6 | tab. 5 |
| EMANet* | 53.1 | tab. 5 |
| DMNet* | 54.4 | tab. 5 |
| APCNet* | 54.7 | tab. 5 |
| CFNet* | 54.0 | tab. 5 |
| SpyGR* | 52.8 | tab. 5 |
| SANet* | 53.0 | tab. 5 |
| OCR* | 54.8 | tab. 5 |
| HamNet | 55.2 | tab. 5 |
Image generation, ImageNet 128x128, FID (lower is better) §3.5 tab. 6. Rows marked * are copied from SAGAN's tables. Setup: 50k samples, best of 6 runs app. E.4.
| Method | FID | Source |
|---|---|---|
| SNGAN-projection* | 27.62 | tab. 6 |
| SAGAN* | 18.28 | tab. 6 |
| HamGAN-baby (Hamburger replaces self-attention) | 16.05 | tab. 6 |
| YLG | 15.94 | tab. 6 |
| HamGAN-strong (Hamburger in the YLG codebase) | 14.77 | tab. 6 |
The paper also reports, on TPUv3, that HamGAN-strong trains about 15% faster in total and its context module about 3.6 times faster than YLG's, measured as iterations per second with and without the context modules §3.5.
Ablation on initialisation, same setting app. F tab. 8. Values are best(mean) mIoU.
| Init | NMF | CD | VQ | Source |
|---|---|---|---|---|
| fixed | 77.4(77.3) | 77.7(77.4) | 77.3(76.9) | tab. 8 |
| learned | 76.8(76.5) | 75.0(73.7) | 75.9(75.8) | tab. 8 |
| random | 78.3(77.8) | 77.9(77.3) | 77.7(77.4) | tab. 8 |
| online (warm start) | 77.8(77.5) | 78.1(77.5) | 78.0(77.2) | tab. 8 |
Temperature T with CD ham app. F tab. 9.
| T | mIoU best(mean) | Source |
|---|---|---|
| 1 | 77.1(77.0) | tab. 9 |
| 0.1 | 78.2(77.5) | tab. 9 |
| 0.01 | 78.1(77.5) | tab. 9 |
Other experiments in the paper. The paper shows how the iteration count K changes results for VQ, CD and NMF, and that K between 3 and 6 is usually enough §3.1 app. F fig. 4 fig. 7 fig. 8 fig. 9. It also shows the effect of the latent dimension d and atom count r §3.1 fig. 3, and spectral energy concentration before and after the block on VOC §3.2 fig. 5 fig. 6.
Paper vs code
Code: the official repository Gsunshine/Enjoy-Hamburger, at commit
d9b51f6f197486df68c6e059e396520680157c08, under GPL-3.0 (root LICENSE).
The repository's code covers the segmentation model (seg/HamNet), a
mmseg-based variant (seg_mm, seg_light_ham) and the TensorFlow GAN
(gan/HamGAN). This card paraphrases and cites the code; it does not quote
it. Only the segmentation code and the GAN code were checked.
- Default architecture is not the one in the equations. Equations 5 and
6 give W_u M(W_l Z) and Z + BN(H(Z)) eq. 5 eq. 6. The released
segmentation default is
VERSION = 'V2'settings.py. In V2, the upper bread is a 1x1 convolution without batch norm burger.py. An extra 1x1 ConvBNReLU "cheese" block sits between the ham and the upper bread burger.py burger.py. The output ends in a ReLU after the residual sum burger.py. Variant V1 has batch norm after the upper bread burger.py and the same ReLU after the sum burger.py. The paper does not say which variant produced the reported segmentation numbers §3.4. - NMF initial codes are not cosine-based. The paper initialises C = softmax(cosine(D, X) / T), with T = 1 for NMF app. F. The PyTorch code takes raw inner products of the (un-normalised) features with the dictionary, then a softmax with inverse temperature 1 ham.py ham.py. The TensorFlow GAN code does the same ham.py.
- Random dictionary normalisation differs between the two codebases. The paper says entries are drawn from Uniform(0, 1) app. F. The PyTorch NMF normalises each atom to unit length after sampling ham.py. The TensorFlow GAN does not normalise ham.py.
- One-step gradient is implemented, but not as the single equation.
The paper's one-step gradient is the product of the output Jacobian at the
fixed point and the derivative of the update map eq. 13. The PyTorch code
runs K no-gradient steps, then one differentiable code update with the
dictionary held constant ham.py
ham.py. The TensorFlow GAN code
applies
stop_gradientto codes and dictionary, then one update ham.py. The CD version solves for the codes in closed form with gradient, instead of using an MU step ham.py. - Temperature. The paper finds a low temperature better for CD and VQ, with the CD ablation at T = 0.1 and 0.01 beating T = 1 app. F tab. 9. The released segmentation default is INV_T = 1 settings.py, which is the paper's NMF setting. The GAN CD code uses an inverse temperature of 100, i.e. T = 0.01 ham.py.
- Segmentation head. The paper says the head "is the same as in the ablation experiments" app. E.3. The released model adds a 3x3 ConvBNReLU to 256 channels, dropout with p = 0.1, and a 1x1 classifier network.py. These are not in the paper's text.
- Learned scalar gate in the GAN. The GAN Hamburger returns the shortcut plus a learned scalar sigma times the block output, with sigma initialised to zero ops.py. This gate does not appear in the paper's equations.
- GAN latent size. The paper says d equals the input channel count app. E.4. The released scripts set d = 256 for the generator and 128 for the discriminator ops.py ops.py, and the lower bread maps the input to d ops.py. I did not verify the input channel count at each GAN placement, so whether the two agree is not stated.
- PASCAL-Context and ablation settings are not in the release. The
paper gives learning rate 0.002 with 25k iterations for PASCAL-Context
app. E.3, and batch 12, 30k iterations for the ablations app. E.1. The
released
seg/HamNet/settings.pyholds a single learning rate of 9e-3 and 60k iterations settings.py settings.py. I did not find the other configurations. - Fine-tuning on trainval. The paper says the learning rate is divided by ten for the final trainval fine-tune, without an iteration count app. E.3. The code divides by ten and runs 20k iterations run.py settings.py.
- Parameter groups. The code uses three SGD parameter groups at learning rate 1x, 1x and 2x train.py. The paper does not mention them. The 1x group holds convolution weights, the second holds batch-norm and coefficient parameters without weight decay train.py. I did not read which parameters fall into the 2x group.
- Hard-coded CUDA. Basis initialisation and the CD inverse call
.cuda()directly ham.py ham.py.
Checked and consistent: ResNet-101 with output stride 8, crop size 513, training scale range, batch size 16, 60k iterations, learning rate 0.009, power 0.9, weight decay 1e-4, K = 6, d = 512, r = 64 settings.py settings.py settings.py settings.py settings.py settings.py.
Pitfalls
- Read the released default, not the equations. Implementing only equations 5 and 6 gives a different network from the released V2 default. See Paper vs code item 1 before reproducing the reported segmentation numbers.
- Use the mean when comparing ablations. The ablations report best(mean) over five runs §3.1. Compare the mean values: "basic" reaches 77.8 mean against a baseline of 75.7 mean tab. 2. Report the mean, not the best.
- The one-step gradient is the central trick, and it is not free of choices. The paper shows BPTT is worse on all three ham types tab. 1, but it also reports that adding more gradient terms was worse than one step §2.3. The released code changes the single step (see Paper vs code item 4), so reproduce the code's variant if you want its numbers.
- Small numerical details matter for MU updates. The paper warns that dictionary or code entries near zero are unsuitable for the MU rule, and it recommends a higher temperature for the NMF initialisation app. F. The code's denominators use 1e-6 ham.py ham.py.
- Temperature is ham-specific. The CD and VQ runs prefer low temperatures app. F tab. 9, but the NMF runs use T = 1 settings.py. Do not reuse one T across all three hams.
- Iteration count is a regulariser. The paper treats a few iterations as early stopping; full convergence overfits the simple prior §3.1 app. F. It recommends the same K at training and test time, and reports more iterations at evaluation as worse app. F.
- Initialisation scheme matters. Random initialisation is the paper's general recommendation, and a learned initialisation is the worst app. F tab. 8. The online warm start scored best only for CD in that table. The released default is random initialisation (RAND_INIT = True settings.py).
- Speed numbers are hardware-specific. Memory and time are measured on a TITAN Xp with a single 512-channel input app. E.2, and the GAN timing on TPUv3 §3.5. All are author-reported.
- FID is best of six runs. The paper reports the best FID across six runs app. E.4, which is optimistic compared with a mean.
- Hard-coded CUDA. The reference code assumes a GPU (see Paper vs code item 12). Port the initialisation and the CD inverse to the device of the input.
- Licence. The repository is GPL-3.0. Do not copy code verbatim into a permissively licensed project. Re-implement from the equations and the pseudocode above.
Lineage
- Builds on: self-attention, from the Transformer paper §2.1 eq. 3. The paper names it as the representative global context block it replaces.
- Builds on: vector quantisation, concept decomposition and non-negative matrix factorisation with multiplicative updates, which the paper cites as classic matrix-decomposition models §2.2.2 app. B alg. 2.
- Builds on: truncated back-propagation through time, which the paper uses as the baseline gradient §2.3.
- Compared against: self-attention and DANet, A^2 Net, APCNet, DMNet and CFNet attention modules §3.3 tab. 3, and the segmentation models in tab. 4 and tab. 5, plus SAGAN and YLG for image generation §3.5 tab. 6.
- Superseded by: none known in this wiki.
- Notes: the paper lists extension to natural language, positional information, and equivariance as future work app. I.
Source and license
Adapted from “Is Attention Better Than Matrix Decomposition?” by Zhengyang Geng, Meng-Hao Guo, Hongxu Chen, Xia Li, Ke Wei, Zhouchen Lin (arXiv:2109.04553), used under CC BY 4.0. Changes: condensed and restructured for implementation, with tables, equations and algorithms taken from the paper and its code, each cited to its source. Not affiliated with or endorsed by the authors. Code citations refer to https://github.com/Gsunshine/Enjoy-Hamburger at commit d9b51f6f1974 (GPL-3.0). Any quoted code is shown under that license.