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.

The tree-cut theory avoids this by restricting admissible latents to cuts of a fixed semantic hierarchy. That is useful as an oracle analysis, but it assumes knowledge of the strategy tree. This note develops a different selection principle:

\boxed{ \text{strategy} = \text{the most informative low-decoder-complexity attribute of }Y\text{ given }X. }

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.

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$ . Let

\Phi_K:=\{\phi:\mathcal X\times\mathcal Y\to[K]\}

be the class of $K$ -state deterministic output attributes. For $\phi\in\Phi_K$ , define $Z_\phi:=\phi(X,Y)$ .

The induced exact factorization is

r_\phi(z\mid x):=\mathbb P(\phi(x,Y)=z\mid X=x),

g_\phi(y\mid x,z):=p(y\mid x,\phi(x,Y)=z)

whenever $r_\phi(z\mid x)>0$ , with arbitrary values on zero-mass states. Write

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

3. Deterministic attributes and max-info

For deterministic attributes, max-info becomes conditional entropy maximization. Thus, without further structure, the criterion prefers the highest-entropy $K$ -way attribute of $Y$ given $X$ , which need not be a reasoning strategy.

deterministic attribute identity

For every $\phi\in\Phi_K$ , the induced pair $(r_\phi,g_\phi)$ is feasible and satisfies

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

Equivalently,

I(\phi)=H(\phi(X,Y)\mid X).

\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}

Why max-info alone is insufficient

Over all $\phi\in\Phi_K$ , max-info selects a high-entropy partition of $Y$ conditional on $X$ . If a length bucket, formatting feature, or arbitrary balanced partition has larger conditional entropy than the intended strategy variable, max-info alone prefers that attribute. The additional ingredient below is decoder complexity.

4. Abstract decoder complexity

We now introduce the inductive bias that replaces the oracle tree restriction. The model is not told the true strategy hierarchy. Instead, it prefers 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:

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

The important modeling choice is that $C(g_\phi)$ should measure the complexity of the generator induced by the latent, including the support restrictions needed to sample from $p(y\mid x,\phi(x,Y)=z)$ . A simple-to-compute attribute can still have a complex induced decoder.

complexity-constrained max-info objective

For a complexity budget $B$ , define

\widehat \Phi_B := \arg\max_{\phi\in\Phi_K:\ C(\phi)\le B} I(\phi).

Since $\phi$ is deterministic,

\widehat \Phi_B = \arg\max_{\phi\in\Phi_K:\ C(\phi)\le B} H(\phi(X,Y)\mid X).

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$ .

5. Reference strategy and recovery notions

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].

Equivalently, for each $x$ , the sets

\mathcal Y_s(x):=\{y:\sigma(x,y)=s\}

partition $\operatorname{supp}p(\cdot\mid x)$ up to null sets. This is the disjoint-support assumption: a trace generated by a strategy is recognizable from the trace.

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^*})$ .

weak and strong equivalence of attributes

Let $\phi\in\Phi_K$ .

We say $\phi$ is weakly equivalent to $S^*$ , written $\phi\sim_{\mathrm w}S^*$ , if for every $x$ with $\mu(x)>0$ there exists a permutation $\pi_x$ of $[K]$ such that

\phi(x,y)=\pi_x(S^*(x,y))

for all $y\in\operatorname{supp}p(\cdot\mid x)$ .

We say $\phi$ is strongly equivalent to $S^*$ , written $\phi\sim_{\mathrm s}S^*$ , if there exists a single permutation $\pi$ of $[K]$ such that

\phi(x,y)=\pi(S^*(x,y))

for all $(x,y)$ in the support of $\mu(x)p(y\mid x)$ .

Weak equivalence means the correct strategy partition is recovered separately for each task, but latent labels may be permuted differently across inputs. Strong equivalence means the same latent label has the same strategy meaning globally.

6. Weak recovery from decoder-complexity constrained max-info

The following result is the core selection theorem. It does not assume a known tree. It assumes only that the reference strategy is the most informative attribute among those whose induced decoders are no more complex than the strategy decoder.

weak recovery from a local information-complexity gap

Let $S^*\in\Phi_K$ be a hard reference strategy with complexity $C^*=C(S^*)$ . Assume that for every $\phi\in\Phi_K$ with $C(\phi)\le C^*$ ,

\phi\not\sim_{\mathrm w}S^* \quad\Longrightarrow\quad I(\phi)<I(S^*).

