# Decrypting Cryptic Crosswords:
Semantically Complex Wordplay Puzzles as a Target for NLP

Josh Rozner Christopher Potts Kyle Mahowald

<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Cryptic crosswords, the dominant English-language crossword variety in the
United Kingdom, can be solved by expert humans using flexible, creative
intelligence and knowledge of language. Cryptic clues read like fluent natural
language, but they are adversarially composed of two parts: a definition and a
wordplay cipher requiring sub-word or character-level manipulations. As such,
they are a promising target for evaluating and advancing NLP systems that seek
to process language in more creative, human-like ways. We present a dataset of
cryptic crossword clues from a major newspaper that can be used as a benchmark
and train a sequence-to-sequence model to solve them. We also develop related
benchmarks that can guide development of approaches to this challenging task.
We show that performance can be substantially improved using a novel
curriculum learning approach in which the model is pre-trained on related
tasks involving, e.g, unscrambling words, before it is trained to solve
cryptics. However, even this curricular approach does not generalize to novel
clue types in the way that humans can, and so cryptic crosswords remain a
challenge for NLP systems and a potential source of future innovation.111Code
to download (from theguardian.com), clean, and process the dataset is publicly
available at https://github.com/jsrozner/decrypt

##  1 Introduction

Modern computational models have made great progress at handling a variety of
natural language tasks that require interpreting the rich syntactic and
semantic structures (Devlin et al., 2018; Radford et al., 2019; Manning et
al., 2020; Rogers et al., 2020). However, in NLP (Bender and Koller, 2020;
Marcus, 2020; Bisk et al., 2020) as in other areas of AI (Lake et al., 2016),
machines still lag humans on tasks that require flexible problem solving,
rapid learning of unseen tasks, and generalization to new domains. Just as
complex games mastered by human experts, such as chess, Go, and video games,
have proved a fertile ground for developing more flexible AI, (Silver et al.,
2018, 2016; Mnih et al., 2015), we propose that creative language games are a
rich area for developing more flexible NLP models. In particular, we argue
that linguistic tasks involving meta-linguistic reasoning (i.e., reasoning
about language qua language) pose an important and significant challenge for
state-of-the-art computational language systems.

Figure 1: Illustration of how the cryptic crossword clue “But everything’s really trivial, initially, for a transformer model” is parsed. The word “initially” is an indicator to apply an initialism function to the string “But everything’s really trivial,” taking the first letter of each word to get BERT. The word “for” is an optional linking word (which connects the wordplay and the definition). The definition part is “a transformer model,” for which a valid answer is BERT. Because this matches the wordplay part and fits the enumeration (which indicates 4 letters), it is a valid answer. Clue type |  Clue example |  Explanation for this example
---|---|---
Anagram: An anagram indicator indicates the letters must be scrambled. |  Confused, Bret makes a language model (4) |  Rearrange the letters of “Bret” to get BERT.
Initialism: An initialism indicator indicates one must take the first letters of a phrase |  But everything’s really trivial, at first, for a language model (4) |  Take the first letters of “everything’s really trivial”
Container: A container indicator indicates the answer is hidden within a larger phrase. |  Language model in somber text (4) |  Extract the word BERT from the phrase “somber text.”
Charade: For a charade clue, each part of the answer is clued sequentially. |  A language model exist? Right time! (4) |  “exist” becomes BE. A standard abbreviation for “right” is R. A standard crossword abbreviation for “time” is T.
Double definition: In a double definition clue, two synonyms or phrases appear next to each other, each of which can refer to the answer. |  Model Sesame Street character (4) |  Bert is a valid answer for “Sesame Street character”, and it is also a model.
Table 1: Sample of 4 common clue types in cryptic crosswords, all
demonstrating clues for the answer: “BERT”.

One such domain is cryptic crossword puzzles. Cryptics are the most popular
style of crossword in the United Kingdom and appear in major newspapers like
_The Times_ and _The Guardian_. They differ from American-style crossword
puzzles in that they have both definition and wordplay components. Consider
this NLP-centric cryptic crossword clue: “But everything’s really trivial,
initially, for a transformer model (4).” The wordplay part is “But
everything’s really trivial, initially.” The word initially in this context is
used as an indicator, which tells the solver to take the initial letter of
each of the preceding words (but everything’s really trivial) to get the
answer word: “BERT”. The definition part of the clue is “a transformer model,”
which is a semantically valid description of BERT. Because both the wordplay
and the definition components lead to the same 4-letter word (which is what
the enumeration calls for), we can be reasonably confident that BERT is the
correct answer. Many clues require the application of multiple, potentially
composed functions (i.e. the result of one transformation, like taking a
synonym, becomes the input to the next), with multiple indicators, to solve
the wordplay.

While cryptic crosswords pose a challenge to novice solvers, expert solvers
draw on a combination of world knowledge, domain-specific cryptic crossword
knowledge, linguistic knowledge, and general problems solving. Expert solvers
know the rules that govern cryptic crosswords, but they also reason about them
flexibly and apply them to solve novel clues. In the psychology literature, it
has been claimed that cryptic crosswords depend on domain-general intelligence
(Friedlander and Fine, 2020). Moreover, Friedlander and Fine (2018) cite
cryptic crosswords as an ideal domain for studying the “aha moment” in humans
because they can be solved by experts with high accuracy (but often not at
first glance), can be easily created by expert humans, and require drawing on
a diverse range of cognitive abilities.

Therefore, we believe that cryptic crosswords are an excellent domain for
developing computational language systems that “learn and think like humans”
(Lake et al., 2016). In particular, we argue that cryptic crossword clues pose
an interesting and important challenge for modern NLP.

