Is Programming by Example solved by LLMs?
Authors: name: Wen-Ding Li, name: Kevin Ellis

Programming-by-Examples (PBE) aims to generate an algorithm from input-output
examples. Such systems are practically and theoretically important: from an
end-user perspective, they are deployed to millions of people, and from an AI
perspective, PBE corresponds to a very general form of few-shot inductive
inference. Given the success of Large Language Models (LLMs) in code-generation
tasks, we investigate here the extent to which LLMs can be said to have
`solved' PBE. We experiment on classic domains such as lists and strings, and
an uncommon graphics programming domain not well represented in typical
pretraining data. We find that pretrained models are not effective at PBE, but
that they can be fine-tuned for much higher performance, provided the test
problems are in-distribution. We analyze empirically what causes these models
to succeed and fail, and take steps toward understanding how to achieve better
out-of-distribution generalization. Collectively these results suggest that
LLMs make strong progress toward solving the typical suite of PBE tasks,
potentially increasing the flexibility and applicability of PBE systems, while
also identifying ways in which LLMs still fall short.