Variational complexity-constrained max-info strategy recovery

1. Purpose

The baseline max-info theory shows that, for an exact factorization

$$p(y\mid x)=\sum_z r(z\mid x)g(y\mid x,z),$$

the objective satisfies

$$I(Y;Z\mid X)=H(Y\mid X)-H(Y\mid X,Z).$$

Thus max-info minimizes residual generator entropy. In highly expressive classes, this is often degenerate: if deterministic simulators exist, max-info selects them, and the latent variable can behave like a random seed rather than a semantically meaningful strategy.

In this note, we consider a different selection principle Instead of asking only for a high-information latent, we ask for a high-information latent whose induced decoder is simple. The guiding principle is

$$\text{strategy} = \text{the most informative latent whose induced decoder is simple.}$$

The central idea is that many high-info latent variables exist, but most arbitrary high-entropy partitions induce complicated conditional generators. A genuine reasoning strategy should be useful because conditioning on it makes the output distribution simpler to generate by a reusable mechanism.

The theory is intentionally abstract about the complexity measure. The functional $C$ should be read as an idealized proxy for the inductive biases of a model architecture and optimization procedure. Different architectures may induce different $C$'s; the theorem characterizes what latent structure is recovered as a function of that bias.

This note develops a series of simple but hopefully insightful results.

The key messages are:

• a low-$\beta$ ELBO is information-seeking;
• a decoder-complexity penalty selects simple strategy-like generators among high-information latents;
• if the information-complexity gap is positive, then population and empirical ELBO minimization recover the reference strategy;
• the sample complexity scales inversely with the square of the population recovery gap, and also with $(1-\beta)^{-2}$.

Throughout, $X,Y$ are finite, $p(y\mid x)$ is the data conditional law, and $\mu$ is the input law. All expectations are under $(X,Y)\sim \mu(x)p(y\mid x)$ unless otherwise stated.

---

2. Setup

Let $X,Y$ be finite, with fixed input law $\mu$ on $\mathcal X$ and fixed conditional law $p(y\mid x)$ on $\mathcal Y$. All entropies and mutual informations are computed under

$$X\sim \mu, \qquad Y\sim p(\cdot\mid X).$$

Fix a latent cardinality $K$ and write $\mathcal Z = [K]$. We assume that the latent state is a deterministic function of the complete reasoning trace $(X, Y)$, and consider a class of latent states $\Phi_K: \mathcal X \times \mathcal Y \to \mathcal Z$ of such functions. Intuitively, this setting corresponds to the intuitive condition that each reasoning trace has a unique strategy. I.e., you can deterministically tell whether a proof uses a "proof-by-contradiction" or a "proof-by-induction" strategy by observing the proof.

\begin{proof} Feasibility follows from the law of total probability:

$$p(y\mid x)=\sum_z \mathbb P(\phi(x,Y)=z\mid X=x)\,p(y\mid x,\phi(x,Y)=z).$$

Since $Z_\phi=\phi(X,Y)$ is deterministic given $(X,Y)$, $H(Z_\phi\mid X,Y)=0$. Therefore

$$I(Y;Z_\phi\mid X)=H(Z_\phi\mid X)-H(Z_\phi\mid X,Y)=H(Z_\phi\mid X).$$

\end{proof}

We write

$$I(\phi):=I(Y;Z_\phi\mid X)=H(Z_\phi\mid X).$$

3. Abstract Decoder Complexity & the Complexity-Constrained Max-Info Objective

Rather than being an arbitrary partition of the output space, a strategy $S$ is an abstract property of the process that generates $Y$ from $X$. We modify the max-info criterion to further prefer attributes whose induced conditional generator is simple.

Let $\{\mathcal G_{\le c}\}_{c\ge 0}$ be a nested family of decoder classes, where $\mathcal G_{\le c}$ contains conditional laws $g(y\mid x,z)$ representable with complexity at most $c$:

$$c\le c' \quad\Longrightarrow\quad \mathcal G_{\le c}\subseteq \mathcal G_{\le c'}.$$

For $\phi\in\Phi_K$, define its decoder complexity by

$$C(\phi):=C(g_\phi):=\inf\{c:g_\phi\in\mathcal G_{\le c}\}.$$

We assume $C$ is invariant under global relabeling of latent names: if $\phi'(x,y)=\pi(\phi(x,y))$ for a fixed permutation $\pi$, then $C(\phi')=C(\phi)$. This encodes the convention that only the partition and generator family matter, not the arbitrary names of latent states.

The complexity is abstract. Examples include:

