CS Paper Radar

Random-Sign IBLTs: Calibration-Free Self-Sizing After Decoding Failure

Min Wu

cs.DS ·submitted 2026-10-30 03:43 UTC · v1
theorycode/data

Abstract

We propose the random-sign Invertible Bloom Lookup Table (IBLT) for calibration-free self-sizing after 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 size the second-round table. In standard IBLTs, failure selection couples the overlap bias with the sign composition of the set difference, making practical sizing depend on offline simulation calibration. A shared pseudorandom sign independent of the position mapping removes this dependence while preserving cell fields, field widths, and ideal peeling recovery. We prove exact unbiasedness on every fixed mapping, a Gaussian limit after failure for $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, uniformly over all $d\ge2$, without offline calibration. More than 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 8. The Skellam rule meets the target within sampling error across all 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 less than one microsecond, with total protocol time within 0.5 percent of the Gaussian rule.

Comment
The implementation, frozen experimental configurations, and summary data are available at https://github.com/whitewum/random-sign-artifact

Closest papers

Nearest neighbours by meaning across the whole index.

IBLTs Measure Before They Decode: Self-Sizing Set Reconciliation for Database Consistency Verification

cs.DB cs.DC ·2026-08-27 ·Min Wu, Ji Qi, Zhengsheng Ye, Chengdui Luo, Shudong Lu +1 more
theorycode/data similarity 0.64
Abstract · Code and archived artifact: https://github.com/whitewum/self-sizing

Cross-system data replication pipelines cannot confirm end-to-end consistency from the local guarantees of each hop, so the two endpoints must be compared directly on a periodic basis. Once the rows of a fixed snapshot are normalized into fingerprints, the task reduces to finding the symmetric difference of the two sets. An Invertible Bloom Lookup Table (IBLT) reconciles the sets with communication that grows only with the difference cardinality $d$, independent of table size, but its capacity must be fixed while $d$ is still unknown. Across 41,603 production reconciliations over 90 days, nonzero $d$ spans about seven orders of magnitude, and no reliable empirical constant exists. We show that the count array of an IBLT has already measured $d$ before decoding. The measurement is in-band: it is carried by the recovery sketch itself and adds no bytes dedicated to estimation. A mapping-aware theorem extends the construction to Irregular, Rateless, and MET IBLTs. The protocol reads the estimate only after a decoding failure; we prove that the failure-conditioned lower quantile bounds the risk of underestimation, which gives the second-round capacity a configurable success-probability guarantee. The resulting self-sizing protocol attempts recovery with a small first-round sketch and stops on success; on failure it reads $d$, sizes the second round, and completes reconciliation in at most two rounds. Against a controlled oracle, communication is 1.29-1.47 times that of a scheme given $d$ in advance. Production workload characterization, relational-database replay, and a cross-city KV deployment confirm the end-to-end mechanism. In production on an Oracle-MySQL link, all completed runs succeeded within two rounds, over 90% on the 1-RTT fast path with a single 16 KB sketch.

0.38

Decoding Failure Biases IBLT Count Measurements: A Gaussian-Selection Law at the Peeling Threshold

cs.DS cs.IT ·2026-10-15 ·Min Wu
unusual similarity 0.62
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\ge5$ 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/\sqrt M\to\infty$, 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.

0.27

RCShift: Certifying When Partial Linkage Suffices for Finite-Sample Decisions

cs.AI ·2026-08-11 ·Shuheng Cao, Ruiqi Chen, Zhenhao Zhang, Renjie Cao, Siyu Zhang +3 more
similarity 0.56
Abstract

Systems with costly gold outcomes and cheaper auxiliary observations must decide how much record linkage to retain. Complete pairing retains every joint counter, while separate margins retain none. Neither endpoint is calibrated to a declared finite-sample decision. Universal reconstruction can retain cycle directions invisible to the likelihood-ratio family. Family-exact storage can exceed what the decision requires because certified residual loss may fit within finite-sample slack. We introduce RCShift, which certifies two routes to sufficiency under a declared observation contract. Its exact mode characterizes minimum-cost family-exact storage through LR-visible cycle directions. Its approximate mode bounds reverse Le Cam deficiency. Its integer mode certifies whether a chosen set preserves the full experiment's minimum integer record count at specified size and power. In a rank-two witness, one aligned counter preserves a four-record minimum. An equal-cost misaligned counter and the margins require eleven records, while universal reconstruction requires two counters. A local perturbation has positive reverse deficiency yet retains the four-record minimum. Proof-checked scheduling bounds instantiate the contract before gold computation and yield exact reconstruction on the admitted tree support. RCShift turns partial-linkage storage into decision-calibrated measurement design for the declared family, costs, target, and common strictly positive support.

