Commitment Instantons: Predicting and Removing the Error Floor of Decimation Decoders

Decimation decoders run message passing, permanently fix the most confident bits, simplify the graph, and repeat. They now match much more expensive decoders on quantum and short classical codes. Belief propagation (BP) is the standard message-passing algorithm that estimates each bit's probability by exchanging local messages on the code's graph. But decimation adds a failure mode plain BP does not have: a single wrong commitment made early can never be undone. Nobody currently knows how often that happens at the very low noise levels where these decoders would actually be used. Monte Carlo simulation cannot reach those error rates, and the existing theory tracks average behaviour, not rare failures.

We propose to compute, for a given code and decimation rule, the commitment instanton. This is the smallest channel-noise pattern that tricks the decoder into permanently fixing a bit to the wrong value. Its size sets the exponential slope of the error floor, and the number of near-minimal patterns sets its height. The decoder is already a spin system: bits are spins, parity checks are multi-spin couplings, and channel outputs are local magnetic fields. Finding the least-cost noise that pushes the decimation trajectory into a wrong commitment is therefore a constrained energy-minimization problem, and it can be solved with gradients through the unrolled decoder. The result is a way to predict the error floors of decimation decoders, to choose decimation schedules that push those floors down, and to generate rare-failure training data without brute-force sampling.

Core Claim

At high signal-to-noise ratio (SNR), the frame error rate of a decimation decoder is dominated by a small family of noise directions that cause an irreversible misdecimation. These directions differ from the trapping sets that dominate plain BP. Take an additive white Gaussian noise (AWGN) channel with noise variance $\sigma^2$, and let $w_{\text{eff}}$ be the smallest Euclidean norm of a noise vector that makes the decimation decoder commit a wrong bit it cannot recover from. Then

$$ P_{\text{fail}}(\sigma) \approx K \exp\!\left(-\frac{w_{\text{eff}}^2}{2\sigma^2}\right), $$

where $K$ counts the near-minimal failure patterns. The form follows from the Laplace approximation of a Gaussian tail around its closest failure point, which is the large-deviation "least-cost path" picture. On the binary symmetric channel with flip probability $p$, the analogue is $P_{\text{fail}} \approx K p^{t_{\text{eff}}}$, where $t_{\text{eff}}$ is the minimum number of flips that causes a wrong commitment.

The claim has three parts, and each is new. First, $w_{\text{eff}}$ and $K$ can be found by optimization, and every candidate the search returns can be checked by running the exact decoder. Second, decimation rules can be ranked by $w_{\text{eff}}$ instead of by simulated waterfall curves. Third, noise sampled around commitment instantons is a far cheaper source of rare-failure training data than Monte Carlo harvesting.

Relation to Prior Work

The spin mapping supplies the method. Finite-connectivity systems as error-correcting codes shows that maximum a posteriori decoding is finding the ground state of a disordered spin Hamiltonian. Approaching the Rate-Distortion Limit With Spatial Coupling, Belief Propagation, and Decimation uses the cavity method to analyze BP-guided decimation for lossy compression. That paper explicitly states that tracking the statistics of the decimated graph rigorously is open. Its analysis concerns typical, average behaviour. We do not attempt the average-case tracking it leaves open; we look instead at the rare, worst-case trajectories that analysis ignores. The large-deviation idea that a rare failure follows a single least-cost deterministic path comes from the continuous-time "skeleton equation" constructions in Large deviation principle for slow-fast systems with infinite-dimensional mixed fractional Brownian motion. We use only the variational principle from that work, not its stochastic calculus. The discrete decoder turns the skeleton into a finite optimization over noise vectors.

Three decoding papers motivate the gap. Belief Propagation Decoding of Quantum LDPC Codes with Guided Decimation fixes the most reliable qubit whenever BP fails to converge. It matches BP-OSD-0 and BP-SI without their cubic-cost matrix inversion, but it chooses hyperparameters by trial and error and has no account of its failures. Learned Decimation for Neural Belief Propagation Decoders branches on the least reliable bits and then uses a small network to "nudge" bits toward their values. It picks branching bits from local reliability thresholds rather than from any analysis of which configurations actually cause failure, and its best configurations cost up to 18 times as much as BP. Boosting Learning for LDPC Codes to Improve the Error-Floor Performance trains a post-decoder only on words the base decoder failed to correct. It notes that collecting such words at very low error rates is the bottleneck. Our instanton search attacks that bottleneck directly.

One line of prior work constrains the design. Large Deviation Methods for Approximate Probabilistic Inference obtains rigorous large-deviation bounds only for dense two-layer networks with weak couplings. Nothing in the file gives rigorous rate functions for loopy sparse graphs under decimation. We therefore do not claim a proven large deviation principle. Our quantity $w_{\text{eff}}$ is an empirically certified upper bound: any noise vector the search finds really does cause failure. The resulting estimate of the error rate is validated wherever Monte Carlo can reach.

Research Program

The first component is a differentiable surrogate of the decimation decoder. We unroll BP-guided decimation for a fixed number of rounds. The hard "pick the most confident bit" step is replaced by a softmax over reliabilities at temperature $\tau$, and the hard clamp by a large but finite field. The surrogate is used only to compute gradients. Every candidate noise vector is then passed through the exact, non-relaxed decoder.

The second component is the commitment-instanton search. The objective is to minimize $\|n\|$ over channel-noise vectors $n$ such that some decimated bit is fixed to the wrong sign and the final output is wrong. We impose this constraint with a penalty on the surrogate's wrong-commitment margin. We then refine each solution by bisection along its direction using the exact decoder, which gives a verified failure boundary. Restarts are seeded in three ways: at random, at known low-weight codewords, and at the failure words of plain BP.