In this paper, we first present a dataset of cryptic crosswords clues taken
from theguardian.com, consisting of 142,380 cleaned clues from 5,518 puzzles
over 21 years. Second, we present a series of computational benchmarks, along
with a sequence to sequence approach that uses the pretrained T5 model, to
characterize the problem space—and to illustrate why cryptic crosswords pose a
particular challenge for existing NLP approaches. Finally, we present a
curriculum learning approach, in which our system is first trained on related
tasks (e.g., an augmented word descrambling task) before being unleashed on
real cryptic crossword clues. This approach meaningfully improves on our
standard T5 sequence-to-sequence approach and on the best performing model in
Efrat et al. 2021—concurrent work that presents a similar dataset and baseline
T5 approach.

While we show that our sequence to sequence approach can learn interesting
features of the problem space, including learning some meta-linguistic facts
about word length, fully solving cryptic crosswords remains a challenge for
NLP. In particular, we show that the Transformer-based approach suffers
significantly when the test set is constructed so as to avoid having answer
words that also appear in the training set. Moreover, although we introduce a
novel method that considerably improves T5’s performance, we are still far
below expert human performance. To that end, we hope that this dataset will
serve as a challenge for future work.

##  2 Background and Related Work

###  2.1 Cryptic Crosswords

Standard cryptic crossword clues generally have two parts: a definition part
and a wordplay part. What makes cryptics hard is that there is huge variety in
the kind of wordplay that can occur. In the introduction, we discussed a type
of cryptic clue that requires extracting the initial letters of a sequence of
words. Another common type of wordplay is the anagram clue type, where a
sequence of letters needs to be scrambled to find a new word. Anagrams are
usually indicated by words like confused, drunk, mixed up, or any other word
in the semantic space of motion, confusion, alteration, accident, etc. (It
would be difficult to construct a list of all possible anagram indicators, but
expert solvers learn to identify indicators of this type.) Clues also have an
enumeration which says how many words and letters are in the answer. For
instance the enumeration “(8, 4)” means the answer consists of two words, the
first word being 8 letters long and the second word being 4 letters long.
Table 1 shows a variety of possible cryptic clues for the word BERT. These
represent only a subset of the many possible types of cryptic clues.

###  2.2 Prior Work

While there is an existing literature on puns and wordplay in NLP He et al.
(2019); Kao et al. (2013); He et al. (2019); Luo et al. (2019) as well as on
solving American-style crosswords Ginsberg (2011); Littman et al. (2002);
Shazeer et al. (1999), there has been relatively little prior work using NLP
methods on cryptic crosswords. Hart and Davis (1992) laid out a computational
framework for solving the problem, and Hardcastle (2001, 2007) proposed some
rule-based solutions. The app Crossword Genius, created by William Tunstall-
Pedoe, solves cryptic crossword clues and gives human-understandable
explanations, but it is proprietary and not available for testing. Deits
(2015) offers a rule-based solution, which can also output explanations, and
which we test on our dataset. Most recently, in work concurrent to ours and
not known to us until shortly before completing our paper, Efrat et al. (2021)
released a dataset of cryptic crossword clues along with a T5-based solution.
In Section 7.4, we provide results demonstrating that our curricular approach
improves on their results using the same model (T5-large) on their Cryptonite
dataset.

##  3 Dataset

We present a cleaned dataset of cryptic crossword clues drawn from puzzles
published in _The Guardian_ between July 23, 1999, and October 8, 2020.222Each
puzzle can be accessed at
https://www.theguardian.com/crosswords/cryptic/puzzle_id

###  3.1 Preprocessing

To produce the clean dataset, we remove 15,360 clues that interact with other
clues in the same puzzle, as well as 231 clues that are ill-formatted (e.g.,
have a solution length not matching the length enumeration, unparsed HTML
characters, etc.). We further remove 1,611 exact duplicates, which are clues
with identical answers and clue strings. Code to fully replicate our data
download and pre-processing pipeline is available in our project code
repository.

###  3.2 Dataset Properties

The cleaned dataset has 142,380 cryptic crossword clues from 5,518 puzzles.
Clues in our dataset have answers consisting of one to six words, with 97.4%
having one or two-word answers; the majority (83.3%) have one-word answers.
The dataset has 55,783 unique answers and 50,525 unique answers up to plural
inflection, giving a mean frequency of 2.55 clues per unique answer (2.82 up
to plural inflection).

###  3.3 Dataset Splits

We consider three splits for experimental work and model assessment:

##### Naive split

A simple 60/20/20 split into train, dev, and test.

##### Disjoint split

A split that ensures that all clues with the same answer appear in only one of
the three sets. That is, if all clues for which the answer word is BERT appear
in the training set, then no clues for which the answer is BERT will appear in
the test set or dev set.

##### Word-initial disjoint split

A split designed to make the training, eval, and test sets maximally distinct
by avoiding having similar words (e.g. inflections) in the same set. To
construct this set, we enforce the rule that all clues with answers that start
with the same two letters will appear in the same set. For example, all clues
that have answers starting with ‘ab’ like “abacus,” “abaci,” “abdicate,”
“abdicates,” “abdicated,” “abdication” will occur in a single split.

