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}