exatok 0.1.1

Exact GPU-resident BPE tokenizer whose token ids match tiktoken byte for byte
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379
2380
2381
2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
2571
2572
2573
2574
2575
2576
2577
2578
2579
2580
2581
2582
2583
2584
2585
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610
2611
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
2636
2637
2638
2639
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
2662
2663
2664
2665
2666
2667
2668
2669
2670
2671
2672
2673
2674
2675
2676
2677
2678
2679
2680
2681
2682
2683
2684
2685
2686
2687
2688
2689
2690
2691
2692
2693
2694
2695
2696
2697
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
2748
2749
2750
2751
2752
2753
2754
2755
2756
2757
2758
2759
2760
2761
2762
2763
2764
2765
2766
2767
2768
2769
2770
2771
2772
2773
2774
2775
2776
2777
2778
2779
2780
2781
2782
2783
2784
2785
2786
2787
2788
2789
2790
2791
2792
2793
2794
2795
2796
2797
2798
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
2900
2901
2902
2903
2904
2905
2906
2907
2908
2909
2910
2911
2912
2913
2914
2915
2916
2917
2918
2919
2920
2921
2922
2923
2924
2925
2926
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937
2938
2939
2940
2941
2942
2943
2944
2945
2946
2947
2948
2949
2950
2951
2952
2953
2954
2955
2956
2957
2958
2959
2960
2961
2962
2963
2964
2965
2966
2967
2968
2969
2970
2971
2972
2973
2974
2975
2976
2977
2978
2979
2980
2981
2982
2983
2984
2985
2986
2987
2988
2989
2990
2991
2992
2993
2994
2995
2996
2997
2998
2999
3000
3001
3002
3003
3004
3005
3006
3007
3008
3009
3010
3011
3012
3013
3014
3015
3016
3017
3018
3019
3020
3021
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
3034
3035
3036
3037
3038
3039
3040
3041
3042
3043
3044
3045
3046
3047
3048
3049
3050
3051
3052
3053
3054
3055
3056
3057
3058
3059
3060
3061
3062
3063
3064
3065
3066
3067
3068
3069
3070
3071
3072
3073
3074
3075
3076
3077
3078
3079
3080
3081
3082
3083
3084
3085
3086
3087
3088
3089
3090
3091
3092
3093
3094
3095
3096
3097
3098
3099
3100
3101
3102
3103
3104
3105
3106
3107
3108
3109
3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
3120
3121
3122
3123
3124
3125
3126
3127
3128
3129
3130
3131
3132
3133
3134
3135
3136
3137
3138
3139
3140
3141
3142
3143
3144
3145
3146
3147
3148
3149
3150
3151
3152
3153
3154
3155
3156
3157
3158
3159
3160
3161
3162
3163
3164
3165
3166
3167
3168
3169
3170
3171
3172
3173
3174
3175
3176
3177
3178
3179
3180
3181
3182
3183
3184
3185
3186
3187
3188
3189
3190
3191
3192
3193
3194
3195
3196
3197
3198
3199
3200
3201
3202
3203
3204
3205
3206
3207
3208
3209
3210
3211
3212
3213
3214
3215
3216
3217
3218
3219
3220
3221
3222
3223
3224
3225
3226
3227
3228
3229
3230
3231
3232
3233
3234
3235
3236
3237
3238
3239
3240
3241
3242
3243
3244
3245
3246
3247
3248
3249
3250
3251
3252
3253
3254
3255
3256
3257
3258
3259
3260
3261
3262
3263
3264
3265
3266
3267
3268
3269
3270
3271
3272
3273
3274
3275
3276
3277
3278
3279
3280
3281
3282
3283
3284
3285
3286
3287
3288
3289
3290
3291
3292
3293
3294
3295
3296
3297
3298
3299
3300
3301
3302
3303
3304
3305
3306
3307
3308
3309
3310
3311
3312
3313
3314
3315
3316
3317
3318
3319
3320
3321
3322
3323
3324
3325
3326
3327
3328
3329
3330
3331
3332
3333
3334
3335
3336
3337
3338
3339
3340
3341
3342
3343
3344
3345
3346
3347
3348
3349
3350
3351
3352
3353
3354
3355
3356
3357
3358
3359
3360
3361
3362
3363
3364
3365
3366
3367
3368
3369
3370
3371
3372
3373
3374
3375
3376
3377
3378
3379
3380
3381
3382
3383
3384
3385
3386
3387
3388
3389
3390
3391
3392
3393
3394
3395
3396
3397
3398
3399
3400
3401
3402
3403
3404
3405
3406
3407
3408
3409
3410
3411
3412
3413
3414
3415
3416
3417
3418
3419
3420
3421
3422
3423
3424
3425
3426
3427
3428
3429
3430
3431
3432
3433
3434
3435
3436
3437
3438
3439
3440
3441
3442
3443
3444
3445
3446
3447
3448
3449
3450
3451
3452
3453
3454
3455
3456
3457
3458
3459
3460
3461
3462
3463
3464
3465
3466
3467
3468
3469
3470
3471
3472
3473
3474
3475
3476
3477
3478
3479
3480
3481
3482
3483
3484
3485
3486
3487
3488
3489
3490
3491
3492
3493
3494
3495
3496
3497
3498
3499
3500
3501
3502
3503
3504
3505
3506
3507
3508
3509
3510
3511
3512
3513
3514
3515
3516
3517
3518
3519
3520
3521
3522
3523
3524
3525
3526
3527
3528
3529
3530
3531
3532
3533
3534
3535
3536
3537
3538
3539
3540
3541
3542
3543
3544
3545
3546
3547
3548
3549
3550
3551
3552
3553
3554
3555
3556
3557
3558
3559
3560
3561
3562
3563
3564
3565
3566
3567
3568
3569
3570
3571
3572
3573
3574
3575
3576
3577
3578
3579
3580
3581
3582
3583
3584
3585
3586
3587
3588
3589
3590
3591
3592
3593
3594
3595
3596
3597
3598
3599
3600
3601
3602
3603
3604
3605
3606
3607
3608
3609
3610
3611
3612
3613
3614
3615
3616
3617
3618
3619
3620
3621
3622
3623
3624
3625
3626
3627
3628
3629
3630
3631
3632
3633
3634
3635
3636
3637
3638
3639
3640
3641
3642
3643
3644
3645
3646
3647
3648
3649
3650
3651
3652
3653
3654
3655
3656
3657
3658
3659
3660
3661
3662
3663
3664
3665
3666
3667
3668
3669
3670
3671
3672
3673
3674
3675
3676
3677
3678
3679
3680
3681
3682
3683
3684
3685
3686
3687
3688
3689
3690
3691
3692
3693
3694
3695
3696
3697
3698
3699
3700
3701
3702
3703
3704
3705
3706
3707
3708
3709
3710
3711
3712
3713
3714
3715
3716
3717
3718
3719
3720
3721
3722
3723
3724
3725
3726
3727
3728
3729
3730
3731
3732
3733
3734
3735
3736
3737
3738
3739
3740
3741
3742
3743
3744
3745
3746
3747
3748
3749
3750
3751
3752
3753
3754
3755
3756
3757
3758
3759
3760
3761
3762
3763
3764
3765
3766
3767
3768
3769
3770
3771
3772
3773
3774
3775
3776
3777
3778
3779
3780
3781
3782
3783
3784
3785
3786
3787
3788
3789
3790
3791
3792
3793
3794
3795
3796
3797
3798
3799
3800
3801
3802
3803
3804
3805
3806
3807
3808
3809
3810
3811
3812
3813
3814
3815
3816
3817
3818
3819
3820
3821
3822
3823
3824
3825
3826
3827
3828
3829
3830
3831
3832
3833
3834
3835
3836
3837
3838
3839
3840
3841
3842
3843
3844
3845
3846
3847
3848
3849
3850
3851
3852
3853
3854
3855
3856
3857
3858
3859
3860
3861
3862
3863
3864
3865
3866
3867
3868
3869
3870
3871
3872
3873
3874
3875
3876
3877
3878
3879
3880
3881
3882
3883
3884
3885
3886
3887
3888
3889
3890
3891
3892
3893
3894
3895
3896
3897
3898
3899
3900
3901
3902
3903
3904
3905
3906
3907
3908
3909
3910
3911
3912
3913
3914
3915
3916
3917
3918
3919
3920
3921
3922
3923
3924
3925
3926
3927
3928
3929
3930
3931
3932
3933
3934
3935
3936
3937
3938
3939
3940
3941
3942
3943
3944
3945
3946
3947
3948
3949
3950
3951
3952
3953
3954
3955
3956
3957
3958
3959
3960
3961
3962
3963
3964
3965
3966
3967
3968
3969
3970
3971
3972
3973
3974
3975
3976
3977
3978
3979
3980
3981
3982
3983
3984
3985
3986
3987
3988
3989
3990
3991
3992
3993
3994
3995
3996
3997
3998
3999
4000
4001
4002
4003
4004
4005
4006
4007
4008
4009
4010
4011
4012
4013
4014
4015
4016
4017
4018
4019
4020
4021
4022
4023
4024
4025
4026
4027
4028
4029
4030
4031
4032
4033
4034
4035
4036
4037
4038
4039
4040
4041
4042
4043
4044
4045
4046
4047
4048
4049
4050
4051
4052
4053
4054
4055
4056
4057
4058
4059
4060
4061
4062
4063
4064
4065
4066
4067
4068
4069
4070
4071
4072
4073
4074
4075
4076
4077
4078
4079
4080
4081
4082
4083
4084
4085
4086
4087
4088
4089
4090
4091
4092
4093
4094
4095
4096
4097
4098
4099
4100
4101
4102
4103
4104
4105
4106
4107
4108
4109
4110
4111
4112
4113
4114
4115
4116
4117
4118
4119
4120
4121
4122
4123
4124
4125
4126
4127
4128
4129
4130
4131
4132
4133
4134
4135
4136
4137
4138
4139
4140
4141
4142
4143
4144
4145
4146
4147
4148
4149
4150
4151
4152
4153
4154
4155
4156
4157
4158
4159
4160
4161
4162
4163
4164
4165
4166
4167
4168
4169
4170
4171
4172
4173
4174
4175
4176
4177
4178
4179
4180
4181
4182
4183
4184
4185
4186
4187
4188
4189
4190
4191
4192
4193
4194
4195
4196
4197
4198
4199
4200
4201
4202
4203
4204
4205
4206
4207
4208
4209
4210
4211
4212
4213
4214
4215
4216
4217
4218
4219
4220
4221
4222
4223
4224
4225
4226
4227
4228
4229
4230
4231
4232
4233
4234
4235
4236
4237
4238
4239
4240
4241
4242
4243
4244
4245
4246
4247
4248
4249
4250
4251
4252
4253
4254
4255
4256
4257
4258
4259
4260
4261
4262
4263
4264
4265
4266
4267
4268
4269
4270
4271
4272
4273
4274
4275
4276
4277
4278
4279
4280
4281
4282
4283
4284
4285
4286
4287
4288
4289
4290
4291
4292
4293
4294
4295
4296
4297
4298
4299
4300
4301
4302
4303
4304
4305
4306
4307
4308
4309
4310
4311
4312
4313
4314
4315
4316
4317
4318
4319
4320
4321
4322
4323
4324
4325
4326
4327
4328
4329
4330
4331
4332
4333
4334
4335
4336
4337
4338
4339
4340
4341
4342
4343
4344
4345
4346
4347
4348
4349
4350
4351
4352
4353
4354
4355
4356
4357
4358
4359
4360
4361
4362
4363
4364
4365
4366
4367
4368
4369
4370
4371
4372
4373
4374
4375
4376
4377
4378
4379
4380
4381
4382
4383
4384
4385
4386
4387
4388
4389
4390
4391
4392
4393
4394
4395
4396
4397
4398
4399
4400
4401
4402
4403
4404
4405
4406
4407
4408
4409
4410
4411
4412
4413
4414
4415
4416
4417
4418
4419
4420
4421
4422
4423
4424
4425
4426
4427
4428
4429
4430
4431
4432
4433
4434
4435
4436
4437
4438
4439
4440
4441
4442
4443
4444
4445
4446
4447
4448
4449
4450
4451
4452
4453
4454
4455
4456
4457
4458
4459
4460
4461
4462
4463
4464
4465
4466
4467
4468
4469
4470
4471
4472
4473
4474
4475
4476
4477
4478
4479
4480
4481
4482
4483
4484
4485
4486
4487
4488
4489
4490
4491
4492
4493
4494
4495
4496
4497
4498
4499
4500
4501
4502
4503
4504
4505
4506
4507
4508
4509
4510
4511
4512
4513
4514
4515
4516
4517
4518
4519
4520
4521
4522
4523
4524
4525
4526
4527
4528
4529
4530
4531
4532
4533
4534
4535
4536
4537
4538
4539
4540
4541
4542
4543
4544
4545
4546
4547
4548
4549
4550
4551
4552
4553
4554
4555
4556
4557
4558
4559
4560
4561
4562
4563
4564
4565
4566
4567
4568
4569
4570
4571
4572
4573
4574
4575
4576
4577
4578
4579
4580
4581
4582
4583
4584
4585
4586
4587
4588
4589
4590
4591
4592
4593
4594
4595
4596
4597
4598
4599
4600
4601
4602
4603
4604
4605
4606
4607
4608
4609
4610
4611
4612
4613
4614
4615
4616
4617
4618
4619
4620
4621
4622
4623
4624
4625
4626
4627
4628
4629
4630
4631
4632
4633
4634
4635
4636
4637
4638
4639
4640
4641
4642
4643
4644
4645
4646
4647
4648
4649
4650
4651
4652
4653
4654
4655
4656
4657
4658
4659
4660
4661
4662
4663
4664
4665
4666
4667
4668
4669
4670
4671
4672
4673
4674
4675
4676
4677
4678
4679
4680
4681
4682
4683
4684
4685
4686
4687
4688
4689
4690
4691
4692
4693
4694
4695
4696
4697
4698
4699
4700
4701
4702
4703
4704
4705
4706
4707
4708
4709
4710
4711
4712
4713
4714
4715
4716
4717
4718
4719
4720
4721
4722
4723
4724
4725
4726
4727
4728
4729
4730
4731
4732
4733
4734
4735
4736
4737
4738
4739
4740
4741
4742
4743
4744
4745
4746
4747
4748
4749
4750
4751
4752
4753
4754
4755
4756
4757
4758
4759
4760
4761
4762
4763
4764
4765
4766
4767
4768
4769
4770
4771
4772
4773
4774
4775
4776
4777
4778
4779
4780
4781
4782
4783
4784
4785
4786
4787
4788
4789
4790
4791
4792
4793
4794
4795
4796
4797
4798
4799
4800
4801
4802
4803
4804
4805
4806
4807
4808
4809
4810
4811
4812
4813
4814
4815
4816
4817
4818
4819
4820
4821
4822
4823
4824
4825
4826
4827
4828
4829
4830
4831
//! The public GPU-resident encode path. OWNER: DeviceApi.
//!
//! [`DeviceTokenizer`] is the composed product: [`crate::pretokenize`] decides
//! the boundaries, the byte-level start state seeds each pretoken, an emitted
//! [`crate::gpu_rank_table`] probe supplies ranks and merged ids, the pass body
//! below selects the leftmost minimum-rank pair per segment, and
//! [`crate::gpu_loop`] converges the whole batch in ONE dispatch. Token ids are
//! identical to [`crate::reference::encode_pretoken`] byte for byte.
//!
//! Every piece of this path was verified end to end against real `cl100k_base`
//! and `o200k_base` artifacts, on the reference interpreter and on a real CUDA
//! device, while it lived in `tests/device_parity.rs` as private test helpers.
//! This module is that path promoted into the library unchanged in behavior.
//! The doc comments on the composition below are the record of what the
//! verification cost, so they are preserved rather than summarized: each one
//! names a defect that was live at some point and the mechanism that hid it.
//!
//! # What changed on promotion
//!
//! Two behavioral changes, both forced by the difference between a test harness
//! and an API:
//!
//! * Everything a caller's input can provoke is a returned [`ExatokError`]
//!   naming the offending value with an actionable `Fix:` clause. In
//!   particular, a pretoken past [`MAX_PRETOKEN_TOKENS`] is a returned error
//!   that states the measured token count and the cap, not a panic.
//! * Genuine internal invariants stay assertions, because no input can reach
//!   them: that pretoken spans tile the input gaplessly, and that every
//!   pretoken lands in exactly one batch.
//!
//! # Before you change the pass body
//!
//! Read `docs/vyre-composition-contracts.md` first. Three of its contracts are
//! load bearing here: a `Node::Region` opens a binding scope, so a probe's
//! consumer must live INSIDE the probe region; a program may declare at most one
//! output buffer, which is why the selection scratch is `ReadWrite` storage
//! rather than an output; and the `*_child` reduction helpers reduce over the
//! WHOLE workgroup, which makes them the wrong tool for a per-segment minimum.
//!
//! The state layout is PADDED, and it belongs to [`crate::gpu_loop`]. Never
//! derive `seg = lane / stride` or `base = seg * stride` here: each workgroup
//! owns exactly [`LOOP_WORKGROUP_WIDTH`] words and holds whole segments only, so
//! both forms attribute a lane to the wrong segment. Bind coordinates with
//! [`segment_coordinates`] and guard every phase with [`lane_is_live`], which
//! are the owning module's statement of its own layout.

use std::collections::BTreeMap;
use std::sync::{Arc, Mutex, OnceLock, PoisonError, RwLock};
use std::sync::atomic::{AtomicU64, AtomicUsize, Ordering};
use std::time::{Duration, Instant};

use vyre::MemoryOrdering;
use vyre::ir::{BufferAccess, BufferDecl, DataType, Expr, Node, Program};
use vyre_driver::{Resource, VyreBackend};
use vyre_primitives::wire::pack_u32_slice;

use crate::gpu_loop::{
    CallerInput, DEAD_SLOT, FIRST_CALLER_BINDING, LOOP_WORKGROUP_WIDTH, LoopBatch, LoopOutcome,
    LoopShape,
    NAME_STATE_CURRENT, NAME_STATE_NEXT, OP_ID as LOOP_OP_ID, cooperative_block_ceiling,
    device_loop_program, lane_is_live, merge_pass_bound, run_device_loop_borrowed,
    segment_coordinates,
};
use crate::gpu_rank_table::{RankTable, SLOT_WORDS, probe_child, probe_id_var, probe_rank_var};
use crate::gpu_select::{
    ARGMIN_INDEX_SLOT, ARGMIN_RANK_SLOT, ARGMIN_WORDS_PER_SEGMENT, NO_MERGE_INDEX,
};
use crate::incremental::MergeState;
use crate::pretokenize::{Span, pretokens};
#[cfg(test)]
use crate::pretokenize::spans;
use crate::reference::{MergeTable, trace_pretoken};
use crate::vocab::Vocabulary;
use crate::{Encoding, PairKey, Rank, TokenId, ExatokError, byte_token_ids};

/// Every merge row the reference encoder can reach from `pretokens`.
///
/// The encoder only ever queries pairs adjacent in some intermediate state, so a
/// table holding exactly those rows answers every query identically to the full
/// table: a present pair keeps its entry, and an absent pair is absent in both.
/// That keeps the uploaded table at a few thousand slots instead of the two
/// million a full `o200k` table needs, per dispatch, without weakening the
/// oracle. A device that diverged would query a pair outside the set and read
/// [`Rank::ABSENT`], which still lands on a wrong final state and still fails.
///
/// [`DeviceTokenizer::new`] deliberately does NOT use this. The subset depends
/// on the INPUT, so a tokenizer built from it would have to rebuild and re-upload
/// its table on every call, which is the cost the single-dispatch design exists
/// to remove. It stays public for the two cases where the tradeoff inverts: a
/// caller encoding one fixed corpus repeatedly, and a parity harness that wants
/// a small uploaded table without weakening its oracle.
#[must_use]
pub fn reachable_rows(
    pretokens: &[Vec<TokenId>],
    table: &impl MergeTable,
) -> Vec<(PairKey, TokenId, Rank)> {
    let mut rows: BTreeMap<u64, (PairKey, TokenId, Rank)> = BTreeMap::new();
    for tokens in pretokens {
        let trace = trace_pretoken(tokens, table);
        let mut states = vec![trace.initial().to_vec()];
        states.extend(trace.steps().iter().map(|step| step.state.clone()));
        for state in &states {
            for window in state.windows(2) {
                let pair = PairKey::new(window[0], window[1]);
                if let Some(entry) = table.lookup(pair) {
                    rows.insert(pair.bits(), (pair, entry.id, entry.rank));
                }
            }
        }
    }
    rows.into_values().collect()
}

// ---------------------------------------------------------------------------
// The composed pass body: rank-table probe plus per-segment leftmost argmin
// ---------------------------------------------------------------------------

/// Uploaded rank-table slots the pass body probes.
const NAME_BPE_SLOTS: &str = "bpe_table_slots";

/// Per-segment selection words, in [`crate::gpu_select`]'s argmin layout:
/// [`ARGMIN_WORDS_PER_SEGMENT`] words per segment, index at
/// [`ARGMIN_INDEX_SLOT`] and rank at [`ARGMIN_RANK_SLOT`].
///
/// Deliberately the SAME encoding `segmented_argmin_leftmost` writes rather than
/// a second one, so the in-body selector and the standalone program agree by
/// construction and a reader comparing them is comparing one layout.
const NAME_BPE_PICK: &str = "bpe_pick";

/// Probe prefix for the rank vote, the index vote, and the merged-id read.
///
/// Three DISTINCT prefixes, not one, because [`probe_child`] declares its result
/// bindings from the prefix and the three probes sit in three separate phases of
/// one pass body. Sharing a prefix would redeclare the same binding names in a
/// scope that already holds them.
///
/// Spelled verbatim as `tests/device_parity.rs` spells them, so the composition
/// this module promoted and the harness that proved it exact emit the same
/// variable names and a reader can diff the two bodies line for line.
///
/// Never hand-spell the derived result names: [`probe_rank_var`] and
/// [`probe_id_var`] own the `{prefix}_rank` and `{prefix}_id` suffixes, and
/// gpu_rank_table's own docs name them as the way a consumer reads a probe.
const PROBE_RANK: &str = "wtp_rank";

/// Probe prefix for the index vote. See [`PROBE_RANK`].
const PROBE_INDEX: &str = "wtp_idx";

/// Probe prefix for the merged-id read. See [`PROBE_RANK`].
const PROBE_MERGED_ID: &str = "wtp_id";

/// Initial [`NAME_BPE_PICK`] words for `segments` segments: no merge selected.
///
/// Ordered by [`ARGMIN_INDEX_SLOT`] and [`ARGMIN_RANK_SLOT`] rather than
/// hand-written as a literal pair, so a future ABI slot swap moves this seed
/// with it instead of leaving it silently transposed.
fn pick_seed(segments: u32) -> Vec<u32> {
    let mut words = vec![0_u32; (segments * ARGMIN_WORDS_PER_SEGMENT) as usize];
    for segment in 0..segments {
        let base = (segment * ARGMIN_WORDS_PER_SEGMENT) as usize;
        words[base + ARGMIN_INDEX_SLOT as usize] = NO_MERGE_INDEX;
        words[base + ARGMIN_RANK_SLOT as usize] = Rank::ABSENT.0;
    }
    words
}

fn lane() -> Expr {
    Expr::gid_x()
}

fn barrier() -> Node {
    Node::Barrier {
        ordering: MemoryOrdering::SeqCst,
    }
}

/// The two buffers the pass body owns, numbered from [`FIRST_CALLER_BINDING`].
///
/// Both are `ReadWrite` storage rather than outputs: vyre rule V022 admits at
/// most one `BufferDecl::output` per program and the loop harness has already
/// spent it, so a selection scratch declared as an output makes the whole
/// program fail validation. The pick buffer's count is
/// [`ARGMIN_WORDS_PER_SEGMENT`] per segment rather than a literal 2, so it
/// tracks the argmin ABI instead of silently under-declaring if that ABI widens.
fn bpe_caller_buffers(shape: LoopShape, capacity: u32) -> Vec<BufferDecl> {
    vec![
        BufferDecl::storage(
            NAME_BPE_SLOTS,
            FIRST_CALLER_BINDING,
            BufferAccess::ReadOnly,
            DataType::U32,
        )
        .with_count(capacity * SLOT_WORDS),
        BufferDecl::storage(
            NAME_BPE_PICK,
            FIRST_CALLER_BINDING + 1,
            BufferAccess::ReadWrite,
            DataType::U32,
        )
        .with_count(shape.segments() * ARGMIN_WORDS_PER_SEGMENT),
    ]
}

/// Segment-local coordinates every phase of the pass body needs.
///
/// The state layout is [`crate::gpu_loop`]'s, so `seg`, `slot`, `base` and `len`
/// come from [`segment_coordinates`] rather than being re-derived here. This is
/// THE single place this module touches that layout, and it must stay that way:
/// under the padded layout each workgroup owns a fixed
/// [`LOOP_WORKGROUP_WIDTH`]-word region and holds whole segments only, so the
/// dense forms `seg = lane / stride` and `base = seg * stride` attribute a lane
/// in one workgroup to a segment owned by another. That failure is silent, since
/// both forms produce a valid-looking index into a real segment.
///
/// `pick_at` is the only name bound here, because the selection scratch is this
/// module's buffer and not the loop's.
fn bpe_locals(shape: LoopShape) -> Vec<Node> {
    let mut locals = segment_coordinates(shape);
    locals.push(Node::let_bind(
        "pick_at",
        Expr::mul(Expr::var("seg"), Expr::u32(ARGMIN_WORDS_PER_SEGMENT)),
    ));
    locals
}

/// Probe this lane's own adjacent pair and run `then` with the result bound.
///
/// The key word order is the table's: `lo` is the RIGHT token and `hi` is the
/// LEFT one, matching `split_key`. Swapping them probes a different slot and
/// reads absent for every real pair, which converges immediately on the
/// unmerged byte stream and is exactly the interface mismatch the parity suite
/// exists to catch.
///
/// Composes through [`probe_child`] rather than splicing the raw fragment, so
/// the emitted Region carries `source_region: Some(exatok::gpu_loop::..)` and
/// `cargo xtask print-composition` can walk from the loop down into the probe.
/// The consumer goes in the `then` body because a Region opens a binding scope,
/// so a sibling placed after it cannot see the probe results.
///
/// The two key expressions index by `lane()`, the absolute state word, not by
/// `base + slot`. That is correct under the padded layout for the same reason
/// the stores below are: a lane's own word is wherever the lane sits, and the
/// pair it heads is the next word along, inside the same segment by
/// [`heads_a_pair`]'s upper bound.
fn probe_own_pair(prefix: &str, capacity: u32, window: u32, then: Vec<Node>) -> Node {
    probe_child(
        LOOP_OP_ID,
        prefix,
        NAME_BPE_SLOTS,
        capacity,
        window,
        Expr::load(NAME_STATE_CURRENT, Expr::add(lane(), Expr::u32(1))),
        Expr::load(NAME_STATE_CURRENT, lane()),
        then,
    )
}

/// This lane heads an adjacent pair: `1 <= slot < len`, so token `slot - 1` has
/// a right neighbour inside the same segment.
///
/// The upper bound is what keeps a merge inside its pretoken. `slot == len`
/// would pair the segment's last live token with the first dead slot, and
/// `slot == len + 1` with the next segment's length word.
fn heads_a_pair(body: Vec<Node>) -> Node {
    Node::if_then(
        Expr::ge(Expr::var("slot"), Expr::u32(1)),
        vec![Node::if_then(
            Expr::lt(Expr::var("slot"), Expr::var("len")),
            body,
        )],
    )
}

