Certified Adaptive List Decoding for Error-Correcting Codes

Jaeho Hwang; Byung-Sun Won; Uiwon Hwang

cs.ITOct 20, 2026

Certified Adaptive List Decoding for Error-Correcting Codes

Authors: Jaeho Hwang, Byung-Sun Won, Uiwon Hwang

Organizations: Human-Centered Artificial Intelligence Research Institute, Ewha Womans University · Institute of Mathematical Sciences, Ewha Womans University · Department of Computer Science and Engineering, Ewha Womans University

Abstract

Maximum-likelihood (ML) decoding of linear block codes is NP-hard, so neural decoders are evaluated by how closely they approach it. We observe that proving a candidate optimal can be far easier than finding it, and build a decoder that does both. We cast decoding as a search over an absorbing-state discrete diffusion model, whose sequential commitment of coordinates turns generation into a tree, and run a probability beam search over it. A dual bound from a linear-programming relaxation and a distance-based test, both derived from the code, then certify per frame that the current candidate is the global ML solution; because both are theorems, certified frames incur no accuracy-computation trade-off. Across $15$ codes and five operating points we certify up to $99.9\%$ of frames, the two tests dividing the space as their derivations predict, one strong for sparse parity-check matrices and the other for codes with a large minimum distance. Certification also behaves as a per-frame reliability signal, with $96.7$ - $100\%$ of all frame errors falling on uncertified frames. Against an exact ML reference at $5$ dB the decoder is within one standard deviation on three of the four codes where the reference is uncensored, and against four neural baselines it attains the best bit-error rate in $71$ of $75$ cells.

Figures & tables

Figure 1: Overview of the proposed CAL-ECC.

Code	$(n,k)$	ECCT			CrossMPT			DDECC			SB-ECC			CAL-ECC $10^{-1}$			CAL-ECC $10^{-2}$			CAL-ECC $10^{-3}$
Code	$(n,k)$	4	5	6	4	5	6	4	5	6	4	5	6	4	5	6	4	5	6	4	5	6
BCH	(31,16)	5.90	7.81	10.34	7.00	9.35	12.36	4.80	6.13	7.67	7.29	9.81	12.90	6.61	8.93	11.83	7.19	9.56	12.47	7.48	9.89	13.04
	(63,36)	4.66	6.51	9.18	4.79	6.75	9.45	5.30	7.29	9.98	5.52	7.55	10.49	5.36	7.62	10.71	6.44	8.78	12.00	7.43	10.16	13.53
	(63,45)	5.33	7.46	10.41	5.31	7.53	10.50	5.77	7.95	10.54	6.29	9.01	12.54	6.04	8.46	11.86	7.12	9.74	13.01	7.82	10.86	14.49
	(63,51)	5.43	7.45	10.50	5.64	7.89	11.17	5.25	7.14	9.25	5.50	7.64	10.79	6.22	8.78	12.27	6.65	9.38	12.89	6.80	9.63	13.28
Polar	(64,32)	6.63	9.04	11.89	7.63	10.26	13.29	7.05	9.50	12.23	7.52	10.15	13.26	7.61	10.30	13.67	7.89	10.58	13.89	7.97	10.67	13.96

Table 1: Decoding accuracy,

-\ln(\mathrm{BER})

E_{b}/N_{0}\in\{4,5,6\}

dB (higher is better). Per cell the best entry is bold and underlined and the runner-up underlined . The

2

–

3

dB columns are in Appendix F .

Code	(a) generator		(b) $+$ search		(c) $+$ certificates		effect		(c)/(a)
Code	$-\ln\mathrm{BER}$	NFE	$-\ln\mathrm{BER}$	NFE	$-\ln\mathrm{BER}$	NFE	search	cert.	NFE
							$\Delta$ BER	NFE cut	ratio
