🤖 machine learning

Discovering Lattice Reduction Strategies via Self-Play

This paper introduces DeltaStar, a deep reinforcement learning agent trained via self-play that discovers a superior lattice reduction strategy, requiring fewer operations than the classic LLL algorithm and demonstrating zero-shot generalization to higher dimensions and unseen moduli.

Original authors: Mohamed Malhou, Kristin Lauter, Ludovic Perret

Published 2026-06-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mohamed Malhou, Kristin Lauter, Ludovic Perret

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a tangled ball of yarn. Your goal is to untangle it and arrange the strands so they are as straight and short as possible. In the world of mathematics and cryptography, this "yarn" is called a lattice, and the "strands" are vectors. Finding the shortest, straightest arrangement is crucial for keeping digital secrets safe, but it is incredibly difficult to do by hand, especially when the ball of yarn gets huge.

For decades, the standard tool for untangling this yarn has been an algorithm called LLL. Think of LLL as a very strict, rule-following robot. It has two simple moves:

Size Reduction: It pulls a strand tight against the ones before it to remove slack.
Swapping: If a strand looks out of order, it swaps it with the neighbor.

The robot decides when to swap based on a rigid, hand-written rule (the "Lovász condition"). While this rule guarantees the robot will finish its job in a reasonable time, it doesn't always produce the perfectly untangled result. It's like following a map that gets you to the city, but you end up taking a few unnecessary detours.

The New Discovery: "Delta-Star"

The authors of this paper asked a simple question: What if we didn't give the robot a rigid rulebook, but instead taught it how to play the game of untangling on its own?

They built an AI agent named Delta-Star using a technique called Deep Reinforcement Learning. Here is how they did it, using some creative analogies:

1. The Training Ground (The "Small Yarn Ball")

They didn't throw the AI into a massive, impossible knot. Instead, they trained it on small, manageable 8-dimensional lattices (think of a small, 8-strand ball of yarn).

The Game: The AI plays a single-player game where it can only make the same two moves as the old robot (pull tight or swap).
The Goal: The AI gets points for making the yarn shorter and straighter. It loses points if it takes too many steps.
The Teacher: The AI learns by playing against itself millions of times (Self-Play). It tries a move, sees if it helps, and if it doesn't, it forgets that move next time.

2. The "Crystal Ball" Strategy (Adaptive Horizon MCTS)

The most clever part of their system is how the AI thinks ahead.

Standard Thinking: Usually, an AI looks one step ahead, then the next, then the next. This is slow and computationally expensive.
Delta-Star's Thinking: The AI has a "crystal ball" that predicts the next several moves at once.
- If the crystal ball says, "The next 10 moves are obvious and automatic," the AI skips them instantly.
- If the crystal ball says, "Whoa, the next move is a tough choice with many possibilities," the AI stops and thinks deeply about that specific moment.
The Analogy: Imagine driving a car. On a straight, empty highway, you don't need to think about every inch of the road; you just cruise. But when you hit a complex intersection, you slow down and focus. Delta-Star does this automatically, saving energy on the boring parts and focusing on the hard decisions.

3. The Magic Trick: Zero-Shot Generalization

This is the most surprising result. The AI was only trained on small 8-strand yarn balls. It never saw a bigger ball during training.

The Test: The researchers handed the AI a giant 32-strand ball of yarn (a dimension it had never seen before).
The Result: The AI didn't get confused. It immediately figured out how to untangle the giant ball better than the old LLL robot ever could.
The Metaphor: It's like teaching a child to tie their shoes on a pair of tiny baby shoes, and then handing them a pair of adult boots. The child doesn't need a new lesson; they just apply the same logic and do a better job than the adult who has been tying shoes for years.

Why Does This Matter?

The paper claims that Delta-Star produces a "cleaner" untangled lattice than the classical LLL algorithm.

Better Quality: The final arrangement of the yarn is shorter and more efficient.
Fewer Steps: It takes fewer "pulls and swaps" to get there.
No Retraining: It works on sizes it has never seen before.

The Catch

The paper is very clear about one limitation: Speed.
While Delta-Star finds a better solution using fewer mathematical steps, the AI itself is currently slower to run than the old robot. This is because the AI has to run a complex neural network (a giant digital brain) to decide on every single move. The old robot is a simple calculator; the AI is a supercomputer.

The authors aren't saying this AI is ready to replace the old robot in your phone today. Instead, they are saying: "We found a better way to untangle the yarn. Now, we need to figure out how to write down the rules this AI discovered so we can build a simple, fast robot that does the same thing."

In short, they used a super-smart AI to discover a better strategy for a math problem, and that strategy works even on problems the AI was never explicitly taught to solve.

Technical Summary: Discovering Lattice Reduction Strategies via Self-Play

Problem Statement

Lattice reduction is a fundamental problem in computational mathematics and cryptography, underpinning the security of post-quantum cryptographic schemes. The Lenstra-Lenstra-Lovász (LLL) algorithm is the standard polynomial-time method for lattice basis reduction. However, while LLL guarantees a specific runtime and bound on vector lengths, its outputs are often suboptimal in practice, particularly as the lattice dimension increases. The algorithm relies on a handcrafted heuristic, the Lovász condition, to decide when to swap basis vectors. This condition ensures a monotonic decrease in a potential function but is not necessarily optimal for achieving the strongest possible reduction.

