summaries: Authors 1) provide a dataset of cryptic crosswords; 2) explore baselines performances on this dataset; 3) provide interesting insights on those performances and come up with a pretraining strategy that increases performances.  Briefly, cryptic crosswords are puzzles that require both mastering definitions and wordplay (i.e. reordering of letters, extracting letters, composing parts of several words to form a novel word, etc.) to be solved. Authors provide a large dataset of such puzzles (in english), that they introduce as a stepping stone to solve more complex real-life settings.  They show that carefully crafted non-neural baselines are not very good (either rule-based following previous work on this, or KNN) and that even T5 (state of the art text-to-text transformer pretrained on many tasks, such as translation, summarization, etc.) cannot be finetuned for optimal performances on this dataset. Worst, when considering adversarial splits, such that for instance all puzzles with answers starting with the same subword are found in the same split, T5 performances drop dramatically.  They hint at a solution for this problem via curriculum learning, and devise the following strategy: first pretrain T5 on a series of tasks resembling the final wordplays (e.g. unscrambling a word using its definition: "etalp + flower part" --> "petal") and only then finetune T5 on the actual cryptic crosswords dataset. T5 performances indeed increase, but authors note that they are far from human performances, or even acceptable performances for a machine.

summaries: This paper presents a new dataset of cryptic crossword clues. The work presents an extensive evaluation study on this dataset with 3 non-neural baselines and one neural baseline, namely the T5 transformer-based model. The authors investigate as well a kind of pre-finetuning stage (a phase of finetuning before the final finetuning stage on the main dataset) as a way to improve the performance of the model on this task.  Contributions: New dataset of cryptic crossword clues that has the potential to foster more research on complex reasoning tasks  Strengths: - The writing is compelling and the paper is a very enjoyable read - The author do a detailed analysis to understand better the limitations and abilities of transformer-based models on the task, including interesting ways of looking at data splits - The authors investigate the use of a pre-finetuning stage as a way to improve the performance of the T5 model on the task - The evaluation is convincing with multiple baselines, non-neural and neural.  Weaknesses: Sometimes, the paper seemed to be a bit condensed

summaries: **What is the task?**  Cryptic crossword puzzles task  **What are the contributions of the paper?**  * Presented a dataset of cryptic crossword clues as a challenging new benchmark for NLP systems that seek to process compositional language in more creative, human-like ways.  * A novel curriculum approach, in which the model is first fine-tuned with related, synthetic tasks (e.g., an augmented word descrambling task) before tackling actual cryptic clues.  * Introduced a challenging word-initial disjoint data split to test composition and generalization and investigated model behavior by systematically perturbing the wordplay part of clues, showing that the model exhibits behavior partially consistent with human solving strategies.

summaries: This paper describes a new corpus of cryptic crossword clues as a challenging NLP task.  Cryptic crossword clues are composed of a literal (synonym) clue and wordplay.  Cryptic wordplay has a conventionalized inventory of ways to clue an answer.  This is a compelling NLP challenge ``1) because it is hard and 2) because it requires a system to process both surface, syntactic and semantic content of the examples.  This is related to being able to understand statements like "Al and Bob got married and bought a house together, but not in that order".  The paper includes a curriculum training approach where a T5 model is presented with data to improve cryptic clue solving.

summaries: The paper focuses on data and methods for studying compositional language through UK-style cryptic crossword puzzles. These puzzles contain a definition and a wordplay cipher which together read like fluent natural language. The output is a word or phrase related to the wordplay cipher for which the definition is a valid description. Expert humans typically use creativity and linguistic and world knowledge to solve this task. The paper makes two main contributions: (1) a new dataset of cryptic clues as a new benchmark for NLP systems that process compositional language, and (2) baselines and an improved curriculum learning approach in which the model is first fine-tuned on related tasks (e.g., unscrambling words). Their experiments suggest that there is significant room for improvement for future work on this new benchmark.

abstractText: Cryptic crosswords, the dominant crossword variety in the UK, are a promising target for advancing NLP systems that seek to process semantically complex, highly compositional language. Cryptic clues read like fluent natural language but are adversarially composed of two parts: a definition and a wordplay cipher requiring character-level manipulations. Expert humans use creative intelligence to solve cryptics, flexibly combining linguistic, world, and domain knowledge. In this paper, we make two main contributions. First, we present a dataset of cryptic clues as a challenging new benchmark for NLP systems that seek to process compositional language in more creative, human-like ways. After showing that three non-neural approaches and T5, a state-of-the-art neural language model, do not achieve good performance, we make our second main contribution: a novel curriculum approach, in which the model is first fine-tuned on related tasks such as unscrambling words. We also introduce a challenging data split, examine the meta-linguistic capabilities of subword-tokenized models, and investigate model systematicity by perturbing the wordplay part of clues, showing that T5 exhibits behavior partially consistent with human solving strategies. Although our curricular approach considerably improves on the T5 baseline, our best-performing model still fails to generalize to the extent that humans can. Thus, cryptic crosswords remain an unsolved challenge for NLP systems and a potential source of future innovation.

authors:
Armen Aghajanyan
Anchit Gupta
Akshat Shrivastava
Xilun Chen
Luke Zettlemoyer
Sonal Gupta

title: Muppet: Massive multi-task representations with pre-finetuning

venue: arXiv preprint arXiv:2101.11038,

authors:
Emily M Bender
Alexander Koller

title: Climbing towards NLU: On meaning, form, and understanding in the age of data

venue: In Proc. of ACL,

authors:
Yonatan Bisk
Ari Holtzman
Jesse Thomason
Jacob Andreas
Yoshua Bengio
Joyce Chai
Mirella Lapata
Angeliki Lazaridou
Jonathan May
Aleksandr Nisnevich
Nicolas Pinto
Joseph Turian

title: Experience grounds language, 2020

authors:
Tom Brown
Benjamin Mann
Nick Ryder
Melanie Subbiah
Jared D Kaplan
Prafulla Dhariwal
Arvind Neelakantan
Pranav Shyam
Girish Sastry
Amanda Askell
Sandhini Agarwal
Ariel Herbert-Voss
Gretchen Krueger
Tom Henighan
Rewon Child
Aditya Ramesh
Daniel Ziegler
Jeffrey Wu
Clemens Winter
Chris Hesse
Mark Chen
Eric Sigler
Mateusz Litwin
Scott Gray
Benjamin Chess
Jack Clark
Christopher Berner
Sam McCandlish
Alec Radford
Ilya Sutskever
Dario Amodei

title: Language models are few-shot learners

venue: Advances in Neural Information Processing Systems,

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova. Bert

title: Pre-training of deep bidirectional transformers for language understanding

venue: arXiv preprint arXiv:1810.04805,

authors:
Avia Efrat
Uri Shaham
Dan Kilman
Omer Levy

title: Cryptonite: A cryptic crossword benchmark for extreme ambiguity in language, 2021

title: WordNet: An electronic lexical database

title: Catastrophic forgetting in connectionist networks

venue: Trends in Cognitive Sciences,

authors:
Kathryn J Friedlander
Philip A Fine

title: The penny drops: Investigating insight through the medium of cryptic crosswords

venue: Frontiers in psychology,

title: Fluid intelligence is key to successful cryptic crossword solving

venue: Journal of Expertise,

authors:
Mor Geva
Ankit Gupta
Jonathan Berant

title: Injecting numerical reasoning skills into language models

venue: In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 946–958,

title: Dr. fill: Crosswords and an implemented solver for singly weighted csps

venue: Journal of Artificial Intelligence Research,

title: Using the bnc to produce dialectic cryptic crossword clues

venue: In Corpus Linguistics

title: Riddle posed by computer (6): the computer generation of cryptic crossword clues

venue: PhD thesis, Citeseer,

authors:
M Hart
Robert H Davis

title: Cryptic crossword clue interpreter

venue: Information and Software Technology,

authors:
He He
Nanyun Peng
Percy Liang

title: Pun generation with surprise

venue: arXiv preprint arXiv:1904.06828,

authors:
Itay Itzhak
Omer Levy

title: Models in a spelling bee: Language models implicitly learn the character composition of tokens

venue: arXiv preprint arXiv:2108.11193,

authors:
Justine T Kao
Roger Levy
Noah D Goodman

title: The funny thing about incongruity: A computational model of humor in puns

venue: In Proceedings of the Annual Meeting of the Cognitive Science Society,

authors:
Taku Kudo
John Richardson

title: Sentencepiece: A simple and language independent subword tokenizer and detokenizer for neural text processing

venue: arXiv preprint arXiv:1808.06226,

authors:
Brenden M Lake
Tomer D Ullman
Joshua B Tenenbaum
Samuel J Gershman

title: Building machines that learn and think like people

venue: Behavioral and brain sciences,

authors:
Michael L Littman
Greg A Keim
Noam Shazeer

title: A probabilistic approach to solving crossword puzzles

venue: Artificial Intelligence,

authors:
Fuli Luo
Shunyao Li
Pengcheng Yang
Baobao Chang
Zhifang Sui
Xu Sun

title: Pun-gan: Generative adversarial network for pun generation

authors:
Christopher D Manning
Kevin Clark
John Hewitt
Urvashi Khandelwal
Omer Levy

title: Emergent linguistic structure in artificial neural networks trained by self-supervision

venue: Proceedings of the National Academy of Sciences,

