MEGABYTE: Predicting Million-byte Sequences with Multiscale Transformers
Authors: LILI YU
Daniel Simig
Colin Flaherty
Armen Aghajanyan
Luke Zettlemoyer
Mike Lewis
Venue: NeurIPS 2023 poster (2023)
Keywords: byte level language model
model architecture
efficient pretraining
TL;DR: Megabyte enables sub-quadratic self-attention, much larger feedforward layers and improved parallelism during decoding. It can effectively model text, image, and audio directly from bytes.

Abstract: Autoregressive transformers are spectacular models for short sequences but scale poorly to long sequences such as high-resolution images, podcasts, code, or books. We proposed Megabyte, a multi-scale decoder architecture that enables end-to-end differentiable modeling of sequences of over one million bytes. Megabyte segments sequences into patches and uses a local submodel within patches and a global model between patches. This enables sub-quadratic self-attention, much larger feedforward layers for the same compute, and improved parallelism during decoding---unlocking  better performance at reduced cost for both training and generation. Extensive experiments show that Megabyte allows byte-level models to perform competitively with subword models on long context language modeling, achieve state-of-the-art density estimation on ImageNet, and model audio from raw files. Together, these results establish the  viability of tokenization-free autoregressive sequence modeling at scale.

MEGABYTE: Modeling Million-byte Sequences with Multiscale Transformers
Lili Yu
Dániel Simig"
Colin Flaherty
Armen Aghajanyan
Luke Zettlemoyer
Mike Lewis
Meta AI
Abstract
Autoregressive transformers are spectacular models for short sequences but scale poorly to long sequences such high-resolution images, podcasts, code, or books. We propose MEGAB YTE, a multi-scale decoder architecture that enables end-to- end differentiable modeling of sequences of over million bytes. MEGAB YTE segments sequences into patches and uses a local submodel within patches and a global model between patches. This enables sub-quadratic self-attention, much larger feedforward layers for the same compute, and improved parallelism during Brroding--ullckiigg better performance reduced cost for both training and gen- eration. Extensive experiments show that MEGAB allows byte-level models perform competitively with subword models long context language mod- eling, achieve stat-oof-theaue density estimation on ImageNet, and model audio from raw files. Together, these results establish the viability of tokenization-fice autoregressive sequence modeling at scale.
Introduction
ga
by
tran
sfor
Sequences of millions of bytes are ubiquitous; for example, music, image, or video files typi- cally consist of multiple megabytes. However, large transformer decoders (LLMs) typically only use several thousand tokens of context (Brown et al. 2020; Zhang et al. [202aa] both because of quadratic cost self-attention but also, more importantly, the cost of large feed- forward networks per-position. This severely limits the set of tasks where LLMs can be ap- plied.
loodloout
Local Modal
Local Model
Local Model
Modal
A Incal-io
m
by
o
he Alobbal-ore
Global Model
h globaliii
Patch Embed
Patch Embed
Patch Embed
Embed
We introduce MEGABYTE, a new approach to modeling long byte sequences. First, byte se- quences are segmented into fixed-sized patches, loosely analogous to tokens. Our model then consists of three parts: (1) patch embedder, which simply encodes a patch by losslessly con- catenating embeddings of each byte, (2) global module, large autoregressive transformer that inputs and outputs patch representations and (3) a local module, a small autoregressive model that predicts bytes within patch. Crucially, observe that for many tasks, most byte predictions
A ggmbeed
g
by
Figure 1: Overview MEGABYTE with patch size 4. A small local model autoregressively predicts cach patch byte-by-byte, using the output of larger global model to condition previous patches. Global and Local inputs are padded by P and token respectively to avoid leaking information about future tokens.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

layer with m.P parameters once Esiaball ambed + E
E (O.TT), Exbbbaa embbed embeed
E ER VxD.
Eon C TTD Hombell C CRTxDo
plubal-in
podkoual-pad
k O, A (1; K):
gebbal RxDDo K
Nembed
((kk 1)- ().
globulloot
transformer
He seolbubiin E RXP.D
D:
localin
GL (.
out
Dloaal Ploea-enbed 2th 112-1)"
ipp= [I..,, P)
Elocal pud RRD, vo
DoXD
k.
Elocal embed
CRVDDL
Pg,0:P
keaa-on
transformer" foeal beakiin
A K,
Ancakin
ER bloss-om
E ERKxP.DE
p(n, (20:s) softmax Egdocal emaeed local out
t=
Summary of MEGABYTE with vocabulary V. sequence length T' global and local dimensions De and Dr, and K patches of size P. Transformer layers use masked self attention to not observe future timesteps.
Figure 2:
relatively easy (for example, completing word given the first few characters), meaning that large networks per-byte are unnecessary, and a much smaller model can be used for intra intra-patch modelling.
MEGABYTE has three main advantages over Transformers for long sequence modeling:
1. Sub-quadratic self-attention Most work on long sequence models has focused on mitigat- ing the quadratic cost of self-attention. MEGABYTH decomposes long sequences into two shorter sequences, and optimal patch sizes reduces the self-attention cost to ((N which remains tractable for even long sequences.
2. Per-patch feedforward layers In GPT3-size models, more than 98% of FLOPS used in computing position-win wise feedforward layers. MEGAB YTE uses large feedforward layers per-patch rather than per-position, enabling much larger and more expressive models for the same cost. With patch size P. where a baseline transformer would use the same feedforward layer with parameters P times, MEGAB YTE for the same cost.
3. Parallelism in Decoding Transformers must perform all computations serially during generation because the input to each timestep the output from the previous timestep. By reusing the global representation over multiple time steps during local model decoding, MEGAB YTE allows greater parallelism during generation. For example, a MEGAB BYE model with 1.5B parameters can generate sequences 40% faster than standard 350M Transformer, whilst also improving perplexity when trained with the same compute.
Together, these improvements allow to train much larger and better-performing models for the same compute budget, scale to very long sequences, and improve generation speed during deployment.
MEGABYTE also provides strong contrast to existing autoregressive models that typically use some form of tokenization, where sequences of bytes are mapped to larger discrete tokens (Sennrich et al. 2015 Ramesh et al. | Hsu et al. 202I). Tokenization complicates pre-processing, multi-moda modelling, and transfer to new domain,, while hiding useful structure from the model. also means that most state-of-the of-the-art models are not truly end to end. The most widely used approaches to tokenization require segguage-specffii heuristics (Radford et al.) (2019) or lose information (Ramesh) al. (021). Replacing tokenization with efficient and performant byte models would therefore have many advantages.
We conduct extensive experiments for both MEGABYTE and strong baselines. We use fixed compute and data budget across all models to focus our comparisons solely on the model architecture rather than training resources, which are known to benefit all models. We find that MEGABYTE allows byte-level models to perform competitively with subword models on long context language modeling, achieve state-of-the ofte-of-thheart perplexities for density estimation ImageNet, and allow audio modelling from raw audio files. Together, these results establish the viability of tokenization -eeeeeeoooneoeeeeeeeeee autoregressive sequence modeling at scale.

---

2 MEGABYTE Transformer
2.1 Overview
MEGABYTE is an autoregressive model for efficiently modeling long imput sequences. MEGABY is comprised of 3 components: (1) a patch embedder that inputs a discrete sequence, embeds each element, and chunks into patches of length P (2) large global Transformer that contextualizes patch representations by performing self-attention over previous patches, and (3) smaller local Transformer that inputs contextualized patch representation from the global model, and autoregressively predict the next patch.
2.2 Components
Patch Embedder with patch size of P maps a byte sequence vo..r to a sequence of patch embeddings of length K = and dimension P- Dc.
First, each byte is embedded with a lookup table Eg E I VxDD to an embedding of size De and positional embeddings are added.
ht
embed
Eyglohll-emher
+ E
E [0..I]
Then, byte embeddings are reshaped into sequence of K patch embeddings with dimension P- De- To allow autoregressive modelling, the patch sequence is padded to start with trainable patch-sized padding embedding (EEzlobul-pad E Px) and the last patch is removed from the input. This sequence is the input the global model, and is denoted Aallbal-i R ((P)De),
Eglobal-pad
if =0 O,
lk
glohal-in
(2)
gembed ((k-1) P):
k E (I,,,,K).
Global Model is decoder-only Transformer with dimension P. DG that operates sequence of K patches. It incorporates a self-attention mechanism and causal masking to capture dependencies between patches. It inputs a sequence of K patch representations N slobull-i and outputs an updated representation fo:K
h,global-our by performing self-attention over previous patches.
h
global-out o:K
= transformer global-in
(3)
The output of the final global layer Aglobal contains K patch representations of dimension P Da- For each of these, we reshape them into sequences of length P and dimension DG. where position uses dimensions p DG to (p + 1) DG. Each position is then projected to the dimension of the local model with a matrix Gl. E IR De XD1 where D,. is the local model dimension. We then combine these with byte embeddings of size Dr. for the tokens in the next patch Flocal-embed. The local byte P'/e.Ptp-1)"
embeddings is offset by one with trainable local padding embedding (Elocal E PE) to allow autoregressive modelling within patch. This results tensor loloaal in RxXxxx
h local-in
GL p out k. (olp-DD)oo (c)(((++)))))) + Elocal-embed Pa(k.--p-1)
k.p
Local Model is a smaller decoder-only Transformer of dimension Dr that operates on single patch & containing P elements, each of which is the sum of an output from the global model and an embedding of the previous byte in the sequence. K copies of the local models are run on each patch independently (and in parallel during training), computing a representation local-ouu E R Kx x. D.
local-out = transformer (1 D.D:
local-in
(5)
Finally, we can compute the probability distribution over the vocabulary at each position. The pth element of the kth patch corresponds to element of the complete sequence, where k- P p.
p( softmax ( locall-embod 1 local-out
k.p
(6)
3

---

2.3 Variations and Extensions
Convolutional Patch Encoder:
One limitation of patchifying sequences is that it is not translation their position in
invariant, and byte sequences may receive different representation depending the patch. This may mean, for example, that a model has to relearn the meaning of a word at different offsets. To mitigate this issue, we experimented with augmenting the Patch Embedder with causal convolutional layers, which allow translation-invarian contextual representations of the bytes before they are chunked into patches. We use stack of convolutional layers, with filter sizes of 3, 5 and 7.
The Local model uses short sequences for efficiency, and relies on the Global model for long-range information. However, we can increase the context of the Local model with little overhead by allowing it to condition on r elements from the previous patch. This approach allows the Global model to focus a longer-range context. Specifically, when computing self- attention in each layer, we concatenate the keys and values with the last r' keys and queries from the previous patch. We use rotary embeddings (Su et al., (02T)) to model relative positions between elements in the sequence. This approach is reminiscent of TransformerX1. (Dai et al. 2019) but differs by being fully differentiable.
posss-pacch&aa Attention:
Strided Inference: We observed empirically that the per-token loss within each patch increases towards the end of the patch, as the prediction relies more on the weaker Local model. To alleviate this issue, we propose strided inference, in which we predict the sequence with two forward passes of the full model, whose inputs are offset by p/2 positions from each other. We then combine the first p/2 positions in each patch for our predictions to predict the complete sequence. Similarly to sliding window methods (Press et al. 2020), this approach doubles the cost of inference but improves results.
3 Efficiency Analysis
3.1
Training Efficiency
Attention The cost of attention in transformer architecture for sequence of length T has O
complexity. Much work has been explored reducing this; for example, Sparse Transformers (Child
et al.
2019) and Routing Transformers (Roy et al. 2020) show strong results with a complexity
OTT))
Many linear attention mechanisms have also been proposed (Katharopoulos et al. 2020
Choromanski et al. 20200, although we are not aware of competitive results on large scale language modeling tasks. Asa a function of sequence length T' and patch size P, the Global model has sequence of length P.
operations, and the Local model uses f sequences of length P so uses O (PT) operations. The overall cost of MEGAB YYTE is therefore in O O To + TP). P hyperparameter that is chosen to create an architecture for sequences of size T. By setting P = T the complexity is in O(T 3). Using much shorter patches of P = 7 would give complexity of O ). The cost is less than the transformer for all non-trivial values of P such that 1 < <.
T so uses O T
pz
Feedforward Layers However, attention is not the main cost in large transformers. Instead of increasing the sequence length, transformers are more commonly scaled by increasing the dimension of their latent state d, and the feedforward network cost dominates the model's ss overall cost (Kaplan) ctt al. 2020). For example, in the GPT3 architecture, the quadratic self-attention computation accounts for only 1.4% of FLOPS. Following the approximation of (Kaplan al.) 2020). a forward pass with a large transformer with m non-embedding parameters on a sequence of length T uses roughly 2mT FLOPS. MEGAB YTE contains two transformers: the Global model uses my parameters sequence of length p. and a Local model with my parameters that sees T sequences of length P. giving an estimate of 2T ma
p + mi) FLOPS. When my >> my, the FLOPS used by MEGABY BYT is approximately 2Tm,, allowing model P times larger than a transformer with equivalent FLOPS. This analysis holds irrespective of any efficient attention mechanisms used in the transformer.
Combined Analysis To understand efficiency at different sequence lengths and model sizes, we calculate the total FLOPS used by transformers, Linear Transformers and MEGABYTE, For each operation,
FL.OP estimates from (Kaplan al., 2020)) except for attention in Linear Transformers, which we estimate as 97 FLOPShoker] where D is the model embedding dimension. Figure 3 shows that for models of size 660M to 173B and sequence lengths of up to 1M tokens,
'This may underestimate the time taken by Linear Transformer decoders, which use recurrence mechanism that is harder parallelize current hardware.

