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

// returns.ts
import { returnService } from "@/services/returnService";

interface ReturnRequest {
    orderId: string;
    reason: ReturnReason;
}

async function createReturn(request: ReturnRequest) {
    ret// <CURSOR>
}

мы формировали контекст для запроса в LLM из текущего файла, импортируемого и недавно редактированного (returns.ts, returnService.ts и cancelService.ts, соответственно). Это помогло нам получить ожидаемую подсказку

Подсказка для файла returns.ts
Подсказка для файла returns.ts

В этом примере полезные файлы выбирались вручную. Чаще всего мы заранее не знаем, где находится необходимая для подсказки информация. Например, в репозитории могут быть тысячи файлов и десятки сниппетов кода, в которых встречаются слова return, request или createReturn. Передать все эти файлы как есть не получится. Даже если они поместятся в контекстное окно выбранной модели - большой объем кода увеличивает задержку генерации и размывает внимание у LLM. Поэтому между сбором контекста и запросом к модели появляется еще один слой

Схема системы автодополнения с ранжированием
Схема системы автодополнения с ранжированием

Сначала система находит потенциально полезные фрагменты, а затем ранжирует их, присваивая каждому кандидату оценку, и выбирает лучшие. Одним из базовых алгоритмов для такого ранжирования является BM25 [7]. Например, в Tabby похожий слой строится вокруг разбиения репозитория на сниппеты, обратного индекса и BM25-поиска по коду [1].

Рассмотрим сначала наивный подход к ранжированию. Строку перед курсором

