Pith. sign in

REVIEW 4 major objections 4 minor 28 references

MADIL: An MDL-based Framework for Efficient Program Synthesis in the ARC Benchmark

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

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

Pith's one-line read MADIL claims MDL-based pattern decomposition enables efficient, interpretable program synthesis on ARC, solving 57 of 400 public evaluation tasks with 82% generalization on found solutions.

desk verdict An honest, well-documented MDL-based program synthesis system for ARC with modest results; the 14%-to-7% public-to-private gap means the headline generalization claim needs more careful support. read the letter →

arxiv 2505.01081 v1 pith:7AO7GCCK submitted 2025-05-02 cs.AI

Sébastien Ferré This is my paper · ORCID
classification cs.AI
keywords AbstractionandReasoningCorpusARC-AGIMinimumDescriptionLengthprogramsynthesispattern-baseddecompositioninductivelearningMonteCarloTreeSearchinterpretableAI
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 is trying to establish that a general inductive learner for the Abstraction and Reasoning Corpus (ARC) can be built on the Minimum Description Length principle, without large pretraining corpora or test-time fine-tuning. It claims that decomposing each grid into parts through reversible patterns, then composing the output from those parts, lets MDL compression guide the search so deeply that solutions of size up to 46 emerge in under a minute on a single CPU. If that claim is right, it matters because it offers a frugal and interpretable alternative to LLM-based ARC systems, and because the same decomposition framework is reusable for other input–output domains. The reported evidence is that MADIL solves 57 of 400 public evaluation tasks with an 82% generalization rate among found solutions, and scores 7% on ArcPrize 2024's private set.

What carries the argument

The load-bearing object is the description: a recursive decomposition of a value by patterns such as BgColor, Monocolor, Motif, or Metagrid, where each pattern runs both from whole to parts and from parts to whole. Around descriptions sits a two-part MDL objective, normalized to give equal weight to input and output, with a rehearsal factor $\alpha$ that weights data against model complexity. Pattern transitions are pruned by a consistency property (Theorem 2: an inconsistent model cannot become consistent through minimal refinement), and search alternates greedy rollout with MCTS. The MDL ranking is what makes the search narrow and deep; it also determines which of several parses of an example is used for learning, and candidate expressions are retrieved by value from a DAG built over the environment.

What would settle it

Take the 69 public evaluation tasks for which MADIL finds a solution and rerun the search with the MDL transition ranking replaced by a random ordering that still respects consistency pruning; if the same solutions keep appearing, then compression is not doing the steering work the paper attributes to it.

Watch

Extended reading notes

Core claim

On this paper's own terms, the discovery is that the Minimum Description Length principle can carry inductive program synthesis on ARC: rather than enumerating transformation sequences, MADIL learns a pair of descriptive models—one decomposes each input grid into parts, the other composes the output grid from those parts—and the search is steered by description length. The resulting system finds a solution for 69 of 400 public evaluation tasks, 57 of which generalize to all test examples (82% of found solutions), and reaches 7% on the private ArcPrize 2024 set. Most solutions are found on the first greedy rollout, with average search depth between 11 and 17, and 80% of solutions appear within 20 seconds on a single CPU.

Load-bearing premise

The argument rests on the assumption that the hand-coded set of patterns and functions, plus the hand-set description-length distributions, is rich enough and correctly ordered for a meaningful share of ARC tasks.

Editorial extensions

If this is right

  • If MDL correctly steers the search, adding more patterns and functions should scale better than brute-force DSL search, because the deepest successful models found here reach size 46 whereas brute-force methods are typically bounded to depth 3–4.
  • On the 69 solved evaluation tasks, 54 solutions come from the first greedy rollout, so greedy MDL search is usually enough and MCTS is a recovery mechanism rather than the main driver.
  • The 82% generalization rate among 57 solved tasks implies that a description-length-minimal model found on training examples is, in the majority of cases, also correct on held-out test examples.
  • Because most predictions are correct on the first attempt (53 of 57 solved tasks), the method is usable under strict attempt budgets.
  • The method finds 16 public evaluation tasks that an earlier layer-stacking approach does not solve, so its decomposition mechanism is at least partly complementary to established DSL search.

