Full search page →

ML 05 · Attention and Vision Transformers

Machine LearningIntermediate25 minUpdated Nov 6, 2026

Needs: ML 03 · Convolution, Image Filtering and CNNs

Navigate: this page and this track: Navigate: this page and this track
Explore this chapter 1 interactive experiment

Compare bidirectional and causal attention using the same query, keys and values.

What you’ll learn

  • Trace queries, keys, values and attention weights.
  • Construct multi-head, masked and cross-attention.
  • Explain positional information and the Transformer block.
  • Compare patch-based, windowed and hybrid vision models.
  • Separate attention’s arithmetic, memory traffic and context trade-offs.

The big picture

A CNN (ML 03) moves information through fixed local neighborhoods: a pixel learns about a distant pixel only after many layers. Attention lets every location decide, based on its current content, which other locations to read from, in a single step. To recognize a bird, a patch containing its head can directly consult a distant patch containing its wing.

The attention idea came from machine translation with recurrent networks: ML 04 shows how it removed the single-vector bottleneck of encoder–decoder RNNs. The Transformer of Vaswani et al. [1] went further and removed recurrence entirely, building both encoder and decoder from attention and small per-token networks. The Vision Transformer (ViT) of Dosovitskiy et al. [2] applied the Transformer encoder almost unchanged to sequences of image patches. Bishop and Bishop [10] give a modern textbook treatment, and the surveys discussed in the Modern view [3], [11], [12] map the many vision variants. Afterwards, DLCV 02 compares CNN and Transformer backbones for classification in practice, and ML 06 shows how such backbones are pretrained without labels.

Self-attention: queries, keys and values

Plain version. A query scores the available keys; normalized scores weight the values. This lets each token select content from the tokens it can access.

Precise version. Stack NN tokens as the rows of X∈RN×DX\in\mathbb{R}^{N\times D}, where DD is the model width. Three learned matrices project them:

Q=XWQ,K=XWK,V=XWV,Q=XW_Q,\qquad K=XW_K,\qquad V=XW_V,

with WQ,WK∈RD×dkW_Q,W_K\in\mathbb{R}^{D\times d_k} and WV∈RD×dvW_V\in\mathbb{R}^{D\times d_v}. Scaled dot-product attention [1] is

Attention⁡(Q,K,V)=softmax⁡row ⁣(QK⊤dk)V=AV.\operatorname{Attention}(Q,K,V)=\operatorname{softmax}_{\text{row}}\!\left(\frac{QK^\top}{\sqrt{d_k}}\right)V=AV .

QK⊤QK^\top is an N×NN\times N matrix of scores: entry (i,j)(i,j) is the dot product of query ii with key jj, a measure of how relevant token jj is to token ii. The row-wise softmax turns each row into nonnegative weights that sum to one, giving the attention matrix AA. The output Y=AV∈RN×dvY=AV\in\mathbb{R}^{N\times d_v} has one row per token: row ii is ∑jAijvj\sum_j A_{ij}v_j, a weighted average of value vectors.

Why three different projections? If queries and keys were the same vector, every token would match itself most strongly, and relevance would be forced to be symmetric. Separate WQW_Q and WKW_K let “what I seek” differ from “what I offer” (an eye patch can seek a nose without being one), and a separate WVW_V lets “what I offer” differ from “what I pass on”.

Why divide by dk\sqrt{d_k}? If the components of a query and a key are independent with mean zero and variance one, their dot product q⋅k=∑l=1dkqlklq\cdot k=\sum_{l=1}^{d_k}q_lk_l has mean zero and variance dkd_k. Without scaling, larger heads produce larger scores, the softmax saturates (almost all weight on one token), and its gradients become tiny. Dividing by dk\sqrt{d_k} restores unit variance. It is a scale convention, not a normalization of each query to unit length.

Content, not position, decides who talks to whom. Unlike a convolution, whose weights are tied to relative positions, attention weights are computed from the data at run time. A related consequence: self-attention is permutation-equivariant. Shuffle the input tokens, and the outputs are shuffled in the same way, because nothing in the formula refers to token order. The snippet checks both the shapes and this symmetry.

Code · Python · 15 lines
import torch

torch.manual_seed(0)
X = torch.randn(5, 8)                   # N=5, D=8
Wq, Wk, Wv = [torch.randn(8, 4) for _ in range(3)]
def attention(x):
    q, k, v = x @ Wq, x @ Wk, x @ Wv
    a = (q @ k.T / q.shape[-1]**.5).softmax(dim=-1)
    return a @ v, a
y, a = attention(X)
perm = torch.tensor([3, 0, 4, 1, 2])
yp, _ = attention(X[perm])
assert torch.allclose(a.sum(-1), torch.ones(5), atol=1e-6)
assert torch.allclose(yp, y[perm], atol=1e-5)
print("output shape:", tuple(y.shape))

This symmetry suits sets, but an image is not a set of patches: a face with its eyes below its mouth is not a face. Positional information, introduced below, breaks the symmetry.

Multi-head attention

Plain version. Run several attention operations in parallel, each with its own smaller projections, so different heads can track different relationships (nearby texture, the same object, symmetric parts). Then concatenate their outputs and mix them.

Precise version. With hh heads, head rr has its own WQ(r),WK(r),WV(r)∈RD×dkW_Q^{(r)},W_K^{(r)},W_V^{(r)}\in\mathbb{R}^{D\times d_k}, usually with dk=dv=D/hd_k=d_v=D/h:

head⁡r=Attention⁡ ⁣(XWQ(r),XWK(r),XWV(r)),MHA⁡(X)=[head⁡1,…,head⁡h] WO,\operatorname{head}_r=\operatorname{Attention}\!\left(XW_Q^{(r)},XW_K^{(r)},XW_V^{(r)}\right),\qquad \operatorname{MHA}(X)=\big[\operatorname{head}_1,\dots,\operatorname{head}_h\big]\,W_O,

