- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper make the existing computational lower bound of transformers more practical by designing a model called numerically-branched Word-RAM, which grant the algorithm the capability of branching. One of the main contribution of this paper is the development of a general lifting theorem, which shows that if a function is hard for arithmetic circuits on every nonempty open region, then it remains hard for algorithms with numerical branching.
Critical strengths
main theorem extends lower bound results from merely arithmetic circuit into algorithms that supports numerical branching, comparisons, and bit-reading operations, which is more practical.
I think the lifting theorem is not limited to Transformers, and it can be extended to other computational problems, which author mentioned through the matrix-multiplication application.
Critical weaknesses
The main computational model assumes exact real arithmetic, where computers uses finite numbers, such as floating-point numbers. This makes the result less practical.
To the best of my understanding, the paper assumes that the matrix-multiplication exponent which has to be greater than 2. However, whether is unknown. Therefore, the lower bound of this paper is conditional
Questions for authors
Q1: Does your general lifting theorem stay the same where the floating-point precisions (constant, , ) are different, where denotes the input sequence length and precisions are defined and discussed well in many expressiveness literature, such as [Li et al, 2024].
Q2: How is your lifting theorem fundamentally different from the classic results on branching algorithms and arithmetic circuits?
[Li et al, 2024] Chain of Thought Empowers Transformers to Solve Inherently Serial Problems. ICLR'24