acceptodds
Under review as a conference paper at ICLR 2027

Infinite Graphs as Limits on Attention

Abstract

A finite-dimensional attention head cannot realize the random graph. Modeling a hard-attention head as a threshold dot-product graph, we show that a head of dimension fails the -extension property at every threshold. The Rado graph, in which every relational query has a witness, therefore lies beyond every finite dimension. Forster's sign-rank bound turns the barrier into a rate: a generic relation on tokens forces , independently of how the token embeddings are chosen. Grading a head by the largest query it answers gives a hierarchy. Answering every query on tokens needs at least tokens and dimension at least . Conversely, with tokens for a constant , a head with independent Gaussian embeddings of dimension suffices with high probability. At an exponential token budget, that Gaussian head fails with high probability for each dimension : some of its directions have a positive cone too small for any available token to hit. For directed heads, with queries and keys separate, the barrier holds on tournaments and the Gaussian bounds transfer for . Whether some head answers all -token queries at dimension linear in is open.

Primary area:
foundation or frontier models, including LLMs
Keywords:
attention, representation capacity, random graphs, extension property, VC dimension, sign-rank

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_1ahMOpenReview ↗
Rating
1
Confidence
1
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

I have to admit that the contributions of this paper are completely obscure to me. The authors wrote a highly mathematical paper (using AI) without properly motivating the reasons why such findings are important. The text is incredibly hard to read. I cannot understand why this paper has been written at all. Therefore, I believe the paper should undergo a more careful proofreading.

Critical strengths

I could not find critical strengths because I could not understand the paper. This is the first time this happens in my experience.

Critical weaknesses

My main concern is with the presentation and overall clarity of the manuscript. While the paper follows several formal conventions of theoretical research, I believe its exposition falls short of the standards expected at a machine learning conference. In particular:

  • Abstract: The abstract is extremely dense and difficult to parse, even for a technically oriented audience. Rather than providing an accessible overview of the problem, its relevance, and the main contributions, it immediately introduces specialized concepts and technical results with little context. An abstract should help readers understand the significance of the work and encourage them to read further. In its current form, it instead constitutes an initial barrier to understanding the paper.

  • Motivation and problem formulation: The introduction does not adequately motivate the research question. It opens with a technical claim involving the Rado graph and finite-dimensional attention, without first establishing why this particular problem is relevant or worth investigating. Although such a presentation might be more common in certain areas of pure mathematics, I would expect a paper submitted to a machine learning conference to provide a clear motivation, an explicit problem formulation, and a discussion of the implications for the field. The absence of this framing makes it difficult to appreciate the significance of the contributions, independently of their mathematical validity.

  • Terminology and accessibility: The manuscript makes extensive use of specialized terminology before providing sufficient definitions or intuition. While technical language is unavoidable in a theoretical paper, readers should be guided through the concepts needed to understand the main arguments. Here, the exposition frequently assumes familiarity with mathematical objects and techniques that have not yet been introduced. This substantially limits the paper's accessibility. In my view, effective communication is an essential component of scientific research, and mathematical rigor should not come at the expense of clarity.

  • Organization and preliminaries: The organization further exacerbates these issues. The preliminaries appear only in Section 2, after several pages devoted to results, techniques, related work, discussion, and open problems. Consequently, the paper presents numerous formal theorem statements before introducing the definitions necessary to understand them. While it is entirely reasonable to summarize the main theoretical contributions in the introduction, I find the decision to present so many detailed theorem statements before establishing the relevant mathematical framework counterproductive. A clearer separation between an intuitive overview of the contributions and their formal development would substantially improve the readability and logical progression of the manuscript.

--

Overall, I believe the manuscript would benefit from a substantial revision of its exposition. My concern is not with the use of advanced mathematics or the technical nature of the results, but with the limited effort devoted to making the problem, its motivation, and its contributions understandable to the intended audience. As currently written, the paper places an unnecessarily high burden on the reader, making it difficult to assess the significance of the work.

Questions for authors

I have no questions for the authors, as I could not understand the motivation or contributions of the paper.

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

The paper studies the limitation of the attention head in terms of realizing certain graphs. The authors show that the Rado graph can not be realized by the attention head of any finite dimension.

Critical strengths

The broad research direction of understanding the limitations of modern architectures is very interesting and important.

Critical weaknesses

As mentioned earlier the paper does not hold to the standards of academic publications. It is hard to follow and incoherent with claims about concepts appearing without the definition of the concepts.

As another criticism I don't see why understanding whether a certain graph is realizable by the attention head architecture will help us improve our understanding of the attention mechanism.

Questions for authors

I don't have any questions that can affect my assessment

Reviewer_h6uaOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This work attempts to characterize limitations of self-attention through the representational capacity of threshold dot-product graphs. The authors study the attention matrix by constructing a corresponding threshold dot-product graph, and then study the dimensional requirements for this graph to satisfy the k-extension property. They obtain these limitations as using VC dimension, derive sign-rank lower bounds, and establish upper and lower bounds for Gaussian embedding constructions. The main technical result shows that Gaussian embeddings require dimension greater than Ω(k2/log⁡k)\Omega(k^2/\log k) at an exponential token budget to satisfy the k-extension property with high probability.

Critical strengths
  1. Limitations of self-attention mechanism is a well-studied problem. The graph-theoretic perspective on attention expressivity is interesting, and the Gaussian lower bound and geometric techniques techniques used to prove such limitations seem novel.
  2. The paper connects geometric representations, VC dimension, sign-rank, and existentially closed graphs within a common framework.
Critical weaknesses
  1. The paper is very difficult to read. The introduction does not convey the intuition, motivation, nor significance of the main results. Writing needs to be substantially improved, where these are clearly stated in the introduction.
  2. At least some background needs to be established before stating the main results, extension barrier before stating it, “even locally as expressive”-- what expressivity lower bound is being proved needs to be explained and justified, threshold dot-product graphs in terms of attention needs to be explained before deep-diving into results like witnessing budget etc.
  3. Many sentences do not make sense, like “The barrier comes from the inner-product threshold relation…”, “sign rank turns barrier into a rate”, and many others.
  4. The novelty and significance of the individual contributions should be explained more clearly. Some of the earlier results follow relatively directly from classical VC-dimension and sign-rank arguments. The Gaussian lower bound appears to be the central technical contribution, but the authors should better distinguish it from the known results and explain its significance, particularly given that the stronger dimensional lower bound applies only to Gaussian embeddings.
Questions for authors

Please see above.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.