Deep-layered machines have a built-in Occam's razor

arXiv:2603.01217 · cond-mat.dis-nn, nlin.CG · Submitted 2026-03-01 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Condensed Matter. The day in condensed matter: materials, phases and the measurements under them.

Kai: We're looking at the paper: "Deep-layered machines have a built-in Occam's razor".

Mira: Here's the gist of the paper. Deep-layered machines have a built-in Occam’s razor because they are inherently biased towards simplicity in the models they generate This paper presents a unified understanding of two seemingly different scientific puzzles: the observed tendency of input-output maps to be biased towards simple outputs and the success of deep-layered machines at producing parsimonious solutions The authors introduce an exact theory for the output distribution of deep-layered machines, confirming that this output is exponentially biased towards simplicity as network depth increases.

Kai: The Core Theory of Output Distribution The paper establishes a mathematical theory for the distribution of outputs given a random choice of inputs to a deep-layered machine The output distribution depends only on the Hamming weight of the output function, which is the number of 1s in its truth table.

Mira: For general k arguments, this probability is related to a vector of probabilities p(n) derived from a transition matrix A such that q(n) = Anq(0).

Kai: The elements of the transition matrix A are defined by the formula Ai,j = 1/l(l/j!) (l − i)/(l−j).

Title and authors: Kai: So we're looking at this paper called "Deep-layered machines have a built-in Occam's razor". It basically says that deep layers of machines are naturally biased towards simple outputs, which is something we see in input output maps generally.

Mira: I think the key thing here is connecting that observation to how these deep machines actually work. They're not just random; they generate these simpler functions more often than we'd expect from a purely random process <ref:2603.01217#pg1>.

Lev: From an engineering standpoint, it’s interesting because it suggests we might be designing systems that inherently favor the simplest possible solutions, which could affect how we approach model complexity in real hardware <ref:2603.01217#pg4>.

Kai: Exactly. It's about moving from just observing that simple outputs are common to understanding the mechanism behind why they happen in these specific architectures.

The paper's summary: Mira: The paper sets out to give an exact theory for how the output distribution looks for a deep-layered machine, and it confirms that this output is exponentially biased towards simplicity as you increase the network depth <ref:2603.01217#pg1>.

Kai: They establish that this distribution only depends on the Hamming weight of the output function, which is just how many ones are in its truth table <ref:2603.01217#pg3>.

Lev: So they model this using a transition matrix A where q n equals A n q zero, and they define the elements of that matrix by this formula involving l and i and j <ref:2603.01217#pg3>.

Mira: The core mathematical structure involves a transition matrix with two k plus one eigenvalues; specifically, the first two eigenvalues are one, corresponding to the true and false outputs <ref:2603.01217#pg3>.

Kai: And for large network depths, they show that the probabilities of all other outputs vanish exponentially fast <ref:2603.01217#pg3>.

The paper's improvements: Lev: One major finding is the identification of a critical network depth, n crit, which is related to two k plus one, and beyond that point, this simplicity bias becomes irrelevant because the true and false outputs start dominating <ref:2603.01217#pg3>.

Mira: They also quantify this simplicity bias using information content, defined as I of f equals log base two of twenty k plus one plus log base two of two to the k divided by the Hamming weight <ref:2603.01217#pg4>.

Kai: The visualization they show in figure four for k equals four, six, and eight arguments shows this bias as the logarithm of the probability distribution rotating clockwise from horizontal to a nearly straight line with a slope of negative one <ref:2603.01217#pg4>.

Lev: They also connect this to Kolmogorov complexity, showing that at the critical network depth, the output can be compressed by s bits with probability one over two k plus one, which is constant regardless of s <ref:2603.01217#pg5>.

Conclusion: Mira: So what this means is that we have a very quantifiable way to see this exponential bias towards simplicity getting stronger as the network depth increases in these deep-layered machines <ref:2603.01217#pg4>.

