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

Xiaoan Xu; Ethan X. Fang; Jesus A. De Loera; Junwei Lu; Luze Xu

cs.LGOct 23, 2026

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

Authors: Xiaoan Xu, Ethan X. Fang, Jesus A. De Loera, Junwei Lu, Luze Xu

Organizations: Department of Electrical and Computer Engineering, Duke University. · Department of Biostatistics and Bioinformatics, Duke University. · Department of Mathematics, University of California, Davis. · Department of Biostatistics, Harvard T.H. Chan School of Public Health. ·

Abstract

Classical optimization and learning-guided search offer complementary approaches to open problems in discrete mathematics, but their outputs are difficult to compare when search spaces, validity checks, and stopping rules differ. We present RadonBench, a benchmark for constructing maximum-cardinality Radon-free lattice configurations: finite subsets of $\mathbb{Z}^d$ admitting no integral Radon partition. It remains open whether Radon-free configurations with $11$ points in $\mathbb{Z}^3$ or $21$ points in $\mathbb{Z}^4$ are possible. If they exist, they would improve the corresponding lower bounds on the integer Radon numbers. We compare exhaustive extension, greedy local search, PatternBoost, AlphaZero, and AlphaEvolve. All outputs use one success predicate: a convex target-sized configuration succeeds exactly when its number of integral Radon points is zero. PatternBoost and AlphaZero construct verified Radon-free configurations of sizes $10$ and $20$ , one point short of the respective targets; AlphaZero's best convex target terminals have two integral Radon points in both dimensions. Exhaustive extension over fixed seeds and declared finite search boxes likewise reaches a minimum of two integral Radon points. Greedy local search and AlphaEvolve each produce target-sized near misses with one integral Radon point. No audited run reaches zero. These results establish reproducible near-miss baselines over explicitly scoped search domains.

Figures & tables

Figure 1: The search problem. (a) Onn’s five-point configuration in

\mathbb{Z}^{2}

is Radon-free ( Onn, 1991 ) . (b) An

11

-point near-miss in

\mathbb{Z}^{3}

found by the declared local-search experiment. The displayed split has the single shared lattice point

p=(3,2,0)

, hence

n_{\mathrm{rp}}=1

; success requires

n_{\mathrm{rp}}=0

Instance	Known feasible configuration	Method	Coordinate domain
$\mathbb{Z}^{3}$ , target $11$	10-point Radon-free	Exhaustive extension	Added point: $20\!\times\!20\!\times\!8$ box
		Greedy local search	All points: $20\!\times\!20\!\times\!5$ box
		PatternBoost	All points: $20\!\times\!20\!\times\!5$ box
		AlphaZero-Radon	All points: $20\!\times\!20\!\times\!5$ box
		AlphaEvolve-style	No finite box
$\mathbb{Z}^{4}$ , target $21$	20-point Radon-free	Exhaustive extension	Added point: $20\!\times\!20\!\times\!5\!\times\!5$ box

Table 1: Open targets, known feasible configurations immediately below them, and the coordinate domain used by each method. Box dimensions are side lengths. “No finite box” means that the evaluator accepts arbitrary finite integer coordinates. The method-specific domains are not box-matched.

Method	Starts from	Core idea
Cardinality construction : add points while keeping $n_{\mathrm{rp}}=0$ .
PatternBoost	No points	Trains a Transformer ordering prior; keeps only convex, Radon-free prefixes.
AlphaZero-Radon	No points	Uses a set-attention policy and PUCT to add points; scores any convex configuration that reaches $N$ points under its evaluator.
Fixed-target optimization : minimize $n_{\mathrm{rp}}$ over $N$ -point configurations.
Exhaustive extension	A Radon-free set of $N-1$ points	Tries every location for one final point in a finite box.
Greedy local search	A convex configuration of $N$ points	Moves one point at a time whenever the number of integral Radon points decreases.

