← All problems
#118 ViT Patch Embedding Medium

Implement the patch embedding stem of a Vision Transformer — the layer that turns a batch of images into a sequence of tokens for ViT, CLIP, SigLIP and DiT. Given a batch of B images of shape (C, H, W), split every image into non-overlapping P × P patches, project each flattened patch to a D-dimensional embedding with patch_weight and patch_bias, prepend the learned cls_token, and add the learned positional embedding pos_embed. All tensors are float32, and H and W are always divisible by P.

image (C, H, W) 0 1 2 3 4 5 6 7 8 row-major patch order flatten patches patch 0 ⋮ patch N-1 (N, C·P·P) project Wᵀ + bias (C·P·P, D) output (N+1, D) cls_token token 0 ⋮ token N-1 + pos_embed (row by row) repeated independently for each of the B images in the batch patch n covers rows [n / (W/P) · P, ...) and columns [n mod (W/P) · P, ...) of the image

With \(g_h = H/P\), \(g_w = W/P\) and \(N = g_h \cdot g_w\) patches per image, patch index \(n = p_y \cdot g_w + p_x\) covers image rows \(p_y P \ldots p_y P + P - 1\) and columns \(p_x P \ldots p_x P + P - 1\). The embedding of that patch is

\[ \text{token}[b][n][d] = \text{patch_bias}[d] + \sum_{c=0}^{C-1} \sum_{i=0}^{P-1} \sum_{j=0}^{P-1} \text{images}[b][c][p_y P + i][p_x P + j] \cdot \text{patch_weight}[d][c][i][j] \]

and the output sequence for image \(b\) is the CLS token followed by the \(N\) patch tokens, with the positional embedding added to every row:

\[ \begin{aligned} \text{output}[b][0][d] &= \text{cls_token}[d] + \text{pos_embed}[0][d] \\[4pt] \text{output}[b][n+1][d] &= \text{token}[b][n][d] + \text{pos_embed}[n+1][d] \end{aligned} \]

Note that the CLS token is not projected — it is a learned vector copied into row 0 of every sequence in the batch.

Implementation Requirements

Example

Input: B = 1, C = 1, H = 4, W = 4, P = 2, D = 2 (so \(g_h = g_w = 2\) and \(N = 4\))

\(\text{images}[0][0]\) (\(4 \times 4\)): \[ \begin{bmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 \end{bmatrix} \] \(\text{patch_weight}\) (\(2\) filters of shape \(1 \times 2 \times 2\)) — filter 0 selects the top-left pixel of a patch, filter 1 the bottom-right pixel: \[ \text{patch_weight}[0][0] = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}, \quad \text{patch_weight}[1][0] = \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix} \] \[ \text{patch_bias} = \begin{bmatrix} 0 & 0 \end{bmatrix}, \quad \text{cls_token} = \begin{bmatrix} 0.5 & -0.5 \end{bmatrix}, \quad \text{pos_embed} = \begin{bmatrix} 0 & 0 \\ 1 & -1 \\ 2 & -2 \\ 3 & -3 \\ 4 & -4 \end{bmatrix} \]

The four patches are \(\begin{bmatrix} 1 & 2 \\ 5 & 6 \end{bmatrix}\), \(\begin{bmatrix} 3 & 4 \\ 7 & 8 \end{bmatrix}\), \(\begin{bmatrix} 9 & 10 \\ 13 & 14 \end{bmatrix}\) and \(\begin{bmatrix} 11 & 12 \\ 15 & 16 \end{bmatrix}\), so the projected tokens are \(\begin{bmatrix} 1 & 6 \end{bmatrix}\), \(\begin{bmatrix} 3 & 8 \end{bmatrix}\), \(\begin{bmatrix} 9 & 14 \end{bmatrix}\) and \(\begin{bmatrix} 11 & 16 \end{bmatrix}\).

Output (\(5 \times 2\), after prepending the CLS token and adding pos_embed): \[ \text{output}[0] = \begin{bmatrix} 0.5 & -0.5 \\ 2 & 5 \\ 5 & 6 \\ 12 & 11 \\ 15 & 12 \end{bmatrix} \]

Constraints

Guided walkthrough coming soon. Below is the official starter signature in each language; the clickable line-by-line explanation hasn't been authored yet.
Problem text & starters from the official AlphaGPU/leetgpu-challenges. Solve it on leetgpu.com.