You are reading immutable version 1. The current guide may be newer.

Study the paper

Kimi Linear: An Expressive, Efficient Attention Architecture

Lessons, visuals, quizzes, flashcards, and resources—organized in teaching order.

All activities

Mathematical Formulation and Chunkwise Parallelism of KDA

Mathematical Formulation and Chunkwise Parallelism of KDA

Mathematical Formulation and Chunkwise Parallelism of KDA

Mathematical Formulation of Kimi Delta Attention (KDA)

Sources

block

Kimi Linear: An Expressive, Efficient Attention Architecture T ECHNICAL R EPORT 3 Kimi Delta Attention: Improving Delta Rule with Fine-grained Gating We propose Kimi Delta Attention (KDA), a new gated linear attention variant that refines GDN’s scalar decay by introducing a fine-grained diagonalized gate Diag( α t ) that enables fine-grained control over memory decay and positional awareness (as discussed in §6.1). We begin by introducing the chunkwise parallelization of KDA, showing how a series of rank-1 matrix transformations can be compressed into a dense representation while maintaining stability under diagonal gating. We then highlight the efficiency gains of KDA over the standard DPLR ( Diagonal-Plus-Low- Rank ) formulation [30, 71]. S t = I − β t k t k ⊤ t  Diag ( α t ) S t − 1 + β t k t v ⊤ t ∈ R d k × d v ; o t = S ⊤ t q t ∈ R d v (1)       =       − × !             + × =       3.1 Hardware-Efficient Chunkwise Algorithm By partially expanding the recurrence for Eq. 1 into a chunk-wise formulation, we have: S r [ t ] = r Y i =1  I − β i [ t ] k i [ t ] k i ⊤ [ t ]  Diag( α i [ t ] ) ! | {z } := P r [ t ] · S 0 [ t ] + r X i =1   r Y j =…

Kimi Delta Attention (KDA) is a gated linear attention variant designed to refine the scalar decay mechanism of Gated DeltaNet (GDN). By introducing a fine-grained diagonalized decay gate Diag(αt)\text{Diag}(\alpha_t), KDA enables precise channel-wise control over memory decay and positional awareness. The recurrent update of the state matrix St∈Rdk×dvS_t \in \mathbb{R}^{d_k \times d_v} and the output ot∈Rdvo_t \in \mathbb{R}^{d_v} are formulated as follows:

Sources

block

Kimi Linear: An Expressive, Efficient Attention Architecture T ECHNICAL R EPORT 3 Kimi Delta Attention: Improving Delta Rule with Fine-grained Gating We propose Kimi Delta Attention (KDA), a new gated linear attention variant that refines GDN’s scalar decay by introducing a fine-grained diagonalized gate Diag( α t ) that enables fine-grained control over memory decay and positional awareness (as discussed in §6.1). We begin by introducing the chunkwise parallelization of KDA, showing how a series of rank-1 matrix transformations can be compressed into a dense representation while maintaining stability under diagonal gating. We then highlight the efficiency gains of KDA over the standard DPLR ( Diagonal-Plus-Low- Rank ) formulation [30, 71]. S t = I − β t k t k ⊤ t  Diag ( α t ) S t − 1 + β t k t v ⊤ t ∈ R d k × d v ; o t = S ⊤ t q t ∈ R d v (1)       =       − × !             + × =       3.1 Hardware-Efficient Chunkwise Algorithm By partially expanding the recurrence for Eq. 1 into a chunk-wise formulation, we have: S r [ t ] = r Y i =1  I − β i [ t ] k i [ t ] k i ⊤ [ t ]  Diag( α i [ t ] ) ! | {z } := P r [ t ] · S 0 [ t ] + r X i =1   r Y j =…

St=(I−βtktkt⊤)Diag(αt)St−1+βtktvt⊤S_t = (I - \beta_t k_t k_t^\top) \text{Diag}(\alpha_t) S_{t-1} + \beta_t k_t v_t^\top

Sources

block