MacKay $(96,48)$	$8.76$	$53.8$	$10.26$	$54.7$	$10.31$	$23.1$	$+1.50$	$2.4\times$	$\bm{0.43\times}$
LDPC $(121,80)$	$8.72$	$88.4$	$10.65$	$92.4$	$10.58$	$29.0$	$+1.93$	$3.2\times$	$\bm{0.33\times}$
BCH $(63,45)$	$5.82$	$45.2$	$7.81$	$149.7$	$7.82$	$113.8$	$+1.99$	$1.3\times$	$2.52\times$
Polar $(128,64)$	$6.37$	$82.9$	$7.67$	$171.8$	$7.61$	$156.4$	$+1.30$	$1.1\times$	$1.89\times$

Table 2: Ablation at

E_{b}/N_{0}=4

dB,

\tau=10^{-3}

: (a) the generator decoded greedily along a single trajectory (

\tau{=}1

L{=}1

); (b) the full beam search with certificates disabled; (c) the complete decoder. “search

\Delta

BER” is (b)

-

(a) in

-\ln(\mathrm{BER})

and “cert. NFE cut” is (b)/(c) in NFE.

Panel of Figure 2 — Figure 2: FER against the exact ML reference (grey) over the $E_{b}/N_{0}$ range where it exists; the shaded region below it is unachievable by any decoder. CAL-ECC curves darken as $\tau$ decreases.

Code	row wt. $H$	$\mathrm{cert}\%$	$[\mathrm{D}]\%$	$[\mathrm{M}]\%$	uncert.%	detected	errors there	selectivity
MacKay $(96,48)$	$6$	$59.5$	$59.2$	$0.0$	$40.5$	$38.1\%$	$98.8\%$	$2.5\times$
LDPC $(49,24)$	$7$	$81.3$	$15.1$	$60.9$	$18.7$	$7.0\%$	$98.9\%$	$5.3\times$
BCH $(31,16)$	$8$	$89.2$	$0.5$	$70.6$	$10.8$	$1.7\%$	$96.7\%$	$9.3\times$
CCSDS $(128,64)$	$8$	$41.0$	$40.9$	$0.0$	$59.0$	$100.0\%$	$100.0\%$	$1.7\times$
LDPC $(121,70)$	$11$	$63.0$	$62.5$	$0.0$	$37.0$	$92.8\%$	$100.0\%$	$2.7\times$
LDPC $(121,80)$	$11$	$72.4$	$70.9$	$0.0$	$27.6$	$66.7\%$	$100.0\%$	$3.6\times$

Table 3: Certificate breakdown at

E_{b}/N_{0}=4

dB,

\tau=10^{-3}

, sorted by the row weight of

H

[\mathrm{D}]

and

[\mathrm{M}]

are the fractions certified by each test;

\mathrm{cert}\%

additionally includes frames with

\bm{s}=\bm{0}

. “detected” is the share of frame errors whose output fails the syndrome check, “errors there” the share falling in the uncertified fraction, and selectivity the bound

1/(1-\mathrm{cert})

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Code	$\tilde{d}$	Source
BCH $(31,16)$	$7$	exhaustive over $2^{16}$ (exact $d_{\min}$ )
BCH $(63,36)$	$11$	BCH bound
BCH $(63,45)$	$7$	BCH bound
BCH $(63,51)$	$5$	BCH bound
Polar $(64,32)$	$8$	$\min_{i\in\mathcal{A}}2^{\mathrm{wt}(i)}$
Polar $(64,48)$	$4$	$\min_{i\in\mathcal{A}}2^{\mathrm{wt}(i)}$

Appendix

Table 4: Distance bounds

\tilde{d}\leq d_{\min}

used by Certificate M. Codes not listed have no proven bound available and the certificate is disabled for them.

Code	dB	$\mathrm{NFE}_{\mathrm{sd}}$				ours, $\tau{=}10^{-3}$		$\mathrm{cert}\%$
Code	dB	SB-ECC	$10^{-1}$	$10^{-2}$	$10^{-3}$	NFE	$p_{99}$	$\mathrm{cert}\%$
BCH $(63,45)$	6	$0.55$	$0.4$	$0.5$	$0.5$	$0.7$	$1$	$99.8$
LDPC $(121,80)$	6	$1.12$	$0.7$	$0.7$	$0.7$	$1.2$	$1$	$99.5$
LDPC $(121,70)$	6	$1.38$	$0.9$	$0.9$	$0.9$	$1.6$	$1$	$99.2$
Polar $(64,48)$	6	$0.47$	$0.4$	$0.4$	$0.4$	$1.9$	$58$	$97.3$
MacKay $(96,48)$	6	$1.66$	$0.9$	$0.9$	$0.9$	$2.7$	$55$	$96.6$

