sourcelibs/MoE/src/MoE.xtl

1⍝│ MoE: mixture-of-experts layers: router scores, top-k gates, experts as adapted projections, the sparse combine, gradients, routing statistics and an expert cache 2⍝│ 3⍝│ Import it with an alias of your choice: "moe:" u_se< "MoE". 4⍝│ Put libs/MoE/src on XETAL_PATH ("just path"); the reference is libs/MoE/docs. 5⍝│ Names with l: are exported; h: names are private to this file. 6⍝│ 7⍝│ Tokens are columns, as in the LoRA library: x is n x N, N tokens of 8⍝│ n numbers. The router R (E x n) scores each token against E experts; 9⍝│ each token's scores become probabilities over the experts (a 10⍝│ column's softmax), and its k most likely experts are kept, their 11⍝│ probabilities renormalized over those k: the gates G (E x N, 0 where 12⍝│ an expert is not chosen). An expert here is an adapted projection, 13⍝│ W_e x + s B_e (A_e x) (the LoRA library's layer); the experts are 14⍝│ stacked, (Ws, As, Bs, s): Ws E x m x n, As E x r x n, Bs E x m x r, 15⍝│ one scale s. The layer is y = sum over the chosen e of G_e (W_e x + 16⍝│ s B_e (A_e x)), each token through its k experts only. Every 17⍝│ function takes its data on the right, so each can be a Flow stage. 18 19"lo:" u̲se< "LoRA" 20 21⍝━━ Helpers (private) 22 23⍝│ The vector v (one number per token) repeated down each row of a 24⍝│ matrix shaped as M: v's j-th number in column j. 25ʰc̲ols ← { v M → (s̲hape M) r̲eshape v } 26⍝│ The one-hot columns of the tokens idx among N: an N x t_ally idx 27⍝│ matrix whose column j is 1 at token idx[j]. 28ʰp̲ick ← { N idx → f̲loat (r̲ange N) '= t̲able idx } 29 30⍝━━ Routing 31 32⍝│ R s̲cores x: each token's score for each expert, R x (E x N). 33⍝│ >> "moe:" u_se< "MoE" 34⍝│ >> (2 2 r_eshape 1.0 0.0 0.0 1.0) moe:s_cores 2 1 r_eshape 3.0 -1.0 35⍝│ 3.0 36⍝│ -1.0 37ˡs̲cores ← { R x → R '+ '× i̲nner x } 38 39⍝│ s̲oftmax S: each column (a token) into probabilities over the 40⍝│ experts; the column's largest is taken off first (the same result, 41⍝│ no overflow). 42⍝│ >> "moe:" u_se< "MoE" 43⍝│ >> moe:s_oftmax 2 1 r_eshape 0.0 0.6931471805599453 44⍝│ 0.3333333333333333 45⍝│ 0.6666666666666666 46ˡs̲oftmax ← { S → 47 e ← e̲xp S − ('m̲ax r̲/₁ S) ʰc̲ols S 48 e ÷ ('+ r̲/₁ e) ʰc̲ols e 49} 50 51⍝│ k m̲ask P: 1 at each token's k most likely experts, 0 elsewhere 52⍝│ (the largest, taken out, then the largest of what is left; a tie 53⍝│ keeps every expert at the tie). 54⍝│ >> "moe:" u_se< "MoE" 55⍝│ >> 1 moe:m_ask 3 2 r_eshape 0.2 0.5 0.7 0.1 0.1 0.4 56⍝│ 0.0 1.0 57⍝│ 1.0 0.0 58⍝│ 0.0 0.0 59ˡm̲ask ← { k P → 60 (_, M) ← k '{ (Q, M) → 61 m ← f̲loat Q = ('m̲ax r̲/₁ Q) ʰc̲ols Q 62 (Q − 2.0 × m, M + m) 63 } p̲ower (P, 0.0 × P) 64 M 65} 66 67⍝│ k t̲opk P: the gates: each token's k most likely experts, their 68⍝│ probabilities over those k's sum (Mixtral's), 0 for the rest. 69⍝│ >> "moe:" u_se< "MoE" 70⍝│ >> 2 moe:t_opk 3 1 r_eshape 0.5 0.3 0.2 71⍝│ 0.625 72⍝│ 0.37499999999999994 73⍝│ 0.0 74ˡt̲opk ← { k P → 75 G ← P × k ˡm̲ask P 76 G ÷ ('+ r̲/₁ G) ʰc̲ols G 77} 78 79⍝━━ Experts 80 81⍝│ (Ws, As, Bs, s) a̲pply (e, x): expert e (from 1) on the tokens x, 82⍝│ W_e x + s B_e (A_e x), as the LoRA library computes it. 83ˡa̲pply ← { (Ws, As, Bs, s) (e, x) → (e s̲elect Ws, e s̲elect As, e s̲elect Bs, s) ˡᵒf̲orward x } 84 85⍝│ (experts, G) c̲ombine x: the layer's output for the gates G: each 86⍝│ expert run only on the tokens that chose it (picked out as columns, 87⍝│ then put back), times their gates, summed: sum over the chosen e of 88⍝│ G_e (W_e x + s B_e (A_e x)). 89ˡc̲ombine ← { ((Ws, As, Bs, s), G) x → 90 N ← 2 s̲elect s̲hape x 91 m ← 2 s̲elect s̲hape Ws 92 E ← f̲irst s̲hape Ws 93 (y, _) ← E '{ (y, e) → 94 idx ← w̲here (e s̲elect G) > 0.0 95 0 = t̲ally idx ? (y, e + 1) 96 P ← N ʰp̲ick idx 97 ye ← ((Ws, As, Bs, s) ˡa̲pply (e, x '+ '× i̲nner P)) '+ '× i̲nner o̲\ P 98 (y + ye × (e s̲elect G) ʰc̲ols ye, e + 1) 99 } p̲ower ((m c̲at N) r̲eshape 0.0, 1) 100 y 101} 102 103⍝│ (experts, G) d̲ense x: the same sum with every expert run on every 104⍝│ token (an unchosen one's gate is 0): the reference c_ombine is 105⍝│ checked against. 106ˡd̲ense ← { ((Ws, As, Bs, s), G) x → 107 E ← f̲irst s̲hape Ws 108 (y, _) ← E '{ (y, e) → 109 ye ← (Ws, As, Bs, s) ˡa̲pply (e, x) 110 (y + ye × (e s̲elect G) ʰc̲ols ye, e + 1) 111 } p̲ower (0.0 × (Ws, As, Bs, s) ˡa̲pply (1, x), 1) 112 y 113} 114 115⍝│ (R, experts, k) l̲ayer x: the whole layer: scores, probabilities, 116⍝│ the top-k gates, the sparse combine. 117⍝│ >> "moe:" u_se< "MoE" 118⍝│ >> 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) 119⍝│ >> (2 2 r_eshape 1.0 0.0 0.0 1.0, ex, 1) moe:l_ayer 2 2 r_eshape 3.0 -1.0 -1.0 3.0 120⍝│ 3.0 -2.0 121⍝│ -1.0 6.0 122ˡl̲ayer ← { (R, experts, k) x → (experts, k ˡt̲opk ˡs̲oftmax R ˡs̲cores x) ˡc̲ombine x } 123 124⍝━━ Gradients, the selection fixed 125 126⍝│ (R, (Ws, As, Bs, s), k) g̲rads (x, g): the gradients for the 127⍝│ tokens x and g, the loss's gradient at the layer's output (m x N), 128⍝│ each token's chosen experts held fixed (the top-k is not 129⍝│ differentiable; a small change keeps it): (dR, dAs, dBs, dx). An 130⍝│ expert's gradients are the LoRA library's with g times its gates; 131⍝│ the router's go through the gates, a softmax over each token's 132⍝│ chosen experts: dL/dS_e = G_e (h_e - sum_i G_i h_i) for a chosen e, 133⍝│ h_e = g . y_e the loss's gradient by the gate; dR = dS x'. dx gathers 134⍝│ every chosen expert's and the router's, R' dS. 135ˡg̲rads ← { (R, (Ws, As, Bs, s), k) (x, g) → 136 E ← f̲irst s̲hape Ws 137 G ← k ˡt̲opk ˡs̲oftmax R ˡs̲cores x 138 (dA, dB, dx, H, _) ← E '{ (dA, dB, dx, H, e) → 139 ye ← (Ws, As, Bs, s) ˡa̲pply (e, x) 140 ge ← g × (e s̲elect G) ʰc̲ols g 141 (a, b, d) ← (e s̲elect Ws, e s̲elect As, e s̲elect Bs, s) ˡᵒg̲rads (x, ge) 142 (dA c̲at r̲avel a, dB c̲at r̲avel b, dx + d, H c̲at '+ r̲/₁ g × ye, e + 1) 143 } p̲ower (0 r̲eshape 0.0, 0 r̲eshape 0.0, 0.0 × x, 0 r̲eshape 0.0, 1) 144 Hm ← (s̲hape G) r̲eshape H 145 dS ← G × Hm − ('+ r̲/₁ G × Hm) ʰc̲ols G 146 (dS '+ '× i̲nner o̲\ x, (s̲hape As) r̲eshape dA, (s̲hape Bs) r̲eshape dB, dx + (o̲\ R) '+ '× i̲nner dS) 147} 148 149⍝│ (R, experts, k) g̲radsW (x, g): the gradients of the experts' 150⍝│ base weights Ws (E x m x n), for training the experts themselves 151⍝│ rather than adapters (a base model): expert e's is (g G_e) x', g 152⍝│ times its gates, the same with any adapter, 0 for an expert no 153⍝│ token chose. 154⍝│ >> "moe:" u_se< "MoE" 155⍝│ >> 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) 156⍝│ >> r_avel (2 1 r_eshape 0.0 1.0, ex, 1) moe:g_radsW (1 1 r_eshape 1.0, 1 1 r_eshape 1.0) 157⍝│ 0.0 1.0 158ˡg̲radsW ← { (R, (Ws, As, Bs, s), k) (x, g) → 159 E ← f̲irst s̲hape Ws 160 G ← k ˡt̲opk ˡs̲oftmax R ˡs̲cores x 161 (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) 162 (s̲hape Ws) r̲eshape dW 163} 164 165⍝━━ Routing statistics 166 167⍝│ f̲requency G: how often each expert is chosen: the fraction of 168⍝│ tokens whose gates include it. 169⍝│ >> "moe:" u_se< "MoE" 170⍝│ >> moe:f_requency 2 4 r_eshape 1.0 0.5 0.0 1.0 0.0 0.5 1.0 0.0 171⍝│ 0.75 0.5 172ˡf̲requency ← { G → ('+ r̲/₂ f̲loat G > 0.0) ÷ f̲loat 2 s̲elect s̲hape G } 173 174⍝│ e̲ntropy P: the mean over tokens of the entropy of their 175⍝│ probabilities over the experts, in nats (log E for a router that 176⍝│ cannot choose, 0 for a certain one). 177⍝│ >> "moe:" u_se< "MoE" 178⍝│ >> moe:e_ntropy 2 1 r_eshape 0.5 0.5 179⍝│ 0.6931471805599453 180ˡe̲ntropy ← { P → ('+ r̲/ r̲avel n̲eg P × l̲og 0.000000000001 m̲ax P) ÷ f̲loat 2 s̲elect s̲hape P } 181 182⍝│ (P, G) b̲alance k: the Switch Transformer's load-balancing loss for 183⍝│ top-k, E sum_e f_e P_e: f_e the share of the k N choices expert e 184⍝│ got, P_e its mean probability. 1 when both are even, up to E when 185⍝│ one expert takes everything. 186⍝│ >> "moe:" u_se< "MoE" 187⍝│ >> (2 2 r_eshape 0.5 0.5 0.5 0.5, 2 2 r_eshape 1.0 0.0 0.0 1.0) moe:b_alance 1 188⍝│ 1.0 189ˡb̲alance ← { (P, G) k → 190 E ← f̲irst s̲hape P 191 N ← 2 s̲elect s̲hape P 192 f ← ('+ r̲/₂ f̲loat G > 0.0) ÷ f̲loat k × N 193 (f̲loat E) × '+ r̲/ f × ('+ r̲/₂ P) ÷ f̲loat N 194} 195 196⍝━━ An expert cache 197 198⍝│ b u̲sed G: which experts each batch of b tokens needs: the gates G 199⍝│ (E x N) in batches of b tokens in turn (a last part batch left out), 200⍝│ an E x (N / b) matrix, 1 where an expert serves a token of the batch. 201⍝│ >> "moe:" u_se< "MoE" 202⍝│ >> 2 moe: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 203⍝│ 1.0 0.0 204⍝│ 1.0 1.0 205⍝│ 1.0 1.0 206ˡu̲sed ← { b G → 207 E ← f̲irst s̲hape G 208 T ← (2 s̲elect s̲hape G) d̲iv b 209 'm̲ax r̲/₃ (E c̲at T c̲at b) r̲eshape (E × T × b) t̲ake r̲avel f̲loat G > 0.0 210} 211 212⍝│ c l̲ru U: a cache of c slots, least recently used out first, over 213⍝│ the needs U (K x T: 1 where step t needs key k, an expert or an 214⍝│ adapter): K x T, 1 where step t had to load key k (it was not held). 215⍝│ After each step the cache holds the c keys used last (a tie by the 216⍝│ higher key), so a step needing more than c keys loads them all and 217⍝│ keeps c. Its sum is the loads; times a key's bytes, what moved. 218⍝│ >> "moe:" u_se< "MoE" 219⍝│ >> 2 moe: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 220⍝│ 1.0 0.0 1.0 0.0 0.0 0.0 221⍝│ 0.0 1.0 0.0 0.0 0.0 1.0 222⍝│ 1.0 0.0 0.0 0.0 0.0 0.0 223ˡl̲ru ← { c U → 224 K ← f̲irst s̲hape U 225 T ← 2 s̲elect s̲hape U 226 (_, _, L, _) ← T '{ (last, held, L, t) → 227 u ← r̲avel (t s̲elect o̲\ U) 228 load ← u × 1.0 − held 229 last2 ← (u × f̲loat t) + last × 1.0 − u 230 key ← (((f̲loat K) × last2) + f̲loat r̲ange K) ÷ f̲loat K × T + 1 231 held2 ← (r̲avel (c m̲in K) ˡm̲ask (K c̲at 1) r̲eshape key) × f̲loat last2 > 0.0 232 (last2, held2, L c̲at load, t + 1) 233 } p̲ower (K r̲eshape 0.0, K r̲eshape 0.0, 0 r̲eshape 0.0, 1) 234 o̲\ (T c̲at K) r̲eshape L 235}