Compositional Generative Modeling

Train small models on the pieces, then multiply their probabilities. The product can draw combinations that no model ever saw, and it needs far less data than one giant model.

Learn why a generative model built from simple parts can beat one monolithic model, how to multiply models together, and how to draw samples from the product.

Press Hide the middle block. A grid of 64 cells is cut: one block of it has no training data. Watch which model can still fill the hidden cells, then drag the sample count or switch models. After that we build, piece by piece, how to multiply models, sample from the product and use it on new tasks.

You need a feel for probability (a number from 0 to 1 that says how likely something is). We build the rest from zero.

A reading for the MIT MMAI: Multimodal AI course, taught with Lecture 9, Multimodal Generation. Paper: Yilun Du and Leslie Kaelbling (MIT), ICML 2024, arXiv 2402.01103.

One big model or two small ones

40

Toy world, illustrative: two independent variables with 8 values each, so 64 cells. Samples come from a fixed seeded stream. The monolithic model counts pairs; the compositional model counts each variable separately, with half the budget for each. Both add a small pseudo-count of 0.05. The gap is the paper’s argument in miniature (its Figures 3 and 4), not its experiment.

Chapter 0

Why One Giant Model Is Not Enough

See what a single huge model costs, where it still fails, and what the paper proposes instead

Imagine a photo with a blue cup below a red bowl. You show a very strong model a photo and ask, “Is the blue cup below the red bowl?” It says no. It even claims the bowl is not visible.

The paper opens with exactly this kind of failure. In its Figure 2, GPT-4V misjudges a simple spatial relation. DALL-E 3 is asked for a picture of a robot dog feeding a person, and it falls back on the biases in its training data. These models have read a large part of the Internet. They still stumble on easy combinations of familiar things.

The default recipe: one model, one giant bill

A generative model is a program that learns what a kind of data looks like and then makes new examples of it. Think of a student who studies ten thousand paintings and then paints a new one. Its knowledge is a distribution: a rule that says how likely each possible example is.

For the last few years, the main recipe has been to build one very large model and feed it more data. The paper calls this a monolithic model, meaning one single block. Monolithic models work. They also have three costs.

The first cost is money. The paper’s Figure 1 plots training compute, in floating point operations, for models from GPT-3 to Gemini Ultra. Training cost rises by a factor of about 3 every year. Current runs already cost several hundred million dollars each. Use the first device to feel what that curve means.

Compound the training bill

Each bar is one year. Each bar is three times taller than the one before. Drag the slider to choose how many years ahead to look.

3

The factor of 3 per year and the phrase “several hundred million dollars” come from the paper’s Figure 1, which uses Epoch data. The $300 million starting point is illustrative: it is one value inside “several hundred million”. Real runs differ, and the trend need not continue.

Six years of tripling make a run 729 times as costly. No lab can pay that bill for ever. Even before then, only a few groups can afford the first step.

The second cost is use. Running a huge model for each answer needs big computer clusters. The paper notes that longer queries and answers cost several dollars each on the largest services.

The third cost is change. Suppose you want the model to handle a new kind of data. Fine-tuning (training it a little more on your own examples) a giant model needs a large cluster and a data set that is hard to collect. Giving it examples in the prompt helps less than it seems. The paper cites work showing that this works only when the new task looks roughly like what the model already saw in training.

The paper’s bet

Yilun Du and Leslie Kaelbling make a different bet. Their paper is a position paper: it argues for a direction and shows evidence from many earlier studies, rather than running one new benchmark. The title says it: a single model is not all you need.

Their proposal is to build a large generative system out of small generative models. Each small model covers a piece of the world. We compose them, which here means we combine their probabilities into one distribution for the whole. Think of a recipe: salt, flour and water are simple, and the dish is not.

They claim three benefits. Each is a chapter of this lesson.

  1. Data efficiency. Each piece needs less data to learn than the whole, and the combined model can draw examples in regions where no data existed, as long as each piece was seen locally.
  2. New tasks without training. Combine existing models in a new way, and you build a model for a task nobody trained for. Probability works as a common language between the parts.
  3. Discovery. In many cases the pieces can be found from raw data, with no labels.

The paper adds two side benefits. Small models can be built by different groups and checked one at a time, so they are easier to understand. They also run on small machines, which uses less energy.

What the paper is, and is not

Read it with care. It does not claim that composition beats scale in every case. It names limits: you must usually choose the structure of the composition by hand, and the data must really split into independent parts. Chapter 8 and the Field Guide return to this.

It also is not a new architecture with a leaderboard. Most of its evidence is a set of figures from earlier work by the same group, plus one number: on the MATH data set, five GPT-3.5 instances composed through multiagent debate reach 58.0 ± 2.8 percent, above GPT-4 at 55.0 ± 2.9 percent. We keep each claim tied to its figure.

The hero at the top of the page is a miniature of the first benefit. It is a toy, not the paper’s experiment. Go back and try it again after you read Chapter 1.

The road

We build the idea in nine steps. Each chapter explains one part of the instrument at the top and one part of the paper.

  1. The data bill: why a joint distribution costs so many samples, and how factors cut the cost.
  2. Probability as currency: multiply for “and”, add for “or”.
  3. Energies: why adding scores is the easy way to multiply models.
  4. Why you cannot just multiply: autoregressive and diffusion models resist composition.
  5. Sampling the product, continuous: Langevin steps and diffusion.
  6. Sampling the product, discrete: Gibbs and Metropolis-Hastings.
  7. New tasks without training: planning, constraints, images, video, language.
  8. Discovering the pieces: learned structure, and where it breaks.
  9. The field guide: numbers, checklist, code, and what to read next.
What is the paper’s main proposal for building a large generative system?

Chapter 1

The Data Bill

Count why a joint distribution needs so many samples, and see how splitting it into factors cuts the count

You run a small restaurant and you plan a set menu with four courses. Each course has ten dishes. A guest picks one dish per course, so there are 10 × 10 × 10 × 10 = 10,000 possible dinners.

You want to learn which dinners guests like. If you must see every dinner at least a few times, you need to serve thousands of guests. But suppose guests choose each course on their own, without caring what they ate before. Then you only need to learn four lists of ten tastes. That is 40 numbers, not 10,000.

