Эффективная управляемая генерация для больших языковых моделей: итеративная обработка и индексирование конечного автомата

Таблица ссылок

• Аннотация и введение
• Выборка LLM и управляемая генерация
• Итеративная обработка и индексирование конечного автомата
• Расширения итеративного анализа
• Обсуждение, ссылки и благодарности

3. Итеративная обработка и индексирование конечного автомата.

Точнее, мы рассматриваем регулярные выражения в 5-кратной конечно-автоматной форме [Sipser, 1996, Определение 1.5]:

Определение 1 (конечный автомат). Конечный автомат или конечный автомат задается формулой (Q, Σ, δ, q0, F), где Q — конечное множество состояний, Σ — конечный алфавит, δ : Q × Σ → Q — функция перехода, q0 ∈ Q — стартовое состояние, а F ⊆ Q — множество состояний принятия.

Символы, составляющие строки в V, взяты из Σ: т.е. V ⊂ P(Σ). Везде состояния автомата Q для простоты будут представлены целыми значениями.

Пример 1. На рисунке 1 мы иллюстрируем процесс выборки автомата для регулярного выражения ([0-9]*)?\.?[0-9]*, которое можно использовать для генерации чисел с плавающей запятой. Для простоты пусть словарь V состоит только из строк: «A», «.», «42», «.2» и «1».

Когда начинается генерация, автомат находится в состоянии 0, поэтому наш алгоритм маскирует строку «А», поскольку она не будет принята автоматом. В этом случае мы можем выбирать только «.», «42», «.2» и «1».

Если мы выбираем «.2», мы переводим автомат в состояние 3. В этом случае только «42» и «1» являются допустимыми завершениями, поэтому мы маскируем другие значения перед выборкой. Если вместо этого мы выбираем «1», мы переводим автомат в состояние 1, и в этом случае «.», «.42», «.2» и «1» являются допустимыми завершениями, а маска остается неизменной.

Перебор словаря для определения допустимых следующих токенов по-прежнему остается самой большой проблемой. Для этого мы предварительно обрабатываем словарь, используя автомат регулярного выражения, и строим индекс. Важная часть заключается в том, что мы рассматриваем возможность запуска в каждом жизнеспособном состоянии автомата, поскольку строки в словаре могут соответствовать произвольным частям регулярного выражения, и эти части неявно являются состояниями автомата.

Процедура создания совпадений, начиная с любой точки автомата, приведена в алгоритме 3. Результатом является список подпоследовательностей, подробно описывающих состояния, через которые будет проходить автомат при принятии предоставленной строки.

Сопоставляя начальные состояния этих подпоследовательностей с последним состоянием автомата, достигнутым за один шаг цикла в алгоритме 2, мы можем эффективно индексировать словарь с помощью карты σ : Q → P(V), соединяющей состояния автомата. и наборы элементов словаря, которые будут приняты ФШМ в этих штатах.

Алгоритм 4 описывает построение σ.

Использование хеш-карты для σ может привести к тому, что шаг m в алгоритме 2 будет стоить в среднем всего O(1). Более того, поскольку σ создается вне процедуры выборки маркеров, ее стоимость во время выполнения фактически не имеет значения, хотя теоретически она требует памяти, равной количеству состояний в автомате (т. е. |Q|). К счастью, для непатологических комбинаций регулярных выражений и словарей не каждая строка в словаре будет принята автоматом, и не каждое состояние автомата будет представлено строкой в V.

3.1 Примеры

В этом разделе мы используем GPT2-среду (355M параметров), чтобы проиллюстрировать, как на практике работает генерация на основе регулярных выражений. Для их генерации мы используем библиотеку Outlines:

Листинг 3.1 (продолжение)

Листинг 3.3 (продолжение)

3.2 Сравнение с современными методами

Чтобы проиллюстрировать эффективность подхода индексирования, описанного здесь и реализованного в Outlines, мы проведем простое сравнение с библиотекой Guidance. На момент написания этой статьи библиотека Guidance использует частичное сопоставление регулярных выражений (применяется каждый раз с начала выборочной последовательности) и должна перебирать словарь LLM (N = 50, 257) на каждом шаге.

Код руководства и подсказка, используемые для этого сравнения, следующие:

Листинг 3.4 (продолжение)

Соответствующий код Outlines выглядит следующим образом:

Листинг 3.5 (продолжение)

Значение max_tokens варьируется, а время записывается с помощью timeit для одного цикла и одного значения повторения (т. е. для каждого значения max_tokens собирается только одна выборка). Результаты представлены в разделе 3.2.

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