title: SubGen: Token Generation in Sublinear Time and Memory
summary: 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.
paper_authors._id: 65c982f7957afc29ceabf34b
paper_authors.name: Amir Zandieh
paper_authors.status: extracted_pending
paper_authors.statusLastChangedAt: 2024-12-09T13:27:31.974Z
paper_authors._id: 6756f028bb1d50918a346330
paper_authors.avatarUrl: /avatars/097b47a72bf8931b50b5971bb4202766.svg
paper_authors.fullname: Amir Zandieh
paper_authors.type: user
paper_authors.user: amirzed512
paper_authors._id: 65c982f7957afc29ceabf34c
paper_authors.name: Insu Han
paper_authors.status: extracted_confirmed
paper_authors.statusLastChangedAt: 2024-02-12T13:49:32.782Z
paper_authors._id: 6563e5bb7061c2cbda39bb98
paper_authors.avatarUrl: /avatars/c0fc559d81df1235501cbfa20f930902.svg
paper_authors.fullname: Insu Han
paper_authors.type: user
paper_authors.user: insuhan
paper_authors._id: 65c982f7957afc29ceabf34d
paper_authors.name: Vahab Mirrokni
paper_authors._id: 65c982f7957afc29ceabf34e
paper_authors.name: Amin Karbasi
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2024-02-12T16:57:04.882Z
paper_authors._id: 652d4155f14b3a0fda975851
paper_authors.avatarUrl: /avatars/58e5c95c694f13c3460c6fe9b652b6c8.svg
paper_authors.fullname: amin karbasi
paper_authors.type: user
paper_authors.user: aminkarbasi
paper_title: SubGen: Token Generation in Sublinear Time and Memory
paper_summary: 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.
paper_ai_keywords: large language models (LLMs) long-context token generation attention module key-value (KV) caching attention module sublinear complexity key embeddings online clustering online $\ell_2$ sampling attention decoding algorithm sublinear memory footprint sublinear time complexity error bound long-context question-answering KV cache compression methods