where the brackets concatenate the hh outputs of width D/hD/h back to width DD, and WO∈RD×DW_O\in\mathbb{R}^{D\times D} mixes them. Because each head has width D/hD/h, multi-head attention costs about the same as one full-width head, and its projections have 4D24D^2 weights in total (plus biases). Heads are not guaranteed to learn human-readable roles; some are redundant and can be pruned.

The implementation below splits the projections into heads, computes the scores per head, concatenates and projects, and matches nn.MultiheadAttention exactly. It also shows a causal mask: setting forbidden scores to −∞-\infty before the softmax gives them exactly zero weight.

Code · Python · 29 lines
import torch
from torch import nn

torch.manual_seed(0)
B, N, D, h = 2, 6, 16, 4
mha = nn.MultiheadAttention(D, num_heads=h, batch_first=True, bias=False)
X = torch.randn(B, N, D)

def multi_head(x):
    Wq, Wk, Wv = mha.in_proj_weight.chunk(3)          # each D x D (rows = outputs)
    q, k, v = x @ Wq.T, x @ Wk.T, x @ Wv.T              # B x N x D
    split = lambda t: t.view(B, N, h, D // h).transpose(1, 2)   # B x h x N x d_k
    q, k, v = split(q), split(k), split(v)
    scores = q @ k.transpose(-2, -1) / (D // h) ** 0.5  # B x h x N x N
    A = scores.softmax(dim=-1)
    heads = A @ v                                       # B x h x N x d_k
    concat = heads.transpose(1, 2).reshape(B, N, D)     # put the heads side by side
    return concat @ mha.out_proj.weight.T, A

ours, A = multi_head(X)
ref, _ = mha(X, X, X)
print("matches nn.MultiheadAttention:", torch.allclose(ours, ref, atol=1e-5))
print("attention tensor:", tuple(A.shape), "| parameters:",
      sum(p.numel() for p in mha.parameters()), "= 4 * D^2 =", 4 * D * D)

# Causal mask: query i may only read keys j <= i
causal = torch.triu(torch.ones(N, N, dtype=torch.bool), diagonal=1)   # True = forbidden
out_c, w_c = mha(X, X, X, attn_mask=causal)
print("no weight on the future:", torch.all(w_c[:, causal] == 0).item())

It prints True, an attention tensor of shape (2, 4, 6, 6) (batch, heads, queries, keys), 1024 = 4 * D^2 = 1024, and True for the causal check. Production code can use torch.nn.functional.scaled_dot_product_attention, which dispatches to fused kernels when supported [7]. Do not copy the Boolean mask unchanged: nn.MultiheadAttention uses True for forbidden positions, while scaled_dot_product_attention uses True for allowed positions. Also pass dropout_p=0.0 to the functional call during evaluation; it does not inspect a module’s training flag. Check mask semantics and dropout explicitly when replacing the teaching implementation.

Three ways to connect tokens

Plain version. Which tokens a query is allowed to read is part of the model’s design, expressed as a mask on the score matrix.

MechanismA query readsTypical use
Bidirectional self-attentionAll tokens of the same sequenceViT and other image encoders
Causal (masked) self-attentionItself and earlier positions onlyNext-token generation, autoregressive image models
Cross-attentionTokens from a different sequenceA decoder reading an encoder; image tokens reading text
Three eight by eight matrices: fully blue for unrestricted attention, a lower-triangular blue region for the causal mask, and two blue blocks on the diagonal for two local windows.
Figure 1 — Attention masks: blue entries are allowed, white entries are forbidden. Causal generation also shifts its inputs by one position so a target cannot simply be copied.

In cross-attention, queries come from one sequence XX and keys and values from another sequence ZZ: Q=XWQQ=XW_Q, K=ZWKK=ZW_K, V=ZWVV=ZW_V. The score matrix has shape NX×NZN_X\times N_Z, and the output has one row per query. This is how the original Transformer decoder reads its encoder, how image captioners read image features, and how text-to-image diffusion models read a text prompt (ML 08) without being autoregressive over image patches.

Attention weights are part of a computation, not automatically an explanation. A large weight can multiply an uninformative value, and the residual and MLP paths also shape the output.

Positional information

Plain version. Content-only self-attention has no built-in position labels. Position embeddings, relative information or position-dependent masks supply structure.

Sinusoidal encodings. The original Transformer [1] adds a fixed vector ppos∈RDp_{pos}\in\mathbb{R}^D to the token at position pospos:

ppos, 2i=sin⁡ ⁣(pos100002i/D),ppos, 2i+1=cos⁡ ⁣(pos100002i/D),i=0,…,D2−1.p_{pos,\,2i}=\sin\!\left(\frac{pos}{10000^{2i/D}}\right),\qquad p_{pos,\,2i+1}=\cos\!\left(\frac{pos}{10000^{2i/D}}\right),\qquad i=0,\dots,\tfrac{D}{2}-1 .

Each pair of dimensions (2i,2i+1)(2i,2i+1) is a point rotating around a circle at angular frequency ωi=10000−2i/D\omega_i=10000^{-2i/D}, from fast (one radian per position) to very slow. Two properties follow from the angle-addition formulas. First, for any fixed offset kk, ppos+k=pposRkp_{pos+k}=p_{pos}R_k for a block-diagonal rotation RkR_k that does not depend on pospos; a linear layer can therefore learn to “look kk positions ahead”. Second, pm⋅pn=∑icos⁡(ωi(m−n))p_{m}\cdot p_{n}=\sum_i\cos\big(\omega_i(m-n)\big) depends only on the offset m−nm-n (Figure 2, middle).

Left: a heatmap of sinusoidal encodings with position on the horizontal axis and 128 dimensions on the vertical axis, showing fast oscillations in low dimensions and slow ones in high dimensions. Middle: the dot product of position 20's encoding with all positions, peaking at 20 and falling off with distance. Right: a 14 by 14 grid colored by similarity of a 2-D row-plus-column encoding to a starred patch, brightest near the star and along its row and column.
Figure 2 — Sinusoidal positional encodings. Left: each dimension pair oscillates at its own frequency. Middle: similarity between encodings depends on the offset. Right: concatenating row and column encodings gives a 2-D encoding for a 14 × 14 patch grid.
Code · Python · 20 lines
import numpy as np

def sinusoidal(n_pos, D):
    pos = np.arange(n_pos)[:, None]
    omega = 1.0 / 10000 ** (np.arange(0, D, 2) / D)    # one frequency per sin/cos pair
    pe = np.zeros((n_pos, D))
    pe[:, 0::2] = np.sin(pos * omega)
    pe[:, 1::2] = np.cos(pos * omega)
    return pe, omega

pe, omega = sinusoidal(100, 16)
k = 7                                                 # a fixed offset
# block-diagonal rotation that maps p_pos to p_{pos+k}, the same for every pos
R = np.zeros((16, 16))
for i, w in enumerate(omega):
    c, s = np.cos(w * k), np.sin(w * k)
    R[2 * i:2 * i + 2, 2 * i:2 * i + 2] = [[c, -s], [s, c]]
print("p[pos+k] == p[pos] @ R for all pos:", np.allclose(pe[:-k] @ R, pe[k:]))
print("dot products depend only on offset:",
      np.isclose(pe[10] @ pe[17], pe[50] @ pe[57]))

Both checks print True.

Other schemes.

  • Learned absolute embeddings: a trainable vector per position, as in ViT [2]. ViT’s 1-D learned embeddings, indexed by raster order, worked about as well as explicitly 2-D ones; after training, embeddings of patches in the same row or column became similar, so the model learned the grid by itself. At a new resolution, the grid of embeddings is resized by 2-D interpolation before fine-tuning.
  • Relative position representations (Shaw et al. [17]) add a learned term that depends on the offset j−ij-i to the score between tokens ii and jj. Swin [5] adds a learned relative position bias table to each window’s scores.
  • Rotary position embedding (RoPE) (Su et al. [16]) rotates each query and key by an angle proportional to its position, using the same rotations as the sinusoidal code above. The score qm⊤knq_m^\top k_n then depends on the positions only through m−nm-n. RoPE is standard in large language models and increasingly used in vision with separate rotations for the two image axes.
  • No explicit encoding: convolutions inside the network, as in CvT [19], or zero padding at borders can leak enough position information on their own.

The Transformer block

Plain version. A block alternates two jobs. Attention lets tokens exchange information; a small MLP then processes each token on its own. Residual connections and normalization keep the stack stable.

Precise version. The pre-norm block used by ViT and most modern models is

U=X+MHA⁡ ⁣(LN⁡(X)),Y=U+MLP⁡ ⁣(LN⁡(U)),MLP⁡(u)=W2 GELU⁡(W1u+b1)+b2.U=X+\operatorname{MHA}\!\big(\operatorname{LN}(X)\big),\qquad Y=U+\operatorname{MLP}\!\big(\operatorname{LN}(U)\big),\qquad \operatorname{MLP}(u)=W_2\,\operatorname{GELU}(W_1u+b_1)+b_2 .

LN⁡\operatorname{LN} is layer normalization [14]: it standardizes each token’s DD features to zero mean and unit variance, then applies a learned scale and shift; unlike BatchNorm, it does not depend on other samples in the batch. The MLP expands each token from DD to typically 4D4D hidden units, applies the GELU nonlinearity [26] (GELU⁡(z)=z Φ(z)\operatorname{GELU}(z)=z\,\Phi(z), where Φ\Phi is the standard normal CDF), and projects back. The residual additions mean each sub-layer only learns a correction, exactly as in ResNet.

A left-to-right block diagram: X, LayerNorm, multi-head self-attention, a plus node, LayerNorm, MLP with D to 4D to D and GELU, a plus node, Y; two curved orange arrows carry X around the attention branch and the intermediate result around the MLP branch to the plus nodes.
Figure 3 — A pre-norm Transformer block. Attention mixes information across tokens; the MLP transforms each token separately; residual paths (orange) carry the input around each branch.

The original Transformer placed LayerNorm after each residual addition (post-norm). Xiong et al. [15] showed that with post-norm the gradients near the output are large at initialization, which is why it needs a learning-rate warm-up, whereas pre-norm keeps gradients well behaved and can train without one. So “a Transformer” is not fully specified until you say where the normalization goes. Counting weights per block: 4D24D^2 for attention and 8D28D^2 for the MLP, so about 12D212D^2, two thirds of it in the MLP.

The Vision Transformer (ViT)

Plain version. Cut the image into square patches, turn each patch into a vector, add position information, and feed the sequence to a standard Transformer encoder. Read the answer from a special extra token.

Patchify. For an image with H×WH\times W pixels and CC channels, and patch size PP dividing both HH and WW, there are N=HW/P2N=HW/P^2 patches. Flatten each into xipatch∈RP2Cx_i^{\text{patch}}\in\mathbb{R}^{P^2C} and project linearly:

z0=[ xcls;  x1patchE;  … ;  xNpatchE ]+Epos,z_0=\big[\,x_{\text{cls}};\;x_1^{\text{patch}}E;\;\dots;\;x_N^{\text{patch}}E\,\big]+E_{\text{pos}},

where E∈RP2C×DE\in\mathbb{R}^{P^2C\times D} is the learned patch embedding, xcls∈RDx_{\text{cls}}\in\mathbb{R}^D is a learned class token prepended to the sequence, and Epos∈R(N+1)×DE_{\text{pos}}\in\mathbb{R}^{(N+1)\times D} holds learned position embeddings. After LL blocks, a LayerNorm and a linear head applied to the class token’s output give the logits. Averaging all patch outputs (mean pooling) is an equally common alternative to the class token.

The astronaut test image resized to 224 by 224 and overlaid with a seven by seven grid of white lines; on the right, the first twelve patches shown as a row of small tiles in raster order, followed by four numbered steps: cut into patches, flatten and multiply by E, add position embeddings and optionally a CLS token, and feed the N by D sequence to the encoder.
Figure 4 — Patchify. A 32-pixel grid is drawn for readability; ViT-Base uses 16 × 16 patches, which turn a 224 × 224 image into 196 tokens.

A linear map applied to non-overlapping P×PP\times P patches is exactly a convolution with kernel size and stride both equal to PP, which is how implementations write it:

Code · Python · 20 lines
import torch
from torch import nn

torch.manual_seed(0)
B, C, H, W, P, D = 2, 3, 32, 32, 8, 48
x = torch.randn(B, C, H, W)

# 1) explicit: cut into P x P patches, flatten each, multiply by E
patches = x.unfold(2, P, P).unfold(3, P, P)                 # B, C, H/P, W/P, P, P
patches = patches.permute(0, 2, 3, 1, 4, 5).reshape(B, -1, C * P * P)   # B, N, P*P*C
E = torch.randn(C * P * P, D) * 0.02
tokens_explicit = patches @ E                                # B, N, D

# 2) the same linear map written as a convolution with kernel = stride = P
conv = nn.Conv2d(C, D, kernel_size=P, stride=P, bias=False)
conv.weight.data = E.T.reshape(D, C, P, P)
tokens_conv = conv(x).flatten(2).transpose(1, 2)             # B, N, D

print("tokens:", tuple(tokens_conv.shape), "| identical:",
      torch.allclose(tokens_explicit, tokens_conv, atol=1e-5))

It prints 16 tokens of width 48 and True.

Sizes. The standard configurations are ViT-Base (12 blocks, D=768D=768, 12 heads, about 86 million parameters), ViT-Large (24 blocks, D=1024D=1024, 16 heads) and ViT-Huge (32 blocks, D=1280D=1280, 16 heads) [2]. “ViT-B/16” means Base with 16×1616\times16 patches. Patch size is the main compute knob: halving PP quadruples NN and multiplies the attention-score count by sixteen. Small patches keep fine detail; large patches are cheap but lose anything finer than the patch, which no later layer can recover.

The data lesson. Dosovitskiy et al. [2] found that ViT trained only on ImageNet-1k (about 1.3 million images) was somewhat worse than comparable ResNets, but when pretrained on ImageNet-21k (14 million) or JFT-300M (300 million) and then fine-tuned, it matched or exceeded them at lower pretraining cost. Their explanation is inductive bias: a CNN assumes locality and translation equivariance in every layer, whereas a ViT is local only within the patch embedding and must learn spatial relationships from data. Raghu et al. [18] compared the internal representations of ViTs and ResNets and found that ViTs have more uniform representations across layers, that their lower layers attend both locally and globally, and that learning local attention in early layers requires large-scale pretraining.

Code: a tiny ViT trained on digits

This complete example trains a small ViT on the same 8×88\times8 digits as the CNN in ML 03, with 2×22\times2 patches (16 tokens), a class token, learned positions and four pre-norm blocks. It runs on CPU in about half a minute.

Code · Python · 52 lines
import copy
import numpy as np
import torch
from torch import nn
from sklearn.datasets import load_digits
from sklearn.model_selection import train_test_split

torch.manual_seed(0)
torch.set_num_threads(1)

class TinyViT(nn.Module):
    def __init__(self, img=8, patch=2, chans=1, D=64, depth=4, heads=4, classes=10):
        super().__init__()
        N = (img // patch) ** 2
        self.patch = nn.Conv2d(chans, D, kernel_size=patch, stride=patch)   # patchify + E
        self.cls = nn.Parameter(torch.zeros(1, 1, D))                       # [CLS] token
        self.pos = nn.Parameter(torch.randn(1, N + 1, D) * .02)             # learned positions
        layer = nn.TransformerEncoderLayer(D, heads, dim_feedforward=4 * D, dropout=0.1,
                                           activation="gelu", batch_first=True,
                                           norm_first=True)                 # pre-norm block
        self.blocks = nn.TransformerEncoder(layer, depth, enable_nested_tensor=False)
        self.norm, self.head = nn.LayerNorm(D), nn.Linear(D, classes)

    def forward(self, x):
        t = self.patch(x).flatten(2).transpose(1, 2)                         # B, N, D
        t = torch.cat([self.cls.expand(len(t), -1, -1), t], dim=1) + self.pos
        return self.head(self.norm(self.blocks(t))[:, 0])                    # read [CLS]

d = load_digits()
X = torch.tensor(d.images[:, None] / 16.0, dtype=torch.float32)
y = torch.tensor(d.target)
train, test = train_test_split(np.arange(len(y)), test_size=.2, stratify=d.target,
                               random_state=0)
train, val = train_test_split(train, test_size=.2, stratify=d.target[train], random_state=1)
model = TinyViT()
opt = torch.optim.AdamW(model.parameters(), lr=1e-3, weight_decay=0.05)
best = (float("inf"), None)
for epoch in range(30):
    model.train()
    for idx in torch.tensor(train)[torch.randperm(len(train))].split(64):
        loss = nn.functional.cross_entropy(model(X[idx]), y[idx])
        opt.zero_grad(); loss.backward(); opt.step()
    model.eval()
    with torch.no_grad():
        v = nn.functional.cross_entropy(model(X[val]), y[val]).item()
    if v < best[0]:
        best = (v, copy.deepcopy(model.state_dict()))
model.load_state_dict(best[1]); model.eval()
with torch.no_grad():
    acc = (model(X[test]).argmax(1) == y[test]).float().mean().item()
print("parameters:", sum(p.numel() for p in model.parameters()))
print("best validation loss:", round(best[0], 4), "| held-out accuracy:", round(acc, 4))

On our run it uses about 202,000 parameters and reaches about 95% held-out accuracy, while the CNN in ML 03 reached about 96% with fewer than 10,000 parameters and the same split. On a small dataset, the CNN’s built-in locality is worth a factor of twenty in parameters. This is the data lesson in miniature, not a verdict on large-scale performance.

Optional: ViT (in the Paper guides). Read the original figure, evidence, design choices and limitations.

Training recipes: DeiT and beyond

Plain version. Much of the early gap between ViTs and CNNs on ImageNet-sized data turned out to be about training, not architecture.

DeiT (Touvron et al. [4]) trained ViTs competitively on ImageNet-1k alone using strong data augmentation (RandAugment, Mixup, CutMix, random erasing), heavy regularization (stochastic depth, label smoothing) and long schedules. It also introduced a distillation token: an extra learned token, like the class token, whose output is trained to match the predictions of a pretrained CNN teacher. The CNN’s inductive bias is thus transferred through its predictions. DeiT III [27] later showed that a simpler, carefully tuned supervised recipe (a lightweight “3-Augment” scheme, simple cropping and a binary cross-entropy loss) makes plain ViTs stronger still. Steiner et al. [25] ran a large study of data, augmentation and regularization (“AugReg”) and found that the right combination of augmentation, regularization and compute can match models trained on roughly ten times more data.

The general lesson, repeated in ML 03’s discussion of ConvNeXt: compare architectures only under matched data, augmentation, resolution, schedule and compute.

Swin and hierarchical Transformers

Plain version. Global attention over thousands of tokens is expensive, and plain ViT keeps one coarse resolution throughout, which is awkward for detection and segmentation. Swin restricts attention to local windows, shifts the windows between layers so information still spreads, and merges patches to build a CNN-like pyramid.

Windows. Swin [5] partitions the token grid into non-overlapping windows of M×MM\times M tokens (typically M=7M=7) and computes self-attention inside each window only. For an h×wh\times w token grid with CC channels, the paper gives the costs

Ω(global MSA)=4hwC2+2(hw)2C,Ω(window MSA)=4hwC2+2M2hwC,\Omega(\text{global MSA})=4hwC^2+2(hw)^2C,\qquad \Omega(\text{window MSA})=4hwC^2+2M^2hwC,

where 4hwC24hwC^2 counts the four projections and the second term counts the score and weighting products. Global cost is quadratic in the number of tokens hwhw; window cost is linear for fixed MM.

Shifted windows. With fixed windows, tokens in different windows would never interact. Swin alternates regular windows with windows displaced by ⌊M/2⌋\lfloor M/2\rfloor tokens in each direction. A token near a window boundary at layer ℓ\ell shares a window with tokens from neighboring windows at layer ℓ+1\ell+1, so information crosses boundaries (Figure 5). An efficient implementation cyclically shifts the feature map and uses a mask so that tokens wrapped from opposite edges do not attend to each other.

Left: an eight by eight token grid divided into four colored four by four windows. Middle: the same grid with window boundaries shifted by two tokens, giving nine regions of different sizes. Right: an eight by eight map in which the top-left four by four window is dark blue, an L-shaped band extending two more tokens right and down is light blue, and a red star marks one token near the window edge.
Figure 5 — Swin's regular and shifted windows on an 8 × 8 token grid. After two layers, information from the starred token reaches the dark window (layer ℓ) plus the light band added by the shifted windows (layer ℓ+1).

Hierarchy. Between stages, patch merging concatenates each 2×22\times2 group of neighboring tokens and projects them linearly, halving the resolution and doubling the channels, as a strided convolution would. The four stages produce feature maps at 1/41/4, 1/81/8, 1/161/16 and 1/321/32 of the input resolution, the same pyramid a ResNet produces, so Swin can replace a CNN backbone in detection and segmentation frameworks. Each window also adds a learned relative position bias to its scores. Swin V2 [32] scaled the design up with residual post-normalization, scaled cosine attention and a continuous, log-spaced position bias that transfers better across window sizes and resolutions.

Hybrid CNN–Transformer models

Plain version. Convolutions are good at local detail with little data; attention is good at long-range interaction. Hybrids use each where it helps.

  • Convolutional stem. The original ViT paper already tested a “hybrid” in which the patches come from a ResNet feature map instead of raw pixels [2]; it helped at smaller compute budgets.
  • Convolutions inside attention. CvT [19] uses a convolutional token embedding at each stage and depthwise-convolutional projections for queries, keys and values, which builds in locality and lets it drop explicit position embeddings.
  • Stacking by stage. CoAtNet [20] places depthwise-convolution stages early, where resolution is high and local patterns dominate, and relative-attention stages later; it reports strong results across data scales because the convolutional stages supply inductive bias when data is limited.
  • Mobile hybrids. MobileViT [28] inserts small Transformer blocks into a MobileNet-style network to add global context at mobile cost.
  • The reverse direction. ConvNeXt (see ML 03) imported Transformer-era design choices into a pure CNN and matched Swin.

Cost and efficient attention

Plain version. Global attention compares token pairs, so its pairwise work grows quadratically with token count. Efficiency methods reduce memory traffic, interactions or token count.

For NN tokens of width DD, the score matrix costs about N2DN^2D multiply–adds per layer and the projections and MLP about 12ND212ND^2. A naive implementation stores an N×NN\times N matrix per head. Doubling the image height and width at a fixed patch size multiplies NN by four and the pairwise scores by sixteen.

Relative pair-score counts at image sides 224, 448 and 896 with patch size 16: global attention grows to 256 times while 7 by 7 window attention grows to 16 times.
Figure 6 — Pair-score scaling, not a measured runtime. Projections, MLPs, memory traffic and kernel quality also determine latency.

The main families:

  • Exact but faster. FlashAttention [6] computes exact attention by tiling the computation so that blocks of queries, keys and values stay in fast on-chip memory, and never writes the full N×NN\times N matrix to slow GPU memory; FlashAttention-2 [29] improves the work partitioning further. The arithmetic is still quadratic; the memory is linear and wall-clock time drops substantially. PyTorch’s scaled_dot_product_attention selects such kernels automatically when it can [7].
  • Restricted connectivity. Windowed (Swin) or other sparse patterns reduce the number of pairs, at the price of needing several layers for global communication.
  • Fewer tokens. Token Merging (ToMe) [21] gradually merges similar tokens inside a pretrained ViT using a fast matching step, increasing throughput without retraining. Larger patches, token pruning and pooling stages do the same more bluntly.
  • Smaller models. Papa et al.’s survey [13] organizes efficient ViTs into compact architectures, pruning, knowledge distillation and quantization, and proposes an “Efficient Error Rate” metric to compare models across parameters, bits, FLOPs and size.

State-space models and hybrids

Plain version. Instead of comparing every pair of tokens, carry a compact state through the sequence, as a recurrent network does (ML 04). The cost grows linearly with the number of tokens.

A simplified state-space recurrence over a token sequence is

ht=Aˉt ht−1+Bˉt xt,yt=Ct ht,h_t=\bar A_t\,h_{t-1}+\bar B_t\,x_t,\qquad y_t=C_t\,h_t,

where hth_t is a hidden state of fixed size, and Aˉt\bar A_t, Bˉt\bar B_t, CtC_t are (discretized) state-space matrices. In selective models such as Mamba, the write/read coefficients and step sizes depend on input xtx_t; the underlying continuous transition can remain fixed while its discretization varies. Input selection and an affine state update permit a parallel scan [33]. An image has no natural one-dimensional order, so vision variants must choose scan orders: Vision Mamba (Vim) [30] scans the patch sequence forward and backward with position embeddings, and VMamba [31] scans along four directions over the 2-D grid. The Visual Mamba survey [8] reviews over 200 papers and identifies scanning as the critical design decision for vision.

A useful counterpoint is MambaOut [9] (CVPR 2025). Its authors argue that Mamba suits tasks with long sequences and causal (autoregressive) structure, and build MambaOut models by removing the state-space component while keeping the gated convolutional blocks. Their models outperform visual Mamba models on ImageNet classification, suggesting that Mamba is unnecessary there, while for detection and segmentation, which involve long token sequences, they find state-space models may still be worth exploring. The broader point is methodological: isolate the mechanism (attention, scan, convolution) from gating, normalization, training recipe and parameter budget before crediting a result to it.

An image scan is an inductive bias

Mamba [33] supplies an efficient sequence operator; it does not choose an image geometry for us. Vim [30] uses a patch sequence, position embeddings and forward/backward processing. VMamba [31] instead places a four-route selective scan inside a hierarchical visual backbone. Neither label alone specifies receptive-field strength, resolution behavior or runtime. The state dimensions, routes, local operators and downsampling stages all matter.

For a fixed scan order, two adjacent pixels in the image may be many steps apart in the sequence. Conversely, the last pixel of one raster row and the first pixel of the next row become consecutive despite being far apart spatially. A local convolution can supply nearby evidence before the scan carries context farther. Multiple routes offer additional paths, but do not restore every geometric symmetry automatically. Position embeddings can also encode useful location while making transfer to a different grid a separate design problem.

A mathematical way to expose the choice is

Y(r)=Pr−1Sr(PrX),Y=1m∑r=1mY(r).Y^{(r)}=P_r^{-1}\mathcal S_r(P_rX),\qquad Y=\frac1m\sum_{r=1}^{m}Y^{(r)}.

Here XX contains flattened image tokens, rr indexes one of mm routes, PrP_r permutes tokens into that route, Sr\mathcal S_r applies its sequence recurrence, Pr−1P_r^{-1} restores image coordinates, and YY averages the resulting features. This is a conceptual route-fusion model. A learned vision block can use different projections or fusion rules; averaging is chosen here to keep the experiment interpretable.

CPU experiment: measure directional bias

The next example uses a single scalar state with the same decay on every route. It compares forward/backward raster scans with four raster/column routes, then rotates the input by 90 degrees, processes it and rotates the output back. Everything uses a synthetic 6×66\times6 impulse; no weights or images are downloaded. This isolates ordering rather than reproducing a trained Vim or VMamba.

Code · Python · 28 lines
import numpy as np

def scan_image(image, four=False):
    ids = np.arange(image.size).reshape(image.shape)
    row, col = ids.ravel(), ids.T.ravel()
    orders = [row, row[::-1]]
    if four:
        orders += [col, col[::-1]]
    outputs = []
    for order in orders:
        h = 0.0
        out = np.zeros(image.size)
        for i in order:
            h = 0.8 * h + 0.2 * image.ravel()[i]
            out[i] = h
        outputs.append(out.reshape(image.shape))
    return np.mean(outputs, axis=0)

image = np.zeros((6, 6))
image[1, 4] = 1.0
errors = []
for four in [False, True]:
    original = scan_image(image, four=four)
    rotated_back = np.rot90(scan_image(np.rot90(image), four=four), -1)
    error = np.max(np.abs(original - rotated_back))
    errors.append(error)
    print('four routes:', four, 'rotation discrepancy:', round(error, 6))
assert 0.0 < errors[1] < errors[0]

The maximum discrepancies are 0.063622 for two routes and 0.026738 for four. More routes reduce directional bias in this example, but the remaining discrepancy is nonzero. Rotating a raster path reverses one traversal axis; that path need not belong to the original four-route collection. Even shared coefficients and averaging therefore do not guarantee rotation equivariance. Learned directional projections, position information and local operations introduce further choices. Test the property you need instead of inferring it from “2-D scan.”

Impulse responses of two-route and four-route scalar image scans
Figure 7 — The red outline marks the input impulse. Two raster routes spread context unevenly; adding column routes changes the influence map. These synthetic responses use the exact recurrence in the example, not learned attention maps or trained VMamba activations.

The recurrence can have a global receptive field because information travels through the entire scan. This says a dependence is possible, not that its influence remains strong at every distance. With scalar decay 0.80.8, the carried contribution decays by another factor of 0.80.8 per intervening step. Selective transitions can change this retention, as derived in ML 04, but training must still learn which information to preserve. Fine boundaries and small objects can be lost through state compression or downsampling even when distant context is available.

What Mamba-2 changes, and how to evaluate it

Mamba-2 [34] reorganizes the selective sequence mixer around structured state-space duality and efficient chunk computation. It changes the transition structure and block parameter projections, rather than making an arbitrary image patch sequence equivalent to a Transformer. The causal structured coefficient matrix has an attention-like interpretation, but standard softmax attention retains different expressive and computational properties. An image application must still specify directions and fusion. The duality therefore answers a computation question; it does not remove the geometry question.

A fair vision comparison should separate three experiments: replace only the mixer inside a shared block; compare complete backbones under a matched training budget; and measure the deployed models on the target hardware. Keep data, augmentation, token resolution and downstream heads controlled. Record state size as well as parameter count, and measure latency and peak memory across image resolutions and batch sizes. A linear token-count term can coexist with expensive projections, route permutations and small-kernel overheads. GPU throughput claims do not follow from the Python loop above.

For dense tasks, inspect errors near boundaries, on small structures and across aspect ratios; for video, distinguish an offline bidirectional encoder from causal live processing. Include rotation/crop sensitivity and longer-grid evaluations rather than only in-distribution classification. MambaOut [9] supplies an important mixer-removal ablation. Its results support a task-dependent comparison, not a theorem that scans are unnecessary for every image problem. Xu et al. [8] organize visual Mamba work by backbones, scan mechanisms and image/video/point-cloud/multimodal applications. Their survey remains a 2024 preprint on the verified record. Its taxonomy is useful for selecting controlled experiments; the number of proposed variants does not establish a universal winner.

Modern view

Survey literature. Khan et al. [3] (ACM Computing Surveys, 2022) start from the foundations (self-attention, large-scale pretraining, bidirectional encoding) and then survey Transformers across recognition, generative modeling, multimodal tasks such as visual question answering, video, low-level vision and 3-D analysis, closing with open problems. Han et al. [11] (IEEE TPAMI, 2023) organize vision Transformers by task (backbones, high- and mid-level vision such as detection and segmentation, low-level vision, video), and also cover efficient Transformer methods. Liu et al. [12] (IEEE TNNLS, 2024) review over a hundred visual Transformers for classification, detection and segmentation on images, point clouds and vision–language data, and suggest three future directions. For efficiency, Papa et al. [13] (IEEE TPAMI, 2024) is the most systematic. For state-space vision models, see Xu et al. [8]. Bishop and Bishop [10] provide the textbook derivations.

State of the art, 2023–2026. The plain ViT has become the default foundation backbone. ViT-22B [24] (ICML 2023) scaled a ViT to 22 billion parameters, with architectural changes (such as normalizing queries and keys) needed for stable training at that size. DINOv2 [23] (TMLR 2024) trained ViTs with self-supervision on a large curated image collection and produced general-purpose features that work frozen across classification, segmentation and depth estimation (ML 06). Darcet et al. [22] (ICLR 2024) found that large ViTs repurpose uninformative background patches as internal scratch space, producing high-norm artifact tokens in attention maps, and that adding a few extra register tokens removes the artifacts and improves dense predictions. Vision–language foundation models (ML 10) and diffusion Transformers (ML 08) build on the same block. At the same time, hierarchical and hybrid designs remain common for dense, high-resolution tasks, modernized CNNs remain competitive under matched budgets (ML 03), and state-space and linear-attention models continue to be explored for very long token sequences such as video.

Open problems. Quadratic cost at high resolution and long video; the large data and compute appetite of plain ViTs; position encodings that generalize across resolutions and aspect ratios; interpreting attention without over-reading it; and fair, compute-matched comparisons between attention, convolution and state-space mechanisms.

Key takeaways

  • Queries and keys determine weights; values provide the content mixed by attention.
  • Score scaling controls magnitude under variance assumptions; it does not guarantee unit variance for arbitrary learned inputs.
  • Masks constrain information access, while positional signals distinguish arrangements that content-only attention cannot.
  • Transformer blocks alternate token mixing and per-token transformations, with residual paths and normalization.
  • ViT, shifted windows and convolutional hybrids make different choices about locality, resolution and training requirements.
  • FlashAttention reduces memory traffic for exact attention; windows, token reduction and state-space scans alter computation or context access.

Exercises

  1. Token budget. Calculate the number of tokens and attention-score entries per head for a 512×512512\times512 image with patches of size 16 and 8. By what factor does the score count grow when the patch size halves?
Hint

N=(512/16)2=1024N=(512/16)^2=1024 and (512/8)2=4096(512/8)^2=4096 tokens; N2=1,048,576N^2=1{,}048{,}576 and 16,777,21616{,}777{,}216 scores. Halving the patch size multiplies NN by 4 and the scores by 16.

  1. Scaling check. Draw random queries and keys with independent standard-normal components for dk=4,64,1024d_k=4,64,1024. Measure the variance of q⋅kq\cdot k with and without division by dk\sqrt{d_k}, and the largest softmax weight over 100 keys in each case. What happens to the softmax without scaling?
Hint

The variance of the raw dot product is close to dkd_k; after scaling it is close to 1. Without scaling, at dk=1024d_k=1024 the softmax puts nearly all weight on a single key (it becomes almost one-hot), so gradients through the other keys vanish.

  1. Remove position. In the TinyViT code, set the position embeddings to zero, drop the class token and use mean pooling, then permute the patch tokens before the blocks and compare the logits in evaluation mode. Explain the result, and what it implies for an image classifier without positional information.
Hint

The logits agree up to floating-point error, because every block is permutation-equivariant and mean pooling is permutation-invariant. Use dropout off (eval()) and permute tokens, not pixels inside a patch. Such a model cannot tell a face from a scrambled face built from the same patches.

  1. Cross-attention shapes. In a text-to-image model, 256 image tokens of width 320 read 77 text tokens of width 768 with 8 heads of width 40. Give the shapes of WQW_Q, WKW_K, WVW_V, one head’s score matrix, and the output.
Hint

WQ∈R320×320W_Q\in\mathbb{R}^{320\times320} (8 heads × 40), WK,WV∈R768×320W_K,W_V\in\mathbb{R}^{768\times320}. Each head’s scores are 256×77256\times77. The output follows the queries: 256×320256\times320 after the output projection. Key and value lengths must match each other, not the query length.

  1. Swin arithmetic. Using the cost formulas, compare global and window attention for a 56×5656\times56 token grid with C=96C=96 and M=7M=7. Which term dominates in each case?
Hint

hw=3136hw=3136. Global: 4⋅3136⋅962≈1.16×1084\cdot3136\cdot96^2\approx1.16\times10^8 plus 2⋅31362⋅96≈1.89×1092\cdot3136^2\cdot96\approx1.89\times10^9, so the quadratic term dominates. Window: the same 1.16×1081.16\times10^8 plus 2⋅49⋅3136⋅96≈2.95×1072\cdot49\cdot3136\cdot96\approx2.95\times10^7, so the projections dominate. The window version is about 14 times cheaper here.

  1. Fair comparison. You have 2,000 labeled images and access to pretrained CNN, ViT and visual Mamba backbones. Design an experiment that tells you which backbone to deploy, and list what must be held fixed. Include a mixer-removal ablation and a resolution/rotation test.
Hint

Compare linear probes on frozen features first, then fine-tuning with matched budgets and tuned learning rates per model on a validation split. Record pretraining data, input resolution, parameters, FLOPs and measured latency on the target device. A pretrained ViT against a CNN trained from scratch tests pretraining, not architecture. For the scan backbone, record state size and test whether benefits survive removing the mixer while retaining gating and local convolution. Keep the same preprocessing in the resolution and rotation tests.

Paper guides

1 paper guide, each on a page of its own.

Open the paper guides →

References

  1. A. Vaswani et al., “Attention Is All You Need,” NeurIPS, 2017. arXiv
  2. A. Dosovitskiy et al., “An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale,” ICLR, 2021. arXiv
  3. S. Khan, M. Naseer, M. Hayat, S. W. Zamir, F. S. Khan and M. Shah, “Transformers in Vision: A Survey,” ACM Computing Surveys, 2022. arXiv
  4. H. Touvron et al., “Training data-efficient image transformers & distillation through attention,” ICML, 2021. arXiv
  5. Z. Liu et al., “Swin Transformer: Hierarchical Vision Transformer using Shifted Windows,” ICCV, 2021. arXiv
  6. T. Dao, D. Y. Fu, S. Ermon, A. Rudra and C. Ré, “FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness,” NeurIPS, 2022. arXiv
  7. PyTorch, scaled_dot_product_attention and TransformerEncoderLayer documentation. Attention, Encoder layer MultiheadAttention mask semantics
  8. R. Xu et al., “Visual Mamba: A Survey and New Outlooks,” arXiv:2404.18861, 2024. arXiv
  9. W. Yu and X. Wang, “MambaOut: Do We Really Need Mamba for Vision?,” CVPR, 2025. Paper
  10. C. M. Bishop and H. Bishop, Deep Learning: Foundations and Concepts, Springer, 2024, ch. 12. Book
  11. K. Han et al., “A Survey on Vision Transformer,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023. DOI
  12. Y. Liu et al., “A Survey of Visual Transformers,” IEEE Transactions on Neural Networks and Learning Systems, 2024. DOI
  13. L. Papa, P. Russo, I. Amerini and L. Zhou, “A Survey on Efficient Vision Transformers: Algorithms, Techniques, and Performance Benchmarking,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024. DOI
  14. J. L. Ba, J. R. Kiros and G. E. Hinton, “Layer Normalization,” arXiv:1607.06450, 2016. arXiv
  15. R. Xiong et al., “On Layer Normalization in the Transformer Architecture,” ICML, 2020. arXiv
  16. J. Su, M. Ahmed, Y. Lu, S. Pan, W. Bo and Y. Liu, “RoFormer: Enhanced Transformer with Rotary Position Embedding,” Neurocomputing, 2024. DOI
  17. P. Shaw, J. Uszkoreit and A. Vaswani, “Self-Attention with Relative Position Representations,” NAACL, 2018. arXiv
  18. M. Raghu, T. Unterthiner, S. Kornblith, C. Zhang and A. Dosovitskiy, “Do Vision Transformers See Like Convolutional Neural Networks?,” NeurIPS, 2021. arXiv
  19. H. Wu et al., “CvT: Introducing Convolutions to Vision Transformers,” ICCV, 2021. arXiv
  20. Z. Dai, H. Liu, Q. V. Le and M. Tan, “CoAtNet: Marrying Convolution and Attention for All Data Sizes,” NeurIPS, 2021. arXiv
  21. D. Bolya et al., “Token Merging: Your ViT But Faster,” ICLR, 2023. arXiv
  22. T. Darcet, M. Oquab, J. Mairal and P. Bojanowski, “Vision Transformers Need Registers,” ICLR, 2024. arXiv
  23. M. Oquab et al., “DINOv2: Learning Robust Visual Features without Supervision,” Transactions on Machine Learning Research, 2024. arXiv
  24. M. Dehghani et al., “Scaling Vision Transformers to 22 Billion Parameters,” ICML, 2023. arXiv
  25. A. Steiner et al., “How to train your ViT? Data, Augmentation, and Regularization in Vision Transformers,” Transactions on Machine Learning Research, 2022. arXiv
  26. D. Hendrycks and K. Gimpel, “Gaussian Error Linear Units (GELUs),” arXiv:1606.08415, 2016. arXiv
  27. H. Touvron, M. Cord and H. Jégou, “DeiT III: Revenge of the ViT,” ECCV, 2022. arXiv
  28. S. Mehta and M. Rastegari, “MobileViT: Light-weight, General-purpose, and Mobile-friendly Vision Transformer,” ICLR, 2022. arXiv
  29. T. Dao, “FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning,” ICLR, 2024. arXiv
  30. L. Zhu et al., “Vision Mamba: Efficient Visual Representation Learning with Bidirectional State Space Model,” ICML, 2024. arXiv
  31. Y. Liu et al., “VMamba: Visual State Space Model,” NeurIPS, 2024. arXiv
  32. Z. Liu et al., “Swin Transformer V2: Scaling Up Capacity and Resolution,” CVPR, 2022. arXiv
  33. A. Gu and T. Dao, “Mamba: Linear-Time Sequence Modeling with Selective State Spaces,” COLM, 2024. Author version
  34. T. Dao and A. Gu, “Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality,” ICML, PMLR 235, 2024. Paper

Check your understanding

This tutorial has 6 exercises. Can you solve them without opening the hints?

Go to the exercises ↑

Next ML 06 · Representation Learning and Self-Supervision · 27 min