Official Review · ICLR 2024

This manuscript studies the ability of transformers to reason with abstract binding --- or symbol binding. The authors contrast MLPs and transformers and argue how MLPs trained with gradient descent are incapable of abstract reasoning. They then show how transformers on the other hand are capable of abstract reasoning given lots of data. Finally, they propose an a transformer variant that generalizes faster to the symbol binding task and verify the same empirically. The paper was a great read! The authors conduct a thorough theoretical analysis with practical insights suggesting changes to the transformer architecture. The work studies if transformers are capable of symbol binding, which is very important question and of broad interest to the community. The paper presents a diverse set of results, but makes them easy to understand to a broader audience too. The template tasks are elegant and easy to understand. It grounds the problem in a concrete scenario that can be studied. The authors present concrete insights for real labels and symbolic labels and identify different sample complexity behaviors for both scenarios. The work identifies important factors like data diversity or transformer embedding size that change the convergence behavior. The authors use their theory to develop practical insights for developing transformer architectures. In particular, they show experiments on a synthetic dataset and on Wikitext to validate their proposed modification. The theory for the transformers seems to rely on training only the final layer of the transformer. Does that mean that there are other architectures that can also do symbol binding? It is unclear which aspect of transformers are important for symbol binding: is the attention, the MLP, the invariance properties or something else? It isn't entirely clear to me how A limitation of most theory that uses the PAC framework often has vacuous bounds. While the paper derives asymptotic trends, it is unclear if they will predictive of what happens in practice as a result. However, I also acknowledge that this is the case for lot of theorems about deep networks. It is unclear if this probabilistic framework is the right tool for analysis. 1. The proof for the failure of MLPs relies on taking an expectation over $\theta_t$ obtained through gradient descent. Does this also hold for a single run of an MLP training. Is it possible for MLPs to converge some of the time (and not with probability at least $1 - \delta$ )? 2. The proof seems to rely on the kernel ridge regression estimator. Does this mean that representation learning is not critical for symbol binding? 3. If the data diversity is small (data follows a Zipf distribution), then do these results hold? In practice we expect datasets to follows such distributions and I am unsure if I am misunderstanding the theorem incorrectly. 4. Are there technical reasons for using the kernel regression with gradient flow in section 4, but the cross-entropy