Table 2: High-level view of the five methods. Gray bands separate the two search objectives; implementation details appear in the subsections below.

Method	Found?	$k_{\max}\uparrow$	$r_{\min}(N)\downarrow$
$\mathbb{Z}^{3}$ , target $N=11$
PatternBoost	No	$10$	–
AlphaZero-Radon	No	$10$	$2$
Exhaustive extension	No	–	$2$
Greedy local search	No	–	$1$
AlphaEvolve-style	No	–	$1$

Table 3: Verified outcomes at the two open targets. Found denotes a verifier-accepted target-sized output; a dash denotes an inapplicable output type.

Figure 2: Method-native construction progress. (a) For PatternBoost, solid curves show the mean cardinality among the 50 retained configurations and dotted curves show the retained maximum at each generation. (b) For AlphaZero-Radon, curves show the mean number of post-origin placements per self-play trajectory, smoothed with a 50-iteration moving average. Values are normalized by the open target cardinality in (a) and by the post-origin horizon

N-1

in (b). The dashed line marks target completion. Horizontal axes are method-specific and do not represent matched compute; each curve summarizes one complete declared run.

Figure 3: Fixed-target search outcomes under the current declared protocols. (a) For exhaustive extension, bars show the distribution of the minimum

n_{\mathrm{rp}}

obtained after searching the full declared box for each of 50 fixed seeds. (b) For greedy local search, curves show empirical CDFs of the initial and terminal scores over 1,000 selected starts. (c) For AlphaEvolve-style program evolution, curves show the best-so-far score over 20 completed mutations; the first score-one program appears at mutation 7 in 3D and 11 in 4D. Colors identify the dimension. Seeds, starts, and mutations are protocol-native units and do not represent matched compute.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Instance	Seeds	Tested	Convex targets
$\mathbb{Z}^{3},\ N=11$	50	159,500	85,913
$\mathbb{Z}^{4},\ N=21$	50	499,000	173,355

Appendix

Table 4: Coverage of the declared exhaustive add-one-point domains. Tested excludes positions occupied by the fixed seed; convex targets are the extensions scored by the verifier.

Figure 4: Representative learning-guided 10-point configurations in 3D. PB-A–PB-D (circles) are PatternBoost outputs; AZ-A–AZ-D (squares) are AlphaZero-Radon construction prefixes. Color encodes height

z

, and each heading gives the layer-count vector from

z=0

z=4

. Gray edges and translucent faces show the convex-hull scaffold. To keep both compact AlphaZero-Radon configurations and box-spanning PatternBoost configurations legible, panels use their own displayed

x

–

y

limits, with the true limits shown by the ticks; the

z

axis is visually expanded. Every panel is a distinct Radon-free configuration. The examples illustrate structural diversity rather than empirical profile frequencies.

Parameter	Value
Initialization draw cap	$100$ per extension request
Evaluated starts / seeds	$1{,}000$ per dimension / 3D $20260819$ , 4D $20260815$
Neighbourhood	$3^{d}-1$ full-coordinate radius- $1$ moves (3D: 26; 4D: 80)
Point / direction order	stored index / lexicographic
Acceptance / plateaus	strict $n_{\mathrm{rp}}$ decrease / disallowed
Coordinate bounds during descent	3D: $[0,19]^{2}\times[0,4]$ ; 4D: $[0,19]^{2}\times[0,4]^{2}$

Appendix

Table 5: Greedy local-search hyperparameters shared across dimensions.

Parameter	Value
Transformer architecture
Causal blocks / attention heads	$4$ / $4$
Embedding / FFN width	$128$ / $512$
Activation / normalization	GELU / pre-LN
Dropout	$0$
Training

Appendix

Table 6: PatternBoost hyperparameters.

