modchallenge-solutions

Our entries + research for the Modular Arithmetic Challenge: learn (a * b) mod p with trained parameters (no hand-coded arithmetic). The challenge repo is kept as a clean reference checkout next door (../modular-arithmetic-challenge); this repo holds our models, training scripts, and experiment notes.

Result (public benchmark, fixed seed, 1100 problems)

Model	Params	Artifact	overall_accuracy	highest_tier_above_90
horner_rnn/	~10.7M	0.04 GB	1.000	10 (the maximum)
smallfield_mlp/ (baseline, tiers 1-2 only)	~10.6M	—	0.216	2

horner_rnn clears every reduction tier, 1 through 10 (primes up to 2^2048): tiers 1-10 = 1.00. Both ranking keys are saturated (highest_tier_above_90 = 10 is the benchmark ceiling; there is no tier 11). Best reference baseline in the challenge repo: 0.127 / tier 1 (dlp_grokking).

The two models have near-identical parameter counts (~10.6M vs ~10.7M) by coincidence — and that is the point: the wide smallfield_mlp baseline spends its capacity on a residue lookup that only covers p < 256 (tiers 1–2, 0.216), while horner_rnn spends the same budget on a learned single-step circuit that composes to every tier. Capacity alone does not generalize across primes; the right inductive bias does.

The approach (horner_rnn/)

Direct classification of (a, b) -> a*b mod p does not generalise across primes — every neural baseline plateaus by tier 3. The Horner step of double-and-add does:

t <- (2*t + a_bit * b) mod p          # one learned step; answer = final state after all bits of a

We train a cell on that single-step map, then run it as an RNN over the bits of a mod p with a hard-quantized bit-vector state — if the cell is exact per step, the chain is exact end-to-end, and it generalises to held-out primes (val == train per step), which is the evidence it is learning rather than memorising. Every cell is the same carry-aware TCN (a non-causal dilated 1-D conv over bit-positions, weight-shared across positions) so it learns one carry/borrow rule applied everywhere — driving per-step error ~15× below an MLP, which is what makes the deep (≥128-step) chains hold up.

Two shared weight files, routed by prime size — one shared set covers 16 through 512 bits, one covers 1024 through 2048 bits:

Weight file	Primes	Tiers	Public
weights_shared_16_512.pt	< 2^512	1-8	1.00 / 1.00 / 1.00 / 1.00 / 1.00 / 1.00 / 1.00 / 1.00
weights_shared_1024_2048.pt	< 2^2048	9-10	1.00 / 1.00

The standalone submission, including both trained weight files, is published at XllentAI/modular_arithmetic. The horner_rnn/ directory in this repository contains the matching model source, manifest, and documentation; download the weights as described in REPRODUCE.md. Three findings drove the accuracy and recur throughout the notes below: sample primes uniform-by-value (matches the test generator), train the state on the true Horner trajectory, and match the benchmark's prime-width distribution (a cell trained near-max-width only scores ~0 on shorter primes).

Repo layout

Path	What
horner_rnn/	submission source and documentation — model.py (entry class), manifest.json, and the legacy MLP-era train.py; trained weights are downloaded separately from Hugging Face
smallfield_mlp/	early enumerable-tier baseline (exact on tiers 1-2 via a residue-pair MLP)
exploration/	training scripts, eval/diagnostics, and research notes (below)
exploration/monoid/	self-contained research variant — can SGD discover a provably-exact mod-mult automaton from global labels? (README.md there; not shipped, zero leaderboard upside)
checkpoints/, logs/	local-only working artifacts (gitignored)

Research notes (in exploration/)

• TIER10_NOTES.md — tier-10 octave transfer + low-lr tail + two hardening tails (0.94 → 1.00)
• TIEBREAKER_NOTES.md — what moves each ranking key once tier 10 ships
• UNIFICATION_NOTES.md / UNIFY_BUILD_SPEC.md — collapsing the small/mid and high cells into two shared sets
• GENERALIZE_RESEARCH.md — cross-prime generalisation findings
• monoid/README.md — the guaranteed-100% (exact-automaton) research bet, settled

Training & evaluating

Full setup + reproduction walkthrough: REPRODUCE.md (environment, weights download, the seeded eval, our evaluation rigor, and retraining). The per-cell training recipes live in horner_rnn/README.md; exploration/EXPERIMENT_INDEX.md says which exploration/ script is canonical vs a research dead-end.

Validate against the public benchmark with the venv active, from this repo's root:

# the public benchmark uses a FIXED seed; WITHOUT --seed the CLI draws a fresh RANDOM sample
# (so it will NOT reproduce the headline number).
PUBLIC_SEED=$(python -c "print(b'modchallenge-public-benchmark-v1'.hex())")
modchallenge check    horner_rnn
modchallenge evaluate horner_rnn --total 1100 --seed "$PUBLIC_SEED"
# -> overall_accuracy 1.000, highest_tier_above_90 10, deterministic True

Compliance

Identity preprocess hooks (no cross-argument leakage); the legal two-operand int(x) % p reduction inside predict_digits; no hand-coded arithmetic over the inputs — tokenise/scan/readout is weight-independent architecture that computes nothing by itself, and all the arithmetic lives in the trained cell weights (perturb them and accuracy collapses to the floor; an untrained re-init scores 0.00 — see exploration/compliance_perturb.py). Held-out-prime generalisation is the anti-memorisation evidence. Passes modchallenge check and the determinism check.