arXiv CSopen access

Leveraging I/O Stalls for Efficient Scheduling in ANNS

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

databases, sql, data management, storage

Leveraging I/O Stalls for Efficient Scheduling in ANNS Juncheng Zhang1 , Yuanming Ren1 , Yongkun Li2 , and Patrick P.C. Lee1 2 University of Science and Technology of China

1 The Chinese University of Hong Kong

arXiv:2605.19335v1 [cs.DB] 19 May 2026

Abstract

granularity that thread-level approaches cannot reach. Applying this idea in practice faces several challenges. First, a single update operation typically lasts much longer than the idle intervals available during search I/O stalls, making fine-grained task decomposition essential to fit update work within short idle periods without interfering with search. Second, it is non-trivial to determine when and how much update work can be safely scheduled, as I/O stall durations are inherently variable and further distorted by techniques such as dynamic I/O width and user-space caching [7, 24]. Third, even when update tasks complete within the estimated idle window, search-update co-execution degrades search latency due to workload- and runtime-dependent effects (e.g., cache pollution and varying workload sensitivity) that cannot be modeled analytically in advance. Keeping degradation within the user’s tolerance requires a runtime mechanism to monitor and adapt to these effects.

Disk-based graph indexes for approximate nearest neighbor search (ANNS) must serve latency-sensitive queries and throughput-demanding updates concurrently. We observe that over 40% of search-thread CPU time is spent stalling on disk I/O; such idle cycles are invisible to thread-level scheduling yet available for other work. We present LIOS (Leverage I/O Stall), a framework that executes index updates inside search-side I/O stall windows. LIOS introduces three techniques: (i) splitting each update into resumable subtasks small enough to fit within a single stall window; (ii) bounding the expected overrun of update subtasks to a given threshold; and (iii) dynamically adjusting the fraction of idle time devoted to updates to drive end-to-end search latency degradation toward a user-specified target. We integrate LIOS into two update-optimized ANNS systems, FreshDiskANN and OdinANN. LIOS achieves speedups of up to 2.68× in insertion and 2.18× in deletion, with search latency degradation maintained near the user-specified target.

We present LIOS (Leverage I/O Stall), a framework that co-executes search and update operations in graph-based ANNS systems by exploiting I/O idle cycles. LIOS introduces three key techniques: (i) fine-grained update decomposition, which breaks monolithic update operations into resumable, checkpoint-able subtasks at both inter-vector and intra-vector granularities so that each piece fits within a short I/O stall window; (ii) overrun-bounded time budgeting, which estimates from recent idle-time samples how long each update subtask can safely be executed within an idle window, bounding the expected overrun of update subtasks to a controlled fraction of the mean idle time; and (iii) adaptive utilization tuning, which uses a feedback loop to dynamically tune the fraction of the idle-time budget devoted to updates, driving end-to-end search latency degradation toward a user-specified target θ (which is the only user-configurable parameter to maintain operational simplicity). LIOS is optimized with system-level mechanisms (§5) to achieve high search-update co-execution performance.

Introduction

On-disk graph-based indexes [4, 7, 9, 11, 19, 22] are widely used for large-scale Approximate Nearest Neighbor Search (ANNS) [10, 14, 23, 25] in recommendation, web search, and retrieval-augmented generation [17]. As datasets grow to billions of vectors and continue to be ingested, these systems must concurrently handle two fundamentally different workloads: latency-sensitive search queries and throughputdemanding index updates [9, 22, 27]. At the thread level, balancing the two under a shared CPU budget is difficult: devoting more cores to one workload reduces the CPU available to the other. Insufficient resources for updates cause the ANNS index to lag behind incoming data, degrading retrieval accuracy and result freshness, while insufficient resources for search directly degrade user-facing latency. Existing systems treat the two as competing consumers of a fixed resource pool, with no principled mechanism to reduce this tension. We observe that even when every search thread is continuously saturated with queries, over 40% of its CPU time is stalled on I/O (§3). This intra-request idle time is invisible to thread-level scheduling: the thread is actively processing a query, yet the CPU is idle until the disk read completes. If these idle cycles can be harvested and redirected to update tasks, it becomes possible to improve update throughput without reducing the CPU budget available to search, at a

We integrate LIOS into two state-of-the-art updateoptimized ANNS systems, FreshDiskANN [22] and OdinANN [9]. We evaluate LIOS on real-world datasets ranging from 10M to 500M vectors across two servers with distinct hardware configurations. At the 100M scale, LIOS achieves update speedups of up to 1.46× (insert) and 1.48× (delete) under FreshDiskANN, and up to 1.72× (insert) and 1.49× (delete) under OdinANN. At the 10M scale, the gains are even larger, reaching up to 2.68× (insert) and 2.18× (delete). Meanwhile, LIOS maintains controlled degradation in search 1

latency. We will open-source our LIOS prototype in the final version of the paper.

the candidate pool. If the pool exceeds size L, it is truncated to retain only the L nearest candidates. This process repeats until every vector in the candidate pool has been visited, at which point the top-K nearest vectors are returned. PipeANN [7] relaxes the strict per-hop data dependency in graph traversal by overlapping disk I/O with computation via pipelining; we refer to its search procedure as PipeSearch, in contrast to the standard BeamSearch. Despite this optimization, the overall performance remains bounded by disk access latency. Each graph-traversal hop requires at least one disk read, and the per-hop disk I/O latency far exceeds the corresponding computation time, making disk access the dominant factor even with pipelining. In §3, we provide a quantitative breakdown of this I/O-bound characteristic.

2.3

On-disk Node Records

Page 0

9 2 7 1

Page 1

Page 2

Compressed Vectors … V0 '

4 0 6

Record 0 1

Record 1 4

Vector V0

Neighbor list of V0 Logical Graph

Record 2

Disk Layout

Lossy compression

V1 '

V2 '

V3 '

V4 '

V5 '

V6 '

V7 '

V8 '

V9 '

V10'

V11'

…

Memory

Figure 1: DiskANN organizes its index by storing raw vectors together with their out-neighbors on disk, while keeping a compressed representation of the vectors in memory to enable fast similarity comparisons.

2.1

Background

Supporting updates, including insertions and deletions, is crucial for maintaining the freshness of disk-based ANNS systems. FreshDiskANN [22] buffers insertions in an auxiliary in-memory index while tracking pending deletions in a separate buffer. Once the in-memory insertion index grows beyond a threshold, a StreamingMerge procedure is triggered to flush all buffered updates into the on-disk index. OdinANN [9] adopts a similar buffering strategy for deletions, but applies in-place insertions directly into the on-disk graph, eliminating the in-memory index to reduce memory overhead and mitigate interference with search. Despite the different approaches, both systems share a computationally intensive step: the neighbor selection procedure, commonly referred to as Prune. After each update, Prune recomputes the neighbor sets of affected nodes to maintain the Sparse Neighborhood Graph (SNG) property [1], which ensures the selected neighbors provide good angular coverage around each node while avoiding redundant short-range edges. Specifically, given a target point p, a candidate set V of potential neighbors, a distance threshold α, and a degree bound R, Prune iteratively selects up to R neighbors. In each iteration, it picks the candidate p∗ closest to p from V and adds p∗ to the neighbor set. It then scans the remaining candidates and removes every p′ for which α · d(p∗ , p′ ) ≤ d(p, p′ ), filtering out candidates whose direction from p is already covered by p∗ . This process repeats until either R neighbors have been selected or the candidate set is exhausted, yielding a neighbor set with diverse angular coverage around p that respects the degree bound. OdinANN proposes an improved variant, DeltaPrune, to reduce pruning overhead, yet pruning remains the key computational bottleneck for updates, as we analyze in §3.

Basics of Graph-based ANNS Systems

We consider graph-based ANNS systems for vector storage in disk-based scenarios where datasets exceed memory capacity. Vectors are organized as nodes in a directed neighbor graph, enabling efficient similarity search through iterative graph traversal. DiskANN [11] stands out as a pioneering graph-based ANNS system that has inspired subsequent optimizations, including FreshDiskANN [22], PipeANN [7], and OdinANN [9]. Thus, we use DiskANN as the representative disk-based graph-based ANNS system for our discussion. As shown in Figure 1, DiskANN organizes vectors as a logical graph, in which each vector is a node and each directed edge points to an out-neighbor. On disk, this logical graph is materialized as fixed-size node records: each record corresponds to a single vector and contains its raw data along with the IDs of its out-neighbors. The number of out-neighbors per node is bounded by a fixed upper limit R, so all records share a consistent size for alignment and page management. In memory, DiskANN keeps compressed vectors, typically generated using Product Quantization [12] or RaBitQ [6], to support fast approximate distance estimation.