Reading between the lines

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

  • Beyond the paper: if compression-guided search is what explains the results, the same pattern-decomposition machinery should transfer to other input–output domains once value distributions and patterns are supplied; the paper already points to string-to-string transformations.
  • The paper's list of missing primitives suggests a testable extension: adding conditionals and recursion in a controlled way, or learning primitives from solved tasks, is the natural next lever, and whether MDL still guides search when such constructs enter is an open question.
  • Observed performance supports a broader conjecture: descriptive compressibility of training examples is a useful proxy for out-of-sample correctness in ARC-like tasks; one could test this by comparing MDL model rank against held-out accuracy across many tasks.
  • If the efficiency claim scales, practical program-synthesis tools may favour MDL-guided narrow search over large generate-and-test loops, since most solutions here are found on the first greedy path.
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 introduces MADIL, a program-synthesis framework for the ARC benchmark that is based on two-part MDL. A task model is a pair of recursive pattern-decomposition models: the input model decomposes an input grid, and the output model composes the output grid from input variables through expressions and functions. Search starts from a maximally unspecific model and refines it by minimal transitions that replace an unknown with a pattern or an expression, with consistency pruning based on a proven anti-monotonicity result and guidance by description length. The implementation adds sampling, top-K selection, greedy search and MCTS, a rehearsal factor, and normalized description lengths. Experiments report 57/400 public evaluation tasks solved with an 82% generalization rate among found solutions, 7% on the private ArcPrize 2024 set, and high search efficiency (average rank 1.6 of the best found model, and 80% of solutions found within the first 20 seconds). The paper also provides a parameter study and a detailed failure analysis.

Significance. If the claims are supported, MADIL is a useful low-resource and interpretable program-synthesis baseline for ARC: it shows that a carefully chosen pattern language combined with compression-guided search can solve nontrivial ARC tasks without LLM pretraining, with transparent models and an open-source implementation. The formal framework of decomposable pattern models, the consistency/pruning theorem, and the detailed ablation study are valuable contributions. The paper is also honest about its limitations, especially in Section 8.4. However, the significance is contingent on the robustness of the public-set evaluation and on the degree to which the implemented objective is actually MDL rather than a manually tuned heuristic; these issues need to be addressed before the central claims can be fully accepted.

major comments (4)
  1. [§8.1, Table 6] The paper treats the 400 public evaluation tasks as a robust evaluation set, but it reports only point estimates: 57/400 tasks (14.25%) on the public evaluation set and 7/100 (7%) on the private ArcPrize set. No confidence intervals, standard errors, or random splits are provided. The gap between the two rates is large enough that the public-set estimate cannot be assumed to be a stable measure of generalization to unseen tasks, especially because the public tasks are a fixed, publicly known collection rather than a random sample. Please add confidence intervals, a repeated random-split analysis of the public tasks, and a discussion of why the private-set rate is lower.
  2. [§8.3] The parameter and ablation study is performed on the 71 evaluation tasks that are 'satisfactorily solved in any MADIL version from v3.2 to v3.6.' This set is selected after observing the outcomes, which biases the robustness claims: for example, the conclusion that using only the most promising transition (Kt = 1) loses only 3 tasks is conditional on a subset that may be enriched for easy or solvable tasks. The same ablations should be reported on the full 400-task evaluation set or on a pre-specified random subset, with the number of affected tasks and exact task IDs rather than proportions only.
  3. [§6.4 and §7.3] The optimized objective is not the two-part MDL criterion L(M) + L(E|M) defined earlier. The rehearsal factor α = 100 changes the trade-off between model complexity and data fit, and the normalized DL L̂(M,E) replaces L(M,E) in the greedy search and in the MCTS value function. Since the paper's central claim is that MDL-based compression is what makes the search efficient, these modifications need to be justified as approximations that preserve the model-ordering properties of the true MDL score, or their role needs to be empirically isolated. The current ablation for α is reported only on the selected 71-task subset, which is not sufficient to establish that the method is robust to this free parameter.
  4. [§5.2.2, Equations (1)-(4)] The model-counting definitions are not a complete coding scheme as written. In Equation (3), #E(1,V) = 2 treats 'constant value' and 'variable' as two syntactic token types even though the sets of constants and variables are infinite, so the formulas count syntactic skeletons rather than models. It is then not shown that the total description length L(M), obtained by adding skeleton counts, constant encodings, and variable encodings, satisfies the Kraft inequality or is otherwise a valid prefix code. This matters because the MDL scores that guide the search are derived from these counts. Please state precisely what is counted (token categories versus concrete values) and prove or verify that the resulting L(M) is a valid description length.
