# A Theory of Usable Information Under Computational Constraints

arXiv: https://arxiv.org/abs/2002.10689 · HTML: https://mlsanity.com/paper/2002.10689/

## Key facts

- Cited by 162 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Feb 2020.

## Built on by (most cited first, 30 of 162)

- [Towards Out-Of-Distribution Generalization: A Survey](https://mlsanity.com/paper/2108.13624/) (2021)
- [Understanding Dataset Difficulty with V-Usable Information](https://mlsanity.com/paper/2110.08420/) (2021)
- [LEACE: Perfect linear concept erasure in closed form](https://mlsanity.com/paper/2306.03819/) (2023)
- [Causal Abstraction: A Theoretical Foundation for Mechanistic Interpretability](https://mlsanity.com/paper/2301.04709/) (2023)
- [Acquisition of Chess Knowledge in AlphaZero](https://mlsanity.com/paper/2111.09259/) (2021)
- [On the Diversity and Realism of Distilled Dataset: An Efficient Dataset Distillation Paradigm](https://mlsanity.com/paper/2312.03526/) (2023)
- [ReCEval: Evaluating Reasoning Chains via Correctness and Informativeness](https://mlsanity.com/paper/2304.10703/) (2023)
- [To Compress or Not to Compress- Self-Supervised Learning and Information Theory: A Review](https://mlsanity.com/paper/2304.09355/) (2023)
- [When Do We Not Need Larger Vision Models?](https://mlsanity.com/paper/2403.13043/) (2024)
- [How Large Language Models Encode Context Knowledge? A Layer-Wise Probing Study](https://mlsanity.com/paper/2402.16061/) (2024)
- [Conditional probing: measuring usable information beyond a baseline](https://mlsanity.com/paper/2109.09234/) (2021)
- [How much do language models memorize?](https://mlsanity.com/paper/2505.24832/) (2025)
- [Probing for the Usage of Grammatical Number](https://mlsanity.com/paper/2204.08831/) (2022)
- [Temporal Predictive Coding For Model-Based Planning In Latent Space](https://mlsanity.com/paper/2106.07156/) (2021)
- [Lossy Compression for Lossless Prediction](https://mlsanity.com/paper/2106.10800/) (2021)
- [What Context Features Can Transformer Language Models Use?](https://mlsanity.com/paper/2106.08367/) (2021)
- [Do language models plan ahead for future tokens?](https://mlsanity.com/paper/2404.00859/) (2024)
- [Controllable Guarantees for Fair Outcomes via Contrastive Information Estimation](https://mlsanity.com/paper/2101.04108/) (2021)
- [RePrompt: Automatic Prompt Editing to Refine AI-Generative Art Towards Precise Expressions](https://mlsanity.com/paper/2302.09466/) (2023)
- [PreFLMR: Scaling Up Fine-Grained Late-Interaction Multi-modal Retrievers](https://mlsanity.com/paper/2402.08327/) (2024)
- [Disentanglement via Latent Quantization](https://mlsanity.com/paper/2305.18378/) (2023)
- [On the generalization of language models from in-context learning and finetuning: a controlled study](https://mlsanity.com/paper/2505.00661/) (2025)
- [Frozen Transformers in Language Models Are Effective Visual Encoder Layers](https://mlsanity.com/paper/2310.12973/) (2023)
- [Fair Normalizing Flows](https://mlsanity.com/paper/2106.05937/) (2021)
- [FedML-HE: An Efficient Homomorphic-Encryption-Based Privacy-Preserving Federated Learning System](https://mlsanity.com/paper/2303.10837/) (2023)
- [Improving Self-Supervised Learning by Characterizing Idealized Representations](https://mlsanity.com/paper/2209.06235/) (2022)
- [Word Order Does Matter (And Shuffled Language Models Know It)](https://mlsanity.com/paper/2203.10995/) (2022)
- [On the Challenges and Opportunities in Generative AI](https://mlsanity.com/paper/2403.00025/) (2024)
- [Value Profiles for Encoding Human Variation](https://mlsanity.com/paper/2503.15484/) (2025)
- [On the Learning of Non-Autoregressive Transformers](https://mlsanity.com/paper/2206.05975/) (2022)

## Abstract (arXiv)

We propose a new framework for reasoning about information in complex systems. Our foundation is based on a variational extension of Shannon's information theory that takes into account the modeling power and computational constraints of the observer. The resulting emphpredictive V-information encompasses mutual information and other notions of informativeness such as the coefficient of determination. Unlike Shannon's mutual information and in violation of the data processing inequality, V-information can be created through computation. This is consistent with deep neural networks extracting hierarchies of progressively more informative features in representation learning. Additionally, we show that by incorporating computational constraints, V-information can be reliably estimated from data even in high dimensions with PAC-style guarantees. Empirically, we demonstrate predictive V-information is more effective than mutual information for structure learning and fair representation learning.