Research map / Large language models / Agents, code and math
Generating Pragmatic Examples to Train Neural Program Synthesizers
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 PraX, which bootstraps a pragmatic neural programming-by-example synthesizer by self-play between neural speaker and listener models with RSA inference used to select informative training examples, requiring no human data.
Problem
Programming-by-example is ambiguous: many programs are consistent with a given set of input-output examples, and exact pragmatic (RSA) reasoning over program and example spaces is intractable for realistic domains like regular expressions.
Approach
Amortize RSA pragmatic inference into neural speaker and listener models by using RSA over sampled consistency matrices to pick informative examples during self-play, then iteratively fine-tune both models on the generated data without human supervision.
Key results
- PraX reaches Top-1@10 of 0.661 vs 0.434 for Literal and 0.587 for HFT in the user study.
- Averaged over 10 turns, PraX Top-1 is 0.373 vs 0.233 for Literal (about 60% relative gain in the reported table, the abstract states 23% absolute, 51% relative), matching HFT at 0.349.
- GPT-3.5 performs worse than the literal model (Top-1@10 0.074).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train with self-play and RSA-selected pragmatic examples instead of randomly chosen examples | ByT5-small regular-expression synthesizer · Regular-expression user study, 10 turns | Top-1@10: 0.434 -> 0.661 | Helped |
| Train with self-play and RSA-selected pragmatic examples instead of randomly chosen examples | ByT5-small regular-expression synthesizer · Regular-expression user study, averaged over 10 turns | Top-1: 0.233 -> 0.373 | Helped |
| Use self-play and RSA-generated examples rather than fine-tuning on human-provided examples | ByT5-small regular-expression synthesizer · Regular-expression user study, 10 turns | Top-1@10: 0.587 -> 0.661 | Helped |
| Use self-play and RSA-generated examples rather than fine-tuning on human-provided examples | ByT5-small regular-expression synthesizer · Regular-expression user study, averaged over 10 turns | Top-1: 0.349 -> 0.373 | No clear effect |
| Use gpt-3.5 instead of the literal synthesizer | Regular-expression synthesizer · Regular-expression user study, 10 turns | Top-1@10: 0.434 -> 0.074 | Hurt |
| Iteratively generate data and update the model rather than generating data and updating only once | PraX regular-expression synthesizer · Regular-expression user study replay | Top-1 | Helped |
Surprising findings
- GPT-3.5 performs substantially worse than the literal neural listener on regex synthesis from examples.
- Speaker loss on human-provided validation examples decreases even without any human data in training.
Limitations
- Evaluated only on regular expression synthesis, not general code.
- User study uses a small number of participants (11 graduate students) and a limited set of regexes.
- Relies on sampled approximations of the consistency matrix rather than exact RSA.
Experimental setup
Datasets: Synthetic regex program-specification pairs sampled from Ye et al. templates Human-provided regex specifications (440 collected; 400 train, 40 validation)
Benchmarks: Regex programming-by-example user study (11 participants, 340 regexes)
Metrics: Top-1@10 Top-10@10 Edit Distance <=1@10 average Top-1 over turns
Baselines: Literal listener HFT (fine-tuned on human-provided specifications) GPT-3.5
Builds on: Rational Speech Acts Pragmatic program synthesis (cooperative game framework) ByT5
Closest papers by meaning
- Program Synthesis with Pragmatic Communication (NeurIPS 2020 · similarity 0.89)
- Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis (ICLR 2018 · similarity 0.88)
- Learning to Combine Per-Example Solutions for Neural Program Synthesis (NeurIPS 2021 · similarity 0.88)
- Learning to Reason via Program Generation, Emulation, and Search (NeurIPS 2024 · similarity 0.86)
- HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis (NeurIPS 2024 · similarity 0.85)
- Programming Every Example: Lifting Pre-training Data Quality Like Experts at Scale (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.