# Lil-Bevo: Explorations of Strategies for Training
Language Models in More Humanlike Ways

Venkata S Govindarajan\Bat Juan Diego Rodriguez📠 Kaj Bostrom📠 Kyle
Mahowald\Bat
\BatDepartment of Linguistics 📠Department of Computer Science
The University of Texas at Austin
<EMAIL_ADDRESS>

###### Abstract

We present Lil-Bevo, our submission to the BabyLM Challenge. We pretrained our
masked language models with three ingredients: an initial pretraining with
music data, training on shorter sequences before training on longer ones, and
masking specific tokens to target some of the BLiMP subtasks. Overall, our
baseline models performed above chance, but far below the performance levels
of larger LLMs trained on more data. We found that training on short sequences
performed better than training on longer sequences. Pretraining on music may
help performance marginally, but, if so, the effect seems small. Our targeted
Masked Language Modeling augmentation did not seem to improve model
performance in general, but did seem to help on some of the specific BLiMP
tasks that we were targeting (e.g., Negative Polarity Items). Training
performant LLMs on small amounts of data is a difficult but potentially
informative task. While some of our techniques showed some promise, more work
is needed to explore whether they can improve performance more than the modest
gains here. Our code and models are available
online.111https://github.com/venkatasg/Lil-Bevo.

##  1 Introduction

Large Language Models (LLMs) generate complex and largely grammatical strings
and display impressive performance with structures traditionally thought to
require abstract and hierarchical syntax (Linzen et al., 2016; Linzen and
Baroni, 2021; Wilcox et al., 2022; Futrell and Levy, 2019). They have achieved
human-like performance at a wide range of natural language tasks (Bubeck et
al., 2023; Frank, 2023), particularly those having to do with linguistic form
(Mahowald et al., 2023). This state of affairs has led to claims that such
models should be taken seriously as cognitive models of human language
(Piantadosi, 2023; Baroni, 2022; Frank, 2023), in line with claims from the
neuroscience literature to “take mechanistic abstraction seriously” (Cao and
Yamins, 2021).

One reason that has been posited not to take LLMs seriously as cognitive
models, though, is the immense amount of data they are trained on relative to
what a human child is exposed to (Warstadt and Bowman, 2022; van Schijndel et
al., 2019). Thus, it is possible that models memorize more than humans do and,
relative to humans, over-rely on statistical heuristics and memorized chunks
of language (Bender et al., 2021).

On the other hand, the quality of data that LLMs get during pretraining is, in
many ways, much worse than what human learners get. Children get richly
structured, interactive, multimodal input, tailored to their specific
interests and needs. A baby might reach for a cup of water and be told “Water.
You want some water?” Given that babies are known to conduct repeated
experiments to learn about the world (Gopnik et al., 1999), the baby might try
this again and again until mastering the concept of what water is. An LLM,
meanwhile, might begin learning language by being asked to predict random
tokens in the Wikipedia article on quantum mechanics.

In this paper, we describe our experiments with Lil-Bevo, a small language
model trained on human-scale data for the BabyLM competition (Warstadt et al.,
2023). The goal of the competition is to train a performant LM on a human-
scale amount of data: 10M words for the small track, 100M for the larger
track. We submitted to both strict tracks — however, we were notified through
the meta-review that our models qualify only for the loose track due to the
usage of additional non-linguistic data (music from the MAESTRO dataset
(Hawthorne et al., 2019)). The evaluation is on a set of natural language
tasks including grammatical acceptability judgments via minimal pairs in the
BLiMP benchmark (Warstadt et al., 2020a), language understanding tasks in
SuperGLUE (Wang et al., 2019), and MSGS (the Mixed Signals Generalization Set)
(Warstadt et al., 2020b)

We started with a baseline DeBERTa model, trained from scratch on BabyLM data
using a custom unigram SentencePiece tokenizer (Kudo and Richardson, 2018).
Our strategy was not focused on the architecture, but on ways in which we
could adjust the training regime to improve performance above the baseline.

Specifically, our strategy targets 3 ways in which typical LLM training
regimes lead to lower-quality data than humans have access to. Here, we
describe those strategies and their motivation. We give detailed methods in
Section 2 and then present results, including a number of ablation studies
that attempt to partition out what strategies were successful.

We treated these studies as proof-of-concept and did not exhaustively test
these strategies. Thus, we think that there is still room for improvement.

#### Training on Short Sequences

Unlike LLMs, babies do not start language by learning long complicated
sequences all at once. Using databases of child and child-directed speech, it
has been shown that there is some alignment of caretakers to the child’s level
in terms of linguistic complexity such that caregivers talk to younger
children using shorter utterances and longer utterances as they develop
(Schwab and Lew-Williams, 2016; Kunert et al., 2011). To that end, Mueller and
Linzen (2023) showed that training on simpler data first could induce a better
hierarchical bias for learning language. We specifically take inspiration from
Press et al. (2021) who showed that LLMs learn better when trained on shorter
sequences before being trained on longer sequences.

#### Training on Music Before Training on Language

Unlike LLMs, babies are exposed to a wide range of input besides just text.
Before and while learning language, they are also learning to map the visual
world, to navigate the physical world, to process non-linguistic auditory
stimuli, and to engage in a wide variety of cognitive operations. Thus, it is
commonly observed that some of the machinery thought to be language-specific
(e.g., hierarchical structure) might be induced in pre-linguistic infants
through exposure to other kinds of stimuli. Papadimitriou and Jurafsky (2020)
use this idea to show that training language models on structured data (e.g.,
music) can help models learn faster. We use a similar idea, with initial
pretraining on a mix of music (piano performances) and text.

#### Targeted Masked Language Model

The role of child-directed speech in human language learning is controversial
(see Consortium and et. al., 2020, for discussion and a large-scale
replication of infant-directed speech preferences). It is generally agreed
that parents do not correct a child every time they make a grammatical error
(Marcus, 1993), but there is also evidence that social feedback acts as a
signal (Tomasello, 1992) and that parents structure input to be helpful
(Weisleder and Fernald, 2013). When a child says something wrong, a parent
might “recast” the utterance or highlight grammatical features that children
are struggling with (Nicholas et al., 2001). Inspired by this idea, targeting
the BLiMP (Warstadt et al., 2020a) syntactic evaluations as well as more
general tasks, we trained with a targeted MLM objective.

We considered some variations of the idea of learning with some external
feedback that distinguishes correct tokens against corrupted/noisy
replacements. For example, ELECTRA (Clark et al., 2020) consists in learning
to detect tokens which have been replaced by an auxiliary model.
Unfortunately, replaced token detection approaches such as ELECTRA (Clark et
al., 2020) suffer from an inability to learn probability distributions over
the entire vocabulary, and so cannot be used for (pseudo)-likelihood scoring
Salazar et al. (2020). Another related approach is Corrective Language
Modeling (CLM) (Bajaj et al., 2022), in which the model is trained to
correctly replace corrupted tokens; however, it is not clear how to best use
these models for scoring sentences in BLiMP.222Initial experiments with CLM
performed worse than masked language modeling (MLM); we believe this is due to
a mismatch between training and how the pseudo-likelihood scoring is done via
masking.

Given the problems outlined above, we decided to use masked language modeling
(MLM) with targeted masks. The motivation is to make it easier for the model
to learn syntactic phenomena that co-occur frequently with certain words.
Other strategies for selecting masks were used in Sadeq et al. (2022); Gu et
al. (2020); unlike these works, we mask specific words which are essential to
the phenomena in BLiMP. For example, to target the filler-gap dependency
subtask in BLiMP, we go through the original data set and mask every
occurrence of “that” and “what” in the corpus. By focusing on these words, we
anticipate that the model will more quickly learn to score “I know what you
did last summer.” more highly than “I know that you did last summer.”

##  2 Experiments & Methods

We report all experiments and results for Lil-Bevo in this paper, as it
enabled quick prototyping, and because we find similar trends with our larger
model Lil-Bevo-X. Lil-Bevo-X differs from Lil-Bevo in the model used (deberta-
base rather than deberta-small), training data (100M versus 10M), and
vocabulary size. Final results for the Lil-Bevo-X are available on our online
repository.

#### Tokenizer

We trained a unigram SentencePiece tokenizer (Kudo and Richardson, 2018) from
scratch on the BabyLM data combined with the MAESTRO (Hawthorne et al., 2019)
dataset (described in detail below) using the sentencepiece library.
Specifically, we trained a tokenizer with a vocabulary size of 16,640 and
33,280 for Lil-Bevo and Lil-Bevo-X respectively. <mask> and <cls> were
included as control symbols in the vocabulary, along with an end-of-sequence
token (</s>), a pad token (<pad>) and an unknown token (<unk>).

#### Model

We chose to use an encoder-based language model, specifically DeBERTa since
(a) encoder-based language models are known to capture many syntactic and
semantic features in language when pretrained on relatively modest amounts of
data (Zhang et al., 2021), (b) there were a wide variety of off-the-shelf
DeBERTa architectures available on HuggingFace for easy prototyping and use.

We trained the model in three phrases: (1) pretraining on a combination of
music and text for 5 epochs with a sequence length of 64 tokens, (2)
continuing pretraining on text for 50 epochs with a sequence length of 128
tokens, and (3) finally pretraining on text using targeted MLM for 2 epochs
with a sequence length of 512 tokens. Each of these is described in more
detail below.

#### 1\. Music Pretraining

Papadimitriou and Jurafsky (2020) find that pretraining on languages other
than the target language — including music and code — lead to lower
perplexities on target language as compared to random distributions of tokens,
or even Zipfian token distributions. Inspired by this idea, we explored
whether supplementing the 10M linguistic tokens with _non-linguistic_ musical
tokens from the MAESTRO dataset (Hawthorne et al., 2019) could lead to
noticeable improvements in LM learning. The impetus behind pretraining on
music is two-fold: (a) additional training data that nevertheless has
structural biases that could help the model learn structural biases found in
language (b) the model reaching a stable region in parameter space that
enables it to learn desired linguistic properties much faster and/or better.

After several experiments, we found that pretraining on the combined _strict-
small_ and the entire MAESTRO dataset for 5 epochs provided the best results.
We use V3.0.0 of the MAESTRO dataset, which contains 85M tokens using our
custom trained tokenizer. The dataset consists of 200 hours of MIDI piano
recordings, which we convert to text and tokenize with the shared unigram
SentencePiece tokenizer. Our textual representation of MIDI consists of a
chronological sequence of codes describing the channel and key of each note
onset and release event (e.g. c0n71 for ‘note on, channel 0, key 71’)
delimited by spaces and optional codes for time between events (e.g. t18 for
18 MIDI ticks). We chose a short sequence length of 64 tokens for pretraining
inspired by the Shortformer, which we now explain in further detail.

#### 2\. Shortformer

Press et al. (2021) introduce a few innovations to the training regime. In
particular, we focused on their idea of training for shorter sequence lengths
before moving onto longer ones. We used a similar training regime to (Press et
al., 2021), where we started with a training sequence length of 128 for 50
epochs, before moving to a training sequence length of 512. We initially
experimented with training on longer subsequence length for 150 epochs as in
Press et al. (2021), but discovered lower evaluation results on most BLiMP
categories (albeit with some improvements on some categories like Island
Effects and Quantifiers). Results on BLiMP (Warstadt et al., 2020a) and
SuperGLUE (Wang et al., 2019) saturated with as little as 2 epochs — we
believe this is because of the much smaller size of the dataset as compared to
that in (Press et al., 2021), leading to overfitting on the dataset.

#### 3\. Targeted MLM

We specifically masked out words which were essential to some of the BLIMP
subtasks. Some of these, such as quantifier and negation words, are also
important to some of the SuperGLUE tasks (e.g., textual entailment.) For
anaphor agreement, we masked the words “himself”, “herself”, “itself”,
“themselves”. For NPI licensing the masked words included “not”, “often”, and
“probably”333Note that the masked words are not necessarily NPI items
themselves, but rather that they are targets of single word substitutions in
NPI items.. The list of words which were masked in each category are shown in
Table 3 in Appendix A. We used a sequence length of 512 tokens, and
additionally masked other random tokens in order to mask a total of 15% of
tokens per sample.

The total number of words masked for each category across the 10M train set
are given in Table 1.