title: The next decade in AI: Four steps towards robust artificial intelligence

venue: arXiv preprint arXiv:2002.06177,

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Andrei A Rusu
Joel Veness
Marc G Bellemare
Alex Graves
Martin Riedmiller
Andreas K Fidjeland
Georg Ostrovski

title: Human-level control through deep reinforcement learning

authors:
F. Pedregosa
G. Varoquaux
A. Gramfort
V. Michel
B. Thirion
O. Grisel
M. Blondel
P. Prettenhofer
R. Weiss
V. Dubourg
J. Vanderplas
A. Passos
D. Cournapeau
M. Brucher
M. Perrot
E. Duchesnay

title: Scikit-learn: Machine learning in Python

venue: Journal of Machine Learning Research,

authors:
Alec Radford
Jeffrey Wu
Rewon Child
David Luan
Dario Amodei
Ilya Sutskever

title: Language models are unsupervised multitask learners

venue: OpenAI Blog,

authors:
Colin Raffel
Noam Shazeer
Adam Roberts
Katherine Lee
Sharan Narang
Michael Matena
Yanqi Zhou
Wei Li
Peter J. Liu

title: Exploring the limits of transfer learning with a unified text-to-text transformer

authors:
Anna Rogers
Olga Kovaleva
Anna Rumshisky

title: A primer in bertology: What we know about how bert works

venue: arXiv preprint arXiv:2002.12327,

authors:
Noam Shazeer
Mitchell Stern

title: Adafactor: Adaptive learning rates with sublinear memory cost

venue: In International Conference on Machine Learning,

authors:
Noam M Shazeer
Michael L Littman
Greg A Keim

title: Solving crossword puzzles as probabilistic constraint satisfaction

venue: In AAAI/IAAI,

authors:
David Silver
Aja Huang
Chris J Maddison
Arthur Guez
Laurent Sifre
George Van Den Driessche
Julian Schrittwieser
Ioannis Antonoglou
Veda Panneershelvam
Marc Lanctot

title: Mastering the game of go with deep neural networks and tree

venue: search. Nature,

authors:
David Silver
Thomas Hubert
Julian Schrittwieser
Ioannis Antonoglou
Matthew Lai
Arthur Guez
Marc Lanctot
Laurent Sifre
Dharshan Kumaran
Thore Graepel

title: A general reinforcement learning algorithm that masters chess, shogi, and go through self-play

authors:
Oyvind Tafjord
Matt Gardner
Kevin Lin
Peter Clark

title: QuaRTz: An open-domain dataset of qualitative relationship questions

venue: In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP),

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Łukasz Kaiser
Illia Polosukhin

title: Attention is all you need

venue: Advances in Neural Information Processing Systems

authors:
Thomas Wolf
Lysandre Debut
Victor Sanh
Julien Chaumond
Clement Delangue
Anthony Moi
Pierric Cistac
Tim Rault
Rémi Louf
Morgan Funtowicz
Joe Davison
Sam Shleifer
Patrick von Platen
Clara Ma
Yacine Jernite
Julien Plu
Canwen Xu
Teven Le Scao
Sylvain Gugger
Mariama Drame
Quentin Lhoest
Alexander M. Rush

title: Transformers: State-of-theart natural language processing

venue: In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations,

authors:
Yuhuai Wu
Markus Rabe
Wenda Li
Jimmy Ba
Roger Grosse
Christian Szegedy

title: Lime: Learning inductive bias for primitives of mathematical reasoning

venue: arXiv preprint arXiv:2101.06223,

heading: 1 Introduction

text:
Modern computational models have made great progress at handling a variety of natural language tasks that require interpreting rich syntactic and semantic structures [6; 30; 25; 32]. However, in NLP [2; 26; 3] as in other areas of AI [22], machines still lag humans on tasks that require flexible problem solving, rapid learning of unseen tasks, and generalization to new domains. Just as complex games mastered by human experts, such as chess, Go, and video games, have proved a fertile ground for developing more flexible AI [36; 35; 27], we propose that creative language games are a rich area for developing more flexible NLP models. In particular, we argue that linguistic tasks involving metalinguistic reasoning pose an important and significant challenge for state-of-the-art computational language systems.
One such domain is cryptic crossword puzzles. Cryptics are the most popular style of crossword in the United Kingdom and appear in major newspapers like The Times and The Guardian. Cryptic clues have two parts: a definition and a wordplay cipher that, when placed adjacent to each other, read like fluent natural language. For example, consider this NLP-centric cryptic crossword clue: “But everything’s really trivial, initially, for a transformer model (4)” with answer “BERT”. “(4)” is the enumeration and specifies the number of letters in the answer. Solvers must identify which
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
part of the clue is definition and which is wordplay. The definition should be a semantically valid description of the answer word: “a transformer model” can mean “BERT”. The wordplay part is the remainder of the clue: “But everything’s really trivial, initially”. The word initially in this context is used as an indicator, which tells the solver to take the initial letter of each of the preceding words (but everything’s really trivial) to produce “BERT”. Because both the wordplay and the definition give the same 4-letter word (which is what the enumeration, “(4)”, calls for), we can be confident that “BERT” is the correct answer.
The clue just discussed is an example of the initialism clue type, which is one of roughly 15 major clue types. Other types can require anagramming words, finding words hidden in longer phrases, performing synonym substitutions, substituting a word for a soundalike (e.g., “hiring” for “high ring”), or composing a number of these manipulations. See Table 1 for examples of several other clue types with answer “BERT” and Appendix A for examples of actual clues from the dataset. As with American-style clues, cryptics require world knowledge and linguistic flexibility to match the definition, but also considerable attention to meta-linguistic concepts to solve the wordplay. In this paper we study the language task of solving individual cryptic clues, rather than full puzzles since, unlike American-style crosswords, cryptics generally have unique answers and so are less reliant on grid constraints in order to achieve a complete solution.
While cryptics pose a challenge to novice solvers unfamiliar with their structure, experts flexibly combine world, domain-specific, and linguistic knowledge to solve novel clues. Experts know the rules that govern cryptic clues, but they also reason about them flexibly and apply them to solve novel clues. In the psychology literature, it has been claimed that cryptics depend on domain-general intelligence and are an ideal domain for studying the “aha moment” in humans [11; 10] because experts can solve them with high accuracy (but rarely at first glance), they can be easily generated, and they require drawing on a diverse range of cognitive abilities. Therefore, we believe that cryptic crosswords are an excellent domain for developing computational language systems that “learn and think like humans” [22], posing an interesting and important challenge for modern machine learning.
Our main contributions are, first, a cleaned dataset of cryptic crosswords clues from theguardian.com, consisting of 142,380 clues from 5,518 puzzles over 21 years;1 and second, a novel curriculum learning approach, in which the model is first fine-tuned on related, synthetic tasks (e.g., an augmented word descrambling task) before tackling actual cryptic clues. This method meaningfully improves on a standard T5 seq-to-seq approach and on the best model of Efrat et al. [7]—concurrent work that presents a similar dataset and similar neural baseline using T5.
In this paper, we aim not only to present a dataset and propose a novel solution but also to characterize the problem and motivate its importance. To that end, we elucidate the task with three non-neural baselines and fine-tune T5 [31], a Transformer-based [38] encoder-decoder, as a neural baseline. Since the character-level wordplay inherent to cryptics might be challenging to language models with subword tokenization (T5 uses SentencePiece [21]), we study whether T5 has or can acquire metalinguistic knowledge. In Section 6.1 we examine whether T5 learns meta-features of the task related to answer length. In Section 6.3 we use a descrambling task to assess whether T5 understands the character composition of words and whether the model can make use of linguistic and meta-linguistic information simultaneously. Our results show, perhaps surprisingly, that the subword-tokenized T5 model is quite robust to character-level challenges. Moreover, the descrambling task may serve as a useful benchmark task in guiding the development of new approaches on the cryptics task.
Given the compositional nature of cryptic clues, we investigate the extent to which the model generalizes under increasingly difficult data splits. In Section 6.2 we introduce a new form of disjoint data split to address T5’s robustness to inflection: a word-initial disjoint split that segments clue– answer pairs based on the first two letters of the answer. In Section 6.4 we examine the systematicity of the model’s answer generation by perturbing the wordplay portion of anagram clues, showing that its behavior is partially consistent with human solving strategies.
Although our novel curricular approach considerably improves performance on this task, fully solving cryptics remains a challenge for modern machine learning, with expert humans still outperforming machines. Therefore, we hope that our dataset will serve as a challenging benchmark for future work.

heading: 2 Related work

