Not All Memories are Created Equal: Learning to Expire
Authors: Sainbayar Sukhbaatar
Da JU
Spencer Poff
Stephen Roller
Arthur Szlam
Jason E Weston
Angela Fan
Venue:  (2021)
Keywords: expire
long attention
memory
transformers

Abstract: Attention mechanisms have shown promising results in sequence modeling tasks that require long-term memory. Recent work has investigated mechanisms to reduce the computational cost of preserving and storing the memories. However, not all content in the past is equally important to remember. We propose Expire-Span, a method that learns to retain the most important information and 
expire the irrelevant information. This enables Transformers to scale to attend to tens of thousands of previous timesteps efficiently, as not all hidden states from previous timesteps are preserved. We demonstrate that Expire-Span can help models identify and retain critical information and show it can achieve state of the art results on long-context language modeling, reinforcement learning, and algorithmic tasks. Finally, we show that Expire-Span can scale to memories that are tens of thousands in size, which is helpful on incredibly long context tasks such as character-level PG-19 and a frame-by-frame moving objects task.


Under review as a conference paper at ICLR 2021
NOT ALL MEMORIES ARE CREATED EQUAL: LEARNING TO EXPIRE
Anonymous authors Paper under double-blind review
ABSTRACT
Attention mechanisms have shown promising results in sequence modeling tasks that require long-term memory. Recent work has investigated mechanisms to re- duce the computational cost of preserving and storing the memories (Rae al.) 2020 However, not all content in the past is equally important to remember. We propose Expire-Span, method that learns to retain the most important infor- mation and expire the irrelevant information. This enables Transformers to scale to attend to tens of thousands of previous timesteps efficiently, as not all hidden states from previous timesteps are preserved. We demonstrate that Expire-Span can help models identify and retain critical information and show it can achieve state of the art results long-context language modeling, reinforcement learning, and algorithmic tasks. Finally, we show that Expire-Span can scale to memories that tens of thousands in size, which is helpful on incredibly long context tasks such as character-level PG-19 and a frame-by-fiee moving objects task.
INTRODUCTION
Transformer architectures /aasaani et al. 2017) have demonstrated strong performance across a va- riety of tasks (Devlin et al. 2019 Roller el al. 22200 Brown et al. 2020)) including those that require
learning long term relationships (Zhang al. 2018 Fan al.) 2019a] Izacard & Grave 2020). Re-
cent work has focused on scaling attention mechanisms efficiently to longer memory sizes, enabling large improvements on long context tasks (Dai al., 2019) [Sukhbaatar al. 2019a). However, critical component of human memory is not just the ability to remember, but also forgetting irrele- vant information to focus on the salient, relevant bits. Most studies of long-term memory humans indicate that not everything is remembered (Murre & Dros 2015) instead, only vivid, remarkable memorics are retained from the far past [Wxteed 2004).
Standard Transformer architectures lack the ability to search over extremely large memories, as the self-attention mechanism is computationally intensive and the storage cost of preserving the large memory grows quickly. Recent work (Child al.] [019] |ae et al.) (220)) has proposed learning how to extend to greater context through sparse mechanisms or through compression, to more compactly represent the past. However, there exists fundamental problem with large memories beyond strict computational concerns: as the amount of information stored increases, deciding which information relevant becomes more challenging. Other work (Lample et al.) 2019) approaches this by consid- ering how to efficiently search large memories. We will focus on learning what to forget, and thereby reducing the computational burden of the model easing the challenges of the search problem.
We propose EXPIRE- SPAN, straightforward extension to attention mechanisms, that learns when to expire unneeded memories. By expiring memories that are no longer useful, EXPIRE-SPAN enables scaling to memories tens of thousands of timesteps long. This learnable mechanism allows the model to adjust the span size as needed, selecting which information critical to retain and forgetting the rest. More concretely, expiration value for each hidden state that determines how long a memory should be retained and accessible to the model. After the EXPIRE-SPAN runs out, the memory will be forgotten, but in a gradually differentiable way to retain end-to-end training with backpropagation. This process is done independently for each layer, allowing different layers to specialize in different time-scales.
augment the self-attention with simple predictor that outputs an
We demonstrate that EXPIRE- SPAN can distinguish between critical and irrelevant information on several illustrative tasks in natural language processing and reinforcement learning. We then show

---

Under review as a conference paper at ICLR 2021
Expire-span
0,
E5
output
63
Attention
C2
query
A1
h2 by ha
hs
hr
time
Figure 1: EXPIRE-SPAN, For every memory his compute EXPIRE-SPAN 6, that determines how long it should stay in memory. Here, memories h2, h& are already expired at time t, so the query de can only access {h1, hg.h1)) h43 } in self-attention.
on long-context language modeling benchmarks and frame-by-frame colliding objects task that EXPIRE-SSN -SANN- can scale to memories the tens thousands - by expiring irrelevant information, capacity is freed to have even larger memory. Finally, analyze the information retained and expired by EXPIRE-SPAN models, to understand the importance of long context memory.
RELATED WORK
Memory is crucial for many tasks and has been studied in recurrent networks (Elman 1990 Hochre- iter & Schmidhuber 1997 Mikolov al. 2010) for long time. The development of memory augmented networks Graves et al. 2014] Sukhbaatar et al. 2015b) made it possible to store large quantities of information and selectively access them using attention (Bahdanau al.) 2015). The Transformer Vaswaan et al. 2017) took full advantage of this approach. Processing long sequences with Transformers an active area with applications in language understanding (Brown et al. 2020),
reinforcement learning (Parisotto et al. (219)) video processing (Wu et al., (201)), and protein fold- ing (Rives et al. 2019). However, extending the memory span is computationally expensive due to the quadratic time and space complexity of self-attention.
Various work has focused on reducing this complexity and increasing memory capacity. Dynamic attention spans, such Adaptive-Span (Sukhbaatar al. 2019a) and Adaptively Sparse Trans- former (Correia et al. 2019), focus on learning which heads can have shorter spans attention, but only extend to spans of few thousand. Other work sparsifies attention by computing fewer to- kens (Fan et al., (019c)), often by using fixed attention masks (Child et al. (201)) or sliding windows and dilation (Beltagy al. 2020). The BP Transformer (Ye et al. (019) structures tokens binary tree, so some tokens have coarse attention. These works focus on learning what to attend to, but searching larger and larger memories is very difficult. In contrast,
focus learning expire what is irrelevant. Compressive Transformer (Rac et al. 2020) reduces the number of memories by replacing every few memories with single compressed one. A disadvantage of this is that all memories have the same compression ratio, so relevant memories are equally compressed.
Another line of work investigates linear-time attention mechanisms. Wu al. (2018) replace self- attention with convolutions that run in linear time, but the scalability to long context tasks remains limited. [Wang et 2020)) propose linear time attention by decomposing attention into multiple smaller attentions, that recombine to form low-rank factorization of the original attention. Those methods, however, focus on making attention more efficient without actually reducing the number of memories. Further, our goal is to reduce the number of memories that feed to self-altention by learning to expire, EXPIRE-SPAN can be easily combined with these efficiency improvements. For review of further recent Transformer variants, see Tay et al. (2020).
BACKGROUND
Transformer architectures have been widely used as decoder-only ruto-regressive models for quential tasks. Each Transformer decoder is made of stack identical layers, composed a multi-head self-attention sublayer followed by feedforward sublayer. The output of each timestep
2

