PaperlayerView exact revision on arXiv

Source-linked AI summary

Beam Search for Error-Correcting Codes via Conditional Diffusion

Ziv Aharoni, Henry D. Pfister

arXiv:2610.32807v1cs.ITmath.IT

TL;DR

Reliable decoding must recover transmitted information from noisy observations, while maximum-likelihood decoding is computationally hard for general linear codes and sequential decisions constrain parallelism. The paper uses conditional masked diffusion with a beam search over candidate paths. Across evaluated settings, MBS improves on single-trajectory diffusion and achieves the best performance among compared neural decoders.

  • Problem

    Maximum-likelihood decoding is NP-hard for general linear codes, and sequential polar decisions can limit parallelism, motivating a principled way to improve neural decoding by searching across candidates.

    Source: §1 · pp. 1–2

  • Method

    The decoder keeps the physical observation fixed, uses an auxiliary masking process to form reverse bit decisions, and applies MBS to branch, prune by accumulated transition log-probabilities, and select a completed candidate.

    Source: §1 · p. 2, §3.2 · p. 3, §4.3.1 · p. 6

  • Results

    Across evaluated scenarios, MBS improves on conditional diffusion and has the best decoding performance among compared neural decoders; it has the highest reported −ln(BER) in all 42 code–SNR comparisons.

    Source: §1 · p. 2, §5.2 · p. 8

  • Takeaways & Limitations

    The experiments support conditional masked diffusion augmented with MBS as a competitive decoding approach across the evaluated settings.

    Source: §6 · p. 10

    The framework assumes a degraded auxiliary channel with clean and uninformative endpoints, and the stated setup uses homogeneous auxiliary noise.

    Source: §3.2 · pp. 3–4

Abstract

from arXiv · show

We introduce a diffusion framework for neural decoding of error-correcting codes (ECCs). We interpret decoding as a conditional diffusion process that progressively predicts codeword bits while treating the physical channel observation as fixed side information. At each stage, a neural model estimates bitwise posteriors conditioned on the physical observation and the current noisy state of the codeword. We focus particularly on masked diffusion, for which the reverse process naturally induces a Maxwell beam search (MBS) procedure inspired by the Maxwell construction of Measson et al. Rather than committing to a single uncertain decision, the decoder maintains multiple candidate trajectories, removes parity-infeasible candidates, and ranks the remaining candidates using accumulated reverse-transition log-probabilities. We evaluate the framework across multiple code families on binary phase-shift keying (BPSK) over additive white Gaussian noise (AWGN). Experiments show competitive decoding performance across Polar, low-density parity-check (LDPC), and Bose-Chaudhuri-Hocquenghem (BCH) codes. The MBS decoder consistently improves upon the corresponding single-trajectory diffusion decoder and, in all evaluated settings, improves upon available neural decoding results.

1 INTRODUCTION

The introduction motivates neural decoding that can improve on sequential decisions without adding more sequential steps. It presents conditional masked diffusion with beam search and reports improved performance over single-trajectory diffusion and other compared neural decoders.

1 INTRODUCTION

  • Maximum-likelihood decoding is NP-hard for general linear codes, while BP and min-sum trade lower complexity for accuracy losses on cyclic graphs and approximation error.Learned message updates have improved message-passing performance on selected codes (Nachmani & Wolf, 2021).Source: §1 · p. 1
  • Polar successive cancellation makes irrevocable sequential decisions; list decoding branches to retain alternatives, but its sequential dependence can increase latency and limit parallelism.SCL decoding outperforms neural decoding methods for polar codes, particularly as block length increases.Source: §1 · pp. 1–2
  • Across evaluated scenarios, MBS improves on single-trajectory conditional diffusion and has the best decoding performance among compared neural decoders.Figure 1 compares methods on Polar(64, 32) at 4 dB; higher −ln(BER) is better.Source: Figure 1 · p. 2, §1 · p. 2
  • The paper asks whether neural decoding can spend additional computation in parallel across candidates instead of adding sequential steps.The motivation is the parallelism and latency trade-off associated with list decoding for SC.Source: §1 · p. 2
  • Conditional diffusion keeps the physical observation fixed while an auxiliary process corrupts the codeword, which the reverse process estimates; masking is chosen for beam decoding.The formulation aims to sample from the posterior of the transmitted codeword given the physical observation.Source: §1 · p. 2, Figure 2 · p. 2
  • MBS branches on multiple bit assignments, prunes paths by accumulated reverse-transition log-probabilities when the beam is too large, and selects the most likely completed candidate.The approach is inspired by the Maxwell construction of M´easson et al. (2008).Source: §1 · p. 2

