Part VI — Shipping the compiled model

Operator coverage — decomposition & the long tail

The first thirteen lessons built every pass that makes a model fast and big — capture, fuse, plan, schedule, codegen, autotune, autodiff, shard. Each one quietly assumed the compiler could take any node in the graph and generate a kernel for it. Codegen (lesson 09) assumed it could emit every op; fusion (lesson 05) assumed it could fuse across any boundary. That assumption is a lie at the scale of a real framework. PyTorch's ATen surface is well over 2,000 operators (counting overloads); capture (lesson 02) faithfully emits them, and somewhere in a real model is an op your backend has no code for. One such op, mid-graph, triggers a graph break back to eager — and the seam it leaves behind shatters fusion across it, vaporizing the win. This lesson is how compilers shrink that surface to something tractable: decomposition to a small closed core, with escape hatches for the irreducible tail.

1 · The op-explosion problem: O(ops × backends)

Start with the number that forces everything else. PyTorch's ATen library — the C++ tensor op layer beneath the Python API (you met it in gpu_kernels · 18) — exposes well over 2,000 operators once you count overloads: aten::add, aten::add_ (in-place), aten::add.Scalar, aten::add.out (pre-allocated output), and on through upsample_bicubic2d, grid_sampler, scaled_dot_product_attention, hundreds of activation and pooling and indexing variants. The count is large for a real reason: each op carries variants for in-place mutation, out-parameter forms, scalar-vs-tensor arguments, and autograd. Capture (lesson 02) emits these faithfully — a captured graph is in this rich, redundant vocabulary.

Now count what a compiler would have to write. A from-scratch backend must provide a kernel for every op it can encounter, on every hardware target it supports. That is the multiplication that kills you:

For four targets (NVIDIA, AMD, a CPU vector path, an accelerator) that is roughly 8,000 hand-written, hand-maintained, separately-tested kernels — and it grows with both factors: add an op, pay for N kernels; add a chip, pay for 2,000. No team finishes this, and the ones that try ship a backend that covers 95% of ops and graph-breaks on the rest. The structure of the problem — a product of two large numbers — is the enemy. Whenever you see a product like this in systems design, the fix is to factor it into a sum.

2 · Decomposition: collapse the surface to a closed core

Decomposition is that factoring. The insight: most of those 2,000 ops are definable in terms of a few hundred others. gelu is arithmetic plus a tanh (or erf); softmax is max, subtract, exp, sum, divide; linear is matmul plus add; upsample is gather and arithmetic. So instead of implementing every op on every backend, you implement each op once as a rewrite into a small, closed set of primitive ops — the core — and then every pass and every backend only ever has to understand the core.

The named cores in practice:

The economics flip from a product to a sum. Each op needs one decomposition rule (backend-independent — it is just math), and each backend needs to implement the core (≈ 250 ops) once:

Add a new op: write one decomposition, every backend gets it for free. Add a new chip: implement ≈ 250 core kernels, every op runs on it. The O(ops × backends) blowup became O(ops + backends). This is the single structural reason a backend can claim to "support PyTorch" without writing 2,000 kernels — and it is why Core ATen exists as a published contract.

Recognize the shape of this move: it is exactly canonicalization from lesson 04, lifted from the value level to the op-vocabulary level. There, canonicalization rewrote x·1, consecutive transposes, and non-normal forms into a single normal form so that one pattern would match many graphs. Here, decomposition rewrites a sprawling op vocabulary into one normal vocabulary so that one backend implementation serves many ops. Same principle — reduce the number of distinct things downstream code must handle — same hard constraint: every decomposition must preserve semantics exactly (watch the float-associativity caveat from lesson 04; a softmax decomposition must keep the max-subtraction for numerical stability, not just be algebraically equal). A worked decomposition, the way primTorch writes it:

# before: a single framework op, opaque to the backend
%y = aten::gelu(%x)                       # 1 op the backend must implement

# after: decomposed into Core ATen / prim ops the backend already has
%a = prims::mul(%x, %x)                   # x²
%b = prims::mul(%a, %x)                   # x³
%c = prims::mul(%b, 0.044715)
%d = prims::add(%x, %c)
%e = prims::mul(%d, 0.7978845608)         # √(2/π)
%t = prims::tanh(%e)
%f = prims::add(%t, 1.0)
%g = prims::mul(%x, 0.5)
%y = prims::mul(%g, %f)                   # 0.5·x·(1 + tanh(...))
# the backend now needs only mul / add / tanh — already in the core

And the win compounds with fusion. After decomposition, that gelu is no longer an opaque node fusion must stop at — it is a chain of pointwise prims, and fusion (lesson 05) happily folds the whole chain (and the surrounding matmul + bias) into one kernel. Decomposition does not just make the op runnable; it makes it fusable, which is the whole point of the seam problem next.

3 · The long tail and the graph-break seam

