PaperlayerView exact revision on arXiv

Source-linked AI summary

Index-Free Dynamic Edge Retrieval with Energy-Tail-Aware Partial Scans

Mohammad Arif Rasyidi, Omar Alhussein

arXiv:2609.01820v1cs.IR

TL;DR

Dynamic MIPS needs fast queries without the costly index maintenance associated with changing datasets. ETAR reduces full-scan work through energy-aware candidate generation and exact reranking, achieving 99.2% Recall@10 at a 4.5× speedup over exact scanning in static experiments.

  • Problem

    Full-vector scanning simplifies dynamic updates but queries every coordinate of every stored vector, making cost grow with dataset size and vector dimension.

  • Method

    ETAR selects high-energy query coordinates, applies tail-aware approximate scoring, and exactly reranks a bounded candidate set while avoiding auxiliary-index maintenance.

  • Results

    99.2% Recall@10 at 0.31 ms/query yields a 4.5× speedup over exact scanning across nine static datasets, while streaming workloads maintain 100% Recall@10 without index rebuilds.

  • Takeaways & Limitations

    ETAR offers a practical middle ground between full-vector scanning and indexed retrieval for dynamic MIPS workloads.

  • Takeaways & Limitations

    Edge-device validation is limited to one ARM-based mobile device and static synthetic workloads.

Abstract

from arXiv · show

Dynamic maximum inner-product search (MIPS) returns the $K$ stored vectors with the largest dot products with a query while allowing the dataset to change through insertions, replacements, and deletions. For edge retrieval, the challenge is to achieve high recall and fast queries without making updates expensive. Full-vector scanning keeps updates simple but compares each query with every stored vector, while indexed methods reduce query cost at the expense of maintaining additional structures during updates. We propose ETAR, an index-free method that reduces query work while preserving simple updates. ETAR keeps the query coordinates with the largest squared values until they cover most of its total squared magnitude and treats the rest as a low-magnitude tail. It estimates similarity from the retained coordinates using a compact lower-precision representation, corrects for skipped coordinates, and reranks a fixed number of candidates using full-precision vectors. Across five runs on nine static datasets, ETAR averages 99.2% Recall@10, the fraction of exact top-10 results recovered, while running over 4$\times$ faster than exact scanning at a representative setting. This speedup also extends to an ARM-based mobile device, where ETAR is up to 6.9$\times$ faster across four synthetic distributions. Under five streaming workloads, it maintains 100% Recall@10 at every measured point without index rebuilds. Overall, ETAR offers a practical middle ground for dynamic MIPS by reducing query cost while retaining simple, index-free updates. Code is available at https://github.com/arasyi/etar-mips.

I. INTRODUCTION

ETAR is an index-free method for dynamic maximum inner-product search that reduces query work while preserving the update simplicity of full-vector scanning. It combines query-dependent coordinate selection, tail-aware candidate scoring, and fixed-budget exact reranking.

  • I. INTRODUCTION: Full-vector scanning computes complete dot products against every stored vector, but its cost grows with dataset size and vector dimension.The approach directly modifies stored vectors during updates and maintains no auxiliary search index.
  • I. INTRODUCTION: ETAR reduces dynamic MIPS query work while preserving simple updates by avoiding auxiliary search-index maintenance.It targets datasets that change through new observations, removals, or replacements, where full-vector scanning is attractive for its update simplicity but costly at query time.
  • I. INTRODUCTION: ETAR uses a two-stage pipeline that generates a likely top-K shortlist before reranking candidates with exact dot products.Its query-dependent coordinate selection retains the largest-energy coordinates, while tail-aware scoring accounts for skipped coordinates.
  • I. INTRODUCTION: The evaluation spans nine static datasets, five streaming workloads, an ARM-based mobile device, and up to one million stored vectors.It measures retrieval quality, query latency, update cost, maintenance overhead, and memory footprint against exact scanning and indexed ANN baselines.

II. SYSTEM MODEL AND PROBLEM DESCRIPTION · III. ETAR DESIGN

