CS Paper Radar

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

Min Wu, Ji Qi, Zhengsheng Ye, Chengdui Luo, Shudong Lu, Zhengyang Wei

cs.DB cs.DC ·submitted 2026-08-27 02:17 UTC · v4
theorycode/data

Abstract

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.

Comment
Code and archived artifact: https://github.com/whitewum/self-sizing

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

Fidelity Collapses with Table Size, Not Turn Count: Delivery Architecture in a Deployed Tool-Using Agent

cs.CL cs.AI ·2026-10-30 ·Tung Thanh Hoang
published similarity 0.60
Abstract · Non-archival paper at the Second Workshop for Research on Agent Language Models (REALM) at EMNLP 2026. 21 pages, 5 figures

When a multi-turn agent delivers a tool's structured records into the model's context and re-emits them each turn, every turn can corrupt data the tool computed correctly. We measure this in a production award-travel agent: two architectures over identical frozen payloads, lineage-matched prompts and sampling, differing only in delivery architecture. SYNTHESIS feeds full record sets into the planner's context and answers follow-ups in-head; BYPASS, the deployed system, keeps records in session state, translates follow-ups into arguments for a deterministic filter, and delivers rows over a typed side channel. Across 24 dialogues (339 scored turns per condition), BYPASS scores 92.3% of turns fully correct, SYNTHESIS 45.7% (paired gap +46.6pp [+35.7, +57.1]). Varying delivered-table size by capture date, SYNTHESIS collapses from near-perfect at 10 rows or fewer to 8% or less beyond about 74 rows. On a content-controlled prefix ladder the collapse threshold orders by model capability, from under 10 rows (GPT-4o-mini) to about 198 or more (Gemini 2.5 Pro), while BYPASS stays size-flat for all four models. The collapse is expensive: beyond 100 rows, where almost no SYNTHESIS answer is correct, each correct one costs roughly 200x BYPASS's flat \$0.012. Practitioners converged on typed side-channel delivery for rendering, not correctness; we show it was, unknowingly, also a correctness decision.

0.40

Checkpoint Reload Explains Most of the Measured State Gap in Two State Discovery Reproductions

