Alpa, Explained with a Restaurant Kitchen

Training a 100B-parameter model means splitting it across dozens or hundreds of GPUs. Get the split right and you train in weeks; get it wrong and you're 10× slower — or you just run out of memory. Until recently, finding the right split was a dark art: experts hand-tuned plans for months, and those plans only worked for one model on one cluster.

Alpa (OSDI 2022, UC Berkeley) asked a simple question: can a compiler figure out the parallelization plan automatically? The answer was yes — and the way it gets there reshaped how the field thinks about parallelism.

Full honesty: my first read of this paper was rough. Sharding specs like S⁰S¹ looked like hieroglyphics, the ILP and DP formulations made my eyes glaze over, and I couldn't tell which parts were the idea and which were machinery. What finally unlocked it for me was a silly analogy that turned out to map onto the paper almost perfectly. So that's how I'm going to explain it.

Welcome to the kitchen.

The kitchen

You run a restaurant. A 1000-dish banquet order comes in. One cook can't handle it, but you have 16 cooks. Your entire job is to answer one question: who does what?

It turns out there are only two fundamental ways to split cooking work:

Way 1: Split each dish. Four cooks make the same soup together — one chops, one stirs, one seasons, one plates. Each dish finishes fast, but the cooks must talk constantly: "onions are chopped, here!" High speed, high chatter.

Way 2: Split the menu. Cooks 1–4 make appetizers, cooks 5–8 make mains, cooks 9–12 make desserts. Orders flow down an assembly line. Almost no talking — appetizer cooks just hand finished plates to the mains team. But there's idle time: the dessert team stands around until the first order reaches them.

These two ways are the paper's two core concepts:

• Splitting one dish = intra-operator parallelism — partitioning a single operation (like one giant matrix multiply) across devices. High utilization, heavy communication.
• Splitting the menu = inter-operator parallelism — assigning different layers of the model to different devices, pipeline-style. Light communication, but idle "bubbles."

Everything you've heard of fits into these two buckets. Data parallelism, tensor parallelism, ZeRO? All flavors of way 1. Pipeline parallelism? Way 2. This re-categorization — collapsing the traditional data/operator/pipeline trichotomy into just two levels — is the paper's first contribution.

The one killer insight

Here's the part that made me put the paper down and stare at the wall.

Your 16 cooks aren't in one big room. They're in 4 rooms, 4 cooks each. Cooks in the same room can just talk — instant. Cooks in different rooms have to text — slow.

Real clusters look exactly like this. GPUs inside one machine are connected by blazing-fast links (NVLink, hundreds of GB/s). Machines are connected to each other by comparatively slow networks (tens of Gbps).

So the obvious plan writes itself: put the chatty teamwork (way 1) inside a room, and the quiet hand-offs (way 2) between rooms. Never make cooks in different rooms collaborate on one soup — they'd be texting non-stop, and the whole kitchen would stall on the messaging.

That's it. That's the insight: the structure of parallelism should mirror the structure of the hardware. Chatty parallelism on fast links, quiet parallelism on slow links. Once you see it, it feels inevitable — which is usually the mark of a great systems idea.

The two planners

Knowing the principle isn't enough — someone still has to decide exactly where to cut the menu and how each room divides its dishes. Alpa does this with two planners, one nested inside the other.

The big planner asks: how do I cut the menu, and how many cooks per section? Should appetizers get 4 cooks and desserts 8? Does the soup course belong with appetizers or mains? There are millions of ways to cut. The big planner searches through them — but to compare options, it needs to know, for each candidate: "if I give these 5 dishes to that room of 4 cooks, how long will they take?"

Which it can't know without the second planner.

The small planner asks: inside one room, what's the fastest division of labor? Given these specific dishes and these specific cooks, who chops and who stirs? It works out the best in-room arrangement and reports back a single number: "these 5 dishes on 4 cooks: 8 minutes."

The search loop is: big planner proposes a cut → asks the small planner to price each section → collects the numbers → keeps the cut where the slowest section is as fast as possible.

Why the slowest? Because in an assembly line, once orders are flowing, food exits at the pace of the slowest station. A brilliant dessert team can't save you from a jammed mains section. The entire game is cutting the menu so every section takes roughly equal time.

In the paper's vocabulary: the big planner is the inter-op pass, solved with dynamic programming. The small planner is the intra-op pass, solved with integer linear programming. Those names intimidated me for a full read-through before I realized they're just the two planners.

Those hieroglyphics: S and R

The notation that scared me most turned out to be the simplest thing in the paper.

In an AI model, nearly every "dish" is the same dish: a giant grid of numbers multiplied by another giant grid of numbers. So "who does what" really means "how do 4 cooks share one giant grid?"

There are only three options per direction of the grid:

• Give each cook some rows
• Give each cook some columns
• Give every cook the whole thing (a full copy)

