Методы построения индексов для векторных баз данных с использованием глубокого обучения тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Добрынин Вячеслав Юрьевич

• Добрынин Вячеслав Юрьевич
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Добрынин Вячеслав Юрьевич

Реферат

Synopsis

Введение

ГЛАВА 1 Формулировка проблемы, обзор предметной области

1.1 Формулировка проблемы

1.2 Плотные и разреженные представления

1.2.1 Плотные представления

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

1.3 Обзор существующих решений

1.3.1 HNSW: Hierarchical Navigable Small World

1.3.2 ColBERT: Contextualized Late Interaction over BERT

1.3.3 SNRM: Standalone Neural Ranking Model

1.3.4 SparTerm: Term-based Sparse Representations

1.3.5 SPLADE: Sparse Lexical and Expansion Model

1.4 Постановка задачи исследования

1.5 Выводы

ГЛАВА 2 Разработка метода построения инвертированного индекса

с использованием векторного словаря

2.1 Предварительное вычисление и хранение векторных представлений токенов

2.2 Описание метода построения векторного словаря

2.2.1 Выбор алгоритма кластеризации векторных представлений

2.2.2 Обоснование применения кластеризации для выделения семантических контекстов

2.2.3 Процесс построения векторного словаря

2.3 Построение инвертированного индекса

2.4 Процесс поиска

2.5 Выводы

ГЛАВА 3 Разработка метода построения инвертированного индекса с использованием нейронной сети для преобразования плотных векторов в разреженные

3.1 Описание метода обучения энкодера с использованием идентифицируемого вариационного автоэнкодера

3.1.1 Алгоритмы анализа независимых компонент

3.1.2 Процесс преобразования плотных векторов в разреженные

3.1.3 Ограничения скрытого пространства вариационного автоэнкодера

3.1.4 Обучение идентифицируемого вариационного автоэнкодера с использованием общей функции потерь

3.2 Описание метода обучения энкодера с использованием K-sparse автоэнкодера

3.2.1 Модель K-sparse автоэнкодера

3.2.2 Обучение K-sparse автоэнкодера с использованием общей функции потерь

3.3 Мультимодальный поиск

3.4 Функция оценки релевантности запроса и документа

3.5 Инвертированный индекс

3.6 Выводы

ГЛАВА 4 Сравнительный анализ и экспериментальное исследование методов построения индексов для векторных баз данных

4.1 Сравнительный анализ предложенных методов

4.1.1 Мультимодальные возможности

4.1.2 Адаптивность к новым эмбеддинг-моделям

4.1.3 Интерпретируемость результирующего представления

4.1.4 Качество поиска и ресурсоемкость

4.2 Выбор и обоснование инструментальных средств для проведения экспериментального исследования

4.3 Экспериментальная оценка метода построения инвертированного индекса с использованием векторного словаря

4.3.1 Программная реализация метода

4.3.2 Результаты экспериментальной оценки метода

4.3.3 Выводы

4.4 Экспериментальная оценка метода построения инвертированного индекса с использованием нейронной сети для преобразования плотных векторов в разреженные

4.4.1 Программная реализация метода

4.4.2 Результаты экспериментальной оценки метода с использованием идентифицируемого вариационного автоэнкодера

4.4.3 Результаты экспериментальной оценки метода с использованием K-sparse автоэнкодера

4.4.4 Выводы

4.5 Общие выводы

Заключение

Список сокращений и условных обозначений

Словарь терминов

Список литературы

Список иллюстративного материала

Список таблиц

Приложение 1: Данные для демонстрации поведения эмбеддингов

Приложение 2: Данные для демонстрации выделения контекстов . . . .176 Тексты публикаций

Реферат

Введение диссертации (часть автореферата) на тему «Методы построения индексов для векторных баз данных с использованием глубокого обучения»

Общая характеристика работы

Актуальность темы. Современное развитие глубокого обучения способствует значительным прорывам во многих научных и инженерных областях. Это также касается и информационного поиска. Нейронные сети архитектуры «Трансформер» [10], позволяющие формировать векторные представления, широко используются для информационного поиска благодаря своей исключительной возможности понимать семантику текстов и данных других модальностей. Документы и запросы кодируются в плотные векторы, после чего между ними находится схожесть благодаря специальным функциям. Описанный подход позволяет значительно улучшить качество поиска, но обычный поиск по векторам имеет линейную сложность, что недопустимо для больших объемов данных. Для решения этой проблемы в векторных базах данных используются приближенные ANN (Approximate Nearest Neighbor) [8] алгоритмы, такие как HNSW (Hierarchical Navigable Small World) [42]. Благодаря внутренней структуре поискового индекса удается добиться в среднем логарифмической сложности поиска при незначительном снижении качества. Однако приближенные алгоритмы также имеют свои недостатки. Так, например, структура индекса HNSW требует большого объёма памяти, а сам индекс обычно хранится в оперативной памяти, что значительно затрудняет использование алгоритма в распределенной среде, необходимой для крупномасштабных информационно-поисковых систем.

Характерной особенностью крупномасштабных поисковых систем является использование структуры данных, называемой инвертированным индексом. Данные в этой структуре хранятся в формате «термин-словопозиции». Все термины образуют словарь или лексикон индекса. Список словопозиций (англ. postings list), сопоставляемый каждому термину, представляет собой набор идентификаторов документов, в которых содержится соответствующий термин. Часто вместе с идентификатором документа хранятся дополнительные сведения,

например, частота термина и список его позиций в документе. Такая структура данных позволяет компактно хранить информацию, поскольку термины сохраняются в единственном экземпляре в словаре, а словопозиции содержат только ссылки на них. Более того, существует множество алгоритмов сжатия как словаря, так и словопозиций [44; 54]. Помимо очевидного преимущества в снижении требований к памяти, сжатие имеет два менее заметных достоинства. Во-первых, оно повышает эффективность кеширования наиболее часто используемых терминов и словопозиций. Во-вторых, сжатые данные быстрее загружаются с диска в оперативную память, что ускоряет общий процесс поиска. Это происходит благодаря тому, что чтение сжатых данных и их последующая распаковка выполняются быстрее, чем только чтение несжатых данных, за счёт высокой скорости алгоритмов распаковки и сравнительно низкой скорости операций ввода-вывода. Таким образом, сжатие инвертированного индекса обеспечивает как снижение требований к памяти, так и увеличение скорости поиска. Этот формат хранения практически не имеет конкурентов, поскольку позволяет быстро выполнять поиск, масштабировать индекс в распределённых системах и гибко применять различные алгоритмы ранжирования.

Однако классический способ использования инвертированного индекса фундаментально ограничен из-за проблемы несовпадения словарей запроса и документов [65; 72]. Например, если в запросе используются синонимы или определенный семантический смысл описан новыми словами с точки зрения словаря документов, то для этого запроса не будут найдены соответствующие документы. Для решения проблемы используют расширение словарей запросов и документов или другие подходы, но многие из них наследуют ограничения исходной проблемы.

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

вает эффективность, масштабируемость и применимость поискового алгоритма в распределенных системах.

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

Степень разработанности темы. Задача эффективного семантического поиска с использованием глубокого обучения активно развивается последние несколько лет, с момента появления архитектуры «Трансформер» [10] (А. Ва-свани, Н. Шазир, И. Полосухин, Л. Кайзер) и моделей BERT [14] (Дж. Девлин, М. Чан, К. Ли, К. Таутанова). Эти работы заложили основу для применения глубоких нейронных сетей к задачам обработки естественного языка и информационного поиска.

С точки зрения организации поискового индекса, исследования развиваются в нескольких основных направлениях.

Р. Ногейра, В. Ян, К. Чо и Дж. Лин [49; 51] разработали многоступенчатую архитектуру ранжирования с использованием BERT-моделей. Несмотря на высокое качество, такой подход требует выполнения множественных проходов по данным, что усложняет архитектуру системы и увеличивает вычислительные затраты.

Исследования плотных векторных представлений, такие как Dense Passage Retrieval [18] (В. Карпухин, Б. Огуз, С. Мин), показали их высокую эффективность для семантического поиска. Для преодоления проблемы масштабирования поиска по векторам были разработаны алгоритмы приближённого поиска ближайших соседей. Наибольшее распространение получил алгоритм HNSW, предложенный Ю. Малковым и Д. Яшуниным [42], который обеспечивает полилогарифмическую сложность поиска и широко применяется в векторных базах данных, таких как Milvus [45] (Ц. Ван). Дополнительные методы сжатия векторов, такие как Product Quantization, разработанные Э. Жегу, М. Дузе, К. Шмидом, Дж. Джонсоном [35; 36], позволяют снизить требования к памяти, но требуют компромисса в качестве поиска. Несмотря на успехи данного направления,

фундаментальная проблема высоких требований к памяти для индексов HNSW остаётся актуальной, особенно в распределённых системах.

О. Хаттаб и М. Захария в работе ColBERT [37] предложили механизм «позднего взаимодействия», при котором документы кодируются на уровне токенов, а релевантность вычисляется через поэлементное сравнение векторов токенов запроса и документа. Данный подход был развит К. Сантанам и К. Поттсом в ColBERTv2 [17], где введены улучшения в виде сжатия векторов и дистилляции моделей. Несмотря на высокое качество поиска, ColBERT требует хранения всех векторов токенов документов, что приводит к линейной зависимости потребления памяти от произведения числа токенов t и размерности векторного пространства d (0(t • d) на документ).

Для преодоления ограничений плотных представлений и обеспечения совместимости с инвертированным индексом активно исследуются методы получения разреженных векторных представлений. Первая успешная нейронная модель SNRM [27] была предложена Х. Замани и М. Дехгани, но её недостатком является отсутствие интерпретируемости исходных терминов. Модель SparTerm [63] (Я. Бай, С. Ли, Г. Ван.) на основе BERT сохраняет интерпретируемость, но имеет сложную архитектуру с модулем отбора терминов. Значительным прорывом стала серия работ SPLADE, предложенная Т. Формалем, Б. Пивоварски и С. Клиншаном [26]. SPLADE упрощает архитектуру SparTerm одновременно повышая качество и скорость поиска. Последующие версии улучшили производительность через дистилляцию, однако модель применима только к текстовой модальности.

Недавние исследования Т. Брикена, А. Темплтона и др. [66] и Л. Гао, Т. Дюпре ла Тура, А. Рэдфорда, И. Суцкевера [60] показали, что разреженные автоэнкоде-ры с избыточной размерностью скрытого пространства способны «распутывать» плотные представления, обеспечивая более интерпретируемые и независимые компоненты. Эти результаты открывают новые возможности для применения автоэнкодеров в задачах информационного поиска.

H. Тхакур, Н. Раймерс и И. Гуревич [13] создали фреймворк BEIR для стандартизированной оценки качества информационно-поисковых систем, что способствует воспроизводимости результатов различных исследований.

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

Целью данной работы является снижение объёма памяти, занимаемой поисковым индексом в векторных базах данных, за счёт применения разреженных векторных представлений при сохранении качества поиска.

