acceptodds
Under review as a conference paper at ICLR 2027

The Complexity of Batched ReLU Network Evaluation

Abstract

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 layers of width costs , and the textbook batch is 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 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.

Primary area:
foundation or frontier models, including LLMs
Keywords:
ReLU networks, batched evaluation, linear regions, point location, matrix multiplication, fine-grained complexity, sketching, approximate matrix multiplication, average-case analysis

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_uxCxOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies the computational complexity of evaluating a ReLU neural network. Let L, d, and B denote the number of layers, the uniform width, and the input batch size, respectively. Evaluating this network requires O(BLd^2) operations when each input is processed independently. This paper aims to reduce this computational complexity by exploiting the structure of the ReLU activation function. It proposes a method that separates the evaluation problem into two components: (1) identifying the activation region containing each input and (2) applying the corresponding affine transformation. The paper derives upper bounds on the computational complexity of the proposed method.

Critical strengths

Computational complexity improvement: The paper shows that the affine transformations associated with the ReLU activation function can be reused across input batches when the inputs belong to a small number of activation regions. In this case, the evaluation cost can be reduced by a factor of Θ(min⁡L,d)\Theta(\min{L,d}) when the activation patterns are known. This result quantitatively characterizes the computational benefits of shared activation patterns.

Identifying the main computational bottleneck: The paper separates the hardness of identifying activation regions and that of applying affine transformations. It shows that when the activation regions of the inputs are known, one can reuse affine transformations across inputs. However, determining the activation region of each input could be computationally expensive. This identifies detecting the activation regions as the key challenge in coming up with a faster evaluation.

Critical weaknesses

Restrictive assumptions for computational improvements: In Theorem 3.1, the speedup of Θ(min⁡{L,d})\Theta(\min\{L,d\}) can be achieved when the activation patterns are known and the batch size is sufficiently large (B≥RLdB\geq RLd). However, identifying these activation patterns can itself be a computationally expensive task. Even though the paper proposes a certificate-based approach to resolve this issue, its guarantees may require an exponentially large batch size with respect to the input dimension. Hence, the theorem’s practical applicability is limited.

Lack of experimental validation: The paper does not evaluate its proposed method in experiments to investigate the claimed speedup in real applications. It is not clear that the proposed method can outperform the standard evaluation methods already existing in realistic applications.

Questions for authors

Theoretical novelty: In Theorem 3.1, can the authors explain the new technique exploited in it beyond the known piecewise-affine structure of the ReLU activation function when activation patterns are known?

Reviewer_k7CoOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper asks 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. The geometric part decides, for each input, which region it belongs to. The algebraic part applies the affine map of that region to the input.

  1. Suppose the BB inputs of a batch occupy RR distinct linear regions and their region labels are given. In the uniform-width case, whenever B≥RLdB \ge RLd, the evaluation cost is O(Bdmax⁡(d,L))O(Bd\max(d,L)), a factor of Θ(min⁡(L,d))\Theta(\min(L,d)) below the pointwise cost Θ(BLd2)\Theta(BLd^2).

  2. 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. A point within the distance-to-nearest-boundary of an evaluated point shares its region and is evaluated by the same affine map. Caching this certificate and recomputing a label only when it fails gives an expected evaluation cost of O(Bd0d)O(Bd_0d) under the stated batch-size condition.

  3. A batched forward pass is a sequence of dense matrix products interleaved with the rectifier, so fast matrix multiplication applies layer by layer. Conversely, any batched-evaluation algorithm that reads the weights yields a matrix-multiplication algorithm of the same cost. The lower bound is one product and the upper bound is LL of them.

  4. Sketching each layer’s product and applying exact rectifiers evaluates a batch of B≥dB\ge d inputs to relative Frobenius error ϵ\epsilon with probability at least 1−δ1-\delta. The cost is governed by the network’s forward condition number and stable-rank profile. Applying exact rectifiers to approximate pre-activations propagates error through the network by the layer operator norms alone, and the discrete activation pattern is never needed.

Critical strengths
  1. The average-case analysis is technically careful and well supported. It handles the dependence between anchors and certificate failures and verifies bounded margin density for concrete Gaussian network models, giving a convincing justification for the claimed speedup.
