Adaptive Computation Time for Recurrent Neural Networks
Alex Graves
cs.NE
2016-03-30
Graves adds a differentiable halting unit so RNNs learn how long to ponder. Parity error falls from ~40% without ACT to under 5% at tau<=0.03; Wikipedia bits-per-char barely moves.
Feedforward depth and RNN unroll length are chosen in advance. Hard and easy inputs pay the same stack of layers. Going deeper can help, if gradients survive, and you still pay for the worst case. The missing piece is letting the net decide how many updates to run on this input before emitting an output.
In 2016 Alex Graves at DeepMind introduced Adaptive Computation Time. The architectural add-on is small: a sigmoidal halting unit, then a mean-field mix of intermediate states and outputs. The procedure is deterministic and differentiable. It does not inject noise into the parameter gradients.
A standard RNN does one state transition per input step. ACT allows N(t) intermediate updates on the same input, sharing the same transition and output parameters. A binary flag marks whether the input step just advanced, so repeated computation is not confused with a repeated input.
Each intermediate state produces a halt activation h. Computation stops when the sum of h exceeds 1-epsilon (epsilon=0.01 in the experiments); the last step takes the remainder so the probabilities sum to one. State and output are the weighted mean under that distribution. No sampling.
Left alone, the net ponders forever to avoid being wrong. Ponder is defined as N(t) plus the remainder, summed over the sequence, and added to the loss with a hand-chosen weight tau. N(t) is discontinuous when the threshold is crossed; training treats N(t) as constant and backprops only through the remainder. The halt bias starts positive so early training does not run away, and a hard cap M (default 100) bounds the worst case.
Training uses Adam at 1e-4 and Hogwild with 16 threads. Synthetic tasks run for 1M iterations, language for 10k. Twenty random seeds per tau, logarithmic grid search on tau.
Parity feeds a 64-d vector with 11 to 64 nonzero bits, once, into a 128-unit tanh RNN. With no time axis the recurrent edge is unused, so this is a one-hidden-layer net. Mean error without ACT is near 40% (chance 50%); for tau at most 0.03, mean error falls below 5%. Successful nets increase ponder roughly linearly with difficulty.
Logic packs 1 to 10 gates into each vector; LSTM width 128. Sequence error without ACT is about 0.2; for tau at most 0.01 it is essentially zero. Low-tau nets solve it in about 10k iterations. Ponder clusters around 5-6, near the mean number of gates per sequence.
Addition presents 1 to 5 numbers of up to 5 digits; LSTM width 512, M=20. Every tau in the grid is solved perfectly with ACT. Efficient nets have ponder-versus-digits slope near 1, like long addition. The text does not quote a no-ACT number for this task.
Sort takes 2 to 15 Gaussian values and emits sorted indices; LSTM width 512. Error is about 12% without ACT and about 6% at the best tau, at roughly 9 times the compute. Ponder spikes near the end of the sequence.
Byte-level Wikipedia with 1500 LSTM units barely moves bits per character, and ponder stays low. Plots show extra thought at spaces, commas, and full stops, and at XML tag boundaries, not on random IDs. Loss and entropy also rise on unpredictable tokens, so they do not separate structure from noise the way ponder does.
This is an early paper in the line that spends different compute per token: a halt unit, a ponder penalty, mean field instead of policy-gradient samples. Early-exit nets, adaptive depth, and test-time compute still face the same two questions: how to match budget to difficulty, and who sets the trade-off weight.
On synthetic tasks it unpacks inherently sequential algorithms from static vectors. On real language the score barely moves; the prize is a probe of implicit segment boundaries. It is not a language-model silver bullet.
Graves says behavior is sensitive to tau and the value is hand-chosen. Mean field assumes states interpolate linearly; at convergence mass collapses to a point and the assumption is idle, mid-training it may not be. The ponder cost is discontinuous in N; the implementation ignores that. Gaussian sort keys can sit almost on top of each other, which the paper flags. Wikipedia has no validation split and reports training loss because the nets did not overfit, so the number is not a modern hold-out. M=100 is a safety cap; learned N stayed far below it.