[Mac agent] CC engine: MRV branching and BFS row order on top of tiebreak

Hub: #15. Stacked on #162 (rule tiebreak, PR #180, not merged).

Hypothesis

With overlap,tiebreak, the CC engine still branches on the lowest-index odd row and scans odd rows for the packing bound in file row order. Two branching-row changes should cut the search tree on the BB codes, and the gain should grow with code size:

MRV (the existing mrv token): branch on the odd row with the fewest free candidates. A smaller branching factor at every depth compounds over the level.
Seed-anchored reversed-BFS row order: renumber the rows of H by a BFS over the Tanner graph that starts from the rows of the first seed qubit, then reverse the order (rows far from the seed first, rows next to the seed last). The new index drives both the greedy packing scan (which disjoint odd rows are found) and the MRV tie-break (lowest index among rows with equal candidate count).

Change

Part A, no new code: measure -cc-rules=excl,pack,orbf,parity,leaf,overlap,tiebreak,mrv against the same set without mrv.
Part B: new flag -cc-roworder=index|bfs (default index, byte-identical to the current output). bfs is a pure relabelling of the rows inside each half search, the same kind of change as the row relabelling of -cc-seed. Also a test-only variant of the tiebreak base order (-cc-tbbase=desc|asc, default desc).

Soundness

The choice of the branching odd row is free in the exactness argument (cc_half.h (2): every odd row of S contains a qubit of e \ S), and every rule's proof, including tiebreak's lex-min argument, keeps an arbitrary fixed target reachable under any choice.
The packing bound holds for any scan order (any family of pairwise-disjoint candidate sets of odd rows is a lower bound).
A row permutation changes no syndrome, candidate set or stabilizer row; the tiebreak base order may be any total order once the seed and the exhausted blocks come first.

Plan

Tier 0 (brute-force oracle over rule subsets x seeds x roworder x mrv, byte identity with defaults, GF(2) witnesses, a mutant BFS order that drops a row), Tiers 1-4 seed-median panel vs main CC and vs the GH-162 tiebreak configuration, Tier 5 (6 h) on the large BB codes, the LP codes and TN codes. yfclab2 cores 28-43, one pinned process per core, 4 GB cap.

Credit: the reversed-BFS row ordering idea is from Qubitserf 04b9349 (S. Cercelescu, MIT); clean-room implementation.

GH-183: runners, Tier 0 records (oracle, identity, witnesses, flags) …

GH-183: Tier 5 (6 h) results and LP / TN diagnostics

Result: PR #204 (do not merge before the PI says merge).

Tier 0: PASS. Part R oracle: 384k ladders at default size and 2.56M at 2,000 instances, 0 bad. Mutants 19 and 20 are caught. Identity with [Mac agent] CC engine: orbit-compatible even-weight overlap tie-break #162 holds, the GF(2) witnesses check out, and the flag tests pass.
Tiers 2-4: geomean vs main 0.611 / 0.593 / 0.400; vs tb 0.655 / 0.590 / 0.436; no cell above 1.0.
Tier 1: a process-floor tie. Every arm, including tb, is 1.7 % above main in a repeated measurement.
Tier 5, BB: BB_756 and BB_864 reach lb 32. BB_1080 reaches lb 32 in 2.7x less time than tb but not 34. At equal levels: BB_360 to BB_1080 take 0.29-0.40x tb's time; TN_496 0.38x, reaching lb 24.
Tier 5, LP and row-weight-9 TN: LP codes are 1.2-3x slower. TN_252 takes 1.17x longer and TN_288 ends one lb lower (21 vs 22).
The new lower bounds are PLAUSIBLE only; stems are unchanged.
Recommendation: not an unconditional default. Next step is a per-half probe (-cc-roworder=auto).

GH-183: cross-check of the PLAUSIBLE lower bounds with relabeled seed…

Cross-check of the PLAUSIBLE lower bounds: REPRODUCED (9/9 runs)

Setup:

Same frozen binary (d26070d) and configuration that found the bounds: -cc-rules=excl,pack,orbf,parity,leaf,overlap,tiebreak,mrv -cc-roworder=bfs.
Relabeled seeds -seed=1..3, which give a different qubit and row order and different orbit representatives.
28800 s per run; yfclab2 cores 24-32, one pinned process per core, 4 GB cap.

Code	Bound	Seed 1	Seed 2	Seed 3	Verdict
BB_756_16_30to34	>= 32	12334 s	12360 s	12924 s	REPRODUCED
BB_864_4_30to40	>= 32	10797 s	11645 s	11084 s	REPRODUCED
TN_496_2_23to30	>= 24	12393 s	9640 s	11147 s	REPRODUCED

