One Reference Bit and the Statistical Cost of Paired-Only Audits

Paired audits may retain only whether two responses differ, discarding the responses themselves. We quantify the statistical cost of this record constraint in a two-hypothesis binary response model. Each acquired response costs one query and is independently flipped with probability $\eta \in (0,1/2)$; comparisons are exact XORs of already acquired responses, not additional measurements. Under a common raw-response budget, we optimize the sampling allocation, pairing graph, and causal adaptive policy. For fixed designs, we derive the exact finite-budget minimax risk and show that the optimal error exponent is half the raw-record exponent. For causal policies whose actions depend only on released differences, we prove that an anytime, noise-rate-free rule—sample the less certain latent bit—is minimax optimal at every horizon. Its exponent is strictly between the fixed-design and raw-record exponents. Retaining one already acquired noisy reference response instead orients any connected difference record, reconstructs all raw responses, and attains the raw-record exponent without another query. Thus adaptivity recovers part, but not all, of the information lost by paired-only storage. The retained bit is an observed noisy response, not a true label or an oracle.