<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="merrill-etal-2022-saturated">
    <titleInfo>
        <title>Saturated Transformers are Constant-Depth Threshold Circuits</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">William</namePart>
        <namePart type="family">Merrill</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Ashish</namePart>
        <namePart type="family">Sabharwal</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Noah</namePart>
        <namePart type="given">A</namePart>
        <namePart type="family">Smith</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>2022</dateIssued>
    </originInfo>
    <typeOfResource>text</typeOfResource>
    <genre authority="bibutilsgt">journal article</genre>
    <relatedItem type="host">
        <titleInfo>
            <title>Transactions of the Association for Computational Linguistics</title>
        </titleInfo>
        <originInfo>
            <issuance>continuing</issuance>
            <publisher>MIT Press</publisher>
            <place>
                <placeTerm type="text">Cambridge, MA</placeTerm>
            </place>
        </originInfo>
        <genre authority="marcgt">periodical</genre>
        <genre authority="bibutilsgt">academic journal</genre>
    </relatedItem>
    <abstract>Transformers have become a standard neural network architecture for many NLP problems, motivating theoretical analysis of their power in terms of formal languages. Recent work has shown that transformers with hard attention are quite limited in power (Hahn, 2020), as they can be simulated by constant-depth AND/OR circuits (Hao et al., 2022). However, hard attention is a strong assumption, which may complicate the relevance of these results in practice. In this work, we analyze the circuit complexity of transformers with saturated attention: a generalization of hard attention that more closely captures the attention patterns learnable in practical transformers. We first show that saturated transformers transcend the known limitations of hard-attention transformers. We then prove saturated transformers with floating-point values can be simulated by constant-depth threshold circuits, giving the class TC0 as an upper bound on the formal languages they recognize.</abstract>
    <identifier type="citekey">merrill-etal-2022-saturated</identifier>
    <identifier type="doi">10.1162/tacl_a_00493</identifier>
    <location>
        <url>https://aclanthology.org/2022.tacl-1.49</url>
    </location>
    <part>
        <date>2022</date>
        <detail type="volume"><number>10</number></detail>
        <extent unit="page">
            <start>843</start>
            <end>856</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Journal Article
%T Saturated Transformers are Constant-Depth Threshold Circuits
%A Merrill, William
%A Sabharwal, Ashish
%A Smith, Noah A.
%J Transactions of the Association for Computational Linguistics
%D 2022
%V 10
%I MIT Press
%C Cambridge, MA
%F merrill-etal-2022-saturated
%X Transformers have become a standard neural network architecture for many NLP problems, motivating theoretical analysis of their power in terms of formal languages. Recent work has shown that transformers with hard attention are quite limited in power (Hahn, 2020), as they can be simulated by constant-depth AND/OR circuits (Hao et al., 2022). However, hard attention is a strong assumption, which may complicate the relevance of these results in practice. In this work, we analyze the circuit complexity of transformers with saturated attention: a generalization of hard attention that more closely captures the attention patterns learnable in practical transformers. We first show that saturated transformers transcend the known limitations of hard-attention transformers. We then prove saturated transformers with floating-point values can be simulated by constant-depth threshold circuits, giving the class TC0 as an upper bound on the formal languages they recognize.
%R 10.1162/tacl_a_00493
%U https://aclanthology.org/2022.tacl-1.49
%U https://doi.org/10.1162/tacl_a_00493
%P 843-856

Markdown (Informal)

[Saturated Transformers are Constant-Depth Threshold Circuits](https://aclanthology.org/2022.tacl-1.49) (Merrill et al., TACL 2022)

• Saturated Transformers are Constant-Depth Threshold Circuits (Merrill et al., TACL 2022)

ACL

• William Merrill, Ashish Sabharwal, and Noah A. Smith. 2022. Saturated Transformers are Constant-Depth Threshold Circuits. Transactions of the Association for Computational Linguistics, 10:843–856.