🤖 machine learning

From I/O to Code with Discovery Agent

This paper introduces DIO-Agent, a discovery framework that solves the challenging IO2Code problem by framing program synthesis as an evolutionary search guided by execution errors and a "Transformation Priority Premise" to prioritize simple hypotheses, demonstrating superior performance over existing methods on a newly constructed IO2CodeBench.

Original authors: Yihong Dong, Jiaru Qian, Haoran Zhang, Peixu Wang, Binhua Li, Zhi Jin, Yongbin Li, Ge Li, Xiaokang Yang, Xue Jiang

Published 2026-05-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yihong Dong, Jiaru Qian, Haoran Zhang, Peixu Wang, Binhua Li, Zhi Jin, Yongbin Li, Ge Li, Xiaokang Yang, Xue Jiang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot how to do a magic trick.

The Old Way (NL2Code):
Usually, you tell the robot, "Please sort these numbers from smallest to largest." The robot reads your words, remembers similar tricks it learned while studying, and performs the task. This is called NL2Code (Natural Language to Code). It's like giving someone a recipe and asking them to cook the dish.

The New Challenge (IO2Code):
Now, imagine you can't speak to the robot. You can't give it a recipe. Instead, you just show it a few examples of the trick in action:

You put in a red ball, and it pulls out a blue ball.
You put in two red balls, and it pulls out a blue ball and a green ball.
You put in a blue ball, and it pulls out nothing.

The robot has to figure out the secret rule behind the magic just by watching the inputs and outputs. It has to guess the "recipe" without ever being told what the ingredients are. The paper calls this IO2Code (Input-Output to Code).

The problem is that this is incredibly hard. If the robot just memorizes the examples ("If red, then blue"), it fails when you give it a new color. If it guesses a complex rule too quickly, it might get stuck in a dead end.

The Solution: The "Discovery Agent" (DIO-Agent)

The authors created a new AI agent called DIO-Agent to solve this puzzle. They didn't just let the AI guess randomly; they gave it a specific strategy based on how human programmers actually learn.

Here is how DIO-Agent works, using a simple analogy:

1. The "Curriculum" (Learning by Stages)

Imagine a video game where you start on "Easy Mode" and slowly unlock harder levels.

The Strategy: Instead of showing the AI all the examples at once, DIO-Agent shows it only the easiest ones first.
Why it helps: The AI learns a simple rule that works for the easy cases. Then, it gets a few harder examples. If the simple rule breaks, the AI knows it needs to upgrade its rule, but it keeps the parts that were already working. It builds up complexity step-by-step, rather than trying to solve the whole puzzle in one giant leap.

2. The "Transformation Priority" (The Rule of Simplicity)

The paper uses a concept from software engineering called the Transformation Priority Premise (TPP). Think of this as a strict rule for how the AI is allowed to change its guess.

The Rule: The AI is forced to try the simplest possible explanation first.
- Level 1: "Is the answer just a constant number?" (e.g., Always return 5).
- Level 2: "Does it depend on the input directly?" (e.g., Return the number you gave me).
- Level 3: "Do we need a decision?" (e.g., If the number is even, do X; if odd, do Y).
- Level 4: "Do we need a loop?" (e.g., Keep doing this until the number is small).
Why it helps: This stops the AI from jumping straight to a super-complicated, messy solution that happens to work for the specific examples but is actually wrong. It forces the AI to "exhaust" simple ideas before trying complex ones, just like a detective ruling out simple suspects before looking for a mastermind.

3. The "Error-Grounded Feedback" (Learning from Mistakes)

When the AI tries a guess and it fails, it doesn't just get a "Wrong" score.

The Strategy: The system shows the AI exactly where it failed. "You got the first three examples right, but you failed on the fourth one because you forgot to handle negative numbers."
Why it helps: This acts like a coach pointing out a specific mistake in a sports drill, rather than just saying "You lost the game." It guides the AI to fix that specific hole in its logic.