Для достижения поставленной цели необходимо было решить следующие задачи:

I. Анализ существующих методов и алгоритмов информационного поиска на основе глубоких нейронных сетей.

2. Разработка метода построения поискового индекса с использованием векторного словаря.

3. Разработка метода построения поискового индекса с использованием нейронной сети для преобразования плотных векторов в разреженные.

4. Программная реализация предложенных методов.

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

Научная новизна: Метод построения поискового индекса для векторных баз данных, основанный на механизме «позднего взаимодействия» (англ. late interaction, ColBERT [37]) и использовании векторного словаря. Новизна метода проявляется в двух ключевых аспектах:

1. Формирование разреженных представлений через предложенный векторный словарь и их размещение в инвертированном индексе, что снижает требования к памяти.

2. Перенос вычисления релевантности (MaxSim, «позднее взаимодействие») на этап индексации (сопоставление выполняется между элементами векторного словаря и векторами слов документа), что существенно сокращает вычислительные затраты на этапе поиска при сохранении преимуществ поэлементного вычисления релевантности.

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

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

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

Теоретическая и практическая значимость. Теоретическая значимость диссертации состоит в развитии теории гибридных лексико-семантических индексов, а именно:

- В обобщении механизма «позднего взаимодействия» на разреженное признаковое пространство.

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

- А также в распространении полученных положений на смежные задачи, в том числе на тематическое моделирование за счёт автоматического выделения ключевых признаков в данных.

Практическая значимость исследования заключается в разработке методов, которые могут быть непосредственно использованы при построении эффективных крупномасштабных поисковых систем и векторных баз данных, способствуя повышению их масштабируемости и эффективности. Исходный код прототипов и экспериментов доступен в открытом репозитории, что обеспечивает воспроизводимость и облегчает перенос результатов в промышленную среду. Кроме того, использование библиотеки Lucene, широко распространённой в индустрии и обладающей зрелым API, упрощает перенос предложенных решений в практические продукты, снижая инженерные риски и трудозатраты.

Методология и методы исследования. Машинное обучение и глубокие нейронные сети, векторные представления текстов, кластерный анализ, методы приближённого поиска ближайших соседей, анализ независимых компонент, методы оптимизации. Экспериментальные исследования выполнены на языке Python с использованием библиотек Faiss, PyTorch, PyTorch Lightning, Transformers, NumPy, NLTK, Wandb, BEIR и на языках Java/Kotlin с использованием библиотеки Lucene.

Положения, выносимые на защиту:

1. Метод индексирования текстовых коллекций, использующий глубокую нейронную сеть для получения плотных d-мерных векторных представлений запросов и документов, отличающийся применением векторного словаря для их преобразования в разреженные представления с к ненулевыми компонентами с целью последующей записи в инвертированный индекс, обеспечивающий снижение объёма памяти, занимаемой индексом, в сравнении с алгоритмами HNSW и ColBERT за счёт замены зависимости от размерности d на зависимость от к (к ^ d).

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

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

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

Достоверность полученных результатов подтверждается использованием признанного научным сообществом математического аппарата, репрезентативных открытых коллекций (MS MARCO, SciFact) и стандартных инструментов измерения качества поиска (Benchmarking-IR, BEIR), сопоставлением с независимыми работами (BM25, ColBERT, HNSW), обсуждением результатов на восьми международных и всероссийских конференциях, и публикациями в изданиях из списка индексируемых международными реферативными базами данных Web of Science и Scopus.

Апробация работы. Основные результаты исследований докладывались и обсуждались на следующих конференциях:

1. XI Конгресс молодых ученых, 2022, Университет ИТМО, Санкт-Петербург, Россия.

2. Всероссийская конференция «Молодые профессионалы», 2022, Университет ИТМО, Санкт-Петербург, Россия.

3. LII Научная и учебно-методическая конференция, 2023, Университет ИТ-МО, Санкт-Петербург, Россия.

4. XII Конгресс молодых ученых, 2023, Университет ИТМО, Санкт-Петербург, Россия.

5. 17th IEEE International Conference on Application of Information and Communication Technologies - AICT, 2023, ADA University, Баку, Азербайджан.

6. LIII Научная и учебно-методическая конференция, 2024, Университет ИТ-МО, Санкт-Петербург, Россия.

7. XIII Конгресс молодых ученых, 2024, Университет ИТМО, Санкт-Петербург, Россия.

8. 18th IEEE International Conference on Application of Information and Communication Technologies - AICT, 2024, Polytechnic University of Turin, Турин, Италия.

Личный вклад. В диссертационной работе использованы результаты, в создании которых автору принадлежит определяющая роль. Теоретические и экспериментальные исследования по теме диссертации проводились автором совместно с Платоновым А.В., Абрамовичем Р.К. и Шерманом М.Л. Автор самостоятельно занимался исследованием в области применения методов глубокого обучения к задаче формирования индекса в информационно-поисковой системе, а также разработкой моделей семантического поиска. Автор осуществлял полный цикл исследовательской работы: постановку задач и разработку методов, программную реализацию прототипов и инфраструктуры экспериментов, планирование и проведение экспериментальных исследований, анализ и интерпретацию результатов, а также подготовку текста статей.

Подготовка публикаций [5; 20; 21] осуществлялась совместно с соавторами, при этом вклад автора был основным, что подтверждается первой позицией автора в соответствующих работах. Вклад соавторов формулируется следующим образом: Абрамович Р.К. - участие в проведении исследований и в написании статей, Шерман М.Л. - участие в поиске источников и в исследованиях, Платонов А.В. - научное руководство. В обзорной статье [1], где автор не указан первым, его вклад остаётся существенным и включает организацию работы, подготовку иллюстративного материала, помощь первому автору в составлении перечня обозреваемых алгоритмов и научное редактирование рукописи. Вклад соавторов в данной работе: Абрамович Р.К. - основной вклад в подготовку текста статьи, Платонов А.В. - научное руководство.

В работе [2] автор является единственным автором, выполнив полный цикл исследования и подготовку рукописи самостоятельно.

Публикации. Основные результаты по теме диссертации изложены в 6 научных статьях, 2 из которых изданы в журналах, рекомендованных ВАК, 4 — в изданиях, индексируемых Web of Science и Scopus.

Объем и структура работы. Диссертация состоит из введения, четырех глав и заключения. Полный объём диссертации составляет 215 страниц, включая 23 рисунка и 14 таблиц. Список литературы содержит 74 наименования.

Содержание работы

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

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

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

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

Приводится описание плотных и разреженных векторных представлений. Особое внимание уделяется разреженным векторным представлениям доку-

ментов и запросов, которые необходимы для использования инвертированного индекса.

Далее в главе представлены обзор и анализ существующих алгоритмов поиска по плотным векторным представлениям, таких как Hierarchical Navigable Small World (HNSW) и Contextualized Late Interaction over BERT (ColBERT), а также алгоритмов информационного поиска, которые используют глубокие нейронные сети для получения разреженных представлений, таких как Standalone Neural Ranking Model (SNRM), Term-based Sparse Representations (SparTerm) и Sparse Lexical and Expansion Model (SPLADE).

Коротко данные модели можно описать следующим образом:

- HNSW - данный метод построения поискового индекса векторной базы данных часто показывает лучшие результаты на реальных данных и считается одним из передовых. В его основе лежит построение иерархических графов близости, где каждый верхний слой является уменьшенным подграфом нижнего, а поиск начинается с самого малого (верхнего) слоя. Такой подход дает полилогарифмическую сложность поиска при высоких показателях качества. Однако одним из главных его недостатков является высокая требовательность к памяти из-за необходимости хранить вершины и связи между вершинами для каждого слоя.

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

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

нейронной сети. Полученные разреженные векторные представления агрегируются в результирующий вектор путем усреднения значений для соответствующих компонент. При обучении нейронной сети авторы используют функцию активации ReLU и Ll-регуляризацию для обеспечения разреженности. Основное ограничение - потеря интерпретируемости исходных терминов.

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

- SPLADE - упрощает архитектуру SparTerm, избавляясь от модуля отбора терминов. Вводит логарифмическое насыщение для предотвращения доминирования терминов и регуляризатор FLOPS для обеспечения разреженности. Это позволило повысить как производительность, так и качество поиска. При этом первая версия имеет недостаток в виде большого числа ненулевых компонент в сравнении с классическими алгоритмами. Последующие версии улучшают производительность, изменяя способ вычисления весов разреженного вектора, и повышают качество, применяя дистилляцию. Однако модель применима только к текстовой модальности. Также сопоставление запроса и документа выполняется по их итоговым векторам, а не по векторам токенов, как в ColBERT, что может снижать выразительность.

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

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

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

Во второй главе разрабатывается метод построения инвертированного индекса с использованием векторного словаря. Под векторным словарём понимается компактный векторный индекс, содержащий словарь терминов, который используется при построении инвертированного индекса. Данный векторный индекс содержит векторы, отражающие различные семантические значения токенов токенизатора BERT. Для получения этих значений используется кластеризация плотных векторных представлений токенов в различных контекстах. Контексты извлекаются из множества документов, по которым строится векторный словарь. Полученные центроиды кластеров интерпретируются как эти семантические значения. Например, существительное «поле» может образовывать словосочетания «магнитное поле» и «пшеничное поле», в результате чего в первом случае оно относится к области физики, а во втором к аграрной сфере. Если собрать множество примеров употребления слова «поле» в различных контекстах, получить их векторные представления, учитывающие контекст, и затем кластеризовать данные представления, то центроиды кластеров будут приближенно соответствовать различным значениям слова. Таким образом, такие центроиды будут представлять расширенный словарь документов (множество слов, встречающихся в индексируемых документах), включающий различные семантические значения токенов.

Полученный векторный словарь используется как при построении инвертированного индекса, так и при поиске. Идентификаторы центроидов словаря используются в качестве ключей инвертированного индекса. Оценка релевантности между центроидом словаря и документом вычисляется с помощью функции MaxSim [37], предложенной в ColBERT, что обеспечивает качество поэлемент-

Список литературы диссертационного исследования кандидат наук Добрынин Вячеслав Юрьевич, 2025 год

Список источников

1. Vaswani A., Shazeer N., Parmar N., et al. Attention is all you need, arXiv (Cornell University), 2017, vol. 30, pp. 5998-6008, DOI:10.48550/arXiv.1706.03762.

2. Guo J., Cai Y., Fan Y., Sun F., et al. Semantic models for the first-stage retrieval: A comprehensive review. ACM Transactions on Information Systems, 2022, 40(4), pp. 1-42, D0I:10.1145/3486250

3. Zamani H., Dehghani M., Croft W.B., et al. From neural re-ranking to neural ranking: Learning a sparse representation for inverted indexing, The 27th ACM International Conference on Information and Knowledge Management, 2018, pp. 497-506.

4. Bank D., Koenigstein N., Giryes R. Autoencoders. Deep learning in science, 2021.

5. Robertson S. E., Zaragoza H. The probabilistic relevance framework: BM25 and beyond, Found. Trends Inf. Retr., 2009, vol. 3, pp. 333-389.

