ОБ ОГРАНИЧЕНИЯХ АРХИТЕКТУРЫ TRANSFORMER

1. Введение

Архитектура Transformer [VSP+17], будучи в целом исключительно перспективным подходом к ИИ, известна тем, что страдает от проблемы «галлюцинаций»: ответы на запросы пользователя слишком часто оказываются несовместимыми с данными обучения и/или самим запросом. Сегодня существует обширная литература о галлюцинациях, их природе, типологии и способах уменьшения; см., например, обзор [JLF+23].

Существуют ли первопричины феномена галлюцинаций, которые можно отнести непосредственно к архитектуре Transformer? Теоретические ограничения Transformers отмечались и ранее: начиная с работы Hahn 2020 года [Hah20], где было доказано, что Transformers не способны распознавать некоторые простые шаблоны, такие как чётность (например, содержит ли фраза чётное число отрицаний) или сбалансированные скобки. Однако элегантные доказательства [Hah20], вдохновлённые теорией вычислительной сложности, являются асимптотическими; по-видимому, выявленные ограничения проявляются лишь на нереалистично больших входах. Более того, было показано, что существуют Transformers, которые вычисляют эти функции надёжно для всех практически значимых размеров [EGZ20, YPPN21]. Transformers также исследовались через призму теории сложности — важного инструмента для понимания пределов вычислительных систем — кульминируя в работе [MS23b], где показано, что с вычислительной точки зрения Transformers принадлежат довольно слабому классу, а именно logspace-uniform TC0; мы вернёмся к этому в разделе 4.

Также недавно Sanford, Hsu и Telgarsky [SHT23] выделили конкретную математическую задачу, называемую 3-Matching, которую не может вычислить однослойный много-головочный Transformer: по заданной последовательности целых чисел требуется найти три числа, сумма которых равна нулю по модулю заданного большого числа. Интересно, что (a) более простая задача 2-Matching решается Transformer-ами, но не решается глубокими полносвязными сетями, что демонстрирует своего рода превосходство Transformers над некоторыми другими ML-архитектурами; и (b) отрицательные результаты проявляются уже при относительно малых размерах подсказки (prompt). Отметим, что, несмотря на концептуальную значимость, 3-Matching — не самый убедительный пример задач «целевого назначения» Transformer-архитектуры. Возникает вопрос: можно ли выделить невозможные задачи, более близкие к предполагаемому семантическому использованию LLM? Именно на этом мы и сосредоточены. Мы показываем новое фундаментальное ограничение Transformer-архитектуры: серьёзные трудности с вычислением очень простой и практически важной семантической операции, которую мы называем композицией функций.

В недавней работе о галлюцинациях [GLL+24] вводный пример — неверный ответ на вопрос: what is the birthday of Frederic Chopin’s father?, когда в подсказку были включены два факта: (a) Frederic Chopin’s father is Nicholas Chopin; (b) Nicholas Chopin was born on April 15, 1771. Это пример композиции функций, где компонуются функции birthday-of и father-of. Примечательно, что далее [GLL+24] предлагает «дооснащать» Transformers графами знаний — именно тем инструментом, который естественным образом реализует композицию функций, — чтобы уменьшить галлюцинации. Ещё один пример композиции функций: по фактам London is in the UK, Alan Turing was born in London (и др.) спросить: In which country was Turing born?. Или, получив генеалогию Матфея [Mat] вида Abraham was the father of Isaac, Isaac was the father of Jacob, … и так далее ещё 39 предложений такого же типа, спросить: did Isaac have any grandchildren?.

Существует трагическое совпадение: великий романтический композитор Фредерик Шопен на протяжении своей короткой жизни страдал от галлюцинаторных эпизодов…

Помимо критической роли в объединении реляционной информации в данных, композиция функций является важным компонентом понимания языка — ключевой компетенции Transformers. В прагматике indexicals — это слова, ссылающиеся на сущности в контексте высказывания. Например, I have a brother and his name is John или this dog has style включают indexicals (his, this). Если же один indexical ссылается на другой, то понимание высказывания требует композиции функций.

