Efficiency and Evaluation: What to Measure
Count the work inside a denoising pass
For a dense transformer with width $d$, total input length $N$, and a fixed number of layers, a rough full-pass cost has projection/MLP terms of order $Nd^2$ and attention terms of order $N^2d$. With $K$ denoising passes over an unchanged canvas, a simple implementation repeats that work $K$ times. The vocabulary head can also be significant when projecting many positions into a large vocabulary.
An autoregressive generator does a prompt prefill, then reuses cached keys and values while processing newly generated tokens. A rough sequential cost model for $L$ response tokens after a prompt of length $P$ is
$A$ and $B$ hide layer counts and architectural constants. These formulas describe approximate operations, not wall-clock predictions. Large matrix multiplications can use hardware more efficiently than single-token steps, while memory traffic, kernel overhead, batching, and attention implementation change the outcome. The existing KV-cache and arithmetic-intensity post explains why operation counts alone can be misleading.
If $L=256$ and $K=32$, the decoder averages eight completed tokens per denoiser call. Reporting that number is useful. Calling it an eightfold speedup would require an actual timed comparison.
Why stable token IDs are insufficient for exact caching
In a bidirectional transformer, a token's deeper hidden state depends on the other positions it attends to. If a masked response position changes, a fixed prompt token can receive different attention context. At a subsequent layer, the prompt token's keys and values may therefore change even though its token ID did not.
Ordinary autoregressive caching is exact because the attention graph ensures earlier hidden states cannot depend on future tokens. Full bidirectional denoising lacks that guarantee. Approximate cache reuse may still be a useful speed–quality tradeoff, but it must be evaluated as such. The claim is about dependency structure, not a ban on caching every tensor: embeddings and some first-layer quantities can remain reusable.
Block diffusion changes the factorization
Partition a sequence into $B$ ordered blocks. An explicitly block-factorized model defines
where each conditional is a diffusion model over the current block. Prior blocks are visible; future blocks are unavailable; positions within the active block can attend bidirectionally. With the corresponding attention graph, previous block representations do not depend on the active block, permitting exact reuse of their keys and values.
Block Diffusion studies this interpolation between autoregressive and diffusion language modeling. Its relevance is the explicit factorization and associated training/inference structure. Block size one recovers an autoregressive factorization; a single sequence-sized block gives a full-sequence diffusion factorization.
By contrast, taking a fully bidirectional model and merely committing its output in blocks is a sampler restriction. If old tokens still attend to the evolving current block, the restriction alone does not establish exact cache validity. Ask both “in what order are blocks generated?” and “what can each hidden state attend to?”
Three quantities often called perplexity
| Quantity | Calculation | Interpretation |
|---|---|---|
| Autoregressive NLL | Sum teacher-forced next-token log losses | Exact sequence NLL for that factorized model |
| Diffusion negative ELBO | Bound estimated using corruption samples and required terms | Upper bound on expected NLL, before Monte Carlo noise |
| External-model score | An evaluator LM scores generated text | Compatibility with the evaluator's preferences |
Perplexity exponentiates a per-token log loss. Exponentiating a valid expected NLL upper bound gives a perplexity upper bound, not an exact likelihood. A finite Monte Carlo estimate can fluctuate below the true NLL; the bound is a property of the expectation, not every sampled estimate. Changing the sampler to confidence decoding also changes the generated distribution, so a training bound is not automatically its exact likelihood.
External-model perplexity may reward repetitive or generic text. Pair it with diversity and task measures. Token-based perplexity is not directly comparable across different tokenizers; use a common representation or a carefully defined byte-normalized measure when appropriate.
Multiple-choice evaluation needs a scoring protocol
A masked model can score candidate answers by corrupting candidate tokens while keeping the question fixed and estimating a conditional denoising objective. Results depend on which tokens are masked, how many Monte Carlo draws are used, whether lengths are normalized, and how prompt/answer boundaries are formed.
Scoring each candidate after independently sampling noise introduces extra comparison variance. Where valid for the estimator, using matched corruption times and mask randomness across candidates can reduce that variance. Report the estimator and seed policy so someone can reproduce which answer wins.
A useful evaluation record
{
"checkpoint": "exact model revision",
"tokenizer": "exact tokenizer revision",
"task_split": "named held-out split",
"prompt_template": "versioned template",
"generation": {
"output_slots": 256,
"steps_per_block": 32,
"block_size": 256,
"position_policy": "independent reverse-kernel reveals",
"temperature": 1.0,
"guidance_weight": 0.0
},
"timing": {
"hardware": "record accelerator and memory",
"precision": "record dtype",
"batch_size": 1,
"warmup": "record excluded warm-up runs",
"synchronization": "synchronize device around measurement"
}
}This is an example schema, not a benchmark result. Add seeds, software versions, confidence/remasking options, cache policy, actual model-call counts, and failure-handling rules. If guidance has two branches, record both the number of invocations and the effective examples processed; batching the branches into one call does not make their arithmetic disappear.
Measure latency in terms a user can observe
Measure time to a stable first output, time to a stable first block when applicable, and end-to-end completion latency. A tentative token at position 100 does not let a user read the unfinished prefix. Report tokens per second together with its denominator: whether it includes prompt prefill, tokenizer work, compilation, retries, and rejected completions.
Sweep step counts and block sizes to plot task quality against latency. Compare methods at matched quality or show the whole curve. One unusually fast configuration that sacrifices most task success is a different operating point, not a universal improvement. Use repeated runs and uncertainty estimates appropriate to the evaluation set.
A diagnosis sequence that saves experiments
- Check prompt preservation, output validity, termination, and token alignment.
- At fixed sampler settings, measure denoising quality across masking levels.
- At fixed checkpoint and temperature, sweep the number of steps.
- Then vary block size or position selection, one axis at a time.
- Measure timing after warm-up and synchronize asynchronous accelerator work.
- Inspect invalid outputs and diversity alongside average task score.
Check your understanding: A cache approximation halves latency and lowers task accuracy. Is it an improvement?
It creates a new operating point. Compare it with other configurations at the same accuracy, or show the quality–latency curve. Whether it helps depends on the required quality and latency budget.
Build a case you can fully understand
The final lab applies these distinctions to a small synthetic language. It separates exact sampling arithmetic, denoiser fit, and final-sequence validity without requiring an accelerator.