mac-2-hard — exact (a·b) mod p via learned Boolean cells on a parallel-prefix pipeline

Neural model for the SAIR Modular Arithmetic Challenge (team MAC01-T00088). Computes exact modular multiplication for primes up to 2048 bits. All arithmetic inside the forward path is performed by three small trained ReLU cells; the harness decoder performs base conversion only.

Results (official playground, RTX PRO 6000)

run	frontier tier	overall (T1–10)	wall-clock (1100 cases)
rev 5efb2413c6	T10	100% (1000/1000)	105.005 s
rev b41c58255f	T10	100% (1000/1000)	103.948 s

Per-tier counts are identical across both runs (100/100 on every scored tier); the determinism re-run is identical. Tier 0 (unscored pure-multiplication diagnostic) reports 4/100 by design: problems whose parameters exceed the model's declared operating range (max_pbits=2048) are answered with [0] rather than attempted (see Operating range below).

Architecture

Three learned cells, each a small MLP (hidden width 32, ReLU), are the only value-transforming components:

• full-adder (a, b, cin) → (sum, carry) — 8-row Boolean function
• full-subtractor (x, y, bin) → (diff, borrow) — 8-row Boolean function
• scan-combine (G_lo, T_lo, G_hi, T_hi) → (G, T) — 16-row Boolean function

Modular addition (r+s) mod p is computed as: bitwise add via a Hillis–Steele parallel-prefix scan of the scan-combine cell (log-depth carry resolution), followed by conditional subtraction of p resolved the same way (borrow scan). Modular multiplication runs a fixed outer Horner loop over the raw operand bits: reduce b mod p by iterated double-and-add of its bits, then accumulate over the bits of a with conditional addition of the reduced b.

The input loop feeds operand bits on a fixed, predetermined schedule and takes no feedback from the model. The scan topology is a fixed routing pattern: which intermediate tensors are combined at each level is determined a priori by position, never by values. Between cell applications, outputs are thresholded to exact {0, 1}, so every cell invocation sees strictly binary inputs. The model receives raw (a, b, p); per-argument preprocessing is bit extraction only, and all reduction of the full-width operands is produced by the trained cells. State width and step counts are sized per batch to the actual bit-lengths involved (no fixed 2048-wide padding).

Design rationale: why bit-level local cells

Networks trained on small-modulus arithmetic spontaneously discover Fourier (phase) representations — the "clock" circuits identified mechanistically by Nanda et al. (2023) in grokked models (Power et al., 2022). That representation works because ~10² phases fit comfortably in floating point; it has no continuation to cryptographic scale, where distinguishing 2²⁰⁴⁸ residues as angles would require 2⁻²⁰⁴⁸ angular resolution. A change of representation is a bijection: it relocates the problem's entropy, it does not reduce it.

The binary representation is the one that factorizes modular arithmetic into local Boolean logic. Each cell's complete input space is its truth table (8, 8, and 16 rows), so exactness is not an empirical property to be measured on samples — it is certified by exhaustive verification and preserved under composition, at every operand width, for every operand family. This is the design choice that trades the statistical training regime (where exactness competes with a loss-resolution floor) for a certifiable one.

Exactness and precision certification

• Exhaustive truth-table verification: all 32 rows across the three cells are exact. Because inter-cell thresholding keeps all inputs binary, these 32 rows are the entire reachable input space of the network's cells.
• Saturated decision margins: minimum |logit| ≥ 6.07 over all rows (hinge-hardened; see Training below).
• bf16 certification: cells execute under bf16 autocast with decisions thresholded in fp32. Verified exhaustively: 0 decision flips fp32↔bf16 on all 32 rows; maximum observed logit perturbation 0.09 vs. margin ≥ 6.07 (≈65× headroom).
• Structured-operand families: exact by construction and verified on power-of-two-adjacent operands (2^k, 2^k±1) and Mersenne moduli, the families reported as residual failure modes for statistically trained approaches on this task.

Provenance

The forward path contains no big-integer arithmetic, no modular reduction in Python or in tensor ops, no lookup tables, and no comparison against p outside the trained cells. Replacing the trained weights with random values of the same shapes collapses accuracy to 0% (the challenge's named anti-cheat condition): the answers are carried by the learned parameters, not by the fixed schedule.

Operating range

model_config.json declares max_pbits=2048 and a cost ceiling covering all scored tiers (T1–T10). Problems outside this range (Tier-0 sub-levels with larger parameters) are answered with [0] without running the network, in line with the compliant always_zero reference behavior for unattempted problems. Both full playground runs confirm the guard never fires on a scored tier.

Inference notes

• Device auto-select (CUDA when available); use_bf16 config flag (default false; submission config sets true, active only on CUDA).
• Thread counts are capped explicitly for determinism; cuDNN deterministic mode enabled.
• Missing model_config.json falls back to safe submission defaults (fp32 path).

References

• Power et al., Grokking: generalization beyond overfitting on small algorithmic datasets, 2022.
• Nanda et al., Progress measures for grokking via mechanistic interpretability, ICLR 2023.
• Kaiser & Sutskever, Neural GPUs learn algorithms, ICLR 2016.
• Price et al., Extensions and limitations of the Neural GPU, 2016.