capbtabboxtable[][]

#  Collie: Systematic Construction of
Constrained Text Generation Tasks

Shunyu Yao111Equal contribution. Project site with code and data:
https://collie-benchmark.github.io. Collie is a herding dog that can help
guide domesticated animals like llamas and alpacas. Howard Chen111Equal
contribution. Project site with code and data: https://collie-
benchmark.github.io. Collie is a herding dog that can help guide domesticated
animals like llamas and alpacas. Austin W. Hanjie111Equal contribution.
Project site with code and data: https://collie-benchmark.github.io. Collie is
a herding dog that can help guide domesticated animals like llamas and
alpacas. Runzhe Yang111Equal contribution. Project site with code and data:
https://collie-benchmark.github.io. Collie is a herding dog that can help
guide domesticated animals like llamas and alpacas. Karthik Narasimhan
Department of Computer Science, Princeton University
{shunyuy, hc22, hjwang, runzhey<EMAIL_ADDRESS>
###### Abstract

Text generation under constraints have seen increasing interests in natural
language processing, especially with the rapidly improving capabilities of
large language models. However, existing benchmarks for constrained generation
usually focus on fixed constraint types (e.g. generate a sentence containing
certain words) that have proved to be easy for state-of-the-art models like
GPT-4. We present Collie, a grammar-based framework that allows the
specification of rich, compositional constraints with diverse generation
levels (word, sentence, paragraph, passage) and modeling challenges (e.g.
language understanding, logical reasoning, counting, semantic planning). We
also develop tools for automatic extraction of task instances given a
constraint structure and a raw text corpus. Using Collie, we compile the
Collie-v1 dataset with 2,080 instances comprising 13 constraint structures. We
perform systematic experiments across five state-of-the-art instruction-tuned
language models and analyze their performances to reveal shortcomings. Collie
is designed to be extensible and lightweight, and we hope the community finds
it useful to develop more complex constraints and evaluations in the future.

##  1 Introduction

Large language models (LLMs) have proven to be extremely capable of generating
coherent and fluent text when provided with high-level prompts, performing
excellently on popular benchmarks [35] and finding use in production systems
such as GPT-4 [28]. Such capabilities have raised the bar for automated text
generation, and allow us to explore more nuanced ways of utilizing LMs to
produce text. One such line of inquiry has been the paradigm of constrained
text generation, whereby the LM can be asked to adhere to a particular topic
[19, 9], or avoid using certain words [26, 27]. However, these works are
scratching the surface of a broader phenomenon — language models are not just
about purely generating text anymore, as evidenced by their use in more
structured tasks like problem solving [38], code generation [6] and even tool
use through API calls [32].

This raises a natural question — ‘what should be the next iteration of text
generation benchmarks for evaluating large language models that can capture
these advanced capabilities’? We posit that one direction is to natively build
in logical and compositional challenges into text generation, through the lens
of constrained text generation. Existing benchmarks for constrained generation
however focus only on a particular constraint type, require tailored pipeline
to collect data and annotations, and/or can only evaluate a specific aspect of
the LM’s strength [25, 5]. They also suffer from challenges in constructing
datasets for scalable and comprehensive evaluation of LLMs.

In this paper, we propose Collie, a grammar-based framework that enables
systematic construction of compositional constraints over diverse generation
levels (e.g., words, sentences, paragraphs) and semantic requirements (e.g.,
language understanding, logical reasoning, counting). Operationally, Collie
allows researchers to 1) easily specify constraint templates, and then
automatically 2) extract constraint values from language corpora, 3) render
them into natural language instructions, and 4) evaluate model generations
against the constraint instructions. The modular and extensible design of
Collie allows the broader NLP community to contribute additional constraints
that can co-evolve with LLM capabilities over time, as well as provide a
convenient endpoint for users that only want to evaluate their model without
developing their own constraints.

Figure 1:  Our Collie framework for constraint structure specification, ground
truth extraction, instruction rendering, and evaluation. First, the user
specifies the constraint structure without a specific target value (expressed
in $*$). Second, the constraint structure is used to extract ground truth
examples from text corpora that contain the target values. Third, the
constraint structure and target values are rendered into a natural language
instruction. Finally, the model’s generation is evaluated against the
constraint and the ground truth. The model (gpt-3.5-turbo) violates the
constraints by exceeding word limits and leaving the word ‘mankind’ at the end
instead of the specified position.

We construct the dataset Collie-v1 with 2,080 constraint instances across 13
different types, using three different corpora: Wikipedia [11], CC-News [12],
and Project Gutenberg [3]. We perform zero-shot evaluations of five state-of-
the-art LLMs of varying sizes including GPT-4 [28] and PaLM [1]. While GPT-4
comparatively performs the best, it still achieves an average constraint
satisfaction rate of only 50.9%. We find that challenges correlate with
position – for instance, instructing models to begin a sentence with a
specific word leads to a 100% success rate for GPT-4, while asking models to
end a sentence with a particular word results in a success rate of 40%-60%.

To summarize, we make the following contributions: (1) We introduce Collie, a
framework for systematic generation of compositional constraints, that is
flexible and extensible. (2) We use Collie to curate a new dataset Collie-v1
comprising of 13 constraint structures. (3) We perform a comprehensive
evaluation of five state-of-the-art LLMs of varying sizes and provide useful
insights for both model and benchmark development in the future.

##  2 Related Work

Constrained text generation. Early work in controllable text generation used
control codes to steer the generation towards desired topics or to reduce
undesirable content, by controlling for broad attributes such as sentiment or
toxicity [17, 19, 9, 20]. Other work on constrained decoding provides to the
language model a collection of lexical items as constraints to be included or
excluded in the final generated text [15, 13, 10, 16, 25, 26, 27, 23]. Recent
advances in instruction tuning LLMs [30] have brought major improvements to
controllability. These advancements have made it challenging to use existing
controllable generation datasets to fully assess the capabilities of modern
LLMs.

Grammar-based compositional tests. Building benchmarks with data synthesized
from grammars has been explored previously in the context of question
answering [37], instruction following [7, 31]) and visual reasoning [18].
These benchmarks showcased the utility of grammars to systematically generate
a comprehensive set of test cases within each domain. However, these datasets
were all synthetic with limited linguistic diversity and practical
applicability to real-world scenarios. In contrast, since our Collie framework
extracts values and examples from natural language corpora to construct the
constraints, it represents a more realistic challenge for modern LLMs.

Systematic and scalable language benchmarks. The emergence of increasingly
powerful general-purpose language models has created a need for scalable
benchmarks that can systematically and comprehensively evaluate them. A few
recent examples include HELM [24], BIG-Bench [33], MMLU [14], TaskBench500
[22], and Natural Instructions [36]. However, building such benchmarks require
considerable human effort, and may become obsolete when stronger models enter
the arena. We provide a new perspective in this race between model
capabilities and challenging benchmarks: leverage compositionality to
construct automatic and scalable benchmarks with minimal human effort that can
co-evolve with model capabilities to remain challenging and relevant.

##  3 Collie: A Grammar-based Framework for Constrained Text Generation

Collie allows researchers to easily 1) specify textual constraint structures
via a grammar, then automatically 2) extract constraint values from text
corpora, 3) render constraints into natural language instructions, and 4)
evaluate generations with respect to constraints.

Grammar. Two observations about text constraints motivate a grammar
characterization: 1) they involve different levels of text, e.g. character,
word, sentence, or paragraph; and 2) many of them specify either the count or
position at a certain text level (existence is equivalent to count$~{}>0$).

