On Minimum Depth and Width of Floating-Point Neural Networks for Representing Floating-Point Functions

SAI paper + code review · Referee report

Summary

This paper asks how deep and how wide a ReLU network with IEEE-754 floating-point parameters, activations, and internal arithmetic must be in order to exactly represent every function from $\mathbb{F}^d$ to $\mathbb{F}$ . The conceptual move — identity, not approximation, inside a finite non-injective arithmetic — sharpens a distinction that classical universal-approximation and memorization results elide, since those results assume affine transformations of the domain are lossless. Under FP arithmetic they are not (nontrivial addition is not injective; overflow can occur), and the authors turn this into a set of tight, or near-tight, separations from the exact-arithmetic literature.

The headline results: (i) the minimum depth for $\mathbb{F}^d\to\mathbb{F}$ is exactly three — three layers suffice (Theorem 1) and, under a side condition on $(p,q)$ , two layers are insufficient (Theorem 2) — strictly above the classical value of two; (ii) the minimum width lies in $[2d, 2d+4]$ (Theorems 5, 6), strictly above the classical $d+1$ ; (iii) restricting the domain or codomain contracts both bounds (Theorems 3, 4, 7, 8), and on the two-point domain $\{0,\omega\}$ the width can drop below $d$ to $\lceil d/(p+1)\rceil + 4$ by lossless bit-packing (Theorem 9). Constructions are explicit — indicator functions from a two-layer sub-network (Lemma 10), aggregated by the " $\omega\oplus\beta_1\oplus(-\beta_1)\oplus\dots=1$ " identity (Lemma 11) — and the proofs are self-contained and complete on a close read of the appendices.

Overall the contribution is well-motivated and technically careful. The most substantive concerns are (i) explicit mis-attribution of which practical FP formats satisfy the side conditions — half-precision does not satisfy the hypotheses of Theorems 2, 6, or 8, though the paper repeatedly says it does — (ii) a persistent constant-4 gap between matched upper and lower bounds that is not analyzed, (iii) constructions of size $\Theta(|\mathbb{F}|^d)$ , so the "understanding real implementations" framing needs qualifying, and (iv) restriction to ReLU. Even so, the separation from the exact-arithmetic literature is real and cleanly proved.

Strengths

Conceptual contribution. The paper isolates a clean distinction — exact representation of finite-valued functions under FP arithmetic vs classical universal-approximation of continuous functions — and shows that classical minima do not transfer. This complements Park et al. (2024), Hwang et al. (2025a,b) in a natural way and closes their depth bound from $\le 4$ down to $3$ .
Matched upper/lower bounds. For every setting (Theorems 1/2, 5/6, 7/8) the paper gives both an achievability construction and an unfeasibility argument, with the gap only in constant additive terms. This is unusually thorough for an expressivity paper.
Sensitivity to domain and codomain. Theorems 3, 4, 7, 9 make precise how shrinking either the domain or the codomain lowers the required depth or width — a phenomenon that has no counterpart under exact arithmetic (where affine rescalings are free) and that is genuinely surprising.
Explicit and verifiable proofs. The two-layer indicator (Lemma 10), the exact-1 aggregation trick using $\omega\oplus\beta\oplus(-\beta)$ (Lemma 11 / Lemma 27), and the deep-and-narrow state-vector construction (Section 4.2, Figure 1) are all written out with enough detail to be checkable step by step; the veritas assessment of each theorem is "supported, low risk".
Clear alignment with prior expressivity literature. Table 1 and Sections 3.1–3.2 place each new bound directly against the closest exact-arithmetic result, making the size of each separation immediate.

Weaknesses

