SpaceByte: Towards Deleting Tokenization from Large Language Modeling
Authors: Kevin Slagle
Venue: NeurIPS 2024 poster (2024)
Keywords: byte level language model
model architecture
tokenization
efficient pretraining
Primary area: natural_language_processing
TL;DR: SpaceByte is a byte-level autoregressive language model that roughly matches the performance of tokenized Transformers in compute-controlled experiments.

Abstract: Tokenization is widely used in large language models because it significantly improves performance. However, tokenization imposes several disadvantages, such as performance biases, increased adversarial vulnerability, decreased character-level modeling performance, and increased modeling complexity. To address these disadvantages without sacrificing performance, we propose SpaceByte, a novel byte-level decoder architecture that closes the performance gap between byte-level and subword autoregressive language modeling. SpaceByte consists of a byte-level Transformer model, but with extra larger transformer blocks inserted in the middle of the layers. We find that performance is significantly improved by applying these larger blocks only after certain bytes, such as space characters, which typically denote word boundaries. Our experiments show that for a fixed training and inference compute budget, SpaceByte outperforms other byte-level architectures and roughly matches the performance of tokenized Transformer architectures.

SpaceByte:
Towards Deleting Tokenization from Large Language Modeling
Kevin Slagle
Rice University kevin. kevin.slagle@riin saaiinssaallericeeded
Abstract
Tokenization is widely used in large language models because significantly improves performance. However, tokenization imposes several disadvantages, such as performance biases, increased adversarial vulnerability, decreased character- level modeling performance, and increased modeling complexity. To address these disadvantages without sacrificing performance, we propose SpaceByte, a novel byte-level decoder architecture that closes the performance gap between byte-level and subword autoregressive language modeling. SpaceByte consists of a byte-level Transformer model, but with extra larger transformer blocks inserted in the middle of the layers. We find that performance is significantly improved by applying these larger blocks only after certain bytes, such space characters, which typically denote word boundaries. Our experiments show that for a fixed training and inference compute budget, SpaceByte outperforms other byte-level architectures and roughly matches the performance of tokenized Transformer architectures.
Introduction
Most language models are trained using tokenization, which partitions text into tokens that typically consist words or subwords. Tokenization is useful because significantly decreases the inference and training computational costs of large language models. However, tokenization also imposes several disadvantages. including performance penalties for languages that are priortizes less by the tokenizer [1-3]; increased vulnerability adversarial attacks [4]; and worse character-level modeling performance [5, 6]. and additional model complexity."
Recently, MegaByte [7], MambaByte [6]. and more [8-12] have been proposed as new byte-level autoregressive language models that model bytes instead of tokens. (See [13-21] for encoder and encoder-decoder byte-level modeling.) To address the longer context size resulting from modeling bytes instead of tokens, MegaByte uses multiscale modeling [22-24], while MambaByte uses Mamba blocks [25] instead of Transformer blocks. But although MegaByte and MambaByte have been shown to perform better than a standard byte-level Transformer, to our knowledge, no byte-level autoregressive large language model architecture has been shown to match the performance of tokenized models when controlling for compute costs.
In this work, we study the performance of byte-level and subword-level autoregressive models when trained using fixed compute budget. We measure the performance in terms of the cross entropy (measured in bytte), which has been shown to be strong predictor of down-stream performance [26]. In addition to controlling for training compute, we also control for inference compute costs (measured in FLOPs). We find that byte-level Transformer and MegaByte models can require roughly times more training FLOPs to achieve the same performance as a subword-
See also Andrej Karpathy's 's tweet twitter.com/knatt woutbbb.ooowwcccii-ddduuuftttatt
and video
the disadvantages of tokenization.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

S
e
y
de-embedding
@
x local transformer blocks
LyauX global transformer blocks
L
local transformer blocks
embedding
Figure 1: An overview of the SpaceByte architecture. The embedding, local transformer blocks, and de-embedding (i.c. a layer norm and linear) are the standard Transformer decoder layers. SpaceByte modifies the standard transformer by applying "global" transformer blocks only after certain bytes, such as space characters. The intuition is that the first character of word is typically the hardest to predict; thus this positioning of the global blocks should make the best use of the global blocks (which use a larger model dimension).
level Transformer. To close this substantial performance gap, we propose a new byte-level decoder architecture: SpaceByte.
SpaceByte also utilizes multiscale modeling to improve efficiency by grouping bytes into patches. But unlike MegaByte, which uses fixed patch size, SpaceByte uses simple rule to dynamically partition the bytes into patches that are aligned with word and other language boundaries. Our compute-controlled experiments show that this simple modification is crucial for performance, allowing SpaceByte to outperform other byte-level architectures and roughly match the performance of subword Transformers across variety of text modalities.
Our experiments are performed on datasets consisting of English books, LaTeX formatted arXiv papers, and open-source code. For other data modalities, SpaceByte with our simple patching rule might not be as effective.
2 SpaceByte
The SpaceByte architecture is summarized in Figure of as a byte-level Transformer model, but with extra "global" transformer blocks (with a larger model dimension) inserted the middle, which are only applied a fraction of the time. While the MegaByte architecture applies the global transformer blocks every P ~ 8 bytes, we hypothesize that this fixed spacing hinders performance. Our intuition that the first character of word is typically significantly harder to predict than the following characters. We therefore expect that performance can be improved by applying the global blocks primarily word boundaries.
nutshell, SpaceByte can be thought
Global Block Insertion Rule In this work, we consider very simple rule to dynamically decide when to apply the global blocks. We assume that the text bytes encoded using the UTF-8 encoding. We define a byte to be spacelike if the byte does not encode letter, number, or UTF-8 continuation bytc?. We apply the global blocks after any spacelike byte that not preceded by another spacelike byte (and after any BOS token). See Figure 2 for examples.
The most common spacelike byte the space character. Thus, the global blocks applied most word, which we expect is the hardest character to predict [27] in given word. With fixed patch size (e.g. in MegaByte), the global blocks are typically inserted in the middle a word, which we expect is inefficient because predicting the rest of the word could likely be more efficiently accomplished using the local blocks. We define continuation bytes to be spacelike so that languages that do not use spaces between words can still benefit from the global blocks between multi-byte characters (e.g. Chinese characters consists of three bytes UTF-8).
frequently to predict the first character
2UTF-8 uses a variable number of bytes to encode a character. English letters or numbers consist of a single byte. Characters that are encoded using multiple bytes are encoded using leading byte (which is spacelike by definition) followed by
continuation bytes (which not spacelike).

---

