Research / 2026

Fast test answers that stay sound

Draft · the definitions and theorems on this page are machine-checked in Lean; independent review is in progress.

After a change, re-run only the test cases that could have seen it, cheapest tier first. Recording each case's read set while it runs, selecting cases by intersection with the changed locations, and ordering tiers by cost combine into one procedure. A Lean proof shows that it reports exactly the verdicts of a full re-run, after any number of changes, while executing no more cases than the change reaches.

Regression test selectionDynamic read setsRefinement
= full run
the cache after selective re-runs equals a full re-run of the suite, after any number of changes
≤ hits
cases executed per change: at most the cases whose recorded read set meets the changed locations
1 read
a case with a single read, under a change to that one location, shows that a rule deciding only from footprint and changed set cannot skip a hit case in general

After a change to code or configuration, a developer wants to know within seconds whether anything broke. Running the whole suite (cheap model-level cases, then integration runs, then runs on a real device) takes minutes or hours. Running a subset picked by guesswork is fast, but it can skip a case that now fails, and a missed failure is worse than a slow answer.

None of the parts used here is new. Recording what a computation reads, re-running only what a change can reach, and ordering checks from cheap to faithful are all known techniques, and each is credited below. The point of this article is the combination: I state the goal precisely, put the three parts together into one procedure, and prove that the procedure achieves the goal. Sometimes that is the useful piece of work.

All Lean below is core Lean 4 (checked with 4.16.0). The code blocks, joined in order, form one file that compiles with no errors, no warnings and no sorry, admit or added axiom. #print axioms on the theorems shows only the standard axioms that simp and omega use (propext, Quot.sound, Classical.choice).

The goal

A suite is a list of test cases. Each case produces a verdict, pass or fail, from the current state of everything it can see. A change moves that state from ss to tt. The procedure keeps a cache of past results and, after each change, updates it. I want four things from it.

Goal.

  1. Exactness. After a change, the cached verdicts equal the verdicts a full re-run of every case would give on the new state tt.
  2. Durability. Exactness holds after any number of changes in a row, with no periodic full re-run to restore it.
  3. Cost. The number of cases executed for one change is at most the number of cases whose recorded inputs the change touches. A smaller change never executes more cases, and an empty change executes none.
  4. Tiers. A pass from a cheap tier has a stated meaning, and the release gate is sound for the facts it checks. Every such claim names the hypothesis it rests on.

“In seconds” is not a theorem. Wall-clock time depends on how long each selected case takes, which no model of this size can know. What the theorems fix is how many cases run and which tier can answer first. If the cheapest tier’s cases are fast, the first answer is fast. That last step is an engineering property, and the limits section returns to it.

The components

Dynamic read sets. While a computation runs, record every location it reads. If a later state agrees with the earlier one on those locations, the computation would read the same things and return the same result, so it need not run again. This is the verifying-trace idea from “Build systems à la carte” (ICFP 2018), where build tasks with dynamic inputs are modelled as computations that request their inputs one at a time. “Shake before building: replacing make with Haskell” (ICFP 2012) records the inputs a build rule actually requests. Self-adjusting computation, from “Adaptive functional programming” (POPL 2002) and “Adapton: composable, demand-driven incremental computation” (PLDI 2014), records the same kind of information at a finer grain to re-execute only what a change reaches.

Safe regression test selection. After a change, re-run only the cases whose earlier execution touched a changed part, and argue that no other case can change its verdict. “Safe” means that no case whose verdict could change is left out. The formulation follows “A safe, efficient regression test selection technique” (ACM Transactions on Software Engineering and Methodology, 1997), which selects by the parts of a program that each case exercised.

Tiers related by refinement. Checks are ordered from cheap and abstract (a model of the system) to expensive and faithful (the system on a device). The link between a tier and the next is a refinement claim: what the abstract level establishes also holds at the concrete level. The idea goes back to “Proof of correctness of data representations” (Acta Informatica, 1972) and “Program development by stepwise refinement” (Communications of the ACM, 1971).

The combination

Procedure. Tiers are numbered 0,1,…,top0, 1, \dots, \mathrm{top}, cheapest first. Tier top\mathrm{top} is the device.

  1. Each tier has its own suite and its own cache. A cache entry holds, for one case, its last verdict and the read set recorded on the state the cache was built from.
  2. A change is given as a new state tt together with a changed set CC, a list of locations outside which tt agrees with the old state.
  3. In each tier, re-run exactly the cases whose cached read set meets CC, recording a fresh read set for each. Keep every other entry as it is.
  4. Report tier 0 first, then tier 1, and so on. The fast path reads the answer of one tier (usually tier 0). The release gate waits for every tier and requires every covered fact to pass.

