# BTR: Binary Token Representations for Efficient Retrieval Augmented Language
Models

Qingqing Cao, Sewon Min, Yizhong Wang, Hannaneh Hajishirzi
Paul G. Allen School of Computer Science & Engineering
University of Washington
<EMAIL_ADDRESS>

###### Abstract

Retrieval augmentation addresses many critical problems in large language
models such as hallucination, staleness, and privacy leaks. However, running
retrieval-augmented language models (LMs) is slow and difficult to scale due
to processing large amounts of retrieved text. We introduce binary token
representations (BTR), which use 1-bit vectors to precompute every token in
passages, significantly reducing computation during inference. Despite the
potential loss of accuracy, our new calibration techniques and training
objectives restore performance. Combined with offline and runtime compression,
this only requires 127GB of disk space for encoding 3 billion tokens in
Wikipedia. Our experiments show that on five knowledge-intensive NLP tasks,
BTR accelerates state-of-the-art inference by up to 4x and reduces storage by
over 100x while maintaining over 95% task performance. Our code will be
publicly available at https://github.com/csarron/BTR.

##  1 Introduction

Large language models (LLMs) Brown et al. (2020b); Touvron et al. (2023a),
despite their widespread success, still suffer from issues such as
hallucinations Mallen et al. (2023); Mündler et al. (2023), staleness, and
privacy leaks Huang et al. (2022). Retrieval-augmented language models (e.g.,
Lewis et al. (2020); Izacard et al. (2022b)) alleviate such problems via a
retrieve-and-read approach (Figure 1), using a retrieval component to find
passages relevant to the input query followed by a reader model (e.g., an LLM)
that generates output given the query concatenated with retrieved passages.
However, this approach is slow (e.g., only handles a few queries for a
powerful server GPU) at inference time mainly due to the reader model that
needs to compute cross-attention between the input query and a large number of
passages. Existing solutions Lee et al. (2021); Cao et al. (2020) improve the
inference computation by decomposing query and passage encoding and
precomputing passage representations, but they come with large storage costs
(terabytes of storage; §4).

In this work, we improve the inference speed of the reader model in a
retrieval-augmented LM with a small storage footprint by introducing
_cacheable and calibrated Binary Token Representations_ (BTR). BTR (Figure 1)
precomputes token representations for the retrieved passages in the reader
model. The binary representations are 1-bit vectors for the tokens in a
passage and are created from the hidden states in the reader encoder layers
via calibrated binarization which are effective for downstream tasks such as
question answering. BTR reduces the storage footprint and improves the runtime
speed since the representations are 1-bit vectors, and the reader uses the
cached representations. To avoid degradation of task accuracy caused by binary
representations, we introduce two training objectives by adding (i) a _passage
representation recovery_ objective that makes the binary representations
preserve the passage semantics before the binarization; and (ii) a _query-
aware passage token distillation_ objective that compensates the information
loss due to precompuation of passage representations independent of the query.

Furthermore, we observe significant redundancies in precomputed token
representations in retrieved passages since they are relevant to the query and
contain similar information. Removing such redundancies only causes minimal
task accuracy loss (<0.5% in our experiments), but shows significant benefits
in storage and runtime inference. To address this, we further develop token
compression over BTR by merging similar precomputed token vectors after
training and merging similar concatenated query-passage representations during
inference.

We evaluate BTR on five knowledge-rich NLP tasks, including three open-domain
question-answering tasks (NaturalQuestions Kwiatkowski et al. (2019), TriviaQA
Joshi et al. (2017), and WebQA Berant et al. (2013)), the FEVER Thorne et al.
(2018) fact-checking task, and the MMLU Hendrycks et al. (2020) reasoning
benchmark. Compared to baseline systems, BTR reduces disk storage by up to
101x and improves inference speed by 2–4x for the reader of two state-of-the-
art retrieval-augmented language models. BTR also retains 90–95% of the
original models’ performance. Our analysis experiments show that binary token
representations are effective and contribute most to improving the inference
speed and reducing the storage costs of readers. The training regularization
objectives help mitigate the task accuracy loss and the offline and runtime
token compression techniques further bring down storage footprint and increase
inference efficiency.

[width=0.95]fig/teaser-v3.pdf

Figure 1: Retrieval-augmented models use a retrieve-and-read pipeline. The
reader can be either an encoder or an encoder-decoder model. BTR creates
cacheable binary representations for the passages via decomposition and
calibrated binarization to speed up reader inference. BTR further reduces
storage by offline compression and improves inference speed by runtime
compression.

##  2 Background and Related work

We first describe the architecture of retrieval-augmented language models and
then related efficiency techniques designed for them. Next, we summarize
relevant methods to improve model efficiency, including quantization and
binary representations.

#### Retrieval-Augmented Language Models.

Retrieval-augmented language models have shown strong performance in many
tasks, including language modeling Borgeaud et al. (2022); Min et al. (2023),
open-domain question answering, and fact checking Izacard et al. (2022b);
Lewis et al. (2020); Guu et al. (2020); Shi et al. (2023).

As shown in Figure 1, a retrieval-augmented language model works by first
using a retriever to retrieve many passages relevant to the input query and
then using a reader component to extract or generate the answers. While the
retriever is often fast enough, the reader causes a speed bottleneck in
retrieval augmentation because it requires computing cross-attention between
the input query and many passages. For example, Figure 1 illustrates a state-
of-the-art encoder-decoder reader Izacard et al. (2022b) architecture called
Fusion-in-Decoder (FiD) Izacard & Grave (2021). FiD first concatenates each
passage with the query and processes them in parallel (independently) in the
encoder; then the decoder fuses information across all the concatenated
passage-query representations and produces answers. In our experiments, we
observe that the passage encoding takes over 60% of the reader’s computation
on commodity GPUs, and we save such computations by precomputing the passage
representations, leading to significant speedup in the inference with reduced
storage costs.

#### Efficient methods for reader models.

DensePhrase Lee et al. (2021) builds contextualized phrase representations for
the passage corpus, completely removes the reader component, and uses phrase
retrieval to produce answers for the query. Despite its high inference
throughput, the accuracy is much lower than similar size BTR models. FiD-light
Hofstätter et al. (2022) and FiDO de Jong et al. (2022) focus on improving the
inference latency for FiD models on customized hardware like TPUs, they
compress passage representations into fixed-size vectors to reduce the decoder
computation. But on more popular hardware like GPUs, the passage encoder is
the computation bottleneck, and their decoder-oriented optimizations are
likely to be less effective in improving inference speed. LUMEN de Jong et al.
(2023) and DeFormer Cao et al. (2020) precompute cacheable continuous passage
representations to speed up reader inference, but they take up 100x more
storage than BTR.

#### Model quantization and binarization.

Another line of research focuses on model quantization Dettmers et al. (2022);
Xiao et al. (2023); Yuan et al. (2023); Frantar et al. (2022) or binarization
Bai et al. (2021); Qin et al. (2022) for resource-constrained settings. It
improves model efficiency by compressing model weights to lower precision to
reduce runtime memory usage. However, quantization does not necessarily
improve the inference speed of readers as we will empirically show in §4. This
is because quantized models still need to process large amounts of input
passage data for readers, which requires huge computation. Meanwhile,
quantization methods are orthogonal to our BTR and can help deploy BTR for
platforms with low resources.

#### Binary representations.

Previous work has used binary representations for text retrieval Yamada et al.
(2021), semantic matching Tissier et al. (2019); Shen et al. (2019), or image
retrieval Jain et al. (2017); Huang et al. (2019); Liu et al. (2016).
Motivated by this line of work, we build binary token representations to
improve reader efficiency which was unexplored before. This leads to various
new challenges, likely because token representations require storing more
fine-grained information than retrieval or semantic matching, which we
effectively address by introducing new calibration techniques and training
objectives.

##  3 Method

We present BTR, a fast and storage-efficient reader for retrieval-augmented
language models. BTR creates cacheable calibrated binary representations for
the retrieved passages to speed up inference and avoid large storage overhead.
We describe BTR for encoder-decoder readers which are most widely used in the
state-of-the-art models (Izacard et al., 2022b; Izacard & Grave, 2021), and
later show how to apply BTR for the encoder-only model (§4). The encoder and
encoder-decoder readers both need to process many passages, which is the
computation bottleneck. Previous solutions (Cao et al., 2020; Lee et al.,
2021) precompute the passage representations to avoid runtime computation but
come with large amounts of storage costs (e.g. terabytes of storage for
Wikipedia scale corpus). BTR tackles the challenge by building compact binary
token representations for the passages.

[width=0.95]fig/arch-v3.pdf

