Certified Locality for Rank-One Edits

Model editing changes a single fact or behavior in a trained network by adding a tiny, carefully computed weight update, usually a rank-one matrix (an outer product of two vectors), to one hidden layer. Editors claim this change is "local": inputs unrelated to the edit should behave exactly as before. Today that claim is checked only by sampling test prompts, and at scale it fails. Formal verification can instead prove that a network behaves correctly on every input in a continuous region. But verifiers assume the network is fixed, so after any weight change they throw away their old proofs and start over. This proposal joins the two problems at a single algebraic fact. A rank-one edit at layer $l$ changes the network only through one scalar, the dot product between the layer's input and the edit's key vector. The edited network is therefore the original network plus a one-dimensional side channel. We propose a verifier that treats it that way. It reuses every bound from the original proof up to the edited layer, bounds the scalar with a single linear query, and pushes a one-dimensional perturbation through the remaining layers.

The result is a new kind of guarantee and a faster way to get it. The guarantee is a certified locality region: a set of inputs on which the edit provably moves the output by at most $\epsilon$. The speed comes from never re-verifying from scratch after an edit to a middle layer. Existing incremental verifiers cannot reuse proofs in that setting, because their guarantees stop at the final layer. We test the idea where complete verification is feasible, on the standard MNIST, CIFAR-10 and ACAS Xu verification networks, using ROME-style repair edits. We also run a cheap diagnostic on real language-model edits that is exact at the edited layer.

Core Claim

Let the edited layer compute $z = W h$, where $h = h_l(x)$ is that layer's input for network input $x$. A rank-one edit replaces $W$ with $W + \Lambda k^\top$, where $k$ is the key vector the editor computed for the subject and $\Lambda$ is the value-direction vector chosen so the key maps to the new fact. Writing $s(x) = k^\top h_l(x)$, the edited pre-activation is

$$z'(x) = W h_l(x) + \Lambda\, s(x).$$

The difference between the edited network $f'$ and the original network $f$ depends on the input only through two things: $h_l(x)$, which is shared and whose bounds the original proof already contains, and the scalar $s(x)$. If $s(x)$ lies in $[s_{lo}, s_{hi}]$ for every $x$ in a region, then

$$\|f'(x) - f(x)\|_\infty \le D_{l}(\Lambda, [s_{lo}, s_{hi}]),$$

where $D_l$ is the bound we get by propagating a perturbation confined to the fixed direction $\Lambda$, with magnitude in that scalar interval, through layers $l+1,\dots,L$.

Two consequences follow. First, bounding $s$ is a linear objective over the original network's layer-$l$ bounds. It costs one bound-propagation pass of the kind used by CROWN, the linear-relaxation method that wraps each ReLU in linear upper and lower envelopes. Second, the source of the downstream perturbation is one-dimensional. Branch-and-bound can therefore split on the scalar $s$ (a 1-D interval split) instead of on the thousands of hidden units (neurons) whose ReLU is "unstable", meaning it could be either on or off within the region. A sequence of $n$ edits becomes $n$ scalar channels. Proofs for earlier edits stay valid as long as the new channel's bound does not flip any neuron those proofs relied on to be stable.

Relation to Prior Work

The verification side supplies the machinery. Beta-CROWN folds per-neuron branching constraints into GPU bound propagation through optimizable dual multipliers. We reuse it unchanged as the engine and change only what is recomputed after an edit. Two papers motivate this proposal by solving a weaker version of the problem.

Incremental Verification of Neural Networks (IVAN) stores the tree of branching decisions from a previous proof and restarts search from its leaves after quantization or weight perturbation. Its validity theorem covers only final-layer perturbations, and it treats updates as unstructured. Online Verification under Domain or Weight Shift reuses unchanged layers' reachable sets, but only when fine-tuning touches the last layer. Editors, by contrast, deliberately target middle feed-forward layers, for example WilKE and salient-layer editing. Our contribution is exactly the part both papers leave open: edits in the middle of the network with known rank-one structure.

Two further papers supply the specification form. SABRE verifies relations between two runs of one network by splitting "relational neurons," meaning differences between the two runs' activations. Formal Mechanistic Interpretability encodes a full model and a circuit extracted from it as a Siamese pair, two copies sharing the same input, to certify that they agree. We use the same kind of pre-edit versus post-edit relational specification. We differ in noticing that the two networks are identical up to layer $l$ and differ afterward by a scalar-gated direction, so the relational problem has one real degree of freedom rather than one per neuron.

