acceptodds
Withdrawn from ICLR 2027

RadonBench: A Benchmark of Classical and Learning-Guided Search Techniques for Problems in Combinatorial Geometry

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Classical optimization and AI-based search offer complementary approaches to open problems in discrete mathematics, but a systematic comparison of these approaches on a common task is lacking. We benchmark five representative classical and AI-based methods on the integer Radon problem, which asks for large sets of lattice points that cannot be partitioned into two nonempty parts whose convex hulls share a lattice point. The Radon number is the smallest such that every -point subset of admits such a partition. The current bounds are and . Finding a Radon-independent set of 11 points in or 21 points in would raise the corresponding lower bound to 12 or 22. We propose RadonBench, which includes exhaustive extension, greedy local search, and task-specific adaptations of PatternBoost, AlphaZero, and AlphaEvolve-style program evolution. The three AI approaches respectively learn point proposals, guide Monte Carlo tree search with a set-attention policy and value network, and evolve candidate-generating programs. To compare their different output types, we report target recovery, the largest valid construction, and the number of shared Radon points in target-sized near misses, where zero certifies a valid construction. PatternBoost and AlphaZero-Radon construct Radon-independent sets with 10 points in and 20 points in , matching the current best-known sizes. At the open targets, AlphaZero-Radon and exhaustive extension reach a minimum of two shared Radon points, while greedy local search and AlphaEvolve-style program evolution reach one. None of the five methods finds a target-sized Radon-independent set. Thus, whether or remains open.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
AI for mathematics, discrete geometry, combinatorial optimization

Reviews

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

This work introduces a benchmark for searching for lattice points configurations with no integral Radon partitions. Mainly two targets are considered 11 points in 3D and 21 points in 4D. The paper compares multiple plausible approaches on this problem. None of the methods finds a valid configuration at either target.

Critical strengths
  • A concrete and relevant task.
  • The authors distinguish unsuccessful searches from nonexistence proofs and disclose differences in search domains and computational budgets. Overall the results seem to be reported carefully.
  • The considered approaches cover a broad spectrum: classical search, RL-guided tree search and LLM based program evolution etc.
Critical weaknesses
  • The evaluation provides very limited insights. All methods fail on the primary criterion, and it is unclear to me if a solution exists at all. Hence, it is difficult to interpret the results and distinguish whether the failure is due to an algorithm’s inductive bias, configurations, or just the nonexistence of a solution.

  • Furthermore, the task coverage is very narrow. The authors only consider open targets that are above known feasible cardinalities. I think the inclusion of known solvable tasks could improve the work and maybe help establish some meaningful differences between the approaches.

  • The presentation is very hard to follow in places.

Questions for authors
  • Which specific capabilities of AI models is Randobench intended to evaluate?
  • Do you have results for easier, solvable targets? How did you tune the methods compared on the presented targets?
1 comment
AuthorsOpenReview ↗

Response to Reviewer QCxx

Thank you for recognizing the concrete task, the careful reporting, and the breadth of methods, and for your questions on the scope of the evaluation. We respond below with:

  • the intended capability of the task (Q1);
  • the status of solvable targets and hyperparameter settings (Q2, Q3);
  • the interpretation of failures on an open problem (Q4);
  • presentation improvements (Q5).

[Q1] Which specific capabilities of AI models is RadonBench intended to evaluate?

[A1] Essentially we present a case study of a very difficult open problem in combinatorial geometry, on which none of the classical or ML/AI search methods we tested found a solution. The intended capability is geometric discovery beyond known constructions: whether a method can build a valid configuration larger than the best-known one, as judged by an exact verifier rather than an approximate score.

[Q2] Do you have results for easier, solvable targets?

[A2] No, not as separately declared targets; every reported run targets the open sizes. The only related evidence is a by-product of those runs. The two constructors start from no points (PatternBoost) or only the origin (AlphaZero-Radon), and both reach the best-known sizes, 10 points in Z3\mathbb{Z}^3 and 20 in Z4\mathbb{Z}^4 (Table 3, kmax⁡k_{\max}). The three fixed-target methods were not run on solvable targets. We agree that results on solvable targets would be useful as positive controls, and we plan to add them.

[Q3] How did you tune the methods?

[A3] We did not run a hyperparameter search for any method. All settings are fixed, listed in Tables 5–8, and shared across the 3D and 4D instances, so each reported result reflects a single untuned configuration per method.

[Q4] All methods fail and it is unclear whether a solution exists, so one cannot tell whether a failure comes from inductive bias, configuration, or nonexistence.

[A4] We agree that this is the main limitation of evaluating an open problem: when no method succeeds, a search failure cannot be separated from nonexistence of a mathematical example. The constructors' rediscovery of the best-known sizes shows that their pipelines work, but it does not resolve this ambiguity. The paper makes no nonexistence claim (Sec. 1, l. 106–107).

