Compositional Learning: Building Complex from Simple

A search assistant that has never seen "red silk"

A fashion marketplace like Myntra or Flipkart trains a visual-question model on catalog images so shoppers can ask a listing page things like "how many blue cotton kurtas are shown here?" and get a number back. The training log has millions of question-answer pairs, but the label distribution is skewed the way real catalogs are skewed: silk garments in the training photos are overwhelmingly blue, green, or gold, because that is what sells in silk; red garments are overwhelmingly cotton or georgette, because that is what red is used for. The model sees "red" thousands of times. It sees "silk" thousands of times. It almost never sees them in the same sentence attached to the same product. Then a shopper opens a page of wedding sarees and types "how many red silk sarees are on this page?"

Nothing about the pixels is new — red is red, silk's sheen is silk's sheen, both well within what the model's vision encoder already resolves. What is new is the combination. If the model actually learned "red" as a reusable, independent piece of knowledge and "silk" as another reusable, independent piece of knowledge, it should be able to intersect them on a garment it has never labeled that way before. If instead it learned "red-cotton-ness" and "blue-silk-ness" as fused, un-decomposable patterns — because that is what the training data made cheapest to fit — it has no principled way to answer a query built from a combination it never saw. This gap, between mastering parts and correctly assembling a whole from parts in a configuration never demonstrated, is exactly what compositional learning studies.

The principle, and why deep networks don't get it for free

The idea has a name older than machine learning: the principle of compositionality, usually credited to the logician Gottlob Frege, states that the meaning of a complex expression is a function of the meanings of its parts and the rules used to combine them. "Red silk saree" means what it means because "red" contributes its meaning, "silk" contributes its meaning, "saree" contributes its meaning, and a fixed combination rule (adjectives modify the noun) glues them together — the same rule that lets you understand "blue cotton kurta" the first time you ever hear it, because you already know "blue," "cotton," "kurta," and the rule.

A standard neural network trained end-to-end on (input, output) pairs is not built to respect this. It is one large parametric function, free to route information however minimizes training loss, and nothing in gradient descent forces it to represent "red" as an isolable direction in some feature space that is reused identically whenever "red" appears, regardless of what else is present. If the training set never forces disentanglement, the network is entitled to take a shortcut: encode "this specific object is a red-cotton object" as one entangled feature rather than "red" and "cotton" as two separable ones — the loss doesn't know the difference, and the shortcut is usually the easier fit. Jerry Fodor and Zenon Pylyshyn made a version of this argument against connectionist networks in their 1988 paper "Connectionism and Cognitive Architecture: A Critical Analysis" (Cognition): they pointed out that genuinely compositional, symbolic systems have systematicity built in for free — if a system can represent "John loves Mary" it can represent "Mary loves John," because both sentences are constructed from the same primitives (John, Mary, loves) via the same combination rule (a transitive-verb frame), and the system that has one automatically has the machinery for the other. A network trained only on "John loves Mary"-shaped sentences has no such guarantee about "Mary loves John" unless something in its architecture or training forces the reuse.

That "unless" is the whole research program. You have already seen one place where this tension shows up: an attention head in a transformer, as covered in the deep-learning-foundations track, builds a representation for a token as a weighted combination of other tokens' representations — a soft, differentiable version of "which parts do I combine, and how." Compositional learning asks a sharper question of that same machinery: does the weighted combination generalize systematically to combinations of parts it never saw combined, or does it merely interpolate within the combinations training happened to include?

Neural Module Networks: composition as an architectural commitment

One influential answer, rather than hoping compositional structure emerges from a monolithic network, is to build it into the architecture directly. Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein proposed Neural Module Networks (NMNs) at CVPR 2016 for visual question answering. Instead of training one network per question type, they train a small library of reusable neural modules, each implementing one primitive operation over an image's attention maps — a Find module that locates instances of an attribute, an And/Filter module that intersects two attention maps, a Count module that reduces an attention map to a scalar, a Compare module, and a handful of others. A separate component (a semantic parser) reads the natural-language question and converts it into a short program specifying which modules to instantiate and how to wire their outputs into each other's inputs. Two different questions produce two different computation graphs, but both graphs are built from the same shared, jointly trained module weights.

