# Discovering Lattice Reduction Strategies via Self-Play

arXiv: https://arxiv.org/abs/2606.15301 · HTML: https://mlsanity.com/paper/2606.15301/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 55 references that are in the map.
- First posted on arXiv 13 Jun 2026.

## Builds on (most cited first, 21 of 21)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Ray: A Distributed Framework for Emerging AI Applications](https://mlsanity.com/paper/1712.05889/) (2017)
- [Mastering Atari Games with Limited Data](https://mlsanity.com/paper/2111.00210/) (2021)
- [Deep Hierarchical Planning from Pixels](https://mlsanity.com/paper/2206.04114/) (2022)
- [SALSA: Attacking Lattice Cryptography with Transformers](https://mlsanity.com/paper/2207.04785/) (2022)
- [SALSA PICANTE: a machine learning attack on LWE with binary secrets](https://mlsanity.com/paper/2303.04178/) (2023)
- [SALSA VERDE: a machine learning attack on Learning With Errors with sparse small secrets](https://mlsanity.com/paper/2306.11641/) (2023)
- [Salsa Fresca: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errors](https://mlsanity.com/paper/2402.01082/) (2024)
- [Spending Thinking Time Wisely: Accelerating MCTS with Virtual Expansions](https://mlsanity.com/paper/2210.12628/) (2022)
- [The cool and the cruel: separating hard parts of LWE secrets](https://mlsanity.com/paper/2403.10328/) (2024)
- [Predicting Future Actions of Reinforcement Learning Agents](https://mlsanity.com/paper/2410.22459/) (2024)
- [Planning and Learning Using Adaptive Entropy Tree Search](https://mlsanity.com/paper/2102.06808/) (2021)
- [Neural Lattice Reduction: A Self-Supervised Geometric Deep Learning Approach](https://mlsanity.com/paper/2311.08170/) (2023)
- [Hedging of Financial Derivative Contracts via Monte Carlo Tree Search](https://mlsanity.com/paper/2102.06274/) (2021)
- [An AlphaZero-Inspired Approach to Solving Search Problems](https://mlsanity.com/paper/2207.00919/) (2022)

## Abstract (arXiv)

The Lenstra-Lenstra-Lov'asz (LLL) algorithm is a seminal contribution to computer science used for lattice basis reduction, yet its polynomial-time outputs produce bases that are far from optimal as the dimension grows. We show that deep reinforcement learning can discover strictly superior, generalizable reduction strategies by interacting with the primitive action space of LLL. We formulate lattice reduction as a single-player Markov Decision Process (MDP) and train a deep residual network using an AlphaZero-style self-play pipeline augmented with adaptive-horizon MCTS (Monte Carlo Tree Search), which couples multi-step network predictions with an entropy-gated expansion mechanism. The resulting policy, DeltaStar, is trained exclusively on small 8-dimensional q-ary lattices and requires fewer primitive row operations than LLL. Crucially, it generalizes zero-shot to unseen moduli and higher dimensions up to n=32 without retraining.