Clemente Pasti

I am a computer science PhD student at ETH Zürich, supervised by Ryan Cotterell and Michael Hahn. I am interested in understanding the cognitive functioning of language models — how they reason, and how this resembles or differs from human cognition. I am also drawn to formal language theory and probabilistic methods, which I also happen to use as tools to better understand language models. I am currently on a 1-year leave at CHI-FRO, where I am working on controlled generation and (probabilistic) program synthesis as part of the genlm project.

Before my PhD, I was an MSc student in CS at USI, in Lugano, and before that I was a BSc student in Mathematical Engineering, at Politecnico di Milano in Italy, my home country. Beyond mathematics and computer science, I am very much interested in philosophy and particularly in idealism, structuralism and the continental tradition in general. I am also very passionate about sports, including running (I used to run the 800 meters during high school), rowing and skiing.

Publications

2026

Prefix Parsing is Just Parsing

Clemente Pasti, Andreas Opedal, Timothy J. O’Donnell, and 2 more authors

In Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics, 2026

Abs

Prefix parsing asks whether a given input prefix can be extended to a complete string in a context-free language. We introduce a prefix grammar transformation that efficiently reduces this problem to ordinary parsing: the transformed grammar generates exactly the prefixes of the original language, so any standard parsing algorithm can solve prefix parsing without modification. The construction keeps the transformed grammar only marginally larger than the input, and we further give an algorithmic differentiation strategy for computing next-token weight vectors. The result is a simple, general, and efficient framework for prefix parsing applicable across parsing implementations.
Ensembling Language Models with Sequential Monte Carlo

Robin Shing Moon Chan, Tianyu Liu, Samuel Kiegeland, and 5 more authors

In arXiv preprint arXiv:2603.05432, 2026

Abs

Naively averaging the next-token probabilities of multiple language models produces biased approximations of natural ensemble distributions. We propose a unified framework for forming ensemble distributions using flexible aggregation functions, and present a byte-level sequential Monte Carlo algorithm that operates in a shared character space, enabling principled combination of models with different vocabularies. Across structured text generation tasks, alternative aggregation strategies outperform standard probability averaging, and we show that better posterior approximations drive these gains.

2025

Are Language Models Efficient Reasoners? A Perspective from Logic Programming

Andreas Opedal, Yanick Zengaffinen, Haruki Shirakami, and 5 more authors

In Advances in Neural Information Processing Systems 38, 2025

Abs

Modern language models display strong deductive reasoning, yet standard evaluations focus on correctness while overlooking efficiency. In real-world reasoning, much of the available information is irrelevant, and effective deduction requires identifying and ignoring such distractions. We propose a framework for assessing LM reasoning efficiency through the lens of logic programming, introducing a method to align proofs written in natural language—as generated by an LM—with shortest proofs found by executing the logic program. We find that current LMs exhibit marked accuracy declines when presented with irrelevant axioms—even minimal, domain-consistent distractions—and that their generated proofs frequently include detours through irrelevant inferences.
Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo

João Loula, Benjamin LeBrun, Li Du, and 12 more authors

In The Thirteenth International Conference on Learning Representations, 2025

Abs

A wide range of LM applications require generating text that conforms to syntactic or semantic constraints. Imposing such constraints can be naturally framed as probabilistic conditioning, but exact generation from the resulting distribution—which can differ substantially from the LM’s base distribution—is generally intractable. In this work, we develop an architecture for controlled LM generation based on sequential Monte Carlo (SMC). Our SMC framework allows us to flexibly incorporate domain- and problem-specific constraints at inference time, and efficiently reallocate computational resources in light of new information during the course of generation. By comparing to a number of alternatives and ablations on four challenging domains—Python code generation for data science, text-to-SQL, goal inference, and molecule synthesis—we demonstrate that, with little overhead, our approach allows small open-source language models to outperform models over 8 larger, as well as closed-source, fine-tuned ones. In support of the probabilistic perspective, we show that these performance improvements are driven by better approximation to the posterior distribution. Our system builds on the framework of Lew et al. (2023) and integrates with its language model probabilistic programming language, giving users a simple, programmable way to apply SMC to a broad variety of controlled generation problems.

2024

Computational Expressivity of Neural Language Models

Alexandra Butoi, Robin Chan, Ryan Cotterell, and 5 more authors

In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 5: Tutorial Abstracts), 2024

Abs

Language models are currently at the forefront of NLP research due to their remarkable versatility across diverse tasks. However, a large gap exists between their observed capabilities and the explanations proposed by established formal machinery. This tutorial provides a comprehensive introduction to a framework for the formal analysis of modern LMs using tools from formal language theory (FLT), showing how FLT can clarify the inner workings and predict the capabilities of modern neural LM architectures.
An L* Algorithm for Deterministic Weighted Regular Languages

Clemente Pasti, Talu Karagöz, Franz Nowak, and 3 more authors

In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, Nov 2024

Abs DOI

Extracting finite state automata (FSAs) fromblack-box models offers a powerful approachto gaining interpretable insights into complexmodel behaviors. To support this pursuit, wepresent a weighted variant of Angluin’s (1987)L* algorithm for learning FSAs. We stay faithful to the original formulation, devising a wayto exactly learn deterministic weighted FSAswhose weights support division. Furthermore,we formulate the learning process in a mannerthat highlights the connection with FSA minimization, showing how L* directly learns aminimal automaton for the target language.

2023

On the Intersection of Context-Free and Regular Languages

Clemente Pasti, Andreas Opedal, Tiago Pimentel, and 3 more authors

In Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics, May 2023

Abs DOI

The Bar-Hillel construction is a classic result in formal language theory. It shows, by a simple construction, that the intersection of a context-free language and a regular language is itself context-free. In the construction, the regular language is specified by a finite-state automaton. However, neither the original construction (Bar-Hillel et al., 1961) nor its weighted extension (Nederhof and Satta, 2003) can handle finite-state automata with \ensuremath\varepsilon-arcs. While it is possible to remove \ensuremath\varepsilon-arcs from a finite-state automaton efficiently without modifying the language, such an operation modifies the automaton’s set of paths. We give a construction that generalizes the Bar- Hillel in the case the desired automaton has \ensuremath\varepsilon-arcs, and further prove that our generalized construction leads to a grammar that encodes the structure of both the input automaton and grammar while retaining the asymptotic size of the original construction.