Summary of Universal Length Generalization with Turing Programs, by Kaiying Hou et al.
Universal Length Generalization with Turing Programs
by Kaiying Hou, David Brandfonbrener, Sham Kakade, Samy Jelassi, Eran Malach
First submitted to arxiv on: 3 Jul 2024
Categories
- Main: Machine Learning (cs.LG)
- Secondary: None
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary Length generalization in large language models refers to the ability to extrapolate from short training sequences to long test sequences. Prior work has proposed architecture or data format changes, but these are limited to specific tasks. This paper builds upon scratchpad and Chain-of-Thought (CoT) techniques by introducing Turing Programs, a novel CoT strategy that decomposes algorithmic tasks into steps mimicking the computation of a Turing Machine. This framework is both universal and simple, requiring only copying text from the context with small modifications. The authors demonstrate robust length generalization on various algorithmic tasks using Turing Programs, including addition, multiplication, and in-context SGD. They also show that transformers can achieve length generalization on random Turing Programs, suggesting that this capability is possible for any algorithmic task. Finally, the paper theoretically proves that transformers can implement Turing Programs, constructing a simple RASP program simulating an arbitrary Turing machine. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary This paper is about making computers better at understanding long sequences of information. Right now, they’re not very good at this, but the authors have come up with a new way to make them more powerful. They call it “Turing Programs,” and it’s based on an old idea called the Turing Machine. The authors show that their method can be used for lots of different tasks, like adding numbers or doing simple math problems. They also prove that computers can use this method to solve any problem that involves following a set of rules. This is important because it could help us make computers even more powerful and useful. |
Keywords
» Artificial intelligence » Generalization
