In supervised learning, understanding an input’s proximity to the training data can help a model decide whether it has sufficient evidence for reaching a reliable prediction. While powerful probabilistic models like Gaussian Processes naturally have this property, deep neural networks often lack it. In this paper, we introduce a new method for enriching deep neural networks with this property. Building on prior information bottleneck methods, our method will learn a codebook that stores a compressed representation of all inputs seen during training. The distance of a new example from this codebook can serve as an uncertainty estimate for the example. The resulting model is simple to train and provides deterministic uncertainty estimates by a single forward pass. Finally, our method achieves better out-of-distribution (OOD) detection and misclassification prediction than prior methods, including expensive ensemble methods, deep Gaussian Processes, and those based on the standard information bottleneck.