Model |  Random split | Fully disjoint split
---|---|---
Top correct |  Top 10 contains | Top correct | Top 10 contains
dev | test | dev | test | dev | test | dev | test
WordNet | 2.8 | 2.6 | 10.8 | 10.7 | 2.6 | 2.6 | 10.6 | 10.5
Rule-based | 7.2 | 7.3 | 14.8 | 14.7 | 7.4 | 7.3 | 14.9 | 14.5
KNN (no lengths) | 5.6 | 5.6 | 9.9 | 10.1 | 0.0 | 0.0 | 0.0 | 0.0
KNN (lengths) | 6.0 | 6.1 | 11.2 | 11.3 | 0.0 | 0.0 | 0.0 | 0.0
T5 (no lengths) | 15.3 | 15.6 | 29.4 | 30.0 | 0.9 | 1.0 | 4.8 | 5.1
T5 (lengths) | 16.0 | 16.3 | 33.1 | 33.9 | 1.1 | 1.1 | 5.6 | 5.8
T5: ACW + ACW-descramble | 21.5 | 21.8 | 42.2 |  42.4 | 6.1 | 6.5 | 18.9 | 20.0
Table 2: Results for the WordNet baseline, KNN model, T5-base, and T5-base
with curriculum learning, in percent of correct answers produced for the naive
split (dev set and test set) and for the word-initial disjoint split (dev and
test set), restricted to outputs of correct length.

##  4 Metrics

Our primary goal is to produce the correct answer to each cryptic clue. Given
that each cryptic clue in a puzzle has a hard length constraint in the form of
the puzzle grid and answer-length enumeration, we take as our primary metric
whether the top-ranked output is correct, after filtering to outputs of the
correct length.

Since cryptic clues are written to be solved as part of a larger puzzle, human
solvers typically rely on information from other, interlocking answers (i.e.
overlap with clues that they have already solved) to come up with the correct
answers for trickier clues. While we do not make such information available to
our solver (instead formulating the task as solving clues in isolation), we
also include the following as a metric: the proportion of the time that the
answer is contained in the top 10 outputs (after filtering to answers of the
correct length). This is a useful heuristic, since if we were to introduce
information from elsewhere in the answer grid, solvers would likely be able to
identify the correct answer word if it appeared in the list of 10 candidates.
For instance, the best-performing crossword solver for American-style (non-
cryptic) crosswords relies heavily on satisfying grid constraints Ginsberg
(2011).

##  5 Baseline Models and Results

To characterize how relatively straightforward solutions do on this dataset,
we test three non-neural baselines: a WordNet-based heuristic model, a
k-nearest-neighbor bag of words model (KNN BoW), and a rule-based model Deits
(2015).

###  5.1 WordNet

Our first baseline takes advantage of the fact that the definition part of a
cryptic clue always appears at the beginning or end of the clue. For instance,
in the clue for BERT in Table 1, “Model Sesame Street character,” the word
“model” appears at the beginning and is a definition (in this case, a
hypernym) for the answer “BERT”.

Taking advantage of this fact, we use WordNet (Fellbaum, 1998), a large
database of English word meanings, to build a reverse dictionary via the
synonym, hyponym, and hypernym graphs. We use LemmInflect (Jascob, 2019) to
get all inflections of the words in the initial output.

We provide an upper bound for this method by noting that, when including
synonyms and hyponyms/hypernyms up to depth 3, and inflecting all outputs, our
definition sets contains the correct answer 22% of the time. However, since
this model lacks a mechanism to effectively rank outputs, we obtain the best
performance on this model restricting our reverse lookup to synonyms, hyponyms
to depth 1, not adding inflected forms, and ranking by character-level
overlap. Using this approach, we achieve accuracies of 2.6% (for the correct
answer being the one produced by the model) and 10.7% (for the correct answer
appearing in the top 10 candidates) on our test set metrics.

While this approach achieves some success, it is inherently limited, since it
cannot handle clues in which the definition part is multiword or phrasal.

###  5.2 KNN BoW

Our second baseline is the KNN BoW. The logic of this approach is, for each
clue, to identify the clue in the training set most similar to that clue in
lexical space. To implement this baseline, we use scikit learn’s (Pedregosa et
al., 2011) CountVectorizer and KNeighborsClassifier. We find that model
performance is best with 1-grams and degrades if longer n-grams are used in
the vectorizer. We test with and without appending the length specification to
the clue. Without lengths, we achieve performance of 5.6% and 10.1% on test
set metrics; with lengths we achieve 6.1% and 11.3%.

###  5.3 Rule-based

For another baseline on our dataset, we use the rule-based approach from Deits
(2015). This solver implements anagrams, initialisms, substrings (initial,
middle, final), insertions, and reversals in a rule-based way. 333Deits (2015)
has a more recently implemented solver in Julia that was used by Efrat et al.
(2021). We use the Python version, which may have small differences from the
Julia version.

While the rule-based version includes a number of common clue types, an
inherent limitation of this approach is that it is difficult to enumerate all
possibilities. For instance, the Deits (2015) solver does not include charade-
type clues, nor does it include double definitions. The rule-based solver uses
WordNet’s (Fellbaum, 1998)’s word similarity functionality to rank outputs,
meaning that, in general, it will fail on clues that have phrasal definitions.
Another limitation is that the rule-based model is slow. We set a timeout of
120 seconds (timed-out clues usually still return some answers) and report an
average time to solve a clue of roughly 40 seconds. This results in a total
time to evaluate on 28,476 clues of approximately 300 CPU hours, substantially
slower than the 1–2 minutes needed for the WordNet baseline and the $\approx$5
minutes for KNN BoW. The rule-based solver achieves 7.3% and 14.7% on test set
metrics, outperforming our KNN and WordNet baselines.

##  6 T5 Models and Results