Understanding what the final word it refers to in this statement requires composing two indexicals: first recognizing that the indexical it points to “this shortcoming,” and then that “this shortcoming” refers to the specific deficiency that sometimes makes Transformers “hallucinate.” It seems relatively easy for humans to “compose” indexicals — but how about Transformers?

Итак, желательно — а по сути важно — чтобы LLM надёжно выполняли композицию функций. В этой работе мы доказываем, что они не могут: композиция функций является врождённой слабостью Transformer-архитектуры. В частности, мы показываем, что один слой много-головочного внимания не может вычислять ответ на запрос композиции функций с существенной вероятностью успеха, если размер области определения достаточно велик и выполняется неравенство, выводимое в теореме 1.

2. Предварительные определения

2.1. Формальная модель слоя внимания

Чтобы математически моделировать вычисления в Transformers, мы слегка адаптируем стандартную формальную модель. Слой внимания (self-attention unit) — это функция \(A:(\mathbb{R}^D)^N \to (\mathbb{R}^d)^N\), где \(N\) — длина подсказки (число токенов), \(D\) — размерность входного представления токена, \(d\) — размерность выходного эмбеддинга. Для одной головы внимания задаются три матрицы \(K, Q, V \in \mathbb{R}^{d\times D}\) (keys, queries, values). Для простоты предполагаем одинаковые размерности для \(K,Q,V\).

Пусть вход \(X=(x_1,\dots,x_N)\in(\mathbb{R}^D)^N\). Тогда для каждого \(i=1,\dots,N\) self-attention вычисляет выход:

Мы предполагаем конечную точность вычислений: вычисления self-attention выполняются с точностью p бит. Много-головочный слой \(L\) содержит \(H\) self-attention блоков с общим входом и объединяющую функцию \(\Phi\), которая по каждому \(i\) отображает \(H\) выходов в выходной токен в \(\mathbb{R}^d\). Наконец, Transformer — это каскад нескольких таких слоёв.

Замечание: в этой формализации мы игнорируем некоторые элементы оригинальной архитектуры (например, embedding, а также pre-/post-processing токенов через feed-forward сети), но это не влияет на корректность аргумента: embedding и pre-processing можно «поглотить» во входные токены, а post-processing — включить в \(\Phi\).

2.2. Задача композиции функций

Определим задачу композиции функций. Рассмотрим две функции: \(g\), отображающую домен \(A\) в домен \(B\), и \(f\), отображающую \(B\) в домен \(C\). Например, \(g(a)\) может быть «mother of person \(a\in A\)», а \(f(b)\) — «profession of person \(b\in B\)». Эти функции описываются подсказкой \(X\). \(N\) токенов \(X\) делятся на три части:

• Part 1. Первая часть описывает \(g\) через \(|A|\) предложений на простом, однозначном языке (разделённых пунктуацией), например: the mother of John is Helen; the mother of Charlotte is Eve; etc.
• Part 2. Вторая часть состоит из \(|B|\) предложений, описывающих \(f\), например: Helen is a doctor; Jane is a teacher; etc.
• Part 3. Запрос (query), например: what is the profession of John’s mother?²

² Можно считать, что предложения приходят именно в таком порядке, но доказательству это не требуется.

Заметим, что число входных токенов \(N\) — это небольшой множитель размера доменов функций. Мы говорим, что \(H\)-головочный слой Transformer \(L\) вычисляет композицию корректно, если для любой подсказки в правильном формате выход слоя, соответствующий токену запроса (в примере — токену John), является правильным ответом на запрос композиции. В основной части статьи также вводятся близкие задачи (итерированная композиция, достижимость), являющиеся простыми расширениями определения.

2.3. Обозначения информационной теории

Мы используем стандартные обозначения: энтропия \(H(\cdot)\), взаимная информация \(I(\cdot;\cdot)\), условная взаимная информация \(I(\cdot;\cdot\mid\cdot)\), а также неравенство Фано и др. Обозначим \(\ln(\cdot)\) как натуральный логарифм, а \(\log(\cdot)\) — логарифм по основанию 2.

