Mini Crosswords Eval

mini-crosswords-eval

Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models — Sel et al. (2023) (arXiv:2308.10379, 2023)

What this evaluates

Evaluates an LLM's ability to perform algorithmic search and recursive reasoning within a single generation window, without external tree search or iterative prompting. It probes systematic exploration, pruning, and backtracking capabilities in a lexical constraint satisfaction task.

Datasets

• Mini Crosswords — total 20; splits: test (20)

Metrics

• Word success rate (primary) — range: percent
  • Percentage of instances where the model correctly fills the entire 5x5 crossword grid matching the provided across/down clues. Calculated as (correct predictions / total instances) * 100.
• Avg. Queries — range: other
  • Average number of LLM generation calls or API requests required per instance to produce a final answer.

Input / output format

Input: A 5x5 grid with across and down clues. Prompts include a 5-shot in-context setup with algorithmic search trajectories and a two-step warm-up phase.

Output: A fully filled 5x5 grid of words that satisfy all across and down clues.

Scoring recipe

def score_crosswords(predictions, gold_grids):
    correct = 0
    for pred_grid, gold in zip(predictions, gold_grids):
        if pred_grid == gold:
            correct += 1
    return (correct / len(gold_grids)) * 100

Common pitfalls

• Early errors cascade through the grid, making it difficult to isolate whether failures stem from initial word selection or later pattern extraction.
• The model's backtracking capability is often underutilized in single-generation mode, causing it to commit to incorrect words prematurely.
• Comparing against ToT is complicated by ToT's use of external memory for backtracking, which AoT must simulate internally within token limits.

Evidence (verbatim from paper)

Table 3 underscores AoT’s proficiency in the mini crosswords task, showcasing a word success rate—a measure used in existing studies to represent the percentage of words correctly completed out of the total—that surpasses earlier methods reliant on various prompting techniques.

Citation

@misc{sel2023algorithmofthoughts,
  title={Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models},
  author={Sel et al. (2023)},
  year={2023},
  note={arXiv:2308.10379}
}

• arXiv: 2308.10379