Phase-Gated Mixtures of Experts for Modular Arithmetic

Neural networks are, by construction, smooth: a small change in the input should produce a small change in the output. Modular arithmetic breaks this contract at every wrap-around, where adding one to $q-1$ sends you back to $0$ — a jump discontinuity that sits exactly at the boundary of what continuous approximators handle well. The empirical record is stark. Transformers drop to near-chance or 0% accuracy on periodic formal languages like parity where LSTMs hold 100% On the Ability and Limitations of Transformers to Recognize Formal Languages, and in cryptanalysis of the Learning with Errors (LWE) problem, neural attacks succeed only when most training samples never wrap around the modulus at all — the "NoMod" condition, with failure below roughly 67% non-wrapping samples SALSA VERDE: a machine learning attack on LWE with sparse small secrets.

Meanwhile, a separate line of work proves that Mixture-of-Experts (MoE) models — networks where a gating function decides which of several local experts handles each input — can approximate any conditional probability density $f(y|x)$ to arbitrary accuracy on compact Euclidean domains, via a constructive three-step argument: partition the input space, approximate the hard partition with soft gating, and approximate the local density with a small mixture Approximations of conditional probability density functions in Lebesgue spaces via mixture of experts models. Nobody has asked what happens when the target lives on a circle instead of a line. This proposal argues the two fields are two halves of one question: whether the modular-counting failure is a fundamental capacity limit of smooth sequence models, or a localization failure that a mixture architecture with the right gating geometry can provably repair.

Core Claim

The claim is two-sided. Theoretically, the constructive denseness machinery for conditional densities extends to quotient domains: MoE models with softmax gating over phase buckets — intervals $[kq, (k+1)q)$ of the lifted real line — and local location-scale experts are dense in $L_p$ for conditional densities on the torus $\mathbb{R}/q\mathbb{Z}$, i.e., densities satisfying $f(y + q \mid x) = f(y \mid x)$. The wrap-around discontinuity, which is fatal for a single smooth model, is harmless to a mixture: each expert sees only an unwrapped local segment, and the gating network absorbs the discontinuity into its partition boundaries, exactly where mixture theory already places sharp transitions. Empirically, an architecture built from this proof — a phase-gated MoE whose gating network routes by wrap count and whose experts predict unwrapped residuals — should push modular-arithmetic performance past limits that monolithic Transformers with angular embeddings cannot pass, notably the 67% NoMod threshold and the $N=128$-term plateau.

The existing theory cannot be applied as-is: Approximations of conditional probability density functions in Lebesgue spaces via mixture of experts models assumes a compact Euclidean input space $[0,1]^d$ and Euclidean output, with no periodicity. What we add is a lifting argument: the torus target is covered by finitely many unwrapped charts, the mixture runs per-chart, and periodicity is restored by summing the lifted density over charts. This is close in spirit to the observation that real-valued networks cannot represent cyclic phase transitions without complex or angular structure Representing Unordered Data Using Complex-Weighted Multiset Automata, but it differs in the remedy: rather than changing the weights to complex values, we change the decomposition to localize phase, keeping every component real and standard.

Research Program

The theoretical work has two parts. First, the denseness theorem on the torus. Let the conditional density $f(y \mid x)$ be defined on $\mathbb{T} = \mathbb{R}/q\mathbb{Z}$ with $x$ in a compact Euclidean domain, and let the MoE take its usual form

$$f_K(y \mid x) = \sum_{k=1}^{K} w_k(x)\, \phi\!\left(y;\, \mu_k(x), \sigma_k(x)\right),$$

where $w_k$ is softmax gating, $\phi$ a location-scale kernel, and the expert means $\mu_k$ are allowed to range over the lifted real line rather than being confined to $[0, q)$. The proof follows the three-step template of Approximations of conditional probability density functions in Lebesgue spaces via mixture of experts models — piecewise approximation, gating approximation, expert approximation — with one new step: the target is lifted to a finite union of phase intervals, approximated there by the standard construction, and re-projected by periodization. The softmax-versus-Gaussian-gating equivalence from that paper's Lemma 1 carries over unchanged, which matters practically because it means the result covers both gating parameterizations we might implement. Second, and more valuable because the existing literature explicitly lacks it, we aim for a quantitative bound: for target conditional densities whose lift is piecewise Lipschitz with $J$ wrap discontinuities, approximation error in $L_p$ should scale like a term decaying in the number of phase buckets times a term decaying in experts per bucket. No rate result exists in the Euclidean MoE literature either A Universal Approximation Theorem for Mixture-of-Experts Models, so even the Euclidean special case of this bound would be a contribution; the modular case adds the bucket-count dependence, and the empirical prediction is testable — error should fall as wrap-coverage per expert shrinks.

