Recurrent Decoder Feedback Over Parallel Encoder Memory

Why People Wanted It

A fixed-depth Transformer gives each position a bounded number of layers to compute with. That is a problem when the task is to update a state one input at a time: parity accumulates bits, while permutation tracking composes group elements. The real question is whether a Transformer can let later tokens build on earlier computation without making every token traverse an ever-growing stack of layers.

RLT splits the work. A causal encoder processes token representations and builds reusable key–value memory. A decoder then processes positions in order, combining each position's encoder representation with the previous position's final decoder output. Thus, with decoder depth $L_D$, a sequence of $t$ tokens creates a recurrent path through $tL_D$ decoder blocks, while each token still passes through only $L_E+L_D$ layers.

The Core Move

Keep a causal encoder's memory available, but make the decoder's input depend on its own previous output: $u_t = \operatorname{Merge}(e_t,s_{t-1})$, then $s_t = D_\phi(u_t;M_{\le t},C^D_{<t})$.

Here $e_t$ is the current encoder representation, $M_{\le t}$ is the encoder memory through position $t$, and $C^D_{<t}$ is the decoder's recent self-attention cache. The decoder state passed forward includes both its final output and that cache.

Quiz

What creates the recurrent computation path in RLT-1?

The encoder repeats its full stack once for every token.

The previous decoder output is fed into the next token's decoder input through a gated merge.

The current token attends to all future encoder representations.

The decoder shares one fixed output across the whole sequence.

$ check

Why the Merge Is Gated

Here is the part that gets technical: the merge is not just a sum of the new encoder feature and old decoder state; it uses a learned gate to choose how much each contributes. In the paper's notation, $u_t = g_t \odot W_e e_t + (1-g_t) \odot W_s s_{t-1}$, where $g_t = \sigma(W_g[e_t;s_{t-1}])$ and the feedback contribution is scaled by $\alpha$ in the implemented form.

The gate is computed from both inputs, so its choice can depend on the current token representation and the accumulated decoder result. $W_e$ and $W_s$ project the two signals into the decoder width; $W_g$ produces an elementwise mixing coefficient, and $\alpha$ controls feedback scale. The main comparison uses $\alpha=0.1$. This gives the decoder a learned route to retain its recurrent computation or emphasize new encoder evidence, rather than forcing a fixed blend.

Why the Decoder Cache Is Part of the Recurrent State

Now the version for readers who want more of the machinery: the recurrent state is not only $s_t$; it is $H_t=(s_t,C^D_t)$, because later decoder updates need both the previous final output and the self-attention keys and values retained from earlier positions.

At each decoder block, the current input forms its key and value before causal sliding-window attention, avoiding a circular dependency at the current position. The block then uses encoder-memory cross-attention and an FFN. After the update, the decoder retains the recent key–value positions allowed by its window. So the transition updates the feedback vector and decoder cache together; the encoder memory supplies conditioning, rather than being the recurrent state itself.

Why Encoder Memory Can Be Reused

Here is the deeper execution constraint: the encoder is causal, and decoder position $t$ attends only to the encoder prefix $M_{\le t}$, even if prefill has already computed memory for the whole prompt. During generation, a new token is encoded incrementally, its encoder key–value entry is appended, and the decoder advances with the updated memory and its own cache.

This lets the decoder revisit token representations through encoder-memory attention without recomputing the encoder stack for every decoder step. But it does not remove sequential dependence in RLT-1: prompt prefill still evaluates decoder states $H_1,\ldots,H_T$ in order, because each update feeds the next. Chunked feedback changes that scheduling; it is a separate variant, not a property of the per-token recurrence described here.

Minimal Causal Code

The sketch exposes the state transition; attention and projections are abbreviated, not optimized.

state = initial_decoder_state()
encoder_memory = []

for t, token in enumerate(tokens):
    e_t, encoder_kv = causal_encoder_step(token)
    encoder_memory.append(encoder_kv)

    # Only the causal prefix is visible to this position.
    memory_prefix = encoder_memory[: t + 1]
    u_t = gated_merge(e_t, state.output)

    # The decoder uses its prior cache and returns both the new output
    # and the updated cache as the next recurrent state.
    output_t, decoder_cache = decoder_step(
        u_t, memory_prefix, state.cache
    )
    state = DecoderState(output=output_t, cache=decoder_cache)

What You Gain, and What You Lose

The gain is a computation path whose depth grows with sequence length, while each token still evaluates only the encoder and decoder stacks once. Reusing encoder memory also gives the decoder access to the causal token representations as its recurrent state evolves. This is aimed at tasks where later decisions need to build on earlier state updates.

The cost is order-dependent decoder work: RLT-1 needs one decoder update per known token, so prompt prefill is sequential through those updates even though the encoder processes known tokens in parallel. More decoder depth lengthens the recurrent path but adds decoder work in token order. The decoder cache is part of the state and must be carried forward as well. The design therefore trades parallel decoder scheduling for recurrent computation; it does not make the whole model parallel across positions.

Quiz

Which components make up the recurrent decoder state described for RLT-1?

Only the current encoder representation.

The entire sequence of token IDs and no cache.

Only the encoder's global key–value memory.

The decoder output and its self-attention cache.

$ check