<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="merrill-sabharwal-2023-parallelism">
    <titleInfo>
        <title>The Parallelism Tradeoff: Limitations of Log-Precision Transformers</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>
    <originInfo>
        <dateIssued>2023</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>Despite their omnipresence in modern NLP, characterizing the computational power of transformer neural nets remains an interesting open question. We prove that transformers whose arithmetic precision is logarithmic in the number of input tokens (and whose feedforward nets are computable using space linear in their input) can be simulated by constant-depth logspace-uniform threshold circuits. This provides insight on the power of transformers using known results in complexity theory. For example, if LʼneqP (i.e., not all poly-time problems can be solved using logarithmic space), then transformers cannot even accurately solve linear equalities or check membership in an arbitrary context-free grammar with empty productions. Our result intuitively emerges from the transformer architecture’s high parallelizability. We thus speculatively introduce the idea of a fundamental parallelism tradeoff: any model architecture as parallelizable as the transformer will obey limitations similar to it. Since parallelism is key to training models at massive scale, this suggests a potential inherent weakness of the scaling paradigm.</abstract>
    <identifier type="citekey">merrill-sabharwal-2023-parallelism</identifier>
    <identifier type="doi">10.1162/tacl_a_00562</identifier>
    <location>
        <url>https://aclanthology.org/2023.tacl-1.31</url>
    </location>
    <part>
        <date>2023</date>
        <detail type="volume"><number>11</number></detail>
        <extent unit="page">
            <start>531</start>
            <end>545</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Journal Article
%T The Parallelism Tradeoff: Limitations of Log-Precision Transformers
%A Merrill, William
%A Sabharwal, Ashish
%J Transactions of the Association for Computational Linguistics
%D 2023
%V 11
%I MIT Press
%C Cambridge, MA
%F merrill-sabharwal-2023-parallelism
%X Despite their omnipresence in modern NLP, characterizing the computational power of transformer neural nets remains an interesting open question. We prove that transformers whose arithmetic precision is logarithmic in the number of input tokens (and whose feedforward nets are computable using space linear in their input) can be simulated by constant-depth logspace-uniform threshold circuits. This provides insight on the power of transformers using known results in complexity theory. For example, if LʼneqP (i.e., not all poly-time problems can be solved using logarithmic space), then transformers cannot even accurately solve linear equalities or check membership in an arbitrary context-free grammar with empty productions. Our result intuitively emerges from the transformer architecture’s high parallelizability. We thus speculatively introduce the idea of a fundamental parallelism tradeoff: any model architecture as parallelizable as the transformer will obey limitations similar to it. Since parallelism is key to training models at massive scale, this suggests a potential inherent weakness of the scaling paradigm.
%R 10.1162/tacl_a_00562
%U https://aclanthology.org/2023.tacl-1.31
%U https://doi.org/10.1162/tacl_a_00562
%P 531-545

Markdown (Informal)

[The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://aclanthology.org/2023.tacl-1.31) (Merrill & Sabharwal, TACL 2023)

• The Parallelism Tradeoff: Limitations of Log-Precision Transformers (Merrill & Sabharwal, TACL 2023)

ACL

• William Merrill and Ashish Sabharwal. 2023. The Parallelism Tradeoff: Limitations of Log-Precision Transformers. Transactions of the Association for Computational Linguistics, 11:531–545.