The Geometry of Robust Symbolic Computation in Neural Networks

When can a neural network reliably carry out multi-step symbolic computation? Correct predictions on canonical symbolic inputs are not sufficient, because intermediate neural representations may fall outside regions in which subsequent modules preserve the intended symbolic semantics. We study this problem for fixed encoders and deterministic decoders, characterizing correct execution by containment of reachable neural states in the intended decoder cells. We establish three main results. A multi-step inner-reachability certificate treats the endpoint as a function of the disturbance sequence and can detect full-dimensional reachable sets even when every individual disturbance is rank deficient. For bounded encodings with the ${\ell }_{\infty }$ norm, we obtain an exact closed-ball capacity bound and a matching finite-ReLU construction for arbitrary finite deterministic transition families, without a network-size constraint. Finally, polyhedral module certificates reduce compositional verification to linear optimization over activation regions. An explicit separation shows that identical canonical tables and identical global Lipschitz constants can coexist with different robustness properties. Outer-radius bounds and quantization-aware recurrences provide complementary sufficient conditions. Experiments with learned arithmetic modules distinguish canonical accuracy from representation robustness and terminal accuracy from pathwise correctness. Additional tests find correct sampled executions despite inconclusive regional inclusion checks, and full numerical rank in multistep endpoint Jacobians under low-rank disturbances, but no positive inner-radius estimate centered at the target encoding.