nx_bpe.nx source
↩ module page · 495 lines · 18152 B
1// nx_bpe.nx -- Byte-Pair Encoding tokenizer.
2//
3// Closes the TEXT-INTERFACE gap. With this brick the substrate can
4// convert input text -> token IDs (encode) and token IDs -> text
5// (decode), completing the input/output bookends around the
6// transformer compute pipeline.
7//
8// Combined with nx_gguf (model loader, 7b4fafc6), nx_embedding (token
9// lookup, 84725593), nx_transformer_block (forward, 8efc7edb), and
10// nx_token_sample (logits sampling, 68e63138), the substrate now has
11// the COMPLETE end-to-end inference path -- pure NishiLang, zero
12// PyTorch, zero CUDA, zero llama.cpp dependency.
13//
14// ===== Algorithm (Sennrich/Haddow/Birch 2016) =====================
15//
16// BPE starts with a base vocabulary of bytes (256 entries 0..255).
17// Training collects an ordered list of merge rules: pairs of token
18// IDs that recur frequently get merged into a new token ID.
19//
20// Encoding (Sennrich 2016, Algorithm 1):
21// 1. Split input text into single bytes (each is an initial token).
22// 2. Find the adjacent token-pair with the LOWEST rank (= highest
23// priority) in the merge table.
24// 3. Apply that merge: replace the pair with the merged token ID.
25// 4. Repeat until no pair has a rank.
26//
27// Decoding: concatenate the byte sequences of each token in order.
28//
29// ===== Substrate composition =====================================
30//
31// nx_intern.nx -- canonical byte-string <-> ID table
32// (the vocab itself)
33// nx_loop -- bounded loops; budget = n_input * n_merges
34// hard ceiling per JPL Rule 2
35//
36// v1 perf: linear scan over the merge table per merge-decision step.
37// For 50k merges + 100-token output that's ~5M comparisons total.
38// O(1) pair lookup via nx_map (key = a*MAX_VOCAB + b) is the
39// queued v2 perf upgrade.
40//
41// genealogy_id: sennrich_haddow_birch_2016_bpe + gage_1994_byte_pair_data_compression +
42// openai_gpt2_2019_byte_level_bpe
43// lineage_id: substrate_bpe_v1
44
45// nx_safety_envelope:
46// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
47// sil_target: SIL1
48// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
49// verdict: NOT_YET_EVALUATED
50
51import "nx_syscalls.nx"
52import "nx_tier.nx"
53import "nx_loop.nx"
54import "nx_intern.nx"
55
56// ===== Sealed-enum: BpeVerdict ====================================
57
58const NX_BPE_OK: nx_int = 0
59const NX_BPE_ERR_OOB: nx_int = 1
60const NX_BPE_ERR_BAD_VOCAB: nx_int = 2
61const NX_BPE_ERR_BUDGET: nx_int = 3
62const NX_BPE_ERR_BAD_TOKEN: nx_int = 4
63const NX_BPE_N_VERDICTS: nx_int = 5
64
65func nx_bpe_verdict_is_valid(v: nx_int) -> nx_int {
66 if v < 0 { return 0 }
67 if v >= NX_BPE_N_VERDICTS { return 0 }
68 return 1
69}
70
71// ===== Vocab + merge-rules structure =============================
72//
73// intern: bytes <-> ID (token ID is the intern's returned i64)
74// merges: flat array of (a, b, merged) triples. Position in the
75// array IS the merge rank (lower index = higher priority).
76
77struct NxBpeMerge {
78 a: i64, // left token ID
79 b: i64, // right token ID
80 merged: i64 // merged token ID
81}
82
83const NX_BPE_MERGE_BYTES: nx_int = 24 // 3 fields * 8
84
85struct NxBpeVocab {
86 intern: *NxIntern,
87 merges: *NxBpeMerge,
88 n_merges: nx_int,
89 cap: nx_int
90}
91
92const NX_BPE_VOCAB_BYTES: nx_int = 32 // 4 fields * 8
93
94func nx_bpe_vocab_new(intern_bytes_cap: i64, intern_ids_cap: i64,
95 n_merges_cap: nx_int) -> *NxBpeVocab {
96 let v: *NxBpeVocab = sys_mmap(NX_BPE_VOCAB_BYTES) as *NxBpeVocab
97 v.intern = nx_intern_new(intern_bytes_cap, intern_ids_cap)
98 v.merges = sys_mmap(n_merges_cap * NX_BPE_MERGE_BYTES) as *NxBpeMerge
99 v.n_merges = 0
100 v.cap = n_merges_cap
101 return v
102}
103
104// Register a byte sequence as a token (returns the assigned ID).
105// Wrapper over nx_intern_get for caller convenience + naming.
106func nx_bpe_add_token(v: *NxBpeVocab, bytes: *u8, len: i64) -> i64 {
107 return nx_intern_get(v.intern, bytes, len)
108}
109
110// Register a merge rule. Rank = position in the merges array.
111func nx_bpe_add_merge(v: *NxBpeVocab, a: i64, b: i64, merged: i64) -> nx_int {
112 if v.n_merges >= v.cap { return 0 - 1 }
113 let idx: nx_int = v.n_merges
114 let m: *NxBpeMerge = (v.merges as i64 + idx * NX_BPE_MERGE_BYTES) as *NxBpeMerge
115 m.a = a
116 m.b = b
117 m.merged = merged
118 v.n_merges = v.n_merges + 1
119 return idx
120}
121
122// Find the lowest-rank merge rule matching (a, b). Returns rank
123// (0..n_merges) or -1 if no rule matches.
124
125func _bpe_find_merge_rank(v: *NxBpeVocab, a: i64, b: i64) -> nx_int {
126 var r: nx_int = 0
127 var iter: nx_int = 0
128 var verdict: nx_int = NX_LOOP_RUNNING
129 let BUDGET: nx_int = v.n_merges
130 while verdict == NX_LOOP_RUNNING && iter < BUDGET {
131 let m: *NxBpeMerge = (v.merges as i64 + r * NX_BPE_MERGE_BYTES) as *NxBpeMerge
132 if m.a == a {
133 if m.b == b {
134 return r
135 }
136 }
137 r = r + 1
138 iter = iter + 1
139 }
140 return 0 - 1
141}
142
143// ===== Encode: text bytes -> token IDs ============================
144//
145// text: input bytes [n]
146// out_tokens: caller-allocated [>= n] i64 array (max possible = n)
147//
148// Returns the number of tokens emitted, or NX_BPE_ERR_* (negative).
149//
150// Algorithm:
151// 1. Split text into bytes -> initial tokens (one per byte).
152// 2. Repeatedly find the adjacent pair with the lowest merge rank
153// and apply it. Stops when no pair has a rule.
154
155const NX_BPE_MERGE_BUDGET_FACTOR: nx_int = 4 // max merges per input byte
156
157func nx_bpe_encode(v: *NxBpeVocab, text: *u8, n: nx_int, out_tokens: *i64) -> nx_int {
158 // Boundary null guards: this is a public-API primitive callable from
159 // any actor / orchestrator / runner. Returning -NX_BPE_ERR_BAD_VOCAB
160 // lets callers handle clean substrate-level rejection per the
161 // four-pillar discipline instead of SEGV deep inside the encode loop.
162 if (v as i64) == 0 { return 0 - NX_BPE_ERR_BAD_VOCAB }
163 if (text as i64) == 0 { return 0 - NX_BPE_ERR_OOB }
164 if (out_tokens as i64) == 0 { return 0 - NX_BPE_ERR_OOB }
165 if n < 0 { return 0 - NX_BPE_ERR_OOB }
166 if n == 0 { return 0 }
167
168 // Step 1: initial single-byte tokens.
169 let tokens: *i64 = sys_mmap(n * 8) as *i64
170 let byte_buf: *u8 = sys_mmap(1)
171 var i: nx_int = 0
172 while i < n {
173 byte_buf[0] = text[i]
174 let id: i64 = nx_intern_get(v.intern, byte_buf, 1)
175 tokens[i] = id
176 i = i + 1
177 }
178 var n_tokens: nx_int = n
179
180 // Step 2: iteratively apply lowest-rank merges.
181 let merge_budget: nx_int = n * NX_BPE_MERGE_BUDGET_FACTOR
182 var merge_iter: nx_int = 0
183 var merge_verdict: nx_int = NX_LOOP_RUNNING
184 while merge_verdict == NX_LOOP_RUNNING && merge_iter < merge_budget {
185 // Scan for lowest-rank pair.
186 var best_rank: nx_int = -1
187 var best_pos: nx_int = -1
188 var p: nx_int = 0
189 var p_iter: nx_int = 0
190 var p_verdict: nx_int = NX_LOOP_RUNNING
191 let P_BUDGET: nx_int = n_tokens - 1
192 while p_verdict == NX_LOOP_RUNNING && p_iter < P_BUDGET {
193 let rank: nx_int = _bpe_find_merge_rank(v, tokens[p], tokens[p + 1])
194 if rank >= 0 {
195 if best_rank < 0 {
196 best_rank = rank; best_pos = p
197 }
198 if rank < best_rank {
199 best_rank = rank; best_pos = p
200 }
201 }
202 p = p + 1
203 p_iter = p_iter + 1
204 }
205 if best_rank < 0 { merge_verdict = NX_LOOP_DONE_EXIT }
206 if merge_verdict == NX_LOOP_RUNNING {
207 // Apply merge at best_pos.
208 let m: *NxBpeMerge = (v.merges as i64 + best_rank * NX_BPE_MERGE_BYTES) as *NxBpeMerge
209 tokens[best_pos] = m.merged
210 // Shift remaining tokens left by one.
211 var s: nx_int = best_pos + 1
212 while s < n_tokens - 1 {
213 tokens[s] = tokens[s + 1]
214 s = s + 1
215 }
216 n_tokens = n_tokens - 1
217 }
218 merge_iter = merge_iter + 1
219 }
220
221 // Step 3: emit.
222 var k: nx_int = 0
223 while k < n_tokens {
224 out_tokens[k] = tokens[k]
225 k = k + 1
226 }
227 return n_tokens
228}
229
230// ===== GPT-2 / Qwen byte-level pre-tokenization ===================
231//
232// GPT-2/Qwen (Radford 2019) map each raw byte to a VISIBLE unicode
233// char before BPE: printable bytes stay, the rest -> U+0100+idx. Space
234// 0x20 -> U+0120 ("G-dot", UTF-8 C4 A0), so " word" tokens are stored
235// space-prefixed in the vocab. Encoding RAW bytes (nx_bpe_encode)
236// interns the space at vocab_size (out of range) and every multi-word
237// prompt breaks. This variant applies the map so spaces resolve to the
238// real base token. Steps 2-3 (merges, emit) mirror nx_bpe_encode.
239
240func _bpe_byte_to_utf8(b: i64, out: *u8) -> nx_int {
241 var cp: i64 = b
242 if b <= 0x20 {
243 cp = 0x100 + b
244 } else {
245 if b >= 0x7F {
246 if b <= 0xA0 {
247 cp = 0x100 + 33 + (b - 0x7F)
248 } else {
249 if b == 0xAD { cp = 0x143 }
250 }
251 }
252 }
253 if cp < 0x80 {
254 out[0] = cp as u8
255 return 1
256 }
257 out[0] = (0xC0 + (cp / 64)) as u8
258 out[1] = (0x80 + (cp - (cp / 64) * 64)) as u8
259 return 2
260}
261
262func nx_bpe_encode_bytelevel(v: *NxBpeVocab, text: *u8, n: nx_int, out_tokens: *i64) -> nx_int {
263 if (v as i64) == 0 { return 0 - NX_BPE_ERR_BAD_VOCAB }
264 if (text as i64) == 0 { return 0 - NX_BPE_ERR_OOB }
265 if (out_tokens as i64) == 0 { return 0 - NX_BPE_ERR_OOB }
266 if n < 0 { return 0 - NX_BPE_ERR_OOB }
267 if n == 0 { return 0 }
268
269 // Step 1: map each byte through GPT-2 byte-to-unicode, intern the mapped char.
270 let tokens: *i64 = sys_mmap(n * 8) as *i64
271 let cbuf: *u8 = sys_mmap(4)
272 var i: nx_int = 0
273 while i < n {
274 let nb: nx_int = _bpe_byte_to_utf8(text[i] as i64, cbuf)
275 let id: i64 = nx_intern_get(v.intern, cbuf, nb as i64)
276 tokens[i] = id
277 i = i + 1
278 }
279 var n_tokens: nx_int = n
280
281 // Step 2: iteratively apply lowest-rank merges (identical to nx_bpe_encode).
282 let merge_budget: nx_int = n * NX_BPE_MERGE_BUDGET_FACTOR
283 var merge_iter: nx_int = 0
284 var merge_verdict: nx_int = NX_LOOP_RUNNING
285 while merge_verdict == NX_LOOP_RUNNING && merge_iter < merge_budget {
286 var best_rank: nx_int = -1
287 var best_pos: nx_int = -1
288 var p: nx_int = 0
289 var p_iter: nx_int = 0
290 var p_verdict: nx_int = NX_LOOP_RUNNING
291 let P_BUDGET: nx_int = n_tokens - 1
292 while p_verdict == NX_LOOP_RUNNING && p_iter < P_BUDGET {
293 let rank: nx_int = _bpe_find_merge_rank(v, tokens[p], tokens[p + 1])
294 if rank >= 0 {
295 if best_rank < 0 { best_rank = rank; best_pos = p }
296 if rank < best_rank { best_rank = rank; best_pos = p }
297 }
298 p = p + 1
299 p_iter = p_iter + 1
300 }
301 if best_rank < 0 { merge_verdict = NX_LOOP_DONE_EXIT }
302 if merge_verdict == NX_LOOP_RUNNING {
303 let m: *NxBpeMerge = (v.merges as i64 + best_rank * NX_BPE_MERGE_BYTES) as *NxBpeMerge
304 tokens[best_pos] = m.merged
305 var s: nx_int = best_pos + 1
306 while s < n_tokens - 1 {
307 tokens[s] = tokens[s + 1]
308 s = s + 1
309 }
310 n_tokens = n_tokens - 1
311 }
312 merge_iter = merge_iter + 1
313 }
314
315 // Step 3: emit.
316 var k2: nx_int = 0
317 while k2 < n_tokens {
318 out_tokens[k2] = tokens[k2]
319 k2 = k2 + 1
320 }
321 return n_tokens
322}
323
324// Reverse of _bpe_byte_to_utf8: a byte-level unicode codepoint -> raw byte.
325func _bpe_unmap_cp(cp: i64) -> i64 {
326 if cp < 0x100 { return cp } // printable (0x21-0x7E or 0xA1-0xFF) = itself
327 if cp <= 0x120 { return cp - 0x100 } // U+0100..U+0120 -> 0x00..0x20
328 if cp <= 0x142 { return 0x7F + (cp - 0x121) } // U+0121..U+0142 -> 0x7F..0xA0
329 return 0xAD // U+0143 -> 0xAD
330}
331
332// Byte-level decode: tokens -> byte-level UTF-8 bytes (nx_bpe_decode) -> UNMAP back to the
333// original raw bytes. Without this, decoded text shows "G-dot" for spaces and 3-char blobs for
334// every non-ASCII byte. Mirrors nx_bpe_encode_bytelevel on the way out.
335func nx_bpe_decode_bytelevel(v: *NxBpeVocab, tokens: *i64, n: nx_int, out_text: *u8) -> nx_int {
336 let tmp: *u8 = sys_mmap(n * 64 + 64)
337 let nb: nx_int = nx_bpe_decode(v, tokens, n, tmp)
338 if nb < 0 { return nb }
339 var i: nx_int = 0
340 var o: nx_int = 0
341 while i < nb {
342 let b0: i64 = tmp[i] as i64
343 var cp: i64 = b0
344 if b0 < 0x80 {
345 i = i + 1
346 } else {
347 cp = (b0 - 0xC0) * 64 + ((tmp[i + 1] as i64) - 0x80)
348 i = i + 2
349 }
350 out_text[o] = _bpe_unmap_cp(cp) as u8
351 o = o + 1
352 }
353 return o
354}
355
356// ===== Decode: token IDs -> text bytes ============================
357//
358// Caller pre-allocates out_text with enough room (worst case =
359// sum of token byte lengths). Returns bytes-written or negative
360// error.
361
362func nx_bpe_decode(v: *NxBpeVocab, tokens: *i64, n: nx_int, out_text: *u8) -> nx_int {
363 // Same boundary discipline as nx_bpe_encode -- public API hardens
364 // against null inputs so callers can't accidentally SEGV the encoder.
365 if (v as i64) == 0 { return 0 - NX_BPE_ERR_BAD_VOCAB }
366 if (tokens as i64) == 0 { return 0 - NX_BPE_ERR_OOB }
367 if (out_text as i64) == 0 { return 0 - NX_BPE_ERR_OOB }
368 if n < 0 { return 0 - NX_BPE_ERR_OOB }
369 if n == 0 { return 0 }
370 var pos: nx_int = 0
371 var t: nx_int = 0
372 var iter: nx_int = 0
373 var verdict: nx_int = NX_LOOP_RUNNING
374 let BUDGET: nx_int = n
375 let len_p: *i64 = sys_mmap(8) as *i64
376 while verdict == NX_LOOP_RUNNING && iter < BUDGET {
377 let id: i64 = tokens[t]
378 len_p[0] = 0
379 let bytes: *u8 = nx_intern_at(v.intern, id, len_p)
380 if (bytes as i64) == 0 { verdict = NX_LOOP_ABORTED }
381 if verdict == NX_LOOP_RUNNING {
382 var k: nx_int = 0
383 while k < len_p[0] {
384 out_text[pos + k] = bytes[k]
385 k = k + 1
386 }
387 pos = pos + len_p[0]
388 }
389 t = t + 1
390 iter = iter + 1
391 }
392 if verdict == NX_LOOP_ABORTED { return 0 - NX_BPE_ERR_BAD_TOKEN }
393 return pos
394}
395
396// ===== Self-test ==================================================
397//
398// Hand-craft a tiny BPE vocab + merge rules and round-trip:
399//
400// Tokens (intern IDs assigned in order):
401// "a" -> 0
402// "b" -> 1
403// "c" -> 2
404// "d" -> 3
405// "ab" -> 4
406// "cd" -> 5
407// "abcd" -> 6
408//
409// Merges (in rank order, lower = higher priority):
410// rank 0: (4=ab, 5=cd) -> 6=abcd -- applied LAST (must wait for ab + cd to form)
411// rank 1: (0=a, 1=b) -> 4=ab -- applied first
412// rank 2: (2=c, 3=d) -> 5=cd -- applied second
413//
414// Encoding "abcd":
415// initial tokens: [0, 1, 2, 3]
416// step 1: pairs (0,1) rank=1, (1,2) no rule, (2,3) rank=2 -> apply rank 1
417// tokens: [4, 2, 3]
418// step 2: pairs (4,2) no rule, (2,3) rank=2 -> apply rank 2
419// tokens: [4, 5]
420// step 3: pairs (4,5) rank=0 -> apply rank 0
421// tokens: [6]
422// final: 1 token = abcd
423//
424// Decode [6] -> "abcd"
425
426func main() -> i64 {
427 let v: *NxBpeVocab = nx_bpe_vocab_new(256, 16, 8)
428
429 // Register the 7 atomic tokens.
430 let a: *u8 = sys_mmap(1); a[0] = 0x61 // 'a'
431 let b: *u8 = sys_mmap(1); b[0] = 0x62
432 let c: *u8 = sys_mmap(1); c[0] = 0x63
433 let d: *u8 = sys_mmap(1); d[0] = 0x64
434 let ab: *u8 = sys_mmap(2); ab[0]=0x61; ab[1]=0x62
435 let cd: *u8 = sys_mmap(2); cd[0]=0x63; cd[1]=0x64
436 let abcd: *u8 = sys_mmap(4)
437 abcd[0]=0x61; abcd[1]=0x62; abcd[2]=0x63; abcd[3]=0x64
438
439 let id_a: i64 = nx_bpe_add_token(v, a, 1)
440 let id_b: i64 = nx_bpe_add_token(v, b, 1)
441 let id_c: i64 = nx_bpe_add_token(v, c, 1)
442 let id_d: i64 = nx_bpe_add_token(v, d, 1)
443 let id_ab: i64 = nx_bpe_add_token(v, ab, 2)
444 let id_cd: i64 = nx_bpe_add_token(v, cd, 2)
445 let id_abcd: i64 = nx_bpe_add_token(v, abcd, 4)
446
447 // Register merges in priority order (rank 0 = highest).
448 nx_bpe_add_merge(v, id_ab, id_cd, id_abcd) // rank 0
449 nx_bpe_add_merge(v, id_a, id_b, id_ab) // rank 1
450 nx_bpe_add_merge(v, id_c, id_d, id_cd) // rank 2
451
452 // Encode "abcd".
453 let text: *u8 = sys_mmap(4)
454 text[0]=0x61; text[1]=0x62; text[2]=0x63; text[3]=0x64
455 let out_tokens: *i64 = sys_mmap(16 * 8) as *i64
456 let n_emitted: nx_int = nx_bpe_encode(v, text, 4, out_tokens)
457 if n_emitted != 1 { return 10 }
458 if out_tokens[0] != id_abcd { return 11 }
459
460 // Decode [id_abcd] -> "abcd".
461 let out_text: *u8 = sys_mmap(16)
462 let n_text: nx_int = nx_bpe_decode(v, out_tokens, 1, out_text)
463 if n_text != 4 { return 20 }
464 if out_text[0] != 0x61 { return 21 }
465 if out_text[1] != 0x62 { return 22 }
466 if out_text[2] != 0x63 { return 23 }
467 if out_text[3] != 0x64 { return 24 }
468
469 // Encode a different input that hits partial merges: "abc"
470 // Initial tokens: [a, b, c]. pairs (a,b) rank=1, (b,c) no rule.
471 // Apply (a,b) -> [ab, c]. pairs (ab, c) no rule. done.
472 // Result: 2 tokens [ab, c].
473 let text2: *u8 = sys_mmap(3)
474 text2[0]=0x61; text2[1]=0x62; text2[2]=0x63
475 let n2: nx_int = nx_bpe_encode(v, text2, 3, out_tokens)
476 if n2 != 2 { return 30 }
477 if out_tokens[0] != id_ab { return 31 }
478 if out_tokens[1] != id_c { return 32 }
479
480 // Decode [ab, c] -> "abc".
481 let n_dec2: nx_int = nx_bpe_decode(v, out_tokens, 2, out_text)
482 if n_dec2 != 3 { return 40 }
483 if out_text[0] != 0x61 { return 41 }
484 if out_text[1] != 0x62 { return 42 }
485 if out_text[2] != 0x63 { return 43 }
486
487 // --- Verdict gate ---
488 var vi: nx_int = 0
489 while vi < NX_BPE_N_VERDICTS {
490 if nx_bpe_verdict_is_valid(vi) != 1 { return 50 + vi }
491 vi = vi + 1
492 }
493
494 return 0
495}