mac-3 — exact (a·b) mod p via learned cells on a carry-save 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 two 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 76b01d578d | T10 | 100% (1000/1000) | 45.04 s |
Tier 0 (unscored pure-multiplication diagnostic): 80/100 — sub-groups whose
parameters fit the declared operating range are computed by the network; the
remainder are answered [0] by the budget guard. A full local evaluation with
the official open-source runner reproduces the result end to end
(overall_accuracy = 1.0, highest_tier_above_90 = 10,
deterministic: true per the runner's own determinism check).
Architecture
Two 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
The accumulator is held in redundant carry-save form (a sum/carry
bit-vector pair). Adding a vector is a single elementwise layer of
full-adder cells (3:2 compression), depth-1, with no carry propagation.
Doubling is a shift. Bits overflowing the register are compensated by
injecting the constant 2^Wd mod p, itself computed in-network from p
by the subtractor cell at setup. A fixed Horner double-and-add recurrence over
the raw operand bits composes these steps into (a·b) mod p: reduce
b mod p, then accumulate over the bits of a. Carries are resolved exactly
once per phase by a bit-serial adder chain followed by conditional
subtractions of shifted p.
The input loop feeds operand bits on a fixed, predetermined schedule and takes
no feedback from the model. All shifts and wrap routing are fixed; all wrap
bookkeeping uses fixed, unconditional round counts — no value-driven
control flow anywhere. 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.
Batches are internally sub-grouped by prime bit-length (input-derived
routing), so mixed-width batches process each width at its own cost.
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. 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 rows each), so exactness is
certified by exhaustive verification and preserved under composition, at every
operand width, for every operand family. The carry-save form additionally
makes every in-loop step an elementwise, depth-1 application of the same
certified cells.
Exactness and precision certification
- Exhaustive truth-table verification: all 16 rows across the two cells
are exact; these rows are the entire reachable input space of the
network's cells.
- Saturated decision margins: minimum |logit| ≥ 6.07 over all rows
(hinge-hardened).
- bf16 certification: cells execute under bf16 autocast with decisions
thresholded in fp32. Verified exhaustively: 0 decision flips fp32↔bf16 on
all rows; maximum observed logit perturbation ≈ 0.09 vs. margin ≥ 6.07.
- Structured-operand families: exact by construction and verified on
power-of-two-adjacent operands (2^k, 2^k±1) and Mersenne moduli, plus
exhaustive-dense small-prime sweeps and mixed-width (heterogeneous) batches.
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), applied per width sub-group. Problems outside this
range are answered with [0] without running the network, in line with the
compliant always_zero reference behavior for unattempted problems.
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.
- Missing
model_config.json falls back to safe submission defaults
(fp32 path).
Files
model.py — submission entry point, I/O, width sub-grouping and guards.modeling/cs_pipeline.py — the cells and the carry-save pipeline.adder.pt, subtractor.pt — trained cell weights.model_config.json, manifest.json — configuration and manifest.
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.
