Language Models are Crossword Solvers

📄 arXiv: 2406.09043v3 📥 PDF

作者: Soumadeep Saha, Sutanoya Chakraborty, Saptarshi Saha, Utpal Garain

分类: cs.CL, cs.AI

发布日期: 2024-06-13 (更新: 2025-02-09)

备注: 10 pages, 3 figures, 6 Appendix. Accepted to NAACL 2025

期刊: NAACL 2025 (Volume 1: Long Papers), pages 2074-2090

DOI: 10.18653/v1/2025.naacl-long.104

💡 一句话要点

利用大型语言模型解决纵横填字游戏难题，显著超越现有技术水平。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大型语言模型 纵横填字游戏 自然语言理解 约束满足 搜索算法

📋 核心要点

  1. 现有方法在解决纵横填字游戏时，难以同时兼顾自然语言理解、推理和约束条件。
  2. 利用大型语言模型强大的语言理解和生成能力，结合搜索算法，求解完整的填字游戏。
  3. 实验结果表明，该方法在填字游戏解题任务上显著优于现有技术，并在《纽约时报》填字游戏中达到93%的准确率。

📝 摘要（中文）

本文探讨了使用大型语言模型（LLMs）解决纵横填字游戏这一难题。纵横填字游戏要求解题者在自然语言理解、文字游戏、推理和世界知识方面表现出高度的熟练程度，同时遵守字符和长度的约束。研究表明，当前一代的语言模型在解读隐晦的填字游戏线索方面表现出显著的能力，并在相关基准测试中优于先前报道的最先进（SoTA）结果2-3倍。此外，还开发了一种搜索算法，利用这种性能首次使用开箱即用的LLM来解决完整的纵横填字游戏网格，在《纽约时报》纵横填字游戏中实现了93%的准确率。最后，证明了LLM具有良好的泛化能力，并且能够为答案提供合理的理由。

🔬 方法详解

问题定义：论文旨在解决自动求解纵横填字游戏的问题。现有方法通常依赖于手工设计的规则或有限的知识库，难以处理复杂的线索和约束条件，尤其是在隐晦的线索和需要世界知识的情况下表现不佳。此外，现有方法通常无法完整地解决整个填字游戏网格，而是侧重于单个线索的解答。

核心思路：论文的核心思路是利用大型语言模型（LLMs）强大的自然语言理解和生成能力，将填字游戏求解视为一个语言建模问题。通过提示工程（Prompt Engineering）引导LLM理解线索并生成候选答案，然后结合搜索算法在满足约束条件（如长度和已填字母）的答案空间中进行搜索。

技术框架：整体框架包含两个主要阶段：1) 线索解答阶段：使用LLM根据线索生成候选答案列表，并评估每个答案的置信度。2) 网格填充阶段：使用搜索算法，根据已有的答案和约束条件，迭代地填充整个填字游戏网格。搜索算法会考虑答案的置信度、与其他答案的兼容性以及是否满足长度和字母约束。

关键创新：最重要的创新在于将大型语言模型应用于完整的纵横填字游戏求解，并结合搜索算法实现了高准确率。与以往方法相比，该方法无需手工设计的规则或知识库，而是直接利用LLM的语言理解能力。此外，该方法还能够为答案提供合理的解释，增强了可解释性。

关键设计：在提示工程方面，论文设计了特定的提示模板，引导LLM理解线索的类型和约束条件。在搜索算法方面，论文采用了基于置信度的搜索策略，优先考虑LLM给出的高置信度答案。此外，论文还使用了约束传播技术，加速搜索过程并提高效率。具体参数设置和损失函数未在摘要中提及，属于未知信息。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，该方法在纵横填字游戏解题任务上显著优于现有技术，在相关基准测试中性能提升了2-3倍。在《纽约时报》纵横填字游戏中，该方法实现了93%的准确率，表明了其在实际应用中的可行性。

🎯 应用场景

该研究成果可应用于智能玩具、教育游戏等领域，提升用户体验。此外，该方法在知识推理、自然语言理解和约束满足等方面的应用潜力巨大，可扩展到其他需要复杂推理和约束优化的任务中，例如自动问答系统、知识图谱构建等。

📄 摘要（原文）

Crosswords are a form of word puzzle that require a solver to demonstrate a high degree of proficiency in natural language understanding, wordplay, reasoning, and world knowledge, along with adherence to character and length constraints. In this paper we tackle the challenge of solving crosswords with large language models (LLMs). We demonstrate that the current generation of language models shows significant competence at deciphering cryptic crossword clues and outperforms previously reported state-of-the-art (SoTA) results by a factor of 2-3 in relevant benchmarks. We also develop a search algorithm that builds off this performance to tackle the problem of solving full crossword grids with out-of-the-box LLMs for the very first time, achieving an accuracy of 93% on New York Times crossword puzzles. Additionally, we demonstrate that LLMs generalize well and are capable of supporting answers with sound rationale.