Pith. sign in

REVIEW 4 major objections 5 minor 26 references

On the algorithmic construction of deep ReLU networks

T0 review · 4 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A ReLU network can be explicitly programmed to sort exactly and to approximate smooth functions with exponentially small error.

desk verdict A genuinely constructive ReLU toolbox with a real but fixable indexing bug in its central folding theorem. read the letter →

arxiv 2506.19104 v1 pith:TN7D5FA4 submitted 2025-06-23 cs.LG cs.NAmath.NA

Daan Huybrechs This is my paper · ORCID
classification cs.LGcs.NAmath.NA MSC 68T0741A3041A25
keywords ReLUnetworksalgorithmicconstructionexactsortingbitonicsortconditionalbranchingfoldingandunfoldingfunctionapproximationrecursivealgorithms
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that a feedforward ReLU network can be built by programming rather than training: from a description of an algorithm, one can write down exact weights that make the network carry it out. The headline examples are an exact sorting network for 16,384 inputs and recursive folding constructions that approximate $e^x$, $\cos x$, $\sin x$, monomials, and $xy$ with error that scales like $2^{-2L}$ in the number of levels. If the claim is right, neural networks can serve as transparent, analyzable algorithms whose approximation rates are proven rather than fitted. The paper's answer to what ReLU networks can represent is constructive: a class of continuous conditional branching can be compiled into explicit ReLU layers.

What carries the argument

The load-bearing object is the conditional-branching identity (20), which expresses the output of an if-then-else as a sum of ReLU terms: $z(x)=b(0)-\operatorname{ReLU}(\beta a(x)-\hat b(x))+\beta\operatorname{ReLU}(a(x))+\operatorname{ReLU}(-\gamma a(x)+\hat c(x))-\gamma\operatorname{ReLU}(-a(x))$, valid when $\hat b$ crosses $\beta a$ and $\hat c$ crosses $\gamma a$ at the critical point. It carries the argument because it converts algorithmic branching into fixed weights, so recursive algorithms (sorting, folding, unfolding) become explicit networks. Around it, the comparison element $\mathrm{minmax}(x,y)=A_1\operatorname{ReLU}(A_2x)$ and the folding/unfolding relations (9), (21) provide the concrete building blocks for sorting and function approximation.

What would settle it

Build the continuous if-then-else with $a(x)=x$, $b(x)=1+\sqrt{|x|}$, $c(x)=1-\sqrt{|x|}$, so both branches agree at $x=0$. On a dense grid near $0$, evaluate the right-hand side of (20) with any finite positive $\beta,\gamma$: for $x>0$ it returns $1+\beta x$ instead of $1+\sqrt{x}$, so the compiled network cannot represent the statement. For the paper's own networks, one can verify the displayed inequalities for $\beta_j,\gamma_j$ at every level $j$ on a fine grid; any violation would show up as an output error on some interval.

Watch

Extended reading notes

Core claim

The paper's central discovery is a compilation scheme: any continuous if-then-else statement of the form 'if $a(x)\ge 0$ then $b(x)$ else $c(x)$' can be realized exactly by a fixed linear combination of ReLU calls, as long as the normalized branch functions $\hat b,\hat c$ cross a fixed multiple of $a$ at the critical point (Assumption 2, identity (20)). This turns recursive algorithms into deep ReLU networks layer by layer. The same scheme gives an exact neural sorting network by wiring min and max comparison elements in a bitonic network, with depth $O(\log^2 N)$ and $O(N\log^2 N)$ nonzero parameters. For smooth univariate functions, folding operations $h_j(x)=2^{-j}-|x-2^{-j}|$ reduce the approximation to a tiny interval, and unfolding adds correction terms that are themselves ReLU-linear; the paper proves the resulting error is exactly $p_L(x)^2$ for $x^2$ and $O(2^{-2L})$ for the other examples. The networks are sparse, recursive, parallel at each layer, and fully transparent.

Load-bearing premise

The construction depends on a geometric crossing condition: at every branch point, each branch function must straddle a fixed multiple of the condition function, rather than merely touching or flattening there; if that condition fails on any level, equation (20) can deliver the wrong branch on some interval.

Editorial extensions