This is the whole idea of the chapter. The rest is care with the words.

Variables, values and the joint distribution

A random variable is a quantity that can take one of several values, each with some probability. A course on the menu is a random variable. Its values are the ten dishes. We write K for the number of values, so K = 10 here.

A joint distribution gives a probability to each full combination of values: one dish for every course. For four variables A, B, C and D we write it p(A, B, C, D). To store it as a table you need one cell for each combination. That is K × K × K × K cells, or K4.

The paper states the growth rate with a known result (Canonne, 2020). Learning the distribution of one variable A needs on the order of K samples, written O(K). Learning the joint distribution of four variables needs on the order of K4 samples. Every new variable multiplies the data you need by K.

Factorization: write the joint as a product

Now suppose we know some structure. Say A and B are independent, meaning that knowing one tells you nothing about the other, and both are independent of the pair (C, D). Then the joint splits into a product of smaller pieces. The paper writes it this way.

p(A, B, C, D)
The joint distribution: a probability for every combination of the four variables.
∝
“Proportional to”. The two sides differ only by one constant that makes the total probability equal 1.
p(A)
A factor over one variable. It needs K numbers.
p(B)
Another factor over one variable. K more numbers.
p(C, D)
A factor over a pair, because C and D may depend on each other. It needs K × K numbers.

Count the cells again. The three factors need K + K + K² cells. With K = 10 that is 10 + 10 + 100 = 120 cells. The joint table needs 104 = 10,000. The factored version is 10,000 / 120, about 83 times smaller.

Add more variables and the gap widens fast. With eight variables of ten values each, the full table has 108 = 100,000,000 cells. Eight independent factors need 8 × 10 = 80. Use the device to move K and the number of variables yourself.

Count the cells

Each bar is the number of cells a model must fill. The bars use a log scale: one step right is ten times more cells. Drag both sliders and compare the three bars.

10
4

Cells are a stand-in for samples: the paper gives growth rates, O(K) for one variable and O(K4) for four, not exact sample counts. The middle bar keeps one pair of variables joint and the rest independent: (n − 2) × K + K² cells.

Reaching cells you never saw

Counting cells is only half the gain. The other half is reach. Look at the hero again, with the middle block hidden. The monolithic model fills a cell only after it sees a sample in that cell. A hidden cell stays almost empty.

The factors do not need that. One factor has seen every value of A. The other has seen every value of B. Multiplying them gives a probability for the pair (A, B), even if that exact pair never appeared. The paper states the condition: the composed model generalizes to unseen combinations as long as each local combination is in distribution. Each factor must have met the values it is asked about.

Figure 3 of the paper draws this as a picture. Training data lie in a narrow diagonal band across a square. A monolithic model covers only the band. Two models, one for each axis, cover the full square when multiplied. The paper uses the same logic for images and text. Models trained on single sentences can describe scenes for which no paragraph exists.

What the paper measured

Four settings back this up. The paper shows them as figures, taken from earlier work, and we describe what each figure shows.

Simple products and mixtures (Figure 4). The target is a product or a mixture of two simple densities. One monolithic model learns the whole target. Two models learn the two factors. The monolithic model gets twice as much data as each factor model, so the total data are the same. The composed models match the target more closely, even for these simple shapes.

Trajectories (Figure 5). The setting is Maze2D: a point moving in a maze with a 4-number state (2D position and 2D velocity) and a 2-number action. Episodes last about 10,000 steps. A factorized model splits a trajectory into chunks of 8 steps. With few episodes it simulates the dynamics with smaller error than a joint model. It also trains in fewer iterations.

Pictures from text (Figure 6). To draw an image x from a long description T with sentences t1, t2 and t3, the paper uses p(x | T) ∝ p(x | t1) p(x | t2) p(x | t3). The model only needs to learn images for single sentences. It then handles long paragraphs and sentence combinations it never saw.

Language (the MATH number). Five instances of GPT-3.5 composed through multiagent debate reach 58.0 ± 2.8 percent. GPT-4 alone reaches 55.0 ± 2.9. We return to this in Chapter 7.

When the factors lie

A factored model assumes the structure is right. Here is the failure as a story. The symptom: a model of dinners keeps offering a heavy soup before a heavy stew, because guests who like one also like the other. The measurement: the factored model cannot represent that link, so its distribution is slightly off for every guest. The fix: keep the linked variables inside one factor, like p(C, D) above.

The paper adds a reassurance. Even if the true distribution is not an exact product, a factorization can still help when data are limited. It shrinks the space of models the learner must search, so noise matters less. Chapter 8 measures what a wrong independence guess costs.

Why does writing p(A, B, C, D) ∝ p(A) p(B) p(C, D) reduce the data needed?

Chapter 2

Probability as Currency

Multiply two models to keep what both accept, or add them to keep what either accepts

Two friends choose a restaurant. Each gives every place a score from 0 to 1. Maya loves noodles and gives low scores to steak. Jon loves steak and gives noodles a medium score. How do you pick a place that works for both?

You could multiply their scores. A place gets a high product only if both scores are high. One zero ruins it. That is an “and”. Or you could add their scores. A place gets a high sum if either friend loves it. That is an “or”.

The paper treats probability the same way. It calls probability a currency for combining models: each model prices every possible sample, and the combined model uses those prices together. This chapter makes the idea exact.

A distribution is a score that sums to 1

A probability distribution p(x) gives each possible sample x a non-negative number, and all the numbers add up to 1 (or integrate to 1, for continuous values). A generative model is a machine that stores such a score and can draw samples in proportion to it.

Take two models p1 and p2 over the same samples. The paper composes them in two ways.

p(x)
The new, composed distribution over samples x.
∝
Proportional to. We rescale at the end so the total is 1.
p1(x)
The score the first model gives sample x.
p2(x)
The score the second model gives sample x.
×
Multiply the scores: x must be likely under both models. This is “and”.
+
Add the scores: x may be likely under either model. This is “or”.

The paper also lists a third operation, the inversion of a distribution, which flips what the model likes. We use only the first two.

A worked example, every step