Category | Total | Avg
---|---|---
S-V agreement | 124197 | 4.3
Animacy | 100206 | 3.5
Quantifiers | 89926 | 3.1
Modal verbs | 58604 | 2.0
NPI licensing | 47484 | 1.6
Filler gap | 34988 | 1.2
D-N agreement | 28675 | 1.0
Adverbs | 19332 | 0.7
Anaphor agreement | 3659 | 0.1
Table 1: Total number of masks and average number of masks per sample for each
targeted category (_S-V agreement_ stands for subject-verb agreement, and _D-N
agreement_ stands for determiner-noun agreement).

The _Animacy_ class consists of animate nouns, and was used to target the
minimal pairs in the _Argument Structure_ category with animate/inanimate
subjects (“Amanda was respected by some _waitresses_.” vs “Amanda was
respected by some picture”). To obtain a list of animate nouns we used all the
lemmas of (direct and indirect) hyponym synsets of _person.n.01_ in WordNet.

In addition to targeting the BLiMP categories of S-V agreement, quantifiers,
NPI licensing, filler gap, argument structure, DN- agreement and anaphor
agreement, we also included some _modal verbs_ (e.g., can, might, shall) and
certain _adverbs_ (e.g., never, maybe, always, perhaps), since these are
important for textual entailment.

###  2.1 Ablations

We compare Lil-Bevo with ablations to explore how important our three
strategies are for final performance. Specifically, we compare Lil-Bevo with
the following:

#### Long-only

Train DeBERTa with a sequence length of 512 tokens for 57 epochs.

#### Short-only

Train DeBERTa with a sequence length of 128 tokens for 57 epochs.

#### Short+target

Train DeBERTa with a sequence length of 128 tokens for 55 epochs. Then train
with targeted MLM for 2 epochs.

#### Music+short

Train DeBERTa on music and text for 5 epochs with a sequence length of 64
tokens. Then continue training on text with a sequence length of 128 tokens
for 52 epochs.

#### Music+short+long

Train DeBERTa on music and text for 5 epochs with a sequence length of 64
tokens. Then continue training on text with a sequence length of 128 tokens
for 50 epochs, followed by training with a sequence length of 512 tokens for 2
epochs.

#### Lil-Bevo (music+short±target)

This is the same as _Music+short+long_ except that the final stage of
pretraining for 2 epochs uses targeted MLM.

#### Implementation

We train all our models using the Trainer API, part of the huggingface python
package. Models are trained using 4 Nvidia A40 GPUs, with the maximum possible
batch size that was permissible with each experiment. Apart from setting
initial learning rate to 6e-4, weight decay to 0.1 and a warmup ratio to
0.0001, we use default training arguments in the API (except for the final
targeted MLM/long stage, where we used all default parameters). Models are
evaluated on the validation split of the BabyLM dataset. We did not use the
test split of the BabyLM data. We release all of the above pretrained models
online on the Huggingface Hub.

##  3 Results

Results for BLiMP, MSGS, SuperGLUE and the supplementary tasks are shown in
Figure 1. The results are color-coded to represent each model’s differences
from the RoBERTa baseline results (obtained from the BabyLM GitHub). We
highlight some results below.

Figure 1: Results for each model, for each task. The color reflects the
difference in score between the given model and the RoBERTa baseline results
released by the organizers of BabyLM.

#### Does pretraining on music help?

Comparing _short-only_ with _music+short_ , we see that pretraining on music
helps slightly on 8 of the 12 BLiMP subtasks, and on two of the 5 supplement
tasks. However, it suffers from a large gap of 9.1 points on _QA Congruence
tricky_. On SuperGLUE, _music+short_ outperforms _short-only_ on 6 of the 11
subtasks, and only slightly. Thus, we do not think there is strong evidence
that pretraining on music improves over the short-only condition, in
isolation.

Comparing _Lil-Bevo_ (music+short+target) with _short+target_ , we see that
_Lil-Bevo_ outperforms _short+target_ on 69% of all tasks. Predicting score
for each task in a mixed-effect linear regression with a fixed effect
predictor for whether the model was _Lil-Bevo_ or _short+target_ , we found
that _Lil-Bevo_ was slightly better ($\beta=1.3$, $\chi^{2}(1)=4.11,p<.05$ by
a likelihood ratio test). So, while music pretraining may help, the effect is
small and inconsistent in our observed data.

#### What is the effect of targeted MLM?

We compare _music+short+long_ with Lil-Bevo (music+short+target) and _short-
only_ with _short+target_ to ascertain whether targeted MLM helps over random
masking. Targeted MLM does not systematically improve performance, except for
two BLiMP tasks: NPI Licensing and Argument Structure. For NPI Licensing, Lil-
Bevo outperforms _music+short+long_ by 14.8 points, and _short+target_
outperforms _short-only_ by 16.2 points. We suspect that this difference could
be meaningful since our Targeted MLM strategy specifically targets NPI terms
that are substituted in BLiMP.

#### The effect of increasing sequence length

When comparing _music+short_ with _music-short-long_ , and _short-only_ with
_long-only_ , we find that pretraining with 512-token sequence lengths
generally underperforms pretraining with 128-token sequence lengths. The
difference between _short-only_ and _long-only_ conditions is quite large in
fact. A linear mixed effect regression comparing the two using the same method
as above found that performance was 1.8 points worse on average for the _long-
only_ method ($\beta=1.8$, $\chi^{2}(1)=14.2,p<.001$ by a likelihood ratio
test). Thus, we believe pretraining with shorter sequences helps significantly
compared to using longer sequences.

##  4 Discussion

Overall, we found that, for BabyLM’s, sequence length matters, music
pretraining may help a little (but may be spurious), and targeted MLM training
may help on specific tasks.

These results are far from exhaustive, and we see a number of areas for future
improvement using these methods. To fully understand the role of initial
pretraining on music, one could construct a series of synthetically-generated
music datasets, with varying degrees of complexity. Would pretraining on music
that is more “language-like” (Lerdahl, 1996) in some sense improve performance
on downstream tasks? Perhaps there is a principled way to interpolate between
music and language, using the same kind of data format (MIDI). At one end of
the spectrum one would have MAESTRO, and at the other end, text that has been
encoded into MIDI events.

Related to the use of varying sequence lengths, future work could consider
improvements in data preprocessing and batching; in particular, knowing the
beginning and ending of coherent chunks of text (e.g., dialogues or documents)
could help improve the model. Beyond this, Mueller and Linzen (2023) provide
some evidence that curriculum learning approaches may be fruitful to improving
low-resource language models.

Finally, a more thorough analysis is needed on when (and by how much) targeted
MLM is able to boost model performance. Other strategies are also possible,
such as combining targeted MLM with information-theoretic strategies for
picking random masks (Sadeq et al., 2022). Beyond MLM, contrastive objectives
could be used to encourage the model to score grammatical sentences more
highly than ungrammatical sentences.

Model | Dynabench score
---|---
Lil-Bevo | 0.64
Music-short-long | 0.64
Music-short | 0.69
Short-only | 0.63
Short-target | 0.62
Long-only | 0.61
Lil-Bevo-X | 0.69
Table 2: Scores on Dynabench for different models.

##  5 Conclusion

A big motivating question for training models on human-scale data is whether
it is possible for models to attain linguistic competence without the massive
amounts of data used to train the massive LLMs that dominate NLP leaderboards.
If so, that would make it more plausible that we should take LLMs seriously as
cognitive models. So can BabyLMs learn like grown-up ones? While we find some
hints of directions to pursue for making small language models learn more from
less, we did not come close to matching LLM performance from larger amounts of
data. Of course, that does not mean it is not possible to do so, and other
teams might have different experiences. We did not fully explore optimizing
all of our methods, and we treated our manipulations largely as proof-of-
concept. Aggregating methods and results from a wider variety of teams will
make it possible to more fully explore these questions.

## References

  * Bajaj et al. (2022) Payal Bajaj, Chenyan Xiong, Guolin Ke, Xiaodong Liu, Di He, Saurabh Tiwary, Tie-Yan Liu, Paul Bennett, Xia Song, and Jianfeng Gao. 2022.  METRO: efficient denoising pretraining of large scale autoencoding language models with model generated signals.  _CoRR_ , abs/2204.06644.
  * Baroni (2022) Marco Baroni. 2022.  On the proper role of linguistically-oriented deep net analysis in linguistic theorizing.  In Shalom Lappin, editor, _Algebraic systems and the representation of linguistic knowledge_ , chapter 1, pages 5–22. Taylor and Francis, Abingdon-on-Thames.
  * Bender et al. (2021) Emily M. Bender, Timnit Gebru, Angelina McMillan-Major, and Shmargaret Shmitchell. 2021.  On the dangers of stochastic parrots: Can language models be too big? In _Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency_ , New York. Association for Computer Machinery – ACM.
  * Bubeck et al. (2023) Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, Harsha Nori, Hamid Palangi, Marco Tulio Ribeiro, and Yi Zhang. 2023.  Sparks of artificial general intelligence: Early experiments with gpt-4.
  * Cao and Yamins (2021) Rosa Cao and Daniel Yamins. 2021.  Explanatory models in neuroscience: Part 1–taking mechanistic abstraction seriously.  _arXiv preprint arXiv:2104.01490_.
  * Clark et al. (2020) Kevin Clark, Minh-Thang Luong, Quoc V. Le, and Christopher D. Manning. 2020.  Electra: Pre-training text encoders as discriminators rather than generators.  In _International Conference on Learning Representations_.
  * Consortium and et. al. (2020) The ManyBabies Consortium and Michael C. Frank et. al. 2020.  Quantifying sources of variability in infancy research using the infant-directed-speech preference.  _Advances in Methods and Practices in Psychological Science_ , 3(1):24–52.
  * Frank (2023) Michael C Frank. 2023.  Large language models as models of human cognition.
  * Futrell and Levy (2019) Richard Futrell and Roger P Levy. 2019.  Do RNNs learn human-like abstract word order preferences? _Proceedings of the Society for Computation in Linguistics_ , 2(1):50–59.
  * Gopnik et al. (1999) Alison Gopnik, Andrew N Meltzoff, and Patricia K Kuhl. 1999.  _The scientist in the crib: Minds, brains, and how children learn._ William Morrow & Co.
  * Gu et al. (2020) Yuxian Gu, Zhengyan Zhang, Xiaozhi Wang, Zhiyuan Liu, and Maosong Sun. 2020.  Train no evil: Selective masking for task-guided pre-training.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6966–6974, Online. Association for Computational Linguistics.
  * Hawthorne et al. (2019) Curtis Hawthorne, Andriy Stasyuk, Adam Roberts, Ian Simon, Cheng-Zhi Anna Huang, Sander Dieleman, Erich Elsen, Jesse Engel, and Douglas Eck. 2019.  Enabling factorized piano music modeling and generation with the MAESTRO dataset.  In _International Conference on Learning Representations_.
  * Kudo and Richardson (2018) Taku Kudo and John Richardson. 2018.  SentencePiece: A simple and language independent subword tokenizer and detokenizer for neural text processing.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 66–71, Brussels, Belgium. Association for Computational Linguistics.
  * Kunert et al. (2011) Richard Kunert, Raquel Fernández, and Willem Zuidema. 2011.  Adaptation in child directed speech: Evidence from corpora.  In _Proceedings of the 15th SemDial Workshop on the Semantics and Pragmatics of Dialogue (Los Angelogue)_ , pages 112–119, Los Angeles, California, USA.
  * Lerdahl (1996) Fred Lerdahl. 1996.  Calculating tonal tension.  _Music Perception: An Interdisciplinary Journal_ , 13(3):319–363.
  * Linzen and Baroni (2021) Tal Linzen and Marco Baroni. 2021.  Syntactic Structure from Deep Learning.  _Annual Review of Linguistics_ , 7(1):195–212.
  * Linzen et al. (2016) Tal Linzen, Emmanuel Dupoux, and Yoav Goldberg. 2016.  Assessing the ability of LSTMs to learn syntax-sensitive dependencies.  _Transactions of the Association for Computational Linguistics_ , 4:521–535.
  * Mahowald et al. (2023) Kyle Mahowald, Anna A. Ivanova, Idan A. Blank, Nancy Kanwisher, Joshua B. Tenenbaum, and Evelina Fedorenko. 2023.  Dissociating language and thought in large language models: a cognitive perspective.
  * Marcus (1993) Gary F. Marcus. 1993.  Negative evidence in language acquisition.  _Cognition_ , 46:53–85.
  * Mueller and Linzen (2023) Aaron Mueller and Tal Linzen. 2023.  How to plant trees in language models: Data and architectural effects on the emergence of syntactic inductive biases.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 11237–11252, Toronto, Canada. Association for Computational Linguistics.
  * Nicholas et al. (2001) Howard Nicholas, Patsy M Lightbown, and Nina Spada. 2001.  Recasts as feedback to language learners.  _Language learning_ , 51(4):719–758.
  * Papadimitriou and Jurafsky (2020) Isabel Papadimitriou and Dan Jurafsky. 2020.  Learning Music Helps You Read: Using transfer to study linguistic structure in language models.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6829–6839, Online. Association for Computational Linguistics.
  * Piantadosi (2023) Steven T Piantadosi. 2023.  Modern language models refute chomsky’s approach to language.  _Lingbuzz Preprint, lingbuzz/007180_.
  * Press et al. (2021) Ofir Press, Noah A. Smith, and Mike Lewis. 2021.  Shortformer: Better language modeling using shorter inputs.  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)_ , pages 5493–5505, Online. Association for Computational Linguistics.
  * Sadeq et al. (2022) Nafis Sadeq, Canwen Xu, and Julian McAuley. 2022.  InforMask: Unsupervised informative masking for language model pretraining.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 5866–5878, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Salazar et al. (2020) Julian Salazar, Davis Liang, Toan Q. Nguyen, and Katrin Kirchhoff. 2020.  Masked language model scoring.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 2699–2712, Online. Association for Computational Linguistics.
  * Schwab and Lew-Williams (2016) Jessica F Schwab and Casey Lew-Williams. 2016.  Language learning, socioeconomic status, and child-directed speech.  _Wiley Interdisciplinary Reviews: Cognitive Science_ , 7(4):264–275.
  * Tomasello (1992) Michael Tomasello. 1992.  The social bases of language acquisition.  _Social Development_ , 1:67–87.
  * van Schijndel et al. (2019) Marten van Schijndel, Aaron Mueller, and Tal Linzen. 2019.  Quantity doesn’t buy quality syntax with neural language models.  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)_ , pages 5831–5837, Hong Kong, China. Association for Computational Linguistics.
  * Wang et al. (2019) Alex Wang, Yada Pruksachatkun, Nikita Nangia, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. 2019.  SuperGLUE: A Stickier Benchmark for General-Purpose Language Understanding Systems.  In _Proceedings of the 33rd International Conference on Neural Information Processing Systems_. Curran Associates Inc., Red Hook, NY, USA.
  * Warstadt and Bowman (2022) Alex Warstadt and Samuel R. Bowman. 2022.  What artificial neural networks can tell us about human language acquisition.
  * Warstadt et al. (2023) Alex Warstadt, Aaron Mueller, Leshem Choshen, Ethan Gotlieb Wilcox, Chengxu Zhuang, Juan Ciro, Rafael Mosquera, Adina Williams, Bhargavi Paranjabe, Tal Linzen, and Ryan Cotterell. 2023.  Findings of the 2023 BabyLM Challenge: Sample-efficient pretraining on developmentally plausible corpora.  In _Proceedings of the 2023 BabyLM Challenge_. Association for Computational Linguistics (ACL).
  * Warstadt et al. (2020a) Alex Warstadt, Alicia Parrish, Haokun Liu, Anhad Mohananey, Wei Peng, Sheng-Fu Wang, and Samuel R. Bowman. 2020a.  BLiMP: The benchmark of linguistic minimal pairs for English.  _Transactions of the Association for Computational Linguistics_ , 8:377–392.
  * Warstadt et al. (2020b) Alex Warstadt, Yian Zhang, Xiaocheng Li, Haokun Liu, and Samuel R. Bowman. 2020b.  Learning which features matter: RoBERTa acquires a preference for linguistic generalizations (eventually).  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 217–235, Online. Association for Computational Linguistics.
  * Weisleder and Fernald (2013) Adriana Weisleder and Anne Fernald. 2013.  Talking to children matters: Early language experience strengthens processing and builds vocabulary.  _Psychological science_ , 24(11):2143–2152.
  * Wilcox et al. (2022) Ethan Gotlieb Wilcox, Richard Futrell, and Roger Levy. 2022.  Using computational models to test syntactic learnability.  _Linguistic Inquiry_ , pages 1–88.
  * Zhang et al. (2021) Yian Zhang, Alex Warstadt, Xiaocheng Li, and Samuel R. Bowman. 2021.  When do you need billions of words of pretraining data? 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)_ , pages 1112–1125, Online. Association for Computational Linguistics.

