# Decoupling Strategy and Generation in Negotiation Dialogues

He He  Derek Chen  Anusha Balakrishnan  Percy Liang
Computer Science Department, Stanford University
<EMAIL_ADDRESS>
###### Abstract

We consider negotiation settings in which two agents use natural language to
bargain on goods. Agents need to decide on both high-level strategy (e.g.,
proposing $50) and the execution of that strategy (e.g., generating _“The bike
is brand new. Selling for just $50!”_). Recent work on negotiation trains
neural models, but their end-to-end nature makes it hard to control their
strategy, and reinforcement learning tends to lead to degenerate solutions. In
this paper, we propose a modular approach based on coarse dialogue acts (e.g.,
propose(price=50)) that decouples strategy and generation. We show that we can
flexibly set the strategy using supervised learning, reinforcement learning,
or domain-specific knowledge without degeneracy, while our retrieval-based
generation can maintain context-awareness and produce diverse utterances. We
test our approach on the recently proposed DealOrNoDeal game, and we also
collect a richer dataset based on real items on Craigslist. Human evaluation
shows that our systems achieve higher task success rate and more human-like
negotiation behavior than previous approaches.

##  1 Introduction

A good negotiator needs to decide on the _strategy_ for achieving a certain
goal (e.g., proposing $6000) and the realization of that strategy via
_generation_ of natural language (e.g., _“I really need a car so I can go to
work, but all I have is 6000, any more and I won’t be able to feed my
children.”_).

Most past work in NLP on negotiation focuses on strategy (dialogue management)
with either no natural language Cuayáhuitl et al. (2015); Cao et al. (2018) or
canned responses Keizer et al. (2017); Traum et al. (2008). Recently, end-to-
end neural models Lewis et al. (2017); He et al. (2017) are used to
simultaneously learn dialogue strategy and language realization from human-
human dialogues, following the trend of using neural network models on both
goal-oriented dialogue Wen et al. (2017a); Dhingra et al. (2017) and open-
domain dialogue Sordoni et al. (2015); Li et al. (2017); Lowe et al. (2017).
However, these models have two problems: (i) it is hard to control and
interpret the strategies, and (ii) directly optimizing the agent’s goal
through reinforcement learning often leads to degenerate solutions where the
utterances become ungrammatical Lewis et al. (2017) or repetitive Li et al.
(2016).

Figure 1: Our modular framework consists of three components similar to
traditional goal-oriented dialogue systems. (1) The parser maps received
utterances to coarse dialogue acts (an intent and its arguments) that capture
the high-level dialogue flow. (2) The manager generates the next coarse
dialogue act $z_{t}$ conditioned on past dialogue acts $z_{<t}$. (3) The
generator then produces a response conditioned on both the predicted coarse
dialogue act $z_{t}$ and the dialogue history $x_{<t}$. Importantly, unlike in
traditional systems, coarse dialogue acts only capture the rough shape of a
dialogue, not the full meaning of its utterances, e.g., inform does not
specify the answer to the question.

To alleviate these problems, our key idea is to decouple strategy and
generation, which gives us control over the strategy such that we can achieve
different negotiation goals (e.g., maximizing utility, achieving a fair deal)
with the same language generator. Our framework consists of three components
shown in Figure 1: First, the parser identifies keywords and entities to map
each utterance to a _coarse dialogue act_ capturing the high-level strategic
move. Then, the dialogue manager chooses a responding dialogue act based on a
sequence-to-sequence model over coarse dialogue acts learned from parsed
training dialogues. Finally, the generator produces an utterance given the
dialogue act and the utterance history.

Our framework follows that of traditional goal-oriented dialogue systems
(Young et al., 2013), with one important difference: coarse dialogue acts are
not intended to and cannot capture the full meaning of an utterance. As
negotiation dialogues are fairly open-ended, the generator needs to depend on
the full utterance history. For example, consider the first turn in Figure 1.
We cannot generate a response given only the dialogue act inform; we must also
look at the previous question. However, we still optimize the dialogue manager
in the coarse dialogue act space using supervised learning, reinforcement
learning, or domain-specific knowledge.

Existing human-human negotiation datasets are grounded in closed-domain games
with a fixed set of objects such as Settlers of Catan (lumber, coal, brick,
wheat, and sheep) Afantenos et al. (2012); Asher et al. (2016) or item
division (book, hat, and ball) DeVault et al. (2015); Lewis et al. (2017).
These objects lack the richness of the real world. To study human negotiation
in more open-ended settings that involve real goods, we scraped postings of
items for sale from craigslist.org as our negotiation scenario. By hiring
workers on Amazon Mechanical Turk (AMT) to play the role of buyers and
sellers, we collected a new dataset (CraigslistBargain) of negotiation
dialogues.111 Available at https://stanfordnlp.github.io/cocoa.  Compared to
existing datasets, our more realistic scenario invites richer negotiation
behavior involving open-ended aspects such as cheap talk or side offers.

We evaluate two families of systems modeling coarse dialogue acts and words
respectively, which are optimized by supervised learning, reinforcement
learning, or domain knowledge. Each system is evaluated on our new
CraigslistBargain dataset and the DealOrNoDeal dataset of Lewis et al. (2017)
by asking AMT workers to chat with the system in an A/B testing setting. We
focus on two metrics: task-specific scores (e.g., utility) and human-likeness.
We show that reinforcement learning on coarse dialogue acts avoids degenerate
solutions, which was a problem in Li et al. (2016); Lewis et al. (2017). Our
modular model maintains reasonable human-like behavior while still optimizes
the objective. Furthermore, we find that models trained over coarse dialogue
acts are stronger negotiators (even with only supervised learning) and produce
more diverse utterances than models trained over words. Finally, the
interpretability of coarse dialogue acts allows system developers to combine
the learned dialogue policy with hand-coded rules, thus imposing stronger
control over the desired strategy.

JVC HD-ILA 1080P 70 Inch TV
Tv is approximately 10 years old. Just installed new lamp. There are 2 HDMI
inputs. Works and looks like new.
Listing price: $275
Buyer’s target price: $192

Agent |  Utterance |  Dialogue Act
---|---|---
Buyer |  Hello do you still have the TV? |  greet
Seller |  Hello, yes the TV is still available |  greet
Buyer |  What condition is it in? Any scratches or problems? I see it recently got repaired |  inquire
Seller |  It is in great condition and works like a champ! I just installed a new lamp in it. There aren’t any scratches or problems. |  inform
Buyer |  All right. Well I think 275 is a little high for a 10 year old TV. Can you lower the price some? How about 150? |  propose(150)
Seller |  I am willing to lower the price, but $150 is a little too low. How about $245 and if you are not too far from me, I will deliver it to you for free? |  counter(245)
Buyer |  It’s still 10 years old and the technology is much older. Will you do 225 and you deliver it. How’s that sound? |  counter(225)
Seller |  Okay, that sounds like a deal! |  agree
Buyer |  Great thanks! |  agree
Seller |  OFFER $225.0 |  offer(225)
Buyer |  ACCEPT |  accept

Table 1: Example dialogue between two people negotiating the price of a used
TV.

##  2 Craigslist Negotiation Dataset

Previous negotiation datasets were collected in the context of games. For
example, Asher et al. (2016) collected chat logs from online Settlers of
Catan. Lewis et al. (2017) asked two people to divide a set of hats, books,
and balls. While such games are convenient for grounding and evaluation, it
restricts the dialogue domain and the richness of the language. Most
utterances are direct offers such as _“has anyone got wood for me?”_ and _“I
want the ball.”_ , whereas real-world negotiation would involve more
information gathering and persuasion.

To encourage more open-ended, realistic negotiation, we propose the
CraigslistBargain task. Two agents are assigned the role of a buyer and a
seller; they are asked to negotiate the price of an item for sale on
Craigslist given a description and photos. As with the real platform, the
listing price is shown to both agents. We additionally suggest a private price
to the buyer as a target. Agents chat freely in alternating turns. Either
agent can enter an offer price at any time, which can be accepted or rejected
by the partner. Agents also have the option to quit, in which case the task is
completed with no agreement.

To generate the negotiation scenarios, we scraped postings on
sfbay.craigslist.org from the 6 most popular categories (housing, furniture,
cars, bikes, phones, and electronics). Each posting produces three scenarios
with the buyer’s target prices at 0.5x, 0.7x and 0.9x of the listing price.
Statistics of the scenarios are shown in Table 2.

We collected 6682 human-human dialogues on AMT using the interface shown in
Appendix A Figure 2. The dataset statistics in Table 3 show that
CraigslistBargain has longer dialogues and more diverse utterances compared to
prior datasets. Furthermore, workers were encouraged to embellish the item and
negotiate side offers such as free delivery or pick-up. This highly relatable
scenario leads to richer dialogues such as the one shown in Table 1. We also
observed various persuasion techniques listed in Table 4 such as
embellishment, side offers, and appeals to sympathy.

# of unique postings | 1402
---|---
% with images | 80.8
Avg # of tokens per description | 42.6
Avg # of tokens per title | 33.8
Vocab size | 12872
Table 2: Statistics of CraigslistBargain scenarios. | CB | DN | SoC
---|---|---|---
# of dialogues | 6682 | 5808 | 1081
Avg # of turns | 9.2 | 6.6 | 8.5
Avg # of tokens per turn | 15.5 | 7.6 | 4.2
Vocab size | 13928 | 2719 | 4921
Vocab size (excl. numbers) | 11799 | 2623 | 4735
Table 3: Comparison of dataset statistics of CraigslistBargain (CB), DealOrNoDeal (DN), and SettlersOfCatan (SoC). CraigslistBargain contains longer, more diverse dialogues on average. Phenomenon |  Example
---|---
Embellishment |  It is in great condition and works like a champ! I just installed a new lamp in it. There aren’t any scratches or problems.
Cheap talk |  How about i give you $20 and you keep the helmet. its for my daughter for her job, she delivers lemonade.
Side offers |  Throw in a couple of movies with that DVD player, and you have yourself a deal.
Appeal to sympathy |  I would love to have this for my mother, she is very sick and this would help her and with me taking care of her and having to take a leave from work I can’t pay very much of it
World knowledge |  For a Beemer 5 series in this condition, I really can’t go that low.
Table 4:  Rich negotiation language in our CraigslistBargain dataset.

##  3 Approach

###  3.1 Motivation

While end-to-end neural models have made promising progress in dialogue
systems Wen et al. (2017a); Dhingra et al. (2017), we find they struggle to
simultaneously learn the strategy and the rich utterances necessary to succeed
in the CraigslistBargain domain, e.g., Table 8(a) shows a typical dialogue
between a human and a sequence-to-sequence-based bot, where the bot easily
agrees. We wish to now separate negotiation strategy and language generation.
Suppose the buyer says: _“All right. Well I think 275 is a little high for a
10 year old TV. Can you lower the price some? How about 150?”_ We can capture
the highest-order bit with a coarse dialogue act propose(price=150). Then, to
generate the seller’s response, the agent can first focus on this coarse
dialogue act rather than having to ingest the free-form text all at once. Once
a counter price is decided, the rest is open-ended justification for the
proposed price, e.g., emphasizing the quality of the TV despite its age.

Motivated by these observations, we now describe a modular framework that
extracts coarse dialogue acts from utterances, learns to optimize strategy in
the dialogue act space, and uses retrieval to fill in the open-ended parts
conditioned on the full dialogue history.

###  3.2 Overview

Our goal is to build a dialogue agent that takes the dialogue history, i.e. a
sequence of utterances $x_{1},\ldots,x_{t-1}$ along with the dialogue scenario
$c$ (e.g., item description), and produces a distribution over the responding
utterance $x_{t}$.

