2 papers
cs.LG2025
Exact Expressive Power of Transformers with Padding
William Merrill, Ashish Sabharwal
Chain of thought is a natural inference-time method for increasing the computational power of transformer-based large language models (LLMs), but comes at the cost of sequential de…
cs.LG2025
A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
William Merrill, Ashish Sabharwal
Recent theoretical results show transformers cannot express sequential reasoning problems over long inputs, intuitively because their computational depth is bounded. However, prior…