#  lrsarith: a small fixed/hybrid arithmetic C library

David Avis
School of Informatics, Kyoto University, Kyoto, Japan and
School of Computer Science, McGill University, Montréal, Québec, Canada
Charles Jordan
Graduate School of Information Science and Technology, Hokkaido University,
Sapporo, Japan

###### Abstract

We describe lrsarith which is a small fixed precision and hybrid arithmetic C
library for integers and rationals that we developed for use in the lrslib
library for polyhedral computation. Using a generic set of operations, a
program can be compiled with either 64-bit or 128-bit (if available) fixed
precision, with an extended precision library such as GMP or the built-in MP
routines. A simple scheme checks for overflow and either terminates the
program or, in hybrid mode, changes to a higher precision arithmetic.
Implementing these arithmetics in lrslib resulted in only minimal changes to
the original code. We give computational results using lrs and mplrs,
vertex/facet enumeration codes in lrslib, using 64 and 128 bit fixed integer
arithmetic with and without overflow checking, GMP arithmetic, lrsarith hybrid
arithmetic with both GMP and MP, and FLINT hybrid arithmetic. We give a small
self-contained example C program using the lrsarith package in both fixed
precision and hybrid mode.

##  1 Introduction

When writing mathematical software, a fundamental choice is the arithmetic to
use. It is easy to be seduced by the performance of native integers, but the
possibility of incorrect output caused by overflow can be a major concern. To
guarantee correctness, in many cases one must rely on multiprecision
arithmetic such as that provided by the GNU Multiple Precision (GMP)
Arithmetic Library. This comes with a large performance penalty compared to
native integers on inputs where they suffice, and it’s tempting to maintain
multiple versions with different arithmetic.

Until version 7, this was the situation with lrslib, a library of programs for
polyhedral computation including e.g. lrs for vertex/facet enumeration and
redund for redundancy removal. From the outset lrslib used exact arithmetic
and could be compiled with either fixed precision C integer arithmetic
(without overflow checking) or with an internal extended precision arithmetic
library. For safety, the default was to use extended precision. Later versions
could also be compiled with the GMP package and more recently, with the hybrid
arithmetic package available in FLINT. The fixed precision versions perform
several times faster than the extended precision versions but can produce
incorrect results if overflow occurs.

For this reason we developed a simple scheme to detect the possibility of
overflow occurring while using fixed precision arithmetic. The code could then
halt and allow the user to restart using higher or extended precision
arithmetic. This led to the development of a hybrid scheme in lrslib to allow
automatic restart with the next higher precision arithmetic. This gives users
the performance of native arithmetic in most cases where it is safe, while
keeping the correctness provided by the extended precision versions. The
restart is from (very near) the point where a possible overflow was detected.
Implementing this in lrslib resulted in only minimal changes to the original
code and gives a significant performance improvement.

The main purpose of this paper is to explain how overflow checking and hybrid
arithmetic was implemented and to give numerical results for a case study
involving vertex/facet enumeration. This explains the improved performance of
lrslib 7 compared to previous versions. These techniques can be used in any C
code without requiring the full lrslib library, so we created the much
smaller, independent lrsarith package which contains only the arithmetic code.
It can be downloaded from [1].

Implementing arithmetic in lrsarith allows developers to postpone the choice
of arithmetic until compile time. With some additional effort to handle
overflows and restarting from intermediate points of the computation, it also
allows the developer to obtain the performance of native integers when they
suffice and the correctness of an extended precision library when required.

###  1.1 Related work

When comparing various codes for vertex/facet enumeration [2], we noted that
the hybrid arithmetic available in normaliz could give a large speedup for
certain inputs. The default in normaliz is to begin the computation in 64-bit
integers and to restart using GMP extended precision if overflow occurs.
However, the restart is from the beginning of the computation, which can hurt
performance on certain inputs where the repeated work is significant (see the
comparison in [2]).

The Fast Library for Number Theory (FLINT) [5] is a collection of modules that
support various arithmetic operations. In particular, we use the fmpz module
for extended precision arithmetic that balances “very efficient” performance
on small integers with performance similar to GMP for large integers. We will
compare lrsarith performance with FLINT in Section 4.4. Although FLINT is
easier to develop with since switching arithmetic is transparent to the user,
lrsarith can give higher performance on small integers. FLINT contains much
additional functionality beyond extended precision arithmetic, but usually
requires the user to install it.

Porta [4] is a collection of routines related to polytopes, including
vertex/facet enumeration. It supports both fixed precision and its own
multiprecision arithmetic and was included in the comparison [2] mentioned
earlier.

The standard general purpose library for extended precision arithmetic with
large integers is GMP111https://gmplib.org/. It is highly optimized for many
platforms and was the default in lrslib for some time. Historically, lrslib
used its own multiprecision arithmetic (MP) and this is still supported.
Comparisons are given in Section 4.4.

###  1.2 Organization of the paper

The paper contains two parts that can essentially be read independently. The
first part gives a detailed explanation of how we implement the various
arithmetics with a simple but complete example program that can be used as a
template for developing with lrsarith. In Section 2 we show how overflow
checking is implemented in our fixed precision lrslong library. We give a
simple example to show how a single C code can be compiled with 64-bit,
128-bit, MP or GMP arithmetic. In the first three cases the program terminates
when the possibility of overflow is detected. In Section 3 we continue the
example to show how a program can restart after overflow has been detected,
using the next level of arithmetic. This form of hybrid arithmetic is used in
lrslib. Computational results are presented in both sections for a larger
example involving Collatz sequences.

The second part of the paper begins in Section 4 where we present our case
study and give computational results comparing various arithmetic packages
that can be used in lrslib. These include fixed integer arithmetic with and
without overflow checking, GMP arithmetic, two versions of lrsarith hybrid
arithmetic and FLINT hybrid arithmetic.

##  2 Fixed arithmetic

###  2.1 Definitions and overflow handling

Arithmetic is handled in lrsarith by defining a generic integer type and a set
of generic operations. A generic integer a, integer vector v and integer
matrix A are defined

    lrs_mp a;     lrs_mp_vector v;    lrs_mp_matrix A;

allocated

    lrs_alloc_mp(a);     v=lrs_alloc_mp_vector(n);    A=lrs_alloc_mp_matrix(m,n);

and freed

    lrs_clear_mp(a);     lrs_clear_mp_vector(n);    lrs_clear_mp_matrix(m,n);

where m and n are the dimensions. The types are assigned at compile time
depending on the arithmetic used. For 64-bit and 128-bit integers they are
assigned to fixed length integers and for GMP arithmetic to the GMP integer
type:

    typedef long long lrs_mp[1];                /*  one long integer     */
    typedef __int128 lrs_mp[1];                 /*  one 128-bit integer  */
    typedef long long lrs_mp[MAX_DIGITS + 1];   /*  one MP integer       */
    typedef mpz_t lrs_mp;                       /*  one GMP integer      */

Operations using lrs_mp integers are written generically. Typical examples are
as follows where a,b,c,d,e are lrs_mp integers, i is a long long and the
equivalent C code is given in parentheses:

    itomp(i,a);           (a=i)
    copy(b,a);            (b=a)
    addint(a,b,c);        (c=a+b)
    mulint(a,b,c);        (c=a*b)
    divint(a,b,c);        (c=a/b a=a%b)
    linint(a, ka, b, kb); (a=a*ka+b*kb for ka, kb long long integers)
    qpiv(a,b,c,d,e);      (a=(a*b-c*d)/e  where the division is exact )

A small C program, fixed.c, using some of these operations is given in
Appendix A. It reads in an integer $k$ and attempts to repeatedly square it
six times. We will discuss the program later in this section. Generic
operations are either assigned at compile time by macros, for example:

    #define addint(a,b,c)         *(c) = *(a) + *(b)          /* 64-bit or 128-bit */
    #define addint(a,b,c)         mpz_add((c),(a),(b))        /* GMP               */

or by C code in the case of MP. In this way arithmetic operations are
essentially the same as using the underlying arithmetic package.

The problem is that overflow is not detected in 64-bit and 128-bit arithmetic.
We solve this problem by a technique we call lazy overflow handling. Using
very light extra computation we detect when it is possible that an overflow
may occur. Control is then given to an overflow handler that either halts
computation or restarts the program using arithmetic with higher precision.
While restarting from the beginning of execution is simplest, later we will
see options for restarting from intermediate checkpoints – allowing programs
to use faster arithmetic for initial portions of computations in some cases.

To incorporate lazy overflow handling we define some constants that depend on
the word size $W$ which is either 64 or 128 in lrsarith:

$\textsf{MAXDm}=\left\lfloor\sqrt{2^{W-1}-1}\right\rfloor~{}~{}~{}\textsf{MAXDl}=2^{W/2-1}-1~{}~{}~{}\textsf{MAXDa}=2^{W-2}-1$
(1)

MAXDa is the constant used in testing for overflow when using addition or
similar operations, MAXDl is used for linint and MAXDm is used for
multiplying. Three macros test whether the operands a and b are out of bounds:

    #define mpsafem(a,b)          *(a)> MAXDm ||*(b)> MAXDm ||*(a)<- MAXDm ||*(b)<- MAXDm
    #define mpsafel(a,b)          *(a)> MAXDl ||*(b)> MAXDl ||*(a)<- MAXDl ||*(b)<- MAXDl
    #define mpsafea(a,b)          *(a)> MAXDa ||*(b)> MAXDa ||*(a)<- MAXDa ||*(b)<- MAXDa

Using these macros we can write macros for the generic operations above as
follows:

    #define addint(a,b,c)      {if(mpsafea(a,b)) lrs_overflow(1); else *(c) = *(a) + *(b);}
    #define mulint(a,b,c)      {if(mpsafem(a,b)) lrs_overflow(1); else *(c) = *(a) * *(b);}
    #define divint(a,b,c)      {*(c) = *(a) / *(b); *(a) = *(a) % *(b);}
    #define linint(a,ka,b,kb)  {if(mpsafel(a,b)) lrs_overflow(1); else *(a)=*(a)*ka+*(b)*kb;}
    #define qpiv(a,b,c,d,e)    {if(mpsafel(a,b)|| mpsafel(c,d)) lrs_overflow(1);
                               else *(a) =(*(a) * *(b) - *(c) * *(d))/(*e);}

We claim that if the integer arithmetic would overflow then lrs_overflow is
called. Since we are using signed integer arithmetic this is equivalent to
proving that the result (and intermediate values) in each case is at most
$2^{W-1}-1$. Proceeding case by case:

  * •

addint($a,b,c$): $|a|,|b|\leq\textsf{MAXDa}$ and so $a+b\leq
2*(2^{W-2}-1)=2^{W-1}-2$ ;

  * •

mulint($a,b,c$): $|a|,|b|\leq\textsf{MAXDm}$ and so
$a*b\leq\left(\sqrt{2^{W-1}-1}\right)^{2}=2^{W-1}-1$ ;

  * •

linint($a,ka,b,kb$) $|a|,|b|,|ka|,|kb|\leq\textsf{MAXDl}$ and so

$~{}~{}~{}~{}~{}a*ka+b*kb\leq 2\,(2^{W/2-1}-1)^{2}=2^{W-1}-2^{W/2+1}+2$ .

Note that divint cannot overflow and that the analysis for qpiv is thus
essentially the same as for linint, proving the claim.

Rational arithmetic is handled in lrsarith in a very simple way by
representing the rational number $a/b$ by two lrs_mp integers a and b. The
operation

    reduce(a,b)

divides a and b by their greatest common divisor. Arithmetic operations for
rationals are based on the integer operations above. For example

    mulrat(a,b,c,d,e,f)        (e/f = a/b * c/d, with e/f reduced)

is implemented by

    mulint (a,c,e);
    mulint (b,d,f);
    reduce (e,f);

Overflow checking for rational arithmetic is inherited from the corresponding
integer arithmetic.

We now look more closely at the code fixed.c for iterated squaring given in
Listing 1 of Appendix A. Among the includes on lines 1–3 we have the lrsarith
header file. On lines 7–9 is the function lrs_overflow that handles overflow
processing. In this case it simply prints a message and halts the program. In
the main routine we see that two lrs_mp variables are declared. These are
allocated and cleared in lines 16 and 26. These are null operations for 64 or
128-bit arithmetic and MP but are needed in GMP. On line 15 we initialize the
arithmetic package. The next lines read an integer $k$ and attempt to
iteratively square it six times.

