Research · Papers · Symmetry, state encodings and search gauges · MF-017
Sparse exact synthesis of a 69,862-variable allocator
Sparse exact CEGIS with 120× row-order symmetry reduction solved a 69,862-variable instance in 12 rounds (26 s); monolithic timed out
Published 2026-08-29
For everyone
Plain summary
This paper reports a practical way to solve a 69,862-variable exact search problem for an allocator. Instead of writing out every requirement at the start, the search uses a feedback loop. A SAT solver proposes an allocator design. Replay tests that design against the required behavior, catches concrete failures—specifically wrong fixed points or missing cases—and feeds only those observed failures back into the next search. Combining this selective feedback with a 120-fold symmetry reduction across equivalent row orders let the search finish in 12 rounds taking 26 seconds. The all-at-once encoding timed out twice. This is an empirical record for this allocator and run, not a general timing guarantee for all synthesis tasks.
Result
For the recorded allocator, a sparse exact CEGIS loop adding only replay-discovered wrong fixed points and completeness failures, paired with 120× row-order symmetry reduction, solved a 69,862-variable instance in 12 SAT/replay/refine rounds taking 26 seconds. The monolithic encoding timed out twice.
Setting and definitions
CEGIS denotes counterexample-guided inductive synthesis. In this sparse formulation, the refinement set accumulates only wrong fixed points and completeness failures surfaced by replay. Row-order symmetry reduction quotients the search space by the 120-fold equivalence group of row permutations.
The allocator is the 69,862-variable exact-synthesis instance designated in the register. "Sparse" specifies the refinement policy, not an approximation of correctness. Tractability is operational: 12 SAT/replay/refine rounds completed in 26 seconds.
Method
Each loop iteration begins with a SAT solver generating a candidate allocator under the current constraint set. Replay evaluates the candidate against target behavior. When replay exposes a wrong fixed point or completeness failure, the loop appends only that observed counterexample to refine the next query, omitting unobserved failure modes.
A 120× row-order symmetry reduction runs alongside this refinement policy. The run resolved in 12 SAT/replay/refine rounds in 26 seconds. By contrast, the monolithic formulation timed out twice.
The raw run records in this paper's downloadable evidence pack document the 12 rounds, the 120× symmetry reduction, the 69,862-variable count, and the 26-second runtime.
Discussion
This entry establishes tractability for the recorded 69,862-variable allocator under sparse refinement and row-order symmetry reduction. It contains no general complexity theorem, universal runtime bound, or multi-allocator benchmark.
The two timeouts of the monolithic encoding form the baseline comparison. The register omits solver options, hardware specifications, per-round runtimes, and prior-art attributions; these cannot be supplied from external sources.
No correction is recorded for MF-017. Scope remains bounded by the instance and run documented in this paper's downloadable evidence pack.
For everyone — the takeaway
What this means
The method makes a large exact search run to completion by learning strictly from observed errors rather than building an intractable all-in-one formula. Collapsing 120 equivalent row permutations stops the solver from retrying symmetric variants of the same design.
The benchmark demonstrates the payoff: the monolithic encoding timed out twice, while the sparse loop finished in 26 seconds over 12 iterations. This provides a concrete pattern for similar exact synthesis workflows without asserting that every large problem will see the same speedup.
Register references
- MF-017.
BRIEF §A.2.- Prior-art work: the register does not record this.
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 0 of 0 receipt files bundled (1 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-08-29
- 2026-08-29Published on this site.