🤖 machine learning

Discovering Lattice Reduction Strategies via Self-Play

本文介绍了 DeltaStar，一种通过自我博弈训练的深度强化学习智能体，它发现了一种优于经典 LLL 算法的格还原策略，该策略所需的运算次数更少，并展示了向更高维数和未知模数的零样本泛化能力。

原作者： Mohamed Malhou, Kristin Lauter, Ludovic Perret

发布于 2026-06-16

📖 1 分钟阅读☕ 轻松阅读

原作者： Mohamed Malhou, Kristin Lauter, Ludovic Perret

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你有一个缠绕在一起的毛线球。你的目标是解开它，并将这些线条排列得尽可能直且短。在数学和密码学领域，这个“毛线”被称为格（lattice），而“线条”则是向量（vectors）。寻找最短、最直的排列方式对于保护数字秘密至关重要，但当这个毛线球变得巨大时，手动完成这项工作是极其困难的。

几十年来，解开这个毛线的标准工具是一种叫做 LLL 的算法。你可以把 LLL 想象成一个非常刻板、循规蹈矩的机器人。它有两个简单的动作：

尺寸规约（Size Reduction）： 它将一条线拉紧，使其贴合之前的线条，从而消除松弛。
交换（Swapping）： 如果某条线看起来顺序不对，它就会将其与相邻的线进行交换。

机器人根据一个僵化的、手写的规则（“Lovász 条件”）来决定何时进行交换。虽然这个规则保证了机器人能在合理的时间内完成任务，但它并不总是能产生最完美的解开结果。这就像是拿着一张地图带你到达城市，但你可能会绕了一些不必要的远路。

新发现：“Delta-Star”

论文的作者提出了一个简单的问题：如果我们不再给机器人一本死板的规则书，而是教它如何通过自主学习来玩这个解开毛线的游戏会怎样？

他们利用一种叫做**深度强化学习（Deep Reinforcement Learning）**的技术，构建了一个名为 Delta-Star 的 AI 智能体。以下是他们如何实现这一目标的，其中使用了一些富有创意的类比：

1. 训练场（“小毛线球”）

他们并没有把 AI 直接扔进一个巨大的、无法处理的乱团中。相反，他们在小型、易于处理的 8 维格（可以理解为一个只有 8 根线条的小毛线球）上对其进行训练。

游戏规则： AI 玩的是一个单人游戏，它只能进行与旧机器人相同的两个动作（拉紧或交换）。
目标： AI 通过让毛线变得更短、更直来获得分数。如果它走的步骤过多，则会扣分。
老师： AI 通过与自己进行数百万次的自我博弈（Self-Play）来学习。它尝试一个动作，观察是否有帮助；如果没有帮助，下次就会忘记这个动作。

2. “水晶球”策略（自适应视界 MCTS）

他们系统中最聪明的部分在于 AI 如何思考未来。

常规思维： 通常情况下，AI 会看一步，再看下一步，接着再看下一步。这种方式速度慢且计算成本高。
Delta-Star 的思维： AI 有一个“水晶球”，可以同时预测接下来的好几步。
- 如果水晶球说：“接下来的 10 步是显而易见且自动完成的，”AI 就会立即跳过它们。
- 如果水晶球说：“哇，接下来的这一步是一个有很多种可能性的艰难抉择，”AI 就会停下来，针对那个特定的时刻进行深度思考。
类比： 想象你在开车。在笔直、空旷的高速公路上，你不需要思考每一寸路面，只需巡航即可。但当你遇到复杂的交叉路口时，你会减速并集中注意力。Delta-Star 会自动执行这种操作，在无聊的部分节省精力，而在关键决策处集中精力。

3. 魔法技巧：零样本泛化（Zero-Shot Generalization）

这是最令人惊讶的结果。该 AI 仅在小型 8 根线条的毛线球上接受过训练。它在训练期间从未见过更大的毛线球。

