acceptodds
Withdrawn from ICLR 2027

Certified Adaptive List Decoding for Error-Correcting Codes

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

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.

Primary area:
optimization
Keywords:
Error-correcting codes, Maximum-likelihood decoding, Discrete diffusion

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_hvxpOpenReview ↗
Rating
2
Confidence
4
Informativeness
3
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes CAL-ECC, which combines a CrossMPT-based masked diffusion generator, adaptive beam search, and two maximum-likelihood (ML) optimality certificates based on LP duality and minimum-distance arguments. The authors evaluate the method on 15 codes across five SNR points, achieving the best BER in 71 out of 75 comparisons and approaching exact ML decoding performance on several codes.

Critical strengths
  1. The learning framework proposed by the authors is quite innovative.
  2. The experimental results are strong compared with the selected baselines.
  3. The proposed validation method is correct.

I acknowledge the strong experimental results. However, I have concerns regarding the actual sources of the performance improvements, the selection of baselines, the theoretical novelty, and the practical value of the ML certification mechanism.

Critical weaknesses
  1. The paper adopts CrossMPT as its neural network backbone. However, the ablation experiments show that most of the performance improvements come from Beam Search. This leads me to believe that the performance gains of this work essentially come from a method similar to list decoding.

  2. If the proposed approach is essentially similar to list decoding, comparing it mainly against ECCT, CrossMPT, DDECC, and SB-ECC is quite unfair. I believe the paper should at least include a comparison with a neural decoder equipped with a list decoding strategy. For example, one could use CrossMPT as the neural backbone and incorporate OSD/Chase-style algorithms as a baseline.

  3. The training budgets are also inconsistent. CAL-ECC is trained for 2 million steps, whereas CrossMPT is trained for only 1 million steps.

  4. The novelty and benefits of the ML Certification Mechanism remain unclear. I acknowledge that incorporating knowledge from classical coding theory into neural decoding is a contribution. However, I would like to understand whether this contribution merely improves performance by combining existing techniques, or whether it brings improvements to the neural network's internal computation mechanisms or architecture. For example, can the ML Certification Mechanism reduce the required training budget? Can it change or narrow the search space of Beam Search?

Questions for authors
  1. Could the authors include a neural decoder with a list decoding strategy as a baseline and report its BER, BLER, and computational costs?

  2. The paper considers a stopping mechanism based on ML optimality conditions. I would like to understand its advantages and disadvantages compared with syndrome-based stopping, particularly in terms of the trade-off between decoding performance and computational cost. For example, if satisfying the ML optimality conditions requires substantial additional computation, this should not necessarily be considered an advantage of ML-certified stopping.

  3. Beyond simply incorporating the ML Certification Mechanism into a neural decoder, what practical benefits or changes can this mechanism bring to the neural decoder itself?

If you can clear up my doubts, I’d be more than happy to improve my score. Before this, I had quite a few doubts about the necessity and novelty of the method proposed in this paper.

1 comment
AuthorsOpenReview ↗

Response to Reviewer hvxp

Thank you for your insightful comments and suggestions. We will improve our paper based on your comment.

Reviewer_T7bmOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces CAL-ECC (Certified Adaptive List Decoding for Error-Correcting Codes), which addresses a key limitation in neural decoders for error-correcting codes: while they can produce a predicted result, they lack the ability to determine whether that output is the maximum-likelihood (ML) optimal solution. Experimental results demonstrate that CAL-ECC achieves the lowest bit error rate (BER) across most settings and successfully certifies ML optimality for a large number of frames.

Critical strengths
  1. The two types of certificates are structurally complementary.
  2. Accuracy and certification cost are explicitly decoupled.
Critical weaknesses
  1. Innovation is limited; the core algorithm essentially functions by "combining existing components."
  2. While the paper discusses methods such as OSD, GRAND, and LP decoding, the primary experiments focus on comparing the proposed approach against four categories of learning-based methods: ECCT, CrossMPT, DDECC, and SB-ECC.
  3. The candidate generator relies entirely on a pre-trained diffusion model, yet the main text provides very limited information regarding its architecture, the volume of training data, and other related details. This significantly hinders reproducibility and makes it difficult to determine whether the performance gains stem from the CAL framework itself or from a more powerful generator.
  4. A single code can be represented by different parity-check matrices (HH), and the certificate rate may vary depending on the choice of HH; however, the paper does not investigate this "representation sensitivity."
  5. The paper primarily uses the number of function evaluations (NFE) as a metric for computational cost. However, different decoders vary in terms of their per-forward-pass computational load, batching strategies, GPU memory footprint, and the costs associated with LP dual calculations. The authors should, at a minimum, report wall-clock latency, GPU memory usage, and throughput.
  6. There is a lack of clear analysis regarding worst-case costs or the trade-offs between coverage, accuracy, and computational cost.
  7. The code lengths used are generally quite short, primarily ranging from approximately 31 to 128.
  8. I will adjust my score based on the authors' rebuttal.