Figure 2: BTR reader architecture, where light blue color indicates the model
from prior work (based on T5 (Raffel et al., 2020) and FiD (Izacard & Grave,
2021), and green indicates our methods. We create cacheable calibrated binary
token representations for retrieved passages in the reader encoder to speed up
inference. Additionally, we compress the precomputed binary token
presentations offline to reduce storage costs. We further reduce inference
computation by runtime compression for the encoder and decoder.

#### Overview.

Figure 2 summarizes the BTR reader architecture and how our techniques are
applied to each component. The key idea in BTR is to create cacheable binary
token representations (§3.1) of the retrieved passages such that the passage
encoding can be precomputed offline and stored in a compact format. We build
on the previous technique (Cao et al., 2020) to decompose the passage and
query computation in the lower layers of the reader encoder and jointly
process the query and passage representations back in the upper layers.
However, unlike them, we create calibrated binary passage representations
after the decomposition to drastically reduce storage. We further develop
offline compression to reduce the storage of these precomputed binary token
representations. Such binarization and decomposition incur task performance
degradation, which we address by designing two regularization techniques
during training (§3.2). For inference, we develop runtime compression
techniques (§3.3) to further speed up the reader computation.

###  3.1 Binary Token Representations for Retrieved Passages

Our goal is to produce binary representations for the retrieved passages while
maintaining downstream task accuracy. We binarize passage representations at
the token level. Specifically, given a continuous passage token vector
$\mathbf{h}_{k}=[h_{1},h_{2},\cdots,h_{d}]$ ($d$ is dimension) at the $k$th
layer of the reader encoder, we hash $\mathbf{h}_{k}$ via the
$\operatorname{sign}$ function to obtain the binary representation vector
$\mathbf{b}_{k}=\operatorname{sign}(\mathbf{h}_{k})$, where ${b}_{i}$ is $1$
if ${h}_{i}>0$ and $-1$ otherwise. We use a differentiable $\tanh$ function to
approximate the non-differentiable sign function (Cao et al., 2017).

Prior work (Yamada et al., 2021) binarized passage representations for
retrieval tasks through an annealing process, i.e.,
$\tilde{\mathbf{b}}=\tanh(\beta\mathbf{h})$, where $\beta$ is a scaling factor
that anneals to infinity to approximate the $\operatorname{sign}$ function.
However, we find that directly converting the continuous float values into
discrete binary values with annealing decreases the representation quality.
The problem is that the float vector values often have large scales (e.g.,
ranging from -500 to +300) which causes the $\tanh$ function to collapse into
-1 and +1 quickly, this is partially due to the pre-layernorm Xiong et al.
(2020) nature of the encoder-decoder architectures like T5. Most recent models
like GPT-3 Brown et al. (2020a) and LLaMA Touvron et al. (2023b; a) also use
pre-layernorm. A naive fix is to introduce a normalization layer (e.g.
layernorm) before the binarization, but then the scale of normalized values
does not match the input passage presentations in the upper encoder layers and
we empirically notice a larger drop in performance.

#### Calibrated binarization.

We introduce a calibration technique that makes two modifications to the pre-
layernorm architecture.111Not necessarily needed for models with post-
layernorm such as BERT. First, instead of applying the binarization after the
Transformer encoder layer as in the previous work (Shen et al., 2019; Yamada
et al., 2021), we insert the binarization after the layernorm layer (but
before the multihead attention layer) inside the Transformer encoder layer as
shown in Figure 2. We also save the variance of all passage token
representations which comes with negligible storage costs222It requires $1/d$
storage of the passage vector. $d$ is usually several hundred or thousand like
768 or 1024.. Using the saved variance information along with the layernorm
weights, we could recover the passage representations to their original scales
(by dividing the product of variance and layernorm weights). Second, during
training, instead of annealing the $\tanh$ function, we adopt a straight-
through estimatior (Bengio et al., 2013) for the binarization, the forward
pass of encoding still uses discrete binary values while the backward
propagation uses the $\tanh$ function to provide the gradients. These two key
changes make the binarization procedure better calibrated and help retain the
representation quality after binarization.

#### Offline compression.

The binary representations for the passage tokens are amenable to further
compression due to _context redundancy_. This redundancy originates from the
passage corpus, where each token can occur millions of times in different
contexts even though many of them have similar semantic information. This is
especially the case for tokens that form stopwords. We design offline token
compression that aims to reduce such redundancy such that we do not need to
store its representations every time it appears in a different context (in our
case, the context is a retrieved passage). For a given token $t$ in the reader
model’s vocabulary, we find all binary representations $T$ from the corpus. If
the token $t$ is a stopword $t_{s}$, then we compute the mean vector values
$\mathbf{b}_{s}$ for all the tokens in $T$. Otherwise, we merge
$r_{o}$%333$r_{o}$% is 100% for stopword token representation since stopwords
are less contextual than other tokens. of the binary token representations
$\mathbf{b}_{v}$ for the token $t_{v}$ based on their semantic similarity. We
use a bipartite merging (Bolya et al., 2022) algorithm and measure the
semantic similarity using the Hamming distance. We find this more efficient
than a clustering method as they require more iterations and do not easily
scale to billions of tokens. Details are provided in LABEL:algo:offline in
Section A.1. Once we compress the binary token representations, we save them
in a key-value data store for fast runtime lookup.

###  3.2 BTR Training

Binarization and decomposition provide efficiency benefits but come with
performance degradation for downstream tasks. We describe how we train BTR in
three steps to mitigate accuracy drops.

  * •

Step 1. We first train a reader model without any decomposition or
binarization. The training objective is the task loss
$\mathcal{L}_{\text{task}}$ using cross entropy between prediction logits and
task labels.

  * •

Step 2. We then train a decomposed (no binarization) model with the reader
model from step 1 as the teacher using _query-aware passage token
distillation_ loss $\mathcal{L}_{\text{distill}}$ and the original task loss
$\mathcal{L}_{\text{task}}$ (described below).

  * •

Step 3. Finally, we train a decomposed reader model by applying BTR
binarization in the reader encoder, where the model weights are initialized
from the distilled decomposed reader model in the second step. We add a
_passage representation recovery_ loss $\mathcal{L}_{recovery}$ to the
original task loss $\mathcal{L}_{\text{task}}$ (described below).

#### Query-Aware passage token distillation.

Passage representation regularization from the original (not decomposed) model
has shown to be helpful in reducing information loss caused by query and
passage decomposition (Cao et al., 2020). We empirically find that the direct
application of this distillation does not reduce information loss for a
retrieval-augmented LM. This is likely because prior work only considers a
single passage where all tokens are important to the task, whereas in our
setting the reader retrieves many passages that may contain more redundant
token information which are not equally effective in regularization.

To address this issue, we design a query-aware passage token distillation loss
to improve the decomposed passage representation quality. We only distill the
passage tokens that are semantically relevant (salient) to the query from the
original (non-decomposed) model. We obtain top-$r$444We set $r$ to 50% of
total passage tokens by default. passage tokens using the query to passage
attention scores.
$\mathcal{L}_{\text{distill}}=\frac{1}{r}\sum_{i=1}^{r}(h_{i}-h_{i}^{\text{decomposed}})^{2}$,
where $h_{i}^{\text{decomposed}}$ is the decomposed passage representations.
The second step training loss is:
$\mathcal{L}_{\text{task}}+\mathcal{L}_{\text{distill}}$.

#### Passage representation recovery.

The end-to-end training objectives do not explicitly encourage the binary
tokens representations to maintain semantic information in the continuous
representations before binarization. We add a representation recovery loss
(Shen et al., 2019) to the second-stage training task objective. This
objective directly provides supervision signals for the binary representations
to retain the semantics of continuous representations. Specifically, we first
add a linear projection layer on top of the binary passage representations
$\mathbf{b}_{k}$; then we use the mean square error as the recovery loss
between the projected representations and original passage representations
$\mathbf{h}_{k}$ before the binarization ($k$th layer in the reader encoder):
$\mathcal{L}_{recovery}=\frac{1}{d}\sum_{i=1}^{d}(h_{i}-b_{i})^{2}$ As we will
show in §4.4, passage recovery loss helps improve the quality of binary
representations and reduce the accuracy gap. The third step training loss is
$\mathcal{L}_{\text{task}}+\mathcal{L}_{recovery}$.

###  3.3 BTR Inference

During inference, given an input query and retrieved passages, BTR reader
first computes query representations (continuous float-point vectors) on the
fly in the encoder (layer 1 to $k$), then it looks up the precomputed binary
token representations (from layer $k$) for the retrieved passages from the
data store. Next, BTR reader converts the loaded binary token representations
into continuous float-point vectors555values are -1.0 and 1.0.) and
concatenates them with query representations before layer $k+1$. Then from
layer $k+1$ to layer $n$ in the reader encoder, BTR applies _runtime
compression_ (described below) over the concatenated query-passage
representations to reduce the number of tokens and further speed up the
encoder inference. Once the encoder finishes computation, the reader flattens
and concatenates all the query-passage representations, and then feeds them
into the reader decoder. The reader decoder applies similar runtime
compression operations to shorten the concatenated text sequence with query
and all passage tokens.

#### Runtime compression.

Runtime compression is possible because the retrieved passages are relevant to
the query and contain similar information for different passages. The runtime
token compression consists of intra-passage and cross-passage compression
steps. At the upper layers ($k+1$ to $n$) in the reader encoder, the query
representations are concatenated with representations of each passage, and the
query-passage representations are processed together. We compress the token
representations of each query-passage pair and call this process intra-passage
token compression since the encoder still computes each query-passage pair
representation in parallel. After the encoder computation, all the query-
passage representations are flattened and concatenated. In the reader decoder,
we further compress the resulting representations across all passages (and the
query) for every $g$ layer666We set $g$ to be 3 as default. We do not merge in
every layer as in the upper part of the encoder because the decoder has more
layers, skipping compression for a few layers provides a balance between
efficiency and accuracy. and call this cross-passage token compression. We use
a similar compression algorithm as in the offline token compression, merging
$r_{p}$% tokens based on their semantic similarity. The difference here is
that the representations are continuous vectors in the upper encoder and the
decoder, so we change the similarity metric to cosine distance accordingly. We
describe the details in Section A.1 in Section A.1.

##  4 Evaluation

We first describe BTR and baselines, followed by five knowledge-rich NLP tasks
to evaluate them. We then report the main results of BTR on task performance
and efficiency gains. We also evaluate the proposed techniques in BTR and
their impacts on efficiency and performance trade-offs.

###  4.1 Baselines

We apply BTR to Atlas Izacard et al. (2022b) base and large variants and call
them BTR-Atlas base and BTR-Atlas large. Atlas is a recent state-of-the-art
retrieval augmented language model. The Atlas reader uses the T5-based Raffel
et al. (2020) Funsion-in-Decoder (FiD) Izacard & Grave (2021) architecture. We
include more implementation details in Section A.2.

#### Baselines.

To compare task performance and efficiency with BTR, we evaluate five
representative baselines (implementation details are in Section A.3):

(1) Atlas (Izacard et al., 2022b) is a state-of-the-art retrieval augmented
language model for knowledge-rich NLP tasks. Due to computing budget
constraints, we compare the base (with 220M parameters) and large (770M
parameters) size variants.

(2) Atlas-Q is a quantized version of the Atlas base model. We use GTPQ
(Frantar et al., 2023) to quantize the fine-tuned Atlas baseline model in
4bit.

(3) DensePhrase (Lee et al., 2021) creates dense phrase representations of
passages. It retrieves answers from the phrase index without using the
retrieve-and-read pipeline and achieves high query processing throughput.

(4) DeFormer (Cao et al., 2020) speeds up the inference in encoder-only reader
models by decomposing the passage and query encoding and caching the
continuous passage representations. We apply DeFormer over Atlas-base and
fine-tune the decomposed model.

(5) LLaMA2 (Touvron et al., 2023b) consists of open-source large language
models that achieve top performance on many NLP benchmarks including the
knowledge tasks we study. Since the few-shot versions still lag behind fine-
tuned models, we finetune the LLaMA2-7B model using the LoRA (Hu et al., 2021)
adapter and report its results on the evaluation tasks.

###  4.2 Tasks and Metrics

