# Language Models are
Multilingual Chain-of-Thought Reasoners

Freda Shi1,2, Mirac Suzgun1,3,∗ Markus Freitag1 Xuezhi Wang1 &Suraj Srivats4
Soroush Vosoughi4 Hyung Won Chung1 Yi Tay1 &Sebastian Ruder1 Denny Zhou1
Dipanjan Das1 Jason Wei1
1Google Research 2Toyota Technological Institute at Chicago
3Stanford University 4Dartmouth College Equal contribution. Work done during
internship at Google Research.

###### Abstract

We evaluate the reasoning abilities of large language models in multilingual
settings. We introduce the Multilingual Grade School Math (MGSM) benchmark, by
manually translating 250 grade-school math problems from the GSM8K dataset
(Cobbe et al., 2021) into ten typologically diverse languages. We find that
the ability to solve MGSM problems via chain-of-thought prompting emerges with
increasing model scale, and that models have strikingly strong multilingual
reasoning abilities, even in underrepresented languages such as Bengali and
Swahili. Finally, we show that the multilingual reasoning abilities of
language models extend to other tasks such as commonsense reasoning and word-
in-context semantic judgment. The MGSM benchmark is publicly available at
https://github.com/google-research/url-nlp.

0.01%1%100%$0$$10$$20$$30$$40$$50$$60$$70$Underrepresented languages (sw, bn,
te, th) High-resource languages (ja, zh, ru, es, fr, de)English (en)Frequency
of language in pre-training dataset (token percentage)MGSM Accuracy
(%)Translate to English with Google Translate and solve with English
intermediate stepsIntermediate reasoning steps in the language of the
questionIntermediate reasoning steps in English Figure 1: Correlation between
language frequency and MGSM accuracy for PaLM-540B. The accuracy is
surprisingly high, even for underrepresented languages like Swahili (sw) and
Bengali (bn), which account for less than 0.01% of the pre-training dataset.

##  1 Introduction

Recent work has shown that presenting explicit reasoning steps (i.e., chains
of thought; CoT) in English elicits multi-step reasoning abilities of large
language models such as GPT-3 and PaLM (Brown et al., 2020; Chowdhery et al.,
2022; Wei et al., 2022b, inter alia). Pretrained multilingual language models
have also achieved impressive performance on various NLP tasks across
typologically distinct languages (Conneau et al., 2020; Xue et al., 2021;
Chowdhery et al., 2022; Clark et al., 2020; Hu et al., 2020; Ruder et al.,
2021, inter alia). Tasks in existing multilingual benchmarks usually require
only simple reasoning steps, and so it is still unclear how well language
models perform on tasks that require more complex reasoning in a multilingual
setting.

In this work, we introduce the MGSM benchmark to bridge the gap between the
progress on English-based chain-of-thought reasoning and multilingual NLP. We
extend a subset of the English-language GSM8K dataset (Cobbe et al., 2021) to
ten typologically diverse languages via manual translation of problems into
target languages. To the best of our knowledge, this is the first multilingual
benchmark to evaluate the arithmetic reasoning abilities of language models.

We evaluate two large language models, GPT-3 (Brown et al., 2020; Ouyang et
al., 2022) and PaLM (Chowdhery et al., 2022), on this benchmark. While both
models solve less than 20% of problems with standard prompting, the
540-billion-parameter PaLM model in particular shows exceptional multilingual
reasoning abilities with intermediate reasoning steps (Figure 1), solving more
than 40% of the problems in any investigated language, including
underrepresented languages such as Bengali and Swahili. In our best setting,
PaLM achieves an average solve rate of 55% across languages. We find that
intermediate reasoning steps in English consistently lead to competitive or
better results than those written in the native language of the question,
suggesting that English chain-of-thought prompting may be a useful baseline
for future multilingual reasoning work.

We further demonstrate that the multilingual reasoning abilities of pretrained
models extend to common-sense reasoning (Ponti et al., 2020) and word-in-
context semantic judgment (Raganato et al., 2020). By presenting the models
with few-shot examples in different languages, PaLM sets a new state-of-the-
art performance ($89.9\%$) on XCOPA (Ponti et al., 2020), outperforming the
prior approaches that require thousands of training examples.

##  2 The MGSM Benchmark

In this section, we describe the collection process of Multilingual Grade
School Math (MGSM), to our knowledge the first multilingual arithmetic
reasoning benchmark.

Figure 2: MGSM problem distribution with respect to the number of reasoning
steps in the standard solution.

#### Source data.

We used GSM8K (Cobbe et al., 2021), an English-language human-annotated grade-
school math problem dataset, as the base data source. For MGSM, we took the
first 250 examples from the GSM8K official test example list. Each problem
requires two to eight steps to solve according to the official solution
(Figure 2). The answer for each question in GSM8K was written as an Arabic
numeral, which we kept consistent across all languages to facilitate cross-
lingual prediction.111Certain scripts such as Devanagari employ different
numerals. We restrict the data to Arabic numerals for consistency but future
work may investigate cross-lingual numeracy by mapping Arabic numerals to
those of the corresponding script (see Spithourakis & Riedel, 2018).

#### Target language selection.

We selected a typologically diverse set of ten languages other than English
(en), spanning eight language families and different levels of representation
in standard pretraining datasets such as mC4 (Xue et al., 2021): Bengali (bn),
Chinese (zh), French (fr), German (de), Japanese (ja), Russian (ru), Spanish
(es), Swahili (sw), Telugu (te), and Thai (th).

#### Manual translation process.

We enlisted the help of paid professional translators (two for Chinese and
German, three for Russian, five for Thai, one for each remaining target
language) for the manual translation of the 250 selected English-language
examples from GSM8K. All translators involved were native speakers of the
target language and had at least two years of professional experience in
translating between English and the target language. All translators had
signed a machine translation (MT) non-usage declaration before they started to
work. To verify the quality of the human translations, the vendor sent a
random subset of translations to an additional translator to verify the
quality, and checked for $n$-gram overlap with popular MT providers to ensure
that no machine translation toolkit has been used. We employ the translation
results as gold standard translations.

##  3 Multilingual Chain-of-Thought Prompting

Original Question |  Frage: Roger hat 5 Tennisbälle. Er kauft noch 2 Dosen Tennisbälle. In jeder  Dose sind 3 Tennisbälle. Wie viele Tennisbälle hat er jetzt?
---|---
Direct |  Antwort: 11
Native-CoT |  Schritt-für-Schritt-Antwort: Roger begann mit 5 Bällen. 2 Dosen von jeweils 3  Tennisbällen macht 6 Tennisbälle. 5 + 6 = 11. Die Antwort ist 11.
EN-CoT |  Step-by-Step Answer: Roger started with 5 balls. 2 cans of 3 tennis balls each is 6 tennis balls. 5 + 6 = 11. The answer is 11.
Translated English Question |  Question: Roger has 5 tennis balls. He buys 2 more cans of tennis balls. Each can has 3 tennis balls. How many tennis balls does he have now?
Translate-EN |  Step-by-Step Answer: Roger started with 5 balls. 2 cans of 3 tennis balls each is 6 tennis balls. 5 + 6 = 11. The answer is 11.
Table 1: Example solution formats (§3) for a German exemplar problem, where
German-specific components are underlined and are changed to the corresponding
translations for other investigated languages. For Direct, Native-CoT and EN-
CoT, we provide the original German question as input to the model and expect
an answer in the corresponding format; for Translate-EN, we input the
translated question in English, and expect a step-by-step solution in English.
To obtain the desirable output format, we prepend few-shot examples in the
corresponding format.

We provide an overview of standard prompting and chain-of-thought prompting,
as well as their extensions to the multilingual setting, which we illustrate
in Table 1 and use in our experiments (§ 4).

In standard prompting, given a prompt in the source language, the model is
asked to predict the answer (Brown et al., 2020; Schick & Schütze, 2021). This
can be done in a zero-shot or few-shot setting by providing exemplars
following the same template as additional input to the model. We refer to this
setting as direct answer prediction (Direct) as the model directly predicts
the answer to the problem. This setting measures the model’s ability to solve
problems without any intermediate reasoning steps.

Chain-of-thought (CoT; Wei et al., 2022b) prompting helps improve many few-
shot reasoning tasks, by augmenting few-shot examples with intermediate
reasoning steps that should be predicted by the model. In the multilingual
setting, we can apply CoT to solve the problem in the native language (Native-
CoT) by predicting the reasoning steps in the original language of the
problem. This measures the model’s ability to both understand and solve the
problem in a specific language.

Alternatively, we can ask the model to predict the chain of thought in English
(EN-CoT), regardless of the problem language. Such an approach may be useful
as English is often used as the source language for cross-lingual transfer (Hu
et al., 2020) and has been found effective when used as the prompt language
(Zhao & Schütze, 2021; Winata et al., 2021; Lin et al., 2021b).

Finally, we can translate the problem to English and solve it with English CoT
(Translate-EN). In this setting, we use the Google Translate API to translate
problems into English. This mirrors the translate-train setup (Hu et al.,
2020; Xue et al., 2021; Ruder et al., 2021), the best-performing setting for
fine-tuning multilingual models where the training data is translated to
English.

Beyond the prompting methods, there are different ways to provide few-shot
examples in context for multilingual prompting:

  * •

All native question exemplars (Native-Exemplars). We use a few in-language
questions together with their solutions as the few-shot prompt exemplars. This
is the most natural setting when we have a few examples in each investigated
language.

  * •

All English question exemplars (English-Exemplars). When we are unable to
access any existing questions or solution examples in some languages, an
intuitive way is to use English questions and solutions as exemplars to
perform zero-shot cross-lingual transfer. Note that it is unrealistic to
combine this exemplar selection setting with Native-CoT, since we assume no
access to the native language for prompting.

  * •

Generic multilingual question exemplars (Multilingual-Exemplars). Similar to
English-Exemplars, we assume access to questions and solutions in a few
languages, and test if multilingual exemplars better elicit the multilingual
reasoning ability of models.

For Translate-EN, as all exemplar questions and solutions are in English, we
only experiment with the translated native question exemplars and English CoT.
We summarize the combinations of prompting and exemplar methods in Table 2,
and present an illustration in Figure 3. Detailed prompting input for each
investigated combination can be found in § A.2.

| Direct | Native-CoT | EN-CoT | Translate-EN
---|---|---|---|---
Native-Exemplars | ✓ | ✓ | ✓ | ✓
English-Exemplars | ✓ | N/A | ✓ | N/A
Multilingual-Exemplars | ✓ | ✓ | ✓ | N/A
Table 2: Possible combinations between few-shot exemplar selection and
solution strategies. Figure 3:  The chain-of-thought prompts and example model
outputs in the MGSM experiments. The solutions are written in the same
language as the questions of interest (Native-CoT).

##  4 Experiments on MGSM

