Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Models

Understand

Large language models (LLMs) have made fundamental changes in human life.

• The attention scheme is one of the key components over all the LLMs, such as BERT, GPT-1, Transformers, GPT-2, 3, 3.5 and 4.
• Inspired by previous theoretical study of static version of the attention multiplication problem [Zandieh, Han, Daliri, and Karbasi arXiv 2023, Alman and Song arXiv 2023].
• In this work, we formally define a dynamic version of attention matrix multiplication problem.