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.
Helpers (private)
ʰc̲ols : a -> b -> a
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
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 }
Routing
ˡs̲cores : Num a => a -> a -> a
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
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
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
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
(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
(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
(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
(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)
(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) }
ˡg̲radsW : (Any b, Any c, Any d) => (Float, (a, b, c, d), Int) -> (Float, Float) -> Float
(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 }
Routing statistics
ˡf̲requency : Float -> Float
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
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
(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
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 }
ˡl̲ru : Int -> Float -> Float
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 }