acceptodds
Under review as a conference paper at ICLR 2027

Neurosymbolic Generation of Valid Cryptic Crosswords with Proof-Guided Clue Generation and Constraint Solver Driven Grid Construction

Abstract

Cryptic crosswords are crossword puzzles where each clue contains both a semantic definition for the solution and a wordplay from which the solver should construct the solution, for instance, using anagrams, homophones or hidden words. As in a regular crossword, the solutions are also connected together in an interlinking grid. Generating puzzles that satisfy this complex set of linguistic and combinatorial constraints presents an interesting challenge for natural language processing. In this work, we evaluate the ability of LLMs to generate valid cryptic crosswords. We break this problem down into two tasks: clue generation, and grid construction and demonstrate both tasks are still beyond the current abilities of state-of-the-art LLMs. However, whilst LLMs alone cannot solve this problem, we show that by combining LLMs with a domain-specific proof language, a set of deterministic validation tools and a satisfiability solver, we can generate cryptic crossword puzzles that are both syntactically and semantically valid.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
crosswords, constrained generation, LLMs, puzzle generation

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_Wb1zOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the generation of cryptic crosswords through a neurosymbolic pipeline. For clue generation, an LLM produces clues and executable DSL derivations, which are checked and revised through a generator–validator loop. For grid construction, the paper encodes crossword rules as satisfiability constraints and explores two ways to incorporate LLM-proposed placements. Experiments compare direct generation with the proposed methods and evaluate clue correctness, answer diversity, several quality proxies, and grid construction performance.

Critical strengths
  1. The paper addresses an interesting constrained-generation problem. Cryptic crosswords combine semantic definitions, exact letter-level transformations, and global grid constraints. This makes them a useful setting for studying how language generation can be combined with symbolic verification.
  2. The pipeline provides a concrete integration of generation, validation, and constraint solving. Executable derivations make the proposed wordplay inspectable and support targeted feedback. The experiments demonstrate improvements in weaker models’ clue correctness and show that symbolic methods can construct valid grids where direct LLM generation fails.
Critical weaknesses
  1. The practical advantage over direct generation remains unclear. GPT-4o improves from 1% to 16% correctness but remains unreliable. For GPT-5.5, correctness stays at 95%, while unique answers increase from 70 to 84 at approximately 2.5 times the reported runtime (Table 4). These results suggest a trade-off rather than a clear overall improvement. A budget-matched comparison of valid, unique outputs is needed to establish the method’s practical value.
  2. The quality evaluation is not sufficiently validated. The stated dimensions—naturalness, appropriate difficulty, and misdirection—are reasonable, but perplexity and clue–answer semantic distance are not validated against expert judgments of these properties. Although an expert checks correctness, this does not establish broader clue quality. Moreover, Table 5 evaluates only correct clues, leaving some baseline quality estimates based on just one or three examples.
Questions for authors
  1. Generation efficiency: Under the same budget, how does the full pipeline compare with direct sampling followed by deduplication and equivalent filtering? Could you report the number of valid, unique clues produced per unit of time or cost?
  2. Validator reliability: Why does correctness remain at 16% and 20% for the weaker models despite the validation loop? Do the remaining errors reflect incorrect validator acceptance or unsuccessful repairs after reaching the iteration limit?
  3. Quality evaluation: Could you validate perplexity and clue–answer semantic distance against expert judgments of naturalness and misdirection? What evidence supports the assessment of clue difficulty beyond these automatic proxies?
  4. Grid construction: Does LLM guidance improve upon standalone SAT when the required number of placed answers and computational budget are matched? This would help distinguish efficiency gains from reductions in the number of answers included.
1 comment

We will answer the questions in order, but we first note that we have updated the presentation of the tables, which can be found here: https://filebin.net/6rol5zg2e10o79w8

Q1: Generation efficiency

