Интересный апдейт в GPT-4

gpt-4-0613 is now available and adds a new capability: function calling. By describing functions in your prompts, the model can intelligently choose to output a JSON object containing arguments to call these functions based on user input — perfect for integrating with other tools or APIs. Learn more in our function calling documentation.

https://platform.openai.com/docs/guides/gpt/function-calling

[DeepMind AlphaDev] Faster sorting algorithms discovered using deep reinforcement learning
Daniel J. Mankowitz, Andrea Michi, Anton Zhernov, Marco Gelmi, Marco Selvi, Cosmin Paduraru, Edouard Leurent, Shariq Iqbal, Jean-Baptiste Lespiau, Alex Ahern, Thomas Köppe, Kevin Millikin, Stephen Gaffney, Sophie Elster, Jackson Broshear, Chris Gamble, Kieran Milan, Robert Tung, Minjae Hwang, Taylan Cemgil, Mohammadamin Barekatain, Yujia Li, Amol Mandhane, Thomas Hubert, Julian Schrittwieser, Demis Hassabis, Pushmeet Kohli, Martin Riedmiller, Oriol Vinyals & David Silver
Статья: https://www.nature.com/articles/s41586-023-06004-9
Пост: https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms
(Псевдо)код: https://github.com/deepmind/alphadev