The modelling choice that makes this checkable is that everything a case may depend on is a location in one store, and a case sees the store only by reading a location. Code lives in the store too: a source file’s content is the value at that file’s location, so editing code is writing to the store. Configuration, clocks, seeds and device state are locations in the same way. In a real system this is an obligation on the instrumentation, stated below as assumption A1.

Stores and computations

Store, computation, run. Locations and values are natural numbers, and a store is a function s:N→Ns : \mathbb{N} \to \mathbb{N}. A computation with results in AA is a tree built from two constructors: ret(a)\mathrm{ret}(a) ends with result aa, and read(l,k)\mathrm{read}(l, k) reads location ll and continues with kk applied to the value read. Running cc on ss gives a pair

run(c,s)=(v,F),\mathrm{run}(c, s) = (v, F),

where vv is the result and FF, the read set or footprint, lists the locations read, in the order the reads happen. Write fp(c,s)\mathrm{fp}(c, s) for FF. A test case is a computation whose result is a Boolean verdict.

Agreement. Two stores agree on a list LL, written s=Lts =_L t, if s(l)=t(l)s(l) = t(l) for every l∈Ll \in L.

Which location a computation reads next can depend on values it has already read, because the continuation kk receives the value. The read set is therefore a property of one run on one store, not of the program text, and this is why it has to be recorded while the case runs.

namespace SoundFastTesting

/-! ## 1. Stores and computations that record what they read -/

abbrev Loc := Nat
abbrev Val := Nat
abbrev Store := Loc → Val

/-- A computation is a tree of reads ending in a result. -/
inductive Comp (α : Type) where
  | ret  : α → Comp α
  | read : Loc → (Val → Comp α) → Comp α

/-- Run on a store; return the result and the read set, in read order. -/
def run {α : Type} : Comp α → Store → α × List Loc
  | .ret a, _    => (a, [])
  | .read l k, s => ((run (k (s l)) s).1, l :: (run (k (s l)) s).2)

/-- Two stores agree on a list of locations. -/
def Agree (s t : Store) (ls : List Loc) : Prop := ∀ l, l ∈ ls → s l = t l

Read-set soundness

Theorem 1 (read-set soundness). For every computation cc and stores s,ts, t: if s=fp(c,s)ts =_{\mathrm{fp}(c, s)} t, then run(c,t)=run(c,s)\mathrm{run}(c, t) = \mathrm{run}(c, s).

Proof. Induction on cc. For ret(a)\mathrm{ret}(a) both runs give (a,[ ])(a, [\,]). For read(l,k)\mathrm{read}(l, k), the read set on ss is ll followed by F′=fp(k(s(l)),s)F' = \mathrm{fp}(k(s(l)), s). Agreement on ll gives s(l)=t(l)s(l) = t(l), so the run on tt continues with the same computation k(s(l))k(s(l)). Agreement on F′F' and the induction hypothesis give run(k(s(l)),t)=run(k(s(l)),s)\mathrm{run}(k(s(l)), t) = \mathrm{run}(k(s(l)), s). Putting ll back in front of both read sets gives the claim. ∎

The equality is between pairs, so the run on tt has the same result and also the same read set. That second half matters below: a case that is not re-run keeps a footprint that is still correct for the new store.

/-- Theorem 1 (read-set soundness). -/
theorem read_set_sound {α : Type} (c : Comp α) :
    ∀ (s t : Store), Agree s t (run c s).2 → run c t = run c s := by
  induction c with
  | ret a => intro s t _; rfl
  | read l k ih =>
    intro s t h
    have hl : s l = t l := h l (List.Mem.head _)
    have rest : Agree s t (run (k (s l)) s).2 :=
      fun x hx => h x (List.Mem.tail _ hx)
    simp only [run]
    rw [← hl, ih (s l) s t rest]

Selecting by intersection

Changed set, hit. For stores s,ts, t and a list CC, write s≈Cts \approx_C t when s(l)=t(l)s(l) = t(l) for every l∉Cl \notin C: the store tt differs from ss at most at locations in CC. A footprint FF hits CC when some location occurs in both.

