Budget-interval and statistical recovery for complexity-constrained max-info

Purpose

The baseline max-info theory shows that, for expressive router-generator classes, maximizing $I(Y;Z\mid X)$ alone is not enough to recover semantic latents: the criterion prefers latents that reduce residual uncertainty in $Y$ , and in expressive classes this can select deterministic simulators or arbitrary high-information partitions.

The complexity-constrained strategy-recovery theory adds an inductive-bias term: among deterministic $K$ -state latents, prefer latents whose induced decoder is simple. The intended interpretation is:

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

This note extends that theory in two directions:

Budget intervals: recovery should not require knowing the exact oracle complexity $C^\star=C(S^\star)$ . We characterize a range of budgets $B$ for which constrained max-info recovers the same strategy.
Statistical recovery: given samples $(X_i,Y_i)$ , empirical max-info recovers the population strategy whenever the information objective is uniformly estimated to accuracy smaller than the population recovery gap.

The theory remains abstract in the complexity functional $C$ . This is deliberate: $C$ is meant to represent architecture- and optimization-induced simplicity, e.g. MDL, shared-module complexity, smoothness over a task graph, or another implicit bias.

Setup

Let $X,Y$ be finite, with joint law $\mu(x)p(y\mid x)$ . Fix $K\ge 2$ and define the class of deterministic $K$ -state latents

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

For $\phi\in\Phi_K$ , write

Z_\phi:=\phi(X,Y).

The latent $Z_\phi$ induces the exact decoder

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

whenever $\mathbb P(\phi(x,Y)=z\mid X=x)>0$ , with arbitrary values on zero-mass states.

Define

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

Since $Z_\phi$ is deterministic given $(X,Y)$ ,

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

Thus max-info over deterministic latents is conditional-entropy maximization.

Let

C(\phi):=C(g_\phi)

be an abstract decoder-complexity functional. Low $C(\phi)$ means that the conditional generator $g_\phi(\cdot\mid x,z)$ admits a simple reusable representation.

Let

S^\star=\sigma(X,Y)\in[K]

be a reference strategy variable, assumed to be a deterministic attribute of the completed reasoning trace. Define

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

Weak and strong recovery

The main obstruction is label alignment. A latent can recover the correct partition separately for each input while using inconsistent labels across inputs.

Weak and strong recovery

Let $\phi\in\Phi_K$ .

We say $\phi$ weakly recovers $S^\star$ , written $\phi\sim_{\mathrm w}S^\star$ , if there exist input-dependent permutations $\pi_x\in S_K$ such that

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

for $\mu(x)p(y\mid x)$ -almost every $(x,y)$ .

We say $\phi$ strongly recovers $S^\star$ , written $\phi\sim_{\mathrm s}S^\star$ , if there exists a single global permutation $\pi\in S_K$ such that

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

for $\mu(x)p(y\mid x)$ -almost every $(x,y)$ .

Weak recovery identifies the strategy partition taskwise. Strong recovery identifies a globally meaningful latent label.

Budget intervals for population recovery

The oracle-budget theorem used the budget $B=C^\star$ . We now ask when recovery holds for an interval of budgets.

The relevant thresholds are the first complexities at which a bad competitor can match the strategy's information.

First bad complexity thresholds

Define the first locally bad complexity level

B_{\mathrm{bad}}^{\mathrm w} := \inf\Bigl\{ C(\phi):\phi\not\sim_{\mathrm w}S^\star, \ I(\phi)\ge I^\star \Bigr\},

and the first alignment-bad complexity level

B_{\mathrm{bad}}^{\mathrm s} := \inf\Bigl\{ C(\phi):\phi\sim_{\mathrm w}S^\star, \ \phi\not\sim_{\mathrm s}S^\star \Bigr\}.

Empty infima are interpreted as $+\infty$ .

Define the recovery budget threshold

B_{\mathrm{rec}} := \min\{B_{\mathrm{bad}}^{\mathrm w},B_{\mathrm{bad}}^{\mathrm s}\}.

