  In recent years, Large Language Models (LLMs) have demonstrated remarkable
capabilities across a wide array of text-centric tasks. However, their `large'
scale introduces significant computational and storage challenges, particularly
in managing the key-value states of the transformer, which limits their wider
applicability. Therefore, we propose to adaptively release resources from
caches and rebuild the necessary key-value states. Particularly, we accomplish
this by a lightweight controller module to approximate an ideal top-$K$ sparse
attention. This module retains the tokens with the highest top-$K$ attention
weights and simultaneously rebuilds the discarded but necessary tokens, which
may become essential for future decoding. Comprehensive experiments in natural
language generation and modeling reveal that our method is not only competitive
with full attention in terms of performance but also achieves a significant
throughput improvement of up to 221.8%. The code for replication is available
on the https://github.com/WHUIR/ADORE.
