按年被提到
20222023 · 3 次2026
大模型与语言模型›模型表达力与计算理论·arXiv:2210.10749 · cs.LG

Transformers Learn Shortcuts to Automata

Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, Cyril Zhang · 2022
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2023-01-10 · 最近 2023-06-17
2不同的人
3活跃月份
3讨论串
30被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Algorithmic reasoning requires capabilities which are most naturally understood through recurrent models of computation, like the Turing machine. However, Transformer models, while lacking recurrence, are able to perform such reasoning using far fewer layers than the number of reasoning steps. This raises the question: what solutions are learned by these shallow and non-recurrent models? We find that a low-depth Transformer can represent the computations of any finite-state automaton (thus, any bounded-memory algorithm), by hierarchically reparameterizing its recurrent dynamics. Our theoretical results characterize shortcut solutions, whereby a Transformer with $o(T)$ layers can exactly replicate the computation of an automaton on an input sequence of length $T$. We find that polynomial-sized $O(\log T)$-depth solutions always exist; furthermore, $O(1)$-depth simulators are surprisingly common, and can be understood using tools from Krohn-Rhodes theory and circuit complexity. Empirically, we perform synthetic experiments by training Transformers to simulate a wide variety of automata, and show that shortcut solutions can be learned via standard training. We further investigate the brittleness of these solutions and propose potential mitigations.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论sinenomine · 2023-01

“Ironic, since the relatively recently discovered double descent makes it clear that bias-variance tradeoff as we know it from statistical learning theory simply doesn't apply to "overparameterized" deep models. Much of old theory is barely applicable and people are, understandably, bewildered and in denial. If someone were to be inclined to theory, I'd …”

Ask HN: What are the foundational texts for learning about AI/ML/NN?原评论 ↗
评论bmc7505 · 2023-06

“The current generation of LLMs will never generalize on problems whose expected complexity is significantly harder than the training set. One way to think of why this is the case is because transformers are learning shortcuts to multistep reasoning tasks [1, 2], but do not learn to reason systematically and unsurprisingly fail to generalize when presented…”

Researchers warn of ‘model collapse’ as AI trains on AI-generated content原评论 ↗
被提交为 story · 1 次