When Integer Overflow Makes On-Device Learning Cryptographically Hard

Small chips without floating-point hardware store numbers in fixed-width integer registers. When a sum grows too large for its register, many of these chips quietly "wrap around": the value is reduced modulo $2^b$, the way a car odometer rolls over. This proposal starts from the observation that wraparound turns a linear model into a periodic function of its input. Periodic functions of a linear projection are exactly the kind of learning problem that cryptographers have proven hard. On the Cryptographic Hardness of Learning Single Periodic Neurons shows that learning $\cos(2\pi\gamma\langle w,x\rangle)$ under polynomial noise is as hard as worst-case lattice problems, the same problems post-quantum encryption relies on. Our hypothesis is that some part of the "training collapse" seen when microcontrollers fine-tune with fixed quantization scales is this hardness showing up on real silicon, and not only a tuning defect.

The practical stakes are concrete. PRIOT found that integer-only weight updates with static scale factors collapse on a Raspberry Pi Pico. Its fix freezes the weights and trains pruning scores instead, at up to 72.26% extra memory. If collapse is caused by wraparound, a much cheaper fix exists: saturating arithmetic, which clips at the register limit instead of rolling over. We would also get a way to predict, before deployment, which combinations of bit width, scale and weight norm can be trained on the chip at all. If collapse is instead caused by updates rounding to zero, the cryptographic explanation is wrong for PRIOT's setting, and the experiments below are designed to show that cleanly.

Core Claim

A $b$-bit wrapping accumulator with fixed scale $s$ computes $(s\langle w,x\rangle) \bmod 2^b$. Over an input distribution with spread $\sigma$ along $w$, this behaves like a periodic neuron with effective frequency

$$\gamma_{\text{eff}} \approx \frac{s\,\|w\|\,\sigma}{2^b},$$

which counts how many times the accumulator wraps across typical inputs. For a Gaussian input, the correlation between a periodic target of frequency $\gamma$ and any smooth, low-frequency statistic, including the expected gradient, shrinks roughly like

$$\rho(\gamma) \sim e^{-2\pi^2\gamma^2}.$$

This form comes from the Gaussian characteristic function, and it is the mechanism behind the gradient and statistical-query lower bounds of Song, Zadik and Bruna.

The claim has two parts. First, once weight growth during static-scale training pushes $\gamma_{\text{eff}}$ past order one, the gradient signal reaching the chip falls off exponentially, and training stalls or diverges. Second, the cryptographic result says this is not specific to gradient descent: under polynomial noise, no efficient algorithm recovers $w$. The only escape route is the exponentially-small-noise regime, where lattice basis reduction (the LLL algorithm) succeeds. Finite register precision itself sets a noise floor near $2^{-b}$, so on-chip LLL recovery should work only in very small dimensions. That gives a hardware-grounded prediction of where the "easy" regime ends.

Prior work plays three roles here. The hardness results for 0–1 loss minimization (Learning Kernel-Based Halfspaces with the Zero-One Loss) and for agnostic halfspaces from worst-case lattices (Tiegel) motivate the view that average-case lattice hardness, not just NP-hardness, is the right lens for learning on typical data. The closest existing bridge, Tractability via Low Dimensionality, constrains our scope. It proves quantized training NP-hard through worst-case combinatorial gadgets and never models register arithmetic or runs on hardware. We differ on both counts: we use an average-case reduction, and the source of hardness is a physical arithmetic mode that can be switched on and off. Leech Lattice Vector Quantization uses lattice geometry constructively for compression on GPUs. We do not use lattices to compress anything. We use lattice hardness to explain and predict failure. NITI and PRIOT supply the training methods and the collapse phenomenon we set out to diagnose.

Research Program

The work has three parts, all run on a Raspberry Pi Pico, which has no floating-point unit, alongside matched simulations on a server.

The first part uses planted periodic instances. We generate the periodic-neuron family of Song et al. with a known hidden direction $w$, sweeping dimension $d$, frequency $\gamma$ and noise level. These instances have a ground truth and known hardness regimes. On the Pico we run integer stochastic gradient descent and measure the cosine between the averaged gradient and $w$. The test is whether its decay in $\gamma$ follows $\rho(\gamma)$. We also implement integer LLL on the Pico and record the largest dimension at which it recovers $w$ from $d+1$ samples, together with wall-clock time. Song et al. report $O(d^6\log^3 M)$ runtime for this algorithm, so it will be slow, and that slowness is part of what we measure.

