Condensation

1. Prerequisites

1. Probability on finite sets, conditional probability, and elementary proofs.
2. Conditional entropy and conditional independence; Section 1.1 collects what we use.

What you’ll learn

Condensation

• Construct latent models and check the three conditions on them: the latent variable model condition, reconstruction, and the Markov condition.
• Explain why a single agent would want its latents to satisfy the last two.
• Prove correspondence between families of latents, first exactly and then with explicit error terms.

A hierarchical clustering example

• Compare how different latent models of the same law meet the conditions, and what the conditioned score charges each for a query.

Condensation in context

• Relate condensation to natural latents, sufficient statistics, common information, computational mechanics, and graphical models.
• Separate informational correspondence from learning, finding, and using a translation.
• Identify which additional claims would connect correspondence to AI safety.

How to use this sheet

After the first lecture, read Sections 2.1 and 2.2 and work Exercises 2.1, 2.2 and 2.4. After the second lecture, read Sections 2.3 and 2.4 and work Exercises 2.5, 2.6, 2.7, 2.8, 2.9 and 2.10. These nine starred exercises, about 140 minutes in all, are the core route. Then read Sections 3 and 4, take the discussion prompts in Section 4.5 to your group, and finish with the quiz in Section 5. Exercises 2.3, 2.11, 2.12 and 3.1 are optional.

1.1 Information theory reference

All random variables have finite ranges and all logarithms are base two. For a finite-valued variable $U$,

$$H(U)=-\sum _{u}p(u)\log p(u),H(U\mid V)=\sum _{v}p(v)H(U\mid V=v),$$

with $0\log 0=0$. Conditional entropy is nonnegative. It is zero precisely when $U$ is a function of $V$ almost surely: values on probability-zero events do not matter. The chain rule and conditioning inequality are

$$H(U,V\mid W)=H(U\mid W)+H(V\mid U,W),H(U\mid V,W)\le H(U\mid W).$$

Conditional mutual information is

$$I(U;V\mid W)=H(U\mid W)-H(U\mid V,W)\ge 0.$$

It is symmetric in $U,V$ and is zero precisely when $U,V$ are conditionally independent given $W$. Omitting $W$ gives mutual information $I(U;V)$. Entropy of a tuple means joint entropy, not the sum of its marginal entropies. An empty tuple is constant and has zero entropy. For probability distributions $p,q$ on a finite set,

$$D_{\mathrm{KL}}(p\Vert q)=\sum _{u}p(u)\log \frac{p(u)}{q(u)}\ge 0.$$

This last quantity appears only in the optional score discussion.

2. Condensation

In empirical work, people look for features in AI systems which correspond robustly to human concepts. In general, these can be hard to find.

One ambitious approach to this problem is to think through from first principles how agents in general might organize information about the world into concepts.

How should information be broken into reusable pieces? Is there one way to do this which many different kinds of agents will converge on?

We will propose two conditions that we think are normative for agents in general: conditions an agent will want its own organization of information to satisfy. Under those conditions, corresponding families of latents in two models determine one another.

2.1 A family of questions

Fix jointly distributed observables $X_1,\dots ,X_n$. We look for latent variables, each assigned to a set of observations, such that the latents assigned to an observation determine it. We will give conditions under which corresponding families of latents in two such models determine one another, and bound the remaining conditional entropy when the conditions hold approximately. We take the joint distributions as given.

2.1.1 Addresses and families

Let $I=\{1,\dots ,n\}$ and write ${\mathcal{P}}^{+}(I)$ for its nonempty subsets. An address $A\in {\mathcal{P}}^{+}(I)$ specifies which observations receive a latent $Y_A$. We use one latent for each nonempty subset, setting unused ones to constants, and order the addresses by inclusion.

Definition 2.2 (Latent model). A latent model of $X=(X_i{)}_{i\in I}$ consists of finite-valued variables $Y=(Y_A{)}_{A\in {\mathcal{P}}^{+}(I)}$ jointly distributed with $X$, such that

$$H(X_i\mid Y_{\{A\in {\mathcal{P}}^{+}(I):i\in A\}})=0\text{for every }i\in I.$$

Here $Y_{\mathcal{F}}=(Y_A{)}_{A\in \mathcal{F}}$ for a family $\mathcal{F}\subseteq {\mathcal{P}}^{+}(I)$.

We call (1) the latent variable model condition, or LVM. The contributing latents, taken together, determine the observation; some of them may represent residual noise.

For nonempty $A\subseteq I$ and $B\subseteq I$, define two different families:

$$\supseteq A=\{C\in {\mathcal{P}}^{+}(I):A\subseteq C\},{\mathcal{J}}_B=\{C\in {\mathcal{P}}^{+}(I):C\cap B\ne \varnothing \}.$$

The tuple $Y_{\supseteq A}$ is the tower above $A$. The tuple $Y_{{\mathcal{J}}_B}$ contains all latents contributing to at least one observation in $B$; we call these latents active for $B$. They determine $X_B=(X_i{)}_{i\in B}$. In particular $\supseteq \{i\}={\mathcal{J}}_{\{i\}}$ is the family of addresses contributing to $X_i$, so (1) reads $H(X_i\mid Y_{\supseteq \{i\}})=0$. For a larger $A$, $\supseteq A$ and ${\mathcal{J}}_A$ generally differ.

Glossary. The sheet uses a small fixed vocabulary.

Address A nonempty $A\subseteq I$. The model has one latent $Y_A$ at each address; unused ones are constant.

Block A nonempty set $B\subseteq I$ of observations, with $X_B=(X_i{)}_{i\in B}$.

Family A set $\mathcal{F}$ of addresses, and the corresponding family of latents $Y_{\mathcal{F}}$.

Contributing $Y_A$ contributes to $X_i$ when $i\in A$. The contributing family of $X_i$ is $\supseteq \{i\}$.

Tower The family of latents $Y_{\supseteq A}$ at $A$ and every address containing it.

Active $Y_A$ is active for a block $B$ when $A\cap B\ne \varnothing$, that is, when it contributes to some observation in $B$. The active family is ${\mathcal{J}}_B$.

Upward closed A family containing every superset of each of its addresses (Section 2.2).

Witness A variable from which a target is recoverable (Section 2.3).

Exercise 2.1 (★) (Overlapping bits; 15 minutes). Use Example 2.1, with all unmentioned latents constant.

(a) Compute $H(X_1)$, $H(X_1,X_2,X_3)$, and $I(X_1;X_2)$.

(b) List $\supseteq \{1\}$, $\supseteq \{2\}$, and $\supseteq \{1,2\}$, including constant latents. Which tuple determines $X_1$? Which of the three is $\supseteq \{1\}\cap \supseteq \{2\}$?

(c) Give explicit functions recovering $X_1$ from its contributing latents and recovering $Y_{\{1,2\}}$ from $X_1$.

(d) Does the address structure have to be a tree? Identify two overlapping addresses in this example neither of which contains the other.

Solution

The independent fair bits are $S,P,Q$, and $X_1=(S,P)$, $X_2=(S,Q)$, $X_3=(P,Q)$.

(a) $H(X_1)=2$. The tuple of all observations determines $(S,P,Q)$ and is determined by it, so $H(X_1,X_2,X_3)=3$. The pair $(X_1,X_2)$ already determines all three bits, hence

$$I(X_1;X_2)=H(X_1)+H(X_2)-H(X_1,X_2)=2+2-3=1.$$

Its shared bit is $S$.

(b) The families, including constant latents, are

$$\begin{array}{rl}\supseteq \{1\}& =\{\{1\},\{1,2\},\{1,3\},\{1,2,3\}\},\\ \supseteq \{2\}& =\{\{2\},\{1,2\},\{2,3\},\{1,2,3\}\},\\ \supseteq \{1,2\}& =\{\{1,2\},\{1,2,3\}\}.\end{array}$$

The first tuple has nonconstant entries $S,P$, so determines $X_1$. Intersecting the first two families leaves $\{\{1,2\},\{1,2,3\}\}=\supseteq \{1,2\}$, the third family listed, whose only nonconstant content is $S$.

(c) Recover $X_1$ by taking the ordered pair $(Y_{\{1,2\}},Y_{\{1,3\}})$. Recover $Y_{\{1,2\}}$ from $X_1$ by projecting onto its first coordinate.

(d) Addresses $\{1,2\}$ and $\{1,3\}$ overlap but neither contains the other. Thus the contribution pattern need not form a nested tree.

2.2 Two conditions on a latent model

Every observable law has trivial latent models: put a copy of each $X_i$ in its singleton latent, or the entire tuple $X$ in the top latent $Y_I$, and LVM holds either way. So LVM alone says nothing about how information is shared. Two further conditions do.

Definition 2.3 (Reconstruction). A latent model has exact reconstruction if

$$H(Y_A\mid X_i)=0\text{whenever }i\in A.$$

Equivalently, $H(Y_{\supseteq A}\mid X_i)=0$ whenever $i\in A$: every latent in that finite tuple can be recovered from $X_i$.

The equivalence in this definition uses exact zero errors. In approximate statements we will bound the entropy of the whole tower; separately small errors for its individual latents could add up.

