Upper bounds on the number of causal pieces in spiking neural networks

Dominik Dold; Dennis Elbrächter; Philipp Petersen

Source-linked AI summary

Upper bounds on the number of causal pieces in spiking neural networks

Dominik Dold, Dennis Elbrächter, Philipp Petersen

arXiv:2610.22484v1Oct 15, 2026cs.NEcs.AIcs.LGq-bio.NCstat.ML

TL;DR

The paper asks how many causal pieces feedforward single-spike SNNs can realise, a question connected to approximation error. It derives combinatorial and model-specific hyperplane-arrangement upper bounds; the latter include an nLIF Dirac-δ bound independent of network depth and subsequent layer widths.

Problem
The number of causal pieces that SNNs can realise is unknown, although that number is relevant to approximation capabilities.
Source: §1 · pp. 1–2
Method
The paper derives combinatorial bounds using temporal constraints and lonesum-matrix counting, alongside hyperplane-arrangement bounds for specific neuron models.
Source: §1 · pp. 2–3, §5.1 · p. 11
Results
The combinatorial approach yields a poly-Bernoulli bound, while the nLIF Dirac-δ hyperplane bound depends only on input dimension, independently of depth and later-layer widths.
Source: §1 · pp. 2, 4
Takeaways & Limitations
Upper bounds on causal-piece counts provide bounds relevant to SNN approximation capabilities.
Source: §1 · p. 1
The paper does not establish that its upper-bound exponents are optimal, and the nLIF exponential-synapse lower bound applies only in a parameter regime where its response sufficiently approximates the ReLU-type response.
Source: §1 · p. 4

Abstract

from arXiv · show

The input space of single-spike neural networks decomposes into causal pieces, and the number of causal pieces has been shown to provide a lower bound on the approximation error for some spiking neural networks. While this decomposition is applicable to a wide range of spiking neuron models, the limits of how many causal pieces can be realised by spiking neural networks are still unknown. In this work, we derive two complementary upper bounds on the number of causal pieces in feedforward single-spike neural networks. First, we establish a combinatorial bound given by the poly-Bernoulli numbers, which applies to a broad class of spiking neuron models. The bound is of order $e^{2(L-1)N\log N+\mathcal{O}(N)}$, with network depth $L$ and maximum layer width $N$. Second, for a specific set of neuron models, we derive a bound based on hyperplane arrangements. Applying the latter framework, we obtain bounds of order $\mathcal{O}\!\left(N^{(4L-3)(N_0-1)}\right)$ for the non-leaky integrate-and-fire model with exponential synapses and the ReLU-type spike response model, and $\mathcal{O}\!\left(N^{L(N_0-1)}\right)$ for the leaky integrate-and-fire model with Dirac-$\delta$ synapses, where $N_0$ is the input dimension. For the non-leaky integrate-and-fire model with Dirac-$\delta$ synapses, additional temporal structure allows us to sharpen the general combinatorial bound to one that depends only on $N_0$, independently of the network depth and widths.

1 Introduction

Causal pieces are input regions that activate the same subnetwork; their number is relevant to SNN approximation error, but how many can be realised was unknown. The paper derives broadly applicable combinatorial bounds and model-specific hyperplane-arrangement bounds, with lower-bound results clarifying limits on their tightness.

1 Introduction

Causal pieces are input regions with the same active subnetwork, and their number lower-bounds approximation error for some SNNs [1, Theorem 1].They capture the neurons and synaptic connections through which input spikes influence output spike times.Source: §1 · p. 1
Temporal ordering forces causal sets of finite-spiking neurons to be nested, yielding lonesum active-connection matrices and a poly-Bernoulli upper bound for arbitrary synaptic weights.This bound is substantially tighter than the initial combinatorial bound; the general combinatorial approach does not require positive weights or a particular neuron model.Source: §1 · p. 2
Hyperplane-arrangement bounds apply to specific models whose causal pieces become polyhedral after reparameterisation, including nLIF with exponential synapses, ReLU-type response, and nLIF/LIF with Dirac-δ synapses.These bounds track intermediate-layer image dimension and can be tighter for networks with low-dimensional bottlenecks.Source: §1 · p. 3
The hyperplane bounds have polynomial dependence on maximum width, while the nLIF Dirac-δ bound depends only on input dimension, not depth or later-layer widths.The paper also reports that shallow ReLU-response networks attain a matching width dependence for fixed input dimension under the stated conditions.Source: §1 · p. 4
Exponential dependence on bottleneck dimension and depth is unavoidable, but the optimality of the upper-bound exponents remains unresolved.For nLIF with exponential synapses, the lower-bound extension applies only in a parameter regime where the response sufficiently approximates the ReLU-type response; Dirac-δ cases have matching lower bounds as described.Source: §1 · p. 4

2 Related work

Prior work bounded causal-piece counts and studied their role in SNN expressivity, including hyperplane-arrangement bounds for particular models. This paper’s approach differs by allowing broader weight settings and accounting for reachable dimensions across layers.

