Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
IASCAR: Incremental Answer Set Counting by Anytime Refinement
Answer set programming (ASP) is a popular declarative programming paradigm with various applications. Programs can easily have many answer sets that cannot be enumerated in practice, but counting still allows quantifying…
NoPE: The Counting Power of Transformers with No Positional Encodings
Positional Encodings (PEs) seem to be indispensable for ensuring expressiveness of transformers; without them attention transformers reduce to a bag-of-word model. NoPE-transformers (i.e. with No PEs) with unique hard at…
Hard AttentionTransRAC: Encoding Multi-scale Temporal Correlation with Transformers for Repetitive Action Counting
Counting repetitive actions are widely seen in human activities such as physical exercise. Existing methods focus on performing repetitive action counting in short videos, which is tough for dealing with longer videos in…
Repetitive Action CountingCounting Cells in Time-Lapse Microscopy using Deep Neural Networks
An automatic approach to counting any kind of cells could alleviate work of the experts and boost the research in fields such as regenerative medicine. In this paper, a method for microscopy cell counting using multiple …
Counting Ability of Large Language Models and Impact of Tokenization
Transformers, the backbone of modern large language models (LLMs), face inherent architectural limitations that impede their reasoning capabilities. Unlike recurrent networks, Transformers lack recurrent connections, con…