# Sub-Sentence Encoder:
Contrastive Learning of Propositional Semantic Representations

Sihao Chen$\clubsuit$ Hongming Zhang$\diamondsuit$ Tong Chen$\heartsuit$ Ben
Zhou$\clubsuit$ Wenhao Yu$\diamondsuit$
Dian Yu$\diamondsuit$ Baolin Peng$\diamondsuit$ Hongwei Wang$\diamondsuit$ Dan
Roth$\clubsuit$ Dong Yu$\diamondsuit$
$\clubsuit$University of Pennsylvania $\heartsuit$University of Washington
$\diamondsuit$Tencent AI Lab
<EMAIL_ADDRESS>Work was done during internship at Tencent AI Lab,
Bellevue.

###### Abstract

We introduce _sub-sentence encoder_ , a contrastively-learned contextual
embedding model for fine-grained semantic representation of text. In contrast
to the standard practice with sentence embeddings, where the meaning of an
entire sequence of text is encoded into a fixed-length vector, the sub-
sentence encoder learns to produce distinct contextual embeddings
corresponding to different atomic propositions, i.e. atomic units of meaning
expressed within a text sequence. The sub-sentence embeddings are
contrastively learned to recognize (inferred) semantic equivalence between
propositions across different text sequences. Our experiments show the
effectiveness of sub-sentence encoders in applications, such as retrieving
supporting facts for fine-grained text attribution or recognizing the
conditional semantic similarity between texts. In practice, we demonstrate
that sub-sentence encoders keep the same level of inference cost and space
complexity compared to sentence encoders.

https://github.com/schen149/sub-sentence-encoder

##  1 Introduction

Sentence embeddings are a class of techniques that represent text semantics as
dense vector embedding(s) Conneau et al. (2017); Cer et al. (2018); Reimers
and Gurevych (2019). Sentence embeddings are widely used in zero-shot or
transfer learning settings on information retrieval and text classification
tasks Karpukhin et al. (2020); Gao et al. (2021). With sentence embeddings,
the common practice is to encode the entire text sequence as a fixed-length
vector, where the semantic relation with other text sequences is typically
modeled by a similarity function Bromley et al. (1993).

While sentence embeddings provide unified and compact semantic representations
of text, it is difficult to query for the varying granularity of semantics
from fixed dimensional sentence embeddings. For example, consider the two
sentences at the bottom of Figure 1 about the novel Dracula. While the two
sentences as a whole convey different meanings, at the level of atomic
propositions, i.e., atomic pieces of meaning conveyed in each sentence, it
becomes obvious that the two sentences in part share similar meanings, e.g.,
both sentences agree on _Dracula is a novel_ and _is published in the 19th
century_.

Efficiently encoding and indexing text on a more granular level potentially
has a profound impact on applications like long-form text evaluation Amplayo
et al. (2022), attribution Rashkin et al. (2023) or factuality estimation Min
et al. (2023). With long-form generated text, multiple propositions in the
same text might have different truthfulness values. The prerequisite for
verifying or attributing such long-form text involves (1) representing the
text on a more granular level of atomic propositions and (2) being able to
retrieve evidence for different propositions within a text sequence. Chen et
al. (2023a); Kamoi et al. (2023).

Figure 1: Given an atomic proposition in a sentence (represented by a
highlighted subset of tokens), the sub-sentence encoder produces a contextual
embedding for the meaning of the proposition. The cosine similarity between
the sub-sentence embeddings captures the (inferred) semantic similarity
between the propositions. Figure 2: Overview of the sub-sentence encoder
architecture and learning objective: The model takes a sentence and its
propositions (represented as binary token masks) as input and outputs an
embedding for each proposition. Given a minibatch of sentences, the model
learns to identify pairs of propositions that express the same meaning. All
others (including other propositions within the same sentence) are taken as
negative examples (section 3).

Motivated by such, we introduce _sub-sentence encoder_ , a contrastively-
learned contextual embedding model for representing sub-sentence-level
semantics. As shown in Figure 2, the sub-sentence encoder takes one or more
propositions within a text sequence as input. It outputs an embedding that
represents the meaning of the proposition. Each proposition takes the format
of a binary token mask sequence over the text, which denotes the tokens
included in each proposition Chen et al. (2023b). We train the sub-sentence
encoder model to recognize the semantic equivalence between pairs of atomic
propositions via in-batch supervised contrastive learning Khosla et al.
(2020). We sample and create training examples from a large corpus of
unlabeled sentence pair data with proposition extraction and NLI models
(section 3.3).

We evaluate sub-sentence encoders on two types of downstream tasks that
involve semantic representation on the sub-sentence level. First, we
demonstrate that sub-sentence encoders can be used for fine-grained retrieval,
e.g., for text attribution, where a model is expected to retrieve supporting
evidence for different parts of a sentence. Second, we show that sub-sentence
encoders can be used to infer the conditional semantic similarity between a
pair of text Deshpande et al. (2023).

We discuss the design choices and practical challenges in applying sub-
sentence encoders in large-scale indexing of a retrieval corpus on the
proposition level. As encoding an entire corpus on the proposition level might
result in a prohibitively large, we reduce the output dimension of the sub-
sentence encoder model during training Wang et al. (2023). We show that this
simple yet effective trick results in 12$\times$ to 16$\times$ compression in
index size with minimal performance drop.

The main contributions of the paper are: (1) We propose the sub-sentence
encoder, a contextual embedding method for fine-grained text semantics; (2) We
introduce an automatic process for creating training data for sub-sentence
encoders; (3) We evaluate the utility of sub-sentence encoders in the
downstream applications of atomic fact retrieval and conditional semantic
textual similarity.

##  2 Preliminaries

###  2.1 Motivation: Text Attribution

Our design of the sub-sentence encoder is largely motivated by the downstream
application of text attribution Rashkin et al. (2023), i.e., identify
supporting information from known sources to attribute model-generated text.
With the widespread adoption of text generation models, evaluating and
attributing generated text has become an emerging research topic in need Gao
et al. (2023a, b); Liu et al. (2023); Malaviya et al. (2023). A key challenge
in such tasks lies in the granularity of attributed information, i.e., one
piece of generated text usually makes more than one claim, each of which might
have different veracity. For instance, as Figure 1 shows, there could exist
multiple claims even within one generated sentence in the form of
propositions. Each claim or proposition needs to be contextualized Choi et al.
(2021) and individually verified against potentially different information
sources Kamoi et al. (2023); Min et al. (2023). This process inevitably
requires an efficient model representing the semantics of different sentence
parts in context, which describes the key design principle for the sub-
sentence encoder.

###  2.2 Limitations of Sentence Embeddings

From the perspective of downstream applications such as text attribution, our
study addresses the following two shortcomings of current sentence encoder
models.

##### Granularity.

Although sentence embeddings usually capture the meaning of the entire text
sequence as a fixed-length embedding Morris et al. (2023), it is difficult in
practice to query sentence embeddings for semantic information or structure on
a more granular level Rudinger et al. (2017); Qin and Van Durme (2023); Wang
and Yu (2023). The format would offer limited expressivity when modeling tasks
such as document retrieval, especially when the task conceptually involves
identifying document parts that respond to the query. For such reason,
previous studies have found empirical success with phrase retrieval or late-
interaction models, which support more granular and expressive representations
of the retrieval corpus Seo et al. (2019); Khattab and Zaharia (2020); Lee et
al. (2021a, b).

##### Contextualization.

A typical assumption for sentence encoder models and training/evaluation task
setup is that the sentence is encoded independently without context. This
becomes a limiting factor in scenarios where similarities and discrepancies
between text pairs depend on the context they appear in Chen et al. (2019);
Schuster et al. (2022); Milbauer et al. (2023a, b); Deshpande et al. (2023).

##  3 Sub-Sentence Encoder

We study a new type of architecture and learning objective – sub-sentence
encoders. Contrary to sentence encoders, sub-sentence encoders are designed to
produce contextual embeddings for each atomic proposition in a sentence.

###  3.1 Architecture

The sub-sentence encoder architecture is instantiated similarly to
transformer-based sentence bi-encoders Reimers and Gurevych (2019), as shown
in Figure 2. The key difference is the sub-sentence encoder takes $k$ sets of
binary token masks as extra inputs, which indicate the $k$ propositions of a
sentence that it should produce embeddings for. The input sentence is first
forwarded through a transformer encoder, which can be initialized from any
pre-trained encoder model. Then, for each of the $k$ token masks, the token
embeddings with mask values of $1$ are mean pooled and forwarded through a
projection MLP layer. The model outputs $k$ fixed length embedding
corresponding to the $k$ input propositions.

Note that the $k$ token masks are only applied during pooling, and the encoder
still gets full attention to the entire sentence. This allows the proposition
embeddings to have the contextual information of the entire input
sentence/paragraph, potentially alleviating the need for decontextualizing the
propositions Choi et al. (2021). In addition, since there is no cross-
attention between the proposition embeddings, each proposition is encoded
independently of others, and its representation is inherently invariant to the
input ordering of the propositions.

Compared to sentence encoders, the sub-sentence encoder adds a small amount of
parameters with the MLP layer on top. As the sentence can be forwarded only
once, the extra inference cost of encoding multiple propositions in a sentence
is minimal in practice, as we discuss in section 4.

###  3.2 Contrastive Learning

With two propositions from different sentences, the goal is to make them have
similar embedding representations if they express similar meanings, and have
dissimilar representations otherwise. Within a minibatch of $N$ propositions
from $M$ sentences. Let $v_{i}=\in\mathbb{R}^{d}$ be the encoded
representation of the $i^{th}$ proposition in the batch. Let $I=\\{1..N\\}$
denote the index of all propositions. We formulate the learning objective as
minimizing the in-batch supervised contrastive loss $\mathcal{L}$ Khosla et
al. (2020):

$\mathcal{L}=\sum_{i\in I}\frac{-1}{|P(i)|}\sum_{p\in
P(i)}\log\frac{\exp(v_{i}\cdot v_{p}/\tau)}{\sum_{j\in
I\setminus\\{i\\}}\exp(v_{i}\cdot v_{j}/\tau)}$

where $P(i)$ is the set of indices of all positive propositions to the
$i^{th}$ proposition within the minibatch, and $|P(i)|$ denotes its
cardinality. $\tau$ controls the softmax temperature. The learning objective
encourages the model to produce embeddings with higher cosine similarity with
positive pairs of propositions, while all other propositions in the same batch
are considered negatives. Note that if all propositions from the same sentence
are packaged in the same minibatch, under the assumption that they cannot be
positive examples of each other, the learning objective would inherently
encourage the model to assign different representations for different parts of
a sentence.

The supervised contrastive loss is a generalized form of other commonly used
loss functions for bi- or dual-encoder training, e.g., N-pairs loss Sohn
(2016) or in-batch softmax Karpukhin et al. (2020). We opt for this
formulation mostly due to its ability to generalize to an arbitrary number of
positive examples in the same batch. In our case, this is important, as each
proposition may have zero or more positive instances in the same minibatch.

###  3.3 Sampling Proposition Pairs for Training

Here, we describe how we automatically sample positive proposition pairs from
a collection of unlabeled sentence pairs as training data for the sub-sentence
encoder. We start from a collection of 2.5M sentence pairs from topically
related news articles Zhou et al. (2022). This data is collected from RealNews
Zellers et al. (2019) to find parallel sentence pairs that generally describe
the same event with slightly different angles and focuses. These instances
serve as great starting points for our need since we want to find proposition
pairs with both similarities and differences.

##### Step 1: Segment Sentences $\Rightarrow$ Propositions.

Given an unlabeled sentence pair, we first parse each sentence into
propositions in natural language forms. First, we prompt GPT-3.5-turbo to
generate propositions for $1\%$ of all sentence pairs as the seed set of
training data. We find that GPT-3.5-turbo with few shot in-context
demonstrations gives reasonable performance on the task, which echos with the
observations from Min et al. (2023); Kamoi et al. (2023).

Next, we finetune T5-large Raffel et al. (2020) on the seed training set and
use the model to generate propositions for the rest of the dataset. We include
more details about the prompt and training process in Appendix A.

##### Step 2: Identify Positive Pairs with NLI models.

