SubGen: Token Generation in Sublinear Time and Memory
Despite the significant success of large language models (LLMs), their
extensive memory requirements pose challenges for deploying them in
long-context token generation. The substantial memory footprint of LLM decoders
arises from the necessity to store all previous tokens in the attention module,
a requirement imposed by key-value (KV) caching. In this work, our focus is on
developing an efficient compression technique for the KV cache. Empirical
evidence indicates a significant clustering tendency within key embeddings in
the attention module. Building on this key insight, we have devised a novel
caching method with sublinear complexity, employing online clustering on key
tokens and online ell_2 sampling on values. The result is a provably
accurate and efficient attention decoding algorithm, termed SubGen. Not only
does this algorithm ensure a sublinear memory footprint and sublinear time
complexity, but we also establish a tight error bound for our approach.
Empirical evaluations on long-context question-answering tasks demonstrate that
SubGen significantly outperforms existing and state-of-the-art KV cache
compression methods in terms of performance and efficiency.
65c982f7957afc29ceabf34b
Amir Zandieh
extracted_pending
2024-12-09T13:27:31.974Z
6756f028bb1d50918a346330
/avatars/097b47a72bf8931b50b5971bb4202766.svg
Amir Zandieh
user
amirzed512
65c982f7957afc29ceabf34c
Insu Han
extracted_confirmed
2024-02-12T13:49:32.782Z
6563e5bb7061c2cbda39bb98
/avatars/be9fce9a03c258f3a205f3616530874d.svg
Insu Han
user
insuhan
65c982f7957afc29ceabf34d
Vahab Mirrokni
65c982f7957afc29ceabf34e
Amin Karbasi
admin_assigned
2024-02-12T16:57:04.882Z
652d4155f14b3a0fda975851
/avatars/58e5c95c694f13c3460c6fe9b652b6c8.svg
amin karbasi
user
aminkarbasi
SubGen: Token Generation in Sublinear Time and Memory
Despite the significant success of large language models (LLMs), their
extensive memory requirements pose challenges for deploying them in
long-context token generation. The substantial memory footprint of LLM decoders
arises from the necessity to store all previous tokens in the attention module,
a requirement imposed by key-value (KV) caching. In this work, our focus is on
developing an efficient compression technique for the KV cache. Empirical
evidence indicates a significant clustering tendency within key embeddings in
the attention module. Building on this key insight, we have devised a novel
caching method with sublinear complexity, employing online clustering on key
tokens and online ell_2 sampling on values. The result is a provably
accurate and efficient attention decoding algorithm, termed SubGen. Not only
does this algorithm ensure a sublinear memory footprint and sublinear time
complexity, but we also establish a tight error bound for our approach.
Empirical evaluations on long-context question-answering tasks demonstrate that
SubGen significantly outperforms existing and state-of-the-art KV cache
compression methods in terms of performance and efficiency.
A novel KV cache compression technique, SubGen, improves memory efficiency and performance in long-context token generation for large language models by using_online clustering and sampling.
large language models memory requirements long-context token generation attention module key-value caching key embeddings sublinear complexity online clustering online $\ell_2$ sampling attention decoding algorithm error bound