1. an MDL code length for a program that samples or evaluates $g(y\mid x,z)$;
2. a shared-module representation length for $g(y\mid x,z)=G_\theta(y\mid x,e_z)$;
3. a norm, smoothness, or architecture-dependent complexity of the $z$-conditioned generator family.

This objective says: among all $K$-state attributes whose induced decoder is simple enough, choose the one that captures the most residual uncertainty about $Y$ beyond $X$.

The complexity $C$ is meant to capture the inductive bias of the architecture and optimizer. A low-complexity decoder is one that can be represented by a simple reusable generator, for example a shared module of the form $g(y\mid x,z)=G_\theta(y\mid x,e_z)$, an MDL-short decoder, or a smooth decoder over a task graph.

---

4. Reference Strategy and notions of recovery

Let $S^*$ be a target strategy variable with $K$ states. We assume the completed reasoning trace determines its strategy:

$$S^*=\sigma(X,Y)\in[K].$$

The strategy-induced decoder is

$$g_{S^*}(y\mid x,s):=p(y\mid x,S^*=s),$$

and its complexity is $C^*:=C(S^*):=C(g_{S^*})$.

We define two notions of "recovering" $S^*$. Weak recovery means that we discover a latent $\phi$ that induces the correct partition of the output space $Y$ separately for each input $x$, but where the latent is state is not necessarily aligned with $S^*$ across different inputs. Strong recovery means that there exists a bijection between $S^*$ and $\phi$.

We write $\phi\sim_{\mathrm w}S^\star$ for weak recovery and $\phi\sim_{\mathrm s}S^\star$ for strong recovery.

---

5. Budget-interval recovery without knowing $C^\star$

The earlier constrained theorem used the oracle budget $C^\star:=C(S^\star)$. The following version shows that exact knowledge of $C^\star$ is not necessary. Recovery holds for a full interval of complexity budgets: any budget large enough to include the reference strategy, but too small to include an equally-informative non-strategy latent, recovers the strategy.

Define

$$I^\star:=I(S^\star)=H(S^\star\mid X), \qquad C^\star:=C(S^\star).$$

Define the first bad complexity level

$$B_{\mathrm{bad}} := \inf\{C(\phi):\phi\not\sim_{\mathrm s}S^\star,\ I(\phi)\ge I^\star\}.$$

Thus $B_{\mathrm{bad}}$ is the smallest decoder complexity at which a non-strongly-strategy-equivalent latent can match or exceed the information of $S^\star$.

\begin{proof} Since $C(S^\star)=C^\star\le B$, the reference strategy $S^\star$ is feasible. Hence any optimizer satisfies

$$I(\widehat\phi_B)\ge I(S^\star)=I^\star.$$

Also, by feasibility,

$$C(\widehat\phi_B)\le B<B_{\mathrm{bad}}.$$

If $\widehat\phi_B\not\sim_{\mathrm s}S^\star$, then $\widehat\phi_B$ is a non-strongly-strategy-equivalent latent with $I(\widehat\phi_B)\ge I^\star$ and $C(\widehat\phi_B)<B_{\mathrm{bad}}$, contradicting the definition of $B_{\mathrm{bad}}$. Therefore $\widehat\phi_B\sim_{\mathrm s}S^\star$. \end{proof}

---

5. Penalized frontier recovery

The budgeted objective is analytically clean. A penalized objective is closer to regularized training:

$$\max_\phi \{I(\phi)-\alpha C(\phi)\}.$$

This section gives the corresponding information-complexity frontier condition.

For $\alpha\ge 0$, define

$$J_\alpha(\phi):=I(\phi)-\alpha C(\phi).$$

\begin{proof} Let $\widehat\phi$ be a maximizer. Since $S^\star$ is feasible,

$$J_\alpha(\widehat\phi)\ge J_\alpha(S^\star).$$

If $\widehat\phi\not\sim_{\mathrm s}S^\star$, then by definition of $\Delta_\alpha$,

J_\alpha(\widehat\phi) \le \sup_{\phi\not\sim_{\mathrm s}S^\star}J_\alpha(\phi) = J_\alpha(S^\star)-\Delta_\alpha &lt; J_\alpha(S^\star),

contradiction. Therefore $\widehat\phi\sim_{\mathrm s}S^\star$. \end{proof}

The condition $\Delta_\alpha>0$ says that $S^\star$ is exposed by a supporting line of slope $\alpha$ on the information-complexity frontier.

A useful sufficient condition can be stated in terms of slopes. Define

$$\alpha_-:= \sup_{\substack{\phi\not\sim_{\mathrm s}S^\star:\ C(\phi)>C^\star}} \frac{(I(\phi)-I^\star)_+}{C(\phi)-C^\star},$$