Theorem 2 (selection soundness). If s≈Cts \approx_C t and fp(c,s)\mathrm{fp}(c, s) does not hit CC, then run(c,t)=run(c,s)\mathrm{run}(c, t) = \mathrm{run}(c, s). In particular, a test case whose footprint misses the changed set keeps its verdict.

Proof. Every ll in fp(c,s)\mathrm{fp}(c, s) is outside CC, so s(l)=t(l)s(l) = t(l). That is s=fp(c,s)ts =_{\mathrm{fp}(c,s)} t, and Theorem 1 applies. ∎

The Lean below defines membership and the hit test as Boolean functions, so that selection is something a program computes, and proves that a negative hit test means every footprint location lies outside the changed set.

/-! ## 2. Changed sets and selection -/

def memb (x : Loc) : List Loc → Bool
  | []      => false
  | y :: ys => x == y || memb x ys

/-- Does a footprint intersect a changed set? -/
def hits : List Loc → List Loc → Bool
  | [],      _  => false
  | l :: ls, ch => memb l ch || hits ls ch

theorem hits_false {fp ch : List Loc} (h : hits fp ch = false) :
    ∀ l, l ∈ fp → memb l ch = false := by
  induction fp with
  | nil => intro l hl; cases hl
  | cons x xs ih =>
    intro l hl
    simp only [hits, Bool.or_eq_false_iff] at h
    cases hl with
    | head => exact h.1
    | tail _ hm => exact ih h.2 l hm

/-- `t` differs from `s` only at locations listed in `ch`. -/
def OffAgree (s t : Store) (ch : List Loc) : Prop :=
  ∀ l, memb l ch = false → s l = t l

/-- Theorem 2 (selection soundness, one case). -/
theorem selection_sound {α : Type} (c : Comp α) (s t : Store) (ch : List Loc)
    (hst : OffAgree s t ch) (h : hits (run c s).2 ch = false) :
    run c t = run c s :=
  read_set_sound c s t (fun l hl => hst l (hits_false h l hl))

The selection step walks the suite and the cache together. For case cic_i with cached entry ei=(vi,Fi)e_i = (v_i, F_i) it produces