Earlier worst-case upper bounds for individual spiking neurons and deep SNNs were reported, and the present work characterizes its bounds as tighter.Source: §2 · p. 4
Singh et al. [6] derive exact shallow-network counts for positive-weight ReLU-response networks with shared positive weight vectors, whereas this paper’s combinatorial result does not require shared or positive weights.Source: §2 · p. 5
For ReLU-response networks, Singh et al. [6] use hyperplane arrangements; this work conditions hyperplane counting on presynaptic spike order and propagates reachable dimensions across layers.The dimension propagation can reduce region counts in networks with bottleneck layers.Source: §2 · p. 5
ReLU networks have affine-piece bounds of order O(N^(L N0)) for fixed input dimension and depth, while the SNN bounds account for intermediate bottleneck dimensions.Source: §2 · p. 5
Other SNN expressivity measures include distinct functions on finite input sets, universal representation and network-size bounds, and generalisation or approximation bounds for encoded ReLU-response networks.These approaches are described in [23], [23], and, respectively.Source: §2 · p. 5

3 Background

The section defines causal sets and subnetworks, then uses them to describe input regions where the same causal subnetwork determines the output. It distinguishes causal-set conventions according to how synaptic input affects a spike.

A causal set records presynaptic neurons that caused a neuron to fire, while a causal subnetwork extends this notion through the layers of a deep network.The subnetwork recursion follows presynaptic indices included in the causal sets.Source: §3 · pp. 5–6
Exclusive causal sets fit models whose incoming-spike contribution starts at zero, whereas inclusive sets fit Dirac-δ synapses, where input contributes immediately.The distinction avoids including simultaneous arrivals when transformed affinity may fail.Source: §3 · p. 6
A causal piece is an input-space region whose inputs produce the output through the same causal subnetwork; this work fixes network weights and considers input space only.Source: §3 · p. 6
The paper studies ReLU-type response, nLIF with exponential or Dirac-δ synapses, and LIF with Dirac-δ synapses; a neuron that never reaches threshold has spike time ∞.Source: §3 · pp. 6–7

4 Combinatoric upper bounds for general spiking neuron models

The section bounds causal-piece counts by representing causal subnetworks as binary activity matrices and exploiting the nesting imposed by spike timing. For layers receiving shared presynaptic spike times, the resulting matrices are lonesum and can be counted using poly-Bernoulli numbers.

The number of causal pieces is bounded by the number of realisable causal-subnetwork tuples, and an unrestricted binary-matrix count gives a worst-case bound.Source: §4 · p. 8
For a layer whose neurons receive the same presynaptic spike times, its causal-subnetwork activity matrices are lonesum because spike-time ordering forces nested causal sets.A lonesum matrix is uniquely reconstructible from its row and column sums.Source: §4 · p. 8
The lonesum-matrix count is exactly given by poly-Bernoulli numbers, yielding the section’s combinatorial counting framework.Nested causal-set assignments are what the poly-Bernoulli count enumerates.Source: §4 · pp. 9–10
The bound applies when each layer’s neurons receive the same presynaptic spike times, including zero-delay and axonal-delay settings; it does not require exclusively positive weights.Source: §4 · p. 9
For maximum width N and depth L, the general estimate is bounded by (N + 1)^(2NL).Source: §4 · p. 9

5 Derivation of hyperplane-based upper bound

This section derives hyperplane-arrangement upper bounds for causal pieces under structural assumptions on neuron spike-time maps, complementing the combinatorial bound. It develops the general bound by iteratively refining input-space partitions while preserving fixed weak orders and the correspondence between finite outputs and transformed input coordinates.

5 Derivation of hyperplane-based upper bound

Hyperplane-based bounds complement the combinatorial bound and provide far tighter scaling with maximum width, input dimension, and depth.The framework also yields tighter bounds for Dirac-δ synapse models because output spikes must coincide with input spikes.Source: §5 · p. 10

5.1 Spiking neuron model assumptions

The assumptions partition transformed spike-time space into polyhedral regions where causal sets are fixed and firing outputs are affine, with translation or scaling symmetry reducing effective dimension by one.Regions are distinguished by affine test functions; without the symmetry, the dimension term uses min_{0≤r≤ℓ} N_r instead of min_{0≤r≤ℓ}(N_r−1).Source: §5.1 · pp. 11–12

5.2 General hyperplane bound

Under Assumption 5.5, a general hyperplane-arrangement bound controls causal-piece counts by constructing a partition on which neuron causal sets are constant.The proof bounds the number of partition regions layer by layer using possible weak orders and affine-test-function sign patterns, then transfers that partition bound to causal pieces.Source: §5.2 · pp. 13, 15
A further corollary applies when each finite output spike coincides with an input-spike coordinate associated with a block in the fixed weak order.Under this additional condition, the partition and affine-test-function counts are bounded in terms of the number of weak-order blocks.Source: §5.2 · pp. 15–16
q ≤ min_{0≤r≤ℓ−1} N_r = d_{ℓ−1} + 1 bounds the distinct finite values entering layer ℓ.Finite output values are inherited from incoming coordinates, so those q distinct values must occur in every preceding layer.Source: §5.2 · p. 16
Each layer partition can be refined either into at most p(q)^{N_ℓ} sets or by joint affine-function sign patterns in dimension at most d_{ℓ−1}.Choosing the refinement with the smaller bound gives the per-layer subdivision factor; the supplied passage does not include its explicit expression.Source: §5.2 · pp. 16–17
Multiplying the subdivision factors across layers and by |P₀| yields the claimed bound, because each final partition set lies within one causal piece.The construction preserves the property that each finite output equals a fixed transformed input coordinate.Source: §5.2 · p. 17

