Pith. sign in

REVIEW 4 major objections 4 minor 50 references

A Minimum Description Length Approach to Regularization in Neural Networks

T0 review · 4 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read MDL regularization keeps perfect solutions; L1 and L2 push them away.

desk verdict Plausible core result — MDL keeps golden RNN solutions where L1/L2 don't — but the optimizer-independence claim outruns the evidence and the GA comparison needs a λ-sweep and seeds. read the letter →

arxiv 2505.13398 v2 pith:UILYYBCZ submitted 2025-05-19 cs.LG cs.CL

Matan Abudy , Orr Well , Emmanuel Chemla , Roni Katzir , Nur Lan This is my paper · ORCID
classification cs.LGcs.CL
keywords minimumdescriptionlengthregularizationneuralnetworksformallanguagesgeneticalgorithmgradientdescentgeneralizationinductivebias
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper argues that the failure of neural networks to learn exact, rule-based solutions is often a failure of the objective function, not of the architecture or optimizer. To test this, the authors build 'golden' networks that perfectly match the true distribution of six formal languages (counting languages, Dyck parentheses, arithmetic syntax, and a miniature English), then train copies of these perfect networks under different regularization schemes. With no regularization, L1, or L2, training pushes the networks away from the perfect solution and raises test cross-entropy; with Minimum Description Length (MDL) regularization, which minimizes the total number of bits needed to describe the network plus the data under it, the perfect solution is preserved or compressed. The paper concludes that MDL supplies an inductive bias that standard regularizers lack, and that the choice of regularization can determine whether a model generalizes exactly or merely approximates.

What carries the argument

The central object is the MDL score |H| + |D:H|, where |H| is the encoded length of the network and |D:H| is the model's log-loss on the data. The |H| term encodes each weight as a signed fraction using a prefix-free code, so a weight like 1/10 gets a short description while a numerically smaller but high-precision weight like 1117/50000 gets a long one; this is what lets MDL penalize information smuggling through precise weight values. The claim is that minimizing this sum creates a bias toward simple networks that still fit the data, which is why a compact golden solution is selected over a larger approximation.

What would settle it

Run the same six-task, golden-network protocol under MDL with a different prefix-free code for weights, for example a standard binary floating-point code instead of the fractional code. If L1 or L2 then preserves the golden solution as well as or better than MDL, the reported advantage is an artifact of the chosen complexity measure rather than of the MDL principle.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that the MDL objective |H|+|D:H| makes a perfect solution a stable minimum, while cross-entropy with L1, L2, or no regularization does not. Starting from golden networks, the genetic search under MDL stayed at or near the optimal test score across all six tasks and usually kept or reduced the network's complexity, whereas L1, L2, and no-regularization runs consistently increased test |D:H| relative to the analytic optimum, often assigning zero probability to a correct next symbol. The same pattern held when the architecture was fixed and only weights were mutated, and under gradient descent the results drifted away even when training began from the golden weights; MDL itself could not be used in gradient descent because |H| is non-differentiable. The paper reads this as evidence that the objective, not the optimization algorithm, determines whether exact generalization is reached.

Load-bearing premise

The results stand or fall on the hand-built complexity measure |H|: if that measure does not genuinely reflect which networks are simpler, then MDL's advantage over L1 and L2 could be an artifact of the encoding rather than a general property of MDL regularization.

Editorial extensions