The Results

The researchers tested this new agent on a huge set of puzzles (called IO2CodeBench) ranging from simple math to complex geometry and even image analysis.

The Winner: DIO-Agent beat all the other methods, including traditional programming tools and other advanced AI "evolution" agents.
Efficiency: It didn't just win by guessing more times; it won by guessing smarter. It found the correct, simple rules faster and with less "wasted" effort than its competitors.
Generalization: The AI didn't just memorize the training examples; it actually figured out the underlying logic, allowing it to solve new, unseen problems correctly.

In a Nutshell

The paper argues that while AI is great at following written instructions (NL2Code), it struggles to figure out rules from behavior alone (IO2Code). By forcing the AI to learn in stages, prioritize simple solutions over complex ones, and learn specifically from its errors, DIO-Agent can successfully "discover" the hidden rules of a system, acting like a true scientific detective rather than just a memorization machine.

Technical Summary: From I/O to Code with Discovery Agent

Problem Definition: IO2Code

The paper addresses a fundamental challenge in program synthesis distinct from the mainstream Natural Language to Code (NL2Code) paradigm. While NL2Code relies on the semantic alignment between natural language descriptions and code acquired during pretraining, IO2Code (Input-Output to Code) requires synthesizing a generalized program strictly from a limited set of input-output (I/O) pairs without any natural language specification.

The authors argue that IO2Code poses significantly more severe challenges than NL2Code:

Induction vs. Composition: NL2Code largely reduces to composing and reusing code patterns aligned with learned descriptions. In contrast, IO2Code demands induction and discovery, requiring the model to uncover latent algorithmic structures, infer causal relationships, and autonomously construct complete logic from concrete computational behavior.
Underspecification: I/O observations are inherently underspecified; multiple distinct programs can be consistent with a finite set of examples. This creates a vast hypothesis space where agents risk overfitting to spurious patterns (memorization) or wandering into structurally complex but incorrect "dead ends."
Failure Modes: The paper identifies two primary failure modes in existing approaches:
1. The Overfitting Trap: Models memorize specific examples (e.g., lookup tables) rather than generalizing, failing on unseen inputs.
2. The Blind Mutation Trap: Evolutionary search without structural guidance produces syntactically complex but semantically wrong programs, leading to structural dead ends that are difficult to escape.

Methodology: DIO-Agent

To address these challenges, the authors propose DIO-Agent, a discovery agent that frames IO2Code as an evolutionary search over discrete program space. The method integrates three core components:

1. Curriculum-wise Evolution

The search process is organized into stages of increasing difficulty.

Curriculum Construction: Visible examples are sorted from easy to hard based on input/output complexity.
Stage-wise Progression: The agent starts with a subset of easy examples ( $C_1$ ) and progressively introduces harder examples ( $C_2, \dots, C_S$ ).
Initialization: For each new stage $s$ , the search is initialized with the best program found in stage $s-1$ , rather than restarting from scratch. This allows the agent to refine partially correct programs rather than re-discovering basic logic.

2. Transformation Priority Premise (TPP) Guided Mutation

Inspired by the Transformation Priority Premise (TPP) from Test-Driven Development (TDD), DIO-Agent introduces a structural prior to bias the Large Language Model (LLM) during mutation.

Ordered Complexity: The LLM is instructed to apply transformations in a specific order of increasing structural complexity: nil $\to$ constant $\to$ variable $\to$ unconditional $\to$ conditional $\to$ iteration $\to$ recursion.
Mechanism: The agent must exhaust simpler hypotheses (e.g., returning a constant or a variable) before attempting more complex constructs (e.g., loops or conditionals). This prevents the search from jumping prematurely to complex, overfitting solutions and forces the agent to identify the minimal sufficient rule.
Implementation: The LLM is prompted to propose SEARCH/REPLACE diffs rather than full rewrites, preserving working code while adhering to the complexity ordering.