6. Bai Y., Li X., Wang G., Zhang C. et al. SparTerm: Learning term-based sparse representation for fast text retrieval, arXiv, 2020.

7. Devlin J., Chang M. W., Lee K., Toutanova K. BERT: Pre-training of deep bidirectional transformers for language understanding. arXiv, 2018, D0I:10.48550/arXiv.1810.04805.

8. Hendrycks D., Gimpel K. Gaussian Error Linear Units (GELUs). arXiv, 2016, D0I:10.48550/arXiv.1606.08415.

9. Ba Jimmy L., Kiros Jamie Ryan, Hinton Geoffrey E. Layer normalization. arXiv, 2016, D0I:10.48550/arXiv.1607.06450.

10. Formal T., Piwowarski B., Clinchant S. SPLADE: Sparse lexical and expansion model for first stage ranking, Proceedings of the 44th International ACM SIGIR Conference on research and development in information retrieval, 2021.

11. Biswajit Paria, Chih-Kuan Yeh, Ian E. H. Yen, et al. Minimizing FLOPs to Learn Efficient Sparse Representations. arXiv, 2020, D0I:10.48550/arXiv.2004.05665.

12. Khattab 0., Zaharia M.A. ColBERT: Efficient and effective passage search via contextualized late interaction over BERT, Proceedings of the 43rd International ACM SIGIR Conference on research and development in information retrieval, 2020.

13. Johnson J., Douze M., Jegou H. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 2017, vol. 7, pp. 535-547, D0I:10.48550/arXiv.1702.08734.

14. Jegou H., Douze M., Schmid C. Product quantization for nearest neighbor search. IEEE Transactions on pattern analysis and machine intelligence, 2011, vol. 33, pp. 117-128, D0I:10.1109/TPAMI.2010.57.

15. Santhanam K., Khattab 0., Saad-Falcon J., et al. ColBERTv2: Effective and efficient retrieval via lightweight late interaction. North American chapter of the association for computational linguistics, 2021, D0I:10.48550/arXiv.2112.01488.

16. Kong W., Dudek J.M., Li C., et al. SparseEmbed: Learning sparse lexical representations with contextual embeddings for retrieval. Proceedings of the 46th International ACM SIGIR conference on research and development in information retrieval, 2023.

Абрамович Роман Константинович. Аспирант, факультет программной инженерии и компьютерной техники университета ИТМО. AuthorlD: 1253076, SPIN: 8710-8245, Scopus AuthorlD: 58759320100, ORCID: 0009-0005-5397-2772, [e-mail], 197101, Россия, Санкт-Петербург, Кронверкский пр. 49.

Добрынин Вячеслав Юрьевич. Аспирант, факультет программной инженерии и компьютерной техники университета ИТМО. AuthorlD: 1014269, SPIN: 9792-5868, Scopus AuthorlD: 57223099701, ORCID: 0009-00043056-8403, [e-mail], 197101, Россия, Санкт-Петербург, Кронверкский пр. 49.

Платонов Алексей Владимирович. Доцент, к.т.н, факультет программной инженерии и компьютерной техники университета ИТМО. AuthorID: 1048089, SPIN: 1973-7334, Scopus AuthorID: 57197736275, ORCID: 0000-0002-8485-1296, [e-mail], 197101, Россия, Санкт-Петербург, Кронверкский пр. 49.

UDC 004.912

DOI:10.25729/ESI.2025.38.2.001

Combining deep language models and sparse vector representations in information retrieval: a review and analysis of modern approaches Roman K. Abramovich, Viacheslav Yu. Dobrynin, Alexey V. Platonov

ITMO university,

Russia, St. Petersburg, [e-mail]

Abstract. Traditional search methods based on sparse vector representations are characterized by high efficiency but limited quality due to their inability to capture semantic relationships in the data. On the other hand, dense vector representations can improve quality by capturing semantic relationships. However, these methods face scalability issues and require significant computational resources. With the development of deep neural networks, including transformer-based architectures, there is a growing interest in combining these two approaches. The purpose of this review paper is to review existing works that use deep models to generate sparse representations. Keywords: deep neural networks, semantic search, computational resources, sparse representations, inverted index

References

1. Vaswani A., Shazeer N., Parmar N., et al. Attention is all you need, arXiv (Cornell University), 2017, vol. 30, pp. 5998-6008, D0I:10.48550/arXiv.1706.03762.

2. Guo J., Cai Y., Fan Y., Sun F. et al. Semantic models for the first-stage retrieval: A comprehensive review. ACM Transactions on Information Systems, 2022, 40(4), pp. 1-42, D0I:10.1145/3486250

3. Zamani H., Dehghani M., Croft W.B., et al. From neural re-ranking to neural ranking: Learning a sparse representation for inverted indexing, The 27th ACM International Conference on Information and Knowledge Management, 2018, pp. 497-506.

4. Bank D., Koenigstein N., Giryes R. Autoencoders. Deep learning in science, 2021.

5. Robertson S. E., Zaragoza H. The probabilistic relevance framework: BM25 and beyond, Found. Trends Inf. Retr., 2009, vol. 3, pp. 333-389.

6. Bai Y., Li X., Wang G., Zhang C. et al. SparTerm: Learning term-based sparse representation for fast text retrieval, arXiv:, 2020.

7. Devlin J., Chang M. W., Lee K., Toutanova K. BERT: Pre-training of deep bidirectional transformers for language understanding. arXiv, 2018, D0I:10.48550/arXiv.1810.04805.

8. Hendrycks D., Gimpel K. Gaussian Error Linear Units (GELUs). arXiv, 2016, D0I:10.48550/arXiv.1606.08415.

9. Ba Jimmy L., Kiros Jamie Ryan, Hinton Geoffrey E. Layer normalization. arXiv, 2016, D0I:10.48550/arXiv.1607.06450.

10. Formal T., Piwowarski B., Clinchant S. SPLADE: Sparse lexical and expansion model for first stage ranking, Proceedings of the 44th International ACM SIGIR Conference on research and development in information retrieval, 2021.

11. Biswajit Paria, Chih-Kuan Yeh, Ian E. H. Yen, et al. Minimizing FL0Ps to Learn Efficient Sparse Representations. arXiv, 2020, D0I:10.48550/arXiv.2004.05665.

12. Khattab 0., Zaharia M.A. ColBERT: Efficient and effective passage search via contextualized late interaction over BERT, Proceedings of the 43rd International ACM SIGIR Conference on research and development in information retrieval, 2020.

13. Johnson J., Douze M., Jégou H. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 2017, vol. 7, pp. 535-547, D0I:10.48550/arXiv.1702.08734.

14. Jégou H., Douze M., Schmid C. Product quantization for nearest neighbor search. IEEE Transactions on pattern analysis and machine intelligence, 2011, vol. 33, pp. 117-128, D0I:10.1109/TPAMI.2010.57.

15. Santhanam K., Khattab 0., Saad-Falcon J., et al. ColBERTv2: Effective and efficient retrieval via lightweight late interaction. North American chapter of the association for computational linguistics, 2021, D0I:10.48550/arXiv.2112.01488.

16. Kong W., Dudek J.M., Li C., et al. SparseEmbed: Learning sparse lexical representations with contextual embeddings for retrieval. Proceedings of the 46th International ACM SIGIR conference on research and development in information retrieval, 2023.

Abramovich Roman Konstantinovich. PhD student, Faculty of software engineering and computer science, ITMO university. SPIN: 8710-8245, AuthorID: 1253076, Scopus AuthorID: 58759320100, ORCID: 0009-0005-5397-2772,, [e-mail], 197101, Russia, Saint Petersburg, Kronverksky pr. 49.

Dobrynin Viacheslav Yurievich. PhD student, Faculty of software engineering and computer science, ITMO university. SPIN: 9792-5868, AuthorID: 1014269, Scopus AuthorID: 57223099701, ORCID: 0009-0004-3056-8403, [e-mail], 197101, Russia, Saint Petersburg, Kronverksky pr. 49.

Platonov Alexey Vladimirovich. Associate Professor, Ph.D., Faculty of software engineering and computer science, ITMO university. SPIN: 1973-7334, AuthorID: 1048089, Scopus AuthorID: 57197736275, ORCID: 0000-00028485-1296, [e-mail], 197101, Russia, Saint Petersburg, Kronverksky pr. 49.

Статья поступила в редакцию 09.07.2024; одобрена после рецензирования 20.03.2025; принята к публикации 11.04.2025.

The article was submitted 07/09/2024; approved after reviewing 03/20/2025; acceptedforpublication 04/11/2025.

Издание: Научно-технический вестник Поволжья, выпуск №5 2023

(журнал)

278 Научно-технический вестник Поволжья №5 2023_Технические науки

2.3.5

В.Ю. Добрынин, В.П. Туров, Р.К. Абрамович, Н.А. Томилов, А.Д. Горшков, А.А. Бабаянц, А.В. Платонов канд. техн. наук

Университет ИТМО, факультет программной инженерии и компьютерной техники, Санкт-Петербург, [e-mail]

РАЗРАБОТКА АЛГОРИТМА ПОИСКА НЕСТРУКТУРИРОВАННОЙ

ИНФОРМАЦИИ С ИСПОЛЬЗОВАНИЕМ НЕЙРОННОЙ СЕТИ АРХИТЕКТУРЫ

ТРАНСФОРМЕР

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

Ключевые слова: поисковая машина, transformer, BERT, инвертированный индекс, оптимизация, контекстуальное значение слов.

Введение

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

Современные поисковые системы используют комбинацию простых алгоритмов и машинного обучения [2]. Поиск производится в два этапа: сперва простые и быстрые алгоритмы отсеивают, а затем нейронные сети оценивают релевантность оставшихся документов. Однако такой подход имеет недостаток: алгоритмы первого этапа отсеивают документы без опоры на семантическую составляющую. Это значит, что некоторые релевантные документы могут быть пропущены из-за несовпадения терминов или многозначных слов в запросе и документе [3].

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

Построение обратного индекса

Предложенный подход основывается на использовании BERT для поиска схожести поискового запроса и документов. Модель BERT представляет документы в виде многомерного семантического пространства в котором метрика расстояния будет эквивалентна семантической близости.

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

Научно-технический вестник Поволжья №5 2023_Технические науки 279

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

Построение HNSW-индекса. Вероятно, что некоторое множество векторов представляют одно и тоже значение. Это значит, что семантическое пространство можно разделить на кластеры, центроиды которых соответствуют определенному контексту. Эмпирическим путем количество кластеров было определено равным 16. Для каждого токена в HNSW-индекс сохраняется кортеж (токен; идентификатор кластера; векторное представление центроида).

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

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

Метод тестирования поиска

Алгоритм. Алгоритм поиска похож на алгоритм индексации.

1. Выделить из запроса последовательности токенов методом скользящего окна.

2. Получить контектуализированное векторное представление для каждого окна.

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