The paper models dynamic MIPS over an evolving table of active vectors and introduces ETAR as an index-free method for approximate retrieval with local updates and reduced query, update, and maintenance costs. ETAR scans rows using query-selected coordinates in an 8-bit representation, then reranks a fixed candidate set with higher-precision vectors.

  • II. SYSTEM MODEL AND PROBLEM DESCRIPTION: The retrieval operator returns indices of the min{L, |B|} highest-scoring rows, resolving ties deterministically.It returns row indices rather than score values.
  • II. SYSTEM MODEL AND PROBLEM DESCRIPTION: Dynamic MIPS retrieves active rows with the largest inner-product scores q^T x_i from the current table.The table contains occupied rows and metadata, while only rows in the active set participate in queries.
  • II. SYSTEM MODEL AND PROBLEM DESCRIPTION: The dynamic table supports inserts, deletions, and replacements, while stale or deleted rows remain stored but cannot be returned.Inserts append active rows; deletes mark rows inactive; replacements delete the old row and append a fresh active row.
  • II. SYSTEM MODEL AND PROBLEM DESCRIPTION: ETAR approximates the exact target over the current active set while keeping ordinary updates local and reducing query, update, and maintenance costs.The objective is to maintain the vector table under the update stream while answering queries over active rows.
  • III. ETAR DESIGN: ETAR is index-free: it builds no graph, tree, or inverted file and scans table rows directly during candidate generation.The candidate-generation pass avoids auxiliary indexing structures.
  • III. ETAR DESIGN: Candidate generation scores rows using only query-selected coordinates in an 8-bit view.This reduces the representation and computation used during the direct table scan.
  • III. ETAR DESIGN: The main ETAR configuration reranks a fixed candidate count with full dot products on 32-bit stored vectors, while ETAR-LM uses row-major 8-bit codes for reranking.These are the two described precision choices for the final reranking stage.

A. Representation and Dynamic Tables · B. Query Pipeline

ETAR combines compact, update-friendly row representations with query-adaptive partial scanning, tail-aware candidate scoring, and fixed-budget reranking. Its ETAR and ETAR-LM configurations differ only in whether shortlisted rows are reranked from 32-bit vectors or reconstructed 8-bit codes.

  • A. Representation and Dynamic Tables: ETAR stores a column-major signed 8-bit scan view with row scales and metadata, plus a row-major full-precision view for exact reranking.ETAR-LM replaces the full-precision reranking view with a row-major copy of the 8-bit codes.
  • A. Representation and Dynamic Tables: Column-major scan storage streams only selected coordinate columns, whereas row-major storage supports full-coordinate access for shortlisted-row reranking.The layouts match ETAR’s two query phases: all-row candidate generation and limited-row reranking.
  • A. Representation and Dynamic Tables: Row-wise encoding lets inserts and replacements be processed independently without retraining a global quantization codebook.Updates append new representations and metadata, while deletions mark rows inactive and ordinary updates cost O(d).
  • B. Query Pipeline: ETAR keeps the top-R active rows by tail-aware score and reranks them to return the top-K results, with R ≥ K.ETAR-LM uses the same candidate set but reranks with row-major 8-bit reconstructions, which can change the final order and reduce recall.
  • B. Query Pipeline: ETAR selects the smallest number of highest-energy query coordinates meeting retained-energy target ρ, subject to cap hmax, and treats the remainder as skipped coordinates.If the target is not reached before the cap, ETAR uses h = hmax.
  • B. Query Pipeline: ETAR corrects selected-coordinate partial scores with a query-dependent, row-scaled estimate of skipped-coordinate contributions based on active-row coordinate-energy statistics.The correction uses a diagonal second-moment approximation and scales the allowance according to shortlist selectivity.
  • B. Query Pipeline: The tail-aware score is a heuristic candidate score rather than a certified bound on the true dot product, with clipping constants controlling correction magnitude.The method uses a Gaussian upper-tail approximation based on the shortlist size and sets ϵ = 10^-12 for numerical stability.

C. Design Rationale and Cost

