Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs¶

会议: NeurIPS 2026
arXiv: 2610.19460
领域: 优化/理论
关键词: 学习增强流算法, 布尔最大约束满足问题, 弱预测预言机, 噪声信道逆解, 空间复杂度下界绕过

一句话总结¶

针对布尔 Max-CSP 在流模型中的空间下界瓶颈，本文提出基于 \(\varepsilon\)-精确预言机的学习增强流算法，通过将弱预测建模为二元对称信道输出并显式高斯消元求逆，在插入流中实现了与变量规模 \(n\) 无关的 \((1-\eta)\)-近似空间复杂度。

研究背景与动机¶

布尔最大约束满足问题（Max-CSPs，涵盖 Max-Cut、Max-Dicut、Max-2AND 与 Max-kAND 等）是组合优化与理论计算的核心基石，其离散标记形式在机器学习结构化预测、CRF 推断以及计算机视觉能量最小化中有着极其广泛的应用。然而，随着海量图与超图数据在流模型（Streaming Model）下持续涌现，算法往往仅被允许单遍（single-pass）扫描约束且工作空间必须严格次线性于输入规模。在无预言机协助的经典计算理论中，以 Chou 等人（FOCS 2020, STOC 2022, JACM 2024）为代表的流复杂度下界构筑了无法逾越的坚固壁垒：对于任意超越特定平凡阈值 \(\alpha\)（如 Max-Dicut 与 Max-2AND 的 \(\alpha=4/9\)）的 \((\alpha+\eta)\)-近似，单遍流算法在动态甚至插入流中均被证明无条件需要 \(\Omega(\sqrt{n})\) 空间；对于更高阶的 Max-kAND，更存在 \(2^{-(k-1)}\) 的不可逼近性。

这一本质困难源于经典信息论与通信复杂度对压缩流实例保真度的硬性约束。近年来蓬勃发展的“学习增强算法”（Learning-augmented algorithms / Algorithms with predictions）为打破传统最坏情况复杂度边界提供了崭新的切入路径。直觉上，由深度神经网络或大语言模型给出的辅助预测往往能提供隐藏最优解的部分侧信息。Dong、Peng 与 Vakilian（ITCS 2025）率先探索了带有独立 \(\varepsilon\)-精确预测（即预言机对每个变量以 \(1/2+\varepsilon\) 概率输出最优赋值、以 \(1/2-\varepsilon\) 概率翻转）的流式 Max-Cut 估算问题，并打破了 Kapralov–Krachun 空间下界。但其算法本质上依赖“预测存活”范式（直接估算预测解诱导割中存活的边数），受限于噪声衰减，天然存在 \(1/2+\Omega(\varepsilon^2)\)（在 Max-Dicut 下更低至 \(1/4+O(\varepsilon)\)）的近似比天花板，无法实现任意接近 1 的常数近似比。

本文切入的角度是：弱预测不应当仅仅被当作候选分配来做“存活过滤”，而应被视为最优解经由二元对称信道（BSC）退化后的带噪编码，其全局统计量的期望蕴含着关于未见最优基数的精确线性系统。核心 idea：将 \(\varepsilon\)-弱预测建模为关于最优分配的带噪线性信道，通过设计度数自适应阈值解耦顶点协方差，在低度子图上构造全秩线性方程组并显式求逆解码无偏统计量，结合高保真草图（CountMin 与 \(\ell_0\)-采样）以完全独立于 \(n\)（或仅对数依赖）的紧凑空间实现任意 \(\eta>0\) 的 \((1-\eta)\)-近似。

方法详解¶

整体框架¶

本文算法的整体逻辑旨在针对由流式到达的约束构成的实例 \(\Psi\)，输出其最优满足值 \(\mathrm{OPT}\) 的 \((1-\eta)\)-近似估计。为了克服变量共享所带来的高协方差与方差爆炸问题，算法首先基于约束度数将变量集合划分为低度变量子集与高度变量子集，分别设计不同的统计捕获机制，最后经由显式求逆合并估算。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["流式输入约束序列<br/>插入流 / 动态增删流"] --> B["度数自适应分解<br/>蓄水池 / l0-采样捕获候选高度变量集合 H"]
    B --> C["双轨统计量流式捕获<br/>全局预测边型计数器 + 四路 CountMin 关联草图"]
    C --> D["线性系统显式信道求逆解码<br/>高斯消元还原低度子图无偏最优统计量"]
    D --> E["高度变量贪心边界收益整合<br/>消除跨子图残差并执行多项式松弛校准"]
    E --> F["输出 (1-eta)-近似最优值"]

