Zach Furman

Instead, we write a program.

we break the problem down hierarchically into a sequence of simple, reusable steps.

Each step, like a logic gate in a circuit, is a tiny lookup table, and we achieve immense expressive power by composing them.

This matches what we see empirically in some deep neural networks via mechanistic interpretability.

They appear to solve complex tasks by learning a compositional hierarchy of features.

A vision model learns to detect edges, which are composed into shapes, which are composed into object parts, wheels, windows, which are finally composed into an object detector for a car.

The network is not learning a single, monolithic function.

It is learning a program that breaks the problem down.

This parallel with classical computation offers an alternative perspective on the approximation question.

While the UAT considers the case of arbitrary functions, a different set of results examines how well neural networks can represent functions that have this compositional, programmatic structure.

One of the most relevant results comes from considering Boolean circuits, which are a canonical example of programmatic composition.

It is known that feedforward neural networks can represent any program implementable by a polynomial-sized Boolean circuit using only a polynomial number of neurons.

This provides a different kind of guarantee than the UAT.

It suggests that if a problem has an efficient programmatic solution, then an efficient neural network representation of that solution also exists.

This offers an explanation for how neural networks might evade the curse of dimensionality.

Their effectiveness would stem not from an ability to represent any high-dimensional function, but from their suitability for representing the tiny, structured subset of functions that have efficient programs.

The problems seen in practice, from image recognition to language translation, appear to belong to this special class.

There's a details box here with the title Why Compositionality, specifically.

Evidence from depth separation results.

The box contents are omitted from this narration.