Google DeepMind pushes ML-based semiprime factorization SOTA from 56 to 68 bits with discrete diffusion and beam search
IAmTimNguyen · x · 2026-11-11
A Google DeepMind paper by Brendan O'Donoghue, Timothy Nguyen, Demis Hassabis and others explores diffusion models for prime factorization. Transformer-based discrete denoising diffusion plus a novel guided test-time beam search reliably recovers prime factors of held-out semiprimes, pushing the ML-based SOTA from 56 to 68 bits — with no number-theoretic priors, learning purely from examples. Empirical scaling laws show problem size is the key bottleneck: unlike language, factorization lacks smooth inductive bias, and compute for fixed accuracy grows exponentially with bit length, suggesting a different approach is needed. The authors stress cryptographic integers remain far out of reach, so no security threat, and offer the work as a rigorous baseline for the community.
More from Research
- Geodesic's NovaAtom-Lite hits 79% on FoldBench antibody-antigen prediction, far above AlphaFold 3's 48% — QuanquanGu · 2026-11-11
- Research taste RLHF by top researchers won't generalize to automated AI scientists — herbiebradley · 2026-11-11
- FlashAttention co-creator Dan Fu on kernels, inference economics, and owning vs leasing GPUs — realDanFu · 2026-11-11
- OpenTac debuts at CoRL as researchers call tactile the missing half of robot data — anand_bhattad · 2026-11-11
- Geodesiclab scores big improvement on antibody structure prediction, the hardest part of the problem — QuanquanGu · 2026-11-11
- AI drug discovery hits its HBM moment as the bottleneck shifts to the wet lab — QuanquanGu · 2026-11-11