4. Для каждой пары (токен; идентификатор кластера) из обратного индекса получить список документов-кандидатов с их метрикой релевантности. Если некоторый документ встречается более одного раза, то метрика релевантности суммируется.

5. Список документов-кандидатов сортируется в порядке убывания метрики релевантности.

Тестирование. Для тестирования разработанной структуры подходит набор данных MS Marco, созданный в 2016 и адаптированный для задач информационного поиска в 2018 [4]. Этот набор данных содержит 3.2 миллиона текстовых документов, полученных из поисковой системы Bing. Тестовый набор содержит 6980 запросов, для которых представлена эталонная выборка в виде ассоциации 100 наиболее релевантных документов. Этот набор данных часто используется исследователями для оценки собственных решений задачи информационного поиска, что упрощает сравнение решений.

Метрики. Существует множество метрик, оценивающих алгоритмы поиска с различных сторон. Для оценки эффективности поиска используются MRR@10/100/1000, Recall@10/100/1000 и DCG@10/100/1000. Помимо этих метрик необходимо обратить внимание на потребление вычислительных ресурсов:

1. Пропускную способность индексации.

2. Время отклика (задержку) при поиске.

3. Занимаемый объем данных в оперативном и постоянном хранилище.

Реализация. На текущий момент реализация алгоритма в процессе разработки, а

результаты реализации будут обсуждаться в следующих работах.

Для тестирования алгоритма был разработан тестовый стенд, совместимый с существующими алгоритмами информационного поиска, так как в качестве эталона выбран Anserini Toolkit. Языком программирования выбран Kotlin как современный и удобный,

280 Научно-технический вестник Поволжья №5 2023_Технические науки

предоставляющий доступ к широким возможностям JVM. Реализация модели BERT — DistilBERT, доступ к которой осуществляется через Deep Java Library. В качестве хранилища обратного индекса используется фреймворк Apache Lucene, хорошо себя зарекомендовавший в качестве подсистемы Elasticsearch.

На текущий момент доступ к тестовому стенду реализован исключительно через командную строку (CLI).

Заключение

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

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

Список литературы

1. S. Hofstätter, A. Hanbury. Let's measure run time! Extending the IR replicability infrastructure to include performance aspects, arXiv preprint arXiv:1907.04614 (2019)

2. R.-C. Chen, L. Gallagher, R. Blanco, J. S. Culpepper. Efficient cost-aware cascade ranking in multi-stage retrieval, Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval (2017) 445-454. doi:10.1145/3077136.3080819.

3. G. W. Furnas, T. K. Landauer, L. M. Gomez, S. T. Dumais. The vocabulary problem in humansystem communication, Commun. ACM 30 (1987) 964-971

4. T. Nguyen, M. Rosenberg, X. Song, J. Gao, R. M. Saurabh Tiwary, L. Deng. Ms marco: A human generated machine reading comprehension dataset., In Proceedings of the Workshop on Cognitive Computation: Integrating neural and symbolic approaches 2016 (CEUR Workshop Proceedings, Vol. 1773) (2016).

Издание: 2023 IEEE 17th International Conference on Application of Information and Communication Technologies (материалы конференции)

Building a Full-text Search Index Using "Transformer" Neural Network

Vyacheslav Dobrynin Faculty of Software Engineering and Computer Systems ITMO University Saint Petersburg, Russian Federation [e-mail]

Roman Abramovich Faculty of Software Engineering and Computer Systems ITMO University Saint Petersburg, Russian Federation [e-mail]

Alexey Platonov Faculty of Software Engineering and Computer Systems ITMO University Saint Petersburg, Russian Federation [e-mail]

Abstract — The use of deep neural networks in information retrieval significantly improves its effectiveness, but negatively affects the performance of the process. To deal with this, we propose a new ranking model that uses the deep neural network of the "Transformer" architecture (in particular, BERT) for efficient information retrieval. In accordance with the proposed approach, contextualized vector representations are extracted from documents during indexing, after which these representations are clustered for each independent token. The resulting clusters reflect different meanings of the words and are indirectly used as inverted index keys. The values represent the documents in which these contextualized word meanings occur, along with the distances from each document to the contextualized embedding. Thus, after the indexing process, we obtain an index containing pre-calculated distances between the contextualized meanings of dictionary elements and documents. This approach helps us avoid the performance overhead of calculating distances online. At the search stage, the query is transformed into a set of contextualized vectors representing each query token, which allows us to use these vectors to retrieve most semantically close neighbor-tokens and use them to extract relevant documents from the index. This way of searching for contextualized embeddings consumes less memory and is more performant due to the use of an inverted index.

Keywords — search engine, transformer, BERT, inverted index, optimization, vocabulary mismatch, word sense disambiguation.

I. Introduction

Pre-trained neural networks make it possible to effectively use complex models with less effort to train them to solve various kinds of problems. Information retrieval is no exception, in this area for a long-time simple algorithms were used that showed high performance, but relatively low quality of search. The use of machine learning makes it possible to significantly improve the quality characteristics of the search, but due to the need to perform a large number of operations, i.e. high algorithmic complexity, this leads to performance losses [1]. In this regard, modern search engines use two stages of retrieving relevant documents [2]. At the first stage, simple and effective algorithms are used that screen out most of the candidates, and at the second stage, neural networks are used to determine the relevance of the remaining documents more accurately. Thus, the speed of simple algorithms and the quality of complex ones are combined. But such an architecture has drawbacks: the documents obtained at the first stage are retrieved without understanding the semantics of the texts, and potentially relevant documents are skipped due to a vocabulary mismatch between the query and documents dictionaries [3, 4].

The paper presents an approach to building an inverted index of a search engine using a neural network of the

"Transformer" architecture, aimed at overcoming the above disadvantages. The paper also considers the solution to the problem of using polysemous words by considering their context. The peculiarity of the approach is that the distances from the elements of the dictionary, taking into account the context, to the documents are calculated at the indexing stage using the neural model, and the search is performed by the index, as a result of which the search is performed quickly and efficiently based on the semantics of the text.

II. Related Work

A. Vector Representation

The work presented by Zamani et al. introduced Standalone Neural Ranking Model (SNRM) [5], an approach for mapping documents to sparse vector representations. This allows the use of an inverted index, resulting in high search speed and comparatively low memory consumption. However, in practice, it turned out that the effectiveness of SNRM is significantly inferior to modern state-of-the-art approaches.

Unlike SNRM, we use dense vector BERT-based representations. However, they also have their limitations. So, for their search, k-nearest neighbors (KNN) algorithms with linear complexity can be used, which is unacceptable for large amounts of data used in information retrieval. An acceptable solution is to use algorithms of the approximate nearest neighbor (ANN) class [6], which allow a small loss of accuracy with an increase in speed by several orders of magnitude. Their disadvantage, depending on the specific implementation, is either high memory consumption or suboptimal performance. In this work, we use the Hierarchical Navigable Small Worlds (HNSW) [7] algorithm based on proximity graphs. Graph-based methods give the best performance so far. And HNSW is one of the fastest implementations of such methods [8]. The disadvantage of this method is that it takes a lot of time to build the data structure, but this is not critical for us, since this happens at the indexing stage.

B. BERT

To convert a document into a semantic vector space, the BERT [9] model is used, which shows the state-of-the-art results in many NLP tasks.

Models SparTerm [10] and it's successor SPLADE [11] also use BERT to build an inverted index with regard to token's contexts and vocabulary mismatch problem.

They use BERT to create a sparse term importance distribution for the whole dictionary for each passage at the indexing time. They do so by extracting contextualized

vectors for each token in the passage and computing its importance with every other token in the dictionary.

Despite the fact that their approach solves the same problems as ours, it requires much more computational resources during indexing as BERT is used not only to extract contextualized vectors, but also to compare these vectors with the entire vocabulary.

Authors of [12] introduce a new concept called "late interaction" with their ColBERT model. It is based on deep contextualized embeddings of document and query tokens, but with the late interaction method they were able to pre-compute document's embeddings offline in order to provide an effective end-to-end retrieval model.

Although our approach shares the same goal to pre-compute all the necessary document embeddings offline, we aim to build an inverted index as the output of our algorithm, while ColBERT relies on using dense vector-similarity search libraries, such as faiss [13], to find relative documents at a query processing time. That also means that using our approach all the term-document scores will be computed offline, while ColBERT still needs to compute scores between document and query online.

C. BERT's optimization

BERT model is computationally expensive. Many researchers optimize it using distilling [14], compression [15], and pruning [16]. We decided to go by changing the architecture, so that BERT is not used to search for similarity score between a query and a document online but is used to calculate it when building the inverted index. Using BERT online is only needed to find contextualized query token vectors, which will not significantly impact performance due to small query sizes. Moreover, to speed up this process, we use DistilBERT, which is 40% smaller, 60% faster, and retains 97% of the language understanding capabilities compared to the base BERT.

D. Contextual Word Sense Disambiguation

There are many polysemous words in document and query dictionaries. The different meanings of a word depend on the contexts in which the word is used and can be distinguished with their help. There are methods that assign different vector representations to polysemous words depending on their context [17]. This is also used in our algorithm, the keys of the inverted index will not be tokens, but the contextualized senses of these tokens. Thus, documents from the inverted index will be retrieved not by a specific token, but by its sense related to a specific context, which is meant in the query.

III. Inverted Index Construction

The proposed approach is based on using BERT to find similarities between a query and a document. This model helps to represent a document or a query in a multidimensional semantic space, using which one can find the distance or otherwise similarity between a document and a query, taking into account the meaning of the texts.

However, the use of deep neural networks is accompanied by performance losses, which can be critical in the direct interaction of the user with the search engine. In view of this, a distinctive feature of the proposed approach is that it involves the use of a neural network only during the construction of the index. This is achieved due to the special structure of the inverted index, which makes it possible to

store all the information necessary for searching. Also, the index is built in such a way that documents are searched for by contextualized meanings of words. This process is carried out in several stages.

A. Getting Contextualized Vector Representations

The first stage is preparatory. On it, for all tokens of each document obtained after preprocessing, windows of a given size are extracted, which are tokens and their contexts. So for a window length of 3 and the sentence "ITMO University is located in Saint-Petersburg", the sets will be as follows: [itmo, university], [itmo, university, locate], [university, locate, saint-petersburg], [locate, saint-petersburg]. Next, the windows are passed to the BERT model to find their vector representations. The resulting contextualized vectors are stored in the key-value database along with the ID of the document to which the passed window belongs. Pairs (document ID, vector) for the same token are appended, not replaced. This completes the preparatory phase. Fig. 1 illustrates the described process.

t1 doc_id=_ Ik-

t2 doc id= -

t3 doc id= L

tn doc id=_

Fig. 1. Preparation of vector representations

This stage is auxiliary, and its results are necessary for the subsequent stages.

B. HNSW Index Building

