Do Efficient Transformers Really Save Computation?
This work addresses the challenge for researchers and practitioners in identifying when to use efficient Transformers, though it is incremental in providing theoretical insights rather than broad practical solutions.
The paper tackled the problem of whether efficient Transformers like Sparse and Linear Transformers truly save computation by analyzing their reasoning capabilities on Chain-of-Thought prompts modeled as Dynamic Programming tasks, finding that they require model sizes scaling with problem size but can be more efficient for a specific class of problems.
As transformer-based language models are trained on increasingly large datasets and with vast numbers of parameters, finding more efficient alternatives to the standard Transformer has become very valuable. While many efficient Transformers and Transformer alternatives have been proposed, none provide theoretical guarantees that they are a suitable replacement for the standard Transformer. This makes it challenging to identify when to use a specific model and what directions to prioritize for further investigation. In this paper, we aim to understand the capabilities and limitations of efficient Transformers, specifically the Sparse Transformer and the Linear Transformer. We focus on their reasoning capability as exhibited by Chain-of-Thought (CoT) prompts and follow previous works to model them as Dynamic Programming (DP) problems. Our results show that while these models are expressive enough to solve general DP tasks, contrary to expectations, they require a model size that scales with the problem size. Nonetheless, we identify a class of DP problems for which these models can be more efficient than the standard Transformer. We confirm our theoretical results through experiments on representative DP tasks, adding to the understanding of efficient Transformers' practical strengths and weaknesses.