# Beam Search: Faster and Monotonic

Sofia Lemons,1, 2 Carlos Linares López,3 Robert C. Holte,4 Wheeler Ruml1

###### Abstract

Beam search is a popular satisficing approach to heuristic search problems
that allows one to trade increased computation time for lower solution cost by
increasing the beam width parameter. We make two contributions to the study of
beam search. First, we show how to make beam search monotonic; that is, we
provide a new variant that guarantees nonincreasing solution cost as the beam
width is increased. This makes setting the beam parameter much easier. Second,
we show how using distance-to-go estimates can allow beam search to find
better solutions more quickly in domains with non-uniform costs. Together,
these results improve the practical effectiveness of beam search.

## Introduction

Heuristic state-space search is a fundamental problem-solving methodology. The
search frontier of open nodes in a best-first search such as A* or weighted A*
can, and typically does, grow very large. This limits the scalability of best-
first search for solving large or difficult problems. Beam search (Bisiani
1987) can be seen as one way to adapt best-first search to large problems.

Beam search takes as parameters the start state and beam width and searches
the state space level by level, as in breadth-first search. If more nodes are
generated for the next level than allowed by the beam width, only those with
the lowest f-values are retained. (We assume throughout this paper that the
heuristics being used are admissible, but not necessarily consistent.) Ties
are broken in preference of nodes with lower h-values. The algorithm stops
after completing the level at which a solution is found, returning the lowest
cost solution from that level if there are multiple.

Figure 1: Solution cost as beam width varies.

Despite its apparent simplicity, the behavior of beam search is not well-
understood and can be surprising. For example, increasing the beam width does
not always result in finding better solutions. Figure 1 demonstrates this non-
monotonic behavior of beam search on an instance of the 15-puzzle. As the beam
width is increased, the general trend is for solution cost to decrease, but
this does not necessarily hold for specific beam widths. To gauge this
phenomenon quantitatively, we will call a beam width $k>1$ ill-behaved if the
cost of the solution that beam search returns when run with width $k$ is
higher than the cost of the solution found when using $k-1$. When looking at
all widths from 30 through 1000 on Korf (1985)’s 100 15-puzzle instances, a
full 30% of the beam widths are ill-behaved on average (varying from 5% to 44%
depending on the instance, with a median of 31%). If one considers the three
outcomes to be higher, lower, or staying the same, this is almost random
chance. A practitioner trying to solve a problem needs to know whether to
increase or decrease the specific beam width that they are using if they wish
to decrease solution cost, so this behavior of beam search can be very
annoying. In this paper, we introduce an algorithm, monobeam, that provably
eliminates this annoying behavior. Its performance is also shown in Figure 1.
We show how this can be done even in combination with duplicate elimination.

In Figure 1, we also see that there is not necessarily a large price paid, in
terms of solution cost, to obtain the guarantee of monotonicity. Indeed, there
are many beam widths in this plot for which monobeam’s solution is cheaper
than beam’s. The experiments in this paper are largely aimed at investigating
this question of what price is paid for monotonic behavior. We demonstrate an
approach that can select nodes for the beam in a way that preserves
monotonicity, without incurring additional overhead in the selection process.

Furthermore, in addition to its nonmonotonicity, beam search demonstrates
undesirable behavior in our non-unit-cost problem domains, often finding very
poor solutions or no solutions at all. We explore the use of distance-to-go
estimates with both regular and monotonic beam search, finding that they
ameliorate the poor behavior of beam search in non-unit-cost domains. We
discover, in multiple domains, the surprising result that using the distance-
to-go measurement not only improves search time but often reduces solution
cost as well.

By providing beam search variants that are monotonic and effective with non-
unit costs, this work makes beam search easier to apply in practice.

## Previous Work

Beam search is a popular heuristic search method and has been widely used in
several fields, including natural language processing (Cohen and Beck 2019;
Meister et al. 2021) and operations research (Valente and Alves 2008). Wilt,
Thayer, and Ruml (2010; 2011) provide empirical comparisons of various flavors
of beam search, finding that the breadth-first-based variant that we use here
is preferred.

The most popular research direction regarding beam search has probably been
completeness. Zhang (1998) proposes a complete anytime beam search based on
iteratively weakening pruning rules that exclude nodes from the beam. Zhou and
Hansen (2005) make beam search complete by integrating systematic
backtracking. Furcy and Koenig (2005) use limited discrepancy search instead
of chronological backtracking. Our concerns in the current paper are
orthogonal to completeness: we aim to make beam search itself more effective
and any of those completeness methods could be layered on top.

Some research has investigated finding a suitable beam width, observing that
larger beam widths might incur larger computational costs while they are more
likely to avoid errors in node selection (Ow and Morton 1988; Wijs and Dashti
2012). Monotonicity makes it easier to select the right beam width, because a
user can pick a beam width as large as their system is able to accommodate,
without worrying about whether that width will cause it to perform worse than
it would have at lower widths.

Nonmonotonicity of beam search has been recognized before. For example, Cohen
and Beck (2019) (see also citations therein) aim to explain the degradation in
the performance of beam search with larger beam widths, but from the
perspective of heuristic search. Vadlamudi, Aine, and Chakrabarti (2013)
propose an algorithm, Incremental Beam Search, which when given a maximum
width and a maximum depth, iteratively performs beams searches of increasing
width. The notable feature of their method is that it avoids repeated work by
storing the previous beam search so that the next increment of width can be
performed quickly. The algorithm is anytime, in that solutions found by
earlier widths are available as the search widens to the pre-specified maximum
width. However, it stops at that maximum width and does not converge to
optimal solutions. In addition to the beam width, the maximum search depth
must be specified for the method in advance, making it difficult to use in
practice as reasonable bounds are often unknown before a problem is solved.
Furthermore, the algorithm is only monotonic across the beam widths within a
single execution, not when rerun with a larger maximum beam width. Preliminary
experiments on unit 15-puzzle instances showed that providing anything other
than a rather tight depth bound led to uncompetitive runtimes. For these
reasons, we do not consider this algorithm further.

## Monotonic Beam Search

ABh=1Dh=2Gh=1*Ch=2Eh=1Hh=1Jh=1Fh=1Ih=1Kh=1g=1g=2g=3g=4 Figure 2: A search
space in which non-monotonicity occurs when the beam width is increased from 1
to 2.

One possible cause of beam search’s non-monotonic behavior is that, when
increasing the width of the beam, there is a risk that the nodes expanded at
one of the later positions in the beam may dominate the priority queue used to
select nodes for the next beam and displace nodes that would have been
selected with a smaller beam width. The children of nodes generated at the
larger beam width may have incorrectly low cost-to-go estimates due to
heuristic error. We refer to these as cuckoo nodes because they cause truly
better nodes to be pushed off the beam, just as, when a cuckoo bird lays its
eggs in another bird’s nest, the cuckoo chicks push the other bird’s eggs out
of the nest. The displaced nodes may look less promising now but may be the
ones which led the narrower beam width search to a better solution than will
be found via the cuckoo nodes. In general, this can cause beam search, with a
larger beam width, to do more work to find a goal, to find a solution of
poorer quality or even to fail to find a solution when a solution is found
with a smaller beam width.

An example is given in Figure 2, where a beam search with width 2 returns a
solution of lower quality than a beam search with width 1. The node indicated
by * is a solution. With width 1, beam search chooses node B at level 1 and
proceeds via node D to find the solution beneath node G. With width 2, nodes B
and C are chosen at level 1, but at level 2 node D is displaced by C’s two
children and it is no longer possible to reach a solution as cheap as that
found beneath node D.

#### Monotonicity

1 begin

2 solutionCost $\leftarrow\infty$;

3 beam[1] $\leftarrow$ start;

4 while  _at least one slot in the beam has a node with f-value $<$
solutionCost _ do

5 candidates $\leftarrow\emptyset$, nextBeam $\leftarrow[]$;

6 for  _each beam slot c from 1 to width_ do

7 if  _beam[c] is a node_ then

8 for  _each child of beam[c]_ do

9 if  _f(child) $<$ f(beam[c]) _ then

10 f(child) $\leftarrow$ f(beam[c]);

11

12 if  _child is a goal and f(child) $<$ solutionCost _ then

13 store as solution;

14 solutionCost $\leftarrow$ f(child);

15

16 else

17 add child to candidates;

18

19 if  _candidates is nonempty_ then

20 nextBeam[c] $\leftarrow$ remove $\min f$-value node from candidates;

21

22 beam $\leftarrow$ nextBeam;

23

24 return solution;

25

Algorithm 1 monobeam(start,width)

In order to avoid cuckoo nodes as the beam is widened, we consider each
specific position in the beam, or slot, sequentially. Pseudocode for our
method, monobeam, is shown in Algorithm 1. It maintains a priority queue,
_candidates_ , containing (line 1) only children of nodes at the current beam
slot and slots before it. For each slot on the beam, it expands the current
node in that slot (line 1) and adds to _candidates_ the non-goal children
(lines 1–1). It then pops the minimum $f$-valued node from _candidates_ and
stores it in the current slot of nextBeam (line 1). Ties among minimum
$f$-valued nodes are broken on low $h$-values. This means that the selection
of the node for a slot is not affected by any later slots.

A second possible cause of beam’s non-monotonic behavior is its stopping
condition. It stops at the shallowest level where it finds a solution, even if
that beam contains nodes with $f$-values smaller than the solution’s cost. A
smaller beam width might have found a better solution deeper in the search
beneath one of the nodes with the smaller $f$-values. To preserve
monotonicity, monobeam continues the search until no nodes are left on the
beam with f-values lower than the current incumbent solution, recording any
lower cost solutions found. To ensure we are always getting closer to this
stopping condition, pathmax (Mérõ 1984) is used to ensure $f$-values along a
path are non-decreasing (lines 1–1.) We also assume that the domain does not
contain infinite sequences of zero-cost operators.

Note that Algorithm 1 does not detect duplicates and retains nodes on the beam
whose f-values are worse than the incumbent solution. We will address those
issues below, but first we will prove some properties of Algorithm 1.

######  Lemma 1.

Given the beam at the start of any iteration of the while loop at line 1 of
Algorithm 1, at the end of the $c$-loop at line 1 the node in nextBeam[c] for
all $c$ will be the same for all $\mathit{width}\geq c$.

###### Proof.

By induction on $c$. When $c=1$ this is trivially true because only the
children of the node in slot 1 of beam have been added to candidates at line 1
when a node for nextBeam[1] is selected at line 1. We will always select the
minimum value child of the node in beam[1] to fill nextBeam[1] regardless of
beam width and the node selected for nextBeam[1] will be removed from
candidates.

For any slot $c>1$, the inductive hypothesis asserts that the same nodes were
selected to fill nextBeam slots 1 through $c-1$ regardless of beam width. We
will now show this implies the same node will be selected for nextBeam slot
$c$ regardless of beam width. At the time this selection is made (line 1),
candidates contains the non-goal children of all the beam nodes in slots 1 to
$c$ except those selected for nextBeam’s slots 1 to $c-1$. The minimum value
node from this set will be selected to fill nextBeam slot $c$. The nodes in
candidates are therefore independent of the beam width, and therefore so is
the node selected for nextBeam slot $c$. ∎

######  Lemma 2.

Let $w_{a}<w_{b}$ be beam widths, $d_{i}$ the depth at which monobeam with
width $w_{i}$ terminates, and $beam_{i,d}$ the beam when the stopping
condition is tested at the beginning of the while loop for iteration $d$ when
width $w_{i}$ is being used. Then for all depths
$1\dots\min\\{d_{a},d_{b}\\}$, $beam_{a,d}[j]=beam_{b,d}[j]$ for all $1\leq
j\leq w_{a}$.