Let capitalized letters ($S,M,C,T$) will denote non-terminal variables, and
other symbols ($\ell,\circ,\oplus,v$) denote terminals. A full constraint
specification within our grammar $S$ (Eq. 1) consists of two parts: a
generation level $(\texttt{level}(\xi)=\ell)$ specifying whether the generated
text $\xi$ should be a word, a sentence, a paragraph, or a document, and a
multi-constraint $M$ (Eq. 2), which is a logical composition of one or more
base-constraints $C$. A text $T$ (Eq. 4) within these constraints can either
be the full generated text $\xi$, or a part of it when qualified with a
$\texttt{pos}(\cdot)$. For example,
$\texttt{pos}(\texttt{pos}(\xi,\text{paragraph},3),\text{sentence},-1)$ means
“the last sentence of the 3rd paragraph of the generated text”. For the
terminal variables, we define a level $\ell$ of a text (Eq. 5), a string or
number relation $\circ$ or $\oplus$ (Eq. 6), and a string or number value
$v_{\text{str}}$ or $v_{\text{num}}$ (Eq. 7) intuitively. $\wedge$ represents
the logical ‘and’ operator, and $\vee$ represents the logical ‘or’. With these
definitions, we construct the following grammar:

$\displaystyle S$ $\displaystyle\to(\texttt{level}(\xi)=\ell)\wedge M$
(constraint specification) (1) $\displaystyle M$ $\displaystyle\to C\mid
C\wedge M\mid C\vee M$ (multi-constraint) (2) $\displaystyle C$
$\displaystyle\to\texttt{count}(T,\ell,v_{\text{str}}\mid\ell^{\prime})\oplus
v_{\text{num}}\mid\texttt{pos}(T,\ell,v_{\text{num}})\circ v_{\text{str}}$
(base-constraint) (3) $\displaystyle T$
$\displaystyle\to\xi\mid\texttt{pos}(T,\ell,v_{\text{num}})$ (text) (4)
$\displaystyle\ell$
$\displaystyle\to\text{char}\mid\text{word}\mid\text{sentence}\mid\text{paragraph}\mid\text{passage}$
(level) (5) $\displaystyle\circ$
$\displaystyle\to=\mid\neq\quad\quad\oplus\to=\mid\neq\mid>\mid<\mid\leq\mid\geq$
(relation) (6) $\displaystyle v_{\text{str}}$
$\displaystyle\in\Sigma^{*}\quad\quad\quad v_{\text{num}}\in\mathbb{Z}$
(value) (7)

At the core of our grammar, we consider two (symmetrical) types of base-
constraints $C$ (Eq. 3):