We present two main sequence-to-sequence solutions to the cryptics task. The
first is a straightforward sequence-to-sequence approach, fine-tuning the
Transformer-based (Vaswani et al., 2017) T5-model (Raffel et al., 2020) on our
cryptic crossword training set. The second builds upon this approach by
introducing a novel curriculum-learning paradigm that first trains the model
on related problems before training on full cryptic clues.

Our motivation for using Transformer-based models is twofold. First, rule-
based approaches are inherently limited to clues of the sort that have been
seen before, whereas human solvers can flexibly understand new clue types with
novel indicator words and novel definitions. Pre-trained contextual embedding
models are a promising candidate for this type of flexibility, in that they
have a strong notion of semantic similarity and access to positional
information.

Second, we believe there is inherent value in testing Transformer-based
approaches on a task like this one, which requires not just linguistic
reasoning but meta-linguistic reasoning, for example about features like word
lengths and anagrams. Whether massive pre-trained transformer models can learn
this sort of information is an open question in NLP (one explored by Brown et
al. (2020) for GPT-3), and we believe our results can be informative in this
regard.

###  6.1 Data and Task Formulation

To fine-tune T5 to our task, we translate each clue into input and target of
the following form (i.e. appending length enumeration to the clue string), and
setting as target the answer. => separates input from target. For instance, a
training instance for our BERT clue would look like the following: But
everything’s really trivial, initially, for a transformer model (4) => bert

Starting from pre-trained embeddings, we fine-tune T5 to produce the target
answer for each input. We evaluate on the dev split, using beam-search
generation with five beams, for each dev example. For test evaluation, we use
the model with the highest number of dev set clues whose top ranked beam
generation is correct (i.e. exact character match of output with target, after
removing whitespace). During test evaluation, we generate 100 outputs for each
input (100 beams with 100 output sequences). After filtering to the outputs
that have the correct length (removing any whitespace characters), we report
the percentage of test-set clues whose top answer is correct and whose top 10
outputs contain the answer.

###  6.2 Vanilla seq2seq Approach

We use T5-base, which can be fine-tuned to convergence on a single GeForce RTX
3090 GPU in roughly 100 minutes. We start with Hugging Face’s (Wolf et al.,
2020) pretrained models, and optimize with Adafactor (Shazeer and Stern, 2018)
using the relative step and warmup initialization options, as implemented in
the Hugging Face library. We use a batch size of 256 sequences with per-batch
truncation-to-longest (via Hugging Face’s T5FastTokenizer).

We train with a patience of 15 epochs and select the best model according to
dev set performance, based on whether the top answer (over 5 beam search
generations) is correct.

For our naive split: If we take just the top answer, the T5-base solver solves
16.3% of the clues (16.0% on dev). For 33.9% of clues (33.1% for dev), the
correct answer appears in the top 10 answers. As can be seen in Table 2, this
outperforms all non-neural baselines.

###  6.3 Curriculum Learning

| Percent correct
---|---
Curricular dataset | full dev set | anagram subset
Baseline (no curricular) | 15.7 | 13.7
ACW | 18.3 | 14.4
ACW-descramble | 13.1 | 21.4
ACW + ACW-descramble | 20.2 | 24.0
ACW + ACW-descramble-word | 17.8 | 18.3
ACW + anagram | 17.1 | 19.1
ACW + ACW-descramble + anagram (7:6 ratio of pretrain exs.) | 20.1 | 27.1
Table 3: Results for various curricular approaches (9.6m pretrain examples) on
the random split. Metrics are percent of correct answers (without length
filter, 5 beams) in the entire dev set and in the subset of the dev set that
are anagram clue types.

The problem of solving cryptic crossword clues is fundamentally different from
the ordinary natural language context on which T5 is pre-trained. Thus, one
possible impediment to the performance of our model is that it has to learn
many sub-parts of the cryptic clue problem simultaneously: how to look up
definitions, how to identify wordplay indicators, how to perform wordplay
operations, etc. Each of these steps is challenging.

A second challenge is that the model needs to be able to output answers that
it has not seen in training. This is especially important for the disjoint
split, but also relevant to our random split, since our training set does not
include all possible crossword answers, and any puzzle is likely to contain
some novel answer words.

To ameliorate these issues, we use a curricular approach. Broadly, the
approach consists of two steps. First, we take the pre-trained T5 model and
train it on a supplementary task (or set of tasks). Second, we train on the
primary dataset of crytpic clues. During the latter step, we intermittently
show batches from the initial training set, in order to prevent catastrophic
forgetting (French, 1999). We tune the following hyperparameters: the number
of curricular epochs, whether the Adafactor optimizer is reset before primary
training (only affects non-constant LR training regime), and the frequency of
curricular subtask review during primary training.

####  6.3.1 Curricular Datasets

For our curricular training, we create four supplementary data sets, all built
from a public dataset of 6.3m American crossword clues (Pwanson, 2021,
henceforth ACW for American Crossword). American crossword clues are typically
synonyms or definitions and thus correspond to the “definition” part of
cryptic clues.

From ACW, we first produce a cleaned set of clue/answer pairs, consisting of
2.5 million clues (removing roughly 3 million exact duplicates and roughly
800k clues that are unlikely to be synonyms or paraphrases, such as fill-in-
the-blank clues). We use this cleaned ACW set to generate our four supplement
datasets: ACW, ACW-descramble, ACW-descramble-word, and anagram. Each dataset
has its own task label, which is passed to the model as part of the string.

##### ACW

ACW is the set of straightforward American-style crossword clues, prepending
“phrase:” as a task label, as done by Raffel et al. (2020) in their original
presentation of T5. For example, a clue for which the answer is “petal” is
phrase: flower part (7).

