ReadingResearchRadarInvestment framework
Sign in / Sign up
← Back to reading
NewsMaterial4 min readDisconfirmAI Editorial

Semantic Diffing of Formal Policies with Anti-Unification

When large language models generate formalized policies for the same requirement twice, textual differences mark numerous meaningless syntactic changes, while true differences that alter authorization behavior (such as And becoming Or) may be drowned out. An AWS Machine Learning blog introduces an open-source engine that uses anti-unification to compute semantic diffs on equivalence graphs, presenting shared structure only once and marking every genuine divergence as a reviewable Variants node.

2026-11-12 07:33 GMT+8

When an automated policy generation process translates the same natural language requirement into two formal policies, the first question facing reviewers is not which one is correct, but where they actually differ. Textual diff tools fail systematically here: swapping the order of two conjuncts, rewriting an external destination as non-internal, or replacing one predicate with an equivalent one will flag many lines as changed, while the real difference in authorization behavior—such as changing And to Or—may be lost in the noise.

The AWS Machine Learning blog introduces semi-persistent, an open-source engine that computes semantic diffs of formal policies using anti-unification. Anti-unification stems from Plotkin's classic 1970 work, aiming to find the most specific common pattern between two expressions. The engine runs over an e-graph, which tracks expressions known to be equal; users inform the engine which syntactic changes do not alter meaning by declaring algebraic laws (such as associativity, commutativity, and idempotence of conjunction) and domain rules (such as equating an external destination with a non-internal one).

The engine outputs a single term where shared structure appears only once, and each divergence is marked as a Variants node containing the complete subtrees of both candidates. Selecting the first child of each Variants node reconstructs candidate A, while selecting the second child reconstructs candidate B. This means the anti-unification result is a lossless merge of the two inputs: it does not discard information but folds identical parts together and retains and locates differing parts.

Sign in / Sign up
ReadingResearchRadarInvestment framework

The blog demonstrates how this works with a concrete example. The requirement is: sensitive data sent to an external destination must be encrypted. Candidate A is written as sensitive(data) ∧ external(dst) → encrypted; Candidate B is written as ¬internal(dst) ∧ sensitive(data) → audited. A textual diff would flag condition rearrangement, predicate rewriting, and different conclusions. The engine initially reports two divergences: one in the conditions (external vs. ¬internal) and one in the conclusions (encrypted vs. audited). The user declares the domain fact as a rewrite rule—equating external with ¬internal—and after saturation, re-runs the diff. The condition divergence disappears, leaving only the conclusion divergence: Candidate B audits where the requirement demands encryption. A single Variants node precisely points to the location requiring review.

In a more complex example, two encodings of a cross-Region replication policy exhibit five textual differences. Three are purely syntactic: reordering of conjuncts, swapping equality arguments, and expanding approvedRegion into two specific Regions. After declaring And as associative, commutative, and idempotent, and Eq as commutative, the first two are absorbed; adding a domain rewrite equating approvedRegion to the disjunction of the two Regions absorbs the third. The remaining two divergences are genuine behavioral differences: one encoding uses Or instead of And in the confidential object clause (allowing either encryption or same-account status, rather than requiring both), and the other uses strict less-than instead of less-than-or-equal at the size threshold (objects exactly at the threshold take a different path). Semantic diffing compresses five textual changes into two reviewable semantic divergences, reducing the compression ratio from 0.59 to 0.40.

The method has clear boundaries. It does not prove any candidate is correct: both translations can share the same error, and shared errors will not appear as divergences. It relies on user-declared algebras and rewrites; if domain knowledge is incomplete, true equivalences may remain as Variants nodes. The search itself may also be incomplete—when using default Monte Carlo search rather than exact solving, results are labeled budget rather than exact, meaning a smaller common pattern may not have been found. The engine does not evaluate policies, query SMT solvers, or judge which translation matches the requirement; it only organizes information, directing reviewer attention to locations that might genuinely change behavior.

For teams using large language models to automatically generate formal policies, the practical value of this method lies in the fact that, after generating multiple candidates, there is no need for manual line-by-line comparison or reliance on the model's own judgment. Semantic diffing provides a deterministic, repeatable starting point for review: examine the positions marked by Variants nodes, and resolve them one by one using schema validation, replay, example input/output pairs, or human judgment.

The engine is open-sourced under the Apache-2.0 license and requires a Rust toolchain to build, taking S-expression files as input. The blog provides several runnable policy examples covering comparative candidate translations across four policy formats: Cedar, Dogwood, OpenShell, and CEL.

Sources

  • aws.amazon.comAmazon Web Services↗
Continue researching →