Two hidden layer suffice: the caterpillar net

Jakob Paul Zimmermann

cs.LGOct 19, 2026

Two hidden layer suffice: the caterpillar net

Authors: Jakob Paul Zimmermann

Organizations: FU Berlin · TU Berlin

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.

Figures & tables

Panel of Figure 1 — Figure 1: A labelled caterpillar with $N=10$ and $S=\{3,6\}$ . The spine $\pi(1)\to\pi(4)\to\pi(7)$ has two leaves at each vertex; all arrows point from parent to child. The apex $\pi(0)$ is separate from the tree. The last spine position is $q=6$ , so the head function is $h_{\pi,S}(x)=x_{\pi(7)}-x_{\pi(0)}$ .

ReLU Neural Networks

Rectified linear unit (ReLU) neural networks use piecewise-linear activations to study approximation, learning dynamics, expressivity, and verification.

See all 113 papers

Shallower ReLU Network Representations via Exact Linear Algebra
Jul 22, 2026Kilian Rueß, Gennadiy Averkov, Florestan Brunck +7Shallow Neural Networks ReLU Neural Networks
University of Technology Nuremberg · Brandenburg University of Technology Cottbus–Senftenberg · University of Copenhagen +3
Representing MAX functions using two-hidden-layer ReLU networks
Aug 25, 2026Zhimao Wang, Amitabh BasuReLU Neural Networks Neural Network Expressivity
Department of Applied Mathematics, Johns Hopkins University
A Hand-Checkable Proof That Two Hidden ReLU Layers Compute the Maximum of Six Numbers
Oct 3, 2026Dimitrios MyrisiotisReLU Neural Networks Neural Network Expressivity
Great Bay University China

Jul 22, 2026J/K move · Enter open · S save

Shallower ReLU Network Representations via Exact Linear Algebra

Kilian Rueß, Gennadiy Averkov, Florestan Brunck, Moritz Grillo+6

University of Technology Nuremberg · Brandenburg University of Technology Cottbus–Senftenberg · University of Copenhagen+3

Shallow Neural Networks ReLU Neural Networks Neural Network Approximation Theory

Open paper AskPDF arXiv

We study the depth required by ReLU networks to exactly represent piecewise linear functions, focusing specifically on the maximum function. This problem has recently received significant attention in both the ML and TCS literature. We prove that

\max_n(x)=\max\{x_1,\ldots,x_n\}

is exactly representable with two hidden layers for every

n\leq 12

. Previously, this was only known up to

n\leq5

[Bakaev, Brunck, Hertrich, Stade, Yehudayoff, STOC'26]. We obtain our constructions through an exact computer-assisted search within a space of candidate solutions: After a symmetry reduction, we obtain a finite system of linear equations over

\mathbb{Q}

such that any solution yields a valid representation of the maximum function. The resulting constructions have a structured first hidden layer, which enables recursive substitution into deeper networks. This yields an exact ReLU representation of

\max_n

with at most

\lceil \log_6(n/2) \rceil+1

hidden layers. Consequently, every continuous piecewise-linear function on

\mathbb{R}^d

admits an exact representation with at most

\lceil\log_6((d+1)/2)\rceil+1

hidden layers; in particular, two hidden layers suffice for

d\leq 11

. Again, these results improve upon [Bakaev, Brunck, Hertrich, Stade, Yehudayoff, STOC'26], who proved analogous logarithmic bounds with base three.

Abstract

ReLU Neural Networks

Explore similar work

Shallower ReLU Network Representations via Exact Linear Algebra

Representing MAX functions using two-hidden-layer ReLU networks

A Hand-Checkable Proof That Two Hidden ReLU Layers Compute the Maximum of Six Numbers