What is a generation counter?

A generation counter is a small integer, incremented once per query, that lets a search algorithm mark nodes as “visited” without ever clearing that marking between queries. Instead of resetting a data structure back to an empty state before each new search, every node stores the number of the last query that touched it, and a node counts as visited only when its stored number matches the number of the query currently running — a trick that turns an operation whose cost would otherwise scale with the size of the whole graph into one that costs nothing at all.

What problem does a generation counter actually solve?

The most natural way to track which nodes a search has already examined is a visited set that starts empty and gets populated as the search proceeds. That works correctly, but it raises an awkward question: what happens to that set once the query finishes and the next one begins? If the implementation reuses the same underlying array or bitset across queries — which is desirable, since allocating a fresh one for every single search adds both memory-allocation overhead and pressure on the memory allocator — then that array has to be reset to a clean state before the next query can trust it. Clearing a bitset sized to the whole graph means touching every single bit, and on a graph with tens of millions of nodes, that reset can end up costing as much as the search itself, even though the search may have only touched a few hundred of those nodes.

A generation counter sidesteps the reset entirely. Rather than storing a single bit per node that means “visited” or “not visited,” each node gets a small integer field. A global counter increments by one every time a new query starts. When the search wants to check whether a node has been visited, it doesn’t ask “is this node marked?” — it asks “does this node’s stored number equal the current query’s number?” A node that was touched during query number 47 will have 47 stored in that field; if the current query is number 48, that comparison fails, and the node is correctly treated as unvisited, with no reset step required anywhere. Marking a node as visited during the current query is just as cheap: overwrite its field with the current generation number.

This turns both operations — checking membership and marking a node — into simple, constant-time integer comparisons and writes, with no dependency on how large the graph is or how many nodes the previous query touched. The technique isn’t unique to HNSW; it’s a general pattern used anywhere a data structure needs “clear all” semantics applied frequently to something too large to actually clear each time.

How does this fit alongside the bitset approach to a visited set?

A plain bitset and a generation-counted array solve the same problem — fast membership checks during a single search — but they part ways on what happens between searches. A bitset needs an explicit reset, whether that means zeroing the whole array or, in a more careful implementation, only zeroing the specific positions that were set during the previous search (which requires keeping a separate list of exactly which positions those were, adding its own bookkeeping). A generation-counted array needs no reset step at all; the increment of the global counter is the entire reset, and it happens once regardless of graph size or how much of it the last query touched.

The trade-off is memory. A bitset uses one bit per node. A generation counter typically needs a wider integer field per node — commonly 32 bits, since a system serving a high volume of queries can run through billions of query numbers over the index’s lifetime, and the counter must be wide enough that it doesn’t wrap around and collide with an old marking still sitting in the array. That’s a meaningfully larger footprint per node than a single bit, so the generation-counter approach spends more static memory to save on repeated per-query reset work. For a system serving many queries per second against a large graph, that trade is usually worth making, since the reset cost saved per query, multiplied across a high query rate, dwarfs the fixed memory cost paid once.

There is one subtlety worth naming explicitly: if the counter is stored in a fixed-width integer and the system runs long enough, it can theoretically wrap back around to a value it has used before, which would cause old, stale markings to be misread as belonging to the current query. In practice this is avoided simply by making the counter wide enough — a 64-bit counter incrementing once per query would take an astronomically long time to wrap, which is why production implementations that care about correctness under sustained load tend to prefer the wider field even though it costs a little more memory per node than a 32-bit one would.

Where does this show up in an actual HNSW implementation?

Inside HNSW‘s layer-search routine, the generation counter (or its bitset equivalent) sits behind exactly the same visited-set check described on that page — before the algorithm computes a distance to a candidate node or expands its neighbor list, it checks whether that node has already been processed during the current traversal. The generation-counter version of that check simply replaces “is this bit set?” with “does this node’s stored generation equal the query’s generation?”, and replaces “clear the bits I set” with “increment the query counter by one.” Everything else about how the visited set participates in the search — when nodes get marked, why a node can be marked visited even after being rejected as a result, and the fact that the whole thing is scoped to a single query — carries over unchanged.

Implementations that serve a high volume of queries against a large, persistent graph tend to reach for the generation-counter pattern specifically because it removes a cost that would otherwise show up on every single query regardless of how selective that query’s search actually was. A system fielding thousands of queries per second against a graph with tens of millions of nodes cannot afford a reset step whose cost is tied to graph size rather than to the work an individual query actually does, and the generation counter is one of the more common ways production systems make that cost disappear.

Having seen how a generation counter avoids paying reset costs on every query, it’s worth reading the visited set glossary page next if you haven’t already, since that page covers the membership-checking role this counter fills in more general terms, including the plain hash-set and bitset alternatives it’s being compared against here. From there, the HNSW search algorithm page walks through exactly where in the traversal these checks happen, which is the best place to see the generation counter operating as part of a complete query rather than in isolation.