Discovering Lattice Reduction Strategies via Self-Play

# Discovering Lattice Reduction Strategies via Self-Play
Source: [https://arxiv.org/html/2606.15301](https://arxiv.org/html/2606.15301)
Mohamed Malhou FAIR, Meta Superintelligence Labs & Sorbonne Université CNRS, LIP6 Paris, France mmalhou@meta\.com &Ludovic Perret EPITA, EPITA Research Lab \(LRE\) Le Kremlin\-Bicêtre, France ludovic\.perret@epita\.fr&Kristin Lauter FAIR, Meta Superintelligence Labs klauter@meta\.com

###### Abstract

The Lenstra\-Lenstra\-Lovász \(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,Delta\-Star, is trained exclusively on small88\-dimensionalqq\-ary lattices and requires fewer primitive row operations than LLL\. Crucially, it generalizes zero\-shot to unseen moduli and higher dimensions up ton=32n=32without retraining\.

## 1Introduction

Lattice reduction is a central problem in computational mathematics, underpinning modern algorithmic number theory, optimization, and cryptography\. The security of modern lattice\-based cryptographic schemes—including those recently standardized by NIST for post\-quantum encryption\[[6](https://arxiv.org/html/2606.15301#bib.bib14)\]—rests on the presumed hardness of finding short non\-zero vectors in high\-dimensional lattices\[[1](https://arxiv.org/html/2606.15301#bib.bib16),[33](https://arxiv.org/html/2606.15301#bib.bib15),[39](https://arxiv.org/html/2606.15301#bib.bib11)\]\. Understanding the practical limits of lattice reduction algorithms is therefore critical for assessing the concrete security of these cryptosystems\[[15](https://arxiv.org/html/2606.15301#bib.bib10)\]\.

The workhorse of practical lattice reduction is the Lenstra\-Lenstra\-Lovász \(LLL\) algorithm\[[25](https://arxiv.org/html/2606.15301#bib.bib1)\]\. LLL is a polynomial\-time algorithm that produces a basis with guaranteed bounds on vector lengths\. It operates through two local, primitive actions:*size reduction*, which orthogonalizes a vector against its predecessors, and*adjacent swaps*, which reorder the basis\. The decision to swap is governed by the Lovász condition, a handcrafted heuristic that ensures a monotonic decrease in a specific potential function\.

While the Lovász condition is sufficient to guarantee polynomial runtime, it is not necessarily optimal for achieving the strongest reduction in practice\. The average\-case behavior of LLL is notoriously difficult to analyze and often yields better bases than the worst\-case bounds suggest\[[15](https://arxiv.org/html/2606.15301#bib.bib10)\]\. This gap raises a natural question:*Can we discover a better sequencing policy for LLL’s primitive operations that achieves stronger reduction than the classical algorithm?*

Recent work has shown that deep reinforcement learning \(RL\) combined with Monte Carlo Tree Search \(MCTS\)\[[9](https://arxiv.org/html/2606.15301#bib.bib17),[23](https://arxiv.org/html/2606.15301#bib.bib18)\]can discover algorithms that outperform human\-designed heuristics\. Starting from complex board games\[[47](https://arxiv.org/html/2606.15301#bib.bib21),[48](https://arxiv.org/html/2606.15301#bib.bib22),[46](https://arxiv.org/html/2606.15301#bib.bib23)\], this approach has been adapted to discover new algorithms for matrix multiplication\[[13](https://arxiv.org/html/2606.15301#bib.bib24)\], sorting\[[31](https://arxiv.org/html/2606.15301#bib.bib27)\], combinatorial problems\[[40](https://arxiv.org/html/2606.15301#bib.bib25)\], and formal mathematical reasoning\[[20](https://arxiv.org/html/2606.15301#bib.bib26)\]\. These results demonstrate that when a mathematical problem is framed as a single\-player game\[[43](https://arxiv.org/html/2606.15301#bib.bib20)\], an RL agent can explore the space of possible algorithms and potentially identify strategies superior to those designed by hand\.

In parallel, neural methods have been explored directly for lattice reduction\.\[[32](https://arxiv.org/html/2606.15301#bib.bib30)\]proposed a self\-supervised equivariant network that outputs factorized unimodular matrices, achieving performance comparable to LLL on benchmarks up ton=8n=8without explicit search\. However, scaling such end\-to\-end approaches to higher dimensions remains challenging\.

In this work, we apply the RL\+MCTS paradigm to the core mechanics of lattice reduction\. We formulate the lattice reduction process as a single\-player Markov Decision Process \(MDP\), restricting our agent to the exact action space of the classical LLL algorithm: cursor movement, size reduction, and adjacent swaps\. We train a deep residual network\[[19](https://arxiv.org/html/2606.15301#bib.bib48)\]using AlphaZero\-style\[[48](https://arxiv.org/html/2606.15301#bib.bib22)\]self\-play and a novel adaptive\-horizon MCTS to discover a data\-driven policy that replaces the rigid Lovász condition\.

Our contributions are:

1. 1\.An RL Formulation for Lattice Reduction\.We define an MDP for lattice reduction that matches the local action space of LLL, enabling a direct comparison of sequencing policies without confounding factors from richer action spaces \(such as exact Shortest\-Vector\-Problem \(SVP\) oracles\[[14](https://arxiv.org/html/2606.15301#bib.bib49)\]\)\.
2. 2\.Adaptive\-Horizon MCTS\.We introduce an entropy\-gated multi\-step expansion mechanism for MCTS that uses the Shannon entropy of predicted policies to allow the search tree to skip deterministic continuations and amortize inference calls\.
3. 3\.Beating LLL on its Own Terms\.Our learned policy achieves a significantly better root Hermite factor and orthogonality defect than the classical LLL algorithm across various dimensions, using only LLL’s primitive operations\.
4. 4\.Zero\-Shot Generalization\.By using aqq\-normalized observation tensor and Resnet architecture with adaptive pooling on output features, our model—trained exclusively on small88\-dimensionalq=251q=251\-ary lattices—generalizes zero\-shot to dimensions up ton=32n=32and unseenqq\(∼20−5000\\sim 20\-5000\)\.

## 2Background

This section reviews the mathematical foundations of lattice reduction, with a focus on the LLL algorithm and the gap between its convergence guarantee and the quality of reduction it achieves in practice\.

### 2\.1Euclidean Lattices and Basis Quality

Annn\-dimensional latticeℒ\\mathcal\{L\}is a discrete additive subgroup ofℝn\\mathbb\{R\}^\{n\}generated bynnlinearly independent basis vectors𝐁=\{𝐛1,…,𝐛n\}\\mathbf\{B\}=\\\{\\mathbf\{b\}\_\{1\},\\dots,\\mathbf\{b\}\_\{n\}\\\}:

ℒ​\(𝐁\)=\{∑i=1nzi​𝐛i:zi∈ℤ\}\.\\mathcal\{L\}\(\\mathbf\{B\}\)=\\left\\\{\\sum\_\{i=1\}^\{n\}z\_\{i\}\\mathbf\{b\}\_\{i\}:z\_\{i\}\\in\\mathbb\{Z\}\\right\\\}\.A lattice admits infinitely many bases:𝐁1\\mathbf\{B\}\_\{1\}and𝐁2\\mathbf\{B\}\_\{2\}generate the same lattice if and only if𝐁1=𝐁2​𝐔\\mathbf\{B\}\_\{1\}=\\mathbf\{B\}\_\{2\}\\mathbf\{U\}for some unimodular matrix𝐔∈ℤn×n\\mathbf\{U\}\\in\\mathbb\{Z\}^\{n\\times n\}\(det\(𝐔\)=±1\\det\(\\mathbf\{U\}\)=\\pm 1\)\. The volumedet\(ℒ\)=\|det\(𝐁\)\|\\det\(\\mathcal\{L\}\)=\|\\det\(\\mathbf\{B\}\)\|is a basis\-invariant quantity\.

qq\-ary Lattices\.An integer latticeℒ⊆ℤm\\mathcal\{L\}\\subseteq\\mathbb\{Z\}^\{m\}isqq\-ary for a modulusq≥2q\\geq 2ifq​ℤm⊆ℒ⊆ℤmq\\mathbb\{Z\}^\{m\}\\subseteq\\mathcal\{L\}\\subseteq\\mathbb\{Z\}^\{m\}, so that membership depends only on the coordinates moduloqq\. For a matrix𝐀∈ℤqn×m\\mathbf\{A\}\\in\\mathbb\{Z\}\_\{q\}^\{n\\times m\}, the primalqq\-ary lattice is defined as

Λq​\(𝐀\)=\{𝐲∈ℤm:∃𝐬∈ℤn,𝐬⋅𝐀≡𝐲\(modq\)\}\.\\Lambda\_\{q\}\(\\mathbf\{A\}\)=\\\{\\mathbf\{y\}\\in\\mathbb\{Z\}^\{m\}:\\exists\\mathbf\{s\}\\in\\mathbb\{Z\}^\{n\},\\ \\mathbf\{s\}\\cdot\\mathbf\{A\}\\equiv\\mathbf\{y\}\\pmod\{q\}\\\}\.\(1\)To apply lattice reduction algorithms such as LLL or BKZ, we require an explicit full\-rank basis forΛq​\(𝐀\)\\Lambda\_\{q\}\(\\mathbf\{A\}\)\. We embed the lattice intoℤn\+m\\mathbb\{Z\}^\{n\+m\}using the following row\-wise basis matrix:

𝐁=\[q​𝐈m𝟎𝐀𝐈n\]∈ℤ\(n\+m\)×\(n\+m\)\.\\mathbf\{B\}=\\begin\{bmatrix\}q\\mathbf\{I\}\_\{m\}&\\mathbf\{0\}\\\\ \\mathbf\{A\}&\\mathbf\{I\}\_\{n\}\\end\{bmatrix\}\\in\\mathbb\{Z\}^\{\(n\+m\)\\times\(n\+m\)\}\.\(2\)The rows of𝐁\\mathbf\{B\}generateΛq​\(𝐀\)\\Lambda\_\{q\}\(\\mathbf\{A\}\)embedded inℤn\+m\\mathbb\{Z\}^\{n\+m\}, and the construction ensuresq​ℤn\+m⊆ℒ​\(𝐁\)q\\mathbb\{Z\}^\{n\+m\}\\subseteq\\mathcal\{L\}\(\\mathbf\{B\}\)\.

Basis quality\.The standard metric for evaluating a reduced basis is the*root Hermite factor*:

δ0=\(‖𝐛1‖det\(ℒ\)1/n\)1/n,\\delta\_\{0\}=\\left\(\\frac\{\\\|\\mathbf\{b\}\_\{1\}\\\|\}\{\\det\(\\mathcal\{L\}\)^\{1/n\}\}\\right\)^\{1/n\},\(3\)which measures how short the first basis vector is relative to the lattice volume\. A smallerδ0\\delta\_\{0\}indicates a stronger reduction\. The global quality of the entire basis is captured by the*orthogonality defect*δ​\(𝐁\)=∏i‖𝐛i‖/det\(ℒ\)\\delta\(\\mathbf\{B\}\)=\\prod\_\{i\}\\\|\\mathbf\{b\}\_\{i\}\\\|/\\det\(\\mathcal\{L\}\), which equals11if and only if the basis is orthogonal \(Hadamard’s inequality\[[17](https://arxiv.org/html/2606.15301#bib.bib50)\]\)\. Additional background is provided in Appendix[A](https://arxiv.org/html/2606.15301#A1)\.

### 2\.2Gram\-Schmidt Orthogonalization

To analyze the geometry of a lattice basis, it is standard to compute its Gram\-Schmidt orthogonalization \(GSO\)\. The GSO vectors𝐁~=\{𝐛~1,…,𝐛~n\}\\widetilde\{\\mathbf\{B\}\}=\\\{\\widetilde\{\\mathbf\{b\}\}\_\{1\},\\dots,\\widetilde\{\\mathbf\{b\}\}\_\{n\}\\\}are defined iteratively:𝐛~1=𝐛1\\widetilde\{\\mathbf\{b\}\}\_\{1\}=\\mathbf\{b\}\_\{1\}, and forj\>1j\>1,

𝐛~j=𝐛j−∑i=1j−1μi,j​𝐛~i,whereμi,j=⟨𝐛j,𝐛~i⟩⟨𝐛~i,𝐛~i⟩\.\\widetilde\{\\mathbf\{b\}\}\_\{j\}=\\mathbf\{b\}\_\{j\}\-\\sum\_\{i=1\}^\{j\-1\}\\mu\_\{i,j\}\\widetilde\{\\mathbf\{b\}\}\_\{i\},\\quad\\text\{where\}\\quad\\mu\_\{i,j\}=\\frac\{\\langle\\mathbf\{b\}\_\{j\},\\widetilde\{\\mathbf\{b\}\}\_\{i\}\\rangle\}\{\\langle\\widetilde\{\\mathbf\{b\}\}\_\{i\},\\widetilde\{\\mathbf\{b\}\}\_\{i\}\\rangle\}\.\(4\)The GSO vectors are mutually orthogonal and span the same subspaces as the original basis vectors\.

### 2\.3The LLL Algorithm

The Lenstra\-Lenstra\-Lovász \(LLL\) algorithm\[[25](https://arxiv.org/html/2606.15301#bib.bib1)\]operates through two local, primitive actions:*size reduction*, which ensures the Gram\-Schmidt coefficients satisfy\|μi,j\|≤1/2\|\\mu\_\{i,j\}\|\\leq 1/2, and*adjacent swaps*, which reorder basis vectors\. The decision to swap is governed by the Lovász condition: for a parameterδ∈\(14,1\]\\delta\\in\(\\frac\{1\}\{4\},1\],

δ​‖𝐛~i‖2≤‖μi,i\+1​𝐛~i\+𝐛~i\+1‖2\.\\delta\\\|\\widetilde\{\\mathbf\{b\}\}\_\{i\}\\\|^\{2\}\\leq\\\|\\mu\_\{i,i\+1\}\\widetilde\{\\mathbf\{b\}\}\_\{i\}\+\\widetilde\{\\mathbf\{b\}\}\_\{i\+1\}\\\|^\{2\}\.\(5\)When this condition is violated, the algorithm swaps rowsiiandi\+1i\+1and decrements the cursor; otherwise it advances\. The full pseudocode is given in Algorithm[1](https://arxiv.org/html/2606.15301#alg1)\.

Algorithm 1The LLL Algorithm0:Basis

𝐁=\{𝐛1,…,𝐛n\}\\mathbf\{B\}=\\\{\\mathbf\{b\}\_\{1\},\\dots,\\mathbf\{b\}\_\{n\}\\\}, parameter

δ∈\(14,1\]\\delta\\in\(\\frac\{1\}\{4\},1\]
1:Compute GSO vectors

𝐁~\\widetilde\{\\mathbf\{B\}\}& coeffs

μi,j\\mu\_\{i,j\}; set

k←2k\\leftarrow 2
2:while

k≤nk\\leq ndo

3:for

j=k−1,…,1j=k\-1,\\dots,1do

4:if

\|μj,k\|\>1/2\|\\mu\_\{j,k\}\|\>1/2then

5:

𝐛k←𝐛k−⌊μj,k⌉𝐛j\\mathbf\{b\}\_\{k\}\\leftarrow\\mathbf\{b\}\_\{k\}\-\\lfloor\\mu\_\{j,k\}\\rceil\\mathbf\{b\}\_\{j\}; update

μi,k\\mu\_\{i,k\}\(

i≤ji\\leq j\) \{SizeReduce\}

6:endif

7:endfor

8:if

δ​‖𝐛~k−1‖2\>‖μk−1,k​𝐛~k−1\+𝐛~k‖2\\delta\\\|\\widetilde\{\\mathbf\{b\}\}\_\{k\-1\}\\\|^\{2\}\>\\\|\\mu\_\{k\-1,k\}\\widetilde\{\\mathbf\{b\}\}\_\{k\-1\}\+\\widetilde\{\\mathbf\{b\}\}\_\{k\}\\\|^\{2\}then

9:Swap

𝐛k,𝐛k−1\\mathbf\{b\}\_\{k\},\\mathbf\{b\}\_\{k\-1\}; update GSO & coeffs;

k←max⁡\(2,k−1\)k\\leftarrow\\max\(2,k\-1\)\{Swap\}

10:else

11:

k←k\+1k\\leftarrow k\+1
12:endif

13:endwhile

14:returnLLL\-reduced basis

𝐁\\mathbf\{B\}

Termination is guaranteed by a potential functionΦ​\(𝐁\)=∏i=1n‖𝐛~i‖n−i\+1\\Phi\(\\mathbf\{B\}\)=\\prod\_\{i=1\}^\{n\}\\\|\\widetilde\{\\mathbf\{b\}\}\_\{i\}\\\|^\{n\-i\+1\}that strictly decreases with every swap\. The Lovász condition is a sufficient condition under which a swap reducesΦ\\Phi, but it is not necessarily the optimal sequencing policy for achieving the strongest reduction\.

BKZ\.Schnorr’s Block Korkine\-Zolotarev \(BKZ\) algorithm\[[45](https://arxiv.org/html/2606.15301#bib.bib3),[44](https://arxiv.org/html/2606.15301#bib.bib2)\]generalizes the Lovász condition to blocks of sizeβ≥2\\beta\\geq 2, achieving smaller root Hermite factors at the cost of exponential complexity inβ\\beta\.

## 3Method forDelta\-Star

This section formalizes lattice reduction as a single\-player Markov Decision Process \(MDP\), introduces our adaptive horizon MCTS mechanism for efficient tree search, and describes the neural network architecture and distributed training pipeline\.

### 3\.1Lattice Reduction as a Single\-Player Game

We define thelatticeenvenvironment as an episodic, deterministic MDP where an agent sequentially manipulates a lattice basis to improve its quality\. The state representation mirrors the internal state of the classical LLL algorithm, tracking both the current basis and a row pointer \(cursor\)kk\.

Basis Sampling andqq\-ary Lattices\.We train onqq\-ary lattices, the primary family of lattices used in cryptography\.

For a base dimensionnn, the agent manipulates a2​n×2​n2n\\times 2nmatrix\. During training, entries of𝐀\\mathbf\{A\}are sampled uniformly from\[0,q−1\]\[0,q\-1\]\.

State Space𝒮\\mathcal\{S\}\.At timesteptt, the statests\_\{t\}consists of the basis matrix𝐁t\\mathbf\{B\}\_\{t\}, its Gram\-Schmidt orthogonalization𝐁t∗\\mathbf\{B\}^\{\*\}\_\{t\}\(see Appendix[A](https://arxiv.org/html/2606.15301#A1)\), the Gram\-Schmidt coefficients𝝁t\\boldsymbol\{\\mu\}\_\{t\}, the cursor positionkt∈\{0,…,2​n−1\}k\_\{t\}\\in\\\{0,\\dots,2n\-1\\\}, and the number of remaining steps\.

Action Space𝒜\\mathcal\{A\}\.The agent selects from four discrete actions, identical to the primitive operations available in LLL \([section˜2\.3](https://arxiv.org/html/2606.15301#S2.SS3)\):

1. 1\.MoveUp: Decrement the cursork←max⁡\(1,k−1\)k\\leftarrow\\max\(1,k\-1\)\.\# not allowed to be in​k=0\\;\\texttt\{\\\# not allowed to be in \}k=0
2. 2\.MoveDown: Increment the cursork←min⁡\(2​n−1,k\+1\)k\\leftarrow\\min\(2n\-1,k\+1\)\.
3. 3\.Swap: Exchange rows𝐛k\\mathbf\{b\}\_\{k\}and𝐛k−1\\mathbf\{b\}\_\{k\-1\}, then updatek←max⁡\(1,k−1\)k\\leftarrow\\max\(1,k\-1\)\.
4. 4\.SizeReduce: Subtract integer multiples of previous rows from𝐛k\\mathbf\{b\}\_\{k\}whenever\|μk,j\|\>1/2\|\\mu\_\{k,j\}\|\>1/2for allj<kj<k\.

Separating cursor movement from basis operations gives the agent complete flexibility to traverse the basis in any order, and limits the action set size to just44actions\.

Reward Function\.Because the initial values of quality metrics \([section˜2\.1](https://arxiv.org/html/2606.15301#S2.SS1)\) vary across random lattices, we define a normalized reward\. LetM​\(𝐁\)M\(\\mathbf\{B\}\)be a chosen metric \(orthogonality defectδ\\deltaor LLL potentialΦ\\Phi, see appendix[A](https://arxiv.org/html/2606.15301#A1)\)\. The step\-wise reward is the normalized relative reduction in the log\-metric:

rtM=log⁡M​\(𝐁t−1\)−log⁡M​\(𝐁t\)log⁡M​\(𝐁0\)\+ϵ,r\_\{t\}^\{M\}=\\frac\{\\log M\(\\mathbf\{B\}\_\{t\-1\}\)\-\\log M\(\\mathbf\{B\}\_\{t\}\)\}\{\\log M\(\\mathbf\{B\}\_\{0\}\)\+\\epsilon\},\(6\)whereϵ\\epsilonis a small constant for numerical stability\. We define a hybrid reward parameterized by a potential weightp∈\[0,1\]p\\in\[0,1\]:

rt=\(1−p\)⋅rtδ\+p⋅rtΦ,r\_\{t\}=\(1\-p\)\\cdot r\_\{t\}^\{\\delta\}\+p\\cdot r\_\{t\}^\{\\Phi\},\(7\)interpolating between the orthogonality defect and the potential function objectives\. The rational behind this is that the size reduction changes the former while the swap action modifies the latter\. At termination, a penalty proportional to the remaining defect is applied\.

Termination\.An episode terminates when the agent exhausts its maximum step horizonTmaxT\_\{\\max\}\.

Statests\_\{t\}Basis𝐁t\\mathbf\{B\}\_\{t\},pointerkkGSO:𝐁t∗,𝝁t\\mathbf\{B\}^\{\*\}\_\{t\},\\boldsymbol\{\\mu\}\_\{t\}, stepttAction Space𝒜\\mathcal\{A\}\(\|𝒜\|=4\|\\mathcal\{A\}\|=4\)MoveUpk←k−1k\\leftarrow k\{\-\}1MoveDownk←k\+1k\\leftarrow k\{\+\}1Swap𝐛k↔𝐛k−1\\mathbf\{b\}\_\{k\}\\leftrightarrow\\mathbf\{b\}\_\{k\-1\}SizeRedreduce𝐛k\\mathbf\{b\}\_\{k\}navigationlattice opsLegal: MoveUp ifk\>1k\>1, MoveDown ifk<2​n−1k<2n\{\-\}1, Swap ifk\>0k\>0, SizeRed alwaysRewardrt=log⁡M​\(𝐁t\)−log⁡M​\(𝐁t\+1\)log⁡M​\(𝐁0\)\+ϵr\_\{t\}=\\dfrac\{\\log M\(\\mathbf\{B\}\_\{t\}\)\-\\log M\(\\mathbf\{B\}\_\{t\+1\}\)\}\{\\log M\(\\mathbf\{B\}\_\{0\}\)\+\\epsilon\}Statest\+1s\_\{t\+1\}Updated𝐁t\+1\\mathbf\{B\}\_\{t\+1\},k′k^\{\\prime\},t\+1t\{\+\}1Observationot\+1o\_\{t\+1\}\(5×2​n×2​n\)\(5\\times 2n\\times 2n\)Ch\. 0–2:𝐁t\+1/q\\mathbf\{B\}\_\{t\+1\}/q,𝐁t\+1∗/q\\mathbf\{B\}^\{\*\}\_\{t\+1\}/q,𝝁t\+1\\boldsymbol\{\\mu\}\_\{t\+1\}Ch\. 3: Time Ch\. 4: PointerkkTerminal?t≥Tt\\geq TcontinueEnd episode

Figure 1:Thelatticeenvenvironment for LLL\-style basis reduction\. The agent controls a pointerkkindicating the current row, with four local actions\. This mimics the sequential structure of classical LLL and enables learning better reduction strategies\.
### 3\.2Adaptive Horizon Monte Carlo Tree Search

We employ an AlphaZero\-style self\-play scheme\[[48](https://arxiv.org/html/2606.15301#bib.bib22)\], combining a dual\-headed neural networkfθ​\(s\)=\(𝐩,v\)f\_\{\\theta\}\(s\)=\(\\mathbf\{p\},v\)with MCTS to iteratively improve the policy through self\-play\. The network is trained on data generated by MCTS to minimize the cross\-entropy between its predicted policy𝐩\\mathbf\{p\}and the MCTS visit\-count policy𝝅\\boldsymbol\{\\pi\}, and the mean squared error between its value estimatevvand the episode returnzz\.

Standard AlphaZero MCTS expands one node per simulation: a leaf is evaluated by the network, its children are created, and the value is backed up\. Our network produces multi\-step horizon predictions—a policy𝐩\(k\)\\mathbf\{p\}^\{\(k\)\}and valuev\(k\)v^\{\(k\)\}for each ofk=0,…,H−1k=0,\\dots,H\-1future steps—which allows expanding multiple nodes along the predicted greedy trajectory in a single evaluation, amortizing the inference computational cost\.

However, the greedy path through horizon predictions is only reliable when the policy is concentrated\. If a future step predicts a near\-uniform distribution over actions, committing to the argmax is arbitrary and the value estimate is unreliable\. We introduce an*adaptive horizon*mechanism that uses the entropy of each predicted policy to detect transitions from forced sequences to genuine decision points, stopping expansion at the first uncertain step\.

Entropy\-gated expansion\.Given logitslog⁡𝐩\(k\)\\log\\mathbf\{p\}^\{\(k\)\}, we compute its Shannon entropy: ℍ​\[𝐩\(k\)\]=−∑a∈𝒜​\(sk\)pa\(k\)​log2⁡pa\(k\)\.\\mathbb\{H\}\\bigl\[\\mathbf\{p\}^\{\(k\)\}\\bigr\]=\-\\sum\_\{a\\in\\mathcal\{A\}\(s\_\{k\}\)\}p\_\{a\}^\{\(k\)\}\\log\_\{2\}p\_\{a\}^\{\(k\)\}\.

An entropy of0indicates a single dominant action;ℍ=1\.0\\mathbb\{H\}=1\.0implies two roughly equal options\. When MCTS reaches a leaf, it queries the network once and expands nodes along the greedy path step\-by\-step\. At each stepkk, ifℍ​\[𝐩\(k\)\]≥τ\\mathbb\{H\}\[\\mathbf\{p\}^\{\(k\)\}\]\\geq\\taufor a predefined thresholdτ\\tau\(set to0\.60\.6see Appendix[C](https://arxiv.org/html/2606.15301#A3)\), the policy is too uncertain: the algorithm halts after expanding this node \(making its children available for future PUCT selection\)\. The valuev\(k\)v^\{\(k\)\}at the deepest expanded state is backpropagated through all newly created and visited horizon nodes and the selection path above them:vt=rt\+λ​vt\+1v\_\{t\}=r\_\{t\}\+\\lambda v\_\{t\+1\}

This mechanism produces trees whose shape adapts to the problem structure\. Forced sequences \(e\.g\., navigation towards a specific row whereℍ<<1\\mathbb\{H\}<<1\) are traversed automatically, preventing wasted simulations on deterministic continuations\. However the starting behavior in early training is standard AlphaZero’s MCTS\[[48](https://arxiv.org/html/2606.15301#bib.bib22)\]\. We provide a comprehensive ablation study of this mechanism’s scaling dynamics in Appendix[C](https://arxiv.org/html/2606.15301#A3)\.

1Selections0s\_\{0\}s1s\_\{1\}s2s\_\{2\}s3s\_\{3\}s4s\_\{4\}sLs\_\{L\}a∗=arg⁡maxa⁡\[Q​\(s,a\)\+cpuct​P​\(s,a\)​∑bNb1\+Na\]a^\{\*\}\\\!=\\\!\\arg\\max\_\{a\}\\\!\\Big\[\\,Q\(s,a\)\+c\_\{\\text\{puct\}\}\\,P\(s,a\)\\,\\frac\{\\sqrt\{\\sum\_\{b\}N\_\{b\}\}\}\{1\{\+\}N\_\{a\}\}\\,\\Big\]2Horizon Expand & Evaluatefθf\_\{\\theta\}single querysLs\_\{L\}\(𝝅\(k\),v\(k\)\)k=0H−1\\bigl\(\\boldsymbol\{\\pi\}^\{\(k\)\},\\,v^\{\(k\)\}\\bigr\)\_\{k=0\}^\{H\-1\}sLs\_\{L\}a∗a^\{\*\}ℍ\(0\)<τ\\mathbb\{H\}^\{\(0\)\}\\\!<\\\!\\taus1′s^\{\\prime\}\_\{1\}a∗a^\{\*\}ℍ\(1\)<τ\\mathbb\{H\}^\{\(1\)\}\\\!<\\\!\\taus2′s^\{\\prime\}\_\{2\}ℍ\(2\)≥τ\\mathbb\{H\}^\{\(2\)\}\\\!\\geq\\\!\\tauStopusev\(d−1\)v^\{\(d\{\-\}1\)\}k=0k\{=\}0k=1k\{=\}1k=2k\{=\}2d=3d\{=\}33Backups0s\_\{0\}s1s\_\{1\}sLs\_\{L\}s1′s^\{\\prime\}\_\{1\}s2′s^\{\\prime\}\_\{2\}G=v\(2\)G\\\!=\\\!v^\{\(2\)\}GGGGGGG←r\+γ​GG\\leftarrow r\+\\gamma GN\(s,a\)\+=1N\(s,a\)\\mathrel\{\+\}=1W\(s,a\)\+=GW\(s,a\)\\mathrel\{\+\}=GQ​\(s,a\)=WNQ\(s,a\)=\\frac\{W\}\{N\}selectionpathhorizonnodes4Plays0s\_\{0\}a1a\_\{1\}a2a\_\{2\}a3a\_\{3\}a4a\_\{4\}𝝅​\(a\)∝N​\(s0,a\)1/τplay\\boldsymbol\{\\pi\}\(a\)\\propto N\(s\_\{0\},a\)^\{1/\\tau\_\{\\text\{play\}\}\}s1s\_\{1\}Next stateRepeat1​–​31\{\\text\{\-\-\}\}3MMtimesContinue withs1s\_\{1\}as new root

Figure 2:Adaptive Horizon MCTS loop\.\(1\) Selection:Starting from the roots0s\_\{0\}, the tree is traversed by PUCT \(Predictive Upper Confidence Bound for Trees\[[41](https://arxiv.org/html/2606.15301#bib.bib61),[47](https://arxiv.org/html/2606.15301#bib.bib21)\]\) to reach a leafsLs\_\{L\}\.\(2\) Horizon Expand & Evaluate:The networkfθf\_\{\\theta\}is queried once, producing horizon predictions\(𝝅\(k\),v\(k\)\)k=0H−1\(\\boldsymbol\{\\pi\}^\{\(k\)\},v^\{\(k\)\}\)\_\{k=0\}^\{H\-1\}\. Nodes are expanded along the greedy path; at each step the Shannon entropyℍ​\[𝐩\(k\)\]\\mathbb\{H\}\[\\mathbf\{p\}^\{\(k\)\}\]is checked against a thresholdτ\\tau\. Low\-entropy steps \(confident policy\) are traversed automatically; expansion halts at the first high\-entropy step \(uncertain decision point\), yielding effective depthd≤Hd\\leq H\. All children at every expanded node are created, making them available for future PUCT selection\.\(3\) Backup:The valuev\(d−1\)v^\{\(d\-1\)\}from the deepest expanded state initializes the returnGG\. This return is propagated back through the horizon chain and the original selection path, accumulating intermediate rewardsrrwith discount factorγ\\gamma\(G←r\+γ​GG\\leftarrow r\+\\gamma G\), updatingNN,WW, andQQ\.\(4\) Play:AfterMMsimulations the root visit counts determine the target policy𝝅\\boldsymbol\{\\pi\}\.
### 3\.3Neural Network Architecture

The agent’s policy and value estimates are parameterized by a deep Residual Network \(ResNet\)\[[19](https://arxiv.org/html/2606.15301#bib.bib48)\]\. The architecture incorporates a lookback window for the input and a multi\-step prediction horizon for the output\.

Observation Tensor\.The statests\_\{t\}is encoded into a 5 channel tensor \(5×2​n×2​n5\\times 2n\\times 2n\):\[0\]modulus\-normalized basis𝐁/q\\mathbf\{B\}/q;\[1\]modulus\-normalized GSO vectors𝐁∗/q\\mathbf\{B\}^\{\*\}/q;\[2\]Gram\-Schmidt coefficients𝝁\\boldsymbol\{\\mu\};\[3\]normalized remaining time\(Tmax−t\)/Tmax\(T\_\{\\max\}\-t\)/T\_\{\\max\}; and\[4\]a one\-hot cursor indicator where thekk\-th row is 1\.

Temporal Lookback\.The network receives a stacked history of theWWmost recent observations along the channel dimension, resulting in an input tensor of shape5​W×2​n×2​n5W\\times 2n\\times 2n\.

ResNet Backbone\.The input tensor is processed by an initial convolutional block \(kernel size 3, padding 1\) followed by Batch Normalization and ReLU activation, then passed throughDDresidual blocks with skip connections\. We use a width of 256 filters and depthD=10D=10\.

Horizon Prediction Heads\.We use adaptive pooling to collapse the spatial dimensions\. The network predictsHHsteps into the future simultaneously, splitting into two heads:

- •Policy Head:Outputs a tensor of shapeH×\|𝒜\|H\\times\|\\mathcal\{A\}\|, representing action probabilities for the current state andH−1H\-1subsequent states along the greedy path\.
- •Value Head:Outputs a tensor of shapeHH, representing expected returns for the current and future states\.

Loss Function\.We minimize a horizon\-weighted loss:

ℒ​\(θ\)=1∑kλk​mk​∑k=0H−1λk​mk​\[ℓCE​\(𝐩\(k\),𝝅^\(k\)\)\+cv​ℓMSE​\(v\(k\),v^\(k\)\)\]\+c​‖θ‖2,\\mathcal\{L\}\(\\theta\)=\\frac\{1\}\{\\sum\_\{k\}\\lambda^\{k\}m\_\{k\}\}\\sum\_\{k=0\}^\{H\-1\}\\lambda^\{k\}\\,m\_\{k\}\\Bigl\[\\ell\_\{\\text\{CE\}\}\\bigl\(\\mathbf\{p\}^\{\(k\)\},\\hat\{\\boldsymbol\{\\pi\}\}^\{\(k\)\}\\bigr\)\+c\_\{v\}\\,\\ell\_\{\\text\{MSE\}\}\\bigl\(v^\{\(k\)\},\\hat\{v\}^\{\(k\)\}\\bigr\)\\Bigr\]\+c\\\|\\theta\\\|^\{2\},\(8\)whereλ∈\(0,1\)\\lambda\\in\(0,1\)is a horizon decay factor giving near\-future predictions more weight,mk∈\{0,1\}m\_\{k\}\\in\\\{0,1\\\}is a validity mask \(zero when the trajectory has fewer thankkremaining steps\),𝝅^\(k\)\\hat\{\\boldsymbol\{\\pi\}\}^\{\(k\)\}is the MCTS visit\-count policy at stept\+kt\+k, andv^\(k\)\\hat\{v\}^\{\(k\)\}is the return from stept\+kt\+k\.

### 3\.4Distributed Training Pipeline

Training requires generating millions of lattice reduction trajectories\. We implement an asynchronous distributed system using the Ray framework\[[34](https://arxiv.org/html/2606.15301#bib.bib62)\], dividing the workload across three actor types\.

Self\-Play Workers \(CPU\)\.Hundreds of parallel workers run thelatticeenvenvironment\. Each worker maintains a batch of active games and executes MCTS in parallel\. Leaf nodes are queued for evaluation and sent as asynchronous requests to inference servers\.

Inference Servers \(GPU\)\.Dedicated GPU servers process batched requests from the self\-play workers\. Requests are queued until a maximum batch size is reached or a timeout expires\.

The Learner \(GPU\)\.A central Learner maintains the master weights, an Adam optimizer\[[22](https://arxiv.org/html/2606.15301#bib.bib63)\], and a trajectory\-aware replay buffer\. Workers send full trajectories\. The Learner constructs target sequences of lengthHHfor each sampled state and optimizes the loss function described above\. The Learner periodically broadcasts updated weights to the inference servers\.

## 4Experiments

### 4\.1Experimental Setup

We train the reinforcement learning agent, denotedDelta\-Star, on randomly generatedqq\-ary lattices of base dimensionn=8n=8\. As described in Section[3\.1](https://arxiv.org/html/2606.15301#S3.SS1), the actual basis matrix is a16×1616\\times 16block matrix embedding the modulusq=251q=251and the identity\. The agent is trained using the distributed pipeline of Section[3\.4](https://arxiv.org/html/2606.15301#S3.SS4)with the hybrid reward at potential weightp=0\.75p=0\.75, selected based on the ablation study in Appendix[B](https://arxiv.org/html/2606.15301#A2)\.

During evaluation, we deploy the trained policy stochastically with a low temperatureT=12T=\\frac\{1\}\{2\}and evaluate over 100 random lattice instances per condition\. The primary metric is the root Hermite factorδ0=\(‖𝐛min‖/det\(ℒ\)1/n\)1/n\\delta\_\{0\}=\(\\\|\\mathbf\{b\}\_\{\\text\{min\}\}\\\|/\\det\(\\mathcal\{L\}\)^\{1/n\}\)^\{1/n\}\. We also track the orthogonality defect\. Baselines are the classical LLL algorithm withδL​L​L=0\.99\\delta\_\{LLL\}=0\.99and BKZ\-β\\betawith block sizeβ=min⁡\(2​n,20\)\\beta=\\min\(2n,20\)which is large enough for such small dimensions with a reasonable runtime\. We track cumulative row operations as a proxy for algorithmic complexity\. Each swap action counts as a single operation and navigation actions incur zero computational cost\. Size\-reduction computational cost is counted dynamically: one operation per indexkksatisfying\|μj,k\|\>12\|\\mu\_\{j,k\}\|\>\\tfrac\{1\}\{2\}, yielding between0and2​n−12n\-1operations per size\-reduction step\.

### 4\.2Scaling to Large Dimensions: Approaching BKZ Quality

A key test for any learned combinatorial policy is zero\-shot generalization: can a policy trained on small instances scale to larger, unseen dimensions? We evaluateDelta\-Star—trained exclusively onn=8n=8—on lattices up ton=32n=32without further fine\-tuning\.

The agent generalizes remarkably well, and its advantage over LLL grows with dimension\. Figure[3](https://arxiv.org/html/2606.15301#S4.F3)summarizes the final root Hermite factorδ0\\delta\_\{0\}across all dimensions fromn=8n=8ton=32n=32\. At the training dimension \(n=8n=8\),Delta\-Starconverges to a slighly lower finalδ0≈1\.00657\\delta\_\{0\}\\approx 1\.00657than LLL’sδ0=1\.0066\\delta\_\{0\}=1\.0066\. However, as the dimension increases,Delta\-Starfinds increasingly better bases compared to LLL\. Up ton=32n=32,Delta\-Starstays within the ’target zone’ between LLL and BKZ\-β\\beta, and atn=32n=32, it achievesδ0=1\.0149\\delta\_\{0\}=1\.0149versus LLL’s1\.01711\.0171and BKZ\-β\\beta’s1\.01251\.0125\.

![Refer to caption](https://arxiv.org/html/2606.15301v1/x1.png)

Figure 3:Zero\-shot scaling of final basis quality across dimensions\.Delta\-Star\(blue\), trained only onn=8n=8, consistently outperforms LLL \(red\) as dimension increases, staying close to the BKZ\-β\\betalower bound \(orange\) up ton=32n=32\. Error bars and table show one standard deviation over 50 instances\.
### 4\.3Complexity Discussion

Beyond final basis quality, the learned policy is substantially more efficient\. By decoupling cursor movement from LLL’s rigid sequential traversal, the agent finds a more direct path through the state space\.

Figure[4](https://arxiv.org/html/2606.15301#S4.F4)contrasts the reduction trajectories at the training dimension \(n=8n=8\) and large zero\-shot dimensions \(n=26,32n=26,32\)\. Atn=8n=8,Delta\-Starconverges to LLL’s quality but requires only55%55\\%of the row operations\. Atn=26n=26,Delta\-Starstays consistently below LLL’s trajectory throughout the entire reduction process and converges to a strictly better final quality\. Finally atn=32n=32, the policy continues to reduce the bases while LLL stopped at aroundδ0=1\.017\\delta\_\{0\}=1\.017\.

![Refer to caption](https://arxiv.org/html/2606.15301v1/x2.png)Figure 4:Reduction trajectories atn=8n=8\(in\-distribution\) andn=26,32n=26,32\(zero\-shot generalizations\)\.Delta\-Starconverges faster than LLL\(δL​L​L=0\.99\\delta\_\{LLL\}=0\.99\) atn=8n=8and achieves a strictly better final root Hermite factor atn=26n=26andn=32n=32\. Shaded regions show the interquartile range\.Complexity Scaling\.To characterize how the computational cost of the algorithm learned byDelta\-Stargrows with lattice dimension, we fit scaling laws to the number of cumulative row operations the agent requires to reach its best root\-Hermite factorδ0\\delta\_\{0\}\.[Figure˜11](https://arxiv.org/html/2606.15301#A5.F11)in the appendix plots this complexity metric as a function of the lattice dimension2​n2n, with individual seed outcomes shown alongside the mean±\\pmone standard deviation\. We compare two candidate models: a polynomiala⋅nba\\cdot n^\{b\}and a sub\-exponentiala⋅exp⁡\(b​n\)a\\cdot\\exp\(b\\sqrt\{n\}\)\. They both reasonably fit the curve with a high coefficient of determination\.

The learned policy is not competitive in wall\-clock time: each action requires a neural\-network forward pass, making it substantially slower per row operation than a classical implementation\. Our comparison in terms of cumulative row operations therefore measures algorithmic efficiency rather than runtime performance\. This distinction is deliberate\. By counting elementary lattice operations, we characterize the structure of the reduction strategy the policy has discovered, independent of its current implementation complexity\. Although we have not yet distilled this strategy into a closed\-form algorithm, the row\-operation scaling curves provide an empirical estimate of the performance and complexity such an algorithm would exhibit — allowing us to study a classical algorithm’s properties before having derived it\.

## 5Related Work

### 5\.1Classical Lattice Reduction

The foundation of polynomial\-time lattice reduction was established by the LLL algorithm\[[25](https://arxiv.org/html/2606.15301#bib.bib1)\]\. Schnorr introduced stronger reduction hierarchies\[[45](https://arxiv.org/html/2606.15301#bib.bib3)\], culminating in the Block Korkine\-Zolotarev \(BKZ\) algorithm\[[44](https://arxiv.org/html/2606.15301#bib.bib2),[28](https://arxiv.org/html/2606.15301#bib.bib9)\]\. BKZ generalizes the Lovász condition to block sizeβ≥2\\beta\\geq 2, requiring exact SVP solutions in projected sublattices, which yields shorter vectors at exponential complexity inβ\\beta\.

Recent work has focused on computational efficiency\. Nguyen and Stehlé\[[35](https://arxiv.org/html/2606.15301#bib.bib6)\]introduced theL2L^\{2\}algorithm, a provably polynomial\-time floating\-point LLL variant forming the basis of modern implementations\. Novocin et al\.\[[38](https://arxiv.org/html/2606.15301#bib.bib5)\]achieved the first quasi\-linear \(in bit\-length\) time complexity for LLL via a recursive structure\. Building on this, Flatter\[[42](https://arxiv.org/html/2606.15301#bib.bib7)\]speeds up reduction through recursive precision and compression, while BLASter\[[12](https://arxiv.org/html/2606.15301#bib.bib8)\]optimizes performance using BLAS operations\. These methods target speed, outputting standard LLL\-reduced bases\. Our work instead aims to improve reduction quality \(producing shorter vectors\) strictly within LLL’s original, local action space\. This task’s difficulty is underscored by Micciancio’s result that approximating the shortest vector to within constant factors is NP\-hard\[[33](https://arxiv.org/html/2606.15301#bib.bib15)\]\.

### 5\.2Machine Learning for Combinatorial Optimization

There is a growing literature on applying machine learning to combinatorial optimization\[[3](https://arxiv.org/html/2606.15301#bib.bib32),[21](https://arxiv.org/html/2606.15301#bib.bib33),[2](https://arxiv.org/html/2606.15301#bib.bib36),[56](https://arxiv.org/html/2606.15301#bib.bib35)\]\. Our approach builds on the integration of deep neural networks with MCTS\[[9](https://arxiv.org/html/2606.15301#bib.bib17),[5](https://arxiv.org/html/2606.15301#bib.bib19)\], pioneered by AlphaGo\[[47](https://arxiv.org/html/2606.15301#bib.bib21)\]and generalized by AlphaZero\[[48](https://arxiv.org/html/2606.15301#bib.bib22)\]\. Since lattice reduction lacks an adversary, we adapt MCTS for single\-player environments, following prior work on puzzles\[[43](https://arxiv.org/html/2606.15301#bib.bib20),[10](https://arxiv.org/html/2606.15301#bib.bib34)\]\.

Our work is most closely related to the recent line of AI\-driven algorithm discovery: AlphaTensor\[[13](https://arxiv.org/html/2606.15301#bib.bib24)\]for matrix multiplication, AlphaDev\[[31](https://arxiv.org/html/2606.15301#bib.bib27)\]for sorting, FunSearch\[[40](https://arxiv.org/html/2606.15301#bib.bib25)\]for combinatorial structures, AlphaEvolve\[[37](https://arxiv.org/html/2606.15301#bib.bib29)\]for general coding tasks, AlphaProof\[[20](https://arxiv.org/html/2606.15301#bib.bib26)\]and AlphaGeometry\[[51](https://arxiv.org/html/2606.15301#bib.bib28)\]for mathematical reasoning\. We extend this paradigm to lattice reduction\.

### 5\.3Machine Learning for Lattice Problems

Most prior work at the intersection of machine learning and lattice problems targets cryptanalysis rather than algorithm discovery\. The SALSA series\[[53](https://arxiv.org/html/2606.15301#bib.bib39),[27](https://arxiv.org/html/2606.15301#bib.bib40),[26](https://arxiv.org/html/2606.15301#bib.bib41),[36](https://arxiv.org/html/2606.15301#bib.bib42),[49](https://arxiv.org/html/2606.15301#bib.bib43)\]uses transformer architectures\[[52](https://arxiv.org/html/2606.15301#bib.bib45)\]to attack LWE instances by recovering sparse secrets\.

Two prior works have directly applied machine learning to lattice reduction\. Marchetti et al\.\[[32](https://arxiv.org/html/2606.15301#bib.bib30)\]proposed a self\-supervised geometric deep learning approach that directly outputs a factorized unimodular transformation matrix\. Their model is invariant to isometries and scaling but achieves performance comparable to, not exceeding, LLL up to dimension88\. Cheong et al\.\[[7](https://arxiv.org/html/2606.15301#bib.bib31)\]used deep RL to dynamically select the BKZ block sizeβ\\betavia a transformer\-based model\. While their agent discovered non\-trivial strategies \(such as prioritizing mid\-range block sizes\), performance plateaued during training and the model failed to generalize to higher dimensions\.

Our approach differs from both works in three respects\. First, we optimize the core reduction decisions \(swaps and size reductions\) within LLL’s exact action space, rather than predicting full transformations or selecting hyperparameters for BKZ\. Second, we employ a ResNet within an AlphaZero\-style self\-play loop augmented with single\-player adaptive horizon MCTS \(Section[3\.2](https://arxiv.org/html/2606.15301#S3.SS2)\)\. Third, our model strictly outperforms LLL in reduction quality and generalizes zero\-shot to dimensions well beyond those seen during training\.

### 5\.4Adaptive Horizon and Entropy in MCTS

Our entropy\-gated adaptive horizon MCTS relates to several efforts to deepen search efficiently\. V\-MCTS\[[54](https://arxiv.org/html/2606.15301#bib.bib51)\]uses multi\-step virtual expansions to approximate final policies for early termination, while 3HNN\[[16](https://arxiv.org/html/2606.15301#bib.bib52)\]introduces an action\-value head to utilize neural evaluations even when node expansion is delayed\. Other works incorporate entropy into MCTS, such as ANTS\[[24](https://arxiv.org/html/2606.15301#bib.bib53)\]and EG\-MCTS\[[29](https://arxiv.org/html/2606.15301#bib.bib54)\], but primarily to bias action selection rather than control expansion depth\. While MuZero\[[46](https://arxiv.org/html/2606.15301#bib.bib23)\]and EfficientZero\[[55](https://arxiv.org/html/2606.15301#bib.bib60)\]use multi\-step unrolling during training, their search expansion remains standard\. The predictive power of MCTS plans has been noted for interpretability\[[8](https://arxiv.org/html/2606.15301#bib.bib55)\], and macro\-actions\[[11](https://arxiv.org/html/2606.15301#bib.bib56),[18](https://arxiv.org/html/2606.15301#bib.bib57)\]allow multi\-step commitments, but these typically rely on pre\-defined options or learned abstractions rather than online policy confidence\. Finally, while MCTS has been applied to non\-game optimization like resource allocation\[[4](https://arxiv.org/html/2606.15301#bib.bib58)\]and financial hedging\[[50](https://arxiv.org/html/2606.15301#bib.bib59)\]—sometimes producing asymmetric trees via standard UCB allocation—Delta\-Staris unique in explicitly using the Shannon entropy of the policy network to dynamically gate the physical expansion depth within a single iteration, skipping forced sequences to concentrate compute on genuine decision points\.

## 6Conclusion

We have demonstrated that deep reinforcement learning can discover lattice reduction strategies that are strictly superior to the classical LLL algorithm\. By formulating reduction as a Markov Decision Process over primitive row operations and training a value\-policy network via self\-play, our model,Delta\-Star, learns a scale\-invariant heuristic\. Despite being trained exclusively on small88\-dimensionalqq\-ary lattices,Delta\-Stargeneralizes zero\-shot to dimensions up ton=30n=30and unseen moduli, consistently converging in significantly fewer operations than LLL while achieving better basis quality that approaches BKZ\.

This work opens several compelling directions for future research\. First, the learned policy weights encode a deterministic, highly efficient reduction algorithm; extracting and formalizing this classical algorithm from the neural network is a primary objective\. Second, the same self\-play methodology can be applied to improve block\-based reduction algorithms like BKZ by augmenting the action space with oracle calls for exact Shortest Vector Problem \(SVP\) subroutines\. Finally, the success ofDelta\-Starsuggests that other fundamental, heuristic\-driven algorithms in computational mathematics and cryptography may be similarly accelerated by discovering optimal decision paths through reinforcement learning\.

## References

- \[1\]\(1998\)The shortest vector problem inL2L\_\{2\}is NP\-hard for randomized reductions\.InProc\. of STOC,pp\. 10–19\.Cited by:[§1](https://arxiv.org/html/2606.15301#S1.p1.1)\.
- \[2\]I\. Bello, H\. Pham, Q\. V\. Le, M\. Norouzi, and S\. Bengio\(2017\)Neural combinatorial optimization with reinforcement learning\.arXiv preprint arXiv:1611\.09940\.Cited by:[§5\.2](https://arxiv.org/html/2606.15301#S5.SS2.p1.1)\.
- \[3\]Y\. Bengio, A\. Lodi, and A\. Prouvost\(2021\)Machine learning for combinatorial optimization: a methodological tour d’horizon\.European Journal of Operational Research290\(2\),pp\. 405–421\.Cited by:[§5\.2](https://arxiv.org/html/2606.15301#S5.SS2.p1.1)\.
- \[4\]D\. Bertsimas, J\. D\. Griffith, V\. Gupta, M\. J\. Kochenderfer, and V\. V\. Mišić\(2017\)A comparison of Monte Carlo tree search and rolling horizon optimization for large\-scale dynamic resource allocation problems\.European Journal of Operational Research263\(2\),pp\. 664–678\.Cited by:[§5\.4](https://arxiv.org/html/2606.15301#S5.SS4.p1.1)\.
- \[5\]C\. B\. Browne, E\. Powley, D\. Whitehouse,et al\.\(2012\)A survey of Monte Carlo tree search methods\.IEEE Transactions on Computational Intelligence and AI in Games4\(1\),pp\. 1–43\.Cited by:[§5\.2](https://arxiv.org/html/2606.15301#S5.SS2.p1.1)\.
- \[6\]L\. Chen, D\. Moody, Y\. Liu,et al\.\(2022\)PQC Standardization Process: Announcing Four Candidates to be Standardized, Plus Fourth Round Candidates\.US Department of Commerce, NIST\.Cited by:[§1](https://arxiv.org/html/2606.15301#S1.p1.1)\.
- \[7\]S\. F\. Cheong, C\. W\. Lim, and Y\. B\. Ti\(2025\)Investigating deep reinforcement learning for BKZ lattice reduction\.Note:DSO National LaboratoriesCited by:[§5\.3](https://arxiv.org/html/2606.15301#S5.SS3.p2.2)\.
- \[8\]S\. Chung, S\. Niekum, and D\. Krueger\(2024\)Predicting future actions of reinforcement learning agents\.arXiv preprint arXiv:2410\.22459\.Cited by:[§5\.4](https://arxiv.org/html/2606.15301#S5.SS4.p1.1)\.
- \[9\]R\. Coulom\(2006\)Efficient selectivity and backup operators in Monte\-Carlo tree search\.InProc\. of Computers and Games,pp\. 72–83\.Cited by:[§1](https://arxiv.org/html/2606.15301#S1.p4.1),[§5\.2](https://arxiv.org/html/2606.15301#S5.SS2.p1.1)\.
- \[10\]E\. Dantsin, V\. Kreinovich, and A\. Wolpert\(2022\)An AlphaZero\-inspired approach to solving search problems\.arXiv preprint arXiv:2207\.00919\.Cited by:[§5\.2](https://arxiv.org/html/2606.15301#S5.SS2.p1.1)\.
- \[11\]M\. de Waard\(2016\)Monte carlo tree search with options for general video game playing\.Tilburg University\.Cited by:[§5\.4](https://arxiv.org/html/2606.15301#S5.SS4.p1.1)\.
- \[12\]L\. Ducas, L\. N\. Pulles, and M\. Stevens\(2025\)Towards a modern LLL implementation\.IACR Cryptol\. ePrint Arch\.\.Note:Report 2025/774Cited by:[§5\.1](https://arxiv.org/html/2606.15301#S5.SS1.p2.1)\.
- \[13\]A\. Fawzi, M\. Balog, A\. Huang,et al\.\(2022\)Discovering faster matrix multiplication algorithms with reinforcement learning\.Nature610\(7930\),pp\. 47–53\.Cited by:[§1](https://arxiv.org/html/2606.15301#S1.p4.1),[§5\.2](https://arxiv.org/html/2606.15301#S5.SS2.p2.1)\.
- \[14\]N\. Gama, P\. Q\. Nguyen, and O\. Regev\(2010\)Lattice enumeration using extreme pruning\.InAdvances in Cryptology \- EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30 \- June 3, 2010\. Proceedings,Lecture Notes in Computer Science, Vol\.6110,pp\. 257–278\.External Links:[Document](https://dx.doi.org/10.1007/978-3-642-13190-5%5F13)Cited by:[item 1](https://arxiv.org/html/2606.15301#S1.I1.i1.p1.1)\.
- \[15\]N\. Gama and P\. Q\. Nguyen\(2008\)Predicting lattice reduction\.InProc\. of EUROCRYPT,pp\. 31–51\.Cited by:[§1](https://arxiv.org/html/2606.15301#S1.p1.1),[§1](https://arxiv.org/html/2606.15301#S1.p3.1)\.
- \[16\]C\. Gao, M\. Müller, and R\. Hayward\(2018\)Three\-head neural network architecture for Monte Carlo tree search\.InProc\. of IJCAI,pp\. 3762–3768\.Cited by:[§5\.4](https://arxiv.org/html/2606.15301#S5.SS4.p1.1)\.
- \[17\]J\. Hadamard\(1893\)Résolution d’une question relative aux déterminants\.Bulletin des Sciences Mathématiques17\(1\),pp\. 240–246\.Cited by:[§2\.1](https://arxiv.org/html/2606.15301#S2.SS1.p3.3)\.
- \[18\]D\. Hafner, K\. Lee, I\. Fischer, and P\. Abbeel\(2022\)Deep hierarchical planning from pixels\.InProc\. of NeurIPS,Cited by:[§5\.4](https://arxiv.org/html/2606.15301#S5.SS4.p1.1)\.
- \[19\]K\. He, X\. Zhang, S\. Ren, and J\. Sun\(2016\)Deep residual learning for image recognition\.Proc\. of CVPR\.Cited by:[§1](https://arxiv.org/html/2606.15301#S1.p6.1),[§3\.3](https://arxiv.org/html/2606.15301#S3.SS3.p1.1)\.
- \[20\]T\. Hubert, K\. Kowalski, L\. Sifre,et al\.\(2025\)Olympiad\-level formal mathematical reasoning with AlphaProof\.Nature\.Cited by:[§1](https://arxiv.org/html/2606.15301#S1.p4.1),[§5\.2](https://arxiv.org/html/2606.15301#S5.SS2.p2.1)\.
- \[21\]E\. Khalil, H\. Dai, Y\. Zhang, B\. Dilkina, and L\. Song\(2017\)Learning combinatorial optimization algorithms over graphs\.InProc\. of NeurIPS,Cited by:[§5\.2](https://arxiv.org/html/2606.15301#S5.SS2.p1.1)\.
- \[22\]D\. P\. Kingma and J\. Ba\(2015\)Adam: A method for stochastic optimization\.In3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7\-9, 2015, Conference Track Proceedings,Y\. Bengio and Y\. LeCun \(Eds\.\),External Links:[Link](http://arxiv.org/abs/1412.6980)Cited by:[§3\.4](https://arxiv.org/html/2606.15301#S3.SS4.p4.1)\.
- \[23\]L\. Kocsis and C\. Szepesvári\(2006\)Bandit based Monte\-Carlo planning\.InProc\. of ECML,pp\. 282–293\.Cited by:[§1](https://arxiv.org/html/2606.15301#S1.p4.1)\.
- \[24\]P\. Kozakowski, M\. Pacek, and P\. Miłoś\(2021\)Planning and learning using adaptive entropy tree search\.arXiv preprint arXiv:2102\.06808\.Cited by:[§5\.4](https://arxiv.org/html/2606.15301#S5.SS4.p1.1)\.
- \[25\]A\. K\. Lenstra, H\. W\. Lenstra, and L\. Lovász\(1982\)Factoring polynomials with rational coefficients\.Mathematische Annalen261\(4\),pp\. 515–534\.Cited by:[§1](https://arxiv.org/html/2606.15301#S1.p2.1),[§2\.3](https://arxiv.org/html/2606.15301#S2.SS3.p1.2),[§5\.1](https://arxiv.org/html/2606.15301#S5.SS1.p1.2)\.
- \[26\]C\. Li, E\. Wenger, Z\. Allen\-Zhu, F\. Charton, and K\. Lauter\(2023\)SALSA VERDE: a machine learning attack on learning with errors with sparse small secrets\.InProc\. of NeurIPS,Cited by:[§5\.3](https://arxiv.org/html/2606.15301#S5.SS3.p1.1)\.
- \[27\]C\. Y\. Li, J\. Sotáková, E\. Wenger, M\. Malhou, E\. Garcelon, F\. Charton, and K\. Lauter\(2023\)SALSA Picante: a machine learning attack on LWE with binary secrets\.InProc\. of ACM CCS,Cited by:[§5\.3](https://arxiv.org/html/2606.15301#S5.SS3.p1.1)\.
- \[28\]J\. Li and P\. Q\. Nguyen\(2025\)A complete analysis of the BKZ lattice reduction algorithm\.Journal of Cryptology38\.Cited by:[§5\.1](https://arxiv.org/html/2606.15301#S5.SS1.p1.2)\.
- \[29\]S\. Li, X\. Jia, Y\. Zhou, D\. Xu, H\. Zhang, and M\. Hu\(2024\)Entropy\-guided exploration in AlphaZero: enhancing MCTS with information gain for strategic decision making\.InProc\. of MLMI,Cited by:[§5\.4](https://arxiv.org/html/2606.15301#S5.SS4.p1.1)\.
- \[30\]V\. Lyubashevsky, C\. Peikert, and O\. Regev\(2010\)On ideal lattices and learning with errors over rings\.InAdvances in Cryptology – EUROCRYPT 2010,Lecture Notes in Computer Science, Vol\.6110,pp\. 1–23\.External Links:[Document](https://dx.doi.org/10.1007/978-3-642-13190-5%5F1)Cited by:[Appendix D](https://arxiv.org/html/2606.15301#A4.p1.1)\.
- \[31\]D\. J\. Mankowitz, A\. Michi, A\. Zhernov,et al\.\(2023\)Faster sorting algorithms discovered using deep reinforcement learning\.Nature618,pp\. 257–263\.Cited by:[§1](https://arxiv.org/html/2606.15301#S1.p4.1),[§5\.2](https://arxiv.org/html/2606.15301#S5.SS2.p2.1)\.
- \[32\]G\. L\. Marchetti, G\. Cesa, P\. Kumar, and A\. Behboodi\(2025\)Neural lattice reduction: a self\-supervised geometric deep learning approach\.Transactions on Machine Learning Research\.Cited by:[§1](https://arxiv.org/html/2606.15301#S1.p5.1),[§5\.3](https://arxiv.org/html/2606.15301#S5.SS3.p2.2)\.
- \[33\]D\. Micciancio\(2001\)The shortest vector in a lattice is hard to approximate to within some constant\.SIAM Journal on Computing30\(6\),pp\. 2008–2035\.Cited by:[§1](https://arxiv.org/html/2606.15301#S1.p1.1),[§5\.1](https://arxiv.org/html/2606.15301#S5.SS1.p2.1)\.
- \[34\]P\. Moritz, R\. Nishihara, S\. Wang, A\. Tumanov, R\. Liaw, E\. Liang, M\. Elibol, Z\. Yang, W\. Paul, M\. I\. Jordan, and I\. Stoica\(2018\)Ray: a distributed framework for emerging AI applications\.In13th USENIX Symposium on Operating Systems Design and Implementation \(OSDI 18\),pp\. 561–577\.External Links:ISBN 978\-1\-939133\-08\-3,[Link](https://www.usenix.org/conference/osdi18/presentation/moritz)Cited by:[§3\.4](https://arxiv.org/html/2606.15301#S3.SS4.p1.1)\.
- \[35\]P\. Q\. Nguyen and D\. Stehlé\(2009\)An lll algorithm with quadratic complexity\.SIAM Journal on Computing39\(3\),pp\. 874–903\.Cited by:[§5\.1](https://arxiv.org/html/2606.15301#S5.SS1.p2.1)\.
- \[36\]N\. Nolte, M\. Malhou, E\. Wenger, S\. Stevens, C\. Li, F\. Charton, and K\. Lauter\(2024\)The cool and the cruel: separating hard parts of LWE secrets\.Proc\. of AFRICACRYPT\.Cited by:[§5\.3](https://arxiv.org/html/2606.15301#S5.SS3.p1.1)\.
- \[37\]A\. Novikov, N\. Vũ, M\. Eisenberger,et al\.\(2025\)AlphaEvolve: a coding agent for scientific and algorithmic discovery\.arXiv preprint arXiv:2506\.13131\.Cited by:[§5\.2](https://arxiv.org/html/2606.15301#S5.SS2.p2.1)\.
- \[38\]A\. Novocin, D\. Stehlé, and G\. Villard\(2011\)An lll\-reduction algorithm with quasi\-linear time complexity\.InProceedings of the forty\-third annual ACM symposium on Theory of computing,pp\. 403–412\.Cited by:[§5\.1](https://arxiv.org/html/2606.15301#S5.SS1.p2.1)\.
- \[39\]O\. Regev\(2005\)On Lattices, Learning with Errors, Random Linear Codes, and Cryptography\.InProc\. of STOC,Cited by:[§1](https://arxiv.org/html/2606.15301#S1.p1.1)\.
- \[40\]B\. Romera\-Paredes, M\. Barekatain, A\. Novikov,et al\.\(2024\)Mathematical discoveries from program search with large language models\.Nature625\(7996\),pp\. 681–689\.Cited by:[§1](https://arxiv.org/html/2606.15301#S1.p4.1),[§5\.2](https://arxiv.org/html/2606.15301#S5.SS2.p2.1)\.
- \[41\]C\. D\. Rosin\(2011\)Multi\-armed bandits with episode context\.Annals of Mathematics and Artificial Intelligence61\(3\),pp\. 203–230\.External Links:[Document](https://dx.doi.org/10.1007/s10115-011-0429-5)Cited by:[Figure 2](https://arxiv.org/html/2606.15301#S3.F2)\.
- \[42\]K\. Ryan and N\. Heninger\(2023\)Fast practical lattice reduction through iterated compression\.IACR Cryptol\. ePrint Arch\.\.Note:Report 2023/237Cited by:[§5\.1](https://arxiv.org/html/2606.15301#S5.SS1.p2.1)\.
- \[43\]M\. P\.D\. Schadd, M\. H\.M\. Winands, M\. J\.W\. Tak, and J\. W\.H\.M\. Uiterwijk\(2012\)Single\-player Monte\-Carlo tree search for SameGame\.Knowledge\-Based Systems34,pp\. 3–11\.Cited by:[§1](https://arxiv.org/html/2606.15301#S1.p4.1),[§5\.2](https://arxiv.org/html/2606.15301#S5.SS2.p1.1)\.
- \[44\]C\. P\. Schnorr and M\. Euchner\(1994\)Lattice basis reduction: improved practical algorithms and solving subset sum problems\.Mathematical Programming66\(2\),pp\. 181–199\.Cited by:[§E\.1](https://arxiv.org/html/2606.15301#A5.SS1.p1.7),[§2\.3](https://arxiv.org/html/2606.15301#S2.SS3.p3.2),[§5\.1](https://arxiv.org/html/2606.15301#S5.SS1.p1.2)\.
- \[45\]C\. P\. Schnorr\(1987\)A hierarchy of polynomial time lattice basis reduction algorithms\.Theoretical Computer Science53\(2\),pp\. 201–224\.Cited by:[§2\.3](https://arxiv.org/html/2606.15301#S2.SS3.p3.2),[§5\.1](https://arxiv.org/html/2606.15301#S5.SS1.p1.2)\.
- \[46\]J\. Schrittwieser, I\. Antonoglou, T\. Hubert,et al\.\(2020\)Mastering Atari, Go, chess and shogi by planning with a learned model\.Nature588,pp\. 604–609\.Cited by:[§1](https://arxiv.org/html/2606.15301#S1.p4.1),[§5\.4](https://arxiv.org/html/2606.15301#S5.SS4.p1.1)\.
- \[47\]D\. Silver, A\. Huang, C\. J\. Maddison,et al\.\(2016\)Mastering the game of Go with deep neural networks and tree search\.Nature529\(7587\),pp\. 484–489\.Cited by:[§1](https://arxiv.org/html/2606.15301#S1.p4.1),[Figure 2](https://arxiv.org/html/2606.15301#S3.F2),[§5\.2](https://arxiv.org/html/2606.15301#S5.SS2.p1.1)\.
- \[48\]D\. Silver, T\. Hubert, J\. Schrittwieser,et al\.\(2018\)A general reinforcement learning algorithm that masters chess, shogi, and Go through self\-play\.Science362\(6419\),pp\. 1140–1144\.Cited by:[§1](https://arxiv.org/html/2606.15301#S1.p4.1),[§1](https://arxiv.org/html/2606.15301#S1.p6.1),[§3\.2](https://arxiv.org/html/2606.15301#S3.SS2.p1.5),[§3\.2](https://arxiv.org/html/2606.15301#S3.SS2.p6.1),[§5\.2](https://arxiv.org/html/2606.15301#S5.SS2.p1.1)\.
- \[49\]S\. Stevens, E\. Wenger, C\. Y\. Li, N\. Nolte, E\. Saxena, F\. Charton, and K\. Lauter\(2024\)SALSA FRESCA: angular embeddings and pre\-training for ML attacks on learning with errors\.Transactions on Machine Learning Research \(TMLR\)\.Cited by:[§5\.3](https://arxiv.org/html/2606.15301#S5.SS3.p1.1)\.
- \[50\]O\. Szehr\(2023\)Hedging of financial derivative contracts via Monte Carlo tree search\.Journal of Computational Finance\.Cited by:[§5\.4](https://arxiv.org/html/2606.15301#S5.SS4.p1.1)\.
- \[51\]T\. H\. Trinh, Y\. Wu, Q\. V\. Le,et al\.\(2024\)Solving olympiad geometry without human demonstrations\.Nature625,pp\. 476–482\.Cited by:[§5\.2](https://arxiv.org/html/2606.15301#S5.SS2.p2.1)\.
- \[52\]A\. Vaswani, N\. Shazeer, N\. Parmar, J\. Uszkoreit, L\. Jones, A\. N\. Gomez, L\. Kaiser, and I\. Polosukhin\(2017\)Attention is all you need\.InProc\. of NeurIPS,Cited by:[§5\.3](https://arxiv.org/html/2606.15301#S5.SS3.p1.1)\.
- \[53\]E\. Wenger, M\. Chen, F\. Charton, and K\. E\. Lauter\(2022\)SALSA: attacking lattice cryptography with transformers\.Proc\. of NeurIPS\.Cited by:[§5\.3](https://arxiv.org/html/2606.15301#S5.SS3.p1.1)\.
- \[54\]W\. Ye, P\. Abbeel, and Y\. Gao\(2022\)Spending thinking time wisely: accelerating MCTS with virtual expansions\.InProc\. of NeurIPS,Cited by:[§5\.4](https://arxiv.org/html/2606.15301#S5.SS4.p1.1)\.
- \[55\]W\. Ye, S\. Liu, T\. Kurutach, P\. Abbeel, and Y\. Gao\(2021\)Mastering Atari games with limited data\.InProc\. of NeurIPS,Cited by:[§5\.4](https://arxiv.org/html/2606.15301#S5.SS4.p1.1)\.
- \[56\]C\. Zhou, C\. Yu, S\. Yao, X\. Lin, Z\. Wang, Y\. Zhou, and Q\. Zhang\(2025\)URS: a unified neural routing solver for cross\-problem zero\-shot generalization\.arXiv preprint arXiv:2509\.23413\.Cited by:[§5\.2](https://arxiv.org/html/2606.15301#S5.SS2.p1.1)\.

## Appendix AAdditional Lattice Background

### A\.1Orthogonality Defect and Its Relationship to the Root Hermite Factor

The orthogonality defect of a basis𝐁\\mathbf\{B\}is defined as:

δ​\(𝐁\)=∏i=1n‖𝐛i‖det\(ℒ\)=∏i=1n‖𝐛i‖‖𝐛~i‖\.\\delta\(\\mathbf\{B\}\)=\\frac\{\\prod\_\{i=1\}^\{n\}\\\|\\mathbf\{b\}\_\{i\}\\\|\}\{\\det\(\\mathcal\{L\}\)\}=\\prod\_\{i=1\}^\{n\}\\frac\{\\\|\\mathbf\{b\}\_\{i\}\\\|\}\{\\\|\\widetilde\{\\mathbf\{b\}\}\_\{i\}\\\|\}\.\(9\)Hadamard’s inequality guaranteesδ​\(𝐁\)≥1\\delta\(\\mathbf\{B\}\)\\geq 1, with equality if and only if the basis is orthogonal\. A globally orthogonalized basis naturally forces individual vectors to be shorter, so minimizing the orthogonality defect tends to improve the root Hermite factor as well\. In practice, lattice reduction algorithms seek a unimodular transformation𝐔\\mathbf\{U\}that simultaneously reduces both quantities\.

### A\.2The LLL Potential Function

The standard termination and complexity analysis of LLL relies on the potential function:

Φ​\(𝐁\)=∏i=1n‖𝐛~i‖n−i\+1\.\\Phi\(\\mathbf\{B\}\)=\\prod\_\{i=1\}^\{n\}\\\|\\widetilde\{\\mathbf\{b\}\}\_\{i\}\\\|^\{n\-i\+1\}\.\(10\)Every swap operation strictly decreasesΦ\\Phiby a factor of at leastδ<1\\sqrt\{\\delta\}<1, while size\-reduction operations leaveΦ\\Phiunchanged\. BecauseΦ\\Phiis bounded below by a function ofdet\(ℒ\)\\det\(\\mathcal\{L\}\), the total number of swaps is polynomial\. The Lovász condition is designed precisely to guarantee this monotonic decrease: it is the sufficient condition under which a swap provably reduces the potential\. However, the condition does not prescribe the optimal sequence of actions for achieving the highest quality reduction\.

## Appendix BAblation Study: Reward Model Selection and Benchmark

A critical design choice in our MDP formulation is the reward function\. As introduced in Section[3\.1](https://arxiv.org/html/2606.15301#S3.SS1), the hybrid reward is parameterized by a potential weightp∈\[0,1\]p\\in\[0,1\], interpolating between the orthogonality defect \(p=0p=0\) and the LLL potential function \(p=1p=1\)\.

We trained five independent models forp∈\{0\.0,0\.25,0\.5,0\.75,1\.0\}p\\in\\\{0\.0,0\.25,0\.5,0\.75,1\.0\\\}onn=8n=8lattices up to 100,000 training steps, then evaluated the best checkpoint for each model across 100 random instances per condition\. The benchmark varies three parameters: lattice modulusqq, dimensionnn, and maximum step allocationTmaxT\_\{\\max\}\. All models are evaluated on the root Hermite factorδ0\\delta\_\{0\}, a neutral metric independent of the training objective\.

### B\.1In\-Distribution Convergence and Efficiency

Figure[5](https://arxiv.org/html/2606.15301#A2.F5)shows the reduction trajectories for all five models at the in\-distribution parameters \(n=8,q=251n=8,q=251\)\. All values ofppconverge to nearly identical finalδ0≈1\.0153\\delta\_\{0\}\\approx 1\.0153, matching LLL\. The models differ in convergence speed\.

![Refer to caption](https://arxiv.org/html/2606.15301v1/x3.png)Figure 5:Trajectories for all five reward models atq=251q=251\. All converge to similar basis quality, butp=1p=1\(yellow\-green\) converges fastest\.When measuring the ratio of row operations required by each RL agent relative to LLL to reach95%95\\%of LLL’s totalδ0\\delta\_\{0\}improvement, every RL formulation requires significantly fewer operations\. Thep=1p=1model is the most aggressive, requiring only∼36\\sim 36–40%40\\%of LLL’s operations forq≥97q\\geq 97\. However,p=0\.75p=0\.75offers the best balance of efficiency \(∼40\\sim 40–65%65\\%of LLL’s operations across all tested dimensions\) and stable zero\-shot generalization, which is why it was selected for the main experiments in Section[4](https://arxiv.org/html/2606.15301#S4)\.

### B\.2Generalization Across Moduli and Dimensions

We evaluate the learned policies on unseen moduliq∈\{23,97,251,499,1009,4019,10007\}q\\in\\\{23,97,251,499,1009,4019,10007\\\}and dimensions up ton=20n=20\.

Figure[6](https://arxiv.org/html/2606.15301#A2.F6)showsδ0\\delta\_\{0\}trajectories across moduli\. All models converge to LLL\-quality bases at moderate moduli \(q≤499q\\leq 499\)\. At extreme out\-of\-distribution moduli \(q≥1009q\\geq 1009\), the pure orthogonality defect model \(p=0p=0\) and hybrid models \(p=0\.5,0\.75p=0\.5,0\.75\) degrade more gracefully thanp=1p=1\.

![Refer to caption](https://arxiv.org/html/2606.15301v1/figures/fig_app_grid_q_rhf_cropped.png)Figure 6:Root Hermite factor trajectories across lattice moduliqq\. The x\-axis is clipped to LLL’s cumulative row operations for eachqq\. Hybrid models generalize better to larger moduli\.Generalization across dimension is the most notable property of the learned policies\. As detailed in Section[4](https://arxiv.org/html/2606.15301#S4), thep=0\.75p=0\.75model scales zero\-shot ton=30n=30, consistently outperforming LLL\. Figure[7](https://arxiv.org/html/2606.15301#A2.F7)shows trajectories for the root Hermite factor across all eight tested dimensions fromn=8n=8ton=30n=30\. The RL agent consistently converges faster than LLL at every dimension, confirming that the network has learned a scale\-invariant reduction heuristic\. At dimensionsn≥24n\\geq 24, the agent’s trajectory stays strictly below LLL’s throughout the entire reduction process\.

![Refer to caption](https://arxiv.org/html/2606.15301v1/x4.png)Figure 7:Root Hermite factor trajectories across all tested dimensionsn∈\{8,12,16,20,24,26,28,30,32\}n\\in\\\{8,12,16,20,24,26,28,30,32\\\}\. The convergence speed advantage is preserved at larger, unseen dimensions, up to 32 where the policy continues to reduce the basis while LLL \(withδ=0\.99\\delta=0\.99\) stopped at a high rhf value\. The policy starts to diverge too from the BKZ performance\.To provide a complete picture of the agent’s behavior at the largest tested dimension, Figure[8](https://arxiv.org/html/2606.15301#A2.F8)shows the reduction trajectories atn=30n=30across all three tracked metrics: root Hermite factor, log orthogonality defect, and log potential\.Delta\-Stardominates LLL on all three metrics, demonstrating that the learned policy optimizes the global basis structure more effectively than the classical heuristic\.

![Refer to caption](https://arxiv.org/html/2606.15301v1/x5.png)Figure 8:Detailed reduction trajectories atn=30n=30\(zero\-shot\) across all three metrics\.Delta\-Star\(blue\) converges faster and to a better final quality than LLL \(red\) on root Hermite factor, log orthogonality defect, and log potential\.
### B\.3Convergence Under Varying Allocations

Figure[9](https://arxiv.org/html/2606.15301#A2.F9)shows performance under constrained step allocations\. LLL requires a fixed number of operations and cannot be halted early without severe quality penalties\. The RL agents behave as anytime algorithms: basis quality improves smoothly as the allocation increases, converging to LLL\-equivalent quality byTmax≈1400T\_\{\\max\}\\approx 1400\.

![Refer to caption](https://arxiv.org/html/2606.15301v1/figures/fig_app_budget_cropped.png)Figure 9:Final basis quality as a function ofTmaxT\_\{\\max\}\. The RL agents smoothly improve with increased step allocation, acting as anytime algorithms\.The choice ofppdictates a trade\-off between convergence speed and generalization robustness\. The pure potential formulation \(p=1p=1\) converges fastest in\-distribution\. For zero\-shot generalization to different dimensions and moduli,p=0\.75p=0\.75provides the best balance, enabling the scaling results in the main text\.

## Appendix CAblation Study: Entropy\-Gated Horizon

The entropy\-gated adaptive horizon mechanism introduced in Section[3\.2](https://arxiv.org/html/2606.15301#S3.SS2)controls the depth of multi\-step expansion during MCTS\. Each simulation consumes exactly one neural network evaluation regardless of horizon depth: the multi\-step expansion is computationally free, amortizing a single forward pass across multiple node creations\. We conduct a preliminary ablation at dimensionn=12n=12, evaluating 11 runs \(1–2 trials per configuration\) across the baseline \(H=1H=1\) and multi\-step configurations \(H∈\{4,8\}H\\in\\\{4,8\\\}\) with entropy thresholdsτ∈\{0\.6,1\.0,1\.5\}\\tau\\in\\\{0\.6,1\.0,1\.5\\\}\. All agents use 25 MCTS simulations per move and are trained for 25–32 million environment samples\.

### C\.1Performance

Table[1](https://arxiv.org/html/2606.15301#A3.T1)summarizes the results\. All horizon variants outperform the baseline, suggesting that multi\-step expansion improves learning when the simulation budget is held constant\. The best\-performing configurations areH=4,τ=1\.5H=4,\\tau=1\.5andH=8,τ=0\.6H=8,\\tau=0\.6, which achieve comparable returns despite operating in very different regimes\.

Table 1:Horizon ablation atn=12n=12\. Metrics are averaged over the final quarter of training\. Total nodes estimates the tree size per action decision \(25×25\\timeshorizon depth\)\. Results should be interpreted cautiously given the limited number of trials per configuration\.The data hints at an interaction between horizon capacityHHand the entropy thresholdτ\\tau\. AtH=4H=4, higher thresholds appear beneficial \(τ=1\.5\>1\.0\>0\.6\\tau=1\.5\>1\.0\>0\.6\): with bounded capacity, the maximum commitment of 4 steps may be short enough that errors remain recoverable\. AtH=8H=8, the relationship appears to invert:τ=0\.6\\tau=0\.6outperformsτ=1\.0\\tau=1\.0\. When the horizon allows very deep commitments, aggressive expansion risks committing to sequences that are not truly forced, potentially injecting unreliable value estimates into the tree\. Strict gating prevents this by restricting expansion to high\-confidence states\. We note, however, that with at most 2 trials per configuration, these trends remain preliminary\.

### C\.2Self\-Regulating Dynamics

The horizon mechanism appears to exhibit a self\-regulating feedback loop during training\. As shown in Figure[10](https://arxiv.org/html/2606.15301#A3.F10), the average horizon depth forH=8,τ=0\.6H=8,\\tau=0\.6grows from 1\.69 in the first quarter of training to 4\.29 in the final quarter—a 153% increase with no sign of saturation\. This growth is not externally scheduled: it emerges as the policy becomes more confident \(lower entropy\), allowing more states to pass the entropy gate\.

![Refer to caption](https://arxiv.org/html/2606.15301v1/x6.png)Figure 10:Horizon depth over the course of training\. Strict\-gating configurations \(τ=0\.6\\tau=0\.6\) start near the baseline and grow as the policy gains confidence, while high\-threshold configurations start high and plateau\.Across all horizon variants, the temporal correlation between horizon depth and return is positive \(r≈\+0\.88r\\approx\+0\.88to\+0\.96\+0\.96\), while the correlation between policy entropy and return is negative \(r≈−0\.93r\\approx\-0\.93\)\. This is consistent with a virtuous cycle: as the policy improves, entropy decreases, more states pass the gate, and the tree captures longer forced sequences\. Multi\-step targets also increase gradient norms \(up to2×2\\timesthe baseline\), but all runs remain stable throughout training\.

## Appendix DZero\-Shot Generalization to Ring\-LWE and Module Lattices

In addition to standard unstructuredqq\-ary lattices, we evaluate our agent on structured ideal lattices underlying the Ring Learning With Errors \(Ring\-LWE\) problem\[[30](https://arxiv.org/html/2606.15301#bib.bib12)\]\. Ring\-LWE forms the mathematical foundation of several NIST post\-quantum cryptographic standards\.

### D\.1Kannan’s Embedding for Primal Attacks

The Ring\-LWE problem asks an adversary to recover a secret polynomial𝐬∈ℛq\\mathbf\{s\}\\in\\mathcal\{R\}\_\{q\}from noisy samples\(𝐚,𝐛=𝐚⋅𝐬\+𝐞\(modq\)\)\(\\mathbf\{a\},\\mathbf\{b\}=\\mathbf\{a\}\\cdot\\mathbf\{s\}\+\\mathbf\{e\}\\pmod\{q\}\), whereℛq=ℤq​\[x\]/\(xn\+1\)\\mathcal\{R\}\_\{q\}=\\mathbb\{Z\}\_\{q\}\[x\]/\(x^\{n\}\+1\)and the coefficients of𝐬\\mathbf\{s\}and𝐞\\mathbf\{e\}are drawn from a narrow centered binomial distribution parameterized byη\\eta\.

The standard primal attack frames secret recovery as finding a uniquely short vector in a specific lattice via Kannan’s embedding\. For a single Ring\-LWE sample, we construct a\(2​n\+1\)×\(2​n\+1\)\(2n\+1\)\\times\(2n\+1\)basis:

𝐁RLWE=\[q​𝐈n𝟎𝟎𝐀neg𝐈n𝟎𝐛⊤𝟎c\],\\mathbf\{B\}\_\{\\text\{RLWE\}\}=\\begin\{bmatrix\}q\\mathbf\{I\}\_\{n\}&\\mathbf\{0\}&\\mathbf\{0\}\\\\ \\mathbf\{A\}\_\{\\text\{neg\}\}&\\mathbf\{I\}\_\{n\}&\\mathbf\{0\}\\\\ \\mathbf\{b\}^\{\\top\}&\\mathbf\{0\}&c\\end\{bmatrix\},\(11\)where𝐀neg\\mathbf\{A\}\_\{\\text\{neg\}\}is then×nn\\times nnegacyclic matrix representing polynomial multiplication by𝐚\\mathbf\{a\}inℛq\\mathcal\{R\}\_\{q\}, andccis a scalar embedding factor \(typicallyc=1c=1\)\.

This lattice contains the target vector𝐯=\(𝐞,−𝐬,c\)\\mathbf\{v\}=\(\\mathbf\{e\},\-\\mathbf\{s\},c\)\. Because𝐬\\mathbf\{s\}and𝐞\\mathbf\{e\}have small coefficients,𝐯\\mathbf\{v\}is unusually short relative to the expected shortest vector in a random lattice of the same volume\. A successful lattice reduction will place𝐯\\mathbf\{v\}among the rows of the reduced basis, allowing direct recovery of the secret key\.

### D\.2Secret Recovery

We train and evaluate our agent on Ring\-LWE instances\. The environment state includes the\(2​n\+1\)×\(2​n\+1\)\(2n\+1\)\\times\(2n\+1\)basis, and the reward function includes a terminal bonus for recovering the target vector\(𝐞,−𝐬,c\)\(\\mathbf\{e\},\-\\mathbf\{s\},c\)\.

The agent generalizes zero\-shot to larger dimensions in this domain as well\. Using the same primitive action space \(MoveUp,MoveDown,Swap,SizeReduce\), the learned policy reduces the Ring\-LWE lattice and recovers the secret polynomial\.

## Appendix EFigures

![Refer to caption](https://arxiv.org/html/2606.15301v1/x7.png)Figure 11:Complexity scaling ofDelta\-Star\. Number of cumulative row operations required to reach the best root\-Hermite factorδ0\\delta\_\{0\}as a function of the lattice dimensiond=2​nd=2n\. Blue circles show the mean across seeds with error bars indicating±\\pmone standard deviation; translucent dots show individual seed outcomes\. The shaded region marks the training dimension \(d=16d\{=\}16\)\. Two scaling models are fit to the empirical means: a sub\-exponentiala⋅exp⁡\(b​d\)a\\cdot\\exp\(b\\sqrt\{d\}\)\(blue dashed;a=2\.21a\{=\}2\.21,b=1\.48b\{=\}1\.48,R2=0\.999R^\{2\}\{=\}0\.999\) and a polynomiala⋅dba\\cdot d^\{b\}\(green dotted;b=5\.58b\{=\}5\.58,R2=0\.999R^\{2\}\{=\}0\.999\)\. Both models achieve comparable coefficients of determination\.### E\.1Analyzing Policy Traces

To characterize the learned strategy beyond aggregate statistics, we mined the top\-kklongest contiguous action subsequences shared across all 100 greedy\-policy trajectories using a generalized suffix\-array algorithm\. The results reveal a strikingly regular two\-phase cycle\. Every trajectory is composed of alternating*descent*and*cascade*phases\. During a descent phase the policy moves the cursor downward through the basis, interleavingMoveDownandSizeReduceactions in an approximate\(D​R\)m\(\\textsc\{D\}\\,\\textsc\{R\}\)^\{m\}pattern; during a cascade phase it executes a burst of consecutiveSwapoperations \(Wn\\textsc\{W\}^\{n\}\) that bubble the current vector toward the top of the basis\. The longest motif present in all 100 trajectories isD​R​D​R​W12\\textsc\{D\}\\,\\textsc\{R\}\\,\\textsc\{D\}\\,\\textsc\{R\}\\,\\textsc\{W\}^\{12\}\(length 16\), capturing the canonical descent\-to\-cascade transition\. The seven longest motifs \(lengths 12–16\) all straddle this phase boundary, confirming that the transition point is the most stereotyped part of the policy\. Shorter motifs \(ℓ≤10\\ell\\leq 10\) include the pure\-descent pattern\(D​R\)5\(\\textsc\{D\}\\,\\textsc\{R\}\)^\{5\}\(756 occurrences\) and the pure\-descent runD7\\textsc\{D\}^\{7\}\(942 occurrences\), the latter corresponding to rapid cursor repositioning without size reduction\. The learned algorithm thus resembles an aggressive deep\-insertion strategy, where the policy first descends to identify a promising vector near the bottom of the basis, then commits to a full swap cascade that inserts it near the top — a pattern closer to deep insertion LLL\[[44](https://arxiv.org/html/2606.15301#bib.bib2)\]than to the standard algorithm, but discovered autonomously by reinforcement learning\.

![Refer to caption](https://arxiv.org/html/2606.15301v1/figures/trace_grid_000.png)Figure 12:Action traces of the learned policy over the first 300 environment steps across multiple q\-ary lattice instances \(n=8n=8,q=251q=251\)\. Each panel shows two rows per instance: a colour\-coded action ribbon \(MoveUp,MoveDown,Swap,SizeReduce\) and the cursor positionkkbefore each action\. The policy exhibits a consistent sweep–reduce–cascade pattern across diverse random seeds\.