0.04

Identities, Not Pairs: Distribution-Free False-Accept Control for Embedding-Based Verification

cs.LG stat.ML ·2026-10-26 ·Salim Khazem
code/data similarity 0.55
Abstract

Embedding-based verification often calibrates a false-accept threshold from all impostor pairs among $m$ identities, although these pairs share identities. We characterize a worst-case limit: when hub identities score highly against a fraction $ρ$ of the population, a calibration-only threshold with marginal false-accept rate (FAR) at most $α$ under every identity-exchangeable law reaches the hub score on hub-free calibration sets with probability at most $(m+2)α/(2ρ)$. Uniformly accepting near that score at levels well below $ρ/m$ therefore requires trial information. We propose COVE, which ranks the trial pair among all $N=\binom{m+2}{2}$ pairs formed by augmenting the calibration units with the probe and reference. Under identity exchangeability, its marginal FAR is at most $\lfloorαN\rfloor/N$, with first possible acceptance at $1/N=O(1/m^2)$. The rule also retains this guarantee with a fixed symmetric cohort-normalized score using an independent cohort. On 6 benchmarks and 8 frozen encoders, realised FAR was consistent with the exact bound. Where both valid calibration-only baselines accepted nothing, COVE retained a median $100\%$ of the sampled oracle's true-accept rate over reliable comparisons. In contrast, an empirical quantile over dependent pairs reached 2.87$\,α$ FAR, and a binomial upper confidence bound over pairs missed its nominal 95\% conditional-FAR target in up to 55\% of calibration draws. Symmetric CSLS raised COVE's true-accept rate by up to 4.3-fold in the tested settings. The code is available in https://github.com/salimkhazem/Cove.git

0.37

Replicable Conformal Prediction

cs.LG stat.ML ·2026-08-23 ·Marios Papamichalis, Regina Ruane, Theofanis Papamichalis
similarity 0.53
Abstract · Preprint

Two analysts who calibrate the same predictive model on independent samples will deploy different prediction sets every time, because the calibration threshold inherits the randomness of the data. Wherever deployments must be audited, cached, or approved across sites, this instability is costly: no one can verify that two calibrations produced the same object. We ask two questions: when can independent calibrations yield the identical classifier, and what must that agreement cost? Perfect agreement is impossible, since a procedure that almost always returns one fixed answer cannot remain valid for every distribution, and exact agreement through shared randomness forces the procedure to ignore its data. Sharing a single random seed and rounding the calibrated threshold up to a coarse shared grid resolves the tension: the deployed classifier becomes identical across analysts with any desired probability, coverage guarantees survive, and the price is a quantified increase in set size and calibration data. Matching lower bounds show that no threshold method can pay less, and the method's one tuning constant vanishes asymptotically. Without any shared seed, a fixed grid still confines all analysts to two adjacent classifiers, and no method does better. Replicability also blocks gaming: selecting the most favorable of many recalibrations barely moves a replicable classifier, while the same selection silently undercovers standard conformal prediction. Experiments on real ImageNet outputs, a four-hospital site split, and four language-model families match the theory, including the measured sample-cost frontier.

0.26

Beyond Parallel Blindness: Information Floors and Model Gaps in Block Drafting

cs.LG cs.CLcs.IT ·2026-08-27 ·Xinwei Qiang, Xiang Fang, Chang Chen, Zaifeng Pan, Yue Guan +1 more
code/data similarity 0.52
Abstract

Block drafters propose several tokens in one forward pass, before earlier target tokens are realised. Their rejection mixes two losses: missing within-block path information and imperfect modelling of observable information. Accepted length cannot distinguish them. We separate the two with an information floor, the minimum expected rejection at a specified conditioning order; rejection above this floor is the model gap. Measurements across four domains and four open-weight targets, plus floor estimates on a frontier API target, yield three findings. First, the all-parallel floor reaches $0.286$ at the final slot on Qwen3-4B, limiting even the best proposal to $71\%$ per-slot acceptance. Second, one realised token removes $86$--$100\%$ of this floor, a locality also recovered by an independent mutual-information analysis. Third, current drafters remain far above their floors: the final-slot model gap accounts for $43$--$64\%$ of DFlash rejection and $85$--$92\%$ of DSpark's oracle-conditioned rejection. Guided by this separation of short-range conditioning from proposal quality, we replace a context-independent predecessor correction with a prefix-attention head that reads committed context conditional on the predecessor. With supporting backbone components, the resulting Qwen3-4B drafter improves mean serving accepted length by $3.93\%$ over the released DSpark checkpoint across nine tasks, without increasing the conditioning order. Code and data: https://github.com/tie-pilot-qxw/specfloor; drafter checkpoints: https://huggingface.co/TIE-Pilot/dspark-attnconv-block7-qwen3-4b.