The architectural work translates the proof into a sequence model. The model maintains an accumulator (a running sum of embedded inputs, as any attention model implicitly does), and the gating network partitions accumulator space into phase buckets, activating one expert per bucket. Each expert predicts a density over the unwrapped residual — the offset of the true sum within its bucket — so no expert ever sees a discontinuity. The output head places this on the circle, combining the phase-bucket estimate with the angular representation $(\sin(2\pi y/q), \cos(2\pi y/q))$ used successfully by Salsa Fresca: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errors. We reuse their angular output encoding but replace their monolithic predictor with a gated mixture; the theory says the gating, not the encoding, is what buys the guarantee. Training follows maximum likelihood on the mixture density rather than mean-square error on the angle, which sidesteps the origin-collapse failure mode documented in Teaching Transformers Modular Arithmetic at Scale, where angular-embedded models trained with MSE collapse to the circle's center unless propped up by a radial regularizer. Density training makes collapse impossible in principle: the origin is not on the support of the target density.

An honest caveat shapes the program: approximation theory says nothing about whether gradient descent finds the good mixture. The universal approximation literature itself flags this gap between denseness and estimability A Universal Approximation Theorem for Mixture-of-Experts Models, and work on softmax Gaussian MoEs shows temperature and sample-size effects govern which regimes are learnable Is Temperature Sample Efficient for Softmax Gaussian Mixture of Experts?. We therefore treat the theorem as a soundness argument for the architecture and rely on experiments, plus width-related optimization results suggesting that adding parameters can eliminate spurious minima On the Benefit of Width for Neural Networks: Disappearance of Basins, to address trainability. The grokking-interpretability studies Towards Empirical Interpretation of Internal Circuits and Properties in Grokked Transformers on Modular Polynomials and Interpreting Grokked Transformers in Complex Modular Arithmetic supply a useful diagnostic lens: they show monolithic Transformers that eventually learn modular addition build implicit Fourier circuits. We will check whether our phase-gated model instead builds the explicit spatial partition the theory predicts — a clean mechanistic contrast between the two solutions.

Proposed Experiments

Three testbeds, in increasing difficulty. First, the formal-language suite of On the Ability and Limitations of Transformers to Recognize Formal Languages: parity and $(aa)^*$, trained on lengths 1–50, tested to 150. The reference numbers are concrete — LSTMs maintain 100% on these periodic languages while standard Transformers drop to 0%. A phase-gated mixture that holds near-100% at length 150, without recurrence, would be the first feed-forward-style model to do so on this suite.

Second, the scaled modular addition testbed of Teaching Transformers Modular Arithmetic at Scale: predict $\left(\sum_{i=1}^{N} x_i\right) \bmod q$. The strongest reported result there is high-accuracy summation of $N = 128$ terms modulo $q \approx 10^6$, using angular embeddings, a circle-enforcing regularizer, and an inverse-square-root training distribution; the same paper reports near-100% accuracy on parity and associative recall with its custom data distributions, and LWE secret recovery at Hamming weight 6, twice the prior limit of 3. Our decisive comparisons are: (a) match $N=128$ at $q \approx 10^6$ with uniform training data, since the theory predicts the mixture needs no distributional crutch, and their own results show monolithic models fail outside a narrow "Goldilocks" band of training-distribution divergence; (b) exceed $N=128$, targeting $N \ge 256$, which directly tests whether localization removes the plateau; (c) degrade the NoMod proportion below the 67% threshold of SALSA VERDE: a machine learning attack on LWE with sparse small secrets and show the mixture survives where the Transformer fails. For modular multiplication — unsolved by all prior work in the file — we report it as exploratory with no success criterion, since no baseline exists to beat.

Third, the LWE benchmarking framework of Benchmarking Attacks on Learning with Errors, which reports that standard SALSA-style attacks succeed only on secrets of Hamming weight $\le 3$ (the "ML modular ceiling"), while the augmented pipeline of Teaching Transformers Modular Arithmetic at Scale reaches Hamming weight 6. Beating this proposal's claim means recovering secrets at Hamming weight $\ge 8$ on the same sparse-secret parameter families, with identical lattice preprocessing (Flatter, per Salsa Fresca) so the comparison isolates the neural component. For the no-reported-number cases we are explicit: no reported result found on Lacuna for phase-gated MoE models on any LWE track, nor for LSTMs on any LWE benchmark.

Baselines

The naive reference point is a standard Transformer with plain integer embeddings and no angular machinery, trained uniformly. On parity and $(aa)^*$ this baseline is documented to fall to 0% accuracy on longer strings while LSTMs hold 100% On the Ability and Limitations of Transformers to Recognize Formal Languages; on LWE-style inner products it is documented to fail outright Benchmarking Attacks on Learning with Errors. It defines the failure floor we must clear.