2 RELATED WORK

The related work spans neural decoders, diffusion decoding, and branching or list-search methods. This paper combines conditional masked diffusion with posterior-guided branching and path scoring.

2 RELATED WORK

  • Neural BP, attention-based decoders, neural polar list decoders, and diffusion decoders provide related approaches, while this formulation fixes the physical observation and adds auxiliary masking.The cited approaches include learned BP updates (Nachmani & Wolf, 2021), ECCT and CrossMPT, neural polar decoders, and DDECC and SB-ECC.Source: §2 · p. 3
  • Unlike prior branching and beam-search approaches, this method uses conditional masked diffusion marginals to guide assignments, reverse-transition log-probabilities to rank paths, and parity constraints to eliminate infeasible candidates.Related examples include the Maxwell decoder (M´easson et al., 2008), SCL, learned decimation for neural BP, and BP-guided quantum LDPC methods (Aydin et al., 2026).Source: §2 · p. 3

3 PRELIMINARIES AND BACKGROUND

The preliminaries define the binary linear-code transmission setup and distinguish the fixed physical observation from the auxiliary noise process that drives decoding. The auxiliary process is homogeneous and degraded, with clean and uninformative endpoints.

3.1 ERROR-CORRECTING CODES

  • A binary linear block code uses generator and parity-check matrices satisfying HG = 0 over F2, with rank(H) = n − k and at least n − k listed checks.The code rate is k/n, and transmission maps codeword bits to BPSK symbols x_s = 1 − 2x.Source: §3.1 · p. 3

3.2 PHYSICAL OBSERVATION AND AUXILIARY NOISE

  • The auxiliary channel is a decoder-design choice governing the evolving state, and the setup uses the same scalar channel at every coordinate.The auxiliary family is assumed degraded: later noise levels can be generated through a channel from earlier auxiliary outputs.Source: §3.2 · pp. 3–4
  • The physical channel supplies R = r, the received observation that remains fixed and conditions decoding decisions.The physical channel distribution is determined by the communication medium.Source: §3.2 · p. 3
  • The auxiliary trajectory has a clean endpoint where Y(t) equals X and an uninformative endpoint independent of X; for masking, these correspond to t = 0 and t = 1.At the masking endpoint t = 1, the state is the all-erasure word.Source: §3.2 · p. 4

4 DECODING ERROR-CORRECTING CODES AS CONDITIONAL DIFFUSION

The section develops conditional masked diffusion for decoding, keeping the physical observation fixed while learned posterior marginals guide reverse decisions. It extends this process with Maxwell beam search, which branches among candidate paths and uses parity constraints and path scores to select a codeword.

4.1 CONSERVATION LAW FOR MASKED DIFFUSION

  • A conditional conservation law relates bitwise mismatched cross-entropies along the masking process to codeword-level conditional cross-entropy given the physical observation.For Polar(128, 64) and CCSDS(128, 64) at 4 dB, the motivating example estimates 0.38 and 0.028 bits, respectively.Source: §4.1 · pp. 4–5

4.2 LEARNING POSTERIOR MARGINALS

  • The learned posterior marginals must be induced by the same auxiliary masking channel as the true distribution; predictions are probabilistic at masked positions and deterministic at revealed positions.Training holds the physical observation fixed while sampling the auxiliary masked state.Source: §4.2 · p. 5