Kimi Linear: An Expressive, Efficient Attention Architecture T ECHNICAL R EPORT 3 Kimi Delta Attention: Improving Delta Rule with Fine-grained Gating We propose Kimi Delta Attention (KDA), a new gated linear attention variant that refines GDN’s scalar decay by introducing a fine-grained diagonalized gate Diag( α t ) that enables fine-grained control over memory decay and positional awareness (as discussed in §6.1). We begin by introducing the chunkwise parallelization of KDA, showing how a series of rank-1 matrix transformations can be compressed into a dense representation while maintaining stability under diagonal gating. We then highlight the efficiency gains of KDA over the standard DPLR ( Diagonal-Plus-Low- Rank ) formulation [30, 71]. S t = I − β t k t k ⊤ t  Diag ( α t ) S t − 1 + β t k t v ⊤ t ∈ R d k × d v ; o t = S ⊤ t q t ∈ R d v (1)       =       − × !             + × =       3.1 Hardware-Efficient Chunkwise Algorithm By partially expanding the recurrence for Eq. 1 into a chunk-wise formulation, we have: S r [ t ] = r Y i =1  I − β i [ t ] k i [ t ] k i ⊤ [ t ]  Diag( α i [ t ] ) ! | {z } := P r [ t ] · S 0 [ t ] + r X i =1   r Y j =…

ot=St⊤qto_t = S_t^\top q_t

Sources

block

Kimi Linear: An Expressive, Efficient Attention Architecture T ECHNICAL R EPORT 3 Kimi Delta Attention: Improving Delta Rule with Fine-grained Gating We propose Kimi Delta Attention (KDA), a new gated linear attention variant that refines GDN’s scalar decay by introducing a fine-grained diagonalized gate Diag( α t ) that enables fine-grained control over memory decay and positional awareness (as discussed in §6.1). We begin by introducing the chunkwise parallelization of KDA, showing how a series of rank-1 matrix transformations can be compressed into a dense representation while maintaining stability under diagonal gating. We then highlight the efficiency gains of KDA over the standard DPLR ( Diagonal-Plus-Low- Rank ) formulation [30, 71]. S t = I − β t k t k ⊤ t  Diag ( α t ) S t − 1 + β t k t v ⊤ t ∈ R d k × d v ; o t = S ⊤ t q t ∈ R d v (1)       =       − × !             + × =       3.1 Hardware-Efficient Chunkwise Algorithm By partially expanding the recurrence for Eq. 1 into a chunk-wise formulation, we have: S r [ t ] = r Y i =1  I − β i [ t ] k i [ t ] k i ⊤ [ t ]  Diag( α i [ t ] ) ! | {z } := P r [ t ] · S 0 [ t ] + r X i =1   r Y j =…

Here, qtq_t, ktk_t, and vtv_t represent the query, key, and value vectors respectively, βt∈[0,1]\beta_t \in [0, 1] is a scalar gate controlling the update strength, and αt∈[0,1]dk\alpha_t \in [0, 1]^{d_k} is the channel-wise decay vector. This diagonalized gating mechanism allows different feature dimensions to decay at different rates, significantly increasing the model's capacity to retain critical context over long sequences.

Sources

block

Kimi Linear: An Expressive, Efficient Attention Architecture T ECHNICAL R EPORT 3 Kimi Delta Attention: Improving Delta Rule with Fine-grained Gating We propose Kimi Delta Attention (KDA), a new gated linear attention variant that refines GDN’s scalar decay by introducing a fine-grained diagonalized gate Diag( α t ) that enables fine-grained control over memory decay and positional awareness (as discussed in §6.1). We begin by introducing the chunkwise parallelization of KDA, showing how a series of rank-1 matrix transformations can be compressed into a dense representation while maintaining stability under diagonal gating. We then highlight the efficiency gains of KDA over the standard DPLR ( Diagonal-Plus-Low- Rank ) formulation [30, 71]. S t = I − β t k t k ⊤ t  Diag ( α t ) S t − 1 + β t k t v ⊤ t ∈ R d k × d v ; o t = S ⊤ t q t ∈ R d v (1)       =       − × !             + × =       3.1 Hardware-Efficient Chunkwise Algorithm By partially expanding the recurrence for Eq. 1 into a chunk-wise formulation, we have: S r [ t ] = r Y i =1  I − β i [ t ] k i [ t ] k i ⊤ [ t ]  Diag( α i [ t ] ) ! | {z } := P r [ t ] · S 0 [ t ] + r X i =1   r Y j =…
Deep dive

