CS Paper Radar

Conditional Correctness in List Decoding: How a Late Second Codeword Can Rescue Confidence in the First

Conrad Struss, Muriel Medard, Ken R. Duffy

cs.IT ·submitted 2026-10-01 20:32 UTC · v1

Abstract

In error correction, the difference between a codeword and a received word, a candidate noise sequence, carries information on the confidence of the codeword as a proposed decoding. For additive channels, it is known that if noise sequences are ranked in decreasing order of likelihood, a lower rank correlates with higher confidence in a decoding. Here we substantially expand considerations by exploring the relationship between the likelihood ranks arising in list decoding and the posterior probability of decoding correctness, establishing that the ranks associated with subsequent list entries carry reliability information that is not obtainable from the first rank alone. Building on the recent development of Soft-Output Guessing Random Additive Noise Decoding, we first show that, under a random codebook model, soft-output expressions for list decoding coincide with the exact finite-blocklength conditional probabilities of decoding correctness. For hard-decision maximum likelihood decoding, we characterize the asymptotic reliability of the first list entry. We identify a decision function whose sign determines whether the posterior correctness probability of the first entry in the list converges to one or zero and whose absolute value gives the exponential rate of convergence. Perhaps surprisingly, the asymptotic reliability of the first list entry depends only on the first, second and last ranks. For list size one, the result recovers the previously known likelihood-rank threshold for reliable decoding. For list size two, a sufficiently late second entry can imply that the first entry is asymptotically correct even when its rank, viewed in isolation, would indicate otherwise.

Closest papers

Nearest neighbours by meaning across the whole index.

Soft GRAND under Channel Uncertainty: Minimax Posterior-Envelope Ordering and Gallager-Exponent Preservation

cs.IT ·2026-09-03 ·Behrooz Razeghi
similarity 0.73
Abstract

Soft Guessing Random Additive Noise Decoding queries corrections in an observation-dependent order. For a known channel, the matched order ranks corrections by nonincreasing conditional posterior probability. Under channel uncertainty, admissible channels may induce matched orders that assign different ranks to the same correction at the same observation. We instead use a posterior-envelope order, defined by the pointwise supremum of codebook-independent uniform-input correction posteriors. For fixed measurable posterior representatives and a measurable envelope, this order minimizes, at each observation, the worst-case logarithm of the rank--posterior product over admissible channel--correction pairs with positive posterior probability. For uniform-subset codebooks, this finite-block minimax property does not by itself determine the ensemble-average error exponent, which depends on the distribution of the realized correction rank. For i.i.d. correction--observation pairs with a finite correction alphabet whose joint distribution is dominated by the product of counting measure on that alphabet and a $σ$-finite measure on the observation space, Arimoto conditional Rényi entropy characterizes the matched rank-moment spectrum. An auxiliary posterior-envelope order preserves this spectrum on $[0,1]$ when its posterior family contains the corresponding conditional power tilts and has subexponential conditional Shtarkov complexity on observation sets whose complement probabilities decay exponentially faster than the reciprocal correction-space cardinality. Under additional differentiability and entropy nondegeneracy conditions, the auxiliary order attains the matched uniform-subset ensemble-average error exponent at every fixed normalized code rate strictly between zero and one. For uniform-input memoryless channels, this exponent equals Gallager's uniform-input random-coding exponent.

0.30

Certified Adaptive List Decoding for Error-Correcting Codes

cs.IT cs.LG ·2026-10-20 ·Jaeho Hwang, Byung-Sun Won, Uiwon Hwang
similarity 0.64
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.

0.31

SECS: A Soft Ensemble-Combining Stage for Low-Latency Decoding

cs.IT eess.SP ·2026-08-10 ·Felix Krieg, Paul Bezner, Stephan ten Brink
similarity 0.63
Abstract · 6 pages, 8 figures, submitted to an IEEE conference for possible publication

Ensemble decoding is a promising technique for ultra-reliable low-latency communication, as it trades hardware parallelism for decoding latency by running M diverse belief propagation (BP) decoders in parallel. Conventional ensembles select their output from the candidates. Hence, decoding fails whenever no member finds the correct codeword. In this work, we show that shallow, diverse BP members are poor correctors, but excellent sorters. Based on this observation, we propose a soft ensemble-combining stage (SECS) that combines extrinsic messages after only a few iterations, yielding a reliability ordering whose most reliable positions are nearly error-free. A subsequent re-encoding stage (like ordered-statistics decoding (OSD)) converts this ordering into a near-maximum likelihood (ML) candidate codeword, at a fraction of the BP latency of a fully converged ensemble. We demonstrate the proposed scheme on three short codes: a (63,30) Bose-Ray-Chaudhuri-Hocquenghem code, an overcomplete PG(2,8) code, and a search-designed (105,53) cyclic code. In all cases, the SECS with OSD post-processing closes most of the gap to ML decoding, while significantly reducing the number of required BP iterations.

0.09

Decoding Error Probability of the Random Code Ensemble over the Erasure Channel

cs.IT ·2026-09-04 ·Chin Hei Chan
similarity 0.61
Abstract · 16 pages, 1 figure

In this paper, we provide explicit formulas for the average decoding error probabilities of the ensemble of all $(n,M)_q$ codes over the erasure channel under unambiguous, list and maximum-likelihood decoding principles. Moreover, we derive the asymptotic error exponents for the ensemble of all $(n,q^{Rn})_q$ codes.

0.31

Universal Decoding via the Pairwise Error Probability

