CS Paper Radar

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

Shuheng Cao, Ruiqi Chen, Zhenhao Zhang, Renjie Cao, Siyu Zhang, Lingwei Dang, Jiajun Zhang, Tingting Dan

cs.AI ·submitted 2026-08-11 04:16 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

DataCupid: Stable Matching Repair for Training Data Acquisition with Delayed Feedback

cs.LG cs.IT ·2026-10-09 ·He Sun, Junyuan Mao, Wenhao Jiang, Mingjun Xiao, Shinan Liu
theory similarity 0.57
Abstract · 2 figures, 8 tables

Matching repair after utility changes can reuse valid observations, but new evaluations must respect matching capacity and may return out of order. We study announced invalidations with bounded, possibly reward-dependent reporting delays and pending evaluations that do not occupy future matching capacity. Residualload repair (RLR) combines sound outcome certificates with batched matching schedules for unequal sample deficits. Its complete dyadic quota schedule admits a sharp issue-round bound with coefficient cb < 1.607 relative to the terminal residual endpoint load, together with separate delay and evidence-lifetime bounds. RLR-P monitors complete issue-order prefixes without changing the sampling plan before acceptance. With a deterministic pure oracle, a single-repair coupling from the same drained initial state guarantees no increase in certification time, issued observations, or time to a reusable checkpoint. We also derive an information-load lower bound. On fixed priority-star markets with unknown Bernoulli gaps, PrioritySearch attains the history-adjusted first-order constant for expected certification time as δ {\sim} 0, under hypothesis-independent linear history scaling and sublogarithmic reporting delays. Paired simulations and measured-feedback replay quantify the trade-offs: in the replay, RLR-P has lower mean capped update-certification time than a monitored width-based baseline, at higher oracle CPU cost.

0.24

Verification Pulses and the Cost of Escaping Wrong Consensus

cs.LG ·2026-09-24 ·Shivam Gupta
code/data similarity 0.57
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

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

cs.DS ·2026-10-30 ·Min Wu
theorycode/data similarity 0.56
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

ULPack: Reference-Conditioned Lossless Compression of Checkpoint Trajectories

cs.LG ·2026-10-09 ·Aniket Srinivasan Ashok
similarity 0.55
Abstract

Studying model training requires checkpoint trajectories, whose storage cost limits temporal resolution. Although adjacent checkpoints are numerically close, existing lossless codecs either operate on XOR bit patterns or ignore trajectory-specific conditional structure. We show that a reference weight's exponent predicts the bit length of its displacement in ordered floating-point space without side information. We introduce \textbf{ULPack}, a lossless codec which exploits this dependence by conditioning entropy models of ordered-integer residuals on the reference exponent. Across bfloat16, float16, and float32 trajectories, ULPack reduces storage by up to 27\% against ZipNN, 21\% against zstd-19, and 11.5\% against FM-Delta. Across two dense trajectories, compression improves as updates shrink and reference conditioning strengthens, while near uniform low-order bits set the remaining compression floor and earlier checkpoints add little information.

0.26

State-Aware Activation Recomputation with Replay Contracts and Selective Preservation

cs.AI ·2026-10-31 ·Annan Zhang, Shengjie Song, Wenshuai Yao, Lihao Zhang, Tianmiao
similarity 0.55
Abstract

Activation recomputation saves accelerator memory by replaying forward segments during the backward pass, but replay is only correct if it sees the state the original forward pass saw. Mutable buffers, aliased bytes and random-generator state can change in between, so re-executing unchanged code can differentiate a different computation. We make this state explicit. A versioned replay contract specifies what replay must restore, and a joint planner chooses, per segment, between activation retention, whole-buffer snapshots and selective-region preservation, charging each option its measured memory and recovery cost. Independent derivative and byte-level checks validate the contract, and a Torch/JAX cohort retains all 5,900 execution records, including matches, rejections and divergences. On frozen sparse-write H100 workloads, each measured over fifty fresh processes, joint planning reduces paired step time by 18.16% against a correctly costed eager/whole planner at a 44 GiB budget (approximate 97.5% ratio interval $[.8172,.8195]$). At 32 GiB, where the eager/whole planner has no feasible static policy, joint planning is 4.98% faster than fixed regions at 29.94 rather than 26.20 GiB. A complete CIFAR-100 dense-queue application runs seven methods for 100 encoder and 25 probe epochs at six training seeds, with byte-identical test scores within each seed. There, joint planning uses 22.41% more allocated memory than whole snapshots, with a process-time geometric-mean ratio of 1.0080 (seed range $[.9845,1.0191]$). Together, the results map where selective preservation pays off: sparse writes with large activations benefit, while in the dense-queue workload whole snapshots use less allocated memory.

0.26

Sampling headroom is not selection gain: a compute-value audit of test-time scaling for video world models

cs.CV cs.AI ·2026-09-06 ·Yuhua Jiang, Junjie Lu, Feifei Gao
theorycode/data similarity 0.55
Abstract · 33 pages

Test-time scaling (TTS) can improve generation only when additional compute produces better candidates and the system can reliably identify them. This distinction is especially important for video world models, where a wider sample pool may contain stronger rollouts without improving the output that is ultimately selected. We introduce the Compute-Value Audit (CVA), a sequential framework that asks whether extra sampling creates opportunity, observable signals provide a reliable state, that state supports a beneficial action, and the resulting gain exceeds the full entry fee of generation and verification. On 192 Physics-IQ scenes, expanding the pool from 4 to 16 candidates increases oracle quality by +9.23 IQ (95% CI [+7.44, +11.14]), but Flow, Cycle, and VideoReward fail to recover this headroom reliably. Across three generators, none of twelve adaptive-depth policies outperforms uniform compute; they recover only 42-69% of the measured entry fee. A matched-60-NFE Predict-and-Perturb intervention on VideoPhy2 is likewise negative across three fresh-seed replicas. These negative results are not universal: anchor-explorer passes all four stages in a sparse PRM800K setting, MMLU-Pro exposes the gap between predictive state and useful action, and a privileged paired future establishes a positive video upper bound. Together, these results show that sampling headroom has deployment value only when it can be converted into a reliable decision whose benefit survives the complete compute charge. Code is available at https://github.com/YuhuaJiang2002/sampling-headroom-is-not-selection-gain.

0.57

Sufficient quantum provenance: retained fields and certified recording precision

cs.ET quant-ph ·2026-10-07 ·George Kourousias, Sergio Carrato, Roberto Pugliese, Aljoša Hafner, Francesco Guzzi +3 more
similarity 0.54
Abstract · v3: Revised abstract and introduction; clarified relation to prior work; added references. Scientific results unchanged

Quantum executions sharing a provenance record can produce different output distributions. We ask which execution details to retain, and at what precision, to guarantee agreement within a declared Hellinger tolerance. Under a specified channel model, we combine independent stochastic mechanisms and coherent rotation differences to certify recording precision without output simulation or explicit dependence on register dimension. For four-qubit quantum approximate optimization at depth one, a 13-bit comparison record suffices at tolerance 0.05 over a declared continuous noise range, uniformly in programmed angles for each fixed task. Pairwise separation constraints characterize sufficient field sets on finite context classes, exposing omissions that pass individually but fail jointly. Separately, six-qubit hardware measurements over six tested contexts certify minimum label counts of two for raw outputs and one after a fixed decoder, at tolerance 0.15 with 97\% simultaneous confidence under stationary independent shots. Execution records thereby carry checkable agreement guarantees.

0.41

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