AWS details semantic diffing of formal policies with anti-unification

AWS published a post on its Machine Learning Blog on 11 November 2026, written by Ferhat Erata and Remi Delmas. It explains how an open source engine uses anti-unification to compute a semantic diff of formal policies.

What happened

In the AWS post, the authors argue that a plain text diff is a poor fit for formal policies. Reordered conditions or an equivalent predicate can make a file look changed when its meaning is the same. A real change, such as an Or where the requirement says and, can get lost in that noise.

The engine works over an e-graph, a structure that tracks expressions known to be equal. Users supply the algebraic laws and domain rules that justify those equalities. The output shows shared parts once and keeps both versions of each differing part.

One use case the post describes is autoformalization: an LLM turns natural-language requirements into a formal language. The excerpt we had access to does not announce a release or say how to get the tool.

Key details

• Anti-unification finds a most specific common pattern for two expressions. The post cites Plotkin's 1970 paper for the classical form.
• The LLM only writes the formal artifact. It plays no part in computing the diff.
• Suggested workflow: generate several candidates by varying model, prompt or sampling temperature, then review the varying parts first.
• Target formats named: SMT-LIB, Cedar, Dogwood, OpenShell sandbox policies and Common Expression Language (CEL).
• The engine reads term encodings of the relevant syntax. It does not import native policies from those four formats.
• Results carry three fields: :size, :cr (a compression ratio) and :completion, which is exact or budget.
• In the worked example, declaring And as associative, commutative and idempotent removes the reordering. Before the rewrite, two differences remain: one is a vocabulary difference with the same meaning, the other a real one.
• Adding one rewrite for external removes the vocabulary difference. The result drops from size 11 and :cr 0.5 to size 8 and :cr 0.1429.
• One difference then remains: one rule audits where the requirement calls for encryption.

Try it

This is the rewrite step from the post. It assumes the vocabulary and the two rules were declared earlier.

(rewrite (external d) (Not (internal d)))
(run 2)
(antiunify ruleA ruleB :algorithm exact)

Why it matters

LLM output has no ground truth to check against. The post proposes comparing several outputs structurally instead. The authors say a low :cr means more shared structure, but not that the result is correct. They also note that a leftover difference may be an equivalence the engine has not found, if the rules or search are incomplete.

For related formal-methods work, see how Google DeepMind says AI agents verified Signal protocol code.

FAQ

What is a semantic diff of policies? It shows what two policies share and where they disagree. It treats as equal only the syntax changes covered by the declared equalities and rewrites, so it does not catch every change that leaves behavior the same.

Does the LLM compute the diff? No. According to AWS, the model writes the formal artifact and plays no part in computing the diff.

What does a cr of 0 mean? According to the post, a score of 0 means full agreement under the declared equalities.