The condition $C^\star<B_{\mathrm{rec}}$ says two things. First, no non-strategy latent of complexity near $C^\star$ captures as much information as $S^\star$ . Second, no $x$ -dependent relabeling of the strategy is as simple as a globally aligned relabeling.

Budget-interval recovery

Suppose $C^\star< B_{\mathrm{rec}}$ . Let

B\in[C^\star,B_{\mathrm{rec}}).

Let

\widehat\phi_B \in \arg\max_{\phi\in\Phi_K} I(\phi) \quad\text{subject to}\quad C(\phi)\le B.

Then

\widehat\phi_B\sim_{\mathrm s}S^\star.

Thus strong strategy recovery holds for every budget in the interval $[C^\star,B_{\mathrm{rec}})$ .

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

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

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

If $\widehat\phi_B\not\sim_{\mathrm w}S^\star$ , then $\widehat\phi_B$ belongs to the set defining $B_{\mathrm{bad}}^{\mathrm w}$ , because it has $I(\widehat\phi_B)\ge I^\star$ . Therefore

C(\widehat\phi_B)\ge B_{\mathrm{bad}}^{\mathrm w},

contradicting $C(\widehat\phi_B)<B_{\mathrm{bad}}^{\mathrm w}$ . Thus

\widehat\phi_B\sim_{\mathrm w}S^\star.

If $\widehat\phi_B\not\sim_{\mathrm s}S^\star$ , then it is weak-but-not-strong. Hence it belongs to the set defining $B_{\mathrm{bad}}^{\mathrm s}$ , and so

C(\widehat\phi_B)\ge B_{\mathrm{bad}}^{\mathrm s},

contradicting $C(\widehat\phi_B)<B_{\mathrm{bad}}^{\mathrm s}$ . Therefore

\widehat\phi_B\sim_{\mathrm s}S^\star.

\end{proof}

Interpretation

The theorem gives a recovery plateau. Once the complexity budget is large enough to include the reference strategy, but not large enough to include equally informative non-strategy latents or misaligned relabelings, the constrained max-info solution is stable and strategy-aligned.

Thus one need not know $C^\star$ exactly. It is enough to choose any budget in the good interval $[C^\star,B_{\mathrm{rec}})$ .

Population recovery gap at a fixed budget

For statistical learning, the exact budget interval is not enough. We need a positive margin separating the strategy from all non-strong competitors at the chosen budget.

Strong recovery gap at budget

B

For $B\ge C^\star$ , define

\Delta_B := I^\star - \sup_{\substack{\phi\in\Phi_K:\ C(\phi)\le B,\ \phi\not\sim_{\mathrm s}S^\star}} I(\phi).

If $\Delta_B>0$ , then $S^\star$ is separated from every non-strong competitor under the complexity budget $B$ .

Population recovery from a positive gap

If $B\ge C^\star$ and $\Delta_B>0$ , then every optimizer of

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

strongly recovers $S^\star$ .

\begin{proof} The strategy $S^\star$ is feasible, so every optimizer $\widehat\phi_B$ has $I(\widehat\phi_B)\ge I^\star$ . If $\widehat\phi_B\not\sim_{\mathrm s}S^\star$ , then by definition of $\Delta_B$ ,

I(\widehat\phi_B) \le I^\star-\Delta_B &lt; I^\star,

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

The budget-interval theorem gives exact population recovery. The positive-gap version is the form needed for finite-sample recovery.

Penalized objectives and frontier slopes

A hard budget is analytically clean, but training objectives often use a penalty. Consider

\mathcal J_\lambda(\phi):=I(\phi)-\lambda C(\phi), \qquad \lambda>0.

The penalized objective recovers $S^\star$ when $S^\star$ is an exposed point of the information-complexity frontier.

For a competitor $\phi$ , the condition that $S^\star$ beat $\phi$ is

I^\star-\lambda C^\star > I(\phi)-\lambda C(\phi).