Given the two sets of propositions (in natural language form) in each sentence
pair, we infer and label the positive proposition pairs with an off-the-shelf
NLI model Nie et al. (2020) 111https://huggingface.co/ynie/roberta-large-
snli_mnli_fever_anli_R1_R2_R3-nli. We forward each pair of propositions across
two sentences through the NLI model two times, with flipped orders between
hypothesis and premise. We label a proposition pair positive if the NLI model
classifies their relation as entailment in both directions. We only keep
sentence pairs with at least one pair of positive propositions. This leaves us
with $240k$ sentence pairs, with $3.32$ propositions per sentence and $1.21$
positive propositions on average.

##### Step 3: Convert Propositions $\Rightarrow$ Token Masks.

We convert the propositions in natural language form to the token mask format
used for sub-sentence encoder input by aligning the tokens in each proposition
to the sentence. We use NLTK Bird et al. (2009) to lemmatize each token in a
proposition and its sentence and construct an affinity matrix between the two,
where tokens with identical lemmas are assigned a similarity score of 1. To
break ties between multiple token matches, we apply a 2D-convolution filter on
the affinity matrix, which adds a small score offset for other token matches
in a context window of three tokens. We find the optimal matches between the
proposition and sentence with max bipartite matching on the affinity matrix
with the Hungarian algorithm Kuhn (1955). We include a more detailed process
description in Appendix A.

##  4 Experimental Setup

###  4.1 Model Configurations

System | Param. Size | Precision@1 | Recall@5 | Recall@10 | Recall@20
---|---|---|---|---|---
MiniLM-L6-v2 | 23M | 18.36 | 37.28 | 44.87 | 51.62
DistilRoberta | 82M | 16.59 | 33.65 | 40.82 | 46.79
SimCSE (unsupervised) | 110M | 8.90 | 45.13 | 69.47 | 84.29
SimCSE (supervised) | 110M | 16.53 | 57.83 | 77.28 | 87.89
GTRbase | 110M | 21.90 | 52.50 | 65.54 | 75.69
ST5base | 110M | 26.16 | 57.65 | 69.00 | 78.58
SubEncoder (SimCSE) | 110M (+0.5M) | 41.64 | 71.48 | 78.22 | 83.34
SubEncoder (ST5base) | 110M (+0.5M) | 40.97 | 72.15 | 79.30 | 84.33
SubEncoder (GTRbase) | 110M (+0.5M) | 40.77 | 72.90 | 80.45 | 85.81
Table 1: Zero-shot evaluation results on the _Atomic Fact Retrieval_ task in
PropSegmEnt (Chen et al., 2023b).  Figure 3: In the Atomic Fact Retrieval task
Chen et al. (2023b), given an atomic proposition in the query, a system is
expected to retrieve the set of supporting atomic propositions from the
corpus. The dataset features $8.8k$ query propositions and $45k$ candidate
evidence propositions from $1.5k$ documents.

We initialize the transformer encoder layers with pre-trained weights from
three types of sentence encoders: SimCSE Gao et al. (2021), Sentence-T5 Ni et
al. (2022a), and GTR Ni et al. (2022b). With Sentence-T5 and GTR, we
experiment with the base, large, and xl-sized variants of the models. For the
MLP layer, we keep the output dimension the same as the transformer encoder.
We discuss the impact of varying output dimensions in section 5.4.

We finetune the sub-sentence encoder with different variants of backbone
sentence encoders on the $240k$ sentence pairs with at least one pair of
positive propositions. We denote the resulting model as SubEncoder. We include
the details for our distributed training setup and hyperparameters in Appendix
B.

###  4.2 Evaluation

To assess the utility of the sub-sentence encoders, we evaluate our model on
two types of downstream tasks in zero-shot settings.

####  4.2.1 Atomic Fact Retrieval for Fine-Grained Text Attribution

We first evaluate the sub-sentence encoders in retrieving fine-grained
attributions Rashkin et al. (2023) for text. We conduct the evaluations with
the PropSegmEnt dataset Chen et al. (2023b). An overview of the task setup is
shown in Figure 3. Given an atomic proposition in the sentence, a system is
expected to identify and retrieve supporting evidence from a corpus of
$\tilde{~}{}45k$ human-labeled atomic propositions from $1.5k$ News or
Wikipedia documents in total. The task setup emulates the setting where each
part of a sentence might have different veracity, and so each atomic
proposition in a sentence might be attributed to different supporting evidence
from different source documents. On average, each query proposition has $1.13$
ground truth supporting propositions.

##### Metrics.

Given a system’s output rankings of the $45k$ candidate evidence propositions
with respect to a query proposition, we measure the precision@$1$ plus
recall@$\\{5,10,20\\}$ of the ranking against the human-annotated ground truth
set of evidence propositions.

##### Baselines.

We compare pre-trained sentence encoders as baselines. We first evaluate
variants of unsupervised and supervised SimCSE, Sentence-T5, and GTR on
similar model parameter sizes. In addition, we compare two popular compact
models, i.e., all-MiniLM-L6-v2 and all-distilroberta-v1 from sentence-
transformers Reimers and Gurevych (2019). We discuss the setup for sentence
encoders for the tasks in Appendix C.

##### Results.

Table 1 summarizes our evaluation results. We observe that the SubEncoder with
different backbone encoders generally improve over their sentence encoder
counterparts. We see the most visible improvements of SubEncoder in terms of
Precision@1 and Recall@5, while the performance gap becomes smaller in terms
of Recall@10 and 20. This suggests that sub-sentence contrastive learning
gives the model better capabilities at recognizing the nuanced semantic
differences between propositions appearing in the same context.

Across different variants of SubEncoder with different backbone sentence
encoders, we observe similar performance levels overall, with the GTRbase
variant having a slight edge. In Table 1, we mostly compare models with the
same backbone encoder size and configurations. Our SubEncoder only introduces
0.5% extra parameters with the MLP layer on top. We include a more
comprehensive analysis of model size, efficiency, and performance trade-off in
section 5.

Type |  Sentence 1 |  Sentence 2 |  Condition | Label | Pred.
---|---|---|---|---|---
Correct. |  A group of people go sledding on a snowy hill, and a dog chases one as he slides. |  A person, dressed in black, skipping down a snow covered road and playing with a black dog. |  The physical activity. | 4 | 3.44
Mistake: fails to find a good set of words. |  A man being thrown into the air while being trampled by a bull. |  The cowboy holds on to the bull who is desperately trying to throw him off. |  The person’s elevation. | 4 | 1
Mistake: correct set of words; failed inference. |  A man wearing a white tank top and a white hard hat is holding two pieces of pipe at a construction site. |  A construction worker in a lime-green safety vest and orange hard hat is looking closely at something held in his hands. |  The occupation of the man. | 5 | 2.47
Table 2: Example outputs and typical mistakes of SubEncoder on C-STS. The set of words identified by gpt-3.5 is highlighted yellow. For display purposes here, the model predicted cosine similarity is normalized to match the human labels’ scale of 1 - 5, where 1 $=$ Least similar, and 5 $=$ Most similar Model | Setting | Spearman $r\uparrow$
---|---|---
Robertabase | 0-shot (No. Cond.) | -0.43∗
SimCSEbase | 0-shot (No. Cond.) | 1.66∗
FlanT5large | 0-shot | -3.0∗
2-shot | 11.7∗
GPT-3.5 | 0-shot | 14.1
2-shot | 15.4
GPT-4 | 0-shot | 36.9
2-shot | 40.7
GPT-3.5 \+ SubEncoder (0-shot) | (SimCSEbase) | 27.5
(GTRbase) | 31.9
(ST5base) | 33.0
GPT-4 \+ SubEncoder (0-shot) | (SimCSEbase) | 34.5
(GTRbase) | 36.9
(ST5base) | 37.2
Table 3: Spearman correlation coefficient ($\times 100$) of model predictions
evaluated in zero- or few-shot settings on the Conditional Semantic Textual
Similarity (C-STS) task. * denotes results from Deshpande et al. (2023).

####  4.2.2 Conditional Semantic Text Similarity

To assess SubEncoder’s ability to produce contextual representations for fine-
grained sub-sentence level semantics of text, we conduct experiments on the
Condition Semantic Text Similarity (C-STS) task Deshpande et al. (2023).
Compared to STS Agirre et al. (2012), C-STS introduces a condition notion of
similarity between text pairs, where an additional natural language condition
is provided along with the text pair as input. A system is expected to output
a similarity score between the pair from the perspective of the given
condition. Table 2 shows some examples of the task.

##### Method.

Given the condition, we first prompt an LLM to identify a set of words in each
sentence that best corresponds to the condition. Here, the LLM only sees one
sentence at a time, so the condition words in each sentence are identified
independently. We use the sub-sentence encoder to encode the set of words in
the context of each sentence as the conditional representation. We take the
cosine similarity between two encoded sets of words from the text pair as
their conditional similarity.

##### Metrics.

We compare the Spearman correlation coefficient between predicted similarity
from a system against human ratings.

##### Baselines.

We compare to a list of zero- and few-shot baselines provided by (Deshpande et
al., 2023). This includes two bi-encoder models, Robertabase and SimCSEbase
that do not make use of the condition as input, as well as zero- and few-shot
prompting results with FlanT5large, GPT-3.5-turbo and GPT-4, where each LLM
provided detailed instructions of the task, and is prompted to generate a
similarity score from 1 to 5 given the text pair and condition with/without
in-context demonstrations.

##### Results.

Table 3 shows the evaluation results. By having SubEncoder comparing the
contextual similarity between the set of words selected by gpt-3.5-turbo, we
see an improvement in zero-shot setting from Spearman’s $r=14.1\rightarrow
33.0$, compared to directly prompt LLM to output the similarity. However, the
performance gap when using gpt-4 becomes much smaller ($r=36.9\rightarrow
37.2$). This is reasonable considering the fact that direct gpt-4 prompting
demonstrates on-par performance with supervised systems on C-STS, as reported
in Deshpande et al. (2023). We show examples of typical mistakes made by our
model in Table 2. We observe that our method typically fails when (1) the LLM
fails to identify a good set of condition words, or when no such corresponding
words explicitly exist in the sentence, or (2) SubEncoder fails to correctly
infer the similarity between the two sets of condition words. For instance,
with the third example in Table 2, the inference is particularly challenging
for the model, considering the relation between two sentences is modeled only
via a cosine similarity with no learned parameters.

##  5 Analysis and Discussions

Figure 4: The effect of varying batch size and model parameter size on the
atomic fact retrieval performance, tested with the Sentence-T5 variant of
SubEncoder.

###  5.1 Scaling SubEncoder

In Figure 4, we show an analysis of the effect of scaling model sizes and
batch sizes during training. For our analysis, we use the Sentence-T5 variant
of SubEncoder, and evaluate the performance on the atomic fact retrieval task.

##### Scaling Batch Size.

As our contrastive learning objective leverages in-batch negative sampling,
scaling up the batch sizes during training could bring performance gains. To
illustrate this, we initialize SubEncoder with Sentence-T5 base encoder
parameters and finetune with a varying batch size of
$\\{8,16,32,64,128,256\\}$. We observe that increasing the batch size
generally increases performance, which suggests that batch size scaling could
yield better model generalizability. We observe a significant performance gain
when increasing batch size from $32\rightarrow 64$ while seeing diminishing
gains with further increase. This echoes the empirical findings with in-batch
contrastive learning in general Khosla et al. (2020). The phenomena can be
attributed to the model-predicted labels in our training dataset, which can be
noisy.

##### Scaling Model Size.

We initialize the encoder with different sizes of Sentence-T5 from 110M to 3B
parameters and finetune with a fixed batch size of 64. We observe that
starting from a larger pre-trained encoder brings better performance. We see a
bigger gain when increasing the model size from 110M to 330M, while the gain
becomes smaller when we increase from 330M to 3B.

###  5.2 Using SubEncoder for Sentence or Document Retrieval

In section 4, we compare SubEncoder’s performance on the atomic fact retrieval
task against the baseline sentence encoders. In reality, a more likely
application scenario is when the system is expected to retrieve supporting
evidence on the sentence or document level. To evaluate this, we cast the
atomic fact retrieval task as a sentence or document retrieval task, where
given a query proposition, a system is expected to retrieve the set of
sentences or documents that contain the target proposition(s).