If this is right

  • If the MDL objective is the right inductive bias, then L1 and L2 regularization should be expected to fail on any task that requires exact rule induction, regardless of architecture.
  • MDL-selected models are smaller, which should make them easier to analyze and interpret.
  • Because MDL preserves exact solutions even when training starts from one, it can serve as a diagnostic: if an objective drifts away from a known perfect solution, that objective is flawed.
  • The non-differentiability of |H| is the main practical bottleneck; differentiable MDL surrogates or faster evolutionary methods would be needed to scale the approach.
  • The authors propose that the same benefit could extend to Transformers and to natural-language tasks requiring compositional reasoning, though this is not yet tested.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper does not resolve the bit-versus-nat mismatch between |H| and |D:H|; checking the ranking under an explicit bits-per-nat convention would show whether the MDL advantage is robust.
  • The hand-built fractional code may be doing much of the work; testing MDL with a different prefix-free weight code would distinguish a property of MDL from a property of this particular simplicity measure.
  • The golden-network drift test could be reused as a general objective sanity check for any architecture and task with a known correct solution.
  • If the effect transfers to large language models, it would imply that some reasoning failures are not scale or data problems but objective-selection problems.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper proposes using Minimum Description Length (MDL) regularization for neural networks and evaluates it on next-token prediction tasks over six formal languages (anbn, anbncn, Dyck-1, Dyck-2, Arithmetic Syntax, Toy-English). For each task, the authors manually construct a 'golden' RNN whose output distribution exactly matches the true grammar, initialize training from this network, and compare MDL against L1, L2, and no regularization under three settings: genetic architecture search (Experiment 1), GA with fixed architecture and weight-only mutations (Experiment 2), and gradient descent (Experiment 3). The central claim is that MDL preserves or compresses the golden solutions and achieves test cross-entropy closest to the analytically optimal value, while L1/L2/no regularization push networks away from the perfect solution and increase test cross-entropy. The abstract further claims this holds 'independently of the optimization algorithm.'

Significance. If the results hold, this is a valuable contribution: it provides systematic evidence that the choice of regularization can determine whether an expressive network converges to an exact symbolic solution versus a mere approximation, and it offers a concrete MDL implementation for recurrent networks. The paper has several strengths: it uses an unambiguous correctness criterion (matching the full grammar distribution, not just argmax accuracy), exhaustive test sets with analytically computed optimal scores, publicly available code, and a comparison across two optimization paradigms and multiple grammars. However, the central comparison currently rests on an unspecified L1/L2 regularization coefficient for the main genetic-algorithm experiments, the MDL objective adds bits to nats without a stated conversion, and the strong 'independently of the optimization algorithm' claim is not directly tested because MDL is absent from the gradient-descent experiments. These issues are load-bearing for the headline conclusions.

major comments (4)
  1. [Section 2.5, Tables 9 and 11] The L1 and L2 objectives in Section 2.5 contain a regularization coefficient λ, but Table 9 (the GA hyperparameter table) does not specify λ for Experiments 1 and 2; only the gradient-descent configuration in Table 11 states λ=1. The relative strength of L1/L2 versus the cross-entropy term determines whether these regularizers preserve or destroy a golden network: a large λ can collapse weights to zero, while a small λ approximates no regularization. The paper's conclusion that 'standard regularization consistently drifts away from the golden solution' is therefore conditional on an unstated hyperparameter choice. Please report the λ values used for the GA runs and provide a sensitivity analysis over a range of λ to demonstrate that the MDL advantage is not an artifact of over- or under-regularizing the L1/L2 baselines.
  2. [Section 1.1 and Section 2.5] The MDL objective is defined as |H| + |D:H|, where |H| is the encoding length of the network in bits (built from bit strings and a prefix-free scheme) and |D:H| is the cross-entropy of the data, which the paper itself identifies with log surprisal and which is conventionally measured in nats. The manuscript adds these two quantities directly without stating a conversion factor. Because the balance between complexity and data fit determines which networks minimize the objective, the lack of a unit conversion makes the MDL objective an arbitrary weighted sum rather than a well-defined information-theoretic quantity. Please either define |D:H| in bits, multiply |H| by log 2 or an equivalent factor, or otherwise justify the chosen scaling as part of the MDL principle.
  3. [Abstract and Section 3.3] The abstract claims that 'using MDL, perfect solutions are selected over approximations, independently of the optimization algorithm,' but Experiment 3 (gradient descent) explicitly excludes MDL because it is non-differentiable (Section 3.3). The only MDL results come from the genetic algorithm, so the claimed independence from the optimization algorithm is not directly tested. At most, the results show MDL success across two GA variants. Please temper the abstract and discussion to reflect that MDL has not been demonstrated under gradient descent, or add a differentiable approximation of MDL and test it in the GD setting.
  4. [Section 3, Tables 2-4 and Appendix D] All experiments appear to use a single seed (Experiment seed 100, Corpus seed 100 in Tables 9 and 11) and no repeated trials or variance estimates are reported. In several comparisons the differences between MDL and L1/L2 are very small; for example, in Table 3 for anbn the test gaps are MDL 0.1%, L1 0.2%, L2 0.1%, and None 0.2%, differences that could easily arise from run-to-run variability. The claim that MDL 'consistently' outperforms the baselines needs support from multiple independent runs or an explicit justification that the single-run differences exceed expected noise levels.