Hardware-Efficient Chunkwise Parallelization

Sources

block

Kimi Linear: An Expressive, Efficient Attention Architecture T ECHNICAL R EPORT 3 Kimi Delta Attention: Improving Delta Rule with Fine-grained Gating We propose Kimi Delta Attention (KDA), a new gated linear attention variant that refines GDN’s scalar decay by introducing a fine-grained diagonalized gate Diag( α t ) that enables fine-grained control over memory decay and positional awareness (as discussed in §6.1). We begin by introducing the chunkwise parallelization of KDA, showing how a series of rank-1 matrix transformations can be compressed into a dense representation while maintaining stability under diagonal gating. We then highlight the efficiency gains of KDA over the standard DPLR ( Diagonal-Plus-Low- Rank ) formulation [30, 71]. S t = I − β t k t k ⊤ t  Diag ( α t ) S t − 1 + β t k t v ⊤ t ∈ R d k × d v ; o t = S ⊤ t q t ∈ R d v (1)       =       − × !             + × =       3.1 Hardware-Efficient Chunkwise Algorithm By partially expanding the recurrence for Eq. 1 into a chunk-wise formulation, we have: S r [ t ] = r Y i =1  I − β i [ t ] k i [ t ] k i ⊤ [ t ]  Diag( α i [ t ] ) ! | {z } := P r [ t ] · S 0 [ t ] + r X i =1   r Y j =…

block

Kimi Linear: An Expressive, Efficient Attention Architecture T ECHNICAL R EPORT B Derivations for Chunkwise Parallelism of KDA We first recall the recurrent form of KDA: S r [ t ] = r Y i =1  I − β i [ t ] k i [ t ] k i ⊤ [ t ]  Diag( α i [ t ] ) ! | {z } := P r [ t ] · S 0 [ t ] + r X i =1   r Y j = i +1  I − β j [ t ] k j [ t ] k j ⊤ [ t ]  Diag( α j [ t ] )   · β i [ t ] k i [ t ] v i ⊤ [ t ] | {z } := H r [ t ] = P r [ t ] · S 0 [ t ] + H r [ t ] Our goal is to transform P r [ t ] and H r [ t ] into matrix forms suitable for parallel computation. We show that P r [ t ] , which involves the cumulative product of generalized Householder matrices, can be optimized using the classic WY representation. Proposition 1. The matrix P r [ t ] can be expressed as: P r [ t ] = Diag( γ r [ t ] ) − r X i =1 Diag( γ i → r [ t ] ) k i [ t ] w i ⊤ [ t ] (16) where the auxiliary vector w r [ t ] ∈ R d k is computed via the following recurrence relation: w r [ t ] = β r [ t ] Diag( γ r [ t ] ) k r [ t ] − r − 1 X i =1 w i [ t ]  k i ⊤ [ t ] Diag  γ i → r [ t ]  k r [ t ]  ! (17) Proof. We proceed with a proof by mathematical induction. Inductive Step: Assume the proposition holds for…
Deep dive

To achieve high hardware utilization during training, the recurrent formulation is expanded into a chunkwise parallel algorithm. For a chunk of size CC, the state at step rr within a chunk can be written as:

Sources

block