For each utterance $x_{t}$ (e.g., _“I am willing to pay $15”_), we define a
coarse dialogue act $z_{t}$ (e.g., propose(price=15)); the coarse dialogue act
serves as a logical skeleton which does not attempt to capture the full
semantics of the utterance. Following the strategy of traditional goal-
oriented dialogue systems (Young et al., 2013), we broadly define our model in
terms of the following three modules:

  1. 1.

A parser that (deterministically) maps an input utterance $x_{t-1}$ into a
coarse dialogue act $z_{t-1}$ given the dialogue history $x_{<t}$ and
$z_{<t}$, as well as the scenario $c$.

  2. 2.

A manager that predicts the responding dialogue act $z_{t}$ given past coarse
dialogue acts $z_{<t}$ and the scenario $c$.

  3. 3.

A generator that turns the coarse dialogue act $z_{t}$ to a natural language
response $x_{t}$ given the full dialogue history $x_{<t}$.

Because coarse dialogue acts do not capture the full semantics, the parser and
the generator maintains full access to the dialogue history. The main
restriction is the manager examining the dialogue acts, which we show will
reduce the risk of degeneracy during reinforcement learning Section 4.4. We
now describe each module in detail (Figure 1).

###  3.3 Parser

Our framework is centered around the coarse dialogue act $z$, which consists
of an intent and a set of arguments. For example, _“I am willing to pay $15”_
is mapped to propose(price=15). The fact that our coarse dialogue acts do not
intend to capture the full semantics of a sentence allows us to use a simple
rule-based parser. It detects the intent and its arguments by regular
expression matching and a few if-then rules. Our parser starts by detecting
entities (e.g., prices, objects) and matching keyword patterns (e.g., _“go
lower”_). These signals are checked against an ordered list of rules, where we
choose the first matched intent in the case of multiple matches. An unknown
act is output if no rule is triggered. The list of intent parsing rules used
are shown in Table 5. Please refer to Appendix B for argument parsing based on
entity detection.

Generic Rules
---
Intent |  Matching Patterns
greet |  hi, hello, hey, hiya, howdy
disagree |  no, not, n’t, nothing, dont
agree |  not disagree and ok, okay, great, perfect, deal, that works, i can do that
insist |  the same offer as the previous one is detected
inquire |  starts with an interrogative word (e.g., what, when, where) or particle (e.g., do, are)
CraigslistBargain Rules
Intent |  Matching Patterns
intro |  greet or how are you, interested
propose |  first price mention
vague-price |  no price mention and come down, highest, lowest, go higher/lower, too high/low
counter |  new price detected
inform |  previous coarse dialogue act was inquire
DealOrNoDeal Rules
Intent |  Matching Patterns
propose |  items and respective counts are detected
Table 5: Rules for intent detection in the parser.

###  3.4 Manager

The dialogue manager decides what action $z_{t}$ the dialogue agent should
take at each time step $t$ given the sequence of past coarse dialogue acts
$z_{<t}$ and the scenario $c$. Below, we describe three ways to learn the
dialogue manager with increasing controllability: modeling human behavior in
the training corpus (supervised learning), explicitly optimizing a reward
function (reinforcement learning), and injecting hand-coded rules (hybrid
policy).

#### Supervised learning.

Given a parsed training corpus, each training example is a sequence of coarse
dialogue acts over one dialogue, $z_{1},\ldots,z_{T}$. We learn the transition
probabilities $p_{\theta}(z_{t}\mid z_{<t},c)$ by maximizing the likelihood of
the training data.

We use a standard sequence-to-sequence model with attention. Each coarse
dialogue act is represented as a sequence of tokens, i.e. an intent followed
by each of its arguments, e.g., “offer 150”. During the agent’s listening
turn, an LSTM encodes the received coarse dialogue act; during its speaking
turn, another LSTM decodes the tokens in the coarse dialogue act. The hidden
states are carried over the entire dialogue to provide full history.

The vocabulary of coarse dialogue acts is much smaller than the word
vocabulary. For example, our implementation includes fewer than 10 intents and
argument values are normalized and binned (see Section 4.2).

#### Reinforcement learning.

Supervised learning aims to mimic the average human behavior, but sometimes we
want to directly optimize for a particular dialogue goal. In reinforcement
learning, we define a reward $R(z_{1:T})$ on the entire sequence of coarse
dialogue acts. Specifically, we experiment with three reward functions:

  * •

Utility is the objective of a self-interested agent. For CraigslistBargain, we
set the utility function to be a linear function of the final price, such that
the buyer has a utility of 1 at their target price, the seller has a utility
of 1 at the listing price, and both agents have a utility of zero at the
midpoint of the listing price and the buyer’s target price, making it a zero-
sum game. For DealOrNoDeal, utility is the total value of objects given to the
agent.

  * •

Fairness aims to achieve equal outcome for both agents, i.e. the difference
between two agents’ utilities.

  * •

Length is the number of utterances in a dialogue, thus encourages agents to
chat as long as possible.

The reward is $-1$ if no agreement is reached.

We use policy gradient Williams (1992) for optimization. Given a sampled
trajectory $z_{1:T}$ and the final reward $r$, let $a_{i}$ be the $i$-th
generated token (i.e. “action” taken by the policy) along the trajectory. We
update the parameters $\theta$ by

$\theta\leftarrow\theta-\eta\sum_{i}\nabla_{\theta}\log p_{\theta}(a_{i}\mid
a_{<i},c)(r-b)$ (1)

where $\eta$ is the learning rate and $b$ is a baseline estimated by the
average return so far for variance reduction.

#### Hybrid policy.

Given the interpretable coarse dialogue acts, a simple option is to write a
rule-based manager with domain knowledge, e.g., if $z_{t-1}=\text{{greet}}$,
then $z_{t}=\text{{greet}}$. We combine these rules with a learned manager to
fine-tune the dialogue policy. Specifically, the dialogue manager predicts the
intent from a learned sequence model but fills in the arguments (e.g., price)
using rules. For example, given a predicted intent propose, we can set the
price to be the average of the buyer’s and seller’s current proposals (a
split-the-difference strategy).

###  3.5 Generator

We use retrieval-based generation to condition on both the coarse dialogue act
and the dialogue history. Each candidate in our database for retrieval is a
tuple of an utterance $x_{t}$ and its dialogue context $x_{t-1}$, represented
by both templates and coarse dialogue acts. i.e.
$(d(x_{t-1}),z_{t-1},d(x_{t}),z_{t})$, where $d$ is the template extractor.
Specifically, given a parsed training set, each utterance is converted to a
template by delexicalizing arguments in its coarse dialogue act. For example,
_“How about $150?”_ becomes “How about [price]?”, where [price] is a
placeholder to be filled in at generation time.

At test time, given $z_{t}$ from the dialogue manager, the generator first
retrieves candidates with the same intent as $z_{t}$ and $z_{t-1}$. Next,
candidates are ranked by similarity between their context templates and the
current dialogue context. Specifically, we represent the context $d(x_{t-1})$
as a TF-IDF weighted bag-of-words vector and similarity is computed by a dot
product of two context vectors. To encourage diversity, the generator samples
an utterance from the top $K$ candidates according to the distribution given
by a trigram language model estimated on the training data.

##  4 Experiments

###  4.1 Tasks

We test our approach on two negotiation tasks. CraigslistBargain (Section 2)
asks a buyer and a seller to negotiate the price of an item for sale given its
Craigslist post. DealOrNoDeal Lewis et al. (2017) asks two agents to divide a
set of items given their private utility functions.

###  4.2 Models

We compare two families of models: end-to-end neural models that directly map
the input dialogue context to a sequence of output words, and our modular
models that use coarse dialogue acts as the intermediate representation.

We start by training the word-based model and the act-based model with
supervised learning (SL).

  * •

SL(word): a sequence-to-sequence model with attention over previous utterances
and the scenario, both embedded as a continuous Bag-of-Words;

  * •

SL(act): our model described in Section 3 with a rule-based parser, a learned
neural dialogue manager, and a retrieval-based generator.

To handle the large range of argument values (prices) in CraigslistBargain for
act-based models, we normalize the prices such that an agent’s target price is
1 and the bottomline price is 0. For the buyer, the target is given and the
bottomline is the listing price. For the seller, the target is the listing
price and the bottomline is set to 0.7x of the listing price. The prices are
then binned according to their approximate values with two digits after the
decimal point.

Next, given the pretrained SL models, we fine-tune them with the three reward
functions (Section 3.4), producing RL${}_{\text{utility}}$,
RL${}_{\text{fairness}}$, and RL${}_{\text{length}}$.

In addition, we compare with the hybrid model, SL(act)+rule. It predicts the
next intent using a trigram language model learned over intent sequences in
the training data, and fills in the arguments with hand-coded rules. For
CraigslistBargain, the only argument is the price. The agent always splits the
difference when making counter proposals, rejects an offer if it is worse than
its bottomline and accepts otherwise. For DealOrNoDeal, the agent maintains an
estimate of the partner’s private utility function. In case of disagreement,
it gives up the item with the lowest value of $(\text{own
utility}-\text{partner utility})$ and takes an item of estimated zero utility
to the partner. The agent agrees whenever a proposal is better than the last
one or its predefined target. A high-level comparison of all models is shown
in Table 6.

