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

Apr 12, 2026

Replicable Composition

Replicability requires that algorithmic conclusions remain consistent when rerun on independently drawn data. A central structural question is composition: given kk problems each admitting a ρρ-replicable algorithm with sample complexity nn, how many samples are needed to solve all jointly while preserving replicability? The naive analysis yields O~(nk2)\widetilde{O}(nk^2) samples, and Bun et al. (STOC'23) observed that reductions through differential privacy give an alternative O~(n2k)\widetilde{O}(n^2k) bound, leaving open whether the optimal O~(nk)\widetilde{O}(nk) scaling is achievable. We resolve this open problem and, more generally, show that problems with sample complexities n1,…,nkn_1,\ldots,n_k can be jointly solved with O~(∑ini)\widetilde{O}(\sum_i n_i) samples while preserving constant replicability. Our approach converts each replicable algorithm into a perfectly generalizing one, composes them via a privacy-style analysis, and maps back via correlated sampling. This yields the first advanced composition theorem for replicability. En route, we obtain new bounds for the composition of perfectly generalizing algorithms with heterogeneous parameters. As part of our results, we provide a boosting theorem for the success probability of replicable algorithms. For a broad class of problems, the failure probability appears as a separate additive term independent of ρρ, immediately yielding improved sample complexity bounds for several problems. Finally, we prove an Ω(nk2)Ω(nk^2) lower bound for adaptive composition, establishing a quadratic separation from the non-adaptive setting. The key technique, which we call the phantom run, yields structural results of independent interest.
Oct 18, 2026

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

Deterministic hash-addressed conditional memory permits local post-hoc knowledge injection. Extending arXiv:2610.21553's bounded-feasibility audit rejecting under-specified generality claims with repaired probes and training-dose/capacity axes, we give, to our knowledge, the first production-scale write-content verdict. We test 124M-7B self-trained/publicly pretrained beds, Qwen3.8-Flash-Next-FP8 (176.95B; 320,001,536 FP8 rows), and DeepSeek-V4.1-Flash. Write coverage requires a sufficiently trained backbone prior, full-width readout, trainable gates; undertrained-bed intervention confirms a threshold, not a slope. At fixed budget, coverage falls from 98% (50 facts) to 12.7% (1,000); table size is not binding. Two-hop composition does not exceed the independent single-hop baseline (26% observed vs 25% expected; 15% lexical-distortion floor). Synergy remains absent across dose/load in two independent bed families. A 28-percentage-point in-context gap (given vs recalled intermediates) localizes failure to retrieval-for-reasoning, not gate access. Writes are independently retrievable, precisely addressable, reversible atoms, not composable into reasoning. A layered protocol, the first, to our knowledge, to cover compositionality in behavioral memory evaluation, separates baseline, synergy and distortion floor. Any addressed/key-value memory must report coverage, synergy ratio and distortion rate before deployment claims. Composition must be system-orchestrated; multi-constraint queries should explicitly chain written atoms. In-context controls show given intermediate entities are exploited at twice the implicit rate. Production load fits exponential interference (R2=0.98R^2=0.98); its mechanism, between budget dilution and write interference, remains open. All numbers are recomputed from archived raw logs/JSON; a fresh 52-target production rerun gives 52/52, exactly matching archived baselines.
Sep 26, 2026

Checking Leakage Witnesses versus Certifying Bounded Non-Leakage

When a language-model audit finds no leak, what is needed to certify non-leakage? We study guarantees over a declared prompt domain under an executable leakage criterion and decoding rule. For general bounded polynomial-time evaluators, a supplied leaking execution is polynomial-time checkable, while leak existence is \NP-complete and deterministic certification is \coNP-complete. Exact stochastic certification is \coNP\PP\coNP^{\PP}-complete at every fixed rational cutoff in (0,1)(0,1). Restricting the computation can change these bounds. For example, certification is in \coNP\ when all randomness is a terminal draw from an efficiently computed finite probability table. Attention models admit polynomial-time certification when local dependency windows of logarithmic length precede one global head, given deterministic decoding, fixed vocabulary, exact rational weighted means, a direct binary affine readout and finite-automaton prompt domains. A construction with two global layers instead makes certification \coNP-complete over template domains, with one head per layer, polynomial width, logarithmic precision and an inverse-polynomial logit margin. Planted-secret experiments measure what finite audits miss relative to complete references. Among 30 secret--model-state pairs that leak under greedy single-prompt execution on their secret's 4,096-prompt domain, uniformly selecting 256 recorded evaluations per pair misses every leak for an expected 41.06%41.06\% of these pairs. Batched and single-prompt checks disagree on one complete-domain decision among all 48 fine-tuned pairs, while a same-order repeat reproduces every single-prompt output. These results distinguish computational conditions for certification from the coverage and execution conditions needed to interpret a negative audit.