Kimi Linear: An Expressive, Efficient Attention Architecture T ECHNICAL R EPORT 3 Kimi Delta Attention: Improving Delta Rule with Fine-grained Gating We propose Kimi Delta Attention (KDA), a new gated linear attention variant that refines GDN’s scalar decay by introducing a fine-grained diagonalized gate Diag( α t ) that enables fine-grained control over memory decay and positional awareness (as discussed in §6.1). We begin by introducing the chunkwise parallelization of KDA, showing how a series of rank-1 matrix transformations can be compressed into a dense representation while maintaining stability under diagonal gating. We then highlight the efficiency gains of KDA over the standard DPLR ( Diagonal-Plus-Low- Rank ) formulation [30, 71]. S t = I − β t k t k ⊤ t  Diag ( α t ) S t − 1 + β t k t v ⊤ t ∈ R d k × d v ; o t = S ⊤ t q t ∈ R d v (1)       =       − × !             + × =       3.1 Hardware-Efficient Chunkwise Algorithm By partially expanding the recurrence for Eq. 1 into a chunk-wise formulation, we have: S r [ t ] = r Y i =1  I − β i [ t ] k i [ t ] k i ⊤ [ t ]  Diag( α i [ t ] ) ! | {z } := P r [ t ] · S 0 [ t ] + r X i =1   r Y j =…

block

Kimi Linear: An Expressive, Efficient Attention Architecture T ECHNICAL R EPORT B Derivations for Chunkwise Parallelism of KDA We first recall the recurrent form of KDA: S r [ t ] = r Y i =1  I − β i [ t ] k i [ t ] k i ⊤ [ t ]  Diag( α i [ t ] ) ! | {z } := P r [ t ] · S 0 [ t ] + r X i =1   r Y j = i +1  I − β j [ t ] k j [ t ] k j ⊤ [ t ]  Diag( α j [ t ] )   · β i [ t ] k i [ t ] v i ⊤ [ t ] | {z } := H r [ t ] = P r [ t ] · S 0 [ t ] + H r [ t ] Our goal is to transform P r [ t ] and H r [ t ] into matrix forms suitable for parallel computation. We show that P r [ t ] , which involves the cumulative product of generalized Householder matrices, can be optimized using the classic WY representation. Proposition 1. The matrix P r [ t ] can be expressed as: P r [ t ] = Diag( γ r [ t ] ) − r X i =1 Diag( γ i → r [ t ] ) k i [ t ] w i ⊤ [ t ] (16) where the auxiliary vector w r [ t ] ∈ R d k is computed via the following recurrence relation: w r [ t ] = β r [ t ] Diag( γ r [ t ] ) k r [ t ] − r − 1 X i =1 w i [ t ]  k i ⊤ [ t ] Diag  γ i → r [ t ]  k r [ t ]  ! (17) Proof. We proceed with a proof by mathematical induction. Inductive Step: Assume the proposition holds for…
Deep dive

Sr[t]=Pr[t]⋅S0[t]+Hr[t]S_r[t] = P_r[t] \cdot S_0[t] + H_r[t]

Sources

block

Kimi Linear: An Expressive, Efficient Attention Architecture T ECHNICAL R EPORT 3 Kimi Delta Attention: Improving Delta Rule with Fine-grained Gating We propose Kimi Delta Attention (KDA), a new gated linear attention variant that refines GDN’s scalar decay by introducing a fine-grained diagonalized gate Diag( α t ) that enables fine-grained control over memory decay and positional awareness (as discussed in §6.1). We begin by introducing the chunkwise parallelization of KDA, showing how a series of rank-1 matrix transformations can be compressed into a dense representation while maintaining stability under diagonal gating. We then highlight the efficiency gains of KDA over the standard DPLR ( Diagonal-Plus-Low- Rank ) formulation [30, 71]. S t = I − β t k t k ⊤ t  Diag ( α t ) S t − 1 + β t k t v ⊤ t ∈ R d k × d v ; o t = S ⊤ t q t ∈ R d v (1)       =       − × !             + × =       3.1 Hardware-Efficient Chunkwise Algorithm By partially expanding the recurrence for Eq. 1 into a chunk-wise formulation, we have: S r [ t ] = r Y i =1  I − β i [ t ] k i [ t ] k i ⊤ [ t ]  Diag( α i [ t ] ) ! | {z } := P r [ t ] · S 0 [ t ] + r X i =1   r Y j =…