测试： 研究人员交给 AI 一个巨大的 32 根线条的毛线球（一个它从未见过的维度）。
结果： AI 并没有感到困惑。它立即找到了比旧的 LLL 机器人更好的解开方法。
隐喻： 这就像教一个孩子在小小婴儿鞋上系鞋带，然后递给他一双成年人的靴子。孩子不需要新的课程；他只需要应用同样的逻辑，并且做得比那位系了多年鞋带的成年人还要好。

这为什么重要？

论文声称 Delta-Star 比经典的 LLL 算法能产生一个更“干净”的解开后的格。

质量更好： 最终的排列更加短小且高效。
步骤更少： 它需要更少的“拉紧和交换”动作才能到达终点。
无需重新训练： 它可以在它从未见过的规模上运行。

局限性

论文非常明确地指出了一项限制：速度。
虽然 Delta-Star 使用更少的数学步骤找到了一个更好的解决方案，但 AI 本身的运行速度目前比旧的机器人要慢。这是因为 AI 需要运行一个复杂的神经网络（一个巨大的数字大脑）来决定每一个动作。旧的机器人是一个简单的计算器；而 AI 是一个超级计算机。

作者并不是说这个 AI 现在就可以取代你手机里的旧机器人。相反，他们是在说：“我们发现了一种更好的解开毛线的方法。现在，我们需要研究如何将这个 AI 发现的规则记录下来，以便我们可以制造出一个简单、快速的机器人，去执行同样的操作。”

简而言之，他们利用一个超级聪明的 AI 来为一个数学问题发现更好的策略，而且这个策略即使在 AI 未经明确教授的情况下，也能解决更大规模的问题。

技术摘要：通过自我博弈发现格规约策略

问题陈述

格规约（Lattice reduction）是计算数学和密码学中的一个基础问题，支撑着后量子密码方案的安全性。Lenstra-Lenstra-Lovász (LLL) 算法是标准的多项式时间格规约方法。然而，尽管 LLL 保证了特定的运行时间并提供了向量长度的上界，但其输出在实际应用中往往并非最优，尤其是在格维度增加时。该算法依赖于一种手工设计的启发式规则——Lovász 条件，来决定何时交换基向量。该条件确保了势函数（potential function）的单调递减，但对于实现最强的规约效果而言，它未必是最优的。

本研究解决的核心挑战在于：能否通过数据驱动的方法，发现一种 LLL 原语操作（尺寸规约与相邻交换）的序列化策略，从而在不扩展动作空间以包含更复杂的预言机（如精确的短向量问题求解器）的情况下，获得比经典算法严格更优的规约质量。

方法论：Delta-Star

作者将格规约建模为单人马尔可夫决策过程 (MDP)，并采用了一种增强了蒙特卡洛树搜索 (MCTS) 的深度强化学习 (RL) 框架。

1. MDP 形式化

状态空间： 状态包括当前的基矩阵 $B$ 、其 Gram-Schmidt 正交化 (GSO) 向量及其系数、游标位置 $k$ （指示当前正在处理的行）以及剩余步数。
动作空间： 为了确保公平比较，智能体被限制在 LLL 算法的精确原语动作内：
- MOVEUP/MOVEDOWN： 调整游标位置。
- SWAP： 交换相邻的基行 $b_k$ 和 $b_{k-1}$ 。
- SIZEREDUCE： 通过减去前序行的整数倍来满足尺寸规约条件（ $|\mu_{j,k}| \le 1/2$ ）。
奖励函数： 基于质量度量（正交缺陷 $\delta$ 和 LLL 势函数 $\Phi$ ）的对数度量的相对规约量，定义了一个归一化的奖励。一种混合奖励在平衡这两个目标之间进行了插值。

2. 自适应时界 MCTS (Adaptive-Horizon MCTS)

作者引入了一种全新的 自适应时界 MCTS 机制以提高搜索效率：