On the editing side, three papers constrain and motivate the design. Model Editing at Scale leads to Gradual and Catastrophic Forgetting shows that sampled locality metrics miss gradual bleed into unrelated inputs until downstream performance collapses. That is the failure a worst-case certificate should expose. Rebuilding ROME attributes much of the collapse to a key-vector inconsistency that inflates the size of the update. We adopt its consistent-key form (r-ROME) as our default editor, and we test whether its fix shows up as certifiably larger locality regions. CrispEdit argues that capability preservation needs global projection onto low-curvature directions of the loss rather than subspace locality. Its evidence is empirical and rests on a second-order Taylor approximation. Our certificates give a direct worst-case test of whether a plain rank-one edit has any non-trivial region of provable invariance, which is the open tension across these three papers.

Research Program

The first component is the rank-one incremental verifier. From the stored pre-edit proof, we keep all intermediate bounds at layers up to $l$ and the stored branching tree. We compute $[s_{lo}, s_{hi}]$ with one linear bound query per subdomain. We then shift the bounds at layer $l$ by $\Lambda \cdot [s_{lo}, s_{hi}]$ and re-tighten only downstream bounds, warm-starting the dual multipliers from the old proof.

The layers after the edit are nonlinear, so the old proof does not automatically survive. We derive a validity test. A downstream neuron that was stable keeps its phase if its shifted interval still excludes zero. A branch of the stored tree needs re-examination only if it depends on a neuron whose phase flipped. This extends IVAN-style tree reuse to middle layers. We will state the soundness argument formally; it follows directly from the interval shift being exact at layer $l$. When $s$ has a wide range, we branch on $s$ first. Splitting one scalar interval shrinks the downstream perturbation for every neuron at once, which is the step that single-neuron splitting cannot imitate.

The second component is the certified locality region. For a rank-one edit, the natural preservation specification is "if $|s(x)| \le \tau$ then the output moves by at most $\epsilon$." We search over $\tau$ for the largest threshold that certifies. We report which preservation points and perturbation balls fall inside the region and which do not. This produces a certified counterpart to the empirical locality score used on CounterFact.

The third component is sequential editing. We maintain a set of scalar channels and study how certification cost and region size change as edits accumulate. We also test whether r-ROME versus original ROME updates change the growth rate of the certified divergence. That would give a formal reading of the collapse reported in Model Editing at Scale.

The fourth component is a language-model diagnostic, kept deliberately modest. Complete verification of GPT-J-scale Transformers is out of reach, and we do not claim it. What is exact and cheap at any scale is the gate itself. For each CounterFact locality prompt, the question is whether $|k^\top h_l|$ stays below $\tau$ over a ball of residual-stream perturbations around that prompt's layer-$l$ hidden state. The residual stream is the running hidden vector that each Transformer layer reads from and adds to. This is one linear optimization per prompt. We will test whether the fraction of prompts whose gate provably stays closed predicts the empirical bleed and downstream drop measured on GPT2-XL and GPT-J edit sequences.

Baselines

The naive reference point is re-verifying from scratch: after each edit, run α-β-CROWN, the combined CROWN and Beta-CROWN verifier from Beta-CROWN, on the edited network with default settings, the same GPU and the same per-property timeout. It is the honest floor, because GPU bound propagation is already fast. Any incremental method must beat it in wall-clock time at an equal number of properties certified, not merely in node counts.

The strongest existing method is IVAN (Incremental Verification of Neural Networks). It reports a geometric-mean speedup of 2.4x on MNIST and CIFAR-10, 3.8x on ACAS Xu, and up to 43x on hard instances over non-incremental α-β-CROWN. We will run it on exactly our edited networks and properties, give it its stored tree from the same pre-edit proof, and use the same timeout. Because its theory covers only final-layer changes, we will report results separately for edits at the last layer and at middle layers. Beating IVAN means a higher geometric-mean speedup over the from-scratch baseline on middle-layer edits with no loss in the number of properties certified. On final-layer edits we would count a tie as acceptable.

We also include the incremental computation and Lipschitz-tolerance scheme of Online Verification under Domain or Weight Shift. It reports a 100x speedup (about 11 s to 0.1 s) for final-layer fine-tuning on a four-layer network. We run it where it applies, which is final-layer edits and its Lipschitz tolerance at any layer. This checks whether a cheap global bound already suffices.

