# Amortizing Pragmatic Program Synthesis with Rankings

arXiv: https://arxiv.org/abs/2309.03225 · HTML: https://mlsanity.com/paper/2309.03225/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 40 references that are in the map.
- First posted on arXiv 1 Sep 2023.

## Builds on (most cited first, 18 of 18)

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Speaker-Follower Models for Vision-and-Language Navigation](https://mlsanity.com/paper/1806.02724/) (2018)
- [DeepCoder: Learning to Write Programs](https://mlsanity.com/paper/1611.01989/) (2016)
- [Reasoning About Pragmatics with Neural Listeners and Speakers](https://mlsanity.com/paper/1604.00562/) (2016)
- [Colors in Context: A Pragmatic Neural Model for Grounded Language Understanding](https://mlsanity.com/paper/1703.10186/) (2017)
- [Unified Pragmatic Models for Generating and Following Instructions](https://mlsanity.com/paper/1711.04987/) (2017)
- [Inferring Rewards from Language in Context](https://mlsanity.com/paper/2204.02515/) (2022)
- [Pragmatically Informative Image Captioning with Character-Level Inference](https://mlsanity.com/paper/1804.05417/) (2018)
- [A mathematical theory of cooperative communication](https://mlsanity.com/paper/1910.02822/) (2019)
- [Learning in the Rational Speech Acts Model](https://mlsanity.com/paper/1510.06807/) (2015)
- [Program Synthesis with Pragmatic Communication](https://mlsanity.com/paper/2007.05060/) (2020)
- [Reference-Centric Models for Grounded Collaborative Dialogue](https://mlsanity.com/paper/2109.05042/) (2021)
- [An Incremental Iterated Response Model of Pragmatics](https://mlsanity.com/paper/1810.00367/) (2018)
- [Neural Program Search: Solving Programming Tasks from Description and Examples](https://mlsanity.com/paper/1802.04335/) (2018)
- [The Usability of Pragmatic Communication in Regular Expression Synthesis](https://mlsanity.com/paper/2308.06656/) (2023)
- [Efficient Pragmatic Program Synthesis with Informative Specifications](https://mlsanity.com/paper/2204.02495/) (2022)

## Abstract (arXiv)

In program synthesis, an intelligent system takes in a set of user-generated examples and returns a program that is logically consistent with these examples. The usage of Rational Speech Acts (RSA) framework has been successful in building pragmatic program synthesizers that return programs which -- in addition to being logically consistent -- account for the fact that a user chooses their examples informatively. However, the computational burden of running the RSA algorithm has restricted the application of pragmatic program synthesis to domains with a small number of possible programs. This work presents a novel method of amortizing the RSA algorithm by leveraging a global pragmatic ranking -- a single, total ordering of all the hypotheses. We prove that for a pragmatic synthesizer that uses a single demonstration, our global ranking method exactly replicates RSA's ranked responses. We further empirically show that global rankings effectively approximate the full pragmatic synthesizer in an online, multi-demonstration setting. Experiments on two program synthesis domains using our pragmatic ranking method resulted in orders of magnitudes of speed ups compared to the RSA synthesizer, while outperforming the standard, non-pragmatic synthesizer.