Let there be three possible samples: noodles, steak and pizza. Maya’s model p1 and Jon’s model p2 give these scores.

Samplep1p2p1 × p2Normalized productNormalized mixture
Noodles0.50.10.050.190.30
Steak0.30.30.090.350.30
Pizza0.20.60.120.460.40

Step 1: multiply row by row: 0.5 × 0.1 = 0.05, 0.3 × 0.3 = 0.09, 0.2 × 0.6 = 0.12. Step 2: add them to get the normalizing constant Z, the number that rescales scores into a distribution: 0.05 + 0.09 + 0.12 = 0.26. Step 3: divide each by Z: 0.05 / 0.26 = 0.19, 0.09 / 0.26 = 0.35, 0.12 / 0.26 = 0.46.

For the mixture, add row by row: 0.6, 0.6 and 0.8. Their total is 2.0, so the normalized scores are 0.30, 0.30 and 0.40. The product favors pizza strongly. It is the sample that neither friend dislikes. The mixture stays flatter.

Now try it with continuous bell curves. Two models each put a bump on a line. Move the bumps and switch between product and mixture.

Multiply or add two models

Teal curves are the two models. The filled shape is the composed model. Choose product or mixture, then drag the peaks apart and together.

0.35
0.65
0.10

Illustrative: two bell curves with the same spread on the interval 0 to 1, evaluated on 200 points. Agreement is the overlap area Z of the two models divided by its largest possible value, which happens when the peaks coincide. The restaurant table above uses invented scores.

What the product does when models disagree

Put the peaks close. The product is a sharp bump between them. Its overlap Z is large. The two models agree, so the product trusts the shared region and gives a narrower answer than either model alone.

Now pull the peaks apart. The symptom is a product that sits in a place neither model likes: the far tails of both curves. The measurement is Z. It collapses toward zero, and the device shows the agreement falling. The fix depends on what you want. If both constraints must hold, a tiny Z is a true message: no sample satisfies both. If you only need one of them, use a mixture, which never collapses.

Why this works as a language between models

The paper uses this to build models for new tasks. Take a model p(τ) of legal paths through an environment. Take a second model r(τ, s, g) that gives high score to paths starting at s and ending at g, and a low score everywhere else. The product is the planner.

q(τ)
The new model: it samples plans that go from the start s to the goal g.
∝
Proportional to.
p(τ)
A model trained on legal state sequences, with no goal in mind.
r(τ, s, g)
A constraint model: high score if the path starts at s and ends at g, low everywhere else.

Neither model was trained for planning. The paper says the product needs no explicit training or data. Each model states a constraint, and the product keeps only what satisfies all constraints. That is the sense in which probability is a communication language among models. Chapter 7 builds a planner this way, with exact numbers.

Two models strongly disagree about which samples are likely. What happens to the normalized product p1(x) p2(x)?

Chapter 3

Energies: Multiply by Adding

Turn each model into a landscape of hills and valleys, then add the landscapes to multiply the models

Picture a marble on a hilly field. It rolls downhill and rests in the valleys. If you shake the field, the marble hops between valleys, and it spends more time in the deep ones than in the shallow ones.

Now give every possible sample a height on that field. High ground means unlikely. Low ground means likely. A probability model is a landscape, and drawing a sample is like finding where a shaken marble would rest. This is the picture behind energy-based models, or EBMs.

Energy and probability

The energy E(x) of a sample x is a single number: its height on the field. The paper defines the model through the exponential of minus the energy.

pi(x)
The probability model number i, for sample x.
∝
Proportional to: we leave out the constant that makes the total equal 1.
e−Ei(x)
The exponential of minus the energy. Low energy gives a large value. The value is never negative.

In practice E is a neural network. It takes a sample x (for an image, a tensor of shape 3 × H × W) and returns one number. The exponential turns that height into a score, and the minus sign makes valleys likely.

The key trick: add energies, multiply probabilities

Here is why the paper likes this form. Take two models and multiply them. A rule of exponents says that ea times eb equals ea + b. So the product has a very simple energy.

e−(E1 + E2)
The composed model. It is a new EBM whose energy is E1(x) + E2(x): the two landscapes stacked.
∝
Equal up to a constant.
e−E1(x)
Model 1’s unnormalized score.
e−E2(x)
Model 2’s unnormalized score.

Check it with the restaurant table from Chapter 2. The energy of a sample is minus the natural logarithm of its score. Noodles: E1 = −ln 0.5 = 0.69 and E2 = −ln 0.1 = 2.30, so the sum is 2.99 and e−2.99 = 0.05. That is exactly the product 0.5 × 0.1. Steak: 1.20 + 1.20 = 2.41, and e−2.41 = 0.09. Pizza: 1.61 + 0.51 = 2.12, and e−2.12 = 0.12. The same three numbers appear.

Stacking landscapes is easy to code. You add two outputs. A mixture also has a simple form: its score is the sum e−E1 + e−E2, which is also an energy function. The paper notes that inversions can be written this way too.

Stack two landscapes

Brighter means more likely. Factor 1 has vertical stripes. Factor 2 has horizontal stripes. Tap the picture to place a probe, then switch views.

3

Illustrative landscapes: each factor is a sum of narrow bumps, E = −ln of the bump sum, with a spread of 0.18 divided by the stripe count. The picture matches the layout of the paper’s Figure 4, which shows product and mixture compositions of two simple factors. Heat is e−E, not rescaled.

In the Product view the bright places are the crossings of the stripes. A sample is likely only if it is on a vertical stripe and a horizontal stripe. In the Mixture view the bright places are the stripes themselves, because either one is enough. The paper’s Figure 4 shows exactly this pair of shapes.

The price: nobody knows Z

There is a catch, and the paper states it plainly. An EBM gives an unnormalized score. To turn scores into probabilities you divide by Z, the sum of the scores over all possible samples. For an image with thousands of pixels, that is a sum over more values than there are atoms in the universe. The paper says the normalization constant is intractable to compute because it requires marginalization over the sample space.

The same holds when you multiply two normalized models: the product is again unnormalized. The grid in the device is small enough to sum. A real image is not.

We cannot read probabilities directly, but we can still sample. Sampling needs only energy differences, and a difference cancels Z. The paper therefore says that any EBM is sampled with Markov Chain Monte Carlo (MCMC): a method that starts with a rough guess and improves it step by step toward high-probability samples. Chapters 5 and 6 build that.

Where EBMs stand today

The paper is open about this. EBMs lag other generative models in efficiency and in the scale of training. So it uses a bridge: diffusion models are closely tied to EBMs (Song and Ermon, 2019). A diffusion model learns the slope of an energy landscape at many noise levels. We can therefore compose diffusion models with the energy rules above. Chapter 5 shows how.

Model 1 gives a sample energy 1.0 and model 2 gives it energy 2.0. What are the energy and the unnormalized score of the product model at that sample?

Chapter 4

Why You Cannot Just Multiply

Find out why two trained language models or diffusion models do not combine by multiplying their outputs step by step

Two co-writers each finish a story one word at a time. You want a story that both would write. A simple plan: at every step, take each writer’s probabilities for the next word, multiply them, and draw a word. That is the obvious way to multiply two language models.

The paper says this plan is wrong. The result is not the distribution you meant. The reason is small and exact, and it deserves a careful look before we fix it.

Autoregressive models: a chain of questions

An autoregressive model writes a sequence one token at a time. Each step asks: given the tokens so far, how likely is each next token? The probability of a whole sequence is the product of these answers. The paper writes the token conditional as p(xi | x0:i−1), meaning the probability of token i given tokens 0 up to i − 1.

Now take two such models, p1 and p2, and ask for the product distribution pproduct(x) ∝ p1(x) p2(x) over whole sequences. What is its token conditional? Marginalize, which means sum over every way the sequence could continue after token i.

pproduct(xi | x0:i−1)
What you would need at each step to sample from the true product.
∝
Proportional to, within each step.
p1(xi | …)
Model 1’s own next-token probability.
p2(xi | …)
Model 2’s own next-token probability.
A(x0:i)
The agreement of the futures: how much both models like the same continuations after this token. The paper does not name it. We name it to keep track.
∑xi+1:T
Add over every possible rest of the sequence, from token i + 1 to the end T.
p1(future | x0:i) p2(future | x0:i)
The product of the two models’ probabilities for one particular future.

Compare this with the naive plan. The naive plan keeps the first two factors and drops A. The paper says it plainly: since the marginalization depends on xi, the true conditional is not p1 times p2. Autoregressive factorizations are not directly compositional.

A two-token example with every number

Let tokens be 0 or 1, and let each sequence have two tokens. Model 1 picks token 1 with probability 0.5. After a 0 it picks 1 with probability 0.9. After a 1 it picks 1 with probability 0.1. Model 2 also picks the first token 1 with probability 0.5. After a 0 it picks 1 with probability 0.9. After a 1 it also picks 1 with probability 0.9.

The naive plan at step 1 multiplies 0.5 × 0.5 for each token, so both tokens get equal weight: P(first token is 1) = 0.50.

Now find A for each first token. After a 0 the models agree: A(0) = 0.9 × 0.9 + 0.1 × 0.1 = 0.82. After a 1 they disagree: A(1) = 0.1 × 0.9 + 0.9 × 0.1 = 0.18. The true product weighs the first token by 0.5 × 0.5 × A. For token 0 that is 0.25 × 0.82 = 0.205. For token 1 it is 0.25 × 0.18 = 0.045. Divide by their sum, 0.25. The true P(first token is 1) is 0.045 / 0.25 = 0.18, not 0.50.

The reason is easy to see. After a 1 the two models cannot agree on any second token. The true product knows that and avoids a first token 1. The naive plan only finds out too late.

Multiply step by step, or do it right

Model 1 is fixed as above. You set how often model 2 picks token 1 after a first token 0 and after a first token 1. Gray bars are the naive plan. Teal bars are the true product.

0.90
0.90

Toy models with two binary tokens, invented for this lesson. The paper gives the formula, not this example. Naive plan: first token drawn from p1 × p2 renormalized, then second token drawn from p1 × p2 renormalized. True product: sum over all four sequences of p1(x) p2(x), renormalized once.

Move the sliders so model 2 matches model 1 (0.9 after 0 and 0.1 after 1). A(1) climbs and the two bars come together. They differ most when the models disagree about what follows a token.

Diffusion models: the same trap at every noise level

A diffusion model makes an image by starting from pure noise and removing a little noise at each step. At each noise level it learns a score: an arrow that points toward more likely data. One might add the two models’ scores and run the normal reverse process. The paper warns that two learned scores are not directly composable, because they do not equal the noisy gradient of the product distribution (Du et al., 2023a).

The cause is the same kind as above. A noisy version of a distribution is a blurred copy of it. Blurring the product is not the same as multiplying two blurred copies. A model trained on one noise level knows the blurred version of its own distribution, not of the product. The paper also notes that using the reverse diffusion process directly on the composed score does not sample from the composed distribution.

What does compose

An energy-based model composes without fuss, because adding energies gives the product directly (Chapter 3). So the paper’s plan is to read diffusion models as energy models, one at each noise level, and sample with MCMC. That is Chapter 5.

Language models have one more difficulty. Proprietary models often hide their logits (the raw scores before the final probabilities). The paper’s option is to combine the models in language space. Each model writes an answer, the answers are put into a shared context, and a final model reads them. This is the multiagent debate method of Du et al. (2023b).

Why is multiplying two autoregressive models’ next-token probabilities at every step not the same as sampling from the product of the two sequence distributions?

Chapter 5

Sampling the Product: Continuous Data

Walk downhill on the summed landscape with a little shaking, and see how a diffusion model does the same at every noise level

You are blindfolded on a hillside, and you want to reach a valley. You cannot see, but your feet feel the slope. So you step downhill. A friend nudges your shoulder at random each step, so you do not get stuck in the first small dip.

That is the sampler this chapter builds. It needs only the slope of the energy, and slopes of stacked landscapes are easy: they add.

Why plain guessing fails

To draw a sample from an EBM you need a point x with low energy. The paper says that a plain random search for such a point gets worse as the dimension D rises. An image has thousands of numbers, so almost every random guess has high energy.