cs.IT ·2026-08-20 ·Nir Elkayam, Meir Feder
theory similarity 0.61
Abstract

We develop a theory of universal decoding built on the pairwise error probability (PEP) primitive of a companion paper. The PEP and its error spectrum are defined for an arbitrary decoding metric, and while raw metric values across a family share no common scale, the PEP supplies one. Universal decoding -- decoding well simultaneously against a whole family of metrics or channels -- becomes the problem of merging the per-metric spectra into a single rule, which we construct from a clipped inverse-PEP statistic. The construction rests on a Kraft-type inequality for decoding, valid for any input prior: per output, every metric canonicalizes into a conditional probability assignment on the codewords, and the merge is the normalized-maximum-likelihood envelope of the induced family. We prove the rule is random-coding universal (it loses only a vanishing rate relative to the best metric in the family, against every channel), show it is an asymptotic minimax/equalizer rule, and derandomize it: over a subexponential channel family a single deterministic code inherits the guarantee. For discrete memoryless channels the construction reduces to types and recovers the maximum-mutual-information decoder, its tilted variant for non-uniform memoryless input, and finite-state universal decoders. It extends to decoding with an erasure option (deterministically, uniformly over erasure margins) and, via a discretization of separable metric families, to continuous alphabets: for AWGN with deterministic interference it attains the matched-ML exponent up to an explicit typical-set cap, and for ISI channels the best exponent in a family of equalize-and-decode rules, under explicit assumptions on the equalizers and the channel spectrum and the same cap. Throughout, universality is a corollary of the PEP analysis rather than a separate theory.

0.26

ICL-SEC: Iterative Cross-Layer Semantic Error Correction

cs.IT cs.NI ·2026-08-15 ·Yirun Wang, Soung Chang Liew, Yuyang Du
similarity 0.61
Abstract

Iterative decoding has been central to the success of modern channel coding, where reliability information is repeatedly exchanged across decoding components to approach fundamental performance limits. This paper brings the same principle to semantic error correction by proposing iterative cross-layer semantic error correction (ICL-SEC), a framework that closes the loop between physical-layer soft channel decoder and application-layer language-model-empowered semantic decoder. In the proposed framework, a soft-input soft-output channel decoder first produces bit-level posterior probabilities, from which word-level reliabilities are derived. Words deemed reliable are exposed to a masked language model as semantic context, while unreliable words are masked. The language model then produces contextual word likelihoods, which are leveraged to generate extrinsic bit-level priors and fed back to the channel decoder for the next iteration. This iterative refinement progressively expands the set of confidently recovered words. A key contribution is our Confirm prior-update rule: once a word is judged reliable, its bits are assigned deterministic priors with probability one in subsequent iterations, making the word fully resolved side information for both the channel decoder and the language model. This successive-confirmation mechanism prevents oscillatory unmask-mask behavior and yields a reliability interpretation consistent across layers. Simulations over text transmission demonstrates that ICL-SEC substantially outperforms both conventional channel decoding and non-iterative CL-SEC. In particular, the proposed Confirm scheme reduces the bit error rate by more than two orders of magnitude relative to non-iterative CL-SEC, while also significantly improving the other five performance metrics.

0.04

Sensing-Aided Ordered Reliability Bits Guessing Random Additive Noise Decoding

eess.SP ·2026-08-14 ·Yu Ge, Lukas Rapp, Ken R. Duffy, Muriel Médard
similarity 0.59
Abstract

Integrated sensing and communication (ISAC) is a key enabler for future wireless systems, providing environmental information that can support tasks beyond conventional data transmission. However, its impact on channel decoding remains less explored. This paper studies sensing-aided ordered reliability bits guessing random additive noise decoding (ORBGRAND) over single-input single-output narrowband fading channels. Environmental information is used to construct a geometry-based prior for the channel coefficient, which is fused with pilot observations via linear minimum mean square error (LMMSE) estimation. The resulting posterior channel estimate and uncertainty are used to compute the log-likelihood ratios (LLRs) supplied to ORBGRAND, improving the reliability ordering that drives its noise-guessing process. Simulation results demonstrate improved block error rate and reduced average query complexity, with the largest gains in pilot-limited regimes.

0.34

Bayesian Entropy-based Reordering for Calibrated Diffusion Language Models

cs.LG cs.AI ·2026-10-04 ·Zhejun Jiang, Mijung Park
similarity 0.59
Abstract

Masked Diffusion Language Models (MDLMs) generate sequences by iteratively replacing masked tokens with model predictions. At each denoising step, the decoder chooses which positions are sufficiently confident to commit. Existing decoding methods typically rely on softmax confidence, which can be miscalibrated. We introduce BayesER (BAYESian Entropy-based Reordering), a post-hoc Bayesian decoding framework that uses predictive uncertainty to guide token commitment. In BayesER, we construct a lightweight approximate posterior centered at the pretrained checkpoint, similar to Laplace-LoRA but without training LoRA adapters. We average predictions over posterior samples and use predictive entropy to prioritize reliable positions. We examine how posterior predictions affect position ordering and token selection across benchmarks spanning code generation, mathematical reasoning, planning, and molecular generation. We show that BayesER reduces sequence-level calibration error while preserving or improving accuracy relative to common decoding schemes, including confidence-threshold decoding. Additionally, a posterior fitted on one code-generation dataset reduces calibration error on another without refitting, suggesting that Bayesian uncertainty may provide a transferable signal for more reliable MDLM decoding.

0.20