TriSearch: Learning to Optimize Triangulations via Bistellar Flips
Yiran Wang, Guido Montúfar · 2026
Read TriSearch: Learning to Optimize Triangulations via Bistellar Flips by Yiran Wang, Guido Montúfar (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-30220.txt.
Introduction
Yiran Wang and Guido Montúfar present TriSearch, a reinforcement learning method for optimizing objectives over polytope triangulations via bistellar flips. Feasible flips are encoded by supporting circuits and local subtriangulations, letting a policy rank them from local features. The interface works across dimensions, traversing the flip graph without enumerating the full space. In three and four dimensions, TriSearch generalizes zero-shot from small cases to larger polytopes. It tops metric objectives in 3D and finds more distinct Fine, Regular, Star triangulations in 4D than current samplers.
Catalog record
| CREATOR | Yiran Wang, Guido Montúfar |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62423 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.30220
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
TriSearch: Learning to Optimize Triangulations via Bistellar Flips Yiran Wang, Guido Montúfar 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 , 2 , 3 ] . In mathematical physics, triangulations of 4D reflexive polytopes parametrize large families of Calabi-Yau 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 , 7 , 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 \mathcal{P} , triangulation optimization is generally hard, especially for d>2 . This difficulty stems from the cardinality of the triangulation space \mathcal{T}(\mathcal{P}) , which can grow exponentially in both the ambient dimension d and the number of vertices |\mathcal{V}(\mathcal{P})| , with a standard worst-case upper bound of 2^{O(|\mathcal{V}(\mathcal{P})|^{\lceil d/2\rceil})} [ 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\geq 2 , is NP-hard [ 6 , 7 , 8 ] . The triangulation space \mathcal{T}(\mathcal{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 \mathcal{G}(\mathcal{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 3 D and 4 D. 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 CYTools 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 , 14 , 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 , 17 , 18 , 19 , 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 \mathcal{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 , 23 , 24 ] . These methods are designed around problem-specific actions for TSP, MaxCut, CVRP, and JSSP [ 22 , 23 , 24 , 25 ] . Local-search controllers such as NeuroLS [ 25 ] operate at a meta level by learning acceptance criteria, operator choice, or perturbation on top of