21 citations · 63 across the 37 of their papers we have counts for
45 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.…
Learning to Reason Efficiently with A* Post-Training
Andreas Opedal, Francesco Ignazio Re, Abulhair Saparov +3
Many applications of large language models (LLMs) require deductive reasoning, yet models frequently produce incorrect or redundant inference steps. We frame natural language infer…
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…
Post-Training Language Models for Crosslingual Consistency
Tianyu Liu, Jirui Qi, Mrinmaya Sachan +3
Language models often respond inconsistently to translation-equivalent prompts across languages, undermining the reliability of multilingual systems. To quantify this, we give an i…
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 -…
Are Language Models Efficient Reasoners? A Perspective from Logic Programming
Andreas Opedal, Yanick Zengaffinen, Haruki Shirakami +5
Modern language models (LMs) exhibit strong deductive reasoning capabilities, yet standard evaluations emphasize correctness while overlooking a key aspect of reasoning: efficiency…
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…
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…
Pointwise Mutual Information as a Performance Gauge for Retrieval-Augmented Generation
Tianyu Liu, Jirui Qi, Paul He +3
Recent work suggests that large language models enhanced with retrieval-augmented generation are easily influenced by the order, in which the retrieved documents are presented to t…
Efficiently Computing Susceptibility to Context in Language Models
Tianyu Liu, Kevin Du, Mrinmaya Sachan +1
One strength of modern language models is their ability to incorporate information from a user-input context when answering queries. However, they are not equally sensitive to the…
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…
What Do Language Models Learn in Context? The Structured Task Hypothesis
Jiaoda Li, Yifan Hou, Mrinmaya Sachan +1
Large language models (LLMs) exhibit an intriguing ability to learn a novel task from in-context examples presented in a demonstration, termed in-context learning (ICL). Understand…
On Affine Homotopy between Language Encoders
Robin SM Chan, Reda Boumasmoud, Anej Svete +8
Pre-trained language encoders -- functions that represent text as vectors -- are an integral component of many NLP tasks. We tackle a natural question in language encoder analysis:…
A Transformer with Stack Attention
Jiaoda Li, Jennifer C. White, Mrinmaya Sachan +1
Natural languages are believed to be (mildly) context-sensitive. Despite underpinning remarkably capable large language models, transformers are unable to model many context-free l…