text:
While there is an existing literature on puns and wordplay in NLP [17; 20; 24] as well as on solving American-style crosswords [13; 23; 34], there has been relatively little work using NLP methods on cryptics, which require processing highly compositional language and disambiguating surface-level from hidden meaning. Hart and Davis [16] laid out a computational framework for solving the problem, and Hardcastle [14, 15] proposed some rule-based solutions. The app Crossword Genius from Unlikely AI solves cryptic clues and gives human-understandable explanations. Because its method is proprietary and not available for open testing, we do not report it as a baseline but note that it is competitive. Deits [5] offers a rule-based solution, which can also output explanations, and which we test on our dataset. Most recently, in work concurrent to ours, Efrat et al. [7] release a similar dataset of cryptic crossword clues and present a neural baseline using T5-large. In Section 6.5, we discuss how our new data split and curricular approach improve on their work.
Our curricular approach fits into the space of recent work on pre-finetuning [37; 1] and curricular approaches for compositional tasks [12; 40]. Our approach is loosely related to the pre-finetuning of Aghajanyan et al. [1] but differs in that our curriculum is composed of fewer tasks that are all closely related to the primary task and synthetically generated. Our approach resembles Geva et al. [12] in that we attempt to endow language models with a specific kind of reasoning by training in a multi-task setup over synthetic data. In the vein of Wu et al. [40], which trains on synthetic datasets to encode inductive bias, our approach can be understood as encoding wordplay functional biases.
Whether large pretrained Transformer models generally pick up on meta-linguistic features like word length and the character composition of words is an open question. Brown et al. [4] explore a set of restricted word unscrambling tasks in the few-shot (versus fine-tuned) setting for GPT-3. Probing results from Itzhak and Levy [18] suggest that information about the character composition of words is present in the embeddings of pretrained, subword-tokenized models. This seems to
1We release the dataset along with all code to reproduce the results in this paper at https://github.com/ jsrozner/decrypt.
confirm our result that subword-tokenized models do have more knowledge of character composition and meta-properties of words than we might have expected.

heading: 3 Dataset and task

text: We present a cleaned dataset of 142,380 cryptic crossword clues from 5,518 puzzles published in The Guardian from July 1999 to October 2020. We also introduce a challenging “word-initial” disjoint split after observing that T5 is robust to inflection. Overall, the dataset has 55,783 unique answers, giving a mean frequency of 2.55 clues per unique answer. Answers in the dataset consist of one to six words, with most (97.4%) having one (83.3%) or two (14.1%) words. Full details of dataset preprocessing are given in Appendix B, and in addition to releasing the full dataset, we include code to fully replicate our data download, pre-processing pipeline, and split generation in the repository.

heading: 3.1 Task

text: We frame the problem as a standard seq-to-seq task from inputs (clues with length enumeration) to outputs (answers). For example, one input could be But everything’s really trivial, initially, for a transformer model (4), with output BERT. This is consistent with how clues are presented to human solvers. Full details of the input–output specification for each model are provided in Appendix C, along with other experimental details.

heading: 3.2 Splits

text: As motivated in the introduction (and in Section 6.2), we consider three splits. The naive (random) split is a standard 60/20/20 random split into train, dev, and test. The disjoint split ensures that all clues with the same answer appear in only one of train, dev, or test. For example, if any clue for which the answer is “BERT” is in the train set, then all clues for which the answer is “BERT” are in the train set. The disjoint split is used to test composition and generalization. It prevents an approach that relies only on lexical similarity across clues (like KNN) from succeeding on the task. Finally, the word-initial disjoint split is designed to address T5’s robustness to inflection. For this split, we enforce that all clues whose answers start with the same two letters will appear in the same set. For example, all clues that have answers starting with ‘ab’ like “abacus,” “abdicate,” “abdicates,” will be grouped, ensuring that inflections or spelling variations of the same base word occur in a single split.

heading: 3.3 Metrics

text: Our primary metric is whether the top-ranked output is correct, after filtering to outputs of the correct length. We filter because each clue in a puzzle has a hard length constraint, i.e., a human solver cannot pencil in a solution that is of the wrong length. Additionally, we report how often the correct answer is contained in the top 10 outputs after length filtering. This is a useful metric since, when clues are presented in the context of a full puzzle, solvers use information from interlocking answers to narrow down a set of candidates. For instance, the best-performing crossword solver for American-style (non-cryptic) crosswords relies heavily on satisfying grid constraints [13]. Comparing post-length-filter results from Section 4.5 with pre-filter results from Section 6.1, the length filter is seen to increase the top-10 metric by roughly 6% for T5 (with length enumeration given).

heading: 4 Baseline models and results

text: To characterize how simpler approaches perform on this task, we test three non-neural baselines: a WordNet-based heuristic model, a k-nearest-neighbor bag of words model (KNN BoW), and a rule-based model designed for the task [5]. For a neural baseline, we fine-tune T5-base [31]. For models that can interpret the answer-length enumeration as a textual token (KNN and T5), we append it to the input string (e.g., “(4)”). For these two models, we report results both with and without appending the enumeration. Implementation details are discussed in Appendix C.

heading: 4.1 WordNet

text: Our first baseline is a simple heuristic based on clue structure. It takes advantage of the fact that the definition part of a cryptic clue always appears at the beginning or end of the clue. For instance, in the double definition clue for “BERT” in Table 1, “Model Sesame Street character,” the word “model” appears at the beginning and is a definition (in this case, a hypernym) for the answer “BERT”. We use WordNet [8], a large database of English word meanings, to build a reverse dictionary via the synonym, hyponym, and hypernym graphs. We take as candidate solutions the set of reverse dictionary outputs for the first and last words of a clue. For example, if “dog” appears at the start of a clue, candidates would include “animal”, “canine”, “labrador”, etc. Ranking outputs by characterlevel overlap with the rest of the clue slightly improves performance, since answers sometimes are rearrangements of the characters in the wordplay portion of the clue.

heading: 4.2 KNN BoW

text: To assess whether clues that are close in lexical space have similar answers, we use a KNN model on top of a bag-of-words featurizer.

heading: 4.3 Rule-based

text: Finally, to evaluate how well a rule-based approach, with a hand-coded grammar, can perform on the task, we use the Deits [5] solver.2 This solver handles anagrams, initialisms, substrings, insertions, and reversals in a rule-based way. While the rule-based version includes common clue types, an inherent limitation of this approach is that it is difficult to enumerate all possibilities. For instance, the Deits solver does not include charade-type clues, nor double definitions. Moreover, the rule-based solver uses WordNet’s [8] word similarity functionality to rank outputs, meaning that, in general, it will fail on clues that have definitional parts consisting of more than one word (e.g. “language model” from our example in the introduction would not be matched).

heading: 4.4 T5: vanilla seq2seq

text: For our baseline neural seq-to-seq approach, we fine-tune the Transformer-based [38] T5-base model [31], starting from HuggingFace’s [39] pretrained model parameters. T5 is an encoder-decoder language model pretrained on the C4 corpus [31]. Fine-tuning is done via supervised learning (teacher-forcing) over standard seq-to-seq input-output pairs. At test time, we generate outputs using beam search. As described in Section 3.3, we filter the outputs to those of the correct length and evaluate by checking whether the top result is correct and whether the answer occurs in the top 10. See Appendix C for details, including hyperparameter selection.

heading: 4.5 Results

text: In Table 2, we report metrics for dev and test sets on both the naive (random) split and word-initial disjoint split (discussion on disjointness in Section 6.2). While the WordNet baseline achieves some success (2.6% and 10.7% top-1 and top-10 on the test set), it is inherently limited, since it cannot handle clues with multiword definitions and lacks a good ranking mechanism. KNN does better, achieving 6.1% and 11.3% with length enumeration. The rule-based solver achieves 7.3% and 14.7%, marginally outperforming the KNN baseline. Though our T5 neural baseline outperforms all non-neural baselines, achieving 16.3% and 33.9%, it leaves considerable room for improvement.

heading: 5 Curriculum learning

text:
Solving cryptic clues uses different linguistic and reasoning abilities compared to the natural language tasks on which T5 is pretrained. Thus, during fine-tuning on the cryptics task, the model must learn many sub-parts of the problem simultaneously: how to look up definitions, how to identify wordplay indicators, how to perform wordplay operations, etc. Although these elements of the task
2Deits [5] has a more recently implemented solver in Julia that was used by Efrat et al. [7]. We use the Python version, which may have small differences from the Julia version and is reportedly much slower (see Appendix C for more details).
each individually benefit from T5’s natural language pretraining, our standard T5 baseline suggests that learning to compose them all at once is challenging. We show that a curriculum of synthetic datasets can address this, substantially improving performance on the primary cryptics task. We test a number of different curricular tasks and task sets and discuss which are most effective. This curricular approach may be useful in other settings where focused linguistic capabilities are required.

heading: 5.1 Curricular datasets