ei′  =  {run(ci,t)if Fi hits C,eiotherwise.e_i' \;=\; \begin{cases} \mathrm{run}(c_i, t) & \text{if } F_i \text{ hits } C, \\ e_i & \text{otherwise.} \end{cases}

Theorem 2′ (selective re-run equals full re-run). If s≈Cts \approx_C t and the cache is the full run of the suite on ss, then refreshing it with CC and tt gives exactly the full run of the suite on tt.

Proof. Induction on the suite, one case at a time. If the cached footprint hits CC, the entry is replaced by run(c,t)\mathrm{run}(c, t) by definition. Otherwise the entry stays run(c,s)\mathrm{run}(c, s), which equals run(c,t)\mathrm{run}(c, t) by Theorem 2. ∎

/-- Re-run exactly the cases whose recorded footprint hits the change. -/
def refresh {α : Type} : List (Comp α) → List (α × List Loc) → List Loc → Store →
    List (α × List Loc)
  | c :: cs, e :: es, ch, t =>
      (if hits e.2 ch then run c t else e) :: refresh cs es ch t
  | _, _, _, _ => []

/-- Theorem 2' (selective re-run equals full re-run). -/
theorem refresh_exact {α : Type} (suite : List (Comp α)) (s t : Store) (ch : List Loc)
    (hst : OffAgree s t ch) :
    refresh suite (suite.map (fun c => run c s)) ch t = suite.map (fun c => run c t) := by
  induction suite with
  | nil => rfl
  | cons c cs ih =>
    simp only [List.map, refresh, ih]
    cases hh : hits (run c s).2 ch with
    | true => rfl
    | false => simp only [selection_sound c s t ch hst hh]; rfl

A history is a list of steps (C1,t1),…,(Cn,tn)(C_1, t_1), \dots, (C_n, t_n). It is valid from ss when t0=st_0 = s and tj−1≈Cjtjt_{j-1} \approx_{C_j} t_j for each jj. Replaying it applies the selection step once per change.

Theorem 2″ (the cache stays exact). If the history is valid from ss and the cache starts as the full run of the suite on ss, then after replaying the history the cache equals the full run of the suite on the final store tnt_n.

Proof. Induction on the history. With no steps there is nothing to show. For a first step (C1,t1)(C_1, t_1), Theorem 2′ turns the cache into the full run on t1t_1, which is the starting condition for the rest of the history from t1t_1, and the induction hypothesis finishes. ∎

The proof works only because each re-run case gets a fresh footprint, recorded on the store it ran on. A cache that kept old footprints for re-run cases could lose the starting condition after one step: if a re-run case now reads a different location, its stale footprint can miss a later change to that location. A case that is not re-run keeps its old footprint, which is still correct by the second half of Theorem 1.

/-- A history of changes, each with the store after it. -/
def Valid : Store → List (List Loc × Store) → Prop
  | _, []             => True
  | s, (ch, t) :: rest => OffAgree s t ch ∧ Valid t rest

def final : Store → List (List Loc × Store) → Store
  | s, []             => s
  | _, (_, t) :: rest => final t rest

def replay {α : Type} (suite : List (Comp α)) :
    List (α × List Loc) → List (List Loc × Store) → List (α × List Loc)
  | cache, []             => cache
  | cache, (ch, t) :: rest => replay suite (refresh suite cache ch t) rest

/-- Theorem 2'' (the cache stays exact across any valid history). -/
theorem replay_exact {α : Type} (suite : List (Comp α)) :
    ∀ (hist : List (List Loc × Store)) (s : Store), Valid s hist →
      replay suite (suite.map (fun c => run c s)) hist
        = suite.map (fun c => run c (final s hist)) := by
  intro hist
  induction hist with
  | nil => intro s _; rfl
  | cons step rest ih =>
    obtain ⟨ch, t⟩ := step
    intro s hv
    simp only [Valid] at hv
    simp only [replay, final]
    rw [refresh_exact suite s t ch hv.1]
    exact ih t hv.2

Hit cases cannot be skipped in general. Take a case that reads location 0 and passes exactly when it sees 0. Let ss be the store that is 0 everywhere and tt the store that is 1 at location 0 and 0 elsewhere, so s≈[0]ts \approx_{[0]} t. The case gives true on ss and false on tt, and its footprint [0][0] hits the change [0][0]. So a rule that decides only from the recorded footprint and the changed set cannot skip a hit case in general: on this input it would report a stale verdict. This does not show that every hit case must be re-run (see the limits section). The block below also states Theorem 2 for Boolean verdicts alone, as kept_verdict, proves s≈[0]ts \approx_{[0]} t as bumped_off, and checks the rest of the example by decide.

/-- Corollary: verdicts of non-hit cases are unchanged. -/
theorem kept_verdict (c : Comp Bool) (s t : Store) (ch : List Loc)
    (hst : OffAgree s t ch) (h : hits (run c s).2 ch = false) :
    (run c t).1 = (run c s).1 := by
  rw [selection_sound c s t ch hst h]

/-- A case that reads location 0 and passes exactly when it sees 0. -/
def probe : Comp Bool := .read 0 (fun v => .ret (v == 0))

/-- The store that is 1 at location 0 and 0 elsewhere. -/
def bumped : Store := fun l => if l == 0 then 1 else 0

/-- `bumped` differs from the all-zero store only inside the change `[0]`. -/
theorem bumped_off : OffAgree (fun _ => 0) bumped [0] := by
  intro l h
  simp [memb] at h
  simp [bumped, h]

/-- Skipping this hit case under the valid change `[0]` would report a stale verdict. -/
example : (run probe (fun _ => 0)).1 = true ∧ (run probe bumped).1 = false ∧
    hits (run probe (fun _ => 0)).2 [0] = true := by decide

The cost of selection

Let runs\mathrm{runs} count the re-runs the selection step performs, and hitCount(C)\mathrm{hitCount}(C) count the cache entries whose footprint hits CC. In Lean, runs\mathrm{runs} is a separate recursive count, and an instrumented copy of the selection step, refreshC, returns the new cache together with the number of times it calls run. Two lemmas prove that its cache is the one refresh returns and that its count is runs\mathrm{runs}, so runs\mathrm{runs} is the number of executions by proof, not by reading the code.

Theorem 3 (cost).

  1. For every suite and cache, runs≤hitCount(C)\mathrm{runs} \le \mathrm{hitCount}(C). When the suite and the cache have the same length, runs=hitCount(C)\mathrm{runs} = \mathrm{hitCount}(C). Every cache the procedure produces has the suite’s length: the selection step returns a list of length min⁡(∣suite∣,∣cache∣)\min(|\text{suite}|, |\text{cache}|), so starting from the full run of the suite, the length is kept through any history.
  2. hitCount(C)\mathrm{hitCount}(C) is at most the size of the cache.
  3. If every location in CC is also in C′C', then hitCount(C)≤hitCount(C′)\mathrm{hitCount}(C) \le \mathrm{hitCount}(C'): a smaller change never executes more cases.
  4. hitCount([ ])=0\mathrm{hitCount}([\,]) = 0: an empty change executes nothing.