| avg | hrl | url | en | de | fr | es | ru | zh | ja | th | te | bn | sw
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Lang. Freq. (PaLM, %) | – | – | – | 78.0 | 3.5 | 3.3 | 2.1 | .53 | .40 | .38 | .04 | .02 | .006 | .005
GPT-3 ($\mathtt{text}$-$\mathtt{davinci}$-$\mathtt{002}$) |  |  |  |  |
Direct | 11.7 | 15.1 | 5.7 | 16.0 | 14.8 | 16.8 | 17.2 | 12.4 | 18.0 | 11.2 | 8.8 | 0.8 | 4.4 | 8.8
Native-CoT | 26.4 | 34.7 | 7.2 | 53.6 | 36.0 | 37.6 | 40.4 | 28.4 | 40.0 | 26.0 | 10.8 | 0.4 | 6.4 | 11.2
EN-CoT | 31.6 | 39.4 | 13.9 | 53.6 | 44.0 | 46.0 | 44.8 | 28.4 | 40.8 | 32.4 | 19.6 | 5.6 | 9.6 | 20.8
Translate-EN | 45.6 | 47.5 | 40.7 | 53.6 | 46.4 | 46.4 | 51.6 | 48.8 | 47.2 | 44.8 | 41.2 | 42.8 | 41.2 | 37.6
PaLM-540B |  |  |  |  |  |  |  |  |  |  |  |  |  |
Direct | 18.6 | 19.3 | 16.8 | 22.0 | 18.8 | 19.6 | 20.0 | 22.0 | 19.2 | 16.0 | 16.8 | 17.6 | 17.2 | 15.6
Native-CoT | 48.1 | 47.9 | 44.9 | 62.4 | 49.2 | 46.4 | 56.8 | 48.4 | 46.8 | 40.0 | 52.8 | 45.6 | 46.0 | 35.2
EN-CoT | 51.3 | 52.3 | 46.8 | 62.4 | 53.6 | 51.2 | 58.0 | 55.6 | 46.0 | 49.6 | 49.6 | 46.8 | 46.4 | 44.4
Translate-EN | 55.0 | 56.3 | 51.2 | 62.4 | 57.2 | 55.2 | 60.0 | 59.6 | 55.6 | 50.0 | 50.8 | 49.6 | 53.2 | 51.2
Table 3:  Accuracy (%) on MGSM of different models and languages with exemplar
questions in native languages (Native-Exemplars). hrl: average performance
across high-resource languages with larger than 0.1% frequency in the training
corpora; url: average performance across underrepresented languages. We use 6
questions and solutions as the few-shot exemplar whenever possible: while the
token number for 6-shot prompts in some languages may exceed the token number
limit of GPT-3, we use the maximum possible number of exemplars instead for
these cases. Detailed numbers of exemplars for each language in GPT-3
experiments can be found in § A.1. The best numbers in each column are in
boldface.

In this section, we evaluate the multilingual reasoning abilities of two
representative state-of-the-art pretrained large language models—GPT-3 (Brown
et al., 2020) and PaLM (Chowdhery et al., 2022) —on our MGSM benchmark in
various prompting settings using exemplars in the source language (Native-
Exemplars).222We focus on these two models due to their notable few-shot
performance. In contrast, current multilingual models perform poorly in few-
shot settings and are generally used for finetuning with more data (Winata et
al., 2021). Throughout this paper, we generate outputs using greedy decoding
(i.e., sampling with temperature $\tau=0$).

###  4.1 Main Results

We first compare the few-shot Native-Exemplars performance with different
solution strategies (Table 3). In line with the English results reported by
Wei et al. (2022b), we find that intermediate reasoning steps (Native-CoT and
EN-CoT) help both models achieve substantial reasoning performance gains
across all languages, outperforming direct answer prediction with no explicit
reasoning steps (Direct) by a significant margin. PaLM shows exceptional
multilingual reasoning ability: while it outperforms GPT-3 on all languages
with different settings, PaLM-540B with intermediate reasoning steps (Native-
CoT and EN-CoT) achieves results similar to Translate-EN on all languages,
even on underrepresented languages such as Bengali (bn) and Swahili (sw),
which cover less than 0.01% of the training corpora.

In addition, reasoning in English (EN-CoT) consistently achieves competitive
or better performance than reasoning in the native language of the question
(Native-CoT), suggesting that English intermediate steps can be considered as
useful baseline in future work on multilingual reasoning.

###  4.2 Further Analysis

#### Effect of language frequency in training corpora.

We illustrate the main results of Native-CoT, EN-CoT and Translate-EN with
respect to the language frequency in PaLM training data (Figure 1).
Surprisingly, there is no strong correlation between the performance and the
language frequency in the training corpora: the average accuracy among the
four underrepresented languages was only 3% lower than the that among the six
high-resource languages (44.9% vs 47.9%). Moreover, the performance of
reasoning in Thai, Telugu, and Bengali is on par with reasoning in French,
Japanese, and Chinese, despite having significantly much less data in the
training corpora.

In contrast to prior work that identifies language frequency as important for
complex NLU tasks with relatively smaller models (Hu et al., 2020; Lauscher et
al., 2020; Ahuja et al., 2022), these results thus indicate that the reasoning
ability of large language models may not be primarily dependent on their
presence in training data and that language models are able to transfer their
knowledge from high-resource to underrepresented languages to some extent.

ABCD1D2$0$$10$$20$$30$$40$$50$$60$$70$Model NamesMGSM Accuracy
(%)GPT-38B62B540B$0$$10$$20$$30$$40$$50$$60$$70$Model
ScalePaLMendefresruzhjathtebnsw Figure 4:  MGSM accuracy with different model
scales. The letters A, B, C, D1, and D2 denote
$\mathtt{text}$-$\mathtt{ada}$-$\mathtt{001}$,
$\mathtt{text}$-$\mathtt{babbage}$-$\mathtt{001}$,
$\mathtt{text}$-$\mathtt{curie}$-$\mathtt{001}$,
$\mathtt{text}$-$\mathtt{davinci}$-$\mathtt{001}$, and
$\mathtt{text}$-$\mathtt{davinci}$-$\mathtt{002}$ in the GPT-3 (Brown et al.,
2020; Ouyang et al., 2022) family, respectively. While the number of
parameters in each GPT-3 model is not publicly available, we order them
alphabetically. Detailed numbers can be found in Table 8.

$1$$2$$4$$6$$0$$10$$20$$30$$40$$50$$60$$70$# few-shot exemplarsMGSM Accuracy
(%)endefresruzhjathtebnsw Figure 5:  MGSM accuracy of PaLM-540B with different
numbers of few-shot exemplars. Detailed numbers can be found in Table 8.

#### Effect of model scale.

We analyze the effect of model scale (i.e., number of model parameters and
computational resources used for training) on their multilingual arithmetic
reasoning abilities (Figure 5). As the models scale up, the performance
generally improves for both GPT-3 and PaLM model series on all languages.
Neither model achieves a substantial solve rate until a certain scale
($\mathtt{text}$-$\mathtt{davinci}$-$\mathtt{001}$ for GPT-3 and PaLM-62B for
PaLM), hence multilingual reasoning can be considered an emergent ability of
large language models (Wei et al., 2022a). It is worth noting that the amount
of training data per language is constant across language model scales for
PaLM—the fact that scale facilitates reasoning implies that further scaling
may continue to improve the multilingual reasoning ability of large language
models.

#### Effect of exemplar amount.

We analyze how the multilingual reasoning performance of PaLM-540B, the
overall best-performing model, is affected by the number of few-shot exemplars
(Figure 5). Although not all trends are strictly increasing with the number of
exemplars, PaLM-540B benefits from having more examples in general for all
languages.

#### Effect of exemplar type choice.

| avg | hrl | url | en | de | fr | es | ru | zh | ja | th | te | bn | sw
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Native-Exemplars |  |  |  |  |
Native-CoT | 48.1 | 47.9 | 44.9 | 62.4 | 49.2 | 46.4 | 56.8 | 48.4 | 46.8 | 40.0 | 52.8 | 45.6 | 46.0 | 35.2
EN-CoT | 51.3 | 52.3 | 46.8 | 62.4 | 53.6 | 51.2 | 58.0 | 55.6 | 46.0 | 49.6 | 49.6 | 46.8 | 46.4 | 44.4
Multilingual-Exemplars |  |  |  |  |
Native-CoT | 29.8 | 31.8 | 26.3 | 52.0 | 41.6 | 7.2 | 10.4 | 36.0 | 42.8 | 32.8 | 18.0 | 33.6 | 26.8 | 26.8
EN-CoT | 48.7 | 50.0 | 46.3 | 57.6 | 53.2 | 43.2 | 53.2 | 48.0 | 51.2 | 43.6 | 46.8 | 46.4 | 48.4 | 43.6
English-Exemplars |  |  |  |  |
EN-CoT | 34.7 | 39.4 | 26.6 | 62.4 | 46.0 | 37.2 | 50.4 | 23.6 | 29.2 | 26.8 | 17.2 | 30.0 | 34.4 | 24.8
Table 4: Performance on MGSM with different prompt exemplar type choices: the
first section is copied correspondingly from Table 3. The best numbers in each
column are in boldface.

We compare the multilingual reasoning performance of PaLM-540B across
languages with different exemplar choices (Table 4). For the Multilingual-
Exemplars setting, we concatenate one example from each of the most frequent
languages (English, German, French, Spanish, Russian, and Chinese) as the
generic prompt for all languages. While the best choice is almost always to
use Native-Exemplars and EN-CoT, Multilingual-Exemplars with EN-CoT achieves
competitive performance across the board, suggesting an effective approach
when we do not have access to any existing example in some languages.

Most notably, with EN-CoT, Multilingual-Exemplars significantly outperforms
English-Exemplars on all non-English languages, including those not covered by
the few-shot examples, suggesting that a multilingual few-shot prompt helps
elicit the multilingual reasoning abilities of models more effectively than a
monolingual (English) one.

##  5 Extension to Other Multilingual Reasoning Benchmarks

To better understand the multilingual reasoning abilities of large pretrained
language models, we extend our experiments to two additional multilingual
reasoning benchmarks, XCOPA (Ponti et al., 2020) and XL-WiC (Raganato et al.,
2020). Throughout this section, we evaluate the Codex
($\mathtt{code}$-$\mathtt{davinci}$-$\mathtt{002}$; Chen et al., 2021)333For
both investigated tasks, we find that
$\mathtt{code}$-$\mathtt{davinci}$-$\mathtt{002}$ generally produces
competitive or better results than
$\mathtt{text}$-$\mathtt{davinci}$-$\mathtt{002}$ on a small set of samples.
In consideration of budget, we choose to use
$\mathtt{code}$-$\mathtt{davinci}$-$\mathtt{002}$ because it supports free
access at the time of our experiment.  and PaLM-540B models.

###  5.1 XCOPA

Model | avg | et | ht | id | it | qu | sw | ta | th | tr | vi | zh
---|---|---|---|---|---|---|---|---|---|---|---|---
Human | 97.6 | 98.2 | 96.4 | 100 | 97 | 94.8 | 99 | 98.6 | 98.2 | 96.4 | 98.4 | 96.6
MAD-X Base | 61.0 | 61.3 | 53.7 | 65.8 | 63.0 | 52.5 | 56.3 | 61.9 | 61.8 | 60.3 | 66.1 | 67.6
XLM-R Large | 68.7 | 71.4 | (50) | 79.8 | 72.6 | (50) | 59.2 | 73 | 72.8 | 74.4 | 73.8 | 78.6
mT5-XXL | 74.9 | 77.5 | 72.1 | 81.1 | 75.9 | 54.5 | 74.1 | 75.9 | 78.3 | 78.1 | 76.9 | 79.5
RoBERTa Large (TT) | 76.1 | 81.0 | 73.8 | 82.2 | 77.8 | (50) | 74.2 | 79.6 | 71.4 | 79.6 | 81.0 | 86.0
1-13 Codex ($\mathtt{code}$-$\mathtt{davinci}$-$\mathtt{002}$)
Direct | 73.3 | 73.8 | 55.6 | 88.8 | 95.4 | 51.2 | 56.0 | 54.6 | 70.2 | 88.6 | 80.4 | 91.4
En-CoT | 80.7 | 88.8 | 79.6 | 91.4 | 96.6 | 52.2 | 67.4 | 55.8 | 84.2 | 91.2 | 86.6 | 93.4
1-13 PaLM-540B
Direct | 83.7 | 77.4 | 78.0 | 92.6 | 96.0 | 61.0 | 69.4 | 85.4 | 87.2 | 92.8 | 89.8 | 91.6
En-CoT | 89.9 | 91.0 | 89.6 | 94.0 | 97.4 | 66.8 | 85.4 | 90.8 | 90.2 | 94.6 | 94.6 | 94.8

