Introduction

Complex games such as chess and Go have long been a source of inspiration to develop more flexible and robust AI systems [1,2]. Recent developments in NLP suggested that creative language games could be exploited as promising benchmarks for quantifying the ability of large language models (LLMs) to carry out multi-step knowledge-intensive reasoning tasks under pre-specified constraints [3]. While crossword puzzles have been historically the main focus of such efforts [4], other categories of linguistic games received only marginal attention, especially for languages other than English. A prominent example of less-studied language games is the rebus, a visual puzzle combining images and graphic signs to encode a hidden phrase. Indeed, rebus solving is a complex, multi-step process requiring factual knowledge, contextual understanding, vocabulary usage, and reasoning within pre-defined constraints -a set of fundamental skills to address a variety of real-world tasks.

In this work, we conduct the first open evaluation of LLMs' rebus-solving capabilities, focusing specifically on the Italian language. We propose a novel strategy to derive text-only verbalized rebuses from transcribed intermediate rebus solutions and use it to produce a large collection with more than 80k verbalized rebuses. We then evaluate the rebus-solving skills of state-of-the-art LLMs, Solution key (# of chars/word): 11 5 including open-source systems and proprietary models, via few-shot prompting. Moreover, we fine-tune a small but capable LLM on verbalized rebus solving, outperforming state-of-the-art systems by a wide margin. Finally, we conduct a fine-grained assessment of LLMs' sequential reasoning steps, explaining model performance in terms of word complexity and memorization.

Gabriele Sarti et al. CEUR Workshop Proceedings

1-10

Beyond rebus solving, our evaluation sheds light on the limits of current LLMs in multi-step reasoning settings, highlighting challenges with their application to complex sequential instruction-following scenarios.1

Background and Related Work

Italian Enigmistica and Rebuses The Italian language is characterized by a rich and long-standing tradition of puzzle games, including rebuses, dating back to the 19th century [5] 2 In Italian rebuses, a first pass (prima lettura) representing an intermediate solution of the puzzle is produced by combining graphemes with underlying image elements in a left-to-right direction (Figure 1). Then, the letters and words of the first pass undergo a re-segmentation (cesura) according to a solution key (chiave di lettura 3 ), which specifies the length of words in the solution (frase risolutiva). The verbalized rebuses we introduce in this work are variants of textual rebuses (rebus descritto or verbis), where the text-based puzzle is crafted by replacing first pass words with their crossword definitions in a templated format (Figure 1).

Linguistic Puzzles as NLP Progress Metrics

Language games have recently been adopted as challenging tasks for LLM evaluation [3,9,10]. While works in this area have historically focused on English crosswords [11,12,4,13], recent tests focus on a more diverse set of games such as the New York Times' "Connections" [14] and "Wordle" [15]. Automatic crossword solvers were also developed for French [16], German [17] and Italian [18,19], while didactic crossword generators are available for Italian [20] and Turkish [21]. Relatedly, the Italian evaluation campaign EVALITA 4 recently hosted two shared tasks focusing on the word-guessing game "La Ghigliottina" (The Guillotine) [22,23]. To our knowledge, our work is the first to attempt the computational modeling and evaluation of rebus-solving systems. Importantly, language games such as rebuses are not easily translatable into other languages due to their structural and cultural elements. This makes them a scarce but valuable resource for language-specific evaluations of language processing systems.

LLMs as Sequential Reasoners State-of-the-art

LLMs were shown to struggle to follow sequential instructions presented in a single query [24], but their performances improved significantly with ad-hoc training [25]. This acts as an initial motivation for our rebus-solving Models We fine-tune Phi-3 Mini 3.8B 4K [28], the most capable LLM below 4B parameters for a wide range of Italian language tasks8 . We use quantized low-rank adapters (QLoRA; 29, 30) for efficient fine-tuning with Unsloth 9and Transformers [31], training the model for 5,000 steps with a batch size of 16 over 81k examples. For comparing our model performances, we select GPT-4o [32] and Claude-3.5 Sonnet [33] as the current state-of-the-art for proprietary LLMs and the instruction-tuned variants of Qwen-2 72B [34] and LLaMA-3 70B [35] as the bestperforming open-source LLMs according to the Invalsi Italian benchmark [36]. These four systems are used as untrained baselines thanks to their instruction-following abilities and prompted for rebus solving in a few-shot setting.

