Abstract
Similarity search over large embedding sets is the retrieval substrate beneath retrieval-augmented generation [1] and vector databases; at billion scale it is a systems problem whose reference point is FAISS [2], with exact-attention cost addressed by IO-aware kernels such as FlashAttention [3]. This paper presents HOF SWIFT Scalable Information Retrieval (SIR): a decomposition of similarity search into five composable stages — Score, Weight, Isolate, Fit, Transform (SWIFT) — expressed as higher-order functions over atomic operations in the functional-programming tradition [4, 5, 6], each stage mapped to the hardware target that runs it best (CPU/GPU/TPU). The architecture is a design; its scaling is given as illustrative arithmetic under stated constants, and the open question it isolates is precise: whether a controller can select the task-relevant sparse subset accurately and cheaply enough to make per-query cost track the subset rather than the corpus. FAISS [2] is the baseline it is built to be measured against.
1. Introduction
Retrieval over embedding sets underpins semantic search, recommendation, and RAG [1].
Exhaustive nearest-neighbor search costs O(N·D) per query for N vectors of dimension D; the
production answer is approximate nearest neighbor (ANN) indexing — inverted files, product
quantization, graph indexes — consolidated and GPU-accelerated in FAISS [2]. Separately, the
quadratic cost of exact attention in a transformer generator [7] is reduced without
approximation by IO-aware kernels such as FlashAttention [3]. These are the measured baselines a
retrieval architecture is positioned against. SWIFT SIR factors the retrieval pipeline so that each
stage is independently swappable and independently placed on hardware — and so that the one hard step,
sparse candidate selection, is named explicitly rather than folded into an index.
2. Related Work
Approximate nearest neighbor search. Billion-scale similarity search with GPU acceleration is what FAISS was built for [2]; FAISS and the IVF/HNSW/PQ family it packages are the reference baseline. SWIFT SIR reorganizes that work into hardware-placed stages; the claim is factoring, not a faster index a priori.
Efficient attention. FlashAttention [3] is the published, benchmarked technique for memory/IO-efficient exact attention, over the transformer backbone [7] — the prior art the Transform stage builds on.
Retrieval-augmented generation. RAG [1] couples a retriever with a generator; retrieval quality bounds generation faithfulness, and hallucination persists even with grounding [8]. This is the system context in which a stronger retriever pays off.
Functional composition. Expressing the pipeline as higher-order functions composed over atomic operations is the functional-programming tradition formalized by Backus [4], Hughes [5], and Strachey [6]. The contribution is applying that composition to a hardware-partitioned retrieval pipeline.
Signal detection for validation. Where the pipeline accepts or rejects a candidate, Signal Detection Theory [9] (d′, criterion β) gives the decision measurable structure — the applied psychophysics of the SWIFT validation stage, alongside the JND and Weber–Fechner scaling that govern the Score and Isolate thresholds.
3. The SWIFT Decomposition
Similarity search is expressed as five composed stages, each an Input–Process–Output transform [4, 5], independently swappable and independently placed on its best hardware target:
- Score (S) — Input: query embedding q, candidate set. Process: a sparse or blockwise scoring pass rather than a dense all-pairs product. Output: scored candidate subset.
- Weight (W) — Input: scored subset. Process: re-weight by context relevance. Output: weighted candidates.
- Isolate (I) — Input: weighted candidates. Process: route/prune to the top-relevance region. Output: a small working set.
- Fit (F) — Input: working set. Process: aggregate into hierarchical context windows. Output: context-fitted results.
- Transform (T) — Input: fitted results. Process: finalize (masking, mixed precision). Output: ranked retrieval.
The composition Transform ∘ Fit ∘ Isolate ∘ Weight ∘ Score is the higher-order function; each stage
is an atomic function [5, 6]. The factoring makes the pipeline's stages
placeable per hardware and makes the sparse-selection step (Score) a first-class, swappable component
— the step ANN indexing exists to solve, here exposed rather than hidden.
4. Illustrative Scaling
The efficiency argument is arithmetic: if the Score stage selects a sparse subset S ≪ N and later stages operate on a fixed top-k, per-query work tracks S, not N. The table below is [ILLUSTRATIVE] — arithmetic under chosen constants (embedding dim D=768, sparse fraction S=0.1% of N, top-k=1000):
[ILLUSTRATIVE — arithmetic under the stated constants]
| Dataset | N (embeddings) | Sparse subset S (0.1%) | Score-stage ops (S·D) |
|---|---|---|---|
| 1 GB | 10⁷ | 10⁴ | ≈ 7.7 × 10⁶ |
| 1 TB | 10¹⁰ | 10⁷ | ≈ 7.7 × 10⁹ |
| 1 PB | 10¹³ | 10¹⁰ | ≈ 7.7 × 10¹² |
This table lays out Dataset, N (embeddings), Sparse subset S (0.1%), Score-stage ops (S·D) across 3 rows.
The saving is a property of the 0.1% sparse fraction, which presupposes a Score stage that finds the 0.1% worth scoring without touching the rest. That selection is the substantive problem, and SWIFT's factoring is what makes it a named, measurable stage instead of an assumption buried in an index. The efficiency claim is therefore conditional and sharp: if a controller predicts the task-relevant subset at low overhead, retrieval cost is dominated by S; the measurement that settles it runs against FAISS [2] on a shared corpus.
5. Where Validation Is Grounded
Retrieval pipelines decide accept/reject on candidates, and that decision is a detection problem. Signal Detection Theory [9] gives it structure: the recall/precision trade-off is a criterion (β) shift along an ROC curve, and retriever quality separates into sensitivity (d′) versus threshold. This is the measurable core of the SWIFT validation stage — the point where the architecture meets a number.
Evidence & Scope
SWIFT SIR is a design with an isolated, testable question. The scaling figures are illustrative arithmetic under the stated constants; the decision layer is grounded in Signal Detection Theory [9]; and the head-to-head that settles the efficiency claim is a SWIFT-SIR-versus-FAISS [2] comparison on a shared corpus (top-k recall and latency for both), bounded by available compute. FAISS is the baseline; the Score stage is the variable that decides the outcome.
References
- Patrick Lewis et al. (2020). Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks. Advances in Neural Information Processing Systems (NeurIPS). arXiv:2005.11401. [RAG]
- Jeff Johnson et al. (2019). Billion-Scale Similarity Search with GPUs. IEEE Transactions on Big Data. arXiv:1702.08734. [FAISS.]
- Tri Dao et al. (2022). FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness. Advances in Neural Information Processing Systems (NeurIPS). arXiv:2205.14135.
- John Backus (1978). Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs. Communications of the ACM. [1977 ACM Turing Award Lecture]
- John Hughes (1989). Why Functional Programming Matters. The Computer Journal.
- Christopher Strachey (2000). Fundamental Concepts in Programming Languages. Higher-Order and Symbolic Computation. [Reprint of 1967 lecture notes]
- Ashish Vaswani et al. (2017). Attention Is All You Need. Advances in Neural Information Processing Systems (NeurIPS). arXiv:1706.03762.
- Ziwei Ji et al. (2023). Survey of Hallucination in Natural Language Generation. ACM Computing Surveys. arXiv:2202.03629.
- David M. Green & John A. Swets (1966). Signal Detection Theory and Psychophysics. Wiley.