It’s true that our pipeline takes more time per correct clue, but we believe this is justified by the number of clues that were repaired (21). It is possible that direct generation would be able to generate more correct clues in the time this repair took, but we note that some clue types are particularly prone to incorrect clues and duplicate clues e.g., homophones, so re-generating in this category is likely to be challenging.

Neither approach currently automates deduplication, so a fair comparison would be to add deduplication into the sampling loop for both direct sampling and our full pipeline. We will add a comparison in the final version to a loop which simply generates in the DSL, discards any invalid or duplicate clues and keeps sampling until a fixed time budget. Note that this is really only possible for generating in the DSL, since there is no accurate way to validate the plain text clues (our experiments with auto-formalization into the proof DSL produced very poor results).

Q2: Validator reliability

These errors are primarily the result of the model failing to repair errors before reaching the iteration limit. We evaluated our evaluator and found it to be 95% accurate on a mix of human-written and generated clues, and will include validator accuracy data in the final version. False positives from the validator are a result of the synonym checker being unduly generous.

Q3: Quality metrics

We have run a user study (with ethics approval), with 46 solvers rating a subset of generated clues in an attempt to provide more accurate quality ratings.

We found that perplexity and semantic distance separate human-written from generated clues at the dataset level (Mann–Whitney p < 0.05, 60 clues per source), but in the user study perplexity did not correlate with perceived quality (Spearman ρ = −0.17, p = 0.50), so we treat these metrics as measures of stylistic resemblance to human clues rather than of quality. Solvers themselves could barely tell the two apart, correctly identifying whether a clue was human-written or generated only 58.5% of the time (Cohen’s κ = 0.17 against a 50% chance rate; 63% for expert solvers). We will update the text accordingly.

However, validity is clearly the most important metric and our pipeline produces more unique valid clues than the baseline.

Q4: grid construction

Both methods use the same binary search over the required number of answers, with a 200 s timeout per level, and our previous table accidentally included only the final solve time for the SAT only baseline. Over the full search, including timed-out levels, the incremental variant places as many answers as SAT (21.0 vs. 21.0, averaged over the six answer sets) using 11% less total time (450 s vs. 508 s), while the soft variant places about 1.8 fewer answers for a smaller saving (468 s). In general, this gain comes from being able to solve problems on which the SAT only case times out. We will clarify in the text

We will include a comparison for specific numbers of words and density requirements in the final version as well as the data on each iteration in the binary search.

Reviewer_ivomOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper addresses the problem of generating valid cryptic crosswords, where each clue consists of two components: a semantic definition of the answer and a wordplay component that describes how to derive the answer through wordplay involving the words or letters in the clue. The paper evaluates the ability of different large language models (LLMs) to generate cryptic clues and arrange them into valid crossword grids.

The paper proposes a neurosymbolic approach with two main components: (1) Verified clue generation: The LLM generates each clue along with a proof, expressed in a domain-specific language (DSL), that specifies how the wordplay leads to the answer. A verifier checks the validity of this proof. (2) Solver-guided crossword construction: Since LLMs struggle to generate entirely valid crossword grids, the proposed method uses the LLM's partially valid output to guide a SAT solver, which constructs a crossword satisfying all the required constraints.

Critical strengths
  • The way the work uses the partially correct output of LLM to guide a SAT solver is interesting. The partially valid outputs of the LLM introduce additional constraints that forces the solver to solve for the remaining variables.