The strongest competitor is the full pipeline of Teaching Transformers Modular Arithmetic at Scale: an encoder-only Transformer with angular embeddings, the circle-enforcing regularizer $\ell = \alpha(x'^2 + y'^2 + 1/(x'^2+y'^2)) + \text{MSE}$, and the inverse-square-root sampling distribution. It is the strongest because it holds every documented record on our testbeds: $N=128$ terms modulo $q \approx 10^6$, near-100% parity and associative recall, and LWE recovery at Hamming weight 6 versus the prior ceiling of 3. To keep the comparison fair, both models get the same parameter count, the same training tokens, the same lattice preprocessing where applicable, and the same tuning budget (a fixed grid of learning rates, batch sizes, and the mixture's analogue of their temperature hyperparameter); when comparing under uniform training data we disable their distributional sampling and ours equally. Beating it means one of three concrete outcomes: high accuracy at $N \ge 256$ where they plateau at 128; high accuracy under uniform training data where their monolithic model is documented to fail outside the Goldilocks KL band; or Hamming weight $\ge 8$ secret recovery where they reach 6. Any single one counts as a win for the localization thesis; none of them counts if it requires more compute.

Two secondary baselines calibrate the field. An LSTM establishes the recurrence ceiling on parity (100% at length 150, per On the Ability and Limitations of Transformers to Recognize Formal Languages) and tests whether it can be ported to the high-dimensional LWE setting at all, which no paper in the file has attempted. And the pre-trained angular-embedding attack of Salsa Fresca: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errors, which recovered sparse binary secrets at dimension $n=1024$, anchors the cryptanalysis end.

The key ablation is our own model with the phase-gating replaced by standard Euclidean softmax gating over input tokens, keeping experts, density head, and parameter count identical. If phase-gated gating beats standard gating on the wrap-heavy regimes (low NoMod, large $N$) while matching it on wrap-free regimes, the architectural ingredient — not the mixture, not the density loss — is doing the work. A second ablation removes the density head in favor of MSE-plus-regularizer to test whether maximum likelihood on the mixture is what prevents angular collapse.

Why not just…?

Why not just use an LSTM, which already solves modular counting? On the formal-language suite, this is a genuine threat: LSTMs hold 100% on parity and $(aa)^*$ where Transformers drop to 0% On the Ability and Limitations of Transformers to Recognize Formal Languages. But the same paper shows LSTMs lose the parallelism and length generalization advantages that make attention models dominant on hierarchical counter languages, and nothing in the file demonstrates an LSTM operating on the LWE setting, where models must ingest millions of high-dimensional samples produced by lattice preprocessing SALSA VERDE: a machine learning attack on LWE with sparse small secrets. We will run the LSTM on parity as a ceiling reference and attempt it on the modular addition testbed; if it matches the mixture at $N \ge 256$ and $q \approx 10^6$, the architectural contribution collapses to a negative result about LSTMs scaling — which we would report, but the LWE-dimension evidence makes this unlikely enough to justify the proposal.

Why not just use angular embeddings on a standard Transformer? This is the closest existing solution and our primary baseline. It works — it enabled recovery at $n = 1024$ Salsa Fresca: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errors and $N = 128$ summation Teaching Transformers Modular Arithmetic at Scale — but the file documents three specific fragilities: origin collapse under MSE requiring a bespoke regularizer, a narrow Goldilocks band of training-distribution divergence outside which the model fails completely, and hard plateaus at $N = 128$ and Hamming weight 6, with modular multiplication unsolved. Our claim is precisely that these plateaus are localization failures that gating removes; if the mixture does not beat the angular baseline at its plateaus under matched compute, the hypothesis is wrong and we will say so.

Why not just fix the data distribution with curriculum learning? The file contains a direct negative result: traditional curriculum learning was tried and proved highly sensitive to hyperparameters with noisy outcomes, and the static inverse-square-root distribution that did work sits in a fragile KL-divergence window Teaching Transformers Modular Arithmetic at Scale. Data manipulation alone has never pushed past the plateaus it currently holds. We include it implicitly — our strongest baseline is the best data-distribution method — and our uniform-training-data condition is the direct test of whether architecture substitutes for distribution engineering.

Why not just use classical lattice reduction and skip neural models? On real cryptographic parameters this objection stands, and we do not contest it: every successful ML attack in the file still requires classical preprocessing, and none comes close to standardized Kyber or HE security parameters. Our question is narrower and scientific — whether the NoMod ceiling is an architectural property or a data property — and the concrete runtimes in the file (neural recovery in 4.5 hours at $n=256$ where uSVP fails after weeks SALSA VERDE; uSVP failing within 1100+ hours where other methods succeed under 40 Benchmarking Attacks on Learning with Errors) show neural methods occupy a real, if sparse-secret, niche.

Decisive Checks

The proposal succeeds or fails on three numbers. Parity at length 150: near-100% without recurrence clears the documented attention failure. Modular addition: $N \ge 256$ at $q \approx 10^6$ under uniform data beats the documented plateau of 128 and the documented distribution fragility. LWE: Hamming weight $\ge 8$ with matched preprocessing beats the documented ceiling of 6. The theory stands independently: the torus denseness theorem and the bucket-count rate bound are checkable by proof regardless of whether training finds the good mixture — and if the experiments fail while the theorem stands, the gap between MoE approximation and MoE estimability becomes itself the follow-up question, one the existing universal-approximation literature has already flagged but never instantiated on a task where the failure mode is this well-characterized A Universal Approximation Theorem for Mixture-of-Experts Models.