Table 5: Accuracy on the XCOPA languages compared to previous work. Human
evaluation (Human) on XCOPA was performed by Ponti et al. (2020). The MAD-X
Base, XLM-R Large, and RoBERTa Large (_translate test_) results are from Ponti
et al. (2020), whereas the mT5 results are from (Ruder et al., 2021). Applying
multilingual CoT-prompting to PaLM-540B has enabled us to achieve a new state-
of-the-art performance on XCOPA. The best model result in each column is in
boldface.

XCOPA is a multilingual evaluation dataset designed to assess the causal
commonsense reasoning capabilities of language models across multiple
languages.444https://github.com/cambridgeltl/xcopa It is an extension and re-
annotation of the English COPA dataset (Gordon et al., 2012) where the
validation and test set examples are carefully translated to and annotated in
11 typologically diverse languages. These languages are Estonian (et),
Indonesian (id), Italian (it), Cusco-Collao Quechua (qu), Swahili (sw), Tamil
(ta), Thai (th), Turkish (tr), Vietnamese (vo), and Mandarin Chinese (zh). The
task objective is to determine the causal relationship between the premise and
two options based on a question (which is either “What was the _cause_?” or
“What happened as a _result_?”). A successful model is, therefore, expected to
not only perform commonsense reasoning but also generalize its reasoning
capabilities to new languages. For each target language, XCOPA contains $100$
annotated examples in the validation set and $500$ examples in the test set.
In our experiments, we focus on the examples in the test sets and use the ones
in the validation set as few-shot exemplars whenever needed.

We test the Codex and PaLM models under both Direct and EN-CoT. In both
settings, we include the same set of examples, randomly selected from the
validation sets of tr, zh, ta, and qu, but for EN-CoT, we additionally write
brief rationales (in English) before the final answers ourselves.

#### Results.

Table 5.1 presents our main results, along with per-language breakdowns for
each XCOPA language. The previous state-of-the-art performance was around
$76\%$, obtained by RoBERTa Large in the translate-test setting where the
English RoBERTa Large model was first trained on the English COPA (Gordon et
al., 2012) and English SIQa (Sap et al., 2019) datasets and then applied to
the XCOPA test data, which was translated to English (Ponti et al., 2020).
With only four multilingual chain-of-thought examples (EN-CoT), PaLM-540B
outperforms RoBERTa Large by a significant margin ($14\%$), thereby setting a
new high bar on XCOPA. While Codex performs better than RoBERTa Large, it
still falls $9\%$ behind PaLM-540B. We also highlight that PaLM-540B performs
noticeably better than all the other models on under-represented languages
such as et, ht, and sw; this result suggests that PaLM-540B might have some
internal knowledge about these languages.

###  5.2 XL-WiC

Model | avg | bg | da | de | et | fa | fr | hr | it | ja | ko | nl | zh
---|---|---|---|---|---|---|---|---|---|---|---|---|---
Human | – | 87.0 | – | 74.0 | – | 97.0 | – | – | 78.0 | 75.0 | 76.0 | – | 85.0
XLM-R Large | 68.9 | 66.5 | 71.1 | 65.8 | 68.7 | 75.3 | 62.5 | 72.3 | 64.9 | 63.8 | 69.6 | 72.8 | 73.2
1-14 Codex ($\mathtt{code}$-$\mathtt{davinci}$-$\mathtt{002}$)
Direct | 60.8 | 59.2 | 59.6 | 68.2 | 59.0 | 58.0 | 58.6 | 65.7 | 55.4 | 56.0 | 62.0 | 64.8 | 63.0
EN-CoT | 61.4 | 60.2 | 66.6 | 70.6 | 60.3 | 63.6 | 64.6 | 61.0 | 54.2 | 52.2 | 56.6 | 62.8 | 64.0
1-14 PaLM-540B
Direct | 66.7 | 62.6 | 67.4 | 72.6 | 62.3 | 75.0 | 64.6 | 65.0 | 59.4 | 64.0 | 70.2 | 72.0 | 64.8
EN-CoT | 63.2 | 63.4 | 64.6 | 68.6 | 61.5 | 67.2 | 64.6 | 55.9 | 57.4 | 55.6 | 66.4 | 69.4 | 64.0

Table 6: Accuracy on the XL-WiC languages with Multilingual-Exemplars. XLM-R
Large denotes the previous state-of-the-art results trained with 5.4K English
examples (Raganato et al., 2020). The best model result in each column is in
boldface.

XL-WiC is a multilingual word in-context semantic judgment benchmark covering
thirteen languages:555https://pilehvar.github.io/xlwic/ Bulgarian (bg), Danish
(da), German (de), Estonian (et), Persian (fa), French (fr), Croatian (hr),
Italian (it), Japanese (ja), Korean (ko), Dutch (nl) and Chinese (zh). Given
two sentences in the same language and a word of interest which appears in
both sentences, the model is asked whether the word is of the same sense in
the sentences. In order to arrive at the correct answer, a model needs to be
aware of the concept of word sense, and to infer the sense of a word based on
its context. Despite its simplicity, this task is extremely challenging;
PaLM-540B only achieves a score of 64.6 on WiC (Pilehvar & Camacho-Collados,
2019), the English version of the task.

#### Results.

We evaluate the cross-lingual word-in-context sense judgment performance of
models (§ 5.2). With the supervision from only four examples, PaLM-540B
achieves competitive or better results that the state-of-the-art model (XLM-R
Large) on 6 (German, Persian, French, Japanese, Korean and Dutch) of the 12
investigated languages. However, we do not observe an improvement over direct
answer prediction when using chain-of-thought prompting on this task.666One
potential reason is that our prompts are not necessarily optimal (Wang et al.,
2022) and may benefit from a broader investigation of other prompt formats. On
the other hand, rationales for this task are fairly straight-forward and
example-specific. It is thus unclear whether the WiC task requires true
reasoning that benefits from the depiction of intermediate reasoning steps. We
leave further investigation for future work.

##  6 Related Work

#### Prompting.

Existing work (Radford et al., 2019; Brown et al., 2020; Schick & Schütze,
2021, inter alia) has shown that prompting pre-trained large language models
can lead to strong performance on various tasks such as text classification
(Shin et al., 2020; Gao et al., 2021), question answering (Khashabi et al.,
2020), and program synthesis (Austin et al., 2021; Nye et al., 2021; Shi et
al., 2022a): taking a few examples of the task in a certain pattern as the
prompting input, models are often able to generate accurate output following
the pattern. Wei et al. (2022b) have shown that chain-of-thought prompting
significantly improves the reasoning performance of language models, by adding
explicit reasoning steps before the final answer. Ahn et al. (2022) apply
chain-of-thought prompting in robotics scenarios, including a multilingual
setting. In this work, we systematically analyze multilingual few-shot chain-
of-thought prompting on complicated reasoning benchmarks.

#### Multilingual pre-trained language models.

Through masked language modeling (Devlin et al., 2019; Conneau et al., 2020),
auto-regressive language modeling (Brown et al., 2020; Ouyang et al., 2022) or
encoder-decoder training (Liu et al., 2020; Chen et al., 2021; Xue et al.,
2021), pre-trained Transformer-based large language models have shown
impressive performance on multiple NLP tasks across languages. Previous work
(Zhao & Schütze, 2021; Winata et al., 2021; Lin et al., 2021b) investigated
prompting in the multilingual setting and found that using English prompts
with non-English examples led to strong few-shot performance. Evaluation of
multilingual models has mostly focused on general information extraction tasks
such as question answering (Clark et al., 2020; Hu et al., 2020; Kassner et
al., 2021; Ruder & Sil, 2021) as well as specific types of reasoning such as
commonsense reasoning (Ponti et al., 2020; Lin et al., 2021a) and temporal
reasoning (Ruder et al., 2021). To the best of our knowledge, this is the
first study to evaluate the multilingual multi-step reasoning abilities of
large language models.

#### Cross-lingual transfer and generalization.

Previous work has demonstrated that pre-trained multilingual models
significantly help cross-lingual transfer on a wide range of NLP tasks such as
cross-lingual named entity recognition (Pires et al., 2019; Mulcaire et al.,
2019), zero-shot cross-lingual dependency parsing (Schuster et al., 2019; Shi
et al., 2022b), and bilingual lexicon induction (Shi et al., 2021). In this
work, we demonstrate strong cross-lingual generalization of PaLM (§4.2, §5)
and Codex (§5), on three tasks that require complicated reasoning.

#### Multilingual benchmarks.

To test the multilingual NLP performance of existing models, there has been
work introducing benchmarks on various multilingual tasks, including cross-
lingual question answering (Liu et al., 2019; Clark et al., 2020), natural
language inference (Conneau et al., 2018) and bilingual lexicon induction
(Lample et al., 2018), as well as collections across tasks (Hu et al., 2020;
Ruder et al., 2021). The tasks in these multilingual benchmarks, to the best
of our knowledge, require relatively simple reasoning processes. In this
paper, we present MGSM, a multilingual arithmetic reasoning benchmark, which
can be used to test multilingual multi-step reasoning abilities of models.

##  7 Conclusion

In this paper, we introduce MGSM, the first multilingual benchmark to evaluate
arithmetic reasoning abilities of language models. MGSM is an extension of the
GSM8K dataset (Cobbe et al., 2021) and contains 250 examples written in _ten_
typologically diverse languages. We also present a comprehensive analysis of
the multilingual reasoning abilities of large language models such as GPT-3
and PaLM on multiple multilingual benchmarks, including our own MGSM dataset.
We find that large-scale language models appear to perform complex multi-step
reasoning across multiple languages, including those underrepresented
languages which are covered by less than $0.01\%$ of training corpora.
Finally, we demonstrate that multilingual chain-of-thought prompting is an
empirically effective approach to multilingual commonsense reasoning,
outperforming the previous best model on the challenging XCOPA dataset by 13%
on average.