4.3 INFERENCE

  • In conditional-diffusion inference, learned bitwise posteriors define the reverse transitions, and the MBS extension adds a beam of candidate paths.The physical observation remains side information throughout decoding.Source: §4.3 · p. 5, §4.3.1 · p. 6

4.3.1 CONDITIONAL-DIFFUSION DECODING.

  • The single-trajectory decoder reveals the most confident masked bits according to their LLRs, checks early hard estimates against parity constraints, and continues by schedule unless a valid codeword is found.A confidence-balanced schedule uses reveal counts equal up to rounding; absent early exit, all bits are revealed as the noise level falls from 1 to 0.Source: §4.3.1 · pp. 5–6

4.3.2 MAXWELL BEAM SEARCH

  • MBS completes candidates, returns a valid codeword nearest the observation when available, and otherwise backtracks to branch and retain parity-consistent children with high path scores.Branching targets least-confident masked bits; parity propagation fixes forced bits and discards contradictions.Source: §4.3.2 · pp. 7–8, Figure 4 · p. 7

5 EXPERIMENTS

The experiments evaluate conditional diffusion and Maxwell beam search (MBS) on linear codes over BPSK-AWGN, including decoding performance and latency. MBS leads the reported BER comparisons, while its latency advantage depends on SNR.

5.1 EXPERIMENTAL SETUP

  • The evaluation covers LDPC, Polar, and BCH codes over BPSK-AWGN, with BP, SC, SCL, and neural decoders among the comparison methods.For Table 1, MBS uses beam size 64; the table reports −ln(BER), with higher values better.Source: §5.1 · p. 8, Table 1 · p. 9

5.2 RESULTS

  • MBS with L = 64 achieves the highest reported −ln(BER) among six methods in all 42 code–SNR comparisons.SB-ECC has lower reported BER than conditional diffusion in 39 of 42 comparisons; the CCSDS(128, 64) result at 6 dB is a lower bound because no errors were observed.Source: §5.2 · p. 8, Table 1 · p. 9
  • On CCSDS, MBS using BP estimates outperforms plain conditional diffusion and SB-ECC, while learned MBS remains below the CCSDS ML and Polar SCL references.On Polar, short cycles and uneven node degrees may contribute to poor BP estimates; MBS improves Polar BP only modestly.Source: §5.2 · p. 9

5.3 DECODING LATENCY AND STOPPING-TIME DISTRIBUTION

  • At 4 dB, MBS has lower mean inference time than SB-ECC (9.30 vs. 25.01 ms), but at 2.5 dB it is slower (47.03 vs. 40.01 ms).At 4 dB, 98.55% of frames stop after one neural evaluation; at 2.5 dB, 66% do, and additional search raises MBS’s mean time.Source: §5.3 · p. 10, Figure 6 · p. 10

5.2 RESULTS

  • Additional experiments evaluate longer LDPC codes in Appendix E, study generalization to Rayleigh fading in Appendix F, and report computational complexity and measured decoding latency in Appendix G.Figure 5 reports BLER over BPSK-AWGN for MBS (L = 2048) on the CCSDS and Polar codes.Source: §5.2 · p. 8, Figure 5 · p. 9, §5.3 · p. 10

6 CONCLUSION

The conclusion presents conditional masked diffusion with fixed received-word side information and learned posterior marginals, then reports that adding MBS yields competitive decoding performance. It also identifies broader diffusion generation as a possible direction for the mechanism.

6 CONCLUSION

  • The framework keeps the received word fixed as side information and uses learned posterior marginals to guide conditional masked diffusion.The approach is motivated by an information-theoretic conservation law.Source: §6 · p. 10
  • Across the evaluated settings, augmenting conditional diffusion with MBS yields competitive decoding performance.Source: §6 · p. 10
  • The authors suggest MBS may benefit diffusion-based generation by retaining alternative partial solutions before uncertain decisions are finalized.They point to search during generation as a direction for extending these ideas beyond ECC.Source: §6 · p. 10