Appendix

Table 5: Computation, measured under two stopping rules.

\mathrm{NFE}_{\mathrm{sd}}

counts evaluations until the first syndrome-consistent candidate, which is the rule SB-ECC uses, whose realised cost we measure rather than assume.

\mathrm{NFE}

is our actual cost, which continues until optimality is proved . Sorted by

\mathrm{cert}\%

. Under SB-ECC’s own rule we are cheaper where certification is high, except on dense

H

, where reaching a syndrome-consistent candidate is itself slow. Table 8 gives every cell.

Code	$2$ dB	$3$ dB	$4$ dB	$5$ dB	$6$ dB
BCH $(31,16)$	$4.41$	$3.27$	$2.29$	$1.48$	$0.86$
BCH $(63,36)$	$6.14$	$4.28$	$2.72$	$1.68$	$0.99$
BCH $(63,45)$	$5.17$	$3.19$	$1.83$	$1.05$	$0.55$
BCH $(63,51)$	$5.63$	$3.42$	$1.70$	$0.81$	$0.36$
Polar $(64,32)$	$5.88$	$4.50$	$3.31$	$2.32$	$1.50$
Polar $(64,48)$	$3.68$	$2.46$	$1.57$	$0.91$	$0.47$

Appendix

Table 6: Realised NFE of SB-ECC with its own syndrome stopping rule enabled. The nominal budget of

10

is an upper bound that is rarely reached, and we use these values wherever SB-ECC’s cost appears.

Code	$2$ dB			$3$ dB			$4$ dB			$5$ dB			$6$ dB
Code	cert	$[\mathrm{D}]$	$[\mathrm{M}]$	cert	$[\mathrm{D}]$	$[\mathrm{M}]$	cert	$[\mathrm{D}]$	$[\mathrm{M}]$	cert	$[\mathrm{D}]$	$[\mathrm{M}]$	cert	$[\mathrm{D}]$	$[\mathrm{M}]$
BCH $(31,16)$	$50.4$	$1.0$	$45.6$	$72.5$	$0.9$	$62.8$	$89.2$	$0.5$	$70.6$	$97.5$	$0.1$	$64.6$	$99.7$	$0.0$	$48.4$
BCH $(63,36)$	$31.4$	$0.0$	$31.1$	$62.4$	$0.0$	$60.9$	$88.8$	$0.0$	$83.4$	$98.6$	$0.0$	$82.5$	$99.9$	$0.0$	$64.8$
BCH $(63,45)$	$24.7$	$0.1$	$23.2$	$54.5$	$0.1$	$49.4$	$83.7$	$0.1$	$68.0$	$97.3$	$0.0$	$62.8$	$99.8$	$0.0$	$41.6$
BCH $(63,51)$	$22.3$	$0.7$	$18.7$	$49.9$	$1.0$	$39.0$	$79.6$	$0.7$	$53.6$	$95.7$	$0.3$	$48.2$	$99.6$	$0.0$	$29.2$
Polar $(64,32)$	$5.1$	$0.1$	$4.9$	$18.4$	$0.1$	$17.8$	$45.7$	$0.1$	$43.1$	$77.4$	$0.1$	$68.8$	$95.4$	$0.0$	$72.9$

Appendix

Table 7: Certification across all cells at

\tau=10^{-3}

\mathrm{cert}

is the fraction of frames proved globally ML, while

[\mathrm{D}]

and

[\mathrm{M}]

are the parts attributed to each certificate, and the remainder of

\mathrm{cert}

is the

\mathrm{skip}_{0}

fraction with

\bm{s}=\bm{0}

. Frames stopped by beam exhaustion are not counted. All figures are percentages.