2.2

Update Algorithm

Search Algorithm

DiskANN’s search procedure, commonly referred to as BeamSearch, follows an iterative greedy strategy on the neighbor graph. Given a query vector q, the algorithm begins from a designated entry point and maintains two data structures: a candidate pool of maximum size L tracking the most promising vectors seen so far, and a visited set recording vectors already expanded. Each iteration proceeds in two steps: ❶ it selects the W closest unvisited candidates from the pool (where W is the beam width), reads their on-disk records, and retrieves the out-neighbor lists; ❷ it computes distances between q and all newly discovered neighbors using the compressed in-memory vectors, and inserts those neighbors into

Motivation

We analyze two complementary phenomena: the CPU idle time that accumulates during search I/O stalls (§3.1), and the 2

Idle Ratio

Beam 1T Pipe 1T

Beam 4T Pipe 4T

Beam 16T Pipe 16T

1.0

0.8

prune

0.6

0.4

Fresh delete

0.2

100

(a) SIFT-10M, R = 32 1.0

0.8

0.6

0.4

0.2

100

92.5%

52.7%

75.0%

92.0% 25

31.4%

22.9%

93.3%

Prune / Search time (%)

100 0

Prune / Search time (%)

100

Note that simple thread-level optimizations, such as adding search threads or reallocating cores, cannot readily reclaim this idle time. A stalled search thread mid-query occupies its CPU context and cannot be preempted with another query without incurring context-switch overhead and breaking query-level state. The stall is intra-request (i.e., occurring within an actively executing query) and is hence invisible to thread-level or queue-based scheduling policies. Observation #1. Search threads in graph-based ANNS systems spend over 40% of time stalled on per-hop disk I/O, even with pipelined execution. This idle time is intra-request and cannot be readily recovered by thread-level scheduling.

100

(d) SIFT-1B R = 64

Figure 2: Idle ratios of BeamSearch and PipeSearch across dataset scales and index configurations.

high computational cost that dominates index updates (§3.2).

3.1

57.6%

(a) (R, L) = (32, 32) (b) (R, L) = (100, 100) Figure 3: Proportion of prune and search times in the overall update time in SIFT-10M.

(b) SIFT-10M, R = 100

1.0

54.4%

43.5%

88.4%

Odin delete

0.6

40.9%

Odin insert

Fresh insert

Idle Ratio

Beam 32T Pipe 32T

Unexploited Idle Time in Search

Search threads in graph-based ANNS systems spend a substantial fraction of their time waiting on disk I/O, consistently across different graph indexes and system configurations. We define the idle ratio as the fraction of a search thread’s execution time spent waiting for outstanding disk reads to complete (i.e., the time during which the thread holds the CPU but performs no useful computation). We validate the prevalence of this idle time by profiling BeamSearch and PipeSearch across multiple datasets and workloads. We consider datasets at scales of 10M, 100M, and 1B vectors. We fix the beam width W = 4 (§2.1), configure different R (i.e., the maximum out-degree per node; §2.1) and L (i.e., the maximum number of candidates; §2.2), and vary the thread count from 1 to 32. Figure 2 shows the idle ratios across different settings. BeamSearch exhibits a high idle ratio of 60-80%. This is because the set of candidate nodes to fetch in hop h + 1 is determined by the distance computations on hop h’s results, so each hop creates a strict sequential data dependency that forces the CPU to wait for the current disk read before it can issue the next one. PipeSearch achieves lower idle ratios by pipelining computation with disk I/O, allowing distance calculations to proceed while the next batch of data is being fetched. However, PipeSearch’s idle ratio remains above 40%, since the per-hop I/O latency still significantly exceeds the computation time (a condition inherent to disk-based traversal); even with the next hop’s I/O already in flight, the CPU completes its distance computations well before the data arrives, leaving it idle for the residual gap. Thus, a pipelined search thread always carries residual idle intervals.

3.2

High Computation Cost of Updates

We profile the insert and delete operations of FreshDiskANN [22] and OdinANN [9], the two state-of-the-art updateoptimized graph-based ANNS systems (§2.3). Figure 3 shows their update time breakdown on the SIFT-10M dataset under (R, L) = (32, 32) and (R, L) = (100, 100). For insertions, the total cost is dominated by two components: (i) the search phase, which locates candidate neighbors for the new vector, and (ii) the subsequent prune phase, which selects a neighbor subset satisfying the SNG property (§2.3). Under (R, L) = (32, 32), pruning accounts for 40.9% of insertion time in OdinANN and 43.5% in FreshDiskANN. Increasing the graph degree to (R, L) = (100, 100) raises these ratios to 57.6% and 75.0%, respectively, as a larger R incurs more iterations and distance computations during neighbor selection. Although OdinANN’s DeltaPrune reduces the absolute pruning cost of FreshDiskANN, pruning remains a major bottleneck, consuming 40.9–57.6% of insertion time. For deletions, the computational burden is even higher. Unlike insertions, which require pruning only the newly inserted node and its displaced neighbors, deletions must identify every node in the graph whose neighbor list references a deleted vector, and each such node must undergo local pruning to repair its neighbor set. This graph-wide repair causes the prune ratio for deletions to far exceed that for insertions. Across both R = 32 and R = 100 configurations on SIFT-10M, pruning accounts for 88.4–93.3% of the total deletion time for OdinANN and FreshDiskANN, confirming that update throughput is con3

Comp.

4.5

Comp.

Large update tasks

3 1.5

Allocate usage fraction

§4.4 Adaptive Utilization Tuning

w/ LIOS Comp.

Comp.

Observed latency

200

400

600

Time (µs)

800 1000

Re-enqueue task

§4.2 Decompose (intra-vector)

LIOS Design

4.1

Overview

180

Time (µs)

240

300

0.75 0.5 0.25

2500

7500

Time (µs)

12500

800 1600 2400 3200 4000

Time (µs)

(c) Delete per-node (d) Insert per-node Figure 5: KDE plots of per-hop search idle (a–b) and per-vector update computation time (c–d) on SIFT-10M, R=100.

strained by CPU computations rather than I/O. Observation #2. Index updates in graph-based ANNS systems are bottlenecked by CPU-intensive neighbor pruning, which accounts for 40.9–93.3% of total update time across both insertions and deletions.

0.8

120

1e-3

0.4

Figure 4: Overview of LIOS’s co-execution design.

1.2

Save checkpoint

(b) BeamSearch idle

KDE

Task Queue

0.5

1e-4

Resume from checkpoint

Dequeue task

0.75 0.25

(a) PipeSearch idle

Per-vector subtasks

KDE

§4.2 Decompose (inter-vector)

1e-2

w/o LIOS KDE

Derived time budget

KDE

Idle time samples

§4.3 Overrun-bounded time budgeting

• Fine-grained update decomposition (§4.2), which breaks monolithic updates into independent per-vector subtasks, and replaces the original pruning procedure within each subtask with a resumable, checkpoint-able procedure that can pause and resume across multiple idle windows; • Overrun-bounded time budgeting (§4.3), which derives a per-hop time budget from empirical idle time data that bounds the expected overrun (i.e., the time by which a scheduled update task exceeds the actual idle window) to a controlled fraction of the mean idle time by leveraging the temporal stability of short-term idle time distributions; • Adaptive utilization tuning (§4.4), which dynamically adjusts the fraction of the time budget allocated to updates via a feedback-driven tuner, thereby steering end-to-end search latency degradation within a user-specified target. LIOS exposes only one user-facing parameter, θ, which specifies the allowed ratio of end-to-end search latency degradation. It guarantees search performance by bounding I/Owindow overruns (§4.3) and controlling co-execution overhead (§4.4). Both sources of degradation are regulated by θ to provide end-to-end latency guarantees. Figure 4 depicts LIOS’s workflow. LIOS first decomposes a large update task into independent per-vector subtasks, which are then enqueued into a FIFO task queue. During each search hop, LIOS derives an overrun-bounded budget from recent idle-time samples and allocates an online-tuned fraction of the derived budget to updates. It dequeues a subtask and executes the subtask within the resulting time slice. If the budget expires before the subtask completes (e.g., mid-pruning), the resumable pruning mechanism checkpoints the task’s progress and re-enqueues the remaining work for completion in a subsequent idle window.