Half-precision does not satisfy the hypotheses of Theorems 2, 6, or 8. Table 2 gives $(p,q)=(10,5)$ for IEEE half, so $2^{q-1}-7=9<10=p$ (Theorem 2's hypothesis fails) and $e^* = (e_{\max}+2p+9)/2 = 22 > 16 = e_{\max}+1$ (Theorems 6 and 8's hypothesis fails). Yet Sections 3.1 and 3.2 repeatedly list half-precision as a format that satisfies these conditions. Since fp16 is arguably the most-cited low-precision ML format, the practical scope of the lower bounds is materially overstated.
E4M3 is silently excluded. For E4M3 all three hypotheses fail as well, and the paper mentions this only by omission. Because E4M3 is included under `Condition 1' in Preliminaries but excluded from every lower bound, a reader is likely to assume more coverage than is actually proved.
Persistent constant-4 gap. Every matched pair (2d vs 2d+4; d vs d+4) has the same +4 slack coming from the two "intermediate" plus two "output" state-vector slots. The paper does not discuss whether this slack is fundamental or an artifact of the deep-and-narrow bookkeeping. Given that expressivity papers usually push for tight constants, this is a real weakness.
Construction size is $\Theta(|\mathbb{F}|^d)$ . The proof of Theorem 1 sums $|\mathbb{F}|^d$ indicator terms; Theorem 7 propagates $\hat m = |[0,\infty)_{\mathbb{F}}^d|$ blocks. For fp16 vectors with $d=10$ this is already $\approx 2^{160}$ terms. The claim that the results "help to better understand real implementations of neural networks" therefore needs qualification — the theorems constrain existence, not efficiency.
Only ReLU. Hwang et al. (2025b) already extended the earlier depth- $\le 4$ result to general activations. The present paper does not comment on which of Theorems 1–9 plausibly extend to smooth/saturating activations, leaving the picture incomplete relative to that prior work.
`Condition 1' is never stated. Preliminaries invoke a global "Condition 1 on $p,q$ " (line 86) but no such condition is ever displayed. Combined with the per-theorem hypotheses, this leaves readers to reconstruct what is assumed globally.
Depth–width tradeoff unstudied. Theorem 1 achieves depth 3 with unbounded width; Theorem 7 achieves width $d+4$ at growing depth. Whether depth $3$ with width $O(d)$ (or any other joint bound) is achievable is not addressed.
Table 1 hides side conditions. The lower-bound rows for Theorems 2, 6, 8 do not mark the conditions on $(p,q)$ or $e^*$ ; a reader who reads only the table (as many will) will over-estimate the theorems' generality.
Motivational bit-count is misleading. The paragraph before Theorem 6 uses $|\mathbb{F}|^d \le |[0,\infty)_{\mathbb{F}}|^{2d-1}$ to motivate the width- $2d$ threshold, but this counting bound does not actually predict $2d$ ; the true lower bound is driven by round-off, not by counting. As written, the paragraph suggests otherwise.
Rounding-mode robustness not addressed. The overflow (Theorem 2) and round-off (Theorem 6) arguments rely on ties-to-even; the paper does not remark on whether they still go through under other IEEE-permitted rounding modes.
Table/theorem notation drift and rendering. Table 1's Theorem 4 row writes $[0,\Omega]_{\mathbb{F}}$ where Theorem 4 writes $[0,\infty)_{\mathbb{F}}$ (equal as sets, but stylistically inconsistent), and Table 1's Theorem 9 row parses as $\lceil d/(p+1)+4\rceil$ instead of $\lceil d/(p+1)\rceil + 4$ . Several display equations are also missing from the manuscript rendering (see Reproducibility & code).

Reproducibility & code

This is a theoretical paper with no released code or numerical artifact; "reproducibility" here means whether the proofs are complete and verifiable from the manuscript. The veritas assessment marks every claim (C1–C12) as supported with low reproducibility risk, which matches this reviewer's read of Sections 4.1–4.4 and Appendices B, C. The concerns below concern the manuscript's presentation and its correctness on external side conditions, not the proof scaffolding.

Format-side-condition arithmetic. As detailed in Weaknesses, the paper's per-format claims for Theorems 2, 6, 8 are incorrect for half-precision (and silently exclude E4M3). Because these claims are the only thing that connects the lower bounds to `real implementations', a reproducer who takes them at face value will draw stronger conclusions than the paper proves. This is a reproducibility issue at the level of scope claims, not of proof steps.
Missing display equations. Multiple display equations are missing in the rendered manuscript — the definition of $\mathbb{F}_{p,q}$ (after "set of finite floating-point numbers defined as"), the two-layer $h_i$ construction on p. 5, $g(x)_i$ 's definition, the $f_i$ recurrence in the Theorem 7 proof, and the final exponent inequality in Claim 15. A reproducer must guess what the intended formulas are. This is likely a compile-time artifact but must be fixed for the camera-ready.
Theorem 7's state-vector bookkeeping. The five-slot invariant $(x, \sigma(\cdot), \gamma_{i,j}, \alpha, \beta)$ that carries width $d+4$ across every affine layer is stated in prose rather than as a formal invariant. Given that this is the paper's most delicate construction, an explicit numbered invariant would substantially aid verification.
Claim 15 arithmetic elided. The final step of Theorem 2's proof (Claim 15) chains three inequalities via $p \le 2^{q-1}-7$ but the closing display is missing. The reader has to reconstruct the exponent arithmetic that produces $g_k(1)=\infty$ .
Global `Condition 1' undefined. Because Preliminaries defer Condition 1 to "Table 2 in Appendix", a reader cannot machine-check which of the six formats in Table 2 the paper's global assumptions cover, independent of the per-theorem side conditions.
No executable sanity check. Because the constructions rely on delicate FP identities (Lemma 11's $\omega\oplus\beta\oplus(-\beta)$ pattern, exponent thresholds in Theorems 6 and 8), a minimal enumerative check on a small format like E5M2 or E4M3 would raise confidence at low cost. None is provided or referenced.
Notational identifications relegated to parentheticals. The identification $[0,\omega]_{\mathbb{F}}=\{0,\omega\}$ — on which Theorem 9's bit-packing crucially depends — is a parenthetical `note that' rather than a labeled observation, making Theorem 9's headline number look more general than it is.