Model | $z$ | Parser | Manager | Generator
---|---|---|---|---
SL/RL${}_{\text{}}$(word) | vector | learned | learned | generative
SL/RL${}_{\text{}}$(act) | logical | rules | learned | retrieval
SL(act)+rule | logical | rules | hybrid | retrieval
Table 6: Comparison of different implementation of the core modules in our framework. | CraigslistBargain | DealOrNoDeal
---|---|---
| Hu | Ut | Fa | Ag | Len | Hu | Ut | Fa | Ag | Len
Human | 4.3 | -0.07 | -0.14 | 0.91 | 10.2 | 4.6 | 5.5 vs. 5.3 | -0.2 | 0.78 | 5.8
SL(word) | 3.0 | -0.32 | -0.64 | 0.75 | 7.8 | 3.8 | 4.7 vs. 5.0 | -0.3 | 0.70 | 5.0
SL(act) | 3.3 | 0.06 | -0.12 | 0.84 | 14.0 | 3.2 | 5.2 vs. 5.0 | -0.2 | 0.67 | 7.0
SL(act)+rule | 3.6 | 0.23 | -0.46 | 0.75 | 11.4 | 4.2 | 5.2 vs. 5.2 | 0 | 0.72 | 8.0
RL${}_{\text{utility}}$(word) | 1.7 | 1.00 | -2.00 | 0.31 | 2.5 | 1.7 | 2.9 vs. 1.8 | -1.1 | 0.33 | 10.4
RL${}_{\text{utility}}$(act) | 2.8 | 1.00 | -2.00 | 0.22 | 6.7 | 2.8 | 3.3 vs. 2.3 | -1.0 | 0.38 | 9.5
RL${}_{\text{fairness}}$(word) | 1.8 | -0.62 | -1.24 | 0.75 | 9.4 | 3.2 | 5.7 vs. 5.9 | -0.2 | 0.79 | 4.0
RL${}_{\text{fairness}}$(act) | 3.0 | -0.28 | -0.56 | 0.68 | 7.1 | 3.5 | 4.2 vs. 5.4 | -1.2 | 0.77 | 7.6
RL${}_{\text{length}}$(word) | 1.9 | -0.79 | -1.58 | 0.85 | 13.8 | 1.6 | 3.4 vs. 2.9 | -0.5 | 0.48 | 9.2
RL${}_{\text{length}}$(act) | 3.0 | 0.89 | -1.78 | 0.40 | 11.8 | 2.5 | 2.5 vs. 3.1 | -0.6 | 0.54 | 11.0
Table 7:  Human evaluation results on human-likeness (Hu), agreement rate (Ag), and RL objectives, including agent utility (Ut), deal fairness (Fa), and dialogue length (Len). Results are grouped by the optimization objective. For each group of RL models, the column of the optimization objective is highlighted. For human-likeness, scores that are better than others in the same group with statistical significance ($p<0.05$ given by paired $t$-tests) are in bold. Overall, with SL, all models are human-like, however, act-based models better matches human statistics across all metrics; with RL, word-based models becomes degenerate, whereas act-based models optimize the reward while maintaining human-likeness.  Title: Fitbit Flex + 2 Bands Activity Tracker |  Listing Price: $60
---|---
Description: Hi, I’m selling a Fitbit Activity Tracker. Track your day
including steps, distance, calories burned, active minutes.
Track your night including hours slept, times to woken up, sleep quality, Wake
with a silent vibrating alarm. You can set a …
(a) A: SL(word) (Buyer) B: Human (Seller) | (b) A: SL(act) (Buyer) B: Human (Seller)
A: hi, i ’m interested in your fitbit. B: Great. It really is a good deal. A: great. B: Do you have any questions about it? A: i ’m interested in your fitbit. i ’m not sure i ’m not sure i ’m interested. B: It has so many functions that are great. I particularly like the sleep tracking. Plus it is waterproof. How about I will deliver it to you and you give me 60 dollars? A: i can do $52 if you come pick it up. B: Well I am selling it. So I will deliver it for 60. Deal? A: yes, i can do that. B: OFFER($60) A: ACCEPT |  | A: how we doing today
---
B: Hi!
A: yes, i really need one, what color is it?
B: It has a black band and a white band.
A: i see, so you bought an extra one by mistake?
B: No, it comes with 2 bands
A: i would like to make you a offer of 36
B: Ooooh….yeah, I can’t. Sorry. It’s wireless, has Bluetooth,
extra bands, and is water resistant. I could do $50.
A: 49?
B: You know..I’d do $49.
A: thank you so much!
B: OFFER($49) A: ACCEPT
(c) A: RL${}_{\text{length}}$(word) (Buyer) B: Human (Seller) | (d) A: RL${}_{\text{length}}$(act) (Buyer) B: Human (Seller)
A: hello B: Hi how are you? A: i am. B: you are interested in the fitbit flex and the 2 trackers? A: it’s in good condition condition. B: yes A: ok, that sounds good. B: I am selling it at $60? A: it’s in good condition condition. B: yes A: ok, that sounds good. B: $60 A: i can go that low. |  | A: hi, i saw your ad about the item.
---
B: Okay great, i’m selling a Fitbit Flex plus 2 bands
A: how old is the item?
B: I’ve only had it for about a few months.
A: but it does work correct?
B: yes it does work, it’s in great condition.
A: excellent. would you consider taking 36 for it?
B: I’m selling for $60 but $36 would be way too low.
A: how about 36?
B: no I cannot accept $36, I’m sorry
A: i’m sorry. would you accept 36?
B: I am not going lower than $50
A: OFFER($36) A: REJECT
Table 8: Example human-bot chats on CraigslistBargain, where bot utterances
are in bold. SL(word) produced generic responses, while SL(act) is more human-
like. RL${}_{\text{length}}$(word) devolved into degenerate behavior repeating
itself while RL${}_{\text{length}}$(act) maintained coherency. Only the first
half of the item description and the RL${}_{\text{length}}$(word) chat are
shown due to space limit.

###  4.3 Training Details

#### CraigslistBargain

For SL(word), we use a sequence-to-sequence model with attention over 3
previous utterances and the negotiation scenario (embedded as a continuous
Bag-of-Words). For both SL(word) and SL(act), we use 300-dimensional word
vectors initialized by pretrained GloVe word vectors Pennington et al. (2014),
and a two-layer LSTM with 300 hidden units for both the encoder and the
decoder. Parameters are initialized by sampling from a uniform distribution
between -0.1 and 0.1. For optimization, we use AdaGrad Duchi et al. (2010)
with a learning rate of 0.01 and a mini-batch size of 128. We train the model
for 20 epochs and choose the model with the lowest validation loss.

For RL, we first fit a partner model using supervised learning (e.g.,
SL(word)), then run RL against it. One agent is updated by policy gradient and
the partner model is fixed during training. We use a learning rate of 0.001
and train for 5000 episodes (dialogues). The model with the highest reward on
the validation set is chosen.

#### DealOrNoDeal

For act-based models, we use the same parameterization as CraigslistBargain.
For word-based models, we use the implementation from Lewis et al.
(2017).222https://github.com/facebookresearch/end-to-end-negotiator Note that
for fair comparison, we did not apply SL interleaving during RL training and
rollouts during inference.

###  4.4 Human Evaluation

We evaluated each system on two metrics: task-specific scores (e.g., utility)
and human-likeness. The scores tell us how well the system is playing the
game, and human-likeness tells us whether the bot deviates from human
behavior, presumably due to over-optimization.

We put up all 9 systems online and hired workers from AMT to chat with the
bots. Each worker was randomly paired with one of the bots or another worker,
so as to compare the bots with human performance under the same conditions. At
the end of a chat, workers were asked the question _“Do you think your partner
demonstrated reasonable human behavior?”_. They provided answers on a Likert
scale from 1 (not at all) to 5 (definitely). Table 7 shows the human
evaluation results on CraigslistBargain and DealOrNoDeal respectively. We also
show example human-bot dialogues in Table 8 and Appendix C.

#### SL(act) learns more human-like behavior.

We first compare performance of SL models over words and coarse dialogue acts.
Both SL(word) and SL(act) achieved similar scores on human-likeness (no
statistically significant difference). However, SL(word) better matched human
statistics such as dialogue length and utility. For instance, SL(word) tended
to produce short, generic utterances as shown in Table 8(a); they also agreed
on a deal more quickly because utterances such as _“deal”_ and _“I can do
that”_ are frequent in negotiation dialogues. This behavior is reflected by
the shorter dialogue length and lower utility of SL(word) models.

#### RL${}_{\text{}}$(word) leads to degeneracy.

On CraigslistBargain, all RL${}_{\text{}}$(word) models clearly have low
scores on human-likeness in Table 7. They merely learned to repeat a few
sentences: The three most frequent sentences of RL${}_{\text{utility}}$(word),
RL${}_{\text{fairness}}$(word), and RL${}_{\text{length}}$(word) account for
81.6%, 100% and 100% of all utterances. For example,
RL${}_{\text{utility}}$(word) almost always opened with _“i can pick it up”_ ,
then offer its target price. RL${}_{\text{length}}$(word) repeated generic
sentences until the partner submitted a price. While they scored high on the
reward being optimized, the conversations are unnatural.

On DealOrNoDeal, we have observed similar patterns. A general strategy learned
by RL${}_{\text{}}$(word) was to pick an offer depending on its objective,
then repeat the same utterance over and over again (e.g., _“i need the
ball.”_), resulting in low human-likeness scores. One exception is
RL${}_{\text{fairness}}$(word), since most of its offers were reasonable and
agreed on immediately (it has the shorted dialogue length), the conversations
are natural.

#### RL${}_{\text{}}$(act) optimizes different negotiation goals while being
human-like.

On both tasks, RL${}_{\text{}}$(act) models optimized their rewards while
maintaining reasonable human-likeness scores. We now show that different
models demonstrated different negotiation behavior. Two main strategies
learned by RL${}_{\text{length}}$(act) were to ask questions and to postpone
offer submission. On CraigslistBargain, when acting as a buyer, 42.4% of its
utterances were questions, compared to 30.2% for other models. On both tasks,
it tended to wait for the partner to submit an offer (even after a deal was
agreed on), compared to RL${}_{\text{margin}}$(act) which almost always
submitted offers first. For RL${}_{\text{fairness}}$(act), it aimed to agree
on a price in the middle of the listing price and the buyer’s target price for
CraigslistBargain. Since the buyer’s target was hidden, when the agent was the
seller, it tended to wait for the buyer to propose prices first. Similary, on
DealOrNoDeal it waited to hear the parter’s offer and sometimes changed its
offer afterwards, whereas the other models often insisted on one offer.

On both tasks, RL${}_{\text{utility}}$(act) learned to insist on its offer and
refuse to budge. This ended up frustrating many people, which is why it has a
low agreement rate. The problem is that our human model is simply a SL model
trained on human-human dialogues, which may not accurately reflects real human
behavior during human-bot chat. For example, the SL model often agrees after a
few turns of insistence on a proposal, whereas humans get annoyed if the
partner is not willing to make compromises at all. However, by injecting
domain knowledge to SL(act)+rule, e.g., making a small compromise is better
than stubbornly being fixed on a single price, we were able to achieve high
utility and human-likeness on both CraigslistBargain and DealOrNoDeal.

##  5 Related Work and Discussion

Recent work has explored the space between goal-oriented dialogue and open-
domain chit-chat through collaborative or competitive language games, such as
collecting cards in a maze Potts (2012), finding a mutual friend He et al.
(2017), or splitting a set of items DeVault et al. (2015); Lewis et al.
(2017). Our CraigslistBargain dialogue falls in this category, but exhibits
richer and more diverse language than prior datasets. Our dataset calls for
systems that can handle both strategic decision-making and open-ended text
generation.

Traditional goal-oriented dialogue systems build a pipeline of modules Young
et al. (2013); Williams et al. (2016). Due to the laborious dialogue state
design and annotation, recent work has been exploring ways to replace these
modules with neural networks and end-to-end training while still having a
logical backbone Wen et al. (2017a); Bordes and Weston (2017); He et al.
(2017). Our work is closely related to the Hybrid Code Network Williams et al.
(2017), but the key difference is that Williams et al. (2017) uses a neural
dialogue state, whereas we keep a structured, interpretable dialogue state
which allows for stronger top-down control. Another line of work tackles this
problem by introducing latent stochastic variables to model the dialogue state
Wen et al. (2017b); Zhao et al. (2017); Cao and Clark (2017). While the latent
discrete variable allows for post-hoc discovery of dialogue acts and increased
utterance diversity, it does not provide controllability over the dialogue
strategy.

Our work is also related to a large body of literature on dialogue policies in
negotiation English and Heeman (2005); Efstathiou and Lemon (2014); Hiraoka et
al. (2015); Cao et al. (2018). These work mostly focus on learning good
negotiation policies in a domain-specific action space, whereas our model
operates in an open-ended space of natural language. An interesting future
direction is to connect with game theory Brams (2003) for complex multi-issue
bargaining. Another direction is learning to generate persuasive utterances,
e.g., through framing Takuya et al. (2014) or accounting for the social and
cultural context Elnaz et al. (2012).

To conclude, we have introduced CraigslistBargain, a rich dataset of human-
human negotiation dialogues. We have also presented a modular approach based
on coarse dialogue acts that models a rough strategic backbone as well
allowing for open-ended generation. We hope this work will spur more research
in hybrid approaches that can work in open-ended, goal-oriented settings.

#### Acknowledgments.

This work is supported by DARPA Communicating with Computers (CwC) program
under ARO prime contract no. W911NF-15-1-0462. We thank members of the
Stanford NLP group for insightful discussion and the anonymous reviewers for
constructive feedback.

#### Reproducibility.

All code, data, and experiments for this paper are available on the CodaLab
platform:
https://worksheets.codalab.org/worksheets/0x453913e76b65495d8b9730d41c7e0a0c/.