Then every solution of

\max_{\phi\in\Phi_K} I(\phi) \quad\text{subject to}\quad C(\phi)\le C^*

weakly recovers $S^*$ .

\begin{proof} Since $C(S^*)=C^*$ , the strategy attribute $S^*$ is feasible for the constrained problem. Hence every optimizer $\hat\phi$ satisfies $I(\hat\phi)\ge I(S^*)$ .

Suppose, for contradiction, that $\hat\phi\not\sim_{\mathrm w}S^*$ . Since $\hat\phi$ is feasible, $C(\hat\phi)\le C^*$ . By the information-complexity gap assumption, $I(\hat\phi)<I(S^*)$ , contradicting optimality. Therefore $\hat\phi\sim_{\mathrm w}S^*$ . \end{proof}

The theorem says that max-info does real work: among low-complexity attributes, it chooses the most informative one. Complexity does the complementary work: it excludes arbitrary high-entropy partitions whose induced decoders are too complicated.

What this assumption means

The condition is not that $S^*$ is the highest-entropy attribute overall. That is often false. The condition is that every non-strategy attribute with comparable decoder complexity has lower information. In words: strategy is the most informative simple decoder-compressing attribute.

7. Alignment curves: recovery as a function of complexity

The previous theorem gives exact weak recovery at the reference budget $C^*$ . A more diagnostic formulation asks how much misalignment is possible at a given complexity budget.

Variation of Information

The variation of information is a measure of the distance between two clusterings or partitions of elements. It satisfies $VI(X; Y) := H(X|Y) + H(Y|X)$ $VI(X; Y| Z) := H(X|Y, Z) + H(Y| X, Z)$

Define the conditional variation of information between $\phi$ and $S^*$ by

d_{\mathrm w}(\phi,S^*) := H(\phi(X,Y)\mid X,S^*)+H(S^*\mid X,\phi(X,Y)).

Then $d_{\mathrm w}(\phi,S^*)=0$ if and only if $\phi\sim_{\mathrm w}S^*$ , up to null sets.

For $B\ge 0$ and $\delta>0$ , define the bad-latent information profile

M_B(\delta) := \sup\{I(\phi):\phi\in\Phi_K, C(\phi)\le B, d_{\mathrm w}(\phi,S^*)\ge \delta\}.

If the set is empty, take $M_B(\delta):=-\infty$ .

Thus $M_B(\delta)$ is the best max-info value achievable by $\delta$ -misaligned latents under complexity budget $B$ .

alignment curve criterion

Let $\hat\phi_B\in\widehat\Phi_B$ . If $C(S^*)\le B$ and

I(S^*)>M_B(\delta),

then

d_{\mathrm w}(\hat\phi_B,S^*)&lt;\delta.

\begin{proof} Because $C(S^*)\le B$ , the reference strategy is feasible, so $I(\hat\phi_B)\ge I(S^*)$ . If $d_{\mathrm w}(\hat\phi_B,S^*)\ge\delta$ , then by the definition of $M_B(\delta)$ ,

I(\hat\phi_B)\le M_B(\delta)<I(S^*),

contradiction. Hence $d_{\mathrm w}(\hat\phi_B,S^*)<\delta$ . \end{proof}

This result clarifies how recovery depends on the complexity measure. A low-complexity reference strategy is not sufficient by itself. What matters is the gap between the information of $S^*$ and the best information achievable by misaligned latents at the same complexity budget.

State result differently. We don't control

I(S^*)

, but we can control

B

8. Strong recovery from an alignment-sensitive complexity gap

Weak recovery is not enough: $\phi(x,y)=\pi_x(S^*(x,y))$ has the same conditional entropy as $S^*$ for any input-dependent permutation $\pi_x$ . To recover globally meaningful labels, the complexity measure must prefer using the same latent label consistently across related inputs.

strong recovery from alignment-sensitive complexity

Assume the conditions of the weak recovery theorem. In addition, assume that every weakly but not strongly equivalent attribute has complexity strictly larger than $C^*$ :

\phi\sim_{\mathrm w}S^*,\ \phi\not\sim_{\mathrm s}S^* \quad\Longrightarrow\quad C(\phi)>C^*.

Then every solution of

\max_{\phi\in\Phi_K} I(\phi) \quad\text{subject to}\quad C(\phi)\le C^*

strongly recovers $S^*$ .

