Why Message Passing Fails on Biased Lossy Codes, and Stochastic Localization as a Fix

A neat way to compress a biased stream of bits (say 80% ones) is to store a short string of fair, random-looking bits and let a fixed nonlinear decoder expand it. Each output bit is +1 when a random projection of the stored string lands inside a band of width $k$ around zero, and −1 otherwise. Replica calculations show this "non-monotonic perceptron" code reaches Shannon's rate-distortion limit (Statistical mechanics of lossy data compression using a nonmonotonic perceptron). The difficulty is the encoder: finding the stored string that reproduces a given source sequence well. The practical encoder is belief propagation (BP), an iterative algorithm that passes local probability estimates around a graph. It needs an ad hoc "inertia" momentum term and a hard stop at 35 iterations. It tracks the Shannon curve at source bias $p=0.8$ and fails at $p=0.2$, even though the two sources have the same entropy (Statistical mechanical approach to lossy data compression: Theory and practice, Statistical mechanical evaluation of error exponents for lossy data compression).

The proposal makes two claims. The first is that this "bias paradox" is a spectral instability question. Because the decoder is mirror-symmetric, it treats a stored string and its negation identically, so BP starts at a fixed point where every bit is a 50/50 guess. Inertia can only amplify an escape direction that the dynamics already make unstable. Whether such a direction exists is set by the top eigenvalue of a weighted random matrix, and that eigenvalue depends on whether the band encodes the majority or the minority symbol. The second claim is that stochastic localization removes the need for the inertia heuristic. Stochastic localization is the discrete-spin version of a diffusion model, a generator that turns noise into samples step by step. It slowly adds a noisy external field until each bit is decided, which breaks the mirror symmetry at a commitment time that the same spectral quantity predicts. This mirrors "speciation" in image diffusion models.

Core Claim

Write the encoder's target as a Gibbs measure over stored strings $\mathbf s\in\{-1,+1\}^N$ that penalizes Hamming mismatches between the source bits $y^\mu$ and the reconstructions $f_k(\mathbf s\cdot\mathbf x^\mu/\sqrt N)$, at inverse temperature $\beta$, with $\alpha=M/N=1/R$ source bits per stored bit. Since $f_k(u)=f_k(-u)$, the output channel is even in $u$. Its first-order message vanishes at zero magnetization, and the linearized approximate message passing (AMP) update around the all-zero state is governed by the curvature $g_\beta(y)=\partial^2_\omega \log Z_{\rm out}(y,\omega,V)\big|_{\omega=0}$ of the output log-partition function. Here $\omega$ is the cavity mean of the projection, $V$ its variance, and $Z_{\rm out}$ the channel's normalizer. By analogy with the weak-recovery analysis of symmetric channels in generalized linear models (Phase Transitions, Optimal Errors and Optimality of Message-Passing in Generalized Linear Models), where GAMP is stuck at zero correlation below $\alpha=0.5$ for sign-less observations, we expect the uninformative point to be unstable exactly when

$$ \alpha\,\mathbb E_{y}\!\left[g_\beta(y)^2\right] > 1 , $$

with the expectation taken over the source distribution, a fraction $p$ of $+1$ symbols. This is equivalent to a BBP-type eigenvalue of $D=\tfrac1N\sum_\mu g_\beta(y^\mu)\,\mathbf x^\mu\mathbf x^{\mu\top}$ separating from its bulk.

Swapping $p\to1-p$ does not map the band decoder onto itself. It maps it onto an "anti-band" decoder $\text{sign}(|u|-k)$ with a different threshold. The curvatures, and therefore the left side of the condition, differ between the two cases. The prediction is falsifiable: inertia-BP stalls exactly in the $(p,R)$ region where the condition fails. In that region the inertia term has nothing to amplify. The 35-iteration non-convergence should concentrate near the boundary, where the instability is weak.