If this is right

  • Exact sorting with ReLU is possible: a network with depth $O(\log^2 N)$ and $O(N\log^2 N)$ nonzero parameters returns the sorted input exactly, not approximately.
  • The same conditional-branching compilation makes the paper's approximations provable: the error for $x^2$ is exactly $p_L(x)^2$ and the error for exp, cos, sin, monomials, and xy is bounded by $O(2^{-2L})$.
  • Because recursion depth equals network depth, increasing the number of levels improves accuracy and requires correspondingly deeper networks; deep networks outperform shallow ones in these constructions.
  • A single if-statement inside a recursive fold can generate exponentially many linear pieces, showing how compact algorithmic descriptions translate into high expressivity.
  • The constructed networks are sparse and fully transparent: every weight, bias, and layer has a known role in the underlying algorithm, so no training is needed.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper, the crossing constants $\beta,\gamma$ could in principle be learned from function samples instead of derived analytically, which would turn the compilation scheme into a practical tool for other algorithms.
  • The exact min/max comparison elements could serve as fixed, understood building blocks for rank-based operations in larger networks, since they are continuous and piecewise linear.
  • Any univariate function with a known shift identity should admit a similar folding/unfolding construction; testing functions such as $\log(1+x)$ or special functions would map the real boundary of the method.
  • Because all examples here are sparse, the paper does not explain dense deep networks; the algorithmic view suggests dense networks must couple quantities across many scales, which is left open.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper develops a constructive, algorithmic view of deep ReLU networks. It first builds an exact sorting network by wiring comparison elements according to the bitonic-sort schedule, with min/max implemented by two ReLU layers. It then introduces a geometric folding/unfolding scheme on graded dyadic meshes to approximate x^2 with error O(2^{-2L}), and proposes a general framework for compiling conditional expressions into ReLU networks under a crossing assumption (Assumption 2). The framework is applied to exponentials, trigonometric functions, monomials, and multiplication, with claimed convergence O(2^{-2L}) and with explicit constants and Julia code supplied.

Significance. If the formal statements are corrected, the paper is a valuable contribution to constructive expressivity results for ReLU networks. Its strengths include the explicit, deterministic bitonic-sort construction with exact sorting; the transparent derivation of all weights; the reproducible Julia package; and the demonstration that conditional branching can be compiled into continuous ReLU networks. The paper also honestly attributes prior results, notably Telgarsky's x^2 construction, and extends it to several new function families. The main value is pedagogical and methodological: it shows concretely what can be programmed into a ReLU network and gives explicit error rates. However, the manuscript as written contains indexing and sign errors in central equations, so the formal justification of the claimed rates is not yet reliable.

major comments (4)
  1. [Section 3.2, Eq. (10) and Theorem 3.1] The definition of f_L in Eq. (10) is misindexed. With p_j(x) defined as the value after j folds, p_j(x) lies in [0,2^{-j}], so eta_j(p_j(x)) is evaluated on the wrong interval; for L=1 one gets eta_1(h_1(x)) = 0 on [0,1], and Theorem 3.1 is false as stated. The correct unfolding is f_L(x) = sum_{j=1}^L eta_j(p_{j-1}(x)) with p_0(x)=x, and the identity should read x^2 = p_L(x)^2 + sum_{j=1}^L eta_j(p_{j-1}(x)). This is load-bearing because the later exponential, trigonometric, monomial, and multiplication constructions all rely on the same unfolding mechanism, and the formal proof of their O(2^{-2L}) rates inherits the defect. The algorithms themselves appear to implement the correct recurrence; the theorem statement and proof need to be fixed.
  2. [Section 4.3, Eq. (20)] Equation (20) uses b(0) as the additive constant, but the general critical point is x*, not 0. The correct formula should have b(x*) in place of b(0); otherwise, for x > x*, the expression evaluates to b(x) only if b(0)=b(x*), which is not assumed. This is not a cosmetic issue: in the examples in Section 5, b(x*) = e^{s_j} or similar, which is not b(0). The derivation above (20) and the definitions of \hat b and \hat c clearly use b(x*), so Eq. (20) appears to contain a typo, but it must be corrected before the compilation formula is usable.
  3. [Section 4.2, Eq. (17)] The sign convention stated for Eq. (17) is incorrect. The formula z(x)=b(0)+ReLU(b(x)-b(0))+ReLU(c(x)-c(0)) implements the conditional only when \hat b(x) is nonnegative for x >= 0 and \hat c(x) is nonnegative for x <= 0 (or the symmetric case), not when both functions are 'positive for x >= 0'. As written, the assertion that (17) is equivalent to the if-then-else statement is false. This is a special-case precursor to the general compilation formula, so the error should be fixed by stating the correct sign conditions.
  4. [Sections 5.1-5.3, Assumption 2 verification] The paper asserts that the constants beta and gamma stated in Sections 5.1-5.3 satisfy Assumption 2, but it does not give a complete proof for all levels j. The figures and the phrase 'by direct computation' are not a substitute for an inequality argument, especially because a failure of the crossing condition at any level would make the compiled network select the wrong branch on some interval. Please add a short lemma, for example using convexity or monotonicity of the relevant functions, verifying that the stated beta and gamma give the required sign pattern for every j. The constants appear plausible and the numerics are consistent, but the formal claim requires proof.
