We present the Berkeley Crossword Solver, a state-of-the-art approach for automatically solving crossword puzzles. Our system works by generating answer candidates for each crossword clue using neural question answering models and then combines loopy belief propagation with local search to find full puzzle solutions. Compared to existing approaches, our system improves exact puzzle accuracy from 57% to 82% on crosswords from The New York Times and obtains 99.9% letter accuracy on themeless puzzles. Our system also won first place at the top human crossword tournament, which marks the first time that a computer program has surpassed human performance at this event. To facilitate research on question answering and crossword solving, we analyze our system's remaining errors and release a dataset of over six million question-answer pairs. The key to solving crosswords is mental flexibility. If one answer doesn't seem to be working out, try something else. Crossword puzzles are perhaps the world's most popular language game, with millions of solvers in the United States alone (Ginsberg, 2011). Crosswords test knowledge of word meanings, trivia, commonsense, and wordplay, while also requiring one to simultaneously reason about multiple intersecting answers. Consequently, crossword puzzles provide a testbed to study open problems in AI and NLP, ranging from question answering to search and constraint satisfaction. In this paper, we describe an end-to-end system for solving crossword puzzles that tackles many of these challenges. Crossword puzzles are word games consisting of rectangular grids of squares that are to be filled in with letters based on given clues (e.g., Figure 1). Puzzles typically consist of 6080 clues that vary in difficulty due to the presence of complex wordplay, intentionally ambiguous clues, or esoteric knowledge. Each grid cell belongs to two words, meaning that one must jointly reason about answers to multiple questions. Most players complete crosswords that are published daily in newspapers and magazines such as The New York Times (NYT), while other more expert enthusiasts also compete in live events such as the American Crossword Puzzle Tournament (ACPT). These events are intensely competitive: one previous winner reportedly solved twenty puzzles per day as practice (Grady, 2010), and top competitors can perfectly solve expert-level puzzles with over 100 clues in just 3 minutes. Automated crossword solvers have been built in the past and can outperform most hobbyist humans. Two of the best such systems are Proverb (Littman et al., 2002) and Dr. Fill (Ginsberg, 2011). Despite their reasonable success, past systems struggle to solve the difficult linguistic phenomena present in crosswords, and they fail to outperform expert humans. At the time of their respective publications, Proverb achieved 213th place out of 252 in the ACPT, while Dr. Fill achieved 43rd place. Answering crossword clues involves challenges not found in traditional question answering (QA) benchmarks. The clues are typically less literal; they span different reasoning types (c.f., Table 1); and they cover diverse linguistic phenomena such as polysemy, homophony, puns, and other types of wordplay. Many crossword clues are also intentionally underspecified, and to solve them, one must be able to know what they don't know and defer answering those clues until crossing letters are known. Crosswords are also useful from a practical perspective as the data is abundant, well-validated, diverse, and constantly evolving. In particular, there are millions of question-answer pairs online, and unlike crowdsourced datasets that are often rife with artifacts (Gururangan et al., 2018; Min et al., 2019), crossword clues are written and validated by experts. Finally, crossword data is diverse as it spans many years of pop culture, is written by thousands of different constructors, and contains various publisher-specific idiosyncrasies. Solving crosswords goes beyond just generating answers to each clue. Without guidance from a constraint solver, QA models cannot reconcile crossing letter and length constraints. Satisfying these constraints is challenging because the search space is enormous and many valid solutions exist, only one of which is correct. Moreover, due to miscalibra-tion in the QA model predictions, exact inference may also lead to solutions that are high-likelihood but completely incorrect, similar to other types of structured decoding problems in NLP (Stahlberg and Byrne, 2019; Kumar and Sarawagi, 2019). Finally, the challenges in search are amplified by the unique long tail of crossword answers, e.g.,  daaa bears  or  eeny meeny miny moe , which makes it highly insufficient to restrict the search space to solutions that contain only common English words. We present the Berkeley Crossword Solver (BCS), which is summarized in Figure 2. The BCS is based on the principle that some clues are difficult to answer without any letter constraints, but other (easier) clues are more standalone. This naturally motivates a multi-stage solving approach, where we first generate answers for each question independently, fill in the puzzle using those answers, and then rescore uncertain answers while conditioning on the predicted letter constraints. We refer to these stages as first-pass QA, constraint resolution, and local search, and we describe each component in Sections 35 after describing our dataset 3074 Question Answering Local Search Loopy Belief Propagation 1 4 5 3 2 1 4 5 3 2 1 4 5 3 2 1 4 5 3 2 Acros    Backward tu    Pikachu traine    Exclamation of surprise in Section 2. In Section 6, we show that the BCS substantially improves over the previous state-of-the-art Dr. Fill system, perfectly solving 82% of crosswords from The New York Times , compared to 57% for Dr. Fill. Nevertheless, room for additional improvement remains, especially on the QA front. To facilitate further exploration, we publicly release our code, models, and dataset: https:// github.com/albertkx/berkeley-crossword-solver . This section describes the dataset that we built for training and evaluating crossword solving systems. Recall that a crossword puzzle contains both question-answer pairs and an arrangement of those pairs into a grid (e.g., Figure 1). Unfortunately, complete crossword puzzles are protected under copyright agreements; however, their individual question-answer pairs are free-to-use. Our dataset efforts thus focused on collecting numerous question-answer pairs (Section 2.1) and we collected a smaller set of complete puzzle grids to use for final evaluation (Section 2.2). We collected a dataset of over six million question-answer pairs from top online publishers such as The New York Times , The LA Times , and USA Today We show qualitative examples in Table 1, summary statistics in Table 2, and additional breakdowns in Appendix B. Compared to existing QA datasets, our crossword dataset represents a unique and challenging testbed as it is large and carefully labeled, is varied in authorship, spans over 70 years of pop culture, and contains examples that are difficult for even expert humans. We built validation and test sets by splitting off every question-answer pair used in the 2020 and 2021 NYT puzzles. We use re-cent NYT puzzles for evaluation because the NYT is the most popular and well-validated crossword publisher, and because using newer puzzles helps to evaluate temporal distribution shift. Word Segmentation of Answers Crossword answers are canonically filled in using all capital letters and without spaces or punctuation, e.g.,  whale that stinks  becomes WHALETHATSTINKS . These unsegmented answers may confuse neural QA models that are pretrained on natural English text that is tokenized into wordpieces. To remedy this, we trained a word segmentation model that maps the clues to their natural language form. 1 We collected segmentation training data by retrieving common n -grams from Wikipedia and removing their spaces and punctuation. We then finetuned GPT-2 small (Radford et al., 2019) to generate the segmented n -gram given its unsegmented version. We ran the segmenter on all answers in our data. In all our experiments, we train our QA models using segmented answers and we post-hoc remove spaces and punctuation from their predictions. To evaluate our final crossword solver, we collected a validation and test set of complete 2020 and 2021 puzzle grids. We use puzzles from The New York Times , The LA Times , Newsday , The New Yorker , and The Atlantic . Using multiple publishers for 1 More simplistic algorithms that segment the answer into known English words are insufficient for many crossword answers, e.g., DAAABEARS and EENYMEENYMINYMOE . evaluation provides a unique challenge as each publisher contains different idiosyncrasies, answer distributions, and crossword styles. We use 2020 NYT as our validation set and hold out all other puzzles for testing. There are 430 total test puzzles. The initial step of the BCS is question answering: we generate a list of possible answer candidates and their associated probabilities for each clue. A key requirement for this QA model is that it does not output unreasonable or overly confident answers for hard clues. Instead, this model is designed to be used as a first-pass that generates reasonable candidates for every clue, in hope that harder clues can be reconciled later when predicted letter constraints are available. We achieve this by restricting our first-pass QA model to only output answers that are present in the training set. As discussed in Section 5, we later generate answers outside of this closed-book set with our second-pass QA model. Model Architecture We build our QA model based on a bi-encoder architecture (Bromley et al., 1994; Karpukhin et al., 2020) due to its ability to score numerous answers efficiently and learn using few examples per answer. We have two neural network encoders: EC (  ) , the clue encoder, and EA (  ) , the answer encoder. Both encoders are initialized with BERT-base-uncased (Devlin et al., 2019) and output the encoder's [CLS] representation as the final encoding. These two encoders are trained to map the questions and answers into the same feature space. Given a clue c , the model scores all possible answers a i using a dot product similarity function between feature vectors: sim( c, a i ) = EC ( c ) TEA ( a i ) . Our answer set consists of the 437.8K answers in the training data. 2 2 Our bi-encoder model is a closed-book QA model because it does not have open-book access to external knowl-Training We train the encoders in the same fashion as DPR (Karpukhin et al., 2020): batches consist of clues, answers, and distractor answers. The two encoders are trained jointly to assign a high similarity to the correct question-answer pairs and low similarity to all other pairs formed between the clue and distractor answers. We use one distractor answer per clue that we collect by searching each clue in the training set using TFIDF and returning the top incorrect answer. We tune hyperparameters of our bi-encoder model based on its topk accuracy on the NYT validation set. Inference At test time, for each clue c , we compute the embedding v c = EC ( c ) and retrieve the answers whose embeddings have the highest dot product similarity with v c . We obtain probabilities for each answer by softmaxing the dot product scores. To speed up inference, we precompute the answer embeddings and use FAISS (Johnson et al., 2019) for similarity scoring. To evaluate our bi-encoder, we compute its topk recall on the question-answer pairs from the NYT test set. We are most interested in top-1000 recall, as we found it to be highly-correlated with downstream solving performance (discussed in Section 7). As a baseline, we compare against the QA portion of the previous state-of-the-art Dr. Fill crossword solver (Ginsberg, 2011). This QA model works by ensembling TFIDF-like scoring and numerous additional modules (e.g., synonym matching, POS matching). Our bi-encoder model considerably outperforms Dr. Fill, improving top-1000 recall from 81.2% to 94.6% (Figure 3). Also note that approximately 4% of test answers are not seen during training, and thus the oracle recall for our first-pass QA model is  96%. Given the list of answer candidates and their associated probabilities from the first-pass QA model, we next built a solver that produces a puzzle solution that satisfies the letter constraints. Formally, crossword solving is a weighted constraint satisfaction problem, where the probability over solutions is given by the product of the confidence scores produced by the QA model (Ginsberg, 2011). There edge sources such as Wikipedia (Roberts et al., 2020). We found in preliminary experiments that open-book models struggle as most crossword answers are not present or are difficult to retrieve from knowledge sources such as Wikipedia. are numerous algorithms for solving such problems, including branch-and-bound, integer linear programming, and more. We use belief propagation (Pearl, 1988), henceforth BP, for two reasons. First, BP directly searches for the puzzle with the highest expected overlap with the ground-truth puzzle, rather than the puzzle with the highest likelihood under the QA model (Littman et al., 2002). This is advantageous as it maximizes the total number of correct words and letters in the solution, and it also avoids strange solutions that may have spuriously high scores under the QA model. Second, BP also produces marginal distributions over words and characters, which is useful for generating an n -best list of puzzle candidates (used in Section 5). Loopy Belief Propagation We use loopy BP, inspired by the Proverb crossword solver (Littman et al., 2002). That is, we construct a bipartite graph with nodes for each of the crossword's clues and cells. For each clue node, we connect it via an edge to each of its associated cell nodes (e.g., a 5-letter clue will have degree 5 in the constructed graph). Each clue node maintains a belief state over answers for that clue, which is initialized using a mixture of the QA model's probabilities and a unigram letter LM. 3 Each cell node maintains a belief state over letters for that cell. We then iteratively 3 The unigram letter LM accounts for the probability that an answer is not in our answer set. apply BP with each iteration doing message passing for all clue nodes in parallel and then for all cell nodes in parallel. The algorithm empirically converges after 510 iterations and completes in just 10 seconds on a single-threaded Python process. Greedy Inference BP produces a marginal distribution over words for each clue. To generate an actual puzzle solution, we run greedy search where we first fill in the answer with the highest marginal likelihood, remove any crossing answers that do not share the same letter, and repeat. Many of the puzzle solutions generated by BP are close to correct but have small letter mistakes, e.g., NAUCI instead of FAUCI or TAZOAMBASSADORS instead of JAZZAMBASSADORS , as shown in Figure 4. 4 We remedy this in the final stage of the BCS with local search (LS), where we take a second-pass through the puzzle and score alternate proposals that are a small edit distance away from the BP solution. In particular, we alternate between proposing new candidate solutions by flipping uncertain letters and scoring those proposals using a second-pass QA model. Proposing Alternate Solutions Similar to related problems in structured prediction (Stahlberg and Byrne, 2019) or model-based optimization (Fu and Levine, 2021), the key challenge in searching for alternate puzzle solutions is to avoid false positives and adversarial inputs. If we score every proposal within a small edit distance to the original, we are bound to find nonsensical character flips that nevertheless lead to higher model scores. We avoid this by only scoring proposals that are within a 2-letter edit distance and also have nontrivial likelihoods according to BP or a dictionary. Specifically, we score all proposals whose 12 modified letters each have probability 0.01 or greater under the character marginal probabilities produced by BP. 5 We also score all proposals whose 12 modified letters 4 These errors stem from multiple sources. First, 4% of the answers in a test crossword are not present in our bi-encoder's answer set. Those answers will be not be filled in correctly unless the solver can identify the correct answer for all of the crossing answers. Second, natural QA errors exist even on questions with non-novel answers. Finally, the BP algorithm may converge to a sub-optimal solution. 5 The character-level marginal distribution for most characters assigns all probability mass to a single letter after a few iterations of BP (e.g., probability 0.9999). We empirically chose 0.01 as it achieved the highest validation accuracy. cause the corresponding answer to segment into valid English words. 6 Scoring Solutions With Second-Pass QA Given the alternate puzzle solutions, we could feed each of them into our bi-encoder model for scoring. However, we found that bi-encoders are not robust they sometimes produce high-confidence predictions for the nonsensical answers present in some candidate solutions. We instead use generative QA models to score the proposed candidates as we found these models to be empirically more robust. We finetuned the character-level model ByT5-small (Xue et al., 2022) on our training set to generate the answer from a given clue. We then score each proposed candidate using the product of the model's likelihoods of the answers given the clues, (cid:81) j P ( a j | c j ) . After scoring all candidate proposals, we apply the best-scoring edit and repeat the proposal and scoring process until no better edits exist. Figure 4 shows an example of the candidates accepted by LS. Quantitatively, we found that LS applied 243 edits that improved accuracy and 31 edits that hurt accuracy across 255 NYT test puzzles. We evaluated our final system on our set of test puzzles and compare the results to the state-of-the-art Dr. Fill system (Ginsberg, 2011). 7 We compute 6 For instance, given a puzzle that contains a fill such as MUNNYANDCLYDE , we consider alternate solutions that contain answers such as BUNNYANDCLYDE and SUNNYANDCLYDE , as they segment to  bunny and clyde  and  sunny and clyde . 7 Note that while the original Dr. Fill paper was published in 2011, the system has been consistently updated and has substantially improved. Dr. Fill can outperform all but the best human solvers (see Table 5 for statistics on its improvement). three accuracy metrics: perfect puzzle, word, and letter. Perfect puzzle accuracy requires answering every clue in the puzzle correctly and serves as our primaryand most challengingmetric. Table 3 shows our main results. We outperform Dr. Fill on perfect puzzle accuracy across crosswords from every publication source. For example, we obtain a 24.8% absolute improvement on perfect puzzle accuracy on crossword puzzles from The New York Times , which is a statistically significant improvement ( p < 0 . 01 ) according to a paired t -test. We also observe comparable or better word and letter accuracies than Dr. Fill across all sources. Our improvement on puzzles from The New Yorker is relatively small; this discrepancy is possibly due to the small amount of data from The New Yorker in our training set (see Figure 7). Themed vs. Themeless Puzzles Although the BCS achieves equivalent or worse letter accuracy on Newsday and LA Times puzzles, it obtains substantially higher puzzle accuracy on these splits. We attribute this behavior to errors concentrated in unique themed puzzles, e.g., ones that place multiple letters into a single cell. To test this, we break down NYT puzzles into those with and without special theme entries (see Appendix D for our definition of theme puzzles). On themeless NYT puzzles, we achieve 99.9% letter accuracy and 89.5% perfect puzzles, showing that themed puzzles are a major source of our errors. Note that the Dr. Fill system includes various methods to detect and resolve themes and is thus more competitive on such puzzles, although it still underperforms our system. our last evaluation, we competed live in the Amer-We ican Crossword Puzzle Tournament (ACPT), the longest-running and most prestigious human crossword tournament. We obtained special permission from the organizers to compete in the 2021 version of the tournament against 1,100 top human competitors. For the live tournament, we used a version 1.0 of our system, which does not use belief propagation or local search but instead uses Dr. Fill's constraint-resolution system. Our system won first placewe had a total score of 12,825 compared to the top human who had 12,810 (scor-ing details in Appendix C). Figure 5 shows our scores compared to the top and median human competitor on the 7 puzzles used in the competition. We also retrospectively evaluated our final BCS system (i.e., using our solver based on belief propagation and local search), and achieved a higher total score of 13,065. This corresponds to getting 6 out of the 7 puzzles perfect and 1 letter wrong on 1 puzzle. System Ablations We also investigated the importance of our QA model, BP inference, and local search with an ablation study. Table 4 shows results for perfect puzzle accuracy on NYT 2021 puzzles under different settings. The first ablation shows that our local search step is crucial for our solver to achieve high accuracy. The second and third ablations show that the BCS's QA and solver are both superior to their counterparts from Dr. Fill swapping out either component hurts accuracy. Our system outperforms the best human solvers; does this mean that crosswords are solved? The answer is, of course, no. In this section, we show that substantial headroom remains on QA accuracy and the handling of special themed puzzles. der for our solver to find the correct solution. We found that when our QA model ranks the true answer within the top 1,000 predictions, the answer is almost always filled in correctly (Figure 11). Despite top-1000 accuracy typically being sufficient, our QA model still makes numerous errors. We manually analyzed these mistakes by sampling 200 errors from the NYT 2021 puzzles and placing them in the same categories used in Table 1. Figure 6 shows the results and indicates that knowledge, wordplay, and cross-reference clues make up the majority of errors. End-to-end Analysis We next analyzed the errors for our full system. There are 43 NYT 2021 puzzles that we did not solve perfectly. We manually separated these puzzles into four categories:  Themes (21 puzzles). Puzzles with unique themes, e.g., placing four characters in one cell. Local Search Proposals (9 puzzles). Puzzles where we did not propose a puzzle edit in local search that would have improved accuracy. Local Search Scoring (9 puzzles). Puzzles where the ByT5 scorer either rejected a correct proposal or accepted an incorrect proposal. Connected Errors (4 puzzles). Puzzles with 3079 1 2 3 4 5 6 7 ACPT Puzzle Number 0 20 40 60 80 100 P e r ce n t o f P e r f ec t S c o r e ( % ) 100 98 88 100 97 79 100 96 76 100 98 86 89 93 34 100 96 81 91 97 76 BCS + Dr. Fill Top Competitor Median Competitor Figure 5: A breakdown of our 2021 ACPT performance. Overall, the largest source of remaining puzzle failures is special themed puzzles, which is unsurprising as our solver does not explicitly handle themes. The remaining errors are mostly split between proposal and scoring errors. Finally, connected errors typically arise when BP fills in an answer that is in our bi-encoder's answer set but is incorrect, i.e., the first-pass model was overconfident. Past Crossword Solvers Prior to our work, the three most successful automated crossword solvers were Proverb, WebCrow (Ernandes et al., 2005), and Dr. Fill. Dr. Fill uses a relatively straightforward TFIDF-like search for question answering, but Proverb and WebCrow combine a number of bespoke modules for QA; WebCrow also relies on a search engine to integrate external knowledge. On the solving side, Proverb and WebCrow both use loopy belief propagation, combined with A* search for inference. Meanwhile, Dr. Fill, uses a modified depth-first search known as limited discrepancy search, as well as a post-hoc local search with heuristics to score alternate puzzles. Standalone QA Models for Crosswords Past work also evaluated QA techniques using crossword question-answer pairs. These include linear models (Barlacchi et al., 2014), WordNet suggestions (Thomas and S., 2019), and shallow neural networks (Severyn et al., 2015; Hill et al., 2016); we instead use state-of-the-art transformer models. clues while maintaining accurate estimates of model uncertainty. Other QA tasks share similar challenges (Ferrucci et al., 2010; Rodriguez et al., 2021; Rajpurkar et al., 2018; Min et al., 2020). Crossword puzzles pose a novel challenge as they contain unique types of reasoning and linguistic phenomena such as wordplay. Crossword Themes We have largely ignored the presence of themes in crossword puzzles. Themes range from simple topical similarities between answers to puzzles that must be filled in a circular pattern to be correct. While Dr. Fill (Ginsberg, 2011) has a variety of theme handling modules built into it, integrating themes into our probabilis-3080 tic formulation remains as future work. Cryptic Crosswords We solve American-style crosswords that differ from British-style cryptic crosswords (Efrat et al., 2021; Rozner et al., 2021). Cryptic crosswords involve a different set of conventions and challenges, e.g., more metalinguistic reasoning clues such as anagrams, and likely require different methods from those we propose. We have presented new methods for crossword solving based on neural question answering, structured decoding, and local search. Our system outperforms even the best human solvers and can solve puzzles from a wide range of domains with perfect accuracy. Despite this progress, some challenges remain in crossword solving, especially on the QA side, and we hope to spur future research in this direction by releasing a large dataset of question-answer pairs. In future work, we hope to design new ways of evaluating automated crossword solvers, including testing on puzzles that are designed to be difficult for computers and tasking models with puzzle generation. Our data comes primarily from crosswords published in established American newspapers and journals, where a lack of diversity among puzzle constructors and editors may influence the types of clues that appear. For example, only 21% of crosswords published in The New York Times have at least one woman constructor (Chen, 2021) and a crossword from January 2019 was criticized for including a racial slur as an answer (Graham, 2019). We view the potential for real-world harm as limited since automated crossword solvers are unlikely to be deployed widely in the real world and have limited potential for dual use. However, we note that these considerations may be important to researchers using our data for question answering research more broadly. We thank Sewon Min, Sameer Singh, Shi Feng, Nikhil Kandpal, Michael Littman, and the members of the Berkeley NLP Group for their valuable feedback. We are also grateful to Will Shortz and the organizers of the American Crossword Puzzle Tournament for allowing us to compete in the event. This work was funded in part by the DARPA XAI and LwLL programs. Nicholas Tomlin is supported by the National Science Foundation Graduate Research Fellowship.
objective result result objective method abstain abstain abstain abstain objective abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other method abstain abstain method method abstain method abstain abstain abstain method method method abstain method method method abstain abstain method abstain method abstain abstain abstain method method abstain abstain abstain abstain abstain method abstain method abstain method abstain method method abstain method abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain method method method abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain method method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain method abstain abstain result result abstain abstain abstain result result result result result abstain abstain result result abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain method abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain other other other other method other other other abstain other method abstain objective objective objective abstain objective method abstain method method other other other other