The contextualized vectors obtained at the previous stage for each token represent its meaning in some context. However, it is highly likely that some vectors will represent the same meaning, and to be more precise, the vectors will be divided into groups in the semantic space, each of which will represent a specific context value of the token. To divide into such groups (clusters), X-Means clustering is used in the work, since it can dynamically determine the number of clusters up to a given boundary. The boundary equal to 8 was chosen empirically and will be refined in future work. Next, for the resulting clusters, their centroids are calculated. The centroid vector represents one of the contextualized token senses. After that, the token, the cluster identifier (which is the cluster serial number for a particular token), and the resulting centroid are stored in the HNSW index.

Fig. 2 illustrates the described process.

Fig. 2. HNSW index building process

The resulting HNSW index is needed both for building an inverted index and during an online search.

C. Inverted Index Building

This stage is the final one, on which the formation of the inverted index is performed.

The vector representations of the contextual senses of the token obtained at the first stage are passed to the HNSW index built in the second stage to search for their nearest neighbors. The number of neighbors equal to 5 was chosen empirically and will be refined in future work. During the evaluation, a compromise will be chosen between the quality of the search and the speed of indexing and searching. The extracted neighbors are semantically close to the original contextual sense of the token, which means that they can also represent the sense of the document to which the token belongs. Although neighbors may contain different tokens, it is important that their semantic meaning be the same, as represented through embeddings. Thus, the vocabulary mismatch problem is solved.

In the next step, distances are calculated between the vector representations of documents and the centroid vectors of the neighbors of the considered contextualized vectors. Distances are found using the dot product. The resulting scores, along with the document IDs, are written as values into an inverted index against the keys, which are (token, cluster ID) pairs. The process is repeated until the scores for all prepared contextualized vectors are indexed.

Fig. 3 illustrates the described process.

Inveted i ndex

token clusterjd doc id=score

Key-value DB

t1

doc_d=E,...

IV. Search Process

The search process starts in the same way as the indexing process. For each token of the input query obtained after preprocessing, windows of the fixed size are extracted. Then, each window is processed with the following algorithm:

• Obtain vector representation by passing window to the BERT model.

• Get nearest neighbours from the HNSW index using obtained vector.

• For each pair (token, cluster ID) returned from HNSW, extract list of candidate-documents from inverted index.

• If a document is already present in a candidate list, merge it with the new candidate by summing their

At the second step of this algorithm, HNSW search can return tokens different, but semantically close to the original token from the query. Thus, the vocabulary mismatch problem is being solved both during indexing and search time.

Next steps are no differ from the classical search algorithms. We sort the list of candidate-documents by their resulting score and return top-N documents as the searching result.

Fig. 4 illustrates the described process.

Take top N

I token_1:cluster_id HJI token_n:cl uster_id f

HNSW

tokenEluster_id:centroid_vector

Fig. 3. Inverted index building process

Fig. 4. Search process for a given Query

V. Methodology

A. Dataset

Many information retrieval works use the MS MARCO [18] dataset from Microsoft, which was released in 2016 and adapted for retrieval in 2018. The dataset contains 8.8 million web page passages and 3.2 million documents that were collected from Bing search engine logs. Each query is associated with a document or multiple documents by

relevancy judgments. The development set contains 6980 requests.

Thus, the dataset makes it possible to solve both the passage retrieval tasks and the document retrieval tasks. Thanks to this, the system is evaluated on real data, which means that the evaluation results will more objectively show how the search engine will work in production environment.

It is also important to note that this dataset is often used by researchers in information retrieval, which makes it easy to compare the evaluation of the proposed solutions.

B. Implementation

To test the algorithms, we implemented IR-stand, which has one interface for working with different information retrieval algorithms, as well as for their evaluation. The algorithm described in this paper has also been added to it. We use the Anserini Toolkit1 as the baseline.

Kotlin is used to implement the stand. This is a modern and convenient programming language that gives access to the whole variety of technologies available in the JVM platform. To save computing resources, the PyTorch implementation of DistilBERT2 from the popular transformers library3 is used. Deep Java Library4 is chosen to access DistilBERT from Kotlin code. Apache Lucene5 was chosen as the implementation of the inverted index, as it is a mature technology that has shown its effectiveness, for example, in systems such as Elasticsearch. As an interface to the stand, the Command Line Interface (CLI) is implemented.

C. Hardware

To build the index and perform searches, we used a computer with 32 GB of RAM and an RTX A4000 Mobile GPU which has 8 GB of memory.

VI. Results of Experiments

The implementation of the algorithm can be found in the public repository6.

As a result of applying the proposed approach to 500 thousand documents from the MS MARCO dataset, a dictionary consisting of approximately 200 thousand tokens was obtained. Each token had an average of 1-2 contextualized values. In fact, this indicates that the dictionary was not cleaned well enough and there are many unique tokens in it. The HNSW index size is 1 GB, and the inverted index is 150 MB, while the HNSW index for ANN search is 1.8 GB. Moreover, when new documents appear, the vector index will hardly grow, since most of the vectors will be reused. Only the inverted index will be padded, which has a simple structure, due to which the data gain will also be small. Thus, the vector index will have a constant size starting from some value. An analytical estimation of the growth dynamics of the usual vector index and the one proposed by us is shown in fig. 5.

1https://github .com/castorini/anserini

2https://huggingface.co/sentence-transformers/msmarco-distilbert-dot-v5

3https://github.com/huggingface/transformers

4https://github .com/deepj avalibrary/dj l

5https://github.com/apache/lucene

6https://github.com/itmo-ml/IR-stand

Dataset size, thousands of documents

Fig. 5. Approximate growth dynamics of the ANN vector index and our vector index

However, as a result of experiments, it was found that the current implementation of the algorithm shows a worse search quality than with an approximate vector search using the MRR@10 metric. So, the MRR@10 for the algorithm was 0.075, while for the ANN search it was 0.156. A non-zero MRR is a proof of concept, but algorithm refinement is required to achieve better quality. This can be either fine-tuning parameters or changing important parts, such as a neural model or a clustering algorithm.

The execution time for 134 search queries for an index of 500 thousand documents is 7.8 seconds, and for the ANN index - 3.4 seconds, while for the KNN index - 78 seconds. That is, in terms of performance, the algorithm is close to ANN algorithms, but it also takes up less memory. Moreover, as the number of documents grows, the search speed will not change much, since our HNSW index is static, and the search on the inverted index works very efficiently.

Indexing time for the proposed approach is 18 hours, and for ANN algorithm 1 hour. This difference is due to the complexity of the index. However, there is an opportunity for further optimization of the process, for example, through better parallelization.

VII. Future Work

In the future, the proposed approach will be analyzed and refined.

We also plan to review and compare different versions of neural networks, as well as approximate neighbor search algorithms and their implementation.

Moreover, for a more objective result, we will test the algorithm on other datasets, while using not only MRR, but also Recall and DCG.

As possible modifications, various clustering algorithms can be considered.

CONCLUSION

In this paper we presented a possible solution to both vocabulary and token's context accounting problems in the information retrieval tasks, which works quite efficiently and consumes relatively little memory.

By using modern language models of the "Transformer" architecture we were able to extract contextualized vector

representations from both documents and queries, cluster them into the finite amount of contextual meaning embeddings for each independent token and use them to build an inverted index and perform search queries. As a result, the index takes up less memory than for the ANN algorithm and works quite efficiently.

References

[1] S. Hofstätter, A. Hanbury, Let's measure runtime! Extending the IR replicability infrastructure to include performance aspects, 2019, arXiv:1907.04614.

[2] R.-C. Chen, L. Gallagher, R. Blanco, J. S. Culpepper, Efficient costaware cascade ranking in multi-stage retrieval, Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2017, pp. 445-454. doi: 10.1145/3077136.3080819.

[3] G. W. Furnas, T. K. Landauer, L. M. Gomez, S. T.Dumais, The vocabulary problem in human-system communication, Commun. ACM 30, 1987, pp. 964-971.

[4] L. Zhao, Modeling and solving term mismatch for full-text retrieval, Ph.D. thesis, Carnegie Mellon University, 2012.

[5] H. Zamani, M. Dehghani, W. B. Croft, E. Learned-Miller, J. Kamps, From neural re-ranking to neural ranking: Learning a sparse representation for inverted indexing, Proceedings of the 27th ACM International Conference on Information and Knowledge Management, 2018, pp. 497-506.

[6] W. Li, Y. Zhang, Y. Sun, W. Wang, M. Li, W. Zhang,X. Lin, Approximate nearest neighbor search on high dimensional data— experiments, analyses, and improvement, IEEE Transactions on Knowledge and Data Engineering, 2019, pp. 1475-1488.

[7] Y. A. Malkov, D. A. Yashunin, Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs, IEEE transactions on pattern analysis and machine intelligence, 2018 pp. 824-836.

[8] M. Aumüller, E. Bernhardsson, A. Faithfull, ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms. Information Systems 2019. DOI: 10.1016/j .is.2019.02.006.

[9] J. Devlin, M.-W. Chang, K. Lee, K. Toutanova, Bert: Pre-training of deep bidirectional transformers for language understanding, 2018, arXiv:1810.04805.

[10] Y. Bai, X. Li, G. Wang, C. Zhang, L. Shang, J. Xu,Z. Wang, F. Wang, Q. Liu, Sparterm: Learning term-based sparse representation for fast text retrieval, 2020, arXiv:2010.00768v1.

[11] T. Formal, B. Piwowarski, S. Clinchant, Splade: Sparse lexical and expansion model for first stage ranking, 2021, arXiv:2107.05720v1.

[12] O. Khattab, M. Zaharia, Colbert: Efficient and effective passage search via contextualized late interaction over BERT, 2020, arXiv:2004.12832v2.

[13] J. Johnson, M. Douze, H. Jegou,Billion-scale similarity search with gpus, 2017, arXiv:1702.08734.

[14] V. Sanh, L. Debut, J. Chaumond, T. Wolf, Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter, 2019, arXiv:1910.01108.

[15] O. Zafrir, G. Boudoukh, P. Izsak, M. Wasserblat, Q8bert: Quantized 8bit bert, 2019, arXiv:1910.06188.

[16] P. Michel, O. Levy, G. Neubig, Are sixteen heads really better than one?, In Advances in Neural Information Processing Systems, 2019.

[17] B. Athiwaratkun, A. Wilson, A. Anandkumar, Probabilistic FastText for multi-sense word embeddings, in: Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), Association for Computational Linguistics, Melbourne, Australia, 2018, pp. 1-11. doi:10.18653/v1/P18-1001.

[18] T. Nguyen, M. Rosenberg, X. Song, J. Gao, R. M. Saurabh Tiwary, L. Deng, Ms marco: A human generated machine reading comprehension dataset., In Proceedings of the Workshop on Cognitive Computation: Integrating neural and symbolic approaches, 2016, CEUR Workshop Proceedings, Vol. 1773.

Издание: 2024 IEEE 18th International Conference on Application of Information and Communication Technologies (материалы конференции)

A Sparsifier Model for Efficient Information

Retrieval

Viacheslav Dobrynin Faculty of Software Engineering and Computer Systems ITMO University Saint Petersburg, Russian Federation [e-mail]