minor comments (4)
  1. [Section 2.6] The evaluation section states that zero probabilities are smoothed by adding 10^-10, but the definition of |D:H| as the log surprisal does not mention this smoothing. Please state explicitly how smoothing enters the reported scores and whether it is applied uniformly to all models in the comparisons.
  2. [Section 2.4] The golden network for Dyck-1 was found by a GA run under MDL, which introduces some circularity into the claim that MDL preserves perfect solutions. The external test-set evaluation mitigates this, but the manuscript should acknowledge this provenance in the limitations or discussion.
  3. [Appendix D.1 and Appendix E] Table 9 lists 'Number of generations 25,000' but Appendix E states that runs were capped at 25,000 generations or 48 hours, whichever came first, and Table 12 marks several simulations with † for the time limit. The main text and Table 2 should note which results were obtained from time-capped runs, since these may not have converged.
  4. [Tables 2 and 3] The column header 'Optim' appears split across lines in some rows; please format these tables so that column headers are unambiguous. Also, in Table 2 the 'None (Lim.|H|)' rows for Dyck-2, Arithmetic, and Toy-English show very large |H| values, which suggests these runs hit the complexity ceiling; the text should discuss whether the ceiling is a fair comparison point for L1/L2.

Circularity Check

1 steps flagged · score 4.0 of 10

MDL's success is partly self-referential because four of the six golden initializations and the |H| encoding come from the same authors' prior MDL work, but the test-set evaluation against the analytically computed optimum gives the central comparison independent content.

  1. self definitional [Section 2.4 (Golden networks) and Section 2.5 (Regularization methods)]
    "For anbn, anbncn and Dyck-2, we use golden networks previously discovered by Lan et al.[22]. The golden network for Dyck-1 was found in a GA run under MDL. ... Following Lan et al. [22], we calculate the regularization term |H| by encoding the structure of the network: unit count, each unit's type, activation and bias, and the connections (recurrent vs. forward)."

    Four of the six 'golden' networks used to test MDL were themselves produced by the same research group's MDL line of work, and the Dyck-1 golden network was explicitly found in a GA run under MDL. The MDL term |H| that defines the objective is also taken from Lan et al. [22]. Therefore, the observation that MDL tends to preserve or select these networks is partly a statement that the MDL objective retains networks it previously found or was designed to favor. The circularity is not complete: the L1/L2/None comparisons are not mathematically forced to fail, and the test |D:H| is measured against an externally computed grammar-optimal score, so the empirical comparison retains independent content.

full rationale

The paper's central claim is an empirical comparison rather than a derivation, and the evaluation is anchored outside the MDL objective: test cross-entropy is compared to the analytically computed optimal score under the true grammar (Section 2.6). The MDL objective |H|+|D:H| is explicitly just cross-entropy plus a hand-designed encoding-length term, and no parameter of that term is fitted to the reported test results. The strongest circularity concern is that for anbn, anbncn, Dyck-2, and Dyck-1 the golden initializations and the |H| encoding originate from the authors' own prior MDL work, so the 'MDL preserves perfect solutions' result is partly re-encountering the objective that produced those solutions. However, L1, L2, and unregularized search could in principle have preserved the same networks, and the analytic test-score benchmark is independent, so the main L1/L2 failures are not forced by construction. The claim that MDL works 'independently of the optimization algorithm' is not fully supported because MDL is only used with the genetic algorithm and is excluded from gradient descent, but that is an evidential gap rather than circularity. Likewise, the unspecified L1/L2 coefficient λ in the GA experiments (λ=1 is given only for the backpropagation setup in Appendix D.3) is a hyperparameter-reporting concern, not a circular step. On balance, there is meaningful self-citation in the load-bearing experimental setup, but the core result retains independent empirical content.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The paper's claims rest on the hand-designed MDL encoding, the correctness of the golden networks, and the representativeness of the test sets. The main free parameters are the L1/L2 coefficient lambda (reported only for GD) and the complexity ceiling for the 'no regularization' baseline. No new physical or mathematical entities are introduced.

