The Complexity of Batched ReLU Network Evaluation

We ask whether a batch of inputs to a fixed rectified-linear network can be evaluated asymptotically faster than by a separate forward pass on each input. One input through $L$ layers of width $d$ costs $\Theta (L{d}^2)$, and the textbook batch is $B$ such passes; ordinary batching improves locality, not this count. The rectifier is free, being linear in its own size, so the cost lies entirely in the affine maps and in which linear region each input falls. Separating evaluation into a geometric part and an algebraic part, we show the algebra amortizes: given the region labels, a batch confined to few regions costs a factor $\Theta (\min (L,d))$ less than pointwise, the cap being the price of reading the labels. Batched evaluation therefore reduces to batched point location, and the converse fails, so location is strictly the harder half. We chart when it is cheap. Under crossing and margin density assumptions, a concentrated batch occupies few regions through a random network, and a single distance comparison certifies a point's region. For arbitrary weights, exact evaluation has matching matrix-multiplication reductions and upper bounds. For approximation the obstacle is the network's conditioning rather than any flipped sign.