Mark Sherman Faculty of Software Engineering and Computer Systems ITMO University Saint Petersburg, Russian Federation [e-mail]

Roman Abramovich Faculty of Software Engineering and Computer Systems ITMO University Saint Petersburg, Russian Federation [e-mail]

Alexey Platonov Faculty of Software Engineering and Computer Systems ITMO University Saint Petersburg, Russian Federation [e-mail]

Abstract—The constant development of dense neural models leads to improved search quality. At the same time, it is crucial to adapt these models to meet performance requirements. Solutions like SPLADE or SparseEmbed address this by solving the ranking task, whereas our work proposes addressing the simplified task of sparsifying dense vector representations. This approach facilitates the faster adaptation of new dense models for use with efficient inverted indexes. The importance of the independence property for sparse space features, achieved through the use of iVAE, is demonstrated. Additionally, the model is trained to maintain the ranking properties of the dense model, which in our case was a BERT model. As a result, the obtained model showed search quality close to the original BERT model. The proposed sparsification approach can be applied to other tasks requiring sparse spaces by adding new or replacing existing properties of the sparse space. Thus, the paper describes the main aspects of a sparsifier model applied to the task of information retrieval.

Keywords—sparsity, inverted index, neural networks, independence

I. Introduction

Modern search engines have a two-stage architecture. This is due to the need to combine the speed and quality of search on huge amounts of data, to the limit on the entire Internet. At the first stage, simple and fast algorithms are used, which significantly reduce the number of candidate documents to hundreds or thousands. The resulting documents are then ranked using a complex model that gives good ranking quality, but is relatively slow, so you cannot use this model alone for the entire dataset. However, this approach is limited in search quality due to the fact that a simple algorithm at the first stage can miss some of the relevant documents, since it does not take into account the semantics of texts.

Solutions like ColBERT(end-to-end) [1] implement one-step search, significantly improving search quality (MRR@10=36.7) compared to BM25 [2] (MRR@10=19.5), which is often used as the first-stage retrieval in classical architectures. The main innovation in this model is the mechanism of late interaction, which involves encoding query and document tokens into vector representations used to calculate similarity. On the other hand, this increases the required number of calculations, so the disadvantage of this solution is the time delay of 458 ms compared to 62 ms for BM25. Moreover, the resulting vectors take up a significant amount of memory.

To solve this problem, it is also proposed to switch to a single-stage architecture and use deep neural networks, but the key difference will be the use of an inverted index, just like in SparseEmbed [3]. However, instead of using contextualized vectors, we propose a sparsifier model for dense vector representations by imposing necessary constraints for the subsequent use of the resulting sparse vectors in an inverted index. The following constraints used for this task are: sparsity and independence of vector components, maintaining consistency and relative distances between sparse and dense vectors. This article proposes an approach that allows to obtain the efficiency of the inverted index while maintaining the quality of dense models.

II. Related Work

The approach of using sparse vectors for an inverted index, as proposed in a standalone neural ranking model (SNRM) [4], resulted in accelerated search and achieved reasonably good search quality. However, the emergence of search models utilizing the "Transformer" architecture marked a significant breakthrough in search quality. Among the state-of-the-art solutions that leverage transformer models and inverted indexes are the SParse Lexical AnD Expansion (SPLADE) model [5-7] and the SparseEmbed model. Both models address the task of learning to rank.

However, our approach instead trains to derive sparse representations from dense ones, possessing the necessary properties. The main advantage of this approach is that as new models based on dense representations emerge, our method allows for easy conversion of these dense representations into sparse ones, thereby obtaining the benefits of modern solutions while adapting them for use with an inverted index. In this work, we explore the application of our approach for information retrieval, but it can be potentially applied to other tasks that require sparse vectors, thus serving as a generic model for sparsifying dense representations.

All the constraints imposed on the resulting sparse space will be discussed in the methodology section. However, let us consider the sources that are important in the context of such a property as the independence of vector components. Independent Component Analysis (ICA) [8] is a primary method for obtaining independent components from a mixture of values. ICA methods can be categorized based on two criteria: the type of mixing and the ratio of the number of original signals to their mixtures. In the first case, the mixing

function plays a key role - it can be either linear or nonlinear. In the second, methods can be divided into three types:

• Complete - the number of mixtures and original sources is the same.

• Undercomplete - the number of sources is less than the number of mixtures.

• Overcomplete - the number of sources is greater than the number of mixtures.

Since we aim to identify individual features from a mixed dense space obtained using a neural network, which is generally a nonlinear function, nonlinear ICA methods are necessary. It is also crucial for us that these methods can handle the overcomplete case, as sparse vectors with independent components have a larger dimensionality than dense ones.

When considering nonlinear ICA methods, only those that guarantee identifiability should be considered, which ultimately implies the existence of a single function for source recovery. If multiple such functions exist, the method is not identifiable [9].

While identifiability for linear ICA was proven long ago, it was only recently established for the nonlinear case. The Identifiable Variational Autoencoder (iVAE) model, described in [10], was the first to demonstrate strict identifiability for the nonlinear case. The authors showed that, in general, the problem is not identifiable. However, by relaxing the properties of the data, identifiability is achievable. Specifically, they were able to prove identifiability by assuming that the latent variables are conditionally independent given an observed auxiliary variable. This can be almost any observation, such as the time point for temporal signal separation tasks or more abstractly, a class label. Thus, the iVAE framework was adopted in our work, allowing us to achieve component independence under reasonable constraints.

III. Methods

The main idea of the proposed approach is to sparsify existing dense vector representations, which possess the necessary properties, for their subsequent use with an inverted index. The model is a combination of a dense backbone and an encoder obtained through the training of iVAE, as shown in Fig. 1.

I I I ■ I I I I

Sparse vector, z

Percentile-Based Feature Selection

v_J

Independent components

f--\

Encoder

s__

Dense vector, x

C \

Backbone (BERT)

D = (Sample document)

Fig. 1. Sparsification of a dense vector

A. Properties of the Sparse Space

During the sparsification process, the following constraints are imposed on the resulting latent space: sparsity and independence of vector components, preservation of consistency and relative distances between sparse and dense vectors. Let us examine each of these constraints.

1) The Property of Sparsity

The use of sparse vectors allows for efficient storage of documents in an inverted index and fast retrieval based on a query. The query is also sparse. Similar to SPLADE, we minimize the number of floating-point operations (FLOPS) to define the sparsity of the vectors. This approach enables the sparsification of the space by gradually reducing the average number of floating-point operations required to compute a document score [11].

Although L1 regularization is also suitable for achieving sparsity, it has been proven to result in a less balanced index compared to FLOPS.

Since in variational autoencoders the values of the latent space are sampled from a certain probabilistic distribution, using regularization to achieve sparsity will not yield explicit zero values but will approximate some of them to zero. To achieve sparsity, we select the most important negative values (values below the 10th percentile) and positive values (values above the 90th percentile).

2) The Property of Preserving Relative Distances

As the backbone of our model, we use BERT [12] fine-tuned on a ranking task. When transitioning to a new space, it is essential to preserve these properties; therefore, we developed a regularization function that maintains the relative distances between vectors. Since we use the dot product to determine the relevance score between a query and a document, the relative dot products of the dense and sparse vectors are approximated.

To achieve this, the pairwise absolute distances are first calculated for both the sparse and dense vectors. The obtained absolute distances are converted to relative distances by dividing by the squared lengths of the vectors. Then, the difference between the obtained relative distances is calculated, followed by the Frobenius norm, and the result is normalized by the batch size. The final result can be represented by the following formula:

j _ ^ lym yn ( XXT___ZZT A . -.

Ld ^J^^Ug^rf ^(zzrfj

where X represents the dense vector representations, Z represents the sparse vector representations, and N is the batch size.

The resulting regularization function allows us to preserve the order between documents in the new space, which is a central aspect of the ranking task.

3) The Property of Independence

In the resulting sparse space, it is necessary to achieve the property of component independence due to the use of the inverted index. Typically, terms from a document are used as keys in this data structure, and the search is performed based on that keys. Each individual term can belong to different documents with different contexts, so the search for it should

be performed independently of other terms in the document or, in other words, independently of other components. Moreover, independence provides a rationale for combining search results for any considered components into a single aggregate value.

In contrast, the coordinates of a dense vector are closely related and intertwined in meaning. All coordinates taken together reflect a certain overall concept, hence the task is to disentangle the dependent components into independent ones.

The property of independence will be ensured by the iVAE model, which combines the ideas of a variational autoencoder and identifiable ICA through the use of auxiliary variables on which the obtained latent variables depend.

As auxiliary variables, we chose the cluster labels of the dense document vectors, thereby achieving independence of the components in the sparse space while maintaining their dependence on the semantic clusters of the documents.

We follow the iVAE approach and use a modified Evidence Lower Bound (ELBO) loss as the loss function to ensure independence.

4) The Property of Consistency

When training the latent space, it is necessary to preserve the same useful properties that exist in the original space. Here, we benefit from using an autoencoder, which allows us to implement these requirements through a reconstruction loss. The idea is that the model will incur penalties for losing the properties of the original space.

Just as with the property of independence, to ensure consistency, we use the ELBO loss proposed in iVAE.

B. Loss

To achieve the above properties in the sparse space, we combine the losses together:

L = aiLELBO + a2Ldist + a3LFLOPS (2)

where a1, a2 and a3 are coefficients that allow adjusting the contribution of each individual loss to the overall loss.

C. Scoring

Ranking documents by relevance to a query requires obtaining relevance scores. To do this, the query and document must first be encoded using the trained model. Then, the relevance score is calculated as the dot product between the query and document vectors:

score(q,d) = S,i|>o9i • d; (3)

where q is the query vector, d is the document vector, and the summation is performed over the non-zero elements in the query vector.

The dot product is easily implemented when using an inverted index, which was the main reason for choosing it.

D. Inverted Index

The proposed model was designed so that the resulting vectors could be used with an inverted index. This data structure significantly reduces search time and memory consumption. Moreover, the sparser the vectors, the stronger this effect.

We use the positions of each independent component as the keys of the inverted index and pairs (docId, component weight) as the values of the index.

For an encoded query, the non-zero components are taken, and the corresponding entries in the index are found. Then, by multiplying the weights and summing them to obtain the overall result, we fully replicate the dot product (3).

IV. Results

We trained the model on 300,000 documents from the MS MARCO passage dataset [13]. Evaluation was performed using the popular benchmarking tool BEIR [14], which provides several datasets for evaluating search systems. The SciFact dataset, containing around 5,000 documents, was chosen for quick checks. Since the task is to approximate our solution to the baseline in terms of quality, this dataset proved to be sufficient for us. In BEIR, search quality is assessed using metrics such as NDCG, MAP, Recall, and Precision, among others. To evaluate the independence between the components of the spaces, we used the Pearson product-moment correlation coefficient matrix and the average correlation value for the resulting matrix.