free parameters (3)
  • L1/L2 regularization coefficient lambda = 1 for gradient descent; unspecified for genetic algorithm experiments
    The strength of L1 and L2 penalties relative to cross-entropy affects how much they perturb the golden network, and the paper does not report lambda for the GA runs.
  • Complexity ceiling for 'None (Lim|H|)' baseline = 3 times the golden network's |H|
    The no-regularization baseline actually includes a hand-chosen complexity cap, which is not a standard training setup and affects the comparison.
  • Unit conversion between |H| and |D:H| in the MDL objective = Not specified; |H| is described in bits, |D:H| as log-surprisal (likely nats)
    Adding a bit-length complexity term directly to a nat-valued cross-entropy loss introduces an arbitrary relative weighting; the paper does not discuss this.
assumptions (5)
  • domain assumption The golden networks exactly match the true grammar distribution for their tasks.
    Required for the claim that training starts from a perfect solution; golden networks were manually constructed or taken from prior MDL work and 'empirically verified' (Section 2.4) rather than formally proven.
  • domain assumption Network complexity is measured by the prefix-free encoding length of weights as signed fractions, and the MDL objective is |H| + |D:H|.
    This definition of simplicity is a design choice; the results depend on it (Section 2.5).
  • standard math Shannon-Fano coding makes |D:H| equivalent to the cross-entropy loss.
    Standard information-theoretic identity, but assumes an appropriate coding scheme for the data (Section 1.1).
  • domain assumption The exhaustive test sets are representative of the full grammar distribution.
    Test sets enumerate strings up to a length threshold; low-probability long strings are excluded (Section 2.6).
  • standard math The free-form RNN is at least as expressive as ReLU RNNs.
    Based on a cited formal result [11]; needed so that the golden networks' expressivity is credible (Section 2.2).

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Minimum Description Length Approach to Regularization in Neural Networks." pith.science (2026). https://pith.science/paper/UILYYBCZ

@misc{pith2026250513398,
  author       = {Pith},
  title        = {Pith review of: A Minimum Description Length Approach to Regularization in Neural Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UILYYBCZ}},
  note         = {Machine review of arXiv:2505.13398}
}
abstract

State-of-the-art neural networks can be trained to become remarkable solutions to many problems. But while these architectures can express symbolic, perfect solutions, trained models often arrive at approximations instead. We show that the choice of regularization method plays a crucial role: when trained on formal languages with standard regularization ($L_1$, $L_2$, or none), expressive architectures not only fail to converge to correct solutions but are actively pushed away from perfect initializations. In contrast, applying the Minimum Description Length (MDL) principle to balance model complexity with data fit provides a theoretically grounded regularization method. Using MDL, perfect solutions are selected over approximations, independently of the optimization algorithm. We propose that unlike existing regularization techniques, MDL introduces the appropriate inductive bias to effectively counteract overfitting and promote generalization.

Figures

Figures reproduced from arXiv: 2505.13398 by the authors.

