TriSearch: Learning to Optimize Triangulations via Bistellar Flips

Triangulations, i.e., well-structured decompositions of geometric objects into triangle-like pieces, are central objects in many domains of mathematics and physics. In particular, fine, regular, and star triangulations (FRSTs) of 4D reflexive polytopes give rise to smooth Calabi-Yau threefolds, which are of significant interest in string theory. However, the high dimensionality and combinatorial complexity of triangulations make them particularly challenging to model with classical numerical methods or machine learning. In this work, we show that transformers, equipped with an appropriate encoding scheme, can be effectively trained to representatively generate new FRSTs across a range of polytope sizes. Moreover, these models can also self-improve through retraining on their own output. This opens the door to both concrete applications to the classification of Calabi-Yau manifolds and further research in physics, combinatorics and algebraic geometry.

We introduce dualGNN', an autoregressive message-passing GNN for sampling fine, regular triangulations of lattice polytopes. dualGNN operates on a generalization of the dual graph of a triangulation, with edges labeled by signed circuits' -- combinatorial invariants from the theory of oriented matroids. We show that these circuits are necessary and sufficient to determine a triangulation's regularity from the graph, provided certain magnitude information is retained. The model is independent of the polytope's point count and invariant under its orientation-preserving symmetries ($\mathrm{SL}(d,\mathbb{Z}) \ltimes \mathbb{Z}^d$), and our masking procedure further guarantees that every rollout produces a fine triangulation (in 2D). On unseen polygons with $N_\mathrm{pts} \leq 40$, dualGNN is the only sampler we tested that is consistent with uniform sampling across all our diagnostics (KL divergence from uniformity, collision counts, and sample autocorrelation). The model is small ($\sim92$k parameters) and trains in $\sim7.5$ hours on a single consumer GPU. We apply dualGNN to string theory, sampling Calabi-Yau threefolds uniformly at $h^{1,1}=86$; we also sample CYs at $h^{1,1}=128$, observing no deviations from uniformity, but our diagnostics are weaker here. Code, training scripts, and pretrained models are available at https://github.com/natemacfadden/dualGNN (pip install dualgnn), and dualGNN is integrated into CYTools.

We introduce a class of random polytopes which simultaneously generalizes several known constructions. While being fairly general, these polytopes are also computationally exceptionally benign. We indicate how these properties can be exploited for classification and clustering tasks in data analysis. Crucially, our construction lets users smoothly trade off between a tighter description of the data and faster computation.