Our observations in §3 reveal a natural complementarity: search threads spend over 40% of their CPU time stalling on disk I/O, while updates are bottlenecked by CPU-intensive neighbor pruning. This motivates us to harvest idle CPU cycles within search threads and redirect them to update computation, improving update throughput without reducing the CPU budget available to search. However, realizing this idea in practice introduces three challenges: • Granularity mismatch: A single update operation (e.g., pruning a vector’s neighbor set) typically lasts much longer than the idle intervals available in a single search hop, so naively executing updates during I/O stalls would spill over into the search computation phase and inflate query latency. • Variable and unpredictable idle periods: Idle intervals vary unpredictably across hops, and optimizations such as dynamic I/O width and user-space caching further distort the underlying distribution, making it difficult to determine how much update work can be safely scheduled in any given window. • Bounding end-to-end search latency degradation: Coexecution degrades end-to-end search latency through workload- and runtime-dependent effects (e.g., cache pollution from displaced search data and varying sensitivity across workload phases) that cannot be modeled analytically in advance. Keeping the degradation within the user’s tolerance requires a runtime mechanism that observes and adapts to these effects. LIOS is a search-update co-execution framework designed to address these challenges in graph-based ANNS systems. It introduces three techniques:

4.2

Decomposition of Update Tasks

LIOS decomposes update work at two levels: inter-vector decomposition partitions an update task into independent pervector subtasks, while intra-vector decomposition enables 4

pruning inside each task resumable across idle windows. Inter-vector decomposition. An update operation in graphbased ANNS can be decomposed into a collection of pervector neighbor-set updates: each affected vector must have its neighbor list recomputed via the Prune procedure (§2.3). For insertions, the affected set consists of the inserted vector itself and the O(R) vectors in its reverse neighborhood whose neighbor lists may now include the new vector as a candidate. For deletions, identifying the affected set requires first scanning the graph to find all vectors whose neighbor lists reference a deleted entry; once this identification phase is complete and tasks are enqueued, each affected vector’s pruning computation depends only on its own local candidate set and distances, and is hence independent of all other pervector tasks. This independence means that per-vector tasks can be executed in any order without affecting the final graph, and it allows LIOS to partition a high-level update into a set of per-vector subtasks, which are enqueued into a shared task queue (§5). Intra-vector decomposition. Inter-vector decomposition alone is insufficient, since a single vector’s pruning time can far exceed an idle window. Figure 5 shows the idle-time and update-time distributions, using kernel density estimation (KDE) [21], a non-parametric method for estimating probability densities. The per-hop idle time is typically below 300 µs (Figures 5(a)-5(b)), whereas per-vector updates take roughly 800–4,500 µs for insertions and 1,000–12,500 µs for deletions (Figures 5(c)-5(d)), often exceeding idle windows by an order of magnitude. Within each per-vector update, the dominant cost is the Prune procedure, which accounts for 40–93% of total update time (§3.2), while the remaining computations (candidate preparation, distance computation, and adjacencylist finalization) are lightweight enough to complete within a single idle window and need not be split further. Thus, LIOS proposes resumable pruning, which transforms the original Prune into a checkpoint-able procedure, enabling it to pause mid-execution and resume in a subsequent idle window. Resumable pruning. Algorithm 1 shows the resumable pruning procedure, which builds upon the original Prune procedure (the shaded text marks LIOS’s additions). LIOS recasts Prune as a resumable procedure whose checkpoint state comprises four mutable variables: the current result set result, a percandidate flag done (indicating whether a candidate has been selected or eliminated under the SNG criterion), and two loop cursors i and j. The candidate list pool is immutable and fixed at task creation time, so it does not need to be checkpointed. When the elapsed time reaches the time budget τest derived from overrun-bounded budgeting (§4.3), the procedure saves the checkpoint and yields control to the search thread. Upon resumption, pruning restores the checkpoint and continues from the saved j, producing a result that is bit-identical to that of uninterrupted execution. The correctness of resumable pruning follows from two properties. First, since the checkpoint captures all four muta-

Algorithm 1: Resumable Pruning /* Shaded code represents LIOS’s logic added to the original Prune */ Input: Point p, sorted candidate list pool, distance threshold α, degree bound R, time budget τest Data: Checkpoint: result, done[0..len − 1], i, j Output: Pruned neighbor set result 1 if resuming from checkpoint then; 2 restore result, done, i, j; 3 goto line 11; / done[0..len − 1] ← false; i ← 0; 4 result ← 0; 5 for i ← 0 to |pool| − 1 do 6 if done[i] = true then 7 continue; 8 end 9 result ← result ∪ {pool[i]}; done[i] ← true; 10 if |result| ≥ R then return result; 11 for j ← i + 1 to |pool| − 1 do 12 if done[ j] = false and α · d(pool[i], pool[ j]) ≤ d(p, pool[ j]) then 13 done[ j] ← true; 14 end 15 if elapsed time ≥ τest then; 16 save checkpoint (result, done, i, j+1); 17 yield to search thread; 18 end 19 end 20 return result;

ble variables, resumed execution is fully deterministic. Second, each per-vector task has its own pool, which is never modified by other threads, so no synchronization is required. Example. Consider pruning a target point with degree bound R = 3 and a candidate pool of 6 vectors sorted by distance: pool = [c0 , c1 , . . . , c5 ], with done = [F, F, F, F, F, F] (F de/ and both loop notes false and T denotes true), result = 0, cursors i and j start at 0. In the first idle window, the outer loop finds c0 (non-done at i = 0), selects it as a neighbor, adds c0 to result, and marks done[0] = T . The inner loop then evaluates c1 through c5 against c0 : c1 and c3 fail the SNG criterion, so done[1] and done[3] are also set to T . After the inner loop completes, the outer loop advances to i = 2 (skipping i = 1 since done[1] = T ), selects c2 , adds it to result, and marks done[2] = T . The inner loop now evaluates c3 , c4 , and c5 against c2 : at j = 4, the SNG check does not eliminate c4 , and the subsequent budget check fires, signaling that the time budget has expired. The checkpoint (i.e., result={c0 , c2 }, done = [T, T, T, T, F, F], i = 2, j = 5) is saved, and control returns to the search thread. In the next idle window, pruning restores the checkpoint and resumes the inner loop from j = 5: it checks c5 against c2 , which is not eliminated. The inner loop completes, and the 5

sample 1 sample 1

sample 2

sample 3

sample 4

sample 3

sample 4

a user-specified threshold. Formally, let τ denote the idle time random variable with mean µτ . Over a short historical window, we collect empirical measurements {τi }Ni=1 , which approximate the current idle time distribution by the temporal stability property. The overall latency degradation is bounded by a user-specified threshold θ (§4.1), which also bounds the I/O-window overrun. Our objective is to find a time budget τest such that the expected overrun does not exceed a fraction θ of the mean idle time:

all samples

.016

Density

.008 0

.02 .01 0 0

400

800

400

800

400

800

400

800

400

800

Latency (µs)

E[max(0, τest − τ)] ≤ µτ · θ.

Figure 6: Temporal stability of idle-time distributions on SIFT-10M, including the KDEs of four independently sampled time windows and the aggregate of all samples. Top row: PipeSearch idle time; bottom row: BeamSearch I/O latency at #IO=4.

LIOS bounds the expected overrun by µτ · θ to ensure that any overrun into the search phase remains a controlled fraction of the idle budget. Replacing the expectation with empirical sample means yields a solvable constraint:

outer loop advances to find the next non-done candidate: i = 3 is skipped (done[3] = T ), and c4 is selected at i = 4 as the third neighbor and added to result. Now, we have |result| = R = 3, and the pruning terminates. The final neighbor set {c0 , c2 , c4 } is identical to that returned by uninterrupted pruning: the checkpoint mechanism changes only when the computation executes, not what it executes. Together with the per-vector independence established above, LIOS ensures that the final graph is returned correctly.

4.3