## References

  * Afantenos et al. (2012) S. Afantenos, N. Asher, F. Benamara, A. Cadilhac, C. Dégremont, P. Denis, M. Guhe, S. Keizer, A. Lascarides, O. Lemon, et al. 2012.  Modelling strategic conversation: Model, annotation design and corpus.  In _Proceedings of SemDial 2012: Workshop on the Semantics and Pragmatics of Dialogue_ , pages 167–168.
  * Asher et al. (2016) N. Asher, J. Hunter, M. Morey, F. Benamara, and S. Afantenos. 2016.  Discourse structure and dialogue acts in multiparty dialogue: the STAC corpus.  In _Language Resources and Evaluation Conference (LREC)_.
  * Bordes and Weston (2017) A. Bordes and J. Weston. 2017.  Learning end-to-end goal-oriented dialog.  In _International Conference on Learning Representations (ICLR)_.
  * Brams (2003) S. J. Brams. 2003.  _Negotiation Games: Applying Game Theory to Bargaining and Arbitration_.  Psychology Press.
  * Cao and Clark (2017) K. Cao and S. Clark. 2017.  Latent variable dialogue models and their diversity.  In _European Association for Computational Linguistics (EACL)_.
  * Cao et al. (2018) K. Cao, A. Lazaridou, M. Lanctot, J. Z. Leibo, K. Tuyls, and S. Clark. 2018.  Emergent communication through negotiation.  In _International Conference on Learning Representations (ICLR)_.
  * Cuayáhuitl et al. (2015) H. Cuayáhuitl, S. Keizer, and O. Lemon. 2015.  Strategic dialogue management via deep reinforcement learning.  In _Advances in Neural Information Processing Systems (NIPS)_.
  * DeVault et al. (2015) D. DeVault, J. Mell, and J. Gratch. 2015.  Toward natural turn-taking in a virtual human negotiation agent.  In _Association for the Advancement of Artificial Intelligence (AAAI)_.
  * Dhingra et al. (2017) B. Dhingra, L. Li, X. Li, J. Gao, Y. Chen, F. Ahmed, and L. Deng. 2017.  End-to-end reinforcement learning of dialogue agents for information access.  In _Association for Computational Linguistics (ACL)_.
  * Duchi et al. (2010) J. Duchi, E. Hazan, and Y. Singer. 2010.  Adaptive subgradient methods for online learning and stochastic optimization.  In _Conference on Learning Theory (COLT)_.
  * Efstathiou and Lemon (2014) I. Efstathiou and O. Lemon. 2014.  Learning non-cooperative dialogue behaviours.  In _Special Interest Group on Discourse and Dialogue (SIGDIAL)_.
  * Elnaz et al. (2012) N. Elnaz, G. Kallirroi, and T. David. 2012.  A cultural decision-making model for negotiation based on inverse reinforcement learning.  In _The Annual Meeting of the Cognitive Science Society_.
  * English and Heeman (2005) M. S. English and P. A. Heeman. 2005.  Learning mixed initiative dialog strategies by using reinforcement learning on both conversants.  In _Empirical Methods in Natural Language Processing (EMNLP)_.
  * He et al. (2017) H. He, A. Balakrishnan, M. Eric, and P. Liang. 2017.  Learning symmetric collaborative dialogue agents with dynamic knowledge graph embeddings.  In _Association for Computational Linguistics (ACL)_ , pages 1766–1776.
  * Hiraoka et al. (2015) T. Hiraoka, K. Georgila, E. Nouri, and D. Traum. 2015.  Reinforcement learning in multi-party trading dialog.  In _Special Interest Group on Discourse and Dialogue (SIGDIAL)_.
  * Keizer et al. (2017) S. Keizer, M. Guhe, H. Cuayahuitl, I. Efstathiou, K. Engelbrecht, M. Dobre, A. Lascarides, and O. Lemon. 2017.  Evaluating persuasion strategies and deep reinforcement learning methods for negotiation dialogue agents.  In _European Association for Computational Linguistics (EACL)_.
  * Lewis et al. (2017) M. Lewis, D. Yarats, Y. N. Dauphin, D. Parikh, and D. Batra. 2017.  Deal or no deal? end-to-end learning for negotiation dialogues.  In _Empirical Methods in Natural Language Processing (EMNLP)_.
  * Li et al. (2016) J. Li, W. Monroe, A. Ritter, D. Jurafsky, M. Galley, and J. Gao. 2016.  Deep reinforcement learning for dialogue generation.  In _Empirical Methods in Natural Language Processing (EMNLP)_.
  * Li et al. (2017) J. Li, W. Monroe, T. Shi, A. Ritter, and D. Jurafsky. 2017.  Adversarial learning for neural dialogue generation.  _arXiv preprint arXiv:1701.06547_.
  * Lowe et al. (2017) R. T. Lowe, N. Pow, I. Serban, L. Charlin, C. Liu, and J. Pineau. 2017.  Training end-to-end dialogue systems with the ubuntu dialogue corpus.  _Dialogue and Discourse_ , 8.
  * Pennington et al. (2014) J. Pennington, R. Socher, and C. D. Manning. 2014.  GloVe: Global vectors for word representation.  In _Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1532–1543.
  * Potts (2012) C. Potts. 2012.  Goal-driven answers in the Cards dialogue corpus.  In _Proceedings of the 30th West Coast Conference on Formal Linguistics_ , pages 1–20.
  * Sordoni et al. (2015) A. Sordoni, M. Galley, M. Auli, C. Brockett, Y. Ji, M. Mitchell, J. Nie, J. Gao, and B. Dolan. 2015.  A neural network approach to context-sensitive generation of conversational responses.  In _North American Association for Computational Linguistics (NAACL)_.
  * Takuya et al. (2014) H. Takuya, N. Graham, S. Sakriani, T. Tomoki, and N. Satoshi. 2014.  Reinforcement learning of cooperative persuasive dialogue policies using framing.  In _International Conference on Computational Linguistics (COLING)_.
  * Traum et al. (2008) D. Traum, S. C. Marsella, J. Gratch, J. Lee, and A. Hartholt. 2008.  Multi-party, multi-issue, multi-strategy negotiation for multi-modal virtual agents.  In _International Workshop on Intelligent Virtual Agents_ , pages 117–130.
  * Wen et al. (2017a) T. Wen, M. Gasic, N. Mrksic, L. M. Rojas-Barahona, P. Su, S. Ultes, D. Vandyke, and S. Young. 2017a.  A network-based end-to-end trainable task-oriented dialogue system.  In _European Association for Computational Linguistics (EACL)_ , pages 438–449.
  * Wen et al. (2017b) T. Wen, Y. Miao, P. Blunsom, and S. Young. 2017b.  Latent intention dialogue models.  In _International Conference on Machine Learning (ICML)_.
  * Williams et al. (2017) J. D. Williams, K. Asadi, and G. Zweig. 2017.  Hybrid code networks: Practical and efficient end-to-end dialog control with supervised and reinforcement learning.  In _Association for Computational Linguistics (ACL)_.
  * Williams et al. (2016) J. D. Williams, A. Raux, and M. Henderson. 2016.  The dialog state tracking challenge series: A review.  _Dialogue and Discourse_ , 7.
  * Williams (1992) R. J. Williams. 1992.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine learning_ , 8(3):229–256.
  * Young et al. (2013) S. Young, M. Gašić, B. Thomson, and J. D. Williams. 2013.  POMDP-based statistical spoken dialog systems: A review.  In _Proceedings of the IEEE_ , 5, pages 1160–1179.
  * Zhao et al. (2017) T. Zhao, R. Zhao, and M. Eskenazi. 2017.  Learning discourse-level diversity for neural dialog models using conditional variational autoencoders.  In _Association for Computational Linguistics (ACL)_.

Figure 2: Our chat interface for CraigslistBargain.

##  Appendix A CraigslistBargain Web Interface

Figure 2 shows our web interface where workers negotiate.

##  Appendix B Argument Detection of the Rule-based Parser

#### Price detection.

On CraigslistBargain, given an utterance, we want to detect mentioned prices
in it, which are arguments of intents such as propose and counter. We first
detect groud truth prices in the training data, which are numbers starting or
ending with the dollar sign. At test time, a number is considered a price if
it starts or ends with the dollar sign, or (a) its left and right neighboring
words appear next to ground truth prices in the training data and (b) it is
not larger than 1.5x of the listing price.

#### Item and count detection.

On DealOrNoDeal, given an utterance, we want to parse the proposed split of
items, i.e. numbers of balls, hats, and books for each agent. We first detect
first/second person pronouns, the three objects (ball, hat, and book), and
counts (1 to 10) by regular expression matching. To decide the grouping of
agent, object, and count, we process the utterance from left to right; as soon
as a pair of object and count is detected, we group it with the most recently
referred agent by resolving the pronouns (e.g., _“I”_ or _“you”_).

##  Appendix C Example Dialogues

Examples of human-bot chats on DealOrNoDeal are shown in Table 9, where bot
utterances are in bold. The full set of evaluation dialogues are available on
the Codalab worksheet.

| Item Count | Value to Bot | Value to Human
---|---|---|---
Book: | 2 | 4 | 3
Hat: | 1 | 2 | 0
Ball: | 2 | 0 | 2

A: SL(word) B: Human | A: SL(act) B: Human
---|---
| A: i would like the books and the hat .
---
B: you can have 1 book and a ball , i need a hat and a book
A: ok
B: deal
A: DEAL AGREED (book: 1, hat: 0, ball: 1)
B: DEAL AGREED (book: 1, hat: 1, ball: 1)
| A: i want the hat and 2 books
---
B: i would like the hat and one book
A: i would need the hat and the books
B: ok sounds fair
A: DEAL AGREED (book: 2, hat: 1, ball: 0)
B: DEAL AGREED (book: 0, hat: 0, ball: 2)

Table 9: Example human-bot dialogue on DealOrNoDeal. Bot utterances are
bolded. SL(word) is quick to concede, while SL(act) is generally harder to
persuade.


# HashFormers: Towards Vocabulary-independent Pre-trained Transformers

