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

Scalable Mamba-Based Message-Passing Neural Decoder for Error-Correcting Codes
May 11, 2026Rostislav Gusev, Nikita Aleksandrov, Artem Solomkin +1Neural Decoding Message Passing Neural Networks
Skolkovo Institute of Science and Technology, Moscow, Russia
Maximum Likelihood Decoding of Quantum Error Correction Codes
May 17, 2026Hanyan Cao, Ge Yan, Yuxuan Du +1Quantum Error Correction Quantum Error Correction Decoding
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
Score Based Error Correcting Code Decoder
May 27, 2026Alon Helvits, Eliya NachmaniError-Correcting Codes
School of Electrical and Computer Engineering (ECE), Ben Gurion University, Beer Sheva, Israel.

May 11, 2026J/K move · Enter open · S save

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

Rostislav Gusev, Nikita Aleksandrov, Artem Solomkin, Dmitry Artemasov

Skolkovo Institute of Science and Technology, Moscow, Russia

Neural Decoding Message Passing Neural Networks Error-Correcting Codes

Open paper AskPDF arXiv

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.

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