betaFeedback

WorksComputer Science

Semiprime Factorization with Discrete Diffusion and Beam Search: Scaling Laws

Abstract

We demonstrate that transformer architectures trained with discrete denoising diffusion and decoded via guided test-time beam search can learn to recover the prime factors of semiprime integers directly from data. Our approach establishes a new frontier for learning-based semiprime factorization, successfully factoring 68-bit integers-a substantial advance over the prior 56-bit state of the art. While computationally less efficient than classical factoring algorithms, our model requires no domain-specific number-theoretic priors and learns purely from training examples. In practice, the diffusion model acts as a generative prior, identifying promising factor candidates where exact verification or lattice-based post-processing can complete the factorization. Furthermore, we derive empirical scaling laws relating approximation quality to training data volume, model size, and test-time computation. In contrast to language, problem size is the key driver of scaling behavior. Achieving a fixed accuracy on a held-out test set requires compute that scales exponentially with bit length. Consequently, our findings pose no threat to security, as the projected compute cost required to factorize cryptographically relevant integers remains prohibitive.

Introduction

Integer factorization is one of the most important open problems in computer science, cryptography, and algorithmic number theory. Given a composite integer nn, the objective is to identify its prime factors such that n=p1⋅p2…pkn = p_1 \cdot p_2 \ldots p_k. In the context of public-key cryptography, such as the Rivest–Shamir–Adleman (RSA) cryptosystem ([40]), the modulus nn is restricted to be a balanced semiprime—the product of two distinct, large, and randomly chosen prime factors pp and qq of equal bit-length. The security guarantees of RSA rely on the assumption that the inverse operation of recovering pp and qq from nn is intractable without additional knowledge.

The integer factorization problem is known to belong to the complexity classes NP (Nondeterministic Polynomial time) and co-NP ([34]), as any proposed solution can be verified in polynomial time. However, it is widely believed to be neither NP-complete nor contained within the polynomial-time class P, even though there is not yet a definitive proof that integer factorization on classical hardware requires exponential or super-polynomial time. Consequently, this problem has attracted substantial research interest. A discovery of an efficient classical factorization method would undermine the security of modern digital infrastructure, making the integer factorization problem not only a question of broader theoretical interest, but one of deep practical significance.

There is no shortage of increasingly sophisticated heuristics that have been proposed over a long period of time. Early naive approaches, such as trial division and Pollard’s rho algorithm ([36]), require exponential time. Therefore, these methods are inapplicable at the cryptographically relevant scale. The current state-of-the-art classical algorithm is the General Number Field Sieve

Corresponding author(s): [email protected] (GNFS) ([4, 25, 27]), which was introduced as an evolution of the Quadratic Sieve (QS) ([37]). GNFS involves constructing two monic irreducible polynomials that share a common root modulo nn, and the search is performed across smooth numbers over complex algebraic number fields. The time complexity of GNFS is sub-exponential, namely

Ln[1/3,c]=exp⁡((c+o(1))(ln⁡n)1/3(ln⁡ln⁡n)2/3)L_n[1/3,c] = \exp\left((c+o(1))(\ln n)^{1/3}(\ln\ln n)^{2/3}\right)

where c=(64/9)1/3≈1.923c=(64/9)^{1/3}\approx1.923. While GNFS outperforms other methods, it remains super-polynomial in the bit-length of nn. Consequently, an 896-bit RSA cryptographic modulus currently remains the largest publicly acknowledged number to have been factored, which required substantial compute ((Weis, 2026)).

Subsequently, Peter Shor introduced a quantum algorithm capable of efficiently solving integer factorization presuming access to future fault-tolerant quantum hardware ([32, 41]). Shor’s algorithm leverages quantum superposition and the Quantum Fourier Transform (QFT) to solve the underlying period-finding problem, reducing the factorization time complexity to a polynomial bound of O((log⁡n)3)O((\log n)^3). This places integer factorization within the Bounded-error Quantum Polynomial time class (BQP) ((Aaronson, 2010)). While such quantum computers remain far in the future, this finding has catalyzed the search for post-quantum cryptography.

Unsurprisingly, semiprime factorization has also been approached with machine learning methods, and more recently deep learning ([3, 20, 33]). This has proven to be challenging, given the discrete combinatorial nature of the problem. Minor changes in activations may translate into severe violations of the imposed constraints. Recently, machine learning approaches have moved away from one-shot prediction to generative models. By formulating integer factorization as a search over a constrained discrete space, it is possible to achieve effective approximations at smaller scales. Specifically, the introduction of discrete denoising diffusion models ([2]) has shown promise.

Here, we contribute an empirical study of the scaling laws for semiprime factorization via discrete diffusion, both with and without subsequent test-time search and post-processing. These scaling laws enable us to characterize the extent to which machine learning can hope to tackle this problem, and extrapolate the findings to project how much time and compute would be required. We conclude that this does not present a risk to the current RSA protocols. Finally, at the 68-bit (k=34k=34) scale, we evaluate a 12B-parameter diffusion model paired with Coppersmith lattice post-processing across 15,523 held-out 68-bit semiprimes, recovering factors on a single test instance (1 candidate per instance) and analyzing the full MSB prefix-match distribution to show that the model captures coarse multiplicative magnitude bounds (≈3×\approx3\times lift over uniform random bit-guessing) while decaying to near-chance accuracy on deeper factor bits.

Related Work

Factorization

The most promising classical factorization algorithms utilize the principle of identifying smooth numbers, which are integers with bounded prime factors ([11]). The Quadratic Sieve (QS) ([37, 38]) aims to discover integers xx and yy such that x2≡y2(modn)x^2\equiv y^2\pmod n while ensuring x≠±y(modn)x\ne\pm y\pmod n, so that gcd⁡(x−y,n)\gcd(x-y,n) would then yield a non-trivial factor of nn.

The General Number Field Sieve (GNFS) ([4]) replaces the quadratic polynomials utilized in the QS with complex, higher-degree polynomials over algebraic number fields. The problem then becomes finding relations among elements within the ring of integers of a specific number field. During the sieve phase, many smaller integers are then factored to identify smooth relations, which can be achieved via Lenstra’s elliptic-curve factorization method [28].

Fermat’s factorization method presents an alternative approach, which is centered around the idea of representing an odd composite integer nn as the difference of two distinct squares: n=x2−y2=(x−y)(x+y)n = x^2 - y^2 = (x-y)(x+y). This is highly efficient if the prime factors pp and qq are close to the square root of nn, within the asymptotic bound of O(n1/4)O(n^{1/4}) [24]. In 1895, Lawrence extended Fermat’s algorithm for scenarios where p/qp/q is not close to 1 [17, 23]. It was shown that if one can deduce an approximation ratio u/v≈p/qu/v \approx p/q, one can then construct an augmented multiplier m=uvnm = uvn and use Fermat’s method to factor mm quickly. Recently, there has been interest in utilizing Lawrence’s extension to reframe the factorization problem into a binary classification or regression problem [3] for deep learning. In this framing, neural networks are trained to estimate the u/vu/v ratio. While this framing is an easier output specification for neural networks, the performance has not been promising.

Neural Arithmetic

Using neural networks for integer factorization has proven to be challenging, which is due to highly non-smooth optimization landscapes (Veličković et al., 2019) and the hard combinatorial nature of the problem. To overcome these obstacles, Vector Symbolic Architectures (VSA) [15] represent complex sub-symbolic data structures as high-dimensional hypervectors [21]. Fractional Power Encoding (FPE) [13, 35] is frequently used within the VSA framework, involving repeated exponentiation of a base hypervector and binding these to different scalar quantities.

Resonator networks [12, 39] maintain several independent groups of hypervector estimates, a^(t)\hat{a}(t) and b^(t)\hat{b}(t), in superposition, and update them iteratively based on the codebook matrices of possible factor representations. This dynamical system converges to a stable equilibrium state once the correct integer factors are isolated [22].

Diffusion Models

Denoising diffusion models were initially developed primarily for continuous domains [5, 10, 44] (Ho et al. 2020) and have seen extensive applications in image generation [10] (Ulhaq and Akhtar 2022). Gaussian noise is added in the forward pass and then iteratively removed in the learned neural inverse process. Discrete problems were initially approached mainly via standard autoregressive approaches, yet these approaches face difficulties in highly structured problems as an early error in the sequence would invalidate the rest of the solution. Discrete diffusion models help overcome this obstacle [2].

Discrete diffusion models are a good fit for highly structured problems as they couple parallel generation and iterative global refinement. These models are often defined with a Markovian transition matrix, rather than Gaussian noise [19]. Recent theoretical findings, tying the negative Evidence Lower Bound (ELBO) to the data entropy and the path Kullback-Leibler (KL) divergence, suggest that the diffusion loss naturally leads to the model correctly capturing the conditional expectation of the reverse denoising steps [2]. Discrete diffusion has shown great promise in structured domains like graph generation [7, 16, 29] (Vignac et al. 2022).

Recently, discrete diffusion has been experimented with for integer factorization [14]. The idea is to learn a mapping that iteratively corrects errors within partially correct solutions. The neural network is trained to output a clean sample x0=μ(xt,αˉt)x_0 = \mu(x_t, \bar{\alpha}_t), which is tightly conditioned on the product sequence. The approximation utilizes the full probabilistic information that is retained between steps:

θ~=[αtxt+(1−αt)/K]⊙[αˉt−1x0+(1−αˉt−1)/K]\tilde{\theta} = [\alpha_t x_t + (1-\alpha_t)/K] \odot[\bar{\alpha}_{t-1}x_0 + (1-\bar{\alpha}_{t-1})/K]

With this approach, the model was able to recover prime factors for numbers up to 56 bits in length [14]. This work also highlighted an inverse exponential relationship between training compute allocation and inference cost: At a specific projected success rate, higher investment in pre-training has been shown to lead to an exponential decrease in the number of discrete sampling steps required.

Method

Data Representation

We formulate the semiprime factorization problem, n=p×qn = p \times q, as a conditional sequence generation task. Given an integer nn, the objective is to generate the prime factors pp and qq. We represent all integers as binary strings. Assuming the prime factors pp and qq are bounded by 2k2^k, kk being the maximum number of factor bits, the binary representations of pp and qq are padded with leading zeros towards a fixed length kk. Similarly, nn occupies 2k2k bits. The employed ordering goes from the Most Significant Bit (MSB) to the Least Significant Bit (LSB).

The input to the model is obtained by concatenating the bit strings for nn, pp, qq, resulting in a total sequence length of 4k4k. The vocabulary consists of binary tokens {0,1}\{0, 1\}, alongside designated mask and padding tokens. During generation, the 2k2k bits corresponding to nn are unmasked and act as a fixed prefix. The model is tasked with inferring the subsequent 2k2k masked bits corresponding to pp and qq.

Data Generation

Training examples are generated on the fly using deterministic pseudorandom streams, while excluding pre-generated held-out evaluation sets to prevent pair-level train/test leakage. At initialization, we pre-generate fixed held-out validation and test splits of 1,024 semiprimes each (with a larger 100,000-example held-out test set generated specifically for the 68-bit factorization evaluation in § 4.5); during on-the-fly training example generation, any sampled pair whose product nn appears in the held-out evaluation splits is rejected and resampled. To sample a factor pair, we draw two random integers uniformly from [0,2k−1][0, 2^k - 1] (without forcing the leading kk-th bit to 1, so factors have bit-length at most kk and are zero-padded to length kk), advance each to the next prime via gmpy2.next_prime while rejecting primes ≥2k\ge2^k or equal factors (p=qp=q), sort them so that p>qp>q to break permutation symmetry, and set n=p⋅qn=p\cdot q.

Note that this holdout protocol enforces pair-level disjointness (Ntrain∩(Nval∪Ntest)=∅N_{\mathrm{train}} \cap(N_{\mathrm{val}} \cup N_{\mathrm{test}}) = \varnothing), ensuring the model never sees a held-out semiprime nn during training, while drawing training and test pairs from the same underlying pool of primes <2k<2^k (Ptrain=PtestP_{\mathrm{train}} = P_{\mathrm{test}}). Let π(n)\pi(n) denote the number of primes less than or equal to nn. For small bit-lengths (k≤19k \le19), a 100,000-step training run at batch size 214=16,3842^{14} = 16{,}384 (1.64×1091.64 \times10^9 examples) makes multiple passes over the (π(2k)2)\binom{\pi(2^k)}{2} non-held-out training pairs (e.g., ≈266\approx266 passes over ≈6.17×106\approx6.17 \times10^6 pairs at k=15k=15, and ≈77\approx77 passes over ≈2.14×107\approx2.14 \times10^7 pairs at k=16k = 16) and exposes each individual prime factor thousands of times (e.g., ≈75,500\approx75{,}500 occurrences per prime across π(219)=43,390\pi(2^{19}) = 43{,}390 primes at k=19k = 19). We discuss the implications of prime-vocabulary memorization versus pair-level generalization in § 5.

Model Architecture and Self-Conditioned Training

We approach semiprime factorization as a machine learning problem, framed as discrete diffusion over binary token sequences, utilising a bidirectional transformer (Vaswani et al., 2023) denoiser. During training, we use a noise schedule to corrupt the factor bits by replacing a dynamically sampled proportion η∈[0.02,1.0]\eta\in[0.02, 1.0] of their tokens with the mask token, and train the model to reconstruct the clean binary values across all 2k2k factor positions.

The spatial structure of the forward noising process is critical for learning multi-bit arithmetic dependencies, leading us to adopt contiguous blockwise masking rather than independent bitwise masking. For each training example we sample a noise level η\eta from the triangular density p(η)∝2ηp(\eta) \propto2\eta on [0.02,1.0][0.02, 1.0] (biasing towards higher noise levels while applying inverse-density importance weighting w=1/(2η)w = 1/(2\eta) so the diffusion objective remains unbiased; see Appendix § 6.§ 3) and mask a contiguous block of length M≈ηkM \approx\eta k in pp and in qq, while leaving the 2k2k prefix bits of nn unmasked. Masking contiguous spans forces the denoiser to resolve long-range carry propagation and global multiplicative constraints rather than relying on local bit interpolation.

