\section*{Details of The Latency Overhead Evaluation} \label{appendix:latency-details}

First, we set up an Elasticsearch cluster using AWS Elasticsearch service\footnote{https://aws.amazon.com/elasticsearch-service/}. 
This service is used by multiple companies and can be consider as reproducing ``real'' production environment. 
We used default settings for the cluster and set node type to m5.xlarge. 

We then created an Elasticsearch index and populated it with documents. 
To study the effect of fetching latency, we duplicate each document multiple times, each with a different blob (aka payload) size. 
Specifically, we repeatedly select a random sample of 10 words, and denote these as a document. 
For each such document, we consider 8 replications, where for each replica we add a blob field with a string of length X, 
and added a unique size word ``SIZE-X'' to the document, where X is selected from the possible sizes \{2, 512, 1K, 2K, 4K, 8k, 16K, 32K\}. 

Once the index was populated, we run some warm-up queries against the index, to ensure the index is in a steady state. 

During experimentation, we repeatedly query (and fetch) documents with blob size of X and measure how retrieval time changes with X.
Each query is composed of a \texttt{should clause}\footnote{https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-bool-query.html} with 3 randomly selected words, and a \texttt{must clause} with the word ``SIZE-X'', which ensures that only documents with blob size X are returned.
The number of documents to retrieve is limited to 1000 (as the default configuration of MSMARCO passage ranking task) or 200. 
All queries are executed by a single thread to avoid concurrency interference and queuing effects, on an AWS EC2 machine in the same datacenter as the Elasticsearch cluster. 
Each experiment issues 100 queries and is repeated 30 times, while interleaving different X values to avoid potential biases. 
We report the average time in milliseconds (ms) and standard deviation in Table~\ref{table:elasticsearch-latency}. \alex{why table and not a chart?}

\end{document}

\section{Succinct Document Representation (SDR)}\label{sec:algorithm}
Our work is based on the late-interaction architecture \cite{macavaney2020efficient,gao2020modularized,chen2020dipair,cao2020deformer,nie2020dc}, which separates BERT into $L$ independent layers for the documents and the queries, and $T-L$ interleaving layers, where $T$ is the total number of layers in the original model, e.g., 12 for BERT-Base. Naively storing all documents embeddings consumes a huge amount of storage with a total of  $m\cdot h \cdot 4$ bytes per document, where $m$ is the average number of tokens per document and $h$ is the model hidden size (384 for the distilled version we use). For MSMARCO, with 8.8M documents and $m\!=\!76.9$, it leads to a high storage cost of over a terabyte, which is not affordable except in large production systems.

Our compression scheme for the document representations consists of two sequential steps, (i) dimensionality reduction and (ii) block-wise quantization, described in \S~\ref{subsec:autoencoder} and \S~\ref{subsec:quantization-algorithm} respectively. \ignore{In \S~\ref{subsec:overall-algo} we describe the overall system and parameter choices.} 


\subsection{Dimensionality Reduction using an AutoEncoder with Side Information (AESI)}\label{subsec:autoencoder}

To compress document representations, we reduce the dimensionality of token representations (i.e., the output of BERT's $L$-th layer) using an autoencoder. 
Standard autoencoder architectures typically consist of a neural network split into an encoder and a decoder: the encoder projects the input vector into a lower-dimension vector, which is then reconstructed back using the decoder. 

\ignore{
\amit{the following paragraph seems to not add much new information, wrapping in \textbackslash WIP for now}
There is an inherent trade-off between compression rate and the quality of the reconstructed vectors. Hence, we formalize two desiderata that our compression algorithm needs to fulfill: \amit{seems a bit redundant to say both desiderata and 'needs to fulfill'}
\begin{enumerate}[leftmargin=*]
\item High document representation compression rate that significantly reduces storage and latency costs.
\item High reconstruction fidelity of compressed representation without harming the utility in downstream tasks.
\end{enumerate}
}



Our architecture, AESI, extends the standard autoencoder by using the document's text as \emph{side information} to both the encoder and decoder. Such an approach is possible since, no matter how the document scores are computed, re-ranking systems have access to the document's text in order to render it back to the user. In the rest of this section, we add the precise details of the AESI architecture.

\ignore{
\amit{the following paragraph seems to not add much new information, wrapping in \textbackslash WIP for now}
The document's textual content can be utilized in two main ways: (i) precompute representations and cache them, thus, inducing significant storage costs, and (ii) compute the representations from raw text by running it through all $L$ transformer layers, thus, inducing high latency costs. Our approach, \mbox{AESI}\xspace{}, finds a middle ground between \emph{caching} an little amount of pre-computed document information, and performing a lightweight \emph{online computation}.
}


\paragraph{\textbf{Side Information.}} In line with our observation that we have access to the document's raw text, we propose utilizing the \emph{token embedding} information, which is computed by the embedding layer used in BERT's architecture. The token embeddings encode rich semantic information about the token itself; however, they do not fully capture the context in which they occur; hence, we refer to them as \emph{static embeddings}. For example, through token embeddings, we cannot disambiguate between the different meanings of the token \texttt{bank}, which can refer to either a geographical location (e.g., ``river bank'') or a financial institution, depending on the context.



Static embeddings are key for upper BERT layers, which learn the contextual representation of tokens via the self-attention mechanism
We use the static embeddings as side information to both the encoder and decoder parts of the autoencoder. This allows the model to focus on encoding the \emph{distilled context}, and less on the token information since it is already provided to the decoder directly. Encoding only the context is an easier task, allowing AESI to achieve higher compression rates, and at the same time, retaining the quality of the contextual representation.
\ignore{\amit{remove this for now since I've hidden all the 'desiderata' part:}
Thus, fulfilling our two desiderata for our approach.
}




\paragraph{\textbf{AESI Approach.}} For a token whose representation we wish to compress, our approach proceeds as follows. We take the $L$-th layer's output contextual representation of the token together with its static embedding and feed both inputs to the autoencoder. The information to be compressed (and reconstructed) is the contextual embedding, and the side-information, which aids in the compression task, is the static embedding. The decoder takes the encoder output, along with the static embedding, and attempts to reconstruct the contextual embedding. Figure~\ref{fig:autoencoder-arch-with-uncontext} shows the AESI architecture.


With the AESI approach, there are several parameters that we determine empirically. First, the $L$-th transformer layer of the contextual representation that is provided as input, which has a direct impact on latency\footnote{A ranker model has to compute layers $L+1$ onward online.}. Second, the size of the encoder's output directly impacts the compression rate and thus storage costs.

Encoding starts by concatenating
the input vector (i.e., the output of layer $L$, the vector we compress) and the static token embedding (i.e., the output of BERT's embedding layer), and then passes the concatenated vector through an encoder network, which outputs a $c$-dimensional {\em encoded vector}. 
Decoding starts by concatenating the encoded vector with the static token embedding, then passes the concatenated vector through a decoder layer, which reconstructs the input vector.
Specifically, we use a two-layer dense network for both the encoder and the decoder, which can be written using the following formula:
\begin{align}
e=E(v, u) := W^e_2\cdot\bigl(\operatorname{gelu}\bigl(W^e_1(v;u)\bigr)\bigr) 
\\
v'=D(e, u) := W^d_2\cdot\bigl(\operatorname{gelu}\bigl(W^d_1(e;u)\bigr)\bigr)
\end{align}
where $v\in\mathbb{R}^h$ is the contextualized token embedding (the output of the $L$-th layer), $u\in\mathbb{R}^h$ is the static token embedding (the output of the embedding layer, which is the input to BERT's layer $0$ and includes token position embeddings and type embeddings), and $u;v$ means concatenation of these vectors. \mbox{$W^e_1\in\mathbb{R}^{i\times 2h}$}, \mbox{$W^e_2\in\mathbb{R}^{c\times i}$}, \mbox{$W^d_1\in\mathbb{R}^{i\times (c+h)}$}, \mbox{$W^d_2 \in\mathbb{R}^{h\times i}$} are trainable parameters. 
$h$ is the dimension of token embeddings (e.g., 384), $i$ is the intermediate autoencoder size, and $c$ is the dimension of the projected (encoded) vector. $\operatorname{gelu}(\cdot)$ is an non-linear activation function \cite{hendrycks2016gaussian}. Additional autoencoder variations are explored in \S~\ref{subsec:auto-encoder-mrr}. 

\begin{figure}
    \centering
    \includegraphics[width=.8\columnwidth]{SuccinctDocRepr/figures/aesi.pdf}
    \caption{AutoEncoder with Side Information\xspace{} (\mbox{AESI}\xspace) architecture. For our usage, the input is the contextual token embedding (the \mbox{$L$-th} layer's output), and the side information is the static token embedding (the output of BERT's initial embedding layer). The resulting $c$--dimensional encoded vector can be thought of as the distilled context of the input token.
   
    }
    \label{fig:autoencoder-arch-with-uncontext}
\end{figure}

\subsection{Quantization}\label{subsec:quantization-algorithm}

Storing the compressed contextual representations in a naive way consumes 32 bits (float32) per coordinate per token, which is still costly. To further reduce storage overhead, we propose to apply a quantization technique, which uses a predetermined $B$ bits per coordinate. We rely on a recently proposed quantization approach, DRIVE~\cite{vargaftik2021drive}, which we describe next and summarize in Algorithm~\ref{code:ourQ}. Later in this subsection, we show how we apply DRIVE to our AESI-encoded documents.




Before going into the details of the quantization method, we first require the following definitions:

\begin{definition}[\cite{horadam2012hadamard}]
 A normalized Walsh-Hadamard matrix,\\ \mbox{$H_{2^k} \in \{+1,-1\}^{2^k\times2^k}$}, is recursively defined as
\begin{gather*}
H_1 = 1;\ \ H_{2^k} = \frac{1}{\sqrt{2}}\begin{pmatrix}
H_{2^{k-1}} & H_{2^{k-1}} \\
H_{2^{k-1}} & -H_{2^{k-1}}
\end{pmatrix} .
\end{gather*}
\end{definition}

\begin{definition}[\cite{10.1145/1132516.1132597}]
A randomized Hadamard transform, $\mathcal{H}$, of a vector, $x \in \mathbb{R}^{2^k}$, is defined as $\mathcal{H}(x) \coloneqq H_{2^k}Dx$, where $H_{2^k}$ is a normazlized Walsh-Hadmard matrix, and $D$ is a diagonal matrix whose diagonal entries are i.i.d. Rademacher random variables (i.e., taken uniformly from $\{+1,-1\}$). While $\mathcal{H}$ is randomized and thus defines a distribution, when $D$ is known, we abuse the notation and define the inverse Hadamard transform as \mbox{$\mathcal{H}^{-1}(x) \coloneqq (H_{2^k}D)^{-1}x = DH_{2^k}x$}.

\end{definition}

The quantization operates as follows.
Given a vector, denoted $x\in \mathbb{R}^d$, we first \emph{precondition} it using a randomized Hadamard transform, $\mathcal{H}$, and normalize by multiplying by $\nicefrac{\sqrt{d}}{\norm{x}_2}$. There are several desired outcomes of this transform\footnote{We also note that the transform has the advantage of having a vectorized, in-place, $O(d\log d)$-time implementation~\cite{fino1976unified}.}. First, the dynamic range of the values is reduced (measured, for instance, by the ratio of the $\ell_\infty$ and the $\ell_2$ norms). Loosely speaking, we can think of the transform as spreading the vector's information evenly among its coordinates. Second, regardless of the distribution of the input vector, each coordinate of the transformed vector will have a distribution that is close to the standard Gaussian distribution (as an outcome of the central limit theorem).
After the transform, we perform scalar quantization that is optimized for the $\mathcal{N}(0,1)$ distribution, using $K$-means (also known as Max-Lloyd in the quantization literature \cite{gershogray92}), with $K=2^B$. 
The vector $X$ of cluster assignments together with the original vector's $\ell_2$ norm can now be stored as the compressed representation of the original vector.



To retrieve an estimate of the original vector, we perform the same steps in reverse. We replace the vector of cluster assignments $X$ with a vector $\hat y$ containing each assigned cluster's centroid, denormalize, and then apply the inverse randomized Hadamard transform, $\mathcal{H}^{-1}$. To avoid encoding $D$ directly, we recreate it using  \emph{shared randomness} \cite{newman1991private} (e.g., a shared pseudorandom number generator seeded from a hash of the vector's text).
Different variations of the quantization scheme are discussed in \S~\ref{subsec:quantization-evaluation}. 

\paragraph{\textbf{Block-wise Quantization.}} The AESI encoder reduces the dimension of the contextual embeddings from hundreds (e.g., 384) to a much smaller number (e.g., 12). On the other hand, the randomized Hadamard transform's preconditioning effect works best in higher dimensions \cite{10.1145/1132516.1132597}. In order to resolve this conflict, we first concatenate the reduced-dimension vectors of all the tokens from a single document. We then apply the Hadamard transform with a larger block size (e.g., 128) on the concatenated vector, block-by-block (padding the last block with zeros when necessary). When evaluating the compression efficiency, we consider the overhead incurred from (a) the need to store the vectors' $\ell_2$ norms and (b) the padding of the final Hadamard block in a concatenated vector. Balancing these factors should be done per use case.

\ignore{
\subsection{Overall architecture}\label{subsec:overall-algo}
The SDR scheme is designed to compress document representations, which consist of BERT contextual embedding vector per token per document. 
In the first step, \mbox{AESI}\xspace{} is applied for each token separately, reducing the dimension of the contextual embeddings from hundreds (e.g., 768 for BERT-Base) to a much smaller number (e.g., 12).
In the next step, we apply block-wise quantization on these vectors.
However, there is a mismatch between these two steps; the Hadamard transform (which is part of the quantization step) works best on high-dimensional vectors \nachshon{can we cite this?} and require vectors to be a power of 2, while the output of the \mbox{AESI}\xspace{} are low-dimensional vectors that are not necessarily power-of-2 size. 
We solve this mismatch by concatenating the \mbox{AESI}\xspace{} vectors for all tokens in the document, then splitting it into blocks that are high-dimensional and power of 2, padding the last block with zeros when necessary. 
Quantization is then applied per block. 
The choice of block size represents a tradeoff between two factors: (1) padding overhead - larger block size lead to higher padding overhead and (2) normalization overhead, consisting of a single normalization value per block - which reduces when block size is large and there are fewer blocks. 
Balancing these factors should be done per use-case. 

In the next section, we evaluate the SDR using the MSMARCO dataset and provide insights on the information that is captured by \mbox{AESI}\xspace-encoded tokens.


\alex{I'm missing a figure that shows overall arch flow \nachshon{Would be good to add depending on time constraint}} 
}


































\begin{algorithm}[t]
\caption{~$B$-bits Vector Quantization (DRIVE) \cite{vargaftik2021drive}}
\begin{flushleft}
$\mathcal H$ - A randomized Hadamard transform \\
$\text{\LARGE $\mathfrak{c}$}$ - $K$-Means centroids over the normal distribution, where $K=2^B$
\end{flushleft}
\begin{algorithmic}[1]
\vspace{1mm}
  \Statex \hspace*{-4mm}\textbf{Quantize($x \in \mathbb{R}^d$):}
  \vspace{0.5mm}
 
  \Statex $y:= \frac{\sqrt{d}}{\norm{x}_2}\mathcal H(x)$
 
  \Statex Compute $X_i = \argmin_k \left| y_i  -  \text{\LARGE $\mathfrak{c}$}_k\right|$: \mbox{$X\in \{0,\dots,2^B-1\}^d$}

   \Statex \Return $X$, $\norm{x}_2$
\end{algorithmic}
\vspace{2mm}
\begin{algorithmic}[1]
  \Statex \hspace*{-4mm}\textbf{Dequantize($X$, $\norm{x}_2$):}
  \vspace{0.5mm}
  \Statex Compute $\hat y_i =   \text{\LARGE $\mathfrak{c}$}_{X_i}$: \mbox{$\hat y \in \{\text{\LARGE $\mathfrak{c}$}_0,\dots,\text{\LARGE $\mathfrak{c}$}_{2^B-1}\}^d$}
   \Statex \Return $ \hat x = \mathcal H^{-1}\left(\frac{\norm{x}_2}{\sqrt{d}} \hat y\right)$
\end{algorithmic}
\label{code:ourQ}
\end{algorithm}

















\section{Appendix: Latency Overhead of Fetching Large Vectors}\label{subsec:analysis-elasticsearch}

\begin{table}[]
    \begin{tabular}{lrr}
        \toprule
       
        payload size & 200 documents & 1000 documents \\
        \hline \hline 
2                                                            & 6.4$\pm$0.8             & 21.9$\pm$1.5             \\
512                                                          & 7.0$\pm$1.1               & 24.9$\pm$0.5             \\
1K                                                           & 7.7$\pm$0.6             & 30.6$\pm$0.5             \\
2K                                                           & 9.7$\pm$0.5             & 42.9$\pm$6.6             \\
4K                                                           & 13.2$\pm$0.6            & 55.1$\pm$1.4             \\
8K                                                           & 21.6$\pm$0.7            & 99.7$\pm$2.8             \\
16K                                                          & 38.4$\pm$1.1            & 191.0$\pm$5.2              \\
32K                                                          & 76.9$\pm$1.9            & 391.8$\pm$11.                   \\
        \bottomrule
    \end{tabular}

\caption{Elasticsearch retrieval latency (in milliseconds, $\pm$ denotes standard deviation) as a function of payload size and number of fetched documents.}
\label{table:elasticsearch-latency}
\end{table}

Existing work, such as PreTTR \cite{macavaney2020efficient}, argue for (some) compression to reduce storage cost. 
In this appendix, we argue that compression should also be done to reduce the fetching latency of document representation, which, without sufficient compression, can offset any benefits from reducing computation costs. 

Standard ad-hoc retrieval is composed of a retrieval service, such as Elasticsearch\footnote{elasticsearch.com}, which stores the entire corpus, and given an online user, request returns a set of $K$ documents, where $K$ is typically between 100 and 1000. 
Normally, the retrieval service is the only location where the entire corpus is stored, so it is a natural location for storing pre-computed document embeddings. 
Therefore, it is important to understand how retrieval latency changes when the size of pre-computed embeddings varies. 

Towards answering this question, we measured how Elasticsearch retrieval latency varies with different payload sizes.  
The full evaluation setup is deferred to the supplementary material for lack of space.
The results appear in Table~\ref{table:elasticsearch-latency}.
We note that 1KB roughly corresponds to \mbox{AESI}\xspace{}-16-6b, while 512 bytes roughly corresponds to \mbox{AESI}\xspace{}-8-6b. 
At this range, the latency increase is minimal. However, the payload size for the baseline system is at least 4x larger, leading to a notable latency increase. 
The original PreTTR work \cite{macavaney2020efficient} considered up to 12x size reduction, leading to 32K document embedding size. 
As can be seen in the table, this results in a prohibitively large latency overhead. 

\ignore{
----------------
\amit{add introduction to elastic search use case}

Existing work, such as PreTTR \cite{macavaney2020efficient}, argue for (some) compression to reduce storage cost. 
In this subsection, we argue that compression should also be done to reduce the fetching latency of document representation, which, without sufficient compression, can offset any benefits from reducing computation costs. 

A standard ad-hoc retrieval flow is composed of two steps, retrieval and ranking. In the retrieval step, the user's query is send to a retrieval service, such as Elasticsearch\footnote{elasticsearch.com}, which returns a set of $K$ documents, where $K$ is typically between 100 and 1000, depending on the scenario and latency budget. 
Then, the $K$ documents are ranked by an ML model.

Late-interaction architectures reduce ranking latency by precomputing document embeddings offline. 
If document embeddings for the entire corpus do not fit into memory (of the machine hosting the ranker), it is necessary to fetch them for the $K$ documents that are fed into the ranker. 
A typical solution to this is to store the document embeddings in the retrieval system, e.g., Elasticsearch, and fetch them together with the 
retrieved documents. 
However, the size of fetched document affects retrieval latency, which was largely ignored in previous work. 

To understand this effect, we perform the following experiment. 
First, we set up an Elasticsearch cluster using AWS Elasticsearch service\footnote{https://aws.amazon.com/elasticsearch-service/}. 
This service is used by multiple companies and can be consider as reproducing ``real'' production environment. 
We used default settings for the cluster and set node type to m5.xlarge. 

We then created an Elasticsearch index and populated it with documents. 
To study the effect of fetching latency, we duplicate each document multiple times, each with a different blob (aka payload) size. 
Specifically, we repeatedly select a random sample of 10 words, and denote these as a document. 
\amit{you meant that each X is determines a replica? if so the following needs rephrasing I think:}
For each such document, we consider 8 replications, where for each replica we add a blob field with a string of length X, 
and added a unique size word ``SIZE-X'' to the document, where X is selected from the possible sizes \{2, 512, 1K, 2K, 4K, 8k, 16K, 32K\}. 
Once the index was populated, we run some warm-up queries against the index, to ensure the index is in a steady state. 

During experimentation, we repeatedly query (and fetch) documents with blob size of X and measure how retrieval time changes with X.
Each query is composed of a \texttt{should clause}\footnote{https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-bool-query.html} with 3 randomly selected words, and a \texttt{must clause} with the word ``SIZE-X'', which ensures that only documents with blob size X are returned.
The number of documents to retrieve is limited to 1000 (as the default configuration of MSMARCO passage ranking task) or 200. 
\amit{the following sentence is a little unclear:}
All queries are executed by a single thread to avoid concurrency interference and queuing effects, on an AWS EC2 machine in the same datacenter as the Elasticsearch cluster. 
Each experiment issues 100 queries and is repeated 30 times, while interleaving different X values to avoid potential biases. 
We report the average time in milliseconds (ms) and standard deviation in Table~\ref{table:elasticsearch-latency}. \alex{why table and not a chart?}


As can be seen from the table, when the number of retrieved documents is 200, payload size of 512 increases latency by just 0.6ms, which falls within the standard deviation. 
This corresponds, for example, to the AESI-8-6b, with an MRR@10 drop of 0.007. 
When the payload size is 1KB, latency increase is 1.3ms; this corresponds, e.g., to AESI-16-6b configuration, with an MRR@10 drop 0f 0.0015. 
However, a standard autoencoder and quantization would require a payload size of 4KB to reach a similar drop, leading to latency increase of 5.5ms. 
The configuration presented in the PreTTR paper, with a 1-layer autoencoder and non-distilled BERT, has a payload size of at least 32KB, with latency increase of at least 70.5ms, making it unfitting to typical interactive settings.  
When the number of retrieved document is 1000, the impact of payload size is even larger: 1KB payload increases latency by 8.7ms, and 4KB payload leads to significant latency increase of 33.2ms, making compression even more crucial. 

} 











\section{More analysis not in the paper}
\WIP{\amit{here to the end of the paper is WIP}
\nachshon{We can stop the paper here, and it might be helpful if we want to write another paper on analyzing how context affects word embedding vectors. }
\paragraph{Part-Of-Speech (POS) tag impact on reconstruction error} next, we consider how the role of a token affect its dependency on the context. 
Therefore, we run spacy\footnote{https://spacy.io/} to compute POS tagging over the document corpus we consider. 
For each token, we aggregate its POS \guy{It's a bit strange to talk about a token's POS} tag over all appearances in the documents. 
In this experiment, we only consider cases where most of the tokens (at least 2/3) share the same POS tag. 
Then, we compute the reconstruction error as a function of POS tag. 
In this experiment, we are less interested in the overall better quality of autoencoder with side information\xspace{}. 
Therefore, to better understand the impact of POS tag on reconstruction error, we normalize it by dividing with the average reconstruction error on all tokens and reducing by 1. 
Therefore, a negative number means that the reconstruction error is lower than an average token (i.e., ``easy to reconstruct''), while a positive number means the reverse. 

Results are depicted in Figure~\ref{fig:analysis-pos}. 
We observe that AE and \mbox{AESI}\xspace{} show very different behavior. 
AE demonstrate lower reconstruction rate for punctuation and determiner, average reconstruction error for prepositions, and high reconstruction error for nouns, verbs, adjectives, and proper nouns. 
In contrast, \mbox{AESI}\xspace{} show lower reconstruction rate for nouns, verbs, adjectives, and proper nouns, but higher reconstruction rates for punctuation and prepositions, and much higher reconstruction rates for determiners. 
This behavior matches our expectation: determiners are stop words, which highly depend on the context, and as mentioned earlier, hard to reconstruct using the static token embedding. 
Similar phenomena happens also for punctuation and prepositions. \guy{I'm not sure the root cause here is that they "highly depend on the context", because we don't really understand what it is that BERT saves in those "contextualized" vectors of these kind of words. It is possible that while for more meaningful words the contextual embeddings are in fact contextual embeddings of the words, for the less meaningful words BERT uses the vectors to store some other information, which varies a lot from the initial embeddings and therefore is harder to reconstruct. Not sure how to deal with this but as a start maybe check similarity between the initial vectors and the contextual ones for different POS groups?} 
In contrast, nouns, verbs, adverbs, and proper nouns, all are very meaningful even without the context of a document. 
Therefore, for these cases, the reconstruction error of \mbox{AESI}\xspace{} is much better than the average. 

\begin{figure}
	\centering
	\includegraphics[width=1.0\columnwidth]{SuccinctDocRepr/figures/mse_pos_error.pdf}
	\caption{Normalized reconstruction error rate as a function of POS tag. Blue bars are autoencoder with side information\xspace{}, while black bars are AE. Different shades imply different number of encoded dimension.}
	\label{fig:analysis-pos}
\end{figure}

\paragraph{Ambiguity impact on reconstruction error}
For humans, perhaps the most important factor in the context is the ability to disambiguate the meaning of a word. 
The word ``bank'' have two different meaning (geographical, institute), which are commonly disambiguate by providing some context, (``river bank'', ``bank of America''). 
Therefore, it is interesting to see if ambiguous tokens are harder to reconstruct based on the static token. 

Recall that in the POS experiment, we only consider tokens where the most frequent meaning cover at least 2/3 of the appearances of the token. 
We call such tokens non-ambiguous. 
We then consider tokens where the most frequent meaning does not cover 2/3 of the appearances of the token, and consider these ambiguous. \guy{I'm not sure this is a good definition for a couple of reasons: 1. a word might be "in POS ambiguous" and 2. number of appearances does not necessarily indicate number of meanings since language tends to be not evenly distributed (e.g. "duck" the animal (noun) is probably a lot more frequent than duck the verb. This might explain the unexpected results.}
We selected a subset of POS tags: nouns, verbs, adjectives, and proper nouns, for which there are many ambiguous and non-ambiguous tokens. 
For each POS tag, we compute the reconstruction error ratio between ambiguous tokens and non-ambiguous ones. 
This ratio minus one is the ambiguity impact: how much harder it is to reconstruct an ambiguous token compared to a non-ambiguous one, assuming that the most frequent interpretation has the same POS. 
Again, a negative score implies that an ambiguous token is easier to reconstruct compared to a non-ambiguous one. 
Unlike previous experiments, we show results for 12 and 16 floats, since they do not follow similar trends to 1, 2, 4, 8 floats we used in previous experiments. 


Results appear in Figure~\ref{fig:analysis-ambiguity}. 
Except perhaps for proper nouns, differences are moderate and rarely bypass 15\% difference. 
This stands in contrast to our expectations that an ambiguous token would be much harder to reconstruct based on the static token and a few floats. 
Nevertheless, we do see that the ambiguity impact on autoencoder with side information\xspace{} is larger than on a standard autoencoder. 
In addition, for the proper noun case, the impact of ambiguity is much stronger, reaching relatively high reconstruction rates for autoencoder with side information\xspace{}, while being relatively easy to reconstruct for the autoencoder case. 
While we do not have an explanation for the exact phenomena, the overall results show that the static token embeddings is less effective for an ambiguous token compared to a non-ambiguous one. 

\begin{figure}
	\centering
	\includegraphics[width=3.2in]{SuccinctDocRepr/figures/ambiguity_reconstruction_error.pdf}
	\caption{Reconstruction error rate vs. ambiguity. Labels are similar to Figure~\ref{fig:analysis-pos}. 
	\amit{color and order seems a bit confusing here and in figure 6, we may want to make sure that AEU/AU are ordered in the graph by number of feature and the brightness in the same scale}}
	\label{fig:analysis-ambiguity}
\end{figure}

}
\section{Evaluation}\label{sec:eval}

We start this section by describing the experimental setup (\S~\ref{subsec:exprsetup}), where we introduce the tasks and datasets, and the competing approaches. Next, we present the main results on compression rates and quality tradeoff of the SDR scheme (\S~\ref{subsec:main-evaluation}). Later, we examine how the proposed autoencoder (\S~\ref{subsec:auto-encoder-mrr}) and quantization (\S~\ref{subsec:quantization-evaluation}) compare to other baselines. 
Finally, in \S~\ref{subsec:analysis-vectors}, we provide insights and discuss the information captured by our \mbox{AESI}\xspace{}-encoded vectors.


\subsection{Experimental Settings} \label{subsec:exprsetup}



\paragraph{\textbf{Tasks and Datasets}} To evaluate the effectiveness of our proposed compression approach SDR and our competing baseline, we consider two tasks from the MSMARCO 2019 Deep Learning Track~\cite{nguyen2016ms}: 

\begin{enumerate}[leftmargin=*]
    \item \textbf{Document Reranking:} In this task, for a given list of top-1000 documents (retrieved via BM25), the task is to rerank the documents such that the most relevant documents for a given query are ranked highest. The performance of models is measured using the mean reciprocal rank, $MRR@10$, metric. This task assess the suitability of the competing approaches in capturing the document context for a given query. We use the development set for this task, which consists of 6980 queries and the corresponding top--1000 documents.
    \item \textbf{Passage Reranking:} Similar as above, here we are given top--1000 passages, and the task is to rerank them such that most relevant passages for a query are ranked highest. This performance of models is measured using the normalized discounted cumulative gain, $nDCG@10$, metric, and assess whether the models can capture the graded passage relevance for a given query. For this task we use the test subset consisting of 200 queries and the corresponding top--1000 passages.
\end{enumerate}











\paragraph{\textbf{Baseline -- \emph{BERT\textsubscript{\textsc{SPLIT}}\xspace}}} 
Our algorithm is based on the late-interaction architecture \cite{macavaney2020efficient,gao2020earl,nie2020dc,chen2020dipair,cao2020deformer} depicted in Figure~\ref{fig:late-interaction}. 
We created a model based on this architecture, which we name BERT\textsubscript{\textsc{SPLIT}}\xspace, consisting of 10 layers that are computed independently for the query and the document with an additional two late-interaction layers that are executed jointly. We initialized the model from a BERT checkpoint\footnote{https://huggingface.co/cross-encoder/ms-marco-MiniLM-L-12-v2} with an embedding space of 384 and fine-tuned it using knowledge distillation from an ensemble of BERT-Large, BERT-Base, and ALBERT-Large \cite{hofstatter2020interpretable} on the MSMARCO small training dataset, which consists of almost 40M tuples of query, a relevant document, and an irrelevant document.\footnote{We used a 384 embedding size BERT since this existing checkpoint reached a higher MRR@10 score than a self-trained classical BERT model of standard 768 dimensions. The checkpoint will be released with the published paper.}

\WIP{ 
\nachshon{low priority: Consider https://huggingface.co/cross-encoder/ms-marco-MiniLM-L-2-v2 model. }
}





\paragraph{\textbf{Quantization overhead}}
We incorporate the quantization overhead into the computation of the compression ratios in the following manner: (a) we assume that the additional DRIVE scalar per block (the \mbox{$\ell_2$-norm}) is a float32 and get a space overhead of $32/(\left<\operatorname{block-size}\right>\cdot B)$ where $B$ is the number of bits in the quantization scheme; and (b) we consider the overhead caused by padding, which depends on the length distribution of documents in the dataset. 
For the sake of simplicity, we fixed the block size at 128 and measured the padding overhead using a random sample of 100k documents from the MSMARCO-DEV dataset. This measured padding overhead is
20.1\%,  9.7\%, 6.7\%, and 4.5\%, for \mbox{AESI}\xspace 4, 8, 12, and 16, respectively. In \S~\ref{subsec:quantization-evaluation}, we discuss possible means to reduce this overhead.

\paragraph{\textbf{Autoencoder training}}
Although the entire MSMARCO collection contains 8.8M documents, which can be used for training autoencoder networks, in this work we trained autoencoders on a random sample of 500K documents to reduce training time.

\paragraph{\textbf{Notation}}
We denote our SDR variants as ``\mbox{\mbox{AESI}\xspace-\{X\}-\{B\}b}'' where \{X\} is replaced with the number of features and \{B\} is replaced with the number of bits in the quantization scheme. When discussing \mbox{AESI}\xspace with no quantization we simply write ``\mbox{\mbox{AESI}\xspace-\{X\}}''.

\subsection{Main results} \label{subsec:main-evaluation}













\begin{table}[]
\setlength{\tabcolsep}{0.3em}
\begin{adjustbox}{center}
	\begin{tabular}{c|c|c|l|l}
	\toprule
		\makecell{Quant. \\ bits ($B$)} & \makecell{\mbox{AESI}\xspace \\ dim. ($c$)}      &  \makecell{Comp. \\ ratio (CR)} & \makecell{DEV \\ MRR@10}  & \makecell{TREC19 \\ nDCG@10}   \\
		\hline \hline
 		& BERT\textsubscript{\textsc{SPLIT}}\xspace      & 0.3768                   & 2\\
 		\hline
		\multirow{4}{*}{\makecell{32\\ (float)}}  
		& 16           & 48 & 0.3759 (-$0.20\%$\ignore{, $-0.0042\nicefrac{\%}{\text{CR}}$})     &  0.772 (-$0.2\%$)            \\
		& 12         & 64 & 0.3725 (-$1.14\%$\ignore{, $-0.0178\nicefrac{\%}{\text{CR}}$})$^{*}$       & 0.739 (-$3.5\%$)$^{*}$         \\
		& 8          & 96 & 0.3711 (-$1.51\%$\ignore{, $-0.0157\nicefrac{\%}{\text{CR}}$})$^{*}$ & 0.699 (-$7.5\%$)$^{**}$   \\
		& 4         & 192 & 0.3660 (-$2.87\%$\ignore{, $-0.0149\nicefrac{\%}{\text{CR}}$})$^{**}$        & 0.659 (-$11.5\%$)$^{**}$ \\
		\hline
		\multirow{4}{*}{6}
		& 16 &  243 &  0.3753 (-$0.40\%$\ignore{, $-0.0016\nicefrac{\%}{\text{CR}}$})  & 0.772 (-$0.2\%$) \\
		& 12 & 318 & 0.3728 (-$1.07\%$\ignore{, $-0.0034\nicefrac{\%}{\text{CR}}$})$^{*}$      & 0.780 (+$0.6\%$)  \\
		& 8  & 463 & 0.3689 (-$2.11\%$\ignore{, $-0.0045\nicefrac{\%}{\text{CR}}$})$^{**}$    & 0.775  (+$0.1\%$)   \\
		& 4 & 846 & 0.3624 (-$3.83\%$\ignore{, $-0.0045\nicefrac{\%}{\text{CR}}$})$^{**}$     & 0.766 (-$0.8\%$)   \\
		\hline
		\multirow{4}{*}{5}
		& 16 & 291 & 0.3735 (-$0.87\%$\ignore{, $-0.0030\nicefrac{\%}{\text{CR}}$})$^{*}$           & 0.772  (-$0.2\%$)         \\
		& 12 & 380 & 0.3714 (-$1.43\%$\ignore{, $-0.0038\nicefrac{\%}{\text{CR}}$})$^{*}$        & 0.778  (+$0.4\%$)          \\
		& 8 & 554 & 0.3649 (-$3.16\%$\ignore{, $-0.0057\nicefrac{\%}{\text{CR}}$})$^{**}$       & 0.770  (-$0.4\%$)  \\
		& 4 &  1013 &  0.3540 (-$6.05\%$\ignore{,   $-0.0060\nicefrac{\%}{\text{CR}}$})$^{**}$       & 0.767  (-$0.7\%$) \\
		\hline
        \multirow{4}{*}{4}
        & 16  & 362 & 0.3665 (-$2.74\%$\ignore{, $-0.0076\nicefrac{\%}{\text{CR}}$})$^{**}$       & 0.766 (-$0.8\%$) \\
        & 12   & 472 & 0.3639 (-$3.41\%$\ignore{, $-0.0072\nicefrac{\%}{\text{CR}}$})$^{**}$      & 0.764  (-$1.0\%$)    \\   
        & 8 & 689 & 0.3544 (-$5.95\%$\ignore{, $-0.0086\nicefrac{\%}{\text{CR}}$})$^{**}$           & 0.765 (-$0.9\%$)    \\ 	
        & 4  & 1259 & 0.3408 (-$9.55\%$\ignore{, $-0.0076\nicefrac{\%}{\text{CR}}$})$^{**}$         & 0.752 (-$2.2\%$)$^{*}$ \\  
        \hline \hline
        \multicolumn{2}{c|}{BERT\textsubscript{\textsc{SPLIT}}\xspace (Baseline)} & 2 & 0.3768 & 0.774  \\
		\bottomrule
	\end{tabular}
	\end{adjustbox}
	\caption{MRR@10 and nDCG@10 performance for the different configuration of SDR and the $BERT_{SPLIT}$ baseline over MSMARCO-DEV and MSMARCO-DL19 document and passage re-ranking tasks, respectively. In parentheses for (MRR and nDCG) is shown the absolute difference in percentage points w.r.t the BERT baseline. Using paired t-test statistic we measure statistical significance and denote with $^{*}$ and $^{**}$ significant and highly significant (for $p-value < 0.05$, and $p-value < 0.001$) the results with means different than the baseline. 
	In terms of compression rate reductions, we measured the reduction in contrast to storing the full 768-dimensions from BERT using \texttt{float32} and considering padding and normalization overheads. The highlighted cells are examples of efficient configurations, the first provides 243x compression without a significant lost, and the second provide 1013x compression with only 6.05\% degradation
	\WIP{\nachshon{low priority: consider t-test with margin.}}
	}
	\label{table:main-results}
\end{table}


The results of SDR evaluation over MSMARCO are reported in Table~\ref{table:main-results}. As can be seen, autoencoder with side information\xspace{} is effective in reducing storage requirements. 
Specifically, \mbox{AESI}\xspace-12 reduces storage requirements by 64x compared to a standard 768-dim BERT model, and by 32x compared to a DistilBERT model, with no observable drop in MRR (absolute drop of 0.004). 
\mbox{AESI}\xspace-8 show slightly larger drop of 0.006, but reach compression rate of 96x. 
\mbox{AESI}\xspace-4 show statistically significant drop of 0.01, which is still minimal, at a storage cost of almost 200x smaller than a naive approach, making it possible to store the entire MSMARCO-DEV dataset in less than 11GB of memory. Finally, the combination of \mbox{AESI}\xspace and quantization is highly effective. 
\mbox{AESI}\xspace-16-6b reach compression rate of 243x, including padding and normalization overheads, while 
MRR@10 drop is just 0.0015, which is not statistically significant. 
The Average document embedding size is 947 bytes, which, 
as shown in Appendix~\ref{subsec:analysis-elasticsearch}, Table~\ref{table:elasticsearch-latency}, does not significantly increase the fetching latency. 
The entire MSMARCO fits into 8.6GB, which makes it reasonable to store in the RAM of the hosting machine.
If further compression rates are required, \mbox{AESI}\xspace-12-4b uses just 6 bytes per token, reaching a compression rate of 472x and 487 bytes per document on average. At this level of compression the entire MSMARCO corpus fits in 4.4GB, making it possible to store it on the GPU memory alongside the model itself. 
The MRR@10 drop is noticeable (0.012), but sill quite low. nDCG@10 results show a similar trend and efficiency although with a bit more noise, which can be attributed to the smaller dataset size.



\subsection{Autoencoder Evaluation} \label{subsec:auto-encoder-mrr}
To better understand the impact of the autoencoder, we present MRR@10 results as a function of autoencoder dimension (i.e., number of floats per token that are stored) and with the different variants of autoencoders discussed in \S~\ref{subsec:autoencoder}.

In addition to the 2 dense layer encoder/decoder architecture we described in \S~\ref{subsec:autoencoder} (\textbf{\mbox{AESI}\xspace{}-2L}), we consider the following variations:
\\\\
\T{AutoEncoder with 2 Layers (AE-2L).} Standard 2-layer autoencoder with $\operatorname{gelu}$ activation. This is the same as AESI only without the side information links. 
	\ignore{\oren{did u tie the weights between the encoder and decoder?
Did u use a normalization layer in the bottleneck in any of the baselines? }}

\T{AutoEncoder with 1 Layer (AE-1L).} Standard autoencoder with a single linear layer in the encoder and decoder.

\T{AESI with 1 Layer (AESI-1L).} \mbox{AESI}\xspace{} with a single linear layer in the encoder and decoder with side information links.

\T{DECoder-only AESI (AESI-DEC-2L).} \mbox{AESI}\xspace{}, but without providing the side information to the encoder. Recall that the static token embeddings are required by the decoder to help reconstructing the original vector. This variant check if the static token embeddings helps in the encoding part. 
\\


Results are provided in Figure~\ref{fig:auto-encoder-mrr}. 
It can be seen that the side information we provide to the autoencoder (namely, the static token embeddings) is very effective in reducing storage requirements, 
achieving much better MRR@10 when the number of dimensions is small compared to a standard 2-layer autoencoder. 
As expected, a 2-layer encoder/decoder architecture is more effective than a single-layer encoder/decoder. 
The gap is especially large when using static vectors, showing that the interaction between the encoded vector and the static token embeddings is highly nonlinear. 
Finally, we note that it is possible to provide static token embeddings only to the decode, but providing it also to the encoder slightly increase overall MRR@10 score. 
\begin{figure}
    \centering
    \includegraphics[width=0.9\columnwidth]{SuccinctDocRepr/figures/mrr_plot.pdf}
    \caption{MRR@10 measured on the MSMARCO-DEV-25 dataset as a function of autoencoder dimensions. The results are shown for standard autoencoders (AE) and our approach (AESI), with single or two layer encoder and decoder networks. The x--axis shows the dimension of the encoded vector $c$. }
    
   
    \label{fig:auto-encoder-mrr}
\end{figure}


\subsection{Quantization Evaluation} \label{subsec:quantization-evaluation}
\label{sec:altQ}
To study the impact of quantization, we fix \mbox{AESI}\xspace{}-16 as our baseline and measure how different quantization strategies and number of bits affect the MRR@10 score. We note that we do not measure quantization over the baseline BERT\textsubscript{\textsc{SPLIT}}\xspace since it can only achieve a compression ratio of up to 32x per coordinate (using 1 bit per coordinate). In addition to {\bf DRIVE} (\S~\ref{subsec:quantization-algorithm}, Algorithm~\ref{code:ourQ}), we consider the following quantization strategies:
\bigskip

\T{Deterministic Rounding (DR) \cite{gershogray92}.}
Maps the input coordinates into the $[0, 2^B-1]$ range using min-max normalization and rounds to the nearest integer.

\T{Stochastic Rounding (SR) \cite{barnes1951electronic, doi:10.1137/20M1334796}.}
Normalizes, as before, using min-max normalization, adds a uniform \emph{dither} noise in $(-0.5, 0.5)$, and then rounds to the nearest integer. This provides an unbiased estimate of each coordinate.

\T{Subtractive Dithering (SD) \cite{1057702, 256489}.}
Same as SR, only now before denormalization, instead of just using the values in \mbox{$\{0,\dots,2^B-1\}$}, we first subtract the original dither noise, which we assume can be regenerated using shared randomness. This is an unbiased estimator with reduced variance.

\T{Hadamard Variants (H-DR, H-SR, and H-SD).}
These variants correspond to the previous methods; only they are preceded by a randomized Hadamard transform.

\T{DRIVE with Bias Correction (DRIVE-BC) \cite[Appendix C.3]{vargaftik2021drive}.}
This variant of DRIVE optimizes for lower bias over the mean squared error (MSE) by multiplying the dequantization result in Algorithm \ref{code:ourQ} by a bias correction scalar: $\norm{x}^2_2/\norm{\hat{y}}^2_2$ .










\bigskip

We plot the results in Figure~\ref{fig:compress_algo_analysis}. First, we observe that the Hadamard variants perform better than their non-Hadamard counterparts. Second, we see that DRIVE performs better than all other schemes. The differences are more pronounced in the low-bit regime, where the choice of quantization scheme has a drastic impact on quality; when the number of bits is large (e.g., 6), all methods perform reasonably well, and the gap between the quantization schemes is reduced. We also note that unlike in other use cases, such as distributed mean estimation, bias correction is not appropriate here and should not be performed at the cost of increased mean squared error (MSE). This conclusion follows by observing that DRIVE and the deterministic rounding methods (DR, H-DR) are respectively better than DRIVE-BC and the stochastic rounding methods (SR, H-SR). We add that the subtractive dithering methods (SD, H-SD), expectedly, work the same or better than their deterministic counterparts since they produce a similar MSE while also being unbiased.


The current quantization scheme require padding to full 128 blocks. 
For 4-8 \mbox{AESI}\xspace{} size, the padding overhead may reach 10\% -- 20\% percent. 
In addition, we send a normalization value per 128-block, which we currently send as a float32 value, adding 4\% -- 5\% additional overhead. 
Padding can be reduced by treating the last 128-block separately, e.g., applying a method that does not require Hadamard transform. 
Normalization overhead can be reduced, e.g., by sending normalization factors as float16 instead of full float32. 
However, such solutions complicate the implementation while providing limited storage benefits, so were not explored in the context of this paper. 
\nachshon{@amir: Add variable length discussion. \amit{and entropy encoding?} }


\begin{figure}
    \centering
    \includegraphics[width=3.2in]{SuccinctDocRepr/figures/mrr_values.pdf}
   
    \caption{MRR@10 for different quantization methods. Each run quantize and dequantize \mbox{AESI}\xspace{}-16 encoded documents over the MSMARCO-DEV-25 dataset. For each randomized quantization method and number of bits, we take the average of 10 runs. The error bars mark the standard deviation of these runs. 
    
   
    }
    \label{fig:compress_algo_analysis}
\end{figure}

\subsection{Towards Interpreting \mbox{AESI}\xspace{}-Encoded Vectors}
\label{subsec:analysis-vectors}
In \S~\ref{subsec:auto-encoder-mrr}, we showed the effectiveness of our autoencoder with side information\xspace{} over the naive autoencoder architectures by comparing MRR@10 scores for the MSMARCO dataset.
However, these results incorporate multiple documents and multiple tokens per document, which makes it harder to understand the low-level behavior of \mbox{AESI}\xspace{} itself.
In this subsection, we turn our focus to the token level and try to discern when and why adding the static embedding as side information is beneficial

\paragraph{Intrinsic evaluation for autoencoder}
To study the effectiveness of an autoencoder at the token level (instead of the task level), we propose to use the \emph{reconstruction error}, defined as the MSE between the original vector and the reconstructed vector:
$$MSE(v, D(E(v, u), u)),$$
where $v$ is a contextualized vector (which is the output of a BERT\textsubscript{\textsc{SPLIT}}\xspace{} model at layer $10$), $u$ is the static embedding, and the encoder $E(v, u)$ and the decoder $D(e, u)$ are as defined in \S~\ref{subsec:autoencoder}.
An high reconstruction error imply that the autoencoder had more difficulty in encoding the original vector's information.

\paragraph{Document frequency impact on reconstruction error}
A common result in the area of information retrieval is that the importance of a token is inversely correlated with its frequency. \amit{would be nice if we could cite something here, although this is mostly common sense}
That is, a token appearing in just a few documents is more important for ranking than a token appearing in most documents in the corpus. 
This motivates schemes like TF-IDF, where the importance of a token is affected by the inverse document frequency, as well as the term frequency. 
\\

In Figure~\ref{fig:analysis-idf} we show the reconstruction error as a function of the \emph{Document Frequency} (DF), 
measured in a logarithmic scale with base 10, that is: $DF(t) = \operatorname{log}_{10}(|\{d \in D:t \in d\}|/|D|)$, where $D$ is the document corpus (this is simply the negation of the standard IDF).
We consider a random sample of 256K documents from MSMARCO, which results in 20M contextualized token embedding. 
Our model uses BERT's tokenizer, with a vocabulary of 30K tokens.
We use a standard 2-layers AutoEncoder with $\operatorname{gelu}$ activation (\textbf{AE-\{X\}}), as well as our \mbox{AESI}\xspace (\mbox{\textbf{\mbox{AESI}\xspace{}-\{X\}}}).
As in the evaluation section, \{X\} is replaced with the number of features in the encoded vectors. 
We only consider relatively small X values: 1, 2, 4, or 8 floats, since larger sizes have smaller MSE, which makes it harder to identify trends.
\\

First, We observe that given a specific code size, the \mbox{AESI}\xspace{} architecture always achieve lower reconstruction error compared to the AE architecture (for all DF values).
This lower reconstruction error correlates with our results in \S~\ref{subsec:auto-encoder-mrr} that \mbox{AESI}\xspace{} achieves better ranking quality. Next, we study how the reconstruction error changes with the token frequency. For the autoencoder, there is a slight downward trend in reconstruction error as the frequency increases, which is more pronounced for the most frequent tokens. This can be explained by the fact that more frequent tokens are represented more often in the autoencoder training set, leading to a more accurate representation. 

The gap in reconstruction error between the autoencoder and \mbox{AESI}\xspace{} is a way to quantify the effect of adding the static embeddings as side information to the compression process. As seen in the figure, this gap is large for infrequent tokens, and shrinks for frequent tokens. 
A possible explanation of this phenomena is that frequent tokens have more meanings, which change according to the context, while lower-frequency tokens often represent words with a single meaning. For example, frequent tokens consist of stop words (e.g., ``the'', ``a'') and punctuation, as well as different suffixes such as ``\#\#ing'' that are a result of the BERT tokenization process. In addition, in the classical work of \citet{britton1978lexical} it was found that frequent words have more distinguished meanings compared to an average word. For tokens with a single meaning, the meaning of the token is already present in its static embedding, so the contextualized embedding can be compressed more aggressively when the static embedding is known. In the other extreme, when a frequent token has many meanings, the contextual embedding can vary greatly, and the static embedding has a more limited effect.






\begin{figure}
	\centering
	\includegraphics[width=1.0\columnwidth]{SuccinctDocRepr/figures/mse_reconstruction_error_idf.pdf}
	\caption{Reconstruction Error vs. DF for the different \mbox{AE} and \mbox{AESI} configurations. Our approach, AESI, is very robust in recovering back the token's representation with a minimal reconstruction error rate (y-axis), which is constant for documents with varying DF scores. It is interesting to note that for frequent tokens (i.e., tokens that are function words, hence play a marginal role in retrieval), the error rate is higher when compared to the rest of the tokens.\amit{todo explain smoothing window / averaging}}
	
	
	\label{fig:analysis-idf}
\end{figure}


\section{Conclusion}
In this paper, we proposed a system called SDR to solve the storage cost and latency overhead of existing late-interaction models. 
The SDR scheme uses a novel autoencoder architecture that uses static token embeddings as side information to improve encoding quality. 
In addition, we explored different quantization techniques and showed that the recently proposed DRIVE (without bias correction) performs well in our use case and presented extensive experimentation. 
Overall, the SDR scheme reduces pre-computed document representation size by 4x--11.6x compared to a baseline that uses existing approaches. 

In future work, we plan to continue investigating means to reduce pre-computed document representation size.
We believe that additional analysis of BERT's vector and their interaction with the context would be fundamental in such an advancement. 



\section{Experimental Settings} \label{subsec:exprsetup}

In this section, we describe the tasks and datasets used to evaluate the competing approaches, which are evaluated in terms of their quality to rank high relevant text passages for a given query. Next, we describe the baseline and the different configurations of SDR with emphasis on how we measure the compression ratio.

\subsection{Evaluation Metrics}

We consider two groups of evaluation metrics that capture different aspects of the resulting embeddings, namely:

\textbf{Ranking:} To measure the quality of the reconstructed token embeddings from their compressed vectors $c$, we consider the two official evaluation metrics in MSMARCO~\cite{nguyen2016ms}: MRR@10 and nDCG@10 (further discussed below).


\textbf{Compression:} We measure \emph{Compression Ratio} as amount of storage required to store the token embeddings when compared to the 
distilled baseline.
E.g., $CR=10$ implies storage size that is one tenth of the baseline vectors.



\subsection{Tasks and Datasets} 
\label{subsec:tasks}
To evaluate the effectiveness of our approach SDR and the competing baseline, we use the passage reranking task of MSMARCO~\cite{nguyen2016ms}. 
In this task, we are given a query and a list of 1000 passages (retrieved via BM25), and the task is to rerank the passages according to their relevance to the query. 
We consider two query sets:

\T{MSMARCO-DEV} We consider the development set for MSMARCO passage reranking task, which consists of 6980 queries. 
On average, each query has a single relevant passage, and other passages are not annotated. 
The performance of models is measured using the mean reciprocal rank, MRR@10, metric. \\
\T{TREC 2019 DL Track} Here we consider the test queries from TREC 2019 DL Track passage reranking dataset. 
Unlike the above, there are many passages annotated for each query, and there are graded relevance labels (instead of binary labels). This allows us to use the more informative nDCG@10 metric. 
Due to the excessive annotation overhead, this dataset consists of just 200 queries, so results are more noisier compared to MSMARCO-DEV. 




\subsection{Baseline -- \emph{BERT\textsubscript{\textsc{SPLIT}}\xspace}} \label{subsection:baseline}
Our algorithm is based on the late-interaction architecture \cite{macavaney2020efficient,gao2020earl,nie2020dc,chen2020dipair,cao2020deformer} depicted in Figure~\ref{fig:late-interaction}. 
We created a model based on this architecture, which we name BERT\textsubscript{\textsc{SPLIT}}\xspace, consisting of 10 layers that are computed independently for the query and the document with an additional two late-interaction layers that are executed jointly. We initialized the model from pre-trained weights\footnote{https://huggingface.co/cross-encoder/ms-marco-MiniLM-L-12-v2} and fine-tuned it using knowledge distillation from an ensemble of BERT-Large, BERT-Base, and ALBERT-Large \cite{hofstatter2020interpretable} on the MSMARCO small training dataset, which consists of almost 40M tuples of query, a relevant document, and an irrelevant document.\footnote{The checkpoint will be released with the published paper.}



\subsection{SDR Configuration and Training}
We denote the SDR variants as ``\mbox{\mbox{AESI}\xspace-\{c\}-\{B\}b}'' where \{c\} is replaced with the width of the encoded vector and \{B\} is replaced with the number of bits in the quantization scheme. When discussing \mbox{AESI}\xspace with no quantization, we simply write ``\mbox{\mbox{AESI}\xspace-\{c\}}''.

\paragraph{\textbf{Training.}} SDR requires a pre-training of its autoencoder to minimize its reconstruction error.
We train the autoencoder on a random subset of 500k documents from the total of 8.8M documents present in MSMARCO collection to reduce training time. 



\paragraph{\textbf{Quantization overhead.}} We incorporate the quantization overhead into the computation of the \emph{compression ratios} as follows: (a) we assume that the additional DRIVE scalar per block (the \mbox{$\ell_2$-norm}) is a float32 and get a space overhead of $32/(\left<\operatorname{block-size}\right>\cdot B)$ {where $B$ is the number of bits in the quantization scheme}; and (b) we consider the overhead caused by padding, which depends on the length distribution of documents in the dataset. 
For the sake of simplicity, we fixed the block size at 128 and measured the padding overhead using a random sample of 100k documents from the MSMARCO-DEV dataset. This measured padding overhead is
20.1\%,  9.7\%, 6.7\%, and 4.5\%, for \mbox{AESI}\xspace 4, 8, 12, and 16, respectively. 
In \S~\ref{subsec:quantization-evaluation}, we discuss possible means to reduce this overhead.




\section{Evaluation}\label{sec:eval}

In this section, we present the main results on compression ratios and quality tradeoff of the SDR scheme (\S~\ref{subsec:main-evaluation}). Later, we examine how the proposed autoencoder (\S~\ref{subsec:auto-encoder-mrr}) and quantization (\S~\ref{subsec:quantization-evaluation}) compare to other baselines. 
Finally, in \S~\ref{subsec:analysis-vectors}, we provide insights and discuss the information captured by our \mbox{AESI}\xspace{}-encoded vectors.



\subsection{Main results} \label{subsec:main-evaluation}










\begin{table}[]
\setlength{\tabcolsep}{0.3em}
\resizebox{1\columnwidth}{!}{
	\begin{tabular}{c|c|c|l|l}
	\toprule
		\makecell{Quant. \\ bits ($B$)} & \makecell{\mbox{AESI}\xspace \\ dim. ($c$)}      &  \makecell{Comp. \\ ratio (CR)} & \makecell{\textsc{msmarco-dev} \\ MRR@10}  & \makecell{TREC19-DL \\ nDCG@10}   \\
		\midrule
		\midrule
 		\multirow{4}{*}{\makecell{32\\ (float)}}  
		& 16           & 24 & 0.3759 (-$0.0009$\ignore{, $-0.0042\nicefrac{\%}{\text{CR}}$})     &  0.772 (-$0.002$)            \\
		& 12         & 32 & 0.3725 (-$0.0043$\ignore{, $-0.0178\nicefrac{\%}{\text{CR}}$})$^{*}$       & 0.784 (+$0.01$)         \\
		& 8          & 48 & 0.3711 (-$0.0057$\ignore{, $-0.0157\nicefrac{\%}{\text{CR}}$})$^{*}$ & 0.781 (+$0.007$)   \\
		& 4         & 96 & 0.3660 (-$0.0108$\ignore{, $-0.0149\nicefrac{\%}{\text{CR}}$})$^{*}$        & 0.775 (+$0.001$) \\
		\hline
		\multirow{4}{*}{6}
		& 16 &  121 &  0.3753 (-$0.0015$\ignore{, $-0.0016\nicefrac{\%}{\text{CR}}$})  & 0.772 (-$0.002$) \\
		& 12 & 159 & 0.3728 (-$0.004$\ignore{, $-0.0034\nicefrac{\%}{\text{CR}}$})$^{*}$      & 0.780 (+$0.006$)  \\
		& 8  & 231 & 0.3689 (-$0.0079$\ignore{, $-0.0045\nicefrac{\%}{\text{CR}}$})$^{*}$    & 0.775  (+$0.001$)   \\
		& 4 & 423 & 0.3624 (-$0.0144$\ignore{, $-0.0045\nicefrac{\%}{\text{CR}}$})$^{*}$     & 0.766 (-$0.008$)   \\
		\hline
		\multirow{4}{*}{5}
		& 16 & 145 & 0.3735 (-$0.0033$\ignore{, $-0.0030\nicefrac{\%}{\text{CR}}$})$^{*}$           & 0.772  (-$0.002$)         \\
		& 12 & 190 & 0.3714 (-$0.0054$\ignore{, $-0.0038\nicefrac{\%}{\text{CR}}$})$^{*}$        & 0.778  (+$0.004$)          \\
		& 8 & 277 & 0.3649 (-$0.0119$\ignore{, $-0.0057\nicefrac{\%}{\text{CR}}$})$^{*}$       & 0.770  (-$0.004$)  \\
		& 4 &  506 &  0.3540 (-$0.0228$\ignore{,   $-0.0060\nicefrac{\%}{\text{CR}}$})$^{*}$       & 0.767  (-$0.007$) \\
		\hline
        \multirow{4}{*}{4}
        & 16  & 181 & 0.3665 (-$0.0103$\ignore{, $-0.0076\nicefrac{\%}{\text{CR}}$})$^{*}$       & 0.766 (-$0.008$) \\
        & 12   & 236 & 0.3639 (-$0.0129$\ignore{, $-0.0072\nicefrac{\%}{\text{CR}}$})$^{*}$      & 0.764  (-$0.01$)    \\   
        & 8 & 344 & 0.3544 (-$0.0224$\ignore{, $-0.0086\nicefrac{\%}{\text{CR}}$})$^{*}$           & 0.765 (-$0.009$)    \\ 	
        & 4  & 629 & 0.3408 (-$0.036$\ignore{, $-0.0076\nicefrac{\%}{\text{CR}}$})$^{*}$         & 0.752 (-$0.022$)$^{*}$ \\  
        \hline \hline
        \multicolumn{2}{c|}{BERT\textsubscript{\textsc{SPLIT}}\xspace (Baseline)} & 1 & 0.3768 & 0.774  \\
		\bottomrule
	\end{tabular}}
	\caption{\emph{SDR performance in various configurations}: MRR@10 and nDCG@10 are measured over MSMARCO, as described in \S~\ref{subsec:tasks}. The absolute difference w.r.t. the BERT\textsubscript{\textsc{SPLIT}}\xspace baseline is shown in parentheses. We measured statistical significance using relative paired t-test\protect\footnotemark{} and denote with $^*$ cases with $p < 0.05$. Note that \mbox{AESI}\xspace{}-16-6b shows no significant drop in ranking quality. The compression ratios indicate the reduction in storage size, including padding and normalization overheads.}
	\label{table:main-results}
\end{table}
	



Table~\ref{table:main-results} shows the results on both query sets for SDR and its compression ratio against storing contextual token embeddings uncompressed. In terms of compression ratio, it can be seen that \mbox{AESI}\xspace{} allows us to massively reduce storage requirements both with and without quantization. 

\textbf{SDR without Quantization:} \mbox{AESI}\xspace-16 reduces storage requirements by 24x with an insignificant performance drop in MRR@10 and nDCG@10 compared to the baseline. Higher compression rates can be achieved by further reducing the \emph{context vector}'s dimensions ($c \in \{4, 8, 12\}$) at the cost of having a small but statistically significant lower performance than the baseline. Depending on the use case, such tradeoffs are highly desirable, allowing for extreme compression rates that minimize the costs of deploying Q\&A systems. 
For instance, \mbox{AESI}\xspace-12 achieves a 32x compression rate, and although the performance drop is statistically significant, the absolute difference is just 0.0043 for MRR@10 (with a tiny increase for nDCG@10). In some situations, a better compression rate would justify this slight reduction in performance.
Lastly, when using only 4 dimensions for the context vector, we obtain nearly 100x compression rate, fitting the entire MSMARCO collection in less than 11GB of memory.

\footnotetext{A relative t-test compares systems on the same queries, making it easier to distinguish subtle differences. An independent t-test corresponds to an external observer that only sees results on one system at a time. According to the latter, most of the cases are indistinguishable, except for AESI-\{4, 8\}-4b and AESI-4-5b.}


\textbf{SDR with Quantization:} Highly efficient compression rates and reranking performance is achieved when using quantization techniques. For instance, \mbox{AESI}\xspace-16-6b reaches a compression rate of 121x, including padding and normalization overheads, while at the same time showing no significant ranking performance drop.  Using \mbox{AESI}\xspace-16-6b, a document's embedding can be stored with only 947 bytes, which, as shown in Table~\ref{table:elasticsearch-latency} in Appendix~\ref{subsec:analysis-elasticsearch}, does not add a significant network latency cost in fetching such vectors. The entire MSMARCO collection can be stored within 8.6GB. There are several advantages of fitting the entire collection's representation into the main memory of the hosting machine, allowing for fast access, further fine-tuning, etc. If further compression rates are required, \mbox{AESI}\xspace-8-5b uses just 5 bytes per token, reaching a compression rate of 277x and 487 bytes per document on average. At this level of compression, the entire MSMARCO corpus fits in 3.8GB.
The MRR@10 drop is noticeable (0.0119) but still quite low. 
Finally, for TREC19-DL, the impact of compressing token embeddings is less evident. Only in the most extreme cases such as \mbox{AESI}\xspace-4-4b we see a significant drop in nDCG@10 performance.
These results demonstrate that the performance drop is very small, showing the effectiveness of our method.


\subsection{Autoencoder Evaluation} \label{subsec:auto-encoder-mrr}
To better understand the impact of the autoencoder, we present MRR@10 results as a function of autoencoder dimensions (i.e., number of floats stored per token) and with the different autoencoder configurations. In addition to the 2-layer \mbox{AESI}\xspace{} architecture we described in \S~\ref{subsec:autoencoder} (\textbf{\mbox{AESI}\xspace{}-2L}), we consider the following variations:
\\\\
\T{AutoEncoder with 2 Layers (AE-2L).} Standard 2-layer autoencoder with $\operatorname{gelu}$ activation. This is the same as AESI, only without the side information.
	\ignore{\oren{did u tie the weights between the encoder and decoder?
Did u use a normalization layer in the bottleneck in any of the baselines? }}

\T{AutoEncoder with 1 Layer (AE-1L).} Standard autoencoder with a single dense layer in the encoder and decoder.

\T{AESI with 1 Layer (AESI-1L).} \mbox{AESI}\xspace{} with a single dense encoder and decoder layer with side information.

\T{DECoder-only AESI (AESI-DEC-2L).} Similar to \mbox{AESI}\xspace{}, however the encoder has no access to the side information. Recall that the static token embeddings are required by the decoder to help reconstructing the original vector. This variant checks if the static token embeddings help in the encoding part
\\

To reduce measurement overhead, we ran the experiment over the top 25 BERT\textsubscript{\textsc{SPLIT}}\xspace{} passages for each query, denoted \textsc{msmarco-dev-25}, which has a negligible impact on the results. 
Figure~\ref{fig:auto-encoder-mrr} shows the results for the different autoencoder configurations. 
Providing the side information to the autoencoder proves to be very effective in reducing storage costs, especially when the encoded vector size is small. 
A 2-layer encoder/decoder model, as expected, is more effective than a single-layer model. The gap is especially large when using side information, showing that the interaction between the encoded vector and the static token embeddings is highly nonlinear. Finally, we note that it is possible to provide static token embeddings only to the decoder, but providing it also to the encoder slightly increases the overall MRR@10 score. 


\begin{figure}
    \centering
    \includegraphics[width=1\columnwidth]{SuccinctDocRepr/figures/mrr_plot.pdf}
    \caption{MRR@10 was measured on the MSMARCO-DEV-25 dataset as a function of autoencoder dimensions. The results are shown for standard autoencoders (AE) and our approach (AESI), with single or two-layer encoder and decoder networks. The x--axis shows the dimension of the encoded vector $c$. }
    \label{fig:auto-encoder-mrr}
\end{figure}


\subsection{Quantization Evaluation} \label{subsec:quantization-evaluation}\label{sec:altQ}

To study the impact of quantization, we fix \mbox{AESI}\xspace{}-16 as our baseline and measure how different quantization strategies and number of bits affect the MRR@10 score. Note that we do not measure quantization over the baseline BERT\textsubscript{\textsc{SPLIT}}\xspace since it can only achieve a compression ratio of up to 32x per coordinate (using 1 bit per coordinate). In addition to {\bf DRIVE} (\S~\ref{subsec:quantization-algorithm}, Algorithm~\ref{code:ourQ}), we consider the following quantization strategies:
\bigskip

\T{Deterministic Rounding (DR) \cite{gershogray92}.}
Maps the input coordinates into the $[0, 2^B-1]$ range using min-max normalization and rounds to the nearest integer.

\T{Stochastic Rounding (SR) \cite{barnes1951electronic, doi:10.1137/20M1334796}.}
Normalizes as before using min-max normalization, and additionally adds a uniform \emph{dither} noise in $(-0.5, 0.5)$ and then rounds to the nearest integer. This provides an unbiased estimate of each coordinate.

\T{Subtractive Dithering (SD) \cite{1057702, 256489}.}
Same as SR, only now before denormalization, instead of just using the values in \mbox{$\{0,\dots,2^B-1\}$}, we first subtract the original dither noise, which we assume can be regenerated using shared randomness. This is an unbiased estimator with reduced variance.

\T{Hadamard Variants (H-DR, H-SR, and H-SD).}
These variants correspond to the previous methods; only they are preceded by a randomized Hadamard transform.

\T{DRIVE with Bias Correction (DRIVE-BC) \cite[Appendix C.3]{vargaftik2021drive}.}
This variant of DRIVE optimizes for lower bias over the mean squared error (MSE) by multiplying the dequantization result in Algorithm \ref{code:ourQ} by a bias correction scalar: $\norm{x}^2_2/\norm{\hat{y}}^2_2$ .










\bigskip

Figure~\ref{fig:compress_algo_analysis} shows the results for the different quantization methods. First, we observe that the Hadamard variants perform better than their non-Hadamard counterparts. Second, we see that DRIVE performs better than all other schemes. The differences are more pronounced in the low-bit regime, where the choice of quantization scheme has a drastic impact on quality\ignore{; when the number of bits is large (e.g., 6), all methods perform reasonably well, and the gap between the quantization schemes is reduced}. We also note that unlike in other use cases, such as distributed mean estimation, bias correction is inappropriate here and should not be performed at the cost of increased mean squared error (MSE). This conclusion follows by observing that DRIVE and the deterministic rounding methods (DR, H-DR) are respectively better than DRIVE-BC and the stochastic rounding methods (SR, H-SR). We add that the subtractive dithering methods (SD, H-SD), expectedly, work the same or better than their deterministic counterparts since they produce a similar MSE while also being unbiased.


The current quantization scheme requires padding to full 128 blocks. For 4-8 \mbox{AESI}\xspace{} size, the padding overhead may reach 10\% -- 20\% percent. In addition, we send a normalization value per 128-block, which we currently send as a float32 value, adding 4\% -- 5\% additional overhead. Padding can be reduced by treating the last 128-block separately, e.g., applying a method that does not require Hadamard transform. Normalization overhead can be reduced, e.g., by sending normalization factors as float16 instead of full float32.  However, such solutions complicate the implementation while providing limited storage benefits, hence, they were not explored in the context of this paper. 

\textbf{Beyond Scalar Quantization.}
Scalar quantization using a fixed number of bits is a suboptimal technique in general since it does not allocate fewer bits for more frequent cases. 
Entropy coding\cite{gershogray92} can do better in this aspect. However, for the 6-bits case, the measured entropy was just 5.71 bits, so the potential improvement from variable-length coding does not seem to justify the efforts (even before accounting for the overhead incurred by Huffman coding or arithmetic coding). 
Another direction is to use vector quantization or entropy-constrained vector quantization. To estimate an upper bound on the benefits of such techniques, we use the rate-distortion theory (from the information theory field), which studies the optimal tradeoffs between distortion and compression rate \cite{cover_thomas}. 
For a Gaussian source, which is a reasonable approximation of the output of Hadamard transform, it is known that the optimal (lossy) compression rate is given by $\frac{1}{2}\log_2(\frac{1}{MSE})$. 
Compared to the 6-bits case, the optimal rate is 5.35 bits, indicating an upper bound of 11\%; results for different bit rates are similar. 
Therefore, we conclude that the limited gains do not seem to justify the added system complexity. 

\ignore{Scalar quantization using $K$-means with a fixed number of bits is a straightforward but suboptimal technique in general. Research in quantization and information theory offers more complex quantization schemes, which achieve a better tradeoff between compression rate and quantization distortion. The first possible improvement is to apply entropy coding~\cite{gershogray92} (such as Huffman coding or arithmetic coding) to the quantization indices. However, this improvement seems may not justify the added complexity: For the case of 6-bit quantization, the entropy of the quantization indices turned out to be 5.71bit, indicating that the compression gain is limited to about 5\% in this case (even before accounting for the overhead incurred from the entropy coding algorithm itself). Additional directions include quantizing multiple values together (vector quantization), as well as designing the quantizer with entropy consideration in mind (entropy-constrained vector quantization). In order to estimate the potential gains of all these methods combined, we turn to information theory, and rate-distortion theory in particular, which studies the optimal tradeoffs between distortion and compression rate \cite{cover_thomas}. For a Gaussian source, which is a reasonable approximation of the vectors that are compressed in our case (following the Hadamard transform), it is known that the optimal (lossy) compression rate is given by $\frac{1}{2}\log_2(\frac{1}{MSE})$, where MSE is the mean squared error of the compressed source.
We computed the optimal rate that is achievable for the MSE that our system achieved for 6 bits, and the optimal rate was 5.35bit, indicating a potential gain of 11\%. Given these results, and also given that for other bit rates the results were similar, we conclude that further quantization improvements have limited gain, which most likely does not justify the added system complexity.}



\begin{figure}
    \centering
    \includegraphics[width=3.2in]{SuccinctDocRepr/figures/mrr_values.pdf}\vspace{-10pt}
   
    \caption{MRR@10 for different quantization methods. Each run quantizes and dequantizes \mbox{AESI}\xspace{}-16 encoded documents over the MSMARCO-DEV-25 dataset. For each randomized quantization method and number of bits, we take the average of 10 runs (the error bars show the standard deviation). 
   
   
    }
    \label{fig:compress_algo_analysis}
\end{figure}

\subsection{Intrinsic Evaluation of \mbox{AESI}\xspace{}-Encoded Vectors}\label{subsec:analysis-vectors}

In the previous sections, we showed the effectiveness in ranking and utility in compression rates of \mbox{AESI}\xspace{} over AE architectures. 
However, such evaluations do not capture the encoded information at the token-level. In this intrinsic evaluation we try to discern when and why adding the static embedding as side information contributes to better capturing the token meaning. 


We study the effectiveness of different autoencoder configurations in reconstructing back the original token vector, as measured through the MSE between the original vector and the reconstructed vector:
\begin{equation*}
MSE\left(v, D\left(E(v, u), u\right)\right)\ ,
\end{equation*}
where $v$ is a contextualized vector (BERT\textsubscript{\textsc{SPLIT}}\xspace{} output at layer $10$), $u$ is the static embedding, and the encoder $E(v, u)$ and the decoder $D(e, u)$ are as defined in \S~\ref{subsec:autoencoder}. High MSE scores indicate the inability of the autoencoder to encode the original vector's information.



\textbf{Document Frequency:} One way to assess the importance of a document w.r.t. a query is through the inverse document frequency of query tokens, typically measured through TF-IDF or BM25 schemes~\cite{robertson2009probabilistic}. In principle, the more infrequent a query token is in a document collection\shorten{(i.e., high IDF)}, the higher the ranking of a document containing that token will be. Tokens with (very) high frequencies are typically stop words or punctuation symbols, which have lower importance when determining the query-document relevance.

Based on this premise, we study how MSE varies across token frequency. 
We selected a random sample of 256k documents from MSMARCO, tokenized them, and run them through BERT\textsubscript{\textsc{SPLIT}}\xspace{} to get 20M contextualized token representations. 
Then, for each token we measured their document frequency as $DF(t) = \operatorname{log}_{10}(|\{d \in D:t \in d\}|/|D|)$ (where D is our document collection), and in Figure~\ref{fig:analysis-idf} we plot the average MSE against the rounded DF scores. 
From this experiment, we make the following observations. 

First, on all encoded width configurations, our approach, \mbox{AESI}\xspace{}, consistently achieves lower MSE compared to the AE architecture (for all DF values). Lower MSE correlates to a better ranking quality, as shown in \S~\ref{subsec:auto-encoder-mrr}. Furthermore, for tokens with low DF, adding the static side information during the training of \mbox{AESI}\xspace{} for compression provides a huge advantage, which shrinks when the token is present in many documents in the collection.

Second, on the end spectrum of high-frequency tokens, we note a downwards trend for AE and an upwards trend for \mbox{AESI}\xspace{}, especially for $DF \in [-1,0]$.
The MSE decrease for AE is expected since the training data contains more frequent tokens. 
The increase for \mbox{AESI}\xspace{} can be explained given that in this frequency range, we deal with tokens that are function words (e.g., `the') whose role is more in tying up content within a sentence and has less standalone meaning. In this case, static embeddings cannot capture context, which reduces the contribution provided by the side information.






\begin{figure}
	\centering
	\includegraphics[width=1.0\columnwidth]{SuccinctDocRepr/figures/mse_reconstruction_error_idf.pdf}\vspace{-10pt}
	\caption{Reconstruction Error vs. DF for the different \mbox{AE} and \mbox{AESI} configurations. AESI shows robust performance in recovering back the token's representation with a MSE score (y-axis), which is constant for documents with varying DF scores. It is interesting to note that for frequent tokens (i.e., tokens that are function words, hence play a marginal role in retrieval), the error rate is higher when compared to the rest of the tokens.
	}
	
	\label{fig:analysis-idf}
\end{figure}
\section{Introduction}

Information retrieval (IR) systems traditionally comprise of two stages: retrieval and ranking. Given a user query, the role of the retrieval stage is to quickly retrieve a set of candidate documents from a (very large) search index. The retrieval algorithm is typically fast but not accurate enough; in order to improve the quality of the end result for the user, the candidate documents are re-ranked using a more accurate but computationally expensive algorithm.

Large deep learning models have achieved the state of the art ranking performance in IR applications~\cite{yates-etal-2021-pretrained}. Transformer networks such as BERT \cite{devlinetal_bert} consistently show better ranking effectiveness at the cost of a higher computational cost and latency \cite{Nogueira_BERT_passage}.




\begin{figure}
    \centering
    \includegraphics[width=1.1\columnwidth]{SuccinctDocRepr/figures/contribution_overview.pdf}
    \caption{\emph{High-level contribution}: MRR@10 performance vs. document corpus size tradeoff, measured on the MSMARCO-DEV dataset. BERT\textsubscript{\textsc{SPLIT}}\xspace is a distilled late-interaction model with reduced vector width and no compression (\S~\ref{subsection:baseline}).
    For MRR@10 above 0.35, SDR is 4x--11.6x more efficient compared to the baseline. 
   
   
   
    }
    \label{fig:contrib-overview}
\end{figure}

To rank $k$ documents, the ranker is called $k$ times with an input of the form (query, document), where the query is the same, but the document is different. Several works~\cite{macavaney2020efficient,gao2020modularized,chen2020dipair,cao2020deformer,nie2020dc,gao2020modularized,khattab2020colbert} have proposed to modify BERT-based rankers in a way that allows part of the model to compute query and document representations separately, and then produce the final score using a low-complexity interaction block (we denote these models as late-interaction rankers, see Fig.~\ref{fig:late-interaction}). With this approach, the document representations can be pre-computed in order to improve latency significantly: during runtime, the model computes the query representation (once), retrieves the pre-computed document representations, and only runs the interaction block $k$ times to produce the final ranking score.

\begin{figure}
    \centering
    \includegraphics[width=1.1\columnwidth]{SuccinctDocRepr/figures/late-interaction-up.pdf}
    \caption{Left: BERT ranker. Right: late-interaction ranker (with two transformer layers as the interaction block). \ignore{\oren{perhaps add and describe the entire flow. Took me a while to understand why you're mentioning the ES index size, ...}}}
    \label{fig:late-interaction}
\end{figure}





Precomputing document representations have been shown to significantly reduce latency while at the same time retaining comparable scores to BERT models~\cite{gao2020modularized}. However, this does not account for additional storage and/or network fetching latency costs: these representations typically consist of the contextual token embeddings in a transformer model, which translate to orders of magnitude larger space requirements than storing the entire corpus search index\footnote{In Appendix~\ref{subsec:analysis-elasticsearch}, we also demonstrate how the latency introduced by such an increase in storage requirements can dominate the end-to-end latency.}.


In this work, we propose Succinct Document Representation (SDR), a general scheme for compressing document representations. Our scheme enables late-interaction rankers to be efficient in both latency and storage while maintaining high ranking quality. SDR is suitable for any ranking scheme that relies on contextual embeddings and achieves extreme compression ratios (2-3 orders of magnitude) with little to no impact on retrieval accuracy. SDR consists of two major components: (1) embedding dimension reduction using an \emph{autoencoder} with \emph{side information} and (2) \emph{distribution-optimized quantization} of the reduced-dimension vectors.

In SDR, the autoencoder consists of two subnetworks: an encoder that reduces the vector's dimensions and a decoder that reconstructs the compressed vector. The encoder's output dimension represents the tradeoff between reconstruction fidelity and storage requirements. To improve the compression-reliability tradeoff, we leverage \emph{static} token embeddings, 
which are available given that the ranker has access to the document text (as it needs to render it to the user), and are computationally cheap to obtain. We feed these embeddings to both the encoder and decoder as \emph{side information},
allowing the autoencoder to focus more on storing \emph{``just the context''} of a token, and less on its original meaning that is available in the \emph{static} embeddings. Ablation tests verify that adding the static vectors significantly improves the compression rates for the same ranker accuracy.


Since data storage is measured in bits rather than floating-point numbers, SDR uses quantization techniques to reduce storage size further. Given that it is hard to evaluate the amount of information in each of the encoder's output dimensions, we perform a randomized Hadamard transform on the vectors, resulting in (1) evenly spread information across all coordinates and (2) transformed vectors that follow a Gaussian-like distribution. We utilize known quantization techniques to represent these vectors using a small number of bits, controlling for the amount of quantization distortion.

Existing late-interaction schemes either ignore the storage overhead, or consider basic compression techniques, such as a simple (1 layer) autoencoder and float16 quantization.
However, this is insufficient to reach reasonable storage size \cite{macavaney2020efficient}; furthermore, fetching latency is unacceptable for interactive systems (cf. Appendix~\ref{subsec:analysis-elasticsearch}). 
As an underlying late-interaction model we use a distilled model with a reduced vector width \cite{hofstatter2020improving}. 
As a baseline compression scheme, we use a non-linear autoencoder consisting of 2 dense layers followed by float16 quantization, a natural extension of \cite{macavaney2020efficient}.
On the MSMARCO dataset, this baseline achieves compression rates of 30x with no noticeable reduction in retrieval accuracy (measured with the official MRR@10 metric). 
On top of this strong baseline, our SDR scheme achieves an additional compression rate of between 4x to 11.6x with the same ranking quality, reducing document representation size to the same order of magnitude as the retrieved text itself. In Figure~\ref{fig:contrib-overview} we include a high-level presentation of the baseline, a variant of our method with float16 quantization, and our full method.













To summarize, here are the contribution of this work:
\begin{itemize}[leftmargin=*]
    \item We propose the Succinct Document Representation (SDR) scheme for compressing the document representations required for fast Transformer-based rankers. The scheme is based on a specialized autoencoder architecture and subsequent quantization.
    \item For the MSMARCO passage retrieval task, SDR shows compression ratios of 121x with no noticeable decrease in ranking performance. Compared to existing approaches for producing compressed representations, our method attains better compression rates (between 4x and 11.6x) for the same ranking quality.
   
    \item We provide a thorough analysis of the SDR system, showing that the contribution of each of the components to the compression-ranking effectiveness is significant.
\end{itemize}









\section{Related Work}

\textbf{Late-interaction models.} The idea of running several transformer layers for the document and the query independently, and then combining them in the last transformer layers, was developed concurrently by multiple teams: PreTTR \cite{macavaney2020efficient}, EARL \cite{gao2020earl}, DC-BERT \cite{nie2020dc}, DiPair \cite{chen2020dipair}, and the Deformer \cite{cao2020deformer}.
These works show that only a few layers where the query and document interact are sufficient to achieve results close to the performance of a full BERT ranker at a fraction of the runtime cost. For each document, the contextual token vectors are stored in a cache and retrieved during the document ranking phase.  This impacts both storage cost (storing token contextual vectors for all documents) as well as latency cost of fetching these vectors during the ranking phase.
MORES \cite{gao2020modularized} is an extension of the late-interaction models, where in the last interaction layers, the query attends to the document, but not vice versa, and without document self-attention. As the document is typically much longer, this modification results in an additional performance improvement with similar storage requirements. ColBERT~\cite{khattab2020colbert} is another variant that runs all transformer layers independently for the query and the document, and the interaction between the final vectors is done through a sum-of-max operator.
In a similar line of work, the Transformer-Kernel (TK)~\cite{hofstatter2020interpretable}, has an interaction block based on a low-complexity kernel operation. 
Both ColBERT and TK result in models with lower runtime latency at the expense of a drop in ranking quality. However, the storage requirements for both approaches are still significant.



Some of the works above acknowledge the issue of storing the precomputed document representations and proposed partial solutions. In ColBERT~\cite{khattab2020colbert}, the authors proposed to reduce the dimension of the final token embedding using a linear layer. However, even moderate compression ratios caused a drop in ranking quality. 
In the PreTTR model~\cite{macavaney2020efficient}, it was proposed to address the storage cost by using a standard auto-encoder architecture and the float16 format instead of float32. Again, the ranking quality drops even with moderate compression ratios (they measured up to 12x).


Several other works \cite{guu2020retrieval,karpukhin2020dense,xiong2021approximate,qu2020rocketqa,lu2020twinbert} proposed representing the queries and documents as vectors (as opposed to a vector per token), and using a simple function (e.g., the dot product or cosine distance) as the interaction block. While this ranker architecture approach is simple (and can also be used for the retrieval step via an approximate nearest neighbor search such as FAISS~\cite{johnson2017billion} or ScaNN \cite{avq_2020}), the overall ranking quality is generally lower compared to methods that employ a query-document cross-attention interaction.




\textbf{Knowledge distillation.} Knowledge distillation techniques, such as DistilBERT \cite{sanh2019distilbert} and TinyBERT \cite{jiao2020tinybert}, can reduce the size of a model at a small cost in terms of quality.
Such works were successfully applied for ranking~\cite{hofstatter2020improving,chen2021simplified} and do not require storing document vectors. However, distillation works best when the distilled model has at least 6 layers. With just 2-3 layers, late interaction models generally achieve better quality than distillation models by smartly using the precomputed document representations.

\textbf{Compressed embeddings.} Our work reduces storage requirements by reducing the number of bits per floating-point value. Quantization gained attention and success in reducing the size of neural network parameters \cite{pmlr-v37-gupta15, 8008430, wang2018training, wu2018training} and distributed learning communication costs \cite{pmlr-v70-suresh17a, NIPS2017_6c340f25, konevcny2018randomized, vargaftik2021drive}. Specifically, compressing word embeddings has been studied as an independent goal. May et al.~\cite{NIPS2019_compressed_embeddings} studied the effect of quantized word embeddings on downstream applications and proposed a metric for quantifying this effect with simple linear models that operate on the word embeddings directly. As our work is concerned with compressing \emph{contextual} embeddings, these methods do not apply since the set of possible embeddings values is not bounded by the vocabulary size. Nevertheless, as in \cite{NIPS2019_compressed_embeddings}, we also observe that simple quantization schemes are quite effective. Our work uses recent advances in this area to further reduce storage requirements for document representation, which, to the best of our knowledge, were not previously attempted in this context. 

\section{Introduction}
ACM's consolidated article template, introduced in 2017, provides a
consistent \LaTeX\ style for use across ACM publications, and
incorporates accessibility and metadata-extraction functionality
necessary for future Digital Library endeavors. Numerous ACM and
SIG-specific \LaTeX\ templates have been examined, and their unique
features incorporated into this single new template.

If you are new to publishing with ACM, this document is a valuable
guide to the process of preparing your work for publication. If you
have published with ACM before, this document provides insight and
instruction into more recent changes to the article template.

The ``\verb|acmart|'' document class can be used to prepare articles
for any ACM publication --- conference or journal, and for any stage
of publication, from review to final ``camera-ready'' copy, to the
author's own version, with {\itshape very} few changes to the source.

\section{Template Overview}
As noted in the introduction, the ``\verb|acmart|'' document class can
be used to prepare many different kinds of documentation --- a
double-blind initial submission of a full-length technical paper, a
two-page SIGGRAPH Emerging Technologies abstract, a ``camera-ready''
journal article, a SIGCHI Extended Abstract, and more --- all by
selecting the appropriate {\itshape template style} and {\itshape
  template parameters}.

This document will explain the major features of the document
class. For further information, the {\itshape \LaTeX\ User's Guide} is
available from
\url{https://www.acm.org/publications/proceedings-template}.

\subsection{Template Styles}

The primary parameter given to the ``\verb|acmart|'' document class is
the {\itshape template style} which corresponds to the kind of publication
or SIG publishing the work. This parameter is enclosed in square
brackets and is a part of the {\verb|documentclass|} command:
\begin{verbatim}
  \documentclass[STYLE]{acmart}
\end{verbatim}

Journals use one of three template styles. All but three ACM journals
use the {\verb|acmsmall|} template style:
\begin{itemize}
\item {\verb|acmsmall|}: The default journal template style.
\item {\verb|acmlarge|}: Used by JOCCH and TAP.
\item {\verb|acmtog|}: Used by TOG.
\end{itemize}

The majority of conference proceedings documentation will use the {\verb|acmconf|} template style.
\begin{itemize}
\item {\verb|acmconf|}: The default proceedings template style.
\item{\verb|sigchi|}: Used for SIGCHI conference articles.
\item{\verb|sigchi-a|}: Used for SIGCHI ``Extended Abstract'' articles.
\item{\verb|sigplan|}: Used for SIGPLAN conference articles.
\end{itemize}

\subsection{Template Parameters}

In addition to specifying the {\itshape template style} to be used in
formatting your work, there are a number of {\itshape template parameters}
which modify some part of the applied template style. A complete list
of these parameters can be found in the {\itshape \LaTeX\ User's Guide.}

Frequently-used parameters, or combinations of parameters, include:
\begin{itemize}
\item {\verb|anonymous,review|}: Suitable for a ``double-blind''
  conference submission. Anonymizes the work and includes line
  numbers. Use with the \verb|\acmSubmissionID| command to print the
  submission's unique ID on each page of the work.
\item{\verb|authorversion|}: Produces a version of the work suitable
  for posting by the author.
\item{\verb|screen|}: Produces colored hyperlinks.
\end{itemize}

This document uses the following string as the first command in the
source file:
\begin{verbatim}
\documentclass[sigconf]{acmart}
\end{verbatim}

\section{Modifications}

Modifying the template --- including but not limited to: adjusting
margins, typeface sizes, line spacing, paragraph and list definitions,
and the use of the \verb|\vspace| command to manually adjust the
vertical spacing between elements of your work --- is not allowed.

{\bfseries Your document will be returned to you for revision if
  modifications are discovered.}

\section{Typefaces}

The ``\verb|acmart|'' document class requires the use of the
``Libertine'' typeface family. Your \TeX\ installation should include
this set of packages. Please do not substitute other typefaces. The
``\verb|lmodern|'' and ``\verb|ltimes|'' packages should not be used,
as they will override the built-in typeface families.

\section{Title Information}

The title of your work should use capital letters appropriately -
\url{https://capitalizemytitle.com/} has useful rules for
capitalization. Use the {\verb|title|} command to define the title of
your work. If your work has a subtitle, define it with the
{\verb|subtitle|} command.  Do not insert line breaks in your title.

If your title is lengthy, you must define a short version to be used
in the page headers, to prevent overlapping text. The \verb|title|
command has a ``short title'' parameter:
\begin{verbatim}
  \title[short title]{full title}
\end{verbatim}

\section{Authors and Affiliations}

Each author must be defined separately for accurate metadata
identification. Multiple authors may share one affiliation. Authors'
names should not be abbreviated; use full first names wherever
possible. Include authors' e-mail addresses whenever possible.

Grouping authors' names or e-mail addresses, or providing an ``e-mail
alias,'' as shown below, is not acceptable:
\begin{verbatim}
  \author{Brooke Aster, David Mehldau}
  \email{dave,judy,steve@university.edu}
  \email{firstname.lastname@phillips.org}
\end{verbatim}

The \verb|authornote| and \verb|authornotemark| commands allow a note
to apply to multiple authors --- for example, if the first two authors
of an article contributed equally to the work.

If your author list is lengthy, you must define a shortened version of
the list of authors to be used in the page headers, to prevent
overlapping text. The following command should be placed just after
the last \verb|\author{}| definition:
\begin{verbatim}
  \renewcommand{\shortauthors}{McCartney, et al.}
\end{verbatim}
Omitting this command will force the use of a concatenated list of all
of the authors' names, which may result in overlapping text in the
page headers.

The article template's documentation, available at
\url{https://www.acm.org/publications/proceedings-template}, has a
complete explanation of these commands and tips for their effective
use.

Note that authors' addresses are mandatory for journal articles.

\section{Rights Information}

Authors of any work published by ACM will need to complete a rights
form. Depending on the kind of work, and the rights management choice
made by the author, this may be copyright transfer, permission,
license, or an OA (open access) agreement.

Regardless of the rights management choice, the author will receive a
copy of the completed rights form once it has been submitted. This
form contains \LaTeX\ commands that must be copied into the source
document. When the document source is compiled, these commands and
their parameters add formatted text to several areas of the final
document:
\begin{itemize}
\item the ``ACM Reference Format'' text on the first page.
\item the ``rights management'' text on the first page.
\item the conference information in the page header(s).
\end{itemize}

Rights information is unique to the work; if you are preparing several
works for an event, make sure to use the correct set of commands with
each of the works.

The ACM Reference Format text is required for all articles over one
page in length, and is optional for one-page articles (abstracts).

\section{CCS Concepts and User-Defined Keywords}

Two elements of the ``acmart'' document class provide powerful
taxonomic tools for you to help readers find your work in an online
search.

The ACM Computing Classification System ---
\url{https://www.acm.org/publications/class-2012} --- is a set of
classifiers and concepts that describe the computing
discipline. Authors can select entries from this classification
system, via \url{https://dl.acm.org/ccs/ccs.cfm}, and generate the
commands to be included in the \LaTeX\ source.

User-defined keywords are a comma-separated list of words and phrases
of the authors' choosing, providing a more flexible way of describing
the research being presented.

CCS concepts and user-defined keywords are required for for all
articles over two pages in length, and are optional for one- and
two-page articles (or abstracts).

\section{Sectioning Commands}

Your work should use standard \LaTeX\ sectioning commands:
\verb|section|, \verb|subsection|, \verb|subsubsection|, and
\verb|paragraph|. They should be numbered; do not remove the numbering
from the commands.

Simulating a sectioning command by setting the first word or words of
a paragraph in boldface or italicized text is {\bfseries not allowed.}

\section{Tables}

The ``\verb|acmart|'' document class includes the ``\verb|booktabs|''
package --- \url{https://ctan.org/pkg/booktabs} --- for preparing
high-quality tables.

Table captions are placed {\itshape above} the table.

Because tables cannot be split across pages, the best placement for
them is typically the top of the page nearest their initial cite.  To
ensure this proper ``floating'' placement of tables, use the
environment \textbf{table} to enclose the table's contents and the
table caption.  The contents of the table itself must go in the
\textbf{tabular} environment, to be aligned properly in rows and
columns, with the desired horizontal and vertical rules.  Again,
detailed instructions on \textbf{tabular} material are found in the
\textit{\LaTeX\ User's Guide}.

Immediately following this sentence is the point at which
Table~\ref{tab:freq} is included in the input file; compare the
placement of the table here with the table in the printed output of
this document.

\begin{table}
  \caption{Frequency of Special Characters}
  \label{tab:freq}
  \begin{tabular}{ccl}
    \toprule
    Non-English or Math&Frequency&Comments\\
    \midrule
    \O & 1 in 1,000& For Swedish names\\
    $\pi$ & 1 in 5& Common in math\\
    \$ & 4 in 5 & Used in business\\
    $\Psi^2_1$ & 1 in 40,000& Unexplained usage\\
  \bottomrule
\end{tabular}
\end{table}

To set a wider table, which takes up the whole width of the page's
live area, use the environment \textbf{table*} to enclose the table's
contents and the table caption.  As with a single-column table, this
wide table will ``float'' to a location deemed more
desirable. Immediately following this sentence is the point at which
Table~\ref{tab:commands} is included in the input file; again, it is
instructive to compare the placement of the table here with the table
in the printed output of this document.

\begin{table*}
  \caption{Some Typical Commands}
  \label{tab:commands}
  \begin{tabular}{ccl}
    \toprule
    Command &A Number & Comments\\
    \midrule
    \texttt{{\char'134}author} & 100& Author \\
    \texttt{{\char'134}table}& 300 & For tables\\
    \texttt{{\char'134}table*}& 400& For wider tables\\
    \bottomrule
  \end{tabular}
\end{table*}

Always use midrule to separate table header rows from data rows, and
use it only for this purpose. This enables assistive technologies to
recognise table headers and support their users in navigating tables
more easily.

\section{Math Equations}
You may want to display math equations in three distinct styles:
inline, numbered or non-numbered display.  Each of the three are
discussed in the next sections.

\subsection{Inline (In-text) Equations}
A formula that appears in the running text is called an inline or
in-text formula.  It is produced by the \textbf{math} environment,
which can be invoked with the usual
\texttt{{\char'134}begin\,\ldots{\char'134}end} construction or with
the short form \texttt{\$\,\ldots\$}. You can use any of the symbols
and structures, from $\alpha$ to $\omega$, available in
\LaTeX~\cite{Lamport:LaTeX}; this section will simply show a few
examples of in-text equations in context. Notice how this equation:
\begin{math}
  \lim_{n\rightarrow \infty}x=0
\end{math},
set here in in-line math style, looks slightly different when
set in display style.  (See next section).

\subsection{Display Equations}
A numbered display equation---one set off by vertical space from the
text and centered horizontally---is produced by the \textbf{equation}
environment. An unnumbered display equation is produced by the
\textbf{displaymath} environment.

Again, in either environment, you can use any of the symbols and
structures available in \LaTeX\@; this section will just give a couple
of examples of display equations in context.  First, consider the
equation, shown as an inline equation above:
\begin{equation}
  \lim_{n\rightarrow \infty}x=0
\end{equation}
Notice how it is formatted somewhat differently in
the \textbf{displaymath}
environment.  Now, we'll enter an unnumbered equation:
\begin{displaymath}
  \sum_{i=0}^{\infty} x + 1
\end{displaymath}
and follow it with another numbered equation:
\begin{equation}
  \sum_{i=0}^{\infty}x_i=\int_{0}^{\pi+2} f
\end{equation}
just to demonstrate \LaTeX's able handling of numbering.

\section{Figures}

The ``\verb|figure|'' environment should be used for figures. One or
more images can be placed within a figure. If your figure contains
third-party material, you must clearly identify it as such, as shown
in the example below.
\begin{figure}[h]
  \centering
  \includegraphics[width=\linewidth]{sample-franklin}
  \caption{1907 Franklin Model D roadster. Photograph by Harris \&
    Ewing, Inc. [Public domain], via Wikimedia
    Commons. (\url{https://goo.gl/VLCRBB}).}
  \Description{A woman and a girl in white dresses sit in an open car.}
\end{figure}

Your figures should contain a caption which describes the figure to
the reader.

Figure captions are placed {\itshape below} the figure.

Every figure should also have a figure description unless it is purely
decorative. These descriptions convey what's in the image to someone
who cannot see it. They are also used by search engine crawlers for
indexing images, and when images cannot be loaded.

A figure description must be unformatted plain text less than 2000
characters long (including spaces).  {\bfseries Figure descriptions
  should not repeat the figure caption – their purpose is to capture
  important information that is not already provided in the caption or
  the main text of the paper.} For figures that convey important and
complex new information, a short text description may not be
adequate. More complex alternative descriptions can be placed in an
appendix and referenced in a short figure description. For example,
provide a data table capturing the information in a bar chart, or a
structured list representing a graph.  For additional information
regarding how best to write figure descriptions and why doing this is
so important, please see
\url{https://www.acm.org/publications/taps/describing-figures/}.

\subsection{The ``Teaser Figure''}

A ``teaser figure'' is an image, or set of images in one figure, that
are placed after all author and affiliation information, and before
the body of the article, spanning the page. If you wish to have such a
figure in your article, place the command immediately before the
\verb|\maketitle| command:
\begin{verbatim}
  \begin{teaserfigure}
    \includegraphics[width=\textwidth]{sampleteaser}
    \caption{figure caption}
    \Description{figure description}
  \end{teaserfigure}
\end{verbatim}

\section{Citations and Bibliographies}

The use of \BibTeX\ for the preparation and formatting of one's
references is strongly recommended. Authors' names should be complete
--- use full first names (``Donald E. Knuth'') not initials
(``D. E. Knuth'') --- and the salient identifying features of a
reference should be included: title, year, volume, number, pages,
article DOI, etc.

The bibliography is included in your source document with these two
commands, placed just before the \verb|\end{document}| command:
\begin{verbatim}
  \bibliographystyle{ACM-Reference-Format}
  