text:
The logic of our curricular approach is to provide some guidance on the sub-parts of the problem space before building up to fully compositional cryptic clues. For curricular training, we create four datasets designed to improve performance and elucidate what makes a good curricular task for this problem. We process a public American crossword clue dataset [29], henceforth “ACW-data” for “American Crossword”, and generate three datasets: ACW, ACW-descramble, ACW-descramble-word. After preprocessing, ACW-data has 2.5m clue–answer pairs with 250k unique answers, giving a mean frequency of roughly ten clues per unique answer. Unlike cryptic clues, American crossword clues often involve relatively straightforward synonym or definition substitions, so the ACW dataset can be used to train definition lookup.
We also produce a separate anagram dataset from a publicly available English dictionary. Details to produce all datasets are included in Appendix D.1. In all example clues that follow, the target output is “PETAL” and we use labels (prepending a word and colon) to help the model distinguish tasks.
1. ACW: ACW-data dataset in input–output form (i.e., a seq-to-seq version of American-style crossword clues) with no augmentation. For example, phrase: flower part (5).
2. ACW-descramble: For each clue–answer pair in ACW-data, we create an input that models a cryptic clue by scrambling the answer word and prepending or appending it to the clue portion. For example, we scramble “petal” and randomly place it at the beginning (descramble: etalp flower part (5)) or end (descramble: flower part etalp (5)) of a clue.
3. ACW-descramble-word: A seq-to-seq task that is just the descrambling of answer words. When compared to ACW-descramble, this elucidates the importance of curricular and primary task similarity, in particular whether teaching a bare descrambling task is helpful to the model. Example: descramble word: etalp (5).
4. Anagrams: Using a dictionary as starting point, we synthesize an anagram dataset: we pair a word (to be anagrammed) with an anagram indicator (e.g., “mixed up”, “drunk”, “confusingly”) and ask the model to produce a valid anagram (i.e., a scrambled version of the word that is itself also a valid word). For example, anagram: confusingly plate (5) (rearrange the letters of ‘plate’ to get “PETAL”). The anagram dataset simulates the anagram type of wordplay in cryptic clues, with definition part omitted.
Table 3: Curricular results (left) and sample metrics for meta-linguistic feature analysis (right)
(a) Curricular approaches on the naive (random) split. Metric is correctness of top-output (5 beams with length filter).
Percent correct Curricular dataset full dev
set anagram subset
Baseline (no curricular) 15.7 13.7
ACW 18.3 14.4 ACW-descramble 13.1 21.4
ACW + ACW-descramble 20.2 24.0 ACW + ACW-descrambleword 17.8 18.3
ACW + anagram 17.1 19.1 ACW + ACW-descramble + anagram 20.1 27.1
(b) Sample metrics calculated over top 10 outputs without length filter, using naive split.
Model % samplecontains answer
(top-10, no filter)
% outputs with correct
length
% outputs correct
word count
dev test dev test dev test
KNN – (no lengths) 6.5 6.6 13.4 13.3 70.7 70.7 – (lengths) 10.6 10.7 85.4 85.3 89.7 89.6
T5-base – (no lengths) 19.0 18.8 16.0 16.2 74.2 74.1 – (lengths) 27.5 28.1 48.3 48.5 97.9 97.9

heading: 5.2 Methods

text: Our curricular approach is as follows: using the same methods as in Section 4.4, first, we fine-tune T5 on one or more supplementary tasks. Second, we continue fine-tuning on the primary cryptics task, periodically showing batches from the supplementary task(s), to decrease the likelihood of catastrophic forgetting [9]. Full details of our curricular training setup are in Appendix D.2.

heading: 5.3 Results

text:
In Table 3a, we report results for our curricular approach. Overall, we find that curricular training using ACW + ACW-descramble is best and report in Table 2 a primary task improvement from 16.3% to 21.8% on the random split and from 1.1% to 6.5% on the word-initial disjoint split.
We begin by testing a curriculum with only ACW, which corresponds roughly to teaching the definitional lookup. Observing that ACW improves performance over the baseline, we test ACWdescramble, which is ACW augmented with a scrambled word component (an implicit wordplay). Surprisingly ACW-descramble leads to a decline in performance relative to both ACW and to Baseline. On the other hand, combining ACW + ACW-descramble leads to our best performing approach, demonstrating that a particular curricular combination can improve over two separate tasks. We also compare ACW + ACW-descramble to ACW + ACW-descramble-word. The drop in performance suggests that inputs that are more similar to the final task are more useful than, e.g., a bare descrambling task. To isolate the effect of task choice, all curricular approaches use the same data distribution, train for the same number of curricular fine-tuning steps, and are reviewed during primary training at the same frequency.
Finally, in order to explore whether the curricular training improves performance across the board or just on the clue types directly involved (e.g., anagrams), we report performance on an algorithmicallylabeled anagram subset (“anagram subset” column in Table 3a). Adding the Anagrams subtask to the curriculum improves anagram performance but interestingly does not improve performance compared to the top curriculum, ACW + ACW-descramble.3 We see a similar gain in anagram performance (but drop in overall performance) when training with only ACW-descramble. This suggests that pretraining for a particular clue type can improve performance on that type, but perhaps at the expense of performance on other clue types.
Beyond providing guidance to T5 on the problem sub-parts, this approach also partially addresses the disjointness of train and test sets. For the word-initial disjoint split, by periodically refreshing the curricular task, we remind T5 to produce outputs that are not in the training set of the cryptic split.
3The distribution and size of the Anagrams dataset is different from the ACW datasets, so we separate curricula involving the Anagrams dataset in Table 3a.

heading: 6 Model analysis

heading: 6.1 Learning meta-linguistic properties: output length and number of words

text:
This task requires not just linguistic but also meta-linguistic reasoning. We investigate how model behavior changes when the enumeration (the specification of the length of the answer) is appended to the end of the input string as a number in parentheses. Whether large pretrained transformer models generally pick up on meta-linguistic features like word length is an open question.
To study whether the models learn length information, we report how often the top-10 candidate outputs for each clue are the correct length and have the correct number of words before applying any length filter. For both the KNN and the T5 models, we find that including the length enumeration improves overall performance, as can be seen in Table 2. (We omit the WordNet and rule-based approaches from this discussion since they have no capacity to learn the meaning of the length enumeration.)
In columns 3 and 4 of Table 3b we see that both KNN and T5 pick up on length information, generating more outputs of the correct length when the enumeration is provided. T5 is particularly proficient at producing the correct number of words in outputs. (Recall that multiword answers are indicated with an enumeration that has two numbers separated by a comma, as in “(4, 6)”, indicating an answer like “ALAN TURING”.) Given that T5 produces 97.9% of outputs with the correct number of words, it seems plausible that the model is learning a correspondence between the enumeration and the presence of a space or spaces in its output.

heading: 6.2 Disjointness

text:
Based on the performance of the KNN model on the naive data split, we see that some clues can be solved by picking up on lexical similarity to other clues. Thus, we investigate whether T5 is also picking up on similarity to previously seen clues or if it is learning something about the compositional and functional structure of the cryptic clues.
To assess how much a Transformer-based model like T5 relies on having seen similar clues for the same word, we segment performance on the random split by whether the answer was in the train set. In Table 4a, we see that performance drops from 16% on the full dev set to only 3.0% on the clue subset not seen during training, confirming our intuition that lexical similarity between clues with the same answer plays a role in model success.
To formalize this result, we create and train on the two disjoint datasets described in Section 3: the basic disjoint and the word-initial disjoint splits. The T5 model achieves 3.3% accuracy on the basic disjoint split (dev) and only 1.1% accuracy on the word-initial disjoint split. The drop is likely partially attributable to robustness to inflection, since inflected forms often start with the same two letters.

heading: 6.3 Wordplay: minimal task

text:
We investigate the extent to which T5, which uses SentencePiece tokenization [21], can perform wordplay-esque tasks like descrambling. We run an experiment as follows: we start with the ACW dataset from Section 5, further restrict to outputs with targets in a dictionary (i.e., no multiword answers), and downsample to 180k clues (10%). We create two descrambling tasks. The first is a direct descramble task, where the input is a scrambled version of the target word (e.g., etalp for target petal). The second task is a descramble with phrase tasks, in which we append the clue of the clue-answer pair after the scrambled answer letters (e.g., input is etalp | flower part for target petal). The second task is designed to mimic the cryptic setup, where we have a wordplay (in this case, the implicit descramble function) whose output is conditioned on a (possibly phrasal) synonym. See Appendix E.1 for more details.
We present results in Table 4b. We observe that the model reasonably learns the task on a random split (63.8%) but fails on a word-initial disjoint split (3.7%). Notably, including a phrasal definition alongside the scrambled letters in the input improves outcomes, suggesting that the model is simultaneously incorporating both meta-linguistic character-level and overall word-embedding information. This task can serve as a benchmark for models to solve the cryptic task, since it roughly upper-bounds how well a model can solve wordplays.
Table 4: Disjointness results (left) and descrambling results (right)
(a) T5-base performance (% for top-10 outputs after length filter) on naive, subset of naive not seen in train, disjoint, and word-initial disjoint splits.
Dataset Top Top 10
correct contains dev test dev test
Naive (random) split – Entire split 16.0 16.3 33.1 33.9 – Subset not in train 3.0 2.8 9.5 9.7
Disjoint splits: – Naive disjoint 3.3 3.2 12.6 12.9 – Word-initial disjoint 1.1 1.1 5.6 5.8
(b) Descrambling task, with and without phrasal definition. Metric is % for top ten outputs without length filter.
Split and task Top Top 10 correct contains
Random split – Descramble 63.8 91.6 – Descramble w/ phrase 79.4 91.2
Word-initial disjoint split – Descramble 3.7 12.5 – Descramble w/ phrase 12.4 24.4
Given that we observe a considerable drop from the random to disjoint data splits, we test whether T5 can learn the identity function under a disjoint split. We find that the model achieves 100% accuracy on a direct copy task in which the model is trained to simply output the string that is given as input. This suggests that T5’s meager performance for descrambling on the disjoint split is not due to an inability to generate an output that has not been seen in fine-tuning.

heading: 6.4 Assessing systematicity

