Choose, Don't Label: Multiple-Choice Query Synthesis for Program Disambiguation
Celeste Barnaby, Danny Ding, Osbert Bastani, Isil Dillig
Abstract
High-level specifications of code are inherently ambiguous, and prior systems have explored interactive techniques to help users clarify their intent and resolve such ambiguities. However, most existing approaches elicit supervision through labeled examples, which are often error-prone and may fail to capture user intent. This paper introduces a new active learning paradigm for program disambiguation based on multiple-choice queries. In this paradigm, the system presents a small set of high-level behaviors as multiple-choice options, and the user simply selects the intended one. Technically, each answer option corresponds to a Hoare triple that characterizes a cluster of semantically similar candidate programs. This formulation enables formal reasoning about the informativeness and interpretability of queries, and supports systematic construction of optimal queries. Building on this insight, we develop a new active learning algorithm and implement it in a tool called Socrates, which automatically synthesizes informative multiple-choice queries for program disambiguation. We evaluate Socrates across four domains spanning both symbolic and neurosymbolic settings and show that it produces intuitive, easy-to-answer queries and achieves efficient convergence. Most importantly, Socrates identifies the intended program more reliably than existing methods, while maintaining competitive runtime performance.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
- CodeGen: An Open Large Language Model for Code with Multi-Turn Program Synthesis cites Language Models are Few-Shot Learners
- Jigsaw: Large Language Models meet Program Synthesis cites Multi-modal synthesis of regular expressions
- Jigsaw: Large Language Models meet Program Synthesis cites Language Models are Few-Shot Learners
Builds on19
- Language Models are Few-Shot LearnersTom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah et al.NeurIPS 2020 · 64,255 citations
- ViperGPT: Visual Inference via Python Execution for ReasoningDídac Surís, Sachit Menon, Carl VondrickICCV 2023 · 732 citations
- CodeGen: An Open Large Language Model for Code with Multi-Turn Program SynthesisErik Nijkamp, Bo Pang, Hiroaki Hayashi, Lifu Tu et al.ICLR 2023 · 234 citations
- Jigsaw: Large Language Models meet Program SynthesisNaman Jain, Skanda Vaidyanath, Arun Iyer, Nagarajan Natarajan et al.ICSE 2022 · 134 citations
- Multi-modal synthesis of regular expressionsQiaochu Chen, Xinyu Wang, Xi Ye, Greg Durrett et al.PLDI 2020 · 81 citations
Related papers
- Active Learning for Neurosymbolic Program SynthesisCeleste Barnaby, Qiaochu Chen, Ramya Ramalingam, Osbert Bastani et al.OOPSLA 2025 · 2 citations
- Assuage: Assembly Synthesis Using A Guided ExplorationJingmei Hu, Priyan Vaithilingam, Stephen Chong, Margo I. Seltzer et al.UIST 2021 · 10 citations
- Active Learning of Symbolic Automata for Reactive Programs via Dynamic Symbolic MapperYoel Kim, Yunja ChoiFSE 2026
- Polygon: Symbolic Reasoning for SQL using Conflict-Driven Under-Approximation SearchPinhan Zhao, Yuepeng Wang, Xinyu WangPLDI 2025
- Guiding Program Synthesis by Learning to Generate ExamplesLarissa Laich, Pavol Bielik, Martin T. VechevICLR 2020 · 17 citations