---

Under review as a conference paper at ICLR 2021
is the hidden state hy layer which is then projected to key kt value v, and query g vectors:
df W. k = Wh = W.
where W represents the weight. Going forward, we focus on a single layer and omit the layer index 7 for brevity. Information from previous timesteps is accessed through attention create output o:
Ct Softmax;ec. (q. k.). or -
Σ 22 SEC,
The set C indicates which memories can be accessed at time t, which is the focus this work. The space and time complexity of self-attention is linearly correlated to |Cr|, making an important metric of efficiency. For the rest of the paper, we will refer to |Cal as the memory size.
Including all previous timesteps in self- elf-attention by setting C₁ = {1..... t- 1) results in a guadratic sequence of length T. Fixed-spans (Dai et al.
complexity ( to compute the full attention 2019) take a more scalable approach such that C, = {t - L...., , }} so the attention restricted previous L steps. The total complexity in this case O(TL), where is the attention span.
Adaptive-Span (Sukhbaatar et al. 2019ah further improves upon this by learning an optimal span L per attention head from data, which results in small L values for many heads. Compression ap- proaches (Rae et al. 2020) reduce memory size by compressing multiple timesteps into a single memory, with complexity O(TL/c), where is the compression rate. However, in all these ap- proaches, all memories are treated equally without regards to their importance to the task. In this work, we focus on distinguishing between relevant and irrelevant memories by learning to expire unneeded information by expiring, the remaining attention relevant information can scale beyond existing long context memory approaches.
EXPIRE-SPAN
We detail the EXPIRE-SPAN mechanism and how to integrate it into Transformer architectures to focus attention on relevant information and expire the rest. We describe how to scale EXPIRE-SPAN and practically train with drastically longer memory spans.
4.1 METHOD
EXPIRE-SPAN, depicted in Figure allows models to selectively forget memories that are no longer relevant. We deseribe it in the context of a single Transformer layer and omit the layer index / for brevity. Our goal is to reduce the size of Ct defined in Section 3 for more efficiency without performance degradation. For each memory h4, we will compute a scalar EXPIRE-SPAN e; [0, L]:
e La(w" h4 b).
Here w, b represent trainable parameters, the sigmoid function, and is the maximum span. This expire-span e, determines how long h4 should be kept and included in Cg.
At time the remaining span of h; rr, = e; (t-i). i). When rt., becomes negative, it indicates the memory h; is expired and can be removed from C. This can be implemented by updating attention weights with binary masking function me,s:
-'' where my {o
if > 0
d', E, myjar."
=
otherwise,
However, with such discrete masking, the expire-span e, will not receive any gradient for training. Therefore, we use a masking function that smoothly transitions from to as shown in Figure
My, = max(0, min(1, + rt,s/
where R is hyper-paramede that determines the length of ramp that is bounded between 0 to 1. This function has non-zero gradient for values which is necessary for expiring memories. Thus C, = {ä my 0}. Since me, is monotonically decreasing function of t, once memory expired, can be permanently deleted.
R, 0) train e;, but also can take a value of 0,
3

---

Under review as a conference paper at ICLR 2021
Our goal is to reduce average memory size, which is directly related with the average EXPIRE-SPE SPAN.
m(x))
+
1 Σ
Ial
cal
T Σ
1 1m
Σ
1
R+
Σ
imsss
T
i<t
1>1
-R
Σ +
R Σ 1>1
1est-i
R 1+ [es]
Σ T
Figure 2: Soft Mask Function
Thus, we add an auxiliary term to the loss function to penalize the LI-norm of EXPIRE-SPANY SPANS: Liotll = Luak a E, e//T,, where 0s hyperparameter. This loss term will decrease the span of memories that contribute less to the main task, resulting in a model with a small memory that focuses the most relevant information. Note that and b are the only new parameters, and negligible in size compared to the total number of parameters in standard neural models.
4.2 ADDING EXPIRE-SPAN TO TRANSFORMERS
We describe how EXPIRE-SPER SPAN can be utilized within Transformer self-attention layers decrease the memory size and focus the memory on the most salient, relevant information, expiring the rest. We also discuss practical training concerns, such efficiency and regularization.
Modifications to Multi-Heade Attention Self-attention consists of multiple heads that have differ- ent keys, values, and queries. However, they all share one underlying memory, memory cannot be removed if it is used by any of the heads. Thus, we compute an EXPIRE-SPAN at each layer that is shared amongst the heads.
Block Parallel We use the caching mechanism Dai et al. 2019). where a block of timesteps B = [t.... + 1] is processed in parallel for efficiency once block is computed, its hidden states (h....,, / are cached so that future blocks can attend to them. This means a memory only be deleted if it is not used by any of the queries in B. Concretely, h; will be deleted when ma, = 0 where t is the first token of B. However, this is not a concern for very long-term memories where L >>>>>> B.
Position Embedding Relative position embeddings (Shaw et al., 2018) make it possible to con- dition the ordering of inputs by modifying the attention to dz Softmax k; + 4: pt-i)- However, because this second term is computed for the whole block in parallel for efficiency, it can become expensive for large even when the average memory size |C&] is small. Our solution is to remove position embeddings from older memories i < t - (where b is the block size), which empirically does not affect performance. The computational complexity of the position embeddings is then (b), thus allowing us to increase the maximum span L.
Loss Computation The LI LI-norm loss for EXPIRE-SPAN must be computed for every memory hi- A simple way is to compute it on tokens within the current block B. This empirically results in poor performance possible explanation is that the time between positive and negative gradients on may become too distant. Negative gradients that increase only come from the main loss Lusk through the masking function My,5, which has non-zero gradients only when memory h; is about to expire with 0 < Me,i < for E B. For large L > B, h; may have been computed many blocks before and since then the model weights would have changed. In contrast, the positive gradients that decrease e, are computed on the current block i E B. To remove this discrepancy, we compute the auxiliary loss on e; at the same time as negative gradients when 0 < m4,a < for E B.
Regularization A potential challenge in exceptionally long memory is greater capacity to overfit. As EXPIRE-SPAN can scale to memories the tens of thousands, can overfit to learning specific span sizes the training set that do not generalize. As a form of regularization, randomly shorten the memory during training. For each batch, we sample ~ 2(00, L) and set a,, 0 for all t i > only during training. This way, the model cannot assume the memory will always contain specific information, as the memory is randomly shortened. This can be seen as a form of structured dropout (Fan al., 2019h) applied the memory size.
propose to
4