From the intuition that finer-grained retrieval, e.g., with propositions,
entails the more coarse sentence- or document-level retrieval, we follow Lee
et al. (2021b) and use a simple strategy with SubEncoder for sentence- and
document-level retrieval. Given each query, we retrieve a slightly larger
number of propositions. From the set of sentences and documents where the
propositions belong, we use the highest score among the set of propositions as
the score for each sentence or document. The top $k$ unique sentences or
documents are then returned as results.

Table 4 shows the the evaluation result. Compared to GTRbase and
Sentence-T5base, which are trained for document-level and sentence-level
retrieval, respectively, we observe a similar level of performance with
retrieving by propositions with SubEncoder. Overall, we see lower top-1
accuracy compared to the baselines. This is possibly due to the more complex
nature of the proposition retrieval task. However, we generally see an
improvement in terms of recall @ 5. The findings indicate the potential of
using SubEncoder for multi-vector retrieval across different granularities.

Model | Sentence-Level | Document-Level
---|---|---
P@1 | R@5 | P@1 | R@5
GTRbase | 49.35 | 77.01 | 51.93 | 81.97
Sentence-T5base | 50.59 | 79.37 | 45.27 | 77.10
SubEncoder (GTR) | 42.94 | 82.27 | 45.04 | 90.13
SubEncoder (ST5) | 43.49 | 81.44 | 45.93 | 89.19
Table 4: Sentence and document retrieval performance of the atomic fact
retrieval task. We evaluate GTRbase and Sentence-T5base variants of
SubEncoder.

###  5.3 Robustness to Input Formats/Boundaries

Although SubEncoder is fine-tuned with data formatted as propositions
specifically, we observe from the C-STS evaluations that the model generalizes
to not necessarily proposition-shaped inputs, as shown in Table 2. In
downstream applications, we would expect the model to generalize to input
token masks with imperfect boundaries, e.g., propositions generated by a model
instead of labeled by humans. Alongside the C-STS evaluation results, which
indirectly support our hypothesis, we conduct a simple evaluation with the
atomic fact retrieval task. Instead of human-annotated queries, we use queries
generated by gpt-3.5-turbo. The evaluation results of the proposition
segmentation performance of gpt-3.5-turbo and the distilled T5-Large model can
be found in Appendix A. We observe that, with a fuzzing token-level Jaccard-
similarity-based metric, most propositions extracted by the model can be
aligned with human-labeled propositions. When we test the atomic fact
retrieval performance on the set of model-generated propositions that can be
fuzzy-matched with the human-annotated ones, we only see a small drop in
performance, e.g., with the GTR-base variant of SubEncoder, precision@1 drops
from 41.21. $\rightarrow$ 39.56, recall@5 drops from 73.14 $\rightarrow$
72.23. We hypothesize that the robustness of proposition boundaries partly
comes from how we train the model. As the labels between proposition pairs are
generated independent of the model-generated fuzzy proposition boundaries, the
model potentially learns to adapt to imperfect proposition boundaries, similar
to the intuition behind unsupervised SimCSE training Gao et al. (2021).

Model | Dim. | Precision@1 | Recall@5
---|---|---|---
SubEncoder (ST5-Large) | 1024 | 42.61 | 72.93
64 | 42.10 (-0.51) | 70.17 (-2.76)
SubEncoder (ST5-Base) | 768 | 40.97 | 72.15
64 | 40.45 (-0.52) | 71.62 (-0.53)
Table 5: The performance difference on the atomic fact retrieval task with vs. without reducing the output dimensionality of SubEncoder. Index | Num. Entries | Dim. | Index Size
---|---|---|---
Propositions | 270M | 64 | 62GB
dpr-100w | 21M | 768 | 61GB
Table 6: The resulting index size with proposition-level indexing with
compressed dimension, compared to a DPR index of 100-word blocks Karpukhin et
al. (2020).

###  5.4 Offline Indexing and Compression

With the promising performance gain from SubEncoder in the atomic fact
retrieval task, we discuss and assess the possibility of applying SubEncoder
for fine-grained retrieval on larger-scale corpora, which involves offline
indexing and caching the encoded corpora. In our case, the indexing happens on
the level of atomic propositions, where we need to store one embedding for
every atomic proposition in the corpora. Compared to document-level indexing,
indexing on the proposition level would result in a prohibitively large index
size. In previous works Lee et al. (2021b), this is commonly addressed with
techniques such as product quantization Jegou et al. (2010) to compress index
size or approximate nearest neighbor search Malkov and Yashunin (2018) for
faster inference.

Orthogonal to the two techniques above, we study a simpler yet effective
compression strategy by reducing the output dimension of SubEncoder. In the
context of sentence encoders, Wang et al. (2023) discover that reducing the
output dimensionality during training generally incurs minimal downstream
performance loss. Following this idea, we finetune the Sentence T5 base and
large variants of SubEncoder with a bottlenecked output dimension of 64
instead of the original output dimensions of 1024 and 768, respectively. Table
5 shows the performance comparison when evaluated on the atomic fact retrieval
task. Overall, we observe a very small performance drop while gaining
12$\times$ to 16$\times$ reduction in output embedding size.

To demonstrate the implication of this in practice, we use the Sentence T5
large variant of SubEncoder to encode and index an English Wikipedia dump from
2021/10/13, as used by Bohnet et al. (2022). We segment all sentences in
Wikipedia into propositions with the T5-large model (section 3.3). This
results in $\tilde{~}{}270$M propositions from 5.3M Wikipedia pages. Table 6
shows the resulting index. The resulting size of 62GB is close to a prebuilt
(uncompressed) dense passage retrieval (DPR) index on the level of 100-word
blocks Karpukhin et al. (2020). We see that decreasing the output dimension of
the embeddings helps in reducing the cached index size. It is worth noting
that compared to the document-level index, we still expect the query speed of
the index to increase slightly due to the increase in the number of entries.
However, in practice, we observe a reasonable overall time and space
complexity involved in offline indexing and online similarity querying on the
proposition-level.

##  6 Conclusion

We introduce sub-sentence encoders, a contrastive learning framework for
learning contextual embeddings for semantic units on the sub-sentence level.
Beyond the use cases covered in the paper, the sub-sentence encoder
architecture could potentially serve as the backbone for any cross-document
information linking tasks in context, and the learning objectives could
potentially apply to a broader range of tasks with various granularity of
information, e.g., linking sentences or spans within different documents Ma et
al. (2023). We hope that the findings in this paper will facilitate further
exploration along these directions.

## Limitations

This work mostly serves as exploratory work to validate the idea behind sub-
sentence encoder architecture and learning objectives. We acknowledge the
limited scale of our experiments, specifically in terms of the languages
supported by the model. In our experiments, we explore the idea of _sub-
sentence encoder_ with English text only. However, the techniques described in
the paper for sampling training data and training the _sub-sentence encoder_
can be applied to other languages as well. We leave exploration on
multilingual _sub-sentence encoder_ for future work.

## Acknowledgements

The authors would like to thank Alex Fabrikant, Jianmo Ni, and Tal Schuster
for the discussions leading to the development of this idea. The authors thank
Xinran Zhao, Kaixin Ma, Vivek Gupta, and Xiaodong Yu for valuable feedback on
the project and the paper presentation.