## References

  * Ahn et al. (2022) Michael Ahn, Anthony Brohan, Noah Brown, Yevgen Chebotar, Omar Cortes, Byron David, Chelsea Finn, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, et al.  Do as I can, not as I say: Grounding language in robotic affordances.  _arXiv preprint arXiv:2204.01691_ , 2022.  URL https://arxiv.org/abs/2204.01691.
  * Ahuja et al. (2022) Kabir Ahuja, Shanu Kumar, Sandipan Dandapat, and Monojit Choudhury.  Multi task learning for zero shot performance prediction of multilingual models.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 5454–5467, Dublin, Ireland, May 2022. Association for Computational Linguistics.  doi: 10.18653/v1/2022.acl-long.374.  URL https://aclanthology.org/2022.acl-long.374.
  * Austin et al. (2021) Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al.  Program synthesis with large language models.  _arXiv preprint arXiv:2108.07732_ , 2021.  URL https://arxiv.org/abs/2108.07732.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D. Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  _NeurIPS_ , 2020.  URL https://papers.nips.cc/paper/2020/hash/1457c0d6bfcb4967418bfb8ac142f64a-Abstract.html.
  * Chen et al. (2021) Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al.  Evaluating large language models trained on code.  _arXiv preprint arXiv:2107.03374_ , 2021.  URL https://arxiv.org/abs/2107.03374.
  * Chowdhery et al. (2022) Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, et al.  PaLM: Scaling language modeling with Pathways.  _arXiv preprint arXiv:2204.02311_ , 2022.  URL https://arxiv.org/abs/2204.02311.
  * Clark et al. (2020) Jonathan H. Clark, Eunsol Choi, Michael Collins, Dan Garrette, Tom Kwiatkowski, Vitaly Nikolaev, and Jennimaria Palomaki.  TyDi QA: A benchmark for information-seeking question answering in typologically diverse languages.  _Transactions of the Association for Computational Linguistics_ , 8:454–470, 2020.  doi: 10.1162/tacl_a_00317.  URL https://aclanthology.org/2020.tacl-1.30.
  * Cobbe et al. (2021) Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman.  Training verifiers to solve math word problems.  _arXiv preprint arXiv:2110.14168_ , 2021.  URL https://arxiv.org/abs/2110.14168.
  * Conneau et al. (2018) Alexis Conneau, Ruty Rinott, Guillaume Lample, Adina Williams, Samuel Bowman, Holger Schwenk, and Veselin Stoyanov.  XNLI: Evaluating cross-lingual sentence representations.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pp. 2475–2485, Brussels, Belgium, October-November 2018. Association for Computational Linguistics.  doi: 10.18653/v1/D18-1269.  URL https://aclanthology.org/D18-1269.
  * Conneau et al. (2020) Alexis Conneau, Kartikay Khandelwal, Naman Goyal, Vishrav Chaudhary, Guillaume Wenzek, Francisco Guzmán, Edouard Grave, Myle Ott, Luke Zettlemoyer, and Veselin Stoyanov.  Unsupervised cross-lingual representation learning at scale.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pp. 8440–8451, Online, July 2020. Association for Computational Linguistics.  doi: 10.18653/v1/2020.acl-main.747.  URL https://aclanthology.org/2020.acl-main.747.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: Pre-training of deep bidirectional transformers for language understanding.  _NAACL_ , 2019.  doi: 10.18653/v1/N19-1423.  URL https://aclanthology.org/N19-1423.
  * Gage (1994) Philip Gage.  A new algorithm for data compression.  _C Users Journal_ , 12(2):23–38, 1994.
  * Gao et al. (2021) Tianyu Gao, Adam Fisch, and Danqi Chen.  Making pre-trained language models better few-shot learners.  _ACL_ , 2021.  doi: 10.18653/v1/2021.acl-long.295.  URL https://aclanthology.org/2021.acl-long.295.
  * Gordon et al. (2012) Andrew Gordon, Zornitsa Kozareva, and Melissa Roemmele.  SemEval-2012 task 7: Choice of plausible alternatives: An evaluation of commonsense causal reasoning.  In _*SEM 2012: The First Joint Conference on Lexical and Computational Semantics – Volume 1: Proceedings of the main conference and the shared task, and Volume 2: Proceedings of the Sixth International Workshop on Semantic Evaluation (SemEval 2012)_ , pp. 394–398, Montréal, Canada, 7-8 June 2012. Association for Computational Linguistics.  URL https://aclanthology.org/S12-1052.
  * Hu et al. (2020) Junjie Hu, Sebastian Ruder, Aditya Siddhant, Graham Neubig, Orhan Firat, and Melvin Johnson.  Xtreme: A massively multilingual multi-task benchmark for evaluating cross-lingual generalisation.  In _International Conference on Machine Learning_ , pp. 4411–4421. PMLR, 2020.
  * Kassner et al. (2021) Nora Kassner, Philipp Dufter, and Hinrich Schütze.  Multilingual LAMA: Investigating Knowledge in Multilingual Pretrained Language Models.  In _Proceedings of EACL 2021_ , pp. 3250–3258, 2021.  URL http://arxiv.org/abs/2102.00894.
  * Khashabi et al. (2020) Daniel Khashabi, Sewon Min, Tushar Khot, Ashish Sabharwal, Oyvind Tafjord, Peter Clark, and Hannaneh Hajishirzi.  UNIFIEDQA: Crossing format boundaries with a single QA system.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pp. 1896–1907, Online, November 2020. Association for Computational Linguistics.  doi: 10.18653/v1/2020.findings-emnlp.171.  URL https://aclanthology.org/2020.findings-emnlp.171.
  * Lample et al. (2018) Guillaume Lample, Alexis Conneau, Marc’Aurelio Ranzato, Ludovic Denoyer, and Hervé Jégou.  Word translation without parallel data.  In _International Conference on Learning Representations_ , 2018.
  * Lauscher et al. (2020) Anne Lauscher, Vinit Ravishankar, Ivan Vulić, and Goran Glavaš.  From Zero to Hero: On the Limitations of Zero-Shot Cross-Lingual Transfer with Multilingual Transformers.  In _Proceedings of EMNLP 2020_ , 2020.  URL http://arxiv.org/abs/2005.00633.
  * Lin et al. (2021a) Bill Yuchen Lin, Seyeon Lee, Xiaoyang Qiao, and Xiang Ren.  Common sense beyond English: Evaluating and improving multilingual language models for commonsense reasoning.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pp. 1274–1287, Online, August 2021a. Association for Computational Linguistics.  doi: 10.18653/v1/2021.acl-long.102.  URL https://aclanthology.org/2021.acl-long.102.
  * Lin et al. (2021b) Xi Victoria Lin, Todor Mihaylov, Mikel Artetxe, Tianlu Wang, Shuohui Chen, Daniel Simig, Myle Ott, Naman Goyal, Shruti Bhosale, Jingfei Du, Ramakanth Pasunuru, Sam Shleifer, Punit Singh Koura, Vishrav Chaudhary, Brian O’Horo, Jeff Wang, Luke Zettlemoyer, Zornitsa Kozareva, Mona Diab, Veselin Stoyanov, and Xian Li.  Few-shot Learning with Multilingual Language Models.  _arXiv preprint arXiv:2112.10668_ , 2021b.  URL http://arxiv.org/abs/2112.10668.
  * Liu et al. (2019) Jiahua Liu, Yankai Lin, Zhiyuan Liu, and Maosong Sun.  XQA: A cross-lingual open-domain question answering dataset.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pp. 2358–2368, Florence, Italy, July 2019. Association for Computational Linguistics.  doi: 10.18653/v1/P19-1227.  URL https://aclanthology.org/P19-1227.
  * Liu et al. (2020) Yinhan Liu, Jiatao Gu, Naman Goyal, Xian Li, Sergey Edunov, Marjan Ghazvininejad, Mike Lewis, and Luke Zettlemoyer.  Multilingual denoising pre-training for neural machine translation.  _arXiv preprint arXiv:2001.08210_ , 2020.  URL https://arxiv.org/pdf/2001.08210.pdf.
  * Mulcaire et al. (2019) Phoebe Mulcaire, Jungo Kasai, and Noah A. Smith.  Polyglot contextual representations improve crosslingual transfer.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pp. 3912–3918, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.  doi: 10.18653/v1/N19-1392.  URL https://aclanthology.org/N19-1392.
  * Nye et al. (2021) Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, et al.  Show your work: Scratchpads for intermediate computation with language models.  _arXiv preprint arXiv:2112.00114_ , 2021.  URL https://openreview.net/forum?id=iedYJm92o0a.
  * Ouyang et al. (2022) Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al.  Training language models to follow instructions with human feedback.  _arXiv preprint arXiv:2203.02155_ , 2022.  URL https://arxiv.org/abs/2203.02155.
  * Pilehvar & Camacho-Collados (2019) Mohammad Taher Pilehvar and Jose Camacho-Collados.  WiC: the word-in-context dataset for evaluating context-sensitive meaning representations.  _NAACL_ , 2019.  doi: 10.18653/v1/N19-1128.  URL https://aclanthology.org/N19-1128.
  * Pires et al. (2019) Telmo Pires, Eva Schlinger, and Dan Garrette.  How multilingual is multilingual BERT?  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pp. 4996–5001, Florence, Italy, July 2019. Association for Computational Linguistics.  URL https://aclanthology.org/P19-1493.
  * Ponti et al. (2020) Edoardo Maria Ponti, Goran Glavaš, Olga Majewska, Qianchu Liu, Ivan Vulić, and Anna Korhonen.  XCOPA: A multilingual dataset for causal commonsense reasoning.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pp. 2362–2376, Online, November 2020\. Association for Computational Linguistics.  doi: 10.18653/v1/2020.emnlp-main.185.  URL https://aclanthology.org/2020.emnlp-main.185.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8), 2019.  URL https://d4mucfpksywv.cloudfront.net/better-language-models/language_models_are_unsupervised_multitask_learners.pdf.
  * Raganato et al. (2020) Alessandro Raganato, Tommaso Pasini, Jose Camacho-Collados, and Mohammad Taher Pilehvar.  XL-WiC: A multilingual benchmark for evaluating semantic contextualization.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pp. 7193–7206, Online, November 2020\. Association for Computational Linguistics.  doi: 10.18653/v1/2020.emnlp-main.584.  URL https://aclanthology.org/2020.emnlp-main.584.
  * Ruder & Sil (2021) Sebastian Ruder and Avirup Sil.  Multi-domain multilingual question answering.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing: Tutorial Abstracts_ , pp. 17–21, 2021.
  * Ruder et al. (2021) Sebastian Ruder, Noah Constant, Jan Botha, Aditya Siddhant, Orhan Firat, Jinlan Fu, Pengfei Liu, Junjie Hu, Dan Garrette, Graham Neubig, and Melvin Johnson.  XTREME-R: Towards more challenging and nuanced multilingual evaluation.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pp. 10215–10245, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.emnlp-main.802.  URL https://aclanthology.org/2021.emnlp-main.802.
  * Sap et al. (2019) Maarten Sap, Hannah Rashkin, Derek Chen, Ronan Le Bras, and Yejin Choi.  Social IQa: Commonsense reasoning about social interactions.  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)_ , pp. 4463–4473, Hong Kong, China, November 2019. Association for Computational Linguistics.  doi: 10.18653/v1/D19-1454.  URL https://aclanthology.org/D19-1454.
  * Schick & Schütze (2021) Timo Schick and Hinrich Schütze.  It’s not just size that matters: Small language models are also few-shot learners.  _NAACL_ , June 2021.  doi: 10.18653/v1/2021.naacl-main.185.  URL https://aclanthology.org/2021.naacl-main.185.
  * Schuster et al. (2019) Tal Schuster, Ori Ram, Regina Barzilay, and Amir Globerson.  Cross-lingual alignment of contextual word embeddings, with applications to zero-shot dependency parsing.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pp. 1599–1613, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.  doi: 10.18653/v1/N19-1162.  URL https://aclanthology.org/N19-1162.
  * Shi et al. (2022a) Freda Shi, Daniel Fried, Marjan Ghazvininejad, Luke Zettlemoyer, and Sida I Wang.  Natural language to code translation with execution.  _arXiv preprint arXiv:2204.11454_ , 2022a.
  * Shi et al. (2022b) Freda Shi, Kevin Gimpel, and Karen Livescu.  Substructure distribution projection for zero-shot cross-lingual dependency parsing.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 6547–6563, Dublin, Ireland, May 2022b. Association for Computational Linguistics.  doi: 10.18653/v1/2022.acl-long.452.  URL https://aclanthology.org/2022.acl-long.452.
  * Shi et al. (2021) Haoyue Shi, Luke Zettlemoyer, and Sida I. Wang.  Bilingual lexicon induction via unsupervised bitext construction and word alignment.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pp. 813–826, Online, August 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.acl-long.67.  URL https://aclanthology.org/2021.acl-long.67.
  * Shin et al. (2020) Taylor Shin, Yasaman Razeghi, Robert L. Logan IV, Eric Wallace, and Sameer Singh.  AutoPrompt: Eliciting Knowledge from Language Models with Automatically Generated Prompts.  _EMNLP_ , 2020.  doi: 10.18653/v1/2020.emnlp-main.346.  URL https://aclanthology.org/2020.emnlp-main.346.
  * Spithourakis & Riedel (2018) Georgios Spithourakis and Sebastian Riedel.  Numeracy for language models: Evaluating and improving their ability to predict numbers.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 2104–2115, Melbourne, Australia, July 2018. Association for Computational Linguistics.  doi: 10.18653/v1/P18-1196.  URL https://aclanthology.org/P18-1196.
  * Wang et al. (2022) Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, and Denny Zhou.  Rationale-augmented ensembles in language models.  _arXiv preprint arXiv:2207.00747_ , 2022.
  * Wei et al. (2022a) Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al.  Emergent abilities of large language models.  _Transactions on Machine Learing Research (TMLR)_ , 2022a.  URL https://arxiv.org/abs/2206.07682.
  * Wei et al. (2022b) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc Le, and Denny Zhou.  Chain of thought prompting elicits reasoning in large language models.  _Conference on Neural Information Processing Systems (NeurIPS)_ , 2022b.  URL https://arxiv.org/abs/2201.11903.
  * Winata et al. (2021) Genta Indra Winata, Andrea Madotto, Zhaojiang Lin, Rosanne Liu, Jason Yosinski, and Pascale Fung.  Language Models are Few-shot Multilingual Learners.  In _Proceedings ofthe 1st Workshop on Multilingual Representation Learning_ , 2021.  URL http://arxiv.org/abs/2109.07684.
  * Xue et al. (2021) Linting Xue, Noah Constant, Adam Roberts, Mihir Kale, Rami Al-Rfou, Aditya Siddhant, Aditya Barua, and Colin Raffel.  mT5: A massively multilingual pre-trained text-to-text transformer.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pp. 483–498, Online, June 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.naacl-main.41.  URL https://aclanthology.org/2021.naacl-main.41.
  * Zhao & Schütze (2021) Mengjie Zhao and Hinrich Schütze.  Discrete and Soft Prompting for Multilingual Models.  In _Proceedings of EMNLP 2021_ , pp. 8547–8555, 2021.  URL http://arxiv.org/abs/2109.03630.

