Rank-constrained max-info and low-dimensional 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),$$

maximizing $I(Y;Z\mid X)$ is equivalent to minimizing the residual entropy $H(Y\mid X,Z)$. In expressive classes this is too permissive: max-info may select arbitrary deterministic simulators or non-semantic high-entropy partitions.

This note develops a different approach. We ask whether strategy structure can be recovered from a weaker, more model-like bias:

among high-information latent variables, prefer those whose branch-conditioned distributions vary across tasks through a low-dimensional log-density-ratio structure.

The intended setting is multi-strategy reasoning:

• $x$ is a task, such as a theorem statement;
• $y$ is a reasoning trace, such as a proof;
• $S$ is an abstract strategy, such as direct proof, contradiction, induction, construction;
• a completed trace usually determines its strategy, so we begin with hard strategy attributes $S=\sigma(X,Y)$;
• different strategies affect the distribution of traces in a reusable, low-dimensional way across many tasks.

The central message is:

Max-info supplies the pressure toward informative latent variables. A low-rank log-ratio constraint supplies the pressure toward reusable strategy structure. Together, they can recover strategy subspaces, and with additional separation or anchor assumptions, strategy labels.

---

2. Setup

Let $X,Y$ be finite, with input law $\mu$ and conditional law $p(y\mid x)$. Let

$$\Omega:=\{(x,y):\mu(x)p(y\mid x)>0\}.$$

All entropies are computed under $\mu(x)p(y\mid x)$.

A hard attribute is a deterministic map

$$\phi:\mathcal X\times\mathcal Y\to[K].$$

It induces the branch probabilities

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

and branch-conditioned laws

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

whenever $r_\phi(z\mid x)>0$.

As in the earlier notes, because $Z=\phi(X,Y)$ is deterministic given $(X,Y)$,

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

Thus unrestricted max-info over hard $K$-state attributes simply searches for high-entropy $K$-way partitions of $Y$ conditional on $X$. This is not enough to define strategy.

---

3. Smoothed log-density-ratio lifts

For an exact hard attribute, $g_\phi(\cdot\mid x,z)$ is supported only on the cell $\phi(x,y)=z$, so the literal log-density ratio $\log(g_\phi/p)$ may contain $-\infty$ values. To get a finite rank object, we use a small smoothing parameter $\varepsilon\in(0,1)$.

For active states, this has the explicit form

$$L_{\phi,\varepsilon}(z;x,y) = \log\left(\varepsilon+(1-\varepsilon)\frac{\mathbf 1\{\phi(x,y)=z\}}{r_\phi(z\mid x)}\right).$$

The log-lift asks: relative to the base conditional law $p(y\mid x)$, how much does conditioning on branch $z$ upweight or downweight the trace $y$?

---

4. Centered log-ratio rank

The normalizing term in a log-density-ratio model may contain arbitrary offsets depending on $(x,z)$. These offsets do not describe how a strategy changes the relative preference among outputs for a fixed task. We therefore remove per-$(x,z)$ means.

For fixed $z$, $\bar L_{\phi,\varepsilon}(z;\cdot,\cdot)$ is a centered function on task-output pairs. It describes the finite-dimensional contrast pattern associated with latent state $z$.

A low-rank attribute is one whose branch-conditioned distributions differ from the base distribution along only a few reusable contrast directions. This is the mathematical proxy for a reusable strategy mechanism.

---

5. Rank-constrained max-info over hard attributes

We first consider a hard rank constraint. Let

$$\Phi_{K,d}^{\varepsilon} := \{\phi:\mathcal X\times\mathcal Y\to[K]:\operatorname{rank}_\varepsilon(\phi)\le d\}.$$

The following theorem is simple but important: under a rank constraint, max-info does not optimize arbitrary hard attributes; it optimizes entropy among hard attributes whose branch-conditioned log-ratio structure is low-dimensional.

\begin{proof} For every hard attribute $Z=\phi(X,Y)$, $H(Z\mid X,Y)=0$. Therefore

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

Restricting the feasible set to $\Phi_{K,d}^{\varepsilon}$ does not change this identity. Hence maximizing conditional mutual information over $\Phi_{K,d}^{\varepsilon}$ is exactly maximizing conditional entropy over $\Phi_{K,d}^{\varepsilon}$. \end{proof}

The role of max-info is still entropy maximization. The rank constraint changes the comparison class: high-entropy arbitrary partitions are excluded unless their branch-conditioned log-ratio patterns are also low-dimensional.