## References

  * Agirre et al. (2012) Eneko Agirre, Daniel Cer, Mona Diab, and Aitor Gonzalez-Agirre. 2012.  SemEval-2012 task 6: A pilot on semantic textual similarity.  In _*SEM 2012: The First Joint Conference on Lexical and Computational Semantics – Volume 1: Proceedings of the main conference and the shared task, and Volume 2: Proceedings of the Sixth International Workshop on Semantic Evaluation (SemEval 2012)_ , pages 385–393, Montréal, Canada. Association for Computational Linguistics.
  * Amplayo et al. (2022) Reinald Kim Amplayo, Peter J Liu, Yao Zhao, and Shashi Narayan. 2022.  Smart: Sentences as basic units for text evaluation.  In _The Eleventh International Conference on Learning Representations_.
  * Bird et al. (2009) Steven Bird, Ewan Klein, and Edward Loper. 2009.  _Natural language processing with Python: analyzing text with the natural language toolkit_.  " O’Reilly Media, Inc.".
  * Bohnet et al. (2022) Bernd Bohnet, Vinh Q Tran, Pat Verga, Roee Aharoni, Daniel Andor, Livio Baldini Soares, Jacob Eisenstein, Kuzman Ganchev, Jonathan Herzig, Kai Hui, et al. 2022.  Attributed question answering: Evaluation and modeling for attributed large language models.  _arXiv preprint arXiv:2212.08037_.
  * Bromley et al. (1993) Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. 1993.  Signature verification using a" siamese" time delay neural network.  _Advances in neural information processing systems_ , 6.
  * Cer et al. (2018) Daniel Cer, Yinfei Yang, Sheng-yi Kong, Nan Hua, Nicole Limtiaco, Rhomni St. John, Noah Constant, Mario Guajardo-Cespedes, Steve Yuan, Chris Tar, Brian Strope, and Ray Kurzweil. 2018.  Universal sentence encoder for English.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 169–174, Brussels, Belgium. Association for Computational Linguistics.
  * Chen et al. (2023a) Jifan Chen, Grace Kim, Aniruddh Sriram, Greg Durrett, and Eunsol Choi. 2023a.  Complex claim verification with evidence retrieved in the wild.  _arXiv preprint arXiv:2305.11859_.
  * Chen et al. (2023b) Sihao Chen, Senaka Buthpitiya, Alex Fabrikant, Dan Roth, and Tal Schuster. 2023b.  PropSegmEnt: A large-scale corpus for proposition-level segmentation and entailment recognition.  In _Findings of the Association for Computational Linguistics: ACL 2023_ , pages 8874–8893, Toronto, Canada. Association for Computational Linguistics.
  * Chen et al. (2019) Sihao Chen, Daniel Khashabi, Wenpeng Yin, Chris Callison-Burch, and Dan Roth. 2019.  Seeing things from a different angle:discovering diverse perspectives about claims.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 542–557, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Choi et al. (2021) Eunsol Choi, Jennimaria Palomaki, Matthew Lamm, Tom Kwiatkowski, Dipanjan Das, and Michael Collins. 2021.  Decontextualization: Making sentences stand-alone.  _Transactions of the Association for Computational Linguistics_ , 9:447–461.
  * Conneau et al. (2017) Alexis Conneau, Douwe Kiela, Holger Schwenk, Loïc Barrault, and Antoine Bordes. 2017.  Supervised learning of universal sentence representations from natural language inference data.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 670–680, Copenhagen, Denmark. Association for Computational Linguistics.
  * Deshpande et al. (2023) Ameet Deshpande, Carlos E Jimenez, Howard Chen, Vishvak Murahari, Victoria Graf, Tanmay Rajpurohit, Ashwin Kalyan, Danqi Chen, and Karthik Narasimhan. 2023.  CSTS: Conditional Semantic Textual Similarity.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_.
  * Falcon and The PyTorch Lightning team (2019) William Falcon and The PyTorch Lightning team. 2019.  PyTorch Lightning.
  * Gao et al. (2023a) Luyu Gao, Zhuyun Dai, Panupong Pasupat, Anthony Chen, Arun Tejasvi Chaganty, Yicheng Fan, Vincent Zhao, Ni Lao, Hongrae Lee, Da-Cheng Juan, and Kelvin Guu. 2023a.  RARR: Researching and revising what language models say, using language models.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 16477–16508, Toronto, Canada. Association for Computational Linguistics.
  * Gao et al. (2021) Tianyu Gao, Xingcheng Yao, and Danqi Chen. 2021.  SimCSE: Simple contrastive learning of sentence embeddings.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 6894–6910, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Gao et al. (2023b) Tianyu Gao, Howard Yen, Jiatong Yu, and Danqi Chen. 2023b.  Enabling large language models to generate text with citations.  _arXiv preprint arXiv:2305.14627_.
  * Jegou et al. (2010) Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010.  Product quantization for nearest neighbor search.  _IEEE transactions on pattern analysis and machine intelligence_ , 33(1):117–128.
  * Kamoi et al. (2023) Ryo Kamoi, Tanya Goyal, Juan Diego Rodriguez, and Greg Durrett. 2023.  Wice: Real-world entailment for claims in wikipedia.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_.
  * Karpukhin et al. (2020) Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020.  Dense passage retrieval for open-domain question answering.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6769–6781, Online. Association for Computational Linguistics.
  * Khattab and Zaharia (2020) Omar Khattab and Matei Zaharia. 2020.  Colbert: Efficient and effective passage search via contextualized late interaction over bert.  In _Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval_ , pages 39–48.
  * Khosla et al. (2020) Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan. 2020.  Supervised Contrastive Learning.  _Advances in neural information processing systems_ , 33:18661–18673.
  * Kuhn (1955) Harold W Kuhn. 1955.  The Hungarian method for the assignment problem.  _Naval research logistics quarterly_ , 2(1-2):83–97.
  * Lee et al. (2021a) Jaewoong Lee, Heejoon Lee, Hwanhee Lee, and Kyomin Jung. 2021a.  Learning to select question-relevant relations for visual question answering.  In _Proceedings of the Third Workshop on Multimodal Artificial Intelligence_ , pages 87–96, Mexico City, Mexico. Association for Computational Linguistics.
  * Lee et al. (2021b) Jinhyuk Lee, Alexander Wettig, and Danqi Chen. 2021b.  Phrase retrieval learns passage retrieval, too.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 3661–3672, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Liu et al. (2023) Nelson F Liu, Tianyi Zhang, and Percy Liang. 2023.  Evaluating verifiability in generative search engines.  _arXiv preprint arXiv:2304.09848_.
  * Ma et al. (2023) Kaixin Ma, Hao Cheng, Yu Zhang, Xiaodong Liu, Eric Nyberg, and Jianfeng Gao. 2023.  Chain-of-skills: A configurable model for open-domain question answering.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1599–1618, Toronto, Canada. Association for Computational Linguistics.
  * Malaviya et al. (2023) Chaitanya Malaviya, Subin Lee, Sihao Chen, Elizabeth Sieber, Mark Yatskar, and Dan Roth. 2023.  Expertqa: Expert-curated questions and attributed answers.  _arXiv preprint arXiv:2309.07852_.
  * Malkov and Yashunin (2018) Yu A Malkov and Dmitry A Yashunin. 2018.  Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs.  _IEEE transactions on pattern analysis and machine intelligence_ , 42(4):824–836.
  * Milbauer et al. (2023a) Jeremiah Milbauer, Ziqi Ding, Zhijin Wu, and Tongshuang Wu. 2023a.  From nuisance to news sense: Augmenting the news with cross-document evidence and context.  _arXiv preprint arXiv:2310.04592_.
  * Milbauer et al. (2023b) Jeremiah Milbauer, Annie Louis, Mohammad Javad Hosseini, Alex Fabrikant, Donald Metzler, and Tal Schuster. 2023b.  LAIT: Efficient multi-segment encoding in transformers with layer-adjustable interaction.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 10251–10269, Toronto, Canada. Association for Computational Linguistics.
  * Min et al. (2023) Sewon Min, Kalpesh Krishna, Xinxi Lyu, Mike Lewis, Wen-tau Yih, Pang Wei Koh, Mohit Iyyer, Luke Zettlemoyer, and Hannaneh Hajishirzi. 2023.  FActScore: Fine-grained atomic evaluation of factual precision in long form text generation.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_.
  * Morris et al. (2023) John X Morris, Volodymyr Kuleshov, Vitaly Shmatikov, and Alexander M Rush. 2023.  Text embeddings reveal (almost) as much as text.  _arXiv preprint arXiv:2310.06816_.
  * Ni et al. (2022a) Jianmo Ni, Gustavo Hernandez Abrego, Noah Constant, Ji Ma, Keith Hall, Daniel Cer, and Yinfei Yang. 2022a.  Sentence-t5: Scalable sentence encoders from pre-trained text-to-text models.  In _Findings of the Association for Computational Linguistics: ACL 2022_ , pages 1864–1874, Dublin, Ireland. Association for Computational Linguistics.
  * Ni et al. (2022b) Jianmo Ni, Chen Qu, Jing Lu, Zhuyun Dai, Gustavo Hernandez Abrego, Ji Ma, Vincent Zhao, Yi Luan, Keith Hall, Ming-Wei Chang, and Yinfei Yang. 2022b.  Large dual encoders are generalizable retrievers.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 9844–9855, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Nie et al. (2020) Yixin Nie, Adina Williams, Emily Dinan, Mohit Bansal, Jason Weston, and Douwe Kiela. 2020.  Adversarial NLI: A new benchmark for natural language understanding.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 4885–4901, Online. Association for Computational Linguistics.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019.  Pytorch: An imperative style, high-performance deep learning library.  _Advances in neural information processing systems_ , 32.
  * Qin and Van Durme (2023) Guanghui Qin and Benjamin Van Durme. 2023.  Nugget: Neural agglomerative embeddings of text.  In _Proceedings of the 40th International Conference on Machine Learning_ , ICML’23. JMLR.org.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _Journal of Machine Learning Research_ , 21(140):1–67.
  * Rashkin et al. (2023) Hannah Rashkin, Vitaly Nikolaev, Matthew Lamm, Lora Aroyo, Michael Collins, Dipanjan Das, Slav Petrov, Gaurav Singh Tomar, Iulia Turc, and David Reitter. 2023.  Measuring attribution in natural language generation models.  _Computational Linguistics_ , pages 1–64.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-BERT: Sentence embeddings using Siamese BERT-networks.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 3982–3992, Hong Kong, China. Association for Computational Linguistics.
  * Rudinger et al. (2017) Rachel Rudinger, Kevin Duh, and Benjamin Van Durme. 2017.  Skip-prop: Representing sentences with one vector per proposition.  In _IWCS 2017 — 12th International Conference on Computational Semantics — Short papers_.
  * Schuster et al. (2022) Tal Schuster, Sihao Chen, Senaka Buthpitiya, Alex Fabrikant, and Donald Metzler. 2022.  Stretching sentence-pair nli models to reason over long documents and clusters.  In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , pages 394–412.
  * Seo et al. (2019) Minjoon Seo, Jinhyuk Lee, Tom Kwiatkowski, Ankur Parikh, Ali Farhadi, and Hannaneh Hajishirzi. 2019.  Real-time open-domain question answering with dense-sparse phrase index.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4430–4441, Florence, Italy. Association for Computational Linguistics.
  * Sohn (2016) Kihyuk Sohn. 2016.  Improved deep metric learning with multi-class n-pair loss objective.  _Advances in neural information processing systems_ , 29.
  * Wang and Yu (2023) Hongwei Wang and Dong Yu. 2023.  Going beyond sentence embeddings: A token-level matching algorithm for calculating semantic textual similarity.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 563–570.
  * Wang et al. (2023) Hongwei Wang, Hongming Zhang, and Dong Yu. 2023.  On the dimensionality of sentence embeddings.  _arXiv preprint arXiv:2310.15285_.
  * Zellers et al. (2019) Rowan Zellers, Ari Holtzman, Hannah Rashkin, Yonatan Bisk, Ali Farhadi, Franziska Roesner, and Yejin Choi. 2019.  Defending against neural fake news.  _NeurIPS_.
  * Zhou et al. (2022) Ben Zhou, Kyle Richardson, Xiaodong Yu, and Dan Roth. 2022.  Learning to decompose: Hypothetical question decomposition based on comparable texts.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 2223–2235, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.

Model | Jaccard $\theta=0.8$ | Jaccard $\theta=0.5$
---|---|---
Precision | Recall | F1 | Precision | Recall | F1
Systems used in this paper
GPT-3.5-turbo | 35.79 | 31.65 | 33.60 | 71.52 | 63.87 | 67.48
T5-Large (w/ GPT3.5 training data) | 35.91 | 31.70 | 33.68 | 70.27 | 63.39 | 66.65
Systems fine-tuned on PropSegmEnt Chen et al. (2023b)
Bert-Large | $34.97$ | $33.42$ | $34.17$ | $67.42$ | $64.17$ | $65.75$
T5-Large | $55.95$ | $55.05$ | $55.50$ | $78.03$ | $76.74$ | $77.38$
Table 7: Sentence segmentation performance of systems used in this paper when
evaluated in zero-shot settings on PropSegmEnt. We include the performance of
models trained on PropSegmEnt reported by Chen et al. (2023b) as a reference.

##  Appendix A Proposition Segmentation

In this section, we provide details on the few-shot prompt and distilled
T5-large model we use for segmenting sentences into propositions. We provide
evaluations the two methods against PropSegmEnt Chen et al. (2023b).

###  A.1 Prompt for Proposition Segmentation

We use the following prompt with gpt-3.5-turbo to generate the initial set of
seed training data for segmenting sentences into propositions. We provide one
example from PropSegmEnt for in-context learning demonstration. We process
$\tilde{~}{}23,000$ sentence pairs with the prompt, which generates a total of
44,970 sentences with propositions, after filtering out malformed and empty
generations.

Prompt for sentence $\Rightarrow$ propositions Given the following sentence,
tell me what claims they are making. Please split the sentence as much as
possible, but do not include information not in the sentence. Sentence: The
Andy Warhol Museum in his hometown, Pittsburgh, Pennsylvania, contains an
extensive permanent collection of art. Claims: 1. The Andy Warhol Museum is in
Pittsburgh. 2. Andy Warhol’s hometown is in Pittsburgh. 3. Pittsburgh is in
Pennsylvania. 4. The Andy Warhol Museum contains an extensive permanent
collection of art. Sentence: (input sentence) Claims:

###  A.2 Training detail of T5 for proposition segmentation

We finetune a T5-large Raffel et al. (2020) model on a seed set of training
data generated via GPT-3.5-turbo. We use an AdamW optimizer with a constant
learning rate of $1e^{-4}$, with a batch size of 128. We train the model for 3
epochs on $8$x Nvidia A6000s, which takes 2 hours to finish.

###  A.3 Converting propositions from natural language to token masks

Given a proposition of a sentence in the natural language form, we convert and
align it to a subset of tokens from the original sentence with the following
steps. We first tokenize and lemmatize each of the tokens in the proposition
using NLTK Bird et al. (2009). Next, we construct an affinity matrix between
the set of lemmatized tokens from the proposition and the sentence. With the
matrix, we assign tokens with identical lemmas are assigned a similarity score
of 1. To break ties between multiple token matches, we apply a 2D-convolution
filter on the affinity matrix, which adds a small score offset for other token
matches in a context window of three tokens. With the affinity matrix, we find
the optimal alignment between the proposition and sentence tokens with max
bipartite matching on the affinity matrix with the Hungarian algorithm Kuhn
(1955).

###  A.4 Proposition Segmentation Evaluation on PropSegmEnt

To evaluate the quality of propositions extracted via our pipeline, we
evaluate the proposition segmentation performance on PropSegmEnt. The results
are shown in Table 7. For details of the Jaccard similarity based evaluation
metrics for proposition segmentation, please refer to Chen et al. (2023b).

##  Appendix B Training and Hyperparameters

We implement the sub-sentence encoder architecture with pytorch Paszke et al.
(2019) and pytorch-lightning Falcon and The PyTorch Lightning team (2019). All
of our sub-encoder model variants are trained on 8$\times$ Nvidia A6000 GPUs
with 48GB VRAM.

##### Distributed Training

Since we adopt in-batch contrastive loss, we scale up the number of negative
examples by increasing the batch size with distributed training across GPUs.
We distribute training processes across GPU nodes via Distributed Data
Parallel (DDP). Specifically, given a minibatch of $N_{gpu}\times M$
sentences, each GPU gets $M$ sentences, which gets forwarded through model
parameters on the GPU. Next, we gather and copy all the encoded propositions
along with gradients to each of the GPUs, so that each GPU has the full
minibatch for loss computation. Each GPU process backpropagates the loss
independently on its copy of the model parameters.

##### Hyperparameters

For all experiments, we use the temperature parameter $\tau=0.01$ for the
supervised contrastive loss, with AdamW optimizer. For Sentence-T5 and GTR
variants of the model, we use learning rate of 1$e^{-4}$. For SimCSE, we use
learning rate of $5e^{-5}$. We train the models for 10 epochs, and a linear
decay is applied at the end of each epoch, which decreases the learning to 0
after 10 epochs. We select the best checkpoint based on validation loss after
each epoch.

##  Appendix C Evaluation Setup

###  C.1 Representing Atomic Propostion with Sentence Encoder

With the atomic fact retrieval evaluation on PropSegmEnt, since the ground
truth query and target propositions are both represented in the format of
token masks, we experiment with a few different strategies of formatting the
input for sentence encoders. Specifically, with respect to the input sentence
and the token masks denoting the proposition, here are the different
strategies in consideration.

  1. 1.

