讲座标题（中文）：浅谈神经网络在算法推理上的局限性
讲座标题（英文）：Understanding the Limitations of Neural Networks on Algorithmic Reasoning
讲座摘要：Deep learning has driven large foundation models to succeed in most cases, yet these models struggle with reasoning. In this talk, I will examine their ability on algorithmic reasoning — the ability to perform reasoning following an algorithm.
The first part of the talk is about a surprising "grokking" phenomenon when training a neural net on certain algorithmically generated datasets: the neural net first “memorizes” the training set, resulting in perfect training accuracy but near-random test accuracy, and after training for sufficiently longer, it suddenly transitions to perfect test accuracy. We exemplify in simple yet insightful settings that a dichotomy of early and late phase implicit biases makes grokking provably occur.
The second part of the talk is about how the architecture of language models limits their reasoning ability. We focus on inference with Chain-of-Thought (CoT), a standard technique to improve reasoning by outputting intermediate steps. While previous results show that Transformers with CoT have sufficient representation power to simulate Turing machines, we prove that, even with CoT, modern RNNs cannot reach the same power, although they have been increasingly popular due to their higher efficiency. We further show that a key bottleneck lies in the inability of RNNs to perfectly retrieve information from the context, but adding just a single Transformer layer can fix this issue.
讲者信息：Kaifeng Lyu will be joining the Institute for Interdisciplinary Information Sciences (IIIS) at Tsinghua University as an Assistant Professor in the fall of 2025. His primary research interests include machine learning theory, AI safety/alignment, and optimization. Kaifeng Lyu graduated from Yao class at Tsinghua University in 2019. He is currently a final-year PhD student at Princeton University, advised by Prof. Sanjeev Arora.
rotartsinimdA