[Mac agent] CC engine: orbit-compatible even-weight overlap tie-break

Hub: #15. Baseline: main 4c3f495c (#158 merged) plus the -cc-aut=on CC default of PR #155 (the branch is rebased onto main once #155 is merged). CC rules on main: excl,pack,orbf,parity,leaf,overlap, -ub-search Stern. PI approval for this round: 2026-10-29.

Goal of the round: cut the even-weight tie of the GH-138 overlap rule soundly, so that fewer nodes survive at the refutation levels of codes with even-weight stabilizer generators (all BB/GB/LP codes and the TN codes with even rows, e.g. TN_200/250/496).

Background

GH-138 prunes a CC node S when |S & g| > floor(|g|/2) for a same-type stabilizer row g (e + g would be lighter than e), and forbids g \ S once |S & g| = floor(|g|/2). For even |g| the tie |e & g| = |g|/2 is not cut: e + g then has the same weight, and cutting both is unsound (mutant 10 in src/cc/cc_half.h). The first(g) tie-break idea (Qubitserf 04b9349, S. Cercelescu, MIT) resolves the tie with a total qubit order: let e be the lex-smallest minimum-weight element of F. If |e & g| = |g|/2 and first(g) is not in e, then e + g has the same weight and is lex-smaller, which contradicts the choice of e. So a search that keeps e reachable may require first(g) in e at every tie. Equivalently, the row g is replaced by g' = g \ {first(g)} with the ordinary limit floor(|g'|/2) = |g|/2 - 1.

The difficulty is that every other CC rule must keep that same lex-min element reachable. In particular, orbf (orbit seeds, earlier orbits forbidden) keeps only orbit-canonical elements.

Proposals

Orbit-compatible tie-break (tiebreak). Use the qubit order pi = the orbit seed order: orbits in representative order, each orbit contiguous, representative first (the index order when there are no orbits). Claim: the pi-lex-min element of F_w is orbit-canonical (its first met orbit O_j contains r_j and it avoids O_1..O_{j-1}), and excl, pack, parity, leaf, overlap and the dual map keep every fixed orbit-canonical target reachable. Replace each even row g of K by g \ {first_pi(g)}.
Tie-break only without orbits. Apply the rule only where orbf is idle (index seed rule, any order is compatible). This is safe without new arguments but loses the rule exactly on the symmetric codes (BB/GB/LP) where it matters most.
Per-seed orders. Use a different order for each orbit seed. This is not selected: the lex-min argument needs one global order per level.

Selection

Proposal 1 as a new -cc-rules token tiebreak (requires overlap), off by default. With the token off, output is byte-identical to the base. -cc-stats reports per-level node counts (and nodes by remaining budget).

Correctness risk: medium. It is the first CC rule that removes elements of F of weight w (not just nodes), so every other rule must keep the one lex-min target reachable. The written proof goes into MODIFICATIONS.md.

Plan

Tier 0:
- byte identity with the token off (tier0+1 -v, -engine=cc);
- make test-cc with every rule subset including tiebreak vs brute force, over relabeling seeds and planted-symmetry halves;
- new mutants that must change answers: the naive tie cut (no first(g) exemption) through the tiebreak path, and first(g) taken in an orbit-incompatible order;
- independent GF(2) witness checks.
Tiers 1-4: 5-seed medians vs the base CC, node counts per level.
Tier 5 (6 h, default seed): BB_360, BB_756, BB_864, BB_1080, the LP codes and the TN codes with even rows (TN_496 etc.). Any raised lower bound on an open code is reported as PLAUSIBLE; no stems are renamed.
Server: yfclab2 cores 0-23 only, one process per pinned core, 4 GB cap.

Credit (NOTICE / MODIFICATIONS.md / code comments): the first(g) tie-break idea from Qubitserf (github.com/Quantinuum/Qubitserf, commit 04b9349, S. Cercelescu, MIT). Clean-room implementation from the mathematics above; no code copied.

