Energy Minima Are Not Enough: A Free-Energy Design Condition for Encoding Shortest Path in Stochastic Spiking Networks

Technical Summary: Energy Minima Are Not Enough: A Free-Energy Design Condition for Encoding Shortest Path in Stochastic Spiking Networks

Problem Statement
The paper addresses the design of stochastic spiking neural networks (SSNNs) that admit a Boltzmann stationary distribution to solve combinatorial optimization problems, specifically the weighted shortest path problem. While previous work established that such networks can be designed so that the solution corresponds to the minimum of an energy function, this paper argues that ensuring the correct configuration is the energy minimum is insufficient. Two distinct conditions are required for the network to correctly encode the shortest path:

1. Ordering: The energy function must rank the shortest path as the minimum among all valid path configurations.
2. Discrimination: The path sector must carry sufficient aggregate probability mass to overcome the entropic advantage of "scatter" configurations (disjoint edge sets) that mimic the path's activity level but lack continuity.

The paper demonstrates that standard design parameters often fail to satisfy the discrimination condition and that a specific structural augmentation (terminal drive) is required to exclude competing configurations that are energetically cheaper than the shortest path.

Methodology
The author analyzes a specific construction where a weighted graph is compiled into a network of Winner-Take-All (WTA) clusters. Each cluster represents a traversal of a vertex rather than the vertex itself. The network employs three coupling classes:

• $\alpha$ (Continuity): Rewards a pair of active neurons in opposite slots of a cluster (representing a path entering and leaving a vertex). The weight depends on the sum of the incident edge weights.
• $\beta$ (Consistency): Rewards agreement between two clusters that an edge is traversed.
• $\gamma$ (Inhibition): Enforces WTA constraints within slots.

The analysis proceeds by:

1. Exact Enumeration: Deriving closed-form expressions for the energy of path configurations and verifying them against compiled networks.
2. Combinatorial Analysis: Calculating the energy difference between a path configuration and "scatter" configurations (matchings) that have identical activity counts and $\beta$-pair counts but zero $\alpha$-pairs.
3. Free-Energy Argument: Comparing the energy margin (driven by the continuity scale $c$) against the log-multiplicity (entropy) of the competing scatter family.
4. Augmentation: Introducing two auxiliary vertices ($S$ and $T$) connected to the source and target by zero-weight edges to ensure every vertex in the path is treated as a traversal, making the energy proportional to the total path weight.
5. Simulation: Implementing an $O(|E|)$ simulator to validate scaling and perform parameter sweeps, avoiding the memory bottlenecks of explicit weight matrices.

Key Contributions

1. Two Design Conditions: The paper identifies that a single condition (ordering) is insufficient.

   • Ordering Condition ($\lambda = 0$): The length-bias coefficient $\lambda \equiv 2b_k + D + c$ must vanish. This ensures the energy of a path depends only on its total weight, not its hop count. This requires a specific bias setting: $b_k = -(D + c)/2$.
   • Discrimination Condition: The continuity scale $c$ must be large enough such that the energy margin $c(L+1)\bar{\alpha}$ exceeds the log-ratio of the number of scatter microstates to path microstates.

2. Structural Role of Terminal Drive: The paper establishes that the additive drive on the terminal neurons ($S$ and $T$) is not merely an implementation detail but a structural necessity. Without this drive, "all-silent" configurations (energy 0) or disjoint cycle configurations (which carry an extra continuity pair) can have lower energy than the shortest path, regardless of the parameterization. The drive excludes these sectors from the accessible ensemble, making the shortest path the minimum of the accessible ensemble rather than the global energy minimum.

3. The Discrimination Threshold is Not Universal: Through enumeration over 1,027 instances across four graph families (sparse, dense, grid, terrain), the author shows that the required continuity scale $c$ is not a simple function of depth or a fixed constant.

   • The required $c$ is a ratio of the log-multiplicity of competitors to the energy margin.
   • At the customary operating point ($c=4$), only 13.4% of instances satisfy the discrimination condition (counting microstates). In the lattice family, 0% clear the condition; in the spatially embedded terrain family, 35.1% clear it.
   • The paper provides a transferable law (Equation 27) to estimate the required $c$ for a given instance based on its depth, edge count, and mean edge weight, achieving a median relative error of 8.6%.

4. Correction of Previous Derivations: The paper corrects specific counting errors in the original construction (e.g., active neuron counts, $\alpha$ and $\beta$ pair counts) and clarifies that the previously published bias condition ($b_k = -(D/4 + 1)$) does not yield $\lambda=0$ unless $D=2$.

5. $O(|E|)$ Formulation: The author presents a decomposition of the membrane potential update that reduces computational complexity from $O(N d^2)$ to $O(|E|)$, enabling simulations on networks with up to 3.6 million neurons, which was previously intractable.

Results

• Failure of Standard Parameters: At the standard operating point ($c=4, B=2w_{max}$), the vast majority of instances fail the discrimination condition. The network's stationary distribution is dominated by scatter configurations or disjoint cycles rather than the shortest path.
• The "Hidden" Competitor: The analysis reveals a sector of configurations consisting of disjoint cycles (plus a path component) that are energetically cheaper than the shortest path because they possess one more continuity pair ($\alpha$-pair). No choice of $c$ can suppress these; they are excluded solely by the terminal drive.
• Trade-offs: Raising the weight normalization bound $B$ improves discrimination but tightens the tolerance required for the ordering condition ($\lambda$), creating a three-way trade-off between continuity scale, bias precision, and weight normalization.
• Sampling Obstruction: Direct sampling to confirm the discrimination condition is structurally obstructed. The path sector exists at a much lower activity level ($2L$) than the network's resting state ($O(N)$), making the probability of reaching the path sector vanishingly small in free-running dynamics without importance sampling.

Significance and Claims
The paper claims that for stochastic spiking networks to solve shortest path problems via energy minimization, the design must satisfy two independent conditions: one for ordering paths by weight and one for discriminating paths against high-entropy scatter configurations.

Crucially, the paper asserts that energy minima are not enough. Even if the shortest path is the minimum of the path sector (which requires $\lambda=0$), it is not the global minimum of the energy function because the all-silent configuration has energy identically zero. Furthermore, the paper demonstrates that disjoint cycle configurations can be energetically cheaper than the shortest path; these are excluded from the accessible ensemble only by the terminal drive, which operates outside the energy function. Thus, the shortest path is the minimum of the accessible ensemble only when the drive is active.

The author concludes that the construction's correctness relies on three components often treated as bookkeeping: the auxiliary vertices, the terminal bias, and the additive drive. Without these, the network fails to encode the shortest path. The paper does not claim that the network successfully reaches the solution in practice under standard dynamics; rather, it establishes the precise theoretical conditions required for the solution to be the minimum of the accessible ensemble and highlights that standard parameter choices ($c=4$) typically fail to meet the discrimination threshold, leaving the solution unreachable in the stationary distribution.

A scientific accuracy reviewer checked the draft against the paper and flagged these problems:

• Summary claims the shortest path is often not the global minimum; paper states it is the minimum of the path sector, while the global minimum is the all-silent state. (the paper says: "It is not the global minimum: Proposition 3 shows the all-silent configuration has energy identically zero")
• Summary claims the shortest path is often not the global minimum; paper states disjoint cycles are cheaper than the path, but the drive excludes them, making the path the minimum of the accessible ensemble. (the paper says: "What excludes them is the terminal drive, outside the energy function.")

Produce a corrected version of the draft. Fix ONLY what the reviewer flagged (verify each point against the paper) and keep everything else — the structure, the level of detail, the terminology — unchanged. Output ONLY the corrected summary.