Critical weaknesses
  1. The approximate-evaluation results have limited novelty beyond standard low-rank approximation. Theorem C.4 combines standard approximate matrix multiplication with ReLU’s 1-Lipschitz property. The observation that approximation does not require preserving activation patterns follows from this established stability argument. Moreover, truncating each layer to rank rr gives relative batch error at most κ/r+1\kappa/\sqrt{r+1}, yielding the same O(κ2/ε2)O(\kappa^2/\varepsilon^2) rank dependence without assuming geometrically decaying singular values. Proposition C.9 considers truncation only under that stronger assumption. Sketching can reduce preprocessing costs, but the paper does not establish how this saving compares with the rank and evaluation cost of general SVD truncation at the same output error. This leaves the computational advantage of the proposed approximation method insufficiently established.

  2. The certificate speedup has a restrictive proven regime, and its relevance to the proposed applications remains unestablished. Corollary A.17 requires B=Ω(L3d3ρmΛ+Ld)B=\Omega(L^3d^3\rho_m\Lambda+Ld), where Λ\Lambda is the total length of the input order. For points spread through a fixed-radius ball, the sufficient batch-size threshold after spatial ordering grows exponentially with the input dimension (lines 1313–1318). The explicit margin guarantees concern random networks, while the discussion proposes applications such as sensitivity analysis, finite differencing, and attribution. The paper provides no evidence that these workloads on trained networks permit enough reuse to recover the cost of constructing the certificates and affine maps. This leaves the computational value of its main new method unclear beyond the restricted settings covered by the theory.

Questions for authors
  1. Can you test certificate-cached evaluation on a trained ReLU network using one of the proposed local workloads, reporting total runtime against standard batched evaluation, including ordering, certificate construction, and recomputation costs?

  2. When is sketching faster than truncated-SVD evaluation at the same output error, including preprocessing costs?

I am very open to raising score!

Reviewer_vaNfOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies when a batch of inputs to a fixed ReLU network can be asymptotically faster than separate forward passes. It central idea is to separate evaluation into a geometric part (identifying each input's activation region) and an algebraic part (applying the affine map shared by that region). Its main contributions are:

  • Regional amortization: Given region labels, the paper shows that the algebraic part can be shared across inputs confined to few regions. For sufficiently large batches, this gives a factor of Θ(min(L,d)) savings over pointwise.
  • Cheap region certification: For random networks under boundary-crossing and margin density assumptions, a certificate avoids explicit point location and enables asymptotic speedups.

The introduction also outlines other contributions, but they are deferred to the appendices. Validation is entirely analytical without any empirical results. Thus, the practical benefits of the method remain untested.

Critical strengths
  • The paper provides a useful cost analysis. Theorem 3.1 explains the cost of grouping activation patterns, constructing shared affine maps, and applying them to a batch. It identifies the conditions where reuse reduces computation compared to separate forward passes. This turns a property of ReLU networks into a concrete speedup guarantee.
Critical weaknesses
  • Lack of empirical results and concrete comparisons against existing methods. The paper needs to show when its caching approach is beneficial over related methods such as EXACTLINE [1] and SplineCam [2]. Its guarantees also rely on random network and margin assumptions. However, reuse requires inputs to be sufficiently close together, and that becomes harder to achieve as points spread across many dimensions, i.e., the required batch size could grow exponentially with input dimension. Without experiments and more concrete cost analysis, it remains unclear whether the method provides realistic benefits.

  • The paper organization makes their contribution unnecessarily difficult to access. The introduction occupies five pages, while the central algorithm and analysis appear in the appendix, when they should be self-contained and complete in the main text. Substantial reorganization of the paper is necessary.

[1] Matthew Sotoudeh and Aditya V. Thakur. Computing linear restrictions of neural networks. NeurIPS 2019.

[2] Ahmed Imtiaz Humayun, Randall Balestriero, Guha Balakrishnan, and Richard G. Baraniuk. SplineCam: Exact visualization and characterization of deep network geometry and decision boundaries. CVPR 2023.

Questions for authors
  • Scope of the main claim: The introduction states that the algebraic part is cheap and amortizable. However, Section 3.1 shows a setting where applying the regional map is more expensive than a forward pass. Under precisely which architectural and batch-size conditions does the method hold?
  • Evidence for practical savings: How does this compare with EXACTLINE or SplineCam? Also, could you provide a concrete experiment result where the total cost of the certificate-based method (including constructing maps and certificates) is lower than a conventional batched evaluation?
  • Completeness of the main text: The introduction outlines several contributions, but the actual algorithm and speedup analysis are in the appendix. Which results contribute to the central contribution, and can they be self-contained in the main text (p1-9)?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.