##  Appendix A Details of MGSM Experiments

In this section, we present details of our experiments on MGSM, including the
number of exemplars used for GPT-3 (§A.1) and the detailed prompts in each
setting summarized in Table 2 (§A.2).

###  A.1 Number of Exemplars for Each Language

Given the unbalanced representation of languages in the training corpora, the
byte-pair encoding (BPE; Gage, 1994) algorithm tokenizes sentences in
underrepresented languages, especially those in a different alphabet from
English, into more tokens. Given that the GPT-3 API supports a maximum number
of 2048 tokens as its input, it does not support 6-shot prompting in some
languages, including Russian, Chinese, Japanese, Thai, Telugu and Bengali;
therefore, we use the maximum possible number of exemplars (Table 7) instead
for GPT-3, while using 6-shot for all languages in PaLM experiments.

| en | de | fr | es | ru | zh | ja | th | te | bn | sw
---|---|---|---|---|---|---|---|---|---|---|---
# Exemplars | 6 | 6 | 6 | 6 | 1 | 5 | 4 | 1 | 1 | 1 | 6
Table 7: Number of few-shot exemplars for GPT-3 experiments in Table 3.

###  A.2 MGSM Prompts in Each Setting

We present the prompts used in our MGSM experiments in Figures 6, 7 and 8,
where the Translate-EN experiments can be viewed as a English one with EN-CoT
and English-Exemplars.

Figure 6: Prompt template in the direct answer prediction setting (Direct),
solving a problem in German. Above dotted lines: few-shot exemplars; below
dotted lines: the question of interest and the expected answer. The dotted
lines are not included in our experiments. Figure 7: Prompt template in the
English CoT setting (EN-CoT), solving a problem in German. Above dotted lines:
few-shot exemplars; below dotted lines: the question of interest and the
expected answer. The dotted lines are not included in our experiments.  Figure
8: Prompt template with CoT in the question language (Native-CoT), solving a
problem in German. Above dotted lines: few-shot exemplars; below dotted lines:
the question of interest and the expected answer. The dotted lines are not
included in our experiments.

##  Appendix B Detailed MGSM Performance

| avg | hrl | lrl | en | de | fr | es | ru | zh | ja | th | te | bn | sw
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Lang, freq. (%) | - | - | - | 78.0 | 3.5 | 3.3 | 2.1 | 0.53 | 0.40 | 0.38 | 0.04 | 0.02 | 0.006 | 0.005
PaLM |  |  |  |  |  |  |  |  |  |  |  |  |  |
Exemplar token length (avg.) | 95 | 108 | 119 | 105 | 113 | 118 | 118 | 193 | 199 | 173 | 130
Native-CoT |  |  |  |  |  |  |  |  |  |  |  |  |  |
\- 8B 6-shot | 4.0 | 4.1 | 3.1 | 6.4 | 6.8 | 4.4 | 2.4 | 2.8 | 4.0 | 4.4 | 3.2 | 3.6 | 3.2 | 2.4
\- 62B 6-shot | 20.0 | 22.7 | 13.2 | 30.4 | 24.0 | 24.0 | 26.0 | 22.8 | 24.8 | 14.8 | 18.0 | 11.6 | 13.6 | 9.6
\- 540B 1-shot | 38.9 | 39.7 | 34.8 | 50.8 | 42.8 | 44.8 | 44.8 | 41.2 | 34.8 | 29.6 | 40.0 | 38.0 | 34.0 | 27.2
\- 540B 2-shot | 43.7 | 44.0 | 39.8 | 57.2 | 47.2 | 43.2 | 50.4 | 44.4 | 44.4 | 34.4 | 47.2 | 38.0 | 40.8 | 33.2
\- 540B 4-shot | 45.1 | 45.5 | 41.0 | 58.8 | 44.8 | 49.6 | 47.6 | 46.4 | 46.4 | 38.4 | 46.4 | 41.2 | 44.4 | 32.0
\- 540B 6-shot | 48.1 | 47.9 | 44.9 | 62.4 | 49.2 | 46.4 | 56.8 | 48.4 | 46.8 | 40.0 | 52.8 | 45.6 | 46.0 | 35.2
Table 8: Detailed performances corresponding to Figures 5 and 5.

We report the detailed numbers in our analysis (Figures 5 and 5) in Table 8.

##  Appendix C The Chain-of-Thought Prompts Used in the Paper

In this section, we present the details of the chain-of-thought prompts used
in our paper for the XCOPA (Figure 9) and the XL-WiC (Figures 10 and 11)
tasks.

Figure 9: The chain-of-thought prompt used in the XCOPA experiments. The four
examples are randomly selected from the validation sets of Turkish (tr),
Mandarin Chinese (zh), Tamil (ta), and Cusco-Collao Quechua (qu). The
rationales are written by the authors, and the task description is taken
directly from (Ponti et al., 2020). Under the direct prompting setup, the
answers (bolded) are given directly and rationales are entirely omitted.

Figure 10: The multilingual chain-of-thought prompt used in the XL-WiC
experiments.

Figure 11: The English-language chain-of-thought prompt used in the XL-WiC
experiments.


# Near-sunflowers and focal families

Noga Alon111Department of Mathematics, Princeton University, Princeton, NJ
08544, USA and Schools of Mathematics and Computer Science, Tel Aviv
University, Tel Aviv 69978, Israel. Email<EMAIL_ADDRESS>Research supported
in part by NSF grant DMS-1855464, ISF grant 281/17, BSF grant 2018267 and the
Simons Foundation. Ron Holzman222Department of Mathematics, Technion – Israel
Institute of Technology, Technion City, Haifa 3200003, Israel. Email:
<EMAIL_ADDRESS>Research done during a visit at the Department of
Mathematics, Princeton University, supported by the H2020-MSCA-RISE project
CoSP–GA No. 823748.

###### Abstract

We present some problems and results about variants of sunflowers in families
of sets. In particular, we improve an upper bound of the first author, Körner
and Monti on the maximum number of binary vectors of length $n$ so that every
four of them are split into two pairs by some coordinate. We also propose a
weaker version of the Erdős-Rado sunflower conjecture.

##  1 Introduction

Introduced by Erdős and Rado [10], sunflowers (also called strong
$\Delta$-systems) have a long history of study and applications in extremal
combinatorics and theoretical computer science. Recall that a family
$\mathcal{H}$ of $r$ distinct subsets of $[n]=\\{1,2,\ldots,n\\}$ is called a
_sunflower_ of size $r$ if every $i\in[n]$ belongs to either $0$, $1$ or $r$
of the sets in $\mathcal{H}$.

Erdős and Rado famously conjectured that if $\mathcal{F}$ is a $k$-uniform
family of sets (i.e., $|A|=k$ for every $A\in\mathcal{F}$) not containing a
sunflower of size $r$, then $|\mathcal{F}|\leq C^{k}$, where $C$ is a constant
depending only on $r$. For many years, the best known upper bound was close to
$k!$ for any fixed $r$. A recent breakthrough due to Alweiss, Lovett, Wu and
Zhang [3] improved the bound to $(\log k)^{(1+o(1))k}$ for any fixed $r$, but
the original conjecture is still open even for $r=3$.

Seeking a bound that depends on the size $n$ of the ground set rather than the
uniformity $k$, Erdős and Szemerédi [11] conjectured that if $\mathcal{F}$ is
a family of subsets of $[n]$ not containing a sunflower of size $r$, then
$|\mathcal{F}|\leq c^{n}$, where $c<2$ is a constant depending only on $r$.
They showed (implicitly, made explicit by Deuber et al. [6]) that their
conjecture would follow from the Erdős-Rado conjecture. The recent solution by
Ellenberg and Gijswijt [8] of the cap set problem, confirmed the $r=3$ case of
the Erdős-Szemerédi conjecture (via a reduction due to the first author,
Shpilka and Umans [2]); see also Naslund and Sawin [17] and Hegedűs [12] for
explicit bounds. But the conjecture is still open for $r\geq 4$.

In this paper we introduce a weaker variant of sunflowers.

######  Definition 1.1.

A family $\mathcal{H}$ of $r$ distinct subsets of $[n]$ is called a _near-
sunflower_ of size $r$ if every $i\in[n]$ belongs to either $0$, $1$, $r-1$ or
$r$ of the sets in $\mathcal{H}$.

