acceptodds
Under review as a conference paper at ICLR 2027

From Local Rewards to Recursive Gains: Hybrid AI Search for C₄-Free Hypercubes

Abstract

Erdős Problem #86 asks how many edges of the -dimensional hypercube can be retained without forming a -cycle. AI-assisted search for recursive constructions must decide both where to search in this exponentially large space of coupled constraints and what to value, since immediate edge count can misrank seeds by their recursive potential. We present a hybrid system with two modes over compact symmetry-quotient states. A frozen language model proposes typed search actions that constraint programming executes and an independent verifier certifies; a low-dimensional mode saturates within one dimension and hands its verified seed pool to a high-dimensional mode, which a jump cycle reaches on already-computed recursive values. Both modes share the proposer, the verifier and a fitted head; the high-dimensional mode adds an analytic, exactly computed recursive advantage under the classical Brass–Harborth–Nienborg (BHN) lift to the score, and these values feed back into repair objectives and retention. The archive shows that a recursive state does not fix graph structure and that seeds with fewer edges can produce stronger descendants: a searched seed starts 1,024 edges below the classical seed yet exceeds its same-template rollout by 12,288 edges after one lift and stays ahead at the next two depths. Combining complementary seed lineages yields a construction family that provably matches or exceeds the refined BHN benchmark for every . Across , six independently verified seeds realize the archive envelope, with strict improvements in 13,805 dimensions (84.3%). These results connect structural exploration to high-dimensional construction guarantees through template-specific recursive value.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
AI-assisted mathematical discovery, adaptive search, neurosymbolic AI, representation learning.

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_sxwhOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper presents a hybrid AI system for constructing C4C_4-free subgraphs of hypercubes. The system uses a frozen language model to propose typed actions, executes them through constraint programming, and has an independent verifier to validate the outputs. Search combines immediate gain, a fitted value head, and exact Brass-Harborth-Nienborg value. Main results include a reversal in the ranking order when comparing rankings based on immediate edge counts versus those based on recursive values. Furthermore, within the reported range, a class of subgraphs constructed by this system outperformed the results of the improved BHN method in a 13805-dimensional hypercube.

Critical strengths
  1. The construction results are verifiable. The compact state n,E,Pn,E,P supports precise recursive computation, and the primary finite-range counts can be reproduced based on the provided distribution profiles.
  2. The motivation for recursive computation is clear. Section 5 shows that a seed with 1024 fewer edges produces 12288 more edges after one identical lift. This supports retaining information beyond immediate edge count.
Critical weaknesses
  1. The benefits of the controller have yet to be fully substantiated. Appendix M and Figure 10 report no improvement over the archived baseline envelope. As shown in Figure 11, the LLM proposer has worse downstream top-1 regret than the random proposer. Figure 7 demonstrates that the value head improves ranking performance; however, the paper does not explicitly establish whether recursive feedback can enhance construction quality or reduce solution costs under equal budgets.
  2. The comparison values are inconsistent. Appendix Q reports integer average edge counts, so rounding in Eq. (8) cannot explain the ''+1'' differences in Table 11. For example, the six listed roots give 3328 at n=10, whereas the archived envelope is 3329. At n=13, the envelope and ''this work'' entries differ by 129 edges, contrary to Appendix P’s ''within a single edge'' statement.
Questions for authors
  1. Which equal-budget comparison isolates the contribution of λΦ\lambda\Phi, while keeping the proposer, value head, and starting states fixed?
  2. Of the six roots presented in Table 12, which were newly discovered by the controller proposed in this paper, and which were already known?
  3. How do you reconcile Table 11 with the recurrence results, including the ''this work'' value of 33664 at n=13?
  4. Please specify the language model, prompt, sampling settings, λ\lambda parameter, stopping criteria, and the extent of human involvement required to reproduce this search process.
Reviewer_E3i3OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper reports an advances on mathematical problem. AI methods are used to improve search and combined with more classical methods.

Critical strengths

The paper provides quite concrete advances on a mathematical problem. AI methods are used as a part of the solution.

Critical weaknesses

It is difficult to judge for me how big is the mathematical advance, especially in the current situation when OpenAI resolved hundreds conjectures. Also is not so clear how critical is AI component in the solution.

Questions for authors

Can the authors provide more clear comparison that AI component is somewhat critical or important ?

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

This paper is studying Erdos problem #86. The claims of the paper are that it introduces a representation for verifiable search with recursive evaluation and certified results. But, I found the paper opaque and would not have drawn these conclusions from the text.

Critical strengths

The paper claims verified results improving the studied Erdos problem.

Critical weaknesses

I found this paper to be unreadable. The problem (C_4-free subgraphs of Q_n) is never defined in the paper (even in the appendix), thus the paper is not self-contained.

The paper has little exposition. It is mostly composed of bolded headings with snippets of text in each section. The paper seems to assume that the reader is intimately familiar with the problem being studied.

To illustrate this, consider the first paragraph of the second section of the paper, which in a typical paper should be understandable by most readers. This section starts with:

“The hypercube has 2^n vertices and n2^{n-1} edges, giving 2^{245,760} candidate edge subsets already at n=15. Every C_4 is a coordinate square, and each edge belongs to n-1 such squares, so feasibility couples local edits across the graph. We expose symmetry orbits as the decision units of AI-assisted search.”

In order, this brings up such questions as:

  1. What hypercube?
  2. Why does it have this number of vertices and edges?
  3. Please define C_4.
  4. Why is the C_4 a coordinate square?
  5. Why does each edge belong to n-1 squares?
  6. What is feasibility in this problem?
  7. What does it mean to couple local edits?
  8. What are symmetry orbits?
  9. How do you expose them?
  10. What is the precise structure of the AI search and what role to decision units play?

Perhaps I don't know enough about the particular Erdos problem being studied, and should go study it for many hours before trying to read this paper. But, I expect that papers at ICLR are more self-contained and at least make some attempt to define their problems clearly. Thus, I think this paper has little to offer to most humans attending the conference hoping to learn from the work.

Adding to this, there are many well-established types of search. (Depth-first, breadth-first, branch and bound, etc). It would seem the paper is using some sort of depth first search where the AI portion is helping to make decisions about branching. If this is the case, the paper should say this plainly and engage with that literature. The reference list is astonishingly short. It does not engage with almost any historical literature on search. Even if the paper were to be perfectly clear, it would require a larger engagement with existing literature.

I have pictures of many posters from ICAPS 2026 that involve search in some way. Just searching for the word "search" in the title of 2026 papers would turn up many of these. There have also been many papers on job shop scheduling (such as Smit et al, 2026) which involve search in some way. The point of a paper is not just to make a scientific advancement, it is also to relate that advancement to other work being done in the field. Even if the work is not directly relevant, the situating the work helps understand how the contributions might apply elsewhere.

Questions for authors

There are no questions the authors could answer that would change my assessment of the paper. The paper would need to be re-written to be more accessible.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.