Table REF  considers
a sequence-to-sequence model,
and breaks down the comparisons
to training (with teacher forcing; [1]})
and autoregressive decoding.
Here we assume enough threads to fully parallelize
softmax attention across timesteps when the inputs are revealed to the model in full.
Rfa has a lower space complexity,
since it never explicitly populates the attention matrices.
As for time,
Rfa trains in linear time,
and so does the softmax attention:
in teacher-forcing training
a standard transformer decoder parallelizes the attention computation
across time steps.
The trend of the time comparison differs during decoding:
when only one output token is produced at a time,
Rfa decodes linearly in the output length,
while softmax attention decodes quadratically.
<TABLE><TABLE>