---

Under review as a conference paper at ICLR 2021
Receive Instruction
Memorize Color
Walk through Correct Door
Extremely Long Corridor
Long Distractor Text
Instruction
Figure 3: Corridor Task (left)- Agents must memorize the color of an object and walk through the door of the corresponding color at the end of long corridor. Instruction Task (right)- A model must recognize instructions, memorize them, and execute when at the correct location.
Trans-XL
Expire-span
Trans-XL
Expiresppan
1.0
1.0
Average Success
Averago Accurnty
0.8
0.8
0.5
0.4
40
80
100
500
1000
1500
2000
2500
Average Memory Span
Average Memory Span
Figure 4: Success on Corridor task as a function of the Memory Size (left) - We trained 10 baseline models with different memory sizes, and five EXPIRE- SPAN models with different random seeds. Corridors are randomly sampled with length between [3, 200). Performance on Instruction task as function of the Memory size (right) We trained baseline models with different memory sizes, and five EXPIRE-SPAN models with different random seeds.
Training with Small Initial Spans EXPIRE-SPAR scales to long attention spans as it quickly leams expire irrelevant content. However, at the beginning of training, the long span use large quantities of GPU memory. To circumvent this, we initialize the bias term with a negative value. This prevents large memory usage the beginning of training, after which the model quickly learns to expire and the memory usage is no longer problematic.
5 EXPERIMENTS AND RESULTS
We show that EXPIRE-SPAN can focus on salient information on various constructed tasks that necessitate expiration. Then, we highlight the scalability of EXPIRE-SPAN when operating on ex- tremely large memories on different tasks. Additional experiments and details are in the Appendix.
5.1 BASELINES
We compare our method against several baselines from Section 3 that takes different approaches to limit the memory size. Transformer-Xi (Dai et al. 2019) corresponds to the fixed-spans approach where simply the last memories are kept. Our Transformer-X0 XI. implementation also serves as a base model for all the other baselines to guarantee that the only difference among them how memo- ries are handled, The other baselines are Adaptive-Span (Sukhbaatar et al., (019a)) and Compressive Transformer (Rae al. 2020). For Compressive Transformer, we implemented the mean-pooling version, which is shown to give good performance despite its simplicity.
5.2 IMPORTANCE OF EXPIRATION: ILLUSTRATIVE TASKS
Walking down a Corridor To illustrate a case where proper expiration of unnecessary memories critical, we begin with RL gridworld task. In the Corridor task, depicted in Figure (left), the agent is placed at one end of a very long corridor, next to an object that either red or blue. The agent must walk down the corrddor and go to the door that corresponds to the color of the object that it saw at the beginning to receive +1 reward. The requirement on the memory is low: the agent should remember the object color so it can walk through the correct door.
5

---

Under review as a conference paper at ICLR 2021
Trans-XL
Expre-span
Wrong Door Choice
80
AA.
Average Relurm
40
0
20
40
60
80
100
200
Wrong Door Choice
Average Memory Span
Figure 5: Portal Task (left)- An agent must trial-and-error memorize the right sequence of doors. Performance as a function of Memory Size on Portal Task (right)- We train multiple models with different memory sizes and random seeds.
EXPIRE-SPAL models can take advantage of this fact and keep the memory size small regardless of the corridor length, which can vary between 3 and 200. This is confirmed in the results shown in Figure 4 (left) where the EXPIRE-SPAN models achieve high performance on this task with very small memories. Without the ability forget, the Transformer-Xe XL models require large memory for storing all navigation steps that grow with the corridor length.
Multi-Room Portal Task Next, we analyze the performance of EXPIRE-SPAS SPAN on a reinforcement learning memorization task. Agents in gridworld are tasked with navigating through multiple rooms separated by different doors, depicted in Figure (left). Each room has two exit doors with different colors- the start. However, which door works in which room is randomized for each episode. Thus, the only way visit more rooms by trial-and-error, where agents need remember the sequence of correct doors to successfully navigate to the end.
door portals the adjacent room, while the other portals the agent back to
We show results in Figure 5 (right). Transformer-XL. models need longer memory to perform better and visit more rooms as each room requires many navigation steps, this requires more memory. However, those navigation steps are irrelevant because the agent only needs to memorize which doors are visited. Since EXPIRE-SPAN models can discard irrelevant memories and focus its mem- ory on memorizing the exact sequence of doors, they achieve strong performance with much smaller memory compared to the Transformer-XL XL baseline.
Receiving and Executing Instructions To illustrate a more difficult task where a model must learn to recognize relevant memories and expire the rest, we use dialogue- story generation task from the LIGHT (Urbanek et al.] 2019) text world game environment. The model visits various locations and receives instructions the form can you tell the [butler] that the [town official) wants to see them?. When the model is in location where the butler is present, they must execute the instruction by generating You tell the butler "town official wants to see you!". Between receiving and executing, thousands of words of distractor text exist. The model must learn what is relevant to retain and expire the distractors. Note multiple instructions can be in queue for execution.
We experiment with dataset where the average distance between receiving and executing instruc- tions around 950 distractor sequences. Models are trained as language models, but evaluated only on their success in executing the instruction. Task details and model architecture provided in the Appendix. We illustrate in Figure 4 (right) and Table 4 that EXPIRF-SPAA is much more suc- cessful solving this task than Transformer-Xi Adaptive-Span, and Compressive Transformer as it can focus on the specific instruction lines. For Adaptive-Spaa and Compressive Transformer, we experiment with various memory sizes tune the maximum span.
5.3 SCALABILITY OF EXPIRE-SPAN
We analyze the scalability of EXPIRE-SPAN On copy task, we train models with spans up to 128K timesteps. Then, we show the utility of EXPIRE-SPA on two character-level language modeling tasks enwiki8 and PG-19, and colliding objects task that is processed frame by frame.
Extremely Long Copy To illustrate the scalability of EXPIRE-SPAN we construct a copy task where the model sees sequence of A very far in the past. The rest of the characters are B. The