Every level each run searched ended EMPTY, with no trap, withdrawn bound or science problem.
On the BB halves every column weight is odd, so the parity rule skips odd levels and level 30 EMPTY certifies 32.
This is an independent search order of the same implementation. Stems are not renamed; that needs the PI.
Records: optimization/experiments/GH-183/S3_xcheck/ (commit a8e4532).

Rename eight tier5 stems with GH-157/GH-162/GH-183/GH-181 CC lower bo…

Merge pull request #216 from guluchen/data/cc-lb-stems-20261031

Merge GH-162 branch (with main c94d390, GH-157 charge default) into G…

Merge main (a516ef0: GH-162 merge, stem renames #216) into GH-183

Merge pull request #204 from guluchen/experiment/gh-183-cc-roworder

Merged into main at 7d91569 as opt-in (PI-approved order 2026-10-31).

-cc-roworder still defaults to index and mrv stays off. The CC default rule set is unchanged: excl,pack,orbf,parity,leaf,overlap,charge.

Retarget and conflicts

PR CC engine: MRV branching and seed-anchored reversed-BFS row order (GH-183, opt-in; do not merge before PI says merge) #204 was retargeted to main after CC engine: orbit-compatible even-weight overlap tie-break (GH-162, opt-in; do not merge before PI says merge) #180 merged.
The [Mac agent] CC engine: orbit-compatible even-weight overlap tie-break #162 branch (with main and [Mac agent] CC engine: fractional-charge / edge-cover node lower bounds #157) was merged in, then main a516ef0.
Conflicts were resolved by keeping both sides:
- HalfSearch takes the row order and tbbase arguments. The driver also passes the [Mac agent] CC engine: fractional-charge / edge-cover node lower bounds #157 charge settings.
- DriverOptions keeps both sets of fields.
- -cc-mutant accepts 0..15 and 17..20. Mutants 19 and 20 kept their numbers.
tests/test_cc_engine.cc:
- ladder_ok takes the [Mac agent] CC engine: fractional-charge / edge-cover node lower bounds #157 arguments first, then the [Mac agent] CC engine: MRV branching and BFS row order on top of tiebreak #183 ones. The Part R calls were updated to match.
- The bfs/mrv driver configurations that stand for the candidate now use the new default (with charge) plus tiebreak.
- New config charge-mrv-bfs-minr1.
- Part R runs charge on seeds 1 and 3.
tests/test_cc_flags.sh checks that the default rules plus tiebreak,mrv with -cc-roworder=bfs are accepted.

Checks (yfclab2, cores 2-23, 4 GB cap)

make test-cc: PASS.
- Part R: 384 000 ladders, 0 bad.
- Mutant 19: 9088/28 800 wrong. Mutant 20: 4656/28 800 wrong.
- Part T and mutants 15, 17 and 18 are still caught.
make test-cc-flags: PASS (485 checks).
Tier 0+1 answers equal the stems: 15/15 with the CC default and 15/15 with -cc-rules=excl,pack,orbf,parity,leaf,overlap,charge,tiebreak,mrv -cc-roworder=bfs.
With the flags off, the tier 0+1 -v logs are byte-identical to main a516ef0:
- -ub-search=off, -cc-stats and -cc-aut=off: 45/45.
- CC default: 13/15. The other 2 differ only in the time-sliced ub-search finder lines.
GitHub CI passed.

Merge GH-183 branch (with GH-162 and main c94d390, GH-157 charge defa…

Merge main (7d91569: GH-162 and GH-183 merges, stem renames #216) into …

Merge GH-206 stack (GH-162, GH-183, GH-206 and main c94d390 with GH-157…

Merge main (30ce62a: GH-162, GH-183, GH-206 merges) into GH-181

Navigation Menu

Repository navigation

[Mac agent] CC engine: MRV branching and BFS row order on top of tiebreak #183

Hypothesis

Change

Soundness

Plan

Cross-check of the PLAUSIBLE lower bounds: REPRODUCED (9/9 runs)

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

[Mac agent] CC engine: MRV branching and BFS row order on top of tiebreak #183

Description

Hypothesis

Change

Soundness

Plan

Activity

guluchen commented on Oct 29, 2026

guluchen commented on Oct 30, 2026

Cross-check of the PLAUSIBLE lower bounds: REPRODUCED (9/9 runs)

guluchen commented on Oct 30, 2026

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions