Zekun WangTest-Time Compositional Generalization
Composing a held-out combination from prototypes discovered at test time
Zekun Wang, Anant Gupta, Tianyi Zhu, Christopher J. MacLellan. Georgia Institute of Technology and University of Virginia.
A grid of the 16 pairs of digit color and background color in ColorMNIST. The model is trained on 12 pairs, and 4 are held out. The query is an image of a held-out pair, a green digit on deep red. Mode ascent ends at prototypes of seen pairs: cyan on deep red, green on dark brown, yellow on dark brown, cyan on dark purple, and pink on dark purple. The product of experts takes the background from the prototype on deep red and the digit color from the green prototype, and its mean is a green digit on deep red. Eight samples guided by it are green digits on deep red.- The model is trained on 12 of the 16 pairs of digit color and background color. Four pairs are held out.
- At test time the model receives one image of a held-out pair: a green digit on deep red.
- Mode ascent ends at prototypes. Each shows a pair the model has seen. One has the background of the query, and one has its digit color.
- The product of experts takes the background from the prototype on deep red and the digit color from the green prototype. Its mean is a green digit on deep red.
- The product of experts guides the sampler. The samples are new images of the held-out pair, which the model never saw in training.
A diffusion model trained on ColorMNIST has seen green digits and deep red backgrounds, but never a green digit on deep red. Compositional generalization asks the model to produce such a held-out combination by recombining what it knows. Diffusion methods for this problem assume that the reusable concepts are given, through labels, prompts, or a learned concept library, and a held-out combination is not among them.
We ask whether the model can discover its own reusable prototypes. A prototype is a mode of a noisy marginal, the distribution that the forward process produces at one noise level. Mode ascent on the learned score reaches it at test time from one query image. A prototype keeps what the model has learned: from a query of a held-out combination, mode ascent ends on seen combinations, and each keeps part of the query.
We select the prototypes that explain the query and compose them into a product of experts, which takes each part of the query from the prototype that explains it best. Its closed-form score guides the composable diffusion sampler. On held-out compositions of ColorMNIST and CelebA, the samples reach 92.5% and 77.0% attribute correctness, within about a point of a near copy of the query, with a lower KID and a higher diversity. The same sampler conditioned on trained concept tokens reaches at most 39.3% and 63.4%.
Training covers every attribute value, but not every combination
Compositional generalization asks a model to produce what it has never seen by recombining what it knows. People do this after learning familiar parts, and the ability has long been linked to reusable primitives and operators for recombining them.1 Neural networks can interpolate well within a training distribution and still fail when familiar primitives appear in unfamiliar combinations.2
ColorMNIST makes the setting concrete. An image has a digit, a digit color, and a background color, which gives 160 combinations. We hold out four pairs of digit color and background color across all ten digits, so 120 combinations are seen in training and 40 are held out. Every digit and every color still appears in training. The model has seen green digits and deep red backgrounds, but never a green digit on deep red.
At test time the model receives one image of a held-out class, the query, and must generate other images of that class. Diffusion composition methods combine concepts that are already available, as labels, prompts, or a learned concept library.3456 A held-out class is not among them, and retrieval over the trained classes can only return a class the model was trained on. We ask whether the model can instead discover its own reusable prototypes and compose them into the held-out class.
A prototype is a mode of a noisy marginal
A diffusion model learns from data at every noise level. At level t the forward process turns a clean image into a noisy one, and the noisy marginal is the distribution of these noisy images.7
xt=αˉtx0+1−αˉtε,ε∼N(0,I)
The network predicts the noise in a noisy image. Up to a factor, this prediction is the score of the noisy marginal, the gradient of its log-density.8
sθ(xt,t)=−1−αˉtεθ(xt,t)≈∇xtlogpt(xt)
We use the score for discovery instead of reverse sampling. A prototype is a mode of a noisy marginal, a point where its density has a local maximum. Mode ascent starts from a noised copy of an image and follows the score.
xt(i+1)=xt(i)+ηsθ(xt(i),t)
A one-dimensional example. At a low noise level the noisy marginal has five modes, and mode ascent from the noised copies of two images reaches two different modes. At a higher noise level neighboring modes have merged, and both ascents reach the same mode. At a high noise level one mode is left, and both ascents reach it.
A draw from a noisy marginal is visibly noisy, but a mode is noise-free. At a mode the score vanishes, and by Tweedie’s formula the expected clean image is then the mode itself, rescaled.9 Around each mode we fit a local Gaussian. The mode is the location of the prototype, and the Gaussian is its extent.
Mode ascent needs no labels, no concept library, and no additional training. It uses the unconditional score, so it explores the full noisy marginal and not the conditional distribution of a trained class. The step size is set from the noise level and is halved whenever a step jumps across the mode, so no step size is tuned.
The noise level sets the level of abstraction
Up to a rescaling, the noisy marginal at level t is the data distribution smoothed by a Gaussian kernel, and the bandwidth of the kernel grows with t. The noise schedule therefore defines a scale-space over the data distribution.10 Mean-shift locates the modes of a density at one fixed bandwidth.11 The forward process fixes a ladder of bandwidths, and the pretrained score gives the gradient of the log-density at each of them. Recent work interprets the modes of the noisy marginals as a hierarchy of concept prototypes.12
For two images of each of four pretrained models, the image and its prototype at seven increasing noise levels. A CIFAR-10 horse and a red boat, two CelebA-HQ faces, a Siberian husky and a strawberry sampled from DiT-XL/2, and a golden retriever and a fire engine sampled from the text-to-image LDM. At higher noise levels each prototype shows a simpler version of its image and then loses the object.
We recover prototypes at noise levels from t = 10 to t = 990 on four pretrained models, without labels: the unconditional DDPMs for CIFAR-10 and CelebA-HQ, DiT-XL/2 trained on ImageNet, and a text-to-image latent diffusion model (LDM) with 1.45B parameters trained on LAION-400M.71314
The prototype of an image changes from level to level. On CelebA-HQ, facial detail and identity persist through the fine levels and give way to more generic faces. On the two larger models the prototype shows a simpler version of its object at a higher noise level. One image therefore yields several distinct prototypes, with changes in visual structure beyond a gradual loss of detail.
Images come to share prototypes as the noise level grows
We measure how far apart the prototypes of different images are with the symmetric KL divergence between their local Gaussians at the same level. At fine levels the prototypes are well separated. As t grows, the separation falls by four to six orders of magnitude on all four models.
We also count the distinct prototypes that the images of a model reach.
The number of distinct prototypes that the images of each model reach. At t = 100 nearly every image has its own prototype on all four models. One or two prototypes remain from t = 460 on the CIFAR-10 and CelebA-HQ DDPMs, from t = 580 on DiT-XL/2, and at t = 860 on the text-to-image LDM.
Every image has its own prototype at fine levels. At coarse levels all images of a model share one or two prototypes, from t = 460 on the two DDPMs, t = 560 on DiT-XL/2, and t = 820 on the LDM. Images with the same content share a prototype first: on DiT-XL/2 at t = 440, 44% of the pairs of images from the same class share a prototype, against 21% of the pairs from different groups of classes.
The prototype of one image does not change at a uniform rate. Its normalized displacement from the image changes slowly over the fine levels and then rises sharply, from t ≈ 450 on CIFAR-10, t ≈ 500 on CelebA-HQ, and t ≈ 600 on the two larger models. This agrees with the phase transitions and speciation times reported for diffusion models.1516
Mode ascent from a held-out combination ends on seen combinations
A prototype could be the image under a growing amount of blur. It would then depend only on the image and on the noise level, and not on what the model has learned. We test this on the ColorMNIST model. We take queries whose color pair is held out, and recolor each digit to two seen pairs, one that keeps the background and one that keeps the digit color.
On the grid of pairs, mode ascent from a held-out query, a green digit on deep red, ends on a seen pair. At t = 300 it ends on yellow on deep red: it keeps the background and replaces the digit color. At t = 400 it ends on green on dark brown: it keeps the digit color and replaces the background. Mode ascent from the same digit recolored to a seen pair, yellow on deep red, keeps that pair. Over 40 queries at t = 300, 9.7% of the ascents from a held-out pair keep their pair, against 89.8% and 92.5% of the ascents from the two seen pairs.- A noised copy of each image. A draw from a noisy marginal is visibly noisy.
- One ascent step removes most of the noise.
- After three ascent steps the noise is gone.
- The later steps move the image toward a mode.
- After 40 ascent steps the image from the held-out pair shows a seen pair. The image from the seen pair still shows its pair.
A prototype keeps a color pair that the model has seen and replaces one that it has not. At t = 300, 89.8% of the ascents from a seen pair with the same background keep their pair, against 9.7% of the ascents from a held-out pair, which end on a seen pair instead. The images differ only in the color pair, so what a prototype keeps is set by what the model has learned and not by the amount of smoothing.
The prototype of a held-out query still keeps part of the query. In the figure, the ascent at t = 300 keeps the background and replaces the digit color, and the ascent at t = 400 keeps the digit color and replaces the background.
The text-to-image LDM has no held-out combination, but some combinations are rarer than others, such as a blue banana. Its prototypes keep a usual color longer than an unusual one: at t = 400 after 10 ascent steps, the usual color is kept in 95% of the images and the unusual one in 81%.
A product of experts takes each part of the query from the prototype that explains it
A single prototype rarely carries every factor of a held-out class, but the prototypes of seen classes carry its parts. We therefore ask whether an out-of-distribution query can be written as a combination of prototypes that the model already has. Given one query, we run mode ascent at several noise levels from noised copies of the query and of the model’s own unconditional samples, and collect a pool of candidate prototypes. Each mode is refined by a second ascent at t = 50, and its local Gaussian is fitted there.
A greedy selection keeps the K = 8 prototypes that jointly best explain the query per dimension. The selected prototypes combine into a weighted product of experts.3 The weights are per dimension: in each dimension, a prototype counts by how well it explains the query there. Different prototypes can therefore dominate different dimensions.
qT(x0)∝j∈SK∏qj(x0)wj
The eight prototypes selected for the query, a green digit on deep red, with the per-dimension weights of each. The weights of the prototypes on deep red are high on the background, and the weights of the green prototypes are high along the digit. The mean of the product of experts is a green digit on deep red.
For the query above, the weights of the prototypes on deep red are high on the background, and the weights of the green prototypes are high along the digit. The mean of the product of experts is a green digit on deep red: the held-out pair, composed from prototypes of seen pairs.
The product is a Gaussian with a closed-form mean and covariance, so the score of its noisy marginal is analytic at every noise level. Composable diffusion adds the score of a trained concept token to the unconditional score of the model.517 We add the analytic score of the product of experts in its place.
x^0=x^0∅+κt(μT−x^0∅),κt=(1−αˉt)[αˉtΣT+(1−αˉt)I]−1
This is the mean of the product of two Gaussians over the clean image: the estimate of the unconditional model and the product of experts. The pull toward the mean of the product of experts is strong at high noise levels, where the estimate of the model is uncertain, and vanishes at low noise levels, so the sampler needs no guidance weight.
Samples from one query are other instances of its held-out class
We evaluate on two benchmarks. ColorMNIST has 120 seen and 40 held-out classes. The CelebA benchmark has 74 combinations of 14 binary face attributes, of which 51 are seen and 23 are held out.18 A method receives one image of a held-out class and generates 16 samples. The other members of the class are used only for evaluation.
For one held-out ColorMNIST query, the digit 0 in green on deep red, and one held-out CelebA query: the query, three of its eight selected prototypes, and five samples each of our method, Comp. 1, Comp. 3, and SDEdit. On ColorMNIST our samples and those of SDEdit have the held-out pair of the query. The samples of Comp. 1 have a seen pair with the same background, cyan on deep red, and those of Comp. 3 a seen pair with the same digit color, green on dark purple. On CelebA the samples of Comp. 1 and Comp. 3 show other attribute combinations.
We compare with two baselines. Composable diffusion is conditioned on trained concept tokens of the same model: Comp. 1 uses the trained class under which the query has the lowest denoising loss, and Comp. 3 composes the three best.5 Their samples land on neighboring classes. On ColorMNIST they show the query’s background under another digit color, or its digit color on another background. SDEdit noises the query to a level t0 and denoises it with the unconditional model.19
Attribute correctness is the fraction of the class’s defining attributes that a sample carries. KID is measured between the 16 samples and the held-out members of the class.20 Diversity rewards samples that stay close to the query and differ from each other.21
SDEdit at t0 = 50 returns near copies of the query, with 92.9% attribute correctness on ColorMNIST and 78.3% on CelebA. Our samples reach 92.5% and 77.0%, with a lower KID and the highest diversity of all methods. Comp. 1 and Comp. 3 reach 37.7% and 39.3% on ColorMNIST, where assigning attribute values at random gives 20%, and 63.4% and 62.2% on CelebA.
On ColorMNIST our method reaches 92.5% attribute correctness at a KID of 0.079. SDEdit reaches 92.9% at 0.107 with t0 = 50 and 92.3% at 0.082 with t0 = 200. On CelebA our method reaches 77.0% at 0.166, and SDEdit reaches 78.3% at 0.218 and 77.1% at 0.179. At every attribute correctness that both methods reach, our method has the lower KID.
A larger t0 lowers the KID of SDEdit only together with its attribute correctness. At every attribute correctness that both methods reach, our method has the lower KID. On CelebA, SDEdit at t0 = 200 matches our attribute correctness, 77.1% against 77.0%, and there our KID is lower in all 23 held-out classes.
The held-out class is composed from prototypes of seen classes
We vary the number of selected prototypes K. Attribute correctness rises with K and saturates between K = 5 and K = 8: from 65.7% at K = 1 to 92.5% at K = 8 on ColorMNIST, and from 72.8% to 77.0% on CelebA.
On ColorMNIST, attribute correctness rises from 65.7% with one prototype to 92.5% with eight. With no ascent from the query it rises from 51.2% to 92.5%. On CelebA it rises from 72.8% to 77.0%, and from 59.6% to 77.1% with no ascent from the query. A near copy of the query reaches 92.9% and 78.3%, and Comp. 1 reaches 37.7% and 63.4%.
The result does not depend on ascents from the query. In a second pool, every candidate is reached from one of the model’s own unconditional samples, and the query enters only through the selection and the weights. With K = 8 this pool gives 92.5% on ColorMNIST and 77.1% on CelebA.
On ColorMNIST at least 95% of the selected prototypes are seen classes. A single prototype carries 1.5 of the three factors of the query on average, and eight prototypes carry 2.9. Eight prototypes jointly carry every factor of the query for 90.5% of the queries. A single prototype does for 2.7%.
Limitations and future work
Our protocol follows the standard setting of compositional generalization: the primitive factors are known, and the test cases are unseen recombinations of them. We evaluate composition through generalization to held-out attribute combinations, and we do not analyze compositional structure in the internal representations of the model.
Prototype discovery operates on the score of the trained model, so it inherits the inductive biases of that model. On ColorMNIST, a query with a black background, which lies between the four trained background colors, yields coherent prototypes and samples. A query with a white background collapses onto the trained dark backgrounds. A mechanism for detecting, consolidating, and reusing new primitives remains future work.