Questions for authors
  1. Please include at least one additional method from the "strong OSD/Chase" category and one from the "GRAND" category, and report results for both within the same bit error rate (BER) regime.
  2. Is it possible to verify the scalability for longer codes?
  3. How sensitive is "Certificate D" to the specific representation of the parity-check matrix?
1 comment
AuthorsOpenReview ↗

Response to Reviewer T7bm

Thank you for your insightful comments and suggestions. We will improve our paper based on your suggestions.

Reviewer_DVwNOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

In classical coding theory parlance, this paper proposes a scheme for near ML decoding of error correcting codes and tests it for various codes of length up to about 128. The idea is to run a search guided by a learned metric and to terminate the decoding algorithm once a suitable criterion can certify that the ML codeword has been found and otherwise output the best candidate found so far. For a set of test codes the claim is that this decoding algorithm gets close to ML decoding. In technical terms: This paper proposes a reduced-state breadth-first trellis decoder of a linear code. In fact it proposes such a scheme in a weaker than the classical form since it never realizes that states can be merged again.

This is a very classical problem that has been studied essentially as long as coding theory was introduced close to 80 years ago. So it is not surprising that there is a flurry of papers and ideas that were introduced over time. Many of those are either extremely close or identical to what the authors propose but the authors do not seem to be aware of this prior art. This could have easily been avoided. An LLM aided search would very quickly find the relevant literature.

As is the paper cannot be published. There is a new idea in this paper. Namely the learned path metric metric has not been considered before. This is potentially useful. It is hence possible that it this metric combined with a proper search gives better results than classical approaches. But this has not been tested in this paper.

Critical strengths
  • the learned path metric for the breath first search is genuinely new; it is quite possible that a nice paper can be build on top of this if one can show that it leads to genuinely better results; it is possible;

  • the paper is honest about what it does, the experiments are set up properly and described in detail, nothing is hidden or glossed over; I very much appreciate all those things

  • the writing is clear

Critical weaknesses
  • the paper defines the optimal rule for block errors; it defines this as ML rule; strictly speaking ML has nothing to do with block versus bit and there are optimal rules for both but they are not the same; you find this mistake in many papers; unfortunately also in this one; the experiments use both bit and block errors; the paper does not cleanly separate the two and uses bounds on the block error also where bit errors are meant (see for example Figure 3 Theorem 4.3); to be fair, the paper mentions at some point that “ML is block-optimal”;

  • certificate M is exactly what in classical coding is known as the Taipale-Pursley test (1991); this work followed Forney’s GMD decoder.

  • the rule in this paper of retaining at most the top candidates is Andersons’ and Mohan’s classical algorithm

  • the pruning algorithm is the classical Simmons T algorithm

  • all this should be framed as a trellis decoder; so the decoding space is not in fact a tree but a trellis since you can merge paths with equal partial trellis (which is curiously not stated); this is called the Wolf trellis; for many codes in this paper this fact itself makes decoding (exact bit or block ML) feasible and the whole certificate business is not in fact needed; and you can use the dual trellis also; so the “hard” cases in your list are mostly the LDPC(121, 80), LDPC(121, 70), LDPC(121, 60) and MacKay(96,48) codes.

  • for the hard cases there are many obvious missing baselines: e.g., BP, or BP for overcomplete representations, or generalized BP, or any of those followed by order statistics decoding (Fossorier), LP and adaptive LP, integer programmming decoding, …

  • with respect to the many many missing references; rather than me listing a large number of them, just look for trellis decoding of linear codes (Wolf), Forney and also Kschischang (trellis structure of linear codes), Mohan (the M algorithm), Simmons (T algorithm),

Questions for authors

NA

1 comment
AuthorsOpenReview ↗

Response to Reviewer DVwN

Thank you for your insightful comments and suggestions. We will improve our paper based on your suggestions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.