The core challenge addressed in this work is whether a data-driven approach can discover a sequencing policy for LLL's primitive operations (size reduction and adjacent swaps) that yields strictly superior reduction quality compared to the classical algorithm, without expanding the action space to include more complex oracles (like exact Shortest Vector Problem solvers).

Methodology: Delta-Star

The authors formulate lattice reduction as a single-player Markov Decision Process (MDP) and employ a Deep Reinforcement Learning (RL) framework augmented with Monte Carlo Tree Search (MCTS).

1. MDP Formulation

State Space: The state includes the current basis matrix $B$ , its Gram-Schmidt orthogonalization (GSO) vectors and coefficients, the cursor position $k$ (indicating the current row being processed), and the remaining steps.
Action Space: The agent is restricted to the exact primitive actions of the LLL algorithm to ensure a fair comparison:
- MOVEUP/MOVEDOWN: Adjusting the cursor position.
- SWAP: Exchanging adjacent basis rows $b_k$ and $b_{k-1}$ .
- SIZEREDUCE: Subtracting integer multiples of previous rows to satisfy the size-reduction condition ( $|\mu_{j,k}| \le 1/2$ ).
Reward Function: A normalized reward is defined based on the relative reduction in the log-metric of quality measures (Orthogonality Defect $\delta$ and LLL Potential $\Phi$ ). A hybrid reward interpolates between these two objectives.

2. Adaptive-Horizon MCTS

The authors introduce a novel Adaptive-Horizon MCTS mechanism to improve search efficiency:

Multi-Step Prediction: The neural network predicts a policy and value for a horizon of $H$ future steps simultaneously.
Entropy-Gated Expansion: Instead of expanding the tree one node at a time, the algorithm traverses the "greedy" path predicted by the network. At each step $k$ $k$ , it computes the Shannon entropy $H[p(k)]$ $H [p (k)]$ of the predicted policy.
- If entropy is low (high confidence), the algorithm automatically traverses the step without branching, amortizing inference costs.
- If entropy exceeds a threshold $\tau$ (indicating a genuine decision point), expansion halts, and the tree branches at that node.
This mechanism allows the search to skip deterministic sequences and focus computational resources on uncertain decision points.

3. Neural Network Architecture

Backbone: A deep Residual Network (ResNet) with a lookback window to capture temporal history.
Observation Tensor: Encodes the basis, GSO, coefficients, time remaining, and cursor position into a 5-channel tensor.
Heads: The network outputs a policy head (probabilities for $H$ steps) and a value head (expected returns for $H$ steps).
Training: The model is trained via AlphaZero-style self-play, minimizing cross-entropy between the predicted policy and MCTS visit counts, and Mean Squared Error between predicted values and episode returns.

4. Training Setup

The agent, named Delta-Star, is trained exclusively on small $q$ -ary lattices with base dimension $n=8$ and modulus $q=251$ . The training utilizes a distributed pipeline with self-play workers, inference servers, and a central learner.

Key Results

1. Superior Reduction Quality

Delta-Star achieves a significantly better root Hermite factor ( $\delta_0$ ) and orthogonality defect than the classical LLL algorithm across various dimensions.

At the training dimension ( $n=8$ ), Delta-Star converges to a slightly lower $\delta_0$ ( $\approx 1.00657$ ) compared to LLL ($1.00660$).
Crucially, the performance gap widens as dimension increases. At $n=32$ , Delta-Star achieves $\delta_0 = 1.0149$ , outperforming LLL ($1.0171$) and approaching the quality of BKZ- $\beta$ ($1.0125$), despite never being trained on dimensions larger than 8.

2. Zero-Shot Generalization

The model demonstrates robust zero-shot generalization:

Dimension: It generalizes to unseen dimensions up to $n=32$ .
Modulus: It generalizes to unseen moduli $q$ in the range of $\sim 20$ to $5000$.
This is achieved through the use of $q$ -normalized observation tensors and adaptive pooling in the network architecture.

3. Algorithmic Efficiency

Delta-Star requires fewer primitive row operations than LLL to reach comparable or better reduction quality.

At $n=8$ , it uses only 55% of the row operations required by LLL.
At higher dimensions ( $n=26, 32$ ), it maintains a strictly better trajectory throughout the reduction process, converging faster and to a better final state.
The authors note that while the neural network inference is slower in wall-clock time than a classical implementation, the reduction in the number of elementary operations indicates a more efficient underlying strategy.

Significance and Claims

The paper claims to demonstrate that deep reinforcement learning can discover strictly superior, generalizable reduction strategies by interacting with the primitive action space of LLL.

Beyond Handcrafted Heuristics: The work shows that the rigid Lovász condition is not optimal and that a learned policy can navigate the state space more effectively.
Scalability: The approach challenges the notion that lattice reduction strategies must be re-engineered for different dimensions, showing that a model trained on small instances can scale to significantly larger, unseen dimensions.
Algorithm Discovery: The authors position this work within the paradigm of AI-driven algorithm discovery (similar to AlphaTensor and AlphaDev), suggesting that fundamental heuristic-driven algorithms in computational mathematics can be optimized by discovering optimal decision paths through RL.
Future Directions: The paper concludes that the learned policy weights encode a deterministic, efficient algorithm. A primary future objective is to extract and formalize this classical algorithm from the neural network. Additionally, the methodology could be extended to improve block-based algorithms like BKZ.

The authors remain modest regarding the current implementation, acknowledging that the neural network is slower per operation than classical code, and emphasize that the value of the work lies in characterizing the structure of a more efficient reduction strategy rather than immediate runtime performance.