Decomposition handles the body of the distribution — the thousands of composite ops definable from the core. What it does not handle is the long tail: ops that are genuinely primitive to your model but absent from your backend — a custom CUDA fused attention, a third-party C++ op, a data-dependent op like nonzero or unique whose output shape is unknown, an op too new for the decomposition table. For these, capture's only fallback (lesson 02) is the graph break: compile the graph up to the unknown op, hand control back to eager Python to run that one op, then start a fresh graph after it.

The graph break is correct — it never produces a wrong answer — but it is expensive in a way that is easy to underestimate, because the cost is not the eager op itself; it is the fusion it forbids. Recall from lesson 05 that fusion's entire value is loading from HBM once, computing a whole region in registers/SRAM, and writing once. A fusable region cannot cross a graph-break seam: the two compiled islands on either side each pay their own HBM round trips at the boundary, and any fusion that would have spanned the unknown op is forbidden. One unknown op mid-chain does not cost one op's time — it splits one fused kernel into two (or three) and re-materializes the intermediate tensor through HBM.

The ranking is the lesson: decompose if you can (keeps the region whole and fusable); if you cannot, keep it in the graph anyway (custom op or library fallback) so you avoid the eager Python bounce and the guard/recompile churn — even though it remains a fusion boundary. A graph break is the last resort, not the default.

4 · Escape hatch: register a custom op with a fake/meta kernel

When an op cannot or should not be decomposed — your hand-written FlashAttention kernel, a CUDA extension, a fused op you want the compiler to treat as a single black box — you register it as a custom op: an opaque node the compiler will not look inside but will keep in the graph instead of graph-breaking. In PyTorch this is torch.library (the modern @torch.library.custom_op API). Two pieces are required.

