Breaking Local-Minimum Traps in Spiking Neural Network-Based Solvers for Constraint Satisfaction Problems via Parallel Tempering

Abstract Spiking neural networks (SNNs) with stochastic neurons provide a biologically grounded substrate for solving constraint satisfaction problems (CSPs): connectivity encodes constraints, while spike dynamics support probabilistic search. However, fixed-temperature dynamics can trap SNN-based solvers in local minima, particularly on difficult problems. We address this limitation by integrating parallel tempering (PT) into a neural sampling solver. Multiple replicas run at different inverse temperatures, balancing exploration against concentration around low-energy configurations, and periodically exchange temperatures. Exchanging temperatures rather than network states preserves the intended statistical behavior while accommodating asynchronous spike-based computation. We evaluate the solver on 1000 instances from the SATLIB uf20-91 benchmark suite against four independent fixed-temperature solvers using equal computational resources. PT improves success probability on 332 instances and reduces it on only five. Gains occur exclusively on hard instances for which independent parallel solvers are insufficient. Analysis of constraint-violation trajectories shows that temperature exchanges allow replicas to access energy regions inaccessible to fixed-temperature dynamics, overcoming confinement within narrow basins. These results demonstrate that PT improves the computational effectiveness of neural sampling on difficult CSP instances without requiring exchanges of network states. To the best of our knowledge, this is the first integration of PT into an SNN-based CSP solver.