# Effects of Algorithmic Trend Promotion:
Evidence from Coordinated Campaigns in Twitter’s Trending Topics

Joseph Schlessinger,1 Kiran Garimella,2111Corresponding author Maurice
Jakesch,3 Dean Eckles4

###### Abstract

In addition to more personalized content feeds, some leading social media
platforms give a prominent role to content that is more widely popular. On
Twitter, “trending topics” identify popular topics of conversation on the
platform, thereby promoting popular content which users might not have
otherwise seen through their network. Hence, “trending topics” potentially
play important roles in influencing the topics users engage with on a
particular day. Using two carefully constructed data sets from India and
Turkey, we study the effects of a hashtag appearing on the trending topics
page on the number of tweets produced with that hashtag. We specifically aim
to answer the question: How many new tweeting using that hashtag appear
because a hashtag is labeled as trending? We distinguish the effects of the
trending topics page from network exposure and find there is a statistically
significant, but modest, return to a hashtag being featured on trending
topics. Analysis of the types of users impacted by trending topics shows that
the feature helps less popular and new users to discover and spread content
outside their network, which they otherwise might not have been able to do.

##  1 Introduction

Leading social media platforms feature personalized feeds of content, often
largely based on what other accounts a user is connected to — whether through
directed or undirected ties or through group co-membership. However, some of
these platforms also give a prominent role to content that is more widely
popular. “Trending topics” is a feature on Twitter that directs users to
popular content on the platform within countries or regions. The algorithms
behind the feature identify viral content on the platform and provides users a
way to access the content even if they are not following any user who tweeted
about it. Ever since its launch over a decade ago, according to Twitter, the
feature has helped Twitter users “understand what is happening in the world
and what people’s opinions are about it” (Twitter 2015). The feature may also
allow Twitter to increase user engagement on the platform, by showing content
to users that they would not have otherwise seen, and boost revenue through
sponsored trends (Twitter 2020).

The trending topics page can also be thought of as an agenda setting tool. It
is a way to influence what people talk about: Twitter implicitly endorses
trending content as important and topical (Proferes and Summers 2019). The
feature has been used in a wide range of high profile events, spreading
messages and spurring conversations during crises events like earthquakes
(Sakaki, Okazaki, and Matsuo 2010), protests (Tufekci 2017; Bruns, Highfield,
and Burgess 2013), or popular sporting events (Knapp 2013). Trending topics
have also been used in harassment campaigns (Flores 2017; Chatzakou et al.
2017), to spread conspiracies (Dickson 2019) and disinformation (Hindman and
Barash 2018), and to amplify extremism (Brooking and Singer 2016). The
trending topics page is a coveted spot for those seeking to promote a
particular hashtag, as it provides algorithmic amplification to the content.
There are many examples of people manipulating the trending topics page to
gain free advertising for their cause (Jakesch et al. 2021; Elmas et al.
2021). All users identified as being in a particular geographical region see
the same trending topics. Once a topic is featured on the page, it is pushed
by Twitter to millions of Twitter users in the region, potentially garnering
more popularity.

Despite the important role the feature plays in popular discourse on social
media, there has not been any study to date investigating the impact of a
hashtag appearing on the trending topics page (henceforth just referred to as
trending). In this paper, we try to understand the causal impact of trending
on tweet volume for a given hashtag. We answer the question: How many new
tweets are caused by a hashtag appearing on the trending topics page? The
analysis helps us understand the power of the trending topics page as an
agenda setting tool; specifically, it explores the extent to which Twitter
contributes to a hashtags’ popularity by labeling it as trending.
Understanding this impact also offers insights into Twitter’s control over its
platform; can it simply pull the trending lever and make users talk about
certain topics?

While the impact of trending is important to understand, its measurement is
elusive for a few reasons. First, there are multiple ways a user can be
exposed to content on Twitter and it is difficult to know how a user has been
exposed with data publicly available. For example, users may engage with
content because they saw it on the trending topics page, saw a friend tweet
about it, or found it through search. Second, events on Twitter can interact
with the real-world or other social media sites, which further confounds
efforts to isolate the effect of trending. If a topic trends because of a
related real-world event, there is no way to know whether engagement is caused
by the actual event or its trending status. Moreover, the exact algorithm
behind trending topics is opaque and under constant revision (Lee and Oppong
2020), making it difficult to understand why a specific hashtag is trending.
In order to characterize the specific impact of the trending topics page, one
must account for all factors that can explain user engagement with a hashtag.
Under most circumstances, it is not possible to collect the necessary data to
perform this analysis without special access from Twitter.

Our analysis relies on two natural experiments to quantify the return to
trending. We use datasets from two different contexts (Turkey and India) where
astroturfed campaigns artificially promoted trends. The inauthentic nature of
these trends allows us to control for external events and thereby isolate the
causal effect of trending.

We find that a hashtag trending causes a 60 to 130% increase in new tweets
within 5 minutes of being trending. Even though this might appear high, the
effect is modest in absolute terms, amounting to approximately one new tweet
per minute. We find that the effect of a hashtag trending varies widely across
hashtags, which suggests content has some endogenous virality: certain trends
were more engaging than others. By measuring who gets exposed to the hashtag
via the trending topics page, we demonstrate that the trending topics page
allows a campaign to expose new parts of the network to the hashtag. Thus,
even though the trending topics page might have a modest absolute impact in
terms of new tweets, it helps promote content to parts of the network that
would not have been exposed otherwise. These results have implications on how
trending topics should be understood and the impacts of manipulating trending
topics.

##  2 Related Work

Trending topics were introduced in 2010 as a tool to organize user-generated
hashtags and help answer the “What’s happening?” question (Burgess and Baym
2020). Twitter trends have been a hallmark feature ever since and have been
constantly evolving. For instance, in September 2020, Twitter added more
context to trends along with displaying representative tweets for a trend.
Trending topics serve an important purpose: exposing users to popular, viral
and serendipitous content, which they might not otherwise not encounter
through their network. The exact algorithm behind identifying trending topics
is not known; however, Twitter reveals that trending topics are created based
on “both volume of a term but also the diversity of people and tweets about a
term and looking for organic volume increases above the norm” (Koumchatzky and
Andryeyev 2017).

The trending topics feature is not unique to Twitter. Facebook had a similar
feature showing popular content on the platform in 2014 but discontinued it in
2018.222https://about.fb.com/news/2018/06/removing-trending Instagram and
TikTok surface new, popular content, but recommendations are linked to users’
previous activity. This is a relevant difference from Twitter’s trends, which
are mostly geographical; thus, everyone within the same region might see the
same trends. Trending topics are also a source of revenue for Twitter. Twitter
offers “promoted trends,” where companies can pay to advertise a specific
hashtag at the top of the trending topics
page.333https://business.twitter.com/en/advertising/takeover/promoted-
trend.html

Twitter trending topics are regularly mentioned in mainstream news
sources.444For instance, a search on Google news for the term ‘trending on
twitter’ yields hundreds of results from mainstream news sources in just the
past week. https://news.google.com/search?q=trendingontwitter. Other work has
posited that Twitter trending topics have had an impact in encouraging
democratic protests (Tufekci 2017), helping disaster response (Ashktorab et
al. 2014), and enabling voices for the marginalized (Milan 2015; Jackson
2016). However, Twitter trends have also been manipulated and misused for
nefarious purposes, such as the spread of conspiracies (Dickson 2019),
misinformation (Hindman and Barash 2018), hate speech (Flores 2017; Chatzakou
et al. 2017) and election manipulation (Bail et al. 2020). Elmas et al. (Elmas
et al. 2021) estimate that these “ephemeral astroturfing attacks” are
responsible for at least 20% of top 10 global trends and up to 50% of trends
in Turkey. Manipulation of Twitter trends has been commonplace and well
documented in research (Zhang et al. 2017), and journalistic
pieces.555https://qz.com/africa/2086139/twitter-has-suspended-its-trends-
section-in-ethiopia/

Even though most of these cases (both positive and negative) are well studied,
it is extremely hard to study the impact that Twitter trends had on real world
outcomes. Regarding elections, Twitter often echoes other media forms, rather
than influence them. Candidates may use Twitter to generate publicity, but
this “buzz” may be irrelevant to election outcomes (Gayo-Avello 2012; Murthy
2015). Due to lack of access to exposure data, which only the social media
platforms have (Lazer 2020), unless in special cases, it is not possible to
make such inferences at scale. Asur et al. (2011) look at the emergence of
trending topics of Twitter and the factors that influence them. They find that
trends appearing on the trending topics page demonstrate linearly increasing
engagement, but it is unclear whether this effect is caused by the trending
topics page. At least some of the engagement driven by the trending topics is
“hashjacking” where users capitalize on the trending status of a hashtag to
advertise something unrelated (DFRLab 2020). While trending hashtags are well-
researched, there is little work on the actual impact of the trending topics
page.

There has been significant research on trying to identify and quantify
influence of content posted on Twitter (Riquelme and González-Cantergiani
2016). The most basic analysis looks at actions naively attributed to tweets,
such as retweets, favorites, and replies, or look at the influence of users,
based on their followers (Cha et al. 2010; Bakshy et al. 2011). Romero,
Meeder, and Kleinberg (2011) examine the relationship between influence and
the number of exposures to a certain hashtag and show that content differs in
the probability of adoption based on non-zero exposure, but it also differs in
the extent to which additional exposures increase probability of adoption.
Despite much effort, influence may be impossible to quantify in a meaningful
way, especially with an observational study. Homophily complicates attempts to
quantify peer effects with observational data (Bakshy et al. 2012). Moreover,
unobservable factors outside of the network may be responsible for user
behavior. In one estimate, 29% of information comes from factors beyond
Twitter (Myers, Zhu, and Leskovec 2012).

Our work falls into the category of studies performing algorithmic audits on
socio-technical systems. The two typical approaches used in literature for
audits are to make use of bot accounts or to work in collaboration with the
platforms. Many socio-technical platforms have been audited in the past couple
of years, including Google (Robertson et al. 2018), Uber (Chen, Mislove, and
Wilson 2015), Amazon (Juneja and Mitra 2021), and YouTube (Ribeiro et al.
2020). Specifically on Twitter, recent studies (Bandy and Diakopoulos 2021b;
Bartley et al. 2021) perform an audit on the algorithmic ranking feature
introduced by Twitter in 2017. Using bot accounts, the authors study the
properties of the algorithmic timeline in terms of the types of content it
surfaces, when compared to the chronological timeline. Another recent study
(Huszár et al. 2022) performs a large scale audit of algorithmic amplification
of politics on Twitter and finds that in six out of seven countries studied,
the mainstream political right enjoys higher algorithmic amplification than
the mainstream political left. They also find that right leaning media sources
are also favored by Twitter’s algorithms. Unlike previous approaches in this
realm, our approach makes use of a natural experiment to study the impacts of
trending topics on Twitter.