##  Appendix A Appendix

Table 3 shows the list of words selected for targeted MLM for each linguistic
category, while age of acquisition results are presented in Table 4

Category | Words
---|---
S-V agreement | is, was, have, do, are, don’t, were, has, does, isn’t, doesn’t, wasn’t, haven’t,
aren’t, weren’t, hasn’t
Quantifiers | all, some, more, any, little, many, much, most, every, both, each, few, enough,
several,half, less,either, none,. lots, neither, plenty
Filler gap | that
Modal verbs | can, would, will, could, should, may, must, might, shall
NPI licensing | not, only, also, really, probably, often, certainly, clearly
D-N agreement | this, these
Adverbs | never, always, maybe, probably, perhaps, certainly, absolutely, likely, possibly,
definitely, surely, truly, constantly, forever, potentially, positively,
undoubtedly,
consistently, invariably, eternally, perpetually, dubiously, uncertainly
Anaphor agreement | himself, themselves, itself, herself
Animacy | people, man, men, family, person, father, mother, girl, woman, son, children,
guy, friend, wife, boy, guys, human, member, friends, women, members,
daughter, child, brother, boys, husband, girls, lady, parents, kids, king,
sister, dad,
| mommy, daddy, player, students, doctor, president, captain, kid, mom,
leader,
| officer, director, players, soldiers, teacher, god, student, sir, officers,
judge, patient,
| brothers, families, mark, actor, ladies, singer, uncle, author, manager,
gentleman,
| humans, lad, writer, sweetie, prince, lawyer, artist, mum, host, owner,
guest,
| teachers, princess, scientists, guard, professor, artists, leaders, agent,
assistant,
| patients, mama, workers, minister, boss, sons, criminal, partner, babies,
citizens,
| adult, politician, gods, mayor, actress, principal, cousin, witness, driver,
hero,
| governor, lord, doctors, authorities, maiden, suspect, victims, aunt,
candidate,
| individuals, producer, champion, gentlemen, founder, enemies, sisters,
winner,
| passenger, client, bride, priest, prisoners, pilot, inhabitants, ghost,
chairman,
| nurse, guests, user, pirate, graduate, merchant, cats, victim, passengers,
pirates,
| noble, agents, expert, parent, editor, grandma, officials, subjects, cops,
maid,
| commander, policeman, writers, servants, academic, peasant, eldest,
engineer,
| musician, devil, critics, users, creatures, twin, composer, personality,
lads,
| followers, poet, adults, boyfriend, fellows, actors, ruler, judges, witch,
daughters,
| lieutenant, musicians, servant, secretary, slave, priests, scholars,
prisoner,
| visitors, residents, lover, cop, companion, knight, deputy, customers,
tourist,
| guards, grandfather, journalist, architect, rival, kings, colleagues,
farmers,
| owners, farmer,…
Table 3: Words which were masked in targeted MLM in the 10M train set. For _Animacy_ only words appearing over 100 times are shown in the table. Model | Overall | Nouns | Predicates | Function words
---|---|---|---|---
RoBERTa-baseline | 2.06 | 1.99 | 1.85 | 2.65
Lil-Bevo | 2.06 | 2.0 | 1.84 | 2.65
Lil-Bevo-X | 2.05 | 1.99 | 1.85 | 2.59
Table 4: Age of Acquisiton results


# On odd perfect numbers of special forms

Luis H. Gallardo  Univ. Brest, UMR CNRS 6205
Laboratoire de Mathématiques de Bretagne Atlantique 6, Av. Le Gorgeu, C.S.
93837, Cedex 3, F-29238 Brest
France<EMAIL_ADDRESS>and  Olivier Rahavandrainy  Univ. Brest,
UMR CNRS 6205
Laboratoire de Mathématiques de Bretagne Atlantique 6, Av. Le Gorgeu, C.S.
93837, Cedex 3, F-29238 Brest
France<EMAIL_ADDRESS>
###### Abstract.

We give necessary conditions for perfection of some families of odd numbers
with special multiplicative forms. Extending earlier work of Steuerwald,
Kanold, McDaniel et al.

###### Key words and phrases:

Sums of divisors, odd perfect numbers, cyclotomic polynomials, congruences.

###### 2010 Mathematics Subject Classification:

Primary 11A25; Secondary 11A07

##  1\. Introduction

A number $n$ is perfect if and only if it is equal to the sum of all its
proper divisors. Let $n$ be an odd perfect number. Euler [7] proved

(1) $n=p^{4k+1}c^{2}$

where $p$ is a prime number congruent to $1$ modulo $4$, $k\geq 0$ is a
nonnegative integer and $c>0$ is a positive integer non divisible by $p$. Put
$\alpha=4k+1$, and $c=a_{1}^{e_{1}}\cdots q_{t}^{e_{t}}$ with prime numbers
$q_{1},\ldots,q_{t}$ and positive integers $e_{1},\ldots,e_{t}$. If all $e$’s
are equal we put $\beta=e_{1}=\ldots=e_{t}$, if all but one are equal, we put,
say, $\gamma=e_{2}=\ldots=e_{t}$. If all $e$’s are congruent to $a$ modulo $m$
we write $\delta\equiv e_{1}\ldots\equiv e_{t}\equiv a\pmod{m}$. Put
$g=\gcd(2e_{1}+1,\ldots,2e_{t}+1)$.

Steuerwald [19] proved that $\beta\neq 1$, Kanold [11] proved that $\beta\neq
2$, and that $g^{4}$ divides $n$. He deduced that none of $9,15,21,33$ can
divide $g$. Brauer [1] and Kanold [12] independently proved that
$e_{1}=2,\gamma=1$, is also impossible; see Brauer’s discussion of the two
proofs in [2]. Kanold [13] announced and Kanold [14] proved that when
$\gamma=1$ one has $e_{1}\notin\\{3,4\\}$. Kanold [15] proved that both cases
$e_{1}=e_{2}=2,e_{3}=\ldots=e_{t}=1$ and
$\alpha=5,e_{1}=\ldots=e_{r}=1,e_{r+1}=\ldots=e_{t}=2$ are impossible.
McCarthy [16] proved that $3\nmid n$ and $\delta\equiv 1\pmod{3}$ cannot hold.
He proved also in the same paper that $3\nmid n,\gamma=1$ and $q_{1}\equiv
2\pmod{3}$ is impossible.

McDaniel proved [17] that $\delta\equiv 1\pmod{3}$ cannot hold. Hagis and
McDaniel [9] proved that $\beta\neq 3$ and that ($q_{1}=7,e_{1}=6$ and $7$
divides $e_{2},\ldots,e_{t}$) is impossible. Hagis and McDaniel [10] proved
that $\beta\notin\\{5,12,17,24,62\\}$. Hagis and McDaniel [10] proposed the
still unresolved conjecture that there are no odd perfect numbers with all
$e$’s equal. Cohen and Williams [3] proved that
$\beta\notin\\{6,8,11,14,18\\}$. Thus, all cases of $\beta$ less than $20$ are
resolved. They also proved that for $\gamma=1$ one has $e_{1}\notin\\{5,6\\}$,
extending earlier results.

Recently, Evans and Pearlman [6] proved the two facts: i) $\delta\equiv
32\pmod{65}$ and ii) $7\mid n,\delta\equiv 2\pmod{5}$, are impossible.
Recently also, Gallardo [8] proved that $n$ cannot be a cube.

See also [4, Chapter 1] for a comprehensive survey on this area.

As usual $a\mid\mid b$ means that $a$ divides $b$ (denoted also by $a\mid b$)
and that $\gcd(a,b/a)=1$. For a positive integer $n>0$, we denote by
$\Phi_{n}(x)$ the $n$-th cyclotomic polynomial. We denote by $\sigma(n)$ the
sum of all positive divisors of $n$. We denote by $\omega(n)$ the number of
distinct prime factors of $n$. For a finite set $A$, we denote by $\sharp(A)$
the number of elements of $A$.

The object of this paper is to prove the following two results:

######  Theorem 1.1.

There is no odd perfect number of the form

$n=5^{\alpha}M^{2\beta}$

where $M$ is square-free and $5\nmid M$.