This is the compositionality principle made literal in a computation graph: the "meaning" of a question — the procedure that computes its answer — is a function of which modules the question invokes (the parts) and the layout that wires them together (the combination rule). A module like Find(red) is trained once and reused inside every question that happens to need "find the red things," whether that question is about counting, comparing, or describing. Because the modules are shared and jointly trained across the full space of programs seen during training, the hope is that a novel program — one that recombines modules in an order not seen at training time — still works, since each module individually has learned a general operation rather than a question-specific one.

Worked example: tracing a program by hand

Strip away the learned CNN weights for a moment and make the mechanism concrete with a small, fully-computable catalog. Suppose an image encoder has already reduced a page of five saree photos to a simple attribute table (this is a pedagogical simplification of the real Find module, which in Andreas et al. is a small convolutional network producing a heatmap over image regions rather than a literal dictionary lookup — the arithmetic below is identical in spirit, just with the attribute lookup made explicit instead of learned):

catalog = [
    {"id": "p1", "fabric": "silk",       "color": "red"},
    {"id": "p2", "fabric": "silk",       "color": "blue"},
    {"id": "p3", "fabric": "cotton",     "color": "red"},
    {"id": "p4", "fabric": "silk",       "color": "red"},
    {"id": "p5", "fabric": "georgette",  "color": "red"},
]

import numpy as np

def find(catalog, key, value):
    # Module 1: produces an attention vector over the 5 catalog items,
    # one entry per item, marking where the attribute holds.
    return np.array([1.0 if item[key] == value else 0.0 for item in catalog])

def filter_and(attn_a, attn_b):
    # Module 2: intersects two attention maps elementwise.
    return attn_a * attn_b

def count(attn):
    # Module 3: reduces an attention map to a scalar.
    return float(np.sum(attn))

# Program for "How many red silk sarees are shown?"
a_silk = find(catalog, "fabric", "silk")
a_red  = find(catalog, "color", "red")
a_silk_red = filter_and(a_silk, a_red)
answer = count(a_silk_red)

print(a_silk, a_red, a_silk_red, answer)

Trace it by hand, item by item. a_silk checks fabric == "silk" against p1..p5: p1 true, p2 true, p3 false (cotton), p4 true, p5 false (georgette) — [1, 1, 0, 1, 0]. a_red checks color == "red": p1 true, p2 false (blue), p3 true, p4 true, p5 true — [1, 0, 1, 1, 1]. filter_and multiplies these elementwise: [1×1, 1×0, 0×1, 1×1, 0×1] = [1, 0, 0, 1, 0] — exactly p1 and p4, the two items that are both silk and red. count sums that vector: 1+0+0+1+0 = 2. The program prints [1. 1. 0. 1. 0.] [1. 0. 1. 1. 1.] [1. 0. 0. 1. 0.] 2.0, and the answer, 2, is correct by inspection of the catalog.

Notice what made this possible: find was called twice, once for "silk" and once for "red," using the identical function both times — the same primitive, reused with different arguments, the same way Find(red) in the real NMN is the identical trained module regardless of which question invokes it. If the shopper had instead asked "how many blue silk sarees?" the program would be count(filter_and(find(catalog,"fabric","silk"), find(catalog,"color","blue"))) — a different layout built from the exact same three functions, requiring no new training. That reuse across programs is the entire mechanism by which compositional generalization becomes possible: the number of programs expressible from three modules grows combinatorially, while the number of module weights to learn stays fixed.

The composition graph

Why sequence models don't inherit this for free: SCAN

NMNs bake composition into the architecture by construction. It is natural to ask whether an ordinary sequence-to-sequence network, given enough data, learns the same reuse on its own. Brenden Lake and Marco Baroni tested this directly at ICML 2018 in "Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks," introducing the SCAN benchmark: simple commands like "jump", "walk twice", "run around left twice" map to short action sequences (JUMP, WALK WALK, and so on) generated by a small, fully specified grammar. Trained and tested on random splits of this data, standard RNN encoder-decoders solve it almost perfectly — the primitives and modifiers ("twice," "around left," "and") all appear together in enough combinations during training that memorizing works.