###### Proof.

By induction on $d$. When $d=1$, $beam_{a,1}=beam_{b,1}$; both searches insert
start in slot 1 and leave empty slots everywhere else. For any depth $d>1$,
the inductive hypothesis asserts that $beam_{a,d-1}[j]=beam_{b,d-1}[j]$ for
all $1\leq j\leq w_{a}$. Applying Lemma 1, we get that, at the end of
iteration $d-1$, $nextBeam[j]$ is independent of the beam width for all $1\leq
j\leq w_{a}$. The lemma follows because $beam[i,d]$ is $nextBeam$ at the end
of iteration $d-1$. ∎

######  Theorem 1.

Algorithm 1 with an admissible heuristic and beam width $k+1$ will always
return a solution with cost lower than or equal to the cost of the solution it
would have returned if it had been run with beam width $k$, for all $k\geq 1$.

###### Proof.

There are three cases to consider. First, a solution may be found in slot
$k+1$ with cost lower than the solution found by a search with beam width $k$.
This solution will be kept as an incumbent until all nodes on the beam have
f-values greater than or equal to its cost (line 1), at which time it will be
returned. Because it has a lower cost than the solution found by a search with
beam width $k$, the theorem holds.

Second, if no solution is found in slot $k+1$, we know from Lemma 2 that the
nodes selected for slots 1 through $k$ will be unaffected by the increased
beam width. Thus, the solution found by a width $k$ search will be found in
these slots and returned.

Third, if a solution is found at beam slot $k+1$ with cost greater than the
solution that would have been found by a search with width $k$, we know from
Lemma 2 that we will still select in slots $1$ through $k$ all nodes which
would be selected by a search of width $k$. We will find the lower-cost
solution which would have been found by a search with width $k$ and we will
return that solution. ∎

### Pruning based on incumbent solutions

1 begin

2 for  _each beam slot c from 1 to width_ do

3 if  _f(nextBeam[c]) $\geq$ solutionCost _ then

4 nextBeam[c] $\leftarrow$ empty;

5

Algorithm 2 Pruning based on incumbent solution, to be added before line 1 of
Algorithm 1.

######  Lemma 3.

Algorithms 1 and 2 with an admissible heuristic will not remove any node that
is along a path to a solution with cost lower than the incumbent’s.

###### Proof.

Algorithm 2 excludes nodes from the beam with $f$-values $\geq$ the current
incumbent solution cost. Because the heuristic is admissible, such nodes
cannot lead to a solution better than the current incumbent. ∎

Pruning can reduce the number of expansions required, as well as the size of
candidates throughout the search. It might mean that we do not explore exactly
the same set of nodes when the beam width expands, because we might find an
incumbent solution at a larger beam width and prune away nodes from lower beam
slots. However, monotonicity can still be maintained.

######  Lemma 4.

Algorithms 1 and 2 with an admissible heuristic will select for nextBeam at
each level exactly those nodes that would have been selected by Algorithm 1
alone, except possibly omitting some nodes which have f-values $\geq$ the
incumbent’s.

###### Proof.

First, note that pruning does not directly introduce any new nodes into the
beam. Second, consider the consequences of pruning a node $n$ (because its
$f$-value is not better than the incumbent solution’s). We know by Lemma 3
that it could not have led to a better solution than the current incumbent.
Its children must (by lines 1 and 1 of Algorithm 1) have $f$-values no better
than the incumbent solution. If those children would have been selected to
fill any given slot in nextBeam without pruning, then candidates at that time
did not contain any nodes with $f$-values better than the incumbent, so that
slot will remain empty when pruning. So pruning does not introduce nodes or
cause nodes to be selected for different slots than they would have been
otherwise. We will select for each slot on nextBeam exactly those nodes
selected by Algorithm 1 that have $f$-values less than the incumbent’s. ∎

######  Theorem 2.

Algorithms 1 and 2 with an admissible heuristic and beam width $k+1$ will
always return a solution with cost $\leq$ to the cost of the best solution
found by the same algorithm with beam width $k$, for all $k\geq 1$.

###### Proof.

There are three cases. First, if no solution is found at slot $k+1$, then all
search in slots $1$ through $k$ will proceed identically to a search of width
$k$, and the same solution will be returned as would be found by a search of
width $k$. Second, if a solution is found at slot $k+1$ with cost less than
the solution that would be found by a search with width $k$, we will
eventually explore all nodes with f-values less than the incumbent solution’s
cost, and will return the solution found at width $k+1$. Third, if a solution
is found at slot $k+1$ with cost greater than the solution which would be
found by a search of width $k$, we know from Lemma 4 that we can use that
incumbent solution to prune nodes with f-values $\geq$ the cost of that
incumbent while still maintaining all the nodes that could lead to a better
solution. Thus, we will eventually find the solution that would have been
found by a search of width $k$ and return it. ∎

### Duplicate Handling

1 begin

2 done $\leftarrow$ false;

_3_ _ _ while  _candidates is nonempty and_

4  _done = false_ do

5 node $\leftarrow\min f$-value node from candidates;

6 node.width $\leftarrow$ c;

7 if  _node’s state is not in closed list_ then

8 add node to closed;

9 done $\leftarrow$ true;

10

11 else

12 dup $\leftarrow$ closed entry for node’s state ;

13 if  _node.width $<$ dup.width _ then

14 update closed entry to node;

15 done $\leftarrow$ true;

16

17 else if  _f(node) $\leq$ f(dup)_ then

18 if  _node.width = dup.width_ then

19 update closed entry to node;

20

21 done $\leftarrow$ true;

22

23 else

24 remove node from candidates;

25

Algorithm 3 Duplicate elimination, to be added before line 1 of Algorithm 1

ABh=1Dh=3Hh=5Eh=3Ih=5Fh=2$\alpha$Jh=4$\beta$$\ldots$*g=7$\gamma$Ch=2$\alpha$Gh=4$\beta$$\ldots$*g=6$\gamma$g=1g=2g=3

A
---
B
F
J
$\ldots$
(a) Width 1 beam.

A |
---|---
B | C
D | E
H | I
$\ldots$ | $\ldots$
(b) Width 2 beam.

Figure 3: An example in which full-beam duplicate elimination causes monobeam
to behave non-monotonically.

Eliminating duplicate nodes during search can be important for search spaces
with many cycles and transpositions, but must be done with care to preserve
monobeam’s monotonicity. Like regular beam search, for the purpose of
duplicate elimination, monobeam stores in a closed list all the nodes that
have been part of any beam along with their $f$-values. Beam search’s method
of duplicate elimination, which we call full-beam duplicate elimination, is:
if a node is generated with $f(n)=f_{new}$ and it occurs in closed with
$f(n)=f_{old}$ then it is discarded if $f_{new}\geq f_{old}$.

To see how adding this to monobeam can introduce non-monotonicity, consider
the example in Figure 3 where a monobeam search using full-beam duplicate
elimination with width 2 will return no solution, whereas a monobeam search
with width 1 will return a solution. In this figure, nodes C and F represent
the same state, which we will call $\alpha$, reached by different sequences of
actions. The trees below them are, of course, identical (for example, nodes G
and J represent the same state, $\beta$, and the goals below them are the same
state $\gamma$). There are no solutions below nodes H and I. The beams at each
level for widths 1 and 2 are shown in the boxes at the bottom of the figure.

For beam width 1, monobeam proceeds directly to the goal via path $A-B-
F-J\dots\gamma$. The width 2 search puts a node representing $\alpha$ into its
level 1 beam when it selects node C. This causes $\alpha$ to be put into the
closed list with $f(\alpha)=3$. When the node in slot 1 of this beam (B) is
expanded, D, E, and F are generated. Because the state F represents is already
closed with a smaller $f$-value, F is dropped. One of D or E is placed in slot
1 of the next beam and the other remains as a candidate for slot 2. Because
$f(G)$ is larger than that candidate’s $f$-value, the beam for the next level
consists of $D$ and $E$ (in some order), and not $G$. There is now no path to
a solution.

For this reason, duplicate handling must also pay attention to the slot from
which a node was expanded in order to preserve monotonic behavior. Nodes that
were expanded from higher beam slots cannot be counted as duplicates in the
lower beam slots or else we risk pruning away a solution that would have been
reached at that lower width. Therefore, we propose a method of duplicate
elimination in which the closed list records the beam slot at which a node was
expanded (denoted as $width$ in Algorithm 3) and that node can only be
considered as a duplicate at that width and higher (line 3). If we see the
node again at a lower beam slot, we update the entry in the closed list to
change it to the lower width value. Even if the higher beam slot version has a
better cost, we must use the worse cost version for pruning in lower beam
slots in order to preserve the search behavior that they would have followed
if the higher beam slots had not existed. It is possible to maintain both
versions for multiple widths to improve pruning, but this would increase both
the computational and memory requirements of duplicate checking.

######  Theorem 3.

Algorithms 1 and 3 with an admissible heuristic and beam width $k+1$ will
always return a solution with cost lower or equal to the cost of the best
solution found by the same algorithm with beam width $k$, for all $k\geq 1$.

###### Proof.

Because line 3 in Algorithm 3 provides that a duplicate child of a node from
slot $k$ can only be eliminated if the original copy was expanded from one of
the slots 1 through $k$, then Lemma 2 still holds and the proof is identical
to the proof of Theorem 1. ∎

#### A Disadvantage of Monotonicity

Monotonicity limits the pool of nodes from which the search can choose as it
selects nodes for each slot of the next layer’s beam. In its attempt to avoid
cuckoo nodes, monobeam prevents the search from choosing exactly those
children of the entire current beam that have the lowest $f$-values
(regardless of parentage). If the heuristic is generally helpful, then these
constraints will tend to lead to solutions with increased cost compared to
beam. It is an empirical question how severe the price of monotonicity tends
to be.

### Empirical Analysis

We implemented beam and monobeam in C++ 111Code available at
https://github.com/snlemons/search. and tested their behavior on several
classic search benchmarks. The implementation of monobeam tested uses the
pruning technique given in Algorithm 2 and the duplicate elimination technique
given in Algorithm 3. Each algorithm was run with widths 30, 100, 300, 1000,
3000, 10000, 30000, and 100000. Algorithms were given a memory limit of 7.5GB.

#### Sliding Tile Puzzle

We used five cost models: unit cost, where the cost of moving any tile is 1;
heavy cost, moving tile numbered $t$ costs $t$; sqrt cost, moving tile $t$
costs $\sqrt{t}$; inverse cost, $1/t$; reverse cost, moving tile t costs
$16-t$. The cost-to-go heuristic was a weighted version of the Manhattan
distance in which each tile’s Manhattan distance is multiplied by the cost of
moving that tile. Our implementation expands nodes at a rate of approximately
1.5 million nodes per second. The standard Korf (1985) 100 15-puzzles were
used in all cost models.

First, we verify that monobeam’s behavior is in fact monotonic, as claimed by
Theorem 1. Figure 1 illustrates its behavior, showing that monobeam lives up
to its name. It often finds worse solutions that regular beam search for very
low beam widths, but its steady behavior can be advantageous as the beam width
increases. Whereas we saw in the introduction that beam search was ill-behaved
on average 30% of the time, of course monobeam is never ill-behaved. In this
sense, monobeam can make beam-style searches simpler to use, because we can
pick a beam width as large as our system is able to accommodate, without
worrying about whether that width will cause it to perform worse than it would
have at lower widths.

(a) 15-puzzle (unit cost)

(b) 15-puzzle (heavy cost)

(c) 15-puzzle (sqrt cost)

(d) 15-puzzle (reverse cost)

(e) 15-puzzle (inverse cost)

(f) 20 pancake problem (unit cost)

(g) 50 pancake problem (unit cost)

