{"id":"b7a61063-8a48-4975-81f3-c29fe5c4b284","arxiv_id":"2505.01081","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":7,"one_line_summary":"MADIL uses MDL-based decomposition and composition of grids to synthesize interpretable programs from a few examples, solving 57 of 400 ARC evaluation tasks with an 82% generalization rate.","lead":"This paper presents MADIL, a program synthesis system that learns grid-transformation rules from a few examples using the Minimum Description Length principle, and applies it to the ARC benchmark. It reports 7% accuracy on ARC's private test set, far below LLM-based systems, but runs on a single CPU in under a minute and produces human-interpretable programs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central claim rests on public evaluation tasks treated as a reliable generalization estimate, but the private-set result (7%) is far below the evaluation-set result (14%) and no confidence intervals or random splits are provided.","rationale":"The reader identifies the hand-crafted priors and value distributions as the weakest assumption, which is a valid concern. My stress-test focuses on a related but more specific issue: the evaluation methodology treats the public evaluation set as a reliable estimate of generalization, yet the paper's own private-set score (7%) is half the evaluation-set score (14.25%), and no uncertainty quantification or random split is provided. This is load-bearing because the central claim asserts general efficiency and applicability, but the main positive result (57/400) could be inflated by the fixed nature of the public evaluation tasks. The paper is honest about limitations and provides open source code, which supports its credibility, but the evidence for the central claim is weaker than the headline numbers suggest. A conditional verdict is appropriate: the method shows promise and is clearly described, but the performance claims need a statistically grounded evaluation, such as a held-out random split or confidence intervals, before the general framework claim can be accepted. The paper's own Section 8.4 lists many missing primitives, which further supports the concern that the approach's performance is tied to the manually engineered DSL rather than a general MDL-based induction mechanism.","tokens_in":27564,"tokens_out":1924,"duration_ms":20738,"concrete_test":"Run MADIL on the 400 public training tasks (disjoint from the evaluation and private sets) and compare the proportion of tasks solved and the generalization rate to the reported evaluation-set results, with bootstrap confidence intervals. Also report the number of failures attributable to 'no model found' vs. 'found but did not generalize' vs. 'missing primitive' on a random subset, to quantify how much of the performance gap stems from the hand-crafted patterns and functions.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's central claim is that MADIL is a general framework enabling efficient program synthesis on ARC, with evidence of 57/400 public evaluation tasks solved (82% generalization among found solutions) and 7% on the private ArcPrize 2024 set. The load-bearing issue is that the public evaluation tasks are a fixed, publicly known set, and the authors use them as if they were a random sample of ARC tasks. No confidence intervals, standard errors, or a random split of tasks are reported. The gap between 14.25% on evaluation tasks and 7% on the private set is large, suggesting the evaluation-set performance may not be a stable estimate of generalization to a random unseen task. Additionally, Section 8.3's parameter study selects 71 evaluation tasks 'that are satisfactorily solved in any MADIL version from v3.2 to v3.6' (Section 8.3), which is post-hoc selection and biases the robustness claims. The authors do not report how many of the 400 evaluation tasks overlap with the private set, nor do they provide a breakdown of failures by missing primitives vs. search failures vs. generalization failures for the evaluation set. Section 8.4 acknowledges missing primitives and other limits, but does not quantify their impact on the reported 7%. Without a random or held-out split, the central claim that MADIL is a general framework with 'highly efficient' search is supported primarily by a single, possibly non-representative public evaluation.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":28058,"tokens_out":6772,"duration_ms":75252,"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":[{"comment":"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.","section":"§8.1, Table 6"},{"comment":"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.","section":"§8.3"},{"comment":"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.","section":"§6.4 and §7.3"},{"comment":"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.","section":"§5.2.2, Equations (1)-(4)"}],"minor_comments":[{"comment":"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.","section":"§8.1"},{"comment":"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.","section":"§8.3 and Table 3"},{"comment":"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.","section":"§6.4 and §7.3"},{"comment":"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.","section":"§1 and §3"}],"recommendation":"major_revision","confidential_remarks":"The paper is honest about its limits and the code and logs are available, which is commendable. The main concerns are statistical: the public/private-set gap and the post-hoc selection in the ablation study. I would encourage the editor to ask for a revision that adds confidence intervals or random splits and reruns the parameter study on the full evaluation set. The theory-practice gap concerning the rehearsal factor and normalized DL is also important but appears fixable within the scope of a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: this is a real, honest program-synthesis attempt for ARC, not a flashy LLM result. The authors extend their prior MADIL framework with collections, dependent patterns, and MCTS, ship open-source code, and report results that are modest but clearly explained. The efficiency claim holds up: most solutions are found within seconds, at search depths that would be intractable for brute-force DSL search. That is the paper's genuine contribution, and it is worth taking seriously.\n\nThe new material is real: collection-valued patterns, dependent patterns like Crop, and an MCTS variant over model transitions. These are incremental but sensible extensions, and the presentation is careful. The formal framework is a reasonable MDL treatment of pattern-based decomposition, though the implementation deviates with ad hoc mechanisms: the rehearsal factor alpha, normalized description length, and sampling approximations. Those deviations are disclosed, which is good, but they mean the theory is a scaffold for the engineering rather than a tight guarantee.\n\nThe soft spot is evaluation. The paper treats the 400 public evaluation tasks as a robust test set, but those tasks are fixed and publicly known. The 57/400 (14.25%) public result versus 7% on the private set is a large gap, and no confidence intervals or random splits are reported. The parameter study selects 71 evaluation tasks that were \"satisfactorily solved in any MADIL version\"—post-hoc selection that weakens the robustness claims. The failure analysis is qualitative and does not quantify how much of the private-set shortfall comes from missing primitives versus search failures versus generalization failures. These are not fatal flaws, but they should be addressed with a held-out split and error bars before the central generalization claim is accepted.\n\nThe authors are transparent about limitations, and the citation pattern is appropriate—prior work is credited, and comparisons to Icecuber and LLM methods are fair. The proofs are sketchy but adequate for a systems paper; the real burden is empirical.\n\nWho is this for? People working on ARC, program synthesis, or interpretable inductive learning. It will not change minds about LLM superiority on ARC, but it is a solid, reproducible counterpoint showing what a frugal MDL-guided search can do. I would send it to a serious referee: the method is clearly described, the code is available, and the claims are testable even if the generalization estimate needs tightening.","headline":"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.","tokens_in":28392,"tokens_out":1283,"would_cite":true,"duration_ms":16257,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["Abstraction and Reasoning Corpus","ARC-AGI","Minimum Description Length","program synthesis","pattern-based decomposition","inductive learning","Monte Carlo Tree Search","interpretable AI"],"falsifier":"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.","tokens_in":1555,"feed_emoji":"🧩","tokens_out":2221,"duration_ms":68080,"temperature":0.7,"pith_summary":"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.","feed_headline":"Compression-guided search solves 57 public ARC tasks in under a minute","feed_subtitle":"A pattern-decomposition learner reaches 82 percent generalization on solved public tasks, with no LLM pre-training.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Provides the MDL principle: the best model is the one that most compresses the data; this is the objective the whole search optimizes.","marker":"[7, 8]"},{"why":"Frames intelligence as skill-acquisition efficiency and defines the ARC task collection that MADIL is built to solve.","marker":"[4]"},{"why":"Supplies the programming-by-example setting and the DAG-based indexing of expressions used to retrieve candidate expression transitions by value.","marker":"[6]"},{"why":"Supplies psychological evidence that human solvers use object-centric representations, motivating object and segmentation patterns.","marker":"[5]"},{"why":"Previous versions of the MADIL approach that this paper extends with collections, dependent patterns, and MCTS.","marker":"[9, 10]"},{"why":"States that efficiency is a key factor in intelligence, the reason the paper emphasizes cheap single-CPU search over brute-force generation.","marker":"[18]"},{"why":"Describes MCTS, which the paper adapts to balance exploitation and exploration when greedy search hits local minima.","marker":"[27]"}],"fun_headline_variants":["MDL-driven search solves ARC puzzles in seconds, no LLM","Compression-guided synthesis: 82% generalization on solved ARC tasks","First greedy rollout finds most ARC solutions via MDL","Under a minute: MDL-based program synthesis on ARC","Pattern decomposition with MDL solves 57 ARC tasks fully"],"cache_read_input_tokens":30464,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["MDL-driven search solves ARC puzzles in seconds, no LLM","Compression-guided synthesis: 82% generalization on solved ARC tasks","First greedy rollout finds most ARC solutions via MDL","Under a minute: MDL-based program synthesis on ARC","Pattern decomposition with MDL solves 57 ARC tasks fully"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000414,"raw_usage":{"total_tokens":2077,"prompt_tokens":821,"completion_tokens":1256,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":437,"completion_tokens_details":{"reasoning_tokens":1172}},"tokens_in":437,"tokens_out":1256,"duration_ms":11450,"temperature":1.0,"reasoning_tokens":1172,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T04:27:21.268250+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Chollet, A definition of intelligence for the real world, Journal of Artificial General Intelligence 11 (2) (2020) 27–30","cited_arxiv_id":null,"evidence_quote":"Frames intelligence as skill-acquisition efficiency and defines the ARC task collection that MADIL is built to solve."},{"cited_title":"Menon, O","cited_arxiv_id":null,"evidence_quote":"Supplies the programming-by-example setting and the DAG-based indexing of expressions used to retrieve candidate expression transitions by value."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Describes MCTS, which the paper adapts to balance exploitation and exploration when greedy search hits local minima."}],"review_version":1}