Code	$2$ dB			$3$ dB			$4$ dB			$5$ dB			$6$ dB
Code	$\mathrm{sd}$	NFE	$p_{99}$	$\mathrm{sd}$	NFE	$p_{99}$	$\mathrm{sd}$	NFE	$p_{99}$	$\mathrm{sd}$	NFE	$p_{99}$	$\mathrm{sd}$	NFE	$p_{99}$
BCH $(31,16)$	$14.8$	$213.8$	$1733$	$6.6$	$61.4$	$1109$	$2.2$	$11.8$	$346$	$0.8$	$2.0$	$22$	$0.5$	$0.6$	$1$
BCH $(63,36)$	$1599.8$	$2521.7$	$5728$	$519.1$	$963.8$	$4432$	$95.7$	$191.1$	$3062$	$9.4$	$17.4$	$545$	$1.0$	$1.1$	$1$
BCH $(63,45)$	$572.3$	$1960.6$	$4651$	$203.6$	$657.0$	$3298$	$37.3$	$113.8$	$2086$	$3.6$	$9.7$	$168$	$0.5$	$0.7$	$1$
BCH $(63,51)$	$70.8$	$1439.1$	$3798$	$28.4$	$421.2$	$2503$	$7.1$	$65.3$	$1300$	$1.2$	$6.2$	$72$	$0.3$	$0.6$	$1$
Polar $(64,32)$	$56.6$	$375.8$	$5578$	$11.1$	$89.1$	$1032$	$2.1$	$32.6$	$109$	$1.0$	$13.1$	$59$	$0.8$	$3.3$	$58$

Appendix

Table 8: Computation across all cells at

\tau=10^{-3}

\mathrm{NFE}_{\mathrm{sd}}

counts evaluations until the first syndrome-consistent candidate, which is the stopping rule SB-ECC uses.

\mathrm{NFE}

continues until optimality is proved, and

p_{99}

is the

99

th percentile of the per-frame NFE.

$\mathrm{cert}\%$ at $\tau=10^{-3}$	cells	median cost	range
$>95\%$	$17$	$1.06\times$	$1.00$ – $8.61\times$
$80$ – $95\%$	$12$	$1.02\times$	$1.00$ – $19.87\times$
$50$ – $80\%$	$15$	$1.28\times$	$1.00$ – $27.93\times$
$<50\%$	$31$	$8.74\times$	$1.08$ – $48.85\times$

Appendix

Table 11: Cost of lowering

\tau

from

10^{-1}

10^{-3}

, grouped by certification rate over all

75

cells.

Code	undetected errors	flag%	certificate	$\Phi$ threshold	NFE threshold
BCH $(31,16)$	$573$	$10.8$	$96.7\%$	$88.5\%$	$96.9\%$
BCH $(63,51)$	$565$	$20.4$	$97.3\%$	$91.7\%$	$97.3\%$
LDPC $(49,24)$	$490$	$18.7$	$98.8\%$	$95.7\%$	$98.8\%$
MacKay $(96,48)$	$310$	$40.5$	$98.1\%$	$91.6\%$	$98.4\%$
LDPC $(121,80)$	$169$	$27.6$	$100.0\%$	$100.0\%$	$100.0\%$
LDPC $(121,70)$	$36$	$37.0$	$100.0\%$	$91.7\%$	$100.0\%$

Appendix

Table 12: Capture of undetected errors at

E_{b}/N_{0}=4

dB,

\tau=10^{-3}

, when the same fraction of valid outputs is flagged by three rules: uncertified frames (the certificate), highest output cost

\Phi

, and highest NFE. Cells are ordered by the number of undetected errors; those below

100

are listed for completeness only.

Code	gap	mean	$p_{90}$	added cert. (all)	(of uncert.)
MacKay $(96,48)$	$51.4\%$	$1.012$	$1.039$	$2.94\%$	$7.3\%$
LDPC $(49,24)$	$41.3\%$	$1.021$	$1.078$	$2.70\%$	$14.5\%$
BCH $(31,16)$	$27.7\%$	$1.046$	$1.173$	$0.19\%$	$1.8\%$
CCSDS $(128,64)$	$62.1\%$	$1.030$	$1.101$	$6.10\%$	$10.4\%$
LDPC $(121,70)$	$57.4\%$	$1.032$	$1.110$	$7.25\%$	$19.7\%$
LDPC $(121,80)$	$47.8\%$	$1.020$	$1.074$	$3.94\%$	$14.3\%$