(h) 70 pancake problem (unit cost)

(i) 20 blocks world (unit cost)

(j) 20 deep blocks world (unit cost)

(k) 20 pancake problem (heavy cost)

(l) Sol length vs cost (heavy 15-puzzle)

Figure 4: Panels a-k: time versus cost as beam width is varied (each point
corresponds to a beam width.) Panel l: solution length versus cost for heavy
tiles.

Next, we study the trade-off between solution cost and solving time in greater
detail. Figure 4 shows how each algorithm’s time / cost trade-off behaves as
the beam width is varied. (Several plots also include bead and monobead, two
algorithms that we will discuss below.) The x axis represents CPU time (log
scaled) and the y axis represents the returned solution’s cost (often log
scaled). A point is drawn for an algorithm for a specific beam width only if
it solved all instances when run with that width. Otherwise, there is simply a
gap left in the line for that beam width. We see in the unit cost plot (Figure
4(a)) that at the lowest beam widths, monobeam generally finds more expensive
solutions and takes more time to do so. But, as the beam width increases, it
converges with regular beam search.

The heavy tiles results shown in Figure 4(b) demonstrate a different kind of
behavior. Beam search is poorly behaved — at lower beam widths it takes a long
time to return poor quality solutions — while monobeam solves problems quickly
and exhibits a smooth well-behaved improvement with increasing beam width. At
large beam widths (10000 onward), beam finally improves enough to outperform
monobeam and at beam width 30000 monobeam fails to solve two instances (due to
the increased memory requirements and not finding a solution quickly enough).
Figure 4(c) demonstrates a less dramatic instance of similar behavior, where
beam search returns poorer quality solutions for the first two beam widths,
and then performs better than or equal with monobeam from there onward.

In reverse cost (Figure 4(d)) we see that beam search is unable to reliably
solve problems at many beam widths (although eventually does well at the
highest beam width of 100000). Monobeam is again much better behaved, solving
problems faster and with lower cost for a wider range of beam widths (it fails
only at widths 30, 30000, and 100000). In inverse cost (Figure 4(e)), beam
search was unable to solve problems reliably at any beam width, while monobeam
does well (failing to solve some instances again only at widths 30, 30000, and
100000). Overall, monobeam is much better behaved on the 15-puzzle than beam.

#### Pancake Problem

We ran with 50 random instances of problems with stacks of 20, 50, and 70
pancakes. The gap heuristic (Helmert 2010) was used by all algorithms. The
results for the 20-pancake problems, shown in Figure 4(f), shows monobeam
performing on average better than beam search at the lower beam widths, though
the differences are small. Likewise, for 50-pancake and 70-pancake problems in
Figures 4(g) and 4(h), we see beam search and monobeam performing roughly the
same with minor variations in solution quality. Overall, it appears that
monotonicity might actually benefit solution cost here instead of imposing
much of a penalty.

#### Blocks World

We tested on 100 random instances of blocks world, with two different action
models: one in which blocks are directly moved to a stack as an action
(‘blocks world’) and one in which picking up and putting down blocks each use
an action, so therefore the branching factor is smaller and plans are longer
(‘deep blocks world’). In both the regular and deep variants (Figures 4(i) and
4(j)), we see a significant trade-off for ensuring monotonicity at lower beam
widths (widths 30, 100, and 300) and both algorithms perform comparably at the
higher beam widths.

#### Summary

The price of monotonicity appears to be noticeable but modest. Beam search
performs very poorly on non-unit cost domains, with monobeam often behaving
much better. However, both algorithms are inconsistent at solving the
nefarious reverse and inverse cost 15-puzzles.

## Beam Search with Costs

We saw in the previous section that beam search behaves poorly in domains with
non-unit costs. For best-first search, searching using distance-to-go $d$
(known as speedy search) instead of cost-to-go $h$ (known as greedy best-first
search or GBFS) is well-known to yield faster search in non-unit domains
(Thayer and Ruml 2009). Originally this was thought to be due to $d$ being a
proxy for remaining search effort (Ruml and Do 2007; Burns, Ruml, and Do
2013). However, later work suggested that $d$ results in smaller local minima
for a best-first search (Wilt and Ruml 2014). It is not clear that the concept
of a local minimum or crater (Heusner, Keller, and Helmert 2017) carries over
from best-first search to beam search. However, the results above clearly show
poor performance for beam search in non-unit problems.

It is natural to ask whether guiding beam search using $d$ might help. In this
section, we explore this idea. We develop variants of the algorithms discussed
above that prefer nodes with low $d$. First, we introduce bead search, which
is beam search using a purely distance-based measurement $l(n)=depth(n)+d(n)$
(estimated length of solution) to select nodes for the beam. Bead search uses
the depth of the node and not the non-unit-cost $g$-value because the
distance-to-go estimate would be overwhelmed by $g$ in domains where costs are
much larger than 1. It uses the domain’s actual $f$ and $g$ values only for
tie-breaking, comparing solutions against an incumbent, and in duplicate
elimination for determining if a duplicate node is better than the previously
seen version.

We also introduce monobead search, which is monotonic beam search according to
the algorithm given in Figures 1 and 3, except using $l(n)$ to select nodes
for the beam. As with bead search, monobead uses the domain’s $f$ and $g$
values for tie breaking and duplicate elimination. It does not use incumbent-
based pruning, because Theorem 2 only applies when the search is ordered on
the same value function used for pruning.

### Empirical Analysis

#### Sliding Tile Puzzle

We use the unweighted Manhattan distance for the distance-to-go estimate $d$
used by bead and monobead.

In Figure 4(b), we see that in the heavy tiles domain, the d-based algorithms,
bead and monobead, find solutions more quickly, more consistently, and with
lower solution cost than the corresponding $f$-based algorithms, beam, and
monobeam. Note that there is no gap in the line for monobead, meaning that it
solves all instances at all beam widths, unlike monobeam. And Figure 4(e)
shows an even more pronounced case of this, with bead and monobead performing
very reasonably whereas beam search never solved more than 80% of the problems
at any beam width and monobeam failed to solve around 20% of the instances at
beam width 30 and failed to solve 20-30% of the instances at the two highest
beam widths (30000 and 100000). In all the non-unit 15-puzzle cost models, the
$d$-based variants are clearly the best performing.

Again, we observe that at lower beam widths, monobead generally finds less
desirable solutions than bead and takes more time to do so. But, as the beam
width increases, solution quality converges to about the same than bead (and
slightly better in inverse). Bead delivers best solutions under 0.01 seconds
but when larger beam widths are used, the solution delivered by both bead and
monobead converges and they both take the same time —see Figures 4(a)–4(e).

#### Pancake Problem

The algorithms were tested on 50 random instances of the heavy pancake problem
(Hatem and Ruml 2014), in which each pancake is given an ID number from 1
through $N$ (the number of pancakes), and the cost of a flip is the ID of the
pancake above the spatula. An adapted version of the gap heuristic was used
for cost-to-go estimates, and the standard gap heuristic was used as a
distance-to-go estimate $d$ for bead and monobead.

Figure 4(k) shows the performance of the algorithms in this domain. The
non-$d$ variants were not able to solve all instances for any of the beam
widths and so there are no points displayed for them in the figure. Monobeam
is able to solve some instances at beam widths 100 through 30000, but never
above 25% of all instances tested. However, the $d$-based variants are able to
consistently solve all instances and improve their solution quality as beam
width increases. The monotonic algorithm (monobead) performs better than the
non-monotonic (bead) algorithm, though the differences in cost are relatively
small.

#### Summary

As would be expected, searching on distance-to-go in non-unit domains leads us
to solutions faster than searching on cost-to-go. This effect is so powerful
that it allows us to find solutions where we otherwise could not. More
surprisingly, we see that beam searches using distance-to-go generally find
solutions with much lower cost than their cost-to-go counterparts. Indeed,
when solving heavy 15-puzzles with a beam width of 100, beam search typically
found solutions 25533 steps long, resulting in an average cost of 85843, while
bead found solutions of length 86, resulting in an average cost of only 622.

We speculate that this is due to a correlation between solution length and
cost. Figure 4(l) shows the costs and lengths of the solutions found by beam
and bead. The red line indicates what the cost would be if a solution of a
particular length used actions of average cost (8 for heavy tiles). We see
that bead finds much shorter solutions, although they tend to be more
expensive per action than those found by beam. One way to understand this is
that, because $d$-based beam searches ignores action costs (except for
duplicates, pruning, and tie-breaking) and instead focus on solution length,
their solutions will tend to be short. If actions along short solutions aren’t
unusually expensive, then the solutions found by $d$-based search will have
costs roughly proportional to the shortest solution path times the average
action cost. This can be much cheaper than the arbitrarily long solutions that
are found by $f$-guided beam searches.

## Discussion

Although this work provides a better-behaved beam search whose solution cost
is monotonic in beam width, clearly much work remains before we fully
understand the behavior of beam search. Our analysis of $d$-based beam search
suggests that, in the domains we tested, it can find short solution that
nonetheless use actions of only average cost, but this phenomenon deserves
comprehensive scrutiny. It remains important to fully understand why
$f$-guided beam search fails to find the shorter and much cheaper solutions
that bead does.

The monobeam algorithm has the limitation that when nodes can have no children
(for example, dead ends) or when pruning from duplicate elimination or a
candidate solution causes no children to be kept from a node, there may be
times at which no node is available to select for the current beam slot. If
all slots below the current one are also empty, those slots will stay empty
for the remainder of the search. For example, if slot 1 in our beam empties at
one level of the search, we will not be able to expand a node from slot 1 to
fill it ever again. A method to address this problem could improve the
performance of the algorithm, but it is not obvious how to retain a guarantee
of monotonicity, as any node that fills in the gap may well act as a cuckoo
node.

Our benchmarks include several classic combinatorial search domains, but
puzzle-like domains are overrepresented and it would be beneficial to extend
our study to domains of different character.

The other major family of unboundedly-suboptimal heuristic search algorithms
is based on best-first search. There has been work on understanding GBFS
(Heusner, Keller, and Helmert 2017) and making it more robust (Valenzano et
al. 2014; Xie, Müller, and Holte 2015). As mentioned above, distance-to-go has
been found an effective accelerator in the best-first setting (Thayer and Ruml
2009) as it appears to generate smaller local minima (Wilt and Ruml 2014). It
is an important area of future work to understand the analog of local minima
for beam search and explain the behavior of $h$ versus $d$ in this setting.

## Conclusions

We have advanced the study of beam search in two ways. First, we introduced a
simple monotonic variant of beam search, monobeam, and studied its interaction
with duplicate detection. Monobeam tends to find slightly worse solutions for
small widths in unit-cost problems, but is more robust and easier to use.
Second, we proposed using distance-to-go to guide beam search, resulting in
new variants that perform much better in non-unit-cost domains. Given the
importance of scalability in many applications, we hope this work widens the
applicability of heuristic search to problems of practical importance.

## Acknowledgments

We are grateful for support from the NSF-BSF program (via NSF grant 2008594)
and Earlham College (via the Lemann Student/Faculty Collaborative Research
Fund) and to Liam Peachey for work on the initial blocks world implementation.