Under stochastic localization each bit additionally receives a field $\mathbf h_t = t\,\mathbf s^\star + \mathbf W_t$, where $\mathbf s^\star$ is the eventual sample and $\mathbf W_t$ is Brownian motion. AMP estimates the conditional mean, and that mean is the drift. As $t$ grows the effective prior variance shrinks, and the trivial point loses stability at a predicted time $t_S$. This is the discrete analogue of the spectral speciation time $\Lambda e^{-2t_S}=1$ in Dynamical regimes of diffusion models and of the Mexican-hat bifurcation in Spontaneous symmetry breaking in generative diffusion models. In the localization process, the random field supplies the symmetry-breaking that inertia supplies by hand, and the process ends at a fixed time horizon instead of an arbitrary iteration cutoff.

Relation to Prior Work

The method we reuse comes from Sampling through Algorithmic Diffusion in non-convex Perceptron problems. That paper runs algorithmic stochastic localization with an AMP-estimated drift to sample perceptron solutions. It predicts success from the unimodality of a free-entropy curve over the overlap between two independent samples. It finds that uniform diffusion fails on binary perceptrons because of an overlap gap, and it repairs this with a $-\log$ stability tilt, reaching $\alpha_{alg}\approx0.65$ against capacity $\alpha_c\approx0.83$. That work addresses zero-error constraint satisfaction with monotonic constraints. We apply the same machinery to a rate-distortion objective with a non-monotonic, mirror-symmetric channel. The symmetry-breaking question there, which bit-sign mode to commit to, is absent from their setting.

The inertia-BP papers motivate the project. They supply the open paradox and the convergence failure, and they offer no mechanism for either. Lossy Data Compression with Random Gates constrains our design. It shows that destroying symmetry structurally, with random nonlinear gates and survey-inspired decimation, works on unbiased sources, but at $2^K$ cost per gate. We keep the cheap perceptron decoder and break symmetry dynamically instead.

The diffusion-compression systems Lossy Compression with Gaussian Diffusion and Lossy Compression with Pretrained Diffusion Models use diffusion on the decoder side, to reconstruct continuous images from reverse-channel-coded noisy samples. We use diffusion on the encoder side, as a search over discrete codewords.

U-Nets as Belief Propagation links BP to diffusion denoisers only on trees, where symmetry traps cannot arise. That paper is a reminder that our dense, loopy setting is exactly where the link has not been tested.

Research Program

The theory step computes $g_\beta(y)$ in closed form for the band and anti-band decoders. Since $u$ is Gaussian given $\omega,V$, $Z_{\rm out}$ is a difference of Gaussian tail integrals. From this we derive the instability boundary $R_c(p,\text{orientation},\beta)$ and the localization commitment time $t_S(p,R)$. We will then write the state evolution of localization-driven AMP. Following the double-replica analysis of the stochastic-localization paper above, we compute the two-sample overlap free entropy along the localization path to check whether an overlap gap appears. If it does, we will test whether the dense-cluster tilt transfers to the distortion objective.

The algorithm step implements stochastic localization with an AMP drift for the non-monotonic perceptron. Each step costs $O(MN)$ for dense Gaussian $\mathbf x$, like inertia-BP. The algorithm rounds $\mathbf s$ at the horizon, and its tunable parameters are $\beta$, the time grid, and an optional tilt. We will also implement the simplest spectral competitor: initialize AMP at the top eigenvector of $D$, which is the analogue of spectral initialization in phase retrieval.

Baselines

The naive reference point has two parts. The first is the zero-rate reconstruction that outputs the majority symbol everywhere, with distortion $\min(p,1-p)$. The second is AMP/BP on the same factor graph with no inertia, started from tiny random messages. This shows how often the symmetric trap actually captures the dynamics.

The strongest existing method on this exact question is inertia-BP from Statistical mechanical approach to lossy data compression: Theory and practice. It is the only published polynomial-time encoder for this code, and it is reported to beat prior information-theory results for $p=0.5$ at $R\le0.4$. No reported numerical result is found on Lacuna for its distortion at $p=0.8$ or $p=0.2$; the source gives only a figure, described as "closely tracked" and "failed to track" respectively. We will therefore reimplement it at $N=500$ and $N=1000$ with the published 35-iteration cutoff. We will also run a version whose inertia coefficient $\gamma$ and iteration budget are tuned on held-out source draws, using the same tuning budget and wall-clock as our method. Beating it means a lower mean distortion gap to $H_2(p)-H_2(D)$ across a rate grid, at matched compute, on identical random matrices and source sequences, with the improvement holding in both decoder orientations.

