TriSearch: Learning to Optimize Triangulations via Bistellar Flips
Pith reviewed 2026-06-29 08:50 UTC · model grok-4.3
The pith
TriSearch trains a reinforcement learning policy to select bistellar flips that optimize triangulations of polytopes, using a circuit-supported action representation that generalizes from small instances to much larger search spaces.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
TriSearch is 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.
What carries the argument
The circuit-supported subtriangulation action representation, which encodes each feasible bistellar flip by its supporting circuit together with the local subtriangulation it realizes so that a policy can rank flips from local features.
If this is right
- The method achieves top performance on metric objectives for triangulations in three dimensions.
- In four dimensions it discovers more distinct Fine, Regular, Star triangulations of reflexive polytopes than existing samplers under a fixed budget.
- Training on small instances produces a policy that applies directly to polytopes whose triangulation spaces are exponentially larger.
- The same action representation supplies a dimension-agnostic interface for traversing flip graphs of polytopes.
Where Pith is reading between the lines
- The same local-feature policy could be tested on polytopes whose triangulations correspond to Calabi-Yau threefolds with prescribed Hodge numbers or other topological invariants.
- If local geometric features suffice for ranking flips, similar representations might transfer to other combinatorial objects whose connectivity is described by circuits, such as matroid bases or oriented matroids.
- The observed zero-shot scaling suggests that the learned ranking function captures regularities in the flip graph that are independent of overall dimension and volume.
- An immediate next measurement would be the fraction of all possible fine regular star triangulations recovered by the policy as polytope size increases.
Load-bearing premise
The circuit-supported subtriangulation action representation allows a learned policy to effectively rank feasible flips using only local geometric and combinatorial features, enabling generalization without full enumeration of the triangulation space.
What would settle it
If a policy trained on small polytopes is applied to larger polytopes and produces no improvement in metric objectives or fewer distinct fine regular star triangulations than existing samplers under the same computational budget, the generalization claim is falsified.
Figures
read the original 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces TriSearch, a reinforcement learning framework for optimizing objectives over triangulations of a polytope via bistellar flips. The key technical contribution is a circuit-supported subtriangulation action representation that encodes feasible flips by their supporting circuit and realized local subtriangulation, allowing a policy to rank actions using only local geometric and combinatorial features. This yields a dimension-agnostic interface. The method is instantiated in 3D and 4D, with claims of zero-shot generalization from small training polytopes to larger ones (with exponentially larger search spaces), top performance on metric objectives in 3D, and discovery of more distinct Fine/Regular/Star triangulations of reflexive polytopes (corresponding to Calabi-Yau threefolds) than existing samplers under fixed budget in 4D.
Significance. If the empirical claims on zero-shot generalization and outperformance hold with proper verification, the work would be significant for computational algebraic geometry: it offers a scalable, learned alternative to exhaustive or random sampling of triangulation flip graphs, which grow factorially with dimension and number of points. The local-feature inductive bias could accelerate enumeration tasks relevant to string theory and mirror symmetry.
major comments (3)
- [Abstract and §4] Abstract and §4 (Experiments): performance and generalization claims are stated without accompanying quantitative results, error bars, training hyperparameters, instance sizes, or statistical tests in the provided text; the central empirical claims cannot be assessed without these details in the experiments section.
- [§3.2] §3.2 (Action Representation): the claim that the circuit-supported subtriangulation encoding enables effective ranking 'using only local geometric and combinatorial features' is load-bearing for the zero-shot generalization result; the manuscript must demonstrate (via ablation or feature analysis) that no global polytope information leaks into the local state representation.
- [§4.3] §4.3 (4D Results): the statement that TriSearch 'discovers more distinct Fine, Regular, Star triangulations ... than existing samplers under a fixed budget' requires explicit reporting of the budget (number of flips or wall-clock time), the exact baselines, and the number of distinct triangulations found per method with variance across runs.
minor comments (2)
- Define all acronyms (e.g., FRS triangulations) at first use and ensure consistent notation for circuits and subtriangulations across sections.
- Add a table or figure summarizing the polytope sizes (number of points, dimension) used for training versus testing to support the zero-shot claim.
Simulated Author's Rebuttal
We thank the referee for the constructive and detailed feedback. We address each major comment below and will revise the manuscript to strengthen the presentation of experimental results and supporting analyses.
read point-by-point responses
-
Referee: [Abstract and §4] Abstract and §4 (Experiments): performance and generalization claims are stated without accompanying quantitative results, error bars, training hyperparameters, instance sizes, or statistical tests in the provided text; the central empirical claims cannot be assessed without these details in the experiments section.
Authors: We agree that the submitted version of the experiments section and abstract did not include sufficient quantitative detail for independent assessment. In the revised manuscript we will expand §4 with tables containing concrete performance metrics (including means and standard deviations across runs), full lists of training hyperparameters, exact polytope instance sizes for training and zero-shot evaluation, and appropriate statistical comparisons. The abstract will be updated to reference these quantitative results. revision: yes
-
Referee: [§3.2] §3.2 (Action Representation): the claim that the circuit-supported subtriangulation encoding enables effective ranking 'using only local geometric and combinatorial features' is load-bearing for the zero-shot generalization result; the manuscript must demonstrate (via ablation or feature analysis) that no global polytope information leaks into the local state representation.
Authors: We acknowledge that an explicit demonstration is needed to support the load-bearing claim. The revised manuscript will include a new ablation study that trains the policy on the local representation while systematically masking or adding global polytope features; performance differences will be reported to confirm that the observed zero-shot generalization relies only on the local circuit-supported subtriangulation encoding. revision: yes
-
Referee: [§4.3] §4.3 (4D Results): the statement that TriSearch 'discovers more distinct Fine, Regular, Star triangulations ... than existing samplers under a fixed budget' requires explicit reporting of the budget (number of flips or wall-clock time), the exact baselines, and the number of distinct triangulations found per method with variance across runs.
Authors: We will revise §4.3 to report the precise computational budget (both flip count and wall-clock time), name the exact baseline samplers, and tabulate the number of distinct Fine/Regular/Star triangulations discovered by each method together with run-to-run variance or standard deviation. revision: yes
Circularity Check
No significant circularity
full rationale
The paper presents TriSearch as an empirical RL method whose performance claims (zero-shot generalization, discovery counts) rest on experimental results rather than any derivation chain. No equations, fitted parameters renamed as predictions, or load-bearing self-citations appear in the abstract or described structure; the action representation is introduced as an inductive bias enabling traversal, not as a self-referential definition. The work is self-contained against external benchmarks.
Axiom & Free-Parameter Ledger
Reference graph
Works this paper leans on
-
[1]
Iste, 2007
Pascal Jean Frey and Paul-Louis George.Mesh generation: application to finite elements. Iste, 2007
2007
-
[2]
Mesh generation and optimal triangulation
Marshall Bern and David Eppstein. Mesh generation and optimal triangulation. InComputing in Euclidean geometry, pages 47–123. World Scientific, 1995
1995
-
[3]
Delaunay refinement algorithms for triangular mesh generation
Jonathan Richard Shewchuk. Delaunay refinement algorithms for triangular mesh generation. Computational Geometry, 22(1–3):21–74, 2002
2002
-
[4]
Dual Polyhedra and Mirror Symmetry for Calabi-Yau Hypersurfaces in Toric Varieties
Victor V Batyrev. Dual polyhedra and mirror symmetry for calabi-yau hypersurfaces in toric varieties.arXiv preprint alg-geom/9310003, 1993
work page internal anchor Pith review Pith/arXiv arXiv 1993
-
[5]
Complete classification of reflexive polyhedra in four dimensions
Maximilian Kreuzer and Harald Skarke. Complete classification of reflexive polyhedra in four dimensions.arXiv preprint hep-th/0002240, 2000
work page internal anchor Pith review Pith/arXiv arXiv 2000
-
[6]
Tetrahedrizing point sets in three dimensions
Herbert Edelsbrunner, Franco P Preparata, and Douglas Brent West. Tetrahedrizing point sets in three dimensions. InInternational Symposium on Symbolic and Algebraic Computation, pages 315–331. Springer, 1988
1988
-
[7]
De Loera, and Jürgen Richter-Gebert
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
2004
-
[8]
Minimum-weight triangulation is NP-hard.Journal of the ACM (JACM), 55(2):1–29, 2008
Wolfgang Mulzer and Günter Rote. Minimum-weight triangulation is NP-hard.Journal of the ACM (JACM), 55(2):1–29, 2008
2008
-
[9]
Cytools: a software package for analyzing calabi-yau manifolds.arXiv preprint arXiv:2211.03823, 2022
Mehmet Demirtas, Andres Rios-Tascon, and Liam McAllister. Cytools: a software package for analyzing calabi-yau manifolds.arXiv preprint arXiv:2211.03823, 2022
-
[10]
On counting triangulations in d dimensions.Computational Geometry, 3(6):315–325, 1993
Tamal Krishna Dey. On counting triangulations in d dimensions.Computational Geometry, 3(6):315–325, 1993
1993
-
[11]
Optimality of the delaunay triangulation in rd
Vadakkedathu T Rajan. Optimality of the delaunay triangulation in rd. InProceedings of the seventh annual symposium on Computational geometry, pages 357–363, 1991
1991
-
[12]
Topcom: Triangulations of point configurations and oriented matroids
Jörg Rambau. Topcom: Triangulations of point configurations and oriented matroids. In Mathematical software, pages 330–340. World Scientific, 2002
2002
-
[13]
Machine learning for combinatorial optimization: a methodological tour d’horizon.European Journal of Operational Research, 290(2):405–421, 2021
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
2021
-
[14]
Reinforcement learning for combinatorial optimization: A survey.Computers & Operations Research, 134:105400, 2021
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey.Computers & Operations Research, 134:105400, 2021
2021
-
[15]
Combinatorial optimization and reasoning with graph neural networks.Journal of Machine Learning Research, 24(130):1–61, 2023
Quentin Cappart, Didier Chételat, Elias B Khalil, Andrea Lodi, Christopher Morris, and Petar Veliˇckovi´c. Combinatorial optimization and reasoning with graph neural networks.Journal of Machine Learning Research, 24(130):1–61, 2023
2023
-
[16]
Pointer networks.Advances in neural information processing systems, 28, 2015
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks.Advances in neural information processing systems, 28, 2015
2015
-
[17]
Neural Combinatorial Optimization with Reinforcement Learning
Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combina- torial optimization with reinforcement learning.arXiv preprint arXiv:1611.09940, 2016
work page internal anchor Pith review Pith/arXiv arXiv 2016
-
[18]
Attention, Learn to Solve Routing Problems!
Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475, 2018
work page internal anchor Pith review Pith/arXiv arXiv 2018
-
[19]
Reinforcement learning for solving the vehicle routing problem
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. InAdvances in Neural Information Processing Systems, volume 31, 2018. 11
2018
-
[20]
POMO: Policy optimization with multiple optima for reinforcement learning
Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. POMO: Policy optimization with multiple optima for reinforcement learning. InAdvances in Neural Information Processing Systems, volume 33, pages 21188–21198, 2020
2020
-
[21]
On the difficulty of triangulating three-dimensional nonconvex polyhedra.Discrete & Computational Geometry, 7(3):227–253, 1992
Jim Ruppert and Raimund Seidel. On the difficulty of triangulating three-dimensional nonconvex polyhedra.Discrete & Computational Geometry, 7(3):227–253, 1992
1992
-
[22]
Learning improvement heuristics for solving routing problems.IEEE Transactions on Neural Networks and Learning Systems, 33(9):5057–5069, 2021
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
2021
-
[23]
Learning to perform local rewriting for combinatorial optimization
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. InAdvances in Neural Information Processing Systems, volume 32, 2019
2019
-
[24]
Barrett, William R
Thomas D. Barrett, William R. Clements, Jakob N. Foerster, and Alex I. Lvovsky. Exploratory combinatorial optimization with reinforcement learning. InProceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3243–3250, 2020
2020
-
[25]
Falkner, Daniela Thyssens, Ahmad Bdeir, and Lars Schmidt-Thieme
Jonas K. Falkner, Daniela Thyssens, Ahmad Bdeir, and Lars Schmidt-Thieme. Learning to control local search for combinatorial optimization. InJoint European Conference on Machine Learning and Knowledge Discovery in Databases (ECML PKDD), pages 361–376. Springer, 2022
2022
-
[26]
Springer Science & Business Media, 2010
Jesús De Loera, Jörg Rambau, and Francisco Santos.Triangulations: structures for algorithms and applications. Springer Science & Business Media, 2010
2010
-
[27]
A-discriminants
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
1994
-
[28]
Transforming triangulations.Discrete mathematics, 3(4):365–372, 1972
Charles L Lawson. Transforming triangulations.Discrete mathematics, 3(4):365–372, 1972
1972
-
[29]
Udo Pachner. P.L. homeomorphic manifolds are equivalent by elementary shellings.European journal of Combinatorics, 12(2):129–145, 1991
1991
-
[30]
Jacky HT Yip, Charles Arnal, François Charton, and Gary Shiu. Transforming calabi- yau constructions: Generating new calabi-yau manifolds with transformers.arXiv preprint arXiv:2507.03732, 2025
-
[31]
Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges
Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veliˇckovi´c. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges.arXiv preprint arXiv:2104.13478, 2021
work page internal anchor Pith review Pith/arXiv arXiv 2021
-
[32]
E(n) equivariant graph neural networks
Vıctor Garcia Satorras, Emiel Hoogeboom, and Max Welling. E(n) equivariant graph neural networks. InInternational conference on machine learning, pages 9323–9332. PMLR, 2021
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 equivari- ant transformer for scaling to higher-degree representations.arXiv preprint arXiv:2306.12059, 2023
-
[35]
Hypergraph neural networks
Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. Hypergraph neural networks. InProceedings of the AAAI conference on artificial intelligence, volume 33, pages 3558–3565, 2019
2019
-
[36]
Simplicial neural networks
Stefania Ebli, Michaël Defferrard, and Gard Spreemann. Simplicial neural networks. In Topological Data Analysis and Beyond workshop at NeurIPS, 2020
2020
-
[37]
Simplicial complex neural networks.IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(1):561–575, 2023
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
2023
-
[38]
Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten.Mathematis- che Annalen, 83(1):113–115, 1921
Johann Radon. Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten.Mathematis- che Annalen, 83(1):113–115, 1921. 12
1921
-
[39]
Non-connected toric Hilbert schemes.Mathematische Annalen, 332(3):645– 665, 2005
Francisco Santos. Non-connected toric Hilbert schemes.Mathematische Annalen, 332(3):645– 665, 2005
2005
-
[40]
Go-explore: a new approach for hard-exploration problems.arXiv preprint arXiv:1901.10995, 2019
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]
Proximal Policy Optimization Algorithms
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms.arXiv preprint arXiv:1707.06347, 2017
work page internal anchor Pith review Pith/arXiv arXiv 2017
-
[42]
High-Dimensional Continuous Control Using Generalized Advantage Estimation
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation.arXiv preprint arXiv:1506.02438, 2015
work page internal anchor Pith review Pith/arXiv arXiv 2015
-
[43]
Searching for Activation Functions
Prajit Ramachandran, Barret Zoph, and Quoc V Le. Searching for activation functions.arXiv preprint arXiv:1710.05941, 2017
work page internal anchor Pith review Pith/arXiv arXiv 2017
-
[44]
Adam: A Method for Stochastic Optimization
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization.arXiv preprint arXiv:1412.6980, 2014
work page internal anchor Pith review Pith/arXiv arXiv 2014
-
[45]
Bounding the Kreuzer-Skarke landscape.Fortschritte der Physik, 68(11-12):2000086, 2020
Mehmet Demirtas, Liam McAllister, and Andres Rios-Tascon. Bounding the Kreuzer-Skarke landscape.Fortschritte der Physik, 68(11-12):2000086, 2020
2020
-
[46]
Constructing unrooted phylogenetic trees with reinforcement learning.Studia Universitatis Babe¸ s-Bolyai Informatica, 66(1):37–53, 2021
Panna Lipták and Attila Kiss. Constructing unrooted phylogenetic trees with reinforcement learning.Studia Universitatis Babe¸ s-Bolyai Informatica, 66(1):37–53, 2021
2021
-
[47]
Rhombus tilings: decomposition and space structure
Frédéric Chavanon and Eric Rémila. Rhombus tilings: decomposition and space structure. Discrete & Computational Geometry, 35(2):329–358, 2006
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 th...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.