cs.LG ·2026-10-26 ·Weijia Han, Lisha Qu
published similarity 0.56
Abstract · Equal contribution, 11 pages, 3 figures, 7 tables. Accepted at the NeurIPS 2026 Workshop on Foundation Models for Temporal Systems (FMTS 202…

Temporal models that maintain per-sequence latent states during training must reconstruct those states when the stored table is unavailable at inference. This creates a basic consistency question: do the reconstructed states agree with those formed during training? We study this question for State Discovery in World Machine, which updates stored states in parallel each epoch but performs inference by sequential rollout from an all-zero start. On Toy1D, we analyze two paired-checkpoint runs whose decoded-state MSE is 27 to 36 percent above the published value. We compare the stored table with rollouts under the best-validation checkpoint reloaded after training and the last-epoch weights that wrote the table. Matching the rollout to the table-writing weights removes 90 to 91 percent of the mean per-dimension Wasserstein-1 distance. Causal distillation and frozen SD updates do not satisfy their pre-specified criteria under either checkpoint. Overall, checkpoint reload accounts for most of the measured gap in these runs.

0.32

Deterministic Temporal Reconciliation for Effective-Dated Identity Lifecycle Events

cs.SE cs.DC ·2026-09-12 ·Pramod Ubbala
benchmark similarity 0.56
Abstract · 13 pages, 3 figures, 4 tables. Synthetic benchmark code and data included as ancillary files

Identity lifecycle automation processes workforce changes that carry two distinct notions of time: when a business fact becomes effective and when an authoritative source last revised it. Corrections, cancellations, future-dated changes, duplicate delivery, and out-of-order arrival can therefore produce divergent account states when processors rely on transport order or effective time alone. This paper presents a deterministic temporal reconciliation method for effective-dated identity events. The method separates logical business facts from their physical revisions, deduplicates exact replays, selects the authoritative revision of each fact using transaction-time freshness, removes canceled facts, and then applies surviving facts in valid-time order. We establish permutation invariance, replay idempotence, revision dominance, and deterministic snapshot construction under explicit source assumptions. A reproducible synthetic fault-injection benchmark compares the method with arrival-order, effective-time, and transaction-time processing. Across 250,000 generated identity histories and 1,585,589 delivered records, the proposed method reconstructed the separately retained authoritative final state in all tested cases. At 75% delivery disorder, exact-state accuracy was 42.35% for arrival-order processing, 85.38% for effective-time sorting, 76.61% for transaction-time sorting, and 100% for the proposed method. A separate 40,000-permutation experiment produced the same final state for every tested permutation under the proposed reconciliation contract.

0.30

Scaling the Lightning Network with Practical Set Reconciliation

cs.NI ·2026-08-16 ·Xingyu Chen, Anish Sinha, David Starobinski, Ari Trachtenberg
published similarity 0.55
Abstract · Published in the 2026 IEEE International Conference on Blockchain and Cryptocurrency (ICBC 2026)

The Lightning Network (LN) utilizes gossip to share network topology, channel announcements and updates, and node announcements among its local constituents. Yet, our measurements show that this flooding-based gossip reconciliation is fundamentally inefficient. We propose, instead, to use set reconciliation protocols for sharing this information, and we systematically evaluate existing approaches under realistic network conditions. We further propose ADAPTIVEIBLT, a novel adaptive IBLT (Invertible Bloom Lookup Table) protocol with a partial-decoding enhancement. By simulating reconciliation in Core-Lightning and evaluating real gossip snapshots, we demonstrate the practical benefits of reconciliation in scaling gossip reconciliation from hours down to a few minutes.

0.28

Generalized DBLog: A Verified Contract for Interleaving Copied Rows with a Change Log

cs.DB cs.DCcs.LO ·2026-09-08 ·Andreas Andreakis
theory similarity 0.55
Abstract · 40 pages, 6 figures. Formal verification artifacts: https://doi.org/10.5281/zenodo.22643866

Change-data capture (CDC) feeds downstream systems like caches, search indexes, and data warehouses from a database's log of committed row changes. When bootstrapping, adding a table, or repairing downstream data, a pipeline must also copy existing rows. Merging this copy with the active log introduces the copy-to-log handoff problem. Changes must not fall through a gap, and older copied state must not overwrite a newer logged update or resurrect a deleted row. DBLog, developed at Netflix, addressed this problem by reading tables in chunks and interleaving those reads with the live log. Watermarks identify the changes that overlap each read, and the log wins when a copied row is stale. Debezium and Flink CDC have since adapted this design. Earlier work proved that applying the original algorithm's copied rows and logged changes in their emitted order reconstructs the source's rows, including the effect of every logged insert, update, and delete processed. Generalized DBLog asks when the same result holds for variants of that design. We state the conditions the source and capture implementation must satisfy. Once copying and reconciliation are complete, we prove that the result holds across all selected tables and key ranges even when their rows were read at different times. A single database snapshot is not required for the copy. Further logged changes advance the reconstructed state one event at a time. We establish these guarantees for classic watermarking, Debezium's signal-table and read-only modes, Flink CDC's parallel chunks, reads and dumps tied to exact log positions, and engine-consistent backups whose log position lies within known bounds. The complete theory is machine-checked in Isabelle/HOL, its core independently verified in Lean 4, and the protocols are also examined by bounded model checking in TLA+.

0.57

Revision-Bound Evidence Cuts: Authenticated Queries and Contextual Witness Capacity

cs.CR cs.DB ·2026-10-27 ·Faruk Alpay, Taylan Alpay
similarity 0.55
Abstract · 54 pages, 10 figures

Authentic records can support unauthorized narratives when their qualifications, query scope, or counterevidence are silently dropped. We present revision-bound evidence cuts, a framework for authenticating both supporting and opposing inference obligations across changing source versions. Signed complete-update frontiers permit transport of unaffected certificates, alternative-cut recovery, and an exact certified-reuse radius given by a frontier-hypergraph transversal number. Their source obligations induce an integral model of context-bound authorization. To secure database-derived claims, we introduce an authenticated relational query contract that binds original source records, complete selected bags, counting units, parameters, and aggregates independently of execution strategy. A full-source verifier checks 16,824 Chogha Mish records across SQLite scans, indexes, and materialized views; three valid strategies agree and eight contract/view mutations are rejected. A separate 340-row NISP cohort shows that changing the admitted weighting rule can reverse a comparison while preserving every source record. A frozen English text-to-frame compiler produces qualified evidence receipts, with linguistic accuracy evaluated separately from cryptographic integrity. We also separate logical-source from transport commitments so lossless re-encoding need not invalidate unchanged scientific evidence. The SCENE prototype evaluates signed revisions, authenticated queries, scoped disclosures, and adversarial mutations at scales reaching one million source records. These guarantees rely on declared policies and independently pinned trust roots; they authenticate specified computations and obligations, not historical truth, complete counterevidence, or institutional endorsement.

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