acceptodds
Under review as a conference paper at ICLR 2027

CayleyPy: Scalable Computation and Conjecture Discovery for Cayley and Schreier Graphs

Abstract

We present the first public release of CayleyPy, an open-source Python library for large-scale computation with Cayley and Schreier graphs. Unlike general-purpose computer algebra systems such as GAP and Sage, CayleyPy is optimized for massive graph exploration and enables computations on instances far beyond the practical range of existing tools, with orders-of-magnitude speedups in our experiments. The library forms the computational backbone of an AI-assisted conjecture-discovery pipeline that combines fast graph algorithms with reinforcement-learning-guided search over generating sets. Using CayleyPy, we obtain approximately 200 new conjectures on diameters and growth functions of Cayley and Schreier graphs. Our main empirical discovery is a quasi-polynomiality phenomenon for Cayley graphs of symmetric groups: for many natural families of generators, the diameter appears to be governed by a small collection of linear or quadratic polynomials indexed by congruence classes of n mod s. We formulate this as a general quasi-polynomiality hypothesis, suggesting that structured diameter problems may admit efficient closed-form solutions despite the general computational hardness of diameter computation. We further propose a sharpened Babai-type conjecture for undirected Cayley graphs of symmetric groups, predicting that every undirected Cayley graph of permutation group has diameter at most n^2/2 + 4n. This improves the expected constant in known (O(n^2))-type bounds. Our reinforcement-learning-guided searches identify explicit candidate extremal generator families, related to involutions arranged in a “square with whiskers” pattern, and exhaustive search verifies their optimality among tested instances for all (n \leq 15). We also conjecture an answer to a question posed by V.M.Glushkov in 1968 on directed Cayley graphs generated by a cyclic shift and a transposition. Finally, for nilpotent groups, we formulate conjectural improvements to results of J.S.Ellenberg on upper unitriangular groups, predicting linear dependence of the diameter on p. Together, these results demonstrate how scalable symbolic-combinatorial software and reinforcement learning can support systematic conjecture discovery in group theory.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Cayley graphs, groups, RL

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_hKToOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents a framework for exploring large Cayley and Schreier graphs through scalable exact computation and learning-guided search. The authors report substantial computational speedups for exact graph-growth calculations and show that learned heuristics can improve search performance, with Bellman refinement providing additional gains. The framework is used to generate and test a large catalogue of conjectures on graph diameters, growth statistics, antipodes, and extremal generator families. Notable mathematical outputs include a fixed-conjugacy-type quasi-polynomiality conjecture, a proposed Babai-type diameter bound, and conjectures related to the Glushkov and unitriangular-group settings. Overall, this is an interesting AI4Math contribution that combines scalable exact computation with learning-guided exploration and mathematically verifiable outputs.

Critical strengths

1. The combination of scalable algebraic computation with learned search and verifiable certificates is a useful AI4Math design principle.

2. The idea seems novel, and the software contribution could be valuable research infrastructure if the reported scalability and correctness are validated. Moreover, several structural conjectures appear mathematically interesting and could motivate follow-up work beyond the immediate benchmarks.

3. The paper is appropriately cautious in several places about distinguishing search outputs from proofs and about the unresolved question of whether learning actually increases the rate of discovery.

Critical weaknesses

1. Correctness, internal consistency and explainability

I found enough concrete inconsistencies that my confidence in some parts is reduced. Examples include:

  • Conflicting CPU benchmark tables: Table 11 and a later unlabeled table report substantially different timings for the same families and sizes.

  • A table on page 27 is labeled as undirected but reproduces the directed diameter values.

  • The generalized symmetric-group section contains apparent algebraic/notation errors, including the codomain of parity maps, an “even n” versus “even m” inconsistency, and a mismatched group relation in the proof.

  • The discussion of Coxeter generators and braid groups is inaccurate as written.

  • The odd-n antipode discussion contradicts its own n=5 example.

  • The LARX+inverse odd-n formula has inconsistent denominators between the catalogue and detailed section.

  • The LSL section should clarify whether it is treating a directed graph, an inverse-closed graph, or a symmetrized operator, especially in the spectral discussion.

  • There are also several instances of visibly unfinished text, such as “Current work:” and “We were able to achieve ...”. More generally, the manuscript would benefit from careful proofreading to remove incomplete sentences, grammatical issues, and other presentation inconsistencies.

