Recognition: 2 theorem links
· Lean TheoremPosterior Matching over Binary-Input Memoryless Symmetric Channels: Non-Asymptotic Bounds and Low-Complexity Encoding
Pith reviewed 2026-05-13 18:46 UTC · model grok-4.3
The pith
Posterior matching with SED partitioning gives non-asymptotic bounds on expected decoding time for variable-length feedback codes over BMS channels.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The paper claims that posterior matching over BMS channels admits an achievability bound on the expected decoding time that decomposes into a communication term governed by the capacity C, a confirmation term governed by the KL divergence C1, and a recovery term governed by the Bhattacharyya parameter. This bound is obtained by developing new stopping-time and overshoot inequalities for submartingales and random walks that have unbounded increments, using renewal theory tools. The scheme is realized with a polynomial-complexity encoder that groups messages by their lattice-structured log-likelihood ratios and applies batched corrections to enforce the exact SED partition at each step.
What carries the argument
The small-enough-difference (SED) partitioning of messages according to their posteriors, which keeps the difference in log-likelihood ratios bounded in a way that enables martingale analysis; this is enforced exactly via lattice grouping and batched correction in the encoder.
Load-bearing premise
That the log-likelihood ratios take values on a discrete lattice, so the encoder can exactly balance the SED partition by grouping and correcting in batches.
What would settle it
For the binary symmetric channel, simulate the posterior evolution under the proposed encoder and measure whether the average number of channel uses until decoding exceeds the sum of the three explicit terms in the bound for given values of C, C1, and the Bhattacharyya parameter.
Figures
read the original abstract
We study variable-length feedback (VLF) codes over binary-input memoryless symmetric (BMS) channels using posterior matching with small-enough-difference (SED) partitioning. Prior analyses of SED-based schemes rely on bounded log-likelihood ratio (LLR) increments, restricting their scope to discrete-output channels such as the binary symmetric channel (BSC). We remove this restriction and provide an analysis of posterior matching that covers a broad class of BMS channels, including continuous-output channels such as the binary-input AWGN channel. We derive a novel non-asymptotic achievability bound on the expected decoding time that decomposes into communication, confirmation, and recovery terms with explicit dependence on the channel capacity~$C$, the KL divergence~$C_1$, and the Bhattacharyya parameter of the channel. The proof develops new stopping-time and overshoot bounds for submartingales and random walks with unbounded increments, drawing on tools from renewal theory. On the algorithmic side, we propose a low-complexity encoder that enforces the exact SED partition at every step by grouping messages according to their log-likelihood ratios that are assumed to land on a lattice, and applying a batched correction step that restores the partition balance. The resulting encoder complexity is polynomial in the number of transmitted bits. For continuous-output channels, the lattice structure is enforced through output quantization satisfying an exact induced-lattice constraint; the associated capacity loss is $O(\log B / B^2)$ for a $B$-level quantizer. These results yield a VLF coding scheme for BMS channels that simultaneously achieves strong non-asymptotic performance and practical encoder complexity.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript develops posterior matching with small-enough-difference (SED) partitioning for variable-length feedback codes over binary-input memoryless symmetric channels, including continuous-output channels such as BI-AWGN. It derives a non-asymptotic achievability bound on expected decoding time that decomposes into communication, confirmation, and recovery terms with explicit dependence on capacity C, KL divergence C1, and the Bhattacharyya parameter. The proof uses new stopping-time and overshoot bounds for submartingales with unbounded increments drawn from renewal theory. A low-complexity encoder is proposed that enforces exact SED partitions via lattice LLR grouping and batched correction, achieving polynomial complexity; for continuous outputs this is realized by B-level quantization with O(log B/B^2) capacity loss under an exact induced-lattice constraint.
Significance. If the central claims hold, the work supplies explicit non-asymptotic performance guarantees and a practical encoder for VLF coding over a broad class of BMS channels, extending prior SED analyses beyond bounded-increment discrete-output cases. The renewal-theoretic treatment of unbounded increments and the explicit decomposition in terms of C, C1, and Bhattacharyya parameter are technical strengths. The polynomial-complexity encoder construction is also a practical contribution. The results would be of interest for finite-blocklength feedback coding if the quantization step is shown to preserve the required process properties.
major comments (2)
- [Quantization and continuous-output analysis] The quantization analysis for continuous-output channels claims that B-level quantization satisfying the exact induced-lattice constraint yields capacity loss O(log B/B^2) while enabling the same renewal overshoot bounds as the discrete case. However, the O(log B/B^2) bound controls average mutual information but does not automatically guarantee that the induced increment distribution preserves the submartingale property and overshoot asymptotics needed for the stopping-time controls in the expected decoding time bound; this is load-bearing for the explicit constants.
- [Low-complexity encoder construction] The low-complexity encoder section states that grouping messages by lattice LLRs plus batched correction enforces the exact SED partition at every step. For the submartingale increments to remain compatible with the new overshoot bounds derived from renewal theory, the correction step must not perturb the posterior process; the manuscript does not supply a verification that the batched correction preserves the exact partition balance for the claimed class of channels.
minor comments (1)
- [Abstract] The abstract refers to 'new stopping-time and overshoot bounds' without indicating the precise assumptions on increment tails under which the renewal-theoretic controls apply; a short clarifying sentence would improve readability.
Simulated Author's Rebuttal
We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below with clarifications and will incorporate the necessary additions in the revision.
read point-by-point responses
-
Referee: [Quantization and continuous-output analysis] The quantization analysis for continuous-output channels claims that B-level quantization satisfying the exact induced-lattice constraint yields capacity loss O(log B/B^2) while enabling the same renewal overshoot bounds as the discrete case. However, the O(log B/B^2) bound controls average mutual information but does not automatically guarantee that the induced increment distribution preserves the submartingale property and overshoot asymptotics needed for the stopping-time controls in the expected decoding time bound; this is load-bearing for the explicit constants.
Authors: We agree that explicit verification is needed to confirm that the quantized increment distribution preserves the submartingale property and the renewal-theoretic overshoot bounds. In the revised manuscript we will add a supporting lemma establishing that the exact induced-lattice constraint keeps the quantized channel BMS-symmetric and that the O(log B/B^2) mutual-information loss implies a total-variation bound on the LLR increments sufficient to retain the positive drift C and the moment conditions required by the stopping-time analysis. The lemma will be placed immediately after the quantization-capacity statement. revision: yes
-
Referee: [Low-complexity encoder construction] The low-complexity encoder section states that grouping messages by lattice LLRs plus batched correction enforces the exact SED partition at every step. For the submartingale increments to remain compatible with the new overshoot bounds derived from renewal theory, the correction step must not perturb the posterior process; the manuscript does not supply a verification that the batched correction preserves the exact partition balance for the claimed class of channels.
Authors: The batched correction is a deterministic reassignment performed conditionally on the observed lattice LLR values. In the revision we will insert a short proposition (with proof) showing that this reassignment preserves the exact SED partition balance and therefore leaves the conditional expectation of the posterior-process increments unchanged. The argument relies only on the BMS symmetry and the lattice structure already assumed in the encoder construction; it will appear in the low-complexity-encoder section. revision: yes
Circularity Check
Derivation self-contained via renewal theory; no circular reduction
full rationale
The paper derives non-asymptotic bounds using new stopping-time and overshoot controls for submartingales with unbounded increments, drawing on renewal theory. This is independent of the performance metrics C, C1, Bhattacharyya. The SED partition enforcement via lattice and quantization is presented as a construction with explicit capacity loss O(log B/B^2), not as a fitted input or self-defined term. No self-citations are load-bearing for the central claims, and no parameters are fitted to subsets then renamed as predictions. The bound decomposes explicitly without reducing to its own assumptions by construction.
Axiom & Free-Parameter Ledger
free parameters (1)
- B (quantizer levels)
axioms (2)
- domain assumption Log-likelihood ratios land on a lattice
- standard math Submartingale and random-walk overshoot bounds hold for unbounded increments
Reference graph
Works this paper leans on
-
[1]
The zero error capacity of a noisy channel,
C. Shannon, “The zero error capacity of a noisy channel,” IRE Trans. on Inf. Theory , vol. 2, no. 3, pp. 8–19, Sep. 1956
work page 1956
-
[2]
Sequential transmission using noiseless feedback,
M. Horstein, “Sequential transmission using noiseless feedback,” IEEE Trans. Inf. Theory , vol. 9, no. 3, pp. 136–143, Jul. 1963
work page 1963
-
[3]
A coding scheme for additi ve noise channels with feedback–I: No bandwidth constraint,
J. Schalkwijk and T. Kailath, “A coding scheme for additi ve noise channels with feedback–I: No bandwidth constraint,” IEEE Trans. Inf. Theory, vol. 12, no. 2, pp. 172–182, Apr. 1966
work page 1966
-
[4]
A new method foremploying feedback to improve coding performance,
A. B. Wagner, N. V . Shende, and Y . Altu˘ g, “A new method foremploying feedback to improve coding performance,” IEEE Trans. Inf. Theory , vol. 66, no. 11, pp. 6660–6681, Nov. 2020
work page 2020
-
[5]
Data transmission over a discrete chan nel with feedback: Random transmission time,
M. V . Burnashev, “Data transmission over a discrete chan nel with feedback: Random transmission time,” Problems of Information Trans- mission, vol. 12, no. 4, pp. 250–265, Aug. 1976
work page 1976
-
[6]
A simple derivation of the coding theorem a nd some applications,
R. Gallager, “A simple derivation of the coding theorem a nd some applications,” IEEE Trans. Inf. Theory , vol. 11, no. 1, pp. 3–18, Jan. 1965
work page 1965
-
[7]
Exponential error bounds for erasure, list, and decision feedback schemes,
G. Forney, “Exponential error bounds for erasure, list, and decision feedback schemes,” IEEE Trans. Inf. Theory, vol. 14, no. 2, pp. 206–220, Mar. 1968
work page 1968
-
[8]
Feedback in the non- asymptotic regime,
Y . Polyanskiy, H. V . Poor, and S. V erd´ u, “Feedback in the non- asymptotic regime,” IEEE Trans. Inf. Theory , vol. 57, no. 8, pp. 4903– 4925, Aug. 2011
work page 2011
-
[9]
H. Y amamoto and K. Itoh, “Asymptotic performance of a mod ified Schalkwijk-Barron scheme for channels with noiseless feed back (cor- resp.),” IEEE Trans. Inf. Theory , vol. 25, no. 6, pp. 729–733, Nov. 1979
work page 1979
-
[10]
A simple converse of Burnashev’s reliability function,
P . Berlin, B. Nakibo˘ glu, B. Rimoldi, and E. Telatar, “A simple converse of Burnashev’s reliability function,” IEEE Trans. Inf. Theory , vol. 55, no. 7, pp. 3074–3080, Jul. 2009
work page 2009
-
[11]
V ariable-lengt h codes with bursty feedback,
J. Y . Chen, R. C. Y avas, and V . Kostina, “V ariable-lengt h codes with bursty feedback,” in IEEE Int. Symp. Inf. Theory (ISIT) , Taipei, Taiwan, Jun. 2023, pp. 1448–1453
work page 2023
-
[12]
R. C. Y avas and V . Y . F. Tan, “V ariable-length feedback c odes over known and unknown channels with non-vanishing error probab ilities,” IEEE Trans. Inf. Theory , vol. 71, no. 5, pp. 3271–3286, May 2025
work page 2025
-
[13]
V ariable-length f eedback codes under a strict delay constraint,
S. H. Kim, D. K. Sung, and T. Le-Ngoc, “V ariable-length f eedback codes under a strict delay constraint,” IEEE Communications Letters , vol. 19, no. 4, pp. 513–516, Apr. 2015
work page 2015
-
[14]
V ariable-le ngth convo- lutional coding for short blocklengths with decision feedb ack,
A. R. Williamson, T. Chen, and R. D. Wesel, “V ariable-le ngth convo- lutional coding for short blocklengths with decision feedb ack,” IEEE Trans. Commun., vol. 63, no. 7, pp. 2389–2403, Jul. 2015
work page 2015
-
[15]
Optimizing transmission lengths for limited feedback wit h nonbinary LDPC examples,
K. V akilinia, S. V . S. Ranganathan, D. Divsalar, and R. D . Wesel, “Optimizing transmission lengths for limited feedback wit h nonbinary LDPC examples,” IEEE Trans. Comm. , vol. 64, no. 6, pp. 2245–2257, Jun. 2016
work page 2016
-
[16]
V ariable-lengt h feedback codes with several decoding times for the Gaussian channel,
R. C. Y avas, V . Kostina, and M. Effros, “V ariable-lengt h feedback codes with several decoding times for the Gaussian channel,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT) , Melbourne, Victoria, Australia, July 2021, pp. 1883–1888
work page 2021
-
[17]
——, “V ariable-length sparse feedback codes for point- to-point, multiple access, and random access channels,” IEEE Trans. Inf. Theory , vol. 70, no. 4, pp. 2367–2394, Apr. 2024
work page 2024
-
[18]
V ariab le-length stop-feedback codes with finite optimal decoding times for B I-AWGN channels,
H. Y ang, R. C. Y avas, V . Kostina, and R. D. Wesel, “V ariab le-length stop-feedback codes with finite optimal decoding times for B I-AWGN channels,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT) , Espoo, Finland, Jun. 2022, pp. 2327–2332
work page 2022
-
[19]
On Gaussian MACs with varia ble- length feedback and non-vanishing error probabilities,
L. V . Truong and V . Y . F. Tan, “On Gaussian MACs with varia ble- length feedback and non-vanishing error probabilities,” IEEE Trans. Inf. Theory, vol. 64, no. 4, p. 2333–2346, Apr. 2018
work page 2018
-
[20]
V ariable length codi ng over an unknown channel,
A. Tchamkerten and I. E. Telatar, “V ariable length codi ng over an unknown channel,” IEEE Trans. Inf. Theory , vol. 52, no. 5, pp. 2126– 2145, May 2006
work page 2006
-
[21]
Optimal feedback communica tion via posterior matching,
O. Shayevitz and M. Feder, “Optimal feedback communica tion via posterior matching,” IEEE Trans. Inf. Theory , vol. 57, no. 3, pp. 1186– 1222, Feb. 2011
work page 2011
-
[22]
Optimal reliab ility over a class of binary-input channels with feedback,
M. Naghshvar, M. Wigger, and T. Javidi, “Optimal reliab ility over a class of binary-input channels with feedback,” in Proc. IEEE Information Theory W orkshop (ITW) , Lausanne, Switzerland, Sep. 2012, pp. 391– 395
work page 2012
-
[23]
Extrinsic Jens en–Shannon divergence: Applications to variable-length coding,
M. Naghshvar, T. Javidi, and M. Wigger, “Extrinsic Jens en–Shannon divergence: Applications to variable-length coding,” IEEE Trans. Inf. Theory, vol. 61, no. 4, pp. 2148–2164, Apr. 2015
work page 2015
-
[24]
Sequentia l transmission over binary asymmetric channels with feedback,
H. Y ang, M. Pan, A. Antonini, and R. D. Wesel, “Sequentia l transmission over binary asymmetric channels with feedback,” IEEE Trans. Inf. Theory, vol. 68, no. 11, pp. 7023–7042, Nov. 2022
work page 2022
-
[25]
Achievabl e rates for low-complexity posterior matching over the binary symmetr ic channel,
A. Antonini, R. Gimelshein, and R. D. Wesel, “Achievabl e rates for low-complexity posterior matching over the binary symmetr ic channel,” IEEE Trans. Inf. Theory , vol. 70, no. 8, pp. 5471–5497, Aug. 2024
work page 2024
-
[26]
G. Lorden, “On excess over the boundary,” Ann. Math. Statist. , vol. 41, no. 2, pp. 520–527, Apr. 1970
work page 1970
-
[27]
Absolute estimates for moments of ce rtain boundary functionals,
A. A. Mogul’skii, “Absolute estimates for moments of ce rtain boundary functionals,” Theory of Probability & Its Applications , vol. 18, no. 2, pp. 340–347, 1974
work page 1974
-
[28]
Feller, An Introduction to Probability Theory and Its Applications , 3rd ed
W. Feller, An Introduction to Probability Theory and Its Applications , 3rd ed. New Y ork: John Wiley & Sons, 1968, vol. I
work page 1968
-
[29]
Tracking a random w alk first-passage time through noisy observations,
M. V . Burnashev and A. Tchamkerten, “Tracking a random w alk first-passage time through noisy observations,” The Annals of Applied Probability, vol. 22, no. 5, pp. 1860–1879, Oct. 2012
work page 2012
-
[30]
A combinatorial lemma and its application to probability theory,
F. Spitzer, “A combinatorial lemma and its application to probability theory,” Transactions of the American Mathematical Society , vol. 82, no. 2, pp. 323–339, Jul. 1956
work page 1956
-
[31]
Spitzer’s formula: A short proof,
J. G. Wendel, “Spitzer’s formula: A short proof,” Proceedings of the American Mathematical Society , vol. 9, no. 6, pp. 905–908, Dec. 1958
work page 1958
-
[32]
S. Asmussen and H. Albrecher, Ruin Probabilities, 2nd ed. Singapore: World Scientific, 2010
work page 2010
-
[33]
Quantization of binary-inp ut discrete memoryless channels,
B. M. Kurkoski and H. Y agi, “Quantization of binary-inp ut discrete memoryless channels,” IEEE Trans. Inf. Theory, vol. 60, no. 8, pp. 4544– 4552, Aug. 2014
work page 2014
-
[34]
Quantization of log-likelihood ratios to max imize mutual information,
W. Rave, “Quantization of log-likelihood ratios to max imize mutual information,” IEEE Signal Process. Lett. , vol. 16, no. 4, pp. 283–286, Apr. 2009
work page 2009
-
[35]
On the limits of comm unication with low-precision analog-to-digital conversion at the re ceiver,
J. Singh, O. Dabeer, and U. Madhow, “On the limits of comm unication with low-precision analog-to-digital conversion at the re ceiver,” IEEE Trans. Commun., vol. 57, no. 12, pp. 3629–3639, Dec. 2009
work page 2009
-
[36]
Integer metrics for binary input symmetric output memoryless channels,
N. Binshtok and S. Shamai (Shitz), “Integer metrics for binary input symmetric output memoryless channels,” IEEE Trans. Commun., vol. 47, no. 11, pp. 1636–1645, Nov. 1999
work page 1999
-
[37]
J. L. Doob, Stochastic Processes. New Y ork: John Wiley & Sons, 1953
work page 1953
-
[38]
Williams, Probability with Martingales
D. Williams, Probability with Martingales . Cambridge: Cambridge University Press, 1991
work page 1991
-
[39]
On Chebyshev’s other inequa lity,
A. M. Fink and M. J. Jodeit, “On Chebyshev’s other inequa lity,” Inequalities in Statistics and Probability , pp. 115–120, 1984, Institute of Mathematical Statistics Lecture Notes–Monograph Serie s, V ol. 5. Recep Can Yavas (Member, IEEE) received the B.S. degree (Hons.) in electrical engineering from Bilkent University, Ankara, T urkey, in 2016. He recei...
work page 1984
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.