A family $\mathcal{F}\subseteq {\mathcal{P}}^{+}(I)$ is upward closed if $A\in \mathcal{F}$ and $A\subseteq C$ imply $C\in \mathcal{F}$. For example, $\supseteq A$ and ${\mathcal{J}}_B$ are upward closed. Upward closure makes a family include every more general latent that its members may depend on.

Definition 2.4 (Markov condition and defect). The Markov condition is

$$I(Y_{\mathcal{F}};Y_{\mathcal{G}}\mid Y_{\mathcal{F}\cap \mathcal{G}})=0$$

for all upward-closed families $\mathcal{F},\mathcal{G}\subseteq {\mathcal{P}}^{+}(I)$. Its quantitative defect is

$${\eta }_Y=\underset{\mathcal{F},\mathcal{G}\text{ upward closed}}{\max }I(Y_{\mathcal{F}};Y_{\mathcal{G}}\mid Y_{\mathcal{F}\cap \mathcal{G}}).$$

The condition says that the latents at the shared addresses $\mathcal{F}\cap \mathcal{G}$ account for the dependence between the two families. In the two-observable case, its only potentially nonzero requirement is

$$I(Y_{\{1\}};Y_{\{2\}}\mid Y_{\{1,2\}})=0.$$

This is a graphical-model condition for the inclusion order. The equivalent local version says that each latent is conditionally independent of all incomparable latents given its strict supersets.

Definition 2.5 (Perfect condensation). A latent model is a perfect condensation if it has exact reconstruction and satisfies the Markov condition.

This is equivalent to Eisenstat's definition by optimal conditioned scores (Eisenstat 2025, Theorem 5.10). Section 2.6 explains that connection. The overlapping-bit model in Example 2.1 is a perfect condensation. All nonconstant latents are mutually independent, so disjoint subfamilies are independent, including after conditioning on the remaining common subfamily. Reconstruction follows from coordinate projections.

Exercise 2.2 (★) (Two failed models; 20 minutes). Keep the observables of Example 2.1. Consider two alternative models.

(a) Set $Y_{\{i\}}=X_i$ for $i=1,2,3$ and every other latent constant. Check LVM and reconstruction. Take $\mathcal{F}=\supseteq \{1\}$ and $\mathcal{G}=\supseteq \{2\}$. Calculate the conditional mutual information in Definition 2.4. Which information is duplicated across singleton latents?

(b) Instead set $Y_{\{1,2,3\}}=(S,P,Q)$ and every other latent constant. Check LVM and the Markov condition. Compute $H(Y_{\{1,2,3\}}\mid X_1)$. Which condition fails?

(c) Explain why LVM, reconstruction, and the Markov condition have different roles.

Solution

(a) In the singleton-copy model $Y_{\{i\}}=X_i$, the contributing family for $i$ includes $X_i$ itself. Thus LVM holds. Each nonconstant latent has just one contributing observation, from which it is recovered identically, so reconstruction holds too.

For $\mathcal{F}=\supseteq \{1\}$ and $\mathcal{G}=\supseteq \{2\}$, all entries of $Y_{\mathcal{F}\cap \mathcal{G}}$ are constant. The only nonconstant entries of the two larger tuples are $X_1$ and $X_2$. Consequently

$$I(Y_{\mathcal{F}};Y_{\mathcal{G}}\mid Y_{\mathcal{F}\cap \mathcal{G}})=I(X_1;X_2)=1.$$

Both singleton latents determine $S$, while their common ancestor latents are constant. This violates the Markov condition. It is enough to exhibit this one pair of upward-closed families; finding the maximum defect is unnecessary.

(b) With only $Y_{\{1,2,3\}}=(S,P,Q)$ nonconstant, each observation is obtained by projection, so LVM holds. Every nonempty upward-closed family contains the top address. If both families are nonempty, their intersection contains that top latent and determines all latent variables; the conditional mutual information is zero. If either is empty it is zero as well. Thus the Markov condition holds.

But $X_1=(S,P)$ leaves the independent fair bit $Q$ unknown, so

$$H(Y_{\{1,2,3\}}\mid X_1)=H(Q\mid S,P)=1.$$

Reconstruction fails.

(c) LVM requires enough latent information to determine each observation. Reconstruction excludes information placed at a shared address that an individual contributing observation cannot recover. The Markov condition excludes dependence between families not accounted for by their common latents. The singleton model satisfies reconstruction but fails the Markov condition; the top-latent model satisfies the Markov condition but fails reconstruction.

2.2.1 Existence is a separate question

The preceding examples test particular latent models. A stronger question is whether a given observable law admits any perfect condensation. Even a pair of correlated binary variables can fail to do so.

Let $I=\{1,2\}$, let $X_1$ be a fair bit, and set $X_2=X_1\oplus N$, where $N$ is independent Bernoulli$(q)$ noise and $0<q<1/2$. Here $\oplus$ is addition modulo two, so $a\oplus b$ is $0$ when the two bits agree and $1$ when they differ. The joint law is

$$\begin{array}{rcc}P(x_1,x_2)& x_2=0& x_2=1\\ x_1=0& \frac{1-q}{2}& \frac{q}{2}\\ x_1=1& \frac{q}{2}& \frac{1-q}{2}\end{array}$$

All four outcomes have positive probability, and $X_1,X_2$ are dependent because the two rows differ ($q\ne 1/2$). Suppose a perfect condensation existed, and consider its top latent $Y_{\{1,2\}}$.

With two observations there are only three addresses, so the whole model is three latents:

$$\begin{array}{rccc}\text{address}& \{1\}& \{1,2\}& \{2\}\\ \text{latent}& Y_{\{1\}}& Y_{\{1,2\}}& Y_{\{2\}}\end{array}$$

LVM says $X_1$ is determined by $(Y_{\{1\}},Y_{\{1,2\}})$ and $X_2$ by $(Y_{\{2\}},Y_{\{1,2\}})$. The top latent $Y_{\{1,2\}}$ is the only one assigned to both observations, so it is the only place shared information can sit.

Reconstruction would give $Y_{\{1,2\}}=f(X_1)=g(X_2)$ almost surely. Because all four observable pairs have positive probability, these equalities force

$$f(0)=g(0)=g(1)=f(1).$$

Thus $Y_{\{1,2\}}$ is constant. The Markov condition would then require $Y_{\{1\}}$ and $Y_{\{2\}}$ to be independent. LVM makes each $X_i$ a function of its singleton latent and the constant $Y_{\{1,2\}}$. Functions of independent variables are independent, contradicting the chosen observable law. No perfect condensation exists for this pair.

There is a quantitative obstruction if we retain exact reconstruction. The same argument makes $Y_{\{1,2\}}$ constant. Data processing then gives

$${\eta }_Y=I(Y_{\{1\}};Y_{\{2\}})\ge I(X_1;X_2)=1-h_2(q)>0,$$

where $h_2(q)=-q\log q-(1-q)\log (1-q)$ is the binary entropy function. Dependence between the observables must remain as a Markov defect when their separately recoverable top latent is constant. The bound is attained by the singleton-copy model $Y_{\{i\}}=X_i$, with constant top.

That bound pins one end of a trade-off: exact reconstruction forces a Markov defect of at least $1-h_2(q)$, and tolerating some reconstruction error buys part of it back. When no perfect condensation exists, which is the usual situation (Exercise 2.3), the latent models of a given observable law trace out a Pareto frontier between reconstruction defect and Markov defect. The useful question is then whether some point on that frontier has both low enough for the correspondence bound of Section 2.3 to say something.

Exercise 2.3 (Full support; optional, 10 minutes). The argument for the noisy pair used only two facts: every combination of values has positive probability, and the observables are dependent. Generalize it. Suppose every combination of values that $X_1,\dots ,X_n$ can individually take has positive probability.

(a) Show that in any perfect condensation, every latent at an address with at least two elements is constant.

(b) For disjoint nonempty blocks $B,C$, apply the Markov condition to ${\mathcal{J}}_B$ and ${\mathcal{J}}_C$ to show that $X_B$ and $X_C$ are independent. Conclude that a perfect condensation exists exactly when the observables are mutually independent.

Solution

(a) Let $A$ contain $i\ne j$. Reconstruction gives $Y_A=f(X_i)=g(X_j)$ almost surely. Every pair of values $(x_i,x_j)$ has positive probability, so $f(x_i)=g(x_j)$ for all of them, and $f$ and $g$ are the same constant.

(b) Every address in ${\mathcal{J}}_B\cap {\mathcal{J}}_C$ meets both disjoint blocks, so it has at least two elements and its latent is constant. The Markov condition therefore makes $Y_{{\mathcal{J}}_B}$ and $Y_{{\mathcal{J}}_C}$ independent, and by LVM $X_B$ and $X_C$ are functions of them. Taking $B=\{1,\dots ,k-1\}$ and $C=\{k\}$ for $k=2,\dots ,n$ factorizes the joint law into its marginals. Conversely, if the observables are mutually independent, the singleton-copy model $Y_{\{i\}}=X_i$ is a perfect condensation: LVM and reconstruction are immediate, and the Markov condition holds because all its nonconstant latents are mutually independent, as for the overlapping-bit model.