The notation just writes one letter per grid direction: S for Split, R for Replicated. SR = row-chunks. RS = column-chunks. RR = everyone holds a full copy. The superscripts (S⁰, S¹) only add bookkeeping about which group of devices holds which chunk. That's the entire secret. Hieroglyphics decoded.

Why the choice matters: the model is a chain of steps, and step 1's output grid is step 2's input. If step 1 finishes with data split by rows, but step 2 wants it split by columns, every cook is holding the wrong pieces. They must stop and swap: "you give me your top-left, I'll give you my bottom-right." This swapping is pure overhead. The paper calls it resharding, and the standard swap patterns have names you'll see in every distributed paper: all-gather, all-reduce, all-to-all. Think of them as named chess openings for piece-swapping.

So the small planner's job is really a shopping problem. Each step has a menu of layouts (by rows? by columns? copies?), each with a price (communication during the step) plus a mismatch fee if it doesn't match its neighbors' layouts. Pick one option per step to minimize the grand total. Sometimes the planner deliberately picks a "worse" layout for one step because matching its neighbors avoids two expensive swaps — the same way a good cook organizes ingredients the way the next station wants them.

The ILP solver? An off-the-shelf calculator you hand this shopping problem to. You never need to look inside it.

The one equation worth deriving

I have equation anxiety, so instead of transcribing the paper's math, I derived its scariest-looking formula from lunch trays. It took five minutes and permanently demystified it.

Setup: the assembly-line kitchen, but instead of processing the banquet as one giant lump (which leaves two-thirds of the kitchen idle at any moment), you cut the order into small trays — say 50 dinners each. The moment tray #1's appetizers are done, it moves to mains and tray #2 starts. Soon every station is busy at once. A tray is what the paper calls a microbatch.

Now, how long does the whole banquet take with B trays and stages that take t₁, t₂, ..., t_S minutes?

• Tray #1 must travel the entire line: t₁ + t₂ + ... + t_S. No shortcut exists.
• Once the line is full, a finished tray pops out at the pace of the slowest station: every max(t_j) minutes.

So:

Total time = (t₁ + t₂ + ... + t_S) + (B − 1) · max(t_j)

That's Equation 2 of the paper — the one that made me close the PDF on my first attempt. It's lunch trays. And it re-confirms the big planner's obsession: the dominant term is (B−1) × slowest stage, so balance your stages.

Two bonus terms this unlocks: a bubble is any moment a station idles while the line fills up or drains. And 1F1B is a counter-space rule — each tray leaves prep scraps (activations) that clutter the counter until the tray is fully processed, so instead of pushing all trays forward first (scraps from every tray pile up — GPU out of memory), each station alternates: advance one tray, fully finish and clear an older one. Same speed, far less clutter.

As for the big planner's dynamic program: it's the classic "partition an array into k contiguous chunks minimizing the maximum chunk sum" interview problem, wearing formal clothes. Operators are the array, stages are the chunks, and the small planner prices each chunk. If you've done that LeetCode problem, you understand Section 5.

Does it actually work?

Three results, one per model type:

• GPT-3-style models: Alpa's auto-generated plans match Megatron-LM — the state-of-the-art system whose plans were hand-tuned by experts specifically for this architecture. Occasionally Alpa wins slightly (it composes a weight-update-sharding trick Megatron lacked).
• Mixture-of-Experts models: 3.5× faster than hand-tuned DeepSpeed on 2 machines, 9.7× on 4 — largely because DeepSpeed had no inter-op parallelism to quiet down the slow cross-machine links.
• Wide-ResNet: the real point. A heterogeneous model with no known manual plan — no expert had ever worked one out. Alpa found a non-trivial plan (3 uneven stages, mixed layouts per layer) that scales to 80% efficiency on 32 GPUs. The generated plan was one no human had designed, and the authors note even domain experts would find it opaque.

Compilation takes minutes to a few hours — noise compared to training runs measured in weeks.

Why this paper still matters

Alpa is a training paper, but its fingerprints are all over modern inference. The two-level view — align parallelism structure with network hierarchy — became the industry's default mental model. And the lineage is direct: Lianmin Zheng and Zhuohan Li, Alpa's lead authors, went on to create vLLM and SGLang, the two dominant open-source LLM serving engines. Reading Alpa is reading the origin story of the systems that serve most open LLMs today.

What I'd tell my past self

The paper has two kinds of content: ideas (two-level parallelism, hardware-matching, planner-queries-planner) and machinery (ILP details, DP recurrences, sharding notation). My mistake was reading linearly and drowning in machinery before grasping the ideas. Read §2.2 and §3 first — the ideas live there. Then decode S/R (it's just sliced-or-copied). Then derive the pipeline equation from trays. Only then skim the solver sections, knowing they're a shopping problem and an array-partitioning DP.

And if the notation makes you want to cry — same. Draw a kitchen.

Paper: Alpa: Automating Inter- and Intra-Operator Parallelism for Distributed Deep Learning, Zheng et al., OSDI 2022. Code: github.com/alpa-projects/alpa