As the backbone, we use the msmarco-distilbert-dot-v51 BERT encoder from Sentence Transformers. This model was chosen because BERT is an implementation ofthe transformer architecture, which has performed well on many applied tasks. Distillation allows for a reduction in computational resources with only a slight loss in quality. The model was fine-tuned to predict similarity between sentences using the dot product, which is an important property for us to preserve in our new space.

The dimensionality of the latent space is 3000 components. The models were trained using PyTorch, PyTorch Lightning, and HuggingFace transformers on a single Tesla V100 GPU with 32GB of memory. The batch size varied between 128 and 384. The number of epochs was 10. The learning rate was 1e-4, and AdamW [15] was used as the optimizer.

It is important to note that the main objective of our work is to develop a sparsification model for application to an inverted index, which demonstrates search quality corresponding to the dense model used for sparsification. Thus, for msmarco-distilbert-dot-v5, the quality for the NDCG@10 metric is 0.59, and we need to approximate this value. The value of the mean correlation (mean_cor), indicating the level of component independence, is 0.06.

The following results were obtained during the experiments with our model:

• NDCG@10=0.51

• mean_cor=0.027

The results indicate that the search quality is slightly inferior to the baseline. This can be explained by the fact that we nullify components with the smallest values, which also carry some meaning. To address this issue, it is necessary to nullify components during the training process to ensure that all useful information is concentrated in the most significant components. Although the independence measure has improved, further enhancement is required in this area, which will be the subject of future research.

1https://huggingface.co/sentence-transformers/msmarco-distilbert-dot-v5

V. Conclusion

This paper proposes an approach for sparsifying dense vector representations for their subsequent use in search. The model combines the advantages of transformer architecture models and the use of sparse space. The resulting sparse vectors improve the property of independence, enabling their use for search in an inverted index. This allows for significantly faster search and reduced memory consumption.

Although the quality is close to the baseline, there is still room for improvement, which will be the subject of future research.

Potentially, the proposed approach, with appropriate modifications, could also be useful in other fields where sparsification is needed.

References

[1] O. Khattab and M. A. Zaharia, "ColBERT: Efficient and effective passage search via contextualized late interaction over BERT," in Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, 2020.

[2] S. E. Robertson and H. Zaragoza, "The probabilistic relevance framework: BM25 and beyond," Found. Trends Inf. Retr., vol. 3, pp. 333-389, 2009.

[3] W. Kong, J. M. Dudek, C. Li, M. Zhang, and M. Bendersky, "SparseEmbed: Learning sparse lexical representations with contextual embeddings for retrieval," in Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2023.

[4] H. Zamani, M. Dehghani, W. B. Croft, E. G. Learned-Miller, and J. Kamps, "From neural re-ranking to neural ranking: Learning a sparse representation for inverted indexing," in Proceedings of the 27th ACM International Conference on Information and Knowledge Management, 2018.

[5] T. Formal, B. Piwowarski, and S. Clinchant, "SPLADE: Sparse lexical and expansion model for first stage ranking," in Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2021.

[6] T. Formal, C. Lassance, B. Piwowarski, and S. Clinchant, "SPLADE v2: Sparse lexical and expansion model for information retrieval," ArXiv, abs/2109.10086, 2021.

[7] T. Formal, C. Lassance, B. Piwowarski, and S. Clinchant, "From distillation to hard negative sampling: Making sparse neural IR models more effective," in Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2022.

[8] A. Hyvarinen and E. Oja, "Independent component analysis: algorithms and applications," Neural networks, vol. 13, no. 4-5, pp. 411-430, 2000.

[9] I. Khemakhem, R. P. Monti, D. P. Kingma, and A. Hyvarinen, "ICE-BeeM: Identifiable conditional energy-based deep models," ArXiv, abs/2002.11537, 2020.

[10] I. Khemakhem, D. P. Kingma, and A. Hyvarinen, "Variational autoencoders and nonlinear ICA: A unifying framework," in International Conference on Artificial Intelligence and Statistics, 2019.

[11] B. Paria, C. Yeh, N. Xu, B. Poczos, P. Ravikumar, and I. E. Yen, "Minimizing FLOPs to learn efficient sparse representations," ArXiv, abs/2004.05665, 2020.

[12] J. Devlin, M. Chang, K. Lee, and K. Toutanova, "BERT: Pre-training of deep bidirectional transformers for language understanding," in North American Chapter of the Association for Computational Linguistics, 2019.

[13] D. F. Campos, T. Nguyen, M. Rosenberg, X. Song, J. Gao, S. Tiwary, R. Majumder, L. Deng, and B. Mitra, "MS MARCO: A human generated MAchine Reading Comprehension dataset," ArXiv, abs/1611.09268, 2016.

[14] N. Thakur, N. Reimers, A. Ruckle, A. Srivastava, and I. Gurevych, "BEIR: A heterogenous benchmark for zero-shot evaluation of information retrieval models," ArXiv, abs/2104.08663, 2021.

[15] I. Loshchilov and F. Hutter, "Decoupled weight decay regularization," in International Conference on Learning Representations, 2017.

Издание: Научно-технический вестник информационных технологий,

механики и оптики (журнал)

НАУЧНО-ТЕХНИЧЕСКИЙ ВЕСТНИК ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ _

% январь-февраль2025 Том25№1 http://nlv.ifmo.ru/ научно технический вестник

I/ITMO SCIENTIFIC AND TECHNICAL JOURNAL OF INFORMATION TECHNOLOGIES, MECHANICS AND OPTICS И НЮ ОРМЛ ЦН D H НЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ПШИКИ

January-February 2025 Vol. 25 No 1 http://nlv.ifmo.ru/en/ i i дм i

ISSN 2226-1494 (print) ISSN 2500-0373 (online)

doi: 10.17586/2226-1494-2025-25-1-61-67

Efficient sparse retrieval through embedding-based inverted index construction

Viacheslav Yu. Dobrynin1^, Roman K. Abramovich2, Alexey V. Platonov3

1,2,3 ITMO University, Saint Petersburg, 197101, Russian Federation

1 Shift Lab LTD, London, W3 7XS, Great Britain

2 Payler Ltd, London, E14 4QA, Great Britain

1 [e-mail], https://orcid.org/0009-0004-3056-8403

2 [e-mail], https://orcid.org/0009-0005-5397-2772

3 [e-mail], https://orcid.org/0000-0002-8485-1296

Abstract

Modern search engines use a two-stage architecture for efficient and high-quality search over large volumes of data. In the first stage, simple and fast algorithms like BM25 are applied, while in the second stage, more precise but resource-intensive methods methods, such as deep neural networks, are employed. Although this approach yields good results, it is fundamentally limited in quality due to the vocabulary mismatch problem inherent in the simple algorithms of the first stage. To address this issue, we propose an algorithm for constructing an inverted index using vector representations combining the advantages of both stages: the efficiency of the inverted index and the high search quality of vector models. In our work, we suggest creating a vector index that preserves the various semantic meanings of vocabulary tokens. For each token, we identify the documents in which it is used, and then cluster its contextualized embeddings. The centroids of the resulting clusters represent different semantic meanings of the tokens. This process forms an extended vocabulary which is used to build the inverted index. During index construction, similarity scores between each semantic meaning of a token and documents are calculated which are then used in the search process. This approach reduces the number of computations required for similarity estimation in real-time. Searching the inverted index first requires finding keys in the vector index, helping to solve the vocabulary mismatch problem. The operation of the algorithm is demonstrated on a search task within the SciFact dataset. It is shown that the proposed method achieves high search quality with low memory requirements. The proposed algorithm demonstrates high search quality, while maintaining a compact vector index whose size remains constant and depends only on the size of the vocabulary. The main drawback of the algorithm is the need to use a deep neural network to generate vector representations of queries during the search process which slows down this stage. Finding ways to address this issue and accelerate the search process represents a direction for future research. Keywords

inverted index, vocabulary mismatch problem, neural networks, vector representations, clusterization For citation: Dobrynin V.Yu., Abramovich R.K., Platonov A.V. Efficient sparse retrieval through embedding-based inverted index construction. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2025, vol. 25, no. 1, pp. 61-67 doi: 10.17586/2226-1494-2025-25-1-61-67

УДК 004.89

Эффективный разреженный поиск с помощью построения инвертированного индекса на основе эмбеддингов

Вячеслав Юрьевич Добрынин1^, Роман Константинович Абрамович2, Алексей Владимирович Платонов3

1'2'3 Университет ИТМО, Санкт-Петербург, 197101, Российская Федерация

1 Shift Lab LTD, Лондон, W3 7XS, Великобритания

2 Payler Ltd, Лондон, E14 4QA, Великобритания

1 [e-mail] https://orcid.org/0009-0004-3056-8403

2 [e-mail], https://orcid.org/0009-0005-5397-2772

3 [e-mail], https://orcid.org/0000-0002-8485-1296

© Dobrynin V.Yu., Abramovich R.K., Platonov A.V., 2025

Аннотация

Введение. Современные поисковые системы используют двухэтапную архитектуру для эффективного и качественного поиска по большим объемам данных. На первом этапе применяются простые и быстрые алгоритмы, такие как ВМ25, а на втором — более точные, но ресурсоемкие методы, например глубокие нейронные сети. Несмотря на то, что такой подход показывает хорошие результаты, он фундаментально ограничен по качеству из-за проблемы несовпадения словарей, что присуще простым алгоритмам первого этапа. Метод. Для решения проблемы ограничений качества поиска, в настоящей работе предлагается алгоритм построения инвертированного индекса с использованием векторных представлений. Представленный подход объединяет преимущества обоих этапов: эффективность инвертированного индекса и высокое качество поиска при использовании векторных моделей. Предложено создание векторного индекса, сохраняющего различные семантические значения токенов словаря. Для каждого токена определяются документы, в которых он используется, после чего его контекстуализированные эмбеддинги кластеризуются. Центроиды полученных кластеров представляют различные семантические значения токенов. Таким образом, формируется расширенный словарь, который применяется для построения инвертированного индекса. При построении индекса вычисляются оценки близости между каждым семантическим значением токена и документами, что затем используется в процессе поиска. Это позволяет сократить количество вычислений для оценки близости в режиме реального времени. Поиск по инвертированному индексу требует нахождения ключей в векторном индексе, что позволяет решить проблему несовпадения словарей. Основные результаты. Работа алгоритма продемонстрирована на задаче поиска в наборе данных SciFact. Показано, что предлагаемый метод обеспечивает высокое качество поиска при низких требованиях к объему памяти. Обсуждение. Разработанный алгоритм демонстрирует высокое качество поиска, при этом он поддерживает компактный векторный индекс, размер которого остается неизменным и определяется исключительно размерами словаря. Основным недостатком алгоритма является необходимость использования глубокой нейронной сети для генерации векторных представлений запроса в процессе поиска, что замедляет этот этап. Поиск путей для решения данной проблемы и сокращения времени поиска представляет собой направление дальнейших исследований. Ключевые слова

инвертированный индекс, проблема несоответствия словарей, нейронные сети, векторные представления, кластеризация