/// One exact BPE merge per segment per pass: the leftmost lowest-rank adjacent
/// pair, with the rank and merged id taken from a real device table probe.
///
/// This IS the reference algorithm's next step in every segment at once, so its
/// exactness follows from the reference algorithm rather than from any property
/// of the state being merged.
///
/// Two unsigned minimum reductions rather than one comparator carrying
/// `(rank, index)`: the first finds the minimum rank in the segment, the second
/// the minimum index among lanes holding it, so leftmost tie-breaking is a
/// consequence of `min` instead of a hand-written tie clause that is wrong
/// invisibly. The reduction is a per-segment atomic rather than
/// `vyre_primitives::reduce::workgroup_tree::min_u32_child`, because that
/// primitive reduces over the WHOLE workgroup while a workgroup here holds
/// several segments; a workgroup-wide minimum would merge one pair per
/// workgroup instead of one per pretoken. That is also why this body binds no
/// `local`: it composes no `*_child` reduction helper, and `probe_child` binds
/// every name it references.
///
/// Leftmost tie-breaking is the SECOND reduction, not a side effect of the
/// first. A bare atomic min on rank alone leaves the winning LANE undefined
/// when two positions hold the same rank, which is why phase two exists: among
/// exactly the lanes holding the winning rank, an atomic min over token index
/// pins the leftmost. That is ground truth's strict `<` tie rule, and it is
/// resolved by `min` rather than by a hand-written comparator.
///
/// Packing rank and index into one atomic word instead is not available here:
/// `o200k_base` ranks reach 199997, so rank needs 18 bits and the index field
/// would be capped at 14, and a vocabulary one bit larger would silently
/// corrupt the index rather than fail. Two reductions have no bit budget to
/// outgrow.
///
/// Phase two is guarded on presence as well as equality, because
/// `Rank::ABSENT == NO_MERGE_INDEX == u32::MAX`: an unguarded index reduction
/// over an all-absent segment finds `rank == minimum` true for every lane and
/// reports a merge at the segment's first pair. At a median pretoken of 3
/// tokens the all-absent window is the common case, not a corner.
///
/// The four phases are separated by barriers because they are a true pipeline:
/// the rank vote must be complete before any lane reads the winning rank, and
/// the index vote before the emit phase reads the winning index. Those barriers
/// are workgroup-scoped, which is the whole reason a single pretoken may not
/// straddle a workgroup and therefore the reason [`MAX_PRETOKEN_TOKENS`] is a
/// hard bound. Note that the reference interpreter runs lanes sequentially, so a
/// deleted barrier has NO observable effect there; that was confirmed by
/// mutation rather than assumed, and only a real device catches it.
fn bpe_merge_body(shape: LoopShape, capacity: u32, window: u32) -> Vec<Node> {
    let pick_rank = Expr::load(
        NAME_BPE_PICK,
        Expr::add(Expr::var("pick_at"), Expr::u32(ARGMIN_RANK_SLOT)),
    );
    let pick_rank_at = || Expr::add(Expr::var("pick_at"), Expr::u32(ARGMIN_RANK_SLOT));
    let pick_index_at = || Expr::add(Expr::var("pick_at"), Expr::u32(ARGMIN_INDEX_SLOT));

    let mut reset = bpe_locals(shape);
    reset.push(Node::if_then(
        Expr::eq(Expr::var("slot"), Expr::u32(0)),
        vec![
            Node::store(NAME_BPE_PICK, pick_rank_at(), Expr::u32(Rank::ABSENT.0)),
            Node::store(NAME_BPE_PICK, pick_index_at(), Expr::u32(NO_MERGE_INDEX)),
        ],
    ));

    let mut vote_rank = bpe_locals(shape);
    let rank_of_own_pair = probe_rank_var(PROBE_RANK);
    vote_rank.push(heads_a_pair(vec![probe_own_pair(
        PROBE_RANK,
        capacity,
        window,
        vec![Node::if_then(
            Expr::ne(
                Expr::var(rank_of_own_pair.as_str()),
                Expr::u32(Rank::ABSENT.0),
            ),
            vec![Node::let_bind(
                "wtp_rank_prev",
                Expr::atomic_min(
                    NAME_BPE_PICK,
                    pick_rank_at(),
                    Expr::var(rank_of_own_pair.as_str()),
                ),
            )],
        )],
    )]));

    let mut vote_index = bpe_locals(shape);
    let rank_at_index_vote = probe_rank_var(PROBE_INDEX);
    vote_index.push(heads_a_pair(vec![probe_own_pair(
        PROBE_INDEX,
        capacity,
        window,
        vec![Node::if_then(
            Expr::and(
                Expr::ne(
                    Expr::var(rank_at_index_vote.as_str()),
                    Expr::u32(Rank::ABSENT.0),
                ),
                Expr::eq(Expr::var(rank_at_index_vote.as_str()), pick_rank.clone()),
            ),
            vec![Node::let_bind(
                "wtp_idx_prev",
                Expr::atomic_min(
                    NAME_BPE_PICK,
                    pick_index_at(),
                    Expr::sub(Expr::var("slot"), Expr::u32(1)),
                ),
            )],
        )],
    )]));

    let mut emit = bpe_locals(shape);
    emit.extend([
        Node::let_bind("pick", Expr::load(NAME_BPE_PICK, pick_index_at())),
        Node::let_bind(
            "new_len",
            Expr::select(
                Expr::ne(Expr::var("pick"), Expr::u32(NO_MERGE_INDEX)),
                Expr::saturating_sub(Expr::var("len"), Expr::u32(1)),
                Expr::var("len"),
            ),
        ),
        Node::if_then_else(
            Expr::eq(Expr::var("slot"), Expr::u32(0)),
            vec![Node::store(NAME_STATE_NEXT, lane(), Expr::var("new_len"))],
            vec![
                Node::let_bind("token", Expr::sub(Expr::var("slot"), Expr::u32(1))),
                Node::if_then_else(
                    // Recanonicalize the dead tail every pass. A leaked stale
                    // word keeps flipping and the fixpoint never settles.
                    Expr::ge(Expr::var("token"), Expr::var("new_len")),
                    vec![Node::store(NAME_STATE_NEXT, lane(), Expr::u32(DEAD_SLOT))],
                    vec![Node::if_then_else(
                        Expr::gt(Expr::var("token"), Expr::var("pick")),
                        // Past the merge: the segment compacts left by one.
                        vec![Node::store(
                            NAME_STATE_NEXT,
                            lane(),
                            Expr::load(NAME_STATE_CURRENT, Expr::add(lane(), Expr::u32(1))),
                        )],
                        vec![Node::if_then_else(
                            Expr::eq(Expr::var("token"), Expr::var("pick")),
                            // The winning lane's own pair IS the picked pair, so
                            // its probe already holds the merged id.
                            vec![probe_own_pair(
                                PROBE_MERGED_ID,
                                capacity,
                                window,
                                vec![Node::store(
                                    NAME_STATE_NEXT,
                                    lane(),
                                    Expr::var(probe_id_var(PROBE_MERGED_ID).as_str()),
                                )],
                            )],
                            // Before the merge, and every slot when nothing was
                            // picked: NO_MERGE_INDEX exceeds every token index.
                            vec![Node::store(
                                NAME_STATE_NEXT,
                                lane(),
                                Expr::load(NAME_STATE_CURRENT, lane()),
                            )],
                        )],
                    )],
                ),
            ],
        ),
    ]);

    // THE single guard site. `lane_is_live` is gpu_loop's own liveness
    // predicate and must be used verbatim: a lane can be idle two ways under
    // the padded layout, sitting in the unused tail of its own workgroup or in
    // a workgroup past the last real segment, and a bare
    // `lane() < shape.state_words()` catches NEITHER because the padding lives
    // inside the state array rather than past its end.
    //
    // What that mis-guard actually costs THIS body was measured by mutation, not
    // assumed, and it is worth writing down because the answer is not "wrong
    // ids": substituting `lane() < shape.state_words()` leaves all ten tests in
    // `tests/device_api.rs` GREEN on the 5090. A tail lane's coordinates resolve
    // to the NEXT group's first segment, and every phase happens to be harmless
    // there. Its reset writes the same two constants that segment's own slot-0
    // lane writes, so it is idempotent. Its votes are guarded on rank presence
    // and `close_pass` pins padding to DEAD_SLOT, so the pair it probes is
    // `(DEAD_SLOT, DEAD_SLOT)` and absent. Its emit writes into padding, which
    // `close_pass` overwrites.
    //
    // The residue is NOT harmless: in the final group the same lane resolves to
    // `seg >= shape.segments()` and stores past the end of NAME_BPE_PICK, which
    // is declared for exactly `segments` entries. This backend does not trap a
    // store a few words past an allocation, so the defect is invisible here and
    // would surface as corruption on a backend that packs buffers or bounds
    // checks. That is why the guard is pinned by
    // `the_pass_body_guards_every_phase_with_the_loops_own_predicate` below
    // rather than left to a behavioral test that cannot see it.
    let guard = |body: Vec<Node>| Node::if_then(lane_is_live(shape), body);
    vec![
        guard(reset),
        barrier(),
        guard(vote_rank),
        barrier(),
        guard(vote_index),
        barrier(),
        guard(emit),
    ]
}

// ---------------------------------------------------------------------------
// Batching
// ---------------------------------------------------------------------------

/// Longest pretoken one dispatch can hold, in tokens.
///
/// Re-derived from the constraint [`crate::gpu_loop`] actually imposes rather
/// than from a remembered rule of thumb: the pass body's phase barriers order
/// writes within ONE workgroup, so a single segment may not straddle a workgroup
/// boundary. A segment costs `len + 1` words, a length word plus its tokens, and
/// a workgroup owns [`LOOP_WORKGROUP_WIDTH`] words, so the bound is
/// `LOOP_WORKGROUP_WIDTH - 1` and nothing longer can be dispatched at all.
///
/// An earlier version of this constant halved the width on the belief that a
/// segment costs `2 * (len + 1)`. It does not: the ping-pong buffers are two
/// separate declarations of `state_words` each, not one buffer of twice the
/// size. That bound was conservative rather than wrong-in-effect, but it would
/// have rejected a 200-token pretoken the loop handles fine.
///
/// This is the ONLY thing the workgroup width still caps. The number of
/// pretokens per dispatch is not bounded by it: the state layout is padded so
/// each workgroup holds whole segments, segments are independent because a
/// merge never crosses a pretoken boundary, and a dispatch carries as many
/// workgroups as the device's cooperative residency admits.
///
/// Note that [`LoopShape::words_per_group`] can exceed
/// [`LOOP_WORKGROUP_WIDTH`], because it rounds a group's used words up to a
/// whole number of widths so a segment wider than one workgroup is allocated
/// rather than addressed past the buffer. That does NOT relax this cap: the
/// allocation is correct there, the barriers are still workgroup-scoped, and a
/// segment spanning two workgroups would be ordered by neither. This cap is why
/// nothing in this module ever reaches that arm.
///
/// 255 is a HARD limit, not a tuning choice, and a pretoken above it is never
/// SPLIT: splitting a pretoken across dispatches would merge across a boundary
/// the reference never crosses, silently producing ids tiktoken does not. It is
/// encoded on the HOST instead, by [`crate::incremental::MergeState`] over the
/// very table the device probes. That is the same leftmost-lowest-rank
/// algorithm over the same rows, byte-identical to
/// [`crate::reference::encode_pretoken`] as `tests/incremental_merge.rs` pins,
/// so the ids are identical either way, and [`Routing`] reports how many
/// pretokens took that path because an operator must be able to see when the
/// device is not doing the work.
///
/// A pretoken's token count on entry EQUALS its byte count, because merging
/// starts one token per byte. So the bound is 256 BYTES in one pretoken, which
/// is far lower than it looks: a base64 blob, a minified JS line, a hex dump, a
/// long CJK run and a wide log line all reach it routinely, and refusing them
/// made the device path unusable on ordinary text.
pub const MAX_PRETOKEN_TOKENS: usize = LOOP_WORKGROUP_WIDTH as usize - 1;

/// Fraction of the device's queried cooperative block ceiling that one dispatch
/// may ask for, as a percentage.
///
/// Headroom, not tuning. [`cooperative_block_ceiling`] answers with a THREAD
/// residency bound, `(max_threads_per_sm / workgroup) * sm_count`, and the
/// stricter per-kernel bound that register and shared-memory pressure impose is
/// enforced only at launch. So the queried number is a ceiling to stay under and
/// not a capacity to fill: one register added to the pass body lowers the real
/// limit without moving the query at all. Asking for three quarters leaves room
/// for that drift, and it is the reason a body edit does not turn into a launch
/// failure on the next encode.
const COOPERATIVE_HEADROOM_PERCENT: u32 = 75;

/// Workgroups one dispatch may ask for, given the device's queried block
/// ceiling.
///
/// Pure arithmetic over a measured input, so the headroom rule is testable
/// without a device. The measurement itself is
/// [`DeviceTokenizer::queried_block_ceiling`], which asks the backend rather
/// than restating a number: the ceiling belongs to the card and to the compiled
/// pass body, so a constant here would be wrong on the next of either.
///
/// A ceiling of zero is not a failure: it means the backend admits no
/// cooperative launch of this program at any grid size, and a single-group
/// dispatch carries no grid barrier and needs none, so one workgroup is exactly
/// what such a backend can run. Never zero either way, because a dispatch of no
/// workgroups encodes nothing.
#[must_use]
fn workgroups_within_headroom(block_ceiling: u32) -> u32 {
    // Widened to 64 bits before multiplying. A `u32` product overflows at a
    // ceiling of 57 million and a saturating one silently collapses the budget to
    // a hundredth of the ceiling instead of three quarters, which is a throughput
    // cliff hiding inside an arithmetic detail.
    let reduced = u64::from(block_ceiling) * u64::from(COOPERATIVE_HEADROOM_PERCENT) / 100;
    // The quotient is at most the input, so the conversion cannot fail. The
    // identity fallback rather than a panic because a headroom rule must never be
    // the thing that takes an encode down.
    u32::try_from(reduced).unwrap_or(block_ceiling).max(1)
}

/// Shape the residency query plans its launch geometry from.
///
/// MULTI-group deliberately. [`cooperative_block_ceiling`] answers zero for a
/// program that carries no grid barrier at all, and only the multi-group form of
/// the loop emits one, so a single-group probe would report "no cooperative
/// launch at any grid size" and pin every dispatch to one workgroup forever.
/// That is the stall the loop's grid fixpoint removed, and it would come back
/// silently: the ids would still be exact and only the throughput would
/// collapse.
///
/// Two groups at a four-token stride, four being the median pretoken this
/// tokenizer sees, so the probe compiles the pass body at a stride real
/// dispatches use. Nothing else about the choice matters: the ceiling is a
/// property of the compiled kernel and of the block width, and every shape this
/// module admits lowers to blocks of [`LOOP_WORKGROUP_WIDTH`] lanes. The pass
/// budget is 2 for the same reason, since a budget bounds passes and not
/// geometry.
fn residency_probe_shape() -> LoopShape {
    const TOKENS: u32 = 4;
    let per_group = LoopShape::new(1, TOKENS, 1).segments_per_group();
    LoopShape::new(per_group * 2, TOKENS, 2)
}

/// Segments one dispatch of `workgroups` workgroups can carry when its longest
/// pretoken holds `longest_tokens` tokens.
///
/// Public because it is the only honest way to pre-size work against this
/// tokenizer: it folds in both the per-workgroup packing and the stride padding,
/// and a caller batching its own inputs would otherwise have to restate the
/// layout arithmetic and fork from it. Pair it with
/// [`DeviceTokenizer::workgroups_per_dispatch`], which supplies the count this
/// device admits.
///
/// `workgroups` is a parameter and not a constant because it is a property of
/// the DEVICE. It was the constant 1 while `gpu_loop` composed a fixpoint whose
/// only barriers were workgroup-scoped, so the emitted program carried no grid
/// barrier, the CUDA backend admitted no cooperative launch of it at any grid
/// size, and a multi-workgroup batch could only fail closed. The grid fixpoint
/// form removed that stall, so the true ceiling is now the device's cooperative
/// residency, which is queried rather than written down: a hardcoded number is
/// wrong on the next card and wrong again as soon as the pass body gains a
/// register.
///
/// Routed through [`LoopShape::segments_per_group`] rather than restating
/// `LOOP_WORKGROUP_WIDTH / stride`, so the packing rule lives once in the module
/// that owns the layout. Stride-aware because every segment in a dispatch is
/// padded to the dispatch's longest pretoken: admitting one long pretoken
/// shrinks how many fit per workgroup, and the arithmetic must see that.
///
/// This is equally a bound on the dispatch's state array, since a workgroup owns
/// [`LoopShape::words_per_group`] words, which is exactly
/// [`LOOP_WORKGROUP_WIDTH`] for every stride this module admits: at 1020
/// workgroups the array is 261120 words, 1020 KiB per ping-pong buffer and just
/// over 2 MiB for the pair, and it holds at any pretoken length rather than
/// ballooning for long ones.
///
/// Total over every `usize`, and it takes ONE guard to be so. The capacity is
/// clamped in `usize` BEFORE it is narrowed to `u32`, which makes the narrowing
/// lossless by construction: there is no fallible conversion left, so there is no
/// fallback branch that could disagree with the clamp about where the boundary
/// is.
///
/// It used to be `u32::try_from(longest_tokens.max(1)).unwrap_or(LOOP_WORKGROUP_WIDTH)`,
/// two mechanisms defending totality with a seam between them, and the seam was a
/// real single-point panic. At exactly `u32::MAX` the conversion SUCCEEDS, so the
/// fallback never fired, and [`LoopShape::stride`] then computed
/// `segment_capacity + 1` on `u32::MAX`. Both failure modes were OBSERVED against
/// the pre-fix expression, not reasoned about: a debug profile panicked on the add
/// (`attempt to add with overflow`, `gpu_loop.rs:402`), and a release profile
/// wrapped the add to 0 and panicked in [`LoopShape::segments_per_group`]'s
/// division instead (`attempt to divide by zero`, `gpu_loop.rs:413`). One defect,
/// two panics, which is why the regression test asserts the returned VALUE: a test
/// phrased as "does not panic" would have gone green in release against a fix that
/// only silenced the add.
/// One value below and one value above were both fine, which is exactly why no
/// sampled fixture found it, and why
/// `numeric_boundary_exactness::segments_per_dispatch_stays_total_across_the_u32_boundary_it_guards`
/// asserts the RETURN VALUE at all three points rather than the absence of a
/// crash.
///
/// The clamp is INERT for every argument the crate itself passes. [`batches`] calls
/// this with a pretoken's token count, and a pretoken above
/// [`MAX_PRETOKEN_TOKENS`] is host routed before batching, so the argument on the
/// encode path never exceeds 255 and never meets the clamp at 256. Shape counts,
/// dispatch counts and plan cache keys are therefore unchanged by it. What the
/// clamp fixes is the surface an external caller reaches, which is the surface this
/// function is `pub` for.
#[must_use]
pub fn segments_per_dispatch(longest_tokens: usize, workgroups: u32) -> usize {
    // Clamping to the workgroup width loses nothing: any capacity at or above the
    // width already leaves room for exactly one segment per workgroup, since a
    // segment costs `capacity + 1` words and `segments_per_group` floors at 1. So
    // every value from the width upward, including the ones that no longer reach
    // the layout arithmetic, has the same answer they would have had.
    // The cast cannot lose information, because `clamped` is at most
    // `LOOP_WORKGROUP_WIDTH`, which is itself a `u32`. That is what the clamp buys:
    // no fallible conversion, so no fallback branch, so no second guard to
    // disagree with this one about where the boundary is.
    let clamped = longest_tokens.max(1).min(LOOP_WORKGROUP_WIDTH as usize);
    let capacity = clamped as u32;
    let per_group = LoopShape::new(1, capacity, 1).segments_per_group() as usize;
    workgroups.max(1) as usize * per_group
}

/// How pretokens are grouped into dispatches.
///
/// Both orders must produce the identical id stream, because merging never
/// crosses a pretoken boundary and parallelism is ACROSS pretokens. That is a
/// contract worth asserting rather than assuming, so both stay reachable.
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
pub enum Batching {
    /// Input order, which is what a dispatcher does before anyone measures it.
    InputOrder,
    /// Longest pretoken first, so each batch is depth-homogeneous.
    ///
    /// A batch runs until its DEEPEST segment converges, so one mixing a
    /// 1-token pretoken with a 40-token one idles most of its lanes for most of
    /// its passes. Merge depth tracks token count closely at these sizes, mean
    /// 3.05 merges against a median of 3 bytes, so grouping by length makes a
    /// batch converge at roughly one depth and removes that waste. Descending
    /// rather than ascending so the greedy stride-aware fill starts from the
    /// widest stride instead of widening mid-batch.
    ///
    /// Sorting alone does not deliver that homogeneity; the stride spread bound
    /// does. Descending order only guarantees that a batch's stride is fixed by
    /// its FIRST member, so without a spread bound a single dispatch would still
    /// swallow the whole corpus and pad every 3-token pretoken to the longest
    /// one present. What sorting buys is that the spread bound then cuts the
    /// corpus into contiguous length bands instead of arbitrary runs.
    #[default]
    ByLength,
}

/// Widest stride a dispatch may carry, as a multiple of its shortest segment's
/// true size.
///
/// This is a PASS budget bound before it is a memory one, and it is what makes
/// [`Batching::ByLength`] mean anything. Every segment in a dispatch is padded
/// to the dispatch's longest pretoken and the loop runs until the DEEPEST
/// segment converges, so a dispatch mixing a 3-token pretoken with a 200-token
/// one runs about 200 passes over all of them and stores 201 words for each.
///
/// The two halves of that waste are bounded DIFFERENTLY, and the difference is
/// worth stating because it is not what "spread of 2" suggests. The predicate
/// below compares STRIDES, `widened + 1` against `2 * (narrowed + 1)`, so it
/// admits a longest of `l` beside a shortest of `s` while `l <= 2s + 1`.
///
/// * WORDS are bounded at exactly 2. A segment's words ARE its stride, so the
///   padded segment occupies at most `2 * (s + 1)` words where it needs `s + 1`,
///   and the factor is attained rather than exceeded.
/// * PASSES are bounded at `2 + 1/s`, not at 2. The dispatch runs until its
///   deepest segment converges, and at the band boundary that is `2s + 1` passes
///   over a segment needing `s`. The overshoot is worst where pretokens are
///   shortest: 3x at `s == 1`, about 2.33x at the median 3-token pretoken this
///   tokenizer actually sees, falling toward 2 as segments grow.
///
/// So the pass waste this constant admits in production is closer to 2.33x than
/// to 2x. Do not tighten it on the strength of that number alone: halving it to 1
/// forbids any padding at all and cuts the corpus into one band per distinct
/// length, which multiplies the dispatch count. The real reach is pinned by
/// `numeric_boundary_exactness::the_spread_bound_delivers_its_word_claim_exactly_and_not_its_pass_claim`,
/// so this doc and its proof move together.
///
/// Without it the whole corpus lands in one dispatch, because the workgroup
/// count alone stops bounding anything useful once the
/// per-dispatch pretoken count is effectively unbounded. That was invisible
/// while a dispatch was capped at one workgroup: the 256-word cap forced small
/// batches, so the padding stayed accidentally bounded and nothing had to state
/// this.
///
/// The cost is dispatch count, and it is logarithmic rather than linear: bands
/// double, so a corpus spanning 1 to 255 tokens needs at most 8 of them however
/// many pretokens it holds.
///
/// Public so [`batches_for_lengths`] callers and the batching-order suite can
/// reproduce the grouping predicate exactly rather than restating the 2.
pub const MAX_STRIDE_SPREAD: usize = 2;

/// The permutation of `0..n` that visits indices by `key`, highest key first
/// and ascending index within one key.
///
/// That is exactly the order a stable `(Reverse(key), index)` comparison sort
/// produces, computed here by counting instead: `key` is read once per index
/// to size the buckets and once to place, bucket starts are the sums of every
/// bucket above, and the scatter walks indices in ascending order so ties keep
/// their index order for free. No two elements are ever compared, which is the
/// whole point at [`batches`]' call site: run lengths there are bounded by
/// [`MAX_PRETOKEN_TOKENS`], so the key domain is 256 buckets and the sort is
/// O(n + 256) reads where the comparison sort was O(n log n) key extractions.
///
/// Public so `tests/encode_batching_order.rs` can inject a counting key and
/// pin the extraction count against the comparison sort it replaced.
///
/// # Panics
///
/// Panics when any `key(index)` is at or past `buckets`. At the [`batches`]
/// call site that cannot happen: [`DeviceTokenizer::encode_batch`] routes a
/// pretoken longer than [`MAX_PRETOKEN_TOKENS`] to the host before batching,
/// so a longer run reaching the sort is a routing defect and is reported
/// rather than silently mis-ordered.
#[must_use]
pub fn counting_permutation(
    n: usize,
    buckets: usize,
    mut key: impl FnMut(usize) -> usize,
) -> Vec<usize> {
    // Nothing to order allocates nothing: an all-host encode still reaches
    // `batches` with zero runs, and it must not pay for buckets it will never
    // read, the same contract the state and id reserves above keep.
    if n == 0 {
        return Vec::new();
    }
    let mut counts = vec![0_usize; buckets];
    for index in 0..n {
        let bucket = key(index);
        assert!(
            bucket < buckets,
            "key {bucket} for index {index} is past the {buckets}-bucket domain: encode_batch \
             routes any pretoken longer than MAX_PRETOKEN_TOKENS to the host before batching, \
             so a longer run reaching the sort is a routing defect"
        );
        counts[bucket] += 1;
    }
    // Emission is highest bucket first, so a bucket's first slot is the count
    // of every index in a bucket above it.
    let mut starts = vec![0_usize; buckets];
    let mut placed = 0_usize;
    for bucket in (0..buckets).rev() {
        starts[bucket] = placed;
        placed += counts[bucket];
    }
    // Ascending index order into per-bucket cursors, so one bucket's indices
    // come out ascending: the comparison sort's stability, for free.
    let mut order = vec![0_usize; n];
    for index in 0..n {
        let bucket = key(index);
        order[starts[bucket]] = index;
        starts[bucket] += 1;
    }
    order
}

/// Group pretokens into batches, one dispatch each.
///
/// Greedy and stride-aware: every segment in a batch is padded to the batch's
/// longest pretoken, so admitting one long pretoken shrinks the batch. This is
/// what a real dispatcher has to do, and getting it wrong is not a silent
/// failure, `device_loop_program` lowers an over-wide shape to an IR trap.
///
/// Two bounds close a batch, and they bound different resources. The segment
/// count bounds the dispatch's GRID through [`segments_per_dispatch`], so a
/// batch never asks for more than `workgroups` workgroups and therefore never
/// asks for a grid the device's cooperative residency will refuse.
/// [`MAX_STRIDE_SPREAD`] bounds the padding and the pass budget, which the
/// segment count does not touch at all.
///
/// Returns ORIGINAL indices, so a reordering mode cannot permute the output
/// stream: the caller places each segment's ids back at its own index.
///
/// Every pretoken is assumed to hold at most [`MAX_PRETOKEN_TOKENS`] tokens.
/// [`DeviceTokenizer::encode_batch`] routes a longer one to the host BEFORE
/// calling this, so nothing here ever sees one and the check is not repeated.
///
/// `runs` names where each device-bound pretoken's start state sits in the
/// encode's flat state buffer. Only [`Run::len`] is read here, because what
/// decides a batch is the STRIDE every segment in it pads out to; the offsets
/// belong to whoever reads the words back.
fn batches(runs: &[Run], mode: Batching, workgroups: u32) -> Vec<Vec<usize>> {
    // Longest first, ties ascending by index: exactly the permutation a stable
    // `(Reverse(len), index)` comparison sort produced here, now counted
    // rather than compared. The length domain is bounded by
    // `MAX_PRETOKEN_TOKENS` because `encode_batch` routes a longer pretoken to
    // the host BEFORE this call, so 256 buckets always suffice.
    let order: Vec<usize> = if mode == Batching::ByLength {
        counting_permutation(runs.len(), MAX_PRETOKEN_TOKENS + 1, |index| runs[index].len)
    } else {
        (0..runs.len()).collect()
    };

    let mut out: Vec<Vec<usize>> = Vec::new();
    let mut current: Vec<usize> = Vec::new();
    let mut longest = 0_usize;
    let mut shortest = usize::MAX;
    for index in order {
        let len = runs[index].len;
        let widened = longest.max(len);
        let narrowed = shortest.min(len);
        // Strides, not token counts: a segment costs its tokens plus one length
        // word, so comparing raw lengths would let a 1-token pretoken join a
        // 3-token one at a real spread of 2 but reject it at a nominal 3.
        let spread_broken = widened + 1 > MAX_STRIDE_SPREAD * (narrowed + 1);
        let count_broken = current.len() + 1 > segments_per_dispatch(widened, workgroups);
        if !current.is_empty() && (spread_broken || count_broken) {
            out.push(std::mem::take(&mut current));
            longest = 0;
            shortest = usize::MAX;
        }
        longest = longest.max(len);
        shortest = shortest.min(len);
        current.push(index);
    }
    if !current.is_empty() {
        out.push(current);
    }
    out
}