text:
We investigate the extent to which the model’s behavior is consistent with the compositional and systematic nature of human solving strategies. Consider our anagram clue from Table 1: “Confused, Bret makes a language model (4),” for which the answer is “BERT”. Using a publicly available list of 18,000 first names, we algorithmically identify clues in the dev set that require the solver to compute an anagram of a first name, and we use those clues to compose two specialized test sets. In the first set, we scramble the original letters (e.g., Bret becomes Treb). If the model is behaving optimally, performance on this set should not suffer: what is important about Bret in this clue is not its semantics but its characters. In the second set we substitute another name of the same length (e.g., John for Bret). We pick first names because swapping a name does not change the grammaticality or linguistic validity of clues. Here, for a human solver, we would expect a major hit in performance since the correct answer is a valid anagram of Bret but not of John, and so the clue is no longer a valid cryptic clue. It does, however, still have a valid definition part (“a language model”), and so, if the model is picking up only on the definition part and ignoring the wordplay part, it might still do well. See Appendix E.2 for more task details.
On this set of clues, prior to any modification, we find a baseline accuracy of 33.3%. When scrambling the name, accuracy drops moderately, to 25.2%. When substituting a name with different letters, accuracy falls to 7.0%. This difference in performance on the substitution and scrambling tasks suggests that the model is, to some extent, correctly picking up on the need to use the letters of the name as the wordplay substrate. This is confirmed by the average character overlap between the altered word and the generated candidate answers. We observe 51.2% multiset overlap for the baseline (name unchanged from original clue), 51.0% for substitution of names with the same letters, and 31.4% when substituting names with different letters. For our example clue, this means that we would expect high character overlap between Bret and the candidate answers in the baseline set, but high overlap between John and the candidate answers in the substitution test set. These results suggest that, like human solvers, the model is sensitive to character manipulations at the location of the wordplay substrate.

heading: 6.5 Comparison to Efrat et al.

text:
In contemporaneous work, Efrat et al. [7] present a dataset of cryptics from two other major newspapers and fine-tune T5-large for the task. While Efrat et al. [7] conclude that train/test disjointness is important, they do not fully consider T5’s robustness to plural and other inflections. The word-initial disjoint split that we present addresses this. In particular, their ‘naive’ split is the same as our naive split, and their ‘official’ split is the same as our (naive) disjoint split. To demonstrate that our split is
relevant to the Efrat work, we replicate their results (we train T5-large and report the same metric, correctness of top output with b=5 beams), show a considerable decline in performance under the word-initial disjoint split (10.9% to 4.9%), and finally demonstrate that our curricular approach substantially improves results on the ‘naive-disjoint’ (10.9% to 19.9%) and word-initial disjoint splits (4.9% to 12.8%). Performance on the ‘naive’ split does not change considerably with our curricular approach. Results are in Table 5, and further training details are given in Appendix E.3.

heading: 7 Conclusion

text:
In this paper we introduce a dataset of cryptic crossword clues that can be used as a challenging new benchmark task and develop a novel curricular approach that considerably improves performance on the benchmark. We further characterize the problem with three non-neural baselines and provide methods for investigating model behavior, including a simple descrambling task and an experiment that explores what T5 learns about compositional task structure. Lastly we introduce a challenging word-initial datasplit to evaluate a model’s ability to achieve compositional generalization. These contributions demonstrate why this task is worth studying and how it may be relevant to related problems. For example, our curricular approach may be useful in other settings where focused linguistic capabilities are required.
Pretrained contextual embedding models like T5, which draw on a rich base of lexical and linguistic knowledge from pretraining, are a promising candidate for the type of flexibility needed to solve this sort of puzzle. However, T5 does not initially succeed at the task, and although our curricular approach considerably improves task performance, cryptics remain an unsolved problem. Although one might initially think that a character-level tokenization scheme would be necessary for this task, Sections 6.1 and 6.3 suggest that T5 can unscramble words (under appropriate generalization splits) and does learn a correspondence between a word’s tokens and the word’s total length.
Given the success of our curricular approach, future work might combine new synthetic datasets under a learned curriculum schedule. In any case, an approach that fully solves this problem will need to more flexibly learn different kinds of wordplay functions and how to functionally compose them to produce the answer word. In that sense, we believe that the cryptic crossword task serves as a good benchmark for those interested in building NLP systems that can apply linguistic and meta-linguistic knowledge in more creative, flexible, and human-like ways.
Acknowledgments and Disclosure of Funding
This work was supported in part by a Stanford HAI Hoffman–Yee grant.
We thank Saul Pwanson for guidance on the release of crossword-related datasets and William Tunstall-Pedoe for discussions on cryptics and for testing his proprietary solver on our dataset. We thank Armando Solar-Lezama, Josh Tenenbaum, Osbert Bastani, and other members of the Neurosym group for helpful feedback. We especially thank Dana Angluin for suggesting (in 2014!) cryptic crosswords as an undergraduate thesis topic for Joshua Rozner.

title: Decrypting Cryptic Crosswords: Semantically Complex Wordplay Puzzles as a Target for NLP


summaries: This work addresses some fundamental questions on Vision Transformers including 1. how are Vision Transformers solving vision tasks? 2. Do they act like convolutions, learning the same inductive biases from scratch? 3. And what is the role of scale in learning these representations? To answer these questions, they investigate the internal representation structure of ViTs and CNN by using representational similarity techniques like CKA (Centered Kernel Alignment).

summaries: The paper studies the representation of features learned by convnet and transformers. It evaluates the similarity of representations within and between architectures using Centered Kernel Alignment. It studies models trained on datasets of different sizes.

summaries: Neural network architectures based on self-attention instead of convolutions (e.g., the Vision Transformer, ViT), have recently be shown to reach similar or better performances on ImageNet classification than CNNs. In this work, the authors investigate whether the "internal representation structure" learned by Vision Transformers is also similar to CNNs. Using Centered Kernel Alignment as main metric to compare internal representations, the authors perform several analyses comparing aspects of three Vision Transformer variants (ViT-B/32, ViT-B/16, ViT-L/16) and two ResNet variants (ResNet50x1, ResNet152x2). The analyses performed look at similarity of representations across different depths, local vs. global information aggregation, importance of skip connections, spatial localization of information and effects of the amount of training data. The analyses reveal several differences between the ViTs and ResNets, indicating that despite similar classification performance, the image processing strategies are quite different for the two model families.

summaries: The paper presents a comparison study between internal representations of recently Vision Transformers and ResNet networks for image classification, using various established tools: Centered kernel alignment, attention distance analysis, effective receptive fields, representation propagation analysis, spatial localization analysis and linear probes. The also train some new models for additional analysis. The findings show significant difference between the models.

summaries: In this work, the authors explore how representations learned with vision transformers (ViT) compare with those of convolutional neural networks (resnet). Making use of centered kernel alignment (CKA), they compare the representations learned at different layers of the same mode, between models, and at different spatial positions. They find that ViT tends to learn similar representations  across all layers while resnets tend to show a clear distinction between lower-level and higher-level representations. They also provide experiments showing that residual connections play a crucial role in transformers, i.e. removing a residual connection causes a big change between preceding and following representations. Another interesting phenomenon in ViT is that residual connections tend to preserve information of the classification token during the first half of the model while it tends to change during the second half of the model. In addition, they compare how ViT and ResNets treat spatial information. They find that both process local information in the first layers but ViT uses global information earlier than ResNets. In fact, they show that while local processing is "hardcoded" in convolutions, ViT requires larger training sets to learn such inductive bias. Finally, they show that MLP Mixer is closer to ViT than to ResNet.

abstractText: Convolutional neural networks (CNNs) have so far been the de-facto model for visual data. Recent work has shown that (Vision) Transformer models (ViT) can achieve comparable or even superior performance on image classification tasks. This raises a central question: how are Vision Transformers solving these tasks? Are they acting like convolutional networks, or learning entirely different visual representations? Analyzing the internal representation structure of ViTs and CNNs on image classification benchmarks, we find striking differences between the two architectures, such as ViT having more uniform representations across all layers. We explore how these differences arise, finding crucial roles played by self-attention, which enables early aggregation of global information, and ViT residual connections, which strongly propagate features from lower to higher layers. We study the ramifications for spatial localization, demonstrating ViTs successfully preserve input spatial information, with noticeable effects from different classification methods. Finally, we study the effect of (pretraining) dataset scale on intermediate features and transfer learning, and conclude with a discussion on connections to new architectures such as the MLP-Mixer.

authors:
G. Alain
Y. Bengio

title: Understanding intermediate layers using linear classifier probes

venue: arXiv preprint arXiv:1610.01644,

authors:
I. Bello
B. Zoph
A. Vaswani
J. Shlens
Q.V. Le

title: Attention augmented convolutional networks

venue: In Proceedings of the IEEE/CVF International Conference on Computer Vision,

authors:
S. Bhojanapalli
A. Chakrabarti
D. Glasner
D. Li
T. Unterthiner
A. Veit

title: Understanding robustness of transformers for image classification

venue: arXiv preprint arXiv:2103.14586,

authors:
N. Carion
F. Massa
G. Synnaeve
N. Usunier
A. Kirillov
S. Zagoruyko

title: End-to-end object detection with transformers

venue: In European Conference on Computer Vision,

authors:
M. Caron
H. Touvron
I. Misra
H. Jégou
J. Mairal
P. Bojanowski
A. Joulin

title: Emerging properties in self-supervised vision transformers

venue: arXiv preprint arXiv:2104.14294,

authors:
M. Chen
A. Radford
R. Child
J. Wu
H. Jun
D. Luan
I. Sutskever

title: Generative pretraining from pixels

authors:
X. Chen
S. Xie
K. He

title: An empirical study of training self-supervised vision transformers

venue: arXiv preprint arXiv:2104.02057,

