Large Language Model (LLM) Based Synthesis

The model's context window (e.g., 128K tokens) defines the immediate searchable space for synthesis. This window contains the prompt, relevant examples (few-shot learning), and any partial code. Effective synthesis requires strategic context engineering to include:

• Task instructions.
• Relevant API documentation or function signatures.
• Example input-output pairs.
• The partially generated code itself, which the model uses for auto-regressive completion.

A fundamental departure from classical synthesis. LLMs generate plausible code, not provably correct code. There is no built-in formal verification against a specification. Reliability is achieved through:

• Execution and Testing: Running the generated code against test cases.
• Self-Consistency: Sampling multiple programs and selecting the most frequent output.
• Iterative Refinement: Using error messages or failed tests as feedback for re-prompting. This necessitates a robust validation layer in any production system.

Modern systems often combine LLMs' generative power with symbolic tools to enhance correctness, creating a neurosymbolic architecture. Common integrations include:

• Code Executors: To validate output via unit tests.
• Static Analyzers & Linters: To catch syntactic errors and enforce style.
• Formal Verifiers & SMT Solvers: To check generated code against formal properties, often in a Counterexample-Guided Inductive Synthesis (CEGIS)-like loop.
• Parser Filters: To ensure generated code is syntactically valid before execution.

While general-purpose models (e.g., GPT-4, CodeLlama) work well, domain-specific fine-tuning dramatically improves performance for specialized tasks. This involves continued training on curated datasets of:

• Code in a specific language or framework (e.g., Solidity for smart contracts).
• Paired natural language bug reports and patches for program repair.
• SQL queries and corresponding natural language questions. Techniques like Parameter-Efficient Fine-Tuning (PEFT), including LoRA, are commonly used to adapt massive models cost-effectively.

A classic synthesis paradigm where the specification is a set of concrete input-output pairs. The synthesizer's goal is to infer a general program that produces the correct output for all given inputs. Key systems include:

• FlashFill: Integrated into Microsoft Excel to synthesize string transformations from cell examples.
• Prosper: A tool for synthesizing data structure manipulations.

LLM-based synthesis can implement PBE through few-shot prompting, where input-output examples are provided in the prompt to guide the model. However, traditional PBE systems often use deductive search algorithms (like version space algebra) that guarantee correctness for the provided examples, a formal guarantee most LLMs lack.

A hybrid architecture that combines the strengths of neural networks and symbolic reasoning. In this paradigm:

• The neural component (often an LLM) handles ambiguous, noisy, or unstructured inputs (like natural language) and proposes candidate program sketches or components.
• The symbolic component (a verifier, solver, or interpreter) checks logical correctness, performs constrained search, and provides formal guarantees.

This approach mitigates key LLM weaknesses like hallucination and lack of verifiable correctness. The LLM acts as a powerful, flexible proposer, while symbolic tools ensure the final output is semantically valid.

A technique where the user provides a partial program (a sketch) containing "holes" (syntactic placeholders) that specify the program's high-level structure. The synthesizer's job is to fill these holes with concrete code fragments to satisfy a formal specification. For example:

pythonCopy
# Sketch with hole `??`
def max(list):
    result = list[0]
    for i in range(1, len(list)):
        result = ??  # Synthesizer must fill this expression
    return result

LLMs excel at sketch completion when the sketch and intent are provided in the prompt. This creates a powerful collaborative workflow: engineers define the structure and invariants, and the LLM fills in the implementation details.

The broadest category of automatically producing source code. It encompasses:

• Program Synthesis: Generating code from a specification (the goal is correctness).
• Template-Based Generation: Filling in code skeletons (e.g., scaffolding from tools like Cookiecutter).
• AI-Powered Code Completion: Real-time suggestions within an IDE (e.g., GitHub Copilot, Tabnine).

LLM-based synthesis is a form of code generation with a focus on creating novel, task-specific code from a non-code specification. It is distinct from simple completion, as it often involves multi-step reasoning to understand the goal and generate a complete, coherent program unit (function, class, script).