/// What [`batches`] returns for pretokens of the given lengths.
///
/// Exists so the batching-order suite can pin the dispatch grouping without
/// reaching the crate-private [`Run`]. The `start` offsets are filled in
/// densely, one pretoken after another, because [`batches`] reads only
/// [`Run::len`]: the offsets belong to whoever reads the words back, and there
/// are no words here.
///
/// # Panics
///
/// Panics when `mode` is [`Batching::ByLength`] and a length exceeds
/// [`MAX_PRETOKEN_TOKENS`]; see [`counting_permutation`].
#[must_use]
pub fn batches_for_lengths(
    lengths: &[usize],
    mode: Batching,
    workgroups: u32,
) -> Vec<Vec<usize>> {
    let mut start = 0_usize;
    let runs: Vec<Run> = lengths
        .iter()
        .map(|&len| {
            let run = Run { start, len };
            start += len;
            run
        })
        .collect();
    batches(&runs, mode, workgroups)
}

// ---------------------------------------------------------------------------
// Where the work happened
// ---------------------------------------------------------------------------

/// Which pretokens the device encoded and which the host did.
///
/// Reported because a caller cannot otherwise tell: the ids are byte-identical
/// either way by construction, so nothing in the output reveals the split. An
/// input that spent most of its work on the host while being reported as GPU
/// tokenization would be a benchmark lie, and these counts are the only thing
/// standing between a reader and that lie, so they are exact rather than
/// indicative.
///
/// Returned rather than stashed behind an accessor like
/// [`DeviceTokenizer::last_dispatch_count`], deliberately. `encode` takes `&self`
/// so a tokenizer can be shared across threads, and two concurrent encodes would
/// overwrite each other's stashed tally; a benchmark reading a clobbered count is
/// exactly the failure these numbers exist to prevent. A returned value cannot be
/// raced.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub struct Routing {
    on_device: usize,
    on_host: usize,
    largest_host_tokens: usize,
}

impl Routing {
    /// Pretokens encoded on the device.
    #[must_use]
    pub const fn on_device(self) -> usize {
        self.on_device
    }

    /// Pretokens encoded on the host because they exceeded
    /// [`MAX_PRETOKEN_TOKENS`].
    #[must_use]
    pub const fn on_host(self) -> usize {
        self.on_host
    }

    /// Token count of the LARGEST pretoken the host took, or zero when the host
    /// took none.
    ///
    /// The largest rather than the total, because host cost is superlinear in one
    /// pretoken's length while the count of them is only linear: one 40 KiB
    /// pretoken is the thing worth seeing, and a total would hide it behind a
    /// thousand 260-byte ones.
    #[must_use]
    pub const fn largest_host_tokens(self) -> usize {
        self.largest_host_tokens
    }

    /// Whether the device did all of the work.
    #[must_use]
    pub const fn all_on_device(self) -> bool {
        self.on_host == 0
    }
}

/// Ids for each input, with the routing that produced them.
///
/// Deliberately NOT `Deref<Target = [Vec<TokenId>]>`, though the ergonomics are
/// tempting and this type carried one briefly. `Encoded` is a two-field value
/// and not a smart pointer, so a deref would let `encoded.len()` read as the
/// whole answer while [`Self::routing`] sat beside it unread. Those counters are
/// the only evidence that a host-routed encode is not being reported as a clean
/// GPU run, and a type offering a path around them defeats the mechanism it
/// exists to carry. [`Self::ids`] and [`Self::into_ids`] read fine.
///
/// [`AsRef`] is implemented instead, because it is explicit at the call site
/// rather than invisible. Its target is `[Vec<TokenId>]` and not `[TokenId]`:
/// `encode_batch` answers per INPUT, and flattening here would silently join two
/// inputs' ids into one stream, which is the misalignment the per-input shape
/// exists to prevent.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Encoded {
    ids: Vec<Vec<TokenId>>,
    routing: Routing,
}

impl Encoded {
    /// Ids per input, in input order.
    #[must_use]
    pub fn ids(&self) -> &[Vec<TokenId>] {
        &self.ids
    }

    /// Take the ids, dropping the routing.
    #[must_use]
    pub fn into_ids(self) -> Vec<Vec<TokenId>> {
        self.ids
    }

    /// Where the work happened.
    #[must_use]
    pub const fn routing(&self) -> Routing {
        self.routing
    }
}

impl AsRef<[Vec<TokenId>]> for Encoded {
    fn as_ref(&self) -> &[Vec<TokenId>] {
        &self.ids
    }
}

// ---------------------------------------------------------------------------
// Where the host time went
// ---------------------------------------------------------------------------

/// One named component of an encode's host cost.
///
/// Every variant is a LEAF: no phase contains another, so their durations add,
/// and whatever they do not account for is
/// [`EncodeProfile::unattributed`] rather than being spread silently over the
/// named rows. That property is the point of the type. A breakdown whose rows
/// sum to a third of the observed wall has not explained the encode, it has
/// found three things that are not the cost, and only an explicit remainder
/// makes that visible instead of persuasive.
///
/// The boundaries fall where a COST OWNER changes rather than where the code
/// happens to break into functions, because the question a profile answers is
/// who has to fix a slow encode.
///
/// [`Self::Dispatch`] is therefore ONE phase and not three. Everything under
/// [`run_device_loop_borrowed`] is either [`crate::gpu_loop`]'s marshalling,
/// vyre's host path, or the device itself, and this module cannot separate them
/// without instrumenting a module it does not own. The CUDA backend already
/// separates them from the inside and publishes the split through
/// [`vyre_driver::VyreBackend::backend_metric_snapshot`], whose
/// `cuda_timed_enqueue_ns_total`, `cuda_timed_device_ns_total` and
/// `cuda_timed_wait_ns_total` counters cover exactly the dispatches this phase
/// wraps. A caller wanting that split reads it there. Inventing one here would
/// be a plausible mechanism presented as a measurement, which is the failure
/// this type exists to prevent.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum EncodePhase {
    /// [`pretokens`] over every input into the session's span buffer, with the
    /// gapless-tiling check folded into the same pass.
    Pretokenize,
    /// Each pretoken's bytes turned into its byte-level start state through
    /// [`DeviceTokenizer::byte_token`], appended to the encode's flat state
    /// buffer.
    ///
    /// One `Vec<u32>` per pretoken until that buffer replaced it, which made the
    /// phase a malloc per pretoken and nothing else: it scaled with the pretoken
    /// COUNT rather than with the bytes mapped, which is why the same 262144
    /// input bytes cost 1.053 ms as prose and 2.359 ms as short pretokens. The
    /// mapping itself is an index into the 256-entry table
    /// [`DeviceTokenizer::new`] builds once, and never was the cost.
    ByteEncode,
    /// The [`MergeState`] merge of the pretokens past [`MAX_PRETOKEN_TOKENS`]
    /// that the host encodes. Zero on any input whose pretokens all fit.
    HostEncode,
    /// [`DeviceTokenizer::workgroups_per_dispatch`]. A bisection over the
    /// backend's geometry predicate on the first encode, a cached load after.
    ResidencyQuery,
    /// [`pack_u32_slice`] over the merge table's slot words, the 16 MiB wire
    /// copy. First encode only: the result lives in a `OnceLock`.
    ///
    /// ZERO on a [`DeviceSession`] encode, and not merely near zero. The pack
    /// happened at [`DeviceTokenizer::bind`] and the session HOLDS the bytes, so an
    /// encode does not even reach the initialized cell: that load is cheap, but a
    /// row reading a few hundred nanoseconds instead of nothing would invite a
    /// reader to ask what work a session is still doing on a table it already
    /// packed.
    TablePack,
    /// Allocating and uploading the resident merge table.
    ///
    /// Once per encode on [`DeviceTokenizer::encode_batch`], which takes the
    /// backend per call and so cannot keep a handle to it. ZERO on a
    /// [`DeviceSession`] encode, where the upload happened once at
    /// [`DeviceTokenizer::bind`] and no encode repeats it. The row is kept rather
    /// than deleted precisely so both paths report in one table and a reader can
    /// see which one an encode took.
    TableUpload,
    /// [`batches`]: grouping pretokens into dispatches by length.
    Batching,
    /// Per dispatch: the `Vec<&[u32]>` of that batch's pretokens and the scan
    /// for its longest, which sets the pass budget.
    CallerInputs,
    /// Per dispatch: the padded state array, built by [`LoopBatch::new`] on an
    /// encode's first dispatch and rewritten in place by [`LoopBatch::reseed`]
    /// on every later one, so the allocation is paid once per encode.
    LoopBatchBuild,
    /// Per dispatch: [`DeviceTokenizer::dispatch_plan`], a cache hit or the
    /// emission of a program for a shape not seen before.
    PlanLookup,
    /// Per dispatch: [`run_device_loop_borrowed`]. Holds `gpu_loop`'s harness
    /// marshalling, vyre's host path and the device kernel together; see the
    /// type doc for why this module does not split it.
    Dispatch,
    /// Per dispatch: copying each segment's converged tokens out of the
    /// [`LoopOutcome`] into the encode's flat id buffer.
    ///
    /// A `Vec<u32>` per segment until that buffer replaced it, one allocation per
    /// device pretoken on top of the one [`Self::ByteEncode`] made.
    OutputAssembly,
    /// Freeing the resident merge table.
    ///
    /// Once per encode on [`DeviceTokenizer::encode_batch`], and ZERO on a
    /// [`DeviceSession`] encode: the table lives as long as the session, and
    /// [`DeviceSession::close`] or the session's [`Drop`] gives it back. See
    /// [`Self::TableUpload`].
    TableFree,
    /// Concatenating each input's pretoken runs into its `Vec<TokenId>`.
    IdAssembly,
    /// Releasing the buffers an encode worked in.
    ///
    /// A phase of its own because it is a real cost that no other row can hold
    /// honestly, and it is where the two entry points differ most.
    /// [`DeviceTokenizer::encode_batch`] builds its buffers per call and gives
    /// them back here; that used to be two `Vec<u32>` per device pretoken,
    /// measured at 22.94 ns per pretoken on prose, which on a corpus of a hundred
    /// thousand short pretokens is hundreds of thousands of frees. A
    /// [`DeviceSession`] keeps the buffers instead, so the row holds only the
    /// emptying of the flat ones, whose capacity the next encode reuses, plus the
    /// pool round trip that hands them to it.
    ///
    /// Charged at the START of an encode rather than at the end of the one
    /// before, because that is the only point every path reaches: an encode that
    /// returned an error must not leave a scratch holding runs into words that a
    /// later encode on the same session never wrote.
    Teardown,
}

impl EncodePhase {
    /// Every phase, in the order the encode reaches them.
    ///
    /// The array is the single statement of how many phases there are:
    /// [`EncodeProfile`] sizes its storage from it and indexes with
    /// [`Self::index`], so adding a variant without adding it here fails to
    /// compile at the exhaustive match rather than silently reporting zero.
    pub const ALL: [Self; 15] = [
        Self::Pretokenize,
        Self::ByteEncode,
        Self::HostEncode,
        Self::ResidencyQuery,
        Self::TablePack,
        Self::TableUpload,
        Self::Batching,
        Self::CallerInputs,
        Self::LoopBatchBuild,
        Self::PlanLookup,
        Self::Dispatch,
        Self::OutputAssembly,
        Self::TableFree,
        Self::IdAssembly,
        Self::Teardown,
    ];

    /// Slot this phase occupies in [`Self::ALL`].
    ///
    /// An exhaustive match rather than a cast, so the discriminant order and the
    /// array order cannot drift apart: a variant added to one and not the other
    /// stops compiling.
    #[must_use]
    pub const fn index(self) -> usize {
        match self {
            Self::Pretokenize => 0,
            Self::ByteEncode => 1,
            Self::HostEncode => 2,
            Self::ResidencyQuery => 3,
            Self::TablePack => 4,
            Self::TableUpload => 5,
            Self::Batching => 6,
            Self::CallerInputs => 7,
            Self::LoopBatchBuild => 8,
            Self::PlanLookup => 9,
            Self::Dispatch => 10,
            Self::OutputAssembly => 11,
            Self::TableFree => 12,
            Self::IdAssembly => 13,
            Self::Teardown => 14,
        }
    }

    /// One column-width name for a report row.
    #[must_use]
    pub const fn label(self) -> &'static str {
        match self {
            Self::Pretokenize => "pretokenize",
            Self::ByteEncode => "byte_encode",
            Self::HostEncode => "host_encode",
            Self::ResidencyQuery => "residency_query",
            Self::TablePack => "table_pack",
            Self::TableUpload => "table_upload",
            Self::Batching => "batching",
            Self::CallerInputs => "caller_inputs",
            Self::LoopBatchBuild => "loop_batch",
            Self::PlanLookup => "plan_lookup",
            Self::Dispatch => "dispatch",
            Self::OutputAssembly => "output_assembly",
            Self::TableFree => "table_free",
            Self::IdAssembly => "id_assembly",
            Self::Teardown => "teardown",
        }
    }
}

/// What one encode did, in units that do not move with machine load.
///
/// Reported beside the durations because a wall taken on a contended box is not
/// reproducible and these are: the same input produces the same counts on an
/// idle machine and on a loaded one. A per-unit rate computed from a duration
/// and one of these replicates across box states where the duration alone does
/// not.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
struct EncodeCounts {
    device_pretokens: usize,
    host_pretokens: usize,
    input_bytes: usize,
    table_bytes: usize,
    output_ids: usize,
}

/// Host time an encode spent in each named component, with what it did.
///
/// Returned by [`DeviceTokenizer::encode_batch_profiled`] rather than stashed on
/// the tokenizer, for the reason [`Routing`] is returned: `encode_batch` takes
/// `&self`, so two concurrent encodes would overwrite one stashed profile and a
/// reader would attribute one call's cost to another.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct EncodeProfile {
    elapsed: [Duration; EncodePhase::ALL.len()],
    total: Duration,
    dispatches: usize,
    state_words: usize,
    counts: EncodeCounts,
}

impl EncodeProfile {
    /// Host time charged to one phase, summed over every time the encode
    /// entered it.
    #[must_use]
    pub const fn phase(&self, phase: EncodePhase) -> Duration {
        self.elapsed[phase.index()]
    }

    /// Every named phase added up.
    #[must_use]
    pub fn named(&self) -> Duration {
        self.elapsed.iter().sum()
    }

    /// The whole call, measured around everything [`Self::named`] measures
    /// inside.
    #[must_use]
    pub const fn total(&self) -> Duration {
        self.total
    }

    /// What the named phases did NOT account for.
    ///
    /// Saturating rather than wrapping, because the clock reads that bound the
    /// phases sit inside the one that bounds the call and so cannot exceed it,
    /// but a coarse clock can round them to equal. A saturating difference
    /// reports zero there; a wrapping one would report several hundred years.
    #[must_use]
    pub fn unattributed(&self) -> Duration {
        self.total.saturating_sub(self.named())
    }

    /// Dispatches this encode issued.
    #[must_use]
    pub const fn dispatches(&self) -> usize {
        self.dispatches
    }

    /// Padded state words summed over every dispatch, which is the volume
    /// [`EncodePhase::LoopBatchBuild`] wrote and [`EncodePhase::Dispatch`]
    /// moved.
    #[must_use]
    pub const fn state_words(&self) -> usize {
        self.state_words
    }

    /// Pretokens the device encoded.
    #[must_use]
    pub const fn device_pretokens(&self) -> usize {
        self.counts.device_pretokens
    }

    /// Pretokens the host encoded, past [`MAX_PRETOKEN_TOKENS`].
    #[must_use]
    pub const fn host_pretokens(&self) -> usize {
        self.counts.host_pretokens
    }

    /// Input bytes, which is also the start-state words
    /// [`EncodePhase::ByteEncode`] wrote: merging starts one token per byte and
    /// the spans tile the input.
    #[must_use]
    pub const fn input_bytes(&self) -> usize {
        self.counts.input_bytes
    }

    /// Wire bytes of the uploaded merge table, or zero when the encode reached
    /// no device work.
    #[must_use]
    pub const fn table_bytes(&self) -> usize {
        self.counts.table_bytes
    }

    /// Token ids returned.
    #[must_use]
    pub const fn output_ids(&self) -> usize {
        self.counts.output_ids
    }
}

/// Something an encode can tell how long each of its phases took.
///
/// A trait with a do-nothing implementation rather than an `Option<&mut _>` the
/// path checks, so [`DeviceTokenizer::encode_batch`] pays NOTHING for the
/// instrumentation: [`Untimed::measure`] is a call to its own argument, and
/// monomorphization leaves no clock read, no branch and no counter behind. An
/// `Option` would leave a test per phase and per dispatch on a path whose whole
/// design is about not paying per-pretoken and per-dispatch costs, and a
/// profiler that slows the thing it profiles reports its own overhead.
///
/// Both implementations run the SAME body through the same generic function, so
/// a profiled encode cannot take a different path from a plain one and the ids
/// are identical by construction rather than by testing.
trait PhaseProbe: Sized {
    /// Run `body` and charge what it took to `phase`.
    ///
    /// `body` is handed the probe back, so a phase that CONTAINS another can
    /// measure it: whatever the inner call charges is deducted from the outer
    /// one, and the two stay disjoint leaves that add. That is what keeps the
    /// table summable when the code nests. The host route is the case that
    /// needs it: [`MergeState::run`] is [`crate::incremental`]'s merge loop and
    /// the walk around it is this module's marshalling, two owners, and the
    /// inner one cannot be lifted out of the walk without traversing the spans
    /// twice, which would change the very cost being measured.
    fn measure<T>(&mut self, phase: EncodePhase, body: impl FnOnce(&mut Self) -> T) -> T;

    /// One dispatch went out, over `state_words` padded state words.
    fn dispatched(&mut self, state_words: usize);

    /// What the whole encode worked on, known only once it is done.
    fn counted(&mut self, counts: EncodeCounts);
}

/// The shipping path's probe: measures nothing and compiles to nothing.
struct Untimed;

impl PhaseProbe for Untimed {
    #[inline]
    fn measure<T>(&mut self, _phase: EncodePhase, body: impl FnOnce(&mut Self) -> T) -> T {
        body(self)
    }

    #[inline]
    fn dispatched(&mut self, _state_words: usize) {}

    #[inline]
    fn counted(&mut self, _counts: EncodeCounts) {}
}

/// The measuring probe, which becomes an [`EncodeProfile`].
struct Timed {
    started: Instant,
    /// Everything charged to any phase so far.
    ///
    /// One running total and not a per-phase discount array, because that is
    /// all a nested measurement needs: the time an outer body must give back is
    /// exactly how much this figure moved while that body ran, whatever phases
    /// the inner calls named and however deep they went.
    charged: Duration,
    profile: EncodeProfile,
}

impl Timed {
    /// Start the call-level clock. Everything after this point is inside
    /// [`EncodeProfile::total`].
    fn start() -> Self {
        Self {
            started: Instant::now(),
            charged: Duration::ZERO,
            profile: EncodeProfile {
                elapsed: [Duration::ZERO; EncodePhase::ALL.len()],
                total: Duration::ZERO,
                dispatches: 0,
                state_words: 0,
                counts: EncodeCounts::default(),
            },
        }
    }

    /// Stop the call-level clock and take the profile.
    fn finish(mut self) -> EncodeProfile {
        self.profile.total = self.started.elapsed();
        self.profile
    }
}

impl PhaseProbe for Timed {
    fn measure<T>(&mut self, phase: EncodePhase, body: impl FnOnce(&mut Self) -> T) -> T {
        let before = self.charged;
        let started = Instant::now();
        let value = body(self);
        let elapsed = started.elapsed();
        // Saturating both ways. A nested body cannot outlast the body enclosing
        // it, but the two clock reads bracketing the inner one sit inside the
        // outer bracket and a coarse clock can round them to equal, which would
        // otherwise wrap a `Duration` to several hundred years.
        let own = elapsed.saturating_sub(self.charged.saturating_sub(before));
        self.profile.elapsed[phase.index()] += own;
        self.charged += own;
        value
    }

    fn dispatched(&mut self, state_words: usize) {
        self.profile.dispatches += 1;
        self.profile.state_words += state_words;
    }

    fn counted(&mut self, counts: EncodeCounts) {
        self.profile.counts = counts;
    }
}

// ---------------------------------------------------------------------------
// The buffers an encode works in
// ---------------------------------------------------------------------------

/// A run of words inside one of an encode's flat buffers.
///
/// Offsets and not slices, deliberately: a run is recorded while the buffer it
/// names is still growing, and a `Vec` moves its block when it reallocates, so a
/// borrow taken at that moment would either dangle or forbid the growth. An
/// offset survives every reallocation and costs the same to read.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
struct Run {
    start: usize,
    len: usize,
}

impl Run {
    /// A pretoken whose ids are not written yet.
    ///
    /// Pushed for every device-bound pretoken so [`Scratch::id_runs`] holds one
    /// slot per pretoken in PRETOKEN order, and filled in after the dispatch that
    /// converges it: batches are grouped by length, so segments come back in an
    /// order that is not the input's.
    const EMPTY: Self = Self { start: 0, len: 0 };

    /// Append `words` to `flat` and name where they landed.
    fn append(flat: &mut Vec<u32>, words: &[u32]) -> Self {
        let start = flat.len();
        flat.extend_from_slice(words);
        Self {
            start,
            len: words.len(),
        }
    }

    /// The words this run names inside `flat`.
    fn of(self, flat: &[u32]) -> &[u32] {
        &flat[self.start..self.start + self.len]
    }
}

/// Everything one encode writes that is not its answer, reusable by the next.
///
/// Two flat buffers and their runs, replacing the `Vec<u32>` this path used to
/// materialize twice per pretoken: once for the byte-level start state and once
/// for the converged tokens. That was two allocations and two frees per
/// pretoken, 122194 allocator calls on a 262144-byte prose encode, and about
/// 4.4 ms of measured host time spread over [`EncodePhase::ByteEncode`],
/// [`EncodePhase::OutputAssembly`], [`EncodePhase::IdAssembly`] and
/// [`EncodePhase::Teardown`].
///
/// Flat rather than a pool of reused `Vec<u32>`s. Reusing the vectors keeps the
/// indirection and the per-pretoken bookkeeping and only avoids the malloc,
/// while one buffer plus offsets removes the per-pretoken allocation outright
/// and hands each dispatch a contiguous region to slice.
///
/// Held by a [`DeviceSession`] and never by a [`DeviceTokenizer`]: a tokenizer
/// is shared across backends and threads by design, and one shared scratch
/// would interleave two concurrent encodes' words in one array and answer each
/// with the other's ids. A session hands one set to one encode; see
/// [`SCRATCH_POOL_LIMIT`].
#[derive(Debug, Default)]
struct Scratch {
    /// Byte-level start states of the DEVICE-bound pretokens, back to back.
    state: Vec<u32>,
    /// One run per device-bound pretoken, into [`Self::state`], in the order the
    /// walk found them. This is also the list [`batches`] groups.
    state_runs: Vec<Run>,
    /// Converged ids of every pretoken, host-routed and device alike, in the
    /// order they were produced rather than in pretoken order.
    ids: Vec<u32>,
    /// One run per pretoken, into [`Self::ids`], in PRETOKEN order, which is the
    /// order [`EncodePhase::IdAssembly`] reads. That is what lets the ids buffer
    /// be filled out of order and never sorted.
    id_runs: Vec<Run>,
    /// Which [`Self::id_runs`] slot each device-bound pretoken owns.
    device_slot: Vec<usize>,
    /// The host route's start state, in the form [`MergeState::load`] takes.
    host_state: Vec<TokenId>,
    /// The host route's merge state, reused across every host pretoken of an
    /// encode and, through the session pool, across encodes.
    ///
    /// [`crate::reference::encode_pretoken`] ran this route before: one fresh
    /// `Vec` per pretoken and a full pair rescan per merge, 1673 pair-table
    /// lookups on the 604-byte cl100k corpus where maintained ranks need 906
    /// (`tests/incremental_merge.rs` pins both numbers against each other).
    /// [`MergeState::load`] replaces the sequence wholesale, so nothing
    /// carries between pretokens except the buffers and the lookup counters,
    /// and a warm session pays no allocation per host pretoken. The counters
    /// are what [`DeviceTokenizer::host_merge_tally`] publishes.
    host_merge: MergeState,
    /// Pretoken spans of the input currently being walked.
    ///
    /// Reused across inputs AND across encodes, where the old path collected a
    /// fresh `Vec<Span>` per input: the spans describe only the walk's current
    /// input and are consumed before the next one is split, so one buffer at
    /// the widest input's capacity serves the whole session. Taken out of the
    /// scratch for the duration of one input's walk and put back after it,
    /// because the walk's byte-encode half borrows the rest of the scratch
    /// mutably while it reads the spans.
    spans: Vec<Span>,
}

impl Scratch {
    /// Empty every buffer, keeping the capacity a previous encode grew.
    fn reset(&mut self) {
        self.state.clear();
        self.state_runs.clear();
        self.ids.clear();
        self.id_runs.clear();
        self.device_slot.clear();
        self.host_state.clear();
        self.spans.clear();
    }

    /// Append one device-bound pretoken's byte-level start state.
    ///
    /// The state IS the bytes mapped through `byte_token`, one token per byte,
    /// which is exactly why a caller can route on `bytes.len()` before calling
    /// this and never build a state it would throw away.
    fn push_start_state(&mut self, bytes: &[u8], byte_token: &[TokenId; 256]) {
        let start = self.state.len();
        self.state
            .extend(bytes.iter().map(|byte| byte_token[*byte as usize].0));
        self.state_runs.push(Run {
            start,
            len: bytes.len(),
        });
    }

    /// Encode one over-cap pretoken on the host and append its ids.
    ///
    /// Straight into the flat buffer: no `Vec<u32>` start state and no second
    /// `Vec` for the result, so the two buffers this route needs are
    /// [`Self::host_state`], which [`MergeState::load`] wants as [`TokenId`],
    /// and [`Self::host_merge`], whose columns keep their capacity across
    /// pretokens.
    ///
    /// The merge is [`crate::incremental`]'s maintained-rank loop, not
    /// [`crate::reference::encode_pretoken`]'s full rescan: only the two pairs
    /// adjacent to each merge site are re-looked-up, which the incremental
    /// suite pins byte-identical to the reference at roughly half the lookups
    /// per byte, and asymptotically better on collapsing runs where the
    /// rescan is quadratic. The sentinel precondition holds by construction:
    /// [`RankTable::from_entries`] rejects a [`Rank::ABSENT`] rank at build,
    /// so no real merge hides at the value the maintained minimum reduction
    /// reads as "no pair".
    fn push_host_ids(
        &mut self,
        bytes: &[u8],
        byte_token: &[TokenId; 256],
        table: &impl MergeTable,
    ) -> Run {
        self.host_state.clear();
        self.host_state
            .extend(bytes.iter().map(|byte| byte_token[*byte as usize]));
        self.host_merge.load(&self.host_state, table);
        self.host_merge.run(table);
        let start = self.ids.len();
        self.ids.extend(self.host_merge.tokens().iter().map(|id| id.0));
        Run {
            start,
            len: self.ids.len() - start,
        }
    }
}