##### ACW-descramble

We synthesize ACW-descramble, in which we randomly choose to prepend or append
scrambled answer letters to the paraphrase. We use the task label
“descramble.” For example, we can scramble “petal” and randomly place it at
the beginning (descramble: etalp flower part (7)) or end (descramble: flower
part etalp (7)) of a clue.

##### ACW-descramble-word

This supplementary dataset omits the phrasal definition (i.e., the clue) and
instead simply asks the model to descramble a word, with length enumeration
given. We use “descramble word” as the task label: descramble word: etalp (7).

##### Anagrams

Finally, we synthesize an anagram dataset with an anagram (a scrambled version
of a word which is itself also a valid word) and an anagram indicator (e.g.,
“mixed up,” “drunk”, “confusingly”) of the sort that are typically used in
cryptic crosswords. An example of a clue in this dataset for is anagram:
confusingly plate (5) (rearrange the letters of ‘plate’ to get ’petal’). This
last type of clue (in the anagram dataset) simulates the anagram type of
wordplay in cryptic clues, omitting the the definition part, whereas clues in
the ACW datset simulate the definitional part of cryptic clues (without
wordplay).

The logic of this approach is to guide our model on these sub-parts before
building up to fully compositional cryptic crossword clues.

Descrambling and anagramming are only a subset of the wordplay operations
available in crytpic crosswords, but the same approach could be extended to
other types of wordplay.

####  6.3.2 Methods

Using the supplemental datasets we constructed for curriculum learning, we
tested our curriculum learning approach by supplementing the full cryptic
training set with curricular pre-training on the ACW and ACW-descramble
supplementary data sets, as well as selected combinations of the supplementary
data sets. In Table 3, we report results for our curricular approach training
on the following supplementary datasets and combinations: ACW, ACW-descramble,
ACW + ACW-descramble, ACW + ACW-descramble-word, ACW + anagram, ACW + ACW-
descramble + anagram.

We use the same T5 training parameters as in our vanilla model and hand-tune
the number of pretraining epochs, generally finding that training nearly to
convergence on a held-out validation set for the primary pretraining task is
optimal. We reset the optimizer between pretraining and primary training, and
we review the curricular tasks by introducing them during the primary training
phase, at a ratio of 6 curricular batches for every 20 primary task batches.

We find that, when training on multiple tasks (i.e when we are in the
curricular setting), using task labels improves performance. We include length
enumeration in all curricular tasks since we observed that doing so improves
performance.

In order to reasonably compare across the different curricular datasets, we
set the number of training examples to be the same for each approach. Since 4
epochs of the ACW set involves 9.6m examples, we match to this number. Thus,
for the experiments with two supplementary datasets (e.g., ACW + ACW-
descramble), we train for 2 epochs, each with twice as many examples.

We train with a patience of 10 epochs (reduced since the model converges
faster than without curricular training), and select the best model according
to dev set performance, based on whether the top answer (over 5 beam search
generations) is correct. We use the best method based on these metrics for our
final curricular evaluation and report results in Table 3.

Our results show that pretraining on the ACW set always improves performance.
Although training on a combination ACW + ACW-descramble further improves
performance, training solely on the ACW-descramble seems to degrade
performance relative to baseline.

In order to explore whether the subtask pretraining improves performance
across the board or just on the clue types directly involved (e.g., anagrams),
we used a simple heuristic to search for and label anagram clue types in the
cryptic crossword set and explored performance on just this set (the “anagram
subset” column in Table 3). Mixing in the anagram subtask produces nearly the
same overall performance as with ACW + ACW-descramble, but does improve
performance on the subset of the data involving anagrams. Thus, it seems that,
to some extent, pre-training geared around a particular clue type can improve
performance on that subtask, but perhaps at the expense of performance on
other clue types. Nonetheless, as seen in Table 3, the curricular approach
substantially improves performance relative to the vanilla T5 approach.

Furthermore, we show that these gains in performance hold for the disjoint set
in Table 2.

##  7 Model Analysis

###  7.1 Learning Meta-Linguistic Properties: Output Length and Number of
Words

Model |  % samples containing answer (no len filter) |  % sample outputs with correct length |  % sample outputs with correct word count
---|---|---|---
dev |  test |  dev |  test |  dev |  test
KNN |  |  |  |  |  |
\- (no lengths) |  6.5 |  6.6 |  13.4 |  13.3 |  70.7 |  70.7
\- (lengths) |  10.6 |  10.7 |  85.4 |  85.3 |  89.7 |  89.6
T5-base |  |  |  |  |  |
\- (no lengths) |  19.0 |  18.8 |  16.0 |  16.2 |  74.2 |  74.1
\- (lengths) |  27.5 |  28.1 |  48.3 |  48.5 |  97.9 |  97.9
Table 4: Sample metrics for models that have access to the meaning of length
enumeration. Metrics are calculated over the top 10 outputs for each clue (a
sample) without length filtering. Models tested on naive split (dev and test).

Beyond characterizing each model’s ability to generate correct outputs, we are
interested in the extent to which each model learns underlying features
relevant to the task, such as how long the answer should be (information it
has access to through the enumeration given with each clue).

For both the KNN and the T5 models, we find that including length enumeration
improves models’ abilities to generate correct answers, as can be seen in
Table 2. (The Wordnet and rule-based models cannot incorporate this
information, except as the hard filter we apply in restricting to answers of
the correct length for the crossword grid, so we do not discuss them in this
analysis.)

