Noise-Tolerant Verification of Compositional Boolean Recovery

A network can be a few hundred bit-flips from the true parity rule yet have an algebraic normal form (ANF) of $24{,}998$ monomials. We call this the *Möbius noise zone*: small residual error catastrophically inflates apparent algebraic complexity, so the natural exact test for compositional recovery (symbolic ANF equality) spuriously rejects networks that behaviorally learned the rule. Accuracy alone errs the opposite way, accepting high-error shortcuts that match the target on easy inputs without computing it. We introduce a noise-tolerant verification framework: Reed--Muller decoding certifies whether the network lies inside the unique-decoding ball of a candidate of known ANF degree, and Walsh-spectrum agreement supplies an exact $L_2$ distance of $4\delta$, where $\delta$ is the bit-error rate. Inside a small template bank of plausible compositional hypotheses, these checks rank the correct rule top-1 in $23/25$ task/output cells on parity, modular addition, and modular multiplication; the two failures correctly flag non-recovered bits. The post-verification residual $e = f \oplus h$ is structured: on modular multiplication, a one-line risk score yields a $3$--$10\times$ spread between low- and high-risk failure rates (high-risk at $1.4$--$1.9\times$ the random baseline), pinpointing where generalization breaks down.