/// Append `spans` to `out`, asserting AS EACH ONE ARRIVES that it starts where
/// the previous one ended and that the last one ends at `input_len`.
///
/// The spans must tile the input: a gap would silently drop bytes and both the
/// device and the host reference would agree on the wrong answer. An assertion
/// rather than an error because no input can provoke it; it is
/// `pretokenize`'s own published contract that the spans are contiguous and
/// gapless, so a failure here is a defect in that module and not a caller's
/// problem.
///
/// Folded into production, where the check used to be a second pass over the
/// collected spans: the running end telescopes through the iterator, so the
/// verification costs the comparisons the pass already makes and no walk of
/// its own. The span source is a parameter rather than a pattern plus input
/// so the batching-order suite can feed a broken stream to the negative
/// control; the encode path passes `pretokens(pattern, input)`.
///
/// # Panics
///
/// Panics on the first span that does not start where its predecessor ended,
/// or when the final end is not `input_len`.
pub fn extend_tiling_spans(
    input_len: usize,
    spans: impl IntoIterator<Item = Span>,
    out: &mut Vec<Span>,
) {
    let mut end = 0_usize;
    out.extend(spans.into_iter().inspect(|span| {
        assert_eq!(
            span.start, end,
            "pretoken spans must be contiguous and gapless over the input: span \
             {}..{} starts where the previous span ended at {}",
            span.start, span.end, end
        );
        end = span.end;
    }));
    assert_eq!(
        end, input_len,
        "pretoken spans must be contiguous and gapless over the input: the last \
         span ends at {end} of {input_len} bytes"
    );
}

/// [`Scratch`] sets a [`DeviceSession`] keeps between encodes.
///
/// A session hands one set to one encode and takes it back, so concurrent
/// encodes on a shared session never share buffers and never serialize behind
/// one: the pool lock is held only to pop and to push, never across a dispatch.
///
/// Bounded because a set retains the capacity of the largest encode that used
/// it, and an unbounded pool would keep one such set per thread that ever
/// encoded concurrently, forever. Four covers the concurrency a tokenizer
/// actually sees while capping the retained capacity at four encodes' worth; a
/// fifth concurrent encode allocates a set for itself and drops it rather than
/// growing the pool, which costs that encode what an unbound call already pays
/// and costs a steady-state caller nothing.
const SCRATCH_POOL_LIMIT: usize = 4;

/// Where an encode's merge table comes from.
///
/// Two arms because the two entry points differ in exactly this one place and
/// nowhere else: they run the same body over the same buffers through the same
/// generic function, so a session cannot take a different path and cannot return
/// different ids.
#[derive(Clone, Copy)]
enum TableSource<'a> {
    /// A [`DeviceSession`]'s table, packed and uploaded once at
    /// [`DeviceTokenizer::bind`].
    ///
    /// Both halves come from the session, which is why a session encode enters
    /// neither [`EncodePhase::TablePack`] nor [`EncodePhase::TableUpload`]: it has
    /// nothing to do in either. `table` is `None` when the backend has no resident
    /// dispatch, where `bytes` is an ordinary host input exactly as on the unbound
    /// path, and `bytes` is non-empty either way because a dispatch needs the table
    /// wherever it sits.
    Session {
        table: Option<&'a Resource>,
        bytes: &'a [u8],
    },
    /// No session: pack on first touch, allocate and upload for this call, and free
    /// before it returns.
    PerCall,
}

// ---------------------------------------------------------------------------
// The public tokenizer
// ---------------------------------------------------------------------------

/// Everything one dispatch needs that depends on its SHAPE and nothing else.
///
/// Both members are pure functions of [`LoopShape`] plus the table's capacity
/// and probe window, and a tokenizer's table never changes, so a plan is
/// reusable by every dispatch that lands on the same shape. Held together in one
/// value because they are cached and handed out together; splitting them into two
/// caches would let a program and a pick seed built for different segment counts
/// meet at a dispatch.
#[derive(Debug)]
struct DispatchPlan {
    /// The emitted merge program for this shape.
    ///
    /// Reused rather than rebuilt, and the reuse buys more than the IR: a
    /// `Program` caches its own blake3 hash and its per-backend validation
    /// verdict internally, so a fresh one per dispatch re-hashed and re-validated
    /// the whole program before every launch.
    ///
    /// THE HASH SAVING IS GUARANTEED, THE VALIDATION SAVING IS A BEST CASE, and
    /// the difference is worth knowing before anyone treats this as a throughput
    /// contract. The hash memo is per instance. The validation verdict is not: it
    /// lives in a `DashSet` that `Program::clone` shares by `Arc`, and any
    /// clone-then-mutate anywhere in the process clears it for every plan sharing
    /// that set, including these. The plan cache still hits and the ids stay
    /// correct, so the only cost is paying validation again, and no gate in this
    /// crate can observe it. The sharing is deliberately the safe direction:
    /// mutating either side over-invalidates and causes a spurious
    /// re-validation, never a skipped one, and a stale verdict cannot outlive a
    /// shape change because the lookup is keyed on a shape-derived validation
    /// key. So this is a throughput leak and never an exactness one.
    program: Program,
    /// Packed [`NAME_BPE_PICK`] seed for this shape's segment count.
    pick_seed: Vec<u8>,
}

impl DispatchPlan {
    /// Host bytes this plan holds while it sits in the cache.
    ///
    /// The cache's eviction weight, so it decides both what fits and what goes.
    ///
    /// Read from the emitted program rather than predicted from the shape.
    /// `node_count` is the exact statement count of the IR this plan actually
    /// carries, cached inside `Program` behind a `OnceLock` and so walked once per
    /// plan and never again, which means the weight follows a change to
    /// [`bpe_merge_body`] instead of going stale against it. Predicting from
    /// `max_passes` alone would hardcode today's 132 nodes per pass and would
    /// silently mis-size the cache the first time the pass body grew.
    ///
    /// The seed is added at its true length, not estimated: it is 8 bytes per
    /// segment and it DOMINATES a wide shallow plan, which is exactly the entry a
    /// pass-weighted bound charged almost nothing for.
    fn retained_bytes(&self) -> usize {
        self.program
            .stats()
            .node_count
            .saturating_mul(PLAN_BYTES_PER_IR_NODE)
            .saturating_add(self.pick_seed.len())
    }
}

/// Retained host bytes one emitted IR node of a plan costs.
///
/// PROBED on this box, and load independent because it is a residency figure
/// rather than a duration. Sixteen fresh 256-pass plans were built and held while
/// `/proc/self/statm` was read either side, three times in one process: resident
/// growth was 187981824 then 187949056 bytes, which is 11748864 and 11746816 bytes
/// per plan over `Program::stats().node_count` of 33794 nodes each, 347.5 and
/// 347.5 bytes per node. Rounded UP to 348, so the weight never under-charges an
/// entry and the ceiling below is never quietly exceeded.
///
/// Two earlier single-round readings on the same fixture came in lower, at 326 and
/// 348 bytes per node, and they are the ones to distrust rather than average in:
/// resident growth UNDER-reports when the process has already freed pages the
/// allocator can hand back, which is exactly the state a first round sits in. The
/// two rounds quoted above were taken after that slack was consumed and they agree
/// to within 0.02 percent, so the figure is the settled one.
///
/// Larger than `size_of::<Node>()`, which is 176 bytes, because a node owns a
/// boxed expression tree and the `Vec`s that hold its children; the walk that
/// produced `node_count` counts statements, not the allocations hanging off
/// them.
const PLAN_BYTES_PER_IR_NODE: usize = 348;

/// Retained host bytes the plan cache may hold across every entry.
///
/// A bound is REQUIRED, not tidiness. A tokenizer takes `&self` and lives as long
/// as its caller, batch shape varies with the longest pretoken in the batch, and
/// the key space is every (segments, capacity, budget) triple a corpus can
/// produce, so a map keyed on shape grows with corpus diversity forever.
///
/// Weighted in BYTES rather than in pass waves, and the difference is not
/// cosmetic. An earlier revision bounded the SUM of cached shapes' pass budgets
/// at 128, and that number was a CLIFF rather than a cost. One encode's working
/// set is the distinct shapes its batch plan produces, each shape is dispatched
/// once, and the next encode of the same bytes asks for exactly the same set in
/// exactly the same order. So a ceiling below that working set gives a CYCLIC
/// access pattern over a too-small cache, which no eviction order can rescue:
/// every entry is evicted before it is asked for again and the hit rate is zero.
/// Counted on the four bench corpora, 262144 bytes each, one encode's working
/// set against the old 128-pass ceiling was `short_pretokens` 2 shapes summing
/// to 5 passes and `prose` 4 shapes summing to 50, both of which fit and reused
/// every plan after the first encode, against `cjk` 6 shapes summing to 189 and
/// `code` 6 shapes summing to 179, neither of which fits: those two rebuilt ALL
/// SIX plans on EVERY encode, measured as 6 misses and 0 hits per encode over
/// four consecutive encodes. That is the three-orders-of-magnitude
/// [`EncodePhase::PlanLookup`] split between shapes, 5.0030 ms on `cjk` against
/// 0.0009 ms on `prose`.
///
/// Bytes rather than passes also because passes were the wrong proxy in a second
/// way: they ignore [`DispatchPlan::pick_seed`], which is 8 bytes per segment and
/// so 783360 bytes for the widest shallow dispatch this module admits, against
/// the 92568 bytes such a plan's two-pass program costs. A pass-weighted cache
/// under-charged that entry by a factor of nine.
///
/// The figure. An ordinary corpus spans doubling length bands, so its budgets
/// come from the nine bands over the admissible pretoken range, at most 256 since
/// [`MAX_PRETOKEN_TOKENS`] is 255, and each band contributes its full batches plus
/// one partial one. Two entries per band at each band's widest budget is
/// `2 * (256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1)`, 1022 passes, and a pass of
/// this pass body is 132 IR nodes, so 46946592 bytes; sixteen worst-case seeds
/// add 12533760. That is 59.5 MB, and 64 MiB admits it with 7.6 MB spare. The four
/// bench corpora together need 21.2 MB of it, DERIVED from their probed shapes and
/// the probed per-node figure above, so the ceiling carries three times what the
/// measured worst corpus asks for.
///
/// Worst-case residency is the ceiling plus the one entry inserted before the
/// sweep runs, and a single plan cannot exceed 256 passes, so 64 MiB + 11.76 MB
/// transiently and 64 MiB at rest. Against the 32 MiB the tokenizer already holds
/// for the merge table and its packed copy.
const PLAN_CACHE_BYTES: usize = 64 << 20;

/// A vocabulary's merge table, built once and reused by every encode.
///
/// Building the table is the expensive part of GPU tokenization and it depends
/// only on the vocabulary, so it happens exactly once in [`Self::new`]. Nothing
/// on the encode path rebuilds or re-derives it.
///
/// `encode` takes `&self` so one tokenizer serves concurrent callers. The
/// dispatch tally is therefore an atomic rather than a `Cell`, which keeps this
/// type `Sync`; a `Cell` would have made a shared tokenizer impossible for the
/// sake of a counter.
#[derive(Debug)]
pub struct DeviceTokenizer {
    encoding: Encoding,
    table: RankTable,
    /// Id of every single-byte token, resolved once.
    ///
    /// The crate's single statement of the byte-level start state, from
    /// [`byte_token_ids`], held so encoding indexes an array instead of hashing
    /// every input byte.
    byte_token: [TokenId; 256],
    batching: Batching,
    dispatches: AtomicUsize,
    /// This device's cooperative block ceiling, PER BACKEND, queried on first use.
    ///
    /// KEYED ON THE BACKEND, because the value is a property of the backend and of
    /// the compiled pass body, never of this tokenizer. An unkeyed `OnceLock` here
    /// supplied zero bits about the only input the answer depends on: bind one
    /// tokenizer to CUDA and then to the reference backend and the second was
    /// handed the first's ceiling. Neither direction moved a token id, which is
    /// why it was invisible, and the two failure modes are not symmetric. A CUDA
    /// ceiling handed to the reference backend is refused loudly at launch. The
    /// reference backend's zero handed to CUDA pins every dispatch to ONE
    /// workgroup forever and still computes correct ids, so every exactness gate
    /// stays green while the device runs at a fraction of its width. A cheaper
    /// ceiling or a third backend turns that case into a wrong id.
    ///
    /// [`VyreBackend::id`] is documented unique among the backends linked into a
    /// process, so it is the whole key. A `Vec` rather than a map because the
    /// count is the number of backends one process binds, which is one or two.
    ///
    /// Cached at all because recovering the ceiling costs a bisection over the
    /// backend's geometry predicate, a run of queries that would otherwise repeat
    /// on every encode.
    ///
    /// A plain `Vec::new()`. This field was briefly `Vec::with_capacity(2)`, to
    /// move the first-push allocation out of the first encode while a cost flake
    /// was suspected to live in this vector. The suspicion was ruled out: the
    /// flake is vyre's process-global resident pool finishing its warmup, and
    /// `tests/encode_cost.rs` now warms to a flat cost window before measuring,
    /// so a first-encode allocation is invisible to it regardless. The capacity
    /// hint was reverted with the concern that motivated it; the decision is
    /// recorded in INNOVATIONS.md.
    block_ceilings: RwLock<Vec<(&'static str, u32)>>,
    /// The merge table packed into wire bytes, on first dispatch.
    ///
    /// [`RankTable`] is built in [`Self::new`] and never mutates, so packing it
    /// per dispatch was a 16 MiB memcpy that produced a byte-identical buffer
    /// every time: `cl100k_base` charged 2.09 copies of the table to each
    /// dispatch, on a path whose whole purpose is to avoid host work.
    ///
    /// A `OnceLock` for the same reason [`Self::block_ceiling`] is one, and NOT a
    /// `LazyLock`: the initializer needs `self.table`, which a field-level
    /// `LazyLock` cannot reach.
    ///
    /// Deferred rather than packed eagerly in [`Self::new`]. Eager is simpler,
    /// but it would charge every tokenizer a second 16 MiB whether or not it ever
    /// reaches the device, and an encode with no device work pays no device cost
    /// here: a caller whose pretokens all exceed [`MAX_PRETOKEN_TOKENS`] never
    /// dispatches and must not carry a buffer no dispatch uploads. Deferring
    /// keeps that true and costs one initialized load per dispatch after the
    /// first.
    table_bytes: OnceLock<Vec<u8>>,
    /// Emitted programs, keyed on the shape they were built for.
    ///
    /// A plain hoist would be wrong: shape varies per dispatch, so one program
    /// cannot serve a corpus. Keyed on the whole shape instead, and bounded by
    /// [`PLAN_CACHE_BYTES`]; see there for why the bound is in bytes and why the
    /// figure is what it is.
    ///
    /// An `RwLock` and not a `Mutex`, because `encode_batch` takes `&self` and is
    /// exercised concurrently. A hit takes the READ lock, finds the entry and
    /// clones an `Arc`, which allocates nothing and lets concurrent encodes
    /// proceed together; only a miss takes the write lock, and only to insert,
    /// never to build.
    ///
    /// A `Vec` scanned linearly rather than a map, because the bound keeps it to a
    /// few dozen entries and a `LoopShape` comparison is three `u32`s: a hash of
    /// the same key costs more than the scan it would replace.
    ///
    /// Eviction takes the CHEAPEST entry to rebuild first, measured by
    /// [`DispatchPlan::retained_bytes`], and on overflow a dispatch whose shape was
    /// dropped rebuilds it, paying exactly what every dispatch paid before this
    /// cache existed and never more. So the worst case is today's cost, and the
    /// cache cannot turn into a leak. Oldest-first was tried and measured to be
    /// the pathological order; see the sweep in [`Self::dispatch_plan`].
    plans: RwLock<Vec<(LoopShape, Arc<DispatchPlan>)>>,
    /// Dispatches that reused a cached plan, and those that had to build one.
    ///
    /// Kept because the allocation gates cannot tell a working cache from a
    /// broken one. A cache that missed on every dispatch would still cut the
    /// FIRST dispatch's cost and would still return byte-identical ids, so every
    /// correctness suite and every "calls added per dispatch" delta would look
    /// the same as a cache that hits. Only the ratio separates them, so it is
    /// counted rather than assumed.
    ///
    /// A miss is charged where the construction happens, so these answer
    /// precisely "how many dispatches avoided emitting a program". The rare
    /// double-build, where two threads miss the same shape at once and one
    /// discards its work, is charged as a miss by both: it did pay.
    plan_hits: AtomicUsize,
    plan_misses: AtomicUsize,
    /// Plans CONSTRUCTED after a cache miss, since this tokenizer was created.
    ///
    /// Separate from `plan_misses` in name because the two answer different
    /// questions. A miss says the cache was asked and did not have the shape;
    /// this says a build was PAID, charged where the construction happens, so
    /// eviction-driven rebuilds and the rare double-build race count here
    /// exactly as many times as they cost. The published accessor is
    /// [`Self::plan_rebuilds`], which exists for tests and cost accounting.
    plan_rebuilds: AtomicU64,
    /// Output-assembly convergence checks, one per dispatch, and per-segment
    /// guard queries, since this tokenizer was created.
    ///
    /// The proving counters of the batch-hoisted output assembly. A converged
    /// dispatch answers ONE batch-level question (`output_batch_checks` up by
    /// one) and asks nothing per segment; only a dispatch that exhausted its
    /// pass budget falls back to the per-segment path, and every segment it
    /// queries adds one to `output_segment_guards`. The pair separates the two
    /// paths exactly: an encode of D converged dispatches and P device
    /// pretokens moves the first by D and the second by 0, where the assembly
    /// this replaced moved the per-segment count by P.
    ///
    /// Counters rather than assumptions, for the same reason `plan_hits`
    /// exists: a fast path that silently never ran would return byte-identical
    /// ids, so every correctness suite would stay green while the per-segment
    /// cost the hoist removed was still being paid.
    output_batch_checks: AtomicU64,
    output_segment_guards: AtomicU64,
    /// Pair-table lookups and merges the host route has issued since this
    /// tokenizer was created.
    ///
    /// The proving counters of the host arm's maintained-rank merge. The per
    /// lookup counting happens inside the scratch [`MergeState`]'s own
    /// counters, which cost no instrumentation, and each completed input adds
    /// its delta here: an encode of H host-routed pretokens moves the pair by
    /// exactly the lookups and merges those pretokens cost, which
    /// `tests/host_route_merge_cost.rs` pins against the full-rescan counts
    /// the host arm used to pay for the same ids.
    host_lookups: AtomicU64,
    host_merges: AtomicU64,
    /// An explicit workgroup count, replacing the queried one.
    ///
    /// `None` on every ordinary tokenizer. See
    /// [`Self::with_workgroups_per_dispatch`].
    workgroup_override: Option<u32>,
}

impl DeviceTokenizer {
    /// Build the device-resident merge table for `vocab`.
    ///
    /// The table holds EVERY row of `vocab`'s merge table, not the subset some
    /// corpus reaches, because it has to answer for inputs this call has not
    /// seen. See [`reachable_rows`] for when the other tradeoff is right.
    ///
    /// # Errors
    ///
    /// Returns [`ExatokError::Artifact`] when `vocab` is missing one of the 256
    /// single-byte tokens the byte-level start state needs, when two of its rows
    /// share a pair, when a row carries [`Rank::ABSENT`], or when no table
    /// capacity admits every key.
    pub fn new(vocab: &Vocabulary, encoding: &Encoding) -> Result<Self, ExatokError> {
        let byte_token = byte_token_ids(encoding.artifact(), vocab)?;

        let rows = vocab
            .merge_table()
            .iter()
            .map(|(pair, entry)| (pair, entry.id, entry.rank));
        let table = RankTable::from_entries(encoding.artifact(), rows)?;

        Ok(Self {
            encoding: encoding.clone(),
            table,
            byte_token,
            batching: Batching::default(),
            dispatches: AtomicUsize::new(0),
            block_ceilings: RwLock::new(Vec::new()),
            plans: RwLock::new(Vec::new()),
            plan_hits: AtomicUsize::new(0),
            plan_misses: AtomicUsize::new(0),
            plan_rebuilds: AtomicU64::new(0),
            output_batch_checks: AtomicU64::new(0),
            output_segment_guards: AtomicU64::new(0),
            host_lookups: AtomicU64::new(0),
            host_merges: AtomicU64::new(0),
            table_bytes: OnceLock::new(),
            workgroup_override: None,
        })
    }

    /// Replace the batching mode, keeping the built table.
    ///
    /// Consuming rather than `&mut self` so the mode is fixed for a tokenizer's
    /// lifetime and `encode` stays `&self`. Moving a tokenizer does not rebuild
    /// anything, so switching modes to compare them costs nothing.
    #[must_use]
    pub fn with_batching(mut self, batching: Batching) -> Self {
        self.batching = batching;
        self
    }

    /// Batching mode this tokenizer groups dispatches with.
    #[must_use]
    pub const fn batching(&self) -> Batching {
        self.batching
    }

    /// Replace the workgroups one dispatch may ask for, keeping the built table.
    ///
    /// Ordinary use does not need this. The default is QUERIED from the device by
    /// [`Self::workgroups_per_dispatch`], because the ceiling is a property of
    /// the card and of the compiled pass body, and a written-down number is wrong
    /// on the next of either.
    ///
    /// It exists for two callers. A benchmark sweeping dispatch width has to hold
    /// that width fixed while it measures. And a test has to be able to ASK for a
    /// grid this device cannot make co-resident, in order to prove that refusal
    /// still propagates: an override above the real residency is refused by
    /// [`crate::gpu_loop`] with the block count and the limit named, and that
    /// error is returned rather than quietly rerouted to the host. The two
    /// failures are not alike. An over-long pretoken has an exact host answer, so
    /// routing it to the host is lossless. An over-residency grid has no host
    /// answer that preserves the reason the device path exists, so it must keep
    /// failing.
    #[must_use]
    pub fn with_workgroups_per_dispatch(mut self, workgroups: u32) -> Self {
        self.workgroup_override = Some(workgroups);
        self
    }

    /// Workgroups one dispatch will ask this backend for.
    ///
    /// The override when [`Self::with_workgroups_per_dispatch`] set one,
    /// otherwise the device's queried cooperative block ceiling reduced by this
    /// module's headroom. Public because a caller sizing its own batches needs it
    /// to feed [`segments_per_dispatch`], and because it is the number that
    /// explains an observed dispatch count.
    #[must_use]
    pub fn workgroups_per_dispatch(&self, backend: &dyn VyreBackend) -> u32 {
        self.workgroup_override
            .unwrap_or_else(|| workgroups_within_headroom(self.queried_block_ceiling(backend)))
    }

    /// Largest grid, in workgroups, this backend admits for one
    /// grid-synchronized dispatch of THIS tokenizer's pass body.
    ///
    /// Queried once PER BACKEND and cached, and reported separately from
    /// [`Self::workgroups_per_dispatch`] because the two answer different
    /// questions: this is what the device says it can hold, that is what this
    /// tokenizer will ask for, and the gap between them is the headroom. An
    /// operator comparing the two sees at once whether a refusal came from the
    /// device or from this module's own budget.
    ///
    /// Treat it as a ceiling to stay under rather than a capacity to fill. It
    /// bounds THREAD residency, and the stricter per-kernel bound that register
    /// and shared-memory pressure impose is enforced only at launch, so a grid
    /// under this number can still be refused.
    ///
    /// Zero means the backend admits no cooperative launch of this program at any
    /// grid size. That is an answer and not a failure: it is what a backend
    /// permitting a host kernel split reports, and a single-group dispatch
    /// carries no grid barrier and needs none.
    #[must_use]
    pub fn queried_block_ceiling(&self, backend: &dyn VyreBackend) -> u32 {
        let id = backend.id();
        if let Some(ceiling) = self
            .block_ceilings
            .read()
            .unwrap_or_else(PoisonError::into_inner)
            .iter()
            .find_map(|(cached, ceiling)| (*cached == id).then_some(*ceiling))
        {
            return ceiling;
        }
        let shape = residency_probe_shape();
        let program = device_loop_program(
            shape,
            bpe_merge_body(shape, self.table.capacity(), self.table.window()),
            bpe_caller_buffers(shape, self.table.capacity()),
        );
        let ceiling = cooperative_block_ceiling(backend, &program, shape);
        let mut cache = self
            .block_ceilings
            .write()
            .unwrap_or_else(PoisonError::into_inner);
        // A concurrent query for the same backend may have inserted while this one
        // was probing. Keep the first answer instead of appending a duplicate, so
        // the lookup above stays single-valued.
        if let Some((_, existing)) = cache.iter().find(|(cached, _)| *cached == id) {
            return *existing;
        }
        cache.push((id, ceiling));
        ceiling
    }

    /// The encoding this tokenizer was built for.
    #[must_use]
    pub const fn encoding(&self) -> &Encoding {
        &self.encoding
    }

    /// The uploaded merge table, for a caller that wants to size or inspect it.
    #[must_use]
    pub const fn table(&self) -> &RankTable {
        &self.table
    }

    /// Encode bytes.
    ///
    /// Bytes, not `&str`, because pretokenization splits bytes and input need
    /// not be valid UTF-8. A byte that is not part of a well-formed UTF-8
    /// sequence belongs to no Unicode class and so lands in the punctuation
    /// alternative, which is what a byte-level device DFA does naturally; see
    /// [`crate::pretokenize`].
    ///
    /// # Errors
    ///
    /// See [`Self::encode_batch`], which this delegates to so there is one
    /// implementation of the path.
    pub fn encode(
        &self,
        backend: &dyn VyreBackend,
        input: &[u8],
    ) -> Result<Vec<TokenId>, ExatokError> {
        let mut per_input = self.encode_batch(backend, &[input])?.into_ids();
        Ok(per_input.pop().unwrap_or_default())
    }

    /// One dispatch of the composed BPE loop over `words`, capped at `budget`
    /// passes.
    ///
    /// The single place a merge program is built, so every caller exercises
    /// byte-identical IR. Two of them building their own would let a divergence
    /// hide in the harness.
    ///
    /// A method rather than a free function because everything it uploads outlives
    /// the dispatch: the packed table and the emitted program, both held by the
    /// tokenizer and both handed to the loop as borrows.
    ///
    /// # Errors
    ///
    /// Propagates whatever [`run_device_loop_borrowed`] reports: a failed
    /// dispatch, or a backend that returned fewer buffers than the harness
    /// declares.
    ///
    /// `probe` charges the three leaves this call is made of: the padded state
    /// build, the plan lookup, and the dispatch itself. They are charged here
    /// rather than by the caller because they are separate cost owners and only
    /// this frame can see the boundaries between them.
    ///
    /// `batch_pool` carries the state allocation across an encode's dispatches:
    /// the first dispatch builds the batch, every later one reseeds it in
    /// place, and [`LoopBatch::reseed`] rewrites every word, so the bytes
    /// handed to the backend are identical to a fresh build while the
    /// allocator sees the state array once per encode instead of once per
    /// dispatch. The pool is the caller's and dies with the encode, so no
    /// state crosses calls.
    fn run_bpe_loop<P: PhaseProbe>(
        &self,
        backend: &dyn VyreBackend,
        words: &[&[u32]],
        budget: u32,
        table: CallerInput<'_>,
        batch_pool: &mut Option<LoopBatch>,
        probe: &mut P,
    ) -> Result<LoopOutcome, ExatokError> {
        let batch = probe.measure(EncodePhase::LoopBatchBuild, |_| {
            match batch_pool {
                Some(batch) => {
                    batch.reseed(words, budget);
                    batch
                }
                None => batch_pool.insert(LoopBatch::new(words, budget)),
            }
        });
        let plan = probe.measure(EncodePhase::PlanLookup, |_| self.dispatch_plan(batch.shape()));
        let caller_inputs = [table, CallerInput::Host(&plan.pick_seed)];
        probe.dispatched(batch.state().len());
        probe.measure(EncodePhase::Dispatch, |_| {
            run_device_loop_borrowed(backend, &plan.program, batch, &caller_inputs)
        })
    }