In particular, a perfect condensation of any full-support law with dependent observables is impossible, which is why the approximate theorem is the one that applies to noisy data.

Exercise 2.4 (★) (Families, not individual latents; 15 minutes). For this exercise let $I=\{1,2\}$, take independent fair bits $C,R,T$, and set $X_1=(C,R)$, $X_2=(C,T)$. Compare

$$\begin{array}{lll}{Y}_{\{1,2\}}=C,& Y_{\{1\}}=R,& Y_{\{2\}}=T,\\ Z_{\{1,2\}}=C,& Z_{\{1\}}=(C,R),& Z_{\{2\}}=(C,T).\end{array}$$

(a) Check that both models are perfect condensations.

(b) Compute $H(Z_{\{1\}}\mid Y_{\{1\}})$.

(c) Show that $Y_{\supseteq \{1\}}$ and $Z_{\supseteq \{1\}}$ determine one another. Explain why correspondence between these tuples is a different claim from correspondence between the singleton latents.

Solution

Here $C,R,T$ are independent fair bits. In model $Y$ the three latents are $C,R,T$; in model $Z$ they are $C,(C,R),(C,T)$.

(a) Both contributing families determine their observations. All latents are recoverable from each observation to which they contribute. For example, $C$ is the first coordinate of either $X_1$ or $X_2$, and $Z_{\{1\}}=X_1$. For two observables the only nontrivial Markov requirement is independence of the two singleton latents given the top latent. For $Y$ this is $I(R;T\mid C)=0$. For $Z$ it is

$$I((C,R);(C,T)\mid C)=I(R;T\mid C)=0.$$

Both are therefore perfect condensations.

(b) $H(Z_{\{1\}}\mid Y_{\{1\}})=H(C,R\mid R)=H(C)=1$.

(c) The $Y$ tower at $\{1\}$ consists of $(R,C)$, and the $Z$ tower consists of $((C,R),C)$. Each is a deterministic function of the other. A copy of the higher-address information can appear in a lower latent without changing the tower's total information. Thus the individual latents need not correspond even when the relevant towers do.

2.2.2 Why we ask for the conditions only approximately

Figure 1 shows a hierarchical model of 36 labelled points, worked through in Section 3. A global shape is assigned to every point, a group center $G_g$ to the 18 points of its group, and a cluster center $M_{gc}$ to the nine points of its cluster.

The cluster center specifies a distribution for its points, not the points themselves, so a point does not determine the center it was drawn from:

$$H(M_{gc}\mid X_i)>0.$$

Every kernel here has full support: no finite set of points pins a parameter. LVM and the Markov condition hold exactly here. The reconstruction condition holds only approximately. So we ask for reconstruction up to a defect: for $i\in A$,

$$H(Y_{\supseteq A}\mid X_i)\le \delta ,$$

and prove a correspondence whose error grows with $\delta$ and $\eta$.

2.3 The correspondence theorem

Take two latent models of the same observable tuple $X$. To compare them, put $(X,Y,Z)$ on one probability space while retaining both specified laws $(X,Y)$ and $(X,Z)$. For finite variables this is always possible: for example, use $p(x,y,z)=p(x)p(y\mid x)p(z\mid x)$. The theorem holds for any such coupling.

Theorem 2.6 (Correspondence). For two latent models $Y,Z$ of $X$ and any nonempty $A\subseteq I$, let $k=|A|$. Then

$$H(Y_{\supseteq A}\mid Z_{\supseteq A})\le \sum _{i\in A}H(Y_{\supseteq A}\mid X_i)+(k-1){\eta }_Z.$$

If each term in the sum is at most $\delta$ and ${\eta }_Z\le \eta$, the bound is $k\delta +(k-1)\eta$. If both budgets are $\epsilon$, it is $(2k-1)\epsilon$. Interchanging $Y,Z$ gives the reverse bound.

Corollary 2.7 (Exact correspondence). If $Y$ and $Z$ are perfect condensations, their towers above every nonempty address $A$ determine one another almost surely:

$$H(Y_{\supseteq A}\mid Z_{\supseteq A})=H(Z_{\supseteq A}\mid Y_{\supseteq A})=0.$$

The forward bound uses reconstruction in $Y$, LVM in $Z$, and the Markov defect of $Z$. It does not use the Markov condition of $Y$ until we reverse the argument. The result concerns corresponding families. Exercise 2.4 shows why we cannot simply replace those families by individual latents.

This proof is a specialization of Eisenstat's approximate correspondence theorem (Eisenstat 2025, Theorem 6.8), using the two-witness inequality (Eisenstat 2025, Lemma 6.4). The exercises below give the full argument without additional machinery.

2.3.1 Proof roadmap

The theorem has three steps.

1. If two witnesses each determine a target and are independent given their common part, that common part determines the target. Entropy gives a version with errors.
2. Each observation $X_i$ is determined by its contributing $Z$-latents. Anything recoverable from $X_i$ is therefore recoverable from that family.
3. Intersect these contributing families over $i\in A$. Exactly the addresses containing all of $A$ survive. Each intersection costs at most one Markov error term.

The word "witness" below means a variable or tuple from which the target is recoverable.

Lemma 2.8 (Two witnesses). For any finite-valued variables $U,M,P,Q$,

$$H(U\mid M)\le H(U\mid M,P)+H(U\mid M,Q)+I(P;Q\mid M).$$

Exercise 2.5 (★) (Prove the two-witness lemma; 20 minutes). (a) Prove Lemma 2.8 by expanding conditional entropies using the chain rule. Find an expression for the difference between the right and left sides that is a sum of nonnegative quantities.

(b) Deduce the exact statement when the three terms on the right are zero.

(c) Explain the three error terms. Which measure failures of reconstruction, and which measures dependence that remains after revealing $M$?

Hint

Try expanding $I(P;Q\mid M)-I(P;Q\mid U,M)$, then rearranging with the chain rule, which is stated in Section 1.1. The desired difference contains a conditional mutual information and a conditional entropy.

Solution

For arbitrary finite $U,M,P,Q$, expand the two conditional mutual informations in entropies and regroup the terms in pairs:

$$\begin{array}{rl}& I(P;Q\mid M)-I(P;Q\mid U,M)\\ & =[H(P\mid M)-H(P\mid U,M)]+[H(Q\mid M)-H(Q\mid U,M)]\\ & -[H(P,Q\mid M)-H(P,Q\mid U,M)]\\ & =I(U;P\mid M)+I(U;Q\mid M)-I(U;P,Q\mid M)\\ & =H(U\mid M)-H(U\mid P,M)-H(U\mid Q,M)+H(U\mid P,Q,M).\end{array}$$

Rearranging gives

$$\begin{array}{rl}& H(U\mid M,P)+H(U\mid M,Q)+I(P;Q\mid M)-H(U\mid M)\\ & =I(P;Q\mid U,M)+H(U\mid M,P,Q).\end{array}$$

Its right side is nonnegative, which proves the lemma.

If $H(U\mid M,P)=H(U\mid M,Q)=I(P;Q\mid M)=0$, the inequality and nonnegativity imply $H(U\mid M)=0$. Thus a target recoverable from each witness is recoverable from their designated common part when the witnesses are conditionally independent given that part.

The first two terms measure what each witness, together with $M$, still fails to determine about $U$. The third measures dependence between $P,Q$ not accounted for by $M$. No independence assumption is needed for the inequality itself; exact independence is the case where the third error is zero.

Exercise 2.6 (★) (The dependence term is needed; 5 minutes). Let $U=P=Q$ be a fair bit and let $M$ be constant. Evaluate every term in (3). What would go wrong if the mutual-information term were omitted? How does this example resemble the singleton-copy model in Exercise 2.2?

Solution

With $U=P=Q$ a fair bit and $M$ constant,

$$H(U\mid M)=1,H(U\mid M,P)=H(U\mid M,Q)=0,I(P;Q\mid M)=1.$$

The inequality is the equality $1\le 0+0+1$. Without its mutual-information term it would assert $1\le 0$. The two witnesses each determine the same bit while the designated common variable is constant, as in the singleton-copy model of Exercise 2.2.

Exercise 2.7 (★) (Transfer through an observable; 10 minutes). Let $U$ be any finite-valued target and suppose $X_i$ is determined by $Z_{\supseteq \{i\}}$. Prove

$$H(U\mid Z_{\supseteq \{i\}})\le H(U\mid X_i).$$

State the equality obtained by adding $X_i$ to the conditioning tuple, then apply the conditioning inequality. Does this argument assume that $U$ and $Z_{\supseteq \{i\}}$ are conditionally independent given $X_i$?

Solution

If $X_i$ is a function of $Z_{\supseteq \{i\}}$ almost surely, adding $X_i$ to that conditioning tuple changes no information. Hence

$$H(U\mid Z_{\supseteq \{i\}})=H(U\mid Z_{\supseteq \{i\}},X_i)\le H(U\mid X_i).$$

The inequality is conditioning monotonicity. It does not assume that $U$ and $Z_{\supseteq \{i\}}$ are conditionally independent given $X_i$. They can share additional information beyond $X_i$.

