Efficient Pragmatic Program Synthesis with Informative Specifications
This work addresses the challenge of making program synthesis more efficient and aligned with human pragmatic communication, though it is incremental as it builds on prior pragmatic models.
The paper tackles the problem of inefficient pragmatic program synthesis by approximating the joint distribution of programs with a factored model, enabling efficient inference. The synthesizer using this approximation outperforms exact methods on human inputs, suggesting humans may use similar factored distributions.
Providing examples is one of the most common way for end-users to interact with program synthesizers. However, program synthesis systems assume that examples consistent with the program are chosen at random, and do not exploit the fact that users choose examples pragmatically. Prior work modeled program synthesis as pragmatic communication, but required an inefficient enumeration of the entire program space. In this paper, we show that it is possible to build a program synthesizer that is both pragmatic and efficient by approximating the joint distribution of programs with a product of independent factors, and performing pragmatic inference on each factor separately. This factored distribution approximates the exact joint distribution well when the examples are given pragmatically, and is compatible with a basic neuro-symbolic program synthesis algorithm. Surprisingly, we find that the synthesizer assuming a factored approximation performs better than a synthesizer assuming an exact joint distribution when evaluated on natural human inputs. This suggests that humans may be assuming a factored distribution while communicating programs.