2 citations · 7 across the 24 of their papers we have counts for
38 papers
Estimating Great Expectations Under Autoregressive Language Models with Potentials
Francesco I. Re, Shubhangi Ghosh, Tim Vieira +1
Many applications of language models require estimating the expectation of a test functional under the model. Obtaining precise estimates can be computationally expensive. We show…
Stochastic Estimation of Transduced Language Models
Vésteinn Snæbjarnarson, Samuel Kiegeland, Manuel de Prada Corral +2
Transduced language models (TLMs) compose a pretrained \emph{source} language model with a functional finite-state transducer to induce a language model over \emph{target} strings.…
On the Proper Treatment of Units in Surprisal Theory
Samuel Kiegeland, Vésteinn Snæbjarnarson, Tim Vieira +1
Surprisal theory links human processing effort to the predictability of an upcoming linguistic unit, but empirical work often leaves the notion of a unit underspecified. In practic…
Prefix Parsing is Just Parsing
Clemente Pasti, Andreas Opedal, Timothy J. O'Donnell +2
Prefix parsing asks whether an input prefix can be extended to a complete string generated by a given grammar. In the weighted setting, it also provides prefix probabilities, which…
Faster LLM Inference via Sequential Monte Carlo
Yahya Emara, Mauricio Barba da Costa, Chi-Chih Chang +4
Speculative decoding (SD) accelerates language model inference by drafting tokens from a cheap proposal model and verifying them against an expensive target model via rejection sam…
Ensembling Language Models with Sequential Monte Carlo
Robin Shing Moon Chan, Tianyu Liu, Samuel Kiegeland +5
Practitioners have access to an abundance of language models and prompting strategies for solving many language modeling tasks; yet prior work shows that modeling performance is hi…
Transducing Language Models
Vésteinn Snæbjarnarson, Samuel Kiegeland, Tianyu Liu +3
Modern language models define distributions over strings, but downstream tasks often require different output formats. For instance, a model that generates byte-pair strings does n…
Automating the Analysis and Improvement of Dynamic Programming Algorithms with Applications to Natural Language Processing
Tim Vieira
This thesis develops a system for automatically analyzing and improving dynamic programs, such as those that have driven progress in natural language processing and computer scienc…
Automating the Analysis of Parsing Algorithms (and other Dynamic Programs)
Tim Vieira, Ryan Cotterell, Jason Eisner
Much algorithmic research in NLP aims to efficiently manipulate rich formal structures. An algorithm designer typically seeks to provide guarantees about their proposed algorithm -…
Language Models over Canonical Byte-Pair Encodings
Tim Vieira, Tianyu Liu, Clemente Pasti +7
Modern language models represent probability distributions over character strings as distributions over (shorter) token strings derived via a deterministic tokenizer, such as byte-…
Syntactic Control of Language Models by Posterior Inference
Vicky Xefteri, Tim Vieira, Ryan Cotterell +1
Controlling the syntactic structure of text generated by language models is valuable for applications requiring clarity, stylistic consistency, or interpretability, yet it remains…
Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo
João Loula, Benjamin LeBrun, Li Du +12
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 condi…
Better Estimation of the Kullback--Leibler Divergence Between Language Models
Afra Amini, Tim Vieira, Ryan Cotterell
Estimating the Kullback--Leibler (KL) divergence between language models has many applications, e.g., reinforcement learning from human feedback (RLHF), interpretability, and knowl…
Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling
Benjamin Lipkin, Benjamin LeBrun, Jacob Hoover Vigly +9
The dominant approach to generating from language models subject to some constraint is locally constrained decoding (LCD), incrementally sampling tokens at each time step such that…
From Language Models over Tokens to Language Models over Characters
Tim Vieira, Ben LeBrun, Mario Giulianelli +5
Modern language models are internally -- and mathematically -- distributions over strings rather than strings, posing numerous challenges for programm…
On the Proper Treatment of Tokenization in Psycholinguistics
Mario Giulianelli, Luca Malagutti, Juan Luis Gastaldi +3
Language models are widely used in computational psycholinguistics to test theories that relate the negative log probability (the surprisal) of a region of interest (a substring of…
The Foundations of Tokenization: Statistical and Computational Concerns
Juan Luis Gastaldi, John Terilla, Luca Malagutti +3
Tokenization - the practice of converting strings of characters from an alphabet into sequences of tokens over a vocabulary - is a critical step in the NLP pipeline. The use of tok…
Variational Best-of-N Alignment
Afra Amini, Tim Vieira, Elliott Ash +1
Best-of-N (BoN) is a popular and effective algorithm for aligning language models to human preferences. The algorithm works as follows: at inference time, N samples are drawn from…
Direct Preference Optimization with an Offset
Afra Amini, Tim Vieira, Ryan Cotterell
Direct preference optimization (DPO) is a successful fine-tuning strategy for aligning large language models with human preferences without the need to train a reward model or empl…
An Exploration of Left-Corner Transformations
Andreas Opedal, Eleftheria Tsipidi, Tiago Pimentel +2
The left-corner transformation (Rosenkrantz and Lewis, 1970) is used to remove left recursion from context-free grammars, which is an important step towards making the grammar pars…
Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages
Alexandra Butoi, Tim Vieira, Ryan Cotterell +1
The class of tree-adjoining languages can be characterized by various two-level formalisms, consisting of a context-free grammar (CFG) or pushdown automaton (PDA) controlling anoth…
Efficient Semiring-Weighted Earley Parsing
Andreas Opedal, Ran Zmigrod, Tim Vieira +2
This paper provides a reference description, in the form of a deduction system, of Earley's (1970) context-free parsing algorithm with various speed-ups. Our presentation includes…
A Formal Perspective on Byte-Pair Encoding
Vilém Zouhar, Clara Meister, Juan Luis Gastaldi +4
Byte-Pair Encoding (BPE) is a popular algorithm used for tokenizing data in NLP, despite being devised initially as a compression method. BPE appears to be a greedy algorithm at fa…
Algorithms for Acyclic Weighted Finite-State Automata with Failure Arcs
Anej Svete, Benjamin Dayan, Tim Vieira +2
Weighted finite-state automata (WSFAs) are commonly used in NLP. Failure transitions are a useful extension for compactly representing backoffs or interpolation in -gram models…