0.3.0 release card: score-based search

Release card

Score-based search

0.3.0

We compare three score-based searches with packages that implement them: XGES with xges, and Tabu search and hill climbing with bnlearn. XGES returns the same graph as xges on every dataset, with or without its extended search, and runs up to 140x faster with it. Tabu search and hill climbing return the same equivalence class as bnlearn on most datasets and run up to 561x and 906x faster. We support all three from 0.3.0.

Graph agreement does not ensure accuracy. From 50 variables on, Tabu search and hill climbing return graphs with more errors than the empty graph’s in both packages, with ten samples per variable (see Known limits). You can find speedups and accuracy in the summary, and measurement and scoring definitions in how to read the results. These results apply to the measured workloads; speed and accuracy depend on the data, settings, and hardware.

Summary

xges and bnlearn are the baselines. We report every paired speed ratio, regardless of accuracy.

Speed.

Method	Compared with	Variables (d)	Cores per fit	Andrey speedup
XGES	xges	25-200	1	3.95-140x
XGES without the extended search	xges	25-200	1	1.13-6.35x
Tabu search	bnlearn	10-800	4	2.38-561x
Hill climbing	bnlearn	10-800	4	3.60-906x

Speedup over xges and bnlearn

Method

XGESXGES without the extended searchTabu searchHill climbing

25 variablesmean degree 23.95x

50 variablesmean degree 210.9x

100 variablesmean degree 243.2x

200 variablesmean degree 2140x

25 variablesmean degree 45.25x

50 variablesmean degree 415.5x

100 variablesmean degree 442.0x

200 variablesmean degree 489.3x

25 variablesmean degree 21.34x

50 variablesmean degree 22.23x

100 variablesmean degree 23.72x

200 variablesmean degree 26.35x

25 variablesmean degree 41.13x

50 variablesmean degree 42.23x

100 variablesmean degree 43.23x

200 variablesmean degree 43.77x

10 variables2.54x

20 variables2.38x

50 variables5.63x

100 variables16.6x

200 variables55.3x

400 variables176x

800 variables561x

10 variables5.27x

20 variables3.60x

50 variables6.13x

100 variables19.3x

200 variables70.6x

400 variables231x

800 variables906x

Each bar is the package's median time divided by Andrey's on the same dataset, the median over five datasets. Each method's bars share its own scale.

Accuracy.

Method	Compared with	Accuracy
XGES	xges	Same graph on 40 of 40 datasets
XGES without the extended search	xges	Same graph on 40 of 40 datasets
Tabu search	bnlearn	Same equivalence class on 31 of 35 datasets
Hill climbing	bnlearn	Same equivalence class on 31 of 35 datasets

Tabu search and hill climbing each return a different equivalence class from bnlearn on four datasets, all with 50 or more variables.

How to read the results

Data. We evaluate every method on linear_gauss_er: Erdos-Renyi directed acyclic graphs (DAGs) with linear mechanisms, Gaussian noise, standardized data, and n = 10d samples for d variables. XGES runs at mean degrees 2 and 4, on 25 to 200 variables with both packages and at 500 and 1,000 with Andrey only. Tabu search and hill climbing run at mean degree 2, on 10 to 800 variables with both packages and at 1,600 and 3,200 with Andrey only. There are five seeds per size and mean degree.

Accuracy. We score each graph by its structural Hamming distance (SHD) to the true completed partially directed acyclic graph (CPDAG); a DAG, as bnlearn returns, is scored through its CPDAG. Lower is better. The empty graph’s SHD is the number of true edges. “Same graph” means equal structure_hash values: both packages return CPDAGs with the same edges and the same marks. For Tabu search and hill climbing, “same class” means the same Markov equivalence class, with the same skeleton and v-structures, because bnlearn returns DAGs and Andrey returns CPDAGs.

BIC. We rescore every graph with Andrey’s BIC on the data it was fitted on, in deviance units, so both packages are compared on one scale; lower is better. For XGES, the BIC gap is the returned graph’s BIC minus the true graph’s: below zero, the returned graph scores better than the truth. For Tabu search and hill climbing, “BIC vs hill climbing” is the fit’s BIC minus Andrey hill climbing’s on the same dataset: below zero, the fit scores better than hill climbing. SHD and BIC are medians over datasets.

