ANPL: Towards Natural Programming with Interactive Decomposition

Summary

In this paper, the authors introduce Abstracted Natural Programming Language (ANPL), a programming language and system to improve Large Language Model (LLM) assisted programming. ANPL programs are structured in a top-down manner; a top level program called the "sketch" solves the task by specifying the data-flow between multiple secondary level sub-functions called "holes". Each "hole" encapsulates a textual description of its targeted functionality. This ANPL program is then translated into a conventional python program via the ANPL compiler, which uses LLMs to implement the "holes". Further, to help debug the generated/compiled program, the system provides features such as exposing execution traces and intelligently merging novel user edits to hole descriptions. Human study shows that compared to using LLMs naively, ANPL helps users solve programming tasks faster and with higher success rate. Finally, the paper also contributes a dataset of textual decomposition (by humans) of 300/400 reasoning tasks in the ARC benchmark, which can provide insights into how humans decompose programming tasks.

Strengths

### Originality The idea of improving programming by decomposing the program into sketches and holes in itself is not a novel idea (the authors properly cite previous works along this direction). However, structuring a LLM-augmented programming interface around this system is indeed novel. ### Quality The paper is well written. Further, it presents insightful experiments and ablations in the main paper as well as the extended appendix. ### Significance This paper targets the fastly-evolving direction of LLM assisted programming, and hence will be of interest to the research community at large. While "sketch-hole decompostion" is commonly used in LLM assisted programming, this paper provides a thorough human study to firmly establish the benefits of such an approach.

Weaknesses

While overall I believe its a well written paper, there are certain weaknesses with the presentation and the experiments section. ### Presentation / Clarity 1) The main paper does not clearly show *what* an ANPL program looks like - what is the input to the LLM?. The main paper only refers to Figure 1 which shows an ANPL program pictorially. While the ANPL compiler (written in ANPL) is in the paper, I believe it would be easier to understand the system with a clearer and explicit presentation of what a "sketch" is and what a "hole" is programmatically. 2) The main paper does not discuss the actual interface that the user uses (only shown in the appendix). As this is a crucial contribution of a "programming" system, I think it should also be shown in the main paper. 3) In general, the paper entangles a methodology contribution (using a sketch-hole paradigm for LLM assisted programming) with a system contribution (The interface, debugging features, merging features, test-case creation tools). ### Experiments 1) The interface seem to have additional features such as grid editor to create test cases etc. which may contribute to the user success. This make it harder the discern what parts of ANPL are essential. 2) An important baseline missing is users directly programming in python. On roughly 30% of the tasks, even with ANPL users take ~15 mins. Looking at the ARC challenge examples, I think directly programming in python may be faster than programming with ANPL (or the other baselines). 3) Program solutions which satisfy test cases but fail for train cases are counted as "successful" while measuring the success rate. (Refer Table 2 appendix and results in the main paper). If we count only the cases where both test and train cases are successful, the performance drops to 56.7% for ANPL versus 48.5% for naive LLM usage, which is significantly lower than the numbers used in the main paper. I think that successful programs should satisfy both train and test cases. ### Others 1) Many real world programming tasks are unlike the problems in ARC. Hence, its unclear if ANPL would be better than naive LLM systems in typical programming use-cases as well. 2) Another drawback of using ARC is that many tasks may involve sub-functions which are similar. Therefore users may benefit from know "what prompts works better" for certain sub-functions, and use them directly in future prompts (sort of saving the previously discovered functions). Therefore, a task benchmark where the tasks were more diverse might have been more suitable. 3) As GPT-4 seems to be much more performant than GPT-3.5 (used in the experiments) I wonder if the gap between ANPL and naive LLM usage is further decreased when larger LLMs are used.

Questions

I thank the authors for providing an extensive appendix which answers many of the questions I had. However, a few more are as follows: 1) How often do users get the "sketch" wrong - are there some cases where the failure is due to wrong sketch while the hole implementations are correct? 2) Can the authors briefly talk about the learning curve of using ANPL? 3) Can the authors justify the choice for using train-fail-test-success as successful programs while measuring success rate?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

The authors have adequately addressed the limitations and potential negative societal impact of their work.

Summary

This paper proposes ANPL, a programming system for user interaction with an LLM for code generation. The main idea is to have the user generate high-level dataflow and program structure, while directing the LLM to fill in the "holes." They present results of a user study of ANPL, where users are asked to write programs to solve ARC tasks, and show that ANPL outperforms a baseline of (undirected) user interaction with GPT-3.5 via ChatGPT, and one-shot program synthesis using ANPL and GPT-3.5.

Strengths

This paper presents a novel method of incorporating LLMs into a programming workflow. A major strength is the design of ANPL. Though the idea of decoupling a synthesis problem into a hole and a sketch is not new in program synthesis (or even neural program synthesis [1]), the application (and execution) here for an LLM-driven coding assistant seems novel and natural. The user study is also significant, and contains a lot of great analysis. The writing is also very clear. [1] Nye, Maxwell, et al. "Representing Partial Programs with Blended Abstract Semantics." International Conference on Learning Representations. 2020.

