Belief propagation (BP) estimates each variable's probability by passing local messages around a graph of constraints. It is widely used to solve hard discrete problems through decimation: run BP, permanently fix the variable BP is most confident about, simplify the problem, and repeat. The method has a blind spot. Many problems are symmetric: flipping every bit in a parity-check code, or relabeling the communities in a network, leaves the problem unchanged. On such problems BP settles on marginals of exactly one half. No variable looks more confident than any other, so the "fix the most confident variable" rule has nothing to act on. The usual remedies are to clamp one arbitrary node, add a single spectral warm start, or randomize. Each is used once, or picks variables and values blindly.
The proposal is to read the choice off the curvature of the landscape BP is implicitly minimizing, rather than off the marginals. When BP stalls or oscillates, we compute the most negative direction of the Hessian of the Bethe free energy at the current state. That direction is a vector over variables saying which ones are poised to move together and with what relative signs. We then fix a small block of variables in agreement with it. The key point is that in a symmetric problem the absolute sign of the first decision is arbitrary, but the relative signs among several variables are not. A blind clamp of one node wastes that information, and a random clamp of several nodes can contradict it. We predict that eigenvector-consistent block decimation beats blind symmetry breaking exactly on symmetric problems, and gives no gain on asymmetric ones like random SAT.
Core Claim
Three results in the literature point to the same gap without closing it. They motivate the proposal.
First, Stable Fixed Points of Loopy Belief Propagation Are Local Minima of the Bethe Free Energy shows that stable BP fixed points are local minima of the Bethe free energy, the approximate objective BP optimizes. It also shows that some genuine minima repel BP's dynamics, which produces oscillations that damping cannot cure.
Second, Spectral Clustering of Graphs with the Bethe Hessian and Community Detection with the Bethe-Hessian derive the Hessian of that free energy at the uniform point, $H(r) = (r^2-1)I - rA + D$. Here $A$ is the adjacency matrix, $D$ the diagonal degree matrix, and $r$ a scale set near $\sqrt{c}$ for average degree $c$. They show its negative eigenvectors expose hidden structure down to the detectability threshold. They use it only as a one-shot spectral clustering method, never inside an iterative solver.
Third, decimation schemes pick variables by first-order confidence alone. These include BP-guided decimation for constraint satisfaction (Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation), survey-inspired decimation for lossy compression (Lossy Data Compression with Random Gates), and guided decimation for quantum codes (Belief Propagation Decoding of Quantum LDPC Codes with Guided Decimation). The measure is the bias $|p_i - 1/2|$ or the log-likelihood ratio magnitude. It is exactly zero in the symmetric regime.
Our claim is that the Bethe Hessian of the current, partially decimated problem supplies three things at once. It gives a trigger: decimate by curvature when the smallest eigenvalue is negative or near zero while biases are flat. It gives a selection: the variables with the largest eigenvector weight. It gives values: the signs of those entries, relative to one anchor whose sign is arbitrary. Formally, let $\lambda_{\min}$ and $v$ be the smallest eigenvalue and eigenvector of the Hessian $H_t$ at decimation round $t$. When $\max_i |p_i - 1/2| < \epsilon$ or BP fails to converge, and $\lambda_{\min} < \delta$, we fix the set $S$ of the $b$ largest $|v_i|$ to
$$x_i = s \cdot \mathrm{sign}(v_i), \quad i \in S,$$
where $s \in \{\pm 1\}$ is the single free global sign. Otherwise ordinary bias-based decimation proceeds.
The problem-specific pieces are handled as follows. For pairwise models, $H_t$ is the Bethe Hessian evaluated at the current fixed point, with decimated variables removed. For models with higher-order factors, such as parity checks, we instead use the leading eigenvector of the linearized BP message update, since an eigenvalue above one signals the same instability. We aggregate it onto variables by summing incoming message components. Both are sparse, so a few Lanczos or power iterations cost about the same as a few BP sweeps.
Research Program
The work has three parts.
Build. We will implement curvature-guided decimation as a drop-in replacement for the selection step in standard BP-guided decimation. The trigger thresholds $\epsilon$ and $\delta$ and the block size $b$ are its only new hyperparameters.
Analyze. We will analyze the method on one tractable case: the sparse planted two-group model. There, clamping $b$ variables along the Bethe Hessian eigenvector can be tracked as an external field aligned with the informative mode. We will ask whether the overlap after one BP round grows with $b$ faster than for $b$ randomly signed clamps. We expect it to, because random signs project onto the informative mode only through a sum of $b$ random-sign terms, which grows like $\sqrt{b}$. Aligned signs add coherently, which grows like $b$.
Measure. We will track $\lambda_{\min}$ across decimation rounds. This tests a second prediction: stall events and Heskes-style oscillations are preceded by a negative or near-zero eigenvalue in the residual problem, so symmetry can re-emerge after the first decision. If $\lambda_{\min}$ stays comfortably positive after the first clamp, a one-shot method suffices. The iterative part of the proposal then collapses, and we will report that.
Two further questions round out the program. The first is whether clamping along the unstable eigenvector removes the limit cycle on the 4-node Boltzmann machine of Heskes' paper. That paper leaves open how to stabilize such minima without slow double-loop solvers. The second is whether errors fixed along the eigenvector cascade less than bias-based errors near the failure density of Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation.
Baselines
The naive reference is plain BP-guided decimation with bias-based selection. When all biases tie, it breaks ties uniformly at random. This is the procedure in Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation, and it shows what happens with no deliberate symmetry breaking.
The strongest existing decoder baseline is randomized guided decimation (BPGD-rd) from Belief Propagation Decoding of Quantum LDPC Codes with Guided Decimation. It samples from a pool of the most reliable qubits to explore degenerate branches, and it is the closest competitor because it already targets near-symmetric, degenerate stalls. That paper reports that it matches or exceeds BP-OSD-0 on the [[882, 24]] bicycle code and outperforms BP-OSD-0 on [[882, 48, 16]] under depolarizing noise. We found no reported numerical logical error rate on Lacuna for these codes, so we will rerun it.
The strongest one-shot symmetry-breaking baselines come in two forms. One is a Bethe-Hessian spectral initialization followed by ordinary decimation, in the spirit of Approximate Message Passing with Spectral Initialization for Generalized Linear Models. The other is the single-node clamp of Pairwise Clustering and Graphical Models.
For lossy compression, the reference points are the following. BP-guided decimation on uncoupled LDGM codes is the plain version. Spatially coupled BP-guided decimation (Approaching the Rate-Distortion Limit With Spatial Coupling, Belief Propagation, and Decimation) changes the code rather than the decoder. Survey-inspired decimation on random gates is reported "only a few percentage points above the absolute Shannon limit" at $N=1000$, $K=6$ (Lossy Data Compression with Random Gates). No exact distortion figure for BP-guided decimation on uncoupled LDGM codes was found on Lacuna.
The ablations that isolate the key ingredient are three. Block decimation of the same $b$ variables with random signs isolates whether relative signs matter. Block decimation of $b$ random variables with eigenvector-consistent signs isolates whether the choice of variables matters. Single-variable eigenvector clamping ($b=1$) isolates whether blocks matter at all.
All methods share the same budget: identical BP iteration counts per round, the same total number of fixed variables, the same damping setting, and the same hyperparameter grid size, tuned on held-out instances. We report wall-clock time including eigensolves. Beating BPGD-rd means a lower logical error rate at equal wall-clock time on at least two of the listed codes. Beating plain BP-guided decimation on LDGM compression means a smaller gap to the rate–distortion curve at matched rate.
Why not just…?
Why not just damp the messages? Stable Fixed Points of Loopy Belief Propagation Are Local Minima of the Bethe Free Energy proves that damping fixes only step-size-induced non-convergence. It does nothing for intrinsically unstable minima. It also cannot help at a stable uniform fixed point, where BP converges but carries no information. We include damped BP in every arm, so any gain is on top of it.
Why not just clamp a random variable, or use randomized decimation? This is the real threat. In a perfectly symmetric problem the first sign is arbitrary, so a random single clamp may be as good as ours. Our prediction concerns blocks and later rounds. Random signs on $b$ variables align with the informative mode only incoherently. The random-sign block ablation, together with BPGD-rd at equal compute, settles this directly. If eigenvector signs give no gain over random signs at $b > 1$, the proposal fails.
Why not break symmetry once with a spectral warm start and then decimate normally? That works if symmetry never reappears. Degenerate quantum codes and parity-check compression plausibly regenerate near-flat biases in residual subproblems, but this is untested. Our $\lambda_{\min}$ tracking and the one-shot baseline test it. If the one-shot variant matches ours, we will report the simpler method as sufficient.
Why not use a convergent double-loop algorithm? Heskes describes these as slow. More importantly, the uniform point in a symmetric model is a legitimate local minimum, so guaranteed convergence simply lands there. Convergence does not choose among symmetric branches, and choosing among them is the problem here.
Proposed Experiments
Symmetric testbeds. We will run on three families. The first is LDGM lossy compression of binary symmetric sources, at the random-gate setting $N=1000$ and at larger $N$, measuring distortion versus the Shannon limit. The second is quantum LDPC decoding on the bicycle codes [[882, 24]] and [[882, 48, 16]], the hypergraph product code [[1922, 50, 16]], and the A5 code [[180, 10]] from the guided-decimation paper, measuring logical error rate against physical error rate and time. The third is community recovery on the sparse planted partition model and on Karate, Dolphins, Political Blogs, and Adjnoun, measuring overlap. On these graphs we compare against pure Bethe Hessian spectral clustering, which reportedly "noticeably outperformed" the non-backtracking approach on Dolphins and Adjnoun (Spectral Clustering of graphs with the Bethe Hessian).
Negative control. Random 4-SAT is not sign-symmetric, so biases are rarely flat. The curvature trigger should almost never fire, and success probability should match plain BP-guided decimation, including its decline near the predicted $\alpha_{spin}(4) \approx 8.05$ reported in Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation. A gain here would indicate that we are measuring something other than symmetry breaking.
Decisive checks. Three results decide the proposal's fate. First, the eigenvector-sign block must beat the random-sign block at matched $b$ on the planted partition model and on LDGM compression; otherwise the core claim is false. Second, the gain must be concentrated in rounds where $\lambda_{\min} < \delta$, and it must be larger than the one-shot spectral baseline on the degenerate quantum codes; otherwise iteration is unnecessary. Third, curvature-guided clamping must eliminate the limit cycle on Heskes' 4-node Boltzmann machine, where bias-based clamping does not.
References
- Stable Fixed Points of Loopy Belief Propagation Are Local Minima of the Bethe Free Energy
- Spectral Clustering of graphs with the Bethe Hessian
- Community detection with the Bethe-Hessian
- Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
- Lossy Data Compression with Random Gates
- Belief Propagation Decoding of Quantum LDPC Codes with Guided Decimation
- Approximate Message Passing with Spectral Initialization for Generalized Linear Models
- Pairwise Clustering and Graphical Models
- Approaching the Rate-Distortion Limit With Spatial Coupling, Belief Propagation, and Decimation