The fix is to use the gradient of the energy, written ∇xE(x). The gradient is a list of D numbers, one slope for each coordinate. It points uphill. Moving against it goes downhill.

Langevin dynamics

Langevin dynamics is the downhill walk with random nudges. The paper gives the update from Du and Mordatch (2019).

xt
The sample after step t. Shape: the same as the data, for example 3 × H × W for an image.
xt−1
The sample one step earlier. At t = 0 it is uniform noise.
λ
The step size: how far one step moves along the slope.
∇xE(x)
The slope of the energy at x. For a composed model it is the sum of the slopes of each model.
ε
A random nudge from a normal distribution with spread σ. It keeps the walk from freezing and makes the samples spread over all valleys.

A worked step, in one dimension. Let E(x) = (x − 2)² / 2. Its slope is x − 2, and the only valley is at 2. Start at x = 5 and take λ = 0.5, ignoring the nudge. Step 1: 5 − 0.5 × 3 = 3.5. Step 2: 3.5 − 0.5 × 1.5 = 2.75. Step 3: 2.75 − 0.5 × 0.75 = 2.375. Each step halves the distance to the valley. With the nudge added, the walker then jitters around 2.

Composition costs one extra addition

For the product of two models the energy is E1 + E2, and slopes add: ∇E = ∇E1 + ∇E2. The code calls each model once for its slope and adds the two. The paper says the same sampler handles products, mixtures and inversions, once each is turned into a composed energy.

Try it. The device starts 140 points at random in a square. The two factors are the stripe landscapes from Chapter 3.

Walk downhill on the sum

Dots are samples. The faint pattern is the target. Drag the steps slider to replay the walk. Then switch the second factor off and replay.

0

Illustrative: 3 stripes per factor, spread 0.06, step size λ = 0.0015 and nudge spread √(2λ), with positions clamped to the square, from a fixed seed. “On a crossing” means within 1.5 spreads of a stripe in both coordinates. This is Langevin sampling as in the paper’s Section 5.2, not one of its experiments.

With only Factor 1 on, the points gather on vertical stripes but stay spread out along them. The second coordinate feels only the nudge. Turn Factor 2 on and the points collect at the crossings. The count at the bottom shows it.

The diffusion version: many energies in a row

Most strong image models today are diffusion models. The paper explains how to compose them. A diffusion model has T learned denoising functions ε(x, t), one for each noise level t. The paper reads each as the slope of an energy: ∇xE(x, t) = ε(x, t). That makes T energy models in a row. The first, at level T, is plain Gaussian noise. The last, at level 0, is the data distribution.

To sample, the paper uses annealed importance sampling. In plain words: start from noise, and at each noise level take several MCMC steps on that level’s energy before moving to the next, less noisy level. To compose two diffusion models, add their energies at every level k: e−(E1(x, k) + E2(x, k)). Then run the same procedure.

The paper stresses that the extra steps matter. Running the ordinary reverse process once per level on the composed score does not sample from the composed distribution. You must repeat the update at each level.

Reusing the reverse step

You do not need new code for the MCMC step. Appendix A shows that one ordinary reverse diffusion step at a fixed noise level is a step of ULA, the unadjusted Langevin algorithm, up to the size of the noise. The reverse step adds noise with scale √βt. ULA with step size η adds noise with scale √(2η). Set η = βt and the two differ by a factor √2.

So there are two choices. Scale the added noise by √2 and you run exact ULA. Or leave it alone and you sample a tempered variant of the distribution with temperature 1/√2, which gives less random samples. In both cases, composition needs only the score function of the composed model and the standard reverse step applied several times at each noise level.

The data flow

Here is the whole sampler as steps with shapes. Let x have shape (B, C, H, W): B images, C channels.

  1. Draw x from Gaussian noise, shape (B, C, H, W).
  2. For each noise level k from T down to 1, repeat R times: call model 1 and model 2 on (x, k). Each returns a score of shape (B, C, H, W).
  3. Add the two scores. Take one reverse step with the sum.
  4. Move to level k − 1. At the end, x is the sample.

The cost is R times that of a single diffusion model, times the number of models. The paper does not give a value for R.

In the Langevin update, what do you do to sample from the product of two energy-based models?

Chapter 6

Sampling the Product: Discrete Data

Use one model to propose and another to accept, and see why the unknown constant cancels

Suppose you write a code of 64 letters, and two judges score it. One judge likes words that sound natural. The other likes words that fit a theme. You want codes that both judges like. You cannot roll downhill here: a letter has no slope. The change from “a” to “b” has no “a little bit”.

Chapter 5 needed gradients, and gradients need smooth numbers. Text, protein letters and quantized images are discrete: each position holds one choice from a list. This chapter gives the paper’s two tools for that case.

Tool 1: Gibbs sampling

The paper first names Gibbs sampling. Pick one position i. Hold all the other positions fixed. Resample position i from its conditional energy E(xi | x−i), where x−i means “everything except position i”. Do this for each position in turn, again and again.

It works, but the paper says it becomes inefficient as the dimension rises. A change at one position needs many sweeps to travel through all the others. The paper also says the gradient trick does not apply here, although it points to discrete analogs (Grathwohl et al., 2021).

Tool 2: one model proposes, the other accepts

The cheaper idea uses a trained model as a source of guesses. We want samples from the energy E(x) = E1(x) + E2(x). Model 1 can already draw samples from e−E1. Model 2 can score any sample. So we draw from model 1 and let model 2 decide.

The paper calls the step a Metropolis-Hastings step. Starting from the current sample xt, it does this.

  1. Draw a candidate xt+1 from model 1, the distribution e−E1. This draw ignores xt.
  2. Compute the acceptance rate a = clip(eE2(xt) − E2(xt+1), 0, 1). Clip means: if the value is above 1, use 1.
  3. Draw a random number u between 0 and 1. If u < a, keep the candidate. Otherwise keep xt again.

Read the formula. If the candidate has lower energy under model 2 than the current sample, the exponent is positive, so a = 1 and you always accept. If the candidate is worse under model 2, you accept it only sometimes.

Why only E2 appears