Mask pooling only. Encoder has full attention, apply proposition mask during
pooling. Note that this is the same method we use for the sub-sentence
encoder.

  2. 2.

Full mask. Apply proposition mask as attention mask during both encoding and
pooling.

  3. 3.

Token subset only. Take the subset of tokens and discard the rest. Feed only
the subset of tokens as a sequence to the encoder and pooling layer.

When tested on a small validation set for the atomic fact retrieval task, we
generally observe that mask pooling only yields the best result across most
models, except for the two compact models, i.e. MiniLM-L6-v2 and
DistilRoberta. On the two compact models, we see full mask outperforming the
mask pooling only strategy by a small margin. We observe that with the third
strategy token subset only, the validation performance trails behind the other
two across all models.


# MATCHA: A Fast and Energy-Efficient Accelerator for Fully Homomorphic
Encryption over the Torus

Lei Jiang<EMAIL_ADDRESS>Indiana University ,  Qian Lou<EMAIL_ADDRESS>Indiana
University and  Nrushad Joshi<EMAIL_ADDRESS>Indiana University

(2022)

###### Abstract.

Fully Homomorphic Encryption over the Torus (TFHE) allows arbitrary
computations to happen directly on ciphertexts using homomorphic logic gates.
However, each TFHE gate on state-of-the-art hardware platforms such as GPUs
and FPGAs is extremely slow ($>0.2ms$). Moreover, even the latest FPGA-based
TFHE accelerator cannot achieve high energy efficiency, since it frequently
invokes expensive double-precision floating point FFT and IFFT kernels. In
this paper, we propose a fast and energy-efficient accelerator, MATCHA, to
process TFHE gates. MATCHA supports aggressive bootstrapping key unrolling to
accelerate TFHE gates without decryption errors by approximate multiplication-
less integer FFTs and IFFTs, and a pipelined datapath. Compared to prior
accelerators, MATCHA improves the TFHE gate processing throughput by
$2.3\times$, and the throughput per Watt by $6.3\times$.

accelerator, fully homomorphic encryption, TFHE, bootstrapping

††journalyear: 2022††copyright: acmcopyright††conference: The 59th Annual
Design Automation Conference 2022; July 10–14, 2022; San Francisco, CA,
USA††booktitle: The 59th Annual Design Automation Conference 2022 (DAC ’22),
July 10–14, 2022, San Francisco, CA, USA††price: 15.00††ccs: Hardware
Application-specific VLSI designs††ccs: Security and privacy Cryptography

##  1\. Introduction

In cloud computing, it is dangerous for clients upload their raw data to
untrusted cloud servers, due to potential data breaches. Moreover, recent
legislation (Hoofnagle:ICTL2019, ) requires cloud computing enterprises to
provide sufficient security for clients’ personal data.

Recently, Fully Homomorphic Encryption (FHE) (Chillotti:JC2018, ;
Brakerski:TCT2014, ; Cheon:CEA2020, ) emerges as one of the most promising
cryptographic solutions to allowing arbitrary computations on encrypted data
in untrusted cloud servers. Compared to Secure Multi-Party Computation, FHE
requires neither frequent communications between clients and cloud servers,
nor significant circuit garbling overhead on the client side. FHE enables a
client to encrypt her data and to send only ciphertexts to a cloud server that
can directly evaluate homomorphic functions, e.g., encrypted neural inferences
(Brutzkus:ICML2019, ) or encrypted general-purpose computing
(Matsuoka:SECURITY2021, ), on the ciphertexts. When all computations are
completed, the server returns the encrypted results to the client without
learning any intermediate or final output, due to the end-to-end encrypted
data flow. Only the client can decrypt the results by her secret key.

Table 1. The comparison between various HE schemes. Scheme | FHE Op. | Data Type | Bootstrapping
---|---|---|---
BGV (Brakerski:TCT2014, ) | mult, add | integer | $\sim 800s$
BFV (Fan:CARCH2012, ) | mult, add | integer | $>1000s$
CKKS (Cheon:CEA2020, ) | mult, add | fixed point | $\sim 500s$
FHEW (DUCAS:ICTACT2015, ) | Boolean | binary | $<1s$
TFHE (Chillotti:JC2018, ) | Boolean | binary | $\mathbf{13ms}$

Among all FHE cryptosystems, FHE over the Torus (TFHE) (Chillotti:JC2018, ) is
the most efficient scheme supporting arbitrary operations with an unlimited
computation depth, as shown in Table 1. First, TFHE supports arbitrary
operations by various homomorphic Boolean logic gates. Traditional FHE schemes
such as BGV (Brakerski:TCT2014, ), BFV (Fan:CARCH2012, ), and CKKS
(Cheon:CEA2020, ) can perform only homomorphic additions and multiplications,
while both FHEW (DUCAS:ICTACT2015, ) and TFHE (Chillotti:JC2018, ) can enable
homomorphic Boolean algebra, e.g., NAND, XOR, and XNOR gates. Second, TFHE
obtains the fastest bootstrapping. Each FHE operation inevitably introduces a
certain amount of noise into the ciphertext. If there are too many FHE
operations on the computational critical path, the accumulated noise in the
ciphertext may exceed a threshold, and thus the ciphertext cannot be decrypted
successfully. To support an unlimited computation depth, a FHE scheme has to
periodically invoke a bootstrapping operation to decrease the amount of noise
in the ciphertext. The bootstrapping operation is extremely expensive for BGV,
BFV, and CKKS. For example, a BGV bootstrapping typically costs several
hundred seconds (Halevi:ICTACT2015, ). Therefore, these FHE schemes can
support only a limited computation depth by designing a large enough noise
budget. Although a bootstrapping of FHEW takes only $1s$, TFHE can obtain a
even faster bootstrapping, i.e., a TFHE bootstrapping requires only $13ms$ on
a CPU. By fast bootstrapping, TFHE allows an unlimited computation depth.

Unfortunately, a TFHE-based complex circuit consisting of multiple TFHE gates
is still extremely slow. For instance, a TFHE-based simple RISC-V CPU
(Matsuoka:SECURITY2021, ) comprising thousands of TFHE gates can run at only
$1.25Hz$. In order to realize practical TFHE-based computing, it is critical
to accelerate TFHE gates by specialized hardware. However, TFHE is only well-
implemented on CPUs (Toufique:HOST2020, ) and GPUs (Dai:CUFHE2018, ). Although
a recent work (Serhan:SPSL2021, ) accelerates TFHE gates on a FPGA, the TFHE
gate latency on the FPGA is much longer than that on a GPU. To the best of our
knowledge, there is no ASIC-based hardware accelerator for TFHE.

In this paper, we propose a fast and energy-efficient accelerator, MATCHA, to
process TFHE gates. We find that the bootstrapping dominates the latency of
all TFHE logic operations. The kernels of fast Fourier transform (FFT) and
inverse FFT (IFFT) are the bottlenecks in a bootstrapping operation. MATCHA is
designed to accelerate the TFHE bootstrapping using approximate
multiplication-less integer FFTs and IFFTs. We also propose a pipelined
datapath for MATCHA to support aggressive bootstrapping key unrolling
(Zhou:ACCESS2018, ; Bourse:CRYPTO2018, ) that invokes FFTs and IFFTs less
frequently. Our contributions can be summarized as follows.

  * •

In order to fully take advantage of the error tolerance capability of TFHE,
MATCHA accelerates polynomial multiplications by approximate multiplication-
less integer FFTs and IFFTs requiring only additions and binary shifts.
Although approximate FFTs and IFFTs introduce errors in each ciphertext, the
ciphertext can still be correctly decrypted, since the errors can be rounded
off along with the noise during decryption.

  * •

We build a pipelined datapath consisting of TGSW clusters and external product
cores to enable aggressive bootstrapping key unrolling that invokes FFTs and
IFFTs less frequently during a bootstrapping operation. The datapath uses
different register banks to serve sequential memory accesses during TGSW
operations, and irregular memory accesses during FFTs and IFFTs.

  * •

We implemented, evaluated, and compared MATCHA against prior TFHE hardware
accelerators. Compared to prior accelerators, MATCHA improves the TFHE gate
processing throughput by $2.3\times$, and the throughput per Watt by
$6.3\times$.

##  2\. Background

FHE. Fully Homomorphic Encryption (FHE) enables arbitrary operations on
ciphertexts. A FHE operation $\diamond$ is defined if there is another
operation $\star$ such that $Dec[Enc(x_{1})\diamond
Enc(x_{2})]=Dec[Enc(x_{1}\star x_{2})]$, where $x_{1}$ and $x_{2}$ are input
plaintexts, $Enc$ indicates encryption, and $Dec$ is decryption.

Notation. $\mathbb{T}$ denotes the torus of real numbers modulo 1,
$\mathbb{R}/\mathbb{Z}$. For any ring $\mathcal{R}$, polynomials of the
variable $X$ with coefficients in $\mathcal{R}$ are represented by
$\mathcal{R}[X]$. We define $\mathbb{R}_{N}[X]:=\mathbb{R}[X]/(X^{N}+1)$,
$\mathbb{Z}_{N}[X]:=\mathbb{Z}[X]/(X^{N}+1)$, and
$\mathbb{T}_{N}[X]:=\mathbb{R}_{N}[X]/\mathbb{Z}_{N}[X]$, which are the ring
of polynomials of variable $X$ with quotient $X^{N}+1$ and real coefficients
modulo 1. $\mathbb{B}\coloneqq\\{0,1\\}$ is a set, and we write vectors in
bold. Given a set $\mathcal{S}$, we write
$\mathbf{s}\xleftarrow{\$}\mathcal{S}$ to indicate that $\mathbf{s}$ is
sampled uniformly at random from $\mathcal{S}$. We write
$e\leftarrow\mathcal{X}$ to denote that $e$ is sampled according to
$\mathcal{X}$.

TFHE. In TFHE (Chillotti:JC2018, ), we assume $m\in\mathbb{B}$ is a plaintext.
The encryption scheme works as follows:

  * •

$Setup(\lambda)$ first selects public parameters $n=n(\lambda)$, and
$\sigma=\sigma(\lambda)$, where $\lambda$ is the security parameter. It
samples and produces a secret key $\mathbf{s}\xleftarrow{\$}\mathbb{B}^{n}$.

  * •

$Enc[\mathbf{s},m]$ samples a uniformly random vector
$\mathbf{a}\xleftarrow{\$}\mathbb{T}^{n}$ and a noise
$e\leftarrow\mathcal{D}_{\mathbb{T}_{N}[X],\sigma}$, where
$\mathcal{D}_{\mathbb{T}_{N}[X],\sigma}$ is the Gaussian distribution over
$\mathbb{T}_{N}[X]$ with a standard deviation $\sigma$. It outputs a
ciphertext $(\mathbf{a},b)$, where $b=\mathbf{a}\cdot\mathbf{s}+e+m/2$.

  * •

$Dec[\mathbf{s},(\mathbf{a},b)]$ returns $\lceil
2(b-\mathbf{a}\cdot\mathbf{s})\rfloor$. It outputs plaintext correctly if the
size of noise $e$ is bounded as $|e|<1/4$, since
$2(b-\mathbf{a}\cdot\mathbf{s})=2e+m$, $|2e|<1/2$, and thus $\lceil
2(b-\mathbf{a}\cdot\mathbf{s})\rfloor=m$.

  * •

$Logic[c_{0},c_{1}]$ returns the ciphertext of the result of the logic
operation between two ciphertexts $c_{0}$ and $c_{1}$, and the logic operation
can be XOR, NAND, AND, and OR. A TFHE logic operation involves an addition
between $c_{0}$ and $c_{1}$, and a bootstrapping.

