We introduce the random‑sign Invertible Bloom Lookup Table (IBLT) that enables calibration‑free self‑sizing after a decoding failure. In a two‑round set reconciliation protocol, the receiver uses the failed first‑round table to estimate an upper bound on the unknown difference size $d$ and sizes the second‑round table accordingly. Standard IBLTs couple the overlap bias with the sign composition of the set difference, making practical sizing depend on offline simulation calibration. By sharing a pseudorandom sign independent of the position mapping, this dependence is removed while preserving cell fields, field widths, and ideal peeling recovery. We prove exact unbiasedness for every fixed mapping; a Gaussian limit after failure when $d\gg\sqrt{M}$; and a discrete limit dominated by duplicate edge pairs at smaller scales, where $M$ is the number of cells. These results yield a Skellam upper‑bound rule whose conditional miss rate is asymptotically at most the target risk for all $d\ge2$, without offline calibration. Over 500 million paired decoding trials and end‑to‑end protocol experiments support the design. For small differences, the Gaussian rule’s conditional miss rate exceeds the target by more than a factor of eight, whereas the Skellam rule meets the target within sampling error across 189 tested load configurations. Total two‑round communication approaches that of an oracle using the true $d$ in the same protocol. With fixed deployment parameters, precomputed table lookup reduces sizing to sub‑microsecond latency, and total protocol time stays within 0.5 % of the Gaussian rule.
Review