3. Невозможность композиции

Мы докажем следующее утверждение.

Теорема 1. Рассмотрим задачу композиции функций с размерами доменов \(|A|=|B|=|C|=n\), и \(H\)-головочный слой Transformer \(L\) с размерностью эмбеддинга \(d\) и точностью вычислений \(p\). Предположим, что \(H(d+1)p \lt n\log n\). Тогда \(L\) не может корректно решать задачу композиции функций. В частности, если \[ R = n\log n - H(d+1)p \gt 0, \] то вероятность (по всем возможным функциям и запросам), что \(L\) ответит неверно, не меньше \[ \frac{R}{3n\log n}. \]

Доказательство опирается на коммуникационную сложность [KN96], раздел теории сложности, где измеряется число бит, необходимых для обмена между распределёнными агентами, имеющими разные части входа, чтобы один из них получил результат вычисления. Агентов считают вычислительно неограниченными и ограниченными только коммуникацией.

Классический пример — set disjointness: если у Боба и Алисы есть по \(n\) бит и они хотят определить, есть ли индекс \(i\), где оба бита равны 1, то им нужно передать \(\Theta(n)\) бит (этот факт используется и в невозможностных доказательствах в [SHT23]). Другая классическая задача — pointer chasing: у Алисы и Боба есть функции \(A,B:[n]\to[n]\), и нужно вычислить композицию вида \(A(B(A(B(A(0)))))\). Это легко делается, если агенты по очереди передают друг другу \(\log n\) бит, сообщая значение указателя; но если уменьшить число раундов на 1 или поменять, кто начинает, известны экспоненциальные нижние оценки по переданным битам (начиная с [PS82]), которые применялись в разных областях сложности, включая bounded-depth circuits ([KN96]) и даже Machine Learning ([CPP22]).

Здесь мы используем слегка иной вариант. Рассмотрим трёх агентов: Faye, Grace, Xavier. Faye знает функцию \(f:[n]\to[n]\), Grace — функцию \(g:[n]\to[n]\), а Xavier знает число \(x\in[n]\) (можно считать, что Faye и Grace тоже знают \(x\)). Разрешена только коммуникация к Xavier (от Faye и Grace), но не между Faye и Grace. Цель — чтобы Xavier узнал \(f(g(x))\), при этом мы минимизируем число бит, отправляемых от Faye к Xavier. (Коммуникация от Grace к Xavier не ограничивается.)

Лемма 1. Если Faye передаёт Xavier меньше, чем \(n\log n\) бит, то Xavier не может узнать \(f(g(x))\). В частности, если от Faye к Xavier передано лишь \(n\log n - R\) бит (для некоторого \(R\gt 0\)), то вероятность (по всем парам функций), что композиция вычислена неверно, не меньше \[ \frac{R}{3n\log n}. \]

Доказательство. Первая часть (качественная) элементарна. Поскольку Grace и Faye не могут общаться, а коммуникация от Grace к Xavier «бесплатна», можно считать, что Grace просто сообщает Xavier значение \(g(x)\) — это всё, что ему от неё нужно. Теперь Xavier должен применить \(f\) к \(g(x)\), но о \(f\) он ничего не знает. Значит, необходима коммуникация от Faye. Существует \(n^n\) возможных функций \(f\), и чтобы описать конкретную \(f\), Faye требуется как минимум \(n\log n\) бит (логарифм по основанию 2 от \(n^n\)); причём \(n\lceil\log n\rceil\) бит достаточно, чтобы просто передать значения \(f(0),f(1),\dots\). Если же Faye отправляет \(B \lt n\log n\) бит, то этим она разбивает \(n^n\) функций на \(2^B\) классов. Так как \(2^B \lt n^n\), по принципу Дирихле найдутся \(f\neq f'\), дающие одно и то же сообщение. Эти функции различаются хотя бы в одной точке \(z\): \(f(z)\neq f'(z)\). Если окажется, что \(g(x)=z\), то Xavier не сможет узнать правильный ответ.