## References

  * Bisiani (1987) Bisiani, R. 1987.  Beam search.  In Shapiro, S. C., ed., _Encyclopedia of Artificial Intelligence_ , 56–58. John Wiley and Sons.
  * Burns, Ruml, and Do (2013) Burns, E.; Ruml, W.; and Do, M. B. 2013.  Heuristic Search When Time Matters.  _Journal of Artificial Intelligence Research_ , 47: 697–740.
  * Cohen and Beck (2019) Cohen, E.; and Beck, C. 2019.  Empirical Analysis of Beam Search Performance Degradation in Neural Sequence Models.  In _Proceedings of ICML_ , 1290–1299.
  * Furcy and Koenig (2005) Furcy, D.; and Koenig, S. 2005.  Limited Discrepancy Beam Search.  In _Proceedings of IJCAI_.
  * Hatem and Ruml (2014) Hatem, M.; and Ruml, W. 2014.  Bounded suboptimal search in linear space: New results.  In _Seventh Annual Symposium on Combinatorial Search_.
  * Helmert (2010) Helmert, M. 2010.  Landmark heuristics for the pancake problem.  In _Third Annual Symposium on Combinatorial Search_.
  * Heusner, Keller, and Helmert (2017) Heusner, M.; Keller, T.; and Helmert, M. 2017.  Understanding the Search Behaviour of Greedy Best-first Search.  In _Proceedings of SoCS_.
  * Korf (1985) Korf, R. E. 1985.  Iterative-Deepening-A*: An Optimal Admissible Tree Search.  In _Proceedings of IJCAI-85_ , 1034–1036.
  * Meister et al. (2021) Meister, C. I.; Amini, A.; Vieira, T.; and Cotterell, R. 2021.  Conditional Poisson Stochastic Beams.  In _Proceedings of EMNLP_ , 664–681.
  * Mérõ (1984) Mérõ, L. 1984.  A heuristic search algorithm with modifiable estimate.  _Artificial Intelligence_ , 23(1): 13–27.
  * Ow and Morton (1988) Ow, P. S.; and Morton, T. E. 1988.  Extended beam search for non-exhaustive state space analysis.  _Int. J. Prod. Res_ , 26(1): 35–62.
  * Ruml and Do (2007) Ruml, W.; and Do, M. B. 2007.  Best-first Utility-guided Search.  In _Proceedings of IJCAI-07_ , 2378–2384.
  * Thayer and Ruml (2009) Thayer, J. T.; and Ruml, W. 2009.  Using Distance Estimates in Heuristic Search.  In _Proceedings of ICAPS_.
  * Vadlamudi, Aine, and Chakrabarti (2013) Vadlamudi, S. G.; Aine, S.; and Chakrabarti, P. 2013.  Incremental Beam Search.  _Information Processing Letters_ , 113(22-24): 888–893.
  * Valente and Alves (2008) Valente, J. M.; and Alves, R. A. 2008.  Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups.  _Computers & Operations Research_, 35(7): 2388–2405.
  * Valenzano et al. (2014) Valenzano, R. A.; Sturtevant, N. R.; Schaeffer, J.; and Xie, F. 2014.  A Comparison of Knowledge-Based GBFS Enhancements and Knowledge-Free Exploration.  In _Proceedings of ICAPS_.
  * Wijs and Dashti (2012) Wijs, A. J.; and Dashti, M. T. 2012.  Extended beam search for non-exhaustive state space analysis.  _The Journal of Logic and Algebraic Programming_ , 81(1): 46–68.
  * Wilt and Ruml (2014) Wilt, C.; and Ruml, W. 2014.  Speedy Versus Greedy Search.  In _Proceedings of SoCS_.
  * Wilt, Thayer, and Ruml (2010) Wilt, C.; Thayer, J.; and Ruml, W. 2010.  A Comparison of Greedy Search Algorithms.  In _Proceedings of SoCS_.
  * Wilt, Thayer, and Ruml (2011) Wilt, C.; Thayer, J.; and Ruml, W. 2011.  Selecting a Greedy Search Algorithm.  Technical Report TR-10-07, University of New Hampshire.
  * Xie, Müller, and Holte (2015) Xie, F.; Müller, M.; and Holte, R. 2015.  Understanding and Improving Local Exploration for GBFS.  In _Proceedings of ICAPS_ , 244–248.
  * Zhang (1998) Zhang, W. 1998.  Complete Anytime Beam Search.  In _Proceedings of AAAI-98_ , 425–430.
  * Zhou and Hansen (2005) Zhou, R.; and Hansen, E. A. 2005.  Beam-Stack Search: Integrating Backtracking with Beam Search.  In _Proceedings of ICAPS_ , 90–98.


# SmoothQuant: Accurate and Efficient
Post-Training Quantization for Large Language Models

Guangxuan Xiao  Ji Lin  Mickael Seznec  Hao Wu  Julien Demouth  Song Han

###### Abstract

Large language models (LLMs) show excellent performance but are compute- and
memory-intensive. Quantization can reduce memory and accelerate inference.
However, existing methods cannot maintain accuracy and hardware efficiency at
the same time. We propose SmoothQuant, a training-free, accuracy-preserving,
and general-purpose post-training quantization (PTQ) solution to enable 8-bit
weight, 8-bit activation (W8A8) quantization for LLMs. Based on the fact that
weights are easy to quantize while activations are not, SmoothQuant smooths
the activation outliers by offline migrating the quantization difficulty from
activations to weights with a mathematically equivalent transformation.
SmoothQuant enables an INT8 quantization of both weights and activations for
all the matrix multiplications in LLMs, including OPT, BLOOM, GLM, MT-NLG, and
LLaMA family. We demonstrate up to 1.56$\times$ speedup and 2$\times$ memory
reduction for LLMs with negligible loss in accuracy. SmoothQuant enables
serving 530B LLM within a single node. Our work offers a turn-key solution
that reduces hardware costs and democratizes LLMs.

Machine Learning, ICML

https://github.com/mit-han-lab/smoothquant

##  1 Introduction

Large-scale language models (LLMs) show excellent performance on various tasks
(Brown et al., 2020a; Zhang et al., 2022). However, serving LLMs is budget and
energy-consuming due to their gigantic model size. For example, the GPT-3
(Brown et al., 2020a) model contains 175B parameters, which will consume at
least 350GB of memory to store and run in FP16, requiring 8$\times$48GB A6000
GPUs or 5$\times$80GB A100 GPUs just for inference. Due to the huge
computation and communication overhead, the inference latency may also be
unacceptable to real-world applications. _Quantization_ is a promising way to
reduce the cost of LLMs (Dettmers et al., 2022; Yao et al., 2022). By
quantizing the _weights and activations_ with low-bit integers, we can reduce
GPU memory requirements, in size and bandwidth, and accelerate compute-
intensive operations (i.e., GEMM in linear layers, BMM in attention). For
instance, INT8 quantization of weights and activations can halve the GPU
memory usage and nearly double the throughput of matrix multiplications
compared to FP16.

Figure 1: The model size of large language models is developing at a faster
pace than the GPU memory in recent years, leading to a big gap between the
supply and demand for memory. Quantization and model compression techniques
can help bridge the gap.

However, unlike CNN models or smaller transformer models like BERT (Devlin et
al., 2019), the _activations_ of LLMs are difficult to quantize. When we scale
up LLMs beyond 6.7B parameters, systematic outliers with large magnitude will
emerge in activations (Dettmers et al., 2022), leading to large quantization
errors and accuracy degradation. ZeroQuant (Yao et al., 2022) applies dynamic
per-token activation quantization and group-wise weight quantization (defined
in Figure 3 Sec. 2). It can be implemented efficiently and delivers good
accuracy for GPT-3-350M and GPT-J-6B. However, it can not maintain the
accuracy for the large OPT model with 175 billion parameters (see Section
5.2). LLM.int8() (Dettmers et al., 2022) addresses that accuracy issue by
further introducing a mixed-precision decomposition (i.e., it keeps outliers
in FP16 and uses INT8 for the other activations). However, it is hard to
implement the decomposition efficiently on hardware accelerators. Therefore,
deriving an _efficient_ , _hardware-friendly_ , and preferably _training-free_
quantization scheme for LLMs that would use INT8 for all the compute-intensive
operations remains an open challenge.

We propose SmoothQuant, an accurate and efficient post-training quantization
(PTQ) solution for LLMs. SmoothQuant relies on a key observation: even if
activations are much harder to quantize than weights due to the presence of
outliers (Dettmers et al., 2022), different tokens exhibit similar variations
across their channels.

Figure 2: SmoothQuant’s intuition: the activation $\mathbf{X}$ is hard to
quantize because outliers stretch the quantization range, leaving few
effective bits for most values. We migrate the scale variance from activations
to weights $\mathbf{W}$ during offline to reduce the quantization difficulty
of activations. The smoothed activation $\hat{\mathbf{X}}$ and the adjusted
weight $\hat{\mathbf{W}}$ are both easy to quantize.

Based on this observation, SmoothQuant offline migrates the quantization
difficulty from activations to weights (Figure 2). SmoothQuant proposes a
mathematically equivalent per-channel scaling transformation that
significantly smooths the magnitude across the channels, making the model
quantization-friendly. Since SmoothQuant is compatible with various
quantization schemes, we implement three efficiency levels of quantization
settings for SmoothQuant (see Table 2, O1-O3). Experiments show that
SmoothQuant is hardware-efficient: it can maintain the performance of OPT-175B
(Zhang et al., 2022), BLOOM-176B (Scao et al., 2022) , GLM-130B (Zeng et al.,
2022), and MT-NLG 530B (Smith et al., 2022), leading to up to 1.51$\times$
speed up and 1.96$\times$ memory saving on PyTorch. SmoothQuant is easy to
implement. We integrate SmoothQuant into FasterTransformer, the state-of-the-
art transformer serving framework, achieving up to 1.56$\times$ speedup and
halving the memory usage compared with FP16. Remarkably, SmoothQuant allows
serving large models like OPT-175B using only half number of GPUs compared to
FP16 while being faster, and enabling the serving of a 530B model within one
8-GPU node. Our work democratizes the use of LLMs by offering a turnkey
solution to reduce the serving cost. We hope SmoothQuant can inspire greater
use of LLMs in the future.

##  2 Preliminaries

Quantization maps a high-precision value into discrete levels. We study
integer uniform quantization (Jacob et al., 2018) (specifically INT8) for
better hardware support and efficiency. The quantization process can be
expressed as:

$\bar{\mathbf{X}}^{\text{INT8}}=\lceil\frac{\mathbf{X^{\text{FP16}}}}{\Delta}\rfloor,\quad\Delta=\frac{\max(|\mathbf{X}|)}{2^{N-1}-1},$
(1)

where $\mathbf{X}$ is the floating-point tensor, $\bar{\mathbf{X}}$ is the
quantized counterpart, $\Delta$ is the quantization step size,
$\lceil\cdot\rfloor$ is the rounding function, and $N$ is the number of bits
(8 in our case). Here we assume the tensor is _symmetric_ at 0 for simplicity;
the discussion is similar for asymmetric cases (e.g., after ReLU) by adding a
zero-point (Jacob et al., 2018).

Such quantizer uses the maximum absolute value to calculate $\Delta$ so that
it preserves the outliers in activation, which are found to be important for
accuracy (Dettmers et al., 2022). We can calculate $\Delta$ offline with the
activations of some calibration samples, what we call static quantization. We
can also use the runtime statistics of activations to get $\Delta$, what we
call dynamic quantization.

Figure 3:  Definition of per-tensor, per-token, and per-channel quantization.
Per-tensor quantization is the most efficient to implement. For vector-wise
quantization to efficiently utilize the INT8 GEMM kernels, we can only use
scaling factors from the outer dimensions (i.e., token dimension $T$ and out
channel dimension $C_{o}$) but not inner dimension (i.e., in channel dimension
$C_{i}$).

As shown in Figure 3, quantization has different granularity levels. The per-
tensor quantization uses a single step size for the entire matrix. We can
further enable finer-grained quantization by using different quantization step
sizes for activations associated with each token (per-token quantization) or
each output channel of weights (per-channel quantization). A coarse-grained
version of per-channel quantization is to use different quantization steps for
different channel groups, called group-wise quantization (Shen et al., 2020;
Yao et al., 2022).