Kai: The main idea they push is that this simplicity bias isn't an isolated incident; it's just one example of a broader phenomenon where repeated application of irreversible local rules generates a global bias towards simplicity <ref:2603.01217#pg4>.

Lev: And they conjecture that this is just one instance, suggesting that the repeated application of irreversible local rules generates this global bias towards simplicity >

Mira: They also suggest studying the opposite extreme, looking at architectures like f of g one g two c d with branching degree two and depth n equal to one, and they found an exponential bias towards simplicity in that structure <ref:2603.01217#pg4>.

Kai: It's a lot to take in because it suggests that the bias towards simplicity isn't just a quirk of these machines but potentially a rule for many learning frameworks <ref:2603.01217#pg1>.

London Institute for Mathematical Sciences · Royal Institution

cond-mat.dis-nn, nlin.CG

Submitted: 2026-03-01

Updated: 2026-11-05

License: http://creativecommons.org/licenses/by-nc-sa/4.0/

Importance score: 89/100

The gist: Deep-layered machines have a built-in Occam’s razor because they are inherently biased towards simplicity in the models they generate This paper presents a unified understanding of two seemingly…

Key concepts

Hamming Weight
This is the number of '1's in a truth table, representing how many inputs result in a true output. The paper uses this to describe the distribution of outputs from deep machines, showing that simple functions (low Hamming weight) are more likely as depth grows.
Critical Network Depth (ncrit)
This is a specific network depth where the bias towards simplicity becomes irrelevant because true and false outputs start dominating the output distribution. This depth is suggested to grow with 2k, allowing systems to choose complexity based on this point.
Spectral Gap
The difference between eigenvalues governing different parts of the network's behavior. A specific gap relates to how quickly the true/false outputs equilibrate compared to the bulk outputs, indicating when simplicity bias loses its dominance.

Terminology

Summary

Deep-layered machines have a built-in Occam’s razor because they are inherently biased towards simplicity in the models they generate This paper presents a unified understanding of two seemingly different scientific puzzles: the observed tendency of input-output maps to be biased towards simple outputs and the success of deep-layered machines at producing parsimonious solutions The authors introduce an exact theory for the output distribution of deep-layered machines, confirming that this output is exponentially biased towards simplicity as network depth increases. p. 0

Where the paper says it

The second is the success of deep-layered machines and other learning frameworks at producing parsimonious solutions [3, 4]. Our overall approach is to introduce an exact theory for the output of deep-layered machines, show that this output is biased towards simplicity and, by regarding learning frameworks as input-output maps, argue that they have a built-in Occam’s razor.

The Core Theory of Output Distribution

The paper establishes a mathematical theory for the distribution of outputs given a random choice of inputs to a deep-layered machine The output distribution depends only on the Hamming weight of the output function, which is the number of 1s in its truth table. For general k arguments, this probability is related to a vector of probabilities p(n) derived from a transition matrix A such that q(n) = Anq(0). p. 4

Where the paper says it

Example of the eigenvalues and eigenvectors For k = 2, the transition matrix A has 22 + 1 eigenvalues λ and eigenvectors v: λ1 = 1 v1 = (0 0 0 0 1) λ2 = 1 v2 = (1 0 0 0 0) λ3 = 3/4 v3 = (−1 16/25 18/25 16/25 −1) λ4 = 3/8 v4 = (−1 2 0 −2 1) λ5 = 3/32 v5 = (1 −4 6 −4 1). Then the probability distribution q(n) of the output having Hamming weight w is q(n) = Anq(0) = c1v1 + c2v2 + c3λ n 3 v3 + c4λ n 4 v4 + c5λ n 5 v5.

The elements of the transition matrix A are defined by the formula Ai,j = 1/l(l/j! p. 2
Where the paper says it

3 There exists a 2k + 1 by 2k + 1 transition matrix A such that q(n) = A n q(0). (2) The elements of A are Ai,j = 1 ℓ ℓ ℓ j !

) (l − i)/(l−j).

Evidence from Computer Experiments

