Bit Cipher — A Simple yet Powerful Word
Representation System that Integrates
Efficiently with Language-Models

Standard-basis encoding is unavoidable for NLP applications, as one must always encode tokens from a given model’s vocabulary: $W$. This makes dimensionality reduction necessary for NLP applications, as the combinatorial overhead on the model parameters required to process $|W|$-dimensional hidden states becomes tremendous inside of models. While dimensionality reduction can be handled via gradient-based optimization in DL systems, the random nature of DL optimization obfuscates the meaning of low dimensions. However, we conjecture that a similar and explicit encoder-decoder-style factorization of standard-basis information exists.

Supposing each token $t$ in $W$ has identity modified from the usual one-hot vector as follows: (1) select a ‘low’ dimension: $b\leq|W|$, and (2) assign a unique bit-vector, $\eta_{t}\in\{0,1\}^{b}$ to each. We base our approach on a distinguishability hypothesis: which expects that a ‘good’ order for the bits distinguishes the highest-frequency tokens best, and has latitude to assign similar-frequency tokens similar vectors, meaning word vectors are assigned based on unigram frequency ranking. Working along these lines, we define $b$-bit encipherment as the process of assigning probabilistically normalized (e.g., vectors are probabilistic vectors and the modulus of vectors is 1) with all $b$-bit vectors in a ‘smooth’ order, by inducting the order that $i=1$: assigns the set of $b$ standard basis vectors: $\mathcal{V}^{b}_{1}$ to the $b$ most-frequent tokens (generalizing one-hots/standard bases); $i=2$: adds standard-basis vectors to those from $\mathcal{V}^{b}_{k-1}$ in reverse order of assignment, while filtering for unique bit-vectors in $\{0,1\}^{b}$; $i=3$: repeats step $i=2$. $b$-bit vectors are then normalized for encipherment: $v_{t}=\eta_{t}/\|\eta_{t}\|_{1}$.

To assure that co-occurrence matrices are dense, we modify the base representation of the model from sparse, one-hot, to dense vectors of the same size. We first form a model: $\beta\in(0,1)^{N}$, for the portion of time that each $i$-token’s observations are (non-)erroneous as the definition shown above. Assuming that the highest-frequency tokens will be the least erroneously observed, we assume that only one error will be observed relative to each token’s observed frequency, that is: $\beta_{i}=f_{i}/(f_{i}+1)$, where $f_{i}$ is the unigram frequency of token i. Next and regardless of the token that is observed, we wish to modify its one-hot vector according to the probabilities that any different, $j$-token, should have been observed, instead, which will take the form of another vector: $\sigma\in(0,1)^{N}$, but which is normalized: $\|\sigma\|_{1}=1$, and so define these other-token observation probabilities as: $\sigma_{j}=(1-f_{j}/M)/(N-1)$. To understand $\sigma$ intuitively, we first note that 1-minus each token’s unigram probability: $1-f_{j}/M$ expresses the probability of each token not being observed. Hence, the model $\sigma$ assumes that these (non-mutually exclusive) probabilities weight a distribution for the other token that should’ve been observed. For each one-hot vector, $y_{i}$, we then pull together these pieces to define noisy/dense vectors as: $\nu_{i}=\beta_{i}y_{i}+(1-\beta_{i})\sigma$, which form the embedding layers used in all language modeling architectures.

Knowing the definition and the encoding method of noise into cipher embedding enables us the procedural generation of word vectors. With the given dimension $d$, the bit-cipher algorithm is capable of generating the number of $2^{d}-1$ vectors. In details of how the process works: The procedure operates in two steps: Initially, a set of probabilistic vectors, referred to as "plain vectors", is generated in accordance with the given definition. Subsequently, noise information is encoded based on the analysis of the ratio of document frequency to word frequency, denoted as $r_{i}=d_{i}/f_{i}$. This ratio determines the extent of noise information encoded into plain vectors. Specifically, words with high word frequency but low document frequency yield a small ratio, indicating that the word is noisy within the entire training set. Consequently, more noise information is "baked" into the plain vectors and vice versa. This is achieved using the formula: $\nu_{i}=\beta_{i}y_{i}+(1-\beta_{i})\sigma$ producing the final set of cipher embeddings The pseudocode of how exactly the algorithm can be implemented is also shown in Fig2

4. For words ranked within the intervals of $[C(5,2)+1,C(5,2)+C(5,3)]$, $[C(5,3)+1,C(5,3)+C(5,4)]$, and $[C(5,4)+1,C(5,4)+C(5,5)]$, values are assigned to positions following the same logic.

Finally, each unique token is allocated a unique vector. By incorporating noise information relative to the distribution of words across various documents, the finalized version of bit-cipher embedding is obtained.

