Program synthesis: principles and links to AGI

Program synthesis automatically constructs a program that meets a specification: logical properties, input-output examples, or a combination of constraints. It can combine symbolic search with deep learning to propose, execute, and select solutions. This makes it relevant to research on systems that acquire new skills, but producing a correct program within a narrow domain does not demonstrate general intelligence.

The principle: search for an executable rule

In conventional programming, you describe the steps to execute. In synthesis, you primarily describe the desired result, and a system searches for a procedure that meets that requirement. The distinction lies in what remains to be discovered: a transformation, a condition, a combination of operations, or an entire function.

A synthesis task generally has three elements:

a specification describing acceptable behavior;
a program space defined by a language and a set of permitted operations;
a search and checking procedure that proposes candidates and evaluates whether they meet the specification.

The resulting program might be ordinary code, a mathematical expression, or a sequence of operations in a specialized language. It must have defined semantics: there must be a clear way to execute it and interpret its instructions.

This separates synthesis from a natural-language explanation. An answer can correctly describe a method without providing an executable procedure. Conversely, a short program can solve a task without explaining its reasoning in a way that helps someone learn.

Generalization becomes relevant whenever the program must handle inputs that were not included in the examples. Reproducing the supplied answers is therefore insufficient: the system must discover a rule that carries over to the relevant unseen cases.

An example: inferring a text transformation

Consider a teaching example. You supply the following transformations:

Entrée : facture_rouge.pdf
Sortie : rouge

Entrée : facture_bleue.pdf
Sortie : bleue

Several procedures fit these examples. A program could remove a fixed prefix and extension, extract the text after the first separator, or select a substring by position. These procedures produce the same answers here, but behave differently on other filenames.

Now add another input:

Entrée : archive_facture_verte.pdf
Sortie attendue : verte

This case rules out some hypotheses. Yet it still does not establish what should happen with a different extension, a missing separator, or a name containing several words. Those decisions belong in the specification, even when the interface leaves them unstated.

The synthesizer therefore has to manage ambiguity about intent. It can rank solutions by simplicity, request an example that distinguishes competing interpretations, or present several possibilities. No algorithm can establish the intended behavior with certainty when the available evidence does not distinguish it from other plausible behaviors.

This reasoning appears in Sumit Gulwani’s work on string transformations, published in January 2011. The original paper on programming by example describes a specialized language and a search for programs consistent with the examples. The goal goes beyond generating text: it is to construct a reusable transformation and resolve ambiguity about what that transformation should do.

A history that predates language models

Program synthesis did not begin with coding assistants. One of its historical traditions comes from logic: if a constructive proof establishes that an output satisfying certain conditions exists, that proof can also provide a method for computing it.

Zohar Manna and Richard Waldinger developed this deductive approach. Their account of the foundations of deductive synthesis, published in 1992, explains how to extract a procedure from a sufficiently constructive proof. The intended guarantee concerns an explicit specification, rather than similarity to familiar programs.

Another tradition starts with examples and searches for a rule that explains them. This makes requests easier to express, but generally provides less complete information. Programming by example illustrates the tradeoff: showing a desired transformation may be straightforward, while specifying every exception is harder.

Sketching offers an intermediate approach. A developer provides a partial program and leaves certain choices for the system to resolve automatically. The developer retains part of the strategy, while the synthesizer searches for the missing details.

These traditions coexist. The field’s history is not a simple progression in which neural networks replace logic. Instead, it includes several responses to the same challenge: expressing enough of the requirement and efficiently exploring the possible implementations.

The main families of methods

Methods differ in how they represent candidate programs, search for them, and check their behavior. A single architecture can combine several approaches.

Method	Search principle	Required information	Characteristic limitation
Enumeration	Construct and try permitted programs	Grammar, examples, or properties	Rapid growth in possible combinations
Constraint solving	Encode choices as a logical problem	Semantics and constraints that can be formalized	Complexity and size of the encoding
Constructive deduction	Extract a procedure from a proof	A suitable logical specification	Formalization and proof search
Learning-guided search	Prioritize candidates judged promising	Training data and checks on results	Bias in the learned guide and exploration cost

Enumeration does not necessarily mean blindly trying every possible string of characters. Types can eliminate incompatible combinations, semantics can group equivalent expressions, and intermediate results can be reused across candidates.

Constraint solvers take a different approach: they search for an assignment of choices that makes the conditions satisfiable. Their effectiveness depends heavily on how the problem is formulated. Converting a task into constraints does not automatically make it easy to solve.