\begin{proof} By the weak recovery theorem, every optimizer $\hat\phi$ satisfies $\hat\phi\sim_{\mathrm w}S^*$ . Since $\hat\phi$ is feasible, $C(\hat\phi)\le C^*$ . The additional assumption rules out weak-but-not-strong attributes at this complexity. Therefore $\hat\phi\sim_{\mathrm s}S^*$ . \end{proof}

The strong-recovery assumption says that an $x$ -dependent relabeling is more complex than a global relabeling. This is exactly the desired semantic consistency principle: a simple generator should not have to reinterpret the same latent label differently on different inputs.

9. Task-graph switch complexity as a sufficient alignment mechanism

One concrete way to model label consistency is through a task graph. Adjacent tasks are tasks for which using a different latent-label convention should incur complexity.

Let $G_X=(\mathcal X,E)$ be an undirected graph. Suppose $\phi\sim_{\mathrm w}S^*$ , so there exist local permutations $\pi_x$ with $\phi(x,y)=\pi_x(S^*(x,y))$ . Define the switch cost

\operatorname{Sw}(\phi;S^*) := \min_{\{\pi_x\}} \sum_{(x,x')\in E}\mathbf 1\{\pi_x\ne\pi_{x'}\},

where the minimum ranges over all permutation witnesses of weak equivalence.

If each strategy has positive probability at each task, the witnessing $\pi_x$ is unique up to null labels, so the switch cost simply counts label-convention changes across edges.

zero switch cost implies global alignment on a connected graph

Assume $G_X$ is connected and $\phi\sim_{\mathrm w}S^*$ . Then $\operatorname{Sw}(\phi;S^*)=0$ if and only if $\phi\sim_{\mathrm s}S^*$ .

\begin{proof} If $\phi\sim_{\mathrm s}S^*$ , then one global permutation witnesses weak equivalence at every $x$ , so the switch cost is $0$ .

Conversely, if $\operatorname{Sw}(\phi;S^*)=0$ , then there are witnesses $\pi_x$ such that $\pi_x=\pi_{x'}$ on every edge $(x,x')$ . Since the graph is connected, equality propagates along paths, so $\pi_x$ is the same permutation for all $x$ . Thus $\phi\sim_{\mathrm s}S^*$ . \end{proof}

task-graph complexity gives strong recovery

Suppose the weak recovery theorem holds at budget $C^*$ . Assume further that, among weakly recovered attributes, decoder complexity decomposes as

C(\phi)=C^*+\eta\operatorname{Sw}(\phi;S^*)

for some $\eta>0$ , up to global relabeling. If $G_X$ is connected, then every constrained max-info optimizer at budget $C^*$ strongly recovers $S^*$ .

\begin{proof} By weak recovery, any optimizer is weakly equivalent to $S^*$ . Feasibility gives $C(\hat\phi)\le C^*$ . Under the displayed decomposition, this implies $\operatorname{Sw}(\hat\phi;S^*)=0$ . By the previous lemma, $\hat\phi\sim_{\mathrm s}S^*$ . \end{proof}

This formalizes the shared-module intuition: if the same latent label is used differently on neighboring tasks, the generator must implement a switch in meaning. A connected task graph forces zero-switch solutions to use one global labeling convention.

10. Penalized information-complexity frontier

The constrained objective is the cleanest exact formulation. A penalized objective is closer to regularized training:

\mathcal J_\lambda(\phi):=I(\phi)-\lambda C(\phi).

The following elementary result characterizes when $S^*$ is selected by such a tradeoff.

exposed information-complexity frontier

Let $\mathcal A\subseteq\Phi_K$ be a comparison class, e.g. all attributes modulo global relabeling. The strategy $S^*$ maximizes

I(\phi)-\lambda C(\phi)

over $\phi\in\mathcal A$ if and only if, for every $\phi\in\mathcal A$ ,

I(S^*)-I(\phi) \ge \lambda\bigl(C(S^*)-C(\phi)\bigr).

It is the unique maximizer up to the chosen equivalence relation if the inequality is strict for every inequivalent $\phi$ .

\begin{proof} The condition is exactly the inequality

I(S^*)-\lambda C(S^*)\ge I(\phi)-\lambda C(\phi)

rearranged. Strict inequality gives uniqueness modulo the allowed equivalence class. \end{proof}

Equivalently, $S^*$ must be an exposed point of the information-complexity frontier. Higher-information competitors are allowed only if they are sufficiently more complex; lower-complexity competitors are allowed only if they lose sufficiently much information.

