Vision transformers (ViTs) have seen an incredible rise in the past four years. They have an obvious upside: in a visual recognition setting, the receptive field of a pure ViT is effectively the entire image 1. In particular, vanilla ViTs maintain the quadratic time complexity (w.r.t. number of input patches) of language models with dense attention. Kernels in convolutional networks, on the other hand, have the property of being invariant to the input pixel/voxel that it is applied to, a feature that is typically referred to as translation equivariance. This is desirable because it allows the model to effectively recognize patterns and objects regardless of where they are located spatially. The weight sharing present in convolutional layers also makes convnets highly parameter-efficient and less prone to overfitting - a property ViTs do not have. As such, you might expect that ViTs and convnets are used equally in production environments that leverage visual models - ViTs for “global” tasks such as scene recognition and convnets for more “local” tasks such as object recognition. Even so, we’ve been inundated with work that utilizes ViTs, with bold high-level claims (mostly by media outlets) that convnets are a thing of the past. Curious to see if I could lend a hand in helping debunk this claim, I set out to figure whether or not a mostly vanilla ResNet could match or even exceed the performance of both ViT and ConvNeXt. The comparison to ConvNeXt is of particular interest, since it is a fully convolutional network that attempts to bridge the gap between transformers and convnets. With a bit of experimentation on Imagenet-1k, we can reach 82.0% accuracy with a 176x176 training image size with no extra data, matching ConvNeXt-T (v1, without pre-training a-la MAE) and surpassing ViT-S (specifically, the ViT flavor from DeiT-III). Training methodology We start by adopting the training methodology set in Pytorch’s late 2021 blog, where they achieved an impressive 80.8% accuracy on Imagenet-1k with a stock ResNet50 model. Here’s a couple of key points to note: We stick with SGD as the optimizer, rather than going for RMSProp or Adam (or any of their variants). The scheduler uses cosine decay with five warmup epochs and 600 total epochs. This may seem like an unnecessarily large number of epochs, but we’ll get around to reducing this later. We utilize a whole slew of augmentations found in modern literature, including, but not limited to: label smoothing, mixup, cutmix, and model EMA. To prevent overfitting on the validation dataset, we’ll skip hyperparameter tuning and grid search and stick with the stock training methodology listed out in the blog post. Nearly all of these training optimizations have already been used to boost the performance of modern visual recognition models, but adopting these changes don’t quite get us to the magical 82% accuracy we’re looking for. Architectural modifications The baseline ResNet architecture is strong but not optimal, so we adopt a few architectural modifications to enable better performance: ResNet-d First order of business is the embrace some “modernizations” to ResNet. For completeness, here are the changes listed out: The initial 7x7 convolution is changed to a sequence of three 3x3 convolutions with 32, 64, and 128 output channels, respectively. The stride remains on the first convolutional layer. With this change, we now use exclusively 3x3 and 1x1 convolutions across the entire network all while retaining the original size of the receptive field for the network head. Strides in downsampling residual blocks are moved from the first 1x1 convolutional layer to the subsequent 3x3 convolutional layer. This has the effect of capturing all input pixels in a downsampling block, since a strided 1x1 convolution effectively skips every other pixel. The max pooling in the stem is removed. The first 3x3 convolution of the first residual block now has a stride of two, matching the remaining residual blocks. While max pooling is theoretically useful for retaining edges, corners, and other low-level features, I haven’t found it to be particularly useful in practice. The strided 1x1 convolution in the shortcut connections of downsampling blocks is replaced with 2x2 average pooling followed by a standard 1x1 convolutional layer. Again, this has the effect of capturing all input activations rather than just one out of every four input channels. The resulting micro-optimizations result in an architecture that is extremely close to ResNet-d, with some very minor differences. ReLU -> SiLU ReLU has two weaknesses compared to other activation functions: 1) it is not smooth (ReLU is, strictly speaking, non-differentiable at 0), and 2) the “dying ReLU” problem, where pre-activation values are near-universally negative during a forward pass, causing gradients to always be zero and the neuron to carry no information. As a direct result, a number of novel activations have been proposed throughout the years - Leaky ReLU, Parametric ReLU, ELU, and Softplus are three well-known albeit older examples. The idea behind all of these is to fix one or both of the above problems; Parametric ReLU, for example, attempts to fix the dying ReLU problem by introducing a learnable parameter $\alpha$ that defines the slope the function for negative pre-activation values. For this model, I went with the SiLU, (also commonly known as Swish), defined by $SiLU(x) = \frac{x}{1+e^{-x}}$, which has already seen success with a number of visual recognition models. Since this switch enabled faster training, I reduced the number of epochs from 600 to 450. Although I could’ve used GELU, I decided to use SiLU because it has an inplace parameter and could serve as a drop-in replacement for ReLU in the original reference implementation. GELU or GLU variants (SwiGLU, GeGLU) might have performed slightly better as they are widely used in language models. Although GELU and SiLU are highly correlated 2, networks trained with GELU are not equivalent to networks trained with SiLU in terms of representational capacity due to differences in weight decay and initialization. Lastly, I hypothesize that a SiLU network would likely perform better with stochastic depth since ReLU may act like a weak implicit regularizer by adding sparsity to the network activations. This can be great for overparameterized models, but not for parameter-efficient models. SiLU, on the other hand, has nonzero gradients for all values $x$ except for $x \approx -1.278$. As such, with the switch from ReLU to SiLU, adding a bit of regularization might be warranted. I’ll have to experiment more with this in the upcoming weeks. Update (03/23/2024): After some experimentation, I found that stochastic depth with a drop probability of 0.1 negatively impacts the performance of the network (by about 0.2% or so), but reducing it to 0.05 results in what is effectively the same accuracy. I’ll need to play around with it a bit more. Split normalization Vanilla ResNet uses a generous amount of batch normalization (BN); one BN layer per convolutional layer to be exact. The original BN paper argues that BN improves internal covariate shift (ICS) - defined by the authors as the change any intermediate layer sees as upstream network weights shift - but this has since proven to be untrue (I’ll elaborate on this in a bit). I wanted to go back to the original ICS thesis, i.e. normalization in BN was meant to re-center the activations, while the learnable affine transformation immediately following normalization was meant to preserve each layer’s representational capacity. It simply made no sense to me that these two must be applied back-to-back. Furthermore, since backpropogation effectively treats each individual layer of neurons as an independent learner, the most sensible thing to do is to normalize layer inputs rather than outputs. Long story short, I found that splitting BN into two separate layers - pre-convolution normalization and post-convolution affine transformation - improves the network’s performance by over 0.4%. While this does negatively affect speed and memory consumption during training, it has zero impact on inference performance since the normalization and affine transformations can be represented as diagonal matrices and fused with the weights of the convolutional layer once the network is fully trained. Split normalization, visualized. I wanted to better understand the theory behind “split” normalization but couldn’t find it anywhere in ML literature3. As a result, I looked towards BN theory first; the most compelling research in my eyes comes from Santurkar et al.’s 2018 paper. In it, they show that BN often increases ICS. Instead, they argue that batch normalization works well because improves the first- and second-order properties of the loss landscape. Through a quick exercise, we can show that split normalization (SN) has the same effect. Let’s consider two networks - one without SN defined by loss function $L$ and one with SN defined by loss function $\hat{L}$. For the network with SN, the gradients through each of these layers is as follows: Where $m$ is the size of each mini-batch and $y_i$, $\hat{y}_i$, $\hat{x}_i$, $x_i$ represent the activations for the $i$th sample in our batch. In practice, the dimensionality of the activation tensors can be arbitrarily large or small (e.g. 3d for most convnets). With this, we can represent the full loss gradient via dot products: For a function $f(a)$, the L2 norm of its gradient $\left\Vert\frac{df}{da}\right\Vert$ is a good proxy for Lipschitzness. The same holds our loss function, i.e. we would like to show that $\left\Vert\frac{\partial\hat{L}}{\partial\mathbf{x}}\right\Vert \leq \left\Vert\frac{\partial L}{\partial\mathbf{x}}\right\Vert$. Given a matrix $\mathbf{A}$ and vector $\mathbf{b}$, the norm of the two multiplied together is bound above by the largest singular value of $\mathbf{A}$, i.e. $\Vert\mathbf{A}\cdot\mathbf{b}\Vert \leq s_{max}(\mathbf{A})\Vert\mathbf{b}\Vert = \sqrt{\lambda_{max}(\mathbf{W}^T\mathbf{W})}\Vert\mathbf{b}\Vert$. Given this, we have: Applying the reduction from C.2 in Santurkar et al., we get: In my eyes, we should separate the multiplicative term (i.e. $\frac{\gamma^2s_{max}^2}{\sigma^2}$) from the additive term (i.e. $- \frac{1}{m}\left\Vert\mathbf{1} \cdot \frac{\partial L}{\partial\mathbf{y}}\right\Vert^2 - \frac{1}{m}\left\Vert\frac{\partial L}{\partial\mathbf{y}} \cdot \mathbf{x}\right\Vert^2$) since a) the multiplicative effects can be counteracted by increasing or decreasing the learning rate and b) $\mathbf{W}$ tends to change much slower than other terms in the equation. In particular, the additive term is strictly negative, which means that the overall loss landscape is smoother, while the potentially large multiplicative upper bound implies that SN may, in certain situations, be increasing the Lipschitz constant of the loss. At the same time, ICS at the inputs of each layer is strictly decreased, as the learnable affine transformation now comes after the weights rather than before. The results The final 26M parameter model successfully reaches 82.0% accuracy on Imagenet-1k without any external sources of data! In the spirit of modern machine learning research, let’s give this network a fancy name: GResNet (Good/Great/Gangster/Godlike ResNet). Model Accuracy Params Throughput GResNet 82.0%* 25.7M 2057 im/s ConvNeXt 82.1% 28.6M 853 im/s ViT (DeiT) 81.4% 22.0M 1723 im/s Comparison of different models. Throughput calculated on a single Nvidia A100 with batch size 256 without network optimizations. *Accuracy improves to 82.2% and throughput drops to 1250 im/s when we use ConvNeXt's train image size of 224x224 instead of 176x176. The GResNet model definition is available here, while weights are available here. Accuracy curve during training. Ending words What exactly have we shown here? With some simple modifications to ResNet, we can attain excellent performance - on par or better than both ViT and a ViT-inspired convnet (ConvNeXt) on smallish datasets. ConvNets never die, they just Transform — Peyman Milanfar (@docmilanfar) October 27, 2023 ResNet strikes back... again? You might be asking: why Imagenet-1k? Aren’t there a number of much larger labelled visual datasets i.e. YFCC, LAION, etc? Secondly, since modern LLMs are exclusively transformer-based, isn’t it beneficial to also use transformers for vision in order to take advantage of cross-attention or by linearly projecting patches into the decoder? The answer is yes: for large multimodal models bound by text, self-attention reigns supreme. But small models (e.g. most embedding models) are arguably more important because of their portability and adaptability, and these models benefit greatly from the exact type experiment of outlined in this post: strong augmentation with limited data trained across many epochs. This is exactly the type of data that Imagenet-1k represents. And on the topic of ViTs being superior to convnets on large datasets: the 2023 paper titled Convnets match vision transformers at scale from folks at Google DeepMind is worth a read. The concluding section contains a stark result: “Although the success of ViTs in computer vision is extremely impressive, in our view there is no strong evidence to suggest that pre-trained ViTs outperform pre-trained ConvNets when evaluated fairly.” This simply reinforces a lesson that ought to be repeated: optimizations to model architecture should always come after 1) a large, high-quality dataset, 2) a solid, highly parallelizable training strategy, and 3) having lots of H100s. I’d argue that the bulk of transformers’ success has come from their ability to be efficiently and effectively scaled to hundreds of billions of parameters - scaling that could theoretically also be done with RNNs if research scientists had decades of time to train them (spoiler: they don’t). Addendum - comparing embedding quality I thought it might be interesting to compare embeddings from GResNet, ConvNeXt, and ViT by storing and indexing the embeddings from each model in Milvus: >>> from milvus import default_server >>> from pymilvus import MilvusClient >>> default_server.start() >>> client = MilvusClient(uri="http://127.0.0.1:19530") >>> # initialize model, transform, and in1k val paths ... >>> with torch.no_grad(): ... for n, path in enumerate(paths): ... img = Image.open(path).convert("RGB") ... feat = gresnet(transform(img).unsqueeze(0)) ... client.insert(collection_name="gresnet", data=[feat]) ... >>> I removed the model initialization and data loading snippets for brevity and used Euclidean/L2 as the distance metric with no indexing (i.e. FLAT). With that step done, we can then query the collections to get results that look like this: One could argue that GResNet tends to pick out images which are stylistically closer to the query image in addition to being the same class, but aside from that, the results between all three models are very comparable. For a visual recognition model, the receptive field is the effective area of the input Nd-xels that a layer or neuron “sees” and can capture. Early layers in a pure convolutional model, for example, have a very small receptive field, while each layer in a vision transformer with dense attention sees the entire input image. ↩ There exists a fairly accurate approximation that relates GELU and SiLU: $GELU(x) = \frac{SiLU(1.702x)}{1.702}$. ↩ Please reach out to me if you know of prior work that implements this so I can give it a proper citation. ↩

