标题： 可预测性使非线性状态空间模型的并行化成为可能 显示英文标题

标题： Predictability Enables Parallelization of Nonlinear State Space Models

摘要： 并行计算硬件的兴起使得理解哪些非线性状态空间模型可以高效并行化变得越来越重要。最近的进展如DEER（arXiv:2309.12252）或DeepPCR（arXiv:2309.16318）表明，评估一个状态空间模型可以重新表述为一个可并行化的优化问题，有时这种方法可以在评估时间上产生显著的加速。然而，决定这些优化问题难度的因素仍然不清楚，限制了该技术的更大规模采用。在本工作中，我们建立了非线性系统动力学与其相应优化公式的条件之间的精确关系。我们证明了系统的可预测性，即状态中的小扰动对未来发展的影响程度，会影响评估所需的优化步骤数量。在可预测的系统中，状态轨迹可以在$O((\log T)^2)$时间内计算，其中$T$是序列长度，这相对于传统的顺序方法是一个重大改进。相比之下，混沌或不可预测的系统表现出较差的条件，结果是并行评估收敛得太慢而无法使用。重要的是，我们的理论分析表明，对于可预测的系统，优化问题总是良好条件的，而对于不可预测的系统，条件随着序列长度的增加呈指数级下降。我们通过广泛的实验验证了我们的主张，提供了关于非线性动力系统何时可以高效并行化的实用指导，并强调可预测性作为可并行化模型的关键设计原则。 显示英文摘要

摘要： The rise of parallel computing hardware has made it increasingly important to understand which nonlinear state space models can be efficiently parallelized. Recent advances like DEER (arXiv:2309.12252) or DeepPCR (arXiv:2309.16318) have shown that evaluating a state space model can be recast as solving a parallelizable optimization problem, and sometimes this approach can yield dramatic speed-ups in evaluation time. However, the factors that govern the difficulty of these optimization problems remain unclear, limiting the larger adoption of the technique. In this work, we establish a precise relationship between the dynamics of a nonlinear system and the conditioning of its corresponding optimization formulation. We show that the predictability of a system, defined as the degree to which small perturbations in state influence future behavior, impacts the number of optimization steps required for evaluation. In predictable systems, the state trajectory can be computed in $O((\log T)^2)$ time, where $T$ is the sequence length, a major improvement over the conventional sequential approach. In contrast, chaotic or unpredictable systems exhibit poor conditioning, with the consequence that parallel evaluation converges too slowly to be useful. Importantly, our theoretical analysis demonstrates that for predictable systems, the optimization problem is always well-conditioned, whereas for unpredictable systems, the conditioning degrades exponentially as a function of the sequence length. We validate our claims through extensive experiments, providing practical guidance on when nonlinear dynamical systems can be efficiently parallelized, and highlighting predictability as a key design principle for parallelizable models.