Format Table 1 presents an example in the templated format used for fine-tuning Phi-3. 10 The model is prompted to reason step-by-step by 1) solving crossword definitions sequentially (definition resolution); 2) producing a first pass copying letters and definitions' words;

Prompt

Risolvi gli indizi tra parentesi per ottenere una prima lettura, e usa la chiave di lettura per ottenere la soluzione del rebus.

Rebus: U [Lo è il passacavallo] LO [È fatta di vimini] F F [Decimi di chilo] S [Disusato soprabito] A [Un rampicante dei Tropici]

Chiave di lettura: 3 6 12 8 Generation Procediamo alla risoluzione del rebus passo per passo:

Definition resolution ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ -U = U -[Lo è il passacavallo] = nave -L O = L O -[È fatta di vimini] = cesta -F F = F F -[Decimi di chilo] = etti -S = S -[Disusato soprabito] = tait -A = A -[Un rampicante dei Tropici] = liana

First pass

{︂

Prima lettura: U nave LO cesta F F etti S tait A liana

Ora componiamo la soluzione seguendo la chiave risolutiva:

Solution segmen- tation ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 3 = Una 6 = veloce 12 = staffettista 8 = italiana Solution {︀ Soluzione: Una veloce staffettista italiana

Results

Table 2 presents our evaluation results. We observe that all prompted models perform poorly on the task, with the overall best prompted system (Claude 3.5 Sonnet) obtaining the correct solution only for 24% of the 2k tested examples. Notably, open-source systems perform significantly worse than proprietary ones, producing correct first passes only for 4% of the examples, and next to no correct solutions. Our fine-tuned system largely outperforms all state-of-the-art prompted models, predicting the correct solution in 51% of cases. From first pass metrics, it is evident these results can be largely explained by the poor word-guessing capabilities of the models, which are greatly improved with fine-tuning. For prompted models, the slight decrease in scores between Def. and FP Words also highlights issues with copying predicted words in the expected format. Finally, we observe that fine-tuning strongly improves the constraint-following abilities of our system, with prompted systems being less strict with applying length and letter-choice constraints for their solutions (Key/FP Match).

What Motivates Model Performances?

In light of the strong performances achieved by our relatively small fine-tuned system, this section conducts an in-depth investigation to identify factors motivating such performance improvements. 2) the word frequency in Paisà [38], a large web Italian corpus; and 3) the length of the word (number of characters). We find a significant positive correlation (𝜌 = 0.44) between first pass word prediction accuracy and training frequency for the fine-tuned Phi-3 model, suggesting that model performance is strongly related to training coverage. The length of characters is also found to negatively affect our model's performance, albeit to a smaller extent (𝜌 = −0.11). The performance of prompted models is unrelated to both properties for first pass words, indicating that these results are the product of fine-tuning. 12 LLM Fine-Tuning Fails to Generalize to Unseen Words To further confirm the importance of finetuning word coverage in defining model performances, 12 Paisà frequency is never found to correlate significantly. Full correlation results are available in Table 6.

Model

we 3 confirm that this is indeed the case. We find Phi-3 performances to be near-perfect on seen first pass words (FP W. ID = 0.96) in both test sets, with a major drop for OOD words (FP W. OOD = 0.20). This produces second-order effects on subsequent steps, causing the FP EM results to drop by 71% (FP EM Test ∆), while significantly impacting downstream solution accuracies. On the contrary, GPT-4o few-shot prompting performances remain nearly identical on both splits, confirming that these results are not the product of a skewed data selection process. Overall, these results strongly suggest that memorization is the main factor behind the strong rebus-solving performance of our fine-tuned LLM.

Manual Inspection

We conclude by manually evaluating some generations produced by the best-performing LLMs. Table 4 presents two examples with definitions (D) and solution (S) words predicted by three LLMs, with more examples provided in Appendix C. We use naw as short-hand for "Not A Word" to mark nonsensical terms.