The ablation that isolates the key ingredient is a dense relational verifier. It uses the same Siamese pre/post encoding as Formal MI and SABRE-style splitting of relational neurons, but treats $\Delta W$ as a generic dense matrix. We will count SABRE's ACAS Xu result, 67 instances solved that RaVeN could not versus 12 for individual splitting, as evidence of how strong relational splitting already is. A second ablation keeps the rank-one bound reuse but turns off branching on $s$. It measures how much of the gain comes from the one-dimensional split rather than from reusing bounds.

Why not just…?

Why not just re-verify from scratch with α-β-CROWN, since it is already fast? For one edit on a small network this may well be good enough, and we will report where that holds. The cost argument concerns sequences: each of $n$ edits triggers a full branch-and-bound search. IVAN's 43x speedups on hard instances show that discarded trees are costly exactly where verification is hard. Our sequential experiment measures whether cumulative cost grows roughly linearly in the number of edits, one cheap scalar pass per edit, or like repeated full searches.

Why not just run IVAN, treating the edit as a small weight perturbation? This is the real threat. If IVAN's tree reuse already works well for middle-layer edits, our speedup claim shrinks to a constant factor. The middle-layer split of the IVAN comparison settles this directly. Even in that case, the certified locality specification, with its threshold $\tau$ on $s$, remains a contribution that IVAN does not express, because IVAN proves that old properties still hold, not how far the edit reaches.

Why not just measure locality empirically, or use CrispEdit's curvature projection? Sampling missed the onset of collapse in Model Editing at Scale. In Formal MI, circuits found by sampling had under 50% robustness under small perturbations, against 100% for the provably robust circuits. CrispEdit reports below 1% average capability loss, but that is a statement about sampled benchmarks under a local approximation. We will compare directly: for every point where empirical locality looks fine, we report whether a certificate exists, and whether an attack using projected gradient descent (PGD) finds a large divergence where certification fails.

Why not just edit with in-context prompts, which beat ROME on RippleEdits? Ripple Effects reports that in-context editing beats ROME by over 10 points on GPT-NeoX and 29 on LLaMA. That is a fair critique of the quality of parametric edits for language models. It does not address this proposal's question, which is certifying a permanent weight change, and it offers nothing for the controller and vision networks where certificates are actually attainable.

Proposed Experiments

For networks, we use the standard fully connected and convolutional MNIST networks (MNIST-F, MNIST-C), the CIFAR-10 base, wide and deep models, and ACAS Xu, as in SABRE and IVAN, with the NN4Sys suite (shuyilinn/NN4Sys_Benchmark) as a held-out check.

The edits are repairs. For a misclassified or specification-violating input, we compute an r-ROME-style closed-form rank-one update at a chosen hidden layer, with the key taken from averaged activations and the value obtained by optimizing toward the correct output. We run sequences of 1 to 100 edits at the first, middle and last hidden layers.

The properties are the networks' original local-robustness and ACAS Xu safety properties on points not involved in the edits. We add the relational property that the output moves by at most $\epsilon$ over a perturbation ball, and we search for the largest certifiable threshold $\tau$.

We measure the fraction of properties certified within the timeout, wall-clock time, and the number of branch-and-bound nodes, all relative to from-scratch verification. We also measure the gap between the certified divergence bound and the largest divergence a PGD attack can find, which tests tightness.

Three decisive checks determine whether the proposal succeeds. First, on middle-layer edits, the rank-one verifier must beat IVAN's speedup over the from-scratch baseline at equal certified count. Second, removing the split on $s$ must measurably increase node counts on instances where $s$ has a wide range. Third, the certified divergence must stay within a small factor of the PGD lower bound. If the bound instead explodes after the first unstable downstream layer, the answer to the open question from Rebuilding ROME and CrispEdit is that rank-one locality is not certifiable in practice. That negative result would be worth reporting.

On the language-model side, we run the gate diagnostic over the sequential edits on GPT2-XL and GPT-J from Model Editing at Scale. We compare ROME and r-ROME against their CounterFact locality scores; Rebuilding ROME reports locality of 75.8 for ROME and 80.62 for r-ROME. We also compare against GLUE trajectories. Success means the fraction of locality prompts whose gate is provably closed falls before downstream collapse, not after it.