MADIL: An MDL-based Framework for Efficient Program Synthesis in the ARC Benchmark
Sébastien Ferré · 2025
Read MADIL: An MDL-based Framework for Efficient Program Synthesis in the ARC Benchmark by Sébastien Ferré (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-01081.txt.
Introduction
Sébastien Ferré presents a 2025 paper on MADIL, a program-learning system tested on the ARC benchmark. ARC asks solvers to infer a rule from a few examples, a test of quick, general reasoning. Large language models have raised ARC scores but rest on huge pre-training and heavy computing. MADIL instead follows the minimum description length principle: prefer the program that describes the examples most compactly.
The system breaks patterns into parts, which supports structured generalization to new cases. Its contest score, seven percent at a 2024 prize event, trails language-model methods. Ferré argues the trade is worth study: MADIL learns with far less machinery and its programs can be read and checked by people. The paper details the method, its ARC application, and its test results. It makes a case for frugal, interpretable learning.
Catalog record
| CREATOR | Sébastien Ferré |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 107 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-01081
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
MADIL: An MDL-based Framework for Efficient Program Synthesis in the ARC Benchmark Sébastien Ferré 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 pretraining 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. 1 Introduction Over the past decade, Artificial Intelligence (AI) has achieved remarkable success in specialized tasks, often surpassing human performance in domains such as image recognition [ 1 ] and board games [ 2 ] . However, despite these advances, AI remains limited in its ability to generalize and adapt to novel tasks with minimal training – a hallmark of human intelligence. To encourage progress beyond narrow task-specific generalization [ 3 ] , F. Chollet proposed a new measure of intelligence that prioritizes skill-acquisition efficiency over skill performance [ 4 ] . In this framework, intelligence is defined by the amount of prior knowledge and experience an agent requires to achieve competence across a diverse range of tasks, rather than its peak performance in any single domain. To empirically assess this notion of intelligence, Chollet introduced the Abstraction and Reasoning Corpus (ARC, aka. ARC-AGI), a benchmark designed as a psychometric test for evaluating and comparing human and machine intelligence. ARC consists of a collection of tasks that require learning transformation rules for colored grids based on very limited input-output examples (3.3 on average). Figures 1 and 2 illustrate two sample ARC tasks, with the second serving as a running example throughout this paper. Figure 1: Task 1caeab9d (inputs at the top, outputs at the bottom, test on the right) The Abstraction and Reasoning Corpus (ARC) presents a significant challenge for AI systems. While humans can solve over 80% of the tasks [ 5 ] , AI performance has lagged far behind. The winner of the Kaggle 2020 competition 1 1 1 https://www.kaggle.com/c/abstraction-and-reasoning-challenge managed to solve only 20% of the tasks, relying heavily on hard-coded primitives and brute-force search. A major breakthrough came with the use of Large Language Models (LLMs) for predicting missing grids, an approach pioneered by J. Cole at MindsAI. This innovation led to rapid progress, reaching 30% accuracy at ARCathon 2023 2 2 2 https://lab42.global/past-challenges/arcathon-2022/ and 55% at ArcPrize 2024 3 3 3 https://arcprize.org/ . By the end of 2024, OpenAI’s o3 reasoning LLM achieved human-level performance, albeit at an extremely high computational cost – running the high-compute version required thousands of dollars per task at inference time. Despite these advances, LLM-based methods rely on extensive pre-training with millions of synthesized tasks and require substantial computational resources for fine-tuning and reasoning during inference. As a result, the challenge of efficient skill acquisition remains largely unresolved. In March 2025, a new version of the benchmark, ARC-AGI-2 4 4 4 https://arcprize.org/blog/announcing-arc-agi-2-and-arc-prize-2025 , was introduced to push AI research further. While still simple to most human solvers, ARC-AGI-2 presents significantly greater difficulty for LLMs – demonstrated by o3’s success rate dropping to just a few percent. In this paper, we present MADIL, an alternative approach to the ARC benchmark. MADIL is a general framework for inductive learning from small sets of input-output examples. While we focus on its application to ARC, the method has also been successfully applied to string-to-string transformation tasks, such as those in FlashFill [ 6 ] . MADIL, which stands for “MDL-based AI,” is founded on the Minimum Description Length (MDL) principle – a concept from information theory that states: “The model that best describes the data is the one that compresses it the most” [ 7 , 8 ] . In essence, MADIL searches for task models that both explain the given examples concisely and generalize well to unseen inputs. At inference time, MADIL operates by pattern-based decomposition, breaking down an input into meaningful subcomponents in a top-down manner, then constructing the corresponding output bottom-up. During learning, it identifies optimal decompositions for both inputs and outputs and determines the transformations between corresponding parts. The key advantage of this approach is that the MDL principle guides the decomposition process – favoring representations that achieve greater compression – while also simplifying the residual part-to-part transformations, making them easier to learn. Although MADIL’s overall performance remains below state-of-the-art methods – improving from 2% at ARCathon 2022 to 7% at ArcPrize 2024 – its MDL-based search is highly efficient, enabling the discovery of complex models in under a minute (on a single CPU). Unlike brute-force search approaches that perform a wide but shallow exploration, MADIL conducts a narrow but deep search, with most solutions found early along the first exploration path. Compared to LLM-based approaches, MADIL does not require synthetic task generation or data augmentation. Instead, it leverages Core Knowledge priors, encoded as a set of primitives, patterns and functions. While these primitives are domain-specific – designed for reasoning over colored grids – many are broadly applicable beyond ARC tasks. Examples include arithmetic and bitwise operations, geometric transformations, and collection manipulations, making MADIL a more structured and interpretable alternative to data-intensive deep learning methods. This paper significantly expands on our previous work on MADIL [ 9 , 10 ] , providing deeper explanations, presenting a more advanced solution to ARC, and introducing several novel contributions. Section 2 offers a quick overview of the ARC benchmark. Section 3 discusses related work, covering existing approaches to ARC and broader research in program synthesis. Section 4 introduces our approach through a concrete example task. Section 5 formalizes the general theoretical framework of MADIL and demonstrates its application to ARC. Section 6 describes the key algorithms and other practical aspects. Section 7 presents three recent enhancements to MADIL: (1) the integration of collection management, (2) the use of dependent patterns, and (3) the application of Monte Carlo Tree Search as an improvement over greedy search. Section 8 reports experimental results evaluating MADIL’s performance, efficiency, and limitations. Finally, Section 9 summarizes our findings and outlines directions for future research. 2 Abstraction and Reasoning Corpus (ARC) Figure 2: Task 47c1f68c (inputs at the top, outputs at the bottom, test on the right) ARC is a collection of tasks 5 5 5 Data and testing interface at https://github.com/fchollet/ARC , where each task is made of training examples (3.3 on average) and test examples (1 in general). Each example is made of an input grid and an output grid. Each grid is a 2D array (with size up to 30x30) filled with integers coding for colors (there are 10 distinct colors). For a given task, the size of grids can vary from one example to another, and between the input and the output. Each task is a machine learning problem, whose goal is to learn a model that can generate the output grid from the input grid, and so from a few training examples only. Prediction