CS Paper Radar

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

Min Wu

cs.DS cs.IT ·submitted 2026-10-15 07:30 UTC · v1
unusual

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DS ·2026-10-30 ·Min Wu
theorycode/data similarity 0.62
Abstract · The implementation, frozen experimental configurations, and summary data are available at https://github.com/whitewum/random-sign-artifact

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.

0.34

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

The Optimal Decoder is Tilted Temperature

cs.LG ·2026-10-10 ·Nikolaos Papagiannis, Ananth Grama, Wojciech Szpankowski
theory similarity 0.52
Abstract

Larger sample budgets benefit from higher sampling temperatures in LLMs, but what temperature tuning optimizes and why it works remain poorly understood. We seek to answer these questions: we pose decoding as pass@$k$ maximization subject to two constraints that encode critical decoding failure modes: an entropy floor preventing diversity collapse, and a cross-entropy ceiling preventing implausibility. We prove that this maximization takes the form of a single closed-form conditional sampling rule, the \emph{tilted temperature} $q^\star \propto \bigl(p e^{ηV}\bigr)^{1/T}$. Here, the tilt comes from a verifier potential $V$ that quantifies how likely a partial generation is to eventually pass. Ordinary temperature sampling, verifier-greedy decoding, and reward-tilted policies represent special cases. We further show that, under a natural rule for scaling the diversity budget with sample size $k$, the resulting optimal temperature increases with $k$, turning empirical choice into a theorem. The optimum still needs the unknown verifier potential, which we estimate using two design approaches. In the online setting, our J-EOS algorithm jointly tracks the two constraint multipliers and learns the verifier potential from binary pass/ fail feedback alone. In the offline setting, we show that when the model is calibrated, its log-probability tracks correctness up to an affine map. Under this condition, the tilt collapses into the exponent and the optimum reduces to ordinary temperature sampling. Calibrated Temperature Decoding (CTD) then fits one scalar offline and samples with zero additional inference-time overhead relative to temperature sampling. Building on these decision rules, we design a practical decoding algorithm for code generation and evaluate it alongside CTD on benchmarks including HumanEval and MBPP, showing improvements over standard and adaptive decoding baselines.

0.36

Securing quantum error correction against misleading advice from AI agents

cs.AI quant-phcs.CReess.SY ·2026-09-16 ·A. Barış Özgüler
similarity 0.50
Abstract · 74 pages, 32 figures (10-page main text, 62 pages of Supplemental Material, and 2 pages of references)

Can an attacker turn influence over an artificial intelligence (AI) adviser into a harmful quantum error-correction update? We identify an ambiguity in passive syndrome records that obstructs recovery selection, then show how additional calibration measurements support certified recovery updates under uncertainty and drift. In an odd-distance square toric code with error-free preparation, syndrome measurements, and recovery operations, opposite coherent $X$ rotations produce identical passive syndrome-history distributions. Yet a fixed phase correction can help at one sign and harm at the other. A terminal logical measurement on known encoded calibration states supplies the missing sign information. A separate evaluator accepts an update only when calibration uncertainty and a justified drift bound certify improvement over the current recovery, without assuming that the adviser recommends correctly. In simulated advice attacks, calibration-confidence checks reject harmful proposals while retaining beneficial updates under honest advice. We derive sufficient limits on calibration age that require improvement through deployment. In matched simulations, a validated channel-specific bound retains more beneficial updates than the general bound after accounting for evaluation time, while preventing the tested harmful activations under the stated drift assumption. A separate surface-code experiment includes stochastic circuit faults and noise changing during acquisition. Deterministic controllers achieve at least as many beneficial updates with the same observations. Violating the drift assumption permits harmful acceptance in the toric experiment. The results identify information required for recovery selection, establish conditional guarantees against harmful updates, and quantify the recovery improvements forgone through conservative acceptance.

0.45

A Sign Law for Entropy Drift under Sampler Mismatch in RLVR

cs.LG cs.AI ·2026-10-25 ·Zhiyuan Wang, Jacob Steeves, Chang Liu
theory similarity 0.50
Abstract

In reinforcement learning with verifiable rewards (RLVR), whether entropy rises or falls can depend on choices that matter little under exact sampling, such as whether over-length responses are masked or counted as failures. We trace this to sampler mismatch: rollouts are drawn with top-k/top-p truncation or at a temperature the learner does not apply. We prove that a constant advantage shift then changes the entropy of a softmax policy, at first order and in expectation, with a sign fixed by the sampler. Positive shifts sharpen the policy under any sampler whose likelihood ratio to the policy increases with token probability, including top-k, top-p, min-p, and temperatures below one, and flatten it under flatter samplers. In group-based RLVR with token-level losses, the baseline-dependent part of this drift is set by the token-weighted net advantage, which masking and failing can push to opposite signs. The rest comes from a covariance between advantages and the sampler's sharpness gap and feeds back on itself: in a two-level model, a push away from a sharper sampler takes off in finite time, while a pull toward it saturates. On a 2B model, the entropy slope is linear in shifts of the net advantage under truncated sampling and indistinguishable from flat under exact sampling. Token-level importance ratios leave 98% of the drift, and four clipped minibatch updates per batch amplify it sevenfold. In 100-step runs, a net-zero baseline only delays an entropy explosion, and entropy raised at the start keeps rising only under truncation; cancelling the first-order drift at every step keeps entropy bounded without changing the learner. On a 9B reasoning model forked from an uncorrected run, zeroing the net advantage or renormalizing the learner raises held-out accuracy after ten steps by 8.2 and 8.8 points over the uncorrected rule, with no difference under exact sampling.

