Second-Order Complexity of Neural ODE Inference

Neural ordinary differential equations replace a finite layer stack by the solution map of a learned dynamical system. Thus the machine-learning primitive evaluated at inference time is the flow endpoint generated by the learned vector field, computed to requested accuracy. We study the complexity of this global forward pass when the vector field has standard compactness and Lipschitz certificates. Using second-order complexity theory, we identify the exact operator-level complexity of this local-to-global computation: scalar Neural-ODE endpoint inference is second-order polynomial-time equivalent to the classical Lipschitz IVP solution operator and is therefore FPSPACE$_2$-complete in the worst case. This complexity resides in the continuous-depth layer itself, independently of any particular numerical solver: even one fixed three-dimensional autonomous Neural-ODE block with $C^1$ local dynamics can define a PSPACE-hard input-output map. At every finite smoothness level $C^k$ with $k\geq2$, such autonomous blocks can define counting-hierarchy-hard maps. One scalar readout-gradient query recovers the forward endpoint, so the same complexity reaches an elementary training-gradient computation. Hence continuous-depth models and compressed-depth tied ResNets can realize worst-case global computational complexity even when local dynamics are cheap. As a tractable counterpart, fixed-dimensional Taylor-certified analytic vector fields admit polynomial-time endpoint inference under quantitative magnitude and radius certificates. These results show, based on the rigorous framework of second-order complexity theory, that the computational reliability of continuous-depth learning systems depends jointly on global flow structure, representation certificates, and the cost of local network evaluations.