在插入流中，算法先通过紧凑的蓄水池抽样（Reservoir Sampling）捕捉高频出现的目标，动态提取出规模仅由 \(\mathrm{poly}(1/\varepsilon, 1/\delta, 1/\eta)\) 决定的候选高度变量集合 \(\widetilde{H}\)，其余变量构成低度子集 \(\widetilde{L}\)；在动态流中则通过多路并行的 \(\ell_0\)-采样器（\(\ell_0\)-sampler）完成相同候选集提取。流处理过程中并行维护全局关于预测分配下不同满足模式的频次统计量，以及由四个定向 CountMin 草图记录的每个变量跨预测正负极的关联频次。流扫描结束后，利用高斯消元反解由噪声信道诱导的全秩线性系统，还原低度子图中真正被最优解满足的边数，同时为高度顶点逐一贪心地指派局部最优符号贡献，最终合成全局目标估计值。

关键设计¶

1. 噪声信道显式高斯消元求逆：突破预测存活范式的近似比天花板

以往学习增强流算法直接计算预测向量 \(\mathbf{Y}\) 诱导的目标值，例如对于 Max-Dicut 仅统计 \((Y_u=1, Y_v=-1)\) 的边数。因为每条真实最优割边以 \((1/2+\varepsilon)(1/2+\varepsilon) \approx 1/4+\varepsilon\) 的低概率存活，此类方法天然受制于 \(1/4+O(\varepsilon)\) 近似障碍。针对该痛点，本文观察到每条边在预测标记下的三种可能状态（正向跨越、同侧内部、反向跨越）所对应的计数值期望向量 \((\mathbb{E}[X_0], \mathbb{E}[X_1], \mathbb{E}[X_2])^T\)，是由真实最优割的三类未知边数 \((k_0, k_1, k_2)^T\) 经由纯依赖于 \(\varepsilon\) 的转移矩阵所映射生成的全秩线性系统。以 Max-2AND 为例，设真实满足两文字的边数为 \(k_0\)，满足恰好一文字的为 \(k_1\)，两文字均不满足的为 \(k_2\)。通过分析独立噪声信道的二项分布概率，转移矩阵显式可逆，由此通过精确高斯消元构建出无偏解码估计量：

\[\widetilde{k}_L = \frac{1}{4\varepsilon^2}\left[\left(\frac{1}{2}+\varepsilon\right)^2 X_0 - \left(\frac{1}{2}+\varepsilon\right)\left(\frac{1}{2}-\varepsilon\right) X_1 + \left(\frac{1}{2}-\varepsilon\right)^2 X_2\right]\]

该解码器使得 \(\mathbb{E}[\widetilde{k}_L] = k_0 = k_L\) 严格成立，彻底摆脱了利用存活比例硬逼近最优值的固有损失，为任意精度 \((1-\eta)\) 逼近提供了数学根基。

2. 度数自适应解耦与协方差收敛机制：控制多边共享顶点的方差爆炸

尽管线性反解得到的解码统计量是无偏的，但流中各约束因共享变量而呈现复杂的统计相关性；若图中存在度数极高的枢纽变量，一个预测变量 \(Y_v\) 的波动将引发数万条边满足指示变量的联动晃动，导致 Chebyshev 不等式下的方差上界激增至失控。为此，本文设计了度数门限切分准则，选定度数门限 \(\theta m = \Theta(\varepsilon^4 \delta \eta^2) m\)，将全部变量解耦为低度变量集 \(L\) 与高度变量集 \(H\)。

对于低度子集 \(L\) 内部的任意约束，每个顶点至多连接 \(\theta m\) 条约束，两两约束共享端点的重叠项总数被严格控制在 \(m_L \cdot 2\theta m\) 以内，从而将示性变量和的方差紧紧约束为 \(\mathrm{Var}[X_i] \le 2\theta m^2\)。应用 Chebyshev 不等式即可保证低度子图内的解码估计量误差在概率 \(1-\delta/6\) 下不超过 \(\varepsilon^2 \eta m / 8\)。另一方面，高度变量集因其每个成员度数均大于等于 \(\theta m\)，总变量数天然受限为 \(|H| \le 2m/(\theta m) = 2/\theta = O(\varepsilon^{-4}\delta^{-1}\eta^{-2})\)。其子图内部全高阶约束总数不超过 \(|H|^2 = O(\varepsilon^{-8}\delta^{-2}\eta^{-4})\)，在流规模满足 \(m = \Omega(\varepsilon^{-26}\delta^{-10}\eta^{-14})\) 时对最终估计值的相对误差影响可完全被吸收进松弛项中。

