Minimal-Change Repair Plans for Knowledge Edits

Methods that edit a language model's facts directly in its weights can change one fact cleanly. They do not change what should follow from it. Rank-one editors are the main example: they rewrite one feed-forward matrix with a single outer-product update so that a subject's internal key maps to a new value. Tell such a model that a country has a new president and it still names the old First Lady. Tell it that A is married to B and it still cannot say who B is married to. We propose to treat every edit as a small constraint-repair problem that is solved before any weight is touched. The fact being edited and its logical neighbors become true/false variables. The relation rules that bind them, such as symmetry, single-valuedness and composition, become constraints. The job is to find the smallest set of other facts that must be added or retracted so the neighborhood stays consistent. That set of changes is then written into the model with a standard batch editor.

The theory of constraint satisfaction contributes one concrete thing here. Reith and Vollmer's classification of optimal-assignment problems states exactly which kinds of rules allow a minimal repair to be computed efficiently and which make it intractable. The dividing line depends on the algebraic "polymorphisms" of the rules, meaning operations that combine satisfying assignments into new ones. This lets us say in advance, for each edit, whether a cheap local propagation is guaranteed to find the right repair, or whether the repair is hard or ambiguous. In the hard or ambiguous cases, existing heuristic propagation such as ChainEdit should be expected to fail.

Core Claim

Ripple failures after weight edits combine two different problems. The first is that the editor never applies the consequences. The second is that the consequences are not determined by the edit alone. Prior work blurs the two. We claim that the second problem can be predicted from the structure of the rules governing the edited fact, before any model is run. We also claim that an editor which computes a minimal-change repair will beat forward rule-chaining on two specific criteria. The first is Preservation, meaning keeping valid facts that should survive. The second is Relation Specificity, meaning not disturbing unrelated attributes. It should do at least as well on symmetry and composition criteria.