0.35

Phantom Gains: Auditing Self-Improvement Against a Measured Null

cs.AI cs.CL ·2026-08-20 ·Cheng Xu, Nan Yan, Liming Chen, M-Tahar Kechadi
code/datahighly cited similarity 0.50
Abstract · Code and evaluation artifacts are available at https://github.com/chengxuphd/phantom-gains

Whether a language model has improved itself is increasingly judged not by mean accuracy but by which individual problems it gains and loses. Tracking these transitions means differencing two noisy estimates, leaving them vulnerable to measurement artifacts. Auditing three rounds of rank-$32$ LoRA self-training on Qwen3-8B against a frozen control pushed through the identical pipeline, we identify seven measurement failures, each of which inverts a reported finding when its control is absent. Several are standard practice. A ledger built on a single greedy decode manufactures capability changes on an untrained model, largely an artifact of inference batching; the expansion statistic separating acquisition from sharpening assigns that same model a rate of $0.280$. The natural threshold repair does not survive replication: estimated across the frozen comparisons such a design already contains, its null stays non-zero. We replace it with a per-problem exact test against a pooled baseline under false-discovery-rate control, which detects nothing on any held-out replicate and is unchanged under the multiple-testing rule, error rate and pool size. Applied to a ladder of arms matched in stream, volume and evaluation, the audit finds that external distillation improves problems the base model rarely reaches while three forms of self-training do not; a regression rejects this asymmetry as a by-product of distillation's larger overall gain ($p < 10^{-8}$). On the far smaller set of problems the base model never reaches, the evidence is inconclusive, while self-training corrupts problems solved at baseline at rates well above the measured floor. Transition-level auditing therefore requires a separately measured null for every statistic it reports: nulls that cost no new experiments, built from baseline replicates a multi-arm study already owns, though not from as few as most possess.

0.66

Verification Pulses and the Cost of Escaping Wrong Consensus

cs.LG ·2026-09-24 ·Shivam Gupta
code/data similarity 0.50
Abstract · 18 pages, 5 figures; code and raw experimental records: https://github.com/shi1720/verification-pulses

External verification can correct individual outputs while leaving a self-reinforcing population in the basin of a wrong consensus. We study how the timing and addressing of a fixed verification budget affect recovery in an asynchronous binary register. For a general nonlinear response, we derive the minimum fuel required to cross a basin boundary under a peak verification constraint. For a finite population, an exact birth--death calculation gives the probability of subsequent wrong consensus after a pulse. Our main asymptotic result identifies the critical budget window: a leading term $N\log(x_0/b)$ and a correction of order $\sqrt N$, with separate variance contributions from repeated verification targets and autonomous amplification after verification stops. The distinction is substantial: with 16 majority-updated slots and 14 initially wrong, 9 random checks cross the mean-field budget threshold, whereas 23 are required for 95% eventual recovery in the exact model. A prospectively specified experiment records 13,392 language-model responses, including calibration and 108 held-out trajectories. Calibration produces different fitted response regimes, but all four adjusted schedule-comparison intervals include zero. A distributional audit also finds that modest mean-prediction error can conceal a large underestimate of terminal consensus occupancy. The results support risk-calibrated reset scheduling under a specified update contract, while explicitly separating it from distinct-target checking and unrestricted evidence broadcast.

0.45

When Accuracy Gaps Fail to Certify: Auditing Cross-Domain Recalibration of LLM Judges

cs.LG ·2026-08-23 ·Fariya Afrin, Ibne Farabi Shihab
theory similarity 0.50
Abstract

A scalar recalibration map fitted for an LLM judge on one task can fail when the task distribution changes, but the source-target accuracy gap is often treated as a proxy for that failure. We test what this gap can predict and what it can certify across thirteen judges, two generators, eight domains, and 1,176 predeclared transfers. After accounting for mean score shift, the gap yields a population lower bound on target calibration error, yet identical gaps can induce opposite transfer outcomes. Exact importance weighting recovers target proper loss under covariate shift, so failure of an estimated weighting pipeline does not by itself establish conditional shift. A finite-sample simultaneous lower certificate converts the population bound into a one-sided rejection rule using audit labels disjoint from evaluation outcomes. The leak-free gap correlation is 0.25 (95% CI [-0.09, 0.55]), falls to 0.09 on the second generator, and does not support a generator-invariant association. The certificate retains nominal coverage but has power 0.13 even at m=1024, whereas target-domain temperature scaling with 16 labels reaches harm rate 0.09, compared with 0.34 for source-fitted Platt scaling. Accuracy gaps are therefore weak warning signals for scalar probability transfer, not deployment certificates.

0.26