Research map / Large language models / Agents, code and math

Property-Guided LLM Program Synthesis for Planning

NeurIPS 2026 · Large language models › Agents, code and math · approach: Execution-based code verification · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes property-guided LLM program synthesis: a counterexample-guided repair loop that has an LLM synthesize direct heuristic functions for PDDL planning domains, cutting candidate generations and evaluation cost versus sample-and-select.

Problem

LLM program synthesis relies on numeric scores that give no guidance on why a candidate failed, so many candidates must be generated and evaluated; the paper targets synthesis of heuristics for satisficing planning that are direct (guarantee hill climbing reaches the goal).

Approach

Replace numeric fitness with a formally defined property (direct heuristic) checked by DFS validation that stops at the first violation and returns a concrete counterexample (failing state, its heuristic value, and successor values) to the LLM in a CEGIS-style repair loop.

Key results

• Direct heuristics with hill climbing solve 623.3 of 900 IPC 2023 test tasks, versus 573 for sample-and-select with GBFS and 298 for FF with GBFS.
• The repair loop generates on average 3.4 candidates per run versus a fixed budget of 25 for sample-and-select (about 7.4x fewer), with average evaluation time of 10.75 minutes per domain versus 206.25 CPU-hours reported for the baseline.
• Across 2,700 test evaluations, only one stopped due to a direct-property violation (in Floortile).

Surprising findings

• Coverage-feedback ablation matches sample-and-select under GBFS (572.7 vs 573) but drops to 412.3 under hill climbing, showing numeric feedback does not yield HC-suitable heuristics.
• Sample-and-select heuristics under HC solve only 430 tasks, indicating the gain comes from the direct property rather than the search algorithm.

Limitations

• Property is only checked on a small training set under bounded resources, so test-time directness is not certified.
• Applicable only when a checkable property with informative counterexamples exists; degenerates to score-based ranking otherwise.
• Synthesized unconstrained Python code is harder to interpret and verify than structured heuristic representations.

Experimental setup

Datasets: IPC 2023 Learning Track domains (training and test tasks)

Benchmarks: IPC 2023 Learning Track test tasks (900 tasks, 10 domains)

Metrics: coverage (solved tasks) number of candidate heuristics generated evaluation time state expansions property violation rate at test time

Baselines: FF heuristic sample-and-select coverage-feedback ablation (Cov.)

Builds on: CEGIS sample-and-select heuristic generation (Correa et al. 2025) direct heuristics (wet DDA) descending and dead-end avoiding heuristics

Closest papers by meaning

• Classical Planning with LLM-Generated Heuristics: Challenging the State of the Art with Python Code (NeurIPS 2025 · similarity 0.88)
• HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis (NeurIPS 2024 · similarity 0.87)
• Program Synthesis via Test-Time Transduction (NeurIPS 2025 · similarity 0.87)
• Code Repair with LLMs gives an Exploration-Exploitation Tradeoff (NeurIPS 2024 · similarity 0.87)
• Rethinking Verification for LLM Code Generation: From Generation to Testing (NeurIPS 2025 · similarity 0.86)
• Online Prompt Selection for Program Synthesis (AAAI 2025 · similarity 0.86)