Using the makefile in Listing 2 we can compile fixed.c with each of the
arithmetic packages depending on the compiler switches used. For 64 or 128-bit
arithmetic the -DLRSLONG switch is set, with -DB128 also set for 128-bit
arithmetic. The -DSAFE switch enables overflow checking and handling as
described in this section. The files lrsarith.h and lrsarith.c use these
switches to ensure that the correct arithmetic files are included. Lines 2 and
3 produce the binaries fixed1 and fixed2. For illustrative purposes we also
compile without the -DSAFE switch obtaining fixed1n and fixed2n in lines 4 and
5. In this case no overflow checking is performed. With the -DMP switch set
the MP version is produced. Finally by setting the -DGMP switch we compile
with the external GMP library which must be preinstalled. For simplicity, we
assume that the necessary files are in standard locations otherwise the
locations need to be specified. We ran fixed1, fixed2, fixedmp and fixedgmp
with the input $k=5$ getting the following output, respectively:

     5 25 625 390625 152587890625  overflow detected:halting
     5 25 625 390625 152587890625 2328364365386962890625  overflow detected:halting
     5 25 625 390625 152587890625 23283064365386962890625 542101086242752217003726400434970855712890625
     5 25 625 390625 152587890625 23283064365386962890625 542101086242752217003726400434970855712890625

fixed1 can compute $5^{16}$ before overflowing and fixed2 can also compute
$5^{32}$. Both fixedmp and fixedgmp can compute $5^{64}$. Running fixed1n and
fixed2n with no overflow protection produces incorrect output. This can
observed by noting the three cases where the last digit is not 5:

     5 25 625 390625 152587890625 3273344365508751233 7942358959831785217
     5 25 625 390625 152587890625 23283064365386962890625 -30240059481632067979667719627811971327

###  2.2 Fixed precision performance

We briefly compare performance of the various fixed arithmetic packages in
order to evaluate the overhead used by overflow checking. While this can also
be seen in the more extended comparison done in Section 4, here we use a
simple code to further demonstrate the use of lrsarith.

We consider a problem that uses a great deal of relatively simple computations
and little output. The Collatz conjecture [6, 7] is a famous open problem in
number theory: given a number $k$, we replace $k$ by $3k+1$ if $k$ is odd and
by $k/2$ if it is even. The process continues in the same way and the question
is whether for every starting value, the sequence eventually reaches $1$.
There is a great deal of work [6, 7] on the conjecture and it has been [3]
verified222See also David Barina’s page on the current status:
https://pcbarina.fit.vutbr.cz/ for all $k<2^{68}$.

Our goal is to compare arithmetic packages and not to computationally verify
larger values, so we avoid techniques such as huge lookup tables for
simplicity. We consider the Collatz sequence from $k$ as a path from the
integer $k$ to the value one. The set of such paths defines an infinite tree
with root $k=1$ and the conjecture holds if all integers appear in the tree.
One way to make the tree finite is to give a parameter $\mathit{max}$ and
consider the tree of all paths to the root that do not contain an integer $k$
greater than $\mathit{max}$. This finite tree can be generated from the root
without using memory to store its nodes using the reverse search procedure.

We wrote a code coll 333coll is contained in lrsarith-010. to generate the
tree in this way. As long as $\mathit{max}<2^{63}/3$ the program will not
overflow in 64-bit arithmetic. Table 1 gives the running times444 _mai48_ : 2x
AMD EPYC7552 2.3GHz, 48 cores, 512 GB memory, CentOS 7.6, gcc 4.8.5 when the
various arithmetic packages are compiled with coll. The binary collflint uses
FLINT arithmetic (version 2.6.3) and the other binaries are labelled in the
same way as for fixed.c above.

$\mathit{max}$ | nodes | coll1 | coll1n | coll2 | coll2n | collgmp | collflint | collmp
---|---|---|---|---|---|---|---|---
$10^{8}$ | 39523168 | 0.70 | 0.60 | 5.20 | 4.63 | 9.20 | 7.24 | 7.19
$10^{9}$ | 395436300 | 6.50 | 5.79 | 54.37 | 48.40 | 91.87 | 72.26 | 72.35
$10^{10}$ | 3953296865 | 82.28 | 57.26 | 570.26 | 511.66 | 923.77 | 866.20 | 864.84

Table 1: Collatz tree generation: times in seconds Collatz tree (_mai48_)

The values in Table 1 are small enough to avoid overflows, but one can see
that overflow checking in lrslong results in only minor overhead. The relative
performance of the packages will vary between machines, mix of arithmetic
operations, compilers and versions of extended precision libraries; however,
these results give a sample of what can be obtained. It is also worth noting
that the multiprecision arithmetics are generally focused more on larger
operands. In any case, for this computation on this machine, 128-bit
arithmetic is roughly eight times slower than 64-bit arithmetic. FLINT
arithmetic is somewhat faster than GMP (version 6.0) but slower than the
dedicated fixed precision arithmetics. This is generally reasonable – FLINT
makes more effort to obtain good performance on small operands, however
lrsarith fixed arithmetic is essentially the same as using native arithmetic.

##  3 Hybrid arithmetic

The fixed arithmetic versions described in the previous section are very
simple to implement and easy to use, giving good performance for inputs that
do not require very long integers. If overflow occurs the user can manually
rerun the job with a higher precision arithmetic package. However, it is
certainly more convenient to automatically switch from one arithmetic to
another with higher precision when overflow could occur. In this section we
describe how this can be done using lrsarith, while making only minor
modifications to the original user code.

###  3.1 Combining fixed arithmetic packages

We illustrate our approach using the example program of the previous section
that reads an integer $k$ and successively squares it. The hybrid code is
shown in Appendix B. Lines 9–29 contain the function run that is essentially
the function main from Appendix A. Instead of reading the integer $k$, it is
passed to run as a parameter.

The major change is the use of setjmp to allow lrs_overflow to return control
to the program that calls run. This is achieved via the variable buf1 defined
on line 7\. The main loop (lines 18–25) of run is enclosed by a test on line
17. If lrs_overflow (lines 31–33) is called by the arithmetic package a long
jump is performed to the statement immediately after the end of the enclosed
loop, i.e. line 26. This prints a warning and returns to the routine that
called run.

In fact there are three routines that call run, namely run1, run2, and runmp
(GMP or MP), but only the first two can trigger a call to lrs_overflow. The
function run itself will need to be compiled three times, once for each
package. The arithmetic package used and the routine to call run are selected
at compile time by compiler directives in the makefile and on lines 35–43,
respectively. The problem now arises that since run will be compiled three
times the three versions will need different names, a process known as name
mangling. In fact all of the routines that use lrs_mp will also need name
mangling. The particular scheme used in lrsarith was suggested by David
Bremner and is illustrated in line 5. A unique suffix suf defined in the
arithmetic header file used is added to the function run. These define lines
will be needed for each user supplied routine. The define for lrs_overflow is
contained in lrslong.h.

Listing 5 contains the main program with its header file given in Listing 4.
It begins by reading the parameter $k$ and by calling run1 which uses 64-bit
arithmetic. If overflow occurs a return code of 1 is triggered by lrs_overflow
causing main to call run2 using 128-bit arithmetic. If this in turn overflows
a final call is made to runmp which uses GMP555For simplicity we have omitted
lines which produce a hybrid executable with MP, but they are in the lrsarith
makefile.. In the makefile given in Listing 6, lines 4–6 compile the
arithmetic libraries. Lines 7–9 compile hybridlib.c three times, once with
each arithmetic library. Finally line 11 combines everything into a single
executable hybrid. Running hybrid with $k=5$ produces:

     5 25 625 390625 152587890625  overflow detected:restarting
     5 25 625 390625 152587890625 2328364365386962890625  overflow detected:restarting
     5 25 625 390625 152587890625 23283064365386962890625 542101086242752217003726400434970855712890625

###  3.2 Hybrid performance

We continue the example of generating Collatz trees introduced in Section 2.2.
This time we use much larger values of $\mathit{max}$ in order to create
overflow conditions in both 64-bit and 128-bit arithmetic. As the trees now
become extremely large, we terminate the programs after $10^{8}$ nodes have
been generated. The program is deterministic so in each case the same nodes
are traversed. The program coll is the hybrid code combining coll1, coll2 and
collgmp created in the same way as hybrid described above.

The results are shown in Table 2. On each line the final arithmetic used in
coll is shown in blue. It is interesting to observe that for each of these
three runs collgmp runs in roughly the same time and that, for
$\mathit{max}=10^{32}$, this is faster than the 128-bit arithmetic coll2 (and
hence coll).

$\mathit{max}$ | coll | coll1 | coll2 | collgmp | collmp | collflint
---|---|---|---|---|---|---
| (hybrid) |  |  |  |  | (hybrid)
$10^{16}$ | 1.67 | 1.70 | 18.60 | 24.43 | 22.93 | 24.85
$10^{32}$ | 36.21 | (o) | 36.17 | 24.15 | 34.10 | 34.04
$10^{48}$ | 25.59 | (o) | (o) | 24.66 | 45.83 | 45.97

  * 1

(o)=possible overflow detected

Table 2: Collatz tree generation: $10^{8}$ nodes, times in seconds (_mai48_)

The simple scheme described in this section will be adequate in many
applications but has a number of disadvantages. First, memory allocated during
the run for a given arithmetic may not be freed after an overflow occurs,
causing a memory leak. More importantly, the simple scheme here restarts from
the start of program execution. Forgetting the past can be helpful but this
can hurt performance if overflow occurs near the end of program execution. It
would be much better to not redo work that has already been done, especially
with slower arithmetic.

In applications such as lrslib, these are serious issues. The definition of
lrs_mp depends on the arithmetic, so offsets into structures containing lrs_mp
can change after switching arithmetic. Handling overflows appropriately is
therefore more complicated than simply forgetting the past and restarting, as
was described here.

The solution used in lrslib was to use a global variable to point to the
allocated data structures. This allows lrs_overflow to free the data after
overflow is detected, before switching to the next arithmetic. A further
improvement in lrslib was to allow the program to restart at the point in the
calculation where the overflow was detected. Again this was done using a
global variable and also the ability of the original code to restart.
Fortunately this was already available. In other programs, it may be necessary
to add periodic checkpoints and it can be helpful to separate structures that
contain lrs_mp from those that don’t.

##  4 Vertex/facet enumeration problems

When comparing [2] various codes for vertex/facet enumeration, we noted that
hybrid arithmetic could give a large speedup for certain inputs, but that this
was not available in lrslib at the time. We now turn our attention to the
original motivation for developing the hybrid version of lrsarith: obtaining
these speedups in lrslib v. 7.

We begin by introducing the basics of vertex and facet enumeration. Then, we
explain the parallel hybrid version mplrs, since this handles overflow
somewhat differently than hybrid lrs. In Section 4.3 we describe the
experimental setup and in Section 4.4 we present a comparison between the
different arithmetic packages as used in lrs and mplrs.

###  4.1 Background

A convex polyhedron $P$ can be represented by either a list of vertices and
extreme rays, called a V-representation, or a list of its facet defining
inequalities, called an H-representation. The vertex enumeration problem is to
convert an H-representation to a V-representation. The computationally
equivalent facet enumeration problem performs the reverse transformation. For
further background see Ziegler [8]. We will use the lrs program in lrslib to
experiment with various instances of these problems. A comparison with other
codes including mplrs, a parallel version of lrs, to solve these problems can
be found in [2].

