Towards Real-Time Maintenance of HNSW for ANN Search on Edge Devices

Edge intelligence requires fast approximate nearest neighbor (ANN) search on mobile devices with tight memory and power budgets. Under frequent updates, the mainstream HNSW index suffers from node isolation, where nodes lose incoming edges. This leads to fragmented graph connectivity, degraded recall, and increased latency. Such issues are exacerbated on resource-limited edge devices, where rapid data changes render traditional index reconstruction impractical. This paper presents a lightweight, real-time maintenance framework for HNSW that dynamically detects and repairs isolated nodes. By analyzing the root causes of connectivity loss, we classify isolated nodes into direct and indirect types, each with a tailored maintenance strategy. Indirect isolations are mitigated by integrating auxiliary edges to the main index, while direct isolations are managed via a compact, extra index. During queries, both indexes are searched concurrently to ensure complete coverage with minimal overhead. Experimental results show that the proposed approach effectively eliminates isolated nodes and stabilizes recall, with at most 10% latency overhead and less than 2% additional memory footprint, enabling practical on-device vector search under dynamic data updates.