What is a skip list?

A skip list is a data structure that keeps its values sorted while stacking several shorter “express lane” layers of connections on top of a single fully-detailed bottom layer, letting a search jump across large stretches of the list quickly before dropping down to careful, step-by-step movement near its actual target, and this exact layered strategy is the direct conceptual ancestor of HNSW‘s own layered graph.

How does a skip list’s layered structure actually let it search faster than an ordinary sorted list?

An ordinary sorted list requires walking through its values roughly one at a time until the target position is reached, since there’s no way to skip ahead without checking what comes in between. A skip list solves this by building several additional layers on top of its full bottom layer, where each higher layer contains a randomly-chosen, progressively smaller subset of the values below it, connected by longer-reaching links. Searching a skip list means starting at the top, sparsest layer and moving as far as possible using its long-reaching connections before dropping down to the next, denser layer once the search overshoots or gets close enough, repeating this drop-down process until the search finally reaches the fully-detailed bottom layer, where the exact target actually gets located.

How directly does this skip-list strategy map onto HNSW’s own layered graph structure?

HNSW‘s layered graph, covered throughout this site’s coverage of building the algorithm from scratch, follows this exact same coarse-to-fine search pattern: most vectors reside only in the bottom layer, with progressively fewer vectors populating each successively higher layer, covered elsewhere in this glossary as random level assignment, and search starts at the sparsest top layer, making large jumps across the graph before dropping down layer by layer to the dense bottom layer for fine-grained, precise movement near the query. This layered coarse-to-fine strategy is precisely the same underlying idea a skip list applies to searching a sorted sequence of values, just adapted from a simple sorted list to a much richer, general graph structure capable of representing nearest-neighbor relationships in high-dimensional space rather than a single linear ordering.

Why is it useful to recognize HNSW’s layered structure as an extension of this earlier, simpler skip-list idea?

Understanding a skip list’s simpler version of coarse-to-fine layered search makes it considerably easier to grasp why HNSW’s own layered structure works the way it does, since both structures rely on the exact same underlying insight: building sparse “express lane” shortcuts on top of a full, detailed bottom layer lets a search cover large distances quickly before slowing down for precise, fine-grained work only once it’s actually needed. Recognizing this shared lineage also clarifies that HNSW’s layering isn’t an arbitrary design choice specific to nearest-neighbor search, but rather a well-established general strategy for speeding up search across ordered or graph-structured data, adapted specifically to the demands of high-dimensional vector search.

A skip list’s layered “express lane” strategy is the direct conceptual ancestor of HNSW’s own layered graph, and understanding one makes the other considerably easier to reason about. From here, the pages on random level assignment and on how HNSW searches a graph step by step show exactly how this same coarse-to-fine strategy gets adapted to the more general graph structure HNSW actually relies on.