Exercise 2.8 (★) (Intersect the address families; 15 minutes). (a) For $I=\{1,2,3\}$, list $\supseteq \{1\}$, $\supseteq \{2\}$, and $\supseteq \{3\}$. Compute $\supseteq \{1\}\cap \supseteq \{2\}$ and then its intersection with $\supseteq \{3\}$.

(b) Show that an intersection of upward-closed families is upward closed.

(c) For general nonempty $A\subseteq I$, prove ${\bigcap }_{i\in A}\supseteq \{i\}=\supseteq A$ by checking membership of an address $C$ on both sides.

(d) If $\mathcal{F},\mathcal{G}$ are upward closed, apply the two-witness lemma with $M=Z_{\mathcal{F}\cap \mathcal{G}}$, $P=Z_{\mathcal{F}}$, and $Q=Z_{\mathcal{G}}$. Why can the extra conditioning on $M$ be dropped from each reconstruction term? Write the resulting bound using ${\eta }_Z$.

Solution

(a) The first two families are listed in Exercise 2.1, and

$$\supseteq \{3\}=\{\{3\},\{1,3\},\{2,3\},\{1,2,3\}\}.$$

Thus $\supseteq \{1\}\cap \supseteq \{2\}=\{\{1,2\},\{1,2,3\}\}$, and intersecting with $\supseteq \{3\}$ leaves only $\{1,2,3\}$.

(b) If $C$ belongs to every family in an intersection and $D\supseteq C$, upward closure places $D$ in each such family, hence in the intersection.

(c) For an address $C$,

$$C\in \bigcap _{i\in A}\supseteq \{i\}⟺(\forall i\in A)i\in C⟺A\subseteq C⟺C\in \supseteq A.$$

(d) Put $M=Z_{\mathcal{F}\cap \mathcal{G}}$, $P=Z_{\mathcal{F}}$, $Q=Z_{\mathcal{G}}$. The tuple $M$ is a subtuple of both $P$ and $Q$. Thus $H(U\mid M,P)=H(U\mid P)$ and similarly for $Q$. By the definition of ${\eta }_Z$, the lemma gives

$$H(U\mid Z_{\mathcal{F}\cap \mathcal{G}})\le H(U\mid Z_{\mathcal{F}})+H(U\mid Z_{\mathcal{G}})+{\eta }_Z.$$

Upward closure is needed to invoke the bound ${\eta }_Z$.

Exercise 2.9 (★) (Complete the correspondence proof; 25 minutes). Fix $A=\{i_1,\dots ,i_k\}$ and set ${\mathcal{G}}_j={\bigcap }_{\ell =1}^j\supseteq \{i_{\ell }\}$. We prove, for $1\le j\le k$,

$$H(Y_{\supseteq A}\mid Z_{{\mathcal{G}}_j})\le \sum _{\ell =1}^{j}H(Y_{\supseteq A}\mid X_{i_{\ell }})+(j-1){\eta }_Z.$$

(a) Use Exercise 2.7 to prove (4) at $j=1$.

(b) Use Exercise 2.8 to show, for $j\ge 2$,

$$H(Y_{\supseteq A}\mid Z_{{\mathcal{G}}_j})\le H(Y_{\supseteq A}\mid Z_{{\mathcal{G}}_{j-1}})+H(Y_{\supseteq A}\mid Z_{\supseteq \{i_j\}})+{\eta }_Z.$$

(c) Conclude (4) by induction. Evaluate it at $j=k$ to prove Theorem 2.6, and check the case $k=1$ explicitly.

(d) Deduce Corollary 2.7, including the reverse direction. Name the assumption used at each step of the proof.

(e) Suppose instead that $H(Y_C\mid X_i)\le \epsilon$ separately for all relevant addresses $C$. Why does this not by itself supply the tower error budget $H(Y_{\supseteq A}\mid X_i)\le \epsilon$?

Solution

Fix a nonempty $A=\{i_1,\dots ,i_k\}$, put ${\mathcal{G}}_j={\bigcap }_{\ell =1}^j\supseteq \{i_{\ell }\}$. Every $\supseteq \{i\}$ is upward closed, as is every ${\mathcal{G}}_j$ by Exercise 2.8. We prove (4) for $1\le j\le k$.

For $j=1$, ${\mathcal{G}}_1=\supseteq \{i_1\}$, and Exercise 2.7 gives $H(Y_{\supseteq A}\mid Z_{{\mathcal{G}}_1})\le H(Y_{\supseteq A}\mid X_{i_1})$. This is the claimed bound with zero intersection terms.

Suppose (4) holds for $j-1$, where $2\le j\le k$. Apply Exercise 2.8 to the upward-closed families ${\mathcal{G}}_{j-1}$ and $\supseteq \{i_j\}$. Their intersection is ${\mathcal{G}}_j$, so

$$\begin{array}{rl}H(Y_{\supseteq A}\mid Z_{{\mathcal{G}}_j})& \le H(Y_{\supseteq A}\mid Z_{{\mathcal{G}}_{j-1}})+H(Y_{\supseteq A}\mid Z_{\supseteq \{i_j\}})+{\eta }_Z\\ & \le \sum _{\ell =1}^{j-1}H(Y_{\supseteq A}\mid X_{i_{\ell }})+(j-2){\eta }_Z+H(Y_{\supseteq A}\mid X_{i_j})+{\eta }_Z\\ & =\sum _{\ell =1}^{j}H(Y_{\supseteq A}\mid X_{i_{\ell }})+(j-1){\eta }_Z.\end{array}$$

The second line uses the induction hypothesis and Exercise 2.7. This completes the induction. At $j=k$, Exercise 2.8 gives ${\mathcal{G}}_k=\supseteq A$, hence

$$H(Y_{\supseteq A}\mid Z_{\supseteq A})\le \sum _{i\in A}H(Y_{\supseteq A}\mid X_i)+(|A|-1){\eta }_Z.$$

For $|A|=1$ this is exactly the observable-transfer inequality, so no intersection or Markov error is required. There are $k$ reconstruction errors and $k-1$ Markov defects. Bounding each reconstruction error by $\delta$ and each Markov defect by $\eta$ gives $k\delta +(k-1)\eta$, or $(2k-1)\epsilon$ for a common budget.

If $Y,Z$ are perfect condensations, each reconstruction error is zero: for every $C\supseteq A$ and $i\in A$, reconstruction says $Y_C$ is a function of $X_i$. The finite tuple of such variables is consequently a function of $X_i$. Also ${\eta }_Z=0$. The inequality gives zero conditional entropy in the forward direction. Interchanging $Y,Z$, using reconstruction in $Z$ and ${\eta }_Y=0$, proves the reverse direction. Zero conditional entropy is almost-sure deterministic recoverability in our finite setting.

The proof uses LVM in $Z$ for Exercise 2.7, reconstruction in $Y$ to bound those errors, and the Markov condition of $Z$ at intersections.

Finally, approximate errors for individual latents do not directly give the same error for a tuple. For example, if two independent fair bits $R,T$ remain unknown given a constant observation, each conditional entropy is one bit but the tuple's is two bits. Conditional subadditivity gives a sum of the individual budgets, not a single budget. The theorem states its hypothesis in terms of tower errors to avoid this ambiguity.

2.4 Why an agent would want these conditions

The correspondence theorem is meant to show when the latents of different agents correspond, so the conditions should not be motivated by correspondence itself. They should serve a single agent's own interests. This section gives two such readings.

The conditioned score. Suppose an agent stores each latent given the more general ones, and answers a query about an observation block $B$ by reading every latent active for $B$, most general first. Its expected description length is the conditioned score

$$\chi (B)=\sum _{A\in {\mathcal{J}}_B}H(Y_A\mid Y_{\supseteq A\setminus \{A\}}).$$

Every strict superset of an address meeting $B$ also meets $B$, so the conditioning is available when reading in reverse inclusion order. Put $V_B=\chi (B)-H(Y_{{\mathcal{J}}_B})$. Then

The second term charges latent information not recoverable from $X_B$. The first charges dependence not accounted for by the inclusion hierarchy. It vanishes under the Markov condition. Exercise 2.12 proves the decomposition.

An agent that answers queries about a block $B$ pays $\chi (B)$, and no latent model does better than $H(X_B)$. The gap splits into exactly our two defects. Short descriptions for the queries an agent cares about are small defects. For $i\in A$, the singleton gap $\chi (\{i\})-H(X_i)$ bounds $H(Y_{\supseteq A}\mid X_i)$, the reconstruction hypothesis of Theorem 2.6 (Exercise 2.12). So the conditions need not be assumed as a coincidence: efficient agents buy them. Efficiency is relative to the blocks an agent actually queries, and there is not always a single model minimizing the score for every block.

Reconstruction: no dead weight. The concept at $A$ is used whenever any observation in $A$ is. Information that only some of those circumstances can use is stored where it is dead weight most of the time the concept is used. The reconstruction error $H(Y_{\supseteq A}\mid X_i)$ measures exactly the part of the concept that a query about $X_i$ pays for but cannot pin down. In the top-latent model of Exercise 2.2, $Y_{\{1,2,3\}}=(S,P,Q)$ carries the bit $Q$, which is dead weight whenever the concept is used for $X_1$.

Markov: local inference. The Markov term also has a reading that does not mention description length. Once the more general concepts are known, a concept should bear only on the observations in its own scope:

Then when the agent learns or revises something about the concept at $A$, it never has to revise its beliefs about observations outside $A$, except through $A$'s more general context. Given LVM and reconstruction, (6) holds for every address exactly when the Markov condition does.

Exercise 2.10 (★) (Local inference; 15 minutes). (a) In the singleton-copy model of Exercise 2.2, compute the left side of (6) for $A=\{1\}$.

(b) Let $I=\{1,2,3\}$, let $U$ be a fair bit, and set $X_1=X_2=X_3=U$. File $U$ at every pair address, $Y_{\{1,2\}}=Y_{\{1,3\}}=Y_{\{2,3\}}=U$, with every other latent constant. Check LVM and reconstruction. Compute the left side of (6) for $A=\{1,2\}$, and find upward-closed families violating the Markov condition. Where should $U$ be filed instead?

(c) Prove that the Markov condition implies (6). Apply Definition 2.4 to $\mathcal{F}=\supseteq A$ and $\mathcal{G}={\mathcal{J}}_{I\setminus A}$, and identify their intersection.

(d) Assume reconstruction. Show that $Y_{{\mathcal{J}}_{I\setminus A}}$ and $X_{I\setminus A}$ determine one another. Conclude that (6) for every $A$ is the local version of the Markov condition stated after Definition 2.4.

Solution

(a) Here $Y_{\{1\}}=X_1=(S,P)$ and every strict superset of $\{1\}$ holds a constant, so the left side is $I(X_1;X_2,X_3)$. The pair $(X_2,X_3)$ determines $S,P,Q$, hence $X_1$, so this is $H(X_1)=2$. The concept at $\{1\}$ carries two bits about observations outside its scope that no more general concept accounts for.

(b) Each observation equals a latent assigned to it, for example $X_1=Y_{\{1,2\}}$, so LVM holds. Every nonconstant latent equals $U=X_i$ for each $i$ in its address, so reconstruction holds. The only strict superset of $\{1,2\}$ is $\{1,2,3\}$, whose latent is constant, so the left side is $I(U;U)=1$. For $\mathcal{F}=\supseteq \{1,2\}$ and $\mathcal{G}=\supseteq \{1,3\}$ the intersection is $\{\{1,2,3\}\}$, and $I(Y_{\mathcal{F}};Y_{\mathcal{G}}\mid Y_{\{1,2,3\}})=I(U;U)=1$. The bit $U$ is shared by all three observations, so it belongs at the top address: $Y_{\{1,2,3\}}=U$ with every other latent constant is a perfect condensation.

(c) An address $C$ meets $I\setminus A$ exactly when $C⊈A$. So $\supseteq A\cap {\mathcal{J}}_{I\setminus A}$ consists of the addresses that contain $A$ but are not contained in it: the strict supersets of $A$. Both families are upward closed, so the Markov condition gives

$$I(Y_{\supseteq A};Y_{{\mathcal{J}}_{I\setminus A}}\mid Y_{\supseteq A\setminus \{A\}})=0.$$

The tuple $Y_A$ is part of $Y_{\supseteq A}$, and by LVM $X_{I\setminus A}$ is a function of $Y_{{\mathcal{J}}_{I\setminus A}}$, which contains $Y_{\supseteq \{j\}}$ for every $j\notin A$. Conditional mutual information cannot increase when either side is replaced by a function of it, so the left side of (6) is zero.

(d) Every $C\in {\mathcal{J}}_{I\setminus A}$ contains some $j\notin A$, and reconstruction makes $Y_C$ a function of $X_j$. So $Y_{{\mathcal{J}}_{I\setminus A}}$ is a function of $X_{I\setminus A}$, and the previous part gave the converse. The left side of (6) therefore equals $I(Y_A;Y_{{\mathcal{J}}_{I\setminus A}}\mid Y_{\supseteq A\setminus \{A\}})$. The family ${\mathcal{J}}_{I\setminus A}$ consists of the strict supersets of $A$, on which we condition, and the addresses incomparable with $A$. So the quantity vanishes exactly when $Y_A$ is conditionally independent of the incomparable latents given its strict supersets. Required for every $A$, this is the local version of the Markov condition, which is equivalent to it.

2.5 Optional: several observations as one witness

A shared parameter need not be recoverable from a single observation. For example, take $n\ge 2$, let $L$ be a fair bit, and set $X_i=L\oplus N_i$, where the $N_i$ are independent Bernoulli$(q)$ noises with $0<q<1/2$, independent of $L$. The model $Y_I=L$, $Y_{\{i\}}=X_i$ satisfies LVM and the Markov condition exactly, but $H(L\mid X_i)=h_2(q)>0$, where $h_2$ is the binary entropy function of Section 2.2.1. Larger observation blocks can reveal more about $L$. To use them in the proof, replace $\supseteq \{i\}$ by ${\mathcal{J}}_B$.

Exercise 2.11 (Block witnesses; optional, 25 minutes). (a) Let $I=\{1,2,3\}$ and suppose a target $U$ has conditional entropy at most $\delta$ given each of $X_{\{1,2\}}$, $X_{\{1,3\}}$, and $X_{\{2,3\}}$. Which addresses survive the intersection ${\mathcal{J}}_{\{1,2\}}\cap {\mathcal{J}}_{\{1,3\}}\cap {\mathcal{J}}_{\{2,3\}}$? Prove a bound on the entropy of $U$ given the surviving $Z$-latents.

(b) More generally, let $\mathcal{W}$ be a nonempty finite family of nonempty observation blocks. Adapt Exercise 2.9 to show

$$H(U\mid Z_{\mathcal{R}})\le \sum _{B\in \mathcal{W}}H(U\mid X_B)+(|\mathcal{W}|-1){\eta }_Z,\mathcal{R}=\bigcap _{B\in \mathcal{W}}{\mathcal{J}}_B.$$

(c) Fix an integer $0\le r<|A|$ and take every $(r+1)$-element subset of $A$ as a witness. Show that $C\in \mathcal{R}$ exactly when $|A\setminus C|\le r$. What does this give for $r=0$? Why is $\mathcal{R}$ generally larger for $r>0$?

Solution

(a) A nonempty address $C\subseteq \{1,2,3\}$ meets each of $\{1,2\},\{1,3\},\{2,3\}$ precisely when $|C|\ge 2$. A singleton misses the complementary pair; every address with at least two elements meets every pair. Thus the surviving tuple consists of the three pair latents and the top latent. Applying the two-witness lemma twice, after observable transfer for each block, gives

$$H(U\mid Z_{\{C:|C|\ge 2\}})\le 3\delta +2{\eta }_Z.$$

It does not isolate the top latent alone.

(b) For each block $B$, the family $Z_{{\mathcal{J}}_B}$ determines $X_B$: for every $i\in B$ it contains $Z_{\supseteq \{i\}}$. Exercise 2.7 therefore extends to $H(U\mid Z_{{\mathcal{J}}_B})\le H(U\mid X_B)$. Each ${\mathcal{J}}_B$ is upward closed. Enumerate $\mathcal{W}=\{B_1,\dots ,B_N\}$ and intersect the first $j$ contributing families. Exactly the induction in Exercise 2.9, now with these families as leaves, gives

$$H(U\mid Z_{\mathcal{R}})\le \sum _{B\in \mathcal{W}}H(U\mid X_B)+(N-1){\eta }_Z,\mathcal{R}=\bigcap _{B\in \mathcal{W}}{\mathcal{J}}_B.$$

For $N=1$ this is just the transfer inequality. We required a nonempty family so the induction and the intersection count apply.

(c) An address $C$ fails to meet some $(r+1)$-subset of $A$ exactly when $A\setminus C$ contains at least $r+1$ elements. Thus it meets every such subset exactly when $|A\setminus C|\le r$. For $r=0$ this says $A\subseteq C$, recovering the tower. For $r>0$ an address can survive even if it misses some elements of $A$; $\mathcal{R}$ is a larger family. If every witness error is at most $\delta$, write $N=\left(\genfrac{}{}{0ex}{}{|A|}{r+1}\right)$ to obtain the explicit bound $N\delta +(N-1){\eta }_Z$. The restriction $r<|A|$ ensures witnesses exist.

Eisenstat's almost-perfect condensation (Eisenstat 2025) builds in block witnesses of this kind, with a threshold $r$ on $|A\cap B|$ that lets small latents absorb local noise.

2.6 Optional: more on the conditioned score

Compare the conditioned score of Section 2.4 with the simple score

$$\sigma (B)=\sum _{A\in {\mathcal{J}}_B}H(Y_A),$$

which charges each latent active for $B$ separately, ignoring what the more general latents already say. Both are ideal expected description-length quantities.

For a graphical-model expression, define

$$q_B(y)=\prod _{A\in {\mathcal{J}}_B}p(y_A\mid y_{\supseteq A\setminus \{A\}}).$$

This is a normalized distribution: sample larger addresses before smaller ones. Conditional kernels on probability-zero parent configurations can be chosen arbitrarily. Direct expansion gives $V_B=D_{\mathrm{KL}}(p_{Y_{{\mathcal{J}}_B}}\Vert q_B)$. Thus (5) separates two nonnegative defects.