6 Hyperplane bounds for specific neuron models satisfying Assumption 5.5

The section derives hyperplane-based causal-piece upper bounds for specific single-spike neuron models, using partitions conditioned on presynaptic spike order. The model-specific arguments exploit affine or linear behavior on those partitions, and for Dirac-δ models exploit the constraint that output spikes coincide with input spikes.

6 Hyperplane bounds for specific neuron models satisfying Assumption 5.5

The bounds apply to networks without delays, where each layer receives the previous layer’s spike times, and are derived for four specific neuron models.The models are nLIF with exponential synapses, ReLU-type response, LIF with Dirac-δ synapses, and nLIF with Dirac-δ synapses.Source: §6 · p. 17, §6.1 · p. 17, §6.2 · p. 19

6.1 Upper bound for nLIF with exponential synapses

For nLIF with exponential synapses, partitions by presynaptic spike order make finite restrictions linear and keep output status and exclusive causal sets constant within each partition.The proof verifies the model assumptions and applies the general hyperplane bound.Source: §6.1 · pp. 17–18

6.2 Upper bound for ReLU-type response model

For the ReLU-type response model, affine threshold-hit conditions partition each presynaptic-order domain into regions with constant causal sets.The proof verifies the assumptions needed to apply the general bound.Source: §6.2 · pp. 19–20

6.3 Upper bound LIF with Dirac-delta synapses

For LIF with Dirac-δ synapses, partition membership is determined by linear tests, with at most q partition sets and q−1 test functions in the stated construction.The theorem covers single-spike networks with a common time constant.Source: §6.3 · pp. 20–21

6.4 Upper bound nLIF with Dirac-delta synapses

For nLIF with Dirac-δ synapses, each weak-order domain lies within one causal piece, so counting input weak orders bounds the number of causal pieces.Induction fixes the finite-spike indices and their weak order across layers; output spikes coincide with incoming spike times.Source: §6.4 · p. 21

Use of AI tools

The authors report iterative use of ChatGPT for brainstorming, refining ideas, mathematical formalisation, and presentation; they state that they revised and verified assisted manuscript parts and take full responsibility for the paper.

Use of AI tools

ChatGPT was used iteratively for brainstorming, idea refinement, mathematical formalisation, and presentation, with assisted manuscript parts subsequently revised and verified by the authors.The authors take full responsibility for the mathematical statements, proofs, conclusions, and final manuscript.Source: Use of AI tools · p. 22

A.1 nLIF neuron with approximately ReLU-type response

Compressing input spike times and rescaling synaptic weights makes the nLIF response converge to the ReLU-type response on bounded intervals. This approximation preserves the selected causal subnetworks for sufficiently small compression, so the nLIF network realizes at least as many distinct causal subnetworks as the construction.

A.1 nLIF neuron with approximately ReLU-type response

The rescaled nLIF response converges uniformly to the ReLU-type response on bounded intervals, and its spike times converge layer by layer.The argument uses nonnegative weights, positive thresholds, and positive slope at each ReLU-response threshold crossing.Source: §A.1 · pp. 23–24
A sufficiently small common compression preserves the causal subnetworks at all selected inputs, so the nLIF network realizes at least as many distinct causal subnetworks as the construction.Finitely many selected inputs and spike-order comparisons allow one positive compression parameter to preserve them all.Source: §A.1 · p. 24

A.2 Neurons with Dirac-δ synapses

A base-m digit-extraction construction shows that the width exponent for LIF networks with Dirac-δ synapses is sharp. Its firing patterns yield Θ_d,L(N^dL) causal pieces for fixed input dimension and depth.

A.2 Neurons with Dirac-δ synapses

The bound for nLIF networks with Dirac-δ synapses is attained exactly when identity-weight layers preserve each input spike time, so final-layer causal sets determine the input's complete weak order.The construction uses equal layer widths n and W^(ℓ) = ϑI_n.Source: §A.2 · p. 24
Θ_d,L(N^dL) is the maximal number of causal pieces for fixed input dimension d+1 and depth L, with common time constant and subsequent widths at most N.The width exponent is sharp.Source: §A.2 · p. 24
Each layer extracts a base-m digit of each transformed input xa = e^-Ta/τ using spike-time tests, while reference spikes and earlier tests are copied forward.The construction uses m−1 test neurons per input and layer.Source: §A.2 · p. 24
Different digit arrays yield distinct final-layer firing patterns and causal pieces, giving C⋄(Φ) ≥ m^dL for ⋄ ∈ {<, ≤}.Firing tests and their copies have nonempty exclusive causal sets; non-firing neurons have empty causal sets.Source: §A.2 · p. 25