To illustrate the efficacy of cipher embeddings, models were trained on the CommonCrawl dataset using Cat (concatenation) and Sum (summation) methods for aggregating contextual information, informed by the bits hyperparameter, log=True, and dtype=’df’. The latter two parameters enhanced sensitivity to infrequent words and adjusted noise levels based on word’s document frequency, optimizing focus on distinctive words and mitigating biases.

The bit-cipher models are trained on five different scales of data-size: 0.5B-token, 1B-token, 2B-token, 4B-token, and 8B-token with setting up different radius (window size) and bits. Through incremental increase of the data-size, we aim to understand how model performance adjusts with the intake of more data. Although this data-size range is relatively small compared to other pre-trained word embedding methods, like GloVe trained with 42B and 840B tokens (Pennington et al., 2014a) and word2vec trained on Google News with 100B tokens (Mikolov et al., 2013a). All that is being said here is to validate the efficiency of bit-cipher as a means of learning representation, which we further corroborate through a series of probing experiments in the section.4.

Standard spaCy tokenization (Honnibal et al., 2020) was used for preprocessing, and models underwent a two-step training procedure as per sec 3.3 & Figure 2. Contextual information was integrated using Cat or Sum methods, with Cat models achieving representation lengths of 200d to 1600d (following the exponent of 2 times 100) across different bit settings and Sum models blending context information through element-wise addition, yielding a total of 60 models across varied radii and data sizes.

For comparability across models, we derived word embeddings from the GlOVe 6B embeddings, encompassing 400,000 tokens and with tokens appear in the evaluation datasets, yielding a total of 419,374 unique word embeddings. Any words identified within the context window that did not exist in our curated word-list were labeled as out-of-vocabulary (OOV) and were consequently assigned a distinctive embedding. This strategy for managing OOV words contributes to memory optimization, given that it mandates the processing of only a particular subset of words.

The conduction of Probing experiments are inspired by (Hewitt & Liang, 2019) with designing POS tagging with the Georgetown University Multilayer (GUM) dataset (Zeldes, 2017), Named Entity Recognition (NER) using CoNLL-2003 shared benchmark dataset (Tjong Kim Sang & De Meulder, 2003) to evaluate the performance of bit-cipher.

Named Entity Recognition. NER probing experiment is conducted by CoNLL-2003 shared benchmark dataset which is a collection of data about Reuters newswire articles containing four different entity types: persons (PER), organizations (ORG), locations (LOC) and miscellaneous names (MISC). The probing model for NER is trained on CoNLL-2003 training data using CoNLL-2003 validation set for hyperparameter tuning. We follow the simplest and most straightforward setup with training an MLP by only using the bit-cipher embedding as the feature and directly adopt labels in the CoNLL-2003 dataset using the label-to-index method to convert each label into a unique number to setup the input and output of the probing model.

Part-of-speech (POS) tagging. Part-of-speech tagging is a task of assigning labels to each word with its corresponding grammatical category, such as noun, verb, adjective, etc. The Georgetown University Multilayer (GUM) dataset is a richly annotated corpus that contains comprehensive linguistic features. We extract the POS tagger of words in the GUM and train an MLP following the same setup as the NER experiment using the bit-cipher embeddings as the input and POS taggers as output.

After obtaining the bit-cipher embeddings following 3.5, we applied a two-step post-processing to refine the word representations, and all probing experiments used this refined version of bit-cipher. Initially, a whitening transformation was employed to eliminate redundancies and normalize the embeddings, ensuring linearly uncorrelated word vectors with uniform variance, reducing inherent bias and making the distribution of embeddings more consistent (Kessy et al., 2016).

Next, we implemented mean-centering and L2 Normalization on each vector to address shifts in statistical distribution, inherent in probabilistic vectors like bit-cipher, which could cause inconsistencies in magnitude. This process stabilized the numerical representations, making them robust, and ensuring unbiased and scale-independent comparisons between word vectors.

For probing experiments, a 2-layer Multi-Layer Perception (MLP) was utilized, incorporating LeakReLU activation to mitigate the vanishing gradient problem, and a dropout rate of 0.5 for regularization (Xu et al., 2015). The output layer featured a LogSoftmax function, maintaining numerical stability and a balanced probability distribution, key for optimal performance.

Probing experiments conducted on 100 separate bit-cipher embedding sets are presented in Tables 2–7. Their results at POS tagging and NER demonstrate noticeable and perhaps expected variations in performance. We see clearly that cipher-only models generally don’t improve with increases of data (Tabs. 6,7), which is sensible given that ciphers only require ranking information and word frequency ranks converge over relatively little data.

