pith. machine review for the scientific record. sign in

arxiv: 2604.03038 · v1 · submitted 2026-04-03 · 💻 cs.IT · math.IT

Recognition: 2 theorem links

· Lean Theorem

Posterior Matching over Binary-Input Memoryless Symmetric Channels: Non-Asymptotic Bounds and Low-Complexity Encoding

Authors on Pith no claims yet

Pith reviewed 2026-05-13 18:46 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords posterior matchingvariable-length feedbacknon-asymptotic boundsBMS channelsSED partitioninglog-likelihood ratioslow-complexity encoderrenewal theory
0
0 comments X

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.

This paper establishes non-asymptotic achievability bounds for posterior matching codes that employ small-enough-difference partitioning over binary-input memoryless symmetric channels. The bounds cover continuous-output channels by removing the prior restriction to bounded log-likelihood ratio increments and decompose the expected decoding time into communication, confirmation, and recovery terms that depend explicitly on the channel capacity C, the KL divergence C1, and the Bhattacharyya parameter. The analysis relies on new stopping-time and overshoot results for submartingales and random walks with unbounded increments drawn from renewal theory. A low-complexity encoder is constructed by assuming log-likelihood ratios lie on a lattice, grouping messages accordingly, and applying batched corrections to enforce the exact partition at every step, yielding polynomial complexity in the number of transmitted bits. For continuous outputs, quantization that induces the required lattice structure incurs a capacity loss of order log B over B squared for a B-level quantizer.

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

Figures reproduced from arXiv: 2604.03038 by Recep Can Yavas.

Figure 1
Figure 1. Figure 1: Rate vs. expected decoding time, BSC(0.11), ǫ = 10−3 . 50 100 150 200 250 E[τ ] 0.24 0.26 0.28 0.30 0.32 0.34 ln M / E[τ ] (nats/ch. use) Converse CAWGN = 0.3368 Clattice = 0.3363 Simulation (B= 31) Thm. 1 (AWGN) Thm. 1 (B= 31) Yavas–Tan [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Rate vs. expected decoding time, BI-AWGN ( [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Rate vs. number of quantization levels B, BI-AWGN (σ 2 = 1, log2 M = 40, ǫ = 10−3 ). V. ANALYSIS OF THE SED SCHEME OVER ARBITRARY BMS CHANNELS We prove Theorem 1 by first establishing N0(M, ǫ′ ) for any ǫ ′ ∈ (0, 1 2 ), then applying the stop-at-time-zero improvement. We begin with four auxiliary results on submartingale stopping times, first-passage times, ruin probabilities, and two-sided exit overshoots… view at source ↗
Figure 4
Figure 4. Figure 4: compares the capacity loss of the exact-lattice BI￾AWGN quantizer against the analytical predictions of The￾orem 6 and Corollary 2. For each odd B from 3 to 101, the optimal spacing δ ∗ and tail label L ∗ tail are computed numerically via Algorithm 5, and the exact induced capacity loss CAWGN − CB,δ∗ is evaluated (blue curve). The red curve plots the leading-order term κAWGN 24 δ ∗2 from (190); by 20 40 60… view at source ↗
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.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

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)
  1. [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.
  2. [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)
  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

2 responses · 0 unresolved

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
  1. 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

  2. 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

0 steps flagged

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

1 free parameters · 2 axioms · 0 invented entities

The central claims rest on the lattice assumption for LLRs and standard submartingale properties for unbounded increments; no new physical entities are introduced.

free parameters (1)
  • B (quantizer levels)
    Number of quantization levels chosen to enforce induced lattice; capacity loss stated as O(log B / B^2)
axioms (2)
  • domain assumption Log-likelihood ratios land on a lattice
    Invoked to allow exact SED partition enforcement by grouping and batched correction
  • standard math Submartingale and random-walk overshoot bounds hold for unbounded increments
    Used to derive the stopping-time and overshoot components of the expected decoding time bound

pith-pipeline@v0.9.0 · 5592 in / 1542 out tokens · 34444 ms · 2026-05-13T18:46:05.832803+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages

  1. [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

  2. [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

  3. [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

  4. [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

  5. [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

  6. [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

  7. [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

  8. [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

  9. [9]

    Asymptotic performance of a mod ified Schalkwijk-Barron scheme for channels with noiseless feed back (cor- resp.),

    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

  10. [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

  11. [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

  12. [12]

    V ariable-length feedback c odes over known and unknown channels with non-vanishing error probab ilities,

    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

  13. [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

  14. [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

  15. [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

  16. [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

  17. [17]

    V ariable-length sparse feedback codes for point- to-point, multiple access, and random access channels,

    ——, “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

  18. [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

  19. [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

  20. [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

  21. [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

  22. [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

  23. [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

  24. [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

  25. [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

  26. [26]

    On excess over the boundary,

    G. Lorden, “On excess over the boundary,” Ann. Math. Statist. , vol. 41, no. 2, pp. 520–527, Apr. 1970

  27. [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

  28. [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

  29. [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

  30. [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

  31. [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

  32. [32]

    Asmussen and H

    S. Asmussen and H. Albrecher, Ruin Probabilities, 2nd ed. Singapore: World Scientific, 2010

  33. [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

  34. [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

  35. [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

  36. [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

  37. [37]

    J. L. Doob, Stochastic Processes. New Y ork: John Wiley & Sons, 1953

  38. [38]

    Williams, Probability with Martingales

    D. Williams, Probability with Martingales . Cambridge: Cambridge University Press, 1991

  39. [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...