---

Under review as a conference paper at ICLR 2021
1/22
Model
Copy Acc (%)
Tea Tai
Transformer-Xe
26.7
1/88
EXPIRE- SPAN 16K
29.6 .4
EXPIRE-SPAN 128K
52.1
1.00
(Ro
(164)
(208)
Table I: Copy Task. We report copy accuracy on the test set.
Figure 6: Performance on character-level PG-19. We re- port bit-per-byte on test.
Model
Params
Test
Trans-XL 24L Dai et al.
2019)
277M
0.99
Trans-XL
Adept-span
Expire-epan
Sparse Trans. C Child
2019
95M
0.99
1.12
Adapt-Span 24L Sukhbaatar
2019a
209M
0.98
Dev. Bit-per-bylt byle
All-Attention (Sukhbaatar of al.
1019h)
114M
0.98
1.08
Compressive Trans. (Rac ct al
2020)
277M
0.97
Routing Trans. (Roy al. 2020
0.99
Feedback Trans. (Tan
2020
77M
0.96
1.04
Trans-XI XL 12L (Dai al.
2019)
41M
1.06
1.02
Adapt-Span 12L Sukhbaatar al.
2019a
39M
1.02
200
400
600
800
1000
Our Trans-XI. 121. baseline
38M
1.06
Average Memory Span
EXPIRE SPAN 12L
38M
0.994
Figure 7: Performance as function of Memory Size on enwiki8.
Table 2: Enwiki8 Results. We report bit-per-byte (bpb) on and the number of parameters.
model must copy the correct quantity of A. We design the task such that long span (up to 128K) can be required, as the A tokens are very far into the past. In Table [ we show that only by scal- ing the attention span to 128K is it possible to achieve improved performance. We compare to Transformer-X X baseline with 2048 attention limit and EXPIRE- SPAN model with smaller span.
enwiki8 We test the enwiki8 character-level language modeling benchmark (Mahoney 2011
We set the maximum span L for EXPIRE-SPAN to 16K. We compare EXPIRE-SPAN to existing work in Table EXPIRE-SPAN outperforms similarly sized baselines by large margin, and matches the performances of much larger models. This indicates that models can learn to expire relevant infor- mation and encode long context effectively, even on competitive language modeling benchmarks.
Next, we compare the performance of EXPIRE-SPAN with Adaptive-Span and Transformer-Xi baselines when we vary the average span size (see Figure 7.. Models with EXPIRE-SPAN achieve stronger results mance than both baselines. Further, the performance of models with EXPIRE-SPAR does not vary widely even if the memory size is drastically reduced]
when comparing at any given memory size, EXPIRE-SPAN has better perfor-
Finally, we compare the performance of EXPIRE-SPAN with the Compressive Transformer base- line. We vary the memory size of Compressive Transformer and compress with rate 4. We find that EXPIRE-SPAN models achieve much better performance, as shown in Table with less GPU memory and faster training time per batch.
Character Level PG-19 We use the PG-19 (Rae et al. 2020) language modeling benchmark and convert it to model characters. We use all characters in the training set, creating vocabulary size of 3506 characters. We compare the performance of Transformer-Xe with an attention over the last 1K and 2K timesteps with an EXPIRE-SPAN model with maximum spans at 8K, 16K, and 32K. As shown in Figure 6 EXPIRE-SPAN models train stably with very long span, and EXPIRE-SPAN substantially better than the Transformer baseline. The performance improves with larger spans,
'The results in Figure 7 are not finetuned with smaller learning rate, thus have slightly worse performances
than Table 2

---

Under review as a conference paper at ICLR 2021
Model
Maximum Span
Test Error (%)
Trans-XI
lk
73.3
Compressive
8k
63.8
Adapt-Span
16k
59.8
Expire-Span
16k
S2.2
Expire-Span
32k
36.7
Red Green Coliison
Expire-Span
64k
26.7
Upowr Right Quadtram
Figure 8: Object Collision: task is to remember the location of specified colored collisions.
Table 3: Colliding Objects Results. We report eтror on the test set.
Model
Performance GPU Memory
Time/Batch
Compressive Transformer Sdaptive-Span EXPIRE-SPAN
71% Acc
9.8 GB
210 ms
Instruction Task
64% Acc
14.2 GB
240 ms
74% Acc
8,4 GB
90 ms
Compressive Transformer
63.8% Error
11.6 GB
327 ms
Collision Task
Adaptive-Span
59.8% Error
17.2 GB
365 ms
EXPIRE-SPAN
52.2% % Error
11.9 GB
130 ms
Compressive Transformer
1.015 bpb
21.3
805 ms
Enwiki8
Adaptive-Span EXPIRE-SPAR
1.036 bpb
20.3 GB
483 ms
1.034 bpb
14.6 GB
408 ms
Span
1.12 bpc
13.5 GB
515 ms
PG19
EXPIRE-SPAN
1.12 bpc
12.9 GB
585 ms
Table 4: Efficiency of EXPIRE-SPAN, We report peak GPU memory usage and per-batch training time, fixing the batch size. We evaluate the mean pooling version of the Compressive Transformer.
though extending to 32K does not increase performance beyond 16K. When comparing to Adaptive Span in Table Adaptive Span has the same performance but requires slightly more memory while running bit faster.
Colliding Objects Another setting where learning which long context may be important is in video understanding. Despite video data being memory intensive, salient events might be localized in space and time. We test our model on task where two objects move around and collide, and the goal is to reason about the location specified-color collisions. Objects have a color that can randomly change. We divide grid into four quadrants and the model is asked recall the quadrants of the last collision a specified-colo pair. Because the collisions are rare, and collisions of specific colors are rarer, the model must process large quantity of frames.
We display the task in Figure g and results in Table The task requires many frames, so long context is very beneficial steadily rises. We train the 64K with the random drop regularization method described in Section 4.2. When extending extremely long span, 64k in size, we find the strongest performance, which matches the size of the largest attention limit reported to date (Kitaev et al. 2019).
that the EXPIRE-SPAS maximal span increases, performance
As baseline, train Adaptive-Span model with maximum spans limited 16k. While this model perform similar to the 16k EXPIRE-SPAN model, it uses 44% more memory (17. (17.2gb com- pared to 11.9gb) and takes 2.8x longer to train on batch (365ms compared 130ms). A 32k Adaptive-Span model run out of memory in the same setting where we trained our 64k EXPIRE- SPAN model, which shows the efficiency of our approach.
We also included Compressive Transformer baseline with maximum span of 8.5k (512 normal memories and 2k memories compressed by 4x). This model performs worse than our model, and increasing its span does not help. It uses the same GPU memory as our 16k model, but runs 2.5x slower, despite having a smaller span.
5.4 EFFICIENCY OF EXPIRE-SPAN
We describe the efficiency of EXPIRE-SPAN compared to various baselines, including Adaptive- Span, Compressive Transformer, and Transformer-XI.. We quantify with two metrics: (1) Peak
8

---

Under review as a conference paper at ICLR 2021
18
1024
Jevertat inflesece in Eppat. Ta HlAttrettrr DE freat:] the city
3489 the wole ( 00ost]] wa5
L-16384
4
revertat inflesece in panveere. To Heleearder th Greet]l the JENerTat infleence IN Spengetat Seserstents ElAlexender the
3459 the wole ( ((dnnea cssst]] was
10
Exprre
Delaa
Dis
the whoe (Gddnea oosst] was
Figure 9: Expiration in EXPIRE-SPAN on enwiki8. In (a), one layer of the model has two focus areas, "Egypt" and "Alexander". In (b), we replace "Egypt" with "some- where" and the focus disappears. In (c), we insert "SpongeBob SquarePants" and the model attends to the full entity.
Figure 10: Prediction Accuracy Needs Memory. As the memory size is artificially decreased at in- ference to 1024, the prediction is less accurate (smaller is better).
GPU memory usage and (2) training time per batch (comparing fixed batch size). Results are shown in TableBann and indicate that across all tasks, EXPIRE-SPAN uses substantially less GPU memory and processes each batch more quickly than all baselines, while achieving better performance in most of the tasks. Transformer-XL. as baseline cannot adapt to the data at all, so it becomes slow and inefficient quite quickly. Adaptive-Span can adapt to the data and adjust its memory size, but this memory size is fixed after training and does not have the dynamic adjustment of Expire-Span (where memory depends on context). Finally, Compressive Transformer does compress the past memories, but it compresses them all the same amount. In contrast, EXPIRE- -PANN can forget irrelevant content, which both improves performance by focusing on salient information, but also reduces the load on the GPU and allows for faster processing per batch. Overall, across all tasks, find that EXPIRE- SPAN achieves strong performance with GPU memory savings and low time per batch.
ANALYSIS AND DISCUSSION
We analyze the information retained and expired by EXPIRE-SPAN models. See the appendix for more analysis and ablations on the importance of regularization.
Retaining Salient Information We analyze what retained by an EXPIRE-SPAN model on en- wiki8. In Figure (a). we show that the model retains information about named entities Egypt and Alexander the Great by attending to them (darker color). Next, we analyze how attention changes when we artificially edit the past text. In Figure 9 (b). we replace Egypt with somewhere, and this generic word is expired. In Figure ( we edit Egypr to Spongebob Square which is rare named entity, and the model attends strongly to this rather than expiring. addition named en- tities, EXPIRE-SPAN also focuses information about words, sentences or sections. These can vary between different layers, indicating that EXPIRE-SPAR models use the memory each layer differently. See the Appendix for details.
spaces, newlines, and section titles, all of which can retain
Importance of Long Term Memory Lastly, analyze which predictions benefit the most from memory capacity. We take an EXPIRE-SPAN model trained on enwiki8 and artificially limit the span size inference. We compare which predictions decreased in accuracy. In Figure [O] we limit the span to 1024 tokens, and see that models have a higher loss when predicting the named entity Guinea coast compared to the 16k span. Guinea coast was mentioned 3584 tokens earlier, which indicates that long attention is often necessary to predict words mentioned in far away context. In general, we found that rare tokens and structural information about documents, such as section headings or document titles, required longer attention span.
7 CONCLUSION
We present EXPIRE-SPAN, an operation that can added to any attention mechanism to enable models to learn what to forget. By expiring irrelevant information, models can scale attention to tens of thousands of past memories. We highlight the strong performance EXPIRE- SPAN in language modeling, reinforcement learning, object collision, and algorithmic tasks, and use it to attend to over tens of thousands of past memories. The scalability of SEPIRE-SPAY has strong potential for allowing models to be applied to more challenging, human-like tasks that would require expiration.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Alexei Baevski and Michael Auli. Adaptive input representations for neural language modeling. In ICLR, 2019.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In ICLR, 2015.
Shaojie Bai, J Zico Kolter, and Vladlen Koltun. Deep equilibrium models. Advances in Neural Information Processing Systems, pp. 988-699, 2019.
Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint wxXv:2004.055500 2020.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. arXiv preprint arXiv:2005. 2020.
Rewon Child, Scott Gray, Alec Radford, and lyya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv: /904. 10509, 2019.
Gonçalo M Correia, Vlad Niculae, and André FT Martins. Adaptively sparse transformers. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLPP), PD- 2174-21844 2019.
Zihang Dai, Zhilin Yang, Yiming Yang. William W Cohen, Jaime Carbonell, Quoc V Le, and Ruslan Salakhutdinov. Transformer-xl: Attentive language models beyond fixed-length context. arXiv preprint arXiv: 010019900000.. 2019.
Jacob Devlin, Ming- Ming-Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In (AACL-HLT(I), 2019.
J. Elman. Finding structure in time. Cogn. Sci., 14:179-211, 1990.
Angela Fan, Claire Gardent, Chloé Braud, and Antoine Bordes. Using local knowledge graph con- struction to scale seq2seq models to multi-document inputs. In Proceedings of the 2019 Con- ference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (FMNN.P-IJCNIP), pp. 4177-4187, 2019a.
Angela Fan, Edouard Grave, and Armand Joulin. Reducing transformer depth on demand with structured dropout. arXiv preprint 1rX.v:1999.11556 2019b.
Angela Fan, Mike Lewis, and Yann Dauphin. Strategies for structuring story generation. In Proceed- ings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 26502266000000 2660, 2019c.
Angela Fan, Thibaut Lavril, Edouard Grave, Armand Joulin, and Sainbayar Sukhbaatar. Accessing higher-level representations in sequential transformers with feedback memory. arXiv preprint arXiv:2002.09442. 2020.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256, 2010.
Edouard Grave, Armand Joulin, Moustapha Cissé, and Hervé Jégou. Efficient softmax approxima- tion for gpus. In ICML, 2017.
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. 14X1v:1410.5401, 2014.
arXiv preprint
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
10

---

Under review as a conference paper at ICLR 2021
Gautier Izacard and Edouard Grave. Leveraging passage retrieval with generative models for open domain question answering. arXiv preprint arXtv:2007.01282. 2020.
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In International Conference Learning Representations, 2019.
Guillaume Lample, Alexandre Sablayrolles, Marc' Aurelio Ranzato, Ludovic Denoyer, and Hervé Jégou. Large memory layers with product keys. In Advances in Neural Information Processing Systems, pp. 8548-8559, 2019.
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint arXiv:/608. 03988, 2016.
Matt Mahoney. Large text compression benchmark. URL: http://ww.. mallmahoney. net/text/text.
html, 2011.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. arXiv preprint arXiv: 16090.08007743 2016.
Tomáš Mikolov, Martin Karafíát, Lukáš Burget, Jan Černocký, and Sanjeev Khudanpur. Recurrent neural network based language model. Eleventh annual conference of the international speech communication association, 2010.
J. Murre and Joeri Dros. Replication and analysis of ebbinghaus' forgetting curve. PLoS ONE, 10, 2015.
Emilio Parisotto, H. Song, Jack W. Rac, Razvan Pascanu, Çaglar Gülçchre, Siddhant M. Jayakumar, Max Jaderberg, Raphael Lopez Kaufman, A. Clark, Seb Noury, M. Botvinick, N. Heess, and Raia Hadsell. Stabilizing transformers for reinforcement learning. ArXiv, abs/19100061 2019.
Jack W. Rae, Anna Potapenko, Siddhant M. Jayakumar, Chloe Hillier, and Timothy P. Lilli- crap. Compressive transformers for long-range sequence modelling. In International Confer- ence Learning Representations, 2020. URL htl.lttts//// httpss://operreviess net forummid BylKikSYDH
A. Rives, S. Goyal, J. Meier, Demi Guo, Myle Ott, C. L. Zitnick, Jerry Ma, and R. Fergus. Bio- logical structure and function emerge from scaling unsupervised learning to 250 million protein sequences, bioRxiv, 2019.
Stephen Roller, Emily Dinan, Naman Goyal, Da Ju, Mary Williamson, Yinhan Liu, Jing Xu, Myle Ott, Kurt Shuster, Eric Smith, et al. Recipes for building an open-domain chatbot. arXiv preprint arXiv:2004. 13637, 2020.
Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. Efficient content-based sparse attention with routing transformers. arXiv preprint arXiv:2003.05997 2020.
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representa- tions. In NAACL-HLT (2), 2018
Sainbayar Sukhbaatar, Arthur Szlam, Gabriel Synnaeve, Soumith Chintala, and R. Fergus. Maze- base: A sandbox for learning from games. ArXiv, 1,.040,,, 2015a.
Sainbayar Sukhbaatar, Arthur Szlam, Jason Weston, and Rob Fergus. End-to-end memory networks. In NIPS, 2015b.
Sainbayar Sukhbaatar, Édouard Grave, Piotr Bojanowski, and Armand Joulin. Adaptive attention span in transformers. In Proceedings of the 57th Annual Meeting of the Association for Compu- tational Linguistics, pp. 331-3331 2019a.
Sainbayar Sukhbaatar, Edouard Grave, Guillaume Lample, Herve Jegou, and Armand Joulin. Aug- menting self-attention with persistent memory. arXiv preprint 1901v:1977.0144 2019b.
Yi Tay, Mostafa Dehghami, Dara Bahri, and Donald Metzler. Efficient transformers: A survey, arXiv preprint ar arXiv:20009066322. 2020.
11

---

Under review as a conference paper at ICLR 2021
Jack Urbanek, Angela Fan, Siddharth Karamcheti, Saachi Jain, Samuel Humeau, Emily Dinan, Tim Rocktäschel, Douwe Kiela, Arthur Szlam, and Jason Weston. Learning to speak and act a fantasy text adventure game. In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNIPP), pp. 673-683, 2019.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Sinong Wang, Belinda Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXhv:2006.04760 2020.
John T Wixted. The psychology and neuroscience of forgetting. Annu. Rev. Psychol., 55:235-269, 2004.
Chao-Yuaa Wu, Christoph Feichtenhofer, Haoqi Fan, Kaiming He, Philipp Krahenbuhl, and Ross Girshick. Long-term feature banks for detailed video understanding. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp.
2019.
Felix Wu, Angela Fan, Alexei Baevski, Yann Dauphin, and Michael Auli. Pay less attention with lightweight and dynamic convolutions. International Conference on Learning Representations, 2018.
Zihao Ye, Qipeng Guo, Quan Gan, Xipeng Qiu, and Zheng Zhang. Bp-transformer: Modelling long-range context via binary partitioning. arXiv preprint arXiv; 1911:0091,000700 2019.
Jiacheng Zhang, Huanbo Luan, Maosong Sun, Feifei Zhai, Jingfang Xu, Min Zhang, and Yang Liu. Improving the transformer translation model with document-level context. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 533-542, 2018
12

---

Under review as a conference paper at ICLR 2021
A APPENDIX
A.1 ADDITIONAL EXPERIMENTAL RESULTS
A.1.1 WIKITEXT-I03 LANGUAGE MODELING
The Wikitext-103 word-level language modeling benchmark (Merity et al. 2016) consists of col- lection of Wikipedia articles and a fixed vocabulary size of 270K. We set the max attention span for EXPIRE-SPAR -SANN to 8K. We compare EXPIRE-SPA SPAN to existing work in Table 5 and show that even fairly small models trained with EXPIRE-SPAN achieve competitive results. Next, we analyze the performance of EXPIRE-SPAN on Wikitext-103 the memory size increases. We compare standard Transformer model in Figure IT much better.
even with far smaller memory, EXPIRE SPAN performs
A.1.2 EXPIRE-SPAN ANALYSIS ENWIK8
In Figure 12, we analyze multiple layers of the model and show that different layers identify different types of information. Several layers retain summarizing information about sentences or sections by attending strongly to spaces, new lines, and section titles.
A.1.3 IMPORTANCE OF STRUCTURED DROPOUT FOR REGULARIZATION
We analyze the importance of structured dropout to regularize the large memory capacity provided by EXPIRE-SPAN. In an experiment on enwiki8, Figure 13 shows that loss on a portion of validation data was incredibly large. This part corresponds model likely never encountered such table during training. During validation, this caused all non- table tokens to expire. Without regularizing the model memory size during training, the model can easily overfit.
66K token long table. We hypothesize that the
Model
Params
Test
exoire span
DEQ-Trans. (Bai et al.
2019)
110M
23.3
Trans-XL. DDai et al. 2019)
257M
18.3
Dev Perplesity
20.0
Feedback Trans. (Fnn et al.
2020)
77M
18.3
18.5
Trans. Lryyr (an el al.
201
423M
17.7
Compressive Trans. |Rac al. (020)
277M
17.1
19.0
Routing Trans. (Roy el al. 2020)
15.8
18.5
100
500
1000
EXPIRE-SPAN
140M
19.6
Average
Table 5: Wikitext-103 Results. We report per-
Figure 11: Performance as a function of Memory Size Wikitext-103
plexity on test.
Toe Breat cRotrES
Cab Gnatt Mriie and THE F.D. wew.k dleval weireinnliie are May great restres in vaberan afriee our the past alctett
Figure 12: Per-Layer Expiration in EXPIRE-SPAN on enwiki8. We visualize the expire-spans of different layers: layer 6 gives long span to spaces, layer favorites special tokens like newlines and section titles, and layer 10 pays attention to named entities.
A. 1.4 COLLIDING ORJECTS EASY
We experiment with easier version of the Colliding Objects task where objects do not have colors. The model has to predict either the last collision, or a mapping of the last collisions. In contrast to the harder task, there color switches and any collision prediction is valid.
13

---

Under review as a conference paper at ICLR 2021
baceline
acphrespan
Valcarion
www.mmm
Long Table of Takens
Figure 13: Extreme Overfitting on part of validation occurs without proper regularization.
Model
Maximum Span
Test Error
Transformer
1024
39.1
Expire-Span
1024
19.5
Expire-Span
2048
9.1
Expire-Span
4096
3.2
Table 6: Colliding Objects Results. We report test emor.
A.2 ADDITIONAL IMPLEMENTATION DETAILS
A.2.1 LIGHT TASKS
Instruction Following Task We train 6-layer models with hidden size of 512 and 8 attention heads. To train, we use the Adam optimizer with a learning rate of 7e-4 and 8000 warmup updates. We set the Expire-Span ramp to 64 and the Expire-Span loss to 2e-6.
A.2.2 REINFORCEMENT LEARNING
We used MazeBase (Sukhbaatar et al. 201 to construct tasks in grid world. Agents can observe its surrounding 3 3 area and move in the four cardinal directions. Every objects and their properties are described by words such as "agent", "block", "blue", etc. Thus, the input the model is binary tensor of size 3 x 3 vocabulary-size.
"bblokt""""loc"",
We train 2-layer Transformers with 64 hidden units using actor-critic algorithm. We used a BPTT length of 100, and an entropy cost of 0.0005.
Corridor Task The corridor length is sampled from L/33, 200). All models are trained for 100M steps. We used RMSProp optimizer with learning rate of 0.0001 and batch size of 64. For the expire-span models, we set the maximum span L 200, the loss coefficient to 5c-6 and the ramp length to 16.
Multi-Room Room Portal In this task, there are 50 rooms sequentially connected together. Each room is 5 x 5 in size, and have two doors with different colors. If agent go the correct door, it will be teleported to the next room, but if it is the wrong door, the agent will be teleported back to the first room and have to start over. Which of the two doors is correct in each room is randomly decided and fixed throughout the episode. This information is not visible to the agent, thus can only be discovered by trial and error within each episode. The current room number is visible the agent.
When the agent successfully transitions from the k-th room to the next, receives a reward of 0.1k. The episode ends if the agent makes two mistakes in the same room, reaches the last room, when the number of steps reach 1000. A reward discount of 0.98 used. All models are trained with Adam optimizer with learning rate 0.0005, and batch size of 1024, with gradients are clipped at O.I. We set L = 100, A = 16 and a =le-6 for the expire-span models.
A.2.3 COLLISION TASK
At the start of the simulation, each particle samples Gaussian Normal velocity and position uniform inside 16 x 16 grid. At each time step the particles' position is updated by adding its velocity (unless it would go off the grid, in which case its velocity is re-sampled). There are 5 different colors, and
14

---

Under review as a conference paper at ICLR 2021
particle can change its color randomly at each step with 0.05 probability. A collision happens when the two particles have the same rasterized locations, but it does not affect the movement.
Given question specifyyng two colors, the task is to report in which of the four quadrants of the grid the last collision of the specified-colors occurred. To make the task easier to learn, 40% of the queries will have the matching colors the last collision.
The model is given an input sequence of tokens that has entries per timestep. The first are the rounded and rasterized (z: y) locations of the two particles, and next are tokens representing the colors of the particles. The last entries are "question" tokens that specify the colors of the collision. The output sequence has token for each quadrant. We generate 50M steps for training. which equals to 400M entries.
Easy Version: The particles have no color in this version. There are two types of questions, in which the task is to report either
1. in which of the four quadrants of the grid the last collision occurred.
2. the label mapping of the last 3 collisions.
A.2.4 LANGUAGE MODELING DETAILS
enwiki8 We train 12-layer models with a hidden size of 512 and 8 attention heads. To train, we use Adam optimizer with a learning rate of 7e-4, batch size of 512, block size of 512 and 8000 warmup updates. All models are trained for 100k updates. The model in Table further fine-tuned for another 10k updates with a 10x smaller LR. The baseline models used for comparison are the same size model following the same training protocol.
PG-19 Besides the attention span, all model parameters and training parameters were held con- stant. Each model had 12 layers, a hidden size of 512, a feed forward hidden size of 2048, attention heads, and processed 512 characters tion as described by Glorot & Bengio (2010), used dropout and attention dropout of 0.2, clipped the gradients 0.3, warmed up the learning rate linearly 8000 steps, and used cosine annealing to decay the learning rate after warmup (Loshchilov & Hutter (016). For the EXPIRE-SPAR models, we used ramp of 128 and an expiration loss coefficient of le-6.
time. We initialized the weights using uniform distribu-
Wikitext-103 All models have 8 layers and 1024 hidden units (4096 in ReLU layers). In addition to the dropout of 0.3 applied to attention and ReLU activation, outputs from the embedding layer and the last layer had a dropout of 0.2. We used the adaptive input Baevski & Auli (2019) and the adaptive softmax Grave et al. (2017) 1) for reducing the number of parameters within word embed- dings. The models trained for 300k updates with block size of 256, and gradients are clipped at 0.1. The other hyperparameters are the same as the enwik8 experiments.
15


Reviews:
[{"review_id": "uPX8CM4JVas", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary**\nThe paper proposes a method for overcoming the long-term memory bottleneck of transformers. The idea is to assign a value (expire-span) to each formed memory, which indicates how long the memory should be stored and be available for the transformer to access it. The authors demonstrate the performance of their approach on a set of\nsynthetic and character-level language modeling benchmarks. \n\n**Significance**\nWhile the idea seems to be quite interesting and the presentation of the paper is clear and sound, I have the following concerns:\n\n- As the expire-span does not seem to be updated, the model must know how long to keep the memory when the memory is formed. Couldn't this potential cause issues when information arriving in the future would influence\nthe span of how long the memory should be kept? \n- From the author's descriptions, the method appears relatively brittle to hyperparameter choice. In particular, the method requires some sophisticated form of regularization for the performed benchmarks. Thus, raising my concerns about the stability and scalability of the approach. \n\nI would appreciate it if the authors could elaborate on my concerns.\n\n- The paper misses important related work in this domain. The paper Gers et al. \"Learning to forget continual prediction with LSTM\" already proposes a mechanism to remove memories that are not needed anymore. Moreover, the proposed approach is adaptive as for each token, the network decides if it should clear some of its memory. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "BnBOom1Xd_U", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Modified score: thank you authors for your thorough response. Given the new information and baselines, I think this is a promising paper that passes the acceptance threshold.\n\nOverall Quality: The authors present a method to improve the efficiency of transformer models when computing attention over previous time steps. Although this presents a neat idea that has the potential to improve an increasingly important model architecture, the experiments fall short of matching the claim that this method provides enables more efficient attention computation over memories _in practice_. Specifically, their baselines do not include relevant transformer modifications aimed at efficiency and they provide no detailed analysis on the memory size in practice. If the authors included more thorough experiments, this would be a strong paper. In their absence, it is marginally below the acceptance threshold. \n\nClarity: The abstract, introduction, background, and methods section were detailed yet easy to follow. The comparison of time complexity of prior work in the background section was particularly helpful. However, this precision did not carry over into the experimental section, which lacked thorough experimentation (detailed under weaknesses below) and figures 3-5 were out of order relative to the prose (the latter point is minor and does not affect my rating).\n\nSignificance: The potential impact is very high, especially as applications for transformers grow. If the authors could address the weaknesses outlined below, this could be an enormously helpful augmentation to the transformer architecture.\n\nStrengths:\n- The authors focus on an important problem for a very relevant architecture.\n- The writing is clear and enjoyable. Section 3 in particular is a very friendly introduction to transformer time complexity.\n- Evaluations performed over a variety of applications, spanning simple/toy to more realistic tasks.\n\nWeaknesses:\n- Corridor, instruction, portal, copy, pg-19, and colliding objects tasks only show comparisons for standard transformer models, as opposed to (at least one or two) comparable efficiency-optimized models. Giving the authors the benefit of the doubt, the first few experiments may serve more as proofs of concepts, where direct comparison with prior work is not as relevant or useful. But this leaves only one task in the paper with comparison to prior work on improving transformer efficiency: en-wiki-8. On en-wiki-8, the authors compare with just 1 modification and the improvement seems rather small. Small margins of improvement alone are not enough to reject a paper, but, given that this is the only result with a head to head comparison of efficiency optimized transformers, it makes it difficult for the community to discern the contribution of the work. Furthermore, on pg-19, copy task, and object collision, the authors do not provide the memory size/average memory size/effective memory size. This makes it difficult to understand if performance gains correspond with performance improvements, which is the methods stated purpose.\n- Intuitively, an inductive bias to expire memories would make a learned model more brittle when transferring to new tasks. E.g., in the instruction task a new form of instruction may become relevant in a test task that was never relevant in training tasks Why is this a reasonable trade-off to make?\n\nQuestion:\n- What value is shown in table 2? The caption says bit-per-byte, but the numbers are inconsistent with figure 7.\n- in figure 11, how is memory computed?", "extra_scores": {}, "extra_text": {}}, {"review_id": "7jX2QcJU19", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "To help Transformer learn long sequence efficiently, the paper performs attention on selective timesteps that have high expire-span scores. For each timestep, the expire-span score is computed by mapping the corresponding hidden feature to a number, which is learnt during training. Soft masking is applied to make the learning differentiable. An additional loss is introduced to reduce the average span, making the attention sparse. The proposed attention is integrated into each layer of Transformer and tested on several synthetic tasks and two language modelling datasets, yielding promising results. \n\nPros:\n- The proposed solution (computing expire score and minimizing the average span) is elegant and seems novel within Transformer context\n- The properties and behaviours of the method are well illustrated with detailed analysis and visualization\n- Diverse experiments are conducted\n\nCons:\n- Insufficient comparison with other Transformer-based baselines \n- The results on real data are weak\n\nDetail comments and questions\n\n- Sec 4.1, the equation computing o_t should be a summation over i\n- Before Transformer, sparse attention has been studied deeply in the literature. It may be beneficial to review some works (e.g., [1,2,3]) and try to integrate them into Transformer as additional baselines to make the experiment stronger. \n- No experimental result demonstrates that the method can reduce computation complexity. Please consider including a comparison of running time or physical memory usages between your method and other Transformers\n- It is unclear what are the baselines mentioned in the experiments. Are they vanilla Transformers? How did the authors control the memory size of the baseline as in Fig.3, 4 and 7?\n- For some synthetic tasks, it is better to include stronger baselines [4,5] to show the advantage of the proposed method over other variants of Transformer\n- In Table 2, the performance gap is significant. Is it possible to improve your performance with more parameters? \n\n[1] Ke, Nan Rosemary, Anirudh Goyal ALIAS PARTH GOYAL, Olexa Bilaniuk, Jonathan Binas, Michael C. Mozer, Chris Pal, and Yoshua Bengio. \"Sparse attentive backtracking: Temporal credit assignment through reminding.\" In Advances in neural information processing systems, pp. 7640-7651. 2018. \n\n[2] Martins, Andre, and Ramon Astudillo. \"From softmax to sparsemax: A sparse model of attention and multi-label classification.\" In International Conference on Machine Learning, pp. 1614-1623. 2016. \n\n[3] Niculae, Vlad, and Mathieu Blondel. \"A regularized framework for sparse and structured neural attention.\" In Advances in neural information processing systems, pp. 3338-3348. 2017. \n\n[4] Gonc¸alo M Correia, Vlad Niculae, and Andre FT Martins. Adaptively sparse transformers. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 2174–2184, 2019.  \n\n[5] Sainbayar Sukhbaatar, Edouard Grave, Piotr Bojanowski, and Armand Joulin. Adaptive attention ´ span in transformers. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 331–335, 2019a. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the problem of identifying what information to forget in attention mechanisms, with the goal of enabling attention mechanisms to deal with longer contexts. This is a simple yet intuitive extension:  self-attention is augmented with an expiration value  prediction. Experiments were carried out on NLP and RL tasks.
Overall, the paper has novelty in the proposed idea, however, there are concerns about the strength of the experiments; that the experiments fall short.
Decision: Reject