SpaceByte: Towards Deleting Tokenization from Large Language Modeling

Authors: kevin  slagle
Venue: NeurIPS_cc_2024_Conference
Published: 2024-04-30 18:14:13

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.

Main paper: 
 introduction: 
 Most language models are trained using tokenization, which partitions text into tokens that typically consist of words or subwords. Tokenization is useful because it 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] [2] [3] ; increased vulnerability to adversarial attacks [4] ; and worse character-level modeling performance [5, 6] , and additional model complexity. 1Recently, MegaByte [7] , MambaByte [6] , and more [8] [9] [10] [11] [12] have been proposed as new byte-level autoregressive language models that model bytes instead of tokens. (See [13] [14] [15] [16] [17] [18] [19] [20] [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] [23] [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 a fixed compute budget. We measure the performance in terms of the cross entropy (measured in bits-per-byte), which has been shown to be a 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 10 times more training FLOPs to achieve the same performance as a subword- 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 a fixed patch size, SpaceByte uses a 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 a 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. 
spacebyte: 
 The SpaceByte architecture is summarized in Figure 1 . In a nutshell, SpaceByte can be thought of as a byte-level Transformer model, but with extra "global" transformer blocks (with a larger model dimension) inserted in 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 is that the first character of a 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 at word boundaries.Global Block Insertion Rule In this work, we consider a very simple rule to dynamically decide when to apply the global blocks. We assume that the text bytes are encoded using the UTF-8 encoding.We define a byte to be spacelike if the byte does not encode a letter, number, or UTF-8 continuation byte 2 . We apply the global blocks after any spacelike byte that is not preceded by another spacelike byte (and after any BOS token). See Figure 2 for examples.The most common spacelike byte is the space character. Thus, the global blocks are applied most frequently to predict the first character of a word, which we expect is the hardest character to predict [27] in a given word. With fixed patch size (e.g. as 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 in UTF-8).the↓enemy!"•• he exclaimed. "••Their capture must be prevented. Come with arXiv:where $q_1=q_2=\dots=q_\kappa$ and $V_1=V_2=\dots V_\kappa$. In this way, Github:exp += 2;↓↓ mbf[3] = exp;↓ mbf[2] = sign | (ieee[2] & 0x7f);↓ Figure 2:Examples of patch boundaries from datasets that we study. Spacelike bytes are underlined and colored blue. Patches boundaries are drawn above the text. Each patch ends after a spacelike byte that is not preceded by another spacelike byte. Consequently, each patch begins with zero or more spacelike bytes, followed by one or more non-spacelike bytes, and ends with a single spacelike byte. The global blocks predict the first character of each patch. The downward arrow (↓) denotes a newline byte. The left and right quotation characters, (") and (") in 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 a bullet point (•) above.Although this very simple "spacelike" rule is likely not the optimal rule, we find that it works surprisingly well in practice for English text, LaTeX formatted papers, and code. Nevertheless, a critical future direction is to optimize [28, 14, 9] better rules using data rather than our simple heuristic.Important Details Since the global blocks are not applied as often as the local transformer blocks, it is advantageous to use a larger model dimension for the global transformer blocks. To increase the dimensions of an activation vector before the global blocks, we simply pad the activation vector with zeros. To decrease the dimension, we truncate the activation vector.In our experiments, we use a significantly larger context size than the model dimension D local of the local transformer blocks. To prevent the attention mechanism from dominating the compute costs for the local model, we use an attention window [29] [30] [31] 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 our results could be limited to 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 to 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 a separate "Limitations" section in 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-specification, asymptotic approximations only holding locally). The authors should reflect on 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be 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 as grounds for rejection, a 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 in developing norms that preserve the integrity of the community.Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
related work: 
 The most straight-forward consequence of modeling bytes instead of subword tokens is that the length of a sequence typically increases by about a factor of four. This increased sequence length increases the training and inference compute cost for modeling a given long sequence of 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 a fixed patch size P . Each patch of bytes is vectorized and then fed into a "global" Transformer model. The output of the global model is then fed into a "local" Transformer model that autoregressively outputs byte-level logits. [7] For a context size of T bytes, MegaByte's global Transformer model compresses the context into only T /P patches, which can significantly decrease the compute cost for modeling long sequences. Similar to Yu et al. [7] , we also find that MegaByte outperforms a standard byte-level Transformer. However, we find that MegaByte's performance is remarkably close to a stronger byte-level Transformer baseline that simply uses a sliding window attention mechanism [29] [30] [31] to increase the context size without increasing the compute costs.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 a subword-level Transformer.Compared to MegaByte, SpaceByte makes the crucial change that patches are dynamically sized to 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 a 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-level Transformers.MambaByte The MambaByte architecture [6] takes an 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) in place of Transformer blocks.Layer Skipping SpaceByte could be though of as a Transformer that employs a novel kind of text-dependent layer skipping [32] [33] [34] [35] [36] [37] [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 subwordlevel models, nor did they identity a 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-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 a sliding window attention [29] [30] [31] in the local blocks to improve performance for long context sizes.Question: For each theoretical result, does the paper provide the full set 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 crossreferenced. • All assumptions should be clearly stated or 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 to 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. 
experiment setup: 
 Our experiments compare the performance of our byte-level SpaceByte architecture to subwordlevel 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 in terms of bits-per-byte. 3 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 evaluation. We use FLOPs-per-byte as a simple software and hardware-independent proxy for inference compute costs, which is the number of FLOPs (see Appendix A.1) required to model a byte of text. 4Note that by controlling for both total training compute and FLOPs-per-byte, we are also controlling for the amount of training data since (bytes trained) = (training FLOPs)/(training FLOPs-per-byte).The FLOPs-per-byte during training is equal to three times the FLOPs-per-byte during inference (due to the backwards pass during training).We therefore study the Pareto frontier of lowest bits-per-byte and lowest FLOPs-per-byte. We train all models using a compute-controlled setup, using either 10 18 or 10 19 FLOPs. In order to effectively explore this Pareto frontier, we train models using a 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] ).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. For the PG-19 and arXiv datasets, the average patch size is roughly 6, so we take T = 6T global for these datasets; for the Github dataset, the average patch size is roughly 8, so we instead take T = 8T global for the Github dataset.For simplicity, we fix the number of global transformer blocks L global to be equal to the total number of local blocks, LEQUATIONlocal , and we evenly split the number of local blocks before (Llocal ) and after (L local = L (2) local = 1 2 L global .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 to roughly match SpaceByte'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 global = D and T = P T global .Byte-level Transformer For a simple baseline comparison (following Yu et al. [7] ), we train bytelevel Transformer models. We take the context size to be equal to the model dimension, T = D.Note that in our setup, a Transformer with model dimension D only sees a context size of D, which is significantly smaller than the context size of P D for SpaceByte (and MegaByte) with patch size P .Since a shorter context is a significant disadvantage for long-form datasets, we also compare against a stronger Transformer baseline that uses a sliding window attention [29] [30] [31] to efficiently increase the context size without increasing compute costs. We train each window attention enhanced Transformer using a context size T = P D and a sliding attention window size equal to D, with P = 6 for all datasets except for the Github dataset for which P = 8. 5MegaByte We also compare to MegaByte [7] . Although MegaByte was originally trained using a 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, L global = L local , which is close Our most important baseline is the standard subword Transformer. We train subword Transformers using two different tokenizers (both with a vocabulary size of 50,257): (1) the GPT2 tokenizer [43] , and (2) a SentencePiece [44] tokenizer using a byte-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.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 qk-layernorm [50] [51] [52] (which we strongly recommend) for all models; i.e. we add an extra layer-normalization to the query and key vectors in the self-attention layers.All hyperparameters have been carefully tuned using grid and random searches. See Appendices A and B for more details. 65 ResultsWe now present our experimental data comparing the different model architectures in computecontrolled settings. Figure 3 plots the Pareto frontier of lowest cross-entropy 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 a grid search over model dimension and number of layers; we then draw a piecewise-linear 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 1 summarizes the results for the lowest overall bits-per-byte for each architecture.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 a wide margin on 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 3 SpaceByte roughly matches the performance of the subword Transformer using SentencePiece tokens, and outperforms the subword Transformer using GPT2 tokens.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-byte (≈ 728M). The bits-per-byte for the Transformer, PerceiverAR, 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 a 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. † These models used slightly different datasets for training and/or testing. For MambaByte-353M, we estimate that this difference very roughly amounts to an extra 3% statistical error. MegaByte; however, MegaByte trained using 10 19 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 is 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 to 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 performance, we compare SpaceByte to a 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.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 the 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 github.com/kjslag/spacebyte. Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a 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 a 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it 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 a 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• The full details can be provided either with the code, in appendix, or as supplemental material. 
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-per-byte, 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 SpaceByte-793M+184M (D = 1536, D local = 768, L local = 26, L global = 28) using roughly the same inference FLOPs-per-byte (728M) but also only 30B bytes of data (following Wang et al. [6] ). Training these models thus requires roughly 3 × 728M FLOPs-per-byte × 30B bytes ≈ 6.5 × 10 19 FLOPS, where the factor of three comes from converting inference FLOPs-per-byte to training FLOPs-per-byte (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 for the PG-19, Stories, arXiv, and Github datasets are 4.05, 4.39, 3.73, and 3.31, respectively. To match the FLOPs-per-byte 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 are 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. 7 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 The Pile [42] . However, Wang et al. [6] use their own test splits to evaluate MambaByte-353M on 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-byte for SpaceByte-793M+184M 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 SpaceByte-793M+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-1B. 
conclusion: 
 We have proposed a new byte-level Transformer decoder architecture, SpaceByte. Our computecontrolled 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 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 as the sentence or paragraph level. It would also be fruitful to investigate if Mamba blocks [25] could further improve SpaceByte's performance. Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: Tables 1 and 2 give upper bounds for the 1-sigma statistical error and clarify that these statistical errors account for the finite number of evaluation samples. We also estimate the statistical uncertainty due to the different test splits used by other works in Section 6.Guidelines:• The answer NA means that the paper does not include experiments. 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 circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment 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 not tied to particular applications, let alone deployments. However, if there is a 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, it 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. • If 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 ML). 
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 or models.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is 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. • We recognize that the procedures for this may vary significantly between institutions and locations, and we 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 as the institution conducting the review. 
 
 Appendix: Hyperparameters for models shown in Table 1 and Table 2 are summarized in Table 3 and Table 4 , respectively. In Figure 4 , we show another perspective of Figure 3 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), we tie the input embedding weights with the output linear matrix weights [54] . In self-attention layers, we use a key dimension equal to 64. Although we apply RoPE embeddings, we also included trained position embeddings.SpaceByte For SpaceByte, we include trained position embeddings just before the first local transformer block, and just before the first global transformer block. m global = L global × 4D 2 Global multi-head attention + L global × 2e ff D 2Global feed-forwardm local = D local D P Global-to-local projection + L local × 4D 2 local Local multi-head attention + L local × 2e ff D 2 local Local feed-forward + D local V De-embedding SpaceByte m global = L global × 4D 2 Global multi-head attention + L global × 2e ff D 2Global feed-forward Just like the other models, SpaceByte is trained using a fixed context size of T bytes. At the same time, we also fix the maximum global context size of T global patches. However, the number of patches in a given context of T bytes is usually not exactly equal to T global . To handle this mismatch during training, if the number of patches from applying the patching rule (see e.g. Figure 2 ) to a context of T bytes is greater T global , then we simply ignore the bytes within these extra patches when calculating the cross entropy. Alternatively, if the number of patches is less than T global , 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 is always a tensor of same shape for each iteration. This discrepancy between the maximal global context size T global and the actual number of patches results in a small fracton of wasted compute during training, which we roughly minimize by roughly tuning T /T global . See Appendix C for pseudocode.m local = L local × 4D 2 local Local multi-head attention + L local × 2e ff D 2 local Local feed-forward + D local V De-embeddingDuring inference, the model must stop predicting tokens before either the max number of bytes (T ) or the max number of patches (T global ) is reached.The inference FLOPs-per-byte is the number of FLOPs required to output a byte of text during inference. We calculate the FLOPs-per-byte as the FLOPs-per-token divided by the average number of bytes per token (which is equal to 1 for byte-level models).The FLOPs-per-token is the number of FLOPs required to output a token of text during inference (or byte of text for byte-level models). The FLOPs-per-token for the various architectures is shown in Table 6 .Notation For all architectures, T is the context length; D is the model dimension (of the global model for SpaceByte and MegaByte); e = 4 is the model dimension expansion factor for feed-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, L 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, D local is the dimension of the local model; L local is the number of local transformer blocks; and L global is the number of global transformer blocks. For SpaceByte, T global is the maximum context size for the global model, and W local (which we set to D local ) is the attention window size for the local blocks. For MegaByte, P is the patch size.Each dataset prepared by downloaded it from Hugging Face8 , concatenating sequences together, and separating sequences with a special BOS token. When preparing a training sample with context size T , we uniformly and randomly sample a sub-sequence of length T from the concatenated dataset. If a BOS token is found in this subset, we align the context with the first BOS token found; i.e. we take the context to 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 is 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: spm_train --input=train.txt --model_prefix=sp --model_type=bpe --vocab_size=50257 --num_threads=32 --byte_fallback=True --allow_whitespace_only_pieces=True --remove_extra_whitespaces=False --normalization_rule_name=identity --input_sentence_size=10000000All models are trained using AdamW [55] with β 1 = 0.9, β 2 = 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 a normal distribution with standard deviation σ init = 1 for all parameters except for linear weight matrices, which are initialized with standard deviation of σ init = 1/ √ d in , where d in is the input dimension for the linear layer. We scale the learning rate for each parameter by its initialization standard deviation σ init .With this setup, we found in our early hyperparameter search experiments that the optimal max learning rate for all models is approximately γ = 0.005B -0.5 = 0.000625, where B = 64 is the batch size. We therefore used γ = 0.000625 as 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 a "half-cosine" learning rate decay function cos(πx/2), where 0 ≤ x ≤ 1 is the fraction of training iterations completed. 9Each model was trained using PyTorch on a single 40GB Nvidia A40 and A100 GPUs with mixedprecision (bfloat16 and float32) training and FlashAttention [57, 58] . SpaceByte-793M+184M took the longest to train, requiring about 10 days on an A100 GPU. 3 , where we plot the bits-per-byte vs the number of bytes used for training divided by the number of non-embedding parameters (defined in Table 5 ).We train models using a grid of different model dimensions and numbers of layers. In our early small-scale experiments, we found that the hyperparameter grid described below effectively explores the bits-per-byte and FLOPs-per-byte 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 1 or 3 2 . For models trained using 10 18 FLOPs, we train model dimensions D ∈ {384, 512, 768}. For models trained using 10 19 FLOPs, we train model dimensions D ∈ {512, 768, 1024}.For SpaceByte and MegaByte, D is the global model dimension. The local model dimension is chosen fromD local ∈ { 1 2 D, 3 4 D} if D is a power of two, or D local ∈ { 1 2 D, 23 D} if D is a power of two times 3 2 . However, in order to avoid excessively low FLOP utilization, we restrict D local ≥ 256 (or D local ≥ 384) for models trained using 10 18 FLOPs (or 10 19 FLOPs).To set the number of layers, we roughly follow Levine et al. [59] , who found that the compute-optimal number of layers for a Transformer roughly follows L ∼ 12.5 log 2 (D/154). We round this number to the nearest half-power of two to obtain L D , for which L 384 = 16, L 512 = 24, L 768 = 32, and L 1024 = 32. For Transformer models, we choose the number of layers from L ∈ { 1 2 L D , L D }. For SpaceByte and MegaByte models, we choose the number of local and global layers fromL local = L global ∈ { 3 8 L D , 1 2 L D } if L D is a power of two, or L local = L global ∈ { 1 3 L D , 1 2 L D } if L D is a power of two times 3 2 .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 github.com/kjslag/spacebyte. (1) 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.(2) Our experiments show that for a fixed training and inference compute budget, SpaceByte outperforms other byte-level architectures and (3) roughly matches the performance of tokenized Transformer architectures." These claims are substantiated in Sections 5 and 6. The first claim is supported by Figure 3 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 in 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. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.See also Andrej Karpathy's tweet twitter.com/karpathy/status/1657949234535211009 and video youtube.com/watch?v=zduSFxRajkE&t=6725s on the disadvantages of tokenization.UTF-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 a leading byte (which is spacelike by our definition) followed by one or more continuation bytes (which are not spacelike).The bits-per-byte (BPB) is equal to BPB = XE Ntokens/(Nbytes ln 2), i.e. the cross entropy per token (XE) times the number of tokens per byte (Ntokens/Nbytes) divided by ln 2 (to convert nats to bits). Ntokens and Nbytes are the number of tokens and bytes in the dataset, respectively. For byte-level models, Ntokens = Nbytes since bytes are used in place of tokens.We note that in order for memory bandwidth to not be a bottleneck during inference, the batch size must be sufficiently large and e.g. grouped-query attention[39,40] must be used.We also tried a simplified Sparse Transformer[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 a sliding window attention.Our training code and data reproduction steps can be found at github.com/kjslag/spacebyte.Yu et al.[7] andWang et al. [6] also show results for a "Books" dataset[42] derived from Books3 (which is similar to PG-19 but also includes modern books). However, the legality of obtaining Books3 is questionable due to copyrights. We consequently exclude comparisons to this dataset.https://huggingface.co/datasets/pg19 https://huggingface.co/datasets/lucadiliello/STORIES https://huggingface.co/datasets/monology/pile-uncopyrightedIn our setup, we found cos(πx/2) to slightly outperform the more standard cosine decay from 1 to 0.1.We very roughly estimate that additional preliminary and failed experiments not shown in this work required roughly as many FLOPs as the experiments shown in this work. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: Is there any specific reason you did not include evaluations on downstream tasks?
limitations: limitations: Yes, the authors discuss limitations as part of the conclusion.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. There is no ablations as to whether the global blocks actually need larger dimension.
3. Presentation of the paper could be improved. See my question/suggestion in the next section.
questions: questions: ### Presentation Suggestions

1. 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.
2. I'd suggest switching Section 2 and 3 and talk about related work first.
3. 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.

### Questions

1. 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).
2. Why set the dimension and context length equal?
3. 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?
4. 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: limitations: See weakness point 1. I'm relatively confident that this could be a potential limitation that needs to be addressed.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The novelty of the SpaceByte approach may be limited by similarities to previous models.

2. The study's focus on specific languages, without detailed experiments on broader language datasets, limits the generalizability of the findings.

3. The paper could benefit from a more extensive discussion on the unique contributions of SpaceByte compared to existing models.
questions: questions: 1. How do the authors plan to address the limitations in generalizability to languages beyond the ones studied in the current work?

2. 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: * 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.
* It would have been nice to see some ablations on the architecture (for example, the local -> global -> local layer ordering seems a little arbitrary).
* 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.
* 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).
questions: questions: Please see weaknesses for my questions.
limitations: limitations: Yes. The paper does a good job of this.

Comments: title: Post-rebuttal Comment
comment: Thank you for the very detailed rebuttal. It clarified my main confusions during my first read of the paper.

Re: Question 1 -- By "adequately" I mean train until convergence, but your budget argument is valid and I will take it.

I still have reservations on the practicality of the proposed method (esp. batching), but otherwise I think the paper should be accepted. I'm improving my final evaluation to "weak accept".

Since the authors also agree that batching is challenging with this proposal, please make sure you make some space to address  this issue/limitation in the final draft of the paper.