In order to present our second result, we need the following definitions. Let
$\Sigma=\\{p\;\text{prime}\;\colon p\in\\{2,4\\}\pmod{7}$. For any prime
number $x>7$ let $T(x)=\\{q\;\text{prime}\;\colon q\neq
3\;\text{and}\;q\mid\Phi_{3}(x)\\}$. Let $p>7$ be a prime number. We say that
$p$ is _good_ if for some nonnegative integer $n\geq 0$ the set
$S_{n}(p)\cap\Sigma$ is nonempty, where $S_{n}(p)$ is a set recursively
defined by:

  * (a)

$S_{0}(p)=\\{p\\}$.

  * (b)

$S_{n+1}(p)=S_{n}(p)\bigcup_{x\in S_{n}(p)}T(x)$.

Observe that $T(x)$ is not empty, since we claim that there exist no prime
number $x$ such that

(2) $\Phi_{3}(x)=3^{m}$

where $m$ is a positive integer. To prove the claim, reduce both sides of (2)
modulo $3$ to get $x\equiv 1\pmod{3}$. So $x\in\\{1,4,7\\}\pmod{9}$. But $x>1$
so that (2) implies $m>1$. Reduce now both sides of (2) modulo $9$ to get the
contradiction $3\equiv\Phi_{3}(x)\equiv 0\pmod{9}$. This proves the claim.

For example, $x=31$ is good since
$S_{0}(31)=\\{31\\}$,$S_{1}(31)=\\{31,331\\}$ and $331\in S_{1}(31)\cap\Sigma$
since $331\equiv 2\pmod{7}$. A more involved example is the fact that $x=13$
is good; indeed McDaniel’s proof of Lemma 2.3 (in our special case $p=5$) is
essentially the proof that $x=13$ is good:

$S_{0}(13)=\\{13\\},S_{1}(13)=\\{13,61\\},S_{2}(13)=\\{13,61,97\\}$,

$S_{3}(13)=\\{13,61,97,3169\\},S_{4}(13)=\\{13,61,97,3169,3348577\\}$,

$S_{5}(13)=\\{13,61,97,3169,3348577,3737657091169\\}$,

$S_{6}(13)\supseteq R_{6}=\\{13,61,97,3169,3348577,3737657091169,181\\}$,

$S_{7}(13)\supseteq R_{7}=R_{6}\cup\\{79,139\\}$,

and $79\equiv 2\pmod{7}$ so that $S_{7}(13)\cap\Sigma$ is a nonempty set. This
proves the result.

We are now able to establish our second result.

######  Theorem 1.2.

  * (a)

There is no odd perfect number of the form

$n=5^{\alpha}3^{2b}q_{1}^{6k_{1}+2}\cdots q_{t}^{6k_{t}+2}$

where at least one of the primes $5<q_{1}<\cdots<q_{t}$ is good.

  * (b)

There is no perfect number of the form

$n=5^{\alpha}3^{2b}q_{1}^{6k_{1}+2}\cdots q_{t}^{6k_{t}+2}$

where $5<q_{1}$ and at least one of the primes $q_{1}<\cdots<q_{t}$ does not
exceed $157$.

  * (c)

Assuming Conjecture 1.4, there is no odd perfect number of the form

$n=5^{\alpha}3^{2b}q_{1}^{6k_{1}+2}\cdots q_{t}^{6k_{t}+2}$

where $q_{1},\ldots,q_{t}$ are prime numbers exceeding $5$.

Some pairs $(\alpha,b)$ for which the condition on part (a) of Theorem 1.2
holds are described in Proposition 4.1.

######  Proposition 1.3.

All prime numbers $p>7$ and less than $160$ are good.

###### Proof.

Follows from some computer calculations. ∎

######  Conjecture 1.4.

All prime numbers $p>7$ are good.

##  2\. Some tools

Some classical results follow.

######  Lemma 2.1.

[21] There is no odd perfect number with less than $3$ distinct prime
divisors.

######  Lemma 2.2.

[11] There is no odd perfect number $n=p^{\alpha}c^{2}$ where $c$ is square-
free.

######  Lemma 2.3.

[17] There is no odd perfect number $n=p^{\alpha}q_{1}^{2e_{1}}\cdots
q_{t}^{2e_{t}}$ with $e_{1}\equiv e_{2}\equiv\cdots\equiv e_{t}\equiv
1\pmod{3}$.

######  Lemma 2.4.

[18] If $n=p^{\alpha}3^{2\beta}d^{2\beta}$ with square-free $d$ and with
$\gcd(3,d)=1=\gcd(p,d)$ is an odd perfect number then
$\sigma(p^{\alpha})\equiv 0\pmod{3^{2\beta}}$.

######  Lemma 2.5.

[20, footnote on page 590] There is no odd perfect number $n$ divisible by
$105=2\cdot 5\cdot 7$.

For distinct prime numbers $p\neq q$ we denote by $ord_{q}(p)$ the smallest
natural number $d$ for which $p^{d}\equiv 1\pmod{q}$. We denote by $a_{q}(p)$
the integer $e$ such that $q^{e}||p^{d}-1$, where $d=ord_{q}(p)$.

The following lemma appears in Pomerance’s paper [5, Lemma 1].

######  Lemma 2.6.

Suppose that $p,q$ are distinct primes with $q\neq 2$ and $b,c$ are natural
numbers. Then

  * (a)

if $p\equiv 1\pmod{q}$, then $q^{b}||\sigma(p^{c})$ if and only if
$q^{b}||c+1$,

  * (b)

if $p\not\equiv 1\pmod{q}$, then $q^{b}||\sigma(p^{c})$ if and only if $b\geq
a_{q}(p),ord_{q}(p)\mid c+1$, and $q^{b-a_{q}(p)}\mid c+1$.

A recent result of Yamada [22] is

######  Lemma 2.7.

If $n$ is an odd perfect number with $\beta=e_{1}=\cdots=e_{t}\geq 1$ then

$\omega(n)\leq 4\beta^{2}+2\beta+3.$

##  3\. Proof of Theorem 1.1

Since $6=\Phi_{2}(5)$ divides $\sigma(5^{\alpha})$ and $M$ is square-free, one
has $M=3Q$ for some positive square-free integer $Q$ coprime with $3$, so that
we can write $n=5^{\alpha}3^{2\beta}Q^{2\beta}$. Since from Lemma 2.1 one has
$\omega(n)>2$,it follows that $Q\neq 1$. Observe that
$3^{2\beta+1}\in\\{3,2\\}\pmod{5}$ so that $5\nmid\sigma(3^{2\beta})$. In
other words, $5\mid\sigma(5^{\alpha})\sigma(3^{2\beta})$. Thus, since $n$ is
perfect we have that $5\mid\sigma(q^{2\beta})$ for some prime divisor $q$ of
$Q$. Set now

(3) $S=\\{p\equiv 1\pmod{5}\colon p\mid Q\\}\;\text{and}\;\gamma=\sharp(S).$

Since for each prime divisor $p$ of $Q$ with $p\not\equiv
1\pmod{5},d=ord_{5}(p)\in\\{2,4\\}$ is even, we have $\gamma>0$ by Lemma 2.6.
More precisely, Lemma 2.6 implies that if a prime divisor $p$ of $Q$ satisfies
$p\not\equiv 1\pmod{5}$ then $5\nmid\sigma(p^{2\beta})$ since the even number
$d$ cannot divide the odd number $c+1$, where $c=2\beta$. In other words,
$q\in S$, so that $S$ is not empty. We can then, by Lemma 2.6 a), since
$q\equiv 1\pmod{5}$ and since $5\mid\sigma(q^{2\beta})$, define a positive
integer $b>0$ by $5^{b}||2\beta+1$. By Lemma 2.6, and by the definition of $S$
we get $5^{b}||\sigma(p^{2\beta})$ for all $p\in S$. Thus, since $n$ is
perfect we get

(4) $\alpha=b\gamma.$

By Lemma 2.3 we can assume that $3\nmid 2\beta+1$. By Lemma 2.6 it follows
that $3\nmid\sigma(Q^{2\beta})$. But since trivially
$3\nmid\sigma(3^{2\beta})$ and $n$ is perfect we must have
$3^{2\beta}||\sigma(5^{\alpha})$. We can also obtain this from Lemma 2.4. So
by Pomerance’s Lemma 2.6 we get

(5) $3^{2\beta-1}||\alpha+1.$

Since $b\leq b\cdot\ln(5)\leq\ln(2\beta+1)$, we get from (4) and (5)

(6) $\gamma\geq\frac{3^{2\beta-1}-1}{\ln(2\beta+1)}.$

But, trivially, $\gamma\leq\omega(n)$. So we get from Yamada’s Lemma 2.7 and
(6)

(7) $3^{2\beta-1}-1\leq\ln(2\beta+1)\cdot(4\beta^{2}+2\beta+3).$

This forces $\beta\in\\{1,2\\}$ so that $\beta=2$ since $\beta\not\equiv
1\pmod{3}$. This contradicts Lemma 2.2 thereby proving the theorem.

##  4\. Proof of Theorem 1.2

Part c) follows from part a). Part b) follows from part a) and from
Proposition 1.3. Now we prove part a). Observe that $\Phi_{3}(y)$ is odd for
all integers $y$. Assume that for some $j\in\\{1,\ldots,t\\}$ the prime
$q_{j}$ is good. Let $k\geq 0$ be a nonnegative integer. Observe that any
element of $S_{k}(q_{j})$ is a prime divisor of $n$ since $n$ is perfect.
Observe also that for any index $i$, $5\notin S_{k}(q_{i})$ since for any
integer $y$ one has $\Phi_{3}(y)\not\equiv 0\pmod{5}$. Thus, by definition
that $q_{j}$ is good there exists an index $i\in\\{1,\ldots,t\\}$ and there
exists a positive integer $k\geq 0$ such that the prime $q_{i}$ satisfies
$q_{i}\in S_{k}(q_{j})$, so in particular we obtain that $q_{i}\mid n$, and,
moreover, one has $q_{i}\in\\{2,4\\}\pmod{7}$. Thus, $\Phi_{3}(q_{i})\equiv
0\pmod{7}$.

Since $3\mid 6k_{i}+3$ we have $\Phi_{3}(q_{i})\mid\sigma(q_{i}^{6k_{i}+2})$.
Thus, $\Phi_{3}(q_{i})\mid n$ since $n$ is perfect and $\Phi_{3}(q_{i})$ is
odd. But $7\mid\Phi_{3}(q_{i})$. So $7\mid n$. This is impossible by Lemma 2.5
since $3$ and $5$ are also divisors of $n$. This proves the theorem.

We give below a sufficient condition in order that the condition on Theorem
1.2 part a) holds.

######  Proposition 4.1.

Let $n$ be an odd perfect number such that

$15\mid n,\;\;5^{\alpha}||n\;\;\text{and}\;\;3^{2b}||n$

for some positive integers $\alpha,b>0$. If

(8) $3\mid(\alpha+1)(2b+1),$

then $n$ has a good prime divisor.

###### Proof.

If $3\mid\alpha+1$ then one has $31=\Phi_{5}(3)\mid\sigma(5^{\alpha})$. Thus,
$31\mid n$ and $31$ is good. If $3\mid 2b+1$ then
$13=\Phi_{3}(3)\mid\sigma(3^{2b})$ so that $13\mid n$ and $13$ is also good. ∎