In the first example, Phi-3 correctly predicts all first pass and solution words. On the contrary, other models make several mistakes in the first pass, leading to incorrect solutions. Both prompted models tend to ignore first pass words when these cannot be assembled to form sensical, length-fitting solution words. For example, for D1 GPT-4o predicts p (naw), which would lead to the solution word "SAPpTE" (naw), but the S8 = "Spettacolo" (show) is predicted instead by the model). In particular, GPT-4o appears to prioritize grammatically correct solutions at the cost of ignoring first pass words and solution key length constraints, while Claude 3.5S

Rebus: SAP [La porta della breccia] D1 TE [La pinza del granchio] D2 SBA [Si legge su alcuni orologi] D3 G [Le sue coccole sono aromatiche] D4 V [Un gioco con dadi e pedine] D5 D [Sono verdi in gioventù] D6

Chiave di lettura: 8 3 2 12 7 5

Step shows an improved ability to follow these constraints, as confirmed by Key/FP Match results of Table 2.

In the second example, the first pass word D2 = salice (willow) is OOD for Phi-3. Consequently, the model produces the incorrect prediction aro (naw), and the error is propagated to all solution words, as previously observed in the Test OOD column of Table 3. Prompted models also underperform in this example, with errors on D1 and D2 propagating to most solution words. However, we note that D1 and D2 incorrect predictions for Claude 3.5S satisfy the provided definitions, suggesting that access to more explicit information about the given constraints could further boost LLMs' performance on this task.

Discussion and Conclusion

This work introduced a verbalized rebus-solving task and dataset for evaluating LLMs' sequential instruction following skills for the Italian language. We crafted a large collection of 83k verbalized rebuses by combining rebus transcriptions with crossword definitions and used it to evaluate the rebus-solving skills of state-of-the-art LLMs. Our experiments revealed the challenging nature of this task, with even the most capable prompted models achieving only 24% accuracy on solutions.

While fine-tuning a smaller LLM dramatically improved performance to 51% solution accuracy, our analysis uncovered that these gains were largely driven by memorization and do not generalize to out-ofdistribution examples. These results suggest important limitations in the generalization capabilities of current systems for sequential instruction following tasks. Our manual analysis further shows that LLMs seldom account for length constraints when solving definitions, despite the fundamental role of these cues in restricting the pool of possible words. These results suggest that searchbased approaches accounting for constraints more explicitly might improve puzzle structure adherence, as previously shown by Chen et al. [39]. Other augmentation techniques employing LLM reformulation skills can also be explored to mitigate overfitting.

Future work in this area should focus on expanding similar evaluations to a wider set of languages, input modalities, and puzzle categories, creating a comprehensive benchmark to test LLMs' puzzle-solving skills. Importantly, the task of solving visual rebuses and their more convoluted variants 13 remains far beyond the current capabilities of vision-language models. Hence, solving these puzzles automatically can be considered an important milestone in developing multimodal AI systems for constrained multi-step reasoning tasks. Our results confirm that the challenging nature of rebuses, even in their verbalized form, makes this task valuable for assessing future progress in LLMs' linguistic proficiency and sequential reasoning abilities. Finally, our rebus-solving LLM can facilitate future interpretability work investigating the mechanisms behind factual recall and multi-step reasoning in transformer models [40].

Limitations Our analysis was limited to a relatively small set of models, and a single prompt template obtained after minimal tuning. Further experiments are needed to verify that memorization patterns after finetuning remain relevant for other model sizes, prompt formats, and training regimes, particularly for full-weight training approaches. [41] the pool of available definitions for every word.

A. Additional Data Information

Dataset statistics

First pass/Solution word distribution Figure 2 shows the distribution of first pass and solution words for the filtered EurekaRebus subset used in our work.

B. Additional Experimental Results

Table 6 presents the correlations between model accuracy and the properties presented in Section 5. Table 7 presents the full ID/OOD performances for all tested models, showing consistent results with Table 3 for all prompted models. Table 8 presents Phi-3 Mini performances across rebus-solving fine-tuning steps.