Learning supplies priorities for the search. It might suggest a useful operation, a program structure, or a likely way to break the problem down. Such suggestions can reduce the exploration required, but a plausible suggestion does not guarantee correctness.

The practical question remains the same across these methods: what mechanism decides whether a candidate is acceptable, and over what domain does that decision hold?

How counterexamples reshape the search

A central architecture alternates between construction and refutation. The synthesizer proposes a program consistent with the known cases. A verifier then searches for an input on which the program violates the specification. If it finds one, that input becomes an additional constraint.

This loop is called CEGIS, short for counterexample-guided inductive synthesis. Armando Solar-Lezama describes its use in work on program sketching, circulated in 2012 and subsequently published in a journal in 2013.

A counterexample provides more than a negative verdict. It also rules out other candidates that would make the same mistake. The search therefore accumulates information about behaviors to avoid, rather than simply starting over after each failure.

The scope of checking must nevertheless remain explicit. A test observes the result for particular inputs. Bounded verification explores a limited domain, while a proof can establish a general property under stated assumptions. These levels of assurance are not interchangeable.

A specification can also be consistent yet incomplete. A program that satisfies every constraint may still fail to meet the actual requirement if a business rule was left out.

When assessing a result, ask which property was checked, under what assumptions, and within what bounds. Calling a program verified is informative only when those details are available.

What deep learning contributes

The main obstacle is often combinatorial: every additional instruction creates more possible combinations. A network can learn which operations appear useful from the examples, then direct a search engine toward those parts of the program space.

DeepCoder, presented at ICLR in 2017, illustrates this division of work. Its network predicts properties of the target program, including which functions are likely to appear in it. Those predictions guide search techniques. The learned model helps find the program, while the program’s behavior is still evaluated through execution or solving.

Another option is to generate candidates directly, then test and revise them. This uses patterns learned from code and task descriptions. The risk is that the system favors a familiar solution that does not satisfy the current constraints.

It is also useful to distinguish neural program synthesis from neural execution. In the former, a network helps produce a program that is then executed according to explicit rules. In the latter, the network performs the transformation itself, without necessarily providing an inspectable symbolic procedure.

These approaches can complement one another. A learned perception system might identify objects in an image, after which program search determines how to move them. The interface between the two becomes critical, however: a poor initial representation can make the correct rule inaccessible to the search.

Learning abstractions with DreamCoder

A specialized language makes search easier, but its operations are often chosen by hand. If those operations are poorly matched to the tasks, solutions become lengthy or impossible to express. This raises another question: can a system expand its own vocabulary of programs?

DreamCoder, described in a paper submitted in June 2020, combines program search, learning a library of components, and learning a neural guide. Recurring structures in solutions can become reusable abstractions.

The benefit is cumulative. A useful combination that previously had to be reconstructed for every problem becomes an operation available for later tasks. The library changes the search space, while the guide learns how to explore it more effectively.

This mechanism differs from simply storing answers. Reusing an abstraction means applying a structure to new inputs or incorporating it into another combination of operations. Its value depends on what it enables the system to solve afterward.

The approach does not eliminate initial design choices. The system still has a starting language, execution rules, and a learning procedure defined by its designers. A learned library can also become unwieldy or overly specialized.

DreamCoder therefore illustrates a mechanism for acquiring abstractions, rather than demonstrating general intellectual autonomy. Transfer to substantially different domains remains a separate question from progress within the domains studied.

Why program synthesis matters for AGI research

A program can represent a compact rule and apply it to new situations. This makes synthesis relevant to the study of how systems combine knowledge, adapt, and learn from limited examples.

In On the Measure of Intelligence, published in November 2019, François Chollet distinguishes attained skill from the efficiency with which a system acquires new skills. His framework calls for considering prior knowledge, experience, and generalization difficulty.

This perspective directs attention to how a solution is acquired, as well as the result itself. The page on generalization examines this distinction in more detail. Synthesis offers a setting in which to study it because hypotheses can take the form of executable procedures.

Grid transformation tasks, discussed on the ARC-AGI reference page, can involve reasoning about objects, relationships, and operations. Finding a procedure consistent with the demonstrations is one possible way to approach them.

Success alone, however, does not identify the mechanism responsible. A correct answer might come from structured search, recognition of previously learned patterns, or a combination of both. Further experiments are needed to distinguish these explanations.

This page covers the lasting principles. The related article on program synthesis and Ndea’s research direction examines the research project angle.

Disagreements also concern prior knowledge

