parallel-tempering-snn-csp

name	parallel-tempering-snn-csp
description	Parallel tempering (replica exchange) integrated into a stochastic Spiking Neural Network (SNN) solver for Constraint Satisfaction Problems (CSPs). Multiple replica networks run at different inverse temperatures and periodically exchange temperatures (not states), letting replicas cross energy barriers unreachable by fixed-temperature dynamics. First integration of PT into an SNN-based CSP solver; concentrated gains on hard SATLIB uf20-91 instances. Use when building or improving stochastic SNN / neural-sampling solvers for combinatorial optimization, escaping local minima in spike-based probabilistic search, neuromorphic CSP/SAT solving, or studying temperature- exchange mechanisms in spiking systems. Triggered by: parallel tempering SNN, replica exchange spiking, stochastic spiking neuron CSP, neural sampling SAT solver, spike-based probabilistic search, local minimum escape SNN, uf20-91, neuromorphic constraint satisfaction.
license	arXiv perpetual non-exclusive
metadata	{"arxiv_id":"2607.08897","published":"2026-07-09","authors":"Recep Bugra Uludag, Ahmet Efe, Ismail Akturk","tags":["spiking-neural-networks","parallel-tempering","replica-exchange","constraint-satisfaction","csp","sat","neural-sampling","stochastic-neurons","combinatorial-optimization","neuromorphic"]}

Parallel Tempering for Spiking Neural Network CSP Solvers

arXiv: 2607.08897 | Published: 2026-07-09 | Category: cs.NE / cs.AI

Core Problem

Stochastic SNNs can solve Constraint Satisfaction Problems (CSPs) by:

• Encoding constraints into network connectivity (weights), and
• Performing probabilistic search via spike-timing / rate dynamics (neural sampling).

But fixed-temperature stochastic dynamics get trapped in local minima — near-satisfying configurations that become harder to escape as problem difficulty grows. This is the central bottleneck for neural-sampling CSP solvers.

Core Innovation

Integrate Parallel Tempering (PT) — a well-known MCMC replica-exchange method — into the spiking neural sampler. Instead of running one network at one temperature:

• Run K parallel replica networks at different inverse temperatures β = 1/T.
• Replicas exchange temperatures (not states) on a schedule.
• A hot replica (low β) explores freely; a cold replica (high β) concentrates on low-energy, near-satisfying solutions.
• Temperature exchange lets the cold replica "inherit" a hot-replica configuration that has crossed an energy barrier it could never cross on its own.

This preserves asynchronous, spike-based, event-driven computation — no central controller, no state copying, just a periodic temperature swap across replicas.

Why This Beats a Parallel Baseline

Equal-compute comparison against 4 independent fixed-temperature solvers on 1000 SATLIB uf20-91 instances:

• PT improves success probability on 332 instances, worsens only 5.
• Gains are concentrated on the hard instances where independent solvers fail.
• Violation-trajectory analysis confirms the mechanism: temperature exchanges let replicas traverse energy barriers unreachable by fixed-temperature dynamics, escaping the narrow basins that constrain the baseline.

Architecture

Neural Sampling SNN (single replica)

• Stochastic spiking neurons; spike probability parameterized by membrane potential.
• Constraints → connectivity; solution = low-energy attractor of the spike dynamics.
• Temperature β scales the stochastic acceptance / effective noise.

Parallel Tempering Layer

For each swap interval:
   1. Run K replicas {R_0..R_{K-1}} at β_0 < β_1 < ... < β_{K-1}
   2. Propose exchange between adjacent (R_i, R_{i+1}) with probability:
         min(1, exp( (β_i − β_{i+1}) · (E_{i+1} − E_i) ))
   3. Accept → swap their temperatures (each replica keeps its own network state)
   4. Continue asynchronous spike-based evolution

• Key detail: only temperatures swap; each replica's weights/state stay local and event-driven. This keeps the per-replica compute identical to a standalone solver.
• Energy E = number of constraint violations (Hamming-style cost of current spiking config).

Geometric temperature ladder

• β spaced geometrically (β_{i+1} = λ·β_i) to balance acceptance rate across the ladder.
• Typical: K = 4, λ chosen so the hottest replica mixes freely and the coldest is near-convergent.

When to Use

• Neuromorphic CSP / SAT solving where fixed-temperature solvers stall on hard instances.
• Escaping local minima in any spike-based probabilistic search.
• Combinatorial optimization on spiking hardware (Loihi, SpiNNaker, TrueNorth-style) where you can instantiate multiple replica cores.
• As a drop-in augmentation to any neural-sampling SNN: keep the base solver, wrap K replicas with a temperature-exchange scheduler.

Implementation Pattern (sketch)

class PTSNNCSP:
    def __init__(self, k_replicas, beta_ladder, swap_interval):
        self.replicas = [StochasticSNN(beta=b) for b in beta_ladder]   # each: own weights+state
        self.swap_interval = swap_interval
        self.step = 0

    def step_network(self):
        for r in self.replicas:
            r.spike_step()                       # async, event-driven, no central control
        self.step += 1
        if self.step % self.swap_interval == 0:
            self.exchange_temperatures()

    def exchange_temperatures(self):
        for i in range(len(self.replicas) - 1):
            r_i, r_j = self.replicas[i], self.replicas[i+1]
            dE = r_j.energy() - r_i.energy()
            p = min(1.0, exp((r_i.beta - r_j.beta) * dE))
            if random() < p:
                r_i.beta, r_j.beta = r_j.beta, r_i.beta   # swap TEMP only, keep states

    def solution():
        coldest = (.replicas, key= r: r.beta)   
         coldest.best_config

Validation Checklist

• Replicas are true independent copies (own weights + state) — only β is shared/exchanged.
• Temperature ladder acceptance rate is balanced (aim ~20–40% adjacent swap acceptance).
• Compare against an equal-resource parallel baseline (same K, same total spike budget).
• Report per-instance success delta, not just aggregate — PT wins on hard instances.
• Violation-trajectory plot to confirm barrier crossing after exchanges.

Relationship to Other Skills

• Pairs naturally with [[dendritic-in-context-learning-snn]] and [[dynamic-neural-manifolds-control]] as part of the stochastic / structured SNN toolbox in this collection — all three show how circuit-level mechanisms (temperature exchange, apical dynamics, subspace control) replace heavy machinery (ensemble depth, attention).
• Conceptually related to replica-exchange MCMC and simulated annealing, but instantiated on an event-driven spiking substrate rather than a von Neumann sampler.