---

6. Strategy subspace and subspace recovery

Let $S=\sigma(X,Y)\in[K]$ be the target strategy attribute. Define its strategy log-ratio subspace

$$\mathcal U_S^{\varepsilon} := \operatorname{span}\{\bar L_{S,\varepsilon}(s;\cdot,\cdot):s\in[K]\}.$$

The goal of the low-rank theory is first to recover this subspace. Label recovery is stronger and requires additional geometry.

Subspace recovery means that the learned latent has found the same reusable contrast directions as the strategy variable, even if the individual labels have not yet been identified.

The next result gives the basic population recovery principle. It is intentionally stated as a separation theorem: the nontrivial modeling work is to justify the separation condition from properties of the reasoning process.

\begin{proof} Since $\operatorname{rank}_\varepsilon(S)\le d$, the strategy attribute $S$ lies in $\Phi_{K,d}^{\varepsilon}$. Let $\phi^\star$ be a maximizer. By the rank-constrained hard max-info theorem,

$$H(\phi^\star(X,Y)\mid X) \ge H(S\mid X).$$

If $\phi^\star$ did not recover $\mathcal U_S^{\varepsilon}$, then by the gap assumption,

$$H(\phi^\star(X,Y)\mid X) \le H(S\mid X)-\gamma,$$

contradicting the previous inequality. Hence $\phi^\star$ recovers $\mathcal U_S^{\varepsilon}$. \end{proof}

This theorem does not say that rank alone always identifies strategy. It says that if the true strategy is the highest-entropy low-rank hard attribute, then max-info under the rank constraint recovers the strategy subspace. The substantive question becomes: when should this gap hold?

---

7. Why a rank gap is plausible for strategies

The rank gap is a modeling assumption, but it is less oracle-like than restricting the model to cuts of a known tree. It asserts that the reasoning process contains a reusable low-dimensional structure.

A strategy affects many task-output pairs in a coherent way. For example, “proof by induction” changes which proof outlines, phrases, lemmas, intermediate goals, and local derivations are likely across many theorem statements. This can be represented by a small number of contrast directions.

A high-entropy spurious partition, by contrast, may divide outputs in a nearly balanced way but usually does so by unrelated idiosyncratic criteria across tasks. Its branch-conditioned distributions then require many independent contrast directions, leading to high log-ratio rank.

Thus the low-rank constraint is meant to capture the idea:

$$\text{strategy} = \text{high-information attribute with reusable low-dimensional effects}.$$

---

8. Label recovery from anchors or simplex geometry

Subspace recovery does not necessarily recover the labels. Linear subspaces are invariant under changes of basis. To identify the individual strategy components, one needs additional geometry.

One clean condition is that the strategy profiles are simplex vertices.

The anchor condition says each strategy profile has a direction in the recovered subspace where it is uniquely exposed. This is the low-rank analogue of anchor features or separability assumptions in matrix factorization.

\begin{proof} The convex hull of affinely independent points $m_1, \dots,m_K$ is a simplex. A simplex has a unique set of vertices. Since the row profiles of $\phi$ lie in the simplex and have convex hull equal to the whole simplex, the extreme points of their hull must be exactly $m_1, \dots,m_K$. Therefore the set of row profiles of $\phi$ contains precisely the strategy profiles, up to permutation. If anchor functionals $a_s$ are given, then $m_s$ is the unique row maximizing $a_s$, which fixes the corresponding label. \end{proof}

This result separates two tasks. Rank constraints can recover a strategy subspace. Anchor or simplex geometry is what turns that subspace into named strategy components.

---

9. The relabeling obstruction and rank rigidity

Max-info is invariant under $x$-dependent relabeling. If

$$\phi^\pi(x,y):=\pi_x(S(x,y))$$

for permutations $\pi_x$ of $[K]$, then

$$H(\phi^\pi(X,Y)\mid X)=H(S\mid X).$$

So information alone cannot distinguish $S$ from $\phi^\pi$.

Low-rank structure can distinguish them if the relabeling breaks the shared log-ratio subspace.

Let $M_{S,\varepsilon}$ be the centered log-lift matrix of $S$, with columns grouped by input $x$. For a taskwise permutation field $\pi=(\pi_x)_x$, let $M_{\pi,\varepsilon}$ be the matrix obtained by applying permutation $\pi_x$ to the rows of the block corresponding to input $x$.

Global permutations apply the same row permutation to every block and therefore preserve rank. Nonconstant taskwise permutations may stitch together incompatible strategy profiles across tasks and increase rank.