The weakening consists in adding the option of belonging to $r-1$ of the sets
(this renders the property interesting only for $r\geq 4$). It is natural in
that it makes the property symmetric: if $\mathcal{H}$ is a near-sunflower
then so is $\\{[n]\setminus A:\,A\in\mathcal{H}\\}$. One may hope that when
sunflowers are replaced by near-sunflowers, the notoriously difficult
conjectures of Erdős-Rado and Erdős-Szemerédi will become easier. We show that
this is indeed the case in the Erdős-Szemerédi setting (bound depending on
$n$), but leave the question in the Erdős-Rado setting (bound depending on
$k$) open.

The following variant of near-sunflowers, in which one member of the family
plays a distinguished role, will be of interest. It is convenient to define it
for binary vectors of length $n$ instead of subsets of $[n]$ – henceforth we
will pass freely between these two equivalent formalisms.

######  Definition 1.2.

A family $x^{(0)},x^{(1)},\ldots,x^{(r-1)}$ of $r$ distinct vectors in
$\\{0,1\\}^{n}$ is _focal_ with focus $x^{(0)}$ if for every coordinate
$i\in[n]$ at least $r-2$ of the $r-1$ entries
$x^{(1)}_{i},\ldots,x^{(r-1)}_{i}$ are equal to $x^{(0)}_{i}$.

Thus, a focal family is a near-sunflower with the additional property that one
of the vectors – the focus – is always in the majority. Unlike near-
sunflowers, focal families are interesting already for $r=3$. While sunflowers
and focal families are both special kinds of near-sunflowers, they are not
logically comparable to each other.

The two extremal functions corresponding to our definitions are:

$\displaystyle g^{\mathrm{ns}}_{r}(n)$ $\displaystyle=$
$\displaystyle\max\\{|\mathcal{F}|:\,\mathcal{F}\subseteq\\{0,1\\}^{n}\textrm{
contains no near-sunflower of size }r\\}$ $\displaystyle
g^{\mathrm{ff}}_{r}(n)$ $\displaystyle=$
$\displaystyle\max\\{|\mathcal{F}|:\,\mathcal{F}\subseteq\\{0,1\\}^{n}\textrm{
contains no focal family of size }r\\}$

It follows from the definitions that $g^{\mathrm{ns}}_{r}(n)\leq
g^{\mathrm{ff}}_{r}(n)$. Our main result gives upper and lower bounds for
these functions.

######  Theorem 1.3.

For $r\geq 3$ we have:

  * (a)

$g^{\mathrm{ns}}_{r}(n)\leq
g^{\mathrm{ff}}_{r}(n)\leq(r-1)2^{\lceil\frac{(r-2)n}{r-1}\rceil}$.

  * (b)

There exist positive constants $c^{\mathrm{ns}}_{r}$ and $c^{\mathrm{ff}}_{r}$
so that

$\displaystyle g^{\mathrm{ns}}_{r}(n)$ $\displaystyle\geq$ $\displaystyle
c^{\mathrm{ns}}_{r}(\frac{2}{(r+1)^{\frac{1}{r-1}}})^{n},$ $\displaystyle
g^{\mathrm{ff}}_{r}(n)$ $\displaystyle\geq$ $\displaystyle
c^{\mathrm{ff}}_{r}(\frac{2}{r^{\frac{1}{r-1}}})^{n}.$

In particular, for $r=4$, our bounds (ignoring constants) are
$2^{\frac{2n}{3}}$ from above and $(\frac{8}{5})^{\frac{n}{3}}$ and
$2^{\frac{n}{3}}$ from below, for near-sunflowers and focal families,
respectively. Families without near-sunflowers of size $4$ were previously
studied (with different terminology) by the first author, Körner and Monti
[1], settling a problem suggested by Sós in the late 80’s. While their lower
bound was the same as ours, their upper bound was roughly $2^{0.773n}$, with a
proof based on Sauer’s lemma. It is remarkable that our short and elementary
proof improves their bound. We note that they also extended their result to
$r>4$, but with a different definition. Whereas our near-sunflowers allow an
element to belong to $0$, $1$, $r-1$ or $r$ of the sets, their definition
allows everything except one forbidden value.

We also remark that a concept analogous to our focal families, where instead
of requiring “at least $r-2$” in Definition 1.2 one requires “at least $1$,”
was studied in coding theory under the names separating codes (Cohen and
Schaathun [5]) and frameproof codes (Blackburn [4]). This case is somewhat
simpler and the bounds obtained in those papers coincide with ours for the
special case $r=3$.

More generally, our paper follows a long line of literature in extremal
combinatorics, information theory and coding theory. The common thread is
bounding the largest possible cardinality of a family of vectors of length
$n$, so that for any $r$ of them there exist coordinates displaying certain
desirable patterns. For $r=2$, Sperner’s [18] classical theorem on antichains
is a prime example. For $r=3$ we mention the theorem of Erdős, Frankl and
Füredi [9] on families in which no set is covered by the union of two others;
the problem of cancellative families solved by Tolhuizen [19]; and a variety
of related problems described by Körner [13]. For $r=4$ there is Lindström’s
[15] theorem on determining two vectors from their sum modulo $2$, and Körner
and Simonyi’s [14] bounds for two-different quadruples. For general $r$, we
refer to the study of disjunctive codes (Dyachkov and Rykov [7]). In all of
these problems, and many others, the cardinality of the largest family grows
exponentially in $n$, but (with few exceptions) the asymptotic growth rate is
not known. Our problems are no exception.

The proof of Theorem 1.3 is given in the next section. In Section 3 we adapt
the definition and the bounds for focal families to vectors over larger
alphabets, noting that the upper bound becomes essentially tight when the size
of the alphabet exceeds $n$. We show in Section 4 that the upper bound in
Theorem 1.3 can be improved if the family of vectors is closed under addition
modulo $2$ (i.e., forms a linear code). In Section 5 we consider one-sided
focal families, where $0$ and $1$ entries are treated asymmetrically, and
obtain corresponding bounds. Finally, in Section 6 we discuss the challenge of
obtaining an exponential upper bound in terms of the uniformity $k$, and prove
such a bound under a stronger condition.

##  2 Proof of Theorem 1.3

### The upper bound.

Let $\mathcal{F}\subseteq\\{0,1\\}^{n}$ have cardinality
$|\mathcal{F}|>(r-1)2^{\lceil\frac{(r-2)n}{r-1}\rceil}$. We have to show that
$\mathcal{F}$ contains a focal family of size $r$. Fix a partition
$A_{1},\ldots,A_{r-1}$ of $[n]$ into $r-1$ parts of size
$|A_{j}|\geq\lfloor\frac{n}{r-1}\rfloor$ each. For a subset $S\subseteq[r-1]$
with $|S|=r-2$, say that a vector $x\in\mathcal{F}$ is $S$-_unique_ if there
is no other vector in $\mathcal{F}$ with the same projection on $\bigcup_{j\in
S}A_{j}$. Since $|\bigcup_{j\in S}A_{j}|\leq\lceil\frac{(r-2)n}{r-1}\rceil$,
for a given $S$ the number of $S$-unique vectors in $\mathcal{F}$ is at most
$2^{\lceil\frac{(r-2)n}{r-1}\rceil}$. It follows from our assumption on
$|\mathcal{F}|$ that there exists a vector $x^{(0)}\in\mathcal{F}$ which is
not $S$-unique for any $S\subseteq[r-1]$ with $|S|=r-2$. This means that we
can find vectors
$x^{(1)},\ldots,x^{(r-1)}\in\mathcal{F}\setminus\\{x^{(0)}\\}$ so that each
$x^{(j)}$ agrees with $x^{(0)}$ except possibly on coordinates in $A_{j}$.
Note that $x^{(1)},\ldots,x^{(r-1)}$ are pairwise distinct, because if two of
them were equal they would have to coincide with $x^{(0)}$. By construction,
the subfamily $x^{(0)},x^{(1)},\ldots,x^{(r-1)}$ is focal with focus
$x^{(0)}$.

### The lower bounds.

As is common in such problems, we use random choice with alterations. We
describe the argument for near-sunflowers, later pointing out how to adapt it
to focal families.

We start by forming a random family $\mathcal{G}\subseteq\\{0,1\\}^{n}$ to
which each vector $x\in\\{0,1\\}^{n}$ belongs, independently, with probability
$p$ (to be determined later). Then $\mathbb{E}(|\mathcal{G}|)=2^{n}p$. Let
$N_{\mathcal{G}}$ be a random variable counting the number of near-sunflowers
of size $r$ contained in $\mathcal{G}$. By removing at most $N_{\mathcal{G}}$
vectors from $\mathcal{G}$, we obtain a family $\mathcal{F}$ of cardinality at
least $|\mathcal{G}|-N_{\mathcal{G}}$ which contains no near-sunflower of size
$r$. By linearity of expectation, $\mathbb{E}(|\mathcal{F}|)\geq
2^{n}p-N^{\mathrm{ns}}_{r}p^{r}$, where $N^{\mathrm{ns}}_{r}$ is the number of
near-sunflowers of size $r$ in $\\{0,1\\}^{n}$.

To estimate $N^{\mathrm{ns}}_{r}$, note that the number of $r\times n$ binary
matrices so that the number of $1$ entries in each column is $0$, $1$, $r-1$
or $r$ is $(2r+2)^{n}$. Since near-sunflowers correspond to such matrices with
distinct rows, and the order of the rows is immaterial, it follows that
$N^{\mathrm{ns}}_{r}\leq\frac{1}{r!}(2r+2)^{n}$. Thus,

$\mathbb{E}(|\mathcal{F}|)\geq 2^{n}p-\frac{1}{r!}(2r+2)^{n}p^{r},$

and choosing $p=c(\frac{1}{(r+1)^{\frac{1}{r-1}}})^{n}$ for a suitable
$c=c(r)>0$ yields $\mathbb{E}(|\mathcal{F}|)\geq
c^{\mathrm{ns}}_{r}(\frac{2}{(r+1)^{\frac{1}{r-1}}})^{n}$ for some
$c^{\mathrm{ns}}_{r}>0$. Hence, there is a realization of $\mathcal{F}$ having
at least this cardinality.

Moving to focal families, the argument is similar, but now we have to estimate
the number $N^{\mathrm{ff}}_{r}$ of focal families of size $r$ in
$\\{0,1\\}^{n}$. The number of $r\times n$ binary matrices so that in each
column the first entry is repeated at least $r-2$ times among the other
entries is $(2r)^{n}$. Since focal families correspond to such matrices with
distinct rows, and the order of the last $r-1$ rows is immaterial, it follows
that $N^{\mathrm{ff}}_{r}\leq\frac{1}{(r-1)!}(2r)^{n}$. Thus,

$\mathbb{E}(|\mathcal{F}|)\geq 2^{n}p-\frac{1}{(r-1)!}(2r)^{n}p^{r},$

and choosing $p=c(\frac{1}{r^{\frac{1}{r-1}}})^{n}$ for a suitable $c=c(r)>0$
yields $\mathbb{E}(|\mathcal{F}|)\geq
c^{\mathrm{ff}}_{r}(\frac{2}{r^{\frac{1}{r-1}}})^{n}$ for some
$c^{\mathrm{ff}}_{r}>0$, as required. $\square$

##  3 Focal families over larger alphabets

Given any integer $q\geq 2$, Definition 1.2 can be applied verbatim to vectors
in $[q]^{n}$ to define $q$-ary focal families. Let
$g^{q\textrm{-}\mathrm{ff}}_{r}(n)$ be the corresponding extremal function. A
straightforward adaptation of the proof above yields the following version of
Theorem 1.3 for $q$-ary focal families.

######  Theorem 3.1.

