Decoding Failure Biases IBLT Count Measurements: A Gaussian-Selection Law at the Peeling Threshold
Abstract
In a self-sizing set-reconciliation protocol, a small first-round Invertible Bloom Lookup Table (IBLT) sketch attempts peeling decoding; after failure, the protocol estimates the difference count d from the count energy and sizes the second round from a lower quantile of the measurement. This quantile must be computed conditionally on failure: the measurement and peeling success are determined by the same random mapping, so conditioning can shift the measurement law. In the ideal peeling model, inside the critical window where failure has nondegenerate probability, the standardized energy and a statistic of the unsigned mapping that governs the peeling outcome (the precritical score) have a joint Gaussian limit with correlation ηkρ2, ρ being the sign imbalance and ηk a closed-form constant. The measurement conditional on failure is thus a bivariate normal truncated to a half-plane, which we call the Gaussian-selection law. Since ηk changes sign between k=4 and k=5, under one-sided imbalance the unconditional threshold undercovers exactly when k≥5 and is conservative for k=3,4. The key tool is a quenched CLT for a signed quadratic form on a random overlap graph; under asymptotically balanced signs, conditioning on any unsigned mapping event that is permutation-invariant and has probability bounded away from zero leaves the standard normal limit unchanged. After failure the protocol observes the total sign; inverting the selection law yields an upper confidence bound for d, asymptotically conservative in the critical window and, when d/√M→∞, along the whole load axis. The experiments use analytic constants, none fitted; the unconditional threshold carries a selection error that does not vanish with scale, while the corrected selection-law threshold matches per-configuration empirical quantiles.
Related
- The Value of Duplicate Measurements When Decoding Second-Order Reed-Muller Codes
- Quantum simultaneous decoding via pretty-good measurements of tilted states
- Chordal Codes: Code Construction and Efficient Gaussian-Elimination Decoding
- The injectivity threshold of a Gaussian ReLU layer
- Temporal Degeneracy Limits Message Passing Decoding of QLDPC Codes Under Repeated Noisy Syndrome Measurements
BibTeX
@misc{wu2026decoding,
title = {{Decoding Failure Biases IBLT Count Measurements: A Gaussian-Selection Law at the Peeling Threshold}},
author = {Min Wu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.21418},
eprint = {2610.21418},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.21418},
}
RIS
TY - UNPB
TI - Decoding Failure Biases IBLT Count Measurements: A Gaussian-Selection Law at the Peeling Threshold
AU - Min Wu
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.21418
UR - https://arxiv.org/abs/2610.21418
AB - In a self-sizing set-reconciliation protocol, a small first-round Invertible Bloom Lookup Table (IBLT) sketch attempts peeling decoding; after failure, the protocol estimates the difference count d from the count energy and sizes the second round from a lower quantile of the measurement. This quantile must be computed conditionally on failure: the measurement and peeling success are determined by the same random mapping, so conditioning can shift the measurement law. In the ideal peeling model, inside the critical window where failure has nondegenerate probability, the standardized energy and a statistic of the unsigned mapping that governs the peeling outcome (the precritical score) have a joint Gaussian limit with correlation η_kρ^2, ρ being the sign imbalance and η_k a closed-form constant. The measurement conditional on failure is thus a bivariate normal truncated to a half-plane, which we call the Gaussian-selection law. Since η_k changes sign between k=4 and k=5, under one-sided imbalance the unconditional threshold undercovers exactly when k≥5 and is conservative for k=3,4. The key tool is a quenched CLT for a signed quadratic form on a random overlap graph; under asymptotically balanced signs, conditioning on any unsigned mapping event that is permutation-invariant and has probability bounded away from zero leaves the standard normal limit unchanged. After failure the protocol observes the total sign; inverting the selection law yields an upper confidence bound for d, asymptotically conservative in the critical window and, when d/√M→∞, along the whole load axis. The experiments use analytic constants, none fitted; the unconditional threshold carries a selection error that does not vanish with scale, while the corrected selection-law threshold matches per-configuration empirical quantiles.
ER -