TLWE. TLWE is a torus analogue of the learning with error (LWE) problem
(Brakerski:TCT2014, ). $k$ is a positive integer. $N$ is a power of 2, and
$\mathcal{X}$ is a probability distribution over $\mathbb{R}_{N}[X]$. A TLWE
secret key $\bar{\mathbf{s}}$ is a vector of $k$ polynomials over
$\mathbb{Z}_{N}[X]$ with binary coefficients, denoted as
$\bar{\mathbf{s}}\in\mathbb{R}_{N}[X]^{k}$. Given a polynomial message
$\mu\in\mathbb{T}_{N}[X]$, a TLWE ciphertext of $\mu$ under the key
$\bar{\mathbf{s}}$ is a TLWE sample
$(\bar{\mathbf{a}},\bar{b})\in\mathbb{T}_{N}[X]^{k}\times\mathbb{T}_{N}[X]$,
where $\bar{\mathbf{a}}\leftarrow\mathbb{T}_{N}[X]^{k}$ and
$\bar{b}=\bar{\mathbf{s}}\cdot\bar{\mathbf{a}}+\mu+e$, where
$e\leftarrow\mathcal{X}$.

TGSW. TGSW is the matrix extension of TLWE. Each row of a TGSW sample is a
TLWE sample. An external product $\boxdot$ that maps $\boxdot$: $TGSW\times
TWLE\rightarrow TLWE$ can be defined by TFHE (Chillotti:JC2018, ). The product
of the TGSW ciphertext of a polynomial message
$\mu_{TGSW}\in\mathbb{T}_{N}[X]$ and the TLWE ciphertext of a polynomial
message $\mu_{TLWE}\in\mathbb{T}_{N}[X]$ becomes a TLWE ciphertext of a
polynomial message $\mu_{TGSW}\cdot\mu_{TLWE}\in\mathbb{T}_{N}[X]$

Input: A TLWE sample $(\mathbf{a},b)$ whose plaintext is $m_{in}$; a constant
$m_{set}$; a bootstrapping key $\mathbf{BK_{s\rightarrow
s^{\prime\prime}}}_{,\alpha}$; and a key-switching key
$\mathbf{KS_{s^{\prime}\rightarrow s}}_{,\gamma^{\prime}}$
($\mathbf{s^{\prime}}=\mathbf{KeyExtract(s^{\prime\prime})}$).

Output: A TLWE sample encrypting $m_{out}=m_{in}\cdot m_{set}$.

$\mu=m_{set}/2$, $\mu^{\prime}=\mu/2$ /* Initialization */

$\bar{b}=\lceil 2Nb\rfloor$, $\bar{a_{i}}=\lceil 2Na_{i}\rfloor$ for each
$i\in[1,n]$ /* Rounding */

1 $testv=(1+X+\ldots+X^{N+1})\cdot X^{N/2}\cdot\mu^{\prime}$

$ACC\leftarrow X^{\bar{b}}\cdot(0,testv)$ /*
$ACC=TLWE(X^{(\bar{b}-\bar{a}s)}\cdot testv)$ */

2 for  _$i=1$ to $n$_ do

3 $\mathbf{BK}_{i}=\mathbf{h}+(X^{-\bar{a_{i}}}-1)\cdot\mathbf{BK}_{i}$

$ACC\leftarrow\mathbf{BK}_{i}\boxdot ACC$ /* BlindRotate */

4

$\mathbf{u}=(0,\mu^{\prime})+SampleExtract(ACC)$ /* Extract */

return $KeySwitch_{KS}(\mathbf{u})$ /* KeySwitch */

Algorithm 1 The bootstrapping operation of TFHE.

Bootstrapping. Each TFHE logic operation inevitably introduces a certain
amount of noise into the resulting ciphertext. A bootstrapping has to be
performed to remove the noise at the end of each TFHE logic operation. In
various TFHE logic operations, the bootstrapping step is the largest
performance bottleneck. The details of a TFHE bootstrapping can be viewed in
(Chillotti:JC2018, ). The bootstrapping procedure is shown in Algorithm 1. The
dimension of the TLWE sample is set as $k=1$ (Chillotti:JC2018, ), which means
that the TLWE sample is simply the Ring-LWE sample
$(\bar{a},\bar{b})\in\mathbb{T}_{N}[X]\times\mathbb{T}_{N}[X]$. The most
computationally intensive step of a bootstrapping is the homomorphic
decryption in line 1, where the message of $ACC$ becomes a polynomial
$X^{\bar{b}-\bar{\mathbf{a}}\mathbf{s}}\cdot testv$. Particularly,
homomorphically computing
$X^{-\bar{\mathbf{a}}\mathbf{s}}=X^{\sum_{i=1}^{n}-\bar{\mathbf{a}_{i}}\mathbf{s}_{i}}=\prod_{i=1}^{n}X^{-\bar{\mathbf{a}_{i}}\mathbf{s}_{i}}$
involves a great number of polynomial multiplications. Naïvely multiplying two
degree $N$ polynomials has the complexity of $\mathcal{O}(N^{2})$. FFT and
IFFT are used to reduce the complexity of a polynomial multiplication to
$\mathcal{O}(N\log(N))$ (Dai:CUFHE2018, ), where $N$ is the degree of
polynomials.

Figure 1. Latency breakdown.

Figure 2. The depth-first FFT.

Figure 3. The lifting butterfly w/o multiplication.

Torus Implementation. Theoretically, the scale invariant scheme of TFHE is
defined over the real torus $\mathbb{T}$, where all operations are modulo 1.
But TFHE rescales the elements over $\mathbb{T}$ by a factor $2^{32}$, and
maps them to 32-bit integers (Chillotti:JC2018, ), since it can work with
approximations. Therefore, TFHE does not have to actively perform modular
reduction, since all operations on 32-bit integers implicitly call a native
and automatic mod $2^{32}$ operation. To maintain high conversion accuracy,
TFHE uses 64-bit double-precision floating point FFT and IFFT kernels
(Chillotti:JC2018, ).

##  3\. Related Work and Motivation

Related Work. Except some TFHE implementations on CPUs (Chillotti:JC2018, ),
GPUs (Dai:CUFHE2018, ), and FPGAs (Serhan:SPSL2021, ), there is no specialized
hardware accelerator that can process TFHE. A TFHE accelerator is different
from the accelerators designed for other FHE schemes such as BGV, BFV, and
CKKS in two points. First, although few prior accelerators
(Feldmann:MICRO2021, ) support BGV and CKKS bootstrapping along a tiny
multiplicative depth datapath, most prior works (Riazi:ASPLOS2020, ;
Roy:HPCA2019, ; Ahmet:DATE2020, ) design hardware accelerators to process
leveled BFV or CKKS homomorphic operations without bootstrapping. However, a
TFHE accelerator must perform bootstrapping at the end of each TFHE gate.
Second, BGV, BFV, and CKKS require NTT and INTT kernels, while TFHE needs only
FFT and IFFT kernels without modular reduction.

Motivation. A TFHE gate performs not only polynomial additions but also a
bootstrapping (FFT+IFFT+other) that costs 99% of the gate latency on a CPU, as
shown in Figure 3. Therefore, in order to shorten the latency of TFHE gates,
we need to accelerate the bootstrapping step in TFHE gates. Moreover, FFTs and
IFFTs consume 80% of the bootstrapping latency in various TFHE gates. In order
to accelerate TFHE gates, MATCHA adopts approximate multiplication-less
integer FFTs and IFFTs, and uses a pipelined datapath to support aggressive
bootstrapping key unrolling (Zhou:ACCESS2018, ; Bourse:CRYPTO2018, ).

##  4\. MATCHA

###  4.1. Approximate Fast Integer FFT and IFFT

Despite the fact that elements over $\mathbb{T}$ are mapped to 32-bit
integers, TFHE still uses 64-bit double-precision floating point FFT and IFFT
kernels, since 32-bit integer or single-precision floating point FFT and IFFT
kernels are not accurate enough to guarantee the correct decryption of a
ciphertext (Chillotti:JC2018, ). However, processing 64-bit double-precision
floating point FFT and IFFT kernels incurs significant hardware overhead and
power consumption.

Novelty. We first identify the opportunity to use approximate integer FFTs and
IFFTs to accelerate TFHE without decryption errors for MATCHA. It is difficult
to apply approximate NTTs and INTTs in accelerating other FHE schemes, e.g.,
BGV, BFV, and CKKS, which do not include a bootstrapping step after each
homomorphic multiplication or addition. The errors introduced by approximate
NTTs and INTTs will be quickly accumulated in the ciphertext and result in a
decryption error, if a bootstrapping step cannot be performed in time. On the
contrary, TFHE keeps the approximation errors of integer FFTs and IFFTs in
check by performing a bootstrapping step at the end of each TFHE gate.

Depth-first FFT. Most prior FHE accelerators (Feldmann:MICRO2021, ;
Riazi:ASPLOS2020, ; Roy:HPCA2019, ) perform NTTs and INTTs by the Cooley-Tukey
data flow that introduces irregular memory accesses particularly in its bit-
reversal stage. In order to remove the bit-reversal overhead, a prior ideal-
lattice-based cryptographic accelerator (Liu:TECS2017, ) uses the Cooley-Tukey
flow for NTTs and the Gentlemen-Sande flow for INTTs. These cryptographic
accelerators store a polynomial mod $X^{N}+1$ as a list of $N$ coefficients.
For each multiplication between two polynomials, they execute two NTT kernels
on two polynomials respectively, perform element-wise multiplications, and
then run an INTT kernel on the result. The invoking frequency ratio between
NTTs and INTTs is $2:1$. These FHE accelerators have are many opportunities
(i.e., switchings from NTT to INTT) to reduce the bit-reversal overhead. In
contrast, TFHE saves a polynomial mod $X^{N}+1$ as either a list of $N$
coefficients or the Lagrange half-complex representation consisting in the
complex evaluations of the polynomial over the roots of unity
$exp(i(2j+1)\pi/N)$ for $j\in\llbracket 0,\frac{N}{2}\llbracket$. FFT and IFFT
kernels are required only during the conversion between these two
representations. The invoking frequency ratio between FFTs and IFFTs in a TFHE
gate is $1:4$. As Figure 3 shows, the latency of IFFT kernels is much longer
than FFT kernels. TFHE does not have many opportunities to reduce the bit-
reversal overhead. Instead, for MATCHA, we focus on decreasing the computing
overhead of a single FFT or IFFT kernel. We adopt the depth-first iterative
conjugate-pair FFT (CPFFT) algorithm (Becoulet:TSP2021, ). Unlike the Cooley-
Tukey or Gentlemen-Sande flow, the CPFFT requires only a single complex root
of unity read per radix-4 butterfly. Two butterflies in the same block can
share the same twiddle factor, further halving the number of reads to the
twiddle-factor buffer (Becoulet:TSP2021, ). Moreover, the Cooley-Tukey and
Gentlemen-Sande flows process FFTs/IFFTs stage by stage in a breadth-first
manner, as shown in Figure 3(a). To capture the spatial locality, as Figure
3(b) shows, CPFFT traverses the FFT flow in a depth-first fashion by
completing a sub-transform before moving to the next.

A Multiplication-less Butterfly. The lifting structure (Oraintara:TSP2002, ),
a special type of lattice substrate implemented by cascading identity matrices
with a single nonzero off-diagonal element, is proposed to approximate
multiplications in FFT and IFFT kernels by additions and binary shifts. The
basic lifting step shown in Figure 3(a) can be expressed by
$y_{j}(n)=x_{j}(n)$, $y_{i}(n)=x_{i}(n)+\lceil T_{x_{j}}(n)\rfloor$,
$z_{j}(n)=y_{j}(n)$, and $z_{i}(n)=y_{i}(n)-\lceil T_{y_{j}}(n)\rfloor$, where
$T$ is a lifting coefficient. And thus, the lifting structure with the
rounding operation can achieve integer-to-integer transform. Also, the lifting
and its inverse matrices in this case are represented as
$\begin{bmatrix}1&T\\\ 0&1\end{bmatrix}$ and $\begin{bmatrix}1&T\\\
0&1\end{bmatrix}^{-1}=\begin{bmatrix}1&-T\\\ 0&1\end{bmatrix}$, respectively.
A floating-point lifting coefficient can be quantized as an approximate
dyadic-valued coefficient $\alpha/2^{\beta}$, and hence computed with only
adders and shifters, where we allocate $\beta$ bits to the lifting
coefficient, and $\alpha,\beta\in\mathbb{N}$. For example, a coefficient
$9/128$ can be operated as
$\frac{9}{128}=\frac{2^{3}+2^{0}}{2^{7}}=\frac{1}{2^{4}}+\frac{1}{2^{7}}$.
Hence, the lifting with its coefficient $9/128$ and a rounding operation is
replaced to the summation of 4 and 7 bit-shifters illustrated in Figure 3(b).
The perfect reconstruction in lifting is always kept if floating-point
coefficients are approximated to dyadic-valued coefficients.

