Why can an autoregressive image model train in parallel but not sample in parallel?

## The factorisation Any joint distribution over an ordered vector `x = (x_1, ..., x_D)` factorises exactly by the chain rule of probability: `p(x) = p(x_1) * p(x_2 | x_1) * p(x_3 | x_1, x_2) * ... * p(x_D | x_<D)` This is an identity, not an approximation — no independence assumption is made. An autoregressive generative model simply parameterises each conditional `p(x_i | x_<i)` with a shared network and fixes an ordering. For images that ordering is conventionally raster order: left to right, top to bottom. For raw audio it is time order over samples. The ordering is arbitrary in principle and the model is only exact with respect to the ordering it was trained on. Because the factorisation is exact, the log-likelihood of a data point is exact too: `log p(x) = sum_i log p(x_i | x_<i)`. Nothing is bounded, nothing is estimated by sampling. That is the family's defining advantage, and it is why autoregressive models sit alongside flows in the exact-likelihood camp rather than with implicit generators. ## Why training parallelises During training the whole ground-truth vector is on hand. The network is given the full input and a **causal mask** — a structural constraint ensuring the computation for position `i` can read positions `< i` and nothing at or beyond `i`. With that mask in place, a single forward pass emits all `D` conditional distributions simultaneously, because each one is conditioned on values that were already known before the pass began. The training loss is the sum of `-log p(x_i | x_<i)` over positions, averaged over the batch, and the gradient flows through one pass. So training cost per example is O(1) network evaluations, not O(D). Doubling image resolution multiplies the work inside a pass but does not multiply the number of passes. ## Why sampling does not Sampling reverses the information flow. To draw `x_2` you must first have drawn `x_1`, because the parameters of `p(x_2 | x_1)` are a function of that realised value. There is no mask trick, because the conditioning values do not exist yet — the model itself must produce them. Generation therefore costs `D` sequential network evaluations, and they cannot be overlapped across positions of the same sample. They can be batched *across independent samples*, which raises throughput but never reduces latency for a single one. Concrete arithmetic makes the cost vivid: - **A 32x32 image, pixel-level factorisation:** 1,024 sequential passes for one image. If the red, green and blue values of a pixel are themselves factorised in sequence, 3,072. - **Raw audio at 24 kHz:** 24,000 sequential passes per second of speech. Real-time generation demands a per-step latency under `1/24000` seconds, roughly 42 microseconds — including every layer of the network and the sampling draw. Miss it and the real-time factor exceeds one, which for an interactive voice product means the system is simply not deployable at that architecture size. The standard framing is the **real-time factor**: wall-clock generation time divided by the duration of the output. Below one is faster than real time; above one is not. For an autoregressive model, RTF is per-step latency times steps per second of output, so shrinking the network is the only lever that moves it — the step count is fixed by the data rate. ## Why this matters in an interview The expected answer is not "sampling is slow". It is the recognition that **the property buying you exactness is the same property costing you sampling speed**. Conditioning each dimension on all previous ones is what makes the likelihood tractable and exact; it is also what serialises generation. You cannot keep the first and delete the second within this family. Common confusions worth heading off: - *"Can't you just predict all positions at once at sampling time?"* You can run one pass on a partially filled input, but every position's output is conditioned on whatever is currently there. Filling them all in one shot from a single pass means each position ignored its true left context, so the joint you sampled is not the model's joint. - *"Isn't training slow too?"* No — training is often the cheap half. This family is unusual precisely because train and sample costs are so asymmetric. - *"Doesn't a bigger batch fix it?"* Batching amortises hardware cost across many samples; it does nothing for the latency of producing one. The honest summary: autoregressive models are parallel to train and hopeless to sample, and any deployment decision about them starts from the dimension count of the thing you want to generate.