Quantifying the uncertainty of regression models is essential to ensure their reliability, particularly since their application often extends beyond their training domain. Based on the solution of a constrained optimization problem, this work proposes ‘prediction rigidities’ as a formalism to obtain uncertainties of arbitrary pre-trained regressors. A clear connection between the suggested framework and Bayesian inference is established, and a last-layer approximation is developed and rigorously justified to enable the application of the method to neural networks. This extension affords cheap uncertainties without any modification to the neural network itself or its training procedure. The effectiveness of this approach is shown for a wide range of regression tasks, ranging from simple toy models to applications in chemistry and meteorology.