We study solution sensitivity for nonlinear programs (NLPs) whose structures are induced by graphs, as is the case for control and spatially indexed problems. We show that for a given pair of nodes, the sensitivity of the primal-dual solution at one node against a data perturbation at the other node decays exponentially with respect to the distance between these two nodes on the graph. This result, which we refer to as the exponential decay of sensitivity, holds under the strong second-order sufficiency condition and the linear independence constraint qualification. We also present conditions under which the decay rate remains uniformly bounded; this allows us to characterize the sensitivity behavior of NLPs defined over subgraphs of infinite graphs. Moreover, we demonstrate that slightly stronger second-order sufficiency and linear independence constraint qualification holding over subgraphs yield this property over the entire graph. This property may help ensure that control problems with multicomponent systems, such as digital twins of complex systems, possess exponential decay of sensitivity by providing sufficient quality of the component problems alone. This makes the property not only easier to verify, but it also implies that decomposition-based control policies, which are computationally faster, will be exponentially close to optimal. If possible, I would pre