We evaluate BTR and baselines on three open-domain QA tasks: NaturalQuestions
(NQ, Kwiatkowski et al. (2019), TriviaQA (TQA, Joshi et al. (2017)),
WebQuestions (WQ, Berant et al. (2013)); one fact-checking task: FEVER (Thorne
et al., 2018), and one knowledge-intensive reasoning benchmark: the mass-
multitask language understanding (MMLU) dataset (Hendrycks et al., 2020).
Dataset details are in Section A.4. We use the same Wikipedia corpus (dumped
from December 2018) for all tasks and compared systems for consistency. The
corpus contains 32.1 million passages, roughly over 3.2 billion tokens
assuming 100 tokens per passage.

#### Evaluation metrics.

We use the exact match score (EM) as the metric for the open-domain QA tasks.
We measure the accuracy of the fact checking task and the MMLU benchmark. For
all tasks and models, we choose the model checkpoint based on the development
set and report the metrics on the test set. All the numbers are average values
across 5 different runs (with different random seeds).

#### Efficiency measurements.

For each task and model, we randomly sample 100 queries from the test dataset
and measure the real inference throughput as the number of queries processed
per second (QPS) of the compared models on the A100 GPU hardware. Actual
throughput reflects a more realistic comparison of efficiency across different
systems.

###  4.3 Main Results

Table 1: Task performance and inference efficiency comparison between the baseline models and BTR-Atlas over five evaluation tasks. ‘Sp’ denotes the speed up over the Atlas base model, and the subscript percentage numbers in brackets are relative performance compared to the Atlas base model. The speed up and percentage for BTR-Atlas large is over the Atlas large model. BTR achieves 2–3x inference speedup while maintaining $>$ 95% of the original models’ performance. | NQ | TQA | WQ | FEVER | MMLU
---|---|---|---|---|---
| EM |  | Sp | EM |  | Sp | EM |  | Sp | Acc |  | Sp | Acc |  | Sp
Atlas base | 52.1 |  | 1.0 | 69.3 |  | 1.0 | 46.4 |  | 1.0 | 72.9 |  | 1.0 | 38.6 |  | 1.0
Atlas-Q | 51.8 | (99%) | 1.2 | 68.5 | (99%) | 1.3 | 45.1 | (97%) | 1.1 | 70.4 | (97%) | 1.1 | 37.8 | (98%) | 1.2
DeFormer | 51.4 | (99%) | 2.2 | 68.0 | (98%) | 2.0 | 44.8 | (97%) | 2.0 | 71.8 | (98%) | 2.3 | 33.9 | (88%) | 1.8
DensePhrase | 40.9 | (79%) | 4.9 | 53.6 | (77%) | 5.8 | 37.5 | (81%) | 5.1 | - |  | - | - |  | -
LLAMA2-7B | 47.8 | (92%) | 0.1 | 74.3 | (108%) | 0.1 | 51.2 | (110%) | 0.1 | 76.3 | (105%) | 0.1 | 51.2 | (133%) | 0.1
BTR-Atlas base | 49.5 | (95%) | 3.1 | 66.7 | (96%) | 2.5 | 43.8 | (94%) | 2.6 | 70.2 | (96%) | 3.1 | 35.4 | (92%) | 2.6
Atlas large | 58.3 |  | 1.0 | 73.6 |  | 1.0 | 51.5 |  | 1.0 | 78.2 |  | 1.0 | 41.1 |  | 1.0
BTR-Atlas large | 56.1 | (96%) | 4.0 | 70.8 | (96%) | 3.9 | 49.1 | (95%) | 3.6 | 75.9 | (97%) | 4.1 | 39.2 | (95%) | 2.5

[width=]fig/baseline-nq.pdf

(a) NaturalQuestions

[width=]fig/baseline-tqa.pdf

(b) TriviaQA

[width=]fig/baseline-wq.pdf

(c) WebQuestions

Figure 3: Task performance and inference efficiency (throughput and storage)
visualization across the baselines and BTR fine-tuned models on three open-
domain QA datasets. The area of the circle denotes storage size (we scale the
area size of BTR-base and DensePhrase by 10 for clear display). A top-right
smaller circle is better.

#### BTR is more accurate and efficient than other baseline methods.

Table 1 presents the accuracy, storage versus inference throughput trade-offs
for BTR, DeFormer, DensePhrase, Atlas-Q, and LLaMA2-7B models on the
evaluation datasets. Atlas-Q and LLaMA-7B provide high accuracy but with very
low inference throughput. DensePhrase achieves the highest throughput, but
comes with much lower accuracy numbers ($>6$% gap); DeFormer has similar
inference throughput and slightly higher accuracy than BTR but its storage
overhead is two orders of magnitude larger. Across all models compared, BTR
presents better efficiency versus accuracy trade-offs by maintaining high
accuracy and inference throughput with a smaller storage footprint. Figure 3
visualizes the trade-offs on the three open QA datasets.

Furthermore, BTR is more scalable than DeFormer and DensePhrase. We estimate
that using a much larger corpus like CCNet (Wenzek et al., 2020) with over 350
million passages will take up 1389 GB using similar compression ratios for the
Wikipedia corpus. However, for baseline models, the DeFormer will spend over
100TB of storage and the DensePhrase will occupy over 3TB of storage.

Table 2: Inference throughput and accuracy for applying binary representations to BERT-base reader model on three open QA datasets. | NQ | TQA | WQ
---|---|---|---
| EM |  | Sp | EM |  | Sp | EM |  | Sp
BERT base | 42.9 |  | 1.0 | 57.1 |  | 1.0 | 43.1 |  | 1.0
BTR-BERT base | 39.8 | (93%) | 3.4 | 54.1 | (95%) | 3.9 | 39.7 | (92%) | 3.2

#### BTR remains effective for encoder-only models.

We study binary passage token representations for encoder-based models and
validate their effectiveness and inference benefits. Specifically, we apply
the token-level binarization technique in §3.1 for the BERT-base model with
DPR (Karpukhin et al., 2020) as the passage retriever. We do not apply scale-
aware modifications since the BERT model is a post-layernorm architecture.
Note that encoder models expect the answer predictions to be exact spans from
the retrieved passages, therefore, our runtime token compression techniques do
not apply since we cannot recover the original exact spans once the tokens are
compressed. Offline binary token compression remains applicable and reduces
storage footprint. Implementation details are in Section A.2. Table 2 shows
the results of the BERT reader model on three open QA datasets, applying
binary representations also effectively improves the inference throughput by
over 3x while maintaining over 92% accuracy.

###  4.4 Ablation Study

#### Each component in BTR provides either efficiency or accuracy gains.

We study the effects of each component in BTR on the inference efficiency and
accuracy using the NaturalQuestions dataset. BTR consists of four efficiency
components that improve either inference throughput or storage footprint and
two training components that improve accuracy. The efficiency components
include (i) binary passage representations; (ii) offline token merging; (iii)
runtime intra-passage token compression; and (iv) runtime cross-passage token
compression. The accuracy components are (v) passage representation recovery
and (vi) query-aware passage token distillation.

Table 3: Ablation analysis for each component in BTR on the NaturalQuestions
dataset.

| Accuracy | Throughput | Storage
---|---|---|---
(%) $\uparrow$ | (QPS) $\uparrow$ | (GB) $\downarrow$
| Atlas base | 52.1 | 10.2 | 0
1-5 |  BTR-Atlas base | 49.5 | 31.5 | 127
efficiency $\Bigg{\\{}$ | w/o binary passage representations | 50.8 (+1.3) | 32.3 | 12,804
w/o offline compression | 49.8 (+0.3) | 31.5 | 159
w/o runtime intra-passage compression | 50.0 (+0.5) | 28.1 | 127
w/o runtime cross-passage compression | 49.9 (+0.4) | 24.6 | 127
accuracy $\Big{\\{}$ | w/o passage representation recovery | 47.4 (-2.1) | 31.5 | 127
w/o query-aware passage token distillation | 48.2 (-1.3) | 31.5 | 127

Section 4.4 shows the efficiency techniques in BTR come with the price of task
accuracy degradation, however the two accuracy components during training
effectively mitigate such accuracy drop. Specifically, the binary passage
representations dramatically reduce the storage by over 100x, and the offline
token compression further reduces the footprint by 20%. On the other hand, the
two online token compression techniques improve the inference throughput by
over 30% without sacrificing too much accuracy drop. Overall, the techniques
in BTR collectively provide efficiency gains without compromising task
accuracy too much.

[width=]fig/storage-accuracy.pdf

(d) Offline token compression

[width=]fig/throughput-accuracy.pdf

(e) Runtime token compression

Figure 4: Accuracy, storage, and throughput comparisons for different two-
stage token compression ratios on the NaturalQuestions dataset. To achieve a
good balance between accuracy, storage, and throughput in BTR, we choose a
compression ratio of 0.2 for both online and offline token compression.
Detailed numbers are in Table 7 in Section A.6.

#### Effects of token compression ratios in BTR.

Figure 4 shows the effects of the two-stage token compression technique in BTR
under different compression ratios. We choose the compression ratio from 5% to
50%777Compression ratios bigger than 50% cause significant accuracy drops.
with a gap of 5% and report the accuracy and storage or throughput numbers for
the NaturalQuestions dataset. For offline token compression, with bigger
compression ratios, BTR achieves linear storage cost reduction but the
accuracy does not drop significantly until the ratio is bigger than 0.2
(default for BTR). We also observe that for online token compression, the
inference throughput consistently improves with higher compression ratios,
while the accuracy degradation is relatively small until the ratio is larger
than 0.2. By configuring different compression ratios, BTR allows flexible
inference throughput, storage, and accuracy trade-offs during inference
without additional training efforts.

##  5 Conclusion and Future Work

Retrieval-augmented language models present viable solutions to address issues
like hallucinations in large language models, but their inference is slow
because the reader component needs to process many passages. We introduce BTR,
a system that creates cacheable binary token representations to improve the
inference and storage efficiency for the reader in retrieval-augmented
language models. Together with training regularization techniques and token
compression methods, BTR effectively reduces the storage costs by 100x,
improves inference throughput by 2$\sim$4x, and maintains performance for a
wide range of knowledge-intensive tasks.

We discuss directions for future work. 1) Extending BTR to decoder-only
readers is non-trivia because decoder models compute passage representations
together with the query in a sequential manner, making it challenging to break
computational dependencies and cache passage representations. Moreover, the
KV-Caches in decoder models speed up the inference decoding, but storing their
binary representation causes much more storage than encoder models. 2)
Improving BTR for extremely long input queries remains challenging and
requires other orthogonal efficient methods. BTR can speed up the inference
when queries are longer, but the speed-up is relatively smaller than shorter
queries. 3) Scaling BTR for larger models with bigger representation sizes is
another important research topic. Potential solutions might include using
autoencoders to compress the dimension of representations. 4) It will also be
interesting to apply binary token representations to the retriever and
incorporate BTR into model pretraining for building better and faster
retrieval-augmented language models.

## Acknowledgements

This research was supported partly by NSF IIS-2044660, an Allen Investigator
Distinguished award. We thank the members of the UW NLP group for their
comments and feedback on this paper.