Metropolis-Hastings accepts a move from x to x′ with probability min(1, [π(x′) q(x)] / [π(x) q(x′)]). Here π is the target and q is the proposal. Our target is π(x) ∝ e−E1(x) e−E2(x). Our proposal is q(x) = e−E1(x) / Z1, where Z1 is model 1’s normalizer.

π(x′) q(x) / [π(x) q(x′)]
The Metropolis-Hastings ratio. It compares moving to x′ with staying at x. The constant Z1 sits in both q terms and cancels.
e−E1(x′) e−E2(x′)
The target at the candidate x′.
e−E1(x)
The proposal at the current sample, up to Z1.
e−E1(x) e−E2(x)
The target at the current sample.
e−E1(x′)
The proposal at the candidate, up to Z1.
eE2(x) − E2(x′)
What is left: only model 2’s energies. This is the paper’s acceptance rate, before clipping to 1.

All the E1 terms cancel. So does the unknown constant Z1. We never need to normalize anything, and model 1 only needs to be good at producing samples. Model 2 only needs to give a score.

A worked example, with the three restaurants

Use model 1 = Maya (0.5, 0.3, 0.2) and model 2 = Jon (0.1, 0.3, 0.6) from Chapter 2. Jon’s energies are E2 = −ln p2: noodles 2.30, steak 1.20, pizza 0.51. Suppose the chain sits at noodles and model 1 proposes pizza. The exponent is 2.30 − 0.51 = 1.79, so a = min(1, e1.79) = min(1, 6.0) = 1. Accept. Now sit at pizza and propose noodles. The exponent is 0.51 − 2.30 = −1.79, so a = e−1.79 = 0.17. Accept 17 percent of the time.

Over a long run, the chain spends time on noodles, steak and pizza in the ratio 0.19 : 0.35 : 0.46, which is the normalized product from Chapter 2. Run it in the device and compare the bars with the exact answer.

Propose with one, accept with the other

Sixteen possible samples. Model 1 and model 2 each prefer a region. Teal bars show how often the chain visited each state. The blue outline is the exact product. Drag the number of steps, then move the peaks.

300
5
9

Toy: each model is a bell-shaped energy over 16 states with spread 2.5. The chain starts at state 0 and uses a fixed seed, with no burn-in removed. Proposals come from model 1 exactly as in the paper’s Section 5.3; the numbers are not from the paper.

Move the peaks far apart. The chain proposes states near model 1’s peak, and model 2 refuses most of them. The accept rate collapses and the histogram needs many more steps to settle. That is the symptom. The measurement is the acceptance rate in the read-out. The fix, when you can, is to propose from a model that is closer to the product, or to run longer.

Where the paper points

The paper cites two uses of this idea: composing ensembles of pre-trained models by iterative consensus (Li et al., 2022), and language models that generalize beyond natural proteins (Verkuil et al., 2022). Both use one generative model as a proposal and other energies as the acceptance rule.

In the proposal-and-accept sampler, why can we skip computing the normalizing constants of both models?

Chapter 7

New Tasks Without Training

Build a planner, a constraint solver and a stylist by multiplying models that already exist

You have a map app that knows which roads exist. It can wander along legal roads, but it knows nothing about where you want to go. You want a route from home to a cafe. Do you collect thousands of trips and train a new model? The paper says no. Add one more model that likes only routes that start at home and end at the cafe, and multiply.

This is the second benefit from Chapter 0: programming a new generative model. The paper says such programming needs no explicit training or data, and works even on distributions where no data exist.

Planning: a path model times a goal model

Let τ be a trajectory, a sequence of states. Let p(τ) be a model that samples legal but otherwise unconstrained paths. Let r(τ, s, g) be a model with high score when τ starts at s and ends at g, and low score everywhere else. Chapter 2 gave the product: q(τ) ∝ p(τ) r(τ, s, g). The paper calls probability a currency, because the two models trade only in probability and need no other interface.

Here is a tiny case with every step. Take a corridor of three cells A, B, C. A walker steps to a random neighbor each time. Start at A, goal C, two steps. The walker’s paths are A → B → A, with probability 1 × 0.5, and A → B → C, with probability 1 × 0.5. The goal model r gives score 1 to paths that end at C and 0 to others. The product keeps only A → B → C, with raw score 0.5. Dividing by the total, 0.5, gives probability 1. The walker alone reached the goal half the time. The composed model reaches it every time.

Exact sampling on a grid

We can do the same on a grid exactly. Let p be a walker that moves to a uniformly random free neighbor each step. Let r say: end at the goal after exactly T steps. Define the backward score βt(s): the probability that a walker standing at cell s at time t ends at the goal at time T. It starts as βT(s) = 1 if s is the goal and 0 otherwise. Then step back: βt(s) = the average of βt+1 over the neighbors of s.

q(s′ | s, t)
The composed model’s step: the chance of moving from cell s to neighbor s′ at time t.
∝
Proportional to.
p(s′ | s)
The plain walker’s step, one over the number of free neighbors.
βt+1(s′)
How likely the plain walker is to reach the goal on time from s′. It acts as the goal model r.

The grid makes the product exact, so no MCMC is needed. The device uses it. It is our illustration of q(τ) ∝ p(τ) r(τ, s, g), not the paper’s experiment. The paper’s planning evidence is Figure 7, which comes from Janner et al. (2022).

Add a goal without training

Fourteen paths on a 6 by 6 grid with walls. The start is bottom left and the goal is the green square at top right. Switch the goal model on and off, and change the time allowed.

12

Illustrative grid and walls, invented for this lesson. The walker moves to a uniformly random free neighbor, never staying put. Composed paths use the exact backward scores β, so no approximation is involved. The percentages are computed from the grid, not from the paper.

With the goal model off, the paths wander. Most never reach the green square, and the chance of success is tiny. With it on, every path ends at the goal and still uses only legal moves. Nothing was trained for planning. The walker is unchanged; r adds the constraint.

The same trick in other settings

The paper lists several more. Each is a product of existing models, and each cites its figure.

