Pith. sign in

REVIEW 2 cited by

Lower bounds on transformers with infinite precision

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 2412.20195 v1 pith:DUSVJ37Q submitted 2024-12-28 cs.LG cs.AIstat.ML

Alexander Kozachinskiy This is my paper · ORCID
classification cs.LGcs.AIstat.ML
keywords consideredinfinitelowerprecisiontransformersboundboundscomposition
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

In this note, we use the VC dimension technique to prove the first lower bound against one-layer softmax transformers with infinite precision. We do so for two tasks: function composition, considered by Peng, Narayanan, and Papadimitriou, and the SUM$_2$ task, considered by Sanford, Hsu, and Telgarsky.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

  1. Attention-based representations for multi-task computation

    cs.LG 2026-08 accept novelty 7.0 of 10

    For min/max readout, two attention heads beat one head by an exponential resource gap, and for n-bit parity and symmetric Boolean functions, heads times polynomial degree must reach the threshold degree, with matching...

  2. Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers

    cs.LG 2025-02 conditional novelty 7.0 of 10

    In the unique-hard-attention transformer model, chain-of-thought length must grow linearly with input size for parity, multiplication, median, and reachability.

Pith tools