Введение

Эта статья про мои эксперименты с языковыми моделями, в которых не используется машинное обучение и аппаратное ускорение. Чтобы избежать недопонимания поясню, что я имею ввиду под языковой моделью (ЯМ).

ЯМ это совокупность алгоритмов, структур данных и собственно данных для генерации связного текста в ответ на запрос. Каким образом ЯМ генерирует ответы определяется способом её реализации. В канонической реализации ЯМ используются методы машинного обучения и мощные аппаратные ускорители. В моей реализации ЯМ я хочу получать связный текст в ответ на запрос без машинного обучения и без аппаратного ускорения.

Если свериться с Википедией на английском и на русском языках, или с многочисленными публикациями про (Large/Small) Language Models, то мои определение и понимание… несколько неканонические. Поскольку я экспериментирую для себя (я сам себе работодатель), то заранее соглашусь с любыми мнениями о неканоничности моего определения ЯМ.

Буду благодарен комментариям — если окажется, что подобное изложенному в этой статье уже было на просторах интернета. Как минимум такие подсказки избавят меня от хождения по тупикам. А как максимум, я надеюсь, позволят сделать мои дальнейшие эксперименты более успешными.

Последующий текст состоит из нескольких небольших частей. Сначала расскажу о своих мыслях, из которых возникли мои идеи для экспериментов. Далее, о своём текущем подходе к реализации ЯМ. Пока он совсем прост. Чем‑то напоминает классический подходы Markov chains и n‑grams, но без статистических и вероятностных методов.

Продолжу коротким изложением и анализом результатов экспериментов. И в заключение поделюсь планами на будущее.

Для понимания содержимого статьи достаточно знаний в объёме 3 курсов Университета ИТМО (кафедра КТ) или аналогичной учебной программы.

Мотивация

Я люблю читать русскую классику. И мне очень хочется с помощью ЯМ создать и прочесть продолжение «Бесов» Ф.М.Достоевского. Спасти Анну Каренину от Л.Н.Толстого. Попросить А.П.Чехова написать рассказ‑другой по темам из соцсетей. Да и много ещё чего в том же духе. Те, кто читал «Код Онегина» или продолжение рассказа «Штабс‑капитан Рыбников», поймут о чем я.

В мозге Достоевского, Толстого, Чехова, Куприна, Салтыкова‑Щедрина, Набокова не было умножения тензоров, градиентного спуска, ускорителей от Nvidia, AMD и пр. Писателям (были) не нужны мегаватты энергии и терабайты тренировочных текстов для создания свои гениальных произведений.

Как же писатели это делали и делают? Я задумался о концепции ЯМ, которая могла бы превратить мои желания в реальность. Одно из основных моих предположений: качественные и эффективные языковые модели возможно сделать на сравнительно небольшом объёме текстов русской классической литературы. А не на терабайтах данных со всего интернета.

Структуры данных и алгоритмы ЯМ

Моя ЯМ использует структуры данных и алгоритмы С++ STL и исполняется на обычном x86 компьютере без аппаратных ускорителей. В ЯМ нет никаких токенизаций, тензоров, градиентных спусков, квантизаций, имбеддингов, энкодеров, декодеров, скрытых слоёв, латентных голов, GeGLU — ничего из жаргона и канонических технологий LLM & ML. С++ STL достаточно функциональна и эффективна для компактного хранения текстов без потерь и для их последующей обработки в ЯМ. Компактное хранение без потерь означает, что сохранённый текст в структурах данных может занимать меньше места по сравнению с исходным объёмом текста. Чем более избыточны исходные тексты и чем их больше, тем более компактным будет их внутреннее представление относительно входных данных.

ЯМ в качестве запросов принимает фразы и предложения, взятые из произвольного места исходных текстов. В ответ на запрос генерируется связный текст в виде комбинации предложений из сохранённых исходных данных.