## References

  * [1] A. Brauer, _On the non-existence of odd perfect numbers of form $p^{\alpha}q_{1}^{2}q_{2}^{2}\cdots q_{t-1}^{2}q_{t}^{2}$_, Bull. Amer. Math. Soc. 49 (1943), p. 712–718.
  * [2] A. Brauer, _Note on the non-existence of odd perfect numbers of form $p^{\alpha}q_{1}^{2}q_{2}^{2}\cdots q_{t-1}^{2}q_{t}^{2}$_, Bull. Amer. Math. Soc. 49 (1942), p. 1943.
  * [3] G. L. Cohen, R. J. Williams, _Extensions of some results concerning odd perfect numbers_ , Fibonacci Quart. 23 (1985), p. 70–76.
  * [4] B. Crstici, J. Sandor, _Handbook of number theory II_ , Kluwer Academic Publishers, Dordrecht, 2004, ii+637 pp.
  * [5] G. G. Dandapat,, J. L. Hunsucker, C. Pomerance, _Some new results on odd perfect numbers_ , Pacific J. Math. 57 (1975), p. 359–364.
  * [6] R. Evans, J. Pearlman, _Nonexistence of odd perfect numbers of a certain form_ , Fibonacci Quart. 45 (2007), p. 122–127.
  * [7] L. Euler, _De numeris amicabilibus_ , Reprinted in Opera posthuma, Euler archive (E798a], http://www.math.dartmouth.edu/ euler 1 (1862), p. 85–100.
  * [8] L. H. Gallardo, _On a remark of Makowski about perfect numbers_ , Elem. Math. 65 (2010), p. 121–126.
  * [9] P. J. Hagis, W. L. McDaniel, _A new result concerning the structure of odd perfect numbers_ , Proc. Amer. Math. Soc. 32 (1972), p. 13–15.
  * [10] P. J. Hagis, W. L. McDaniel, _Some results concerning the non-existence of odd perfect numbers of the form $p^{\alpha}M^{2\beta}$_, Fibonacci Quart. 13 (1975), p. 25–28.
  * [11] H. J. Kanold, _Untersuchungen über ungerade vollkommenen Zahlen_ , J. Reine Angew. Math. 183 (1941), p. 98–109.
  * [12] H. J. Kanold, _Verschärfung einer notwendigen Bedingung für die Existenz einer ungeraden vollkommenen Zahl_ , J. Reine Angew. Math. 184 (1942), p. 116–123.
  * [13] H. J. Kanold, _Kreisteilungspolynome und ungerade vollkommenen Zahlen_ , Ber. Math.-Tagung Tübingen 1946 (1947), p. 84–87.
  * [14] H. J. Kanold, _Sätze über Kreisteilungspolynome und ihre Anwendungen auf einige zahlen theoretische Probleme. II._ , J. Reine Angew. Math. 188 (1950), p. 129–182.
  * [15] H. J. Kanold, _Einige neuere Bedigungen für die Existenz ungerader vollkommener Zahlen_ , J. Reine Angew. Math. 192 (1953), p. 24–34.
  * [16] P. J. McCarthy, _Remarks concerning the non-existence of odd perfect numbers_ , Amer. Math. Monthly 64 (1957), p. 257–258.
  * [17] W. L. McDaniel, _The non-existence of odd perfect numbers of a certain form_ , Arch. Math. (Basel), 21 (1970), p. 52–53.
  * [18] P. Starni, _On some properties of the Euler’s factor of certain odd perfect numbers_ , J. Number Theory, 116 (2006), p. 483–486.
  * [19] R. Steuerwald, _Verschärfung einer notwendigen Bedingung für die Existenz einer ungeraden vollkommenen Zahl_ , S. B. math.-nat. Abt. Bayer. Akad. Wiss. München, (1937), 69–72.
  * [20] J. J. Sylvester, _Note on a proposed addition to the vocabulary of ordinary arithmetic_ , Coll. Math. Papers of J. J. Sylvester H. F. Baker, Ed. Cambridge University Press, 4 (1912), pp. 588–591. Reprinted from Nature 37 (1888), 152–153.
  * [21] J. J. Sylvester, _Sur les Nombres Parfaits_ , Coll. Math. Papers of J. J. Sylvester H. F. Baker, Ed. Cambridge University Press, 4 (1912), pp. 604–606; pp. 615–619. Reprinted from Comptes Rendus 106 (1888), 403–405, 641–642; Mathesis 8 (1888), 57–61.
  * [22] T. Yamada, _Odd perfect numbers of a special form_ , Colloq. Math., 103 (2005), p. 303–307.


# Cascade Speculative Drafting for Even Faster LLM Inference

Ziyi Chen  Xiaocong Yang  Jiacheng Lin  Chenkai Sun  Kevin Chen-Chuan Chang
Jie Huang

###### Abstract

Speculative decoding reduces the latency of large language model (LLM)
inference by leveraging a draft model to draft for a larger target model to
review. However, drafting in speculative decoding involves slow autoregressive
generation and allocates the same amount of time to generating tokens of
varying importance. These two inefficiencies lead to its suboptimal
performance. To address this issue, we introduce Cascade Speculative Drafting
(CS Drafting), a speculative execution algorithm that comprises two types of
cascades. The Vertical Cascade eliminates autoregressive generation from
neural models, while the Horizontal Cascade constitutes efficient time
allocation in drafting. Combining both cascades, our CS Drafting algorithm has
achieved up to a 72 percent additional speedup over speculative decoding in
our experiments, while maintaining the same output distribution as the target
model.

Machine Learning, ICML

mO Ziyi[#1] mO Chenkai[#1]

##  1 Introduction

The advent of Large Language Models (LLMs), like GPT-4 (OpenAI, 2023) has
marked a significant milestone in the field of natural language processing
(NLP). These models have not only excelled in various NLP tasks but have also
found widespread application in user-interactive settings such as chatbots and
virtual assistants. This application involves an extremely high number of
users, up to hundreds of millions daily. To serve in real-time at this scale,
a low-latency system is not only cost-saving but also crucial for keeping the
service running. In addition, the sheer scale of the service means that even a
slight improvement in the latency of LLMs can greatly contribute to both the
provider and the community. Consequently, optimizing LLM latency has become a
crucial and impactful research focus.

Unfortunately, LLMs currently suffer from high latency, especially in long-
form generation, as autoregressive LLMs generate tokens one by one. An
emerging solution, known as speculative decoding (Leviathan et al., 2023; Chen
et al., 2023), shows potential to mitigate this issue. In speculative
decoding, a draft model (which is smaller and faster) generates $k$ tokens in
each step (with $k$ being a hyperparameter), and these tokens are then
reviewed by a target model (which is larger and slower) in parallel. The
target model will accept any tokens aligned with its output and further
generate one token; the process happens all in a single run while maintaining
the output distribution identical to the autoregressive one by the target
model itself. As a larger number of expected accepted tokens per run indicates
fewer target model runs, the efficiency of speculative decoding can be
attributed to two main factors: the expected number of tokens accepted by the
target model per run, and the latency of drafting.

Figure 1: The probability of acceptance of draft tokens in relation to their
positions in a single step of speculative decoding, evaluated on
FLAN-T5-small, base, and large models. The draft model generates 30 tokens at
each step. Figure 2: Cascade Speculative Sampling uses LLMs of multiple sizes
to generate and verify tokens. The model at the inner layer
$\mathcal{M}_{d(i)}$ generates tokens proposed to and verified by LLMs at the
next outer layer, $\mathcal{M}_{d(i+1)}$. This recursive process forms the
vertical cascade. After a vertical cascade, a smaller $\mathcal{M}_{d(i)}$
will serve as the target model and perform a vertical cascade. The process
repeats until the smaller model becomes a statistical language model that will
generate autoregressively forming the horizontal cascade.

Herein lies a trade-off between these two factors: to increase the expected
number of accepted tokens, we can use a larger draft model or generate more
draft tokens per target run. However, both of these approaches will
significantly increase the latency of drafting. Consequently, the maximum
speed improvement achievable by the current speculative decoding algorithm
depends on finding an optimal balance between model size and the number of
generated tokens. Previous work by Leviathan et al. (2023) has shown that very
small models (e.g., less than 1/100$th$ the size of the target model), with
varying values of $k$, are optimal for most tasks they experimented with,
suggesting that the cost of drafting can be a limiting factor in the
speculative decoding algorithm. This underscores that improving drafting
efficiency is crucial for further enhancing the performance of speculative
decoding.

In light of this, there exist a type of draft models, including statistical
language models like bigram language models, that are immune to drafting
efficiency issues. Owing to their simple structure, these models incur
negligible latency and computational resource costs compared to neural
language models, thereby avoiding the aforementioned trade-off. Therefore,
assuming enough parallel computing power to perform computation on additional
$k$ tokens with similar time cost (Leviathan et al., 2023), utilizing
speculative decoding with a statistical language model as the draft model can
generally and intuitively enhance the efficiency of a neural language model.
However, due to their limited capabilities, speculative decoding with
statistical language models alone may not yield optimal results compared to
using a well-sized neural language model from the same family as the target
model when the neural language model is available.

Based on the above analysis, we propose Cascade Speculative Drafting (CS
Drafting), a speculative execution algorithm that comprises multiple draft
models, starting with the smallest being a statistical language model. Each
neural draft model reviews generations from a smaller model and then proposes
its reviewed content to either a larger draft model or the target model. We
refer to this tiered speculative decoding approach as the Vertical Cascade.

Furthermore, our analysis in Figure 1 reveals an interesting pattern in the
expected acceptance rate during the drafting step: tokens generated later in
the sequence by the draft model show a progressively lower probability of
being accepted by the target model111A theoretical analysis is provided in
Section 4. Note that this probability differs from the acceptance rate, which
is the probability of a token being accepted conditioned on the previous
tokens’ acceptance.. This indicates that later tokens from draft models, more
prone to rejection, contribute less to the expected number of accepted tokens,
yet incur the same latency. Based on this observation and our practice, we
suggest the use of smaller, faster draft models for generating these high-
rejection tokens, forming the Horizontal Cascade. Along with the
aforementioned Vertical Cascade, these strategies compose our complete CS
Drafting approach, as illustrated in Figure 2.

Through theoretical analysis and empirical studies, we demonstrate that the CS
Drafting algorithm outperforms speculative decoding in terms of latency across
various tasks and settings, achieving an additional speedup of up to 72% over
speculative decoding. These findings highlight the practical advantages and
efficiency enhancements offered by both vertical and horizontal cascades.

Our main contributions are summarized as follows:

  * •

We introduce Cascade Speculative Drafting (CS Drafting), a speculative-
execution-based algorithm that improves language model inference speed without
sacrificing generation quality.

  * •

We provide theoretical analyses supporting the effectiveness of the proposed
CS Drafting approach.

  * •

We conduct empirical experiments showing that CS Drafting achieves further
speedup over speculative decoding across different tasks and settings.

##  2 Preliminary

###  2.1 Speculative Decoding Algorithm

In real-world applications of large language models (LLMs), the sequential
nature of autoregressive decoding emerges as a primary latency bottleneck in
terms of response time. Addressing this, speculative decoding (SD) (Leviathan
et al., 2023) presents an innovative solution that utilizes a compact draft
model for sequential token generation with validation by a larger target model
resulting in reduced latency.

The core concept of speculative decoding involves a novel algorithm that
accelerates sampling from autoregressive models without altering output
distributions. At its heart, there are two key observations: 1) certain
generations in language modeling are simpler than others and can be predicted
by more efficient models correctly, and 2) using speculative execution along
with a new sampling method enables faster, exact decoding from large models.

Specifically, let $x$ be the input tokens at a run and $\mathcal{M}_{t}$ and
$\mathcal{M}_{d}$ are the target and the draft model respectively, and
$\mathcal{M}_{t}(x)[i]$ and $\mathcal{M}_{d}(x)[i]$ be their probability
output at $i$-th token when input is $x$. We interpret speculative sampling as
a two-stage operation. In the proposing stage, we sample
$\\{x_{t+1},...,x_{t+k}\\}$ from draft model $\mathcal{M}_{d}$
autoregressively and append them to $x$ . In the reviewing stage, let
$x_{i}\in\\{x_{t+1},...,x_{t+k}\\}$ represents the token at the current
position, and we accept it if
$\mathcal{M}_{d}(x)[i-1]<\mathcal{M}_{t}(x)[i-1]$; in the event that
$\mathcal{M}_{d}(x)[i-1]>\mathcal{M}_{t}(x)[i-1]$, we reject $x_{i}$ with a
probability of $1-\frac{\mathcal{M}_{t}(x)[i-1]}{\mathcal{M}_{d}(x)[i-1]}$ and
proceed to resample $x_{i}$ from a recalibrated distribution
$\text{norm}(\max(0,\mathcal{M}_{t}(x)[i-1]-\mathcal{M}_{d}(x)[i-1]))$ and
reject any token following $x_{i}$. At the end, the target model will generate
one additional token following the accepted tokens. Such a design guarantees
the output is the same as sampling autoregressively using the target model
alone (Leviathan et al., 2023).

This method was empirically validated on various tasks and model sizes,
demonstrating a significant acceleration in inference times (2x-3x faster)
compared to standard implementations, without affecting the outputs.
Importantly, it does not require task-specific training, altering model
architectures, or changing training procedures, making it a practical solution
for enhancing the efficiency of LLMs.

##  3 Cascaded Speculative Drafting

Algorithm 1 CascadeSpeculativeDrafting

Require:draft model $\\{\mathcal{M}_{d_{1}},...,\mathcal{M}_{d_{n}}\\}$,
target model $\mathcal{M}_{t}$, $prefix$, flag $isFirstCall$, hyperparameters
$K_{nn}$, $l$

