# Identification of maximal C∗-covers of some operator algebras

Benton L. Duncan  Department of Mathematics
Illinois State University
Normal, Illinois
USA<EMAIL_ADDRESS>
###### Abstract.

We use results on inclusions of free products and extensions of completely
positive maps to determine the maximal C∗-envelope for upper triangular
$3\times 3$ matrices. We consider these same results in the context of larger
upper triangular matrices and graph algebras associated to cycle graphs.

###### Key words and phrases:

maximal C∗-covers, free products

###### 1991 Mathematics Subject Classification:

47L30, 47L40, 46L09

##  1\. Introduction

In 1999, Blecher [2] introduced the concept of the maximal C∗-cover of an
operator algebra. This algebra encodes the completely contractive
representation theory of an operator algebra. In particular, given an operator
algebra $A$, the maximal C∗-cover C${}^{*}_{\rm max}(A)$ is the C∗-algebra
generated by a completely isometric copy of $A$ so that any completely
contractive representation of $A$ into a C∗-algebra extends to a
∗-representation of C${}^{*}_{\rm max}(A)$ into the same C∗-algebra. In that
paper, Blecher provided a concrete example for the operator algebra $T_{2}$ of
the upper triangular $2\times 2$ matrices which is the universal C∗-algebra
generated by a contractive nilpotent of degree 2 (see the first row of Table 1
in [15]).

Several authors have extended the use of the maximal C∗-cover for operator
algebras. It has found use in [4] to understand a version of $Ext$ for
nonselfadjoint operator algebras. More recently, in [7] and [19] the maximal
C∗-cover of an operator algebra was used to study a notion of residually
finite dimensional nonselfadjoint operator algebras. At the same time, the use
of the maximal C∗-covers is constrained somewhat by the lack of concrete
examples of maximal C∗-covers. The author made a general attempt to understand
the maximal C∗-cover of an operator algebra using Banach $*$-algebra methods
in [10], but even there concrete examples were absent.

In a similar spirit to that of this paper, in [13], the authors consider the
universal C∗-algebra generated by an operator system (arising in a similar
manner from universal properties) and there they construct maximal C∗-algebras
of the operator systems $\mathbb{C},\mathbb{C}\oplus\mathbb{C},$ and
$\mathbb{C}\oplus\mathbb{C}\oplus\mathbb{C}$. They also show that the
universal C∗-algebra of the operator system $M_{2}(\mathbb{C})$ is non-exact.
An important difference to note is that viewing these as operator systems is
different from viewing them as operator algebras, since in all three cases, as
C∗-algebras, their (algebraic) maximal C∗-cover is themselves. In that
context, maximal C∗-envelopes of operator systems were used by Davidson and
Kennedy in a recent preprint [9].

In this paper, we do two things. First, we build tools to more readily
understand inclusions of free products of C∗-algebras. These extend results of
[16] concerning pushout diagrams and their extensions in [1] to general
inclusions of C∗-algebras in free products. We also extend recent results on
conditional expectations of free products from [8]. Second, we use the tools
we develop to consider a method to build concrete maximal C∗-covers in two
contexts. There we will see that even simple operator algebras give rise to
non-exact maximal C∗-covers. We will also demonstrate how quickly the
complications of this technique interfere in coherent natural generalizations
of the example we build.

##  2\. Inclusions of free products

Before we focus on identifying the maximal C∗-covers of interest, we need to
provide a context for placing them into a concrete C∗-algebra. To do this we
will need to extend some well-known results on C∗-algebras. We are able to do
this because we will be identifying our operator algebras as free products of
well understood operator algebras. These extensions of known results are
interesting in their own right.

We start by letting $A_{j,k}$ be the C∗-subalgebra of $M_{k}\otimes C[0,1]$ of
the form

$\begin{bmatrix}C[0,1]&\cdots&0&0&0&0&\cdots&0\\\
\vdots&\cdots&\ddots&\ddots&\ddots&\ddots&\cdots&\vdots\\\
0&\cdots&C[0,1]&0&0&0&\cdots&0\\\ 0&\cdots&0&C[0,1]&C[0,1]&0&\cdots&0\\\
0&\cdots&0&C[0,1]&C[0,1]&0&\cdots&0\\\ 0&\cdots&0&0&0&C[0,1]&\cdots&0\\\
\vdots&\cdots&\ddots&\ddots&\ddots&\ddots&\cdots&\vdots\\\
0&\cdots&0&0&0&0&\cdots&C[0,1]\end{bmatrix}.$

Here the first row with two copies of $C[0,1]$ is the $j$-th row of the
matrix. Of course, this only make sense if $j\leq k-1$.

######  Example 2.1.

For $k=2$ there is only one possible algebra

$A_{1,2}=\begin{bmatrix}C[0,1]&C[0,1]\\\ C[0,1]&C[0,1]\end{bmatrix}$

but when $k=3$ there are two options

$\displaystyle A_{1,3}$ $\displaystyle=\begin{bmatrix}C[0,1]&C[0,1]&0\\\
C[0,1]&C[0,1]&0\\\ 0&0&C[0,1]\end{bmatrix}\mbox{ and }$ $\displaystyle
A_{2,3}$ $\displaystyle=\begin{bmatrix}C[0,1]&0&0\\\ 0&C[0,1]&C[0,1]\\\
0&C[0,1]&C[0,1]\end{bmatrix}$

Next we write $A_{k,k}$ for the algebra

$\begin{bmatrix}C[0,1]&0&0&\cdots&0&0&C[0,1]\\\ 0&C[0,1]&0&\cdots&0&0&0\\\
0&0&C[0,1]&\ddots&0&0&0\\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\\
0&0&0&\cdots&C[0,1]&0&0\\\ 0&0&0&\cdots&0&C[0,1]&0\\\
C[0,1]&0&0&\cdots&0&0&C[0,1]\end{bmatrix}.$

We denote by $e_{i,j}$ the elementary matrix in $M_{k}\otimes C[0,1]$ with $1$
in the $i$-$j$ position and zero everywhere else, and we let $D_{k}$ be the
diagonal subalgebra of $A_{j,k}$ spanned by $\\{e_{i,i}\\}_{i=1}^{k}$.

We collect a number of facts about these algebras.

######  Lemma 2.2.

$A_{m,k}\cong A_{n,k}$ for all $m,n\leq k$

###### Proof.

The isomorphism is a unitary equivalence induced by elementary row and column
operations in $M_{k}\otimes C[0,1]$. ∎

We can also see that $A_{j,k}\cong(C[0,1]\otimes M_{2})\oplus C[0,1]\oplus
C[0,1]\oplus\cdots\oplus C[0,1]$ with $k-2$ copies of $C[0,1]$. In what
follows we will often write proofs as if we are restricting to $j<k$ but all
of the results will follow for the case $j=k$ because of the preceding lemma
(or by natural changes to the indicated maps).

There is an injective $*$-homomorphism $\lambda_{j,k}:C[0,1]\rightarrow
A_{j,k}$ given by

$\lambda_{j,k}(f)=\begin{bmatrix}f&\cdots&0&0&0&0&\cdots&0\\\
\vdots&\cdots&\ddots&\ddots&\ddots&\ddots&\cdots&\vdots\\\
0&\cdots&f&0&0&0&\cdots&0\\\ 0&\cdots&0&f&0&0&\cdots&0\\\
0&\cdots&0&0&f&0&\cdots&0\\\ 0&\cdots&0&0&0&f&\cdots&0\\\
\vdots&\cdots&\ddots&\ddots&\ddots&\ddots&\cdots&\vdots\\\
0&\cdots&0&0&0&0&\cdots&f\end{bmatrix}$

Next we let $E_{j,k}:A_{j,k}\rightarrow A_{j,k}$ be given by sending

$\begin{bmatrix}f_{1,1}&\cdots&0&0&0&0&\cdots&0\\\
0&\cdots&0&0&0&0&\cdots&0\\\
\vdots&\cdots&\ddots&\ddots&\ddots&\ddots&\cdots&\vdots\\\
0&\cdots&f_{j-1,j-1}&0&0&0&\cdots&0\\\
0&\cdots&0&f_{j,j}&f_{j,j+1}&0&\cdots&0\\\
0&\cdots&0&f_{j+1,j}&f_{j+1,j+1}&0&\cdots&0\\\
0&\cdots&0&0&0&f_{j+2,j+2}&\cdots&0\\\
\vdots&\cdots&\ddots&\ddots&\ddots&\ddots&\cdots&\vdots\\\
0&\cdots&0&0&0&0&\cdots&0\\\ 0&\cdots&0&0&0&0&\cdots&f_{k,k}\end{bmatrix}$

to the matrix

$\begin{bmatrix}f_{1,1}&\cdots&0&0&0&0&\cdots&0\\\
0&\cdots&0&0&0&0&\cdots&0\\\
\vdots&\cdots&\ddots&\ddots&\ddots&\ddots&\cdots&\vdots\\\
0&\cdots&f_{1,1}&0&0&0&\cdots&0\\\ 0&\cdots&0&f_{1,1}&0&0&\cdots&0\\\
0&\cdots&0&0&f_{1,1}&0&\cdots&0\\\ 0&\cdots&0&0&0&f_{1,1}&\cdots&0\\\
\vdots&\cdots&\ddots&\ddots&\ddots&\ddots&\cdots&\vdots\\\
0&\cdots&0&0&0&0&\cdots&0\\\ 0&\cdots&0&0&0&0&\cdots&f_{1,1}\end{bmatrix}.$

######  Lemma 2.3.

The map $E_{j,k}$ is a conditional expectation onto $\lambda_{j,k}(C[0,1])$
such that $E_{j,k}(D_{k})=\lambda_{j,k}\left(\mathbb{C}\cdot
1_{[0,1]}\right)$.

###### Proof.

That $E_{j,k}$ is linear and $E_{j,k}^{2}=E_{j,k}$ follows from direct
computation. By Tomiyama’s Theorem [6, Theorem 1.5.10] we need only verify
that $E_{j,k}$ is contractive. So let $X=[f_{m,n}]\in A_{j,k}$ and notice that

$\displaystyle\left\|E_{j,k}\left(X\right)\right\|$
$\displaystyle=\|f_{1,1}(e_{1,1}+e_{2,2}+\cdots+e_{k,k}\|$
$\displaystyle\leq\|f_{1,1}\|\|e_{1,1}+e_{2,2}+\cdots+e_{k,k}\|$
$\displaystyle=\|f_{1,1}\|$ $\displaystyle=\|e_{1,1}Xe_{1,1}\|$
$\displaystyle\leq\|X\|,$

verifying that $E_{j,k}$ is contractive. ∎

Thus we have the following commutative diagrams:

$\textstyle{A_{j,k}}$$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces
D_{k}}$$\textstyle{C[0,1]\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\lambda_{j,k}}$$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\mathbb{C}}$$\scriptstyle{\lambda_{j,k}|_{\mathbb{C}\cdot
1_{[0,1]}}}$

of which all of the maps are injections, and

$\textstyle{C[0,1]\otimes
M_{k}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{E_{j,k}}$$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces
D_{k}}$$\scriptstyle{E_{j,k}|_{D_{k}}}$$\textstyle{C[0,1]}$$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\mathbb{C}}$

with conditional expectations on the vertical arrows. Applying [1, Proposition
2.4] we conclude the following

######  Proposition 2.4.

The induced map
$\Lambda_{j,j+1}:C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\rightarrow
A_{j,k}\underset{\scriptscriptstyle D_{k}}{\displaystyle{\ast}}\,A_{j+1,k}$ is
injective.