A second strong baseline is the orientation-flip trick. For $p<0.5$, the encoder negates the source and the decoder negates its output, so a $p=0.2$ source is coded as a $p=0.8$ source with the anti-band decoder. Each method is run in its better orientation. Third, spectral-initialized damped AMP with the same budget. Fourth, survey-inspired decimation with $K=6$ random gates. On unbiased sources it is reported at "only a few percentage points above the absolute Shannon limit" at $N=1000$ (Lossy Data Compression with Random Gates), which gives an unbiased-source target to match at $p=0.5$.

Two ablations isolate the ingredients. The first replaces the Brownian term with a deterministic, sign-of-current-mean field ramp. This is reinforcement without randomness, and it tests whether the random field matters. The second removes the tilt.

Why not just…?

Why not just flip the bits when $p<0.5$? This does fix the paradox operationally, and we treat it as a baseline rather than argue against it. What it does not provide is a rule for which orientation works at which rate. Our theory predicts that the good orientation can change with $R$, and that even the $p=0.8$ band decoder should stall above some $R_c$. If flipping plus inertia-BP matches localization everywhere on the grid, the encoder contribution collapses, and the remaining value is the predictive spectral theory. The experiments report that outcome plainly.

Why not just use a spectral initialization? This is the most serious threat, because the theory itself says the escape direction is the top eigenvector of $D$. Spectral initialization fixes the start of the run but not the oscillations that forced the 35-iteration cutoff. In the region where the trivial point is stable, the eigenvector carries little information, and AMP can relax back toward zero. The head-to-head comparison over the $(p,R)$ grid settles this. Localization must win specifically near and beyond $R_c$ to justify itself.

Why not just run simulated annealing or MCMC on $\mathbf s$? Annealing is generic and also breaks symmetry through noise, but its cost is many sweeps of $O(MN)$ updates with no asymptotic prediction of success. The stochastic-localization paper found that plain uniform diffusion fails on binary perceptrons and needed tilting even for its annealing-based MCMC. We include tuned annealing at matched wall-clock to measure this directly.

Why not just use random-gate codes? They avoid the trap by design, but their cost grows as $2^K$. The file reports them only for unbiased sources, and linear-style gates wash out bias. Matching them at $p=0.5$ while also handling biased sources at perceptron cost is the bar we set.

Proposed Experiments

All experiments use synthetic binary memoryless sources at $p\in\{0.1,0.2,0.3,0.5,0.7,0.8,0.9\}$, rates on a grid in $[0.1,0.9]$, and $N\in\{500,1000,4000,16000\}$, with 50 independent matrix and source draws per cell. We report the distortion gap to the rate-distortion function, the fraction of runs reaching a fixed point, wall-clock time, and the empirical overlap between independent localization runs.

The first decisive check tests the theory. Over the $(p,R)$ grid, the region where inertia-free AMP leaves the zero state should match the predicted instability condition, and the reproduced $p=0.2$ failure of inertia-BP should fall inside the predicted stable region for the band orientation. If the observed stall boundary does not move with $\mathbb E[g_\beta^2]$, the spectral explanation is wrong.

The second check tests whether the dynamics match the prediction. The time at which localization trajectories commit to a sign mode, measured as the jump in $|\mathbf m_t\cdot\mathbf v_1|$ where $\mathbf v_1$ is the top eigenvector, should match $t_S(p,R)$ and scale correctly with $N$.

The third check compares performance. Localization must beat tuned inertia-BP and spectral AMP at matched compute in both orientations. Its gap should shrink with $N$, as state evolution predicts, rather than plateau.

The fourth check concerns failure modes. If the independent-run overlap shows a gap, the tilted variant must close it, or we report that this rate-distortion problem has a frozen landscape like the binary perceptron. That outcome would itself bound what any diffusion-style encoder can achieve here.