В текущей реализации ЯМ на C++ STL скорость доступа к сохраненным данным по заданному запросу аппроксимируется O(M*log2(N)), где M это количество слов в запросе, а N это размер словаря для всех сохранённых текстов. Под словами понимаются последовательности символов из исходного текста, разделённые пробелами. Скорость генерации ответа на запрос оценивается O(K), где К это обобщённое обозначение внутренних констант алгоритма. Скорость генерации текста теоретически не зависит от размера заданного запроса, от размера сгенерированного ответа и от объёма исходных текстов.

ЯМ использует два основных алгоритма: алгоритм (1) сохранения входных текстов во внутренних структурах данных и алгоритм (2) генерации связного текста в ответ на запрос.

Алгоритм (1) сканирует входной текст и для каждого слова собирает информацию о следующих за ним словах — какие слова и на каком расстоянии (через сколько слов) следуют за текущим. Расстояние между двумя словами определяется как количество слов между этими двумя словами.

Например, при обработке предложений из текста «Мы идём домой. Мы идём в магазин. Мы остались дома.» алгоритм сканирования обнаруживает, что за словом «Мы» на расстоянии 0 дважды следует слово «идём» и один раз следует слово «остались». Также за словом «Мы» на расстоянии 1 следуют слова «домой.», «в» и «дома.». А слово «магазин.» следует за словом «Мы» на расстоянии 2.

Собранная таким образом для каждого слова информация сохраняется в двумерном массиве. В элементах строки массива хранится идентификатор слова, следующего за текущим. Индекс строки массива соответствует расстоянию до слов, сохранённых в элементах этой строки. Так, для слова «Мы» содержимое строки с индексом 0 в массиве может быть представлено в псевдо‑нотации языка С как {next_word(«идём»), next_word(«остались»)}. Содержимое строки с индексом 1 в массиве — {next_word(«домой.»), next_word(«в»), next_word(«дома.»)}, содержимое строки с индексом 2 в массиве — {next_word(«магазин.»)}. Обозначение next_word(word) — это функция, которая возвращает ссылку на структуру данных для слова.

Таким образом, для слова «Мы» содержимое двумерного массива из трёх строк целиком будет выглядеть так:

{
	{next_word(«идём»), next_word(«остались»)},
	{next_word(«домой.»), next_word(«в»), next_word(«дома.»)},
	{next_word(«магазин.»)}
}

Строки двумерного массива имеют переменную длину и могут быть представлены типом std::vector<>.

Для слова «идём» содержимое массива из трёх строк будет выглядеть так:

{
	{next_word(«домой.»), next_word(«в»)},
	{next_word(«Мы»), next_word(«магазин.»)},
	{next_word(«идём»), next_word(«Мы»)}
}

Обобщая в терминах C++ STL, эту структуру данных можно определить так:

enum { NEXT_MAX = 3 }; // количество строк элементов в двумерном массиве

struct next_word_t;// тип ссылки на слово, см. определение типа ниже
struct dict_word_t {
	std::vector<next_word_t> next[NEXT_MAX];// переменное число элементов в строке
};

Алгоритм (1) сохраняет слова из текста и собранную для них информацию в структуре данных kv‑store, которая обеспечивает быстрый поиск по слову в качестве key. Такая структура данных может быть определена в терминах C++ STL как:

struct words_dict_t: std::map<std::wstring, dict_word_t>{
};

В этом определении std::wstring — это слово из исходного текста, оно используется как ключ (key) для поиска. Объект типа dict_word_t — это значение (value), которое соответствует конкретному ключу.

Теперь можно определить тип next_word_t, форвардная декларация которого дана выше:

struct next_word_t {
	words_dict_t::iterator it; //iterator returned by words_dict_t::find(wstring);
};

Псевдокод алгоритма (1) в терминах C++ STL:

vector<wstring> words;
words_dict_t words_dict;