##  3 Data

One of the contributions of our paper is the curation of datasets which allows
us to study the causal impact of trending topics. We make use of two large-
scale datasets from Turkey and India containing hashtags which were
artificially trended using different astroturfing techniques. A quantitative
summary of the datasets is shown in Table 1.

###  3.1 Case Study 1: Turkey

The first dataset comes from Elmas et al. (2021). The dataset consists of
hundreds of hashtags from Turkey which were manipulated using a technique
termed “ephemeral astroturfing”. The attack takes place as follows: attackers
control tens of thousands of compromised accounts of real individuals, which
are used to tweet a specific hashtag in unison. These tweets only stay active
for a few seconds before they are deleted. However, due to a sudden surge in
the tweet volume, Twitter labels the hashtag as trending. As a result, these
hashtags appear on the trending topics page largely without associated tweets,
leading other users to add their own content using the hashtags. The tweets
for this dataset were collected in two stages. First, Elmas et al. collected
1% of all real-time tweets using the Twitter streaming API and discovered
astroturfed trends by detecting the unique properties of the campaigns. They
also collected complete global and Turkish trending information at a 5 minute
interval. Second, using the Twitter search API, we augmented this data by
collecting all existing tweets containing the astroturfed hashtags, along with
the full follower networks of participating users. In this paper, we made use
of the hashtags which reached the top 50 in Turkish trends at some point in
time in July 2019, which amounts to 418 hashtags with a total of over 3
million tweets made by over 790,000 users.

Most of the manipulated hashtags were illicit advertisements (e.g., gambling
sites), politics, policy appeals, and boycotts. These are unique because the
trends are promoted with tweets that use nonsensical assortments of Turkish
words (e.g. “to organize milk frost deposit panel”). They are deleted soon
after they are posted, so the trend appears on the Trending Topics page with
few associated tweets.

###  3.2 Case Study 2: India

The second dataset was collected during the 2019 general elections in India by
Jakesch et al. (2021). One of the leading political parties in the election
(the BJP) created an infrastructure of social media accounts for online
campaigning and mobilization of voters. The infrastructure consisted of a
network of volunteers incubated through public WhatsApp groups. Through these
volunteer networks, organizers coordinated “trend attacks” on Twitter. First,
through the WhatsApp groups, leaders disseminated links to Google Docs that
contained a bank of a few hundred “template” tweets (example tweets) for a
hashtag, that individuals could choose from. At a predetermined time, the
volunteers copy pasted these template tweets from their personal Twitter
accounts. The coordinated action would send a particular hashtag to the
trending topics page by tweeting in unison, thus fooling the Twitter trending
algorithm into thinking the hashtags were popular. For a more detailed
explanation of the dataset and the manipulation, see Jakesch et al. (2021).

The dataset contains 75 such campaigns, each with a corresponding hashtag,
making up over 2.3 million tweets from 244,000 users. The campaigns were
seemingly quite successful at their stated goal of making hashtags trend; 62
of the 75 campaigns were trending across India on the day the campaign was
organized. For this dataset, we only have half-hourly trending data indicating
whether a hashtag was trending nationally every 30 minutes. We also obtained
the follower and friend network of all the users in our dataset.

The manipulated hashtags are political messages, but not necessarily distinct
from “natural” political trends. They mostly support events or initiatives of
the BJP. They differ from regular trends in that they are due organizers
coordinating a volunteer network in the background to post pre-written
messages at an agreed time.

Table 1: Summary of the two datasets. Dataset | Hashtags | Tweets | Users |  | Median
---
tweets/hashtag
Turkey | 418 | 3M | 790k | 693
India | 75 | 2.36M | 244k | 5268

###  3.3 Importance of dataset choice

Both our datasets were carefully curated to fit the objective of our study.
One of the main obstacles to disentangling the effects of the trending topics
page is the presence of external events. In both case studies, we know that
the investigated trends have been artificially created. Moreover, we know
which tweets were used to artificially promote the hashtag. If we account for
these artificial tweets, we are left with tweets that are genuinely engaging
with the hashtag and are not responding to an event outside of Twitter. We can
then use information about the friend network (who the users follow) to
separate the effect of the trending topics page from natural diffusion across
the network. Finally, the dataset is linked to trending information. For all
investigated trends, we know when the hashtags appeared on the trending page
within some margin of error. With the Turkish data, we know the trending time
within 5 minutes and with the India data, we know the trending time within 30
minutes of uncertainty. Data on when hashtags appear on the trending page are
not available through Twitter’s API.

###  3.4 Terminology

Our methodology assumes hashtag use can be explained by three proximate
causes: (i) a users adopts the hashtag after someone in their friend network
uses it, (ii) from the trending topics page, or, or (iii) because of some
external event.666Admittedly, this is a simplification. These factors need not
be independent. For example, a user may be thinking about using a hashtag
because someone they follow uses it. Then, they see the hashtag on the
trending topics page and decide to tweet. On top of that, users can be exposed
to tweets from users outside their friends network, such as through Twitter’s
algorithmically-curated timeline. Please see Section 5 for discussion on how
these factors might impact our findings. Through out the rest of the paper, we
refer to two sets of users/tweets based on how they got exposed to a hashtag
prior to themselves posting the hashtag. If a user tweets a hashtag after one
of their friends tweet with the same hashtag, we call the user _network
exposed_ , indicating that they were likely exposed through their friend
network.777By extension we label the tweets by such users as network exposed
tweets. On the other hand, if a user tweets a hashtag without any prior
exposure through their friend network, we assume that they saw the hashtag
through the trending topics page and label the user _trending exposed_.

Figure 1 shows the fraction of network, trending exposed, and astroturfed
tweets in our dataset. We can see that the Turkish dataset has a much higher
fraction of exposure through the trending topics page. This is expected given
the way the manipulation works, where most original tweets that get the
hashtag trending are deleted, thus leaving a significant fraction of the
exposure through the trending topics page.

Figure 1: Distribution of network, trending exposed, and astroturfed tweets in
our datasets. Each observation is a single hashtag.

##  4 Causal Impact of Twitter’s Trending Topics

In this section, we study the causal impact of a hashtag trending on hashtag
tweet volume. This is typically a challenging query because, for any hashtag,
we only observe the trending and network exposed factors, but the user may
already be aware of the hashtag because they heard of it through an external
source (e.g., it being a popular topic that day). Such external, often
unobserved events, make it difficult to measure returns to trending. Hashtags
often have a real-world analogous event that drives hashtag engagement. Using
the Super Bowl as an example, many tweets will use #SuperBowl, but it may be
impossible to determine why they are using it. It could be because of tweets
from their Twitter friends, the trending topics page or because of the event
itself.

In our carefully chosen datasets, we observe relevant external events. These
hashtags were created and promoted by a group of actors for the sole purpose
of trending and did not have any prominent external events associated with
them prior. For instance, in the case of Indian dataset, we have the messages
from the WhatsApp groups in which the participants plan the tweets and can
identify template tweets (from lists of tweets in documents shared in the
WhatsApp groups). In the case of the Turkish data, the tweets used to create
the trend are deleted almost instantly and they are semantically distinct from
normal tweets. Thus, we can more safely assume that there is no other
contemporaneous external event that impacts the tweet volume. If we remove the
tweets we know are part of the manipulation (i.e. the astroturfed tweets), we
arrive at the following model to estimate the causal effect that the trending
topics page has on new tweets produced:

$\log(\operatorname{\mathbb{E}}(Y_{th}))=\alpha+\lambda D_{th}+\tau
t+\gamma(D_{th}\times t)+\beta E_{th}+\xi_{h},$ (1)

where $Y_{th}$ is the number of tweets with hashtag $h$ at time $t$, $D_{th}$
is a binary indicator for whether the hashtag $h$ is trending at time $t$,
$E_{th}$ is the tweets that came after friends network exposure, and $\xi_{h}$
are hashtag-specific fixed effects. Here $\lambda$ is the causal effect of
interest, which represents the volume of new tweets that happen specifically
because of the hashtag appearing on the trending topics page. Additionally,
$\gamma$ is the interaction effect between the trending and time, and in
practice represents the trending effect over time. In effect, we are measuring
the increase in tweets from users who had no exposure to the hashtag prior to
posting (trending exposed tweets) after the hashtag appears on the trending
topics page. It is important to note that we are estimating the immediate
impact of a hashtag appearing on the trending topics page. Near the initial
time of trending, there is very little exposure through the network. However,
as time goes on and more tweets occur, much of the network is exposed.

Figure 2 shows a visual depiction of our setup in the Turkish dataset. The
figure depicts the average tweet volume over all hashtags in our Turkey
dataset over time. The top part of the Figure includes all tweets, including
the exposures through the network and the trending topics page, while the
bottom specifically focuses on the tweets we estimate to have come through
trending exposure. The x-axis shows the time in minutes from the hashtag
appearing on the trending topics page. We can see a clear increase in the mean
tweet volume at time 0, which is when the hashtag starts trending. We use the
increase in trending exposed tweets, i.e., tweets that we assume come from
exposure via the trending topics page, to estimate the causal effect.

###  4.1 Modeling Considerations

We estimate Equation 1 using a quasi-Poisson generalized linear model, which
uses a log-link but which does not impose the assumption of equal mean and
variance of the Poisson distribution. We use a Poisson model because our
outcome of interest is a count of the number of tweets using a hashtag binned
every five minutes. Thus, the coefficients we report are a the logarithm of
the multiplicative increase in new tweets after the hashtag started trending.
In all the results, we use clustered standard errors at the hashtag level
(Liang and Zeger 1986). All the regression models reported included hashtag-
specific fixed effects.

