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

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

GUOJX @ STANFORD . EDU

Stanford University

Xingyu Ren The Chinese University of Hong Kong

Jingxin Yang

arXiv:2611.11899v1 [cs.DS] 9 Nov 2026

Stanford University

Youran Sun Haizhao Yang 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 m 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 ℓ of uniformly random writes from a start distribution; a tester adds its own write chains of depth d. 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(m2 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/2. For the worst start distribution, take ϵ = m−β with fixed 0 < β ≤ 1. For d ≤ cm with fixed c < 1/2, a polynomial budget of samples and writes exists exactly when ℓ = Ω(m), where law checks suffice. With no runs, the least depth for this budget is (1/2 + o(1))m. Counting samples alone, in the worst case at ϵ = 1/(32m) and d ≤ m/16, the critical mean for a polynomial budget is Θ(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 m if writes are counted. Keywords: property testing; self-testing; algebraic laws; read–write interfaces; random walks

1. Introduction Random tests check stateful code in the way Claessen and Hughes (2002) check queues: they run random sequences of operations from a start state and check laws or a model at the reached states. For m binary variables, each with a read and two writes, the laws say that a written value is read back (success), that writing back the current value changes nothing (write-back), that of two writes to one variable the second wins (overwrite), that a write to one variable keeps the others (preservation), and that writes to different variables commute (commutation) (Foster et al., 2016). For one variable, success, write-back and overwrite are the PutGet, GetPut and PutPut laws of a very well-behaved 1

G UO R EN YANG S UN YANG

total lens (Foster et al., 2007), which the Haskell lens library checks with QuickCheck (Kmett and Charles, 2026). The laws hold at every state exactly when the code behaves like a record of m bits with hidden data, which no read reveals and no write changes (Proposition 9), so a pass is taken as evidence of this behavior. A one-bit record may have the states A0, A1, B0 and B1: reads and writes act on the bit, and the letter is hidden data. But a pass checks only the reached states: each law is local, checked at one state with at most two writes in a row, while behaving like a record is a global property of how all states fit together. Self-testing and stability theorems justify this interpretation in other settings. There, rare failures of local laws imply closeness to an exact solution of the laws (Blum et al., 1993; Rubinfeld and Sudan, 1996; Becker and Mosheiff, 2021; Becker and Chapman, 2023). Their analyses control the distribution at which the laws are checked. The homomorphism test of Blum et al. (1993) checks f (xy) = f (x)f (y) at a uniformly random pair of group elements x, y, so each of x, y and xy is uniform. In stability theorems, the tested permutations preserve the counting measure. In random tests of stateful software, even in a record, setting a variable to 0 maps two states that differ only in this variable to the same state, so the image of a sample under a write need not be distributed like a sample. The writes under test also generate the sample distribution. We ask how far beyond its samples a test must explore before a pass certifies that an interface, an implementation of these reads and writes, is close to a record, and we call such a record a composable interface (as in database view updates, Bancilhon and Spyratos, 1981). A sample is the end of a run: a geometric number of uniformly random writes from a state drawn from a start distribution. We measure exploration by the mean ℓ of the runs and the depth d of the tester’s own chains of writes from each sample, and closeness by the distance of Section 2. ℓ

one start state

worst start distribution, ϵ = m−β

ℓ

ℓ ≥ αm: law checks certify (Thm. 2) Θ(m) ℓ = o(m), d ≤ cm: no polynomial budget (Thm. 2)

law checks certify at every ℓ > 0 (Thm. 1)

audit certifies (Thm. 4)

ℓ∗m d

cm

m 16

√ m + O( m log m) 2

d

Figure 1: The depth d ≥ 2 and the run mean ℓ, schematic and not to scale, for fixed 0 < β ≤ 1, α > 0 and 1/16 < c < 1/2; Theorem 2 holds for every 0 < c < 1/2. Budgets count samples and writes. The dashed curve ℓ∗m = m log(m/d)/ log m counts samples alone, at ϵ = 1/(32m): polynomially many samples do not suffice below its order and suffice at its order (Thm. 5). The boundary for d − m/2 = o(m) and 0 < ℓ = o(m) is open.

From one start state, law checks at the ends of geometric runs certify closeness at every positive mean, while for m ≥ 2 runs of a fixed positive length can pass at distance 1/2 (Theorem 1). A geometric run can stop after any of its writes, so the sample distribution puts weight on every prefix of a run. 2

H OW FAR M UST A T EST E XPLORE ?

For the worst start distribution at polynomially small thresholds, exploration linear in m is necessary. At each threshold ϵ = m−β with fixed 0 < β ≤ 1, a polynomial budget of samples and writes forces ℓ = Ω(m) as long as d ≤ cm for a fixed c < 1/2 (Theorem 2). Either kind of exploration suffices. Law checks after runs of linear mean meet the budget (Theorem 2). So does an audit with no runs, which walks from each sample to a target label and checks that flips rejoin this walk, at depth about m/2, the least depth at these thresholds (Theorem 4). At ϵ = 1/(32m) and d ≤ m/16, counting samples alone lowers the necessary mean by a factor of at most log m. A tester that exhausts the ball of radius d around each sample needs only ℓ = Θ(m log(m/d)/ log m), at a cost in writes exponential in d (Theorem 5). So the two budgets separate: at d = ⌊m/16⌋ and ℓ = m/ log m, polynomially many samples certify at every threshold m−β , and polynomially many samples and writes do not. Figure 1 draws these regions. 1.1. Related work Self-testing and stability. In a composable interface, the flips, which write the opposite value of one variable, commute with each other, each flip undoes itself, and flipping a nonempty set of variables changes every state (Proposition 9). So testing composability resembles testing stability for the group {0, 1}m (Chapman and Lubotzky, 2025). Chapman et al. (2026) ask how far unitary matrices U1 , . . . , Um that nearly satisfy the relations of the flips, Ui2 = I and Ui Uj = Uj Ui , are from unitary matrices V1 , . . . , Vm of the same size that satisfy them exactly. For n × n matrices, they take as squared distance the sum of the squared moduli of the entries of the difference, divided by n. Suppose that, for a relation drawn as an equal mixture of a uniform Ui2 = I and a uniform Ui Uj = Uj Ui with i ̸= j, its two sides are at mean squared distance at most η. Then some exact solution has Ui and Vi at mean squared distance O(min{1, mη}) for a uniform i, and this order is best possible. Their lower bound uses permutations that flip an extra bit conditionally on another bit, close to the twisted interface of Section 4. Our setting differs in two ways. A flip of a general interface need not be a bijection, and the writes under test generate the distribution under which failures are counted. Testing from samples. Distribution-free testers measure the distance under an unknown distribution from which they sample, and they may also query the tested function at any point (Halevy and Kushilevitz, 2003). In the vertex-distribution-free model of Goldreich (2019), testers may be assumed, at a constant-factor cost, to query only vertices that they have sampled or received as answers. Our testers obey the same restriction for states. In the huge-object model of Goldreich and Ron (2023), a tester draws samples of long strings and probes each at locations of its choice, and the tester with the fewest samples need not be the one with the fewest queries. Our two budgets are these two measures for probes that are writes, and Section 5 separates them at the thresholds m−β for the worst start distribution. Local exploration from randomly selected vertices is a standard method in bounded-degree graph testing (Goldreich and Ron, 2002; Bender and Ron, 2002), and our depth is such an exploration radius, bounded as a function of m alone. Identity testers that decide from a single trajectory whether a symmetric Markov chain equals a known reference chain also face states that the trajectory rarely visits (Daskalakis et al., 2018; Cherapanamjeri and Bartlett, 2019); here the chain is generated by the interface under test. Conformance testing. Conformance testing of finite-state machines decides from input and output sequences whether a black box behaves like a given specification machine, and the length of 3

G UO R EN YANG S UN YANG

the sequences is a central quantity, bounded in terms of the number of states (Vasilevskii, 1973; Chow, 1978; Lee and Yannakakis, 1996). Here the laws are the only specification, and exploration is measured against the number of variables, not of states.

2. Interfaces, laws, runs and distances Interfaces and laws. An interface I = (r, T ) supplies readers and setters on a finite set S of states, for m ≥ 1 binary variables. A reader ri : S → {0, 1} reports the value of variable i; a setter Ti,a : S → S is the operation intended to write a ∈ {0, 1} to it. The label r(x) = (ri (x))i∈[m] collects all readings at x. The flip of variable i is Fi (x) = Ti,1−ri (x) x, the write of the opposite value. A composable interface I˜ acts like a record with hidden data. Formally, a bijection ϕ : S → {0, 1}m × Ξ gives r̃i (x) = ui and ϕ(T̃i,a x) = (u[i 7→ a], z) when ϕ(x) = (u, z). Here u[i 7→ a] replaces coordinate i of u by a. Fixing z gives a cube, the 2m states ϕ−1 ({0, 1}m × {z}), one of each label, such as {A0, A1} in the one-bit record of Section 1. A composable interface on S exists exactly when 2m divides |S|, with M = |S|/2m cubes. Fixing the variables and values in a law gives a law instance. The following laws hold at every state x of a composable interface, for all i ̸= j and a, b, with maps composed from right to left. • success, ri (Ti,a x) = a; write-back, Ti,ri (x) x = x; overwrite, Ti,a Ti,b x = Ti,a x; • preservation, rj (Ti,a x) = rj (x); commutation, Ti,a Tj,b x = Tj,b Ti,a x. Conversely, satisfying all five laws everywhere makes an interface composable (Proposition 9; Power and Shkaravska, 2004). Runs and samples. A random edit applies a uniformly random setter. It sends a distribution µ to P µP , where P = (2m)−1 i,a Ti,a . The start distribution ν specifies where runs start: a run draws its start state from ν, makes L independent random edits, and returns its final state as a sample. For geometric run lengths of mean ℓ > 0, put q = ℓ/(1 + ℓ) and Pr(L = s) = (1 − q)q s , s ≥ 0. The sample distribution is X µℓ = (1 − q) q s νP s , (1) s≥0

For measures, µ ≤ µ′ means µ(X) ≤ µ′ (X) for every X

and µ0 = ν. ⊆ S. The measure µℓ satisfies µℓ = (1 − q)ν + q µℓ P , hence µℓ P ≤ (1 + 1/ℓ)µℓ . More generally, µ is λ-subinvariant if µP ≤ λµ, for λ ≥ 1: one random edit increases the probability of any set by at most a factor λ. Violation rate and distances. Fix a probability measure µ on S. Let N be the set of states at which some law instance fails. The violation rate is γµ (I) = µ(N ), the probability that checking all law instances at one sample rejects. The disagreement of a candidate I˜ with I is the largest probability that a reader or setter differs,  ˜ = max max µ{ri ̸= r̃i }, µ{Ti,a ̸= T̃i,a } . Rµ (I, I) i,a

(2)

The distance Dµ (I) is the least disagreement over composable interfaces on S, which exist when 2m divides |S|. The distance Dµ∞ (I) is the infimum of the disagreement over composable interfaces on finite sets S ′ ⊇ S, measured under µ on S with an output outside S counted as a disagreement, so Dµ∞ ≤ Dµ . The theorems below hold for both distances: an upper bound speaks of Dµ only when 2m divides |S|, and every lower bound holds for both. For Dµ , the audit of Section 4 adds 4

H OW FAR M UST A T EST E XPLORE ?

a bridge check: it draws a uniform label and, when the depth tests allow, attempts to reach a state with that label and checks, through intermediate states, that the audit’s walk sends this state to the same state as the sample (Appendix C.2). The distance on S needs this check because a composable interface on S itself cannot add states to supply missing labels. Subscripts ℓ mean evaluation at µℓ : we write γℓ , Dℓ and Dℓ∞ . All logarithms are natural. Definition 1 (Testers) (i) Access. A tester holds states only as opaque handles: the samples of µ that it draws and the outputs of its setter calls, also called writes. On any held state it may call readers and setters, and it may compare two held states for equality. Its transcript lists its draws, calls and comparisons, with the reader outputs and comparison outcomes, and numbers each handle by its first appearance. (ii) Depth. A held state has depth j if the shortest chain of the tester’s setter calls that leads from a sample to this state has j calls. A setter call has depth one more than its argument, determined when the call is made. A tester has depth d on an input if all its setter calls on this input have depth at most d. (iii) Law checks. A law-check tester evaluates law instances at samples and rejects only when one of them fails. It may decide how many samples to draw and which instances to evaluate from the outcomes so far. It calls readers and setters only on samples and on outputs of the setter calls of these evaluations, so its depth is 2. (iv) One-sided error. A tester has one-sided error if it accepts every composable interface with probability 1. Depth measures how far calls reach from a sample, not how many calls there are. A call has depth one more than its argument even if it returns a state that the tester already holds, such as its argument. In a composable interface, writing the current value of a variable is such a call. Later calls use the shortest chain of calls that has reached the returned state. For instance, take a sample x with r1 (x) = 0 and call T1,1 on x, then T1,0 , then any setter, each on the previous output. In a composable interface, the first output is a new state of depth 1 and the second is x again, so the three calls have depths 1, 2 and 1. If the first two outputs are new states, the calls have depths 1, 2 and 3.

01

11

T1,0

T2,1 00

T1,1

01

11

T2,0

10

00

z=0

10 z=1

Figure 2: The eight states (u, z) of the interface defined below, each shown by its label u1 u2 , in two layers by the hidden bit z. Lines join states that differ by one flip. The thick path is (00, 0) → (10, 0) → (11, 0) → (01, 1) → (00, 1).

Certification and budgets. A tester certifies Dµ < ϵ with confidence 1 − δ if it accepts every composable interface with probability at least 1 − δ and rejects every interface with Dµ ≥ ϵ with probability at least 1 − δ; define this for Dµ∞ in the same way. Each theorem below certifies the 5

G UO R EN YANG S UN YANG

distance under the sample distribution µℓ of its own mean, and Section 6 compares the measures of different means. A budget counts samples, or samples and setter calls. It does not count the writes that generate a sample, ℓ in expectation (Lemma 7), and lower bounds leave reader calls, comparisons and computation free. For sequences ℓm ≥ 0 and dm ≥ 2 and thresholds ϵm , a polynomial budget is a constant A and, for all large m, a tester of depth at most dm on samples of µℓm that certifies at ϵm with confidence 2/3 for all interfaces and start distributions, and uses at most mA counted operations in expectation on every composable interface. A quantity is superpolynomial if, for each A, it exceeds mA for all large m. A bound Dµ ≤ Kγµ yields a law-check tester from ⌈K log(1/δ)/ϵ⌉ samples (Appendix A). Reads and state identity. Success and preservation speak only about reads, while write-back, overwrite and commutation compare states. The interface of Figure 2 separates the two. Its states are S = {0, 1}2 ×{0, 1} with r(u, z) = u, and its setters are T1,v (u, z) = (u[1 7→ v], z⊕(v⊕u1 )u2 ) and T2,v (u, z) = (u[2 7→ v], z). All its reads are correct: after any sequence of writes, the label is the one that a record predicts. But the thick path of the figure returns to label 00 with the hidden bit toggled, and a composable interface that kept these four writes would return to the state where it started. So the distance is at least 1/8 under the uniform measure, which is stationary (Proposition 42). For ℓ > 0, along independent uniform random writes from a sample of µℓ , reads alone are controlled by the violation rate, with no factor of m (Proposition 41). So the exploration question below asks about state identity: whether two write sequences from the same sampled state that predict the same label reach the same state. In the interface of Figure 2, commutation fails at every state, so one law check finds the failure. The instance of Section 4 hides it.

3. One start state Theorem 1 (One start state) Let m ≥ 2. (a) Let the start distribution be a point mass ν = δo . There is a coefficient K = O(m2 log m), explicit in Appendix G.8, such that for every interface and every ℓ > 0, Dℓ ≤ min{1, Kγℓ } (with Dℓ∞ in place of Dℓ if 2m ∤ |S|; Section 2). So, for 0 < ϵ, δ < 1, law checks at ⌈K log(1/δ)/ϵ⌉ independent samples of µℓ certify Dℓ < ϵ with confidence 1 − δ. (b) For every integer k ≥ 1, there are a set S of states with 2m | |S|, an interface on S and a point mass ν such that the sample distribution νP k of runs of exactly k writes has γνP k = 0 and ∞ =D DνP k νP k = 1/2. Why part (b) holds. Figure 3 shows the core, for m = 2, with samples uniform on x and w. All law instances hold at x and at w. Take a composable interface, even with additional states, that keeps the four bold entries T1,1 x = y, T2,1 x = v ′ , T2,0 w = y and T1,0 w = v. A setter of a composable interface keeps the cube of its argument, changes only its own variable, and leaves its argument unchanged exactly when the variable already has the written value. So x, y and w lie in one cube, drawn in Figure 3(c). There y = T1,1 x = T2,0 w gets the label 10, by the values these setters write, and as T1,1 changes x and T2,0 changes w, x and w get the labels 00 and 11. Then v ′ = T2,1 x and v = T1,0 w both get the label 01, which is impossible as v ′ ̸= v. So the distance is at least 1/2. The law instances at x never reach v, and those at w never reach v ′ , so no law instance compares these two states. For k = 1, add a start state o with Ti,0 o = x and Ti,1 o = w: every run of exactly one write ends at x or w (Appendix G.9). 6

H OW FAR M UST A T EST E XPLORE ?

(a) 01

01

v′

v

T2,0

(b) T1,0

w 11

T2,1

T2,0

x

y 10

00

T1,1

(c) state r1 r2 T1,0 T1,1 T2,0 T2,1 laws failing x w y v′ v

00 11 10 01 01

x v x v′ v

y w y w w

x y y x x

v′ w w v′ v

none none commutation overwrite overwrite

01: v ′ , v

11: w

00: x

10: y

Figure 3: An interface with two variables whose square of labels has a split corner, reached at two different states v ′ and v. (a) Labels r1 r2 of the states x, y, v ′ , v, w; the samples are the shaded states x and w. Thick arrows are the bold entries of (b), and the gray arrow is T2,0 v = x. (b) The images under each Ti,a and the laws failing at each state. (c) The cube that a composable interface keeping the thick arrows needs, each cell giving a label and its states; the shaded cell holds both v ′ and v.

Why part (a) holds. In a composable interface, a run from o stays in one cube, and its end state is determined by the predicted label B, obtained by applying the run’s writes to r(o) as coordinate writes. The proof shows an approximate version for a general interface in four steps (Appendix G). • The sample distribution weights every prefix of a run. A geometric run makes its (s + 1)-st write with probability q s+1 , from a state distributed as νP s . So by (1), the expected number of writes that a run makes at states of a set X is ℓµℓ (X), and the probability that a run makes a write at a state of N is at most ℓγℓ . Runs of exactly k writes have no such property: for k = 1 above, write-back fails at o, but every run ends at x or w. • Runs with one predicted label usually end at one state. A run meets a failure with a variable j if a law instance that involves a setter of j fails at one of its states. Otherwise the last write to j can be moved to the front and the other writes to j deleted, so these writes matter only through Bj . For instance, let a run make the writes T1,1 , T2,0 , T1,0 and T2,1 in this order, and take j = 1. Commutation at T1,1 o and overwrite at o give T1,0 T2,0 T1,1 o = T2,0 T1,0 T1,1 o = T2,0 T1,0 o, so the run ends at T2,1 T2,0 T1,0 o. Now let writes arrive in continuous time at rate 1, and stop the run at an independent exponential time ι of mean ℓ, its stopping time, which gives the same sample distribution. Given B and ι, the histories of the variables, the times and values of the run’s writes to each variable, are independent. So, by the Efron–Stein inequality (van Handel, 2016), which bounds a variance by resampling one independent variable at a time, two independent runs with the same B and ι end at different states with probability at most the sum over j of the probability that resampling the history of j alone, with the same Bj , changes the end state. The j-th term compares the run with the run whose history of j is resampled, and these two end at different states only if one of them meets a failure with j. • The stopping time matters little. A cube has one state of each label, so given B the end state must also vary little with ι. Given B, the conditional histories at different stopping times can be coupled so that the write counts of the variables are pure-birth processes with rates at most 2/m. At a birth the history of that variable gains a write and may redraw its previous last value, and the end state is unchanged if the old run meets no failure with that variable (Appendix G.2). Appendix G.3 controls the law of ι given B through an integral-kernel bound, which turns this rate into a bound on the variation over ι. 7

G UO R EN YANG S UN YANG

• One state per label forms a cube. For each label, choose among the states that read this label the one where runs with this predicted label most often end, weighting a run by 1/(1 − e−ι/m ), one over the probability, given ι, that it writes a given variable, and choose o for r(o). These states have distinct labels, so they fit into one cube, and filling the other positions, including labels that no state reads, gives the composable interface. A setter Tj,a at a sample X acts like resampling the history of j with last value a, and the weight offsets the factor by which this conditioning can raise the probability of a history (Appendix G.4). If neither run meets a failure with j, then Tj,a X is the end of the new run, whose predicted label is B[j 7→ a], so Tj,a X is usually the chosen state of this label, which is the output of the composable setter.

4. Many start states Theorem 2 (Worst start distribution) Fix 0 < β ≤ 1 and 0 < c < 1/2, and let ϵm = m−β and 2 ≤ dm ≤ cm. For both distances, a polynomial budget of samples and setter calls at ϵm exists if and only if ℓm = Ω(m). (a) Necessity. If ℓm = o(m), every tester of depth at most dm that certifies at ϵm with confidence 2/3 for all interfaces and start distributions uses a superpolynomial expected number of samples and setter calls on some composable interface and start distribution, even if it learns the length of each run. (b) Sufficiency. Let m ≥ 2, α > 0 and Kα = 4α(2e)2/α m1+2/α . If ℓ ≥ αm, then for all 0 < ϵ, δ < 1, law checks at ⌈Kα log(1/δ)/ϵ⌉ samples of µℓ certify with confidence 1 − δ, at depth 2 and with at most 2m2 + 2m setter calls per sample. Also Dµ ≤ Kα γµ for every (1 + 1/(αm))-subinvariant measure µ. The necessity extends beyond these thresholds. For a fixed C > 1, the conclusion of (a) holds for 1/(32m) ≤ ϵm ≤ (log m)−C and ℓm = o(m log(1/ϵm )/ log m) (Proposition 33(b)); a matching upper bound at this scale is open. So if (log m)C ≤ ℓm = o(m), there is no polynomial budget at the threshold 1/ℓm either. Why the necessity holds. The proof builds one family of interfaces at distance above ϵm , and the worst start distribution comes from this family (Appendix E). • One twist. Split 8J variables into two blocks of 4J, with values u′ and u′′ . In the twisted interface, a setter of the first block also toggles a hidden bit when it moves |u′ | across 2J while |u′′ | ≥ 2J. So commutation between the blocks fails only where both Hamming weights are near 2J (Figure 4). • No composable interface, even with additional states, can match the twist. The loop of Figure 4 writes each coordinate it touches once to 1 and once back to 0, and |u′ | crosses 2J upwards while |u′′ | = J and downwards while |u′′ | = 3J. So it returns to its start label with the hidden bit toggled, and a composable interface that kept every write would return to the start state. Averaging over such loops, for ℓ = o(m) and every composable interface, the expected number of setters of the two blocks that differ from it at a sample is at least a positive constant. • A frozen block hides the twist. Each start state has a frozen block of weight J or 3J. Suppose that its threshold function, f1 = 1{|u′ | ≥ 2J} or f2 = 1{|u′′ | ≥ 2J}, keeps its initial value at every label that the tester queries from a sample. If the first block is frozen, or the second with f2 = 0, no setter toggles the hidden bit. If the second block is frozen with f2 = 1, a setter of 8

H OW FAR M UST A T EST E XPLORE ?

|u′′ | z toggles 3J 2J J |u′ | J

2J

3J

Figure 4: The Hamming weights of the two blocks of 4J variables of one group, with the thresholds 2J (dashed). Dark square, enlarged: {2J − 1, 2J}2 , where commutation between the blocks can fail. Thick: the start states, each with a frozen block of weight J or 3J, and the loop along them in the order bottom, right, top, left. The hidden bit z toggles only where the top edge crosses the threshold (dot). Appendix E.1 writes out J = 1.

the first block toggles the hidden bit exactly when it changes f1 , so the hidden bit plus f1 stays constant. Either way, up to this renaming the tester sees a composable interface (Lemma 28). • The distance. For one twist at a random place, dividing the expected number above among all 2m setters gives a disagreement lower bound of only order 1/m. So the instance uses Ng = ⌊m/(8J)⌋ disjoint groups of 8J variables, each with its own twist, hidden bit and frozen block. Their expected numbers add up before the division, which gives a lower bound of order Ng /m, or 1/J. With J = ⌊1/(512ϵm )⌋, this lower bound exceeds ϵm (Lemma 27). At thresholds above order 1/m, this J is much smaller than m, and the instance hides these small blocks. • Copies separate samples. A state of the instance consists of a copy, a label in {0, 1}m and one hidden bit for each group. Each of 2m copies of the states, closed under the setters, draws its own groups and blocks, and polynomially many samples lie in distinct copies except with exponentially small probability. On this event, no state is reached from two samples, and one sample says nothing about where the blocks of another lie. • A mask keeps the tester from aiming at a block. Each copy also draws a mask, a random vector added to the labels before the weights are computed. After averaging over the mask, the label of a sample is uniform and independent of the groups, the blocks, and the start label and edits relative to the mask, given the run length. On the composable interface the answers depend only on the labels of the samples and the setters called. So the coordinates that the tester flips are independent of the groups and the frozen blocks, however it chooses them (Lemma 30). • The margin: half the dimension. Flipping d coordinates of a sample flips 4Jd/m coordinates of a frozen block in the mean. At a start state of weight J, a quarter of the coordinates of this block are ones, so each flip in this block raises its weight by 1/2 in the mean, and the mean weight rises to J + 2Jd/m. Call the distance from the mean weight to the threshold the margin. Then flips multiply the margin by 1 − 2d/m, for every J. This is a positive constant for d ≤ cm with c < 1/2, and the margin vanishes only when d is about m/2. • Time: long runs, and where log(1/ϵ) comes from. A run lowers the margin as well. Each write to a group replaces a coordinate by a fair bit, so t̂ such writes multiply the margin by (1 − 1/(8J))t̂ , and the margin falls to the fluctuations of the weight after order J log J of them. The number of writes to one group in a run is geometric with mean ℓ0 = 8Jℓ/m, so with 9

G UO R EN YANG S UN YANG

q0 = ℓ0 /(1 +ℓ0 ) it exceeds t̂ with probability q0t̂+1 ≤ exp[−(t̂ +1)/(1 + ℓ0 )]. For ℓ > 0 and t̂ of order J log J, this exponent has order min{J log J, m log J/ℓ}, so the tail is superpolynomially small for ℓ = o(m log J/ log m) once J log J/ log m → ∞. As J has order 1/ϵm , this is the scale stated after Theorem 2, and at ϵm = m−β it reads ℓ = o(m). These bounds hold state by state and group by group, so a union over them needs a polynomial budget (Lemma 31). Why long runs suffice. A word is a sequence of setters. The path of x under W = Et · · · E1 with Es = Tis ,as is x0 = x, xs = Es xs−1 , and the fiber of x is W −1 (W x). In a composable interface, a word that writes every variable sends two states to the same state exactly when they lie in one cube, so fibers serve as candidate cubes. With the old value bs = ris (xs−1 ), step s passes if r(xs ) = r(xs−1 )[is 7→ as ],

Tis ,bs xs = xs−1 .

(3)

Where all steps pass, x 7→ (r(x), W x) is injective, so a fiber fits into a cube at its labels. Take a word of t = ⌈m log(2m)⌉ random setters, conditioned on writing every variable, an event of probability at least 1/2. Before conditioning, the state Pafter s random edits has distribution µP s ≤ λs µ, so the path meets N with probability at most 2 s<t λs γµ . For µℓ , λ = 1 + 1/ℓ, and λt is polynomial exactly when ℓ ≳ m. If the path avoids N , commutation moves any setter along it until the first write to its variable absorbs it, so every setter at x stays in the fiber (Lemma 13). With added states, each fiber takes a cube of its own, and this finishes the proof for D∞ . On the same states there are only M cubes, so the proof keeps the M heaviest fibers and bounds the probability that this loses (Lemma 11). Here the µ-mass of a fiber W −1 (z) counts only its states whose path avoids N , and if weights κ(z) ∈ [0, 1] on the fibers of positive mass sum to at most M , this loses at most the mean of 1 − κ(W x) for x ∼ µ besides the paths that meet N . Lemma 3 (Capacity) A transition of Ti,a at x is kept if it passes (3), with Ti,a x = x when a = ri (x). The capacity κ◦ (z) of a state z is the probability that a second random word, drawn like the first, makes only kept transitions along the path of z. For every label b, the capacities of the states with label b sum to at most M . If the transition of Ti,a from x to y ̸= x is kept, then the transition of Ti,ri (x) from y back to x is kept. The random word has the same law as its reverse, as its setters are independent and uniform before the conditioning, and reversal keeps the event of writing every variable. So a walk along kept transitions leads from x to y with the same probability as from y to x, and this symmetry replaces the invariance of the counting measure, which permutations have and general setters lack. By this symmetry, the sum of these capacities equals the sum over all states x of the probability that such a walk from x ends at label b, at most 2−m each as the written label is uniform (Appendix D.2). Passing paths end at the label that W writes, so Lemma 11 applies, losing at most the mean of 1 − κ◦ (W x) over the covering word W and x ∼ µ. As a transition fails to P be kept only where a law other than commutation fails, this mean is at most 2λt times the bound 2 s<t λs γµ on paths that meet N . Adding the earlier path loss gives Kα (Appendix D.4). An audit replaces the run by its own walk from each sample. Fix a target label â and put Wâ = Tm,âm · · · T1,â1 . The path check follows the path of a sample x under Wâ and rejects if a step fails (3). Each step that writes a new value first checks the label of its output and then calls the undo, the setter of the old value, whose output must be the state before the step. The flip check rejects if write-back fails at x, if a flip yi = Fi x has a wrong label, or if the path of yi fails (3) or 10

H OW FAR M UST A T EST E XPLORE ?

does not join the path of x at step i. In a composable interface, step i is the first write to variable i and erases the flip, so the two paths meet there. Passing both checks puts every setter at x in the fiber of x with the updated label (Lemma 15). The calls of these checks have depth at most |r(x)⊕â|+2, the Hamming distance from the label of x to the target label plus two (Lemma 16). A passed step that writes the current value returns its argument, so the path of x gains depth only at the coordinates where r(x) differs from â. The flip adds one more, and the undo of a step adds one more. A uniform target label lies at distance about m/2 from the label of a sample, so depth about m/2 covers all but a small fraction of the rounds, and the other rounds accept without checking. Algorithm 1 in Appendix C lists the calls of one round. On the interface of Figure 3, with samples uniform on x and w, take â = 00 and d = 3, so Wâ = T2,0 T1,0 . From w, step 1 calls T1,0 w = v, and its undo T1,1 v = w passes. Step 2 calls T2,0 v = x, but its undo T2,1 x = v ′ is not v, so the path check rejects w, although every law instance holds at w. Theorem 4 (Audit) Let µ be a probability measure on S and 0 < ϵ, δ < 1. Rounds of Algorithm 1 have one-sided error. (a) For d = m + 1 and any fixed â, a round has depth at most m + 1, makes at most m2 + 5m setter calls and rejects with probability at least Dµ∞ , so ⌈log(1/δ)/ϵ⌉ rounds certify. With the bridge check of Appendix C.2, the same holds for Dµ , with at most 2m2 + 6m setter calls per round. (b) Let 2 ≤ d ≤ m + 1 and τj = Pr{Bin(m, 1/2) > d − j}. For a uniform â, a round has depth at most d and rejects with a probability p such that Dµ∞ ≤ p + τ2 ; with the bridge check, Dµ ≤ p + (m + 2)τ2 . We call the term added to p the tail term; if it is at most ϵ/2, ⌈2 log(1/δ)/ϵ⌉ rounds certify. (c) Let ℓ = 0 and ϵm = m−β with fixed 0 < β ≤ 1. The least depth with a polynomial budget of samples and setter calls at ϵm is (1/2 + o(1))m, for both distances. √ By Hoeffding’s inequality, depth m/2 + O( m log m) makes the tail term of (b) at most ϵm /2. This is the upper bound in (c), and the lower bound is the instance of Theorem 2 at mean zero (Appendix E.7).

5. Counting samples alone Theorem 5 (Samples alone) Let 2 ≤ dm ≤ ⌊m/16⌋ and ℓ∗m = m log(m/dm )/ log m. For both distances, a polynomial budget of samples at ϵm = 1/(32m) exists if and only if ℓm = Ω(ℓ∗m ). (a) Necessity. If ℓm = o(ℓ∗m ), every tester of depth at most dm that certifies at ϵm = 1/(32m) with confidence 2/3 for all interfaces and start distributions uses a superpolynomial expected number of samples on some composable interface and start distribution, whatever its number of setter calls. (b) Sufficiency. If ℓm ≥ bℓ∗m with a constant b > 0, then for all 0 < ϵ, δ < 1, evaluating all law instances at the ends of all words of length at most dm − 2 from each sample certifies from a number of samples polynomial in m, 1/ϵ and log(1/δ). The setter calls of this tester can be exponential in dm . For m ≥ 96, d = ⌊m/16⌋ and ℓ ≥ ςm/ log m with ς > 0, ⌈140m2+8/ς log(1/δ)/ϵ⌉ samples suffice. 11

G UO R EN YANG S UN YANG

Why Theorem 5 holds. For sufficiency, a random word need not write every variable. If it misses at most d − 2 of them, the exhaustive check at its end stands in for the missing writes, as all words of length at most d − 2 on the missing variables behave like writes in a record (Theorem 35). Writing all but d − 2 variables takes about t = 2m log(m/d) random writes, against m log m for all of them. The factor λt = (1 + 1/ℓ)t that moves failures along the word to the samples is polynomial exactly when t/ℓ ≲ log m, which is ℓ ≳ ℓ∗m . For necessity, take the instance of Theorem 2 with one group of 8⌊m/8⌋ variables and no mask. The transcripts stay equal as long as the threshold function of the frozen block is constant on the whole ball of radius d around a sample. For a run with at most t̂ writes to the group, this holds with high probability if the margin J(1 − 1/(8J))t̂ exceeds d by more than the fluctuations of the weight, which allows t̂ of order m log(m/d). The writes to this group, which holds almost all variables, exceed t̂ with probability at most exp[−t̂/(1 + ℓ)], so polynomially many samples include such a run only if t̂/(1 + ℓ) ≲ log m, the same scale ℓ ≳ ℓ∗m (Appendix E.5). The two theorems differ in how the tester’s writes can lower the margin. Exhausting the ball reaches the labels that subtract d from the margin, at a cost in setter calls exponential in d. Writes chosen without knowing the mask only multiply the margin by about 1−2d/m, so with a polynomial budget the twist appears only once the margin falls to the fluctuations, after order m log m writes. The two budgets separate. Take d = ⌊m/16⌋ and ℓ = m/ log m. For m ≥ 96, part (b) with ς = 1 says that ⌈140m10 log(1/δ)/ϵ⌉ samples certify at every ϵ, so polynomially many samples certify at each ϵm = m−β . As ℓ = o(m), Theorem 2(a) with c = 1/16 says that at each such ϵm polynomially many samples and setter calls do not.

6. Discussion Which measure a certificate speaks about. Law checks after runs certify µℓ , and the audit with no runs certifies ν, so these are two different certificates. A two-state interface shows the difference: with target label 0 and depth 2, every audit round passes, and Dν = 0, while after one random write the distance is 1/2 (Proposition 43). A tester that may change the mean of its runs can still certify the distance under the original µℓ . With L = max{ℓ, m}, µℓ ≤ 1+L 1+ℓ µL , so law checks at mean L certify the distance under µℓ from polynomially many samples (Proposition 44). For ℓ > 0, a distance certified under µℓ bounds how often independent random edits from a sample leave the path of one composable interface (Corollary 10). How large the worst start distribution must be. With added states and no runs, depth one and a budget polynomial in m and N suffice for a start distribution of support at most N , as a tester can compare states across samples (Proposition 45). So at mean zero, the necessity of Theorem 2 for D∞ needs start distributions of superpolynomial support. Larger thresholds. At a fixed threshold, the question for law checks reduces to one quantity. Call a state locally exact to depth d if every word of length at most d from it ends at the label that coordinate writes predict, and two such words end at one state exactly when these labels agree. Let ad be the supremum of Dν∞ (I) over finite interfaces I of any number of variables and distributions ν on such states. Law checks at each fixed positive mean certify D∞ at each fixed positive threshold from polynomially many samples if and only if ad → 0 (Theorem 39). Without runs, a sample 12

H OW FAR M UST A T EST E XPLORE ?

bound uniform over interfaces and start distributions requires depth Ω(min{m, 1/ϵ}) at 0 < ϵ ≤ 1/512 and confidence above 1/2, unconditionally (Theorem 34). Tightness. For ϵ ≤ 1/16 and δ ≤ 1/3, the number of samples of the audit is optimal up to a constant factor (Proposition 18). At ℓ = αm the coefficient of law checks is at least of order m1/(2α) (Proposition 22), so the degree of the law-check budget obtained from this coefficient grows with 1/α. Scope. The results assume binary variables, uniformly random writes in the runs, geometric run lengths, exact comparison of states, and a tester that is not given the start states or write sequences of the sampling runs (Definition 1(i)). The lower bounds apply to testers that stay local: the audit of depth m + 1 is always available. Open problems. First, whether ad → 0. Second, the condition on the mean for a polynomial budget at depths with dm − m/2 = o(m). Third, the orders of the coefficients in Theorem 1 and in law checks after long runs. Fourth, how the exploration needed at positive means varies between one start state and the worst start distribution, for instance at support polynomial in m.

References François Bancilhon and Nicolas Spyratos. Update semantics of relational views. ACM Transactions on Database Systems, 6(4):557–575, 1981. Oren Becker and Michael Chapman. Stability of approximate group actions: uniform and probabilistic. Journal of the European Mathematical Society, 25(9):3599–3632, 2023. Oren Becker and Jonathan Mosheiff. Abelian groups are polynomially stable. International Mathematics Research Notices, 2021(20):15574–15632, 2021. Michael A. Bender and Dana Ron. Testing properties of directed graphs: Acyclicity and connectivity. Random Structures & Algorithms, 20(2):184–205, 2002. Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. Journal of Computer and System Sciences, 47(3):549–595, 1993. Michael Chapman and Alexander Lubotzky. Stability of homomorphisms, coverings and cocycles I: Equivalence. European Journal of Mathematics, 11:Article 13, 2025. Michael Chapman, Thomas Vidick, and Henry Yuen. Efficiently stable presentations from errorcorrecting codes. Discrete Analysis, 2026. Yeshwanth Cherapanamjeri and Peter L. Bartlett. Testing symmetric Markov chains without hitting. In Proceedings of the Thirty-Second Conference on Learning Theory, pages 758–785, 2019. Tsun S. Chow. Testing software design modeled by finite-state machines. IEEE Transactions on Software Engineering, SE-4(3):178–187, 1978. Koen Claessen and John Hughes. Testing monadic code with QuickCheck. In Proceedings of the 2002 ACM SIGPLAN Workshop on Haskell, pages 65–77, 2002. 13

G UO R EN YANG S UN YANG

Constantinos Daskalakis, Nishanth Dikkala, and Nick Gravin. Testing symmetric Markov chains from a single trajectory. In Proceedings of the 31st Conference on Learning Theory (COLT), pages 385–409, 2018. J. Nathan Foster, Michael B. Greenwald, Jonathan T. Moore, Benjamin C. Pierce, and Alan Schmitt. Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem. ACM Transactions on Programming Languages and Systems, 29(3):Article 17, 2007. Simon Foster, Frank Zeyda, and Jim Woodcock. Unifying heterogeneous state-spaces with lenses. In Theoretical Aspects of Computing – ICTAC 2016, pages 295–314. Springer, 2016. Oded Goldreich. Testing graphs in vertex-distribution-free models. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 527–534, 2019. Oded Goldreich and Dana Ron. Property testing in bounded degree graphs. Algorithmica, 32(2): 302–343, 2002. Oded Goldreich and Dana Ron. Testing distributions of huge objects. TheoretiCS, 2:Article 12, 2023. Shirley Halevy and Eyal Kushilevitz. Distribution-free property testing. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX 2003 and RANDOM 2003), pages 302–317, 2003. Chris A. J. Klaassen. On an inequality of Chernoff. The Annals of Probability, 13(3):966–974, 1985. Edward Kmett and Oliver Charles. lens-properties: QuickCheck Properties for lens, 4.11.1 edition, 2026. URL https://hackage-content.haskell.org/package/lens-5.3. 6/lens-5.3.6.tar.gz. Source bundled with lens 5.3.6. David Lee and Mihalis Yannakakis. Principles and methods of testing finite state machines—a survey. Proceedings of the IEEE, 84(8):1090–1123, 1996. John Power and Olha Shkaravska. From comodels to coalgebras: State and arrays. Electronic Notes in Theoretical Computer Science, 106:297–314, 2004. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252–271, 1996. Adrien Saumard. Weighted Poincaré inequalities, concentration inequalities and tail bounds related to Stein kernels in dimension one. Bernoulli, 25(4B):3978–4006, 2019. Ramon van Handel. Probability in high dimension. APC 550 lecture notes, Princeton University, 2016. URL https://web.math.princeton.edu/˜rvan/APC550.pdf. Version of December 21, 2016. M. P. Vasilevskii. Failure diagnosis of automata. Cybernetics, 9(4):653–665, 1973.

14

H OW FAR M UST A T EST E XPLORE ?

Appendix A. Preliminaries Lemma 6 (Properties of the sample distribution) For all ℓ > 0 and integers s ≥ 0, (i) µℓ = (1 − q)ν + q µℓ P , (ii) µℓ P s ≤ q −s µℓ and (iii) ν ≤ (1 + ℓ) µℓ . Put tm = ⌈m log(2m)⌉, and let ht be the probability that t independent uniform draws cover [m]. Lemma 7 (Samples and coverage) For every ℓ > 0, a sample as in Section 2 has distribution µℓ and expected cost EL = ℓ setter calls. Also ht ≥ 1 − m(1 − 1/m)t ≥ 1 − me−t/m , ht > 0 for t ≥ m, and htm ≥ 1/2. Finally tm ≤ m log(2m) + 1, and tm ≥ m for m ≥ 2. Proof of Lemmas 6 and 7 Write µ = µℓ . Given distribution νP s , P L = s, the returned Pstate has so the sample has distribution (1), and EL = s≥1 Pr(L ≥ s) = s≥1 q s = q/(1 − q) = ℓ. P Reindexing the series gives (i) of Lemma 6, qµP = (1 − q) s≥0 q s+1 νP s+1 = µ − (1 − q)ν. Dropping either nonnegative term of (i) gives (iii), ν ≤ (1 − q)−1 µ = (1 + ℓ)µ, and µP ≤ q −1 µ. By positivity of P , induction with µP s+1 ≤ q −s µP ≤ q −(s+1) µ gives (ii). For coverage, a union bound over the variables absent from the t draws gives the first inequality, and 1 − 1/m ≤ e−1/m the second. The first m draws are distinct with positive probability, so ht > 0 when t ≥ m. For m = 1 coverage is certain; for m ≥ 2 and t = tm ≥ m log(2m), me−t/m ≤ 1/2. The ceiling gives tm ≤ m log(2m) + 1, and log(2m) ≥ 1 gives tm ≥ m for m ≥ 2.

Lemma 8 (Subinvariant measures) Let λ ≥ 1. If µ is λ-subinvariant, then µP s ≤ λs µ for all s ≥ 0. Proof As P is nonnegative, applying it to both sides of µP s ≤ λs µ gives µP s+1 ≤ λs µP ≤ λs+1 µ, and induction gives the claim.

Proposition 9 (Characterization) An interface satisfies the five laws at every state if and only if it is composable. Proof A composable interface satisfies the five laws by direct evaluation. Conversely, suppose the laws hold everywhere. By success and preservation, the flip Fi changes exactly reader i. Overwrite and write-back give Fi2 x = Ti,ri (x) Ti,1−ri (x) x = Ti,ri (x) x = x. For i ̸= j, preservation makes the values chosen by Fi and Fj in Fi Fj x and Fj Fi x equal to the values chosen at x, and commutation of the corresponding setters gives Fi Fj = Fj Fi . These involutions define an action of {0, 1}m under bitwise addition. Applying u ∈ {0, 1}m changes the label by u, so nonzero elements move every state and every orbit has 2m points, one per label. With Z the set of orbits, x 7→ (r(x), [x]) is the required bijection; by write-back, Ti,a x is x if a = ri (x) and Fi x otherwise.

15

G UO R EN YANG S UN YANG

Law checks at samples. The five laws of Section 2 have 4m2 +3m law instances: 2m for success, m for write-back, 4m for overwrite, 2m(m − 1) for preservation and 2m(m − 1) for commutation, one for each pair i < j and values a, b. Let x be a state with label u, and put yi = Ti,1−ui x. The 2m2 + 2m setter calls Ti,a x, Ti,a yi and Ti,a yj , for all i ̸= j and a, give every law instance at x as a reading or a comparison of their outputs, given write-back at x; for instance, overwrite of i compares Ti,a yi with Ti,a x. Let K be a coefficient with Dµ ≤ Kγµ for all µ in a class. Evaluating all law instances at n = ⌈K log(1/δ)/ϵ⌉ independent samples of µ and rejecting when one fails has one-sided error, by Proposition 9. If Dµ ≥ ϵ, each sample shows a failure with probability γµ ≥ ϵ/K, so all n samples pass with probability at most e−nϵ/K ≤ δ. The same holds for Dµ∞ . Conversely, a law-check tester rejects with probability at most γµ times its expected number of samples, as the decision to draw a sample does not depend on that sample. What a distance bound gives. A small distance controls sequences of random edits from the samples. Along a sequence, the same setters are applied under I and under a closest composable interface. Corollary 10 (Sequences of random edits) Let ℓ > 0, let I˜ be a composable interface on S with ˜ = Dℓ , and let k ≥ 1 be an integer. Draw x ∼ µℓ and independent uniformly random Rµℓ (I, I) setters (i1 , a1 ), . . . , (ik , ak ), independent of x, and put X0 = X̃0 = x, Xs = Tis ,as Xs−1 and X̃s = T̃is ,as X̃s−1 for s = 1, . . . , k. Then the probability that Xs ̸= X̃s for some s ≤ k is at most ℓ (q −k − 1) Dℓ , and the probability that this happens or r(Xk ) ̸= r̃(X̃k ) is at most (ℓ (q −k − 1) + mq −k ) Dℓ . For k ≤ ℓ, these bounds are at most ek Dℓ and e(k + m) Dℓ . Proof At the first s with Xs ̸= X̃s , the setters Tis ,as and T̃is ,as differ at Xs−1 = X̃s−1 . Here Xs−1 has distribution µℓ P s−1 ≤ q −(s−1) µℓ by Lemma 6(ii), and (is , as ) is uniform and independent of it, over the 2m setters bounds this probability by q −(s−1) Dℓ . Summing over s with P so averaging −s = ℓ(q −k −1) gives the first bound. If X = X̃ for every s ≤ k but r(X ) ̸= r̃(X̃ ), then s s k k s<k q k ≤ q −k µ , this has probability at most ri (XP ) = ̸ r̃ (X ) for some i. As X has distribution µ P i k k k ℓ ℓ q −k i µℓ {ri ̸= r̃i } ≤ mq −k Dℓ , which gives the second bound. For k ≤ ℓ, q −k = (1 + 1/ℓ)k ≤ ek/ℓ ≤ e and ℓ(q −k − 1) ≤ ℓ(ek/ℓ − 1) ≤ kek/ℓ ≤ ek, by ey − 1 ≤ yey for y ≥ 0.

Appendix B. Completion and reversible words This appendix holds the tools behind the upper bounds of Theorems 2, 4 and 5. In a composable interface, a word that writes every variable sends two states to the same state exactly when they lie in one cube. So the fibers of such a word serve as candidate cubes in a general interface. With added states, each fiber can take a cube of its own. On the same states there are only M cubes, so the proofs keep the M heaviest fibers and bound the probability that this loses. Lemma 11 (Completion by heavy fibers) Let |S| = M 2m , let µ be a probability measure on S, let W be any map S → S, let G ⊆ S be a set on which x 7→ (r(x), W x) isP injective, and let A ⊆ G. −1 Put wz = µ(A ∩ W (z)) for z ∈ W (S), let κ : W (S) → [0, 1] satisfy z: wz >0 κ(z) ≤ M , and P ′ ˜ put ∆ = z wz (1 − κ(z)). There are a composable interface I on S and a set G ⊆ G with µ(A \ G′ ) ≤ ∆ such that r̃ = r on G′ , and T̃i,a x = Ti,a x whenever x ∈ G′ , y = Ti,a x ∈ G, W y = W x and r(y) = r(x)[i 7→ a]. 16

H OW FAR M UST A T EST E XPLORE ?

01

11

01

00

10

00

fiber 1

10

fiber 2

01 fiber 3

01

11

01

11

00

10

00

10

cube 1

cube 2

Figure 5: Completion by heavy fibers for m = 2 and M = 2 cubes. Left: three fibers of a word, with each state shown by its label. Right: the two cubes when the first two fibers carry the most probability. The state of the third fiber (gray), whose label was 01, fills the empty position and reads 11 there.

Proof Let Ωz = G ∩ W −1 (z). By injectivity, the states of Ωz have distinct labels. Let Z∗ be a set of at most M points z with nonempty Ωz and largest wz , containing all of them if there are at most M , and let G′ be the union of the sets Ωz with z ∈ Z∗ . If at most M sets Ωz are nonempty, then G′ = G ⊇ A. Otherwise |Z∗ | = M ; let w∗ = minz∈Z∗ wz . If w∗ = 0, then wz = 0 for z ∈ / Z∗ . If w∗ > 0, then   X X X X X wz − wz κ(z) = wz (1 − κ(z)) − wz κ(z) ≥ w∗ M − κ(z) ≥ 0. z∈Z∗

z

z∈Z∗

z: wz >0

z ∈Z / ∗

In both cases z∈Z∗ wz ≥ z wz κ(z), so µ(A\G′ ) ≤ z wz − z∈Z∗ wz ≤ ∆. Place each set Ωz with z ∈ Z∗ in its own cube, at the positions given by the labels of its states. For |Z∗ | = M ′ ≤ M , these cubes have M ′ 2m − |G′ | ≤ |S| − |G′ | empty positions, which we fill with states outside G′ . ˜ At x ∈ G′ The remaining (M − M ′ )2m states form the other cubes in any way, which defines I. ˜ If y = Ti,a x ∈ G, W y = W x and r(y) = r(x)[i 7→ a], then y is the state the readers agree with I. of ΩW x with this label, which is the position of T̃i,a x. P

P

P

P

The first choice of κ is the fraction of labels that occur in a fiber, κ(z) = |r(W −1 (z))|/2m . The fibers are disjoint and each has at least as many states as distinct labels, so these fractions sum to at most M over all z. A uniformly random label occurs in the fiber W −1 (z) with probability κ(z), so ∆ is the probability that x ∼ µ lies in A and a uniformly random label occurs nowhere in the fiber W −1 (W x). This fiber is a subset of S and may contain states outside G. Figure 5 shows how the sum bounds the loss. There the second fiber misses a quarter of the labels, the third misses three quarters, and the second carries at least as much probability as the third. So the average of 1 − κ over the fibers, which counts a quarter of the probability of the second fiber and three quarters of that of the third, is at least the probability of the third. This is the part that the composable interface drops. Appendix D uses another choice of κ. Reversible words. Let W = Et · · · E1 be a word with Es = Tis ,as , put Us = Es · · · E1 and U0 = Id, and let xs = Us x be the path of x. The reversible set GW is the set of states x whose path passes (3) at every step s = 1, . . . , t. Lemma 12 (Reversible set) The map x 7→ (r(x), W x) is injective on GW . Proof Let x ∈ GW . The first equalities of (3) determine each label r(xs ), and so each old value bs , from r(x) and the word. Starting at W x, the setters Tit ,bt , . . . , Ti1 ,b1 undo the steps in reverse order by the second equalities and end at x. 17

G UO R EN YANG S UN YANG

Lemma 13 (Inserted setters) Let W = Et · · · E1 write every variable, and let x be a state with xj ∈ / N for 0 ≤ j < t. Then x ∈ GW , and every setter Ti,a satisfies Ti,a x ∈ GW , W Ti,a x = W x and r(Ti,a x) = r(x)[i 7→ a]. Proof A state z ∈ / N and a setter Tk,e pass (3): success and preservation give the label, and with v = rk (z), write-back handles e = v, while overwrite and write-back give Tk,v Tk,e z = Tk,v z = z for e ̸= v. So x ∈ GW . Fix T = Ti,a and let τ be the first position with iτ = i. The label claim is success and preservation at x. Let ys = Us T x. For j < τ , let z = xj−1 , z ′ = xj and Ej = Tk,e with k ̸= i. Both z and z ′ lie outside N , as j < t. Commutation at z gives Ej T z = T z ′ , so yj = T xj by induction. Success and preservation at z and at z ′ give r(T z) = r(z)[i 7→ a] and r(T z ′ ) = r(z ′ )[i 7→ a] = r(T z)[k 7→ e], which is the first equality of (3) for this step of the path of T x. For the second, let v = rk (T z) = rk (z). If e = v, write-back at z gives z ′ = z, so Tk,v T z ′ = Ej T z = T z ′ = T z. If e ̸= v, commutation at z ′ , overwrite at z and write-back at z give Tk,v T z ′ = T Tk,v Tk,e z = T Tk,v z = T z. At j = τ , let z = xτ −1 and Eτ = Ti,e . Overwrite at z gives Eτ T z = Ti,e z = xτ , so the two paths meet, and Ti,a xτ = Ti,a Ti,e z = Ti,a z = T z, where a = ri (T z) by success. Success and preservation at z give r(xτ ) = r(T z)[i 7→ e]. So this step passes (3). From step τ on, the path of T x is that of x, and x ∈ GW . Hence T x ∈ GW and W T x = W x. For a word W and A ⊆ S, let ∆A be the probability that x ∼ µ lies in A and a uniformly random label, independent of x, occurs nowhere in the fiber W −1 (W x). This is the ∆ of Lemma 11 for the first choice of κ. Lemma 14 (Bounds from a reversible set) Let W be a word, let A ⊆ GW , and suppose every x ∈ A and every setter Ti,a satisfy Ti,a x ∈ GW , W Ti,a x = W x and r(Ti,a x) = r(x)[i 7→ a]. Then Dµ∞ ≤ µ(S \ A), with no condition on |S|. If 2m | |S|, then Dµ ≤ µ(S \ A) + ∆A . In both cases one composable interface agrees with all readers and setters at once outside an event of at most this probability. Proof For Dµ∞ : by Lemma 12, the states of GW in one fiber have distinct labels. Additional states complete each such set, and each state of S \ GW , to a cube of its own, with the states of S at the positions of their labels. Coordinate setters on these cubes define a composable interface on a finite set containing S, whose readers agree with r on S. For x ∈ A, Ti,a x is the state of the cube of x with the label r(x)[i 7→ a], which is the output of the composable setter. For Dµ : apply Lemma 11 with G = GW and the first choice of κ, by Lemma 12. Its composable interface agrees with I on A ∩ G′ .

Appendix C. Proof of Theorem 4(a) and (b) Throughout, â is a target label, Wâ = Tm,âm · · · T1,â1 , Uj = Tj,âj · · · T1,â1 and U0 = Id. A checked step from a state z under Tj,âj calls z ′ = Tj,âj z and checks r(z ′ ) = r(z)[j 7→ âj ]. With b = rj (z), it then compares z ′ with z if b = âj , and otherwise calls Tj,b z ′ and compares the output with z. Each checked step makes at most two calls, and a passed one satisfies (3). A round stops at its first failed check. On the path of yi , step i compares its output with the state xi = Ui x of the path of x before it calls the undo. Part (c) is proved in Appendix E.7. 18

H OW FAR M UST A T EST E XPLORE ?

C.1. Path and flip checks Lemma 15 (Checked setters) Let x pass the path check and the flip checks of a round with target label â. Then x ∈ GWâ , and every setter Ti,e satisfies Ti,e x ∈ GWâ , Wâ Ti,e x = Wâ x and r(Ti,e x) = r(x)[i 7→ e]. Proof The path check gives x ∈ GWâ . If e = ri (x), the check of write-back gives Ti,e x = x, and the claims follow. Otherwise Ti,e x = yi , and the check of its label gives the third claim. The path of yi satisfies (3) at steps 1, . . . , i and reaches the same state as the path of x at step i. From step i on, the two paths coincide, so the path of yi satisfies (3) at the later steps as well. Hence yi ∈ GWâ and Wâ yi = Wâ x. Lemma 16 (Depth of the path and flip checks) Let ϱ = |r(x) ⊕ â|. The calls of the path and flip checks on x have depth at most min{ϱ + 2, m + 1} when they are made, and there are at most m2 + 5m of them. Proof Let ϱj be the number of h ≤ j with rh (x) ̸= âh . On the path of x, a passed step that writes the old value is a self-loop that the tester has seen, so xj has depth at most ϱj when step j + 1 is made. Hence the calls of the path check have depth at most ϱ + 1 ≤ m + 1. Let j < i. Before step j of the path of yi , the flip and the earlier passed steps give a chain of length at most 1 + ϱj−1 , so this step and its undo have depth at most ϱj + 2. As ϱj ≤ min{ϱ, m − 1}, this is at most min{ϱ + 2, m + 1}. Step i itself has depth at most ϱi−1 + 2. It is followed by a comparison with xi , so its undo acts on a state of depth at most ϱi and has depth at most ϱi + 1. These bounds use only comparisons that passed before the call. The path P check makes at most 2m calls, the write-backs and flips 2m, and the paths of the states yi at most i 2i = m(m + 1), in total m2 + 5m. C.2. The bridge check On the same states, the M heaviest fibers lose at most the probability that x passes the checks above and a uniform label u is missing from its fiber (Lemma 14). The bridge check pays for this loss by showing that a state of label u lies in the fiber of x. It runs after the path and flip checks of Algorithm 1, as follows. 1. Draw a uniform label u, and let u(j) = (â1 , . . . , âj , uj+1 , . . . , um ) for 0 ≤ j ≤ m. Algorithm 1: One audit round with target label â and depth cap d. A failed check rejects. draw x ∼ µ; put x0 = x if d ≤ m and |r(x) ⊕ â| > d − 2 then accept the round // first test for s = 1, . . . , m do // path check put bs = rs (xs−1 ); call xs = Ts,âs xs−1 and check its label; if âs = bs , compare xs with xs−1 ; otherwise call the undo Ts,bs xs and compare its output with xs−1 for i = 1, . . . , m do // flip check check Ti,ri (x) x = x; put yi = Fi x; check r(yi ) = r(x)[i 7→ 1 − ri (x)] for s = 1, . . . , i do do step s of the path of yi as above; if s = i, compare its output with xi before any undo

19

G UO R EN YANG S UN YANG

2. If some |u(j) ⊕ r(x)| > d − 1, accept the round (the second test). 3. For j = 0, . . . , m − 1: from x, write the values of u(j) where it differs from r(x), to get wj , and check r(wj ) = u(j) . 4. Put wm = Wâ x, and check Tj,âj wj−1 = wj for j = 1, . . . , m. Applying Wâ to w0 directly could take depth 2m. The bridge check instead reaches each intermediate state wj from x by a word of length at most m and checks one setter between neighbors, so its depth is at most m + 1. Lemma 17 (Bridge check) If the bridge check of a round passes, then w0 reads u and lies in the fiber of x under Wâ . The bridge check makes at most m2 + m calls, and with a depth cap d, its calls have depth at most d. Proof The label check gives r(w0 ) = u(0) = u, and the comparisons give Wâ w0 = wm = Wâ x. Each wj with j < m takes at most m calls, and there are m comparisons with a call each. The word that produces wj has length |u(j) ⊕ r(x)| ≤ d − 1, so its calls have depth at most d − 1, whatever their outputs are, and a bridge call on wj−1 has depth at most d. For a depth cap d = m + 1 the length is at most m = d − 1 for every u and â.

C.3. Proof of parts (a) and (b) Proof of Theorem 4(a) and (b) One-sided error. In a composable interface every path satisfies (3), writing the current value fixes the state, and a flip changes only coordinate i. The paths of x and yi reach the same state at step i, the first write to i. Each wj is the state of the cube of x with the label u(j) , and Tj,âj takes u(j−1) to u(j) . So every check passes, and a round that stops early accepts. Depth and calls. Lemma 16 bounds the depth by m + 1 without the first test of Algorithm 1, and by d with it. Lemma 17 bounds the bridge check. So a round has depth at most d, with at most m2 + 5m calls without the bridge check and at most 2m2 + 6m with it. Part (a). Let d = m + 1, fix â, and let A be the set of states that pass the path and flip checks. By Lemma 15, Lemma 14 applies with W = Wâ . So Dµ∞ ≤ µ(S \ A), which is the rejection probability of a round without the bridge check. For Dµ , the label u is uniform and independent of x. If x ∈ A and u occurs nowhere in the fiber of x, the bridge check rejects, by Lemma 17. So a round rejects with probability at least µ(S \ A) + ∆A ≥ Dµ . If the distance is at least ϵ, then ⌈log(1/δ)/ϵ⌉ independent rounds all pass with probability at most δ. Part (b). Let 2 ≤ d ≤ m; for d = m + 1 the bounds follow from part (a). For a fixed target label â, let A(â) be the set of states that pass the first test of Algorithm 1 and the path and flip checks. By Lemma 14, Dµ∞ ≤ µ(S \ A(â)). Averaged over the uniform target label, the probability that the first test ends the round is τ2 , as r(x) ⊕ â is uniform. So Dµ∞ ≤ p + τ2 . For Dµ , Lemma 14 gives Dµ ≤ µ(S \ A(â)) + ∆A(â) . If x ∈ A(â) and u occurs nowhere in the fiber of x, then either the second test ends the round or the bridge check rejects, by Lemma 17. For fixed x and j, the label u(j) is uniform, as â and u are, so the second test ends the round with probability at most (m + 1)τ1 . Rejections by the two kinds of checks are disjoint events, so Dµ ≤ p + τ2 + (m + 1)τ1 ≤ p + (m + 2)τ2 . If the tail is at most ϵ/2 and the distance at least ϵ, then p ≥ ϵ/2, and ⌈2 log(1/δ)/ϵ⌉ independent rounds all pass with probability at most δ.

20

H OW FAR M UST A T EST E XPLORE ?

C.4. Lower bounds for every tester Proposition 18 (Every tester) Let 0 < ϵ ≤ 1/16, 0 < δ ≤ 1/3 and Nδ,ϵ = ⌈log(1/δ)/(2ϵ)⌉ + 2. Let a tester, whenever µ is the uniform measure on a set of 2m Nδ,ϵ states, accept composable interfaces and reject interfaces with Dµ∞ > ϵ, each with probability at least 1 − δ. Then it uses, in expectation, at least log(1/δ)/(48ϵ) samples and at least (m/(48ϵ)) log(1/δ) setter calls on some composable interface on such a set, even if reader calls and comparisons are free. Proof of Proposition 18 Instances. Let N0 = ⌊2ϵNδ,ϵ ⌋ + 1 and ϵ̃ = N0 /Nδ,ϵ . As log(1/δ) ≥ log 3 > 1 and Nδ,ϵ ≥ log(1/δ)/(2ϵ), 2ϵ < ϵ̃ ≤ 2ϵ + 1/Nδ,ϵ ≤ 4ϵ ≤ 1/4 and 1 ≤ N0 ≤ Nδ,ϵ . The set of states is {0, 1}m × [Nδ,ϵ ] with cubes {0, 1}m × {z}, the measure ν is uniform, and ri (u, z) = ui . The null input has Ti,a (u, z) = (u[i 7→ a], z). A negative input, indexed by a variable j∗ and an N0 -set Z0 ⊆ [Nδ,ϵ ], makes both setters of j∗ the identity on the cubes with z ∈ Z0 . On each cube the random-edit kernel averages kernels that resample one coordinate of u uniformly, one of them possibly replaced by the identity, so ν is stationary for every input. Identity setters satisfy write-back, overwrite and preservation and commute with setters that keep the cube, so only success fails, on the states of the cubes with z ∈ Z0 and uj∗ = 1 − a. At each state of such a cube, a composable interface, on the set of states or on any finite set containing it, moves the state by exactly one of its two setters of variable j∗ , while both original setters fix the state. So the two disagreements sum to at least ϵ̃. As a composable interface on the same states, the null input differs from the negative input only in the two setters of j∗ , each with probability ϵ̃/2, so Dν∞ = Dν = ϵ̃/2 ∈ (ϵ, 2ϵ]. Avoidance probability. For an integer 0 ≤ v ≤ Nδ,ϵ , let Av(v) be the probability that a uniformly random N0 -subset of [Nδ,ϵ ] misses a given v-subset, and let Av be its linear interpolation on [0, Nδ,ϵ ], extended by zero. The decrement Av(v) − Av(v + 1) ≥ 0 is the probability of missing v given points and containing another one, which does not increase in v. The slope 0 of the zero extension is at least the last slope of the interpolation. Q So Av is nonincreasing and convex. For integers 0 ≤ v ≤ ⌊Nδ,ϵ /2⌋, each factor of Av(v) = v′ <v (1 − N0 /(Nδ,ϵ − v ′ )) satisfies N0 /(Nδ,ϵ − v ′ ) ≤ 2ϵ̃ ≤ 1/2, so Av(v) ≥ (1 − 2ϵ̃)v ≥ e−4ϵ̃v , as − log(1 − 2ϵ̃) ≤ 4ϵ̃ for 2ϵ̃ ≤ 1/2. By convexity of the exponential, Av(v) ≥ e−4ϵ̃v also for real 0 ≤ v ≤ ⌊Nδ,ϵ /2⌋. Coupling. Draw j∗ uniformly from [m] and Z0 uniformly among the N0 -subsets of [Nδ,ϵ ], independently of the tester’s randomness and of the samples, and execute the tester on the null input; Pr0 and E0 refer to this execution. Let nT and nS be its numbers Pof setter calls and samples. Let Vi be the set of cubes in which it calls a setter of variable i, so i |Vi | ≤ nT , and let V0 be the set of cubes that contain a sample, so |V0 | ≤ nS . Couple the execution on the negative input (j∗ , Z0 ), using the same randomness and samples. Setters keep the cube of their argument, so every held state lies in a cube of V0 . If Z0 misses Vj∗ , or if it misses V0 , then every setter call has the same output on both inputs, and, inductively, the transcripts and decisions coincide, as readers and comparisonsP agree on equal states. Conditional on the null execution, Z0 misses Vj∗ with P probability m−1 i Av(|Vi |) ≥ Av(m−1 i |Vi |) ≥ Av(nT /m), by convexity and monotonicity of Av, and it misses V0 with probability Av(|V0 |) ≥ Av(nS ). Let acc be the event that the null input is accepted, so Pr0 (acc) ≥ 1 − δ. Soundness on every negative input, averaged over (j∗ , Z0 ), gives δ ≥ E0 [1acc Av(nT /m)] ≥ Pr0 (acc) Av(n̄T ) for n̄T = E0 [nT | acc]/m, by conditional Jensen, and in the same way δ ≥ Pr0 (acc) Av(n̄S ) for n̄S = E0 [nS | acc]. Both hold trivially if the expectations are infinite. 21

G UO R EN YANG S UN YANG

Extracting log(1/δ). We claim n̄T ≥ log((1 − δ)/δ)/(4ϵ̃). As 1 − δ < 1 and ϵ̃ > 2ϵ, the right side is at most log(1/δ)/(8ϵ) ≤ (Nδ,ϵ −1)/2 ≤ ⌊Nδ,ϵ /2⌋. So the claim holds if n̄T > ⌊Nδ,ϵ /2⌋, and otherwise it follows from δ ≥ (1 − δ)e−4ϵ̃n̄T . The same argument gives n̄S ≥ log((1 − δ)/δ)/(4ϵ̃). As 1 − δ ≥ 2/3, ϵ̃ ≤ 4ϵ and log((1 − δ)/δ) ≥ log(1/δ)/2 by (1 − δ)2 ≥ δ, we get E0 nT ≥ Pr0 (acc) mn̄T ≥ (m/(48ϵ)) log(1/δ) and E0 nS ≥ Pr0 (acc) n̄S ≥ log(1/δ)/(48ϵ).

Appendix D. Proof of the sufficiency in Theorem 2 Throughout Appendices D.1–D.4, |S| = M 2m , λ ≥ 1, µ is a λ-subinvariant probability measure on S and γ = γµ . Let U ⊆ N be the set of states success, write-back, overwrite or preserP at which k , with h as in Lemma 7. For a composable vation fails. For v ≥ m, put Φv (λ) = h−1 λ v v k<v ˜ let Eµ (I) ˜ be the probability that some reader or setter of I differs from that of I˜ at x ∼ µ, interface I, ˜ so Dµ ≤ Eµ (I). Theorem 19 (Parametric form) For m ≥ 1 and all integers t, t′ ≥ m, some composable interface I˜ on S has n o t ˜ ≤ min 1, Φt (λ)γ + λ Φt′ (λ)µ(U) . Eµ (I) ht The proof fixes a word, takes its fibers as candidate cubes, and applies Lemma 11. To pay for the labels missing from a fiber, it uses a function κ◦ defined once from the interface alone: the capacity function of Appendix D.2. D.1. Retained steps For a setter Ti,a , let Πi,a be the kernel with row zero or one defined as follows. If a = ri (x), it keeps the transition x → Ti,a x when Ti,a x = x. If a ̸= ri (x), it keeps x → y = Ti,a x when r(y) = r(x)[i P 7→ a] and Ti,ri (x) y = x. Otherwise the row of x is zero. Put Πi = (Πi,0 + Πi,1 )/2 −1 and Π = m i Πi . Each kept transition passes (3). Each Πi is symmetric: if x → y is a kept transition with y ̸= x, then the labels of x and y differ exactly at i, and y → x is kept with the setter of the old value, so both entries are 1/2. Entrywise, Πi ≤ (Ti,0 + Ti,1 )/2 and Π ≤ P . For x ∈ / U, write-back keeps the setter of the current value, and success, preservation, overwrite and write-back keep the other, so Πi 1(x) = 1 for all i. Hence 0 ≤ 1 − Π1 ≤ 1U .

(4)

D.2. The capacity function Draw t′ independent uniform coordinates i1 , . . . , it′ , condition on the event that they cover [m], and put Υ = E[Πi1 · · · Πit′ | cover] and κ◦ = Υ1. The product applies Πi1 first. The transpose of a product reverses the word, and given coverage a uniform word has the same distribution as its reverse. So Υ is symmetric, and 0 ≤ κ◦ ≤ 1. Fix a start state and a covering word of coordinates, and attach independent fair values to its steps. The label that these values write is uniform, as each coordinate takes its last value, and a path 22

H OW FAR M UST A T EST E XPLORE ?

that survives all kept transitions ends at this label. So Υ(x, r−1 (b)) ≤ 2−m for every state x and label b. By symmetry, X X κ◦ (z) = Υ(x, r−1 (b)) ≤ |S|2−m = M. (5) z: r(z)=b

x∈S

P P P ′ By (4) and Π ≤ P , µ(1 − Πt 1) = k<t′ µΠk (1 − Π1) ≤ k<t′ µP k (U) ≤ k<t′ λk µ(U). ′ Now Πt 1 is the expectation of Πi1 · · · Πit′ 1 over the coordinates. Splitting it on coverage, and ′ bounding the product by 1 when the coordinates do not cover [m], gives Πt 1 ≤ ht′ κ◦ + (1 − ht′ )1, ′ t so 1 − κ◦ ≤ h−1 t′ (1 − Π 1). Integrating against µ gives µ(1 − κ◦ ) ≤ Φt′ (λ)µ(U).

(6)

D.3. Proof of Theorem 19 Proof of Theorem 19 Fix a word W = Et · · · E1 that writes every variable, with path xs = Us x, and let AW = {x : xj ∈ / N for 0 ≤ j < t}. By Lemma 13, each x ∈ AW lies in GW , and each of its setters leads to a state of GW in its fiber with the updated label. On GW the map x 7→ (r(x), W x) is injective (Lemma 12). Every x ∈ GW has the same end label, the label bW that W writes. So −1 the bW , and (5) gives P points z◦ with wz = µ(AW ∩ W (z)) > 0 are distinct states with label ◦ gives a composable κ (z) ≤ M . Lemma 11 with G = G , A = A and κ = κ W W z: wz >0 interface that agrees with all readers and setters of I on AW ∩ G′ , so X ˜ ≤ µ(S \ AW ) + Eµ (I) wz (1 − κ◦ (z)). (7) z

Now draw the steps of W as t independent uniform setters conditioned on writing every variable, with x ∼ µ independent of them. Before conditioning, xk has distribution µP k ≤ λk µ, so X E[µ(S \ AW ) | cover] ≤ h−1 µP k (N ) ≤ Φt (λ)γ. t k<t

The last term of (7) is the expectation of 1AW (x)(1 − κ◦ (W x)) over x. Dropping 1AW and the coverage from the numerator, and using (6), hX i λt λt t ◦ ◦ E wz (1 − κ◦ (z)) cover ≤ h−1 µP (1 − κ ) ≤ µ(1 − κ ) ≤ Φt′ (λ)µ(U). t z ht ht So some word attains at most the sum of these two bounds.

D.4. The coefficients Let m ≥ 2, t = t′ = tm , so ht ≥ 1/2 (Lemma 7), and recall µ(U) ≤ γ. The case λ ≤ 1+1/(αm). Such a µ is also (1+1/(αm))-subinvariant, so take λ = 1+1/(αm), and put λ̄ = λt ≥ 1. Then Φt (λ) = αm(λ̄ − 1)/ht , and Theorem 19 gives   ˜ ≤ Φt (λ) 1 + λ̄ γ ≤ 2αm(λ̄ − 1)(1 + 2λ̄)γ ≤ 4αm λ̄2 γ, Eµ (I) ht

λ̄ ≤ et/(αm) ≤ (2em)1/α ,

as t ≤ m log(2m) + 1 and 1/m ≤ 1. This is at most Kα γ with Kα = 4α(2e)2/α m1+2/α . 23

(8)

G UO R EN YANG S UN YANG

D.5. Law checks, for every set of states Lemma 20 (Padding) Let I be an interface on a finite set S, with no condition on |S|, and µ a measure on S. Add (−|S|) mod 2m states with arbitrary readings and setters that stay among the ¯ = γµ (I), µ̄ is added states, and extend µ by zero to µ̄. The new interface I¯ on S̄ satisfies γµ̄ (I) ∞ ¯ λ-subinvariant if µ is, and Dµ (I) ≤ Dµ̄ (I). Extending a start distribution by zero extends its sample distributions by zero. Proof The set S is closed under the setters, and the laws at its states involve only states of S. Added states have mass zero. A composable interface on S̄ is a candidate for Dµ∞ (I) with the same ¯ As S is closed under the setters, disagreements under µ. Let P̄ be the random-edit kernel of I. P̄ acts on S as P , so µ̄P̄ is the extension of µP by zero. Hence µP ≤ λµ gives µ̄P̄ ≤ λµ̄: on S this is the hypothesis, and on the added states both sides vanish. By induction, if ν̄ extends a start distribution ν by zero, then ν̄ P̄ s extends νP s by zero for every s ≥ 0. So, by (1), the sample distribution of ν̄ extends µℓ by zero for every ℓ ≥ 0. Corollary 21 (Long runs) Let m ≥ 2, α > 0, ℓ ≥ αm and Kα = 4α(2e)2/α m1+2/α . Then Dℓ ≤ Kα γℓ when 2m | |S|, and Dℓ∞ ≤ Kα γℓ for every finite S. So evaluating all law instances at ⌈Kα log(1/δ)/ϵ⌉ samples of µℓ certifies these distances, with depth 2 and 2m2 + 2m setter calls per sample. Proof By Lemma 6(i), µℓ is (1 + 1/ℓ)-subinvariant, so (8) and Lemma 20 give the two bounds, and Appendix A gives the tester. Corollary 21 and (8) are part (b) of Theorem 2. D.6. The coefficient at mean αm For α > 0, put
 32(1 + 1/(2α)) 1+1/(2α) 1 Cα = 24 · 81/(2α) Γ 1 + 2α + , e bα = 1 − e−1/(8α+1) and cα = bα /(128 Cα 161/(2α) ). Proposition 22 (Coefficient at mean αm) For m ≥ 32 and each α > 0, some interface and start ∞ ≥ c m1/(2α) γ distribution have Dαm α αm > 0. Proof Let m ≥ 32 and take the unmasked twisted interface I − of Appendix E.2 with J = ⌊m/8⌋ ≥ 4 and Nc = 1, which does not depend on α. Let ℓ = αm. By Lemma 27, Dℓ∞ ≥ ((J + 1)/(128J 2 ))(1 − q0J ) with q0 = 8αJ/(1 + 8αJ). As log(1/q0 ) ≥ 1/(1 + 8αJ), q0J ≤ e−1/(8α+1) , so Dℓ∞ ≥ bα /(128J). It remains to bound γℓ = µℓ (N ), where N is given by Lemma 23 and γℓ > 0, as µℓ has full support: for ℓ > 0 a run reaches every label with positive probability, and by Lemma 24 its hidden bit is a fair bit independent of the final label. Let the edits arrive at the times of a Poisson process of rate 1 and stop at an independent time ι of density ℓ−1 e−t/ℓ ; this gives µℓ (Appendix G.1). Given ι = t, the numbers of edits of the variables are independent and Poisson of mean t/m, with fair written values. So each final bit is its initial bit 24

H OW FAR M UST A T EST E XPLORE ?

shifted by an independent Bernoulli variable of parameter (1 − y)/2, where y = e−t/m , and e−ι/m has density α−1 y 1/α−1 on (0, 1). Given the start label and y, the two blocks are independent. For a sum Z of N1 independent Bernoulli variables, Hoeffding’s inequality gives Pr(Z − EZ ≥ 2 a) ≤ e−2a /N1 for a p ≥ 0, and the same for the lower tail. If all parameters lie in [1/4, 3/4], 2π/(3N1 ) for every integer h: Fourier inversion gives Pr(Z = h) ≤ then Pr(Z = h) ≤ Rπ 2 (2π)−1 −π |EeiθZ |dθ, each factor has squared modulus 1 − 4p(1 − p) sin2 (θ/2) ≤ e−(3/4) sin (θ/2) , | sin(θ/2)| ≥ |θ|/π on [−π, π], and a Gaussian integral finishes the bound. Let 0 < y ≤ 1/2. The √ parameters lie in [1/4, 3/4], so a block of 4J bits lies in {2J − 1, 2J} with probability at most 2/ J. A start label has a frozen block, of initial weight J or 3J, whose final weight Z has mean 2J ∓Jy. Split its bits into two parts of 2J, with sums Z1 and Z2 , which are independent, and let a = |h − EZ|. If Z = h, then Z1 or Z2 deviates from its mean by at least a/2 in the direction of h − EZ. By Hoeffding’s inequality with N1 = 2J, Z1 does so with probability 2 2 at most e−2(a/2) /(2J) = e−a /(4J) . Given such a value of p Z1 , the event Z √ = h fixes Z2 , which by the point bound with N1 = 2J has probability at most π/(3J) ≤ 2/ J. The same holds √ 2 with the two parts exchanged, and adding the two cases gives Pr(Z = h) ≤ (4/ J)e−a /(4J) . For h ∈ {2J − 1, 2J}, a ≥ (Jy − 1)+ , and (x − 1)2+ ≥ x2 /2 − 1 gives Pr(Z ∈ {2J − 1, 2J}) ≤ √ 2 2 (12/ J)e−Jy /8 , as e1/(4J) < 3/2. With the other block, Pr(N | y) ≤ (24/J)e−Jy /8 . For 1/2 < y < 1, the frozen block has to deviate from its mean by at least J/2 − 1 ≥ J/4 in a fixed direction, so Pr(N | y) ≤ e−J/32 . Integrating over y, with v = Jy 2 /8, Z
−1−1/(2α) 24 ∞ 1/α−1 −Jy2 /8 1 y e dy + e−J/32 = 24 · 81/(2α) Γ 1 + 2α γℓ ≤ J + e−J/32 . αJ 0 ′

′

As xe e−x/32 ≤ (32e′ /e)e for x, e′ > 0, taking e′ = 1 + 1/(2α) gives γℓ ≤ Cα J −1−1/(2α) . So Dℓ∞ /γℓ ≥ (bα /(128Cα ))J 1/(2α) ≥ cα m1/(2α) , as J ≥ m/16.

Appendix E. The twisted rectangle This appendix proves the necessity in Theorems 2 and 5, part (c) of Theorem 4, and the depth bound at fixed thresholds of Section 6. All of them use one family of interfaces. E.1. A small instance The smallest member of the family has J = 1. Take m = 8, blocks B ′ = {1, 2, 3, 4} and B ′′ = {5, 6, 7, 8}, and states (v, z) with v ∈ {0, 1}8 and a hidden bit z. Readers read v, and v ′ and v ′′ are the restrictions of v to the blocks. A setter of B ′′ replaces its coordinate. A setter of B ′ replaces its coordinate, and it also toggles z when it moves |v ′ | across the threshold, between weights 1 and 2, while |v ′′ | ≥ 2. Commutation between the blocks fails exactly where both weights lie in {1, 2}, and all other law instances hold everywhere (Lemma 23). Start at the label with ones at variables 1 and 5, so at weights (|v ′ |, |v ′′ |) = (1, 1). The loop has four segments, with eight writes in all. • Bottom: write 1 to variables 2 and 3. The weights go (1, 1) → (2, 1) → (3, 1), and z stays, as |v ′′ | = 1. • Right: write 1 to variables 6 and 7. The weights go (3, 1) → (3, 2) → (3, 3). • Top: write 0 to variables 3 and 2. The weights go (3, 3) → (2, 3) → (1, 3), and the second step toggles z, as |v ′′ | = 3. 25

G UO R EN YANG S UN YANG

• Left: write 0 to variables 7 and 6. The weights go (1, 3) → (1, 2) → (1, 1). So the loop returns to its start label with z toggled, and a composable interface that kept all eight writes would return to the start state (Lemma 25). The start distribution of Appendix E.2 draws the arguments of such loops, with random choices of the variables, so each of the 16 setters of the blocks carries at most 8J/(J + 1) = 4 times the start distribution. Every loop has a disagreement, so 1 ≤ 4 · 16 · R for the disagreement R of any candidate, and at ℓ = 0 the distance is at least 1/64 (Lemma 27). For J = 1 some start states meet the set where commutation fails, and for J ≥ 2 the frozen block keeps all of them outside it. E.2. The instances Let J, Ng , Nc ≥ 1 be integers and n = 8J, with nNg ≤ m. The states are the triples (σ, v, z) ∈ [Nc ] × {0, 1}m × {0, 1}Ng , so there are Nc 2m+Ng of them, and the readers read v. A hidden assignment ω gives each copy σ a mask eσ ∈ {0, 1}m and Ng disjoint groups Vσ,g ⊆ [m] of n ′ ′′ of 4J variables each. The variables each, and it splits each group into two blocks Bσ,g and Bσ,g other variables of the copy are passive. The relative label of a state is u = v⊕eσ , with restrictions u′g and u′′g to the blocks of group g, and fg,1 = 1{|u′g | ≥ 2J} and fg,2 = 1{|u′′g | ≥ 2J} are functions ′ ′′ = [8J] \ [4J] of σ and v. The unmasked assignment has Ng = 1, eσ = 0m , Bσ,1 = [4J] and Bσ,1 for all σ, and then we drop the index g. The setters of I + replace one coordinate of v and keep σ and z, so I + is composable. In the ′ maps (σ, v, z) to twisted interface Iω− , a setter of a variable i ∈ Bσ,g
σ, v[i 7→ a], z ⊕ [fg,1 (σ, v[i 7→ a]) ⊕ fg,1 (σ, v)] fg,2 (σ, v) eg , (9) with eg the g-th unit vector, and the other setters are those of I + . The start distribution νω draws σ uniformly and then, independently for each group, one of four sides, each with probability 1/4: |u′g | uniform on {J, . . . , 3J − 1} and |u′′g | = J; |u′′g | uniform on {J, . . . , 3J − 1} and |u′g | = 3J; |u′g | uniform on {J + 1, . . . , 3J} and |u′′g | = 3J; |u′′g | uniform on {J + 1, . . . , 3J} and |u′g | = J. Given the weights, the blocks are uniform and independent. The relative labels of the passive variables and z are fair bits, independent of the rest. The frozen block Bgf of a start state in group g is the block whose weight the side fixes at J or 3J; the side also fixes the value of its threshold function. Lemma 23 (Laws) In Iω− , success, write-back, overwrite and preservation hold everywhere, and N is exactly the set of states with |u′g |, |u′′g | ∈ {2J − 1, 2J} for some group g. Proof Every setter changes the label as written, and writing the current value changes neither v nor ′ the value of f any threshold function. Between two writes to Bσ,g g,2 does not change, so the changes of z telescope, and overwrite and commutation within this block hold. A setter of a group reads and changes only the labels of this group and the bit zg , so setters of different groups commute, and ′′ commute with each other. Commutation of a so do passive setters with all others. Writes to Bσ,g ′ ′′ variable i of Bσ,g with a variable j of Bσ,g fails in the bit zg by [fg,1 (v[i 7→ a])⊕fg,1 (v)][fg,2 (v[j 7→ b]) ⊕ fg,2 (v)]. This vanishes unless both weights lie in {2J − 1, 2J}, and at those weights suitable writes cross both thresholds. Fix a copy σ and a group g. The rest of a state is its label outside Vσ,g with its hidden bits other than zg . Let νg be the distribution of the group’s label and zg under νω given σ, and let Pg apply a uniformly random setter of the group. 26

H OW FAR M UST A T EST E XPLORE ?

Lemma 24 (Common sample distribution) Let ℓ ≥ 0, ℓ0 = nℓ/m and q0 = ℓ0 /(1 + ℓ0 ). The interfaces I + and Iω− have the same sample distribution µℓ from νω , and at a sample the hidden vector is a fair vector independent of the label and of the edits of the run. The number Lg of edits of group g in a run satisfies Pr(Lg ≥ j) = q0j . Given Lg = j, these edits are independent and uniform on the setters of the group, and with Λσ,g,j the conditional distribution of the final rest, X q0j (νg Pgj ) ⊗ Λσ,g,j . (10) µℓ (· | σ) = (1 − q0 ) j≥0

Proof Each edit lies in the group with probability n/m, so for 0 ≤ y ≤ 1 Ey Lg =

X j≥0

(1 − q)q j (1 − n/m + (n/m)y)j =

1−q 1 = . 1 − q(1 − n/m + (n/m)y) 1 + ℓ 0 − ℓ0 y

So Lg is geometric with mean ℓ0 . A random edit can first decide whether it lies in the group and then choose its variable and value, and the choices inside the group are independent of these decisions, of the length of the run and of the choices outside the group. The setters of the group act only on its labels and zg , the other setters act only on the rest, and the start state draws these two parts independently given σ. This gives (10) for each of the two interfaces. They move labels in the same way, and the hidden vector is its fair initial value plus an amount determined by the labels and the edits, so it stays a fair vector independent of the labels and the edits. So the two sample distributions are equal.

E.3. The distance Lemma 25 (Forcing walk) Let w0 , . . . , wn1 satisfy wt = Tit ,at wt−1 , let every variable that occurs be written exactly twice, first with a value a and then with 1 − a, let each first write change the state, and let wn1 ̸= w0 . Then every composable interface I˜ on a finite set S ′ ⊇ S disagrees with one of these calls. Proof If I˜ kept all of them, it would follow the same states. Before the first write to a variable i, the reading of I˜ at i is that of w0 . As the first write, of a, changes the state, this reading is 1 − a, and the last write restores it. Variables that do not occur never change, and neither does the hidden data ˜ So I˜ would return to w0 , a contradiction. The argument does not use the readers of I. of I. Lemma 26 (One group) Let ℓ ≥ 0, fix ω, a copy σ and a group g, and let I˜ be a composable interface on a finite set S ′ ⊇ S, with Di,a the set of states of S at which Ti,a of Iω− and T̃i,a differ. Then 8J X 1 − q0J ≤ µℓ (Di,a | σ). (11) i∈Vσ,g , a J +1 Proof A random loop. Fix the rest of the state, and draw zg uniformly. Let π ′ , π ′′ be independent ′ ′′ , and let X , Y be the relative block labels with ones at the uniform permutations of Bσ,g and Bσ,g t t first t elements. From the relative label (XJ , YJ ), the word Q writes the relative value 1 to π ′ (J + 1), . . . , π ′ (3J), then to π ′′ (J + 1), . . . , π ′′ (3J), then the relative value 0 to π ′ (3J), . . . , π ′ (J + 1), and then to π ′′ (3J), . . . , π ′′ (J + 1). A relative value ā at i is the setter Ti,ā⊕eσ,i . During the first segment fg,2 = 0, the second and fourth segments do not change zg , and during the third segment 27

G UO R EN YANG S UN YANG

fg,2 = 1 while fg,1 falls from 1 to 0 once. So Q returns to its label with zg toggled, and Lemma 25 applies to its 8J calls. Let occP i,a (X) be the expected number of calls of Ti,a on the walk whose argument lies in X. Then 1 ≤ i∈Vσ,g ,a occi,a (Di,a ). Occupation. In the first segment, the call at weight t has the argument with relative label (Xt , YJ ). The other segments are alike. The current hidden bit is a fair bit independent of the permutations. So this argument has the distribution of νg given the first side and the weight t, an event of probability 1/(8J). Given Xt , the next variable written to the relative value 1 is uniform on the 4J − t ≥ J + 1 relative zeros of Xt , and the next one written to 0 in the third segment is uniform on the t ≥ J + 1 relative ones. At a fixed state, (i, a) is one relative value. So, state by state, occi,a ≤ (8J/(J + 1)) νg . Noisy loops. Fix a word W of j ≤ J − 1 setters of the group, and let LW be its action on labels: a coordinate that W does not write keeps its value, and a written one takes its last written value. Let L̂W apply LW to the label and keep the hidden bit. As the hidden bit of νg is fair and independent of the label, and W adds to it an amount determined by the label, νg W = (L̂W )∗ νg . Apply LW to all labels of the loop Q, skip its calls to variables that W writes, and start from a fresh fair hidden bit; call the result the noisy loop. By induction over the positions, the label at each position is the image under LW of the label of Q there. Let occW i,a be the occupation measure of the noisy loop. If W writes W i, then occi,a = 0. Otherwise the argument of the noisy loop has the distribution of L̂W applied to the argument of Q, so occW i,a = (L̂W )∗ occi,a ≤ (8J/(J + 1))(L̂W )∗ νg = (8J/(J + 1)) νg W . As j ≤ J − 1, every low end of the loop has weight at most J + j ≤ 2J − 1 and every high end weight at least 3J − j ≥ 2J + 1. Every remaining write changes the relative label by one. So in the third segment the weight of the first block falls past 2J exactly once while fg,2 = 1, and the noisy loop returns to its label with the hidden bit toggled. Every first write of a variable changes the state. So Lemma 25 applies again. Summing. Averaging over j independent uniform setters of the group and over the rest drawn from Λσ,g,j gives, for 0 ≤ j < J,   8J X 1≤ (νg Pgj ) ⊗ Λσ,g,j (Di,a ). i∈V , a J +1 σ,g Summing with coefficients (1 − q0 )q0j and using (10) gives (11). Lemma 27 (Distance) For every ω and ℓ ≥ 0, Dµ∞ℓ (Iω− ) ≥

Ng (J + 1) (1 − q0J ). 16mJ

If Ng = ⌊m/n⌋, this is at least (1 − q0J )/(256J). If Ng = 1 and the group is the same in all copies, then Dµ∞ℓ (Iω− ) ≥ ((J + 1)/(128J 2 ))(1 − q0J ) ≥ (1 − q0J )/(128J). ˜ for a candidate I. ˜ Proof Let R = Rµℓ (Iω− , I) P The groups of one copy are disjoint, so summing (11) J over g gives Ng (1 − q0 ) ≤ (8J/(J + 1)) i∈[m],a µℓ (Di,a | σ). The right side now sums over fixed setters, so we may average over the uniform copy σ, which gives Ng (1−q0J ) ≤ (8J/(J +1))·2mR. As ⌊m/n⌋ ≥ m/(16J), the second claim follows. A sum over one group alone could not be bounded by 16JR in this way, as the group varies with the copy. If it does not vary, averaging (11) over σ gives 1 − q0J ≤ (8J/(J + 1)) · 16JR.

28

H OW FAR M UST A T EST E XPLORE ?

E.4. Renaming Couple the executions of a tester on I + and Iω− by the same internal randomness and the same samples, drawn from the common distribution µℓ together with the latent sides and edits. The hidden vector of a sample is a fresh fair vector, which is legal by Lemma 24. Lemma 28 (Renaming) Suppose that the samples drawn lie in distinct copies and that, in the execution on I + , for each sample and each group g, one of fg,1 , fg,2 is constant on the labels of all states held in the copy of this sample. Then the two transcripts coincide. Proof Fix a sample w∗ = (σ, v∗ , z∗ ). In the execution on I + all states held in copy σ have hidden vector z∗ . If fg,1 is constant on their labels, put bg = 0. Otherwise let bg be the constant value of fg,2 . Put   X bg [fg,1 (σ, v) ⊕ fg,1 (σ, v∗ )] eg . ren(σ, v, z∗ ) = σ, v, z∗ ⊕ g

− + Then ren fixes w∗ , keeps labels and is injective. By (9), Ti,a ren(w) = ren(Ti,a w) whenever w and + ′ Ti,a w are held: for i ∈ Bσ,g the change of z in (9) is exactly that of ren, and the other setters change neither z nor any fg,1 . The union of these maps over the samples is injective, as states of distinct copies differ. By induction over the steps of the tester, each state it holds on Iω− is the image of the one it holds on I + , so all readings, comparisons, depths and choices agree.

E.5. Unmasked: a ball around each sample Lemma 29 (Unmasked transcripts) Let ω be unmasked, let d ≥ 0 and t̂ ≥ 1 be integers with Jt̂ = J(1 − 1/n)t̂ > d, and put p̂ = q0t̂+1 + exp[−(Jt̂ − d)2 /(2t̂)]. The transcripts of a tester of depth at most d with at most s samples of µℓ on I + and on Iω− differ in total variation by at most sp̂ + s(s − 1)/(2Nc ), whatever its number of setter calls. Proof Fix a side, condition on the complete initial label of the frozen block, and let Zj be the weight of this block after j edits of the group. A coordinate is untouched with probability (1 − 1/n)j , and otherwise its last value is a fair bit, so EZj = 2J ∓ J(1 − 1/n)j on a side with initial weight J or 3J. Changing one edit changes Zj by at most two, so the bounded-difference inequality (van 2 Handel, 2016) gives Pr(Zj − EZj ≥ y) ≤ e−y /(2j) , and the same for the lower tail. Call a sample good if Zj ≤ 2J − d − 1 on the low side and Zj ≥ 2J + d on the high side. Then the threshold function of the frozen block is constant on the Hamming ball of radius d around the label of the sample. For 1 ≤ j ≤ t̂, a failure needs a deviation of at least Jt̂ − d in a fixed direction. For j = 0 the sample is good, as J ≥ Jt̂ > d. So a sample is good except with probability p̂. A held state on I + differs from its sample in at most d coordinates, as a write changes one coordinate. Lemma 28 finishes the proof, and two of s samples share a copy with probability at most s(s − 1)/(2Nc ).

E.6. Masked: every query separately For polynomial budgets the tester queries few labels, so a mask replaces the union over the whole ball by a union over the queries. In this subsection Ng = ⌊m/n⌋, and ω is uniform: for each copy, independently, a uniform mask on {0, 1}m , uniform disjoint groups and uniform splits into blocks. 29

G UO R EN YANG S UN YANG

We let the tester learn the length of each run, which only helps it. Write each edit Ti,a of a sample in copy σ as the pair (i, ā) with relative value ā = a ⊕ eσ,i . The latent data K of a sample in a new copy are the groups and blocks of this copy, the sides, the initial relative label and the list of pairs of its edits. The tester sees the visible label v ⋆ of the sample and the length of its run, and it holds the hidden vector only behind a handle. Hidden from it are K and the mask. Lemma 30 (Independence) Generate the copies of the first s potential samples in advance, condition on the event that they are distinct, and condition on the table of their run lengths. (i) The visible label of each sample is uniform and independent of its latent data, and its hidden vector is a fair vector independent of both. The data of different samples are independent. (ii) The whole execution of the tester on I + is a function of the visible labels of the samples, the table and the internal randomness, and it does not depend on the mask or the latent data. (iii) So, for each held state, its sample and the set Y ⊆ [m] of coordinates where its label differs from the label of this sample are independent of the latent data of all samples. If the depth is at most d, then |Y | ≤ d. Proof (i) Fix the length of a run in a new copy σ. The groups, the blocks, the sides and the initial relative label do not depend on eσ . Given these and eσ , the pairs are independent and uniform on [m] × {0, 1}, as a is a fair bit independent of i. So K is independent of eσ . The relative end label u⋆ is a function of K, as each coordinate keeps its initial relative value or takes the last relative value written toPit. The visible label is v ⋆ = eσ ⊕ u⋆ . So, for each v and each event E, Pr(v ⋆ = v, K ∈ E) = y Pr(K ∈ E, u⋆ = y) Pr(eσ = v ⊕ y) = 2−m Pr(K ∈ E): v ⋆ is uniform and independent of K. The hidden vector is a fair vector independent of K and eσ by Lemma 24. Different samples lie in different copies, whose data are independent. (ii) In a copy of I + , a setter replaces one coordinate of the label and keeps the hidden vector. So the end points of paths and their equalities depend only on the root label and the setters called. By induction over the steps of the tester, each reading, each comparison and each choice is a function of the visible labels, the table and the internal randomness. (iii) This follows from (i) and (ii). A write changes one coordinate of the label, so a state of depth at most d has |Y | ≤ d. Lemma 31 (Masked transcripts) Let 0 ≤ d < m/2 and t̂ ≥ 0 be integers, η = 1 − 2d/m, and   ζ = exp[−Jη 2 /2] + exp − J 2 η 2 (1 − 1/n)2t̂ /(8(4J + t̂)) .

(12)

A tester of depth at most d with at most s samples of µℓ and at most sh samples and setter calls in total has transcripts on I + and on Iω− that differ in total variation by at most sNg q0t̂+1 + sh Ng ζ + s(s − 1)/(2Nc ). This holds with free reader calls, comparisons and computation, and also if the tester learns the length of each run. Proof One query, one group. Fix Y with |Y | ≤ d and a group g, and condition on Lg = j ≤ t̂. This keeps the law of the groups, as the number of edits of a set of n variables has the same distribution for each such set. So the frozen block Bgf is a uniform 4J-subset of [m]. Let ov = |Y ∩ Bgf |, so Eov ≤ 4Jd/m = 2J(1 − η). Reveal the 4J elements of Bgf one at a time. Each step has 30

H OW FAR M UST A T EST E XPLORE ?

conditional range at most one, as swapping two elements changes ov by at most one, so the Azuma– 2 Hoeffding inequality (van Handel, 2016) gives Pr(ov − Eov ≥ y) ≤ e−2y /(4J) . With y = Jη, 2 Pr(ov > 2J(1 − η/2)) ≤ e−Jη /2 , and otherwise 1 − ov/(2J) ≥ η/2. Let Z be the relative weight of Bgf at the queried label, and let EZ be its conditional expectation given Bgf , the side, Y and Lg = j. Given Lg = j, the edits of the group are independent and uniform on its pairs. Each initial bit has mean 1/4 or 3/4, a coordinate is untouched with probability θj = (1 − 1/n)j , and otherwise its last relative value is fair. Flipping the ov coordinates of Y in Bgf gives EZ = 2J ∓ J(1 − ov/(2J))θj , with the sign of the side. Now fix Bgf and the side. The initial label is the first J or 3J elements of a uniform permutation of Bgf . Swapping two of them changes at most two initial bits, and changing one pair at most two final bits. So, given these data, Z is a function with at most 4J + j martingale 2 increments of conditional range at most two, and Pr(Z − EZ ≥ y) ≤ e−y /(2(4J+j)) , also for the lower tail. If 1 − ov/(2J) ≥ η/2, crossing the threshold 2J needs a deviation of at least Jηθt̂ /2 in a fixed direction. Averaging over Bgf and the side, the threshold function of Bgf at the queried label differs from its value on the side with probability at most ζ. All queries and groups. Let the execution on I + be good if the first s potential samples lie in distinct copies, each drawn sample has Lg ≤ t̂ for every group, and at each of the at most sh held states and for every group, the threshold function of the frozen block of its sample has its value on the side. The union bound runs over the unconditioned execution on I + and uses only the distribution of each Lg , not a joint law of the groups. By Lemma 30(iii), the query bound applies to each held state and each group. This gives the stated bound on the probability that the execution is not good, and Lemma 28 applies to good executions. Lemma 32 (Expected cost) Let a tester accept a first input with probability at least 2/3 and a second input with probability at most 1/3, where an input may be a mixture of instances. Fix the operations that it counts. The truncation at t of an execution is the whole execution before its (t + 1)-st counted operation, with the free operations in between and the outcome if it stops there. Let p̂ ≥ 0, and suppose that for every t the truncations at t on the two inputs differ p in total variation by at most tp̂ + t(t − 1)/(2Nc ). Then the tester uses at least ⌊min{1/(12p̂), Nc /6}⌋/6 counted operations in expectation on the first input, with 1/0 = ∞. p Proof Let t = ⌊min{1/(12p̂), Nc /6}⌋, so the truncations at t differ by at most 1/6. Let E be the event that the tester accepts before its (t + 1)-st counted operation, which the truncation at t determines, and let E ′ be the event that it makes more than t of them. With Pr+ and Pr− for the first and the second input, Pr− (E) ≤ 1/3, so Pr+ (E) ≤ 1/2, and Pr+ (E) ≥ 2/3 − Pr+ (E ′ ). So Pr+ (E ′ ) ≥ 1/6, and the expected number is at least t/6. Lemmas 29 and 31 supply this hypothesis. The tester stopped before its (t + 1)-st counted operation has at most t counted operations, and by Lemma 28 the coupling keeps its free operations and its outcome. E.7. Necessity Proposition 33 (Necessity) Fix either distance. Consider testers that certify this distance at ϵm with confidence 2/3 on samples of µℓm , for all interfaces and start distributions. 31

G UO R EN YANG S UN YANG

(a) Let ϵm = 1/(32m), 2 ≤ dm ≤ ⌊m/16⌋, ℓ∗m = m log(m/dm )/ log m and ℓm = o(ℓ∗m ). Every such tester of depth at most dm uses a superpolynomial expected number of samples on I + , for the unmasked start distribution. (b) Fix C > 1 and 0 < c < 1/2. Let 1/(32m) ≤ ϵm ≤ (log m)−C , 2 ≤ dm ≤ cm and ℓm = o(m log(1/ϵm )/ log m). Every such tester of depth at most dm , even if it learns the length of each run, uses a superpolynomial expected number of samples and setter calls on I + , for some start distribution νω . (c) Let 1/(32m) ≤ ϵm = o(1/ log m), J = ⌊1/(512ϵm )⌋, ℓm = 0 and 2 ≤ dm ≤ ⌊m/2 − wm ⌋ 2 /(m2 log m) → ∞. The conclusion of (b) holds. with wm > 0 and Jwm Proof (a) Take the unmasked assignment with J = ⌊m/8⌋, n = 8J and Nc = 2m . As ℓ∗m ≤ m, ℓm = o(m), so J/(1 + ℓ0 ) → ∞ and q0J → 0. Lemma 27 gives Dℓ∞m ≥ (1 − o(1))/(128J) ≥ (1 − o(1))/(16m) > ϵm for large m and every ω. So a tester as in the statement accepts (I + , νω ) with probability at least 2/3 and (Iω− , νω ) with probability at most 1/3. Put d+ = max{dm , n3/4 } and t̂ = ⌊(n − 1) log(J/(3d+ /2))⌋. As dm ≤ J/2 = n/16 and n3/4 ≤ n/16 for large m, the logarithm is at least log(4/3), so t̂ ≥ 1. As log(1 − 1/n) ≥ −1/(n − 1), Jt̂ ≥ 3d+ /2, so Jt̂ − dm ≥ d+ /2. As t̂ ≤ n log n/4 and d+ ≥ n3/4 , the second √ + 2 term of p̂ in Lemma 29 is at most e−(d ) /(8t̂) ≤ e− n/(2 log n) . Let a0 = 1 − log 12/ log 16 > 0. If dm ≥ n3/4 , the logarithm in t̂ is log(n/(12dm )) ≥ a0 log(n/dm ), as n/dm ≥ 16. Otherwise it is at least (log n)/8 ≥ log(n/dm )/8 for n ≥ 128 . So t̂ is at least a positive constant times m log(m/dm ), as n/m → 1. This gives (t̂ + 1)/((1 + ℓ0 ) log m) → ∞, since ℓ0 ≤ ℓm = o(ℓ∗m ) and ℓ∗m → ∞. As q0 ≤ e−1/(1+ℓ0 ) , p̂ = m−ω(1) . Lemma 32, counting samples, gives the claim. (b) Take J = ⌊1/(512ϵm )⌋, n = 8J, Ng = ⌊m/n⌋ and Nc = 2m . For large m, J ≥ (log m)C /1024 and log J ∼ log(1/ϵm ), and J ≤ m/16 as ϵm ≥ 1/(32m), so Ng ≥ 2. As log(1/ϵm ) ≤ log(32m), ℓm = o(m), so h q0J ≤ exp −

i h i J 1 = exp − → 0. 1 + 8Jℓm /m 1/J + 8ℓm /m

Lemma 27 gives Dℓ∞m ≥ (1 − o(1))/(256J) ≥ (2 − o(1))ϵm > ϵm for large m and every ω. So a tester as in the statement accepts (I + , νω ) with probability at least 2/3 and (Iω− , νω ) with probability at most 1/3. Let aC = (C − 1)/(4C) > 0 and t̂ = ⌊aC (n − 1) log J⌋ in Lemma 31. As log(1 − 1/n) ≥ −1/(n − 1), (1 − 1/n)t̂ ≥ J −aC . With η0 = 1 − 2c > 0 and η ≥ η0 , the exponent of the second term of (12) is at least η02 J 1−2aC /(8(4 + 8aC log J)). Here C(1 − 2aC ) = (C + 1)/2 > 1, and y 1−2aC /(4 + 8aC log y) increases for large y. So, with J ≥ (log m)C /1024, this exponent divided by log m is at least a positive constant times (log m)(C−1)/2 / log log m, which tends to infinity. The first term of (12) is superpolynomially small as well, so ζ = m−ω(1) . Next,  log m n log J ℓm log m −1 = + → ∞, (1 + nℓm /m) log m n log J m log J so q0t̂+1 ≤ exp[−(t̂ + 1)/(1 + ℓ0 )] = m−ω(1) . As Ng ≤ m, p̂ = Ng (q0t̂+1 + ζ) = m−ω(1) . Lemma 32, counting samples and setter calls, with the mixtures over ω of the instances (I + , νω ) and of the instances (Iω− , νω ) as the two inputs, gives the bound on the first mixture, hence for some ω. 32

H OW FAR M UST A T EST E XPLORE ?

(c) Take n = 8J, Ng = ⌊m/n⌋ and Nc = 2m , so J ≤ m/16. As q0 = 0, Lemma 27 gives ∞ Dν ≥ 1/(256J) ≥ 2ϵm . As dm ≤ m/2 − wm , η = 1 − 2dm /m ≥ 2wm /m > 0, so dm < m/2 and Lemma 31 applies. Take t̂ = 0 there, so ζ ≤ 2 exp[−Jη 2 /32]. Squaring η ≥ 2wm /m, whose 2 /(8m2 )] = m−ω(1) . Conclude as in (b). two sides are positive, gives ζ ≤ 2 exp[−Jwm Proof of Theorem 2 Part (b) is Corollary 21 and (8). For part (a), ϵm = m−β lies in the range of Proposition 33(b) for C = 2 and large m, and log(1/ϵm )/ log m = β, so its hypothesis is ℓm = o(m). If ℓm ≥ αm for all large m, part (b) gives a polynomial budget at depth 2 ≤ dm . If ℓm is not Ω(m), some subsequence has ℓm /m → 0, and part (a) along it excludes a polynomial budget. For the statement after the theorem, let (log m)C ≤ ℓm = o(m) and ϵm = 1/ℓm , which lies in the range of Proposition 33(b) for large m. Fix y > 0. As t/ log t increases for t ≥ e and ℓm ≤ ym for large m, ℓm log m/(m log ℓm ) ≤ y log m/ log(ym) → y. So ℓm = o(m log(1/ϵm )/ log m). 2 Proof of Theorem 4(c) Upper bound. By p Hoeffding’s inequality, τ2 ≤ exp[−2(d − 2 − m/2) /m] for d ≥ 2 + m/2. √ So d = 2 + ⌈m/2 + (m/2) log(2(m + 2)/ϵm )⌉ gives (m + 2)τ2 ≤ ϵm /2, and d = m/2 + O( m log m). If this value exceeds m + 1, take d = m + 1 and part (a). Part (b) gives certification of both distances with ⌈2 log 3/ϵm ⌉ rounds of at most 2m2 + 6m setter calls, which is a polynomial budget. Lower bound. Take wm = m1−β/2 log m, which is positive and o(m), in Proposition 33(c). For 2 /(m2 log m) ≥ log m/1024 → ∞. So depths at most m/2 − w large m, J ≥ mβ /1024, so Jwm m have no polynomial budget, for both distances.

E.8. Samples from the start distribution Let ℓ = 0, so that a tester draws samples of the start distribution µ = ν. A tester is an (ϵ, δ)-tester if it certifies the distance under µ at ϵ with confidence 1 − δ for every interface on a finite set and every start distribution µ. Theorem 34 (Samples from the start distribution) For both distances, at ℓ = 0: let 0 < δ < 1/2, m ≥ 32 and 0 < ϵ ≤ 1/512. No (ϵ, δ)-tester has a bound on its number of samples, or on its expected number, that depends only on m, ϵ and δ, if its depth is at most ⌊min{m/8, 1/(128ϵ)}⌋, which is at least min{m, 1/ϵ}/256. Proof of Theorem 34 Let y = min{m/8, 1/(128ϵ)}. The ranges of m and ϵ give y ≥ 4, so J = ⌊y⌋ ≥ y/2 ≥ min{m, 1/ϵ}/256, and m ≥ 8J. Take the unmasked instance with ℓ = 0 and any Nc . As J ≤ 1/(128ϵ), Lemma 27 gives Dν (I − ) ≥ Dν∞ (I − ) ≥ 1/(128J) ≥ ϵ. Fix a start state with block labels u′0 , u′′0 , hidden bit z0 and b = f2 (u′′0 ), and on the states of its copy with hidden bit z0 whose block labels lie within Hamming distance J of (u′0 , u′′0 ) put ren(σ, v, z0 ) = (σ, v, z0 ⊕b[f1 (u′ )⊕f1 (u′0 )]). This map fixes the start state, keeps the readers and is injective. Setters of Bσ′′ and of passive variables do not change f1 , and I − treats them as I + does. A setter of Bσ′ whose two labels lie in this ball changes f1 only while f2 = b. Indeed, if |u′′0 | ∈ {J, 3J} and f2 (u′′ ) ̸= b, then u′′ is at Hamming distance at least J from u′′0 , so u′ = u′0 at both ends and f1 does not change. If |u′0 | ∈ {J, 3J} and f1 changes, one end is at Hamming distance at least J from − + u′0 , so u′′ = u′′0 and f2 = b. Every start state has such a block. So Ti,a ren(w) = ren(Ti,a w) for ′ every state w of this domain whose block labels lie within Hamming distance J − 1 of (u0 , u′′0 ). A 33

G UO R EN YANG S UN YANG

setter call of depth at most J from the start state acts on a state reached by at most J − 1 calls. So, as in Lemma 28, the two transcripts of a tester of depth at most J coincide when its samples lie in distinct copies, pand two of s samples share a copy with probability at most s(s − 1)/(2Nc ). Let t = ⌊ Nc (1 − 2δ)⌋, let E be the event that the tester accepts before it draws a (t + 1)-st sample, and let E ′ be the event that it draws more than t samples. Then Pr− (E) ≤ δ and Pr+ (E) ≥ 1 − δ − Pr+ (E ′ ). The coupling then gives Pr+ (E ′ ) ≥ 1 − 2δ − t(t − 1)/(2Nc ) ≥ (1 − 2δ)/2. Hence the expected number of samples under I + is at least t(1−2δ)/2, which grows without bound with Nc . A bound on the number of samples that depends only on m, ϵ and δ would bound this expectation.

Appendix F. Proof of Theorem 5 The necessity in Theorem 5 follows from Proposition 33(a). If ℓm is not Ω(ℓ∗m ), some subsequence has ℓm /ℓ∗m → 0, and the proposition, applied along it, excludes a polynomial budget of samples. This appendix proves the sufficiency. A random word need not write every variable: short words from its end can stand in for the few variables that it misses. For an integer d¯ ≥ 0, let Nd¯ be the set of P states from which some word of length at most d¯ reaches N , so N0 = N . Let H0 = 0 and Hj = v≤j 1/v. Theorem 35 (Partial coverage) Let m ≥ 2, 2 ≤ d ≤ m, d¯ = d − 2, λ ≥ 1, let µ be λsubinvariant and t = ⌈2m(Hm − Hd¯)⌉. Then Dµ∞ ≤ min{1, 2(t + 1)λt µ(Nd¯)}, and if 2m | |S|, then Dµ ≤ min{1, (t + 1)(t + 4)λt µ(Nd¯)}. The tester. Exhausting all words of length at most d¯ from a sample and evaluating all law instances at their ends has depth at most d¯ + 2 = d. It rejects with probability µ(Nd¯) and accepts every composable interface. So, if K is the coefficient of Theorem 35, ⌈K log(1/δ)/ϵ⌉ samples certify as in Appendix A. The number of setter calls of a sample can be exponential in d. Proof of Theorem 35 The word. Draw t independent uniform setters E1 , . . . , Et , with prefixes Uk = Ek · · · E1 . Let H be the event that at most d¯ variables are not written, and let R0 be the set of these variables. On H, let W0 write 0 once to each variable of R0 in increasing order, and put W = W0 Ut , which writes every variable. The number of draws needed to collect m − d¯ distinct variables has mean m(Hm − Hd¯), so Markov’s inequality gives Pr(H) ≥ 1/2. The distance with added states. Let AW be the set of states with Uk x ∈ / N for k < t and Ut x ∈ / Nd¯. Every step of W0 acts on a state within d¯− 1 writes of Ut x, so the path of x ∈ AW under W avoids N before its last step. By Lemma 13, Lemma 14 applies to AW , and Dµ∞ ≤ µ(S \ AW ). For x ∼ µ independent of the setters, Uk x has distribution µP k ≤ λk µ, and N ⊆ Nd¯. So, dropping H from the numerator and dividing by Pr(H) ≥ 1/2, hX i E[µ(S \ AW ) | H] ≤ 2 λk + λt µ(Nd¯) ≤ 2(t + 1)λt µ(Nd¯). (13) k<t

¯ Let Wg write the values g ∈ {0, 1}R0 to the variables A local rule. Let z ∈ / Nd¯ and |R0 | ≤ d. of R0 , once each, in increasing order. Each suffix of Wg acts on a state within d¯ − 1 writes of z, so these states lie outside N . Commuting a setter Ti,e with i ∈ R0 through Wg and absorbing it by overwrite gives Ti,e Wg z = Wg′ z, where g ′ is g with coordinate i replaced by e. In particular 34

H OW FAR M UST A T EST E XPLORE ?

Wg′′ Wg z = Wg′′ z for all g, g ′′ . Commuting a setter E of a variable outside R0 through Wg gives EWg z = Wg Ez. A second word. Let g1 , . . . , gt be fair bits and g0 ∈ {0, 1}R0 a fair vector, independent of the rest. Put Vk = Tik ,gk and V = V1 · · · Vt , which applies Vt first. For 1 ≤ a ≤ k ≤ t put za,k = Ua−1 Vk+1 · · · Vt x, and for 0 ≤ j ≤ t put x′j = Uj Vj+1 · · · Vt x. The positions used by za,k are disjoint, so before conditioning za,k has distribution µP t−k+a−1 , and x′j has distribution µP t . Consider the event G that all za,k ∈ / N and all x′j ∈ / Nd¯. Summing the t(t + 1)/2 and the t + 1 terms, h t(t + 1) i Pr(G c | H) ≤ 2 + t + 1 λt µ(Nd¯). (14) 2 A witness. Assume G. Fix k and let jk be the first position with ijk = ik . Commutation at za,k for a < jk and overwrite at zjk ,k give, for j ≥ k, Uj Vk Vk+1 · · · Vt x = Uj Vk+1 · · · Vt x. Removing V1 , . . . , Vj in turn gives Uj V x = x′j . Let y = Wg0 V x, and let û be the label predicted by applying the writes of V and Wg0 to r(x). Given W and x, û is uniform: V applies V1 last, so each written variable takes the bit gk of V at its first position k in W , and each variable of R0 a coordinate of g0 . The steps of V act at z1,k ∈ / N and those of Wg0 within d¯ − 1 writes of x′0 = V x ∈ / Nd¯, so r(y) = û. The steps of Ut avoid R0 and act at Uj−1 V x = x′j−1 ∈ / Nd¯, so the local rule moves Wg0 through them: Ut y = Wg0 Ut V x = Wg0 Ut x. As x′t = Ut x ∈ / Nd¯, the local rule gives W0 Wg0 Ut x = W0 Ut x. Hence W y = W x and r(y) = û. The distance on the same states. By Lemma 14, Dµ ≤ µ(S \ AW ) + ∆AW . Given W , the term ∆AW is at most the probability that û occurs nowhere in the fiber of x, which needs G c . Averaging given H and adding (13) and (14) gives 2[t(t + 1)/2 + 2t + 2]λt µ(Nd¯) = (t + 1)(t + 4)λt µ(Nd¯). Proof of the sufficiency in Theorem 5 Let 2 ≤ d ≤ m/16, d¯ = d − 2, and ℓ ≥ bℓ∗m with ℓ∗m = m log(m/d)/ log m and a constant b > 0. For d¯ ≥ 1, integral comparison gives Hm − Hd¯ ≤ ¯ and d¯ ≥ d/3 for d ≥ 3, so log(m/d) ¯ ≤ log 3 + log(m/d) ≤ 2 log(m/d). For d¯ = 0, log(m/d), Hm ≤ 1 + log m ≤ 2 log(m/2) for m ≥ 32. So t ≤ 5m log(m/d), and with λ = 1 + 1/ℓ, λt ≤ et/ℓ ≤ m5/b . As (t + 1)(t + 4) is polynomial in m, the tester above uses a polynomial number of samples, for both distances; for D∞ , no condition on |S| is needed. The explicit bound. Let m ≥ 96, d = ⌊m/16⌋ and ℓ ≥ ςm/ log m with ς > 0. Then d¯ ≥ m/32 ≥ 1, so Hm − Hd¯ ≤ log 32 and t ≤ 2m log 32 + 1 ≤ 8m, and (t + 1)(t + 4) ≤ 140m2 . Also λt ≤ et/ℓ ≤ m8/ς . So ⌈140m2+8/ς log(1/δ)/ϵ⌉ samples certify both distances.

Appendix G. Proof of Theorem 1 Route. Part (a) follows the four steps of Section 3, and each subsection gives one ingredient. • Appendix G.1 sets up continuous time and predicted labels, and gives two events on which the history of a variable matters only through Bj : (16) moves the last write to the front, and strongly good words allow a whole history to be replaced. Their failure probabilities are charged to γ in (17) and (18). • Appendix G.2 couples the histories given B as the time grows, which bounds the derivative in time of the end state given B in (19). • Appendix G.3 proves a bound on the density of the time given a label (Lemma 36) and turns a derivative into a variance bound (20). 35

G UO R EN YANG S UN YANG

• Appendix G.4 introduces the weight ϖ, which is what a setter pays when it resamples a history. It bounds the error from resampling one history at a time (23) and from the time (25), and it chooses a state f (b) for each label b ̸= r(o). • Appendix G.5 treats the label r(o), where the weight is not integrable at time 0 and f (r(o)) = o. • Appendix G.6 places the chosen states in one cube and proves the bound (28) for ℓ ≥ 2. • Appendix G.7 treats means at most 2, where a Stein kernel replaces the coupling and the integral kernel. • Appendix G.8 assembles the cases, with means of at least 2m taken from (8), and Appendix G.9 proves part (b). Throughout Appendices G.1–G.6, m ≥ 2, the start distribution is ν = δo , ℓ ≥ 2, q = ℓ/(1 + ℓ), µ = µℓ , γ = γµ , α = ℓ/m (this ratio, not the free constant α of Theorem 2), and all law instances hold at o. Each law instance then fails with probability at most γ at x ∼ µ, and this is the only use of γ. G.1. Histories and two good events Continuous time. Let the edits the times of a Poisson process of rate 1, each a uniformly Parrive at −t n n random setter, and let ρt = e n≥0 (t /n!) νP be the distribution of the state at time t. Stop at an independent time ι with density ℓ−1 e−t/ℓ . The number L of edits before ι satisfies Z ∞ 1 ℓn Pr(L = n) = e−(1+1/ℓ)t tn dt = = (1 − q)q n , ℓ n! 0 (1 + ℓ)n+1 by integration by parts and induction on n. So the state X at time ι has distribution µ; this holds forR every start Rdistribution and every ℓ > 0. For a nonnegative function φ on states, this gives ι ∞ E 0 ρs φ ds = 0 e−s/ℓ ρs φ ds = ℓµφ. Predicted labels. Let b0 = r(o). Applying the same edits to the vector b0 as coordinate writes gives the predicted label B. Split by variable, the edits form independent Poisson processes of rate 1/m, with independent fair written values. So, with w = |b ⊕ b0 |, Pr(B = b | ι = t) = 2−m (1 − e−t/m )w (1 + e−t/m )m−w ,

(15)

which is positive for t > 0. Given B = b and ι = t, the histories of the variables, with their arrival times and written values, are still independent, as the event B = b is the intersection of one event for each variable. Moving the last write to the front. Fix a variable j. For an edit E = Ti,a , let Ij (x, E) indicate that, for b = 0 or b = 1, the equality P Tj,b Ex = ETj,b x fails if i ̸= j, or Tj,b Tj,a x = Tj,b x fails if i = j. Let I¯j (x) = (2m)−1 i,a Ij (x, Ti,a ), so µI¯j ≤ 2γ. Let W = En · · · E1 be a word, Us = Es · · · E1 and U0 = Id, and let W−j delete the writes to j from W . If Ij (Us−1 o, Es ) = 0 for every s before the last write to j, then W o = W−j Tj,Bj o.

(16)

Indeed, if W writes j, let s∗ be its last write to j, with value b = Bj , and put T∗ = Tj,b . For (−j) (−j) s < s∗ , induction gives T∗ Us o = Us T∗ o, where Us deletes the writes to j: an edit of another variable commutes with T∗ at Us−1 o, and a write to j is overwritten by T∗ . So Us∗ o = T∗ Us∗ −1 o = 36

H OW FAR M UST A T EST E XPLORE ?

(−j)

Us∗ −1 T∗ o, and the later edits do not write j. If W does not write j, then Bj = b0j , and write-back at o gives Tj,b0 o = o. If Ij (Us−1 o, Es ) = 0 for all s, the same induction gives Tj,a W o = W−j Tj,a o j for a = 0, 1. Let p̄j (t) be the probability that the word of the edits up to time t fails the condition of (16), and pj (t) the probability that it fails the stronger condition for all s. An edit arriving at time s acts at a state of distribution ρs , and a later write to j occurs with probability 1 − e−(t−s)/m , independently of this state and this edit. So Z t Z t −(t−s)/m ¯ (17) ] ds, pj (t) ≤ ρs I¯j ds. p̄j (t) ≤ ρs Ij [1 − e 0

0

Strongly good words. Call a word strongly good for j if the four overwrite equalities Tj,a Tj,b x = Tj,a x hold at every prefix state, including the end state, and every edit of another variable commutes with Tj,0 and Tj,1 at the state where it acts. If a word is strongly good for j, then replacing the whole history of j by another one with the same value Bj keeps the end state. To see this, scan the old writes to j, the new writes to j and the common other edits in their merged order, with x the old prefix state, y the new prefix state and e the new predicted value of j. The invariant y = Tj,e x holds at the start by write-back at o. An old write to j changes only x, and overwrite at x keeps the invariant. A new write to j changes y and e, and overwrite at x keeps it. Another edit commutes with Tj,e at x. At the end, y = Tj,Bj X. Induction along the old word, with commutation for other edits and Tj,a Tj,a x = Tj,a x for writes to j, gives Tj,Bj X = X. So y = X. A new write may come after all old edits, which is why the end state is included. Let Ij◦ indicate that one of the four overwrite equalities fails at a state, and let I¯j∗ be Ij◦ plus the average over the edit of the indicator that this edit, if it does not write j, fails to commute with Tj,0 or Tj,1 . Then µIj◦ ≤ 4γ and µI¯j∗ ≤ 6γ. Let p∗j (t) be the probability that the word up to time t is not Rt strongly good for j, and p∗j (t | b) the same given B = b. Then p∗j (t) ≤ 0 ρs I¯j∗ ds + ρt Ij◦ , so E p∗j (ι) ≤ (6ℓ + 4)γ.

(18)

G.2. A pure-birth coupling given the label Fix a variable, let y = t/m, pn = e−y y n /n! and Rn = Pr{Pois(y) > n}. Given its predicted value and t, the number of writes to this variable has the masses pn /(1 − p0 ) for n ≥ 1 if the value differs from the initial one, and 2p0 /(1+p0 ) for n = 0 and pn /(1+p0 ) for n ≥ 1 otherwise. Differentiating the distribution functions 1 − Rn /(1 ∓ p0 ) in t, using dp0 /dy = −p0 and dRn /dy = pn , shows that these masses are the marginals of a pure-birth process with rates 1h p0 Rn i 1− , m (1 − p0 )pn

1h p0 Rn i 1+ (n ≥ 1), m (1 + p0 )pn

1 (n = 0), m(1 + p0 )

in the two cases. Let N (t) be the state of this process at time t. Its entrance law is N (0+) = 1 when the predicted value differs from the initial one, and N (0+) = 0 when they are equal. As P v y Rn /pn = v≥1 y n!/(n + v)! ≤ e − 1, all rates lie in [0, 2/m]. Given n ≥ 1 writes, the normalized arrival times are independent uniform points of [0, 1], the last value is the given one, and the earlier values are fair. At a birth, insert an independent uniform point. If it is not the new last point, give it a fair value. If it is, redraw the old last value as a fair bit and give the new point the given value. For n = 0 there is no old last value, so the first birth skips the redraw. This keeps the 37

G UO R EN YANG S UN YANG

law of the history. Multiplying by t does not change the order of the normalized points. So running this process independently for each variable couples the histories given B = b for all t > 0, and a birth changes one history only. If the word before the birth is strongly good for that variable, the end state does not change. P Let gb,x (t) = Pr(X = x | B = b, ι = t) and vb (t) = 1 − x gb,x (t)2 . As the rates are at most R t+h P ∗ 2/m, the probability that the end state changes in (t, t + h] is at most (2/m) t j pj (s | b) ds. These conditional probabilities are quotients of power series that converge uniformly with their derivatives on compact subsets of (0, ∞). So X 4 X ∗ ′ |gb,x (t)| ≤ p (t | b). (19) x j j m G.3. An integral kernel of the time given the label Lemma 36 (Integral kernel) Let n ≥ 1 and 0 ≤ k̄ ≤ n be integers and ℓ′ > 0. Let ψ be the ′ probability density on (0, ∞) proportional to e−t/ℓ (1 − e−t/n )k̄ (1 + e−t/n )n−k̄ , with distribution function Ψ. Then Ψ(t)(1 − Ψ(t))/ψ(t) ≤ 200(1 + ℓ′ /n) min{t, n} for all t > 0. Proof Let S = (log ψ)′ , so 1 k̄ n − k̄ S(t) = − ′ + − , ℓ n(et/n − 1) n(et/n + 1)

1 1 S(t) ≥ − ′ − . ℓ 2

With a′ = n/ℓ′ and y = e−t/n , n(1 − y 2 )S(t) = (a′ + n)y 2 + (2k̄ − n)y − a′ . The right side has roots y+ ∈ (0, 1] and −y− < 0, with (a′ + n)y+ y− = a′ ; y+ = 1 exactly when k̄ = 0. So ψ has a unique mode at t∗ = −n log y+ : an interior maximum if k̄ ≥ 1, and the boundary point t∗ = 0 if k̄ = 0, when ψ decreases on (0, ∞). With v = e−(t−t∗ )/n , S(t) =

1 1 + (y+ /y− )v (v − 1) , 2 v2 ′ ℓ 1 − y+

where the last fraction is at least 1. Hence S(t∗ + z) ≤ −(1 − e−z/n )/ℓ′ for z > 0, and S(t∗ − z) ≥ (ez/n − 1)/ℓ′ for 0 < z < t∗ . The scale n. For t ≤ t∗ , moving left by at most n the density ratio is at most 1, and beyond that the logarithmic derivative is at least (e − 1)/ℓ′ ≥ 1/ℓ′ . So Ψ(t)/ψ(t) ≤ n + ℓ′ . For t ≥ t∗ , moving right by at most n the ratio is at most 1, and beyond that the logarithmic derivative is at most −(1 − e−1 )/ℓ′ ≤ −1/(2ℓ′ ). So (1 − Ψ(t))/ψ(t) ≤ n + 2ℓ′ . As Ψ(1 − Ψ) ≤ min{Ψ, 1 − Ψ}, always Ψ(1 − Ψ)/ψ ≤ n + 2ℓ′ ≤ 2(1 + ℓ′ /n)n. This gives the claim for t ≥ n/64, as then n ≤ 64 min{t, n}. The scale t. Let t < n/64. If t ≤ t∗ , ψ does not decrease on (0, t], so Ψ(t)/ψ(t) ≤ t. Let ′ t > t∗ , and let q ′ = ℓ′ /(1 + ℓ′ ). If t ≤ q ′ , then for 0 < z < t, ψ(z)/ψ(t) ≤ e(1/ℓ +1/2)t ≤ e, so Ψ(t)/ψ(t) ≤ 3t. Let t > q ′ and ℓ′ ≥ 2, so t ≥ 2/3. For 0 < z ≤ k̄/2 ≤ n/2, ez/n − 1 < 2z/n gives S(z) > −1/ℓ′ −1/2+ k̄/(2z) ≥ 0. So t∗ ≥ k̄/2, and k̄ ≤ 2t. Let z0 = 32t < n/2. For z0 ≤ z ≤ n, ez/n − 1 ≥ z/n and ez/n + 1 < 4 give S(z) ≤ k̄/z − (1 − k̄/n)/4 ≤ 1/16 − 31/128 < −1/16. So ψ does not increase on [t, z0 ], it falls at rate at least 1/16 on [z0 , n], and ψ(n)/ψ(t) ≤ e−n/32 . With the bound n + 2ℓ′ at n and ne−n/32 ≤ 32, 1 − Ψ(t) ≤ 32t + 16 + 32(1 + 2ℓ′ /n) ≤ (104 + 96ℓ′ /n)t. ψ(t) 38

H OW FAR M UST A T EST E XPLORE ?

Let t > q ′ and ℓ′ < 2. For 0 < z ≤ k̄ℓ′ /(2 + ℓ′ ) < n/2, the same estimate gives S(z) > 0, so k̄ ≤ (2/ℓ′ + 1)t. For z ≥ 8t, S(z) ≤ −1/ℓ′ + k̄/z ≤ −(6 − ℓ′ )/(8ℓ′ ) ≤ −1/(2ℓ′ ). So (1 − Ψ(t))/ψ(t) ≤ 8t + 2ℓ′ ≤ 14t, as ℓ′ ≤ (1 + ℓ′ )t < 3t. For a positive probability density ψ with distribution function Ψ and a locally absolutely continuous vector g of probabilities, the inequality ∥y − y ′ ∥22 ≤ ∥y − y ′ ∥1 for probability vectors gives Z ∞ Z X 2 ∥g ′ (z)∥1 Ψ(z)(1 − Ψ(z)) dz. (20) ∥g(t) − g(s)∥2 ψ(s)ψ(t) ds dt ≤ Varψ gx = x

0

s<t

G.4. Weighted errors and the chosen states Let ϖ(t) = 1/(1−e−t/m ), which is at least 1, and Ωℓ = ℓ+(m/q) log(1+ℓ). For every nonnegative φ on states, Z ι h i E ϖ(ι) ρs φ ds ≤ Ωℓ µφ. (21) 0

Indeed, ϖ(t) ≤ 1 + m/t. The constant part gives ℓµφ. RFor the other part, expand ρs φ over ∞ the number k of edits. The coefficient of νP k φ is (m/ℓ) 1/ℓ [v(1 + v)k+1 ]−1 dv, after writing R∞ e−t/ℓ /t = 1/ℓ e−tv dv and exchanging integrals. The substitution (1 + v)−1 = y turns it into P m(1 − q)q k v≥0 q v /(k + v + 1) ≤ (1 − q)q k (m/q) log(1 + ℓ), as q/ℓ = 1 − q. P One history at a time. Let V (t) = b Pr(B = b | ι = t) vb (t). For independent variables ω1 , . . . , ωm and a vector-valued function f of them, X X E∥f − Ef ∥2 ≤ E Varωj (f | ω−j ) = 21 E∥f − f (j) ∥2 , (22) j

j

where f (j) resamples ωj . This is the tensorization of the variance, also called the Efron–Stein inequality (van Handel, 2016). Take f = (1X=x )x and resample the history of j given Bj . By (16) the two end states agree unless one of the Ptwo words fails the condition there, and the two words have the same distribution. So V (t) ≤ 2 j p̄j (t). As ϖ(t)[1 − e−(t−s)/m ] ≤ 1, (17) gives E[ϖ(ι)V (ι)] ≤ 4mℓγ.

(23)

Along a run, the reading of j stays equal to Bj unless success or preservation fails. So, by (21), E[ϖ(ι)1r(X)̸=B ] ≤ mΩℓ γ.

(24)

The time given the label. Let b ̸= b0 . By (15), the density of ι given B = b under the measure ϖ(ι) d Pr is proportional to e−t/ℓ (1 − e−t/m )w−1 (1 + e−t/m )m−w ; call it ψb , with distribution function Ψb . The substitution n = m − 1, k̄ = w − 1, z = nt/m, ℓ′ = nℓ/m reduces it to Lemma 36, and gives Ψb (1 − Ψb )/ψb ≤ 200(1 + α) min{t, m}. Let Zb = E[ϖ(ι)1B=b ]. With (19), (20), ϖ(t) min{t, m}/m ≤ 2 and (18), i X X X 800(1 + α) h ∗ Z Var g ≤ E ϖ(ι) min{ι, m} p (ι | B) b ψ b,x b x b̸=b0 j j m (25) ≤ 1600(1 + α)m(6ℓ + 4)γ. P 2 P Put ḡb,x = Eψb gb,x . The law of total variance gives 1 − x ḡb,x = Eψb vb + x Varψb gb,x . For b ̸= b0 withPSb = r−1 (b) nonempty, let f (b) ∈ Sb have the largest ḡb,x . The largest ḡb,x over 2 and exceeds ḡ all x is at least x ḡb,x b,f (b) by at most the mass of ḡb outside Sb . So 1 − ḡb,f (b) ≤ P 2 P 1 − x ḡb,x + x∈S / b ḡb,x , also when Sb is empty, with the convention ḡb,f (b) = 0. 39

G UO R EN YANG S UN YANG

G.5. The initial label Put f (b0 ) = o. Let v0 (t) = ℓ−1 e−t/ℓ Pr(B = b0 | t) and ϖ0 = ϖv0 , which is not integrable 0 at 0. Given R ∞ B = b and t, the probability of no edits tends to 1 as t ↓ 0, so gb0 ,o (t) → 1. Let e0 = 0 ϖ0 (t)[1 − gb0 ,o (t)] dt. The bound of Appendix G.2 on the probability that the end state RtP changes gives 1 − gb0 ,o (t) ≤ (2/m) 0 j p∗j (s | b0 ) ds. So, by an exchange of integrals, 2 e0 ≤ m

Z ∞X 0

p∗ (s | b0 ) j j

Z ∞ ϖ0 (t) dt ds. s

For t ≤ m, the logarithmic derivative of v0 is at most −1/(et/m + 1) ≤ −1/4, and beyond m at most −1/ℓ. With ϖ(t) ≤ 1 + m/t and ϖ(t) ≤ 2 for t ≥ m, for s ≤ m, 1 v0 (s)

Z ∞

ϖ0 (t) dt ≤ 4 + m[1 + log(1 + 4/s)] + 2ℓ ≤ m[6 + 2α + log+ (1/s)],

s

R∞ using 0 e−z /(z + s/4) dz ≤ log(1 + 4/s) + 1, 4 ≤ 2m and log 5 < 2. For s ≥ m the left side is at most 2ℓ. R1 Also E[log+ (1/ι) p∗j (ι)] ≤ 18γ. For the path term, s e−t/ℓ log(1/t) dt ≤ 1 ≤ 2e−s/ℓ for 0 < s < 1, so its expectation is at most 2µI¯j∗ ≤ 12γ. For the end state, given k edits the density ′ of ι is proportional to e−λ t tk with λ′ = 1 + 1/ℓ ≤ 3/2, and ι is independent of the word. So E[log+ (1/ι) | L = k] ≤ λ′ k+1 /(k!(k + 1)2 ) ≤ 3/2, the bound being largest at k = 0, and this term is at most (3/2)µIj◦ ≤ 6γ. With (18), e0 ≤ (12 + 4α)m(6ℓ + 4)γ + 36mγ.

(26)

G.6. One cube The states f (b) have distinct labels. Place them in one cube, each at its label, fill the other positions of this cube with other states, which exist as 2m divides |S|, and split the remaining states into cubes in any way. This defines a composable interface I˜ on S that keeps the readers at every state f (b). Let G = {(f (b), b) : Sb ̸= ∅} and e∗ = E[ϖ(ι)1(X,B)∈G / ]. By the last paragraph of Appendix G.4 and (23), (25), (24) and (26), e∗ ≤ m{4ℓ + [1612 + 1604α](6ℓ + 4) + 36 + Ωℓ }γ.

(27)

Fix a setter Tj,a . Given ι = t, keep the histories of the other variables and resample the history of j conditioned on its last value being a. The new history has density at most 2ϖ(t) with respect to the old one, by (15). If both words satisfy the stronger condition of Appendix G.1, then the new end state is Y = W−j Tj,a o = Tj,a X. If moreover (X, B) and (Y, B[j 7→ a]) lie in G, then Tj,a X = f (B[j 7→ a]) = T̃j,a X. By (21) and (17), E[ϖ(ι)pj (ι)] ≤ 2Ωℓ γ. So each setter disagrees with probability at most e∗ + 2e∗ + 2Ωℓ γ + 4Ωℓ γ, and each reader with probability at most e∗ . With (27), 6ℓ + 4 ≤ 8ℓ, 108 ≤ 54ℓ, q ≥ 2/3 and 3m + 6 ≤ 6m, Dµ ≤ m{12ℓ + [4836 + 4812α](6ℓ + 4) + 108}γ + (3m + 6)Ωℓ γ ≤ m2 [38760α + 38496α2 + 9 log(1 + ℓ)]γ. 40

(28)

H OW FAR M UST A T EST E XPLORE ?

G.7. Short means ◦ be the density on Let 0 < ℓ < 4, and keep the other notation. For an integer 0 ≤ w ≤ m, let ψw −t/ℓ −t/m w −t/m m−w (0, ∞) proportional to e (1 − e ) (1 + e ) , the density of ι given |B ⊕ bR0 | = w, t ◦ (Saumard, 2019), by ϑ (t)ψ ◦ (t) = with mean t̄w . Define ϑw , the Stein kernel of ψw w w 0 (t̄w − ◦ (z) dz. z)ψw

Lemma 37 (Short means) For 0 < ℓ < 4, ϑw (t) ≤ ξℓ t for all t > 0, with ξℓ = ℓ/(1 − ℓ/4). Proof Fix w and drop it from the notation, and write ξ = ξℓ . The mean. Write ψ ◦ (t) as a positive constant times tw e−t/ℓ g(t) with g(t) = ((1 − e−t/m )/t)w (1 + e−t/m )m−w . Both factors of g do not increase: the derivative of (1−e−t/m )/t has the numerator (1+t/m)e−t/m −1 ≤ 0. Let τ, τ ′ be independent Gamma variables with shape w+1 and scale ℓ, of mean (w+1)ℓ. Then 2 Cov(τ, g(τ )) = E[(τ − τ ′ )(g(τ ) − g(τ ′ ))] ≤ 0, and g is bounded R t and positive, so t̄ = E[τ g(τ )]/Eg(τ ) ≤ (w + 1)ℓ. A sign change. Let Ψ◦ (t) = ξt ψ ◦ (t) − 0 (t̄ − z)ψ ◦ (z) dz and β0 (t) = ξ + t − t̄ + ξtS(t), with S the logarithmic derivative of ψ ◦ . Then (Ψ◦ )′ = β0 ψ ◦ . Let φ0 (y) = y/(ey − 1) and φ1 (y) = y/(ey + 1), so that tS(t) = −t/ℓ + wφ0 (t/m) − (m − w)φ1 (t/m). The function φ0 does not increase, as the numerator ey (1 − y) − 1 of its derivative vanishes at 0 and has derivative −yey ≤ 0. Also −φ′1 (y) ≤ 1/4 for y > 0: this is equivalent to 4y ≤ ey + 6 + 5e−y , and ey + 6 − 4y ≥ 7 − 3y + y 2 /2 = (y − 3)2 /2 + 5/2 > 0. Hence β0′ (t) = 1 −

 ξ ξ ξ ξ + w φ′0 (t/m) − (m − w)φ′1 (t/m) ≤ 1 − + = 0. ℓ m ℓ 4

As tS(t) → w for t ↓ 0, β0 (0+) = ξ(w + 1) − t̄ ≥ 0, by the bound on the mean and ξ > ℓ. As S(t) → −1/ℓ and t(S(t) + 1/ℓ) → 0 for t → ∞, β0 (t) = ξ − t̄ + (1 − ξ/ℓ)t + o(1) → −∞. So β0 is first nonnegative and then nonpositive. R∞ Conclusion. As tψ ◦ (t) → 0 at 0 and at ∞, and 0 (t̄−z)ψ ◦ (z) dz = 0, Ψ◦ (0+) = Ψ◦ (∞) = 0. As Ψ◦ first increases and then decreases, Ψ◦ ≥ 0, which is ϑ(t) ≤ ξt. Lemma 38 (Bound for short means) For 0 < ℓ ≤ 2 and m ≥ 2, if all law instances hold at o, then Dµ ≤ 296m2 γ. ◦ , ϑ = ϑ and ξ = ξ , with ξ ≤ 4 as ℓ ≤ 2. For every bounded smooth function Proof Write ψ = ψw w ℓ φ on (0, ∞), Z Varψ φ = (φ(y ′ ) − φ(y))2 ψ(y)ψ(y ′ ) dy dy ′ y<y ′

Z ≤

Z y′

′

(y − y) y<y ′

′

′

2

′

Z ∞

φ (t) dt ψ(y)ψ(y ) dy dy =

(29) ′

2

φ (t) ϑ(t)ψ(t) dt, 0

y

by the Cauchy–Schwarz inequality and an exchange of integrals, with t̄ the mean of ψ and Z tZ ∞ Z t ′ ′ ′ (y − y)ψ(y)ψ(y ) dy dy = (t̄ − y)ψ(y) dy. 0

t

0

This is the weighted R ∞ Poincaré inequality (Klaassen, 1985; Saumard, 2019). By Lemma 37, the right side is at most ξ 0 tφ′ (t)2 ψ(t) dt. 41

G UO R EN YANG S UN YANG

Fix b and t, and put y = t/m. Let Li be the number of edits of variable i. If bi ̸= b0i , then Li is Poisson with mean y, conditioned to be positive, and its variance is y/(1 − e−y ) − y 2 e−y /(1 − e−y )2 ≤ y. If bi = b0i , its variance is y/(1 + e−y )P + y 2 e−y /(1 + e−y )2 ≤ y + y 2 e−y ≤ 2y. These numbers are conditionally independent, so Lt = i Li has Var(Lt | b, t) ≤ 2t. Given ι = t, Lt is Poisson with mean t, and given theP numbers of edits and B, the end state does not depend on t. So Pr(X = x, B = b | ι = t) = e−t n≥0 χb,x,n tn /n! with numbers χb,x,n that do not depend on t, namely the probabilities of X = x and B = b given n edits. As t (tn /n!)′ = n tn /n!, the quotient ′ (t) = t−1 Cov(1 rule for gb,x gives gb,x X=x , Lt | b, t). By the Cauchy–Schwarz inequality, 2 Var(Lt | b, t) X gb,x (t)(1 − gb,x (t)) ≤ vb (t). 2 x x t t P 2 Let pP b,x = Pr(X = x | B = b). By the law of total variance, 1 − x pb,x = E[vb (ι) P | B = b] + x Var(gb,x (ι) | B = b) ≤ (1 + 2ξ)E[vb (ι) | B = b]. Averaging over b, V ≤ 2 j p̄j and Ep̄j (ι) ≤ 2ℓγ give   X X Pr(B = b) 1 − p2b,x ≤ 4mℓ(1 + 2ξ)γ. X

′ gb,x (t)2 ≤

b

x

For each label b with nonempty Sb , choose f (b) ∈ Sb with the largest pb,x , and let π0 be the joint distribution of (X, B) and G = {(f (b), b) : Sb ̸= ∅}. inequality at the end of Appendix G.4, P P The 2 with pb,x in place of ḡb,x , gives 1 − pb,f (b) ≤ 1 − x pb,x + x∈S / b pb,x , also when Sb is empty, with the convention pb,f (b) = 0. Average this over b. The bound above takes care of the first two terms, and the last term averages to Pr(r(X) ̸= B) ≤ mℓγ. So π0 (G c ) ≤ mℓ(5 + 8ξ)γ. Place the states f (b) in one cube as in Appendix G.6. Let P Ti,a (x, b) = (Ti,a x, b[i 7→ a]). The geometric history gives π0 = (1 − q)δ(o,b0 ) + (q/(2m)) i,a π0 Ti,a , so π0 Ti,a ≤ (2m/q)π0 . If (X, B) ∈ G and Ti,a (X, B) ∈ G, then Ti,a X = T̃i,a X. So each setter disagrees with probability at most (1 + 2m/q)π0 (G c ). With ℓ/q = 1 + ℓ, Dµ ≤ m[2m + (2m + 1)ℓ](5 + 8ξ)γ. As ℓ ≤ 2 and ξ ≤ 4, this is at most 8m2 · 37γ = 296m2 γ. G.8. Proof of Theorem 1(a) The proof treats four cases: means ℓ ≥ 2m by (8), means ℓ < 2m with a law instance failing at o by Lemma 6(iii), and, with all law instances holding at o, means ℓ ≤ 2 by Lemma 38 and means 2 ≤ ℓ ≤ 2m by (28). Let K = m2 [231504 + 9 log(1 + 2m)]. Proof of Theorem 1(a) As m ≥ 2, the intervals (0, 2], [2, 2m] and [2m, ∞) cover every mean ℓ > 0. We show Dℓ ≤ Kγℓ in four cases. With Dℓ ≤ 1, this gives Dℓ ≤ min{1, Kγℓ }. Means ℓ ≥ 2m. By Lemma 6(i), µℓ is (1 + 1/ℓ)-subinvariant, hence (1 + 1/(2m))-subinvariant, whether or not the laws hold at o. So (8) with α = 2 gives λ̄ ≤ (2em)1/2 and Dℓ ≤ 8mλ̄2 γℓ ≤ 16em2 γℓ . As 16e < 48, this coefficient is at most K. Means ℓ < 2m with a law instance failing at o. Then o ∈ N , and Lemma 6(iii) gives γℓ ≥ µℓ ({o}) ≥ 1/(1 + ℓ). So Dℓ ≤ 1 ≤ (1 + ℓ)γℓ ≤ (1 + 2m)γℓ , and 1 + 2m ≤ 2m2 ≤ K as m ≥ 2. Means ℓ ≤ 2 with all law instances holding at o. Lemma 38 gives Dℓ ≤ 296m2 γℓ , and 296m2 ≤ K. Means 2 ≤ ℓ ≤ 2m with all law instances holding at o. These are the assumptions of Appendices G.1–G.6, with α = ℓ/m ≤ 2 and log(1 + ℓ) ≤ log(1 + 2m). So (28) gives Dℓ ≤ m2 [2 · 38760 + 4 · 38496 + 9 log(1 + 2m)]γℓ = Kγℓ . 42

H OW FAR M UST A T EST E XPLORE ?

For D∞ on every finite S, apply this to the interface of Lemma 20, which keeps the start state, the law instances at it and γℓ . The tester follows from Appendix A.

G.9. Proof of Theorem 1(b) Proof of Theorem 1(b) A core. Let S ◦ consist of eight distinct states x, w, y, v ′ , v, x̄, ȳ, w̄. For m = 2, the table in Figure 3 gives the readers and setters at x, w, y, v ′ and v. The states x̄, ȳ, w̄ read (0, 0), and every setter fixes them. Let ν ◦ = (δx + δw )/2, and call x and w its atoms. ˜ on Four entries that no composable interface keeps. We claim that no composable interface I, ◦ ◦ ′ S or on a finite set containing S , has T̃1,1 x = y, T̃2,1 x = v , T̃2,0 w = y and T̃1,0 w = v. In a composable interface, every setter keeps the cube of its argument. So the first and third entries put x, y and w in one cube, and the other two entries put v ′ and v in it as well. By the first and third entries, the label of y in I˜ starts with (1, 0). As x ̸= y, the first entry changes x, so the label of x starts with (0, 0). As w ̸= y, the label of w starts with (1, 1) in the same way. So v ′ = T̃2,1 x and v = T̃1,0 w both have labels that start with (0, 1). The four setters keep all other coordinates, so the labels of v ′ and v agree, and v ′ = v, a contradiction. Hence every composable interface, on S ◦ or on a larger set, disagrees with I at x or at w, and Dν∞◦ ≥ 1/2. The laws hold at x and w. Success, write-back and preservation at x and w follow from the table. Overwrite involves two writes to one variable. At x, these stay in {x, y} for variable 1 and in {x, v ′ } for variable 2, and at w, in {v, w} and in {y, w}. On each of these pairs, the two setters of the variable act as an exact binary write, so overwrite holds. For commutation, both orders of T1,a and T2,b give the same state: x b=0 b=1 a=0 x v′ a=1 y w

w b=0 b=1 a=0 x v . a=1 y w

So all 4m2 + 3m = 22 law instances hold at x and w, and γν ◦ = 0. A composable interface at distance 1/2. Give x, y, v ′ , w the labels 00, 10, 01, 11 in one cube, and x̄, ȳ, v, w̄ the same labels in a second cube. This composable interface keeps the readers at x and w. At x and w, its setters differ from those of I only in T1,0 w = v ′ ̸= v. So Dν ◦ = 1/2. ◦ = S ◦ × {0, 1}m−2 . The first two variables act on the first More variables. For m ≥ 2, let Sm component as above, the other variables are coordinate readers and setters of the second component, and labels concatenate. Let ν ◦ = (δ(x,0m−2 ) + δ(w,0m−2 ) )/2. The laws that involve only the first two variables hold as for m = 2, and those that involve only the others hold for coordinate readers and setters. Setters of the first two variables and of the others act on different components, so they commute and keep each other’s readings. Hence γν ◦ = 0. The four entries at the atoms keep the second component, so the argument above gives Dν∞◦ ≥ 1/2. The product of the composable interface above with the interface that reads and replaces the coordinates of {0, 1}m−2 changes only ◦ has 2m+1 states. T1,0 at (w, 0m−2 ) on the support of ν ◦ , so Dν ◦ = 1/2. The core Sm m−2 One start state. Let k ≥ 1, let o0 = (x, 0 ) and o1 = (w, 0m−2 ) be the atoms of ν ◦ , and add k extra states o′0 , . . . , o′k−1 with arbitrary readings. Every setter maps o′j to o′j+1 for j < k − 1, and Ti,a maps o′k−1 to oa . With ν the point mass at o′0 , the last of k random edits reaches oa when it writes a, so νP k = ν ◦ . Add (−k) mod 2m further states, with arbitrary readings and fixed by ◦ is closed under the setters, the law instances at the atoms every setter, so that 2m divides |S|. As Sm 43

G UO R EN YANG S UN YANG

◦ , and γ involve only states of Sm νP k = γν ◦ = 0. The lower bound concerns only the entries at the atoms, so it holds as before. The added states form full cubes, so the composable interface above ∞ =D extends to S with disagreement 1/2. Thus DνP k νP k = 1/2.

Appendix H. Fixed thresholds: reduction to one quantity For an integer d ≥ 1, a state x is locally exact to depth d if every word of length at most d that starts at x ends at a state whose label is the one predicted by coordinate writes from r(x), and two such words end at the same state exactly when their predicted labels agree. Let Ad be the set of these states, and let ad = sup{Dν∞ (I) : I a finite interface of any number of variables, ν(Ad ) = 1}. So ad ∈ [0, 1] does not increase with d. The local exactness check of depth d reads the end label of every word of length at most d from a sample, checks it against the predicted label, and checks for every two of these words that their ends are equal exactly when their predicted labels agree. It rejects with probability µ(S \ Ad ). Theorem 39 (Reduction) For every interface and µ, Dµ∞ ≤ µ(S \ Ad ) + µ(Ad )ad . The following are equivalent: (1) ad → 0; (2) for every fixed ℓ > 0, every sequence of interfaces and start distributions with m → ∞ and γℓ = m−ω(1) has Dℓ∞ → 0; (3) the same for one fixed ℓ > 0; (4) for all fixed ℓ > 0 and 0 < η, δ < 1, law checks at samples of µℓ certify Dµ∞ℓ < η from a number of samples polynomial in m, with degree and coefficient depending on ℓ, η, δ only. Lemma 40 (Passive embedding) Let I be an interface with n1 variables on S, and let ν(Ad ) = 1 with d ≥ 2. For all m ≥ n1 and ℓ > 0 there is an interface I¯ with m variables and a start ¯ ≤ (ℓn1 /(m + ℓn1 ))d−1 . ¯ ≥ Dν∞ (I)/(1 + ℓ) and γℓ (I) distribution with Dℓ∞ (I) Proof Let S̄ = S ×{0, 1}m−n1 , r̄(s, v) = (r(s), v) and ν̄ = ν ⊗δ0m−n1 . The first n1 setters act on s, the others replace coordinates of v. Then µ̄ℓ ≥ ν̄/(1 + ℓ). A composable interface with m variables, with the last m − n1 readers and setters forgotten, is a composable interface with n1 variables: each m-dimensional cube splits into 2m−n1 cubes by the last coordinates. Its set of states contains the slice S × {0m−n1 }, so it is a candidate for Dν∞ (I). This gives the distance bound. The number La of edits of the first n1 variables is geometric with mean ℓn1 /m, as in Lemma 24. If La ≤ d − 2, both sides of each law instance on these variables are words of length at most La + 2 ≤ d from the start state, which lies in Ad , so the law holds at the end of the run. Passive coordinates are exact and commute with all writes. So γℓ ≤ Pr(La ≥ d − 1). Proof of Theorem 39 The inequality. If µ(Ad ) = 0, the right side is 1 and each disagreement probability is at most 1. Otherwise, let ν be µ conditioned on Ad . For every composable interface and every disagreement set X, µ(X) ≤ µ(S \ Ad ) + µ(Ad )ν(X). Taking the largest X and the infimum over candidates gives the inequality. As Ad+1 ⊆ Ad , ad does not increase. From laws to local exactness. If no state within d−1 writes of x lies in N , then x ∈ Ad . Indeed, along a word of length at most d, success and preservation give the predicted labels. Commutation sorts the writes by variable, overwrite deletes all but the last write of each variable, and write-back at 44

H OW FAR M UST A T EST E XPLORE ?

x deletes a write of the current value of x. Each commutation or overwrite applies to a state reached by at most d − 2 writes, and write-back applies at x after commutation moves the write to the front. So two words with the same predicted label reduce to the same word, and words P with different predicted labels end at different labels. If µ is λ-subinvariant, µ(S \ Ad ) ≤ γµ k<d (2mλ)k , as the push-forwards of µ under all (2m)k words of length k sum to (2m)k µP k ≤ (2mλ)k µ. (1) implies (2). Fix d and ℓ. As µℓ is (1+1/ℓ)-subinvariant, γℓ = m−ω(1) gives µℓ (S \Ad ) → 0, so lim sup Dℓ∞ ≤ ad . Let d → ∞. Choosing a fixed ℓ > 0 in (2) gives (3). (3) implies (1). Suppose a∞ = limd ad > 0 and put η = a∞ /2. For each j ≥ 2, choose an interface Ij with nj variables and νj with νj (Aj ) = 1 and Dν∞j (Ij ) ≥ η. Fix ℓ > 0 and choose increasing integers mj ≥ max{j, n2j , (ℓnj )2 , 4}. For m ≥ m2 , let j(m) = max{j : mj ≤ m}, which tends to infinity, and embed Ij(m) by Lemma 40. Then Dℓ∞ ≥ η/(1 + ℓ) and γℓ ≤ (ℓnj(m) /m)j(m)−1 ≤ m−(j(m)−1)/2 = m−ω(1) , against (3). (1) implies (4). Fix ℓ, η, δ, choose d with ad ≤ η/2 and put λ = 1 + 1/ℓ. If Dµ∞ℓ ≥ η, the inP P equality gives µℓ (S \ Ad ) ≥ η/2, so γℓ ≥ η/(2 k<d (2mλ)k ). So ⌈(2/η) k<d (2mλ)k log(1/δ)⌉ samples suffice. (4) implies (2). If (2) fails, there are a fixed ℓ > 0, a fixed η > 0 and a sequence with Dℓ∞ ≥ η and γℓ = m−ω(1) . A law-check tester with polynomially many samples rejects these with probability o(1).

Appendix I. Reads, measures and small supports This appendix proves Propositions 41–45. I.1. Reads along random writes Let ℓ > 0 and let k ≥ 1 be an integer. Draw X0 ∼ µℓ and independent uniformly random setters (i1 , a1 ), . . . , (ik , ak ), independent of X0 . Put Xs = Tis ,as Xs−1 , B0 = r(X0 ) and Bs = Bs−1 [is 7→ as ], the label that a record predicts. Proposition 41 (Reads) For every interface and start distribution, the probability that r(Xs ) ̸= Bs for some s ≤ k is at most ℓ(q −k − 1)γℓ , which is at most ekγℓ for k ≤ ℓ. Proof Take the first s with r(Xs ) ̸= Bs . As r(Xs−1 ) = Bs−1 , the setter does not update the label as written at Xs−1 , so success or preservation fails there, and Xs−1P∈ N . Here Xs−1 has distribution µℓ P s−1 ≤ q −(s−1) µℓ by Lemma 6(ii). Summing over s with s<k q −s = ℓ(q −k − 1) gives the bound. The last estimate of Corollary 10 gives ℓ(q −k − 1) ≤ ek for k ≤ ℓ. Each step checks a whole label at once, so no union over the m variables appears. I.2. Correct reads at constant distance For m ≥ 2, let S = {0, 1}m × {0, 1} and r(u, z) = u, and let T1,v (u, z) = (u[1 7→ v], z ⊕ (v ⊕ u1 )u2 ),

Ti,v (u, z) = (u[i 7→ v], z)

For m = 2 this is the interface of Figure 2. 45

(i ̸= 1).

(30)

G UO R EN YANG S UN YANG

Proposition 42 (Eight states) Let µ be the uniform measure on S. Success, preservation, writeback and overwrite hold at every state, so after any sequence of writes the label is the one that coordinate writes predict. Commutation fails at every state. Also µP = µ and Dµ∞ ≥ 1/8. Proof Every setter updates the label as written, which gives success and preservation. For v = u1 the change of z in (30) vanishes, which gives write-back. Writing w and then v to variable 1 changes z by (w ⊕ u1 )u2 ⊕ (v ⊕ w)u2 = (v ⊕ u1 )u2 , the change of writing v alone, which gives overwrite for this variable; for the other variables it is direct. At (u, z), the two orders of T1,1−u1 and T2,1−u2 give the same label, and their values of z differ by (1 ⊕ u1 ⊕ u1 )(u2 ⊕ 1 ⊕ u2 ) = 1. Each flip is an involution, as F1 (u, z) = (u ⊕ e1 , z ⊕ u2 ) and the other flips change one coordinate of u. So each flip preserves µ. By write-back, the two setters of variable i average to (Id + Fi )/2, so µP = µ. From x = (u, z), apply F1 , F2 , F1 , F2 . Each of the two coordinates is first written with the opposite value and then with its initial value. The label returns to u, and z changes by u2 ⊕(1−u2 ) = 1. Let I˜ be a composable interface on a finite set S ′ ⊇ S. By Lemma 25, it disagrees with one of the four calls. Draw x ∼ µ. As the flips are involutions, the argument of each call is uniform. A call of variable i uses one of its two setters, so it disagrees with probability at most the sum of their ˜ So 1 ≤ 8Rµ (I, I). ˜ disagreements, at most 2Rµ (I, I).

I.3. An audit at mean zero certifies the start distribution Let m = 1, S = {x, y}, ν = δx , r(x) = 0 and r(y) = 1, and let T0 x = x, T1 x = y, T0 y = x and T1 y = x. Proposition 43 (Two states) Every audit round with target label â = 0 and depth m + 1 = 2 passes, with or without its bridge check, and Dν = Dν∞ = 0. After one random write, DνP = ∞ = 1/2. DνP Proof The round. The path check has T0 x = x, with the correct label, and the comparison with x passes. Write-back at x is T0 x = x. The flip is y1 = T1 x = y, of label 1. Its path has T0 y = x, of label 0, which equals x1 = x, and the undo T1 x = y returns to y. For the bridge check, u(1) = a = 0, and w0 is x if u = 0 and y if u = 1, with the correct label. In both cases T0 w0 = x = w1 . The distances. The record with labels r(x) = 0 and r(y) = 1, whose setters T0 and T1 always output x and y, agrees with the interface at x, so both distances under ν are 0. Now νP = (δx + δy )/2. This record differs only in T1 y, which gives the upper bound 1/2. A candidate with disagreement below 1/2 would keep all readers and setters at both atoms. As T1 y = x and r(x) = 0, it would violate success, on the same states or with added states.

I.4. Lengthening the runs Proposition 44 (Longer runs) Let m ≥ 2, ℓ ≥ 0 and L ≥ ℓ with L > 0. Then µℓ ≤ 1+L 1+ℓ µL , 1+L ∞ 1+L ∞ m so Dµℓ ≤ 1+ℓ DµL , and also Dµℓ ≤ 1+ℓ DµL when 2 | |S|. Let L = max{ℓ, m}. Then 1+L 2 3 1+L 1+ℓ ≤ 1+m, and law checks at depth 2 at ⌈16e m 1+ℓ log(1/δ)/ϵ⌉ samples of µL certify Dµℓ < ϵ m ∞ when 2 | |S|, and Dµℓ < ϵ for every finite S. 46

H OW FAR M UST A T EST E XPLORE ?

Proof Put qℓ = ℓ/(1 + ℓ). As qℓ ≤ qL , comparing (1) term by term gives (1 − qℓ )qℓs ≤ ((1 − qℓ )/(1 − qL ))(1 − qL )qLs , and (1 − qℓ )/(1 − qL ) = (1 + L)/(1 + ℓ). The bound on the distances follows for each candidate and each disagreement set. For the tester, Corollary 21 with α = 1 gives DµL ≤ 16e2 m3 γµL when 2m | |S|, and Dµ∞L ≤ 16e2 m3 γµL for every finite S. So a distance of at least ϵ under µℓ gives γµL ≥ ϵ(1 + ℓ)/(16e2 m3 (1 + L)), and law checks reject as in Appendix A. If ℓ ≥ m then L = ℓ, and otherwise L = m, which gives the bound on the ratio.

I.5. Small supports with added states Proposition 45 (Small support) Let m, N ≥ 1, 0 < ϵ, δ < 1, and let µ have support of size at most N . A tester of depth at most one with one-sided error, ⌈(N/ϵ) log(N/δ)⌉ samples and at most 2mN setter calls certifies Dµ∞ < ϵ with confidence 1 − δ. It needs only the bound N . Proof The tester. Draw the samples and remove repetitions by comparison, which leaves a set BN . For each x ∈ BN , call all Ti,a x and read the labels of their outputs. Reject if Ti,ri (x) x ̸= x or r(Ti,a x) ̸= r(x)[i 7→ a] for some i, a. Among all held states, join x and Ti,a x by an edge, and reject if a connected component has two distinct states of one label. The calls act only on samples, so the depth is at most one, and there are at most 2mN of them. A composable interface passes, as each setter keeps the cube and a cube has one state of each label. A pass gives a composable interface. Suppose the tester passes. Each component has distinct labels. Give each component its own cube, with its states at their labels, and fill the other positions with added states. Give each state of S that is not held a cube of its own in the same way. This is a composable interface on a finite set containing S. It keeps the readers on S, and for x ∈ BN all setters at x, as Ti,a x lies in the cube of x with the updated label. So Dµ∞ ≤ µ(S \ BN ). Heavy atoms are sampled. Let AN be the support of µ and HN = {x ∈ AN : µ(x) ≥ ϵ/N }. With s = ⌈(N/ϵ) log(N/δ)⌉ samples, a state of HN is missed with probability at most (1−ϵ/N )s ≤ δ/N , so HN ⊆ BN except with probability at most δ. On this event, µ(S \BN ) ≤ µ(AN \HN ) < ϵ. So an interface with Dµ∞ ≥ ϵ passes with probability at most δ.

47

Related documents

• Chronicle: Cut-Point Replay for Regression Testing of LLM Agents#1034432
• Chronicle: Cut-Point Replay for Regression Testing of LLM Agents#978466
• Randomness Is Unpredictability#725122
• The Scheduler Is a Hidden Retriever: How Asynchrony Shapes Evidence Acquisition in Search Agents#1401484
• Auditing the Privacy of Synthetic Gene Expression Data: A Unified Weighted-Distance Framework for No-Box Membership Inference#1199334