The algebra enters through a specific result. The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae shows that finding a lexicographically minimal satisfying assignment can be done in polynomial time in four cases: every constraint is Horn (preserved by AND), every constraint is anti-Horn (preserved by OR), every constraint is bijunctive (preserved by the majority operation), or every constraint is affine (preserved by the Mal'tsev operation $x - y + z$). Otherwise the problem is OptP-complete.

Many rules in a knowledge base fall into these classes:

  • Symmetry ("spouse(A,B) implies spouse(B,A)") and single-valuedness ("at most one capital") are 2-clauses, so they are bijunctive.
  • Composition rules ("head-of-state(X,P) and spouse(P,S) imply first-lady(X,S)") are Horn.

There is a catch the algebra makes visible. Minimal change measured against the model's current beliefs requires flipping the polarity of some variables. Bijunctive and affine constraints are closed under that flip, but Horn constraints are not. Neighborhoods that contain only symmetric, inverse and single-valued relations therefore keep a guaranteed-tractable minimal repair. Neighborhoods that mix composition rules with retractions can leave the tractable classes. We expect those mixed neighborhoods to be exactly where both heuristics and our planner struggle. This is a falsifiable prediction about where editing gets hard, and no existing editing paper makes it.

Relation to Prior Work

Three papers motivate the problem. Evaluating the Ripple Effects of Knowledge Editing in Language Models built RippleEdits, which has six logical criteria. It showed that ROME, MEMIT and MEND average only 38–66% on them, with ROME's symmetry score falling to 5.5% on popular entities. It diagnoses the failure but offers no account of when consequences are determined. Locating and Editing Factual Associations in GPT introduced ROME and noted that its edits are one-directional. Mass-Editing Memory in a Transformer introduced MEMIT, which spreads a least-squares update over several layers so that thousands of facts can be edited at once. That makes it the natural backend for writing a repair set, but it applies no logic.

ChainEdit is the closest work. It mines rules from Wikidata, checks that the model accepts them, chains forward from the edit, and batch-edits the resulting cluster with MEMIT. ChainEdit only adds implied facts. It has no notion of minimal change, does not systematically retract facts that a single-valued or symmetric relation forces out, and cannot tell when the repair is underdetermined. Our planner replaces its forward chaining with a solver that has known guarantees for each class of rules. Our classification then explains where ChainEdit-style propagation must break.

Two further papers constrain the design. CrispEdit protects general capability by projecting updates into low-curvature directions. It addresses a different failure, capability loss rather than logical consistency, so we treat it as an alternative backend rather than a competitor to the planner. Testing Assignments to Constraint Satisfaction Problems shows that whether a solution can be checked with a constant number of queries also depends on majority and Mal'tsev polymorphisms. We use this only as a secondary design guide for cheap post-edit consistency audits. We do not borrow its theorem as a guarantee about neural models.

Research Program

The work has four parts.

First, we build the constraint language. For each relation in RippleEdits we extract its Wikidata property constraints: symmetric, inverse-of, single-value, and type constraints. We add ChainEdit-style composition rules mined from the graph. Each rule becomes a clause over Boolean fact variables, and each clause is tagged with the polymorphisms it admits (Horn, anti-Horn, majority, affine). This tagging can be done mechanically, because Boolean clause classes can be recognized syntactically.

Second, for each edit we build the neighborhood. This contains facts within two hops of the subject and the new and old objects. Each fact is given a reference truth value: the model's own belief, obtained by querying it, with its probability recorded. The neighborhood is labeled by the smallest tractable class that contains all of its constraints after the polarity flip, or labeled "mixed."

Third, we compute the repair. The goal is a satisfying assignment that differs least from the reference beliefs, with ties broken lexicographically so that higher-confidence beliefs are kept first. Tractable neighborhoods use the polynomial-time algorithms behind Reith and Vollmer's classification. Mixed neighborhoods go to an exact weighted MaxSAT solver under a time cap. When several minimal repairs tie, the edit is flagged as underdetermined.

Fourth, we write the repair into the model. Added facts and object replacements become MEMIT edits. Symmetric relations get an explicit reverse edit, keyed on the other entity's subject token, which addresses the one-direction problem directly. Retracted facts with no replacement are handled by editing the fact toward a "none/unknown" target. The same repair set is also written with CrispEdit, so we can tell whether the editing backend or the planner drives the results.

Baselines

The naive reference point is plain MEMIT applied only to the requested fact, using the setup of Mass-Editing Memory in a Transformer. It shows how much ripple behavior appears with no planning at all. On Llama-3-8B, ChainEdit reports a symmetry (Logical Generalization) score of 18.6% for this baseline on RippleEdits.

The strongest existing parametric method is ChainEdit with a MEMIT backend. It reports raising Logical Generalization on Llama-3-8B from 18.6% to 58.7% on RippleEdits. We will rerun it on the same model, the same edits and the same rule set. That way any difference comes from how consequences are chosen, not from which rules are available. Beating it means at least matching 58.7% on Logical Generalization while improving Preservation and Relation Specificity by a margin larger than the seed-to-seed spread. No reported Preservation number for ChainEdit was found on Lacuna, so we will measure it ourselves.

The key ablation is "Datalog closure plus MEMIT." It uses the same constraints and the same backend, but replaces the minimal-change solver with plain forward chaining of the Horn rules, with no retraction and no minimality. This isolates exactly what the optimization adds.

A second ablation drops the class-based routing and sends every neighborhood to MaxSAT. This tests whether the tractability classification matters in practice or only in theory.

In-context editing is the non-parametric reference. Evaluating the Ripple Effects of Knowledge Editing in Language Models reports that it beats ROME by over 10 points on GPT-NeoX and by 29 points on LLaMA. We run it both with the edit alone and with the full repair set in the prompt. All methods share the same edit batches, a single-GPU budget, and the same hyperparameter search for MEMIT layers and regularization.

Why not just…?

Why not just use in-context editing? On ripple criteria it is the strongest number in the file. Putting our repair set in the prompt will show whether the planner's value carries over to that setting. Still, prompt-based edits do not persist in the model, and they grow with the number of edits. Our claim concerns parametric editing. If in-context editing with the edit alone still beats repair-plus-MEMIT, we will report that the consistency problem lies mostly in the weight-writing step, not in deciding which facts to change.

Why not just forward-chain rules, as ChainEdit does? This is the real threat. On pure-Horn neighborhoods, forward chaining is the minimal repair, so we expect no gain there. The Datalog ablation is designed to show where the two diverge. We predict divergence on neighborhoods that involve single-valued and symmetric relations, where retractions are needed. If no divergence appears on Preservation or Relation Specificity, the proposal shrinks to its diagnostic half, the prediction of where editing is hard, and we will say so.

Why not just use a better weight editor such as CrispEdit? Curvature projection protects broad capability, but it does not decide which facts follow from an edit. Running both backends on the same repair sets separates the two contributions. We expect CrispEdit to reduce MMLU damage, while the ripple gains should track the planner, not the backend.

Proposed Experiments

The main evaluation runs RippleEdits on all three subsets (RECENT, RANDOM, POPULAR) on Llama-3-8B and GPT-J. We report all six criteria. Results are broken down by the algebraic label of each edit's neighborhood: bijunctive-only, Horn-only, affine, or mixed.

The decisive check has three parts:

  • On bijunctive-only neighborhoods, which are dominated by symmetry and single-value rules, the planner should clearly beat both ChainEdit and the Datalog ablation on Preservation and Relation Specificity.
  • On Horn-only neighborhoods, the three should be roughly tied.
  • On mixed neighborhoods, every method should score lowest, and flagged-underdetermined edits should show the highest disagreement across random seeds.

The pattern itself is the test. If accuracy does not differ across the algebraic labels after controlling for neighborhood size and entity popularity, the classification adds nothing, and we will drop it.

Secondary checks guard against side effects. COUNTERFACT specificity on neighboring subjects confirms that the extra edits in the repair set do not spread to unrelated entities. MMLU and GSM8K after 1,000 and 3,000 sequential edits measure the cost of larger repair sets. That cost is measured against CrispEdit's reported degradation of below 1% and against MEMIT's reported double-digit drops, both from CrispEdit. We also report planner wall-clock time for tractable versus MaxSAT-routed neighborhoods, to show whether the tractability boundary shows up in real running time.