To further study the extent to which the models learn length information, we
look at model performance without the length filter and ask, not only how
often the list of top 10 candidates contains the correct answer, but also how
often the top 10 candidates are the correct length, both in characters and in
words.

The results of this analysis are in Table 4. Both the KNN model and the T5
model seem able to pick up on length information and more often generate
answers of the correct length when the enumeration is provided. The KNN model
learns length in a somewhat trivial way: a clue for the word PETAL will always
have the enumeration “(5).” And so, for a bag-of-words nearest neighbor
approach that cares about lexical overlap between clues, it is relevant that
all PETAL clues will have at least one “word” in common: the “(5).” This
effectively guarantees at least some overlap.

The fact that T5 seems to learn both character-level and word-level length
information is perhaps more interesting. It is particularly proficient at
learning when an answer is more than one word. Recall that multiword answers
are indicated with an enumeration that has two numbers separated by a comma,
as in “(4, 6)” (indicating an answer composed of 4-letter word plus a 6-letter
word, like ALAN TURING). Based on the fact that T5 generates a high proportion
of multi-word answers when the enumeration calls for it, it seems plausible
that the sequence-to-sequence model is learning the correspondence between the
enumeration (in particular the comma(s)) and the presence of a space or spaces
in its output.

###  7.2 Disjointness

Dataset | Top output | Top 10 outputs
---|---|---
correct | contain answer
dev | test | dev | test
Random split |  |  |  |
\- Full split | 16.0 | 16.3 | 33.1 | 33.9
\- Subset not in train set | 3.0 | 2.8 | 9.5 | 9.7
\- Subset not in train set, up to plurals | 2.3 | 2.2 | 7.6 | 8.0
Disjoint split: |  |  |  |
\- Basic disjoint | 3.3 | 3.2 | 12.6 | 12.9
\- Word-initial disjoint split | 1.1 | 1.1 | 5.6 | 5.8
Table 5: T5-base performance under various tests of disjointness: performance
on the random split and subsets of the random split, performance on the basic
disjoint and word-initial disjoint subsets

Based on the performance of the KNN model on the naive data split, we see that
at least some answers can be learned merely by picking up on similarity to
previous clues. Thus, there is an open question as to what explains the
relative success of the T5 model approaches: are they picking up on similarity
to previous seen clues? Or are they understanding something about the
compositional and functional structure of the cryptic clues?

To assess the extent to which the T5 model relies on having seen similar clues
for the same word, we first segment performance on the random split into
groups based on whether the answer occurs in the train set. Performance is
considerably lower on the 8,354 examples (29.3%) of the dev set clues whose
answers do not occur in the train set.

We further assess this question by training on two disjoint datasets,
described in 3: the naive disjoint split (e.g., if ‘BERT’ is seen as an answer
in train, then ‘BERT’ cannot be an answer in dev or test), and the word-
initial disjoint dataset (words with the same two initial characters cannot
appear in both train and test). The T5 model achieves 3.3% accuracy on the
naive disjoint dev set and only 1.1% accuracy on the word-initial disjoint
split. We attribute this drop between the naive disjoint set and the word-
initial disjoint set to the fact that the model seems to benefit from seeing
similar clues for related words, and related words, like inflected forms,
start with the same two letters.

As can be seen in Section 7.4, the challenge of the fully disjoint split is
not substantially ameliorated by a larger model (T5-large) trained on the
larger Cryptonite dataset.

###  7.3 Wordplay: Minimal Task

Split and task | Match top | Match any
---|---|---
| sampled | sampled (10)
Random split |  |
\- Descramble | 63.8 | 91.6
\- Descramble w/ phrase | 79.4 | 91.2
Disjoint split |  |
\- Descramble | 3.7 | 12.5
\- Descramble w/ phrase | 12.4 | 24.4
Table 6: Descrambling task under random and disjoint splits, with and without
paraphrase given. Performance reported without filter.

We know that the SentencePiece tokenization scheme used by T5 may pose a
problem for subword and character-level manipulations. To characterize whether
the T5 model is capable of wordplay-like tasks, we test it on a simple
descrambling task. In effect, this task can put an upper bound on how well the
full model can actually do a wordplay similar to what is necessary to arrive
at a “full understanding” of the answer (that is, without simply relying on
heuristics or solving the clue by guessing the definition part).

We start with the ACW dataset from Section 6.3 We further restrict it to words
found in a dictionary (i.e. removing multiword answers), and then downsample
to 10% of the dataset producing 180k examples. We note that this dataset does
contain multiple clues that map to the same answer but that there are no exact
duplicates (i.e. although the answer is the same, the clue strings differ). We
test under a random and disjoint split of the data, as well as under two task
setups.

Using the ACW set which maps from clue to answer, we produce examples of the form scrambled(answer) => answer for the first task and of the form scrambled(answer) | clue => answer for the second task. The second task is designed to mimic the cryptic setup, in which we have a wordplay whose output is conditioned on a phrasal synonym. In this case our wordplay is the implicit descramble function.

We present results for this wordplay subtask in Table 6. Accuracy (as measured
by how often the correct answer is in the top 11 candidates) is high (over
90%) when the answer word appears in both the training and test set, even
though the actual scrambled form of the word can be quite different. But
accuracy drops considerably when the training and test sets are disjoint.

To see whether this marked drop in performance was simply because the T5 model
cannot produce answers that it has not seen in its training set, we ran an
experiment in which the model simply had to reproduce answers verbatim (i.e.,
a copy task). We use the same four datasets as just described, but replace all
occurrences of scrambled(answer) with answer, i.e., as if we used the identity
function in place of the scramble function. The model achieves 100% accuracy
on all four versions of the dataset, suggesting that the inability of the
T5-based model to do the descrambling task on the disjoint set is not due
merely to an inability to generate an answer that has not been seen in
training.

