Choosing the Reference Machine: Library Priors for Description-Length Training

Occam's razor, in its mathematically exact form, says to prefer the hypothesis with the shortest program on a universal computer. That length, the Kolmogorov complexity, cannot be computed, so every practical learner substitutes something computable for it. Recent work shows that a well-chosen substitute can rank solutions correctly and still be useless in practice. Shaw et al. built a differentiable description-length objective for Transformers. It counts the bits needed to encode the weights plus the bits needed to encode the data given the weights. On the parity task, the objective scores a hand-compiled, length-general Transformer (100% out-of-distribution accuracy) as simpler than ordinary solutions. Adam, started from random weights, never finds that solution and reaches only 60.4%. The failure has a specific signature, "prior collapse": the learned mixture-of-Gaussians prior over weight values, which should form a discrete codebook, merges into a single blob.

This note argues that the missing ingredient is a choice of reference machine, the "language" in which simplicity is measured, and that inductive bias transfer is the natural way to supply one. Kolmogorov complexity depends on the reference universal machine only up to an additive constant. That constant can be arbitrarily large at finite sample sizes (All Kolmogorov complexity functions are optimal, but are some more optimal?), so in practice the reference machine is the prior. We propose to measure a student's weights not in bits relative to nothing, but in bits relative to a library of weight motifs extracted from compiled Transformer programs for other tasks. This is a continuous, block-level version of Mahmud's conditional-complexity transfer. The claim can be tested: with the target task held out of the library, description-length training under a library prior should recover length-general solutions that the same objective under a from-scratch or fixed-grid prior cannot.

Core Claim

Prior collapse is not a flaw of the description-length idea. It happens because a prior learned from scratch has no reason to place its modes where algorithmic solutions live. A prior whose components are weight blocks from compiled programs (attention query-key products, value-output products, and multilayer-perceptron blocks) fixes the codebook before training starts. This makes pointing at a known algorithmic part cheap. It also reshapes the map from parameters to functions so that random draws from the prior already favor algorithmic functions. Mimetic initialization (Trockman and Kolter) appears as the degenerate case of a one-motif library, since it sets attention products to scaled identities plus noise. Shaw et al.'s adaptive prior is the degenerate case of a scalar-level library learned from nothing. The new element is a structured, cross-task library that serves both as the prior and as the initialization distribution.

Concretely, for weights $\theta$ grouped into blocks $\theta_b$ with variational posterior $q(\theta)$ and data $D$, the student minimizes

$$\mathcal{L}(q) = \mathbb{E}_{q}[-\log p(D \mid \theta)] + \mathrm{KL}\big(q(\theta)\,\|\,p_{\mathrm{lib}}(\theta)\big),$$

$$p_{\mathrm{lib}}(\theta) = \prod_b \Big[\pi_0\,\mathcal{N}(\theta_b; 0, \tau^2 I) + \sum_{m=1}^{M} \pi_m\,\mathcal{N}(\theta_b; s_b M_m, \sigma^2 I)\Big].$$

Here $M_m$ are the $M$ library motifs, $s_b$ is a per-block scale whose cost is counted in bits, $\pi_m$ are mixture weights, and the $\pi_0$ "escape" component lets a block ignore the library at a cost. The KL term is the bits-back code length of the weights, as in Shaw et al. The escape component is what should prevent negative transfer, following Mahmud's argument: an unrelated library costs at most roughly the bits needed to select the escape.

Research Program

The first step is building the library. Using the program-to-weights compiler of Shaw et al., we compile Transformers for the synthetic tasks of Zhou et al. (counting, mode, reversed addition with index hints) and for tasks from the Chomsky-hierarchy suite used by Grau-Moya et al.. We then cut the compiled weights into motifs at the attention-head and MLP-block level. Student width matches the compiler's residual-stream layout, so motifs align without a learned permutation. Relaxing that assumption is a later extension.

All evaluation is leave-one-out. For each target task, every motif compiled for that task is removed, together with any motif that duplicates one of them. Library size and composition are then varied to measure how transfer scales with the number and relatedness of source programs. Mahmud evaluated only one-to-one transfer and left this scaling question open.

The second step is diagnosing the mechanism rather than just scoring accuracy. We track three quantities: the effective number of prior components in use during training (prior collapse shows up as this number falling to one), the final weight description length in bits, and whether trained students land in the basin of the held-out compiled solution. The basin test interpolates between the student and the compiled solution and checks for a loss barrier.

We also borrow the function-space view of Valle Pérez et al., who showed that random networks put exponentially more probability on simple functions. We sample weights from each prior and enumerate the Boolean functions the resulting networks compute on short inputs. We then ask whether the library prior shifts probability mass from low Lempel-Ziv-complexity functions toward algorithmic ones such as parity. This speaks directly to the tension raised by the CVPR 2025 study of optimal inductive biases. That study found that the ReLU simplicity bias hurts algorithmic tasks and causes grokking. Our reading is that it hurts because "simple" was being measured on the wrong reference machine, not because description-length minimization is wrong for algorithms.