[Q5] The presentation is hard to follow in places.

[A5] We will add a plain-language overview of the problem and the evaluation before the technical sections.

Thank you again for your constructive questions!

Reviewer_YJs5OpenReview ↗
Rating
1
Confidence
3(−1)
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

The authors evaluate whether five existing search methods (among which AlphaZero-Radon is an adaptation of AlphaZero to the Radon number search task) can solve two open problems concerning Radon numbers, without using unified search budgets or search spaces. The results show that none of the methods can solve either problem.

Critical strengths

None

Critical weaknesses

This paper does not propose any new method. Although the title contains "Bench," it does not introduce a new dataset either. It merely evaluates the performance of five methods on open problems, finding that none of these methods can solve the problems, while the experimental settings used for comparison are also inconsistent. In short, this paper merely reports the experimental results obtained by the authors, without providing any substantive conclusions or contributions.

Questions for authors

What substantive contributions does this paper make?

2 comments
AuthorsOpenReview ↗

Response to Reviewer YJs5

Thank you for your direct questions about the contribution and the experimental setup. We respond below with:

  • a clarification of the contribution and scope of the paper (Q1, Q3);
  • the role of the method adaptations (Q2);
  • the rationale for protocol-specific settings (Q4).

[Q1] What substantive contributions does this paper make?

[A1] There are some combinatorial numbers that are incredibly difficult to compute (e.g., Ramsey numbers). Computing the integer Radon number is a less famous, but very difficult challenge. Our paper sets up the integer Radon problem as a verifiable search task and evaluates five method families against it. Each target lies one point above the largest known Radon-free configuration (11 points in Z3\mathbb{Z}^3, 21 in Z4\mathbb{Z}^4), so a success would improve the best known lower bound on the integer Radon number. The paper provides an exact verifier (Sec. 2, Alg. 1), task-specific adaptations of the five methods, and the released configurations, seeds, and outputs.

The main empirical observation is that the two learned constructors reach the best-known sizes (10 in Z3\mathbb{Z}^3, 20 in Z4\mathbb{Z}^4) from scratch but never exceed them, in 20 PatternBoost generations or in 200,000 AlphaZero-Radon trajectories. The problem is easy to state, yet r(Z3)r(\mathbb{Z}^3) and r(Z4)r(\mathbb{Z}^4) remain unknown (currently 11≤r(Z3)≤1711 \le r(\mathbb{Z}^3) \le 17 and 21≤r(Z4)≤6321 \le r(\mathbb{Z}^4) \le 63). In our runs, none of the five methods, classical or AI-guided, found an 11- or 21-point Radon-free configuration.

[Q2] The paper does not propose any new method.

[A2] No. The goal of the paper is not to propose a new method but to evaluate the quality of machine learning and AI techniques to solve difficult mathematical problems. This is important given that AI companies have solved many famous problems, but here we exhibit a combinatorial search problem that is quite difficult. Even the 3-dimensional integer Radon number is unknown. The methods we implemented are adapted to the task; for example, AlphaZero-Radon uses a permutation-invariant set-attention policy-value network over unordered point sets (Sec. 3.5).

[Q3] Despite "Bench" in the title, the paper does not introduce a new dataset.

[A3] We agree that "benchmark" is not the best description. The paper provides one very hard open problem, finding an 11-point Radon-free configuration in Z3\mathbb{Z}^3 or a 21-point one in Z4\mathbb{Z}^4, together with an exact verifier, fixed seeds, and runs from five method families. It is not a dataset of labeled examples or a suite for ranking methods.

[Q4] The experimental settings are inconsistent: search budgets and search spaces are not unified.

[A4] The paper states this explicitly (Sec. 4, l. 369–371; Sec. 6, Limitations). The methods produce different kinds of output and spend different units of work. The paper therefore reports what each declared protocol produced and does not rank the methods by efficiency.

Thank you again for your time and feedback!

Thank you for your detailed response. I understand and recognize that the main contribution of this paper is formulating the integer Radon problem as a verifiable search task and evaluating five method families on it.

Nevertheless, while I acknowledge the value of this contribution, I remain unconvinced that it is sufficient to meet the acceptance criteria of the conference. Therefore, I will maintain my original rating.

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

This paper presents a benchmark for constructing maximum-cardinality Radon-free lattice configurations. It runs a handful of methods on this benchmark: exhaustive extension, greedy local search, a task-adapted PatternBoost solver, AlphaZero-Radon, a single-agent AlphaZero-style MCTS solver with a task-specific set-attention network, and AlphaEvolve-style program evolution.

Critical strengths

None.

Critical weaknesses

