2 citations · 7 across the 24 of their papers we have counts for
31 papers · 1 filter
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…
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…
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 Weighted Pushdown Automata
Alexandra Butoi, Brian DuSell, Tim Vieira +2
Weighted pushdown automata (WPDAs) are at the core of many natural language processing tasks, like syntax-based statistical machine translation and transition-based dependency pars…
Exact Paired-Permutation Testing for Structured Test Statistics
Ran Zmigrod, Tim Vieira, Ryan Cotterell
Significance testing -- especially the paired-permutation test -- has played a vital role in developing NLP systems to provide confidence that the difference in performance between…
Searching for More Efficient Dynamic Programs
Tim Vieira, Ryan Cotterell, Jason Eisner
Computational models of human language often involve combinatorial problems. For instance, a probabilistic parser may marginalize over exponentially many trees to make predictions.…
Conditional Poisson Stochastic Beam Search
Clara Meister, Afra Amini, Tim Vieira +1
Beam search is the default decoding strategy for many sequence generation tasks in NLP. The set of approximate K-best items returned by the algorithm is a useful summary of the dis…
Efficient Sampling of Dependency Structures
Ran Zmigrod, Tim Vieira, Ryan Cotterell
Probabilistic distributions over spanning trees in directed graphs are a fundamental model of dependency structure in natural language processing, syntactic dependency trees. In NL…