where $(t)_+:=\max\{t,0\}$, and

$$\alpha_+:= \inf_{\substack{\phi\not\sim_{\mathrm s}S^\star:\ C(\phi)<C^\star}} \frac{I^\star-I(\phi)}{C^\star-C(\phi)}.$$

We also require that every non-strong competitor with $C(\phi)=C^\star$ has $I(\phi)<I^\star$.

\begin{proof} Fix $\alpha\in(\alpha_-,\alpha_+)$ and let $\phi\not\sim_{\mathrm s}S^\star$.

If $C(\phi)>C^\star$, then by the definition of $\alpha_-$,

I(\phi)-I^\star &lt; \alpha(C(\phi)-C^\star),

so

$$I(\phi)-\alpha C(\phi)<I^\star-\alpha C^\star.$$

If $C(\phi)<C^\star$, then by the definition of $\alpha_+$,

$$I^\star-I(\phi)>\alpha(C^\star-C(\phi)),$$

which again gives

$$I(\phi)-\alpha C(\phi)<I^\star-\alpha C^\star.$$

If $C(\phi)=C^\star$, the assumed strict information gap gives $I(\phi)<I^\star$, so the same strict inequality holds. Thus every non-strong competitor has strictly smaller $J_\alpha$ than $S^\star$, so $\Delta_\alpha>0$. \end{proof}

---

6. Variational beta-ELBO with decoder complexity

We now connect the information-complexity objective to a beta-ELBO. The key point is that, after optimizing the variational gaps, the beta-ELBO equals a constant minus an information-complexity score when \beta&lt;1.

Let $q(z\mid x,y)$ be an encoder, $r(z\mid x)$ a conditional prior/router, and $g(y\mid x,z)$ a decoder. Define the population objective

$$\mathcal L_{\beta,\lambda}(q,r,g) := \mathbb E_{X,Y}\mathbb E_{Z\sim q(\cdot\mid X,Y)}[-\log g(Y\mid X,Z)] + \beta\,\mathbb E_{X,Y}\operatorname{KL}(q(\cdot\mid X,Y)\|r(\cdot\mid X)) + \lambda C(g).$$

Here $\beta\ge 0$ is the KL strength and $\lambda\ge 0$ is the decoder-complexity weight. We use a conditional prior $r(z\mid x)$ because different tasks may use different mixtures of strategies.

Given $q$, define

$$q(z\mid x):=\sum_y p(y\mid x)q(z\mid x,y),$$

and, when $q(z\mid x)>0$,

$$q(y\mid x,z):=\frac{p(y\mid x)q(z\mid x,y)}{q(z\mid x)}.$$

Let $I_q(Y;Z\mid X)$ denote conditional mutual information under the joint law

$$\mu(x)p(y\mid x)q(z\mid x,y).$$

\begin{proof} First decompose reconstruction. Under the joint law induced by $q$,

$$\mathbb E[-\log g(Y\mid X,Z)] = \mathbb E_{X,Z}\left[ \sum_y q(y\mid X,Z)(-\log g(y\mid X,Z)) \right].$$

For each $(x,z)$, cross-entropy decomposes as entropy plus KL:

$$\sum_y q(y\mid x,z)(-\log g(y\mid x,z)) = H(q(\cdot\mid x,z))+ \operatorname{KL}(q(\cdot\mid x,z)\|g(\cdot\mid x,z)).$$

Averaging gives

$$\mathbb E[-\log g(Y\mid X,Z)] = H_q(Y\mid X,Z)+\operatorname{DecGap}(q,g).$$

Since $I_q(Y;Z\mid X)=H(Y\mid X)-H_q(Y\mid X,Z)$, this equals

$$H(Y\mid X)-I_q(Y;Z\mid X)+\operatorname{DecGap}(q,g).$$

Next decompose the KL-to-prior term:

$$\mathbb E_{X,Y}\operatorname{KL}(q(\cdot\mid X,Y)\|r(\cdot\mid X)) = \mathbb E_{X,Y,Z}\log\frac{q(Z\mid X,Y)}{r(Z\mid X)}.$$

Insert $q(Z\mid X)$:

$$\log\frac{q(Z\mid X,Y)}{r(Z\mid X)} = \log\frac{q(Z\mid X,Y)}{q(Z\mid X)} + \log\frac{q(Z\mid X)}{r(Z\mid X)}.$$

The first expectation is $I_q(Y;Z\mid X)$, and the second is $\operatorname{PriorGap}(q,r)$. Combining the reconstruction and KL decompositions gives the stated identity. \end{proof}