minor comments (5)
  1. [Section 2.2] The text contains a typo: 'how bitcoin sort operates' should be 'how bitonic sort operates'.
  2. [Section 3.1] The name 'Telgarsy' should be 'Telgarsky'.
  3. [Section 3.4, Eq. (11)] The first trigonometric identity has a typo: 'sin b' should be 'sin x'.
  4. [Section 4.3, after Eq. (18)] The expression for \tilde c(x) is written with beta in the text preceding Eq. (20), but Eq. (20) and the subsequent discussion use gamma. These should be made consistent.
  5. [Section 5.4] The text refers to 'Algorithm 11' when it means 'Algorithm 7', and 'approxiation' should be 'approximation'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the constructions are explicit, the constants are analytically derived, and no load-bearing premise rests on self-citation.

full rationale

The derivation chain is not circular. The sorting construction transcribes the classical bitonic sorting network into the explicit min/max ReLU identities, so the sorting property is imported from an external algorithm rather than assumed in the weights. The x^2 construction is explicitly attributed to Telgarsky/Yarotsky, and the paper's own folding correction eta_j follows from the exact identity (8), not from the approximation being claimed. In Section 5, the constants beta and gamma entering (20) are computed analytically from the target functions and the shift identities (11)-(13), and the base intervals are approximated by Taylor or interpolating linear functions; these are standard constructive-analysis choices, not fitted parameters renamed as predictions. No load-bearing assumption is supported only by a self-citation: the author cites no prior work of his own, and the external references (bitonic sort, Telgarsky's x^2, Yarotsky's multiplication scheme) are independently checkable. The manuscript's real weaknesses are correctness gaps, most visibly the indexing in Eq. (10), where eta_j is evaluated at p_j instead of p_{j-1}, and the incomplete verification of the crossing inequalities in Assumption 2; these are not circular reductions, since Eq. (10) is not defined in terms of the error bound it asserts and the crossing constants are not fitted to the claimed rates. Accordingly, circularity score is 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central constructions use standard ReLU identities and two external results: correctness of bitonic sort and Telgarsky's x^2 approximation (the latter is re-derived). The paper's own conditional-branching theorem is explicitly conditional on Assumption 2, which is stated and verified for each example. No free parameters are fitted to data: constants such as β and γ are computed analytically from the target functions. No new entities are postulated.

assumptions (3)
  • domain assumption Bitonic sort correctly sorts any input vector of length N=2^L.
    Used in §2.2-2.3 to conclude the constructed network sorts exactly; correctness is cited to Batcher [1] and Knuth [10], not proved in the paper.
  • domain assumption For each conditional compilation, there exist constants β,γ > 0 such that the normalized branch functions cross βa and γa at the critical point.
    Stated as Assumption 2 in §4.3; the entire compilation formula (20) rests on it. The paper argues it is generic for Lipschitz functions on bounded intervals, and verifies it graphically for the examples.
  • domain assumption The condition function a changes sign exactly once on the interval [x0,x1].
    Assumed in §4.1 to reduce the continuity condition to b(x*)=c(x*); isolated critical values are handled by subdivision.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the algorithmic construction of deep ReLU networks." pith.science (2026). https://pith.science/paper/TN7D5FA4