authors:
A. Conneau
G. Kruszewski
G. Lample
L. Barrault
M. Baroni

title: What you can cram into a single vector: Probing sentence embeddings for linguistic properties

venue: In ACL,

authors:
J.-B. Cordonnier
A. Loukas
M. Jaggi

title: On the relationship between self-attention and convolutional layers

venue: arXiv preprint arXiv:1911.03584,

authors:
C. Cortes
M. Mohri
A. Rostamizadeh

title: Algorithms for learning kernels based on centered alignment

venue: The Journal of Machine Learning Research,

authors:
S. d’Ascoli
H. Touvron
M. Leavitt
A. Morcos
G. Biroli
L. Sagun

title: Convit: Improving vision transformers with soft convolutional inductive biases

venue: arXiv preprint arXiv:2103.10697,

authors:
J. Deng
W. Dong
R. Socher
L.-J. Li
K. Li
L. Fei-Fei

title: Imagenet: A large-scale hierarchical image database

venue: IEEE conference on computer vision and pattern recognition,

authors:
J. Devlin
M.-W. Chang
K. Lee
K. Toutanova. Bert

title: Pre-training of deep bidirectional transformers for language understanding

venue: arXiv preprint arXiv:1810.04805,

authors:
A. Dosovitskiy
L. Beyer
A. Kolesnikov
D. Weissenborn
X. Zhai
T. Unterthiner
M. Dehghani
M. Minderer
G. Heigold
S. Gelly

title: An image is worth 16x16 words: Transformers for image recognition at scale

venue: arXiv preprint arXiv:2010.11929,

authors:
A. Gretton
K. Fukumizu
C.H. Teo
L. Song
B. Schölkopf
A.J. Smola

title: A kernel statistical test of independence

venue: In Nips,

authors:
A. Kolesnikov
L. Beyer
X. Zhai
J. Puigcerver
J. Yung
S. Gelly
N. Houlsby

title: Big transfer (bit): General visual representation learning

venue: arXiv preprint arXiv:1912.11370,

authors:
S. Kornblith
M. Norouzi
H. Lee
G. Hinton

title: Similarity of neural network representations revisited

venue: In ICML,

authors:
S. Kornblith
H. Lee
T. Chen
M. Norouzi

title: What’s in a loss function for image classification

venue: arXiv preprint arXiv:2010.16402,

authors:
N. Kriegeskorte
M. Mur
P.A. Bandettini

title: Representational similarity analysis-connecting the branches of systems neuroscience

venue: Frontiers in systems neuroscience,

authors:
A. Krizhevsky
I. Sutskever
G.E. Hinton

title: Imagenet classification with deep convolutional neural networks

venue: Advances in neural information processing systems,

authors:
S.R. Kudugunta
A. Bapna
I. Caswell
N. Arivazhagan
O. Firat

title: Investigating multilingual nmt representations at scale

title: Convolutional neural networks as a model of the visual system: past, present, and future

venue: Journal of cognitive neuroscience,

authors:
W. Luo
Y. Li
R. Urtasun
R. Zemel

title: Understanding the effective receptive field in deep convolutional neural networks

venue: arXiv preprint arXiv:1701.04128,

authors:
N. Maheswaranathan
A.H. Williams
M.D. Golub
S. Ganguli
D. Sussillo

title: Universality and individuality in neural dynamics across large populations of recurrent networks

authors:
A. Merchant
E. Rahimtoroghi
E. Pavlick
I. Tenney

title: What happens to bert embeddings during fine-tuning

venue: arXiv preprint arXiv:2004.14448,

authors:
A.S. Morcos
M. Raghu
S. Bengio

title: Insights on representational similarity in neural networks with canonical correlation

venue: arXiv preprint arXiv:1806.05759,

authors:
B. Mustafa
A. Loh
J. Freyberg
P. MacWilliams
M. Wilson
S.M. McKinney
M. Sieniek
J. Winkens
Y. Liu
P. Bui

title: Supervised transfer learning at scale for medical imaging

venue: arXiv preprint arXiv:2101.05913,

authors:
M. Naseer
K. Ranasinghe
S. Khan
M. Hayat
F.S. Khan
M.-H. Yang

title: Intriguing properties of vision transformers, 2021

authors:
T. Nguyen
M. Raghu
S. Kornblith

title: Do wide and deep networks learn the same things? uncovering how neural network representations vary with width and depth

authors:
N. Parmar
A. Vaswani
J. Uszkoreit
L. Kaiser
N. Shazeer
A. Ku
D. Tran

title: Image transformer

authors:
S. Paul
P.-Y. Chen

title: Vision transformers are robust learners

venue: arXiv preprint arXiv:2105.07581,

authors:
M.E. Peters
M. Neumann
L. Zettlemoyer
W.-t. Yih

title: Dissecting contextual word embeddings: Architecture and representation

venue: In EMNLP,

authors:
A. Raghu
M. Raghu
S. Bengio
O. Vinyals

title: Rapid learning or feature reuse? towards understanding the effectiveness of maml

authors:
M. Raghu
J. Gilmer
J. Yosinski
J. Sohl-Dickstein

title: Svcca: Singular vector canonical correlation analysis for deep learning dynamics and interpretability

venue: arXiv preprint arXiv:1706.05806,

authors:
M. Raghu
C. Zhang
J. Kleinberg
S. Bengio

title: Transfusion: Understanding transfer learning for medical imaging

venue: arXiv preprint arXiv:1902.07208,

authors:
P. Ramachandran
N. Parmar
A. Vaswani
I. Bello
A. Levskaya
J. Shlens

title: Stand-alone self-attention in vision models

authors:
O. Russakovsky
J. Deng
H. Su
J. Krause
S. Satheesh
S. Ma
Z. Huang
A. Karpathy
A. Khosla
M. Bernstein

title: Imagenet large scale visual recognition challenge

venue: International journal of computer vision,

authors:
J. Shi
E. Shea-Brown
M. Buice

title: Comparison against task driven artificial neural networks reveals functional properties in mouse visual cortex

venue: Advances in Neural Information Processing Systems,

authors:
L. Song
A. Smola
A. Gretton
J. Bedo
K. Borgwardt

title: Feature selection via dependence maximization

authors:
C. Sun
A. Shrivastava
S. Singh
A. Gupta

title: Revisiting unreasonable effectiveness of data in deep learning era

venue: In Proceedings of the IEEE international conference on computer vision,

authors:
Y. Tay
M. Dehghani
J. Gupta
D. Bahri
V. Aribandi
Z. Qin
D. Metzler

title: Are pre-trained convolutions better than pre-trained transformers

venue: arXiv preprint arXiv:2105.03322,

authors:
I. Tolstikhin
N. Houlsby
A. Kolesnikov
L. Beyer
X. Zhai
T. Unterthiner
J. Yung
D. Keysers
J. Uszkoreit
M. Lucic

title: Mlp-mixer: An all-mlp architecture for vision

venue: arXiv preprint arXiv:2105.01601,

authors:
H. Touvron
P. Bojanowski
M. Caron
M. Cord
A. El-Nouby
E. Grave
A. Joulin
G. Synnaeve
J. Verbeek
H. Jégou

title: Resmlp: Feedforward networks for image classification with dataefficient training

venue: arXiv preprint arXiv:2105.03404,

authors:
A. Vaswani
N. Shazeer
N. Parmar
J. Uszkoreit
L. Jones
A.N. Gomez
L. Kaiser
I. Polosukhin

title: Attention is all you need

venue: arXiv preprint arXiv:1706.03762,

authors:
E. Voita
R. Sennrich
I. Titov

title: The bottom-up evolution of representations in the transformer: A study with machine translation and language modeling objectives

authors:
B. Wu
C. Xu
X. Dai
A. Wan
P. Zhang
Z. Yan
M. Tomizuka
J. Gonzalez
K. Keutzer
P. Vajda

title: Visual transformers: Token-based image representation and processing for computer vision

venue: arXiv preprint arXiv:2006.03677,

authors:
J.M. Wu
Y. Belinkov
H. Sajjad
N. Durrani
F. Dalvi
J. Glass

title: Similarity analysis of contextual word representation models

venue: arXiv preprint arXiv:2005.01172,

authors:
S. Wu
A. Conneau
H. Li
L. Zettlemoyer
V. Stoyanov

title: Emerging cross-lingual structure in pretrained language models

authors:
L. Yuan
Y. Chen
T. Wang
W. Yu
Y. Shi
Z. Jiang
F.E. Tay
J. Feng
S. Yan

title: Tokens-to-token vit: Training vision transformers from scratch on imagenet

heading: 1 Introduction