1 N 1 N max(0, τest − τi ) ≤ ∑i=1 τi · θ. N ∑i=1 N Since the left-hand side is monotonically non-decreasing in τest , LIOS solves the empirical constraint efficiently via binary search over τest using recent idle time samples. The formulation above assumes a single idle time distribution, but BeamSearch and PipeSearch produce structurally different idle time patterns, requiring the following adaptations: • BeamSearch adaptation: BeamSearch dynamically decides how many I/O requests to issue per hop; more concurrent requests lead to longer I/O waits and hence different idle window distributions. LIOS maintains Bu buckets (one per batch size nrequests ∈ {1, . . . , Bu }), each with its own sample history and solved τest , so that the budget is conditioned on the actual I/O concurrency of each hop. • PipeSearch adaptation: PipeSearch’s pipeline I/O yields heavily right-skewed idle distributions (most intervals in [0, 10] µs), so scheduling on every interval produces an overly conservative τest . LIOS adopts a K-sparse strategy: update tasks run only every Kth interval. When solving for τest , overrun is counted only on scheduled intervals while the budget is averaged over all N intervals, amortizing the cost and letting τest target the longer windows that actually carry work.

Overrun-Bounded Time Budgeting

While decomposition fits update work into idle windows, scheduling each subtask safely requires bounding how long it may run. Since idle window lengths vary across hops, LIOS must determine a time budget for each idle window to bound the duration an update subtask may execute. Instead of predicting the exact length of the next idle window, our goal is to derive a budget τest such that the expected overrun (i.e., the amount by which the budget exceeds the actual idle time) remains a controlled fraction of the mean idle time. This ensures that any time taken from the search computation phase stays within a controlled tolerance. Deriving such a budget requires knowledge of the idle time distribution, which is difficult to model in practice: whether it is disk I/O latency in BeamSearch or CPU idle time in PipeSearch, empirical distributions often exhibit irregular, heavily skewed shapes. Despite this, our observations reveal a useful property: within short, continuous time windows, the shape of the idle time distribution remains remarkably stable. As shown in Figure 6, the distributional shape within each configuration is highly consistent across independently sampled time chunks. This temporal stability means that a budget derived from recent samples reliably bounds overrun for upcoming windows, enabling a data-driven approach that solves for a budget directly from the empirical distribution. We call a time budget overrun-bounded if its expected overrun, as a fraction of the mean idle time, stays within

4.4

Adaptive Utilization Tuning

The per-hop budget τest controls overrun within each idle window, but cannot by itself keep end-to-end search latency degradation within the user-specified bound θ: co-execution introduces additional sources of degradation (cache pollution from displaced search data and varying sensitivity across workload phases) that per-hop analysis cannot enumerate or model. Since such additional sources cannot be eliminated directly, LIOS adds an automated, end-to-end feedback loop based on the observed actual query latency, and adaptively adjusts the fraction of τest devoted to updates to keep the 6

ratio of end-to-end latency degradation within θ. It further employs cache prefetching to mitigate cache pollution at its origin, giving the loop more headroom to push α higher. We elaborate on both mechanisms as follows. Feedback-loop. LIOS continuously adjusts a utilization ratio α (i.e., the fraction of τest actually allocated for updates), as workload and system conditions change. Its objective is to maximize update throughput while keeping the degradation in end-to-end search latency within the user-specified bound θ. It is a feedback-driven state machine taht uses periodically observed query latency (mean by default, but replaceable with P95 or P99 by substituting the observed statistic): • Step 1: Recording. LIOS first suspends update scheduling. It then profiles search latency and idle time to establish a no-update baseline and to compute the first-time budget τest . • Step 2: Binary search. Using the baseline and τest obtained in Step 1, LIOS searches for an initial feasible α such that query_latency is not higher than 1 + θ. If no feasible α exists, baseline LIOS disables co-execution. • Step 3: Steady. Once a feasible α is found, LIOS enters a continuous adaptation loop. It increases α by a small fixed increment when the measured latency remains below (1 + θ) times of the baseline to gain additional update throughput; it decreases α when a violation is observed (i.e., query_latency > 1 + θ). The no-update baseline is periodibaseline cally refreshed by temporarily suspending update scheduling for a short profiling interval. • Step 4: Rebaseline. Triggered by excessive baseline drift (i.e., three consecutive violations observed in Step 3) or Search failure, this phase returns to Step 1 to re-establish the baseline and re-find a feasible α. Cache prefetching. While the feedback loop can absorb cache pollution by reducing α, doing so sacrifices update throughput. LIOS therefore prefetches (i) the query vector, (ii) the PQ distance lookup table, and (iii) visited-set metadata. Prefetches are issued both after each update execution and after I/O completion, ensuring search data is warm before distance computation resumes. By shrinking cache-induced degradation at its origin, prefetching allows LIOS to sustain a higher α without violating θ.

LIOS does not change their semantics.

We choose two open-source disk-based ANNS systems as backends, FreshDiskANN [5] and OdinANN [8], and implement LIOS atop them. We add approximately 1,900 lines of C++ to each. Our co-execution model includes the search-side and update-side integration. Search-side integration. To execute update subtasks during I/O stalls, the search thread must retain CPU control rather than blocking on I/O completion. LIOS decomposes each hop’s I/O into a submit–execute–poll protocol: • Submit: The search thread batches all frontier read requests and submits them asynchronously via io_uring [15]. Requests that hit the user-space page cache are resolved immediately, bypassing the kernel I/O path. • Execute: While I/O is in flight, the search thread consults LIOS’s time budgeting logic and, if permitted, executes one update subtask from the queue, converting a CPU stall into useful computation. • Poll: The thread harvests completions with a non-blocking batch poll; if requests remain outstanding, it falls back to a blocking wait. Update-side integration. On the update side, LIOS bridges to the search side via a shared FIFO task queue that decouples task production from consumption. • Task generation: The update thread enqueues tasks at pervector granularity (§4.2). Tasks employ self-re-enqueueing: after processing one vector, the search thread that executed the task re-enqueues it if vectors remain, eliminating the need for the update thread to manage per-vector enqueuing and reducing synchronization overhead. • Time-budgeted execution: During each idle window, a search thread dequeues one task and executes it within a time budget of α · τest , where α is LIOS’s utilization ratio (§4.4). If the budget expires mid-pruning, the checkpoint mechanism (§4.2) saves progress and re-enqueues the continuation.

6 4.5

Implementation

Evaluation

Parameter Configuration 6.1

LIOS exposes only one user-facing parameter: the latency degradation bound θ, which specifies the maximum searchlatency overhead allowed during search–update co-execution. A smaller θ prioritizes search latency, while a larger θ allows more aggressive use of search-side idle time for updates. Given θ, LIOS automatically estimates per-hop budgets and tunes utilization at runtime. The standard ANNS parameters of the underlying graph index, such as graph degree R, candidate pool size L, beam width W , and result size K, remain application-level choices for recall, latency, and throughput;

Methodology

Testbeds. We use two server testbeds with complementary hardware profiles. Testbed A is equipped with 2× 20core Intel Xeon Gold 5218R @ 2.10 GHz, 128 GiB DRAM (8×16 GiB DDR4-2666), an Intel P4610 2.9 TiB SSD, and Ubuntu 20.04.4 LTS (Linux 5.4.0-80-generic). Its 40 physical cores provide a high degree of parallelism needed to saturate both search and update threads at large scale, in which we allocate 64 search threads and 16 update threads. Testbed B is equipped with 2× 8-core Intel Xeon Silver 4309Y 7

Table 1: Exp #1 (100M end-to-end): 100M-scale datasets at default settings (§6.1). Dataset

Workload

Speedup

Delete-phase latency change (%)

Insert-phase latency change (%)

Delete Insert

Avg

P95

P99

Avg

P95

P99

SIFT-100M

Beam+Fresh Pipe+Fresh Beam+Odin Pipe+Odin

1.34× 1.27× 1.25× 1.23× 1.20× 1.36× 1.38× 1.51×

+2.6±0.06 +0.7±0.07 +7.0±0.10 −0.6±0.12

−0.3±0.09 −1.4±0.12 +3.1±0.13 −3.5±0.18

+0.8±0.63 +0.5±0.40 +5.6±1.36 −2.3±0.75

+0.8±0.17 +0.7±0.17 +6.6±0.10 +6.8±0.16

−2.0±0.23 −1.4±0.26 +8.2±0.15 +9.5±0.34

+1.8±2.50 +3.3±1.50 +8.3±0.25 +7.7±0.74

DEEP-100M

Beam+Fresh Pipe+Fresh Beam+Odin Pipe+Odin

1.25× 1.18× 1.23× 1.19× 1.13× 1.47× 1.42× 1.72×

+3.4±0.06 +0.8±0.07 +7.1±0.09 +1.0±0.13

