cs.DSNov 9, 2026

How Far Must a Test Explore? Certifying Composable Read-Write Interfaces from Their Own Random Edits

Authors: Jiaxuan Guo, Xingyu Ren, Jingxin Yang, Youran Sun, Haizhao Yang

Organizations: Stanford University · The Chinese University of Hong Kong · University of Maryland, College Park

Abstract

Random tests of stateful code check laws, like reading back a written value, at states that random writes reach. The laws hold at every state exactly when the code behaves like a record with hidden data, so a pass is taken as evidence. This can fail: the laws can hold at every sample while the code is far from any record. The laws are local, but behaving like a record is global. Self-testing and stability theorems bridge this gap when the query distribution is controlled by the tester or preserved by the tested maps, but here it is generated by the tested writes, which need not be invertible. We ask how far a test must explore. An interface has mm binary variables, each with a read and two writes; in a record, reads return their bits and writes set only their bits. Samples are the ends of geometric runs of mean ℓ\ell of uniformly random writes from a start distribution; a tester adds its own write chains of depth dd. The distance is the least, over records with hidden data, of the largest probability that a read or write differs from it at a sample. From one start state, law checks at O(m2log⁡m/ε)O(m^2\log m/ε) samples certify, at fixed confidence, any threshold εε after geometric runs of every positive mean, while runs of fixed positive length can pass at distance 1/21/2. For the worst start distribution, take ε=m−βε=m^{-β} with fixed 0<β≤10<β\le1. For d≤cmd\le cm with fixed c<1/2c<1/2, a polynomial budget of samples and writes exists exactly when ℓ=Ω(m)\ell=Ω(m), where law checks suffice. With no runs, the least depth for this budget is (1/2+o(1))m(1/2+o(1))m. Counting samples alone, in the worst case at ε=1/(32m)ε=1/(32m) and d≤m/16d\le m/16, the critical mean for a polynomial budget is Θ(mlog⁡(m/d)/log⁡m)Θ(m\log(m/d)/\log m), by exhaustive search. So one start state needs only law checks, and the worst case at these thresholds needs exploration linear in mm if writes are counted.

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Replicable Composition

    Apr 12, 2026Kiarash Banihashem, MohammadHossein Bateni, Hossein Esfandiari +2Sample ComplexityML Reproducibility

  2. Atoms, Not Knowledge: What Production-Scale Addressed-Memory Writes Deposit

    Oct 18, 2026Wei Gao, Cheng Tian, Duan Yang +1Memory-Augmented Language ModelsPersistent Memory for Language Models

  3. Checking Leakage Witnesses versus Certifying Bounded Non-Leakage

    Sep 26, 2026Chao Feng, Burkhard StillerLanguage Model AuditingPrivacy Leakage in Language Models