minor comments (4)
  1. [§8.1] Please reconcile the counts reported in this section: the text says 57 tasks are correct on all test examples, then later says MADIL is correct on 59 evaluation tasks when all test outputs must be correctly predicted, and also mentions two tasks with correct predictions where the model is correct on one training example out of two. The relation between these counts and the micro-accuracy scoring with two attempts should be stated explicitly.
  2. [§8.3 and Table 3] The default value of the maximum expression size Se is listed as 6 in Table 3, but the parameter study compares 'Se = 5 (vs 9)' and discusses Se = 1 as a reduction. Please clarify which default value was actually used in the experiments and make Table 3 consistent.
  3. [§6.4 and §7.3] There are several typos, including 'pragmactic' in Section 6.4, 'exprression' in the proof of Theorem 1, and 'loosing' in Section 8.3; these should be corrected.
  4. [§1 and §3] The introduction states that MADIL has been 'successfully applied' to string-to-string transformation tasks such as FlashFill, but no experiments or results for such tasks are reported. Either provide supporting evidence or temper the claim to say that the framework is intended to be applicable to such domains.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: held-out evaluation and self-contained formalization support the central claims.

full rationale

MADIL's derivation chain is self-contained. Task models, patterns, functions, and description lengths are formally defined in Sections 5.1-5.2, and the parsing, generation, prediction, and search algorithms in Section 6 operate on the training examples of a task. The MDL objective L(M,E) is constructed from explicit value/pattern/function distributions and is not defined in terms of test outputs or private-set scores. Predictions are produced by choosing the most compressive description compatible with a test input and are then independently scored against held-out ARC tasks in Section 8, so the reported results (57/400 evaluation tasks, 7% private) are external evidence rather than consequences of the objective by construction. The author's prior MADIL papers [9,10] are cited as background and are not load-bearing: the paper itself provides the formal definitions, algorithms, and experiments. The parameter study in Section 8.3 selects '71 evaluation tasks that are satisfactorily solved in any MADIL version from v3.2 to v3.6' (footnote 10), which is a post-hoc selection that limits the strength of robustness claims, but this is an evaluation-design concern, not circularity. No fitted parameter is renamed as a prediction, no equation reduces to its own input, and no self-citation is used to forbid alternative explanations. The hand-coded primitives are an acknowledged prior and are not derived from the target outputs. Therefore the paper does not exhibit circular reasoning.

Assumptions & free parameters 7 free parameters · 6 assumptions · 0 invented entities

The central claim rests on hand-designed value distributions, a hand-crafted DSL, and several ad hoc parameters. No new physical or mathematical entities are introduced.