draftList $\leftarrow$ $[\mathcal{M}_{d_{1}},...,\mathcal{M}_{d_{n}}]$

$\triangleright$ Initialize curGen and curProb

curGen $\leftarrow$ $prefix$, curProbs $\leftarrow$ a list of ones of length
prefix

$\triangleright$ Unpack the a list of $k$ for current function call

$[k_{1},...,k_{n-1}]\leftarrow$ first row of $K_{nn}$

$\triangleright$ Base case of the recursive call when the MaG generate

if draftList only contains one element then

$\mathcal{M}\leftarrow$ first element of draftList

$res\leftarrow$ $\mathcal{M}(curGen)$

$\triangleright$ MaG generates greedily, so the logits will be 1 at the
position of the generation token and 0 otherwise

return $res.generation,res.logits$

end if

$\triangleright$ Begin the cascade

for $i\leftarrow 1$ to $n$ do

curTarget $\leftarrow$ the $i$-th item of draftList

curDraftList $\leftarrow$ the sublist of draftList starting from index $i+1$

curK $\leftarrow$ the submatrix of $K_{nn}$ from with the top-left corner at
$(i+1,j)$ extending to the bottom-right corner

while length of curGen - prefix.length is less than $k_{i}$ do

$[x_{1},..,x_{r}],[p_{1},p_{2},...,p_{r}]\leftarrow$
CascadeSpeculativeDecoding(curDraftList, curTarget, curGen, False, curK, $l$)

curGen $\leftarrow[x_{1},..,x_{r}]$

$\triangleright$ Do not overwrite the previous probabilities

s $\leftarrow$curProbs.length + 1

Add elements of $[p_{s},p_{2},...,p_{r}]$ to curProbs

end while

end for

$\triangleright$ No leniency when the target model reviews

if isFirstCall then

$l\leftarrow 1$

end if

$\triangleright$ Review process by $\mathcal{M}_{t}$ to ensure the output
distribution is the same as autoregressive generation

$[p_{1}^{\prime},p_{2}^{\prime},...,p_{m}^{\prime}]\leftarrow$
$\mathcal{M}_{t}(curGen)$

$index\leftarrow m$

for $i\leftarrow 1+prefix.length$ to $m-1$ do

Sample $r$ from a uniform distribution

if $r\leq min(1,\frac{lp_{i}^{\prime}}{p_{i}})$ then

$index\leftarrow i$ and exit the loop

end if

end for

Sample $x_{last}$ from $p_{index}^{\prime}-p_{index}$

return $[x_{1},...,x_{index-1}]+[x_{last}]$,
$[p_{1}^{\prime},p_{2}^{\prime},...,p_{index}^{\prime}]$

###  3.1 Vertical Cascade

The speculative decoding algorithm relies on the autoregressive generation of
a smaller draft model. However, despite its smaller size, the draft model must
run $k$ times for each target model run, and the cost can still be
significant. To further reduce latency in the drafting process, we propose
using an even smaller model to assist in drafting and employing the original
draft model to review the generation of this smaller model. This process can
be done recursively until it reaches the smallest draft model. The smallest
draft model can be a statistical language model, such as a bigram language
model, where the cost is negligible compared to neural language models. We
refer to this recursive process as Vertical Cascade.

Furthermore, to further improve speed, we can introduce leniency, a
hyperparameter in speculative decoding that loosens the review process by the
target model, allowing for faster speed at the trade-off of potentially
differing results from the target model (Leviathan et al., 2023). With
leniency $l\in[1,\infty)$, the acceptance condition for token $x_{i}$ in
speculative decoding becomes
$\mathcal{M}{d}(x)[i]<l\times\mathcal{M}{t}(x)[i]$. Otherwise, with a
probability of $1-\frac{l\times\mathcal{M}{t}(x)}{\mathcal{M}{d}(x)}$, we
reject $x_{i}$ and any following tokens. While the reduced quality introduced
by leniency in speculative decoding is generally undesirable in practice, it
fortunately does not affect the final output in our vertical cascade
approach—we can only apply leniency in the inner speculative decoding. As long
as leniency is not applied to the target model, the final quality is always
guaranteed by the target model.

###  3.2 Horizontal Cascade

As illustrated in Figure 1, another key observation is that during the
drafting steps of speculative decoding, not all drafting tokens are created
equal. The first draft token is more likely to be accepted as it only depends
on itself; the last token is rarely accepted, as it has a chance of being
reviewed only if all preceding tokens are accepted. From another perspective,
one could also say that the first draft token bears the responsibility for all
succeeding tokens, while the last token bears none. In Section 4, we provide a
theoretical analysis of this phenomenon.

Based on this observation, we propose better allocation of the time cost of
drafting by using larger models to generate the preceding draft tokens and
smaller models for the succeeding tokens. This design allows more time to be
allocated to more effective tokens, leading to a reduction in overall latency.
We refer to this design as the Horizontal Cascade.

###  3.3 Max-gram for Better Statistical Drafting

A statistical language model is special to speculative decoding, as it incurs
almost no cost when drafting for its target model. In our pursuit of a more
effective statistical language model, we noticed a general pattern: in
language model generation, some words and phrases from the input query
frequently reappear in the generated content. Based on this observation, we
designed the Max-Gram (MaG) algorithm. It greedily identifies maximal matches
between the initial input (or existing generation) and tokens from the end of
the generation. In cases where there is no match, we resort to a bigram model
based on the probability distribution of Wikipedia (chosen to maintain the
generality of our experiment). Surprisingly, despite its simplicity, this
straightforward and general algorithm has proven highly effective in aligning
with neural language model outputs. We include a GPU-friendly version of the
Max-Gram algorithm in Appendix A.

###  3.4 Algorithm

Combining the horizontal and vertical cascades, the algorithm is presented in
Algorithm 1. At its center, there is a for-loop that performs the horizontal
cascade, while the recursive call forms the vertical cascade. Notably, the
last element of the draft models is the MaG model.

The algorithm requires a two-dimensional hyperparameter, $K_{nn}$, with each
row serving as the stop criteria for a layer of recursive calls. For
simplicity, we assume the leniency parameter $l$ is universal for the
algorithm, except when the target model is under review; thus, the algorithm
can benefit from the speedup of leniency without altering the output
distribution.

##  4 Theoretical Analysis

In this section, we present some theoretical analyses of the proposed Cascade
Speculative Drafting algorithm.

###  4.1 Expected Walltime Improvement

To assist our theoretical analysts, we establish the notions. Let
$\mathcal{M}_{t}$ be the target model, $\\{\mathcal{M}_{i}\\}$ be the draft
models assisting generation with $\mathcal{M}_{i}$ being the draft model
generating the $i$-th token. In the simpler case of the speculative decoding,
$\mathcal{M}_{i}=\mathcal{M}_{d}$ for any $i$. Let $x$ be the input to the
model at a single run, $\mathcal{M}_{t}(x)$ and $\mathcal{M}_{i}(x)$ are then
the output probability distribution with input $x$.

Expected acceptance rate
$\alpha=\mathbf{E}(1-\frac{1}{2}|\mathcal{M}_{t}(x)-\mathcal{M}_{i}(x)|)$ is
the probability of draft generation by $\\{\mathcal{M}_{i}\\}$ being accepted
by target model $\mathcal{M}_{t}$ (Leviathan et al., 2023).

Cost coefficient $c_{i}$ is the ratio of time for a single run of draft model
$\mathcal{M}_{i}$ over target model $\mathcal{M}_{t}$.

Expected walltime improvement factor (EWIF) is the expected time improvement
of an algorithm based on. We provide the formula for EWIF in an extended
setting when multiple draft models are involved.

######  Theorem 4.1.

The expected walltime improvement factor (EWIF) by Algorithm 1 is
$T(k,{\alpha_{1},...,\alpha_{k}},{c_{1},...,c_{k}})=\frac{\sum_{i=0}^{k}\prod_{j=1}^{i}\alpha_{j}}{1+\sum_{i=1}^{k}c_{i}}$.

###### Proof.

Since every token will only be considered by the target model if all tokens
before are accepted, a simple recursion leads to the probability of acceptance
of the $i$-th token being $\prod_{j=1}^{i-1}\alpha_{j}$, and the
$\prod_{j=1}^{0}\alpha_{j}=1$ representing the token generated by the target
model. In the right-hand side, the numerator is the expected number of tokens
generated, and the denominator is the time costs for each step of such a
system, so the right-hand side is the expected efficiency improvement. ∎

We can immediately achieve a formula for speculative decoding by requiring all
the draft models to be the same.

######  Corollary 4.2.

When $q_{1}=q_{2}=...=q_{k}$, let $\alpha_{i}=\alpha$ and $c_{i}=c$ for any
$i$, the EWIF is $\frac{1-\alpha^{k+1}}{(1-\alpha)(c\cdot k+1)}$.

Furthermore, theorem 4.1 can be used to analyze the importance of the tokens
in the drafting step.

######  Corollary 4.3.

The probability of $i$-th token being accepted is $\prod_{j=1}^{i}\alpha_{j}$.
The derivative of EWIF with respect to $\alpha_{l}$ is
$\frac{dT(k,{\alpha_{1},...,\alpha_{k}},{c_{1},...,c_{k}})}{d\alpha_{l}}=\frac{\sum_{i=l}^{k}\prod_{j=1,j\neq
l}^{i}\alpha_{j}}{1+\sum_{i=1}^{k}c_{i}}$. Specifically,
$\frac{dT(k,{\alpha_{1},...,\alpha_{k}},{c_{1},...,c_{k}})}{d\alpha_{1}}=\frac{\sum_{i=1}^{k}\prod_{j=2}^{i}\alpha_{j}}{1+\sum_{i=1}^{k}c_{i}}$
and
$\frac{dT(k,{\alpha_{1},...,\alpha_{k}},{c_{1},...,c_{k}})}{d\alpha_{k}}=\frac{\prod_{j=1}^{k-1}\alpha_{j}}{1+\sum_{i=1}^{k}c_{i}}$.

Using the information provided by Leviathan et al. (2023), we calculat a
simulated EWIF under the assumption that the event of acceptance by the target
model is a Bernoulli trial. The results, shown in Table 1, indicate that
speculative sampling with a horizontal cascade achieved better EWIF than
vanilla speculative sampling under this assumption.

###  4.2 Analysis of Model Interpolation

The setting of cascade drafting can be simply extended using model
interpolation that involves choosing between two models using randomness.
Given two draft systems $d_{1}$ and $d_{2}$ (They can be two models generating
autoregressive or two speculative decoding systems as used in vertical
cascade) and a probability function $f$, an interpolation $d_{inter}$ is
defined as $f(i)d_{1}+(1-f(i))d_{2}$. In other words, with probability $f(i)$,
$d_{inter}$ is $d_{1}$, and with probability $1-f(i)$, $d_{inter}$ is $d_{2}$.
As a result,
$\alpha_{i}=f(i)\alpha_{d1}+(1-f(i))\alpha_{d2}=\alpha_{d2}+f(i)(\alpha_{d1}-\alpha_{d2})$
and $c_{i}=f(i)c_{d1}+(1-f(i))c_{d2}=c_{2}+f(i)(c_{d1}-c_{d2})$. An
interpolation system can provide a smooth transition between two systems;
however, in theorem 4.4, we prove that the optimal can always be reached
without interpolation.

######  Theorem 4.4.

Given a horizontal cascade system with the setting mentioned above. There
exists a probability function $f$ that optimizes the system such that $f$
satisfies $f(i)\in\\{0,1\\}$ for any $i$. This means each of the tokens will
be generated by either $d_{1}$ or $d_{2}$, and the optimal system is
deterministic.

Proof of Theorem 4.4 is included in appendix B.

Dataset | $\mathcal{M}_{d1}$ | $\mathcal{M}_{d2}$ | $k_{1}$ | $k_{2}$ | EWIF
---|---|---|---|---|---
CNNDM | small | - | 9 | - | 2.65
CNNDM | base | - | 8 | - | 2.96
CNNDM | base | small | 5 | 3 | 3.03
ENDE | small | - | 12 | - | 3.61
ENDE | base | - | 11 | - | 3.75
ENDE | base | small | 5 | 8 | 3.93
Table 1: Simulated EWIF under the assumption that the acceptance distribution
is a Bernoulli distribution. BASE and SMALL refer to FLAN-T5-base and
FLAN-T5-small. In the simulation, speculative sampling with horizontal cascade
exceeded the performance of the vanilla speculative decoding on both CNN
Dailymail (Nallapati et al., 2016) and WMT EnDe (Bojar et al., 2018) datasets.