To allow the discrete denoiser to refine its factor estimates across iterations without losing continuous uncertainty information when discretizing to hard tokens {0,1}\{0, 1\}, we incorporate a gated feed-forward self-conditioning module (Chen et al., [6]). Rather than feeding only discrete tokens at each step, the model maps its previous step’s vocabulary logits ℓ\ell into a continuous probability-weighted embedding S(ℓ)=d softmax⁡(ℓ)E^S(\ell) = \sqrt{d}\,\operatorname{softmax}(\ell)\hat{E} over the shared normalized token embedding table E^\hat{E}, transforms S(ℓ)S(\ell) through a zero-bias gated GeLU feed-forward network GSCG_{\mathrm{SC}}, and adds the result residually to the discrete canvas token embeddings CC prior to the first transformer layer (Appendix § 6.§ 2).

Training proceeds via a two-pass self-conditioned rollout on each minibatch (detailed in Appendix § 6.§ 3):

  1. Pass 1 (Unconditioned Proposal): The denoiser is evaluated on the block-masked canvas x~\tilde{x} with an all-zero self-conditioning tensor S(0)=0S^{(0)} = 0 (and stop_gradient) to produce first-pass logits ℓ(1)\ell^{(1)} and soft self-conditioning embeddings S(1)=stop_gradient⁡(S(ℓ(1)))S^{(1)} = \operatorname{stop\_gradient}(S(\ell^{(1)})).

  2. Concave Canvas Resampling and Pass 2 (Self-Conditioned Update): During iterative inference, the denoiser encounters canvases containing a mixture of masked spans and potentially erroneous discrete bits committed at earlier steps. To match this distribution during training, we sample discrete tokens x^(1)∼Categorical⁡(ℓ(1))\hat{x}^{(1)} \sim\operatorname{Categorical}(\ell^{(1)}) and overwrite each factor position of x~\tilde{x} (both masked and initially unmasked) independently with probability preplace(η)=4ρη(1−η)p_{\mathrm{replace}}(\eta) = 4\rho\eta(1-\eta) (ρ=0.5\rho= 0.5; Eq. (10)), forming a resampled canvas x~(2)\tilde{x}^{(2)}. On Pass 2, S(1)S^{(1)} is retained with probability pSC=0.99p_{\mathrm{SC}} = 0.99 and zeroed out with probability 1−pSC=0.011 - p_{\mathrm{SC}} = 0.01 so that a single parameter update per step trains the model predominantly in the self-conditioned regime while preserving calibration for the initial unconditioned step (S(0)=0S^{(0)} = 0). The training objective computes the importance-weighted cross-entropy between the Pass-2 predicted logits and the ground-truth binary tokens across all 2k2k factor positions of pp and qq (Eq. (11)), training the denoiser both to inpaint masked blocks and to correct erroneous discrete tokens committed on unmasked positions.

Test-Time Denoising and Guided Search

At inference time, we consider two distinct decoding procedures that trade off single-trajectory iterative refinement against structured tree search over partial factor prefixes (full mathematical details and a step-by-step worked walkthrough are provided in Appendix § 6.§ 4).

Non-Monotonic Ancestral Block-Diffusion Sampling

Standard ancestral sampling generates a single candidate factorization over TT discrete steps (t=0,…,T−1t = 0, \ldots, T - 1) following a linearly decaying noise schedule ηt+1=1−t+1T\eta_{t+1} = 1 - \frac{t+1}{T}, starting from a fully masked factor canvas (η0=1\eta_0 = 1) and S(0)=0\mathbf{S}^{(0)} = 0. Unlike absorptive discrete diffusion samplers that monotonically unmask and freeze one token at a time, our ancestral sampler performs non-monotonic predict-and-remask block refinement. At each step tt:

  1. The denoiser predicts clean binary logits ℓ(t)\boldsymbol{\ell}^{(t)} across all 2k2k factor bits simultaneously.

  2. The temperature-scaled binary probabilities are converted into the continuous self-conditioning embedding S(ℓ~(t))\mathbf{S}(\tilde{\boldsymbol{\ell}}^{(t)}) and passed to step t+1t + 1.

  3. A complete clean discrete guess x^0(t)∼Categorical⁡(ℓ~(t))\hat{\mathbf{x}}_0^{(t)} \sim\operatorname{Categorical}(\tilde{\boldsymbol{\ell}}^{(t)}) is sampled for all 2k2k bits of pp and qq, and two fresh, independently positioned contiguous blocks of width Mt=max⁡(⌊ηt+1k⌋,1)M_t = \max(\lfloor\eta_{t+1}k \rfloor, 1) are re-masked at newly sampled random offsets in pp and qq.

Because the masked window slides randomly across pp and qq at every step while continuous beliefs accumulate in S(ℓ~(t))\mathbf{S}(\tilde{\boldsymbol{\ell}}^{(t)}), running T≫2kT \gg2k steps (e.g., T=1,024T = 1{,}024 to 16,38416{,}384 for 2k=302k = 30) acts as annealed blocked-Gibbs refinement: bits outside the current mask that were guessed inconsistently at earlier steps can be re-masked and corrected on subsequent steps once neighbouring bits settle. No intermediate arithmetic check (whether p^⋅q^=n\hat{p} \cdot\hat{q} = n) is performed during the TT steps; verification occurs only once after step T−1T - 1.

Guided Beam Search with Inner Mini-Denoising and Oracle Self-Conditioning

While non-monotonic ancestral sampling can revise earlier bit guesses, it still evolves a single stochastic trajectory without explicit arithmetic verification until the final step. To prevent early bit errors from derailing generation and to exploit deterministic arithmetic constraints during decoding, we replace single-trajectory generation with a two-level guided search procedure over the binary factor tokens (Figure 1 and Figure 2). While we had initially explored Monte Carlo Tree Search (MCTS) with PUCT selection (Silver et al., [42]), we empirically found it to be less effective than maintaining a synchronized frontier via beam search (Lowerre, [30]; Lys et al., [31]) augmented with iterative inner mini-denoising.

The oracle self-conditioning iteration

Figure 1. The oracle self-conditioning iteration. During the inner mini-denoising loop, decided bits are mapped to one-hot target embeddings, while remaining masked positions receive soft logits. Both signals are merged to form the conditioning input for the subsequent denoising step.

Beam search expansion and feasibility pruning

Figure 2. Beam search expansion and feasibility pruning. At each step, valid states in the active beam are expanded. If a partial assignment violates the arithmetic constraints, it is pruned. The remaining feasible states are ranked, and the top BB paths are retained in the beam.

Our procedure couples an outer beam search that commits to discrete factor bits one by one with an inner mini-denoising loop that uses the diffusion model—via a mechanism we term oracle self-conditioning—to calibrate the branching probabilities at each search depth:

  • Outer Loop (MSB-to-LSB Beam Search): The outer search operates sequentially over the 2k2k factor positions (i=0,…,2k−1i = 0, \ldots, 2k - 1) by alternating between the MSBs of pp (even steps i=2ri = 2r, deciding bit prp_r) and the MSBs of qq (odd steps i=2r+1i = 2r + 1, deciding bit qrq_r). At outer depth ii, each hypothesis node in the active beam of width BB partitions the 2k2k factor positions into a subset of already committed (decided) MSB positions Di\mathcal{D}_i with fixed binary assignments xj∗∈{0,1}x_j^* \in\{0,1\} (j∈Dij \in\mathcal{D}_i) and a subset of remaining undecided masked positions Ui\mathcal{U}_i.

  • Inner Loop (Mini-Denoising with Oracle Self-Conditioning): Before expanding a node at outer depth ii to decide the next target MSB ti∈Uit_i \in\mathcal{U}_i, we run a short inner rollout of Tmini=5T_{\mathrm{mini}} = 5 recurrent denoising passes (m=0,…,Tmini−1m = 0, \ldots, T_{\mathrm{mini}} - 1) to let the diffusion model refine its beliefs over the undecided bits Ui\mathcal{U}_i conditioned on the committed prefix Di\mathcal{D}_i. In standard diffusion self-conditioning, the model feeds back its own soft predictions across all factor positions. In oracle self-conditioning (Figure 1), any bit j∈Dij \in\mathcal{D}_i already committed by the outer beam search is treated as ground-truth (“oracle”) knowledge during the inner rollout: decided positions j∈Dij \in\mathcal{D}_i are clamped in the self-conditioning input to their exact one-hot token embeddings d exj∗E^\sqrt{d}\,\mathbf{e}^{*}_{x_j}\hat{E} ([6]), while undecided masked positions u∈Uiu \in\mathcal{U}_i continue to refine soft probability-weighted embeddings d softmax⁡(ℓ~u(m))E^\sqrt{d}\,\operatorname{softmax}(\tilde{\ell}^{(m)}_u)\hat{E} across the TminiT_{\mathrm{mini}} inner steps.

Even though the output logits at already-decided positions j∈Dij \in\mathcal{D}_i are discarded after the inner loop (since only the logit at the next undecided MSB position tit_i is read to expand the tree), clamping j∈Dij \in\mathcal{D}_i to one-hot self-conditioning embeddings is essential because the self-conditioning vector is added to the input canvas embeddings before entering the bidirectional transformer. Through all-to-all self-attention across all layers, every undecided masked position u∈Uiu \in\mathcal{U}_i attends directly to the keys and values at decided positions j∈Dij \in\mathcal{D}_i. Injecting the one-hot embedding at j∈Dij \in\mathcal{D}_i both matches the Pass-2 training distribution on unmasked factor tokens and prevents internal conflict between the discrete canvas token xj∗x_j^{*} and the model’s unconditioned prior when exploring lower-probability branches of the beam (see Appendix § 6.§ 4).