## References

  * Bai et al. (2021) Haoli Bai, Wei Zhang, Lu Hou, Lifeng Shang, Jin Jin, Xin Jiang, Qun Liu, Michael Lyu, and Irwin King.  BinaryBERT: Pushing the Limit of BERT Quantization.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pp. 4334–4348, Online, August 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.acl-long.334.  URL https://aclanthology.org/2021.acl-long.334.
  * Bengio et al. (2013) Yoshua Bengio, Nicholas Léonard, and Aaron Courville.  Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation, August 2013.  URL http://arxiv.org/abs/1308.3432.
  * Berant et al. (2013) Jonathan Berant, Andrew Chou, Roy Frostig, and Percy Liang.  Semantic Parsing on Freebase from Question-Answer Pairs.  In _Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing_ , pp. 1533–1544, Seattle, Washington, USA, October 2013. Association for Computational Linguistics.  URL https://aclanthology.org/D13-1160.
  * Bolya et al. (2022) Daniel Bolya, Cheng-Yang Fu, Xiaoliang Dai, Peizhao Zhang, Christoph Feichtenhofer, and Judy Hoffman.  Token Merging: Your ViT But Faster.  In _The Eleventh International Conference on Learning Representations_ , September 2022.  URL https://openreview.net/forum?id=JroZRaRw7Eu.
  * Borgeaud et al. (2022) Sebastian Borgeaud, Arthur Mensch, Jordan Hoffmann, Trevor Cai, Eliza Rutherford, Katie Millican, George Bm Van Den Driessche, Jean-Baptiste Lespiau, Bogdan Damoc, Aidan Clark, Diego De Las Casas, Aurelia Guy, Jacob Menick, Roman Ring, Tom Hennigan, Saffron Huang, Loren Maggiore, Chris Jones, Albin Cassirer, Andy Brock, Michela Paganini, Geoffrey Irving, Oriol Vinyals, Simon Osindero, Karen Simonyan, Jack Rae, Erich Elsen, and Laurent Sifre.  Improving Language Models by Retrieving from Trillions of Tokens.  In _Proceedings of the 39th International Conference on Machine Learning_ , pp. 2206–2240. PMLR, June 2022.  URL https://proceedings.mlr.press/v162/borgeaud22a.html.
  * Brown et al. (2020a) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language Models are Few-Shot Learners.  In _Advances in Neural Information Processing Systems_ , volume 33, pp. 1877–1901. Curran Associates, Inc., 2020a.  URL https://papers.nips.cc/paper/2020/hash/1457c0d6bfcb4967418bfb8ac142f64a-Abstract.html.
  * Brown et al. (2020b) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language Models are Few-Shot Learners.  _arXiv:2005.14165 [cs]_ , July 2020b.  URL http://arxiv.org/abs/2005.14165.
  * Cao et al. (2020) Qingqing Cao, Harsh Trivedi, Aruna Balasubramanian, and Niranjan Balasubramanian.  DeFormer: Decomposing Pre-trained Transformers for Faster Question Answering.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pp. 4487–4497, Online, July 2020. Association for Computational Linguistics.  doi: 10.18653/v1/2020.acl-main.411.  URL https://www.aclweb.org/anthology/2020.acl-main.411.
  * Cao et al. (2017) Zhangjie Cao, Mingsheng Long, Jianmin Wang, and Philip S. Yu.  HashNet: Deep Learning to Hash by Continuation.  In _2017 IEEE International Conference on Computer Vision (ICCV)_ , pp. 5609–5618, October 2017.  doi: 10.1109/ICCV.2017.598.
  * de Jong et al. (2022) Michiel de Jong, Yury Zemlyanskiy, Joshua Ainslie, Nicholas FitzGerald, Sumit Sanghai, Fei Sha, and William Cohen.  FiDO: Fusion-in-Decoder optimized for stronger performance and faster inference, December 2022.  URL http://arxiv.org/abs/2212.08153.
  * de Jong et al. (2023) Michiel de Jong, Yury Zemlyanskiy, Nicholas FitzGerald, Joshua Ainslie, Sumit Sanghai, Fei Sha, and William Cohen.  Pre-computed memory or on-the-fly encoding? A hybrid approach to retrieval augmentation makes the most of your compute, January 2023.  URL http://arxiv.org/abs/2301.10448.
  * Dettmers et al. (2022) Tim Dettmers, Mike Lewis, Younes Belkada, and Luke Zettlemoyer.  LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scale, August 2022.  URL http://arxiv.org/abs/2208.07339.
  * Dettmers et al. (2023) Tim Dettmers, Artidoro Pagnoni, Ari Holtzman, and Luke Zettlemoyer.  QLoRA: Efficient Finetuning of Quantized LLMs, May 2023.  URL http://arxiv.org/abs/2305.14314.
  * Frantar et al. (2022) Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh.  GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers, October 2022.  URL http://arxiv.org/abs/2210.17323.
  * Frantar et al. (2023) Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh.  GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers, March 2023.  URL http://arxiv.org/abs/2210.17323.
  * Guu et al. (2020) Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Mingwei Chang.  Retrieval Augmented Language Model Pre-Training.  In _Proceedings of the 37th International Conference on Machine Learning_ , pp. 3929–3938. PMLR, November 2020.  URL https://proceedings.mlr.press/v119/guu20a.html.
  * Hendrycks et al. (2020) Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt.  Measuring Massive Multitask Language Understanding.  In _International Conference on Learning Representations_ , October 2020.  URL https://openreview.net/forum?id=d7KBjmI3GmQ.
  * Hofstätter et al. (2022) Sebastian Hofstätter, Jiecao Chen, Karthik Raman, and Hamed Zamani.  FiD-Light: Efficient and Effective Retrieval-Augmented Text Generation, September 2022.  URL http://arxiv.org/abs/2209.14290.
  * Hu et al. (2021) Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen.  LoRA: Low-Rank Adaptation of Large Language Models.  In _International Conference on Learning Representations_ , October 2021.  URL https://openreview.net/forum?id=nZeVKeeFYf9.
  * Huang et al. (2022) Jie Huang, Hanyin Shao, and Kevin Chen-Chuan Chang.  Are Large Pre-Trained Language Models Leaking Your Personal Information?, October 2022.  URL http://arxiv.org/abs/2205.12628.
  * Huang et al. (2019) Long-Kai Huang, Jianda Chen, and Sinno Pan.  Accelerate Learning of Deep Hashing With Gradient Attention.  In _2019 IEEE/CVF International Conference on Computer Vision (ICCV)_ , pp. 5270–5279, October 2019.  doi: 10.1109/ICCV.2019.00537.
  * Izacard & Grave (2021) Gautier Izacard and Edouard Grave.  Leveraging Passage Retrieval with Generative Models for Open Domain Question Answering.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_ , pp. 874–880, Online, April 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.eacl-main.74.  URL https://aclanthology.org/2021.eacl-main.74.
  * Izacard et al. (2022a) Gautier Izacard, Mathilde Caron, Lucas Hosseini, Sebastian Riedel, Piotr Bojanowski, Armand Joulin, and Edouard Grave.  Unsupervised Dense Information Retrieval with Contrastive Learning.  _Transactions on Machine Learning Research_ , May 2022a.  ISSN 2835-8856.  URL https://openreview.net/forum?id=jKN1pXi7b0.
  * Izacard et al. (2022b) Gautier Izacard, Patrick Lewis, Maria Lomeli, Lucas Hosseini, Fabio Petroni, Timo Schick, Jane Dwivedi-Yu, Armand Joulin, Sebastian Riedel, and Edouard Grave.  Atlas: Few-shot Learning with Retrieval Augmented Language Models, November 2022b.  URL http://arxiv.org/abs/2208.03299.
  * Jain et al. (2017) Himalaya Jain, Joaquin Zepeda, Patrick Perez, and Remi Gribonval.  SUBIC: A Supervised, Structured Binary Code for Image Search.  In _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , pp. 833–842, 2017.  URL https://openaccess.thecvf.com/content_iccv_2017/html/Jain_SUBIC_A_Supervised_ICCV_2017_paper.html.
  * Joshi et al. (2017) Mandar Joshi, Eunsol Choi, Daniel Weld, and Luke Zettlemoyer.  TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 1601–1611, Vancouver, Canada, July 2017. Association for Computational Linguistics.  doi: 10.18653/v1/P17-1147.  URL https://aclanthology.org/P17-1147.
  * Karpukhin et al. (2020) Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih.  Dense Passage Retrieval for Open-Domain Question Answering.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pp. 6769–6781, Online, November 2020. Association for Computational Linguistics.  doi: 10.18653/v1/2020.emnlp-main.550.  URL https://aclanthology.org/2020.emnlp-main.550.
  * Kwiatkowski et al. (2019) Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, Kristina Toutanova, Llion Jones, Matthew Kelcey, Ming-Wei Chang, Andrew M. Dai, Jakob Uszkoreit, Quoc Le, and Slav Petrov.  Natural Questions: A Benchmark for Question Answering Research.  _Transactions of the Association for Computational Linguistics_ , 7:453–466, August 2019.  doi: 10.1162/tacl_a_00276.  URL https://doi.org/10.1162/tacl_a_00276.
  * Lee et al. (2021) Jinhyuk Lee, Mujeen Sung, Jaewoo Kang, and Danqi Chen.  Learning Dense Representations of Phrases at Scale.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pp. 6634–6647, Online, August 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.acl-long.518.  URL https://aclanthology.org/2021.acl-long.518.
  * Lewis et al. (2020) Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela.  Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks.  In _Advances in Neural Information Processing Systems_ , volume 33, pp. 9459–9474. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/hash/6b493230205f780e1bc26945df7481e5-Abstract.html.
  * Liu et al. (2016) Haomiao Liu, Ruiping Wang, Shiguang Shan, and Xilin Chen.  Deep Supervised Hashing for Fast Image Retrieval.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 2064–2072, 2016.  URL https://openaccess.thecvf.com/content_cvpr_2016/html/Liu_Deep_Supervised_Hashing_CVPR_2016_paper.html.
  * Mallen et al. (2023) Alex Mallen, Akari Asai, Victor Zhong, Rajarshi Das, Daniel Khashabi, and Hannaneh Hajishirzi.  When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non-Parametric Memories, May 2023.  URL http://arxiv.org/abs/2212.10511.
  * Mangrulkar et al. (2022) Sourab Mangrulkar, Sylvain Gugger, Lysandre Debut, Younes Belkada, and Sayak Paul.  Peft: State-of-the-art parameter-efficient fine-tuning methods.  Hugging Face, September 2022.  URL https://github.com/huggingface/peft.
  * Min et al. (2023) Sewon Min, Weijia Shi, Mike Lewis, Xilun Chen, Wen-tau Yih, Hannaneh Hajishirzi, and Luke Zettlemoyer.  Nonparametric Masked Language Modeling, May 2023.  URL http://arxiv.org/abs/2212.01349.
  * Mündler et al. (2023) Niels Mündler, Jingxuan He, Slobodan Jenko, and Martin Vechev.  Self-contradictory Hallucinations of Large Language Models: Evaluation, Detection and Mitigation, May 2023.  URL http://arxiv.org/abs/2305.15852.
  * Qin et al. (2022) Haotong Qin, Yifu Ding, Mingyuan Zhang, Qinghua Yan, Aishan Liu, Qingqing Dang, Ziwei Liu, and Xianglong Liu.  BiBERT: Accurate Fully Binarized BERT.  In _International Conference on Learning Representations_ , March 2022\.  URL https://openreview.net/forum?id=5xEgrl_5FAJ.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu.  Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer.  _Journal of Machine Learning Research_ , 21(140):1–67, 2020.  ISSN 1533-7928.  URL http://jmlr.org/papers/v21/20-074.html.
  * Shen et al. (2019) Dinghan Shen, Pengyu Cheng, Dhanasekar Sundararaman, Xinyuan Zhang, Qian Yang, Meng Tang, Asli Celikyilmaz, and Lawrence Carin.  Learning Compressed Sentence Representations for On-Device Text Processing.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pp. 107–116, Florence, Italy, July 2019. Association for Computational Linguistics.  doi: 10.18653/v1/P19-1011.  URL https://aclanthology.org/P19-1011.
  * Shi et al. (2023) Weijia Shi, Sewon Min, Michihiro Yasunaga, Minjoon Seo, Rich James, Mike Lewis, Luke Zettlemoyer, and Wen-tau Yih.  REPLUG: Retrieval-Augmented Black-Box Language Models, May 2023.  URL http://arxiv.org/abs/2301.12652.
  * Thorne et al. (2018) James Thorne, Andreas Vlachos, Christos Christodoulopoulos, and Arpit Mittal.  FEVER: a Large-scale Dataset for Fact Extraction and VERification.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pp. 809–819, New Orleans, Louisiana, June 2018. Association for Computational Linguistics.  doi: 10.18653/v1/N18-1074.  URL https://aclanthology.org/N18-1074.
  * Tissier et al. (2019) Julien Tissier, Christophe Gravier, and Amaury Habrard.  Near-lossless binarization of word embeddings.  In _Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence_ , AAAI’19/IAAI’19/EAAI’19, pp. 7104–7111, Honolulu, Hawaii, USA, January 2019. AAAI Press.  ISBN 978-1-57735-809-1.  doi: 10.1609/aaai.v33i01.33017104.  URL https://dl.acm.org/doi/10.1609/aaai.v33i01.33017104.
  * Touvron et al. (2023a) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample.  LLaMA: Open and Efficient Foundation Language Models, February 2023a.  URL http://arxiv.org/abs/2302.13971.
  * Touvron et al. (2023b) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom.  Llama 2: Open Foundation and Fine-Tuned Chat Models, July 2023b.  URL http://arxiv.org/abs/2307.09288.
  * Wenzek et al. (2020) Guillaume Wenzek, Marie-Anne Lachaux, Alexis Conneau, Vishrav Chaudhary, Francisco Guzmán, Armand Joulin, and Edouard Grave.  CCNet: Extracting high quality monolingual datasets from web crawl data.  In _Proceedings of the Twelfth Language Resources and Evaluation Conference_ , pp. 4003–4012, Marseille, France, May 2020. European Language Resources Association.  ISBN 979-10-95546-34-4.  URL https://aclanthology.org/2020.lrec-1.494.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pp. 38–45, Online, October 2020. Association for Computational Linguistics.  URL https://www.aclweb.org/anthology/2020.emnlp-demos.6.
  * Xiao et al. (2023) Guangxuan Xiao, Ji Lin, Mickael Seznec, Hao Wu, Julien Demouth, and Song Han.  SmoothQuant: Accurate and Efficient Post-Training Quantization for Large Language Models, February 2023.  URL http://arxiv.org/abs/2211.10438.
  * Xiong et al. (2020) Ruibin Xiong, Yunchang Yang, Di He, Kai Zheng, Shuxin Zheng, Chen Xing, Huishuai Zhang, Yanyan Lan, Liwei Wang, and Tieyan Liu.  On Layer Normalization in the Transformer Architecture.  In _Proceedings of the 37th International Conference on Machine Learning_ , pp. 10524–10533. PMLR, November 2020.  URL https://proceedings.mlr.press/v119/xiong20b.html.
  * Yamada et al. (2021) Ikuya Yamada, Akari Asai, and Hannaneh Hajishirzi.  Efficient Passage Retrieval with Hashing for Open-domain Question Answering.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 2: Short Papers)_ , pp. 979–986, Online, August 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.acl-short.123.  URL https://aclanthology.org/2021.acl-short.123.
  * Yuan et al. (2023) Zhihang Yuan, Lin Niu, Jiawei Liu, Wenyu Liu, Xinggang Wang, Yuzhang Shang, Guangyu Sun, Qiang Wu, Jiaxiang Wu, and Bingzhe Wu.  RPTQ: Reorder-based Post-training Quantization for Large Language Models, April 2023.  URL http://arxiv.org/abs/2304.01089.