3. Error-Grounded Feedback

Instead of relying solely on scalar accuracy scores, DIO-Agent utilizes structured feedback artifacts.

Concrete Failure Cases: The evaluator executes candidate programs on both the current curriculum set and a replay set of earlier examples. It returns specific failure cases (mismatched outputs or runtime errors).
Feedback Chain: These concrete errors, along with an inherited chain of feedback from ancestor programs, are injected into the prompt for subsequent mutations. This provides the LLM with explicit debugging evidence rather than abstract rewards.
Scoring: A stage-level selection score balances accuracy on the current curriculum against penalties for complexity and memorization (overlap between provided I/Os and generated code).

Key Contributions

Formalization of IO2Code: The paper defines IO2Code as a distinct task focusing on induction and discovery, contrasting it with the composition-heavy NL2Code task.
IO2CodeBench: The authors construct a new benchmark spanning four difficulty levels: Base (scalar/list operations), Algorithm (complex reasoning), Geometry (spatial computation), and Multimodal (image-to-numerical extraction). The benchmark includes 125 tasks with strict train-test splits to prevent leakage.
DIO-Agent Architecture: The proposal of a structured evolutionary loop combining curriculum learning, TPP-guided mutation, and error-grounded feedback to navigate the underspecified program space.
Active Exploration: The paper demonstrates the agent's capability in an "Autonomous Discovery" setting where the model actively designs its own I/O examples to query a ground-truth oracle, further validating the agent's ability to resolve logical ambiguities.

Experimental Results

Extensive experiments on IO2CodeBench demonstrate that DIO-Agent consistently outperforms existing approaches:

Performance: DIO-Agent achieves state-of-the-art results across all difficulty levels.
- Base Level: 61.29% (matching the best baseline).
- Algorithm Level: 71.43% (surpassing all baselines).
- Geometry Level: 61.11% (a substantial improvement over CodeEvolve's 44.44%).
- Multimodal Level: 40.67% (nearly doubling AlphaEvolve's 22.00%).
Generalizability: The method shows robust performance gains across diverse base LLMs (DeepSeek V3.2, Qwen-3.6-Plus, Claude-Sonnet-4.6), confirming it is model-agnostic.
Efficiency: DIO-Agent is more token-efficient than other evolutionary baselines (e.g., 3,738 tokens/iter vs. 5,829 for CodeEvolve), indicating a targeted search process rather than brute-force generation.
Comparison with Scaling: DIO-Agent significantly outperforms test-time scaling strategies (Direct, Best-of-N, Self-Consistency) even when those baselines are granted equivalent sampling budgets (N=40). This suggests that systematic refinement via iterative search is superior to repeated independent sampling for program discovery.
Ablation Studies: Removing Curriculum-wise Evolution caused the largest performance drop (58.63% $\to$ 51.33%), highlighting its critical role in pruning unproductive paths. Removing TPP also led to significant declines, particularly in Geometry and Algorithm tasks.

Significance and Claims

The paper claims that IO2Code represents a "holy grail" of computer science that remains largely unsolved compared to NL2Code. The significance of this work lies in:

Shifting the Paradigm: Moving beyond natural-language-driven code generation to behavior-driven program discovery, which is essential for tasks like legacy system migration, reverse-engineering black-box APIs, and scientific algorithm abduction.
Structural Constraints: Demonstrating that applying software engineering principles (specifically TPP from TDD) as a structural constraint in autonomous agents effectively mitigates overfitting and guides search through vast hypothesis spaces.
Generalizability: Proving that structured, feedback-driven evolutionary search can significantly enhance the induction and discovery capabilities of LLMs across various domains and model backbones, pushing the ceiling of automated program discovery beyond what is achievable through simple prompting or scaling.

The authors conclude that their work draws attention to the broader problem of program discovery from I/O behavior and inspires further exploration beyond natural-language-driven generation.