0.66

Signal-Routed Temperature Scaling: Low-Capacity Risk-Conditioned Calibration for Small Validation Budgets

cs.LG cs.AI ·2026-09-30 ·Wenhao Liang, Liangwei Nathan Zheng, Lin Yue, Wei Emma Zhang, Mingyu Guo +2 more
similarity 0.52
Abstract · Preprint. 9 pages main text plus appendix (47 pages total)

When a classifier is recalibrated from only a few thousand held-out examples, the capacity of the calibration map becomes a statistical design choice rather than a purely architectural one: a scalar map can underfit structured residual miscalibration, while a highly adaptive map can be hard to estimate reliably from so small a split. We disentangle the calibration objective from adaptive capacity and propose signal-routed temperature scaling (SRTS-BCE), a 10-parameter, argmax-preserving calibrator that cross-fits a correctness-risk score over six logit statistics and fits one top-label-BCE temperature per $K=3$ risk groups, recovering TvA-TS as its $K=1$ limit. On fine-tuned CIFAR-100 / ViT-B/16, SRTS-BCE reduces $\mathrm{ECE}_{15}$ from 1.65 (scalar TvA-TS) to 0.96, matching the higher-capacity SMART+BCE head (0.95) at the full calibration budget. The two regimes separate as the budget shrinks: at $n=250$ SRTS-BCE beats SMART+BCE on all three CIFAR-100 backbones (the seed-to-draw hierarchical interval excludes zero), whereas the flagship comparison against the scalar remains directional. A protocol-frozen Tiny-ImageNet follow-up reproduces the small-budget separation and exhibits a budget-dependent ranking reversal on Swin-T; matched routing and map controls show that the effect is tied neither to the learned router nor to discrete grouping. Together the results identify post-hoc calibrator capacity as a finite-sample design choice whose preferred level shifts with the amount of available calibration data.

0.30

When Does an AUROC Comparison Survive a Change in Population Mix?

cs.LG cs.CV ·2026-11-15 ·Mahtab Movahhedrad, Hamidreza Hasani Balyani, Seyed Pouyan Mousavi Davoudi
theory similarity 0.52
Abstract · 30 pages, 5 figures. This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after w…

Does an AUROC comparison survive a change in the proportions of tasks, populations, or image corruptions? A pooled-AUROC ranking of failure detectors or uncertainty scores describes one particular mix of groups. We study two fixed scores for a common binary target under mixtures of fixed group-conditional laws. Using the cross-group AUC decomposition, we prove that every rational symmetric quadratic comparison geometry is realizable by finite scalar-score distributions. Universal dominance is thus coNP-hard, and even exhaustive checks of every mixture on fewer than $K$ groups can miss a $K$-group reversal. A grid bound gives a dimension-uniform approximation certificate with sharp $1/m$ order. Common score marginals across groups make the comparison numerator linear, with an error envelope for imperfect alignment. These results yield exact finite-bank audits, explicit reversal mixtures and distances, and simultaneous population statements. For failure detection with a frozen ResNet-50 on ImageNet-C, 15 of 18 confidence-score comparisons win in every corruption family on a discovery split, and all 15 are finite-bank certified over all family mixtures on a held-out split; over all 15 corruption types, of 14 discovery winners the corrected grid certifies 10, leaves 3 unresolved, and finds one confirmation reversal of at least 0.05 AUROC. An audit of all 11,019 released Stable LM 2 12B outputs and 35 uncertainty methods finds 66 confirmation-set comparisons that win within all four tasks yet reverse under mixing. Discovery-fitted marginal rank alignment removes all 66; an alignment-error envelope certifies 83 comparisons. Label checks also change several selected reversals. The findings distinguish robustness of frozen scores from robustness after calibration; they do not establish human-error detection, robustness to unseen corruptions, or generalization beyond the evaluated banks.

0.40