##  Appendix A Appendix

###  A.1 Token compression algorithm

Output: compressed binary passage token vectors $\mathcal{B}_{c}$

1:for each stopword token $t_{s}$ in $\mathcal{V}$, do

2: collect all binary representations $\mathbf{B}_{s}$ in corpus $\mathcal{C}$

3: compute the average across all binary representations:
$\overline{\mathbf{b}}_{s}=\operatorname{sign}(\frac{1}{|\mathbf{B}_{s}|}\sum\mathbf{B}_{s})$

4:end for

5:for each token $t_{v}$ in $\mathcal{V}$ that is non-stopword, do

6: collect all binary representations $\mathcal{B}_{v}$ in corpus
$\mathcal{C}$

7: merge $\mathbf{B}_{v}$ using hamming distance $\mathcal{H}$:
$\mathcal{B}_{v}=\operatorname{sign}(\text{bipartite_merge}(\mathbf{B}_{v},r_{o},\mathcal{H}))$;

8:end for

9:

10:function bipartite_merge(input tokens: $\mathbf{B}$, merge ratio: $r$,
distance metric $\mathcal{M}$)

11: divide tokens $\mathbf{B}$ into two sets of tokens $\mathbf{B}_{i}$ and
$\mathbf{B}_{j}$ based on even and odd order

12: for each token in $\mathbf{B}_{i}$, do

13: create an token edge $e$ to its most similar token in $\mathbf{B}_{j}$
using $\mathcal{M}$

14: store token edge $e$ into $\mathbf{B}$

15: end for$\triangleright$ this is implemented as a fast parallel operation

16: Keep top-$r^{\prime}$ edges $\mathbf{E}_{r}$, where
$r^{\prime}=r|\mathbf{X}|$

17: for each token edge in $\mathbf{E}_{r}$, merge connected tokens in
$\mathbf{B}_{i}$ and $\mathbf{B}_{j}$ into $\mathbf{B}_{e}$ by computing
the average of token vectors, gather the rest unmerged tokens
$\mathbf{B}^{rest}_{i}$ and $\mathbf{B}^{rest}_{j}$ return merged tokens
$\mathbf{B}_{m}=gather(\mathbf{B}_{e},\mathbf{B}^{rest}_{i},\mathbf{B}^{rest}_{j})$

18:end function

Algorithm 2 Runtime Compression

Input: query-passage token representations $\mathbf{h}_{k}$, compression ratio
$r_{p}$

Output: merged text token representations $\mathbf{h}_{n}$

1:for each layer $\ell$ from layer $k+1$ to $n$ in the reader encoder, do

2: merge $\mathbf{h}_{\ell}$ using cosine distance $\mathcal{D}$:
$\mathbf{h}_{\ell+1}=\text{bipartite_merge}(\mathbf{h}_{\ell},r_{p},\mathcal{D})$;

3:end for$\triangleright$ intra-passage token compression

4:for each layer $d$ from layer $1$ to $n$ in the reader decoder, do

5: if $d$ % $g$ == 0 then continue end if$\triangleright$ skip merging for $g$
layers

6: merge $\mathbf{h}_{\ell}$ using cosine distance $\mathcal{D}$:
$\mathbf{h}_{\ell+1}=\text{bipartite_merge}(\mathbf{h}_{\ell},r_{p},\mathcal{D})$;

7:end for$\triangleright$ cross-passage token compression return
$\mathbf{H}_{n}$

###  A.2 Implementation Details

#### BTR Details.

We develop BTR based on the Atlas codebase using PyTorch 1.13.1 and
HuggingFace Transformers v4.18.0 (Wolf et al., 2020). We conducted training
using 4 to 8 A40 or A100 GPUs (depending on their availability on our cluster)
with BF16 mixed precision. We list the training hyperparameters in Table 4.
The decomposition layer $k$ is 9 for the BTR-Atlas base model, $k$ is 20 for
the BTR-Atlas large model, and $k$ is 9 BTR-BERT. We implemented BTR-BERT
using the original DPR (Karpukhin et al., 2020) codebase.

Table 4: Training hyperparameters for BTR-Atlas. | NQ | TQA | WQ | Fever | MMLU
---|---|---|---|---|---
Hyperparameters | base | large | base | large | base | large | base | large | base | large
batch size | 8 | 4 | 8 | 4 | 8 | 4 | 8 | 4 | 4 | 2
learning rate | 6e-5 | 6e-5 | 4e-5 | 4e-5 | 8e-5 | 8e-5 | 6e-5 | 6e-5 | 5e-5 | 5e-6
training steps | 20000 | 20000 | 20000 | 20000 | 3000 | 3000 | 10000 | 10000 | 2000 | 2000
warmup steps | 200 | 200 | 200 | 200 | 200 | 200 | 200 | 200 | 50 | 50
weight decay | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01
number of passages | 40 | 40 | 40 | 40 | 40 | 40 | 40 | 40 | 30 | 30
max query length | 40 | 40 | 64 | 64 | 40 | 40 | 40 | 40 | 256 | 256
max passage length | 320 | 320 | 320 | 320 | 320 | 320 | 320 | 320 | 320 | 320
max answer length | 32 | 32 | 32 | 32 | 32 | 32 | 32 | 32 | 32 | 32

###  A.3 Baseline Details.

Atlas (Izacard et al., 2022b) models obtain state-of-the-art performance on a
wide range of knowledge-rich NLP tasks. Atlas model retrieves passages from
the corpus using a Contriever Izacard et al. (2022a)-based retriever, which is
a BERT-like architecture with 110 million parameters shared between the query
and the passage encoder. Since our focus is on the reader component, we use
the retriever in the Atlas 11B model to obtain query-relevant passages and
fine-tune Atlas reader models with these retrieved passages. Due to computing
budget constraints, we compare the base (with 220M parameters) and large (770M
parameters) size variants. We use the original hyperparameters to finetune
Atlas.

Atlas-Q is a quantized version of Atlas. We use GTPQ (Frantar et al., 2023) to
quantize the fine-tuned Atlas baseline model in 4bit. We do not directly use
quantization-aware training such as QLoRA (Dettmers et al., 2023) since the
quantized model’s inference is much slower.

DensePhrase (Lee et al., 2021) creates dense representations of phrases from
the passages. It retrieves answers from the phrase index without using the
retrieve-and-read pipeline and achieves high query processing throughput. We
run the official DensePhrase implementation on an A100 GPU and report the
throughput numbers.

DeFormer (Cao et al., 2020) speeds up the inference in encoder-only reader
models by decomposing the passage and query encoding and caching the
continuous passage representations. We apply DeFormer over Atlas and fine-tune
the adapted model. In fact, we can view DeFormer as a simplified system from
BTR without binary representations and the offline and runtime compression
components.

LLaMA2 (Touvron et al., 2023a; b) consists of open-source large language
models that achieve top performance on many NLP benchmarks including the
knowledge tasks we study. Since the few-shot versions still lag behind fine-
tuned models, we finetune the LLaMA2-7B model using the LoRA adapter and
report its results on the evaluation tasks. Due to memory constraints, we
limit the retrieved passages to 5. We implemented this baseline using the PEFT
library (Mangrulkar et al., 2022), the LoRA config is as follows: r=8,
alpha=32, dropout=0.05, task_type="CAUSAL_LM",
target_modules=.*(q|k|v|o|gate|down|up)_proj.*, bias="none".

###  A.4 Datasets Details

Table 5: Statistics of the number of examples for the evaluation datasets. | NQ | TQA | WQ | Fever | MMLU
---|---|---|---|---|---
Train | 79168 | 78785 | 3400 | 145449 | 95127
Validation | 8757 | 8837 | 378 | 19998 | 1531
Test | 3610 | 11313 | 2032 | 19998 | 14042

Open-domain QA. We use the original open-domain variants of NaturalQuestions
(Kwiatkowski et al., 2019), TriviaQA (Joshi et al., 2017), WebQuestions
(Berant et al., 2013). The NaturalQuestions (NQ) dataset consists of natural
Google search questions that have answers from Wikipedia articles. The open-
domain variant contains 91,535 question-answer pairs (79168 for training, 8757
for development, and 3610 for testing). TriviaQA (TQA) has 98,935 quiz-style
trivia questions (78785 for training, 8837 for validation, 11313 for testing),
its unfiltered version is used for open-domain QA. The questions from
WebQuestions (WQ) are constructed from Freebase KB and Google Suggest API and
their answers are labeled by Amazon Mechanical Turk. It has 3,778 examples for
training and 2,032 for testing. We reserve 10% of the training set for
development and use the rest for training.

Fact Checking. We use the original FEVER (Thorne et al., 2018) dataset for the
fact-checking task. FEVER contains 145k training examples, and both
development and testing tests have 20k examples. Each example has a claim
sentence and a 3-class (supported, refuted, or not enough info) label. The
task requires retrieving evidence from the Wikipedia corpus and making a
judgment.

Table 6: Inference throughput numbers for the baselines and BTR-Atlas. | NQ | TQA | WQ | FEVER | MMLU
---|---|---|---|---|---
DeFormer | 22.4 | 16.7 | 18.8 | 24.6 | 9.6
DensePhrase | 50.4 | 48.5 | 48.1 | - | -
Atlas-Quant | 12.5 | 13.2 | 11.2 | 11.8 | 6.4
LLaMA-7B | 1.2 | 0.8 | 1.3 | 1.2 | 0.5
Atlas base | 10.2 | 8.4 | 9.5 | 10.5 | 5.2
BTR-Atlas base | 31.5 | 21.4 | 25.1 | 32.1 | 13.4
Atlas large | 3.8 | 2.1 | 2.2 | 3.5 | 3.3
BTR-Atlas large | 15.3 | 8.2 | 7.9 | 14.3 | 8.1

Knowledge-Intensive Reasoning. We use the mass-multitask language
understanding (MMLU) benchmark (Hendrycks et al., 2020) to evaluate the
knowledge reasoning ability of RaLMs. MMLU is a multiple-choice question-
answering dataset that has 57 subdatasets covering various domains like
history, math, law, etc. The benchmark tests models’ world knowledge and
problem-solving ability. The training set has 95127 examples, the development
set has 1531 examples, and the test set has 14042 examples.

Table 5 summarizes the number of examples for each split in the datasets.

###  A.5 Baseline Results

Table 6 contains the inference throughput numbers of the baselines and BTR-
Atlas models.

###  A.6 Ablation Results

Table 7 includes the detailed numbers of the compression ratio ablation
experiments.

Compression Ratio | Storage (GB) | Accuracy (%)
---|---|---
0.05 | 151 | 50.2
0.1 | 143 | 49.8
0.15 | 135 | 49.6
0.2 | 127 | 49.5
0.25 | 119 | 48.2
0.3 | 111 | 47.1
0.35 | 103 | 46.2
0.4 | 95 | 43.5
0.45 | 87 | 38.4
0.5 | 80 | 32.1
(a) Accuracy and storage effects for different offline token compression
ratios.