    /// Allocate a device buffer for the packed table and upload it once.
    ///
    /// Split out so the failure path is explicit: an allocation that succeeds and
    /// an upload that then fails must release the buffer, or a retrying caller
    /// leaks 16 MiB of device memory per attempt.
    ///
    /// # Errors
    ///
    /// Returns [`ExatokError::Backend`] when the backend cannot allocate a
    /// resident buffer of the table's size or cannot upload into it.
    fn upload_resident_table(
        &self,
        backend: &dyn VyreBackend,
        bytes: &[u8],
    ) -> Result<Resource, ExatokError> {
        let resource = backend.allocate_resident(bytes.len()).map_err(|error| {
            ExatokError::Backend(format!(
                "device resident table allocation of {} byte(s) failed: {error}. \
                 Fix: free device memory and retry, or encode without a resident session \
                 so the table is bound from host memory per call",
                bytes.len()
            ))
        })?;
        if let Err(error) = backend.upload_resident(&resource, bytes) {
            // The original upload error is what gets reported; a free that also
            // fails here would only mask the cause.
            drop(backend.free_resident(resource));
            return Err(ExatokError::Backend(format!(
                "device resident table upload of {} byte(s) failed: {error}. \
                 Fix: drop this tokenizer or session and bind a fresh one, since a buffer \
                 the backend just allocated refusing its upload marks the device context \
                 as suspect",
                bytes.len()
            )));
        }
        Ok(resource)
    }

    /// The plan for `shape`, built on first use and reused afterwards.
    ///
    /// Takes the shape from the caller's own [`LoopBatch`] rather than deriving it
    /// again, so a plan can never describe a shape other than the batch it runs.
    fn dispatch_plan(&self, shape: LoopShape) -> Arc<DispatchPlan> {
        if let Some(plan) = self.cached_plan(shape) {
            self.plan_hits.fetch_add(1, Ordering::Relaxed);
            return plan;
        }
        self.plan_misses.fetch_add(1, Ordering::Relaxed);
        // Built with NO lock held. Construction is thousands of IR allocations,
        // and holding the write lock across it would serialize the concurrent
        // encodes this cache exists to speed up. Two threads that miss the same
        // shape therefore both build it; the programs are byte-identical, so the
        // insert below keeps whichever arrives first and the other is dropped.
        let built = Arc::new(DispatchPlan {
            program: device_loop_program(
                shape,
                bpe_merge_body(shape, self.table.capacity(), self.table.window()),
                bpe_caller_buffers(shape, self.table.capacity()),
            ),
            pick_seed: pack_u32_slice(&pick_seed(shape.segments())),
        });
        // Charged AFTER the construction returns, so the count is plans that
        // were actually built and paid for, including the loser of a
        // double-build race: its program was constructed too.
        self.plan_rebuilds.fetch_add(1, Ordering::Relaxed);

        let mut plans = self.plans.write().unwrap_or_else(PoisonError::into_inner);
        if let Some((_, plan)) = plans.iter().find(|(cached, _)| *cached == shape) {
            return Arc::clone(plan);
        }
        plans.push((shape, Arc::clone(&built)));
        // Cheapest to rebuild goes first, NOT oldest first.
        //
        // Oldest-first was measured to be the worst possible order here. An
        // encode walks its bands longest first, so the oldest entry is the widest
        // plan, the one whose rebuild costs 1565 host allocations per pass of a
        // budget that can be 256. Oldest-first therefore threw away the single
        // most expensive plan to make room for the cheapest, on a cyclic access
        // pattern, which is the arrangement with a guaranteed zero hit rate.
        //
        // Rebuild cost is linear in IR size and [`DispatchPlan::retained_bytes`]
        // measures IR size, so evicting the smallest weight first bounds the WORK
        // an overflow loses rather than the number of entries it loses. On a
        // working set that still does not fit, that leaves the wide plans resident
        // and rebuilds only the cheap ones, instead of rebuilding all of them.
        //
        // `min_by_key` returns the FIRST minimum, so equal weights break to the
        // oldest and the sweep stays deterministic: a cache state reproduces.
        //
        // `len() > 1` keeps the cache from emptying itself. Combined with
        // cheapest-first it also means the entry that may go uncached when nothing
        // fits is the cheapest one to rebuild, where the old rule sacrificed
        // whichever happened to be oldest.
        let mut held: usize = plans.iter().map(|(_, plan)| plan.retained_bytes()).sum();
        while held > PLAN_CACHE_BYTES && plans.len() > 1 {
            let victim = plans
                .iter()
                .enumerate()
                .min_by_key(|(_, (_, plan))| plan.retained_bytes())
                .map_or(0, |(index, _)| index);
            let (_, evicted) = plans.remove(victim);
            held -= evicted.retained_bytes();
        }
        built
    }

    /// Plans this tokenizer has constructed after a cache miss, since
    /// creation.
    ///
    /// Exists for tests and cost accounting: the cache is an internal cost
    /// property, and this count is how a test proves a multi-band encode does
    /// not rebuild every plan per encode. Charged where the construction
    /// happens, so it is exact: a hit adds nothing, a miss adds one, and the
    /// rare double-build race adds one per builder because each paid for the
    /// construction. Eviction is not special-cased either; a shape the cache
    /// dropped and had to rebuild counts again, because the rebuild was paid.
    ///
    /// The expectation a test derives from it: the first encode over a set of
    /// shapes adds one per distinct shape, and repeated encodes of the same
    /// shapes add zero, so the count stays flat across them.
    #[must_use]
    pub fn plan_rebuilds(&self) -> u64 {
        self.plan_rebuilds.load(Ordering::Relaxed)
    }

    /// The already-built plan for `shape`, under a shared read lock.
    ///
    /// Separated from [`Self::dispatch_plan`] so the read guard is dropped before
    /// the miss path takes the write lock. Written as one expression on a guard
    /// that lives for the statement, an `if let` would hold the read lock across
    /// the whole `else`, and taking the write lock there would deadlock.
    fn cached_plan(&self, shape: LoopShape) -> Option<Arc<DispatchPlan>> {
        self.plans
            .read()
            .unwrap_or_else(PoisonError::into_inner)
            .iter()
            .find(|(cached, _)| *cached == shape)
            .map(|(_, plan)| Arc::clone(plan))
    }

    /// Plans reused and plans built, since this tokenizer was created.
    ///
    /// `#[cfg(test)]` and not `pub`: the cache is an internal cost property, not
    /// a contract a caller may build on, and this path's published API is fixed.
    /// The counters themselves are unconditional, since two atomic adds per
    /// dispatch are free against the construction they account for.
    #[cfg(test)]
    fn plan_cache_tally(&self) -> (usize, usize) {
        (
            self.plan_hits.load(Ordering::Relaxed),
            self.plan_misses.load(Ordering::Relaxed),
        )
    }

    /// Bind this tokenizer to `backend`, uploading the merge table ONCE.
    ///
    /// The table is 16 MiB for `cl100k_base` and it never changes for a
    /// tokenizer's lifetime, yet [`Self::encode_batch`] has to allocate, upload
    /// and free it on every call. That is not an oversight: it takes the backend
    /// per call and does not own it, so a resident handle cached on the tokenizer
    /// could outlive the backend that minted it. vyre's resident ids come from a
    /// counter private to one backend INSTANCE, so a stale handle would not
    /// dangle visibly, it would name a live buffer belonging to a different
    /// backend, and binding a wrong 16 MiB table produces wrong merges that still
    /// look like plausible ids. It would also leak the buffer, since nothing left
    /// would be able to free it.
    ///
    /// A session states that lifetime instead of guessing it. It borrows both the
    /// tokenizer and the backend, so the handle cannot outlive either, and
    /// [`DeviceSession::close`] or [`Drop`] gives the buffer back. On prose this
    /// removes [`EncodePhase::TableUpload`] and [`EncodePhase::TableFree`],
    /// measured at 2.816 ms and 0.140 ms of a 19.656 ms encode, from every encode
    /// after the bind.
    ///
    /// The session also carries the per-encode [`Scratch`], which is the other
    /// cost a single call cannot amortize.
    ///
    /// The plan cache and the packed table bytes stay on the TOKENIZER, because
    /// neither depends on a backend: two sessions over two devices share both.
    ///
    /// # Errors
    ///
    /// Returns [`ExatokError::Backend`] when the backend cannot allocate or
    /// upload a resident buffer of the table's size. A backend with no resident
    /// dispatch at all is NOT an error: the session holds no buffer and every
    /// encode passes the table as an ordinary host input, exactly as
    /// [`Self::encode_batch`] does there.
    pub fn bind<'a>(
        &'a self,
        backend: &'a dyn VyreBackend,
    ) -> Result<DeviceSession<'a>, ExatokError> {
        // Packed here rather than on first encode, because a session IS the
        // caller's statement that device work is coming: there is no all-host case
        // to protect from the 16 MiB serialization, which is the one reason
        // `encode_batch` defers it.
        //
        // Unconditionally, and NOT only when the backend has resident dispatch. A
        // backend without it still needs the bytes, as an ordinary host input on
        // every dispatch, so making the pack conditional would leave that path
        // reaching back into the tokenizer's `OnceLock` on every encode for a value
        // the session could simply be holding. The borrow is what makes holding it
        // sound: the bytes live in `self`, and the session cannot outlive `self`.
        let bytes = self
            .table_bytes
            .get_or_init(|| pack_u32_slice(self.table.slot_words()))
            .as_slice();
        let table = if backend.supports_resident_dispatch() {
            Some(self.upload_resident_table(backend, bytes)?)
        } else {
            None
        };
        Ok(DeviceSession {
            tokenizer: self,
            backend,
            table,
            table_bytes: bytes,
            scratch: Mutex::new(Vec::new()),
        })
    }

    /// Encode many inputs, batching across them so short inputs do not each pay
    /// a dispatch.
    ///
    /// Batching is across INPUTS as well as across each input's pretokens: every
    /// pretoken of every input goes into one flat list, and a dispatch is filled
    /// from that list regardless of which input a pretoken came from. That is
    /// what makes a thousand short inputs cost a handful of dispatches instead
    /// of a thousand. It is sound for the same reason batching within one input
    /// is: a merge never crosses a pretoken boundary, so segments in a dispatch
    /// are independent and their grouping cannot affect any id.
    ///
    /// Pretokens above [`MAX_PRETOKEN_TOKENS`] are encoded on the HOST and
    /// spliced back in pretoken order; see [`Routing`] for why that is
    /// scheduling and not a fallback.
    ///
    /// Every call uploads and frees the resident merge table, because a call
    /// cannot keep a handle to a backend it was only lent. [`Self::bind`] pays
    /// that once for a whole session of encodes and is what a repeated caller
    /// should reach for. This entry point stays the right one for a single
    /// encode, and for an encode whose pretokens may all be host-routed: it does
    /// not touch the device until it knows there is device work, which is a
    /// question a session has already answered by existing.
    ///
    /// # Errors
    ///
    /// Returns [`ExatokError::Backend`] when a dispatch fails, and
    /// [`ExatokError::Divergence`] when a segment was still merging at the pass
    /// budget, which is a pass-body defect rather than a budget to raise. A
    /// pretoken past [`MAX_PRETOKEN_TOKENS`] is NOT an error: it is routed to the
    /// host. A span that does not lie inside its input still is, because that
    /// would mean `pretokenize` returned a span for bytes the input does not
    /// have.
    pub fn encode_batch(
        &self,
        backend: &dyn VyreBackend,
        inputs: &[&[u8]],
    ) -> Result<Encoded, ExatokError> {
        self.encode_batch_per_call(backend, inputs, &mut Untimed)
    }

    /// [`Self::encode_batch`], reporting where its host time went.
    ///
    /// The SAME function body, reached through the same generic call with a
    /// measuring [`PhaseProbe`] instead of the do-nothing one, so a profiled
    /// encode cannot diverge from a plain one and the ids are identical by
    /// construction. The plain path pays nothing for this: `Untimed` inlines
    /// away and leaves no clock read behind.
    ///
    /// The profile's named phases are LEAVES that do not overlap, and
    /// [`EncodeProfile::unattributed`] is what they did not cover. Read that
    /// figure first: a breakdown is only an explanation when the remainder is
    /// small, and reporting the named rows without it turns four measured costs
    /// into a story about a cost nobody measured.
    ///
    /// [`EncodePhase::TableUpload`] and [`EncodePhase::TableFree`] are this
    /// path's own cost and read near zero through
    /// [`DeviceSession::encode_batch_profiled`], which is the comparison those
    /// two rows exist to make visible.
    ///
    /// # Errors
    ///
    /// Exactly [`Self::encode_batch`]'s. A failed encode returns the error
    /// rather than a partial profile, because a profile of a call that did not
    /// finish describes no complete encode.
    pub fn encode_batch_profiled(
        &self,
        backend: &dyn VyreBackend,
        inputs: &[&[u8]],
    ) -> Result<(Encoded, EncodeProfile), ExatokError> {
        let mut probe = Timed::start();
        let encoded = self.encode_batch_per_call(backend, inputs, &mut probe);
        let profile = probe.finish();
        encoded.map(|ids| (ids, profile))
    }

    /// One encode over a table and a [`Scratch`] that live for this call alone.
    ///
    /// The scratch is owned HERE rather than inside [`Self::encode_batch_probed`]
    /// so that giving it back is inside the measured region: that release is
    /// [`EncodePhase::Teardown`]'s cost on this path, and a scratch dropped by a
    /// caller after the profile's clock stopped would land in no row at all.
    ///
    /// # Errors
    ///
    /// See [`Self::encode_batch`].
    fn encode_batch_per_call<P: PhaseProbe>(
        &self,
        backend: &dyn VyreBackend,
        inputs: &[&[u8]],
        probe: &mut P,
    ) -> Result<Encoded, ExatokError> {
        let mut scratch = Scratch::default();
        let encoded =
            self.encode_batch_probed(backend, inputs, probe, TableSource::PerCall, &mut scratch);
        probe.measure(EncodePhase::Teardown, |_| drop(scratch));
        encoded
    }

    /// The one implementation of the encode path, generic over its probe and
    /// indifferent to where its table and its buffers came from.
    ///
    /// # Errors
    ///
    /// See [`Self::encode_batch`].
    fn encode_batch_probed<P: PhaseProbe>(
        &self,
        backend: &dyn VyreBackend,
        inputs: &[&[u8]],
        probe: &mut P,
        source: TableSource<'_>,
        scratch: &mut Scratch,
    ) -> Result<Encoded, ExatokError> {
        // Clear the tally FIRST, so it describes this call whatever happens. An
        // encode that returns an error before reaching the device must report
        // zero dispatches rather than leaving the previous call's count standing,
        // which would read as "the refused input dispatched once".
        self.dispatches.store(0, Ordering::Relaxed);
        // Emptied at the START of an encode and not at the end of the one before,
        // because this is the only point every path reaches: an encode that
        // returns an error leaves its runs behind, and a later encode on the same
        // session would read them as its own and answer with ids from an input it
        // was never given. Only the lengths go; the capacity is the whole point.
        probe.measure(EncodePhase::Teardown, |_| scratch.reset());

        // One reserve for the whole call. Merging starts one token per byte and
        // the spans tile the input, so this is the EXACT word count the start
        // states need and an upper bound on the ids they converge to, since no
        // merge ever adds a token. Both are no-ops on a session whose previous
        // encode was this size, which is what turns two allocations per PRETOKEN
        // into none, and both are no-ops at zero bytes, so an encode of nothing
        // still allocates nothing here.
        let input_bytes: usize = inputs.iter().map(|input| input.len()).sum();
        scratch.state.reserve(input_bytes);
        scratch.ids.reserve(input_bytes);

        // Host-bound pretokens are encoded during the SAME walk that discovers
        // them, so the splice is positional and there is no reordering step to get
        // wrong. A design that collected host pretokens separately and merged the
        // two streams afterwards would have to reconstruct the interleaving, which
        // is the part a splice gets wrong.
        let mut pretokens_per_input: Vec<usize> = Vec::with_capacity(inputs.len());
        let mut routing = Routing::default();
        // Host-route cost accounting. The scratch merge state counts every
        // pair-table lookup it issues, so this encode's share of the
        // tokenizer-wide tally is the delta against a baseline taken now.
        // The counters are NOT reset between encodes: a pooled scratch hands
        // its running totals to whichever encode checks it out, and only a
        // per-encode snapshot attributes them to the encode that paid them.
        let mut host_tally = (
            scratch.host_merge.lookups(),
            scratch.host_merge.merges(),
        );

        for (input_index, input) in inputs.iter().enumerate() {
            // Taken out of the scratch for the walk and put back after it, so
            // the spans are readable while `scratch` stays borrowable for the
            // state and id buffers. `take` and the put-back move the Vec and
            // allocate nothing: a warm session splits every input into the one
            // buffer its earlier encodes grew, where the old path collected a
            // fresh `Vec<Span>` per input.
            let mut span_buf = std::mem::take(&mut scratch.spans);
            // The buffer holds the PREVIOUS input's spans: one buffer serves
            // every input of the encode, so each walk starts it empty. The
            // capacity is the point; the lengths are per input.
            span_buf.clear();
            probe.measure(EncodePhase::Pretokenize, |_| {
                // The gapless-tiling check rides the same pass that produces
                // the spans: `extend_tiling_spans` asserts each span starts
                // where the last one ended as it arrives, so the invariant is
                // still enforced on every encode and the second walk the check
                // used to cost is gone.
                extend_tiling_spans(
                    input.len(),
                    pretokens(self.encoding.pattern(), input),
                    &mut span_buf,
                );
            });
            pretokens_per_input.push(span_buf.len());
            // Exactly one run per pretoken of this input, host-routed or not, and
            // the count is known before the walk fills them.
            //
            // `state_runs` and `device_slot` deliberately get no such reserve.
            // Their length is decided by ROUTING and not by the span count, so
            // reserving the span count would over-allocate for a host-heavy input
            // and, worse, would allocate device-path buffers for an all-host
            // encode, which must pay no device cost at all. Amortized growth
            // already makes their pushes constant time.
            scratch.id_runs.reserve(span_buf.len());

            let walked =
                probe.measure(EncodePhase::ByteEncode, |probe| -> Result<(), ExatokError> {
                    for &span in &span_buf {
                        let Some(bytes) = span.bytes(input) else {
                            return Err(self.span_error(input_index, span, input.len()));
                        };

                        // Routed on the BYTE count, before any state is built: a
                        // pretoken's token count on entry equals its byte count,
                        // because merging starts one token per byte. So the host
                        // route never materializes a `u32` start state only to
                        // convert it.
                        if bytes.len() > MAX_PRETOKEN_TOKENS {
                            routing.on_host += 1;
                            routing.largest_host_tokens =
                                routing.largest_host_tokens.max(bytes.len());
                            // Routed, not degraded, and the ids are identical BY
                            // CONSTRUCTION rather than by testing: `RankTable`
                            // implements `MergeTable` as a step-for-step mirror of
                            // the device probe, so this walks the very rows the
                            // device would have walked, through the same
                            // leftmost-lowest-rank rule. Passing `self.table` and
                            // not a vocabulary is what makes that true; a
                            // vocabulary lookup would be a second table and the
                            // claim would rest on the two agreeing.
                            let run = probe.measure(EncodePhase::HostEncode, |_| {
                                scratch.push_host_ids(bytes, &self.byte_token, &self.table)
                            });
                            scratch.id_runs.push(run);
                            continue;
                        }

                        routing.on_device += 1;
                        // The slot is claimed now and filled after the dispatch
                        // that converges this pretoken, because batches are
                        // grouped by length and segments come back in an order
                        // that is not the input's.
                        scratch.device_slot.push(scratch.id_runs.len());
                        scratch.id_runs.push(Run::EMPTY);
                        scratch.push_start_state(bytes, &self.byte_token);
                    }
                    Ok(())
                });
            // Put back before the error can propagate, so a failed encode still
            // returns the buffer and its capacity to the session.
            scratch.spans = span_buf;
            walked?;
            // Charge this input's host-route work now that its walk completed,
            // per input rather than once at the end so an encode that fails on
            // a later input still counts the work it genuinely paid. Two
            // relaxed adds per input; the per-lookup counting itself happened
            // inside the merge state's own counters at no instrumentation cost.
            let host_tally_now = (
                scratch.host_merge.lookups(),
                scratch.host_merge.merges(),
            );
            self.host_lookups
                .fetch_add(host_tally_now.0 - host_tally.0, Ordering::Relaxed);
            self.host_merges
                .fetch_add(host_tally_now.1 - host_tally.1, Ordering::Relaxed);
            host_tally = host_tally_now;
        }

        let mut covered = 0_usize;
        let mut dispatches = 0_usize;
        // The residency query happens ONLY when there is device work. An encode
        // whose every pretoken went to the host must not pay a bisection over the
        // backend's geometry predicate to size a grid it will never ask for, and
        // an encode of nothing must not touch the device at all.
        let workgroups = if scratch.state_runs.is_empty() {
            1
        } else {
            probe.measure(EncodePhase::ResidencyQuery, |_| {
                self.workgroups_per_dispatch(backend)
            })
        };

        // Empty FIRST, so an all-host encode carries no table at all. A caller
        // whose every pretoken exceeds `MAX_PRETOKEN_TOKENS` never reaches the
        // device, and it must not pay for a buffer no dispatch binds nor report
        // table bytes it did not move.
        //
        // On the unbound path this is a 16 MiB serialization on first touch, which
        // is the whole reason it is deferred to here rather than done in `new`. A
        // session hands the bytes over instead, so it enters
        // [`EncodePhase::TablePack`] not at all: not even for the initialized
        // `OnceLock` load, which is cheap but is still a phase entry, and a row that
        // reads a few hundred nanoseconds instead of zero invites a reader to
        // wonder what work a session is still doing on a table it already packed.
        let table_bytes: &[u8] = if scratch.state_runs.is_empty() {
            &[]
        } else {
            match source {
                TableSource::Session { bytes, .. } => bytes,
                TableSource::PerCall => probe.measure(EncodePhase::TablePack, |_| {
                    self.table_bytes
                        .get_or_init(|| pack_u32_slice(self.table.slot_words()))
                        .as_slice()
                }),
            }
        };
        // The merge table is 16 MiB and never changes, yet vyre re-uploads every
        // binding on every dispatch, so a four-dispatch prose encode moved four
        // identical copies of it: 67.1 MB of the 71.00 MB this path transfers, and
        // 88 to 96 percent of the per-dispatch fixed cost. Uploading it once and
        // binding the handle for every batch removes all but the first copy.
        //
        // Once per CALL here, and once per SESSION at bind. The per-call arm cannot
        // be cached on the tokenizer: resident ids are handed out by a counter
        // private to one backend INSTANCE, so a handle cached across calls could
        // outlive the backend that made it and then name a live buffer belonging to
        // a different one. Binding a wrong 16 MiB table produces wrong merges, and
        // wrong merges still return plausible ids, which is the single failure mode
        // this crate exists to rule out. That is why the lifetime is either this
        // frame or a session's, and never a guess.
        let per_call_table = match source {
            TableSource::PerCall
                if !table_bytes.is_empty() && backend.supports_resident_dispatch() =>
            {
                Some(probe.measure(EncodePhase::TableUpload, |_| {
                    self.upload_resident_table(backend, table_bytes)
                })?)
            }
            _ => None,
        };
        // No table bytes means no dispatch at all, so a session's handle is left
        // unbound rather than described to a dispatch that never happens. That
        // keeps an all-host encode reporting zero table bytes on BOTH paths, which
        // is what makes the two profiles comparable row by row.
        let resident: Option<&Resource> = match source {
            TableSource::Session { table, .. } if !table_bytes.is_empty() => table,
            TableSource::Session { .. } => None,
            TableSource::PerCall => per_call_table.as_ref(),
        };
        let table = match resident {
            Some(resource) => CallerInput::Resident {
                resource,
                bytes: table_bytes,
            },
            None => CallerInput::Host(table_bytes),
        };

        // Split into its fields for the rest of the encode, because one dispatch
        // reads its caller inputs as slices of `state` while writing its output
        // into `ids`, and a single `&mut Scratch` would make those one borrow.
        let Scratch {
            state,
            state_runs,
            ids,
            id_runs,
            device_slot,
            host_state: _,
            host_merge: _,
            spans: _,
        } = scratch;

        let mut dispatch_batches = |probe: &mut P| -> Result<(), ExatokError> {
            let plan = probe.measure(EncodePhase::Batching, |_| {
                batches(state_runs, self.batching, workgroups)
            });
            // One vector for the whole encode, cleared and refilled per dispatch.
            // It holds borrows of `state`, so it cannot live in the scratch across
            // calls, but nothing makes it a per-dispatch allocation either.
            let mut batch_words: Vec<&[u32]> = Vec::new();
            // One [`LoopBatch`] for the whole encode, reseeded per dispatch, so
            // the state array is allocated on the first dispatch and reused
            // with resize afterwards. See [`DeviceTokenizer::run_bpe_loop`].
            let mut batch_pool: Option<LoopBatch> = None;
            for batch_indices in plan {
                // Borrowed rather than cloned. This used to deep-copy every
                // pretoken's word vector on every dispatch, one allocation per
                // device pretoken for bytes the scratch already holds.
                // [`LoopBatch`] is generic over `AsRef<[u32]>`, so a slice seeds it
                // identically to a `Vec`.
                let longest = probe.measure(EncodePhase::CallerInputs, |_| {
                    batch_words.clear();
                    batch_words
                        .extend(batch_indices.iter().map(|index| state_runs[*index].of(state)));
                    // Every merge drops exactly one token, so the longest pretoken
                    // bounds the merges and [`merge_pass_bound`] publishes that
                    // bound. Reported raw here; the budget is derived from it below.
                    batch_words.iter().map(|word| word.len()).max().unwrap_or(1) as u32
                });
                // The budget is DERIVED from the published bound rather than
                // restated: `merge_pass_bound(longest)` is `longest.max(1)`, and the
                // `+ 1` is the one extra pass that observes nothing changed. This
                // used to spell `longest.max(1) + 1` inline, a second statement of a
                // bound the loop module already owns. The value is unchanged.
                let passes = merge_pass_bound(longest) + 1;
                let outcome =
                    self.run_bpe_loop(backend, &batch_words, passes, table, &mut batch_pool, probe)?;
                dispatches += 1;

                probe.measure(EncodePhase::OutputAssembly, |_| {
                    // One convergence question per DISPATCH, not per segment.
                    // A converged batch has nothing per segment left to guard,
                    // so the fast path walks the state with the layout
                    // arithmetic done once and bulk-appends, skipping the
                    // per-segment `segment_changed` load, the `Result`
                    // construction, and the repeated bounds checks the
                    // per-segment path pays. Only a capped batch can refuse,
                    // so only it keeps the fallible per-segment walk, and that
                    // walk stays byte-identical to what the fast path appends.
                    self.output_batch_checks.fetch_add(1, Ordering::Relaxed);
                    if let Some(segments) = outcome.converged_segments() {
                        for (tokens, index) in segments.zip(batch_indices.iter()) {
                            // Appended to the flat buffer and named by a run,
                            // rather than copied into a `Vec` of its own. The
                            // same bytes move, one amortized allocation for the
                            // whole encode instead of one per segment, and the
                            // run is what lets the buffer be filled in dispatch
                            // order while it is read in pretoken order.
                            id_runs[device_slot[*index]] = Run::append(ids, tokens);
                            covered += 1;
                        }
                    } else {
                        for (segment, index) in batch_indices.iter().enumerate() {
                            self.output_segment_guards.fetch_add(1, Ordering::Relaxed);
                            let tokens = outcome.converged_tokens(segment as u32)?;
                            id_runs[device_slot[*index]] = Run::append(ids, tokens);
                            covered += 1;
                        }
                    }
                    Ok::<(), ExatokError>(())
                })?;
            }
            Ok(())
        };
        let dispatched = dispatch_batches(probe);

        // Freed before the dispatch result is propagated, so a failed encode
        // releases the 16 MiB rather than holding it until the tokenizer drops.
        // The dispatch error wins if both fail: it is the cause, and a free error
        // reported in its place would send a reader to the wrong half of the path.
        // A session's table is not freed here at all: it is the session's, and it
        // outlives this encode by design.
        if let Some(resource) = per_call_table {
            let freed = probe.measure(EncodePhase::TableFree, |_| backend.free_resident(resource));
            // Reported only when the dispatch itself succeeded. If both failed the
            // dispatch error is the cause, and surfacing the free error in its
            // place would point a reader at the wrong half of the path.
            if dispatched.is_ok() {
                freed.map_err(|error| {
                    ExatokError::Backend(format!(
                        "device resident table free failed: {error}. \
                         Fix: retry the encode on a fresh backend, because a free that \
                         fails after a successful dispatch points at the device context, \
                         not at the input"
                    ))
                })?;
            }
        }
        dispatched?;

        // Exact count, not `.all(|covered| covered)`. That form was shape-only
        // and vacuous on an empty batch plan, since `.all()` is true over an
        // empty iterator: a `batches` bug that emitted NO batches would have
        // passed it while every pretoken went unencoded. Counting the covered
        // pretokens and comparing to the total fails in that case.
        //
        // Against the DEVICE runs and NOT every pretoken, because host-routed
        // pretokens are already filled and were never handed to `batches`.
        assert_eq!(
            covered,
            state_runs.len(),
            "every device pretoken must land in exactly one batch, so all {} must be covered",
            state_runs.len()
        );
        assert_eq!(
            routing.on_device + routing.on_host,
            id_runs.len(),
            "the routing counts must account for every pretoken, or a reported \
             device share is arithmetic on the wrong denominator"
        );

        self.dispatches.store(dispatches, Ordering::Relaxed);

        let (out, output_ids) = probe.measure(EncodePhase::IdAssembly, |_| {
            let mut out = Vec::with_capacity(inputs.len());
            let mut output_ids = 0_usize;
            let mut remaining: &[Run] = id_runs;
            // The partition must account for every run. `pretokens_per_input` pushes
            // one count per input, `pretoken_spans.len()`, in the same walk that
            // pushes exactly one run per pretoken, host-routed or not, so
            // `sum(pretokens_per_input) == id_runs.len()` is an invariant of that
            // walk and a disagreement is a defect in it rather than a caller's input.
            //
            // Asserted rather than clamped, because the clamp this replaces was
            // FAIL-OPEN on an internal invariant and hid two defects in opposite
            // directions. An OVER-count slid the partition: that input stole its
            // successor's first pretoken, every later input shifted, and the last was
            // truncated short or empty. An UNDER-count is the mirror: trailing runs
            // are never consumed and their ids are silently dropped.
            //
            // What made the over-count case survivable is why this is unconditional.
            // EVERY observable a caller has is unchanged by it: each individual id,
            // the total id count, `EncodeProfile::output_ids`, `Encoded::ids().len()`,
            // the flattened concatenation, and `Routing`, which counts pretokens
            // rather than inputs. Six agreeing quantities and the wrong answer, with
            // only per-input attribution wrong, which is the one thing a batch caller
            // asked for.
            //
            // Release rather than `debug_assert_eq!`, matching the two unconditional
            // assertions immediately above: one of them already pins `id_runs.len()`
            // here, so checking `sum(pretokens_per_input)` against the same quantity
            // in debug only would leave the two halves of ONE invariant verified at
            // different optimization levels. It costs one add per input against an
            // encode doing millions of merges.
            //
            // WHAT IT CATCHES, measured by injecting each defect here and running
            // `tests/batch_consistency.rs`, not reasoned about:
            //
            // * `pretokens_per_input[0] += 1` fires it, `left: 76, right: 75`, before
            //   the first `Vec` is allocated. Injected and observed in BOTH profiles,
            //   debug and `--release`, which is the only thing that proves the check is
            //   live where it matters: a green two-profile run cannot distinguish this
            //   from a `debug_assert_eq!`, because both are green in release. If
            //   someone demotes it, re-running this injection in release is what
            //   catches the demotion.
            // * A COMPENSATING PAIR does NOT fire it: `+1` on one input and `-1` on
            //   another leaves the sum equal, the assertion passes, and the partition
            //   still slides ids between those two inputs. That is the honest limit of
            //   a sum check and it is why this assertion is not the whole guard. The
            //   behavioural suite catches that case, 13 of its 24 tests, because it
            //   compares each input's ids against that input encoded ALONE rather than
            //   checking bookkeeping. The other 11 are silent STRUCTURALLY, not
            //   weakly: a compensating pair between inputs 0 and 1 needs a batch with
            //   two inputs of DIFFERING content at those positions, so the
            //   single-input cases have no pair, the all-identical case makes the swap
            //   a no-op by construction, the all-empty and empty-batch cases have no
            //   runs to move, and the premise tests never encode. Each is aimed at a
            //   different edge. So do not read this assertion as subsuming those
            //   tests, do not read 13 of 24 as a weak suite, and do not trim the 11:
            //   they carry the empty-input and degenerate-partition coverage nothing
            //   else has. The two layers catch different defects, sum violations here
            //   at one add per input, and sum-preserving partition violations there.
            //
            // The clamp is DELETED rather than guarded, and that is the load-bearing
            // half of this change. A clamp cannot fail, so it converted a detectable
            // partition bug into a silently plausible attribution: exactly a check
            // that reports success for having looked nowhere. Restoring it "for
            // safety" would re-open the fail-open path this assertion exists to close.
            assert_eq!(
                pretokens_per_input.iter().sum::<usize>(),
                id_runs.len(),
                "the per-input pretoken counts must account for all {} runs, or ids \
                 are attributed to the wrong input",
                id_runs.len()
            );
            for count in pretokens_per_input {
                // Unclamped. The assertion above makes `count <= remaining.len()`
                // hold at every step by induction, so a clamp here could only mask
                // the violation it already ruled out.
                let (slots, rest) = remaining.split_at(count);
                // Sized from the ids it will hold. The token count for this input is
                // known right here, so the output is one allocation instead of a
                // doubling sequence.
                let mut input_ids = Vec::with_capacity(slots.iter().map(|run| run.len).sum());
                for run in slots {
                    input_ids.extend(run.of(ids).iter().copied().map(TokenId));
                }
                output_ids += input_ids.len();
                out.push(input_ids);
                remaining = rest;
            }
            (out, output_ids)
        });
        // Counted rather than timed, and handed over once. Every figure here is
        // decided by the INPUT and not by the machine, so it reproduces on a
        // contended box where none of the durations above do, and a rate built
        // from a duration and one of these is the part of a measurement that
        // survives a change of box state.
        //
        // `input_bytes` is the start-state word count as well: merging begins one
        // token per byte and the spans tile the input gaplessly, which the
        // assertion in the walk above enforces.
        probe.counted(EncodeCounts {
            device_pretokens: routing.on_device,
            host_pretokens: routing.on_host,
            input_bytes,
            table_bytes: table_bytes.len(),
            output_ids,
        });
        Ok(Encoded { ids: out, routing })
    }

    /// Dispatches the last encode consumed, so a caller and a benchmark can see
    /// batching efficiency.
    ///
    /// Zero after an encode of nothing: no pretokens means no dispatch, which is
    /// the distinction a per-input loop would lose. Zero as well after an encode
    /// that returned an error before dispatching, because the tally describes the
    /// most recent call rather than the most recent success.
    ///
    /// Meaningful for one caller at a time. `encode` takes `&self` so a
    /// tokenizer can be shared, and two concurrent encodes then overwrite each
    /// other's tally; the ids are unaffected, since nothing else on the path is
    /// mutable.
    #[must_use]
    pub fn last_dispatch_count(&self) -> usize {
        self.dispatches.load(Ordering::Relaxed)
    }

    /// Output-assembly convergence checks and per-segment guard queries,
    /// since this tokenizer was created, as `(batch_checks, segment_guards)`.
    ///
    /// Exists for tests and cost accounting. The assembly asks ONE batch-level
    /// convergence question per dispatch and, on the converged path, nothing
    /// per segment: an encode of D converged dispatches over P device
    /// pretokens returns `(D, 0)` here, where the per-segment assembly it
    /// replaced would have returned a guard count of P. A nonzero guard count
    /// means a dispatch exhausted its pass budget and the fallible per-segment
    /// path ran; that path is what [`ExatokError::Divergence`] comes from.
    ///
    /// Cumulative and shared, so meaningful for one caller at a time, exactly
    /// like [`Self::last_dispatch_count`]: two concurrent encodes add to the
    /// same pair, and a reader wanting a per-encode figure brackets one
    /// encode with two reads.
    #[must_use]
    pub fn output_assembly_tally(&self) -> (u64, u64) {
        (
            self.output_batch_checks.load(Ordering::Relaxed),
            self.output_segment_guards.load(Ordering::Relaxed),
        )
    }

    /// Pair-table lookups and merges the host route has issued since this
    /// tokenizer was created, as `(lookups, merges)`.
    ///
    /// Exists for tests and cost accounting. The host arm merges over
    /// maintained pair ranks, refreshing only the two pairs adjacent to each
    /// merge site, so an encode's lookup delta lands near one per host-routed
    /// token plus at most two per merge, where the full rescan it replaced
    /// paid one per SURVIVING pair per pass, quadratic on a collapsing run.
    /// Both produce the same ids, so only a counted comparison can see a
    /// reroute back to the rescan: `tests/host_route_merge_cost.rs` pins the
    /// delta on a fixed corpus against both counts.
    ///
    /// Cumulative and shared, so meaningful for one caller at a time, exactly
    /// like [`Self::last_dispatch_count`]: two concurrent encodes add to the
    /// same pair, and a reader wanting a per-encode figure brackets one
    /// encode with two reads. An encode that fails mid-walk has already
    /// tallied the inputs whose walks completed, since those lookups were
    /// genuinely paid.
    #[must_use]
    pub fn host_merge_tally(&self) -> (u64, u64) {
        (
            self.host_lookups.load(Ordering::Relaxed),
            self.host_merges.load(Ordering::Relaxed),
        )
    }

    /// A span outside its own input. Unreachable through the public API, since
    /// `spans` reports ranges inside the input it was given, but reported rather
    /// than sliced past the end so the path is total.
    fn span_error(&self, input_index: usize, span: Span, len: usize) -> ExatokError {
        ExatokError::Artifact {
            artifact: format!("{} input", self.encoding.artifact()),
            location: format!("input {input_index}, bytes {}..{}", span.start, span.end),
            detail: format!("this pretoken span falls outside the {len}-byte input"),
            fix: "this is a defect in crate::pretokenize, whose spans must lie inside their \
                  input; report it rather than working around it"
                .to_owned(),
        }
    }
}

