mlsanityData to 14 Oct 2026

Discovering Lattice Reduction Strategies via Self-Play

arXiv 2606.15301 ↗First posted 13 Jun 2026cs.LG cs.AIcited by 0

Not on the map. Why?

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.

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

21 of 55 references.

References · 21

  1. 2017Attention Is All You Needcited by 60,361
  2. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  3. 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,353
  4. 2025AlphaEvolve: A coding agent for scientific and algorithmic discoverycited by 867
  5. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 623
  6. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 608
  7. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  8. 2017Ray: A Distributed Framework for Emerging AI Applicationscited by 527
  9. 2021Mastering Atari Games with Limited Datacited by 237
  10. 2022Deep Hierarchical Planning from Pixelscited by 101
  11. 2022SALSA: Attacking Lattice Cryptography with Transformerscited by 28
  12. 2023SALSA PICANTE: a machine learning attack on LWE with binary secretscited by 11
9 more
  1. 2023SALSA VERDE: a machine learning attack on Learning With Errors with sparse small secretscited by 8
  2. 2024Salsa Fresca: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errorscited by 7
  3. 2022Spending Thinking Time Wisely: Accelerating MCTS with Virtual Expansionscited by 4
  4. 2024The cool and the cruel: separating hard parts of LWE secretscited by 4
  5. 2024Predicting Future Actions of Reinforcement Learning Agentscited by 4
  6. 2021Planning and Learning Using Adaptive Entropy Tree Searchcited by 3
  7. 2023Neural Lattice Reduction: A Self-Supervised Geometric Deep Learning Approachcited by 3
  8. 2021Hedging of Financial Derivative Contracts via Monte Carlo Tree Searchcited by 2
  9. 2022An AlphaZero-Inspired Approach to Solving Search Problemscited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Learning Fast Monomial Orders for Gr"obner Basis Computations
  2. 2026Playing to Par: Reinforcement Learning for Provably Optimal Quadrilateral Block Decompositions
  3. 2026RLGT: A reinforcement learning framework for extremal graph theory
  4. 2026Self-Play Reinforcement Learning under Imperfect Information in Big 2
  5. 2026Improving and Accelerating Offline RL in Large Discrete Action Spaces with Structured Policy Initialization
  6. 2026Modularized Reinforcement Learning on LLMs: From MDP Creation to Exploration and Learning
  7. 2025Deep Reinforcement Learning for Dynamic Algorithm Configuration: A Case Study on Optimizing OneMax with the (1+(λ,λ))-GA
  8. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space