The theoretical predictions are confirmed through extensive computer experiments across various values of k and network depth n. For k = 2 arguments, the authors enumerated all input configurations for depths n = 1 to 4 and plotted the probability q(n) of obtaining a given Hamming weight w, which exactly matched their theoretical predictions. p. 2

Where the paper says it

We enumerated all of these inputs and, for each, determined the network’s output function. Since the probability of an output is the same for outputs with the same Hamming weight w, we plot the probability q(n) of obtaining a given w in Fig.

Similar results were found for k = 3 arguments by enumerating inputs for n = 0 and 1, and sampling inputs for n = 2 and 3. p. 2
Where the paper says it

Because the computational cost of enumerating all possible inputs is formidable—it grows as 2 2 k nk+1—our experiments include complete enumeration when possible, and sampling from the ensemble of inputs otherwise. For k = 2 arguments (Fig.

Quantifying Simplicity Bias

The simplicity bias is quantified using the information content of a logic function, defined as I(f) = log2(2k + 1) + log2(2 k/w). The distribution of output functions f is shown to be biased towards simplicity in Fig. p. 4

Where the paper says it

Critical network depth Crucially, the bias of the bulk towards simplicity happens faster than true and false take over—the distribution flattens out before it diminishes. We have verified this computationally, as shown in Fig.

4 for k = 4, 6, and 8 arguments as the network depth n increases. p. 0
Where the paper says it

We give an exact theory for the distribution of outputs, and we confirm our predictions through extensive computer experiments. As the network depth increases, the distribution becomes exponentially biased towards simple outputs.

This bias manifests as the logarithm of the probability distribution rotating clockwise from horizontal to a nearly straight line with slope −1. p. 3
Where the paper says it

The vertical axis is the probability of an output function and the horizontal axis is its information content given by eq. As the network depth n increases, the logarithm of the probability distribution of the output rotates clockwise from horizontal to a nearly straight line with slope −1.

Critical Network Depth and Generalization

The paper identifies a critical network depth ncrit beyond which the simplicity bias becomes irrelevant because true and false outputs dominate. This depth is suggested to grow as 2k, with true and false starting to dominate around network depth 2k. p. 4

Where the paper says it

Since the equilibration time is proportional to the inverse of the spectral gap, ncrit grows as 2k . A separate argument, given in the Methods, likewise suggests that true and false start to dominate around network depth 2k .

The authors conjecture that this bias towards simplicity is just one instance of a more general phenomenon where the repeated application of irreversible local rules generates a global bias towards simplicity. p. 4
Where the paper says it

For this branching architecture we also observed an exponential bias towards simplicity. We conjecture that the bias towards simplicity described in this paper is just one instance of a more general phenomenon: the repeated application of irreversible local rules generates a global bias towards simplicity.

Kolmogorov Complexity Connection

The output of a deep layered machine can be compressed by s bits with probability 1/(2k+1) at the critical network depth, which is important because it is a constant independent of s. This contrasts with an arbitrary logic of k arguments which can be compressed by s bits with probability 1/2 s for large enough l. p. 4

Where the paper says it

This is an important conclusion. Whereas an arbitrary logic of k arguments can be compressed by s bits with probability 1/2 s , the output of a deep layered machine can be compressed by s bits with probability 1/(2k+1) at the critical network depth.

p. 4
Where the paper says it

This is an important conclusion. Whereas an arbitrary logic of k arguments can be compressed by s bits with probability 1/2 s , the output of a deep layered machine can be compressed by s bits with probability 1/(2k+1) at the critical network depth.

Methods and Composition

The methods section details the representation and composition of logics, noting that the order of operations is defined as and takes precedence over xor, which takes precedence over or. For example, for k = 2 arguments and network depth n = 1, the output is f(g1(a, b), g2(a, b)). p. 1

Where the paper says it

2: Inputs-output map for two arguments. For k = 2 arguments and network depth n = 1, there are 163 inputs but only 16 outputs.

The composition of logics works just like the composition of ordinary functions. p. 4
Where the paper says it

The order of operations is and takes precedence over xor, which takes precedence over or. The composition of logics works just like the composition of ordinary functions.

Eigenvalue Analysis

The transition matrix A has 2k + 1 eigenvalues, where the first two eigenvalues are λ1 = λ2 = 1, corresponding to the eigenvectors (1, 0,..., 0) and (0,..., 0, 1). The third eigenvalue λ3 is given by the formula λj = (l)(j-1)/l(j-1), where l = 2k. p. 2

Where the paper says it

, 0) and (0, . As we confirm in Methods, the jth eigenvalue is λj = (ℓ)j−1 ℓ j−1 , (4) where ℓ = 2k and (ℓ)j = ℓ(ℓ − 1).

This structure dictates the behavior of the bulk outputs, which are governed by the third eigenvector v3. p. 5
Where the paper says it

So the ratio of the smallest and largest components of the interior of the third eigenvector of A is at least (1 − e)/e and at most 1. Critical network depth The first two eigenvalues govern the leading behavior of the endpoints (true and false), and the third eigenvalue governs the leading behavior of everything else (the bulk).

Spectral Gap and Equilibration

The spectral gap λ1 − λ3 = λ2 − λ3 = 1/2 k governs the equilibration of true and false, while the spectral gap λ3 − λ4 = (1 - 1/2 k) 2/2 k governs the equilibration of the bulk. This difference in time scales implies that a critical network depth ncrit exists where simplicity bias is irrelevant because the distribution is dominated by true and false. p. 4

Where the paper says it

From a mathematical perspective, this is because the spectral gap λ1 − λ3 = λ2 − λ3 = 1/2 k , which governs the equilibration of true and false, is smaller than the spectral gap λ3 − λ4 = (1 − 1/2 k ) 2/2 k ≃ 2/2 k , which governs the equilibration of the bulk. Intriguingly, these two time scales—one for the endpoints and one for the bulk—implies the existence of a critical network depth ncrit beyond which the simplicity bias is irrelevant because the distribution is dominated by true and false.

Generalizations and Future Work

The authors conjecture that the bias towards simplicity described is just one instance of a more general phenomenon: the repeated application of irreversible local rules generates a global bias towards simplicity. They also considered an opposite extreme, studying f(g1(a, b), g2(c, d)) (branching degree 2 and n = 1) and observed an exponential bias towards simplicity in that architecture. p. 4

Where the paper says it

For example, instead of f(g1(a, b), g2(a, b)) (k = 2 and n = 1), we studied f(g1(a, b), g2(c, d)) (branching degree 2 and n = 1). For this branching architecture we also observed an exponential bias towards simplicity.

Transition Matrix Trace Confirmation

The trace of the transition matrix A is shown to be equal to the sum of its eigenvalues, which is confirmed by Abel’s binomial theorem applied to the formula for tr(A). The trace is calculated as tr(A) = Xlj=0 (l)(j)/j! p. 2

Where the paper says it

3B (points). We calculated errors A k = 2 n = 0 n = 1 n = 2 n = 3 n = 4 F T 0 1 2 3 4 0.

Critical Network Depth Derivation

The critical network depth ncrit is derived by setting the probability of the endpoints equal to the probability of the interior, leading to ncrit = 2k ln(4 c3), where c3 ∼ 1. This suggests that true and false start to dominate around network depth 2k. p. 4

Where the paper says it

Since the equilibration time is proportional to the inverse of the spectral gap, ncrit grows as 2k . A separate argument, given in the Methods, likewise suggests that true and false start to dominate around network depth 2k .

Asymptotic Behavior of Endpoints

The probability of true and false each asymptotically approach 1/2, although faster than this lower bound argument suggests. This asymptotic behavior is supported by the intuitive proof that at each level in the network, there is a finite probability that all of the k logics are true, independent of the level n. p. 4

Where the paper says it

As an aside, there is an intuitive proof that true and false must dominate eventually. At each level in the network, there is a finite probability that all of the k logics are true, independent of the level n.

Comparison with Related Work

The paper references prior work on related phenomena, including input-output maps being strongly biased towards simple outputs, and observations from Mozeika et al. [12] regarding deep-layered machines with rectified linear unit functions computing only constant Boolean functions in the infinite depth limit. p. 4

Where the paper says it

Mozeika et al. [12] observed a similar phenomena when they considered deep-layered machines with rectified linear unit functions: “random deep ReLU networks compute only constant Boolean functions in the infinite depth limit”.

The work also references studies on biological logics being restricted. p. 5
Where the paper says it

Fink and R. Hannam, Biological logics are restricted, arxiv.

Acknowledgements and Competing Interests

The author thanks Evgeny Sobko for helpful discussions, and declares that he has no competing interests. The paper includes references [1] through [8] in the acknowledgements section. p. 1

Where the paper says it

2 In this section we work out the exact probability of the output of a deep-layered machine given a random input, that is, a random assignment of logics to the light gray nodes in Fig. Distribution for small k In a deep-layered machine, each Boolean function, or logic for short, depends on the k arguments in the layer below it.

The list of references is provided at the end of the paper. p. 0
Where the paper says it

This suggests that deep-layered machines and other learning methodologies may be inherently biased towards simplicity in the models that they generate. Introduction This paper presents a unified understanding of two seemingly different scientific puzzles.

Input-Output Map Context

Input-output maps are prevalent throughout science and technology, and they tend to be many-to-one because a lot of different instructions produce the same function—there’s more than one way to skin a cat. The authors frame learning frameworks as input-output maps with a constraint on the output, arguing that deep-layered machines have a built-in Occam’s razor. p. 0

Where the paper says it

The second is the success of deep-layered machines and other learning frameworks at producing parsimonious solutions [3, 4]. Our overall approach is to introduce an exact theory for the output of deep-layered machines, show that this output is biased towards simplicity and, by regarding learning frameworks as input-output maps, argue that they have a built-in Occam’s razor.

They study the archetypal input-output map: a deep-layered machine in which every node is a Boolean function of all the nodes below it. p. 0
Where the paper says it

They are empirically observed to be biased towards simple outputs, but we don’t understand why. To address this puzzle, we study the archetypal input-output map: a deep-layered machine in which every node is a Boolean function of all the nodes below it.

The goal is to show that learning frameworks are biased towards the simplest outputs that meet constraints. p. 0
Where the paper says it

The task is to find a set of weights that yields one of the many valid cat and dog classifiers. As we shall see, just as Occam’s razor prescribes the simplest explanation that fits the facts, deep-layered machines are biased towards the simplest outputs that meet the constraints.

p. 0
Where the paper says it

The task is to find a set of weights that yields one of the many valid cat and dog classifiers. As we shall see, just as Occam’s razor prescribes the simplest explanation that fits the facts, deep-layered machines are biased towards the simplest outputs that meet the constraints.

Puzzle Illustration

A conceptual understanding of the simplicity bias is illustrated by a puzzle about friends where one's mood depends on the moods of Alice and Bob, and this dependency structure is shown in Fig. 1 and Fig. 2. The favored dependencies are simple in that they are happy most of the time or sad most of the time. p. 0

Where the paper says it

The chance of copying one and ignoring the other (happy 1/2 of the time) is 4%. The favored dependencies are simple in that they are happy most of the time or sad most of the time.

The bias becomes stronger when extending the game such that Carol and Dan each depend on Eve and Frank. p. 0
Where the paper says it

The favored dependencies are simple in that they are happy most of the time or sad most of the time. Were we to extend the game such that the mood of Carol and Dan each depends on Eve and Frank, the bias would be stronger still.

Distribution of Outputs Visualization

The distribution of output functions is shown in Fig. 4 for k = 4, 6, and 8 arguments across various network depths n. p. 2

Where the paper says it

For k = 2 arguments (Fig. 1A), there are 163 , 165 , 167 and 169 input configurations for network depths n = 1, 2, 3 and 4.

The orange points represent the third eigenvector of A, which governs the shape of the bulk distribution translated from q to p via eq. p. 3
Where the paper says it

For clarity the rising curves are black and the falling curves are gray. The orange points are the third eigenvector of A, which governs the shape of the bulk, translated from q to p via eq.

(1). As n increases, the distribution appears to approach them before falling away. p. 3
Where the paper says it

4 by the orange points. As n increases, the distribution appears to approach them before falling away.

The line which they approach is −I. p. 2
Where the paper says it

The solid line indicates the probabilities of the bulk of the outputs and the dotted line connects to the outputs true (w = 4) and false (w = 0). As n increases, the likelihood of true and false approach 1/2 and the likelihoods of the remaining outputs fall, bearing in mind that the likelihoods sum to one.

Final Conclusion on Bias

The authors conclude that the distribution of output functions is exponentially biased towards simplicity in a surprisingly quantifiable way, and this effect gets stronger as the network depth n increases. The conjecture is that the bias towards simplicity described is just one instance of a more general phenomenon: the repeated application of irreversible local rules generates a global bias towards simplicity. p. 4

Where the paper says it

For this branching architecture we also observed an exponential bias towards simplicity. We conjecture that the bias towards simplicity described in this paper is just one instance of a more general phenomenon: the repeated application of irreversible local rules generates a global bias towards simplicity.

p. 4
Where the paper says it

For this branching architecture we also observed an exponential bias towards simplicity. We conjecture that the bias towards simplicity described in this paper is just one instance of a more general phenomenon: the repeated application of irreversible local rules generates a global bias towards simplicity.

Simplicity bias in input-output maps is not the exception but the rule. p. 4
Where the paper says it

We conjecture that the bias towards simplicity described in this paper is just one instance of a more general phenomenon: the repeated application of irreversible local rules generates a global bias towards simplicity. In other words, simplicity bias in input-output maps is not the exception but the rule.

p. 4
Where the paper says it

We conjecture that the bias towards simplicity described in this paper is just one instance of a more general phenomenon: the repeated application of irreversible local rules generates a global bias towards simplicity. In other words, simplicity bias in input-output maps is not the exception but the rule.

Methods for Composition

When composing logics by hand, it’s convenient to write them in disjunctive normal form, which consists of a disjunction of conjunctions: we write them as ors of ands, or sums of products. The composition works just like the composition of ordinary functions. p. 4

Where the paper says it

The order of operations is and takes precedence over xor, which takes precedence over or. The composition of logics works just like the composition of ordinary functions.

p. 4
Where the paper says it

The order of operations is and takes precedence over xor, which takes precedence over or. The composition of logics works just like the composition of ordinary functions.

For k = 2 arguments and network depth n = 1, the output is f(g1(a, b), g2(a, b)). p. 1
Where the paper says it

2: Inputs-output map for two arguments. For k = 2 arguments and network depth n = 1, there are 163 inputs but only 16 outputs.

p. 1
Where the paper says it

2: Inputs-output map for two arguments. For k = 2 arguments and network depth n = 1, there are 163 inputs but only 16 outputs.

The example shows that if f = g1g2 then f = a xor b. p. 4
Where the paper says it

(6) Set g1 = a or b and g2 = a or b, that is, g1 = a + b, g2 = a + b. If we set f = g1 and g2, then f = g1g2 = (a + b)(a + b) = ab + ab = a ⊕ b, that is, f = a xor b.

p. 4
Where the paper says it

(6) Set g1 = a or b and g2 = a or b, that is, g1 = a + b, g2 = a + b. If we set f = g1 and g2, then f = g1g2 = (a + b)(a + b) = ab + ab = a ⊕ b, that is, f = a xor b.

Input-output maps are prevalent in biology, physics, mathematics and technology. The inputs can be thought of as instructions, and the outputs can be thought of as functions. p. 0

Where the paper says it

Input-output maps are prevalent in biology, physics, mathematics and technology. The inputs can be thought of as instructions, and the outputs can be thought of as functions.

p. 0
Where the paper says it

Input-output maps are prevalent in biology, physics, mathematics and technology. The inputs can be thought of as instructions, and the outputs can be thought of as functions.

In neural networks, synapse weights (input) determine the overall function of the arguments (output). p. 0
Where the paper says it

A similar process occurs in 3D when proteins self-assemble into protein complexes. In neural networks, synapse weights (input) determine the overall function of the arguments (output).

p. 0
Where the paper says it

A similar process occurs in 3D when proteins self-assemble into protein complexes. In neural networks, synapse weights (input) determine the overall function of the arguments (output).

The authors study the archetypal input-output map: a deep-layered machine in which every node is a Boolean function of all the nodes below it. p. 0
Where the paper says it

They are empirically observed to be biased towards simple outputs, but we don’t understand why. To address this puzzle, we study the archetypal input-output map: a deep-layered machine in which every node is a Boolean function of all the nodes below it.

p. 0
Where the paper says it

They are empirically observed to be biased towards simple outputs, but we don’t understand why. To address this puzzle, we study the archetypal input-output map: a deep-layered machine in which every node is a Boolean function of all the nodes below it.

Deep Learning Connection

The paper encompasses discrete neural networks in which the logics are threshold Boolean functions. The authors confirm their theory through extensive computer experiments for networks of different sizes, matching their theoretical predictions exactly or to within statistical significance. p. 3

Where the paper says it

Our theory predicts the computer experiments exactly for n = 1 and to within statistical significance for n = 2 and 3. We also show our n = 4 predictions for comparison.

This suggests that a broad range of learning frameworks are biased towards simplicity in the models that they generate. p. 0
Where the paper says it

Four, we conjecture that this bias is part of a more general phenomenon in which the repeated application of irreversible rules gives rise to a bias towards simple outputs. If so, it suggests that a broad range of learning frameworks are biased towards simplicity in the models that they generate.

Pruning Redundant Reasoning Tokens

The first two eigenvalues are λ1 = λ2 = 1, corresponding to the eigenvectors (1, 0,..., 0) and (0,..., 0, 1). The leading eigenvector for the bulk is approximately flat apart from the endpoints. p. 4

Where the paper says it

Leading eigenvector for the bulk is flat The third eigenvector of the transition matrix A is the principal eigenvector for the bulk of the outputs (everything but true and false). We are unable to work it out explicitly, but we can show that, apart from the endpoints, it is approximately flat.

This flatness is key to the main result of exponential bias towards simple outputs. p. 2
Where the paper says it

632 and at most 1. As we shall see, this flatness is key to our main result, namely, that the distribution of output functions is exponentially biased towards simple outputs.

The spectral gap λ3 − λ4 = (1 - 1/2 k) 2/2 k governs the equilibration of the bulk. p. 4
Where the paper says it

4 from the p perspective (the probability of the output). From a mathematical perspective, this is because the spectral gap λ1 − λ3 = λ2 − λ3 = 1/2 k , which governs the equilibration of true and false, is smaller than the spectral gap λ3 − λ4 = (1 − 1/2 k ) 2/2 k ≃ 2/2 k , which governs the equilibration of the bulk.

Comparison with Kolmogorov Complexity

The probability of some f with information content I approaches 1/(l + 1), which is a constant, independent of s, and it is also the probability that the string can be compressed by s bits. This contrasts with an arbitrary logic of k arguments which can be compressed by s bits with probability 1/2 s for large enough l. The output of a deep layered machine can be compressed by s bits with probability 1/(2k+1) at the critical network depth. p. 4

Where the paper says it

This is an important conclusion. Whereas an arbitrary logic of k arguments can be compressed by s bits with probability 1/2 s , the output of a deep layered machine can be compressed by s bits with probability 1/(2k+1) at the critical network depth.

Discussion on Critical Depth

The first two eigenvalues govern the leading behavior of the endpoints (true and false), and the third eigenvalue governs the leading behavior of everything else (the bulk). The critical network depth ncrit grows as 2k, with true and false starting to dominate around network depth 2k. p. 4

Where the paper says it

Since the equilibration time is proportional to the inverse of the spectral gap, ncrit grows as 2k . A separate argument, given in the Methods, likewise suggests that true and false start to dominate around network depth 2k .

The existence of ncrit is suggested by the spectral gap λ1 − λ3 = 1/2 k, which is smaller than the spectral gap λ3 − λ4 = (1 - 1/2 k) 2/2 k. p. 4
Where the paper says it

From a mathematical perspective, this is because the spectral gap λ1 − λ3 = λ2 − λ3 = 1/2 k , which governs the equilibration of true and false, is smaller than the spectral gap λ3 − λ4 = (1 − 1/2 k ) 2/2 k ≃ 2/2 k , which governs the equilibration of the bulk. Intriguingly, these two time scales—one for the endpoints and one for the bulk—implies the existence of a critical network depth ncrit beyond which the simplicity bias is irrelevant because the distribution is dominated by true and false.

The argument that true and false must dominate eventually is based on a finite probability that all k logics are true at each level. p. 4
Where the paper says it

As an aside, there is an intuitive proof that true and false must dominate eventually. At each level in the network, there is a finite probability that all of the k logics are true, independent of the level n.

Methods for Composing Logics

When composing logics by hand, it’s convenient to write them in disjunctive normal form, which consists of a disjunction of conjunctions: we write them as ors of ands, or sums of products. The composition works just like the composition of ordinary functions. For k = 2 arguments and network depth n = 1, the output is f(g1(a, b), g2(a, b)). The example shows that if f = g1g2 then f = a xor b.

Input-output maps are prevalent in biology, physics, mathematics and technology. The inputs can be thought of as instructions, and the outputs can be thought of as functions. In neural networks, synapse weights (input) determine the overall function of the arguments (output). The authors study the archetypal input-output map: a deep-layered machine in which every node is a Boolean function of all the nodes below it. The goal is to show that learning frameworks are biased towards the simplest outputs that meet constraints.

The distribution of output functions is shown to be biased towards simplicity in a surprisingly quantifiable way, and this effect gets stronger as the network depth n increases. p. 3

Where the paper says it

) is biased towards simplicity in a surprisingly quantifiable way. This effect gets stronger as the network depth n increases.