Equivalently,

I^\star-I(\phi) > \lambda(C^\star-C(\phi)).

This imposes a lower bound on $\lambda$ for more-complex, higher-information competitors, and an upper bound on $\lambda$ for lower-complexity, lower-information competitors.

Frontier slope quantities

Define

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

and

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

If the index set is empty, set $\Lambda_+=0$ for the first supremum and $\Lambda_-=+\infty$ for the second infimum.

The remaining case is competitors with exactly the same complexity as $S^\star$ . They must lose information.

Penalized frontier recovery

Assume:

for every $\phi\not\sim_{\mathrm s}S^\star$ with $C(\phi)=C^\star$ , one has $I(\phi)<I^\star$ ;
$\Lambda_+<\Lambda_-$ .

Then for every

\lambda\in(\Lambda_+,\Lambda_-),

every maximizer of

\max_{\phi\in\Phi_K}\{I(\phi)-\lambda C(\phi)\}

strongly recovers $S^\star$ .

\begin{proof} Let $\phi\not\sim_{\mathrm s}S^\star$ . We show $\mathcal J_\lambda(S^\star)>\mathcal J_\lambda(\phi)$ .

If $C(\phi)>C^\star$ , then

I(\phi)-I^\star \le \Lambda_+(C(\phi)-C^\star) &lt; \lambda(C(\phi)-C^\star),

I^\star-\lambda C^\star > I(\phi)-\lambda C(\phi).

If $C(\phi)<C^\star$ , then by $\lambda<\Lambda_-$ ,

I^\star-I(\phi) > \lambda(C^\star-C(\phi)),

which again gives $\mathcal J_\lambda(S^\star)>\mathcal J_\lambda(\phi)$ .

If $C(\phi)=C^\star$ , then $I(\phi)<I^\star$ by assumption, so $\mathcal J_\lambda(S^\star)>\mathcal J_\lambda(\phi)$ .

Thus no non-strong competitor can maximize $\mathcal J_\lambda$ . Therefore every maximizer strongly recovers $S^\star$ . \end{proof}

Relation to the constrained theorem

The penalized theorem is a Lagrangian/frontier version of the constrained theorem, but it is not strictly equivalent in nonconvex or discrete settings. A budget optimum need not be exposed by a linear penalty. The penalized theorem recovers $S^\star$ when its information-complexity point is exposed by a slope $\lambda$ .

A convenient sufficient condition is a slope separation condition.

Simple slope-separation sufficient condition

Suppose there exist numbers $0\le a_+<a_-$ such that every non-strong competitor satisfies:

if $C(\phi)>C^\star$ , then $I(\phi)-I^\star\le a_+(C(\phi)-C^\star);$
if $C(\phi)<C^\star$ , then $I^\star-I(\phi)\ge a_-(C^\star-C(\phi));$
if $C(\phi)=C^\star$ , then $I(\phi)<I^\star$ .

Then every $\lambda\in(a_+,a_-)$ yields strong recovery under the penalized objective.

\begin{proof} The first two inequalities imply $\Lambda_+\le a_+$ and $\Lambda_-\ge a_-$ . Apply the penalized frontier theorem. \end{proof}

Statistical recovery from empirical max-info

Now suppose we observe i.i.d. samples

(X_1,Y_1),\dots,(X_n,Y_n)\sim \mu(x)p(y\mid x).

Let $\widehat I_n(\phi)$ be an estimator of $I(\phi)=H(\phi(X,Y)\mid X)$ , for example a plug-in conditional entropy estimator. Define the empirical constrained optimizer

\widehat\phi_{n,B} \in \arg\max_{\phi\in\Phi_K}\widehat I_n(\phi) \quad\text{subject to}\quad C(\phi)\le B.

The next theorem isolates the only statistical requirement: uniform accuracy below half the population recovery gap.

Empirical recovery under uniform convergence

Fix $B\ge C^\star$ and assume $\Delta_B>0$ . Suppose