---

7. Hard-realizable variational triples

We now specialize the ELBO to deterministic latents. For $\phi\in\Phi_K$, define

$$q_\phi(z\mid x,y):=\mathbf 1\{z=\phi(x,y)\},$$

with induced $r_\phi$ and $g_\phi$ as above.

For this triple, the variational gaps vanish:

$$\operatorname{DecGap}(q_\phi,g_\phi)=0, \qquad \operatorname{PriorGap}(q_\phi,r_\phi)=0.$$

Therefore

$$\mathcal L_{\beta,\lambda}(\phi) := \mathcal L_{\beta,\lambda}(q_\phi,r_\phi,g_\phi) = H(Y\mid X)-(1-\beta)I(\phi)+\lambda C(\phi).$$

If \beta&lt;1, define the effective information-complexity penalty

$$\alpha:=\frac{\lambda}{1-\beta}.$$

Then

$$\mathcal L_{\beta,\lambda}(\phi) = H(Y\mid X)-(1-\beta)\bigl[I(\phi)-\alpha C(\phi)\bigr] = H(Y\mid X)-(1-\beta)J_\alpha(\phi).$$

Thus minimizing the beta-ELBO is exactly equivalent to maximizing the penalized information-complexity score $J_\alpha$.

\begin{proof} For deterministic latents,

$$\mathcal L_{\beta,\lambda}(\phi)=H(Y\mid X)-(1-\beta)J_\alpha(\phi).$$

Since \beta&lt;1, minimizing $\mathcal L_{\beta,\lambda}$ is equivalent to maximizing $J_\alpha$. By the penalized information-complexity recovery theorem, a positive gap $\Delta_\alpha>0$ implies every maximizer of $J_\alpha$ strongly recovers $S^\star$. Therefore every minimizer of $\mathcal L_{\beta,\lambda}$ strongly recovers $S^\star$. \end{proof}

---

8. Empirical ELBO recovery under uniform convergence

Now suppose we observe samples

$$(X_i,Y_i)_{i=1}^n\overset{\mathrm{i.i.d.}}\sim \mu(x)p(y\mid x).$$

For a deterministic latent $\phi$, define the per-sample hard-ELBO loss

$$\ell_{\beta,\lambda,\phi}(x,y) := -\log g_\phi(y\mid x,\phi(x,y)) + \beta\operatorname{KL}(q_\phi(\cdot\mid x,y)\|r_\phi(\cdot\mid x)) + \lambda C(\phi).$$

Because $q_\phi$ is a point mass, this can be written as

$$\ell_{\beta,\lambda,\phi}(x,y) = -\log g_\phi(y\mid x,\phi(x,y)) - \beta\log r_\phi(\phi(x,y)\mid x) + \lambda C(\phi).$$

Define

$$\widehat{\mathcal L}_{\beta,\lambda,n}(\phi) := \frac1n\sum_{i=1}^n\ell_{\beta,\lambda,\phi}(X_i,Y_i).$$

The complexity term is deterministic; it is included in both the empirical and population objectives.

The population ELBO gap corresponding to $\Delta_\alpha$ is

$$\Gamma_{\beta,\lambda}:=(1-\beta)\Delta_\alpha.$$

Indeed, if $\phi\not\sim_{\mathrm s}S^\star$, then

$$\mathcal L_{\beta,\lambda}(\phi)-\mathcal L_{\beta,\lambda}(S^\star) = (1-\beta)(J_\alpha(S^\star)-J_\alpha(\phi)) \ge (1-\beta)\Delta_\alpha.$$

\begin{proof} Let $\varepsilon_n$ denote the uniform deviation:

$$\varepsilon_n:= \sup_{\phi\in\Phi_K} \left| \widehat{\mathcal L}_{\beta,\lambda,n}(\phi) - \mathcal L_{\beta,\lambda}(\phi) \right|.$$

By assumption, \varepsilon_n&lt;(1-\beta)\Delta_\alpha/2.

Let $\widehat\phi_n$ be an empirical minimizer. Since $S^\star$ is feasible,

$$\widehat{\mathcal L}_{\beta,\lambda,n}(\widehat\phi_n) \le \widehat{\mathcal L}_{\beta,\lambda,n}(S^\star).$$

Therefore

$$\mathcal L_{\beta,\lambda}(\widehat\phi_n) \le \widehat{\mathcal L}_{\beta,\lambda,n}(\widehat\phi_n)+\varepsilon_n \le \widehat{\mathcal L}_{\beta,\lambda,n}(S^\star)+\varepsilon_n \le \mathcal L_{\beta,\lambda}(S^\star)+2\varepsilon_n.$$