The conjecture is that the bias towards simplicity described is just one instance of a more general phenomenon: the repeated application of irreversible local rules generates a global bias towards simplicity. Simplicity bias in input-output maps is not the exception but the rule. The distribution of output functions is shown to be biased towards simplicity in a surprisingly quantifiable way, and this effect gets stronger as the network depth n increases.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Development of a bias-aware learning framework that incorporates an explicit Occam's razor mechanism into its architecture to inherently favor parsimonious solutions during model generation. This system can generate models that are exponentially biased towards simple outputs, as demonstrated by the distribution of output functions in deep-layered machines.

  2. Implementation of a network depth control mechanism based on the critical network depth ncrit, which is proportional to 2k, to dynamically manage model complexity based on desired simplicity versus accuracy trade-offs. This allows the system to operate in a regime where the simplicity bias is irrelevant because the distribution is dominated by true and false.

  3. A method for analyzing and pruning neural network architectures by monitoring the spectral gap between eigenvalues governing endpoint behavior (true/false) and bulk behavior, enabling early detection of when model complexity starts favoring simple outputs. This helps identify the optimal network depth before excessive computational resources are wasted on overly complex models.

Abstract

Many complex systems map vast numbers of microscopic descriptions onto far fewer macroscopic outcomes. Surprisingly, these input-output maps strongly favor simple outputs. In an exactly solvable deep-layered machine, we prove that simplicity bias strengthens with every layer. The probability of an output function F approaches (F) proportional to 2-K(F), where K is the Kolmogorov complexity. Our results show that hierarchical composition alone can generate an intrinsic Occam's razor, suggesting a general mechanism for simplicity bias in learning and evolution.

Sources

Related papers