\sup_{\phi:C(\phi)\le B}|\widehat I_n(\phi)-I(\phi)|&lt;\frac{\Delta_B}{2}.

Then every empirical optimizer $\widehat\phi_{n,B}$ strongly recovers $S^\star$ .

\begin{proof} Since $S^\star$ is feasible, empirical optimality gives

\widehat I_n(\widehat\phi_{n,B})\ge \widehat I_n(S^\star).

By the uniform deviation bound,

I(\widehat\phi_{n,B}) \ge \widehat I_n(\widehat\phi_{n,B})-\frac{\Delta_B}{2} \ge \widehat I_n(S^\star)-\frac{\Delta_B}{2} \ge I^\star-\Delta_B.

If $\widehat\phi_{n,B}$ did not strongly recover $S^\star$ , then by definition of $\Delta_B$ ,

I(\widehat\phi_{n,B})\le I^\star-\Delta_B.

With a strict uniform bound $<\Delta_B/2$ , the preceding chain gives $I(\widehat\phi_{n,B})>I^\star-\Delta_B$ , a contradiction. Therefore $\widehat\phi_{n,B}\sim_{\mathrm s}S^\star$ . \end{proof}

Sample complexity principle

Empirical recovery requires estimating the population max-info objective accurately enough to resolve the recovery gap $\Delta_B$ . Thus the generic scaling is

n \asymp \frac{\text{statistical complexity of the budgeted class}}{\Delta_B^2}.

Finite-class sample complexity

The cleanest finite-sample statement assumes a finite budgeted class and a pointwise concentration inequality for $\widehat I_n$ .

Let

\Phi_B:=\{\phi\in\Phi_K:C(\phi)\le B\}, \qquad N_B:=|\Phi_B|.

Finite-class empirical recovery

Assume $\Phi_B$ is finite, $B\ge C^\star$ , and $\Delta_B>0$ . Suppose that for each fixed $\phi\in\Phi_B$ and every $t>0$ ,

\mathbb P\bigl(|\widehat I_n(\phi)-I(\phi)|>t\bigr) \le 2\exp\left(-\frac{n t^2}{2\sigma^2}\right).

n \ge \frac{8\sigma^2}{\Delta_B^2} \log\frac{2N_B}{\delta},

then with probability at least $1-\delta$ , every empirical constrained optimizer $\widehat\phi_{n,B}$ strongly recovers $S^\star$ .

\begin{proof} By the assumed concentration inequality and a union bound,

\mathbb P\left( \sup_{\phi\in\Phi_B}|\widehat I_n(\phi)-I(\phi)|>t \right) \le 2N_B\exp\left(-\frac{nt^2}{2\sigma^2}\right).

Set $t=\Delta_B/2$ . The displayed lower bound on $n$ makes the right-hand side at most $\delta$ . On the complementary event, the empirical recovery theorem applies. \end{proof}

The concentration assumption can be instantiated by standard finite-alphabet plug-in entropy bounds when $X$ and $Z$ are finite. The important point for this theory is the dependency on the recovery gap and the size/complexity of the budgeted class.

MDL-style infinite-class extension

For infinite classes, one replaces $\log N_B$ by a statistical complexity measure. Since the decoder-complexity functional is intended to encode description length or architecture bias, an MDL-style bound is natural when candidates admit prefix codes.

MDL-uniform recovery bound

Suppose each $\phi\in\Phi_K$ has a code length $L(\phi)$ satisfying the Kraft inequality

\sum_{\phi\in\Phi_K}e^{-L(\phi)}\le 1.

Assume the pointwise concentration bound

\mathbb P\bigl(|\widehat I_n(\phi)-I(\phi)|>t\bigr) \le 2\exp\left(-\frac{n t^2}{2\sigma^2}\right)

holds for every fixed $\phi$ .

Then with probability at least $1-\delta$ , simultaneously for all $\phi\in\Phi_K$ ,