block

Kimi Linear: An Expressive, Efficient Attention Architecture T ECHNICAL R EPORT B Derivations for Chunkwise Parallelism of KDA We first recall the recurrent form of KDA: S r [ t ] = r Y i =1  I − β i [ t ] k i [ t ] k i ⊤ [ t ]  Diag( α i [ t ] ) ! | {z } := P r [ t ] · S 0 [ t ] + r X i =1   r Y j = i +1  I − β j [ t ] k j [ t ] k j ⊤ [ t ]  Diag( α j [ t ] )   · β i [ t ] k i [ t ] v i ⊤ [ t ] | {z } := H r [ t ] = P r [ t ] · S 0 [ t ] + H r [ t ] Our goal is to transform P r [ t ] and H r [ t ] into matrix forms suitable for parallel computation. We show that P r [ t ] , which involves the cumulative product of generalized Householder matrices, can be optimized using the classic WY representation. Proposition 1. The matrix P r [ t ] can be expressed as: P r [ t ] = Diag( γ r [ t ] ) − r X i =1 Diag( γ i → r [ t ] ) k i [ t ] w i ⊤ [ t ] (16) where the auxiliary vector w r [ t ] ∈ R d k is computed via the following recurrence relation: w r [ t ] = β r [ t ] Diag( γ r [ t ] ) k r [ t ] − r − 1 X i =1 w i [ t ]  k i ⊤ [ t ] Diag  γ i → r [ t ]  k r [ t ]  ! (17) Proof. We proceed with a proof by mathematical induction. Inductive Step: Assume the proposition holds for…
Deep dive

where Pr[t]P_r[t] represents the cumulative decay and update transformations, and Hr[t]H_r[t] represents the accumulated input contributions. Using the WY representation, we can express these terms in a parallelizable form:

Sources

block

Kimi Linear: An Expressive, Efficient Attention Architecture T ECHNICAL R EPORT B Derivations for Chunkwise Parallelism of KDA We first recall the recurrent form of KDA: S r [ t ] = r Y i =1  I − β i [ t ] k i [ t ] k i ⊤ [ t ]  Diag( α i [ t ] ) ! | {z } := P r [ t ] · S 0 [ t ] + r X i =1   r Y j = i +1  I − β j [ t ] k j [ t ] k j ⊤ [ t ]  Diag( α j [ t ] )   · β i [ t ] k i [ t ] v i ⊤ [ t ] | {z } := H r [ t ] = P r [ t ] · S 0 [ t ] + H r [ t ] Our goal is to transform P r [ t ] and H r [ t ] into matrix forms suitable for parallel computation. We show that P r [ t ] , which involves the cumulative product of generalized Householder matrices, can be optimized using the classic WY representation. Proposition 1. The matrix P r [ t ] can be expressed as: P r [ t ] = Diag( γ r [ t ] ) − r X i =1 Diag( γ i → r [ t ] ) k i [ t ] w i ⊤ [ t ] (16) where the auxiliary vector w r [ t ] ∈ R d k is computed via the following recurrence relation: w r [ t ] = β r [ t ] Diag( γ r [ t ] ) k r [ t ] − r − 1 X i =1 w i [ t ]  k i ⊤ [ t ] Diag  γ i → r [ t ]  k r [ t ]  ! (17) Proof. We proceed with a proof by mathematical induction. Inductive Step: Assume the proposition holds for…
Deep dive

Pr[t]=Diag(γr[t])−∑i=1rDiag(γi→r[t])ki[t]wi⊤[t]P_r[t] = \text{Diag}(\gamma_r[t]) - \sum_{i=1}^r \text{Diag}(\gamma_{i \to r}[t]) k_i[t] w_i^\top[t]

Sources

block