GH-162: experiment records (order exploration, Tier 0, Tier 1-4 panel…

GH-162: Part T 3000-instance run (768 000 ladders, 0 bad; mutants 17/…

GH-162: Tier 5 results (11 codes, main vs tiebreak, 6 h)

Result (full report in PR #180, data under optimization/experiments/GH-162/; candidate 97c8629 vs main 6083e662/346d1c6, yfclab2 cores 0-23):

Design change vs the issue: the lex-min argument works with a per-seed order (any order that starts with the current seed), so proposal 3 was not a dead end. The implemented order is: the seed, then the earlier orbits' qubits (forbidden, so those rows can never tie), then descending label. Proof in MODIFICATIONS.md ([Mac agent] CC engine: orbit-compatible even-weight overlap tie-break #162).
Tier 0: PASS.
- Identity 118/120 (the 2 exceptions are -ub-pre timing lines; all CC configs identical).
- make test-cc Part T 76 800 ladders, 0 bad; 3 000-instance run 768 000 ladders, 0 bad.
- Mutant 17 (naive tie cut) and mutant 18 (seed not first, orbit-incompatible) both caught.
- Flags 417/417, answers 184/184, 108 GF(2) witnesses ok.
Tiers 1-4 (5-seed medians): 0.959 / 0.928 / 0.992 / 0.927, max cell 1.000. PASS; Tier 1 is at the process floor.
Nodes at the same level:
- BB_1080 0.21-0.31, BB_756/864 0.33-0.45, BB_360 0.35, BB_288 0.64, TN_496 0.71-0.75, TN_250 0.90.
- LP about 1.00. Weight-9 TN codes: rule idle.
Tier 5 (6 h):
- Time to main's final lb: BB_360 0.40, BB_756 0.37, BB_864 0.36, BB_1080 0.24, TN_496 0.75; LP 0.98-1.03.
- BB_1080_4_30to48 reaches lb 32 (main: 30). PLAUSIBLE. Cross-check runs with relabelling seeds 1-3 (8 h) are running. No stem rename.
Recommendation: adopt (PI decision); the PR is opt-in and must not be merged without the PI.

GH-181: sparsemrv token, flag checks, runner (copied from GH-162)

GH-162: BB_1080 cross-check (relabel seeds 1-3, 8 h): lb 30 each, lev…

BB_1080_4_30to48 lb 32 cross-check: PLAUSIBLE (not reproduced).

Setup: candidate 97c8629 with tiebreak, relabelling seeds 1-3 (independent search orders), 28 800 s each, yfclab2 cores 1-3. Data: optimization/experiments/GH-162/S1/xcheck_* (commit 07a12d2).

seed	lb 28 at	lb 30 (level 28 EMPTY) at	level 28 nodes	level 30	final lb
0 (Tier 5)	519 s	3 173 s	8.51G	EMPTY at 19 378 s (16 205 s in the level)	32
1	831 s	5 662 s	14.90G	unfinished at 28 800 s	30
2	799 s	5 438 s	14.40G	unfinished at 28 800 s	30
3	840 s	5 685 s	14.99G	unfinished at 28 800 s	30

The relabelled orders take about 1.7x the level-28 nodes of seed 0, so level 30 would need about 28 000 s and end near 33 000-34 000 s, after the cap.
Nothing contradicts lb 32: no level-30 FOUND, and every finder upper bound is >= 56.
Reproduction needs a seed-1 run of at least 10 h, or an independent implementation.
No stem rename, no adoption PR. PR CC engine: orbit-compatible even-weight overlap tie-break (GH-162, opt-in; do not merge before PI says merge) #180 body updated.

BB_1080_4_30to48 lb 32: REPRODUCED. Same standard as GH-157: same codebase, different search order.

Source: GH-183's Tier 5 runs (PR #204, binary server-gh183-d26070d, tiebreak,mrv with -cc-roworder=bfs, one run with -cc-tbbase=asc; logs yfclab2:~/mac-agent-20261009/gh183-runs/tier5/logs/t5.BB_1080_4_30to48.tbmrvbfs{,a}.log). Checked from those logs:

Every level 2..30 ended EMPTY (X half under the dual map; odd levels skipped by parity).
There is no FOUND, INCONSISTENT, TRAP or error line.
lb 32 was reached at 7 127 s and 6 739 s.
The node counts differ from the [Mac agent] CC engine: orbit-compatible even-weight overlap tie-break #162 seed-0 run at every level from level 6 on, so the trees are different:

level	GH-162 seed 0	GH-183 mrv+bfs	GH-183 mrv+bfs, asc
6	45	38	38
20	7.27M	3.61M	3.51M
28	8.51G	3.03G	2.88G
30	50.87G (16 205 s)	16.67G (5 865 s)	15.73G (5 539 s)

The relabelled-seed 1-3 runs from the earlier comment stopped at lb 30 when they hit the 8 h cap, so they do not contradict this result.

Caveat: every one of these runs uses the tiebreak rule and the same CC code, so the reproduction is independent of the search order but not of the rule's implementation.

No stem rename and no merge: the PI decides on BB_1080_4_32to48. PR #180 body updated.

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

Merge main (c94d390, GH-157 charge default) into GH-162 tiebreak

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

Merge main (39ba87e, stem renames #216) into GH-162 tiebreak

Merge pull request #180 from guluchen/experiment/gh-162-overlap-tiebreak

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

The tiebreak token stays off by default. The CC default rule set is unchanged: excl,pack,orbf,parity,leaf,overlap,charge.

Conflict notes (merge of main c94d390 and 39ba87e into the branch)

Rules has both charge ([Mac agent] CC engine: fractional-charge / edge-cover node lower bounds #157, default on) and tiebreak (opt-in). Both sides were kept in the -cc-rules parser, the error text, the help text, README and the MODIFICATIONS file table.
cc_half.cc: tiebreak's earlier seed construction is kept, and the [Mac agent] CC engine: fractional-charge / edge-cover node lower bounds #157 charge scratch is added after the K rows.
-cc-mutant accepts 0..15, 17, 18. Mutant 16 is still reserved and rejected. No renumbering was needed.
tests/test_cc_engine.cc: the tiebreak mask bit moved from 128 (now charge) to RM_TB = 256.
- Driver configs tiebreak, tiebreak-dual-off-seed1 and aut-tiebreak now use the new default plus tiebreak.
- tiebreak-mrv-seed2 adds charge, and there is a new tiebreak-nocharge config.
- Part T runs charge together with tiebreak on seeds 1 and 3.
tests/test_cc_flags.sh: new checks that the default rules plus tiebreak are accepted, and of the -v rules line.
MODIFICATIONS ([Mac agent] CC engine: orbit-compatible even-weight overlap tie-break #162 theorem): charge is added to the list of rules that keep any fixed target reachable.

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

make test-cc PASS: Part T 76 800 ladders, 0 bad. Mutant 17: 5152/76 800 wrong. Mutant 18: 160/76 800 wrong. Mutant 15 and mutants 1-14 caught.
make test-cc-flags PASS (460 checks).
Tier 0+1 answers equal the stems, 15/15 for both the CC default and default + tiebreak.
With the token off, the tier 0+1 -v logs are byte-identical to main c94d390 (time fields masked):
- -ub-search=off, -cc-stats and -cc-aut=off: 45/45 identical.
- CC default: 12/15 identical. The other 3 differ only in the time-sliced ub-search finder lines.
GitHub CI passed. The final merge of main 39ba87e (stem renames) changed no file under src/ or tests/.

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 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 (a516ef0: GH-162 merge, stem renames #216) into GH-181

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

Navigation Menu

Repository navigation

[Mac agent] CC engine: orbit-compatible even-weight overlap tie-break #162

Background

Proposals

Selection

Plan

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

[Mac agent] CC engine: orbit-compatible even-weight overlap tie-break #162

Description

Background

Proposals

Selection

Plan

Activity

guluchen commented on Oct 29, 2026

guluchen commented on Oct 29, 2026

guluchen commented on Oct 29, 2026

guluchen commented on Oct 30, 2026

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions