A Reasoning-Based Approach to Cryptic Crossword Clue Solving

Authors: Martin Andrews, Sam Witteveen
Primary area: applications to computer vision, audio, language, and other modalities
Keywords: NLP, Cryptic Crosswords, Reasoning, Proof/Verification

Abstract:
Cryptic crossword clues are challenging language tasks for which new test sets are released daily by major newspapers on a global basis. Each cryptic clue contains both the definition of the answer to be placed in the crossword grid (in common with regular crosswords), and ‘wordplay’ that *proves* that the answer is correct (i.e. a human solver can be confident that an answer is correct without needing crossing words as confirmation). This work describes an LLM-based reasoning system built from open-licensed components that solves cryptic clues by (i) hypothesising answers; (ii) proposing wordplay explanations; and (iii) using a verifier system that operates on codified reasoning steps. Overall, this system establishes a new state-of-the-art performance on the challenging Cryptonite dataset of clues from The Times and The Telegraph newspapers in the UK. Because each proved solution is expressed in Python, interpretable wordplay reasoning for proven answers is available for inspection

Decision: reject
Reviewer scores: 6, 5, 3, 8

Reviews and discussion:
<thread>
creation date:
1729715192298

thread_type:
official_review

<thread_object>
creator: reviewer_2vau

<content>
summary:
The paper introduces a novel reasoning approach to generate answers for cryptic crossword clues. It is a multistage approach which does the following:
1. First, a fine-tuned LLM suggests possible answers for the entire clue.
2. Second, for each candidate answer, another LLM generates possible definition/wordplay suggestions.
3. Third, for each suggestion, another few-shot LLM generates python code which wraps their domain-specific language to prove the wordplay. If there's an error in the verifier, it is fed back to the LML in a loop up to K times to improve/correct the proof. If there is no error, the answer is used as the final prediction. 

This system improves overall performance on the Cryptonite dataset from 15.7% to 32.5%, and the authors give some analysis on the benefits and shortcomings of their approach.

strengths:
* The authors introduce a novel approach to a uncommonly studied task, which has interest to the NLP/reasoning communities for its difficulty and unique reasoning requirements, and to the cryptic crossword hobbyist community. They provide motivation for why this task is relevant and should be worked on. 

* Their approach is effective, more than doubling the previous SOTA performance on the same task. Additionally, it offers several "obvious" avenues for improvement as it breaks the task down into more easily tunable parts.

* Finally, the paper is very clearly written and communicates their relatively unknown task and novel method effectively.

weaknesses:
* A full ablation study would make clear the shortcomings of each part of the pipeline. While the authors demonstrate the effectiveness of just using the top candidate answer, it would be helpful to know the benefit of adding the definition/wordplay model (combined with e.g., a simple LLM-based reranker) compared with the full pipeline.

questions:
- When you say `The Wordplay dataset follows the train, validation, and test split defined by
  Cryptonite`, I assume you mean there is no contamination between the two, i.e., no clue in the
  train dataset for Wordplay will appear in the Cryptonite val/test splits. Is this correct or did
  you have mean something different?
- The performance of your pipeline is of course capped by the recall of the candidate answer
  suggestion model, which seems to be about $40$% at $N=20$. This means that the rest of your pipeline
  can correctly choose about $32.5 / 40 \approx 81$% of the results, which seems promising. Have you
  considered just making N as large as possible? It might be an easy (albeit inefficient) way to
  improve overall performance by a bit, assuming the rest of the pipeline is robust to many wrong
  candidates.
- Also, I'd be curious to know how much the 'verification' system helps. While your system is
  certainly effective, I wonder how much the verification system improves over a "dumb" reranker
  (e.g., scoring the probability of each (answer, definition/wordplay) pair using the LLM and
  choosing the best).
</content>
</thread_object>

</thread>
<thread>
creation date:
1730497511532

thread_type:
official_review

<thread_object>
creator: reviewer_pnnh

<content>
summary:
This paper identifies the gap that cryptic crosswords, a well-known language-oriented reasoning puzzle, have received little attention from the community. To this end, the authors propose a system that combines LLMs and a Python interpreter to solve cryptic clues. In the paper, they elaborate on the system architecture and run experiments using Gemma and Gemini model family to show better performance than the baselines on Cryptonite benchmark.

strengths:
Identifying the gap that cryptic crosswords have received little attention from the community, especially post LLM era, the authors propose a framework that combines LLMs and a Python interpreter to solve cryptic clues, and show better performance than baselines on Cryptonite benchmark.

weaknesses:
1. This paper may lack enough strong baselines and the comparisons with these baselines may not be entirely fair. There are 3 baselines including rule-based, a fine-tuned T5 large, and Gemini Pro 1.0 zero-shot. First, The T5 large model only has 770M parameters while Gemma 9b (which is used in this paper) has 9B parameters. Comparing Gemma 9B-FT with T5, we can see that changing the model with the same training data improved the accuracy from 7.6% to 15.9%. Second, Gemini 1.5 Flash is used in the proposed system while the baseline is zero-shot Gemini Pro 1.0 which shows inferior performance across general benchmarks. Third, while the papers mentions limited computation resource, rows in table 1 are reported based on different number of examples, which make them not comparable.

2. It may not be clearly stated in the paper the reason of following the proposed order: i.e. generating answer candidates first, then generating possible definitions and wordplays, and then doing verification. Reasoning tasks typically generate reasoning steps followed by the final answer and verification, e.g. ReAct format. In this case, possible definitions and wordplays can be followed by the final answer candidates and external verifiers. This is also consistent with line 44 regarding the reasoning steps. Have you tried different variations and concluded that the proposed order is the best?

questions:
1. Regarding weakness 2, have you tried different variations and concluded that the proposed order is the best?
2. Since the current system combines multiple open source fine-tuned models (Gemma) and a closed source model (Gemini) for different stages, I wonder if you have tried a single model performing all different tasks, either prompting or fine-tuning, which makes the system simpler?
3. The last paragraph in section 2.2 mentions that an apple-to-apple comparison with Rozner et al. (2021) is hard because of different split setting. Could you elaborate more on the challenge of comparing using the same data? Is it because the test split in one approach is used for training of another approach, or their model is not publicly available?

Minor points => Typo(s): 
1. Line 155, T5 large is 770M
2. Line 200, the first sentence in section 3.1 has two “from”
3. Line 344, that -> than
</content>
</thread_object>

</thread>
<thread>
creation date:
1730647971547

thread_type:
official_review

<thread_object>
creator: reviewer_5dqk

<content>
summary:
The authors propose a method that achieves state of the art performance on cryptic crosswords. The method uses LLMs to solve the subtasks using various strategies. First, Gemma2-9B is fine-tuned using low-rank adapters on answer-candidate generation, which returns a list of answers which match the 'pattern' (the length of the answer). Second, Gemma2-9B is again fine-tuned using low-rank adapters, but this time for 'wordplay suggestion', which takes each answer candidate and generates multiple definition/wordplay pairs, which are meant to explain why the answer is correct. Third, prompting is used in combination with Gemini-Flash to formalise the wordplay into Python 'proofs'. The Python proofs are run and any errors are reported back to Gemini-Flash, which is given a chance to correct its proof (until the answer is valid, or the maximum of 2 rewrites is reached). In the experiments, the formalisation process is shown to be helpful in the general, although for the 'Quick' subset, using the most frequent answer candidate proves too strong a baseline.

strengths:
- State of the art result on complex task.
- The reported results show that LLMs are very helpful as components in a system to solve complex tasks, while also not sufficient to solve it completely on their own.

weaknesses:
- I think more space could be devoted to explaining cryptic crosswords. As someone previously unfamiliar with them, it took quite long for me to understand what exactly was happening in the example given in the introduction. Maybe a table or diagram that explains exactly how each part in the wordplay is related to the parts in the clue?
- A solid motivation for why this work is important is missing. What is the primary reason to be interested in LLM performance on this task? And relatedly, what should be the general take-away after reading it?

questions:
How were the in-context learning prompts constructed, and how many versions did you try? What is your sense of the sensitivity of the final accuracy w.r.t. the prompt, how important is it?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730689440846

thread_type:
official_review

<thread_object>
creator: reviewer_hu2t

<content>
summary:
The paper proposes a reasoning-based system for solving cryptic crossword clues using fine-tuned LLMs and a Python-based verification process. The model generates candidate answers and wordplay suggestions, formulates these into Python code, and verifies correctness via assertions.

strengths:
**Originality**
The paper offers a unique approach to solving cryptic crossword clues. Like math proofs, the authors combined LLMs for candidate generation, wordplay suggestions, and formalized Python-based verifiers.

**Quality**
The paper details the fine-tuning of models for clue and wordplay generation and the creation of a domain-specific verifier, including formalization in Python. The experiments demonstrate a clear improvement over previous state-of-the-art results on the Cryptonite dataset, significantly outperforming prior baselines.

**Clarity**
The paper includes figures containing examples that help in understanding.

**Significance**
The paper shows an improvement in the cryptic crossword domain.

weaknesses:
1. The mention of a 23.5% accuracy on the Cryptonite dataset using GPT-4-turbo in the paper [1] suggests that a more rigorous baseline is possible for this study. Using the same prompting strategy on the Gemini-Flash that is used in the paper could provide better insight into the improvement of the proposed method.

2. The paper's reliance on the Wordplay dataset, gathered from newspapers (The Times, etc.), raises the possibility of data leakage, as The Times also contributes to the Cryptonite test set. If fine-tuning data includes patterns or clues from the test set, results may be artificially inflated.


[1] Saha, Soumadeep, et al. "Language Models are Crossword Solvers." arXiv preprint arXiv:2406.09043 (2024).

questions:
1. Partial correctness metrics, as reported in [1], can provide a more nuanced understanding of model success on cryptic crosswords, where the model might have answered some rows/columns but not the whole crossword.

2. Some minor corrections on line 200 ("from" is repeated twice)

[1] Saha, Soumadeep, et al. "Language Models are Crossword Solvers." arXiv preprint arXiv:2406.09043 (2024).
</content>
</thread_object>

</thread>
<thread>
creation date:
1732566723766

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
## Up-to-Date Baselines

We have run 5-Shot prompting benchmarks to increase the strength of the baseline, 
and the following results can be substituted for the 'Gemini-1.0-Pro' line in the paper's Table 1:

| model |  samples | val-overall |  val-quick |  val-hard | test-overall |  test-quick |  test-hard |
| :---------- | ----------: | ----------: | ----------: | ----------: | ----------: | ----------: | ----------: |
| Gemma2-9B-it  | 1000 | 5.7% | 11.5% | 5.2% | 4.5% | 10.5% | 4.0% |
| Gemini-1.5-Flash-001 | 1000 | 6.6% | 12.5% | 6.1% | 6.5% | 11.8% | 6.1% |
| GPT-4o (2024-11-25) | 1000 | 29.8% | 45.0% | 28.5% | 27.6% | 47.4% | 26.0% |

Interestingly, this shows that:
(a) GPT-4o_2024-11-25 gives stronger results than those of GPT-4-Turbo_2024-04-09 given in Saha (2024);
(b) Gemini-Flash (which was used in development of the formaliser) is not particularly good at solving cryptic clues in itself;
(c) The Gemma2-9B model gets a large uplift from fine-tuning on the Cryptonite training set (compared to 5-shot prompting).

Given the large gap between the performance of GPT-4o and those of 
Claude 3 Sonnet / GPT 3.5 Turbo reported in Saha (2024), 
it seems reasonable to postulate that the GPT-4 model
has also been fine-tuned on the Cryponite dataset itself.  Further evidence being that, 
as shown in Saha (2024), the GPT-4 model hardly benefits from CoT prompting (with 3-way self-consistency) - 
it seems that GPT-4 is familiar the facts, but not the reasoning.

We will update the paper throughout to reflect the new baseline - against which we note we still
have a state-of-the-art result, both with Gemini-Flash as the Formaliser, and (narrowly) with
a fully Open-licensed solution (using Gemma2-9B models throughout).  An additional aspect to note is 
that the method provided in the paper provides clearly interpretable output, since
the reasoning steps are made directly available (as in Figure 3).
</content>
</thread_object>

</thread>
<thread>
creation date:
1732620296779

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
## Exploiting Partially Filled Grids

We have run an analysis to address the Exploiting Partially Filled Grids section of Saha et al (2024), 
the results are as follows (note that these are on the Cryptonite splits, 
rather than their 'Init', though the percentage differences are large enough to draw some initial conclusions):

| model | Hint (%) | samples | val-overall |  val-quick |  val-hard | test-overall |  test-quick |  test-hard |
| :---------- | ----------: | ----------: | ----------: | ----------: | ----------: | ----------: | ----------: | ----------: |
| Gemini-Flash | 25% | 200 | 37.0% | 38.5% | 36.9% | **45.5%** | 66.7% | 43.8% |
| Gemma2-9B-it | 25% | 200 | 37.5% | 38.5% | 37.4% | 44.0% | 66.7% | 42.2% |
||
| FastText k=0 NN | 25% | 200 | 15.5% | 15.4% | 15.5% | 21.0% | 33.3% | 20.0% |
| FastText k=0 NN | 50% | 200 | 52.5% | 38.5% | 53.5% | **62.0%** | 46.7% | 63.2% |
| FastText k=0 NN | 70% | 200 | 79.0% | 61.5% | 80.2% | **81.0%** | 100.0% | 79.5% |

The first two rows show the effect of simply filtering the output of our Gemma2-9B fine-tuned candidate answer 
proposal model, based on a random letter pattern (using the same formulation as Saha et al (2024)) and then
using the rest of our pipeline.  Here, our paper's approach outpaces their reported GPT-4T results, but is itself
limited by our first stage Gemma2 model's 'Top-20' candidate answers
only containing the correct answer only around 45% of the time 
(as astutely observed by another reviewer).  Since the existing Gemma2 has not been fine-tuned on the filtering 
task, the other top-20 results are essentially restricting our systems performance, 
even at this low level of partial fill.

To gain an insight into higher levels of partial fill, 
and perhaps bolster our earlier comments on the relevance of these statistics,
the 'FastText k=0 NN' lines correspond to running a nearest neighbour (i.e. k=0) search.
For each question, we search for the whole clue (without any special processing)
over the FastText (Bojanowski et al (2016)) embeddings of a crossword word list 
(The UK Advanced Cryptics Dictionary - Beresford (2000)) which
contains 250,378 valid words that might be found in crosswords 
(Note that the wordlist is not exhaustive, 
since 7.0% of the gold answers do not appear in the list).  We then
use the closest found word as the 'FastText k=0 NN' model answer.  While the 25% line is lower-performing 
than the models considered in our work, the 50% (realistic for solvers) and 70% lines show 
that even this simplistic nearest neighbour search outperforms all the models of Saha et al (2024).  

The kNN systematic approach would (naturally) form the baseline for our models in the partially filled grid case, 
and thus opens up an interesting line of attack for future work 
(although, as mentioned, we prefer to focus on the stand-alone clue problem, 
since the reasoning aspect there is most applicable across other fields, such as mathematical theorem proving, 
where we see no clear analogy with partially filled answers).
</content>
</thread_object>

</thread>
<thread>
creation date:
1732792739502

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
### Revised PDF

An updated PDF has been uploaded, including many changes that have been prompted by reviewer feedback:

* **Motivation** - the initial focus has been altered to emphasise 
that the core challenge of this work is one of 
reasoning using LLMs.  Cryptic crosswords is a fascinating test-bed for this
* **Diagrams** - 4 separate cryptic clues are shown in diagram form (our new Figure 2), 
which aim to make the principles of cryptic solution clearer for those unfamilar with the topic
* **Pipeline Ordering** - an introductory section discusses the choices made, which may have seemed unusual at first
* **Wordplay dataset splits** - the deliberate alignment of the Wordplay splits with Cryptonite have been highlighted
* **Candidate list size** - this was additionally commented on in the Methods section
* **ICL Prompting** - this has been clarified a little, specifically which parts of the process required care,
and also the degree of transferability of the ICL prompts from Gemini-Flash directly to Gemma2-9B-it 
(an off-the-shelf open-licensed model)
* **Baselines** - updated baselines have been incorporated into the results.  We note that our system
still achieves a new state-of-the-art result, 
and our same pipeline built using fully open-licensed models would also beat the previous state-of-the-art
* **Ablations** - 2 ablation results were added, showing the effect of using average-logprob measures from
the LLMs generating (a) candidate answers, and (b) wordplay hypotheses.  The second of these 
(which showed limited performance) was a little surprising.  Overall, these ablations showed that 
neither 'dumb ranker' would be able to remove the need for formalisation/verification step.  Many thanks are due 
to reviewer `2vAu` for this insightful suggestion.
* **Testing on 'Init'** - we have updated the discussion in Section 2.2 to explain our focus on the Cryptonite
dataset, and added a more detailed break-down in the Appendix.  The appendix explanation also
identifies the looming problem of cross-contamination of training vs test data
(specifically for commercial models) between Cryptonite and the Rozner datasets
* **Partial Correctness Metrics** - this aspect 
(more related to solving full grids than the standalone solving that was the main focus of our work),
along with a viable solution approach, is now described in our Methods Section 3.6.  For reasons of space, 
the corresponding table of results is in the Appendix.

The authors are confident that the paper has been significantly improved through the review process so far,
and welcome the opportunity for further discussion that ICLR has provided by 
extending the author/reviewer discussion period.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733312639800

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We greatly appreciate the reviewers' time and effort in evaluating our paper, including their careful review of our revisions. Your feedback has been invaluable in strengthening our work.
</content>
</thread_object>

</thread>


Metareview:
metareview:
**Summary**

The paper fosus on the problem of cryptic crosswords for LLMs by proposing a sort of CoT model to solve varius subtasks.

**Strengths**

- The paper present a CoT to solve an apparently complex task

**Weaknesses**

- A solid motivation for why this work is important is missing. Even after the rebuttal, motivation is really weak. The inportance should be better evalated.


**Final remarks**

- The paper can be better motivated