// ---------------------------------------------------------------------------
// A bound tokenizer
// ---------------------------------------------------------------------------

/// A [`DeviceTokenizer`] bound to one backend, holding what an encode should not
/// have to rebuild.
///
/// Two costs a single call cannot amortize, both measured rather than supposed:
/// the 16 MiB resident merge table, at 2.816 ms of upload and 0.140 ms of free
/// per encode on prose, and the flat buffers an encode writes its start states
/// and converged ids into. A session pays the upload once and reuses the buffers,
/// so the second and every later encode skips all of it.
///
/// It borrows the tokenizer AND the backend, and that is the point rather than an
/// inconvenience: vyre's resident ids come from a counter private to one backend
/// INSTANCE, so a handle outliving its backend would not dangle visibly, it would
/// name a live buffer belonging to a different backend. Binding a wrong 16 MiB
/// table produces wrong merges, and wrong merges return plausible ids, which is
/// the one failure this crate exists to rule out. The borrow makes that
/// unrepresentable instead of merely unlikely.
///
/// Shareable across threads, and the ids are unaffected by sharing: the resident
/// table is read-only for a dispatch's whole life, and the buffers come one set
/// per encode from [`SCRATCH_POOL_LIMIT`]'s pool.
///
/// Ids are byte-identical to [`DeviceTokenizer::encode_batch`]'s, by construction
/// rather than by testing: both entry points run the same
/// `encode_batch_probed` body over the same buffers, differing only in
/// [`TableSource`], which decides who OWNS the table and never what is in it.
pub struct DeviceSession<'a> {
    tokenizer: &'a DeviceTokenizer,
    backend: &'a dyn VyreBackend,
    /// The resident merge table, uploaded at [`DeviceTokenizer::bind`].
    ///
    /// `None` on a backend with no resident dispatch, where every encode passes
    /// the table as an ordinary host input exactly as the unbound path does
    /// there. Also `None` after [`Self::close`], which is what keeps [`Drop`]
    /// from freeing a buffer twice.
    table: Option<Resource>,
    /// The packed table, serialized once at [`DeviceTokenizer::bind`].
    ///
    /// Borrowed from the tokenizer's own cell rather than copied, so a session
    /// costs 16 MiB of upload and nothing of host memory. Held even when
    /// [`Self::table`] is `None`: a backend without resident dispatch binds these
    /// bytes as an ordinary host input on every dispatch, and it should not have to
    /// go back through the tokenizer to find them.
    table_bytes: &'a [u8],
    scratch: Mutex<Vec<Scratch>>,
}

impl DeviceSession<'_> {
    /// Encode many inputs, reusing the session's table and buffers.
    ///
    /// Identical to [`DeviceTokenizer::encode_batch`] in every observable way,
    /// including [`Routing`] and [`DeviceTokenizer::last_dispatch_count`]. What
    /// differs is what it does NOT do: no table allocation, upload or free, and
    /// no per-pretoken buffer.
    ///
    /// # Errors
    ///
    /// See [`DeviceTokenizer::encode_batch`].
    pub fn encode_batch(&self, inputs: &[&[u8]]) -> Result<Encoded, ExatokError> {
        self.encode_probed(inputs, &mut Untimed)
    }

    /// [`Self::encode_batch`], reporting where its host time went.
    ///
    /// [`EncodePhase::TableUpload`], [`EncodePhase::TablePack`] and
    /// [`EncodePhase::TableFree`] read ZERO here, which is the comparison against
    /// [`DeviceTokenizer::encode_batch_profiled`] those rows exist to make.
    ///
    /// # Errors
    ///
    /// See [`DeviceTokenizer::encode_batch`].
    pub fn encode_batch_profiled(
        &self,
        inputs: &[&[u8]],
    ) -> Result<(Encoded, EncodeProfile), ExatokError> {
        let mut probe = Timed::start();
        let encoded = self.encode_probed(inputs, &mut probe);
        let profile = probe.finish();
        encoded.map(|ids| (ids, profile))
    }

    /// Encode bytes, reusing the session's table and buffers.
    ///
    /// A STEP-FOR-STEP mirror of [`DeviceTokenizer::encode`], including the
    /// delegation to `encode_batch` with a one-input slice, so both paths dispatch
    /// the identical shape and neither can drift from the other. That is the whole
    /// reason this exists rather than callers writing `encode_batch(&[input])`
    /// themselves: `encode_batch` flattens pretokens across INPUT boundaries and
    /// fills each dispatch from the combined list, so a caller who reaches for it
    /// to encode one input is choosing a different grouping than `encode` would,
    /// and a benchmark cell that did so would silently measure a different
    /// operation than its name says. With one input the two are the same thing,
    /// which is exactly what makes this delegation safe and a multi-input
    /// substitution unsafe.
    ///
    /// Bytes, not `&str`, for [`DeviceTokenizer::encode`]'s reason: pretokenization
    /// splits bytes and input need not be valid UTF-8.
    ///
    /// # Errors
    ///
    /// See [`DeviceTokenizer::encode_batch`].
    pub fn encode(&self, input: &[u8]) -> Result<Vec<TokenId>, ExatokError> {
        let mut per_input = self.encode_batch(&[input])?.into_ids();
        Ok(per_input.pop().unwrap_or_default())
    }

    /// Give the resident table back and report whether the backend accepted it.
    ///
    /// [`Drop`] does the same thing and cannot report, because a destructor that
    /// returns nothing has nowhere to put a failure and a panicking one during
    /// unwinding aborts. So a caller who needs to KNOW the 16 MiB went back calls
    /// this, and every other caller lets the session fall out of scope. Calling
    /// this is not required for correctness: the buffer is freed either way.
    ///
    /// Consumes the session, so the freed handle cannot be described to a later
    /// encode, and takes the table out before dropping, so the [`Drop`] that
    /// follows finds `None` and does not free it a second time.
    ///
    /// # Errors
    ///
    /// Returns [`ExatokError::Backend`] when the backend refuses the free. The
    /// buffer is not retried and not leaked back into the session: the handle is
    /// already gone from it, and a backend that will not free a resident buffer
    /// it minted will not free it on a second ask either.
    pub fn close(mut self) -> Result<(), ExatokError> {
        let Some(resource) = self.table.take() else {
            return Ok(());
        };
        self.backend.free_resident(resource).map_err(|error| {
            ExatokError::Backend(format!(
                "device resident table free failed: {error}. \
                 Fix: destroy and re-acquire the device context, and do not reuse a \
                 session whose table could not be freed"
            ))
        })
    }

    /// One encode over the session's table and a pooled [`Scratch`].
    ///
    /// The pool round trip is charged to [`EncodePhase::Teardown`], which is where
    /// the per-pretoken frees it replaced were charged. That keeps the row
    /// comparable between the two paths rather than making a cost disappear from
    /// the table by moving it outside every measured region.
    ///
    /// # Errors
    ///
    /// See [`DeviceTokenizer::encode_batch`].
    fn encode_probed<P: PhaseProbe>(
        &self,
        inputs: &[&[u8]],
        probe: &mut P,
    ) -> Result<Encoded, ExatokError> {
        let mut scratch = probe.measure(EncodePhase::Teardown, |_| {
            self.scratch
                .lock()
                .unwrap_or_else(PoisonError::into_inner)
                .pop()
                .unwrap_or_default()
        });
        let encoded = self.tokenizer.encode_batch_probed(
            self.backend,
            inputs,
            probe,
            TableSource::Session {
                table: self.table.as_ref(),
                bytes: self.table_bytes,
            },
            &mut scratch,
        );
        // Returned even when the encode FAILED, because the capacity is worth
        // keeping either way and the next encode empties it before reading it:
        // `encode_batch_probed` resets the scratch on entry, which is precisely
        // why that reset is at the start of an encode and not at the end.
        probe.measure(EncodePhase::Teardown, |_| {
            let mut pool = self.scratch.lock().unwrap_or_else(PoisonError::into_inner);
            if pool.len() < SCRATCH_POOL_LIMIT {
                pool.push(scratch);
            }
        });
        encoded
    }
}

impl Drop for DeviceSession<'_> {
    /// Free the resident table, silently.
    ///
    /// Silently because there is nowhere to report: a destructor returns nothing,
    /// and panicking here would abort the process whenever a session dropped
    /// during unwinding, turning a recoverable error into a crash. A caller who
    /// needs the outcome calls [`Self::close`], which exists for exactly this
    /// reason.
    fn drop(&mut self) {
        if let Some(resource) = self.table.take() {
            drop(self.backend.free_resident(resource));
        }
    }
}

impl std::fmt::Debug for DeviceSession<'_> {
    /// Hand-written because `&dyn VyreBackend` is not [`Debug`], and naming the
    /// backend by its own report rather than by its type keeps a two-device
    /// session pair distinguishable in a test failure.
    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        formatter
            .debug_struct("DeviceSession")
            .field("encoding", &self.tokenizer.encoding.artifact())
            .field("backend", &self.backend.id())
            .field("resident_table", &self.table.is_some())
            .field(
                "pooled_scratch",
                &self
                    .scratch
                    .lock()
                    .unwrap_or_else(PoisonError::into_inner)
                    .len(),
            )
            .finish()
    }
}

#[cfg(test)]
mod tests {
    // Matches the exemption every other test module in this crate carries; see
    // `reference.rs` and `parity.rs`. `Cargo.toml` denies these three crate-wide,
    // which is right for library code and wrong for tests: a test asserts by
    // panicking, so `assert!` is already an allowed panic and `expect` on a
    // fixture that cannot fail is the same statement with a message attached.
    #![allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]

    use super::*;

    /// Locks out reintroducing a hand-rolled liveness guard in the pass body.
    ///
    /// This exists because the defect is INVISIBLE to every behavioral test in
    /// `tests/device_api.rs`. Substituting `lane() < shape.state_words()` for
    /// [`lane_is_live`] leaves all ten of them green on a 5090, measured by
    /// mutation, because a tail lane's coordinates resolve to the next group's
    /// first segment where the reset is idempotent, the votes are absent over
    /// DEAD_SLOT padding, and the emit is overwritten by `close_pass`. The one
    /// real consequence is a store past the end of NAME_BPE_PICK in the final
    /// group, which this backend does not trap.
    ///
    /// So the guard is pinned structurally instead: it must be gpu_loop's own
    /// published predicate, not an arithmetic restatement that happens to look
    /// right. Comparing against `lane_is_live(shape)` is not circular, because
    /// what it forbids is the pass body computing liveness itself.
    #[test]
    fn the_pass_body_guards_every_phase_with_the_loops_own_predicate() {
        // A stride that leaves a real tail: 256 words hold 51 segments of stride
        // 5 with 1 word left over, and 300 segments need 6 groups. Both kinds of
        // idle lane therefore exist in this shape.
        let shape = LoopShape::new(300, 4, 8);
        assert!(
            shape.groups() > 1 && shape.words_per_group() > shape.segments_per_group() * 5,
            "the fixture must have BOTH a per-group tail and more than one group, \
             or it cannot distinguish the two guards"
        );

        let body = bpe_merge_body(shape, 1 << 12, 8);
        let expected = lane_is_live(shape);
        let guards: Vec<&Expr> = body
            .iter()
            .filter_map(|node| match node {
                Node::If { cond, .. } => Some(cond),
                _ => None,
            })
            .collect();
        assert_eq!(
            guards.len(),
            4,
            "all four phases must be guarded; a phase spliced in unguarded is the \
             defect this test exists for"
        );
        for (phase, guard) in guards.iter().enumerate() {
            assert_eq!(
                **guard, expected,
                "phase {phase} must guard on lane_is_live(shape) verbatim"
            );
        }
    }

    /// Locks out dropping or reordering a phase barrier.
    ///
    /// Also unreachable behaviorally on the cheap path: the reference
    /// interpreter runs lanes sequentially, so a deleted barrier has NO effect
    /// there, and on a real device a missing barrier is a race that can pass.
    /// The phase structure is the invariant, so assert the structure.
    #[test]
    fn every_phase_of_the_pass_body_is_separated_by_a_barrier() {
        let body = bpe_merge_body(LoopShape::new(300, 4, 8), 1 << 12, 8);
        let kinds: Vec<&str> = body
            .iter()
            .map(|node| match node {
                Node::If { .. } => "phase",
                Node::Barrier { .. } => "barrier",
                _ => "other",
            })
            .collect();
        assert_eq!(
            kinds,
            ["phase", "barrier", "phase", "barrier", "phase", "barrier", "phase"],
            "reset, rank vote, index vote and emit must alternate with barriers: \
             each phase reads what the previous one wrote"
        );
    }

    /// Locks out a batcher that drops, duplicates or silently reorders inputs.
    ///
    /// [`batches`] returns ORIGINAL indices precisely so a reordering mode cannot
    /// permute the output, and `encode_batch` scatters results back by those
    /// indices. If a mode ever lost an index, that input would encode to an empty
    /// id vector rather than failing, which is the worst possible outcome for a
    /// tokenizer: silently short output.
    ///
    /// Swept over workgroup budgets as well as modes, because the per-dispatch
    /// segment count is now a device-queried number rather than a constant 1. A
    /// partition bug that only appears once several workgroups fit in one dispatch
    /// would otherwise be invisible on this device and appear on another.
    #[test]
    fn every_batching_mode_partitions_the_inputs_exactly_once() {
        // Deliberately spans the spread bound and the per-dispatch count, with
        // duplicate lengths so the sort's tie handling is exercised.
        let lengths = [1_usize, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 2, 1];
        let pretokens = runs_of_lengths(&lengths);

        for workgroups in [1_u32, 3, 64, 765] {
            for mode in [Batching::InputOrder, Batching::ByLength] {
                let batches = batches(&pretokens, mode, workgroups);
                let mut seen: Vec<usize> = batches.iter().flatten().copied().collect();
                seen.sort_unstable();
                assert_eq!(
                    seen,
                    (0..pretokens.len()).collect::<Vec<_>>(),
                    "{mode:?} at {workgroups} workgroups must cover every input index exactly once"
                );
                assert!(
                    batches.iter().all(|batch| !batch.is_empty()),
                    "{mode:?} at {workgroups} workgroups must not emit an empty dispatch"
                );
            }
        }
    }

    /// Locks out a batch whose stride spread or segment count exceeds what a
    /// single dispatch is sized for.
    ///
    /// These are the two bounds [`batches`] exists to enforce, and neither is
    /// observable from encoded ids: a batch over the spread bound still produces
    /// CORRECT ids, just after padding every short pretoken out to the longest
    /// one and spinning it through passes it did not need. A regression here is a
    /// silent throughput cliff, so it has to be asserted directly.
    ///
    /// The segment bound is the one that keeps a grid inside the device's
    /// cooperative residency, so it is checked at every workgroup budget rather
    /// than at the single one this card happens to admit.
    #[test]
    fn no_batch_exceeds_the_stride_spread_or_the_per_dispatch_segment_count() {
        let lengths = [1_usize, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 2, 1];
        let pretokens = runs_of_lengths(&lengths);

        for workgroups in [1_u32, 3, 64, 765] {
            for mode in [Batching::InputOrder, Batching::ByLength] {
                for batch in batches(&pretokens, mode, workgroups) {
                    let strides: Vec<usize> =
                        batch.iter().map(|i| pretokens[*i].len + 1).collect();
                    let widest = *strides.iter().max().expect("no empty batch");
                    let narrowest = *strides.iter().min().expect("no empty batch");
                    assert!(
                        batch.len() == 1 || widest <= MAX_STRIDE_SPREAD * narrowest,
                        "{mode:?} batch {batch:?} spans strides {narrowest}..={widest}, \
                         past the {MAX_STRIDE_SPREAD}x spread bound"
                    );
                    assert!(
                        batch.len() <= segments_per_dispatch(widest - 1, workgroups),
                        "{mode:?} batch of {} segments exceeds what one {workgroups}-workgroup \
                         dispatch of stride {widest} can carry",
                        batch.len()
                    );
                }
            }
        }
    }

