# Semantic diffing of formal policies with anti-unification

- Source: MechNext — https://mechnext.eu/en/article/69-semantic-diffing-of-formal-policies-with-anti-unification
- Published: 2026-11-12
- Updated: 2026-11-12
- Category: Industry News
- Language: en (Markdown in other languages: ?lang=de, ?lang=sk, ?lang=pl, ?lang=zh, ?lang=ru)

> AWS describes an anti-unification engine that stores shared policy structure once and exposes disagreements as Variants nodes. Its results are relative to declared laws, rewrites, encodings, and search completion, with explicit limits on what has been formally verified.

An AWS Machine Learning Blog post titled _Semantic diffing of formal policies with anti-unification_ was published on November 11, 2026, at 23:33:03 UTC. It describes a semantic diff based on anti-unification over an e-graph. The process identifies structure shared by two formal policy representations while retaining both versions of every fragment that still differs under the declared algebraic laws and rewrite rules.

### A shared backbone with localized alternatives

The anti-unifier stores common structure once and marks disagreements with `Variants` nodes. Each such node preserves the corresponding fragments from both inputs. Consistently selecting one input’s side at every `Variants` node reconstructs that input, modulo the equalities declared for the comparison. The result is therefore a shared policy backbone with localized alternatives rather than a sequence of changed text lines.

If no differences remain, the two inputs are equivalent under the declared laws and rules. That qualification matters. Incomplete rules or an incomplete search can leave differences between expressions that are nevertheless equivalent. A remaining variant consequently describes what the configured process did not reconcile; it does not, by itself, establish every broader claim about the policies.

### What the language model does

In the described autoformalization workflow, a large language model generates formal artifacts, but it does not compute the diff. The engine performs that operation on term encodings. It does not directly import native SMT-LIB, Cedar, Dogwood, OpenShell, or CEL policies. This separates candidate generation from comparison: the diff operates on the encoded terms presented to it.

### Equational knowledge and reported metrics

The engine accepts algebraic annotations and explicit rewrites. Associative, commutative, and idempotent declarations make regrouping, reordering, and duplication equivalent. An identity element also allows a missing operand to align with the operator’s neutral element. These declarations determine which structural differences can disappear during semantic comparison.

The result reports `:size`, `:cr`, and `:completion`. The compression ratio is `(s − a) / b`, where `s` is the result size and `a` and `b` are the smaller and larger input sizes. A ratio of zero represents full agreement under the declared equalities. One is a no-sharing reference, not an upper bound. Completion is reported as either `exact` or `budget`. The ratio describes sharing in the result; a low value does not establish that a candidate is correct.

### What the examples expose

In the cross-Region replication example, five textual differences were reduced by the declared algebra and one domain rewrite to two semantic disagreements: a weakened confidential clause and a strict size threshold. The reported `:cr` fell from 0.5862 to 0.4000, reflecting the additional structure recognized as shared.

For the Dogwood candidates, the algebra and three rewrites removed six presentational differences. A schema error and a dropped path guard remained. Combining the correct event kind from one candidate with the guard from the other produced a policy that neither candidate had supplied. The diff exposes these components, but the anti-unifier does not determine which candidate correctly matches the requirement.

In the OpenShell example, checks for the binary, host, port, and layer stayed in the shared backbone. Two `Variants` nodes isolated disagreements about the permitted HTTP method and the scope of the path. The common checks did not need to be repeated, leaving the alternatives concentrated at the two points of disagreement.

In the CEL example, the diff localized a missing production condition in the port-443 branch. With `is_prod` false and the port set to 443, candidate A denied the request while candidate B allowed it. The encoding did not model CEL errors or unknown values, and the engine did not check the stated assumptions about inputs. The localized result must therefore be read within those modeling limits.

### Solvers, state, and verification boundaries

The engine provides an exact dynamic-programming solver and a default anytime Monte Carlo graph search. It optimizes first for result size and then for shared-backbone structure. For repeated queries and backtracking, it uses semi-persistent `push` and `pop` snapshots stored as sparse diffs.

The engine is available on GitHub under the Apache-2.0 license. Its container-layer restore property has been verified in Verus with 1,703 verified conditions and zero errors. The scope of that result is specific: the full solver does not have an end-to-end refinement proof, and logged equivalence justifications are not yet independently replay-checked certificates. The semantic diff is thus presented with both its operating mechanism and its current verification boundaries made explicit.