I should emphasize that these are only some of the issues related to inconsistencies in the manuscript. Therefore the authors should review the manuscript carefully and rigorously to ensure that no inconsistencies remain. Many of these issues may be individually repairable, but collectively they raise concerns about the rigor of the study. I therefore strongly encourage the authors to conduct a systematic check across the manuscript.

Beyond correctness and internal consistency, I think the paper would benefit from a stronger emphasis on explainability and mathematical intuition. A particularly valuable aspect of AI4Math systems is not only that they search efficiently or generate candidate conjectures, but that they help expose new structure that can guide human understanding. In the current manuscript, the outputs are often verifiable and some appendices do provide useful mathematical interpretation, but for several headline discoveries it remains unclear what genuinely new intuition the learning component reveals. I would encourage the authors to explore this more explicitly—for example, by identifying structural or algebraic features associated with difficult/extremal states, explaining why particular scaling or residue-class patterns emerge, or extracting interpretable principles from the learned search. Incorporating such insights more directly into the main presentation would strengthen both the mathematical contribution and the broader AI4Math significance of the work.

2. Novelty and positioning

The paper would benefit from distinguishing more clearly between its three sources of novelty: the scalable graph calculations, the learning-guided search procedure, and the resulting mathematical discoveries. In my view, the main novelty is mostly on the integration of learned search with scalable exact algebraic computation and independently verifiable mathematical evidence (not on particularly new RL method for example). Clarifying which mathematical discoveries specifically depended on the learning component would strengthen the paper's AI4Math positioning.

Some mathematical novelty statements should also be calibrated more carefully. For example, the Babai-type discussion should distinguish conjectural polynomial behavior from proved general diameter bounds, and several literature attributions should be tightened. More broadly, it should be made more explicit which of the conjectures actually depended on learning.

I also noticed several issues with the existing literature attribution that would benefit from correction or further clarification. Some illustrative examples include, but are not limited to:

  1. “In line with the literature, our computations confirm the exact formula Dn=⌊n2/4⌋D_n=\lfloor n^2/4\rfloor.” It would be helpful to provide the specific literature reference supporting this exact formula.

  2. “For nilpotent groups, we formulate conjectural improvements to results of J. S. Ellenberg on upper unitriangular groups over ...” It would be helpful to include the relevant citation to the work of J. S. Ellenberg being referred to here.

  3. “We also conjecture an answer to a question posed by V. M. Glushkov in 1968 on directed Cayley graphs generated by a cyclic shift and a transposition.” It would be helpful to provide the corresponding citation for the original Glushkov result/question.

  4. The Babai-type framing would benefit from more clearly distinguishing proved and conjectural bounds. Babai–Seress and Helfgott–Seress provide respectively subexponential and quasipolynomial general upper bounds, while a universal quadratic bound for arbitrary generators remains conjectural. Thus, n2/2+4nn^2/2+4n may be more accurately presented as a sharpening of a conjectural O(n2)O(n^2) prediction rather than as an improvement in the constant of an established O(n2)O(n^2) theorem.