For $q\geq 2$ and $r\geq 3$ we have

$c^{q\textrm{-}\mathrm{ff}}_{r}(\frac{q}{((q-1)(r-1)+1)^{\frac{1}{r-1}}})^{n}\leq
g^{q\textrm{-}\mathrm{ff}}_{r}(n)\leq(r-1)q^{\lceil\frac{(r-2)n}{r-1}\rceil}$

for some positive constant $c^{q\textrm{-}\mathrm{ff}}_{r}$.

When $q\geq n$ and $q$ is a prime power, we can replace the probabilistic
lower bound by a constructive one which matches (up to a constant factor
depending on $r$) the upper bound.

######  Proposition 3.2.

If $q\geq n$ and $q$ is a prime power then

$g^{q\textrm{-}\mathrm{ff}}_{r}(n)\geq q^{\lceil\frac{(r-2)n}{r-1}\rceil}.$

###### Proof.

The Reed-Solomon code with suitable parameters gives the desired lower bound.
For completeness, we describe the construction. We identify the elements of
the finite field $\mathbb{F}_{q}$ with the $q$ symbols in our alphabet. We
choose and fix $n$ distinct elements
$a_{1},a_{2},\ldots,a_{n}\in\mathbb{F}_{q}$, and identify them with the
coordinates $1,2,\ldots,n$. There are $q^{\lceil\frac{(r-2)n}{r-1}\rceil}$
polynomials $p(x)$ of degree less than $\lceil\frac{(r-2)n}{r-1}\rceil$ over
$\mathbb{F}_{q}$. With every such polynomial we associate the vector
$(p(a_{1}),p(a_{2}),\ldots,p(a_{n}))$, which gives a family $\mathcal{F}$ of
$q$-ary vectors of length $n$, with
$|\mathcal{F}|=q^{\lceil\frac{(r-2)n}{r-1}\rceil}$.

We claim that $\mathcal{F}$ contains no focal family of size $r$. Indeed,
suppose that $x^{(0)},x^{(1)},\ldots,x^{(r-1)}\in\mathcal{F}$ form such a
family with focus $x^{(0)}$. Then by the pigeonhole principle, some $x^{(j)}$,
$j\in[r-1]$, has to agree with $x^{(0)}$ on at least
$\lceil\frac{(r-2)n}{r-1}\rceil$ coordinates. This means that the
corresponding polynomials $p^{(j)}$ and $p^{(0)}$ agree on at least
$\lceil\frac{(r-2)n}{r-1}\rceil$ elements of $\mathbb{F}_{q}$. But this is
impossible, as they are distinct polynomials of degree less than
$\lceil\frac{(r-2)n}{r-1}\rceil$. ∎

##  4 Improved upper bound in the linear case

While Proposition 3.2 shows that our upper bound is essentially tight when
$q\geq n$, we believe that for $q=2$ and large $n$ it is not. To support this
belief, we show here that the upper bound can be significantly improved if we
restrict attention to families of binary vectors which are linear codes (i.e.,
closed under addition modulo $2$). This can be done for any value of $r$, but
for simplicity and concreteness of the bound we do it for $r=4$.

We are going to use a known bound on the tradeoff between cardinality and
minimum Hamming distance in a family $\mathcal{F}$ of binary vectors of length
$n$. Recall that, by the linear programming bound (McEliece, Rodemich, Rumsey
and Welch [16]), if the Hamming distance between any two distinct vectors in
$\mathcal{F}$ is greater than $\delta n$, then

$|\mathcal{F}|\leq 2^{(h(\frac{1}{2}-\sqrt{\delta(1-\delta)})+o(1))n},$

where $h(x)$ is the binary entropy function defined by

$h(x)=-x\log_{2}x-(1-x)\log_{2}(1-x).$

We first prove the following theorem, which does not require linearity.

######  Theorem 4.1.

Let $\mathcal{F}$ be a family of at least $2^{0.44n}$ subsets of $[n]$, where
$n$ is large enough. Then there exist three pairs of distinct sets in
$\mathcal{F}$ such that their symmetric differences $A\bigtriangleup B$,
$C\bigtriangleup D$ and $E\bigtriangleup F$ are pairwise disjoint.

###### Proof.

We apply the above-mentioned bound repeatedly. First, a calculation shows that
for $\delta=0.213$, we have $h(\frac{1}{2}-\sqrt{\delta(1-\delta)})<0.44$. As
$|\mathcal{F}|\geq 2^{0.44n}$ and $n$ is large, the bound implies the
existence of distinct sets $A,B\in\mathcal{F}$ with $|A\bigtriangleup B|\leq
0.213n$. Next, by the pigeonhole principle, we can find at least
$\frac{|\mathcal{F}|}{2^{|A\bigtriangleup B|}}$ sets in $\mathcal{F}$ having
the same intersection with $A\bigtriangleup B$. Let $\mathcal{F}^{\prime}$ be
the family obtained by restricting these sets to $[n]\setminus(A\bigtriangleup
B)$. A calculation shows that for $\delta^{\prime}=0.287$, we have
$h(\frac{1}{2}-\sqrt{\delta^{\prime}(1-\delta^{\prime})})<0.28$. As
$|\mathcal{F}^{\prime}|\geq 2^{0.44n-|A\bigtriangleup
B|}>2^{0.28(n-|A\bigtriangleup B|)}$ and $n$ is large, the bound implies the
existence of distinct sets $C,D\in\mathcal{F}$ such that $(C\bigtriangleup
D)\cap(A\bigtriangleup B)=\emptyset$ and $|C\bigtriangleup D|\leq
0.287(n-|A\bigtriangleup B|)$. Now $|A\bigtriangleup B|+|C\bigtriangleup
D|<0.44n$, and again by the pigeonhole principle we can find two distinct sets
$E,F\in\mathcal{F}$ having the same intersection with $(A\bigtriangleup
B)\cup(C\bigtriangleup D)$, which completes the proof. ∎

######  Corollary 4.2.

Let $\mathcal{F}$ be a linear subspace of $\\{0,1\\}^{n}$ of dimension at
least $0.44n$, where $n$ is large enough. Then $\mathcal{F}$ contains a focal
family of size $4$.

###### Proof.

Viewing $\mathcal{F}$ as a family of subsets of $[n]$, it is closed under
symmetric difference. Hence the theorem yields three pairwise disjoint non-
empty sets $X^{(1)},X^{(2)},X^{(3)}\in\mathcal{F}$. Taking the empty set as
the focus $X^{(0)}$, we obtain a focal family of size $4$. ∎

##  5 One-sided focal families

The requirement defining a focal family may be separated into two one-sided
requirements as follows.

######  Definition 5.1.

Let $b\in\\{0,1\\}$. A family $x^{(0)},x^{(1)},\ldots,x^{(r-1)}$ of $r$
distinct vectors in $\\{0,1\\}^{n}$ is $b$-_focal_ with focus $x^{(0)}$ if for
every coordinate $i\in[n]$ such that $x^{(0)}_{i}=b$, at least $r-2$ of the
$r-1$ entries $x^{(1)}_{i},\ldots,x^{(r-1)}_{i}$ are equal to $b$.

The corresponding extremal functions for $b=0,1$ are:

$g^{b\textrm{-}\mathrm{ff}}_{r}(n)=\max\\{|\mathcal{F}|:\,\mathcal{F}\subseteq\\{0,1\\}^{n}\textrm{
contains no $b$-focal family of size }r\\}$

It will be convenient to study the extremal questions first for $k$-uniform
families. Let ${[n]\choose k}$ be the family of all $k$-element subsets of
$[n]$. For $b=0,1$ let:

$g^{b\textrm{-}\mathrm{ff}}_{r}(n,k)=\max\\{|\mathcal{F}|:\,\mathcal{F}\subseteq{[n]\choose
k}\textrm{ contains no $b$-focal family of size }r\\}$

Since $\mathcal{H}$ is $0$-focal if and only if $\\{[n]\setminus
A:\,A\in\mathcal{H}\\}$ is $1$-focal, we have
$g^{0\textrm{-}\mathrm{ff}}_{r}(n)=g^{1\textrm{-}\mathrm{ff}}_{r}(n)$ and
$g^{0\textrm{-}\mathrm{ff}}_{r}(n,k)=g^{1\textrm{-}\mathrm{ff}}_{r}(n,n-k)$.
So we only need to study these questions for one value of $b$.

######  Theorem 5.2.

For $r\geq 3$ and $0\leq k\leq n$ we have

$g^{1\textrm{-}\mathrm{ff}}_{r}(n,k)\leq(r-1)\frac{{n\choose\lceil\frac{(r-2)k}{r-1}\rceil}}{{k\choose\lceil\frac{(r-2)k}{r-1}\rceil}}.$

###### Proof.

Let $\mathcal{F}$ be a family of $k$-element subsets of $[n]$ containing no
$1$-focal family of size $r$. For a set $A\in\mathcal{F}$, we say that a set
$S$ is an _own-subset_ of $A$ if $S\subseteq A$ and $S\nsubseteq B$ for any
$B\in\mathcal{F}\setminus\\{A\\}$.

Consider an arbitrary $(r-1)$-tuple $A_{1},\ldots,A_{r-1}$ of pairwise
disjoint $\lfloor\frac{k}{r-1}\rfloor$-element subsets of a set
$A\in\mathcal{F}$. If for every $j\in[r-1]$ there exists a set
$B_{j}\in\mathcal{F}\setminus\\{A\\}$ such that $A\setminus A_{j}\subseteq
B_{j}$, then the sets $A,B_{1},\ldots,B_{r-1}$ form a $1$-focal family of size
$r$ with focus $A$, contradicting our assumption on the family $\mathcal{F}$.
Hence there exists $j\in[r-1]$ so that $A\setminus A_{j}$ is an own-subset of
$A$.

We claim that for a fixed set $A\in\mathcal{F}$, the probability that a
uniformly random $\lceil\frac{(r-2)k}{r-1}\rceil$-element subset $S$ of $A$ is
an own-subset is at least $\frac{1}{r-1}$. Indeed, consider the following two-
step random process. First, choose uniformly at random an $(r-1)$-tuple
$A_{1},\ldots,A_{r-1}$ of pairwise disjoint
$\lfloor\frac{k}{r-1}\rfloor$-element subsets of $A$. Second, choose uniformly
at random a value $j\in[r-1]$ and let $S=A\setminus A_{j}$. Clearly, the
resulting $S$ is uniformly distributed over the
$\lceil\frac{(r-2)k}{r-1}\rceil$-element subsets of $A$. Conditional on the
choice in the first step, the argument in the previous paragraph implies that
the probability that $S$ is an own-subset of $A$ is at least $\frac{1}{r-1}$.
As this holds for any outcome of the first step, it also holds
unconditionally.

Thus, with each $A\in\mathcal{F}$ we can associate a family of at least
$\frac{1}{r-1}{k\choose\lceil\frac{(r-2)k}{r-1}\rceil}$ own-subsets of $A$ of
size $\lceil\frac{(r-2)k}{r-1}\rceil$. The disjoint union of these families
over all $A\in\mathcal{F}$ is contained in
${[n]\choose\lceil\frac{(r-2)k}{r-1}\rceil}$, implying that
$|\mathcal{F}|\cdot\frac{1}{r-1}{k\choose\lceil\frac{(r-2)k}{r-1}\rceil}\leq{n\choose\lceil\frac{(r-2)k}{r-1}\rceil}$.
It follows that
$|\mathcal{F}|\leq(r-1)\frac{{n\choose\lceil\frac{(r-2)k}{r-1}\rceil}}{{k\choose\lceil\frac{(r-2)k}{r-1}\rceil}}$,
as claimed. ∎

