Conditional Correctness in List Decoding: How a Late Second Codeword Can Rescue Confidence in the First
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.
Related
- Exact Conditional Confidence Intervals for Cramér's V: Near-Nominal and Tight Where the Guaranteed Interval Is Wide and the Software Interval Does Not Cover
- The Value of Duplicate Measurements When Decoding Second-Order Reed-Muller Codes
- The 3/4 Conjecture for q-Ary Fix-Free Codes With at Most Three Distinct Codeword Lengths
- Dijkstra Is NOT Greedy: A Global-to-Local Proof of Correctness
- Minimum-coordinate elimination on a simplex: polynomial first-step safety and coNP-complete correctness
BibTeX
@misc{struss2026conditional,
title = {{Conditional Correctness in List Decoding: How a Late Second Codeword Can Rescue Confidence in the First}},
author = {Conrad Struss and Muriel Medard and Ken R. Duffy},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02458},
eprint = {2610.02458},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02458},
}
RIS
TY - UNPB
TI - Conditional Correctness in List Decoding: How a Late Second Codeword Can Rescue Confidence in the First
AU - Conrad Struss
AU - Muriel Medard
AU - Ken R. Duffy
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02458
UR - https://arxiv.org/abs/2610.02458
AB - 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.
ER -