−0.7±0.09 −2.1±0.11 +2.0±0.11 +0.6±0.31

−1.2±0.59 −3.8±0.39 +5.8±1.63 +5.6±1.02

+1.6±0.17 −3.0±0.20 +2.3±2.25 +1.1±0.15 −1.7±0.22 −0.9±1.62 +8.6±0.09 +10.1±0.13 +9.7±0.16 +7.5±0.15 +6.6±0.24 −3.4±0.73

Beam+Fresh Pipe+Fresh SPACEV-100M Beam+Odin Pipe+Odin

1.48× 1.43× 1.48× 1.46× 1.26× 1.19× 1.49× 1.48×

+0.3±0.12 +0.1±0.10 +7.8±0.22 −0.8±0.23

−1.1±0.17 −2.3±0.12 +5.1±0.28 −2.1±0.33

−2.2±1.08 −2.5±0.50 +8.9±0.59 −0.3±0.94

+0.5±0.38 +0.4±0.31 +6.0±0.27 +6.4±0.29

−0.0±0.40 −2.2±0.35 +7.6±0.46 +4.6±0.63

+8.8±5.67 +5.1±3.35 +9.3±0.79 −3.2±1.43

Table 2: Exp #1 (10M end-to-end): 10M-scale datasets at default settings (§6.1). Dataset

Workload

Speedup

Delete-phase latency change (%)

Insert-phase latency change (%)

Delete Insert

Avg

P95

P99

Avg

P95

P99

SIFT-10M

Beam+Fresh Pipe+Fresh Beam+Odin Pipe+Odin

1.65× 1.77× 1.58× 1.67× 2.02× 1.34× 2.15× 1.72×

+2.4±0.05 +3.7±0.06 +8.0±0.17 +3.5±0.10

−0.2±0.07 +4.2±0.14 +7.2±0.18 +3.5±0.13

−1.2±0.45 +6.7±0.46 +6.1±0.63 +1.1±0.38

+2.7±0.12 +2.8±0.15 +2.6±0.20 +7.8±0.27

−1.3±0.11 +2.0±0.34 +3.2±0.45 +7.5±0.61

−1.2±1.71 +1.7±1.55 +2.7±0.64 +2.6±0.76

DEEP-10M

Beam+Fresh Pipe+Fresh Beam+Odin Pipe+Odin

1.39× 1.48× 1.60× 1.57× 1.70× 1.36× 2.18× 1.84×

+1.9±0.08 +3.6±0.07 +6.6±0.15 +3.0±0.12

−0.2±0.13 +5.0±0.13 +4.1±0.22 +3.4±0.15

+0.2±0.42 +7.8±0.40 +5.0±0.79 +5.2±0.62

+4.3±0.16 +0.2±0.22 −0.1±0.14 −0.1±0.27 +4.8±0.23 +4.6±0.42 +10.2±0.31 +9.2±0.57

+2.5±1.77 −0.5±1.35 +4.6±0.61 +5.0±0.54

Beam+Fresh Pipe+Fresh SPACEV-10M Beam+Odin Pipe+Odin

1.81× 2.68× 1.83× 1.90× 1.86× 1.21× 2.16× 1.63×

+2.0±0.10 +2.0±0.11 +9.6±0.71 +4.6±0.26

−0.7±0.11 +2.4±0.43 +6.0±0.65 +5.3±0.35

−0.4±0.51 +2.1±0.57 +6.3±1.45 +7.0±0.61

+7.3±0.67 +1.4±0.29 +1.8±0.43 +5.5±0.47

+8.2±4.53 +1.7±2.25 +4.5±1.97 +4.5±1.38

+2.6±1.12 +0.8±0.86 +2.1±1.20 +6.5±1.21

R = 96, L = 100, and B = 32. In all experiments, both search and update threads are continuously saturated, ensuring that no thread-level idleness exists; the only idle resource exploited by LIOS is the intra-request I/O stall time within each busy search thread. All search operations use K = 10 and L = 100, and the resulting recall@10 ranges from 95% to 99% across all datasets. We report search-side average/P95/P99 latency and throughput (queries per second (QPS)), and updateside throughput (vectors/second), along with execution times for deletion and insertion. We collect all search-run samples, averaging 1,633 samples per run at 10M scale and 5,157 samples per run at 100M scale, and report 95% confidence intervals using the normal distribution.

@ 2.80 GHz, 256 GiB DRAM (16×16 GiB DDR4-2666), a WD Ultrastar DC SN640 7 TiB SSD, and Ubuntu 22.04.5 LTS (Linux 5.15.0-163-generic). Its smaller core count is representative of a resource-constrained deployment and is better suited for isolating per-mechanism effects, in which we allocate 28 search threads and 4 update threads. Hyper-threading is enabled on both testbeds. Workloads. We evaluate mixed search-update co-execution on three datasets: SIFT [13], SPACEV [20], and DEEP [2], sliced at scales from 10M to 500M vectors. Unless otherwise stated, each run deletes 5% of vectors from the original index and then inserts 5% new vectors, with concurrent search. Default settings. We use backend-specific latency thresholds unless otherwise stated: θ=5% for FreshDiskANN-based backends and θ=8% for OdinANN-based backends. The higher threshold for OdinANN reflects its user-space cache, which amplifies per-episode overhead and requires a larger budget for meaningful speedup. All indexes are built with

Baselines. We derive the baselines from DiskANN [11] (BeamSearch), FreshDiskANN [22] (Buffered Insert), PipeANN [7] (PipeSearch), and OdinANN [9] (Direct Insert), forming four configurations: (i) BeamSearch + Buffered Insert, (ii) BeamSearch + Direct Insert, (iii) PipeSearch + 8

w/o LIOS

Buffered Insert, and (iv) PipeSearch + Direct Insert. For each configuration, we compare with LIOS against without LIOS. I/O Time (µs)

6.2

End-to-End Performance

7000

+2.5%

+2.3%

w/o LIOS w/ LIOS

(a) Beam, R=32 Idle Time (µs)

+2.4%

6000 5000

Exp #1 (End-to-end performance). We evaluate all configurations at the default settings (§6.1) on 100M-scale and 10Mscale datasets. Table 1 reports results on SIFT-100M, DEEP100M, and SPACEV-100M using Testbed A; Table 2 reports SIFT-10M, DEEP-10M, and SPACEV-10M using Testbed B. LIOS consistently reduces update execution time across all datasets and configurations. On the 100M-scale datasets, LIOS achieves an update speedup of up to 1.48× (delete) and 1.46× (insert) over the non-LIOS baseline under FreshDiskANN, and up to 1.49× (delete) and 1.72× (insert) under OdinANN. On the 10M-scale datasets, the gains are even larger: LIOS achieves an update speedup of up to 1.83× (delete) and 2.68× (insert) over the non-LIOS baseline under FreshDiskANN, and up to 2.18× (delete) and 1.84× (insert) under OdinANN. The two search strategies generally show opposite speedup rankings across the two backends, particularly during the delete phase. Under FreshDiskANN, BeamSearch tends to achieve higher speedup because its blocking I/O creates longer idle windows for LIOS to exploit. Under OdinANN, the ranking reverses: by default, OdinANN’s PipeSearch does not cache disk pages fetched on cache misses; the resulting extra misses raise PipeSearch’s idle ratio above BeamSearch’s, yielding more co-execution opportunities and thus higher speedup. Search latency remains controlled. On the 100M-scale datasets, mean latency overhead stays within 8.6%, and on the 10M-scale datasets within 10.2%; P95 remains within 10.1% and 9.2%, respectively. Note that a few mean-latency entries are above the configured θ due to LIOS’s best-effort design: θ guides adaptive tuning but is not a hard bound for every search sample. Short workload or I/O fluctuations can, in a few cases, increase the phase average beyond the target, while most configurations remain within the budget as LIOS reduces co-execution aggressiveness. P95 and P99 sometimes fall below the baseline, which we attribute to cache prefetching after co-execution episodes. In a few configurations, tail latency increases more noticeably (e.g., +9.7% P99 for DEEP-100M Beam/OdinANN insert) because LIOS reports mean latency by default; deployments prioritizing tail latency can report P95 or P99 in the observed latency statistics with comparable throughput (Exp #9).

6.3

w/ LIOS

8000

w/o LIOS

w/ LIOS

(b) Beam, R=64

w/o LIOS

w/ LIOS

4900 +2.1%

3900

2900

+5.1%

w/o LIOS w/ LIOS