##  5 Evaluation

Previous works on speculative decoding and related methods relied on walltime
as an evaluation method. However, there are standardization and legitimacy
concerns related to walltime. Leviathan et al. (2023) mentioned that cost
coefficiency, the ratio between the time for a single run of draft model and
target model will vary from system to system which can result in significant
variation in wall time improvement across different systems, making
comparisons across different research work difficult.

In addition, a recent analysis suggests GPU speed can vary for the same GPU
model with one being 1.5x faster than another GPU of the same model (Sinha et
al., 2022), and even for the same GPU, the performance variation between
different runs is unknown; therefore, theoretical walltime improvement up to
1.5x can be undermined by GPU variation, and methods without any improvement
can be measured with an improvement up to 1.5x by running on a different GPU.
The properties of such lack of standardization and stability make walltime
unfit for measuring algorithmic improvement. To resolve this issue, we design
a new metric to measure speculative decoding and its related algorithms which
can reduce the impact of varying/unstable GPU performance.

Our proposed method, standardized walltime improvement (SWI), calculates the
GPU times of the models, assuming that each run of a language model costs the
same amount of time, an assumption made when inventing the speculative
sampling algorithm (Chen et al., 2023). Given a speculative decoding system
$S$ containing $k$ draft models $\mathcal{M}_{d1},...,\mathcal{M}_{dk}$,
target model $\mathcal{M}_{t}$ solving a task $T$, and let $count(S,m,T)$ be
the count of runs of model $m$ during the execution of task $T$ with system
$S$, let $c_{i}$ be the expected cost coefficient being the time ratio between
a single run of $\mathcal{M}_{i}$ and $\mathcal{M}_{t}$, and let $n$ be the
total of tokens generated, the standardized walltime improvement is defined as

$\begin{split}SWI&(\mathcal{M}_{d1},...,\mathcal{M}_{dk},\mathcal{M}_{t},T)=\\\
&\frac{n}{count(S,\mathcal{M}_{t},T)+\sum_{i=1}^{n}count(S,\mathcal{M}_{di},T)c_{i}},\end{split}$

which is simply the sum of GPU time by all models when $c_{i}$ is measured
during a local experiment. The benefit of the $SWI$ evaluation is that
$count(S,\mathcal{M}_{t},T)$ and $count(S,\mathcal{M}_{di},T)$ will be the
same across different systems, so by using the same $c_{i}$ across different
experiments the GPU performance variation will be eliminated; therefore, it
provides a standardized, reproducible measurement.

During our experiment, we will use two sets of $\\{c_{i}\\}$, existing
$\\{c_{i}\\}$ reported by Leviathan et al. (2023) and an heuristic
$\\{c_{i}\\}$ being the ratio of number of tunable parameters between
$\mathcal{M}_{di}$ and $\mathcal{M}_{t}$.

Dataset | Algorithm | $\\{\mathcal{M}_{di}\\}$ | SWI (MS) | $k_{11}$ | $k_{21}$ | $k_{12}$ | $l$
---|---|---|---|---|---|---|---
GSM8K | Autoregressive | - | 1 | - | - | - | -
GSM8K | S. Decoding | base | $3.38$ | 10 | - | - | -
GSM8K | S. Decoding | small | $3.06$ | 11 | - | - | -
GSM8K | C.S. Drafting |  base, mag | $3.62$ | 9 | - | - | -
GSM8K | C.S. Drafting |  small, mag | $3.16$ | 11 | - | - | -
GSM8K | C.S. Drafting |  base, small, mag | 3.75 | 7 | 1 | 10 | 1.5
MMLU | Autoregressive | - | 1 | - | - | - | -
MMLU | S. Decoding | base | $3.97$ | 13 | - | - | -
MMLU | S. Decoding | small | $4.12$ | 19 | - | - | -
MMLU | C.S. Drafting |  base, mag | $4.50$ | 12 | - | - | -
MMLU | C.S. Drafting |  small, mag | $4.36$ | 17 | - | - | -
MMLU | C.S. Drafting |  base, small, mag | 4.83 | 5 | 1 | 19 | 2
Dataset | Algorithm | $\\{\mathcal{M}_{di}\\}$ | SWI (PW) | $k_{11}$ | $k_{21}$ | $k_{12}$ | $l$
GSM8K | Autoregressive | - | 1 | - | - | - | -
GSM8K | S. Decoding | base | $2.99$ | 8 | - | - | -
GSM8K | S. Decoding | small | $2.76$ | 8 | - | - | -
GSM8K | C.S. Drafting |  base, mag | $3.22$ | 8 | - | - | -
GSM8K | C.S. Drafting |  small, mag | $2.90$ | 7 | - | - | -
GSM8K | C.S. Drafting |  base, small, mag | 3.29 | 5 | 1 | 9 | 1.5
MMLU | Autoregressive | - | 1 | - | - | - | -
MMLU | S. Decoding | base | $3.42$ | 10 | - | - | -
MMLU | S. Decoding | small | $3.51$ | 11 | - | - | -
MMLU | C.S. Drafting |  base, mag | $4.07$ | 9 | - | - | -
MMLU | C.S. Drafting |  small, mag | $3.97$ | 12 | - | - | -
MMLU | C.S. Drafting |  base, small, mag | 4.23 | 5 | 1 | 13 | 1.5
Table 2:  The experiment results from datasets GSM8K and MMLU. BASE and SMALL
refer to FLAN-T5-base and FLAN-T5-small. SWI (MS) is the standardized walltime
improvement with the assumption that the latency of each run of a model is its
number of parameters (model size). SWI (PW) is the SWI with the assumption
that the latency of each run of a model is the time cost data reported from
previous work (Leviathan et al., 2023). $k_{11}$, $k_{21}$, $k_{12}$, $l$ are
the hyperparameters. $k_{1i}$ represents the step limitation target model and
the draft models, $k_{21}$ is the step limitations between the first and
second draft model, and $l$ is leniency as shown in algorithm 1. For
speculative decoding, the $k_{11}$ is simply the $k$.

##  6 Experiment

###  6.1 Setup

We chose our target and draft models from the FLAN-T5 (Chung et al., 2022)
family for our experiment, as there is a large variation in model sizes within
the FLAN-T5 family (ranging from 77 million to 11 billion parameters). To
align our experiment with current common usage, we do not perform fine-tuning,
and the generation is conducted in a zero-shot manner. We use FLAN-T5-xxl as
our target model, FLAN-T5-base and FLAN-T5-small as our reviewing draft
models, and the Max-Gram algorithm as the generating draft model.

To ensure our experiments are fully reproducible, we perform sampling at
temperature $0$, which is essentially greedy decoding. And we do not observe
any significant difference between sampling with temperature $1$ and greedy
decoding in previous speculative decoding experiments (Leviathan et al.,
2023).

Cascade Speculative Drafting Inference To reduce the number of hyperparameters
to tune, we use MaG to generate 10 tokens at once, as it is rare for more than
10 tokens to be accepted. We do not use lenience when the reviewer is
$\mathcal{M}_{t}$ to ensure the output distribution remains does not change.
Additionally, we eliminate leniency between $\mathcal{M}_{d2}$ and MaG because
the performance gap between them is large.

With these constraints, we are left with at most four hyperparameters:
$k_{11}$, $k_{21}$, $k_{12}$, and $l$. For the CS Drafting step where the
target model is the reviewer, $k_{11}$ and $k_{12}$ are used. $k_{21}$ and $l$
are used in the step where $\mathcal{M}_{d1}$ is the reviewer. However, there
are still too many hyperparameters for us to exhaustively search for the
optimal result; instead, we employ a halving grid search to find a set of
hyperparameters.

Baseline We consider both speculative decoding and vanilla autoregressive
generation as our baselines. For speculative decoding, we opt for
FLAN-T5-small and FLAN-T5-base as the draft models, as they perform better
than FLAN-T5-large, according to Leviathan et al. (2023) and our preliminary
experiments. We test a wide range of $k$-values, from 2 to 30, to ensure that
we find the best result for each model serving as our draft model to establish
our baseline.

Dataset We chose two commonly used datasets for our experiments. For both
datasets, we conducted experiments in a zero-shot chain-of-thought setup
(Kojima et al., 2022; Wei et al., 2023):

  * •

GSM8K (Cobbe et al., 2021) is a dataset comprising 8,500 high-quality,
linguistically diverse, grade-school math word problems. It focuses on multi-
step reasoning with problems that are typically solvable using basic
arithmetic in 2-8 steps.

  * •

MMLU (Hendrycks et al., 2021), or Massive Multitask Language Understanding, is
a benchmark for testing how well large language models grasp knowledge. It
encompasses 57 diverse subjects, ranging from elementary science to advanced
law.

###  6.2 Experimental Results

Table 2 presents the experimental results. In two settings of SWI, Cascade
Speculative Decoding has outperformed the speculative decoding algorithm. For
GSM8K, Cascade Speculative Decoding achieved a maximum additional speedup of
37% over the fastest speculative algorithm; for MMLU, the maximum additional
speedup improvement over speculative decoding is 72%.

Additionally, we emphasize the effectiveness of the MaG algorithm. When
comparing CS Drafting with one neural model and MaG against the fastest
speculative decoding setup, we found that CS Drafting with one neural model
gained up to a 56% speedup on MMLU and a 24% speedup on GSM8K. Notably, the
MaG algorithm only involves a bigram model with as many parameters as the size
of the tokenizer, making its memory cost negligible. Thus, the speedup gained
using CS Drafting with one neural model involves no additional deployment
overhead while reducing both latency and computational cost, making it a
superior choice over speculative decoding.

When comparing CS Drafting with two neural models to CS Drafting with one
neural model, the former requires additional memory utilization. Despite the
latency reduction, CS Drafting with two neural models can potentially incur
more computational cost. However, during our experiments, since the draft
models had only 2% of the number of parameters of the target model, the memory
cost did not outweigh the reduced latency. Therefore, the CS Drafting
algorithm with two neural models still uses less computational resources, as
it completes each generation round faster.

Another observation is that despite FLAN-T5-small sometimes outperforming
FLAN-T5-base as a draft model for speculative decoding, in CS Drafting with
the aid of MaG, FLAN-T5-base consistently outperforms FLAN-T5-small. This
raises a topic for future study: determining the ideal size of draft models
for CS Drafting.

##  7 Related Work

###  7.1 Efficienct Methods for Language Model Inference

In the era of large language models, the efficiency during inference becomes a
key to model service. To reduce the model inference cost and speed up, several
efficient methods have been proposed, including pruning, knowledge
distillation and quantization (Treviso et al., 2023). Model pruning takes
structured (Xia et al., 2022; Voita et al., 2019) or unstructured (Guo et al.,
2021; Chen et al., 2020) methods to remove the redundant model parameters to
reduce the storage memory and increase inference speed. Knowledge distillation
takes the approach of transferring knowledge from a superior teacher model to
a smaller student model (Hinton et al., 2015; Gou et al., 2021). Quantization
maps high-precision data representations (e.g. 32 bits) into low-precision
ones (e.g. 8 bits) to reduce memory consumption (Bhandare et al., 2019;
Schaefer et al., 2023).

###  7.2 Speculative Decoding

Recent works improved the speed of speculative decoding by experimenting with
task-specific knowledge distillation (Zhou et al., 2023), or using approaches
similar to speculative decoding to achieve a tradeoff between quality and
speed (Leviathan et al., 2023; Kim et al., 2023). However, the reduced quality
for speed can be undesirable, and task-specific training might not be
applicable to many real-world NLP applications such as chatbots; overall, we
found no generic improvement for speculative decoding in the current
literature.

Speculative decoding (Chen et al., 2023; Leviathan et al., 2023) is proposed
to improve inference speed by using a draft model to perform auto-regressive
decoding and a target model to check and replace the generated tokens. A key
to further speed up is to increase the acceptance rate in speculative
decoding, which can be done by aligning the distribution between the draft
model and the target model. Some recent work has proposed to improve the
performance of speculative decoding in a domain/task-specific setting. Zhou et
al. (2023) use generalized knowledge distillation to finetune the draft model
and achieve 10%-45% speedup compared to draft models without knowledge
distillation. Liu et al. (2023) propose Online Speculative Decoding to
continually update multiple draft models on observed user query data, and the
draft models align with the query distribution in real-time. However, both
approaches require additional task-specific training making it difficult to
apply the methods in a general setting. On the other hand, He et al. (2023)
proposed constructing a datastore from a domain-specific corpus to serve as a
draft model which can be used when a draft model is not available.