Количественная часть использует информационную теорию и взаимную информацию.³ Рассмотрим случай, когда вход Grace — случайное отображение \(g:[n]\to[n]\) при фиксированном \(x\). Пусть \(i^*=g(x)\), тогда \(i^*\) равномерно распределён по \([n]\). Обозначим через \(\Pi\) сообщение от Faye к Xavier длины \(n\log n - R\) бит. Оценим взаимную информацию между \(\Pi\) и \(f(i^*)=f(g(x))\):

Выход Xavier — это post-processing \(\Pi\) и \(i^*\). Обозначим через \(\delta\) вероятность ошибки. По неравенству Фано:

Из (3) следует нижняя граница \(\delta \ge \dfrac{R}{3n\log n}\).

³ Строго говоря, вторая (количественная) часть леммы имплицирует первую; однако простое доказательство первой части приведено для наглядности.

Замечание 1. Нижняя граница \(\dfrac{R}{3n\log n}\) оптимальна с точностью до небольшой константы: существует схема, достигающая ошибки порядка \(\dfrac{1}{n}\left\lceil \dfrac{R}{\log n}\right\rceil\) (при \(n\) — степени двойки), если Faye кодирует первые \(n-\left\lceil \dfrac{R}{\log n}\right\rceil\) значений функции.

Теперь перейдём к доказательству теоремы 1. Предположим от противного, что существует слой self-attention \(L\), который надёжно компонует любые \(f\) и \(g\) на любых доменах \(A,B,C\) размера \(n\) при условии \(n\log n \gt H(d+1)p\). Покажем, что это противоречит лемме 1.

Пусть агенты Faye, Grace, Xavier такие же, как в лемме, и хотят вычислить \(f(g(x))\). Они составляют подсказку для задачи композиции, которую должен решить \(L\): Faye поставляет токены, описывающие \(f\) (например, «value of \(f\) applied to 0 is 3», и т.п.), Grace — токены, описывающие \(g\), а Xavier — query-часть: «what is the result of \(f\) applied to \(g\) applied to 23?», где \(x=23\). Пусть токен, соответствующий 23, — это токен \(t\) (то есть \(x_t=23\)). Тогда агенты вычисляют результат работы \(L\), соответствующий токену \(t\); по предположению о корректности композиции, этот результат должен быть равен \(f(g(x))\).

3.2. Сведение слоя внимания к протоколу

Для каждой головы внимание в позиции \(t\) имеет вид:

Ключевое наблюдение: (4) можно записать как \[ y_t=\frac{F+G+X}{F'+G'+X'}, \] где \(F\) — часть числителя, соответствующая токенам Faye, \(G\) — часть, соответствующая токенам Grace, \(X\) — часть, соответствующая токенам Xavier (и аналогично \(F',G',X'\) для знаменателя). Следовательно, Faye может вычислить и сообщить Xavier величины \(F\) и \(F'\) (вектор размера \(d\) и скаляр), Grace — \(G\) и \(G'\), после чего Xavier добавляет \(X\) и \(X'\), делит и тем самым вычисляет \(y_t\) для данной головы. Повторяя это для всех \(H\) голов и применяя \(\Phi\), Xavier получает \(f(g(x))\).

Но теперь заметим: это достигается передачей от Faye к Xavier лишь \(H(d+1)p\) бит (\(dp\) бит на \(F\) и \(p\) бит на \(F'\) для каждой из \(H\) голов). По гипотезе \(H(d+1)p \lt n\log n\), что противоречит лемме 1. Количественная часть по вероятности ошибки следует из того же сведения. Теорема 1 доказана.

Замечание 2. Вероятностная часть предполагает, что \(f\) — равномерно случайная функция \([n]\to[n]\). Для отрицательных результатов некоторое вероятностное предположение необходимо: например, если \(f(x)=a\) для всех \(x\), требуется существенно меньше бит. Результат расширяем на другие распределения, заменяя \(n\log n\) на энтропию \(f\).

Замечание 3. Из доказательства видно, что \(g\) играет минимальную роль: значение \(g(x)\) передаётся Xavier «бесплатно». Можно считать, что доказана невозможность вычисления произвольной функции \(f\). Аналогичный аргумент работает для промптов вида: ...where was Einstein born?, если ответ должен появиться строго в позиции токена.

3.3. Chain of Thought

Может ли CoT помочь решить задачу композиции? Интуитивно — да. Для конкретной композиции (например, для примера про Turing/London/England) можно дать короткий CoT, разбивающий задачу на шаги: Let’s see, Turing was born in generate, and generate is in the country of generate, so Turing was born in generate. Однако ниже мы доказываем, что для обобщения композиции на множество последовательных применений функций требуется произвольно большое число CoT-шагов.

В задаче итерированной композиции функций заданы \(K\) функций \(f_1,f_2,\dots,f_K\), и нужно вычислить \(f_K(f_{K-1}(\dots(f_1(x))\dots))\) для \(x\in[n]\). В доказательстве мы рассматриваем частный случай \(f^{(K)}(x)=f(f(\dots f(x)\dots))\), то есть \(f_1=\cdots=f_K=f\).

Теорема 2. Пусть \(H\) — число голов, \(d\) — размерность эмбеддинга, \(p\) — точность вычислений, а \(n\) — размер домена задачи итерированной композиции. Тогда слой Transformer требует \[ \Omega\!\left(\sqrt{\frac{n}{Hdp}}\right) \] CoT-шагов, чтобы корректно отвечать на промпты итерированной композиции.

Доказательство (идея). Сведение идёт от классической задачи коммуникационной сложности pointer chasing. В \((n,c)\)-pointer chasing Алиса знает функцию \(f_A:[n]\to[n]\), Боб — \(f_B:[n]\to[n]\). Указатели \(w(1),w(2),\dots\) задаются рекурсивно:

Коммуникация идёт \(2r\) раундов (начинает Алиса), цель — вывести бит \(w(2r+2)\bmod 2\). Известно (лемма 2, [NW91, Kla00, Yeh20]), что любой рандомизированный протокол с ошибкой \(\le 1/3\) под равномерным распределением должен передать не меньше \(n/(2000c) - 2c\log n\) бит.

Далее (лемма 3) показывается: если существует слой \(L\), решающий \(K\)-итерированную композицию за \(R\) CoT-шагов, то можно построить протокол для \((n,K-1)\)-pointer chasing, работающий за \(2R\) раундов и обменивающийся \(2R\cdot H(d+1)p\) бит. Подбором параметров получается противоречие с нижней оценкой pointer chasing, что завершает доказательство теоремы 2.

4. Композициональность и логарифмическая память

В [DLS+23] выделен новый жанр галлюцинаций: эксперименты показывают, что Transformers плохо справляются с compositionality tasks, то есть задачами, требующими многократного повторения элементарных операций; сходные явления отмечались и в других работах [MS23b, FGZ+23, MS23a]. Примеры из [DLS+23]: умножение многозначных чисел, задачи динамического программирования («+» и «max»), логические головоломки типа Zebra Puzzle.

Примечание: несмотря на лингвистическую близость терминов “composition” (в разделе 3) и “compositionality” из [DLS+23], это разные понятия. “Compositionality” — широкая неформальная категория; “function composition” — конкретное математическое понятие.

Чтобы понять, почему такие задачи могут быть фундаментально трудны для Transformers, мы переходим к вычислительной сложности [Pap93, AB09] и рассматриваем базовые вычислительные проблемы, лежащие в основе compositionality tasks: вычисление схем, достижимость (reachability/derivability), а также SAT-подзадачи (2-SAT, Horn-SAT, Mod 2 SAT).

Наблюдение 1. Вычисление многослойного Transformer на подсказке длины \(N\) можно выполнить, используя \(O(\log N)\) бит памяти.

Это согласуется с результатом [MS23b] (log-uniform TC0). Интуитивно, вычисление одного слоя внимания — это два внешних цикла по \(i\) и \(j\), с вложенными циклами по координатам и приближённым вычислением экспоненты; индексы и частичные суммы требуют лишь \(O(\log N)\) бит. Для нескольких слоёв выходы можно не хранить целиком, а пересчитывать при необходимости (обмен «время-память»).

Следовательно, вычисление многослойного Transformer принадлежит классу сложности \(L\) (logarithmic space). Наряду с гипотезой \(P\ne NP\) широко принимается гипотеза \(L\ne NL\), и ряд задач (2-SAT, reachability) являются \(NL\)-полными; circuit evaluation и Horn-SAT — \(P\)-полны.

Теорема 3. Четыре задачи: Derivability (Reachability), 2-SAT, Horn-SAT и Circuit evaluation не могут быть решены многослойными Transformers, если только \(L=NL\). Для Horn-SAT и Circuit evaluation результат верен, если только не выполняется более сильное равенство \(L=P\). Для Mod 2 SAT результат верен, если только не выполняется более слабое равенство \(L=\mathrm{Mod}\;2\;L\).

Мы считаем, что эта теорема помогает объяснить недостатки Transformers, выявленные в [DLS+23], учитывая близость указанных базовых задач к compositionality tasks и наблюдаемое ухудшение качества при росте глубины задачи.

5. Обсуждение

Мы использовали аргументы двух разных типов — коммуникационной и вычислительной сложности — чтобы прояснить некоторые недостатки Transformer-архитектуры, приводящие к различным типам галлюцинаций. Мы показали, что элементарная композиция функций не может быть решена одним слоем Transformer, а CoT может решать итерированную композицию лишь ценой генерации подсказки длины \(\Omega(\sqrt{N})\).

Эти результаты имеют оговорки: невозможность композиции относится к одному слою и является вероятностной, а результаты вычислительной сложности условны (зависят от широко принимаемых, но недоказанных гипотез) и асимптотичны. Тем не менее, как и в случае \(P\ne NP\), практические трудности часто проявляются уже на относительно малых размерах, что видно и в [DLS+23], и в примерах Приложения A.

«Трагедия» нижних оценок сложности не в их условности и асимптотичности, а в том, что (a) они редки и трудны, и существуют лишь в нескольких известных формах; и (b) часто они чрезмерно консервативны, переоценивая способности вычислительных агентов, границы которых пытаются очертить. Лемма 1 — пример: она остаётся верной даже если Grace использует сколь угодно сложную математику, чтобы закодировать вход в сообщение.

Наконец, два типа отрицательных результатов подсказывают вызов: что нужно, чтобы спроектировать иной слой «внимания», устойчивый к таким техникам нижних оценок, но сохраняющий практическую эффективность? Доказательство указывает на возможные варианты вычисления, которые либо некоммутативны/неассоциативны, либо требуют больше, чем логарифмическая память; однако «обход» техники нижней оценки сам по себе не гарантирует улучшение качества.

Благодарности. Мы признательны Fernando Pereira за идеи, вовлечённость и конструктивную критику на протяжении проекта. Также благодарим Olivier Bousquet за множество содержательных комментариев к ранней версии. Работа выполнена в период, когда третий автор был приглашённым исследователем в Google DeepMind (Цюрих). Работа первого и третьего авторов частично поддержана грантом NSF.

Appendix A. Examples

Below are qualitative examples illustrating the difficulty of composition for modern LLMs. A more comprehensive empirical study of compositional failures is given in [DLS+23]. The experiments are done on GPT-3.5, GPT-4 and Bard. We use prompts involving simple compositions of spatial, temporal and family relations. The experiments are done before 21 Jan 2024. We allow all models to reason step-by-step, but we show only the final answer; the answers are typical.

A.1. Spatial Composition

When prompts contain spatial information, transformer-based systems struggle with composition; see Figure 1.

A.2. Temporal Composition

Figure 2 shows two simple cases where temporal composition “breaks” and all models return wrong answers.

A.3. Family Composition

Wrong and “hallucinatory” answers also occur when prompts involve family composition; see Figure 3.