… glorified marketing for portfolio companies, that is I came across one of a16z’s blog posts on Hacker News today, titled Emerging Architectures for LLM Applications. For folks who didn’t catch it, here’s the tl;dr: The emerging LLM stack is composed of several elements centered around data orchestration tools such as Langchain and Llamaindex. Data pipelines, embedding models, vector databases, and queries form the primary input for these orchestration tools. The stack is based on in-context learning, where off-the-shelf LLMs are used and their behavior is controlled through prompting and conditioning on contextual data. Strategies for prompting LLMs are becoming increasingly complex and are a core differentiating factor for both closed-source and open-source LLMs. Of these LLMs, strategies for GPT-3.5 and GPT-4 are most common, seeing as OpenAI is the current leader. AI agents - programmatic runtimes that can reason and plan - excite both developers and researchers alike, but don’t work just yet. Most agent frameworks are currently in PoC phase. Overall, I thought the article was informative, but I was surprised that the section on vector databases mentions neither Milvus nor Zilliz, especially since Milvus was mentioned in an older a16z blog on data and ML infrastructure: Also of note: another Zilliz project (GPTCache) is listed in the post. My initial instinct was that Milvus was left off because it is part of the LF AI & Data Foundation rather being a project wholly owned by Zilliz, so I left a comment on the HN post that links back to the Milvus website. I came back a couple of hours later to find an interesting take: Full disclosure: we (Zilliz) raised $103M back in 2022, and Pinecone raised $100M this April. Running it back in my head, I felt that SheepHerdr’s response actually made excellent sense - a16z’s ultimate goal is to generate returns for LPs, and the best way to do that is by supporting founders and propping their portfolio companies. To me, this is also unequivocally unfair to Vespa, Weaviate, etc as it delivers a subliminal message that they have no realistic long-term chance in the vector database space relative to Pinecone. This, of course, is absolute nonsense: vector databases are NOT a zero-sum game. I dove a bit deeper and was surprised to find that this is fairly commonplace behavior for a16z as a firm: The aforementioned article also lists Databricks in the “Data Pipelines” section, but not Snowflake. There is a Snowflake loader for Langchain and a guide for using Llamaindex with Snowflake. Databricks is an a16z portfolio company. The Modern Transactional Stack doesn’t come close to listing all of the available data connectors. To be fair, Airbyte and Fivetran (an a16z portfolio company) are the two largest and most well-known, but to distill the entire segment to just two companies seems unfair. a16z’s crypto division has backed LayerZero, going as far as actively voting against Wormhole, a LayerZero competitor. Side note: LayerZero was also featured in a16z’s Crypto Startup School. These are just three random examples I dug out - there are probably many other examples in verticals that I am unfamiliar with. Other LLM/GenAI Infrastructure landscapes Here’s a couple alternative landscapes that are, in my eyes, more wholly representative: ML/AI/Data Landscape (Interactive version). Matt Turck’s MAD Landscape is arguably the most complete out there. Companies that do vector search are listed under “Infrastructure/Vector Database” and “Analytics/Enterprise Search” categories. It was released in February 2023 so it’s about 4 months old, but a good resource nonetheless. Future of AI-Native Infrastructure. This one’s from Wei Lien Dang and David Hershey of Unusual Ventures. I found this pretty unique as it has a vertical for AI agents. It’s unfortunately not as complete as the MAD Landscape (missing Vespa, Vectara, etc), but still a good overview. The New Language Model Stack. Sequoia Capital’s blog post on the LLM stack is also excellent. Milvus isn’t in the diagram, but it’s mentioned in the section on vector databases. Vector Database Landscape. Yingjun Wu’s infographic is centered specifically around vector search infrastructure. Final thoughts I have tremendous respect for a16z, a firm that helped pioneer the practice of working with and nurturing founders rather than forcing them out pre-IPO or minmaxing term sheets. Their content is also incredibly informative and valuable for understanding the nuances of building a company, from finding PMF to hiring executives. I also wholeheartedly understand a16z’s motivation for sharing knowledge and highlighting their portfolio companies, but to do so under the guise of being helpful and impartial is just plain silly. In particular, a16z’s blog post yesterday has as much to do with emerging strategies for portfolio company marketing as it does with emerging architectures for LLM applications. This practice would be somewhat analagous to Google putting paid URLs at the very top of search results without an “Ad” label. (To be clear, Google doesn’t do this.) I’d like to end with some glorified marketing of my own: % pip install milvus