text:
Over the past several years, the successes of deep learning on visual tasks has critically relied on convolutional neural networks [20, 16]. This is largely due to the powerful inductive bias of spatial equivariance encoded by convolutional layers, which have been key to learning general purpose visual representations for easy transfer and strong performance. Remarkably however, recent work has demonstrated that Transformer neural networks are capable of equal or superior performance on image classification tasks at large scale [14]. These Vision Transformers (ViT) operate almost identically to Transformers used in language [13], using self-attention, rather than convolution, to aggregate information across locations. This is in contrast with a large body of prior work, which has focused on more explicitly incorporating image-specific inductive biases [30, 9, 4]
This breakthrough highlights a fundamental question: how are Vision Transformers solving these image based tasks? Do they act like convolutions, learning the same inductive biases from scratch? Or are they developing novel task representations? What is the role of scale in learning these representations? And are there ramifications for downstream tasks? In this paper, we study these questions, uncovering key representational differences between ViTs and CNNs, the ways in which these difference arise, and effects on classification and transfer learning. Specifically, our contributions are:
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
• We investigate the internal representation structure of ViTs and CNNs, finding striking differences between the two models, such as ViT having more uniform representations, with greater similarity between lower and higher layers.
• Analyzing how local/global spatial information is utilised, we find ViT incorporates more global information than ResNet at lower layers, leading to quantitatively different features.
• Nevertheless, we find that incorporating local information at lower layers remains vital, with large-scale pre-training data helping early attention layers learn to do this
• We study the uniform internal structure of ViT, finding that skip connections in ViT are even more influential than in ResNets, having strong effects on performance and representation similarity.
• Motivated by potential future uses in object detection, we examine how well input spatial information is preserved, finding connections between spatial localization and methods of classification.
• We study the effects of dataset scale on transfer learning, with a linear probes study revealing its importance for high quality intermediate representations.

heading: 2 Related Work

text:
Developing non-convolutional neural networks to tackle computer vision tasks, particularly Transformer neural networks [44] has been an active area of research. Prior works have looked at local multiheaded self-attention, drawing from the structure of convolutional receptive fields [30, 36], directly combining CNNs with self-attention [4, 2, 46] or applying Transformers to smaller-size images [6, 9]. In comparison to these, the Vision Transformer [14] performs even less modification to the Transformer architecture, making it especially interesting to compare to CNNs. Since its development, there has also been very recent work analyzing aspects of ViT, particularly robustness [3, 31, 28] and effects of self-supervision [5, 7]. Other recent related work has looked at designing hybrid ViT-CNN models [49, 11], drawing on structural differences between the models. Comparison between Transformers and CNNs are also recently studied in the text domain [41].
Our work focuses on the representational structure of ViTs. To study ViT representations, we draw on techniques from neural network representation similarity, which allow the quantitative comparisons of representations within and across neural networks [17, 34, 26, 19]. These techniques have been very successful in providing insights on properties of different vision architectures [29, 22, 18], representation structure in language models [48, 25, 47, 21], dynamics of training methods [33, 24] and domain specific model behavior [27, 35, 38]. We also apply linear probes in our study, which has been shown to be useful to analyze the learned representations in both vision [1] and text [8, 32, 45] models.

heading: 3 Background and Experimental Setup

text:
Our goal is to understand whether there are differences in the way ViTs represent and solve image tasks compared to CNNs. Based on the results of Dosovitskiy et al. [14], we take a representative set of CNN and ViT models — ResNet50x1, ResNet152x2, ViT-B/32, ViT-B/16, ViT-L/16 and ViT-H/14. Unless otherwise specified, models are trained on the JFT-300M dataset [40], although we also investigate models trained on the ImageNet ILSVRC 2012 dataset [12, 37] and standard transfer learning benchmarks [50, 14]. We use a variety of analysis methods to study the layer representations of these models, gaining many insights into how these models function. We provide further details of the experimental setting in Appendix A.
Representation Similarity and CKA (Centered Kernel Alignment): Analyzing (hidden) layer representations of neural networks is challenging because their features are distributed across a large number of neurons. This distributed aspect also makes it difficult to meaningfully compare representations across neural networks. Centered kernel alignment (CKA) [17, 10] addresses these challenges, enabling quantitative comparisons of representations within and across networks. Specifically, CKA takes as input X ∈ Rm×p1 and Y ∈ Rm×p2 which are representations (activation matrices), of two layers, with p1 and p2 neurons respectively, evaluated on the same m examples. Letting K = XXT and L = Y Y T denote the Gram matrices for the two layers (which measures the similarity of a pair of datapoints according to layer representations) CKA computes:
CKA(K,L) = HSIC(K,L)√
HSIC(K,K)HSIC(L,L) , (1)
0 20 40 60 80 100 120 140 Layers ViT-L/16
0
20
40
60
80
100
120
140
La ye
rs V
iT -L
/1 6
ViT-L/16
0 25 50 75 100 125 150 175 Layers ViT-H/14
0
25
50
75
100
125
150
175
La ye
rs V
iT -H
/1 4
ViT-H/14
0 20 40 60 80 100 120 Layers R50
0
20
40
60
80
100
120
La ye
rs R
50
R50
0 50 100 150 200 250 300 350 Layers R152
0
50
100
150
200
250
300
350
La ye
rs R
15 2
R152
where HSIC is the Hilbert-Schmidt independence criterion [15]. Given the centering matrix H = In− 1n11
T and the centered Gram matrices K ′ = HKH and L′ = HLH , HSIC(K,L) = vec(K ′) · vec(L′)/(m− 1)2, the similarity between these centered Gram matrices. CKA is invariant to orthogonal transformation of representations (including permutation of neurons), and the normalization term ensures invariance to isotropic scaling. These properties enable meaningful comparison and analysis of neural network hidden representations. To work at scale with our models and tasks, we approximate the unbiased estimator of HSIC [39] using minibatches, as suggested in [29].

heading: 4 Representation Structure of ViTs and Convolutional Networks

text:
We begin our investigation by using CKA to study the internal representation structure of each model. How are representations propagated within the two architectures, and are there signs of functional differences? To answer these questions, we take every pair of layers X,Y within a model and compute their CKA similarity. Note that we take representations not only from outputs of ViT/ResNet blocks, but also from intermediate layers, such as normalization layers and the hidden activations inside a ViT MLP. Figure 1 shows the results as a heatmap, for multiple ViTs and ResNets. We observe clear differences between the internal representation structure between the two model architectures: (1) ViTs show a much more uniform similarity structure, with a clear grid like structure (2) lower and higher layers in ViT show much greater similarity than in the ResNet, where similarity is divided into different (lower/higher) stages.
We also perform cross-model comparisons, where we take all layers X from ViT and compare to all layers Y from ResNet. We observe (Figure 2) that the lower half of 60 ResNet layers are similar to approximately the lowest quarter of ViT layers. In particular, many more lower layers in the ResNet are needed to compute similar representations to the lower layers of ViT. The top half of the ResNet is approximately similar to the next third of the ViT layers. The final third of ViT layers is less similar to
all ResNet layers, likely because this set of layers mainly manipulates the CLS token representation, further studied in Section 6.
Taken together, these results suggest that (i) ViT lower layers compute representations in a different way to lower layers in the ResNet, (ii) ViT also more strongly propagates representations between lower and higher layers (iii) the highest layers of ViT have quite different representations to ResNet.

heading: 5 Local and Global Information in Layer Representations

text:
In the previous section, we observed much greater similarity between lower and higher layers in ViT, and we also saw that ResNet required more lower layers to compute similar representations to a smaller set of ViT lower layers. In this section, we explore one possible reason for this difference: the difference in the ability to incorporate global information between the two models. How much global information is aggregated by early self-attention layers in ViT? Are there noticeable resulting differences to the features of CNNs, which have fixed, local receptive fields in early layers? In studying these questions, we demonstrate the influence of global representations and a surprising connection between scale and self-attention distances.
Analyzing Attention Distances: We start by analyzing ViT self-attention layers, which are the mechanism for ViT to aggregate information from other spatial locations, and structurally very different to the fixed receptive field sizes of CNNs. Each self-attention layer comprises multiple self-attention heads, and for each head we can compute the average distance between the query patch position and the locations it attends to. This reveals how much local vs global information each self-attention layer is aggregating for the representation. Specifically, we weight the pixel distances by the attention weights for each attention head and average over 5000 datapoints, with results shown in Figure 3. In agreement with Dosovitskiy et al. [14], we observe that even in the lowest layers of ViT, self-attention layers have a mix of local heads (small distances) and global heads (large distances). This is in contrast to CNNs, which are hardcoded to attend only locally in the lower layers. At higher layers, all self-attention heads are global.
Interestingly, we see a clear effect of scale on attention. In Figure 4, we look at attention distances when training only on ImageNet (no large-scale pre-training), which leads to much lower performance in ViT-L/16 and ViT-H/14 [14]. Comparing to Figure 3, we see that with not enough data, ViT does not learn to attend locally in earlier layers. Together, this suggests that using local information early on for image tasks (which is hardcoded into CNN architectures) is important for strong performance.
Does access to global information result in different features? The results of Figure 3 demonstrate that ViTs have access to more global information than CNNs in their lower layers. But does this result in different learned features? As an interventional test, we take subsets of the ViT attention heads from the first encoder block, ranging from the subset corresponding to the most local attention
heads to a subset of the representation corresponding to the most global attention heads. We then compute CKA similarity between these subsets and the lower layer representations of ResNet.
The results, shown in Figure 5, which plot the mean distance for each subset against CKA similarity, clearly show a monotonic decrease in similarity as mean attention distance grows, demonstrating that access to more global information also leads to quantitatively different features than computed by the local receptive fields in the lower layers of the ResNet.
Effective Receptive Fields: We conclude by computing effective receptive fields [23] for both ResNets and ViTs, with results in Figure 6 and Appendix C. We observe that lower layer effective receptive fields for ViT are indeed larger than in ResNets, and while ResNet effective receptive fields grow gradually, ViT receptive fields become much more global midway through the network. ViT receptive fields also show strong dependence on their center patch due to their strong residual connections, studied in the next section. As we show in Appendix C, in attention sublayers, receptive fields taken before the residual connection show far less dependence on this central patch.

