# ANPL: Towards Natural Programming with Interactive Decomposition

arXiv: https://arxiv.org/abs/2305.18498 · HTML: https://mlsanity.com/paper/2305.18498/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 71 references that are in the map.
- First posted on arXiv 29 May 2023.

## Builds on (most cited first, 30 of 40)

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Teaching Large Language Models to Self-Debug](https://mlsanity.com/paper/2304.05128/) (2023)
- [Measuring Coding Challenge Competence With APPS](https://mlsanity.com/paper/2105.09938/) (2021)
- [CodeGen: An Open Large Language Model for Code with Multi-Turn Program Synthesis](https://mlsanity.com/paper/2203.13474/) (2022)
- [CodeXGLUE: A Machine Learning Benchmark Dataset for Code Understanding and Generation](https://mlsanity.com/paper/2102.04664/) (2021)
- [Visual ChatGPT: Talking, Drawing and Editing with Visual Foundation Models](https://mlsanity.com/paper/2303.04671/) (2023)
- [ViperGPT: Visual Inference via Python Execution for Reasoning](https://mlsanity.com/paper/2303.08128/) (2023)
- [MM-REACT: Prompting ChatGPT for Multimodal Reasoning and Action](https://mlsanity.com/paper/2303.11381/) (2023)
- [InCoder: A Generative Model for Code Infilling and Synthesis](https://mlsanity.com/paper/2204.05999/) (2022)
- [CodeT: Code Generation with Generated Tests](https://mlsanity.com/paper/2207.10397/) (2022)
- [CodeRL: Mastering Code Generation through Pretrained Models and Deep Reinforcement Learning](https://mlsanity.com/paper/2207.01780/) (2022)
- [Binding Language Models in Symbolic Languages](https://mlsanity.com/paper/2210.02875/) (2022)
- [Grounded Copilot: How Programmers Interact with Code-Generating Models](https://mlsanity.com/paper/2206.15000/) (2022)
- [TaskMatrix.AI: Completing Tasks by Connecting Foundation Models with Millions of APIs](https://mlsanity.com/paper/2303.16434/) (2023)
- [DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning](https://mlsanity.com/paper/2006.08381/) (2020)
- [Synchromesh: Reliable code generation from pre-trained language models](https://mlsanity.com/paper/2201.11227/) (2022)
- [PromptChainer: Chaining Large Language Model Prompts through Visual Programming](https://mlsanity.com/paper/2203.06566/) (2022)
- [Language Model Cascades](https://mlsanity.com/paper/2207.10342/) (2022)
- [Learning a Neural Semantic Parser from User Feedback](https://mlsanity.com/paper/1704.08760/) (2017)
- [InternGPT: Solving Vision-Centric Tasks by Interacting with ChatGPT Beyond Language](https://mlsanity.com/paper/2305.05662/) (2023)
- [Hierarchical Task Learning from Language Instructions with Unified Transformers and Self-Monitoring](https://mlsanity.com/paper/2106.03427/) (2021)
- ["What It Wants Me To Say": Bridging the Abstraction Gap Between End-User Programmers and Code-Generating Large Language Models](https://mlsanity.com/paper/2304.06597/) (2023)
- [People construct simplified mental representations to plan](https://mlsanity.com/paper/2105.06948/) (2021)
- [Leveraging Language to Learn Program Abstractions and Search Heuristics](https://mlsanity.com/paper/2106.11053/) (2021)

## Built on by (most cited first, 13 of 13)

- [Cut the Crap: An Economical Communication Pipeline for LLM-based Multi-Agent Systems](https://mlsanity.com/paper/2410.02506/) (2024)
- [Combining Induction and Transduction for Abstract Reasoning](https://mlsanity.com/paper/2411.02272/) (2024)
- [CodeS: Natural Language to Code Repository via Multi-Layer Sketch](https://mlsanity.com/paper/2403.16443/) (2024)
- [SOP-Agent: Empower General Purpose AI Agent with Domain-Specific SOPs](https://mlsanity.com/paper/2501.09316/) (2025)
- [The Stochastic Parrot on LLM's Shoulder: A Summative Assessment of Physical Concept Understanding](https://mlsanity.com/paper/2502.08946/) (2025)
- [Enhancing LLM-Based Code Generation with Complexity Metrics: A Feedback-Driven Approach](https://mlsanity.com/paper/2505.23953/) (2025)
- [ARC-GEN: A Mimetic Procedural Benchmark Generator for the Abstraction and Reasoning Corpus](https://mlsanity.com/paper/2511.00162/) (2025)
- [Automated Prompt Engineering for Cost-Effective Code Generation Using Evolutionary Algorithm](https://mlsanity.com/paper/2408.11198/) (2024)
- [Understanding LLMs' Fluid Intelligence Deficiency: An Analysis of the ARC Task](https://mlsanity.com/paper/2502.07190/) (2025)
- [NVIDIA-labs OO Agents: Native Python Object-Oriented Agents](https://mlsanity.com/paper/2607.20709/) (2026)
- [Sharing State Between Prompts and Programs](https://mlsanity.com/paper/2512.14805/) (2025)
- [GraphSeek: Next-Generation Graph Analytics with LLMs](https://mlsanity.com/paper/2602.11052/) (2026)
- [The New Compiler Stack: A Survey on the Synergy of LLMs and Compilers](https://mlsanity.com/paper/2601.02045/) (2026)

## Abstract (arXiv)

Though LLMs are capable of generating plausible programs, it's challenging to interact with the LLMs further to revise the program, especially if the user's specific requirements are different from the initial proposal. In this paper, we introduce ANPL, an interactive programming system that ensures users can always refine the generated code towards their specific programmatic intents via structured decompositions. Borrowing the paradigm of sketching from program synthesis, an ANPL program consists of a set of input-outputs that it must satisfy, a ``sketch'' -- control/data flow expressed in precise code (e.g. Python), and ``holes'' -- sub-modules to be implemented by the LLM specified with natural language. The user revises an ANPL program by either modifying the sketch, changing the language used to describe the holes, or providing additional input-outputs to a particular hole, turning it into a sub-ANPL program that can be solved recursively. This workflow allows the users to offload programming burdens to the LLM as much as possible while retaining the ability to pinpoint and resolve bugs locally, without exposing the rest of the program to the LLM. We deploy ANPL on the Abstraction and Reasoning Corpus (ARC), a set of unique tasks that are challenging for state-of-the-art AI systems, showing it outperforms baseline programming systems that (a) without the ability to decompose tasks interactively and (b) without the guarantee that the modules can be correctly composed together. Additional evaluations on APPS, HumanEval, and real-world programming tasks have validated that the ANPL framework is applicable to multiple programming domains. We release the ANPL solutions to the ARC tasks as a dataset, providing insights into how humans decompose novel tasks programmatically. See our code at https://iprc-dip.github.io/ANPL/.