The revealing experiment held out a systematic split: the word "jump" appeared during training only on its own, never combined with any modifier, while every other primitive ("walk," "run," "look") appeared with the full range of modifiers. At test time the network had to handle "jump twice," "jump around left," "jump and walk" — compositions of a primitive it knew perfectly well in isolation, with modifiers it knew perfectly well from other primitives, just never demonstrated together for "jump" specifically. Training accuracy stayed near ceiling. Generalization accuracy on this held-out compositional split collapsed to a small fraction of that, well under what near-perfect training performance would predict, even though every piece needed for a correct answer had individually been seen many times. The network had learned to produce correct outputs for the combinations training happened to contain, not a reusable representation of "jump" that composes with "twice" the way "walk" already did. This is the empirical face of the Fodor–Pylyshyn worry: fluency on the parts is not proof of a rule for combining them.

Misconception: modular architecture is not a guarantee

The natural conclusion to draw from NMNs — build the composition into the architecture and the generalization problem is solved — is one worth correcting directly, because it is wrong in a specific, informative way. Dzmitry Bahdanau, Shikhar Murty, Michael Noukhovitch, Thien Huu Nguyen, Harm de Vries, and Aaron Courville tested this at ICLR 2019 in "Systematic Generalization: What Is Required and Can It Be Learned?" Their finding: NMNs supplied with the ground-truth program for each question (bypassing the learned parser entirely) do generalize far better than an end-to-end seq2seq baseline on compositional splits — the modular structure is genuinely helping. But once the parser has to predict the program from the question text itself, as it must in any realistic deployment, accuracy on novel compositions drops well below the ground-truth-program number.

There are two separate failure points hiding inside "use a modular architecture," and conflating them is the misconception. First, the semantic parser — the component that maps a question to a layout — is itself a learned model trained on the layouts it happened to see, and it can fail to produce the right structure for a question requiring a module combination it never saw demonstrated, exactly the SCAN failure mode one level up, now applied to programs instead of action sequences. Second, even when the layout is correct, an individual module can receive attention-map inputs that lie outside the distribution it saw during training, because the upstream module that produced them was itself invoked in an unfamiliar combination — a kind of covariate shift internal to the computation graph, where a well-trained module is fed inputs shaped by a path through the graph it never experienced. Modularity gives the network the capacity to compose correctly; it does not by itself guarantee that the parser will choose the right composition or that every module will behave well when composed in a new way. Both the parser and the modules have to generalize, and they can fail independently.

Where this shows up now: composing tool calls

