# Amazon — Semantic diffing of formal policies with anti-unification

- Company: Amazon (amazon.com)
- Announced: 2026-11-11T23:33:03+00:00
- Category: not stated
- Coverage: not counted
- Announcement: no
- Group: routine
- Source: https://aws.amazon.com/blogs/machine-learning/semantic-diffing-of-formal-policies-with-anti-unification/
- Record: https://forck.live/items/34924-semantic-diffing-of-formal-policies-with-anti-unification
- Subject: Bedrock / Nova

Amazon's post explains a semantic diff engine that uses anti-unification over an e-graph to show what two formal policies share and where they disagree. A textual diff often flags syntactic changes that do not affect meaning, so a real behavioral change, such as an Or where the requirement says and, can get lost in the noise. The engine supplies algebraic laws and domain rules that justify equalities, such as equating an external destination with one that is not internal, and shows the shared parts once while keeping both versions of each differing part for review. If no differences remain, the policies are equivalent under those laws and rules, though when the rules or the search are incomplete a remaining difference might reflect an equivalence the engine has not found. One use case is autoformalization, where an LLM generates formal artifacts from prose and can produce two different formalizations with no ground truth; the model writes the artifact and plays no part in computing the diff. Requirements can also become OpenShell sandbox policies or Common Expression Language expressions, and the engine reads encodings of the relevant syntax rather than importing native policies from those formats. In a worked example, two candidate rules for the requirement that sensitive data sent to an external destination must be encrypted produce an anti-unifier with two Variants nodes, one of which is a difference in vocabulary rather than meaning.

## Evidence

Verbatim from https://aws.amazon.com/blogs/machine-learning/semantic-diffing-of-formal-policies-with-anti-unification/:

> When reviewing code, you start with a diff. You wouldn’t compare two 3,000-line files by eye and hope to spot every change. Formal policies can be even harder to compare because a textual diff often highlights syntactic changes that don’t affect meaning. Reorder two conjuncts, swap the arguments of an equality, or use an equivalent predicate, and much of the file might appear changed. A real change in behavior, such as an Or where the requirement says and , can get lost in that noise.
> 
> A semantic diff shows what two policies have in common and where they disagree. The open source engine used in this post computes this diff using anti-unification , which finds a most specific common pattern for two expressions. Plotkin’s 1970 paper gives the classical formulation. The engine works over an e-graph, which keeps track of expressions known to be equal. We supply the algebraic laws and domain rules that justify those equalities, such as equating an external destination with one that isn’t internal. The result shows the shared parts once and keeps both versions of each differing part for review. If no differences remain, the policies are equivalent under those laws and rules.

---

Record: https://forck.live/items/34924-semantic-diffing-of-formal-policies-with-anti-unification
Catalogue: https://forck.live/llms.txt
Current issue: https://forck.live/feed.md