PG-19:
mmm I
the eee he exclaimed. "eeTheir capture must be prevented. Come with
arXiv:
pommmnnrrii 0 kkappa
where $g \kpppp and $V _V_1=V_2-\dota v V_>kappaš. In this way,
Github:
exp += 2;44
mbf [3] e
mbf [2] sigg
(ieee & 0x7f);
Examples of patch boundaries from datasets that we study. Spacelike bytes are underlined and colored blue. Patches boundaries drawn above the text. Each patch ends after spacelike byte that is not preceded by another spacelike byte. Consequently, each patch begins with zero or more spacelike bytes, followed by one more non-spacelike bytes, and ends with single spacelike byte. The global blocks predict the first character of each patch. The downward arrow (l) denotes newline byte. The left and right quotation characters, (*) and (") the PG-19 example, are encoded using three bytes in UTF-8. The first of the three bytes is spacelike, while the later two bytes are UTF-8 continuation bytes, which are not spacelike and are each denoted using bullet point (*) above.
Figure 2:
Although this very simple "spacelike" rule is likely the optimal rule, find that it works surprisingly well in practice for English text, LaTeX formatted papers, and code. Nevertheless, critical future direction to optimize [28, 14, 9] better rules using data rather than our simple heuristic.
applied often the local transformer blocks, it advantageous to use a larger model dimension for the global transformer blocks. To increase the dimensions of activation vector before the global blocks, simply pad the activation vector with zeros. To decrease the dimension, we truncate the activation vector.
Important Details Since the global blocks
In our experiments, we use significantly larger context size than the model dimension Diocal of the local transformer blocks. To prevent the attention mechanism from dominating the compute costs for the local model, we use attention window [29-31] of length Diocal for the local transformer blocks. The global blocks use a global attention that attends to all other global blocks.
See Appendix C for pseudocode. Additional details specific to our experiments are provided in Sections 4.1 and 4.2 and Appendix A.
Related Work
The most straight- forward consequence of modeling bytes instead of subword tokens is that the length of sequence typically increases by about factor of four. This increased sequence length increases the training and inference compute cost for modeling a given long sequence text for a Transformer due to the quadratic scaling of attention.
The MegaByte architecture strives to use multiscale Transformer modeling to lessen these performance issues. In particular, MegaByte groups bytes into patches of fixed patch size P. Each patch bytes is vectorized and then fed into "global" Transformer model. The output of the global model is then fed into "local" Transformer model that autoregressively outputs byte-level logits. [7]
MegaByte
For context size of T bytes, MegaByte's global Transformer model compresses the context into only Ty patches, which can significantly decrease the compute cost for modeling long sequences. Similar to et [7], we also find that MegaByte outperforms a standard byte-level Transformer. However, we find that MegaByte's performance is remarkably close to stronger byte-level Transformer baseline that simply uses a sliding window attention mechanism [29-31] to increase the context size without increasing the compute costs.
3

---

Yu et al. [7] do not compare MegaByte to subword-level Transformer in compute controlled experiments. In our compute controlled experiments, we find that MegaByte's performance significantly lags behind subword-level Transformer.
Compared MegaByte, SpaceByte makes the crucial change that patches are dynamically sized be commensurate with the text, e.g. with word boundaries. We also add an additional local model before the global model (while MegaByte only utilizes single local model after the global model) to help the model deal with the dynamical patch sizes. We also use significantly longer attention windows for our local models. We find that these changes allow SpaceByte to significantly improve upon the performance of MegaByte and roughly match the performance of subword-lews Transformers.
MambaByte The MambaByte architecture [6] takes alternative approach to avoiding the quadratic compute scaling of the attention mechanism by replacing the Transformer block with a Mamba block [25]. Wang et al. [6] find that their byte-level MambaByte models outperform byte-level Transformer and byte-level MegaByte models. They perform one controlled experiment with a subword model, where they find that MambaByte slightly outperforms Mamba (using tokens) when controlling for the amount of model parameters and training data (which was 14 epochs of the PG-19 dataset). But this experiment was not controlled for compute as MambaByte was trained using roughly four times as much compute than Mamba. We view the Mamba and MambaByte architectures as complementary to our work, as the Mamba block could be integrated into SpaceByte (or MegaByte) place of Transformer blocks.
Layer Skipping SpaceByte could be though of as Transformer that employs novel kind of text-dependent layer skipping [32-38] on the middle layers.
Word Boundary Prior works have shown utility in using word boundaries to partition patches for autoregressive multi-scale byte-level modeling [9, 8, 11] (and also [18] for encoder-decoder modeling). However, these works did not compare autoregressive byte-level models to subword- level models, nor did they identity patch partitioning rule that could generically be applied to UTF-8 encoded text. Our primary contributions beyond these prior works is to show how to scale word-boundary byte-level modeling to more diverse text modalities while roughly matching the performance of subword-level models in compute- compute-controllic controlled experiments.
Nawrot et al. [9] and Fleshman and Van Durme [11] make use of the Hourglass Transformer architecture [23]. The SpaceByte architecture is similar to the Hourglass Transformer, except SpaceByte uses a simpler technique for shortening and upscaling the activations before and after the
global blocks, and SpaceByte uses sliding window attention [29-31] in the local blocks to improve
performance for long context sizes.
4 Experiment Setup
Our experiments compare the performance of our byte-level SpaceByte architecture to subword- level Transformer and byte-level Transformer and MegaByte architectures. To fairly compare the performance between the byte and subword level models, we measure the cross-entropy of the test dataset terms of bits- bits-per-byte. Given the substantial variation in inference compute costs across the models we study, we also compare their inference compute costs to provide a more comprehensive simple software and hardware-indepennde
evaluation. We use FLOPs-per-bye inference compute costs, which is the number of FLOPs (see Appendix A. 1) required to model byte of text."
proxy for
Note that by controlling for both total training compute and FLOPs -er-s-per-byte, we are also controlling for the amount of training data since (bytes trained) = (training FL.OPs) /(rainiig FI.OPs-per-byee The Peoss-eer-byte during training is equal to three times the Fe.OP--ee-bytte during inference (due to the backwards pass during training).
'The bits-per-hyte (BPB) is equal to BPB = XE Nosem/ / (Noynes In 2), i.e. the cross entropy per token (XE) times the number of tokens per byte (Nuaann/Nvee divided by In (to convert nats to bits). Nuken and Nuyts are the number of tokens and bytes in the dataset, respectively. For byte-level models, Nesten = Noyees since bytes are used in place of tokens.
"We note that in order for memory bandwidth to not be bottleneck during inference, the batch size must be sufficiently large and e.g. grouped-query attention [39, 40] must be used.

---

We therefore study the Pareto frontier of lowest bits-per- per-byte and lowest FLOPs-per-byle We train all models using a compute-controlled setup, using either 10 or 10 FLOPs. In order to effectively explore this Pareto frontier, we train models using grid of different model dimensions and numbers of layers, as specified in Appendix B.3.
Datasets Following the MegaByte [7] and MambaByte [6] experiments, we benchmark our models on a diverse range of long-form datasets: PG-19 (English-language books written before 1919) [41]; arXiv (papers from ArXiv written in LaTeX, extracted from the arXiv component of The Pile [42];; and Github (open-source code repositories, extracted from the Github component of The Pile [42].
4.1 Models
The models we study tend to perform best when the compute cost is roughly evenly split between the attention and feedforward layers. To ensure this, we fix the context size (or attention window) to be equal to the model dimension for every layer. We detail our model setup below.
Notation For all models, we use T to denote the context length, and D to be the model dimension (of the global model for SpaceByte and MegaByte).
For SpaceByte and MegaByte, Dincal is the dimension of the local model, and Tglobal is the maximum context size for the global model. The patch size P is the number of bytes between global blocks. If the patch size is fixed (which is always the case for MegaByte), we naturally set the context size to be =
glabal.
Below, we describe each of the model architectures that we compare in our experiments.
SpaceByte We fix the global context size and global model dimension to be equal, Tglobal D, and we set the local attention window Vocal equal to the local model dimension, W Voeal = D For the PG-19 and arXiv datasets, the average patch size is roughly 6, take T = 6T globba for these datasets; for the Github dataset, the average patch size is roughly 8, so we instead take T = gioal
for the Github dataset.
For simplicity, we fix the number of global transformer blocks Lygobaal to be equal to the total number (2)
of local blocks, Local + L locar and evenly split the number of local blocks before (I((ea) and after local) the global blocks, i.e. we fix L L Lgloball
SpaceByte (fixed patches) To clearly demonstrate the utility of dynamically aligning patch boundaries in SpaceByte, we also train a simplified version SpaceByte where the patches all have a fixed size. In order roughly match SpaceByte's 's average patch size, we take the fixed patch size to be P = 6 for all datasets except for the Github dataset, for which we use P = 8. We again use T "glohal D and T globba-
Byte-level Transformer For a simple baseline comparison (following Yu et al. [7]), we train byte- level Transformer models. We take the context size to be equal to the model dimension, T 7= D.
Note that in our setup, Transformer with model dimension D only sees a context size of D, which is significantly smaller than the context size of PD for SpaceByte (and MegaByte) with patch size P.
Byte-level Transformer (Window Attention) Since shorter context is significant disadvantage for long-form datasets, we also compare against a stronger Transformer baseline that uses a sliding window attention [29-31] ]] to efficiently increase the context size without increasing compute costs. We train each window attention enhanced Transformer using a context size T PD and a sliding attention window size equal to D, with P 6 for all datasets except for the Github dataset for which P 8.5
MegaByte We also compare to MegaByte [7]. Although MegaByte was originally trained using patch size of P = 8, we found that a patch size of P = 4 was often better in our setup. We thus include both of these patch sizes (4 and 8) in our hyperparameter grid for MegaByte. For simplicity, we fix the number of layers in the global and local blocks to be equal, Lgtobal = Lieaal which is close
'We also tried a simplified Sparse Transtormer [30] where the first attention layer uses a sliding attention window of size D; the second attention layer uses a strided attention with stride P:: and the remaining layers continue to alternate between sliding and strided attention. However in our setup, we found this to perform worse than just using sliding window attention.
5

---

Table 1: Best bits-per- Lowest bits-per-byte for each model architecture when trained using 10 FLOPs on different text modalities. The lowest bits-per-byte for each dataset are underlined; and the lowest within 2.5% are bolded. The largest statistical error (due to a finite number of evaluation samples) is 0.4%. SpaceByte significantly outperforms other byte-level architectures and performs on par with the SentencePiece subword Transformer.
Model
PG-19
arXiv
Github
byte-Ievel subword
Transformer (GPT2 tokenizer)
1.013
0.796
0.554
Transformer (SentencePiece)
0.989
0.768
0.508
Transformer
1.138
0.909
0.655
Transformer (Window Attention)
1.089
0.818
0.560
MegaByte
1.083
0.822
0.570
SpaceByte (fixed P)
1.112
0.804
0.552
SpaceByte
1.009
0.748
0.500
what was used by Yu et [7]. Similar to SpaceByte, we set the context size to T PD, where D is the global model dimension.
Subword Transformers Our most important baseline is the standard subword Transformer. We train subword Transformers using two different tokenizers (hoth with a vocahulary size of 50,257): (1) the GPT2 tokenizer [43], and (2) SentencePiece [44] tokenizer using hyte-pair-encoding model [45] that was separately trained for each dataset. As usual, we set the context size to be equal to the model dimension, T' D.
4.2
More Details
We use fairly standard Pre-LN [46, 30, 47] Transformer [48] blocks with no bias terms. Since MegaByte uses Rotary Position Embedding (RoPE) [49], we also use RoPE for all models (which slightly improves the loss). To prevent loss divergences during training, we use gk-layernorm [50-52] (which we strongly recommend) for all models; i.e. add an extra layer-normalization the query and key vectors the self-attention layers.
All hyperparameters have been carefully tuned using grid and random searches. See Appendices A and B for more details.
Results
We now present our experimental data comparing the different model architectures in compute- controlled settings. Figure plots the Pareto frontier of lowest cross-entrops bits-per-byte and lowest FLOPs-per-byte (i.e. inference compute cost) for each architecture and training compute budget. We assume that the Pareto frontier is convex. Thus, for each architecture and compute budget, we perform grid search line connecting the best (i.e. minimal subset of) models such that all other models (not shown in figure) lie above and to the right of the line. Table I summarizes the results for the lowest overall bits-per-byte for each architecture.
model dimension and number of layers; we then draw a piecewise-linent
Across all datasets, training compute budgets, and inference compute budgets (i.e. FLOPs-per-byte), SpaceByte significantly outperforms all other byte-level architectures. SpaceByte also consistently outperforms the subword Transformer when using GPT2 tokens, and by wide margin the arXiv and Github datasets. SpaceByte roughly matches the performance of the most competitive baseline, the subword Transformer using the SentencePiece tokenizer, with SpaceByte performing slightly better on the arXiv and Github datasets. Figure also suggests that SpaceByte's performance improves faster than the subword Transformer as the training compute budget increases.
Byte-level architectures other than SpaceByte perform significantly worse than SpaceByte or the SentencePiece Transformer. For example, for PG-19, the next best byte-level architecture is
"Our training code and data reproduction steps can be found gichub.com///slngssppeeyee

---

14
subword-ievel.
1.4
Transformer
1.3
(GPT2 tokenizer)
Transformer (SentencePlece)
byte-level:
cros-entropp
Transformer
Transformer
(Window Attention)
1.1
MegaByte
SpaceByte
P)
SpaceByte
1.0
10"
10"
inference FLOPs-per-byte
(a) PG-19 dataset
subword-level:
Transformer
cross-enrrpy (bits-per-byte
(GPT2 takenizer)
Transformer (SentencePiece)
byte-level:
Transformer
0.9
Transformer
(Window Attention)
MegaByte
SpaceByte
0.8
P)
SpaceByte
107
10"
inference FLOPs-per-byy
(b) arXiv dataset
1.0
subword-level:
Transformer
cross-entropy (ils-per-byte)
(GPT2 tokenizer)
Transformer
0.8
(SentencePiece)
byte-level:
Transformer
Transformer
(Window Attention)
0.6
MegaByte
SpaceByte
P)
SpaceByte
0.5
10'
10a
inference FLOPs-per-byle
Githuh dataset
Figure Pareto frontier the cross-entropy bits-per-byte* vs FLOPs-per-bytee during inference (details in Appendix A. for each model architecture trained using 1018 (connected by thin lines) or 10 (thick lines) FL.OPs on different datasets (on a log-log scale). Each dot describes model with different number of layers and/or model dimension. Lower and to the left is better. SpaceByte (red) outperforms all other byte-level architectures across the entire Pareto frontier for all datasets. SpaceByte roughly matches the performance of the subword Transformer using SentencePiece tokens, and outperforms the subword Transformer using GPT2 tokens.
7

---

Table 2: Comparison with other works. We compare SpaceByte to byte-level models trained in other works, along with a subword transformer that we train. All models are trained using roughly the same inference FLOPs-per--e and MegaByte models are taken from Yu et al. [7], while MambaByte results are taken from Wang et al. [6]. The best bits-per-byte for each dataset are underlined; and the lowest within 3% are bolded. The largest 1-sigma statistical error (due to finite number of evaluation samples) for the models we train is less than 0.001. SpaceByte is the overall best performing byte-level model and consistently performs within a few percent of the subword Transformer.
(= 728M). The bits-per-byte for the Transformer, PerceiverAR,
These models used slightly different datasets for training and/or testing. For MambaByte-352M
we estimate that this difference very roughly amounts to an extra 3% statistical error.
Context size
Data trained
Test bits- bits-per-byte +
Model
PG-19
Stories
arXiv
Github
2048
subword
tokens
30B*
Transformer-I1
0.908
0.809
0.666
0.400
8192
bytes
bytes
Transformer:320M [7]
1024
80B
1.057
1.064
0.816t
0.575
byte-level
PerceiverAR-248M [7]
8192
80B
1.104
1.070
0.791
0.546t
MegaByyce775MM+222M [7]
8192
80B
1.000
0.978
0.6781
0.411
MambaByte-353M [6]
8192
30B
0.930
0.908t
0.663
0.396
SpaceByte-7933+-14M
8192
30B*
0.918
0.833
0.663
0.411
(bytes)
(bytes)
MegaByte; however, MegaByte trained using 10 FLOPs (thick green line in Figure 3a) performs worse across nearly the entire Pareto frontier than the SentencePiece Transformer trained using only 10% as many training FLOPs (thin black line). Although the standard byte-level transformer (which the primary baseline used by Yu et al. [7], blue in Figure 3) performs significantly worse than the other byte-level models, we note that by simply using a sliding window attention mechanism to increase the context size more closely match that of the other byte-level models, this stronger baseline (purple) performs almost as well as MegaByte. Nevertheless, SpaceByte still significantly outperforms this stronger baseline.
To verify the importance of dynamic patch sizes for SpaceByte's 's performance, we compare SpaceByte to variant of SpaceByte with fixed patch sizes (orange in Figure 3). We observe that fixing the patch size significantly degrades the performance of SpaceByte.
Note that on the arXiv and Github datasets, the subword Transformer performs significantly worse when using GPT2 tokens (which were trained on WebText [43]) than SentencePiece tokens (which were trained using the specific dataset). This exemplifies the bias that tokenization can introduce on data distributions different from what the tokenizer was trained on.
6 Comparison with Other Works
We also compare SpaceByte performance to byte-level models trained in other works. Yu et al. [7] trained Transformer, PerceiverAR, and MegaByte models, each using the same amount of compute, FLOPs FLOPs-per-bytee bet-b and data (80B bytes). Wang et al. [6] additionally trained a MambaByte model using the same FLOPs-per-byte but only 30B bytes of data. We train 7eMecBByte-93M+11AM (D 1536, Dioeal = 768, Liocal 26, Lglobal = 28) using roughly the same inference FLOPs-per-byte (728M) but also only 30B bytes of data (following Wang al. [6]). Training these models thus requires roughly 3 x 728M FLOPs-per-byte x 30B bytes ze 6.5 x 10 FLOPS, where the factor three comes from converting inference FLOPs-per- to training FLOPs-per-be
(which additionally requires a backwards pass). For this experiment, we set the context size of SpaceByte to 8192 bytes to follow the prior works. See Appendix A for more details.
We also train subword Transformer- 1B (D = 1536) models using the SentencePiece tokenizer (except for the Stories dataset, for which we use the GPT2 tokenizer). The average number of bytes per token
8

---

for the PG-19, Stories, arXiv, and Github datasets are 4.05, 4.39, 3.73, and 3.31, respectively. To match the per of the subword Transformer- 1B models to the byte-level models, we set the number of layers to 40, 44, 37, or 31, for Transformer- 1B on these four respective datasets.
Results shown in Table 2. We show experiments for the PG-19 [41], Stories [53], arXiv (extracted from The Pile [42]), and Github (extracted from The Pile [42]) datasets." Yu et al. [7] used proprietary
"arXiv" and "Code" datasets, which we do not have access to. Following Wang et al. [6]. we compare Yu et al. [7]'s results to the similar (but likely slightly different) arXiv and Github components of on
The Pile [42]. However, Wang et al. [6] use their own test splits evaluate MambaByte-3555 Stories, arXiv, and Github. Due to the rather small test splits (~ 100MB for the arXiv and Github datasets), this difference can be significant. For example. the validation (and test) bits-per-bye for 19eceByyte793M+1155
on the Stories, arXiv, and Github datasets are 0.877 (0.833), 0.658 (0.663) and 0.397 (0.411), which differ by +5%, - 1%, and -3,, respectively. Given this variation, the bits-per-byte of MambaByte-353M. and 7933 184M are not statistically different on the arXiv or Github datasets.
Overall, we find that SpaceByte outperforms the byte-level models trained in other works. SpaceByte outperforms MegaByte, even though MegaByte was trained using 2.7 times as much compute and data. Moreover, SpaceByte's performance is competitive with the subword Transformer-IBB.
Conclusion
We have proposed new byte-level Transformer decoder architecture, SpaceByte. Our compute- controlled experiments show that SpaceByte outperforms all other byte-level architectures and roughly matches the performance of sub-word level Transformers.
Limitations SpaceByte uses a simple byte partitioning rule that relies on "spacelike" bytes, such as spaces which typically denote word boundaries. As such, SpaceByte should not be expected to perform well on arbitrary sequences of bytes, such as images or audio. Some languages, such as Chinese, do not use spaces between words. SpaceByte is somewhat robust to these languages, since e.g. Chinese characters are encoded using three bytes in UTF-8, which SpaceByte will group together. However, our preliminary experiments suggest that SpaceByte performs worse than subword transformers on Chinese text. It would therefore be desirable to improve upon and generalize SpaceByte's 's global block insertion rule.
The variable spacing between global blocks makes it more challenging to design and implement an efficient batched inference sampling algorithm for SpaceByte.
Future Work SpaceByte uses multiscale modeling where the local model operates on bytes while the global model typically operates on words. Another natural extension of our work is to try recursively applying multiscale modeling at even longer scales, such the sentence paragraph level. It would also be fruitful to investigate if Mamba blocks [25] could further improve SpaceByte's performance.
Acknowledgments and Disclosure of Funding
We thank Tushaar Gangavarapu, Junxiong Wang, and Lili Yu for helpful conversations. This work was supported in part by the NSF Campus Cyberinfrastructure grant CC Compute: Interactive Data Analysis Platform OAC-201900 and by Rice University's Center for Research Computing (CRC).
References
[1] J. Pourmostafa Roshan Sharami, D. Shterionov, and P. Spronck. A Systematic Analysis of Vocabulary and BPE, Settings for Optimal Fine-tuning of NMT; A Case Study of In-domain Translation. March 2023. doi: 00.48550/axii.2233..000
[2] Aleksandar Petrow, Emanuele La Malfa, Philip Torr, and Adel Bibi. Language model tokenizers introduce unfairness between languages. In sevenhh Conference on Neural Information Processing Systems. http://rrmmiddd/y111100000
2023. URL https:
YYu et al. [7] and Wang et al. [6] also show results for a "Books" dataset [42] derived from Books3 (which similar to PG-19 19 but also includes modern books). However, the legality of obtaining Books3 is questionable due copyrights. We consequently exclude comparisons to this dataset.

---

[3] Orevaoghene Ahia, Sachin Kumar, Hila Gonen, Jungo Kasai, David Mortensen. Noah Smith. and Yulia Tsvetkov. Do all languages cost the same? tokenization in the era of commercial language models. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing. 10. 181638/1/202233
Singapore, December 2023, Association for Computational Linguistics. doi: pages emmlpp- main.614. URL
wwwpooologyoogg///ae org/2023 wwt.2222..........mmmmmmmmmm emnlp main. .644
[4] Jessica Rumbelow and mwatkins. Solidgoldmagiiarrp (plus, prompt generation) 2023. URL https: //www. lesswrong. cww.coo////o/oo www/posts////cccoccccccooossssss pwwps//aeeeeepoopoooppppppeeppe aPe Att.e///ioot....oogggg//goaaaa/a
plus- pro.pt-eneetttttoonnn
[5] Peter Welinder, May 2022. URL http:////..aaaaae...o///////aaap
[6] Junxiong Wang. Tushaar Gangavarapu, Jing Nathan Yan, and Alexander M Rush. MambaByte: Token-free Selective State Space Model. January 2024. doi: 10.485500/aXiv.44000 13660.
[7] Lili Yu, Daniel Simig, Colin Flaherty, Armen Aghajanyan, Luke Zeutlemoyrr and Mike Lewis. MegaByte: Predicting Million-byte byte Sequences with Multiscale Transformers. In seventh Conference on Neural Information Processing Systems, 2023. URL /ttttts://oppereiieeeee
[8] Avijit Thawani, Saurabh Ghanekar, Xiaoyuan Zhu, and Jay Pujara. Learn your tokens: Word-pooled tokenization for language modeling. In Conference on Empirical Methods in Natural Language Processing, 2023, URL https: //tp:////////eee////ee http:pppwwwe.eeeeeeeeeoooooaaaaa wttp://ooooo//dddod/rr//
[9] Piotr Nawrot, Jan Chorowski, Adrian Lańcucki, and Edoardo M. Ponti. Efficient Transformers with Dynamic Token Pooling. art. arXiv:221 0e.222211.97766 1.09761, November 2022. doi: 10.48550/arXiv.2211
[10] Brian Lester, Jachoon Lee, Alex Alemi, Jeffrey Pennington, Adam Roberts, Jascha Sohl- Dickstein, and Noah Constant. Training LLMs over Neurally Compressed Text. art. arXiv:2404.03626, April 2024.
[11] William Fleshman and Benjamin Van Durme. Toucan: Token-Aware Character Level Language Modeling. arXiv e-prints, art. arXiv:231 L.W:231,.08620, November 2023. doi: 10.48550/arXiv.2311..00
[12] Tomasz Limisiewicz, Terra Blevins, Hila Gonen, Orevaoghene Ahia, and Luke Zettlemoyer. MYTE: Morphology-Driven Byte Encoding for Better and Fairer Multilingual Language Modeling. arXiv e-prints, art. arXiv:2403.1 10691, March 2024. doi: 10 10.48550/arXiv24000 10691.
[13] Linting Xue, Aditya Barua, Noah Constant, Rami Al-Rfou, Sharan Narang, Mihir Kale, Adam Roberts, and Colin Raffel. ByT5: Towards foken-free future with pre-trained byte-to-byte models. Transactions of the Association for Computational Linguistics, 10:291-306, 2022. doi: 10. 10.1162/tacl.1.... 00006.1 URL
org//o/2/ tac1-1.17.
[14] Nathan Godey, Roman Castagné, Éric de la Clergerie, and Benoît Sagot. MANTa: Efficient Gradient- Based Tokenization for Robust End-to -od Language Modeling. art. arXiv:2212.072M. December 2022. doi: 10. 14455500a2xi.22222.7733
[15] Jonathan H. Clark, Dan Garrette, Iulia Ture, and John Wieting. CANINE: Pre-training an Efficient Tokenization-Free Encoder for Language Representation. art arXiv:2103.06874, March 2021. doi: 0.485500aaxi.22003.066744
[16] Hicham EI Boukkouri, Olivier Ferret, Thomas Lavergne, Hiroshi Noji, Pierre Zweigenbaum, and Jun'ichi Tsujüi. CharacterBERT: Reconciling ELMo and BERT word-level open- vocabuaayyy representations from characters. In International Committee on Computational Linguistics, pages 6903- 6915, Barcelona. Spain (Ouline), December 2020. doi: 118855//122200.conngg http:/0000..iingaaaa..000000 main URL
https: https://aclest httes///acaaaahhllgeeoe orgo 00g/2020..r col2on....nn.................... main maain.600 609.
[17] Yi Tay, Vinh Q. Tran, Schastian Ruder, Jai Gupta, Hyung Won Chung, Dara Bahri, Zhen Qin, Simon Baumgartner, Cong Yu, and Donald Metzler. Charformer: Fast Character Transformers via Gradient-based Subword Tokenization. art. arXiv:2106.1 12277,, June 2021.
doi: 10.48550/arXi.221066.
[18] Lukas Edman, Antonio Toral, and Gertjan van Noord. Subword-Delimited Downsampling for Better Character-Level Translation. art. arXiv:2212.01304 December 2022. doi: 10.44850/arxx..2222...33 304..
[19] Makesh Narsimhan Sreedhar, Xiangpeng Wan, Yu Cheng, and Junjie Hu. Local byte fusion for neural machine translation. In Association for Computational Linguisticss pages 7199-7214, Toronto, Canada, July 2023. doi: 10. 18.53/v aal........oon..39999 URL
orgo atgg/023.addeea 1oel-long.333 397.
[20] Lukas Edman, Gabriele Sarti, Antonio Toral, Gertjan van Noord, and Arianna Bisazza. Are Character Translations Worth the Wait? Comparing ByT5 and mT5 for Machine Translation. art. axXiv:2302.1422) February 2023. doi: 10.48550/arxxv.2222.2222
10

---

[21] Kris Cao. What is the best recipe for character-level encoder-only modelling? art. arXiv:2305.05461 May 2023, doi: 10.48550kn2ii.22055.5544
[22] Sandeep Subramanian, Ronan Collobert, Marc'Aurelio Ranzato, and Y-Lan Boureau. Multi-scale Transformer Language Models, art. arXiv:2005.00881, May 2020. doi: 10:48500aXXi.2205.0088
[23] Piotr Nawrot, Szymon Tworkowski, Michal Tyrolski, Lukasz Kaiser, Yuhuai Wu, Christian Szegedy, and Henryk Michalewski. Hierarchical transformers are more efficient language models. Association, for Computational Linguistics, pages
Scattle, United States, July 2022. doi: 10. 18653/v1/2022. iidingg-naacl. 17. URL https: / http:///aaaaaatlooa//// wwwellogoyyoooogggeeee org/2022.. httg/222..innniiii.. findings- naacl. 117.
[24] Zihang Dai, Guokun Lai, Yiming Yang, and Quae V. Le. Franc-Trranfoommrr: Filtering out Sequential Redundancy for Efficient Language Processing. art. arXiv:2006.0333 03236, June 2020. doi: 10.48550/arXiv. 2006.03236.
[25] Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces, 2024. URL attps://openreviev..u
[26] Yuzhen Huang, Jinghan Zhang, Zifei Shan, and Junxian He. Compression Represents Intelligence L Linearly. art. arXiv:2404.09931, April 2024. doi: 10.48555VarXx..2244400099.
[27] Rami Al-Rfou, Dokook Choe, Noah Constant, Mandy Guo, and Llion Jones. Character level language modeling with deeper attfnttten AAAI, 2019. doi: 10.1609/aaii (6609aaaivv3300133330000 3330113301111159 //doi oro//.oorg/... 10. 1609/aaai. v33101.33013111.. 33013159.
URL https:
[28] Md Mofijul Islam, Gustavo Aguilar, Pragaash Ponnusamy, Clint Solomon Mathialagan, Chengyuan Ma, and Chenlei Guo. A vocabulary-free multilingual neural tokenizer for end-to-end task learning. Association for Computational Linguistics, May 2022. doi: 10. 10.18655//112022.rrpbhh...
URL
https://aclanthol..o www.ollyyyorrgg2222/2// http://00002222..p11111---- repp:e2-rrppn11p111111
[29] Iz Beltagy, Matthew F. Peters, and Arman Cohan. Longformer: The Long-Doeument Transformer. April 2020. doi: 10.485500/r2x1.22000.5555
[30] Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating Long Sequences with Sparse Transformers. April 2019. doi: 10.48550/arXiv. 1904. 10509.
[31] Ofir Press, Noah A. Smith, and Mike Lewis. Shortformer: Better language modeling using shorter inputs. In Association for Computational Linguistics, pages 5493-5505, August 2021. doi: 10. 10.18663/v1/2000 acl-Iong.427 427. URL htapp::s//aaaattholl..
org/2021. htt//2221.cc1111100. 427.
[32] Alex Graves. Adaptive Computation Time for Recurrent Neural Networks. art. 1rXiv:1603.08933, March 2016. doi: 00.48550/rrii.1163..om 160300883.
[33] Xin Wang, Fisher Yu, Zi-Yi Dou, Trevor Darrell, and Joseph E. Gonzalez. SkipNet: Learning Dynamic Routing in Convolutional Networks. art. arXiv:1711.09k0 November 2017. doi: 10.48550/arxiv.1111 09485.
[34] Andreas Veit and Serge Belongie. Convolutional Networks with Adaptive Inference Graphs. art. 1rXiv:1711.11500, November 2017. doi: 1..48500/rxii..111.111
[35] Zuxuan Wu, Tushar Nagarajan, Abhishek Kumar, Steven Rennie, Larry S. Davis, Kristen Grauman, and Rogerio Feris. BlockDrop: Dynamic Inference Paths in Residual Networks. art. November 2017. doi: 10.48 111.00//..ii.1111...
[36] Tal Schuster, Adam Fisch, Tommi Jaakkola, and Regina Barzilay. Consistent accelerated inference via confident adaptive transformers. In Association for Computational Linguistics, pages 4962-4979, Online and Punta Cana, Dominican Republic, November 2021. doi: 10. 00.18833/v1/222 http:///.21....m-.e.ee
comnlp-main.dee URL
https: httpp://aclanttoooggg org/2021. emnlp-mane main.
[37] Yizeng Han, Gao Huang, Shiji Song. Yang. Honghui Wang, and Yulin Wang. Dynamic Neural Networks: A Survey. art. arXiv:2102.04900 February 2021. doi: 10.485500arxii.2120..0444
[38] David Raposo, Sam Ritter, Blake Richards, Timothy Lillicrap, Peter Conway Humphreys, and Adam Santoro. -fepptte Dynamically allocating compute in transformer-based language models. art. arXiv:2404.02258. April 2024.
[39] Noam Shazeer. Fast Transformer Decoding: One Write-Head is All You Need. art. arXiv: M01.::9111002.00. 01.000050. November 2019. doi: 115550/a2ii..911..2222

---

[40] Joshua Ainslie, James Lee-Thorp Michiel de Jong, Yury Zemlyanskiy. Federico Lebron, and Sumit Sanghai. GQA: Training generalized multi-query transformer models from multi-head checkpoints. In Association for Computational Linguisties, pages 4895-4901, Singapore, December 2023. doi: 10. 118633/1/20233cmmllp m98. URL
wwwpo/logyyyogg///0/ org/2023. emnll- main. 2988.
[41] Jack W. Rae. Anna Potapenko. Siddhant M. Jayakumar, Chloe Hillier, and Timothy Lillicrap. Compressive transformers for long-range sequence modelling. In International Conference on Learning Representations, 2020. URL
net fortt//ormmmm/ weeee//oommiddyyyloolloe serriddssyyykkks
[42] Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima. Shawn Presser, and Connor Leahy. The Pile: 800GB Dataset of Diverse Text for Language Modeling. December 2020.
doi: 10.48550/rxx..2101.0000
[43] Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models unsupervised multitask leamers. 2019. URL //cdn. openai. cww coom/bbtter-rte http//btterlaannaageee models/ language serguaag__odess.ce modemsmddrrrrreeeee _arr___rr______ www.uupprrissee_mlliiieeeeeo learnerseeeeeeeeeeeeeeee pdf.
[44] Taku Kudo and John Richardson. SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing. Association for Computational Linguistics, pages 66-71, nov 2018. doi: 10. 10.18663/1/D118-200
URL
org/D18-2010
[45] Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units, In Association for Computational Linguistics, pages 1715-1725, August 2016. doi: 10. 1/688//1//11-111 162. URL
org/P16-1122
[46] Alexei Bacvski and Michael Auli. Adaptive input representations for neural language modeling. In International Conference on Learning Representations, 2019. URL https: httptpp:///ppeevviiii http://ppenerreeeeeeeefrrr. id id-ByxZX20qFQ.
[47] Qiang Wang, Bei Li. Tong Xiao, Jingbo Zhu, Changliang Li. Derek F. Wong, and Lidia Chao. Learning deep transformer models for machine translation. In Association for Computotional Linguistics, pages 1810-1822, July 2019. doi: 10. 10.18653/w1/199 176. URL http:: / //claa/tolllaaalogoooooo org/P19- 1176.
[48] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, L ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, volume 30, 2017.
[49] Jianlin Su, Yu Lu, Shengfeng Pan, Ahmed Murtadha, Bo Wen, and Yunfeng Liu. RoFormer: Enhanced Transformer with Rotary Position Embedding. April 2021. doi: 10. (0-48550/axxi.22144.0866
[50] Alex Henry, Prudhvi Raj Dachapally. Shubham Shantaram Pawar, and Yuxuan Chen. Query-key normalization transformers. Trevor Cohn, Yulan He. and Yang Liu, editors, Findings of the Association for Computational Linguistics: EMNLP 2020, pages 4246-4253, Online, November 2020. Association for Computational Linguistics. doi: 10. 2.118633/1/2020 12000.nn/.... findings-emmll.377. URL https://acceeee htapsss//aclanhhooogg org/2020..... 1::00...nma findings----ii .et.ggs--emlp.39......
[51] Mostafa Dehghani, Josip Djolonga, Basil Mustafa, Piotr Padlewski, Jonathan Heek, Justin Gilmer, Andreas Steiner, Mathilde Caron, Robert Geirhos. Ibrahim Alabdulmohsin. Rodolphe Jenatton, Lucas Beyer, Michacl Tschannen, Anurag Arna,, Xiao Wang, Carlos Riquelme, Matthias Minderer, Joan Puigcerver, Utku Evci, Manoj Kumar, Sjoerd van Steenkiste, Gamaleldin F. Elsayed, Aravindh Mahendran, Fisher Yu, Avital Oliver, Fantine Huot, Jasmijn Bastings, Mark Patrick Collier, Alexey Gritsenko, Vighnesh Birodkar, Cristina Vasconcelos, Yi Tay, Thomas Mensink, Alexander Kolesnikov, Filip Pavetić, Dustin Tran, Thomas Kipf, Mario Lučié, Xiaohua Zhai, Daniel Keysers, Jeremiah Harmsen, and Neil Houlshy. Scaling Vision Transformers to 22 Billion Parameters. February 2023. doi:
[52] Mitchell Wortsman, Peter J Liu, Lechao Xiao, Katic E Everett, Alexander A Alemi, Ben Adlam, John D Co- Reyes, Izzeddin Gur, Abhishek Kumar, Roman Novak, Jeffrey Pennington, Jascha Sohl-Dickstein, Kelvin Xu, Jachoon Lee, Justin Gilmer, and Simon Kornblith. Small-scale proxies for large-scale transformer training instabilities. In The Twelfth International Conference on Learning Representations, 2024. URL https: settss//oppere http:///ppeeeeveeeee net forum? ? id dddd840pmXbbZ.
[53] Trieu H. Trinh and Quoe V. Le. A Simple Method for Commonsense Reasoning. art. 180.02180 June 2018, doi: 10.48550/arXiv. 18011800088 006.02847..
[54] Ofir Press and Lior Wolf. Using the Output Embedding to Improve Language Models. August 2016. doi: 10.48550/arxivv11 wwt.iiivv66000.... 058599
[55] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019. URL httpps://openreiiiiiii http:p/wwww....eeee/o//ooed/aaaa
12

---

[56] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training Recurrent Neural Networks. arXiv:1211.5066 November 2012. doi: 10.48550/arxiv.2111 1211..00
[57] Tri Dao, Daniel Y Fu, Stefano Ermon, Atri Rudra, and Christopher Re. Flashattention: Fast and memory- efficcint exact attention with IO-awareness. In Advances in Neural Information Processing Systems, 2022.
URL httts::/ www.neeeffformmmimm df bmx.
[58] Tri Dao. Flashattention-2: Faster attention with better parallelism and work partitioning. In The Twelfth International Conference Learning Representations, 2024. URL httpps:///ppnneeiie..eeeee
1d-mZn2Xyh9Ec.
[59] Yoav Levine, Noam Wies. Sharir, Hofit Bata, and Amnon Shashua. Depth-to- Width Interplay in Self-Attentio,, art. arXiv:2006. 12467, June 2020. doi: 10.48550/rXiv.20066 12467.
13

---

Table 3: Model hyperparameters. Hyperparameters for models shown in Table 1.
Hyperparameters
FLOPs-
L
D
Model
Dataset
Parameters
T
per-byte
(Lgloral/ Liccat
(D/Dieal)
PG-19
454M
279M
32
1024
1024
Transformer
arXiv
253M
202M
16
1024
1024
(GPT2 tokenizer)
Github
253M
253M
16
1024
1024
PG-19
454M
260M
32
1024
1024
Transformer
arXiv
253M
155M
16
1024
1024
(SentencePiece)
Github
253M
182M
16
1024
1024
PG-19
202M
470M
16
1024
1024
Transformer
arXiv
202M
470M
16
1024
1024
Github
202M
470M
16
1024
1024
PG-19
227M
529M
32
768
4608
Transformer
arXiv
202M
470M
16
1024
6144
(Window Attention)
Github
202M
470M
16
1024
8192
PG-19
201M+51M
219M
16/16
1024/512
4096
MegaByte
arXiv
201M+51M
219M
16/16
1024/512
4096
Github
201M+51M
219M
16/16
1024/512
4096
PG-19
201M+113M
343M
16/16
1024/768
6144
SpaceByte (fixed P)
arXiv
201M+113M
343M
16/16
1024/768
6144
Github
201M+1133 13M
323M
16/16
1024/768
8192
PG-19
201M+50M
196M
16/16
1024/512
6144
SpaceByte
arXiv
201M+50M
196M
16/16
1024/512
6144
Github
151M+38M
132M
12/12
1024/512
8192
Table 4: Model hyperparameters. Hyperparameters for models shown in Table 2. order to roughly match the FLOPs- of the other models, for the subword-level Transformer- IB, used 40, 44, 37, and layers the PG-19, Stories, arXiv, and Github datasets, respectively.
Hyperparameters
FLOPs- per-byte
D
Model
Parameters
Others
(Tgloball Troeal)
Transformer
IB
730M
40, 44, 37, 31
1536
subword-level
Transformer
320M [7]
732M
22
1024
byte-level
PerceiverAR
248M [7]
17
1024
latents 1024
MegaByte
758M+262M [7]
729M
14/18
2048/
2048/1024 1022
P P= Nssate 16
MambaByte
353M [6]
713M
53
1024
SpaceByte
793M+1844 184M
728M
28/26
1536/768
Tglobal = 1344
A Model Details
Hyperparameters for models shown in Table and Table 2 are summarized in Table 3 and Table 4, respectively. Figure 4, we show another perspective of Figure where we plot the bits-per-byte vs the bytes trained divided by the number of model parameters.
For the subword models (but not the byte-level models), tie the input embedding weights with the output linear matrix weights [54]. In self-attention layers, we use a key dimension equal to 64. also included trained position embeddings.
Although apply RoPE embeddings,
SpaceByte For SpaceByte, we include trained position embeddings just before the first local transformer block, and just before the first global transformer block.
14

---

Table 5: Model non-embedding parameter counts. For MegaByte and SpaceByte, we separate the number of parameters (m) into global (Mgloba) and local (Miiaa) model contributions. We ignore embeddings and subleading parameters, such as layer norms, but include de-embedding parameters. See Section A.1 for symbol definitions.
Architecture
Parameters (non-embedding)
Component
m x 4D²
Multi-head attention Feed-forward
Transformer
+ 2e
+ DV
De-embedding
Miglbbal
Ligiobal x 4D2
Global mulltihead attention
+ Lglobal x 2e D
Global feed-forward
MegaByte
Mocal
Diocal p
Global-to-local projection
Luweat x 4D2 local
Local multi-head attention
+ Luocal x 2e D
Local feed-forward
local
Diocal V
De-embedding
Miglohal
Lyglohal
x 4D2
Global multi-head attention
+ Liubball x 2
Global ferwfforwrrd
SpaceByte
Mycal
Lical
4D
Local multi-head attention
Liocal X 2c 2e local
Local feed-forward
Diocal V
De-embedding
Table Inference FL.OPs-pe-ttoeen. We calculate the inference FL.OPs-per-token in terms of the numbers of parameters (m)) shown in Table 5. See Section A. for symbol definitions.
Architecture
inference FLOPS-per-token
Transformer
2m 2L (2W
Miglobal 1 + 2 (2
MegaByte
277lc + 2L (2PD)ocall (local)
Tyse 2 gggollll Twoy + 2 Lgoobal (2T global D) 2Mocaal + 2T (2W Diocal)
Taao Tiea
SpaceByte
Just like the other models, SpaceByte trained using a fixed context size of T bytes. At the same time, also fix the maximum global context size of T gigobal patches. However, the number of patches in given context of T bytes usually not exactly equal to Tglobal- To handle this mismatch during training. if the number of patches from applying the patching rule (see e.g. Figure 2) context of T bytes is greater Tglohal, then we simply ignore the bytes within these extra patches when calculating the cross entropy. Alternatively, the number of patches less than Tglobal, then we pad the activations for the global transformer blocks with zeroes and ignore the output of these global blocks. Thus, the input activations to the global blocks always tensor of same shape for each iteration. This discrepancy between the maximal global context size Tolobal and the actual number of patches results in small fracton of wasted compute during training, which roughly minimize by roughly tuning T/Tgloba See Appendix C for pseudocode.
During inference, the model must stop predicting tokens before either the max number of bytes (T) or the max number of patches (Tglobal) is reached.
A.1 FLOPs
The inference FLOPs-per-byte is the number of FLOPs required to output byte text during inference. We calculate the of bytes per token (which is equal to 1 for byte-level models).
the FLOPs-per-tokke divided by the average number
The FL.OPs-pe-token is the number of FLOPs required to output token of text during inference (or byte of text for byte-level models). The Fe-oPs-eerttoken for the various architectures shown in Table 6.
15

---

Notation For all architectures, T is the context length; D is the model dimension (of the global model for SpaceByte and MegaByte): ear the model dimension expansion factor for forw-forward layers; and V is the vocabulary size (which is 256 for byte-level models and 50257 for our subword models). For the transformer architecture, I. is the number of transformer blocks, and W is the attention window size (which is equal to T if window attention is not used). For SpaceByte and MegaByte, Decal is the dimension of the local model; Lieal is the number of local transformer blocks; and Loglobal is the number of global transformer blocks. For SpaceByte, T globall is the maximum context size for the global model, and local (which we set to Dieea) is the attention window size for the local blocks. For MegaByte, P is the patch size.
B Training Details
B.1
Data
Each dataset prepared by downloaded it from Hugging Face", concatenating sequences together, and separating sequences with a special BOS token. When preparing a training sample with context size T, uniformly and randomly sample sub-sequence of length T from the concatenated dataset. If a BOS token found in this subset, we align the context with the first BOS token found; i.e. we take the context be the first BOS token followed by the next T' 1 tokens in the concatenated dataset. If a BOS token is not found in the subset, we prepend a BOS token to the context. The context window always full and always begins with a BOS token.
For the SpaceByte models, we always insert global blocks after a BOS token. A valid UTF-8 encoding never makes use of the byte values 254 or 255. We use 255 to encode the BOS token.
We train the SentencePiece tokenizers using the following command: -model_type=bbs
tpann - --input=train. txt -tmmmmde__prefixxee -- -vocab_size-5022 --num -num_threadd=--e threads=32 --byte_ bbyte_fallback-Truee
-aallowwwwitessppeaeeaaaaeeeeeea sacpieeee_ooll_eeeeeeeeeeeeeeeee only_pieces-True --remove_ aanoove_exrr__wittspeeeee
-normalization wtw.ruleeeeeeeeeiiitttttrr suaput_sentence_siee10000000
B.2 Training
All models are trained using AdamW [55] with 31 = 0.9, 82 = 0.98, batch size 64, weight decay of 0.01, and gradient clipping [56] with a maximum norm of 1.0. Trainable parameters are randomly initialized using normal distribution with standard deviation Gintt 1 for all parameters except for linear weight matrices, which are initialized with standard deviation of F = 1/ ddns where dn is the input dimension for the linear layer. We scale the learning rate for each parameter by its initialization standard deviation iiii-
With this setup, we found in our early hyperparameter search experiments that the optimal max learning rate for all models is approximately 7 0. 0.005BB-.. = 0.000625, where B = 64 is the batch size. We therefore used > 0.000625 the max learning rate for all models trained in this work. We applied a linear learning rate warmup over the first 1% of training iterations. We also multiply the learning rate by "half-cosine" learning rate decay function cos(Tr/2),, where 0 S æ & is the fraction of training iterations completed."
Each model was trained using PyTorch on single 40GB Nvidia A40 and A100 GPUs with mixed- precision (b and float32) training and FlashAttention [57, 58]. SpaceByte-793MM 1EMM++184M 184M took the longest to train, requiring about 10 days on an 1100 GPU.
"httss//hugginggace http://wwggggnnaa.coo/////tt///a
https:/hugginngface http://ggggggggoooaaaatttttaaaaa co///aataett/lucaadillll///ooooo
https:/huuggingfaceccm
http::/hwwggggnic..oo/////ttttta wwt.daaatttte//oooooogyyy/ pile-uncopyrrghted
"In our setup. we found / to slightly outperform the more standard cosine decay from I O.I. (e very roughly estimate that additional preliminary and failed experiments not shown in this work required roughly many FLOPs the experiments shown in this work.
16

---

subword-level:
1.4
Transformer
Tross-entrppy (bits- per--pe-byte)
1.3
(GPT2 tokenizer)
Transformer er
(Sentence Plece)
byte-level:
Transformer
1.2
Transformer
(Window Attention)
1.1
MegaByte
SpaceByte
1.1
(fixed P)
SpaceByte
1.0
10a
10a
trained bytes parameters (non-embedding)
(a) PG-19 dataset
subword-level:
cross-entropy (bits (bits-per-byte) (yr-byte)
Transformer
(GPT2 tokenizer)
Transformet
1.0
(Sentencee Piece)
byte-level:
Transformer
0.9
Transformer
(Window Attention)
MegaByte
SpaceByte
0.8
(fixed P)
SpaceByte
10a
10a
10a
trained bytes / parameters (non-embedding)
arXiv dataset
subword-levei
cross- cross-enropyy (bits-per (tt--er-byte))
0.9
Transformer
(GPT2 tokenizer)
Transformer
0.8
(SentencePiece) Piece)
byte-level:
0.7
Transformer
Transformes
(Window Attention)
0.6
MegaByte
SpaceByte
P)
SpaceByte
0.5
10a
102
10a
trained parameters (non-embedding)
(c) Github datasct
Figure 4: The Pareto frontier models from Figure 3, where we plot the bits-per-byte the number of bytes used for training divided by the number of non-embedding parameters (defined in Table 5).
17

---

B.3 Hyperparameter Grid
We train models using a grid of different model dimensions and numbers of layers. In our early ssall-scale experiments, we found that the hyperparameter grid described below effectively explores the bits-per-byte and bye Pareto frontier for all models. To simplify the hyperparameter grid, we restrict ourselves to model dimensions and layer numbers to half-powers of two, i.e. a power of two times or
For models trained using 10 FLOPs, we train model dimensions D E (384, 512, 768). For models trained using 10 FLOPs, we train model dimensions D E {512, 768, 1024].
For SpaceByte and MegaByte, D is the global model dimension. The local model dimension is chosen from Diocal E D two times & 2. However, in order to avoid excessively low FLOP utilization, we restrict Diocal 2 256 (or Diocal 2 384) for models trained using 10 FLOPs (or 10 FLOPs).
2 D) if a power of two, or D Diocal E D D) if D a power of
To set the number of layers, roughly follow Levine et al. [59], who found that the compute-optimal
number layers for Transformer roughly follows L ~ 12.5 log. (//14).. We round this number to the nearest salf-power of two to obtain LD, for which L384 16, L512 24, L768 32, and L1024 = 32. For Transformer models, we choose the number of layers from L E LD LD).
For SpaceByte and MegaByte models, we choose the number of local and global layers from Lieal Ligohhll L ]LD if Ln is power of two, or Liocal = Lglobal E ( LD)
if Ln
a power of two times 3 2-
C Pseudocode
See Listing 1 for Pytorch pseudocode for the SpaceByte forward method. The implementation of SpaceByte that we used in our experiments can be found at cetbub.com//jslagssaccbbbb
18

---

Listing 1: Pytorch pseudocode for SpaceByte
def forward (self, tokens, targets-None);
B, I tokens shape batch size, context size T-global self self.global_coneett..ee D_local self www.looall_aaa mod.ooallldeediieeeeeeeee dimensioo self helf.global manell__mdelldimensis..
embedding:
x self. www.ne/eeeddinggteeenenee
x self www..oaootoaiiioooeeeee....
initial local transformer blocks:
block in self.intial..lodkss
x block(x)
global block insertion rule: use-global ( (
letter, number, UTF continuation byte
(tokens ord())))
((9)d()9)) tokens) & (tokens < ord (?A))))
((ord('2)) < tokens) & (tokens < ord ('aa))
((ord('2') tokens) & (tokens < 0b1000 0000))
(0b1100_0000)
tokens)
use_global[:, 1:] 2= use_global :-1]. bitviissteeenott.. () not
preceded by another spacelike byte
use_global == tokens == self B0S_token # always use global blocks after BOS tokens
calculate global block indices:
num-global corch.fule ((B)), -1) # number of global blocks used global_ids idx = torch. ((B, T_global), T-1) # global block indices for b range(B):
idx, use_global [b] (an
if targets is not None and len(idx) T_global:
# ignore targets with insufficient global blocks: targets [b, idx[T_globall:] [um.globalbb] Ien(id[[:T.global]] global_idx(b, :num_global [b]] idx [dT[ooaal
select activations for global blocks:
y gather (1, global_idx Monel expand T_global, D_local))
expand model dimension by padding with zeros:
torch. cathccat((ttrct 2er T.global, D D_local), y), -1)
global transformer blocks:
y y self heff.global.posttin .ncooiin
for block in self self.globale lll.glllbblloooo blocks: y byock(y)
add global block activations to local blocks: torch. s[
x[b] x[b].inde ind for b, n in enumerate mumerate(num.globb ])
ilobal_idx(b :n], y[b, i, -D_local:]
final local transformer blocks: for block in self final_blocks:
x block(x) de-embedding:
logits self lineer (self layer_norm
cross_entropy__oe if targets is not None:
None
cross_ engeeerroyyloss torch mn functional, entropy
segits.view(e (B+T, 256). vargets.view(B)
ignore_index=-11 (B,
return logits, cross_ satssseetrrpppyoo____
19

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our claims are summarized in the abstract, and restated in the introduction.
Our abstract makes three claims, which we enumerate the following quote:
"SpaceByte consists of byte-level Transformer model, but with extra larger transformer blocks inserted in the middle of the layers. (1) We find that performance significantly improved by applying these larger blocks only after certain bytes, such as space characters, which typically denote word boundaries. (2) Our experiments show that for fixed training and inference compute budget, SpaceByte outperforms other byte-level architectures and (3) roughly matches the performance of tokenized Transformer architectures."
These claims substantiated in Sections 5 and 6. The first claim is supported by Figure and Table 1, which compare SpaceByte to "SpaceByte (fixed P)." which is a variant of SpaceByte that uses fixed patch sizes instead of applying the larger blocks only after certain bytes. The final two claims are also supported by Figure 3 and Table 1, along with Table 2. At the end of our introduction, we note that our results could be limited to the text modalities (English text, LaTex formatted arXiv papers, and source code) that we study.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: At the end of our introduction, we note that results could be limited the text modalities (English text, LaTex formatted arXiv papers, and source code) that we study, We emphasize in Section 2 and our conclusion that generalizing SpaceByte's performance other text modalities (by improving the global block insertion rule) is an important direction for future work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well sell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be
20

---

used reliably to provide closed captions for online lectures because it fails to handle technical Jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [NA]
Justification:
No theoretical results were presented.
Guidelines:
The answer NA means that the paper does not include theoretical results,
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Open source code, job execution scripts, and a jupyter notebook for fully reproducing our results are available at gittub.com/iislggssacceyy
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
21

---

(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should descrihe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Open access to code and thorough instructions for reproducing our experiments are available github. com//jslag/spaccbyt.. This includes code for the models, training, and bits-per-byte evaluation, and requirements.tx for pip.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (attps://nips.ce
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https://nips
wwimimisssoppiiyooccc for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: The experimental setting described in Section 4. The models studied are summarized in Sections 4.1, 4.2, and 6. Additional model details are provided in Appendix A. Training details are provided Appendix B. Any additional details are available in our released source code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
22

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Tables and give upper bounds for the 1 1-sigma statistical error and clarify that these statistical errors account for the finite number evaluation samples. We also estimate the statistical uncertainty due to the different test splits used by other works in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" the results are accompanied by error bars, confidence intervals, statistical significance tests, least for the experiments that support the main claims the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative enror rates).
show in tables
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: Compute resource requirements are detailed at the end of Appendix B.2, along with an additional compute estimate for preliminary and failed experiments (in footnote). Models trained in our main experiments used 1018 or 1029 FLOPs for training, as specified in Section When comparing to other works, training each model required 6.5 10 FI.OPs, as specified in Section 6.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https :/tt::/isn..eeeeeeeee httprr/ss...ppplleecccceeeaaaaea
Answer: [Yes]
23

---

Justification:
Regarding the data-related concern,, we omit comparisons to the Books3 dataset since this dataset no longer publically available and because it is unclear us Books3 is legal under fair use, as stated in Footnote 7.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We briefly mention in the abstract and introduction that tokenization can increase the vulnerability to adversarial attacks. Lessening this adversarial vulnerability was one of our motivations. We are not aware of any potential negative societal impacts of our work.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (c.g.. disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deploymenn of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
We do not release any data models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
24

---

Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
We include citations to all datasets that we use. We believe that we have properly respected the licenses and terms of use for all code and datasets that used. Notably, we avoided the Books3 dataset for this reason, since Books3 may not be respecting the licenses of the works from which it derives. Code attributions and licenses provided in the 'license' directory of our released source code.
Justification:
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The only asset introduced is source code. We provide detailed instructions for using this code to reproduce our results in the "reproduce" directory of the source code.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the datasct/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA].
Justification: Human subjects were not involved in this research.
25

---

Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA].
Justification: Human subjects were not involved in this research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
26


Reviews:
[{"review_id": "dvqTM6Vcu2", "reviewer": "Reviewer_8HNC", "summary": "This paper proposes SpaceByte, a byte-level decoder architecture for language modeling. As opposed to comparable models such as MegaByte, SpaceByte applies global transformer blocks after space-like characters, not after patches of a fixed size. The authors show that this approach leads to a substantially improved performance: compared to several other byte-level decoder architectures (including MegaByte), SpaceByte is the only one that matches or even exceeds the performance of subword-level models trained with the same compute budget.", "questions": "Is there any specific reason you did not include evaluations on downstream tasks?", "limitations": "Yes, the authors discuss limitations as part of the conclusion.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The proposed SpaceByte architecture is novel. The experimental setup is rigorous --- I think the authors did a great job in (a) evaluating a range of different architectures and (b) ensuring a fair comparison by controlling compute costs and using bits-per-byte as the evaluation measure. The results show clear performance improvements for SpaceByte, highlighting its advantages compared to other byte-level decoder architectures. Overall, I liked the paper very much and think that it should be accepted.", "weaknesses": "The main weakness that I see is that the authors only evaluate the different architectures using bits-per-byte, not any downstream task. To become a real alternative to subword-level models in practice, it would be important to show that the similar language modeling performance translates to a similar downstream task performance. While the authors cite work indicating that this might be the case (Huang et al., 2024), without actual experiments it is unclear whether this holds for the examined architectures as well.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thoughtful review and for accurately assessing strengths and weaknesses of our work.\n\nWe would have loved to include evaluations on downstream tasks, but we unfortunately ran out of manpower and time.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "e5YLWbaWBb", "reviewer": "Reviewer_HARv", "summary": "Byte-level modeling allows transformers to circumvent subword tokenization, thus avoiding the many weaknesses introduced by tokenization. However those models are not very performant compared to subword-based transformers. This paper proposes a novel architecture named *SpaceByte*. The idea is to add an extra wide layer (i.e. \"global block\") between regular transformer layers (i.e. \"local block\") if and only if \"the byte does not encode a letter, number, or UTF-8 continuation byte\". Results show that when normalizing for training FLOPs, SpaceByte achieves the best PPL on multiple datasets. Plus, at different model dimensions and number of layers (?), SpaceByte always achieve the optimal or near-optimal Pareto optimality between PPL and inference FLOPs-per-byte.", "questions": "### Presentation Suggestions\n\n1. It's worth explaining more about how context lengths work differently for global vs. local blocks in Section 2. I'm also not very sure why the larger context length is necessary.\n2. I'd suggest switching Section 2 and 3 and talk about related work first.\n3. Three suggestions for Figure 3 -- a. make it clear in the caption that you are changing inference FLOPs with different model dimensions & layers (per line 206); b. use dashed/solid lines rather than thin/thick lines; c. mark the pareto frontier for each subfigures.\n\n### Questions\n\n1. Is the FLOP limits you imposed enough to make the models converge adequately on those datasets? It might have been the case that your model simply converges faster, but if trained longer, doesn't work as well as, e.g. sub-word models (which weakens your case).\n2. Why set the dimension and context length equal?\n3. I'm very confused what's the difference between section 6 and 5. How does the results in section 6 further complements the one in section 5?\n4. In Table 2, you only have one context size, but don't global blocks have larger context size? What context size is being reported then?", "limitations": "See weakness point 1. I'm relatively confident that this could be a potential limitation that needs to be addressed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The idea is simple and well-motivated\n2. Experiment results show that it is competitive when compared subword-based models", "weaknesses": "1. While normalizing for FLOPs, I think there is some potential that the proposal will make the transformer blocks significantly harder to batch (due to the input-dependent dynamic structure of the model), hence the clock-time of the inference might actually be slower with the same FLOPs. It would be good to see some discussions on that.\n2. There is no ablations as to whether the global blocks actually need larger dimension.\n3. Presentation of the paper could be improved. See my question/suggestion in the next section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review of our work. Although we agree that SpaceByte is more challenging to batch than a Transformer, we would like to emphasize that our work does establish a very significant milestone in byte-level LLMs because SpaceByte is the first byte-level attention-based architecture to demonstrate performance parity with the subword Transformer architecture. We believe this significance warrants acceptance (while leaving room for future work to show that the batching issue is not a significant hurdle).\n\n## Weakness 1\nYou are correct that batching during inference is more challenging with SpaceByte. Nevertheless, we do believe that with a moderate amount of effort, a high FLOP utilization could be maintained with batching and without significantly sacrificing latency. One solution would be to maintain three separate queues for three parts of the model pipeline:\n1. embedding + initial local blocks\n2. global blocks\n3. final global blocks + de-embedding\n\nEach queue processes a batch of input tokens or activations at a time. The batch size and context lengths are variable. Variable context lengths is not an issue since padding could be used (and padding is already typically used for batching due to variable prompt lengths). In a multi-GPU setup, it could be useful to put different queues on different GPUs in a 1-2-1 ratio for the three queues (to roughly even out the FLOPs). And 8 GPU setup would then naturally allow for two instances of each queue, which would be useful for reducing latency due to waiting in a queue. Thus, although the batching issue is annoying, we do not think that it is a major obstacle.\n\n## Weakness 2\nIn preliminary experiments, we found that taking equal model dimensions for the local and global blocks to be significantly worse. Therefore, in our hyperparameter grid search, we take the local block dimension to be:  \nD_local = 1/2 * D or (3/4 if D is a power of two else 2/3) * D  \nwhere D is the global block dimension. This is specified in Appendix B.3. But as seen in Tables 3 and 4, which shows optimal hyperparameters found by our grid search, the smaller D_local = 1/2 * D performs better. Therefore, our paper does show strong evidence that it's important to use a larger model dimension for the global blocks.\n\n## Presentation Suggestion 1\nThank you for the suggestion. We have appended the following sentence to line 76 at the end of Section 2: \"The global blocks use a global attention that attends to all other global blocks.\"\n\nThe context length that we experiment on is the natural (and roughly optimal) choice for all architectures that we evaluated. In particular, the chosen context length is natural and roughly optimal for the subword tokenizer since it roughly balances the FLOPs between the attention and MLP layers. SpaceByte uses a similar context length (after converting tokens to bytes) for a fair comparison (see Table 3 for precise numbers). But this context length would be too large for the local blocks to be efficient if we did not utilize an attention window since then the local attention blocks would use significantly more FLOPs than the local MLP blocks. An attention window prevents this inefficiency.\n\n## Presentation Suggestion 2\nThank you for the suggestion. We made the choice to put the Related Work section after the SpaceByte section so that we could comment on how SpaceByte relates to the related works.\n\n## Presentation Suggestion 3a\nThank you very much for this suggestion! We agree that it greatly improves the clarity of the caption. We added the following additional sentence in the new version:\n\"Each dot describes a model with a different number of layers and/or model dimension.\"\n\n## Presentation Suggestion 3b\nThank you for the suggestion. We tried dashed/solid lines as per your suggestion; but we feel the thin/thick lines are cleaner and easier to read.\n\n## Presentation Suggestion 3c\nWe already show the Pareto frontier, which is drawn for each model using a thin or think line.\n\n## Question 1\nIt depends on what you mean by \"adequately.\" The models are certainly not trained to convergence, as that would be prohibitively expensive in practice. In practice, one (almost always) does not care how well a LLM performs when trained to convergence. Instead, one cares about how well a LLM performs for a given cost budget. There are two important budgets that we consider: a training budget and an inference budget. We use training and inference FLOPs as a simple proxy for these respective costs since FLOPs are independent of software and hardware choices. This results in the Pareto frontiers shown in Figure 3. In this sense, all of the models shown in Figure 3 are very adequately trained as they lie on the Pareto frontier of performance vs cost.\n\n## Question 2\nWe set the model dimension and context length equal so that the FLOPs are roughly balanced between the MLP and attention blocks, which tends to be the most efficient. This was a simple choice that we thought made the most sense for a fair comparison that evaluates all of the models at their best.\n\n## Question 3\nSection 5 is our main experiment. But we include Section 6 to make closer comparisons to the MegaByte and MambaByte experiments. Table 2 of Section 6 also includes PerceiverAR and MambaByte, which were not studied in Section 5. Furthermore, Table 2 shows MegaByte results trained by the MegaByte authors to help demonstrate that our finding that SpaceByte outperforms MegaByte is not just because we didn't train MegaByte well. (Unfortunately, this fact is only established for the PG-19 and Stories datasets in Table 2, since MegaByte was trained and evaluated on proprietary arXiv and Github datasets that are slightly different than the public datasets that we have access to).\n\n## Question 4\nWe report the context size available to the LLM. For SpaceByte, this is the total number of bytes in the input sequence.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "19pd6TNxAN", "reviewer": "Reviewer_zbbv", "summary": "The paper introduces SpaceByte, a byte-level Transformer model that incorporates larger transformer blocks at specific byte boundaries to enhance performance in language modeling tasks. While the approach bears similarities to previous work (e.g. MegaByte), it demonstrates improved performance over traditional tokenization models. The study focuses on specific languages, acknowledging limitations in generalizability, particularly in languages like Chinese, which do not use spaces between words.", "questions": "1. How do the authors plan to address the limitations in generalizability to languages beyond the ones studied in the current work?\n\n2. Are there plans to conduct experiments on a more diverse set of language datasets to further validate the effectiveness of SpaceByte in different linguistic contexts?", "limitations": "The authors have acknowledged the limitations of their work, particularly in terms of language generalizability. To enhance the impact of the study, it would be beneficial for the authors to consider conducting experiments on a broader range of language datasets to strengthen the validity and applicability of SpaceByte across various linguistic domains.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper presents a novel approach in utilizing byte-level Transformer models with specific block insertions to enhance language modeling performance.\n\n2. The study provides insights into the limitations of tokenization models and the potential benefits of byte-level architectures.\n\n3. The experimental methodology is well-documented, controlling for compute costs and providing detailed training details in the appendices.", "weaknesses": "1. The novelty of the SpaceByte approach may be limited by similarities to previous models.\n\n2. The study's focus on specific languages, without detailed experiments on broader language datasets, limits the generalizability of the findings.\n\n3. The paper could benefit from a more extensive discussion on the unique contributions of SpaceByte compared to existing models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your careful review of our work and for identifying its key strengths.\n\n## Weakness 3\nAs discussed in Section 3, our primary contributions beyond prior works is to show how to scale word-boundary byte-level modeling to more diverse text modalities while roughly matching the performance of subword-level models in compute-controlled experiments. Previous works that studied word boundary LLMs did not demonstrate that this is possible or how to do it.\n\n## Question 1\nThis is a very important direction for future work. Unfortunately, we will not have time to address it in the foreseeable future. However, Reference 9 studied some promising techniques, such as using entropy to partition the patch boundaries. It would be useful to see if this approach is also capable of matching subword Transformer performance, especially on broader language datasets.\n\n## Question 2\nWe unfortunately do not currently have plans for this (due to time limitations).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Hq55SFoSbK", "reviewer": "Reviewer_ZB8e", "summary": "The authors propose a byte-level architecture called SpaceByte that involves local blocks (lower dimension, windowed attention) and global blocks (higher dimension, global attention) where the global blocks are between chunks of local blocks and only selectively applied. The global blocks are applied to \"spacelike\" characters (such as an actual space character), with the intuition being that at such points predicting the next character (like start of word) would be harder. The authors run extensive experiments to show that their proposed architecture outperforms previous byte-level architectures and in fact performs similarly to subword-level transformer baselines.", "questions": "Please see weaknesses for my questions.", "limitations": "Yes. The paper does a good job of this.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "**Originality**: While this work seems to share much in common with past byte-level architecture work, the intuitive idea of some bytes being harder to predict (in a rule predictable way) is very natural and useful (and first presented in this work, as far as I am aware). The architecture itself is also novel.\n\n**Quality**: The authors run a lot of experiments to demonstrate the capabilities of their architecture.\n\n**Clarity**: The paper was clear, down-to-earth, and easy to understand.\n\n**Significance**: This paper shows that byte-level architectures can be competitive with subword tokenization transformers in a flop-matched setting.", "weaknesses": "* As a main weakness I'd say that even though this method beats other byte-level approaches and is comparable to subword tokenization, I don't see a compelling reason to use it over standard tokenization. In the Introduction the authors mention several downsides of tokenization, but don't have results that focus on these issues per se. I'm also a bit confused about the \"additional modeling complexity (line 20)\" point. It seems like tokenization is actually simpler.\n* It would have been nice to see some ablations on the architecture (for example, the local -> global -> local layer ordering seems a little arbitrary).\n* It would have been nice to see some modifications of the global rule. For example, only \"space\" characters like actual space and newline vs the more broad definition of \"space\" used in the paper.\n* It might be nice to include more info on what the \"spacelike\" tokens actually look like (what are the most common \"spacelike\" tokens and what percentage of all \"spacelike\" tokens do these make up).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your insightful and thorough review.\n\n## Weakness 1\nWe agree that there is not a compelling case to use SpaceByte over a subword Transformer. However, we hope that iterating upon the SpaceByte architecture could eventually yield a compelling byte-level model. And we believe that SpaceByte is a significant milestone in this process since it's the first attention-based architecture to achieve performance parity with subword Transformers.\n\nWe would have loved to address the other tokenization issues, but we unfortunately ran out of time. However, we were very pleased to see that MambaByte [7] (i.e. byte-level Mamba [25]) exhibits a significantly higher character-level noise-tolerance than subword Transformers. We expect SpaceByte to show a similar tolerance improvement, although we have unfortunately not had time to experimentally check this.\n\nThe sentence on line 20 is not making a claim about SpaceByte. We simply mean that additional modeling complexity is a disadvantage of tokenized Transformers over e.g. a byte-level Transformer. We agree that the extra complexity of SpaceByte largely cancels out the simplicity of removing the tokenizer, and thus simplicity is unfortunately not a compelling reason to use SpaceByte over a tokenized Transformer.\n\n## Weakness 2\nWe apologize for the lack of ablations. We don't have ablations because when faced with an architecture decision, we simply made the simplest choice that should work well. Examples include: the local block attention window (else the FLOPs for the local attention would be roughly 36x larger and dominate the model's flops), the lack of a linear layer to change model dimensions between local and global blocks (which MegaByte had but we found in preliminary experiments to slightly hurt FLOP-controlled performance), and our choice of spacelike characters.\n\nThe local -> global -> local ordering is not at all arbitrary. If no local layers preceded the global layers (e.g. global -> local), then the global layers would not have any information about the majority of the bytes. Similarly, if no local layers followed the global layers (e.g. local -> global), then the global layers would have no influence on the majority of the output bytes. As such, local -> global -> local is the simplest good choice.\n\n## Weakness 3\nWe studied something like this in preliminary experiments, and found that it performed slightly worse on the datasets we studied.\n\n## Weakness 4\nThat is a nice suggestion, although it is certainly very dataset-dependent. We may include it in the next version. Until then, we hope that the demonstration in Figure 2 is helpful.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Paper introduces SpaceByte, a novel byte-level language model designed to bridge the performance gap between byte-level and subword-based models.  The core idea revolves around strategically inserting wider, global transformer blocks after "space-like" bytes, aiming to improve performance on predicting word beginnings.

The notable weaknesses like limited generalizability, lack of downstream evals and ablations need to be addressed in the future and discussed in the paper. That said, the very topic this paper tackles and the novelty of the proposed method with the early wins potentially lead to acceptance as a poster.
Decision: Accept (poster)