ETAR controls query cost and recall through the retained-energy target ρ, coordinate cap hmax, and reranking budget R. Its partial scans reduce arithmetic when h(q) ≪ d and small fixed R suffice, at the cost of additional storage that ETAR-LM reduces.

  • Resource controls: ETAR uses ρ to select coordinates and R to control reranking, trading candidate-generation cost and missed scores against candidate coverage and recall.The coordinate count is h(q)=|H|, bounded by hmax; smaller ρ lowers work but can miss vectors, while larger R costs more and improves the chance of including exact top-K indices.
  • Calibration: For a target recall, ρ, R, and hmax can be calibrated on heldout queries with exact top-K labels.For ETAR-LM, candidate coverage and final recall should be evaluated separately because 8-bit reranking may reorder candidates.
  • Query cost: Candidate arithmetic is O(|A|h(q)) plus O(Rd) reranking instead of O(|A|d) full dot-product arithmetic, while remaining linear in |A|.The benefit depends on h(q) ≪ d and a small fixed R.
  • Memory cost: ETAR uses C(5d+13) bytes versus about 4|A|d bytes for a packed exact table, while ETAR-LM uses C(2d+13) bytes to reduce the storage overhead.ETAR adds row-major 32-bit and column-major 8-bit views plus 13 bytes of metadata per row; ETAR-LM uses 8-bit views for both layouts.

IV. EXPERIMENTAL SETUP

The experiments assess ETAR’s retrieval quality, query latency, streaming update cost, and latency–memory scaling with dataset size. Unless noted, tests use K = 10 and single-threaded online operations, with server experiments on an AMD EPYC 9655 CPU.

  • ETAR is evaluated for retrieval quality, query latency, streaming update cost, and latency and memory scaling with dataset size.
  • Unless otherwise noted, experiments use MIPS with K = 10 and measure single-query or single-operation online latency under single-threaded execution.
  • Server experiments run on an AMD EPYC 9655 CPU, with each configuration repeated five times and latencies averaged across runs excluding setup and evaluation overhead.

A. Static Retrieval

The static-retrieval evaluation uses nine capped datasets spanning synthetic distributions and ANN-Benchmarks workloads. It compares ETAR variants with exact scanning, quantized scanning, and indexed references, including a controlled Android-device evaluation.

  • Datasets: The benchmark covers nine datasets capped at N = 50,000 vectors and Q = 1,000 queries, including four synthetic d = 256 distributions and five ANN-Benchmarks datasets.The synthetic sets are dense Gaussian, sparse Gaussian, mixed heavy-tail, and norm-heavy; the real datasets are SIFT, GloVe, LastFM, Fashion-MNIST, and NYTimes.
  • Configurations: ETAR is compared with exact full-precision scanning, full-coordinate 8-bit scanning without reranking, and indexed references across sweeps of ρ and R.The sweep uses ρ ∈{0.80, 0.90, 0.96}, R ∈{50, 100, 200}, hmax = 128, row-wise 8-bit codes, tail-aware scoring, and exact reranking; ETAR-LM uses row-major 8-bit reranking.
  • Mobile evaluation: On a Samsung Galaxy S25 Ultra, single-threaded AArch64/NEON implementations of ETAR and ETAR-LM are compared with exact scanning on the four synthetic distributions.Both ETAR variants use ρ = 0.90 and R = 100; after 100 warm-up queries, each method is measured five times for 10 s with rotated execution order.

B. Streaming Retrieval

Streaming evaluation interleaves queries with inserts, replacements, deletions, and maintenance across five workloads, using dynamic-table policies and periodic or native baseline updates. A separate high-churn stress test measures ETAR’s compaction and table-maintenance costs under delete- and replacement-heavy workloads.

  • B. Streaming Retrieval: Five streaming workloads start with 50,000 vectors of dimension d = 256 and run for 5,000 simulation steps, with recall measured every 250 updates.The workloads are append-only growth, query-heavy drift, balanced churn, burst ingest, and sliding window.
  • B. Streaming Retrieval: ETAR and ETAR-LM use ρ = 0.96 and R = 100, maintain tail statistics over active rows, and use the dynamic-table policy starting with C = 1.25N.Compaction follows deletions or replacements after deleted rows reach 10% of occupied rows and at least 1,024 rows.
  • B. Streaming Retrieval: The workloads use specified query, insertion, replacement, and deletion mixes, including burst ingest phases that switch to 20/70/5/5 for 100 steps every 500 steps.Sliding window cycles through insertion, oldest-item deletion, and querying.
  • B. Streaming Retrieval: Dynamic Faiss references rebuild every 500 updates, whereas HNSWlib uses native updates with M = 32, efconstruction = 200, efsearch = 512, marked deletions, and no scheduled rebuilds.Faiss deletions use external live-set filtering until rebuild, and replacements delete the old item before inserting the new one.
  • B. Streaming Retrieval: A high-churn stress experiment runs for 20,000 steps with 40% queries, 15% insertions, 15% replacements, and 30% deletions to measure compaction and table-maintenance costs.It uses the same initial size, dimension, query configuration, and baseline update policies as the main streaming experiment.