##  8 Conclusion

In our work, we propose a novel algorithm, CS Drafting, which involves two
cascades: the vertical cascade and the horizontal cascade. The vertical
cascade eliminates the necessity of autoregressive generation from a neural
language model, while the horizontal cascade effectively allocates the cost of
drafting tokens at different positions. Our experiments demonstrate that CS
Drafting achieves up to a 72 percent additional speedup over speculative
decoding without any additional training, while maintaining the same
generation quality as the target model.

## References

  * Bhandare et al. (2019) Bhandare, A., Sripathi, V., Karkada, D., Menon, V., Choi, S., Datta, K., and Saletore, V.  Efficient 8-bit quantization of transformer neural machine language translation model, 2019.
  * Bojar et al. (2018) Bojar, O., Federmann, C., Fishel, M., Graham, Y., Haddow, B., Huck, M., Koehn, P., and Monz, C.  Findings of the 2018 conference on machine translation (WMT18).  In Bojar, O., Chatterjee, R., Federmann, C., Fishel, M., Graham, Y., Haddow, B., Huck, M., Yepes, A. J., Koehn, P., Monz, C., Negri, M., Névéol, A., Neves, M., Post, M., Specia, L., Turchi, M., and Verspoor, K. (eds.), _Proceedings of the Third Conference on Machine Translation: Shared Task Papers_ , pp. 272–303, Belgium, Brussels, October 2018. Association for Computational Linguistics.  doi: 10.18653/v1/W18-6401.  URL https://aclanthology.org/W18-6401.
  * Chen et al. (2023) Chen, C., Borgeaud, S., Irving, G., Lespiau, J.-B., Sifre, L., and Jumper, J.  Accelerating large language model decoding with speculative sampling.  _arXiv preprint arXiv:2302.01318_ , 2023.
  * Chen et al. (2020) Chen, T., Frankle, J., Chang, S., Liu, S., Zhang, Y., Wang, Z., and Carbin, M.  The lottery ticket hypothesis for pre-trained bert networks, 2020.
  * Chung et al. (2022) Chung, H. W., Hou, L., Longpre, S., Zoph, B., Tay, Y., Fedus, W., Li, Y., Wang, X., Dehghani, M., Brahma, S., et al.  Scaling instruction-finetuned language models.  _arXiv preprint arXiv:2210.11416_ , 2022.
  * Cobbe et al. (2021) Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., Hesse, C., and Schulman, J.  Training verifiers to solve math word problems, 2021.
  * Gou et al. (2021) Gou, J., Yu, B., Maybank, S. J., and Tao, D.  Knowledge distillation: A survey.  _International Journal of Computer Vision_ , 129(6):1789–1819, March 2021.  ISSN 1573-1405.  doi: 10.1007/s11263-021-01453-z.  URL http://dx.doi.org/10.1007/s11263-021-01453-z.
  * Guo et al. (2021) Guo, D., Rush, A. M., and Kim, Y.  Parameter-efficient transfer learning with diff pruning, 2021.
  * He et al. (2023) He, Z., Zhong, Z., Cai, T., Lee, J. D., and He, D.  Rest: Retrieval-based speculative decoding, 2023.
  * Hendrycks et al. (2021) Hendrycks, D., Burns, C., Basart, S., Zou, A., Mazeika, M., Song, D., and Steinhardt, J.  Measuring massive multitask language understanding, 2021.
  * Hinton et al. (2015) Hinton, G., Vinyals, O., and Dean, J.  Distilling the knowledge in a neural network, 2015.
  * Kim et al. (2023) Kim, S., Mangalam, K., Moon, S., Malik, J., Mahoney, M. W., Gholami, A., and Keutzer, K.  Speculative decoding with big little decoder, 2023.
  * Kojima et al. (2022) Kojima, T., Gu, S. S., Reid, M., Matsuo, Y., and Iwasawa, Y.  Large language models are zero-shot reasoners.  _Advances in neural information processing systems_ , 35:22199–22213, 2022.
  * Langley (2000) Langley, P.  Crafting papers on machine learning.  In Langley, P. (ed.), _Proceedings of the 17th International Conference on Machine Learning (ICML 2000)_ , pp. 1207–1216, Stanford, CA, 2000. Morgan Kaufmann.
  * Leviathan et al. (2023) Leviathan, Y., Kalman, M., and Matias, Y.  Fast inference from transformers via speculative decoding.  In _International Conference on Machine Learning_ , pp. 19274–19286. PMLR, 2023.
  * Liu et al. (2023) Liu, X., Hu, L., Bailis, P., Stoica, I., Deng, Z., Cheung, A., and Zhang, H.  Online speculative decoding, 2023.
  * Nallapati et al. (2016) Nallapati, R., Zhou, B., dos santos, C. N., Gulcehre, C., and Xiang, B.  Abstractive text summarization using sequence-to-sequence rnns and beyond, 2016.
  * OpenAI (2023) OpenAI.  Gpt-4 technical report, 2023.
  * Schaefer et al. (2023) Schaefer, C. J., Guo, E., Stanton, C., Zhang, X., Jablin, T., Lambert-Shirzad, N., Li, J., Chou, C., Joshi, S., and Wang, Y. E.  Mixed precision post training quantization of neural networks with sensitivity guided search, 2023.
  * Sinha et al. (2022) Sinha, P., Guliani, A., Jain, R., Tran, B., Sinclair, M. D., and Venkataraman, S.  Not all gpus are created equal: characterizing variability in large-scale, accelerator-rich systems.  In _SC22: International Conference for High Performance Computing, Networking, Storage and Analysis_ , pp. 01–15. IEEE, 2022.
  * Treviso et al. (2023) Treviso, M., Lee, J.-U., Ji, T., van Aken, B., Cao, Q., Ciosici, M. R., Hassid, M., Heafield, K., Hooker, S., Raffel, C., Martins, P. H., Martins, A. F. T., Forde, J. Z., Milder, P., Simpson, E., Slonim, N., Dodge, J., Strubell, E., Balasubramanian, N., Derczynski, L., Gurevych, I., and Schwartz, R.  Efficient methods for natural language processing: A survey, 2023.
  * Voita et al. (2019) Voita, E., Talbot, D., Moiseev, F., Sennrich, R., and Titov, I.  Analyzing multi-head self-attention: Specialized heads do the heavy lifting, the rest can be pruned, 2019.
  * Wei et al. (2023) Wei, J., Wang, X., Schuurmans, D., Bosma, M., Ichter, B., Xia, F., Chi, E., Le, Q., and Zhou, D.  Chain-of-thought prompting elicits reasoning in large language models, 2023.
  * Xia et al. (2022) Xia, M., Zhong, Z., and Chen, D.  Structured pruning learns compact and accurate models, 2022.
  * Zhou et al. (2023) Zhou, Y., Lyu, K., Rawat, A. S., Menon, A. K., Rostamizadeh, A., Kumar, S., Kagy, J.-F., and Agarwal, R.  Distillspec: Improving speculative decoding via knowledge distillation, 2023.

##  Appendix A Max-Gram Implementation

Listing 1: Max-Gram Algorithm

⬇

1def torch_index(t, value):

2 return (t == value).nonzero(as_tuple=True)[0][0]

3

4

5def max_gram(input_ids, encoder_ids, n=1):

6 matches = (encoder_ids[0] == input_ids[0, -1]).int()

7 if matches.sum() < 1:

8 return None

9 for i in range(2, input_ids.shape[-1] + 1):

10 new_matches = (encoder_ids[0, :(-1 * (i - 1))] == input_ids[0, -1 *
i]).int()

11 combined_matches = (2 - new_matches == matches[1:]).int()

12 if combined_matches.sum() < 1:

13 index = torch_index(torch.cat(

14 (

15 torch.tensor([0] * (i - 1), device=torch.device(encoder_ids.device)),

16 matches

17 ),

18 dim=-1

19 ), 1)

20 return encoder_ids[:, index:index + n]

21 else:

22 matches = combined_matches

23 index = torch_index(torch.cat((

24 torch.tensor([0] * (encoder_ids.shape[-1] - matches.shape[-1])), matches),
dim=-1

25 ), 1)

26 return encoder_ids[:, index+1:index + n+1]

##  Appendix B Proof and Analysis of Theorem 4.4

We first prove a lemma that helps the proof of theorem 4.4

######  Lemma B.1.

$\forall a,b,c,d\in\mathbb{R}_{>0},\gamma\in(0,1)$

$\frac{\gamma a+(1-\gamma)b}{\gamma
c+(1-\gamma)d}\leq\max(\frac{a}{c},\frac{b}{d})$

###### Proof.

Without loss of generality, assume $\frac{a}{c}\geq\frac{b}{d}$,

$\frac{a}{c}\geq\frac{\gamma a+(1-\gamma)b}{\gamma c+(1-\gamma)d}$

$\Longleftrightarrow a(\gamma c+(1-\gamma)d)\geq c(\gamma a+(1-\gamma)b)$
$\Longleftrightarrow(1-\gamma)ad\geq(1-\gamma)cb$
$\Longleftrightarrow\frac{a}{c}\geq\frac{b}{d}$

∎

#### Proof of Theorem 4.4

###### Proof.

Let $\alpha_{d_{1}},\alpha_{d2}$ and $c_{d_{1}},c_{d2}$ be the acceptence rate
and cost ratio for model $d_{1},d_{2}$ respectively. Without loss of
generality, we assume $\alpha_{d_{1}}>\alpha_{d2}$ and $c_{d_{1}}>c_{d2}$ Then
the system satisfies $\alpha_{i}=f(i)\alpha_{d_{1}}+(1-f(i))\alpha_{d_{2}}$
and $c_{i}=f(i)\alpha_{d_{1}}+(1-f(i))c_{d_{2}}$ We prove using contradiction.
Assuming all optimal systems need at least one interpolation of models at some
positions. Let an optimal system of $f$ given $d_{1},d_{2}$, Without loss of
generality, assume $r$ to be the first indices such that $f(r)$ not being an
integer and the system $f$ to be the one with largest $r$ among all optimal
systems.

$T(k,{\alpha_{1},...,\alpha_{k}},{c_{1},...,c_{k}})=\frac{\alpha_{r}(1+\sum_{i=r+1}^{k}\prod_{j=r+1}^{i}\alpha_{j})+\sum_{i=0}^{r-1}\prod_{j=1}^{i}\alpha_{j}}{1+c_{r}+\sum_{i=1,i\neq
r}^{k}c_{i}}$

$=\frac{(f(r)\alpha_{d_{1}}+(1-f(r))\alpha_{d_{2}})(1+\sum_{i=r+1}^{k}\prod_{j=r+1}^{i}\alpha_{j})+\sum_{i=0}^{r-1}\prod_{j=1}^{i}\alpha_{j}}{1+f(r)c_{d_{1}}+(1-f(r))c_{d_{2}}+\sum_{i=1,i\neq
r}^{k}c_{i}}$

Let
$A_{1}=1+\sum_{i=r+1}^{k}\prod_{j=r+1}^{i}\alpha_{j},A_{2}=\sum_{i=0}^{r-1}\prod_{j=1}^{i}\alpha_{j}$

$=\frac{f(r)(\alpha_{d_{1}}A_{1}+A_{2})+(1-f(r))(\alpha_{d_{2}}A_{1}+A_{2})}{f(r)(1+c_{d_{1}}+\sum_{i=1,i\neq
r}^{k}c_{i})+(1-f(r))(1+c_{d_{2}}+\sum_{i=1,i\neq r}^{k}c_{i})}$
$\leq\max{(\frac{\alpha_{d_{1}}A_{1}+A_{2}}{1+c_{d_{1}}+\sum_{i=1,i\neq
r}^{k}c_{i}},\frac{\alpha_{d_{2}}A_{1}+A_{2}}{1+c_{d_{2}}+\sum_{i=1,i\neq
r}^{k}c_{i}})}$

This means that $f(r)=0$ or $f(r)=1$ will result in a time improvement factor
that is no less than that of a non-integer $f$, indicating that replacing
$f(r)$ with an integer will still yield an optimal system. This contradicts
the assumption that $f$ is the system with the largest $r$. As a result, there
exists an optimal system that does not require interpolation. ∎

Figure 3: Acceptance rate of draft tokens by their positions on MMLU datasets,
evaluated on FLAN-T5-small, base and large models.