######  Corollary 5.3.

For $r\geq 3$ and $b=0,1$ we have

$g^{b\textrm{-}\mathrm{ff}}_{r}(n)\leq(r-1)\sum_{k=0}^{n}\frac{{n\choose\lceil\frac{(r-2)k}{r-1}\rceil}}{{k\choose\lceil\frac{(r-2)k}{r-1}\rceil}}=(1+\frac{r-2}{(r-1)^{\frac{r-1}{r-2}}}+o(1))^{n}.$

###### Proof.

As pointed out above, it suffices to treat the case $b=1$. Let $\mathcal{F}$
be a family of subsets of $[n]$ containing no $1$-focal family of size $r$.
Then $|\mathcal{F}|=\sum_{k=0}^{n}|\mathcal{F}\cap{[n]\choose k}|$, and
applying the theorem to the families $\mathcal{F}\cap{[n]\choose k}$ yields
the upper bound in summation form.

To obtain the asymptotic expression for the sum, we first use Stirling’s
formula to approximate ${k\choose\lceil\frac{(r-2)k}{r-1}\rceil}$ up to a
factor of order $\sqrt{k}$ by
$(\frac{(r-1)^{r-1}}{(r-2)^{r-2}})^{\frac{k}{r-1}}$. Plugging this
approximation in the sum gives

$\sum_{k=0}^{n}{n\choose\lceil\frac{(r-2)k}{r-1}\rceil}(\frac{r-2}{(r-1)^{\frac{r-1}{r-2}}})^{\frac{(r-2)k}{r-1}}$

which, by the binomial formula, is
$\Theta((1+\frac{r-2}{(r-1)^{\frac{r-1}{r-2}}})^{n})$. ∎

In the case $r=3$, a $1$-focal family is a triple of distinct sets satisfying
$A\subseteq B\cup C$, and Corollary 5.3 reproduces the bound of
$(\frac{5}{4}+o(1))^{n}$ obtained by Erdős, Frankl and Füredi [9] for the
maximum possible cardinality of families not containing such triples. In the
case $r=4$, a $1$-focal family is a $4$-tuple of distinct sets satisfying
$A\subseteq(B\cup C)\cap(B\cup D)\cap(C\cup D)$, and we get an upper bound of
roughly $2^{0.47n}$ for the corresponding extremal problem.

Lower bounds on the extremal functions $g^{b\textrm{-}\mathrm{ff}}_{r}(n,k)$
and $g^{b\textrm{-}\mathrm{ff}}_{r}(n)$ may be obtained, as above, by random
choice with alterations. Here, however, one should start with a random
subfamily of ${[n]\choose k}$ instead of $\\{0,1\\}^{n}$. Optimizing the
bounds requires rather messy calculations, which we omit.

##  6 Bounds in terms of the set size

We turn our attention now to bounding the cardinality of a family of
$k$-element sets (on a ground set of any size) not containing any near-
sunflower of size $r$. Note that this question does not make sense for focal
families, because we may take arbitrarily many pairwise disjoint $k$-element
sets, avoiding focal families of size $3$. With respect to near-sunflowers,
however, any upper bound on the cardinality of a $k$-uniform family not
containing a sunflower of size $r$ automatically applies to our question, too;
in particular, the recent bound of Alweiss, Lovett, Wu and Zhang [3] of order
$(\log k)^{(1+o(1))k}$. Can this be improved for near-sunflowers?

######  Conjecture 6.1.

Let $r\geq 4$, and let $\mathcal{F}$ be a family of $k$-element sets which
contains no near-sunflower of size $r$. Then $|\mathcal{F}|\leq C^{k}$, where
$C$ is a constant depending only on $r$.

This is a weaker version of the Erdős-Rado sunflower conjecture. In view of
the fame and difficulty of the latter, this weakening may turn out to be a
more accessible goal. But we have not been able to make progress, even for
$r=4$.

We do have an upper bound of the desired exponential form under a stronger
condition. Saying that a $4$-tuple of distinct sets $A,B,C,D$ is not a near-
sunflower can be expressed as follows: there is a way to partition
$\\{A,B,C,D\\}$ into two pairs with intersecting symmetric differences. A
natural strengthening is to require this for every pairing of $A,B,C,D$. Let
$\mathcal{F}$ be a family of sets so that for any (ordered) four distinct sets
$A,B,C,D\in\mathcal{F}$ we have $(A\bigtriangleup B)\cap(C\bigtriangleup
D)\neq\emptyset$. Körner and Simonyi [14] proved that if all sets are subsets
of an $n$-element ground set then $|\mathcal{F}|\leq 1.217^{n}$ for large $n$.
But here we are interested in such families that are $k$-uniform on any ground
set. Fixing $A,B$, the condition implies that any $C$ and $D$ must differ
within $A\bigtriangleup B$, which has at most $2k$ elements, easily giving
$|\mathcal{F}|\leq 2^{2k}$. The following theorem improves this bound.

######  Theorem 6.2.

Let $\mathcal{F}$ be a family of $k$-element sets so that for any (ordered)
four distinct sets $A,B,C,D\in\mathcal{F}$ we have $(A\bigtriangleup
B)\cap(C\bigtriangleup D)\neq\emptyset$. Then $|\mathcal{F}|\leq 2.148^{k}$
for large enough $k$.

###### Proof.

Fix two sets $A,B\in\mathcal{F}$ so that $|A\cap B|=t$ maximizes the
intersection size over all pairs of distinct sets in $\mathcal{F}$.

For any set $E$, denote by $[E]_{t}$ a set which is $E$ itself if $|E|\leq t$,
and otherwise it is an arbitrarily chosen $(t+1)$-element subset of $E$. Let
${A\bigtriangleup B\choose\leq t+1}$ be the family of all subsets of
$A\bigtriangleup B$ of size at most $t+1$. Define a mapping
$f:\mathcal{F}\setminus\\{A,B\\}\to{A\bigtriangleup B\choose\leq t+1}$ by
$f(C)=[C\cap(A\bigtriangleup B)]_{t}$.

We check that $f$ is injective. Let $C$ and $D$ be two distinct sets in
$\mathcal{F}\setminus\\{A,B\\}$. We have to show that $[C\cap(A\bigtriangleup
B)]_{t}\neq[D\cap(A\bigtriangleup B)]_{t}$. If the sets on both sides have
size at most $t$, then $C\cap(A\bigtriangleup B)\neq D\cap(A\bigtriangleup B)$
follows from $(A\bigtriangleup B)\cap(C\bigtriangleup D)\neq\emptyset$. If
both $[C\cap(A\bigtriangleup B)]_{t}$ and $[D\cap(A\bigtriangleup B)]_{t}$
have size $t+1$, they cannot be equal since that would imply $|C\cap D|\geq
t+1$, contradicting the maximality of $t$. Finally, if one of them has size at
most $t$ and the other has size $t+1$, they are obviously not equal. This
implies that

$|\mathcal{F}|-2\leq\sum_{j=0}^{t+1}{2(k-t)\choose j}.$

For large $k$, we want to bound the right-hand side from above by $C^{k}$ for
some $C<2.148$. Let us write $x=\frac{t}{2(k-t)}$. If $x\geq\frac{1}{2}$ then
$2(k-t)\leq k$ and the sum is bounded by $2^{k}$. Thus we may assume that
$x<\frac{1}{2}$ and approximate the sum by
$2^{2(k-t)h(x)}=2^{\frac{2h(x)}{1+2x}k}$, where $h(x)$ is the binary entropy
function. Routine calculations show that the maximum of
$2^{\frac{2h(x)}{1+2x}}$ is attained when $x=(1-x)^{3}$ and its value is less
than $2.148$. ∎

As in all these problems, the probabilistic method can be used to show the
existence of a $k$-uniform family $\mathcal{F}$ with pairwise intersecting
symmetric differences, so that $|\mathcal{F}|$ is exponential in $k$. Our
argument gives $|\mathcal{F}|\approx 1.25^{k}$, we omit the details.

## References

  * [1] Noga Alon, János Körner, and Angelo Monti.  String quartets in binary.  Combin. Probab. Comput., 9(5):381–390, 2000.
  * [2] Noga Alon, Amir Shpilka, and Christopher Umans.  On sunflowers and matrix multiplication.  In 2012 IEEE 27th Conference on Computational Complexity—CCC 2012, pages 214–223. IEEE Computer Soc., Los Alamitos, CA, 2012.
  * [3] Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang.  Improved bounds for the sunflower lemma.  arXiv preprint 1908.08483, 2019.
  * [4] Simon R. Blackburn.  Frameproof codes.  SIAM J. Discrete Math., 16(3):499–510, 2003.
  * [5] G. D. Cohen and H. G. Schaathun.  New upper bounds on separating codes.  In Proc. 2003 Int. Conf. Telecommunications, pages 1990–1994. 2003.
  * [6] W. A. Deuber, P. Erdős, D. S. Gunderson, A. V. Kostochka, and A. G. Meyer.  Intersection statements for systems of sets.  J. Combin. Theory Ser. A, 79(1):118–132, 1997.
  * [7] A. G. Dyachkov and V. V. Rykov.  Bounds on the length of disjunctive codes.  Problemy Peredachi Informatsii, 18(3):7–13, 1982.
  * [8] Jordan S. Ellenberg and Dion Gijswijt.  On large subsets of $\mathbb{F}^{n}_{q}$ with no three-term arithmetic progression.  Ann. of Math. (2), 185(1):339–343, 2017.
  * [9] P. Erdős, P. Frankl, and Z. Füredi.  Families of finite sets in which no set is covered by the union of two others.  J. Combin. Theory Ser. A, 33(2):158–166, 1982.
  * [10] P. Erdős and R. Rado.  Intersection theorems for systems of sets.  J. London Math. Soc., 35:85–90, 1960.
  * [11] P. Erdős and E. Szemerédi.  Combinatorial properties of systems of sets.  J. Combinatorial Theory Ser. A, 24(3):308–313, 1978.
  * [12] G. Hegedűs.  An improved upper bound for the size of a sunflower-free family.  Acta Math. Hungar., 155(2):431–438, 2018.
  * [13] János Körner.  On the extremal combinatorics of the Hamming space.  J. Combin. Theory Ser. A, 71(1):112–126, 1995.
  * [14] János Körner and Gábor Simonyi.  Separating partition systems and locally different sequences.  SIAM J. Discrete Math., 1(3):355–359, 1988.
  * [15] Bernt Lindström.  Determination of two vectors from the sum.  J. Combinatorial Theory, 6:402–407, 1969.
  * [16] Robert J. McEliece, Eugene R. Rodemich, Howard Rumsey, Jr., and Lloyd R. Welch.  New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities.  IEEE Trans. Inform. Theory, IT-23(2):157–166, 1977.
  * [17] Eric Naslund and Will Sawin.  Upper bounds for sunflower-free sets.  Forum Math. Sigma, 5:Paper No. e15, 10, 2017.
  * [18] Emanuel Sperner.  Ein Satz über Untermengen einer endlichen Menge.  Math. Z., 27(1):544–548, 1928.
  * [19] Ludo M. Tolhuizen.  New rate pairs in the zero-error capacity region of the binary multiplying channel without feedback.  IEEE Trans. Inform. Theory, IT-46(3):1043–1046, 2000.