heading: 6 Representation Propagation through Skip Connections

text:
The results of the previous section demonstrate that ViTs learn different representations to ResNets in lower layers due to access to global information, which explains some of the differences in represen-
Attention 1 Attention 3 Attention 6 Attention 9 Attention 12 ViT-B/32
Initial Conv Block 3 Block 7 Block 12 Block 16 ResNet-50
Figure 6: ResNet effective receptive fields are highly local and grow gradually; ViT effective receptive fields shift from local to global. We measure the effective receptive field of different layers as the absolute value of the gradient of the center location of the feature map (taken after residual connections) with respect to the input. Results are averaged across all channels in each map for 32 randomlyselected images.
0 2 4 6 8 Token index
0
2
4
6
8
10
Bl oc
k In
de x
Ratio of Norms (first few tokens)
2
4
6
8
10
12
0 2 4 6 8 10 12 14 Block Index
0
2
4
6
8
10
Av er
ag e
no rm
o f r
ep re
se nt
at io
n
Ratio of Norms (aggregated) Self-Attention MLP Self-Attention CLS MLP CLS ResNet50
Figure 7: Most information in ViT passes through skip connections. Comparison of representation norms between the skip-connection (identity) and the long branch for ViT-B/16 trained on ImageNet and a ResNet. For ViT, we show the CLS token separately from the rest of the representation. (left) shows the ratios separated for the first few tokens (token 0 is CLS), (right) shows averages over all tokens.
tation structure observed in Section 4. However, the highly uniform nature of ViT representations (Figure 1) also suggests lower representations are faithfully propagated to higher layers. But how does this happen? In this section, we explore the role of skip connections in representation propagation across ViTs and ResNets, discovering ViT skip connections are highly influential, with a clear phase transition from preserving the CLS (class) token representation (in lower layers) to spatial token representations (in higher layers).
Like Transformers, ViTs contain skip (aka identity or shortcut) connections throughout, which are added on after the (i) self-attention layer, and (ii) MLP layer. To study their effect, we plot the norm ratio ||zi||/||f(zi)|| where zi is the hidden representation of the ith layer coming from the skip connection, and f(zi) is the transformation of zi from the long branch (i.e. MLP or self-attention.)
The results are in Figure 7 (with additional cosine similarity analysis in Figure E.2.) The heatmap on the left shows ||zi||/||f(zi)|| for different token representations. We observe a striking phase transition: in the first half of the network, the CLS token (token 0) representation is primarily propagated by the skip connection branch (high norm ratio), while the spatial token representations have a large contribution coming from the long branch (lower norm ratio). Strikingly, in the second half of the network, this is reversed.
The right pane, which has line plots of these norm ratios across ResNet50, the ViT CLS token and the ViT spatial tokens additionally demonstrates that skip connection is much more influential in ViT compared to ResNet: we observe much higher norm ratios for ViT throughout, along with the phase transition from CLS to spatial token propagation (shown for the MLP and self-attention layers.)
ViT Representation Structure without Skip Connections: The norm ratio results strongly suggest that skip connections play a key role in the representational structure of ViT. To test this interventionally, we train ViT models with skip connections removed in block i for varying i, and plot the CKA representation heatmap. The results, in Figure 8, illustrate that removing the skip connections in a block partitions the layer representations on either side. (We note a performance drop of 4% when
0 1 2 3 4 5 6 0 1 2 3 4 5 6
Token at Location(0, 0)
0 1 2 3 4 5 6 0 1 2 3 4 5 6
Token at Location(2, 1)
0 1 2 3 4 5 6 0 1 2 3 4 5 6
Token at Location(4, 2)
0 1 2 3 4 5 6 0 1 2 3 4 5 6
Token at Location(4, 4) ViT-B/32 final block
ViT-L/16 final block
removing skip connections from middle blocks.) This demonstrates the importance of representations being propagated by skip connections for the uniform similarity structure of ViT in Figure 1.

heading: 7 Spatial Information and Localization

text:
The results so far, on the role of self-attention in aggregating spatial information in ViTs, and skipconnections faithfully propagating representations to higher layers, suggest an important followup question: how well can ViTs perform spatial localization? Specifically, is spatial information from the input preserved in the higher layers of ViT? And how does it compare in this aspect to ResNet? An affirmative answer to this is crucial for uses of ViT beyond classification, such as object detection.
We begin by comparing token representations in the higher layers of ViT and ResNet to those of input patches. Recall that ViT tokens have a corresponding input patch, and thus a corresponding input spatial location. For ResNet, we define a token representation to be all the convolutional channels at a particular spatial location. This also gives it a corresponding input spatial location. We can then take a token representation and compute its CKA score with input image patches at different locations. The results are illustrated for different tokens (with their spatial locations labelled) in Figure 9.
For ViT, we observe that tokens corresponding to locations at the edge of the image are similar to edge image patches, but tokens corresponding to interior locations are well localized, with their representations being most similar to the corresponding image patch. By contrast, for ResNet, we see significantly weaker localization (though Figure D.3 shows improvements for earlier layers.)
One factor influencing this clear difference between architectures is that ResNet is trained to classify with a global average pooling step, while ViT has a separate classification (CLS) token. To examine this further, we test a ViT architecture trained with global average pooling (GAP) for localization (see Appendix A for training details). The results, shown in Figure 10, demonstrate that global average pooling does indeed reduce localization in the higher layers. More results in Appendix Section D.
Localization and Linear Probe Classification: The previous results have looked at localization through direct comparison of each token with input patches. To complete the picture, we look at using each token separately to perform classification with linear probes. We do this across different layers of the model, training linear probes to classify image label with closed-form few-shot linear regression similar to Dosovitskiy et al. [14] (details in Appendix A). Results are in Figure 11, with further results in Appendix F. The left pane shows average accuracy of classifiers trained on individual tokens, where we see that ResNet50 and ViT with GAP model tokens perform well at higher layers, while in the standard ViT trained with a CLS token the spatial tokens do poorly – likely because their representations remain spatially localized at higher layers, which makes global classification challenging. Supporting this are results on the right pane, which shows that a single token from the
ViT-GAP model achieves comparable accuracy in the highest layer to all tokens pooled together. With the results of Figure 9, this suggests all higher layer tokens in GAP models learn similar (global) representations.

heading: 8 Effects of Scale on Transfer Learning

text:
Motivated by the results of Dosovitskiy et al. [14] that demonstrate the importance of dataset scale for high performing ViTs, and our earlier result (Figure 4) on needing scale for local attention, we perform a study of the effect of dataset scale on representations in transfer learning.
We begin by studying the effect on representations as the JFT-300M pretraining dataset size is varied. Figure 12 illustrates the results on ViT-B/32 and ViT-L/16. Even with 3% of the entire dataset, lower layer representations are very similar to the model trained on the whole dataset, but higher layers require larger amounts of pretraining data to learn the same representations as at large data scale, especially with the large model size. In Section G, we study how much representations change in finetuning, finding heterogeneity over datasets.
We next look at dataset size effect on the larger ViT-L/16 and ViT-H/14 models. Specifically, in the left pane of Figure 13, we train linear classifer probes on ImageNet classes for models pretrained on JFT-300M vs models only pretrained on ImageNet. We observe the JFT-300M pretained models achieve much higher accuracies even with middle layer representations, with a 30% gap in absolute
accuracy to the models pretrained only on ImageNet. This suggests that for larger models, the larger dataset is especially helpful in learning high quality intermediate representations. This conclusion is further supported by the results of the right pane of Figure 13, which shows linear probes on different ResNet and ViT models, all pretrained on JFT-300M. We again see the larger ViT models learn much stronger intermediate representations than the ResNets. Additional linear probes experiments in Section F demonstrate this same conclusion for transfer to CIFAR-10 and CIFAR-100.

heading: 9 Discussion

text:
Limitations: Our study uses CKA [17], which summarizes measurements into a single scalar, to provide quantitative insights on representation similarity. While we have complemented this with interventional tests and other analyses (e.g. linear probes), more fine-grained methods may reveal additional insights and variations in the representations.
Conclusion: Given the central role of convolutional neural networks in computer vision breakthroughs, it is remarkable that Transformer architectures (almost identical to those used in language) are capable of similar performance. This raises fundamental questions on whether these architectures work in the same way as CNNs. Drawing on representational similarity techniques, we find surprisingly clear differences in the features and internal structures of ViTs and CNNs. An analysis of self-attention and the strength of skip connections demonstrates the role of earlier global features and strong representation propagation in ViTs for these differences, while also revealing that some CNN properties, e.g. local information aggregation at lower layers, are important to ViTs, being learned from scratch at scale. We examine the potential for ViTs to be used beyond classification through a study of spatial localization, discovering ViTs with CLS tokens show strong preservation of spatial information — promising for future uses in object detection. Finally, we investigate the effect of scale for transfer learning, finding larger ViT models develop significantly stronger intermediate representations through larger pretraining datasets. These results are also very pertinent to understanding MLP-based architectures for vision proposed by concurrent work [42, 43], further discussed in Section H, and together answer central questions on differences between ViTs and CNNs, and suggest new directions for future study. From the perspective of societal impact, these findings and future work may help identify potential failures as well as greater model interpretability.

title: Do Vision Transformers See Like Convolutional Neural Networks?