async function createReturn(request: ReturnRequest) {

разобьем на отдельные логические поисковые термины:

async
function
create
return
request
ReturnRequest

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

src/legacy/returnUtils.ts           24
src/services/returnService.ts        8
src/returns/createReturn.test.ts     7
src/returns/cancelReturn.ts          4
...

На первом месте оказался файл returnUtils.ts. Однако большое количество совпадений еще не означает, что файл полезен для подсказки. Внутри файла может быть следующий код

// returnUtils.ts
export function returnIfDefined<T>(value: T | undefined): T | undefined {
    return value;
}

export function returnEmptyArray<T>(): T[] {
    return [];
}

export function returnNull(): null {
    return null;
}

Слово return встречается в нем много раз, но файл никак не связан с оформлением возврата заказа. У такого наивного алгоритма подсчета совпадений есть несколько проблем:

Во-первых, разные термины имеют разную ценность в конкретной ситуации. Термин return встречается почти в любом TypeScript-проекте, а ReturnRequest скорее всего используется только в нескольких файлах.

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

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

BM25 учитывает все три перечисленные проблемы.

Редкие термины важнее популярных

Рассмотрим два термина из нашего примера return и ReturnRequest. Термин return может встречаться сто раз в некотором документе, но само по себе такое совпадение почти ничего не говорит о полезности этого документа для поиска. ReturnRequest, напротив, может встречаться только в нескольких местах

async function createReturn(request: ReturnRequest)
export interface ReturnRequest {
    orderId: string;
    reason: ReturnReason;
}
function validateReturn(request: ReturnRequest)

Редкий идентификатор гораздо лучше сужает область поиска. Поэтому его вклад в итоговую оценку должен быть выше. Для этого в алгоритме BM25 используется величина Inverse Document Frequency, или IDF. Она оценивает, насколько редко термин встречается во всей коллекции документов. Упрощенно её можно представить следующей формулой

\text{IDF}(\text{term}) = log\left(\frac{\text{количество всех документов}}{количество документов с термином}\right)

Если термин встречается почти везде - отношение близко к единице, а его итоговый вес при ранжировании получается небольшим. Если термин встречается только в нескольких документах - IDF имеет большое значение.

Допустим, в репозитории находятся 1000 файлов. Во время поиска мы получили, что return встречается в 800 документах, request - в 300 документах, а ReturnRequest - в 5 документах. Тогда веса могут выглядеть так

IDF(return) = 0.2
IDF(request) = 1.2
IDF(ReturnRequest) = 5.3

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

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

Частота совпадений должна насыщаться

Теперь представим два фрагмента кода:

// fragment A
function validateReturn(request: ReturnRequest) {
    // ...
}
// fragment B
function validateReturnRequest(request: ReturnRequest): ReturnRequest {
    const copy: ReturnRequest = request;

    return copy as ReturnRequest;
}

Во втором фрагменте ReturnRequest встречается четыре раза, а в первом всего один. Второй фрагмент действительно может оказаться полезнее, но он не обязательно полезнее ровно в четыре раза. Обычный Term Frequency увеличивается линейно:

1 совпадение -> 1
2 совпадения -> 2
4 совпадения -> 4

BM25 же использует насыщение частоты

1 совпадение   -> сильный сигнал
2 совпадения   -> сигнал усилился
4 совпадения   -> усилился еще немного
20 совпадений  -> почти не изменился

Первое совпадение дает самый большой прирост. Каждое следующее влияет все меньше. За скорость насыщения отвечает параметр k1. Обычно он подбирается индивидуально для каждой поисковой системы. Смысл параметра можно описать так:

  • при небольшом k1 нескольких совпадений уже достаточно;

  • при большом k1 частота термина продолжает сильнее влиять на результат.

Для кода насыщение особенно важно. Большие generated-файлы, интерфейсы клиентов и автоматически созданные API могут содержать десятки одинаковых идентификаторов. Без насыщения они постоянно оказывались бы наверху выдачи.

Длина документа тоже имеет значение

Рассмотрим два документа. Первый - небольшой интерфейс:

export interface ReturnService {
    submit(command: SubmitReturnCommand): Promise<Return>;
}

Второй - файл на тысячу строк, где ReturnService один раз упоминается в импорте:

import { ReturnService } from "@/services/returnService";
// еще 998 строк кода

В обоих документах этот термин встречается ровно один раз. Но первое совпадение намного плотнее связано с содержимым документа.

BM25 нормализует оценку относительно длины документа. Длинный файл не должен выигрывать только потому, что в нем больше текста и больше возможности случайно совпасть с запросом. Для этого в алгоритме длина документа сравнивается со средней длиной документов в индексе

b \cdot \left(\frac{\text{длина документа}}{\text{средняя длина документов}} \right)

Степень такой нормализации контролирует параметр b:

  • b = 0 - длина документа не учитывается;

  • b = 1 - используется полная нормализация по длине;

  • 0 < b < 1 задает компромисс.

На практике часто используется значение около 0.75, но оно не является универсальным. Оптимальные параметры зависят от способа разбиения кода, языка программирования и размера индексируемых фрагментов. Если индекс состоит из функций сопоставимой длины, сильная нормализация может быть не нужна, а при индексации целых файлов, разброс длины будет намного больше. Поэтому практические системы часто индексируют не только целые файлы, а более мелкие фрагменты: функции, классы, соседние строки вокруг символа или секции документации [1].

Формула BM25

Теперь можно собрать описанные идеи в одну формулу

\text{BM25}(D, Q) = \sum_{i=1}^n \text{IDF}(q_i) \cdot \frac{f(q_i, D) \cdot (k_1+1)}{f(q_i, D) + k_1 \left(1 - b + b \cdot \frac{|D|}{\text{avrgdl}}\right)}

Где:

  • D - некоторый документ;

  • Q - некоторый поисковый запрос;

  • qi — очередной термин из запроса Q;

  • f(qi, D) - количество вхождений термина qi в документ D;

  • IDF(qi) - редкость термина qi в коллекции;

  • |D| - длина текущего документа;

  • avgdl - средняя длина документов;

  • k1 - степень насыщения частоты;

  • b - степень нормализации по длине.

Несмотря на размер формулы, в ней нет новой идеи. Она объединяет три уже известных нам правила:

  • редкие термины важнее популярных

  • повторения полезны, но их вклад насыщается

  • длинные документы нормализуются.

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

Ранжируем кандидатов

Вернемся к примеру с createReturn. Допустим, запрос состоит из следующих терминов:

createReturn
ReturnRequest
returnService

В индексе находятся три документа.

// Кандидат A: определение сервиса
export interface ReturnService {
    submit(command: SubmitReturnCommand): Promise<Return>;
}
// Кандидат B: похожий вызов
async function cancelReturn(id: string) {
    const userId = authService.getCurrentUserId();
    return await returnService.cancel({
        id,
        requestedBy: userId,
    });
}
// Кандидат C: большой легаси файл
// legacyReturns.ts
// сотни строк кода
export function createReturnPayload(request: LegacyRequest) {
    // ...
}

Применим алгоритм BM25 и получим следующие значения (примерно):

1. returnService.ts    -> 8.4
2. cancelReturn.ts     -> 6.8
3. legacyReturns.ts    -> 2.1

Определение сервиса получило высокий score благодаря редкому совпадению returnService и небольшой длине самого фрагмента. cancelReturn.ts не содержит ReturnRequest, но в нем встречается returnService, а сам фрагмент достаточно компактный. В легаси файле есть точное совпадение по createReturn, однако остальные термины не совпали, а большой размер документа уменьшил итоговую оценку.

После этого система автодополнения может взять первые два фрагмента и добавить их в промпт.

Retrieval и ranking

До этого момента мы использовали слова retrieval и ranking почти как синонимы. Однако на практике их стоит разделять.

Retrieval отвечает за поиск множества потенциальных кандидатов:

репозиторий
    ↓
retrieval
    ↓
100 подходящих фрагментов

Ranking определяет их порядок:

100 кандидатов
    ↓
ranking
    ↓
топ 10 кандидатов

Далее могут применяться дополнительные фильтры:

топ 10
    ↓
удаление дублей
    ↓
исключение generated-файлов
    ↓
ограничение контекста
    ↓
3 фрагмента для промпта

В случае BM25 граница действительно размывается. Этот индекс сразу позволяет найти и документы с нужными терминами, и вычислить для них score. Но разделение все равно полезно. В реальной системе автодополнения кандидаты могут приходить из нескольких источников: search, LSP definitions, recent files, similar code search и т.д. Все источники используют разные способы поиска и имеют собственные оценки. Затем отдельный ranking-слой должен упорядочить их. Один из практических вариантов такого объединения - rank fusion, когда система не пытается привести все оценки к одной шкале, а объединяет порядки из разных источников [4].

Финальный промпт для модели будет иметь следующий вид:

Заключение

Реальная система автодополнения обычно устроена сложнее. BM25 становится только одним из алгоритмов, по которым оценивается полезность найденного фрагмента. Если у фрагмента есть отдельные поля - путь, имя символа, сигнатура, тело, комментарии, - то можно использовать идею BM25F и давать совпадениям в разных полях разные веса [3]. Дополнительно система может учитывать:

  • близость кандидата к текущему файлу;

  • связи между модулями и символами;

  • недавно открытые и отредактированные файлы;

  • тип файла;

  • принадлежность к generated-, test- или legacy-коду;

  • результаты семантического поиска.

Кандидаты также могут поступать из разных источников: BM25 search, symbol definitions, recent files, similar code search и т.д. Результаты этих источников объединяются, повторяющиеся фрагменты удаляются, а оставшиеся кандидаты укладываются в доступный контекстный бюджет модели. Некоторые системы делают еще один шаг: сначала решают, нужен ли внешний контекст для конкретной подсказки, и запускают retrieval только если ожидают от него пользу [5]. Простую подсказку модель может сгенерировать только по коду вокруг курсора, а поиск в таком случае только увеличит задержку и может добавить лишний шум.

В итоге задача такой системы автодополнения - не передать модели как можно больше кода, а выбрать минимальный набор фрагментов, который поможет модели сгенерировать верную подсказку. Некоторые виды контекста при этом удобнее получать не через текстовый поиск. Например, определение импортированного объекта можно найти напрямую с помощью инструментов анализа кода. А если подсказка уже сгенерирована, ее можно использовать как новый поисковый запрос и итеративно уточнить контекст - такой подход исследуется в RepoCoder [2]. Качество подобных систем обычно проверяют на задачах cross-file completion, где модели действительно нужен контекст из других файлов репозитория [6]. В следующей заметке рассмотрим Language Server Protocol и разберемся, как система автодополнения получает определения, типы и другие данные о проекте.

Полезные ссылки

  1. Repository context for LLM assisted code completion - Tabby, 2023. Практический пример: Tree-sitter, разбиение кода на сниппеты, обратный индекс и BM25-поиск по репозиторию.

  2. RepoCoder: Repository-Level Code Completion Through Iterative Retrieval and Generation - Yuning Zhang et al., 2023. Итеративный процесс retrieval-generation, в котором предварительная подсказка помогает улучшить поисковый запрос.

  3. Keeping it boring (and relevant) with BM25F - Julie Tibshirani, 2025. Использование BM25F, весов полей и дополнительных сигналов при поиске по коду.

  4. Rank Fusion for improved Code Context in Tabby - Tabby, 2024. Объединение нескольких источников контекста и их ранжирований для code completion.

  5. Repoformer: Selective Retrieval for Repository-Level Code Completion - Toufique Ahmed et al., 2024. Selective retrieval: система определяет, принесёт ли внешний контекст пользу конкретной подсказке.

  6. CrossCodeEval: A Diverse and Multilingual Benchmark for Cross-File Code Completion - Yue Wang et al., 2023. Benchmark для оценки completion, которому необходим контекст из других файлов репозитория.

  7. The Probabilistic Relevance Framework: BM25 and Beyond - Stephen Robertson, Hugo Zaragoza, 2009. Подробное описание вероятностной модели поиска, BM25 и BM25F.