TL;DR
The Berkeley Crossword Solver (BCS) achieves state-of-the-art performance in automatically solving crossword puzzles by combining neural question answering with loopy belief propagation and local search. This system significantly outperforms previous methods and even human competitors in live tournaments, demonstrating a major leap in AI's ability to tackle complex linguistic and constraint-satisfaction problems.
What Problem Does This Paper Address?
Crossword puzzles, while a popular pastime, represent a significant challenge for Artificial Intelligence. They require not only a vast knowledge base and the ability to understand diverse linguistic phenomena (like wordplay, puns, and homophones) but also the capacity to reason about multiple intersecting answers simultaneously. Traditional AI approaches have struggled to achieve high accuracy, often failing to match the performance of expert human solvers. This paper aims to bridge this gap by developing a robust, end-to-end system that can automatically solve crossword puzzles with high precision.
Methods
The Berkeley Crossword Solver (BCS) employs a multi-stage approach:
- Neural Question Answering (QA): The system first uses a bi-encoder neural network, initialized with BERT, to generate candidate answers for each crossword clue. This model is trained to map clues and answers into a shared embedding space, allowing for efficient retrieval of likely answers. A key aspect is its "closed-book" nature, focusing on answers seen during training, which surprisingly proved more effective than open-book models for this task.
- Loopy Belief Propagation (BP): To handle the interconnectedness of crossword answers, BCS uses loopy belief propagation. This technique iteratively refines the probabilities of answers by considering the constraints imposed by intersecting words. BP is chosen for its ability to directly search for solutions maximizing expected overlap with the ground truth, rather than just likelihood, and for its generation of marginal distributions useful for subsequent steps.
- Local Search (LS): To further improve solutions and correct minor errors, a local search phase is applied. This involves proposing small edits to the puzzle (e.g., flipping uncertain letters) and scoring these proposals using a second-pass generative QA model (ByT5-small). This iterative refinement helps to fix errors that BP might miss.
Datasets
The paper introduces a new, large-scale dataset of over six million question-answer pairs collected from 26 publishers, including The New York Times, The LA Times, and USA Today. This dataset spans over 70 years of crossword puzzles and is unique in its diversity and expert validation. For evaluation, they used 2020 NYT puzzles for validation and held out other puzzles for testing. They also collected a smaller set of complete puzzle grids for final evaluation.
Key Insights and Ideas
- "Closed-book" QA is surprisingly effective: The authors found that a "closed-book" QA model, which relies only on knowledge seen during training, performed better for crossword solving than open-book models that could access external knowledge like Wikipedia. This suggests that the specific nature of crossword answers and clues favors memorized patterns over broad knowledge retrieval.
- Loopy Belief Propagation for Constraint Satisfaction: BP is a powerful tool for solving crossword puzzles because it directly optimizes for the correctness of intersecting words, not just the individual likelihood of each answer. This is crucial for handling the complex dependencies in a crossword grid.
- Local Search as a Fine-Tuner: While BP gets the solver close, local search is essential for achieving near-perfect accuracy. It acts as a fine-tuning mechanism, correcting subtle errors that might otherwise prevent a perfect solve.
- Crossword Puzzles as a Rich AI Testbed: The paper highlights crosswords as an excellent benchmark for AI, testing not only QA but also complex constraint satisfaction, reasoning under uncertainty, and handling of linguistic nuances like wordplay.
Key Results
- State-of-the-Art Accuracy: The BCS achieves 82% exact puzzle accuracy on The New York Times crosswords, a significant improvement from the previous state-of-the-art 71%.
- Near-Perfect Themeless Puzzles: On themeless puzzles, the system achieves an impressive 99.9% letter accuracy.
- Human Competition Victory: In the 2021 American Crossword Puzzle Tournament (ACPT), a hybrid system incorporating BCS outperformed all 1033 human competitors, achieving a perfect score on 6 out of 7 puzzles.
- Improved QA Recall: The bi-encoder QA model achieves 94.6% top-1000 recall on NYT test sets, outperforming Dr.Fill's 84.4%.
Limitations and Future Work
- Themed Puzzles: The BCS struggles with "themed" puzzles, which often involve unique constraints like multiple letters in a single cell or topical connections between answers. The system does not explicitly handle these themes.
- QA Errors: While significantly improved, QA errors remain a source of failure, particularly for wordplay and cross-reference clues.
- Future Work: The authors suggest designing better evaluation metrics for automated crossword solvers, exploring methods for handling crossword themes, and potentially developing puzzle generation capabilities. They also emphasize the importance of their released dataset for future research in QA and crossword solving.
Summary updated