###  7.4 Comparison to Efrat et al.

Split | Efrat et al | Our replication | Curricular
---|---|---|---
|  | of Efrat et al | (our best approach)
Efrat ‘naive’ (test) | 56.2 | 53.2 | 52.1
Efrat ‘official’ (test) | 7.6 | 10.9 | 19.9
Word-initial disjoint (test) | – | 4.9 | 12.8
Table 7: Performance of T5-large as reported by Efrat et al. (2021), in our
replication of their work, and using our best-performing curricular approach
(ACW + ACW-descramble). Metric is correctness of top output using 5 beams over
the test set for each split.

Contemporaneously, Efrat et al. (2021) presented a similar dataset and trained
T5-large to produce answers to cryptic clues. While Efrat et al. (2021) reach
the conclusion that train/test disjointness is important in this problem, they
stop short of creating a truly disjoint dataset, overlooking T5’s robustness
to plural and other inflections. The word-initial disjoint split that we
produce addresses this oversight. (Note that our “naive disjoint split” is
equivalent to their “official disjoint split.”)

In order to directly compare our own results to to those of Efrat et al.
(2021), we first replicate their results by training and testing T5-large (the
model they use) on their ‘naive’ and ‘official’ splits. Note that their
‘naive’ is the same as our naive split, that their ‘official’ is the same as
our disjoint (i.e. answer-disjoint) split. We select the top model based on
dev-split performance and evaluate on the test split. For both model selection
and test evaluation, we use the same metric used in their paper: percent
accuracy as percentage of clues where the model’s top output (over 5 beams) is
correct. Having shown that we achieve slightly lower accuracy on their naive
split and slightly high accuracy on their official split, we next show a
considerable decline in performance under a truly disjoint split (10.9% to
4.9%). This illustrates that, for a truly disjoint split, training a larger
model on more data does not lead to real “success” on the task. (As a point of
comparison, t5-base achieved 1.1% on the true disjoint split of our dataset).

Next, we apply our curricular pretraining approach to T5-large, using our best
performing ACW + ACW-descramble curriculum (three epochs of pretraining) and
show that it considerably improves primary task performance. In particular,
performance on the Cryptonite ‘official’ split almost doubles, from 10.9% to
19.9%, and performance on the true disjoint split more than doubles, improving
from 4.9% to 12.8%. Performance on the ‘naive’ split does not change
considerably with curricular pretraining. This may be because the Cryptonite
training set itself is already a reasonably representative distribution for
the test set, so supplementary data actually very slightly reduces
performance. Our results are presented in Table 7.

##  8 Conclusion

Our contribution is, first, to introduce a dataset of cryptic crossword clues
and answers that can be used as a task for future work and, second, to offer a
set of benchmarks and models that attempt to solve the task.

In particular, we found that a T5-based solution, with curriculum learning,
shows some promise at solving cryptic crossword clues. It achieves this
success despite being exposed in its early training phase to only a small
subset of the sub-tasks (namely descrambling and definition matching) that are
core parts of solving cryptic crossword clues. In future work, it may be
possible to extend this approach to a wider variety of sub-tasks by using
heuristics to generate additional curricular datasets.

That said, an approach which requires enumerating possible clue types is
inherently limited by the time and imagination of the people training the
model. Expert humans flexibly learn and adapt to new clue types and recognize
novel ways in which they are combined. For instance, a recent cryptic
crossword contained the clue: “Auntie is primed for college, briefly (3).” The
answer is “UNI”, which is derived by taking the “prime number” letters of
“auntie” (namely, the letters in positions 2, 3, and 5). These form the answer
“UNI”, which is a synonym for “college.” There are no clues like this in our
database, but an expert solver can draw on their experience to understand how
to solve this clue.

Being able to solve novel clue types like this points to the need for a system
which can draw on a rich base of lexical and linguistic knowledge like that
contained in T5 (that “college” and “uni” are synonyms, that the word “prime”
has a meaning in math, that “briefly” indicates that the word being clued is a
shortening of a longer word “university”). But it also needs to be able to
more flexibly learn different kinds of wordplay functions and how to
functionally compose them to create the answer word. Given the need to learn
novel functions, it may be worth exploring other approaches to this problem,
like the compositional recursive learner (Chang et al., 2019) or the recursive
routing network Cases et al. (2019).

In that sense, we believe that the cryptic crossword task serves as a good
candidate task for those interested in building NLP systems that can apply
linguistic knowledge in more creative, flexible, and human-like ways.

##  9 Ethics

To respect the intellectual property of the crossword creators and publisher,
we do not release the dataset but make available the code we used to download
and clean it.