Figure 1
Figure 1. Method overview. We compare the relative benefit of different regularization methods with the same pipeline (A) across training regimes (B). 2.1 Overview We define a battery of next-token prediction tasks based on formal languages, each represented by a probabilistic grammar. For each task, we manually construct a “golden” RNN that perfectly solves it by matching the true data distribution. Initializing the learning… view at source ↗
Figure 2
Figure 2. Relative deviation (∆%) from optimal |D : H| for each final network in Experiment 1, on train (x-axis) and test (y-axis), grouped by task. Proximity to center indicates better approximation of the analytical optimum. 3.3 Experiment 3: Gradient descent One might object that the optimization algorithm plays an important role in promoting generalization, and propose that unlike GA, GD allows standard regularization to … view at source ↗
Figure 3
Figure 3. Golden network for the a nb n task. # 0 Linear + 4 Linear + 15.00 a 1 Linear + 6 Relu + 2.00 b 2 Linear + -15.00 P(#) 3 Linear + P(a) P(b) 5 Linear + -15.00 1.00 6.00 -0.86 -1.00 [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figures from the paper (10 more)
Figure 4
Figure 4. Figure 4: Differentiable golden network for the a nb n task, used in Experiment 3. 14 [PITH_FULL_IMAGE:figures/full_fig_p014_4.png]
Figure 5
Figure 5. Figure 5: Golden network for the a nb nc n task. # 0 Linear + 5 Linear + 15.00 8 Linear + 1.00 a 1 Linear + -2.00 b 2 Linear + -15.00 1.00 c 3 Linear + 1.00 P(#) 4 Linear + P(a) P(b) 6 Sigmoid + P(c) 7 Linear + 31.00 1.00 9 Tanh + 2.00 15.00 10 Linear + -1.00 1.00 1.33 -1.00 [P…
Figure 6
Figure 6. Figure 6: Differentiable golden network for the a nb nc n task, used in Experiment 3. 15 [PITH_FULL_IMAGE:figures/full_fig_p015_6.png]
Figure 7
Figure 7. Figure 7: Golden network for the Dyck-1 task. # 0 Linear + [ 1 Linear + 6 Linear + -1.00 ] 2 Linear + 1.00 P(#) 3 Linear + P([) 4 Tanh + P(]) 5 Linear + 7.00 1.00 7 Relu + 1.00 -7.00 -0.75 1.00 [PITH_FULL_IMAGE:figures/full_fig_p016_7.png]
Figure 8
Figure 8. Figure 8: Differentiable golden network for the Dyck-1 task, used in Experiment 3. [PITH_FULL_IMAGE:figures/full_fig_p016_8.png]
Figure 9
Figure 9. Figure 9: Golden network for the Dyck-2 task. # 0 Linear + 6 Linear + 1.00 ( 1 Linear + 0.33 9 Linear + 0.67 10 Linear x 1.00 11 Linear + 1.00 16 Step + 1.00 ) 2 Linear + 12 Linear x 1.00 19 Step + 1.00 21 Step + 1.00 26 Step + 1.00 + 3 Linear + 0.33 0.67 23 Step + 1.00 1 4 Line…
Figure 10
Figure 10. Figure 10: Golden network for the Arithmetic task. 17 [PITH_FULL_IMAGE:figures/full_fig_p017_10.png]
Figure 11
Figure 11. Figure 11: Golden network for the Toy-English task. [PITH_FULL_IMAGE:figures/full_fig_p018_11.png]
Figure 12
Figure 12. Figure 12: Relative deviation (∆%) from optimal |D : H| for each final network in Experiment 2, on train (x-axis) and test (y-axis), grouped by task. Proximity to center indicates better approximation of the analytical optimum [PITH_FULL_IMAGE:figures/full_fig_p020_12.png]
Figure 13
Figure 13. Figure 13: Relative deviation (∆%) from optimal |D : H| for each final network in Experiment 3, on train (x-axis) and test (y-axis), grouped by task. Proximity to center indicates better approximation of the analytical optimum. G Full results 20 [PITH_FULL_IMAGE:figures/full_fi…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

50 extracted references · 34 canonical work pages

  1. [1]

    Minimum Description Length Hopfield Networks

    Matan Abudy, Nur Lan, Emmanuel Chemla, and Roni Katzir. Minimum description length Hopfield networks.arXiv preprint arXiv:2311.06518, 2023. Presented at the Associative Memory & Hopfield Networks Workshop at NeurIPS 2023

    work page Pith review arXiv 2023

  2. [2]

    Review of parallel genetic algorithms bibliography.Technical Report, 1994

    Panagiotis Adamidis. Review of parallel genetic algorithms bibliography.Technical Report, 1994

    work page 1994

  3. [3]

    A systematic analysis of large language models as soft reasoners: The case of syllogistic inferences.arXiv preprint arXiv:2406.11341, 2024

    Leonardo Bertolazzi, Albert Gatt, and Raffaella Bernardi. A systematic analysis of large language models as soft reasoners: The case of syllogistic inferences.arXiv preprint arXiv:2406.11341, 2024

    arXiv 2024

  4. [4]

    PhD thesis, Massachusetts Inst

    Robert Cregar Berwick.Locality principles and the aquisition of syntactic knowledge. PhD thesis, Massachusetts Inst. of Technology Cambridge, 1982

    work page 1982

  5. [5]

    Language models are few-shot learners.Advances in neural information processing systems, 33:1877–1901, 2020

    Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners.Advances in neural information processing systems, 33:1877–1901, 2020

    1901

  6. [6]

    A survey of parallel genetic algorithms.Calculateurs paralleles, reseaux et systems repartis, 10(2):141–171, 1998

    Erick Cantú-Paz et al. A survey of parallel genetic algorithms.Calculateurs paralleles, reseaux et systems repartis, 10(2):141–171, 1998

    work page 1998

  7. [7]

    Neural networks generalize on low complexity data

    Sourav Chatterjee and Timothy Sudijono. Neural networks generalize on low complexity data. arXiv preprint arXiv:2409.12446, 2024

    arXiv 2024

  8. [8]

    On the implicit bias of gradient descent for temporal extrapolation

    Edo Cohen-Karlik, Avichai Ben David, Nadav Cohen, and Amir Globerson. On the implicit bias of gradient descent for temporal extrapolation. InInternational Conference on Artificial Intelligence and Statistics, pages 10966–10981. PMLR, 2022

    work page 2022

Show all 50 references
  1. [9]

    Unsupervised language acquisition.arXiv preprint cmp-lg/9611002, 1996

    Carl De Marcken. Unsupervised language acquisition.arXiv preprint cmp-lg/9611002, 1996

    1996 arXiv

  2. [10]

    Faith and fate: Limits of transformers on compositionality.Advances in Neural Information Processing Systems, 36: 70293–70332, 2023

    Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, et al. Faith and fate: Limits of transformers on compositionality.Advances in Neural Information Processing Systems, 36: 70293–...

    2023

  3. [11]

    Formal and empirical studies of counting behaviour in relu rnns

    Nadine El-Naggar, Andrew Ryzhikov, Laure Daviaud, Pranava Madhyastha, and Tillman Weyde. Formal and empirical studies of counting behaviour in relu rnns. InInternational Conference on Grammatical Inference, pages 199–222. PMLR, 2023

    2023

  4. [12]

    Language models do hard arith- metic tasks easily and hardly do easy arithmetic tasks.arXiv preprint arXiv:2406.02356, 2024

    Andrew Gambardella, Yusuke Iwasawa, and Yutaka Matsuo. Language models do hard arith- metic tasks easily and hardly do easy arithmetic tasks.arXiv preprint arXiv:2406.02356, 2024

    2024 arXiv

  5. [13]

    Serial and parallel genetic algorithms as function optimiz- ers

    V Scott Gordon and Darrell Whitley. Serial and parallel genetic algorithms as function optimiz- ers. InICGA, pages 177–183, 1993

    1993

  6. [14]

    Inductive biases for deep learning of higher-level cognition

    Anirudh Goyal and Yoshua Bengio. Inductive biases for deep learning of higher-level cognition. Proceedings of the Royal Society A, 478(2266):20210068, 2022

    2022

  7. [15]

    A minimum description length approach to grammar inference

    Peter Grünwald. A minimum description length approach to grammar inference. InInternational joint conference on artificial intelligence, pages 203–216. Springer, 1995

    1995

  8. [16]

    Testing the limits of logical reasoning in neural and hybrid models

    Manuel Guzman, Jakub Szymanik, and Maciej Malicki. Testing the limits of logical reasoning in neural and hybrid models. InFindings of the Association for Computational Linguistics: NAACL 2024, pages 2267–2279, 2024. 10

    2024

  9. [17]

    Keeping the neural networks simple by minimizing the description length of the weights

    Geoffrey E Hinton and Drew Van Camp. Keeping the neural networks simple by minimizing the description length of the weights. InProceedings of the sixth annual conference on Computational learning theory, pages 5–13, 1993

    1993

  10. [18]

    MIT press, 1992

    John H Holland.Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press, 1992

    1992

  11. [19]

    Stanford University, 1969

    James Jay Horning.A study of grammatical inference. Stanford University, 1969

    1969

  12. [20]

    Inductionbench: Llms fail in the simplest complexity class.arXiv preprint arXiv:2502.15823, 2025

    Wenyue Hua, Tyler Wong, Sun Fei, Liangming Pan, Adam Jardine, and William Yang Wang. Inductionbench: Llms fail in the simplest complexity class.arXiv preprint arXiv:2502.15823, 2025

    2025 arXiv

  13. [21]

    macmillan, 2011

    Daniel Kahneman.Thinking, fast and slow. macmillan, 2011

    2011

  14. [22]

    Minimum description length recurrent neural networks.Transactions of the Association for Computational Linguistics, 10: 785–799, 2022

    Nur Lan, Michal Geyer, Emmanuel Chemla, and Roni Katzir. Minimum description length recurrent neural networks.Transactions of the Association for Computational Linguistics, 10: 785–799, 2022

    2022

  15. [23]

    Benchmarking neural network generalization for grammar induction

    Nur Lan, Emmanuel Chemla, and Roni Katzir. Benchmarking neural network generalization for grammar induction. InProceedings of the 2023 CLASP Conference on Learning with Small Data (LSD), pages 131–140, 2023

    2023

  16. [24]

    Bridging the empirical-theoretical gap in neural network formal language learning using minimum description length.arXiv preprint arXiv:2402.10013, 2024

    Nur Lan, Emmanuel Chemla, and Roni Katzir. Bridging the empirical-theoretical gap in neural network formal language learning using minimum description length.arXiv preprint arXiv:2402.10013, 2024

    2024 arXiv

  17. [25]

    Springer, 2008

    Ming Li and Paul Vitányi.An introduction to Kolmogorov complexity and its applications, volume 3. Springer, 2008

    2008

  18. [26]

    Deep neural networks have an inbuilt occam’s razor.Nature Communications, 16(1):220, 2025

    Chris Mingard, Henry Rees, Guillermo Valle-Pérez, and Ard A Louis. Deep neural networks have an inbuilt occam’s razor.Nature Communications, 16(1):220, 2025

    2025

  19. [27]

    Gsm-symbolic: Understanding the limitations of mathematical reasoning in large language models.arXiv preprint arXiv:2410.05229, 2024

    Iman Mirzadeh, Keivan Alizadeh, Hooman Shahrokhi, Oncel Tuzel, Samy Bengio, and Mehrdad Farajtabar. Gsm-symbolic: Understanding the limitations of mathematical reasoning in large language models.arXiv preprint arXiv:2410.05229, 2024

    arXiv

  20. [28]

    Alice in wonderland: Simple tasks showing complete reasoning breakdown in state-of-the-art large language models

    Marianna Nezhurina, Lucia Cipolina-Kun, Mehdi Cherti, and Jenia Jitsev. Alice in wonderland: Simple tasks showing complete reasoning breakdown in state-of-the-art large language models. arXiv preprint arXiv:2406.02061, 2024

    2024 arXiv

  21. [29]

    Arithmetic without algo- rithms: Language models solve math with a bag of heuristics.arXiv preprint arXiv:2410.21272, 2024

    Yaniv Nikankin, Anja Reusch, Aaron Mueller, and Yonatan Belinkov. Arithmetic without algo- rithms: Language models solve math with a bag of heuristics.arXiv preprint arXiv:2410.21272, 2024

    2024 arXiv

  22. [30]

    Bayesian learning of visual chunks by human observers.Proceedings of the National Academy of Sciences, 105(7):2745– 2750, 2008

    Gerg˝o Orbán, József Fiser, Richard N Aslin, and Máté Lengyel. Bayesian learning of visual chunks by human observers.Proceedings of the National Academy of Sciences, 105(7):2745– 2750, 2008

    2008

  23. [31]

    On evaluation metrics in optimality theory.Linguistic Inquiry, 47 (2):235–282, 2016

    Ezer Rasin and Roni Katzir. On evaluation metrics in optimality theory.Linguistic Inquiry, 47 (2):235–282, 2016

    2016

  24. [32]

    Approaching explanatory adequacy in phonology using minimum description length.Journal of Language Modelling, 9 (1):17–66, 2021

    Ezer Rasin, Iddo Berger, Nur Lan, Itamar Shefi, and Roni Katzir. Approaching explanatory adequacy in phonology using minimum description length.Journal of Language Modelling, 9 (1):17–66, 2021

    2021

  25. [33]

    Modeling by shortest data description.Automatica, 14(5):465–471, 1978

    Jorma Rissanen. Modeling by shortest data description.Automatica, 14(5):465–471, 1978

    1978

  26. [34]

    Discovering neural nets with low kolmogorov complexity and high generalization capability.Neural Networks, 10(5):857–873, 1997

    Jürgen Schmidhuber. Discovering neural nets with low kolmogorov complexity and high generalization capability.Neural Networks, 10(5):857–873, 1997

    1997

  27. [35]

    PhD thesis, Massachusetts Institute of Technology, 2009

    Lauren A Schmidt.Meaning and compositionality as statistical induction of categories and constraints. PhD thesis, Massachusetts Institute of Technology, 2009. 11

    2009

  28. [36]

    A mathematical theory of communication.The Bell system technical journal, 27(3):379–423, 1948

    Claude E Shannon. A mathematical theory of communication.The Bell system technical journal, 27(3):379–423, 1948

    1948

  29. [37]

    On the computational power of neural nets

    Hava T Siegelmann and Eduardo D Sontag. On the computational power of neural nets. In Proceedings of the fifth annual workshop on Computational learning theory, pages 440–449, 1992

    1992

  30. [38]

    A formal theory of inductive inference

    Ray J Solomonoff. A formal theory of inductive inference. part i and ii.Information and control, 7(1):1–22, 1964

    1964

  31. [39]

    A provably stable neural network turing machine with finite precision and time.Information Sciences, 658:120034, 2024

    John Stogin, Ankur Mali, and C Lee Giles. A provably stable neural network turing machine with finite precision and time.Information Sciences, 658:120034, 2024

    2024

  32. [40]

    University of California, Berkeley, 1994

    Andreas Stolcke.Bayesian learning of probabilistic language models. University of California, Berkeley, 1994

    1994

  33. [41]

    How to grow a mind: Statistics, structure, and abstraction.science, 331(6022):1279–1285, 2011

    Joshua B Tenenbaum, Charles Kemp, Thomas L Griffiths, and Noah D Goodman. How to grow a mind: Statistics, structure, and abstraction.science, 331(6022):1279–1285, 2011

    2011

  34. [42]

    Evaluating the world model implicit in a generative model.Advances in Neural Information Processing Systems, 37:26941–26975, 2025

    Keyon Vafa, Justin Chen, Ashesh Rambachan, Jon Kleinberg, and Sendhil Mullainathan. Evaluating the world model implicit in a generative model.Advances in Neural Information Processing Systems, 37:26941–26975, 2025

    2025

  35. [43]

    Large language models still can’t plan (a benchmark for llms on planning and reasoning about change)

    Karthik Valmeekam, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati. Large language models still can’t plan (a benchmark for llms on planning and reasoning about change). InNeurIPS 2022 Foundation Models for Decision Making Workshop, 2022

    2022

  36. [44]

    Thinking like transformers

    Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers. InInternational Conference on Machine Learning, pages 11080–11090. PMLR, 2021

    2021

  37. [45]

    Reasoning or reciting? exploring the capabilities and limitations of language models through counterfactual tasks

    Zhaofeng Wu, Linlu Qiu, Alexis Ross, Ekin Akyürek, Boyuan Chen, Bailin Wang, Najoung Kim, Jacob Andreas, and Yoon Kim. Reasoning or reciting? exploring the capabilities and limitations of language models through counterfactual tasks. InProceedings of the 2024 Conference of the...

    2024

  38. [46]

    Word learning as bayesian inference.Psychological review, 114(2):245, 2007

    Fei Xu and Joshua B Tenenbaum. Word learning as bayesian inference.Psychological review, 114(2):245, 2007

    2007

  39. [47]

    When can transformers count to n?arXiv preprint arXiv:2407.15160, 2024

    Gilad Yehudai, Haim Kaplan, Asma Ghandeharioun, Mor Geva, and Amir Globerson. When can transformers count to n?arXiv preprint arXiv:2407.15160, 2024

    2024

  40. [48]

    Balancing accuracy and parsimony in genetic programming.Evolutionary Computation, 3(1):17–38, 1995

    Byoung-Tak Zhang and Heinz Mühlenbein. Balancing accuracy and parsimony in genetic programming.Evolutionary Computation, 3(1):17–38, 1995

    1995

  41. [49]

    Evolving optimal neural networks using genetic algorithms with occam’s razor.Complex systems, 7(3):199–220, 1993

    Byoung-Tak Zhang, Heinz Muhlenbein, et al. Evolving optimal neural networks using genetic algorithms with occam’s razor.Complex systems, 7(3):199–220, 1993

    1993

  42. [50]

    On the paradox of learning to reason from data.arXiv preprint arXiv:2205.11502, 2022

    Honghua Zhang, Liunian Harold Li, Tao Meng, Kai-Wei Chang, and Guy Van den Broeck. On the paradox of learning to reason from data.arXiv preprint arXiv:2205.11502, 2022. A Task-specific probabilistic grammars We generate training strings using probabilistic grammars, most of th...

    2022 arXiv

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.