AI USE STATEMENT

This material includes an AI-use statement and outlines appendix analyses of masking conservation laws, path scores, and implementation and evaluation details. The path-score analysis connects parallel reveals to dependence penalties.

AI USE STATEMENT

  • OpenAI Codex assisted with related-work review, methodological and experimental options, research code and evaluations, and manuscript drafting and editing.The authors state they reviewed AI-assisted outputs and take responsibility for the paper’s claims, results, and content.Source: AI USE STATEMENT · p. 10

APPENDIX CONTENTS

  • The appendices cover conditional masking conservation laws, parallel-sampling path scores, posterior-estimator implementation, evaluation protocols, longer-code results, Rayleigh fading, and beam-size and latency analyses.Source: APPENDIX CONTENTS · p. 14

A CONDITIONAL CONSERVATION LAWS FOR MASKING

  • The masking proof assumes the true posterior is absolutely continuous with respect to the model posterior and that conditional cross-entropy is finite.Under both laws, coordinates are independently masked with probability t_i, independently of R given X.Source: A CONDITIONAL CONSERVATION LAWS FOR… · p. 14

B PARALLEL SAMPLING, TOTAL CORRELATION, AND PATH SCORES

  • For exact posterior marginals, revealing one bit at a time gives the log-posterior path score; parallel reveals incur total-correlation penalties, and learned marginal error adds to the dependence penalty.The expected negative path score upper-bounds posterior entropy.Source: B PARALLEL SAMPLING, TOTAL… · p. 15

C POSTERIOR-ESTIMATOR IMPLEMENTATION

The posterior estimator combines representations of the current auxiliary state and fixed physical observation, then predicts extrinsic posteriors for masked bits. The evaluation appendix documents protocols and cautions that published-method comparisons may differ in training and evaluation conditions.

C POSTERIOR-ESTIMATOR IMPLEMENTATION

  • Separate auxiliary-state and physical-observation encoders condition every CrossMPT layer through adaptive layer normalization.Code-bit and parity-check tokens use alternating H- and HT-masked cross-attention.Source: C POSTERIOR-ESTIMATOR IMPLEMENTATION · p. 15
  • For masked bits, the output head predicts extrinsic posterior logits, while the known local auxiliary-channel likelihood is applied outside the network.The resulting marginals drive both the diffusion and MBS decoders.Source: C POSTERIOR-ESTIMATOR IMPLEMENTATION · pp. 15–16

D EVALUATION PROTOCOLS AND REFERENCE RESULTS

D.1 BASELINES EVALUATIONS

The evaluations compare conditional diffusion and MBS with published neural and classical baselines across code families and channel conditions. They describe training and simulation protocols, decoder configurations, and a Polar(64, 32) BER comparison.

D.1 BASELINES EVALUATIONS

  • The baseline comparison reports BP, CrossMPT, DDECC, and SB-ECC BER values transcribed from Helvits & Nachmani (2026, Table 1); BP uses 50 decoding iterations, while DDECC and SB-ECC share the CrossMPT backbone.For LDPC(49, 24), DDECC reports at least 105 frames and at least 500 erroneous frames per SNR; SB-ECC stops after 500 frame errors or 109 evaluated LDPC frames; CrossMPT reports at least 500 erroneous frames without specifying the total frame count.Source: §D.1 · p. 16

D.2 TRAINING AND SIMULATION DETAILS

  • Training uses separate code-specific posterior estimators and online BPSK-AWGN samples; evaluations use EMA checkpoints and specified stopping rules.Training samples span 2–7 dB; the reported diffusion evaluation uses up to 16 confidence-balanced steps with parity-based early exit.Source: §D.2 · pp. 16–17