For a linear layer in Transformers (Vaswani et al., 2017)
$\mathbf{Y}=\mathbf{X}\cdot\mathbf{W},\mathbf{Y}\in\mathbb{R}^{T\times
C_{o}},\mathbf{X}\in\mathbb{R}^{T\times
C_{i}},\mathbf{W}\in\mathbb{R}^{C_{i}\times C_{o}}$, where $T$ is the number
of tokens, $C_{i}$ is the input channel, and $C_{o}$ is the output channel
(see Figure 3, we omit the batch dimension for simplicity), we can reduce the
storage by half compared to FP16 by quantizing the weights to INT8. However,
to speed up the inference, we need to quantize both weights and activations
into INT8 (i.e., W8A8) to utilize the integer kernels (e.g., INT8 GEMM), which
are supported by a wide range of hardware (e.g., NVIDIA GPUs, Intel CPUs,
Qualcomm DSPs, etc.).

Figure 4:  Magnitude of the input activations and weights of a linear layer in
OPT-13B before and after SmoothQuant. Observations: (1) there are a few
channels in the original activation map whose magnitudes are very large
(greater than 70); (2) the variance in one activation channel is small; (3)
the original weight distribution is flat and uniform. SmoothQuant migrates the
outlier channels from activation to weight. In the end, the outliers in the
activation are greatly smoothed while the weight is still pretty smooth and
flat.

##  3 Review of Quantization Difficulty

LLMs are notoriously difficult to quantize due to the outliers in the
activations (Dettmers et al., 2022; Wei et al., 2022; Bondarenko et al.,
2021). We first review the difficulties of activation quantization and look
for a pattern amongst outliers. We visualize the input activations and the
weights of a linear layer that has a large quantization error in Figure 4
(left). We can find several patterns that motivate our method:

1\. Activations are harder to quantize than weights.  The weight distribution
is quite uniform and flat, which is easy to quantize. Previous work has shown
that quantizing the weights of LLMs with INT8 or even with INT4 does not
degrade accuracy (Dettmers et al., 2022; Yao et al., 2022; Zeng et al., 2022),
which echoes our observation.

2\. Outliers make activation quantization difficult. The scale of outliers in
activations is $\sim 100\times$ larger than most of the activation values. In
the case of per-tensor quantization (Equation 1), the large outliers dominate
the maximum magnitude measurement, leading to low _effective quantization
bits/levels_ (Figure 2) for non-outlier channels: suppose the maximum
magnitude of channel $i$ is $m_{i}$, and the maximum value of the whole matrix
is $m$, the effective quantization levels of channel $i$ is $2^{8}\cdot
m_{i}/m$. For non-outlier channels, the effective quantization levels would be
very small (2-3), leading to large quantization errors.

3\. Outliers persist in fixed channels.  Outliers appear in a small fraction
of the _channels_. If one channel has an outlier, it persistently appears in
all tokens (Figure 4, red). The variance amongst the channels for a given
token is large (the activations in some channels are very large, but most are
small), but the variance between the magnitudes of a given channel across
tokens is small (outlier channels are consistently large).

Table 1: Among different activation quantization schemes, only per-channel quantization (Bondarenko et al., 2021) preserves the accuracy, but it is _not_ compatible (marked in gray) with INT8 GEMM kernels. We report the average accuracy on WinoGrande, HellaSwag, PIQA, and LAMBADA.  Model size (OPT-) | 6.7B | 13B | 30B | 66B | 175B
---|---|---|---|---|---
FP16 | 64.9% | 65.6% | 67.9% | 69.5% | 71.6%
INT8 per-tensor | 39.9% | 33.0% | 32.8% | 33.1% | 32.3%
INT8 per-token | 42.5% | 33.0% | 33.1% | 32.9% | 31.7%
INT8 per-channel | 64.8% | 65.6% | 68.0% | 69.4% | 71.4%

Due to the persistence of outliers and the small variance inside each channel,
if we could perform _per-channel_ quantization (Bondarenko et al., 2021) of
the activation (i.e., using a different quantization step for each channel),
the quantization error would be much smaller compared to _per-tensor_
quantization, while _per-token_ quantization helps little. In Table 1, we
verify the assumption that simulated per-channel activation quantization
successfully bridges the accuracy with the FP16 baseline, which echos the
findings of Bondarenko et al..

However, per-channel activation quantization does not map well to hardware-
accelerated GEMM kernels, that rely on a sequence of operations executed at a
high throughput (e.g., Tensor Core MMAs) and do not tolerate the insertion of
instructions with a lower throughput (e.g., conversions or CUDA Core FMAs) in
that sequence. In those kernels, scaling can only be performed along the outer
dimensions of the matrix multiplication (i.e., token dimension of activations
$T$, output channel dimension of weights $C_{o}$, see Figure 3), which can be
applied after the matrix multiplication finishes:

$\mathbf{Y}=\text{diag}(\mathbf{\Delta}_{\mathbf{X}}^{\text{FP16}})\cdot(\mathbf{\bar{X}}^{\text{INT8}}\cdot\mathbf{\bar{W}}^{\text{INT8}})\cdot\text{diag}(\mathbf{\Delta}_{\mathbf{W}}^{\text{FP16}})$
(2)

Therefore, previous works all use per-token activation quantization for linear
layers (Dettmers et al., 2022; Yao et al., 2022), although they cannot address
the difficulty of activation quantization (only slightly better than per-
tensor).

##  4 SmoothQuant

Instead of per-channel activation quantization (which is infeasible), we
propose to “smooth” the input activation by dividing it by a per-channel
smoothing factor $\mathbf{s}\in\mathbb{R}^{C_{i}}$. To keep the mathematical
equivalence of a linear layer, we scale the weights accordingly in the
reversed direction:

$\mathbf{Y}=(\mathbf{X}\text{diag}(\mathbf{s})^{-1})\cdot(\text{diag}(\mathbf{s})\mathbf{W})=\hat{\mathbf{X}}\hat{\mathbf{W}}$
(3)

Considering input $\mathbf{X}$ is usually produced from previous linear
operations (e.g., linear layers, layer norms, etc.), we can easily fuse the
smoothing factor into previous layers’ parameters offline, which doe not incur
kernel call overhead from an extra scaling. For some other cases, when the
input is from a residual add, we can add an extra scaling to the residual
branch similar to Wei et al. (2022).

#### Migrate the quantization difficulty from activations to weights.

We aim to choose a per-channel smoothing factor $\mathbf{s}$ such that
$\hat{\mathbf{X}}=\mathbf{X}\text{diag}(\mathbf{s})^{-1}$ is easy to quantize.
To reduce the quantization error, we should _increase the effective
quantization bits_ for all the channels. The total effective quantization bits
would be largest when all the channels have the same maximum magnitude.
Therefore, a straight-forward choice is
$\mathbf{s}_{j}=\max(|\mathbf{X}_{j}|),j=1,2,...,C_{i}$, where $j$ corresponds
to $j$-th input channel. This choice ensures that after the division, all the
activation channels will have the same maximum value, which is easy to
quantize. Note that the range of activations is dynamic; it varies for
different input samples. Here, we estimate the scale of activations channels
using calibration samples from the pre-training dataset (Jacob et al., 2018).
However, this formula pushes _all_ the quantization difficulties to the
weights. We find that, in this case, the quantization errors would be large
for the weights (outlier channels are migrated to weights now), leading to a
large accuracy degradation (see Figure 10). On the other hand, we can also
push all the quantization difficulty from weights to activations by choosing
$\mathbf{s}_{j}=1/\max(|\mathbf{W}_{j}|)$. Similarly, the model performance is
bad due to the activation quantization errors. Therefore, we need to _split_
the quantization difficulty between weights and activations so that they are
both easy to quantize.

Figure 5: Main idea of SmoothQuant when $\alpha$ is $0.5$. The smoothing
factor $s$ is obtained on calibration samples and the entire transformation is
performed offline. At runtime, the activations are smooth without scaling.

Here we introduce a hyper-parameter, migration strength $\alpha$, to control
how much difficulty we want to migrate from activation to weights, using the
following equation:

$\mathbf{s}_{j}=\max(|\mathbf{X}_{j}|)^{\alpha}/\max(|\mathbf{W}_{j}|)^{1-\alpha}$
(4)

We find that for most of the models, e.g., all OPT (Zhang et al., 2022) and
BLOOM (Scao et al., 2022) models, $\alpha=0.5$ is a well-balanced point to
evenly split the quantization difficulty, especially when we are using the
same quantizer for weights and activations (e.g., per-tensor, static
quantization). The formula ensures that the weights and activations at the
corresponding channel share a similar maximum value, thus sharing the same
quantization difficulty. Figure 5 illustrates the smoothing transformation
when we take $\alpha=0.5$. For some other models where activation outliers are
more significant (e.g., GLM-130B (Zeng et al., 2022) has $\sim$30% outliers,
which are more difficult for activation quantization), we can choose a larger
$\alpha$ to migrate more quantization difficulty to weights (like 0.75).

Figure 6: SmoothQuant’s precision mapping for a Transformer block. All
compute-intensive operators like linear layers and batched matmul (BMMs) use
INT8 arithmetic.

#### Applying SmoothQuant to Transformer blocks.

Linear layers take up most of the parameters and computation of LLM models. By
default, we perform scale smoothing for the input activations of self-
attention and feed-forward layers and quantize all linear layers with W8A8. We
also quantize BMM operators in the attention computation. We design a
quantization flow for transformer blocks in Figure 6. We quantize the inputs
and weights of compute-heavy operators like linear layers and BMM in attention
layers with INT8, while keeping the activation as FP16 for other lightweight
element-wise operations like ReLU, Softmax, and LayerNorm. Such a design helps
us to balance accuracy and inference efficiency.

##  5 Experiments

###  5.1 Setups

#### Baselines.

Table 2: Quantization setting of the baselines and SmoothQuant. All weight and activations use INT8 representations unless specified. For SmoothQuant, the efficiency improves from O1 to O3 (i.e., lower latency).  Method | Weight | Activation
---|---|---
W8A8 | per-tensor | per-tensor dynamic
ZeroQuant | group-wise | per-token dynamic
LLM.int8() | per-channel | per-token dynamic+FP16
Outlier Suppression | per-tensor | per-tensor static
SmoothQuant-O1 | per-tensor | per-token dynamic
SmoothQuant-O2 | per-tensor | per-tensor dynamic
SmoothQuant-O3 | per-tensor | per-tensor static

We compare with four baselines in the INT8 post-training quantization setting,
i.e., without re-training of the model parameters: W8A8 naive quantization,
ZeroQuant (Yao et al., 2022), LLM.int8() (Dettmers et al., 2022), and Outlier
Suppression (Wei et al., 2022). Since SmoothQuant is orthogonal to the
quantization schemes, we provide gradually aggressive and efficient
quantization levels from O1 to O3. The detailed quantization schemes of the
baselines and SmoothQuant are shown in Table 2.