Critical weaknesses
  • The main novelty appears to be extending the DSL-based proof approach for cryptic clue generation introduced by Andrews et al. (ICML 2025) to full crossword generation. However, the contribution of the LLM to the grid generation remains unclear. Table 3 shows that the SAT solver alone achieves comparable, and sometimes better, performance in significantly less time than the SAT+LLM approaches. This raises questions about the added value of incorporating the LLM and the overall effectiveness of the proposed approach. While the paper states the LLM is effective in instances where the clues and answers are "hard", the paper doesn't provide further analysis on this.

  • The experimental section needs further refinement. The dataset and its characteristics are not clearly described, and Table 3 is difficult to interpret. In particular, the meaning of Gen1, Gen2, and so on is unclear. Are these independent runs, different generations, or different experimental settings?

  • The results in Table 5 do not clearly demonstrate the effectiveness of the proposed method. Incorporating the DSL leads to worse reported metrics across the board: higher perplexity, lower semantic distance, and shorter clues. It is unclear how these changes relate to clue quality, and the paper should provide stronger evidence that the proposed approach improves cryptic clue generation.

  • GPT-5.5 already achieves good performance in cryptic clue generation, while incorporating the DSL leads to a decline in performance. It is unclear whether this observation is specific to GPT-5.5 or also holds for other capable agentic foundation models. The evaluation would benefit from experiments with open-source models to better understand the generality of the findings.

  • The work focuses on a specific problem, namely cryptic crossword generation, and it is unclear whether the proposed ideas can be generalized to other domains.

Questions for authors
  • Describe the Datasets clearly. Cite the Times Dataset. For your approach, how the runs Gen1, Gen2 etc are generated? How do we know the clues are difficult or easy for grid generation.

  • Please provide analysis of the results in table 5. Is the DSL really improving the quality of the clues?

  • Please explain the core contribution (and novelty) clearly. Many recent works [1,2,3] use SAT solver with LLM in their pipeline. Is this work's contribution is in applying those technique to cryptic crossword generation?

[1] SATLM: satisfiability-aided language models using declarative prompting. (Xi Ye et al., NeurIPS 2023)

[2] Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning (Pan et al., EMNLP Findings 2023)

[3] Bridging LLMs and SAT Solving: Automated Evolution of High-Performance Heuristics (Mao Luo, et al., International Joint Conference on Artificial Intelligence, 2026)

1 comment
AuthorsOpenReview ↗

Update data and contributions summarised

We will first answer the questions and then respond to the weaknesses. First we note that we have updated the presentation of the tables, and the new ones can be found here: https://filebin.net/6rol5zg2e10o79w8

Q1: The dataset.