Huiyin Xue  Nikolaos Aletras
Department of Computer Science, University of Sheffield
United Kingdom
{hxue12<EMAIL_ADDRESS>
###### Abstract

Transformer-based pre-trained language models are vocabulary-dependent,
mapping by default each token to its corresponding embedding. This one-to-one
mapping results into embedding matrices that occupy a lot of memory (i.e.
millions of parameters) and grow linearly with the size of the vocabulary.
Previous work on on-device transformers dynamically generate token embeddings
on-the-fly without embedding matrices using locality-sensitive hashing over
morphological information. These embeddings are subsequently fed into
transformer layers for text classification. However, these methods are not
pre-trained. Inspired by this line of work, we propose HashFormers, a new
family of vocabulary-independent pre-trained transformers that support an
unlimited vocabulary (i.e. all possible tokens in a corpus) given a
substantially smaller fixed-sized embedding matrix. We achieve this by first
introducing computationally cheap hashing functions that bucket together
individual tokens to embeddings. We also propose three variants that do not
require an embedding matrix at all, further reducing the memory requirements.
We empirically demonstrate that HashFormers are more memory efficient compared
to standard pre-trained transformers while achieving comparable predictive
performance when fine-tuned on multiple text classification tasks. For
example, our most efficient HashFormer variant has a negligible performance
degradation (0.4% on GLUE) using only 99.1K parameters for representing the
embeddings compared to 12.3-38M parameters of state-of-the-art models.111Code
is available here: https://github.com/HUIYINXUE/hashformer and the pre-traied
HashFormer models are available here: https://huggingface.co/klein9692.

##  1 Introduction

The majority of transformer-based (Vaswani et al., 2017) pre-trained language
models (PLMs; Devlin et al. 2019; Liu et al. 2019; Dai et al. 2019; Yang et
al. 2019) are vocabulary-dependent, with each single token mapped to its
corresponding vector in an embedding matrix. This one-to-one mapping makes it
impractical to support out-of-vocabulary tokens such as misspellings or rare
words (Pruthi et al., 2019; Sun et al., 2020). Moreover, it linearly increases
the memory requirements with the vocabulary size for the token embedding
matrix (Chung et al., 2021). For example, given a token embedding size of 768,
BERT-base with a vocabulary of 30.5K tokens needs 23.4M out of 110M total
parameters while RoBERTa-base with 50K tokens needs 38M out of 125M total
parameters. Hence, disentangling the design of PLMs from the vocabulary size
and tokenization approaches would inherently improve memory efficiency and
pre-training, especially for researchers with access to limited computing
resources (Strubell et al., 2019; Schwartz et al., 2020).

Previous efforts for making transformer-based models vocabulary-independent
include dynamically generating token embeddings on-the-fly without embedding
matrices using hash embeddings (Svenstrup et al., 2017; Ravi, 2019) over
morphological information Sankar et al. (2021a). However, these embeddings are
subsequently fed into transformer layers trained from scratch for on-device
text classification without any pre-training. Clark et al. (2022) proposed
CANINE, a model that operates on Unicode characters using a low-collision
multi-hashing strategy to support ~1.1M Unicode codepoints as well as infinite
character four-grams. This makes CANINE independent of tokenization while
limiting the parameters of its embedding layer to 12.3M. Xue et al. (2022)
proposed models that take as input byte sequences representing characters
without explicit tokenization or a predefined vocabulary to pre-train
transformers in multilingual settings.

In this paper, we propose HashFormers a new family of vocabulary-independent
PLMs. Our models support an unlimited vocabulary (i.e. all possible tokens in
a given pre-training corpus) with a considerably smaller fixed-sized embedding
matrix. We achieve this by employing simple yet computationally efficient
hashing functions that bucket together individual tokens to embeddings
inspired by the hash embedding methods of Svenstrup et al. (2017) and Sankar
et al. (2021a). Our contributions are as follows:

  1. 1.

To the best of our knowledge, this is the first attempt towards reducing
memory requirements of PLMs using various hash embeddings with different hash
strategies aiming to substantially reduce the embedding matrix compared to the
vocabulary size;

  2. 2.

Three HashFormer variants further reduce the memory footprint by entirely
removing the need of an embedding matrix;

  3. 3.

We empirically demonstrate that our HashFormers are consistently more memory
efficient compared to vocabulary-dependent PLMs while achieving comparable
predictive performance when fine-tuned on a battery of standard text
classification tasks.

##  2 Related Work

###  2.1 Tokenization and Vocabulary-independent Transformers

Typically, PLMs are pre-trained on text that has been tokenized using subword
tokenization techniques such as WordPiece (Wu et al., 2016), Byte-Pair-
Encoding (BPE; Sennrich et al. 2016) and SentencePiece (Kudo and Richardson,
2018).

Attempts to remove the dependency of PLMs on a separate tokenization component
include models that directly operate on sequences of characters (Tay et al.,
2022; El Boukkouri et al., 2020). However, these approaches do not remove the
requirement of an embedding matrix. Recently, Xue et al. (2022) proposed PLMs
that take as input byte sequences representing characters without explicit
tokenization or a predefined vocabulary in multilingual settings. PLMs in
Clark et al. (2022) operating on Unicode characters or ngrams also achieved
the similar goal. These methods improve memory efficiency but still rely on a
complex process to encode the relatively long ngram sequences of extremely
long byte/Unicode sequences, affecting their computational efficiency.

In a different direction, Sankar et al. (2021b) proposed ProFormer, an on-
device vocabulary-independent transformer-based model. It generates token hash
embeddings (Svenstrup et al., 2017; Shi et al., 2009; Ganchev and Dredze,
2008) on-the-fly by applying locality-sensitive hashing over morphological
features. Subsequently, hash embeddings are fed to transformer layers for text
classification. However, ProFormer is trained from scratch using task-specific
data without any pre-training.

###  2.2 Compressing PLM Embeddings

A different line of work has focused on compressing the embedding matrix in
transformer models (Ganesh et al., 2021). Prakash et al. (2020) proposed to
use compositional code embeddings (Shu and Nakayama, 2018) to reduce the size
of the embeddings in PLMs for semantic parsing. Zhao et al. (2021) developed a
distillation method to align teacher and student token embeddings using a
mixed-vocabulary training (i.e. the student and teacher models have different
vocabularies) for learning smaller BERT models. However, these approaches
still rely on a predefined vocabulary. Clark et al. (2022) adopted low-
collision multi-hashing strategy to support ~1.1M Unicode codepoints and a
larger space of character four-grams with a relatively small embedding matrix
containing 12.3M parameters.

##  3 HashFormers

In this section, we present HashFormers, a family of vocabulary-independent
hashing-based pre-trained transformers.

###  3.1 Many-to-One Mapping from Tokens to an Embedding

Given a token $t$, HashFormers use a hash function $\mathcal{H}$ to map $t$
into a value $v$. Using hashing allows our model to map many tokens into a
single embedding and support an infinite vocabulary. We obtain the embedding
index by squashing its hash value $v$ into $i=[1,...,N]$ where
$\mathbf{e}=\mathbf{E}_{i}$ is the corresponding embedding from a matrix
$\mathbf{E}\in\mathbb{R}^{N\times d}$ where $N$ is the number of the
embeddings and $d$ is their dimensionality. We assume that $|V|\gg N$ where
$|V|$ is the size of the vocabulary. Subsequently, $\mathbf{e}$ is passed
through a series of transformer layers for pre-training. This is our first
variant, HashFormer-Emb that relies on a look-up embedding matrix (see Figure
1). Our method is independent of tokenization choices.

Figure 1: HashFormer-Emb.

###  3.2 Message-Direct Hashing (HashFormers-MD)

Our first approach to hash tokens is by using a Message-Digest (MD5) hash
function (Rivest and Dusse, 1992) to map each token to its 128-bits output,
$v=\mathcal{H}(t)$. The mapping can be reproduced given the same secret key.
MD5 is a ‘random’ hashing approach, returning mostly different hashes for
tokens with morphological or semantic similarities. For example:

$\displaystyle\text{MD5}(\text{`play'})$
$\displaystyle=\textit{d077f244def8a70e5ea758bd8352fcd8}$
$\displaystyle\text{MD5}(\text{`plays'})$
$\displaystyle=\textit{4a258d930b7d3409982d727ddbb4ba88}$

It is simple and does not require any pre-processing to obtain the bit
encoding for each token. To map the hash output $v$ into its corresponding
embedding, we transform its binary value into decimal and then compute the
index $i$ to $\mathbf{E}$ as $i=v\mathbin{\%}N$.

###  3.3 Locality-Sensitive Hashing (HashFormers-LSH)

Locality-sensitive hashing (LSH) hashes similar tokens into the same indices
with high probability (Rajaraman and Ullman, 2011). HashFormer-LSH uses LSH
hashing to assign tokens with similar morphology (e.g. ‘play’, ‘plays’,
‘played’) to the same hash encoding. This requires an additional feature
extraction step for token representation.

#### Token to Morphological Feature Vector:

We want to represent each token with a vector $\mathbf{x}$ as a bag of
morphological (i.e. character n-grams) features. For each token, we first
extract character n-grams ($n\in{1,2,3,4}$) to get a feature vector whose
dimension is equal to the vocabulary size.222We keep the top-50K most frequent
n-grams in the pre-training corpus. Each element in the feature vector is
weighted by the frequency of the character n-grams of the token.

#### Morphological Vector to Hash Index:

Once we obtain the morphological feature vector of each token, we first define
$N$ random hyperplanes, each represented by a random unit vector
$\mathbf{r^{i}}\in\mathbb{R}^{d_{x}}$, where $d_{x}$ is the dimensionality of
the morphological feature vector. Following a similar approach to Kitaev et
al. (2020), we compute the hash value $v$ as the index of the nearest random
hyperplane vector to the token’s feature vector, $\mathbf{x}$ obtained by
computing
$v=\mathcal{H}(\mathbf{x})=\operatorname*{arg\,max}(\mathbf{x}\mathbf{R}),\mathbf{R}=[\mathbf{r}^{1};...;\mathbf{r}^{N}]$
where $[\alpha;\beta]$ denotes the concatenation of two vectors. This approach
results into bucketing together tokens with similar morphological vectors.
Similar to HashFormer-MD-Emb, we compute the embedding index as
$i=v\mathbin{\%}N$.

To prevent storing a large projection matrix ($\mathbb{R}^{d_{x}\times N}$)
for accommodating each unit vector, we design an on-the-fly computational
approach. We only store a vector $\mathbf{\eta}\in\mathbb{R}^{d_{x}}$ that is
randomly initialized from the standard normal distribution, guaranteeing that
each column $\mathbf{r}$ in the matrix $\mathbf{R}$ is a permutation of
$\mathbf{\eta}$ with a unique offset value (e.g.
$\mathbf{r}^{1}=[\mathbf{\eta}_{2},...,\mathbf{\eta}_{N},\mathbf{\eta}_{1}]$).
Each offset value only relies on the index of the hyperplane. This setting
ensures that each hyperplane has the same L2-norm.

###  3.4 Compressing the Embedding Space

We also propose three embedding compression approaches that allow an even
smaller number of parameters to represent token embeddings and support
unlimited tokens (i.e. very large $|V|$) without forcing a large number of
tokens to share the same embedding. For this purpose, we first use a hash
function $\mathcal{H}$ to map each token $t$ into a $T$-bit value $b$,
$b\in[0,2^{T})$. Then, we pass $b$ through a transformation procedure to
generate the corresponding embedding (to facilitate computation, we cast $b$
into a $T$-bit vector $\mathbf{\tau}$). This way tokens with different values
$b$ will be assigned to a different embedding by keeping the number of
parameters relatively small. Figure 2 shows an overview of this method.

Figure 2: Compressing the embedding space.

#### Pooling Approach (Pool)

Inspired by Svenstrup et al. (2017) and Prakash et al. (2020), we first create
a universal learnable codebook, which is a matrix denoted as
$\mathbf{B}\in\mathbb{R}^{2^{k}\times d}$. Then, we split the hash bit vector
$\tau$ in $k$ successive bits without overlap to obtain
$\lceil\frac{T}{k}\rceil$ binary values. We then cast these binary values into
an integer value representing a codeword. Hence, each token is represented by
a vector $\mathbf{c}\in\mathbb{R}^{d}$ with elements $c_{j}\in[0,2^{k})$. For
example, given $k=4$ and a 12-bits vector [1,0,1,0,0,1,0,0,0,0,0,1], 4-bit
parts are treated as separate binary codewords [1010,0100,0001] then
transformed into their decimal format codebook [10,4,1]. We construct the
embedding $\mathbf{e}\in\mathbb{R}^{d}$ for each token by looking up the
decimal codebook and extracting $\lceil\frac{T}{k}\rceil$ vectors
corresponding to its $\lceil\frac{T}{k}\rceil$ codewords. We then apply a
weighted average pooling on them using a softmax function:

$\displaystyle\hat{\textbf{W}_{j}}$
$\displaystyle=\frac{\exp\textbf{W}_{j}}{\sum_{l=1}^{\lceil\frac{T}{k}\rceil}\exp\textbf{W}_{l}},j=1,..,\lceil\tfrac{T}{k}\rceil$
(1a) $\displaystyle\mathbf{e}$
$\displaystyle=\sum_{j=1}^{\lceil\frac{T}{k}\rceil}[\mathbf{B}_{\mathbf{c}}\odot\hat{\textbf{W}}]_{j}$
(1b)

where $\mathbf{W}\in\mathbb{R}^{\lceil\frac{T}{k}\rceil\times d}$ is a
learnable weight matrix as well as the codebook $\mathbf{B}$. The total number
of parameters required for this pooling transformation is
$(\lceil\frac{T}{k}\rceil+2^{k})\times d$. This can be much smaller than the
$N\times d$ parameters required for standard PLMs that use a one-to-one
mapping between tokens and embeddings, where
$N=|V|\gg(\lceil\frac{T}{k}\rceil+2^{k})$. Figure 3 shows the overview of the
Pool process.

Figure 3: HashFormer-Pool.

#### Additive Approach (Add)

Different to the Pool method that uses a universal codebook, we create $T$
different codebooks $\\{\textbf{B}^{1},\textbf{B}^{2},...,\textbf{B}^{T}\\}$,
each containing two learnable embedding vectors corresponding to codewords $0$
and $1$ respectively. We get a $T$-bits vector $\mathbf{\tau}\in\\{0,1\\}^{T}$
for each token, where each element in the vector $\mathbf{\tau}$ is treated as
a codeword. We look up each codeword in their corresponding codebook to obtain
$T$ vectors and add up them to compute the token embedding $\mathbf{e}$:

$\mathbf{e}=\sum^{T}_{j=1}\textbf{B}^{j}_{\mathbf{\tau}_{j}}\bigg{/}\gamma$
(2)

where $\mathbf{B}^{j}\in\mathbb{R}^{2\times d},j=1,..,T$, $\gamma$ is the
scaling factor.333Instead of averaging ($\gamma=T$), we set $\gamma=\sqrt{T}$
which we found to perform better in early experimentation. Hence, the total
number of parameters the additive transformation approach requires is $2\times
T\times d$. Similar to the Pool approach, the number of parameters required is
smaller than the vocabulary size: $2\times T\times d\ll N=|V|$.

Figure 4: HashFormer-Add.

#### Projection Approach (Proj)

Finally, we propose a new simpler approach compared to Pool and Add. We create
$T$ learnable random initialized vectors as $T$ pseudo-axes to trace the
orientation of each $T$-bits vector $\mathbf{\tau}$ corresponding to the token
$t$. Given a token bit vector $\mathbf{\tau}$, the $j$th element in the
embedding $\mathbf{e}$ is computed as the Pearson’s correlation coefficient
(PCC) between $\mathbf{\tau}$ and the learnable vector $\mathbf{w}^{j}$
corresponding to $j$.

$\displaystyle\mathbf{e}_{j}$
$\displaystyle=\frac{\langle\mathbf{\tau}-\bar{\tau},\mathbf{w^{j}}-\bar{\mathbf{w^{j}}}\rangle}{\|\tau-\bar{\tau}\|\centerdot\|\mathbf{w^{j}}-\bar{\mathbf{w^{j}}}\|},\quad
j=1,...,d$ (3) $\displaystyle\mathbf{e}$ $\displaystyle=(e_{1},...,e_{d})$

$\mathbf{w}^{j}\in\mathbb{R}^{d},j=1,..,T$, hence, the total number of
parameters the projection transformation approach requires is only $T\times
d\ll N=|V|$. Figure 5 depicts an overview of our HashFormer-Proj model.

###  3.5 Hashing for Compressed Embeddings

Similar to the embedding based HashFormers-Emb, our embedding compression-
based models also consider the same two hash approaches (MD and LSH) for
generating the $T$-bit vector of each token.

#### MD5:

We directly map the tokens to its 128-bits output $b$ with a universal secret
key.

#### LSH:

We repeat the same morphological feature extraction step to obtain a feature
vector $\mathbf{x}$ corresponding to each token $t$. However, rather than
using $2^{T}$ random hyperplanes that require storing vectors of size
$\mathbb{R}^{2^{T}}$, we simply use $T$ random hyperplanes similar to Ravi
(2019); Sankar et al. (2021b). Each bit in $b$ represents which side of the
corresponding hyperplane $\mathbf{r}\in\mathbb{R}^{d}$ the feature vector
$\mathbf{x}$ is located:
$b_{j}=\operatorname{sgn}(\operatorname{sgn}(\mathbf{x}\cdot\mathbf{r^{i}})+1),j=1,...,T$.
This allows an on-the-fly computation without storing any vector (Ravi, 2019).

Figure 5: HashFormer-Proj.

###  3.6 Pre-training Objective

Since our models support an arbitrary number of unique tokens, it is
intractable to use a standard Masked Language Modeling (Devlin et al., 2019)
pre-training objective. We opted using Shuffle + Random (S+R), a
computationally efficient three-way classification objective introduced by
Yamaguchi et al. (2021) for predicting whether tokens in the input have been
shuffled, replaced with random tokens or remain intact.

##  4 Experimental Setup

###  4.1 Baseline Models

We compare HashFormers against the following baselines: (i) a BERT-base model
(Devlin et al., 2019) with BPE tokenization and an MLM objective (BERT-MLM);
(ii) another BERT-base model with BPE tokenization and a Shuffle+Random
objective (BERT-S+R); (iii) Canine-C444We use the off-the-shelf Canine-C from
https://huggingface.co/google/canine-c. (Clark et al., 2022) a vocabulary-free
pre-trained PLM on Unicode character sequences; (iv) ProFormer555ProFormer is
not open-source, hence we have re-implemented it following the description of
the model in the paper. (Sankar et al., 2021b) a vocabulary-free LSH
projection based transformer model with two encoder layers that is not pre-
trained but only trained from scratch on the task at hand.

###  4.2 Implementation Details

#### Model Architecture

Following the architecture of BERT-base, we use 12 transformer layers, an
embedding size of 768 and a maximum sequence length of 512.666We note that the
transformer encoder could easily be replaced with any other encoder. For
HashFormers-LSH, we set $T=128$ to make it comparable to HashFormers-MD, as
MD5 produces a 128-bit hash value. For HashFormer-MD-Pool and HashFormer-LSH-
Pool, we choose $k=10$ to keep the number of total parameters for the
embeddings relatively small. We also experiment with two sizes of the
embedding matrix of HashFormers-Emb for MD and LSH hashing. The first uses an
embedding matrix of 50K, the same number of embedding parameters as BERT-base,
while the second uses 1K which is closer to the size of the smaller Pool, Add
and Proj models.

#### Hyperparameters

Hyperparameter selection details are in Appendix A.

#### Pre-training

We pre-train all HashFormers, BERT-MLM and BERT-S+R on the English Wikipedia
and BookCorpus (Zhu et al., 2015) from HuggingFace (Lhoest et al., 2021) for
up to 500k steps with a batch size of 128. For our HashFormer models, we use
white space tokenization resulting into a vocabulary of 11,890,081 unique
tokens. For BERT-MLM and BERT-S+R, we use a 50,000 BPE vocabulary Liu et al.
(2019).

#### Hardware

For pre-training, we use eight NVIDIA Tesla V100 GPUs. For fine-tuning on
downstream tasks, we use one NVIDIA Tesla V100 GPU.

###  4.3 Predictive Performance Evaluation

We evaluate all models on Glue (Wang et al., 2018) benchmark. We report
matched accuracy for MNLI, Matthews correlation for CoLA, Spearman correlation
for STS, F1 score for QQP and accuracy for all other tasks.

Model | Token | MNLI | QNLI | QQP | RTE | SST | MRPC | CoLA | STS | Avg.
---|---|---|---|---|---|---|---|---|---|---
BERT-MLM | subword | 81.9 | 88.9 | 86.7 | 60.4 | 92.0 | 85.7 | 54.5 | 86.0 | 79.5(0.4)
BERT-S+R | subword | 79.9 | 88.7 | 86.7 | 64.6 | 88.6 | 85.6 | 55.6 | 86.8 | 79.6(0.3)
CANINE-C | unicode | 77.7 | 87.6 | 82.8 | 62.0 | 85.7 | 81.4 | 2.3 | 83.9 | 70.4(1.3)
ProFormer | word | 45.2 | 59.1 | 71.4 | 53.9 | 82.1 | 71.2 | 9.7 | 22.1 | 51.8(0.5)
HashFormers-MD (Ours) |
Emb (50K) | word | 79.6 | 88.4 | 86.9 | 66.4 | 88.0 | 86.8 | 57.3 | 86.1 | 79.9(0.3)
Emb (1K) | word | 67.9 | 80.5 | 81.0 | 55.8 | 72.9 | 78.4 | 19.0 | 79.0 | 66.8(0.9)
Pool | word | 75.6 | 84.9 | 84.9 | 59.7 | 86.7 | 82.7 | 45.7 | 82.0 | 75.3(0.2)
Add | word | 76.2 | 86.3 | 85.2 | 60.2 | 86.6 | 81.9 | 47.4 | 82.2 | 75.7(0.5)
Proj | word | 76.0 | 85.8 | 84.8 | 60.9 | 87.3 | 83.0 | 45.9 | 82.1 | 75.7(0.3)
HashFormers-LSH (Ours) |
Emb (50K) | word | 76.1 | 86.5 | 85.5 | 65.5 | 83.6 | 84.2 | 42.7 | 83.7 | 76.0(0.3)
Emb (1K) | word | 65.6 | 80.1 | 80.0 | 56.4 | 71.3 | 78.1 | 5.2 | 76.9 | 64.2(0.8)
Pool | word | 78.0 | 87.7 | 86.4 | 65.6 | 88.1 | 84.2 | 55.3 | 85.6 | 78.9(0.3)
Add | word | 78.6 | 88.2 | 86.0 | 63.1 | 88.0 | 84.0 | 57.7 | 85.9 | 78.9(0.2)
Proj | word | 79.2 | 88.7 | 86.5 | 63.4 | 88.9 | 84.6 | 56.2 | 85.5 | 79.1(0.3)

Table 1: Results on Glue dev sets with standard deviations over three runs in
parentheses. Bold values denote best performing method in each task.

###  4.4 Efficiency Evaluation

Furthermore, we use the following metrics to measure and compare the memory
and computational efficiency of HashFormers and the baselines.

#### Memory Efficiency Metrics

We define the three memory efficiency metrics together with a performance
retention metric to use it as a point of reference:

  * •

Performance Retention Ratio: We compute the ratio between the predictive
performance of our target model compared to a baseline model performance. A
higher PRR indicates better performance.

$\mathbf{PRR}=\frac{\mathbf{score}_{model}}{\mathbf{score}_{baseline}}$ (4)

  * •

Parameters Compression Ratio (All): We compute use the ratio between the total
number of parameters of our target model and that of the baseline to measure
the memory efficiency of the target model compared to the baseline. A higher
$\text{PCR}_{\text{All}}$ score indicates better memory efficiency for the
entire model.

$\mathbf{PCR_{All}}=1-\frac{\mathbf{\\#}_{ModelParams}}{\mathbf{\\#}_{baselineParams}}$
(5)

  * •

Parameters Compression Ratio (Emb): We also use the ratio between the number
of parameters required by a target model for representing embeddings and that
of the baseline. A higher $\text{PCR}_{\text{Emb}}$ score indicates better
memory efficiency for the embedding representation.

$\mathbf{PCR_{Emb}}=1-\frac{\mathbf{\\#}_{ModelEmbParams}}{\mathbf{\\#}_{baselineEmbParams}}$
(6)

  * •

Proportion of Embedding Parameters: We also use the proportion of parameters
of embeddings out of the total parameters of each model to show the memory
footprint of the embedding space on each model.

$\mathbf{PoEP}=\frac{\mathbf{\\#}_{EmbParams}}{\mathbf{\\#}_{TotalParams}}$
(7)

Ideally, we expect a smaller PoEP, indicating that the embedding parameters
occupy as little memory as possible out of the total number of parameters of a
model.

For number of parameters calculations, please see Appendix B.

#### Computational Efficiency Metrics

We also measure the computational efficiency for pre-training (PT) and
inference (Infer). Each pre-training step is defined as a forward pass and a
backward pass. The inference is defined by a single forward pass.

  * •

Time per Sample (Time) This measures the average time of a sample completing a
PT or Infer step. It is measured in milliseconds (ms)/sample. Lower PT and
Infer time indicates a more computational efficient model.

  * •

Speed-up Rate We finally measure the model’s computation speed-up rate against
a baseline. It is defined as:

$\mathbf{Speed\text{-}upRate}=1\bigg{/}\frac{\mathbf{Time}_{model}}{\mathbf{Time}_{baseline}}$
(8)

##  5 Results

###  5.1 Predictive Performance Comparison

Table 1 presents results on Glue for our HashFormers models and all baselines.
We first observe that both the performance of our HashFormers-Emb models (MD
and LSH) are comparable to the two BERT variants (MLM and S+R) and CANINE-C on
average Glue score (79.9 and 76.0 vs. 79.5, 79.6 and 70.4 respectively).
Surprisingly, the more sophisticated HashFormer-LSH-Emb that takes
morphological similarity of tokens into account does not outperform
HashFormer-MD-Emb that uses a random hashing. We believe that HashFormer-MD
generally outperforms HashFormer-LSH mainly due to its ability to map
morphologically similar tokens to different vectors. This way it can
distinguish tenses etc.. On the other hand, HashFormer-LSH confuses words with
high morphological similarity (e.g. play, played) because it assigns them to
the same embedding.

However, LSH contributes to the performance improvement of smaller HashFormers
with compressed embedding spaces compared to their MD variants, i.e. Add (78.9
vs. 75.3), Add (78.9 vs. 75.7) and Proj (79.1 vs. 75.7). The best performing
compressed HashFormer-LSH-Proj model obtains 79.1 average Glue score, which is
only 0.4 lower than the BERT baselines. Reducing the number of embedding
vectors in Emb (1K) models is detrimental to performance and leads to drastic
drops between 11.8% and 13.1%. This indicates that the model size plays a more
important role than the choice of tokenization approach (i.e. white space or
BPE) or the vocabulary size (i.e. 12M vs. 50K). At the same time, comparing to
Emb, the Pool, Add and Proj approaches do not suffer from predictive accuracy
degradation, i.e. 0.4-4.2%.

All our HashFormers show clear advantages comparing to the LSH based ProFormer
which is not pre-trained across the majority of tasks (i.e. MNLI, QNLI, QQP,
MRPC, CoLA and STS). Although ProFormer shows that for a relatively simpler
sentiment analysis task (SST), pre-training might not be necessary.

###  5.2 Memory Efficiency Comparison

T  Emb. MNLI QNLI QQP RTE SST MRPC CoLA STS Glue Avg. #Total Params #Emb
Params PCR (All) PCR (Emb) PoEP CANINE-C 94.9 98.5 95.5 102.6 93.2 95.0 4.2
97.6 88.6 121.0M 12.3M 2.9 68.1 10.2 ProFormer 55.2 66.5 82.4 89.2 89.2 83.1
17.8 25.7 65.2 15.1M 322.6K 87.9 99.2 2.1 HashFormers-MD (Ours) Emb (50K) 97.2
99.4 100.2 109.9 95.7 101.3 105.1 100.1 100.5 124.6M 38.6M 0.0 0.0 31.0 Emb
(1K) 82.9 90.6 93.4 92.4 79.2 91.5 34.9 91.9 84.0 86.8M 797.2K 30.3 97.9 1.0
Pool 92.3 95.5 97.9 98.8 94.2 96.5 83.9 95.3 94.7 86.8M 797.2K 30.3 97.9 1.0
Add 93.0 97.1 98.3 99.7 94.1 95.6 87.0 95.6 95.2 86.2M 197.4K 30.8 99.5 0.2
Proj 92.8 96.5 97.8 100.8 94.9 96.8 84.2 95.5 95.2 86.1M 99.1K 30.9 99.7 0.1
HashFormers-LSH (Ours) Emb (50K) 92.9 97.3 98.6 108.4 90.9 98.2 78.3 97.3 95.6
124.6M 38.6M 0.0 0.0 31.0 Emb (1K) 80.1 90.1 92.3 93.4 77.5 91.1 9.5 89.4 80.8
86.8M 797.2K 30.3 97.9 1.0 Pool 95.2 98.7 99.7 108.6 95.8 98.2 101.5 99.5 99.2
86.8M 797.2K 30.3 97.9 1.0 Add 96.0 99.2 99.2 104.5 95.7 98.0 105.9 99.9 99.2
86.2M 197.4K 30.8 99.5 0.2 Proj 96.7 99.8 99.8 105.0 96.6 98.7 103.1 99.4 99.5
86.1M 99.1K 30.9 99.7 0.1

Table 2: Memory efficiency metrics and performance retention (%) on Glue for
HashFormer models, CANINE-C and ProFormer using BERT-MLM as a baseline.

Table 2 shows the results on memory efficiency and performance retention (%)
on GLUE using BERT-MLM as a baseline. Notably, Pool, Add and Proj models
provide large compression to the total number of embeddings parameters
compared to Emb as well as Canine-C and BERT variants. This is approximately a
30% $\text{PCR}_{\text{All}}$ and 97-99% $\text{PCR}_{\text{Emb}}$ compared to
BERT. These models also achieve very high performance retention (from 94.7% to
99.5%) which highlights their efficiency. In one case, HashFormer-LSH-Add
outperforms the BERT-MLM baseline on CoLA with a retention ratio of 105.9%
using only 197.4K parameters for token embeddings.

Proj variants, the smallest of HashFormers achieve the highest performance
retention (95.2% with MD, 99.5% with LSH) compared to Pool (94.7% with MD,
99.2% with LSH) and Add (95.2% with MD, 99.2% with LSH). Overall, they only
have a negligible drop in performance retention (0.5%) while they are
extremely more memory efficient. Proj uses a substantially smaller number of
embedding parameters (99.1K) compared to Canine-C and BERT variants (i.e.,
12.3M and 38.6M respectively). In general, Pool, Add and Proj models lead to a
30% reduction in the total number of parameters (around 30.0M) compared to the
baseline model and make their embedding footprint minimal, i.e. 0.1-1% PoEP.
On the other hand, Canine-C has a larger embedding footprint (10.2% PoEP) but
with similar or smaller performance retention compared to HashFormers.

Model |  PT Time (ms/samp) |  PT Speed-up Rate |  Infer Time (ms/samp) |  Infer Speed-up Rate
---|---|---|---|---
BERT
-MLM | 24.9 | 1.0 | 4.6 | 1.0
-S+R | 11.6 | 2.1x | 4.6 | 1.0x
Canine-C | - | - | 6.9 | 0.6x
HashFormers (Ours)
-Emb | 11.6 | 2.1x | 2.0~4.6 | 1.0x~2.4x
-Pool | 12.0 | 2.1x | 2.0~4.6 | 1.0x~2.3x
-Add | 11.7 | 2.1x | 2.0~4.6 | 1.0x~2.4x
-Proj | 10.6 | 2.4x | 1.8~4.6 | 1.0x~2.6x

Table 3: Results on pre-training speed and inference speed under different
embedding compression strategies. We use BERT-MLM as the baseline model. The
sequence length is fixed to 512 for pre-training. For inference, sequence
length is equal to the length of the longest sequence in the batch.

HashFormers-Emb have an embedding matrix of equal size (i.e. 50K embeddings)
as BERT. However, BERT only supports a vocabulary of 50K tokens, while
HashFormers-Emb supports an unlimited vocabulary, e.g. 12M unique tokens in
our pre-training corpora. Using a smaller embedding matrix (i.e. 1K), the
performance retention drops 20%~26%. Despite the fact that HashFormers-Emb
(1K) has a similar number of embedding parameters as the embedding compression
approaches (i.e. Pool, Add, Proj), it falls far behind those models, i.e.
between 8.5% and 14.3% for both MD and LSH variants. This demonstrates the
effectiveness of our proposed embedding compression approaches.

Although, the more lightweight ProFormer with only two transformer layers
consists of 15.1M parameters in total (approximately a 87.9%
$\text{PCR}_{\text{All}}$), its performance777The predictive performance of
ProFormer does not improve, even if we train it for four times more epochs (20
epochs). We report the results when trained for a maximum of five epochs. fall
far behind our worst HashFormer-MD-Pool with a difference of 29.5% PRR on Glue
Avg. score. Nevertheless, ProFormer requires more bits for hashing the tokens,
resulting in more parameters for representing token embeddings (322.6K)
comparing to HashFormers-Add and HashFormers-Proj (197.4K and 99.1K). Such
memory efficiency gains substantially sacrifice model’s predictive
performance.

###  5.3 Computational Efficiency Comparison

Table 3 shows the pre-training (PT) and inference (Infer) time per sample for
HashFormers, Canine-C, BERT-S+R using BERT-MLM as a baseline for reference. We
note that HashFormers have comparable pre-training training time (PT) to the
fastest BERT model (BERT-S+R). This highlights that the complexity of the pre-
training objective is more important than the size of the embedding matrix for
improving computational efficiency for pre-training.

During inference, we observe that the speed-up obtained by HashFormers is up
to 2.6x compared to both BERT models. However, this is due to the tokenization
approach. HashFormers operate on the word level, so the sequence length of the
input data is smaller, leading to inference speed-ups. Finally, we observe
that Canine-C has a slower inference time compared to both BERT models and
HashFormers. This might be due to its relatively more complex approach for
processing the long Unicode character input sequence.

##  6 Conclusions

We have proposed HashFormers, a family of vocabulary-independent hashing-based
pre-trained transformers. We have empirically demonstrated that our models are
computationally cheaper and more memory efficient compared to standard pre-
trained transformers, requiring only a fraction of their parameters to
represent token embeddings. HashFormer-LSH-Proj variant needs 99.1K parameters
for representing the embeddings compared to millions of parameters required by
state-of-the-art models with only a negligible performance degradation. For
future work, we plan to explore multilingual pre-training with HashFormers and
explore their ability in encoding linguistic properties Alajrami and Aletras
(2022).

## Limitations

We experiment only using English data to make comparisons with previous work
easier. For languages without explicit white spaces (e.g. Chinese and
Japanese), our methods can be applied with different tokenization techniques,
e.g. using a fixed length window of characters.

## Acknowledgments

This project made use of time on Tier 2 HPC facility JADE2, funded by EPSRC
(EP/T022205/1). We would like to thank Miles Williams and the anonymous
reviewers for their invaluable feedback.

## References

  * Alajrami and Aletras (2022) Ahmed Alajrami and Nikolaos Aletras. 2022.  How does the pre-training objective affect what large language models learn about linguistic properties? In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 131–147, Dublin, Ireland. Association for Computational Linguistics.
  * Chung et al. (2021) Hyung Won Chung, Thibault Fevry, Henry Tsai, Melvin Johnson, and Sebastian Ruder. 2021.  Rethinking embedding coupling in pre-trained language models.  In _International Conference on Learning Representations_.
  * Clark et al. (2022) Jonathan H. Clark, Dan Garrette, Iulia Turc, and John Wieting. 2022.  Canine: Pre-training an Efficient Tokenization-Free Encoder for Language Representation.  _Transactions of the Association for Computational Linguistics_ , 10:73–91.
  * Dai et al. (2019) Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoc Le, and Ruslan Salakhutdinov. 2019.  Transformer-XL: Attentive language models beyond a fixed-length context.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 2978–2988, Florence, Italy. Association for Computational Linguistics.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  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 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * El Boukkouri et al. (2020) Hicham El Boukkouri, Olivier Ferret, Thomas Lavergne, Hiroshi Noji, Pierre Zweigenbaum, and Jun’ichi Tsujii. 2020.  CharacterBERT: Reconciling ELMo and BERT for word-level open-vocabulary representations from characters.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 6903–6915, Barcelona, Spain (Online). International Committee on Computational Linguistics.
  * Ganchev and Dredze (2008) Kuzman Ganchev and Mark Dredze. 2008.  Small statistical models by random feature mixing.  In _Proceedings of the ACL-08: HLT Workshop on Mobile Language Processing_ , pages 19–20, Columbus, Ohio. Association for Computational Linguistics.
  * Ganesh et al. (2021) Prakhar Ganesh, Yao Chen, Xin Lou, Mohammad Ali Khan, Yin Yang, Hassan Sajjad, Preslav Nakov, Deming Chen, and Marianne Winslett. 2021.  Compressing large-scale transformer-based models: A case study on BERT.  _Transactions of the Association for Computational Linguistics_ , 9:1061–1080.
  * Kitaev et al. (2020) Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. 2020.  Reformer: The efficient transformer.  In _International Conference on Learning Representations_.
  * Kudo and Richardson (2018) Taku Kudo and John Richardson. 2018.  SentencePiece: A simple and language independent subword tokenizer and detokenizer for neural text processing.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 66–71, Brussels, Belgium. Association for Computational Linguistics.
  * Lhoest et al. (2021) Quentin Lhoest, Albert Villanova del Moral, Yacine Jernite, Abhishek Thakur, Patrick von Platen, Suraj Patil, Julien Chaumond, Mariama Drame, Julien Plu, Lewis Tunstall, Joe Davison, Mario Šaško, Gunjan Chhablani, Bhavitvya Malik, Simon Brandeis, Teven Le Scao, Victor Sanh, Canwen Xu, Nicolas Patry, Angelina McMillan-Major, Philipp Schmid, Sylvain Gugger, Clément Delangue, Théo Matussière, Lysandre Debut, Stas Bekman, Pierric Cistac, Thibault Goehringer, Victor Mustar, François Lagunas, Alexander Rush, and Thomas Wolf. 2021.  Datasets: A community library for natural language processing.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 175–184, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized BERT pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Prakash et al. (2020) Prafull Prakash, Saurabh Kumar Shashidhar, Wenlong Zhao, Subendhu Rongali, Haidar Khan, and Michael Kayser. 2020.  Compressing transformer-based semantic parsing models using compositional code embeddings.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 4711–4717, Online. Association for Computational Linguistics.
  * Pruthi et al. (2019) Danish Pruthi, Bhuwan Dhingra, and Zachary C. Lipton. 2019.  Combating adversarial misspellings with robust word recognition.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 5582–5591, Florence, Italy. Association for Computational Linguistics.
  * Rajaraman and Ullman (2011) Anand Rajaraman and Jeffrey David Ullman. 2011.  _Mining of massive datasets_.  Cambridge University Press.
  * Ravi (2019) Sujith Ravi. 2019.  Efficient on-device models using neural projections.  In _International Conference on Machine Learning_ , pages 5370–5379. PMLR.
  * Rivest and Dusse (1992) Ronald Rivest and S Dusse. 1992.  The MD5 message-digest algorithm.
  * Sankar et al. (2021a) Chinnadhurai Sankar, Sujith Ravi, and Zornitsa Kozareva. 2021a.  On-device text representations robust to misspellings via projections.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_ , pages 2871–2876, Online. Association for Computational Linguistics.
  * Sankar et al. (2021b) Chinnadhurai Sankar, Sujith Ravi, and Zornitsa Kozareva. 2021b.  ProFormer: Towards on-device LSH projection based transformers.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_ , pages 2823–2828, Online. Association for Computational Linguistics.
  * Schwartz et al. (2020) Roy Schwartz, Jesse Dodge, Noah A Smith, and Oren Etzioni. 2020.  Green AI.  _Communications of the ACM_ , 63(12):54–63.
  * Sennrich et al. (2016) Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016.  Neural machine translation of rare words with subword units.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1715–1725, Berlin, Germany. Association for Computational Linguistics.
  * Shi et al. (2009) Qinfeng Shi, James Petterson, Gideon Dror, John Langford, Alex Smola, Alex Strehl, and SVN Vishwanathan. 2009.  Hash kernels.  In _Artificial intelligence and statistics_ , pages 496–503. PMLR.
  * Shu and Nakayama (2018) Raphael Shu and Hideki Nakayama. 2018.  Compressing word embeddings via deep compositional code learning.  In _International Conference on Learning Representations_.
  * Strubell et al. (2019) Emma Strubell, Ananya Ganesh, and Andrew McCallum. 2019.  Energy and policy considerations for deep learning in NLP.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 3645–3650.
  * Sun et al. (2020) Lichao Sun, Kazuma Hashimoto, Wenpeng Yin, Akari Asai, Jia Li, Philip Yu, and Caiming Xiong. 2020.  Adv-BERT: BERT is not robust on misspellings! Generating nature adversarial samples on BERT.  _arXiv preprint arXiv:2003.04985_.
  * Svenstrup et al. (2017) Dan Svenstrup, Jonas Hansen, and Ole Winther. 2017.  Hash embeddings for efficient word representations.  _Advances in neural information processing systems_ , 30.
  * Tay et al. (2022) Yi Tay, Vinh Q. Tran, Sebastian Ruder, Jai Gupta, Hyung Won Chung, Dara Bahri, Zhen Qin, Simon Baumgartner, Cong Yu, and Donald Metzler. 2022.  Charformer: Fast character transformers via gradient-based subword tokenization.  In _International Conference on Learning Representations_.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in neural information processing systems_ , pages 5998–6008.
  * Wang et al. (2018) Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. 2018.  GLUE: A multi-task benchmark and analysis platform for natural language understanding.  In _Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_ , pages 353–355, Brussels, Belgium. Association for Computational Linguistics.
  * Wu et al. (2016) Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. 2016.  Google’s neural machine translation system: Bridging the gap between human and machine translation.  _arXiv preprint arXiv:1609.08144_.
  * Xue et al. (2022) Linting Xue, Aditya Barua, Noah Constant, Rami Al-Rfou, Sharan Narang, Mihir Kale, Adam Roberts, and Colin Raffel. 2022.  ByT5: Towards a token-free future with pre-trained byte-to-byte models.  _Transactions of the Association for Computational Linguistics_ , 10:291–306.
  * Yamaguchi et al. (2021) Atsuki Yamaguchi, George Chrysostomou, Katerina Margatina, and Nikolaos Aletras. 2021.  Frustratingly simple pretraining alternatives to masked language modeling.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 3116–3125, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Yang et al. (2019) Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le. 2019.  Xlnet: Generalized autoregressive pretraining for language understanding.  _Advances in neural information processing systems_ , 32.
  * Zhao et al. (2021) Sanqiang Zhao, Raghav Gupta, Yang Song, and Denny Zhou. 2021.  Extremely small BERT models from mixed-vocabulary training.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_ , pages 2753–2759, Online. Association for Computational Linguistics.
  * Zhu et al. (2015) Yukun Zhu, Ryan Kiros, Rich Zemel, Ruslan Salakhutdinov, Raquel Urtasun, Antonio Torralba, and Sanja Fidler. 2015.  Aligning books and movies: Towards story-like visual explanations by watching movies and reading books.  In _Proceedings of the IEEE international conference on computer vision_ , pages 19–27.

##  Appendix A Hyperparameters

The hyperparameters used in pre-training are listed in Table 4.

Hyperparameter | Pretraining
---|---
Maximum train epochs | 10 epochs
Batch size (per GPU) | 16 instances
Adam $\epsilon$ | 1e-8
Adam $\beta_{1}$ | 0.9
Adam $\beta_{2}$ | 0.9999
Sequence length | 512
Peak learning rate | 1e-4 for MLM, 5e-5 for others
Learning rate schedule | linear
Warmup steps | 10000
Weight decay | 0.01
Attention Dropout | 0.1
Dropout | 0.1

Table 4: Details of hyperparameters used in pre-training.

The hyperparameters used in fine-tuning are listed in Table 5.

Hyperparameter | Pretraining
---|---
Maximum train epochs | 5 epochs
Batch size (per GPU) | 32 instances
Adam $\epsilon$ | 1e-6
Adam $\beta_{1}$ | 0.9
Adam $\beta_{2}$ | 0.999
Peak learning rate | 3e-5
Learning rate schedule | cosine with hard restarts
Warmup steps | first 6% steps
Weight decay | 0
Attention Dropout | 0.1
Dropout | 0.1
Evaluation steps | 2455 for MNLI, 655 for QNLI,
| 2275 for QQP, 48 for RTE,
| 421 for SST, 69 for MRPC,
| 162 for CoLA and 108 for STS

Table 5: Details of hyperparameters used in fine-tuning.

##  Appendix B Model Parameter Counts

We count the total number of parameters of each model on a binary
classification task. This is computed by counting all learnable variables used
for the task (including those in the classification head) without freezing any
weights. For all BERT variants and our HashFormers, we adopt the same setting
of BERT-Base by setting $Dim_{hidden}=768$, $Dim_{intermediate}=3072$ with 12
hidden layers and 12 attention heads. For CANINE-C, we use the default base-
sized model whose $Dim_{hidden}=768$, $Dim_{intermediate}=3072$ and has 12
hidden layers and attention heads.

We only count the number of parameters which are used for retrieving or
generating the embeddings of any tokens (excluding those special tokens e.g.
<PAD>) and we also exclude those for position embeddings. Specifically,
$\\#_{[Model]EmbParams}$ are computed as the follow:

  * •

BERT variants:

$\\#_{BERT}=|V|\times d$ (9)

  * •

CANINE-C:

$\\#_{CANINE-C}=\\#_{HashBuckets}\times d$ (10)

CANINE-C employs 16,000 hash buckets (Clark et al., 2022).

  * •

ProFormer:

$\\#_{ProFormer}=\\#_{LSHDigestSize}\times d$ (11)

ProFormer hashes each token into a 420-bit vector (Sankar et al., 2021b).

  * •

HashFormers-Emb:

$\\#_{HashFormers}-Emb=N\times d$ (12)

  * •

HashFormers-Pool:

$\\#_{HashFormers}-Pool=(\lceil\frac{T}{k}+2^{k}\rceil)\times d$ (13)

  * •

HashFormers-Add:

$\\#_{HashFormers}-Add=2\times T\times d$ (14)

  * •

HashFormers-Proj:

$\\#_{HashFormers}-Proj=T\times d$ (15)

##  Appendix C HashFormers with BPE Tokenization

Table 6 presents results on Glue for our HashFomers with BPE tokenization. In
general, we observe that using BPE tokinization, the performance of HashFomers
slightly drops.

Model | Token | MNLI | QNLI | QQP | RTE | SST | MRPC | CoLA | STS | Avg.
---|---|---|---|---|---|---|---|---|---|---
HashFormers-MD |
Emb (50K) | subword | 78.6 | 87.7 | 86.0 | 65.6 | 88.5 | 85.1 | 51.2 | 85.0 | 78.5(0.4)
Emb (50K) | word | 79.6 | 88.4 | 86.9 | 66.4 | 88 | 86.8 | 57.3 | 86.1 | 79.9(0.3)
Proj | subword | 74.6 | 84.8 | 83.7 | 58.7 | 85.5 | 80.7 | 44.6 | 80.1 | 74.1(0.5)
Proj | word | 76.0 | 85.8 | 84.8 | 60.9 | 87.3 | 83.0 | 45.9 | 82.1 | 75.7(0.3)
HashFormers-LSH |
Emb (50K) | subword | 62.6 | 80.2 | 80.8 | 59.3 | 71.3 | 80.2 | 18.3 | 75.5 | 66.0(0.2)
Emb (50K) | word | 76.1 | 86.5 | 85.5 | 65.5 | 83.6 | 84.2 | 42.7 | 83.7 | 76.0(0.3)
Proj | subword | 78.2 | 87.5 | 86.3 | 64.3 | 88.6 | 85.5 | 51.2 | 85.1 | 78.3(0.1)
Proj | word | 79.2 | 88.7 | 86.5 | 63.4 | 88.9 | 84.6 | 56.2 | 85.5 | 79.1(0.3)

Table 6: Results on Glue dev sets with standard deviations over three runs in
parentheses using BPE tokenization.