Exercise 2.12 (The two charges; optional, 25 minutes). (a) Order ${\mathcal{J}}_B$ so strict supersets appear first. Use the chain rule and conditioning inequality to prove $\chi (B)\ge H(Y_{{\mathcal{J}}_B})$.

(b) Use LVM to prove $H(Y_{{\mathcal{J}}_B})-H(X_B)=H(Y_{{\mathcal{J}}_B}\mid X_B)$, hence (5).

(c) For both models in Exercise 2.4, calculate $\sigma (\{1,2\})$ and $\chi (\{1,2\})$. Why is copying the top variable into a lower latent free under one score but not the other?

(d) If $A\cap B\ne \varnothing$, show that $H(Y_{\supseteq A}\mid X_B)\le \chi (B)-H(X_B)$.

(e) Prove that a latent model is a perfect condensation exactly when $\chi (B)=H(X_B)$ for every nonempty block $B$, which is Eisenstat's definition.

Solution

(a) List ${\mathcal{J}}_B$ as $A_1,\dots ,A_q$ with strict supersets appearing before subsets. Such an order exists because strict inclusion has no cycles. Every strict superset of an active address also meets $B$, so is in this list. Therefore

$$H(Y_{A_t}\mid Y_{\supseteq A_t\setminus \{A_t\}})\ge H(Y_{A_t}\mid Y_{A_1},\dots ,Y_{A_{t-1}}).$$

Summing and applying the chain rule gives $\chi (B)\ge H(Y_{{\mathcal{J}}_B})$, hence $V_B\ge 0$.

(b) Since $Y_{{\mathcal{J}}_B}$ determines $X_B$, the joint entropy can be expanded in two ways:

$$H(X_B,Y_{{\mathcal{J}}_B})=H(Y_{{\mathcal{J}}_B})=H(X_B)+H(Y_{{\mathcal{J}}_B}\mid X_B).$$

Subtracting $H(X_B)$ and adding $V_B$ proves

$$\chi (B)-H(X_B)=V_B+H(Y_{{\mathcal{J}}_B}\mid X_B).$$

(c) In Exercise 2.4, the independent model $Y$ has simple score $1+1+1=3$ and conditioned score $1+1+1=3$. In model $Z$, the simple score is $1+2+2=5$, while the conditioned score is

$$H(C)+H(C,R\mid C)+H(C,T\mid C)=1+1+1=3.$$

Both models determine $X_1,X_2$, whose joint entropy is three. The conditioned score charges only the extra information below $C$; its copies add zero conditional entropy. The simple score charges those copies again.

(d) If $A\cap B\ne \varnothing$, every $C\supseteq A$ meets $B$. Thus $Y_{\supseteq A}$ is a subtuple of $Y_{{\mathcal{J}}_B}$ and

$$H(Y_{\supseteq A}\mid X_B)\le H(Y_{{\mathcal{J}}_B}\mid X_B)\le \chi (B)-H(X_B),$$

where the last inequality uses the nonnegative score decomposition.

(e) Let $V_I=\chi (I)-H(Y_{{\mathcal{P}}^{+}(I)})$. For upward-closed $\mathcal{F},\mathcal{G}$, partition ${\mathcal{P}}^{+}(I)$ into

$$\mathcal{C}=\mathcal{F}\cap \mathcal{G},\mathcal{P}=\mathcal{F}\setminus \mathcal{G},\mathcal{Q}=\mathcal{G}\setminus \mathcal{F},\mathcal{R}={\mathcal{P}}^{+}(I)\setminus (\mathcal{F}\cup \mathcal{G}).$$

Order these blocks $\mathcal{C},\mathcal{P},\mathcal{Q},\mathcal{R}$, internally by reverse inclusion. Upward closure ensures this order is valid and no latent in $\mathcal{Q}$ has a strict superset in $\mathcal{P}$, or conversely. Conditioning inequalities and chain rules within each block imply

$$\begin{array}{rl}\chi (I)& \ge H(Y_{\mathcal{C}})+H(Y_{\mathcal{P}}\mid Y_{\mathcal{C}})+H(Y_{\mathcal{Q}}\mid Y_{\mathcal{C}})+H(Y_{\mathcal{R}}\mid Y_{\mathcal{C}},Y_{\mathcal{P}},Y_{\mathcal{Q}})\\ & =H(Y_{{\mathcal{P}}^{+}(I)})+I(Y_{\mathcal{P}};Y_{\mathcal{Q}}\mid Y_{\mathcal{C}}).\end{array}$$

The latter mutual information equals $I(Y_{\mathcal{F}};Y_{\mathcal{G}}\mid Y_{\mathcal{F}\cap \mathcal{G}})$. Hence ${\eta }_Y\le V_I$.

If all score gaps vanish, the decomposition forces $V_I=0$, giving the Markov condition. The singleton gap at $B=\{i\}$ forces the contributing tuple, and therefore each latent at an address containing $i$, to be determined by $X_i$. This gives reconstruction.

Conversely, suppose reconstruction and the Markov condition hold. For every $B$, each active latent $Y_A$ is determined by some $X_i$ with $i\in A\cap B$, and hence by $X_B$. Therefore $H(Y_{{\mathcal{J}}_B}\mid X_B)=0$. In a reverse-inclusion order, the earlier latents consist of all strict supersets of the current latent and some incomparable latents. The global Markov condition implies that conditioning on these extra earlier latents does not reduce its entropy beyond conditioning on strict supersets: apply the condition to the upward cone of the current address and the upward-closed family of earlier addresses. Their intersection is the strict-superset family. Thus the score's chain-rule inequality is an equality, $V_B=0$. The decomposition gives $\chi (B)=H(X_B)$ for all $B$.

Small score gaps therefore force small defects. The converse for Eisenstat's positive-threshold version needs extra reconstruction coverage (Benson 2026).

3. A hierarchical clustering example

3.1 Thirty-six observations

There are two groups, each containing two clusters, each with nine observations. Write $X_{gcj}$ for the $j$th two-dimensional point in cluster $c$ of group $g$. The labels $(g,c,j)$ and memberships are fixed. We are comparing models of this labeled family, not inferring an unknown partition of an unlabeled cloud.

The parameters are a global shape $S$, group centers $G_1,G_2$, and cluster centers $M_{gc}$. Given these parameters, the 36 observations are independent. Marginalizing over shared parameters generally makes observations dependent. The plotted cloud in Figure 1 is one realization; the random variables and their entropies refer to the joint law across realizations.

3.2 An explicit finite law

Let $D=\{0,\dots ,200{\}}^2$. Draw $S$ uniformly from three shape labels, and draw $G_1,G_2$ independently and uniformly from $\{60,\dots ,140{\}}^2$, independently of $S$. Conditional on $G_g$, draw its two centers independently:

$$P(M_{gc}=m\mid G_g=a)\propto \exp \left(-\frac{\Vert m-a{\Vert }^2}{128}\right),m\in D.$$

Given $S$ and all centers, draw the observations independently, using

$$P(X_{gcj}=x\mid M_{gc}=m,S=s)\propto \exp \left(-\frac{1}{2}(x-m{)}^{\mathsf{T}}{Q}_s^{-1}(x-m)\right),x\in D,$$

where

$$Q_{\mathrm{round}}=\left(\begin{array}{cc}5& 0\\ 0& 5\end{array}\right),Q_{\mathrm{right}}=\left(\begin{array}{cc}25& 20\\ 20& 25\end{array}\right),Q_{\mathrm{left}}=\left(\begin{array}{cc}25& -20\\ -20& 25\end{array}\right).$$

Each proportionality means normalization by the sum over $D$. These are probability mass functions on a finite grid. The matrices control shape; they are not the exact covariances after discretization and boundary truncation. Every grid point has positive probability. Cluster centers tend to lie near their group center, but the four components need not be visually separated in every realization.

3.3 A structured latent model

Let $I$ contain all 36 indices. Let $A_g$ be the 18 indices of group $g$, and $A_{gc}$ the nine indices of cluster $(g,c)$. Assign

$$Y_I=S,Y_{A_g}=G_g,Y_{A_{gc}}=M_{gc},Y_{\{i\}}=X_i,$$

and make every other latent constant. The joint law factorizes in the address inclusion order, so its Markov defect is zero.

LVM holds exactly because the singleton latent supplies the sampled point itself. The cluster center and shape alone only specify a distribution for the point, leaving residual conditional entropy $H(X_i\mid M_{gc},S)$.

Reconstruction is different. All the kernels have full support, so any finite observation block leaves several parameter configurations with positive posterior probability. For example, $H(M_{gc}\mid X_i)>0$. The model's joint law satisfies the Markov condition exactly, but it is not a perfect condensation. Since every combination of points has positive probability and the points are dependent, no latent model of this law is (Exercise 2.3).

For a nonempty block $B$, the general score-gap identity (5) is

$$\chi (B)-H(X_B)=[\chi (B)-H(Y_{{\mathcal{J}}_{\mathcal{B}}})]+H(Y_{{\mathcal{J}}_{\mathcal{B}}}\mid X_B).$$

Here the bracketed Markov term is zero. The gap is the latent information remaining uncertain after observing the queried block.