Compression Ratio | Accuracy (%) | Throughput (QPS)
---|---|---
0.05 | 50.1 | 28.5
0.1 | 49.8 | 29.2
0.15 | 49.6 | 30.4
0.2 | 49.5 | 31.5
0.25 | 48.7 | 32.2
0.3 | 47.6 | 34.4
0.35 | 45.2 | 35.6
0.4 | 43.2 | 37.5
0.45 | 40.6 | 38.9
0.5 | 38.1 | 41.2
(b) Accuracy and throughput effects for different intra- and cross- passage
token compression ratios.

Table 7: Accuracy, storage and throughput comparisons for different two-stage
token compression ratios on the NaturalQuestions dataset. To achieve a good
balance between accuracy, storage and throughput in BTR, we choose compression
ratio 0.2 for both online and offline token compression.


# A mono-monostatic polyhedron with point masses at the 21 vertices

Flórián Kovács<EMAIL_ADDRESS>MTA-BME Morphodynamics Research
Group, Budapest University of Technology and Economics, Műegyetem rpk. 1-3.,
Budapest, Hungary, 1111  Department of Structural Mechanics, Budapest
University of Technology and Economics, Műegyetem rpk. 1-3., Budapest,
Hungary, 1111  and  Gábor Domokos<EMAIL_ADDRESS>MTA-BME Morphodynamics
Research Group, Budapest University of Technology and Economics, Műegyetem
rpk. 1-3., Budapest, Hungary, 1111  BME Department of Mechanics and
Structures, Budapest University of Technology and Economics, Műegyetem rpk.
1-3., Budapest, Hungary, 1111

# Conway’s spiral and a discrete Gömböc with 21 point masses

Flórián Kovács<EMAIL_ADDRESS>MTA-BME Morphodynamics Research
Group, Budapest University of Technology and Economics, Műegyetem rpk. 1-3.,
Budapest, Hungary, 1111  Department of Structural Mechanics, Budapest
University of Technology and Economics, Műegyetem rpk. 1-3., Budapest,
Hungary, 1111  and  Gábor Domokos<EMAIL_ADDRESS>MTA-BME Morphodynamics
Research Group, Budapest University of Technology and Economics, Műegyetem
rpk. 1-3., Budapest, Hungary, 1111  BME Department of Mechanics and
Structures, Budapest University of Technology and Economics, Műegyetem rpk.
1-3., Budapest, Hungary, 1111

###### Abstract.

We show an explicit construction in 3 dimensions for a convex, mono-monostatic
polyhedron with 21 vertices and 21 faces. This polyhedron is a homogeneous
0-skeleton, with equal masses located at each vertex. This construction serves
as an upper bound for the minimal number of faces and vertices of mono-
monostatic polyhedra, interpreted as homogeneous 0-skeletons and complements
the recently provided lower bound of 8 vertices. This is the first known
discrete construction of a homogeneous mono-monostatic object.

###### Key words and phrases:

polyhedron, static equilibrium, monostatic polyhedron

###### 2010 Mathematics Subject Classification:

52B10, 77C20, 52A38

Support of the NKFIH Hungarian Research Fund grant 134199 and of the TKP2020
IES Grant No. TKP2020 BME-IKA-VIZ is kindly acknowledged.

##  1\. Introduction

###  1.1. Mono-stability and homogeneous polyhedra

If a rigid body has one single stable position then we call it mono-stable,
and this property was probably first explored by Archimedes as he developed
his famous design for ships [1]. Mono-stability might also be of advantage for
rigid bodies under gravity, supported on a rigid (frictionless) surface, as it
facilitates self-righting.

Beyond these applications, mono-stable bodies have also attracted considerable
mathematical interest. In particular, in case of convex polyhedra with
homogeneous mass distribution, it is still unclear what are the minimal
numbers $F^{S},V^{S}$ of faces and vertices necessary to achieve mono-
stability. Conway and Guy in 1967 [4] offered the first upper bound by
describing such an object with $F=19$ faces and $V=34$ vertices. The Conway-
Guy construction was improved by Bezdek [2] to $(F,V)=(18,18)$ and later by
Reshetov [12] to $(F,V)=(14,24)$. The mentioned values of $F$ and $V$ define
the best known upper bounds for a mono-stable polyhedron, so we have
$F^{S}\leq 14,V^{S}\leq 18$. Even less is known about the lower bounds: the
only known result is due to Conway [5] who proved that a homogeneous
tetrahedra have at least two stable equilibria, from which $F^{S},V^{S}\geq 5$
follows.

###  1.2. Mono-unstable and mono-monostatic homogeneous polyhedra

The natural dual property to being mono-stable is being mono-unstable, i.e. to
have one single unstable static balance position. The Conway-Guy polyhedron
has, beyond the single stable position on one face, 4 unstable equilibria at 4
vertices. The first example for a mono-unstable polyhedron was demonstrated in
[10], having $F=18$ faces and $V=18$ vertices and in the same paper it was
proven that a homogeneous tetrahedron can not be mono-unstable. Thus, for the
minimal numbers $F^{U},V^{U}$ for the faces and vertices that a homogeneous,
mono-unstable polyhedron may have, the following bounds apply: $5\leq
F^{U}\leq 18$, $5\leq V^{U}\leq 18$.

If a rigid body is either mono-stable or mono-unstable then we call it
monostatic. If it has both properties, then we call it mono-monostatic. The
construction of the first convex, homogeneous, mono-monostatic body called
Gömböc [14] in 2006 raised the interest in the subject, because a polyhedral
version of the Gömböc is not known. This implies that for the minimal numbers
$F^{\star},V^{\star}$ for the faces and vertices of a mono-monostatic
polyhedron the only known bounds are $F^{\star},V^{\star}\geq 5.$

###  1.3. 0-skeletons and the main result

Here we highlight a new aspect of this problem: instead of looking at uniform
mass distribution, we consider polyhedra with unit masses at the vertices,
also called polyhedral 0-skeletons. The latter problem may appear, at first
sight, almost ‘unsportingly’ easy. However, the minimal vertex number
$V^{\star}_{0}$ and face number $F^{\star}_{0}$ to produce a mono-monostatic
polyhedral 0-skeleton are not known. Even more curiously, the minimal number
of vertices for a mono-monostatic, polygonal 0-skeleton (in 2 dimensions) is
not known either.

The first related results have been reported in [3] where, for the minimal
number of vertices $V^{U}_{0}$ for a mono-unstable polyhedral 0-skeleton
$V^{U}_{0}\geq 8$ was proven and this implies the lower bounds $F^{U}_{0}\geq
6$ (via the theorem of Steinitz [13]) and it also implies the bounds
$F^{\star}_{0}\geq 6,V^{\star}_{0}\geq 8$ for mono-monostatic polyhedral
0-skeletons.

In this paper we explain the background and show some constructions which may
inspire further research. In particular, by providing an explicit construction
of a mono-monostatic polyhedral 0-skeleton with 21 faces and 21 vertices, we
prove

######  Theorem 1.

$F^{\star}_{0},V^{\star}_{0}\leq 21.$

Our example, illustrated in Figure 1(c) and defined on line 3 of Table 1,
appears to be the first discrete construction of a mono-monostatic object and
it may help to inspire thinking about the bounds $F^{\star},V^{\star}$ for the
homogeneous case.

The paper is structured as follows: in Section 2 we explain the geometric idea
behind Conway’s classical construction and how this idea may be generalized in
various directions. In Section 3, by relying on an idea by Dawson [5], we
describe the construction for a mono-monostatic 0-skeleton in 2 dimensions,
having $V_{0}=11$ vertices and then we proceed to prove Theorem 1 by providing
the construction of the mono-monostatic 0-skeleton. In Section 4 we show the
connection to other problems, including the mechanical complexity of
polyhedra, and also point out why the particular geometry of our constructions
may not be applied to the construction of a homogeneous mono-monostatic
polyhedron. In Section 5 we draw conclusions.

##  2\. The geometry of Conway spirals

Figure 1. Construction of symmetric, mono-monostatic discs and polyhedra; a)
Geometry of the Conway spiral $P_{0},\ldots,P_{n}$. $P_{0}$ is fixed at $z=1$
and each radius $OP_{i}$ is perpendicular to the corresponding edge
$P_{i-1}P_{i}$. The geometry of the spiral is uniquely described in terms of
$n$ angular variables $\alpha_{1},\ldots,\alpha_{n}$; b) 2D mirror-symmetric
mono-monostatic polygon with 11 vertices for $n=5$ and $k=2$, see Table 1,
line 6 for numerical data; c) 3D mono-monostatic polyhedron with 5-fold
rotational symmetry for $n=4$ and $k=5$, see Table 1, line 3 for numerical
data.

###  2.1. The classical Conway double spiral and the Conway-Guy monostable
polyhedron

The essence of the Conway-Guy polyhedron is a remarkable planar construction
to which we will briefly refer as the Conway spiral, illustrated in Figure
1(a). In terms of symbols shown in the figure, it can be defined as an open
planar polygon $M$ composed of the sequence of points $P_{0},\ldots,P_{n}$
with $\angle OP_{i}P_{i-1}=\pi/2$, $i=1\ldots n$. Without loss of generality,
$O$ is considered here as the origin of the coordinate system, all points
$P_{i}$ lie in the plane $xz$ and the coordinates of $P_{0}$ are fixed at
(0,0,1). If we consider double Conway spirals generated by reflection
symmetry, for the $x$-coordinate of center of mass $C$ of any double Conway
spiral we have $x_{C}=0$ and due to the special design, the double Conway
spiral is monostatic if and only if $z_{C}<0$.

The original Conway-Guy construction is equivalent to Figure 1(a) if all
central angles are equal, i.e., we have

(1) $\alpha_{1}=\alpha_{2}=\dots=\alpha_{n+1},$

implying that all triangles $P_{i}P_{i+1}O$ are similar. This case, to which
we refer as the classical Conway spiral admits a discrete family of shapes,
parametrized by the integer $n$, and a corresponding family of double Conway
spirals. None of these polygons (interpreted as homogeneous discs rolling
along their circumference on a horizontal plane) is monostatic, i.e., we have
$z_{C}>0$ for all values of $n$, since convex monostatic, homogeneous discs do
not exist [11]. Still, the Conway spiral may be regarded as a best shot at a
monostatic polyhedral disc with reflection symmetry. The same intuition
suggests that a Conway spiral may need minimal added ‘bottom weight’ to become
monostatic.

Conway and Guy added this bottom weight by extending the shape into 3D as an
oblique prism and they computed the minimal value of $n$ necessary to make
this homogeneous oblique prism (with the cross-section of a classical Conway
spiral) monostable as $n=8$, resulting in a homogeneous, convex polyhedron
with 34 vertices and 19 faces.

###  2.2. The modified Conway double spiral and Dawson’s monostable simplices
in higher dimensions

The idea of the Conway spiral may be generalized to bear more fruits. In [5]
Dawson, seeking monostatic simplices in higher dimensions, considered the
generalized version with

(2) $\alpha_{i}=c^{i-1}\alpha_{1},\quad i=1,2,\dots
n\qquad\mbox{and}\qquad\alpha_{n+1}=\alpha_{n}$

to which we refer as a modified Conway spiral. To describe Dawson’s
construction we again consider a double spiral, with the mirror images of the
vertex $P_{i}$ defined as $P_{-i}$. In this model the vectors
$\mathbf{x}_{i}=OP_{i}$, $i=-n,-n+1\dots n$ are interpreted as the face
vectors of a simplex ($\mathbf{x}_{i}$ being orthogonal to the face $f_{i}$
and having magnitude proportional to the area of $f_{i}$). To qualify as face
vectors, any set of vectors must be balanced [8], i.e., we must have