Timing. Times are seconds per fit, the median over datasets of each dataset’s median over its repeats. XGES fits once per dataset; Tabu search and hill climbing fit three times per dataset up to 400 variables and once from 800. For each dataset, we divide the package’s median time by Andrey’s, then report the median of these paired ratios. This need not equal the ratio of the displayed median times. Every timed fit compared across packages follows one untimed warm-up fit of the same solution, and no fit reached its time limit. For Tabu search and hill climbing, memory was capped at 30,000 MB per fit. Times and ratios have three significant figures and BIC values two decimals, as in the summary.

Hardware. XGES fits ran on an AMD EPYC 7713 64-Core Processor with 1 core per fit, and Tabu search and hill-climbing fits on an Intel Core i7-7820X with 4 cores per fit. Ratios apply within each comparison and do not transfer between machines.

Recorded campaign

Comparison	d	Andrey build	Measured package versions
XGES, XGES without the extended search	25-200; 500 and 1,000 (Andrey only)	Pre-release 0.3.0, 11 October 2026	xges 0.1.6
Tabu search, hill climbing	10-800; 1,600 and 3,200 (Andrey only)	Pre-release 0.3.0, 11 October 2026	bnlearn 5.2.1 on R 4.6.1

We measured a pre-release Andrey 0.3.0 build of 11 October 2026. The summary contains one row per method, mean degree, and size: rows for the sizes both packages ran and reach for the larger sizes, which only Andrey ran. Each row gives median seconds, the paired ratio, the number of paired datasets and of those with the same graph, each package’s median SHD beside the empty graph’s, and the BIC columns that bic_definition names; a reach row gives Andrey’s columns only. fits, andrey_ok, and comparator_ok count the fits and those that finished.

Score-based methods

Every fit in a comparison searches under the same BIC penalty. Tabu search runs with bnlearn’s default tabu settings in both packages. In the XGES comparison, no search limits a variable’s parents, Andrey GES included.

XGES

XGES searches the equivalence classes that GES searches, with GES’s moves and the turning move of GIES, in a different order. Each step takes the best improving deletion, else the best reversal of a directed edge, else the best addition; the base search stops when no move improves the score. The extended search then deletes each edge of that graph in turn, forbids adding it back in that direction, and reruns the base search, keeping any result with a better score.

Mean degree	d	Andrey (s)	xges (s)	Speedup
2	25	0.0718	0.281	3.95x
2	50	0.250	3.40	10.9x
2	100	0.557	24.0	43.2x
2	200	1.64	244	140x
4	25	0.495	2.91	5.25x
4	50	1.66	23.5	15.5x
4	100	3.07	129	42.0x
4	200	12.3	1,090	89.3x

Mean degree	d	Same graph	SHD, Andrey	SHD, xges	SHD, Andrey GES	Empty-graph SHD	BIC gap, Andrey	BIC gap, xges
2	25	5 of 5	13	13	22	25	-8.74	-8.74
2	50	5 of 5	33	33	47	50	-41.50	-41.50
2	100	5 of 5	78	78	82	100	-121.55	-121.55
2	200	5 of 5	190	190	204	200	-290.15	-290.15
4	25	5 of 5	38	38	55	50	55.15	55.15
4	50	5 of 5	45	45	109	100	66.11	66.11
4	100	5 of 5	63	63	179	200	-81.18	-81.18
4	200	5 of 5	151	151	266	400	-238.91	-238.91

Andrey only, at d = 500 and 1,000:

Mean degree	d	Andrey (s)	SHD, Andrey	Empty-graph SHD	BIC gap, Andrey	Fits finished
2	500	9.08	671	500	-1,153.79	5 of 5
2	1,000	51.6	1,758	1,000	-3,287.64	5 of 5
4	500	48.7	523	1,000	-918.39	5 of 5
4	1,000	289	1,368	2,000	-2,613.21	5 of 5

XGES returns the same graph as xges on every dataset, so their SHD and BIC columns are equal. Its median SHD is below Andrey GES’s and below the empty graph’s at every size both packages ran.

XGES without the extended search

With extended_search=False, XGES returns the base search’s graph and skips the extended search.

Mean degree	d	Andrey (s)	xges (s)	Speedup
2	25	0.0185	0.0240	1.34x
2	50	0.0354	0.0745	2.23x
2	100	0.0681	0.266	3.72x
2	200	0.164	0.978	6.35x
4	25	0.0442	0.0528	1.13x
4	50	0.105	0.236	2.23x
4	100	0.242	0.786	3.23x
4	200	0.449	1.88	3.77x