We will be focused on free products of multiple algebras at once, so we will
need to extend the result of [1] to apply to multiple free products
simultaneously. To do that we turn to a version of Boca’s Theorem [5] which
was extended in [8]. Essentially it allows us to show that the “free product”
of a finite number of conditional expectations is again a conditional
expectation, given some additional hypotheses on the algebras. We can then use
induction to extend [1, Proposition 2.4].

We refer the reader to the introduction of [8] for the relevant details on the
construction of amalgamated free products. For our purposes, given unital
C∗-algebras $C_{i}$ with common C∗-subalgebra $C$ the amalgamated free product
$C_{1}\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,C_{2}\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,C_{n}$ contains a dense subalgebra spanned by
elements of the form $c_{i_{1}}c_{i_{2}}\cdots c_{i_{m}}$ where $c_{i_{j}}$ is
in one of the $C_{i}$’s, but no two consecutive terms $c_{i_{j}}$ and
$c_{i_{j+1}}$ are contained in the same $C_{i}$. Thus a continuous linear map
with domain $C_{1}\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,C_{2}\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,C_{n}$ is uniquely determined by its action on these
generating elements. Now, when there exist conditional expectations
$E_{i}:C_{i}\rightarrow C$, we can say more. In this case the algebra
$C_{1}\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,C_{2}\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,C_{n}$ is the closure of

$C\oplus\left(\oplus_{1\leq p\leq\infty,i_{k}\neq i_{k+1}}\ker
E_{i_{1}}\otimes\ker E_{i_{2}}\otimes\ker E_{i,p}\right).$

This allows [8] a stronger version of Boca’s theorem which we will utilize in
the following result.

######  Proposition 2.5.

Consider a finite family of unital C∗-algebras with inclusions $B_{i}\subseteq
A_{i}$ and assume that there are common C∗-subalgebras $C^{\prime}\subseteq
B_{i}$ for all $i$, $C\subseteq A_{i}$ for all $i$ and $C^{\prime}\subseteq
C$. Assume for each $i$ there is a surjective conditional expectation
$F_{i}:A_{i}\rightarrow C$. If there are conditional expectations
$E_{i}:A_{i}\rightarrow B_{i}$ with $E_{i}(c)=E_{j}(c)$ for all $c\in C$, and
$E_{i}|_{C}:C\rightarrow C^{\prime}$ is a surjective conditional expectation
for each $i$, then there is a surjective conditional expectation

$G:A_{1}\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,A_{2}\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,A_{k}\rightarrow B_{1}\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,B_{2}\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,B_{k}$

such that $E_{i}=G|_{A_{i}}$ for all $i$.

###### Proof.

Since the maps $E_{i}$ are onto conditional expectations, they are completely
positive and are the identity on their range which is $B_{i}$. Then using the
natural inclusion maps $\iota_{i}:B_{i}\rightarrow
B_{1}\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,B_{2}\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,B_{n}$, we define

$G_{i}=\iota_{i}\circ E_{i}:A_{i}\rightarrow B_{1}\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,B_{2}\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,B_{k}$

and notice that by hypothesis $G_{i}|_{C}=G_{j}|_{C}$ for all $i,j$.

Now let $\mathcal{H}$ be a Hilbert space so that there exists

$\pi:B_{1}\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,B_{2}\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,B_{k}\rightarrow B(\mathcal{H})$

which is a faithful $*$-representation. Then $\pi\circ G_{i}$ is a unital
completely positive map from $A_{i}\rightarrow B(\mathcal{H})$ such that
$\pi\circ G_{i}|_{C}=\pi\circ G_{j}|_{C}$ is a $*$-representation for all
$i,j$. It follows from [8, Theorem 3.4] that there is a unital completely
positive map $\Phi:A_{1}\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,A_{2}\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,A_{n}\rightarrow B(\mathcal{H})$ such that
$\Phi|_{A_{i}}=\pi\circ G_{i}$ and

$\Phi(a_{j_{1}}a_{j_{2}}\cdots a_{j_{k}})=\pi\circ
G_{j_{1}}(a_{j_{1}})\pi\circ G_{j_{2}})(a_{j_{2}})\cdots\pi\circ
G_{j_{k}}(a_{j_{k}})$

when $j_{i}\neq j_{i+1}$ and $a_{j_{i}}\in\ker I_{j_{i}}$.

In particular, the existence of the conditional expectations
$F_{i}:A_{i}\rightarrow C$ means that $A$ is the closed linear span of the
space

$C\oplus\left(\oplus_{m\geq 1}\ker E_{i_{1}}\otimes\cdots\otimes\ker
E_{i_{m}}\right)$

and $\ker E_{i_{j}}\subseteq\ker\pi\circ G_{i_{j}}$. Applying the formula for
$\Phi$ to elements of the form $b_{0}b_{i_{1}}b_{i_{2}}\cdots b_{i_{m}}$ with
$b_{0}\in C^{\prime}$, and $b_{i_{j}}\in\ker F_{j}|_{B_{j}}$ and $i_{j}\neq
i_{j+1}$ establishes that $\Phi$ is a surjective unital completely positive
map onto $\mathop{\mathrm{ran}}\pi$. It follows that $G=\pi^{-1}\circ\Phi$ is
a unital completely positive map from $A_{1}\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,A_{2}\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,A_{k}\rightarrow B_{1}\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,B_{2}\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,B_{k}$. As it is also an idempotent we can
conclude that $G$ is a conditional expectation. ∎

In the absence of the conditional expectation $F_{i}$, we cannot establish the
additional detail that the range of our extended map into $B(\mathcal{H})$ has
range inside the range of $\pi$ so that the argument breaks down. However for
the algebras we’re interested in there is a natural conditional expectation
$F_{j,k}:A_{j,k}\rightarrow D_{k}$. given by

$F_{j,k}\left(\sum_{r,s=1}^{k}e_{r,s}\otimes
f_{r,s}\right)=\sum_{r=1}^{k}f_{r,r}(0)e_{r,r},$

which allows us to apply the following extension of [1, Proposition 2.4].

######  Theorem 2.6.

Consider a finite family of C∗-algebras with inclusions $B_{i}\subseteq A_{i}$
and assume that there are common C∗-subalgebras $C^{\prime}\subseteq B_{i}$
for all $i$, $C\subseteq A_{i}$ for all $i$ and $C^{\prime}\subseteq C$. If
there are conditional expectations $F_{i}:A_{i}\rightarrow C$ and
$E_{i}:A_{i}\rightarrow B_{i}$ , the latter of which when restricted to $C$ is
a conditional expectation onto $C^{\prime}$ then the natural map

$\lambda:B_{1}\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,B_{2}\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,B_{n}\rightarrow
A_{1}\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,A_{2}\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,A_{n}$

is injective.

###### Proof.

The base case is [1, Proposition 2.4] so we assume that it is true for $1\leq
k<n$ and consider the case of $k=n$. Then by the previous proposition there is
a conditional expectation $E_{n-1}:A_{1}\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,A_{2}\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,A_{n-1}\rightarrow B_{1}\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,B_{2}\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,B_{n-1}$ which when restricted to $C$ is a
conditional expectation onto $C^{\prime}$. Then we apply the base case result
to the following commutative diagram of C∗-algebras