(Note: A version of this post has been cross-published to the Zilliz blog) In a previous blog, we took a look at scalar quantization and product quantization - two indexing strategies which are used to reduce the overall size of the database without reducing the scope of a search. To better illustrate how scalar quantization and product quantization works, we also implemented our own versions in Python. In this tutorial, we’ll build on top of that knowledge by looking at what is perhaps the most commonly used primary algorithm today: Hierarchical Navigable Small Worlds (HNSW). HNSW performs very well when it comes to both speed and accuracy, making it an incredibly robust vector search algorithm. Despite it being popular, understanding HNSW can be a bit tricky. In the next couple of sections, we’ll break down HNSW into its individual steps, developing our own simple implementation along the way. HNSW basics Recall from a previous post that there are four different types of vector search indexes: hash-based, tree-based, cluster-based, and graph-based. HNSW fits firmly into the lattermost, combining two core concepts together - the skip list and Navigable Small World (NSW). Let’s first dive into these two concepts individually before discussing HNSW. Skip list overview First up: skip lists. Recall the venerable linked list - a well-known data structure where each element in the list maintains a pointer the the next element. Although linked lists work great for implementing LIFO and FIFO data structures such as stacks and queues, a major downside is their time complexity when it comes to random access: O(n). Skip lists aim to solve this problem by introducing additional layers, allowing for O(log n) random access time complexity. By incurring extra memory (O(n log n) space complexity as opposed to O(n) for a normal linked list) and a bit of runtime overhead for inserts and deletes. A skip list is essentially a multi-level linked list, where the upper levels maintain long connections. As we move down the layers, the connections become shorter and shorter, with the bottommost layer being the “original” linked list containing all of the elements. The image below illustrates this: The skip list, illustrated. Higher layers have fewer elements. To reach element i in a skip list, we first start at the highest layer. Once we find a node that corresponds to an element in the list that is greater than i, we then backtrack to the previous node and move to the layer below. This continues all the way until we’ve found the element we’re looking for. Note that skip lists only work for sorted lists, as we need a way to directly compare the magnitude of two objects. Inserts work probabilistically. For any new element, we first need to figure out the layer with which the element appears first. The uppermost layer has the lowest probability, with increasing probability as we move down in layers. The general rule is that any element in a layer will appear in layer above it with some pre-defined probability p. Therefore, if an element first appears in some layer l, it will also get added to layers l-1, l-2, and so on. Note that, while it is possible to have a terribly balanced skip list that performs no better than a standard linked list, the probability of this happening is incredibly low. What the heck is a Navigable Small World? Now that we’ve gotten skip lists out of the way, let’s take some time to talk about Navigable Small Worlds. The general idea here is to first imagine a large number of nodes in a network. Each node will will have short-, medium-, and long-range connections to other nodes. When performing a search, we’ll first begin at some pre-defined entry point. From there, we’ll evaluate connections to other nodes, and jump to the one closest to the one we hope to find. This process repeats until we’ve found our nearest neighbor. This type of search is called greedy search. For small NSWs in the hundreds or thousands of nodes, this algorithm works, but it tends to break down for much larger NSWs. We can fix this by increasing the average number of short-, medium-, and long-range connections for each node, but this increases the overall complexity of the network and results in longer search times. In the absolute “worst” case, where each node is connected to every other node in our dataset, NSW is no better than naïve (linear) search. NSWs are cool and all, but how does this relate to vector search? The idea here is to imagine all vectors in our dataset as points in an NSW, with long-range connections being defined by vectors which are dissimilar from one another and the opposite for short-range connections. Recall that vector similarity scores are measured with a similarity metric - typically L2 distance or inner product for floating point vectors and Jaccard or Hamming distance for binary vectors. By constructing an NSW with dataset vectors as vertices, we can effectively perform nearest neighbor search by simply greedily traversing the NSW towards vertices closer and closer to our query vector. HNSW, explained When it comes to vector search, we often have dataset sizes in the hundreds of millions or even billions of vectors. Plain NSWs are less effective at this scale, so we’ll need a better graph. HNSW extends NSW by borrowing from the concept of skip lists. Like the skip list, HNSW maintains multiple layers (hence the term Hierarchical Navigable Small World), only of NSWs instead of linked lists. The uppermost layer of an HNSW graph has few nodes and the longest links, while the bottommost layer has all nodes and the shortest links. During the search process, we enter a pre-defined point in the uppermost layer and greedily route ourselves towards the nearest neighbor to our query vector. Once we reach the nearest node, we then move to the second layer and repeat this process. This continues until we’ve reached our nearest neighbor. A diagram from the HNSW paper which visualizes the layered graph concept. Inserts work similarly to the skip list. For some vector v, We first traverse the first layer of the graph, finding its nearest neighbor before moving to the layer below it. We then traverse the graph again to find its nearest neighbor in the second layer. This process until we’ve reached the nearest neighbor in the bottommost graph. From here, we then need to determine which links (connections between vertices) to create. Again, we have a pre-defined parameter M which determines the maximum number of bidirectional links that we can add. These links are usually simply set as the nearest neighbors to v, but other heuristics can be used as well. The same process then repeats for the upper layers, assuming the vector appears there. As with the skip list, the query vector will appear in upper layers with exponentially decreasing probability. Specifically, the HNSW paper uses the equation floor(-ln(rand(0, 1))), where rand(0, 1) is a random number sampled from a uniform distribution between (0, 1]. Note how this does not actually constrain the minimum distance between any two vertices/vectors in a particular layer - it’s entirely possible that we end up with a poorly constructed graph, but the probability that this happens is incredibly low, especially as we scale up the number of vectors in the HNSW index. Implementing HNSW HNSW is not trivial to implement, so we’ll implement only a very basic version here. As usual, let’s start with creating a dataset of (128 dimensional) vectors: >>> import numpy as np >>> dataset = np.random.normal(size=(1000, 128)) The first step is to build the HNSW index. To do so, we’ll need to add each vector in our dataset one-by-one. Let’s first create a data structure to hold our index. In this basic example, we’ll use a list of lists to represent the index, with the inner lists corresponding to each layer/graph: >>> L = 5 # 5-layer HNSW >>> index = [[] for _ in range(L)] Every element in each graph is a 3-tuple containing the vector, a list of indexes that the vector links to within the graph, and the index for the corresponding node in the layer below it. For the bottommost layer, the third element of the 3-tuple will be set to None. Since every insert first requires a search for the nearest neighbor in graph, let’s implement that first. We can traverse any of the subgraphs in the index as so: def _search_layer(graph, entry, query, ef=1): best = (np.linalg.norm(graph[entry][0] - query), entry) nns = [best] visit = set(best) # set of visited nodes candid = [best] # candidate nodes to insert into nearest neighbors heapify(candid) # find top-k nearest neighbors while candid: cv = heappop(candid) if nns[-1][0] > cv[0]: break # loop through all nearest neighbors to the candidate vector for e in graph[cv[1]][1]: d = np.linalg.norm(graph[e][0] - query) if (d, e) not in visit: visit.add((d, e)) # push only "better" vectors into candidate heap if d < nns[-1][0] or len(nns) < ef: heappush(candid, (d, e)) insort(nns, (d, e)) if len(nns) > ef: nns.pop() return nns This code snippet is a bit more involved, but it’s much easier to understand with a bit of explanation. Here, we use a heap to implement a priority queue, which we use to order nearest neighbor vectors in the graph. Like all of the previous examples, I’m using L2 distance here, but this code can be extended to other distance metrics as well. We first populate the heap with the entry point. Here, all we’re doing is implementing greedy search. At every iteration, our goal is to update two variables: nns, our output list of nearest neighbors, and candid, a heap of candidate points. We evaluate all nearest neighbors to the “best” vector in candid, adding better (better means closer to the query vector) vectors to the output list of nearest neighbors as well as to the heap of candidate points for evaluation on the next iteration. This repeats until one of two stopping conditions is reached: we either run out of candidate points to evaluate, or we’ve determined that we can no longer do any better than what we already have. With top-k graph search out of the way, we can now now implement the top-level search function for searching the entire HNSW index: def search(index, query, ef=1): # if the index is empty, return an empty list if not index[0]: return [] best_v = 0 # set the initial best vertex to the entry point for graph in index: best_d, best_v = _search_layer(graph, best_v, query, ef=1)[0] if graph[best_v][2]: best_v = graph[best_v][2] else: return _search_layer(graph, best_v, query, ef=ef) We first start at the entry point (zeroth element in the uppermost graph), and search for the nearest neighbor in each layer of the index until we reach the bottommost layer. Recall that the final element of the 3-tuple will resolve to None if we are at the bottommost layer - this is what the final if statement is for. Once we reach the bottommost layer, we search the graph using best_v as the entry point. Let’s go back go the HNSW insert. We’ll first need to figure out which layer to insert our new vector into. This is fairly straightforward: def _get_insert_layer(L, mL): # ml is a multiplicative factor used to normalized the distribution l = -int(np.log(np.random.random()) * mL) return min(l, L) With everything in place, we can now implement the insertion function. def insert(self, vec, efc=10): # if the index is empty, insert the vector into all layers and return if not index[0]: i = None for graph in index[::-1]: graph.append((vec, [], i)) i = 0 return l = _get_insert_layer(1/np.log(L)) start_v = 0 for n, graph in enumerate(index): # perform insertion for layers [l, L) only if n < l: _, start_v = _search_layer(graph, start_v, vec, ef=1)[0] else: node = (vec, [], len(_index[n+1]) if n < L-1 else None) nns = _search_layer(graph, start_v, vec, ef=efc) for nn in nns: node[1].append(nn[1]) # outbound connections to NNs graph[nn[1]][1].append(len(graph)) # inbound connections to node graph.append(node) # set the starting vertex to the nearest neighbor in the next layer start_v = graph[start_v][2] If the index is empty, we’ll insert vec into all layers and return immediately. This serves to initialize the index and allow for successful insertions later. If the index has already been populated, we begin insertion by first computing the insertion layer via the get_insert_layer function we implemented in the previous step. From there, we find the nearest neighbor to the vector in the uppermost graph. This process continues for the layers below it until we reach layer l, the insertion layer. For layer l and all those below it, we first find the nearest neighbors to vec up to a pre-determined number ef. We then create connections from the node to its nearest neighbors and vice versa. Note that a proper implementation should also have a pruning technique to prevent early vectors from being connected to too many others - I’ll leave that as an exercise for the reader :sunny:. We now have both search (query) and insert functionality complete. Let’s combine everything together in a class: from bisect import insort from heapq import heapify, heappop, heappush import numpy as np from ._base import _BaseIndex class HNSW(_BaseIndex): def __init__(self, L=5, mL=0.62, efc=10): self._L = L self._mL = mL self._efc = efc self._index = [[] for _ in range(L)] @staticmethod def _search_layer(graph, entry, query, ef=1): best = (np.linalg.norm(graph[entry][0] - query), entry) nns = [best] visit = set(best) # set of visited nodes candid = [best] # candidate nodes to insert into nearest neighbors heapify(candid) # find top-k nearest neighbors while candid: cv = heappop(candid) if nns[-1][0] > cv[0]: break # loop through all nearest neighbors to the candidate vector for e in graph[cv[1]][1]: d = np.linalg.norm(graph[e][0] - query) if (d, e) not in visit: visit.add((d, e)) # push only "better" vectors into candidate heap if d < nns[-1][0] or len(nns) < ef: heappush(candid, (d, e)) insort(nns, (d, e)) if len(nns) > ef: nns.pop() return nns def create(self, dataset): for v in dataset: self.insert(v) def search(self, query, ef=1): # if the index is empty, return an empty list if not self._index[0]: return [] best_v = 0 # set the initial best vertex to the entry point for graph in self._index: best_d, best_v = HNSW._search_layer(graph, best_v, query, ef=1)[0] if graph[best_v][2]: best_v = graph[best_v][2] else: return HNSW._search_layer(graph, best_v, query, ef=ef) def _get_insert_layer(self): # ml is a multiplicative factor used to normalize the distribution l = -int(np.log(np.random.random()) * self._mL) return min(l, self._L-1) def insert(self, vec, efc=10): # if the index is empty, insert the vector into all layers and return if not self._index[0]: i = None for graph in self._index[::-1]: graph.append((vec, [], i)) i = 0 return l = self._get_insert_layer() start_v = 0 for n, graph in enumerate(self._index): # perform insertion for layers [l, L) only if n < l: _, start_v = self._search_layer(graph, start_v, vec, ef=1)[0] else: node = (vec, [], len(self._index[n+1]) if n < self._L-1 else None) nns = self._search_layer(graph, start_v, vec, ef=efc) for nn in nns: node[1].append(nn[1]) # outbound connections to NNs graph[nn[1]][1].append(len(graph)) # inbound connections to node graph.append(node) # set the starting vertex to the nearest neighbor in the next layer start_v = graph[start_v][2] Boom, done! All code for this tutorial can be accessed on Github: https://github.com/fzliu/vector-search.