TaskCompositionWhat it shows
Object arrangement (Fig. 8)q(V) ∝ ∏c pc(Vc | Uc)Each constraint, such as collision-free, is a small factor over a few variables. Sampling the product solves the arrangement problem.
Hierarchical planning (Fig. 9)pLLM pVideo pActionA language model, a video model and an action model, all pre-trained on Internet data, are combined so that text plan, image plan and action plan agree.
Image tapestries (Fig. 10)q(x | D) ∝ ∏i p(xbboxi | texti)One model for each box region and its text, combined into a detailed scene.
Video style (Fig. 11)ppretrained(τ | text) padapt(τ | text)A big video model times a small model of one style gives stylized video.
Language (MATH)p(x) ∝ ∏i pi(x), in language spaceFive GPT-3.5 instances reach 58.0 ± 2.8%, above GPT-4 at 55.0 ± 2.9% (Du et al., 2023b).

Take the object arrangement row. The problem is a graph G = ⟨V, U, C⟩. V holds decision variables, such as an object’s pose. U holds conditioning variables, such as an object’s shape. C holds constraints. Each constraint c becomes a factor pc over only the variables it touches, which is low-dimensional. This is Chapter 1 again: small factors, cheap to learn, and the product handles new graphs.

In the hierarchical case the product assigns high score to a text plan that is plausible for the goal g, consistent with an image plan from observation o, and consistent with the actions that reach it. Sampling finds the three plans that satisfy all three models together. No model was trained on all three.

What this section does and does not prove

The paper’s own words are careful: the evidence is in earlier work, which it cites for each figure. For planning it says quantitative results are in Janner et al. (2022). For constraint solving it cites Yang et al. (2023b), and for hierarchical planning Ajay et al. (2023). The MATH number is the one quantitative result printed in this paper. Treat this chapter as a map of where composition has worked, with each claim tied to its source.

How does the paper build a goal-reaching planner from a model p(τ) of legal trajectories?

Chapter 8

Discovering the Pieces

Let a model find the factors itself, then recombine them, and measure what a wrong independence guess costs

Imagine a toy box that holds a jumble of cubes, spheres, trucks and boots. Nobody labeled the pieces. Still, if you look at many photos of the box, you start to notice that the world is made of objects, and each object can appear or not appear on its own.

The earlier chapters assumed that a person tells the model which factors to use. The paper’s third benefit is that, in many cases, the factors can be found from data with no labels. This is the least developed part of the paper, and it has the most limits. We look at it closely.

The recipe: a product with learned factors

Write the model as a product of K factors, and learn the factors by maximum likelihood, which means choosing the model that makes the training data most probable. The paper writes the product as pθ(x) ∝ ∏i piθ(x). Each piθ has its own parameters, and the same learning rule discovers them. The paper says learned factors give both more data-efficient learning and new samples for new tasks, as in Chapters 1 and 7.

Example 1: factors of one image

Given an image x of a scene, the paper models its pixels as a product over components. Each component is conditioned on a small code from its own encoder.

pθ(x)
The model of the image x. The symbol θ stands for all learned weights.
∝
Proportional to.
∏i
Multiply over the components i, such as one per object.
pθ(x | Enci(x))
Component i: a generative model of the image, given the code Enci(x) that encoder i read from the image.

The encoder is a neural network with a low-dimensional output. That small size is the whole trick. Think of K reporters who each get a single sticky note to describe the scene. No reporter can describe everything, so they divide the work. One writes about the cube, one about the sphere, one about the lighting.

Here is the data flow, with illustrative shapes, since the paper does not give them. An image x has shape (B, 3, H, W). Encoder i returns a code zi of shape (B, d), with d small, for each of the K components. Component i is a generative model, such as a diffusion model, that takes x and zi. The composed model adds the component energies, as in Chapter 5. Training makes the product reconstruct x, which the paper calls training to autoencode images with this likelihood.

The paper reports that each component then finds an interpretable decomposition: individual objects in a scene, and global factors such as lighting (Du et al., 2021; Su et al., 2024). Figure 12 shows the payoff. A model trained on cubes and spheres gives components pθ(x | z1) and pθ(x | z2). A separate model trained on trucks and boots gives pφ(x | z3) and pφ(x | z4). Multiply all four to draw a scene with objects from both data sets.

Example 2: relations between particles

For N particles moving together, the paper discovers one factor for each pair of particles: pθ(τ) ∝ ∏i,j, j≠i pθ(τ | Encij(τ)). Here Encij encodes how particle i and particle j interact. In Figure 13, one particle system has hidden springs and another has hidden charges. Swap the discovered pair factors between the systems, and you can simulate the forces of one on the particles of the other (Comas et al., 2023).

Example 3: classes from a pile of images

For images drawn from five ImageNet classes, the paper learns components with weights.

pθ(x)
The model of the image set.
∝
Proportional to.
pφ(w | x)
A model that chooses the weights w for an image x.
piθ(x)wi
Component i raised to the weight wi. A weight near 0 switches the component off. A weight near 1 keeps it on.

The paper reports that the discovered components correspond to the original classes (Figure 14). Components can be composed to make images that contain more than one class (Liu et al., 2023).

What happens when the independence guess is wrong

All three examples assume the data really is a product. The paper says so in its limitations: current work assumes data is naturally an independent product of components. In real data, spurious correlations (links that hold in the training set but not in general) break that assumption, and the algorithms can then fail.

We can measure the damage in the simplest case. Two variables x and y are linked by a correlation ρ. A factored model uses only each variable’s own distribution. Its error is the number of nats (a unit of information, like bits but with the natural logarithm) per sample that it loses. That loss equals the mutual information between x and y. For two Gaussian variables it has a standard closed form, −½ ln(1 − ρ²). This formula is textbook, not from the paper.

Use it in the device. Drag the correlation up and watch the right panel: the factored model keeps each variable’s spread but loses the link.

Break the independence guess

Left: data in which x and y are linked. Right: samples from a model that multiplies the separate distributions of x and y. Drag the link strength.

0.80

Illustrative: 240 seeded points from two unit-variance Gaussian variables. The factored model keeps the exact marginals of x and y and shuffles the pairing. The mutual information formula for Gaussians is standard. The sample correlation is measured on the plotted points.

