Attention is only as good as its witnesses: When higher-order layers help, and when they do not
The authors explain the Transformer's failures — not learning graph search as the graph grows, and needing many different problems before it learns the card game SET — as each layer computing a partition function over a family of witnesses and reading it off at a temperature. Two laws follow: a depth law, in which L layers of two-step walks cover exactly 2^L - 1 steps, with the corresponding construction verified in Lean; and a scale law, which requires inverse temperature times margin to be no less than the log of the number of candidates.
Why it matters: The paper reduces the power of higher-order attention layers to two laws, depth and scale, and gives a construction that matches a 73-million-parameter model on CLRS-30 with 186,000 parameters.