Baselines

The naive reference point is standard maximum-likelihood training of the same Transformer with weight decay. Shaw et al. report 56.4% out-of-distribution accuracy on parity for it. The strongest method within the description-length family is Shaw et al.'s adaptive-mixture variational objective, which reaches 60.4% out-of-distribution accuracy on parity. The compiled solution's 100% is the ceiling. We rerun both baselines with the same architecture, training lengths, test lengths, optimizer, number of seeds, and hyperparameter search budget as our method, so that the comparison does not depend on reproducing their exact numbers. Our method beats this baseline only if leave-parity-out library training clearly exceeds the rerun Shaw objective across seeds, and reaches the compiled solution's basin in a meaningful fraction of runs.

The scratchpad approach of Zhou et al. reaches 100% on length-50 parity after training on lengths up to 30. We report it as an upper reference, not as a like-for-like competitor, because it requires supervised intermediate traces while our method changes only the prior. For the Chomsky-hierarchy tasks, the file gives only qualitative gains, so there is no reported result found on Lacuna for per-task accuracy numbers. We will produce our own baseline numbers there.

Four ablations isolate the key ingredient. The first is a fixed quantization-grid prior with the same number of components, which tests whether any fixed codebook prevents collapse. The second is a random library: blocks with the same norms and spectra as the real motifs but shuffled structure. The third is a one-motif mimetic library. The fourth separates the two roles of the library by using it as the initialization distribution only, or as the prior only. The claim survives only if the real library beats the random library and the fixed grid at matched bit budgets.

Why not just…?

Why not just distill from an LSTM that already length-generalizes? Grau-Moya et al. report that LSTMs extrapolate up to four times their training length, so an LSTM teacher is tempting. On deterministic tasks like parity, however, the teacher's outputs at training lengths are just the labels. Logit distillation then adds almost nothing unless the teacher labels longer sequences, and that turns the method into length augmentation and changes the problem. What Mechanisms Does Knowledge Distillation Distill? further finds that students copy outputs while skipping the teacher's mechanism, and that even Jacobian matching transfers mechanisms incompletely. We include LSTM-teacher distillation, with both logit matching and Jacobian matching, queried only at training lengths. If it matches our method, the library idea is unnecessary and we will say so.

Why not just use a scratchpad? It works: Zhou et al. report 100% on parity. But it requires task-specific trace annotation. Zhou et al. also show that a scratchpad can hurt when it lengthens the required program, as on the Mode task. Our question is whether the objective alone can find the short program. Scratchpads answer a different question.

Why not just initialize at the compiled solution, or use mimetic initialization? Initializing at the target's compiled solution is not learning. The leave-one-out protocol forbids it. Mimetic initialization is included as the one-motif ablation. Its reported gains shrink from about 4% to about 0.5% under long, heavily tuned training, which suggests a single generic motif is too weak to steer toward a specific algorithm. This is the real threat. If mimetic or fixed-grid priors match the full library, then the effect is about quantization, not transferred structure.

Why not just use weight decay or other standard regularizers? The maximum-likelihood baseline already includes weight decay and sits at 56.4%. The label-noise failures reported for network-to-network regularization, where cross-entropy training drops to about 66% on MNIST with 50% label noise, point the same way. We also add network-to-network regularization itself as a same-family complexity-anchor comparison.

Proposed Experiments

The first decisive check is parity under leave-parity-out. The library is built from compiled counting, mode, addition, and Chomsky-task programs. We measure out-of-distribution length accuracy, weight bits, effective component count over training, and basin arrival rate across seeds, against the rerun Shaw objective and all ablations. A positive result is a large margin over 60.4%-class performance with no collapse in component usage, and the random-library control failing.

The second check repeats leave-one-out for each Zhou and Chomsky-hierarchy task. We plot the gain against library size and against a relatedness score, namely the number of bits the escape component saves.

The third check is a negative-transfer test that pairs algorithmic targets with a library of vision-style motifs, such as mimetic identity patterns. Mahmud's guarantee predicts performance close to the no-transfer objective, not below it.

The fourth check is the function-space enumeration on small Boolean inputs. It asks whether priors that train better also place more prior mass on the target function class before any data is seen. That would connect the transfer effect to parameter volume in the sense of Pakman et al., who found that the volume of good solutions in parameter space dominates generalization once there is enough data.

A null result is also informative. If the real library, random library, and fixed grid all perform alike, prior collapse is an optimization pathology unrelated to what the prior encodes.