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

arXiv: https://arxiv.org/abs/2609.26207 · HTML: https://mlsanity.com/paper/2609.26207/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 34 references that are in the map.
- First posted on arXiv 11 Aug 2026.

## Builds on (most cited first, 18 of 18)

- [Learning deep representations by mutual information estimation and maximization](https://mlsanity.com/paper/1808.06670/) (2018)
- [Deep Variational Information Bottleneck](https://mlsanity.com/paper/1612.00410/) (2016)
- [MINE: Mutual Information Neural Estimation](https://mlsanity.com/paper/1801.04062/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [On Variational Bounds of Mutual Information](https://mlsanity.com/paper/1905.06922/) (2019)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [On Mutual Information Maximization for Representation Learning](https://mlsanity.com/paper/1907.13625/) (2019)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Graph Information Bottleneck](https://mlsanity.com/paper/2010.12811/) (2020)
- [A Theory of Usable Information Under Computational Constraints](https://mlsanity.com/paper/2002.10689/) (2020)
- [Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning](https://mlsanity.com/paper/2010.12367/) (2020)
- [EDDI: Efficient Dynamic Discovery of High-Value Information with Partial VAE](https://mlsanity.com/paper/1809.11142/) (2018)
- [Active Feature Acquisition with Generative Surrogate Models](https://mlsanity.com/paper/2010.02433/) (2020)
- [Learning Optimal Representations with the Decodable Information Bottleneck](https://mlsanity.com/paper/2009.12789/) (2020)
- [Flow Models for Arbitrary Conditional Likelihoods](https://mlsanity.com/paper/1909.06319/) (2019)
- [Acquisition Conditioned Oracle for Nongreedy Active Feature Acquisition](https://mlsanity.com/paper/2302.13960/) (2023)
- [Certifying Parity Reasoning Efficiently Using Pseudo-Boolean Proofs](https://mlsanity.com/paper/2209.12185/) (2022)

## Abstract (arXiv)

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.