This paper, as written, is only interesting to people who care about the integer Radon number. I believe this would be an extremely small portion of the ICLR audience. It is full of jargon and, as written, would not be interpretable or of interest to anyone who hasn't studied the integer Radon number before. I'll note that it's ok for benchmark papers to choose specific mathematical problems, but it's important to explain to the audience what the benchmark reveals about the evaluated methods. Do failures expose generalizable weaknesses in the evaluated methods---i.e., weaknesses that would generalize to other important problems? Are there ways we can improve the evaluated methods based on these failures? How does this benchmark highlight those failures when other benchmarks fell short? As written, I can't find insights in this paper that generalize beyond the very specific problem of constructing maximum-cardinality Radon-free lattice configurations.

Questions for authors

I included questions in the "Weaknesses" section above, but unfortunately, answering them wouldn't materially affect my assessment. The paper would need a very significant re-evaluation and rewrite.

1 comment
AuthorsOpenReview ↗

Response to Reviewer QMTr

Thank you for your feedback on the audience and the insights of the paper. We respond below with:

  • the relevance of the problem to the ML/AI community (Q1);
  • what the results show about the evaluated methods (Q2, Q3);
  • what the task makes observable (Q4).

[Q1] The paper is only of interest to people who study the integer Radon number, and it is full of jargon.

[A1] We acknowledge that the scope seems narrow, but the key point we are trying to drive for the ML/AI community is that some easy-to-state problems, like this one or the Ramsey numbers, remain open: none of the state-of-the-art methods we tested found an 11-point configuration, and it is unknown whether one exists. The problem is elementary to state: choose integer points so that no split into two groups gives two convex hulls that share an integer point (Fig. 1). We will add a plain-language overview and a short glossary.

[Q2] What does the benchmark reveal about the evaluated methods? Do the failures generalize?

[A2] The clearest observation is that both learned constructors reach the best-known sizes from scratch but never exceed them. Since it is unknown whether larger configurations exist, this observation does not by itself indicate a weakness of these methods. Radon-freeness is hereditary (closed under taking subsets), like the defining properties of cap sets and no-three-in-line sets. Whether the same pattern appears on those problems can therefore be tested directly; we do not claim that it does.

[Q3] Are there ways to improve the evaluated methods based on these failures?

[A3] Section 6 (l. 441–447) lists protocol-level changes suggested by the runs, such as coordinated multi-point moves for repair methods. These suggestions are untested.

[Q4] How does this benchmark expose failures that other benchmarks miss?

[A4] Each target lies exactly one point beyond the best-known construction, and every output is checked exactly. The task can therefore separate rediscovering a known size from going beyond it. Because all methods fail at the targets, this separation is currently observed only for the two constructors.

Thank you again for your comments!

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response to the AC and All Reviewers

We thank the AC and the reviewers for their time and feedback. We are encouraged that the reviewers recognized the following strengths:

  • The paper studies a concrete and relevant task (QCxx).
  • The results are reported carefully: unsuccessful searches are distinguished from nonexistence proofs, and differences in search domains and computational budgets are disclosed (QCxx).
  • The evaluated approaches cover a broad spectrum, from classical search to RL-guided tree search and LLM-based program evolution (QCxx).

Below we summarize our responses to the main concerns:

Scope: one very hard open problem. The paper presents one easy-to-state open problem in combinatorial geometry: finding an 11-point Radon-free configuration in Z3\mathbb{Z}^3 or a 21-point one in Z4\mathbb{Z}^4, either of which would improve the best known lower bound on the integer Radon number. Together with the problem, the paper provides an exact verifier, fixed seeds, and runs from five classical and AI-guided method families. It is not a dataset, and we agree that "benchmark" is not the best description.

What the results show. The two learned constructors reach the best-known sizes (10 points in Z3\mathbb{Z}^3, 20 in Z4\mathbb{Z}^4) from scratch but do not exceed them, and none of the five methods found an 11- or 21-point configuration. Because it is unknown whether such configurations exist, this outcome does not by itself indicate a weakness of any method, and the paper makes no nonexistence claim.

Experimental setup. Search budgets and search spaces differ across methods because the methods produce different kinds of output; the paper therefore reports what each declared protocol produced and does not rank the methods by efficiency. No hyperparameter search was run for any method. The runs do not include separately declared solvable targets; we agree that such results would be useful as positive controls and plan to add them.

In addition, we have uploaded a revised manuscript that adds a plain-language overview of the problem (Section 1) and a short glossary (Appendix E) to make the paper accessible beyond discrete geometry. All changes are highlighted in blue; no other part of the paper has been changed. Line numbers in our responses refer to the revised manuscript.

We hope these clarifications address the reviewers' concerns, and we are happy to answer any further questions.

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

Related papers

Discussion (0)

Sign in to comment.