Papers With

← All papers
First page of Two hidden layer suffice: the caterpillar net

Two hidden layer suffice: the caterpillar net

Jakob Paul Zimmermann

cs.LG Oct 19, 2026 · v1
formalization ai-agents ml-theory combinatorics
Read PDF arXiv abstract Code
TL;DR
Results on two-hidden-layer ReLU representations of the maximum were obtained via AI-assisted proof search in Lean and formalized in a public repository.
Abstract
Every continuous piecewise linear (CPWL) function is a finite signed sum of maxima of affine functions, making maximum representation a central problem in the study of the expressiveness of ReLU networks. A now-disproved conjecture predicted logarithmic depth for maxima. Inspired by the proof by Brunck et al. (2026) that two hidden layers suffice for general CPWL functions, we give the Caterpillar Net, a nonrecursive construction for the maximum of $N$ inputs with two hidden layers of widths $O(N^2)$ and $2^{O(N\log N)}$. The construction has a direct geometric interpretation.
Problem

The work asks how to represent the maximum of N inputs exactly with a two-hidden-layer ReLU network, and how small the hidden layers can be. A conjecture predicting logarithmic depth for maxima has since been disproved.

Approach

The Caterpillar Net is a nonrecursive construction built from labelled caterpillar trees. Their edge and head functions define a dictionary of face functions. Alternating sums of support functions of caterpillar polytopes, corrected by face support functions and linear terms, yield the maximum exactly. Equal second-layer units are merged by normalizing hinge orientations. Definitions and theorems are linked to a Lean formalization, and the results were found through proof search in Lean using Claude Code and Codex.

Results

The maximum of N inputs is represented with two hidden layers of widths O(N^2) and 2^{O(N log N)}. A separate Lean development extends a known first-layer width lower bound of C(N,2) - floor(4N/3) to networks with affine skip connections. It sharpens the bound to C(N,2) - N when every first-layer weight vector is proportional to some e_i - e_j.