Pith. sign in

REVIEW 3 cited by

Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2308.03212 v2 pith:N23I3SJ7 submitted 2023-08-06 cs.CL cs.CCcs.LG

Lena Strobl This is my paper · ORCID
classification cs.CLcs.CCcs.LG
keywords circuitsconstant-depththresholdtransformersuniformattentionaverage-hardlanguages
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

Transformers have emerged as a widely used neural network model for various natural language processing tasks. Previous research explored their relationship with constant-depth threshold circuits, making two assumptions: average-hard attention and logarithmic precision for internal computations relative to input length. Merrill et al. (2022) prove that average-hard attention transformers recognize languages that fall within the complexity class TC0, denoting the set of languages that can be recognized by constant-depth polynomial-size threshold circuits. Likewise, Merrill and Sabharwal (2023) show that log-precision transformers recognize languages within the class of uniform TC0. This shows that both transformer models can be simulated by constant-depth threshold circuits, with the latter being more robust due to generating a uniform circuit family. Our paper shows that the first result can be extended to yield uniform circuits as well.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A First-Principles Theory of Slow Thinking and Active Perception

    cs.AI 2026-07 conditional novelty 7.5 of 10

    Active lifting of data distributions via latent-sequence sampling and max-rate uncertainty reduction formally derives slow-thinking LLMs and places them on representation and sampler hierarchies that can be climbed.

  2. On the Ability of Transformers to Verify Plans

    cs.AI 2026-03 accept novelty 7.5 of 10

    Decoder-only transformers provably length-generalize on verifying plans in delete-free/well-formed domains via C*-RASP membership, but fail on general STRIPS and conditional effects.

  3. BAR Conjecture: the Feasibility of Inference Budget-Constrained LLM Services with Authenticity and Reasoning

    cs.LG 2025-07 reject novelty 2.0 of 10

    A purported impossibility theorem for LLM services reduces to the paper's own assumption that reasoning and authenticity necessarily consume extra inference budget.

Pith tools