TriSearch: Learning to Optimize Triangulations via Bistellar Flips

arXiv:2605.30220 · cs.LG · Submitted 2026-05-28 · Read on arXiv

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

Where the paper says it

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.

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. p. 0
Where the paper says it

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.

30220#pg3>.

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

Where the paper says it

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.

30220#pg4>. 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. p. 3
Where the paper says it

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.

30220#pg5>.

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

Where the paper says it

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.

30220#pg7>. The actor outputs a score for each flippable circuit Z ∈ F(△) using a linear projection with learnable matrix W, yielding sθ(△, Z) = W⊤zZ <ref:2605. p. 5
Where the paper says it

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.

30220#pg7>.

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

Where the paper says it

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.

30220#pg7>.

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

Where the paper says it

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.

30220#pg2> Furthermore, in Calabi-Yau (CY) setting sampling, TriSearch outperforms the existing CYTOOLS samplers by discovering more distinct CY threefold classes <ref:2605. p. 1
Where the paper says it

• 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.

30220#pg10>.

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

Where the paper says it

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.

30220#pg11>. For CY sampling, future work could involve learning the distribution of FRSTs in height space instead of uniform sampling <ref:2605. p. 8
Where the paper says it

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.

30220#pg10>. The framework's structure is noted as having potential for other problems like phylogenetic tree search and unknotting problems <ref:2605.30220#pg7>.

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

Where the paper says it

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.

30220#pg9>. For CY threefold sampling, TriSearch recovers all known classes at h 1,1 = 4 and h 1,1 = 8, and outperforms CYTOOLS samplers at h 1,1 = 12 and h 1,1 = 16 <ref:2605. p. 8
Where the paper says it

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.

30220#pg10>. The results confirm that learned flip-graph navigation is an effective approach for combinatorial geometry problems whose search spaces are too large to enumerate <ref:2605. p. 8
Where the paper says it

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.

30220#pg7>. The paper also details the construction of bistellar flips via Radon partitions in Appendix A <ref:2605. p. 3
Where the paper says it

Appendix A unpacks the linked construction and the proof of the uniqueness. Through bistellar flips, the triangulation space becomes a flip graph.

30220#pg15>. The final training objective minimizes L = Lpolicy(θ, κ) + αvalLvalue(ψ, κ) + αentLentropy(θ, κ) <ref:2605. p. 0
Where the paper says it

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.

30220#pg17>. The model and PPO hyperparameters are summarized in Table 2 <ref:2605. p. 7
Where the paper says it

The full TriSearch model uses an SNN actor to score each flip from its local subtriangulation. Table 1: Controlled 4D ablation at 500 flips.

30220#pg18>. The synthetic data generation procedure is detailed in Algorithm 2 <ref:2605. p. 6
Where the paper says it

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.

30220#pg19>. The evaluation setup for optimization includes a budget of 500 flips from the same starting triangulations as TriSearch <ref:2605. p. 6
Where the paper says it

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.

30220#pg19>. The comparison tables for optimization results are provided in Tables 3 and 4 <ref:2605. p. 0
Where the paper says it

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.

p. 7
Where the paper says it

43% in 4D, against 8. 09% for the next-best baseline NLS, where the detailed aggregated result tables can be found in Appendix D.

30220#pg20>. The results show that removing simplicial information substantially worsens the controlled 4D results across all three objectives <ref:2605. p. 5
Where the paper says it

The ablation in Table 1 supports this choice. Removing simplicial information substantially worsens the controlled 4D results across all three objectives.

30220#pg9>. The ablation study confirms the necessity of d-simplicial information when making a flip decision <ref:2605. p. 7
Where the paper says it

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.

30220#pg9>. The paper acknowledges support from NSF grant DMS-2522495 and others <ref:2605. p. 9
Where the paper says it

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).

30220#pg11>.

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

Where the paper says it

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.

30220#pg7>. The framework's high-level structure is noted as appearing in phylogenetic tree search and rhombus tiling problems <ref:2605.30220#pg7>. The authors conclude that the method successfully navigates the flip graph by learning how to rank feasible moves based on global context and realized local subtriangulation <ref:2605. p. 8
Where the paper says it

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.

30220#pg3>. The paper's findings are significant for applying reinforcement learning to complex combinatorial geometry tasks where explicit enumeration is infeasible <ref:2605.30220#pg11>. The authors also suggest future work on parallelizing the geometric routine and learning FRST distributions in height space <ref:2605. p. 8
Where the paper says it

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.

30220#pg7>. The paper concludes that TriSearch provides a robust method for navigating the flip graph by leveraging local mathematical structure <ref:2605. p. 8
Where the paper says it

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.

30220#pg7>. The final results show that TriSearch achieves top performance on metric objectives in 3D and discovers more distinct Fine, Regular, Star triangulations of reflexive polytopes in 4D <ref:2605. p. 0
Where the paper says it

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.

30220#pg2>. The paper's overall contribution is the introduction of a circuit-supported action representation for triangulation optimization <ref:2605.30220#pg3>. The entire methodology is presented through Algorithm 1 <ref:2605.30220#pg7> and detailed model specifications are in Appendix B. p. 6
Where the paper says it

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.

4 <ref:2605.30220#pg18>. The paper provides a comprehensive search framework for triangulations in any fixed dimension <ref:2605. p. 2
Where the paper says it

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.

30220#pg7>. The paper's success across different objectives validates the unified search framework's power <ref:2605.30220#pg3>. The paper is a significant contribution to the field of learning methods for combinatorial optimization <ref:2605. p. 1
Where the paper says it

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.

30220#pg14>.

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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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

Related papers