Review: LLM-Guided Compositional Program Synthesis

Below is a “cheat-sheet” of the core equations/definitions you’ll want to be comfortable with plus a narrative of the main control-flow (loops) inside SYMLLM’s synthesizer.

1 ️⃣ Equations & formal definitions that matter

Why these six? Everything that happens later—prompt engineering, verification, evaluation metrics—relies on this small algebra of example sets and function composition.

2 ️⃣ Control-flow / “loops” inside the synthesizer

2.1 High-level outer loop (Figure 1, p. 3)

1. Generate a candidate program (F) with one LLM call.
2. Verify (F) on all training pairs.
3. If failure, iterate over up to four strategy branches in this order:
   1. Forward-1
   2. Forward-All
   3. Backward-1
   4. If-Then-Else The first branch that returns a verified program halts the loop.
4. (Optional) Self-reflection could wrap around the whole procedure, but in the paper they cap recursion depth at 1 for cost.

Think of this as a for-loop over strategies with early-exit on success.

2.2 Inner loops per strategy

| Strategy | Loop-like behaviour | |———-|——————–| | Forward-1 / Forward-All | Single LLM call to build (F’) on the derived (\text{Ex}’). No further iteration—just verify once. | | Backward-1 | (a) Loop over LLM samples when inverse-executing (prompt asks for multiple candidate ((v_a,v_b))). (b) For each surviving pair, two sub-tasks are issued in parallel; failure of either kills the branch. | | If-Then-Else | Three fixed calls: 1️⃣ learn (F_1) 2️⃣ learn (F_2) 3️⃣ learn condition (c). Only if (c) classifies all seen examples correctly does the branch succeed. |

2.3 Verification loop

Every LLM-produced fragment is executed over the training examples. This acts as a fast rejection loop that cuts off hallucinated code before composition. (§3 last paragraph)

3 ️⃣ How the loops realise the paper’s logic

1. Exploit partial correctness early – Prefix/suffix salvage means the first wrong attempt is never wasted; its correct bits seed sub-tasks.
2. Bounded exploration – By limiting to one LLM attempt per sub-task (and depth = 1) the algorithm keeps latency predictable (~2–6 calls total).
3. Soundness by checking, not by proof – Instead of logical inference loops (à-la SyGuS), the only loop needed is “run on examples; did it pass?”—simple yet effective.

TL;DR

Learn equations (E1)–(E6); they’re the algebraic backbone linking examples to decomposed tasks. Understand the outer “try-four-strategies” loop and the per-strategy micro-loops; together they form SYMLLM’s lightweight yet surprisingly potent control-flow for repairing LLM-generated programs.

Below are three battle-tested “levels of abstraction” you can adopt, plus plug-ins and libraries that cover every moving part of SYMLLM (LLM calls → AST → data-flow → sandbox → verification).

Must-have helper libraries

Minimal “hello-SYMLLM” scaffold (pure Python ≈ 120 LOC)

import openai, ast, networkx as nx, textwrap
from verifier import verify_examples           # your sandbox runner
from decompose import forward1, backward1      # your prefix/suffix logic

EXAMPLES = [...]                               # load Playgol split
prompt_init  = PROMPT_TEMPL.format(ex=EXAMPLES)
code0        = openai.chat.completions.create(...).choices[0].message.content

if verify_examples(code0, EXAMPLES):
    return code0                               # solved first-shot

for strategy in (forward1, forward_all, backward1, if_then_else):
    sub_codes = strategy(code0, EXAMPLES)      # 1–3 more LLM calls inside
    final     = compose(code0, *sub_codes)
    if verify_examples(final, EXAMPLES):
        return final

(Replace each ellipsis with the paper’s prompt wording.)

Once this works for Python Playgol, you can swap in LangChain or AutoGen without touching the synthesis logic—just move each box into a Chain or an Agent.

Tips when choosing a framework

1. Start flat, then climb the abstraction ladder. Most bugs in SYMLLM are parsing- or sandbox-related; frameworks can’t fix those but can add noise. Get a vanilla script passing 10–20 benchmarks first.

2. Pick **LangChain if you need observability** (built-in tracing dashboards) or quick-swap vector-store / RAG tricks.

3. Pick **Semantic Kernel if you’re already on .NET/Java**—its “skills” mirror the four strategies almost verbatim, and SK ships with guarded code-executor plugins.

4. Pick **AutoGen to explore future work** the authors mention (agentic recursion, multi-agent debate).

5. LLM model swap is orthogonal. All three frameworks let you drop‐in GPT-4-o, Azure OpenAI, Claude 3, or local Llama-3-70B; keep an env-var-driven provider layer.

Quick links

• AutoGen GitHub – high-level agent framework, Python 3.10+ (microsoft/autogen: A programming framework for agentic AI … - GitHub)

• LangChain docs – chains, tools, LangGraph state-machines ([Introduction

  🦜️ LangChain](https://python.langchain.com/docs/introduction/?utm_source=chatgpt.com))

• Semantic Kernel starters – ready-made Python & .NET templates (microsoft/semantic-kernel-starters - GitHub)
• LlamaIndex – optional RAG layer if you add retrieval hints to prompts (LlamaIndex - Build Knowledge Assistants over your Enterprise Data)

TL;DR

For a faithful re-implementation, pure Python + openai + a custom AST pass is fastest. If you want batteries-included orchestration, choose LangChain (single agent) or AutoGen (multi-agent). All three paths share the same core: “one LLM call → verify → (maybe) decompose → compose → verify”.