TriSearch: Learning to Optimize Triangulations via Bistellar Flips
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "TriSearch: Learning to Optimize Triangulations via Bistellar Flips".
Jane: Here's the gist of the paper. TriSearch introduces 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 <ref:2605.30220#pg3> This yields a dimension-agnostic interface and enables efficient traversal of the flip graph without explicit enumeration of the full triangulation space <ref:2605.30220#pg3>.
Tom: Problem Formulation Triangulation optimization is identified as search on an implicit flip graph, where states are complete triangulations and actions are currently feasible bistellar flips <ref:2605.30220#pg4>.
Jane: The problem is formulated as a Markov Decision Process (MDP) M = M = 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 <ref:2605.30220#pg4>.
Tom: The reward function Rf is defined by the improvement in the objective induced by a flip, such as Rf (△, Z) = f(△) − f(Flip(△;Z)), Z ∈ F(△),, where the sign is reversed for maximization case <ref:2605.30220#pg5>.
Title and authors: Tom: So we're looking at this paper called TriSearch: Learning to Optimize Triangulations via Bistellar Flips. It sounds like they've put a reinforcement learning framework on top of optimizing shapes made from polytopes using these flips.
Jane: That’s right, and the main idea is that instead of trying to search the whole space at once, they use a method called a circuit-supported action representation to figure out which moves are actually allowed at any given point.
Lu: The core concept is encoding feasible flips by their supporting circuit and the local subtriangulation they create, which lets the learned policy rank these moves using local geometric and combinatorial features.
Meng: So, what does this mean for us on a practical side? It sounds like they've created a way to navigate a flip graph without having to list out every single possible triangulation in advance.
Tom: Exactly. They’re essentially treating the problem as searching an implicit flip graph, where the states are complete triangulations and the actions are those feasible bistellar flips available right now.
Jane: The reward function they set up is based on how much better the objective function improves when you make a flip, like reducing total edge length or minimizing simplices.
Lu: And to handle the actual selection, they use a two-stage policy architecture involving an encoder and an actor that scores those circuit-supported subtriangulations.
Meng: What kind of encoder are we talking about? Is it just looking at the current shape, or is it trying to capture some deeper structure of the whole triangulation?
Lu: They use a graph neural network called EGNN that processes the entire triangulation graph to produce vertex-level representations, which they then lift up to maximal simplices to build features on the dual graph.
Tom: That sounds like a lot of data processing upfront, but then the actor outputs a score for each flippable circuit using a linear projection with learnable weights.
Jane: So, when you’re driving or cooking and you have multiple options—turn left or turn right—the policy learns how to quickly tell which path is better based on what it sees locally.
Meng: I worry about the scale here. If this whole setup requires processing the entire triangulation graph for every move, how much memory and time does that add to the actual search process?
Lu: They're aiming for a dimension-agnostic interface, which means you could theoretically use it in three dee or 4D without rewriting the core policy structure <ref:2605.30220#pg1>.
Tom: That’s huge. It suggests they’ve found a way to make the search method adaptable across different dimensions without needing a complete redesign every time.
Title and authors: Jane: And they mention that this allows for an efficient traversal of the flip graph without having to explicitly list out the entire triangulation space, which is usually impossible in high dimensions.
Meng: That sounds good for efficiency, but what about when things get really complex? If the search space is still exponentially large, does this method still manage to find a good solution quickly?
Lu: They state that TriSearch generalizes zero-shot from small training instances to larger polytopes with exponentially larger search spaces during training.
Tom: That’s a key point. It means the learned local search actually works well even when the problem space explodes beyond what you can just brute force or enumerate.
Jane: And they show this in three dee and 4D, achieving top performance on metric objectives like minimizing total edge length for both dimensions under a fixed flip budget of five hundred flips <ref:2605.30220#pg1,top performance on metric objectives>.
Meng: Top performance against what exactly? Against classical heuristics based on greedy or DFS methods, right? Because those are usually the ones people use when they don't have enough time to run a complex AI model.
Tom: Yeah, they compare it against classical baselines like GREEDY, DFS, BEFS, and even a learned meta-heuristics controller called NLS. TriSearch beats them in three dee and 4D optimization under the same budget of five hundred flips <ref:2605.30220#pg1>.
Jane: But they also show something interesting in four dimensions: TriSearch discovers more distinct Fine, Regular, Star triangulations of reflexive polytopes than existing samplers under that same budget.
Lu: That’s because they are looking at Calabi-Yau threefolds, which are related to these reflexive polytopes. The results suggest TriSearch finds more topological classes than the tools like CYTOOLS can find with a fixed budget.
Meng: So, in practice for someone trying to sample those complex shapes, this means you might discover more unique structures faster than you currently can.
Tom: It confirms that learned flip-graph navigation is an effective way to tackle combinatorial geometry problems where enumerating the space is just not feasible.
Jane: They also mention a limitation, though, which is that parallelizing the geometric routine used to enumerate flippable circuits can be really difficult when you try to scale this up.
Lu: And they also noted that the framework doesn't currently address disconnected flip graphs, which means if the polytope has separate pieces, it might not work as expected.
Meng: That’s a fair caveat for production use. If your input data doesn't form one single connected piece, you need to know that limitation upfront.
Title and authors: Tom: To wrap up on the methodology, they detail how they construct bistellar flips using Radon partitions in an appendix, which is pretty detailed for anyone wanting to reproduce the geometric part.
Jane: And they show that the final training objective minimizes a combination of policy loss, value function loss, and an entropy loss to keep things exploring.
Lu: The overall contribution here is really introducing this circuit-supported action representation for triangulation optimization, which is a way to learn how to rank moves based on local structure.
Tom: So, it’s about learning the nuances of geometry from local information rather than having a massive lookup table of all possible global states.
Jane: It’s a powerful tool for searching spaces that are too big for traditional solvers because it learns the navigation skills directly from the geometric constraints.
Meng: For deployment, we need to know how much overhead this learned policy adds compared to just using a fast heuristic when time is of the essence.
Lu: The paper points out that this framework’s structure might actually be useful for other problems like phylogenetic tree search and unknotting problems as well.
Tom: It seems like they’ve built something quite flexible because the underlying concept of flipping local structures applies to a lot of geometric optimization tasks.
Jane: So, to summarize TriSearch: it uses reinforcement learning on an implicit flip graph, encoding moves via circuits to learn a policy that ranks feasible flips based on local geometry and combinatorics.
Meng: That’s what I got. It sounds like a solid piece of research for exploring those hard combinatorial spaces.
Lu: It is significant because it shows that you can use geometric deep learning principles to respect underlying symmetries in the combinatorial space effectively.
Tom: It validates using learned methods when explicit enumeration of the entire search space is intractable, which is exactly what we need for many complex optimization problems.
Jane: And while they have limitations regarding parallelization and disconnected graphs, their empirical results show top performance against established tools in three dee and 4D optimization tasks <ref:2605.30220#pg1>.
Meng: I think the main thing for us to watch is how robust this policy is when we move away from the specific polytope types they tested to more general ones.
Lu: That’s definitely the next question, exploring its generalization outside of those specific reflexive polytopes will tell us a lot about its real-world applicability.
Tom: So that’s it for TriSearch: a reinforcement learning framework for optimizing triangulations via bistellar flips, and it points toward using learned navigation skills to tackle geometry problems where enumerating the space is too hard.
The paper's summary: Tom: So, TriSearch is basically an AI system designed to optimize shapes made from polytopes by learning how to flip their internal triangles, and it does this by figuring out which flips are good using reinforcement learning.
Jane: That's right, and the main idea they're pushing is that you don't have to list every single possible shape you could make; instead, the AI learns a strategy for navigating a whole graph of shapes based on local information.
Lu: They use something called a circuit-supported action representation to encode those flips. This means they can mathematically describe exactly which flips are allowed at any given point, and then the learning system ranks them using geometric features right there.
Tom: It sounds like they've created a dimension-agnostic way to search these shapes, which is pretty cool because it suggests you could use this same framework for three dee or 4D problems without rewriting the whole setup <ref:2605.30220#pg1>.
Jane: What that means for someone just listening is that you don't need a huge, pre-programmed map of every possible shape; the system learns to make good moves on its own based on what it sees right now.
Lu: They trained this using something called Proximal Policy Optimization with generalized advantage estimation, which is the standard way to teach an AI agent to maximize rewards over a long period.
Tom: And they added a little exploration bonus, that count-based expansion bonus, because without that, the AI would just get stuck doing the same small set of moves it already knows are okay.
Jane: They show strong results in both three and four dimensions when optimizing things like minimizing edge length or the number of simplices within a fixed budget of five hundred flips.
Lu: And in four dimensions, they found that this method discovers more different types of shapes than previous sampling tools when looking at reflexive polytopes.
Tom: That's solid performance against classical heuristics and even some learned meta-heuristics controllers, but it’s really about showing that learning how to move on a graph is a very effective way to solve these massive combinatorial geometry problems.
Jane: But they also have some limitations, like the geometric part of finding all possible flips can be hard to parallelize, and they don't currently handle disconnected flip graphs.
Lu: And for their future work in four dimensions, they suggest learning the distribution of those specific shapes instead of just picking them randomly when sampling Calabi-Yau threefolds.
Tom: It’s a lot of technical detail here—all the GNNs and the policy architecture—but what it boils down to is that this framework gives us a robust method for navigating these flip graphs by leveraging local mathematical structure.
Jane: So, the big picture is that we can use reinforcement learning to tackle combinatorial geometry problems where you just can't possibly enumerate all the possibilities on your computer.
Lu: And they’ve even hinted that this kind of structure could be useful for other things, like searching for phylogenetic trees or even solving unknotting problems.
Tom: It validates using learned methods when traditional exact enumeration algorithms are simply too slow because the search space grows exponentially.
Jane: The real impact here is showing that learning how to rank moves based on local geometry and global context is a very powerful approach for complex shapes in high dimensions.
The paper's improvements: Tom: So, we're looking at how they suggest improving TriSearch to make it even better than what they have right now. It’s like taking a good engine and adding turbochargers to get more power out of the search process.
Jane: Exactly, and one big suggestion is about making the geometric routine that finds all those possible flips faster so the whole thing doesn't grind to a halt when you try to run it on really complicated shapes.
Lu: They mentioned parallelizing that part, which is hard right now because geometry routines are often sequential, but they think if you can make them run on many processors at once, that would be huge for scaling up the search.
Tom: I get that; when we're shipping models to production like Meng does, having a routine that runs in constant time or near constant time is usually a deal-breaker because latency adds up fast.
Jane: And then there’s this other idea, which is more about the data itself—they suggest learning the shape distribution rather than just sampling uniformly when you're doing those Calabi-Yau threefolds.
Lu: That would be way smarter, because uniform sampling often wastes a lot of time looking at areas of the shape space that are actually impossible or highly unlikely to be found.
Tom: So instead of throwing random points at the wall, the AI learns where the interesting shapes are likely to hide, which should cut down on wasted computation time.
Jane: It’s about learning how to navigate these complex spaces more intelligently by understanding their underlying statistical structure instead of just guessing.
Lu: And they also pointed out that this whole framework has potential for other problems too, like searching for phylogenetic trees or even solving unknotting problems.
Tom: That's interesting because it suggests the core idea of learning to navigate local moves is a very general concept, not just limited to triangulations.
Jane: So if you look at the broader picture, this isn't just about optimizing shapes; it’s about building a search framework that respects geometry in many different ways.
Lu: And they’ve also pointed out that they need to figure out how to handle disconnected flip graphs, which is a structural issue that could limit where this method can be applied.
Tom: That's the caveat—if the problem breaks into separate pieces, this specific navigation strategy won't work as smoothly across those gaps.
Jane: So, while the potential is huge because of how it learns to rank moves locally, you have to be aware of those structural limitations in your input data.
Lu: And we're still waiting on more work there regarding parallelization and that distribution learning for the Calabi-Yau cases.
Tom: So, the next thing we should watch is how they tackle those technical hurdles—parallelizing geometry and handling disconnected graphs—because those are what separate a cool research paper from something you can actually deploy reliably.
Conclusion: Tom: So to wrap up, TriSearch is an AI method that uses reinforcement learning to find the best way to optimize shapes made from polytopes by learning how to navigate a flip graph using local geometric features.
Jane: That’s right, and it shows that you can use learned search skills instead of brute-force enumeration when the search space is just too big for traditional exact methods.
Lu: The core contribution is this circuit-supported action representation, which lets the AI rank feasible flips based on both local geometry and what's happening in the surrounding structure.
Tom: It’s pretty clean because it gives you a dimension-agnostic interface, so you could potentially use this for three dee or 4D problems without rewriting your whole system <ref:2605.30220#pg1>.
Jane: But there are still hurdles, like the difficulty of parallelizing the routine that finds all those possible flips, and they haven't fully addressed disconnected flip graphs yet.
Meng: From a deployment standpoint, I need to know how much overhead this learned policy adds compared to just running a fast heuristic when we have real traffic and tight latency requirements.
Lu: And for the Calabi-Yau sampling task specifically, they suggest learning the distribution of those shapes instead of just using uniform sampling, which would be a big improvement for discovering new classes.
Tom: So this paper really validates using reinforcement learning to handle complex combinatorial geometry problems where you can't enumerate the space on your own.
Jane: It’s significant because it shows that learning how to move on a graph based on local structure is a very effective way to solve these massive search spaces.
Meng: I just worry about the practical cost of training this kind of policy and whether it actually generalizes when we move away from these specific reflexive polytopes they tested.
Lu: The framework’s structure is flexible, though, and they’ve even mentioned it could be applied to other problems like phylogenetic tree search or unknotting problems.
Tom: It’s a solid piece of work for showing that learned navigation skills can handle geometric constraints in ways traditional methods struggle with.
Jane: So the main point is that TriSearch provides a robust method for navigating these flip graphs by leveraging local mathematical structure to find good solutions.
Yiran Wang, Guido Montúro
University of California, Los Angeles · Massachusetts Institute of Physics
cs.LG
Submitted: 2026-05-28
Updated: 2026-11-10
Code: https://github.com/jokofa/NeuroLS
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 83/100
The gist: TriSearch introduces a reinforcement-learning framework for optimizing objectives over triangulations of a polytope via bistellar flips The key idea is a circuit-supported subtriangulation action…
Key concepts
- Bistellar Flips
- These are specific local moves that change one triangulation of a polytope into another by replacing a single simplex with an adjacent one. They form the fundamental actions in the search space, allowing the system to navigate between different possible triangulations of a given geometric shape.
- Circuit-Supported Subtriangulation Action Representation
- This is how TriSearch encodes feasible flips. Instead of treating every possible flip as a separate action, it represents them using a circuit structure and the resulting local change in the triangulation. This representation allows the policy to understand both which moves are valid and what local geometric consequences they have.
- Policy Architecture (EGNN Encoder and Actor)
- The system uses two main neural network parts: an encoder that reads the current triangulation graph to create feature representations, and an actor that takes these features to score every possible flip. This structure allows the AI to learn how to rank moves based on the global context of the polytope while considering local geometric details.
- Proximal Policy Optimization (PPO) with GAE
- This is the reinforcement learning algorithm used for training. PPO is a stable method that updates the policy iteratively to maximize rewards. Generalized Advantage Estimation (GAE) helps estimate how much better or worse a specific flip was compared to what was expected, guiding the AI toward optimal long-term strategies.
Terminology
Summary
TriSearch introduces 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 <ref:2605. p. 0 edu
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. 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.Where the paper says it
Where the paper says it
Problem Formulation
Triangulation optimization is identified as search on an implicit flip graph, where states are complete triangulations and actions are currently feasible bistellar flips <ref:2605.30220#pg4>. The problem is formulated as a Markov Decision Process (MDP) M = M = 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 <ref:2605. p. 3 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. 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.Where the paper says it
Where the paper says it
Policy Architecture
The policy architecture employs a two-stage design involving a shared encoder Encκ and an actor that scores circuit-supported subtriangulations <ref:2605.30220#pg6>. The EGNN encoder processes the entire triangulation graph G(△) to produce vertex-level representations, which are then lifted to maximal simplices to build features on the dual graph Gˆ(△) <ref:2605. p. 4 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. 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
{g
(Lπ)
a
: σa ∈ △+(Z)}
, sθ(△, Z) = W⊤zZ.Where the paper says it
Where the paper says it
Training Methodology
The policy is trained using Proximal Policy Optimization (PPO) with generalized advantage estimation (GAE) to maximize the expected discounted cumulative reward over a horizon H <ref:2605.30220#pg7>. To encourage exploration and prevent overfitting, a count-based expansion bonus bt = βN(△t+1) − 1/2 is added to the reward, and weighted initial state sampling is used to sample from under-explored areas of the implicit graph <ref:2605. p. 5 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.Where the paper says it
Empirical Results
TriSearch demonstrates strong performance in triangulation optimization under a fixed flip budget, achieving the lowest aggregate relative gap among evaluated search algorithms in both 3D and 4D <ref:2605.30220#pg8>. In 4D, TriSearch discovers more distinct Fine, Regular, Star triangulations of reflexive polytopes than existing samplers under a fixed budget <ref:2605. p. 0 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. • 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.Where the paper says it
Where the paper says it
Limitations and Future Work
Current limitations include the difficulty of parallelizing the geometric routine used to enumerate flippable circuits <ref:2605.30220#pg11>, and the lack of addressing disconnected flip graphs <ref:2605. p. 3 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(△). 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. 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.Where the paper says it
Where the paper says it
Experiments and Baselines
The experiments compare TriSearch against classical heuristics-based baselines (GREEDY, DFS, BEFS, SA) and the learned meta-heuristics controller NLS <ref:2605.30220#pg8>. In 4D optimization, TriSearch surpasses the 109-steps TOPCOM reference on Min Simplices and Min Weight at both V = 13 and V = 14 within a budget of 500 flips <ref:2605. p. 6 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. Figure 4d aggregates the
final class fractions across h
1,1 ∈ {4, 8, 12, 16}. TriSearch recovers all known classes at h
1,1 = 4
and h
1,1 = 8, and outperforms both CYTOOLS samplers at h
1,1 = 12 and h
1,1 = 16. TriSearch outperforms all the baselines under the same budget across 3D and 4D
triangulation optimization, and outperforms the widely used samplers in CYTOOLS 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. Appendix A unpacks the linked construction and the proof of the uniqueness. Through bistellar flips, the triangulation space becomes a flip graph. 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]. arXiv:2605. The full TriSearch model uses an SNN actor to score each flip from its local subtriangulation. Table 1: Controlled 4D ablation at 500 flips. 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. The more detailed
descriptions of the baseline algorithms are deferred to Appendix C. Each method receives a budget
of 500 flips from the same starting triangulations, and we report the average relative gap as:
RelativeGap(A) = 1
|S|
X
P∈S
f(△ˆ A(P)) − f(△ref(P))
f(△ref(P)) ,
where △ˆ A(P) is the best triangulation found by A within the budget or from TOPCOM enumeration. 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]. arXiv:2605. 43% in 4D, against 8. 09% for the next-best
baseline NLS, where the detailed aggregated result tables can be found in Appendix D. The ablation
in Table 1 supports this choice. Removing simplicial information substantially worsens the controlled
4D results across all three objectives. 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. 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).Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Conclusion
TriSearch outperforms all baselines under the same budget across 3D and 4D triangulation optimization, and outperforms the widely used samplers in CYTOOLS across 4D CY threefold sampling task <ref:2605.30220#pg7>. This work supports 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 <ref:2605. p. 8 TriSearch outperforms all the baselines under the same budget across 3D and 4D
triangulation optimization, and outperforms the widely used samplers in CYTOOLS 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. TriSearch recovers all known classes at h
1,1 = 4
and h
1,1 = 8, and outperforms both CYTOOLS samplers at h
1,1 = 12 and h
1,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. 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. 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. 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. 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. The
other detailed hyperparameters can be found in Appendix B. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Reinforcement learning framework for optimizing triangulations via bistellar flips allows systems to perform search on implicit flip graphs without explicit enumeration of the full triangulation space. This enables efficient traversal of the flip graph by using a circuit-supported subtriangulation action representation that encodes both admissibility and local replacement.
-
The system can effectively rank feasible flips using learned local geometric and combinatorial features, leading to a dimension-agnostic interface for optimization objectives such as minimizing total edge length or the number of simplices. This enables the policy to choose moves useful for long-range optimization without needing prior knowledge of the entire search space structure.
-
TriSearch can generalize zero shot from small training instances to larger polytopes with exponentially larger search spaces, demonstrating that
the learned local search generalizes beyond the hardness regime during training.
This capability means AI systems can tackle problems where traditional exact enumeration algorithms are intractable due to exponential growth in the triangulation space. -
For Calabi-Yau threefold sampling, TriSearch can be repurposed as a practical Fine, Regular, Star triangulation sampler that
outperforms the existing CYTOOLS samplers under the same budget by discovering more distinct CY threefold classes.
This allows AI systems to discover more topological classes of threefolds than current state-of-the-art methods. -
The policy architecture uses an equivariant graph neural network encoder over the current triangulation and a simplex-level GNN actor to score circuit actions, ensuring that
the action representation
handles both optimization and Fine, Regular, Star triangulation discovery. This structure leverages geometric deep learning principles to respect underlying symmetries in the combinatorial space. -
The training procedure incorporates a count-based expansion bonus bt = beta N(△t+1) - 1/2 to encourage exploration of the implicit flip graph, preventing
the model from overfitting and getting stuck at suboptimal trajectories.
This mechanism helps the policy learn reusable navigation behavior that can generalize across different polytope combinatorial and geometric configurations.
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.
Sources
- Dual Polyhedra and Mirror Symmetry for Calabi-Yau Hypersurfaces in Toric Varieties
- Complete classification of reflexive polyhedra in four dimensions
- CYTools: A Software Package for Analyzing Calabi-Yau Manifolds
- Neural Combinatorial Optimization with Reinforcement Learning
- Attention, Learn to Solve Routing Problems!
- Transforming Calabi-Yau Constructions: Generating New Calabi-Yau Manifolds with Transformers
- Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges
- Equiformer: Equivariant Graph Attention Transformer for 3D Atomistic Graphs
- EquiformerV2: Improved Equivariant Transformer for Scaling to Higher-Degree Representations
- Go-Explore: a New Approach for Hard-Exploration Problems
- Proximal Policy Optimization Algorithms
- High-Dimensional Continuous Control Using Generalized Advantage Estimation
- Searching for Activation Functions
- Adam: A Method for Stochastic Optimization
- What makes math problems hard for reinforcement learning: a case study
Related papers
- A Physics-Regulated Neural Framework for Learning 3D Grain Growth Dynamics
- FlexMoE: Learning One-for-All Multi-Budget Expert Pruning for Flexible MoE Deployment
- OptiMind: Improving Small Language Models for Optimization Modeling through Formulation Guidance and Multi-Turn Learning
- Staying in the Sweet Spot: Boost Reasoning Evolution via Responsive Rollout Difficulty Manipulation
- Examining the Impact of Data and Training Methods on Emergent and Subliminal Misalignment
- Rethinking Black-Box On-Policy Distillation: A Rubric-based Analysis