Faith and Fate: Limits of Transformers on Compositionality

Multiplying two 3-digit numbers by the long method takes a few dozen small steps: one-digit products, carries, sums. GPT-4 got 59% of such problems right zero-shot and ChatGPT 55%. The authors wanted to know whether failures like this are accidents or a pattern.

They write an algorithm's execution as a computation graph. Each node is an intermediate value, each edge says which values a step used, and the graph's depth (longest chain of steps) and width (how many values are live at once) measure how compositional an instance is. They build three tasks this way: multi-digit multiplication, Einstein's logic grid puzzle, and a dynamic-programming problem (the best sum of a sequence's non-adjacent elements).

Then they push the models as hard as their budget allowed. Zero-shot and few-shot accuracy fell toward zero as the graphs grew. GPT-3 fine-tuned on about 1.8 million multiplication pairs, with or without step-by-step scratchpads, was near perfect on sizes it had seen and failed on larger ones; training far past the point where in-domain accuracy plateaued did not change that. Correctly answered test problems had sub-computations that appeared far more often in training. Most wrong nodes were wrong because an earlier node was wrong. Two propositions formalize the last point: if each step fails with some probability and recovery is unlikely, the chance of a correct final answer shrinks geometrically with the number of steps.

This paper explains a pattern you will see in customer deployments: a model handles the small version of a task and falls apart on the large one.

Count the steps. If a workflow chains 50 dependent steps and each is right 99% of the time, about 60% of runs finish correctly. Whether the steps happen inside one long answer or across an agent's tool calls, the arithmetic is the same. Cutting the chain length or adding checks between steps does more than prompting.

Give exact work to tools. Multiplication, totals, joins and date arithmetic are exactly the tasks whose graphs grow with the input. The paper's own recommendations are to use transformers for tasks with few compositional steps, where approximate answers are acceptable, or alongside planners and refinement. In practice that means calling a calculator, a SQL engine or a solver for the exact parts.

Test beyond what you tuned on. Fine-tuning on a customer's examples up to a size makes the model look excellent on that size. The paper's out-of-distribution results are the warning: build a test split with larger or deeper instances than training contained before claiming the model "learned the procedure".