3. 双轨草图模拟与自适应贪心赋值：单遍流下的盲区还原与全局合成

在真实的流模型下，算法无法预知各变量的度数分布，因而无法在流的开始预先划定 \(L\) 与 \(H\)。为实现纯单遍流处理，本文设计了双轨统计机制：一方面维持大小为 \(O(\beta/(\varepsilon^8 \delta^3 \eta^4))\) 的蓄水池采样集（在动态流中则为并行独立 \(\ell_0\)-采样器阵列），以在流结束时以 \(1-\delta/8\) 的极高概率捕获所有真正度数超标的高度变量，形成候选集 \(\widetilde{H}\)；另一方面维持四组带有精度参数 \(\varepsilon^{10}\delta^5\eta^6/(128\beta)\) 的 CountMin 草图，流式记录每个变量与预测符号 \(+1/-1\) 之间的出入度频次。

流结束并确定 \(\widetilde{H}\) 后，算法通过容斥原理从全局边计数中扣除所有与 \(\widetilde{H}\) 发生关联的投影统计量，精确模拟出诱导低度子集 \(\widetilde{L}\) 的计数 \((\overline{X}_0, \overline{X}_1, \overline{X}_2)\)，继而解码出 \(\overline{k}_{\widetilde{L}}\)。对于高度变量 \(i \in \widetilde{H}\)，算法通过解析 CountMin 草图估算其在最优解赋值为正或负时所能带来的最大满足边数 \(\max\{\overline{k}_{i,\widetilde{L}(+)}^{\mathrm{pos}}, \overline{k}_{i,\widetilde{L}(+)}^{\mathrm{neg}}\}\)，并执行贪心叠加。最后，引入全局修正偏差 \(-\frac{\eta m}{16}\)，利用多项式松弛巧妙平衡 CountMin 点查询与蓄水池漏检的微小单侧上溢，确保最终输出值 \(\mathrm{ALG}\) 严格满足 \((1-\eta)\mathrm{OPT} \le \mathrm{ALG} \le \mathrm{OPT}\)。

4. 高阶超图动态门限演进与黑盒规范规约：拓展至任意布尔 Max-kCSP

当约束阶数扩展至 \(k \ge 3\) 时，低度约束内部多文字联合概率的反解矩阵规模剧增，且高度变量之间的交叉作用无法用简单的单点贪心解耦。为此，本文针对无界度 Max-kAND 引入了动态演进门限：当当前集合已有 \(|H|\) 个元素时，仅当候选变量度数超过 \(\frac{\theta m}{|H|+1}\) 时才将其并入。基于调和级数发散性质 \(\sum_{s=1}^{|H|} \frac{1}{s} \le \frac{km}{\theta m} = \frac{k}{\theta}\)，严格证明了 \(|H|\) 的规模上限仍被牢固限制在 \(\exp(O(k^2 \varepsilon^{-2k}\eta^{-2}\log(1/\delta)))\) 以内。

由于剩余低度变量在任意子集规模下的影响力被 \((|H|+1)^{-1}\) 严格压制，结合 McDiarmid 有界差分不等式，使得所有针对 \(H\) 的 \(2^{|H|}\) 种可能符号分配下的解码多项式能够进行一致收敛的联合界控制。最后，利用布尔函数的规范析取标准型，将任意布尔谓词 \(f: \{-1,1\}^k \to \{0,1\}\) 分解为至多 \(2^k\) 个相互互斥的合取子项，构建出保留最优解且约束数至多膨胀 \(2^k\) 倍的黑盒归约映射，将全部流式算法完备推广至通用的任意布尔 Max-kCSP。

实验关键数据¶

主实验¶

论文通过严格的理论数学分析与算法复杂度证明确立了主定理成果。下表系统对比了在具有 \(\varepsilon\)-精确预言机辅助下，本算法与经典流算法及既有学习增强流算法在近似比和空间复杂度上的理论性能：