for (i = 0; i < words.size(); ++i) {
	dict_word_t &dict_word = words_dict[words[i]];
	for (j = 0; i + 1 + j < words.size() && j < NEXT_MAX; ++j)
		push_if_unique(dict_word.next[j], words_dict.find(words[i + 1 + j]);
}

В этом коде dict_word содержит ссылку на значение (value) для ключа words[i].
Функция push_if_unique() заполняет строку массива next[j] уникальными значениями next_word_t. То есть, значение next_word_t добавляется только в том случае если оно отсутствует в строке массива next[j]. Метод std::map::find() описан в документации C++ STL.

Псевдокод подразумевает что алгоритм (1) двухпроходный. В первом проходе, который ввиду тривиальности опущен, исходный текст сканируется и разбивается на отдельные слова. Эти слова заносятся в массив words. Также каждое слово word из исходного текста помещается в словарь words_dict в результате вызова words_dict_t::operator []:

words_dict[word] = dict_word_t();

Алгоритм (2) ЯМ использует все определённые выше структуры данных для генерации связного текста в ответ на запрос. В текущей реализации запрос к ЯМ это фраза или фрагмент из любого места исходного текста.

Например, для запроса «Мы идём домой.» алгоритм (2) выполнит следующие шаги. Для каждого слова запроса будет выполнен поиск в words_dict среди отсканированных слов из исходных текстов.

В результате поиска для каждого слова будет найден двумерный массив. Как мы помним в этом массиве собрана информация о словах, следующих за данным словом на разных расстояниях.

Используя собранную информацию однозначно определяется слово, которое следует за «домой.». Это слово «Мы».

Запрос модифицируется — отбрасывается первое слово запроса, и добавляется найденное слово в конец запроса. Новый запрос будет «идём домой. Мы». Далее вышеописанные шаги повторяются для модифицированного запроса. Эффективность работы алгоритма (2) может быть повышена кэшированием результатов поиска.

Повторение шагов происходит до тех пор пока возможно найти следующее слово для запроса.

Псевдокод алгоритма (2) в терминах C++ STL:

next_word_t prompt[NEXT_MAX];// запрос как входной параметр
words_dict_t words_dict;// словарь заполненный алгоритмом (1)
int pi = NEXT_MAX — 1;// индексирование элементов в запросе с последнего слова
vector<next_word_t> result = prompt[pi].it→second.next[0];
// предсказание следующего слова сразу после запроса
if (result.size() == 0)
	goto DONE;// нет данных для предсказания (в конце текста)
for (i = 1; i < NEXT_MAX; ++i) {// по словам от конца запроса к началу
	--pi;// индекс предыдущего слова в запросе
	const vector<next_word_t> &b = prompt[pi].it→second.next[i];
	if (b.size() == 0)
		goto DONE;//нет данных для предсказания (в конце текста)
	const vector<next_word_t> a = result;
	intersect_next_words(result, a, b);
}
auto next_word = result.begin();// предсказанное слово после запроса
push_back(prompt, next_word);
DONE:// прыгаем сюда если не удалось предсказать следующее слово

Функция intersect_next_words() возвращает массив слов которые могут следовать за двумя последовательными словами [pi] и [pi — 1] в запросе. Функция intersect_next_words() не использует вычисление вероятностей или каких-либо арифметических операций. Она сравнивает содержимое двух массивов и находит в них общие элементы, которые помещает в возвращаемых массив. Возвращаемый массив result в свою очередь используется как аргумент для этой функции на следующей итерации цикла. По завершению цикла for() или раньше в массиве result останется один элемент, который и будет использован как продолжение запроса.

Функция push_back() добавляет предсказанное слово в конец запроса и отбрасывает первое слово запроса.

Длина запроса в алгоритме (2) эффективно ограничивается константой NEXT_MAX. То есть, для предсказания следующего слова используется NEXT_MAX или меньше последних слов запроса. Для однозначности предсказания в текущей реализации ЯМ значение NEXT_MAX должно быть больше длины максимального повтора в тексте. Максимальный повтор — среди повторяющихся фраз, предложений или абзацев — определяется на этапе предварительного сканирования исходных текстов.

Эксперимент, входные данные ЯМ и обсуждение результата

Для своего первого эксперимента я выбрал создание продолжения романа «Бесы» Ф.М.Достоевского.

В качестве исходных данных для ЯМ в рамках этого эксперимента я использовал два набора исходных текстов:

1. великое пятикнижие Ф.М.Достоевского «Преступление и наказание», «Идиот», «Бесы», «Подросток» и «Братья Карамазовы»;

2. 15-томное собрание сочинений Ф.М.Достоевского, которое включает великое пятикнижие. Тексты из 15-томного набора были вручную разбиты на отдельные крупные произведения и были удалены комментарии к текстам.

Цель использование двух наборов данных — оценить эффективность выбранных структур данных и устойчивость работы алгоритмов ЯМ. Кратко статистика по наборам данных:

1. размер исходных текстов первого набора данных (source) 12246KB, размер структур данных ЯМ в RAM 150499KB, отношение RAM/source == 12.29;

2. размер исходных текстов второго набора данных (source) 30767KB, размер структур данных ЯМ в RAM 345535KB, отношение RAM/source == 11.23.

Из приведённой статистики видно что с увеличением размера исходных текстов эффективность структур данных ЯМ улучшается. Также статистика показывает, что для сравнительно маленьких размеров входных данных их представление в RAM занимает существенное место.

Запросом для ЯМ в эксперименте послужила фраза из начала главы первой части первой романа «Бесы»: «Приступая к описанию недавних». Альтернативные допустимые и работающие варианты запросов в рамках этого эксперимента — любые другие фразы из романа «Бесы».

Напомню, роман «Бесы» заканчивается так:

Ставрогин даже задрожал от гнева и почти от испуга.

— Проклятый психолог! — оборвал он вдруг в бешенстве и, не оглядываясь, вышел из кельи.

ЯМ сгенерировала длинное продолжение, которое начинается со слов:

Он не остановился и на крылечке, но быстро сошёл вниз. Полная восторгом душа его жаждала свободы, места, широты. Над ним широко, необозримо опрокинулся небесный купол, полный тихих сияющих звёзд...

Многоточие здесь заменяет довольно длинный сгенерированный текст, который я не привожу из‑за ограничений на размер статьи.

Наблюдательный читатель в этом продолжении узнает фрагмент текста из романа «Братья Карамазовы». Такое функционирование ЯМ ожидаемо. ЯМ всего лишь комбинирует фрагменты исходных текстов для генерации ответа на запрос.

Разумеется, в качестве входных данных для ЯМ можно использовать какие угодно тексты. Например, тексты статей про AI/LLM с сайта arXiv.org. Либо дистилляцию вопросов и ответов любой доступной LLM. Либо использовать представление исходных данных в виде «вопрос — ответ». Затем, соответственно, задавать запросы по соответствующей тематике. ЯМ точно также будет комбинировать фрагменты исходных данных для генерации ответов на запросы.

Обобщая полученный результат: чем больше объем исходных данных для ЯМ, тем сложнее будет казаться сгенерированный текст. Тем труднее с человеческой точки зрения будет обнаружить происхождение фрагментов в сгенерированном тексте. А значит, тем сильнее будет желание очеловечить ЯМ — воспринять работу машинных алгоритмов как проявление (Artificial) Intelligence.

Сравнение с каноническими LLM

Моя экспериментальная ЯМ не использует методов Machine Learning, тензорных вычислений, вычислений вероятностей и не требует аппаратного ускорения. При значительном увеличении объёма исходных тестов практическая производительность ЯМ будет зависеть от объема RAM, от скорости доступа к памяти, от промахов в кэшах, от заполнения конвейеров процессора, от скорости memory paging and swapping, major page fault latencies, etc.

М оя ЯМ работает в терминах слов и словосочетаний (n-grams), то есть предсказывает следующее слово на основе предыдущих NEXT_MAX n-grams. Примерно так же, с точностью до реализации, как работают Markov chains.

Алгоритмы ЯМ делают её функционирование объяснимым (explainable) без привлечения дополнительных сущностей — Intelligence, reasoning, emergent properties, and so on.
Из‑за отсутствия тензорных вычислений над слоями коэффициентов и отсутствия необходимости сжатия коэффициентов ЯМ не подвержена галлюцинациям в смысле канонических LLM. Однако ЯМ все же может генерировать несвязный текст, поскольку она лишь комбинирует фрагменты текстов из входных данных большого объёма. В использованной реализации ЯМ несвязности в тексте могут быть отлажены. То есть, ввиду сравнительной простоты используемых алгоритмов и структур данных, возможно обнаружить какие именно исходные тексты приводят к несвязности сгенерированного текста. И соответственно изменить внутренние параметры ЯМ для получения более связного или более «разумного» ответа на запрос.

В ЯМ отсутствует понятие длины контекста. Запрос большого размера сканируется алгоритмом (1) также как и любой входной текст, в реальном времени. В результате все слова и и отношения следования слов из такого запроса будут помещены во внутренние структуры данных ЯМ. После чего ЯМ генерирует ответ на запрос.

Для генерации ответа на запрос не требуется огромная дополнительная память, то есть не требуется аналога «kv‑cache».

Заключение и планы на ближайшее будущее

Моя ЯМ использует эффективную реализацию идей цепей Маркова и n-grams в терминах STL C++. ЯМ сначала определяет зависимости каждого слова от предшествующих слов во входных текстах. Вычисления вероятностей при этом не требуется. Затем, на основе этой информации исходя из содержимого запроса (prompt) ЯМ предсказывает следующее слово и таким образом генерирует ответ на запрос. Цепи Маркова и n-grams достаточно хорошо описаны в Википедии и других источниках.

Это достаточно простые алгоритмы для обработки исходных текстов и для генерирования ответа на запрос. Причина простоты алгоритмов — их реализация на традиционной x86/ARM платформе, где есть строки переменной длины, массивы переменного размера, деревья, указатели и пр. Если те же самые алгоритмы переложить на аппаратный ускоритель, то... потребуется токенизация и представление слов в виде векторов, поскольку в ускорителях нет строк переменной длины. Потребуются тензоры и операции с ними, поскольку в ускорителях нет указателей и деревьев. Потребуется умножение векторов поскольку в ускорителях нельзя сравнить поэлементно два массива переменной длины. И тому подобное. И, как следствие, возникает необходимость в тяжеловесных машинном обучении и инференсе.

«Магия» моей ЯМ не в алгоритмах, а в исходных данных. Чем больше исходных данных и чем более они релевантны к предметной области (предполагаемым запросам), тем «умнее» будут казаться ответы ЯМ. Поэтому в моих планах прежде всего увеличение объёма исходных данных. Хочется практически оценить объем RAM в зависимости от объёма исходных данных, производительность ЯМ в IPC (Instructions per Cycle), CPU cache misses, etc. Убедиться, что с увеличением объёма хранимых и обрабатываемых данных все работает как задумано. Найти узкие места в алгоритмах и реализовать их более эффективно, насколько это возможно.

Следующий серьёзный шаг — сделать запросы нечёткими, то есть использовать достаточно произвольно составленную фразу для генерации продолжения этой фразы по сохраненным в ЯМ текстам.

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

Благодарности

Большое спасибо всем согласившимся прочитать черновик этой статьи. В особенности я благодарен следующим людям за ценные комментарии, вопросы и идеи:

• А.Дмитриев предложил повысить эффективность структур данных заменив 64-битные указатели на 32-битные индексы. Это будет очень актуально для огромных наборов входных данных;

• П.Кринов подсказал, что желательно добавить подробностей о сходстве и отличиях между предлагаемым подходом и цепями Маркова (n‑grams). Также для научной статьи (не для Habr) необходимы более формальная постановка проблемы, детальное сравнение с другими методами, анализ качества текста (типа BLEU‑score), кода или репозитория для повторения экспериментов;

• Б.Козак заметил, что NEXT_MAX может рассматриваться в определённом смысле как длина контекста, а алгоритм (1) ЯМ все равно можно считать вариантом ML. Также Б.Козак задал вопрос — как решить в рамках предлагаемой ЯМ проблему потери частоты для частых и редких вхождений слов при предсказании следующего слова. На последний вопрос я уже ответил в тексте выше. Поскольку этот вопрос часто задавали и другие читатели,то коротко повторю ответ здесь: моя ЯМ не использует частоты встречаемости слов из входных данных для генерации ответа на запрос.