nx_token_permutation.nx source
↩ module page · 274 lines · 9893 B
1// nx_token_permutation.nx -- order-effect analyzer for prompt token sequences.
2//
3// Foundation primitive for reasoning about PROMPT ORDER EFFECTS in
4// image-gen models. Given two ordered token-id sequences that share
5// the same multi-set (i.e., a permutation of each other), measure:
6//
7// 1. Kendall tau distance # of pairwise inversions; the
8// canonical permutation-distance metric
9// 2. Position-0 changed did the first token swap? (CLIP and
10// T5 both weight position-0 heavily)
11// 3. Position-last changed did the trailing token swap?
12// (some text encoders weight the EOS-
13// adjacent position differently)
14// 4. New-neighbor pairs pairs of tokens now adjacent that
15// weren't before (attention is denser
16// between adjacent tokens; new pairs
17// means new latent joint-meaning)
18// 5. Same-multi-set check did the two sequences share tokens?
19// (if not, this analysis doesn't apply
20// and the verdict is NOT_PERMUTATION)
21//
22// Output also carries a SEALED-ENUM verdict per the dual-reading
23// cardinal:
24//
25// NX_PERMUT_IDENTICAL identical sequences
26// NX_PERMUT_ADJACENT_SWAP single adjacent transposition
27// NX_PERMUT_MINOR_REORDER tau >= 0.85
28// NX_PERMUT_MODERATE_REORDER tau in [0.5, 0.85)
29// NX_PERMUT_SEVERE_REORDER tau < 0.5
30// NX_PERMUT_NOT_PERMUTATION different multi-sets
31//
32// USE CASES:
33// - "beautiful tall girl" vs "tall beautiful girl" -> ADJACENT_SWAP
34// position-0 changed -> for CLIP-based models, predict ~35% attention
35// shift; for T5-based models (Z-Image), predict ~15% shift.
36// - "beautiful tall girl" vs "girl tall beautiful" -> SEVERE_REORDER
37// tau ~ 0; position-0 + position-last both changed; new neighbor
38// pairs (girl-tall, tall-beautiful where before was beautiful-tall).
39// - "tall girl" vs "tall beautiful girl" -> NOT_PERMUTATION (different
40// multi-sets; "added a word" case the user asked about).
41//
42// For the "added a word" case the verdict NOT_PERMUTATION is the
43// signal that a different analysis layer applies (per-token L1
44// semantics + position-mass model -- both queued).
45//
46// All math i64 / Q10; deterministic. Token-ids are caller-provided
47// i64 arrays (caller's tokenizer is responsible for producing them --
48// future nx_tokenizer.nx will close that gap; today the substrate is
49// vocabulary-agnostic).
50//
51// genealogy_id: kendall_1938_tau + spearman_1904_rho +
52// radford_etal_2021_clip + raffel_etal_2020_t5
53// lineage_id: token_permutation_kendall_q10
54
55// nx_safety_envelope:
56// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
57// sil_target: SIL1
58// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
59// verdict: NOT_YET_EVALUATED
60
61import "nx_syscalls.nx"
62import "nx_tier.nx"
63
64const NX_PERMUT_Q: nx_int = 1024
65
66// Sealed-enum verdicts
67const NX_PERMUT_IDENTICAL: nx_int = 0
68const NX_PERMUT_ADJACENT_SWAP: nx_int = 1
69const NX_PERMUT_MINOR_REORDER: nx_int = 2
70const NX_PERMUT_MODERATE_REORDER: nx_int = 3
71const NX_PERMUT_SEVERE_REORDER: nx_int = 4
72const NX_PERMUT_NOT_PERMUTATION: nx_int = 5
73const NX_PERMUT_N_VERDICTS: nx_int = 6
74
75struct PermutationReport {
76 n_tokens: nx_int,
77 same_multi_set: nx_int, // 1 = yes, 0 = no
78 n_inversions: nx_int, // raw inversion count
79 kendall_tau_q10: nx_int, // 1 - 2 * inv / max_inv; Q10
80 position_0_changed: nx_int, // 1 = yes
81 position_last_changed: nx_int, // 1 = yes
82 n_new_neighbors: nx_int, // pairs adjacent in s2 but not s1
83 verdict: nx_int, // NX_PERMUT_*
84}
85
86// ===== Multi-set equality check ===================================
87//
88// Two arrays have the same multi-set iff each value appears the same
89// number of times in both. O(n^2) check; fine for small prompt
90// token sequences (typical prompt < 50 tokens).
91
92func _permut_same_multi_set(a: *i64, n_a: nx_int, b: *i64, n_b: nx_int) -> nx_int {
93 if n_a != n_b { return 0 }
94 // For each unique value in a, count it in both arrays.
95 var i: nx_int = 0
96 while i < n_a {
97 let tok: nx_int = a[i]
98 // Skip already-checked tokens (avoid duplicate work).
99 var already: nx_int = 0
100 var k: nx_int = 0
101 while k < i {
102 if a[k] == tok {
103 already = 1
104 break
105 }
106 k = k + 1
107 }
108 if already == 0 {
109 var ca: nx_int = 0
110 var cb: nx_int = 0
111 var j: nx_int = 0
112 while j < n_a {
113 if a[j] == tok { ca = ca + 1 }
114 if b[j] == tok { cb = cb + 1 }
115 j = j + 1
116 }
117 if ca != cb { return 0 }
118 }
119 i = i + 1
120 }
121 return 1
122}
123
124// Map each position in b back to its index in a (taking the FIRST
125// unused match -- handles multi-set duplicates correctly).
126// Returns 1 on success. Caller passes pos_buf of size n.
127func _permut_build_position_map(a: *i64, b: *i64, n: nx_int, pos_buf: *i64) -> nx_int {
128 let used: *u8 = sys_mmap(n)
129 var i: nx_int = 0
130 while i < n {
131 var found: nx_int = 0 - 1
132 var j: nx_int = 0
133 while j < n {
134 if used[j] == 0 {
135 if a[j] == b[i] {
136 found = j
137 used[j] = 1
138 break
139 }
140 }
141 j = j + 1
142 }
143 if found < 0 { return 0 }
144 pos_buf[i] = found
145 i = i + 1
146 }
147 return 1
148}
149
150// Count inversions in pos_buf via simple O(n^2) pass.
151// (Merge-sort variant is O(n log n) but for typical prompt < 50
152// tokens the O(n^2) cost is negligible.)
153func _permut_count_inversions(pos_buf: *i64, n: nx_int) -> nx_int {
154 var inv: nx_int = 0
155 var i: nx_int = 0
156 while i < n {
157 var j: nx_int = i + 1
158 while j < n {
159 if pos_buf[i] > pos_buf[j] { inv = inv + 1 }
160 j = j + 1
161 }
162 i = i + 1
163 }
164 return inv
165}
166
167// Count adjacent-token pairs in b that are not adjacent in a.
168// Adjacent in a means there exist k1, k2 in a with k2 = k1 + 1
169// where a[k1] = b[i] and a[k2] = b[i+1].
170func _permut_count_new_neighbors(a: *i64, b: *i64, n: nx_int) -> nx_int {
171 if n <= 1 { return 0 }
172 var new_pairs: nx_int = 0
173 var i: nx_int = 0
174 while i < n - 1 {
175 let l: nx_int = b[i]
176 let r: nx_int = b[i + 1]
177 var found_in_a: nx_int = 0
178 var k: nx_int = 0
179 while k < n - 1 {
180 if a[k] == l {
181 if a[k + 1] == r {
182 found_in_a = 1
183 break
184 }
185 }
186 k = k + 1
187 }
188 if found_in_a == 0 { new_pairs = new_pairs + 1 }
189 i = i + 1
190 }
191 return new_pairs
192}
193
194// ===== Public compute =============================================
195
196func nx_token_permutation_compute(
197 a: *i64, n_a: nx_int,
198 b: *i64, n_b: nx_int,
199 report: *PermutationReport
200) -> nx_int {
201 report.n_tokens = n_a
202 report.same_multi_set = 0
203 report.n_inversions = 0
204 report.kendall_tau_q10 = 0
205 report.position_0_changed = 0
206 report.position_last_changed = 0
207 report.n_new_neighbors = 0
208 report.verdict = NX_PERMUT_NOT_PERMUTATION
209
210 if _permut_same_multi_set(a, n_a, b, n_b) == 0 {
211 return 0 // verdict already NOT_PERMUTATION
212 }
213 report.same_multi_set = 1
214 report.n_tokens = n_a
215 if n_a == 0 {
216 report.verdict = NX_PERMUT_IDENTICAL
217 report.kendall_tau_q10 = NX_PERMUT_Q
218 return 0
219 }
220
221 // Build position map: pos_buf[i] = index in a of the i-th token in b.
222 let pos_buf: *i64 = (sys_mmap(n_a * NX_SIZEOF_NX_INT)) as *i64
223 let ok: nx_int = _permut_build_position_map(a, b, n_a, pos_buf)
224 if ok == 0 {
225 report.verdict = NX_PERMUT_NOT_PERMUTATION
226 return 0
227 }
228
229 // Inversions + Kendall tau.
230 let inv: nx_int = _permut_count_inversions(pos_buf, n_a)
231 report.n_inversions = inv
232 let max_inv: nx_int = (n_a * (n_a - 1)) / 2
233 if max_inv == 0 {
234 report.kendall_tau_q10 = NX_PERMUT_Q
235 } else {
236 // tau = 1 - 2 * inv / max_inv
237 // Q10: tau_q10 = Q - (2 * inv * Q) / max_inv
238 let drop: nx_int = (2 * inv * NX_PERMUT_Q) / max_inv
239 var tau: nx_int = NX_PERMUT_Q - drop
240 if tau < (0 - NX_PERMUT_Q) { tau = 0 - NX_PERMUT_Q }
241 if tau > NX_PERMUT_Q { tau = NX_PERMUT_Q }
242 report.kendall_tau_q10 = tau
243 }
244
245 // Position-0 + position-last sentinels.
246 if a[0] != b[0] { report.position_0_changed = 1 }
247 if a[n_a - 1] != b[n_a - 1] { report.position_last_changed = 1 }
248
249 // New-neighbor pairs.
250 report.n_new_neighbors = _permut_count_new_neighbors(a, b, n_a)
251
252 // Sealed-enum verdict routing.
253 if inv == 0 {
254 report.verdict = NX_PERMUT_IDENTICAL
255 } else {
256 if inv == 1 {
257 report.verdict = NX_PERMUT_ADJACENT_SWAP
258 } else {
259 // Use tau bands.
260 if report.kendall_tau_q10 >= 870 { report.verdict = NX_PERMUT_MINOR_REORDER }
261 if report.kendall_tau_q10 < 870 { report.verdict = NX_PERMUT_MODERATE_REORDER }
262 if report.kendall_tau_q10 < 512 { report.verdict = NX_PERMUT_SEVERE_REORDER }
263 }
264 }
265
266 return 0
267}
268
269// Sealed-enum validity check.
270func nx_token_permutation_verdict_is_valid(v: nx_int) -> nx_int {
271 if v < 0 { return 0 }
272 if v >= NX_PERMUT_N_VERDICTS { return 0 }
273 return 1
274}