Kimi Linear: An Expressive, Efficient Attention Architecture T ECHNICAL R EPORT B Derivations for Chunkwise Parallelism of KDA We first recall the recurrent form of KDA: S r [ t ] = r Y i =1  I − β i [ t ] k i [ t ] k i ⊤ [ t ]  Diag( α i [ t ] ) ! | {z } := P r [ t ] · S 0 [ t ] + r X i =1   r Y j = i +1  I − β j [ t ] k j [ t ] k j ⊤ [ t ]  Diag( α j [ t ] )   · β i [ t ] k i [ t ] v i ⊤ [ t ] | {z } := H r [ t ] = P r [ t ] · S 0 [ t ] + H r [ t ] Our goal is to transform P r [ t ] and H r [ t ] into matrix forms suitable for parallel computation. We show that P r [ t ] , which involves the cumulative product of generalized Householder matrices, can be optimized using the classic WY representation. Proposition 1. The matrix P r [ t ] can be expressed as: P r [ t ] = Diag( γ r [ t ] ) − r X i =1 Diag( γ i → r [ t ] ) k i [ t ] w i ⊤ [ t ] (16) where the auxiliary vector w r [ t ] ∈ R d k is computed via the following recurrence relation: w r [ t ] = β r [ t ] Diag( γ r [ t ] ) k r [ t ] − r − 1 X i =1 w i [ t ]  k i ⊤ [ t ] Diag  γ i → r [ t ]  k r [ t ]  ! (17) Proof. We proceed with a proof by mathematical induction. Inductive Step: Assume the proposition holds for…
Deep dive

Hr[t]=∑i=1rDiag(γi→r[t])ki[t]ui⊤[t]H_r[t] = \sum_{i=1}^r \text{Diag}(\gamma_{i \to r}[t]) k_i[t] u_i^\top[t]

Sources

block

Kimi Linear: An Expressive, Efficient Attention Architecture T ECHNICAL R EPORT Proposition 2. The matrix H r [ t ] can be expressed as: H r [ t ] = r X i =1 Diag  γ i → r [ t ]  k i [ t ] u i ⊤ [ t ] (18) where the auxiliary vector u r [ t ] ∈ R d v is computed via the following recurrence relation: u r [ t ] = β r [ t ] v r [ t ] − r − 1 X i =1 u i [ t ]  k i ⊤ [ t ] Diag  γ i → r [ t ]  k r [ t ]  ! (19) Proof. We again use mathematical induction. Inductive Step: Assume the proposition holds for r − 1 . H r [ t ] =  I − β r [ t ] k r [ t ] k r ⊤ [ t ]  Diag( α r [ t ] ) H r − 1 [ t ] + β r [ t ] k r [ t ] v r ⊤ [ t ] =  I − β r [ t ] k r [ t ] k r ⊤ [ t ]  Diag( α r [ t ] ) r − 1 X i =1 Diag  γ i → r − 1 [ t ]  k i [ t ] u i ⊤ [ t ] ! + β r [ t ] k r [ t ] v r ⊤ [ t ] =  I − β r [ t ] k r [ t ] k r ⊤ [ t ]  r − 1 X i =1 Diag  γ i → r [ t ]  k i [ t ] u i ⊤ [ t ] ! + β r [ t ] k r [ t ] v r ⊤ [ t ] = r − 1 X i =1 Diag  γ i → r [ t ]  k i [ t ] u i ⊤ [ t ] − β r [ t ] k r [ t ] k r ⊤ [ t ] r − 1 X i =1 Diag  γ i → r [ t ]  k i [ t ] u i ⊤ [ t ] + β r [ t ] k r [ t ] v r ⊤ [ t ] = r − 1 X i =1 Diag  γ i → r [ t ]  k i [ t ] u i ⊤ [ t ] − k r [ t ] β r [ t ] r…
Deep dive

The auxiliary vectors wr[t]∈Rdkw_r[t] \in \mathbb{R}^{d_k} and ur[t]∈Rdvu_r[t] \in \mathbb{R}^{d_v} are computed via the following recurrence relations, which avoid expensive matrix inversions during state updates:

Sources

block

Kimi Linear: An Expressive, Efficient Attention Architecture T ECHNICAL R EPORT B Derivations for Chunkwise Parallelism of KDA We first recall the recurrent form of KDA: S r [ t ] = r Y i =1  I − β i [ t ] k i [ t ] k i ⊤ [ t ]  Diag( α i [ t ] ) ! | {z } := P r [ t ] · S 0 [ t ] + r X i =1   r Y j = i +1  I − β j [ t ] k j [ t ] k j ⊤ [ t ]  Diag( α j [ t ] )   · β i [ t ] k i [ t ] v i ⊤ [ t ] | {z } := H r [ t ] = P r [ t ] · S 0 [ t ] + H r [ t ] Our goal is to transform P r [ t ] and H r [ t ] into matrix forms suitable for parallel computation. We show that P r [ t ] , which involves the cumulative product of generalized Householder matrices, can be optimized using the classic WY representation. Proposition 1. The matrix P r [ t ] can be expressed as: P r [ t ] = Diag( γ r [ t ] ) − r X i =1 Diag( γ i → r [ t ] ) k i [ t ] w i ⊤ [ t ] (16) where the auxiliary vector w r [ t ] ∈ R d k is computed via the following recurrence relation: w r [ t ] = β r [ t ] Diag( γ r [ t ] ) k r [ t ] − r − 1 X i =1 w i [ t ]  k i ⊤ [ t ] Diag  γ i → r [ t ]  k r [ t ]  ! (17) Proof. We proceed with a proof by mathematical induction. Inductive Step: Assume the proposition holds for…

block

Kimi Linear: An Expressive, Efficient Attention Architecture T ECHNICAL R EPORT Proposition 2. The matrix H r [ t ] can be expressed as: H r [ t ] = r X i =1 Diag  γ i → r [ t ]  k i [ t ] u i ⊤ [ t ] (18) where the auxiliary vector u r [ t ] ∈ R d v is computed via the following recurrence relation: u r [ t ] = β r [ t ] v r [ t ] − r − 1 X i =1 u i [ t ]  k i ⊤ [ t ] Diag  γ i → r [ t ]  k r [ t ]  ! (19) Proof. We again use mathematical induction. Inductive Step: Assume the proposition holds for r − 1 . H r [ t ] =  I − β r [ t ] k r [ t ] k r ⊤ [ t ]  Diag( α r [ t ] ) H r − 1 [ t ] + β r [ t ] k r [ t ] v r ⊤ [ t ] =  I − β r [ t ] k r [ t ] k r ⊤ [ t ]  Diag( α r [ t ] ) r − 1 X i =1 Diag  γ i → r − 1 [ t ]  k i [ t ] u i ⊤ [ t ] ! + β r [ t ] k r [ t ] v r ⊤ [ t ] =  I − β r [ t ] k r [ t ] k r ⊤ [ t ]  r − 1 X i =1 Diag  γ i → r [ t ]  k i [ t ] u i ⊤ [ t ] ! + β r [ t ] k r [ t ] v r ⊤ [ t ] = r − 1 X i =1 Diag  γ i → r [ t ]  k i [ t ] u i ⊤ [ t ] − β r [ t ] k r [ t ] k r ⊤ [ t ] r − 1 X i =1 Diag  γ i → r [ t ]  k i [ t ] u i ⊤ [ t ] + β r [ t ] k r [ t ] v r ⊤ [ t ] = r − 1 X i =1 Diag  γ i → r [ t ]  k i [ t ] u i ⊤ [ t ] − k r [ t ] β r [ t ] r…
Deep dive

wr[t]=βr[t]Diag(γr[t])kr[t]−∑i=1r−1wi[t](ki⊤[t]Diag(γi→r[t])kr[t])w_r[t] = \beta_r[t] \text{Diag}(\gamma_r[t]) k_r[t] - \sum_{i=1}^{r-1} w_i[t] \left( k_i^\top[t] \text{Diag}(\gamma_{i \to r}[t]) k_r[t] \right)