While we collected trending information for the hashtags in both our datasets,
we did so at different temporal granularities. For the Turkish dataset, we
collected whether a hashtag was trending every 5 minutes (and thus have only a
5 minute error interval). On the other hand, for the Indian dataset, we only
have hourly trending information, which means our trending times could be off
by an hour in the worst case. Thus, we have an hour long period of uncertainty
about the treatment time or when the hashtag appeared on the trending topics
page. To deal with this period of uncertainty in the Indian dataset, we run
one set of models assuming the hashtag trended at the beginning of this period
(_Earliest_ model) and one model where we remove all data from the period of
uncertainty (_Donut hole_ model). The latter strategy is commonly used in the
regression discontinuity literature and is referred to as the “donut hole”
approach (Cattaneo and Titiunik 2021). For instance, if we record that a
hashtag was trending during the period 10–11 am, our _Earliest_ strategy would
assume that the hashtag started trending at 10 am, whereas the _Donut hole_
approach ignores all data during the hour and considers data starting at 11
am.

We depict this phenomenon in Figure 3, which shows the average tweet volume of
all the hashtags in our Indian dataset. The x-axis shows the minutes since the
hashtag was trending, where the zero indicates the top of hour in which the
hashtag was trending. The figure clearly shows how the _Donut hole_ approach
might produce an under-estimate since we ignore a large chunk of data and the
effects of trending do not last long.

Figure 2: The average number of tweets (per five minutes) for all hashtags
over time in the Turkish dataset. The top panel shows the average across all
the tweets, while the bottom panel shows on only the tweets that we estimate
to be potentially exposed through the trending topics page. Time is adjusted
to be minutes from appearing on the trending topics page. Note the sudden jump
in the tweet volume right at the time the hashtag was trending. Figure 3:
Average number of tweets (for every 5 minute bucket) in the Indian dataset.
The top panel shows the average across all the tweets, while the bottom panel
shows on only the tweets that we estimate to be potentially exposed through
the trending topics page. Time is adjusted to be minutes from appearing on the
trending topics page. The figure also shows our donut hole approach to
handling trending time uncertainty. In the Donut hole model, we drop tweets in
the 60 minute uncertainty period where the treatment status is uncertain.

###  4.2 Results

Figure 4 shows the effects of trending for both the datasets. The figure shows
the percentage increase in the tweet volume.888We plot the exponent of the
regression coefficient along with the 95% confidence intervals. Since we are
using a quasi-Poisson model, the coefficient indicates the effect on a
logarithmic scale. We find that appearing on the trending topics page leads to
an immediate increase in tweet volume of between 60 and 130% on average. For
India, we also present results for two scenarios: _Earliest_ and _Donut hole_.
The point estimates remain similar for both approaches, however, as expected,
the confidence intervals for the _Donut hole_ approach are wider. The full
regression output for both datasets can be found in Table 2 in the Appendix.

#### Effect of trending position.

The position of the hashtag in the trending list might affect the returns of
trending. A trending hashtag can be the first item displayed on the trending
topics page or the 50th. To understand the impacts of the position, we modify
our model in Equation 1 to include an additional effect for when a hashtag
reaches the top 10 of the trending topics page, which can result in the topic
appearing on the home page, at least for Web users. This gives the following
model:

$Y_{th}=\alpha+\lambda D_{th}+\tau t+\gamma(D_{th}\times t)+\beta E_{th}+\rho
D^{10}_{th}+\xi_{h}+\epsilon_{th}$ (2)

where $D^{10}_{th}$ is a dummy for whether hashtag $h$ is in the top 10 of
trends at time $t$, $\rho$ gives the additional return to a hashtag moving
from the top 50 to the top 10 and $\rho+\lambda$ can be thought of as the
total return to reaching the top 10. This model relies on a hashtag reaching
the top 50 and the top 10 at different times. This requires more granularity
than the Indian dataset’s hourly trending data, and thus this analysis can
only be performed on the Turkish dataset, with it’s trending data available
every 5 minutes. In Turkey, all the 418 trends that reached the top 50 also
reached the top 10 and a total of 89 hashtags entered the top 50 and top 10 at
different times. When we study both treatment effects, we find that trending
causes a $\approx 130\%$ increase in new tweets using the hashtag. There is an
additional boost of $\approx 4\%$ when a hashtag enters the top 10. While this
top 10 “boost” alone is not statistically significant, the total effect of
trending in the top 10 is jointly significant ($\lambda+\rho\neq 0$ with
$p<.0001$ ).

Figure 4: Estimated effects of a hashtag trending in the top 50 for both
datasets. Error bars are cluster-robust 95% confidence intervals clustered on
hashtag.

#### Effects over time.

Next, we look at the returns to trending over time. As can be seen in Figures
2 and 3, the effects of a hashtag trending appear to dissipate quickly. To
quantify this effect, we look at the coefficient of the interaction of
trending and time in Equation 1 in Table 2. While there is a positive slope
prior to trending, this is negated or reverses once the hashtag is trending.

#### Potential bias and external validity.

While there is some possibility that some trending exposed tweets were not
caused by the trending topics page (they may have been from the algorithmic
timeline, false positives from gaps in the friend network (from private
users), or artifacts of deleted tweets), which would tend to overstate the
trending effect, many of the assumptions we made are conservative. By
construction, any users that were exposed through their follower network
cannot be impacted by the trending topics page. This tends to underestimate a
trending effect because it is very possible for a user to not see every tweet
that appears on their timeline. In the Indian case study, for example, many
users are only exposed to the hashtag by accounts like BJP politicians and
official BJP accounts, who have millions of followers. As soon as an account
like @bjp4india (17.4 million followers in January 2022) uses one of the
hashtags, millions of users on the network are thereby network exposed and
thus “disqualified” — according to our assumptions — from contributing to the
trending effect. Our analysis shows that while only 2.5% of all users belonged
to the trending exposed group, $\approx$16% of users tweeted a hashtag after
exactly one friend used the hashtag. It is possible that some of these users
with only one network exposure may have actually been caused by trending
topics page exposure. This is not an issue of concern with Turkey because the
campaigns were not started by high-centrality users.

In addition to being an underestimate, this estimate is likely specific to
these circumstances (artificially seeded Turkish trends or Indian political
Twitter and pro-BJP political hashtags). The trending topics page in different
markets covering different subjects likely has a different return. Even within
this case study, different hashtags see very different returns, which is
consistent with the idea that content has endogenous virality (Goel et al.
2016).

While our estimates may be smaller than the real effect size, the true returns
to trending are likely still modest. We also point to caution in interpreting
the results — a 60 to 130% increase may sound large, but this should be put in
the proper context of the campaigns, which involve very few tweets prior to
the campaign beginning and thus prior to them trending. Much of the hashtag
adoption in these campaigns can be explained by organic spread via the
follower network. This suggests that Twitter’s trending topics page might not
be such a powerful agenda setting tool. That is, simply (artificially)
promoting a trend to the trending topics page does not cause massive
widespread adoption. Consistent with the literature, most of the hashtag
adoption comes from the influence by high-degree users and network diffusion.
Still, the trending topics page may be useful to a campaign like the cases
used in this paper by enabling the hashtag to reach new audiences outside the
range of network diffusion. We explore this topic in the following section.

###  4.3 Who participates because of exposure through the trending topics
page?

While we quantified the causal effect of a hashtag appearing on the trending
topics page, an important unanswered question is who is reached by the
trending topics page. One argument that is often made on the benefits of
having a trending page is that it helps solve the cold start problem for new
users and expose users to content which they might not have seen otherwise. In
this section, we explore the characteristics of the users who participate
after a hashtag trends. Our results, using data from both India and Turkey,
show that users exposed through the trending topics page are less popular,
less active, lower degree users, but are able to expose more of their
followers because they spread the trend in a previously unexposed part of the
Twitter network.

We compare users across the network exposed and trending exposed groups. For
each group, we compare users along three characteristics: activity (tweet
volume), network measures (such as followers/friends), and their effectiveness
to convince others. Figure 5 shows the results.

(a)

(b)

(c)

Figure 5: (a) Tweet volume, (b) Network characteristics, and (c) Effectiveness
of exposing others. The characteristics that are statistically significant are
marked with ***.

In both our datasets, participants who are exposed to the trend via trending
are generally less active (Figure 5 (a), posting less number of tweets), and
less popular (Figure 5 (a), with fewer number of friends) when compared to the
users who were exposed through the network. Both these differences are
statistically significant at the $p$ <.01 level. Moreover, those exposed to
the trend through the trending topics page are less connected to the main
Twitter network, as evidenced by their follower and friend numbers (Figure
5(b)).

Despite being less popular, these users are still effective at exposing new
users to the trend by bringing the hashtag to a relatively unexposed Twitter
community (Figure 5 (c)). To compute the effectiveness of exposing new users,
we first identified users who were trending exposed, and then looked at what
fraction of their followers tweet a hashtag after they tweet the hashtag.
Users reached through the trending topics page often expose a significantly
larger fraction of their followers compared to users who were network exposed.
On average, while around 40% of the followers of the trending exposed users
were exposed through them, only 20% of the followers of the network exposed
group were reached. This provides evidence that the trending topics page
allows the campaigns to reach new users who are not as connected to pro-BJP
Indian political Twitter.999We only collected the follower data only for
India, and hence can provide these estimates only for India.

In general, these findings support the idea that trending can be important for
expanding an idea beyond a highly connected sub-network. This may be
especially important in considering the impact of trends, where manipulated
campaigns like the political campaigns in the Indian case reach new audiences.
Spreading the hashtag within pro-BJP Twitter echo chamber may not provide a
return on investment in creating the infrastructure to manipulate the trends
from an agenda setting standpoint because the users are already sympathetic to
the BJP cause. However, if the trending section helps the hashtag reach a more
diverse set of users, this can be quite helpful in setting the agenda in more
moderate Twitter communities.

##  5 Discussion

In this paper, using carefully curated datasets, we study the causal impact of
a hashtag appearing on the trending topics page on Twitter. Our analysis
suggests that the returns to trending are limited. While in both case studies
there is a detectable boost in engagement from trending, the effect size is
small. Simply put, the trending topics page cannot create a massively popular
hashtag on its own; the spread through the network still plays an important
role in creating viral trends. However, the trending topics page does give an
ambitious agenda-setter the opportunity to reach a broader audience than what
is just possible through network seeding.