Parameter	Value
Output cap	$32$ candidates
Reference seeds	16 cataloged $(N-1)$ -point records
Reference-selection seed / program RNG	$2026$ / NumPy PCG64 seed $42$
Internal oracle allowance	$1{,}000$ find_rps calls per program
Convexity calls / evaluator replay	uncharged / outside internal allowance
Evolution mutations / target score	$20$ per dimension / $1$

Appendix

Table 7: AlphaEvolve-style program-evolution settings.

Parameter	Value
Search and trajectory generation
Self-play worker processes	$32$
Training iterations	$2{,}000$
Self-play games / iteration	$100$
MCTS reads / move	$500$
PUCT constant $c_{\mathrm{puct}}$	$1.0$

Appendix

Table 8: AlphaZero-Radon hyperparameters shared across dimensions.

Figure 5: Training diagnostics for the complete 2,000-iteration AlphaZero-Radon runs. The top and bottom rows show the 3D (

N=11

) and 4D (

N=21

) instances, respectively. Curves are 50-iteration moving averages. The trajectory panels show only the mean trajectory length; the dashed line is the full horizon of 10 or 20 policy-selected placements after the fixed origin.

Combinatorial Optimization

Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.

See all 386 papers

Geometry-Aware MCTS for Extremal Problems in Combinatorial Geometry
Jun 24, 2026Luoning Zhang, Xu Zhuang, Tianhao Wang +1Symmetry Breaking Combinatorial Optimization
Department of Mathematics, University of California, Irvine
New Bounds for Zarankiewicz Numbers via Reinforced LLM Evolutionary Search
May 1, 2026Jay Bhan, Nicole Nobili, Patrick LangerGraph Construction
ETH Zürich Zürich, Switzerland 8092 · Stanford University Stanford, CA 94305
Reinforced Generation of Combinatorial Structures: Ramsey Numbers
Mar 10, 2026Ansh Nagda, Prabhakar Raghavan, Abhradeep ThakurtaAutomated Algorithm Discovery
University of California, Berkeley, and Google DeepMind. · Google. · Google DeepMind.

Jun 24, 2026J/K move · Enter open · S save

Geometry-Aware MCTS for Extremal Problems in Combinatorial Geometry

Luoning Zhang, Xu Zhuang, Tianhao Wang, Nathan Kaplan

Department of Mathematics, University of California, Irvine

Symmetry Breaking Combinatorial Optimization Monte Carlo Tree Search

Open paper AskPDF arXiv

We study certain extremal problems in combinatorial geometry that ask about configurations of points in an

n \times n

grid that satisfy strict, global geometric constraints. Classical exact solvers suffer from combinatorial explosion for these types of problems, and standard reinforcement learning and transformer-based models struggle with the sparse reward "validity cliff" and quadratic token-consumption limits. To overcome these bottlenecks, we propose a Geometry-Aware Monte Carlo Tree Search (MCTS) framework. Our approach strictly enforces geometric constraints through incremental updates to the feasible action space. For constraints about collections of collinear points, like those that occur in the classic No-Three-in-Line problem (Max-N3IL), this mechanism reduces the constraint checking complexity from

O(n^3)

O(n^2)

. To improve search efficiency, we exploit geometric symmetries in two ways: canonical pruning during node expansion to reduce the branching factor, and symmetric batch transitions to accelerate the discovery of promising configurations. We perform extensive experiments and establish new best-known computational results on five out of six of the problems that we considered. Notably, for Max-N3IL we find configurations of size roughly

1.8 n

for grids of size

82 \le n \le 119

. For the Smallest Complete Set problem, we find configurations of size roughly

0.95 n

, providing new upper bounds within the tested grids. This work establishes Geometry-Aware MCTS as a highly adaptable framework for discovering novel configurations in combinatorial geometry.

Abstract

Combinatorial Optimization

Explore similar work

Geometry-Aware MCTS for Extremal Problems in Combinatorial Geometry

New Bounds for Zarankiewicz Numbers via Reinforced LLM Evolutionary Search

Reinforced Generation of Combinatorial Structures: Ramsey Numbers