Ссылка для цитирования: Добрынин В.Ю., Абрамович Р.К., Платонов А.В. Эффективный разреженный поиск с помощью построения инвертированного индекса на основе эмбеддингов // Научно-технический вестник информационных технологий, механики и оптики. 2025. Т. 25, № 1. С. 61-67 (на англ. яз.). 10.17586/2226-1494-2025-25-1-61-67

Introduction

Modern search systems typically use a two-stage architecture to balance between speed and search quality while working with massive volumes of data such as the entire Internet. At the first stage, simple and fast algorithms are used to reduce the number of candidates to hundreds or thousands. At the second stage, these candidate documents are re-ranked using more complex models that provide high-quality results but require by an order of magnitude more processing power. Consequently, those models cannot be efficiently applied to the entire dataset due to performance constraints. However, this approach has limitations in search quality, as the algorithm at the first stage can miss relevant documents by not accounting for the semantics of the texts.

nd-to-end solutions, such as Contextualized Late Interaction over Bidirectional Encoder Representations from Transformers (BERT) (ColBERT), implement search using a single stage, allowing for significantly improved search quality. For example, Best Matching 25 (BM25), which is often used as a first-stage ranking model, achieves a Mean Reciprocal Rank (MRR)@10 of 19.5 on the Microsoft Machine Reading Comprehension (MS MARCO) dataset, whereas ColBERT (end-to-end) achieves an MRR@10 of 36.7 [1]. The main innovation in the ColBERT architecture is the late interaction mechanism which independently encodes query and document tokens into vector representations that are used for computing relevance scores. This approach allows us to independently

pre-compute document embeddings at the offline stage and store them in a vector index for further retrieval. However, it also requires a significant amount of resources to store the indexed documents and process incoming queries, making it challenging to apply to large-scale datasets.

To address this problem, we propose implementing a single-stage architecture algorithm that uses an inverted index as the primary structure for indexing and searching. However, unlike classical approaches like BM25, our method constructs an inverted index using deep neural networks, allowing for a more precise capture of the context of tokens and their relevance to the documents.

In this paper, we present a new method that leverages the efficiency of an inverted index while maintaining the search quality of vector models. Our approach combines the advantages of inverted index structure with the scoring provided by deep learning models that deeply understand token semantics.

Related works

The Sparse Neural Ranking Model (SNRM), introduced by Zamani et al. in 2018 [2], was one of the first works that tried to integrate deep neural networks with traditional inverted indexing. By using sparsity constraints, SNRM is trained to generate high-dimensional sparse embeddings for both queries and documents, which can be later used to construct an inverted index. This model was able to significantly improve search quality, but, at the same time, it has certain limitations related to its architecture, such as

loss of token interpretability, fixed dimensionality of output vectors, and the need to process queries through the model which significantly increases computational resources at query time.

SparTerm, introduced by Bai et al. in 2020 [3], was designed to improve traditional sparse term-based representations by using deep models like BERT [4]. By generating dense contextualized embeddings that capture the semantics of each term and using a gating controller to sparsify the resulting vectors, SparTerm is able to construct an inverted index using original vocabulary terms. By doing so, SparTerm improves semantic matching in the inverted index, while keeping the interpretability and efficiency of classical methods.

The Sparse Lexical And Expansion (SPLADE) model by Formal et al. [5], builds upon SparTerm by simplifying its architecture. The main idea is that instead of using a gating controller to achieve sparsity, the authors would employ a log-saturation function and a sparsifying regularization at the training stage to induce sparsity in the output vectors, thus addressing one of the key limitations of SparTerm, allowing for end-to-end training and reducing computational complexity.

ColBERT [1] and ColBERTv2 [6] can be considered an alternative approach to generating sparse vectors, as instead of building an inverted index, it focuses on algorithmic optimizations to reduce computational resources required for search. In this work, the authors introduce the concept of "late interaction" which separates the encoding of queries and documents from computing relevance scores between them. By employing an Approximate Nearest Neighbor (ANN) index with the Facebook AI Similarity Search [7] library and vector compression techniques like Product Quantization [8], combined with offline indexing, ColBERT allows for significantly reducing resources required for storing and processing search queries. However, despite achieving high search quality and requiring significantly fewer resources than traditional vector search methods, ColBERT still requires more computational resources during query time and greater storage space for document embeddings than inverted index models.

The model SparseEmbed [9] was inspired by both SPLADE and ColBERT. By generating sparse vectors using the same approach as SPLADE and storing dense embeddings for each input token, SparseEmbed constructs an inverted index with original vocabulary terms, where the values stored in the index are the dense representations of the tokens. At search time, it uses dense embeddings of activated tokens to compute relevance scores efficiently. This approach improves context capture compared to SPLADE by using dense representations and is more efficient than ColBERT as it requires linear time relative to the number of activated terms rather than quadratic time. SparseEmbed achieved an MRR@10 score of 39.2 on the MS MARCO dataset, which is slightly the score of 39.7 achieved by ColBERTv2. However, it still requires storing dense vectors for each token and document and computing contextualized embeddings at query time, increasing the computational resources needed during search.

The work Sparse Transformer Matching (SPARTA) [10] offers an efficient neural ranking method that addresses

the limitations of dense vector search in open-domain question answering. Unlike similar models that rely entirely on dense embeddings, SPARTA learns sparse representations that can be implemented as an inverted index, allowing for scalable retrieval without the need for expensive ANN search. SPARTA captures finegrained relevance information by focusing on token-level interactions between queries and documents, allowing for high-quality matching while maintaining efficiency. This approach significantly improves retrieval performance compared to dense models and achieves state-of-the-art results across multiple open-domain question answering tasks.

This paper is a continuation of the algorithm proposed in [11]. The main improvement is in the way we select contextualized embeddings from documents. Instead of computing context based on a sliding window algorithm as in our earlier approach, we now utilize contextualized vector representations of tokens within the entire document. This change allows us to perform more effective clustering and capture different semantic meanings of words. By constructing an inverted index using these embeddings, we address the resource-intensive computations required during search, achieving efficiency comparable to traditional methods while capturing the semantic richness highlighted in models like SPARTA and SPLADE.

In the next sections we describe the whole algorithm with the new upgrades.

Description of the Proposed Algorithm

The usage of transformer models allows for significantly improved search quality due to their ability to capture complex semantic relationships between tokens in the text. However, these models also require substantial computational resources, making them far less practical to use directly in large-scale search systems.

In contrast, the usage of inverted indexes is a standard practice in modern production search systems due to their scalability, high performance, and relatively low memory usage.

Inverted indexes are able to efficiently retrieve documents based on exact query term matching, however, when queries and documents use different words with similar meanings, traditional inverted indexes fail to retrieve relevant documents, which is known as the vocabulary mismatch problem.

To address this problem, we propose a novel method of inverted index construction, where the index terms are selected based on their semantic similarity, rather than exact term matching. By doing so, we aim to resolve the vocabulary mismatch problem by incorporating semantic understanding into the index building process.

Our method involves training a compact vector index that contains embeddings representing different semantic meanings for each token in the vocabulary. To generate these embeddings, we cluster the contextualized token embeddings across all documents in the dataset. This allows us to capture the various contexts in which a token appears, effectively representing its multiple semantic meanings.

Index construction

As search systems face the requirement to work with massive data volumes, the efficient implementation of the indexing stage is a crucial concern. Caching is one of the most common optimization techniques to speed up data processing, and the one that we adopted to optimize our indexing algorithm.

As we build both a compact vector index and an inverted index using vector representations extracted from documents, it is a logical step to cache those representations for both processes. Our vector representations are obtained using a deep neural network based on the transformer architecture. More specifically, it is a bidirectional encoder that considers each token context by looking at both preceding and following tokens. This allows for a deeper semantic understanding of words depending on their context, which is a critical factor for calculating the relevance score between tokens and documents.

The result of this preparation stage is a collection that contains mappings of document identifiers to their corresponding contextualized embeddings, represented as pairs (doc_id, contextualizedembs), which is later used for obtaining semantic clusters for tokens, building a vector index and an inverted index.

The index construction is divided into two main stages: first, we use vector representations and clustering to build an expanded vocabulary that captures different semantic contexts of tokens, and second, we use this expanded vocabulary to construct the inverted index.

The core idea of the proposed approach is to construct a fixed Hierarchical Navigable Small World (HNSW) [12] index that contains vector representations of all vocabulary tokens in their various semantic contexts across indexed documents. This index allows us to efficiently distinct different token contexts at both indexing and query time. Since a token can have multiple meanings depending on its usage, capturing these variations is essential for semantic search.

The first step is quite similar to building a classical inverted index. For each token, we collect and store all the document ids in which this token appears, ending up with a map of token id to the list of document ids. This collection will later be used to gather contextualized embeddings for each token across different contexts.

Then, for each token in the map, the following steps are performed:

1. Collect Contextualized Embeddings from all the documents that the token appears in. As the token might have different semantic meanings based on the context, by collecting token embeddings from all documents we make sure to account for all of them. At this step, we use the (doc_id, contextualized_embs) map prepared at the preparation step to speed up the process and avoid re-calculating embeddings for each document over and over.

2. Clustering: As soon as we have all token embeddings from each document it appears in, we perform clustering on these embeddings using the A>means++ algorithm [13]. As a result, we get a small set of cluster centroids that group similar embeddings and represent different semantic meanings that this token has.

3. Store semantic centroids: Finally, we store the resulting centroids to the HNSW index, where they can be later used for building an inverted index. With each centroid, we also store the associated metadata required for further steps: a source token and a unique cluster identifier (token_id, clustered). This process is depicted in Fig. 1. The constructed HNSW index enables efficient nearest neighbor search based on semantic similarity during both indexing and query processing. By using those centroids to build an inverted index we address the vocabulary mismatch problem and allow for a search based on semantics and thus more agile, but still interpretable as we save corresponding token and cluster identifiers with each embedding in both vector and inverted index.

At this step, we combine the results from all the previous steps in order to construct the inverted index.

To do so, we iterate over the collection of document ids mapped to their contextualized embeddings generated at the preparation step. For each contextualized token embedding e in the document, we search for its nearest semantic centroids from the HNSW index built at the previous step.

The relevance score between contextualized embeddings of a document and retrieved semantic centroids is calculated using the MaxSim operator as defined in [1]. Thus, in our work, most of the computations of the "late interaction" mechanism are performed at the indexing stage, which speeds up the search process compared to ColBERT. Finally, these relevance scores are then stored in the inverted index along with the document ids, where the keys are represented as pairs of token and cluster identifiers (tokenid, clustered).

The whole inverted index construction process is presented in Fig. 2.

This algorithm allows us to effectively expand the vocabulary of the inverted index based on a deep semantic understanding of the source texts. The vocabulary mismatch problem is addressed by searching for nearest semantic clusters for each token, allowing for including semantic clusters from different tokens to the resulting posting list even if they do not appear in the document. The inverted index remains efficient and interpretable, as it still relies on tokens from the original vocabulary augmented with cluster identifiers representing different semantic meanings.

HNSW [token : cluster id: centroid]

centroids