Estimating the uncertainty of a model's prediction is a crucial part of ensuring reliability under distribution shifts. A minimum description length approach to this problem considers every possible label for a data point, and decreases confidence in a prediction if other labels are also consistent with the model and training data. However, this normalized maximum likelihood (NML) distribution and its associated stochastic complexity measure require training an oracle learner for each label, which is misspecified and computationally intractable for deep neural networks. In this work we propose IF-COMP, a scalable and efficient method to approximate the NML distribution and complexity by linearizing the model with a temperature-scaled Boltzmann influence function. IF-COMP can then be used to produce well-calibrated predictions as well as measures of complexity in both labelled and unlabelled settings. We experimentally validate IF-COMP across uncertainty calibration, mislabel detection, and outlier detection tasks, where it consistently matches or beats strong baseline methods.