Comparison Benchmarks — vs. Python Heuristics
How does max-div compare to the subset-selection tools a Python user would otherwise
reach for? This page benchmarks it against the surveyed single-shot heuristics (see the
Comparison page for the tool landscape) on the built-in
benchmark problems.
Protocol
- max-div runs a wall-clock budget ladder (2× steps from 1 ms; the last rung is the
first ≥ 10 s), one independent solve per budget × seed (3 seeds),
DEFAULTpreset (an alias ofSMART— figures label itmax-div[DEFAULT]). Figures plot measured solve time, never the nominal budget. One ladder per diversity metric — max-div optimizes the metric it is scored under. - Competitors are single-shot: one run per seed, plotted as a dot at (measured time, quality).
- Every tool's selection is scored under max-div's own diversity metrics, computed identically for all tools.
- Labels matter:
apricot[facility-location]optimizes coverage andkmedoids[FasterPAM]representativeness — they are included as different-objective references, not as dispersion competitors.qc-selector(GPL) is included when installed. - Hardware: 16" MacBook Pro with M3-class CPU, single sequential run.
- Reproduce with
uv run --group benchmarks python -m benchmarks.tier2.full(records), then... -m benchmarks.tier2.report(figures/tables).
Key findings
There is a crossover, and it is driven by k (the selection size). max-div wins clearly on the separation objectives up to n ≈ 1000, wins narrowly at n = 5000 given ~10 s, and loses at n = 20000 (k = 2000) — there, farthest-point-sampling pickers reach better separation values in a few seconds than the local search reaches at any tried budget. At k = 2000, a 1 s budget fits only a few hundred iterations: not even one improvement pass over the selected set.
On MEAN_PAIRWISE_DISTANCE (classical max-sum), the greedy construction is already at
par. max-div matches greedy[max-sum] at small-to-mid sizes and trails slightly at the
largest; it does not beat it. If pure max-sum at scale is the goal, the greedy baseline is
the pragmatic choice.
Where max-div is differentiated: the separation-family objectives below n ≈ 5000, the anytime property (near-plateau quality within ~1 s at most sizes), and constrained selection (below) — where the heuristic field thins out to a single competitor that stops at n ≈ 2000.
Unconstrained results (U1, uniform density)
Anytime curves on U1 for the max-min and geomean objectives; the margin tables further down cover all problems and metrics.
MIN_SEPARATION
GEOMEAN_SEPARATION
Margin tables (all problems)
Each cell: max-div's margin vs. the best competitor under that metric, at ~1 s / ~16 s of budget. Positive = max-div ahead.
MIN_SEPARATION
max-div's margin vs. the best single-shot competitor under MIN_SEPARATION (positive = max-div ahead), at ~1 s / ~16 s of budget:
| n | U1 | U2 | U3 | U4 |
|---|---|---|---|---|
| 200 | +7.1% / +7.9% | +11.3% / +13.6% | +8.4% / +8.7% | +9.4% / +9.4% |
| 1000 | +3.0% / +3.5% | +1.4% / +1.4% | +2.8% / +2.8% | +2.0% / +2.2% |
| 5000 | -2.6% / +0.8% | -5.5% / +0.8% | -7.1% / +1.0% | -12.9% / +0.5% |
| 20000 | -9.4% / -3.7% | -13.7% / -6.6% | -17.5% / -8.6% | -95.1% / -44.6% |
MEAN_SEPARATION
max-div's margin vs. the best single-shot competitor under MEAN_SEPARATION (positive = max-div ahead), at ~1 s / ~16 s of budget:
| n | U1 | U2 | U3 | U4 |
|---|---|---|---|---|
| 200 | +7.5% / +7.5% | +7.2% / +9.3% | +7.3% / +7.3% | +8.0% / +8.1% |
| 1000 | +2.0% / +2.1% | +2.0% / +2.1% | +1.8% / +2.0% | +2.5% / +4.1% |
| 5000 | -1.2% / +0.7% | -2.1% / +0.8% | -2.7% / +0.8% | -5.4% / +0.2% |
| 20000 | -6.0% / -1.9% | -9.0% / -3.3% | -10.9% / -4.3% | -38.2% / -8.9% |
GEOMEAN_SEPARATION
max-div's margin vs. the best single-shot competitor under GEOMEAN_SEPARATION (positive = max-div ahead), at ~1 s / ~16 s of budget:
| n | U1 | U2 | U3 | U4 |
|---|---|---|---|---|
| 200 | +7.7% / +8.8% | +8.1% / +8.2% | +5.7% / +7.0% | +6.0% / +7.1% |
| 1000 | +2.0% / +2.2% | +1.8% / +1.8% | +1.9% / +2.2% | +2.0% / +2.5% |
| 5000 | -1.0% / +0.7% | -2.4% / +0.8% | -2.4% / +0.7% | -3.6% / +0.4% |
| 20000 | -6.1% / -1.8% | -9.0% / -3.5% | -11.1% / -4.3% | -47.8% / -9.4% |
MEAN_PAIRWISE_DISTANCE
max-div's margin vs. the best single-shot competitor under MEAN_PAIRWISE_DISTANCE (positive = max-div ahead), at ~1 s / ~16 s of budget:
| n | U1 | U2 | U3 | U4 |
|---|---|---|---|---|
| 200 | +0.0% / +0.0% | +0.0% / +0.0% | +0.0% / +0.0% | -0.0% / -0.0% |
| 1000 | +0.0% / +0.0% | +0.0% / +0.0% | +0.0% / +0.0% | +0.0% / +0.0% |
| 5000 | -0.1% / +0.0% | -0.1% / +0.0% | -0.1% / +0.0% | -0.0% / +0.0% |
| 20000 | -4.3% / -0.1% | -6.5% / -0.1% | -7.5% / -0.1% | -25.0% / -0.0% |
Constrained results
With fairness constraints, the only surveyed heuristic competitor is code-FDM (FairFlow), and it bounds the comparison twice over: it scales roughly cubically (~150 s at n = 2000, impractical beyond), and its disjoint-color fairness model cannot even express overlapping constraint groups — so the harder constrained problems (C3/C4) have no competitor at all. The comparison therefore covers C1/C2 up to n = 2000; beyond either limit, no surveyed Python heuristic produces constraint-satisfying selections (exact solvers can, at small n — see the exact-reference benchmarks).
max-div's margin vs. the best single-shot competitor under MIN_SEPARATION (positive = max-div ahead), at ~1 s / ~16 s of budget:
| n | C1 | C2 |
|---|---|---|
| 200 | +221.7% / +232.4% | +106.8% / +113.8% |
| 1000 | +301.5% / +304.7% | +279.7% / +289.7% |
| 2000 | +1284.6% / +1310.8% | +592.8% / +635.6% |