C. Memory and Scaling Profiles · D. Metrics

The paper profiles analytical memory, process RSS, and scaling across dataset sizes using fresh-process measurements, while defining recall, candidate coverage, and timing metrics for evaluation. Results are summarized through recall–latency tradeoffs and parameter sweeps across nine static datasets.

  • C. Memory and Scaling Profiles: Analytical memory includes vector views, scan codes, row metadata, norms, deletion markers, identifiers, and allocated capacity.Process RSS is recorded before and after construction, but its build delta is implementation-level rather than an exact device-memory requirement.
  • C. Memory and Scaling Profiles: Scaling uses dense Gaussian data with d = 256, Q = 50, and N from 50,000 to 1,000,000, measuring each method-size pair in a fresh process.ETAR and ETAR-LM use C = N, ρ = 0.96, R = 200, and hmax = 192; exact scanning, Faiss HNSW, and Faiss IVF are also included without recall matching.
  • D. Metrics: For each query, recall compares the returned set bIK(q; A(q)) with the exact top-K target IK(q; A(q)) over the active set.The effective target size is Kq = min{K, |A(q)|}.
  • D. Metrics: Mean recall–latency tradeoffs are reported across nine static datasets.The supplied figure caption identifies the scope of the comparison but does not provide numerical cell values.
  • D. Metrics: ETAR’s mean recall–latency sweep across nine datasets varies the candidate parameter R and retained-energy threshold ρ.The supplied figure caption identifies the sweep dimensions but does not establish numerical winners or values.
  • D. Metrics: Diagnostic candidate coverage replaces the returned set with ETAR’s candidate set, while ETAR-LM’s coverage–recall gap reflects 8-bit quantization reordering during final scoring.Coverage is reported where this distinction is informative.
  • D. Metrics: Event time includes queries, updates, and maintenance, whereas initial construction from 50,000 rows is measured separately and excluded from event time.Query latency and maintenance latency are also reported.

V. RESULTS AND DISCUSSION · A. Static Retrieval

Across nine static datasets, ETAR achieves high Recall@10 with substantially lower latency than exact scanning, including 99.2% recall at a 4.5× speedup. Its performance varies with query sparsity, tail correction, reranking precision, and the recall–latency setting.

  • A. Static Retrieval: 99.2% Recall@10 at 0.31 ms/query gives ETAR a 4.5× speedup over exact scanning across nine static datasets.At ρ = 0.90 and R = 100, exact scanning reaches perfect Recall@10 at about 1.42 ms/query; ρ = 0.96 and R = 200 reaches 99.97% Recall@10 at 0.37 ms/query.
  • A. Static Retrieval: On mobile, ETAR achieves 97.59–100% mean Recall@10 with 1.76–6.88× speedups, while ETAR-LM achieves 96.37–99.42% with 1.86–7.14× speedups.The largest gains occur on sparse Gaussian data.
  • A. Static Retrieval: At R = 100, increasing ρ from 0.80 to 0.90 to 0.96 raises Recall@10 from 95.42% to 99.19% and 99.79%, while latency increases from 0.282 to 0.312 and 0.325 ms/query.Lower ρ risks skipping important score contributions, whereas larger R can recover candidates at additional reranking cost.
  • A. Static Retrieval: At ρ = 0.90 and R = 100, dense Gaussian queries select 114.4 coordinates and reach 97.19% Recall@10, whereas 10%-sparse queries select 12.3 and reach 99.68%.Recall depends on how query magnitude is distributed across coordinates, not dimension alone.
  • A. Static Retrieval: ETAR is faster than exact scanning on all nine datasets, with speedups up to 9.83×, although an indexed baseline is faster on three datasets.Gains are smaller on lower-dimensional LastFM and GloVe because their full dot products involve fewer coordinates.
  • A. Static Retrieval: Removing the tail term lowers average Recall@10 from 99.19% to 98.17%, while mixed heavy-tail data improves from 94.17% to 99.98% with correction.A fixed-tail variant with α = 0.10 nearly matches the derived correction on average while running slightly faster.
  • A. Static Retrieval: With deterministic tie-breaking and exact reranking, ETAR’s 99.19% candidate coverage matches final recall, while ETAR-LM reaches 97.19% because of 8-bit reranking quantization.ETAR-LM uses the same candidate sets as ETAR.