At ρ = 0 the two panels look alike and the loss is 0. At ρ = 0.8 the loss is −½ ln(1 − 0.64) = 0.51 nats per sample. At ρ = 0.95 it is 1.16. The symptom in a real system is a model that draws pairs that never occur together. The measurement is the link between the variables. The fix is to put linked variables in one factor, or to learn the structure instead of assuming it.

The paper’s list of limits

The paper names three. The structure of the composition is fixed by hand, so the model cannot flexibly adapt it to new tasks. It also wants systems that discover the right structure and the right weight for each model. Discovery assumes independence. And there is no theory yet that explains compositional generalization in these systems, although earlier theory covers additive models (Wiedemer et al., 2024; Lachapelle et al., 2024).

Why do the encoders in the discovery recipe have a low-dimensional output?

Chapter 9

The Field Guide

Review the paper on one page: the numbers, the terms, a checklist, the core code and where to read next

You can now state the paper from memory. Large monolithic models cost more each year and still miss simple combinations. Small models, each covering a piece, can be combined by multiplying their probabilities. That needs fewer samples, reaches combinations never seen, builds models for new tasks without training, and in some cases finds the pieces itself. The price is a harder sampling problem, a structure you must usually choose by hand, and an independence assumption that can fail.

The numbers

WhatNumberWhere
Growth of training costabout 3 times every year; several hundred million dollars per runFigure 1, Epoch data
Data to learn one variableO(K) samplesSection 2, Canonne (2020)
Data to learn four variables jointlyO(K4) samplesSection 2
Factored cells for p(A) p(B) p(C, D)K + K + K²; with K = 10 that is 120 against 10,000Chapter 1 arithmetic
Maze2D setting4D state, 2D action, chunk size 8, about 10,000 steps per episodeFigure 5
Five composed GPT-3.5 on MATH58.0 ± 2.8% against GPT-4 at 55.0 ± 2.9%Section 2, Du et al. (2023b)
Noise gap between a reverse step and ULAa factor of √2; leaving it gives temperature 1/√2Appendix A
Discrete acceptance ratea = clip(eE2(xt) − E2(xt+1), 0, 1)Section 5.3

The figures, one line each

FigureWhat it shows
1Training compute from GPT-3 to Gemini Ultra, up about 3 times a year.
2GPT-4V and DALL-E 3 failing on simple spatial and compositional requests.
3Two per-axis models cover the full square from a narrow band of training data.
4Composed models fit simple products and mixtures better than one model given twice the data of each factor, so the same total.
5Factorized trajectory models have lower dynamics error with few episodes and train in fewer iterations.
6Images from long text descriptions, built from one model per sentence.
7 to 11Planning, object arrangement, hierarchical planning, image tapestries, video stylization.
12 to 14Discovered objects, relation potentials and image classes, recombined.
15A decentralized agent made of models for each modality, communicating through the joint distribution.

The terms

A checklist before you compose

  1. Can the target be written as a product of factors that each touch few variables? If not, expect to lose the links.
  2. Does each factor see every value it will be asked about? Composition reaches new combinations only then.
  3. Can you read each model’s energy or score? Language models with hidden logits need language-space combination.
  4. Do the factors agree somewhere? A tiny normalizer Z means the product is empty.
  5. Which sampler fits the data? Slopes for continuous data, propose and accept for discrete data.
  6. Did you repeat the update at each noise level of a diffusion model?

The core as code

This is a sketch. models stands for any list of trained score functions. It follows Sections 5.2 and 5.3 and Appendix A, and it leaves out the importance weights that a full annealed sampler would track.

pythonimport math, random, torch

def composed_score(models, x, k):
    # slopes add, because the energies add (Ch 3). Each model(x, k) returns grad_x E_i(x, k).
    return sum(m(x, k) for m in models)               # shape (B, C, H, W)

def sample_composed_diffusion(models, shape, betas, abar, R=4):
    x = torch.randn(shape)                                # Gaussian level, (B, C, H, W)
    for k in reversed(range(len(betas))):              # noise level, high to low (Ch 5)
        for _ in range(R):                              # several MCMC steps per level
            g = composed_score(models, x, k) / math.sqrt(1 - abar[k])
            x = x - betas[k] * g + math.sqrt(2 * betas[k]) * torch.randn_like(x)   # ULA: noise sqrt(2 beta)
    return x

def mh_compose(propose1, energy2, x0, steps):
    x = x0
    for _ in range(steps):
        y = propose1()                                  # draw from model 1, e^{-E1} (Ch 6)
        a = min(1.0, math.exp(energy2(x) - energy2(y)))   # E1 and Z cancel
        if random.random() < a: x = y
    return x

Where this sits in the field

The paper is a position paper from MIT. It builds on a line of work by the same group: composable diffusion models for visual generation (Liu et al., 2022), energy-based composition and MCMC sampling (Du et al., 2023a), and multiagent debate (Du et al., 2023b). It also connects to older ideas, such as probabilistic graphical models, products of experts (Hinton, 2002) and the “daemons” of Selfridge (1988), which Figure 15 uses to describe separate models passing messages through a joint distribution.

The paper adds one practical argument: small component models can be built by separate groups, checked one at a time, run on small machines and placed on separate computers. It offers this as a direction next to scaling, not a replacement for it.

This reading belongs to Lecture 9, Multimodal Generation of MMAI, which covers how generative models handle several modalities.

Keep going

The takeaway. Probability is a currency. Small models that each price a piece of the world can be multiplied into a model of the whole. You get fewer samples, new combinations, new tasks and sometimes the pieces themselves. You pay with harder sampling and with the risk that the pieces are not independent.
You have two trained models and want one that satisfies both of their constraints on a task nobody trained for. What does the paper tell you to do, and what must you check?

Now press Present or Teach and explain the paper out loud from memory: why a joint table is expensive, what product and mixture do, why adding energies multiplies models, why naive step-by-step multiplication fails, how Langevin and Metropolis-Hastings sample the product, and what breaks when independence is false. Then go back to the instrument and hide the middle block again.

Compositional Generative Modeling: A Single Model is Not All You Need
Read the paper · MMAI course schedule · Lecture 9 · Back to Gleams