$\textstyle{B_{1}\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,B_{2}\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
C^{\prime}}{\displaystyle{\ast}}\,B_{n-1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{C^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{B_{n}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{A_{1}\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,A_{2}\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
C}{\displaystyle{\ast}}\,A_{n-1}}$$\textstyle{C\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{A_{n}}$

to get that the map $\lambda$ is indeed injective. ∎

Applying this to the free products we’re considering the following is a direct
application of the preceding.

######  Corollary 2.7.

There is a natural injection of the $j$-fold free product

$C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]$

into the algebra

$A_{1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{2,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{j,k}$

for all $1\leq j\leq k$.

We now consider the other main inclusion of free products that will play a
result in our results. We start again with introducing some notation. We let
$B_{j,k}$ denote the subalgebra of $A_{j,k}$ of the form

$\begin{bmatrix}\mathbb{C}&\cdots&0&0&0&0&\cdots&0\\\
\vdots&\cdots&\ddots&\ddots&\ddots&\ddots&\cdots&\vdots\\\
0&\cdots&\mathbb{C}&0&0&0&\cdots&0\\\
0&\cdots&0&\mathbb{C}&\mathbb{C}&0&\cdots&0\\\
0&\cdots&0&\mathbb{C}&\mathbb{C}&0&\cdots&0\\\
0&\cdots&0&0&0&\mathbb{C}&\cdots&0\\\
\vdots&\cdots&\ddots&\ddots&\ddots&\ddots&\cdots&\vdots\\\
0&\cdots&0&0&0&0&\cdots&\mathbb{C}\end{bmatrix}.$

Then we can see that as before $B_{m,k}\cong B_{n,k}$ for $m,n\leq k-1$ and
that the algebra $B_{m,k}\cong M_{2}\oplus\mathbb{C}^{k-2}$. In this context
we do not need conditional expectations to get at our result. In fact we have
the following commutative diagram of inclusions of C∗-algebras

$\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern
11.82544pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{A_{m,k}}$}}}}}}}{\hbox{\kern 41.64973pt\raise
0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern-3.0pt\raise-39.32219pt\hbox{\hbox{\kern
0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
35.82544pt\raise-39.32219pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{D_{k}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\kern
6.8464pt\raise-6.03333pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\kern
11.1681pt\raise-68.81107pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy<EMAIL_ADDRESS>0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{B_{m,k}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
0.0pt\raise-6.03333pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx<EMAIL_ADDRESS>
It is a straightforward induction argument using [16, Theorem 4.2] that yields
the following theorem.

######  Theorem 2.8.

The induced map

$\sigma:B_{1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,B_{2,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,B_{l,k}\rightarrow
A_{1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{2,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,B_{l,k}$

is injective for $2\leq l\leq k$.

Now we can see from [11] and noting that $B_{i,k}$ is the graph C∗-algebra
corresponding to $k$ vertices and a single edge connecting the $(i-1)$-vertex
to the $i$-th vertex to see that

$B_{1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,B_{2,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,B_{k-1,k}\cong M_{k}$

and that

$B_{1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,B_{2,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,B_{k,k}$

is the graph algebra associated to a cycle of length $k$ and hence [18] is
isomorphic to $M_{k}\otimes C(\mathbb{T})$.

To understand the free products

$A_{1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{k-1,k}$

and

$A_{1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{k,k}$

we will first notice that the range of the two injections $\pi$ and $\sigma$
together include generating sets for the free product. Hence we can consider
how elements in the ranges of these two injections “multiply” together to get
a sense of the entire free product algebra. In particular, we know the
structure of the ranges of $\pi$ (free products of copies of $C[0,1]$) and
$\sigma$ (full matrix algebras or full matrix algebras tensored with
$C(\mathbb{T})$). The interesting piece is what happens when we consider
elements of the range of $\pi$ multiplied against elements of the range of
$\sigma$. Because we are going to investigate this carefully we will consider
the first algebra and then utilize that in understanding the second algebra.

######  Theorem 2.9.

The algebra $A_{1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{2,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{k-1,k}$ is isomorphic to

$\left(C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\right)\otimes
M_{k}$

where there are $k-1$ copies of $C[0,1]$ in the free product.

###### Proof.

The range of $\sigma$ creates a set of matrix units inside

$\mathcal{A}:=A_{1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{k-1,k}$

which we will denote by $F_{i,j}$. We know that the range of $\sigma$ is the
linear span of the $F_{i,j}$s, that

$F_{i,j}F_{m,n}=\begin{cases}F_{i,n}&m=n\\\ 0&\mbox{ otherwise}\end{cases},$

that $1_{\mathcal{A}}=F_{1,1}+F_{2,2}+\cdots+F_{k,k}$, and $D_{k}$ is the span
of $\\{F_{1,1},F_{2,2},\cdots,F_{k,k}\\}$. More importantly since amalgamation
occurs over $D_{k}$ and as $A_{i,k}$ is a direct sum and a tensor product,
from the universal property of tensor products, we know that inside $A_{i,k}$
the image of $f\in C[0,1]$ will commute with all of the $F_{i,i}$ and

$f=\sum_{i=}^{k}F_{i,i}fF_{i,i}.$

Since this is true for each $f\in C[0,1]$ it must be true for any $F$ in the
range of $\pi$, and hence the range of $\pi$ must be “diagonal” with respect
to the matrix units for $M_{n}$ inside the range of $\sigma$. Then for a
generic multiplication $F_{i,j}F=F_{i,j}F_{j,j}fF_{j,j}$ and
$FF_{i,j}=F_{i,i}FF_{i,i}F_{i,j}$ and hence the algebra $\mathcal{A}$ is
generated inside a matrix algebra over
$C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]$.
That it is onto requires only establishing that there is a representation of
the free product algebra onto the matrix algebra, which follows from the
universal property of the free product with the fact that each of the
$B_{i,k}$s has a natural inclusion into the matrix algebra which is onto a
generating set of that matrix algebra. ∎

We can now use a result of Pedersen [16, Theorem 5.5] to get an analogous
result in the remaining case.

######  Theorem 2.10.

The algebra $A_{1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{2,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{k,k}$ is isomorphic to

$\left(\left(C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\right)\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C(\mathbb{T})\right)\otimes
M_{k}$

where there are $k$ copies of $C[0,1]$ in the free product.

###### Proof.

Consider the commutative pushout diagram

$\textstyle{\mathbb{C}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{C(\mathbb{T})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\left(C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\right)\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C(\mathbb{T})}$

and notice that the maps are proper and hence [16, Theorem 5.5] tells us that
the following commutative diagram is a pushout

$\textstyle{\mathbb{C}\otimes
M_{k}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{C(\mathbb{T})\otimes
M_{k}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\otimes
M_{k}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\left(C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\right)\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C(\mathbb{T})\otimes
M_{k}.}$

In other words

$\left(C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\otimes
M_{k}\right)\underset{\scriptscriptstyle\mathbb{C}\otimes
M_{k}}{\displaystyle{\ast}}\,\left(C(\mathbb{T})\otimes M_{k}\right)$

is isomorphic to

$\left(C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C(\mathbb{T})\right)\otimes
M_{k}.$

We also have a third pushout diagram which puts the algebras we just
recognized in the bottom left and top right corner and the algebra we wish to
describe into the bottom right hand corner:

$\textstyle{B_{1,1}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{2,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{k-1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,B_{k,k}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{B_{1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{2,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{k,k}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{A_{1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{2,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{k-1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,B_{k,k}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{A_{1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{2,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{k,k}.}$

The algebra in the bottom left corner of the second pushout diagram is
isomorphic to both

$A_{1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{2,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{k-1,k}$

and

$A_{2,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{3,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{k,k}.$

The algebra in the upper right corner of the same pushout diagram is
isomorphic to $B_{1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,B_{2,k}\underset{\scriptscriptstyle
D_{K}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{K}}{\displaystyle{\ast}}\,B_{k,k}$. Alternatively, we can recognize these
two algebras as, respectively

$\left(A_{1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{k-1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,D_{k}\right)\underset{\scriptscriptstyle
B_{1,1}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,B_{k-1,k-1}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,D_{k}}{\displaystyle{\ast}}\,\left(B_{1,1}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,B_{k,k}\right)$

and

$\left(D_{k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{2,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{k,k}\right)\underset{\scriptscriptstyle
D_{k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,B_{2,2}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,B_{k,k}}{\displaystyle{\ast}}\,\left(B_{1}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,B_{k}\right),$

which can be rewritten as

$B_{1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{2,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{3,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{k,k}$

and

$A_{1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{2,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{k-1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,B_{k,k}.$

So we can use the previous theorem to turn the third pushout diagram into the
following:

$\textstyle{B_{1,1}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{2,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{k-1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,B_{k,k}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{M_{k}\left(C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C(\mathbb{T})\right)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{M_{k}\left(C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C(\mathbb{T})\right)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{A_{1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{2,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{k,k}.}$

Where there are $k-1$ copies of $C[0,1]$ in both the upper right and bottom
left corners of the commutative diagram. We need only consider how

$B_{1,1}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{2,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{3,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{k-1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,B_{k,k}$

embeds into the two different corners of the commutative diagram. Looking at
the previous theorem on the generators of this subalgebra we can follow the
maps to see that for the top row the embedding is into everything but the
first copy of $C[0,1]$ and the column embedding is into everything but the
last copy of $C[0,1]$. In particular,

$B_{1,1}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{2,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{3,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{k-1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,B_{k,k}$

is isomorphic to

$\left(C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C(\mathbb{T})\right)\otimes
M_{k},$

with $k-2$ copies of $C[0,1]$. The description of

$A_{1,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{2,k}\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{k}}{\displaystyle{\ast}}\,A_{k,k}$

now follows.

∎

We can now consider these results in the context of determining the algebras
C${}^{*}_{\rm max}(T_{n})$ and C${}^{*}_{\rm max}(B_{n})$.

##  3\. Some maximal covers

We start with a result of Blecher [2] which gives the maximal C∗-cover of the
upper triangular $2\times 2$ matrix algebra.

######  Proposition 3.1.

We denote by $\omega$ the function $\sqrt{1-t}\in C[0,1]$ then the inclusion

$\begin{bmatrix}\lambda_{1,1}&\lambda_{1,2}\\\
0&\lambda_{2,2}\end{bmatrix}\mapsto\begin{bmatrix}\lambda_{1,1}&\lambda_{1,2}\omega\\\
0&\lambda_{2,2}\end{bmatrix}$

induces a completely contractive map which generates

${\rm C}^{*}_{\rm max}(T_{2})=\begin{bmatrix}C[0,1]&\omega C[0,1]\\\ \omega
C[0,1]&C_{0}[0,1]\end{bmatrix}.$

The set $\omega C[0,1]$ is a principal ideal which can be identified as those
functions in $C[0,1]$ which are $0$ when evaluated at $1$. A key element of
our analysis is that C${}^{*}_{\rm max}(T_{2})$ can be generated by matrices
of the form

$\begin{bmatrix}f_{1,1}(t)&0\\\ 0&0\end{bmatrix},\begin{bmatrix}0&0\\\
0&f_{2,2}(t)\end{bmatrix},\mbox{ and }\begin{bmatrix}0&\omega\\\
0&0\end{bmatrix}$

where $f_{i,i}\in C[0,1]$. Combining the previous result with another result
of Blecher [2] we can find the maximal C∗-covers of upper triangular $n\times
n$ matrix algebras and certain semicrossed products studied by Peters in [17].
To do this we recognize that these algebras arise as graph operator algebras
[14] corresponding to the directed graphs $L_{n}$ and $C_{n}$, respectively,
where $L_{n}$ is the directed graph with $n$ vertices
$v_{1},v_{2},\cdots,v_{n}$ and $n-1$ edges $e_{1},e_{2},\cdots,e_{n-1}$ where
$s(e_{i})=v_{i}$ and $r(e_{i})=v_{i+1}$ and $C_{n}$ is the $n$-cycle graph.
The key point that we use is from [11] which applies since each edge has
unique range. We can summarize the graph algebra results with the following
restatements of [11, Theorem 4] in this specific context.

######  Theorem 3.2.

Let $A_{1}=T_{2}\oplus\mathbb{C}^{n-2},A_{2}=\mathbb{C}\oplus
T_{2}\oplus\mathbb{C}^{n-3},\cdots A_{n-1}=\mathbb{C}^{n-2}\oplus T_{2}$
viewing each as subalgebras of $M_{n}$, then

$T_{n}=A(L_{n})=A_{1}\underset{\scriptscriptstyle
D_{n}}{\displaystyle{\ast}}\,A_{2}\underset{\scriptscriptstyle
D_{n}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{n}}{\displaystyle{\ast}}\,A_{n-1},$

where amalgamation occurs over the subalgebra of $n\times n$ diagonal
matrices. If we further write $A_{n}$ for the matrix algebra

$\begin{bmatrix}\lambda_{1,1}&0&0&\cdots&0&0\\\
0&\lambda_{2,2}&0&\cdots&0&0\\\ \vdots&\vdots&\ddots&\cdots&\vdots&\vdots\\\
\lambda_{n,1}&0&0&\cdots&0&\lambda_{n,n}\end{bmatrix}\subseteq M_{n}$

then

$A(C_{n})=A_{1}\underset{\scriptscriptstyle
D_{n}}{\displaystyle{\ast}}\,A_{2}\underset{\scriptscriptstyle
D_{n}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{n}}{\displaystyle{\ast}}\,A_{n-1}\underset{\scriptscriptstyle
D_{n}}{\displaystyle{\ast}}\,A_{n}.$

We know from combining universal properties that maximal C∗-covers of free
products, amalgamated over common C∗-subalgebras, are the free products of
maximal C∗-covers amalgamated over the same C∗-subalgebra [2, Proposition
2.2]. Combining this fact with the previous theorem yields the following.

######  Theorem 3.3.

For $n\geq 3$

${\rm C}^{*}_{\rm max}(T_{n})={\rm C}^{*}_{\rm
max}(A_{1})\underset{\scriptscriptstyle D_{n}}{\displaystyle{\ast}}\,{\rm
C}^{*}_{\rm max}(A_{2})\underset{\scriptscriptstyle
D_{n}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{n}}{\displaystyle{\ast}}\,{\rm C}^{*}_{\rm max}(A_{n-1})$

and for $n\geq 2$

${\rm C}^{*}_{\rm max}(A(C_{n}))={\rm C}^{*}_{\rm
max}(A_{1})\underset{\scriptscriptstyle D_{n}}{\displaystyle{\ast}}\,{\rm
C}^{*}_{\rm max}(A_{2})\underset{\scriptscriptstyle
D_{n}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle
D_{n}}{\displaystyle{\ast}}\,{\rm C}^{*}_{\rm
max}(A_{n-1})\underset{\scriptscriptstyle D_{n}}{\displaystyle{\ast}}\,{\rm
C}^{*}_{\rm max}(A_{n})$

It is a straightforward application of the fact the maximal C∗-cover of a
C∗-algebra is the C∗-algebra and that maximal C∗-covers of direct sums are
direct sums of the C∗-covers to see that for $1\leq i\leq n-1$, C${}^{*}_{\rm
max}(A_{i})=\mathbb{C}^{i-1}\oplus C^{*}_{\rm
max}(T_{2})\oplus\mathbb{C}^{n-(i+1)}$ and

${\rm C}^{*}_{\rm max}(A_{n})=\begin{bmatrix}C[0,1]&0&0&\cdots&0&\omega
C[0,1]\\\ 0&0&0&\cdots&0&0\\\ \vdots&\vdots&\ddots&\cdots&\vdots&\vdots\\\
\omega C[0,1]&0&0&\cdots&0&C[0,1]\end{bmatrix}.$

Viewing each of these algebras as subalgebras of $M_{n}\otimes C[0,1]$ we see
how the algebras from the previous section come into play.

######  Proposition 3.4.

The maximal C∗-cover of $T_{n}$ and $A(C_{k})$ are subalgebras of

$\left(C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\right)\otimes
M_{n}$

and

$\left(C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C(\mathbb{T})\right)\otimes
M_{k},$

respectively.

###### Proof.

Since all of the algebras C${}^{*}_{\rm max}(A_{i})$ contain the diagonal
algebras $D_{n}$ and amalgamation for the maximal C∗-algebras and the algebra
$A$ occur over the same C∗-subalgebra, $D_{n}$, we can apply the result of
Pedersen [16, Theorem 5.5] directly. ∎

In theory, this gives us a practical method of computing the maximal C∗-covers
for these algebras. We just determine the subalgebra generated by the
generating subsets of the algebras that make up the free product. However this
analysis is not necessarily amenable to a nice closed form solution. We will
start by illustrating this result in the context of $T_{3}$ where the
computations are manageable. We are dealing with multiple copies of $C[0,1]$
so we will introduce some notation to keep track of where algebra elements
lie.

Considering
$C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]$
the two algebras separately are continuous functions in $t$ and hence the free
product can be viewed as functions in two noncommuting self-adjoint variables
$t_{1}$ and $t_{2}$. In general, we will write $C\langle
t_{1},t_{2},\cdots,t_{n}\rangle$ as shorthand for
$C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,\cdots\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]$
so that we can track which copy of $C[0,1]$ a function might appear in.
Similarly, we will write $\omega_{i}$ to represent $\sqrt{1-t_{i}}$ in the
$i$-th copy of $C[0,1]$, since it plays an important role in the maximal
C∗-cover.

For a collection of elements $\\{f_{1},f_{2},\cdots,f_{j}\\}\in C\langle
t_{1},t_{2},\cdots,t_{n}\rangle$ we write

  * •

$(f_{i})C\langle t_{1},t_{2},\cdots,t_{n}\rangle$ to denote the closed
subspace consisting of all elements of the form $f_{i}A$ where $A\in C\langle
t_{1},t_{2},\cdots,t_{n}\rangle$,

  * •

$C\langle t_{1},t_{2},\cdots,t_{n}\rangle(f_{i})$ to denote the closed
subspace consisting of all elements of the form $Af_{i}$ where $A\in C\langle
t_{1},t_{2},\cdots,t_{n}\rangle$,

  * •

and, $(f_{i})C\langle t_{1},t_{2},\cdots,t_{n}\rangle(f_{j})$ to denote the
closed subspace consisting of all elements of the form $f_{i}Af_{j}$ where
$A\in C\langle t_{1},t_{2},\cdots,t_{n}\rangle$. Note here that $i$ may equal
$j$.

Having established the notation we provide the following characterizations of
the maximal C∗-cover for $T_{3}$.

######  Proposition 3.5.

${\rm C}^{*}_{\rm max}(T_{3})=\begin{bmatrix}C\langle
t_{1}\rangle+\omega_{1}C\langle
t_{1},t_{2}\rangle\omega_{1}&\omega_{1}C\langle
t_{1},t_{2}\rangle&w_{1}C\langle t_{1},t_{2}\rangle\omega_{2}\\\ C\langle
t_{1},t_{2},\rangle\omega_{1}&C\langle t_{1},t_{2}\rangle&C\langle
t_{1},t_{2}\rangle\omega_{2}\\\ \omega_{2}C\langle
t_{1},t_{2}\rangle\omega_{1}&\omega_{2}C\langle t_{1},t_{2}\rangle&C\langle
t_{2}\rangle+\omega_{2}C\langle t_{1},t_{2}\rangle\omega_{2}\end{bmatrix}.$

###### Proof.

We will denote by $\mathfrak{A}$ the subset of $M_{3}\otimes C\langle
t_{1},t_{2},t_{3}\rangle$ given by

$\begin{bmatrix}C\langle t_{1}\rangle+\omega_{1}C\langle
t_{1},t_{2}\rangle\omega_{1}&\omega_{1}C\langle
t_{1},t_{2}\rangle&w_{1}C\langle t_{1},t_{2}\rangle\omega_{2}\\\ C\langle
t_{1},t_{2},\rangle\omega_{1}&C\langle t_{1},t_{2}\rangle&C\langle
t_{1},t_{2}\rangle\omega_{2}\\\ \omega_{2}C\langle
t_{1},t_{2}\rangle\omega_{1}&\omega_{2}C\langle t_{1},t_{2}\rangle&C\langle
t_{2}\rangle+\omega_{2}C\langle t_{1},t_{2}\rangle\omega_{2}\end{bmatrix}.$

Straightforward calculations will verify that $\mathfrak{A}$ is a linear
subspace of $M_{3}\otimes C\langle t_{1},t_{2}\rangle$. Similarly one can use
matrix multiplication to see that it is, in fact, a C∗-subalgebra.

Now the inclusion

$\begin{bmatrix}\lambda_{1,1}&\lambda_{1,2}&\lambda_{1,3}\\\
0&\lambda_{2,2}&\lambda_{2,3}\\\
0&0&\lambda_{3,3}\end{bmatrix}\mapsto\begin{bmatrix}\lambda_{1,1}&\lambda_{1,2}\omega_{1}&\lambda_{3,1}\omega_{1}\omega_{2}\\\
0&\lambda_{2,2}&\lambda_{2,3}\omega_{2}\\\ 0&0&\lambda_{3,3}\end{bmatrix}$

gives an inclusion of $T_{3}\subseteq\mathfrak{A}$. The proof then comes down
to verifying that every element of $\mathfrak{A}$ is contained in the algebra
generated by the range of these two inclusions.

Since we know that $T_{2}$ embeds into $T_{3}$ as $2\times 2$ matrix
subalgebras in two ways we have that C${}^{*}_{\rm max}(T_{2})$ embeds into
$M_{3}\otimes C\langle t_{1},t_{2}\rangle$ and in the same way in particular
we have that it embeds in $\mathfrak{A}$ in similar matrix constructions and
hence the range of $T_{3}$ must generate, at minimum the following subsets of
$\mathfrak{A}$:

$\begin{bmatrix}C\langle t_{1}\rangle&\omega_{1}&0\\\ 0&C\langle
t_{1}\rangle&0\\\ 0&0&0\end{bmatrix}\mbox{ and }\begin{bmatrix}0&0&0\\\
0&C\langle t_{2}\rangle&\omega_{2}\\\ 0&0&C\langle t_{2}\rangle\end{bmatrix}.$

Considering adjoints and focusing on the multiplication in the $2$-$2$ entry
we can generate the subset of $\mathfrak{A}$ of the form

$\begin{bmatrix}C\langle t_{1}\rangle&\lambda_{1,2}\omega_{1}&0\\\
\lambda_{2,1}\omega_{1}&C\langle t_{1},t_{2}\rangle&\lambda_{2,3}\omega_{2}\\\
0&\lambda_{3,2}\omega_{2}&C\langle t_{2}\rangle\end{bmatrix}$

where the $\lambda_{1,j}$ are complex scalars. Considering the multiplication
of two elements of that form and linear combinations we get matrices of the
form

$\begin{bmatrix}f+\omega_{1}g_{1,1}\omega_{1}&\omega_{1}g_{1,2}&\omega_{1}g_{1,3}\omega_{2}\\\
g_{2,1}\omega_{1}&g_{2,2}&g_{2,3}\omega_{2}\\\
\omega_{2}g_{3,1}\omega_{1}&\omega_{2}g_{3,2}&h+\omega_{2}g_{3,3}\omega_{2}\end{bmatrix}$

where $f\in C\langle t_{1}\rangle$, $h\in C\langle t_{2}\rangle$ and the
$g_{i,j}\in C\langle t_{1},t_{2}\rangle$. Since this describes every element
of the closed subalgebra $\mathfrak{A}$ we have the intended result.

∎

Since
$C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]$
is not exact by [20] we already, in this “simple” nonselfadjoint operator
algebra, see that the maximal C∗-cover is not exact (this is similar in spirit
to the “simple” case of $M_{2}(\mathbb{C})$ in [13]).

######  Corollary 3.6.

For $n\geq 2$, ${\rm C}^{*}_{\rm max}(T_{n})$ is not exact and ${\rm
C}^{*}_{\rm max}(A(C_{n}))$ is not exact.

###### Proof.

By the previous proposition we know that this result is true for $T_{3}$. In
general, though we can see that for $n\geq 3$ the $2$-$2$ entry of the maximal
C∗-cover of $T_{n}$ will, at minimum, contain a copy of $C\langle
t_{1},t_{2}\rangle$ and hence they are all non-exact when $n\geq 2$. The same
subalgebra will be in the $2$-$2$ corner of C${}^{*}_{\rm max}(A(C_{n}))$
giving us non-exactness for these algebras as well. ∎

In addition to this pathology of the maximal C∗-covers, the algebraic
calculations for bigger values of $n$ quickly become overwhelming. Considering
even the case of $T_{4}$ begins to illustrate the difficulty of generating a
general expression for $T_{n}$.

######  Example 3.7.

We focus on the $1$-$4$ entry in C${}^{*}_{\rm max}(T_{4})$. Considering
multiplications of generating elements as in the proof of the previous
proposition, we can get at least all the elements of the form
$\omega_{1}C\langle t_{1},t_{2}\rangle\omega_{2}C\langle
t_{2},t_{3}\rangle\omega_{3}$ but the set of such elements is not a subspace.
Hence one must consider the closed span of all elements of that form in the
$1$-$4$ entry. It quickly becomes unclear what a general expression would look
like, and those problems only compound as the number of variables increases.

Finally, we will consider the graph C∗-algebra for the $2$-cycle graph,
although we will not get a complete answer here. We will present a plausible
candidate for the maximal C∗-algebra although as before generalizing to longer
cycle-graphs is not obvious or straightforward how to proceed.

######  Example 3.8.

To determine this algebra we recognize it as the C∗-subalgebra of
$A_{1,2}\underset{\scriptscriptstyle D_{2}}{\displaystyle{\ast}}\,A_{2,2}$
generated by the matrices (abusing notation) $\begin{bmatrix}0&\omega_{1}\\\
0&0\end{bmatrix}$, $\begin{bmatrix}0&\omega_{2}\\\ 0&0\end{bmatrix}$ and
$\begin{bmatrix}f\langle t_{1},t_{2}\rangle&0\\\ 0&g\langle
t_{1},t_{2}\rangle\end{bmatrix}$ inside
$C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C[0,1]\underset{\scriptscriptstyle\mathbb{C}}{\displaystyle{\ast}}\,C(\mathbb{T})\otimes
M_{2}$. This looks like, as in the previous example, matrices of the form

$\begin{bmatrix}C\langle t_{1},t_{2}\rangle&\begin{matrix}C\langle
t_{1},t_{2}\rangle\omega_{1}C\langle t_{1},t_{2}\rangle\\\ +C\langle
t_{1},t_{2}\rangle\omega_{2}C\langle t_{1},t_{2}\rangle\end{matrix}\\\
\begin{matrix}C\langle t_{1},t_{2}\rangle\omega_{1}C\langle
t_{1},t_{2}\rangle\\\ +C\langle t_{1},t_{2}\rangle\omega_{2}C\langle
t_{1},t_{2}\rangle\end{matrix}&C\langle t_{1},t_{2}\rangle\end{bmatrix}.$

Notice that the copy of $C(\mathbb{T})$ is generated by
$M_{2}\underset{\scriptscriptstyle D_{2}}{\displaystyle{\ast}}\,M_{2}$ inside
$A_{1,2}\underset{\scriptscriptstyle D_{2}}{\displaystyle{\ast}}\,A_{2,2}$ the
generators of which are not inside this subalgebra.

## References

  * [1] Armstrong, S., Dykema, K., Exel, R., Li, X.: On embeddings of full amalgamated free product C∗-algebras. Proc. Am. Math. Soc. (2004). https://doi.org/10.1090/S0002-9939-04-07370-8
  * [2] Blecher, D.: Modules over operator algebras, and the maximal C∗-dilation. J. Funct. Anal. (1999). https://doi.org/10.1006/jfan.1999.3491
  * [3] Blecher, D., Le Merdy, C.: Operator Algebras and Their Modules—an Operator Space Approach. Oxford University Press, Oxford (2004)
  * [4] Blecher, D., Duncan, B.: Nuclearity-related properties for nonselfadjoint algebras. J. Oper. Theory. 65, 47–70 (2011)
  * [5] Boca, F.: Free products of completely positive maps and spectral sets. J. Funct. Anal. (1991). https://doi.org/10.1016/0022-1236(91)90001-L
  * [6] Brown, N., Ozawa, N.: C∗-algebras and Finite-Dimensional Approximations. American Mathematical Society, Providence (2008)
  * [7] Clouâtre, R., Ramsey, C.: Residually finite-dimensional operator algebras. J. Funct. Anal. (2019). https://doi.org/10.1016/j.jfa.2018.12.016
  * [8] Davidson, K., Kakariadis, E.: A proof of Boca’s theorem. Proc. R. Soc. Edinb., Sect. A, Math. (2019). https://doi.org/10.1017/prm.2018.50
  * [9] Davidson, K., Kennedy, M.: Noncommutative Choquet Theory, preprint (2019).
  * [10] Duncan, B.: Explicit construction and uniqueness for universal operator algebras of directed graphs. J. Lond. Math. Soc. (2005). https://doi.org/10.1112/S0024610705006940
  * [11] Duncan, B.: Certain free products of graph operator algebras. J. Math. Anal. Appl. (2010). https://doi.org/10.1016/j.jmaa.2009.11.023
  * [12] Duncan, B.: Exactness of universal free products of finite dimensional C∗-algebras with amalgamation. Oper. Matrices. (2012). https://doi.org/10.7153/oam-06-02
  * [13] Kirchberg, E., Wassermann, S.: C∗-algebra generated by operator systems. J. Funct. Anal. (1998). https://doi.org/10.1006/jfan.1997.3226
  * [14] Kribs, D. Power, S.: Free semigroupoid algebras. J. Ramanujan Math. Soc. 19, 117–159 (2004)
  * [15] Loring, T.: Lifting Solutions to Perturbing Problems in C∗-algebras. American Mathematical Society, Providence (1997)
  * [16] Pedersen, G.: Pullback and pushout constructions in C∗-algebra theory. J. Funct. Anal. (1999). https://doi.org/10.1006/jfan.1999.3456
  * [17] Peters, J.: Semicrossed products of C∗-algebras. J. Funct. Anal. (1984). https://doi.org/10.1016/0022-1236(84)90063-6
  * [18] Raeburn, I.: Graph Algebras. American Mathematical Society, Providence (2005)
  * [19] Thompson, I.: Maximal C∗-covers and residual finite-dimensionality. J. Math. Anal. Appl. (2022). https://doi.org/10.1016/j.jmaa.2022.126277
  * [20] Wassermann, S.: On tensor products of certain group C∗-algebras. J. Funct. Anal. (1976). https://doi.org/10.1016/0022-1236(76)90050-1


# APAR: LLMs Can Do Auto-Parallel Auto-Regressive Decoding

Mingdao Liu1,†,∗, Aohan Zeng1,2,∗, Bowen Wang1,†, Peng Zhang2, Jie Tang1,
Yuxiao Dong1

1Tsinghua University 2Zhipu AI

###### Abstract

The massive adoption of large language models (LLMs) demands efficient
deployment strategies. However, the auto-regressive decoding process, which is
fundamental to how most LLMs generate text, poses challenges to achieve
efficient serving. In this work, we introduce a parallel auto-regressive
generation method. By instruct-tuning on general domain data that contains
hierarchical structures, we enable LLMs to independently plan their generation
process and perform auto-parallel auto-regressive (APAR) generation,
significantly reducing the number of generation steps. APAR alone can achieve
up to 2$\times$ speed-up, and when combined with speculative decoding, the
speed-up can reach up to 4$\times$. In addition, APAR reduces the key-value
cache consumption and attention computation during generation. This leads to a
throughput increase of 20-70% and a latency reduce of 20-35% in high-
throughput scenarios, compared to state-of-the-art serving frameworks.

APAR: LLMs Can Do Auto-Parallel Auto-Regressive Decoding

Mingdao Liu1,†,∗, Aohan Zeng1,2,∗, Bowen Wang1,†, Peng Zhang2, Jie Tang1,
Yuxiao Dong1 1Tsinghua University 2Zhipu AI

∗ Equal contribution.† Work done while these authors interned at Zhipu AI.

##  1 Introduction

Large language models (LLMs) (OpenAI, 2023; Touvron et al., 2023; Zeng et al.,
2022) have increasingly become foundational to various AI applications
(Richards, 2023; Nakajima, 2023; Park et al., 2023; Zhou et al., 2023). This
widespread adoption has led to a growing demand for efficient model
deployment, i.e., low latency and high throughput (Aminabadi et al., 2022).
However, the intrinsic auto-regressive (AR) structure of these models presents
significant challenges in achieving more efficient serving (Radford et al.,
2018).

Figure 1: APAR Decoding Overview. Different from the original auto-regressive
decoding, APAR detects potential parts to be generated in parallel and issues
multiple generation threads.

First, each new token is auto-regressively generated conditioned on the entire
set of previously-generated tokens. This incremental decoding process results
in sub-optimal generation speeds, as each generation step requires accessing
the vast number of parameters of a LLM (Aminabadi et al., 2022). Consequently,
when the generation batch size is not sufficiently large, this process becomes
memory-bound, resulting in an under-utilization of the GPU compute.

Second, the computation of attention over all preceding tokens in Transformer
(Vaswani et al., 2017) also limits the serving throughput. In high-throughput
scenarios, many sequences are generating in parallel and the generation
process becomes computation-bound. Meanwhile, the computation cost of
attention scales linearly with the sequence length, which hinders further
improvements of the throughput, especially for long responses. In addition,
the caching of key and value tensors (KV cache) for generated tokens, despite
advancements in memory-efficient algorithms (Kwon et al., 2023), scales
linearly with the sequence length, constraining the number of concurrent
requests that a system can handle.

In light of these challenges, we introduce the Auto-Parallel Auto-Regressive
(APAR) decoding strategy with the goal of improving the inference efficiency
of LLMs. APAR leverages the inherent parallelizable structure in LLM
generation, capitalizing on LLMs’ understanding of text structures. By fine-
tuning LLMs on corpora with hierarchical structures, the models can learn to
autonomously initiate parallel generation threads when encountering
parallelizable response structures. This approach transforms the conventional
linear generation into a parallelizable paragraph tree structure. This not
only facilitates greater decoding parallelism but also reduces attention spans
through tree-based attention mechanisms, and enables the earlier release of
consumed KV cache memory.

We perform experiments on the Vicuna family of models. In memory-bound
scenarios, APAR can help reduce the model latency and achieve an average
generation speed increase of 2$\times$ on Vicuna Bench (Chiang et al., 2023).
Furthermore, the design of APAR is complementary to most existing inference
acceleration methods. For example, when combined with Medusa (Cai et al.,
2023), a speculative decoding strategy, APAR-based models yield speed
improvements of up to 4$\times$ on Vicuna Bench. In certain specific
categories, this combination even achieves a speed-up of up to 6$\times$.

In high-throughput scenarios, APAR’s compatibility with vLLM enables early
memory release, reducing KV cache requirements by up to 50% while still
maintaining the same level of throughput. In addition, APAR reduces the number
of tokens involved in attention calculation. By using the same amount of KV
cache memory, it gets a 20-70% improvement in throughput over the original AR
process, and achieves a 20-35% reduction in latency while maintaining the same
serving concurrency.

Importantly, the quality of generation with APAR is not compromised.
Evaluations across multiple categories on the MT Bench and Vicuna Bench (Zheng
et al., 2023) demonstrate that the response quality remains largely
consistent, with variations within a $\pm$2% range compared to its AR
counterparts. This indicates that APAR-based models retain the contextual
generation capability while enhancing the decoding speed and efficiency.

##  2 Auto-Parallel Auto-Regressive Decoding

###  2.1 Overview

Parallelizable structures are ubiquitous in the response of LLMs. For
instance, in the ShareGPT dataset, 58% of the dialogues contain at least one
response of ordered or unordered lists from ChatGPT, and about 32% of the
responses contains listed structure. Most listed structures are naturally
suitable for paralleled generation, since the details of an itemized paragraph
is usually conditioned on its leading sentence or phrase.

Figure 2: APAR Training Inputs. Based on pre-defined rules, the _original
sequence_ is transformed into a _paragraph tree_ , which is used to train APAR
models. Any token attends only to tokens on its path to root. Figure 3: APAR
Decoding. Suppose we are generating a sequence $p_{0}-p_{1}-p_{2}$. The
decoding of $p_{1}$(root) and $p_{0}$(detail) are issued in parallel at
($t_{1}+1$). Similarly, $p_{2}$(root) and $p_{1}$(detail) are issued at
($t_{2}+1$). Prefix tokens are shared and forked generation threads can be
released once finished.

The key idea of APAR is to make LLMs explicitly aware of such parallelizable
structures, and spawn auto-parallel auto-regressive decoding threads
accordingly. Specifically, APAR involves two key components. First, we post-
train the LLMs with hierarchical text structures, which we referred to as
_paragraph nodes_ (Section 2.2). Second, we design the decoding algorithm to
support parallel decoding operations, including maintaining the hierarchical
structure in generation and restoring it into a linear sequence (Section 2.3).

###  2.2 Input Format

This section introduce the corpora used to fine-tune APAR models, including
the tree structure, attention mechanism and control tokens. See Section 3.2
for data pre-processing details.

#### Paragraph tree.

As illustrated in Fig 2, a paragraph tree is used to represent a sequence with
hierarchical structure. Each node in the tree, which is referred to as a
_paragraph node_ in the sections to follow, denotes a component of the
generation response. Each paragraph node has 0 or 2 pointers. One pointer of
the paragraph node is referred to as _first child_ (blue arrow in Fig 2),
which points to the detailed texts (sub-paragraph) of the paragraph; the other
child pointer is _next sibling_ (red arrow in Fig 2), which points to the next
paragraph of the same hierarchical level.

#### Control tokens.

To enable the language model to spawn a parallel decoding thread, 2 control
tokens are added to the vocabulary.

  * •

Fork Identifier. [Fork] is used to indicate a parallel-able structure in the
response. Models are trained to output a [Fork] token when they discover that
what follows is considered detailed information (or a sub-paragraph) and thus
can be decoded together with the next paragraph of the same level. When the
inference system detects a [Fork] token output by the model, it creates a
paralleled decoding thread sharing the same prefix until that [Fork] token.
This token works just like the `fork()` system call used in operating systems.

  * •

Child Identifier. [Child] always follows a [Fork], and is used to indicate
that the following content is the beginning of a sub-paragraph lead by the
previous content, like the zero return value of `fork()` in some operating
systems. In particular, [Child] is attended to but is not taken loss in the
training process. Thus, the model never learns to output this token, but
learns to output the content of the sub-paragraph when [Child] is injected
into the context (i.e. a [Fork] [Child] sequence appears in the context). On
the other hand, when [Fork] appears without followed by a [Child], the model
will generate the next paragraph of the same level.

#### Training attention.

In order for the paragraphs to be generated in a parallel, all nodes only
attend to their ancestors, and to themselves with a causal mask, as shown in
Fig 2.

###  2.3 Decoding Procedures

Algorithm 1 APAR decoding algorithm. IsFinished($G$) returns True if all
sequences in the sequence group $G$ have finished. Sample($\Theta$, $s$)
samples the next token for sequence $s$ given language model $\Theta$. A
paragraph node $n$ associated with sequence $s$ points to slice
$s[\text{start:end}]$ ($s[\text{start:}]$ if end is _null_). PNode(s, $x$)
creates a new paragraph node associated with sequence $s$, initializing
start=$x$, end=_null_. The current_node attribute of a sequence is used to
record the leaf paragraph node pointing to the end of the sequence, and is
maintained (line 25$\sim$29) every time a new sequence is forked. Restore($r$)
recursively traverse the paragraph tree defined by root $r$ in root -
first_child - next_sibling order.

1:Input: A user prompt sequence $p$, language model $\Theta$.

2:Output: Decoded generation sequence $g$.

3:

4:$r\leftarrow$ PNode($p$, $p$.len)

5:$G\leftarrow\\{p\\}$

6:$p$.current_node $\leftarrow r$

7:

8:while not IsFinished(G) do

9: $G\leftarrow$ AparDecode(G, $\Theta$)

10:

11:$g\leftarrow$ Restore($r$)

12:return g

13:

14:function AparDecode($G$, $\Theta$)

15: for each sequence $s$ in $G$ do

16: if $s$.finished = True then

17: continue

18: $x\leftarrow$Sample($\Theta$, s)

19: if $s.\text{last\\_token}$ = [Fork] then

20: $s^{\prime}\leftarrow s$

21: $s^{\prime}.$append_token([Child])

22: $G\leftarrow G\cup\\{s^{\prime}\\}$

23: $n\leftarrow$ PNode($s$, $s$.len)

24: $n^{\prime}\leftarrow$ PNode($s^{\prime}$, $s^{\prime}$.len)

25: $s$.current_node.end $\leftarrow s$.len

26: $s$.current_node.next_sibling $\leftarrow n$

27: $s$.current_node.first_child $\leftarrow n^{\prime}$

28: $s$.current_node $\leftarrow n$

29: $s^{\prime}$.current_node $\leftarrow n^{\prime}$

30: $s.$append_token($x$)

31: if $x$ = [EOS] then

32: $s.$finish $\leftarrow$ True

33: ReleaseCache(s)

34: return $G$

An overview of the generation process is illustrated in Fig. 3 and the
algorithm is formulated in Algorithm 1. We first introduce the concept of
sequence and sequence groups following the implementation in Kwon et al.
(2023), then expound the generating procedures of APAR decoding algorithm.

#### Sequence and sequence group.

A sequence is defined as an ordered list of tokens. A sequence group is the
set of all sequences generated for the same prompt sequence and is initialized
with only the prompt sequence. In APAR decoding algorithm, each sequence group
corresponds to a paragraph tree.

Each sequence, on the other hand, is a generation thread and is associated
with a leaf node in the paragraph tree.

#### Decoding.

As described in Algorithm 1, we start the decoding with the user prompt
sequence $p$ and construct a sequence group $G$ initialized as {$p$}. We
initialize the paragraph tree corresponding to $G$ with root node $r$ and
associate sequence $p$ with $r$ (which is now a leaf node). Then, we iterative
perform AparDecode on sequence group $G$ until all sequences in $G$ have
finished. In the end, the paragraph tree is traversed to restore the
sequential output $g$.

Next, we delve into the details for AparDecode, which performs a single decode
step for sequence group $G$ with language model $\Theta$. For each unfinished
sequence $s$ in $G$, If the last token is [Fork], it means that the model
calls for a new generation thread, and now it’s time to fork the sequence
$s^{\prime}$. The forked sequence shares the same prefix tokens as the parent
sequence. When implementation with paged attention (Kwon et al., 2023), the
fork operation creates a shared memory mapping for the shared prefix (the
dotted red box in Fig 3), which _copies at most 1_ KV cache block and _shares_
all other blocks. After the fork operation, $s^{\prime}$ is appended a forced
[Child] token to identify this sequence to the language model as a child
sequence. Also, two new leaf nodes are created and $s$ and $s^{\prime}$ are
set to track the latest leaf nodes.

Finally, sampled new token $x$ is appended to $s$. If [EOS] token is sampled,
the generation of sequence $s$ is considered finished, and the KV cache
belonging _only_ to $s$ is released (the dotted red box in Fig 3).

###  2.4 Features

Based on the aforementioned decoding algorithm and the distribution of user
queries, we identify three key features of APAR decoding that give rise to its
superior performance in terms of inference latency, throughput, and memory
consumption.

#### 1\. Paralleled decoding structure reduces latency.

Through training on paragraph trees, the language model becomes an automatic
online miner for parallel-able structure and concurrent generation threads are
issued accordingly. The paralleled generation reduces generation steps. In
memory-bound scenarios, the latency in each step remains roughly unchanged
wrt. different level of decoding parallelism (i.e. dynamic batch size) and the
latency can therefore be reduced proportionately (Fig 4).

#### 2\. Early release of child KV cache reduces memory consumption.

In the auto-regressive generation process, the KV cache of all tokens must be
retained before the sequence is completely generated. In APAR, however, once a
forked sequence (i.e. a generation thread) completes generation, the KV cache
belonging only to the forked sequence can be released immediately, while the
remaining part of the generation continues. Under the effect of early release
strategy, as shown in later Fig 5(a), up to $50\%$ of the generation cache can
be saved while throughput remains the same.

#### 3\. Reduced attention length saves computation.

Auto-regressive generation requires a token to attend to all previously
generated tokens. In APAR, on the other hand, a new token only attends to
tokens along its path to the root of the paragraph tree, which reduces
attention computation in generation. In a heavily-batched generation setting,
latency incurred by memory access is amortized by the intense batched
computation, make the generation process primarily computation-bound. Thus,
the computation reduction in each token results in an improvement in
throughput across different memory usages (Fig 5(a)), as well as reduction in
latency with different extents of concurrency (Fig 5(b)).

##  3 Experiments

###  3.1 Data Pre-processing

We adopt one open-sourced version of ShareGPT
dataset111https://huggingface.co/datasets/anon8231489123/ShareGPT_Vicuna_unfiltered
as instruction corpora. Fine-tuning data are composed as follows.

#### Ordered list.

Many responses are represented as ordered lists with the pattern of `root -
detail` for each bullet point, where `root` is usually an introduction phrase
and `detail` is the detailed content of that specific point. Thus, the `root`
is extracted as the content for the root node and `detail` as the content in
the detail node, as illustrated in Fig 2.

#### Paragraph.

Most of LLM’s response paragraphs are structured in a root-and-details format,
even when not presented as an ordered list, where the first sentence of the
paragraph typically summarizes the main idea of that paragraph. Therefore, we
extract the first sentence of the paragraph as the `root` for that section,
while the rest of the content serves as the `detail`.

#### Unstructured data.

To accurately extract the hierarchical structure, responses with confusing
formats, like code and math data, are excluded in the aforementioned structure
extraction process. However, while learning to generate paralleled decoding
threads, a model must also learn not to generate [Fork] in cases where
coherent attention is necessary to accurately predict the next token.
Therefore, some filtered conversations are added as negative examples to
prevent the model from excessive [Fork] issuing. This portion of data is
organized as a single paragraph node with no descendants.

See Appendix B for detailed procedures and rules used in data pre-processing.

(a) Results in Vicuna Bench

(b) Results in MT Bench

Figure 4: Generation speed in memory-bound scenario. Models served on one
H800-SXM5-80G GPU with batch size 1.

###  3.2 Experimental Setup

#### Models.

To evaluate the generation speed, throughtput and qualities, we apply APAR
fine-tuning on vicuna-v1.3-{7B,13B} models, producing APAR-{7B,13B}. In this
section, original Vicuna models will be referred to as Original-{7B,13B}
(O-{7B,13B} as abbreviations) and the fine-tuned APAR models will be referred
to as APAR-{7B,13B} (A-{7B,13B} as abbreviations).

#### Implementation.

We implement 3 settings for evaluation, including

  * •

Vanilla-APAR. Vanilla-APAR is implemented directly with `transformers` (Wolf
et al., 2020), which is a widely adopted python deep learning platform for
transformer-based models.

  * •

Medusa-APAR. Medusa-APAR is implemented with Medusa (Cai et al., 2023), which
is an open-source speculative decoding algorithm that follows the predict -
verify paradigm for decoding. Medusa adopts a light-weighed extra language
modeling head to predict the next few tokens and verify generation using tree
attention. This setting is used to test the combined effect of APAR and
speculative decoding algorithm.

  * •

Batched-APAR. Batched-APAR is implemented with vLLM (Kwon et al., 2023), a
high-throughput and memory-efficient inference engine using paged-attention
mechanism. This setting is used to test APAR on realistic serving situations,
where we not only care about the latency but also throughput and memory
efficiency.

#### Training setup.

During the fine-tuning process, we sample from structured (ordered list and
paragraph mentioned above, 16k samples) and unstructured data (9k samples)
with sampling ratio 1:1. The models are fine-tuned with batch size 128,
learning rate $2e\text{-}5$ for 2000 steps. After fine-tuning, we train 2
medusa heads with learning rate 1$e$-3 for 2000 steps using the same data as
fine-tuning. See Appendix A for detailed hyper-parameter settings.

#### Evaluation datasets.

Several datasets are used to evaluate the generation statistics and quality.

  * •

Vicuna Bench (Chiang et al., 2023) is a benchmark for evaluating LLMs on
language understanding, reasoning and context awareness. It covers 9
categories and contains 80 single-turn queries. For a clearer layout, we
abbreviate 2 long category names in Vicuna Bench in the following figures and
tables, i.e. Commonsense to CS, Counterfactual to CF.

  * •

MT Bench (Zheng et al., 2023) is a benchmark consisting of 80 multi-turn
questions. It covers 8 common categories and can be used to evaluate the
multi-turn conversation and instruction-following ability of LLMs.

  * •

APAR Test Set consists of 1000 user queries sampled from ShareGPT dataset to
simulate the query distribution in realistic deployment scene using the same
rule we extract structured training data. Because of its large quantity, it’s
would be too expensive to evaluate generation quality for all test set queries
on all models. Thus, APAR test set is only used for measurement of generation
statistics.

###  3.3 Results in Memory-Bound Scenarios

We inspect how APAR reduces generation latency in a memory-bound (i.e. small
batch size) scenario, as well as its combined acceleration effect with
speculative decoding. Considering that the the model is re-trained and the
output length can be different on the same prompt, we normalize generation
latency with generated tokens, adopting tokens per second as the metric for
generation speed. The results are reported with batch size fixed as 1 and
prefix sharing is not enabled.

As shown in Fig 4, Vanilla-APAR achieves $2\times$ average speed up in Vicuna
Bench and $1.4\times$ average speed up on MT Bench. APAR models learns to
spawn parallel generation thread in and only in categories that exists a
parallel-able structure. For instance, APAR-{7B,13B} seldom try to issue
parallel a generation threads in coding and math related queries, which
typically requires careful step by step reasoning or rigorous formats,
resulting in no speed up. On the other hand, on categories like common-sense,
generic and knowledge, the speed up is significant. When combined with
speculative decoding, Medusa-APAR achieves an impressive $4\times$ average
speed up in Vicuna Bench and $2.9\times$ average speed up in MT Bench,
demonstrating strong reduction in generation latency.

###  3.4 Results in High-Throughput Scenarios

(a) Throughput wrt. cache memory usage

(b) End-to-end decode latency wrt. concurrency

Figure 5: Serving statistics of Batched-APAR. Models served on one
A100-SXM4-80G GPU. Error bars in (b) omitted for a clearer view.

In high performance serving situations, increasing throughput and reducing
serving memory are also important. We use Batched-APAR to serve the queries in
APAR test set with different amount of GPU memory available. An overview of
generation throughput and per-token latency is summarized in Fig 5. The dots
in the plot show the mean value and error bars represent the 25% and 75%
percentile in each setting.

As shown in Fig 5(a), the throughput of Batched-APAR models surpass the
maximum throughput of original models with only 20% of the KV Cache used,
demonstrating memory efficiency. When using similar amount of memory,
throughput is consistently increase by 20%$\sim$ 70% across different cache
usages. Batched-APAR models also demonstrate remarkable latency reduction in
computation bound scenarios. As shown in Fig 5(b), Batched-APAR reduces
20%$\sim$35% average latency when serving the same amount of concurrent
requests. The latency of Batched-APAR-13B is even similar to the Original-7B
model.

The improvement in latency and throughput can be best explained by feature 2
and 3 as described in Section 2.4. We quantitatively measure how much
computation and cache memory can be saved by using APAR decoding algorithm. We
adopt the following metrics.

  * •

Max cached tokens is defined as the maximum number of KV cache slots required
for generating a response. For auto-regressive generation, prompt tokens and
all generated tokens need to be cached before generating [EOS] token.

  * •

Attended tokens is defined as the number of tokens attended to when predicting
a specific token. For auto-regressive generation, all preceding tokens is
needed when predicting a next token.

Table 1: Average Max Cached Tokens Benchmark | Model | APAR | Flatten | Saved
---|---|---|---|---
Vicuna | A-7B | 303.2 | 417.2 | 27.3%
A-13B | 306.7 | 419.3 | 26.8%
MT | A-7B | 502.1 | 571.1 | 12.1%
A-13B | 513.3 | 590.6 | 13.1%
Table 2: Average Attended Tokens Benchmark | Model | APAR | Flatten | Saved
---|---|---|---|---
Vicuna | A-7B | 166.2 | 256.4 | 35.2%
A-13B | 166.6 | 255.9 | 34.9%
MT | A-7B | 417.5 | 496.5 | 15.9%
A-13B | 428.0 | 514.2 | 16.8%

Since the response length is difference between APAR models and original
models, we flatten the paragraph tree generated by APAR models as the
reference output. When calculating average, we exclude categories that are not
accelerated by APAR, i.e. Coding, Extraction and Math.

As summarized in Table 1 and Table 2, compared with flattened results, APAR
reduces max cached tokens by 12%$\sim$27% and reduced attended tokens by
15%$\sim$35%. Detailed results for all categories are reported in Appendix D.3
and Appendix D.2.

###  3.5 Generation Quality

Table 3: Generation Quality in MT Bench Task | O-7B | A-7B | O-13B | A-13B
---|---|---|---|---
Coding | 2.60 | 2.60 | 3.70 | 3.70
Extraction | 4.90 | 5.75 | 5.35 | 4.85
Humanities | 9.45 | 9.40 | 9.45 | 9.55
Math | 2.70 | 2.00 | 2.60 | 2.65
Writing | 7.90 | 7.15 | 8.40 | 7.88
Roleplay | 6.35 | 7.25 | 7.67 | 7.58
Reasoning | 4.85 | 5.40 | 5.95 | 5.85
Stem | 7.92 | 7.15 | 7.67 | 7.80
Mean | 5.83 | 5.92 | 6.35 | 6.24
Table 4: Generation Quality in Vicuna Bench Task | O-7B | A-7B | O-13B | A-13B
---|---|---|---|---
Coding | 3.86 | 3.29 | 6.14 | 3.71
CS | 9.40 | 9.50 | 9.50 | 9.60
CF | 8.05 | 8.00 | 8.65 | 9.00
Fermi | 6.80 | 6.90 | 7.35 | 6.60
Generic | 9.45 | 9.50 | 9.30 | 9.50
Knowledge | 9.40 | 9.30 | 9.60 | 9.35
Math | 1.67 | 2.00 | 1.67 | 4.67
Roleplay | 8.80 | 8.80 | 8.90 | 8.75
Writing | 9.50 | 9.00 | 9.50 | 9.00
Mean | 8.08 | 7.99 | 8.45 | 8.29

To measure the generation quality of APAR models compared with original
models, we adopt MT Bench and Vicuna Bench as evaluation framework. For each
response, we provide GPT-4 with conversation history, user query and model
responses, asking GPT-4 to grade the response with a score ranging from 1 to
10 and we follow the prompt template used by Zheng et al. (2023).

The quality scores of each category are summarized in Table 3 and Table 4.
Compared with original models, APAR models differs by -2%$\sim$+2% in MT Bench
and Vicuna Bench overall scores, showing negligible overall quality change.

##  4 Related Works

This section discuss the difference and connection of APAR with prior works
concerning inference acceleration.

#### Optimized computation.

Optimizations on operators (Dao et al., 2022) and computational graphs
(Aminabadi et al., 2022) are active research fields. Model compression is
widely used in deployment, like quantization (Dettmers et al., 2022; Frantar
et al., 2022) and pruning (Frantar and Alistarh, 2023; Ma et al., 2023).
Another line of works modifies the model architecture, including efficient
attention (Kitaev et al., 2020) for computation complexity and multi-query
attention (Shazeer, 2019) for optimized IO. Different from prior works, APAR
makes no modification to operators or model architecture but reduces
computation by adopting attention tree structure. APRA is thus _orthogonal to_
and can be applied jointly with the aforementioned works.

#### Improved parallelism.

Scheduling strategies, including dynamic batching (Yu et al., 2022) and paged-
attention (Kwon et al., 2023), improve maximum generation throughput. Another
stream of works explores speculative decoding (SD) (Leviathan et al., 2023;
Yang et al., 2023; Cai et al., 2023), which verifies multiple speculated
tokens in parallel, reducing generation latency in small batch sizes. Non-
auto-regressive generation (Gu et al., 2018) propose to sample multiple
generation tokens in parallel, which typically requires re-training and
applies to restricted scenarios. APAR can be conveniently combined with
efficient scheduling and SD methods to achieve augmented efficiency as
demonstrated by Medusa-APAR and Batched-APAR. Different from previous methods,
APAR propose to exploit the _intrinsic organization ability_ of LLMs to
automatically issue paralleled generation threads, and is applicable to
multiple scenarios. Notably, SoT (Ning et al., 2023) proposes to enable
parallelism by prompting, which generates the skeleton of the response and
then expands each point in parallel. Different from SoT, which entails an
external classifier and re-computation of KV cache between stages, APAR
requires negligible extra computation (2 control tokens for a thread) and no
re-computation, and thus does not compromise generation throughput.

##  5 Conclusion

This paper introduces APAR, a new decoding method that allows LLMs to
autonomously structure the decoding process and dynamically create parallel
decoding threads, without compromising the generation quality. APAR not only
enhances parallelism in generation, but also reduces the computation and KV
cache memory consumption. Experiments show that APAR can be seamlessly
integrated with existing inference frameworks, significantly lowering the
generation latency across various scenarios while improving serving throughput
in situations involving extreme batch sizes and concurrency levels.

## References

  * Aminabadi et al. (2022) Reza Yazdani Aminabadi, Samyam Rajbhandari, Minjia Zhang, Ammar Ahmad Awan, Cheng Li, Du Li, Elton Zheng, Jeff Rasley, Shaden Smith, Olatunji Ruwase, and Yuxiong He. 2022.  Deepspeed inference: Enabling efficient inference of transformer models at unprecedented scale.
  * Cai et al. (2023) Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, and Tri Dao. 2023.  Medusa: Simple framework for accelerating llm generation with multiple decoding heads.  https://github.com/FasterDecoding/Medusa.
  * Chiang et al. (2023) Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E. Gonzalez, Ion Stoica, and Eric P. Xing. 2023.  Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality.
  * Dao et al. (2022) Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. 2022.  Flashattention: Fast and memory-efficient exact attention with io-awareness.
  * Dettmers et al. (2022) Tim Dettmers, Mike Lewis, Younes Belkada, and Luke Zettlemoyer. 2022.  Llm.int8(): 8-bit matrix multiplication for transformers at scale.
  * Frantar and Alistarh (2023) Elias Frantar and Dan Alistarh. 2023.  Sparsegpt: Massive language models can be accurately pruned in one-shot.
  * Frantar et al. (2022) Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh. 2022.  GPTQ: Accurate post-training compression for generative pretrained transformers.  _arXiv preprint arXiv:2210.17323_.
  * Gu et al. (2018) Jiatao Gu, James Bradbury, Caiming Xiong, Victor O.K. Li, and Richard Socher. 2018.  Non-autoregressive neural machine translation.  In _International Conference on Learning Representations_.
  * Kitaev et al. (2020) Nikita Kitaev, Łukasz Kaiser, and Anselm Levskaya. 2020.  Reformer: The efficient transformer.
  * Kwon et al. (2023) Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. 2023.  Efficient memory management for large language model serving with pagedattention.  In _Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles_.
  * Leviathan et al. (2023) Yaniv Leviathan, Matan Kalman, and Yossi Matias. 2023.  Fast inference from transformers via speculative decoding.  In _Proceedings of the 40th International Conference on Machine Learning_ , ICML’23. JMLR.org.
  * Ma et al. (2023) Xinyin Ma, Gongfan Fang, and Xinchao Wang. 2023.  Llm-pruner: On the structural pruning of large language models.  In _Advances in Neural Information Processing Systems_.
  * Nakajima (2023) Yohei Nakajima. 2023.  Babyagi.  _Python. https://github.com/yoheinakajima/babyagi_.
  * Ning et al. (2023) Xuefei Ning, Zinan Lin, Zixuan Zhou, Zifu Wang, Huazhong Yang, and Yu Wang. 2023.  Skeleton-of-thought: Large language models can do parallel decoding.
  * OpenAI (2023) OpenAI. 2023.  Gpt-4 technical report.
  * Park et al. (2023) Joon Sung Park, Joseph C. O’Brien, Carrie J. Cai, Meredith Ringel Morris, Percy Liang, and Michael S. Bernstein. 2023.  Generative agents: Interactive simulacra of human behavior.  In _In the 36th Annual ACM Symposium on User Interface Software and Technology (UIST ’23)_ , UIST ’23, New York, NY, USA. Association for Computing Machinery.
  * Radford et al. (2018) Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, et al. 2018.  Improving language understanding by generative pre-training.
  * Richards (2023) Toran Bruce Richards. 2023.  Auto-gpt: An autonomous gpt-4 experiment.
  * Shazeer (2019) Noam Shazeer. 2019.  Fast transformer decoding: One write-head is all you need.
  * Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. 2023.  Llama: Open and efficient foundation language models.  _ArXiv preprint_ , abs/2302.13971.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 38–45, Online. Association for Computational Linguistics.
  * Yang et al. (2023) Nan Yang, Tao Ge, Liang Wang, Binxing Jiao, Daxin Jiang, Linjun Yang, Rangan Majumder, and Furu Wei. 2023.  Inference with reference: Lossless acceleration of large language models.
  * Yu et al. (2022) Gyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim, and Byung-Gon Chun. 2022.  Orca: A distributed serving system for Transformer-Based generative models.  In _16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22)_ , pages 521–538, Carlsbad, CA. USENIX Association.
  * Zeng et al. (2022) Aohan Zeng, Xiao Liu, Zhengxiao Du, Zihan Wang, Hanyu Lai, Ming Ding, Zhuoyi Yang, Yifan Xu, Wendi Zheng, Xiao Xia, et al. 2022.  Glm-130b: An open bilingual pre-trained model.  _arXiv preprint arXiv:2210.02414_.
  * Zheng et al. (2023) Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric. P Xing, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica. 2023.  Judging llm-as-a-judge with mt-bench and chatbot arena.
  * Zhou et al. (2023) Shuyan Zhou, Frank F Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Yonatan Bisk, Daniel Fried, Uri Alon, et al. 2023.  Webarena: A realistic web environment for building autonomous agents.  _arXiv preprint arXiv:2307.13854_.

##  Appendix A Training Hyper-parameters

###  A.1 APAR Models

Table 5: Training Hyper-parameters for APAR Models Hyper-parameter | Value
---|---
batch size | 128
data type | bf16
training step | 2000
learning rate | 2e-5
weight decay | 0
warm-up ratio | 0.03
lr decay schedule | cosine
context length | 2048

###  A.2 Medusa Heads

The following hyper-parameters are used to train the medusa heads for
speculative decoding. Only medusa heads are trained and the reset of the
language model remains frozen.

Table 6: Training Hyper-parameters for Medusa Heads Hyper-parameter | Value
---|---
batch size | 128
data type | bf16
training step | 2000
learning rate | 1e-3
weight decay | 0
warm-up ratio | 0.1
lr decay schedule | cosine
context length | 2048
# of Medusa heads | 2
# of layers per Medusa head | 2

##  Appendix B Rules for Extracting Structured Data

The process and rules to determine and extract the structure of each assistant
response are outlined as follows.

  1. 1.

Try to extract the response as ordered list.

    1. (a)

Use regular expression like
`(\d+\.)\s+(.+?):(.+?)`
to extract individual numeric points.

    2. (b)

If

      1. i.

the regular expression does not does not match at least 3 numeric points, or

      2. ii.

any of the content of the numeric points are less then 10 characters

the response is not consider as a valid ordered list.

  2. 2.

If the response is not consider as a valid ordered list, try to extract the
response as multiple paragraph.

    1. (a)

Use two consecutive `\n` to divide the entire response into paragraphs and
extract the first sentence of each paragraph. Paragraphs with only one
sentence is skipped.

  3. 3.

If ambiguous patterns, including code blocks, math expressions, URLs, etc,
exists in the response, the, or if the response fails to match the above 2
criteria, the response is considered unstructured.

Pre-processing code will be made public in the project repository.

##  Appendix C Generation Speed Evaluation Setup

###  C.1 Vanilla-APAR and Medusa-APAR

Vanilla-APAR and Medusa-APAR are implementation directly from transformers
package. To keep KV cache contiguous, prefix sharing is not enabled and the
prefix KV caches are copied when a new generation thread is forked. The
implementation of Medusa-APAR is adopt from its official repository. When
different number of tokens are accepted across batches, the longest accepted
length is adopted and the mis-predicted slots are masked out in attention
calculation. The evaluation batch-size is fixed as 1 and the pre-filling time
is not measured when calculating generation speed.

###  C.2 Batched-APAR

To measure the maximum throughput of each generation method, GPU cache
utilization is set to $0.1,\cdots,0.9$ for each setting and the system is
profiled every 3 seconds. For a stable performance, we ignore the terminal
samples when no requests are pending and ignore the first $\frac{1}{3}$
samples as warm-up when calculating mean and percentiles.

All 1k requests are push into waiting queue in the beginning of the
performance test. We limit the max number of concurrent requests to 350 for 7B
models and 180 for 13B models. The reason for this limit is that in the
beginning, the average sequence length is relatively sort and the system is
prone to excessively accept requests, leading to frequent swapping and
recompute of KV cache. Note that this concurrency limit mainly takes effect in
warm-up stage, which is ignore in the calculation for mean and percentage. The
concurrency limit is much larger than the maximum in the average concurrent
request as shown in Fig 5(b).

##  Appendix D Generation Speed Details

###  D.1 Parallel Generation Statistics

We measure how many parallel threads are issued in generation across
benchmarks and categories. Results are reported in Table 7 and Table 8. #T
stands for average number of generation threads, %P stand for ratio of
parallel-able response, i.e. response that has at least 2 generation threads.

Table 7: Parallel Generation Statistics in Vicuna Bench Task | APAR-7B | APAR-13B
---|---|---
#T | %P | #T | %P
Coding | 1.0 | 0.0 | 1.0 | 0.0
CS | 6.0 | 1.0 | 6.5 | 1.0
CF | 4.1 | 0.9 | 5.4 | 1.0
Fermi | 5.3 | 0.9 | 5.5 | 0.9
Generic | 7.7 | 1.0 | 7.7 | 1.0
Knowledge | 6.8 | 1.0 | 5.6 | 1.0
Math | 1.0 | 0.0 | 1.0 | 0.0
Roleplay | 4.5 | 0.8 | 5.1 | 1.0
Writing | 5.4 | 0.9 | 4.6 | 0.7
Mean | 5.1 | 0.81 | 5.2 | 0.82
Table 8: Parallel Generation Statistics in MT Bench Task | APAR-7B | APAR-13B
---|---|---
#T | %P | #T | %P
Coding | 1.0 | 0.0 | 1.0 | 0.0
Extraction | 1.0 | 0.0 | 1.3 | 0.1
Humanities | 5.0 | 0.7 | 6.1 | 0.8
Math | 1.1 | 0.1 | 1.0 | 0.0
Reasoning | 2.0 | 0.3 | 2.5 | 0.6
Roleplay | 4.1 | 0.8 | 4.0 | 0.7
STEM | 3.4 | 0.6 | 3.6 | 0.6
Writing | 3.7 | 0.6 | 3.4 | 0.6
Mean | 2.7 | 0.37 | 2.9 | 0.41

###  D.2 Max Cached Tokens

Detailed results of max cached tokens across benchmarks and categories are
reported in Table 9, Table 10, 11 and Table 12, . Mean value of all categories
and categories accelerated by APAR are reported.

Table 9: Max Cached Tokens (Vanilla-APAR-7B on Vicuna Bench) Task | APAR | AR | Saved
---|---|---|---
Coding | 378.0 | 378.0 | 0.0%
CS | 296.6 | 417.7 | 29.0%
CF | 245.6 | 312.4 | 21.4%
Fermi | 365.3 | 496.8 | 26.5%
Generic | 251.5 | 388.8 | 35.3%
Knowledge | 345.0 | 489.9 | 29.6%
Math | 210.7 | 210.7 | 0.0%
Roleplay | 292.5 | 364.1 | 19.7%
Writing | 325.6 | 450.4 | 27.7%
Mean | 306.2 | 406.0 | 24.6%
Mean(>1%) | 303.2 | 417.2 | 27.3%
Table 10: Max Cached Tokens (Vanilla-APAR-13B on Vicuna Bench) Task | APAR | AR | Saved
---|---|---|---
Coding | 370.0 | 370.0 | 0.0%
CS | 287.6 | 416.9 | 31.0%
CF | 276.9 | 383.0 | 27.7%
Fermi | 401.0 | 529.7 | 24.3%
Generic | 260.7 | 389.2 | 33.0%
Knowledge | 313.2 | 419.7 | 25.4%
Math | 203.3 | 203.3 | 0.0%
Roleplay | 254.3 | 346.5 | 26.6%
Writing | 353.5 | 449.8 | 21.4%
Mean | 308.4 | 406.9 | 24.2%
Mean(>1%) | 306.7 | 419.3 | 26.8%
Table 11: Max Cached Tokens (Vanilla-APAR-7B on MT Bench) Task | APAR | AR | Saved
---|---|---|---
Coding | 744.8 | 744.8 | 0.0%
Extraction | 567.2 | 567.2 | 0.0%
Humanities | 647.0 | 757.3 | 14.6%
Math | 408.5 | 410.4 | 0.4%
Reasoning | 314.9 | 335.4 | 6.1%
Roleplay | 461.2 | 533.6 | 13.6%
STEM | 574.2 | 641.7 | 10.5%
Writing | 513.0 | 587.6 | 12.7%
Mean | 529.6 | 573.3 | 7.6%
Mean(>1%) | 502.1 | 571.1 | 12.1%
Table 12: Max Cached Tokens (Vanilla-APAR-13B on MT Bench) Task | APAR | AR | Saved
---|---|---|---
Coding | 589.6 | 589.6 | 0.0%
Extraction | 640.3 | 641.7 | 0.2%
Humanities | 676.1 | 822.5 | 17.8%
Math | 451.9 | 451.9 | 0.0%
Reasoning | 318.2 | 344.8 | 7.7%
Roleplay | 484.6 | 548.5 | 11.7%
STEM | 591.1 | 677.5 | 12.8%
Writing | 496.4 | 559.6 | 11.3%
Mean | 530.3 | 579.1 | 8.4%
Mean(>1%) | 513.3 | 590.6 | 13.1%

###  D.3 Attended Tokens

Detailed results of attend tokens across benchmarks and categories are
reported in Table 13, Table 14, Table 15 and Table 16. Mean value of all
categories and categories accelerated by APAR are reported.

Table 13: Attended Tokens (Vanilla-APAR-7B on Vicuna Bench) Task | APAR | AR | Saved
---|---|---|---
Coding | 221.6 | 221.6 | 0.0%
CS | 152.0 | 244.6 | 37.9%
CF | 142.0 | 185.3 | 23.4%
Fermi | 214.6 | 309.6 | 30.7%
Generic | 126.3 | 222.2 | 43.2%
Knowledge | 154.7 | 290.3 | 46.7%
Math | 139.7 | 139.7 | 0.0%
Roleplay | 166.8 | 229.0 | 27.2%
Writing | 189.1 | 270.0 | 30.0%
Mean | 170.3 | 251.7 | 32.4%
Mean(>1%) | 166.2 | 256.4 | 35.2%
Table 14: Attended Tokens (Vanilla-APAR-13B on Vicuna Bench) Task | APAR | AR | Saved
---|---|---|---
Coding | 222.0 | 222.0 | 0.0%
CS | 151.3 | 248.7 | 39.2%
CF | 144.6 | 224.2 | 35.5%
Fermi | 204.9 | 325.7 | 37.1%
Generic | 125.3 | 221.8 | 43.5%
Knowledge | 158.6 | 248.8 | 36.3%
Math | 137.3 | 137.3 | 0.0%
Roleplay | 150.3 | 217.1 | 30.8%
Writing | 209.0 | 271.8 | 23.1%
Mean | 170.5 | 251.4 | 32.2%
Mean(>1%) | 166.6 | 255.9 | 34.9%
Table 15: Attended Tokens (Vanilla-APAR-7B on MT Bench) Task | APAR | AR | Saved
---|---|---|---
Coding | 577.4 | 577.4 | 0.0%
Extraction | 570.8 | 570.8 | 0.0%
Humanities | 456.5 | 556.0 | 17.9%
Math | 616.0 | 616.9 | 0.1%
Reasoning | 286.7 | 322.0 | 11.0%
Roleplay | 404.3 | 477.7 | 15.4%
STEM | 413.0 | 473.8 | 12.8%
Writing | 437.9 | 533.1 | 17.8%
Mean | 477.0 | 528.3 | 9.7%
Mean(>1%) | 417.5 | 496.5 | 15.9%
Table 16: Attended Tokens (Vanilla-APAR-13B on MT Bench) Task | APAR | AR | Saved
---|---|---|---
Coding | 449.9 | 449.9 | 0.0%
Extraction | 767.8 | 769.2 | 0.2%
Humanities | 507.0 | 636.0 | 20.3%
Math | 601.3 | 601.3 | 0.0%
Reasoning | 314.3 | 350.1 | 10.2%
Roleplay | 404.8 | 464.9 | 12.9%
STEM | 445.3 | 521.1 | 14.6%
Writing | 360.8 | 442.7 | 18.5%
Mean | 482.3 | 539.6 | 10.6%
Mean(>1%) | 428.0 | 514.2 | 16.8%

###  D.4 Response Length

Figure 6: Response Length on Vicuna Bench and MT Bench

Apart from generation quality, we also analyze the response length
distribution of model before and after fine-tuning in Fig 6. The average
length varies from -0.3%$\sim$+4.0% compared with respective original model
and the distributions highly overlap. This indicate that if fine-tuned with
the same material, APAR does not significantly affect the generation length
distribution.