Down and Across: Introducing Crossword-Solving as a New NLP Benchmark (2022)

Abstract: Solving crossword puzzles requires diverse reasoning capabilities, access to a vast amount of knowledge about language and the world, and the ability to satisfy the constraints imposed by the structure of the puzzle. In this work, we introduce solving crossword puzzles as a new natural language understanding task. We release a corpus of crossword puzzles collected from the New York Times daily crossword spanning 25 years and comprised of a total of around nine thousand puzzles. These puzzles include a diverse set of clues: historic, factual, word meaning, synonyms/antonyms, fill-in-the-blank, abbreviations, prefixes/suffixes, wordplay, and cross-lingual, as well as clues that depend on the answers to other clues. We separately release the clue-answer pairs from these puzzles as an open-domain question answering dataset containing over half a million unique clue-answer pairs. For the question answering task, our baselines include several sequence-to-sequence and retrieval-based generative models. We also introduce a non-parametric constraint satisfaction baseline for solving the entire crossword puzzle. Finally, we propose an evaluation framework which consists of several complementary performance metrics.

## introduction recent breakthroughs in nlp established high standards for the performance of machine learning methods across a variety of tasks. however, even state-of-the-art models demonstrate fragility @xcite and exhibit sensitivity to shallow data patterns @xcite @xcite @xcite @xcite . this has led to a growing demand for successively more challenging tasks. one of the important tasks in natural language understanding is question answering (qa), with many recent datasets created to address different different aspects of this task @xcite @xcite @xcite . there are two main forms of question answering (qa): extractive qa and open-domain qa. in extractive qa, a passage that answers the question is provided as input to the system along with the question. in open-domain qa, only the question is provided as input, and the answer must be generated either through memorized knowledge or via some form of explicit information retrieval over a large text collection which may contain answers. the task of answering clues in a crossword is a form of open-domain question answering. once a human or an open-domain qa system generates a few possible answer candidates for each clue, one of these candidates may form the correct answer to a word slot in the crossword grid, if the candidate meets the constraints of the crossword grid. solving a crossword puzzle is therefore a challenging task which requires (1) finding answers to a variety of clues that require extensive language and world knowledge, and (2) the ability to produce answer strings that meet the constraints of the crossword grid, including length of word slots and character overlap with other answers in the puzzle. our contributions in this work are as follows: r e a m a n v i j o e s a c r o f e l l a a t u r b a t s h y f n o t e e l a n o m e g r e d r s e a n n l l s s s o d a y t b i b r a r a m y i p l l s a e s i c a p d e n a n e c r i l e d u e l s r e x d o r i e r t a l e p l o d s e v e a a l n t e l i a g e r a f d o n n q u i p s t a r u n n i n g l o t e t r u m e t b a n r i a a a u t s e a figure 1: crossword puzzle example. a few clues from the puzzle have been provided on the right, they are filled horizontally (across) or vertically (down) in the crossword grid. the clue number tells the player where in the grid the answer needs to be filled in. some of these clue and their answers have further been highlighted with different colors which belong to different clue categories as described in section 3.2, color-coded in accordance with figure 2 . highlight colors denote distinct clue categories: red for word meaning clues, purple for fill-inthe blank clue, orange for synonym/antonym, blue for factoid question type, grey for abbreviation and brown for historical. source: new york times daily crossword which appeared on the july 7, 2009. copyright of the new york times, 2009. ## related work our work is in line with open-domain qa benchmarks. examples of such tasks include datasets where each question can be answered using information contained in a relevant wikipedia article @xcite @xcite . several qa tasks have been designed to require multi-hop reasoning over structured knowledge bases @xcite . the main limitation of such datasets is that their question types are mostly factual. crossword clues differ from these efforts in that they combine a variety of different reasoning types. another line of research that is relevant to our work explores the problem of solving sudoku puzzles since it is also a constraint satisfaction problem. most sudoku puzzles can be efficiently solved by algorithms that take advantage of the fixed input size and do not rely on machine learning methods @xcite . the machine learning attempts for solving sudoku puzzles have been inspired by convolutional @xcite and recurrent relational networks @xcite . unlike sudoku, however, where the grids have the same structure, shape and constraints, crossword puzzles have arbitrary shape and internal structure and rely on answers to natural language questions that require reasoning over different kinds of world knowledge. several previous studies have treated crossword puzzle solving as a constraint satisfaction problem (csp) @xcite @xcite . littman et al. (2002)'s proverb system incorporates a variety of information retrieval modules to generate candidate answers. the database module searches a large database of historical clue-answer pairs to retrieve the answer candidates. they find very poor crossword-solving performance in ablation experiments where they limit their answer candidate generator modules to not use historical clue-answer databases. webcrow @xcite builds upon proverb and makes improvements to the database retriever module augmented with a new web module which searches the web for snippets that may contain answers. it allows partial matching to retrieve clues-answer pairs in the historical database that do not perfectly overlap with the query clue. dr. fill system proposed by @xcite treats each crossword puzzle as a singly-weighted csp. similarly to prior work, dr. fill relies on a large set of historical clue-answer pairs (up to 5m) collected over multiple years from the past puzzles by applying direct lookup and a variety of heuristics. one common design aspect of all these solvers is to generate answer candidates independently from the crossword structure and later use a separate puzzle solver to fill in the actual grid. in our work, we partition the task of crossword solving similarly. @xcite and @xcite observe that the most important source of candidate answers for a given clue is a large database of historical clue-answer pairs and introduce methods to better search these databases. @xcite apply a bm25 retrieval model to generate clue lists similar to the query clue from historical clue-answer database, where the generated clues get further refined through application of reranking models. @xcite introduce a distributional neural network to compute similarities between clues trained over a large scale dataset of clues that they introduce. in contrast to the previous work, our goal in this work is to motivate solver systems to generate answers organically, just like a human might, rather than obtain answers via the lookup in historical clue-answer databases. the answers could be generated either from memory of having read something relevant, using world knowledge and language understanding, or by searching encyclopedic sources such as wikipedia or a dictionary with relevant queries. ## task and dataset for the purposes of our task, crosswords are defined as word puzzles with a given rectangular grid of white-and black-shaded squares. the goal is to fill the white squares with letters, forming words or phrases by solving textual clues which lead to the answers. the answer words and phrases are placed in the grid from left to right ("across") and from top to bottom ("down"). the shaded squares are used to separate the words or phrases. usually, the white spaces and punctuation are removed from the answer phrases. a sample crossword puzzle is given in figure 1 . note that the answers can include named entities and abbreviations, and at times require the exact grammatical form, such as the correct verb tense or the plural noun. solving a crossword puzzle is a complex task that requires generating the right answer candidates and selecting those that satisfy the puzzle constraints. similar to prior work, we divide the task of solving a crossword puzzle into two subtasks, to be evaluated separately. the first subtask can be viewed as a question answering task, where a system is trained to generate a set of candidate answers for a given clue without taking into account any interdependencies between answers. the sec-ond subtask involves solving the entire crossword puzzle, i.e., filling out the crossword grid with a subset of candidate answers generated in the previous step. the two tasks could be solved separately or in an end-to-end fashion. in contrast to prior work @xcite , our clueanswer data is linked directly with our puzzlesolving data, so no data leakage is possible between the qa training data and the crossword-solving test data. in the present work, we propose a separate solver for each task. we provide details on the challenges of implementing an end-to-end solver in the discussion section. ## baselines our baseline approach is a two-step solution that treats each subtask separately. we first develop a set of baseline systems that solve the question answering problem, ignoring the grid-imposed answer interdependencies. we use seq-to-seq and retrieval-augmented transformer baselines for this subtask. we feed generated answer candidates to a crossword solver in order to complete the puzzle and evaluate the produced puzzle solutions. ## qualitative analysis evaluation on the annotated subset of the data reveals that some clue types present significantly higher levels of difficulty than others (see in particular, all of our baseline systems struggle with the clues requiring reasoning in the context of historical knowledge. as expected, all of the models demonstrate much stronger performance on the factual and word-meaning clue types, since the relevant answer candidates are likely to be found in the wikipedia data used for pre-training. we observe the biggest differences between bart and rag performance for the "abbreviation" and the "prefixsuffix" categories. the document retrieval step in rag allows for more efficient matching of supporting documents, leading to generation of more relevant answer candidates. for instance, the clue "warehouse abbr." results in "pkg" and "bldg" candidates among rag predictions, whereas bart generates abstract and largely irrelevant strings. our manual inspection of model predictions suggest that both bart and rag correctly infer the grammatical form of the answer from the formulation of the clue. for example, the clue "stitched" produces the candidate answers "sewn" and "made", and the clue "word repeated after "que"" triggers mostly spanish and french generations (e.g. "avec" or "sera"). as previously stated rag-wiki and rag-dict largely agree with each other with respect to the ground truth answers. we qualitatively assessed instances where either rag-wiki or rag-dict predict the answer correctly in appendix a. ## discussion and future work the presented task is challenging to approach in an end-to-end model fashion. there are several reasons for this, which we discuss below. character-level outputs. commonly used transformer decoders do not produce characterlevel outputs and produce bpe and wordpieces instead, which creates a problem for a potential end-to-end neural crossword solver. one possible solution can be the modification of the loss term, designed with character-based output logits instead of bpe since the crossword grid constraints are at a single cell-(i.e. character-) level. there is some work done in the character-level output transformer encoders such as @xcite . however, to our best knowledge there is no major generative transformer architecture which supports character-level outputs yet, we intend to explore this avenue further in future work to develop an end-to-end neural crossword solver. smt solver constraints. as mentioned earlier, our current baseline solver does not allow partial solutions, and we rely on pre-filtering using the oracle from the ground-truth answers. although this strategy is flawed for the obvious use of the oracle, the alternatives are currently either computationally intractable or too lossy. one such strategy is to remove k clues at a time, starting with @xmath0, where n is the total number of clues in the puzzle. another approach we tried was to relax certain constraints of the puzzle grid, maximally satisfying as many constraints as possible, which is formally known as the maximal satisfaction problem (max-sat). this is a np-hard problem for which it is hard to find approximate solutions @xcite . our initial foray into such approximate solvers @xcite produced severely under-constrained puzzles with garbage character entries. further work needs to be done to extend this solver to handle partial solutions elegantly without the need for an oracle, this could be addressed with probabilistic and weighted constraint satisfaction solvers, in line with the work by @xcite ; @xcite and @xcite , but without the dependency on the past crossword clues. ## conclusion we present a new challenging task of solving crossword puzzles and present the new york times crosswords dataset, which can be approached at a qa-like level of individual clue-answer pairs, or at the level of an entire puzzle, with imposed an-swer interdependency constraints. this new benchmark contains a broad range of clue types that require diverse reasoning components. we carry out a set of baseline experiments that indicate the overall difficulty of this task for the current systems, including retrieval-augmented sota models for open-domain question answering. we also discuss the technical challenges in building a crossword solver and obtaining partial solutions as well as in the design of end-to-end systems for this task. we hope that the nyt crosswords task would define a new high bar for the ai systems.