B. Streaming Retrieval · C. Compaction Stress Test · D. Memory and Scaling

Across streaming, high-churn, and scaling tests, ETAR reduces query and event costs while keeping updates simple, with ETAR-LM additionally reducing storage at some recall cost. ETAR’s latency and memory advantages persist as datasets grow, without frequent index rebuilds.

  • B. Streaming Retrieval: 0.523 ms/query and at most 0.007 ms per update make ETAR faster to query and update than HNSWlib, while Faiss HNSW rebuilds average 21.3 s.ETAR and ETAR-LM build in under 0.05 s; Faiss IVF also requires periodic retraining and rebuilds.
  • C. Compaction Stress Test: 4.24 s total event time lets ETAR outperform HNSWlib’s 16.25 s under 20,000 high-churn steps, while ETAR compacts only once.The workload uses 30% deletes and 15% replacements; ETAR’s compaction takes 31.4 ms, compared with 19.2 ms for ETAR-LM.
  • C. Compaction Stress Test: ETAR-LM compacts once in 19.2 ms under high churn and uses less storage than ETAR, but incurs a moderate recall loss.Both ETAR variants compact only once during the 20,000-step workload.
  • D. Memory and Scaling: At N = 50,000, ETAR uses 61.7 MiB, or 1.26× exact, whereas ETAR-LM uses 25.0 MiB, or 0.51× exact.ETAR primarily reduces query computation; ETAR-LM also reduces storage at the cost of moderate recall loss.
  • D. Memory and Scaling: At one million rows, ETAR takes 12.3 ms/query at 100% Recall@10 versus 30.8 ms for exact scanning, while ETAR-LM takes 12.0 ms at 97.4%.Fixed HNSW and IVF settings achieve lower recall at this scale.
  • D. Memory and Scaling: Query latency grows approximately linearly with N for exact scanning and both ETAR configurations.RSS build delta also grows roughly linearly, with ETAR-LM remaining smallest at 500.6 MiB.

VI. LIMITATIONS AND FUTURE WORK · VII. CONCLUSION

ETAR reduces dynamic-MIPS query work without auxiliary-index maintenance by concentrating computation on high-energy query coordinates and reranking bounded candidates. Its practical benefits are tempered by linear scan scaling, heuristic and maintenance limitations, fixed evaluation settings, and limited edge-device validation.

  • VI. LIMITATIONS AND FUTURE WORK: ETAR latency grows linearly with N because it scans all active rows, limiting scalability as the dataset expands.
  • VI. LIMITATIONS AND FUTURE WORK: The heuristic score does not guarantee every true top-K row enters SR, and ETAR-LM may reorder candidates during 8-bit reranking.
  • VI. LIMITATIONS AND FUTURE WORK: Resizing and compaction can cause maintenance spikes, while parameter settings do not adapt to workload changes.
  • VI. LIMITATIONS AND FUTURE WORK: The evaluation uses fixed indexed-baseline settings and one periodic rebuild policy, excludes other scan-based MIPS methods, and has limited edge-device validation.
  • VII. CONCLUSION: ETAR reduces full-scan query work without auxiliary-index maintenance while preserving simple updates through high-energy coordinate focus and bounded candidate reranking.The conclusion characterizes ETAR as achieving high recall and substantial speedups across server and mobile experiments.
  • VII. CONCLUSION: ETAR maintains 100% Recall@10 across streaming workloads without index rebuilds, while ETAR-LM extends the design to lower-storage retrieval.
  • VII. CONCLUSION: ETAR offers a practical middle ground between full-vector scanning and index-based retrieval for dynamic MIPS workloads.
Loading 2609.01820v1…