First, the real implementation — the actual kernel that runs on device. Second, and this is the part beginners omit, a fake kernel (also called a meta kernel or abstract/meta implementation). The fake kernel does no compute; it takes the input metadata — shapes, dtypes, devices — and returns the output metadata. The compiler needs this because every pass downstream of the op reasons about shapes and dtypes, not values: fusion needs to know the output shape to plan the next kernel, memory planning (lesson 06) needs the byte size to allocate, layout (lesson 07) needs the dtype, and dynamic-shape reasoning (lesson 11) needs to propagate symbolic sizes through the op. Without a fake kernel the compiler is blind past the opaque node and must graph-break to discover the shape at runtime — defeating the purpose. This is the same meta device that lets you trace a model with no real allocations (lesson 03's typed-IR shape propagation), now extended to your op.

import torch

# 1) the real kernel — runs on device, the compiler treats it as a black box
@torch.library.custom_op("mylib::fused_attn", mutates_args=())
def fused_attn(q: torch.Tensor, k: torch.Tensor, v: torch.Tensor) -> torch.Tensor:
    return my_cuda_extension.fused_attn(q, k, v)   # opaque to the compiler

# 2) the FAKE / META kernel — no compute, only shape + dtype propagation
@fused_attn.register_fake
def _(q, k, v):
    # q: (B, H, S, D)  ->  out: (B, H, S, D); shapes flow, no data touched
    return torch.empty_like(q)

With both registered, the compiler keeps mylib::fused_attn in the graph as one opaque node, propagates shapes through it via the fake kernel (so dynamic batch/sequence in lesson 11 still works), schedules and allocates around it, and never graph-breaks. The cost you accept is honest: fusion cannot cross the opaque node — the compiler will not fold anything into a box it cannot see inside — so it is a fusion boundary like any library call. The decomposition-vs-opaque trade is exactly that: decompose and the region stays fusable but you expose the op's internals to the float-reassociation and numerical risks of lesson 04; register opaque and you keep your hand-tuned numerics and kernel, but you forfeit cross-op fusion at that node.

5 · Escape hatch: fall back to a vendor library

The other escape hatch is to not generate a kernel at all and instead call a vendor library: cuBLAS (dense GEMM), cuDNN (convolution, attention, normalization), or CUTLASS (NVIDIA's templated GEMM/conv building blocks). These are decades of hand-tuning per architecture, and for the canonical shapes — a large square GEMM, a standard conv — they hit a fraction of peak the compiler's generated Triton (lesson 09) often cannot match. So Inductor's policy is pragmatic: for matmul and a few key ops it autotunes (lesson 10) the generated Triton kernel against the cuBLAS/CUTLASS option and picks whichever is faster for that exact shape. Generated-vs-vendor is not a religious choice; it is a per-shape benchmark.

Why does a hand-tuned library still win some shapes after all the work of lessons 04–10? Three reasons. The library encodes architecture-specific tricks (split-K, specialized tensor-core fragment layouts, hand-scheduled software pipelining) that the compiler's search space (lesson 10) may not cover; it has been tuned by humans for years on the exact shapes that matter; and for a standalone GEMM there is nothing to fuse anyway, so the compiler's structural advantage — fusing the epilogue (lesson 05) — does not apply. The flip side: when there is an epilogue to fuse (bias, GELU, residual add after the matmul), the generated fused kernel can beat the library call plus a separate epilogue kernel, because it saves the HBM round trip the library boundary forces. So the rule is: library when the op is a standalone canonical primitive; generate when there is fusion to capture.

Every major stack has this fallback mechanism under a different name:

Note the common shape: all three keep the un-generatable work inside the graph as a declared node (with shapes), not as an eager-Python escape. That is the whole trick of coverage — turn "I can't compile this" from a graph break into an in-graph opaque node, and you keep the rest of the pipeline intact.

6 · Drive it: coverage vs fusion

The widget sets a model graph of pointwise ops with a tunable fraction of unknown ops (ops your backend has no kernel for), and lets you pick how to handle them: graph-break to eager, decompose to prims, register opaque, or library fallback. Watch four readouts: # graph breaks, # fusable regions, % of graph compiled, and est. speedup vs eager. The knob that breaks: put even one unknown op mid-chain and choose graph-break — fusion shatters into islands and the speedup collapses; switch the same op to decompose and the chain re-fuses whole.

Drive it and the verdict is stable. With zero unknown ops the whole chain is one fusable region at a large speedup. Add one unknown op in graph-break mode and the chain splits into islands, graph breaks climb, % compiled drops, and the speedup falls toward eager. Switch that same op to decompose and the region heals — one fusable region, zero breaks, full speedup — because the op became fusable prims. Switch to opaque or library and the breaks stay at zero (no eager bounce) but you keep two fusable regions split around the in-graph node: better than a graph break, not as good as decomposition. That ordering — decompose > keep-in-graph > graph-break — is the entire coverage strategy.

Failure modes & checklist

Checkpoint

Where this points next

Coverage is now solved: decomposition collapses the 2,000-op surface to a ≈ 250-op core every backend implements once, turning an O(ops × backends) blowup into O(ops + backends); and for the irreducible tail, custom ops (with fake kernels for shape flow) and library fallback keep the work in the graph instead of graph-breaking it. Every op the compiler meets now lowers to something it can schedule. But notice what that buys and what it doesn't. We have made every op runnable and most of them fusable — we have squeezed the kernel count and the launch overhead. The track's deepest currency, though, has been bytes moved across HBM, and so far every byte has been an fp16 or bf16 byte. The single largest remaining attack on traffic is not a cleverer kernel or a tighter fusion — it is moving fewer bits per number: int8 halves HBM traffic and lights up int8/fp8 tensor cores, int4 weight-only quarters the weight bandwidth that dominates decode. Spending precision is a pass we have never run, and it is the biggest lever left. That is 15 · Quantization & precision lowering.

Interview prompts

• Why can't a backend just implement every framework op? (§1 — ATen has 2,000+ operators/overloads and you'd need a kernel for each on every target, an O(ops × backends) product that grows with both factors; no team finishes ~8,000 hand-written kernels.)
• What is decomposition and how does it change the cost structure? (§2 — rewrite each composite op once into a small closed core of prims (Core ATen ≈ 250, StableHLO); each op needs one backend-independent decomposition and each backend implements the core once, turning O(ops × backends) into O(ops + backends).)
• How is decomposition related to canonicalization from lesson 04? (§2 — same principle one level up: canonicalization normalizes values so one pattern matches many graphs; decomposition normalizes the op vocabulary so one backend impl serves many ops. Both must preserve semantics exactly.)
• An unknown op appears mid-graph. Why is graph-breaking on it worse than it looks? (§3 — the cost isn't the eager op, it's the fusion it forbids: a fusable region can't cross the seam, so intermediates re-materialize through HBM on both sides — the lesson-01 bandwidth ceiling returns mid-graph.)
• You register a custom op. What is a fake/meta kernel and why is it mandatory? (§4 — it does no compute, only maps input shapes/dtypes/devices to output metadata; the compiler reasons about shapes not values, so fusion, memory planning (06), layout (07), and dynamic shapes (11) all need it to propagate past the opaque node — without it you graph-break for shape.)
• Decompose vs register-opaque vs library-fallback — when each? (§3–5 — decompose when possible (keeps the region fusable); register opaque to keep your hand-tuned numerics/kernel in-graph (fusion boundary, but no eager bounce); library-fallback for standalone canonical primitives where cuBLAS/CUTLASS beats generated code; graph-break never if avoidable.)
• Why does a hand-tuned library still beat generated code for some shapes after all the compiler's passes? (§5 — architecture-specific tricks (split-K, fragment layouts, hand-pipelining) outside the autotuner's space, years of human tuning, and for a standalone GEMM there's no epilogue to fuse so the compiler's structural advantage doesn't apply; the autotuner picks per shape.)
• Name the coverage escape hatch in three stacks. (§5 — Inductor: library fallback + torch.library custom op; XLA: custom-call; TVM: BYOC. All keep the un-generatable work in-graph as a declared node, not an eager escape.)