For both Sum and Cat models (Tabs. 2–4), we see marked improvements from training over increased volumes of data, as observed from Figure 3(a) & 3(b) that when the bits is fixed, increasing the data size often results in improved model performance. Furthermore, in the case of Sum models, a clear performance gain is observed with an increase in the value of bits with bits = 200 set of models consistently demonstrate the highest performance. However, the performance is likewise sensible, assuming that the quadratic co-frequency information in co-occurrences requires more data to stabilize. However, between the Sum and Cat models, we note that Cat models improve over increases in data with greater stability—they scale more reliably as shown in Figure 3(a) & 3(b) that with fixing bits, 8B models always have the best performance. Moreover, we find that Cat models appear to consistently outperform same-dimension Sum models, despite being constrained to fewer bits, as can be seen from the cross-section of comparable models presented in Tab. 1. The inconsisency of model performance tendency is partially due to the fact that we did not do any preprocessing of the data except lowercase when training the bit-cipher. With refined preprocessing, the information gain would be even obviously to observe with the increase of data size.

When similar quantities of data are utilized, models that are more performant than word2vec, as well as quite comparable to GloVe, can be trained from bit-cipher co-occurrences. This can be see directly in Tab. 1 for 200-dimensional bit-cipher models, which we compare to an externally-trained 300-dimensional word2vec model, a 200-dimensional GloVe and bit-cipher models. On its own, the noised cipher out-competes word2vec, while relatively-low radius ($r=4$) Sum and Cat models perform comparably to a set of GloVe embedding, which were also externally trained. Despite the Sum and Cat models both utilizing a substantially smaller radius ($r=4$) than GloVe ($r=10$), we see that both of the comparable co-occurrent bit-cipher models out-perform GloVe at POS tagging, and perform comparably at NER. Finally, we note that these results rank the bit-cipher at position 20 amongst the NER models retained on a well-known/public page: Tracking Progress in Natural Language Processing (Ruder, 2022), and moreover, present POS tagging results quite similar to other strong baselines (Ruder & Plank, 2018), whose model architectures tend to be much more complex and expressive than the MLPs used in our probing experiments.

Firstly, the potential application of cipher is in the efficient training of language models. By using bit-cipher to construct the embedding layer of the language model and integrating it into the model’s training process, we could potentially improve training efficiency and reduce the demand for computational resources.

Models are trained from scratch, utilizing both cold-start and warm-start approaches, with standard transformers (Vaswani et al., 2017). Our approach involves initially training bit-cipher with the BabyLM 10M dataset and replacing the randomly initialized embeddings in the warm-start model. An additional technique employed in the warm-start cipher with language model training involves freezing the embedding layer before the model is trained and subsequently unfreezing it for further optimization using backpropagation. This freezing/thawing technique offers two benefits: (1) As the embedding layer is the first layer in any language model, it typically requires the most optimization time through backpropagation and is thus the most expensive layer. By initially freezing this layer, (2) we avoid the deterioration of model performance, in terms of perplexity, that can occur when the sensitive and delicate embeddings are modified during warm-start training. Therefore, the warm-start model adopts a two-step training procedure: initially freezing the embedding layer and proceeding with regular training, followed by unfreezing the embedding layer for further optimization through backpropagation. Cold-start models adhere to the traditional training approach, initializing all parameters randomly and optimizing them through backpropagation.

We conducted experiments using two sets of cipher embeddings: one with bits=$2^{7}$ and radius=$2^{7}$, and another with bits=$2^{7}$ and radius=$2^{3}$. The comparison of perplexity between warm-start and cold-start models is illustrated in Fig4. The figure distinctly demonstrates that not only do warm-start models begin with a superior start, but they can also be further optimized through backpropagation, making this an overall more effective method for training language models.

In addition to using bit-cipher as part of LM training, we find it’s also promising to use the algorithm for efficient LM fine-tuning. The traditional finetuning process, which necessitates retraining the model on a task-specific dataset, remains costly, leading to the exploration of zero-shot, few-shot, and in-context learning strategies, prioritizing performance and efficiency. Although these methods effectively extract useful features learned during training, there is a known trade-off; for instance, prompted models do not always outperform fine-tuned models. Fine-tuned models, trained for a specific purpose on one or a series of related datasets for a downstream task, typically achieve state-of-the-art (SOTA) results.

A paradigm of fine-tuning that balances performance and training efficiency is desirable, allowing for the deployment of numerous specific-purpose models with superior performance that are less costly than training large models. In our method, we first train cipher embeddings on the fine-tuned dataset to acquire what we term “cipher fine-tune embeddings”, then replace the embedding layer in the pre-trained language models with these cipher-fine-tuned embeddings, designed with specific fine-tune objectives. The efficiency of cipher training renders this step cost-effective, enhancing overall model efficiency.