@misc{pith2026250619104,
  author       = {Pith},
  title        = {Pith review of: On the algorithmic construction of deep ReLU networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TN7D5FA4}},
  note         = {Machine review of arXiv:2506.19104}
}
read the original abstract

It is difficult to describe in mathematical terms what a neural network trained on data represents. On the other hand, there is a growing mathematical understanding of what neural networks are in principle capable of representing. Feedforward neural networks using the ReLU activation function represent continuous and piecewise linear functions and can approximate many others. The study of their expressivity addresses the question: which ones? Contributing to the available answers, we take the perspective of a neural network as an algorithm. In this analogy, a neural network is programmed constructively, rather than trained from data. An interesting example is a sorting algorithm: we explicitly construct a neural network that sorts its inputs exactly, not approximately, and that, in a sense, has optimal computational complexity if the input dimension is large. Such constructed networks may have several billion parameters. We construct and analyze several other examples, both existing and new. We find that, in these examples, neural networks as algorithms are typically recursive and parallel. Compared to conventional algorithms, ReLU networks are restricted by having to be continuous. Moreover, the depth of recursion is limited by the depth of the network, with deep networks having superior properties over shallow ones.

Figures

Figures reproduced from arXiv: 2506.19104 by the authors.

Figure 1
Figure 1. The min and max functions are continuous and piecewise linear functions of [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Structure of the bitonic network (image from [ [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Illustration of the repeated foldings. First, the point [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: Approximation error of Algorithm 3. Left: maximum error on [0, 1] as a function of the level L, using initialization by zero or following Remark 3.2. Right: pointwise error on [0, 1] for different values of L. The solid black lines show the error bound 2−2L. The point …
Figure 5
Figure 5. Figure 5: Illustration of two crossing functions following Definition [PITH_FULL_IMAGE:figures/full_fig_p015_5.png]
Figure 6
Figure 6. Figure 6: Illustration of the quantities in the conditional expression for Algorithm [PITH_FULL_IMAGE:figures/full_fig_p017_6.png]
Figure 7
Figure 7. Figure 7: Approximation error of Algorithm 4. Left: maximum error on [0, 1] for increasing L for the functions e x and e −x using Taylor series initialization (solid) or interpolation (dashed). Right: pointwise error on [0, 1] for different values of L. The solid black lines sho…
Figure 8
Figure 8. Figure 8: This figure is the analogue of Fig [PITH_FULL_IMAGE:figures/full_fig_p019_8.png]
Figure 9
Figure 9. Figure 9: Approximation error of Algorithm 5. Left: maximum error on [0, π] for increasing L for the functions cos(x) and sin(x) using Taylor series initialization (solid) or interpolation (dashed). Right: pointwise error on [0, π] for different values of L for cos(x) (solid) an…
Figure 10
Figure 10. Figure 10: Approximation error of Algorithm 6 for the computation of monomials up to degree d = 10. Left: maximum error on [0, 1] for increasing L and for a few degrees. Right: pointwise error on [0, 1] for different values of L for f(x) = x 10 . Note that βk is precisely the de…
Figure 11
Figure 11. Figure 11: Illustration of the approximation to f(x, y) = xy by Algorithm 7. Some results are shown in [PITH_FULL_IMAGE:figures/full_fig_p021_11.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 23 canonical work pages

  1. [1]

    K. E. Batcher. Sorting networks and their applications. InProceedings of the April 30–May 2, 1968, spring joint computer conference, pages 307–314, 1968

    work page 1968

  2. [2]

    Boull´ e, Y

    N. Boull´ e, Y. Nakatsukasa, and A. Townsend. Rational neural networks.Advances in neural information processing systems, 33:14243–14253, 2020

    work page 2020

  3. [3]

    G. Cybenko. Approximation by superpositions of a sigmoidal function.Math. Control Signals Syst (MCSS), 2:303—-314, 1989

    work page 1989

  4. [4]

    Daubechies, R

    I. Daubechies, R. DeVore, N. Dym, S. Faigenbaum-Golovin, S. Z. Kovalsky, K.-C. Lin, J. Park, G. Petrova, and B. Sober. Neural network approximation of refinable functions.IEEE Transac- tions on Information Theory, 69(1):482–495, 2022

    work page 2022

  5. [5]

    Daubechies, R

    I. Daubechies, R. DeVore, S. Foucart, B. Hanin, and G. Petrova. Nonlinear approximation and (deep) ReLU networks.Constr. Appr., 55:127–172, 2022

    work page 2022

  6. [6]

    Davis and M

    O. Davis and M. Motamed. Approximation power of deep neural networks: an explanatory mathematical survey. Technical Report arXiv:2207.09511, 2024

    arXiv 2024

  7. [7]

    DeVore, B

    R. DeVore, B. Hanin, and G. Petrova. Neural network approximation.Acta Numerica, 30:327–444, 2021

    2021

  8. [8]

    G¨ uhring, M

    I. G¨ uhring, M. Raslan, and G. Kutyniok. Expressivity of deep neural networks. In P. Grohs and G. Kutyniok, editors,Mathematical Aspects of Deep Learning. Cambridge University Press, Cambridge, 2022

    work page 2022

Show all 26 references
  1. [9]

    Hornik, M

    K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks are universal ap- proximators.Neural Netw., 2:359—-366, 1989

    1989

  2. [10]

    D. E. Knuth.The art of computer programming, volume 3: (2nd ed.) sorting and searching. Addison Wesley Longman Publishing Co., Inc., USA, 1998

    1998

  3. [11]

    Marcati, J

    C. Marcati, J. A. A. Opschoor, P. C. Petersen, and C. Schwab. Exponential ReLU neural network approximation rates for point and edge singularities.Found. Comp. Math., 2024. to appear

    2024

  4. [12]

    McCane and L

    B. McCane and L. Szymanski. Efficiency of deep networks for radially symmetric functions. Neurocomputing, 313:119–124, 2018

    2018

  5. [13]

    Mhaskar and R

    H. Mhaskar and R. O’Dowd. Learning on manifolds without manifold learning. Technical Report arXiv:2402.12687, 2024

    2024 arXiv

  6. [14]

    H. N. Mhaskar. Approximation properties of a multilayered feedforward artificial neural network. Adv Comput Math, 1:61–80, 1993

    1993

  7. [15]

    H. N. Mhaskar and T. Poggio. Function approximation by deep networks.Communications on Pure and Applied Analysis, 19(8):4085–4095, 2020. 23

    2020

  8. [16]

    J. A. A. Opschoor, P. C. Petersen, and C. Schwab. Deep ReLU networks and high-order finite element methods.Analysis and Applications, 18:715–770, 2019

    2019

  9. [17]

    J. A. A. Opschoor and C. Schwab. Exponential expressivity of ReLU k neural networks on gevrey classes with point singularities. Technical Report arXiv:2403.02035, 2024

    2024 arXiv

  10. [18]

    Petersen, C

    F. Petersen, C. Borgelt, H. Kuehne, and O. Deussen. Differentiable sorting networks for scalable sorting and ranking supervision. InInternational conference on machine learning, pages 8546–

  11. [19]

    Petersen and F

    P. Petersen and F. Voigtlander. Optimal approximation of piecewise smooth functions using deep ReLU neural networks.Neural Networks, 108:296–330, 2018

    2018

  12. [20]

    Petersen and J

    P. Petersen and J. Zech. Mathematical theory of deep learning, 2024

    2024

  13. [21]

    Schneider and J

    C. Schneider and J. Vyb´ ıral. A multivariate Riesz basis of ReLU neural networks.Appl. Comput. Harm. Anal., 68:101605, 2024

    2024

  14. [22]

    S. H. T. and E. D. Sontag. On the computational power of neural nets.J. Comput. Syst. Sci., 50(1):132–150, 1995

    1995

  15. [23]

    Telgarsky

    M. Telgarsky. Representation benefits of deep feedforward networks. Technical Report arXiv:1509.08101, 2015

    2015 arXiv

  16. [24]

    Telgarsky

    M. Telgarsky. Neural networks and rational functions. InInternational Conference on Machine Learning, pages 3387–3393, 2017

    2017

  17. [25]

    Bitonic sorter — wikipedia, the free encyclopedia, 2024

    Wikipedia contributors. Bitonic sorter — wikipedia, the free encyclopedia, 2024. Accessed: 2025- 04-13

    2024

  18. [26]

    Yarotsky

    D. Yarotsky. Error bounds for approximations with deep ReLU networks.Neural Networks, 94:103–114, 2017. 24

    2017

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.