Trace-Guided Program Synthesis Using Large Language Model Priors

Abstract

Learning from Demonstration allows robot behaviour to be specified by examples rather than manual programming, but demonstrations are often noisy and provide limited structure for efficient search. Framing the problem as program synthesis allows us to search for programs that follow the demonstrated behaviour, but enumerative synthesis suffers from an enormous search space and inefficient exploration. Recent work shows that large language models (LLMs) can guide synthesis by providing probabilistic priors over program structure, though such methods typically ignore execution traces and structural depth. In this thesis, we propose a synthesis framework that combines LLM-guided probabilistic grammars with trace-based feedback and depth-sensitive costs. We derive a depth-aware probabilistic grammar from LLM-generated programs, guide bottom-up enumeration using the induced costs, and dynamically update rule probabilities based on how closely candidate programs follow demonstrated execution traces. The results show that the effectiveness of LLM guidance and trace-based feedback depends on structural depth: while LLM priors mainly improve reachability in depth-agnostic settings, trace-based updates performs better when depthaware costs are used, and their combination yields the strongest gains in search efficiency.