---
name: benchmarks-0.3.0
description: The Andrey 0.3.0 release card - XGES compared with xges, and Tabu search and hill climbing compared with bnlearn, on linear-Gaussian data.
meta:
  type: guide
  tags: [benchmarks, performance, accuracy, score-based]
---

# 0.3.0 release card: score-based search

% The release's cover, as on the Release cards page, beside the opening (_static/benchmarks.css).
:::::{div} release-opening

:::{card}
:class-card: release-cover release-art release-art-0-3-0
:shadow: none

Release card

Score-based search

0.3.0
:::

::::{div} release-opening-text

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](#known-limits)). You can find speedups and accuracy in the [summary](#summary), and
measurement and scoring definitions in [how to read the results](#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 |

```{raw} html
:file: 0.3.0/speedup.html
```

**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
{download}`summary <../../../benchmarks/published/0.3.0/summary.json>` 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][harness] 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.

```shell
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.

```shell
$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
```

[harness]: https://github.com/Abel-ai-lab/andrey/blob/main/benchmarks/README.md