Figure 4. The truth table of $X^{-\mkern
1.5mu\overline{\mkern-1.5mua_{2i-1}\mkern-1.5mu}\mkern 1.5mu\cdot
s_{2i-1}-\mkern 1.5mu\overline{\mkern-1.5mua_{2i}\mkern-1.5mu}\mkern
1.5mu\cdot s_{2i}}$.

Figure 5. Bootstrapping key unrolling.

Figure 6. The pipelined MATCHA for aggressive BKU.

###  4.2. Aggressive Bootstrapping Key Unrolling

Bootstrapping Key Unrolling. A TFHE bootstrapping needs to compute external
produces, i.e., $X^{-\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{a}\mkern-1.5mu}\mkern
1.5mu\mathbf{s}}=X^{\sum_{i=1}^{n}-\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{a}_{i}\mkern-1.5mu}\mkern
1.5mu\mathbf{s}_{i}}$ sequentially, thereby becoming the performance
bottleneck of a TFHE gate. Instead, bootstrapping key unrolling (BKU)
(Zhou:ACCESS2018, ; Bourse:CRYPTO2018, ) is proposed to compute
$X^{\sum_{i=1}^{n/2}-\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{a}_{2i-1}\mkern-1.5mu}\mkern
1.5mu\mathbf{s}_{2i-1}-\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{a}_{2i}\mkern-1.5mu}\mkern
1.5mu\mathbf{s}_{2i}}$ in each external product, so that the number of
homomorphic additions can be reduced from $n$ to $n/2$. The secret key
$\mathbf{s}$ is sampled from $\mathbb{B}^{n}$, so $s_{i}\in\\{0,1\\}$, where
$0\leq i\leq n$. Based on the values of $s_{2i}$ and $s_{2i+1}$, the truth
table of $X^{\sum_{i=1}^{n/2}-\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{a}_{2i-1}\mkern-1.5mu}\mkern
1.5mu\mathbf{s}_{2i-1}-\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{a}_{2i}\mkern-1.5mu}\mkern
1.5mu\mathbf{s}_{2i}}$ can be shown in Figure 5. So BKU rewrites $X^{-\mkern
1.5mu\overline{\mkern-1.5mua_{2i-1}\mkern-1.5mu}\mkern 1.5mu\cdot
s_{2i-1}-\mkern 1.5mu\overline{\mkern-1.5mua_{2i}\mkern-1.5mu}\mkern
1.5mu\cdot s_{2i}}$ as $X^{-\mkern
1.5mu\overline{\mkern-1.5mua_{2i-1}\mkern-1.5mu}\mkern 1.5mu-\mkern
1.5mu\overline{\mkern-1.5mua_{2i}\mkern-1.5mu}\mkern 1.5mu}\cdot
s_{2i-1}s_{2i}-X^{-\mkern
1.5mu\overline{\mkern-1.5mua_{2i-1}\mkern-1.5mu}\mkern 1.5mu}\cdot
s_{2i-1}(1-s_{2i})-X^{-\mkern
1.5mu\overline{\mkern-1.5mua_{2i}\mkern-1.5mu}\mkern
1.5mu}\cdot(1-s_{2i-1})s_{2i}-(1-s_{2i-1})(1-s_{2i})$. Due to the fact that
$s_{2i-1}s_{2i}+(1-s_{2i})s_{2i-1}+s_{2i}(1-s_{2i-1})+(1-s_{2i-1})(1-s_{2i})$
is always equal to 1 (Bourse:CRYPTO2018, ), $X^{-\mkern
1.5mu\overline{\mkern-1.5mua_{2i-1}\mkern-1.5mu}\mkern 1.5mu\cdot
s_{2i-1}-\mkern 1.5mu\overline{\mkern-1.5mua_{2i}\mkern-1.5mu}\mkern
1.5mu\cdot s_{2i}}$ can be further simplified to $(X^{-\mkern
1.5mu\overline{\mkern-1.5mua_{2i-1}\mkern-1.5mu}\mkern 1.5mu-\mkern
1.5mu\overline{\mkern-1.5mua_{2i}\mkern-1.5mu}\mkern 1.5mu}-1)\cdot
s_{2i-1}s_{2i}+(X^{-\mkern
1.5mu\overline{\mkern-1.5mua_{2i-1}\mkern-1.5mu}\mkern 1.5mu}-1)\cdot
s_{2i-1}(1-s_{2i})-(X^{-\mkern
1.5mu\overline{\mkern-1.5mua_{2i}\mkern-1.5mu}\mkern
1.5mu}-1)\cdot(1-s_{2i-1})s_{2i}+1$. As Figure 5 shows, BKU encrypts
$s_{2i-1}s_{2i}$, $s_{2i-1}(1-s_{2i})$, and $(1-s_{2i-1})s_{2i}$ as TGSW
ciphertexts, and builds a bootstrapping key bundle to unroll the orginal
bootstrapping key for two times.

Aggressive BKU Performing Badly on CPUs. BKU can be further generalized as

(1) $X^{\sum_{i=1}^{\frac{n}{m}}-\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{a}_{m\cdot i}\mkern-1.5mu}\mkern
1.5mu\mathbf{s}_{m\cdot i}-\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{a}_{m\cdot i+1}\mkern-1.5mu}\mkern
1.5mu\mathbf{s}_{m\cdot i+1}-\ldots-\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{a}_{m\cdot i+m-1}\mkern-1.5mu}\mkern
1.5mu\mathbf{s}_{m\cdot i+m-1}},$

where $m\in[2,n]$. So it is possible to more aggressively unroll the
bootstrapping key by increasing $m$. Although unrolling the bootstrapping key
for two times ($m=2$) reduces the bootstrapping latency by 49%, we find that
further enlarging $m$ beyond 2 even prolongs the bootstrapping latency on a
CPU, as explained in Section 6. Our experimental methodology is described in
Section 5. The reason can be summarized as follows.

  * •

The limited number of cores on a CPU. With an enlarged $m$, there are more
terms in the exponent part of Equation 1. For instance, when $m=4$, there are
15 terms, each of which requires a TGSW scale-and-add operation.
Unfortunately, our CPU baseline has only 8 physical cores. Mapping each terms
to a core, and summing the results from all cores introduce significant
communication overhead.

  * •

More cache conflicts. The size of bootstrapping key increases exponentially
with an enlarged $m$. For example, as Figure 5 shows, instead of a single
bootstrapping key, BKU with $m=2$ requires three bootstrapping keys. Each TGSW
scale-and-add operation happening on a term fetches its corresponding
bootstrapping key to the shared last level cache, generating more cache
conflicts.

  * •

The lack of a pipelined design. As Figure 5 highlights, in each iteration, the
construction of the bootstrapping key bundle $\mathbf{BKB}$ and the external
product operation are executed sequentially. Although it is possible to start
the computation of $\mathbf{BKB}$ for the next iteration and perform the
external product operation of this iteration at the same time, the current BKU
implementation (Zhou:ACCESS2018, ) cannot do this, due to the lack of a
pipelined design.

Figure 7. The architecture of MATCHA (mem. ctrl: memory controller; addr gen.:
address generation; twid: twiddle factor; butt.: butterfly; and shift.:
shifter).

MATCHA for Aggressive BKU. In this paper, we propose a pipeline flow for
MATCHA to support aggressive BKU with a larger $m$. Compared to our CPU
baseline, our pipeline flow can be easily accelerated by a large number of
specialized hardware components including TGSW clusters and External Product
(EP) cores. As Figure 6(a) shows, we divide the bottleneck of a TFHE
bootstrapping into two steps, i.e., the construction of the bootstrapping key
bundle, and the EP operation. A TGSW cluster is used to construct the
bootstrapping key bundle, while an EP core processes EP operations between the
bootstrapping key bundle and $ACC$. ❶ A TGSW cluster consists of a TGSW adder
tree and multiple TGSW scale units, each of which computes one term in the
bootstrapping key bundle, e.g., when $m=2$, $(X^{-\mkern
1.5mu\overline{\mkern-1.5mua_{2i-1}\mkern-1.5mu}\mkern 1.5mu-\mkern
1.5mu\overline{\mkern-1.5mua_{2i}\mkern-1.5mu}\mkern
1.5mu}-1)\cdot\mathbf{BK_{i,0}}$, where $\mathbf{BK_{i,0}}$ is the TGSW
ciphertext of $s_{2i-1}s_{2i}$. And then, the TGSW adder sums all terms and
generates the bootstrapping key bundle. ❷ With the bootstrapping key bundle
($\mathbf{BKB_{i}}$), an EP core computes
$ACC\leftarrow\mathbf{BKB_{i}}\boxdot ACC$. The TGSW cluster and the EP core
have their separated register file banks to reduce on-chip memory conflicts.
Moreover, these two steps of a TFHE bootstrapping can be deployed on a TGSW
cluster and an EP core in a pipelined manner, as shown in Figure 6(b). In each
time step, the EP core computes the EP operation with the bootstrapping key
bundle generated by the TGSW cluster in the previous time step. When $m$ is
increased, the workload of the bootstrapping key bundle construction becomes
larger. The workloads of the two steps in the pipeline can be approximately
balanced by adjusting $m$.

###  4.3. The Architecture of MATCHA

Architecture. The overall architecture of MATCHA is shown in Figure 7(a).
MATCHA has multiple computing components including a polynomial unit, eight
TGSW clusters, and eight External Product (EP) cores. All computing components
of MATCHA are connected to 32 scratchpad memory (SPM) banks by crossbars.
MATCHA also employs a memory controller to manage the off-chip memory requests
issued to HBM2 DRAMs. The polynomial unit is in charge of performing
polynomial additions/subtractions for each TFHE logic operation, initializing
bootstrapping operations, extracting samples, and conducting key-switching
operations that consist of additions, logic comparisons, and Boolean logic
operations. One TGSW cluster and an EP core can support one bootstrapping
pipeline. As Figure 7(b) shows, a TGSW cluster 16 32-bit integer multipliers
and 16 32-bit integer adders to support TGSW scale operations. Each TGSW
cluster has only two register banks, since the memory accesses during a TGSW
scale operation have strong spatial locality. The TGSW cluster can read a
register bank while write the other bank concurrently. An EP core consists of
an FFT core and four IFFT cores to accelerate the FFT and IFFT kernels during
an EP operation, as shown in Figure 7(c). It has 8 register banks to serve the
irregular memory accesses in FFT and IFFT kernels. An EP core also has four
32-bit integer multipliers and four 32-bit integer adders to manipulate TGSW
ciphertexts during an EP operation. An FFT core is similar to an IFFT core,
except its data flow. As Figure 7(d) highlights, an FFT core comprises an
address generation unit, a twiddle factor buffer, two input/output FIFOs, and
128 butterfly cores, each of which consists of two 64-bit integer adders and
two 64-bit binary shifters. The address generation unit guides butterfly cores
to access the twiddle factor buffer.

Table 2. The power and area of MATCHA operating at $2GHz$. Name | Spec |  Power ($W$) |  Area ($mm^{2}$)
---|---|---|---
TGSW |  $\times 16$ multipliers & adders, | 0.98 | 0.368
cluster | and a 16KB, 2-bank reg. file
EP |  4 IFFT, 1 FFT, $\times 4$ multipliers & adders, | 2.87 | 1.89
core | and a 256KB, 8-bank reg. file
Sub-total |  $\times 8$ EP cores and TGSW clusters | 30.8 | 18.06
polynomial |  $\times 32$ adders & cmps & logic units, | 2.33 | 0.32
unit | and a 8KB, 2-bank reg. file
crossbar |  1/2 $8\times 32/8$ NoCs (256b bit-sliced) | 2.11 | 0.44
SPM | a 4MB, 32-bank SPM | 3.52 | 3.25
mem ctrl | memory controller and HBM2 PHY | 1.225 | 14.9
Total |  | 39.98 | 36.96

