Complete Symmetry Breaking for Finite Models

Marek Danco, Mikolás Janota, Michael Codish, João Jorge AraújoAAAI 2025 · DOI

Introduction

In automated reasoning and finite model finding, the "symmetry explosion" problem presents a significant hurdle. When searching for mathematical structures of a fixed size $n$, such as groups or semigroups, solvers often encounter millions of isomorphic copies—structures that are identical except for the labeling of their elements. This redundancy drastically increases the search space and computational cost. This paper, presented at AAAI-25, introduces a novel SAT-based technique to achieve complete symmetry breaking, ensuring that only a single unique representative of each structure is considered.

The Symmetry Challenge

For a domain of size $n$, there are $n!$ possible permutations of elements. Traditional "partial" symmetry breaking methods reduce redundancy but do not eliminate it entirely. "Complete" symmetry breaking, while theoretically ideal, has historically been viewed as impractical due to the super-exponential growth of required constraints. The authors address this by developing a method to generate compact sets of constraints that still guarantee completeness.

Methodology: Canonizing Sets and SAT Encoding

The researchers employ a "constrain and generate" approach centered on lexicographical ordering (lex-leader constraints). A structure is defined as a lex-leader if its multiplication table is the smallest possible version across all permutations.

Canonizing Sets

Instead of utilizing all $n!$ permutations, the authors propose an incremental algorithm to identify a "canonizing set"—a minimal subset of permutations sufficient to break all symmetries for a given class of structures.

Canonizing set size vs. magma size (n) for various algebraic structures.

As shown in the figure above, the size of these canonizing sets remains remarkably small compared to the theoretical maximum of $n!-1$, particularly for structures with more inherent algebraic properties. For instance, groups of size 10 required only 18 permutations for a complete break.

Vectorization Strategies

The efficiency of the SAT encoding depends on how the 2D multiplication table is flattened into a 1D vector for comparison. The authors compared a standard "row-by-row" approach with a "diagonal-first" strategy.

Comparison of canonizing set sizes between row-by-row and diagonal vectorization.

Empirical results indicate that diagonal vectorization consistently yields smaller canonizing sets and faster solving times. This "diagonal advantage" likely stems from the fact that diagonal elements often provide more immediate information for symmetry breaking in many algebraic structures.

Empirical Results and New Mathematical Data

By integrating these compact symmetry breaks with the d4 model counter, the authors successfully enumerated non-isomorphic structures that were previously beyond reach. Key findings include:

  • AG-groupoids: The study determined there are exactly 643,460,323,187 non-isomorphic AG-groupoids of size 7. Previous efforts had only reached size 6.
  • Implication Zroupoids: For $n=7$, the count was found to be approximately 600 trillion, a result previously undocumented in mathematical literature.
  • Efficiency in Groups: For groups of size 10, the system completed the count in just 149 seconds.

Conclusion

This research demonstrates that complete symmetry breaking is not only theoretically possible but practically feasible through compact canonizing sets and optimized SAT encodings. While computational limits are still encountered around $n=10$ for less-structured magmas, the method provides a powerful tool for mathematical discovery and the verification of sequences in the Online Encyclopedia of Integer Sequences (OEIS). Future work will explore extending the framework to multi-functional structures and further investigating the theoretical underpinnings of the diagonal vectorization advantage.

Summary updated

BibTeX
@inproceedings{danco2025complete,
  author = {Marek Danco and Mikolás Janota and Michael Codish and João Jorge Araújo},
  title = {{Complete Symmetry Breaking for Finite Models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i11.33217},
}
Figure