---
name: foundations-information-theory
description: Information-theory primitives for AI systems, entropy, mutual information, KL, compression, channel limits, MDL, bottlenecks, and signal quality. Use when quantifying information.
compatibility: Portable core only.
version: "1.2"
last_validated: 2026-08-14
---

# Information Theory Foundations


## When to Apply

**Apply information-theory when:**
- Compressing prompts, retrieval contexts, logs, or feature sets
- Drift detection — distribution shift from baseline (KL, JS divergence)
- Feature selection by mutual information with target
- Retrieval re-ranking, MMR, or diversity-aware candidate selection
- Prompt-quality diagnosis via output-conditional entropy / Fano bound
- Hallucination / abstention gating via semantic entropy over meaning-clustered samples (#1)
- RL post-training diagnostics — policy-entropy collapse is the dominant failure mode in RLVR (#1)
- Agent-to-agent message budgets and KV-cache handoff sizing, framed as a bottleneck/rate problem (#6, #8)

**Skip and use simpler alternatives when:**
- Question is about *causation*, not *information* — use foundations-causal-inference
- Single-feature linear correlation is sufficient — Pearson r is cheaper than MI for monotonic continuous data
- Streaming data with hard latency budget — full MI/KL is too slow; use sketches or sampled approximations
- N samples too small for stable entropy estimate (rule of thumb n > 5 × #bins per variable)
- Problem is system-stability or feedback control — use foundations-control-theory
- Bits/nats unit doesn't map to a business decision — risk of treating it as decoration, not signal

---

11 applied information-theory primitives for quantifying uncertainty, signal, and compression, backed by a formal theory map. Each primitive solves a specific measurement problem. Primitives are domain-agnostic: the same entropy calculation that budgets a context window also bounds a lossless compressor; mutual information that scores retrieval also measures feature relevance in ML.

## Contents

- [Quick Reference](#quick-reference)
- [Primitive Index](#primitive-index)
- [Formal Supporting Theory](#formal-supporting-theory)
- [Anti-Patterns](#anti-patterns)
- [Misuse Boundaries](#misuse-boundaries)
- [Decision Checklist](#decision-checklist)
- [Composition Recipes](#composition-recipes)
- [Workflow](#workflow)
- [ASCII Flow](#ascii-flow)
- [Practitioner Judgment](#practitioner-judgment)
- [Navigation](#navigation)
- [Related Skills](#related-skills)
- [Fact-Checking](#fact-checking)

---

## Quick Reference

| # | Primitive | Core Formula | Use When |
|---|-----------|-------------|----------|
| 1 | [Shannon Entropy](#1-shannon-entropy) | H(X) = −Σ p log p | Measuring uncertainty, budgeting bits. Two high-value LLM specializations: *semantic* entropy — cluster sampled generations by meaning (NLI equivalence), take entropy over clusters, not tokens (Farquhar et al., *Nature* 630, 2024) — for hallucination detection; and *policy* entropy for RLVR collapse diagnosis. |
| 2 | [Mutual Information](#2-mutual-information) | I(X;Y) = H(X) − H(X\|Y) | Scoring relevance, detecting dependence |
| 3 | [KL Divergence](#3-kl-divergence) | D_KL(P‖Q) = Σ p log(p/q) | Comparing distributions, training objectives |
| 4 | [Cross-Entropy](#4-cross-entropy) | H(P,Q) = −Σ p log q | Loss functions, perplexity, model evaluation |
| 5 | [Channel Capacity](#5-channel-capacity) | C = max_{p(x)} I(X;Y) | Theoretical throughput ceilings |
| 6 | [Rate-Distortion](#6-rate-distortion) | R(D) = min_{p(x̂\|x)} I(X;X̂) | Lossy compression tradeoffs. When the reconstruction must also *look real* (generative models, image compression), apply the rate-distortion-perception (RDP) extension: high perceptual fidelity requires strictly higher rate than distortion alone predicts (Niu et al., *Entropy* 2025; Lei et al., NeurIPS 2025). |
| 7 | [MDL Principle](#7-mdl-principle) | MDL = L(M) + L(D\|M) | Model selection, Occam complexity |
| 8 | [Information Bottleneck](#8-information-bottleneck) | min I(X;T) − βI(T;Y) | Representation compression, deep learning |
| 9 | [Fano's Inequality](#9-fanos-inequality) | P_e ≥ (H(X\|Y) − 1) / log\|X\| | Error lower bound from residual uncertainty |
| 10 | [Typical Sets / AEP](#10-typical-sets--aep) | \|A_ε^(n)\| ≈ 2^{nH(X)} | Source coding theorem, block length planning |
| 11 | [Redundancy & Compression](#11-redundancy--compression) | R = H_max − H(X) | Compression budget, Huffman / LZ framing |

---

## Primitive Index

Each primitive is summarized here, expanded in [`references/primitives-overview.md`](references/primitives-overview.md), and covered by standalone playbooks under [`assets/templates/information-theory/`](assets/templates/information-theory/). Use [`references/formal-theory-map.md`](references/formal-theory-map.md) when the task needs theorem assumptions or derivation boundaries.

| # | Mechanism | Failure Mode It Addresses |
|---|-----------|--------------------------|
| 1 | Shannon Entropy | Treating all tokens/states as equally uncertain; unquantified information budget |
| 2 | Mutual Information | Correlation-based relevance scoring that ignores non-linear dependence |
| 3 | KL Divergence | Symmetric distance assumptions on asymmetric divergences; division-by-zero on Q=0 |
| 4 | Cross-Entropy | Conflating cross-entropy loss with distribution similarity |
| 5 | Channel Capacity | Over-estimating throughput without accounting for noise |
| 6 | Rate-Distortion | Assuming lossless compression is achievable when distortion is acceptable |
| 7 | MDL Principle | Overfitting via models that describe noise rather than signal |
| 8 | Information Bottleneck | Feature extractors that retain task-irrelevant variance |
| 9 | Fano's Inequality | Optimism about classifiers when residual entropy is high |
| 10 | Typical Sets / AEP | Designing block codes shorter than entropy lower bound |
| 11 | Redundancy & Compression | Compressing without knowing the redundancy budget; picking the wrong code family |

---

## Formal Supporting Theory

| Theory Area | Use When | Applied Primitives It Grounds |
|---|---|---|
| Measure-theoretic foundations | Need discrete vs continuous entropy, differential entropy caveats, or invariance boundaries | #1, #2, #3 |
| Source coding | Need lossless compression limits, AEP, entropy rate, or universal coding | #1, #10, #11 |
| Channel coding | Need noisy-channel throughput limits and finite-blocklength caveats | #5, #9 |
| Rate-distortion theory | Need lossy compression tradeoffs and distortion measure assumptions | #6 |
| Statistical divergence | Need KL, JS, f-divergences, cross-entropy, or variational objectives | #3, #4 |
| Model selection | Need MDL, stochastic complexity, Bayesian code-length analogies | #7 |
| Representation learning | Need IB, sufficient statistics, compression vs prediction tradeoffs | #2, #8 |
| Estimation theory | Need finite-sample MI/entropy estimator bias and confidence intervals | #1, #2 |

---

## Anti-Patterns

| Anti-Pattern | Diagnosis | Fix |
|-------------|-----------|-----|
| Using KL divergence as a symmetric distance metric | D_KL(P‖Q) ≠ D_KL(Q‖P); treating it like Euclidean distance produces asymmetric results and can cause infinite penalty when Q assigns zero probability to events P can produce | Use Jensen-Shannon divergence (symmetric, bounded [0,1]) or explicitly select the forward/reverse direction based on the cost asymmetry you intend (#3) |
| Estimating mutual information in high dimensions from finite samples | Sample estimators of MI are positively biased and scale with dimension; reported MI values can be inflated several-fold on small datasets | Apply NSB or JVHW correction for discrete MI; use MINE or NWJ estimators for continuous variables; always report confidence intervals alongside MI estimates (#2). New (2025): use the Abdelaleem-Martini-Nemenman protocol (arXiv:2506.00330) — confidence intervals + consistency checks before trusting any neural MI estimate; estimators are reliable only when dependence lies in a low-dimensional latent subspace. For continuous high-dimensional data, consider normalizing-flow-based difference-of-entropies estimators (Ni & Lotz, arXiv:2502.13085) as an alternative to MINE. |
| Treating cross-entropy as a distribution similarity score | H(P,Q) = H(P) + D_KL(P‖Q); a low cross-entropy loss does not imply the model distribution is close to the data distribution when H(P) is large | Decompose cross-entropy into entropy + KL divergence; use JS divergence or Wasserstein distance for direct distribution comparison (#4) |
| Comparing perplexity scores across tokenizers | Perplexity is exp(H(P,Q)) conditioned on a vocabulary; different tokenizers produce different sequence lengths for the same text, making cross-tokenizer perplexity incomparable | Normalize by bits-per-character (BPC) or bits-per-byte (BPB) for vocabulary-neutral comparison (#4) |
| Ignoring the continuous-discrete entropy distinction | Differential entropy (continuous) can be negative; it lacks the absolute probability interpretation of discrete entropy and is not invariant under invertible transforms | Explicitly state which entropy definition is in use; for continuous random variables, use mutual information (which is transform-invariant) rather than raw differential entropy (#1) |
| Applying the Huffman/LZ code directly without checking entropy rate | Huffman codes are optimal only for known i.i.d. distributions; they are suboptimal for correlated sources where the entropy rate H(X_n | X_{n-1},...,X_1) < H(X_1) | Model source correlations first (estimate entropy rate); apply arithmetic coding or LZ-family codes that exploit sequential dependencies (#11) |
| Assuming the information bottleneck β controls compression monotonically | The IB curve is non-convex for finite-sample or discrete cases; solutions can jump discontinuously as β changes | Sweep β densely and validate the I(T;X)/I(T;Y) tradeoff curve empirically; confirm phase transitions match the task (#8) |
| Using InfoNCE/NWJ as an unconstrained MI estimator in contrastive learning | InfoNCE is bounded above by log(K) where K = number of negative samples; severely underestimates MI when true MI >> log(K), which is common in SSL pretraining; gradients become misleading at high MI regimes | Apply f-DIME estimators (Letizia, Novello & Tonello, NeurIPS 2024; code: github.com/tonellolab/fDIME) which use derangement architecture to remove the upper-bound artefact; or use the Abdelaleem-Martini-Nemenman confidence-interval protocol (#2) to detect estimator failure before trusting MI values |
| Claiming "LLMs are optimal compressors" without a Kolmogorov benchmark | Current models (GPT-4o, Llama-3.1-405B) fail the KoLMogorov Test — producing the *shortest* program for a data sequence is distinct from next-token prediction; synthetic gains do not transfer to real sequences | Split the claim in two, because the evidence points opposite ways. *Average-case* compression does track capability: BPC on a held-out corpus correlates near-linearly with benchmark scores, Pearson ≈ −0.95 across 30 models and 12 benchmarks (Huang et al., COLM 2024, arXiv:2404.09937) — which makes BPC a cheap, contamination-resistant evaluation proxy. *Worst-case* compression does not: producing the shortest program for a sequence is a different problem, and frontier models score poorly on the KoLMogorov Test (ICLR 2025), with synthetic gains failing to transfer to real sequences. Use BPC to rank models; do not upgrade that correlation into a Kolmogorov-optimality claim (#11) |
| Using classical R(D) to bound generative model compression | Classical R(D) does not account for perceptual quality; the RDP tradeoff proves that matching the source *distribution* (not just minimising distortion) requires additional rate | Apply the three-way RDP function; use KL, TV, or Wasserstein as the perception constraint divergence measure (#3, #6) |
| Ignoring R(D) theory when choosing LLM weight quantization scheme | Scalar quantization is suboptimal; block-coding (vector quantization) yields strictly lower distortion at the same bitrate per classical R(D) results — Radio (ICML 2025) directly applies R(D)-optimal stochastic quantization to LLM weights and outperforms standard PTQ | Frame LLM quantization as a rate-distortion optimization; prefer vector/lattice quantizers over scalar; use Blahut-Arimoto to find the optimal bit allocation per layer (#6, #7) |
| Using token-level entropy or sequence log-prob to detect hallucination | Token entropy is high whenever *phrasing* is free, which is almost always; the same fact stated five ways scores as maximum uncertainty. It measures lexical, not epistemic, uncertainty, so it fires on paraphrase and misses confident falsehoods | Compute entropy over meaning-equivalence clusters, not tokens: sample N generations, cluster by bidirectional NLI entailment, take entropy of the cluster distribution (Farquhar et al., *Nature* 630:625–630, 2024). For single-generation latency budgets, semantic entropy probes read the estimate off hidden states (Kossen et al., arXiv:2406.15927). Semantic entropy detects confabulation — arbitrary, sampling-unstable answers — not consistently-wrong beliefs, which are invisible to any sampling-based estimator (#1) |
| Treating falling policy entropy during RL post-training as convergence | In RLVR the empirical fit R = −a·e^H + b holds: downstream reward is *bought* with policy entropy, so a collapsed-entropy policy has spent its exploration budget and has hit a ceiling, not found an optimum. Over 95% of the entropy drop and most of the gain occur early, then a plateau (Cui et al., arXiv:2505.22617) | Log policy entropy as a first-class training metric and fit the R/H curve to predict the ceiling before spending the compute. Collapse is driven by tokens with high covariance between log-prob and advantage — restrict updates on those via Clip-Cov or KL-Cov rather than adding a blanket entropy bonus, which trades away the signal indiscriminately (#1) |
| Sizing agent-to-agent messages by token count instead of task-relevant information | Multi-agent handoffs are a rate-constrained channel; a message budget set by token count optimizes the wrong quantity and drops task-critical bits while preserving fluent filler | Frame the handoff as an IB problem — minimize I(X;M) subject to I(M;task) — and quantize the message rather than truncating it. Farooq & Iqbal (IEEE ICRA 2026, arXiv:2602.02035) combine IB with vector quantization and a gating mechanism for 71.4% bandwidth reduction; the same framing applies to KV-cache handoffs and summary passing between LLM agents (#6, #8) |
| Applying standard IB directly to multimodal (image-text) representations | Standard IB's randomness and hyperparameter dependency cause failure in multimodal settings; the IB curve is not interpretable for CLIP-type architectures | Use NIBT (ICLR 2025, code: github.com/LMBTough/NIB) which satisfies attribution axioms and eliminates these pathologies (#8) |

---

## Misuse Boundaries

| Misuse | Why It Is Wrong | Required Correction |
|---|---|---|
| Comparing perplexity across tokenizers | Perplexity depends on tokenization | Use bits-per-byte or bits-per-character |
| Treating differential entropy like discrete entropy | Differential entropy can be negative and coordinate-dependent | Use mutual information or specify units/transform |
| Using KL as a metric | KL is asymmetric and can be infinite | Use JS, Wasserstein, or explicit forward/reverse KL |
| Reporting MI from small high-dimensional samples | MI estimators are biased and unstable | Add estimator choice, confidence intervals, and permutation baselines |
| Treating IB as settled DNN theory for either unimodal DNNs (compression phase is activation-dependent, Saxe et al. 2018) or multimodal models. The 2025 exception: in multimodal (CLIP-type) settings, the Narrowing IB Theory (NIBT, ICLR 2025) and CIBR (ICANN 2025) provide peer-reviewed working applications of IB to representation interpretability and generalization — but only with the NIBT reformulation, not standard IB. For unimodal DNNs with ReLU activations, the Generalized IB (GIB, Westphal et al. arXiv:2509.26327, preprint 2025/2026) reformulates IB via synergistic information and recovers compression phases where standard IB fails; note GIB is unreviewed — treat as promising candidate, not established practice. | Compression claims are activation/estimator dependent; multimodal IB requires NIBT reformulation; ReLU unimodal IB failure has a candidate fix in GIB | Cite both IB and rebuttal evidence; for multimodal settings use NIBT (code: github.com/LMBTough/NIB); for ReLU unimodal architectures, evaluate GIB once peer-reviewed |
| Equating LLM perplexity with Kolmogorov-complexity-optimal compression | Cross-entropy/perplexity measures average-case prediction, not worst-case shortest-program compression | Use KoLMogorov Test benchmark to bound the gap; flag "compression = intelligence" claims as unverified (#11, #7) |
| Calling content “high information” because it is long | Length is not entropy or relevance | Estimate novelty, redundancy, and query MI |
| Ignoring finite-blocklength effects | Asymptotic theorems do not guarantee short-block performance | Check finite-blocklength bounds |

---

## Decision Checklist

- [ ] **Uncertainty measurement**: Need to quantify how many bits a distribution contains? → Shannon entropy (#1)
- [ ] **Relevance scoring**: Need to measure how much knowing X reduces uncertainty about Y? → mutual information (#2)
- [ ] **Distribution comparison (asymmetric)**: Comparing a learned distribution to a reference where direction matters (e.g., RLHF KL penalty)? → KL divergence (#3)
- [ ] **Distribution comparison (symmetric)**: Need a proper metric between distributions? → JS divergence via KL (#3)
- [ ] **Training objective / model evaluation**: Computing a loss between predicted and true distribution? → cross-entropy (#4)
- [ ] **Model comparison across tokenizers**: Need tokenizer-neutral perplexity? → bits-per-byte normalization (#4)
- [ ] **Throughput ceiling**: Need the theoretical limit on reliable transmission over a noisy channel? → channel capacity (#5)
- [ ] **Compression with acceptable loss**: Need to find the minimum bitrate for a target distortion? → rate-distortion (#6)
- [ ] **Model selection / Occam's razor**: Choosing between models of different complexity? → MDL (#7)
- [ ] **Feature / representation compression**: Building a compressed representation that retains task-relevant information? → information bottleneck (#8)
- [ ] **Error lower bound**: Need the minimum achievable classification error given residual uncertainty? → Fano's inequality (#9)
- [ ] **Block code length planning**: Determining how many samples are needed for near-optimal source coding? → AEP / typical sets (#10)
- [ ] **Compression efficiency audit**: Measuring how much redundancy remains in a source relative to its entropy? → redundancy / compression (#11)

---

## Composition Recipes

### Context-Window Budget

**Problem**: A retrieval or summarization pipeline fills a context window but needs to prioritize content under a token budget.

**Stack**:
1. Estimate entropy of each candidate segment (#1) — higher entropy segments carry more novel information.
2. Compute I(segment; query) (#2) — rank by relevance, using mutual information as the relevance signal.
3. Apply MDL penalty (#7) — prune segments whose description cost (length) exceeds the information gain they add.

**Output**: A ranked, pruned set of segments that maximizes information per token.

**LLM app note**: This maps directly to KV-cache pruning and gist-token compression in LLM inference: high-surprisal tokens (H(token | context) large) carry more information and should be retained; low-surprisal tokens are candidates for KV eviction or soft merging. First-token surprisal (I