Comparison of different Unique hard attention transformer models by the formal languages they can recognize

Leonid Ryvkin
6/3/2025
cs.LGcs.CLcs.FL

No confident code implementation found for this paper. 3 possible matches can be shown below.

Abstract

This note is a survey of various results on the capabilities of unique hard attention transformers encoders (UHATs) to recognize formal languages. We distinguish between masked vs. non-masked, finite vs. infinite image and general vs. bilinear attention score functions. We recall some relations between these models, as well as a lower bound in terms of first-order logic and an upper bound in terms of circuit complexity.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. 3 weaker matches are hidden by default — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Logical Languages Accepted by Transformer Encoders with Hard Attention

88% match2026

Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages

86% match2023

Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages

86% match2026

Tighter Bounds on the Expressivity of Transformer Encoders

82% match2023

On the Existence of Universal Simulators of Attention

82% match2025

Characterizing the Expressivity of Fixed-Precision Transformer Language Models

82% match2025

Cite this paper

@article{ryvkin2025comparison,
  title  = {Comparison of different Unique hard attention transformer models by the formal languages they can recognize},
  author = {Leonid Ryvkin},
  year   = {2025},
  eprint = {2506.03370},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2506.03370v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2506.03370.svg)](https://codeofpaper.com/paper/2506.03370)

Discussion