Table 3: SmoothQuant maintains the accuracy of OPT-175B model after INT8 quantization, even with the most aggressive and most efficient O3 setting (Table 2). We extensively benchmark the performance on 7 zero-shot benchmarks (by reporting the average accuracy) and 1 language modeling benchmark (perplexity). *For ZeroQuant, we also tried leaving the input activation of self-attention in FP16 and quantizing the rest to INT8, which is their solution to the GPT-NeoX-20B. But this does not solve the accuracy degradation of OPT-175B. _OPT-175B_ | LAMBADA | HellaSwag | PIQA | WinoGrande | OpenBookQA | RTE | COPA | Average$\uparrow$ | WikiText$\downarrow$
---|---|---|---|---|---|---|---|---|---
FP16 | 74.7% | 59.3% | 79.7% | 72.6% | 34.0% | 59.9% | 88.0% | 66.9% | 10.99
W8A8 | 0.0% | 25.6% | 53.4% | 50.3% | 14.0% | 49.5% | 56.0% | 35.5% | 93080
ZeroQuant | 0.0%* | 26.0% | 51.7% | 49.3% | 17.8% | 50.9% | 55.0% | 35.8% | 84648
LLM.int8() | 74.7% | 59.2% | 79.7% | 72.1% | 34.2% | 60.3% | 87.0% | 66.7% | 11.10
Outlier Suppression | 0.00% | 25.8% | 52.5% | 48.6% | 16.6% | 53.4% | 55.0% | 36.0% | 96151
SmoothQuant-O1 | 74.7% | 59.2% | 79.7% | 71.2% | 33.4% | 58.1% | 89.0% | 66.5% | 11.11
SmoothQuant-O2 | 75.0% | 59.0% | 79.2% | 71.2% | 33.0% | 59.6% | 88.0% | 66.4% | 11.14
SmoothQuant-O3 | 74.6% | 58.9% | 79.7% | 71.2% | 33.4% | 59.9% | 90.0% | 66.8% | 11.17
Table 4: SmoothQuant works for different LLMs. We can quantize the 3 largest, openly available LLM models into INT8 without degrading the accuracy. For OPT-175B and BLOOM-176B, we show the average accuracy on WinoGrande, HellaSwag, PIQA, and LAMBADA. For GLM-130B we show the average accuracy on LAMBADA, MMLU, MNLI, and QNLI. *Accuracy is not column-wise comparable due to different datasets.  Method | OPT-175B | BLOOM-176B | GLM-130B*
---|---|---|---
FP16 | 71.6% | 68.2% | 73.8%
W8A8 | 32.3% | 64.2% | 26.9%
ZeroQuant | 31.7% | 67.4% | 26.7%
LLM.int8() | 71.4% | 68.0% | 73.8%
Outlier Suppression | 31.7% | 54.1% | 63.5%
SmoothQuant-O1 |  71.2% | 68.3% | 73.7%
SmoothQuant-O2 | 71.1% |  68.4% | 72.5%
SmoothQuant-O3 | 71.1% | 67.4% | 72.8%

#### Models and datasets.

We choose three families of LLMs to evaluate SmoothQuant: OPT (Zhang et al.,
2022), BLOOM (Scao et al., 2022), and GLM-130B (Zeng et al., 2022). We use
seven zero-shot evaluation tasks: LAMBADA (Paperno et al., 2016), HellaSwag
(Zellers et al., 2019), PIQA (Bisk et al., 2020), WinoGrande (Sakaguchi et
al., 2019), OpenBookQA (Mihaylov et al., 2018), RTE (Wang et al., 2018), COPA
(Roemmele et al., 2011), and one language modeling dataset WikiText (Merity et
al., 2016) to evaluate the OPT and BLOOM models. We use MMLU (Hendrycks et
al., 2020), MNLI (Williams et al., 2018), QNLI (Wang et al., 2018) and LAMBADA
to evaluate the GLM-130B model because some of the aforementioned benchmarks
appear in the training set of GLM-130B. We use lm-eval-
harness***https://github.com/EleutherAI/lm-evaluation-harness to evaluate OPT
and BLOOM models, and GLM-130B’s official
repo†††https://github.com/THUDM/GLM-130B for its own evaluation. Finally, we
scale up our method to MT-NLG 530B (Smith et al., 2022) and for the first time
enabling the serving of a >500B model within a single node. Note that we focus
on the _relative_ performance change before and after quantization but not the
absolute value.

#### Activation smoothing.

The migration strength $\alpha=0.5$ is a general sweet spot for all the OPT
and BLOOM models, and $\alpha=0.75$ for GLM-130B since its activations are
more difficult to quantize (Zeng et al., 2022). We get a suitable $\alpha$ by
running a quick grid search on a subset of the Pile (Gao et al., 2020)
validation set. To get the statistics of activations, we calibrate the
smoothing factors and the static quantization step sizes _once_ with 512
random sentences from the pre-training dataset Pile, and apply the same
smoothed and quantized model for all downstream tasks. In this way, we can
benchmark the generality and zero-shot performance of the quantized LLMs.

#### Implementation.

We implement SmoothQuant with two backends: (1) PyTorch
Huggingface‡‡‡https://github.com/huggingface/transformers for the proof of
concept, and (2)
FasterTransformer§§§https://github.com/NVIDIA/FasterTransformer, as an example
of a high-performance framework used in production environments. In both
PyTorch Huggingface and FasterTransformer frameworks, we implement INT8 linear
modules and the batched matrix multiplication (BMM) function with CUTLASS INT8
GEMM kernels. We simply replace the original floating point (FP16) linear
modules and the bmm function with our INT8 kernels as the INT8 model.

###  5.2 Accurate Quantization

#### Results of OPT-175B.

SmoothQuant can handle the quantization of very large LLMs, whose activations
are more difficult to quantize. We study quantization on OPT-175B. As shown in
Table 3, SmoothQuant can match the FP16 accuracy on all evaluation datasets
with all quantization schemes. LLM.int8() can match the floating point
accuracy because they use floating-point values to represent outliers, which
leads to a large latency overhead (Table 10). The W8A8, ZeroQuant, and Outlier
Suppression baselines produce nearly random results, indicating that naively
quantizing the activation of LLMs will destroy the performance.

#### Results of different LLMs.

SmoothQuant can be applied to various LLM designs. In Table 4, we show
SmoothQuant can quantize all existing open LLMs beyond 100B parameters.
Compared with the OPT-175B model, the BLOOM-176B model is easier to quantize:
none of the baselines completely destroys the model; even the naive W8A8 per-
tensor dynamic quantization only degrades the accuracy by 4%. The O1 and O2
levels of SmoothQuant successfully maintain the floating point accuracy, while
the O3 level (per-tensor static) degrades the average accuracy by 0.8%, which
we attribute to the discrepancy between the statically collected statistics
and the real evaluation samples’ activation statistics. On the contrary, the
GLM-130B model is more difficult to quantize (which echos Zeng et al.).
Nonetheless, SmoothQuant-O1 can match the FP16 accuracy, while SmoothQuant-O3
only degrades the accuracy by 1%, which significantly outperforms the
baselines. Note that we clip the top 2% tokens when calibrating the static
quantization step sizes for GLM-130B following Wei et al. (2022). Note that
different model/training designs have different quantization difficulties,
which we hope will inspire future research.

Figure 7: SmoothQuant-O3 (the most efficient setting, defined in Table 2)
preserves the accuracy of OPT models across different scales when quantized to
INT8. LLM.int8() requires mixed precision and suffers from slowing down.

#### Results on LLMs of different sizes.

SmoothQuant works not only for the very large LLMs beyond 100B parameters, but
it also works consistently for smaller LLMs. In Figure 7, we show that
SmoothQuant can work on all scales of OPT models, matching the FP16 accuracy
with INT8 quantization.

#### Results on Instruction-Tuned LLM

Table 5: SmoothQuant’s performance on the OPT-IML model.  OPT-IML-30B |  LAMBADA $\uparrow$ |  WikiText $\downarrow$
---|---|---
FP16 | 69.12% | 14.26
W8A8 | 4.21% | 576.53
ZeroQuant | 5.12% | 455.12
LLM.int8() | 69.14% | 14.27
Outlier Suppression | 0.00% | 9485.62
SmoothQuant-O3 | 69.77% | 14.37

Shown in Table 5, SmoothQuant also works on instruction-tuned LLMs. We test
SmoothQuant on the OPT-IML-30B model using the WikiText-2 and LAMBADA
datasets. Our results show that SmoothQuant successfully preserves model
accuracy with W8A8 quantization, whereas the baselines fail to do so.
SmoothQuant is a general method designed to balance the quantization
difficulty for Transformer models. As the architecture of instruction-tuned
LLMs is not fundamentally different from vanilla LLMs, and their pre-training
processes are very similar, SmoothQuant is applicable to instruction-tuned
LLMs as well.

#### Results on LLaMA models.

Table 6: SmoothQuant can enable lossless W8A8 quantization for LLaMA models (Touvron et al., 2023). Results are perplexity on WikiText-2 dataset. We used per-token activation quantization and $\alpha$=0.8 for SmoothQuant.  Wiki PPL$\downarrow$ | 7B | 13B | 30B | 65B
---|---|---|---|---
FP16 | 11.51 | 10.05 | 7.53 | 6.17
W8A8 SmoothQuant | 11.56 | 10.08 | 7.56 | 6.20

LLaMA models are new open languange models with superior performance (Touvron
et al., 2023). Through initial experiments, we find LLaMA models generally
have less severe activation outlier issues compared to models like OPT and
BLOOM. Nonetheless, SmoothQuant still works quite well for LLaMA models. We
provide some initial results of LLaMA W8A8 quantization in Table 6.
SmoothQuant enables W8A8 quantization at a negligible performance degradation.

###  5.3 Speedup and Memory Saving

In this section, we show the measured speedup and memory saving of
SmoothQuant-O3 integrated into PyTorch and FasterTransformer.

#### Context-stage: PyTorch Implementation.

We measure the end-to-end latency of generating all hidden states for a batch
of 4 sentences in one pass, i.e., the context stage latency. We record the
(aggregated) peak GPU memory usage in this process. We only compare
SmoothQuant with LLM.int8() because it is the only existing quantization
method that can preserve LLM accuracy at all scales. Due to the lack of
support for model parallelism in Huggingface, we only measure SmoothQuant’s
performance on a single GPU for the PyTorch implementation, so we choose
OPT-6.7B, OPT-13B, and OPT-30B for evaluation. In the FasterTransformer
library, SmoothQuant can seamlessly work with Tensor Parallelism (Shoeybi et
al., 2019) algorithm, so we test SmoothQuant on OPT-13B, OPT-30B, OPT-66B, and
OPT-175B for both single and multi-GPU benchmarks. All our experiments are
conducted on NVIDIA A100 80GB GPU servers.

Figure 8: The PyTorch implementation of SmoothQuant-O3 achieves up to
1.51$\times$ speedup and 1.96$\times$ memory saving for OPT models on a single
NVIDIA A100-80GB GPU, while LLM.int8() slows down the inference in most cases.

In Figure 8, we show the inference latency and peak memory usage based on the
PyTorch implementation. SmoothQuant is consistently faster than the FP16
baseline, getting a 1.51x speedup on OPT-30B when the sequence length is 256.
We also see a trend that the larger the model, the more significant the
acceleration. On the other hand, LLM.int8() is almost always slower than the
FP16 baseline, which is due to the large overhead of the mixed-precision
activation representation. In terms of memory, SmoothQuant and LLM.int8() can
all nearly halve the memory usage of the FP16 model, while SmoothQuant saves
slightly more memory because it uses fully INT8 GEMMs.

Figure 9: Inference latency (top) and memory usage (bottom) of the
FasterTransformer implementation on NVIDIA A100-80GB GPUs. For smaller models,
the latency can be significantly reduced with SmoothQuant-O3 by up to 1.56x
compared to FP16. For the bigger models (OPT-66B and 175B), we can achieve
similar or even faster inference using only half number of GPUs. Memory
footprint is almost halved compared to FP16.

#### Context-stage: FasterTransformer Implementation.