Proof. Each is an induction on the cache (and the suite, for part 1), adding one per hitting entry. The length statements are inductions on the suite and on the history. For part 3, a footprint that hits CC also hits C′C', by induction on the footprint. ∎

/-! ## 3. Cost of selection -/

def runs {α : Type} : List (Comp α) → List (α × List Loc) → List Loc → Nat
  | _ :: cs, e :: es, ch => (if hits e.2 ch then 1 else 0) + runs cs es ch
  | _, _, _ => 0

/-- The selection step, instrumented: also count the calls to `run`. -/
def refreshC {α : Type} : List (Comp α) → List (α × List Loc) → List Loc → Store →
    List (α × List Loc) × Nat
  | c :: cs, e :: es, ch, t =>
      if hits e.2 ch then (run c t :: (refreshC cs es ch t).1, (refreshC cs es ch t).2 + 1)
      else (e :: (refreshC cs es ch t).1, (refreshC cs es ch t).2)
  | _, _, _, _ => ([], 0)

theorem refreshC_fst {α : Type} :
    ∀ (suite : List (Comp α)) (cache : List (α × List Loc)) (ch : List Loc) (t : Store),
      (refreshC suite cache ch t).1 = refresh suite cache ch t := by
  intro suite
  induction suite with
  | nil => intro cache ch t; cases cache <;> rfl
  | cons c cs ih =>
    intro cache ch t
    cases cache with
    | nil => rfl
    | cons e es =>
      simp only [refreshC, refresh]
      split <;> simp [ih]

/-- `runs` is exactly the number of executions the selection step performs. -/
theorem refreshC_snd {α : Type} :
    ∀ (suite : List (Comp α)) (cache : List (α × List Loc)) (ch : List Loc) (t : Store),
      (refreshC suite cache ch t).2 = runs suite cache ch := by
  intro suite
  induction suite with
  | nil => intro cache ch t; cases cache <;> rfl
  | cons c cs ih =>
    intro cache ch t
    cases cache with
    | nil => rfl
    | cons e es =>
      simp only [refreshC, runs]
      split <;> simp [ih] <;> omega

theorem refresh_length {α : Type} :
    ∀ (suite : List (Comp α)) (cache : List (α × List Loc)) (ch : List Loc) (t : Store),
      (refresh suite cache ch t).length = min suite.length cache.length := by
  intro suite
  induction suite with
  | nil => intro cache ch t; cases cache <;> rfl
  | cons c cs ih =>
    intro cache ch t
    cases cache with
    | nil => simp [refresh]
    | cons e es =>
      simp only [refresh, List.length_cons, ih]
      omega

/-- Every cache the procedure produces has the suite's length. -/
theorem replay_length {α : Type} (suite : List (Comp α)) :
    ∀ (hist : List (List Loc × Store)) (cache : List (α × List Loc)),
      cache.length = suite.length → (replay suite cache hist).length = suite.length := by
  intro hist
  induction hist with
  | nil => intro cache h; exact h
  | cons step rest ih =>
    obtain ⟨ch, t⟩ := step
    intro cache h
    simp only [replay]
    apply ih
    rw [refresh_length, h]
    omega

def hitCount {α : Type} : List (α × List Loc) → List Loc → Nat
  | [],      _  => 0
  | e :: es, ch => (if hits e.2 ch then 1 else 0) + hitCount es ch

/-- Theorem 3, part 1: runs performed ≤ cached cases whose footprint hits the change. -/
theorem runs_le_hits {α : Type} :
    ∀ (suite : List (Comp α)) (cache : List (α × List Loc)) (ch : List Loc),
      runs suite cache ch ≤ hitCount cache ch := by
  intro suite
  induction suite with
  | nil => intro cache ch; cases cache <;> simp [runs, hitCount]
  | cons c cs ih =>
    intro cache ch
    cases cache with
    | nil => simp [runs]
    | cons e es =>
      have := ih es ch
      simp only [runs, hitCount]; omega

