<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="bhattamishra-etal-2020-computational">
    <titleInfo>
        <title>On the Computational Power of Transformers and Its Implications in Sequence Modeling</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Satwik</namePart>
        <namePart type="family">Bhattamishra</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Arkil</namePart>
        <namePart type="family">Patel</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Navin</namePart>
        <namePart type="family">Goyal</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>2020-11</dateIssued>
    </originInfo>
    <typeOfResource>text</typeOfResource>
    <relatedItem type="host">
        <titleInfo>
            <title>Proceedings of the 24th Conference on Computational Natural Language Learning</title>
        </titleInfo>
        <name type="personal">
            <namePart type="given">Raquel</namePart>
            <namePart type="family">Fernández</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Tal</namePart>
            <namePart type="family">Linzen</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <originInfo>
            <publisher>Association for Computational Linguistics</publisher>
            <place>
                <placeTerm type="text">Online</placeTerm>
            </place>
        </originInfo>
        <genre authority="marcgt">conference publication</genre>
    </relatedItem>
    <abstract>Transformers are being used extensively across several sequence modeling tasks. Significant research effort has been devoted to experimentally probe the inner workings of Transformers. However, our conceptual and theoretical understanding of their power and inherent limitations is still nascent. In particular, the roles of various components in Transformers such as positional encodings, attention heads, residual connections, and feedforward networks, are not clear. In this paper, we take a step towards answering these questions. We analyze the computational power as captured by Turing-completeness. We first provide an alternate and simpler proof to show that vanilla Transformers are Turing-complete and then we prove that Transformers with only positional masking and without any positional encoding are also Turing-complete. We further analyze the necessity of each component for the Turing-completeness of the network; interestingly, we find that a particular type of residual connection is necessary. We demonstrate the practical implications of our results via experiments on machine translation and synthetic tasks.</abstract>
    <identifier type="citekey">bhattamishra-etal-2020-computational</identifier>
    <identifier type="doi">10.18653/v1/2020.conll-1.37</identifier>
    <location>
        <url>https://aclanthology.org/2020.conll-1.37</url>
    </location>
    <part>
        <date>2020-11</date>
        <extent unit="page">
            <start>455</start>
            <end>475</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Conference Proceedings
%T On the Computational Power of Transformers and Its Implications in Sequence Modeling
%A Bhattamishra, Satwik
%A Patel, Arkil
%A Goyal, Navin
%Y Fernández, Raquel
%Y Linzen, Tal
%S Proceedings of the 24th Conference on Computational Natural Language Learning
%D 2020
%8 November
%I Association for Computational Linguistics
%C Online
%F bhattamishra-etal-2020-computational
%X Transformers are being used extensively across several sequence modeling tasks. Significant research effort has been devoted to experimentally probe the inner workings of Transformers. However, our conceptual and theoretical understanding of their power and inherent limitations is still nascent. In particular, the roles of various components in Transformers such as positional encodings, attention heads, residual connections, and feedforward networks, are not clear. In this paper, we take a step towards answering these questions. We analyze the computational power as captured by Turing-completeness. We first provide an alternate and simpler proof to show that vanilla Transformers are Turing-complete and then we prove that Transformers with only positional masking and without any positional encoding are also Turing-complete. We further analyze the necessity of each component for the Turing-completeness of the network; interestingly, we find that a particular type of residual connection is necessary. We demonstrate the practical implications of our results via experiments on machine translation and synthetic tasks.
%R 10.18653/v1/2020.conll-1.37
%U https://aclanthology.org/2020.conll-1.37
%U https://doi.org/10.18653/v1/2020.conll-1.37
%P 455-475

Markdown (Informal)

[On the Computational Power of Transformers and Its Implications in Sequence Modeling](https://aclanthology.org/2020.conll-1.37) (Bhattamishra et al., CoNLL 2020)

• On the Computational Power of Transformers and Its Implications in Sequence Modeling (Bhattamishra et al., CoNLL 2020)

ACL

• Satwik Bhattamishra, Arkil Patel, and Navin Goyal. 2020. On the Computational Power of Transformers and Its Implications in Sequence Modeling. In Proceedings of the 24th Conference on Computational Natural Language Learning, pages 455–475, Online. Association for Computational Linguistics.