As shown in Figure 9 (top), compared to FasterTransformer’s FP16
implementation of OPT, SmoothQuant-O3 can further reduce the execution latency
of OPT-13B and OPT-30B by up to 1.56$\times$ when using a single GPU. This is
challenging since FasterTransformer is already more than 3$\times$ faster
compared to the PyTorch implementation for OPT-30B. Remarkably, for bigger
models that have to be distributed across multiple GPUs, SmoothQuant achieves
similar or even better latency using only _half_ the number of GPUs (1 GPU
instead of 2 for OPT-66B, 4 GPUs instead of 8 for OPT-175B). This could
greatly lower the cost of serving LLMs. The amount of memory needed when using
SmoothQuant-O3 in FasterTransformer is reduced by a factor of almost
2$\times$, as shown on Figure 9 (bottom).

#### Decoding-stage.

In Table 7, we show SmoothQuant can significantly accelerate the
autoregressive decoding stage of LLMs. SmoothQuant constantly reduces the per-
token decoding latency compared to FP16 (up to 1.42x speedup). Additionally,
SmoothQuant halves the memory footprints for LLM inference, enabling the
deployment of LLMs at a significantly lower cost.

Table 7: SmoothQuant ’s performance in the decoding stage.  BS | SeqLen | Latency (ms) | Memory (GB)
---|---|---|---
FP16 | Ours |  Speedup ($\uparrow$) | FP16 | Ours |  Saving ($\uparrow$)
OPT-30B (1 GPU)
1 | 512 | 422 | 314 |  1.35$\times$ | 57 | 30 |  1.91$\times$
1 | 1024 | 559 | 440 |  1.27$\times$ | 58 | 31 |  1.87$\times$
16 | 512 | 2488 | 1753 |  1.42$\times$ | 69 | 44 |  1.59$\times$
16 | 1024 | OOM | 3947 | - | OOM | 61 | -
OPT-175B (8 GPUs)
1 | 512 | 426 | 359 |  1.19$\times$ | 44 | 23 |  1.87$\times$
1 | 1024 | 571 | 475 |  1.20$\times$ | 44 | 24 |  1.85$\times$
16 | 512 | 2212 | 1628 |  1.36$\times$ | 50 | 30 |  1.67$\times$
16 | 1024 | 4133 | 3231 |  1.28$\times$ | 56 | 37 |  1.52$\times$
Table 8: SmoothQuant can quantize MT-NLG 530B to W8A8 with negligible accuracy loss. | LAMBADA | HellaSwag | PIQA | WinoGrande | Average
---|---|---|---|---|---
FP16 | 76.6% | 62.1% | 81.0% | 72.9% | 73.1%
INT8 | 77.2% | 60.4% | 80.7% | 74.1% | 73.1%
Table 9: When serving MT-NLG 530B, SmoothQuant can reduce the memory by half at a similar latency using _half_ number of GPUs, which allows serving the 530B model within a single node. SeqLen | Prec. | #GPUs | Latency | Memory
---|---|---|---|---
128 | FP16 | 16 | 232ms | 1040GB
| INT8 | 8 | 253ms | 527GB
256 | FP16 | 16 | 451ms | 1054GB
| INT8 | 8 | 434ms | 533GB
512 | FP16 | 16 | 838ms | 1068GB
| INT8 | 8 | 839ms | 545GB
1024 | FP16 | 16 | 1707ms | 1095GB
| INT8 | 8 | 1689ms | 570GB

###  5.4 Scaling Up: 530B Model Within a Single Node

We can further scale up SmoothQuant beyond 500B-level models, enabling
efficient and accurate W8A8 quantization of MT-NLG 530B (Smith et al., 2022).
As shown in Table 8 and 9, SmoothQuant enables W8A8 quantization of the 530B
model at a negligible accuracy loss. The reduced model size allows us to serve
the model using half number of the GPUs (16 to 8) at a similar latency,
enabling the serving of a >500B model within a single node (8$\times$A100 80GB
GPUs).

Table 10: GPU Latency (ms) of different quantization schemes. The coarser the quantization scheme (from per-token to per-tensor, dynamic to static, O1 to O3, defined in Table 2), the lower the latency. SmoothQuant achieves lower latency compared to FP16 under all settings, while LLM.int8() is mostly slower. The batch size is 4. Model | OPT-13B | OPT-30B
---|---|---
Sequence Length | 256 | 512 | 256 | 512
FP16 | 152.6 | 296.3 | 343.0 | 659.9
LLM.int8() | 237.1 | 371.5 | 387.9 | 654.9
SmoothQuant-O1 | 124.5 | 243.3 | 246.7 | 490.7
SmoothQuant-O2 | 120.5 | 235.1 | 240.2 | 478.3
SmoothQuant-O3 | 112.1 | 223.1 | 227.6 | 458.4

###  5.5 Ablation Study

#### Quantization schemes.

Table 10 shows the inference latency of different quantization schemes based
on our PyTorch implementation. We can see that the coarser the quantization
granularity (from O1 to O3), the lower the latency. And static quantization
can significantly accelerate inference compared with dynamic quantization
because we no longer need to calculate the quantization step sizes at runtime.
SmoothQuant is faster than FP16 baseline under all settings, while LLM.int8()
is usually slower. We recommend using a coarser scheme if the accuracy
permits.

#### Migration strength.

We need to find a suitable migration strength $\alpha$ (see Equation 4) to
balance the quantization difficulty of weights and activations. We ablate the
effect of different $\alpha$’s on OPT-175B with LAMBADA in Figure 10. When
$\alpha$ is too small (<0.4), the activations are hard to quantize; when
$\alpha$ is too large (>0.6), the weights will be hard to quantize. Only when
we choose $\alpha$ from the sweet spot region (0.4-0.6) can we get small
quantization errors for both weights and activations, and maintain the model
performance after quantization.

Figure 10: A suitable migration strength $\alpha$ (sweet spot) makes both
activations and weights easy to quantize. If the $\alpha$ is too large,
weights will be hard to quantize; if too small, activations will be hard to
quantize.

##  6 Related Work

#### Large language models (LLMs).

Pre-trained language models have achieved remarkable performance on various
benchmarks by _scaling up_. GPT-3 (Brown et al., 2020b) is the first LLM
beyond 100B parameters and achieves impressive few-shot/zero-shot learning
results. Later works (Rae et al., 2021; Smith et al., 2022; Du et al., 2022;
Chowdhery et al., 2022) continue to push the frontier of scaling, going beyond
500B parameters. However, as the language model gets larger, serving such
models for inference becomes expensive and challenging. In this work, we show
that our proposed method can quantize the three largest, openly available
LLMs: OPT-175B (Zhang et al., 2022), BLOOM-176B (Scao et al., 2022) and
GLM-130B (Zeng et al., 2022), and even MT-NLG 530B (Smith et al., 2022) to
reduce the memory cost and accelerate inference.

#### Model quantization.

Quantization is an effective method for reducing the model size and
accelerating inference. It proves to be effective for various convolutional
neural works (CNNs) (Han et al., 2016; Jacob et al., 2018; Nagel et al., 2019;
Wang et al., 2019; Lin et al., 2020) and transformers (Shen et al., 2020; Kim
et al., 2021; Liu et al., 2021; Wang et al., 2020; Bondarenko et al., 2021).
Weight equalization (Nagel et al., 2019) and channel splitting (Zhao et al.,
2019) reduce quantization error by suppressing the outliers in weights.
However, these techniques cannot address the activation outliers, which are
the major quantization bottleneck for LLMs (Dettmers et al., 2022).

#### Quantization of LLMs.

GPTQ (Frantar et al., 2022) applies quantization only to weights but not
activations (please find a short discussion in Appendix A). ZeroQuant (Yao et
al., 2022) and nuQmm (Park et al., 2022) use a per-token and group-wise
quantization scheme for LLMs, which requires customized CUDA kernels. Their
largest evaluated models are 20B and 2.7B, respectively and fail to maintain
the performance of LLMs like OPT-175B. LLM.int8() (Dettmers et al., 2022) uses
mixed INT8/FP16 decomposition to address the activation outliers. However,
such implementation leads to large latency overhead, which can be even slower
than FP16 inference. Outlier Suppression (Wei et al., 2022) uses the non-
scaling LayerNorm and token-wise clipping to deal with the activation
outliers. However, it only succeeds on small language models such as BERT
(Devlin et al., 2019) and BART (Lewis et al., 2019) and fails to maintain the
accuracy for LLMs (Table 4). Our algorithm preserves the performance of LLMs
(up to 176B, the largest open-source LLM we can find) with an efficient per-
tensor, static quantization scheme without retraining, allowing us to use off-
the-shelf INT8 GEMM to achieve high hardware efficiency.

##  7 Conclusion

We propose SmoothQuant, an accurate and efficient post-training quantization
method to enable lossless 8-bit weight and activation quantization for LLMs up
to 530B parameters. SmoothQuant enables the quantization for both weight and
activations for all GEMMs in the LLMs, which significantly reduces the
inference latency and memory usage compared with the mixed-precision
activation quantization baseline. We integrate SmoothQuant into PyTorch and
FasterTransformer, getting up to 1.56$\times$ inference acceleration and
halving the memory footprint. SmoothQuant democratizes the application of LLMs
by offering a turnkey solution to reduce the serving cost.

## Acknowledgements

We thank MIT-IBM Watson AI Lab, MIT AI Hardware Program, Amazon and MIT
Science Hub, NVIDIA Academic Partnership Award, Qualcomm Innovation
Fellowship, Microsoft Turing Academic Program, and NSF for supporting this
research. We thank Haotian Tang, Aohan Zeng, Eric Lin and Jilei Hou for the
helpful discussions.

