Breaking Local-Minimum Traps in Spiking Neural Network-Based Solvers for CSPs via Parallel Tempering

Jul 16, 2026

Upload by Riley

Spiking neural networks (SNNs) with stochastic neurons solve constraint satisfaction problems (CSPs) by encoding constraints in connectivity and performing probabilistic search through spike dynamics. Fixed-temperature dynamics often become trapped near-satisfying local minima, especially as instances get harder. This work integrates parallel tempering (PT) into a neural sampling solver by running multiple replicas at different inverse temperatures and exchanging temperatures. Experiments on SATLIB uf20-91 show improved success on 332/1000 instances with gains concentrated on hard cases, and trajectory analysis confirms PT enables escape from energy barriers unreachable by fixed-temperature dynamics.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages14

Reading Time35 min

Introduction

Local-minimum trapping in CSP solving with SNNs

Parallel tempering and replica exchange

Contributions and evaluation setup

Breaking Local-Minimum Traps in Spiking Neural Network-Based Solvers for CSPs via Parallel Tempering Recep Bugra Uludag University of Minnesota-Twin Cities [uluda002@umn. edu](uluda002@umn. edu) Ahmet Efe University of Minnesota-Twin Cities [efe00002@umn. edu](efe00002@umn. edu) Ismail Akturk Ozyegin University [ismail. akturk@ozyegin. edu. tr](ismail. akturk@ozyegin. edu. tr) Ulya R. Karpuzcu University of Minnesota-Twin Cities [ukarpuzc@umn. edu](ukarpuzc@umn. edu) arXiv :2607 .08897v 1 [ cs .ET] 9 Jul 2026 Abstract Spiking neural networks (SNNs) with stochastic neurons can solve constraint satisfaction problems (CSPs) by encoding constraints via connectivity and performing probabilistic search via spike dynamics. However, fixed-temperature stochastic dynamics often get trapped in local minima—near-satisfying configurations—a vulnerability that escalates with problem difficulty. To overcome this, we integrate parallel tempering (PT) into the neural sampling solver, running multiple parallel replicas at varying inverse temperatures. Replicas periodically exchange temperatures rather than network states, managing the trade-off between exploration and concentration around low-energy configurations while preserving asynchronous, spike-based computation. We evaluate this architecture against a parallel baseline of four independent, fixed-temperature solvers using equal computational resources across 1000 instances from the SATLIB uf20-91 benchmark. Parallel tempering improves success probability on 332 instances while worsening only 5 . Crucially, these gains are concentrated on hard instances where independent solvers fail. Violation trajectory analysis confirms the underlying mechanism: temperature exchanges allow replicas to traverse energy barriers unreachable by fixed-temperature dynamics, successfully escaping the narrow basins that constrain the baseline. To our knowledge, this represents the first integration of parallel tempering into an SNN-based CSP solver. 1 Introduction Constraint satisfaction problems (CSPs) are mathematical problems in which values must be assigned to variables so that a set of constraints is satisfied [1] . Many important real-world decisionmaking tasks can be formulated as CSPs or closely related constraint-based optimization problems, including digital circuit verification [2], vehicle routing in logistics networks [3, 4], and resource allocation in cloud and data-center infrastructures [5] . Despite this broad applicability, CSPs are often computationally challenging. Many classes of CSPs are NP-complete, and practical search procedures frequently become trapped in local minima or near-satisfying configurations that hinder efficient discovery of valid solutions [6] . These challenges motivate the exploration of alternative search paradigms, particularly stochastic neural approaches that can support probabilistic exploration of complex solution spaces [7] . In these approaches, constraints are encoded directly in the network connectivity, and stochastic spike dynamics perform probabilistic search through the space of configurations. The neural sampling framework [8] provides a principled foundation for this approach, establishing conditions under (a) Analytical energy landscape for the SAT formula (x1 ∨ x2 ∨ x3 ) ∧ (¬x2 ∨ ¬x3 ∨ ¬x4 ) . Each cell represents a configuration of the binary variables. Cross marks (in green) mark satisfying assignments. (b) Boltzmann probability distribution over the same configuration space at different inverse temperatures β = 1/T. Higher β concentrates probability mass around low-energy configurations, illustrating how temperature controls the progress of the stochastic search. Figure 1: Energy landscape and temperature-controlled sampling for a representative SAT problem. which stochastic spiking dynamics approximate sampling from an energy-based probability distribution defined by the network structure. Within this framework, solvi

FAQs

How do spiking neural network-based solvers encode CSPs?

They encode CSP constraints directly into the network connectivity and use stochastic spike dynamics to perform a probabilistic search over configurations. Solving corresponds to finding low-energy configurations in the induced energy landscape.

What problem limits fixed-temperature stochastic neural dynamics?

Fixed-temperature dynamics can get trapped in local minima, spending substantial time in partially satisfying assignments that block progress toward valid solutions. This vulnerability increases as problem difficulty grows.

How does parallel tempering improve the SNN-based CSP solver?

Parallel tempering runs multiple asynchronous replicas at different inverse temperatures and periodically exchanges temperatures between replicas. This lets some replicas cross energy barriers while others refine low-energy configurations, improving success especially on hard instances.

Jul 16, 2026

Upload by Riley