# MIT Researchers Open-Sourced ‘MADDNESS’: An AI Algorithm That Speeds Up Machine Learning Using Approximate Matrix Multiplication (AMM)

Matrix multiplication is one of the essential operations in machine learning (ML). However, these operations are extensively computationally costly due to the extensive use of multiply-add instructions. Therefore, many studies have focused on estimating matrix multiplies effectively.

GPU and TPU chips perform matrix multiplication faster than CPUs because they can execute many multiply-adds in parallel. This makes them particularly attractive for ML applications. However, they may be too expensive or unavailable for researchers on a tight budget or in resource-constrained applications like IoT. To this end, numerous studies have looked at AMM algorithms, which trade-off matrix multiplication precision for speed.

Earlier this year, researchers from MIT’s Computer Science & Artificial Intelligence Lab (CSAIL) has introduced Multiply-ADDitioN-lESS (MADDNESS). This algorithm does not require multiply-add operations and speeds up ML by employing approximate matrix multiplication (AMM). MADDNESS runs 10x quicker than other approximation algorithms and 100x faster than accurate multiplication. This algorithm is now made open-sourced.

Most AMM algorithms use multiply-add operations. MADDNESS, on the other hand, employs a collection of highly efficient learning hash functions to attain coding rates of 100GB/second with just one CPU thread. The hash functions convert input data into an index into a lookup database with pre-calculated dot-products. Although the approach introduces some output error, the authors show that the error has a theoretical upper bound that can be paid off against speed.

The MADDNESS algorithm makes various assumptions common in ML applications about the matrices that are multiplied, including that they are “large, somewhat dense, and resident in a single computer’s memory.” One matrix, for instance, has fixed values; this may be the weights in an image classification model. The other matrix represents the input data, which may be the image pixels to be classified.

MADDNESS is based on the product quantization (PQ) algorithm, which is a vector quantization approach. PQ analyses a vast number of input vectors to generate a limited number of prototype vectors. Each prototype vector’s products with the fixed weight vector are computed in advance. Then, using a hash function, any new input vector is mapped to its most comparable prototype. This provides an index to the pre-computed product.
{"ft_lang_label":"__label__en","ft_lang_prob":0.9168302,"math_prob":0.89528096,"size":4260,"snap":"2023-40-2023-50","text_gpt3_token_len":828,"char_repetition_ratio":0.122415416,"word_repetition_ratio":0.0,"special_character_ratio":0.1814554,"punctuation_ratio":0.10288066,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9888787,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-10-03T21:03:19Z\",\"WARC-Record-ID\":\"<urn:uuid:a974166c-9b82-4e63-afd5-9cb24acb9120>\",\"Content-Length\":\"374238\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:68bdf34a-b7e1-444d-8338-db0517b78aad>\",\"WARC-Concurrent-To\":\"<urn:uuid:c199740e-eb20-468c-9865-d4a7dc243db4>\",\"WARC-IP-Address\":\"35.215.82.39\",\"WARC-Target-URI\":\"https://www.marktechpost.com/2021/10/07/mit-researchers-open-sourced-maddness-an-ai-algorithm-that-speeds-up-machine-learning-using-approximate-matrix-multiplication-amm/\",\"WARC-Payload-Digest\":\"sha1:2DJYN5VBAB4TFMG5TL5CQU52GCSFQLGG\",\"WARC-Block-Digest\":\"sha1:TE6M7MGUEN5BCNH3PIHVNGYZGMK6UZY2\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-40/CC-MAIN-2023-40_segments_1695233511220.71_warc_CC-MAIN-20231003192425-20231003222425-00586.warc.gz\"}"}