The second part induces wraparound in ordinary models. We train linear models and small convolutional networks with static scales under three accumulator modes that differ only in overflow handling: wrapping, saturating, and wider accumulators that never overflow. We instrument overflow counts and estimate $\gamma_{\text{eff}}$ online from accumulator histograms. The prediction is that collapse begins when estimated $\gamma_{\text{eff}}$ crosses order one, and only in the wrapping mode.

The third part diagnoses PRIOT's collapse directly. We reproduce PRIOT's static-scale integer baseline on rotated MNIST at 30° and 45°, and on rotated CIFAR-10 with VGG11 as a stretch goal. We log two quantities during the run: the fraction of weight updates that round to zero, and the fraction of accumulations that overflow.

Baselines

The naive reference points are full-precision training on a server, which serves as an accuracy ceiling, and PRIOT's static-scale integer baseline, which is the known collapsing configuration. We rerun the latter from its description on the same Pico, data and number of epochs.

The strongest existing on-chip method is PRIOT, together with its memory-light variant PRIOT-S. PRIOT reports accuracy gains of 8.08 to 33.75 percentage points over static-scale integer baselines on rotated MNIST, a 72.26% memory increase, and, for PRIOT-S, memory reduced to 28.38% (PRIOT). The file gives no absolute PRIOT accuracy, so we will measure it ourselves under identical conditions. We count it as beaten if static-scale weight training with saturating accumulators lands within one point of PRIOT's accuracy while using less memory than PRIOT-S on the same task.

NITI's dynamic block exponent is the dynamic-scale reference. NITI reports zero accuracy degradation against FP32 for LeNet-5 on MNIST (NITI), but those results were on a GPU and an FPGA. We port it to the Pico and measure its memory and time cost. All methods get the same hyperparameter search budget.

The key ablation changes only the overflow mode, wrapping versus saturating, and holds everything else fixed. A second ablation adds NITI-style pseudo-stochastic rounding, which removes zero-rounding of small updates, while keeping wrapping.

Why not just…?

Why not just blame gradient underflow? Small updates rounding to zero under a fixed scale is a plausible and simpler explanation of PRIOT's collapse, and it is the main threat to this proposal. We test it with a two-by-two design that crosses wrap versus saturate with deterministic versus stochastic rounding. If stochastic rounding alone removes collapse while wrapping remains, we drop the wraparound explanation for PRIOT. The planted-instance results would still stand on their own as a calibration of on-chip learnability.

Why not just use saturating arithmetic or dynamic scaling and skip the theory? If our claim is right, saturation is the fix, and we would recommend it. What the theory adds is a predictor: $\gamma_{\text{eff}}$ can be estimated from activation histograms before training starts, which avoids trial-and-error. It also explains why the fix works, where PRIOT's edge-popup only sidesteps the problem. Dynamic scaling works too, but PRIOT argues it is too expensive on microcontrollers. Our memory measurements will check whether saturation reaches the same accuracy at lower cost.

Why not a plain gradient-variance or statistical-query analysis instead of cryptography? For gradient descent alone, that analysis is enough, and it is part of what Song et al. prove. The cryptographic reduction adds a further statement: no efficient on-chip algorithm escapes, lattice methods included, except in the exponentially-low-noise regime. Our LLL experiment checks that boundary directly. If integer LLL succeeds at dimensions well beyond what the $2^{-b}$ noise floor allows, the cryptographic framing loses its value for practice, and we will report that.

Decisive Checks

Three results would settle the question. The first is whether the measured gradient–truth cosine on planted instances tracks $e^{-2\pi^2\gamma^2}$ on the chip. The second is whether collapse onset in real models lines up with estimated $\gamma_{\text{eff}}$ near one under wrapping, and disappears under saturation with all else fixed. The third is whether the factorial underflow/overflow design attributes PRIOT's static-scale collapse mainly to overflow. If the first two hold but the third does not, we still have a validated hardness map for integer learning, but PRIOT's collapse would have a different explanation. If none hold, the analogy between register wraparound and lattice hardness is not useful for practice.