Processing Strings 109x Faster Than Nvidia on H100
Выпущена StringZilla v4 — первая версия библиотеки для обработки строк с поддержкой CUDA, которая ускоряет вычисления на GPU. Она обеспечивает до 500 гигаопераций в секунду для расчёта расстояний Левенштейна и других метрик схожести строк, что в 109 раз быстрее решений на NVIDIA H100. Библиотека оптимизирована для больших объёмов данных в базах данных, биоинформатике и информационном поиске, включая алгоритмы с аффинными штрафами за разрывы и мини-хэширование.
Новые функции включают хэш-функции на основе AES, генераторы псевдослучайных строк и алгоритмы сортировки для работы с коллекциями строк. StringZilla использует SIMD-инструкции на CPU и GPU, поддерживает несколько архитектур и языков программирования. Библиотека распространяется под лицензией Apache 2.0 и доступна через pip, предлагая надёжный и быстрый базис для масштабируемых workloads.
Комментарии (23)
After publishing this a few days ago, 2 things have happened.First, it tuned out that StringZilla scales further to over 900 GigaCUPS around 1000-byte long inputs on Nvidia H100. Moreover, the same performance is obviously accessible on lower-end hardware as the algorithm is not
The Theoretical Limitations of Embedding-Based Retrieval
Ключевая идея:
Методы ретривала на основе эмбеддингов (EBR) не могут точно воспроизвести полный ранжир по BM25 из-за фундаментальных ограничений геометрии евклидовых пространств.
Проблема:
EBR приближает BM25 через косинусное сходство векторов запроса и документа. Однако BM25 зависит от частоты терминов (TF) и обратной частоты документов (IDF), что нельзя точно закодировать в фиксированном векторе.
Результаты:
- Нижняя граница ошибки: Для коллекции из n документов минимальная ошибка приближения BM25 через EBR составляет Ω(1/n).
- Практический эксперимент: На MS MARCO даже идеальные эмбеддинги (обученные для имитации BM25) показывают значительное падение качества (nDCG@10 ↓ на 15–25%).
Вывод:
EBR полезен как компрессия, но не заменяет точные методы. Гибридные системы (EBR + BM25) остаются необходимыми для высокой точности.
Комментарии (34)
- Все сжатия информации (включая эмбеддинги) потерянны, и «обед безплатен» не работает, потому что лучший способ зависит от задачи.
- Теоретические оценки, экстраполирующие полином на тысячи измерений, вызывают сомнение: рост может быть экспоненциальным.
- Плотные векторы ограничены размерностью 4 k, поэтому идеал — «разреженная семантическая» модель вроде SPLADE или гибридные схемы.
- На практике работают многовекторные и late-interaction подходы (ColBERT), но они всё ещё уступают BM25 по ранжированию.
- Реальные системы идут по пути параллельных каналов: плотные, разреженные, BM25 → объединение, дедупликация, переранжирование LLM.