Program Synthesis

Follow this topic Ask about this topic

Program synthesis studies how to turn desired behavior into executable code, from small transformations and algorithms to robot policies and engineering designs. Methods include enumerative and constraint-based search over domain-specific languages, learning programs from input-output examples, and language-model proposals refined through execution, counterexamples, or formal verification. These approaches can produce reusable, inspectable programs and support settings such as CAD, GPU optimization, and verified software; benchmarks such as ARC-AGI, PBEBench, and ProgramBench test how well systems infer behavior and generalize. Systems are increasingly effective when tasks have clear constraints and feedback, but open-ended synthesis remains difficult: plausible code may fail behavioral tests, miss the intended specification, or generalize poorly beyond the examples and search budget.

Latest papers

182 papers29 papers in the last four weeks, up 61% on the four weeks before. 0.2% of all new papers.

PBEBench: A Multi-Step Programming by Examples Reasoning Benchmark inspired by Historical Linguistics
May 29, 2025Atharva Naik, Prakam, Yash Mathur +6Program Synthesis Inductive Inference
Carnegie Mellon University · Independent Researcher · Ohio State University
ShIOEnv: A Command Evaluation Environment for Grammar-Constrained Synthesis and Execution Behavior Modeling
May 23, 2025Jarrod Ragsdale, Rajendra BoppanaSynthetic Data Generation for Language Models Cybersecurity
Department of Computer Science, University of Texas at San Antonio, San Antonio, USA.

May 29, 2025J/K move · Enter open · S save

PBEBench: A Multi-Step Programming by Examples Reasoning Benchmark inspired by Historical Linguistics

Atharva Naik, Prakam, Yash Mathur, Darsh Agrawal+5

Carnegie Mellon University · Independent Researcher · Ohio State University

Program Synthesis Inductive Inference LLM Evaluation Logical Reasoning Synthetic Benchmark Generation LLM Reasoning+1

Open paper AskPDF arXiv

Although many benchmarks evaluate the reasoning abilities of Large Language Models (LLMs) within domains such as mathematics, coding, or data wrangling, few abstract away from domain specifics to examine reasoning as a capability in and of itself. We contribute a novel type of benchmark evaluating the inductive reasoning capabilities of LLMs that is inspired by the forward reconstruction task from historical linguistics but is formulated in an extremely simple, general way (in the form of Programming by Examples). The task involves generating a cascade of simple string rewrite programs to transform a given list of input strings into a list of desired output strings. We present a fully automated pipeline that programmatically generates problems of this type with controllable difficulty, enabling scalable evaluation of reasoning models while avoiding contamination. Using this approach, we construct two benchmarks: PBEBench-Lite, which efficiently stratifies models of varying capabilities, and PBEBench, which requires models to induce programs similar in complexity to those constructed by historical linguists. Our experiments reveal a substantial performance gap between models that leverage test-time compute or LCoT (long chain-of-thought) reasoning and those that do not. Moreover, although recent models show promise, the solve rate for both of them drops below 5% for hard instances of the PBEBench dataset (ground truth cascade lengths of 20 and 30, respectively), falling well short of realistic historical linguistics requirements even with computationally expensive, popular scaling techniques from the PBE and reasoning literature. Additionally, we also study the effectiveness of different scaling strategies and the impact of various hyperparameters on the difficulty of the generated data using gpt-oss-120b, the best-performing open-source model.

Latest papers

PBEBench: A Multi-Step Programming by Examples Reasoning Benchmark inspired by Historical Linguistics

ShIOEnv: A Command Evaluation Environment for Grammar-Constrained Synthesis and Execution Behavior Modeling