free parameters (7)
  • Rehearsal factor alpha = 100
    Gives more weight to data in the MDL objective, chosen by hand to balance search depth and overfitting (Section 6.4).
  • Sampling parameters Np, Kp, Ng, Kg = 100, 3, 3, 3
    Control the number of parsed and generated descriptions, affecting search completeness and cost (Section 6.1).
  • Expression size limit Se = 6
    Limits the complexity of expressions considered in transitions, trading expressiveness for tractability (Section 6.2).
  • Number of expression candidates Ne = 1000
    Limits the finite collection of expressions evaluated, affecting search coverage (Section 6.2).
  • Number of transitions Kt = 100
    Limits the number of candidate transitions evaluated per step, controlling efficiency (Section 6.3).
  • Attempts K = 3
    Number of allowed prediction attempts per test input, set by benchmark rules (Section 6.3).
  • Decomposition wrapping depth Sd = 1
    Controls how often pure decomposition patterns wrap transitions, improving exposure of parts (Section 6.4).
assumptions (6)
  • domain assumption Working assumption: there exists a program mapping all inputs to their output (Definition 13).
    This is a standard assumption in program synthesis and is stated explicitly in the task definition.
  • domain assumption The value distributions V_i and V_o are given a priori (Section 5.2).
    For ARC, these are uniform over 10-color grids up to 30x30, which is provided by the benchmark.
  • ad hoc to paper Uniform distribution over models of the same size (Section 5.2.2).
    The description length of model syntax assumes a uniform prior over models of a given size, which is an arbitrary but common choice in MDL.
  • domain assumption The MDL principle is a reliable guide for generalization in program synthesis (Section 5.2).
    This is a foundational assumption of the paper, based on information theory and prior MDL literature.
  • domain assumption The hand-crafted pattern and function library is sufficient to express a useful subset of ARC tasks (Section 4, 5).
    The paper acknowledges in Section 8.4 that many primitives are missing, but the central evaluation depends on this library.
  • ad hoc to paper The rehearsal factor alpha and normalized DL are appropriate for ARC (Section 6.4).
    These modifications to the MDL objective are introduced to address specific difficulties in ARC and are not derived from first principles.

how reviews work

0 comments
Cite this review

Pith. "Pith review of MADIL: An MDL-based Framework for Efficient Program Synthesis in the ARC Benchmark." pith.science (2026). https://pith.science/paper/7AO7GCCK

@misc{pith2026250501081,
  author       = {Pith},
  title        = {Pith review of: MADIL: An MDL-based Framework for Efficient Program Synthesis in the ARC Benchmark},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7AO7GCCK}},
  note         = {Machine review of arXiv:2505.01081}
}
read the original abstract

Artificial Intelligence (AI) has achieved remarkable success in specialized tasks but struggles with efficient skill acquisition and generalization. The Abstraction and Reasoning Corpus (ARC) benchmark evaluates intelligence based on minimal training requirements. While Large Language Models (LLMs) have recently improved ARC performance, they rely on extensive pre-training and high computational costs. We introduce MADIL (MDL-based AI), a novel approach leveraging the Minimum Description Length (MDL) principle for efficient inductive learning. MADIL performs pattern-based decomposition, enabling structured generalization. While its performance (7% at ArcPrize 2024) remains below LLM-based methods, it offers greater efficiency and interpretability. This paper details MADIL's methodology, its application to ARC, and experimental evaluations.

Figures

Figures reproduced from arXiv: 2505.01081 by the authors.