多步预测： 神经网络同时预测未来 $H$ 个步骤的策略和价值。
熵门控扩展 (Entropy-Gated Expansion)： 算法并非逐个节点扩展树，而是沿着网络预测的“贪婪”路径进行遍历。在每一步 $k$ $k$ ，计算预测策略的香农熵 $H[p(k)]$ $H [p (k)]$ 。
- 如果熵较低（置信度高），算法会自动遍历该步骤而不进行分支，从而摊销推理成本。
- 如果熵超过阈值 $\tau$ （表明存在真正的决策点），则停止扩展，并在该节点处进行树分支。
该机制允许搜索跳过确定性序列，并将计算资源集中在不确定的决策点上。

3. 神经网络架构

骨干网络： 具有回溯窗口（lookback window）的深度残差网络 (ResNet)，用以捕捉时间历史。
观测张量： 将基、GSO、系数、剩余时间及游标位置编码为一个 5 通道的张量。
头部 (Heads)： 网络输出一个策略头（预测 $H$ 步的概率分布）和一个价值头（预测 $H$ 步的预期回报）。
训练： 模型通过类 AlphaZero 的自我博弈进行训练，最小化预测策略与 MCTS 访问计数之间的交叉熵，以及预测价值与回合回报之间的均方误差。

4. 训练设置

名为 Delta-Star 的智能体完全在小型 $q$ -ary 格上进行训练，其基维度 $n=8$ ，模数 $q=251$ 。训练利用了一个包含自我博弈工作者、推理服务器和中央学习器的分布式流水线。

关键结果

1. 更优的规约质量

在各种维度下，Delta-Star 实现了比经典 LLL 算法显著更好的 根 Hermite 因子 ( $\delta_0$ ) 和 正交缺陷。

在训练维度（ $n=8$ ）下，Delta-Star 收敛到的 $\delta_0$ （ $\approx 1.00657$ ）略低于 LLL（$1.00660$）。
至关重要的是，随着维度的增加，性能差距进一步扩大。在 $n=32$ 时，Delta-Star 的 $\delta_0$ 达到 $1.0149$，优于 LLL（$1.0171$），并接近 BKZ- $\beta$ 的质量（$1.0125$），尽管它从未在大于 8 的维度上进行过训练。

2. 零样本泛化 (Zero-Shot Generalization)

该模型展示了强大的 零样本泛化能力：

维度： 它能泛化到未见过的维度，最高达 $n=32$ 。
模数： 它能泛化到范围在 $\sim 20$ 至 $5000 $之间的未见模数$ q$。
这通过使用 $q$ 归一化的观测张量和网络架构中的自适应池化技术得以实现。

3. 算法效率

Delta-Star 实现同等或更优规约质量所需的 原语行操作次数 比 LLL 更少。

在 $n=8$ 时，它仅使用了 LLL 所需行操作次数的 55%。
在更高维度（ $n=26, 32$ ）下，它在整个规约过程中始终保持着更优的轨迹，收敛更快且最终状态更好。
作者指出，虽然神经网络的推理在墙钟时间（wall-clock time）上比经典实现慢，但基础操作数量的减少表明其底层策略更为高效。

意义与主张

本文声称证明了深度强化学习可以通过与 LLL 的原语动作空间交互，发现 严格优越且具有泛化能力的规约策略。

超越手工启发式： 本研究表明，僵化的 Lovász 条件并非最优，学习到的策略可以更有效地导航状态空间。
可扩展性： 该方法挑战了格规约策略必须针对不同维度进行重新设计的观点，证明了在小型实例上训练的模型可以扩展到显著更大的未见维度。
算法发现： 作者将这项工作置于 AI 驱动算法发现（类似于 AlphaTensor 和 AlphaDev）的范式之内，暗示基础的启发式驱动算法可以通过强化学习发现最优决策路径来进行优化。

论文最后指出，学习到的策略权重编码了一个确定性的、高效的算法。一个主要的未来目标是从神经网络中提取并形式化这个经典的算法。此外，该方法论也可以扩展以改进像 BKZ 这样的基于块（block-based）的算法。

作者对目前的实现保持谦逊，承认神经网络在单次操作上的速度慢于经典代码，并强调这项工作的价值在于表征一种更高效规约策略的结构，而非仅仅是即时的运行性能。