|\widehat I_n(\phi)-I(\phi)| \le \sigma\sqrt{\frac{2(L(\phi)+\log(2/\delta))}{n}}.

In particular, if $L(\phi)\le B$ for all $\phi$ in the feasible class and

n > \frac{8\sigma^2(B+\log(2/\delta))}{\Delta_B^2},

then empirical constrained max-info strongly recovers $S^\star$ .

\begin{proof} For each $\phi$ , set

t_\phi:=\sigma\sqrt{\frac{2(L(\phi)+\log(2/\delta))}{n}}.

Then

\mathbb P(|\widehat I_n(\phi)-I(\phi)|>t_\phi) \le 2e^{-L(\phi)}e^{-\log(2/\delta)} = \delta e^{-L(\phi)}.

A union bound and Kraft's inequality give simultaneous validity with probability at least $1-\delta$ .

If all feasible $\phi$ have $L(\phi)\le B$ , then the displayed uniform bound is at most $\Delta_B/2$ under the stated sample-size condition. Apply the empirical recovery theorem. \end{proof}

Rademacher/covering-number extension

More generally, the finite-class or MDL term may be replaced by any uniform convergence bound for the estimator class:

\sup_{\phi:C(\phi)\le B}|\widehat I_n(\phi)-I(\phi)| \le U_n(B,\delta).

Empirical recovery holds whenever $U_n(B,\delta)<\Delta_B/2$ . For neural or parametric classes, $U_n$ may be controlled by covering numbers, Rademacher complexity, compression bounds, or stability bounds, depending on the chosen architecture and estimator.

Failure modes

Superficial low-complexity attributes can win

The theory does not say that max-info plus arbitrary complexity recovers human-interpretable strategies. It says that the recovered latent is the most informative latent that is simple under $C$ .

If a superficial attribute $L(X,Y)$ , such as length bucket or formatting style, satisfies

C(L)\le C(S^\star), \qquad I(L)>I(S^\star),

then the constrained objective at budget $C(S^\star)$ selects $L$ rather than $S^\star$ .

Therefore the complexity functional must encode a bias under which strategy-conditioned generators are simpler than superficial-attribute-conditioned generators.

Statistical recovery requires a population gap

If $\Delta_B=0$ , exact finite-sample recovery is not stable: arbitrarily small estimation error may cause the empirical optimizer to select a non-strategy latent. Positive recovery gaps are the statistical counterpart of identifiability.

Relation to variational objectives

The results above assume direct empirical access to an estimator $\widehat I_n(\phi)$ . In a variational implementation, one typically optimizes an encoder-decoder objective rather than $I(\phi)$ directly. The same proof strategy should apply after adding approximation terms.

Suppose a variational estimator produces a score $\widehat J_n(\phi)$ satisfying

\sup_{\phi:C(\phi)\le B}|\widehat J_n(\phi)-I(\phi)|\le \varepsilon_n

with high probability, where $\varepsilon_n$ includes statistical error, variational approximation error, and optimization error. Then empirical recovery follows whenever

\varepsilon_n&lt;\frac{\Delta_B}{2}.

Thus the next step is to analyze when an ELBO-like objective provides a uniformly accurate proxy for the max-info objective over the complexity-bounded class.

Self-evaluation

The theory now gives a cleaner and more realistic selection principle than the fixed-tree theory:

\text{recover strategy} \Longleftrightarrow \text{strategy wins the information-complexity competition.}

Its strengths are:

it does not assume the learned latent is a cut of a known ground-truth tree;
it gives recovery over a budget interval rather than only at the oracle budget $C^\star$ ;
it separates population identifiability from finite-sample estimation;
it clarifies the role of the complexity functional $C$ as the source of semantic bias.

Its main limitation is also explicit: the decisive condition is the information-complexity gap. The theory characterizes when recovery happens but does not, by itself, prove that a given neural architecture induces a complexity functional for which human strategy variables win. That requires additional structural modeling of reusable strategy-conditioned generation, task-graph smoothness, or common-cause/sequential reasoning structure.