At Data Engineering Summit (DES) 2023, presenting a talk about Unleashing the Power of Probabilistic Data Structures: Optimizing Storage and Performance for Big Data, Sudarshan Pakrashi, Director of Data Engineering at Zeotap spoke about statistical algorithms designed to optimise use of memory in storing and querying large datasets. In one of the questions asked, he spoke about if data sketching can be used in current generative AI models such as LLMs.

To this, Pakrashi responded that it is possible to do so and is actually a “great analogy”. He explained how in every language model there are word associations that need to be maintained when there is a huge dataset of words. “Imagine the permutations and combinations that you want to have and sketches are in fact used to maintain those because then your model is actually going to query the frequencies for those combinations,” he explained. 

Data sketching is a method of summarising large datasets using compact data structures that can provide approximate answers to queries about the data. In the context of LLMs, data sketching can be used to summarise the text corpus used to train the model, which can help reduce the memory requirements of the model and improve its training efficiency.

Why Do We Need Data Sketching in LLMs

“Do you ever feel overwhelmed by a constant stream of information?” – reads the first line of the paper – ‘What is Data Sketching, and Why Should I Care’ by Graham Cormode in 2017. When you start filtering out information based on what is required, that is exactly similar to what data sketching essentially is. And this can greatly benefit the training of LLMs. 

Data sketching can help improve the efficiency and scalability of generative models in the following ways:

• Data compression: Summarising large datasets using sketching techniques, LLMs can be trained on representations that are smaller than the original one, reducing the memory requirements and computational resources needed for deploying and training. This can be especially helpful when dealing with limited resources or large-scale datasets.

• Faster training: Speed up the training process for LLMs by reducing the amount of data they need to process. Data sketching, by essentially reducing the size of the data, can lead to faster convergence and shorter training times without significantly compromising the quality of the generated samples.

• Real-time data: Sketching can enable LLMs to process and learn from data streams efficiently, and automatically update their internal representations on-the-fly by generating new samples based on the most recent data.

• Anomaly detection: For identifying outliers or anomalies in the training data, sketching and sampling techniques can be used to improve the quality of LLMs outputs. By identifying and potentially removing anomalous data points, LLMs can focus on learning the underlying structure and patterns in the data, leading to better generated samples.

• Data exploration: For exploring large datasets to gain insights into their structure and characteristics, sketching can provide insights that can be used to guide the design and configuration of LLMs, such as selecting appropriate architectures, hyperparameters, or loss functions.

Data Sketching Techniques in LLMs

Although data sketching has been used previously in natural language processing (NLP) tasks, the recent rise of LLMs like GPT-3, that require huge compute, data sketching can, and in fact have, increased the efficient training and deployment of AI models. 

One commonly used data sketching technique in LLMs is the Bloom filter, which is a probabilistic data structure that can efficiently test whether an item is in a set. Bloom filters can be used to represent the vocabulary of the text corpus used to train the model, allowing the model to store the vocabulary in a much smaller memory footprint. 

Another technique used in LLMs for data sketching is Count-min sketches. This is another type of probabilistic data structure that can efficiently estimate the frequency of items in a set. Count-min sketches can be used to estimate the frequency of words in the text corpus, which can be used to optimise the training of the model.

Similar techniques include HyperLogLog, which is another probabilistic algorithm used to estimate the number of distinct elements in a large dataset. 

Moreover, Quantiles sketches is another technique that provides approximate answers to queries about percentiles, medians, or other order statistics of a dataset. This is similar to Sampling, which means selecting a subset of data for representing the entire dataset.