publications

2026

1. 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.

2. 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

1. 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.

2. 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.

3. Language Models over Canonical Byte-Pair Encodings

   Tim Vieira, Tianyu Liu, Clemente Pasti, and 8 more authors

   In Forty-second International Conference on Machine Learning, 2025

   Abs

   Modern language models represent probability distributions over character strings as distributions over (shorter) token strings derived via a deterministic tokenizer, such as byte-pair encoding. While this approach is highly effective at scaling up language models to large corpora, its current incarnations have a concerning property: the model assigns nonzero probability mass to an exponential number of noncanonical token encodings of each character string – these are token strings that decode to valid character strings but are impossible under the deterministic tokenizer (i.e., they will never be seen in any training corpus, no matter how large). This misallocation is both erroneous, as noncanonical strings never appear in training data, and wasteful, diverting probability mass away from plausible outputs. These are avoidable mistakes! In this work, we propose methods to enforce canonicality in token-level language models, ensuring that only canonical token strings are assigned positive probability. We present two approaches: (1) canonicality by conditioning, leveraging test-time inference strategies without additional training, and (2) canonicality by construction, a model parameterization that guarantees canonical outputs but requires training. We demonstrate that fixing canonicality mistakes improves the likelihood of held-out data for several models and corpora.

2024

1. 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.

2. 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

1. 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.