From I/O to Code with Discovery Agent

Yihong Dong, Jiaru Qian, Haoran Zhang, Peixu Wang, Binhua Li, Zhi Jin, Yongbin Li, Ge Li, Xiaokang Yang, Xue Jiang · 2026

Read From I/O to Code with Discovery Agent by Yihong Dong, Jiaru Qian, Haoran Zhang, Peixu Wang, Binhua Li, Zhi Jin, Yongbin Li, Ge Li, Xiaokang Yang, Xue Jiang (2026) 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-2605-15334.txt.

Introduction

Yihong Dong and nine others tackle program synthesis from input-output behavior, a harder problem than building from natural language, which can lean on pretraining fit. Their DIO-Agent frames the task as evolutionary search over program space, with a language model as mutation operator and execution errors guiding each step. A transformation-priority premise biases changes toward the simplest hypothesis consistent with evidence, climbing from constants to conditionals to loops only when simpler forms fail. A benchmark supports methodical study.

Catalog record

CREATORYihong Dong, Jiaru Qian, Haoran Zhang, Peixu Wang, Binhua Li, Zhi Jin, Yongbin Li, Ge Li, Xiaokang Yang, Xue Jiang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE75902
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.15334

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

From I/O to Code with Discovery Agent Yihong Dong, Jiaru Qian, Haoran Zhang, Peixu Wang, Binhua Li, Zhi Jin, Yongbin Li, Ge Li, Xiaokang Yang, Xue Jiang Abstract The automatic synthesis of a program from any form of specification is regarded as a holy grail of computer science. Fueled by LLMs, NL2Code has achieved tremendous success, yet the fundamentally more challenging task of synthesizing programs from input-output behavior, which we refer to as IO2Code, remains largely unsolved. Whereas NL2Code can exploit the semantic alignment between natural language and code acquired during pretraining, IO2Code requires recovering underlying principles from concrete computational behavior, navigating a vast and underspecified hypothesis space. To address this, we propose DIO-Agent, a discovery agent for IO2Code. Our method frames IO2Code as an evolutionary search over discrete program space, in which an LLM serves as the mutation operator and concrete error signals from execution guide each mutation. To prevent the search from wandering into structurally complex yet incorrect dead ends, we introduce the Transformation Priority Premise as a mutation prior that biases the LLM toward the simplest hypothesis consistent with current evidence, progressively escalating from constants to conditionals to iteration only when simpler constructs are insufficient. To facilitate systematic study, we further construct an IO2CodeBench spanning multiple difficulty levels. Extensive experiments show that DIO-Agent consistently outperforms both traditional program-by-example method and SOTA evolution-agent baselines across all difficulty levels and various LLMs, while substantially surpassing test-time scaling strategies with equivalent sampling budgets. 1 1 1 Our code and dataset are available at https://github.com/JiaruQian/IO2Code . 1 Introduction Large language models (LLMs) have achieved remarkable success in code generation ( Chen et al. 2021 , Nijkamp et al. 2022 , Jiang et al. 2024 , Dong et al. 2024 ) , largely built upon the NL2Code formulation ( Iyer et al. 2018 , Lu et al. 2021 , Austin et al. 2021 ) that converts natural-language descriptions into executable programs ( Hendrycks et al. 2021 ) . NL2Code relies on human-provided descriptions, limiting its applicability when such descriptions are unavailable or unreliable. However, a wide range of real-world tasks requires developers and researchers to work not from NL descriptions, but from computational behavior. From migrating legacy systems with lost source code and reverse-engineering black-box APIs, to abducing algorithms from scientific observations and capturing user intent through input-output demonstrations, these scenarios span system evolution, scientific discovery, and human-computer interaction ( Collie et al. 2020 ) . We refer to this class of tasks as IO2Code, where the goal is to synthesize programs from input-output behavior(Figure 1 ). Figure 1: Illustration of IO2Code, where the mainstream NL2Code task evaluates the composition and reuse ability of LLMs, while the IO2Code task evaluates the induction and discovery ability. IO2Code poses fundamentally more severe challenges than NL2Code. NL2Code largely reduces to composing and reusing code patterns aligned with natural-language descriptions learned during pretraining ( Zan et al. 2023 , Feng et al. 2020 , Wang et al. 2021 ) . In contrast, IO2Code demands induction and discovery, where the model must uncover latent algorithmic structures from concrete computational behavior, infer causal relationships between inputs and outputs, and autonomously construct complete program logic. This requires abductive reasoning from the specific to the general, in which the composition and reuse strategies effective in NL2Code become inapplicable. Furthermore, input-output observations are inherently underspecified, as multiple programs can be consistent with a finite set of examples, demanding that the agent navigate a vast hypothesis space while avoiding overfitting to spurious patterns. To tackle the challenge of IO2Code, we draw on a well-established observation from software engineering. In the practice of Test-Driven Development (TDD), the Transformation Priority Premise (TPP) ( Martin 2021 ) shows that programmers construct algorithms that pass all tests most effectively when they apply transformations in order of increasing complexity, progressing from constants to variables, from unconditional statements to conditionals, and from conditionals to loops or recursion, and that violating this ordering frequently leads to impasses requiring costly rewrites. We observe that TPP can be repurposed as a structural constraint on autonomous program discovery. In IO2Code, where no specification exists beyond input-output behaviors, such a complexity ordering offers a principled mechanism to force the search process to exhaust simpler hypotheses before entertaining structurally more complex ones, thereby preventing both overfitting to surface patterns and aimless wandering in the program space. In this paper, we propose DIO-Agent, a discovery agent for IO2Code. Our method formulates the task as an evolutionary search in which an LLM acts as the mutation operator. In the discrete program space without natural-language guidance, allowing a model to mutate code blindly can easily lead it into structurally complex yet incorrect dead ends. To address this, we introduce TPP as a mutation prior that biases the search toward the simplest hypothesis first, escalating to more expressive constructs only when simpler ones fail to explain the observed behavior. This evolutionary process is organized as a curriculum of increasing difficulty, with concrete error signals from execution grounding each mutation in debugging evidence rather than scalar rewards. To facilitate research, we establish an IO2CodeBench spanning multiple difficulty levels from basic data operations to complex algorithmic reasoning. We conduct extensive experiments on the IO2CodeBench across all difficulty levels. The results demonstrate that DIO-Agent achieves consistent improvements over existing approaches, including traditional PBE methods and SOTA evolution-agent baselines, while substantially surpassing test-time scaling strategies with equivalent sampling budgets. Moreover, DIO-Agent yields stable performance gains across diverse base models, confirming its generalizability. We further validate the effectiveness of each component through comprehensive ablation studies, hyperparameter sensitivity analyses, and illustrative case studies. 2 Motivation Example To illustrate the challenges of IO2Code and motivate our approach, consider a concrete example. Suppose an agent is presented with the following input-output pairs and asked to synthesize a program f consistent with all of them: f(1) = [] f(2) = [2] f(3) = [3] f(4) = [2, 2] f(6) = [2, 3] f(8) = [2, 2, 2] f(12) = [2, 2, 3] f(30) = [2, 3, 5] To human with mathematical training, the underlying rule is recognizable: f computes prime factorization of its input. But the agent receives no such hint. It has no access to the function name, docstring, or NL description, and must recover the rule purely from computational behavior. The Overfitting Trap. The most straightforward strategy, and the one that unconstrained models tend to adopt, is to memorize the observations directly: ⬇ def f ( n ): if n == 1: return [] elif n == 2: return [2] elif n == 3: return [3] ... This program mirrors the tests rather than generalizing from them. It is a lookup table, not an algorithm. It will fail on any input not seen during synthesis such as f(9) or f(100) . In NL2Code, such overfitting is unlikely because the NL specification (e.g., “compute the prime factors of n ”) already constrains the model toward a general solution. In IO2Code, no such constraint exists, and the agent faces an underspecified hypothesis space in which memorization is always locally optimal. The Blind Mutation Trap. An alternative strategy is to apply evolutionary search, randomly mutating candidate programs and selecting those that pass more test cases. However, without structural

Read the complete text