Design Overhead. We implemented MATCHA in RTL, and synthesized it in $16nm$
PTM process technology using state-of-the-art tools. We used CACTI to model
all SPM components and register file banks. Due to its simple structure, the
entire design of MATCHA can run at $2GHz$. Among various on-chip network
architectures, e.g., meshs, rings, and crossbars, we selected two $8\times
32$, and one $8\times 8$ bit-sliced crossbars, i.e., SPM $\rightarrow$
cores/clusters, cores/clusters $\rightarrow$ SPM, and cores/clusters
$\rightarrow$ cores/clusters. The hardware overhead and power consumption of
MATCHA are shown in Table 2. Totally, MATCHA occupies $36.96mm^{2}$ and
consumes $39.98$ Watt. The HBM2 bandwidth is $640GB/s$.

Error and Noise. The error of the polynomial multiplication result caused by
approximate multiplication-less integer FFT and IFFT kernels is shown in
Figure 8. All polynomial coefficients are 32-bit integers, while we quantize
the twiddle factors of FFT and IFFT with various bitwidths. With an increasing
bitwidth of twiddle factors, the error caused by approximate FFT and IFFT
decreases, and is similar to that generated by original double-precision
floating point FFT and IFFT. With 64-bit dyadic-value-quantized twiddle
factors (DVQTFs), the error caused by approximate FFT and IFFT is $\sim
141dB$, which is still larger than that produced by 64-bit double-precision
floating point FFT and IFFT, since the approximate FFT and IFFT perform only
additions and binary shifts. At the TFHE gate level, the noise comparison
between BKU and MATCHA is exhibited in Table 3, where BKU unrolls the
bootstrapping key for two times while MATCHA unrolls that for $m$ times
($m\geq 2$). With an enlarging $m$, the noise from EP and rounding operations
decreases linearly, but the noise caused by bootstrapping keys increases
exponentially. As a result, TFHE with a smaller $m$ can tolerate more errors
caused by approximate FFT and IFFT. Based on our experiments, 38-bit DVQTFs
produce no decryption failure in the test of $10^{8}$ TFHE gates. However, for
a large $m$, e.g., $m=5$, we have to use 64-bit DVQTFs to guarantee there is
no decryption failure in the same test, since the noise caused by more
bootstrapping keys dominates the total noise in ciphertexts. Therefore, MATCHA
adopts 64-bit DVQTFs for all approximate multiplication-less integer FFT and
IFFT kernels.

Figure 8. The error of approx. FFT & IFFT.

metric |  BKU (Zhou:ACCESS2018, ; Bourse:CRYPTO2018, ) | MATCHA
---|---|---
EP | $\delta/2$ | $\delta/m$
rounding | $\mathcal{RO}/2$ | $\mathcal{RO}/m$
BK | $3\mathcal{BK}$ | $(2^{m}-1)\mathcal{BK}$
I/FFT | -150dB | -141dB

Table 3. The noise comparison ($\delta$: the noise of EPs; $\mathcal{RO}$: the
noise of roundings; $\mathcal{BK}$: the noise of bootstrapping keys).

##  5\. Experimental Methodology

Simulation and Compilation: To simulate the performance of MATCHA at cycle
level, we used a CGRA modeling framework, OpenCGRA (Cheng:ICCD2020, ), which
has been validated against multiple ASIC accelerators. OpenCGRA first compiles
a TFHE logic operation into a data flow graph (DFG) of the operations
supported by MATCHA, solves its dependencies, and removes structural hazards.
The architecture of MATCHA is abstracted to an architecture description (AD)
in OpenCGRA, which computes the latency and the energy consumption of each
TFHE logic operation by scheduling and mapping the DFG onto the AD.

Figure 9. Latency comparison.

Figure 10. Throughput comparison.

Figure 11. Thrghpt/Watt comparison.

Our Baselines. We compared MATCHA against state-of-the-art CPU-, GPU-, FPGA-,
and ASIC-based TFHE hardware platforms. Our CPU baseline is a 8-core $3.7GHz$
Xeon E-2288G processor executing the TFHE library (Chillotti:JC2018, ), while
our GPU baseline is a 5120-core Tesla-V100 GPU equipped with a 16GB HBM2 DRAM
running the cuFHE library (Dai:CUFHE2018, ). TFHE Vector Engine (TVE)
(Serhan:SPSL2021, ) was implemented on a low-end ZedBoard Zynq-7000 FPGA. We
implemented 8 copies of TVE on a Stratix-10 GX2800 FPGA, and used it as our
FPGA baseline, since the Stratix-10 board has more resources. Because there is
no existing ASIC-based design, we synthesized our FPGA baseline with the
$16nm$ PTM process as our ASIC baseline. We enable BKU on CPU, GPU, and MATCHA
but fix $m=1$ on FPGA and ASIC, since they do not support BKU.

TFHE Operations and Parameters. We studied all TFHE logic operations including
NOT, AND, OR, NAND, XOR, and XNOR, but we only report the results on NAND in
Section 6. This is because AND, OR, NAND, XOR, and XNOR have almost the same
latency which is dominated by the bootstrapping step, while NOT has no
bootstrapping at all. To maintain the standard 110-bit security, we adopt the
TFHE parameters from (Chillotti:JC2018, ), i.e., the polynomial degree in the
ring $N=1024$, the TLWE dimension $k=1$, the basis and length for the TGSW
ciphertext decomposition $Bg=1024$ and $\mathscr{l}=3$.

##  6\. Results and Analysis

Latency. The latency comparison of a TFHE NAND gate between our various
baselines and MATCHA is shown in Figure 11. The NAND gate on CPU costs
$13.1ms$, while $m=2$ reduces its latency to $6.67ms$. Aggressive BKU with an
increasing $m$ cannot further reduce the NAND gate latency anymore on CPU, due
to the limited number of cores, more cache conflicts, and the non-pipelined
processing style. It takes only $0.37ms$ for GPU to process a NAND gate. With
an enlarging $m$, GPU gradually reduces the NAND gate latency. When $m=4$, the
NAND gate latency on GPU is $0.18ms$. MATCHA reduces the NAND gate latency by
$13\%$ over GPU only when $m=3$, since GPU can fully use its all resources to
process one TFHE gate when $m=1$ or $2$. MATCHA cannot support aggressive BKU
with $m=4$ efficiently either, since it has only 8 TGSW clusters. FPGA and
ASIC do not have any pipelined design or memory optimization to support BKU,
and they need $>6.8ms$ to complete a NAND gate when $m=1$.

Throughput. The NAND gate throughput comparison between various baselines and
MATCHA is shown in Figure 11. FPGA and ASIC duplicate 8 copies of the TVE
(Serhan:SPSL2021, ), so they support only $m=1$. By enabling aggressive BKU,
even CPU ($m=2$) can achieve higher gate processing throughput than ASIC and
FPGA with $m=1$. GPU and MATCHA obtain much higher throughput than ASIC, FPGA
and CPU. Compared to GPU, MATCH improves the NAND gate throughput by
$2.3\times$ ($m=3$), due to its pipelined architecture for aggressive BKU.

Throughput per Watt. The comparison of the NAND gate throughput per Watt
between various baselines and MATCHA is shown in Figure 11. FPGA and ASIC
consume only $\sim 40W$ and $\sim 26W$, and improve the NAND gate throughput
per Watt by $2.4\times$ and $8.3\times$ over CPU respectively, when $m=1$. Due
to the large power consumption ($>200W$) of GPU, the best throughput per Watt
of GPU ($m=4$) is only about 58% of that of ASIC. Compared to ASIC, MATCHA
improves the NAND gate throughput per Watt by $6.3\times$, since it consumes
only $39.98W$.

##  7\. Conclusion

TFHE enables arbitrary computations with an unlimited multiplicative depth to
directly occur on ciphertexts. However, TFHE gates are time-consuming and
power-hungry on state-of-the-art hardware platforms. In this paper, we build
MATCHA to accelerate TFHE gates. MATCHA allows aggressive bootstrapping key
unrolling to process TFHE gates without decryption errors by approximate
multiplication-less integer FFTs and IFFTs, and a pipelined datapath. Compared
to prior CPU-, GPU-, FPGA- and ASIC-based solutions, MATCHA improves the TFHE
gate processing throughput by $2.3\times$, and the throughput per Watt by
$6.3\times$.

## References

  * (1) A. Becoulet and A. Verguet, “A Depth-First Iterative Algorithm for the Conjugate Pair Fast Fourier Transform,” _IEEE Transactions on Signal Processing_ , 2021.
  * (2) F. Bourse, _et al._ , “Fast Homomorphic Evaluation of Deep Discretized Neural Networks,” in _Annual International Cryptology Conference_ , 2018.
  * (3) Z. Brakerski, _et al._ , “(Leveled) Fully Homomorphic Encryption without Bootstrapping,” _ACM Transaction Computing Theory_ , 6(3), July 2014\.
  * (4) A. Brutzkus, _et al._ , “Low Latency Privacy Preserving Inference,” in _International Conference on Machine Learning_ , pages 812–821, 2019.
  * (5) J. H. Cheon, _et al._ , “Remark on the Security of CKKS Scheme in Practice,” Cryptology ePrint Archive, Report 2020/1581, 2020, https://eprint.iacr.org/2020/1581.
  * (6) I. Chillotti, _et al._ , “TFHE: Fast Fully Homomorphic Encryption Over The Torus,” _Journal of Cryptology_ , 33(1):34–91, 2020.
  * (7) W. Dai, “CUDA-accelerated Fully Homomorphic Encryption Library,” https://github.com/vernamlab/cuFHE, 2018, worcester Polytechnic Institute.
  * (8) L. Ducas and D. Micciancio, “FHEW: Bootstrapping Homomorphic Encryption in Less than A Second,” in _International Conference on the Theory and Applications of Cryptographic Techniques_ , pages 617–640, Springer, 2015.
  * (9) J. Fan and F. Vercauteren, “Somewhat Practical Fully Homomorphic Encryption,” Cryptology ePrint Archive, Report 2012/144, 2012.
  * (10) S. Gener, _et al._ , “An FPGA-based Programmable Vector Engine for Fast Fully Homomorphic Encryption over the Torus,” _SPSL: Secure and Private Systems for Machine Learning_ , 2021.
  * (11) S. Halevi and V. Shoup, “Bootstrapping for HElib,” in _International conference on the theory and applications of cryptographic techniques_ , 2015.
  * (12) C. J. Hoofnagle, _et al._ , “The European Union General Data Protection Regulation: What It Is & What It Means,” _Information & Communications Technology Law_, 2019.
  * (13) Z. Liu, _et al._ , “High-Performance Ideal Lattice-Based Cryptography on 8-Bit AVR Microcontrollers,” _ACM Transactions on Embedded Computing Systems_ , 16(4), July 2017, https://doi.org/10.1145/3092951.
  * (14) K. Matsuoka, _et al._ , “Virtual Secure Platform: A Five-Stage Pipeline Processor over TFHE,” in _USENIX Security Symposium_ , pages 4007–4024, 2021.
  * (15) A. C. Mert, _et al._ , “A Flexible and Scalable NTT Hardware : Applications from Homomorphically Encrypted Deep Learning to Post-Quantum Cryptography,” in _Design, Automation & Test in Europe Conference & Exhibition_, 2020.
  * (16) T. Morshed, _et al._ , “CPU and GPU Accelerated Fully Homomorphic Encryption,” in _IEEE International Symposium on Hardware Oriented Security and Trust_ , pages 142–153, 2020.
  * (17) S. Oraintara, _et al._ , “Integer fast Fourier transform,” _IEEE Transactions on Signal Processing_ , 50(3):607–618, 2002.
  * (18) M. S. Riazi, _et al._ , “HEAX: An Architecture for Computing on Encrypted Data,” in _ACM International Conference on Architectural Support for Programming Languages and Operating Systems_ , 2020.
  * (19) N. Samardzic, _et al._ , “F1: A Fast and Programmable Accelerator for Fully Homomorphic Encryption,” in _IEEE/ACM International Symposium on Microarchitecture_ , 2021.
  * (20) S. Sinha Roy, _et al._ , “FPGA-Based High-Performance Parallel Architecture for Homomorphic Computing on Encrypted Data,” in _IEEE International Symposium on High Performance Computer Architecture_ , pages 387–398, 2019.
  * (21) C. Tan, _et al._ , “OpenCGRA: An Open-Source Unified Framework for Modeling, Testing, and Evaluating CGRAs,” in _2020 IEEE 38th International Conference on Computer Design_ , pages 381–388, 2020.
  * (22) T. Zhou, _et al._ , “Faster Bootstrapping With Multiple Addends,” _IEEE Access_ , 6:49868–49876, 2018.