TriSearch: Learning to Optimize Triangulations via Bistellar Flips
arXiv:2605.30220v1 [cs.LG] 28 May 2026
Yiran Wang UCLA [email protected]
Guido Montúfar UCLA & MPI MiS [email protected]
Abstract We introduce TriSearch, a reinforcement-learning framework for optimizing objectives over triangulations of a polytope via bistellar flips. The key idea is a circuit-supported subtriangulation action representation: feasible flips are encoded by their supporting circuit and realized local subtriangulation, enabling a learned policy to rank them using local geometric and combinatorial features. This yields a dimension-agnostic interface and enables efficient traversal of the flip graph without explicit enumeration of the full triangulation space. Instantiated in 3D and 4D, TriSearch generalizes zero-shot from small training instances to larger polytopes with exponentially larger search spaces. It achieves top performance on metric objectives in 3D and, in 4D, discovers more distinct Fine, Regular, Star triangulations of reflexive polytopes, corresponding to Calabi-Yau threefolds, than existing samplers under a fixed budget.
1
Introduction
A triangulation of a d-dimensional polytope is a decomposition into d-dimensional simplices that meet only along shared faces. Triangulations are fundamental objects in computational and combinatorial geometry. They underpin a wide range of downstream pipelines: in mesh generation, finite element analysis, and computer graphics, triangulations discretize a continuous geometric domain so that numerical solvers and rendering algorithms can operate over a finite set of simplices [1–3]. In mathematical physics, triangulations of 4D reflexive polytopes parametrize large families of CalabiYau threefolds [4, 5]. Different applications value different properties of a triangulation, so the practical task is to find one that is good for a chosen objective. Mesh generation and finite element analysis prioritize element shape and count to control solver cost and numerical accuracy [2, 3], whereas computational geometry studies combinatorial and geometric objectives such as minimizing total edge length and minimizing the number of simplices [6–8]. Constructing a Calabi-Yau threefold requires finding a fine, regular, star triangulation (FRST) of a 4D reflexive polytope and applying Batyrev’s toric construction to map it to a corresponding threefold [4]. Within this constrained family, the practical goal is to discover as many distinct topological classes as possible [5, 9]. Each of these objectives selects a different region of the same combinatorial space, motivating a unified search framework that can target any of them. For a d-dimensional polytope P, triangulation optimization is generally hard, especially for d > 2. This difficulty stems from the cardinality of the triangulation space T (P), which can grow exponentially in both the ambient dimension d and the number of vertices |V(P)|, with a standard ⌈d/2⌉ ) worst-case upper bound of 2O(|V(P)| [10]. Within this exponentially large search space, only a few special cases are known to admit polynomial-time algorithms [11]. In contrast, many natural objectives are computationally intractable: for example, deciding whether a triangulation minimizes the number of simplices for d > 2, or the total edge length for d ≥ 2, is NP-hard [6–8]. Preprint.
The triangulation space T (P) has a natural local structure given by bistellar flips. A circuit is a minimal affinely dependent set of vertices that supports two local triangulations. A bistellar flip replaces the realized local triangulation in the current triangulation with the other one. These moves organize triangulations into a flip graph G(P), whose nodes are triangulations and whose edges correspond to single flips. At any given state, only circuits whose realized subtriangulation is contained in the current triangulation are flippable, so the set of feasible moves is local and changes after each move. This state-dependent, geometry-constrained action space makes standard neural combinatorial optimization methods difficult to apply directly. This observation leads to our formulation of the triangulation problem, and the design of TriSearch. We identify triangulation optimization as search on an implicit flip graph, where states are complete triangulations and actions are currently feasible bistellar flips. We then reformulate the problem as reinforcement learning on this graph, but do not ask the policy to learn geometric validity from data. Instead, we use a geometric routine [12] to expose the valid local moves, and the learned policy decides which move is useful for long-range optimization. This formulation requires an architecture that can compare a state-dependent set of graph actions. We address this by representing each feasible action through the circuit supporting the flip and the realized local subtriangulation structure. This encodes both a certificate of admissibility and the local replacement performed by the move. Since circuits are defined intrinsically in any fixed dimension, the same action representation can handle different flip arities and objectives, and applies to both optimization and FRST discovery. Changing the task modifies only the reward, not the search interface. Main Contributions.
We summarize our contributions as follows:
• We identify triangulation optimization as reinforcement learning on an implicit flip graph, and introduce a learned search framework for this formulation. Geometric routines enumerate valid local moves, while a circuit-supported policy architecture scores which move is promising for long-range search. • Empirically, TriSearch shows strong performance in triangulation optimization under a fixed flip budget. It achieves the lowest aggregate relative gap among evaluated search algorithms in both 3D and 4D. Policies trained on smaller polytopes generalize to larger unseen instances, demonstrating that the learned local search generalizes beyond the hardness regime during training. • In the Calabi-Yau (CY) setting, we show that TriSearch has real application-level potential beyond benchmark optimization. The same framework becomes a practical FRST sampler and outperforms the existing CYT OOLS samplers under the same budget by discovering more distinct CY threefold classes.
2
Related Work
Deep Learning for Combinatorial Optimization. A large body of work leverages deep learning and reinforcement learning to address combinatorial optimization problems [13–15]. Prior work mostly focused on routing, scheduling, or graph-optimization settings. In these settings, states and actions have standard representations. Triangulation optimization is an important problem, but it has remained under-studied by the machine learning community. Constructive approaches build solutions incrementally, with representatives including pointer networks, attention-based policies, and policy-gradient models for routing [16–20]. This paradigm is effective when partial solutions are meaningful and feasibility can be checked or enforced locally. Triangulation optimization does not naturally fit this setting: once a d-simplex is placed inside P, the remaining region is generally non-convex in dimension above 2, and deciding whether such a region admits a triangulation is itself NP-hard [21]. Thus a partial list of simplices is not a reliable state for learning, and the validity of the final triangulation remains a global constraint. Another line of work focuses on learning local-improvement rules for complete solutions, such as routing tours, local rewrites, or Boolean assignments [22–24]. These methods are designed around problem-specific actions for TSP, MaxCut, CVRP, and JSSP [22–25]. Local-search controllers such as NeuroLS [25] operate at a meta level by learning acceptance criteria, operator choice, or perturbation on top of predefined local-search procedures, rather than scoring primitive moves themselves. In triangulation optimization, the primitive actions are bistellar flips, whose admissibility depends on the currently realized circuit subtriangulation. The policy therefore cannot act on a fixed set of nodes, 2
edges, variables, or tokens. Instead, we use a geometric routine [12] to enumerate valid flips, and train the policy to select among them based on their circuit-supported local subtriangulation. Triangulation Optimization and FRST Sampling. Triangulations, circuits, regular triangulations, and secondary polytopes have a well-developed theory [26, 27], with bistellar flips serving as the standard local moves between triangulations [28, 29]. Optimizing over this space is challenging, as reflected in hardness results for minimum-size triangulations in dimension three and for minimumweight triangulation [7, 8]. Unlike many combinatorial-optimization benchmarks, this setting lacks a natural formulation for general-purpose solvers such as OR-Tools, MOSEK, or Gurobi. Instead, triangulation-specific software such as TOPCOM is used for exact traversal of the flip graph [12]. In the CY setting, Batyrev’s construction and the Kreuzer-Skarke classification reduce a large computational pipeline to sampling fine, regular, and star triangulations (FRSTs) of 4D reflexive polytopes [4, 5]. CYT OOLS is a widely used computational and sampling tool for this pipeline [9]. Concurrent work, CYTransformer [30], adopts a constructive approach, training an encoder-decoder transformer to generate candidate triangulations one token at a time while relying on CYT OOLS to verify whether the output is an FRST. While this yields a useful learned generator, it inherits the structural difficulty noted above: generated sequences are not guaranteed to be valid triangulations or FRSTs. In the largest reported setting, with Hodge number h1,1 = 10, the FRST generation rate remains below 50%. In contrast, TriSearch does not generate full triangulations and then reject invalid outputs. Instead, it starts from a valid triangulation and navigates the flip graph via certified bistellar flips, ensuring that every move remains within the valid triangulation space by construction. Geometric Deep Learning. Geometric deep learning builds neural models for coordinate-based data, such as point clouds and meshes, while respecting underlying symmetries [31–34]. Graph neural networks (GNNs) are widely used to represent instances in combinatorial optimization [15], but most operate on pairwise graphs and do not fully exploit the underlying geometric structure. Complementary higher-order approaches, such as hypergraph and simplicial neural networks [35–37], model interactions beyond pairwise edges via faces and incidence relations. Triangulation optimization requires geometric encoding and higher-order local information, but the central issue is the action representation. Each action corresponds to a flippable circuit, whose realized subtriangulation carries combinatorial and geometric information. TriSearch reflects this structure through a global equivariant graph neural network (EGNN) encoder over the current triangulation and an actor that scores circuit-supported subtriangulations.
3
Problem Formulation and Preliminaries
3.1
Optimal Triangulations
A d-polytope P with vertex set V(P) = {p1 , . . . , pn } ⊂ Rd is the convex hull of the vertices, P = ConvHull({p1 , . . . , pn }) ⊂ Rd . We abbreviate the notation of vertex set to V whenever the context is clear. A d-simplex σ is a d-polytope with (d + 1) extreme points, e.g., a 2-simplex is a triangle and a 3-simplex is a tetrahedron. A triangulation is a collection of full-dimensional simplices △ = {σ1 , . . . , σk } that decompose a polytope: Definition 3.1 (Triangulation). Let P ⊂ Rd be a d-polytope with vertex set V(P). A triangulation △ = {σ1 , . . . , σk } of P is a decomposition of P into d-simplices with the following properties: • (Convex Hull Union) the union of all d-simplices equals P: ∪ki=1 σi = P. • (Intersection) the intersection of any two d-simplices is either empty or a shared face. • (Vertex Union) the vertices of the simplices are in V(P): ∪ki=1 V(σi ) ⊆ V(P). A triangulation is fine when the Vertex Union property holds with equality, i.e., ∪ki=1 V(σi ) = V(P), meaning it uses all vertices of the polytope. This condition is automatically met when V(P) is the set of extreme points of the convex hull, but non-trivial in settings such as FRST sampling, where the polytopes are reflexive polytopes containing interior vertices. A triangulation △ is regular if there exists a set of heights, such that we can lift the vertex set one dimension higher to Rd+1 , and projecting the lower envelope of the convex hull back to Rd recovers the simplices. For a fixed polytope P, let T (P) denote the space of all triangulations of P. The central optimization problem in this paper is to search this space for a triangulation that is best for a given objective. 3
Problem 3.2 (Optimal Triangulation). In a fixed dimension d, given a polytope P and an objective function f : T (P) → R, an optimal triangulation is defined as △⋆ ∈ argmin△∈T (P) f (△). 3.2
Navigating Triangulation Spaces via Flip Graphs
We will navigate the space of triangulations by local moves between triangulations implemented by local modifications defined as follows. Given a polytope P, a circuit Z is a minimal affinely dependent subset of V(P). For any circuit Z, the affine dependence has positive and negative parts by Radon partition [38], which induce two unique triangulations of ConvHull(Z), denoted by △+ (Z) and △− (Z). A circuit Z is flippable in △ if one of these two local triangulations is realized in △. Definition 3.3 (Flippable Circuit). Let △ be a triangulation of a d-polytope P. A circuit Z ⊂ V(P) is flippable in △ if either △+ (Z) ⊆ △ or △− (Z) ⊆ △. By convention, we denote by △+ (Z) the realized local subtriangulation in △, and by △− (Z) its replacement. A bistellar flip replaces the realized side by the other side as defined in Definition 3.4, with an illustrative example in 3D in Figure 1. Definition 3.4 (Bistellar Flip). Let Z be a flippable circuit in △, with the labels oriented so that △+ (Z) ⊆ △. The bistellar flip on Z replaces △+ (Z) by △− (Z), producing a new triangulation △′ := (△ \ △+ (Z)) ∪ △− (Z). When ConvHull(Z) has dimension below d, the circuit gives the core of the move. Given the current triangulation △ and a flippable circuit Z, the surrounding triangulation uniquely determines the common link L△ (Z). We therefore use Z ∈ F (△) to denote the full circuit-supported flip action, with this link suppressed. The notation △+ (Z) denotes the full-dimensional local subtriangulation removed from △, and △− (Z) denotes the full-dimensional replacement. This realized subtriangulation fixes the direction of the bistellar flip, since the same local move can be traversed in both directions. Appendix A unpacks the linked construction and the proof of the uniqueness. Through bistellar flips, the triangulation space becomes a flip graph. The flip graph G(P) is a bidirectional graph, whose node set is the set of all triangulations T (P), and the edge set is all the bistellar flips. For a triangulation △, we use F (△) to denote the set of flippable circuits, each understood as its full circuit-supported flip action. Its one-step neighborhood is N (△) = {Flip(△; Z) | Z ∈ F (△)}, where Flip(△; Z) is the triangulation obtained by applying the flip supported by Z. However, the flip graph does not need to be fully-connected when d > 2, there are known examples with disconnected flip graph in 6D [39]. 3.3
Triangulation Optimization via Reinforcement Learning
Finding an exact solution for a generic objective usually requires enumerating the whole triangulation space. This is infeasible beyond small instances because T (P) grows exponentially with |V(P)|. Instead of treating this space as an unstructured set, we leverage its local graph structure, and reformulate the problem into a reinforcement learning problem. The optimal triangulation problem can be viewed as search over G(P). Exact enumeration algorithms are reliable on small instances, but they scale poorly with the size of the flip graph. We formulate the search over the triangulation graph as a Markov Decision Process (MDP) M = {T (P), F (·), Rf , H, γ}. The state space T (P) is the vertex set of G(P), and the action space at a state △ is the state-dependent set of flippable circuits F (△) under the convention above. TriSearch does not materi- Figure 1: An illustration of bistellar flips alize G(P), so this MDP is a conceptual description of in 3D. the search problem. At each visited triangulation, geometric routines enumerate only the currently feasible outgoing flips F (△), and the policy chooses among those locally visible actions. The reward function Rf is defined by the improvement in the objective induced by a flip. For a minimization objective, we use Rf (△, Z) = f (△) − f (Flip(△; Z)), Z ∈ F (△), , the sign is reversed for maximization case. The horizon H specifies the number of flips per episode, and γ ∈ (0, 1) is the discount factor. Equivalently under the circuit-supported action notation, given 4
Shared Weights
Shared Weights
Figure 2: Architecture and training loop of TriSearch. The shared encoder Encκ maps the triangulation graph to node-level embeddings. The value head Vψ pools these into a scalar estimate of the state value, while the actor scores each circuit that supports a flip Zi ∈ F (△) using a simplex-level GNN and selects a flip via softmax. △ and a flippable circuit Z, the next state is uniquely determined as Flip(△; Z). The realized subtriangulation △+ (Z) specifies which direction of the bidirectional flip is applied. The reinforcement learning objective is to learn a policy πf that chooses flips at each state to maximize the expected discounted cumulative reward over the horizon H: "H−1 # X J (π) := E γ t r(△t , Zt ) , π ⋆ = argmax J (π). (1) π
t=0
The resulting policy is used to navigate the flip graph by selecting feasible bistellar flips from the current triangulation, with the aim of finding candidate triangulations that optimize the objective.
4
TriSearch
4.1
Policy
In this section, we present our policy architecture and optimization method for triangulation optimization. At a state △, the policy must select a circuit from the variable-size action set F (△) while conditioning on the full triangulation. We therefore propose a two-stage architecture illustrated in Figure 2. A shared encoder Encκ , shared by both actor and value networks, processes the entire triangulation and produces vertex-level representations, providing each vertex with global geometric context. The actor πθ then lifts these vertex embeddings to maximal simplices, propagates information over the d-simplicial graph, and outputs a score for each flippable circuit. A value head Vψ pools the embeddings and uses an MLP to estimate the state value for policy gradient training. For a triangulation △, let G(△) = (V(P), E(△)) denote the graph whose nodes are the vertices of the polytope and whose edges are the 1-skeleton of △. For a flippable circuit Z ∈ F (△), we let △+ (Z) be the realized local subtriangulation contained in △, and let △− (Z) be its replacement. Encoder. The triangulation problem is invariant under rigid motions of the polytope and does not depend on the ordering of the vertices. To respect these symmetries, the encoder employs an EGNN [32] to the full graph G(△). For each vertex pi ∈ V(P), the coordinates serve as the geometric input and a learnable projection initializes the hidden features. After LEnc layers, the encoder outputs vertex embeddings h⋆ and updated coordinates x⋆ . Actor. The actor turns geometric context into a flip decision. The shared encoder works at the vertex level because relative coordinates relations such as affine dependence naturally live on V(P). However, a feasible flip is not decided by one vertex or one edge. Instead, it replaces the realized local subtriangulation △+ (Z) by △− (Z). So the useful action context is carried by d-simplices and their adjacency relations. For this reason, we design the actor to leverage the geometric information extracted by the encoder to build features on maximal simplices and then pooling the features over △+ (Z) for each feasible circuit and its realized subtriangulation. Given the encoder embeddings h⋆ , the actor lifts the vertex embeddings to simplex level for each d-simplex σa ∈ △ by performing pooling over its vertices: ga(0) = MaxPool ({h⋆i : pi ∈ V(σa )}) . 5
(2)
The actor operates on the dual graph Ĝ(△) of the triangulation, where nodes are the d-simplices and two nodes are adjacent if the corresponding simplices share a (d − 1)-face. Simplicial convolution layers [36] are used to refine the features along this graph. Simplex embeddings ga⋆ are produced for each d-simplex σa ∈ △ after Lπ layers. This propagation lets the score for a flip depend on the local arrangement around △+ (Z), rather than only on the raw vertices in its circuit. Finally, for a feasible circuit Z ∈ F (△), the actor pools the refined simplex features over the realized local subtriangulation △+ (Z) and projects the result to one logit using a linear projection with learnable matrix W : zZ = MaxPool {ga(Lπ ) : σa ∈ △+ (Z)} , sθ (△, Z) = W ⊤ zZ . (3) The policy is the categorical distribution over the currently flippable circuits: πθ (Z | △) = P
exp(sθ (△, Z)) . exp(sθ (△, Z ′ ))
Z ′ ∈F (△)
The resulting distribution compares only currently flippable circuits, which matches the implicit flip-graph setting. The encoder supplies reusable geometric features for the whole triangulation, and the actor specializes them to the local simplicial structure that determines each action. The ablation in Table 1 supports this choice. Removing simplicial information substantially worsens the controlled 4D results across all three objectives. Value Function. We also use a light-weight value model Vψ , consisting of a pooling layer followed by an MLP ϕV . It takes the encoder node embeddings h⋆ , aggregates them into a global state representation, and outputs a scalar value estimate: Vψ (△) = ϕV (MaxPool(h⋆ )). 4.2
(4)
Policy Optimization
Our goal is to have a policy to perform optimization across polytopes with different combinatorial and geometric configurations. To this end, we train the policy over a distribution of polytopes to learn the reusable navigation behavior that can generalize beyond the training data. Each polytope induces its own Markov Decision Process (MDP) and the parameters of encoder, actor and value function are shared across these MDPs. For each training polytope, we maintain a small set of its triangulations V̂ ⊆ T (P) as initial state. In each episode, we initialize our policy at one of the initial triangulation from V̂ and generate rollouts. To prevent the model from overfitting and getting stuck at suboptimal trajectories, we add a count-based expansion bonus bt = βN (△t+1 )−1/2 , where N (△) is the visitation count of triangulation state △ in the discovered training graph for P, initialized to one. It encourages the agent to enlarge the observed portion of the implicit graph during training, as well as exploring new optimization strategies. Weighted Initial State Sampling. For training efficiency, we want to prevent TriSearch from repetitively sampling from a well-explored region [40], which would gather biased samples from a concentrated region of the graph, causing the policy to get stuck in sub-optimality. Hence, we further apply N (△0 )−1/2 to a weighted initial state sampling: the initial states with higher bonus represents under-explored area, which will be sampled with higher weights. Training. We train the encoder, actor, and value head jointly with PPO [41] using generalized advantage estimation (GAE) [42]. In each iteration, the current policy collects B rollout trajectories with transitions (△t , Zt , r̃t , △t+1 ), where r̃t = rt + bt includes the expansion bonus. We use the standard clipped policy loss and a squared value loss on Vψ (△t ) against the empirical return. Advantages are estimated by GAE with smoothing parameter λ. The full algorithm is given in Algorithm 1, and the details of the PPO can be found in Appendix B.3.
5
Experiments
We design our experiments around three questions about TriSearch. First, we ask whether the learned policies by TriSearch can solve diverse triangulation objectives in both 3D and 4D. Second, we ask whether the policy generalizes from small training polytopes to larger unseen ones, where the flip graph is exponentially larger. Third, we ask whether the same framework supports a real downstream pipeline beyond benchmark optimization. We address the first two questions in Section 5.1 through 6
Algorithm 1 TriSearch Training Input: Training polytopes D, Seed Triangulations V̂D = ∪P∈D V̂P , Objective f , Horizon H, Bonus coefficient β, Number of parallel environments N Initialize: Model Parameters (κ, θ, ψ), and Visitation counts NP (·) = 1 for training iteration j = 1, 2, . . . , J do (i) (i) Sample N initial triangulations: △0 ∼ V̂D proportional to weight NP (△0 )−1/2 Initialize rollout buffer: B ← ∅ for each rollout i and step t = 0, . . . , H − 1 do (i) Enumerate flippable circuits F (△t ) with TOPCOM (i) (i),⋆ (i) Apply Encκ to G(△t ) to obtain global representation: ht ← Encκ (G(△t )) (i),⋆ (i) (i) Pool ht on d-simplex level, apply πθ to select circuit to flip: Zt ∈ F (△t ) (i),⋆ Obtain the value estimate Vψ (ht ) (i) (i) (i) Flip the triangulation and obtain the next state: △t+1 ← Flip(△t ; Zt ) (i) (i) (i) (i) Compute the reward r and store the transition (△t , Zt , rt , △t+1 ) to rollout buffer B end for Update (κ, θ, ψ) using PPO with rollout buffer B end for
triangulation optimization against classical and learned local-search baselines. We address the third question in Section 5.2 by reusing the training pipeline for FRST discovery on 4D reflexive polytopes from the Kreuzer-Skarke list [5], and then applying the trained model to Calabi-Yau threefold sampling against the CYT OOLS samplers [9]. Our experiments were run with a RTX 2080 Ti GPU and Intel Xeon CPU. Throughout the experiments, all MLPs and GNNs have 64 hidden units in each layer, with 3 layers in encoder and value function and two layers for GNN actor, use SiLU activation function [43], and are trained using the Adam optimizer with a learning rate of 0.0001 [44]. The other detailed hyperparameters can be found in Appendix B.4. 5.1
Triangulation Optimization
In this setting, we aim to evaluate the capacity of TriSearch in triangulation optimization across various objectives, and verify its out-of-distribution generalization across polytope size. For each dimension d ∈ {3, 4}, we sample 130 training polytopes with 8 to 11 vertices and generate up to 2000 seed triangulations per polytope with TOPCOM. The detailed data generation procedure is provided in Appendix C.1. Evaluation uses held-out polytopes with 13 or 14 vertices, where the flip graph is exponentially larger than what the policy saw at training time. For each dimension, we train one policy per objective for three objectives: Min Simplices (number of d-simplices), Min Diameter (diameter of the dual graph), and Min Weight (total edge length). We compare against four classical heuristics-based baselines (G REEDY, DFS, B E FS, SA), which select the flip based on objective improvements, and the learned meta-heuristics controller NLS [25], which learns a state-conditioned acceptance rule on random flip proposals. For fair comparison, NLS shares the same EGNN architecture and the training hyperparameters as TriSearch. The more detailed descriptions of the baseline algorithms are deferred to Appendix C.2. Each method receives a budget of 500 flips from the same starting triangulations, and we report the average relative gap as: RelativeGap(A) =
ˆ A (P)) − f (△ref (P)) 1 X f (△ , |S| f (△ref (P)) P∈S
ˆ A (P) is the best triangulation found by A within the budget or from TOPCOM enumeration. where △ In 3D, the reference △ref (P) is the exact optimum found by exhaustive TOPCOM enumeration. In 4D, an exhaustive enumeration is not feasible at this size, we perform a 109 -steps enumeration with TOPCOM as an additional baseline, and use the best triangulation found across all algorithms tested as the reference △ref (P). Figure 3 reports the optimization curves on the held-out polytopes. Notably, TriSearch surpasses the 109 -steps TOPCOM reference on Min Simplices and Min Weight at both |V| = 13 and |V| = 14 within 500 flips in 4D. TriSearch largely closes the gap within around 100 flips on every objective and 7
Figure 3: Triangulation optimization under a 500-flip budget. It shows the mean relative gap and standard deviation over evaluation polytopes. The black dashed line is exact optimality in 3D, and the gold dashed line is 109 TOPCOM enumeration used as an external 4D baseline. reaches an average gap of 0.16% in 3D and 1.43% in 4D, against 8.97% and 9.09% for the next-best baseline NLS, where the detailed aggregated result tables can be found in Appendix D. Ablation study. We ablate the actor on the shared 4D evaluation splits with |V| = 13 and |V| = 14. The full TriSearch model uses an SNN actor to score each flip from its local subtriangulation. The EGNN variant removes simpli- Table 1: Controlled 4D ablation at 500 flips. Entries are average cial information, and the Pooling + relative gap with standard error (%, ↓). MLP variant removes subtriangulaMin Simp. Min Diameter Min Weight tion structure altogether. Table 1 re- Variant 0.185±0.183 4.000±1.265 0.137±0.052 ports the average relative gap over 40 TriSearch (SNN) w/o simplicial information (EGNN) 8.977±2.213 12.500±1.531 3.112±0.660 evaluation polytopes for each objec- w/o subtriangulation (Pooling + MLP) 15.121±2.780 14.167±1.558 6.992±0.655 tive. The reference includes the 4D TOPCOM enumeration value and every 500-flip method in the main and ablation result files. Both removals increase the relative gap across all three objectives, indicating the necessity of d-simplicial information when making a flip decision. 5.2
Calabi-Yau Threefold Sampling
We next evaluate the framework on CY threefold sampling. At the geometry level, our task is to find Fine, Regular, Star triangulations (FRSTs) of 4D reflexive lattice polytopes, then use the Batyrev construction to map each FRST to a CY threefold, where different FRSTs may yield topologically equivalent threefolds.1 The practical goal is therefore to discover as many distinct threefold classes as possible. We formulate this as a nearby-FRST discovery task from a random starting triangulation with sparse binary reward. We train the policy to start from a regular triangulation induced by random heights and may take at most 50 flips to locate nearby target triangulations. It succeeds and receives a positive reward +1 when it reaches a fine regular triangulation, after which standard post-processing 1 Recall that a triangulation is fine if it uses every lattice point, regular if it can be induced by a lifting, and star if all
maximal simplices contain the origin.
8
(a)
(b)
(c)
(d)
Figure 4: CY threefold sampling experiments. (a) Success rate of locating a nearby FRST within a 50-flip budget on unseen polytopes with h1,1 ∈ {4, 6, . . . , 16}. Error bars show standard deviations across 20 polytopes. (b, c) Cumulative numbers of unique FRSTs (b) and CY threefolds (c) discovered over sampling time at h1,1 = 16. The dashed line represents that the stopping criterion was met. TriSearch stopped at the maximum iteration, while FRST FAST S AMPLER was stopped by hitting max retries. (d) Fraction of CY threefold classes discovered for h1,1 ∈ {4, 8, 12, 16}. Labels give the discovered class count and the percentage. closes it into a star triangulation [45]. We train TriSearch on small reflexive polytopes with Hodge number h1,1 = 3, and evaluate on 1000 random triangulations of unseen polytopes with h1,1 from 4 to 16. Figure 4a shows that TriSearch maintains a perfect success rate across the range, while TOPCOM breadth-first search and R ANDOM WALK degrade quickly as h1,1 grows. We then turn the trained FRST locator into a CY sampler. In each iteration, we draw a random height vector in R|V(P)| from a diagonal Gaussian distribution, construct the induced regular triangulation through lifting, and run TriSearch to search for a nearby FRST. Sampling efficiency is evaluated on 10 polytopes each for h1,1 ∈ {4, 8, 12, 16}. We compare against the widely used software CYT OOLS [9, 45], including FRST FAST S AMPLER and MCMC, under the same budgeted regime. Each sampler is assigned at most 300 seconds or 1024 iterations per polytope, and sampling stops after 50 consecutive retries without discovering a new FRST. Figures 4b and 4c show the sampling count at h1,1 = 16. TriSearch exhibits nearly linear FRST growth and discovers significantly more distinct CY classes than baseline samplers. MCMC also continues to discover new FRSTs and CY classes, but suffers from low sampling efficiency, while FRST FAST S AMPLER initially achieves very high FRST sampling speed before rapidly decaying and hitting max retries. Figure 4d aggregates the final class fractions across h1,1 ∈ {4, 8, 12, 16}. TriSearch recovers all known classes at h1,1 = 4 and h1,1 = 8, and outperforms both CYT OOLS samplers at h1,1 = 12 and h1,1 = 16.
6
Conclusion
We introduced TriSearch, a reinforcement-learning framework for optimizing and exploring triangulations of polytopes in any fixed dimension, where the key design element is a circuit-supported subtriangulation action representation: geometric routines enumerate valid bistellar flips, and the policy learns how to rank them using both global triangulation context and the realized local subtriangulation. TriSearch outperforms all the baselines under the same budget across 3D and 4D triangulation optimization, and outperforms the widely used samplers in CYT OOLS across 4D CY threefold sampling task. These results support learned flip-graph navigation as an effective approach to combinatorial geometry problems whose search spaces are too large to enumerate, yet whose local moves are mathematically well formulated. Similar high-level structure also appears in phylogenetic tree search [46], rhombus tiling [47], and unknotting problems [48], where the feasible space is too large to enumerate but local moves expose rich mathematical structure. Despite the strong empirical performance of TriSearch, our current work has several limitations: First, the method relies on a geometric routine to enumerate flippable circuits, which is currently difficult to parallelize; future work could investigate replacing this component with a neural network. Second, the method does not currently address situations in which the flip graph is disconnected. Third, in the CY sampling application, the random starting triangulations are sampled uniformly. Future work could instead learn the distribution of FRSTs in height space and sample more strategically. 9
Acknowledgments This project has been supported by NSF grant DMS-2522495. GM was partially supported by DARPA AIQ grant HR00112520014, NSF grants DMS-2145630, CCF-2212520, DFG SPP 2298 grant 464109215, and BMFTR in DAAD project 57616814 (SECAI).
10
References [1] Pascal Jean Frey and Paul-Louis George. Mesh generation: application to finite elements. Iste, 2007. [2] Marshall Bern and David Eppstein. Mesh generation and optimal triangulation. In Computing in Euclidean geometry, pages 47–123. World Scientific, 1995. [3] Jonathan Richard Shewchuk. Delaunay refinement algorithms for triangular mesh generation. Computational Geometry, 22(1–3):21–74, 2002. [4] Victor V Batyrev. Dual polyhedra and mirror symmetry for calabi-yau hypersurfaces in toric varieties. arXiv preprint alg-geom/9310003, 1993. [5] Maximilian Kreuzer and Harald Skarke. Complete classification of reflexive polyhedra in four dimensions. arXiv preprint hep-th/0002240, 2000. [6] Herbert Edelsbrunner, Franco P Preparata, and Douglas Brent West. Tetrahedrizing point sets in three dimensions. In International Symposium on Symbolic and Algebraic Computation, pages 315–331. Springer, 1988. [7] Alexander Below, Jesús A. De Loera, and Jürgen Richter-Gebert. The complexity of finding small triangulations of convex 3-polytopes. Journal of Algorithms, 50(2):134–167, 2004. [8] Wolfgang Mulzer and Günter Rote. Minimum-weight triangulation is NP-hard. Journal of the ACM (JACM), 55(2):1–29, 2008. [9] Mehmet Demirtas, Andres Rios-Tascon, and Liam McAllister. Cytools: a software package for analyzing calabi-yau manifolds. arXiv preprint arXiv:2211.03823, 2022. [10] Tamal Krishna Dey. On counting triangulations in d dimensions. Computational Geometry, 3(6):315–325, 1993. [11] Vadakkedathu T Rajan. Optimality of the delaunay triangulation in rd. In Proceedings of the seventh annual symposium on Computational geometry, pages 357–363, 1991. [12] Jörg Rambau. Topcom: Triangulations of point configurations and oriented matroids. In Mathematical software, pages 330–340. World Scientific, 2002. [13] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d’horizon. European Journal of Operational Research, 290(2):405–421, 2021. [14] Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, 134:105400, 2021. [15] Quentin Cappart, Didier Chételat, Elias B Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. Journal of Machine Learning Research, 24(130):1–61, 2023. [16] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in neural information processing systems, 28, 2015. [17] Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940, 2016. [18] Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475, 2018. [19] Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, volume 31, 2018. 11
[20] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. POMO: Policy optimization with multiple optima for reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pages 21188–21198, 2020. [21] Jim Ruppert and Raimund Seidel. On the difficulty of triangulating three-dimensional nonconvex polyhedra. Discrete & Computational Geometry, 7(3):227–253, 1992. [22] Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for solving routing problems. IEEE Transactions on Neural Networks and Learning Systems, 33(9):5057–5069, 2021. [23] Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. In Advances in Neural Information Processing Systems, volume 32, 2019. [24] Thomas D. Barrett, William R. Clements, Jakob N. Foerster, and Alex I. Lvovsky. Exploratory combinatorial optimization with reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3243–3250, 2020. [25] Jonas K. Falkner, Daniela Thyssens, Ahmad Bdeir, and Lars Schmidt-Thieme. Learning to control local search for combinatorial optimization. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases (ECML PKDD), pages 361–376. Springer, 2022. [26] Jesús De Loera, Jörg Rambau, and Francisco Santos. Triangulations: structures for algorithms and applications. Springer Science & Business Media, 2010. [27] Israel M Gelfand, Mikhail M Kapranov, and Andrei V Zelevinsky. A-discriminants. In Discriminants, resultants, and multidimensional determinants, pages 271–296. Birkhäuser Boston, Boston, MA, 1994. [28] Charles L Lawson. Transforming triangulations. Discrete mathematics, 3(4):365–372, 1972. [29] Udo Pachner. P.L. homeomorphic manifolds are equivalent by elementary shellings. European journal of Combinatorics, 12(2):129–145, 1991. [30] Jacky HT Yip, Charles Arnal, François Charton, and Gary Shiu. Transforming calabiyau constructions: Generating new calabi-yau manifolds with transformers. arXiv preprint arXiv:2507.03732, 2025. [31] Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104.13478, 2021. [32] Vıctor Garcia Satorras, Emiel Hoogeboom, and Max Welling. E(n) equivariant graph neural networks. In International conference on machine learning, pages 9323–9332. PMLR, 2021. [33] Yi-Lun Liao and Tess Smidt. Equiformer: Equivariant graph attention transformer for 3d atomistic graphs. arXiv preprint arXiv:2206.11990, 2022. [34] Yi-Lun Liao, Brandon Wood, Abhishek Das, and Tess Smidt. Equiformerv2: Improved equivariant transformer for scaling to higher-degree representations. arXiv preprint arXiv:2306.12059, 2023. [35] Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. Hypergraph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 3558–3565, 2019. [36] Stefania Ebli, Michaël Defferrard, and Gard Spreemann. Simplicial neural networks. In Topological Data Analysis and Beyond workshop at NeurIPS, 2020. [37] Hanrui Wu, Andy Yip, Jinyi Long, Jia Zhang, and Michael K Ng. Simplicial complex neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(1):561–575, 2023. [38] Johann Radon. Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten. Mathematische Annalen, 83(1):113–115, 1921. 12
[39] Francisco Santos. Non-connected toric Hilbert schemes. Mathematische Annalen, 332(3):645– 665, 2005. [40] Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. Go-explore: a new approach for hard-exploration problems. arXiv preprint arXiv:1901.10995, 2019. [41] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017. [42] John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. Highdimensional continuous control using generalized advantage estimation. arXiv preprint arXiv:1506.02438, 2015. [43] Prajit Ramachandran, Barret Zoph, and Quoc V Le. Searching for activation functions. arXiv preprint arXiv:1710.05941, 2017. [44] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014. [45] Mehmet Demirtas, Liam McAllister, and Andres Rios-Tascon. Bounding the Kreuzer-Skarke landscape. Fortschritte der Physik, 68(11-12):2000086, 2020. [46] Panna Lipták and Attila Kiss. Constructing unrooted phylogenetic trees with reinforcement learning. Studia Universitatis Babeş-Bolyai Informatica, 66(1):37–53, 2021. [47] Frédéric Chavanon and Eric Rémila. Rhombus tilings: decomposition and space structure. Discrete & Computational Geometry, 35(2):329–358, 2006. [48] Ali Shehper, Anibal M. Medina-Mardones, Lucas Fagan, Bartłomiej Lewandowski, Angus Gruen, Yang Qiu, Piotr Kucharski, Zhenghan Wang, and Sergei Gukov. What makes math problems hard for reinforcement learning: a case study. arXiv preprint arXiv:2408.15332, 2024.
13
A
Radon Partitions and Circuit Flips
This appendix records the standard construction behind the two local triangulations used in Definition 3.4. Let P have vertex set V and let Z ⊂ V be a circuit. When forming links and joins, we identify a simplex with its vertex set. Since Z is minimally affinely dependent, there is an affine dependence relation, unique up to nonzero scaling, X X λi pi = 0, λi = 0, pi ∈Z
pi ∈Z
where all coefficients are nonzero and both signs occur. The signs define the Radon partition Z − = {pi ∈ Z : λi < 0},
Z + = {pi ∈ Z : λi > 0}, and the two parts have intersecting convex hulls:
ConvHull(Z + ) ∩ ConvHull(Z − ) ̸= ∅. Let r = dim ConvHull(Z). The circuit therefore admits two sets of maximal r-simplices in ConvHull(Z): + △+ core (Z) := {Z \ {p} : p ∈ Z }, − △− core (Z) := {Z \ {p} : p ∈ Z }.
We write these cores by their maximal faces, following the convention in the main text. Whenever lower-dimensional faces are needed, we pass to the corresponding simplicial closure. Changing the sign of the affine dependence swaps the + and − labels. When r = d, the core triangulations are full-dimensional. This is the general-position case. We set − L△ (Z) = {∅}, and the bistellar flip directly replaces △+ core (Z) by △core (Z). When r < d, the circuit core must be embedded into the surrounding triangulation through a link. Since △ is written by its maximal simplices, let △ denote its simplicial closure: △ = {F ⊆ V(P) : F ⊆ V(σ) for some σ ∈ △}. For a face F ∈ △, its link in △ is Lk△ (F ) = {G ∈ △ : G ∩ F = ∅, F ∪ G ∈ △}. The link lives in △ and uses vertices outside F . For a flippable circuit, orient the signs so that every maximal face in △+ core (Z) lies in △. The common link is \ L△ (Z) = Lk△ (Z \ {p}). p∈Z +
Equivalently, every maximal face Z \ {p} with p ∈ Z + has the same link L△ (Z). This link lives on vertices outside Z and has maximal faces of dimension d − r − 1. Joining it with the r-dimensional circuit core gives d-simplices. For two collections of faces K and L on disjoint vertices, their join is K ∗ L = {F ∪ G : F ∈ K, G ∈ L}. When we write △± core (Z) ∗ L△ (Z) as part of △, we mean the set of maximal d-simplices obtained by taking F ∈ △± core (Z) and G a maximal face of L△ (Z). The notation in the main text suppresses the link by writing the full-dimensional local subtriangulations as △− (Z) = △− core (Z) ∗ L△ (Z).
△+ (Z) = △+ core (Z) ∗ L△ (Z),
The full bistellar flip supported by Z replaces the first joined complex by the second. At the level of maximal d-simplices, it produces △′ = △ \ △+ (Z) ∪ △− (Z). This recovers the direct replacement in Definition 3.4. 14
Proposition A.1 (Uniqueness of the flip supported by a fixed circuit). Let △ be a geometric triangulation of P with point configuration V(P). Let Z ⊂ V(P) be a circuit. If △2 and △3 are both obtained from △ by bistellar flips supported on Z, then △2 = △3 . Equivalently, for fixed △ and fixed Z, there is at most one successor triangulation Flip(△; Z). Proof. Suppose △2 and △3 are two successors obtained by flips supported on Z. Without loss of generality, orient the Radon partition so that the first flip removes the + side of Z. Thus there is a link L2 such that, at the level of maximal d-simplices, △2 = △ \ (△+ (Z) ∗ L ) ∪ △− 2 core core (Z) ∗ L2 . We first show that the second flip must also remove the + side. Assume the opposite. Then the second flip removes the − side for some link L3 . Because ∅ belongs to every link, this would imply − that both △+ core (Z) and △core (Z) are contained in △. We show that this is impossible in a geometric triangulation. Choose p ∈ Z + and q ∈ Z − . Then Z \ {p} is a maximal face of △+ core (Z), while Z \ {q} is a maximal face of △− core (Z). The affine dependence on the circuit gives a Radon point x ∈ ConvHull(Z + ) ∩ ConvHull(Z − ). Thus x ∈ ConvHull(Z \ {p}) ∩ ConvHull(Z \ {q}). However, x ∈ / ConvHull(Z \ {p, q}). Otherwise x would have two affine representations in the affinely independent set Z \ {q}. One uses Z + with a positive coefficient on p, and the other uses Z \ {p, q} with coefficient 0 on p. This contradicts that every proper subset of a circuit is affinely independent. Therefore the two simplices Z \ {p} and Z \ {q} do not meet in their common face. They cannot both be faces of △. Thus the second flip cannot remove the − side. Therefore both flips remove the realized core △+ core (Z). By the linked construction above, the link is then uniquely determined by △ and Z: \ L2 = L3 = L△ (Z) = Lk△ (Z \ {p}). p∈Z +
The removed joined complexes are identical, and the inserted joined complexes are identical. Hence △2 = △3 .
B
Architecture and Training Details
B.1
EGNN Encoder Details
The encoder applies EGNN message passing to the graph G(△) induced by the 1-skeleton of the current triangulation. For each vertex pi ∈ V(P), the initial coordinate and hidden feature are (1)
xi
(1)
:= pi ,
hi
:= W pi .
At layer ℓ, the encoder computes an edge message for each neighbor j ∈ N (i): (ℓ) (ℓ) (ℓ) (ℓ) mij = ϕe hi , hj , ∥xi − xj ∥2 . It then updates the coordinate and hidden feature by X 1 (ℓ+1) (ℓ) xi = xi + |N (i)|
(ℓ)
(ℓ)
xi − x j
ϕx (mij ),
j∈N (i)
(ℓ+1)
hi
X (ℓ) (ℓ) = hi + ϕh hi , mij . j∈N (i)
Here ϕe , ϕx , and ϕh are MLPs. After LEnc layers, the encoder outputs vertex embeddings h⋆ and updated coordinates x⋆ . 15
B.2
Circuit-Supported Action Scoring
The actor scores circuit-supported flips through their realized full-dimensional local subtriangulations. It first lifts vertex features to maximal simplices. For each σa ∈ △, it pools the encoder embeddings of the vertices in that simplex: ga(0) = MaxPool ({h⋆i : pi ∈ V(σa )}) . Collecting these features gives G(0) ∈ RM ×m , where each row corresponds to one maximal simplex in △ = {σ1 , . . . , σM }. The actor then propagates information over maximal simplices rather than only over vertices. This step gives each action score access to how the simplices in △+ (Z) meet nearby simplices through shared facets. Let Bd be the oriented boundary matrix from d-simplices to (d − 1)-faces. The top-degree down Laplacian is Ld = Bd⊤ Bd . It connects two maximal simplices when they share a facet. In the implementation, we normalize this e d . We sparse Laplacian by a global row-sum scale for numerical stability and denote the result by L use the simplicial propagation rule proposed by Ebli et al. [36]. The Chebyshev recursion is defined by e d G, e d Tk−1 (G) − Tk−2 (G) k ≥ 2. T0 (G) = G, T1 (G) = L Tk (G) = 2L Each action-scoring propagation layer updates simplex features by ! KX act −1 (ℓ) (ℓ+1) (ℓ) (ℓ) G =σ Tk (G )Θk + b , k=0
where the final layer omits σ. For a circuit-supported flip Z ∈ F (△), the actor pools features over the realized full-dimensional local subtriangulation △+ (Z): zZ = MaxPool {ga(Lπ ) : σa ∈ △+ (Z)} , sθ (△, Z) = W ⊤ zZ . The policy normalizes these logits across the current feasible action set F (△). B.3
PPO Training Objective
For each rollout transition, the training reward is r̃t = rt + bt , where bt is the expansion bonus from Algorithm 1. The PPO probability ratio is πθ (Zt | △t ) ρt (θ) := . πθold (Zt | △t ) Generalized advantage estimation uses the temporal-difference residual δt = r̃t + γVψ (△t+1 ) − Vψ (△t ), with the bootstrap term omitted at the episode horizon. The advantage estimate is H−1−t X Ât = (γλ)h δt+h . h=0
The clipped PPO policy loss is h i Lpolicy (θ, κ) = −Et min ρt (θ)Ât , clip(ρt (θ), 1 − ϵ, 1 + ϵ)Ât . The value loss is Lvalue (ψ, κ) = Et
Vψ (△t ) − R̂t
2
,
where R̂t is the empirical return. The negative entropy loss is X Lentropy (θ, κ) = Et πθ (Z | △t ) log πθ (Z | △t ) . Z∈F (△t )
The parameters (θ, ψ, κ) are updated by minimizing L = Lpolicy (θ, κ) + αval Lvalue (ψ, κ) + αent Lentropy (θ, κ), where αval is the value coefficient and αent is the entropy coefficient, whose value is provided in Appendix B.4 16
B.4
Model and Training Hyperparameters
Table 2 reports the architecture and PPO settings used in the triangulation optimization experiments. We largely follow the conventional hyperparameters used in [41, 32, 36]. Table 2: Model and PPO hyperparameters used for TriSearch and NLS. NLS uses the same encoder and PPO setup as TriSearch, but replaces direct feasible-flip scoring with pooling followed by an MLP acceptance head. Group
Architecture
PPO
NLS
Setting
Value
EGNN encoder depth EGNN hidden size Action-scoring propagation depth Chebyshev order Value head Actor head Actor and value MLP width
3 message-passing layers 64 2 layers 3 3-layer MLP Linear 64
Rollout length Parallel training states PPO epochs per update PPO Iterations Learning rate Clip parameter Discount factor GAE parameter Value coefficient Entropy coefficient
50 flips 128 for 3D, 512 for 4D 1 2000 10−4 0.1 0.99 0.95 0.5 0.001
Encoder Policy head Training
same EGNN encoder as TriSearch pooling followed by a 3-layer MLP of width 64 same PPO settings as TriSearch
C
Experimental Details
C.1
Synthetic Polytope Data
Algorithm 2 gives the synthetic data-generation procedure used in the triangulation optimization experiments. The purpose of the isomorphism check is to avoid filling the train or test set with many coordinate realizations of the same combinatorial type. For each accepted training polytope, we use TOPCOM to enumerate up to 2000 triangulations. These triangulations form the seed set V̂P used as initial states during training. If fewer than 2000 triangulations are available, we keep all enumerated triangulations. The evaluation dataset follows the same generation procedure as described in Algorithm 2 C.2
Baseline Algorithm Details
All search baselines operate on the same feasible flips enumerated by the geometric routines. G REEDY chooses the flip with the largest immediate objective improvement. DFS performs depth-first search while prioritizing unvisited neighbors with better immediate objective values. Best First Search (B E FS) is the best-first frontier baseline reported in the optimization tables. S IMULATED A NNEALING samples flips according to a probabilistic rule based on immediate objective improvement. NLS adapts the acceptance-only NeuroLS controller to triangulation optimization. The proposal distribution is the same as S IMULATED A NNEALING, while the learned controller decides whether to accept the proposed move. Its encoder architecture matches TriSearch, and its policy head follows NeuroLS by pooling the encoded state and applying an MLP. The expanded baseline definitions are given in the per-method paragraphs below. All search methods start from the same initial triangulations as TriSearch and receive a 500-flip budget. TOPCOM is used for exact enumeration in 3D and as a 100M-enumeration external baseline in 4D. The nearby-FRST baselines use the same initial regular triangulations and the same 50-flip budget as TriSearch. 17
Algorithm 2 d-Polytope Data Generation Initialize: number of sampled points n, dataset D ← ∅, target dataset size K repeat i.i.d. Sample v1 , v2 , . . . , vn ∼ N (0, Id ) P ← ConvHull({v1 , v2 , . . . , vn }) Set exist ← 0 for P ′ ∈ D do if P ′ is combinatorially isomorphic to P then exist ← 1 end if end for if exist = 0 then D ← D ∪ {P} end if until |D| = K
G REEDY. At each state △, G REEDY enumerates the feasible flips F (△). It evaluates the resulting objective f (Flip(△; Z)) for every Z ∈ F (△) and applies the flip with the largest immediate decrease. If every feasible flip strictly increases f , G REEDY applies the least-bad flip and continues. There is no memory and no backtracking, so the trajectory is determined entirely by the local objective landscape. DFS. At each state, DFS expands the current triangulation by enumerating F (△). It sorts the resulting neighbors by their immediate objective value and pushes the unvisited ones onto a stack with the most promising on top. The next move pops the top of the stack and applies the corresponding flip. When a branch has no unvisited neighbor with an improving objective value, DFS backtracks via the stack and continues from the previous unfinished branch. B E FS. At each state, B E FS maintains a global priority queue of all discovered triangulations, keyed by their objective value. It pops the lowest-objective state and enumerates its feasible flips. The unvisited neighbors are inserted into the queue with their values. The next pop expands whichever discovered state currently has the lowest value, even if it is not adjacent to the most recent one. S IMULATED A NNEALING. At each state, S IMULATED A NNEALING samples a feasible flip Z ∼ Uniform(F (△)). It computes the objective change ∆ = f (Flip(△; Z)) − f (△) and accepts the flip with probability min(1, exp(−∆/Tt )). The temperature Tt decays over the budget, so non-improving moves are common early in the run and rare near the end. NLS.
At each state, NLS samples a candidate flip from the same proposal distribution as S IMU LATED A NNEALING. A learned policy then decides whether to accept it. The shared EGNN encoder embeds the current triangulation, and the embeddings are pooled into a global state representation. A 3-layer MLP then outputs the acceptance probability. The proposed flip is applied with this probability and otherwise rejected, in which case the state remains △. The implementation is adapted from the official repo : https://github.com/jokofa/NeuroLS/tree/master. TOPCOM. At each state, TOPCOM performs breadth-first traversal of the flip graph by enumerating the feasible flips and adding the resulting triangulations to the queue. It tracks visited states to avoid cycles. In 3D, this enumerates the entire flip graph and gives the exact optimum used as the gap reference. In 4D, the search is capped at 100M expansions and is reported only as an external sanity check. In nearby-FRST discovery, TOPCOM runs the same BFS from the initial regular triangulation and stops as soon as an FRST is reached. The implementation is from https://github.com/passagemath/upstream-topcom. R ANDOM WALK. At each state, R ANDOM WALK enumerates the feasible flips and applies one chosen uniformly at random. There is no objective awareness and no memory across steps, so the trajectory is determined entirely by the local geometry of the flip graph. 18
FRST FAST S AMPLER. At each iteration, FRST FAST S AMPLER (the CYT OOLS random_triangulations_fast_generator) draws a random height vector h ∈ R|V(P)| . It constructs the regular triangulation induced by h and asks CYT OOLS whether the result is an FRST. New iterations are drawn until the retry stopping rule fires after 50 consecutive iterations without a new FRST. The implementation is directly from https://cy.tools/. MCMC. At each iteration, MCMC (the CYT OOLS random_triangulations_fair_generator) advances a Markov chain over regular triangulations whose stationary distribution approximates the uniform distribution over FRSTs. The chain proposes a perturbation of the current height vector and accepts it via the CYT OOLS fairness rule. Sampling stops under the same 50-retry rule as FRST FAST S AMPLER. The implementation is directly from https://cy.tools/. NLS is the feasible NLS Acceptance variant for this action space. The full NLS design includes policy heads for choosing local-search components that do not map directly to feasible bistellar flips in triangulation optimization. We therefore keep the S IMULATED A NNEALING proposal mechanism and learn only whether to accept the proposed move. This makes the comparison test learned acceptance against the direct flip-ranking policy used by TriSearch. For sparse-reward nearby-FRST discovery, G REEDY, DFS, B E FS, and S IMULATED A NNEALING are not used. Their rules require one-step objective differences, while nearby-FRST discovery gives a binary success signal. C.3
Sparse-Reward FRST Details
For nearby-FRST discovery, TriSearch is trained on 200 reflexive polytopes with h1,1 = 3. Evaluation uses unseen reflexive polytopes with h1,1 ∈ {4, 6, 8, 10, 12, 14, 16}. For each Hodge number, we sample 20 polytopes and 50 random regular triangulations per polytope, giving 1000 initial states. Each method receives a 50-flip budget from each initial triangulation. The baselines are R ANDOM WALK, which samples uniformly from feasible flips, and TOPCOM, which performs breadth-first flip-graph traversal from the same initial state. Local-improvement baselines are omitted because the reward is binary. For CY threefold sampling, each TriSearch iteration samples a random height vector in R|V(P)| , constructs the associated regular triangulation, and searches for a nearby FRST with the trained policy. We compare against the CYT OOLS random_triangulations_fast_generator and random_triangulations_fair_generator, reported as FRST FAST S AMPLER and MCMC. Sampling is evaluated on 10 reflexive polytopes for each h1,1 ∈ {4, 8, 12, 16} and stops for a polytope after 50 consecutive retries without finding a new FRST. Figure 4d reports the final fraction of known CY threefold classes discovered for those evaluated polytopes; the numerator is the number discovered by the method and the denominator is the known total for that setting.
D
Complementary Optimization Results
Tables 3 and 4 report the numerical values for the 500-flip optimization comparison. Each entry is the mean relative gap with standard error. The average row aggregates per-instance gaps over all listed objectives and evaluation sizes. Lower is better.
19
Table 3: Relative gap (%, ↓) after 500 bistellar flips on unseen simplicial polytopes in 3D. The reference is the exact optimum found by exhaustive enumeration. Bold and underlined entries mark the best and second-best 500-flip search methods. Relative Gap @ 500 (%, ↓)
Evaluation Setup d |V| Objective
G REEDY
DFS
B E FS
SA
NLS
Ours
13
Min Simplices 23.11±2.69 6.41±0.95 2.14±0.62 6.64±0.86 13.00±2.35 0.13±0.13 Min Diameter 14.30±2.20 11.50±2.12 16.70±2.19 12.30±2.11 3.90±1.27 0.50±0.49 Min Weight 10.56±0.85 7.18±0.69 3.54±0.58 11.42±0.92 8.12±0.99 0.13±0.05
14
Min Simplices 23.51±2.50 12.07±2.05 6.17±1.30 12.60±1.51 14.25±2.18 0.00±0.00 Min Diameter 15.40±1.82 16.50±1.10 20.60±1.71 18.20±1.12 6.10±1.32 0.00±0.00 Min Weight 11.78±0.89 8.87±0.79 6.21±0.76 11.87±0.98 8.43±0.92 0.19±0.08
3
Average
16.44±0.85 10.42±0.61
9.23±0.67
12.17±0.57
8.97±0.69
0.16±0.09
Table 4: Relative gap (%, ↓) after 500 bistellar flips on unseen simplicial polytopes in 4D. The TOPCOM result is obtained by 109 (100M) enumeration, and the reference is the best value found between this value and the 500-flip search methods. Bold and underlined entries mark the best and second-best 500-flip search methods. Relative Gap @ 500 (%, ↓)
Evaluation Setup d |V| Objective
100M TOPCOM
G REEDY
DFS
B E FS
SA
NLS
Ours
13
Min Simplices Min Diameter Min Weight
2.41±0.94 1.00±0.97 3.18±0.61
17.25±4.68 20.01±6.30 19.24±5.17 6.93±2.14 11.29±3.12 0.00±0.00 20.00±0.00 20.00±0.00 20.00±0.00 19.00±0.97 13.00±2.13 3.00±1.60 4.98±1.24 5.44±1.47 4.49±1.20 3.10±0.82 2.50±0.70 0.13±0.07
14
Min Simplices Min Diameter Min Weight
14.50±2.60 4.00±1.79 4.49±0.60
55.14±7.56 22.74±4.62 22.55±4.92 14.24±3.32 10.89±2.79 0.37±0.36 28.67±2.80 23.00±3.02 20.33±3.02 16.67±2.92 14.67±2.37 5.00±1.94 13.10±1.67 5.42±1.04 5.25±1.04 2.10±0.64 2.22±0.60 0.10±0.07
Average
4.93±0.72
23.19±2.16 16.10±1.59 15.31±1.48 10.34±1.04
4
20
9.09±1.00
1.43±0.46