PAC Prediction Sets for Large Language Models of Code
Adam Khakhar, Stephen Mell, Osbert Bastani
Abstract
Prediction sets have recently been shown to be a promising strategy for quantifying the uncertainty of deep neural networks in a way that provides theoretical guarantees. However, existing techniques have largely targeted settings where the space of labels is simple, so prediction sets can be arbitrary subsets of labels. For structured prediction problems where the space of labels is exponential in size, even prediction sets containing a small fraction of all labels can be exponentially large. In the context of code generation, we propose a solution that considers a restricted set of prediction sets that can compactly be represented as partial programs, which are programs with portions replaced with holes. Given a trained code generation model, our algorithm leverages a programming language's abstract syntax tree to generate a set of programs such that the correct program is in the set with high-confidence. Valuable applications of our algorithm include a Codex-style code generator with holes in uncertain parts of the generated code, which provides a partial program with theoretical guarantees. We evaluate our approach on PICARD (a T5 model for SQL semantic parsing) and Codex (a GPT model for over a dozen programming languages, including Python), demonstrating that our approach generates compact PAC prediction sets. This is the first research contribution that generates PAC prediction sets for generative code models. 1
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Conformal Structured Prediction cites Uncertainty Sets for Image Classifiers using Conformal Prediction
- Conformal Structured Prediction cites PAC Confidence Sets for Deep Neural Networks via Calibrated Prediction
- Uncertainty Sets for Image Classifiers using Conformal Prediction cites PAC Confidence Sets for Deep Neural Networks via Calibrated Prediction
Cited by top-tier papers1
Builds on5
- Language Models are Few-Shot LearnersTom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah et al.NeurIPS 2020 · 64,255 citations
- PAC Confidence Sets for Deep Neural Networks via Calibrated PredictionSangdon Park, Osbert Bastani, Nikolai Matni, Insup LeeICLR 2020 · 77 citations
- Learning to Complete Code with SketchesDaya Guo, Alexey Svyatkovskiy, Jian Yin, Nan Duan et al.ICLR 2022 · 42 citations
- Autoregressive Structured Prediction with Language ModelsTianyu Liu, Yuchen Eleanor Jiang, Nicholas Monath, Ryan Cotterell et al.EMNLP Findings 2022 · 33 citations
- Uncertainty Sets for Image Classifiers using Conformal PredictionAnastasios Nikolas Angelopoulos, Stephen Bates, Michael I. Jordan, Jitendra MalikICLR 2021 · 31 citations
Related papers
- R-U-SURE? Uncertainty-Aware Code Suggestions By Maximizing Utility Across Random User IntentsDaniel D. Johnson, Daniel Tarlow, Christian WalderICML 2023 · 11 citations
- Language Models of Code are Few-Shot Commonsense LearnersAman Madaan, Shuyan Zhou, Uri Alon, Yiming Yang et al.EMNLP 2022 · 103 citations
- Searching a Database of Source Codes Using Contextualized Code SearchRohan Mukherjee, Chris Jermaine, Swarat ChaudhuriVLDB 2020 · 11 citations
- Improving Uncertainty Quantification of Deep Classifiers via Neighborhood Conformal Prediction: Novel Algorithm and Theoretical AnalysisSubhankar Ghosh, Taha Belkhouja, Yan Yan, Janardhan Rao DoppaAAAI 2023 · 30 citations
- TreeCoder: Systematic Exploration and Optimisation of Decoding and Constraints for LLM Code GenerationHenrijs Princis, Arindam Sharma, Cristina DavidPLDI 2026