Recommended Changes

Essential (each addresses a specific concern above)

Fix the per-format applicability lists for Theorems 2, 6, 8. Delete half from the sentences in Sections 3.1 and 3.2 that list formats satisfying the hypotheses, and explicitly note that Theorems 2, 6, 8 do not apply to IEEE half-precision or FP8 E4M3 as-proved. Alternatively, supply a separate small- $p$ argument that covers fp16 and E4M3. (Weaknesses: half-precision applicability; E4M3.)
State Condition 1 explicitly. Add a numbered Condition 1' in Preliminaries with the exact inequality on $(p,q)$, and mark in Table 2 which rows satisfy it. (Weaknesses: Condition 1' never stated; Reproducibility & code: global condition undefined.)
Mark the per-theorem side conditions on Table 1. Add a symbol on the Theorem 2, 6, 8 rows referencing the $p\le 2^{q-1}-7$ / $e^* \le e_{\max}+1$ conditions and the list of formats to which they apply. (Weakness: Table 1 hides side conditions.)
Restore the missing display equations. In particular, fill in $\mathbb{F}_{p,q}$ 's definition, the $h_i$ construction on p. 5, $g(x)_i$ , the $f_i$ recurrence in Section 4.2, and the closing exponent inequality of Claim 15. (Reproducibility & code: missing display equations, Claim 15 arithmetic elided.)
Qualify the `real implementations' framing. Add a sentence to the Conclusion noting that the constructions are $\Theta(|\mathbb{F}|^d)$ in size, so the results constrain what is representable in principle, not what is efficiently representable. (Weakness: construction size.)

Suggested

Analyze the constant-4 gap. Include even a remark on whether the +4 slack in Theorems 5/6 and 7/8 is inherent, or whether some of the four auxiliary slots (intermediate values' + intermediate/final output') can be merged. Ideally strengthen either the upper bound to $2d+3$ or the lower bound to $2d+1$ . (Weakness: constant-4 gap.)
Add a state-vector invariant for Theorem 7. Write out the five-slot invariant $(x, \sigma(\hat w_{i,j}\otimes x_{\iota_j}\oplus\hat b_{i,j}), \gamma_{i,j}, \alpha_{i-1,x}, \beta_{i-1,x})$ as a labeled lemma before Section 4.2 and prove that each affine layer preserves it. (Reproducibility & code: Theorem 7 bookkeeping.)
Discuss the depth–width tradeoff. Add a paragraph, or a table row, stating what is (and is not) known about achieving depth 3 at width $O(d)$ or width $d+4$ at bounded depth. (Weakness: depth–width tradeoff unstudied.)
Comment on activation-function generality. Note which of Theorems 1–9 plausibly extend to smooth or saturating activations, and cite Hwang et al. (2025b) as the reference point. (Weakness: only ReLU.)
Discuss rounding-mode robustness. Add a remark on whether the overflow argument for Theorem 2 and the round-off argument for Theorem 6 depend on ties-to-even, or extend to round-toward-zero / round-to- $\pm\infty$ / ties-to-away. (Weakness: rounding-mode robustness.)
Reword the bit-counting motivation. Rewrite the paragraph before Theorem 6 so that it does not appear to derive the $2d$ threshold from counting reachable states — the actual argument is a round-off separation. (Weakness: motivational bit-count.)
Promote $[0,\omega]_{\mathbb{F}}=\{0,\omega\}$ to a labeled observation. State it as an explicit remark near Theorem 9 so that readers see the theorem is about Boolean-cube functions. (Reproducibility & code: notational identifications.)
Fix Table 1 notation drift. Reconcile $[0,\Omega]_{\mathbb{F}}$' with Theorem 4's $[0,\infty)_{\mathbb{F}}$ ' (a footnote defining $S_{\mathbb{F}} = S\cap\mathbb{F}$ would suffice), and move `+4' outside the ceiling in the Theorem 9 row. (Weakness: table/theorem notation drift.)
Provide an executable sanity check on a small format. A short enumeration script over $\mathbb{F}_{2,5}$ (or $\mathbb{F}_{3,4}$ ) that constructs the three-layer network of Theorem 1 for a random $f^*$ and verifies exact equality would strengthen confidence, especially given the FP-arithmetic-heavy proofs. (Reproducibility & code: no executable sanity check.)