The Times dataset consists of 100 clues taken from publicly available Times cryptic crossword clues, and was constructed by us. We will make the dataset public (it is temporarily here: https://filebin.net/6rol5zg2e10o79w8)

Gen1-4 are word lists generated by our pipeline (each word list is a sample of 50 of the answers to the clues generated by the previous experiments, filtered to exclude invalid clues and duplicates). Times1 and Times2 are word lists taken from the Times dataset. We will rename these to wordlist1 wordlist2 etc. When we say the clues are difficult or easy for grid generation, we mean that the standard approach of using a SAT solver to find a valid grid takes a long/short time respectively. We will clarify in the text.

Q2: improvement in quality

The most important metric to consider is the number of unique and valid clues generated, and our pipeline with GPT5.5 finds 84 distinct and valid answers, instead of 68 without the pipeline (see updated table 4 which make this clearer. Our previous table presented correctness percentages including duplicate clues).

Considering the quality metrics, Table 5 compares the correct generated clues with Times Quick Cryptic clues. The generated clues are similar in length but less misdirecting (semantic distance 0.67–0.71 vs 0.80) and perplexity is slightly increased. The DSL and validator raise correctness without materially changing these measures for GPT5.5.

However, whilst perplexity does increase for GPT 5.5, this isn’t a perfect metric for fluidity, as demonstrated by the fact the times crosswords actually have higher perplexity than GPT4o. We have run a user study (with ethics approval) on a subset of generated clues, and we found that perplexity and semantic distance distinguish human from generated clues (Mann–Whitney p < 0.05 on 60 clues per source), but a user study with 46 solvers rating 18 clues (6 human-written, 12 generated) found no significant correlation between perplexity and mean perceived quality (Spearman ρ = −0.17, p = 0.50). We will add this data into the paper, and a more nuanced discussion of the quality metrics

Q3: Our Contributions:

Our main contributions are:

  • A proof-guided clue generation approach, which improves clue validity over baseline LLMs. Prior work (Andrews) uses a proof DSL for solving crossword clues only, and not for generation. In order to use the DSL for generation, we extended and further developed several aspects of the DSL and the validator, improving robustness and accuracy substantially. Prior work on constrained text generation cannot handle constraints as complex as those required for cryptic crosswords.

  • An approach to grid layout that allows an LLM to provide intuition that helps a SAT solver complete the grid layout, on hard problems, by providing suggested constraints which guide the SAT solvers initial assignment choices. Prior work uses SAT solvers to help LLMs solve problems by enabling LLMs to use solvers in their reasoning, or uses LLMs as auto-formalization of problems which are then solved by a SAT solver. The closest work to our approach is [3], which evolves the heuristic functions of a SAT solver with an LLM to improve solving speed. Our approach aims to improve solving speed but does it by allowing the LLM to input suggestions about the satisfying assignment, which enables it to use intuition about the problem domain more directly.

This contribution to grid layout is in the updated table 3. This originally reported the runtime only for the final successful solve for the baseline and omitted the levels of the binary search. Measured over the whole search, the incremental LLM-guided variant places as many answers as the SAT solver (21.0 vs. 21.0 on average) in less total time on five of the six answer sets (mean 450 s vs. 508 s). By “hard” we mean the instances on which the standalone SAT search takes longest (Times 2 and Gen4, at 600 s and 727 s); on both, the incremental variant finishes sooner (443 s and 538 s).

Other weaknesses

open source models

We would be happy to add an evaluation with Qwen 3.5

Applicability beyond crosswords

We chose cryptic crosswords as a demanding testbed, but the two parts of our method are general patterns:

  1. Generation in DSLs raises validity when using small models. This result is also reported in Mora et al. (2024), in a different domain, which suggests this effect is not specific to crosswords

  2. Using LLM soft-constraints as hints for a solver has potential applications in other domains where the task is to solve an NP-hard problem, but large amounts of historical data may exist on how similar problems were solved (for instance, timetabling and planning)

Reviewer_1MBeOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes a two-stage neurosymbolic pipeline for generating valid cryptic crossword puzzles, decomposing the task into (1) cryptic clue generation and (2) crossword grid construction. For clue generation, the authors adapt a Python-based domain-specific language (DSL) originally developed for cryptic crossword solving (Andrews & Witteveen, 2025a,b) into a generator-validator repair loop: an LLM is prompted to output both a candidate clue and an executable DSL proof asserting its definition, indicators, abbreviations, and string manipulations, which are verified using lookup databases (CrosswordQA, curated indicator/abbreviation lists), fastText similarity, deterministic Python string checks, and fallback LLM calls. For grid construction, the authors formulate 13×13 grid layout over a 50-word candidate pool as a satisfiability/SMT problem in Z3 and propose two ways to warm-start the solver using GPT-4o placement suggestions: an incremental solver (which pushes valid LLM placements onto the Z3 assertion stack and pops them upon conflict) and an optimization solver (which adds LLM placements as length-weighted soft constraints).

Critical strengths
  1. The paper worked on a very interesting and motivated NP-Hard problem.
  2. The analysis in Table 6 provides very meaningful insights. It demonstrates that GPT-5.5 exhibit good local constraint-following ability yet consistently ignores global constraints.
Critical weaknesses
  1. Neither Table 3 and Table 4 fully support your claim that the proposed neurosymbolic component helps. In Table 4, GPT 5.5 already achieved good performance, and was dragged down by the neurosymbolic component. It seems to be only working on inferior models. Table 3 even demonstrate that using your pipeline consistently hurts model performance.
  2. I believe there is a bug in Algorithm 1. Currently it pops in LIFO order, resulting in popping shortest words first, which is a direct contradiction to your claim in Section 3.2.
  3. The paper, expecially its results section, needs better polishing in presentation. Table 3's bolded items seems to be random and misleading, and Table 4 and 5 are poorly formatted.
Questions for authors
  1. Could the author explain why GPT-5.5, after using the proposed component, has a worse performance?
  2. Could the authors provide more error analysis on why GPT 4o and 5.2 performs bad?
1 comment
AuthorsOpenReview ↗

We have updated the tables!

Weakness 1/3: tables

We agree the presentation of the tables was confusing. We’ve attached a clearer version, but we disagree that Table 3 demonstrates our pipeline consistently hurts model performance. Also, while preparing the revised tables we also found that the two LLM-guided rows of Table 3 were misaligned with the answer-set columns, and that the reported times covered only the final successful solve rather than the full search; both are corrected in the following version.

In Table 3: Stand-alone LLMs never produce a valid grid, so we compare against the SAT solver alone. Guided by LLM suggestions, the incremental variant places the same number of answers on average (21.0 vs 21.0), builds denser grids on four of six answer sets, and completes the full search in less total time on five of the six answer sets, including the two hardest (mean 450 s vs. 508 s; worst case 563 s vs. 727 s).

Table 4: For every model, the DSL and validator together give the highest correctness and the most distinct correct answers. For GPT-5.5, which is already highly accurate, correctness stays at 95% but the correct clues cover 84 distinct answers instead of 68, so the model repeats itself less.

The updated tables can be downloaded from here (for the next 6 days): https://filebin.net/6rol5zg2e10o79w8

(We are unable to add improved tables to this response because of the character limit)

Weakness 2: bug in alg 1

There are two methods for SMT solving. The first uses simple incremental solving, which attempts to find a grid for all words. The words are all added to the solver at once, longest first (as per line 288 and lines 7-9 of algorithm 1). We then try to find a valid grid (line 11 alg 1) and if cannot find a grid, it removes the most recently added constraint i.e., the shortest word (as per line 289 and line 15 of algorithm 1). The text and the algorithm are consistent. The solver will find a placement that uses the longest words.

The second method uses an optimization solver. Here all constraints are added with a cost, which is equal to the length of the word. The solver aims to minimize the cost of the unsatisfied constraints. This means it will be biased towards placing longer words Both approaches are consistent: they attempt to find grids with the longest words placed.

Question 1: Why is GPT5.5 worse with the pipeline?

Actually, for every model, the DSL and validator together give the highest correctness and the most distinct correct answers. For GPT-5.5, which is already highly accurate, correctness stays at 95% but the correct clues cover 84 distinct answers instead of 68, so the model repeats itself less.

Clue quality is harder to quantify beyond validity. Table 5 compares the correct generated clues with Times Quick Cryptic clues. The generated clues are similar in length but less misdirecting (semantic distance 0.67–0.71 vs 0.80). The DSL and validator raise correctness without materially changing these measures.

Whilst perplexity does increase, this isn’t a perfect metric for fluidity, as demonstrated by the fact the times crosswords actually have higher perplexity than GPT4o. We have run a user study (with ethics approval) on a subset of generated clues, and we found that perplexity and semantic distance distinguish human from generated clues (Mann–Whitney p < 0.05 on 60 clues per source), but a user study with 46 solvers rating 18 clues (6 human-written, 12 generated) found no significant correlation between perplexity and mean perceived quality (Spearman ρ = −0.17, p = 0.50). We will add this data into the paper, and a more nuanced discussion of the quality metrics

Question 2: Error analysis for GPT4o and 5.2

GPT4o and GPT5.2 are simply incapable of satisfying the rules for valid cryptic crossword clues. We manually analyzed the errors and the most common error from GPT5.2 was including the answer in the clue e.g., “sincere upset is a rescue (RESCUE)”. The most common error for GPT4 was producing clues with no actual wordplay, e.g., “Overpower completely? (OVERWHELM)” is just a standard crossword clue with a semantic definition. Other common errors for both models were letters not adding up, for example “Rage set to become rank (SERGEANT, missing an N)”, and invalid wordplays using invalid synonyms, e.g., “Might generate power -> flower”.

We will add a table with an error analysis.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.