A formal approach for understanding the behavior of constrained language models

Abstract

We study language models under explicit formal constraints by treating common operations, such as prompting, masking, temperature scaling, and vocabulary translation, as composable transformations, in particular those that preserve the set of generable sequences and/or its probability distribution. We focus on constraints that disable tokens, potentially leading to dead-ends during generation. Moreover, we formalize bounded-length and safe decoding procedures. The theoretical results enable the algorithmic approximation of the probability of subsets (properties) of the generable language, as well as active learning of automata representations, such as DFA o Moore machines. We evaluate the approach to analyze the behavior of several state-of-the-art large language models.