REVIEW 1 cited by
Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers
Not yet reviewed by Pith; the record is open.
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
abstract
Deriving formal bounds on the expressivity of transformers, as well as studying transformers that are constructed to implement known algorithms, are both effective methods for better understanding the computational power of transformers. Towards both ends, we introduce the temporal counting logic $\textsf{K}_\text{t}$[#] alongside the RASP variant $\textsf{C-RASP}$. We show they are equivalent to each other, and that together they are the best-known lower bound on the formal expressivity of future-masked soft attention transformers with unbounded input size. We prove this by showing all $\textsf{K}_\text{t}$[#] formulas can be compiled into these transformers.
Forward citations
Cited by 1 Pith paper
-
From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP
Embedding a narrow C-RASP teacher into a wider quantized Transformer yields sample complexity O((L d log Q)/ε) under posterior sampling of zero-training-error models.
Discussion (0). Continue with ORCID to comment.