The same structure reappears, largely unremarked, in agentic LLM systems. An assistant built for something like IRCTC-style booking or bank customer support does not train one model per possible customer request; it exposes a small set of primitive tools — search, a calculator, a database query, a payments API, a calendar lookup — and generates, per query, a short program of tool calls with arguments, wiring one tool's output into the next tool's input. That is the NMN pattern again: a fixed library of primitives, a parser (now the LLM's own generation) choosing the layout, and the same reuse-across-programs argument for why a system can plausibly handle a request whose exact tool sequence it never saw during training, as long as it saw each tool used correctly in some other combination.

It also inherits the NMN pattern's systems cost. GPU training and serving are efficient when a batch of examples all execute the identical static computation graph, because identical operations across the batch fuse into a small number of large matrix multiplications. A modular system where every example can invoke a different subgraph of modules or tools breaks that assumption — naively, a batch of heterogeneous programs serializes into one example at a time, discarding most of the hardware's throughput. Moshe Looks, Marcelo Herreshoff, DeLesley Hutchins, and Peter Norvig addressed exactly this at ICLR 2017 in "Deep Learning with Dynamic Computation Graphs," proposing dynamic batching: automatically group operations of the same type across differently-shaped graphs within a batch, so that even though no two examples follow the same structure, same-type operations still execute together as large fused kernel calls. That is the general lesson for any production system built on compositional reuse — modularity buys generalization but taxes throughput, and it stays affordable only if the serving system is engineered to re-batch across heterogeneous graphs rather than assuming every request looks the same.

Active recall

Attempt each question before reading its answer.

1. State the principle of compositionality in one sentence, and identify the "atoms" and the "combination rule" in the saree-catalog NMN example.
2. In the worked example, p2 has color: "blue". Suppose a data-labeling fix changes p2's color to "red" (the original label was simply wrong). Recompute all four quantities: count(find(silk) & find(red)), count(find(red)), count(find(silk) & find(blue)), and count(find(blue)). Which of these change from the original worked example, and why?
3. In Lake & Baroni's SCAN "jump" split, the network reaches near-perfect training accuracy but generalizes poorly to "jump twice" and similar held-out compositions. Explain why high training accuracy on the individual primitive "jump" and high training accuracy on the modifier "twice" (applied to other primitives) do not entail correct behavior on "jump twice".
4. Using the Bahdanau et al. (2019) result, name the two separate points inside an NMN pipeline where compositional generalization can fail, and explain why supplying the ground-truth program (removing one of the two) improves accuracy so much.
5. Why does a batch of examples that each invoke a different composition of modules (or tools) hurt GPU throughput compared to a batch that all run the same fixed network? Name the class of solution that addresses this.

Answers.

1. The principle of compositionality: the meaning of a complex expression is a function of the meanings of its parts plus the rule used to combine them. In the saree example, the atoms are the outputs of the individual Find calls — the attention vectors for "silk" and for "red" — and the combination rule is the fixed Filter (elementwise AND) followed by Count; "how many red silk sarees" means whatever running that fixed combination rule over those two atoms produces.

2. Original vectors: find_silk = [1,1,0,1,0], find_red = [1,0,1,1,1], find_blue = [0,1,0,0,0], giving count(silk&red)=2, count(red)=4, count(silk&blue)=1, count(blue)=1. After correcting p2 from blue to red: find_red becomes [1,1,1,1,1] and find_blue becomes [0,0,0,0,0]. Recomputing: count(silk&red) = sum([1,1,0,1,0]×[1,1,1,1,1]) = sum([1,1,0,1,0]) = 3 (up from 2, gaining p2); count(red) = sum([1,1,1,1,1]) = 5 (up from 4); count(silk&blue) = sum([1,1,0,1,0]×[0,0,0,0,0]) = 0 (down from 1); count(blue) = 0 (down from 1). All four change, because p2's color attribute is a shared input read by every module that queries color — one label correction ripples into every downstream program that touches "red" or "blue," not only the query the correction was made for.

3. High accuracy on "jump" alone only shows the network can map the single token jump to the action JUMP in the specific context it was trained in — isolated, with no modifier attached. High accuracy on "twice" applied to walk, run, look only shows the network can apply the doubling operation to those specific primitives. Nothing in ordinary sequence-to-sequence training forces "twice" to be represented as an operation that applies uniformly to any primitive's output regardless of which primitive produced it; the network is free to learn "twice" as tied to the specific primitives it appeared with. So encountering jump and twice together for the first time at test time is a genuinely new combination the training objective never required the network to handle correctly, even though each ingredient was mastered separately.

4. The two failure points are (a) the semantic parser mapping the question to a program/layout, which can select the wrong module structure for a question whose module combination was not seen during training, and (b) an individual module receiving attention-map inputs that are out-of-distribution because the upstream module producing them was invoked in an unfamiliar wiring — a covariate shift internal to the graph. Supplying the ground-truth program removes failure point (a) entirely: the correct modules are guaranteed to be wired together regardless of what the parser would have predicted, isolating how much of the original gap was parser error versus module error. Bahdanau et al. found this recovers most of the performance gap, indicating the parser's structural predictions, not the modules' numerical behavior, are the dominant bottleneck.

5. GPU efficiency during training and inference comes from batching many examples through the identical sequence of matrix operations, so the hardware executes one large fused matrix multiply instead of many small ones. When each example in a batch invokes a different subset or ordering of modules (or tools), there is no single shared operation sequence to fuse across the batch — naive execution falls back to processing examples one at a time, or grouping only the rare examples that happen to share identical structure, discarding most of the parallelism the hardware is built for. The general solution class is dynamic (automatic) batching — as in Looks et al.'s TensorFlow Fold — which regroups same-type operations across structurally different graphs within a batch so they can still run as large fused kernel calls despite no two examples following the same computation graph.

Think About It

Think about this: How would you explain compositional learning: building complex from simple to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where compositional learning: building complex from simple is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting compositional learning: building complex from simple to at least 3 other topics you have studied.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind compositional learning: building complex from simple, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.