Материал подготовлен автоматически по первоисточникам: ссылки на них — в конце статьи.
При дефиците вычислений запросы к LLM можно ставить в очередь по готовности пользователей платить за более быстрый ответ, не ухудшая повторное использование кэша. В работе UC Berkeley, TTIC и Google Research, которая ещё не прошла рецензирование, а все числа получили сами авторы, такой подход повысил общую полезность очереди на 12–18,6% по сравнению с планировщиком, который не учитывает ставки. Для провайдера это возможная замена двум-трём фиксированным уровням приоритета на более точное распределение доступных мощностей.
Ставка меняет порядок ветвей, а не отдельных запросов
Аукцион работает поверх очереди запросов, которые ждут предварительной обработки промпта. Пользователь указывает, сколько для него стоит перемещение запроса из конца текущей группы в начало. Ценность считается линейно: чем большую часть группы запрос обгоняет, тем выше полученная им доля приоритета.
Просто отсортировать запросы по ставкам нельзя. SGLang объединяет промпты с общими префиксами в префиксное дерево и повторно использует кэш ключей и значений (KV-кэш). Если постоянно переключаться между несвязанными промптами, общие префиксы вытесняются из памяти, а сервер снова тратит вычисления на их обработку.
Поэтому ставки не разрывают группы с общими префиксами. Планировщик обходит дерево в глубину: сначала целиком обслуживает одну ветвь, затем переходит к соседней. На каждом разветвлении он ставит выше поддерево с большей средней ставкой среди входящих в него запросов.
Из-за этого отдельная высокая ставка не гарантирует немедленного обслуживания. В примере из статьи запрос со ставкой 8 идёт после запроса со ставкой 3, потому что средняя ставка всей его ветви ниже. Такой компромисс сохраняет выгодный для кэша порядок, но направляет приоритет к группам, где ранний ответ ценят выше.
Условие оптимальности действует, если кэш вмещает самый длинный запрос в группе. Сам аукцион определяет только относительный порядок уже собранных запросов и не решает, когда формировать группу или какие запросы в неё включать.
Платёж заставляет раскрывать реальную ценность
Если победитель просто платит свою ставку, пользователям выгодно угадывать минимальную цену и занижать ценность. Авторы применили платежи VCG: каждый участник платит за то, насколько его присутствие ухудшило результат для остальных. При таком механизме честная ставка становится оптимальной стратегией в рамках одного аукциона.
Наивный расчёт потребовал бы заново строить очередь без каждого пользователя. Предложенный алгоритм вместо этого смотрит, как обнуление его ставок меняет средние значения вдоль пути в префиксном дереве. Он учитывает только соседние ветви, которые после этого обгонят изменившуюся ветвь, поэтому расчёт платежей добавляет к обходу дерева сравнительно небольшой объём работы.
Для серии запросов одной честной ставки недостаточно: пользователь может исчерпать бюджет в начале периода. Агент автоматических ставок умножает ценность запросов на общий коэффициент и корректирует его по фактическим расходам. Если бюджет тратится слишком быстро, ставки снижаются; если медленно — растут.
Разные коэффициенты пользователей вредят общей полезности только тогда, когда меняют порядок ветвей относительно порядка по исходной ценности. Это связывает экономический результат с устройством префиксного дерева: различия между ставками внутри ветви несущественны, пока они не переставляют соседние группы.
Когда аукцион стоит закладывать в архитектуру сервиса
В экспериментах механизм работал отдельным слоем перед неизменённым сервером SGLang. Его проверяли на нескольких типах нагрузки с разной структурой общих префиксов, на одной модели и одном исполнителе инференса. Сравнением служили планировщик без ставок, который сохраняет оптимальный для кэша порядок, и свободная сортировка запросов по убыванию ставки.
При независимых оценках запросов общая полезность выросла на 12–18,6%, а при оценках, связанных со структурой нагрузки, выигрыш доходил до 100%. Аукцион при этом сохранял долю попаданий в кэш и среднее время до первого токена на уровне обычного планировщика SGLang.
По полезности механизм достигал примерно 80% результата свободной сортировки по ставкам. Но свободная сортировка разрушала повторное использование префиксов и увеличивала среднюю задержку до 12 раз. Это и есть практический смысл ограничения: аукцион уступает теоретическому порядку по цене, зато не оплачивает этот выигрыш деградацией сервера.
Работа меняет планы прежде всего для команд, которые сами управляют инференсом, сталкиваются с очередями и обслуживают запросы с разной чувствительностью к задержке. Аукцион можно добавить как слой планирования без изменений модели и SGLang, но продукту всё равно придётся переводить режимы работы клиентов в ценность и бюджет.
Сразу заменять тарифные уровни таким механизмом рано. Эксперименты охватывают группы запросов к одной модели на одном исполнителе, тогда как крупному сервису нужно одновременно маршрутизировать нагрузку между несколькими исполнителями и управлять их кэшами. Кроме того, линейная ценность места в очереди лишь приближает реальную цену задержки, поэтому разумный следующий шаг — испытать аукцион внутри одного перегруженного пула.
Источники
Иллюстрация: рисунок из статьи «Inference Auctions», Keegan Harris, Siddharth Prasad, Asher Trockman и др., CC BY 4.0
Похоже на вашу задачу?
Расскажите, что собираете. За полчаса разложим на этапы и назовём сроки — это бесплатно и ни к чему не обязывает.