For each verified instanton we record two labels. The first is whether plain BP with the same total iteration budget, or BP-OSD, would have decoded that noise correctly. That tells us whether the failure is caused by decimation. The second is the decimation step at which the wrong commitment happened. Clustering the instantons by the set of bits involved gives the multiplicity $K$.

The third component uses the instantons. For estimation, we run importance sampling with a mixture of Gaussians centred on the instantons, which yields floor estimates with confidence intervals. For design, we sweep decimation hyperparameters and pick the setting with the largest $w_{\text{eff}}$. These hyperparameters are the number of BP iterations before each decimation, how many bits are fixed per round, and the reliability threshold. For training, we replace Monte Carlo-harvested failures in the boosting pipeline with instanton-centred samples.

Classical codes come first, on the CCSDS (128, 64) code and on WiMAX, WiFi, and 5G NR LDPC codes. Quantum codes come second, on the [[882, 24]] and [[882, 48]] generalized bicycle codes and the [[1922, 50, 16]] hypergraph product code. There the noise is discrete, so the search runs over the binary symmetric channel or depolarizing flips using the relaxed-then-rounded procedure.

Baselines

The naive reference point is brute-force Monte Carlo followed by straight-line extrapolation of the log error rate from the lowest SNR it reaches. For estimation, we give it the same GPU-hours as our search plus importance sampling. We beat it if our estimate agrees with a long, independent Monte Carlo run at a held-out higher SNR within its confidence interval while the extrapolation does not, or if we reach the same interval width at a small fraction of the compute.

The strongest design competitor on short classical codes is NBP-D from Learned Decimation for Neural Belief Propagation Decoders. It reports a 0.75 dB gain over neural BP at a block error rate of $10^{-4}$ on CCSDS (128, 64), coming within 1 dB of maximum-likelihood decoding, at up to 18 times BP complexity. Our instanton-tuned, non-branching decimation decoder will be compared at matched complexity, counted in message-passing operations. We beat NBP-D if we match its $10^{-4}$ point at lower complexity, or if we sit below it at $10^{-6}$ and beyond, measured by instanton importance sampling cross-checked with Monte Carlo.

On standard LDPC codes the strongest competitor is the boosted neural min-sum decoder of Boosting Learning for LDPC Codes to Improve the Error-Floor Performance. It reports a frame error rate more than two orders of magnitude below weighted min-sum at the onset of the floor, using 50 iterations against 150 for post-processing. We rerun its pipeline with the same architecture, number of training examples, and iterations, changing only where the post-decoder's training words come from. We beat it if instanton-sourced training reaches the same or a lower floor with at least an order of magnitude less data-generation compute.

On quantum codes the reference is BPGD from Belief Propagation Decoding of Quantum LDPC Codes with Guided Decimation, together with its randomized variant and BP-OSD-0. No numerical logical error rates were reported on Lacuna for BPGD on these codes, so we will reproduce all three ourselves.

The key ablation seeds and trains using instantons of plain BP instead of commitment instantons, keeping everything else fixed. If that works equally well, the decimation-specific part of the idea adds nothing.

Why not just…?

Why not just use BP-OSD or stabilizer inactivation and ignore decimation failures? These decoders pay cubic cost in block length for Gaussian elimination, and BPGD already matches their accuracy at linear cost per round, according to Belief Propagation Decoding of Quantum LDPC Codes with Guided Decimation. The open question is whether BPGD keeps that parity deep in the floor. OSD therefore serves in this proposal as a reference, not a replacement. If commitment instantons show that BPGD's $w_{\text{eff}}$ is below OSD's, that is a useful negative result for anyone planning to build decimation hardware.

Why not just harvest failures by Monte Carlo and boost, as Kwak et al. do? That approach works, but the paper itself names harvesting at very low error rates as its bottleneck. The data-source ablation above measures this directly. There is a real threat: if failures at the onset of the floor are common enough to harvest cheaply, our advantage appears only deeper in the floor. We will report the crossover SNR honestly.

Why not just run existing trapping-set or instanton analysis for plain BP? This is the most serious alternative. If misdecimations mostly happen on BP's own trapping sets, then decimation introduces no new failure mode and BP-level analysis is enough. The labelling step answers the question by measuring what fraction of verified failures plain BP or OSD would have corrected, together with the BP-seeded ablation. If that fraction is small, we will reframe the work as instanton estimation for decimation decoders rather than as a claim about new failure modes.

Why not just extrapolate the waterfall curve? Error floors are exactly where the slope of the log error rate changes, so straight-line extrapolation is known to fail there. The held-out high-SNR Monte Carlo check shows whether the instanton prefactor fixes this.

Decisive Checks

The first check is agreement. On CCSDS (128, 64), and on one WiFi LDPC code at SNRs where a Monte Carlo run of about $10^9$ frames resolves the error rate, the instanton estimate must match within a factor of three and have the right slope. If it misses badly, the gradient search is failing to find the smallest instantons, or the multiplicity is too large for a leading-term estimate. Either outcome would be informative, but it would sink the estimation claim.

The second check is design transfer. Across a sweep of decimation settings, the ranking by $w_{\text{eff}}$ must predict the ranking by measured floor.

The third check is the ablation: commitment instantons must beat plain-BP instantons as training seeds. If they do not, the decimation-specific mechanism is not what matters.