The input is represented by an $m$ by $n$ matrix. For a vertex enumeration
problem this is a list of $m$ inequalities in $n-1$ variables whose
intersection define $P$. A vertex (resp. extreme ray) is the intersection of a
set of $n-1$ (resp. $n-2$) input inequalities, taken as equations, that
satisfies the remaining inequalities. A major difficulty is caused by
degeneracy which occurs when more than $n-1$ inequalities intersect at a
vertex. In this case lrs generates multiple representations of the vertex,
known as bases. For a facet enumeration problem the input is a list of the
vertices of $P$ each beginning with a 1 in column one666Extreme rays would be
indicated by a zero in column one.. A facet is defined by a set of $n-1$ input
vertices which span a hyperplane for which all of the other input vertices lie
on one side. Here degeneracy is manifested when more than $n-1$ vertices lie
on the hyperplane. Again lrs will generate the facet multiple times, each
known as a basis. When degeneracy occurs the vertex or facet is output when
the index-wise lexicographically minimum basis is found.

###  4.2 Hybrid mplrs

On detecting a possible overflow, the hybrid version of lrs switches to the
next highest precision arithmetic package which it uses from that point
onwards. The sequential implementation was parallelized as mplrs [2] which
dynamically partitions the work and provides a series of subproblems to
multiple lrs workers.

If each of these workers was a hybrid lrs process, it would start each problem
with the fastest arithmetic and switch to higher precision when detecting a
possible overflow. This has a few drawbacks;

  1. 1.

Duplicate output: it’s possible that when restarting after an overflow, we
reprint the most recent line of output.

  2. 2.

Performance: if overflow occurs, it usually occurs often in the run (ie not
infrequently). There is overhead in restarting and switching arithmetic and so
we would prefer to avoid frequent switches.

In the hybrid version of mplrs, each of the workers is a fixed arithmetic
process that returns to mplrs when possible overflow is detected. At that
point, mplrs re-initializes the worker in question using the next available
arithmetic. All output produced by the subproblem is discarded and the worker
restarts from the beginning (of the subproblem). The worker uses the new
arithmetic from that point onwards.

This approach avoids duplicate output: by default, hybrid mplrs holds output
produced by the worker if the arithmetic could overflow, flushing it only when
the job ends. It also resolves the second problem; each worker can only
overflow and switch arithmetic twice in the overall run – the same as hybrid
lrs. In addition, if overflow is a rare event then it is possible for only
some workers to overflow. This makes larger speedups possible comparable to
hybrid lrs.

There is overhead in two areas. First, when overflow is detected the worker
restarts its job. This overhead is limited because jobs are usually very
small777See e.g., Figure 3(c,d) in [2]. and workers can only overflow at most
twice during the run. Next, since mplrs traverses different parts of the
reverse search tree in a different order compared to lrs, it’s possible for
overflow to occur earlier than it would in lrs. This could hurt performance if
lrs overflows only at the end but could also help performance by avoiding
early lrs overflows.

One complication is that for volume computation, mplrs internally uses the
maximum precision arithmetic available. This means that mplrs may not agree
with the worker process on arithmetic. Communication between the worker
process and mplrs therefore avoids using lrs_mp integers.

After checkpointing and restarting, hybrid mplrs begins again with the fastest
arithmetic available. Checkpoint files are compatible between the various
arithmetic packages.

###  4.3 Experimental setup

The polytopes we tested are described in Table 3 and, except for two new
problems, were previously described and used in [2]. The problems range from
non-degenerate to highly degenerate polyhedra. This table includes the results
of an lrs run on each polytope as lrs gives the number of bases in a symbolic
perturbation of the polytope. The new problems are:

  * •

_cp7_ is the cut polytope for 7 points which has input coefficients 0 or 1 and
is highly degenerate.

  * •

_p8-6_ is related to the holographic cone studied in physics and is an
extension of the eight point cut polytope. Input coordinates are 0, 1 or -1
and it is the most degenerate problem studied.

We include a column labelled degeneracy which is the number of bases divided
by the number of vertices (or facets) output, rounded to the nearest integer.
We have sorted the table in order of increasing degeneracy. The horizontal
line separates the non-degenerate from the degenerate problems. The
corresponding input files are available by following the download link at [1].
Note that the input sizes are small, roughly comparable and much smaller than
the output sizes.

Name | Input | Output | lrs
---|---|---|---
| H/V | $m$ | $n$ | size | V/H | size | bases | secs | depth | degeneracy
_c30_ | V | 30 | 16 | 4.7K | 341088 | 73.8M | 319770 | 36 | 14 | 1
_c40_ | V | 40 | 21 | 12K | 40060020 | 15.6G | 20030010 | 7531 | 19 | 1
_km22_ | H | 44 | 23 | 4.8K | 4194304 | 1.2G | 4194304 | 234 | 22 | 1
_perm10_ | H | 1023 | 11 | 29K | 3628800 | 127M | 3628800 | 283 | 45 | 1
_vf500_ | V | 500 | 7 | 98K | 56669 | 38M | 202985 | 137 | 41 | 4
_vf900_ | V | 900 | 7 | 20K | 55903 | 3.9M | 264385 | 23 | 45 | 5
_mit71_ | H | 71 | 61 | 9.5K | 3149579 | 1.1G | 57613364 | 15474 | 20 | 18
_fq48_ | H | 48 | 19 | 2.1K | 119184 | 8.7M | 7843390 | 44 | 24 | 66
_mit_ | H | 729 | 9 | 21K | 4862 | 196K | 1375608 | 132 | 101 | 283
_cp7_ | V | 64 | 22 | 3K | 116764 | 7.4M | 308644212 | 4071 | 41 | 2643
_bv7_ | H | 69 | 57 | 8.1K | 5040 | 867K | 84707280 | 1256 | 17 | 16807
_p8-6_ | H | 154 | 92 | 36K | 4452 | 1.2M | 110640628 | 16152 | 63 | 24852

Table 3: Polytopes tested and lrs v. 7.1 times (_mai48_)

###  4.4 Comparison of arithmetic packages

In this section we give numerical results on using lrslib to solve the vertex
enumeration problems described in the previous section with the various
arithmetic packages in lrsarith. We test the following suite of codes, which
apart from the exception noted below, are available in lrslib v. 7.1:

  * •

lrs1: 64-bit fixed arithmetic with overflow checking.

  * •

lrs2: 128-bit fixed arithmetic with overflow checking.

  * •

lrsgmp: GMP arithmetic (version 6.0). Comparable to default lrs v. 6.2 and
earlier.

  * •

lrs: lrsarith hybrid arithmetic. Starts with lrs1 and switches to lrs2 (if
available) and finally lrsgmp. Default version of lrs.

  * •

lrsMP 888Available in v. 7.2 or on request.: As lrs except in the final step
internal MP arithmetic is used.

  * •

lrsflint: FLINT hybrid arithmetic (version 2.6.3).

  * •

mplrsgmp: Multi-core version of lrsgmp, comparable to default mplrs v. 6.2 and
earlier.

  * •

mplrs: Hybrid multi-core version of lrs. Default version of mplrs.

Also available in lrslib v. 7.1 are the parallel versions mplrs1, mplrs2, and
mplrsflint of the corresponding lrs codes above.

Name | Single Arithmetic | Hybrid Arithmetic | 40 cores
---|---|---|---
| lrs1 | lrs2 | lrsgmp | lrs | lrsMP | lrsflint | mplrsgmp | mplrs
_c30_ | (o) | (o) | 36 | 36 | 295 | 42 | 2 | 3
_c40_ | (o) | (o) | 7707 | 7581 | 97532 | 8341 | 402 | 389
_km22_ | (o) | (o) | 237 | 234 | 384 | 187 | 8 | 8
_perm10_ | 288 | 538 | 2429 | 283 | 284 | 1120 | 113 | 16
_vf500_ | (o) | (o) | 139 | 137 | 1658 | 163 | 12 | 11
_vf900_ | (o) | 23 | 103 | 23 | 23 | 170 | 8 | 2
_mit71_ | (o) | (o) | 15489 | 15474 | 110467 | 26432 | 731 | 723
_fq48_ | 44 | 77 | 265 | 44 | 44 | 147 | 11 | 1
_mit_ | (o) | 134 | 563 | 132 | 131 | 270 | 27 | 7
_cp7_ | 4105 | 6824 | 25030 | 4071 | 4039 | 14413 | 1141 | 191
_bv7_ | 1276 | 2346 | 7981 | 1256 | 1252 | 4874 | 357 | 65
_p8-6_ | 16197 | 23271 | 56519 | 16152 | 15970 | 45838 | 2395 | 661

  * 1

(o)=possible overflow detected

Table 4: Comparison of running times for various types of arithmetic, lrslib
v. 7.1 (_mai48_)

The results of the tests are shown in Table 4. The programs lrs1 and lrs2
either produce the correct output or indicate that an overflow may occur (o)
and terminate. The columns lrs and lrsMP give the running times for the hybrid
versions. When 64 or 128-bit arithmetic suffices these two running times are
essentially the same. When extended precision is required the internal MP
arithmetic may be much slower than GMP, especially for _c40_ , which requires
459 decimal digits. The final two columns show the speedups obtained by using
the multicore versions mplrs and mplrsgmp with 40 processors available.

In the table we show in blue which arithmetic version was in use when lrs,
shown in red, terminated. As to be expected lrs performs roughly the same as
lrsgmp when the integers become too large for fixed precision. Speedups of 2–4
times are observed for the combinatorial problems which can be solved using
only 64 or 128 bits. In general lrsflint did not perform as well as lrs but it
is usually faster than lrsgmp on the combinatorial problems. The approach used
in lrsarith hybrid arithmetic allows it to obtain essentially native integer
performance, but requires effort from the developer to handle overflow. FLINT
is easier for the developer but did not achieve the same performance when all
values are small. Another possible reason for the lack of performance is that
we did not use FLINT matrices as this would have required substantial
reprogramming of lrs.

We can observe that 128-bit arithmetic runs roughly 1.5–2 times slower than
64-bit arithmetic, when 64-bit arithmetic suffices. Hence there is a strong
incentive to start the computation with 64 bits using 128 bits only when
necessary. This latter outcome occurred for _mit_ and _vf900_.

##  5 Conclusion

We introduced lrsarith which is a small C library for performing fixed
precision arithmetic on integers and rationals with overflow protection and
allows hybrid arithmetic. It was developed as part of the lrslib polyhedral
computation package. However, due to its small size and ease of use we decided
to release it as an independent package. The details of the method used and
small examples were given in the first part of the paper.

In the second part we gave computational results for some vertex enumeration
problems. The examples show the diversity of such problems and this is
reflected in the arithmetic precision required to solve them. Many
combinatorial polytopes involve calculations that can be completed without
overflow using 64 (or 128) bit integers. Using fixed arithmetic with overflow
checking or hybrid arithmetic, speedups of 2–4 times can be achieved and these
carry over to parallel implementations. The new hybrid version described here
explains the performance improvements found in lrslib version 7 relative to
previous versions or earlier comparisons [2].

## Acknowledgements

We thank David Bremner for many helpful discussions and in particular for the
elegant implementation of name mangling. This work was partially supported by
JSPS Kakenhi Grants 16H02785, 18H05291, 18K18027, 20H00579, 20H00595 .

## References

  * [1] D. Avis.  http://cgm.cs.mcgill.ca/~avis/C/lrs.html.
  * [2] David Avis and Charles Jordan.  mplrs: A scalable parallel vertex/facet enumeration code.  Mathematical Programming Computation, 10(2):267–302, 2018.
  * [3] David Barina.  Convergence verification of the Collatz problem.  The Journal of Supercomputing, 2020.
  * [4] T. Christof and A. Loebel.  http://porta.zib.de.
  * [5] William B. Hart.  Fast library for number theory: an introduction.  In Mathematical Software – ICMS 2010, volume 6327 of Lecture Notes in Computer Science, pages 88–91, 2010.
  * [6] Jeffrey C. Lagarias.  The $3x+1$ problem: An annotated bibliography (1963–1999) (sorted by author).  arXiv:math/0309224, 2003.
  * [7] Jeffrey C. Lagarias.  The $3x+1$ problem: An annotated bibliography, II (2000-2009).  arXiv:math/0608208, 2006.
  * [8] Günter M. Ziegler.  Lectures on polytopes.  Springer, 1995.

##  Appendix A Single arithmetic code for repeated squaring

Listing 1: fixed.c

⬇

3#include <stdio.h>

4#include <stdlib.h>

5#include ”lrsarith.h”

6

7FILE *lrs_ifp,*lrs_ofp;