Weaknesses

My major concern is that the main contributions are (1) a programming system and (2) its evaluation. There is not much novelty on LLMs or even neural program synthesis. Some additional points about the design of the user study: - Most users in the user study were unfamiliar with code generation using LLMs (Figure 5 in the appendix), and only 1 prompt was provided as example (Figure 10 in the appendix). Therefore, it's not clear how much the difference in performance is due to inexperienced users of System B. For instance, the design of the study could have provided both the ANPL prompt (Figure 4 in the appendix) to the users as well, or given them some basic training first. - ARC is designed as a test of human intelligence, so the performance of a human + ANPL on ARC doesn't directly translate into performance on writing programs. Ideally the results would have included an additional dataset designed for synthesis (such as MBPP or HumanEval).

Questions

Can you provide results for users aggregated by the language model code generation experience? The performance of System B appears to saturate very quickly. This could be due to a degradation in performance of System B over time, for instance, as the context grows too long. Were the contexts for the LLMs reset at any point for either ANPL or System B?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

2 fair

Limitations

Yes

Summary

The paper proposes ANLP, a framework that interactively gets the definition of the data flow of a program from user input, and then fill the "holes" in the sketched program using LLMs. The authors conducted comprehensive human experiments on the Abstraction and Reasoning Corpus by letting human subjects solve the problems using an off-the-shelf language model and the ANPL-wrapper language model. The results show that with ANLP people are better at solving ARC problems.

Strengths

1. Splitting the burden of reasoning between human programmers and language models is reasonable. Humans can focus on higher-level planning and leave the implementation details to language models. 2. The evaluation with human subjects is convincing. In terms of solving rate and efficiency, it's clear that ANPL is easier to use than bare ChatGPT. 3. Letting users define the dataflow in a python-like language is friendly for programmers and easy for the model to understand.

Weaknesses

1. The idea of decomposing a task into modular functions is not new. As the authors have mentioned, even under the LLM setting it's been used by Parsel (https://arxiv.org/pdf/2212.10561.pdf). Even though the authors emphasizes the novelty of human interaction, I don't find your system significantly different from theirs. Of course your human evaluation is much more comprehensive. 2. Evaluating on ARC alone seems not enough. While the tasks seem good for testing the reasoning ability, it is not clear whether ANPL can work for real-world applications that help actual programmers. The definition of data flow can get complicated and harder for the model to understand as the program gets longer.

Questions

1. Does ANPL work well for complicated data flows and longer programs? 2. Does ANPL work for real world applications at larger scales?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

The authors have addressed the limitations.

Summary

ANPL proposes a Sketch guided program synthesis using Natural Language in an interactive fashion.The results show better interactive coding than base LLM.

Strengths

The paper shows potential in using sketch guided methods in conjunction with LM inference. It can be a good tool to use for debugging and potentially to teach programming.

Weaknesses

Though the method show promise, some amount of work is necessary to justify the applicability of the system in wider settings. Some proof of guarantee on how the sketch helps in overall synthesis can also throw some light to the reader on why a system like this can be useful and should be adopted by wider research community. Some specific points: 1. Although an interesting direction, it would have been great to see the performance of the model in general purpose programming tasks, and not only for debugging. 2. The availability of only a specific syntax seem very limiting to applicability. It is not clear on how to use the system for new domains. 3. Some recent works on LLM that work in conjunction with Sketch guided synthesis seem to be missing.

Questions

1. How do we extend the system to a general purpose program decomposition problem solving method?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

The limitations section need considerable improvement.

Thank you for the rebuttal!

## Summary Thank you for the detailed rebuttal. The rebuttal, along with the other reviews has helped improve my understanding of the proposed system. I have decided to increase the score of the paper to 7-accept as the authors have addressed almost all of the weaknesses and questions I raised. ## Response to the rebuttal in detail 1) Presentation - It is unclear what are the changes the authors are planning. How are the authors planning to revise the paper? My suggestion would to at least include one figure of the interface. Further, it would be useful if figure one explicitly shows the "sketch" code as well as the "hole" code (instead of a pictorial representation). I would be happy to hear the author's view. 2) Experiments: Thank you for clarifying that the grid is provided for all the ablated systems. I find it interesting that a lot of the time is spent waiting for the GPT prompts. I wonder if the users were told to use python functions that they code up if necessary. Nonetheless, the lack of a python only baseline is but a minor drawback. My third query, on test-set vs train-set scores is also well addressed. I recommend that the authors include the stated reasons in the appendix while discussing these statistics. 3) Others - I appreciate the results in the real-world program setup, it addresses my first two issues. I thank the authors for results with GPT-4. Since ANPL's goal is reasoning about user intent (rather than solving a task), better models would perhaps improve ANPL as well. Also, thank you for answering my questions! I find the results useful to improve my understanding of ANPL.