# Interactive Program Synthesis

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2017.

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

- [Hypothesis Search: Inductive Reasoning with Language Models](https://mlsanity.com/paper/2309.05660/) (2023)
- [Interactive Code Generation via Test-Driven User-Intent Formalization](https://mlsanity.com/paper/2208.05950/) (2022)
- [Code to Think, Think to Code: A Survey on Code-Enhanced Reasoning and Reasoning-Driven Code Intelligence in LLMs](https://mlsanity.com/paper/2502.19411/) (2025)
- [NeuroSync: Intent-Aware Code-Based Problem Solving via Direct LLM Understanding Modification](https://mlsanity.com/paper/2508.02823/) (2025)
- [Neural Program Synthesis with Query](https://mlsanity.com/paper/2205.07857/) (2022)
- [Example-based Synthesis of Static Analysis Rules](https://mlsanity.com/paper/2204.08643/) (2022)

## Abstract (arXiv)

Program synthesis from incomplete specifications (e.g. input-output examples) has gained popularity and found real-world applications, primarily due to its ease-of-use. Since this technology is often used in an interactive setting, efficiency and correctness are often the key user expectations from a system based on such technologies. Ensuring efficiency is challenging since the highly combinatorial nature of program synthesis algorithms does not fit in a 1-2 second response expectation of a user-facing system. Meeting correctness expectations is also difficult, given that the specifications provided are incomplete, and that the users of such systems are typically non-programmers. In this paper, we describe how interactivity can be leveraged to develop efficient synthesis algorithms, as well as to decrease the cognitive burden that a user endures trying to ensure that the system produces the desired program. We build a formal model of user interaction along three dimensions: incremental algorithm, step-based problem formulation, and feedback-based intent refinement. We then illustrate the effectiveness of each of these forms of interactivity with respect to synthesis performance and correctness on a set of real-world case studies.