arXiv:2507.23186cs.LGcs.PL2025-07

用NaN污染检测黑箱函数稀疏性,避免误判,提速超1.5倍。

NaN-Propagation: A Novel Method for Sparsity Detection in Black-Box Computational Functions

  • 通过输入注入NaN追踪输出依赖,重建保守稀疏模式。
  • 在机翼重量模型中实现1.52倍加速,发现数十个传统方法遗漏的依赖。
  • 无需修改代码,兼容多语言,适合工程优化中的梯度计算瓶颈场景。

数值计算函数梯度时,稀疏性检测可通过雅可比着色与压缩显著提升计算效率。然而,针对黑箱函数的稀疏性检测方法有限,现有基于有限差分的方法因偶然零梯度产生大量假阴性,可能无声地破坏梯度计算,导致难以排查的错误。本文提出NaN-propagation,利用IEEE 754标准中NaN的通用污染特性,在浮点数运算中追踪输入-输出依赖关系。通过系统性地将输入替换为NaN,观察哪些输出变为NaN,该方法重构出保守的稀疏模式,有效消除主要的假阴性来源。我们在一个航空航天机翼重量模型上验证了该方法,实现了1.52倍的速度提升,并发现了数十个传统方法遗漏的依赖关系——这对常以梯度计算为瓶颈的优化流程具有显著实际价值。该技术依托于对IEEE 754的合规性,可在不修改现有黑箱代码的前提下跨编程语言和数学库使用。此外,通过直接位操作编码NaN载荷等高级策略,可实现优于线性的时间复杂度,进一步提升效率;同时提出了实用算法,以应对工程应用中常见的分支执行挑战。

原文摘要 · Abstract (English)

When numerically evaluating a function's gradient, sparsity detection can enable substantial computational speedups through Jacobian coloring and compression. However, sparsity detection techniques for black-box functions are limited, and existing finite-difference-based methods suffer from false negatives due to coincidental zero gradients. These false negatives can silently corrupt gradient calculations, leading to difficult-to-diagnose errors. We introduce NaN-propagation, which exploits the universal contamination property of IEEE 754 Not-a-Number values to trace input-output dependencies through floating-point numerical computations. By systematically contaminating inputs with NaN and observing which outputs become NaN, the method reconstructs conservative sparsity patterns that eliminate a major source of false negatives. We demonstrate this approach on an aerospace wing weight model, achieving a 1.52x speedup while uncovering dozens of dependencies missed by conventional methods -- a significant practical improvement since gradient computation is often the bottleneck in optimization workflows. The technique leverages IEEE 754 compliance to work across programming languages and math libraries without requiring modifications to existing black-box codes. Furthermore, advanced strategies such as NaN payload encoding via direct bit manipulation enable faster-than-linear time complexity, yielding speed improvements over existing black-box sparsity detection methods. Practical algorithms are also proposed to mitigate challenges from branching code execution common in engineering applications.

稀疏性检测黑箱函数梯度加速数值计算

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。