Thus

\mathcal L_{\beta,\lambda}(\widehat\phi_n) &lt; \mathcal L_{\beta,\lambda}(S^\star)+(1-\beta)\Delta_\alpha.

But every non-strongly-recovering $\phi$ has population loss at least

$$\mathcal L_{\beta,\lambda}(S^\star)+(1-\beta)\Delta_\alpha.$$

Hence $\widehat\phi_n$ cannot be non-strongly-recovering. Therefore $\widehat\phi_n\sim_{\mathrm s}S^\star$. \end{proof}

---

9. Finite-class sample complexity

The preceding theorem reduces statistical recovery to uniform convergence. The following corollary gives a simple finite-class bound.

\begin{proof} For a fixed $\phi$, sub-Gaussian concentration gives

$$\mathbb P\left( \left| \widehat{\mathcal L}_{\beta,\lambda,n}(\phi)-\mathcal L_{\beta,\lambda}(\phi) \right| \ge t \right) \le 2\exp\left(-\frac{nt^2}{2\sigma^2}\right).$$

A union bound over $N$ candidates gives

$$\mathbb P\left( \sup_{\phi\in\Phi_K} \left| \widehat{\mathcal L}_{\beta,\lambda,n}(\phi)-\mathcal L_{\beta,\lambda}(\phi) \right| \ge t \right) \le 2N\exp\left(-\frac{nt^2}{2\sigma^2}\right).$$

Set $t=(1-\beta)\Delta_\alpha/2$. The stated lower bound on $n$ makes the right-hand side at most $\delta$. On this event, the uniform convergence condition of the empirical recovery theorem holds, so every empirical minimizer strongly recovers $S^\star$. \end{proof}

---

10. Infinite-class extensions

The finite-class theorem is intentionally simple. For larger classes, the same proof works with any uniform convergence bound.

These bounds are schematic but capture the general dependence:

$$\text{sample complexity} \approx \frac{\text{statistical complexity of the candidate class}}{(1-\beta)^2\Delta_\alpha^2}.$$

---

11. Soft variational triples

The hard-realizable theorem is the cleanest version. For general soft encoders and decoders, the ELBO decomposition still gives an exact population objective.

Assume \beta&lt;1 and define $\alpha=\lambda/(1-\beta)$. Rearranging the decomposition gives

$$\mathcal L_{\beta,\lambda}(q,r,g) = H(Y\mid X) - (1-\beta)\widetilde J_{\alpha,\beta}(q,r,g),$$

where

$$\widetilde J_{\alpha,\beta}(q,r,g) := I_q(Y;Z\mid X) - \alpha C(g) - \frac{\operatorname{DecGap}(q,g)+\beta\operatorname{PriorGap}(q,r)}{1-\beta}.$$

Thus, in the soft variational class, ELBO minimization is exactly equivalent to maximizing the gap-penalized information-complexity score $\widetilde J_{\alpha,\beta}$.

This clarifies the role of variational approximation. The beta-ELBO does not simply maximize information; it maximizes information minus decoder complexity minus the normalized decoder/prior mismatch gaps.

---

12. Failure modes and interpretation

---

13. Main takeaway

The variational theory can be summarized as follows.

For deterministic strategy-like latents,

$$\mathcal L_{\beta,\lambda}(\phi) = H(Y\mid X)-(1-\beta)\left[I(\phi)-\frac{\lambda}{1-\beta}C(\phi)\right].$$

Thus, in the information-seeking regime \beta&lt;1, minimizing a beta-ELBO with decoder-complexity penalty is equivalent to maximizing an information-complexity frontier objective.

A reference strategy $S^\star$ is recovered when it is the unique high-scoring point on this frontier:

$$I(S^\star)-\alpha C(S^\star) > I(\phi)-\alpha C(\phi) \quad \text{for all }\phi\not\sim_{\mathrm s}S^\star.$$

Empirically, recovery requires estimating the ELBO well enough to resolve the population gap:

\sup_\phi|\widehat{\mathcal L}_{\beta, \lambda,n}(\phi)-\mathcal L_{\beta,\lambda}(\phi)| &lt; \frac{(1-\beta)\Delta_\alpha}{2}.

For a finite candidate class, this yields

$$n \gtrsim \frac{\sigma^2}{(1-\beta)^2\Delta_\alpha^2} \log\frac{N}{\delta}.$$

So the complete message is:

$$\boxed{ \text{Low-}\beta\text{ ELBO supplies information pressure; decoder complexity supplies semantic selection.} }$$