用扩散模型提升约束求解，高维系统中表现更优
When Do Learned Diffusion Proposals Help Constraint Solving? A Controlled Study on Continuous Algebraic Systems
- 用图神经网络扩散去噪生成候选解，再用代数方法精修验证
- 高维系统下学习型方案优于随机重启，低维或耦合变量时失效
- 在机器人、优化等真实系统中，传统多起点搜索已全覆盖
求解连续代数约束系统需决定满足约束的取值及结构增强方式。经典求解器对前者表现良好，后者仅靠枚举。基于候选条件的修复排序器在仅调用少量增广方案时即达到穷举上限，准确率0.997（远超随机0.236，p<10^-70），且在跨种子测试中稳定达0.982±0.006。MARC将系统转为因子图，由图神经扩散去噪器提出赋值，精确代数能量下降精修，符号检查器认证解。评估中引入关键对照：同预算下的随机多起点启动。结果表明，学习型提案在取值决策上仅在高维未耦合情形下略胜于随机重启；一旦变量耦合，优势消失。所有方法共享同一精修与验证模块，最佳单次随机重启的成功概率为1-(1-q(n))^K，其中q(n)为单起点可达率，该公式无自由参数即可精准复现曲线（平均绝对误差0.012）。该有利区间非仅限于合成数据，在机器人、定位、优化、代数等8个真实系统中，经典多起点均解决全部问题，无一处于学习优势区。论文揭示了学习型提案在哪些条件下能真正提升求解器。
原文摘要 · Abstract (English)
Solving a continuous algebraic constraint system requires two decisions: which values satisfy the constraints, and which structural augmentation renders an unsolvable system solvable. Classical solvers answer the first well and the second only by enumeration. On that discrete decision, a candidate-conditioned repair ranker choosing among K augmentations reaches the exhaustive-search ceiling at a fraction of the calls, outperforming random (0.997 vs 0.236 balanced nonlinear menu accuracy; p < 10^-70; 0.982 +/- 0.006 across seeds) and beating a budget-matched per-candidate probe on accuracy and cost. MARC turns such a system into a factor graph, over which a graph-neural diffusion denoiser proposes assignments, descent on an exact computer-algebra energy polishes them, and an exact symbolic checker certifies solutions. Evaluations of diffusion-based proposals rarely include one control: random multi-start under the same refinement budget. Applied to our system, it sharply curtails what the learned proposal contributes on the value decision. Does it beat random multi-start at choosing satisfying assignments? Only narrowly, in a predictable regime. Across trapped low-dimensional families it ties with random restart, but dominates in high dimension, where random search fails. Once variables couple, the advantage is gone. Since all methods share one polish and one checker, best-of-K random multi-start succeeds with probability exactly 1 - (1 - q(n))^K, where q(n) is single-start reachability; one measured constant, with no free parameters, reproduces the entire curve (mean absolute error 0.012). The favorable regime is not specific to our synthetic families: across eight real-world systems in robotics, positioning, optimization, and algebra, classical multi-start solved all eight, none in the learning-favorable regime. We map the regimes in which learned proposals improve solvers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。