Appendix

Table 13: Greedy dual bound

\Lambda_{\mathrm{D}}

against the exact LP optimum

\mathrm{LP}^{\star}

E_{b}/N_{0}=4

dB,

\tau=10^{-3}

20{,}000

frames per cell. “gap” is the fraction of frames with

\mathrm{LP}^{\star}>\Lambda_{\mathrm{D}}

; mean and

p_{90}

are of

\mathrm{LP}^{\star}/\Lambda_{\mathrm{D}}

over those frames. “added cert.” is the fraction of all frames (and of uncertified frames) that the exact optimum would additionally have certified, a lower bound on its gain.

Code	ECCT	CrossMPT	DDECC	SB-ECC	CAL-ECC	exact ML
BCH $(31,16)$	$4.59{\times}10^{-3}$	$6.13{\times}10^{-4}$	$4.20{\times}10^{-2}$	$2.32{\times}10^{-4}$	$\bm{2.16{\times}10^{-4}}$	$2.31{\times}10^{-4}$
LDPC $(49,24)$	$2.62{\times}10^{-3}$	$7.38{\times}10^{-4}$	$1.65{\times}10^{-3}$	$2.19{\times}10^{-4}$	$\bm{6.11{\times}10^{-5}}$	$5.21{\times}10^{-5}$
BCH $(63,51)$	$1.28{\times}10^{-2}$	$7.02{\times}10^{-3}$	$2.78{\times}10^{-2}$	$7.16{\times}10^{-3}$	$\bm{7.24{\times}10^{-4}}$	$6.89{\times}10^{-4}$
MacKay $(96,48)$	$9.02{\times}10^{-4}$	$2.57{\times}10^{-4}$	$6.28{\times}10^{-5}$	$4.87{\times}10^{-5}$	$\bm{2.00{\times}10^{-5}}$	$1.80{\times}10^{-5}$
LDPC $(121,80)$	$3.97{\times}10^{-4}$	$7.64{\times}10^{-5}$	$4.12{\times}10^{-5}$	$1.15{\times}10^{-5}$	$\bm{2.65{\times}10^{-6}}$	$4.50{\times}10^{-7}$ ‡

Appendix

Table 14: FER at

E_{b}/N_{0}=5

dB against the exact ML reference. CAL-ECC at

\tau=10^{-3}

, with codes sorted by block length. No decoder can go below the reference beyond finite-sample fluctuation (Section 5.3 ). ‡ The reference for LDPC

(121,80)

is censored at this operating point and is quoted for scale only. The uncensored comparison for that code is at

4

dB, where it is

2.82{\times}10^{-4}

against

6.67{\times}10^{-5}

Panel of Figure 3 — Figure 3: BER on all fifteen codes. CAL-ECC curves darken as $\tau$ decreases, and baselines are dashed. The CAL-ECC family is nested, with lower $\tau$ shifting the curve down without changing its slope, which is the signature of a decoder approaching a fixed ceiling rather than one whose error exponent has changed.

Panel of Figure 4 — Figure 4: FER on all fifteen codes, same conventions as Figure 3 . Panels marked ∗ carry the exact ML reference (grey) with the unachievable region shaded. A reference is published for eleven of the fifteen codes ( Helmling et al., 2019 ) , and five of those are reproduced in Figure 2 . The reference terminates at $5$ or $6$ dB because the integer program becomes infeasible at the frame counts needed below that FER.

Error-Correcting Codes

See all 34 papers

May 11, 2026

Scalable Mamba-Based Message-Passing Neural Decoder for Error-Correcting Codes