D.3 POLAR AND CCSDS DECODER-COMPARISON CURVES

  • Polar and CCSDS comparison curves cover 1–3.5 dB, while the Polar(64, 32) BER comparison uses BP and CRC-free SCL baselines alongside neural-decoder results.The SCL list sizes are 32 and 512 for the Polar and CCSDS curves; the Polar(64, 32) SCL evaluation uses list sizes 1, 4, 8, 16, 32, and 64.Source: §D.3 · p. 17, §D.4 · p. 17

D.4 POLAR(64, 32) BER COMPARISON

  • −ln(BER) = 7.92292 (rounded to 7.92) for MBS on Polar(64, 32) at 4 dB, with 502 frame errors over 177,664 frames.The same frames yielded 5,134 bit errors for diffusion and 4,120 for MBS; OSD-3’s estimate used 8,776 errors over 400,000 frames.Source: §D.4 · p. 17, Table 2 · p. 18

E LONGER-CODE RESULTS

The longer-code evaluation compares two LDPC codes over BPSK-AWGN at 4 and 5 dB. MBS has the strongest reported point estimates, while the study omits 6 dB because reliable estimates would require substantially longer simulations.

E LONGER-CODE RESULTS

F.1 GENERALIZATION TO RAYLEIGH FADING

The study evaluates AWGN-trained decoders on a memoryless Rayleigh-fading channel without fine-tuning. MBS has lower observed BER than diffusion at all six displayed points, but published-baseline comparisons are cross-study references.

F.1 GENERALIZATION TO RAYLEIGH FADING

  • The fading amplitudes are independent across coordinates, and the receiver is not given their values; the AWGN-trained checkpoints are evaluated without fine-tuning.Source: §F.1 · p. 18
  • MBS has lower observed BER than diffusion at all six displayed Rayleigh-fading points and the strongest BER point estimates among the displayed methods.The table compares AWGN-trained decoders against BP-50, BP-200, CrossMPT, and SB-ECC.Source: §F.1 · pp. 18–19, Table 4 · p. 19
  • Published-baseline comparisons use separate evaluations and do not control for code construction or SNR normalization, so the authors present them as cross-study references.Source: §F.1 · p. 19

G.1 EFFECT OF THE MAXIMUM BEAM SIZE

The section examines beam-size effects, latency estimation, and related decoding approaches. Its latency estimates vary by SNR, and the related-work discussion distinguishes the decoder’s posterior-guided branching and parity pruning from other beam-search methods.

G.1 EFFECT OF THE MAXIMUM BEAM SIZE

  • The beam-size study evaluates L ∈ {64, 128, 2048} on CCSDS(128, 64) and Polar(128, 64) at 2.5 and 4 dB, with BER measured on shared frames across beam sizes.The runtime approximation excludes parity-pruning width reductions, early probe termination, and decoder overhead.Source: §G.1 · p. 19, Table 5 · p. 20

G.2 COMPUTATIONAL COMPLEXITY AND LATENCY COMPARISON

  • Neural-decoder call counts include branching and completion queries; branching-round counts alone omit the repeated completion steps.A batch of candidates counts as one forward call, and each completion attempt uses KC steps.Source: §G.2 · p. 20
  • Estimated mean latency is 47.03 ms for MBS versus 40.01 ms for SB-ECC at 2.5 dB, and 9.30 ms versus 25.01 ms at 4 dB.Estimates average forward-call counts from stopping-time histograms, including the full MBS tail, using RTX A5000 timings.Source: §G.2 · p. 20, Table 6 · p. 20

H EXTENDED RELATED WORK

  • Unlike related branching and beam-pruning approaches, this decoder uses learned posterior marginals to guide branching, reverse-transition log probabilities to rank paths, and parity constraints to eliminate infeasible candidates.The related work also describes diffusion decoding as separating physical-channel noise from the auxiliary diffusion process.Source: H EXTENDED RELATED WORK · pp. 20–21

Related papers

Loading 2610.32807v1…