Researchers disagree about how much structure a system should receive at the outset. Objects, spatial relationships, and predefined operations can make learning easier. They can also steer results toward categories anticipated by the designers.

Richard Sutton argues for a different priority in The Bitter Lesson, published in March 2019: favor general methods of search and learning that can benefit from more computation, rather than accumulating specialized human knowledge.

This position does not rule out program synthesis. Search over a program space can itself be general and guided by learning. The tension arises particularly when success depends on a highly specialized language tailored to the problems being evaluated.

Several questions therefore need to be considered separately: are the primitives written by hand? Is the search guide learned? Can the system invent abstractions? Can it change its representation when its current language is insufficient?

Framing this debate as symbols versus neural networks would obscure hybrid architectures. The disagreement also concerns how useful structure is acquired and the conditions under which it transfers to other tasks.

A cautious approach compares mechanisms on new tasks with documented resources. Neither a theoretical preference nor an isolated result settles which architecture is necessary for AGI.

The limits: representation, cost, and intent

Synthesis assumes that a solution is accessible within the space being searched. If the language cannot express an essential operation, searching longer will not solve the problem. Expanding the language increases its expressive power, but also increases the possibilities to examine.

The choice of representation matters just as much. An image represented as a list of pixels offers different shortcuts from an image represented as a collection of objects. Constructing the right representation can require as much work as discovering the transformation.

A program’s simplicity also depends on the available language. A rule appears short when a primitive already does most of the work. Comparing program lengths therefore requires examining the library and the knowledge it contains.

Cost extends beyond the number of calls to a model. It includes candidates explored, their execution, verification, memory, and any adaptation performed along the way. A result obtained through more extensive search should be reported alongside that resource budget.

Finally, an explicit program is not automatically safe. Its effects can extend beyond the intended transformation if it has access to files or a network. When executing unfamiliar candidates, a sandbox and resource limits help contain those effects during evaluation.

Assessing demonstrations and identifying useful applications

A convincing evaluation must distinguish the examples used to search for solutions from the cases held back to measure performance. It should also document human involvement: choosing primitives, correcting the specification, and making the final selection among candidates.

When reading a paper or examining a prototype, check:

The request: examples alone, a free-form description, or formal properties.
The search space: language, library, and restrictions.
The checking method: tests, counterexample search, or proof.
The resources: computation, time, memory, and human involvement.
The transfer: nearby variations or changes in underlying structure.

The guide to evaluating an AI agent provides a complementary method when synthesis operates within a tool-use loop. An improvement might come from the model, the search engine, or a better verifier. Experiments need to make it possible to distinguish their contributions.

Development assistants such as Codex, Claude Code, and OpenHands operate in a related setting. Their involvement in a programming task does not, by itself, establish that formally verified synthesis is taking place. You need to examine the constraints and checks actually used.

The easiest applications to define have an executable output, a bounded domain, and observable success criteria. As the objective depends more heavily on unstated intent or effects that are difficult to simulate, specification and validation become increasingly central.

Key takeaways

Synthesis constructs a procedure from constraints; its reliability depends on the specification and the checking method.
Deep learning can guide search, propose candidates, and help systems acquire abstractions.
Matching the examples proves neither general correctness nor transfer to other domains.
Synthesis provides useful mechanisms for studying intelligence, without establishing on its own a sufficient path to AGI.

The AGI and research hub places these mechanisms alongside other approaches to learning, reasoning, and evaluation.

Frequently asked questions

How does program synthesis differ from compilation?

A compiler generally translates an existing program into another representation while preserving its behavior. A synthesizer must find an implementation from a description that leaves some choices unresolved. Some tools combine both functions.

Does program synthesis require a language model?

No. It can use program enumeration, constraint solvers, or logical proofs. A learned model can help explore the possibilities, but it is not a requirement.

Are synthesized programs always readable?

No. Readability depends on the programming language, available abstractions, and selection criteria. A compact program can still be difficult to understand if its operations are opaque or its names do not explain their purpose.

Can program synthesis replace developers?

It automates parts of the search for an implementation, but defining requirements, designing the system, and assessing consequences remain separate responsibilities. Its usefulness depends on how precisely the constraints can be expressed and how thoroughly the result can be checked.

Does the ability to write code establish that a system is AGI?

Coding ability is one aspect of evaluation, not a sufficient criterion. Evaluators must also examine how a system acquires new skills, transfers them across domains, and uses resources. Programming performance alone does not answer those questions.

Program synthesis: principles, history, and a possible path to AGI