## References

  * Bisk et al. (2020) Bisk, Y., Zellers, R., Bras, R. L., Gao, J., and Choi, Y.  Piqa: Reasoning about physical commonsense in natural language.  In _Thirty-Fourth AAAI Conference on Artificial Intelligence_ , 2020\.
  * Bondarenko et al. (2021) Bondarenko, Y., Nagel, M., and Blankevoort, T.  Understanding and overcoming the challenges of efficient transformer quantization.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pp. 7947–7969, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.  URL https://aclanthology.org/2021.emnlp-main.627.
  * Brown et al. (2020a) Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D.  Language models are few-shot learners.  In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), _Advances in Neural Information Processing Systems_ , volume 33, pp. 1877–1901. Curran Associates, Inc., 2020a.  URL https://proceedings.neurips.cc/paper/2020/file/1457c0d6bfcb4967418bfb8ac142f64a-Paper.pdf.
  * Brown et al. (2020b) Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020b.
  * Chowdhery et al. (2022) Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., et al.  Palm: Scaling language modeling with pathways.  _arXiv preprint arXiv:2204.02311_ , 2022.
  * Dettmers et al. (2022) Dettmers, T., Lewis, M., Belkada, Y., and Zettlemoyer, L.  Llm.int8(): 8-bit matrix multiplication for transformers at scale.  _arXiv preprint arXiv:2208.07339_ , 2022.
  * Devlin et al. (2019) Devlin, J., Chang, M., Lee, K., and Toutanova, K.  BERT: pre-training of deep bidirectional transformers for language understanding.  In _NAACL-HLT 2019_ , pp. 4171–4186. Association for Computational Linguistics, 2019.
  * Du et al. (2022) Du, N., Huang, Y., Dai, A. M., Tong, S., Lepikhin, D., Xu, Y., Krikun, M., Zhou, Y., Yu, A. W., Firat, O., et al.  Glam: Efficient scaling of language models with mixture-of-experts.  In _International Conference on Machine Learning_ , pp. 5547–5569. PMLR, 2022.
  * Frantar et al. (2022) Frantar, E., Ashkboos, S., Hoefler, T., and Alistarh, D.  Gptq: Accurate post-training quantization for generative pre-trained transformers.  _arXiv preprint arXiv:2210.17323_ , 2022.
  * Gao et al. (2020) Gao, L., Biderman, S., Black, S., Golding, L., Hoppe, T., Foster, C., Phang, J., He, H., Thite, A., Nabeshima, N., et al.  The pile: An 800gb dataset of diverse text for language modeling.  _arXiv preprint arXiv:2101.00027_ , 2020.
  * Han et al. (2016) Han, S., Mao, H., and Dally, W. J.  Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding.  In _ICLR_ , 2016.
  * Hendrycks et al. (2020) Hendrycks, D., Burns, C., Basart, S., Zou, A., Mazeika, M., Song, D., and Steinhardt, J.  Measuring massive multitask language understanding.  _CoRR_ , abs/2009.03300, 2020.  URL https://arxiv.org/abs/2009.03300.
  * Jacob et al. (2018) Jacob, B., Kligys, S., Chen, B., Zhu, M., Tang, M., Howard, A., Adam, H., and Kalenichenko, D.  Quantization and training of neural networks for efficient integer-arithmetic-only inference.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 2704–2713, 2018.
  * Kim et al. (2021) Kim, S., Gholami, A., Yao, Z., Mahoney, M. W., and Keutzer, K.  I-bert: Integer-only bert quantization.  In _International conference on machine learning_ , pp. 5506–5518. PMLR, 2021.
  * Lewis et al. (2019) Lewis, M., Liu, Y., Goyal, N., Ghazvininejad, M., Mohamed, A., Levy, O., Stoyanov, V., and Zettlemoyer, L.  Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  _arXiv preprint arXiv:1910.13461_ , 2019.
  * Lin et al. (2020) Lin, J., Chen, W.-M., Lin, Y., Gan, C., Han, S., et al.  Mcunet: Tiny deep learning on iot devices.  _Advances in Neural Information Processing Systems_ , 33:11711–11722, 2020.
  * Liu et al. (2021) Liu, Z., Wang, Y., Han, K., Zhang, W., Ma, S., and Gao, W.  Post-training quantization for vision transformer.  _Advances in Neural Information Processing Systems_ , 34:28092–28103, 2021.
  * Merity et al. (2016) Merity, S., Xiong, C., Bradbury, J., and Socher, R.  Pointer sentinel mixture models, 2016.
  * Mihaylov et al. (2018) Mihaylov, T., Clark, P., Khot, T., and Sabharwal, A.  Can a suit of armor conduct electricity? a new dataset for open book question answering.  In _EMNLP_ , 2018.
  * Nagel et al. (2019) Nagel, M., Baalen, M. v., Blankevoort, T., and Welling, M.  Data-free quantization through weight equalization and bias correction.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pp. 1325–1334, 2019.
  * Paperno et al. (2016) Paperno, D., Kruszewski, G., Lazaridou, A., Pham, N. Q., Bernardi, R., Pezzelle, S., Baroni, M., Boleda, G., and Fernández, R.  The LAMBADA dataset: Word prediction requiring a broad discourse context.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 1525–1534, Berlin, Germany, August 2016. Association for Computational Linguistics.  doi: 10.18653/v1/P16-1144.  URL https://aclanthology.org/P16-1144.
  * Park et al. (2022) Park, G., Park, B., Kwon, S. J., Kim, B., Lee, Y., and Lee, D.  nuqmm: Quantized matmul for efficient inference of large-scale generative language models.  _arXiv preprint arXiv:2206.09557_ , 2022.
  * Pope et al. (2022) Pope, R., Douglas, S., Chowdhery, A., Devlin, J., Bradbury, J., Levskaya, A., Heek, J., Xiao, K., Agrawal, S., and Dean, J.  Efficiently scaling transformer inference.  _arXiv preprint arXiv:2211.05102_ , 2022.
  * Rae et al. (2021) Rae, J. W., Borgeaud, S., Cai, T., Millican, K., Hoffmann, J., Song, F., Aslanides, J., Henderson, S., Ring, R., Young, S., et al.  Scaling language models: Methods, analysis & insights from training gopher.  _arXiv preprint arXiv:2112.11446_ , 2021.
  * Roemmele et al. (2011) Roemmele, M., Bejan, C. A., and Gordon, A. S.  Choice of plausible alternatives: An evaluation of commonsense causal reasoning.  In _Logical Formalizations of Commonsense Reasoning, Papers from the 2011 AAAI Spring Symposium, Technical Report SS-11-06, Stanford, California, USA, March 21-23, 2011_. AAAI, 2011.  URL http://www.aaai.org/ocs/index.php/SSS/SSS11/paper/view/2418.
  * Sakaguchi et al. (2019) Sakaguchi, K., Bras, R. L., Bhagavatula, C., and Choi, Y.  Winogrande: An adversarial winograd schema challenge at scale.  _arXiv preprint arXiv:1907.10641_ , 2019.
  * Scao et al. (2022) Scao, T. L., Fan, A., Akiki, C., Pavlick, E., Ilić, S., Hesslow, D., Castagné, R., Luccioni, A. S., Yvon, F., Gallé, M., et al.  Bloom: A 176b-parameter open-access multilingual language model.  _arXiv preprint arXiv:2211.05100_ , 2022.
  * Shen et al. (2020) Shen, S., Dong, Z., Ye, J., Ma, L., Yao, Z., Gholami, A., Mahoney, M. W., and Keutzer, K.  Q-bert: Hessian based ultra low precision quantization of bert.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pp. 8815–8821, 2020.
  * Shoeybi et al. (2019) Shoeybi, M., Patwary, M., Puri, R., LeGresley, P., Casper, J., and Catanzaro, B.  Megatron-lm: Training multi-billion parameter language models using model parallelism.  _CoRR_ , abs/1909.08053, 2019.  URL http://arxiv.org/abs/1909.08053.
  * Smith et al. (2022) Smith, S., Patwary, M., Norick, B., LeGresley, P., Rajbhandari, S., Casper, J., Liu, Z., Prabhumoye, S., Zerveas, G., Korthikanti, V., et al.  Using deepspeed and megatron to train megatron-turing nlg 530b, a large-scale generative language model.  _arXiv preprint arXiv:2201.11990_ , 2022.
  * Touvron et al. (2023) Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., et al.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_ , 2023.
  * Vaswani et al. (2017) Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Wang et al. (2018) Wang, A., Singh, A., Michael, J., Hill, F., Levy, O., and Bowman, S. R.  GLUE: A multi-task benchmark and analysis platform for natural language understanding.  _CoRR_ , abs/1804.07461, 2018.  URL http://arxiv.org/abs/1804.07461.
  * Wang et al. (2020) Wang, H., Zhang, Z., and Han, S.  Spatten: Efficient sparse attention architecture with cascade token and head pruning.  _CoRR_ , abs/2012.09852, 2020.  URL https://arxiv.org/abs/2012.09852.
  * Wang et al. (2019) Wang, K., Liu, Z., Lin, Y., Lin, J., and Han, S.  HAQ: Hardware-Aware Automated Quantization with Mixed Precision.  In _CVPR_ , 2019.
  * Wei et al. (2022) Wei, X., Zhang, Y., Zhang, X., Gong, R., Zhang, S., Zhang, Q., Yu, F., and Liu, X.  Outlier suppression: Pushing the limit of low-bit transformer language models, 2022.  URL https://arxiv.org/abs/2209.13325.
  * Williams et al. (2018) Williams, A., Nangia, N., and Bowman, S.  A broad-coverage challenge corpus for sentence understanding through inference.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pp. 1112–1122. Association for Computational Linguistics, 2018.  URL http://aclweb.org/anthology/N18-1101.
  * Yao et al. (2022) Yao, Z., Aminabadi, R. Y., Zhang, M., Wu, X., Li, C., and He, Y.  Zeroquant: Efficient and affordable post-training quantization for large-scale transformers, 2022.  URL https://arxiv.org/abs/2206.01861.
  * Yu et al. (2022) Yu, G.-I., Jeong, J. S., Kim, G.-W., Kim, S., and Chun, B.-G.  Orca: A distributed serving system for $\\{$Transformer-Based$\\}$ generative models.  In _16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22)_ , pp. 521–538, 2022.
  * Zellers et al. (2019) Zellers, R., Holtzman, A., Bisk, Y., Farhadi, A., and Choi, Y.  Hellaswag: Can a machine really finish your sentence?  _CoRR_ , abs/1905.07830, 2019.  URL http://arxiv.org/abs/1905.07830.
  * Zeng et al. (2022) Zeng, A., Liu, X., Du, Z., Wang, Z., Lai, H., Ding, M., Yang, Z., Xu, Y., Zheng, W., Xia, X., et al.  Glm-130b: An open bilingual pre-trained model.  _arXiv preprint arXiv:2210.02414_ , 2022.
  * Zhang et al. (2022) Zhang, S., Roller, S., Goyal, N., Artetxe, M., Chen, M., Chen, S., Dewan, C., Diab, M., Li, X., Lin, X. V., Mihaylov, T., Ott, M., Shleifer, S., Shuster, K., Simig, D., Koura, P. S., Sridhar, A., Wang, T., and Zettlemoyer, L.  Opt: Open pre-trained transformer language models, 2022.  URL https://arxiv.org/abs/2205.01068.
  * Zhao et al. (2019) Zhao, R., Hu, Y., Dotzel, J., De Sa, C., and Zhang, Z.  Improving neural network quantization without retraining using outlier channel splitting.  In _International conference on machine learning_ , pp. 7543–7552. PMLR, 2019.

##  Appendix A Discussion on Weight-Only Quantization

In this work, we study W8A8 quantization so that we can utilize INT8 GEMM
kernels to increase the throughput and accelerate inference. There is another
line of work that only quantizes the weight of LLMs (e.g., GPTQ (Frantar et
al., 2022)). It converts the quantized weights to FP16 on the fly for matmul
during inference and can also lead to speed up due to the reduced data
loading, especially for the generation stage with batch size 1.

We mainly compare our method with existing work on weight-activation
quantization (i.e., W8A8) like (Dettmers et al., 2022; Yao et al., 2022; Wei
et al., 2022) since they are under the same setting. Here we would like to
give a short discussion about the weight-only quantization methods in LLM
settings:

  1. 1.

Firstly, we were trying to compare our method with GPTQ (Frantar et al., 2022)
but found it difficult due to different implementations. GPTQ’s low-bit kenerl
¶¶¶https://github.com/IST-DASLab/gptq only supports the generation stage with
batch size 1 (i.e., only processing a single token at a time), and cannot
support the context stage (widely used in different downstream tasks and
chatbot) or batch-based setting. Furthermore, its low-bit kernel optimization
only targets the OPT-175B model (as stated in the README). At the same time,
our work utilizes FasterTransformer for serving large models, which may lead
to an unfair advantage if we make a direct comparison.

  2. 2.

GPTQ may perform better at handling a small number of input tokens (1 in its
experiments) since the process is highly memory-bounded. In contrast,
SmoothQuant may serve better with a batching setting or for the context stage
(i.e., when the number of processed tokens is more significant). Nonetheless,
some work shows that in production, we can improve the throughput of serving
GPT models by 37$\times$ at similar latency with advanced batching (Yu et al.,
2022). We believe in production, batching will be the future standard, and
SmoothQuant will bring further improvement, even for the generation stage.

  3. 3.

Applications like chatbots need to handle a long context length and
potentially run under a batch setting. Due to the two factors, the memory size
of the KV cache can no longer be ignored (as shown in (Pope et al., 2022), the
KV cache totals 3TB given batch size 512 and context length 2048, which is
3$\times$ larger than the model weights). In this case, quantization of
activation can also help reduce the memory cost from storing the KV cache.

  4. 4.

Finally, we think the two settings are somewhat orthogonal. We believe we can
integrate GPTQ’s method for a better weight quantization and potentially
achieve W4A4 quantization, which will lead to even better hardware efficiency
(INT4 instructions are supported on NVIDIA’s Hopper GPU architecture). We
leave this exploration to future work.