Forward error correction is essential for reliable communication over noisy channels. Attention-based model-free neural decoders have shown strong performance for short codes, but their scalability to longer codes is limited by the quadratic memory and computational cost of attention. In this paper, we introduce the Mamba message-passing decoder (MMPD), an attention-free syndrome-based neural decoder for binary linear codes. MMPD retains the Tanner-graph structure of a message-passing decoder by performing local pairwise aggregation along variable-check edges. To enable efficient long-range information propagation, these local updates are combined with bidirectional Mamba state-space blocks. By avoiding dense attention matrices, MMPD scales more favorably for long codes in both memory and computation. Experiments on the (1056, 880) LDPC code show that MMPD achieves a 0.45 dB gain over the state-of-the-art CrossMPT decoder at a specified target bit error rate, while reducing memory consumption by a factor of 1.5. This reduction factor increases substantially for longer codes, demonstrating the applicability of MMPD to scalable neural decoding of practical long codes.

Rostislav Gusev, Nikita Aleksandrov, Artem Solomkin +1

Skolkovo Institute of Science and Technology, Moscow, Russia

Neural Decoding Message Passing Neural Networks Error-Correcting Codes

Ask PDF

May 17, 2026

Maximum Likelihood Decoding of Quantum Error Correction Codes

Quantum error correction (QEC) is indispensable for realizing fault-tolerant quantum computation, yet its effectiveness hinges critically on the classical decoding algorithm that interprets noisy syndrome measurements. Among all possible decoding strategies, maximum likelihood decoding (MLD) is provably optimal, since it identifies the logical group with largest likelihood by summing over all possible errors within logical class consistent with the observed syndrome. Despite its optimality, MLD is computationally intractable in general (#P-hard), motivating a rich landscape of exact and approximate algorithms. In this topical review, we provide a unified perspective on MLD by surveying recent advances through three complementary lenses: statistical mechanics, tensor networks, and artificial intelligence. From the statistical mechanics viewpoint, the MLD problem maps onto evaluating partition functions of disordered spin models, enabling exact solutions for certain codes and noise models as well as threshold estimation via phase-transition analysis. From the tensor network perspective, approximate contraction of tensor networks on the code's factor graph yields decoders that closely approach MLD accuracy with polynomial computational cost. From the artificial intelligence perspective, neural-network-based decoders, including autoregressive generative models and recurrent transformers, learn to approximate the MLD distribution from data, achieving high accuracy with the parallelism afforded by modern hardware accelerators. We discuss the connections among these three approaches, review their application to both simulated and experimental quantum hardware, and outline open challenges including real-time decoding, scalability to large code distances, and generalization to high-rate quantum low-density parity-check codes.

Hanyan Cao, Ge Yan, Yuxuan Du +1

1Science, Mathematics and Technology Cluster, Singapore University of Technology and Design, 8 Somapah Road, 487372, Singapore · College of Computing and Data Science, Nanyang Technological University, Singapore, Singapore · School of Physical and Mathematical Sciences, Nanyang Technological University,2026 Singapore, Singapore

Quantum Error Correction Quantum Error Correction Decoding Error-Correcting Codes

Ask PDF

May 27, 2026

Score Based Error Correcting Code Decoder

Error-correcting codes enable reliable communication, yet practical soft decoding remains challenging across code families and block lengths. We propose SB-ECC, a score-based decoder that casts decoding as continuous-time denoising. A neural denoiser defines a probability-flow ordinary differential equation (ODE) that iteratively updates the noisy channel observation toward a valid codeword, guided by parity constraints. The model is trained across noise levels without time/SNR conditioning, enabling inference without SNR estimation and supporting a direct latency accuracy trade off controlled by the ODE solver budget. We use the raw signed channel observation as input for learning a continuous denoising field. Across 42 code/SNR settings, SB-ECC achieves the best BER in 39/42 entries, with an average SNR gain of 0.17dB and a maximum gain of 0.46dB over the strongest competing baseline, we showed that swapping the solver from Euler to DPM preserves -ln(BER) while reducing end-to-end decoding time by 8.86% on average (up to 12.82%).

Alon Helvits, Eliya Nachmani

School of Electrical and Computer Engineering (ECE), Ben Gurion University, Beer Sheva, Israel.

Error-Correcting Codes

Ask PDF

Abstract

Error-Correcting Codes

Explore similar work

Scalable Mamba-Based Message-Passing Neural Decoder for Error-Correcting Codes

Maximum Likelihood Decoding of Quantum Error Correction Codes

Score Based Error Correcting Code Decoder