11. Failure modes

The theory does not say that complexity-constrained max-info always recovers human-interpretable strategies. It says that the recovered latent is the most informative attribute that is simple under the chosen decoder complexity. This distinction matters.

simple superficial attributes can beat strategy

Suppose there exists $L\in\Phi_K$ such that $C(L)\le C(S^*)$ and $I(L)>I(S^*)$ . Then $S^*$ is not a solution of the constrained objective at budget $C(S^*)$ .

\begin{proof} Both $S^*$ and $L$ are feasible at budget $C(S^*)$ , but $L$ has strictly larger objective value $I(L)$ . Hence $S^*$ cannot be optimal. \end{proof}

A length bucket, style marker, or formatting feature can therefore win if its induced decoder is simple and its conditional entropy is larger than the strategy entropy. Strategy recovery requires that such attributes either have lower information or induce more complex decoders under the relevant complexity measure.

max-info and local complexity do not identify global labels

Suppose $\phi=\pi_X(S^*)$ is an $x$ -dependent relabeling of $S^*$ and $C(\phi)=C(S^*)$ . Then no objective depending only on $I(\phi)$ and $C(\phi)$ can distinguish $\phi$ from $S^*$ .

\begin{proof} Since $\phi$ is an $x$ -dependent relabeling of $S^*$ ,

I(\phi)=H(\phi\mid X)=H(S^*\mid X)=I(S^*).

By assumption, $C(\phi)=C(S^*)$ . Therefore both attributes have identical values for any objective that is a function only of $(I,C)$ . \end{proof}

Thus strong semantic recovery requires complexity to be alignment-sensitive, or else requires an additional synchronization criterion.

12. Interpretation for shared-module generators

The abstract complexity $C$ can be instantiated by a shared-module decoder class such as

g(y\mid x,z)=G_\theta(y\mid x,e_z),

where $\theta$ is a shared interpreter and $e_z$ is a latent code or strategy embedding. Under this interpretation:

$S^*$ is simple if each strategy corresponds to a reusable generator mode $e_s$ ;
arbitrary cross-strategy fragments are complex because their decoders require irregular support restrictions;
$x$ -dependent relabelings are complex because the same fixed code $e_z$ must switch meanings across inputs;
task-graph switch costs approximate the complexity of implementing these meaning switches.

This note does not require a particular neural parameterization. Instead, it says what any architecture-induced complexity must satisfy for strategy recovery: the reference strategy must be a low-complexity, high-information attribute, and misaligned high-information alternatives must be more complex.

13. Self-evaluation and scope

What this theory improves

The tree-cut theory assumes an admissible semantic hierarchy. The present theory does not. It allows arbitrary deterministic attributes $\phi(X,Y)$ and asks which one is selected by max-info under a decoder-complexity bias.

The main message is sharper:

\boxed{ \text{complexity-constrained max-info recovers the simplest high-information decoder-compressing latent.} }

If that latent is the reference strategy $S^*$ , the strategy is recovered. If a simpler or more informative superficial attribute exists, the theory correctly predicts failure.

What assumptions do real work

Hard strategy assumption: $S^*=\sigma(X,Y)$ is determined by the completed trace.
Fixed cardinality: $|\mathcal Z|=K$ is known.
Decoder-complexity gap: non-strategy high-info attributes must have larger induced-decoder complexity.
Alignment-sensitive complexity: $x$ -dependent relabelings must be more complex than global relabelings.

These assumptions are not cosmetic. Without them, max-info either selects arbitrary high-entropy deterministic attributes or remains invariant under $x$ -dependent relabeling.

What remains for future work

Extend exact representability $g_\phi\in\mathcal G_{\le c}$ to approximate representability.
Add complexity of the router $r(z\mid x)$ for soft factorizations.
Prove structural sufficient conditions for the decoder-complexity gap in concrete shared-module classes.
Develop sample-complexity guarantees for empirical estimates of $I(\phi)$ and $C(\phi)$ .
Combine this complexity view with sequential or multi-view structure, where a strategy is a persistent common cause of many parts of the reasoning trace.

14. Main takeaway

Max-info alone answers:

\text{Which latent captures the most information about }Y\text{ beyond }X?

The complexity-constrained theory answers:

\text{Which latent captures the most information while making }Y\text{ simple to generate?}

A reasoning strategy is recoverable when it is the answer to the second question.