---

MEGABYTE with P = 8 uses less FLOPS than either transformers or Linear Transformers, Baseline model architectures are based on GPT3, and Megabyte global/local model sizes are 452M/151M, 5.8B/604M, 170B/3.28 3.2 respectively.
3.2 Generation Efficiency
Tansforme6601M
Linear604M
16g
Generating long sequences with transformers is slow, because the input to each timestep is the output from the previous timestep, meaning each layer must be computed for each token serially, As running a layer on a single token typically does not saturate the amount of parallelism avail- able within a GPU, for analysis, we model each layer as constant cost independently of size. Consider MEGA YTE model with Lyglball lay- ers in the Global model and Licaa layers in the Local model and patch size P. compared with a Transformer architecture with Livaal + Lggnbal layers. Generating each patch with MEGABYTE requires a sequence (T + P. Tooaal) serial operations, whereas the Transformer quires O(P-Lgsbal
Transformer..o
Linear6.48
MagaByto6.58
Wraddtrmer773
Linear1738
MogoByte1738
10a2
FLOPSitoken
10a1
10.0
10*
10a
256
2048
16384
131072
1048576
Sequence Length
Figure 3: Computational cost (FLOPS/token) for differ- ent model architectures at different scales. MEGABYTE architectures (here with P = 8) use less FLOPS than cquivalently sized Transformers and Lincar Transform- ers (Katharopoulos al. 2020) across a wide range of model sizes and sequence lengths, allowing larger mod- els to be used for the same computational cost.
serial operations. When Lglobal >> Liocal (i.e. the Global model has many more layers than the Local model), MEGABYTE reduce inference costs by factor close to P.
4 Experimental setup
Controlling for Compute and Data Models show consistent improvements when increasing both data and compute Kaplan al. (2020); Hoffmann et al. (2022), meaning that one model can outperform another because of an increased training budget instead of improved architecture. However, in practice, both compute and data are typically limited. We conduct experiments using a fixed compute and data budget across all models to focus comparisons solely on the model architecture rather than training resources. To achieve this, we adjust model hyperparameters (mainly, number of layers) within each architecture that the forward pass time taken per byte is matched, and then train all models for the same number of bytes.
Comparison Systems We compare MEGAB with both a standard decoder-only Transformer and PerceiverAR (Hawthorne et al., 2022 PerceiverAR extends the original transformer with single cross-attention layer over a much longer context sequence, and is the best performing general purpose autoregressive model we are aware of and achieves state-of-the-an results across several modalities. We implemented both models in the same codebase, and all models share a similar data loader, preprocessing step, and trainer to avoid any artifacts in our compute-controlle experiments.
Training Procedure All models were trained using M base Zhang et al. (202bb). The training used the Py PyTorc framework Paszke et al. (2019), with fairscale to improve memory efficiency through fully sharded model and optimizer states Baines et al. (202T). Mixed precision training was used to improve training efficiency at scale Micikevicius er al. (2017). More training details and various model parameters can be found in Section A.. in the Appendix. To validate implementation of PerceiverAR, we reproduced their experiments on downsized ImageNet at 64 pixels. By carefully matching hyperparameters, we achieved a bits per byte (bpb) score of 3.53, compared to the reported 3.54 in the original paper.
Inference Methods Several techniques have been proposed for trading off speed for performance during inference with language models, including sliding windows Press et al. (2020) and our strided inference. We only use these methods when comparing with prior published work (Tables andd 3).
5

---

Dataset
Total Bytes
bytes/doc
Transformer
PerceiverAR
MEGABY YTE
PG-19
10.1GB
411,404
1.057
1.104
1.000
Stories
21.3GB
35,265
1.064
1.070
0.978
Books
79.7GB
509,526
1.097
1.104
1.007
arXiv
91.5GB
58,518
0.816
0.791
0.678
Code
353.7GB
7,461
0.575
0.546
0.411
Table 1: Text dataset sizes and mean document lengths. We also report bph of various models ( (Transformer, PerceiverAR, and MEGABYTE) trained with the same compute.
Tokenizer
Vocab
Context Length
Validation
Test
TransformerXL Rae al. (201aa)
SentPiece
32k
512+1024
45.5
36.3
Compressive Transformer Rac al (019a)
SentPicce
32k
512+51242x512
43.4
33.6
PerceiverAR Hawthorne ét al. 2
SentPiece
32k
2048
45,9
28.9
BlockRecurrent Hurchhn et at.
2022
SentPiece
32k
1024+rccurrence
26.5
Transformer byte-level (ours)
Bytes
256
2048
81.6
69.4
PereeiverAR byte-level (ours)
Bytes
256
8192
119.1
88.
MEGABYTE
Bytes
256
8192
42.8
36.4
Table Larger scale experiments on PG19, converting bits-per-byte word-level perplexities comparison with prior work. Results below the line are compute-matched. MEGABY TE outperforms other byte models by a wide margin, and gives results competitive with statc-of-the-art models trained on subwords.
Language Modeling
We evaluated the performance of MEGABYTE on language modeling on a set diverse datasets emphasizing long-range dependencies: Project Gutenberg (PG-19), Books, Stories, arXiv, and Code.
Datasets We experiment on range of long form text datasets. The PG-19 dataset Rae al. (2019b) consists of English-language books written before 1919 and is extracted from the Project Gutenberg online library The Stories dataset Trinh Le (018) subset of CommonCrawi data meant to emulate Winograd schemas. Books Gao et al. (2020) is another collection of English-languaat The arXiv dataset contains technical publications written in IЯTEX from the aiv online archive Finally, the Code dataset is a large publicly available dataset of open source code, under Apache, BSD or MIT licenses. More details on dataset sizes and document lengths are shared Table
books.
Controlled Experiments Table D lists bpb on each dataset. Each model is trained for 80 billion bytes, and models scaled architectures to best utilize the available compute budget. MEGAB YTE consistently outperforms both transformers and PerceiverAR across all datasets. We use the same sets of parameters on all dataset. In all experiments presented in Table I transformer has size of 320M with context length of 1024, PerceiverAR has size of 248M with context size of 8192 and latent size of 1024, and MEGAB BYEE global/local model sizes are 758M/262M with context length of 8192 and patch size of 8.
the same compute budget. We carefully tune hyperparameters for all
Scaling Experiment We scale up training data on PG-19 (Table 2 and compare MEGABYTE with byte baselines, as well as converting all results to word-level perplexitess to benchmark with state- of-art token based models. We train byte-level Transformer, PerceiverAR and MEGAB models for 400B bytes and the same compute budget using same model parameters as in the controlled experiments, We find that MEGAB YTE outperforms other byte-level models by a wide margin at this scale We also compare with the best previously reported numbers for sub-word models. These results may be confounded by differing amounts of compute and tuning used, but show that MEGABY BTE gives results competitive with state-of-the th-tth-art art models trained on subwords. These results suggest that MEGABYTE may allow future large language models be tokenization-free.
Image Modeling
Sequence Modeling on ImageNet We test MEGABYTE on variants of the autoregressive image generation task on ImageNet (Oord et al. 2016), to measure its ability to efficiently use long context. We test on three different resolutions of images, ranging from 64x64 640x640 pixels the latter
'The only prior byte-level experiments we are aware of are at a smaller seale in Hutchins et al, (2022), who report results equivalent to test perplexities of 46.5 with version of the BlockReeurrent transformer, and 49.5 with Memorizing Transformers Wu al. 2022), compared to 36.4 with model.

---

requiring the effective modeling of sequences with over 1.2M tokens. This generation task becomes increasingly challenging as the image's resolution grows: doing well on this task requires the modeling of local patterns (textures, lines, etc.) and long-range context that provides information about the high level structure of the image. Inspired by recent works in Vision Transformers (Dosovitskiy et al. 2020), we model image data patch by patch (more details can be found in Appendix
Comparison with State of the Art We train large MEGAB YTE model on ImageNet 64x64 with Global and Local models sized 2.7B and 350M parameters, respectively. for 1.4T tokens. We estimate that training this model consumed less than half the GPU hours we would have needed reproduce the best PerceiverAR model described by (Hawthorne et al.) 2022). As shown in Table matches the tate-of-the-ar performance of PerceiverAR whilst using only half the compute.
2 MEGAB YTE
ImageNet64
bpb
Context
Image64
Image256
Image640
Routing Transformer (Ry al.
2020
3,43
Total len
12288
196608
1228800
Combiner (Ren et al. 2021)
3.42
Perceiver AR (Hawthoree et al. 2022
3.40
Transformer 1024
3.62
3.801
2.847
MEGABYTE
3,40
Perceiver AR 12000
3,55
3,373
2.345
Table 3: Bits per byte (bpb) on ImageNet
MEGABYTE
Full 3.52
3.158
2.282
64x64. MEGABYTE matches the current state-of-the-an while only using half the amount of GPU hours to train.
Table 4: Bits per byte (bpb) on ImageNet with different resolutions. All models use the same compute and data. MEGABYTE scales well to sequences of over 1M tokens.
Scaling to higher resolutions We compare three transformer variants (vanilla, PerceiverAR, MEGABYTE) to test scalability to long sequences increasingly large image resolutions. We use our own implementations of these in the same framework and budget the same amount of GPU hours and data to train each of these model variants.
MEGA BYTE is able to handle all sequence lengths with a single forward pass of up to 1.2M tokens. We found neither the standard Transformer nor PerceiverAR could model such long sequences at a reasonable model size, so instead we split images into segments of size 1024 and 12000 respectively. For Megabyte, and Image640 datasets. Model sizes are adjusted to match overall training speeds across models and we do not use any form of sliding window evaluation in this experiment. As seen in Table 4 MEGABYTT outperforms baselines across all resolutions in this compute-controle
set patch size 12 for Image64 and patch size 192 for Image256
setting, The precise settings used for each of the baseline models such as context length and number of latents are summarized in Table 12] Results show that MEGA BYTE YTE outperforms the other systems at all resolutions, demonstrating an effective model of sequences of over 1M bytes.
7 Audio Modeling
Audio has aspects of both the sequential structure of text and the continuous nature of images, so is an interesting application for MEGABYTE.
Raw audio is typically stored as sequence of 16-bit integer values (one per timestep); a softmax layer would need to output 65,536 probabilities per timestep to model all possible values. To address this issue, various techniques have been developed to reduce the memory and computational requirements of the softmax layer. For instance, vaa den Oord et al. (2016) apply μı-law companding transformation and quantizes the input into 256 possible values. Alternatively, van den Oord et al. (2017) model the samples using the discretized mixture of logistics distribution introduced by Salimans et al. (2017). Finally, Kalchbrennerr al. (2018) use dual softmax technique to produce 8 coarse and 8 fine bits. In our approach, we simplify the audio modeling process by directly reading the bytes (256 possible values) from the audio file and conducting autoregressive language model on top of that. This greatly streamlines the modeling process, making it easier and more efficient.
Our audio modeling approach focuses on 16 kHz, 16-bit audio, which equates to 32k bytes per one-second clip. We use an extensive audio dataset consisting of 2 terabytes (roughly 18,000 hours) of audio. We use sequence length of 524,288, patch size of 32, and batch size of 32 to facilitate model training. By utilizing these settings, we can effectively train our model on large volumes of audio data, helping to improve its accuracy and efficacy. Our model obtains bpb of 3.477, much
7

---

Global Size
(Local) Size
Generation
bph
Time (s)
Transformer MEGABYTE
350M
1.064
132
1.3B
218M
0.991
93
Table 5: Comparison of bits per byte (bpb) and generation speed of 8192 bytes of transformer model (with context length 1024) and MEGABYTE with context length 8192 and patch size 8.
lower than the results with perceiverAR (3.543) and vanilla transformer model (3.567). More ablation results presented in Table
Analysis
We study different behaviors of MEGABYTE. experiments in the same group use the same compute.
We also compare the text generation speed between MEGABYTE and a trans- former. We compare 350M parameter baseline transfomer and MEGAB model with 1.3B parameter Global model and a 218M parameter local model, trained on PG19 with equal compute. As shown in Table 5 the MEGABYTE model achieves much lower perplexity as expected. However, MEGABYTE YTE also generates sequence of 8192 tokens 40% faster than transformer, despite having over 4 times the parameters. This speed up is due the bulk of the parameters being the Global model, which only needs to be computed once for every 8 tokens, whereas all the parameters in the baseline model are used on every token.
Generation speed
Model Components In Table [ we analyze the significance of different components in the MEGABYTE architecture by studying arXiv, Librilight-L. and ImageNer256 datasets. Removing Local (w/o local model) global (w/o global model) model, observe substantial increase in bpb all datasets, showing that both parts are crucial. The performance of the model without the pross-patch local model (w/o cross-patchs local model) is competitive, indicating that the architecture is robust to this modification. We observe slight improvement on the Librilight-L and ImageNet256 datasets by augmenting the MEGABYTE model with a CNN encoder (w/ CNN encoder). This suggests that the MEGABYTE architecture can benefit from integrating alternative encoding mechanisms.
Effective Use of Context Long-context models often struggle to benefit from the full context (Sun) et al. 2021). Figure 7 shows that later tokens within each context window have higher likelihood, indicating that MEGA YTE can effectively use at least 8k bytes of context on the PG19 dataset.
Arxiv
Audio
Image256
MEGABYTE
0.6871
3.477
3.158
local model
1.263
5,955
4.768
w/o global model
1.373
3.659
3.181
w/o cross potsh attention
0.6781
3,481
3.259
w/ CNN encoder
0.6871
3.475
3.155
Vedla Sentiren 2322 undest brugh Thrafrrer alding sieetr zrids
Table 6: Ablation of MEGABYTE model components. Models with the same dataset are trained using the same compute. The hyperparameters are listed in Table
Table 7: Average log probability assigned different positions within context length by MEGAB and by a vanilla transformer model on PG19 test set.
probabiity
Method
Inference Cost
bpb
Used trcwns
Discur ded tokenn
-0.94
Basic Inference w/ Shiding Window w/ Strided Inference w/ Sliding & Strided
0.9079
PO5 IO IN.SEGUENCE
0.8918
2X
0.8926
Table 8: An illustration of strided inference with patch size 8. Blue and yellow represents two inferences that shifted by half patch size. Solid line indicates final probablity being taking during strided inference.
4X
0,8751
Table 9: Performance of various inference tech- niques on the PG19 test. using best MEGA B BYT model.

---

Strided Inference We find that within a single patch, on average, the MEGABYTE performs worse on later tokens within patch (see Figure B). Section 2.3 proposes strided inference as a solution, where two forward passes are performed offset by & tokens, and results from the first half of each patch are combined.
performance improvements from strided inference, which are additive with the standard sliding window.
Patch Size. We experimented with various patch sizes on Image256 dataset and found a wide range of values where MEGAB YTE performs similarly. We found similar robustness to patch size choices across all modalities, although the optimal patch size itself can be different across modalities.
Local to Global model Size Ratio. We experimented with different Local/Global model size ratios on PG19 dataset. By grouping bytes into patches, MEGAB YTE effectively uses P times less tokens for the Global model as on the Local model-enabling us to increase the size of the Global model with reduced cost. We find that given compute budget is spent optimally when the Global model is larger than the Local model, consistently across all modalities and various patch sizes.
Patch
Global Size
Local Size
bpb
Global Size
Local Size
bpb
48
125M
114M (L=11)
3,178
350M (D=1024.L=24)
290M (D=1024,L=20)
1.014
192
125M
125M (I=12)
3.158
760M (D=1536.1=24)
262M (D=1024.1=18)
1.002
768
125M
83M (L=8)
3.186
1.3B (D=2048.L=24)
218M (D=1024.L=15)
0.991
Table 10:
Effects of patch size on perfor-
Table 11: Effects of Local / Global model size the PGT9
mance on the Image256 dataset, All versions use the same amount of GPU hours and data.
dataset. Increasing the capacity of global model improves performance. Models are compute and data matched.
Related Work
Prior research has explored the possibility of improving the efficiency of Transformers on long sequences, primarily motivated by mitigating the quadratic cost of self-attention.
Efficient Encoder Models Several related techniques ours have been developed for transformer encoder architectures but cannot be straightforwardly applied to decoders. In particular, patchifying operations have previously been used in image encoder models such as ViT (Dosovitskiy et al., 2020). and down- and up-sampling operations have been used for text encoders (Clark et al.) (022). but such methods cannot be naively applied to decoder-only models without leaking information to future bytes in the same patch. MEGAB YTE generalizes these approaches to an efficient decoder model by using a intra-patch transformer to predict each sequence element's likelihood, and offseting the inputs to the two models to avoid leaking information. Jaegle et al. (202T) use self-attention on shorter latent sequence also resembles patchification, but this technique cannot easily be applied to decoder architectures without leaking information to future timesteps.
Efficient Decoder models Improving the efficiency of decoder models is harder because of the need to make one prediction per timestep, and not leak information to future timesteps. The most popular approaches can be categorized as (1) chunking sequences into smaller blocks, and propagating information from previous blocks with either recurrence (Dai et al., 2019 Hutchins et al. 2022) or cross-attention (Hawthorne et al. (202)) (2) linear alternatives to attention, which typically involve
forms of token-level recurrence (Katharopoulos et al. 2020) or state space models (Gu et al. 2021 Smith et al., 2022 Ma et al., 2022), or (3) sparse approximations of attention (Kitaev et al. 2020
Beltagy et al. 2020 Child et 2019 Wu et al.) (022). However, the performance of dense attention
means it is typically still chosen for large scale decoders (Touvron et al., 2023] Chowdhery et al..
2022). MEGAB YTE takes the alternative approach of decomposing the complete sequence into two shorter sequences, giving sub-quadratic attention. We also note that feedforward networks are the dominant cost in large decoders, not self-attention. Our approach to compressing sequences allows much larger models than would be possible when using large feedforward networks at every timestep.
Tokenization The most common approach to shortening sequence lengths in Transformer decoders is to pre-process the input with a form of tokenization, which multiple bytes are mapped to a single discrete token from fixed vocabulary. For text, this can be done losslessly using methods such as BPE (Sennrich et al. (015) and SentencePiece (Kudo & Richardson 2018), but these approaches can require language-specift heuristics (Radford et al. 2019), limit of performance (Sharami

---

et al. 2023), and can affect prompting and truncated sampling in unpredictable ways The amount of high-freee frequency information images and audio means that tokenization cannot be performed losslessly, and instead clustering (Hsu et al. 202T) or discrete auto-encoders (Ramesh et al. 202 are used compress the inputs, which lose information and likely limit generative model performance. Our patches are analogous to traditional lossless tokens, and the Local model performs the role of mapping a hidden state to a distribution over possible patches.
10 Conclusion
We introduced MEGABYTE, a scaleable architecture for modeling long sequences. MEGAB YTE outperforms existing byte-level models across range of tasks and modalities, allowing large models of sequences of over 1 million tokens. It also gives competitive language modeling results with subword models, which may allow byte-level models to replace tokenization. However, the scale of experiments here is far below those of state-of-the-art language models (Brown et al. 2020), and future work should explore scaling MEGABYTH to much larger models and datasets.
References
Baines, M., Bhosale, S., Caggiano, V., Goyal, N., Goyal, S., Ott, M., Lefaudeux, B., Liptchin- sky, V., Rabbat, M., Sheiffer, S., Sridhar, A., and Xu, M. FairScale: A general purpose mod- ular PyTorch library for high performance and large scale training. https://githe: com/ facebookresaarcc/faarrccaa 2021.
Beltagy, I., Peters, M. E., and Cohan, A. Longformer: The long-document transformer. arXiv preprint arXiv:2004.05/550 2020.
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et Language models are few-shot learners. Advances neural information processing systems, 33:1877-1901, 2020.
Child, R., Gray, S., Radford, A., and Sutskever, I. Generating long sequences with sparse transformers. arXiv preprint arXiv:1904. 2019.
Choromanski, K., Likhosherstov, V., Dohan, D., Song, X., Gane, A., Sarlos, T., Hawkins, P., Davis, J., Mohiuddin, A., Kaiser, L., et al. Rethinking attention with performers. arXiv preprint arXiv:2009. 14794, 2020.
Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., et al. Palm: Scaling language modeling with pathways. arXiv preprint ar XXXx:2204.02311 2022.
Clark, J. H., Garrette, D., Turc, I., and Wieting, J. Canine: Pre-training an efficient tokenization free encoder for language representation. Transactions the Association for Computational Linguistics, 10:73-91, 2022.
Dai, Z., Yang. Z., Yang, Y., Carbonell, J., Le. Q. V., and Salakhutdinov, R. Transformer-xl: Attentive language models beyond a fixed-length context, 2019. URL http::::/axxvvv.orr/eee abs/ 02860
Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al. An image worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11 1929, 2020.
Gao, L., Biderman, S., Black, Golding, L., Hoppe, T., Foster, C., Phang, J., He, H., Thite, A.. Nabeshima, N., Presser, S., and Leahy, C. The pile: An 800gb dataset of diverse text for language modeling, 2020.
Gu, A., Goel, K., and Ré, C. Efficiently modeling long sequences with structured state spaces. arXiv preprint 1eXiv:2111.00300 2021.
For example, whether prompt should end in whitespace depends details of the subword algorithm.
10

---

Hawthorne, C.. Jaegle, A., Cangea, C., Borgeaud, S., Nash, C., Malinowski, M., Dieleman, S.. Vinyals, O., Botvinick, M., Simon, I., al. General- purerse,, long-context autoregressive modeling with perceiver ar. In International Conference on Machine Learning, pp.
PMLR, 2022.
Hoffmann, J., Borgeaud, S., Mensch, A., Buchatskaya, E., Cai, T., Rutherford. E., Casas, D. d. L., Hendricks, L. A., Welbl, J., Clark, A., et al. Training compute-optimal large language models. arXiv preprini arXivv2208: /0000..5555.... 2022.
Hsu, W.-N., Bolte, B., Tsai, Y.-H. H., Lakhotia, K., Salakhutdinov, R., and Mohamed, A. Hubert: Self-super speech representation learning by masked prediction of hidden units. IEEE/ACM Transactions Audio, Speech, and Language Processing, 29:3451-3460, 2021.
Hutchins, D., Schlag. I., Wu, Y., Dyer, E., and Neyshabur, B. Block-recurrent transformers. arXiv preprint arXiv:2203.00 078552, 2022.
Jaegle, A., Gimeno, F., Brock, A., Vinyals, O., Zisserman, A., and Carreira, Perceiver: General
perception with iterative attention. In International conference machine learning, pp. 4651-4664.
PMLR, 2021.
Kalchbrenner, N., Elsen, E., Simonyan, K., Noury, S., Casagrande, N., Lockhart, E., Stimberg, F,, van den Oord, A., Dieleman, S., and Kavukcuoglu, K. Efficient neural audio synthesis. CoRR, abs/1802.00444 0842508435, 2018. URL http::/://aaxi org h/tg///b/////a 18020802200 08435
Kaplan, J., McCandlish, S., Henighan, T., Brown, B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., and Amodei, D. Scaling laws for neural language models. arXiv preprint arXiv:2001.08661, 2020.
Katharopoulos, A., Vyas, A., Pappas, N., and Fleuret, Transformers are mass: Fast autoregressive transformers with linear attention. In International Conference on Machine Learning, pp. 5156- 5165. PMLR, 2020.
Kingma, D. and Ba, J. Adam: A method for stochastic optimization. In ICLR, 2015.
Kitaev, N., Kaiser, L., and Levskaya, A. Reformer: The efficient transformer. arXiv preprint arXiv:2001.04451, 2020.
Kudo, T. and Richardson, J. Sentencepiece: A simple and language independent subword tokenizer and detokenizer for neural text processing. arXiv preprint 1rXiv:1808.002222 2018.
Ma, X., Zhou, C., Kong, X., He, J., Gui, L.., Neubig, G., May, J., and Zetteeoyee, L. Mega: moving average equipped gated attention. arXiv preprint arXiv:2209. 10655, 2022.
Micikevicius, P., Narang, S., Alben, J., Diamos, G., Elsen, E., Garcia, D., Ginsburg, B., Houston, M.,
Kuchaiev, O., Venkatesh, G., al. Mixed precision training. arXiv preprint 1711v:1700.03740, 2017.
Oord, A. v. d., Kalchbrenner, N., and Kavukcuoglu, K. Pixel Recurrent Neural Networks. ICML, 4:261 1-220,, 1 2016. doi: 14455500arxxi.1601.0067777 URL 06759v3
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, 7., Gimelshein, N., Antiga, L., et al. PyTorch: An imperative style, pegghperformance deep learning library. In NeurIPS, 2019.
Press, O., Smith, N. A., and Lewis, M. Shortformer: Better language modeling using shorter inputs. arXiv preprint arXiv:2012.15833 2020.
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, Language models are unsupervised multitask learners. 2019.
Rae, J. W., Potapenko, A., Jayakumar, S. M., and Lillicrap, T. P. Compressive transformers for long-range sequence modelling. arXiv preprint arXiv:1911.05500 2019a.
Rae, W., Potapenko, A., Jayakumar, S. M., and Lillicrap, P. Compressive transformers for rangerange sequence modelling. arXiv preprint arXiv:1911.05550 2019b.

---

Ramesh, A., Pavlov, M., Goh, G., Gray, S., Voss, C., Radford, A., Chen, M., and Sutskever, 1. Zero- shot rext-to-image generation. International Conference on Machine Learning, pp. 8821-8831. PMLR, 2021.
Ren, H., Dai, H., Dai, Z., Yang, M., Leskovec, J., Schuurmans, D., and Dai. B. Combiner: Full attention transformer with sparse computation cost, 2021. URLhtttps//arxxy, wwtpxxvwworg/bbb///////// 05768
Roy, A., Saffar, M., Vaswani, A., and Grangier, D. Efficient content-based sparse attention with routing transformers, 2020.
05997
Salimans, T., Karpathy, A., Chen, X., and Kingma, D. P. Pixelen+++: Improving the pixelenn with discretized logistic mixture likelihood and other modifications. CoRR, abs/1701.05517, 2017. URL
httt::/arxiv.co wrg. abs/ 1701 05517
Sennrich, R., Haddow, B., and Birch, A. Neural machine translation of rare words with subword units. arXiv preprint arXiv: 500. 079099 2015.
Sharami, J., Shterionov, D., and Spronck, P. A systematic analysis of vocabulary and bpe settings for optimal fine-tuning of nmt: case study of in domannii translation. arXiv preprint arX0v:2303.00722, 2023.
Smith, J. T., Warrington, A., and Linderman, S. W. Simplified state space layers for sequence modeling. arXiv preprint arXiv:2208.0499) 2022.
Su, J., Lu, Y., Pan, S., Murtadha, A., Wen, B., and Liu, Y. Roformer: Enhanced transformer with rotary position embedding. arXiv preprint 3rXiv:2104.09866 2021.
Sun, S., Krishna, K., Mattarella-Mick, A., and lyyer, M. Do long-range language models actually 09115, use long-range context? arXiv preprint arXiv:2 109.0995, 2021.
Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E.. Azhar, F., et al. Llama: Open and efficient foundation language models. arXiv preprint arxiv:2302. 13971, 2023.
Trinh, T. H. and Le, Q. V. A simple method for commonsense reasoning. arXiv preprint arXiv: 1eXivv/806.nn 02847, 2018.
van den Oord, A., Dieleman, S., Zen, H.. Simonyan, K., Vinyals, O., Graves, A., Kalchbrenner, N., Senior, A. W., and Kavukcuoglu, K. Wavenet: A generative model for raw audio. CoRR, abs/ hss/1609.03499, 2016. htttp////aaxi org/ abs 1601.6600..0 03499
van den Oord, A., Li, Y., Babuschkin, I., Simonyan, K., Vinyals, O., Kavukcuoglu, K., van den Driessche, G., Lockhart, E., Cobo, L. C., Stimberg. F., Casagrande, N., Grewe, D., Noury, S., Dieleman, S., Elsen, E., Kalchbrenner, N., Zen, H., Graves, A., King, H., Walters, T., Belov, D., and Hassabis, D. Parallel wavenet: Fast fighhlfiiiityy speech synthesis. CoRR, abs/1711..04333, 2017. http:///:
org/abs..... org/abs/1711 10433
Wu, Y., Rabe, M. N., Hutchins, D., and Szegedy, C. Memorizing transformers. arXiv preprint arXiv:2203.088: 200.20993...1.... 2022.
Zhang, S., Roller, S. Goyal, N., Artetxe, M., Chen, M., Chen, S., Dewan, C., Diab, M., Li, X., Lin, V., Mihaylov, T., Ott, M., Shleifer, S., Shuster, K., Simig, D., Koura, S., Sridhar, A., Wang, T., Zettlemoyer, L., and Ai, M. OPT: Open Pre-trained Transformer Language Models. 2022a. doi: URL
10. 40.48850/anxiv.2255...0o
Zhang, S., Roller, S.. Goyal, N., Artetxe, M., Chen, M., Chen, S., Dewan, C., Diab. M., Li, X., Lin, X. V., et al. Opt: Open pre-trained transformer language models, arXiv preprint arXiv:2205.01063 2022b.
12

---

A Supplementary Material
A.1 Training Details
To ensure stable training, we applied gradient clipping with a maximum norm of 1.0 and used the Adam optimizer with 31 0.9, 32 = 0.98 Kingma & Bal Ba] (2015). We used the built-in polynomial decay learning rate scheduler in MetaSeq with 500 warmup updates and the end learning rate set to 0. All models are trained with pre-norm and using ReLU activation. We apply dropout of 0.1 throughout, but we do not apply any dropout to embeddings. We also use weight decay of 0.1. To initialize the weights, we use variant based on Megatron-LM codebase, which involves using a normal distribution with mean of zero and a standard deviation of 0.006. We truncate this normal distribution within two standard deviations and observed substantial gain in both training stability and performance.
A.2 Motivation
Why the local model needed? Many of the efficiency advantages of the MEGABYTE design could be realized with the Global model alone. which would resemble decoder version of ViT (Dosovitskiy al. 2020). However, the joint distribution over the patch p(It+11 214 has an output space of size 256 so direct modeling is only tractable for very small patches. We could instead factor the joint distribution into conditionally independent distributions p(
poo.o...). ), but this would greatly limit the model's 's expressive power. For example, it would be unable to express a patch distribution such as 50% cat and 50% dog, and would instead have to assign probability mass to strings such cag and dot. Instead, our autoregressive Local model conditions on previous characters within the patch, allowing it to only assign probability to the desired strings.
Increasing Parameters for Fixed Compute Transformer models have shown consistent improve- ments with parameter counts (Kaplan al., 2220).. However, the size of models limited by their increasing computational cost. MEGAB YTE allows larger models for the same cost, both by mak- ing self attention sub-quadratic, and by using large feedforward layers across patches rather than individual tokens.
Re-use of Established Components MEGAB YTE consists of two transformer models interleaved with shifting, reshaping and a linear projection. This re-use increases the likelihood that the architec- ture will inherit the desirable scaling properties of transformers.
A.3 Model Details
As discussed in Section 4 we conduct experiments using a fixed compute and data budget across all models to foeus our comparisons solely the model architecture rather than training resources. To achieve this, we adjust model hyperparameters within each architecture so that the time taken for a single update is matched and then train all models for the same number of updates. We list all of model details in Table [nn and Table
Model
#L
dmodee
#H
dhead
SI
125M
12
768
12
64
S2
350M
24
1024
16
64
S3
760M
24
1536
16
96
S4
1.3B
24
2048
32
64
S5
2.7B
32
2560
32
80
S6
6.7B
32
4096
32
128
Table 12: Common Model architecture details by size. For each model size, we show the number layers
(HI.), the embedding size (dmodel), the number attention heads (#H), the dimension each attention head (docul).
13

---

Model
(Global) Size
Local Size
BS
LR
Context Length (in bytes)
arXiv
Transformer
320M (D=1024, L=22)
N/A
72
2.00E-04
1,024
Perceiver AR
248M (D= 1024, L=17)
N/A
72
2,00E-04
8,192
(1024 latents)
MEGABYTE
758M (D=2048, L=14)
262M (D=1024, L=18)
48
2.00E-04
8.192
(patch 8)
w/o Local model
2.3B (D=2560, L=20)
N/A
48
1.50F-04
8.192
(patch size 4)
w/o global model
N/A
350M (D=1024, 2
192
2.00E-04
8,192
(patch size 8)
cross patsh-pucch Local model
921M (D=2048, L=17)
350M (D=1024, L=24)
48
2,00E-04
8,192
(patch size 8)
w/ CNN encoder
704M (D=2048, L=13)
262M (D=1024, L=18)
48
2.00E-04
8,192 (putch size 8)
Image task 64 (Table
MEGABYTE
2.7B (D=25600, 1.=22)
350M (D=1024, l.=24)
2.00F-04
12,288 (patch size 12)
Image task (Table
Transformer
760M (D=1536, L=24)
N/A
512
3.00E-04
2,048
Perceiver
227M (D=1024, L=16)
N/A
3.00E-04
12,288 (1024 latents)
MEGABYTE
1.3 (D=2048, L=24)
1.3B (D=2048, L=24)
256
3.00E-04
12,288 (patch size 12)
Image task 256
Transformer
(D=768, L=6)
N/A
1536
2.00E-04
1,024
Perceiver AR
62M (D=768,
N/A
256
2.00E-04
8,192 (768 latents)
MEGABYTH
125M (D=768, L==22
125M (D=768, L=12)
16
2.00E-04
196,608
(patch size 192)
local model
2.7B (D=4096, L=32)
N/A
16
2.00E-04
196.608
(patch size
w/o global model
125M (D=768, L=12)
125M (D=768, L=12)
16
2.00E-04
196.608
(patch size 192)
cross-puthh Local model
250M
156M (D=768, 1=15)
2.00F-044 16
196.608
(patch size 192)
w/ CNN encoder
125M (D=768, L=12)
125M (D=768, L=12)
2.00E-04 16
196,608
(patch size 192)
Image task 640
Transforner
(D=768,
N/A
4800
3.00E-04
1,024
Perceiver AR MEGABYTE
62M (D=768, L=6)
N/A
2048
3.00E-04
4,09 (1024 latents)
125M (D=768, L=12)
83M (D=768, L=8)
32
3.00E-04
1,228,800 (192 patch size)
audio
Transformer
135M (D=768, I.=13)
N/A
2048
2.00F-04
1024
Perceiver AR
62M (D=768, L=6)
N/A
384
2.00 2.00E-04
8,192 (1024 latents)
MEGABYTE
350M (DD10024] L=24)
125M (D=768, L=12)
256
2,00E-04
524.288 (32 patch size)
w/o local model
2.7B (D=4096, L=32)
125M (D=768, L=12)
256
2.00E-04
524,288 (32 patch sizc)
global model
350M 1024, I=24)
125M (D=768, T=12)
2.00F-044
524,288 (32 patch size)
wlo pross-pates Locul model
350M (D= 1024, L=24)
146M (D=768, L=14)
256
2.00E-04
524,288 (32 patch size)
w/ CNN encoder
350M (D=1024, I==4)
125M (D=768, 1=12)
2.00F-04
524,288 (32 patch size)
Table Model architecture details. report the model size, the embedding size (D), number layaers(L),
total batch size (BS), learning rate(LR), context length. When we vary the number model layers from
standard amount for the given size (Table[2). we note this accordingly. For PerceiverAR models, we note the
number of latents used, and for MEGABYTH models note the patch sizes.
B Pseudocode
Listing 1: Pseudocode of Megabyte model
class MegaByteDecoder:
def __init__ self, global_arge local_args, patch_size,
):
self pad = self patch_size size = patch_size
self gll.amlobalmdel TransformerDecoder (local_args)
(gg.ooreeeeeoooeeeeglobo.... args)
self. lof.looclmodel
def forward self, bytes,
):
bytes_global, bytes_local self prepare input (bytes)

---

global_bytes_emteddee = self globalmodel embed (bbed global_in rearrange( global_bytes embedded, (t p) -> b (p e)",
p=self. sizch
global_output aelf globalmodel (glooaal
global_ wttpoouuttt__seappeee = rearrange
"b (p e) (b t) p e*, p-self patch_
local_bytes, embedded self localmodel. embed lbytes__locall local in local_bytes. wtw.byyyeeeeedddeeeeeeee embedded global. output_reshapee
lotal_output self localmodel (local_in)
batch_size = bytes-global. shapel [0]
x rearrange (local "bb t) l -> b (t 1) v", b" batch_size)
return
def prepare_inpule (self, bytes):
padding-global bytes. new new (bytes shape [0], self patch_size). (self pad)
bytes.global torch. cat wwrrc..aattppadiiiiiioteaaaaaaaa (ppadding_global, bytes[:, : self patch_sizel), -1)
bytes_ = rearrange (bytes, "b (t p) -> (b t) p", p=self.
patch_size)
padding_local bytes_input. new neytes shape [0], 1) fill_
(self. pad)
bytes_local = torch. cat (paddingg_local, bytes_input [;, :-1]), -1)
return bytes-global, bytes_local
C PerceiverAR Implementation
To reproduce PerceiverAR compute-controlled setting we extended the standard transformer implementation in metaseq with an additonal cross attention layer to compute the latents and match the architecture of PerceiverAR. We trained the model by sampling random spans from each text, matching the procedure used in the PerceiverAR codebase. To be consistent with the original work, we use sliding window evaluation with a stride rumm_ latmm_attenss? unless otherwise noted. several cases used the standard metaseq implementation opposed to specific techniques reported in the original paper: 1) we used standard attention dropout instcad of cross-attentics dropout 2) We did not implement chunked attention. We verified our implementation by reproducing the "Standard Ordering" experiments in Table of the Perceiver AR paper. After carefully matching context size, number of latents, the amount of data and training steps used and learning rate, achieved 3.53 bpb vs 3.54 reported in the original paper.
D More results
D.I Patch scan Implementation
Images have a natural structure, containing a grid of n x n pixels each composed of bytes (corresponding to color channels). We explore two ways of converting images to sequences for modeling (see Figure 4.. Firstly, raster sean where the pixels are linearized into bytes and concatenated row-by-row. Secondly, patch scan where create patches of shape p x 3 bytes
15

---

Figure 4: Two ways to model 2D data sequentially. Left, raster scan, by taking bytes row by row and left to right; right, patch scan, where first split image into patches, and do raster scan across patches and within patch. (T=36,
where p V P. 3. and then use raster scan both within and between patches. Unless otherwise specified, MEGABYTE models patch scan for image data.
D.2 Patch scan Raster scan
The patch sean method inspired by recent works in Vision Transformers (Dosovitskiy et al. 2020). and it is more effective than raster scan for modeling image sequencing. We found it improves both MEGABYTE and Perceiver AR.
(Global) Size
Local Size
context
bpb
MEGABYTE (patch scan)
62M (D=768, L=6)
N/A N/A
8,192 (768 latents)
3.158
MEGABYTE (raster scan)
62M (D=766, L=6)
8,192 (768 latents)
3,428
Perceiver AR (patch scan)
125M (D=768, L=12)
125M (D=768, L=12)
196,608 (patch size 192)
3.373
Perceiver AR (raster scan)
125M (D=768, L=12)
125M (D=768, 1.=12)
196,608 (patch size 192)
3.552
Table 14: ImageNet256 performance with patch scan vs raster scan for MEGABYTE and Perceiver AR.
D.3
Longer sequence modeling
For our pg19 scaling experiment, we also use longer context length for MEGABYTE. The results are shown in Table [5] With longer sequence. didn't 't observer further improvement, consistent with findings in Hawthorne et al. (2022). We think we will benefit more from longer sequence when we futher scale up the model size and data.
context
bpb
MEGABYTH YTE MEGABYTE
8,192 (patch size 8)
0.8751
16.384 (patch size 8)
0.8787
Table 15: Longer sequence for PGT9 dataset. For both experiments, we set global model 1,3b, local model as 350m, and MEGABYTE patch size as 8.
16


Reviews:
[{"review_id": "tdwrB4zOjN", "reviewer": "Reviewer_tnBu", "summary": "This paper proposes a new architecture of sequential modeling called MEGABYTE. MEGABYTE splits the long data sequence into patches and encode the patches using the Global model. The output of Global model is forwarded into the Local model, which facilitates the within-patch encoding. The output of the Local model is used to make next position generation. Compared with typical sequence modeling architectures, MEGABYTE has the advantages of no tokenization, lower complexity of attention, much larger feedforward layers for the same computation and faster generation speed via higher parallelisms. The experimental results over various benchmarks shows the effectiveness of this model design. Sufficient analysis and ablations are also provided.", "questions": "Just an extra question, is there any experimental results with the use of FLASH-attention and other SOTA speed and memory optimization libraries, given the fact that they are prevalently used in sequential models? Will the experimental conclusions still holds the same?", "limitations": "This work proposed a fundamental model architecture for efficient byte-level sequence modeling. This research topic is crucial for the development of future large language models. From my perspective, I would say there is not any so-called negative societal impact in this work.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. This paper focuses on a crucial problem in current sequential modeling tasks, which is making the encoding of extreme long sequences more efficient.\n2. The architecture is easy to understand and reasonable. \n3. The experiments are conducted on prevalent benchmarks related to long sequence modeling. And the SOTA models are compared on these benchmarks.\n4. Several tricks are proposed to improve the performance of MEGABYTE, including strided inference, cross-patch attention and convolutional embedding. The contribution of these tricks are also analyzed in detail.\n5. The models are implemented using open-sourced framework, which make it more reproducible.", "weaknesses": "Generally speaking, I think this paper is complete. I would say if more case study and analysis can be provided (especially on the language modeling task), it will be very good for a byte-level sequential model.\n\nA typo: Line 220: datasest → dataset", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer tnBu,\n\nWe greatly appreciate your positive and thoughtful review of our paper. We're glad you acknowledged our contributions and the effort we made in ensuring reproducibility. We would like to address your comments and questions:\n\nTypo Correction:\nWe appreciate you pointing out the typo. It will be corrected in the final version of the paper.\n\nMore Case Studies and Analysis:\nWe'd be happy to add further case studies, and would welcome any suggestions here.\n\nExperimental Results with FLASH-Attention and Other Libraries:\nYour question about the application of FLASH-attention and other state-of-the-art speed and memory optimization libraries is an important one. Flash-attention, particularly, is an exact attention algorithm that uses tiling to reduce the number of memory reads/writes between GPU high bandwidth memory (HBM) and GPU on-chip SRAM. Adding flash-attention, it should (theoretically) improve megabyte and also maintain its advantage compared with naive transformers. However, many SOTA speed and memory optimization libraries (including Flash-attention) are not implemented or tested for long sequences or more attention heads, requiring writing new cuda-kernels. We will add  FLASH-attention and other state-of-the-art speed and memory optimization libraries in the future work.\n\nIn conclusion, we thank you for your encouraging review and your constructive suggestions. We believe your feedback will help improve the clarity and impact of our paper."}, {"review_id": "qKFjkTRTSz", "reviewer": "Reviewer_bsD9", "summary": "This paper proposes Megabyte, a Transformer architecture that combines global and local attention to scale sub-quadratically in sequence length. The authors evaluate Megabyte on byte-level language modeling, image modeling, and audio modeling.", "questions": "1. Can you conduct a perplexity-based analysis of whether Megabyte uses the full context of its models?\n2. Can you compare against state-of-the-art tokenizer-based language models?\n3. Does Megabyte scale?", "limitations": "Brief mentions of scaling limitations but no concrete experiments", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "There is an extensive empirical validation, and Megabyte seems to perform well in the evaluated contexts. Megabyte has strong performance across different modalities, and scales well to long sequence lengths. The analysis of FLOP cost is nuanced and refreshing to see in an ML paper. Overall strong work.", "weaknesses": "There are a few ways that the paper could be improved.\n\nFirst, the presentation of the paper is a bit messy. There are links/references that go across page boundaries (e.g., bottom of page 5 in the submission). There are also some dead references (e.g. line 304). These problems should be cleaned up in the camera ready.\n\nThe analysis of whether the language models can use their full context seems a little naive. A better analysis would be to see if perplexity on long documents (e.g., books) is worse than perplexity on short documents, relative to a baseline.\n\nIt would be nice to see some comparison against state-of-the-art tokenizer-based language models, e.g. GPT-Neo [1], Pythia [2], Hyena [3], H3 [4]. These models are not byte-based, but they are standard benchmarks of Transformer quality for language modeling.\n\nLastly, it would be nice to see if this approach scales to larger models.\n\n[1] https://github.com/EleutherAI/gpt-neo\n[2] https://github.com/EleutherAI/pythia\n[3] https://arxiv.org/abs/2302.10866\n[4] https://arxiv.org/abs/2212.14052", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer bsD9,\nWe appreciate the time you have taken to review our paper and provide us with constructive feedback. We agree with your suggestions to improve the paper, and will address your concerns below:\n\nPresentation and references:\nWe apologize for the presentation issues you've mentioned, such as the cross-page references and dead links. We will rectify these issues in the final version of the paper to ensure a cleaner, more reader-friendly format.\n\nMegabyte uses the full context of its models:\nFigure 5 gives a perplexity-based analysis if MegaByte's ability to use its full context window on PG19. The average likelihood of a token increases monotonically throughout the 8192 token context window, which we argue shows that the model is able to use 8k previous tokens to improve its predictions.\n\nComparison with state-of-the-art tokenizer-based language models:\nWe focus on controlled comparisons between architectures, and it is difficult to make meaningful scientific comparisons with language models trained with very different sizes, datasets and compute budgets. For example, we might outperform some open source models on books data simply because of the kind of data we trained on. We do however show competitive results with SOTA tokenizer-based models trained on the PG19 corpus (better on dev, worse on test). \n\nScalability of Megabyte:\nSome experiments in the paper are already at quite large scale, for example the SOTA runs on image64 takes about a week on 128 A100s. These results suggest MeagByte scales well, but training at true foundation model scale is beyond the scope of this submission, and we are happy to study that in the future work. \n\nWe appreciate your constructive feedback and agree with your suggestions for improvement. We will incorporate these changes to improve the overall quality and impact of our paper.\nThank you for considering our paper for acceptance.\n"}, {"review_id": "I83Cd6NjLP", "reviewer": "Reviewer_RJHZ", "summary": "A new auto-regressive decoder-only Transformer variant for language modeling is presented which operates well on byte level. Similar to the Vision Transformer, the main idea is to operate on patches instead of single tokens (bytes). Those patches are composed of a fixed number of $P$ tokens. Then, a big global Transformer operates on those patches, i.e. on the spatial dimension $T / P$. After that, a smaller local Transformer operates on the spatial dimension $P$ inside a patch.\n\nActual values for $P$ are quite small, e.g. 8 for language modeling.\n\nThe model is tested on text for classic language modeling, but also on image data and audio data, where PPL on byte-level is measured in all cases. The performance on language modeling compared to other BPE-level models is worse. When comparing to other models on byte-level, it is always better or at least as good.", "questions": "Really sub-quadratic? How? From the figure 1 and 2 it just looks like reduced by constant factor P or thus P^2?\n\n\"MegaByte decomposes long sequences into two shorter sequences, and optimal patch sizes reduces the self-attention cost to $O(N^{\\frac{4}{3}})$\" - I don't understand this. Why two shorter sequences? Where do I see that in the model? What is meant by optimal patch size? $P$ is the patch size? As I understand it, $P$ is a fixed hyper parameter, which you cannot change later on, as it is the dimension for the input.\n\n\"By setting $P = T^{\\frac{1}{3}}$ - this does not make sense. $T$ is a variable length, depending on the input. $P$ is a fixed hyperparameter, which you can set once and then not change anymore. Or if you want to say, you also never change $T$ in practice, then the whole cost reduces to $O(1)$, but it's not really meaningful to think of $T$ as a fixed size.\n\n\n\nLine 136: \"the Global model has a sequence of length $\\frac{P}{T}$ - I assume it should be $\\frac{T}{P}$.\nLine 136: \"Local model uses $\\frac{P}{T}$ sequences\" - I assume it should be $\\frac{T}{P}$ as well?\n\n\"Extensive experiments show that MEGABYTE allows byte-level models to perform competitively with subword models on long context language modeling\" - but not on standard language modeling tasks?\n\n\n$E^{\\textrm{global-pad}} \\in \\mathbb{R}^{P \\times D_G}$ should probably be $E^{\\textrm{global-pad}} \\in \\mathbb{R}^{P \\cdot D_G}$ instead?\n\n\"Section ?? proposes strided inference as a solution\" - cross reference broken.\n\nFrom the NeurIPS template: \"The table number and title always appear before the table\". However, this is wrong in the paper, where the table caption is incorrectly below the table.\n\nFigure 4, Figure 7: I think that are tables, not figures?\n\nTable 1 caption should describe, what are those numbers for the models? PPL?\n\nIn Table 1, Stories dataset, for PerceiverAR, the number looks inconsistent to all other numbers in that it only has 2 digits after the decimal point instead of 3. Is this on purpose?\n\nImage modeling: It is not stated, but the model operates on the raw bytes, and you have 4 bytes per pixel? This should be explained.\n\nThe proposed model can be used to also operate on BPE level instead of byte level. While this is against the motivation of the work, I think this is still an interesting experiment. And also an important experiment. Because I would expect that this still improves over the byte-level variant. And this implies that BPE tokens are still overall better, and it is probably better to use BPEs also for this model, just like it is better to use BPEs for the other models.", "limitations": "-", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Novel model which performs well on byte-level\n- Many experiments, including ablations.\n", "weaknesses": "- The argumentation on sub-quadratic computation runtime for self-attention is flawed and not true. See details below.\n- Proposed model can also be used on BPE-level. How would this perform? Maybe even with this model, BPE would be prefered? This experiment is missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer RJHZ,\n\nThank you for your thoughtful review of our submission and for recognizing the novel aspects of our work. We appreciate your feedback and are eager to clarify the points you have raised:\n\nSub-quadratic computation runtime argument:\nThankyou for raising this issue, which is a bit subtle, and needs to be better described in the camera ready. There are really two places where T can be chosen for a Transformer model –- before training (which determines the maximum training sequence length, the number of positional encodings, and MegaByte's patch size), and during inference. Our analysis is about the former, whereas you assume the latter. We argue the former is more meaningful, because it is well established that during inference, most transformers generalize badly to sequences longer than they were trained on --- meaning that the training sequence length is usually an upper bound on the inference sequence length, so we cannot simply apply a pre-trained model to arbitrarily long sequences. However, the only limits on scaling to a large T during training are computational, so asymptotic analysis is more relevant here. \n\nIn our experiments, we do scale the patch sizes for problems where we need to model longer sequences (although we do not use the theoretical optimal choice). This scalability is what allows us to model longer sequences than are possible with vanilla transformers. \n\n\nUse of model on BPE-level:\nYour suggestion to experiment with our model on the BPE-level is indeed an interesting one, and we agree it could provide additional insights. Our byte-level experiments are grounded on our initial observations that most byte predictions are relatively easy (hence, can be handled by a small local model) due to the locality within a patch. We think it needs some extensive studies to apply it to BPE tokens and beyond the scope of this work. However, we are extremely interested in how our model works on BPE-level and such an experiment could potentially further demonstrate the versatility of our proposed model. We will study this in our future work.\n\nVarious formatting issues:\nWe'll fix the reference and table format in the revised version. Thanks for your feedback, this makes the paper  cleaner to readers. For image modeling, the model does operate on the raw bytes from three different channels, so we have 3 bytes for each pixel. We will add a clear description in the revised paper.\n\nWe greatly appreciate your constructive feedback, which will significantly improve the quality of our paper. We look forward to incorporating your suggestions in our revised version.\n"}, {"review_id": "7C2HvIo5Bo", "reviewer": "Reviewer_W4cB", "summary": "The authors propose MegaByte, a decoder style model consisting of 3 parts: patching of bytes, processing of patches (with autoregressive model), and converting patches back to bytes (with autoregressive model). Their model allows for sub-quadratic attention, more expressive models for the same flop count, faster decoding, and no need for tokenization. They show that it outperforms Transformer and Perceiver AR on byte-level modeling of language, images, and audio. There is also some indication that future language models may be able to successfully avoid tokenization entirely by using this model type.", "questions": "Please see weaknesses.", "limitations": "There is currently no substantive discussion of limitations, and it could be a helpful addition but probably not necessary.", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 4, "strengths": "**Originality**: The proposed model architecture is novel. Comparison to Perceiver AR seems reasonable and shows understanding of related work in the area.\n\n**Quality**: Experiments do a good job of demonstrating the quality of the model.\n\n**Clarity**: For the most part the paper is well-written and easy to follow.\n\n**Significance**: This paper brings forward more evidence that tokenization could be avoided entirely in language modeling. It explores a well-motivated and novel architecture. It opens up some interesting possibilities for future work.", "weaknesses": "Main weakness: While the paper does a laudable job of covering a lot of ground, this comes at a cost.\n1. First, the paper is unclear about when the three \"Extensions\" proposed in Section 2.3 are used in the results tables. It would be great to have something like a table in the appendix that just tells for each MegaByte result whether each extension was used. That would help readers get a sense (beyond Figure 4) of how much heavy lifting the architecture is doing vs the extensions.\n2. The paper focuses on high-level ideas (as it should) but it leaves some low-level details unclear. Here are a couple examples:\n    * Does the local model use position embeddings (when not using cross-patch attention)?\n    * What audio modeling dataset was used?\n    * When the GPT-3 architecture is brought up, is that including use of locally banded sparse attention patterns?\n3. In general, the results in the paper are not reproducible.\n\nWith the above being said, I do want to point out that the authors have clearly made efforts along these lines as the appendix has substantial detail.\n\nA quick fix to all of my above concerns would be to (1) release code associated with the paper, and (2) to add more detail regarding when \"Extensions\" were used in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer W4cB,\n\nWe sincerely appreciate your thoughtful review and your kind words about the novelty and potential significance of our work. \n\n\"Extensions\":\nWe report models with simple patch embedder, we use cross-attention for image and audio, but not for text. We used strided inference only when comparing with prior published work (Tables 2 and 3). We will add all those details in our revised version. This would indeed make it easier for readers to follow, thanks!\n\nMore details:\nWe tried out bets to add \nFor the local model, when not using cross-patch attention, we do use position embeddings; The GPT-3 architecture mentioned in the paper does not include the use of locally banded sparse attention patterns. We will add these details to the revised version. \n\nReproducibility and code release:\nWe plan to release the code associated with the paper and will make that clear in the revised paper. \n\nWe appreciate your constructive feedback and agree with your suggestions for improvement. We will incorporate these changes in our revised paper to improve its clarity, detail, and reproducibility.\n\nThank you for your positive evaluation and for considering our paper for acceptance.\n"}]

Author rebuttal:

Meta-review: The paper proposes an improved transformer architecture that by having local transformer to decoder byte level token more efficiently. The reviewers are generally in favor of the acceptance, acknowledging the novelty in the paper, and good experimental results on byte-level modeling of text, images and audio. Particularly, the work shows a good promise for language modeling without needing tokenization. However, there are some limitations and doubts of the proposed method. Such as the byte-level performance is still lag behind compared to BPE-based models and it is unclear if the proposed method helps when BPE is used. There are also some concerns around details and clarity in the paper, along with reproducibility concerns. Overall the reviewers assessed the submission positively and recommended acceptance after the authors addressed the feedback.
Decision: Accept (poster)