1\. Count constraints. $\texttt{count}(T,\ell,v_{\text{str}})\oplus
v_{\text{num}}$ constrains the occurrences of a particular level-$\ell$ string
$v_{\text{str}}$. For example,
$\texttt{count}(T,\text{word},\text{`happy'})\leq 3$ means “T should contain
the word ‘happy’ no more than 3 times”. In contrast,
$\texttt{count}(T,\ell,\ell^{\prime})\oplus v_{\text{num}}$ constrains the
occurrences of level-$\ell$ strings in each level-$\ell^{\prime}$ unit of text
T. For example, $\texttt{count}(T,\text{char},\text{sentence})=50$ means “each
sentence of text T should have exactly 50 characters”.

2\. Position constraints. $\texttt{pos}(T,\ell,v_{\text{num}})\circ
v_{\text{str}}$ specifies that a particular part of the text T should equal
(or not equal) the given string $v_{\text{str}}$. For example,
$\texttt{pos}(T,\text{word},3)=\text{`happy'}$ means “the 3rd word should be
‘happy’ in text T”. We also allow negative indices for reverse counting, e.g.
$\texttt{pos}(T,\text{char},-1)\neq\text{x}$ means “the last letter should not
be ‘x’ in text T”.

Note that the grammar above can easily be extended to accommodate more types
of base-constraints (e.g. part of speech, sentiment) by implementing the
corresponding semantic checks — we leave this to future work. Also for
convenience, we use constraint structure to refer to a family of constraint
specifications that only differ in their values (e.g. generate a sentence with
exactly $x$ words, $x\in\mathbb{N}$), and constraint to refer to a particular
constraint specification with concrete values (e.g. generate a sentence with
exactly 5 words).

Examples and conceptual challenges. Our grammar can express a wide range of
constraints through logical compositions of base-constraints across different
text levels. Table 1 illustrates some constraint structures across generation
levels, identified by names such as para01 for paragraph generation, etc. In
addition to the generation levels, count and pos across different levels
introduce a variety of challenges. For example, word01 and sent01 challenge
token-based language models to count characters; pass01 requires high-level
semantic planning for models to generate a coherent passage under constraints;
sent04 and para02 challenge models to generate text with presence or absence
of particular words; sent03, para03, and para04 require counting at multiple
levels; and word02, word03, sent02, para05, and pass01 combine counting and
positional challenges at different levels, which can be considered most
demanding conceptually. We empirically assess the difficulty of constraint
structures in Section 5.

ID |  Example instruction |  Multi-constraint $M$
---|---|---
word01 |  Generate a word with at least 15 letters. |  $\texttt{count}(\xi,\text{char},\text{word})\geq 15$
word02 |  Generate a word with 10 letters, where letter 1 is ‘s’, letter 3 is ‘r’, letter 9 is ‘e’. |  $\texttt{count}(\xi,\text{char},\text{word})=10$ $\wedge$ $\texttt{pos}(\xi,\text{char},1)=\text{`s'}$ $\wedge$ $\texttt{pos}(\xi,\text{char},3)=\text{`r'}$ $\wedge$ $\texttt{pos}(\xi,\text{char},9)=\text{`e'}$
word03 |  Generate a word with at most 10 letters and ends with “r". |  $\texttt{count}(\xi,\text{char},\text{word})\leq 10$ $\wedge$ $\texttt{pos}(\xi,\text{char},-1)=\text{`r'}$
sent01 |  Please generate a sentence with exactly 82 characters. Include whitespace into your character count. |  $\texttt{count}(\xi,\text{char},\text{sentence})=82$
sent02 |  Generate a sentence with 10 words, where word 3 is “soft” and word 7 is “beach” and word 10 is “math”. |  $\texttt{count}(\xi,\text{word},\text{sentence})=10$ $\wedge$ $\texttt{pos}(\xi,\text{word},3)=\text{``soft"}$ $\wedge$ $\texttt{pos}(\xi,\text{word},7)=\text{``beach"}$ $\wedge$ $\texttt{pos}(\xi,\text{word},10)=\text{``math"}$
sent03 |  Generate a sentence with at least 20 words, and each word less than six characters. |  $\texttt{count}(\xi,\text{word},\text{sentence})\geq 20$ $\wedge$ $\texttt{count}(\xi,\text{char},\text{word})\leq 6$
sent04 |  Generate a sentence but be sure to include the words “soft”, “beach” and “math”. |  $\texttt{count}(\xi,\text{word},\text{`soft'})>0$ $\wedge$ $\texttt{count}(\xi,\text{word},\text{`beach'})>0$ $\wedge$ $\texttt{count}(\xi,\text{word},\text{`math'})>0$
para01 |  Generate a paragraph where each sentence begins with the word “soft”. |  $\texttt{pos}(\texttt{pos}(\xi,\text{sentence},1),\text{word},1)=\text{`soft'}\wedge$ $\texttt{pos}(\texttt{pos}(\xi,\text{sentence},2),\text{word},1)=\text{`soft'}\wedge...$
para02 |  Generate a paragraph with at least 4 sentences, but do not use the words “the”, “and” or “of”. |  $\texttt{count}(\xi,\text{sentence},\text{paragraph})\geq 4$ $\wedge$ $\texttt{count}(\xi,\text{word},\text{`the'})=0$ $\wedge$ $\texttt{count}(\xi,\text{word},\text{`and'})=0$ $\wedge$ $\texttt{count}(\xi,\text{word},\text{`of'})=0$
para03 |  Generate a paragraph with exactly 4 sentences, each with between 10 and 15 words. |  $\texttt{count}(\xi,\text{sentence},\text{paragraph})=4$ $\wedge$ $\texttt{count}(\xi,\text{word},\text{sentence})\geq 10$ $\wedge$ $\texttt{count}(\xi,\text{word},\text{sentence})\leq 15$
para04 |  Generate a paragraph with at least 3 sentences, each with at least 15 words. |  $\texttt{count}(\xi,\text{sentence},\text{paragraph})\geq 3$ $\wedge$ $\texttt{count}(\xi,\text{word},\text{sentence})\geq 15$
para05 |  Generate a paragraph with 2 sentences that end in “math” and “rock” respectively. |  $\texttt{count}(\xi,\text{sentence},\text{paragraph})=2$ $\wedge$ $\texttt{pos}(\texttt{pos}(\xi,\text{sentence},1),\text{word},-1)=\text{``math"}$ $\wedge$ $\texttt{pos}(\texttt{pos}(\xi,\text{sentence},2),\text{word},-1)=\text{``rock"}$
pass01 |  Generate a passage with 2 paragraphs, each ending in “I sit.” and “I cry.” respectively. |  $\texttt{count}(\xi,\text{paragraph},\text{passage})=2$ $\wedge$ $\texttt{pos}(\texttt{pos}(\xi,\text{paragraph},1),\text{sentence},-1)=\text{``I sit."}$ $\wedge$ $\texttt{pos}(\texttt{pos}(\xi,\text{paragraph},2),\text{sentence},-1)=\text{``I cry."}$

Table 1: List of all constraint structures used in Collie-v1, with
(simplified) example values.

In conjunction with the grammar, we develop a set of compiling tools to help
construct datasets with minimal human efforts. Concretely, the pipeline of
dataset construction involves 4 stages (Figure 1):

1\. Specify constraint structures. Researchers can specify constraint
structures (e.g. Table 1), and optionally with a value range (e.g. “generate a
sentence with $x$ words”, and $5\leq x\leq 10$). This is the only stage that
involves manual effort.

2\. Extract constraint values from corpora. We design an automatic extraction
algorithm that runs through a given text corpus to find strings that fit a
constraint structure with some value ranges. For example, given the constraint
structure $\texttt{count}(\xi,\text{word},\emptyset)=x$ with value range
$5\leq x\leq 10$, the extraction algorithm returns sentences in the corpus
that have 5-10 words, with associated word counts. This ensures each
constraint has at least one natural solution. More details are in Section 4.1.

3\. Render natural language instructions. Each constraint can be rendered into
a natural language instruction (Table 1) via ruled-based translation to prompt
language models (details in Section A.1).

4\. Evaluate generations. Given text $\xi$ generated by a model, we use a
parser to evaluate it against a constraint specification $S$ and derive a
True/False value, indicating if $\xi$ satisfies $S$. We use an average Success
Rate as the main metric to evaluate constraint conformance. We can also
compare the fluency of $\xi$ against the corpus-extracted “groundtruth” text,
and render more fine-grained natural language feedback indicating which base-
constraints are met and which not (see Section A.2).

##  4 Dataset Construction: Collie-v1

We construct Collie-v1 using constraints structures from Table 1, which
contains 2,080 constraint instances from 13 constraint types, with 1,435
unique constraint prompts. The broader NLP community can contribute to future
dataset releases by adding additional constraints, metrics, data sources. The
curated constraint set can co-evolve with models to become more challenging
and comprehensive as model capabilities improve. All code and data are
available at https://collie-benchmark.github.io, and further details on
dataset construction are also provided in Section B.

###  4.1 Constraint specification and extraction

Constraint specification. We begin by defining 13 constraint structures. We
chose these 13 structures to span various generation levels (word, sentence,
paragraph and passage generation) and challenges (counting, position). In
total, we have 3 word-level, 4 sentence-level, 5 paragraph-level, and 1
passage-level constraint structures. Of these 13 constraint structures, 5 are
single-level and the remaining 8 are multi-level constraints. See Table 1 for
the exact constraint structures we use.

Constraint extraction. While constructing constraint structures is
straightforward using our grammar, choosing constraint targets is challenging
for two reasons: (1) Not all targets will admit a conforming natural language
string. For instance, the constraint, “Generate a two word sentence beginning
with the word The.” has no grammatically acceptable answer. (2) Even if a
constraint admits a possible answer, it may not admit a plausible answer. For
instance, “Generate a sentence with 1928 words” is possible, but any such
sentence is very unlikely to appear in regular discourse.

To address both challenges, we sample constraint target values from natural
language corpora, which we denote as the data source. Given a constraint
structure $\mathcal{C}$ and documents $\mathcal{D}=\\{d_{1},...,d_{n}\\}$, we
chunk each document into a series of strings $d_{i}=\\{s_{1},...,s_{m}\\}$,
where each $s_{i}$ can be a sentence, paragraph, or passage as required by
$\mathcal{C}$. Each string $s_{i}$ undergoes source-specific automated
filtering and post-processing to remove artifacts, which we detail in Section
4.2. In all the data sources we consider, a single or double newline is used
to delimit paragraphs. To obtain sentences, we use the nltk [2] sentence
tokenizer on each paragraph. To obtain passages, we string together multiple
consecutive paragraphs that survive filtering. To obtain word-level constraint
targets, we iterate each $s_{i}$ from an English language word list***We use
the word list from http://www.gwicks.net/textlists/english3.zip.. Given
$\mathcal{C}$ and $s_{i}$, we extract target values such that $\mathcal{C}$ is
satisfied. In most cases, the satisfying target values can be directly
extracted using our provided utilities. For example, for constraints with
structure “sentence with $x$ words”, we can directly apply word tokenization
and counting to the example string $s_{i}$. In cases in which direct
extraction is not possible, (e.g. “do not include word $w$”), we specify a
range of possible targets (e.g. $\\{$the, and, of$\\}$) to sweep over. All in
all, our approach ensures that (1) there exists a natural language string that
can satisfy each constraint and target pair, and (2) the targets follow a
plausible distribution induced by natural language corpora. Our extraction
system is extensible, and can operate on new constraints and data sources with
minimal modifications. An end user wishing to extract targets from their
constraints on our data sources simply provides the constraint configuration
and optionally a target range to sweep over, and the extraction is handled
automatically using our tools. Adding additional data sources to the
extraction pipeline is similarly easy, requiring a text delimiter, and
optional string filtering and post-processing functions.

###  4.2 Data sources

Figure 2: Data statistics. (a) Number of constraints from each constraint
structure. (b) Fraction of strings removed by automated filtering. (c) Length
statistics for different levels for each data source.

To ensure adequate coverage of diverse styles and content, we extract
constraint targets from three distinct data sources: Wikipedia (Wiki)[11],
Common Crawl News (CC-News)[12], and the Project Gutenberg Corpus (Guten)[3].
We provide an overview of these data sources below and in Section B.4.

Wiki. Wikipedia (Wiki) [11] is a dump from the Wikimedia Foundation,
consisting of over 6 million English Wikipedia articles. We included this data
source for its diverse subject matter. We filter any string that is a figure
caption, contains a URL, or does not contain any sentences. Each filter is
based off heuristics and utilize regular expressions (see Section B.2). The
strings are then stripped of section titles, which are always followed by a
single newline, instead of a double newline.†††We use the preprocessed
20220301.en split from Huggingface.

CC-News. The Common Crawl News corpus (CC-News) [12] consists of 708,241
English language news articles published between Jan 2017 and December 2019.
We include CC-News to include documents which feature interview dialogues, as
well as popular culture and current events. In addition to the filters used
for Wiki, we found it necessary to include a copyright filter that rejects any
string containing the copyright symbol ©, or begins with the word “copyright”.
We do not use any post-processing function for strings from CC-News.

Guten. The Project Gutenberg corpus (Guten) [3] consists of over 50,000
documents that include fiction, histories, biographies, and other works that
are in the public domain in the United States‡‡‡We use the processed corpus
from Gutenberg, dammit at: https://github.com/aparrish/gutenberg-dammit. We
include this corpus for its variety in style with text from different time
periods. Similar to Wiki, we remove any string without a sentence using the
same heuristics. We further filter any section titles by removing any line
entirely in upper case. Each document in Guten is formatted using Markdown.
For each string we remove Markdown formatting (e.g. **, __,), and remove all
references and footnotes using regular expressions (see Section B.3). We
further clean the text by replacing single newlines and multiple consecutive
whitespace tokens with a single whitespace token.

###  4.3 Data validation and statistics

We extract constraints from 300 randomly sampled documents from each source.
After extracting the target values, we sample up to 100 targets for each
constraint structure on each data source. We remove any string targets by that
begins or ends with any character that is not a letter or number. We randomly
sample 5 out of these 100 targets and their supporting examples to
qualitatively verify their validity. Since the extraction process is
relatively fast, we modify filters and post-processors if there are systemic
issues and re-run the extraction phase. We provide statistics of the final
number of constraints from each constraint structure in Figure 2(a). Some
constraints (e.g. number of sentences per paragraph) are tightly clustered
around the mean, and thus does not induce many valid constraint targets. The
fraction of strings filtered for each data source and level is presented in
Figure 2(b). The automated filtering removes a large fraction of the strings
in most cases, as high recall is important to ensure the quality of extracted
targets. The high fraction of omitted passages is due to the removal of
passages less than two paragraphs in length. Mean length statistics for each
level and data source is presented in Figure 2(c). There is high variance in
lengths across data sources, demonstrating the diversity of the text used to
extract the targets. For instance, the mean number of paragraphs per passage
is 11.8 in Guten, while it is almost half that in Wikipedia at 6.1 paragraphs
per passage. Finally, for para02, para03, and pass01 constraints, authors did
manual filtering to make sure paragraph and passage examples are clean and
with proper lengths.

##  5 Results & Analysis

Figure 3: Model comparison. (a) Overall model performance summarized by
weighted average across all constraint groups. (b) -(f) Constraint
satisfaction rates of generated texts by GPT-4, GPT-3.5, PaLM, Vicuna-7B, and
Alpaca-7B across various constraint groups. Error bars represent standard
error. Constraint group names are in Table 1. Sample sizes are reported in
Figure 10.

[]  []

Figure 4: Pass@k performance. We sample the model-generated text 20 times for
all instruction prompts in the dataset. The curves represent the average pass
rate across all instruction prompts up to $k$ samples. The shaded areas
indicate the standard errors. Figure 5: Position effect. Satisfaction rates of
LMs on tasks involving $\texttt{pos}(\xi,\text{level},i)$. The tasks word02
and sent02 impose constraints on characters and words at arbitrary positions.
The task para01 constrains the first word. The tasks word03, para05, and
pass01 constrain the last characters, words, and sentences.

Our main experiments in this paper focus on a zero-shot§§§We tried one-shot
prompting and find GPT performances similar to zero-shot, see Section C.1.
prompting setup with the following language models (LMs): 1) larger and
closed-source LMs such as OpenAI GPT [4, 29] (gpt-3.5-turbo, gpt-4) and Google
PaLM-2 [1] (text-bison-001); 2) smaller and open-source LMs such as Alpaca-7B
[34], Vicuna-7B [8] . By default, we use a sampling temperature of 0.7, and
sample multiple trials (20 for GPT/PaLM, 5 for Alpaca/Vicuna). All experiments
were run in July, 2023.

###  5.1 Main results

Zero-shot performance comparison. As evidenced in Figures 3(a), GPT-4
consistently surpassed other models in zero-shot constrained text generation
performances, achieving more than twice the constraint satisfaction rate than
other non-GPT models. The overarching performance trend observed shows GPT-4
leading the pack, followed by GPT-3.5 and PaLM with a large gap, and then
followed closely by the smaller models, Vicuna-7B and Alpaca-7B.

Constraints all models can follow. Certain tasks, specifically word01
(generating a word with at least $a$ letters), sent04 (generating a sentence
containing words X, Y, Z), and para01 (generating a paragraph with each
sentence starting with the word X), posed minimal challenge to the majority of
contemporary language models. These tasks demonstrate the proficiency of
current models at simple constraints ensuring existence, as depicted in Figure
8(f).

Constraints partially solved by GPT-4 only. However, a notable distinction
arose when tasks incorporated more counting/position constraints and requested
longer generations. Tasks such as word03, para04, para05, and pass01 were only
partially addressed by GPT-4, with constraint satisfaction rates ranging
between 40% and 70%. Despite GPT-4’s partial success in these tasks, other
models failed to deliver any satisfactory performance.

Constraints remaining very challenging. Furthermore, some tasks proved
challenging across all models. Tasks word02, sent01, sent02, and para03
present challenges in terms of arbitrary position constraints and mixed
counting levels (see Section 5.2 for detailed analysis), indicating areas that
necessitate further advancements in language model technology. Moreover, the
average pass@20 rate of GPT-4 was above 63% across all constraints,
significantly higher than the 32% achieved by GPT-3.5, as depicted in Figure
5. Although GPT-4 demonstrated a significant performance advantage, its
constraint satisfaction rate of 63% is far from perfect. This suggests
considerable scope for improvement in controllable text generation with
language models. These findings underscore the opportunities and challenges in
the continued evolution of language models.

###  5.2 Analysis

Performance consistency across data sources. We observe a high degree of
consistency in the performance of models on a given constraint structure,
regardless of the data source. This uniformity is evident across all models,
as highlighted in Figure 8 (g). This indicates that the ability of a language
model to adhere to the logic of constraints takes precedence over the specific
target values or the distribution of the data.

Position effect. As depicted in Figure 5, the
$\texttt{pos}(\xi,\text{level},i)$ function, constraining the $i$-th sub-
string (letter, word, or sentence), exhibits varying levels of difficulty
depending on the value of $i$. Models generally perform well when the
positional constraint is applied to the first sub-string ($i=1$, task para01).
However, only GPT-4 displays partial success with the last positional
constraints ($i=-1$, tasks word03, para05, pass01). Notably, all models
encounter difficulties when generating text that satisfies positional
constraints at arbitrary positions $i$. Additionally, we find that the
position effect exhibits a lower sensitivity to constraint levels.

Figure 6: Counting level effect. Satisfaction rates for LMs on tasks involving
$\texttt{count}(\xi,\text{level},\varphi)$. Task word01 sets a minimum word
length of $a$. Task sent01 requires exactly $a$ characters in a sentence. Task
sent03 asks a sentence to contain at least $b$ words, with each word no longer
than $a$ letters. Task para04 asks a paragraph to consist of at least $b$
sentences, each containing a minimum of $a$ words. Task para03 further imposes
an upper limit on the number of words per sentence.

Counting level effect. The task of counting characters within a word is
comparatively easier for models than counting characters within a sentence, as
illustrated in Figure 6. Furthermore, tasks demanding exact equality (task
sent01) prove more challenging than those requiring a range (task para03), and
are considerably more difficult than tasks specifying just an upper or lower
bound (tasks word01, sent03, para04).

Increased difficulty with logical composition. The incorporation of logical
compositions into constraints considerably increases their difficulty. Task
sent03 serves as an example of this, adding an extra constraint at the
sentence level compared to task word01. Despite the assumption that the added
constraint should be manageable for all models, performance on task sent03
uniformly trails behind that on task word01, as shown in Figure 6. This
highlights the intricacy and challenge introduced by logical compositions
within constraints.

Performance enhancement through feedback and interaction. We utilize Collie to
generate automated natural language feedback for previous generations,
prompting the model to generate text in subsequent rounds. This approach
resembles a pass@k setup but incorporates additional feedback. In Figure 7, we
observe a significant 20% improvement in GPT-4 performance after the second
round of feedback. However, the model’s performance plateaus at 66% even after
three additional rounds of feedback, comparable to pass@5. The extent of
performance improvement varies across tasks, with word03’s constraint
satisfaction rate increasing from 62.1% to 10%. Conversely, word02, sent01,
and sent02 tasks remain challenging for the model. These findings suggest that
there is still room for improvement, highlighting the difficulty of our
dataset, and emphasizing the need for further research on better ways to
incorporate natural language feedback.

Figure 7: GPT-4 interactive generation performance. (a) Constraint
satisfaction rate of GPT-4 generated texts in the 4th round across various
constraint groups. (b) GPT-4 overall performance in different feedback rounds.
The 1st round is zero-shot, and the 2nd - 4th rounds are with feedback.

##  6 Conclusion

In this work, we present Collie, a grammar-based framework for specifying
textual constraints. Collie simplifies the process of creating constrained-
generation datasets by enabling researchers to focus on specifying high level
constraint structures, while Collie automatically extracts constraint values,
renders natural language instructions, and assesses model performance. To
demonstrate the utility of the Collie framework, we construct Collie-v1 with
1,132 constraints from 13 different types, extracted from 3 different data
sources. We evaluate five state-of-the-art LLMs of various sizes on Collie-v1,
and find that it provides fine-grained insights into model capabilities and
shortcomings. We hope that model developers can use Collie-v1 to develop more
capable models, while future releases of Collie can continue to adapt to the
capabilities and needs of future models and users.

Limitations and impacts. Although care was taken to design the filtering and
processing functions, such automated approaches are never perfect and can
affect the quality of downstream constraints. We plan to continue mitigating
such effects with additional utilities such as grammar checkers and parsers.
Our representative constraint structures were selected to encompass diverse
constrained generation challenges, but as with all generation benchmarks, they
cannot capture all dimensions and nuances of model capabilities. Benchmarks
are highly influential in shaping model development, the capabilities and
limitations of which may disproportionately impact different communities. Our
benchmark is no exception. However, by providing an extensible, easy-to-use
framework for constraint development, we hope Collie will enable diverse
stakeholders to engage with the construction of datasets, helping ensure that
future model capabilities serve diverse interests and needs.

## Acknowledgements

We thank Xiao Liu for Vicuna/Alpaca APIs that supported our preliminary
experiments, and Princeton NLP Group for helpful discussion and feedback in
general. We acknowledge support from the National Science Foundation under
Grant No. 2107048. Any opinions, findings, and conclusions or recommendations
expressed in this material are those of the author(s) and do not necessarily
reflect the views of the National Science Foundation.

## References

  * Anil et al. [2023] R. Anil, A. M. Dai, O. Firat, M. Johnson, D. Lepikhin, A. Passos, S. Shakeri, E. Taropa, P. Bailey, Z. Chen, et al.  Palm 2 technical report.  _arXiv preprint arXiv:2305.10403_ , 2023.
  * Bird [2006] S. Bird.  Nltk: the natural language toolkit.  In _Proceedings of the COLING/ACL 2006 Interactive Presentation Sessions_ , pages 69–72, 2006.
  * Brooke et al. [2015] J. Brooke, A. Hammond, and G. Hirst.  Gutentag: an nlp-driven tool for digital humanities research in the project gutenberg corpus.  In _Proceedings of the Fourth Workshop on Computational Linguistics for Literature_ , pages 42–47, 2015.
  * Brown et al. [2020] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert-Voss, G. Krueger, T. Henighan, R. Child, A. Ramesh, D. M. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2020.  URL https://papers.nips.cc/paper/2020/hash/1457c0d6bfcb4967418bfb8ac142f64a-Abstract.html.
  * Chen et al. [2022a] H. Chen, H. Li, D. Chen, and K. Narasimhan.  Controllable text generation with language constraints.  In _preprint_ , 2022a.  URL https://arxiv.org/abs/2212.10466.
  * Chen et al. [2022b] M. Chen, J. Tworek, H. Jun, Q. Yuan, H. Ponde de Oliveira Pinto, J. Kaplan, H. Edwards, Y. Burda, N. Joseph, G. Brockman, A. Ray, R. Puri, G. Krueger, M. Petrov, H. Khlaaf, G. Sastry, P. Mishkin, B. Chan, S. Gray, N. Ryder, M. Pavlov, A. Power, L. Kaiser, M. Bavarian, C. Winter, P. Tillet, F. Petroski Such, D. Cummings, M. Plappert, F. Chantzis, E. Barnes, A. Herbert-Voss, W. Hebgen Guss, A. Nichol, A. Paino, N. Tezak, J. Tang, I. Babuschkin, S. Balaji, S. Jain, W. Saunders, C. Hesse, A. N. Carr, J. Leike, J. Achiam, V. Misra, E. Morikawa, A. Radford, M. Knight, M. Brundage, M. Murati, K. Mayer, P. Welinder, B. McGrew, D. Amodei, S. McCandlish, I. Sutskever, and W. Zaremba.  Evaluating large language models trained on code.  In _preprint_ , 2022b.  URL https://arxiv.org/abs/2107.03374.
  * Chevalier-Boisvert et al. [2019] M. Chevalier-Boisvert, D. Bahdanau, S. Lahlou, L. Willems, C. Saharia, T. H. Nguyen, and Y. Bengio.  Babyai: A platform to study the sample efficiency of grounded language learning.  In _International Conference on Learning Representations (ICLR)_ , 2019.  URL https://arxiv.org/abs/1810.08272.
  * Chiang et al. [2023] W.-L. Chiang, Z. Li, Z. Lin, Y. Sheng, Z. Wu, H. Zhang, L. Zheng, S. Zhuang, Y. Zhuang, J. E. Gonzalez, I. Stoica, and E. P. Xing.  Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality, March 2023.  URL https://lmsys.org/blog/2023-03-30-vicuna/.
  * Dathathri et al. [2020] S. Dathathri, A. Madotto, J. Lan, J. Hung, E. Frank, P. Molino, J. Yosinski, and R. Liu.  Plug and play language models: A simple approach to controlled text generation.  In _International Conference on Learning Representations (ICLR)_ , 2020.  URL https://openreview.net/pdf?id=H1edEyBKDS.
  * Dinu et al. [2019] G. Dinu, P. Mathur, M. Federico, and Y. Al-Onaizan.  Training neural machine translation to apply terminology constraints.  In _Association for Computational Linguistics (ACL)_ , 2019.
  * Foundation [2022] W. Foundation.  Wikimedia downloads, 2022.  URL https://dumps.wikimedia.org.
  * Hamborg et al. [2017] F. Hamborg, N. Meuschke, C. Breitinger, and B. Gipp.  news-please: A generic news crawler and extractor.  In _Proceedings of the 15th International Symposium of Information Science_ , pages 218–223, March 2017.  doi: 10.5281/zenodo.4120316.
  * Hasler et al. [2018] E. Hasler, A. de Gispert, G. Iglesias, and B. Byrne.  Neural machine translation decoding with terminology constraints.  In _North American Association for Computational Linguistics (NAACL)_ , 2018.
  * Hendrycks et al. [2020] D. Hendrycks, C. Burns, S. Basart, A. Zou, M. Mazeika, D. Song, and J. Steinhardt.  Measuring massive multitask language understanding.  _arXiv preprint arXiv:2009.03300_ , 2020.
  * Hokamp and Liu [2017] C. Hokamp and Q. Liu.  Lexically constrained decoding for sequence generation using grid beam search.  In _Association for Computational Linguistics (ACL)_ , 2017.
  * Hu et al. [2019] J. E. Hu, H. Khayrallah, R. Culkin, P. Xia, T. Chen, M. Post, and B. Van Durme.  Improved lexically constrained decoding for translation and monolingual rewriting.  In _North American Association for Computational Linguistics (NAACL)_ , 2019.
  * Hu et al. [2017] Z. Hu, Z. Yang, X. Liang, R. Salakhutdinov, and E. P. Xing.  Toward controlled generation of text.  In _International Conference on Machine Learning (ICML)_ , 2017.
  * Johnson et al. [2017] J. Johnson, B. Hariharan, L. van der Maaten, L. Fei-Fei, C. L. Zitnick, and R. Girshick.  Clevr: A diagnostic dataset for compositional language and elementary visual reasoning.  In _Conference on computer vision and pattern recognition (CVPR)_ , 2017.  URL https://ieeexplore.ieee.org/document/8099698.
  * Keskar et al. [2019] N. S. Keskar, B. McCann, L. R. Varshney, C. Xiong, and R. Socher.  CTRL: A conditional transformer language model for controllable generation.  In _preprint_ , 2019.  URL https://arxiv.org/abs/1909.05858.
  * Krause et al. [2021] B. Krause, A. D. Gotmare, B. McCann, N. S. Keskar, S. Joty, R. Socher, and N. F. Rajani.  GeDi: Generative discriminator guided sequence generation.  In _Findings of the Empirical Methods in Natural Language Processing (EMNLP Findings)_ , 2021.  URL https://aclanthology.org/2021.findings-emnlp.424.
  * Lhoest et al. [2021] Q. Lhoest, A. Villanova del Moral, Y. Jernite, A. Thakur, P. von Platen, S. Patil, J. Chaumond, M. Drame, J. Plu, L. Tunstall, J. Davison, M. Šaško, G. Chhablani, B. Malik, S. Brandeis, T. Le Scao, V. Sanh, C. Xu, N. Patry, A. McMillan-Major, P. Schmid, S. Gugger, C. Delangue, T. Matussière, L. Debut, S. Bekman, P. Cistac, T. Goehringer, V. Mustar, F. Lagunas, A. Rush, and T. Wolf.  Datasets: A community library for natural language processing.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 175–184, Online and Punta Cana, Dominican Republic, Nov. 2021. Association for Computational Linguistics.  URL https://aclanthology.org/2021.emnlp-demo.21.
  * Li et al. [2022a] B. Z. Li, J. Yu, M. Khabsa, L. Zettlemoyer, A. Halevy, and J. Andreas.  Quantifying adaptability in pre-trained language models with 500 tasks.  In _North American Association for Computational Linguistics (NAACL)_ , 2022a.  URL https://arxiv.org/abs/2112.03204.
  * Li et al. [2022b] X. L. Li, J. Thickstun, I. Gulrajani, P. Liang, and T. B. Hashimoto.  Diffusion-lm improves controllable text generation.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2022b.  URL https://openreview.net/forum?id=3s9IrEsjLyk.
  * Liang et al. [2022] P. Liang, R. Bommasani, T. Lee, D. Tsipras, D. Soylu, M. Yasunaga, Y. Zhang, D. Narayanan, Y. Wu, A. Kumar, et al.  Holistic evaluation of language models.  _arXiv preprint arXiv:2211.09110_ , 2022.
  * Lin et al. [2020] B. Y. Lin, W. Zhou, M. Shen, P. Zhou, C. Bhagavatula, Y. Choi, and X. Ren.  Commongen: A constrained text generation challenge for generative commonsense reasoning.  In _Findings of the Empirical Methods in Natural Language Processing (EMNLP Findings)_ , 2020.
  * Lu et al. [2021] X. Lu, P. West, R. Zellers, R. L. Bras, C. Bhagavatula, and Y. Choi.  Neurologic decoding: (un)supervised neural text generation with predicate logic constraints.  In _North American Association for Computational Linguistics (NAACL)_ , 2021.  URL https://aclanthology.org/2021.naacl-main.339.pdf.
  * Lu et al. [2022] X. Lu, S. Welleck, P. West, L. Jiang, J. Kasai, D. Khashabi, R. L. Bras, L. Qin, Y. Yu, R. Zellers, N. A. Smith, and Y. Choi.  Neurologic a*esque decoding: Constrained text generation with lookahead heuristics.  In _North American Association for Computational Linguistics (NAACL)_ , 2022.  URL https://aclanthology.org/2022.naacl-main.57.
  * OpenAI [2023a] OpenAI.  Gpt-4 technical report.  In _preprint_ , 2023a.  URL https://arxiv.org/abs/2303.08774.
  * OpenAI [2023b] OpenAI.  Gpt-4 technical report, 2023b.
  * Ouyang et al. [2022] L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. L. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, J. Schulman, J. Hilton, F. Kelton, L. Miller, M. Simens, A. Askell, P. Welinder, P. Christiano, J. Leike, and R. Lowe.  Training language models to follow instructions with human feedback.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2022.  URL https://openreview.net/forum?id=TG8KACxEON.
  * Ruis et al. [2020] L. Ruis, J. Andreas, M. Baroni, D. Bouchacourt, and B. M. Lake.  A benchmark for systematic generalization in grounded language understanding.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2020.  URL https://arxiv.org/abs/2003.05161.
  * Schick et al. [2023] T. Schick, J. Dwivedi-Yu, R. Dessì, R. Raileanu, M. Lomeli, L. Zettlemoyer, N. Cancedda, and T. Scialom.  Toolformer: Language models can teach themselves to use tools.  In _preprint_ , 2023.  URL https://arxiv.org/abs/2302.04761.
  * Srivastava et al. [2022] A. Srivastava, A. Rastogi, A. Rao, A. A. M. Shoeb, A. Abid, A. Fisch, A. R. Brown, A. Santoro, A. Gupta, A. Garriga-Alonso, et al.  Beyond the imitation game: Quantifying and extrapolating the capabilities of language models.  _arXiv preprint arXiv:2206.04615_ , 2022.
  * Taori et al. [2023] R. Taori, I. Gulrajani, T. Zhang, Y. Dubois, X. Li, C. Guestrin, P. Liang, and T. B. Hashimoto.  Stanford alpaca: An instruction-following llama model.  https://github.com/tatsu-lab/stanford_alpaca, 2023.
  * Wang et al. [2018] A. Wang, A. Singh, J. Michael, F. Hill, O. Levy, and S. R. Bowman.  Glue: A multi-task benchmark and analysis platform for natural language understanding.  In _Empirical Methods in Natural Language Processing (EMNLP)_ , 2018\.  URL https://openreview.net/pdf?id=rJ4km2R5t7.
  * Wang et al. [2022] Y. Wang, S. Mishra, P. Alipoormolabashi, Y. Kordi, A. Mirzaei, A. Naik, A. Ashok, A. S. Dhanasekaran, A. Arunkumar, D. Stap, et al.  Super-naturalinstructions: Generalization via declarative instructions on 1600+ nlp tasks.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 5085–5109, 2022.
  * Weston et al. [2015] J. Weston, A. Bordes, S. Chopra, A. M. Rush, B. Van Merriënboer, A. Joulin, and T. Mikolov.  Towards ai-complete question answering: A set of prerequisite toy tasks.  _arXiv preprint arXiv:1502.05698_ , 2015.
  * Yao et al. [2022] S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y. Cao.  React: Synergizing reasoning and acting in language models.  In _International Conference on Learning Representations (ICLR)_ , 2022.  URL https://arxiv.org/abs/2210.03629.

## Code Availability

The code, data, and additional details are available at
https://collie-benchmark.github.io.

##  Appendix A Natural Language Rendering of Constraints

###  A.1 Instruction rendering

Collie provides a rule-based constraint renderer that converts constraints
into natural language instructions (see examples in Table 1).

Leveraging the compositionality of the context-free grammar, the renderer
first parses the constraint as a tree. In the case of multi-constraints, it
generates prompts for each base-constraint individually and then concatenates
the generated prompts together at the end. For a base-constraint, it follows a
pre-order traversal of the subtree to modify the initial template "Please
generate a {generation_level} with @… {tagert_level}," where "@…" serves as a
placeholder.

Although the rule-based instruction prompts are natural enough for all
examples in Collie-v1, there might be some edge cases where the rule-based
instructions are not fluent enough for newly specified constraints. To address
this, we offer an option to utilize language models to enhance the rule-based
instructions. We employ the following prompt for the language model to refine
the instructions: "Please rewrite the following paragraph to improve fluency
without altering the original meaning. You should provide the revised
paragraph directly. Original paragraph: {prompt}."

The renderer is independent of the constraint construction and can be easily
extended with new rules for parsing and mapping to instruction templates.

###  A.2 Feedback rendering

We further extend our framework to provide natural language feedback when the
extracted value of the generated text differs from the target value. Similar
to instruction rendering, we first employ a rule-based renderer to compose the
feedback by modifying a template. We also provide an option to use language
models to polish the generated feedback.

For instance, consider a constraint
$\texttt{count}(\xi,\text{char},`v^{\prime})=2\wedge\texttt{count}(\xi,\text{char},`i^{\prime})=3$,
while the generated word includes three ‘v’ and four ‘i’. Our framework can
generate the following instructions and feedback:

  * •

INSTRUCTION:
Please generate a word with exactly 2 character ‘v’ and exactly 3 character
‘i’.

  * •

GPT-POLISHED INSTRUCTION:
Please generate a word that contains exactly 2 instances of the letter ‘v’ and
exactly 3 instances of the letter ‘i’.

  * •

FEEDBACK:
Your task is to generate a word with exactly 2 character ‘v’ and exactly 3
character ‘i’. However, you generate a word with 3 character ‘v’ and 4
character ‘i’.

  * •

GPT-POLISHED FEEDBACK:
Your task was to generate a word with precisely 2 ‘v’ characters and precisely
3 ‘i’ characters. However, you generated a word with precisely 3 ‘v’
characters and precisely 4 ‘i’ characters.

By incorporating this feedback mechanism, our framework can provide explicit
guidance for the language models to improve the generation quality and adhere
to the specified constraints.

##  Appendix B Dataset

###  B.1 Extraction overview

The extraction phase is split into six steps:

  1. 1.

Document loading. The document $d$, usually consisting of multiple paragraphs
is loaded.

  2. 2.

Text chunking. Each document is divided into paragraphs using a source-
specific delimiter (e.g. \n). Sentence-level constraints are further sentence
tokenized using nltk.

  3. 3.

Text filtering. The paragraph or sentence passes a source-specific filtering
function that attempts to remove all strings that are not natural language,
for instance copyright statements.

  4. 4.

Text post-processing. The paragraphs or sentences that survive filtering are
post-processed to remove source-specific artifacts, such as Markdown
formatting.

  5. 5.

Passage construction (passage-level only). Paragraphs and sentences pass
through to the next step. Passages are constructed by appending as many
consecutive paragraphs that survive filtering as possible. For instance, if a
document contains paragraphs $p_{1},...,p_{9}$, and $p_{4}$ is the only
paragraph that is removed due to filtering, then we return two passages:
$(p_{1},p_{2},p_{3})$ and $(p_{5},...,p_{9})$. Each paragraph is joined by two
newline characters within each passage.

  6. 6.

Constraint extraction. The sentence, paragraph, or passage-level string is
passed to the constraint extractor that pulls out constraint targets from the
string. This can either be done directly, such as directly extracting the
total word count, or sweeping over a set of possible target values.

For each data source, we randomly sample $300$ documents. For each document,
we randomly sample up to $100$ text sequences of the specified level
(sentence, paragraph, or passage) for constraint extraction to prevent over-
representation from very long documents. We then randomly sample up to $100$
constraint targets for each constraint structure and data source. We now
discuss source-specific details below:

###  B.2 Text filters

In this section, we describe the text filter heuristics in detail. Note that
which filters to use are source-specific.

  * •

URL. This filter removes any string that contains a pattern that appears to be
a URL. The pattern we find is expressed using the following regex:

r"(http(s)?://)?(www\\.)?[a-zA-Z0-9\\-]+\\.[a-zA-Z]{2,6}

(\\.[a-zA-Z]{2,6})?(/[a-zA-Z0-9\\-]*)*(\?[a-zA-Z0-9\\-=&]*)?"

  * •

All caps. This filter removes any text that only contains capitalized letters,
which may be indicative of a section heading.

  * •

No sentences. This is a filter that tries to detect strings without any valid
sentences in the text. We first sentence tokenize the string. If no “sentence”
contains a period and has length greater than 2, then we remove the string.
Otherwise, we keep it. Future improvements could use a parser or trained
classifier.

  * •

Copyright. This filter removes copyright statements typically found at the end
of articles. It removes any string that contains the copyright symbol “©” or
where the uncased first word is “copyright”.

  * •

Caption. This filter attempts to remove captions, such as those under diagrams
or images. These strings typically follow the format: “Photo: a green car.”.
We heuristically detect such strings by rejecting any string where the number
of characters to the left of the first “:” is less than six characters.

###  B.3 Text post-processing

In this section, we describe the post-processing functions used on the
strings. Note that which post-processing functions to use depends on the data-
source.

  * •

Markdown removal. We remove markdown artifacts using the following
substitution rule: (r’(\\*\\*|__|\\*|_|backslash~\~)(.*?)\1’, r’\2’)

  * •

Consecutive whitespace. Consecutive whitespace is removed with the following
substitution rule: (r’\s{2,}’, ’ ’)

  * •

Single newline to space. Single newlines are replaced with a single space
using the following substitution rule: (r"(?<!\n)\n(?!\n)", " ")

  * •

Bracket removal. We remove brackets from the text using the following
substitution rule: (r’\\[[^\\]]*\\]’, ""). This is useful for removing
references inside the text.

###  B.4 Data sources

Detailed statistics on the number of constraints extracted for each constraint
structure for the grouped, and individual data sources are found in Figures 10
and 9 respectively. None of the datasets used contain PII, as far as authors
are aware.

#### Wiki

We use the 20220301.en train split of the dataset from Huggingface [21]. We
split each document into paragraphs using two newlines as the delimiter
(\n\n). We use three filters for Wiki: URL, caption, and no sentences. For our
passage level constraint, we also omit any text that contains the vertical
line character "|", as these were identified to often be tables. We use a Wiki
specific post-processing function that removes any text before the first
newline character, for any text that contains a newline character. We found
that these are almost always section headings. Wiki is licensed under a CC BY-
SA 3.0 license and GNU Free Documentation License¶¶¶See
https://dumps.wikimedia.org/legal.html.

#### CC-News

We load from the train split of the cc_news dataset on Huggingface Datasets
for convenience. We split each document into paragraphs using a single newline
as the delimiter (\n. We use four filters for CC-News: copyright, URL,
cpation, and no sentences. We do not use any post-processing function. The TOS
for this data can be found at https://commoncrawl.org/terms-of-use/full/.

#### Guten

We use the processed dataset from Gutenberg, dammit:
https://github.com/aparrish/gutenberg-dammit. We split each document using two
newlines as the delimiter (\n\n). We two filters for Guten: all caps, and no
sentences. We post-process the text using four processors, applied in the
following order: markdown removal, bracket removal, single newline to space,
consecutive whitespace to single whitespace. All documents in Guten are in the
public domain in the U.S.

#### Words

For word-level constraints, we iterate over the the words present in the
following newline-separated word list:
http://www.gwicks.net/textlists/english3.zip. We conduct no filtering or post-
processing on the words from the list.

Our entire code, including those used for data extraction will be released
under an MIT license.

##  Appendix C Additional Experimental Results

We note that out of $1132$ constraints, $2$ constraint prompts are blocked by
PaLM-2 API for the guardrailing reason:

  1. 1.

In ccnews_c07: Please generate a sentence containing the word ’charged’,
’been’, ’Father’.

  2. 2.

In ccnews_c14: Please generate a passage with all paragraphs having the last
sentence to be ’Gramercy’s portfolio looks attractive relative to peers’, ’I
am going to add Gramercy Property Trust to my income portfolio this week’, ’An
investment in GPT yields $6.6$ percent’, ’The REIT’s shares have slumped a
whopping $\sim 15$ percent in 2018, but are no longer oversold’ respectively.
Only generate the passage, without extra things like “Paragraph 1" or
“Answer:".

###  C.1 One-shot experiments

To understand if LLM performances are bottlenecked by the zero-shot
instruction format and if example input-output pairs could boost performances,
we did a preliminary one-shot prompting experiment using an internal version
of the dataset before the current Collie-v1, where for each constraint
structure, we use a fixed constraint and its corpus example as an example
input-output pair attached before the constraint prompt. As shown below in
Table 2, results are very similar for both GPT-3.5 and GPT-4, which suggests
the task difficulty is mainly about generation under the constraint instead of
understanding the constraint (by similar examples).

| GPT-3.5 | GPT-4
---|---|---
0-shot | 23.1 | 40.7
1-shot | 23.6 | 39.4
Table 2: 0 vs. 1-shot results across all constraints (%).

###  C.2 Constraint satisfaction rates

Figure 8: Model performance on different constraints and datasets. (a)-(e)
Constraint satisfaction rates of texts generated by GPT-4, GPT-3.5, PaLM,
Vicuna-7B, and Alpaca-7B across various constraints and datasets. Error bars
indicate standard error. The constraint group names can be found in Table 1.
Sample sizes are reported in supplementary Figure 9. (f) Summary heatmap of
model performance on different constraint groups. (g) Summary heatmap of model
performance on different constraints and datasets.

Figure 8 provides a comparison of constraint satisfaction rates for various
models across all tasks. The performance of the models remains consistently
high for a specific constraint structure, regardless of the data source. The
satisfaction rates are summarized in heatmap Figures 8(f)-(g).

Figures 9 and 10 provide detailed information about the dataset size and
sample size for each model in the study. Specifically, we conducted 20 trials
for each instruction prompt in the case of GPT-4 and GPT-3.5. For PaLM, a
total of 30 trials were conducted for each instruction prompt. However, due to
a certain failure rate, the number of generated texts may not be a multiple of
the number of instruction prompts. Vicuna-7B and Alpaca-7B were each run for
10 trials, and they also experienced some low failure rates during the
experiments.

Figure 9: Dataset and sample sizes. (a) Dataset sizes for each constraint and
data source. (b)-(f) Total sample sizes of generated texts from different
models for each constraint and data source. Figure 10: Grouped dataset and
sample sizes. (a) Dataset sizes for each constraint group. (b)-(f) Total
sample sizes of generated texts from different models for each constraint
group.

###  C.3 Additional evaluations

In addition to evaluating binary constraint satisfaction in general, it is
also possible to evaluate particular aspects of text generation with respect
to the constraint and extracted corpus text.

Word validity evaluation. To determine the validity of word-level generations
as English words, we cross-reference the generated words with the word list
available at http://www.gwicks.net/textlists/english3.zip. Since this word
list is not complete, we supplement it by including eight additional uncommon
but valid English words: ’supercalifragilisticexpialidocious’,
’pneumonoultramicroscopicsilicovolcanoconiosis’,
’antidisestablishmentarianism’, ’pseudopseudohypoparathyroidism’,
’extraterrestrializationism’, ’acceleratrix’, ’circumlocutrix’, and
’procrastinatrix’.

Figure 12 illustrates the performance comparison of different models in
generating long words (word01). Notably, GPT-4 demonstrates superior
performance compared to other models in generating long words. However, when
faced with more challenging constraints, such as the requirement for the
$i$-th letter to be ’r’, all models fail to generate a word that satisfies the
constraint (see Figure 8). In this case, GPT-3.5 manages to generate valid
words, while GPT-4 resorts to fabricating words like "coordinasor" to better
conform to the constraints.

Regarding task word03, only GPT-4 is capable of generating words that satisfy
the constraint on the last character. However, it still frequently generates
made-up words. None of the other models are able to generate valid words or
strings that satisfy the given constraint.

[]  []

Figure 11: Word validity. Percentage of generated words that are “valid" words
for a given English vocabulary list. Language models can sometimes generate
plausible words, such as “coordinasor" and “adventudposis", but those are not
common or valid words in modern English. Figure 12: Passage coherence. Average
passage coherence scores rated by GPT-4. Each generated passage was evaluated
through three independent runs, while roughly one trial was taken for each
model. GT-examples are ground truth. The error bars represent the standard
error across the dataset.

Passage coherence evaluation. In order to assess the coherence and flow of
content within the generated paragraphs, we utilize GPT-4 as a third-party
judge to provide coherence scores. For this evaluation, we employ the
following prompt: "Analyze the following passage, then conclude with the
statement ’Thus, the coherency score is $s$,’ where $s$ is an integer ranging
from 1 to 10." We conduct three separate samplings of coherence scores for
each generated text and calculate the average score. This methodology allows
us to quantitatively measure the overall coherence of the generated paragraphs
and gauge their coherence in a relatively consistent and reliable manner.

Figure 12 presents the coherence scores of generated passages for task pass01.
Notably, both GPT-4 and GPT-3.5 consistently outperform the other models in
terms of coherence. Furthermore, GPT-4 achieves a level of coherence that is
comparable to the ground truth passages in the dataset.