8

9void lrs_overflow(int parm){

10 fprintf(lrs_ofp,” overflow detected:halting\n”);

11 exit (1);

12}

13

14int main (void){

15 long i,k;

16 lrs_mp a,b;

17 lrs_mp_init(10,stdin,stdout);

18 lrs_alloc_mp(a); lrs_alloc_mp(b);

19 fscanf(lrs_ifp,”%ld”,&k);

20 itomp(k,b);

21 pmp(””,b);

22 for(i=1;i<=6;i++)

23 {

24 copy(a,b);

25 mulint(a,a,b);

26 pmp(””,b);

27 }

28 lrs_clear_mp(a); lrs_clear_mp(b);

29 fprintf(lrs_ofp,”\n”);

30 return 0;

31}

Listing 2: makefile

⬇

16fixed: fixed.c lrsarith.c lrsarith.h lrslong.c lrslong.h lrsgmp.c lrsgmp.h
lrsmp.c lrsmp.h

17 $(CC) -DLRSLONG -DSAFE -o fixed1 lrsarith.c fixed.c

18 $(CC) -DLRSLONG -DB128 -DSAFE -o fixed2 lrsarith.c fixed.c

19 $(CC) -DLRSLONG -o fixed1n lrsarith.c fixed.c

20 $(CC) -DLRSLONG -DB128 -o fixed2n lrsarith.c fixed.c

21 $(CC) -DMP -o fixedmp lrsarith.c fixed.c

22 $(CC) -DGMP -o fixedgmp lrsarith.c fixed.c -lgmp

##  Appendix B Hybrid arithmetic code for repeated squaring

Listing 3: hybridlib.c

⬇

4#include <stdio.h>

5#include <stdlib.h>

6#include <setjmp.h>

7#include ”lrsarith.h”

8#define run suf(run)

9

10static jmp_buf buf1; /* return location when overflowing */

11

12int run(long k){

13 long i;

14 lrs_mp a,b;

15 lrs_mp_init(0,stdin,stdout);

16 lrs_alloc_mp(a); lrs_alloc_mp(b);

17 itomp(k,b);

18 pmp(””,b);

19

20 if (!setjmp(buf1)){ /* overflow test */

21 for(i=1;i<=6;i++){

22 copy(a,b);

23 mulint(a,a,b);

24 pmp(””,b);

25 }

26 lrs_clear_mp(a); lrs_clear_mp(b);

27 return 0;

28 }

29 printf(” overflow detected:restarting\n”);

30 lrs_clear_mp(a); lrs_clear_mp(b);

31 return 1;

32}

33

34void lrs_overflow(int parm){

35 longjmp(buf1,1);

36}

37

38#if defined(MA) && defined(LRSLONG)

39#ifdef B128