问题类型	算法范式 / 文献来源	近似比保证 (\(\alpha\))	插入流空间复杂度 (Words)	动态流空间复杂度 (Bits)
Max-Cut	经典流下界 (Kapralov 2019)	\(\le 1/2 + \eta\)	\(\Omega(n)\)	\(\Omega(n)\)
Max-Cut	经典次线性 (Goemans-Williamson流)	\(1/2\) (平凡随机割)	\(O(1)\)	\(O(\log n)\)
Max-Cut	学习增强 (Dong et al. ITCS 2025)	\(1/2 + \Omega(\varepsilon^2)\)	\(\mathrm{poly}(1/\varepsilon)\)	\(\mathrm{poly}(1/\varepsilon) \log n\)
Max-Cut (本文)	学习增强信道逆解 (本文)	\(1 - \eta\) (任意 \(\eta>0\))	\(O\left(\frac{1}{\varepsilon^{10}\delta^5\eta^6}\log\frac{1}{\varepsilon\delta\eta}\right)\)	\(O\left(\frac{\log^2 n}{\varepsilon^{10}\delta^5\eta^6}\log\frac{1}{\varepsilon\delta\eta}\right)\)
Max-Dicut	经典确定性单遍 (Chou et al. 2020)	\(4/9 - \eta \approx 0.444\)	\(O(\log n)\)	\(O(\log n)\)
Max-Dicut	经典随机单遍 (Azarmehr et al. 2026)	\(1/2 - \eta = 0.500\)	\(n^{1-o(1)}\)	\(n^{1-o(1)}\)
Max-Dicut	预测存活基线 (直接沿用 ITCS 2025)	\(1/4 + O(\varepsilon)\)	\(\mathrm{poly}(1/\varepsilon)\)	\(\mathrm{poly}(1/\varepsilon, \log n)\)
Max-Dicut (本文)	学习增强信道逆解 (本文)	\(1 - \eta\) (任意 \(\eta>0\))	\(O\left(\frac{1}{\varepsilon^{10}\delta^5\eta^6}\log\frac{1}{\varepsilon\delta\eta}\right)\)	\(O\left(\frac{\log^2 n}{\varepsilon^{10}\delta^5\eta^6}\log\frac{1}{\varepsilon\delta\eta}\right)\)
Max-2AND	经典流下界 (Chou et al. FOCS 2020)	\(> 4/9\) 时不可行	\(\Omega(\sqrt{n})\)	\(\Omega(\sqrt{n})\)
Max-2AND (本文)	学习增强信道逆解 (本文)	\(1 - \eta\) (任意 \(\eta>0\))	\(O\left(\frac{1}{\varepsilon^{10}\delta^5\eta^6}\log\frac{1}{\varepsilon\delta\eta}\right)\)	\(O\left(\frac{\log^2 n}{\varepsilon^{10}\delta^5\eta^6}\log\frac{1}{\varepsilon\delta\eta}\right)\)
Max-kAND (\(k \ge 3\))	经典流下界 (Chou et al. STOC 2022)	\(> 2^{-(k-1)}\) 时不可行	\(\Omega(n)\)	\(\Omega(n)\)
Max-kAND (\(k \ge 3\))	学习增强信道逆解 (本文)	\(1 - \eta\) (任意 \(\eta>0\))	\(\exp(\mathrm{poly}(k, \varepsilon^{-k}, \eta^{-1}, \log\delta^{-1}))\)	\(\exp(\mathrm{poly}(k, \varepsilon^{-k}, \eta^{-1}, \log\delta^{-1})) \log n\)

消融与鲁棒性分析¶

针对各核心算法组件的作用以及关键参数预设的敏感性，本文在附录与理论章节中进行了深入的消融与参数扰动推演：