\begin{proof} Because $\phi(x,y)=\pi_x(S(x,y))$, the centered log-lift matrix of $\phi$ is exactly $M_{\pi,\varepsilon}$, the blockwise row-permuted version of the strategy matrix. The assumption $\operatorname{rank}_\varepsilon(\phi)\le d$ gives $\operatorname{rank}(M_{\pi,\varepsilon})\le d$. By rank rigidity, this is possible only if $\pi_x$ is constant in $x$. Therefore $\phi$ is a global relabeling of $S$. \end{proof}

The rank-rigidity condition is the formal expression of “the same $z$ must be used the same way across tasks.” If labels are permuted independently for each task, the row profiles no longer fit into the same low-dimensional subspace.

---

10. Regularized information-rank objective

The previous results use a hard rank constraint. A regularized version is often more natural:

$$\mathcal J_\lambda(\phi) := H(\phi(X,Y)\mid X)-\lambda\operatorname{rank}_\varepsilon(\phi).$$

The following theorem states the general exposed-frontier principle.

\begin{proof} The displayed inequality is exactly the statement that $S$ has strictly larger regularized objective value than every non-equivalent competitor. Therefore every maximizer is globally equivalent to $S$. \end{proof}

This theorem is abstract but useful: it says recoverable strategies are exposed points of the information-rank frontier. In practice, the constrained version is easier to analyze first, while the regularized version describes how an implicit simplicity bias may select among high-information alternatives.

---

11. Self-evaluation loop and limitations

This note deliberately weakens the oracle assumption in the tree-cut theory. Instead of assuming the true reasoning tree is known, it assumes that true strategies have low-dimensional log-ratio structure. This is closer to the intended setting, but it introduces new assumptions that must be treated carefully.

The theory went through three design passes.

Pass 1: raw rank. A first idea is to rank the matrix of branch-conditioned log-density ratios. This captures reusable strategy directions, but exact hard attributes create zero probabilities and hence infinite log ratios.

Pass 2: smoothed log-lifts. We therefore introduced $g_{\phi,\varepsilon}$ and $L_{\phi,\varepsilon}$, which preserve the branch structure while producing finite matrices. Centering removes per-task normalization offsets.

Pass 3: rank is not labels. Low-rank structure naturally identifies a subspace, not named strategies. The note therefore separates subspace recovery from label recovery, and adds anchors/simplex geometry and rank-rigidity as additional assumptions for semantic labels and global alignment.

Issue 1: exact hard attributes create zeros

A hard attribute gives branch-conditioned distributions with disjoint supports, so literal log-density ratios may be infinite. The smoothing parameter $\varepsilon$ is a technical fix. A more complete theory should prove stability as $\varepsilon\downarrow 0$ or work directly with support-pattern complexity plus finite log-ratio complexity.

Issue 2: rank alone is not always enough

If the feature class is unconstrained, low rank may be too weak. For example, an $x$-dependent relabeling can sometimes be absorbed into a redefined feature map without increasing matrix rank. This is why the rank-rigidity condition is needed for strong recovery.

Issue 3: subspace recovery is weaker than semantic recovery

Low-rank methods naturally identify subspaces or convex geometry, not necessarily named components. Label recovery requires additional separation, anchors, simplex geometry, or another identifiability condition.

Issue 4: the information-rank gap is the key substantive assumption

The theory does not claim that every reasoning distribution has recoverable strategies. It says that strategies are recoverable when they are the most informative attributes compatible with a low-dimensional reusable log-ratio structure. This is the non-oracle replacement for assuming the model knows the semantic tree.

---

12. Main takeaway

The tree-cut theory asks: if the semantic hierarchy is known, which cut does max-info select?

The rank-constrained theory asks a different question:

if strategies are reusable low-dimensional ways of changing the distribution of reasoning traces, does max-info plus a low-rank bias recover them?

The answer, in this first-pass theory, is:

1. for hard attributes, max-info is conditional entropy maximization;
2. a low-rank log-density-ratio constraint restricts the search to reusable branch structures;
3. if the true strategy is the highest-entropy low-rank attribute, max-info recovers its strategy subspace;
4. anchors or simplex geometry recover individual labels from the subspace;
5. rank rigidity can upgrade weak, taskwise recovery to strong global semantic alignment.

This gives a plausible route from the degeneracy of unrestricted max-info to strategy-aligned latent variables without assuming the ground-truth reasoning tree is known in advance.