40int run2(long k){ /* 128 bit */

41#else

42int run1(long k){ /* 64 bit */

43#endif

44#else

45int runmp(long k){ /* other arithmetic */

46#endif

47

48 return(run(k));

49}

Listing 4: hybrid.h

⬇

4#include <stdio.h>

5#include <stdlib.h>

6

7FILE *lrs_ifp; /* input file pointer */

8FILE *lrs_ofp; /* output file pointer */

9

10int run1(long k);

11int run2(long k);

12int runmp(long k);

Listing 5: hybrid.c

⬇

3int main (void) {

4long k;

5

6scanf(”%ld”,&k);

7

8if(run1(k)) /* TRUE on 64 bit overflow */

9 if(run2(k)) /* TRUE on 128 bit overflow */

10 runmp(k);

11

12printf(”\n”);

13return 0;

14}

Listing 6: makefile

⬇

3HOBJ=lrslong1.o hybridlib1.o lrslong2.o lrsgmp.o hybridlib2.o hybridlibgmp.o

4

5hybrid: hybrid.c lrslong.c lrslong.h lrsgmp.c lrsgmp.h hybridlib.c hybrid.h
lrsarith.c

6 $(CC) -DMA -DSAFE -DLRSLONG -c -o lrslong1.o lrsarith.c

7 $(CC) -DMA -DB128 -DSAFE -DLRSLONG -c -o lrslong2.o lrsarith.c

8 $(CC) -DMA -DGMP -c -o lrsgmp.o lrsarith.c

9 $(CC) -DMA -DSAFE -DLRSLONG -c -o hybridlib1.o hybridlib.c

10 $(CC) -DMA -DB128 -DSAFE -DLRSLONG -c -o hybridlib2.o hybridlib.c

11 $(CC) -DMA -DGMP -c -o hybridlibgmp.o hybridlib.c

12

13 $(CC) -DMA -DLRSLONG -DSAFE -o hybrid ${HOBJ} hybrid.c -lgmp


# MixMAE: Mixed and Masked Autoencoder for Efficient Pretraining of
Hierarchical Vision Transformers

Jihao Liu1,2 Xin Huang2 Jinliang Zheng2 Yu Liu2 ✉ Hongsheng Li1,3
1 CUHK MMLab
2 SenseTime Research
3 CPII under InnoHK

###### Abstract

In this paper, we propose Mixed and Masked AutoEncoder (MixMAE), a simple but
efficient pretraining method that is applicable to various hierarchical Vision
Transformers. Existing masked image modeling (MIM) methods for hierarchical
Vision Transformers replace a random subset of input tokens with a special
$\mathrm{[MASK]}$ symbol and aim at reconstructing original image tokens from
the corrupted image. However, we find that using the $\mathrm{[MASK]}$ symbol
greatly slows down the training and causes pretraining-finetuning
inconsistency, due to the large masking ratio (e.g., 60% in SimMIM). On the
other hand, MAE does not introduce $\mathrm{[MASK]}$ tokens at its encoder at
all but is not applicable for hierarchical Vision Transformers. To solve the
issue and accelerate the pretraining of hierarchical models, we replace the
masked tokens of one image with visible tokens of another image, i.e.,
creating a mixed image. We then conduct dual reconstruction to reconstruct the
two original images from the mixed input, which significantly improves
efficiency. While MixMAE can be applied to various hierarchical Transformers,
this paper explores using Swin Transformer with a large window size and scales
up to huge model size (to reach 600M parameters). Empirical results
demonstrate that MixMAE can learn high-quality visual representations
efficiently. Notably, MixMAE with Swin-B/W14 achieves 85.1% top-1 accuracy on
ImageNet-1K by pretraining for 600 epochs. Besides, its transfer performances
on the other 6 datasets show that MixMAE has better FLOPs / performance
tradeoff than previous popular MIM methods. Code is available at
https://github.com/Sense-X/MixMIM.

00footnotetext: ✉ Corresponding author.

##  1 Introduction

Utilizing unlabeled visual data in self-supervised manners to learn
representations is intriguing but challenging. Following BERT [14] in natural
language processing, pretraining with masked image modeling (MIM) shows great
success in learning visual representations for various downstream vision tasks
[21, 4, 51, 50, 44], including image classification [13], object detection
[31], semantic segmentation [56], video classification [20], and motor control
[50]. While those state-of-the-art methods [4, 21] achieved superior
performance on vanilla Vision Transformer (ViT) [16, 45], it is still an open
question that how to effectively pretrain hierarchical ViT to purchase further
efficiencies [36, 46, 9, 33, 12] on broad vision tasks.

In general, existing MIM approaches replace a portion of input tokens with a
special $\mathrm{[MASK]}$ symbol and aim at recovering the original image
patches [4, 51]. However, using $\mathrm{[MASK]}$ symbol leads to two
problems. On the one hand, the $\mathrm{[MASK]}$ symbol used in pretraining
never appears in the finetuning stage, resulting in pretraining-finetuning
inconsistency [14]. On the other hand, the pretrained networks waste much
computation on processing the less informative $\mathrm{[MASK]}$ symbols,
making the pretraining process inefficient. Those problems become severer when
a large masking ratio is used [21, 51, 4, 44]. For example, in SimMIM [51], a
masking ratio of 60% is used during the pretraining, i.e., 60% of the input
tokens are replaced with the $\mathrm{[MASK]}$ symbols. As a result, SimMIM
needs relatively more epochs (i.e., 800) for pretraining. In addition, as the
high masking ratio causes much pretraining-finetuning inconsistency, the
performances of SimMIM on downstream tasks are limited.

In contrast, MAE [21] does not suffer from the above problems by discarding
the masked tokens in the encoder and uses the $\mathrm{[MASK]}$ symbols only
in the lightweight decoder. MAE utilizes the vanilla ViT [16] as the encoder,
which can process the partial input efficiently with the self-attention
operation. However, the design also limits the application of MAE on
hierarchical ViTs as the hierarchical ViTs cannot process 1D token sequences
with arbitrary lengths [36, 46].

In this work, we propose MixMAE, a generalized pretraining method that takes
advantage of both SimMIM [51] and MAE [51] while avoiding their limitations.
In particular, given two random images from the training set, MixMAE creates a
mixed image with random mixing masks as input and trains a hierarchical ViT to
reconstruct the two original images to learn visual representations. From one
image’s perspective, instead of replacing the masked tokens of the image with
the special $\mathrm{[MASK]}$ symbols, the masked tokens are replaced by
visible tokens of the other image. MixMAE adopts an encoder-decoder design.
The encoder is a hierarchical ViT and processes the mixed image to obtain
hidden representations of the two partially masked images. Before the
decoding, the hidden representations are unmixed and filled with the
$\mathrm{[MASK]}$ tokens. Following MAE [21], the decoder is a small ViT to
reconstruct the two original images. We illustrate the proposed MixMAE in
Figure 1.

Approach |  Compatible with hierarchical ViT |  Pretraining efficient |  Pretrain-finetune consistent
---|---|---|---
BEiT [4] | ✓ | ✗ | ✗
SimMIM [51] | ✓ | ✗ | ✗
MAE [21] | ✗ | ✓ | ✓
MixMAE | ✓ | ✓ | ✓

Table 1: Key differences between MixMAE and related works.

MixMAE can be widely applied to pretrain different hierarchical ViTs, such as
Swin Transformer [36], Twins [9], PVT [46], etc. Thanks to the utilization of
the hierarchical architecture, we can naturally apply the pretrained encoder
to object detection and semantic segmentation tasks. Empirically, with similar
model sizes and FLOPs, MixMAE consistently outperforms BEiT [4] and MAE [21]
on a wide spectrum of downstream tasks, including image classification on
iNaturalist [23] and Places [55], object detection and instance segmentation
on COCO [31], and semantic segmentation on ADE20K [56]. By abandoning using
$\mathrm{[MASK]}$ tokens in the encoder, MixMAE shows much better pretraining
efficiency than SimMIM [51] on various hierarchical ViTs [36, 46, 9].

##  2 Related Works

Inspired by BERT [14] for Masked Language Modeling, Masked Image Modeling
(MIM) becomes a popular pretext task for visual representation learning [4,
21, 2]. MIM aims to reconstruct the masked tokens from a corrupted input.
Current MIM approaches can be divided into two categories by the
reconstruction targets. SimMIM [51] points out that raw pixel values of the
randomly masked patches are a good reconstruction target and a lightweight
prediction head is sufficient for pretraining. Different from SimMIM, MAE [21]
only takes the visible patches as the input of the encoder. Mask tokens are
added in the middle of the encoder and the decoder. Such an asymmetric design
greatly reduces the computation overhead of the encoder. To further enhance
the feature extraction capability of the encoder, CAE [7] separates the
encoder and decoder explicitly by adding a feature alignment module in the
middle of them. Jean-Baptiste et al. [1] propose to learn representations by
reconstructing original videos from synthetically mixed ones.

Instead of building the reconstruction target manually, using a network to
generate the reconstruction target has also been widely applied. In such
works, an image tokenizer is used to transform an image into visual tokens.
BEiT [4] utilizes a pretrained discrete VAE (dVAE) [41, 40] as the tokenizer.
However, the originally used MSE loss in dVAE is insufficient to force the
tokenizer to capture high-level semantics. PeCo [15] proposed to apply
perceptual similarity loss on the training of dVAE can drive the tokenizer to
generate better semantic visual tokens, which helps pretraining. Moreover, the
tokenizer in BEiT [4] needs to be offline pretrained, which limits the model’s
adaption ability. To address the problem, iBOT [57] proposed to use an online
tokenizer to generate the visual tokens.

There are also concurrent works that explore using MAE on hierarchical Vision
Transformers. UM-MAE [28] proposed a new masking strategy for adapting MAE to
pretrain pyramid-based ViTs (e.g., PVT [46], Swin [36]). GreenMIM [25] also
adapt MAE on hierarchical architectures. It partitions the local windows into
several equal-sized groups and proposes an optimal grouping algorithm to find
the optimal group size. Instead of designing specific masking or grouping
strategies, we focus on rearranging the inputs and targets. Empirical
evaluation shows that MixMAE can obtain better performance with various
hierarchical architectures.

Our MixMAE is also motivated by other mixing-based training techniques [52,
54, 34]. In contrast to those works which conduct data augmentation for
supervised learning, MixMAE can effectively pretrain hierarchical transformers
without human annotations.

Figure 1:  Overview of MixMAE. For pretraining, two images are mixed with a
random mixing mask to create a mixed image. MixMAE takes the mixed image as
input and reconstructs the two original images. Right before decoding, the
token embeddings are unmixed and filled with mask tokens for dual
reconstruction of the two original images.

##  3 Methodology

In this section, we introduce the proposed MixMAE for learning visual
representations via Masked Image Modeling (MIM). We start by briefly
revisiting MIM, and then introduce how MixMAE creates training inputs and
performs image reconstruction, as well as the hierarchical Transformer
architecture. Finally, we present how to reduce the difficulty of the pretext
task to improve the pretraining efficiency.

###  3.1 A Revisit of Masked Image Modeling

Following BERT [14], recent works [4, 21, 51] proposed MIM for learning visual
representations. Given an input image $x$, MIM firstly divides the image into
non-overlapping image patches $x^{p}$, following ViT [16]. It then samples a
random mask $M$ to mask a portion of the image patches, and fills the masked
place with a special symbol $\mathrm{[MASK]}$, $\hat{x}^{p}=x^{p}\odot
M+\mathrm{[MASK]}\odot(1-M)$, where $\odot$ denotes element-wise
multiplication. The masked image $\hat{x}^{p}$ is processed by an image
encoder to produce the latent representations, and a lightweight decoder
(head) is utilized to reconstruct the original image based on the latent
representations. The reconstruction target can be chosen as the normalized raw
pixel [21, 51] or visual tokens [4, 15]. MIM computes the mean squared error
(MSE) between the reconstructed image patches $y^{p}$ and the original image
patches $x^{p}$ as the reconstruction loss,
$\mathcal{L}_{\mathnormal{rec}}=\|(y^{p}-x^{p})\odot(1-\mathrm{M})\|_{2}^{2}$,
which is only calculated on masked patches [21]. After pretraining, the
decoder is discarded and the encoder is used for further finetuning on
downstream visual tasks.

###  3.2 Mixed and Masked Autoencoder (MixMAE)

While previous MIM works achieved great progress in self-supervised visual
representation pretraining, they usually require a large number of epochs for
pretraining. One reason is that they waste much computation on processing the
less informative $\mathrm{[MASK]}$ symbols. Besides, using the
$\mathrm{[MASK]}$ symbol also causes pretraining-finetuning inconsistency as
those symbols never appear during finetuning. To tackle the issues, we create
mixed images as training inputs from pairs of unlabelled training images,
which are generated by mixing two groups of visible tokens from two images,
for pretraining. The mixed input is processed by MixMAE to reconstruct
original images simultaneously. For better transferring the learned multi-
scale representations to downstream tasks, we utilize the popular Swin
Transformer with larger-window size as the encoder of the proposed MixMAE [36,
35]. Figure 1 illustrates the proposed framework. Mixed Training Inputs. Given
two sets of image patches $\\{x^{p}_{1},x^{p}_{2}\\}$ of two random training
images, we create a mixed image by filling each spatial location with the
corresponding visual token from either $x^{p}_{1}$ or $x^{p}_{2}$. The mask
notation $M$ is slightly abused and we denote $M=1$ as choosing a token from
$x^{p}_{1}$ and vice versa. The mixed training image $\hat{x}^{p}_{m}$ is
therefore formulated as:

$\hat{x}^{p}_{m}=x^{p}_{1}\odot\mathrm{M}+x^{p}_{2}\odot(1-\mathrm{M}).$ (1)

MixMAE then takes the mixed image as input for reconstruction during
pretraining. The mixed image no longer consists of the extra $\mathrm{[MASK]}$
symbol and only actual visual tokens, leading to better performances on
downstream tasks. The design shares the same principle of MAE [21], but our
approach does not disassemble the structure of the 2D image, making it more
flexible for adapting to various visual backbones, such as PVT [46] and Swin
Transformer [36]. We can conduct better pretraining based on various
hierarchical vision architectures. We follow common practices to use random
masking strategy [21, 51].

Hierarchical Vision Transformer. For better encoding multi-scale
representations, we build the encoder of MixMAE with popular Swin Transformer
[36] and use larger window size [35] to encode more context for better
reconstruction.

Following Swin Transformer, the input is split into non-overlapping image
patches and processed by a linear projection layer. Then the image patches
added with positional embeddings are processed by 4 stages of Transformer
blocks to produce hierarchical representations, with a downsampling layer
between every two successive stages. However, we do not use the complicated
shifted window for information propagation across non-overlapping windows.
Instead, we use a relatively large window size (i.e., 14$\times$14), and only
conduct global self-attention in stage-3 and -4 111The feature map resolution
is 14$\times$14 / 7$\times$7 for stage-3 / -4. A 14$\times$14 / 7$\times$7
window attention is equivalent to global self-attention. . The larger window
size brings negligible computation overhead, but can better integrate the
global context. As we usually use a large masking ratio in MIM, the global
context is important for better reconstruction.

We scale the encoder of MixMAE following [35] with configuration parameters
listed bellow:

  * •

Base: $C=(128,256,512,1024)$, $H=(4,8,16,32)$, $B=(2,2,18,2)$,

  * •

Large: $C=(192,384,768,1536)$, $H=(6,12,24,48)$, $B=(2,2,18,2)$,

  * •

Huge: $C=(352,704,1408,2816)$, $H=(11,22,44,88)$, $B=(2,2,18,2)$,

where $C$, $H$, and $B$ denote the channel numbers, numbers of the attention
heads, and the numbers of blocks for each stage. The window size is set to
$14\times 14$ / $7\times 7$ for stage-1, -2, and -3 / -4 during pretraining. A
linear layer is added between the encoder and the decoder to convert the
embedding dimension of the encoder’s output to 512.

Dual Reconstruction. After encoding the mixed input, we unmix the token
embeddings into two groups according to the binary mask $M$. We then add the
$\mathrm{[MASK]}$ tokens to reconstruct the original two images from the two
groups with the decoder, which has 8 Transformer blocks with an embedding
dimension of 512. The loss is therefore set as

$\mathcal{L}_{\mathnormal{rec}}=\|(y_{1}^{p}-x_{1}^{p})\odot(1-\mathrm{M})\|_{2}^{2}+\|(y_{2}^{p}-x_{2}^{p})\odot\mathrm{M}\|_{2}^{2},$
(2)

where $y_{1}^{p}$ and $y_{2}^{p}$ are the reconstructed images corresponding
to $x_{1}^{p}$ and $x_{2}^{p}$, respectively. The intuition behind is that as
the mixed input contains tokens from two images, we can fully utilize them by
reconstructing both images to pretrain the neural network. The computation
overhead of reconstructing both images is negligible as the decoder is
lightweight. Our approach demonstrates much higher efficiency than previous
works, as to be introduced in Section 5.

###  3.3 Reducing the Difficulty of the Pretext Task

Although the dual reconstruction (Eq. (2)) enjoys several benefits, it is a
much more challenging optimization problem due to the mixing of image tokens,
which causes slow convergence in our preliminary experiments. To reduce the
optimization difficulty, we facilitate the dual reconstruction by exploring
the following approaches.

  * •

Mix embedding: Besides the positional embeddings, we add two mix embeddings to
the visual tokens to implicitly differentiate the two mixing groups. Each mix
embedding is a vector and is shared for tokens from the same image. In
practice, we use different mix embeddings for the 4 stages of the encoder and
add the embedding at the beginning of each stage.

  * •

Masked self-attention: Thanks to the flexibility of the self-attention
mechanism, we can also differentiate two mixing images explicitly by masking
the self-attention fields. Specifically, for each token, it is only allowed to
aggregate information from the tokens belonging to the same image (group). We
implement the masked self-attention by reusing the mixing mask $M$ described
in Section 3.2. Note that we upsample the mask $M$ by nearest interpolation at
different stages to match the resolution of the feature map.

Figure 2: Tradeoffs of FLOPs vs. (left) top-1 accuracy on ImageNet-1K,
(middle) APbox on COCO, (right) and mIoU on ADE20K. All results are from
various self-supervised pretraining methods followed by supervised finetuning.
All entries on COCO [31] use Mask RCNN [22] framework. All entries on ADE20K
[56] use UperNet [49] framework. Note that this comparison confounds
differences in architecture and pretraining strategy.

Both approaches do not introduce much computation overhead or extra
parameters. The empirical results show that both approaches can help obtain
better results. However, the second approach also leads to a faster
convergence speed, which is crucial for large-scale pretraining. We use the
second approach by default and ablate the design in Section 6.

##  4 Experimental Setup

We validate our proposed MixMAE by conducting experiments with pretraining-
then-finetuning strategy, following previous practices [21, 4]. In particular,
we use ImageNet-1K [13] as the training set for self-supervised pretraining.
We then finetune the encoder of MixMAE to downstream tasks, including image
classification on ImageNet-1K [13], iNaturalist [23], and Places [55], object
detection and instance segmentation on COCO [31], and semantic segmentation on
ADE20K [56].

Pretraining on ImageNet-1K. We conduct self-supervised pretraining on
ImageNet-1K [13]. By default, we pretrain for 600 epochs with the input size
of $224\times 224$. The window size is set as $14\times 14$ for the first 3
stages and $7\times 7$ for stage-4. The patch size of the mask is set to
$32\times 32$ as our hierarchical encoder eventually downsamples the input to
$\frac{1}{32}$ of the input resolution. Following MAE [21], a masking ratio of
75% is used by default, which is implemented by mixing 4 images. We follow all
other pretraining hyperparameters of those in MAE [21] for a fair comparison.

Finetuning for image classification. We conduct supervised finetuning with the
pretrained encoder of our MixMAE on image classification tasks, including
ImageNet-1K [13], Places [55], and iNaturalist [23]. We follow previous
practices [4, 21] and use a layer-wise learning-rate decay strategy [10] for
finetuning. We sweep the decay rate in {0.7, 0.75, 0.8}, and report the best-
performing results. We use drop path regularization [24], and set the drop
rate to 0.15/0.2/0.3 for Swin-B/L/H, respectively. We finetune Swin-B/L/H for
100/50/50 epochs following MAE [21].

Finetuning on COCO. We perform supervised finetuning on COCO [31] for object
detection and instance segmentation using the Mask RCNN framework [22] with
our pretrained encoder as the backbone. We reuse the training setup in MAE
[21] for a fair comparison. We change the window size to $16\times 16$ for
being divisible by the input $1024\times 1024$ resolution. Besides, we change
the window sizes of the 6th-, 12th-, and 18th-block in stage-3 to 32$\times$32
for cross-window interactions following the previous practice [29].

Finetuning on ADE20K. We perform supervised finetuning on ADE20K [56] for
semantic segmentation. We use the UperNet [49] framework with our pretrained
encoder as its backbone. We also change the window size as mentioned above. We
reuse the training setup in BEiT [4] for a fair comparison.

We include more details about pretraining and finetuning in the Appendix.

Method | Backbone | FLOPs (G) | Param. (M) | Supervision | Pretrain Epochs | FT | LIN
---|---|---|---|---|---|---|---
ViT [16] | ViT-B | 17.5 | 86 | RGB | 14 $\dagger$ | 79.9 | -
BEiT [4] | ViT-B | 17.6 | 87 | DALL-E | 800 | 83.2 | 37.6
CAE [7] | ViT-B | 17.5 | 86 | DALL-E | 800 | 83.6 | 68.6
MaskFeat [47] | ViT-B | 17.5 | 86 | HOG | 300 | 83.6 | -
data2vec [3] | ViT-B | 17.5 | 86 | Feature | 800 | 84.2 | -
iBOT [57] | ViT-B | 17.5 | 86 | Momentum | 1600 | 84.0 | 79.5
PeCo [15] | ViT-B | 17.5 | 86 | MoCo v3 | 800 | 84.5 | -
MAE [21] | ViT-B | 17.5 | 86 | RGB | 1600 | 83.6 | 67.8
MAE$\diamond$ [21] | Swin-B/W14 | 16.3 | 88 | RGB | 600 | 84.4 | 61.0
EsViT$\ddagger$ [27] | Swin-B/W14 | 16.3 | 87 | Momentum | 300 | 83.9 | 81.3
SimMIM [51] | ViT-B | 17.5 | 86 | RGB | 800 | 83.8 | 56.7
SimMIM [51] | Swin-B | 15.6 | 88 | RGB | 800 | 84.0 | -
SimMIM$\diamond$ [51] | Swin-B/W14 | 16.3 | 88 | RGB | 300 | 84.1 | 20.2
GreenMIM [25] | Swin-B | 15.6 | 88 | RGB | 800 | 83.8 | -
GreenMIM [25] | Swin-B/W14 | 16.3 | 88 | RGB | 800 | 84.1 | -
MixMAE | Swin-B | 15.6 | 88 | RGB | 600 | 84.6 | 61.2
MixMAE | Swin-B/W14 | 16.3 | 88 | RGB | 300 | 84.8 | 63.8
MixMAE | Swin-B/W14 | 16.3 | 88 | RGB | 600 | 85.1 | 71.0

Table 2: Comparison with state-of-the-art MIM methods. All entries are results
of base-level models and have comparable model sizes. We report the finetuning
accuracy on ImageNet-1K. The FLOPs and Params. are calculated for the
encoders. $\dagger$ denotes the number of epochs is based on JFT [42].
$\ddagger$ results are from [48]. $\diamond$ denotes our implementation with
the official code. FT and LIN denote top-1 accuracy on ImageNet-1K after
finetuning and linear probing respectively.

##  5 Main Results

In this section, we compare our MixMAE to prior arts on various visual
benchmarks. We present the results on ImageNet-1K [13] in Section 5.1, and
then show the results on the other 6 benchmarks in Section 5.2. Note that all
the results of MixMAE are obtained by conducting supervised finetuning of the
encoder with self-supervised pretraining, without extra intermediate
finetuning [4].

Pretrain Method | Backbone |  Pretrain Epochs |  Finetune Epochs |  Top-1 Acc.
---|---|---|---|---
Supervised [36] | Swin-B | - | 300 | 83.5
SimMIM [51] | Swin-B | 800 | 100 | 84.0
GreenMIM [25] | Swin-B | 800 | 100 | 83.8
MixMAE | Swin-B | 600 | 100 | 84.6
Supervised [51] | Swin-L | - | 300 | 83.5
SimMIM [51] | Swin-L | 800 | 100 | 85.4
GreenMIM [25] | Swin-L | 800 | 100 | 85.1
MixMAE | Swin-L | 600 | 50 | 85.9
Supervised [46] | PVT-L | - | 300 | 81.7
SimMIM$\dagger$ | PVT-L | 800 | 100 | 82.0
MixMAE | PVT-L | 600 | 100 | 83.4
Supervised [9] | Twins-SVT-L | - | 300 | 83.7
SimMIM$\dagger$ | Twins-SVT-L | 800 | 100 | 83.3
GreenMIM [25] | Twins-SVT-L | 800 | 100 | 83.9
MixMAE | Twins-SVT-L | 600 | 100 | 83.9

Table 3: Comparison with state-of-the-art MIM methods using the same encoder.
We report the finetuning accuracy on ImageNet-1K. $\dagger$ denotes our
implementation with the official code using input size of $224\times 224$.

###  5.1 Results on ImageNet-1K

Comparisons with other MIM approaches. Table 2 presents the comparison between
MixMAE and state-of-the-art Masked Image Modeling (MIM) works. Our MixMAE can
obtain higher accuracy while requiring fewer epochs for pretraining. In
particular, we achieve 84.8% top-1 accuracy with 300 epochs of pretraining,
1.6% better than BEiT [4] with 62.5% fewer epochs for pretraining. Besides,
our MixMAE also enjoys longer pretraining as previous methods [21].
Specifically, we obtain strong 85.1% top-1 accuracy with only 600 epochs of
pretraining with Swin-B/W14.

Figure 3: Efficiency comparison between MixMAE and SimMIM. We report the
finetuning accuracy on ImageNet-1K. The encoder is Swin-B/W14 with input size
of $224\times 224$.

Method | Backbone | Pretrain | FLOPs | Params. | COCO | FLOPs | Params. | ADE20K
---|---|---|---|---|---|---|---|---
Epochs | (G) | (M) | APbox | APmask | (G) | (M) | mIoU
MoCo v3 [8] | ViT-B | 300 | 853 | 116 | 47.9 | 42.9 | 606 | 164 | 47.3
BEiT [4] | ViT-B | 800 | 853 | 116 | 49.8 | 44.4 | 606 | 164 | 47.1
MAE [21] | ViT-B | 1600 | 853 | 116 | 50.3 | 44.9 | 606 | 164 | 48.1
iBOT [57] | ViT-B | 1600 | - | - | 51.2 | 44.2 | - | - | 50.0
EsViT [51] | Swin-B | 300 | - | - | - | - | - | - | 47.3
SimMIM [51] | Swin-B | 800 | - | - | 52.3 | - | - | - | 52.8$\dagger$
SimMIM $\diamond$ [51] | Swin-B/W14 | 300 | 701 | 110 | 51.1 | 45.4 | 302 | 122 | 48.9
GreenMIM [25] | Swin-B | 800 | - | - | 50.0 | 44.1 | - | - | -
MixMAE | Swin-B/W14 | 300 | 701 | 110 | 52.3 | 46.4 | 302 | 122 | 49.9
MixMAE | Swin-B/W14 | 600 | 701 | 110 | 52.7 | 47.0 | 302 | 122 | 51.1
MoCo v3 [8] | ViT-L | 300 | 1907 | 339 | 49.3 | 43.9 | 877 | 392 | 49.1
BEiT [4] | ViT-L | 800 | 1907 | 339 | 53.3 | 47.1 | 877 | 392 | 53.3
MAE [21] | ViT-L | 1600 | 1907 | 339 | 53.3 | 47.2 | 877 | 392 | 53.6
SimMIM [51] | Swin-L | 800 | - | - | 53.8 | - | - | - | 53.5$\dagger$
MixMAE | Swin-L | 600 | 1119 | 319 | 54.3 | 48.2 | 460 | 236 | 53.8

Table 4: Comparison with other self-supervised approaches on COCO and ADK20K.
We report APbox and APmask on COCO, and mIoU on ADE20K. The results of BEiT
and MoCo v3 are from MAE [21]. The results of EsViT are from [48]. $\dagger$
denotes using supervised finetuning on ImageNet. $\diamond$ denotes our
implementation with the official code.

Method | Backbone | FLOPs (G) | Params. (M) | INat2018 | INat2019 | Places205 | Places365 | Average
---|---|---|---|---|---|---|---|---
DINO [5] | ViT-B | 17.5 | 86 | 72.6 | 78.2 | - | - | -
MAE [21] | ViT-B | 17.5 | 86 | 75.4 | 80.5 | 63.9 | 57.9 | 69.4
MixMAE | Swin-B/W14 | 16.3 | 88 | 78.2 | 83.3 | 68.6 | 59.0 | 72.3
MAE [21] | ViT-L | 61.3 | 304 | 80.1 | 83.4 | 65.8 | 59.4 | 72.1
MixMAE | Swin-L | 35.8 | 235 | 80.6 | 84.4 | 69.3 | 59.6 | 73.5

Table 5: Comparison with other self-supervised approaches on classification
tasks. We report the top-1 accuracy and average accuracy of all datasets. We
also report the average accuracy over the 4 datasets.

While previous works design various reconstruction targets to speed up the
pretraining process [4, 47], our MixMAE reconstructs simply normalized pixels
[21] and demonstrates strong pretraining efficiency. Compared to MaskFeat
[47], our MixMAE obtains +1.2% better accuracy with the same pretraining
epochs. PeCo [15] proposed to reconstruct the perceptual codebook from a
pretrained MoCo v3 network [8] and can achieve better performance to some
extent. In comparison, our MixMAE obtains even better performance (+0.6%) than
PeCo with fewer pretraining epochs (-200). The superior performance of MixMAE
comes from our mixed pretraining as well as the hierarchical Vision
Transformer. However, SimMIM [51] also utilizes a hierarchical Swin
Transformer [36], but its performance is worse (-1.1%) than MixMAE with more
pretraining epochs (+200). We conduct a thorough comparison with SimMIM by
using the same encoder Swin-B/W14 and show the results in Figure 3. Our
proposed MixMAE shows much better pretraining efficiency than SimMIM. We list
the training time in the Appendix.

We test with scaling MixMAE up to 600M parameters, as shown in Figure 2
(Left). MixMAE has better FLOPs vs. accuracy tradeoff than other approaches.
In particular, MixMAE pretrained Swin-L and -H achieve 85.9% and 86.9% top-1
accuracy, respectively, being comparable with MAE-L (85.9%) and -H (86.9%) but
requiring fewer FLOPs for inference (-40% for -L and -30% for -H).

Integrating MixMAE to other backbones. While previous works [21, 47] may be
restricted to a specific architecture, our proposed MixMAE can generalize to
various visual backbones, including Swin Transformer [36], Twins [9], and PVT
[46]. We conduct a thorough comparison with other MIM approaches with fixed
encoders. As shown in Table 3, MixMAE consumes the same or fewer epochs for
pretraining but obtains consistently better performance on hierarchical ViTs.
In particular, our MixMAE achieves 84.6% top-1 accuracy with Swin-B, +0.6%
better than SimMIM [51] while requiring 200 fewer epochs for pretraining. With
Swin-L, our MixMAE obtains 85.8% top-1 accuracy with 600 epochs of pretraining
and 50 epochs of finetuning, showing higher efficiency than SimMIM. Besides,
our MixMAE achieves 83.2% top-1 accuracy with PVT-L [46], improving the
supervised baseline by a non-trivial margin.

###  5.2 Results of Transferring to Downstream Tasks

To further demonstrate the effectiveness of the visual representations learned
by MixMAE, we transfer MixMAE to various visual benchmarks with settings
described in Section 4.

Object detection and instance segmentation. We show the results on COCO [31]
in Table 4. By pretraining for 600 epochs on ImageNet-1K, we achieve 52.7
APbox and 47.0 APmask with Swin-B, surpassing previous self-supervised
approaches with fewer FLOPs and parameters. Compared to BEiT [4], our MixMAE
obtains higher APbox (+2.9) and APmask (+2.6) with less pretraining epochs
(-200). Note that our hierarchical backbone can naturally be transferred to
object detection without re-designing [29] network architectures such as FPN
[30].

Our MixMAE can also scale up to larger models in object detection task and
obtains better performance. As shown in Table 4, we achieve 54.3 APbox (48.2
APmask) with Swin-L, +1.0 (+1.1) better than BEiT while requiring 200 fewer
epochs for pretraining and 41% fewer FLOPs for inference. We further evaluate
the tradeoff of FLOPs vs. APbox in Figure 2 (Middle). We also found that
MixMAE outperforms other approaches by large margins.

Semantic segmentation. Table 4 also presents the results of MixMAE on ADE20K
[56]. We compare its Mean Intersection over Union (mIoU) on ADE20K with other
self-supervised approaches. Our pretrained Swin-B achieves 51.1 mIoU, +4.0
better than BEiT while requiring only half of FLOPs for inference. Besides, we
obtain 53.8 mIoU by scaling up the model to Swin-L. Thanks to the hierarchical
design, our MixMAE consumes much fewer FLOPs for inference compared to other
approaches with plain ViT. In Figure 2 (Right), our MixMAE outperforms other
approaches by large margins.

Image classification. We further transfer MixMAE to other 4 classification
datasets and show the results in Table 5. These datasets are challenging as
the accuracies are relatively low, e.g., 57.9% top-1 accuracy on Places365
[55] for MAE-B [21]. However, our MixMAE can still outperform previous self-
supervised approaches. In particular, we achieve an average +2.9% performance
gain compared to MAE-B with Swin-B. Besides, our pretrained Swin-L has an
average +1.4% performance gain over MAE-L while requiring only 58% FLOPs for
inference.

##  6 Ablation Studies

In this section, we ablate the key designs of MixMAE and report the
transferring results of each ablation. Unless otherwise specified, we pretrain
Swin-B/W14 for 300 epochs with a masking ratio of 50%. By default, we report
the top-1 accuracy on ImageNet-1K [13] and mIoU on ADE20K [56]. We also show
the results on COCO [31] in Appendix.

Figure 4: Examples images for different filling contents.

Type | Top-1 Acc. | mIoU
---|---|---
Mix | 84.6 | 49.9
Zero | 84.1 | 48.0
Learnable | 84.1 | 48.9
Shuffle | 82.6 | 43.0
Zoomin | 83.5 | 44.9

Table 6: Filling content.

# Epochs | Top-1 Acc. | mIoU
---|---|---
300 | 84.6 | 49.9
600 | 85.1 | 50.3
900 | 85.1 | 51.0

Table 7: Pretraining epochs.

# Images (ratio) | Top-1 Acc. | mIoU
---|---|---
2 (0.5) | 84.6 | 49.9
2 w/ $\mathrm{[M]}$ (0.75) | 84.4 | 49.0
3 (0.67) | 84.7 | 49.9
4 (0.75) | 84.8 | 49.9
5 (0.8) | 84.5 | 49.5

Table 8: Number of mixing images.

Dual | Top-1 Acc. | mIoU
---|---|---
✓ | 84.6 | 49.9
✗ | 84.0 | 47.3

Table 9: Dual reconstruction.

Approach | 300 | 600 | 900
---|---|---|---
Ours w/o unmixing | 84.4 | 84.4 | 84.4
Ours w/ mix embedding | 84.4 | 84.6 | 84.8
Ours w/ masked self-attention | 84.6 | 85.1 | 85.1

Table 10: Ablation on reducing the difficulty of the pretext task. We report
the top-1 accuracy on ImageNet-1K for each approach with different pretraining
epochs. Ours w/o unmixing denotes that we do not reduce the difficulty of the
pretext task. Details of the other two approaches are described in Section
3.3.

Content to filling. While MixMAE default fills the masked tokens of one image
with visible tokens from another image, we also explore more design choices.
Specifically, we try to fill the masked tokens with the following contents.

  * •

Zero: Filling the masked tokens with zeros. This approach causes serious
mismatches between the masked tokens and the visible tokens.

  * •

Learnable: Following previous works [4, 51], we fill the masked tokens with a
shared learnable token. The difference between the zero approach is that
learnable tokens can be adapted to visible tokens to match the distribution of
the training set.

  * •

Shuffle: We randomly shuffle the masked tokens, and then fill the masked
locations with the shuffled tokens. We note that this approach is similar to
solving jigsaw puzzles [39] with the difference that we need to fully regress
the pixels.

  * •

Zoomin: We zoom in the original image and randomly crop an image patch with
the size of the original image. We then fill the masked tokens with tokens
from the cropped image. This approach also provides masking tokens that are
similar to visible ones but is harder than the shuffle approach.

We visualize the four approaches in Figure 4. We compare the performances of
the four approaches in Table 9. Our default choice Mix performs best in terms
of accuracy on ImageNet-1K and mIoU on ADE20K. We find the learnable approach
has a similar performance on ImageNet-1K but better performance on ADE20K
compared to Zero. We hypothesize that the training-finetuning inconsistency
has a larger impact on tasks without a lot of labeled images. The shuffle and
zoomin approaches perform much worse than other approaches. Those two
strategies cause easier pretext task and have lower pretraining loss. However,
the learned representation quality is lower.

Dual reconstruction. We ablate the proposed dual reconstruction in Table 9. We
find that dual reconstruction greatly boosts the performance on downstream
tasks. The performance gap is larger on ADE20K, where we observe +2.6 mIoU
with the dual reconstruction. Note that the computation overhead of dual
reconstruction is negligible as the decoder is lightweight.

Masking ratio. Our MixMAE implements different masking ratios by mixing more
images at inputs. In addition, we also experiment to add $\mathrm{[MASK]}$
tokens for a higher masking ratio. We ablate the masking ratios in Table 9. We
find that using a masking ratio 75% by mixing 4 images performs best. In
contrast, adding $\mathrm{[MASK]}$ tokens for a 75% masking ratio has worse
performance, demonstrating the effectiveness of the proposed mixing approach.

Pretraining epochs. Thanks to the dual reconstruction, our MixMAE can achieve
strong performance with few pretraining epochs. We ablate the pretraining
epochs in Table 9. We find that the mIoU on ADE20K can be further improved
with more pretraining epochs. We achieve 51.0 mIoU with 900 epochs of
pretraining. In contrast, the accuracy on ImageNet-1K does not improve after
600 epochs. It might be because the finetuning on ImageNet-1K is more
adequate.

Reducing the difficulty. As stated in Section 3.3, directly performing
reconstruction with the mixed input is a much more challenging optimization
problem. Hence, we provide two practical approaches to reduce the difficulty.
We ablate the design in Table 10. We note that all the approaches do not bring
nonnegligible FLOPs or parameters. We find that the performance of the
approach without unmixing is worst even when trained for more epochs. In
contrast, using mix embedding alleviates the problem and improves its
performance with longer pretraining. However, using masked self-attention in
our final solution is much more efficient, and has better performance.

##  7 Discussion and Conclusion

This paper proposes Mixed and Masked AutoEncoder (MixMAE) for efficient visual
representation learning. Our MixMAE uses a mixed input created by mixing two
(or more) images with random masks, and applies dual reconstruction to recover
the original two (or more) images from the mixed hidden representations. We
further explore using Swin Transformer with a larger window size for efficient
representation learning. Empirical results on 7 visual benchmarks demonstrate
MixMAE can learn high-quality visual representations efficiently and has
better FLOPs / performance tradeoff than previous MIM works. While this paper
focuses on the vision field, we hope our work will inspire future works in
other modalities, such as text and audio.

##### Acknowledgement

This project is funded in part by National Key R&D Program of China Project
2022ZD0161100, by the Centre for Perceptual and Interactive Intelligence
(CPII) Ltd under the Innovation and Technology Commission (ITC)’s InnoHK, by
General Research Fund of Hong Kong RGC Project 14204021. Hongsheng Li is a PI
of CPII under the InnoHK.

## References

  * [1] Jean-Baptiste Alayrac, Joao Carreira, and Andrew Zisserman.  The visual centrifuge: Model-free layered video representations.  In CVPR, 2019.
  * [2] Sara Atito, Muhammad Awais, and Josef Kittler.  Sit: Self-supervised vision transformer.  arXiv:2104.03602, 2021.
  * [3] Alexei Baevski, Wei-Ning Hsu, Qiantong Xu, Arun Babu, Jiatao Gu, and Michael Auli.  Data2vec: A general framework for self-supervised learning in speech, vision and language.  arXiv:2202.03555, 2022.
  * [4] Hangbo Bao, Li Dong, and Furu Wei.  Beit: Bert pre-training of image transformers.  In ICLR, 2021.
  * [5] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.  Emerging properties in self-supervised vision transformers.  In ICCV, 2021.
  * [6] Mark Chen, Alec Radford, Rewon Child, Jeffrey Wu, Heewoo Jun, David Luan, and Ilya Sutskever.  Generative pretraining from pixels.  In ICML, 2020.
  * [7] Xiaokang Chen, Mingyu Ding, Xiaodi Wang, Ying Xin, Shentong Mo, Yunhao Wang, Shumin Han, Ping Luo, Gang Zeng, and Jingdong Wang.  Context autoencoder for self-supervised representation learning.  arXiv:2202.03026, 2022.
  * [8] Xinlei Chen, Saining Xie, and Kaiming He.  An empirical study of training self-supervised vision transformers.  In ICCV, 2021.
  * [9] Xiangxiang Chu, Zhi Tian, Yuqing Wang, Bo Zhang, Haibing Ren, Xiaolin Wei, Huaxia Xia, and Chunhua Shen.  Twins: Revisiting the design of spatial attention in vision transformers.  NeurIPS, 34:9355–9366, 2021.
  * [10] Kevin Clark, Minh-Thang Luong, Quoc V Le, and Christopher D Manning.  Electra: Pre-training text encoders as discriminators rather than generators.  In ICLR, 2020.
  * [11] Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le.  Randaugment: Practical automated data augmentation with a reduced search space.  In CVPRW, 2020.
  * [12] Zihang Dai, Hanxiao Liu, Quoc V Le, and Mingxing Tan.  Coatnet: Marrying convolution and attention for all data sizes.  NeurIPS, 34:3965–3977, 2021.
  * [13] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, K. Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In CVPR, 2009.
  * [14] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  In NAACL, 2019.
  * [15] Xiaoyi Dong, Jianmin Bao, Ting Zhang, Dongdong Chen, Weiming Zhang, Lu Yuan, Dong Chen, Fang Wen, and Nenghai Yu.  Peco: Perceptual codebook for bert pre-training of vision transformers.  arXiv:2111.12710, 2021.
  * [16] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  In ICLR, 2021.
  * [17] Golnaz Ghiasi, Yin Cui, Aravind Srinivas, Rui Qian, Tsung-Yi Lin, Ekin D Cubuk, Quoc V Le, and Barret Zoph.  Simple copy-paste is a strong data augmentation method for instance segmentation.  In CVPR, 2021.
  * [18] Xavier Glorot and Yoshua Bengio.  Understanding the difficulty of training deep feedforward neural networks.  In AISTATS, 2010.
  * [19] Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He.  Accurate, large minibatch sgd: Training imagenet in 1 hour.  arXiv:1706.02677, 2017.
  * [20] Raghav Goyal, Samira Ebrahimi Kahou, Vincent Michalski, Joanna Materzynska, Susanne Westphal, Heuna Kim, Valentin Haenel, Ingo Fründ, Peter N. Yianilos, Moritz Mueller-Freitag, Florian Hoppe, Christian Thurau, Ingo Bax, and Roland Memisevic.  The “something something” video database for learning and evaluating visual common sense.  In ICCV, 2017.
  * [21] Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Doll’ar, and Ross B. Girshick.  Masked autoencoders are scalable vision learners.  In CVPR, 2021.
  * [22] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask r-cnn.  In ICCV, 2017.
  * [23] Grant Van Horn, Oisin Mac Aodha, Yang Song, Yin Cui, Chen Sun, Alexander Shepard, Hartwig Adam, Pietro Perona, and Serge J. Belongie.  The inaturalist species classification and detection dataset.  In CVPR, 2018.
  * [24] Gao Huang, Yu Sun, Zhuang Liu, Daniel Sedra, and Kilian Q Weinberger.  Deep networks with stochastic depth.  In ECCV, 2016.
  * [25] Lang Huang, Shan You, Mingkai Zheng, Fei Wang, Chen Qian, and Toshihiko Yamasaki.  Green hierarchical vision transformer for masked image modeling.  arXiv preprint arXiv:2205.13515, 2022.
  * [26] Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Joan Puigcerver, Jessica Yung, Sylvain Gelly, and Neil Houlsby.  Big transfer (bit): General visual representation learning.  In ECCV, 2020.
  * [27] Chunyuan Li, Jianwei Yang, Pengchuan Zhang, Mei Gao, Bin Xiao, Xiyang Dai, Lu Yuan, and Jianfeng Gao.  Efficient self-supervised vision transformers for representation learning.  In ICLR, 2022.
  * [28] Xiang Li, Wenhai Wang, Lingfeng Yang, and Jian Yang.  Uniform masking: Enabling mae pre-training for pyramid-based vision transformers with locality.  arXiv:2205.10063, 2022.
  * [29] Yanghao Li, Saining Xie, Xinlei Chen, Piotr Dollar, Kaiming He, and Ross Girshick.  Benchmarking detection transfer learning with vision transformers.  arXiv:2111.11429, 2021.
  * [30] Tsung-Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongie.  Feature pyramid networks for object detection.  In CVPR, 2017.
  * [31] Tsung-Yi Lin, Michael Maire, Serge J. Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitnick.  Microsoft coco: Common objects in context.  In ECCV, 2014.
  * [32] Guilin Liu, Kevin J Shih, Ting-Chun Wang, Fitsum A Reda, Karan Sapra, Zhiding Yu, Andrew Tao, and Bryan Catanzaro.  Partial convolution based padding.  arXiv:1811.11718, 2018.
  * [33] Jihao Liu, Xin Huang, Guanglu Song, Hongsheng Li, and Yu Liu.  Uninet: Unified architecture search with convolution, transformer, and mlp.  In ECCV, pages 33–49. Springer, 2022.
  * [34] Jihao Liu, Boxiao Liu, Hang Zhou, Hongsheng Li, and Yu Liu.  Tokenmix: Rethinking image mixing for data augmentation in vision transformers.  In ECCV, pages 455–471. Springer, 2022.
  * [35] Ze Liu, Han Hu, Yutong Lin, Zhuliang Yao, Zhenda Xie, Yixuan Wei, Jia Ning, Yue Cao, Zheng Zhang, Li Dong, et al.  Swin transformer v2: Scaling up capacity and resolution.  In CVPR, pages 12009–12019, 2022.
  * [36] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In ICCV, 2021.
  * [37] Ilya Loshchilov and Frank Hutter.  Sgdr: Stochastic gradient descent with warm restarts.  In ICLR, 2016.
  * [38] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  In ICLR, 2017.
  * [39] Mehdi Noroozi and Paolo Favaro.  Unsupervised learning of visual representations by solving jigsaw puzzles.  In ECCV, 2016.
  * [40] Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever.  Zero-shot text-to-image generation.  In ICML, 2021.
  * [41] Jason Tyler Rolfe.  Discrete variational autoencoders.  In ICLR, 2016.
  * [42] Chen Sun, Abhinav Shrivastava, Saurabh Singh, and Abhinav Gupta.  Revisiting unreasonable effectiveness of data in deep learning era.  In ICCV, 2017.
  * [43] Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna.  Rethinking the inception architecture for computer vision.  In CVPR, 2016.
  * [44] Zhan Tong, Yibing Song, Jue Wang, and Limin Wang.  Videomae: Masked autoencoders are data-efficient learners for self-supervised video pre-training.  arXiv:2203.12602, 2022.
  * [45] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  NeurIPS, 30, 2017.
  * [46] Wenhai Wang, Enze Xie, Xiang Li, Deng-Ping Fan, Kaitao Song, Ding Liang, Tong Lu, Ping Luo, and Ling Shao.  Pyramid vision transformer: A versatile backbone for dense prediction without convolutions.  In ICCV, 2021.
  * [47] Chen Wei, Haoqi Fan, Saining Xie, Chao-Yuan Wu, Alan Yuille, and Christoph Feichtenhofer.  Masked feature prediction for self-supervised visual pre-training.  arXiv:2112.09133, 2021.
  * [48] Yixuan Wei, Han Hu, Zhenda Xie, Zheng Zhang, Yue Cao, Jianmin Bao, Dong Chen, and Baining Guo.  Contrastive learning rivals masked image modeling in fine-tuning via feature distillation.  arXiv:2205.14141, 2022.
  * [49] Tete Xiao, Yingcheng Liu, Bolei Zhou, Yuning Jiang, and Jian Sun.  Unified perceptual parsing for scene understanding.  In ECCV, 2018.
  * [50] Tete Xiao, Ilija Radosavovic, Trevor Darrell, and Jitendra Malik.  Masked visual pre-training for motor control.  arXiv:2111.11429, 2022.
  * [51] Zhenda Xie, Zheng Zhang, Yue Cao, Yutong Lin, Jianmin Bao, Zhuliang Yao, Qi Dai, and Han Hu.  Simmim: A simple framework for masked image modeling.  In CVPR, 2021.
  * [52] Sangdoo Yun, Dongyoon Han, Seong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo.  Cutmix: Regularization strategy to train strong classifiers with localizable features.  In ICCV, 2019.
  * [53] Sangdoo Yun, Dongyoon Han, Seong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo.  Cutmix: Regularization strategy to train strong classifiers with localizable features.  In ICCV, 2019.
  * [54] Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz.  mixup: Beyond empirical risk minimization.  In ICLR, 2017.
  * [55] Bolei Zhou, Àgata Lapedriza, Jianxiong Xiao, Antonio Torralba, and Aude Oliva.  Learning deep features for scene recognition using places database.  In NeurIPS, 2014.
  * [56] Bolei Zhou, Hang Zhao, Xavier Puig, Sanja Fidler, Adela Barriuso, and Antonio Torralba.  Scene parsing through ade20k dataset.  In CVPR, 2017.
  * [57] Jinghao Zhou, Chen Wei, Huiyu Wang, Wei Shen, Cihang Xie, Alan Yuille, and Tao Kong.  ibot: Image bert pre-training with online tokenizer.  In ICLR, 2021.

##  Appendix A Training Details

###  A.1 Hyperparameters of Pretraining and Finetuning

We include details about the hyperparameters for reimplementation.

Pretraining. The default setting is in Table 11. We use xavier_uniform [18] to
initialize all Transformer blocks following original ViT [16]. We by default
use batch size of 1024 and scale the learning rate with linear rule [19]:
lr=base_lr $\times$ batch_size / 256.

config | value
---|---
optimizer | AdamW [38]
base learning rate | $1.5\times 10^{-4}$
weight decay | 0.05
optimizer momentum |  $\beta_{1},\beta_{2}$=0.9,0.95 [6]
learning rate schedule | cosine decay [37]
warmup epochs | 40
augmentation | RandomResizedCrop

Table 11: Pretraining on ImageNet-1K.

Finetuning on ImageNet-1K. The default setting is in Table 12. We use layer-
wise learning rate decay following [4, 10]. The decay ratio is swept in {0.7,
0.75, 0.8}, and we find 0.7 performs best. Following pretraining, the learning
rate is scaled with linear rule: lr=base_lr $\times$ batch_size / 256.

config | value
---|---
optimizer | AdamW
base learning rate | $5\times 10^{-4}$
layer-wise lr decay [4, 10] | 0.7
batch size | 1024
weight decay | 0.05
optimizer momentum |  $\beta_{1},\beta_{2}$=0.9,0.999
learning rate schedule | cosine decay
warmup epochs | 5
training epochs | 100 (B), 50 (L/H)
augmentation | RandAug(9, 0.5) [11]
LabelSmooth [43] | 0.1
Mixup [54] | 0.8
CutMix [53] | 1.0
drop path [24] | 0.15 (B), 0.2 (L), 0.3 (H)

Table 12: Finetuning on ImageNet-1K.

Finetuning on other classification datasets. We reuse the setting in Table 12.
We adjust the drop path rate for each dataset.

Finetuning on COCO. We use the Mask RCNN [22] framework with the encoder of
MixMAE as its backbone. We follow the training setting in [29, 21]. In
particular, we use large-scale jitter [17] augmentation with 1024$\times$1024
resolution and [0.1, 2.0] scale range. We use step learning rate schedule with
0.25 epochs of warmup. We finetune Swin-B/-L for 55/80 epochs. We use a layer-
wise learning rate and set the decay ratio to 0.85/0.9 for Swin-B/-L.

Finetuning on ADE20K. We use the UperNet [49] framework with the encoder of
MixMAE as its backbone. We finetune for 16K iterations with a batch size of
16. We use the layer-wise learning rate and set the decay ratio to 0.85/0.9
for Swin-B/-L. We adopt others settings from BEiT [4].

###  A.2 Additional Results of Ablation Studies

####  A.2.1 Ablation results on COCO

We show more results of our ablation studies on COCO benchmark in Table 14 14
16 16. We find that the performance on the COCO is similar to that on ADE20K.

Type | APbox | APmask
---|---|---
Mix | 51.5 | 45.9
Zero | 51.0 | 45.3
Learnable | 50.9 | 45.1
Shuffle | 46.5 | 41.6
Zoomin | 47.9 | 42.6

Table 13: Filling content.

# Images (ratio) | APbox | APmask
---|---|---
2 (0.5) | 51.5 | 45.9
2 w/ $\mathrm{[M]}$ (0.75) | 51.2 | 45.4
3 (0.67) | 51.6 | 45.9
4 (0.75) | 52.3 | 46.4
5 (0.8) | 51.4 | 45.4

Table 14: Number of mixing images.

# Epochs | APbox | APmask
---|---|---
300 | 51.5 | 45.9
600 | 52.2 | 46.5
900 | 52.4 | 46.7

Table 15: Pretraining epochs.

Dual | APbox | APmask
---|---|---
✓ | 51.5 | 45.9
✗ | 50.0 | 44.4

Table 16: Dual reconstruction.

Method | Backbone |  Pretrain Epochs |  Top-1 Acc.
---|---|---|---
Supervised | ViT-B | - | 81.8
MAE | ViT-B | 1600 | 83.6
BEiT | ViT-B | 800 | 83.2
MixMAE | ViT-B | 600 | 83.8

Table 17: Performance of MixMAE and other methods on ViT.

####  A.2.2 Pretraining Time Comparison

We compare the wall-clock time of the pretrain in Table 18. The pretrain time
is measured on 8 NVIDIA-A100-SXM-80GB GPUs with a total batch size of 1024.

Method | Backbone |  Pretrain epochs |  Pretrain Time (GPU hours) |  Top-1 Acc.
---|---|---|---|---
SimMIM [51] | Swin-B | 800 | 116 | 84.0
MAE [21] | ViT-B | 1600 | 123 | 83.6
BEiT [4] | ViT-B | 800 | 151 | 83.2
MixMAE | Swin-B | 600 | 85 | 84.6
MixMAE | Swin-B/W14 | 300 | 64 | 84.8
MixMAE | Swin-B/W14 | 600 | 127 | 85.1

Table 18: Wall-clock time comparison of MIM methods.

####  A.2.3 Performance on ViT.

We show the results on ViT [16] in Table 17.

Figure 5: Mixed convolution.

Method | Backbone | Input Size | Pretrain Data | Top-1 Acc.
---|---|---|---|---
BiT-S [26] | Res50x3 | $448\times 448$ | ImageNet-1K | 80.0
BiT-M [26] | Res50x3 | $448\times 448$ | ImageNet-21K | 84.0
MixMAE | Res50x3 | $224\times 224$ | ImageNet-1K (w/o labels) | 81.8
BiT-S [26] | Res101x3 | $448\times 448$ | ImageNet-1K | 80.3
BiT-M [26] | Res101x3 | $448\times 448$ | ImageNet-21K | 84.3
MixMAE | Res101x3 | $224\times 224$ | ImageNet-1K (w/o labels) | 82.6

Table 19: Results on ConvNets. All results of MixMAE are obtained by
pretraining for 300 epochs and finetuning for 100 epochs on ImageNet-1K. We
report the top-1 accuracy on ImageNet-1K.

###  A.3 Extend to ConvNets

While our MixMAE uses a hierarchical Transformer as the encoder, we also
explore popular ConvNets. In particular, we use ResNet50x3 and ResNet101x3 as
the encoder and compare the finetuning results on ImageNet-1K with BiT [26].
To reduce the difficulty of the pretext task, we extend the idea of partial
convoluation [32] and propose a mixed version, as illustrated in Figure 5.

We compare the results in Table 19. In particular, our MixMAE outperforms
BiT-S by a large margin with half the input size. We note that BiT-M achieves
better results by pretraining with 10 $\times$ larger dataset ImageNet-21K. We
believe the results of MixMAE can be further improved by using much larger
datasets as shown by [4], and we leave it as future work.