/-- Theorem 3, part 1: equality when suite and cache have the same length. -/
theorem runs_eq_hits {α : Type} :
    ∀ (suite : List (Comp α)) (cache : List (α × List Loc)) (ch : List Loc),
      suite.length = cache.length → runs suite cache ch = hitCount cache ch := by
  intro suite
  induction suite with
  | nil => intro cache ch h; cases cache with
    | nil => rfl
    | cons _ _ => simp at h
  | cons c cs ih =>
    intro cache ch h
    cases cache with
    | nil => simp at h
    | cons e es =>
      simp only [List.length_cons, Nat.add_right_cancel_iff] at h
      simp only [runs, hitCount, ih es ch h]

/-- Theorem 3, part 2. -/
theorem hitCount_le_length {α : Type} :
    ∀ (cache : List (α × List Loc)) (ch : List Loc), hitCount cache ch ≤ cache.length := by
  intro cache ch
  induction cache with
  | nil => simp [hitCount]
  | cons e es ih =>
    simp only [hitCount, List.length_cons]
    split <;> omega

theorem hits_mono {ch ch' : List Loc} (hsub : ∀ l, memb l ch = true → memb l ch' = true) :
    ∀ fp, hits fp ch = true → hits fp ch' = true := by
  intro fp
  induction fp with
  | nil => simp [hits]
  | cons x xs ih =>
    intro h
    simp only [hits, Bool.or_eq_true] at h ⊢
    cases h with
    | inl h => exact Or.inl (hsub x h)
    | inr h => exact Or.inr (ih h)