(3) $\sum_{i=-n}^{n}\mathbf{x}_{i}=0.$

Dawson proved that the condition for the simplex tipping from face $f_{i}$ to
$f_{j}$ can be written as

(4) $\lvert\mathbf{x}_{i}\rvert<\lvert\mathbf{x}_{j}\rvert\cos\theta_{ij},$

where $\theta_{ij}$ is the angle between $\mathbf{x}_{i}$ and
$\mathbf{x}_{j}$. By using this tipping condition he found that for
$n=5,c=1.5$ the modified Conway spiral (2) yields a set of balanced vectors,
the small perturbation of which defines a 10-dimensional, homogeneous mono-
stable simplex.

##  3\. Mono-monostatic 0-skeletons

###  3.1. The generalized double Conway spiral and planar 0-skeletons

If, instead of considering double Conway spirals as homogeneous disks we
associate unit masses with the vertices then we obtain objects which may be
called polygonal 0-skeletons. Since there are relatively many vertices with
negative $z$ coordinate and relatively few ones with positive $z$ coordinate,
this interpretation appears to be a convenient manner to add ‘bottom weight’
to the geometric double Conway spiral. In this interpretation as planar
0-skeletons, one may ask whether mono-monostable double Conway spirals exist
and if yes, what is the minimal number of their vertices necessary to have
this property. Since static balance equations for such a skeleton coincide
with (3) and the tipping condition (4) is equivalent to prohibit an unstable
equilibrium at vertex $v_{i}$ [3], it is easy to see that Dawson’s geometric
construction, interpreted as a 0-skeleton, has $z_{C}<0$ and it defines a
polygon with $V=11$ vertices which is mono-monostatic.

One can ask whether this construction is optimal in two ways: whether there
exists a smaller value of $n$ which defines a mono-monostatic modified double
Conway spiral (interpreted as a 0-skeleton) and whether by keeping $n=5$, one
may pick other values for $\alpha_{i}$ which yield a center of mass with
larger negative coordinate. The first question was answered in [6] in the
negative by proving that monostable simplices in $d<9$ dimensions do not
exist. This implies that for $n<5$ no mono-monostatic Conway spiral
(interpreted as a 0-skeleton) exists, but nothing is known about the existence
of mono-monostatic 10-gonal disks as 0-skeletons since they cannot be
represented by a symmetric double Conway spiral. The second question may be
addressed if we admit generalized Conway spirals with arbitrary $\alpha_{i}$
and optimize this construction to seek the minimum of $z_{C}$.

In any case, to verify monostatic property of a given double Conway spiral,
$z_{C}$ needs to be computed. In terms of coordinates $z_{i}$, we have from
Figure 1(a):

(5) $z_{C}=\dfrac{1+k\displaystyle\sum_{i=1}^{n}z_{i}}{1+kn},$

where $k$ stands for the multiplicity of Conway spirals; now $k=2$.
Furthermore, any $z_{i}$ can be expressed in terms of angles $\angle
P_{0}OP_{i}=\sum_{j=1}^{i}\alpha_{j}$ and distances

$r_{i}=\overline{OP_{i}}=\overline{OP_{0}}\cdot\prod_{j=1}^{i}\cos\alpha_{j}$

as follows:

(6)
$z_{i}=\prod_{j=1}^{i}\cos\alpha_{j}\cdot\cos\left(\sum_{j=1}^{i}\alpha_{j}\right).$

By merging (5) and (6) we get

(7)
$z_{C}(\bm{\alpha})=\dfrac{1+k\displaystyle\sum_{i=1}^{n}\prod_{j=1}^{i}\cos\alpha_{j}\cdot\cos\left(\sum_{j=1}^{i}\alpha_{j}\right)}{1+kn},$

or briefly,

(8) $z_{C}(\bm{\alpha})=\dfrac{1+kS_{n}(\bm{\alpha})}{1+kn}.$

We performed an optimization for $\bm{\alpha}=(\alpha_{1}\ldots\alpha_{n})$
and found the shape in Figure 1(b) (see Table 1, line 6 for computed values of
$\bm{\alpha}$). Note that this single result is an alternative proof for the
existence of monostable $10$-dimensional simplices given by Dawson [5].

We remark that a similar optimization process of the Conway spiral is
discussed in [7] for the homogeneous case.

###  3.2. Proof of Theorem 1: Conway $k$-spirals and mono-monostatic
0-skeletons in 3 dimensions

###### Proof.

Generalized Conway spirals may be used as the building blocks of mono-
monostatic 0-skeletons in 3 dimensions. The key idea is to consider instead of
a double Conway spiral multiple Conway spirals in a $D_{k}$-symmetrical
arrangement around the $z$-axis, rotated at angles $\beta=2\pi/k$. We call
such a construction a Conway $k$-spiral. Planar double spirals correspond to
$k=2$, while for higher values of $k$ one may seek to find mono-monostatic
0-skeletons. If for $k=2$ the Conway spiral defines a mono-monostatic planar
0-skeleton then we expect that for higher values of $k$ we will obtain mono-
monostatic polyhedral 0-skeletons.

The procedure of finding mono-monostatic Conway $k$-spirals (interpreted as
0-skeletons) is as follows:

Let us consider a planar polygonal line $M$ as the intersection of a symmetry
plane bisecting a sequence of faces, while another polygonal line
$N(Q_{0},\ldots,Q_{n})$ remains on a sequence of edges as before.

Figure 2. Construction of polyhedra with rotational symmetry: side and top
views. Polygonal lines $M(P_{0},\ldots,P_{n})$ (solid line) and
$N(Q_{0},\ldots,Q_{n})$ (dashed line) lie in symmetry planes through faces and
edges, respectively. Any optimal construction requires $Q_{0}Q_{1}$ instead of
$P_{0}P_{1}$ to be perpendicular to radius $OQ_{1}$.

Let $e_{i}$ be an edge $Q_{i}Q_{i+1},i=0\ldots n-1$ and face $f_{i}$ be
adjacent to $e_{i}$. Call face $f_{i}$ (edge $e_{i}$) ‘outwards’ if its upper
edge (endpoint) is farther from the axis of symmetry than the bottom one,
i.e., for a face $f_{i}$, $\sum_{j=i+2}^{n+1}\alpha_{j}\leq\pi/2$. Clearly,
$e_{i}$ is outwards if and only if $f_{i}$ does.

By construction, $e_{0}$ and $f_{0}$ are never outwards but we assume from now
on that any $e_{i}$, $f_{i}$ with $i>0$ are outwards edges and faces. For them
it is clear that $\angle OQ_{i+1}Q_{i}>\angle OP_{i+1}P_{i}$ and if this
latter equals $\pi/2$, there will be no equilibrium points inside $f_{i}$.
Non-outwards edges, however, are just on the contrary and therefore an optimal
construction for the entire polyhedron requires $\angle OQ_{i+1}Q_{i}=\pi/2$,
causing the top vertex $Q_{0}$ to be moved up by a positive distance $h$ as
shown in Figure 2.

It is easy to read from the right triangle $OP_{0}P_{1}$ that
$z_{1}=\cos^{2}\alpha_{1}$ and $x_{1}=\sin\alpha_{1}\cos\alpha_{1}$. Let the
distance between $z$ and $Q_{1}$ (also between $z$ and $Q^{\prime}_{1}$ in the
figure) be denoted by $x^{\prime}_{1}$. Since
$x_{1}=x^{\prime}_{1}\cos(\pi/k)$ (see the top view) and
$OQ^{\prime}_{1}Q_{0}$ is also a right triangle, for its height of length
$x^{\prime}_{1}$ the following equality holds:

$\cos^{2}\alpha_{1}(\sin^{2}\alpha_{1}+h)=\left(\dfrac{\sin\alpha_{1}\cos\alpha_{1}}{\cos(\pi/k)}\right)^{2},$

which yields

$h=\sin^{2}\alpha_{1}\tan^{2}\dfrac{\pi}{k}.$

Since it affects the vertical position of the top vertex and thus of the
centroid, (8) should be modified as

(9) $z^{\ast}_{C}(\bm{\alpha})=\dfrac{1+kS^{\ast}_{n}(\bm{\alpha})}{1+kn},$

where

(10)
$S^{\ast}_{n}(\bm{\alpha})=S_{n}(\bm{\alpha})+\dfrac{1}{k}\sin^{2}\alpha_{1}\tan^{2}\dfrac{\pi}{k}.$

We performed calculations in search of minimum $z^{\ast}_{C}$ that lead to
different constructions (denoted as $P_{n,k}$), one of these constructions
with $n=4,k=5$ is illustrated in Figure 1(c).

Table 1 summarizes the possible mono-monostatic objects with minimum required
$k$ found by the above method ($v=kn+1$ stands for the number of vertices
or/and faces):

no. | $n$ | $k$ | $v$ | $z_{C}$ |  $(\alpha_{n+1},\alpha_{n},\ldots,\alpha_{1})$
---|---|---|---|---|---
1 | 2 | 25 | 51 | -0.00051277 |  $(49.799,49.799,80.402)^{\circ}$
2 | 3 | 8 | 25 | -0.0061413 |  $(30.273,30.273,46.543,72.912)^{\circ}$
3 | 4 | 5 | 21 | -0.015354 |  $(19.716,19.716,29.875,44.519,66.173)^{\circ}$
4 | 5 | 4 | 21 | -0.029972 |  $(13.494,13.494,20.336,29.781,43.215,59.680)^{\circ}$
5 | 7 | 3 | 22 | -0.042695 |  $(7.1815,7.1815,10.7864,15.6392,22.1409,$ $30.9129,43.0793,43.0788)^{\circ}$
6 | 5 | 2∗ | 11 | -0.017984 |  $(13.201,13.201,19.890,29.110,42.172,62.427)^{\circ}$

Table 1. List of some mono-monostatic 0-skeletons $P_{n,k}$ with
$D_{k}$-symmetry and $v=nk+1$ vertices; $z_{C}$ can be verified via (7). $k=2$
marked by ‘$\ast$’ is the two -dimensional case already mentioned at the end
of Subsection 3.1. The minimum number of vertices for monostatic 3D rotational
polyhedra is 21.

∎

We believe that this construction is close to a (local) optimum, i.e., we
think that this may be the mono-monostatic 0-skeleton defined by multiple
generalized Conway spirals which has the least number of vertices. This,
however, does not exclude the existence of mono-monostatic 0-skeletons with
smaller number of vertices which have less symmetry. Our construction provides
21 as an upper bound for the minimal number of vertices and faces of a mono-
monostatic 0-skeleton. The lower bound for the number of vertices was given in
[3] as 8, from which a lower bound of 6 for the number of faces follows [9].

##  4\. Connection to related other problems

###  4.1. Mechanical complexity of polyhedra

It is apparent that constructing monostatic polyhedra is not easy. In [10]
this general observation was formalized by introducing the mechanical
complexity $C(P)$ of a polyhedron $P$ as

(11) $C(P)=2(V(P)+F(P)-S(P)-U(P)),$

where $V(P),F(P),S(P),U(P)$ stand for the number of vertices, faces, stable
and unstable equilibrium points of $P$, respectively. The equilibrium class of
polyhedra with given numbers $S,U$ of stable and unstable equilibria is
denoted by $(S,U)^{E}$ and the complexity of such class was defined as

(12) $C(S,U)=min\\{C(P):P\in(S,U)^{E}\\}.$

The only material distribution considered in [10] was uniform density. Other
types of homogeneous mass distributions, commonly referred to as h-skeletons
are also possible: 0-skeletons have mass uniformly distributed on their
vertices, 1-skeletons have mass uniformly distributed on the edges,
2-skeletons have mass uniformly distributed on the faces. To distinguish
between these cases we will apply an upper index to the symbol $C$ of
complexity, indicating the type of skeleton (the absence of index indicates
classical homogeneity).