Even with all the steps we took in conducting the analysis and reporting the
results, our work has limitations, which mostly arise from data access issues.
First, there is the issue of accessing historical trending information, which
is challenging to collect and lacks the granularity desired for this kind of
study. Even with our effort to collect trending data in real time, without
access to granular trending data, our estimates can have bias and lower
statistical precision (particularly in our Indian dataset). Secondly, our
analysis hinges on exposure through the follower network, and we posit that
everyone who follows a user is exposed by their content instantly after
tweeting. To the extent that this misclassifies users who are induced to use a
hashtag as network, rather than trending exposed, we expect this attenuates
our estimates. Since exposure data is only available to the social media
companies (Lazer 2020), this is a systemic problem for any academic research
paper trying to audit these social media systems. Thirdly, we assume that
exposure through the trending topics page leads people to tweet the hashtag.
People may be influenced by the trend, yet not be inspired to use the hashtag
and may, for instance, just retweet or like content with the hashtag. We have
no way of measuring such an effect.

Finally, we lack some important information about algorithms for trending
topics and other parts of Twitter. The exact algorithm behind the trending
topics section is unknown to external researchers. There are some exposure
sources, such as exposure to content in Twitter’s main algorithmically-ranked
feed that is not from accounts followed by a user (e.g. the “liked by @user”
feature), which we have not accounted for here. The amount of such content
that is included in users’ feeds (starting in 2017) has changed over the
years, thereby perhaps modifying both effects of trending topics and our
ability to distinguish this from other exposures (Koumchatzky and Andryeyev
2017). That is, as is the issue with any audit study, the exact technology
used is constantly evolving. To check whether algorithmic ranking influences
how trending hashtags are shown to users, we obtained data collected by Bandy
and Diakopoulos (2021a) to compare chronological and non-chronological (i.e.
algorithmic) ranking. From the 3,000 hashtags from their data, we looked for
hashtags which were trending on the day the data was collected which gave us
148 hashtags. For these hashtags, we looked at whether their ranking in the
feed is significantly different in the algorithmic vs. chronological timeline.
We find no significant difference (p $\textgreater$ 0.1). Even though this
does not provide concrete evidence that trending hashtags were not impacted by
algorithmic ranking in the cases we study, we could build on such measurement
to study the effects of algorithmic ranking in future work.

Despite these limitations, we believe our study makes an impactful
contribution to the literature. Even a lower bound, context specific result is
interesting, since our methodology is generic and can be extended to include
other cases where astroturfing happens. We also use multiple large datasets
from different real world contexts. The datasets, by design can partly help
address some of the limitations. For instance, in the Turkish dataset, all the
tweets that are used to make the hashtag trend are deleted in a short time
frame. So the chances of users getting exposed through the network (at least
in the initial few minutes) is quite low.

### Ethics Statement

The paper provides analysis and results on a highly relevant and current
topic: the ethics of algorithmic amplification. Our paper provides concrete,
data driven evidence to build the case for a debate on trending topics. As we
saw from our results, the effects of trending might be short lived but
depending on the case, they might be impactful. As with the two cases used in
our analysis, Twitter trends have been widely manipulated and artificially
manipulated trends happen all the time. There have been numerous calls to
disable trending topics, due to posited harms and their susceptibility to
manipulation.101010e.g. See https://bit.ly/33EuwK8 In many cases, the
manipulation of trending topics is readily detectable and can be fixed easily,
though perhaps such campaigns would effectively adapt in response to such
efforts.. The Indian WhatsApp campaigns are easily detectable based on their
repetitive content (Jakesch et al. 2021). With the Turkish ephemeral trend
attacks, Twitter could simply account for deleted tweets in the trending
algorithm (Elmas et al. 2021). In October 2020, in preparation for the 2020 US
election, Twitter started adding more context to their trending topics just
for users in the United States, thus manually curating trending topics.
Compared with the U.S., where trends are at most rarely astroturfed,
astroturfed trending topics are apparently more common in the Global South, in
countries such as Nigeria, India, and Brazil. This can reflect a pattern of
U.S. tech companies neglecting less lucrative foreign markets. This paper
contributes evidence about the prevalence and consequences of trending topics,
which could feature in arguments for greater effort ensuring the integrity of
trending topics or removing that feature where they cannot.

##  6 Acknowledgements

J.S. was funded by the MIT Lincoln Laboratory Military Fellowship. K.G.
completed part of this work while at MIT and was supported by a Michael Hammer
postdoctoral fellowship. His research is supported through funding from Knight
Foundation, Google and NSF. D.E. was a paid consultant to Twitter while this
work was undergoing revision. K.G. and D.E. have received received funding for
other work from Meta Platforms.

## Appendix

### Regression Tables

The full regression results are shown in Table 2.

Table 2: Regression results | Turkey | India
---|---|---
| Combined | Standard | Earliest | Donut Hole
Intercept | 2.654∗∗∗ | 2.778∗∗∗ | 1.282∗∗∗ | 1.406∗∗∗
| (0.159) | (0.153) | (0.155) | (0.144)
Trending ($\lambda$) | 0.836∗∗ | 0.823∗∗∗ | 0.506∗∗∗ | 0.524∗
| (0.224) | (0.142) | (0.182) | (0.312)
Exposed Tweets ($\beta$) | 0.004∗∗∗ | 0.003∗∗∗ | 0.033∗∗∗ | 0.034∗∗∗
| (0.001) | (0.001) | (0.006) | (0.007)
Time ($\tau$) | 0.016∗∗∗ | 0.027∗∗∗ | 0.007∗∗∗ | 0.007∗∗∗
| (0.008) | (0.007) | (0.003) | (0.003)
Time $\times$ Trending ($\gamma$) | -0.019∗∗ | -0.027∗∗∗ | -0.007∗∗∗ | -0.007∗
| (0.008) | (0.007) | (0.003) | (0.004)
Trending in Top 10 ($\rho$) | 0.042 |  |  |
| (0.245) |  |  |
Observations | 10,327 | 7,346 | 2,441 | 1,790
$R^{2}$ | 0.856 | 0.855 | 0.691 | 0.698
Note: |  |  ∗p$<$0.1; ∗∗p$<$0.05; ∗∗∗p$<$0.01
|  |  Standard errors clustered at hashtag level.