In this four-part article, I’ll go over some of the lessons I learned living and doing business in China’s tech industry. During my time in China, I’ve led a team of 10+ engineers to develop a location-based IoT and sensing platform, co-founded an open-source project called Towhee, and developed countless relationships with folks in a number of difference cities (many of whom I now consider good friends). I’ll go over some of the common misconceptions about China ranging from living and working in China to the government’s pandemic response. I originally intended for part II of this blog post to cover the tech industry in more detail (996, CSDN, open-source, etc…), but given the current spike in COVID cases these past two weeks plus the current lockdown in Shanghai, I felt it was more appropriate to first cover pandemic life in China. As always, if you have any questions, comments, or concerns, feel free to connect with me on Twitter or LinkedIn. Thanks for reading! Before reading this blog post, I strongly recommend you read part I if you haven’t yet. Part I received much more exposure than I had anticipated; I received a lot of positive feedback and I enjoyed reading many of the responses, especially those which provided a different outlook on China and its citizens. While I had originally intended for part II to cover China’s tech industry, I decided to instead cover China’s handling of the pandemic first, given Shanghai’s current lockdown. Stocking up on food right before the Shanghai lockdown in March 2022. I imagine the conversation with supermarket staff went something like this: Q - What kind of ramen would you like? A - All if it. A couple of words before steaming ahead into part II: 1) This article will be focused around three pandemic stories from China which will depict how China’s zero-COVID policy has affected Chinese citizens. These purely anecdotal stories are not meant to directly prove a point or argue a cause; rather, my hope is that they can provide a “boots-on-the-ground” perspective for readers unfamiliar with life in China (and, to a lesser extent, other east Asian countries) during COVID. 2) Recent articles with visualizations which conveniently ignore certain population segments (or other statistical anomalies) have unfortunately reduced my faith in “data-driven” articles1. As such, a small portion of this blog post will be dedicated towards picking apart pure data-driven arguments against China’s COVID statistics. 3) Lastly, I’d like to remind everyone to keep comments civil. I was subject to a private but fairly negative personal attack from one of the readers over the Personal identity section in part I. As the post’s author, I’m fine with it, but do not subject other readers and community members to the same or similar treatment - it’s irresponsible and does nothing to improve the quality of the discussion. With that said, let’s dive in. Three pandemic stories It would be easy for me to simply “tell you” how the pandemic has changed China; instead, I’d like to start this blog post with three “pandemic stories” - short excerpts which highlight the scope with which China’s zero-COVID policy has affected the population. These purely anecdotal stories are not meant to directly prove a point or argue a cause; rather, my hope is that they can provide a “boots-on-the-ground” perspective. Alex’s story Alex (I’ve used an alias to ensure privacy) is a Taiwanese expat working in Shanghai. Her story is a bit unique given her background - she’s been in Shanghai since early 2020 and, due to quarantine policies on both sides of the Taiwan strait, hasn’t been back home in over two years. More on this in a bit. When Alex flew from Taiwan to Shanghai in February of 2020, she immediately found herself in unfamiliar territory. Streets were nearly completely empty, and the few folks who did wander outside were tightly masked. The only businesses open were supermarkets, which were required by central government policy to have workers and/or guards standing by entrances, recording everybody’s name, ID number, phone number, and body temperature. News on Wuhan and the COVID-related restrictions popping up around the country were being constantly broadcast by state-run media. Red propaganda posters filled the streets, warning the general populace to remain masked and to stay away from wild game (野味). As time progressed, it became clear to Alex that, while people living in Western countries had lost jobs and loved ones, people living in China lost significant freedom and social capital in a country already short on both. In a culture that prides itself on family and connectivity - especially during Lunar New Year 2 - not returning home for over two years is borderline criminal. However, for Alex, this was not by choice. The policy for foreign travelers entering Taiwan is 14 days of quarantine, while the policy for travelers entering Shanghai is 14 days of hotel quarantine plus another 7 days at home. Because no human contact is allowed during the entire quarantine period, these quarantine periods are generally referred to as isolation (隔离) in Mandarin. For Alex, spending over a month in quarantine/isolation would simply be unacceptable, especially as the rest of her co-workers are all in-office. Two years away from Taiwan also resulted in a loss of something known as household registration (户籍). Although it may not seem like a big deal, household registration is more significantly meaningful in Taiwan than residency in the USA or Canada - everything from local health insurance to voting rights are impacted by the loss or acquisition of household residency. While she’s still in Shanghai today, she remains hopeful for the opportunity to return home to Taiwan later this year. Although the strict COVID policies have soured her attitudes toward working and living in mainland China, her views on the citizens of Shanghai and Cross-Strait relations remain positive. Ding Liren’s story Ding Liren (Ding is his family name; this is the standard naming convention in China) is China’s top-rated chess player. He’s currently world number 2 behind Magnus Carlsen of Norway3. A bit about competitive chess before I continue. The World Chess Championship is almost universally recognized as the world’s premier chess tournament. It is a head-to-head match between the reigning world champion and a challenger. In modern times, the challenger has been determined via a biennial 8-player tournament called the Candidates Tournament. Ding first participated in 2018’s tournament, placing 4th of 8. It was a decent showing, but after an unbeaten streak of 100 games ending in late 2018 and a win in the 2019 Sinquefield Cup (where he beat top-rated Magnus Carlsen in playoffs), he was widely considered to be one of the favorites in the 2020 Candidates Tournament (along with Fabiano Caruana, the winner of the 2018 Candidates Tournament). Early 2020 is where Ding’s story take a turn for the worse. The 2020 Candidates Tournament was scheduled to take place mid-March in Yekaterinburg, Russia. Upon entry, the Russian government decided to put Ding into quarantine in a rural cottage near Moscow due to the COVID pandemic. This quarantine took an incredible mental toll on Ding, putting him in a tie for last place after 7 of 14 rounds. After the 7th round, FIDE, chess’s governing body, decided to suspend play to mitigate the spread of COVID. When play resumed mid-April 2021, Ding (who did not have to quarantine this time around) looked to be back in top form, winning his final three games of the tournament, one of which was over the eventual challenger, Ian Nepomniachtchi. In a game where draws are incredibly common at the highest level of play, three wins in a row can be considered a major accomplishment in and of itself. The story doesn’t quite end there. With Ian bombing out of the 2022 World Chess Championship match with Magnus, Ding is once again widely considered to be one of the favorites to win the 2022 Candidates Tournament… if he could actually qualify for it. The top two finishers of the 2021 Chess World Cup, 2021 Grand Swiss Tournament, and 2022 Grand Prix are given berths into the FIDE Candidates Tournament4. Although Ding was invited to and had planned on participating in all three of the aforementioned tournaments, he ended up being unable to attend any of them due to a combination of China’s zero-COVID stance and the Schengen area visa policy; he’s repeatedly been unable to purchase a return flight from Europe to China due to China’s constant updating of return flight rules and the complete lack of available flight options. For reference, a one-way flight from San Francisco to Shanghai on 05/13 of this year costs $9628 (transiting through a third country is disallowed if direct flights exist). I was able to secure a one-way flight from San Francisco to Shanghai for $267.20 pre-pandemic. In a major twist of events, it seems that Ding may yet qualify due to Sergey Karjakin’s chess ban5. If Ding does end up playing in the 2022 Candidates Tournament, I’ll certainly be rooting for him - I hope you will too. Ding Liren so obviously belongs in the candidates tournament. That he does not even get a chance to qualify, is saddening. — Peter Heine Nielsen (@PHChess) February 1, 2022 My own story The word “lockdown” is generally understood to be a break in transportation and other non-essential public services; this is not the case in China. The last story that I’d like to share is a personal one detailing the time I had the great displeasure of participating in a 48-hour COVID-induced building-wide lockdown in Shanghai. On the evening of December 13th of 2021, the Anlian building in Shanghai’s Yangpu district went under a full-fledged 48-hour lockdown. Although I had left before police and health officials came to lock the building down, Anlian’s building management was still able to contact and inform me of the mandatory 48-hour quarantine (I was obviously not enthralled by this). Right before I re-entered the building, I took the picture below. One of the police officers noticed me snapping photos and was about to confiscate my phone before I told him that I had already deleted them (I lied). I didn’t end up taking any more pictures of the lockdown due to this strict “no photographs” policy. Shanghai's Anlian building on the first night of lockdown - notice the barricade at the entrance to the left of the blue tent. There's police everywhere, and local health workers arrived in full personal protective equipment (PPE) to administer nucleic acid amplification tests (NAATs). The first night was the most eventful. Occupants ordered takeout (外卖) for dinner, resulting in mass confusion as bags of food were left outside the building entrance with nobody to bring them in. There was also mandatory COVID testing for the entire building and strict mask requirements while lining up for the test; those who weren’t wearing them tightly over both the nose and mouth were forcibly pulled aside and given stern warnings. Later at night, internet speeds slowed considerably as everybody began streaming television shows, downloading Steam games (CS:GO, anyone?), watching Netflix (through a VPN), etc. Long lines formed at bathrooms as well. In particular, the women’s bathroom became congested as many vied for mirror space to apply dry shampoo and/or remove makeup. Local health workers brought and distributed blankets, but only enough for about 1/5th of the people in the building - tough luck for everybody else. Day 2 was much of the same, with most folks fairly tired and sleep-deprived from the night before. Another round of NAATs took place on the first floor during a very specific time window. I was unfortunately late, which resulted in a heated argument between building management (who was supposed to make sure everyone in the building was present for the second round of COVID tests) and local health workers (who had to once again put on PPE and re-open test kits). This happened even though it was fairly clear at that point that nobody in the building had contracted COVID. I later found out that the 48-hour lockdown wasn’t due to secondary contact (次秘接) as opposed to primary contact: an international traveller from Japan who was in contact with a confirmed COVID case had passed through the 25th floor of the building earlier in the day. I was skeptical that health officials would go through , but I later confirmed it with both a local health official as well as one of the folks most heavily affected who worked on the 25th floor of the office building. In any case, if there’s one thing I learned from this whole ordeal, it’s that sleeping in office chairs is extremely uncomfortable. On China’s COVID statistics These stories should help shed some light the three distinct phases that China’s zero-COVID policy has gone through. The first phase takes place from December 2019 to April 2020. During these critical months, China set a precedent for the rest of the world by engaging in mass lockdowns, city-wide testing, and virtual meetings. Official statistics (deaths, cases, recoveries) during this time are highly inaccurate due mostly to intentional but also some inadvertent miscounts. From May 2020 onward, China entered a delicate equilibrium, maintaining its zero-COVID policy through strict 21-day quarantine for international travelers - 14 in a hotel plus 7 at home. Chinese policy became fairly standard throughout the country, and most citizens simply forgot about COVID altogether, save for the occasional article or two bashing America for an unnecessarily high death count. Since January 2022, driven by Omicron’s high transmissibility, China has been grappling with outbreak after outbreak and re-engaging in citywide lockdowns. Through a fundamental misunderstanding of the first two phases, China writers such as George Calhoun criticize Beijing for underreporting the infection rate. He views China’s COVID statistics as a “statistical, medical, biological, political and economic impossibility” because he’s never lived in a dense, authoritarian country. Writers like George deserve substantial criticism for cherry-picking statistics while simultaneously avoiding a wholistic approach to analyzing China’s COVID response. China’s COVID eradication program in phases one and two were successful because the central government’s containment policies were unimaginably draconian. The 48-hour lockdown story should serve as a great example of this - a city or state leader in America forcing an entire building into a military lockdown would be political suicide. As mentioned above, I have no doubt that the COVID cases and deaths for phase one are significantly higher than initially reported. Phase two, however, is entirely different. With COVID’s strong transmissibility and incredibly dense urban centers, entire swaths of the population would be simultaneously unable to work if even a few COVID cases slipped through without quarantine. Simply put, hospitals would be overrun, and the Chinese populace would notice. Halloween (2020) in a tier 2 Chinese city. Quite the super-spreader event, no? My personal opinion The purpose of the three above stories was to portray how lockdowns, quarantine, and general COVID policy in China differs from that of other countries. This should hopefully also show why China’s zero-COVID strategy was considerably more successful than that of other countries in addition to why zero-COVID is socially and economically unsustainable in the era of Omicron. Unless China cuts its citizens off completely from the rest of the world, I don’t see zero-COVID as a long-term possibility for any country, let alone one with an economy and population as large as China’s. China’s zero-COVID policy was warranted when the disease was much deadlier, but with Omicron accounting for nearly 100% of all recent worldwide COVID cases, it is highly impractical for China to continue these unsustainable zero-COVID rules, as they will have increasingly negative social and economic side effects. In particular, China’s zero-COVID policy has put the population in a COVID-ignorant state of mind - more and more people are showing an unwillingness to comply with local COVID mandates, all while the percentage of fully vaccinated elderly Chinese citizens remains low. Thankfully, there are rumors that China wants to ease its zero-COVID policy. However, given the speed with which the central government was able to lockdown cities and restrict the flow of people in early 2020, I see no excuse for the current unease and slowness with which opening up is being discussed. Western media coverage One final note on Western media and its coverage of China’s pandemic response. The majority of media outlets have repeatedly failed to read between the lines when it comes to CPC pandemic policy6. While part of the reason is to prevent the spread of COVID domestically, another major reason is talent retention. China is undergoing a fairly seismic demographic shift, with a rapidly shrinking young population (ages 25-34). I personally know several young Chinese professionals who studied at an international university before deciding to return to China instead of staying abroad - nearly all of these instances were due to rising costs associated with traveling in and out of mainland China, both in terms of time and money. Alex’s and Ding’s stories are perfect reflections of this. It’s time for Western media to treat China’s policies as socioeconomic manipulation at the expense of other countries (including America) rather than natural byproducts of an authoritarian government. Western governments should band together and respond in kind with their own talent retention policies, and, if necessary, embargoes/sanctions against China. Wrapping up Thanks for making it this far - I hope this post was informative. As mentioned before, this is part II of a four-part series. In part III, I’ll cover the Chinese tech scene, from 996’ing to the open source community. Stay tuned! Example: where’s the line for white, non-Latina women in this article? ↩ 有钱没钱回家过年, i.e. returning home for LNY is a must, regardless of one’s fiscal condition. ↩ Ding and Levon Aronian are my two favorite players. In particular, I enjoy watching Ding’s solid playstyle in conjunction with his cold, hard calculation capabilities. He’s also an incredibly humble person.</sup> ↩ Traditionally, there has also been a slot for the highest-rated player, but this was removed in the 2022 cycle due to rating protection/manipulation by previous Candidates Tournament participants (Ding would’ve otherwise qualified this year). ↩ Sergey had qualified via the Chess World Cup held in 2021, but due to his support of the Russian invasion of Ukraine, he received a 6-month ban from all FIDE tournaments. This reinforces my belief that the only true winners of Russia’s invasion of Ukraine are China and India. ↩ China’s great firewall is another example of Western media missing the complete picture. While minimizing external influence and internal dissent is undoubtedly a major reason for building the firewall, an equally important reason was to promote the growth of China’s own tech giants - Alibaba, Tencent, Baidu, etc. I’ve actually read articles and papers which argue that the latter reason is the primary one for the great firewall; given the prevalence of VPNs and proxies (翻墙软件) within mainland China, I must say that I agree. ↩