Matching-Based CCA Pairing: a Negative Result

pairing_frustration.md diagnosed the CCA pairing bottleneck: in the hard regime, 97.4% of failures (38/39) had a valid alternative pairing available in the same cluster pool that greedy first-fit never considered. This page reports the implementation and benchmarking of the direct response — exact maximum-cardinality matching in place of greedy first-fit — and its outcome: no measurable improvement (+0.2 percentage points over 4200 trials). The cause is identified in the Discussion. The result is reported in the same manner as the project’s prior negative results (candidate ordering, pair prefilters, Γ-expansion, FFT docking, soft relaxation, densify_method="voronoi").

Method

pyfracval/cca/matching.py adds two alternatives to _generate_pairs()’s greedy first-fit, selected via the cca_pairing_strategy config flag ("greedy" default, "matching", "matching_leaf_weighted"):

• max_cardinality_matching: exact maximum-cardinality matching via memoized brute-force DP. Round pool sizes are small (bounded by roughly 1/n_subcl_percentage, empirically ≤16), so this is cheap and exact; a Blossom-algorithm implementation is unnecessary at this scale.

• leaf_weighted_matching: the same matching, with total edge weight (from a per-cluster-pair leaf classification, reusing candidates.py’s per-particle leaf mask aggregated into a per-cluster leaf fraction) as a tiebreaker among cardinality-optimal solutions. Cardinality is optimized first and never sacrificed for weight, since giving up a matchable pair for a higher-weight edge would directly contradict the diagnosed problem.

Both operate over the same inexpensive gamma-feasibility graph _generate_pairs()’s greedy loop already builds (gamma_real and gamma_pc < sum_rmax, with the existing 10% relaxation fallback) — deliberately not the graph pairing_frustration_probe.py builds for offline diagnosis, which tests every edge by attempting production sticking (3 retries each). That census is appropriate for a one-off diagnostic; running it inside _generate_pairs() on the hot path would be prohibitively slow and would perturb the RNG state real trials depend on. This design constraint turns out to explain the negative result — see Discussion.

Results

Single-shot (frustration-probe regime and seeds)

benchmarks/pairing_strategy_frustration_rerun.py: same hard and easy-control regimes, same 40 seeds, same single-shot (no internal retry) methodology as the original probe, varying only cca_pairing_strategy.

Regime	greedy	matching	matching_leaf_weighted
Hard (Df=2.25, kf=0.95, σ=1.9)	2.5% (1/40)	5.0% (2/40)	2.5% (1/40)
Easy control (Df=1.8, kf=1.0, σ=1.5)	100% (40/40)	100% (40/40)	100% (40/40)

A one-trial difference at n=40 is not distinguishable from noise. Plain matching does not measurably outperform greedy first-fit; leaf-weighted matching performs identically to greedy on these seeds.

Retry-inclusive boundary sweep

benchmarks/pairing_strategy_sweep.py --config configs/hard_regime_boundary_sweep.toml --strategies matching: the full 840-combination, 4200-trial grid from hard_regime_boundary_sweep.md, run with cca_pairing_strategy="matching" and compared cell-by-cell against the greedy baseline (same literal seeds 1–5 per combination in both runs).

Strategy	Total successes
greedy (baseline)	3039/4200 (72.4%)
matching	3048/4200 (72.6%)

The net difference is +9 trials (+0.2 percentage points) across the grid. Of the 840 combinations, 51 (6.1%) differ at all between the two strategies, and the differences run in both directions in roughly equal measure (largest single swing +3 at one cell, against several −2 and +2 swings elsewhere). There is no systematic improvement concentrated anywhere in the grid; the pattern is consistent with noise from each internal-retry attempt consuming a different amount of shared RNG state once the pairing decision diverges between strategies, even from the same literal seed.

matching_leaf_weighted was not re-run at full-grid scale: the single-shot comparison above shows it performing identically to greedy on the exact seeds where an effect was expected, and a second 4200-trial run for a strategy with no signal in the targeted test was not considered a justified use of the compute budget.

Raw output: benchmark_results/pairing_strategy_frustration_rerun.json, benchmark_results/hard_regime_boundary_sweep_matching/.

Discussion

The 97.4% “rescuable” figure from pairing_frustration.md was computed against a feasibility graph built from actual sticking outcomes (each edge tested via the real production sticking path, 3 retries). Matching over that graph would find rescuing pairings in nearly every case — that is what the diagnostic showed. But _generate_pairs() cannot afford to build that graph: it runs before any geometry has been attempted, using only the inexpensive gamma-feasibility test (gamma_pc < sum_rmax), which is a necessary but not sufficient condition for two clusters sticking without overlap. The cheap graph is systematically denser and more optimistic than the real one. Maximizing cardinality over the too-permissive graph does not preferentially select edges that succeed at the sticking stage; it selects a different feasible-looking pairing, which fails at approximately the same rate as greedy’s first-fit choice, because both draw from the same pool of geometrically plausible pairs without information about which the sticking search will resolve.

The same argument explains the absence of a leaf-weighting effect: the weighting can only re-rank among cardinality-optimal solutions within the same optimistic graph, and carries no additional information about sticking outcomes.

The lever the diagnosis actually identified — repartnering when a chosen pair fails to stick, using outcome information a precomputed graph does not have — is a different design: backtracking within _run_iteration rather than a smarter upfront graph. That design is implemented and evaluated in backtracking_pairing.md.

Status

cca_pairing_strategy="matching"/"matching_leaf_weighted" are implemented, tested (tests/test_cca_matching.py), and available as opt-in config values. They do not move hard-regime success rates and are not promoted beyond opt-in.