Technical Summary: TriSearch

Problem Formulation

The paper addresses the optimization of triangulations for a $d$-dimensional polytope $P$. A triangulation decomposes $P$ into $d$-simplices meeting only at shared faces. The space of all triangulations, $\mathcal{T}(P)$, is exponentially large, growing as $2^{O(|V(P)|\lceil d/2 \rceil)}$. Many natural objectives over this space, such as minimizing the number of simplices or total edge length, are NP-hard for $d \geq 2$.

The search space is structured as a flip graph $\mathcal{G}(P)$, where nodes are triangulations and edges correspond to bistellar flips. A bistellar flip is a local move that replaces a realized local subtriangulation supported by a circuit (a minimal affinely dependent set of vertices) with an alternative triangulation of the same vertex set. The challenge lies in navigating this graph: the set of feasible actions (flippable circuits) is state-dependent and changes after every move, making standard neural combinatorial optimization difficult as the action space is not fixed.

Methodology: TriSearch

The authors propose TriSearch, a reinforcement learning (RL) framework that treats triangulation optimization as a search on an implicit flip graph.

1. Problem Reformulation

The problem is modeled as a Markov Decision Process (MDP):

• State: A complete triangulation $\Delta$.
• Action: A currently feasible bistellar flip $Z \in \mathcal{F}(\Delta)$.
• Reward: The improvement in the objective function $f$ induced by the flip ($R = f(\Delta) - f(\text{Flip}(\Delta; Z))$).
• Horizon: A fixed number of flips per episode.

Crucially, the framework does not ask the policy to learn geometric validity. Instead, a geometric routine (based on TOPCOM) enumerates all valid local moves (flippable circuits) at the current state. The learned policy's role is to rank these valid moves to identify which one leads to long-range optimization.

2. Circuit-Supported Action Representation

To handle the variable and state-dependent action space, TriSearch introduces a novel action representation. Each feasible action is encoded by:

1. The supporting circuit $Z$.
2. The realized local subtriangulation $\Delta^+(Z)$ contained in the current triangulation.

This representation encodes both the certificate of admissibility and the specific local geometry being replaced. Because circuits are defined intrinsically, this representation is dimension-agnostic and supports different flip arities.

3. Neural Architecture

The policy uses a two-stage architecture (Figure 2):

• Global Encoder: An Equivariant Graph Neural Network (EGNN) processes the 1-skeleton of the triangulation graph $G(\Delta)$. It produces vertex-level embeddings $h^*$ that capture global geometric context while respecting rigid motion symmetries.
• Actor (Action Scorer): The actor lifts vertex embeddings to the level of maximal $d$-simplices. It operates on the dual graph of the triangulation (where nodes are simplices) using Simplicial Neural Network (SNN) layers. For each feasible circuit $Z$, the actor pools the refined simplex features over the realized local subtriangulation $\Delta^+(Z)$ and projects them to a scalar score.
• Value Head: A lightweight MLP estimates the state value $V(\Delta)$ using pooled vertex embeddings, used for policy gradient training.

4. Training Strategy

The policy is trained using Proximal Policy Optimization (PPO) with Generalized Advantage Estimation (GAE).

• Generalization: The model is trained on a distribution of small polytopes and evaluated on larger, unseen polytopes.
• Exploration: To prevent getting stuck in suboptimal trajectories, the training includes a count-based expansion bonus $b_t = \beta N(\Delta_{t+1})^{-1/2}$, encouraging the agent to visit new states in the implicit graph.
• Initial State Sampling: Initial states are sampled with weights proportional to $N(\Delta_0)^{-1/2}$ to prioritize under-explored regions.

Key Contributions

1. RL Formulation for Triangulation: The paper identifies triangulation optimization as RL on an implicit flip graph, utilizing geometric routines for validity and a learned policy for move selection.
2. Circuit-Supported Action Representation: A dimension-agnostic interface that encodes actions via their supporting circuit and local subtriangulation, enabling the policy to rank moves based on local geometric and combinatorial features.
3. Zero-Shot Generalization: The framework demonstrates strong generalization from small training instances to larger polytopes with exponentially larger search spaces.
4. Application to Calabi-Yau Sampling: The framework is adapted as a sampler for Fine, Regular, Star (FRST) triangulations of 4D reflexive polytopes, which parametrize Calabi-Yau threefolds.

Experimental Results

Experiments were conducted in 3D and 4D across three objectives: Min Simplices, Min Diameter, and Min Weight.

• Optimization Performance:

  • In 3D, TriSearch achieves an average relative gap of 0.16% against the exact optimum (found by exhaustive TOPCOM enumeration), significantly outperforming baselines like NLS (8.97%), GREEDY, and Simulated Annealing.
  • In 4D, where exhaustive enumeration is infeasible, TriSearch surpasses a $10^9$-step TOPCOM enumeration baseline on Min Simplices and Min Weight. It achieves an average relative gap of 1.43%, compared to 9.09% for the next-best baseline (NLS).
  • Ablation: Removing simplicial information (using only EGNN) or subtriangulation structure (using simple pooling) drastically increases the relative gap, confirming the necessity of the circuit-supported representation.

• Calabi-Yau Threefold Sampling:

  • In the task of discovering distinct FRSTs for 4D reflexive polytopes (Kreuzer-Skarke list), TriSearch outperforms existing CYTOOLS samplers (FRST Fast Sampler and MCMC).
  • Under a fixed budget, TriSearch discovers more distinct Calabi-Yau threefold classes, particularly for higher Hodge numbers ($h^{1,1} = 12, 16$), where other methods suffer from low sampling efficiency or rapid decay in success rates.

Significance and Limitations

The paper claims that TriSearch provides a unified search framework capable of targeting diverse objectives (shape optimization, combinatorial minimization, and topological discovery) without requiring explicit enumeration of the search space. It demonstrates that learned policies can effectively navigate complex, geometry-constrained graphs where local moves are mathematically well-defined but the global space is intractable.

The authors acknowledge limitations:

• The method currently relies on a geometric routine (TOPCOM) to enumerate valid flips, which is difficult to parallelize.
• It does not currently address cases where the flip graph is disconnected (known to occur in dimensions $d \geq 6$).
• In the CY sampling application, starting triangulations are sampled uniformly; future work could learn the distribution of FRSTs in height space for more strategic sampling.

The work suggests that this high-level structure (searching a large space via local, mathematically constrained moves) may be applicable to other domains such as phylogenetic tree search, rhombus tiling, and unknotting problems.