Sampling from Language Models under Syntactic Constraints

Speaker(s)

Paweł Parys

Affiliation

University of Warsaw

Language of the talk

English

Date

Nov. 5, 2025, 2:15 p.m.

Room

room 5440

Title in Polish

Sampling from Language Models under Syntactic Constraints

Seminar

Seminar Automata Theory

---

In recent years, large language models (LLMs) have revolutionized code writing. Using LLMs, one can quickly arrive at solutions that are close to the correct answer for many tasks, though mistakes still occur frequently. However, in some cases, we have formal syntactic or even semantic constraints on the code to be generated. Can we account for these constraints while generating code from an LLM?

In this work, we treat the language model as a black-box, returning conditional probabilities of the next tokens. We will not discuss the internal construction of LLMs. Rather, this talk focuses on sampling from appropriate distributions and efficient parsing techniques.

This is joint work with Sairam Vaidya, Taylor Berg-Kirkpatrick, Loris D'Antoni, and others.

---