{"id":"f96fb537-5966-4723-a94c-a9d6bd7bd2e4","arxiv_id":"2505.18023","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Discrete-time LIF spiking networks realize piecewise constant functions on polyhedral regions, and each first-layer neuron generates only O(T^2) parallel hyperplanes over T time steps, not exponentially many.","lead":"This paper analyzes discrete-time spiking neural networks, a widely used energy-efficient alternative to standard neural networks, and shows that each neuron partitions the input space using at most roughly T^2 regions, where T is the number of time steps. It also proves universal approximation for continuous functions and argues that latency matters more than depth for input-space partitioning.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Tightness of Theorem 4.3 hinges on Lemma B.13's general-position construction, whose proof skips verifying that the translated hyperplane families keep all spike-history-dependent shifts distinct and active; an explicit small-case arrangement would settle it.","rationale":"The reader's weakest assumption correctly identifies the most load-bearing soft spot: Theorem 4.3 is called tight, and tightness requires Lemma B.13 to produce simultaneously well-separated, active, general-position hyperplane families. The upper bound direction of Theorem 4.3 is solid because Lemma 4.2's per-neuron quadratic bound is carefully proven and Lemma B.11 is a standard deletion-restriction count. The per-neuron tightness in Lemma B.12 is also convincing: the β=1 shifts are explicitly computed, the outermost-region conditions and the distinctness condition (14) are stated, and a generic irrational uk(0) satisfies them. What remains under-argued is the interaction between the per-neuron shift structure and the multi-neuron spatial construction in Lemma B.13. The proof's translation argument is plausible and likely repairable, but as written it does not rigorously rule out coincident shifts, inactive hyperplanes, or accidental multi-hyperplane concurrence; any of these would make the maximum smaller than claimed. This matches the reader's condition and does not require changing the verdict. I also note the separate algebraic error in Theorem 3.2 and Corollary B.8: the displayed formula places Γ in the denominator (diam∞/(εΓ)) instead of the numerator (diam∞·Γ/ε), which would invert the dependence on the Lipschitz constant. That is a genuine correctness issue for the approximation-rate result, but it is not part of the partitioning claim that is the strongest claim; it reinforces the CONDITIONAL verdict without altering it. Overall, no objection to the upper-bound results or to the qualitative latency-versus-depth contrast is identified.","tokens_in":38548,"tokens_out":39620,"duration_ms":401411,"concrete_test":"Verify Lemma B.13 in the smallest nontrivial case: nin=2, n1=3, T=3. Choose β=1, ϑ=1, and uk(0) as three distinct irrational values in (0,1), e.g., √2/10, √3/10, √5/10. Pick W as a 3×2 matrix with rows in general position, then choose b following the translation construction in Lemma B.13 so that all intersections of earlier families lie on one side of every shifted copy of the new family. Enumerate the exact hyperplane arrangement of the resulting 3·6=18 lines in R^2, compute its cells, and record the first-layer spike pattern for each cell. Check two things: (1) the number of distinct activation patterns equals the Theorem 4.3 bound 1 + 6·3 + 36·3 = 127; (2) each of the 18 lines separates two cells with different spike patterns for its own neuron, so every hyperplane is active.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central partitioning claim has two parts: the per-neuron quadratic bound (Lemma 4.2) and the multi-neuron tight upper bound (Theorem 4.3). The per-neuron bound is convincingly proved: the lexicographic-ordering argument in Lemma B.12 correctly shows at most one new region per Hamming weight per time step, and the β=1 construction with generic uk(0) attains it. The weak point is the tightness of the multi-neuron bound, which depends entirely on Lemma B.13. There one must choose first-layer weights and biases so that the active parallel hyperplanes of all n1 neurons form families in general position, with each family containing exactly k = (T^2+T)/2 distinct hyperplanes. The proof translates each new family far from all prior intersection points, using boundedness of the spike-history shifts. What it does not explicitly verify is: (i) after this translation, every neuron's active hyperplanes still lie inside their own parent slabs, so the per-neuron splitting condition from Lemma B.12 is preserved; (ii) the shift values for each neuron are pairwise distinct across all time steps and across neurons, so the family size is exactly k rather than smaller; and (iii) no degeneracy is created where a hyperplane from the new family passes through an intersection of hyperplanes from three or more previous families, which would violate general position for n1 > nin. These conditions are not algebraic conveniences: if any one fails, the number of activation regions drops strictly below the formula in Theorem 4.3 and the claimed tight Θ(T^2) scaling for the maximum partition is not established. The upper bound itself is unaffected, so the concern is specifically about the 'tight' claim, not about whether a single neuron can achieve quadratic growth.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the expressivity of discrete-time LIF spiking neural networks with static inputs, direct encoding, and membrane-potential decoding. The main theoretical claims are: (1) every continuous function on a compact set can be uniformly approximated by a network with T=1 time step and L=2 hidden layers, with explicit width bounds for Lipschitz functions (Theorem 3.2) and a matching lower bound for f(x)=Γx on [0,1] (Proposition 3.3); (2) the first hidden layer partitions the input space into polyhedral regions, and although a naive count allows 2^T regions per neuron, a single neuron creates at most (T^2+T+2)/2 regions (Lemma 4.2), leading to the upper bound in Theorem 4.3 on activation and constant regions in terms of nin, n1, and T; (3) the bound is claimed to be tight under a general-position condition for families of parallel hyperplanes (Lemma B.13); (4) depth does not increase the number of activation regions, in contrast to ReLU ANNs, and this is supported by experiments on CIFAR10 and SVHN and by a toy region-counting experiment. The paper also discusses how the leaky parameter β affects the shift of parallel hyperplanes.","tokens_in":38821,"tokens_out":24493,"duration_ms":252697,"significance":"The paper addresses a timely and under-theorized model class: discrete-time LIF-SNNs, which are the standard SNN implementation framework but are much less analyzed than continuous-time spike-response models. If the results are correct after revision, the main contributions are the explicit width bounds for universal approximation with T=1, the per-neuron O(T^2) region bound in Lemma 4.2/B.12, and the sharp contrast with ReLU ANNs: latency plays a role analogous to width for the first hidden layer, while depth does not increase the number of activation regions. The proofs are largely self-contained and constructive: the identity construction, the step-function realization, and the lexicographic-region argument for the quadratic bound are genuine strengths, as is the use of families of parallel hyperplanes rather than generic arrangements. The experiments illustrate the predicted bottleneck behavior, though they do not by themselves prove the theory. However, the approximation-rate formula in the main theorem and the proof of tightness in Lemma B.13 need correction before the claimed rates can be relied upon.","major_comments":[{"comment":"The printed width formulas invert the Lipschitz constant. The proof in Corollary B.8 chooses δ = min{ε/Γ, 2K}, so m = ceil(2K/δ)^n = ceil(2KΓ/ε)^n, and hence n1 = (ceil(2KΓ/ε)+1)n and n2 = ceil(2KΓ/ε)^n. The formulas printed as ceil(2K/(εΓ)) have the reciprocal dependence: as Γ decreases (an easier function class), the required width increases, which contradicts the Γ=0 remark just below Theorem 3.2 and the lower bound in Proposition 3.3. Since the stated approximation rates are a central contribution, Eq. (3) and Corollary B.8 must be corrected consistently, with diam∞(Ω)Γ/ε in place of diam∞(Ω)/(εΓ).","section":"§3.2, Eq. (3); Corollary B.8"},{"comment":"The construction of families in general position is incomplete. The proof only ensures that the hyperplanes of a newly added family avoid the 0-dimensional intersection points of nin previous families; it does not rule out that a new hyperplane contains a lower-dimensional intersection (e.g., in R^3 the line of intersection of two previous hyperplanes), which would violate general position for n1 > nin. It also does not explicitly verify that the translations used to push the family away from previous intersections preserve the per-neuron splitting condition (11) of Lemma B.12 for all k hyperplanes, nor that the bound B on the shifts is compatible with the choices of u_k(0), β, and ϑ needed to attain k distinct active hyperplanes. Because Theorem 4.3's tightness statement rests entirely on this lemma, a complete existence proof (e.g., a genericity argument over the free parameters (w_k, b_k, u_k(0), β_k, ϑ_k)) is required.","section":"§B.2.3, Lemma B.13"}],"minor_comments":[{"comment":"The text says 'the shifts (as defined in the proof of Lemma B.11) are bounded,' but the shift term is defined in equation (10) of Lemma B.12, not in Lemma B.11.","section":"§B.2.3, Lemma B.13"},{"comment":"The remark that 'K can be chosen as diam∞(Ω)' is off by a factor of two: for a compact set Ω, the enclosing cube has side length at least diam∞(Ω), so the correct statement is 2K = diam∞(Ω) or K = diam∞(Ω)/2. As written, the constant in Corollary B.8 differs by a factor of two from Eq. (3).","section":"§3.2, Remark after Theorem 3.2"},{"comment":"The statement that the values Σ a_{t-i}β^i are 'decreasing' with lexicographic order is not literally true for β=1, where all codes with the same number of ones have equal shift. The argument still works because in that case the hyperplanes coincide, but the wording should be adjusted to 'non-increasing' with the equality case handled separately.","section":"§B.2.2, Lemma B.12, step 3"},{"comment":"In the proof that |C| = |R|, the identity-mapping construction via Proposition 3.1 only propagates spikes; to ensure that distinct activation patterns produce distinct outputs, the decoder must be injective on {0,1}^{n1×T} (e.g., a_t = 2^{t-1} and V = I). This is straightforward but should be stated explicitly.","section":"§B.2.4, Theorem B.14"}],"recommendation":"major_revision","confidential_remarks":"The paper is well within scope for a machine-learning theory venue, and the errors flagged are local and fixable in a revision; I do not see grounds for rejection. The main unresolved risk is Lemma B.13: if the general-position construction cannot be completed, the tightness claim of Theorem 4.3 would fail, although the upper bound would survive. I would ask the authors to provide a complete argument or a concrete small-case verification of the general-position construction."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"I've read arXiv:2505.18023 (Nguyen et al.). The genuinely new thing is the O(T^2) bound on input-space regions for discrete-time LIF-SNNs. Each first-layer neuron, despite 2^{T-1} possible spike histories, can only carve its input into (T^2+T+2)/2 regions using parallel hyperplanes. The proof via lexicographic ordering (Lemma B.12) is solid, and the tightness construction with beta=1 and irrational initial potential is convincing. The upper bound in Theorem 4.3, built on the deletion-restriction recursion for families of parallel hyperplanes, is a clean and useful contrast with ReLU ANNs: latency is doing the work that depth does in ReLU nets, and later layers just merge regions.\n\nBut there are two soft spots. First, the approximation-rate formulas in Theorem 3.2 and Corollary B.8 have an arithmetic error. With delta = epsilon/Gamma, the number of grid intervals per dimension is diam(Gamma/epsilon), not diam/(epsilon Gamma). As printed, the bound scales inversely with Gamma, which is backwards for approximating a Gamma-Lipschitz function. The proof text in the appendix actually derives the correct scaling, so this is a typo, but it is in the main theorems and it matters.\n\nSecond, the tightness of Theorem 4.3 depends on Lemma B.13, and that proof is not complete. The iterative translation construction never verifies that after shifting, every neuron's hyperplanes still lie inside the slabs from Lemma B.12, that the spike-history shifts are pairwise distinct, or that no new hyperplane passes through an intersection of several prior families. Any one of those failures would drop the region count below the claimed bound. The upper bound is safe; the tight Theta(T^2) claim is not fully established. An explicit construction for a small T and n_in, or a more careful degeneracy argument, would settle it.\n\nThe experiments are a nice sanity check, but there's no released code and no variance estimates. That's minor for a theory paper.\n\nOverall, the partitioning result is a real contribution and the paper deserves a serious referee. It needs the formula fix and a rigorous Lemma B.13 before the tight claim is usable. I'd send it to review, and I'd probably cite the per-neuron bound even with a note.","headline":"A genuinely new O(T^2) partitioning bound for discrete-time LIF-SNNs, with a fixable approximation-rate typo and a tightness proof that needs to be completed.","tokens_in":39447,"tokens_out":3433,"would_cite":true,"duration_ms":31169,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","52C35","41A25"],"pacs":[],"model":"deepseek-v4-flash","headline":"Discrete-time LIF spiking networks are universal approximators with explicit neuron counts, and their input-space partitions grow quadratically with latency while depth adds no new regions.","keywords":["spiking neural networks","discrete-time LIF","expressivity","universal approximation","input space partitioning","hyperplane arrangements","latency","polyhedral regions"],"falsifier":"Enumerate, with exact rational arithmetic, all spike histories of a single first-layer LIF neuron for a fine sweep of $\\beta,\\vartheta,u_k(0)$ and $T=8$: the quadratic bound predicts at most $(8^2+8+2)/2=37$ distinct spike time series over inputs, and tightness predicts that some parameter choice attains 37. Finding 38 or more histories would refute Lemma 4.2; an exhaustive search that never reaches 37 would refute the tightness claim.","tokens_in":38340,"feed_emoji":"⚡","tokens_out":15637,"duration_ms":108478,"temperature":0.7,"pith_summary":"The paper sets out to establish a quantitative theory of what discrete-time leaky integrate-and-fire spiking neural networks (LIF-SNNs) can represent when inputs and outputs are static vectors. Its main claims are that these networks realize piecewise-constant functions on polyhedral regions, that two-layer networks with a single time step are universal approximators of continuous functions with explicit neuron counts, and that the number of input-space regions produced by a first-layer neuron grows only quadratically with latency $T$: at most $(T^2+T+2)/2$, despite $2^{T-1}$ possible spike histories at time $T$. A consequence is that depth does not increase the region count, since later layers only merge regions, so latency is the resource that separates these networks from ReLU and Heaviside ANNs. The paper also reports experiments on CIFAR-10 and SVHN that are consistent with the first hidden layer acting as a bottleneck, with larger $T$ raising training accuracy.","feed_headline":"One spiking neuron carves at most (T^2+T+2)/2 input regions","feed_subtitle":"Each neuron's parallel boundaries grow quadratically with time steps; deeper layers only merge regions.","key_machinery":"The engine of the argument is the closed-form expression for a single first-layer neuron's spike output,\n$$s_k(t) = H\\Bigl(\\langle w_k,x\\rangle + b_k + g_{t-1}(s_k(1),\\ldots,s_k(t-1))\\Bigr),$$\nwhere $g_{t-1}$ is a scalar shift depending only on the neuron's past spikes and on the temporal parameters $u_k(0),\\beta,\\vartheta$ and $t$. Because the weight vector $w_k$ is shared across time steps, every decision boundary of this neuron is a hyperplane parallel to $\\langle w_k,x\\rangle+b_k=0$, and the shift only moves that hyperplane along its normal. The proof counts how many of these shifted hyperplanes can actually lie inside the region they are supposed to cut: at transition $t-1\\to t$, at most $t$ regions are split, summing to $1+\\sum_{t=1}^T t=(T^2+T+2)/2$. The extension to many neurons applies a deletion-restriction count for families of parallel hyperplanes, a variant of Zaslavsky's theorem, and a general-position construction for the tightness claim.","core_discovery":"The central discovery is that the representational complexity of a discrete-time LIF-SNN is fixed already by the first hidden layer together with the latency $T$: each neuron in that layer separates the input space by a family of parallel hyperplanes, and one neuron can create at most $(T^2+T+2)/2$ regions, on each of which its spike time series is constant. Across $n_1$ first-layer neurons and input dimension $n_{\\mathrm{in}}$, the maximum number of activation regions is bounded by $\\sum_{i=0}^{n_{\\mathrm{in}}} ((T^2+T)/2)^i \\binom{n_1}{i}$ when $n_1 \\ge n_{\\mathrm{in}}$, and by $((T^2+T+2)/2)^{n_1}$ when $n_1 < n_{\\mathrm{in}}$; the paper claims the bound is attainable by suitable network parameters. The same section proves that adding layers beyond the first cannot create new activation regions, only merge them. On the approximation side, the paper proves that $T=1$ two-layer discrete-time LIF-SNNs realize any step function on a grid of hypercubes, hence approximate every continuous function on a compact set, with explicit width bounds in the Lipschitz case and a matching lower bound on $[0,1]$ for $f(x)=\\Gamma x$.","pith_inferences":["If the quadratic region bound is generically attained, the first-layer geometry is an arrangement of parallel slabs rather than a generic hyperplane arrangement; this suggests the network's effective decision surface is closer to a set of correlated thresholded projections, which may explain why a narrow first layer cannot be rescued by depth.","The empirical observation that shifts can become periodic for leaky parameters below 1 (for example $\\beta=0.8$) suggests the theoretical $O(T^2)$ growth may overstate practically realizable region counts at large $T$; one test is to count non-empty regions under random initialization and increasing latency.","The order-optimal approximation lower bound is proven only in one dimension; identifying worst-case Lipschitz targets in higher dimensions would determine whether the linear width scaling of the upper bound is fundamental.","Viewing the membrane potential as a hidden state, the quadratic region bound resembles a reachable-state count for a one-dimensional threshold automaton; this suggests direct comparisons with recurrent networks and state machines that the paper does not draw."],"forward_implications":["Increasing latency $T$ in a shallow discrete-time LIF-SNN raises the maximum number of activation regions by a factor quadratic in $T$ per first-layer neuron, whereas increasing depth leaves the region count unchanged.","With $n_1 < n_{\\mathrm{in}}$, a first hidden layer of $n_1$ neurons can generate at most $((T^2+T+2)/2)^{n_1}$ regions, so the width of the first layer is an exact ceiling on the number of distinct spike patterns the network can produce.","At $T=1$ the model reduces to a Heaviside ANN, and the paper's approximation results give explicit worst-case-optimal neuron counts for Lipschitz functions, improving the previous quadratic width bound to a linear one.","Because deeper layers only merge activation regions, a network that needs many separable input regions must put width or latency into the first layer; later layers can refine the function on existing regions but cannot create new ones.","The experiments indicate that high latency raises training accuracy mainly through the refined first-layer partition, and that the practical benefit of further increasing $T$ can be limited because the added regions shrink in width."],"supporting_citations":[{"why":"defines the linear-region counting problem for ReLU networks whose bounds the SNN region result extends and contrasts with","marker":"Montúfar et al., 2014"},{"why":"provides the shallow-ReLU arrangement bound and the general-position role that Theorem 4.3 compares against","marker":"Pascanu et al., 2014"},{"why":"supplies Zaslavsky's theorem, the enumerative result underlying the count of regions created by families of parallel hyperplanes","marker":"Zaslavsky, 1975"},{"why":"supplies the hyperplane-arrangement definitions, deletion-restriction recursion, and general-position terminology used in the proof","marker":"Stanley, 2011"},{"why":"establishes that linear-threshold (Heaviside) networks realize piecewise-constant polyhedral functions and gives size bounds that the approximation theorem builds on and improves","marker":"Khalife et al., 2024"},{"why":"earlier empirical observation that discrete LIF neurons generate parallel hyperplanes in input space, which the paper formalizes and quantifies","marker":"Kim et al., 2022"}],"fun_headline_variants":["Spiking nets: first layer sets all limits, depth only merges","One neuron, T steps: (T^2+T+2)/2 regions max","SNN power: latency boosts regions, extra layers don't","Discrete-time spiking: capacity fixed by first layer and T"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The claim that the upper bound on region counts can actually be attained assumes one can arrange the parallel decision lines of all first-layer neurons so that they never coincide or cross in forbidden ways; the proof gives a translation construction for this but does not check every possible shift coincidence across time steps.","fun_headline_variants_meta":{"raw":{"variants":["Spiking nets: first layer sets all limits, depth only merges","One neuron, T steps: (T^2+T+2)/2 regions max","SNN power: latency boosts regions, extra layers don't","Discrete-time spiking: capacity fixed by first layer and T"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000236,"raw_usage":{"total_tokens":1544,"prompt_tokens":1027,"completion_tokens":517,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":643,"completion_tokens_details":{"reasoning_tokens":438}},"tokens_in":643,"tokens_out":517,"duration_ms":4015,"temperature":1.0,"reasoning_tokens":438,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:38:01.219524+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate, with exact rational arithmetic, all spike histories of a single first-layer LIF neuron for a fine sweep of $\\beta,\\vartheta,u_k(0)$ and $T=8$: the quadratic bound predicts at most $(8^2+8+2)/2=37$ distinct spike time series over inputs, and tightness predicts that some parameter choice attains 37. Finding 38 or more histories would refute Lemma 4.2; an exhaustive search that never reaches 37 would refute the tightness claim.","supporting_citations":[{"cited_title":"On the number of inference regions of deep feed forward networks with piece-wise linear activations","cited_arxiv_id":null,"evidence_quote":"provides the shallow-ReLU arrangement bound and the general-position role that Theorem 4.3 compares against"},{"cited_title":"Facing up to arrangements: Face-count formulas for partitions of space by hyperplanes","cited_arxiv_id":null,"evidence_quote":"supplies Zaslavsky's theorem, the enumerative result underlying the count of regions created by families of parallel hyperplanes"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the hyperplane-arrangement definitions, deletion-restriction recursion, and general-position terminology used in the proof"},{"cited_title":"Neural networks with linear threshold activations: structure and algorithms","cited_arxiv_id":null,"evidence_quote":"establishes that linear-threshold (Heaviside) networks realize piecewise-constant polyhedral functions and gives size bounds that the approximation theorem builds on and improves"},{"cited_title":"Neural architecture search for spiking neural networks","cited_arxiv_id":null,"evidence_quote":"earlier empirical observation that discrete LIF neurons generate parallel hyperplanes in input space, which the paper formalizes and quantifies"}],"review_version":1}