配置 / 理论消融设定	近似比保证	空间复杂度主导阶	失败概率与理论结论
基准全算法 (Max-2AND 插入流)	\(1 - \eta\)	\(O(\varepsilon^{-10}\delta^{-5}\eta^{-6}\log(\varepsilon\delta\eta)^{-1})\)	失败概率 \(\le \delta\)，完备兼顾两端点误差抵消
移除度数解耦 (无高度集 \(H\))	无法保证 (方差发散)	\(O(1)\)	当存在度数 \(\Omega(m)\) 的稠密星型点时，Chebyshev 失败概率趋于 1
移除 CountMin (退化为精确计数)	\(1 - \eta\)	\(O(n \log m)\)	违背流空间亚线性约束，退化为离线算法
预测精度参数微扰 \(\varepsilon' = (1 \pm \frac{\eta}{256})\varepsilon\)	\(1 - \eta\)	同基准 (常数调整 \(\theta\) 分母至 3072)	鲁棒：高斯消元分母微扰误差受控，近似比依然严格成立
有界度约束特例 (\(\Delta < \frac{\varepsilon^{2k}\delta\eta^2 m}{4k(k+1)}\))	\(1 - \eta\)	\(O(k)\) words	无需显式高度集与草图，仅需 \(k+1\) 个计数器即实现解码

关键发现¶

彻底击碎下界瓶颈：经典单遍流计算中，Max-Dicut 与 Max-2AND 在 \(4/9\) 处存在严格的信息论空间下界 \(\Omega(\sqrt{n})\)。本文证明只要预测质量仅比完全随机猜测好一点点（\(\varepsilon > 0\) 哪怕任意微小），便能以仅与 \(\varepsilon\) 和目标精度 \(\eta\) 相关的常数空间（完全独立于问题规模 \(n\)）实现任意接近 1 的逼近比。
高阶 CSP 的复杂度代价：当约束元数从 \(k=2\) 跨越至 \(k \ge 3\) 时，由于不能再通过简单的出入度二分图做单点贪心解耦，空间复杂度由多项式阶跃迁为指数阶 \(\exp(\mathrm{poly}(k, 1/\varepsilon^k, 1/\eta, \log(1/\delta)))\)，但其对于变量数 \(n\) 的绝佳独立性（插入流）或多对数依赖（动态流）依然保持成立。
预言机参数鲁棒性要求：相较于 Dong 等人（ITCS 2025）针对 Max-Cut 仅需 \(\varepsilon\) 的常数因子估计，本文由于采用了精确高斯消元逆解线性方程，消元系数包含 \(1/\varepsilon^2\) 项，因此要求预言机先验参数 \(\varepsilon\) 具有相对精度 \((1 \pm O(\eta))\varepsilon\)；理论推导证明该估算误差不会破坏最终的主定理界。

亮点与洞察¶

从“统计存活”到“信道求逆”的方法论跃迁：此前学习增强流算法往往把弱预测当作次优解来度量残余，而本文将其视作经典通信模型中的有噪信道传输。借助预言机误差的独立性，直接建立统计可观测量与最优未观测量之间的全秩线性方程，实现了无偏解码这一极具通识启发性的架构创新。
高度顶点贪心解耦的“不可实现”解码器巧思：算法最终产出的估算值并非来自某个在流中显式物化出的真实割划分（在次线性甚至常数空间下根本无法存储 \(n\) 维变量赋值），而是纯粹由低度子图求逆估计量与高度顶点的边际最大收益拼接而成的虚拟数学代数解。这一设计展示了流式估值与流式构造之间的精妙理论解耦。
调和级数门限截断法控制组合爆炸：在处理高阶 Max-kAND 时，利用阶梯下降阈值 \(\theta m / (|H|+1)\)，巧妙借助调和级数的对数增长严格封顶高度集元素个数，从而控制了 \(2^{|H|}\) 种枚举状态下的联合界失效风险，这一技巧对超图流式谱稀疏化具有重要借鉴价值。

局限与展望¶

对预测精度的先验依赖偏严苛：算法要求预先已知 \(\varepsilon\) 或其高精度近似估计 \(\varepsilon' = (1 \pm O(\eta))\varepsilon\)。在实际机器学习部署场景中，模型预测的不确定性往往是空间异质的且难以预先标定。探索能够在无需预知精确 \(\varepsilon\) 的前提下自适应拟合误差分布的盲学习增强流算法是一个关键开放课题。
高阶 CSP 的空间常数随 \(k\) 双重指数膨胀：对于 \(k \ge 3\) 的 Max-kCSP，空间复杂度中的指数项包含了 \(1/\varepsilon^k\) 与 \(1/\eta\)，在低偏差高精度场景下常数极其庞大。未来工作亟需研究是否存在更加精细的多多项式核化技术，将 \(k \ge 3\) 时的空间复杂度压缩至 \(\mathrm{poly}(1/\varepsilon, 1/\eta)\)。
字母表规模局限在布尔域：当前技术高度依赖二元变量下的对称二项分布信道求逆。如何将这一信道逆解框架推广至具有任意 \(q\) 阶有限域字母表（如一般图多着色、Unique Games 等）的通用 CSP，依然悬而未决。

评分¶

新颖性: ⭐⭐⭐⭐⭐ [颠覆传统预测存活路径，首创基于噪声信道高斯消元求逆的流式无偏解码范式]
理论深度: ⭐⭐⭐⭐⭐ [数学推导严丝合缝，巧妙结合方差解耦、调和级数高度集控制、CountMin/\(\ell_0\)-采样与鲁棒微扰分析]
写作质量: ⭐⭐⭐⭐⭐ [结构层层递进，从 Max-Dicut 启发直觉自然拓展至 Max-2AND 及通用高阶 CSP，逻辑清晰完备]
价值: ⭐⭐⭐⭐⭐ [圆满解决了学习增强流算法在布尔约束满足领域的近似比极限问题，对次线性算法理论具有深远指导意义]