Learning Large-Scale Modular Addition with an Auxiliary Modulus

• URL: http://arxiv.org/abs/2605.07648v1
• Date: Fri, 08 May 2026 12:16:07 GMT
• Title: Learning Large-Scale Modular Addition with an Auxiliary Modulus
• Abstract summary: A recent study substantially scaled modular addition learning in both the number of summands and the modulus.<n>This study theoretically and empirically analyzes this side effect and proposes a co-shift-free method for modular addition.
• Score: 11.864560633772678
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning parity functions, more general modular addition, is a challenging machine learning task due to its input sensitivity. A recent study substantially scaled modular addition learning in both the number of summands and the modulus. Its key idea is to increase zeros in training sequences, reducing the effective number of summands and thus controlling training difficulty; however, this induces covariate shift between training and test input distributions. This study theoretically and empirically analyzes this side effect and proposes a covariate-shift-free method for modular addition. Specifically, we introduce an auxiliary modulus $Kq$ during training, which reduces wrap-around frequency and problem difficulty while preserving the same input distribution across training and testing. Experiments show strong scalability and sample efficiency: even for large input length $N$, large modulus $q$, and small datasets -- where the sparse method fails to learn -- our method achieves equal or better match accuracy and relaxed $τ$-accuracy. For example, at $N=64$ and $q=974269$, our method trained on 100K samples achieves $97.0\%$ $τ$-accuracy at $τ=0.05$, while the sparse method achieves only $9.5\%$ with the same data size and $93.9\%$ even when extended to 1M samples.

Related papers

• DecompRL: Solving Harder Problems by Learning Modular Code Generation [27.116622101805984]
  We introduce DecompRL, an RL algorithm that explicitly learns to decompose and implement hierarchical code structures.<n>On LiveCodeBench and CodeContests, DecompRL outperforms standard and diversity-optimized RL baselines beyond $105$ tokens per problem.
  arXiv  Detail & Related papers  (2026-07-02T16:25:10Z)
• Efficiently Learning Drifting Halfspaces with Massart Noise [50.4331323695175]
  We study the problem of learning a drifting concept in the presence of Massart noise.<n>In this framework, an online learner has access to a history of independent samples.<n>The goal is to output, in each round, a hypothesis with small prediction error.
  arXiv  Detail & Related papers  (2026-06-09T17:35:18Z)
• CarBoN: Calibrated Best-of-N Sampling Improves Test-time Reasoning [62.56541355300587]
  We introduce a general test-time calibration framework that adaptively modifies the model toward high-reward reasoning paths.<n>Within this framework, we propose CarBoN, a two-phase method that first explores the solution space and then learns a calibration of the logits.<n>Experiments on MATH-500 and AIME-2024 show that CarBoN improves efficiency, with up to $4times$ fewer rollouts to reach the same accuracy.
  arXiv  Detail & Related papers  (2025-10-17T14:04:37Z)
• MaskPro: Linear-Space Probabilistic Learning for Strict (N:M)-Sparsity on Large Language Models [53.36415620647177]
  Semi-structured sparsity offers a promising solution by strategically retaining $N$ elements out of every $M$ weights.<n>Existing (N:M)-compatible approaches typically fall into two categories: rule-based layerwise greedy search, which suffers from considerable errors, and gradient-driven learning, which incurs prohibitive training costs.<n>We propose a novel linear-space probabilistic framework named MaskPro, which aims to learn a prior categorical distribution for every $M$ consecutive weights and subsequently leverages this distribution to generate the (N:M)-sparsity throughout an $N$-way sampling
  arXiv  Detail & Related papers  (2025-06-15T15:02:59Z)
• ALLMod: Exploring $\underline{\mathbf{A}}$rea-Efficiency of $\underline{\mathbf{L}}$UT-based $\underline{\mathbf{L}}$arge Number $\underline{\mathbf{Mod}}$ular Reduction via Hybrid Workloads [18.634794494170617]
  High-bit-width operations are crucial for enhancing security.<n>They are computationally intensive due to the large number of modular operations required.<n>AllMod is a novel approach that improves the area efficiency of LUT-based large-number modular reduction.
  arXiv  Detail & Related papers  (2025-03-20T07:47:34Z)
• EMC$^2$: Efficient MCMC Negative Sampling for Contrastive Learning with Global Convergence [43.96096434967746]
  A key challenge in contrastive learning is to generate negative samples from a large sample set to contrast with positive samples. We propose an Efficient Markov Chain Monte Carlo negative sampling method for Contrastive learning (EMC$2$) We prove that EMC$2$ is the first algorithm that exhibits global convergence (to stationarity) regardless of the choice of batch size.
  arXiv  Detail & Related papers  (2024-04-16T13:53:58Z)
• Testable Learning with Distribution Shift [9.036777309376697]
  We define a new model called testable learning with distribution shift. We obtain provably efficient algorithms for certifying the performance of a classifier on a test distribution. We give several positive results for learning concept classes such as halfspaces, intersections of halfspaces, and decision trees.
  arXiv  Detail & Related papers  (2023-11-25T23:57:45Z)
• FABind: Fast and Accurate Protein-Ligand Binding [127.7790493202716]
  $mathbfFABind$ is an end-to-end model that combines pocket prediction and docking to achieve accurate and fast protein-ligand binding. Our proposed model demonstrates strong advantages in terms of effectiveness and efficiency compared to existing methods.
  arXiv  Detail & Related papers  (2023-10-10T16:39:47Z)
• A Finite Sample Complexity Bound for Distributionally Robust Q-learning [17.96094201655567]
  We consider a reinforcement learning setting in which the deployment environment is different from the training environment. Applying a robust Markov decision processes formulation, we extend the distributionally robust $Q$-learning framework studied in Liu et al. This is the first sample complexity result for the model-free robust RL problem.
  arXiv  Detail & Related papers  (2023-02-26T01:15:32Z)
• Blessing of Class Diversity in Pre-training [54.335530406959435]
  We prove that when the classes of the pre-training task are sufficiently diverse, pre-training can significantly improve the sample efficiency of downstream tasks. Our proof relies on a vector-form Rademacher complexity chain rule for composite function classes and a modified self-concordance condition.
  arXiv  Detail & Related papers  (2022-09-07T20:10:12Z)
• On the Modularity of Hypernetworks [103.1147622394852]
  We show that for a structured target function, the overall number of trainable parameters in a hypernetwork is smaller by orders of magnitude than the number of trainable parameters of a standard neural network and an embedding method.
  arXiv  Detail & Related papers  (2020-02-23T22:51:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.