Putting the outer and inner loops together, the guided search proceeds over outer steps i=0,…,2k−1i = 0, \ldots, 2k - 1 across a fixed-size frontier of BB hypothesis slots as follows (detailed in Appendix § 6.§ 4):

  1. Initialization: At outer step i=0i = 0, the frontier is initialized with BB slots where only slot 0 is marked active (score = 0.0, valid = True) with nn unmasked and all 2k2k bits of pp and qq set to the mask token (D0=∅\mathcal{D}_0 = \varnothing), while slots 1,…,B−11, \ldots, B - 1 are marked inactive (score = −∞-\infty, valid = False) to prevent duplicate clones at the root. Thus, the number of active hypotheses grows as 1→2→4→⋯→B1 \to2 \to4 \to\cdots\to B.

  1. Expansion via Inner Mini-Denoising (TminiT_{\mathrm{mini}} steps): At outer step ii, for each active candidate in the beam, we execute the Tmini=5T_{\mathrm{mini}} = 5 inner mini-denoising loop (m=0,…,Tmini−1m = 0, \ldots, T_{\mathrm{mini}} - 1). Unlike ancestral sampling, the discrete canvas x~\tilde{\mathbf{x}} is held completely fixed throughout the inner loop (decided positions j∈Dij \in\mathcal{D}_i retain their committed tokens xj∗∈{0,1}x_j^* \in\{0,1\}, undecided positions u∈Uiu \in\mathcal{U}_i remain masked, and no re-masking occurs); only the continuous self-conditioning tensor S(m)\mathbf{S}^{(m)} evolves from S(0)=0\mathbf{S}^{(0)} = \mathbf{0} by repeatedly merging the fixed one-hot oracle embeddings on Di\mathcal{D}_i with the refining soft predictions on Ui\mathcal{U}_i (Figure 1). After TminiT_{\mathrm{mini}} inner passes, the calibrated binary log-probabilities log⁡softmax⁡(ℓ(Tmini−1))\log\operatorname{softmax}(\ell^{(T_{\mathrm{mini}}-1)}) at the target MSB position tit_i are used to expand each active parent into two child branches (xti∗∈{0,1}x_{t_i}^* \in\{0,1\}), yielding up to 2B2B candidate states.

  1. Arithmetic Interval Feasibility Pruning: Because bit expansion proceeds from MSB to LSB, any partial assignment of prefixes p≤rp_{\le r} and q≤r′q_{\le r'} defines deterministic integer lower and upper bounds on each factor by setting all undecided lower bits in Ui+1\mathcal{U}_{i+1} to 0 (pmin⁡,qmin⁡p_{\min}, q_{\min}) or 1 (pmax⁡,qmax⁡p_{\max}, q_{\max}), respectively. Any child branch whose target semiprime falls outside the feasible product interval, i.e., n∉[pmin⁡qmin⁡,pmax⁡qmax⁡]n \notin[p_{\min}q_{\min}, p_{\max}q_{\max}], is immediately pruned by setting its score to −∞-\infty (Figure 2).

  1. Top-BB Selection: The remaining feasible children across all 2B2B candidates are ranked by their cumulative log-probabilities, and the top BB candidates are retained to form the active frontier for outer step i+1i + 1.

At the final depth i=2k−1i = 2k - 1 (U2k=∅\mathcal{U}_{2k} = \varnothing), pmin⁡=pmax⁡=p^p_{\min} = p_{\max} = \hat{p} and qmin⁡=qmax⁡=q^q_{\min} = q_{\max} = \hat{q}, so interval feasibility pruning reduces to exact multiplicative verification p^⋅q^=n\hat{p} \cdot\hat{q} = n. If all branches become infeasible prior to reaching the final depth, the search terminates early and returns the highest-log-probability partial MSB prefix for lattice-based post-processing.

Post-Processing

Optionally, we perform post-processing of the ML predictions via Coppersmith’s algorithm [9]. Based on the Lenstra–Lenstra–Lovász (LLL) lattice basis reduction algorithm [26], Coppersmith’s method can efficiently find small roots of modular polynomial equations. In the context of semiprime factoring, Coppersmith’s theorem states that if at least half of the MSBs of either prime factor are known, the remaining unknown bits can be recovered in polynomial time.

Consequently, for a factorization to be successful, it is not strictly necessary for either the model or the test-time search to generate a fully accurate factorization, if the generated candidate is approximately correct with a sufficient degree of accuracy. Coppersmith’s method can complement the ML approaches to deterministically resolve the remaining bits.

Test-Time Scaling Laws

Given that scaling test-time compute is now seen as one of the primary directions for enhancing complex problem-solving capabilities in AI models [8, 43], our focus here was to not only develop scaling laws for discrete diffusion models in pretraining when attempting to solve the integer factorization problem, but perhaps even more importantly, understand the test-time scaling properties and the conditions under which beam search can help improve the factorization success rate at different levels of complexity, and for different levels of quality of the underlying diffusion model. Test-time scaling is particularly appealing in domains where verification remains easier than generation, making integer factorization a good match for the overall approach.

Given that the optimal test time compute allocation strategy depends, in principle, on the difficulty distribution across samples, uniform allocation is highly ineffective when that distribution is fairly mixed. In our case, however, we presume that we are solving a problem at a particular (fixed) bit-length, and since the factors themselves are sampled to be large, the intrinsic factorization difficulty remains fairly uniform, at each specific bit-length. We are therefore not concerned with adaptively allocating compute per-example, rather aiming to understand how much test-time compute is required in expectation to successfully factor numbers at increasing bit-lengths, for varying quality of the underlying model, expressed in its denoising negative log-likelihood. We evaluate both axes of test-time compute scaling empirically: scaling the denoising step budget of single-trajectory ancestral diffusion on long-horizon checkpoints in § 4.3 (Table 1 and Figure 5–Figure 6), and scaling the beam search frontier width with oracle self-conditioning across pre-training stages in Appendix § 8.§ 5 (Figure 16–Figure 18).

Factor Bits102420484096819216384
1564.55%68.85%76.47%80.18%87.60%
201.86%3.42%4.59%6.35%8.30%
340.00%0.00%0.00%0.00%0.00%

Table 1. Single-trajectory ancestral diffusion exact factorization accuracy on the held-out test set (1,024 test instances per bit-length; no beam search or Coppersmith post-processing; 1 sample per test instance, τ=0.7\tau= 0.7) across denoising step budgets TT. Models: 325M trained for 100k steps at k=15k = 15, 325M trained for 348k steps at k=20k = 20, and 12B trained for 109k steps at k=34k = 34.

Log-linear plot of held-out solve rate versus denoising steps at inference, with slopes 0.3, 0.1, and 0.01 for training steps 30000, 100000, and 1000000

Figure 5. Log-linear scaling of single-trajectory ancestral solve rate with inference denoising steps TT across training horizons (30k, 100k, 1M steps) for a 325M model at k=15k = 15 trained with our initial pointwise-corruption baseline recipe (prior to contiguous blockwise masking and two-pass concave rollout used in Figure 6 and Table 1).

Scatter plot of held-out solve rate versus validation NLL for models with 100 and 500 denoising steps

Figure 6. Each point on the above plot is a model’s solve rate and validation loss at a particular point in training. The lower the validation loss, the higher the solve rate for any fixed number of denoising steps. This is true across various model sizes.

Test-Time Compute Scaling across Pre-Training Checkpoints

Figure 16. Test-Time Compute Scaling across Pre-Training Checkpoints. Exact factorization mean as a function of max search frontier size (B∈{32,128,512,1024}B \in\{32, 128, 512, 1024\}, labeled NN on the horizontal axis; log⁡2\log_{2} scale) across factor bit-lengths (k∈{16,20,24,28}k \in\{16, 20, 24, 28\}, greedy decoding temperature τ=0\tau= 0, labeled T=0T = 0). Subplots denote pre-training progression (fraction complete ∈{0.25,0.50,0.75,1.00}\in\{0.25, 0.50, 0.75, 1.00\}). Test-time search scaling yields monotonic performance gains, with larger frontier budgets partially compensating for earlier checkpoint maturity.

Compute Efficiency (Test-Time FLOPs vs. Performance)

Figure 18. Compute Efficiency (Test-Time FLOPs vs. Performance). Exact factorization mean as a function of total test-time inference FLOPs, faceted by factor bit-length (k∈{16,20,24,28}k \in\{16, 20, 24, 28\}) bits, greedy decoding τ=0\tau= 0. Colored curves represent pre-training checkpoint stages (0.25 to 1.00). Note independent xx- and yy-axes per subplot. Within each fixed problem hardness, expanding test-time search compute demonstrates predictable efficiency scaling.

Results

Here we present a variety of empirical scaling laws for semiprime factorization using discrete diffusion models along the dimensions of data, model size, problem size, and test time compute. Additional plots, including those measured in terms of train time compute, are shown in the appendix.

Data

In Figure 3, we plot validation loss against training steps (which is equivalent to data seen, since all models use the same batch size).1 We see that the loss curves exhibit power law behavior. Unlike natural language, since prime factorization is a noiseless problem, it is no surprise that the y-intercepts of the fitted power laws can and often are 0. Importantly, because validation NLL averages over all 2k2^k factor positions (both masked and unmasked) across noise levels η∼2η\eta\sim2\eta with importance weights wb=1/(2ηb)w_b = 1/(2\eta_b), a non-factoring local-arithmetic baseline—which simply copies visible unmasked bits and propagates revealed MSB/LSB prefixes and suffixes across mismatched mask offsets without global factoring (derived in Appendix § 6.§ 3.1)—already achieves an importance-weighted validation NLL ≈0.262\approx0.262. Consequently, validation NLL values above ≈0.262\approx0.262 reflect learning token copying and local carry/division consistency on partially unmasked canvases, whereas genuine η→1\eta\to1 factorization emerges only once validation NLL drops below ≈0.262\approx0.262.

Validation negative log-likelihood across training steps

Figure 3. Validation negative log-likelihood (NLL) across training steps ss (with power-law fits L(s)=As−α+L∞L(s) = As^{-\alpha} + L_{\infty}) for the 325M model across factor bit-lengths k∈{15,…,21}k \in\{15,\ldots,21\}.

Model Size

In Figure 4, we plot validation loss curves against train steps for three model sizes (325M, 1B, 2B) across a range of factor bits. The decrease in the final loss value with model size is a bit noisy: while 2B is always (tied) for the best, the relationship between 325M and 1B is inconsistent, where which one has the lowest loss changes across factor bits.

Validation NLL across training steps for three model sizes (325M, 1B, and 2B), faceted by factor bit-length

Figure 4. Validation NLL across training steps for three model sizes (325M, 1B, and 2B), faceted by factor bit-length k∈{15,…,21}k \in\{15,\ldots,21\}.

Inference-Time Scaling

Here, we analyze how the performance of standalone single-trajectory ancestral diffusion (§ 3.4.1; temperature τ=0.7\tau= 0.7, no beam search, oracle self-conditioning, or Coppersmith post-processing) scales with the number of inference-time denoising steps TT (beam search frontier scaling is analyzed separately in Appendix § 8.§ 5, Figure 16–Figure 18). As detailed in § 3.4.1 and Appendix § 6.§ 4.1, the ancestral sampler performs no intermediate arithmetic check (p^⋅q^=n\hat{p} \cdot\hat{q} = n) during the TT steps; instead, scaling T≫2kT \gg2k improves solve rate via non-monotonic blocked-Gibbs refinement as fresh contiguous blocks of width Mt=max⁡(⌊ηt+1k⌋,1)M_t = \max(\lfloor\eta_{t+1}k\rfloor, 1) are repeatedly re-masked and re-evaluated against the evolving soft self-conditioning state.

Table 1 reports single-trajectory exact factorization accuracy on the held-out test set (1,024 semiprimes) across T∈[1024,16384]T \in[1024, 16384] for three trained checkpoints: a 325M model trained for 100,000 steps at k=15k = 15, a 325M model trained for 347,800 steps at k=20k = 20, and a 12B-parameter model trained for 109,000 steps at k=34k = 34. Whenever a model factorizes a non-zero fraction of held-out semiprimes at T=1024T = 1024, accuracy improves roughly log-linearly with log⁡T\log T; conversely, models with zero accuracy at low budgets (k=34k = 34) show no exact-factorization gains up to T=16,384T = 16,384. For comparison at k=15k = 15, trial division over odd candidates up to 2152^{15} guarantees success in at most 214=16,3842^{14} = 16,384 divisions.

In Figure 5, we illustrate this log-linear relationship across training horizons (30k, 100k, and 1M steps) on an initial k=15k = 15 (325M) baseline trained with pointwise token corruption prior to introducing contiguous blockwise masking and two-pass concave rollout resampling; better-trained checkpoints exhibit steeper test-time scaling slopes. Figure 6 evaluates checkpoints trained with our final blockwise-masking and two-pass rollout recipe (reaching ≈0.75\approx0.75 accuracy at T=100T = 100 steps within 100k training steps for k=15k = 15) and demonstrates across model sizes and bit-lengths that single-trajectory solve rate at fixed T∈{100,500}T \in\{100, 500\} is tightly governed by validation NLL. Notably,

solve rate in Figure 6 remains identically zero for all checkpoints with validation NLL ≳0.262\gtrsim0.262 and rises sharply only after NLL penetrates below ≈0.262\approx0.262—matching the exact theoretical NLL floor of our non-factoring local-arithmetic baseline (Appendix § 6.§ 3.1).

Problem Size

Our prime factorization setup gives us another dimension for which to analyze scaling: problem size (factor bits). Despite favorable scaling laws for data and test-time compute, we encounter a hurdle with problem size. In Figure 7, we plot loss curves for Flash 325M trained on factor bits 15, 16, 17, 18. What we see is roughly a geometric relation between factor bits and a given loss value below the ≈0.262\approx0.262 non-factoring local-arithmetic threshold (Appendix § 6.§ 3.1); each increase in factor bit requires roughly a 2x2x increase in training steps to achieve a given loss value. This trend suggests that data requirements scale exponentially in factor bits, i.e. linearly in the size of the problem. If this trend holds, this suggests that our diffusion model is unable to exploit substructure from a sparse amount of data, and requires seeing a large fraction of semiprime examples in order to perform well. In essence, our modeling component scales similarly to brute force methods.

Loss curves for Flash 325M trained on factor bits 15, 16, 17, and 18

Figure 7. Loss curves for Flash 325M trained on factor bits 15, 16, 17, 18. We look at the final loss values of factor bits 16, 17, 18 and trace horizontal lines showcasing at what step loss curves corresponding to lower factor bits achieve those loss levels. Circled are approximate points along the loss curve for factor bit 15 where the horizontal lines meet it, corresponding to points in training where it achieves the final loss that the factor bits 16, 17, 18 problem achieves. Square boxes denote analogous approximate points of intersection among the other loss curves.

Evaluation at 68 Bits (k=34k = 34) with Coppersmith Post-Processing

To probe the upper boundary of our training recipe, we trained a 12B-parameter diffusion model at k=34k = 34 factor bits for 109K steps at batch size 214=16,3842^{14} = 16{,}384 (1.79×1091.79 \times10^9 training examples, a negligible fraction of the ≈2.9×1017\approx2.9 \times10^{17} distinct 34-bit-bounded semiprimes). As shown in Table 1, standalone ancestral sampling achieves 0% factorization at k=34k = 34 even with T=16,384T = 16{,}384 denoising steps. However, Coppersmith’s lattice-reduction method (§ 3.5) requires a candidate factor to match only the leading ⌊k/2⌋+1=18\lfloor k/2 \rfloor+ 1 = 18 MSBs to recover the remaining 16 bits in polynomial time.

For this 68-bit experiment, we evaluated across a 100,000-example held-out test split using single-trajectory ancestral diffusion (T=500T = 500 denoising steps, τ=0.7\tau= 0.7, without beam search), generating one candidate pair (p^,q^)(\hat{p}, \hat{q}) per test instance and running Coppersmith reduction (18-bit prefix) on p^\hat{p} and q^\hat{q} (2 factor candidates tested per instance). Because our data generator samples primes <234< 2^{34} without forcing the 34-th bit to 1 (§ 3), 25,228 of the 100,000 held-out instances have two full 34-bit prime factors (p,q∈[233,234)p, q \in[2^{33}, 2^{34})), and 15,523 instances are strict 68-bit semiprimes (n∈[267,268)n \in[2^{67}, 2^{68})).

Out of the 15,523 strictly 68-bit held-out semiprimes, Coppersmith post-processing succeeded on 1 instance (0.0064%; 1/25,228 = 0.0040% across all pairs with two 34-bit factors), factoring

182990651592147505079=15850613929×11544704351182990651592147505079 = 15850613929 \times11544704351

where q^\hat{q} matched the leading 19 ≥\geq 18 MSBs of q=11544704351q = 11544704351 (and p^\hat{p} matched 8 MSBs of pp).

To assess statistical significance against random prefix coincidence, Table 2 compares the model’s empirical MSB match distribution across all 15,523 full 68-bit instances against two non-factoring baselines: (A) naive independent uniform bit-guessing in [233,234)[2^{33}, 2^{34}), and (B) a zero-learning hyperbola magnitude prior. Because any valid ordered factor pair p≥qp \geq q of n=p⋅qn = p \cdot q with p,q<234p, q < 2^{34} must satisfy p∈[⌈n⌉,234−1]p \in[\lceil\sqrt{n}\rceil, 2^{34} - 1] and lie on the rectangular hyperbola q=n/pq = n/p, the hyperbola prior simply draws p^\hat{p} uniformly at random from the valid integer interval {⌈n⌉,…,234−1}\{\lceil\sqrt{n}\rceil, \ldots, 2^{34} - 1\} and sets q^=⌊n/p^⌋\hat{q} = \lfloor n/\hat{p}\rfloor by division. Across intermediate prefix lengths (m∈[4,16]m \in[4, 16]), the 12B denoiser consistently matches leading prefixes at ≈3×\approx3\times the rate of naive uniform bit-guessing (e.g., 189 vs. 60.6 expected matches at m≥10m \geq10, z>16z > 16). Comparing against the hyperbola prior reveals the source of this lift: roughly 2.5×\times arises purely from restricting (p^,q^)(\hat{p}, \hat{q}) to the product hyperbola p^⋅q^≈n\hat{p} \cdot\hat{q} \approx n with p^≥q^\hat{p} \geq\hat{q}, with a modest additional ≈1.25×\approx1.25\times concentration over uniform hyperbola sampling (189 vs. 151.8 at $m \geq 10). Beyond bit m=4m = 4, however, each additional bit halves the empirical survival rate (≈0.52×\approx0.52\times per bit), mirroring random guessing on deeper factor bits. Consequently, at the Coppersmith threshold m=18m = 18, a single observed hit across 15,523 single-sample trials (compared to 0.24 expected under naive uniform guessing and 0.62 under the hyperbola prior) reflects tail sampling from a magnitude-calibrated prior rather than reliable 68-bit algorithmic factorization—consistent with our exponential scaling law.

MSBs (mm)12B Count12B RateUniform PriorHyperbola Prior
≥2\geq215,48999.78%75.00% (11,642.3)100.00% (15,523.0)
≥4\geq47,95751.26%23.44% (3,638.2)47.84% (7,426.9)
≥6\geq62,52616.27%6.15% (955.0)14.74% (2,288.4)
≥8\geq87014.516%1.556% (241.6)3.924% (609.2)
≥10\geq101891.218%0.390% (60.6)0.978% (151.8)
≥12\geq12490.316%0.098% (15.2)0.238% (37.0)
≥14\geq14140.090%0.024% (3.8)0.059% (9.1)
≥16\geq1650.032%0.0061% (0.95)0.0142% (2.20)
≥18\geq1810.0064%0.0015% (0.24)0.0040% (0.62)
≥19\geq1910.0064%0.0008% (0.12)0.0020% (0.31)

Table 2. Empirical leading-MSB prefix match distribution P(Lmatch≥m)P(L_{\mathrm{match}} \geq m) for the 12B model at k=34k = 34 (1 ancestral sample (p^,q^)(\hat{p}, \hat{q}) per instance, T=500T = 500, across N=15,523N = 15{,}523 held-out 68-bit semiprimes with n≥267n \geq2^{67}), compared against (A) naive uniform random bit-guessing on 2 factor candidates with fixed leading bit 1 (1−(1−2−(m−1))2)(1 - (1 - 2^{-(m-1)})^2), and (B) a zero-learning hyperbola magnitude prior that samples a random point on the product hyperbola p^q^≈n\hat{p}\hat{q} \approx n with p^≥q^\hat{p} \geq\hat{q} by drawing p^\hat{p} uniformly from the valid integer interval {⌈n⌉,…,234−1}\{\lceil\sqrt{n}\rceil, \ldots, 2^{34} - 1\} and setting q^=⌊n/p^⌋\hat{q} = \lfloor n/\hat{p}\rfloor.

Conclusion

Through our experiments, we have identified several key insights. At small bit lengths (k≤20k \le20), our models are able to reach high semiprime factoring performance. Our training setup rules out direct memorization, leading us to conclude that the denoiser can learn to successfully solve the task given sufficient training data. Due to the overlap in the constituent prime factor pool that is used to derive semiprimes for training and testing, the model benefits from having encountered the same factors previously in different numbers. The size of this prime factor vocabulary scales as π(2k)≈2k/(kln⁡2)\pi(2^k) \approx2^k/(k \ln2). This scaling aligns with our empirical finding that achieving a target validation loss requires a multiplicative growth in training data and compute (≈2×\approx2\times) for each added factor bit. Our scaling results also indicate that the model fails to uncover any polynomial or sub-exponential factoring algorithm, scaling approximately as a kind of learned brute force search.

It is instructive to contrast this performance with the scaling dynamics arising in natural language modeling, where smooth power-law scaling and length generalization occur. This generalization stems from a rich, hierarchical, and locally constrained structure that the model is able to learn and exploit. In contrast, semiprime factorization is globally coupled and cryptographically pseudorandom; a single bit-flip in the semiprime number has discontinuous, chaotic effects on its factors. The lack of reusable local substructure makes it virtually impossible for a diffusion model to generalize from kk-bit instances to k+1k+1-bit instances without a prohibitive, exponential increase in data.

Finally, our 68-bit MSB distribution analysis reveals that while the denoiser reliably learns coarse multiplicative magnitude bounds (≈3×\approx3\times prefix-match lift over naive random bits), its accuracy on deeper bits decays at near-chance rates. We therefore conclude that direct bit-prediction ML methods pose no present or future threat to RSA cryptography.

Architectural, Training, and Test-Time Search Details

In this appendix, we detail the input representations, self-conditioning architecture, importance-weighted diffusion training objective, and test-time beam search with oracle self-conditioning used in our experiments. We are unable to provide full architectural details, since we used proprietary Flash models as our transformer-based diffusion model.

Canvas Representation

Each factorization instance consists of a 2k2k-bit semiprime n=p⋅qn = p \cdot q and its two kk-bit prime factors p≥qp \ge q, serialized into a single sequence (or canvas) of length L=4kL = 4k:

x=(x1,…,x2k⏟n (2k bits), x2k+1,…,x3k⏟p (k bits), x3k+1,…,x4k⏟q (k bits))∈VL,(1)\mathbf{x} = \left(\underbrace{x_1,\ldots,x_{2k}}_{n\ (2k\ \text{bits})},\ \underbrace{x_{2k+1},\ldots,x_{3k}}_{p\ (k\ \text{bits})},\ \underbrace{x_{3k+1},\ldots,x_{4k}}_{q\ (k\ \text{bits})}\right) \in\mathcal{V}^{L}, \tag*{(1)}

where V\mathcal{V} denotes the discrete token vocabulary containing binary bit tokens {0,1}\{0,1\}, the absorbing mask token, and the pad token (∣V∣=4|\mathcal{V}| = 4). Let Loff=2kL_{\mathrm{off}} = 2k denote the prefix offset corresponding to the conditioned semiprime nn.

Token Embedding Normalization. Let E∈R∣V∣×d\mathbf{E} \in\mathbb{R}^{|\mathcal{V}|\times d} denote the learnable token embedding table with model dimension dd. Each row of E\mathbf{E} is projected onto the unit Euclidean (ℓ2\ell_2) sphere (∥E^v∥2=1\|\hat{\mathbf{E}}_v\|_2 = 1, corresponding to root-mean-square 1/d1/\sqrt{d}):

E^v=Ev∑j=1dEv,j2+ϵ,ϵ=10−30.(2)\hat{\mathbf{E}}_v = \frac{\mathbf{E}_v}{\sqrt{\sum_{j=1}^{d} E_{v,j}^{2} + \epsilon}}, \qquad\epsilon= 10^{-30}. \tag*{(2)}

For a discrete noisy canvas x~∈VL\tilde{\mathbf{x}} \in\mathcal{V}^{L}, the raw token embeddings are scaled by d\sqrt{d} upon lookup so that each token embedding has Euclidean norm d\sqrt{d} (unit root-mean-square):

C=Htok(x~)=d O(x~)E^∈RL×d,(3)\mathbf{C} = \mathbf{H}_{\mathrm{tok}}(\tilde{\mathbf{x}}) = \sqrt{d}\,\mathbf{O}(\tilde{\mathbf{x}})\hat{\mathbf{E}} \in\mathbb{R}^{L\times d}, \tag*{(3)}

where O(x~)∈{0,1}L×∣V∣\mathbf{O}(\tilde{\mathbf{x}}) \in\{0,1\}^{L\times|\mathcal{V}|} is the one-hot encoding of x~\tilde{\mathbf{x}}.

Self-Conditioning Architecture

To allow the discrete diffusion denoiser to refine its factor estimates across iterations without losing continuous uncertainty information when discretizing to hard tokens, we incorporate a gated feed-forward self-conditioning module.

Soft-Logit Embedding. Given unnormalized vocabulary logits ℓ∈RL×∣V∣\ell\in\mathbb{R}^{L \times\lvert V \rvert} produced by a preceding denoising pass, we compute a continuous probability-weighted embedding over the shared normalized token embedding table E^\hat{\mathbf{E}}:

S(ℓ)=d softmax⁡(ℓ)E^∈RL×d.(4)\mathbf{S}(\ell) = \sqrt{d}\,\operatorname{softmax}(\ell)\hat{\mathbf{E}} \in\mathbb{R}^{L \times d}. \tag*{(4)}

Given that Htok\mathbf{H}_{\mathrm{tok}} and S\mathbf{S} project onto the exact same normalized basis d E^\sqrt{d}\,\hat{\mathbf{E}}, a degenerate (one-hot) probability distribution in Eq. (4) recovers the exact discrete token embedding in Htok\mathbf{H}_{\mathrm{tok}}.

Prefix Zeroing and Gated FFN Transformation. Because the first Loff=2kL_{\mathrm{off}} = 2k positions correspond to the known semiprime nn, the self-conditioning module first masks out the prefix positions:

S~i={0if 1≤i≤2k,Siif 2k<i≤4k.(5)\tilde{\mathbf{S}}_i = \begin{cases} 0 & \text{if } 1 \le i \le2k,\\ \mathbf{S}_i & \text{if } 2k < i \le4k. \end{cases} \tag*{(5)}

Rather than concatenating S~\tilde{\mathbf{S}} with the canvas representations along the channel dimension, S~\tilde{\mathbf{S}} is transformed by a dedicated pre-normalized gated GeLU feed-forward network (FFWSubBlock) with hidden expansion dimension dffw=4dd_{\mathrm{ffw}} = 4d and zero bias:

U=RMSNorm⁡γ(S~),(6)\mathbf{U} = \operatorname{RMSNorm}_{\gamma}(\tilde{\mathbf{S}}), \tag*{(6)}
GSC(S~)=(GeLU⁡(UWA)⊙(UWB))WC,(7)\mathbf{G}_{\mathrm{SC}}(\tilde{\mathbf{S}}) = \left(\operatorname{GeLU}(\mathbf{U}\mathbf{W}_{A}) \odot(\mathbf{U}\mathbf{W}_{B})\right)\mathbf{W}_{C}, \tag*{(7)}

where WA,WB∈Rd×4d\mathbf{W}_{A}, \mathbf{W}_{B} \in\mathbb{R}^{d \times4d} and WC∈R4d×d\mathbf{W}_{C} \in\mathbb{R}^{4d \times d} are learnable projection matrices and ⊙\odot denotes elementwise multiplication. Because all linear projections in Eq. (7) are bias-free and GeLU⁡(0)=0\operatorname{GeLU}(0) = 0, any zero vector in S~\tilde{\mathbf{S}} (such as the 2k2k-bit prefix nn, or the entire self-conditioning tensor on the first denoising step) maps identically to 0∈Rd\mathbf{0} \in\mathbb{R}^{d}.

Residual Combination and Output Normalization. The transformed self-conditioning signal GSC(S~)\mathbf{G}_{\mathrm{SC}}(\tilde{\mathbf{S}}) is combined with the pre-normalized canvas embeddings C\mathbf{C} from Eq. (3) via elementwise residual addition, followed by a scale-free RMSNorm layer before entering the NlayerN_{\mathrm{layer}}-block bidirectional transformer trunk:

Z(0)=RMSNorm⁡(C+GSC(S~)).(8)\mathbf{Z}^{(0)} = \operatorname{RMSNorm}(\mathbf{C} + \mathbf{G}_{\mathrm{SC}}(\tilde{\mathbf{S}})). \tag*{(8)}

After passing Z(0)\mathbf{Z}^{(0)} through the bidirectional transformer layers, the final hidden states Z(Nlayer)∈RL×d\mathbf{Z}^{(N_{\mathrm{layer}})} \in\mathbb{R}^{L \times d} are unembedded via transposed projection against E^T\hat{\mathbf{E}}^{\mathsf{T}} with tanh logit soft-capping (c=30.0c = 30.0) to yield the output logits. Note that the transformer denoiser takes no explicit scalar timestep or noise-level embedding ηt\eta_t; instead, it infers the current progress of decoding directly from the spatial pattern of mask tokens on x~\tilde{\mathbf{x}} and the sharpness of the continuous self-conditioning embeddings S~\tilde{\mathbf{S}}.

Two-Pass Training Rollout and Noise-Level Loss Weighting

Importance-Weighted Noise Sampling and Blockwise Masking. During training, each example b∈{1,…,Bbatch}b \in\{1,\ldots,B_{\mathrm{batch}}\} in a minibatch is assigned a noise proportion ηb∈[ηmin⁡,1]\eta_b \in[\eta_{\min},1] with ηmin⁡=0.02\eta_{\min} = 0.02. To reduce gradient variance without biasing the diffusion objective, we employ importance sampling with a triangular proposal distribution p(η)∝2ηp(\eta) \propto2\eta on [ηmin⁡,1][\eta_{\min}, 1]. Specifically, we draw ub∼U(ηmin⁡2,1)u_b \sim\mathcal{U}(\eta_{\min}^{2},1) and set ηb=ub\eta_b = \sqrt{u_b} via inverse-transform sampling, pairing each example with its inverse-density importance weight:

ηb=ub,ub∼U(ηmin⁡2,1),wb=12ηb.(9)\eta_b = \sqrt{u_b}, \qquad u_b \sim\mathcal{U}(\eta_{\min}^{2},1), \qquad w_b = \frac{1}{2\eta_b}. \tag*{(9)}

Given ηb\eta_b, the forward masking process leaves the semiprime prefix xb,1:2kx_{b,1:2k} intact and masks two independently positioned contiguous blocks of deterministic length Mb=max⁡(⌊ηbk⌋,1)M_b = \max(\lfloor\eta_b k\rfloor, 1) starting at uniformly sampled bit offsets sb,p,sb,q∼U{0,…,k−Mb}s_{b,p},s_{b,q} \sim\mathcal{U}\{0,\ldots,k-M_b\} within pp and qq, respectively, yielding the corrupted canvas x~b\tilde{x}_b.

Two-Pass Self-Conditioning Rollout with Concave Canvas Resampling. Standard self-conditioning [6] randomly chooses with 50% probability whether to run a single unconditioned pass (S(0)=0S^{(0)} = 0) or a two-pass self-conditioned rollout. In our pipeline, we instead execute a two-pass rollout on every training step so that Pass 2 can simultaneously train self-conditioning and expose the denoiser to partially resampled discrete canvases:

  1. Pass 1 (Unconditioned Proposal): With dropout disabled, the denoiser is evaluated on x~b\tilde{x}_b with an all-zero self-conditioning tensor S(0)=0S^{(0)} = 0, producing first-pass logits ℓb(1)\ell_b^{(1)}. No parameter gradients are backpropagated through Pass 1.

  2. Soft Self-Conditioning and Concave Canvas Resampling: We compute the soft self-conditioning embeddings Sb(1)=stop_gradient⁡(S(ℓb(1)))S_b^{(1)} = \operatorname{stop\_gradient}(S(\ell_b^{(1)})) via Eq. (4). In addition, during iterative test-time inference and beam search, the denoiser must operate on canvases containing a mixture of masked tokens and partially committed discrete predictions (some of which may be erroneous guesses from earlier steps). To simulate this regime during training, we sample discrete tokens x^b(1)∼Categorical⁡(ℓb(1))\hat{x}_b^{(1)} \sim\operatorname{Categorical}(\ell_b^{(1)}) and replace each factor position i>2ki > 2k of x~b\tilde{x}_b (across both masked positions and initially unmasked ground-truth factor positions) with x^b,i(1)\hat{x}_{b,i}^{(1)} independently with a concave noise-dependent probability:

preplace(ηb)=4ρηb(1−ηb),ρ=0.5,(10)p_{\mathrm{replace}}(\eta_b) = 4\rho\eta_b(1-\eta_b), \qquad\rho= 0.5, \tag*{(10)}

forming the resampled canvas x~b(2)\tilde{x}_b^{(2)}. Note that preplace(ηb)p_{\mathrm{replace}}(\eta_b) vanishes at ηb∈{0,1}\eta_b \in\{0,1\} and peaks at ρ=0.5\rho= 0.5 when ηb=0.5\eta_b = 0.5. Overwriting both masked and unmasked factor bits teaches Pass 2 not only to inpaint mask tokens using Sb(1)S_b^{(1)}, but also to detect and correct erroneous discrete bit commitments on the canvas.

  1. Pass 2 (Self-Conditioned Update with 1% Unconditioned Dropout): Because parameter gradients are computed exclusively on Pass 2, always passing Sb(1)S_b^{(1)} would leave the denoiser untrained for the initial inference step t=0t = 0, where no prior prediction exists (S(0)=0S^{(0)} = 0). Therefore, on Pass 2, Sb(1)S_b^{(1)} is retained with Bernoulli probability pSC=0.99p_{\mathrm{SC}} = 0.99 and zeroed out (Sb(1)←0S_b^{(1)} \leftarrow0) with probability 1−pSC=0.011-p_{\mathrm{SC}} = 0.01. The denoiser then predicts second-pass logits ℓb(2)\ell_b^{(2)} from (x~b(2),Sb(1))(\tilde{x}_b^{(2)}, S_b^{(1)}).

Importance-Weighted Cross-Entropy Loss. Only Pass 2 contributes to the parameter gradient. The batch loss is computed as the self-normalized importance-weighted cross-entropy:

L(θ)=∑b=1Bbatch∑i=2k+14kwb ℓCE ⁣(xb,i,ℓb,i(2)(θ))2k∑b=1Bbatchwb,wb=12ηb.(11)\mathcal{L}(\theta) = \frac{\sum_{b=1}^{B_{\mathrm{batch}}}\sum_{i=2k+1}^{4k} w_b\,\ell_{\mathrm{CE}}\!\left(x_{b,i},\ell_{b,i}^{(2)}(\theta)\right)} { 2k\sum_{b=1}^{B_{\mathrm{batch}}}w_b}, \qquad w_b = \frac{1}{2\eta_b}. \tag*{(11)}

Non-Factoring Local-Arithmetic Baseline

Because Eq. (11) and validation token accuracy are averaged across all 2k2k factor positions of pp and qq—including both masked and unmasked positions—at noise levels ηb∼p(η)=2η\eta_b \sim p(\eta) = 2\eta on [0.02,1][0.02, 1], a model with zero global factoring ability can still achieve a low validation NLL and high per-token accuracy. Specifically, consider an idealized non-factoring local-arithmetic baseline operating on a partially masked canvas (n,p~,q~)(n, \tilde{p}, \tilde{q}) that applies only three elementary local rules without attempting to factor nn:

  1. Copying visible unmasked factor bits (≈33.3%\approx33.3\% of all factor positions): At noise level η\eta, a contiguous block of width M=max⁡(⌊ηk⌋,1)M = \max(\lfloor\eta k \rfloor, 1) is masked in pp and in qq, leaving the remaining 1−M/k≈1−η1 - M/k \approx1 - \eta fraction of factor bits unmasked on x~b\tilde{x}_b. Under the triangular proposal p(η)=2ηp(\eta) = 2\eta on [0.02,1][0.02, 1], the expected masked fraction is

E[η]≈∫01η⋅(2η) dη=23,\mathbb{E}[\eta] \approx\int_0^1 \eta\cdot(2\eta)\,\mathrm{d}\eta= \frac{2}{3},

meaning 1−E[η]≈131 - \mathbb{E}[\eta] \approx\frac{1}{3} (33.3%33.3\%) of the 2k2k factor bits are already visible on the input canvas. Even a pure token-copying baseline that copies the visible 13\frac{1}{3} of bits (NLL =0= 0, Accuracy =1= 1) and predicts 50/50 coin flips (NLL =ln⁡2≈0.693= \ln2 \approx0.693, Accuracy =0.5= 0.5) on the masked 23\frac{2}{3} of bits already achieves unweighted NLL =23ln⁡2≈0.462= \frac{2}{3}\ln2 \approx0.462 and Accuracy =13(1)+23(0.5)=66.7%= \frac{1}{3}(1) + \frac{2}{3}(0.5) = 66.7\%.

  1. Odd parity on the two LSBs: Every prime >2> 2 is odd, so the least significant bits pk−1=1p_{k-1} = 1 and qk−1=1q_{k-1} = 1 are deterministically 1 even when covered by the mask.

  1. Cross-factor MSB division and LSB modular multiplication across mismatched mask offsets: Because the contiguous mask starting offsets sb,p,sb,q∼U{0,…,k−Mb}s_{b,p}, s_{b,q} \sim\mathcal{U}\{0, \ldots, k-M_b\} are drawn independently in pp and qq, the masked spans [sb,p,sb,p+Mb)[s_{b,p}, s_{b,p} + M_b) and [sb,q,sb,q+Mb)[s_{b,q}, s_{b,q} + M_b) rarely align:

    • LSB suffix propagation (p⋅q≡n(mod2r)p \cdot q \equiv n \pmod{2^r}): Whenever the mask in qq extends rr bits closer to the LSB than the mask in pp (or vice versa), the rr lowest bits of pp are unmasked while the corresponding rr lowest bits of qq are masked. Since odd primes are invertible modulo 2r2^r, schoolbook multiplication and carry propagation uniquely determine those rr masked LSBs of q≡n⋅p−1(mod2r)q \equiv n \cdot p^{-1} \pmod{2^r}.

    • MSB prefix propagation (q=n/pq = n/p): Symmetrically, whenever sb,p>sb,qs_{b,p} > s_{b,q}, the leading sb,ps_{b,p} MSBs of pp are visible while bits [sb,q,sb,p)[s_{b,q}, s_{b,p}) of qq are masked; long division of nn by the visible prefix of pp deterministically resolves the corresponding masked MSBs of qq (up to boundary carry).

For two independent uniform draws sb,p,sb,qs_{b,p}, s_{b,q} on [0,(1−η)k][0, (1-\eta)k], the expected offset mismatch E[∣sb,p−sb,q∣]\mathbb{E}[|s_{b,p} - s_{b,q}|] is 13(1−η)k\frac{1}{3}(1-\eta)k bits on the MSB side and 13(1−η)k\frac{1}{3}(1-\eta)k bits on the LSB side, allowing local cross-factor arithmetic to deterministically resolve an additional ≈13(1−E[η])≈11\approx\frac{1}{3}(1-\mathbb{E}[\eta]) \approx11–13%13\% of all factor positions. On all remaining positions where both pp and qq are simultaneously masked beyond local carry reach, the baseline predicts a 50/50 coin flip (NLL =ln⁡2= \ln2, Accuracy =0.5= 0.5).

Integrating this non-factoring predictor over ηb∼2η\eta_b \sim2\eta on [0.02,1][0.02, 1] (including the Pass-2 concave token replacement Preplace⁡(ηb)=2ηb(1−ηb)\operatorname{Preplace}(\eta_b) = 2\eta_b(1-\eta_b) of Eq. (10)) yields two exact reference benchmarks corresponding to the two validation weighting conventions used across our figures:

  • Importance-Weighted Validation (wb=12ηbw_b = \frac{1}{2\eta_b}, Main-Text Figure 3, Figure 4, Figure 6, and Figure 7): Multiplying each example by wb=12ηbw_b = \frac{1}{2\eta_b} cancels the 2η2\eta proposal density and heavily upweights low-noise examples (ηb→0.02\eta_b \to0.02, where nearly all factor bits are unmasked and locally recoverable), yielding:

NLLbaseline(weighted)≈0.262.(12)\mathrm{NLL}_{\mathrm{baseline}}^{(\mathrm{weighted})} \approx0.262. \tag*{(12)}

This explains the sharp phase transition in Figure 6: every checkpoint with weighted validation NLL ≥0.262\ge0.262 has 0.0% exact solve rate, and non-zero factorization emerges only once validation NLL penetrates below 0.262.

  • Unweighted Validation (wb=1w_b = 1, Appendix § 8 Figure 8–Figure 15): Evaluating over ηb∼2η\eta_b \sim2\eta on [0.02,1][0.02, 1] with unit weights wb=1w_b = 1 yields:

IsoFLOP smile curves for $k = 24$, demonstrating the trade-off between final validation NLL and final validation accuracy against model parameters for fixed compute budgets

Figure 8. IsoFLOP smile curves for k=24k = 24, demonstrating the trade-off between final validation NLL (left) and final validation accuracy (right) against model parameters for fixed compute budgets.

Validation NLL versus cumulative training tokens (linear scale) for the 325M parameter model

Figure 15. Validation NLL versus cumulative training tokens (linear scale) for the 325M parameter model.

NLLbaseline(unweighted)≈0.375,Accuracybaseline(unweighted)≈0.732  (73.2%).(13)\mathrm{NLL}_{\mathrm{baseline}}^{(\mathrm{unweighted})} \approx0.375,\qquad\mathrm{Accuracy}_{\mathrm{baseline}}^{(\mathrm{unweighted})} \approx0.732\ \ (73.2\%). \tag*{(13)}

This explains why models at large bit-lengths (k≥24k \ge24) in Figure 8–Figure 15 plateau at NLL ≈0.375\approx0.375–0.3850.385 and Accuracy ≈73.2%\approx73.2\%: achieving 73.2% validation bit accuracy reflects mastering token copying and local MSB/LSB carry propagation on partially unmasked canvases, while still guessing 50/50 on the unfactored core.

Test-Time Denoising, Beam Search, and Oracle Self-Conditioning

Here we provide a full specification of our two test-time decoding procedures: single-trajectory non-monotonic ancestral sampling and guided MSB-to-LSB beam search with oracle self-conditioning.

Non-Monotonic Ancestral Block-Diffusion Sampling

Given a TT-step inference budget (t=0,1,…,T−1t = 0, 1, \ldots, T - 1), ancestral sampling initializes the canvas x~(0)\tilde{\mathbf{x}}^{(0)} with the 2k2k bits of nn unmasked and all 2k2k factor bits of pp and qq set to the mask token (η0=1\eta_0 = 1), alongside an all-zero self-conditioning tensor S(0)=0\mathbf{S}^{(0)} = \mathbf{0}. At each step tt, with incoming noise level ηt=T−tT\eta_t = \frac{T-t}{T} and target next-step noise level ηt+1=1−t+1T=T−1−tT\eta_{t+1} = 1 - \frac{t+1}{T} = \frac{T-1-t}{T}, the sampler executes four operations:

  1. Denoising Forward Pass: The transformer denoiser evaluates (x~(t),S(t))(\tilde{\mathbf{x}}^{(t)}, \mathbf{S}^{(t)}) to produce vocabulary logits ℓ(t)∈R4k×∣V∣\ell^{(t)} \in\mathbb{R}^{4k \times|\mathcal{V}|}.

  1. Binary Logit Shaping and Temperature Scaling: To prevent the sampler from proposing non-binary tokens (mask or pad) at factor positions, we form shaped logits ℓ~(t)\tilde{\ell}^{(t)} by setting the logits of all non-binary vocabulary entries to −∞-\infty and scaling by sampling temperature τ=0.7\tau= 0.7:

ℓ~j,v(t)={ℓj,v(t)/τif v∈{0,1},−∞otherwise.(14)\tilde{\ell}^{(t)}_{j,v} = \begin{cases} \ell^{(t)}_{j,v}/\tau& \text{if } v \in\{0,1\},\\ -\infty& \text{otherwise}. \end{cases} \tag*{(14)}
  1. Soft Self-Conditioning Update: The continuous self-conditioning tensor for step t+1t+1 is computed from the shaped binary logits via Eq. (4): S(t+1)=S(ℓ~(t))=d softmax⁡(ℓ~(t))E^\mathbf{S}^{(t+1)} = \mathbf{S}(\tilde{\ell}^{(t)}) = \sqrt{d}\,\operatorname{softmax}(\tilde{\ell}^{(t)})\hat{\mathbf{E}}.

  1. Full Factor Sampling and Fresh Contiguous Block Re-Masking: We sample a complete clean discrete factor hypothesis across all 2k2k factor positions simultaneously: x^0,j(t)∼Categorical⁡(ℓ~j(t))\hat{x}^{(t)}_{0,j} \sim\operatorname{Categorical}(\tilde{\ell}^{(t)}_j) for j∈{2k+1,…,4k}j \in\{2k+1,\ldots,4k\} (keeping x^0,1:2k(t)=x1:2k\hat{x}^{(t)}_{0,1:2k} = x_{1:2k}). If t=T−1t = T - 1 (ηT=0\eta_T = 0), the sampler returns x^0(T−1)\hat{\mathbf{x}}^{(T-1)}_0 without re-masking. Otherwise (t<T−1t < T - 1), rather than keeping previously unmasked bits frozen, the sampler applies the forward contiguous block-masking kernel at target noise level ηt+1\eta_{t+1} to x^0(t)\hat{\mathbf{x}}^{(t)}_0. Specifically, at inference time we use deterministic floor rounding with a single-bit minimum floor:

Mt=max⁡(⌊ηt+1k⌋,1),(15)M_t = \max(\lfloor\eta_{t+1}k \rfloor, 1), \tag*{(15)}

draw two fresh, independent uniform block offsets st,p,st,q∼U{0,…,k−Mt}s_{t,p},s_{t,q} \sim\mathcal{U}\{0,\ldots,k-M_t\}, and replace the contiguous spans [2k+1+st,p, 2k+st,p+Mt][2k+1+s_{t,p},\,2k+s_{t,p}+M_t] in pp and [3k+1+st,q, 3k+st,q+Mt][3k+1+s_{t,q},\,3k+s_{t,q}+M_t] in qq of x^0(t)\hat{\mathbf{x}}^{(t)}_0 with the mask token to form x~(t+1)\tilde{\mathbf{x}}^{(t+1)}.

Why Scaling T≫2kT \gg2k Improves Accuracy Without Intermediate Verification. In standard absorptive discrete diffusion where one masked token is permanently unmasked per step, the process terminates after 2k2k steps unless an external verifier restarts failed trajectories. By contrast, in our non-monotonic predict-and-remask sampler, no arithmetic check p^⋅q^=n\hat{p} \cdot\hat{q} = n is ever performed during the TT steps. When T≫kT \gg k (e.g., T=16,384T = 16{,}384 for k=15k = 15), the deterministic block width MtM_t in Eq. (15) remains constant for ≈T/k\approx T/k consecutive steps before decrementing by 1. Across those T/kT/k steps, the masked window of width MtM_t slides to newly sampled random offsets st,p,st,qs_{t,p}, s_{t,q} at every step while the continuous embedding S(t+1)S^{(t+1)} carries forward the full probability distribution over {0,1}\{0,1\} at all 2k2k factor bits. Consequently, any factor bit that was guessed inconsistently at an earlier step is repeatedly re-masked and re-evaluated in the context of updated beliefs elsewhere on the canvas. In particular, during the final T/kT/k steps where 0<ηt+1<1/k0 < \eta_{t+1} < 1/k, Eq. (15) clamps Mt=1M_t = 1, so the sampler executes T/kT/k steps of single-bit random-scan blocked-Gibbs refinement over pp and qq before final readout at t=T−1t = T - 1.

Outer MSB-to-LSB Beam Search with Inner Mini-Denoising

While non-monotonic ancestral sampling refines a single trajectory, it can still be trapped in local modes when early high-order bit guesses are mutually inconsistent with nn. Guided beam search replaces single-trajectory sampling with a two-loop algorithm: an outer tree-search loop over i=0,1,…,2k−1i = 0,1,\ldots,2k-1 that permanently commits one factor bit per step from MSB to LSB, and an inner mini-denoising loop of Tmini=5T_{\mathrm{mini}} = 5 recurrent self-conditioning steps that estimates calibrated branching probabilities for the next undecided bit.

Alternating MSB-to-LSB Expansion Schedule and Frontier Initialization. Let p=(p0,p1,…,pk−1)p = (p_0,p_1,\ldots,p_{k-1}) and q=(q0,q1,…,qk−1)q = (q_0,q_1,\ldots,q_{k-1}) denote the kk bits of each factor ordered from MSB (r=0r = 0, weight 2k−12^{k-1}) to LSB (r=k−1r = k-1, weight 202^0), occupying canvas indices 2k+1+r2k + 1 + r and 3k+1+r3k + 1 + r, respectively. The outer loop alternates between factors at each depth i∈{0,…,2k−1}i \in\{0,\ldots,2k-1\}:

ti={2k+1+⌊i/2⌋if i is even (deciding MSB p⌊i/2⌋),3k+1+⌊i/2⌋if i is odd (deciding MSB q⌊i/2⌋).(16)t_i = \begin{cases} 2k + 1 + \lfloor i/2 \rfloor& \text{if } i \text{ is even (deciding MSB }p_{\lfloor i/2 \rfloor}\text{)},\\ 3k + 1 + \lfloor i/2 \rfloor& \text{if } i \text{ is odd (deciding MSB }q_{\lfloor i/2 \rfloor}\text{)}. \end{cases} \tag*{(16)}

After ii outer steps, every node in the beam shares the same set of decided canvas positions Di={t0,t1,…,ti−1}\mathcal{D}_i = \{t_0,t_1,\ldots,t_{i-1}\} (∣Di∣=i|\mathcal{D}_i| = i) and undecided masked positions Ui={2k+1,…,4k}∖Di\mathcal{U}_i = \{2k+1,\ldots,4k\} \setminus\mathcal{D}_i (∣Ui∣=2k−i|\mathcal{U}_i| = 2k-i).

To maintain fixed tensor shapes of batch size BB on accelerators without evaluating duplicate root nodes at early depths, the frontier at i=0i = 0 is initialized with BB slots, (x~[b],score[b],valid[b])(\tilde{x}^{[b]}, \mathrm{score}^{[b]}, \mathrm{valid}^{[b]}) for b∈{0,…,B−1}b \in\{0,\ldots,B-1\}, where every slot contains nn followed by 2k2k mask tokens, but only slot 0 is marked active:

score[0]=0.0,valid[0]=True,score[b]=−∞,valid[b]=False∀b∈{1,…,B−1}.(17)\mathrm{score}^{[0]} = 0.0,\quad\mathrm{valid}^{[0]} = \mathrm{True},\qquad \mathrm{score}^{[b]} = -\infty,\quad\mathrm{valid}^{[b]} = \mathrm{False}\quad\forall b \in\{1,\ldots,B-1\}. \tag*{(17)}

Because invalid slots carry score −∞-\infty, their children are automatically discarded during top-BB selection. Thus, at i=0i = 0 only slot 0 expands into 2 valid children (p0∈{0,1}p_0 \in\{0,1\}); at i=1i = 1 those ≤2\leq2 valid states expand into ≤4\leq4 valid children, and the active frontier grows as 1→2→4→⋯→B1 \rightarrow2 \rightarrow4 \rightarrow\cdots\rightarrow B.

Inner Mini-Denoising Loop (Tmini=5T_{\mathrm{mini}} = 5): Frozen Canvas, Recurrent Self-Conditioning. At outer step ii, before branching on position tit_i, we run an inner loop of Tmini=5T_{\mathrm{mini}} = 5 steps (m=0,1,…,Tmini−1m = 0,1,\ldots,T_{\mathrm{mini}}-1) on each beam slot's partial canvas x~\tilde{x}. In sharp contrast to ancestral sampling, there is no re-masking or token sampling inside the inner loop:

  • The discrete input canvas x~\tilde{x} remains completely frozen across all m∈{0,…,Tmini−1}m \in\{0,\ldots,T_{\mathrm{mini}}-1\}: positions j∈Dij \in\mathcal{D}_i hold their committed bits xj∗∈{0,1}x_j^* \in\{0,1\}, and positions u∈Uiu \in\mathcal{U}_i remain set to the mask token. Thus, the discrete fraction of masked factor tokens is constant at ηi=2k−i2k\eta_i = \frac{2^{k-i}}{2^k}.

  • At m=0m=0, the inner rollout initializes S(0)=0\mathbf{S}^{(0)} = 0 and evaluates the denoiser to obtain initial logits ℓ(0)\boldsymbol{\ell}^{(0)}.

  • For each subsequent inner step m∈{0,…,Tmini−2}m \in\{0,\ldots,T_{\mathrm{mini}}-2\}, the model constructs the oracle self-conditioning tensor Soracle,(m+1)∈R4k×d\mathbf{S}^{\mathrm{oracle},(m+1)} \in\mathbb{R}^{4k \times d} by clamping all search-decided positions j∈Dij \in\mathcal{D}_i to their exact one-hot token embeddings while feeding back the temperature-scaled soft binary predictions at undecided positions u∈Uiu \in\mathcal{U}_i:

Sjoracle,(m+1)={0if 1≤j≤2k(semiprime prefix n),d exj∗TE^if j∈Di(search-decided bits, one-hot),d softmax⁡(ℓ~j(m))E^if j∈Ui(undecided bits, soft logits).(18)\mathbf{S}^{\mathrm{oracle},(m+1)}_j = \begin{cases} 0 & \text{if } 1 \le j \le2k \quad\text{(semiprime prefix }n\text{)},\\ \sqrt{d}\,\mathbf{e}_{x_j^*}^{\mathsf{T}}\hat{\mathbf{E}} & \text{if } j \in\mathcal{D}_i \quad\text{(search-decided bits, one-hot)},\\ \sqrt{d}\,\operatorname{softmax}\left(\tilde{\boldsymbol{\ell}}_j^{(m)}\right)\hat{\mathbf{E}} & \text{if } j \in\mathcal{U}_i \quad\text{(undecided bits, soft logits)}. \end{cases} \tag*{(18)}
  • After TminiT_{\mathrm{mini}} forward passes, we read out the binary log-probabilities log⁡P(xti=v∣Di)=(log⁡softmax⁡(ℓti(Tmini−1)))v\log P(x_{t_i}=v \mid\mathcal{D}_i) = \left(\log\operatorname{softmax}\left(\boldsymbol{\ell}_{t_i}^{(T_{\mathrm{mini}}-1)}\right)\right)_v for v∈{0,1}v \in\{0,1\} solely at the next target MSB position tit_i.

Why Clamping Decided Positions in Oracle Self-Conditioning Matters. A natural question is why Eq. (18) must explicitly inject the non-zero one-hot embedding d exj∗TE^\sqrt{d}\,\mathbf{e}_{x_j^*}^{\mathsf{T}}\hat{\mathbf{E}} at already-decided positions j∈Dij \in\mathcal{D}_i, given that (i) the discrete canvas x~\tilde{x} already contains xj∗x_j^* at position jj, and (ii) the output logits at j∈Dij \in\mathcal{D}_i are discarded after the inner loop. The reason is that Soracle,(m)\mathbf{S}^{\mathrm{oracle},(m)} modifies the input to layer 0 of the bidirectional transformer via Zj(0)=RMSNorm⁡(Cj+GSC(Sjoracle,(m)))\mathbf{Z}_j^{(0)} = \operatorname{RMSNorm}(\mathbf{C}_j + \mathbf{G}_{\mathrm{SC}}(\mathbf{S}_j^{\mathrm{oracle},(m)})) (Eq. (8)). Because every transformer block applies bidirectional all-to-all self-attention across all 4k4k positions, every undecided masked position u∈Uiu \in\mathcal{U}_i attends directly to the keys and values produced at the decided positions j∈Dij \in\mathcal{D}_i:

  1. Matching the Pass-2 Training Distribution: During Pass 2 of training (Appendix § 6.§ 3), unmasked factor positions j∈{2k+1,…,4k}j \in\{2k+1,\ldots,4k\} carry both their discrete token embedding Cj=d exj∗TE^\mathbf{C}_j = \sqrt{d}\,\mathbf{e}_{x_j^*}^{\mathsf{T}}\hat{\mathbf{E}} and a sharp, near-one-hot self-conditioning vector GSC(Sj(1))≈GSC(d exj∗TE^)\mathbf{G}_{\mathrm{SC}}(\mathbf{S}_j^{(1)}) \approx\mathbf{G}_{\mathrm{SC}}(\sqrt{d}\,\mathbf{e}_{x_j^*}^{\mathsf{T}}\hat{\mathbf{E}}). If we instead passed Sj=0\mathbf{S}_j=0 at decided positions j∈Dij \in\mathcal{D}_i for m≥1m \ge1, the layer-0 representation at j∈Dij \in\mathcal{D}_i would remain RMSNorm⁡(Cj+0)\operatorname{RMSNorm}(\mathbf{C}_j+0) (a Pass-1 representation) while undecided positions u∈Uiu \in\mathcal{U}_i would carry Pass-2 representations RMSNorm⁡(Cmask+GSC(Su(m)))\operatorname{RMSNorm}(\mathbf{C}_{\mathrm{mask}}+\mathbf{G}_{\mathrm{SC}}(\mathbf{S}_u^{(m)})), creating a distribution mismatch across the attention context.

  1. Enforcing Branch Consistency on Lower-Probability Beams: When beam search explores a branch that committed to a lower-probability bit assignment xj∗x_j^* (e.g., P^(xj=0)=0.2\hat{P}(x_j=0)=0.2, so the branch committed to xj∗=0x_j^*=0 while the model’s unconditioned Pass-1 logit at position jj still favours 11 with probability $0.8), standard soft self-conditioning would feed a vector weighted 80% toward “1” into GSC(Sj)\mathbf{G}_{\mathrm{SC}}(\mathbf{S}_j), directly contradicting the discrete canvas token Cj\mathbf{C}_j (“0”). Clamping Sjoracle\mathbf{S}_j^{\mathrm{oracle}} to the exact one-hot embedding of xj∗x_j^* forces both the canvas pathway Cj\mathbf{C}_j and the self-conditioning pathway GSC(Sjoracle)\mathbf{G}_{\mathrm{SC}}(\mathbf{S}_j^{\mathrm{oracle}}) to agree unanimously on the branch commitment xj∗x_j^*.

Arithmetic Interval Feasibility Pruning. When each active beam hypothesis bb expands at position tit_i into two children c∈{2b,2b+1}c \in\{2b,2b+1\} assigning xti∗=0x_{t_i}^*=0 and xti∗=1x_{t_i}^*=1 with updated cumulative log-probability score⁡child=score⁡[b]+log⁡P(xti=xti∗∣Di)\operatorname{score}_{\mathrm{child}} = \operatorname{score}^{[b]} + \log P(x_{t_i}=x_{t_i}^* \mid\mathcal{D}_i), the committed MSB prefixes define closed integer intervals [pmin⁡,pmax⁡][p_{\min}, p_{\max}] and [qmin⁡,qmax⁡][q_{\min}, q_{\max}] for the two factors:

pmin⁡=∑r:2k+1+r∈Di+1x2k+1+r∗2k−1−r,pmax⁡=pmin⁡+∑r:2k+1+r∈Ui+12k−1−r.(19)p_{\min} = \sum_{r:2k+1+r\in\mathcal{D}_{i+1}} x^{*}_{2k+1+r}2^{k-1-r}, \qquad p_{\max} = p_{\min} + \sum_{r:2k+1+r\in\mathcal{U}_{i+1}} 2^{k-1-r}. \tag*{(19)}
qmin⁡=∑r:3k+1+r∈Di+1x3k+1+r∗2k−1−r,qmax⁡=qmin⁡+∑r:3k+1+r∈Ui+12k−1−r.(20)q_{\min} = \sum_{r:3k+1+r\in\mathcal{D}_{i+1}} x^{*}_{3k+1+r}2^{k-1-r}, \qquad q_{\max} = q_{\min} + \sum_{r:3k+1+r\in\mathcal{U}_{i+1}} 2^{k-1-r}. \tag*{(20)}

Because p,q≥0p,q \ge0, any completion of the undecided bits in Ui+1\mathcal{U}_{i+1} must yield a product in [pmin⁡qmin⁡,pmax⁡qmax⁡][p_{\min}q_{\min},p_{\max}q_{\max}]. Thus, a child hypothesis is arithmetically feasible if and only if

pmin⁡⋅qmin⁡≤n≤pmax⁡⋅qmax⁡.(21)p_{\min}\cdot q_{\min} \le n \le p_{\max}\cdot q_{\max}. \tag*{(21)}

Any child violating Eq. (21) is immediately pruned by setting score⁡child=−∞\operatorname{score}_{\mathrm{child}}=-\infty and marking valid⁡child=False\operatorname{valid}_{\mathrm{child}}=\mathrm{False} before selecting the top BB children for outer step i+1i+1.

Worked Example Walkthrough of Beam Search and Oracle Self-Conditioning

To make the interplay between the outer search loop, the Tmin⁡iT_{\min i}-step inner loop, oracle self-conditioning, and arithmetic interval pruning concrete, consider factoring the 8-bit semiprime n=143=13×11n=143=13\times11 with k=4k=4 factor bits (p=13=11012p=13=1101_2, q=11=10112q=11=1011_2, and n=100011112n=10001111_2), beam width B=2B=2, and Tmin⁡i=5T_{\min i}=5. The canvas has length L=4k=16L=4k=16:

x=(1,0,0,0,1,1,1,1∥p0,p1,p2,p3∥q0,q1,q2,q3),\mathbf{x}=(1,0,0,0,1,1,1,1\parallel p_0,p_1,p_2,p_3\parallel q_0,q_1,q_2,q_3),

n=143n=143 (indices 1...8)  pp (indices 9...12)  qq (indices 13...16)

where p0,q0p_0,q_0 have bit value 23=82^3=8, p1,q1p_1,q_1 have value 22=42^2=4, p2,q2p_2,q_2 have value 21=22^1=2, and p3,q3p_3,q_3 have value 20=12^0=1.

Initialization (i=0i=0). The frontier has B=2B=2 slots with D0=∅\mathcal{D}_0=\varnothing and all 8 factor bits masked (M):

  • Slot 0: x~[0]=[10001111∥M M M M∥M M M M]\tilde{\mathbf{x}}^{[0]}=[10001111\parallel\mathrm{M\,M\,M\,M}\parallel\mathrm{M\,M\,M\,M}], score⁡[0]=0.0\operatorname{score}^{[0]}=0.0, valid⁡[0]=True\operatorname{valid}^{[0]}=\mathrm{True}.

  • Slot 1: x~[1]=[10001111∥M M M M∥M M M M]\tilde{\mathbf{x}}^{[1]}=[10001111\parallel\mathrm{M\,M\,M\,M}\parallel\mathrm{M\,M\,M\,M}], score⁡[1]=−∞\operatorname{score}^{[1]}=-\infty, valid⁡[1]=False\operatorname{valid}^{[1]}=\mathrm{False}.

Outer Step i=0i=0 (Deciding MSB p0p_0 at Canvas Index t0=9t_0=9).

  1. Inner Mini-Denoising (m=0,…,4m=0,\ldots,4): Throughout all 5 inner passes, the discrete canvas x~[0]\tilde{\mathbf{x}}^{[0]} stays frozen with all 8 factor positions masked. At m=0m=0, S(0)=0\mathbf{S}^{(0)}=0, producing initial soft probabilities (say P^(0)=[0.75,0.52,0.40,0.90∥0.72,0.48,0.55,0.90]\hat{\mathbf{P}}^{(0)}=[0.75,0.52,0.40,0.90\parallel0.72,0.48,0.55,0.90]). Since D0=∅\mathcal{D}_0=\varnothing, for m=1,2,3,4m=1,2,3,4 the oracle self-conditioning tensor Soracle,(m)\mathbf{S}^{\mathrm{oracle},(m)} simply feeds back the evolving soft embeddings d softmax⁡(ℓ~(m−1))E^\sqrt{d}\,\operatorname{softmax}(\tilde{\boldsymbol{\ell}}^{(m-1)})\hat{\mathbf{E}} at all 8 masked factor positions, sharpening the marginal belief at p0p_0 to, say, P(4)(p0=1)=0.92P^{(4)}(p_0=1)=0.92 and P(4)(p0=0)=0.08P^{(4)}(p_0=0)=0.08.

  2. Branching and Feasibility Pruning: Expanding Slot 0 on p0∈{0,1}p_0\in\{0,1\} (while Slot 1’s children inherit score −∞-\infty) yields two active candidate children with D1={9}\mathcal{D}_1=\{9\}:

    • Child A (p0∗=0p_0^*=0): Canvas [10001111∥0 M M M∥M M M M][10001111\parallel0\,\mathrm{M\,M\,M}\parallel\mathrm{M\,M\,M\,M}], score log⁡(0.08)=−2.53\log(0.08)=-2.53. By Eqs. (19)–(20), p∈[00002,01112]=[0,7]p\in[0000_2,0111_2]=[0,7] and q∈[00002,11112]=[0,15]q\in[0000_2,1111_2]=[0,15], so the maximum possible product is pmax⁡qmax⁡=7×15=105<143p_{\max}q_{\max}=7\times15=105<143. Because 143∉[0,105]143\notin[0,105], Child A is pruned immediately (score ←−∞\leftarrow-\infty, valid ←False\leftarrow\mathrm{False}).

    • Child B (p0∗=1p_0^*=1): Canvas [10001111∥1 M M M∥M M M M][10001111\parallel1\,\mathrm{M\,M\,M}\parallel\mathrm{M\,M\,M\,M}], score log⁡(0.92)=−0.083\log(0.92)=-0.083. Here p∈[10002,11112]=[8,15]p\in[1000_2,1111_2]=[8,15] and q∈[0,15]q\in[0,15], giving feasible product interval [0,225]∋143[0,225]\ni143 (valid).

  1. Top-2 Selection: Slot 0 becomes [10001111 ∥ 1 M M M ∥ M M M M] (score = −0.083-0.083, valid = True), and Slot 1 remains invalid (score = −∞-\infty).

Outer Step i=1i = 1 (Deciding MSB q0q_0 at Canvas Index t1=13t_1 = 13).

  1. Inner Mini-Denoising with Oracle Self-Conditioning (m=0,…,4m = 0, \ldots, 4): Now D1={9}\mathcal{D}_1 = \{9\} (p0∗=1p_0^* = 1) and U1={10,11,12,13,14,15,16}\mathcal{U}_1 = \{10, 11, 12, 13, 14, 15, 16\}. On every inner step m≥1m \ge1, Eq. (18) clamps index 9 of Soracle,(m)\mathbf{S}^{\mathrm{oracle},(m)} to the exact one-hot embedding d eE^\sqrt{d}\,\mathbf{e}_{\hat{E}}, while indices 10…1610\ldots16 receive soft probability-weighted embeddings. After 5 inner passes, suppose P(4)(q0=1∣p0∗=1)=0.94P^{(4)}(q_0 = 1 \mid p_0^* = 1) = 0.94 and P(4)(q0=0∣p0∗=1)=0.06P^{(4)}(q_0 = 0 \mid p_0^* = 1) = 0.06.

  1. Branching and Feasibility Pruning: Expanding Slot 0 on q0∈{0,1}q_0 \in\{0,1\}:

  • Child A (p0∗=1,q0∗=0p_0^* = 1, q_0^* = 0): p∈[8,15]p \in[8,15] and q∈[00002,01112]=[0,7]q \in[0000_2,0111_2] = [0,7], so pmax⁡qmax⁡=15×7=105<143p_{\max}q_{\max} = 15 \times7 = 105 < 143 (pruned).

  • Child B (p0∗=1,q0∗=1p_0^* = 1, q_0^* = 1): p∈[8,15]p \in[8,15] and q∈[8,15]q \in[8,15], so [pmin⁡qmin⁡,pmax⁡qmax⁡]=[64,225]∋143[p_{\min}q_{\min},p_{\max}q_{\max}] = [64,225] \ni143 (valid, cumulative score −0.083+log⁡(0.94)=−0.145-0.083 + \log(0.94) = -0.145).

  1. Top-2 Selection: Slot 0 holds [10001111 ∥ 1 M M M ∥ 1 M M M] (score = −0.145-0.145, valid = True).

Outer Step i=2i = 2 (Deciding Second MSB p1p_1 at Canvas Index t2=10t_2 = 10).

  1. Inner Mini-Denoising (m=0,…,4m = 0, \ldots, 4): Now D2={9,13}\mathcal{D}_2 = \{9,13\} (p0∗=1,q0∗=1p_0^* = 1, q_0^* = 1) are both clamped to one-hot embeddings in Soracle,(m)\mathbf{S}^{\mathrm{oracle},(m)}, while the 6 undecided bits refine their soft embeddings. Suppose after m=4m = 4 the model predicts P(4)(p1=1∣p0∗=1,q0∗=1)=0.65P^{(4)}(p_1 = 1 \mid p_0^* = 1,q_0^* = 1) = 0.65 and P(4)(p1=0∣p0∗=1,q0∗=1)=0.35P^{(4)}(p_1 = 0 \mid p_0^* = 1,q_0^* = 1) = 0.35.

  1. Branching and Feasibility Pruning: Expanding Slot 0 on p1∈{0,1}p_1 \in\{0,1\}:

  • Child A (p0∗=1,p1∗=1,q0∗=1p_0^* = 1,p_1^* = 1,q_0^* = 1): p∈[11002,11112]=[12,15]p \in[1100_2,1111_2] = [12,15] and q∈[10002,11112]=[8,15]q \in[1000_2,1111_2] = [8,15], giving product interval [96,225]∋143[96,225] \ni143 (valid, score −0.145+log⁡(0.65)=−0.576-0.145 + \log(0.65) = -0.576).

  • Child B (p0∗=1,p1∗=0,q0∗=1p_0^* = 1,p_1^* = 0,q_0^* = 1): p∈[10002,10112]=[8,11]p \in[1000_2,1011_2] = [8,11] and q∈[8,15]q \in[8,15], giving product interval [64,165]∋143[64,165] \ni143 (also valid, score −0.145+log⁡(0.35)=−1.195-0.145 + \log(0.35) = -1.195).

  1. Top-2 Selection: Both children satisfy Eq. (21), so for the first time both slots of the B=2B = 2 beam become active: Slot 0 tracks the prefix (p0:1∗=112,q0∗=12)(p_{0:1}^* = 11_2,q_0^* = 1_2) and Slot 1 tracks the alternative prefix (p0:1∗=102,q0∗=12)(p_{0:1}^* = 10_2,q_0^* = 1_2). Notice how at i=3i = 3, when evaluating Slot 1 (where $p_1^* = 0 was chosen against the model’s 0.65 preference for p1=1p_1 = 1), clamping index 10 of Soracle,(m)\mathbf{S}^{\mathrm{oracle},(m)} to the one-hot embedding of “0” forces the inner mini-denoising loop to compute the distribution of q1q_1 conditioned on p∈[8,11]p \in[8,11] (which requires q1=1q_1 = 1 since $11 \times 11 = 121 < 143$), rather than leaking the model’s unconditioned preference for p1=1p_1 = 1.

Continuing through outer step i=7i = 7 (q3q_3), the interval bounds collapse to a single point pmin⁡=pmax⁡=p^p_{\min} = p_{\max} = \hat{p} and qmin⁡=qmax⁡=q^q_{\min} = q_{\max} = \hat{q}, where Eq. (21) verifies p^⋅q^=13×11=143\hat{p} \cdot\hat{q} = 13 \times11 = 143.

Supplementary Power-Law Results

Optimal Compute Allocation

To establish the optimal compute allocation in terms of model size and training tokens, we conducted an IsoFLOP analysis for the k=24k = 24 bit-length factorization task. Figure 8 shows the characteristic smile curves. The minima of these curves correspond to the compute-optimal model size for a given

FLOP budget. At these compute-optimal minima (≈3×108\approx3 \times10^{8} parameters), scaling the FLOP budget from 0.5×0.5\times to 4.0×4.0\times pushes validation NLL down from ≈0.365\approx0.365 to ≈0.324\approx0.324 (and validation accuracy up from ≈0.745\approx0.745 to ≈0.776\approx0.776), penetrating well below the unweighted non-factoring local-arithmetic baseline (NLL ≈0.375\approx0.375, Accuracy ≈0.732\approx0.732; see Appendix § 6.§ 3.1). Conversely, on the right-hand branch of the smile curves (∼1010\sim10^{10} parameters), over-allocating FLOPs to model parameters at the expense of training steps leaves the largest models token-starved near the NLL ≈0.375\approx0.375 / Accuracy ≈0.732\approx0.732 non-factoring baseline.

Impact of Factor Bit-Length

Note on the differences loss scale and step budget vs Figure 4: The main-text trajectories were trained for a fixed 100,000 steps with inverse-PDF noise-level importance weighting, whereas the Appendix sweeps use uniform example weighting across sampled noise levels and scale the training step budget as 2500⋅2(k−16)/42500 \cdot2^{(k-16)/4}.

Figure 9 illustrates the increasing difficulty of the integer factorization problem as the number of factor bits increases. The final validation NLL increases and the final validation accuracy drops when factoring larger numbers. Because validation NLL and accuracy in Figure 8–Figure 15 average over all 2k2k factor bits under η∼2η\eta\sim2\eta with unit weights wb=1w_b = 1 (Appendix § 6.§ 3.1), the plateau at NLL ≈0.38\approx0.38–0.390.39 and Accuracy ≈0.728\approx0.728–0.7340.734 for k≥24k \ge24 in Figure 9 corresponds directly to the non-factoring local-arithmetic baseline of Eq. (13) (NLL ≈0.375\approx0.375, Accuracy ≈0.732\approx0.732). At these larger bit-lengths and short step budgets (2500⋅2(k−16)/42500 \cdot2^{(k-16)/4} steps), the models learn token copying, odd-parity LSBs, and local multiplicative/divisive consistency across partially unmasked factor spans, but make negligible progress on global η→1\eta\to1 factorization; genuine factoring capability emerges only once validation NLL penetrates substantially below this 0.375 floor (as seen at k=16k = 16, where NLL reaches 0.360 and beam search solves ≈15.5%\approx15.5\% of test instances in Figure 16).

Figure 9. Difficulty scaling illustrating the degradation of final validation NLL (left) and final validation accuracy (right) as the number of factor bits increases, compared between the 325M and 2B models.

Here we present extended empirical results illustrating the model training dynamics and the power law fits, complementing the results in the main text.

Fitting Individual Trajectories

The faceted per-trajectory power-law fits for the 2B model are shown in Figure 10 and for the 325M model in Figure 11. The empirical validation NLL is fitted to the functional form L(D)=a+b⋅D−cL(D) = a + b \cdot D^{-c}, where DD represents the cumulative training tokens.

Faceted per-trajectory power-law fits for the 2B parameter model across factor bit-lengths

Figure 10. Faceted per-trajectory power-law fits for the 2B parameter model across factor bit-lengths k=16k = 16 to k=40k = 40. The fits closely track the empirical validation NLL with low mean absolute percentage error (MAPE).

Faceted per-trajectory power-law fits for the 325M parameter model across factor bit-lengths $k = 16$ to $k = 40$

Figure 11. Faceted per-trajectory power-law fits for the 325M parameter model across factor bit-lengths k=16k = 16 to k=40k = 40.

The theoretical fit closely matches the empirical data across all evaluated bit-lengths. This indicates that the power-law decay consistently holds at the individual trajectory level. Note that for k≥24k \ge24, the fitted asymptotes a∈[0.370,0.376]a \in[0.370, 0.376] (Figure 11) reflect rapid power-law convergence toward the ≈0.375\approx0.375 non-factoring local-arithmetic floor (Appendix § 6.§ 3.1) over the short sweep horizon, rather than convergence toward zero-loss factorization.

Training Dynamics

Figure 12 and Figure 13 show the log-log scaling trajectories of validation NLL versus cumulative training tokens for the 2B and 325M parameter models across factor bit-lengths k∈{16,…,40}k \in\{16, \ldots, 40\}. The validation NLL decay holds across different model scales, maintaining a linear trend in log-log space.

Figure 12. Validation NLL versus cumulative training tokens on a log-log scale for the 2B parameter model across factor bit-lengths k=16k = 16 to k=40k = 40.

Validation NLL versus training tokens for the 325M parameter model across various factor bit-lengths

Figure 13. Validation NLL versus training tokens on a log-log scale for the 325M parameter model across various factor bit-lengths.

Figure 14 and Figure 15 present the validation NLL against cumulative training tokens on a standard linear scale for the 2B and 325M models respectively. While these plots clearly show the rapid initial improvement and the long-tail convergence as training progresses, the underlying power-law relationships are heavily compressed. This visualizes why log-log representations are necessary to properly analyze the scaling behavior and extrapolate future performance.

Validation NLL versus cumulative training tokens (linear scale) for the 2B parameter model

Figure 14. Validation NLL versus cumulative training tokens (linear scale) for the 2B parameter model.

Beam Search Frontier Scaling Across Pre-Training Stages

Figure 16–Figure 18 evaluate beam search with oracle self-conditioning and MSB-to-LSB interval feasibility pruning (§ 3.4; Tmini=5T_{\mathrm{mini}} = 5 inner mini-denoising steps, greedy expansion, and frontier widths B∈{32,128,512,1024}B \in\{32, 128, 512, 1024\}) across k∈{16,20,24,28}k \in\{16, 20, 24, 28\} on 1,024 held-out test semiprimes per configuration. Unlike Table 1—which evaluates long-horizon checkpoints (100k–348k training steps) using single-trajectory ancestral sampling—Figure 16–Figure 18 evaluate intermediate and final checkpoints (completion fractions 0.25, 0.50, 0.75, 1.00) from the short-horizon 2B difficulty-scaling sweep of Appendix § 8.§ 2, where total training steps scale as 2500⋅2(k−16)/42500 \cdot2^{(k-16)/4} (i.e., only 2,500 steps at k=16k = 16 and 5,000 steps at k=20k = 20). Even on these lightly trained checkpoints (validation NLL ≈0.362\approx0.362 at k=16k = 16 and ≈0.375\approx0.375 at k=20k = 20), expanding the search frontier from B=32B = 32 to B=1024B = 1024 increases exact factorization accuracy from <1%< 1\% to ≈15.5%\approx15.5\% at k=16k = 16 and ≈1.5%\approx1.5\% at k=20k = 20, whereas checkpoints stuck on the non-factoring validation plateau (k=28k = 28) remain at 0% across all tested beam widths.

Pre-Training Stage Progression vs. Test-Time Search Budget

Figure 17. Pre-Training Stage Progression vs. Test-Time Search Budget. Exact factorization mean vs. pre-training completion fraction (0.25 to 1.00), faceted by search frontier size (B∈{32,128,512,1024})(B \in\{32, 128, 512, 1024\}), labeled NN; greedy decoding τ=0\tau= 0. Colored lines denote factor bit-length (k∈{16,20,24,28})(k \in\{16, 20, 24, 28\}). As pre-training matures, higher search budgets (B=1024)(B = 1024) unlock substantially steeper performance trajectories compared to constrained search (B=32)(B = 32).

References

  1. [2]J. Austin, D. D. Johnson, J. Ho, D. Tarlow, and R. Van Den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in neural information processing systems, 34:17981–17993, 2021.
  2. [3]S. Blake. Integer factorisation, Fermat & machine learning on a classical computer. arXiv preprint arXiv:2308.12290, 2023.arxiv.org/abs/2308.12290
  3. [4]J. P. Buhler, H. W. Lenstra Jr, and C. Pomerance. Factoring integers with the number field sieve. In The development of the number field sieve, pages 50–94. Springer, 2006.
  4. [5]H. Cao, C. Tan, Z. Gao, Y. Xu, G. Chen, P.-A. Heng, and S. Z. Li. A survey on generative diffusion models. IEEE transactions on knowledge and data engineering, 36(7):2814–2830, 2024.DOI
  5. [6]T. Chen, R. Zhang, and G. Hinton. Analog bits: Generating discrete data using diffusion models with self-conditioning, 2023a. URL https://arxiv.org/abs/2208.04202.
  6. [7]X. Chen, J. He, X. Han, and L.-P. Liu. Efficient and degree-guided graph generation via discrete diffusion modeling. arXiv preprint arXiv:2305.04111, 2023b.arxiv.org/abs/2305.04111
  7. [8]Y. Chen, X. Pan, Y. Li, B. Ding, and J. Zhou. Provable scaling laws for the test-time compute of large language models. Advances in Neural Information Processing Systems, 38:167074–167108, 2026.arxiv.org/abs/2411.19477
  8. [9]D. Coppersmith. Finding a small root of a univariate modular equation. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 155–165. Springer, 1996.DOI
  9. [10]F.-A. Croitoru, V. Hondru, R. T. Ionescu, and M. Shah. Diffusion models in vision: A survey. IEEE transactions on pattern analysis and machine intelligence, 45(9):10850–10869, 2023.DOI
  10. [11]J. D. Dixon. Asymptotically fast factorization of integers. Mathematics of computation, 36(153):255–260, 1981.DOI
  11. [12]E. P. Frady, S. J. Kent, B. A. Olshausen, and F. T. Sommer. Resonator networks, 1: An efficient solution for factoring high-dimensional, distributed representations of data structures. Neural computation, 32(12):2311–2331, 2020.DOI
  12. [13]E. P. Frady, D. Kleyko, C. J. Kymn, B. A. Olshausen, and F. T. Sommer. Computing on functions using randomized vector representations (in brief). In Proceedings of the 2022 Annual Neuro-Inspired Computational Elements Conference, pages 115–122, 2022.DOI
  13. [14]Freivalds, Kārlis and Ozoliņš, Emīls and Bārzd̅iņš, Guntis. Discrete denoising diffusion approach to integer factorization. In International Conference on Artificial Neural Networks, pages 123–134. Springer, 2023.arxiv.org/abs/2309.05295
  14. [15]R. W. Gayler. Vector symbolic architectures answer Jackendoff’s challenges for cognitive neuroscience. arXiv preprint cs/0412059, 2004.DOI
  15. [16]K. K. Haefeli, K. Martinkus, N. Perraudin, and R. Wattenhofer. Diffusion models for graphs benefit from discrete state spaces. arXiv preprint arXiv:2210.01549, 2022.arxiv.org/abs/2210.01549
  16. [17]M. Hittmeir. A time-space tradeoff for lehman’s deterministic integer factorization method. Mathematics of Computation, 90(330):1999–2010, 2021.DOI
  17. [19]E. Hoogeboom, D. Nielsen, P. Jaini, P. Forré, and M. Welling. Argmax flows and multinomial diffusion: Learning categorical distributions. Advances in neural information processing systems, 34:12454–12465, 2021.
  18. [20]B. Jansen and K. Nakayama. Neural networks following a binary approach applied to the integer prime-factorization problem. In Proceedings. IEEE International Joint Conference on Neural Networks, volume 4, pages 2577–2582. IEEE, 2005.
  19. [21]P. Kanerva. Hyperdimensional computing: An introduction to computing in distributed representation with high-dimensional random vectors. Cognitive computation, 1(2):139–159, 2009.
  20. [22]D. Kleyko, C. Bybee, C. J. Kymn, B. A. Olshausen, A. Khosrowshahi, D. E. Nikonov, F. T. Sommer, and E. P. Frady. Integer factorization with compositional distributed representations. In Proceedings of the 2022 Annual Neuro-Inspired Computational Elements Conference, pages 73–80, 2022.DOI
  21. [23]F. W. Lawrence. Factorisation of numbers. Messenger of Math, 24:100–109, 1895.
  22. [24]R. S. Lehman. Factoring large integers. Mathematics of Computation, 28(126):637–646, 1974.
  23. [25]A. K. Lenstra and H. W. Lenstra. The development of the number field sieve, volume 1554. Springer Science & Business Media, 1993.
  24. [26]A. K. Lenstra, H. W. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261:515––534, 1982.
  25. [27]A. K. Lenstra, H. W. Lenstra Jr, M. S. Manasse, and J. M. Pollard. The number field sieve. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 564–572, 1990.
  26. [28]H. W. Lenstra Jr. Factoring integers with elliptic curves. Annals of mathematics, pages 649–673, 1987.
  27. [29]S. Limnios, P. Selvaraj, M. Cucuringu, G. Maple, G. Reinert, and A. Elliott. Sagess: Sampling graph denoising diffusion model for scalable graph generation. arXiv preprint arXiv:2306.16827, 2023.arxiv.org/abs/2306.16827
  28. [30]B. T. Lowerre. The Harpy speech recognition system. Carnegie Mellon University, 1976.
  29. [31]J. Lys, V. Gripon, A. Marmoret, L. Mauch, F. Cardinaux, G. B. Hacene, and B. Pasdeloup. D5P4: Partition determinantal point process for diversity in parallel discrete diffusion decoding, 2026. URL https://arxiv.org/abs/2603.19146.
  30. [32]T. Monz, D. Nigg, E. A. Martinez, M. F. Brandl, P. Schindler, R. Rines, S. X. Wang, I. L. Chuang, and R. Blatt. Realization of a scalable Shor algorithm. Science, 351(6277):1068–1070, 2016.DOI
  31. [33]R. Nene and S. Uludag. Machine learning approach to integer prime factorisation. arXiv preprint arXiv:2202.02023, 2022.
  32. [34]C. H. Papadimitriou. Computational complexity. In Encyclopedia of computer science, pages 260–265. 2003.
  33. [35]T. A. Plate. Holographic reduced representations. IEEE Transactions on Neural networks, 6(3):623–641, 1995.
  34. [36]J. Pollard. A Monte Carlo method for factorization. BIT Numerical Mathematics, 15:331–334, 1975.DOI
  35. [37]C. Pomerance. The quadratic sieve factoring algorithm. In Advances in cryptology, pages 169–182. Springer Berlin/Heidelberg, 1985.
  36. [38]C. Pomerance. A tale of two sieves. Notices of the American Mathematical Society, 43(12):1473–1485, 1996.
  37. [39]A. Renner, L. Supic, A. Danielescu, G. Indiveri, B. A. Olshausen, Y. Sandamirskaya, F. T. Sommer, and E. P. Frady. Neuromorphic visual scene understanding with resonator networks. Nature Machine Intelligence, 6(6):641–652, 2024.DOI
  38. [40]R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126, 1978.
  39. [41]P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. arXiv preprint quant-ph/9508027, 1995.
  40. [42]D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, T. Lillicrap, K. Simonyan, and D. Hassabis. Mastering chess and shogi by self-play with a general reinforcement learning algorithm, 2017. URL https://arxiv.org/abs/1712.01815.
  41. [43]C. Snell, J. Lee, K. Xu, and A. Kumar. Scaling LLM test-time compute optimally can be more effective than scaling model parameters, 2024. URL https://arxiv.org/abs/2408.03314.
  42. [44]J. Sohl-Dickstein, E. Weiss, N. Maheswaranathan, and S. Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International conference on machine learning, pages 2256–2265. PMLR, 2015.

Paper details

vlnc:W_f7swfg85
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents