Making Transformer inference from scratch

Draft prepared with AI assistance. Read, verify, and rewrite this in your own words before submission. Add your own Miyabi measurements and interpretation.

Problem

The project benchmarks a small decoder-only Transformer, the architecture used for autoregressive language generation. Given a sequence of token IDs, the model computes probabilities for the next token. It selects the most probable token, appends it, and repeats. Tokens are integers from a small vocabulary.

The goal is to reduce inference time while preserving the computed probabilities. The baseline uses fixed, randomly initialized weights and synthetic input tokens. It is a benchmark of the Transformer computation, not a trained language model: generated IDs have no linguistic meaning, and entropy is not a measure of language quality. This allows the entire program to be self-contained without downloading weights or data. Correctness is assessed numerically and through mathematical properties of causal attention.

The main questions are how context length and model width affect runtime, and how later KV caching, multicore execution and GPU execution improve performance. The first pass over the input prompt is called prefill. Subsequent steps are called decode. They have different opportunities for parallel execution.

How the baseline code works

transformer.cc uses C++17 and only the standard library. Weights and activations are flat arrays accessed through ordinary serial loops. There is one sequence per request; repeated requests use the same prompt and model.

  1. Look up a vector for each token and add a fixed sinusoidal position vector.
  2. In each decoder block, apply LayerNorm, then project the vectors into queries Q, keys K and values V.
  3. Split the features into attention heads. For each position t and head, compute softmax(Q[t] * K[0..t]^T / sqrt(head_width)) * V[0..t]. Only positions up to t are visible; this is the causal mask.
  4. Concatenate the heads, apply an output projection and add the block’s input (a residual connection).
  5. Apply LayerNorm and a two-layer feed-forward network with GELU activation, then another residual connection.
  6. After all blocks, apply final LayerNorm. Project the last position to vocabulary scores and apply softmax. Select the highest-probability token.

This is a pre-LayerNorm decoder with bias-free projections, fixed normalization gain 1 and bias 0, and no dropout. Attention scores use one reusable row buffer; the implementation still performs every causal query-key dot product.

Defaults are model width D=256, feed-forward width F=1024, 4 heads, L=2 blocks, vocabulary size V=64, prompt length 128 and 8 generated tokens. There are 2*V*D + L*(4*D*D + 2*D*F) randomly initialized weight values. For prefix length S, one forward pass costs approximately O(L*(S*D*D + S*D*F + S*S*D) + V*D).

The simple baseline recomputes the full prefix for each generated token. The prefill pass produces the first generated token; G generated tokens therefore require one prefill and G-1 further passes. This is a useful reference for later KV caching, which stores old keys and values instead of recomputing old positions.

The program times the forward computation and greedy token selection with std::chrono::steady_clock, separately for prefill and decode. Initialization, allocation, one warm-up request, output validation, checks and printing are excluded. It reports time, token throughput, mean probability entropy, a checksum over every generation step’s distribution, and generated IDs.

Every request checks finite, nonnegative probabilities summing to one. --check also compares attention to an independently materialized double-precision attention matrix and verifies the known uniform-attention case (Q=K=0). A short prefix of the configured model is evaluated in float and double using the same forward equations. Finally, altering or removing future tokens must leave earlier hidden states unchanged. The latter checks test causal masking. These numerical tests do not assert that randomly initialized weights solve a language task.

Where is parallelism

Limits include dependencies between blocks and generated tokens, reduction costs, cache capacity, memory bandwidth and thread/GPU launch overhead. Long-context attention has quadratic arithmetic cost. Cached single-sequence decode has less parallelism and may be limited by weight and KV-cache memory traffic. Small-model results do not directly predict production LLM performance.

Measure speedup at identical model parameters, input, seed and generation length. Distinguish the effect of KV caching from multicore/GPU acceleration by comparing both cached and uncached serial versions when those are implemented. Check full probability vectors: identical greedy token IDs alone can conceal numerical bugs.

Measurements to add after running on Miyabi

Record compiler/options, node/queue, command-line parameters, prefill and decode times, token throughput and correctness errors. Explain the effect of context length or model width and identify a plausible bottleneck. See TRANSFORMER.md for build/run commands and an experiment table.