    /// Locks out a single-pretoken batch being refused for spread.
    ///
    /// A lone pretoken has a spread of exactly 1 against itself, so the bound
    /// must never split it out into nothing. The guard for this is the
    /// `!current.is_empty()` term in [`batches`]; without it a corpus of one long
    /// pretoken would emit an empty leading dispatch, and with a strict rather
    /// than non-strict comparison the longest legal pretoken would batch alone
    /// forever.
    #[test]
    fn the_longest_legal_pretoken_still_forms_one_batch_on_its_own() {
        let solo = runs_of_lengths(&[MAX_PRETOKEN_TOKENS]);
        for workgroups in [1_u32, 765] {
            for mode in [Batching::InputOrder, Batching::ByLength] {
                assert_eq!(
                    batches(&solo, mode, workgroups),
                    vec![vec![0_usize]],
                    "{mode:?} must place a lone cap-length pretoken in exactly one batch"
                );
            }
        }
    }

    /// Locks out asking the device for every block it says it can hold.
    ///
    /// The queried ceiling bounds THREAD residency only, and the stricter
    /// per-kernel bound that register pressure imposes is enforced at launch, so a
    /// dispatch sized at exactly the ceiling can be refused by the device while
    /// the query said yes. The headroom is what keeps one added register in the
    /// pass body from becoming a launch failure, so it is asserted as a real
    /// reduction and not merely as "at most the ceiling": returning the ceiling
    /// unchanged would satisfy an upper-bound-only check.
    #[test]
    fn the_workgroup_budget_stays_strictly_under_a_real_ceiling() {
        assert_eq!(
            workgroups_within_headroom(1020),
            765,
            "three quarters of the 1020-block thread residency this device reports"
        );
        assert_eq!(workgroups_within_headroom(100), 75);
        assert!(
            workgroups_within_headroom(1020) < 1020,
            "the budget must be a REDUCTION of the ceiling, not the ceiling itself"
        );
    }

    /// Locks out a headroom rule that returns a grid of zero workgroups.
    ///
    /// Both inputs that produce it are real. Zero is what a backend permitting a
    /// host kernel split reports, the reference interpreter included, and a small
    /// ceiling rounds to zero under any percentage below 100. A dispatch of zero
    /// workgroups encodes nothing and would return empty ids for every pretoken in
    /// the batch, so the floor is load bearing rather than defensive.
    #[test]
    fn the_workgroup_budget_is_never_zero() {
        for ceiling in [0_u32, 1] {
            assert_eq!(
                workgroups_within_headroom(ceiling),
                1,
                "a ceiling of {ceiling} must still dispatch one workgroup"
            );
        }
        assert_eq!(
            workgroups_within_headroom(u32::MAX),
            3_221_225_471,
            "three quarters of the widest representable ceiling, computed in 64 bits: \
             a 32-bit product overflows here and a saturating one would report \
             42949672, a hundredth of the ceiling"
        );
        for ceiling in [1_u32, 2, 99, 100, 1020, 57_000_000, u32::MAX] {
            assert!(
                workgroups_within_headroom(ceiling) <= ceiling,
                "the budget must never exceed the ceiling it reduces, at {ceiling}"
            );
        }
    }

    /// Locks out probing residency with a single-group program.
    ///
    /// `cooperative_block_ceiling` returns zero for a program carrying no
    /// `GridSync` barrier, and only the multi-group form of the loop emits one. So
    /// a one-group probe shape reports "no cooperative launch at any grid size",
    /// the budget floors to one workgroup, and every dispatch is pinned to one
    /// group forever while every id stays exact. That is a pure throughput
    /// collapse with no failing assertion anywhere else in the crate, which is why
    /// the probe's group count is pinned here.
    #[test]
    fn the_residency_probe_shape_spans_more_than_one_workgroup() {
        let shape = residency_probe_shape();
        assert_eq!(
            shape.groups(),
            2,
            "the probe must span two groups, or the query answers about a program \
             with no grid barrier"
        );
        assert_eq!(
            shape.words_per_group(),
            LOOP_WORKGROUP_WIDTH,
            "the probe must plan blocks of the loop's own workgroup width, since \
             the ceiling is a function of that width"
        );
    }

    /// A tokenizer whose only job is to answer plan-cache questions.
    ///
    /// Built field by field rather than through [`DeviceTokenizer::new`] because
    /// the cache is decided by shape alone: `new` wants a real vocabulary, and a
    /// one-row table emits the same program structure a two-million-row one does.
    /// No backend and no artifact are involved, so these run anywhere.
    fn plan_cache_fixture() -> DeviceTokenizer {
        let table = RankTable::from_entries(
            "plan cache fixture",
            [(PairKey::new(TokenId(0), TokenId(1)), TokenId(2), Rank(0))],
        )
        .expect("a single-row table must build");
        DeviceTokenizer {
            encoding: Encoding::cl100k_base(),
            table,
            byte_token: [TokenId(0); 256],
            batching: Batching::default(),
            dispatches: AtomicUsize::new(0),
            block_ceilings: RwLock::new(Vec::new()),
            table_bytes: OnceLock::new(),
            plans: RwLock::new(Vec::new()),
            plan_hits: AtomicUsize::new(0),
            plan_misses: AtomicUsize::new(0),
            plan_rebuilds: AtomicU64::new(0),
            output_batch_checks: AtomicU64::new(0),
            output_segment_guards: AtomicU64::new(0),
            host_lookups: AtomicU64::new(0),
            host_merges: AtomicU64::new(0),
            workgroup_override: None,
        }
    }

    /// Host bytes the fixture's cache is holding, by the cache's own weight.
    fn held_bytes(device: &DeviceTokenizer) -> usize {
        device
            .plans
            .read()
            .unwrap_or_else(PoisonError::into_inner)
            .iter()
            .map(|(_, plan)| plan.retained_bytes())
            .sum()
    }

    /// The shapes the fixture's cache is holding, oldest first.
    fn held_shapes(device: &DeviceTokenizer) -> Vec<LoopShape> {
        device
            .plans
            .read()
            .unwrap_or_else(PoisonError::into_inner)
            .iter()
            .map(|(shape, _)| *shape)
            .collect()
    }

    /// A shape whose plan weight is almost entirely its pick seed.
    ///
    /// Wide and shallow on purpose. The seed is 8 bytes per segment while a
    /// two-pass program is 266 IR nodes however many segments there are, so this
    /// buys a multi-megabyte cache entry for the cost of one `Vec` fill instead of
    /// unrolling hundreds of waves. That keeps a ceiling test that has to build
    /// SEVERAL over-ceiling entries from taking minutes in a debug build, and it
    /// exercises the term a pass-weighted bound ignored completely.
    fn seed_heavy(segments: u32) -> LoopShape {
        LoopShape::new(segments, 1, 2)
    }

    /// One program per SHAPE, not one per dispatch.
    ///
    /// This is the whole point of the cache, and nothing else in the crate sees
    /// it: a cache that rebuilt on every call would return byte-identical IR, so
    /// every id stays exact and every parity suite stays green while the path pays
    /// about 1565 host allocations per pass of the budget on every dispatch.
    /// Pointer identity is the only observation that separates the two.
    ///
    /// The second half is just as load bearing. A cache keyed too coarsely, on the
    /// segment count alone say, would hand a dispatch a program built for a
    /// different stride, and THAT is a wrong-ids defect rather than a cost one.
    #[test]
    fn the_plan_cache_serves_one_program_per_shape() {
        let device = plan_cache_fixture();
        let shape = LoopShape::new(8, 4, 5);

        let first = device.dispatch_plan(shape);
        let second = device.dispatch_plan(shape);
        assert!(
            Arc::ptr_eq(&first, &second),
            "a repeated shape must return the plan already built, or construction \
             is still per dispatch"
        );

        // Each differs from `shape` in exactly one component, so a key that
        // ignored any one of the three would collide here.
        for other in [
            LoopShape::new(9, 4, 5),
            LoopShape::new(8, 5, 5),
            LoopShape::new(8, 4, 6),
        ] {
            let plan = device.dispatch_plan(other);
            assert!(
                !Arc::ptr_eq(&first, &plan),
                "{other:?} differs from {shape:?} and must not be served that \
                 shape's program"
            );
        }
    }

    /// The cache is bounded, so a long-lived tokenizer cannot leak.
    ///
    /// `encode_batch` takes `&self`, so anything cached lives as long as the
    /// tokenizer, and shape varies with the longest pretoken in a batch. An
    /// unbounded map keyed on shape therefore grows with corpus diversity for the
    /// process lifetime, which is a leak wearing an optimization's clothes.
    ///
    /// WHICH entry goes is asserted as hard as the bound, and it is asserted
    /// against the recency order rather than alongside it. The victim here sits in
    /// the MIDDLE of the vector, so an oldest-first sweep and a cheapest-first
    /// sweep name different entries and the two cannot both pass. Oldest-first is
    /// what produced the [`EncodePhase::PlanLookup`] cliff: an encode walks its
    /// length bands longest first, so the oldest entry is the widest plan, and
    /// discarding it to admit a cheap one is the single worst choice available.
    #[test]
    fn the_plan_cache_evicts_the_cheapest_to_rebuild_past_its_byte_ceiling() {
        let device = plan_cache_fixture();
        // Four wide entries that fit together at 66770272 bytes, 338592 short of
        // the ceiling, with a cheap one inserted third so it is neither the oldest
        // nor the newest when the sweep runs. Sized so that dropping the cheap
        // entry alone brings the cache back under: a fixture where the sweep had to
        // take two entries would not say which rule chose the second.
        let wide = [
            seed_heavy(2_400_000),
            seed_heavy(2_200_000),
            seed_heavy(2_000_000),
            seed_heavy(1_700_000),
        ];
        let cheap = seed_heavy(400_000);

        let widest = device.dispatch_plan(wide[0]);
        device.dispatch_plan(wide[1]);
        let cheap_plan = device.dispatch_plan(cheap);
        assert!(
            held_bytes(&device) <= PLAN_CACHE_BYTES,
            "the fixture must still be under the ceiling before the entry that \
             overflows it, or the sweep under test has already run: {} bytes",
            held_bytes(&device)
        );
        device.dispatch_plan(wide[2]);
        device.dispatch_plan(wide[3]);

        assert!(
            held_bytes(&device) <= PLAN_CACHE_BYTES,
            "the cache must respect its own ceiling: {} bytes held against {}",
            held_bytes(&device),
            PLAN_CACHE_BYTES
        );
        assert_eq!(
            held_shapes(&device),
            wide.to_vec(),
            "the cheapest entry is the one that goes, and it was neither the \
             oldest nor the newest, so recency did not choose it"
        );
        assert!(
            Arc::ptr_eq(&widest, &device.dispatch_plan(wide[0])),
            "the widest plan must survive the sweep, since it is the one whose \
             rebuild costs the most"
        );
        assert!(
            !Arc::ptr_eq(&cheap_plan, &device.dispatch_plan(cheap)),
            "an evicted shape must be rebuilt rather than resurrected, which is \
             what makes the worst case merely the cost before this cache existed"
        );
    }

    /// A plan too big for the whole ceiling is still cached.
    ///
    /// The bound is on the SUM, so an entry whose own weight exceeds it would be
    /// evicted the instant it was inserted under a naive rule, and a corpus that
    /// produces only such shapes would cache nothing at all. That is the case where
    /// rebuilding costs most, so it is exactly the case that must not fall through.
    /// `plans.len() > 1` in the sweep is the whole guarantee, and nothing else in
    /// the crate observes it.
    #[test]
    fn the_plan_cache_keeps_a_plan_heavier_than_its_whole_ceiling() {
        let device = plan_cache_fixture();
        // 8 bytes of seed per segment, so this is just over the ceiling on its own.
        let huge = seed_heavy(PLAN_CACHE_BYTES as u32 / 8 + 1);

        let first = device.dispatch_plan(huge);
        assert!(
            first.retained_bytes() > PLAN_CACHE_BYTES,
            "the fixture must actually exceed the ceiling by itself, or this \
             asserts nothing: {} bytes against {PLAN_CACHE_BYTES}",
            first.retained_bytes()
        );
        assert!(
            Arc::ptr_eq(&first, &device.dispatch_plan(huge)),
            "a plan heavier than the whole ceiling must still be reused, or the \
             widest dispatches pay full construction every time"
        );
    }

    /// Prose with the length spread real text has, repeated `repeats` times.
    ///
    /// Parameterized because the load-bearing measurement is how misses scale
    /// with corpus size, not their value at one size. A single size cannot
    /// distinguish "misses are bounded by the key space" from "misses are a
    /// fixed fraction of dispatches", and those are exactly a working cache and
    /// a broken one.
    fn prose_corpus(repeats: usize) -> String {
        let paragraph = "The tokenizer must agree with tiktoken byte for byte, \
             which is a stronger claim than agreeing on average. A merge table \
             lookup that returns the wrong rank for one pair in ten million \
             still produces plausible text, and plausible is the failure mode \
             that survives review. Exactness is checked against the reference \
             implementation on every commit, over a corpus chosen to include \
             the cases that break naive implementations: combining marks, \
             zero-width joiners, unpaired surrogates written as replacement \
             characters, and runs of whitespace long enough to cross a \
             pretoken boundary.\n\n";
        paragraph.repeat(repeats)
    }

    /// Runs of the given token lengths, as [`batches`] takes them.
    ///
    /// The offsets tile a hypothetical state buffer, exactly as a real encode's
    /// do, even though [`batches`] reads only [`Run::len`]. Overlapping or
    /// duplicate offsets would still batch identically, so a run list that did
    /// NOT tile would quietly stop resembling the input the batcher really gets,
    /// and a later assertion that reads the words would be reading a fiction.
    fn runs_of_lengths(lengths: &[usize]) -> Vec<Run> {
        let mut start = 0_usize;
        lengths
            .iter()
            .map(|len| {
                let run = Run { start, len: *len };
                start += *len;
                run
            })
            .collect()
    }

    /// The device-bound pretokens' start states, exactly as `encode_batch` builds
    /// them.
    ///
    /// Through [`Scratch::push_start_state`] and the routing rule rather than a
    /// restated length filter: a pretoken past [`MAX_PRETOKEN_TOKENS`] goes to the
    /// host and is never handed to [`batches`], so counting it here would measure
    /// a batch plan the encoder never asks for. Returning the [`Scratch`] itself
    /// keeps the flat layout the encoder batches over, so a test cannot batch a
    /// shape the encoder would not.
    fn device_words(device: &DeviceTokenizer, corpus: &str) -> Scratch {
        let mut scratch = Scratch::default();
        for span in spans(device.encoding.pattern(), corpus.as_bytes()) {
            let Some(bytes) = span.bytes(corpus.as_bytes()) else {
                continue;
            };
            if bytes.len() > MAX_PRETOKEN_TOKENS {
                continue;
            }
            scratch.push_start_state(bytes, &device.byte_token);
        }
        scratch
    }

    /// Drives the real batch plan through the real cache and returns the tally.
    ///
    /// Every step is the encoder's own: [`batches`] for the grouping, the
    /// `merge_pass_bound(longest) + 1` budget from `encode_batch`, and
    /// [`LoopBatch::new`] for the shape. Nothing here recomputes a shape by hand,
    /// because a hand-rolled shape would measure the hit rate of a cache the
    /// encoder does not use. The budget goes through [`merge_pass_bound`] for the
    /// same reason: if the encoder's budget ever changes, this mirror must move
    /// with it rather than silently measuring a shape the encoder stopped using.
    fn tally(device: &DeviceTokenizer, words: &Scratch, workgroups: u32) -> (usize, usize) {
        for batch_indices in batches(&words.state_runs, device.batching, workgroups) {
            let batch_words: Vec<&[u32]> = batch_indices
                .iter()
                .map(|index| words.state_runs[*index].of(&words.state))
                .collect();
            let longest = batch_words
                .iter()
                .map(|word| word.len())
                .max()
                .unwrap_or(1) as u32;
            let shape = LoopBatch::new(&batch_words, merge_pass_bound(longest) + 1).shape();
            device.dispatch_plan(shape);
        }
        device.plan_cache_tally()
    }

    /// The distinct shapes ONE `cjk` encode dispatches, as measured.
    ///
    /// Transcribed from a counted run of `examples/encode_profile` over the 262144
    /// byte `cjk` corpus at this device's 765 workgroups per dispatch: six
    /// dispatches, six distinct shapes, budgets summing to 189 pass waves. Hardcoded
    /// rather than re-derived from a corpus, because the property under test is
    /// about the CACHE and a fixture that regenerated the shape set would silently
    /// stop straddling the ceiling if pretokenization or banding changed. A drift
    /// there should change this list deliberately, with the new counts recorded.
    const CJK_ENCODE_WORKING_SET: [LoopShape; 6] = [
        LoopShape::new(1530, 91, 92),
        LoopShape::new(2635, 52, 53),
        LoopShape::new(1897, 25, 26),
        LoopShape::new(2560, 10, 11),
        LoopShape::new(3129, 4, 5),
        LoopShape::new(1709, 1, 2),
    ];

    /// A multi-band encode does not rebuild every plan on every encode.
    ///
    /// THE CLIFF THIS LOCKS OUT. The bound used to be on the SUM of cached shapes'
    /// pass budgets, at 128. One encode's working set is the distinct shapes its
    /// batch plan produces, each dispatched exactly once, and the next encode of
    /// the same bytes asks for the same set in the same order. So a ceiling below
    /// that working set makes the access pattern cyclic over a too-small cache,
    /// which no eviction order can rescue: every entry is evicted before it is
    /// asked for again. Counted at the time: `prose` summed to 50 passes and reused
    /// all four of its plans, while `cjk` summed to 189 and `code` to 179 and BOTH
    /// rebuilt all six of theirs on every single encode, 6 misses and 0 hits per
    /// encode over four consecutive encodes. In wall time that was
    /// [`EncodePhase::PlanLookup`] at 5.0030 ms on `cjk` against 0.0009 ms on
    /// `prose`, three orders of magnitude apart on the same 262144 bytes.
    ///
    /// A rebuild COUNT and not a duration, so no amount of foreign load on this box
    /// can flake it and no amount of foreign load can hide the regression either.
    /// The counts are exact: six builds for six first-time shapes, then zero,
    /// forever. A cache that regressed to any bound below this working set would
    /// report six again on the second round.
    ///
    /// IF IT REGRESSES: every encode over long pretokens pays about 1565 host
    /// allocations per pass of budget, 189 passes' worth here, and it pays that on
    /// EVERY encode rather than once. Ids stay byte-identical, so every parity and
    /// determinism suite stays green while the encode wall grows by milliseconds.
    ///
    /// WHAT THIS TEST CANNOT SEE, and which sibling covers it. This test is blind
    /// to eviction ORDER, and provably so: it was run against a tree with
    /// cheapest-first eviction reverted to oldest-first, ceiling unchanged, and it
    /// stayed GREEN. The reason is structural rather than accidental. Its working
    /// set fits under the ceiling, so the sweep never executes, so no ordering rule
    /// inside the sweep is reachable from here. The half it DOES cover is the
    /// ceiling: reverting the bound to the old pass sum turns it red at
    /// [(0, 6), (1, 5), (1, 5)]. Eviction order is covered by
    /// [`a_working_set_past_the_ceiling_keeps_reusing_its_widest_plans`], which
    /// goes red under EITHER revert, and the fits-under-the-ceiling precondition
    /// that makes order unobservable here is pinned by
    /// [`a_working_set_under_the_ceiling_never_evicts`]. The three look redundant
    /// and are not: delete this one and the ceiling loses its encode-shaped
    /// witness, delete that one and eviction order loses its only witness.
    #[test]
    fn a_multi_band_encode_rebuilds_no_plan_after_the_first_encode() {
        let device = plan_cache_fixture();
        let budget: u32 = CJK_ENCODE_WORKING_SET
            .iter()
            .map(|shape| shape.max_passes())
            .sum();
        assert_eq!(
            budget, 189,
            "the fixture must be the measured working set, 189 pass waves over six \
             shapes, or it no longer describes the encode that had the cliff"
        );

        let mut previous = (0_usize, 0_usize);
        let mut per_round: Vec<(usize, usize)> = Vec::new();
        for _ in 0..3 {
            // Longest band first, exactly as `batches` orders a `ByLength` encode,
            // because the order is what made oldest-first eviction pathological.
            for shape in CJK_ENCODE_WORKING_SET {
                device.dispatch_plan(shape);
            }
            let now = device.plan_cache_tally();
            per_round.push((now.0 - previous.0, now.1 - previous.1));
            previous = now;
        }

        assert_eq!(
            per_round,
            vec![(0, 6), (6, 0), (6, 0)],
            "the first encode must build all six plans and no later encode may \
             build any: (hits, misses) per encode was {per_round:?}"
        );
        // Strict, and by a stated margin. `<=` would also hold at a ceiling
        // exactly equal to the working set, where the sweep starts firing and the
        // reuse above becomes order-dependent. The margin is the precondition.
        assert!(
            held_bytes(&device) < PLAN_CACHE_BYTES,
            "reuse must not have come from an unbounded cache: {} bytes held \
             against {PLAN_CACHE_BYTES}",
            held_bytes(&device)
        );
        assert_eq!(
            held_shapes(&device),
            CJK_ENCODE_WORKING_SET.to_vec(),
            "the whole working set must be resident, in insertion order, with \
             nothing evicted"
        );
    }

    /// The measured working set fits under the ceiling with room to spare.
    ///
    /// The precondition [`a_multi_band_encode_rebuilds_no_plan_after_the_first_encode`]
    /// depends on and never states. That test reuses all six plans because the
    /// sweep never fires, not because the sweep is correct, and a reader cannot
    /// tell those apart from its assertions. This one names the reason: total
    /// retained bytes strictly under [`PLAN_CACHE_BYTES`], so `plans` is never
    /// swept, so eviction order is unreachable and its blindness is a documented
    /// boundary rather than an accident.
    ///
    /// WHY A MARGIN AND NOT JUST AN INEQUALITY. This is the test that fails FIRST,
    /// and with a legible message, if someone lowers the ceiling or raises
    /// [`PLAN_BYTES_PER_IR_NODE`] until the measured working set stops fitting.
    /// Without it the first symptom is a rebuild-count test reporting a strange
    /// hit pattern, which reads as an eviction-order bug and sends the reader into
    /// the wrong half of the cache.
    ///
    /// IF IT REGRESSES: nothing is wrong yet, but the cliff is one step away. The
    /// margin here is the whole safety factor between a corpus that reuses its
    /// plans and one that thrashes, so a shrinking margin is the early warning the
    /// original cliff never had.
    #[test]
    fn a_working_set_under_the_ceiling_never_evicts() {
        let device = plan_cache_fixture();
        for shape in CJK_ENCODE_WORKING_SET {
            device.dispatch_plan(shape);
        }

        // Probed on this fixture, not derived: `retained_bytes` summed over the six
        // plans the measured `cjk` working set builds.
        assert_eq!(
            held_bytes(&device),
            8_793_760,
            "the measured working set's host weight is pinned, so a change in plan \
             size or in PLAN_BYTES_PER_IR_NODE has to be acknowledged here"
        );
        // 8793760 of 67108864 bytes, so the working set occupies 13.1 percent of
        // the ceiling and clears it by 7.6x. Asserted as a ratio and not just an
        // inequality so that a ceiling cut to a quarter still fails HERE, with the
        // margin named, rather than surfacing as a puzzling hit pattern elsewhere.
        assert!(
            held_bytes(&device) * 4 < PLAN_CACHE_BYTES,
            "the measured working set must clear the ceiling by at least 4x, or the \
             cliff is one corpus away: {} bytes against {PLAN_CACHE_BYTES}",
            held_bytes(&device)
        );
        assert_eq!(
            held_shapes(&device).len(),
            CJK_ENCODE_WORKING_SET.len(),
            "every shape must still be resident, which is what proves the sweep \
             never fired: eviction is the only thing that removes an entry"
        );
    }

    /// A working set past the ceiling loses the CHEAP plans, not all of them.
    ///
    /// The companion to the test above, and the reason the fix is two changes and
    /// not one. Raising the ceiling removes the cliff for every corpus this
    /// batcher can produce, but a ceiling is still a ceiling, and the failure mode
    /// on the far side of it must be graceful rather than total. Under the old
    /// oldest-first sweep it was total: a cyclic access pattern over a cache
    /// smaller than the working set hits zero percent, whatever the ceiling is.
    ///
    /// Five entries weighing 80.5 MB against a 67.1 MB ceiling. Cheapest-first
    /// leaves the three widest permanently resident and rebuilds only the two
    /// cheapest, so the steady state is exactly 3 hits and 2 misses per round.
    /// Oldest-first would report 0 hits and 5 misses, so the two orders cannot both
    /// pass. Counts again, never durations.
    ///
    /// WHAT THIS TEST COVERS THAT ITS SIBLING CANNOT. This is the only witness for
    /// eviction ORDER. Verified by mutation: reverting cheapest-first to
    /// oldest-first with the ceiling left alone turns this red at 0 hits and 5
    /// misses per round while
    /// [`a_multi_band_encode_rebuilds_no_plan_after_the_first_encode`] stays fully
    /// green, because that test's working set fits and never reaches the sweep.
    /// Reverting the ceiling instead turns this red too, so it sees both halves.
    /// Do not delete it as a duplicate of the encode-shaped test: they overlap on
    /// the ceiling and only this one reaches the ordering rule.
    #[test]
    fn a_working_set_past_the_ceiling_keeps_reusing_its_widest_plans() {
        let device = plan_cache_fixture();
        let working_set = [
            seed_heavy(2_400_000),
            seed_heavy(2_200_000),
            seed_heavy(2_000_000),
            seed_heavy(1_800_000),
            seed_heavy(1_600_000),
        ];
        let weight: usize = working_set
            .iter()
            .map(|shape| {
                let device = plan_cache_fixture();
                device.dispatch_plan(*shape).retained_bytes()
            })
            .sum();
        assert!(
            weight > PLAN_CACHE_BYTES,
            "the fixture must not fit, or there is nothing to degrade: {weight} \
             bytes against {PLAN_CACHE_BYTES}"
        );

        let mut previous = (0_usize, 0_usize);
        let mut per_round: Vec<(usize, usize)> = Vec::new();
        for _ in 0..3 {
            for shape in working_set {
                device.dispatch_plan(shape);
            }
            let now = device.plan_cache_tally();
            per_round.push((now.0 - previous.0, now.1 - previous.1));
            previous = now;
        }

        assert_eq!(
            per_round[1..],
            [(3, 2), (3, 2)],
            "a working set past the ceiling must settle at three reused plans and \
             two rebuilt, not at zero reused: (hits, misses) per round was \
             {per_round:?}"
        );
        assert_eq!(
            held_shapes(&device)[..3],
            working_set[..3],
            "the three widest plans must be the resident ones, since they are the \
             three whose rebuild costs the most"
        );
        assert!(
            held_bytes(&device) <= PLAN_CACHE_BYTES,
            "degrading must still respect the ceiling: {} bytes held",
            held_bytes(&device)
        );
    }