Это в каком-то смысле продолжение истории про AlphaTensor (https://news.1rj.ru/str/gonzo_ML/1146). Там семейство алгоритмов AlphaZero применяли для поиска более быстрого алгоритма матричного умножения, а здесь его применили для поиска алгоритмов сортировки. Полученная система или агент, AlphaDev, нашла новый оптимизированный алгоритм сортировки. Код найденного алгоритма интегрировали в стандартную C++ библиотеку алгоритмов в LLVM (https://reviews.llvm.org/D118029). В этой части библиотеки не было изменений больше десятка лет и это там первый алгоритм, найденный RL. Делаем ставки, через сколько лет в libc++ не останется кода, написанного человеком.

Что интересно, работа эта не новая. Код в libc++ засабмитили ещё в начале прошлого года, а сама работа видимо сделана была и того раньше. В Nature статью засабмитили в июле 2022. AlphaTensor тоже, кстати, был засабмичен за год до самой статьи, ещё в октябре 2021.

Авторы фокусировались на алгоритмах для коротких последовательностей (3-5 элементов) и ищут функции для fixed sort (строго заданное количество элементов, 3, 4 или 5) и variable sort (любое количество элементов от нуля до 3-5). Поиск идёт на уровне ассемблерных инструкций (подмножество инструкций x86: mov/cmov/cmp/jump) с нуля, не с какого-то готового алгоритма. Как и AlphaTensor, AlphaDev основан на AlphaZero. Для использования RL задачу оформили в виде игры c одним игроком AssemblyGame (в случае AlphaTensor был TensorGame).

На каждом ходу AlphaDev смотрит на уже сгенерированный алгоритм (его репрезентацию P_t) и на состояние процессора (регистры и память, Z_t), и делает ход, выбирая инструкцию для добавления в алгоритм. Это делается через MCTS (Monte-Carlo Tree Search), которая по входному состоянию S_t = <P_t, Z_t> выдаёт полиси (распределение действий) и value function предсказывающую cumulative returns из текущего состояния. У value function две головы, одна для latency, другая для корректности.

Пространство решений здесь огромно, поэтому применялись правила для прунинга действий (типа, запрещены последовательные инструкции сравнения, ячейки памяти читаются строго в инкрементальном порядке, регистры аллоцируются также, и т.д.).

Также заявлено, что разрешены и другие трансформации типа перестановки двух инструкций, случайные замены опкода и/или операнда. Гиперпараметрами оптимизировали веса этих других трансформаций.

Алгоритм валидируется на тестовых кейсах, где его выход должен совпасть с эталонным, и вознаграждение агент получает за корректность и скорость (либо длину как прокси для latency) алгоритма.

Для вычисления репрезентации собрали отдельную сеть из двух энкодеров. Один генерит эмбеддинг алгоритма, второй эмбеддинг состояния процессора и памяти. Оба эмбеддинга затем объединяются в итоговую репрезентацию.

Эмбеддинг алгоритма делается трансформером Multi-Query Attention (в котором K и V шарятся между головами, https://arxiv.org/abs/1911.02150), 6 слоёв, 4 головы. Инструкции кодируются опкодом и операндами через one-hot и дают входную последовательность. В доп.материалах также описывается графовый энкодер через GNN.

Эмбеддинг состояния делается двуслойным MLP с relu, от состояния всех регистров и памяти.

Обучали на 16 ядрах TPUv3, миллион итераций с батчем 1024 на ядро. Актор работает на отдельном TPUv4, их было 512. Обучение во всех случаях заканчивалось не больше чем за два дня.

AlphaDev нашла более короткие варианты sort3 и sort5. Для VarSort длина алгоритма уже не очень показатель, потому что там бранчинг в коде, поэтому здесь меряли реальное время исполнения. Здесь тоже система нашла более быстрые решения.

По аналогии с “ходом 37” в го (неожиданный и нестандартный ход), алгоритм и здесь нашёл неожиданное решение, помогшее сэкономить одну инструкцию. Здесь это решение назвали ‘AlphaDev swap and copy moves’ (https://www.nature.com/articles/s41586-023-06004-9/tables/2).

Найденные алгоритмы перевели из ассемблера в C++ и добавили в LLVM libc++. Они быстрее имеющихся в библиотеке алгоритмов до 70% на коротких последовательностях, и примерно на 1.7% на последовательностях длиннее 250К элементов.

Для сравнения сделали версию AlphaDev-S со встроенным state-of-the-art stochastic superoptimization (https://theory.stanford.edu/~aiken/publications/papers/asplos13.pdf) решением для оптимизации функций сортировки. Обычный AlphaDev лучше исследует пространство решений (это называют Exploration hypothesis, её проверили через отображение исследованных пространств с помощью t-SNE), перебирая меньше вариантов, к тому же ему не надо каждый раз вычислять честную latency (у него есть предсказатель value function), что получается быстрее. AlphaDev-S может быть вычислительно более эффективным, если стартует не с нуля, а уже с хорошего решения недалеко от оптимума. Но для алгоритмов с бранчингом AlphaDev всё равно лучше.

Кроме сортировки применили AlphaDev на десериализацию VarInt из protobuf (нашли в три раза более быстрое решение), а также на одной задаче competitive coding из датасета CodeContests (тоже получилось быстрее).

В статье в Nature не нашёл (там только про теоретическую возможность), но в посте заявлено также что проверили AlphaDev на хешировании и там нашли алгоритм, который на 30% быстрее. Закоммитили его в abseil (https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7dcd2dbaa69b2c654596d8024e).

Что сказать, большое будущее (https://www.deepmind.com/blog/optimising-computer-systems-with-more-generalised-ai-tools) у такого направления как “ML for Systems” (http://mlforsystems.org/). В достаточную универсальность семейства алгоритмов AlphaZero я давно верю.

Неужели наконец AMD'шные GPU можно будет нормально использовать для deep learning'а? Даже не верится.

https://huggingface.co/blog/huggingface-and-amd

In the meantime, a discussion on AGI between Joscha Bach and Connor Leahy

Video: https://www.youtube.com/watch?v=Z02Obj8j6FQ
Podcast: https://podcasters.spotify.com/pod/show/machinelearningstreettalk/episodes/Joscha-Bach-and-Connor-Leahy-on-AI-risk-e25ukc5

Очередные слухи про устройство GPT-4:

Mixture model с 220B параметров x 8 экспертов, обученных на разные распределения задач и данных. И ещё почему-то делают 16 инференсов.

Вероятно к нынешнему моменту всё отдистиллировано.

https://twitter.com/soumithchintala/status/1671267150101721090?t=lKs8fcz_Nzlda4kiEQvDsw&s=19

Вспоминается эта безумная картинка, широко ходившая по сети в недалёком прошлом

:)