librarylibs/MoE/src/MoE.xtl

MoE: mixture-of-experts layers: router scores, top-k gates, experts as adapted projections, the sparse combine, gradients, routing statistics and an expert cache

Import it with an alias of your choice: "moe:" u_se< "MoE". Put libs/MoE/src on XETAL_PATH ("just path"); the reference is libs/MoE/docs. Names with l: are exported; h: names are private to this file.

Tokens are columns, as in the LoRA library: x is n x N, N tokens of n numbers. The router R (E x n) scores each token against E experts; each token's scores become probabilities over the experts (a column's softmax), and its k most likely experts are kept, their probabilities renormalized over those k: the gates G (E x N, 0 where an expert is not chosen). An expert here is an adapted projection, W_e x + s B_e (A_e x) (the LoRA library's layer); the experts are stacked, (Ws, As, Bs, s): Ws E x m x n, As E x r x n, Bs E x m x r, one scale s. The layer is y = sum over the chosen e of G_e (W_e x + s B_e (A_e x)), each token through its k experts only. Every function takes its data on the right, so each can be a Flow stage.

source · imports lo: libs/LoRA/src/LoRA.xtl libs/LoRA/src/LoRA.xtlm

Helpers (private)

ʰc̲ols : a -> b -> a

function (private) · line 25

The vector v (one number per token) repeated down each row of a matrix shaped as M: v's j-th number in column j.

ʰc̲ols ← { v M → (s̲hape M) r̲eshape v }

ʰp̲ick : Int -> Int -> Float

function (private) · line 28

The one-hot columns of the tokens idx among N: an N x t_ally idx matrix whose column j is 1 at token idx[j].

ʰp̲ick ← { N idx → f̲loat (r̲ange N) '= t̲able idx }
Used in: ˡc̲ombine

Routing

ˡs̲cores : Num a => a -> a -> a

function · line 37

R s̲cores x: each token's score for each expert, R x (E x N).

      "moe:" u̲se< "MoE"
      (2 2 r̲eshape 1.0 0.0 0.0 1.0) ᵐᵒᵉs̲cores 2 1 r̲eshape 3.0 -1.0
 3.0
-1.0
ˡs̲cores ← { R x → R '+ '× i̲nner x }

ˡs̲oftmax : Num a => a -> Float

function · line 46

s̲oftmax S: each column (a token) into probabilities over the experts; the column's largest is taken off first (the same result, no overflow).

      "moe:" u̲se< "MoE"
      ᵐᵒᵉs̲oftmax 2 1 r̲eshape 0.0 0.6931471805599453
0.3333333333333333
0.6666666666666666
ˡs̲oftmax ← { S →
  e ← e̲xp S − ('m̲ax r̲/₁ S) ʰc̲ols S
  e ÷ ('+ r̲/₁ e) ʰc̲ols e
}

ˡm̲ask : Int -> Float -> Float

function · line 59

k m̲ask P: 1 at each token's k most likely experts, 0 elsewhere (the largest, taken out, then the largest of what is left; a tie keeps every expert at the tie).

      "moe:" u̲se< "MoE"
      1 ᵐᵒᵉm̲ask 3 2 r̲eshape 0.2 0.5 0.7 0.1 0.1 0.4
0.0 1.0
1.0 0.0
0.0 0.0
ˡm̲ask ← { k P →
  (_, M) ← k '{ (Q, M) →
    m ← f̲loat Q = ('m̲ax r̲/₁ Q) ʰc̲ols Q
    (Q − 2.0 × m, M + m)
  } p̲ower (P, 0.0 × P)
  M
}

ˡt̲opk : Int -> Float -> Float

function · line 74

k t̲opk P: the gates: each token's k most likely experts, their probabilities over those k's sum (Mixtral's), 0 for the rest.

      "moe:" u̲se< "MoE"
      2 ᵐᵒᵉt̲opk 3 1 r̲eshape 0.5 0.3 0.2
              0.625
0.37499999999999994
                0.0
ˡt̲opk ← { k P →
  G ← P × k ˡm̲ask P
  G ÷ ('+ r̲/₁ G) ʰc̲ols G
}

Experts

ˡa̲pply : Num a => (a, a, a, a) -> (Int, a) -> a

function · line 83

(Ws, As, Bs, s) a̲pply (e, x): expert e (from 1) on the tokens x, W_e x + s B_e (A_e x), as the LoRA library computes it.

ˡa̲pply ← { (Ws, As, Bs, s) (e, x) → (e s̲elect Ws, e s̲elect As, e s̲elect Bs, s) ˡᵒf̲orward x }

ˡc̲ombine : ((Float, Float, Float, Float), Float) -> Float -> Float

function · line 89

(experts, G) c̲ombine x: the layer's output for the gates G: each expert run only on the tokens that chose it (picked out as columns, then put back), times their gates, summed: sum over the chosen e of G_e (W_e x + s B_e (A_e x)).

ˡc̲ombine ← { ((Ws, As, Bs, s), G) x →
  N ← 2 s̲elect s̲hape x
  m ← 2 s̲elect s̲hape Ws
  E ← f̲irst s̲hape Ws
  (y, _) ← E '{ (y, e) →
    idx ← w̲here (e s̲elect G) > 0.0
    0 = t̲ally idx ? (y, e + 1)
    P ← N ʰp̲ick idx
    ye ← ((Ws, As, Bs, s) ˡa̲pply (e, x '+ '× i̲nner P)) '+ '× i̲nner o̲\ P
    (y + ye × (e s̲elect G) ʰc̲ols ye, e + 1)
  } p̲ower ((m c̲at N) r̲eshape 0.0, 1)
  y
}

ˡd̲ense : ((Float, Float, Float, Float), Float) -> Float -> Float

function · line 106

(experts, G) d̲ense x: the same sum with every expert run on every token (an unchosen one's gate is 0): the reference c_ombine is checked against.

ˡd̲ense ← { ((Ws, As, Bs, s), G) x →
  E ← f̲irst s̲hape Ws
  (y, _) ← E '{ (y, e) →
    ye ← (Ws, As, Bs, s) ˡa̲pply (e, x)
    (y + ye × (e s̲elect G) ʰc̲ols ye, e + 1)
  } p̲ower (0.0 × (Ws, As, Bs, s) ˡa̲pply (1, x), 1)
  y
}

ˡl̲ayer : (Float, (Float, Float, Float, Float), Int) -> Float -> Float

function · line 122

(R, experts, k) l̲ayer x: the whole layer: scores, probabilities, the top-k gates, the sparse combine.

      "moe:" u̲se< "MoE"
      ex ← (2 2 2 r̲eshape 1.0 0.0 0.0 1.0 2.0 0.0 0.0 2.0, 2 1 2 r̲eshape 0.0, 2 2 1 r̲eshape 0.0, 1.0)
      (2 2 r̲eshape 1.0 0.0 0.0 1.0, ex, 1) ᵐᵒᵉl̲ayer 2 2 r̲eshape 3.0 -1.0 -1.0 3.0
 3.0 -2.0
-1.0  6.0
ˡl̲ayer ← { (R, experts, k) x → (experts, k ˡt̲opk ˡs̲oftmax R ˡs̲cores x) ˡc̲ombine x }

Gradients, the selection fixed

ˡg̲rads : (Float, (Float, Float, Float, Float), Int) -> (Float, Float) -> (Float, Float, Float, Float)

function · line 135

(R, (Ws, As, Bs, s), k) g̲rads (x, g): the gradients for the tokens x and g, the loss's gradient at the layer's output (m x N), each token's chosen experts held fixed (the top-k is not differentiable; a small change keeps it): (dR, dAs, dBs, dx). An expert's gradients are the LoRA library's with g times its gates; the router's go through the gates, a softmax over each token's chosen experts: dL/dS_e = G_e (h_e - sum_i G_i h_i) for a chosen e, h_e = g . y_e the loss's gradient by the gate; dR = dS x'. dx gathers every chosen expert's and the router's, R' dS.

ˡg̲rads ← { (R, (Ws, As, Bs, s), k) (x, g) →
  E ← f̲irst s̲hape Ws
  G ← k ˡt̲opk ˡs̲oftmax R ˡs̲cores x
  (dA, dB, dx, H, _) ← E '{ (dA, dB, dx, H, e) →
    ye ← (Ws, As, Bs, s) ˡa̲pply (e, x)
    ge ← g × (e s̲elect G) ʰc̲ols g
    (a, b, d) ← (e s̲elect Ws, e s̲elect As, e s̲elect Bs, s) ˡᵒg̲rads (x, ge)
    (dA c̲at r̲avel a, dB c̲at r̲avel b, dx + d, H c̲at '+ r̲/₁ g × ye, e + 1)
  } p̲ower (0 r̲eshape 0.0, 0 r̲eshape 0.0, 0.0 × x, 0 r̲eshape 0.0, 1)
  Hm ← (s̲hape G) r̲eshape H
  dS ← G × Hm − ('+ r̲/₁ G × Hm) ʰc̲ols G
  (dS '+ '× i̲nner o̲\ x, (s̲hape As) r̲eshape dA, (s̲hape Bs) r̲eshape dB, dx + (o̲\ R) '+ '× i̲nner dS)
}
Used in: ᵘb̲ack6

ˡg̲radsW : (Any b, Any c, Any d) => (Float, (a, b, c, d), Int) -> (Float, Float) -> Float

function · line 158

(R, experts, k) g̲radsW (x, g): the gradients of the experts' base weights Ws (E x m x n), for training the experts themselves rather than adapters (a base model): expert e's is (g G_e) x', g times its gates, the same with any adapter, 0 for an expert no token chose.

      "moe:" u̲se< "MoE"
      ex ← (2 1 1 r̲eshape 2.0 3.0, 2 1 1 r̲eshape 0.0, 2 1 1 r̲eshape 0.0, 1.0)
      r̲avel (2 1 r̲eshape 0.0 1.0, ex, 1) ᵐᵒᵉg̲radsW (1 1 r̲eshape 1.0, 1 1 r̲eshape 1.0)
0.0 1.0
ˡg̲radsW ← { (R, (Ws, As, Bs, s), k) (x, g) →
  E ← f̲irst s̲hape Ws
  G ← k ˡt̲opk ˡs̲oftmax R ˡs̲cores x
  (dW, _) ← E '{ (dW, e) → (dW c̲at r̲avel (g × (e s̲elect G) ʰc̲ols g) '+ '× i̲nner o̲\ x, e + 1) } p̲ower (0 r̲eshape 0.0, 1)
  (s̲hape Ws) r̲eshape dW
}
Used in: ᵘb̲ack6

Routing statistics

ˡf̲requency : Float -> Float

function · line 172

f̲requency G: how often each expert is chosen: the fraction of tokens whose gates include it.

      "moe:" u̲se< "MoE"
      ᵐᵒᵉf̲requency 2 4 r̲eshape 1.0 0.5 0.0 1.0 0.0 0.5 1.0 0.0
0.75 0.5
ˡf̲requency ← { G → ('+ r̲/₂ f̲loat G > 0.0) ÷ f̲loat 2 s̲elect s̲hape G }

ˡe̲ntropy : Float -> Float

function · line 180

e̲ntropy P: the mean over tokens of the entropy of their probabilities over the experts, in nats (log E for a router that cannot choose, 0 for a certain one).

      "moe:" u̲se< "MoE"
      ᵐᵒᵉe̲ntropy 2 1 r̲eshape 0.5 0.5
0.6931471805599453
ˡe̲ntropy ← { P → ('+ r̲/ r̲avel n̲eg P × l̲og 0.000000000001 m̲ax P) ÷ f̲loat 2 s̲elect s̲hape P }

ˡb̲alance : (Float, Float) -> Int -> Float

function · line 189

(P, G) b̲alance k: the Switch Transformer's load-balancing loss for top-k, E sum_e f_e P_e: f_e the share of the k N choices expert e got, P_e its mean probability. 1 when both are even, up to E when one expert takes everything.

      "moe:" u̲se< "MoE"
      (2 2 r̲eshape 0.5 0.5 0.5 0.5, 2 2 r̲eshape 1.0 0.0 0.0 1.0) ᵐᵒᵉb̲alance 1
1.0
ˡb̲alance ← { (P, G) k →
  E ← f̲irst s̲hape P
  N ← 2 s̲elect s̲hape P
  f ← ('+ r̲/₂ f̲loat G > 0.0) ÷ f̲loat k × N
  (f̲loat E) × '+ r̲/ f × ('+ r̲/₂ P) ÷ f̲loat N
}

An expert cache

ˡu̲sed : Int -> Float -> Float

function · line 206

b u̲sed G: which experts each batch of b tokens needs: the gates G (E x N) in batches of b tokens in turn (a last part batch left out), an E x (N / b) matrix, 1 where an expert serves a token of the batch.

      "moe:" u̲se< "MoE"
      2 ᵐᵒᵉu̲sed 3 4 r̲eshape 0.6 0.5 0.0 0.0 0.4 0.0 0.0 1.0 0.0 0.5 1.0 0.0
1.0 0.0
1.0 1.0
1.0 1.0
ˡu̲sed ← { b G →
  E ← f̲irst s̲hape G
  T ← (2 s̲elect s̲hape G) d̲iv b
  'm̲ax r̲/₃ (E c̲at T c̲at b) r̲eshape (E × T × b) t̲ake r̲avel f̲loat G > 0.0
}
Used in: U1, U2

ˡl̲ru : Int -> Float -> Float

function · line 223

c l̲ru U: a cache of c slots, least recently used out first, over the needs U (K x T: 1 where step t needs key k, an expert or an adapter): K x T, 1 where step t had to load key k (it was not held). After each step the cache holds the c keys used last (a tie by the higher key), so a step needing more than c keys loads them all and keeps c. Its sum is the loads; times a key's bytes, what moved.

      "moe:" u̲se< "MoE"
      2 ᵐᵒᵉl̲ru 3 6 r̲eshape 1.0 0.0 1.0 0.0 1.0 1.0 0.0 1.0 0.0 0.0 0.0 1.0 1.0 1.0 0.0 1.0 0.0 0.0
1.0 0.0 1.0 0.0 0.0 0.0
0.0 1.0 0.0 0.0 0.0 1.0
1.0 0.0 0.0 0.0 0.0 0.0
ˡl̲ru ← { c U →
  K ← f̲irst s̲hape U
  T ← 2 s̲elect s̲hape U
  (_, _, L, _) ← T '{ (last, held, L, t) →
    u ← r̲avel (t s̲elect o̲\ U)
    load ← u × 1.0 − held
    last2 ← (u × f̲loat t) + last × 1.0 − u
    key ← (((f̲loat K) × last2) + f̲loat r̲ange K) ÷ f̲loat K × T + 1
    held2 ← (r̲avel (c m̲in K) ˡm̲ask (K c̲at 1) r̲eshape key) × f̲loat last2 > 0.0
    (last2, held2, L c̲at load, t + 1)
  } p̲ower (K r̲eshape 0.0, K r̲eshape 0.0, 0 r̲eshape 0.0, 1)
  o̲\ (T c̲at K) r̲eshape L
}
Used in: ᵘt̲raffic