Sources

block

Kimi Linear: An Expressive, Efficient Attention Architecture T ECHNICAL R EPORT B Derivations for Chunkwise Parallelism of KDA We first recall the recurrent form of KDA: S r [ t ] = r Y i =1  I − β i [ t ] k i [ t ] k i ⊤ [ t ]  Diag( α i [ t ] ) ! | {z } := P r [ t ] · S 0 [ t ] + r X i =1   r Y j = i +1  I − β j [ t ] k j [ t ] k j ⊤ [ t ]  Diag( α j [ t ] )   · β i [ t ] k i [ t ] v i ⊤ [ t ] | {z } := H r [ t ] = P r [ t ] · S 0 [ t ] + H r [ t ] Our goal is to transform P r [ t ] and H r [ t ] into matrix forms suitable for parallel computation. We show that P r [ t ] , which involves the cumulative product of generalized Householder matrices, can be optimized using the classic WY representation. Proposition 1. The matrix P r [ t ] can be expressed as: P r [ t ] = Diag( γ r [ t ] ) − r X i =1 Diag( γ i → r [ t ] ) k i [ t ] w i ⊤ [ t ] (16) where the auxiliary vector w r [ t ] ∈ R d k is computed via the following recurrence relation: w r [ t ] = β r [ t ] Diag( γ r [ t ] ) k r [ t ] − r − 1 X i =1 w i [ t ]  k i ⊤ [ t ] Diag  γ i → r [ t ]  k r [ t ]  ! (17) Proof. We proceed with a proof by mathematical induction. Inductive Step: Assume the proposition holds for…
Deep dive

ur[t]=βr[t]vr[t]−∑i=1r−1ui[t](ki⊤[t]Diag(γi→r[t])kr[t])u_r[t] = \beta_r[t] v_r[t] - \sum_{i=1}^{r-1} u_i[t] \left( k_i^\top[t] \text{Diag}(\gamma_{i \to r}[t]) k_r[t] \right)

Sources

block

Kimi Linear: An Expressive, Efficient Attention Architecture T ECHNICAL R EPORT Proposition 2. The matrix H r [ t ] can be expressed as: H r [ t ] = r X i =1 Diag  γ i → r [ t ]  k i [ t ] u i ⊤ [ t ] (18) where the auxiliary vector u r [ t ] ∈ R d v is computed via the following recurrence relation: u r [ t ] = β r [ t ] v r [ t ] − r − 1 X i =1 u i [ t ]  k i ⊤ [ t ] Diag  γ i → r [ t ]  k r [ t ]  ! (19) Proof. We again use mathematical induction. Inductive Step: Assume the proposition holds for r − 1 . H r [ t ] =  I − β r [ t ] k r [ t ] k r ⊤ [ t ]  Diag( α r [ t ] ) H r − 1 [ t ] + β r [ t ] k r [ t ] v r ⊤ [ t ] =  I − β r [ t ] k r [ t ] k r ⊤ [ t ]  Diag( α r [ t ] ) r − 1 X i =1 Diag  γ i → r − 1 [ t ]  k i [ t ] u i ⊤ [ t ] ! + β r [ t ] k r [ t ] v r ⊤ [ t ] =  I − β r [ t ] k r [ t ] k r ⊤ [ t ]  r − 1 X i =1 Diag  γ i → r [ t ]  k i [ t ] u i ⊤ [ t ] ! + β r [ t ] k r [ t ] v r ⊤ [ t ] = r − 1 X i =1 Diag  γ i → r [ t ]  k i [ t ] u i ⊤ [ t ] − β r [ t ] k r [ t ] k r ⊤ [ t ] r − 1 X i =1 Diag  γ i → r [ t ]  k i [ t ] u i ⊤ [ t ] + β r [ t ] k r [ t ] v r ⊤ [ t ] = r − 1 X i =1 Diag  γ i → r [ t ]  k i [ t ] u i ⊤ [ t ] − k r [ t ] β r [ t ] r…