(d) Pipe, R=32

+4.2%

w/o LIOS

w/ LIOS

(e) Pipe, R=64

w/o LIOS

w/ LIOS

(f) Pipe, R=96

Figure 7: Exp #2 (Overrun-bounded time budgeting): SIFT-10M, Testbed B; θ=5%. Top row: BeamSearch (I/O time); bottom row: PipeSearch (idle time).

Exp #2 (Overrun-bounded time budgeting). Figure 7 shows hop-level violin distributions of per-request I/O time (BeamSearch) and idle time (PipeSearch) with and without LIOS at R ∈ {32, 64, 96}, using SIFT-10M on Testbed B (28 search + 4 update threads, θ=5%). Each violin shows the mean and distribution; its width indicates sample density at each I/O or idle-time value. Under BeamSearch, LIOS increases mean per-request I/O time by 2.3–2.5% across different R; under PipeSearch, the corresponding mean idle-time increases are 2.1–5.1%. In all cases, the overhead stays at or near the θ=5% bound, confirming that the overrun-bounded sampling (§4.3) effectively limits per-hop overrun. Exp #3 (Adaptive utilization tuning). We trace LIOS’s utilization tuning on SIFT-100M (Testbed A). Figure 8 shows insertion followed by deletion. LIOS reaches Steady 20s after updates start and re-enters Steady 26s after deletion begins. During insertion, it uses 94.0% average utilization with 4.5% latency overrun and 596 adjustments. During deletion, latency is more sensitive, so LIOS lowers utilization to 59.5%, keeps latency overrun at 7.5% within the θ=8% target, and makes 2,127 adjustments. The few deletion samples above θ reflect transient deviations from the profiled baseline; LIOS therefore treats θ as a best-effort latency target rather than a per-sample hard bound. When such violations appear, LIOS reduces utilization and, if needed, re-enters profiling/binary search to keep phase-level latency close to the target.

6.4

Breakdown Analysis

Exp #4 (Breakdown analysis). We isolate the contribution of each major component by starting from naive co-execution and adding the mechanisms cumulatively: • w/o intra-vector decomposition: only inter-vector decomposition; updates cannot be interrupted mid-pruning. • w/o overrun-bounded time budgeting: replace LIOS’s adaptive time budgeting with a fixed time budget.

Mechanism Validation

We validate the two control mechanisms that enable the default operating point: overrun-bounded time budgeting, which bounds the per-hop overrun, and adaptive utilization tuning, which adapts the usable fraction of the estimated idle budget to enforce end-to-end latency targets. 9

Recording

Rebaseline

theta tolerance band

100

Utilization Ratio (%) Latency Overrun (%)

Steady

75 50 25

Insertion Phase

Deletion Phase

20 0 −20

5000

10000

15000

20000

25000

Time (s)

Figure 8: Exp #3 (Adaptive utilization tuning): Utilization ratio and latency overrun over time on SIFT-100M. Merge phase

37.9

20 8.6

8.4

0 Na

7.7

7.6

7.3

Latency (ms)

Delete phase

+In

2.7×

0 Na

2.2× 1.5×

ı̈ve

tra

+In

1.0×

st. uner fetch eline T s re +U Ba +P

Speedup (×)

5.1×

2.6×

7.7

7.5

7.3

tra +Est. uner fetch eline T s +U +Pre Ba

ı̈ve

+In

6.5

(b) Insert-phase latency

4 2

8.5

8.3

(a) Delete-phase latency 6

5% of baseline, but reduces speedup to 1.5×/1.6× as the controller conservatively limits co-execution. Finally, enabling cache prefetching (+Prefetch) recovers speedup to 2.2× for both phases while keeping latency within 3% of baseline. Together, the four mechanisms achieve substantial update speedup while keeping search latency tightly controlled.

15.4

tra +Est. uner fetch eline T s +U +Pre Ba

ı̈ve

Confidence Interval

3.8× 2.6×

2.4×

We study how the throughput-latency trade-off varies with key operating parameters, including the latency threshold θ, thread configuration, graph degree R, tuning latency statistics, and dataset scale. Exp #5 (Latency threshold sensitivity). Figure 10 characterizes the configurable throughput-latency frontier for BeamSearch and PipeSearch. Under BeamSearch, LIOS achieves an update-time reduction of up to 53% (delete) and 54% (insert) over the non-LIOS baseline when sweeping θ from 1% to 20%. At the default θ = 5%, delete time already decreases by 38% and insert time by 48%, while mean search latency grows by less than 3%. Under PipeSearch, LIOS achieves an update-time reduction of up to 47% (delete) and 49% (insert) over the non-LIOS baseline under the same sweep. Even at conservative thresholds, co-execution produces meaningful time savings; across the full 1%–20% sweep, mean latency growth stays under 7%. Exp #6 (Thread configuration sensitivity). Different deployments allocate varying fractions of CPU resources to search vs. update depending on workload priorities: a search-heavy service uses more search threads, while an ingestion-heavy pipeline favors update threads. Figure 11 evaluates LIOS across such configurations. Gains grow as a larger share of threads is allocated to search: at the default 28/4 search/update split, LIOS achieves an update-time reduction of up to 38% (delete) and 48% (insert) over the non-LIOS baseline under BeamSearch, up from negligible at the 4/28 split. PipeSearch

2.2× 1.6× 1.0×

0 Na

ı̈ve

tra

+In

Sensitivity and Generalization

st. uner fetch eline T s re +U Ba +P

(d) Insert speedup

Figure 9: Exp #4 (Breakdown analysis): SIFT-10M (R=32, θ=5%). Components added cumulatively from naive co-execution. (a, b) Search latency; (c, d) update speedup vs. w/o LIOS.

• w/o utilization tuner: use a fixed utilization ratio instead of LIOS’s adaptive control. • w/o cache prefetching: disable prefetching of searchcritical data after each co-execution episode. Figure 9 shows the results. Starting from naive coexecution without any control, the system achieves 5.1× delete speedup and 3.8× insert speedup, but at the cost of severely degraded search performance: average latency increases to 5.2× baseline during delete and 2.1× baseline during insert. Adding intra-vector decomposition (+Intra) enables fine-grained preemption, cutting delete-phase latency by 78% and insert-phase latency by 46% while retaining 2.6× and 2.4× update speedup. Replacing the fixed time budget with overrun-bounded time budgeting (+Est.) marginally improves speedup to 2.7×/2.6× with similar latency. Introducing adaptive utilization tuning (+Tuning) to adaptively enforce the latency threshold brings average latency within 10

Delete Phase

Merge Phase

Avg

P95

P99

10 5 Baseline 1

10 5 0

Threshold(%)

Latency (ms)

Time (s)

5 0

Baseline 1

5 0

Baseline 1

Threshold(%)

(b) Beam: Delete-phase latency

(a) Beam: Execution time

Baseline 1

Threshold(%)

1e3

Baseline 1

Latency (ms)

Time (s)

1e3

10 5 0

Baseline 1

Threshold(%)

(d) Pipe: Execution time (e) Pipe: Delete-phase latency (f) Pipe: Insert-phase latency Figure 10: Exp #5 (Latency threshold sensitivity): SIFT-10M, Testbed B; R=96. Top row: BeamSearch; bottom row: PipeSearch. Delete Speedup

7.5 5.0 2.5 0.0

4/28 8/24 12/20 16/16 20/12 24/8 26/6 27/5 28/4

Search/Update threads

0.5 0.0

4/28 8/24 12/20 16/16 20/12 24/8 26/6 27/5 28/4

Search/Update threads

8/24 12/20 16/16 20/12 24/8

26/6

27/5

5.0 2.5 0.0

28/4

4/28

4 2 4/28

8/24 12/20 16/16 20/12 24/8

26/6

Search/Update threads

26/6

27/5

28/4

8/24 12/20 16/16 20/12 24/8

Search/Update threads

(b) Beam: Delete-phase latency Latency (ms)

Speedup

1.0

4/28

7.5

Search/Update threads

(a) Beam: Speedup 1.5

w/ LIOS

Latency (ms)

w/o LIOS Latency (ms)

Latency (ms)

Speedup

Merge Speedup

27/5

28/4

6 4 2 0

4/28

8/24 12/20 16/16 20/12 24/8

26/6

27/5

28/4

Search/Update threads

