@inproceedings{
bergstr{\"a}{\ss}er2024the,
title={The Power of Hard Attention Transformers on Data Sequences: A formal language theoretic perspective},
author={Pascal Bergstr{\"a}{\ss}er and Chris K{\"o}cher and Anthony Widjaja Lin and Georg Zetzsche},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=NBq1vmfP4X}
}
Formal language theory has recently been successfully employed to unravel 
    the power of transformer encoders. This setting is primarily applicable in
    Natural Language Processing (NLP), as a token embedding function (where
    a bounded number of tokens is admitted) is first applied before feeding 
    the input to the transformer. 
    On certain kinds of data (e.g. time 
    series), we want our transformers to be able to handle arbitrary
    input sequences of numbers (or tuples thereof) without a priori
    limiting the values of these numbers. In this
    paper, we initiate the study of the expressive power of transformer encoders
    on sequences of data (i.e. tuples of numbers).
    Our results indicate an increase in expressive power of 
    hard attention transformers over data sequences, in stark contrast to the 
    case of strings.
    In particular, we prove that Unique Hard Attention Transformers (UHAT) over 
    inputs as data sequences no longer lie within the circuit complexity 
    class AC0 (even without positional encodings), unlike the case of string
    inputs, 
    but are still within the complexity class TC0 (even with positional
    encodings). Over strings, UHAT without positional encodings capture only
    regular languages. In contrast, we show that over data sequences
    UHAT can capture non-regular properties.
    Finally, we show that UHAT capture languages 
    definable in an extension of linear temporal logic with unary numeric
    predicates and arithmetics.
The Power of Hard Attention Transformers on Data Sequences: A formal language theoretic perspective
Pascal Bergsträßer Chris Köcher Anthony Widjaja Lin Georg Zetzsche