## References

  * Ashktorab et al. (2014) Ashktorab, Z.; Brown, C.; Nandi, M.; and Culotta, A. 2014.  Tweedr: Mining twitter to inform disaster response.  In _ISCRAM_ , 269–272. Citeseer.
  * Asur et al. (2011) Asur, S.; Huberman, B. A.; Szabo, G.; and Wang, C. 2011.  Trends in Social Media: Persistence and Decay.  _SSRN Electronic Journal_.
  * Bail et al. (2020) Bail, C. A.; Guay, B.; Maloney, E.; Combs, A.; Hillygus, D. S.; Merhout, F.; Freelon, D.; and Volfovsky, A. 2020.  Assessing the Russian Internet Research Agency’s impact on the political attitudes and behaviors of American Twitter users in late 2017.  _Proceedings of the national academy of sciences_ , 117(1): 243–250.
  * Bakshy et al. (2011) Bakshy, E.; Hofman, J. M.; Mason, W. A.; and Watts, D. J. 2011.  Everyone’s an Influencer: Quantifying Influence on Twitter.  In _Proceedings of the Fourth ACM International Conference on Web Search and Data Mining - WSDM ’11_ , 65. Hong Kong, China: ACM Press.  ISBN 978-1-4503-0493-1.
  * Bakshy et al. (2012) Bakshy, E.; Rosenn, I.; Marlow, C.; and Adamic, L. 2012.  The Role of Social Networks in Information Diffusion.  In _Proceedings of the 21st International Conference on World Wide Web_ , WWW ’12, 519–528. New York, NY, USA: Association for Computing Machinery.  ISBN 978-1-4503-1229-5.
  * Bandy and Diakopoulos (2021a) Bandy, J.; and Diakopoulos, N. 2021a.  Curating Quality? How Twitter’s Timeline Algorithm Treats Different Types of News.  _Social Media+ Society_ , 7(3): 20563051211041648.
  * Bandy and Diakopoulos (2021b) Bandy, J.; and Diakopoulos, N. 2021b.  More Accounts, Fewer Links: How Algorithmic Curation Impacts Media Exposure in Twitter Timelines.  _Proceedings of the ACM on Human-Computer Interaction_ , 5(CSCW1): 1–28.
  * Bartley et al. (2021) Bartley, N.; Abeliuk, A.; Ferrara, E.; and Lerman, K. 2021.  Auditing Algorithmic Bias on Twitter.  In _13th ACM Web Science Conference 2021_ , 65–73.
  * Brooking and Singer (2016) Brooking, E. T.; and Singer, P. W. 2016.  War Goes Viral.  https://www.theatlantic.com/magazine/archive/2016/11/war-goes-viral/501125/.
  * Bruns, Highfield, and Burgess (2013) Bruns, A.; Highfield, T.; and Burgess, J. 2013.  The Arab Spring and social media audiences: English and Arabic Twitter users and their networks.  _American behavioral scientist_ , 57(7): 871–898.
  * Burgess and Baym (2020) Burgess, J.; and Baym, N. K. 2020.  _Twitter: A biography_.  NYU Press.
  * Cattaneo and Titiunik (2021) Cattaneo, M. D.; and Titiunik, R. 2021.  Regression Discontinuity Designs.  _arXiv preprint arXiv:2108.09400_.
  * Cha et al. (2010) Cha, M.; Haddadi, H.; Benevenuto, F.; and Gummadi, K. P. 2010.  Measuring User Influence in Twitter: The Million Follower Fallacy.  _Proceedings of the International AAAI Conference on Web and Social Media_ , 4(1): 8.
  * Chatzakou et al. (2017) Chatzakou, D.; Kourtellis, N.; Blackburn, J.; De Cristofaro, E.; Stringhini, G.; and Vakali, A. 2017.  Hate is not binary: Studying abusive behavior of# gamergate on twitter.  In _Proceedings of the 28th ACM conference on hypertext and social media_ , 65–74.
  * Chen, Mislove, and Wilson (2015) Chen, L.; Mislove, A.; and Wilson, C. 2015.  Peeking beneath the hood of uber.  In _Proceedings of the 2015 internet measurement conference_.
  * DFRLab (2020) DFRLab. 2020.  South African Twitter Accounts Gamed Trending Algorithms to Promote Prank Political Hashtags.  https://bit.ly/3nWBjZP.
  * Dickson (2019) Dickson, E. 2019.  A Jeffrey Epstein-Clinton Conspiracy Theory Was Trending — And That’s a Problem.  https://www.rollingstone.com/culture/culture-features/jeffrey-epstein-clinton-conspiracy-theories-twitter-863446/.
  * Elmas et al. (2021) Elmas, T.; Overdorf, R.; Özkalay, A. F.; and Aberer, K. 2021.  Ephemeral astroturfing attacks: The case of fake Twitter trends.  In _2021 IEEE European Symposium on Security and Privacy (EuroS &P)_, 403–422. IEEE.
  * Flores (2017) Flores, N. M. 2017.  Tweeting the gendered city: Analysis of harassment, reflections on justice.  _Journal of Critical Thought and Praxis_ , 6(3).
  * Gayo-Avello (2012) Gayo-Avello, D. 2012.  No, you cannot predict elections with Twitter.  _IEEE Internet Computing_ , 16(6): 91–94.
  * Goel et al. (2016) Goel, S.; Anderson, A.; Hofman, J.; and Watts, D. J. 2016.  The structural virality of online diffusion.  _Management Science_ , 62(1): 180–196.
  * Hindman and Barash (2018) Hindman, M.; and Barash, V. 2018.  Disinformation, and influence campaigns on twitter.  _Knight Foundation: George Washington University_.
  * Huszár et al. (2022) Huszár, F.; Ktena, S. I.; O’Brien, C.; Belli, L.; Schlaikjer, A.; and Hardt, M. 2022.  Algorithmic amplification of politics on Twitter.  _Proceedings of the National Academy of Sciences_ , 119(1).
  * Jackson (2016) Jackson, S. J. 2016.  (Re) imagining intersectional democracy from Black feminism to hashtag activism.  _Women’s Studies in Communication_ , 39(4): 375–379.
  * Jakesch et al. (2021) Jakesch, M.; Garimella, K.; Eckles, D.; and Naaman, M. 2021.  Trend Alert: How a Cross-Platform Organization Manipulated Twitter Trends in the Indian General Election.  arXiv:2104.13259.
  * Juneja and Mitra (2021) Juneja, P.; and Mitra, T. 2021.  Auditing e-commerce platforms for algorithmically curated vaccine misinformation.  In _Proceedings of the 2021 chi conference on human factors in computing systems_ , 1–27.
  * Knapp (2013) Knapp, A. 2013.  Super bowl tweeting: By the numbers.
  * Koumchatzky and Andryeyev (2017) Koumchatzky, N.; and Andryeyev, A. 2017.  Using deep learning at scale in Twitter’s timelines.  _Twitter Blog_ , 9.
  * Lazer (2020) Lazer, D. 2020.  Studying human attention on the Internet.  _Proceedings of the National Academy of Sciences_ , 117(1): 21–22.
  * Lee and Oppong (2020) Lee, L.; and Oppong, F. 2020.  Adding more context to Trends.  https://blog.twitter.com/en“˙us/topics/product/2020/adding-more-context-to-trends.
  * Liang and Zeger (1986) Liang, K.-Y.; and Zeger, S. L. 1986.  Longitudinal data analysis using generalized linear models.  _Biometrika_ , 73(1): 13–22.
  * Milan (2015) Milan, S. 2015.  Mobilizing in Times of Social Media. From a Politics of Identity to a Politics of Visibility.  SSRN Scholarly Paper ID 2880402, Social Science Research Network, Rochester, NY.
  * Murthy (2015) Murthy, D. 2015.  Twitter and Elections: Are Tweets, Predictive, Reactive, or a Form of Buzz?  _Information, Communication & Society_, 18(7): 816–831.
  * Myers, Zhu, and Leskovec (2012) Myers, S. A.; Zhu, C.; and Leskovec, J. 2012.  Information Diffusion and External Influence in Networks.  In _Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’12, 33–41. New York, NY, USA: Association for Computing Machinery.  ISBN 978-1-4503-1462-6.
  * Proferes and Summers (2019) Proferes, N.; and Summers, E. 2019.  Algorithms and agenda-setting in Wikileaks’# Podestaemails release.  _Information, Communication & Society_, 22(11): 1630–1645.
  * Ribeiro et al. (2020) Ribeiro, M. H.; Ottoni, R.; West, R.; Almeida, V. A.; and Meira Jr, W. 2020.  Auditing radicalization pathways on YouTube.  In _Proceedings of the 2020 conference on fairness, accountability, and transparency_ , 131–141.
  * Riquelme and González-Cantergiani (2016) Riquelme, F.; and González-Cantergiani, P. 2016.  Measuring User Influence on Twitter: A Survey.  _Information Processing & Management_, 52(5): 949–975.
  * Robertson et al. (2018) Robertson, R. E.; Jiang, S.; Joseph, K.; Friedland, L.; Lazer, D.; and Wilson, C. 2018.  Auditing partisan audience bias within google search.  _Proceedings of the ACM on Human-Computer Interaction_ , 2(CSCW): 1–22.
  * Romero, Meeder, and Kleinberg (2011) Romero, D. M.; Meeder, B.; and Kleinberg, J. 2011.  Differences in the Mechanics of Information Diffusion Across Topics: Idioms, Political Hashtags, and Complex Contagion on Twitter.  _Proceedings of the 20th international conference on World wide web_ , 10.
  * Sakaki, Okazaki, and Matsuo (2010) Sakaki, T.; Okazaki, M.; and Matsuo, Y. 2010.  Earthquake shakes twitter users: real-time event detection by social sensors.  In _Proceedings of the 19th international conference on World wide web_.
  * Tufekci (2017) Tufekci, Z. 2017.  _Twitter and tear gas_.  Yale University Press.
  * Twitter (2015) Twitter. 2015.  Twitter Trends FAQs.  https://help.twitter.com/en/using-twitter/twitter-trending-faqs.
  * Twitter (2020) Twitter. 2020.  Trend Takeover and Trend Takeover+.  https://business.twitter.com/en/advertising/takeover/trend-takeovers.html.
  * Zhang et al. (2017) Zhang, Y.; Ruan, X.; Wang, H.; Wang, H.; and He, S. 2017.  Twitter Trends Manipulation: A First Look Inside the Security of Twitter Trending.  _IEEE Transactions on Information Forensics and Security_ , 12(1).


# SWAT: Scalable and Efficient Window Attention-based Transformers
Acceleration on FPGAs

