Research · Papers · The SHA-256 record and exact synthesis · MF-020
Full-domain replay for candidate XAG validity
∀x ∈ {0,1}^n, C(x) = f(x)
Published 2026-08-29
For everyone
Plain summary
Two shortcuts repeatedly suggested circuit improvements that disappeared on complete checking. ABC overlap counts compare how often internal signals share structure. They can guide a search, yet three such readings produced mirage wins, apparent improvements that were not real. A second shortcut fit a circuit on only part of the input table. CEGIS is a loop that proposes a circuit, finds a counterexample, and refines the proposal. In the recorded examples, circuits fit 180 checked rows while retaining zero real directions, so the sample gave a convincing answer with no valid full behavior. The dependable test is full-domain replay: run the proposed circuit on every input and compare its outputs with the target. MF-020 presents this as a method for distrusting instruments, not a numerical lower bound. The register does not state a prior-art position.
Result
Let C be a candidate XAG for a target Boolean function f on n inputs. Agreement with ABC overlap statistics or with a partial CEGIS sample is insufficient to establish the claimed circuit improvement. The claim must be checked by replay over the full domain:
\forall x \in \{0,1\}^n, C(x) = f(x).
The register records three ABC mirage wins and partial-domain CEGIS fits of 180 rows with zero real directions. Full-domain replay is the only arbiter recorded for the circuit claim.
Setting and definitions
An XAG is an XOR-and-AND graph representation of a Boolean function. C denotes the candidate graph and f the target function. ABC overlap statistics are the recorded overlap measurements used as an instrument during search. The entry does not give a further definition of the particular overlap statistic.
CEGIS is used here as an iterative exact-synthesis procedure that works from a selected set of rows, proposes a candidate, and refines it when a counterexample is found. A partial-domain fit means agreement on the rows currently supplied to that procedure. The phrase zero real directions is retained from the register; the register does not define that term further.
Full-domain replay evaluates C on every element of {0,1}^n and compares the resulting output with f. A circuit claim is therefore separated from the search instrument that proposed the candidate. The method concerns the validity of the claimed function over the domain; the entry does not state a separate cost model or a numerical improvement.
Method
The result was established through the instrument-distrust exhibits recorded in HANDOFF section 3. The first exhibit class compared ABC overlap statistics with the actual outcomes of candidate XAG claims. Three separate mirage wins were recorded. Each is evidence that an overlap signal can suggest an improvement which does not survive the check required for the function claim.
The second exhibit class used partial-domain CEGIS fits. The recorded circuits fit 180 rows with zero real directions. This is the relevant failure mode for sample-based evidence: a candidate can satisfy the supplied rows while the sample fails to expose the behavior that matters elsewhere in the domain. The register summarizes this distinction as sample-valid not equal to valid.
The decisive procedure was full-domain replay. After a candidate was suggested by the instrument or fit by the partial procedure, its behavior was replayed over the full Boolean domain and checked against the target. The register identifies that replay as the only arbiter. The method therefore uses these instruments for proposing cases and reserves the complete replay for deciding whether the function claim survives.
The source record names no individual ABC statistic, no solver, no encoding format, and no separate certificate artifact beyond HANDOFF section 3. Those details are not supplied here. The evidence is the recorded comparison between heuristic or partial-domain indications and the full-domain replay checks.
Discussion
MF-020 sets an evidence hierarchy for exact circuit work. ABC overlap counts may still be useful as search signals. The three mirage wins show that their agreement with a hoped-for improvement cannot serve as the final check. The entry does not claim that every overlap statistic fails on every candidate. It records that the instrument produced three separate false indications in the examined exhibits.
Partial-domain CEGIS has the same boundary. Fitting 180 rows is a statement about those 180 rows. It is not a statement about the entire Boolean function when the remaining rows have not been replayed. The recorded zero real directions make the warning concrete, while the register gives no further definition or count for that phrase.
Full-domain replay resolves the specific validity question: whether the candidate and target agree on all inputs in the encoded domain. MF-020 does not report a new lower bound, an improved XAG, or a universal theorem about all search instruments. It gives a method for deciding when an apparent improvement has earned the status of a circuit result.
There are no corrections recorded for this entry. No prior-art position is stated in the curation notes, and the register does not record one. The page verdict is SHOW because the three mirage wins and the 180-row fits provide direct exhibits for the method's central warning.
For everyone — the takeaway
What this means
A shortcut can be a useful search compass and a poor judge. An overlap count can point a researcher toward a promising circuit. Fitting selected rows can produce a candidate quickly. Neither result carries the meaning of a complete function check. Full-domain replay asks the simple decisive question: does the candidate give the target output for every possible input? That habit matters whenever a system is optimized with a proxy score or a sample. MF-020's contribution is practical. It keeps a suggestive measurement in its proper role and gives the final decision to the complete replay.
Register references
- Entry: MF-020
- Receipt: HANDOFF section 3
- Prior art: 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.