Mean degree	d	Same graph	SHD, Andrey	SHD, xges	SHD, Andrey GES	Empty-graph SHD	BIC gap, Andrey	BIC gap, xges
2	25	5 of 5	16	16	22	25	-8.74	-8.74
2	50	5 of 5	35	35	47	50	-34.37	-34.37
2	100	5 of 5	77	77	82	100	-120.46	-120.46
2	200	5 of 5	196	196	204	200	-258.73	-258.73
4	25	5 of 5	44	44	55	50	148.60	148.60
4	50	5 of 5	88	88	109	100	450.61	450.61
4	100	5 of 5	113	113	179	200	36.28	36.28
4	200	5 of 5	236	236	266	400	665.74	665.74

Andrey only, at d = 500 and 1,000:

Mean degree	d	Andrey (s)	SHD, Andrey	Empty-graph SHD	BIC gap, Andrey	Fits finished
2	500	0.499	663	500	-1,127.54	5 of 5
2	1,000	1.54	1,688	1,000	-3,227.51	5 of 5
4	500	1.71	576	1,000	-117.99	5 of 5
4	1,000	5.15	1,344	2,000	-2,195.07	5 of 5

Tabu search

Tabu search is hill climbing that also takes non-improving moves and never returns to a recently visited DAG. It returns the best-scoring DAG it visits; Andrey returns that DAG’s CPDAG. Until it leaves its first local optimum, it takes hill climbing’s moves, so its score is never worse than hill climbing’s.

d	Andrey (s)	bnlearn (s)	Speedup
10	0.0100	0.0255	2.54x
20	0.0163	0.0389	2.38x
50	0.0381	0.213	5.63x
100	0.0777	1.22	16.6x
200	0.187	9.68	55.3x
400	0.474	83.1	176x
800	1.74	967	561x

d	Same class	SHD, Andrey	SHD, bnlearn	Empty-graph SHD	BIC vs hill climbing, Andrey	BIC vs hill climbing, bnlearn
10	5 of 5	10	10	10	-0.15	-0.15
20	5 of 5	14	14	20	-0.06	-0.06
50	3 of 5	54	55	50	-15.44	-15.44
100	5 of 5	117	117	100	-24.66	-24.66
200	4 of 5	267	267	200	-49.64	-49.64
400	5 of 5	615	615	400	-53.90	-53.90
800	4 of 5	1,495	1,495	800	-69.01	-69.01

Andrey only, at d = 1,600 and 3,200:

d	Andrey (s)	SHD, Andrey	Empty-graph SHD	BIC vs hill climbing, Andrey	Fits finished
1,600	8.39	3,754	1,600	-53.62	5 of 5
3,200	58.3	9,312	3,200	-58.31	5 of 5

In both packages, Tabu search reaches a lower median BIC than Andrey’s hill climbing at every size. From 50 variables on, the median SHD is above the empty graph’s at every size, in both packages.

Hill climbing

Hill climbing repeatedly adds, removes, or reverses the edge that most improves the BIC, and stops when no move improves it. In 0.3.0, Andrey keeps each move’s score between passes, rescores only the moves into variables whose parents changed, and runs in one process.

d	Andrey (s)	bnlearn (s)	Speedup
10	0.00541	0.0240	5.27x
20	0.00970	0.0335	3.60x
50	0.0285	0.156	6.13x
100	0.0509	0.993	19.3x
200	0.127	8.43	70.6x
400	0.316	73.0	231x
800	0.967	893	906x

d	Same class	SHD, Andrey	SHD, bnlearn	Empty-graph SHD	BIC vs hill climbing, bnlearn
10	5 of 5	10	10	10	0.00
20	5 of 5	12	12	20	0.00
50	3 of 5	55	54	50	0.00
100	5 of 5	120	120	100	0.00
200	4 of 5	273	273	200	0.00
400	5 of 5	605	605	400	0.00
800	4 of 5	1,500	1,500	800	0.00

Andrey only, at d = 1,600 and 3,200:

d	Andrey (s)	SHD, Andrey	Empty-graph SHD	Fits finished
1,600	3.76	3,752	1,600	5 of 5
3,200	19.3	9,306	3,200	5 of 5

bnlearn’s median BIC equals Andrey’s at every size both packages ran. From 50 variables on, the median SHD is above the empty graph’s at every size, in both packages.

Known limits

• Data coverage. We measure one regime: linear-Gaussian Erdos-Renyi graphs with mean degree 2 or 4, standardized, with ten samples per variable, on up to 1,000 variables for XGES and 3,200 for Tabu search and hill climbing. These results do not establish performance across all data regimes.

• Tabu search and hill climbing against the empty graph. From 50 variables on, both methods return graphs with more errors than the empty graph’s, in both packages. The excess grows with size: at 3,200 variables, which only Andrey ran, their median SHD is nearly three times the empty graph’s. The packages return the same equivalence class on most datasets, so these results reflect the methods at this sample size, not differences between implementations.

• XGES against the empty graph. At mean degree 2 and from 500 variables on, which only Andrey ran, XGES returns graphs with more errors than the empty graph’s, with or without the extended search. Their BIC gap is below zero, so at this sample size the BIC score itself prefers these graphs to the true one. At every size both packages ran, XGES’s median SHD is below the empty graph’s.

• XGES fit times. At 1,000 variables on one core, XGES’s median fit takes under a minute at mean degree 2 and under five minutes at mean degree 4; without the extended search, it takes a few seconds. The extended search reruns the base search for each edge it tries to delete, so its time grows with the number of edges.

• Hardware. Ratios are specific to the measured hardware, core budget, and settings.

Reproduce

The benchmark harness guide documents environment setup, the campaign drivers, and the scores. To rerun the comparisons, install Andrey 0.3.0 (andrey-core), xges 0.1.6 in its own environment, and bnlearn 5.2.1 on R 4.6.1, then run the drivers with the settings below. Times will differ with the hardware and build; graphs and scores should match closely.

Comparison	Driver	d	Mean degree	Seeds x repeats	Warm-up fits	Wall cap (s)	Cores
XGES, XGES without the extended search	xges_cpu.py	25-200	2, 4	5 x 1	1	3,600	1
XGES, XGES without the extended search, Andrey only	xges_cpu.py	500 and 1,000	2, 4	5 x 1	1	3,600	1
Tabu search, hill climbing	tabu_cpu.py	10-400	2	5 x 3	1	1,800	4
Tabu search, hill climbing	tabu_cpu.py	800	2	5 x 1	1	7,200	4
Tabu search, hill climbing, Andrey only	tabu_cpu.py	1,600 and 3,200	2	5 x 1	1	3,600	4

The XGES driver runs the xges arms in their own interpreter, named by ANDREY_BENCH_XGES_PYTHON. The sizes only Andrey ran need only Andrey’s XGES solutions and the empty graph.

ANDREY_BENCH_XGES_PYTHON=... $ANDREY_BENCH_PYTHON benchmarks/xges_cpu.py --out outputs/xges-cpu \
    --ladder 25 50 100 200 --densities 2 4 --seeds 5 --cap-wall-s 3600 --cores 1
$ANDREY_BENCH_PYTHON benchmarks/xges_cpu.py --out outputs/xges-cpu-andrey \
    --ladder 500 1000 --densities 2 4 --seeds 5 --cap-wall-s 3600 --cores 1 \
    --solutions andrey.xges.numpy andrey.xges.numpy.no_extended_search baseline.empty

The Tabu search driver also runs hill climbing in both packages and the empty graph. Load the R modules and export R_LIBS_USER as benchmarks/start_r.sh --env prints, then run each size range with its repeats and cap. The sizes only Andrey ran need no R: --solutions names Andrey’s solutions and the empty graph.

$ANDREY_BENCH_PYTHON benchmarks/tabu_cpu.py --out outputs/tabu-cpu \
    --ladder 10 20 50 100 200 400 --seeds 5 --repeats 3 --cap-wall-s 1800 --cap-mem-mb 30000 --cores 4
$ANDREY_BENCH_PYTHON benchmarks/tabu_cpu.py --out outputs/tabu-cpu-800 \
    --ladder 800 --seeds 5 --repeats 1 --cap-wall-s 7200 --cap-mem-mb 30000 --cores 4
$ANDREY_BENCH_PYTHON benchmarks/tabu_cpu.py --out outputs/tabu-cpu-andrey \
    --ladder 1600 3200 --seeds 5 --repeats 1 --cap-wall-s 3600 --cap-mem-mb 30000 --cores 4 \
    --solutions andrey.hc.numpy.serial,andrey.tabu.numpy.serial,baseline.empty