/-- Theorem 3, part 3: a smaller change never runs more cases. -/
theorem hitCount_mono {α : Type} {ch ch' : List Loc}
    (hsub : ∀ l, memb l ch = true → memb l ch' = true) :
    ∀ (cache : List (α × List Loc)), hitCount cache ch ≤ hitCount cache ch' := by
  intro cache
  induction cache with
  | nil => simp [hitCount]
  | cons e es ih =>
    simp only [hitCount]
    cases h : hits e.2 ch with
    | false => simp only [Bool.false_eq_true, ↓reduceIte]; split <;> omega
    | true =>
      have h' := hits_mono hsub e.2 h
      simp only [↓reduceIte, h']; omega

/-- Theorem 3, part 4: empty change, nothing runs. -/
theorem hitCount_nil {α : Type} (cache : List (α × List Loc)) : hitCount cache [] = 0 := by
  have : ∀ fp : List Loc, hits fp [] = false := by
    intro fp; induction fp with
    | nil => rfl
    | cons x xs ih => simp [hits, memb, ih]
  induction cache with
  | nil => rfl
  | cons e es ih => simp [hitCount, this, ih]

Tiers

Tiers. A tier structure over a type of facts has a top index top\mathrm{top} and two predicates, covers(i,f)\mathrm{covers}(i, f) (tier ii checks fact ff) and pass(i,f)\mathrm{pass}(i, f) (tier ii‘s check of ff passes). Let truth\mathrm{truth} be a predicate on facts: what is actually the case on the real system.

  • Faithful (hypothesis): if tier top\mathrm{top} covers ff and passes it, then truth(f)\mathrm{truth}(f).
  • Refines (hypothesis): for every i<topi \lt \mathrm{top}, if tier ii covers and passes ff, then tier i+1i + 1 covers and passes ff.
  • Gate passes: for every i≤topi \le \mathrm{top} and every ff that tier ii covers, tier ii passes ff.

Faithful says the device tier is the real system for the facts it checks. Refines says a pass at one tier predicts a pass at the next, which in particular requires every higher tier to check every fact that a lower tier checks and passes. Neither is proved here. They are claims about how the tiers were built, and the theorems below show exactly where each one is used.

Theorem 4.

  • (a) Gate soundness at the top. Faithful and gate passes imply truth(f)\mathrm{truth}(f) for every ff that tier top\mathrm{top} covers. Refines is not used.
  • (b) Fast-path soundness. Faithful and Refines imply: for every i≤topi \le \mathrm{top}, if tier ii covers and passes ff, then truth(f)\mathrm{truth}(f).
  • (c) Gate soundness for all tiers. Faithful, Refines and gate passes imply truth(f)\mathrm{truth}(f) for every ff that any tier covers.
  • (d) Early refutation. Faithful and Refines imply: for every i≤topi \le \mathrm{top}, if tier ii covers ff and ff is false, then tier ii does not pass ff.

Proof. (a) Gate passes at i=topi = \mathrm{top} gives a top-tier pass, and Faithful turns it into truth. (b) Induction on d=top−id = \mathrm{top} - i lifts a pass at tier ii to a pass at tier top\mathrm{top}, one Refines step at a time, and Faithful finishes. (c) Gate passes supplies the pass that (b) needs. (d) is the contrapositive of (b). ∎

/-! ## 4. Tiers -/

structure Tiers (Fact : Type) where
  top    : Nat
  covers : Nat → Fact → Prop
  pass   : Nat → Fact → Prop

variable {Fact : Type}

/-- The top tier is the real system: its passes are true. (Hypothesis.) -/
def Faithful (T : Tiers Fact) (truth : Fact → Prop) : Prop :=
  ∀ f, T.covers T.top f → T.pass T.top f → truth f

/-- Each tier's pass on a fact it covers implies the next tier covers and passes it. -/
def Refines (T : Tiers Fact) : Prop :=
  ∀ i, i < T.top → ∀ f, T.covers i f → T.pass i f → T.covers (i+1) f ∧ T.pass (i+1) f

def GatePasses (T : Tiers Fact) : Prop :=
  ∀ i, i ≤ T.top → ∀ f, T.covers i f → T.pass i f

/-- Theorem 4a: the gate is sound for top-tier facts, with no refinement hypothesis. -/
theorem gate_sound_top (T : Tiers Fact) (truth : Fact → Prop)
    (hF : Faithful T truth) (hG : GatePasses T) :
    ∀ f, T.covers T.top f → truth f :=
  fun f hc => hF f hc (hG T.top (Nat.le_refl _) f hc)

theorem lift (T : Tiers Fact) (hR : Refines T) :
    ∀ d i f, i + d = T.top → T.covers i f → T.pass i f →
      T.covers T.top f ∧ T.pass T.top f := by
  intro d
  induction d with
  | zero => intro i f h hc hp; rw [← h]; exact ⟨hc, hp⟩
  | succ d ih =>
    intro i f h hc hp
    have ⟨hc', hp'⟩ := hR i (by omega) f hc hp
    exact ih (i+1) f (by omega) hc' hp'

/-- Theorem 4b: fast-path soundness: a pass at any tier certifies the facts it covers. -/
theorem fast_path_sound (T : Tiers Fact) (truth : Fact → Prop)
    (hF : Faithful T truth) (hR : Refines T) :
    ∀ i, i ≤ T.top → ∀ f, T.covers i f → T.pass i f → truth f := by
  intro i hi f hc hp
  have ⟨hc', hp'⟩ := lift T hR (T.top - i) i f (by omega) hc hp
  exact hF f hc' hp'

/-- Theorem 4c: the full gate is sound for every fact any tier covers. -/
theorem gate_sound_all (T : Tiers Fact) (truth : Fact → Prop)
    (hF : Faithful T truth) (hR : Refines T) (hG : GatePasses T) :
    ∀ i, i ≤ T.top → ∀ f, T.covers i f → truth f :=
  fun i hi f hc => fast_path_sound T truth hF hR i hi f hc (hG i hi f hc)

/-- Theorem 4d (contrapositive of 4b): under refinement, a false fact fails at the cheapest tier covering it. -/
theorem early_refutation (T : Tiers Fact) (truth : Fact → Prop)
    (hF : Faithful T truth) (hR : Refines T) :
    ∀ i, i ≤ T.top → ∀ f, T.covers i f → ¬ truth f → ¬ T.pass i f :=
  fun i hi f hc hn hp => hn (fast_path_sound T truth hF hR i hi f hc hp)

end SoundFastTesting

Theorem 4(d) runs in one direction only. A false fact fails at every tier that covers it, including the cheapest, so a bug is caught as early as the tiers allow. A failure at a cheap tier, however, does not show that the fact is false: a cheap tier may be stricter than the real system, and the hypotheses say nothing about that direction.

What the combination achieves

The two halves connect through the tier predicates. Fix a tier ii with suite SiS_i of test cases, and let each fact ff that tier ii covers be checked by one case of SiS_i. Read pass(i,f)\mathrm{pass}(i, f) as “the verdict of that case on the current store is pass”. The procedure keeps one cache per tier and replays every change into each of them. By Theorem 2″, applied to each tier separately, every cached verdict equals the verdict a full re-run of that case would give on the current store. So the fast path and the release gate, read from the caches, evaluate the same predicates as a full re-run would, and Theorem 4 applies to them unchanged. Under this reading, Faithful and Refines are hypotheses about the current store and must hold for each store in the history. This step is an instance of Theorem 2″ argued in prose; the Lean file proves the two halves separately and does not state the instance as one theorem.

goaldelivered byrests on
exactnessTheorem 2′A1–A4
durabilityTheorem 2″A1–A4
costTheorem 3A6 for what “cost” counts
fast pathTheorem 4(b), 4(d)Faithful, Refines (A5)
release gateTheorem 4(a)Faithful only
release gate, all tiersTheorem 4(c)Faithful, Refines (A5)

The release gate always includes the device tier because of the “release gate” row: Theorem 4(a) is the only tier result that does not depend on Refines, and Refines is an unproved claim about how faithful the cheaper tiers are. Requiring every tier to pass adds the guarantee of the last row, Theorem 4(c), which does depend on Refines. The fast path gives a quick answer whose soundness is conditional on Refines. The release gate gives an answer whose soundness for device-checked facts needs only Faithful. Selection keeps both cheap: in every tier, only the cases the change reaches are executed.

Limits and assumptions

The theorems hold in the model. These are the places where a real system has to meet the model.

  • A1, complete instrumentation. Every input a case depends on is a store read that gets recorded: code, configuration, time, randomness, network and device state. In Lean this holds by construction, because a computation can only see the store through read\mathrm{read}. In a real system it is an obligation on the implementation, and an unrecorded input takes the case outside the model, and Theorem 1 then no longer applies to it, with no visible sign.
  • A2, changes are store writes. A code change is modelled as a write to the locations the computation reads, such as a file’s content. The changed set CC must contain every location that actually changed; this is the hypothesis s≈Cts \approx_C t.
  • A3, determinism. A case is a function of the store. A flaky or nondeterministic case falls outside the model, unless its source of variation is itself a recorded location, such as a seed.
  • A4, footprints from the cached store. Footprints are recorded on the store the cache holds, the previous store. Theorem 2″ shows this stays consistent over any history.
  • A5, tier hypotheses. Faithful and Refines are hypotheses about the tiers and are not proved. Refines also asks every higher tier to cover the facts that a lower tier covers and passes.
  • A6, what cost counts. The cost theorems count case executions, each with weight 1. The time of each case and the work of computing intersections are not modelled, so “seconds” depends on the selected cases being cheap.
  • Granularity. Selection is only as precise as the locations. If a location is a whole file, a change to a comment in it re-runs every case that read the file. That is safe but costs extra runs.
  • Minimality is not proved. A case whose footprint hits the change may still keep its verdict. The one-read example shows only that hit cases cannot be skipped in general.
  • Types. Locations and values are natural numbers. Generalising them to any type with decidable equality would be routine but was not done.
  • No cryptography. Nothing here involves a cryptographic property or a computational model.

Prior work

The read-set theorem is the soundness property behind verifying traces in “Build systems à la carte” (ICFP 2018), and the representation of a computation as a tree of reads is close to the monadic tasks of that paper. A generic form of such trees, with arbitrary requests in place of reads, appears in “Interaction trees: representing recursive and impure programs in Coq” (POPL 2020). Recording the inputs a computation actually requests, rather than declaring them in advance, is the approach of “Shake before building: replacing make with Haskell” (ICFP 2012). Self-adjusting computation, from “Adaptive functional programming” (POPL 2002) and “Adapton: composable, demand-driven incremental computation” (PLDI 2014), records reads to re-execute only what a change reaches.

Safe selection of regression tests from the parts of a program that each case exercised is the subject of “A safe, efficient regression test selection technique” (ACM Transactions on Software Engineering and Methodology, 1997). Theorem 2 is the same safety property stated for a store model with read sets recorded at run time.

Refinement between an abstract model and a concrete system is the subject of “Proof of correctness of data representations” (Acta Informatica, 1972) and “Program development by stepwise refinement” (Communications of the ACM, 1971). The tier hypothesis Refines is a one-step refinement claim between neighbouring tiers, restricted to the facts each tier checks.

What this article adds is the combination of the three, a statement of the goal it serves, and a single Lean file that proves the combination meets that goal under assumptions that are stated explicitly.