## References

  * Bender and Koller (2020) Emily M Bender and Alexander Koller. 2020.  Climbing towards nlu: On meaning, form, and understanding in the age of data.  In _Proc. of ACL_.
  * Bisk et al. (2020) Yonatan Bisk, Ari Holtzman, Jesse Thomason, Jacob Andreas, Yoshua Bengio, Joyce Chai, Mirella Lapata, Angeliki Lazaridou, Jonathan May, Aleksandr Nisnevich, Nicolas Pinto, and Joseph Turian. 2020.  Experience grounds language.
  * Brown et al. (2020) Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020.  Language models are few-shot learners.  _arXiv preprint arXiv:2005.14165_.
  * Cases et al. (2019) Ignacio Cases, Clemens Rosenbaum, Matthew Riemer, Atticus Geiger, Tim Klinger, Alex Tamkin, Olivia Li, Sandhini Agarwal, Joshua D. Greene, Dan Jurafsky, Christopher Potts, and Lauri Karttunen. 2019.  Recursive routing networks: Learning to compose modules for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 3631–3648, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Chang et al. (2019) Michael B. Chang, Abhishek Gupta, Sergey Levine, and Thomas L. Griffiths. 2019.  Automatically composing representation transformations as a means for generalization.
  * Deits (2015) Robin Deits. 2015.  rdeits/cryptics.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Efrat et al. (2021) Avia Efrat, Uri Shaham, Dan Kilman, and Omer Levy. 2021.  Cryptonite: A cryptic crossword benchmark for extreme ambiguity in language.
  * Fellbaum (1998) C. Fellbaum. 1998.  _WordNet: An electronic lexical database_.  MIT Press, Cambridge, MA.
  * French (1999) Robert M. French. 1999.  Catastrophic forgetting in connectionist networks.  _Trends in Cognitive Sciences_ , 3(4):128–135.
  * Friedlander and Fine (2018) Kathryn J Friedlander and Philip A Fine. 2018.  “the penny drops”: Investigating insight through the medium of cryptic crosswords.  _Frontiers in psychology_ , 9:904.
  * Friedlander and Fine (2020) Kathryn J Friedlander and Philip A Fine. 2020.  Fluid intelligence is key to successful cryptic crossword solving.  _Journal of Expertise_ , 3(2):101–132.
  * Ginsberg (2011) Matthew L Ginsberg. 2011.  Dr. fill: Crosswords and an implemented solver for singly weighted csps.  _Journal of Artificial Intelligence Research_ , 42:851–886.
  * Hardcastle (2001) D Hardcastle. 2001.  Using the bnc to produce dialectic cryptic crossword clues.  In _Corpus Linguistics 2001_ , pages 256–265.
  * Hardcastle (2007) David Hardcastle. 2007.  _Riddle posed by computer (6): the computer generation of cryptic crossword clues._ Ph.D. thesis, Citeseer.
  * Hart and Davis (1992) M Hart and Robert H Davis. 1992.  Cryptic crossword clue interpreter.  _Information and Software Technology_ , 34(1):16–27.
  * He et al. (2019) He He, Nanyun Peng, and Percy Liang. 2019.  Pun generation with surprise.  _arXiv preprint arXiv:1904.06828_.
  * Jascob (2019) Brad Jascob. 2019.  bjascob/lemminflect.
  * Kao et al. (2013) Justine T Kao, Roger Levy, and Noah D Goodman. 2013.  The funny thing about incongruity: A computational model of humor in puns.  In _Proceedings of the Annual Meeting of the Cognitive Science Society_ , volume 35.
  * Lake et al. (2016) Brenden M. Lake, Tomer D. Ullman, Joshua B. Tenenbaum, and Samuel J. Gershman. 2016\.  Building machines that learn and think like people.
  * Littman et al. (2002) Michael L Littman, Greg A Keim, and Noam Shazeer. 2002.  A probabilistic approach to solving crossword puzzles.  _Artificial Intelligence_ , 134(1-2):23–55.
  * Luo et al. (2019) Fuli Luo, Shunyao Li, Pengcheng Yang, Baobao Chang, Zhifang Sui, Xu Sun, et al. 2019\.  Pun-gan: Generative adversarial network for pun generation.  _arXiv preprint arXiv:1910.10950_.
  * Manning et al. (2020) Christopher D Manning, Kevin Clark, John Hewitt, Urvashi Khandelwal, and Omer Levy. 2020.  Emergent linguistic structure in artificial neural networks trained by self-supervision.  _Proceedings of the National Academy of Sciences_.
  * Marcus (2020) Gary Marcus. 2020.  The next decade in ai: Four steps towards robust artificial intelligence.  _arXiv preprint arXiv:2002.06177_.
  * Mnih et al. (2015) Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. 2015.  Human-level control through deep reinforcement learning.  _nature_ , 518(7540):529–533.
  * Pedregosa et al. (2011) F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. 2011.  Scikit-learn: Machine learning in Python.  _Journal of Machine Learning Research_ , 12:2825–2830.
  * Pwanson (2021) Saul Pwanson. 2021.  [link].
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language models are unsupervised multitask learners.  _OpenAI Blog_ , 1(8):9.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _Journal of Machine Learning Research_ , 21(140):1–67.
  * Rogers et al. (2020) Anna Rogers, Olga Kovaleva, and Anna Rumshisky. 2020.  A primer in bertology: What we know about how bert works.  _arXiv preprint arXiv:2002.12327_.
  * Shazeer and Stern (2018) Noam Shazeer and Mitchell Stern. 2018.  Adafactor: Adaptive learning rates with sublinear memory cost.  In _International Conference on Machine Learning_ , pages 4596–4604. PMLR.
  * Shazeer et al. (1999) Noam M Shazeer, Michael L Littman, and Greg A Keim. 1999.  Solving crossword puzzles as probabilistic constraint satisfaction.  In _AAAI/IAAI_ , pages 156–162.
  * Silver et al. (2016) David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. 2016.  Mastering the game of go with deep neural networks and tree search.  _nature_ , 529(7587):484–489.
  * Silver et al. (2018) David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. 2018.  A general reinforcement learning algorithm that masters chess, shogi, and go through self-play.  _Science_ , 362(6419):1140–1144.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems 30_ , pages 5998–6008. Curran Associates, Inc.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 38–45, Online. Association for Computational Linguistics.