Zhenyu Bai, Pranav Dangi, Huize Li🖂, Tulika Mitra🖂 School of Computing,
National University of Singapore, 119077, Singapore{zhenyu.bai, dangi,
<EMAIL_ADDRESS><EMAIL_ADDRESS>
(2024)

###### Abstract.

Efficiently supporting long context length is crucial for Transformer models.
The quadratic complexity of the self-attention computation plagues traditional
Transformers. Sliding window-based static sparse attention mitigates the
problem by limiting the attention scope of the input tokens, reducing the
theoretical complexity from quadratic to linear. Although the sparsity induced
by window attention is highly structured, it does not align perfectly with the
microarchitecture of the conventional accelerators, leading to suboptimal
implementation. In response, we propose a dataflow-aware FPGA-based
accelerator design, SWAT, that efficiently leverages the sparsity to achieve
scalable performance for long input. The proposed microarchitecture is based
on a design that maximizes data reuse by using a combination of row-wise
dataflow, kernel fusion optimization, and an input-stationary design
considering the distributed memory and computation resources of FPGA.
Consequently, it achieves up to 22$\times$ and 5.7$\times$ improvement in
latency and energy efficiency compared to the baseline FPGA-based accelerator
and 15$\times$ energy efficiency compared to GPU-based solution.

Acknowledgement: this research is partially supported by the National Research
Foundation, Singapore under its Competitive Research Program Award NRF-
CRP23-2019-0003 and AMD Research gift.

The corresponding authors are Huize Li and Tulika Mitra

††journalyear: 2024††copyright: acmcopyright††conference: Proceedings of the
61th ACM/IEEE Design Automation Conference (DAC); June 23–27, 2024; San
Francisco, CA, USA††booktitle: Proceedings of the 61th ACM/IEEE Design
Automation Conference (DAC) (DAC ’24), June 23–27, 2024, San Francisco, CA,
USA††price: 15.00††doi: 10.1145/000000.0000000††isbn: xxxx

##  1\. Introduction

Transformer-based models (Vaswani et al., 2017), known for their self-
attention mechanisms, are leading advancements in artificial intelligence. A
typical transformer model contains linear layers, multi-head attention layers,
and Feed-Forward Networks (FFN). The self-attention process involves first
transforming each input token into the Query (Q), Key (K), and Value (V)
vectors. Then it computes the dot products of Q and K for each token
$S=Q\times K^{T}$, determining the similarity scores $S$ between them. These
scores are then normalized using a softmax function to form probabilities
$S^{\prime}=SoftMax(S)$. Finally, the V vectors are multiplied by these
probabilities and summed up to produce the final output $Z=S’\times V$. This
mechanism allows each token to contextually relate to every other token in the
input, which is crucial for tasks requiring complex contextual understanding.

However, a notable impediment of this model is its quadratic complexity, which
necessitates each sequence element to be compared against every other element.
This complexity becomes particularly intractable in tasks with long contexts,
such as document-level translation or long-form questions, due to the
computational demands (Kim et al., 2023). This issue is illustrated in Figure
1 where the floating point operations (FLOPs) and memory operations (MOPs) for
attention computation grow with increasing input length and become a critical
performance bottleneck.

128256512102420484096819216384$0$$0.2$$0.4$$0.6$$0.8$$1$Input LengthRatioFLOPs
BreakdownLinerAttentionFFN128256512102420484096819216384Input LengthMOPs
Breakdown

Figure 1. Floating point operations (FLOPs) and memory operations (MOPS)
breakdown for different input lengths

(a) Window Attention

(b) sliding chunks implementation

Figure 2. Sliding window attention and its SOTA sliding chunks implementation

To address this, the sliding window attention has been introduced (Beltagy et
al., 2020). This method limits the attention of each token to a fixed subset
of adjacent tokens, thereby reducing the theoretical complexity from quadratic
to linear. From the computational perspective, this method introduces a
structured pattern of sparsity in the attention computation, as shown in
Figure 2(a) where each token attends to $w$ tokens before and after, forming a
diagonal sparsity pattern of width $2w$. This sparsity manifests as a mask
applied to the $S$ and $S^{\prime}$ matrices, resulting in a Sampled Dense-
Dense Matrix Multiplication between $Q$ and $K$, and a Sparse-Dense Matrix
Multiplication between $S^{\prime}$ and $V$. Despite the structured nature of
this sparsity pattern, unlike dense operations, it is not perfectly aligned to
be seamlessly filled into the vector/matrix math lanes of conventional
accelerators. Instead, it requires fine-grain control of the microarchitecture
for optimal performance that is not provided by existing accelerators. For
instance, the Tensor Cores in Nvidia GPUs for accelerating dense matrix
multiplications can only be accessed through higher-level programming models
such as CUDA C++ API or C libraries, limiting micro-architecture level
control. The current state-of-the-art implementation111Hugging Face’s
Longformer implementation, as per the original Longformer paper(Beltagy et
al., 2020)., known as _sliding chunks_ , addresses this limitation by dividing
the sparse operation into smaller dense operations across chunks of width
$2w$, as illustrated in Figure 2(b).

512102420484096819216384$0$$5$$10$$15$Input LengthExecution time (ms) per
attentionDense (GPU—FP32)Sliding Chunks (GPU—FP32)SWAT (FPGA—FP16)SWAT
(FPGA—FP32)512102420484096819216384$0$$500$$1{,}000$Input LengthMemory(MB)
usage per attention

Figure 3. Execution time and memory usage of existing approaches Dense and
Sliding Chunks compared to SWAT

Yet, this approach leads to redundant computations in the form of the
overlapping regions (gray regions in figure 2(b)) and corner areas (dashed
regions in the figure) of each chunk. The ratio of these redundant computation
is given by $\frac{1}{2}-\frac{1}{4|chunks|}$ where $|chunks|$ is the number
of chunks. This ratio increases and approaches rapidly to $\frac{1}{2}$, i.e.,
50% redundancy. Moreover, eliminating these redundant calculations is
challenging as the correctness of the results must be ensured, which further
increases the computational overhead. In Figure 3, We compare the execution
time and memory usage222The experimental setup will be presented in Section 5.
of the sliding chunks with the naïve dense operations approach on an AMD MI210
GPU. The result indicates that while the sliding chunks approach significantly
reduces memory usage, the computational time remains similar to the dense
method, primarily due to the redundant computation but also due to the
overhead for increased frequency of small kernel launches on GPU.

#### Motivation & Contribution:

We aim to refine the implementation of sliding window attention by focusing on
the efficient computation of its structured, yet imperfectly aligned sparsity,
which requires precise control over computation and memory operations. We
propose a novel hardware design using Field-Programmable Gate Arrays (FPGAs).
FPGAs are favored over ASICs because their programmability allows for the
support of various attention mechanisms such as global attention and random
attention, enhancing the model accuracy across different tasks. Additionally,
FPGAs are readily available on cloud platforms, e.g., Microsoft
Azure(Caulfield et al., 2016) and Amazon AWS, offering a cost-effective
deployment solution.

The implementation of the sliding window attention has to consider the
computation workload and how it is mapped onto the distributed memory and
computation resources of the FPGA fabric for optimal performance. Therefore,
we deeply analyze the data flow of the sliding window attention, which reveals
that a combination of window attention, row-major dataflow, and kernel fusion
can significantly enhance off-chip transfer efficiency, ensuring each data
item is loaded just once. We propose employing a fixed-size First-In-First-Out
(FIFO) buffer to manage the sliding window input, leading to an input-
stationary data flow. Here, the input data remains in the buffers after being
loaded while necessary computational resources are placed around them by the
micro-architecture design. This approach better utilizes the on-chip memory
blocks’ bandwidth and minimizes on-chip data movement, aligning well with the
distributed memory and computation units of the underlying FPGA fabric and
therefore achieving higher performance.

As demonstrated in Figure 3, SWAT exhibits linear scaling of memory use with
input length. SWAT achieves 6$\times$ energy efficiency to conventional GPU-
based solutions for comparable execution time for input length below 8K tokens
and shows superior performance for longer input. When compared to a baseline
FPGA accelerator, SWAT achieves 22$\times$ and 5.7$\times$ improvements in
latency and energy efficiency, respectively (with 16384 tokens). Moreover,
SWAT shows better scalability compared to both GPU and FPGA solutions.

##  2\. Background & Related works

###  2.1. Efficient Transformers

Efficient Transformers (Treviso et al., [n. d.]) are the variants of the
vanilla Transformer model, aiming at improving the computational efficiency.
Two main strategies underlie these improvements. The first seeks to
approximate the traditional SoftMax attention mechanisms with algorithms of
lower computational complexity. For instance, FNet (Lee-Thorp et al., 2021)
and Linformer (Wang et al., 2020) substitute the standard attention
calculations with Fourier Transforms and linear projections, respectively. The
second pathway, sparse attention, aims to reduce attention operations while
preserving the SoftMax-based attention formulation.

###  2.2. Sparse attention

Sparse attention can be further classified into two categories. Dynamic
mathods (Lu et al., 2021; Qu et al., 2022; Qin et al., 2023) evaluate or
predict attention scores in real-time, prioritizing the most significant ones
for subsequent computation. These methods, while adaptable, introduce
irregular sparsity patterns that hinder efficient computation. In contrast,
static methods (Beltagy et al., 2020; Zaheer et al., 2020; Dao et al., 2019)
pre-define attention patterns, achieving structured sparsity at the cost of
some accuracy. The structured sparsity can be leveraged for predictable
performance gains with static optimization and dedicated hardware support.

Sliding window attention (Beltagy et al., 2020), is the key component of
nearly all static sparse attention approaches. This technique limits each
token’s attention to a predetermined number of adjacent tokens, based on the
research findings that show the substantial impact of the local context within
the attention mechanism (Parmar et al., 2018; You et al., [n. d.]).

###  2.3. Accelerators for static structured attention

ASIC-based accelerator SALO (Shen et al., 2022), designed explicitly for the
Longformer model, utilizes structured sparsity in window attention with a 2D
square systolic array. However, it is limited to the basic Longformer setup.
Furthermore, the systolic array’s square structure requires square tiling of
the input and the intermediate matrices. This tiling is suboptimal for row-
wise SoftMax operations, necessitating supplementary computations outside the
accelerator’s capabilities.

Butterfly (Fan et al., 2022) is an FPGA-based accelerator for efficient
transformer models that utilizes a static butterfly sparsity pattern. Notably,
this pattern can be approximated through Discrete Fourier Transformations.
However, this FFT-based approximation of the original SoftMax attention has
not consistently demonstrated reliable accuracy across various downstream
tasks. Butterfly attempts to mitigate this by combining vanilla SoftMax
attention layers with FFT-based attention layers. Our analysis in Section 5.2
reveals that incorporating at least one conventional attention mechanism is
crucial for acceptable accuracy. Unfortunately, this traditional attention’s
quadratic complexity leads to suboptimal performance for the accelerator when
managing long input sequences.

(a) Data-reuse

(b) Fixed-length FIFO

Figure 4. Data management for window attention

##  3\. Dataflow Analysis & Optimization

###  3.1. Enabling kernel fusion

The standard implementation of Transformer models involves a sequential three-
step computation- $QK$ multiplication, SoftMax, and $SV$ multiplication-
primarily due to the row-wise data dependency of the SoftMax operation. As on-
chip memory is typically insufficient for handling the entire computation in
one go, each step is broken down into smaller tile-wise operations, leading to
redundant off-chip data transfers for loading and storing the tile-wise
intermediate results (the tiles of $S$ and $S^{\prime}$).

Kernel fusion (Dao et al., 2022), as an optimization technique, aims to
consolidate these steps into a single operation for each input tile, thereby
reducing off-chip data transfers. However, the inherent row-wise dependency in
the SoftMax operation presents a significant challenge to this fusion. By
reinterpreting the SoftMax operation, we can divide it into two components:
the numerator that does not depend on the other elements of the row and the
denominator that depends on the sum of the exponential of all elements of the
same row. By viewing the denominator as a scaling factor, it can be placed
after the third step $Z=S^{\prime}\times V$ as shown in Equation 1. This
restructuring allows for the fusion of the three operations into a unified
row-wise kernel.

(1)
$\begin{split}Z_{i,j}&=\sum_{n=0}^{H}S^{\prime}_{i,n}V_{n,j}=\sum_{n=0}^{H}\frac{exp(S_{i,n})}{\sum_{l=0}^{H}exp(S_{i,l})}V_{n,j}\\\
&=(\frac{1}{\sum_{l=0}^{H}exp(S_{i,l})})(\sum_{n=0}^{H}exp(S_{i,n})V_{n,j})\\\
\end{split}$

###  3.2. Row-major dataflow & Data reuse

In the standard three-step computation of transformers, independent execution
of each step limits the benefits gained from tiling strategies or dataflow
optimization. However, in the context of sliding window attention, these three
computations share a common sparsity pattern, as depicted in Figure 2(a). When
considering the attention computation for a given input row of $Q$, say
$Q_{i}$, and the subsequent row vector $Q_{i+1}$, we observe significant data
reuse of the attended rows of $K$ (columns of $K^{T}$) and $V$, as shown in
Figure 4(a) for the window width $w=1$. The most effective way to harness this
data reuse is by adopting a row-major dataflow. Although kernel fusion
_postpones_ the row-wise dependencies of SoftMax, it does not _eliminate_
them. A row-major approach, therefore, becomes advantageous, minimizing the
memory needed for storing intermediate results $S$ and $S^{\prime}$, which now
can be stored in on-chip memories.

To capitalize on this data reuse opportunity, SWAT employs fixed-size on-chip
FIFO buffers for the $K$ and $V$ inputs, while the $Q$ input changes for each
row. This setup, illustrated in Figure 4(b), features a buffer with a moving
pointer that indicates the next element to be replaced, ensuring data is
loaded exactly once and achieving 100% off-chip memory transfer efficiency.

###  3.3. Input-Stationary dataflow for FPGA

The previous sections discussed SWAT’s dataflow at the algorithmic level. Now,
it’s important to consider how this dataflow is mapped onto the FPGA’s
microarchitectural design. The following key aspects are considered. First,
FPGAs have distributed memory (BRAMs and URAMs) and computing elements (LUTs,
DSP slices) across the chip. Secondly, by utilizing fixed-size FIFO buffers
for input data, as exhibited in Figure 4(b), input data mostly remains
stationary. Finally, kernel fusion ensures a consistent pairing of
$(K_{j},V_{j})$ for each Key/Value row $j\in[i-w,i+w]$. This coherency is
apparent both in the fusion equation (see Equation 1) and the FIFO eviction
process (Figure 4(b)). From the algorithm level, this is because the same
input sequence indexes $Key$ and $Value$ matrices according to the self-
attention mechanism.

Figure 5. input-stationary dataflow

Consequently, we adopt an _input-stationary_ dataflow. In this design, input
data remain in their respective buffers, and computational units are
positioned nearby. This is different from conventional accelerator designs,
where the data is brought to the computational units. Figure 5 illustrates
this dataflow for one row of input $Q$ within the input stationary paradigm.
An _Attention Core_ —our terminology for the minimal computational
unit—consists of a buffer holding one row of $K$ ($K_{j}$), and one row of $V$
($V_{j}$). Upon the arrival of a new row of $Q$, denoted as $Q_{i}$, the
multiplication with $K_{j}$ is performed locally within each Attention Core:
$S_{i,j}=Q_{i}\cdot K_{j}$. Subsequently, the numerator of the SoftMax
computation is performed: $S^{\prime}_{i,j}=exp(S_{i,j})$ according to the
kernel fusion. For the multiplication of $S^{\prime}$ with $V$, we adhere to
the input-stationary paradigm, where each $S^{\prime}$ element multiplies with
the corresponding $V$ row stored in the same attention core. This operation
yields one slice of $Z$ per attention core. The slices produced by all
attention cores are summed up outside of the attention cores to form the final
result $Z$.

###  3.4. Dataflow compatibility for ASIC

The dataflow optimization techniques we have developed, particularly row-major
dataflow and kernel fusion, are also applicable to ASIC-based implementations,
which, unlike FPGAs, are not constrained by the distribution of computation
and memory resources. While ASICs can potentially offer superior performance,
they lack the flexibility of FPGAs, which is crucial for adapting to the
evolving landscape of Transformer models.

Figure 6. SWAT Microarchitecture design

##  4\. Architecture design

Figure 6 shows the architecture design of SWAT by following the dataflow
design outlined in the previous section. The architecture makes use of a
pipeline execution to improve resource usage efficiency. The functions of the
pipeline stages are as follows:

_LOAD Stage_ : Data from the main memory is fetched and loaded into the $K/V$
buffers of the attention cores. For the standard window width configuration
($2w=512$), 512 attention cores are instantiated. Each $K/V$ buffer uses one
BRAM block, storing a full row of $K$ or $V$ of size $H$(head dimensionality).
According to the $K/V$ buffer replacement policy, the entire $K/V$ buffer of
one attention core is refreshed per attention of one row. The selection signal
is computed by the row index $i$ modulo the window size according to the FIFO
policy. The $Q$ row is loaded during this stage and distributed across all
attention cores.

_QK Stage_ : This stage calculates the dot product between the $K$ row and the
$Q$ row in the attention cores. Due to FPGA constraints, the FP16 multiply-
accumulate (MAC) operation is pipelined at an Initial Interval (II) of 3
cycles. Forcing the MAC to be pipelined at fewer cycles will significantly
increase resource usage.

_SV Stage_ : Following the QK stage, the SV stage computes the exponential of
the $S$ values and multiplies these with the corresponding $V$ elements within
the same attention core, generating a slice of $Z$ per attention core, stored
in $ZBuf$. The FP16 multiplications are executed over an II=3 pipeline. While
a lower II is feasible, it does not improve overall performance due to the
II=3 of QK stage and would lead to increased resource usage for pipelining.

_Z Reduction_ : This two-phase stage sums the individual $Z$ slices from each
attention core to form the complete output $Z$ vector. For a standard
configuration of $H=64$, parallel accumulation over $H$ channels (because $Z$
has $H$ elements) would result in a stage duration of approximately $3\times
2w$ which is 8x that of QK and SV stages of $3\times H$ cycles. To maintain
pipeline balance, the reduction is split into two substages, ZRED1 and ZRED2.
In ZRED1, $Z$ slices are grouped by each $H$ of them and processed with $H$
accumulation channels per group, which results in approximately an overall
latency of $3\times H$ cycles. ZRED2 then combines the outputs from ZRED1 into
the final $Z$ vector.

_Row sum_ : Operating in parallel to Z reduction, the Row Sum stage computes
the sum of $S^{\prime}$ values from the attention cores. With $2w$ elements of
$S^{\prime}$, this stage employs a similar two-stage approach as Z reduction
for timing balance, comprising ROWSUM1 and ROWSUM2.

_Division and Output_ : The final stage divides each $Z$ element by the
corresponding sum of the $S^{\prime}$ row, as per the post-fusion algorithm.
The division is pipelined at a 2-cycle interval because better throughput is
unnecessary. The output vector is then written back to HBM or DRAM.

Table 1 presents the timing for each pipeline stage based on the Xilinx Vitis
HLS synthesis tool report. The design uses half-precision 16-bit floating-
point data, with default settings of head dimension $H=64$ and window width
$2w=512$. The overall pipeline is well balanced and timed at 201 cycles,
predominantly due to the longer stage, $QK$.

Table 1. The timing (in cycles) of the pipeline stages

|  |  | ZRED1 | ZRED2 |
---|---|---|---|---|---
LOAD | QK | SV | 195 | 66 | DIV&OUT
66 | 201 | 197 | ROWSUM1 | ROWSUM2 | 179
|  |  | 195 | 27 |

###  4.1. Parameterized design

SWAT’s architecture integrates basic window attention with additional
attention mechanisms to improve accuracy across various tasks. One such
mechanism is _global attention_ , which designates important global tokens to
be attended by all input tokens. Models like Longformer (Beltagy et al., 2020)
and ViL (Zhang et al., [n. d.]) have demonstrated the effectiveness of global
attention in enhancing accuracy for text classification and vision tasks,
respectively. Another mechanism, _random attention_ , introduced by the
BigBird model (Zaheer et al., 2020), generally improves model accuracy by
incorporating randomly (but statically) selected additional tokens for each
input token to attend to.

Figure 7. Parameterized Design of SWAT

As illustrated in Figure 7, SWAT supports these mechanisms through design-time
parameters: the indices of the random and global attention tokens, as well as
the width of the sliding window, are set as synthesis parameters. SWAT’s
architectural design can adapt to these additional attention patterns with
minimal changes. Specific subsets of attention cores are allocated for
computing global and random attention with respect to the parameters.
Attention cores dedicated to global attention have fixed K and V buffers,
aligning with the consistent nature of global tokens. These buffers are pre-
loaded prior to the attention computation, minimizing performance impact. In
contrast, attention cores handling random attention update their K and V
buffers dynamically, which increases the latency of the LOAD stage to 195
cycles from the initial 66. However, thanks to the pipelined design of our
system, this increase in latency does not hamper overall execution speed.

###  4.2. FPGA resources utilization

Table 2 provides a detailed account of resource usage on the Alveo U55C FPGA
post-synthesis. We present four configurations: the standard Longformer setup
of pure window attention with FP16 datatype and 512 attention cores; the
BigBird configuration of 192 sliding window tokens, 192 random attention
tokens, 128 global tokens, i.e. total 512 tokens per row with FP16; the same
BigBird configuration but with dual pipelines for parallel processing two
heads (which also demonstrates the potential of handling 1024 tokens per row
in different attention configurations); and an FP32 version for later
comparative analysis with GPUs.

Table 2. Resources usage on U55C/VCU128

Design | DSP | LUT | FF | BRAM
---|---|---|---|---
FP16 (512 attn) | 19% | 38 % | 11% | 25%
FP16 (BigBird 512 attn) | 19% | 33 % | 11 % | 25%
FP16 (BigBird 2 x 512 attn) | 38% | 66 % | 22 % | 50%
FP32 (512 attn) | 49% | 67% | 23% | 25%
Butterfly (FP16, 120-BE) | 32% | 79% | 63% | 49%

##  5\. Evaluation

###  5.1. Butterfly accelerator baseline

The Butterfly Accelerator(Fan et al., 2022) is the only FPGA-based accelerator
for static sparse attention–the butterfly sparsity(Dao et al., 2019)– and
serves as our baseline. It incorporates two key hardware components: the FFT-
BTF (Fast Fourier Transform-Butterfly) engine for approximating the standard
SoftMax attention using Fourier transform; and the ATTN-BTF (Attention-
Butterfly) engine that behaves just as the standard SoftMax attention. The
FFT-BTF offers increased speed at the expense of some accuracy, whereas the
ATTN-BTF ensures accuracy with slower operation. The hybrid use of FFT and
SoftMax layers in Butterfly’s software model is tuned for specific datasets to
achieve a balance between speed and accuracy through design space exploration.
However, the performance study of the Butterfly Accelerator in (Fan et al.,
2022) focuses only on the full-FFT version.

###  5.2. Accuracy comparison with Butterfly

To draw a fair comparison with SWAT, we delve into the accuracy-performance
tradeoff in Butterfly’s adaptable design. We evaluated model accuracies using
the Long-Range Arena (LRA) benchmark datasets (Tay et al., [n. d.]), which are
tailored for efficient transformer models. Table 3 shows the accuracy
advantage of SWAT implementations over the purely FFT-layered Butterfly model,
particularly in vision tasks. Additionally, we observe an accuracy improvement
in the Butterfly model when replacing one or two last FFT layers with
traditional SoftMax attention layers (respectively noted as configuration
BTF-1 and BTF-2), underscoring the accuracy benefit of incorporating even a
single layer of traditional SoftMax attention. However, Longformer and Bigbird
still show better average accuracy compared to BTF-1 and BTF2, especially in
vision tasks. For the accuracy consideration, we will use BTF-1 and BTF-2 in
the performance analysis in the next section.

Table 3. Accuracy gain of window attention-based models (Longformer and
BigBird supported by SWAT) and baseline Butterfly models with one or two
layers (BTF-1, BTF-2) replaced by the vanilla SoftMax attention on LRA
datasets compared to Butterfly’s full-FFT attention

| Vision based | Text based |
---|---|---|---
Model | Image | PathFinder | Text | ListOps | AVG.
Longformer | +15.26% | +3.03% | +0.17% | +1.61% | +5.02%
Bigbird | +13.87% | +8.16% | +1.34% | +2.03% | +6.35%
BTF-1 | +6.26% | +2.85% | +0.01% | +2.4% | +3.01%
BTF-2 | +8.95% | +2.14% | +1.05% | +2.42% | +3.64%

Figure 8. Top-1 accuracy of PixelFly (butterfly model) against ViL (supported
by SWAT) on ImageNet-1K (Deng et al., 2009)

Model | Params | Top-1
---|---|---
ViL-Tiny | 6.7M | 76.7%
Pixelfly-M-S | 5.9M | 72.6%
ViL-Small | 24.6M | 82.4%
Pixelfly-V-S | 16.9M | 77.5%
Pixelfly-M-B | 17.4M | 76.3%
Pixelfly-V-B | 28.2M | 78.6%
ViL-Med | 39.7M | 83.5%

1024204840968192163845x10x15x20x25x30x35x40x45xInput LengthNormalized
SpeedupSWAT vs. BTF-1SWAT vs. BTF-2

Figure 9. Speedup (times) of SWAT over Butterfly versions

In addition to the Butterfly model comparison, we explored the effectiveness
of the sliding window attention versus FFT-based approximations in vision-
specific tasks. Our analysis, detailed in Table 9, compares the accuracy of
the state-of-the-art ViL (Vision Longformer) model (Zhang et al., [n. d.]),
which is supported by SWAT, against the SOTA FFT-attention-based Pixelfly
model (Dao et al., 2021). This comparison is particularly insightful as both
models operate with a similar number of parameters. The results highlight that
the ViL model achieves superior accuracy on the ImageNet-1K dataset,
underscoring the effectiveness of sliding window attention in vision
applications.

###  5.3. Performance comparison with Butterfly

Both SWAT and Butterfly accelerators were synthesized on FPGAs of the same
characteristics333U55C (SWAT) and VCU128 (Butterfly) have the same number of
logical resources. They are also using a similar number of FPGA resources in
FP16 precision, as shown in Table 2. Using the cycle-accurate simulator
provided by Butterfly, we independently evaluated the performance of the FFT-
BTF engine and ATTN-BTF engine. As the original performance evaluation of
Butterfly only considered the full-FFT configuration, we project its
performance by computing the optimal ratio of resource distribution for FFT-
BTF and ATTN-BTF engines at different input lengths.

SWAT’s latency is based on its pipeline latency as stated earlier in Table 1.
For FPGA implementations, both accelerators produce consistent operation
latencies regardless of the concrete values of input data, number of heads,
layers, and batches. Total attention time is proportional to the execution
time of a single head, which has an arbitrarily chosen dimensionality of 64.
Figure 9 shows the speedup of SWAT in Longformer or Bigbird configuration
against the Butterfly accelerator in BTF-1 (1 softmax layer) and BTF-2 (2
softmax layers) configurations across various sequence lengths, from 1024 to
16384 tokens. Due to the poor scalability of the vanilla SoftMax attention,
the Butterfly accelerator exhibits declining performance with long input
sequences. At the standard Longformer configuration of 4096 input tokens (the
accuracies in Table 3 are obtained at this configuration), SWAT performs
6.7$\times$ and 12.2$\times$ better respectively over BTF-1 and BTF-2. Due to
the faster computation of SWAT, it also outperforms Butterfly from the energy
perspective. We evaluate the power consumption of SWAT using the Xilinx Power
Estimator. Figure 10 shows the energy efficiency (energy consumption per
attention) of SWAT against BTF-1 and BTF-2. SWAT shows an increasing energy
efficiency advantage along the input length, attaining 11.4$\times$ and
21.9$\times$ over BTF-1 and BTF-2 at 16384 context length, respectively.

10242048409681921638450x40x30x20x10x0xInput LengthEnergy EfficiencySWAT FP16
vs. BTF-1 FP16SWAT FP16 vs. BTF-2 FP16SWAT FP16 vs. GPU denseSWAT FP16 vs. GPU
sliding-chunksSWAT FP32 vs. GPU sliding-chunksSWAT FP32 vs. GPU dense

Figure 10. Energy Efficiency of SWAT against SOTA GPU and FPGA implementations

###  5.4. Comparison with GPU

We benchmarked SWAT against GPU implementations with the same Transformer
model, using AMD’s rocBLAS and MIOpen libraries for tensor multiplication and
SoftMax operation in the sliding chunks and the naïve dense approach which
have been discussed in Section 1. We measured the execution time while
excluding the overhead due to the first kernel launch and averaged the latency
over 100 attention computations for consistency. To compare fairly with GPU
implementation, we synthesized an FP32 version of SWAT, which exhibits a
higher pipeline latency of 264 cycles due to the FPGA’s limitation on the FP32
MAC operation. The execution time comparison has been shown previously in
Figure 3. At short input length, SWAT demonstrates better latency, which can
be partly ascribed to the underutilization of the GPU in our single-batch
experimental setup. However, as the input length reaches 4k, the GPU’s
execution time begins to rise sharply, indicating its full utilization. In
contrast, SWAT exhibits a linearly increasing execution time in relation to
input length, with similar performance of GPU between 4k and 8k input length
but much better scalability for longer input length.

A key aspect of SWAT is its energy efficiency, which is notably remarkable
when compared to MI210, which has a power consumption of 300 watts. This
efficiency is highlighted in Figure 10, where SWAT’s energy efficiency is
compared against MI210 in both FP32 and FP16 precision. In FP32 precision,
particularly considering the under-utilization of the GPU at shorter input
lengths, SWAT achieves an impressive 20$\times$ energy efficiency advantage at
an input length of 1k. However, as the GPU becomes better utilized with longer
input sequences, SWAT’s relative energy efficiency advantage decreases,
reaching a minimum of 4.2$\times$ at an input length of 8k. SWAT’s
scalability, however, becomes increasingly pronounced with longer context
lengths, and hence SWAT’s superior energy efficiency grows, reaching up to
approximately 8.4$\times$ that of GPU-based implementations at 16k input
length.

##  6\. Conclusion

We introduced SWAT, an FPGA-based accelerator specifically designed for window
attention-based transformer models. Our approach is rooted in a comprehensive
analysis of window attention workloads, leading to an input-stationary
dataflow. This dataflow combines the advantages of FPGA’s inherent distributed
memory-and-computation architecture with a row-major dataflow and kernel
fusion optimization. This unique combination effectively leverages the
diagonal-structured sparsity inherent in sliding window attention, resulting
in significantly improved performance. For long context lengths, SWAT stands
out by delivering superior performance and energy efficiency over both the
current SOTA FPGA-based static sparse attention accelerator and server-class
GPUs.

## References

  * (1)
  * Beltagy et al. (2020) Iz Beltagy et al. 2020\.  Longformer: The long-document transformer.  _arXiv preprint arXiv:2004.05150_.
  * Caulfield et al. (2016) Adrian M Caulfield et al. 2016\.  A cloud-scale acceleration architecture. In _MICRO-49_. IEEE, 1–13.
  * Dao et al. (2019) Tri Dao et al. 2019\.  Learning fast algorithms for linear transforms using butterfly factorizations. In _ICML_. 1517–1527.
  * Dao et al. (2021) Tri Dao et al. 2021\.  Pixelated butterfly: Simple and efficient sparse training for neural network models.  _arXiv_.
  * Dao et al. (2022) Tri Dao et al. 2022\.  Flashattention: Fast and memory-efficient exact attention with io-awareness.  _NeurIPS-35_.
  * Deng et al. (2009) Jia Deng et al. 2009\.  Imagenet: A large-scale hierarchical image database. In _2009 IEEE conference on computer vision and pattern recognition_. Ieee, 248–255.
  * Fan et al. (2022) Hongxiang Fan et al. 2022\.  Adaptable Butterfly Accelerator for Attention-based NNs via Hardware and Algorithm Co-design. In _MICRO-55_. IEEE, 599–615.
  * Kim et al. (2023) Sehoon Kim et al. 2023\.  Full Stack Optimization of Transformer Inference. In _Architecture and System Support for Transformer Models (ASSYST@ ISCA 2023)_.
  * Lee-Thorp et al. (2021) James Lee-Thorp et al. 2021\.  Fnet: Mixing tokens with fourier transforms.  _arXiv preprint arXiv:2105.03824_.
  * Lu et al. (2021) Liqiang Lu et al. 2021\.  Sanger: A co-design framework for enabling sparse attention using reconfigurable architecture. In _MICRO-54_.
  * Parmar et al. (2018) Niki Parmar et al. 2018\.  Image transformer. In _International conference on machine learning_. PMLR, 4055–4064.
  * Qin et al. (2023) Yubin Qin et al. 2023\.  FACT: FFN-Attention Co-optimized Transformer Architecture with Eager Correlation Prediction. In _ISCA-50_. 1–14.
  * Qu et al. (2022) Zheng Qu et al. 2022\.  Dota: detect and omit weak attentions for scalable transformer acceleration. In _ASPLOS-27_. 14–26.
  * Shen et al. (2022) Guan Shen et al. 2022\.  SALO: an efficient spatial accelerator enabling hybrid sparse attention mechanisms for long sequences. In _DAC-59_. 571–576.
  * Tay et al. ([n. d.]) Yi Tay et al. [n. d.].  Long range arena: A benchmark for efficient transformers.  _arXiv preprint arXiv:2011.04006_.
  * Treviso et al. ([n. d.]) Marcos Treviso et al. [n. d.].  Efficient methods for natural language processing: A survey.  _TACL_ 11, 826–860.
  * Vaswani et al. (2017) Ashish Vaswani et al. 2017\.  Attention is all you need.  _NeurIPS_ 30\.
  * Wang et al. (2020) Sinong Wang, , et al. 2020\.  Linformer: Self-attention with linear complexity.  _arXiv preprint arXiv:2006.04768_.
  * You et al. ([n. d.]) Haoran You et al. [n. d.].  Vitcod: Vision transformer acceleration via dedicated algorithm and accelerator co-design. In _HPCA 2023_. 273–286.
  * Zaheer et al. (2020) Manzil Zaheer et al. 2020\.  Big bird: Transformers for longer sequences.  _Advances in neural information processing systems_ 33, 17283–17297.
  * Zhang et al. ([n. d.]) Pengchuan Zhang et al. [n. d.].  Multi-scale vision longformer: A new vision transformer for high-resolution image encoding. In _ICCV 2021_. 2998–3008.