acceptodds
Under review as a conference paper at ICLR 2027

Transformers Are Hard for Machines, Not Only for Circuits

Abstract

Saha, Xu, Ye, and Yu construct a transformer that no extended arithmetic circuit computes in fewer than gates when , and ask whether the bound survives in the Word-RAM model, whose algorithms branch on the values they compute. We prove one theorem, and a corollary answers their question for the numerically-branched algorithms defined next. Call a Word-RAM algorithm numerically-branched if its operations on real cells come from and a real value reaches word memory only in two ways. One is a comparison; the other is a read of its bits by a function whose level sets are countable unions of intervals. Rectified activations, argmax, threshold masking, and top- retrieval are all computed by numerically-branched algorithms. The theorem: if every extended arithmetic circuit agreeing with a function on some nonempty open subset of a region has size at least , then every numerically-branched algorithm computing on the whole region takes time at least . Every circuit lower bound whose reduction reads only local information therefore transfers. There is no hypothesis on , because the proof works with the algorithm's own trace. On a region where every comparison and every bit-read has a fixed outcome, that trace is a fixed circuit, and the region is built by nested shrinking rather than by a genericity assumption. The theorem has four consequences, for the transformer of Saha et al., its sigmoid and gated-linear-unit variants, rectified-linear-unit variants on an open piece where every rectifier is active and the perceptron is the identity, and real matrix multiplication.

Primary area:
foundation or frontier models, including LLMs
Keywords:
circuit complexity, algebraic complexity, Word-RAM, lower bounds, computational complexity, numerical computation, transformers, matrix multiplication

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_ZyUDOpenReview ↗
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

∙\bullet 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.

∙\bullet 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

∙\bullet The main computational model assumes exact real arithmetic, where computers uses finite numbers, such as floating-point numbers. This makes the result less practical.

∙\bullet To the best of my understanding, the paper assumes that the matrix-multiplication exponent ω\omega which has to be greater than 2. However, whether ω>2\omega > 2 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, log⁡n\log n, polyn\mathrm{poly n}) are different, where nn 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

Reviewer_bqF2OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies real-valued transformers, relating them both to real-valued circuits and to RAM machines that have both real-valued and word-valued registers. The main result relates a bound on circuits that compute f on an open subset of its domain to the time that it takes a machine to compute the same function. Combining this result with Saha et al's recent result, they get a lower bound on the running time of a RAM machine to compute the function a transformer computes.

Critical strengths

Studying transformers using models of computation that use real numbers is an interesting area. Transferring Saha et al's result from circuits to machines arguably brings the result closer to the computers that transformers are implemented on.

Critical weaknesses

I didn't understand very clearly the choice of numerically-branched Word-RAM machines. In particular, the bit-reading operations seem like a very broad class of operations and I didn't understand why they are needed to compute what transformers compute.

The first part of the paper is fairly clearly written, but clarity drops rapidly starting at page 6. I particularly didn't understand how sections 4.1-2 fit into the rest of the paper. Does Cor 4.1 not follow straight from Thm 3.3 and Saha et al?

Questions for authors
  • Can you give some intuition for why bit-reading operations are needed?
  • I didn't understand how sections 4.1-2 fit into the rest of the paper. Does Cor 4.1 not follow straight from Thm 3.3 and Saha et al?
Reviewer_PN8aOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the hardness of expressing transformers in the Word-RAM model. An existing result establishes a lower bound for expressing a transformer as an extended arithmetic circuit. The paper shows that the same lower bound is obtained for numerically branched Word-RAM algorithms but in terms of worst-case running time rather than size.

Critical strengths

Soundness: The reviewer could not find any errors despite careful reading and the technical difficulty of the proofs.

Critical weaknesses

Clarity: While most of the paper is relatively easy to follow, Section 4.2 gets quite dense and technical. Perhaps some of the technical details could be saved for the appendix, making room for more insight.

Questions for authors

Why is it interesting to extend the hardness result of Saha et al. for the Word-RAM model? More discussion on this in the paper early on could be useful to the reader.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.