In the case of uniform density (classical homogeneity), the complexity for all
non-monostatic equilibrium classes $(S,U)^{E}$ for $S,U>1$ has been computed
in [10]. On the other hand, the complexity has not yet been determined for any
of the monostatic classes $(1,U)^{E},(S,1)^{E}$. Lower and upper bounds exist
for $C(S,1),C(1,U)$ for $S,U>1$. The most difficult appears to be the mono-
monostatic class $(1,1)^{E}$ for the complexity $C(1,1)$ of which the prize
USD $1.000.000/C(1,1)$ has been offered in [10]. Not only is $C(1,1)$ unknown,
at this point there is no upper bound known either.

###  4.2. Complexity of some monostable and mono-unstable polyhedral
0-skeletons

Admittedly, computing upper bounds for 0-skeletons is easier. This is already
apparent in the planar case, where monostatic discs with homogeneous mass
distribution in the interior do not exist [11] whereas a monostatic 0-skeleton
could be constructed with $V=11$ vertices [5]. In 3D, our construction of a
0-skeleton with $F=21$ faces and $V=21$ vertices (see the top left polyhedron
in Figure 3 and Table 1, line 3) offers such an upper bound as

(13) $C^{0}(1,1)\leq 2(21+21-1-1)=80$

This is the first known such construction and its existence may help to solve
the more difficult cases, in particular, the case with uniform density. In
Figure 3 we provide upper bounds for the complexity of 0-skeletons in some
other monostatic equilibrium classes as well.

Figure 3. Complexity of some monostable and mono-unstable polyhedra. Drawn
representatives of equilibrium classes $(S,U)$ prove an upper bound for
complexity of the respective class, see the bracketed numbers as lower and
upper bounds, respectively, in the top left corner of their cells. Since mono-
unstable polyhedra with less than 8 vertices (and therefore, by Steinitz’s
theorem, with less than 6 faces) cannot exist, 24 is a lower bound of
complexity of classes $(S,1)$. Complexity of the four non-monostatic classes
is exactly known by the existence of simplicial representatives of each class
[10]. Coordinates of drawn polyhedra, except for the one in class (1,1), are
given in Table 2.

###  4.3. Existence and non-existence of certain types of mono-monostatic
0-skeletons and homogeneous bodies

The following paragraphs illustrate the relative difficulty of constructing
mono-monostatic $h$-skeletons from a different point of view. Firstly, it is
known from [11] that no homogeneous mono-monostatic two-dimensional objects
rolling along their perimeter exist; however, $P_{5,2}$ drawn in Figure 1b is
a mono-monostatic 0-skeleton in 2D. A similar property of non-existence of
homogeneous mono-monostatic objects will be proven below for Conway
$k$-spirals, interpreted as homogeneous solids.

######  Theorem 2.

Let $P$ be a convex solid with center of mass at $C$. Let $a$ denote an axis
intersecting $P$ and let $h(a)$ be a half-plane the boundary of which is $a$.
Let $N$ denote the intersection of $P$ and $h(a)$ and let us describe $N$ as
the polar distance $r(\varphi)$, measured from $C$ as origin.

If there exists an axis $a$ such that $r(\varphi)$ is strictly monotonic for
all possible $h(a)$ then

$P$ is not mono-monostatic.

###### Proof.

Let an axis $z$ be directed along $a$ and let a point $Q$ on the surface of
$P$ be parametrized as $Q(\theta,\varphi,r)$ where $0\leq\theta\leq\pi$ is the
meridian angle between $CQ$ and $z$, $0\leq\varphi<2\pi$ is the azimuth angle
(with respect to a fixed starting position), $r=\lvert Q-C\rvert$. Since $P$
is convex, $r=r(\theta,\varphi)$ for all surface points is uniquely defined.
In this polar system, $C$ can only be the centre of mass of $P$ if

(14)
$\int\limits_{0}^{2\pi}\int\limits_{0}^{\pi}\dfrac{2}{9}r(\theta,\varphi)^{4}\sin\theta\cos\theta
d\theta d\varphi=0,$

once $(1/3)r^{3}\sin\theta d\theta d\varphi$ is the volume of an elementary
pyramid with its apex at $C$ and $(2/3)r\cos\theta$ measures the $z$
coordinate for the centre of mass of an elementary pyramid. From the condition
of the theorem, it follows that $r$ is strictly monotonic in $\theta$: assume
now that $\theta_{1}<\theta_{2}\iff r_{1}>r_{2}$ for all
$Q_{1}(\theta_{1},\varphi,r_{1}),Q_{2}(\theta_{2},\varphi,r_{2})$ and rewrite
(14) as follows:

$\dfrac{2}{9}\int\limits_{0}^{2\pi}\int\limits_{0}^{\pi/2}\left(r(\theta,\varphi)^{4}\sin\theta\cos\theta+r(\pi-\theta,\varphi)^{4}\sin(\pi-\theta)\cos(\pi-\theta)\right)d\theta
d\varphi=0$ (15)
$\dfrac{1}{9}\int\limits_{0}^{2\pi}\int\limits_{0}^{\pi/2}\left(r(\theta,\varphi)^{4}-r(\pi-\theta,\varphi)^{4}\right)\sin
2\theta d\theta d\varphi=0.$

Here both terms of the product in the integrand are positive, so the definite
integral cannot evaluate to zero. ∎

######  Corollary 1.

Conway $k$-spirals, interpreted as homogeneous solids, are never mono-
monostatic.

###### Proof.

We prove the Corollary by showing that a Conway $k$-spiral satisfies the
monotonicity condition of the theorem. Consider $a$ to be aligned with axis
$z$ again. Since we consider polyhedral solids, the ‘level sets’ for $r$ are
concentric circles on all faces. By construction, perpendicular projection of
$C$ on the base $k$-gon is incident to $a$, so $r$ increases monotonically
within that $k$-gon along any $h$. For all other faces, assume that there is a
plane $h$ intersecting or being tangent to a level set, but it would
immediately imply that a non-horizontal edge (surely contained by some plane
$h$) of the same face carries an equilibrium point which contradicts the mono-
monostatic property. As a consequence, any $h$ intersects all set levels
without being even tangent to any of them, which is a necessary and sufficient
condition for $r$ being strictly monotonic along any line $N$ started and
ended at the axis $a$. ∎

We note that Theorem 2 also implies that any homogeneous smooth solid of
revolution cannot be mono-monostatic.

##  5\. Concluding comments

In this paper, by relying on the geometric idea of Conway spirals, we
demonstrated the existence of mono-monostatic 0-skeletons in two and three
dimensions. In the former case, by drawing on an earlier result of Dawson [5]
we showed that mono-monostatic planar 0-skeletons with $V=11$ vertices exist.
It follows from another result of Dawson [6] that for $V=9$ such constructions
can not exist The $V=10$ case is not known. In three dimensions we showed an
explicit construction with $V=21$ vertices, thus providing an upper bound for
the minimal number of vertices. The lower bound is $V=8$ [3] and other results
are not known. We hope that these constructions will motivate further research
to find the minimal number of $V$ for a mono-monostatic 0-skeleton, both in
two and in 3 dimensions.

$(S,U)=(1,2)$
---
$x$ | $y$ | $z$
0 | 374 | 0
154 | 80 | 0
124 | -32 | 0
81 | -78 | 0
47 | -95 | 0
24 | -100 | 0
-24 | -100 | 0
-47 | -95 | 0
-81 | -78 | 0
-124 | -32 | 0
-154 | 80 | 0
0 | -1200 | 5000

$(S,U)=(1,3)$
---
$x$ | $y$ | $z$
0 | 466 | 0
166 | 70 | 0
121 | -47 | 0
71 | -87 | 0
35 | -100 | 0
-35 | -100 | 0
-71 | -87 | 0
-121 | -47 | 0
-166 | 70 | 0
0 | -100 | -900
0 | -100 | 900

$(S,U)=(2,1)$
---
$x$ | $y$ | $z$
0 | 374.328 | 0
153.589 | 80.2023 | 20
124.268 | -32.3675 | 14.9819
81.1006 | -77.5258 | 8.45141
46.9121 | -94.4981 | 3.41302
23.4562 | -100 | 0
-23.4562 | -100 | 0
-46.9121 | -94.4981 | 3.41302
-81.1006 | -77.5258 | 8.45141
-124.268 | -32.3675 | 14.9819
-153.589 | 80.2023 | 20

$(S,U)=(3,1)$
---
$x$ | $y$ | $z$
0 | 334.907 | 0
145.019 | 83.7267 | 10
145.019 | 0 | 9.6018
94.9161 | -68.9606 | 5.40618
53.5898 | -92.8203 | 2.10256
26.7949 | -100 | 0
-26.7949 | -100 | 0
-53.5898 | -92.8203 | 2.10256
-94.9161 | -68.9606 | 5.40618
-145.019 | 0 | 9.6018
-145.019 | 83.7267 | 10

Table 2. Coordinates of some polyhedra shown in Figure 3. Monostable objects
are provided with integer coordinates which would be difficult for mono-
unstable ones due to oblique polygonal faces.

## References

  * [1] H. Nowacki,  Archimedes and ship stability. In: Passenger ship design, construction, operation and safety: Euroconference; Knossos Royal Village, Anissaras, Crete, Greece, October 15–17, 2001, 335–360 (2002). Ed: Kaklis, P.D. National Technical Univ. of Athens, Department of Naval Architecture and Marine Engineering, Athens.
  * [2] A. Bezdek, On stability of polyhedra, in: Workshop on Discrete Geometry, Fields Institute, Canada, Sep 13-16 2011, 2490–2491.
  * [3] S. Bozóki, G. Domokos, F. Kovács and K. Regős, Mono-unstable polyhedra with point masses have at least 8 vertices, Int. J. Solids Struct. (2021) in press, https://doi.org/10.1016/j.ijsolstr.2021.111276
  * [4] J. H. Conway and R. K. Guy, Stability of polyhedra, SIAM Rev. 11 (1969) 78–82.
  * [5] R. Dawson, Monostatic simplexes, Amer. Math. Monthly 92 (1985) 541–546.
  * [6] R. Dawson and W. Finbow, Monostatic Simplexes III, Geometriae Dedicata 84 (2001) 101–113.
  * [7] C. Minich, Search for small monostatic polyhedra, WSCG ’2012, Plzeń, Czech Republic, June 26-28 2012, ISSN 1213–6980
  * [8] H. Minkowski, Allgemeine Lehrsätze Über die Konvexe Polyeder, Nachr. Ges. Wiss. Göttingen (1897) 198–219.
  * [9] E. Steinitz, Über die Eulersche Polyderrelationen, Arch. Math. Phys. 11 (1906) 86–88.
  * [10] G. Domokos, F. Kovács, Z. Lángi, K. Regős and P. T. Varga, Balancing polyhedra, Ars Mathematica Contemporanea 19(1) (2020) 95–124. DOI 10.26493/1855-3974.2120.085
  * [11] G. Domokos, J. Papadopulos and A. Ruina, Static equilibria of planar, rigid bodies: is there anything new? J. Elasticity 36 (1994) 59–66.
  * [12] A. Reshetov, A unistable polyhedron with $14$ faces (English summary), Internat. J. Comput. Geom. Appl. 24 (2014) 39–-59.
  * [13] E. Steinitz,Über die Eulersche Polyderrelationen, Arch. Math. Phys. 11 (1906), 86-88.
  * [14] P. L. Várkonyi and G. Domokos, Static equilibria of rigid bodies: Dice, Pebbles and the Poincaré-Hopf Theorem J. Nonlinear Science 16 (2006) 255–281.