3.4 Three organizations of the same observable law

For a nonempty queried observation block $B$, the conditioned score sums the charges of all latents active for $B$.

One global tuple. Put $Z_I=X_I$ and make every other latent constant. The global latent determines each observation. This is the top-latent model of Exercise 2.2 at scale: it satisfies the Markov condition but fails reconstruction. For every nonempty $B$,

$${\chi }_{\mathrm{global}}(B)=H(X_I),{\chi }_{\mathrm{global}}(B)-H(X_B)=H(X_I\mid X_B).$$

This attains the entropy bound when querying the whole tuple. Even a singleton query incurs the entire tuple's entropy in this score.

An ordered chain. Choose an ordering $X_1,\dots ,X_{36}$. Set $Z_{\{j,j+1,\dots ,36\}}=X_j$ and make other latents constant. The contributing latents for $X_i$ contain $X_1,\dots ,X_i$. The charge for the latent holding $X_j$ is $H(X_j\mid X_1,\dots ,X_{j-1})$, hence

$${\chi }_{\mathrm{chain}}(B)=H(X_1,\dots ,X_{\max B}).$$

This attains the entropy bound for prefix queries. Querying only $X_{36}$ costs $H(X_I)$.

The structured model. The score charges the shape once, the group and cluster parameters needed by $B$, and the residual uncertainty of each requested observation:

$$\begin{array}{rl}{\chi }_{\mathrm{structured}}(B)=& H(S)+\sum _{g:B\cap A_g\ne \varnothing }H(G_g)\\ & +\sum _{g,c:B\cap A_{gc}\ne \varnothing }H(M_{gc}\mid G_g)+\sum _{i\in B}H(X_i\mid M_{g(i)c(i)},S).\end{array}$$

This expression avoids charging for unrelated observations. It need not be smaller than the other scores for every block. In particular, for $B=I$ it exceeds $H(X_I)$ by the remaining parameter uncertainty, whereas both baseline constructions attain $H(X_I)$. Fitting the observable law does not by itself settle which organization is preferable across queries.

Exercise 3.1 (The three organizations and the conditions; optional, 10 minutes). (a) Show that the global and chain models satisfy the Markov condition. Why is it automatic for the chain?

(b) For a single point $X_i$, describe the reconstruction error $H(Z_{\supseteq \{i\}}\mid X_i)$ in each of the three models. How does it depend on $i$ in the chain, and on the number of observations in each model?

(c) None of the three models is a perfect condensation. Which comes closest to satisfying the conditions with a small tolerance?

Solution

(a) In the global model every nonempty upward-closed family contains the top address, whose latent is the only nonconstant one, so every Markov term conditions on everything, as in Exercise 2.2. In the chain, the nonconstant addresses $\{j,\dots ,36\}$ are nested, so an upward-closed family contains exactly those with $j$ up to some bound: its nonconstant latents are $X_1,\dots ,X_a$ for some $a$. Of two such families, one's nonconstant latents are then those of the intersection, and the Markov term vanishes.

(b) In the global model the tower above $\{i\}$ is $X_I$, so the error is $H(X_I\mid X_i)$: the uncertainty about all other points, which grows with their number. In the chain the tower is $(X_1,\dots ,X_i)$, so the error is $H(X_1,\dots ,X_{i-1}\mid X_i)$: zero for the first point and growing along the ordering. In the structured model the tower is $(S,G_g,M_{gc},X_i)$, so the error is $H(S,G_g,M_{gc}\mid X_i)$: the parameter uncertainty a single point leaves, which does not grow with the number of observations.

(c) The structured model. It satisfies the Markov condition exactly, and its reconstruction errors are bounded by the parameter uncertainty one point leaves, uniformly in $i$ and in the number of points. With a tolerance of that size, or a smaller one using block witnesses (Section 2.5), it satisfies the approximate conditions; the other two models' errors grow with the number of points.

3.5 Why blocks help recover parameters

For nonempty $B$ inside a fixed cluster $(g,c)$, set $\Theta =(S,G_g,M_{gc})$. The nonconstant contributing tuple is $(\Theta ,X_B)$, so

$${\chi }_{\mathrm{structured}}(B)-H(X_B)=H(\Theta \mid X_B).$$

For nonempty $B\subseteq B^{\prime }\subseteq A_{gc}$, the reduction in this gap is

$$H(\Theta \mid X_B)-H(\Theta \mid X_{B^{\prime }})=I(\Theta ;X_{B^{\prime }\setminus B}\mid X_B)\ge 0.$$

More points can inform the shared parameters. Exact recovery still fails for finite blocks. Even knowing one cluster center need not determine its parent group center. This example motivates block witnesses (Section 2.5).

Source. The motivating hierarchy is from Gillen and Chiang, A summary of Condensation and its relation to Natural Latents (Gillen & Chiang 2026), §1.1.1. The finite law, illustration, and exact score comparisons above are this course's adaptation.

4. Condensation in context

4.1 What the result says

LVM alone leaves considerable freedom. The additional reconstruction and Markov conditions constrain where shared information can reside. The correspondence theorem compares two models satisfying these conditions, that is, two joint laws extending the same observable law: their towers at the same address determine one another, exactly or with a controlled conditional-entropy error. The theorem does not give a learning algorithm, and a perfect condensation need not exist, as Section 2.2.1 shows.

This provides a conditional sense of objectivity: once the observables and the conditions are fixed, agreement in information content follows from each model's relationship to the observations, not from a shared vocabulary. The theorem does not choose the observables, and changing them may change the information that must correspond.

4.2 Connections to prior work

4.2.1 Natural latents

Wentworth and Lorell ask when one agent's latent is guaranteed to be a function of another's (Wentworth & Lorell 2025). A latent $\Lambda$ over observables $X_1,\dots ,X_n$ is a mediator if the $X_i$ are independent given $\Lambda$, and a redund if it is determined by each $X_i$ individually; a natural latent is both. Their first theorem, that a mediator determines any redund, is for two observations the two-witness lemma (Lemma 2.8) with the observations as witnesses. Two natural latents over the same observables therefore determine one another.

For two observations, the top latent of a perfect condensation is a natural latent: reconstruction makes $Y_{\{1,2\}}$ a redund, and the Markov condition with LVM makes $X_1,X_2$ independent given it. Condensation asks for a latent at every address rather than one latent for the whole family, and its correspondence theorem compares all the towers at once. Gillen and Chiang show that natural-latent agreement is a special case of condensation's agreement theorem (Gillen & Chiang 2026).

4.2.2 Sufficient statistics

For a fixed joint law of $(X,V)$, a statistic $T=f(X)$ is sufficient for predicting $V$ when

$$I(X;V\mid T)=0.$$

Knowing $X$ then gives no predictive information about $V$ beyond $T$. For finite alphabets, grouping values $x$ with the same conditional distribution $P(V\mid X=x)$ gives a minimal such statistic, on the support of $X$. This differs from parametric sufficiency, where the conditional law of the sample given a statistic must be independent of the unknown parameter. Both formulations ask which distinctions must be retained for an inference task.

Predictive sufficiency does not say that $T$ determines the realized value of $V$. Condensation's LVM condition does demand determination, using the whole contributing family, including residual variables.

A sufficient statistic is by construction a function of $X$. A latent need not be, because reconstruction is asked for only up to a defect: that leaves room for latents which are parameters of a law rather than functions of the observations. The additional question here is how to organize a family of latent parts across many specified observables. See Fisher 1922 and Shalizi's account of predictive sufficiency (Shalizi 2019).

4.2.3 Common information

Two older questions distinguish requirements that appear together in the perfect case. The maximal deterministic common part of $X_1,X_2$ is a variable $K$ recoverable from either observation, through which every other common function factors. Its entropy is the Gacs–Korner common information. Wyner's common information instead minimizes $I(X_1,X_2;W)$ over extensions satisfying $X_1\perp X_2\mid W$. Such a $W$ need not be separately recoverable from the observations.

If $W$ is both separately recoverable and screens off dependence, then

$$I(X_1;X_2)=H(W)+I(X_1;X_2\mid W)=H(W).$$

Moreover, every common function $K$ is determined by $W$: the two-witness lemma, with witnesses $X_1,X_2$ and common part $W$, gives $H(K\mid W)=0$. So $W$ is the Gacs–Korner common part, and the three quantities coincide: the Gacs–Korner common information, Wyner's common information and $I(X_1;X_2)$ all equal $H(W)$. For two observations, the top latent of a perfect condensation is such a $W$.

It is restrictive: for the noisy pair of Section 2.2.1, every common function is constant although $I(X_1;X_2)=1-h_2(q)>0$. Recoverable common information and mutual information differ.

Condensation extends this from two observations to a family of subset-addressed latents. See G'acs & K"orner 1973 and Liu, Xu and Chen's extension of Wyner's common information (Liu et al. 2010).

4.2.4 Computational mechanics

Computational mechanics groups past histories according to their conditional distributions over futures. Its causal states have predictive optimality, minimality, and uniqueness properties. This is an important precedent for characterizing such a construction through informational requirements.

The present setup starts from a family of jointly distributed questions rather than a distinguished past/future split, and its formulation is static: time and learning are not required. It characterizes families of latents associated with different observable subsets. See Shalizi & Crutchfield 2001.