(d) Pipe: Speedup (e) Pipe: Delete-phase latency (f) Pipe: Insert-phase latency Figure 11: Exp #6 (Thread configuration sensitivity): SIFT-10M, Testbed B; R=96, θ = 5%. Top: BeamSearch; bottom: PipeSearch. Left: speedup; right: mean search latency (w/o LIOS vs. w/ LIOS).

exhibits the same pattern, reaching 40% and 42% at the 28/4 split. This is expected: more search threads generate more I/O idle periods, creating additional overlap opportunities for LIOS. Notably, LIOS provides meaningful speedup across all tested thread ratios, confirming its applicability to a wide range of workload mixes. Exp #7 (Graph degree sensitivity). Table 3 shows that coexecution gains diminish as graph degree increases. For BeamSearch, LIOS achieves an update-time reduction of up to 55% (delete) and 57% (insert) over the non-LIOS baseline at R=32, which narrows to 38% and 48% at R=96. PipeSearch follows the same trend: the reduction decreases from 56% to 40% for delete and from 55% to 42% for insert. The insert-side decline is milder because insert operations are intrinsically less compute-intensive than delete processing. Across all configurations, QPS drop remains under 4.1% and search latency growth stays within the target budget. This trend is expected: larger R increases per-update computation, including more distance evaluations and graph maintenance, while search-side I/O idle time does not grow with

R. Each update must therefore be split into more slices to fit within the same idle windows, raising scheduling overhead and reducing the net benefit.

Exp #8 (Dataset scale sensitivity). We sweep SIFT from 10M to 500M vectors on Testbed A. As shown in Table 4, delete-phase speedup remains consistent across all scales (1.16 – 1.27×). Insert-phase speedup is lower at 200M (1.13×) and 500M (1.04×) than at 10M – 100M (1.21 – 1.36×); this is an artifact of sharded index construction, where memory constraints force multi-shard builds that leave many nodes with degree well below R, replacing full ROBUSTP RUNE with inexpensive appends and thus reducing the CPUintensive work available for LIOS; profiling confirms the pruning ratio drops from 100% at 100M to 3.6% and 12.4% at 200M and 500M. Mean latency overhead stays within 7% across all scales, confirming that LIOS’s effectiveness is scaleindependent. 11

Table 3: Exp #7 (Graph degree sensitivity): SIFT-10M, Testbed B; 28/4 threads, θ = 5%. Workload

Speedup

Delete phase

Insert phase

Delete

Insert

Time (s) w/o→w/

QPS↓ (%)

Lat↑ (ms)

Time (s) w/o→w/

QPS↓ (%)

Lat↑ (ms)

Beam Beam Beam

32 64 96

2.23× 1.82× 1.61×

2.34× 2.12× 1.94×

1987.7→892.9 7456.9→4096.8 11793.8→7349.2

2.59±0.11 2.92±0.25 2.61±0.08

+0.202±0.009 +0.252±0.028 +0.209±0.009

568.3→242.8 1790.4→845.7 2735.3→1412.9

2.67±0.48 3.46±0.15 2.54±0.19

+0.207±0.042 +0.290±0.013 +0.217±0.018

Pipe Pipe Pipe

32 64 96

2.29× 1.93× 1.67×

2.24× 2.08× 1.73×

2739.7→1199.0 10603.8→5507.1 16666.3→10006.1

4.08±0.08 2.08±0.11 2.92±0.07

+0.318±0.007 +0.149±0.011 +0.213±0.006

783.3→349.6 2663.9→1279.8 3984.0→2303.2

3.71±0.23 -0.06±0.27 3.78±0.43

+0.291±0.018 -0.010±0.021 +0.317±0.045

Table 4: Exp #8 (Dataset scale): SIFT at 10M–500M, OdinANN backend, default settings (§6.1). Dataset

Workload

SIFT-10M Beam (OdinANN) SIFT-20M Beam (OdinANN) SIFT-50M Beam (OdinANN) SIFT-100M Beam (OdinANN) SIFT-200M Beam (OdinANN) SIFT-500M Beam (OdinANN)

6.6

Speedup

Delete-phase latency change (%)

Insert-phase latency change (%)

Delete Insert

Avg

P95

P99

Avg

P95

P99

1.19× 1.21× 1.17× 1.26× 1.18× 1.28× 1.20× 1.36× 1.27× 1.13× 1.16× 1.04×

+6.9±0.36 +7.0±0.21 +6.6±0.14 +7.0±0.10 +6.7±0.08 +6.7±0.07

+3.6±0.53 +3.6±0.40 +3.2±0.19 +3.1±0.13 +2.9±0.10 +2.6±0.07

+8.0±4.76 +7.2±3.07 +6.8±1.93 +5.6±1.36 +7.0±1.08 +4.9±0.90

+4.8±0.29 +4.4±0.23 +5.9±0.15 +6.6±0.10 +3.0±0.12 +1.8±0.07

+6.1±0.38 +5.6±0.32 +7.5±0.21 +8.2±0.15 +3.2±0.17 +2.0±0.09

+9.2±4.84 +8.7±2.47 +7.5±0.34 +8.3±0.25 +4.6±0.29 +2.4±0.14

Additional Experiments

to a single SSD page read; Gorgeous [28] revisits caching and layout designs to achieve higher throughput with fewer disk accesses. VeloANN [29] combines locality-aware layout, buffer pooling, and coroutine-based async execution to reduce storage stalls. Another line of research aims to entirely mask I/O latency: PipeANN [7] pipelines computation and SSD I/Os to narrow the gap between disk-based and in-memory searches; Li et al. [18] survey memory, disk, and algorithmlayer designs targeting this I/O bottleneck. However, these search-centric optimizations primarily focus on accelerating query execution, often leaving residual CPU idle time during unresolved I/O bottlenecks unexploited.

We include two additional studies in the Appendix in the supplementary file. Exp #9 evaluates the latency statistics used by the utilization tuner and shows that adding P95 or P99 to the observed signal tightens latency control while preserving comparable delete speedup. Exp #10 examines resource utilization and shows that LIOS does not increase search-side disk traffic, roughly doubles effective CPU utilization, and adds only KiB-level checkpoint memory overhead.

Related Work

Some ANNS systems target update performance. FreshDiskANN [22] buffers inserts and deletes in a shortterm in-memory index and periodically merges them into a long-term SSD index at a cost proportional only to the change set. SPFresh [27] builds on SPANN with a cluster-partitioned index and incremental vector reassignment, achieving update throughput comparable to full rebuilds with lower overhead than graph-based methods. IP-DiskANN [26] supports direct in-place updates on the graph, avoiding periodic merges while preserving recall under streaming updates. OdinANN [9] preserves stable search performance under dynamic vector insertions through an in-place insertion strategy.

DiskANN [11] and SPANN [3] are two pioneering disk-based ANNS systems. DiskANN adopts a graph-based index inspired by prior in-memory graph-based indexes (e.g., NSG [4] and HNSW [19]), while SPANN adopts a cluster-based index that organizes vectors into partitions for disk-efficient retrieval. LIOS specifically targets graph-based ANNS systems (including DiskANN and its variants) as their updates are compute-bound and can effectively fill CPU idle time during search I/O stalls. SPANN’s updates, by contrast, are I/O-bound, leaving limited room for such co-execution. Several follow-up studies of DiskANN focus on optimizing search performance, primarily by reducing disk I/Os or hiding I/O latency. One line of research improves data layout and locality to minimize redundant reads during graph traversal: Starling [24] co-optimizes data layout and search flows to shorten traversal paths; PageANN [16] introduces a page-aligned graph layout to ensure that each hop maps

LIOS focuses on resource utilization rather than optimizing search or updates in isolation. It schedules update work to run during I/O stalls in search threads, exploiting otherwise wasted CPU idle time. This co-execution strategy improves resource utilization without requiring new index structures or sacrificing search latency. 12

Conclusion

[10] Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. Accelerating large-scale inference with anisotropic vector quantization. In International Conference on Machine Learning (ICML), 2020.

LIOS is a search-update co-execution framework for improving resource efficiency in disk-based graph ANNS systems. By harnessing intra-request CPU idle time during searchside I/O stalls, LIOS runs fine-grained update work without reducing the CPU budget for search. Its resumable update decomposition, overrun-bounded time budgeting, and adaptive utilization tuning fit update tasks into short, variable stall windows while controlling search latency. Evaluations show that LIOS accelerates updates by up to 2.68× in insertion and 2.18× in deletion while keeping search latency bounded.

