Constrained Adaptive Rejection Sampling - Loris D’Antoni

Loris D’Antoni, Professor of Computer Science and Engineering at UC San Diego, discusses his paper “Constrained Adaptive Rejection Sampling,” which introduces a constrained decoding algorithm that preserves the original language model distribution while satisfying formal constraints, enabling higher-quality structured generation for applications including compiler testing, code generation, and scientific discovery.

Explore how the rise of large language models has reshaped research in programming languages, and how formal methods remain essential for producing software that is both useful and trustworthy in the era of AI-generated code.

In This Episode -

• Program synthesis in the age of LLMs

• Why constrained decoding distorts language model distributions

• Adaptive rejection sampling with remembered failures

• Formal methods for trustworthy AI-generated code

• Compiler fuzzing with language models

• Using symbolic methods to improve LLM output

• Automata theory

• Verified code translation and equivalence checking

References -

• UCSD Programming Systems: https://cseweb.ucsd.edu/groups/progsys/

• Nadia Polikarpova: https://cseweb.ucsd.edu/~npolikarpova/

• Rajeev Alur: https://www.cis.upenn.edu/~alur/

• Code Metal: https://www.codemetal.ai/

About the Paper -

“Constrained Adaptive Rejection Sampling”

Loris D’Antoni, Pavel Parys, Sriram Vadia, Taylor Berg-Kirkpatrick

Large language models often rely on constrained decoding to generate outputs that satisfy grammars or structured schemas, but existing methods can substantially distort the model’s probability distribution. This paper introduces Constrained Adaptive Rejection Sampling (CARS), an algorithm that incrementally learns from rejected samples while provably sampling from the correct constrained distribution, producing significantly higher-quality outputs and large improvements in practical tasks such as compiler fuzzing.

https://arxiv.org/pdf/2510.01902

About the Guest -

Loris D’Antoni is Jacobs Faculty Scholar and Professor of Computer Science and Engineering at the University of California, San Diego, where he leads the Programming Systems Group. His research spans program synthesis, programming languages, formal verification, compiler testing, and trustworthy AI systems, with recent work focusing on combining formal methods with LLMs. He also serves as a Scholar at Code Metal, where he works on verified AI-assisted software engineering.

https://cseweb.ucsd.edu/~ldantoni/

Credits -

• Host & Music: Bryan Landers, Technical Staff, Ndea

• Editor: Alejandro Ramirez

• https://x.com/ndea

• https://x.com/bryanlanders

• https://ndea.com