Figure 1
Figure 1. Task 1caeab9d (inputs at the top, outputs at the bottom, test on the right) [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Task 47c1f68c (inputs at the top, outputs at the bottom, test on the right) [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Solution with a sequence of transformations. [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Solution with a decomposition/composition of the grids (solid lines), and map [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]
Figure 5
Figure 5. Figure 5: A MADIL program that is a solution to the running task. [PITH_FULL_IMAGE:figures/full_fig_p011_5.png]
Figure 6
Figure 6. Figure 6: Task 9f236235 (inputs at the top, outputs at the bottom, test on the right) [PITH_FULL_IMAGE:figures/full_fig_p038_6.png]
Figure 7
Figure 7. Figure 7: Distribution of model sizes: all evaluation tasks (left), and correct solutions only [PITH_FULL_IMAGE:figures/full_fig_p044_7.png]
Figure 8
Figure 8. Figure 8: Percentage of solved tasks under a given runtime. [PITH_FULL_IMAGE:figures/full_fig_p046_8.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 23 canonical work pages

  1. [1]

    Krizhevsky, I

    A. Krizhevsky, I. Sutskever, G. E. Hinton, Imagenet classification with deep convolutional neural networks, Advances in neural information pro- cessing systems 25 (2012) 1097–1105

    work page 2012

  2. [2]

    Silver, A

    D. Silver, A. Huang, C. J. Maddison, et al., Mastering the game of Go with deep neural networks and tree search, Nature 529 (7587) (2016) 484–489

    work page 2016

  3. [3]

    Goertzel, Artificial general intelligence: concept, state of the art, and future prospects, Journal of Artificial General Intelligence 5 (1) (2014)

    B. Goertzel, Artificial general intelligence: concept, state of the art, and future prospects, Journal of Artificial General Intelligence 5 (1) (2014)

    work page 2014

  4. [4]

    Chollet, A definition of intelligence for the real world, Journal of Artificial General Intelligence 11 (2) (2020) 27–30

    F. Chollet, A definition of intelligence for the real world, Journal of Artificial General Intelligence 11 (2) (2020) 27–30. 51

    work page 2020

  5. [5]

    Johnson, W

    A. Johnson, W. K. Vong, B. Lake, T. Gureckis, Fast and flexible: Human program induction in abstract reasoning tasks, arXiv preprint arXiv:2103.05823 (2021)

    arXiv 2021

  6. [6]

    Menon, O

    A. Menon, O. Tamuz, S. Gulwani, B. Lampson, A. Kalai, A machine learning framework for programming by example, in: Int. Conf. Machine Learning, PMLR, 2013, pp. 187–195

    work page 2013

  7. [7]

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

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

    work page 1978

  8. [8]

    Grünwald, T

    P. Grünwald, T. Roos, Minimum description length revisited, Interna- tional journal of mathematics for industry 11 (01) (2019)

    work page 2019

Show all 28 references
  1. [9]

    Ferré, Dexteris: Data exploration and transformation with a guided query builder approach, in: Int

    S. Ferré, Dexteris: Data exploration and transformation with a guided query builder approach, in: Int. Conf. Database and Expert Systems Applications, Springer, 2023, pp. 361–376

    2023

  2. [10]

    Ferré, Tackling the abstraction and reasoning corpus (ARC) with object-centric models and the MDL principle, in: Int

    S. Ferré, Tackling the abstraction and reasoning corpus (ARC) with object-centric models and the MDL principle, in: Int. Symp. Intelligent Data Analysis, Springer, 2024, pp. 3–15

    2024

  3. [11]

    Fischer, M

    R. Fischer, M. Jakobs, S. Mücke, K. Morik, Solving Abstract Reasoning Tasks with Grammatical Evolution., in: LWDA, CEUR-WS 2738, 2020, pp. 6–10

    2020

  4. [12]

    Alford, A

    S. Alford, A. Gandhi, A. Rangamani, A. Banburski, T. Wang, S. Dan- dekar, J. Chin, T. Poggio, P. Chin, Neural-guided, bidirectional program search for abstraction and reasoning, in: Int. Conf. Complex Networks and Their Applications, Springer, 2021, pp. 657–668

    2021

  5. [13]

    Ouellette, Towards efficient neurally-guided program induction for arc-agi, arXiv preprint arXiv:2411.17708 (2024)

    S. Ouellette, Towards efficient neurally-guided program induction for arc-agi, arXiv preprint arXiv:2411.17708 (2024)

    2024 arXiv

  6. [14]

    Y. Xu, E. B. Khalil, S. Sanner, Graphs, constraints, and search for the abstraction and reasoning corpus, arXiv preprint arXiv:2210.09880 (2022)

    2022 arXiv

  7. [15]

    Ainooson, D

    J. Ainooson, D. Sanyal, J. P. Michelson, Y. Yang, M. Kunda, An ap- proach for solving tasks on the abstract reasoning corpus, arXiv preprint arXiv:2302.09425 (2023). 52

    2023 arXiv

  8. [16]

    Greenblatt, Getting 50%(sota) on arc-agi with gpt-4o (2024)

    R. Greenblatt, Getting 50%(sota) on arc-agi with gpt-4o (2024). URL https://redwoodresearch.substack.com/p/ getting-50-sota-on-arc-agi-with-gpt

    2024

  9. [17]

    Berman, How i came in first on arc-agi-pub using sonnet 3.5 with evolutionary test-time compute (2024)

    J. Berman, How i came in first on arc-agi-pub using sonnet 3.5 with evolutionary test-time compute (2024). URL https://jeremyberman.substack.com/p/ how-i-got-a-record-536-on-arc-agi

    2024

  10. [18]

    Chollet, On the measure of intelligence, arXiv preprint arXiv:1911.01547 (2019)

    F. Chollet, On the measure of intelligence, arXiv preprint arXiv:1911.01547 (2019)

    2019 arXiv

  11. [19]

    Acquaviva, Y

    S. Acquaviva, Y. Pu, M. Kryven, T. Sechopoulos, C. Wong, G. Ecanow, M. Nye, M. Tessler, J. Tenenbaum, Communicating natural programs to humans and machines, Advances in Neural Information Processing Systems 35 (2022) 3731–3743

    2022

  12. [20]

    Lieberman, Your Wish is My Command, The Morgan Kaufmann series in interactive technologies, Morgan Kaufmann / Elsevier, 2001

    H. Lieberman, Your Wish is My Command, The Morgan Kaufmann series in interactive technologies, Morgan Kaufmann / Elsevier, 2001

    2001

  13. [21]

    Muggleton, L

    S. Muggleton, L. D. Raedt, Inductive logic programming: Theory and methods, Journal of Logic Programming 19,20 (1994) 629–679

    1994

  14. [22]

    Polozov, S

    O. Polozov, S. Gulwani, Flashmeta: A framework for inductive pro- gram synthesis, in: ACM SIGPLAN Int. Conf. Object-Oriented Pro- gramming, Systems, Languages, and Applications, 2015, pp. 107–126

    2015

  15. [23]

    Mulleners, J

    N. Mulleners, J. Jeuring, B. Heeren, Program synthesis using example propagation, in: Int. Symp. Practical Aspects of Declarative Languages, Springer, 2023, pp. 20–36

    2023

  16. [24]

    J. S. Rule, S. T. Piantadosi, A. Cropper, K. Ellis, M. Nye, J. B. Tenen- baum, Symbolic metaprogram search improves learning efficiency and explains rule learning in humans, Nature Communications 15 (1) (2024) 6847

    2024

  17. [25]

    Ellis, et al., Dreamcoder: Bootstrapping inductive program synthe- sis with wake-sleep library learning, in: ACM Int

    K. Ellis, et al., Dreamcoder: Bootstrapping inductive program synthe- sis with wake-sleep library learning, in: ACM Int. Conf. Programming Language Design and Implementation, 2021, pp. 835–850. 53

    2021

  18. [26]

    B. M. Lake, R. Salakhutdinov, J. B. Tenenbaum, Human-level concept learning through probabilistic program induction, Science 350 (6266) (2015) 1332–1338

    2015

  19. [27]

    C. B. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. I. Cowl- ing, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, S. Colton, A survey of monte carlo tree search methods, IEEE Transactions on Computational Intelligence and AI in games 4 (1) (2012) 1–43

    2012

  20. [28]

    E. K. Burke, Y. Bykov, The late acceptance hill-climbing heuristic, Eu. J. Operational Research 258 (1) (2017) 70–78. 54

    2017

Pith tools

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