[11] Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. DiskANN: Fast accurate billion-point nearest neighbor search on a single node. In Advances in Neural Information Processing Systems (NeurIPS), 2019. [12] Herve Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010.

References [1] Sunil Arya and David M Mount. Approximate nearest neighbor queries in fixed dimensions. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 1993.

[13] Hervé Jégou, Romain Tavenard, Matthijs Douze, and Laurent Amsaleg. Searching in one billion vectors: re-rank with source coding. In IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2011.

[2] Artem Babenko and Victor Lempitsky. Efficient indexing of billion-scale datasets of deep descriptors. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.

[14] Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billionscale similarity search with gpus. IEEE Transactions on Big Data, 2019.

[3] Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. SPANN: Highly-efficient billion-scale approximate nearest neighborhood search. In Advances in Neural Information Processing Systems (NeurIPS), 2021.

[15] Kanchan Joshi, Anuj Gupta, Javier González, Ankit Kumar, Krishna Kanth Reddy, Arun George, Simon Lund, and Jens Axboe. I/o passthru: Upstreaming a flexible and efficient i/o path in linux. In USENIX Conference on File and Storage Technologies (FAST), 2024.

[4] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Fast approximate nearest neighbor search with the navigating spreading-out graph. Proceedings of the VLDB Endowment (PVLDB), 2019.

[16] Dingyi Kang, Dongming Jiang, Hanshen Yang, Hang Liu, and Bingzhe Li. Scalable disk-based approximate nearest neighbor search with page-aligned graph. arXiv preprint arXiv:2509.25487, 2025.

[5] g4197. FreshDiskANN baseline implementation. https://github.com/g4197/ FreshDiskANN-baseline, 2024. Commit 8ea2f4d. [6] Jianyang Gao and Cheng Long. RaBitQ: Quantizing high-dimensional vectors with a theoretical error bound for approximate nearest neighbor search. In ACM SIGMOD International Conference on Management of Data (SIGMOD), 2024.

[17] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. Retrieval-augmented generation for knowledgeintensive NLP tasks. In Advances in Neural Information Processing Systems (NeurIPS), 2020.

[7] Hao Guo and Youyou Lu. Achieving low-latency graphbased vector search via aligning best-first search algorithm with SSD. In USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2025. [8] Hao Guo and Youyou Lu. PipeANN implementation. https://github.com/thustorage/PipeANN, 2025. Commit e6acdec.

[18] Liang Li, Shufeng Gong, Yanan Yang, Yiduo Wang, and Jie Wu. I/o optimizations for graph-based diskresident approximate nearest neighbor search: A design space exploration. Proceedings of the VLDB Endowment (PVLDB), 2026.

[9] Hao Guo and Youyou Lu. OdinANN: Direct insert for consistently stable performance in billion-scale graphbased vector search. In USENIX Conference on File and Storage Technologies (FAST), 2026.

[19] Yu A Malkov and Dmitry A Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018. 13

[20] Microsoft. SPACEV1B: A billion-scale vector dataset for text descriptors. https: //github.com/microsoft/SPTAG/tree/master/ datasets/SPACEV1B, 2020. [21] Emanuel Parzen. On estimation of a probability density function and mode. The Annals of Mathematical Statistics, 1962. [22] Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. FreshDiskANN: A fast and accurate graph-based ann index for streaming similarity search. arXiv preprint arXiv:2105.09613, 2021. [23] Philip Sun, David Simcha, Dave Dopson, Ruiqi Guo, and Sanjiv Kumar. Soar: Improved indexing for approximate nearest neighbor search. In Advances in Neural Information Processing Systems (NeurIPS), 2023. [24] Mengzhao Wang, Weizhi Xu, Xiaomeng Yi, Songlin Wu, Zhangyang Peng, Xiangyu Ke, Yunjun Gao, Xiaoliang Xu, Rentong Guo, and Charles Xie. Starling: An I/O-efficient disk-resident graph index framework for high-dimensional vector similarity search on data segment. In ACM SIGMOD International Conference on Management of Data (SIGMOD), 2024. [25] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. Proceedings of the VLDB Endowment (PVLDB), 2021. [26] Haike Xu, Magdalen Dobson Manohar, Philip A Bernstein, Badrish Chandramouli, Richard Wen, and Harsha Vardhan Simhadri. In-place updates of a graph index for streaming approximate nearest neighbor search. arXiv preprint arXiv:2502.13826, 2025. [27] Yuming Xu, Hengyu Liang, Jin Li, Shuotao Xu, Qi Chen, Qianxi Zhang, Cheng Li, Ziyue Yang, Fan Yang, Yuqing Yang, et al. SPFresh: Incremental in-place update for billion-scale vector search. In ACM Symposium on Operating Systems Principles (SOSP), 2023. [28] Peiqi Yin, Xiao Yan, Qihui Zhou, Hui Li, Xiaolu Li, Lin Zhang, Meiling Wang, Xin Yao, and James Cheng. Gorgeous: Revisiting the data layout for disk-resident high-dimensional vector search. In ACM SIGMOD International Conference on Management of Data (SIGMOD), 2026. [29] Weichen Zhao, Yuncheng Lu, Yao Tian, Hao Zhang, Jiehui Li, Minghao Zhao, Yakun Li, and Weining Qian. Optimizing SSD-resident graph indexing for high-throughput vector search. arXiv preprint arXiv:2602.22805, 2026.

Table 7: Exp #10 (Resource utilization): Phase-wise CPU utilization on SIFT-10M/Testbed B (R=96, 28/4 threads, θ=5%). w/o = without LIOS; w/ = with LIOS.

Additional Experiments

We report two additional experiments on SIFT-10M using Testbed B. We first study how the observed latency statistics affect the online tuner’s behavior, then measure disk I/O, CPU utilization, and checkpoint memory overhead.

Search Algo. Phase Util. (w/o) Util. (w/) BeamSearch Delete BeamSearch Insert PipeSearch Delete PipeSearch Insert

Exp #9 (Observed latency statistics). We compare three choices of observed latency statistics (mean only, mean+P95, and mean+P95+P99) under the default BeamSearch configuration. As shown in Table 5, incorporating P95 notably tightens mean-latency control (overhead drops from +2.975% to +1.879%) while further reducing tail latency. Adding P99 yields diminishing returns because P99 samples are sparser and noisier, making online adjustment less stable. Delete speedup stays comparable across all three settings (1.88– 1.94×), confirming that tail-aware observed statistics curb burst-driven overscheduling without sacrificing overlap opportunity.

Memory Usage (KiB)

|Rres | = 32

Mean Mean+P95 Mean+P95+P99

1.88× 1.94× 1.92×

P95 lat.

P99 lat.

+2.975% −1.747% −2.481% +1.879% −2.744% −3.144% +1.747% −2.911% −3.738%

Table 6: Exp #10 (Resource utilization): Average disk I/Os per query on SIFT-10M/Testbed B. Search Algo. Avg. I/Os (w/o) Avg. I/Os (w/) Change (%) 119.17 120.38

119.17 120.20

|Rres | = 64

+98.6 +128.3 +101.4 +93.7

|Rres | = 96

7.5 5.0 2.5 100

200

300

400

500

Figure 12: Exp #10 (Resource utilization): Checkpoint memory overhead on SIFT-10M/Testbed B.

Exp #10 (Resource utilization analysis). We measure three resources to understand where LIOS’s gains come from: search-side disk I/O, CPU utilization, and checkpoint memory. Table 6 first shows that LIOS does not increase search-side disk traffic: BeamSearch has identical average I/O counts with and without LIOS (119.17 I/Os/query), while PipeSearch changes only from 120.38 to 120.20 I/Os/query (−0.15%). Table 7 then shows that LIOS converts idle/polling windows into productive update work, roughly doubling effective utilization across both phases (93–128% improvement). Finally, Figure 12 shows that this added state is small: each checkpoint remains at the KiB level; for example, selecting R=96 from a candidate pool of size 500 requires less than 10 KiB.

BeamSearch PipeSearch

0.535 0.603 0.728 0.713

Pool Size

Table 5: Exp #9 (Observed latency statistics): SIFT-10M, BeamSearch + FreshDiskANN, Testbed B; 28/4 threads, θ=5%. Results averaged over R ∈ {32, 64, 96}. Observed latency Delete spd. Mean lat. statistics

0.269 0.264 0.362 0.368

Improvement (%)

+0.00 -0.15

Leveraging I/O Stalls for Efficient Scheduling in ANNS

Related documents