Beyond correcting and clarifying the existing references, I believe the related-work discussion could benefit from broader coverage of learning-assisted mathematical discovery and automated conjecturing in graph/combinatorial settings. Relevant examples include:

  • Adam Zsolt Wagner (2021), “Constructions in Combinatorics via Neural Networks.” Uses reinforcement learning to search for constructions and counterexamples to open problems in extremal combinatorics and graph theory.

  • Randy Davila (2024), “Automated Conjecturing in Mathematics with TxGraffiti.” Develops an automated conjecturing system based largely on relationships between graph invariants.

  • Ján Pastorek (2026), “AutoGraphForge: Towards Automated Graph Theory Discovery.” Develops a graph-theoretic pipeline combining conjecture generation, counterexample search, and formal verification.

  • Hakan Akgün et al. (2026), “KnottedGraph: Scalable Knotted-Graph Topology for Scientific and Mathematical Discovery.” Combines scalable computation of graph-topological invariants with LLM-assisted discovery of closed-form mathematical relations.

  • Giorgi Butbaia et al. (2026), “Hierarchical Reinforcement Learning for Sparse-Reward Search in Commutative Algebra,” ICML 2026. Casts the search for counterexamples to mathematical conjectures as sparse-reward reinforcement learning on graph-structured search spaces.

These works, among other related studies that the authors may consider, would help place the present contribution more clearly within the broader literature on learning-assisted and automated mathematical discovery.

Questions for authors

1. Which mathematical discoveries genuinely required learned search rather than exact BFS and formula fitting alone?

2. What explainability or interpretability analyses have the authors explored to understand what the learned model is capturing mathematically (e.g., probing correlations with algebraic invariants such as cycle structure or parity, analyzing which generator choices drive the score, or extracting symbolic or structural rules from highly ranked states)?

3. How automated is the conjecture-generation stage itself? In particular, which parts of the process—identifying patterns, proposing functional forms, selecting candidate extremal states, and formulating conjectures—are performed automatically, and which rely on manual mathematical inspection?

Reviewer_SP67OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper gives a library for exploration/search with Cayley and Schreier graphs. It has BFS for exact search, a learned search, which is a beam search guided a learned heuristic, and then makes a number of conjectures about diameter and growth formulas.

Critical strengths

The main strength is this is a useful piece of open-source software, and the catalog of exact data is a great resource. The GPU BFS is faster than general math software, and the data is valuable for future math work.

The paper also does a good job carefully documenting the different types of evidence, and in isolating the contribution of the learned heuristic.

Critical weaknesses

There are a number of claims in the abstract that I was unable to find, such as the “sharpened Babai-type conjecture”, or the n<=15 verification for the extremal generator families. Also J.S.Ellenberg is never cited despite being mentioned in the abstract.

Next, the main empirical discovery mentioned in the abstract "for many natural families of generators, the diameter appears to be governed by a small collection of linear or quadratic polynomials indexed by congruence classes of n mod s” is a much broader statement than the one in the paper. The conjecture in the paper is also supported only by things from the literature, and I don’t see any new computational evidence for unions of classes or different cycles types.

On the ML side of things, many of the results “were previously also reported in a related manuscript” and the results also contain “previously reported cube experiments.” Also the fact that the "original result JSON and complete move sequences are no longer available" is concerning. Finally, as the paper is clear about, the RL evidence is not strong.

Questions for authors

Where are all of the results promised in the abstract? If they are not in the paper, the abstract should be revised.

Which experiments are new and which were in “related manuscripts”?

How many entries in the table are new conjectures? What are the “approximately 200” mentioned in the abstract?

What is the computational evidence for Conjecture 1 that is new, not from the literature?

You write that D(U4(m),X4±)=3m/2D(U_4(m),X_4^\pm)=3m/2 holds for sufficiently large even mm, and the small values you give don’t match the formula: where does this formula start? What data supports it?

Reviewer_b2rhOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper uses search algorithms and RL to analyze Cailey graphs that are much larger than previous work and proposes new conjectures related to Cailey graphs.

Critical strengths
  • The paper proposes new conjectures
  • It could address graphs larger than previous work
Critical weaknesses
  • It is hard to follow for researchers not familiar with Cailey graphs
  • The search algorithm on the cube is not compared to IDA* with pattern databases
Questions for authors
  • Why did not you compare to the state of the art on the cube?
  • Can you make the paper understandable for people not familiar with Cailey graphs?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.