4.2.5 Graphical models and the information bottleneck

The Markov condition in condensation is a graphical-model condition. A subset-ordered directed graph places larger addresses above smaller ones. Under the corresponding factorization, the latent joint law is

$$P(y)=\prod _{A\ne \varnothing }P(y_A\mid y_{⊋A}).$$

A factorization alone does not ensure that observations recover the latents, or that different latent models correspond. Those are additional requirements. Eisenstat discusses this connection explicitly in Definition 5.8 and Example 6.3 of the condensation paper (Eisenstat 2025).

The information bottleneck compresses an input $X$ into $T$ while retaining information about a specified relevance variable $V$. A standard objective is

$$I(X;T)-\beta I(T;V),T\perp V\mid X.$$

Our condensation problem instead involves many addressed latents, LVM, and conditions across observable sets. See Tishby et al. 1999.

4.3 What information theory leaves out

4.3.1 An encoding and access to its inverse

Let $X$ be uniform on $\{1,\dots ,N\}$ and let $Y=\pi (X)$ for a fixed permutation $\pi$. Then

$$H(X\mid Y)=H(Y\mid X)=0.$$

This is exact correspondence whether $\pi$ is the identity or a large unstructured lookup table. The entropies do not charge for describing the table, learning it, storing it, or using it. For a finite table an inverse exists and is computable; that does not make it available to a particular learner.

For a concrete learning distinction, draw $\pi$ uniformly from all permutations and reveal $m<N$ distinct input–output pairs. Conditional on those pairs, the image of a previously unseen input is uniform over the $N-m$ unused outputs. The best success probability without further information is $1/(N-m)$. For every fixed permutation the correspondence entropy is zero, yet a learner with few examples cannot predict an unseen pairing.

Computation is a separate question, even when a transformation has a short known description. Fix a large prime $p$ and a generator $g$ of the multiplicative group modulo $p$, and let $Y=g^X\mathrm{mod}p$ for $X$ uniform on $\{1,\dots ,p-1\}$. Then $X$ and $Y$ determine one another, and the map has a one-line description that is fast to compute. Inverting it is the discrete-logarithm problem, believed to be hard for suitable $p$. Entropy does not see the difference.

4.3.2 Rare events and average error

Let $E\sim \mathrm{Bernoulli}(p)$. Define $R=0$ when $E=0$ and, when $E=1$, let $R$ be uniform over $M$ other values. Since $R$ reveals $E$,

$$H(R)=h_2(p)+p{\log }_{2}M.$$

For $p=10^{-6}$ and $M=2^{10^6}$, the rare branch contributes one full bit. An independent sample of size $m$ misses that branch with probability $(1-p{)}^m$. Large informational contributions can be absent from a small dataset.

Conversely, suppose a variable $T$ records $E$, and records the value of a fair bit $D$, independent of $E$, only when $E=0$. Then

$$H(D\mid T)=p.$$

The average uncertainty is small, but conditional on the rare event $E=1$, the bit is entirely unknown. Entropy is an average informational quantity, not a measure of the consequences of errors.

These examples distinguish informational equivalence, statistical access, and performance on important cases. A useful translation needs guarantees about all three.

4.4 The connection to AI safety

1. Corresponding information. Under the reconstruction and Markov conditions, the theorem gives correspondence between specified families of latents in two models of the same observables.
2. Concepts of actual agents. To apply that result, we need to identify suitable variables in actual agents and establish the relevant conditions, including how their observables relate. The theorem does not show that learning procedures produce such models. That many kinds of agents learn such concepts is a version of the natural abstraction hypothesis (Wentworth 2021).
3. A usable translation. Informational correspondence could support identifying which of an AI's latents carries something humans care about. We must still find the correspondence with available data and computation, and connect it to the particular human distinction of interest. This is the ontology-identification problem at the heart of eliciting latent knowledge (Christiano et al. 2021).
4. Interpretation and specification. A usable translation could help interpret predictions or express objectives in an AI's world model. This requires preserving relevant distinctions when circumstances or models change.
5. Safer systems. Better interpretation and specification could improve oversight and alignment. Sharing concepts does not entail sharing values, reporting faithfully, or following an intended objective.

The first step is the mathematical result of this lesson. The subsequent steps state a research program and the additional work required to connect it to safety.

4.5 Discussion

1. Comparing with prior work. Choose a comparison from Section 4.2. State one mathematical similarity and one difference in what is being characterized. If it relates to one of the condensation conditions, say how.
2. Choosing the questions. Consider two agents describing the same physical system, one using local measurements and another using a different collection of measurements. What would have to be established before applying a theorem that assumes the same observables? Distinguish changing value labels from changing which distinctions an observable makes. Identify one restriction on observable choice that seems justified for a concrete application.
3. What would count as a useful translation? Suppose two latent tuples $U,V$ satisfy $H(U\mid V)=H(V\mid U)=0$. Specify an additional test that would make this correspondence useful for interpreting a learned model. State what access the test requires: paired samples, interventions, model internals, or a known decoder. Which part of the permutation example would that access resolve?
4. From correspondence to oversight. Choose one human distinction that matters for evaluating an AI's behavior. Trace the steps from a correspondence theorem to an oversight procedure that uses that distinction, using the chain in Section 4.4; say where it breaks. Name a failure that could occur despite exact informational correspondence, and state what additional evidence would address it.

5. Quiz

Take the quiz at this link. The questions are reproduced here because the form cannot typeset mathematics.

5.1 Questions

Use base-two logarithms. In questions 1–3, $S,P,Q$ are independent fair bits and $X_1=(S,P)$, $X_2=(S,Q)$, $X_3=(P,Q)$, with latents $Y_{\{1,2\}}=S$, $Y_{\{1,3\}}=P$ and $Y_{\{2,3\}}=Q$.

1. What is $I(X_1;X_2)$?
   • $0$
   • $1$
   • $2$
   • $3$
2. Same model. What is $H(Y_{\{1,2\}}\mid X_1)$?
   • $0$
   • $1/2$
   • $1$
   • $2$
3. Now put $Y_{\{i\}}=X_i$ at each singleton address, with every other latent constant. Which condition fails?
   • the latent variable model condition (LVM)
   • the reconstruction condition
   • the Markov condition
   • none of them fails
4. Complete the two-witness bound $H(U\mid M)\le H(U\mid M,P)+H(U\mid M,Q)+$ ?
   • $I(P;Q)$
   • $I(P;Q\mid M)$
   • $H(P\mid Q)$
   • $0$
5. In the correspondence theorem with $|A|=k$, suppose every reconstruction error and every Markov defect is at most $\epsilon$. What is the bound on $H(Y_{\supseteq A}\mid Z_{\supseteq A})$?
   • $k\epsilon$
   • $(k-1)\epsilon$
   • $(2k-1)\epsilon$
   • $2k\epsilon$
6. Two corresponding families of latents satisfy $H(U\mid V)=H(V\mid U)=0$. Which of these does that not establish?
   • each family is a function of the other almost surely
   • neither family retains uncertainty about the other
   • an efficient procedure for translating between them
   • the two families carry the same information
7. Let $X_1$ be a fair bit and $X_2=X_1\oplus N$ with $N\sim \mathrm{Bernoulli}(q)$, $0<q<1/2$. Does this pair admit a perfect condensation?
   • yes: put $(X_1,X_2)$ in the top latent
   • yes: put each $X_i$ in its singleton latent
   • no: the top latent must be constant, so the Markov condition would force $X_1,X_2$ to be independent
   • only for small enough $q$
8. $Y$ and $Z$ are perfect condensations of the same observables. Which must determine one another?
   • $Y_{\{1\}}$ and $Z_{\{1\}}$
   • the towers $Y_{\supseteq \{1\}}$ and $Z_{\supseteq \{1\}}$
   • $Y_{\{1,2\}}$ and $Z_{\{1\}}$
   • nothing, in general

6. Further reading

The required mathematics is contained in this sheet and the lectures.

• Sam Eisenstat, Condensation: A Theory of Concepts (2025). Definitions and exact characterization: Sections 4–5. Correspondence: Theorems 5.15 and 6.8; two-witness inequality: Lemma 6.4 (Eisenstat 2025).
• Satya Benson, Relating Almost Perfect Condensation Conditions and the Conditioned Score. The score/condition bridge, and the extra reconstruction coverage its converse needs (Benson 2026).
• Jeremy Gillen and Daniel Chiang, A Summary of Condensation and its Relation to Natural Latents. The source of the clustering example, and the reduction of natural-latent agreement to condensation (Gillen & Chiang 2026).
• John Wentworth and David Lorell, Natural Latents: Latent Variables Stable Across Ontologies (Wentworth & Lorell 2025); John Wentworth, Testing the Natural Abstraction Hypothesis (Wentworth 2021).
• For the wider statistical context: Cover and Thomas, Elements of Information Theory (Cover & Thomas 2006); Lauritzen, Graphical Models (Lauritzen 1996); Shalizi and Crutchfield, Computational Mechanics: Pattern and Prediction, Structure and Simplicity (Shalizi & Crutchfield 2001).

References