    /// Misses track the SHAPE KEY SPACE, not the dispatch count.
    ///
    /// This is the gate `tests/encode_cost.rs` cannot provide. Those gates measure
    /// allocations charged to a dispatch, and a cache that missed every single
    /// time would still improve the FIRST dispatch and would still return
    /// byte-identical ids, so every correctness suite and every allocation delta
    /// would look exactly the same as a cache that works.
    ///
    /// Asserted as a scaling property rather than a threshold, because the
    /// threshold value is an accident of one corpus while the scaling is the
    /// actual claim: quadrupling the corpus quadruples the dispatches, and a
    /// working cache answers almost all of the new ones from shapes it already
    /// holds. [`MAX_STRIDE_SPREAD`] is what makes that true, grouping pretokens
    /// into doubling length bands so the distinct-shape count is bounded by the
    /// bands a corpus spans and not by how much text passes through.
    ///
    /// A cache keyed too finely, on a per-batch identity say, would miss once per
    /// dispatch and fail the growth bound while still passing every id check.
    ///
    /// REUSE IS EXPECTED ONLY WHERE THERE IS REUSE TO BE HAD, and that is a
    /// property of the key, not a cache defect. `LoopShape.segments` is the exact
    /// per-band pretoken count rather than a bucket, so distinct shapes recur only
    /// when a corpus produces many dispatches. At 1 and 3 workgroups the dispatch
    /// count far exceeds the shape count and reuse dominates; at 64 workgroups a
    /// whole corpus fits in four dispatches whose segment counts are all different,
    /// so there are ZERO hits and nothing to reuse. An earlier revision asserted
    /// `hits > misses` at every workgroup count, which is a RATIO claim that the
    /// comment beside it already explained must degrade as the dispatch count falls
    /// toward the key-space size; it was measured false at 64 workgroups (0 hits
    /// against 4 misses) and is corrected here rather than weakened away.
    ///
    /// The load-bearing claim is therefore the ADDITIVE miss bound, which holds at
    /// every workgroup count, plus domination where the dispatch count makes reuse
    /// possible at all.
    #[test]
    fn plan_cache_misses_do_not_grow_with_the_corpus() {
        for (workgroups, reuse_expected) in [(1_u32, true), (3, true), (64, false)] {
            let small = plan_cache_fixture();
            let large = plan_cache_fixture();
            let small_words = device_words(&small, &prose_corpus(16));
            let large_words = device_words(&large, &prose_corpus(64));

            let (small_hits, small_misses) = tally(&small, &small_words, workgroups);
            let (large_hits, large_misses) = tally(&large, &large_words, workgroups);
            let small_dispatches = small_hits + small_misses;
            let large_dispatches = large_hits + large_misses;

            println!(
                "{workgroups} workgroups: {small_hits}/{small_dispatches} reused \
                 then {large_hits}/{large_dispatches} at four times the corpus, \
                 {small_misses} then {large_misses} built"
            );
            assert!(
                large_dispatches > small_dispatches,
                "the larger corpus must actually cost more dispatches or this \
                 measures nothing: {small_dispatches} then {large_dispatches} at \
                 {workgroups} workgroups"
            );
            // The bound is ADDITIVE. Four times the text may reach a band or a
            // partial-batch segment count the smaller corpus never did, which is
            // a handful of new shapes, but it must not be a fraction of the new
            // dispatches.
            assert!(
                large_misses <= small_misses + 4,
                "misses must be bounded by the shapes a corpus spans, not its \
                 size: {small_misses} misses over {small_dispatches} dispatches \
                 grew to {large_misses} over {large_dispatches} at {workgroups} \
                 workgroups"
            );
            if reuse_expected {
                assert!(
                    large_hits > large_misses,
                    "the cache must reuse more than it builds at {workgroups} \
                     workgroups, where the dispatch count exceeds the shape count: \
                     {large_hits} hits against {large_misses} misses"
                );
            } else {
                // Not a weaker restatement: at this workgroup count the whole
                // corpus fits in a handful of dispatches with distinct segment
                // counts, so the claim is that the cache costs NOTHING when it
                // cannot help, never building a shape it already holds.
                assert_eq!(
                    large_misses, large_dispatches,
                    "with no shape recurring, every dispatch must be a first build \
                     and none may be built twice: {large_misses} misses over \
                     {large_dispatches} dispatches at {workgroups} workgroups"
                );
            }
        }
    }

    /// Every phase owns exactly one row, so no two costs share one.
    ///
    /// Locks out a variant added to [`EncodePhase`] and to
    /// [`EncodePhase::index`] but given a slot another variant already holds.
    /// That failure is silent and it is the worst kind for this table: two
    /// unrelated costs add into one row while another reads zero forever, so a
    /// reader attributes one owner's time to a different owner and the sum still
    /// looks right. `ALL.len()` is also what [`EncodeProfile`] sizes its storage
    /// from, so a slot past the end would panic rather than mislead, and the
    /// bound below is what keeps it in range.
    #[test]
    fn every_phase_owns_exactly_one_row_of_the_table() {
        let mut seen = [false; EncodePhase::ALL.len()];
        for phase in EncodePhase::ALL {
            let slot = phase.index();
            assert!(
                slot < seen.len(),
                "{} indexes slot {slot}, past the {} the profile allocates",
                phase.label(),
                seen.len()
            );
            assert!(
                !std::mem::replace(&mut seen[slot], true),
                "{} shares slot {slot} with an earlier phase, so their costs add \
                 into one row and some other row can only ever read zero",
                phase.label()
            );
        }
        let labels: BTreeMap<&str, ()> = EncodePhase::ALL
            .iter()
            .map(|phase| (phase.label(), ()))
            .collect();
        assert_eq!(
            labels.len(),
            EncodePhase::ALL.len(),
            "two phases print the same label, so a report cannot say which one a \
             row belongs to"
        );
    }

    /// A phase nested inside another is charged once, not to both.
    ///
    /// This is the property that makes the table an explanation rather than a
    /// story. Without the discount in [`Timed::measure`] the enclosing phase
    /// bills the inner body's time again, the named rows sum to more than the
    /// call took, and [`EncodeProfile::unattributed`] saturates to zero: a
    /// breakdown that claims to account for everything precisely when it has
    /// double counted. The encode nests exactly once, the host route inside the
    /// pretoken walk, and this is what keeps that honest.
    ///
    /// The inner body sleeps long enough to dominate the four clock reads that
    /// bracket it, so the double-counting failure is a factor of two rather than
    /// a margin, and the assertion does not depend on how fast the box is.
    #[test]
    fn a_nested_phase_is_charged_once_rather_than_to_both_rows() {
        let inner_body = Duration::from_millis(20);
        let mut probe = Timed::start();
        probe.measure(EncodePhase::ByteEncode, |probe| {
            probe.measure(EncodePhase::HostEncode, |_| {
                std::thread::sleep(inner_body);
            });
        });
        let profile = probe.finish();

        assert!(
            profile.phase(EncodePhase::HostEncode) >= inner_body,
            "the inner phase must carry the sleep: {:?}",
            profile.phase(EncodePhase::HostEncode)
        );
        assert!(
            profile.phase(EncodePhase::ByteEncode) < inner_body / 2,
            "the enclosing phase must keep only its OWN time, not the inner \
             body's: {:?} against an inner body of {inner_body:?}",
            profile.phase(EncodePhase::ByteEncode)
        );
        assert!(
            profile.named() <= profile.total(),
            "the named rows may never sum past the call they were measured \
             inside: {:?} named against {:?} total",
            profile.named(),
            profile.total()
        );
    }

    /// Time no phase measured lands in the remainder, not in a named row.
    ///
    /// The whole point of [`EncodeProfile::unattributed`] is to make an
    /// unexplained cost visible instead of persuasive. Locks out redefining the
    /// total as the sum of the named rows, which would report a perfect
    /// breakdown of a call whose cost was mostly somewhere else, and locks out a
    /// remainder that wraps: `Duration` subtraction past zero panics in debug
    /// and the saturating form is what keeps a coarse clock from turning a
    /// rounding tie into a several-hundred-year row.
    #[test]
    fn time_outside_every_phase_lands_in_the_remainder() {
        let unmeasured = Duration::from_millis(20);
        let mut probe = Timed::start();
        probe.measure(EncodePhase::Batching, |_| {});
        std::thread::sleep(unmeasured);
        let profile = probe.finish();

        assert!(
            profile.unattributed() >= unmeasured,
            "time no phase measured must show up as the remainder: {:?} against \
             {unmeasured:?} spent outside every phase",
            profile.unattributed()
        );
        assert_eq!(
            profile.named() + profile.unattributed(),
            profile.total(),
            "the named rows plus the remainder must be the observed call, or the \
             table is not a breakdown of anything"
        );
    }

    // -----------------------------------------------------------------------
    // Sessions, the scratch pool, and the flat arenas
    // -----------------------------------------------------------------------

    /// A tokenizer that really merges, over a backend that needs no device.
    ///
    /// [`plan_cache_fixture`] cannot serve these: its byte map sends every byte to
    /// [`TokenId`] 0 and its one row is keyed on a pair no byte produces, so
    /// nothing it encodes ever merges. Every pretoken would converge on its first
    /// pass to a run of equal ids, and a defect that returned the WRONG pretoken's
    /// ids, or the right ids at the wrong offset, would be invisible against a
    /// buffer of zeros.
    ///
    /// This fixture makes those defects observable, and each property is load
    /// bearing:
    /// - bytes map to themselves, so an id names the byte it came from and a
    ///   misdirected run reads as visibly foreign text;
    /// - the rows CHAIN, `(t,h)` then `(th,e)` then `(the,space)`, so a pretoken
    ///   takes several passes and the flat state is rewritten more than once;
    /// - the corpus's pretokens differ in length, so [`Batching::ByLength`] really
    ///   reorders them and the scatter back through
    ///   [`Scratch::device_slot`] is exercised rather than being the identity.
    fn merging_fixture() -> DeviceTokenizer {
        let mut byte_token = [TokenId(0); 256];
        for (byte, token) in byte_token.iter_mut().enumerate() {
            *token = TokenId(byte as u32);
        }
        // Ids at and above 256 cannot collide with a byte id, so a merged token is
        // always distinguishable from a literal byte in a failure message.
        let table = RankTable::from_entries(
            "session fixture",
            [
                (PairKey::new(TokenId(b't' as u32), TokenId(b'h' as u32)), TokenId(256), Rank(0)),
                (PairKey::new(TokenId(256), TokenId(b'e' as u32)), TokenId(257), Rank(1)),
                (PairKey::new(TokenId(257), TokenId(b' ' as u32)), TokenId(258), Rank(2)),
                (PairKey::new(TokenId(b'e' as u32), TokenId(b'r' as u32)), TokenId(259), Rank(3)),
                (PairKey::new(TokenId(b'o' as u32), TokenId(b'o' as u32)), TokenId(260), Rank(4)),
            ],
        )
        .expect("the fixture's five rows must build");
        DeviceTokenizer {
            encoding: Encoding::cl100k_base(),
            table,
            byte_token,
            batching: Batching::default(),
            dispatches: AtomicUsize::new(0),
            block_ceilings: RwLock::new(Vec::new()),
            table_bytes: OnceLock::new(),
            plans: RwLock::new(Vec::new()),
            plan_hits: AtomicUsize::new(0),
            plan_misses: AtomicUsize::new(0),
            plan_rebuilds: AtomicU64::new(0),
            output_batch_checks: AtomicU64::new(0),
            output_segment_guards: AtomicU64::new(0),
            host_lookups: AtomicU64::new(0),
            host_merges: AtomicU64::new(0),
            workgroup_override: None,
        }
    }

    /// The interpreter backend, so every test here runs with no device present.
    ///
    /// A session's contract is about OWNERSHIP and BUFFER REUSE, and neither is a
    /// device property: the same `encode_batch_probed` body runs either way and the
    /// ids come from the same IR. Running these on the reference backend puts them
    /// in the default `--lib` gate, where they guard the arenas on every commit
    /// rather than only on a machine with a CUDA card.
    fn cpu() -> vyre_driver_reference::CpuRefBackend {
        vyre_driver_reference::CpuRefBackend
    }

    /// Pretokens of deliberately unequal length, several of which merge.
    ///
    /// In DESCENDING length order, which is what makes it adversarial for the
    /// scatter: [`Batching::ByLength`] sorts longest first, so an input already in
    /// that order leaves the sort a near-identity and any comparison against
    /// [`Batching::InputOrder`] would agree even if indices were being confused
    /// with offsets. The trailing short pretokens break that, so the two modes
    /// really do group differently.
    const SESSION_CORPUS: &[&[u8]] = &[
        b"theresoooo therefore the other",
        b"the there theresoooo",
        b"other",
        b"the",
        b"",
    ];

    /// Ids of `inputs` through the unbound per-call path.
    fn per_call_ids(device: &DeviceTokenizer, inputs: &[&[u8]]) -> Vec<Vec<TokenId>> {
        device
            .encode_batch(&cpu(), inputs)
            .expect("the reference backend must encode the fixture corpus")
            .into_ids()
    }

    /// How many [`Scratch`] sets `session` is holding for its next encode.
    fn pooled(session: &DeviceSession<'_>) -> usize {
        session
            .scratch
            .lock()
            .unwrap_or_else(PoisonError::into_inner)
            .len()
    }

    /// A session's ids are the unbound path's ids.
    ///
    /// The one claim the whole optimization rests on, and it is not implied by the
    /// suites that already pass: every other device test drives
    /// [`DeviceTokenizer::encode_batch`], so a session could return anything at all
    /// and they would stay green. Both paths run the same body, differing only in
    /// [`TableSource`] and in whether the buffers are fresh, so this asserts that
    /// neither difference reaches an id.
    ///
    /// Asserted over the SECOND session encode as well as the first, because the
    /// first runs on empty buffers exactly as an unbound call does. Only the second
    /// runs on buffers a previous encode left dirty, which is where a reuse bug
    /// lives.
    #[test]
    fn a_session_returns_the_unbound_paths_ids() {
        let device = merging_fixture();
        let backend = cpu();
        let expected = per_call_ids(&device, SESSION_CORPUS);
        assert!(
            expected.iter().any(|ids| ids.iter().any(|id| id.0 >= 256)),
            "the fixture must actually merge, or this compares two encoders that \
             both just copy bytes: got {expected:?}"
        );

        let session = device.bind(&backend).expect("binding must succeed");
        for round in 0..3 {
            let ids = session
                .encode_batch(SESSION_CORPUS)
                .expect("a session encode must succeed")
                .into_ids();
            assert_eq!(
                ids, expected,
                "session encode {round} must return the unbound path's ids exactly"
            );
        }
    }

    /// A session's single-input encode is the tokenizer's, id for id.
    ///
    /// The floor and single-input benchmark cells reach for this instead of
    /// `encode_batch(&[input])`, and the substitution they must NOT make is the
    /// reason it is asserted rather than assumed: `encode_batch` flattens pretokens
    /// across input boundaries, so calling it with several inputs is a different
    /// grouping than several `encode` calls. With ONE input the two coincide, and
    /// this pins that coincidence so a later change to either path cannot quietly
    /// break it while every batch test stays green.
    ///
    /// Over each corpus entry separately, including the EMPTY one: an input with no
    /// pretokens must return an empty id vector rather than panicking on a `pop`
    /// from an empty result, which is the one edge the delegation could get wrong.
    #[test]
    fn a_sessions_single_input_encode_matches_the_tokenizers() {
        let device = merging_fixture();
        let backend = cpu();
        let session = device.bind(&backend).expect("binding must succeed");

        for input in SESSION_CORPUS {
            let unbound = device
                .encode(&backend, input)
                .expect("the unbound single-input encode must succeed");
            let bound = session
                .encode(input)
                .expect("the session single-input encode must succeed");
            assert_eq!(
                bound,
                unbound,
                "a session's encode of {} bytes must equal the tokenizer's",
                input.len()
            );
        }
    }

    /// A previous encode's words never reach the next one's answer.
    ///
    /// The hazard the flat arenas introduce: a reused buffer that is truncated
    /// rather than logically emptied lets encode B read bytes encode A wrote,
    /// wherever a length is computed from something other than the run that names
    /// it. Nothing else in the crate can catch it, since a single encode on a fresh
    /// session is exactly the case that cannot leak.
    ///
    /// The first encode is deliberately the LARGER one, so B runs over buffers
    /// holding strictly more stale words than it will write, and past its own runs
    /// there is real data rather than zeros.
    #[test]
    fn an_encode_after_a_larger_one_matches_that_encode_alone() {
        let device = merging_fixture();
        let backend = cpu();
        let second: &[&[u8]] = &[b"the other", b"theresoooo"];
        let alone = per_call_ids(&device, second);

        let session = device.bind(&backend).expect("binding must succeed");
        session
            .encode_batch(SESSION_CORPUS)
            .expect("the priming encode must succeed");
        let after = session
            .encode_batch(second)
            .expect("the second encode must succeed")
            .into_ids();

        assert_eq!(
            after, alone,
            "an encode on used buffers must equal the same encode on fresh ones, \
             or a stale word from the previous encode is reaching an id"
        );
    }

    /// A scratch reused by a DIFFERENT thread than last used it still answers
    /// exactly.
    ///
    /// Specific to the pool, and unreachable by a design that kept one scratch per
    /// session: the buffers cross a thread boundary between the encode that dirtied
    /// them and the encode that reuses them. That is the case where a missing reset
    /// and a data race look identical from the outside, so it gets its own test
    /// rather than being assumed to follow from the single-threaded one.
    #[test]
    fn a_scratch_dirtied_on_one_thread_answers_exactly_on_another() {
        let device = merging_fixture();
        let backend = cpu();
        let second: &[&[u8]] = &[b"the other", b"theresoooo"];
        let alone = per_call_ids(&device, second);

        let session = device.bind(&backend).expect("binding must succeed");
        session
            .encode_batch(SESSION_CORPUS)
            .expect("the priming encode must succeed");
        assert_eq!(
            pooled(&session),
            1,
            "the primed scratch must be back in the pool, or the next encode \
             cannot be the one that reuses it"
        );

        let after = std::thread::scope(|scope| {
            scope
                .spawn(|| {
                    session
                        .encode_batch(second)
                        .expect("the borrowed-thread encode must succeed")
                        .into_ids()
                })
                .join()
                .expect("the encoding thread must not panic")
        });

        assert_eq!(
            after, alone,
            "a scratch dirtied on another thread must answer exactly, or the \
             reset is thread-local in a way the pool does not honour"
        );
    }

    /// Overlapping encodes each get their OWN buffers.
    ///
    /// The regression this exists for is invisible to every other test in the
    /// crate: one [`Scratch`] behind a mutex held across the encode returns
    /// perfectly correct ids, so no correctness suite can distinguish it, and it
    /// does not change an allocation count or a single-threaded profile either. It
    /// would show up only as multi-threaded throughput collapsing to one core.
    /// [`DeviceTokenizer::encode_batch`] takes `&self` precisely so a tokenizer can
    /// be shared, so serializing a session's encodes would take that property away
    /// silently.
    ///
    /// Structural rather than timed: it compares a COUNT and never a duration, so
    /// there is no threshold to tune and contention cannot fail it. Contention in
    /// fact makes it stronger, since overlap becomes more likely rather than less.
    /// The pool ends up holding one set per concurrent encode that ever ran, so
    /// more than one set in the pool IS the observation that two encodes held two
    /// scratches at the same moment. A design that held the lock across the encode
    /// could never put a second set in the pool, whatever the scheduling.
    #[test]
    fn overlapping_encodes_hold_distinct_scratches() {
        const THREADS: usize = 4;
        const ROUNDS: usize = 8;

        let device = merging_fixture();
        let backend = cpu();
        let expected = per_call_ids(&device, SESSION_CORPUS);
        let session = device.bind(&backend).expect("binding must succeed");
        // Released together, so the encodes really are concurrent rather than a
        // staggered sequence that happens to use several threads.
        let start = std::sync::Barrier::new(THREADS);

        std::thread::scope(|scope| {
            for _ in 0..THREADS {
                scope.spawn(|| {
                    start.wait();
                    for _ in 0..ROUNDS {
                        let ids = session
                            .encode_batch(SESSION_CORPUS)
                            .expect("a concurrent session encode must succeed")
                            .into_ids();
                        assert_eq!(
                            ids, expected,
                            "a concurrent encode must return the same ids as a \
                             lone one"
                        );
                    }
                });
            }
        });

        assert!(
            pooled(&session) >= 2,
            "{THREADS} threads running {ROUNDS} encodes each past a barrier must \
             have held at least two scratches at once, so the pool must retain at \
             least two; it holds {}, which is what a single scratch guarded across \
             the whole encode would leave",
            pooled(&session)
        );
        assert!(
            pooled(&session) <= SCRATCH_POOL_LIMIT,
            "the pool must stay inside its own bound: {} sets retained past a \
             limit of {SCRATCH_POOL_LIMIT}",
            pooled(&session)
        );
    }

    /// A session's buffers survive its encodes instead of being rebuilt.
    ///
    /// The reuse is the entire point, and it is not observable from ids: a session
    /// that dropped its buffers every time would still answer exactly, and would
    /// still pass every test above. Capacity is what separates the two, and it is
    /// an exact structural figure rather than a timing, so it holds on a contended
    /// box.
    ///
    /// Asserted as "at least the words the encode wrote" rather than as an exact
    /// number, because the growth policy is the allocator's business; what must be
    /// true is that the second encode finds room already there.
    #[test]
    fn a_session_keeps_the_capacity_its_encodes_grew() {
        let device = merging_fixture();
        let backend = cpu();
        let session = device.bind(&backend).expect("binding must succeed");

        session
            .encode_batch(SESSION_CORPUS)
            .expect("the first encode must succeed");
        let device_bytes: usize = SESSION_CORPUS
            .iter()
            .flat_map(|input| spans(device.encoding.pattern(), input))
            .map(|span| span.len())
            .filter(|len| *len <= MAX_PRETOKEN_TOKENS)
            .sum();
        let grown = {
            let pool = session.scratch.lock().unwrap_or_else(PoisonError::into_inner);
            let scratch = pool.first().expect("the encode must return its scratch");
            // Still holding the last encode's words, and that is the design rather
            // than an oversight. The reset is at the START of an encode, because
            // that is the only point EVERY path reaches: an encode that returns an
            // error leaves its runs behind, and clearing on the way out would skip
            // exactly that case. So a pooled scratch is dirty by construction and
            // the next encode empties it before reading a word of it, which is what
            // `an_encode_after_a_larger_one_matches_that_encode_alone` and
            // `a_scratch_dirtied_on_one_thread_answers_exactly_on_another` prove
            // from the outside. Asserted rather than merely described, so a later
            // move of the reset to the end of the encode has to come here and
            // confront the error path.
            assert!(
                !scratch.state.is_empty() && !scratch.ids.is_empty(),
                "a pooled scratch holds the previous encode's words: the reset is \
                 on entry, so that the error paths are covered by it too"
            );
            (scratch.state.capacity(), scratch.ids.capacity())
        };
        assert!(
            grown.0 >= device_bytes,
            "the state buffer must retain room for the {device_bytes} start-state \
             words the encode wrote, not {} ",
            grown.0
        );

        session
            .encode_batch(SESSION_CORPUS)
            .expect("the second encode must succeed");
        let pool = session.scratch.lock().unwrap_or_else(PoisonError::into_inner);
        let scratch = pool.first().expect("the encode must return its scratch");
        assert_eq!(
            (scratch.state.capacity(), scratch.ids.capacity()),
            grown,
            "an identical second encode must reuse the capacity the first grew \
             rather than allocating again"
        );
    }

    /// Grouping never changes an id, over the arena's own indexing.
    ///
    /// [`batches`] returns ORIGINAL indices so a reordering mode cannot permute the
    /// output, and the arena change moves where each pretoken's words LIVE while
    /// leaving those indices in place. That is exactly the change that could start
    /// using an offset where an index was meant: every length-based assertion in
    /// this module would still pass, every batch would still be well formed, and
    /// the ids would be attributed to the wrong pretokens.
    ///
    /// [`SESSION_CORPUS`] is in descending length order for this test's benefit;
    /// see its own note.
    #[test]
    fn batching_mode_does_not_change_a_sessions_ids() {
        let backend = cpu();
        let mut expected = None;
        for mode in [Batching::InputOrder, Batching::ByLength] {
            let mut device = merging_fixture();
            device.batching = mode;
            let session = device.bind(&backend).expect("binding must succeed");
            let ids = session
                .encode_batch(SESSION_CORPUS)
                .expect("a session encode must succeed")
                .into_ids();
            match &expected {
                None => expected = Some(ids),
                Some(first) => assert_eq!(
                    &ids, first,
                    "{mode:?} must return the same ids as the first mode: a \
                     grouping change may reorder DISPATCHES and may never reorder \
                     ids"
                ),
            }
        }
    }

    /// Closing a session twice is impossible, and dropping one is enough.
    ///
    /// [`DeviceSession::close`] consumes the session and takes the handle out
    /// before returning, so the [`Drop`] that immediately follows finds `None`. A
    /// double free of a resident buffer is a backend-level error rather than a
    /// wrong id, which is why it gets a structural check here instead of being left
    /// to a parity suite that could never see it.
    ///
    /// The reference backend has no resident dispatch, so the handle is `None` from
    /// the start and `close` reports success over nothing. That is the interesting
    /// half on this backend: it pins that a session on a device without resident
    /// dispatch is a working session and not an error, which is what lets these
    /// tests run in the default gate at all.
    #[test]
    fn a_session_on_a_backend_without_resident_dispatch_still_encodes() {
        let device = merging_fixture();
        let backend = cpu();
        assert!(
            !backend.supports_resident_dispatch(),
            "this test is about the no-resident-dispatch path; the reference \
             backend having gained one makes it vacuous"
        );
        let expected = per_call_ids(&device, SESSION_CORPUS);

        let session = device.bind(&backend).expect("binding must succeed");
        assert!(
            session.table.is_none(),
            "a backend with no resident dispatch must hold no resident table"
        );
        let ids = session
            .encode_batch(SESSION_CORPUS)
            .expect("the encode must succeed with a host-input table")
            .into_ids();
        assert_eq!(ids, expected, "the ids must not depend on where the table sat");
        session
            .close()
            .expect("closing a session that holds no buffer must succeed");
    }

    /// A session pays for the merge table once, not once per encode.
    ///
    /// The measured reason sessions exist: [`EncodePhase::TableUpload`] and
    /// [`EncodePhase::TableFree`] were 2.816 ms and 0.140 ms of a 19.656 ms prose
    /// encode, and [`EncodePhase::TablePack`] is a 16 MiB serialization. All three
    /// must read exactly ZERO on a session encode, and the unbound path must still
    /// show the upload, or the two rows have stopped distinguishing the paths.
    ///
    /// Exact zeros rather than a ratio, which is why this is not a timing test and
    /// cannot be flaky under load: a phase the encode never enters is charged
    /// nothing at all.
    ///
    /// Requires a real device, because a resident table needs a backend with
    /// resident dispatch and the whole claim is about that buffer.
    #[cfg(feature = "cuda")]
    #[test]
    fn a_session_charges_nothing_for_the_merge_table() {
        // Through the factory, exactly as `tests/device_determinism.rs` does:
        // `CudaBackend` itself does not implement [`VyreBackend`], the registration
        // wrapper does, and the factory is the only public way to reach one.
        let backend = vyre_driver_cuda::cuda_factory()
            .expect("a CUDA device is required by this test and must not be skipped past");
        assert!(
            backend.supports_resident_dispatch(),
            "the CUDA backend must offer resident dispatch, or this asserts nothing"
        );
        let device = merging_fixture();

        let (_, unbound) = device
            .encode_batch_profiled(backend.as_ref(), SESSION_CORPUS)
            .expect("the unbound encode must succeed");
        assert!(
            unbound.phase(EncodePhase::TableUpload) > Duration::ZERO,
            "the unbound path must still upload the table, or this test would \
             pass on a path that stopped dispatching at all"
        );

        let session = device.bind(backend.as_ref()).expect("binding must succeed");
        assert!(
            session.table.is_some(),
            "a resident-dispatch backend must leave the session holding the table"
        );
        for round in 0..2 {
            let (_, profile) = session
                .encode_batch_profiled(SESSION_CORPUS)
                .expect("a session encode must succeed");
            for phase in [
                EncodePhase::TablePack,
                EncodePhase::TableUpload,
                EncodePhase::TableFree,
            ] {
                assert_eq!(
                    profile.phase(phase),
                    Duration::ZERO,
                    "session encode {round} must not enter {}, which the bind \
                     already paid for",
                    phase.label()
                );
            }
        }
        session
            .close()
            .expect("the backend must accept its own resident buffer back");
    }
}