[Mac agent] CC engine: erasure bound as a default rule (on top of GH-217 candidate A)

Hub: #15. Follows #195 (PR #219, opt-in erasure, merged in 86d1d59) and builds on #217 / PR #220 (candidate A, not merged yet).

Question

Should the GH-195 erasure bound join the CC default rule set?

Comparison

A (baseline): PR GH-217: CC default rules + tiebreak, sparse rows and -cc-roworder=auto (Tier 1 floor: PI decision) #220 head (42d7d1d; main fecee8c merged in). Rules excl,pack,orbf,parity,leaf,overlap,charge,tiebreak,sparse,sparseov,sparsemrv, -cc-roworder=auto.
A+E (candidate): A + erasure, start threshold -cc-erasure-start=N (default 16384; a brief tuning pass may pick another N).

The branch is stacked on #220. It will not be merged before #220.

Plan

Brief tuning on a few Tier 2/3 and Tier 5 codes: the default start, plus one or two other start values. Keep it cheap to avoid overfitting.
Tier 0: make test-cc, make test-cc-flags, answer checks with GF(2) witness verification. Update the tests for the new default.
Tiers 1-3 on the current layout (tier4 is empty). 5-seed medians, A and A+E run concurrently on pinned cores. Pass = geomean < 1 and no cell > 1.25. Sub-50 ms cells may still show the 10 ms child-polling floor (Parent wait loop: remove the 10 ms usleep polling floor on fast runs #224); such cells are flagged, not chased.
Tier 5: 6 h, default seed, A and A+E concurrent. Every code A solves must stay <= 1.2x. Report lb gains; new lbs stay PLAUSIBLE until reproduced.

Server: yfclab2 logical CPUs 104-127 only, one pinned process per core, 4 GB cap; each core and its SMT sibling are checked idle before each launch.

Credit: erasure bound idea from Qubitserf 04b9349 (S. Cercelescu, MIT); clean-room implementation (NOTICE, MODIFICATIONS.md).

GH-225: runners, tuning, Tier 0 and Tier 1-3 panel records

GH-225: Mac same-session interleaved LP Tier 5 re-runs (A vs A+erasure)

Interim results (branch experiment/gh-225-cc-erasure-default, candidate 5a201fd = PR #220 head 42d7d1d + erasure in the default rules, start 16384). Records: optimization/experiments/GH-225/.

Tuning (A binary, -cc-erasure-start 4096 / 16384 / 65536; 10 Tier 1-3 codes x 3 seeds, 7 Tier 5-style codes x 1 seed): no start value is better overall. 4096 helps BB_144_14_14 a little and costs more on AMC_522_6_20; 65536 is the reverse. The default 16384 was kept. Records: tune/analysis.md.

Tier 0: make test-cc-flags 582 checks, 0 failed. Answers: 550 runs (50 tier0-3 codes x 11 variants, including start 0 with index / bfs+mrv orders), all equal to their stems, 17.7M erasure prunes. GF(2) witness check: 289 witnesses OK, 0 bad. Identity check, candidate with the explicit GH-217 rule list vs A on tier0+1: every configuration IDENTICAL, except 5 timing-only differences (MaxSAT ub-pre and CC ub-search finder lines). make test-cc is still running.

Tiers 1-3 (5 seeds, A and E concurrent on pinned CPUs 112-127, ratio = median E / median A): PASS.

Tier	geomean	worst cell
1	0.930	1.114 (HGP_265, 35 ms cell, 0 erasure tests: polling floor)
2	0.679	1.157 (AMC_522_6_20; nodes 0.245x, but the tests cost more than they save)
3	0.869	1.062 (LP_1020)

Tier 5: the 1.2x rule FAILS on two LP codes. The 6 h runs are still going for the open codes. The codes A solves have finished:

Code	A	E	E/A (server)	Mac interleaved (6 or 4 reps, ABBA)
LP_1768_224_22	15.1 s	19.5 s	1.29	1.235 (search time 1.40)
LP_2610_744_16	2.78 s	3.25 s	1.17	1.264 (search 1.33)
LP_1428_184_24	115.9 s	124.7 s	1.08	1.09
LP_1054_140_20	1.70 s	1.83 s	1.07	1.075
LP_1122_148_20	4.77 s	4.75 s	1.00	1.053
COLOR_331_1_21	4.32 s	2.66 s	0.62
HGP_1105_1_24	3.38 s	3.27 s	0.97
BB_360_12_24	27.8 s	22.1 s	0.80
TN_180_2_17	126.5 s	57.0 s	0.45
TN_216_4_18	333.9 s	173.4 s	0.52
TN_252_2_21	running

On the LP codes, erasure cuts 15-20x of the nodes, but each test costs about as much as the subtree it removes. For example, LP_1768 level 20: 42.9M -> 2.6M nodes, 10.1 s -> 13.1 s. The start threshold cannot fix this, because the dominant level is the last one. With the current gate, erasure therefore cannot join the default. The remaining 6 h runs are kept for the lb record.

GH-225: make test-cc output (PASS)

Merge main (1239e9a: #220 GH-217 default flip, #226 polling fix) into G…

Update after #220 / #226 merged (main 1239e9a):

The branch now has main merged in (ac46040); its diff against main is only the erasure default change. On the merged binary, make test-cc-flags gives 582 checks, 0 failed (Mac). make test-cc on the candidate (5a201fd, same solver source minus the polling fix) is PASS (Part U 259 200 ladders, 0 bad; mutants 25/26 caught).
I re-ran the failing Tier 5 cells on the Mac against main 1239e9a: same session, 6 reps per arm in ABBA order, default seed.
- LP_1768_224_22: 5.34 s -> 6.60 s (1.235x; search time 1.41x).
- LP_2610_744_16: 0.90 s -> 1.14 s (1.268x; search 1.32x).
These are search-time costs; the 10 ms polling floor plays no part. The Tier 5 1.2x rule fails, so erasure is not merged as a default. No PR has been opened for the flip. The 6 h Tier 5 runs for the open codes continue for the lb record.

GH-225: LP re-check against main 1239e9a (Mac, interleaved)

GH-225: Tier 5 records (A vs A+erasure, 6 h, 30 codes)

Verdict: NO-GO. Erasure does not join the CC default with its current gate.

All other gates pass. The Tier 5 1.2x rule fails on LP_1768_224_22 (1.29x on the server; 1.235x interleaved on the Mac against main 1239e9a) and on LP_2610_744_16 (1.17x on the server; 1.268x interleaved on the Mac). No PR was opened. Branch experiment/gh-225-cc-erasure-default (ac46040 + records e36b242) is main 1239e9a plus the one-line default flip, tests and docs, in case a gated version is wanted later. Records: optimization/experiments/GH-225/.

Tier 5 (6 h, default seed, A = PR #220 head = main minus the polling fix, E = A + erasure; yfclab2 CPUs 104-127)

Codes A solves (1.2x rule):

Code	A	E	E/A
BB_360_12_24	27.8 s	22.1 s	0.80
COLOR_331_1_21	4.3 s	2.7 s	0.62
HGP_1105_1_24	3.4 s	3.3 s	0.97
LP_1054_140_20	1.7 s	1.8 s	1.07
LP_1122_148_20	4.8 s	4.7 s	1.00
LP_1428_184_24	115.9 s	124.7 s	1.08 (Mac interleaved 1.09)
LP_1768_224_22	15.1 s	19.5 s	1.29 (Mac interleaved 1.235)
LP_2610_744_16	2.8 s	3.3 s	1.17 (Mac interleaved 1.268)
TN_180_2_17	126.5 s	57.0 s	0.45
TN_216_4_18	333.9 s	173.4 s	0.52
TN_252_2_21	6942 s	3690 s	0.53

Why the LP codes fail: erasure removes 15-20x of the nodes, but each test costs about as much as the subtree it cuts. For example, LP_1768 level 20 goes from 42.9M to 2.6M nodes, but from 10.1 s to 13.1 s. The start threshold cannot help, because the dominant level is the last one.

The same holds on COLOR_2791_1_26to61 (unsolved, information only): level 26 has 20x fewer nodes but takes 2538 s -> 9146 s. E reaches lb 27 at 17 221 s; A reaches it at 4 825 s and goes on to lb 28.

Lower bounds above the stem names: PLAUSIBLE. Each is a single run on the same engine, not reproduced yet.

Code	stem lb	A	E
COLOR_1027_1_28to37	28	30 (14 257 s)	31 (16 091 s)
COLOR_2791_1_26to61	26	28 (10 312 s)	27
TN_324_4_22to25	22	22	23 (20 985 s)
TN_496_2_27to30	27	27	28 (17 997 s)
TN_540_4_23to34	23	23	24 (19 169 s)
TN_648_14_21to28	21	21	22 (20 292 s)
TN_684_2_22to29	22	23 (16 368 s)	23 (20 207 s)

Where both arms reach the same final lb on open TN codes, E reaches A's final lb 0.59-0.92x as fast (TN_684 is the exception at 1.23x). On open BB codes, E reaches lb 32 1.02-1.08x more slowly.

Caveat: in the second wave, the A and E runs of TN_360, TN_576 and TN_684 started 3 252-4 637 s apart, because the idle check skipped busy cores. These are information-only cells.

Earlier gates (all PASS)

Tier 0:
- make test-cc PASS;
- make test-cc-flags 582/582 (candidate, and the branch merged with main 1239e9a);
- 550 answer runs, all equal to their stems;
- 289 GF(2) witnesses OK, 0 bad;
- identity with the explicit [Mac agent] CC engine default flip: tiebreak + sparse rows + -cc-roworder=auto #217 rule list: IDENTICAL apart from 5 timing-only finder lines.
Tiers 1-3 (5 seeds): geomean 0.930 / 0.679 / 0.869. Worst cells: 1.114 (HGP_265, a sub-50 ms cell with 0 erasure tests), 1.157 (AMC_522_6_20) and 1.062.

Suggested follow-up

A cost-aware erasure gate, e.g. a per-half probe in the style of -cc-roworder=auto: time the first level >= 0.1 s with and without erasure and keep the faster. This would keep the TN/BB/COLOR_331 gains (0.45-0.80x) and fall back on LP_1768, LP_2610 and COLOR_2791. It is a code change, so it needs a new round with the full gates.

GH-227: cost-aware erasure gate; erasure joins the CC default rule set

Merge pull request #230 from guluchen/data/gh225-lb-stems

Lower-bound reproduction for GH-225 / GH-227 (2026-11-06)

Seven tier5 stems were renamed in DistQLDPC #230 (merge a79d7c8) and QDistSAT #18 (merge c5eef912). Each lb was reached by at least two CC runs with different search trees (12 h relabelled or reordered runs on main 1239e9a, yfclab2 CPUs 64-95). This is the same engine family, not an independent method.

Old	New
TN_324_4_22to25	TN_324_4_23to25
TN_496_2_27to30	TN_496_2_28to30
TN_540_4_23to34	TN_540_4_24to34
TN_648_14_21to28	TN_648_14_22to28
TN_684_2_22to29	TN_684_2_24to29 (lb 24 from two relabelled erasure runs, 39 232 s and 39 063 s)
COLOR_1027_1_28to37	COLOR_1027_1_31to37
COLOR_2791_1_26to61	COLOR_2791_1_28to61

Still PLAUSIBLE (single tree): COLOR_1027 lb 32 and COLOR_2791 lb 29. Two 12 h runs on main 755e0c2 are checking COLOR_2791 lb 29 (yfclab2 CPUs 65-66).

Records: optimization/experiments/GH-225/lb-repro/.

GH-225 follow-up: 12 h lb-push runs (yfclab2, CPUs 64-95)

COLOR_2791 lb 29 is reproduced. A -cc-roworder=bfs run on main 755e0c2 searched a different tree from [Mac agent] CC engine: cost-aware erasure gate (GH-225 follow-up) #227 C and reached lb 29 at 37 963 s. A -cc-roworder=index run reached it at 20 425 s, but its tree is essentially C's, so I do not count it as a separate order.
Two different-tree runs reached each of these new lbs. C = 755e0c2's default (gated erasure); E = 1239e9a plus ungated erasure.
- TN_288 23: C 30 093 s, E 30 030 s.
- TN_432 24: C 29 251 s, E 29 784 s.
- TN_468 24: C 38 806 s, E 38 061 s.
- TN_576 25: C 28 223 s, E 30 871 s.
- TN_612 25: C 35 008 s, E 37 476 s.
- COLOR_1027 32: C 38 288 s, and an E index-order run on the [Mac agent] CC engine: erasure bound as a default rule (on top of GH-217 candidate A) #225 tree at 37 190 s.
Still PLAUSIBLE: BB_1080 lb 34. Only C reached it, at 40 586 s; E reached only 32 in 12 h.

Rename PRs: #232 (CI green) and guluchen/QDistSAT#19. QDistSAT's test (3.9) job fails in setup because ubuntu-latest is now Ubuntu 26.04 and has no Python 3.9. The fix needs a workflow edit, so both PRs are on hold.

Records: optimization/experiments/GH-225/lb-push/ on branch data/gh225-lb-push.

data: finish the GH-225 follow-up renames (19 stems in this branch)

GH-225 follow-up complete (24-36 h runs, yfclab2 CPUs 64-95). DistQLDPC #232 and QDistSAT #19 now rename 19 tier5 stems; both are open and not merged, because QDistSAT's test (3.9) job is red (ubuntu-latest is now Ubuntu 26.04, which has no Python 3.9).

Solved: BB_756_16_34, TN_288_2_24, TN_360_4_24, TN_496_2_30. Each lb was reached by two different-tree runs (main 755e0c2's gated-erasure CC default and main 1239e9a plus ungated erasure), and the [Mac agent] Stern/Dumer collision step in the verified upper-bound finder (large open codes) #146 witness of the same weight is VALID.
Raised (two different-tree runs each): BB_1080 34, BB_864 34, COLOR_1027 33, COLOR_2791 30, TN_324 24, TN_396 24, TN_432 25, TN_468 25, TN_504 25, TN_540 25, TN_576 26, TN_612 26, TN_648_10 23, TN_648_14 23, TN_684 25.
Still PLAUSIBLE: COLOR_2791 lb 31 (one tree, 88 551 s).

Pure-Python re-checks are in optimization/experiments/GH-225/lb-push/: last-level EMPTY in all 71 runs, odd-level parity of the BB codes, and the XZ-dual maps of all X-half-only codes (including TN_496). This is the same engine family, not an independent method; both arms use the erasure rule.

records: strip host-specific details from the GH-225 lb-push records

data: rename 19 tier5 stems with reproduced CC lower bounds (GH-225 f…

Navigation Menu

Repository navigation

[Mac agent] CC engine: erasure bound as a default rule (on top of GH-217 candidate A) #225

Question

Comparison

Plan

Verdict: NO-GO. Erasure does not join the CC default with its current gate.

Tier 5 (6 h, default seed, A = PR #220 head = main minus the polling fix, E = A + erasure; yfclab2 CPUs 104-127)

Earlier gates (all PASS)

Suggested follow-up

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

[Mac agent] CC engine: erasure bound as a default rule (on top of GH-217 candidate A) #225

Description

Question

Comparison

Plan

Activity

guluchen commented on Nov 4, 2026

guluchen commented on Nov 4, 2026

guluchen commented on Nov 5, 2026

Verdict: NO-GO. Erasure does not join the CC default with its current gate.

Tier 5 (6 h, default seed, A = PR #220 head = main minus the polling fix, E = A + erasure; yfclab2 CPUs 104-127)

Earlier gates (all PASS)

Suggested follow-up

guluchen commented on Nov 5, 2026

guluchen commented on Nov 6, 2026

guluchen commented on Nov 8, 2026

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions