Nghiên cứu về Cấu trúc Dữ liệu trong Hệ thống AI Tối ưu


Trong kỹ thuật hệ thống AI hiện đại, cấu trúc dữ liệu tối ưu là thành phần quyết định trực tiếp đến thông lượng và giới hạn bộ nhớ thông qua cơ chế đồng thiết kế với phần cứng, nhằm giảm thiểu chi phí di chuyển dữ liệu xuyên qua phân cấp lưu trữ—từ thanh ghi, bộ nhớ trên chip (SRAM/L1), bộ nhớ băng thông cao (HBM), RAM máy chủ, ổ cứng NVMe cho tới liên kết mạng đa nút1. Nghiên cứu này phân tích có hệ thống bảy lớp cấu trúc dữ liệu cốt lõi kiến tạo nên hiệu năng của hạ tầng AI tối ưu: bố cục tensor và khối chia nhận thức I/O kèm hoán vị XOR (swizzling) trên SRAM; cấu trúc ma trận thưa và bố cục đóng gói bit lượng tử hóa; bảng phân trang, cây tiền tố nén và bộ đệm vòng quản lý KV Cache; cây suy đoán động và automata cho giải mã có ràng buộc; chỉ mục đồ thị gần đúng và lượng tử hóa xoay ngẫu nhiên trong tìm kiếm vector; đồ thị trung gian (IR) trình biên dịch, cây khoảng thời gian bộ nhớ, thuật toán cắt cực tiểu và tensor phân tán; cùng các cấu trúc cây tổng, hàng đợi ưu tiên và bảng băm chuyển vị trong học tăng cường và tìm kiếm heuristic.

Một quy luật thực nghiệm xuyên suốt các bằng chứng giai đoạn 2023–2026 là sự đảo nghịch thường xuyên giữa độ phức tạp tiệm cận trên giấy và tốc độ thực thi trên phần cứng thực tế. Nhiều cấu trúc dữ liệu tối ưu về mặt lý thuyết—như đống Fibonacci với thao tác khấu hao O(1), tỉa thưa 2:4 hứa hẹn nhân đôi thông lượng toán học, hay cây tiền tố nén tối ưu tái sử dụng bộ nhớ đệm—có thể chạy chậm hơn đáng kể so với mảng liên tục, phép nhân ma trận dày đặc (dense GEMM) hoặc trình lập lịch C++ đơn giản khi gặp phải truy cập con trỏ rời rạc gây trượt bộ đệm L1/L2, phân kỳ luồng trong một warp (warp divergence), thiếu hợp nhất nhân (kernel fusion), hoặc nghẽn khóa GIL trong Python5. Do đó, việc lựa chọn cấu trúc dữ liệu trong AI đòi hỏi đánh giá đồng thời mô hình truy cập bộ nhớ, tỷ lệ trúng bộ đệm và ngưỡng hòa vốn thực nghiệm trên từng kiến trúc phần cứng cụ thể.

1. Bố cục Tensor, Phân cấp Bộ nhớ GPU và Kỹ thuật Tiling Tối ưu I/O

Cách bố trí các chiều của tensor đa chiều trong bộ nhớ tuyến tính quyết định trực tiếp khả năng GPU gộp yêu cầu đọc của một warp (32 luồng) thành ít giao dịch bộ nhớ 32 byte hoặc 128 byte nhất10. Trong mạng nơ-ron tích chập (CNN), hai bố cục phổ biến là NCHW (Channels-First, chiều rộng W biến thiên liên tiếp trong bộ nhớ) và NHWC (Channels-Last, chiều kênh C biến thiên liên tiếp tại mỗi tọa độ không gian)10. Theo giải thích kỹ thuật từ diễn đàn nhà phát triển NVIDIA và cộng đồng, trên các GPU thế hệ cũ không trang bị Tensor Core, NCHW từng được ưu tiên hơn để tránh chi phí cộng gộp liên luồng (một bình luận trên StackOverflow năm 2020 dẫn lại kết quả thử nghiệm cho thấy NCHW nhanh hơn gần 2,5 lần ở cấu hình thời kỳ đó)14. Ngược lại, từ kiến trúc NVIDIA Volta và Turing trở đi, nhân Tensor Core nạp dữ liệu theo từng khối dọc theo chiều kênh, khiến NHWC (cùng các biến thể lai như NC/xHWx) trở thành định dạng tối ưu cho truy cập bộ nhớ hợp nhất và tận dụng bộ đệm10.

Việc chọn sai bố cục tensor phát sinh phụ phí lớn về bộ nhớ tạm và độ trễ chuyển đổi ngầm. Một bài blog kỹ thuật dẫn lại tài liệu PyTorch ghi nhận việc chuyển sang NHWC kết hợp Tự động Hỗn hợp Độ chính xác (AMP) giúp tăng tốc 22% trên GPU NVIDIA13. Trong một đề xuất tối ưu hóa Tensor Core trên diễn đàn Apache TVM (năm 2020), việc chuyển bố cục sang NHWC trên ResNet50 đạt mức tăng tốc tới 3,43 lần so với TVM FP16 thông thường và 1,28 lần so với TensorFlow XLA16. Trên thực tế triển khai cuDNN và TensorRT, một báo cáo của lập trình viên trên diễn đàn NVIDIA (năm 2020) cho thấy cùng một lớp tích chập kích thước lớn (1000 x 256 x 7 x 7), NHWC chỉ yêu cầu 12 byte bộ nhớ tạm (workspace) trong khi NCHW bị thư viện yêu cầu tới 19 GB (hoặc 2 GB tùy cấu hình giới hạn bộ nhớ tạm)14. Tương tự, nếu mô hình ONNX đầu vào giữ nguyên định dạng NCHW, TensorRT dù tự động thử nghiệm các bố cục vẫn có thể phải chèn các nhân chuyển đổi (Reformat) lặp đi lặp lại trong đồ thị thực thi12.

Ở tầng thuật toán chú ý (Attention), cấu trúc dữ liệu chia khối (tiling) kết hợp thống kê trực tuyến của FlashAttention giải quyết triệt để nút thắt băng thông HBM. Theo phân tích độ phức tạp I/O trong bài báo gốc FlashAttention (Dao et al., 2022), cách tính chú ý chuẩn phải hiện thực hóa các ma trận trung gian và kích thước N x N trên HBM với tổng lượng truy cập Θ(Nd + N²)3; theo tính toán của một bài blog kỹ thuật, với chuỗi dài 128.000 token và số chiều đầu chú ý d = 128 ở định dạng FP16, riêng ma trận S đã tiêu tốn 32 GB VRAM và phải đọc ghi nhiều lần18. FlashAttention chia Q, K, V thành các khối vừa khít bộ nhớ SRAM trên chip (trên A100 là 192 KB/SM dùng chung cho L1 và Shared Memory, cấu hình tối đa 164 KB Shared Memory2), đồng thời duy trì mảng thống kê chạy gồm giá trị cực đại cục bộ m và tổng lũy thừa l kèm hệ số hiệu chỉnh trực tuyến khi quét qua từng khối K2. Nhờ không bao giờ ghi S và P ra HBM, thuật toán hạ độ phức tạp I/O xuống Θ(N²d² / M) (với M là dung lượng SRAM), giảm 4–16 lần lưu lượng bộ nhớ theo ước tính từ bài phân tích trên Hugging Face, đưa bộ nhớ tiêu thụ về tuyến tính O(N), và đạt tốc độ nhanh hơn tới 3 lần so với cài đặt chuẩn trên chuỗi dài tới 2K2.

Trên kiến trúc NVIDIA Hopper (H100/SM90+), FlashAttention-3 (công bố năm 2024) nâng cấp cấu trúc lưu trữ trung gian thành bộ đệm vòng đa tầng trên bộ nhớ dùng chung (s-stage circular SMEM buffer) kết hợp chuyên biệt hóa warp (warp specialization): tách các warpgroup thành nhóm sản xuất (producer) chuyên gọi đơn vị phần cứng TMA (Tensor Memory Accelerator—tự động tính chỉ số và kiểm tra biên nhằm giải phóng thanh ghi) để tải bất đồng bộ từ HBM vào SMEM, và nhóm tiêu thụ (consumer) chuyên chạy lệnh nhân ma trận WGMMA gối đầu với phép softmax2. Nhờ che giấu độ trễ bộ nhớ và lượng tử hóa theo khối (block quantization) kèm xử lý khử tương quan cho FP8, thử nghiệm trên H100 trong bài báo gốc ghi nhận FlashAttention-3 đạt tới 740 TFLOPS với FP16 (75% công suất lý thuyết, nhanh hơn 1,5–2,0 lần ở lượt xuôi và 1,5–1,75 lần ở lượt ngược so với FlashAttention-2) và tiệm cận 1,2 PFLOPS với FP8 cùng sai số số học thấp hơn 2,6 lần so với FP8 cơ sở19.

Để tốc độ của SRAM không bị triệt tiêu bên trong khối xử lý, dữ liệu chia khối phải giải quyết bài toán xung đột băng tần (shared memory bank conflicts). Bộ nhớ dùng chung trên GPU NVIDIA hiện đại gồm 32 bank độc lập, mỗi bank rộng 32 bit (4 byte), ánh xạ từ địa chỉ byte theo công thức (offset >> 2) & 0x1F23. Nếu n luồng trong cùng một warp truy cập n địa chỉ khác nhau rơi vào cùng một bank—chẳng hạn khi đọc theo cột của mảng 2D có bước nhảy là bội số của 32 từ—phần cứng buộc phải tuần tự hóa thành n sóng truy cập (wavefronts), làm sụt giảm băng thông hiệu dụng đúng n lần và chậm tới 32 lần trong trường hợp xấu nhất23.

Thay vì chèn đệm làm lãng phí dung lượng SMEM quý giá, các nhân tối ưu như CUTLASS/CuTe áp dụng phép hoán vị địa chỉ XOR (XOR Swizzling), biến đổi ánh xạ arr[row][col] thành arr[row][row XOR col] để mọi phần tử trên cùng cột logic phân bổ đều sang các bank vật lý khác nhau25. Thư viện CuTe mô hình hóa tổng quát qua khuôn mẫu Swizzle<BBits, MBase, SShift>, trong đó MBase giữ nguyên các bit thấp nhằm bảo toàn tính liên tục cho lệnh nạp vector 128-bit, còn BBits và SShift xác định mặt nạ bit vùng cao dịch phải rồi thực hiện phép XOR offset ^ shiftr(offset & yyy_msk, msk_sft)27. Một thử nghiệm tối ưu nhân FlashAttention trên blog kỹ thuật lubits.ch ghi nhận việc loại bỏ xung đột bank 8 chiều bằng XOR swizzling đã giảm 8 lần số wavefront cần thiết, hạ mức tiêu thụ băng thông SMEM do truyền thừa từ 93,64% xuống còn 23,48%, đồng thời nhân đôi hiệu năng tính toán từ 33,28 lên 66,12 TFLOPS25. Khi triển khai thực tế, mọi thao tác đọc và ghi SMEM đều phải áp dụng cùng một hàm swizzle để tránh sai lệch dữ liệu25; ngoài ra, theo thảo luận kỹ thuật của cộng đồng lập trình viên trên StackOverflow và diễn đàn NVIDIA, các lệnh nạp vector hóa rộng (như 16 byte) vẫn có thể phát sinh xung đột bên trong từng pha phục vụ gồm một nhóm làn con, và khi phân tích bằng Nsight Compute cần theo dõi chỉ số L1 Wavefronts Shared Excessive để tách riêng xung đột SMEM thực sự khỏi nhiễu từ truy cập L128.

2. Cấu trúc Dữ liệu Thưa và Đóng gói Bit Lượng tử hóa

Việc sử dụng cấu trúc dữ liệu nén thưa hoặc đóng gói bit thấp chỉ mang lại tốc độ thực tế khi lợi ích tiết kiệm băng thông vượt qua chi phí giải mã chỉ số và không phá vỡ mô hình thực thi đồng bộ SIMT.

Biểu diễn Thưa Phi cấu trúc và Bài toán Đồ thị

Các định dạng thưa kinh điển như CSR (Compressed Sparse Row) và COO (Coordinate) lưu giá trị khác 0 kèm mảng chỉ số hàng và cột30. Tuy nhiên, nhân SpMM của cuSPARSE trên CSR thường chậm hơn rất nhiều so với nhân dày đặc cuBLAS GEMM ở độ thưa trung bình32. Một phép đo của nhà phát triển trên GPU Titan Black (CUDA 6.5) được chia sẻ trên StackOverflow cho thấy với ma trận thưa 50% (192x2400 nhân 2400x256), cusparseScsrmm tốn 1,4 ms trong khi cublasSgemm chỉ mất 0,21 ms (chậm hơn gần 7 lần)32. Nguyên nhân là cuBLAS khai thác tối đa nạp trước (prefetching), truy cập hợp nhất và bộ nhớ dùng chung để tiệm cận trên 95% năng lực đỉnh, còn cấu trúc CSR ép GPU phải đọc gián tiếp (pointer-chasing), ngăn cản vector hóa và phát sinh phân nhánh điều kiện32. Vì vậy, ngưỡng hòa vốn để cuSPARSE vượt cuBLAS thường đòi hỏi độ thưa từ 99% trở lên (tối đa 1% phần tử khác 0, hoặc dưới 10 phần tử mỗi hàng trên ma trận cỡ lớn), và ngay cả định dạng cải tiến GCOOSpDM cũng chỉ kéo ngưỡng hòa vốn xuống 98%32.

Trong mạng nơ-ron đồ thị (GNN), phân phối bậc đỉnh lệch (scale-free) càng làm trầm trọng thêm mất cân bằng tải giữa các warp và hiện tượng phân kỳ warp khi một số hàng quá dài trong khi phần lớn hàng rất ngắn31. Nghiên cứu SMaT (2024) giải quyết bài toán SpMM bằng cách ánh xạ khối thưa trực tiếp lên Tensor Core (đồng thời công bố mô hình hiệu năng SpMV trên định dạng khối BCSR), hạ ngưỡng hòa vốn xuống ≥78% trên ma trận dải nhân tạo và ≥96% trong đánh giá tổng quát so với cuBLAS, đạt tốc độ trung bình nhân nhanh hơn cuSPARSE 16,32 lần (tối đa 125,48 lần) trên 9 ma trận thử nghiệm37. Đối với đồ thị lớn có chỉ số đỉnh cập nhật phân tán gây tỷ lệ trượt bộ đệm L1/L2 cao, các thuật toán sắp xếp lại đỉnh như Reverse Cuthill–McKee (RCM) hoặc hoán vị cửa sổ (trong phương pháp BVSS năm 2026) gom nhóm các nút lân cận về gần nhau trên địa chỉ bộ nhớ để tăng tỷ lệ trúng L1/L236; kết hợp với cơ chế lập lịch warp nhận thức phân kỳ (DAWS)38 hoặc mô hình Warp-Consolidation (gộp mỗi khối CTA chỉ gồm một warp duy nhất để thay thế đồng bộ khối tốn kém bằng trao đổi trực tiếp qua thanh ghi nội bộ)39.

Thưa Bán cấu trúc 2:4 và Khoảng cách giữa Lý thuyết với Suy luận LLM

Từ kiến trúc Ampere (A100), NVIDIA tích hợp phần cứng Sparse Tensor Core cho mẫu thưa bán cấu trúc 2:4: trong mỗi nhóm 4 trọng số liên tiếp theo chiều rút gọn K, có tối đa 2 giá trị khác 05. Cấu trúc lưu trữ của cuSPARSELt và CUTLASS nén mảng giá trị xuống còn một nửa kèm siêu dữ liệu vị trí kích thước vài bit cho mỗi nhóm 4 phần tử5. Về mặt toán học, A100 Sparse Tensor Core đạt 624 TFLOPS (gấp đôi mức 312 TFLOPS dày đặc)2; benchmark công bố bởi NVIDIA trên cuSPARSELt đạt mức tăng tốc 1,3x–1,6x trên các lớp BERT-Large (batch 128, độ dài 128)43, và nghiên cứu SlideSparse (2026) đo được nhân 2:4 bản địa trên A100 đạt 2,03x–2,08x so với cuBLASLt ở kích thước ma trận lớn42.

Tuy vậy, khi đưa vào suy luận LLM thực tế, mức tăng tốc 2x thường không đạt được do ba rào cản cấu trúc. Rào cản thứ nhất là chế độ nghẽn băng thông khi kích thước lô M nhỏ (pha giải mã từng token): theo thực nghiệm trên B200 (năm 2026), khi M nhỏ, chi phí giải nén chỉ số khiến GEMM thưa 2:4 không nhanh hơn—thậm chí chậm hơn—GEMM dày đặc, và chỉ tiệm cận ngưỡng 2x khi M đủ lớn41. Minh chứng điển hình là một báo cáo sự cố trên kho mã nguồn NVIDIA Model-Optimizer (năm 2026) khi triển khai Qwen3-4B chuẩn 2:4 trên TensorRT-LLM (mức đồng thời tới 128): thông lượng và độ trễ gần như giữ nguyên (~485 tok/s, độ trễ liên token ~33,8 ms, mức tăng tốc ~0%) trong khi kích thước engine tăng từ ~8,9 GB lên ~12 GB do chứa siêu dữ liệu, một phần vì cờ --gemm_plugin auto vẫn định tuyến qua cuBLASLt dày đặc thay vì nhân thưa9.

Rào cản thứ hai là thiếu hợp nhất nhân khi kết hợp thưa và lượng tử hóa. Theo một thử nghiệm minh họa trong ghi chú bài giảng cộng đồng CUDA MODE, so với mức cơ sở BF16 (1600 ms), chạy riêng thưa 2:4 hoặc riêng lượng tử đều rút xuống 1400 ms, nhưng ghép cả hai mà không hợp nhất lại chậm đi thành 1420 ms; chỉ khi bật hợp nhất một phần bằng alpha-vector của cuSPARSELt thời gian mới giảm còn 1278 ms, và để hợp nhất hoàn toàn cả phép chuyển vị lẫn giải lượng tử phải tự phát triển nhân trên CUTLASS5.

Rào cản thứ ba là sự sụp đổ độ chính xác của mẫu 50% thưa cứng nhắc trên các mô hình suy luận nhạy cảm. Nghiên cứu SlideSparse (2026) ghi nhận trên Qwen3-1.7B, độ chính xác trung bình rơi từ 54,0% xuống 15,3% ở chế độ 2:4 (và giảm 14,9–16,5 điểm trên Qwen2.5-7B/14B), trong khi mẫu nhẹ hơn là 6:8 (bỏ 25% trọng số) giữ được 51,6% trên Qwen3-1.7B và chỉ lệch 0,4–1,8 điểm trên Qwen2.542. Để tận dụng phần cứng 2:4 cho mẫu 6:8, SlideSparse dùng cấu trúc Phân rã Cửa sổ Trượt (Sliding Window Decomposition) biến đổi mẫu (2N-2):2N thành các cửa sổ 2:4 chồng lấp với hệ số phình γ = (2N-2)/N (bằng 1,5 cho 6:8), đạt đúng mức tăng tốc lý thuyết N/(N-1) = 1,33x trên Qwen2.5-7B ở tác vụ giới hạn tính toán42.

Bố cục Đóng gói Bit Lượng tử hóa

 

Định dạng / Kiến trúc

Cấu trúc dữ liệu & Bố cục bộ nhớ

Chi phí siêu dữ liệu (Scale)

Cơ chế giải nén & Phần cứng

Hiệu năng thực tế & Giới hạn

QLoRA NF4 + Double Quant

16 mức phân vị tối ưu cho phân phối chuẩn; đóng gói 4-bit chỉ phục vụ lưu trữ45.

Scale 32-bit nén về 8-bit kèm meta-scale 32-bit dùng chung, hạ phụ phí từ 0,5 xuống 0,127 bit/tham số47.

Giải lượng tử lên BF16/FP16 trước khi tính; kết hợp Paged Optimizers45.

Cho phép tinh chỉnh mô hình 65B trên một GPU 48 GB45; tốn chi phí giải nén động nếu không có nhân hợp nhất.

Marlin (INT4 x FP16)

Trọng số INT4 hoán vị ngoại tuyến theo mẫu xen kẽ 75316420, thẳng hàng nạp 128-bit vào thanh ghi49.

Scale theo cột hoặc theo nhóm (thường G = 128) đồng bộ qua SMEM49.

Dùng duy nhất 1 lệnh LOP3 trong thanh ghi để chuyển INT4 sang FP16 cho mma.sync49.

Kho mã nguồn báo cáo tăng tốc tới 3,87x (paper ~3x) ở batch 16–32 trên Ampere/Ada50; thiếu đường tối ưu riêng cho Hopper/Blackwell53.

OCP MXFP4 (Blackwell / MI355)

Khối 32 phần tử micro-float 4-bit (E2M1) dùng chung 1 hệ số mũ 8-bit (E8M0)55.

8 bit chia cho 32 phần tử, dung lượng hiệu dụng đúng 4,25 bit/trọng số55.

Phần cứng bản địa trên Blackwell (SM100/SM120) và AMD MI355 giải mã trong ống lệnh56.

Gấp đôi thông lượng FP8 trên Blackwell58; một số biến thể mới như SM121 vẫn đang cần vá phần mềm chuyển E2M1 trong vLLM/CUTLASS59.

3. Cấu trúc Dữ liệu Quản lý KV Cache trong Suy luận LLM

Trong pha giải mã tự hồi quy, bộ nhớ đệm Key-Value (KV Cache) phình lớn nhanh chóng theo độ dài chuỗi—chẳng hạn với LLaMA-2 13B, mỗi token chiếm khoảng 800 KB KV cache, tức chuỗi 2048 token tiêu tốn khoảng 1,6 GB60. Các hệ thống phục vụ tiền nhiệm cấp phát vùng nhớ liên tục theo độ dài tối đa của từng yêu cầu, gây lãng phí 60%–80% VRAM (theo đo đạc của nhóm nghiên cứu vLLM công bố tại SOSP 2023) do ba nguyên nhân: phân mảnh nội bộ (dành sẵn cho độ dài tối đa nhưng câu trả lời thực tế ngắn hơn), vùng dự trữ chưa dùng ở hiện tại, và phân mảnh ngoại bộ (khoảng trống rời rạc giữa các yêu cầu có độ dài khác nhau không thể tái sử dụng)60.

Lấy cảm hứng từ phân trang bộ nhớ ảo của hệ điều hành, PagedAttention (vLLM) tách rời chuỗi token logic khỏi cách lưu trữ vật lý trên HBM60. Toàn bộ vùng nhớ KV được chia thành các khối vật lý kích thước cố định (thường 16 token mỗi khối cho một head; với kích thước head 128, một khối lưu 2048 phần tử), còn mỗi yêu cầu giữ một Bảng khối (Block Table) ánh xạ khối logic sang các khối vật lý nằm rải rác60. Thiết kế này loại bỏ phân mảnh ngoại bộ và giới hạn phân mảnh nội bộ chỉ còn tối đa ở khối cuối cùng, hạ tỷ lệ lãng phí bộ nhớ xuống dưới 4%, đồng thời cho phép chia sẻ khối vật lý theo cơ chế Copy-on-Write (CoW) trong tìm kiếm chùm hoặc lấy mẫu song song60. Nhân CUDA đọc phân tán theo bảng khối theo từng gói 16 byte giúp vLLM đạt thông lượng cao hơn 2–4 lần so với các hệ thống cơ sở được đánh giá năm 2023 (tài liệu vLLM lưu ý con số này gắn với bối cảnh bài báo năm 2023 chứ không phải bảo chứng cố định)62.

Một hiểu lầm thường gặp là đặt RadixAttention (của SGLang) đối lập với PagedAttention. Tài liệu kiến trúc của cả hai hệ thống làm rõ rằng hai cấu trúc này giải quyết hai tầng khác nhau: phân trang giải quyết bài toán cấp phát bên trong một yêu cầu để chống phân mảnh, còn cây cơ số giải quyết bài toán lưu giữ và tái sử dụng bộ nhớ đệm xuyên suốt nhiều yêu cầu67. RadixAttention tổ chức các khối KV đã tính thành một Cây tiền tố nén (Radix Tree / Compressed Trie) với mỗi cạnh là một chuỗi token độ dài biến thiên, cho phép nhiều tác tử AI hoặc nhánh suy luận chia sẻ cùng nút gốc (lời nhắc hệ thống, định nghĩa công cụ) và rẽ nhánh mà không nhân bản bộ nhớ68. Khi cạn VRAM, SGLang áp dụng chính sách loại bỏ nhận thức cây (Tree-Aware LRU Eviction): giải phóng các nút lá cũ nhất trước tiên nhằm giữ các nút gốc được tham chiếu nhiều nằm cố định trong VRAM68.

Các kết quả đo đạc giai đoạn 2024–2026 chỉ ra ranh giới vận hành rõ ràng giữa hai cấu trúc. Khi các yêu cầu là chuỗi độc nhất (không trùng tiền tố), thử nghiệm độc lập năm 2026 trên H100 giữa vLLM v0.18.0 và SGLang v0.5.9 (do hãng đám mây Spheron thực hiện) cho thấy thông lượng tương đương nhau trong biên độ nhiễu 2%–5% (~1.850 so với ~1.920 tok/s ở mức đồng thời 50)71. Ngược lại, khi tỷ lệ trùng lặp tiền tố vượt 60% (dưới 40% lợi thế không đáng kể), cấu trúc cây radix tạo khác biệt lớn: trong bài kiểm thử tác tử 16 luồng trên blog kỹ thuật praveentechworld (so sánh các phiên bản cũ hơn là vLLM 0.6.3 với APC và SGLang 0.3.5), RadixAttention nâng tỷ lệ trúng bộ nhớ đệm từ 84,2% lên 96,8%, giảm độ trễ token đầu tiên (TTFT) lượt 2 xuống 2,7 lần (từ 184 ms còn 68 ms, trong đó bước khớp nhánh trên cây radix chỉ mất 0,2 ms) và tăng thông lượng duy trì thêm 39,8%68; trong bài đo năm 2026 trên H100 (80% trùng lặp tiền tố 512 token, đồng thời 50), SGLang vẫn giảm 37% TTFT ở p50 và 41% ở p9571. Tuy nhiên, cấu trúc cây phức tạp đòi hỏi đồng bộ hóa khéo léo ở tầng điều phối: một báo cáo benchmark trên kho mã nguồn vLLM (Issue #37730) ở mức đồng thời 150 luồng ghi nhận bộ định tuyến Python của SGLang bị kẹt bởi Python GIL (chỉ sử dụng 127,09% CPU trên máy 32 vCPU), khiến thông lượng tụt xuống 150,00 req/s (độ trễ trung bình 1,0134 s), thua kém một nửa so với kiến trúc mở rộng C++ tránh GIL của vLLM đạt 363,76 req/s (0,4140 s, tận dụng 251,12% CPU)6.

Đối với các mô hình sử dụng chú ý cửa sổ trượt (Sliding Window Attention) như Mistral 7B (cửa sổ W = 4096 token), thay vì lưu toàn bộ lịch sử, hệ thống sử dụng Bộ đệm Vòng (Rolling Buffer KV Cache) dung lượng cố định W, trong đó KV của token thứ i ghi đè trực tiếp vào khe i mod W73. Cấu trúc này giữ mức tiêu thụ VRAM không đổi theo chiều dài chuỗi (giảm một nửa bộ nhớ ở chuỗi 8K và còn 1/8 ở chuỗi 32K), nhưng buộc nhân tính toán phải thực hiện bước mở vòng (un-rotation) hoặc nạp theo từng đoạn73. Bên cạnh đó, nghiên cứu StreamingLLM cảnh báo rằng việc ghi đè vòng thuần túy làm sụp đổ chất lượng chú ý khi chuỗi vượt quá kích thước cửa sổ nếu không ghim giữ lại một số token đầu chuỗi làm "hố chú ý" (attention sinks) bên cạnh vùng đệm xoay vòng77.

 

Cấu trúc KV Cache

Chi phí VRAM theo độ dài N

Lãng phí / Phân mảnh

Tra cứu & Chia sẻ liên yêu cầu

Điểm nghẽn vận hành điển hình

Cấp phát Liên tục (Truyền thống)

O(N_max) cấp trước

60%–80% (nội & ngoại bộ)61

Không chia sẻ tiền tố62

Cạn kiệt VRAM khi đồng thời cao, nghẽn batch size60.

PagedAttention (Block Table)

O(N) theo khối cố định

<4% (chỉ ở khối cuối)60

Tra bảng gián tiếp; chia sẻ CoW theo khối60

Bảng băm khối (APC) kém hiệu quả khi tiền tố phân nhánh phức tạp69.

RadixAttention (Radix Tree + Paging)

O(N_unique) qua nút chia sẻ

<4% (kế thừa phân trang)67

Khớp cây radix; giữ gốc bằng Tree-Aware LRU68

Rủi ro nghẽn Python GIL ở bộ định tuyến khi tải đồng thời rất lớn6.

Rolling Ring Buffer (SWA)

O(W) hằng số73

Không phân mảnh73

Ghi đè i % W, cần un-rotate khi tính attention73

Suy sụp phân phối Softmax nếu thiếu khe attention sinks cố định77.

4. Cấu trúc Cây Suy đoán và Automata cho Giải mã có Kiểm soát

Tối ưu hóa suy luận hiện đại mở rộng sang tổ chức lại cấu trúc dữ liệu của luồng token đầu ra nhằm tăng thông lượng xác minh song song và cưỡng chế cấu trúc cú pháp với chi phí CPU tối thiểu.

Cây Token Suy đoán

Trong giải mã suy đoán truyền thống, mô hình nháp sinh một chuỗi đơn tuyến tính; chỉ một token bị từ chối ở giữa sẽ buộc toàn bộ phần đuôi sau đó phải hủy bỏ80. Để tăng số token được chấp nhận mỗi lượt chạy mô hình mục tiêu, các hệ thống như Medusa, Sequoia và họ EAGLE biểu diễn tập ứng viên dưới dạng Cây Token Suy đoán (Speculative Token Tree) kết hợp Mặt nạ Chú ý Cây (Tree Attention Mask) để mỗi nút chỉ nhìn thấy các nút tổ tiên trên đúng nhánh của mình80.

Sự tiến hóa của họ mô hình EAGLE minh họa rõ tầm quan trọng của không gian biểu diễn và tính động của cây. Thế hệ EAGLE-1 chuyển từ dự đoán ở mức token (vốn chịu nhiễu ngẫu nhiên của bước lấy mẫu) sang dự đoán tự hồi quy ở mức đặc trưng ẩn áp chót trên một cấu trúc cây cố định, chỉ gắn thêm dưới 5% tham số cho mô hình 70B80. Đến EAGLE-2 (EMNLP 2024), tác giả nhận thấy xác suất chấp nhận phụ thuộc mạnh vào ngữ cảnh (sau "10+2=" chỉ cần 1 ứng viên "1", còn sau "10+2" cần nhiều nhánh hơn), từ đó xây dựng Cây Nháp Động Nhận thức Ngữ cảnh dựa trên điểm tin cậy ngay lúc suy luận mà không cần huấn luyện thêm mô hình, đạt tốc độ nhanh hơn khoảng 2 lần so với Medusa và 2,3 lần so với Lookahead trên MT-bench mà vẫn bảo toàn phân phối đầu ra nguyên bản80. Tiếp nối đó, EAGLE-3 bổ sung Training-Time Test (TTT) để giảm sai số tích lũy qua các bước nháp83, còn DEAGLE (bản thảo đánh giá trên OpenReview cuối năm 2025) đưa ra cơ chế dừng chiều sâu cây động bằng bỏ phiếu ba nhân tố (tổng xác suất sống sót, động lượng và độ dài kỳ vọng) để cắt giảm các lượt chạy thừa của cây cố định độ sâu84. Dù vậy, một vấn đề mở thực tế được ghi nhận trên kho mã nguồn SGLang là nhiều nhân chú ý suy luận vẫn chưa tối ưu triệt để cho bước xác minh cây nháp trên các kiến trúc mô hình mới85.

Automata và Cấu trúc Mặt nạ cho Giải mã có Ràng buộc

Khi ép LLM tạo đầu ra tuân thủ JSON Schema, câu lệnh SQL hoặc danh sách giá trị hữu hạn (enum), động cơ ràng buộc phải tính toán một mặt nạ bit (thường là mảng int32 kích thước B x ⌈|V|/32⌉) để gán -∞ cho các logit vi phạm trước bước Softmax86. Lựa chọn cấu trúc dữ liệu automaton quyết định trực tiếp sự đánh đổi giữa năng lực biểu diễn văn phạm và độ trễ trên CPU.

Với các biểu thức chính quy (regex), thư viện Outlines biên dịch văn phạm thành Máy trạng thái hữu hạn (FSM) và dựng sẵn bảng chuyển trạng thái ánh xạ tới tập token hợp lệ để tra cứu O(1) ở mỗi bước87. Tuy nhiên, FSM không hỗ trợ đệ quy lồng nhau của văn phạm phi ngữ cảnh (CFG), đồng thời chi phí biên dịch FSM trên bộ từ vựng lớn làm tăng vọt độ trễ TTFT (các phiên bản Outlines ≥ 1.x chuyển việc giải CFG sang lõi llguidance)89. Để hỗ trợ CFG đệ quy với hiệu năng cao, XGrammar sử dụng Automaton Đẩy xuống Cấp độ Byte (Byte-Level PDA) kèm ngăn xếp thực thi bền vững nhằm xử lý các token cắt ngang ranh giới quy tắc hoặc ký tự UTF-887. Trọng tâm tối ưu của XGrammar là phân hoạch bộ từ vựng thành hai nhóm: các token độc lập ngữ cảnh được kiểm tra và lưu đệm trước theo vị trí quy tắc, chỉ các token phụ thuộc ngăn xếp mới cần kiểm tra động lúc chạy87. Nhờ đó, một thử nghiệm tích hợp trên vLLM (đăng tải trên blog BentoML) ghi nhận XGrammar giảm thời gian mỗi token đầu ra (TPOT) tới 5 lần dưới tải cao so với Outlines v090, dù trên GPU ít đồng thời như RTX 4090 có ghi nhận Outlines vẫn có thể nhanh hơn do chi phí đồng bộ hóa91.

Tuy nhiên, hai công bố khoa học mới trong năm 2026 đã chỉ ra giới hạn của XGrammar ở hai thái cực khác nhau. Thứ nhất, đối với ràng buộc tập chuỗi hữu hạn (enum/IDs), nghiên cứu Trie Automaton (COLM 2026) phát hiện FSM và PDA gặp phải "bức tường lực lượng" (cardinality wall) do phải tính chuyển tiếp cho cả 256 giá trị byte tại mỗi trạng thái: trên Qwen3-8B (từ vựng 151K), thời gian biên dịch của XGrammar tăng từ 5 ms (K = 10) lên 695 ms (K = 10.000) và chạm 2,7 giây ở K = 100.000, còn llguidance biên dịch nhanh (0,6–24 ms) nhưng mất 73–141 µs/bước do phải quét O(|V|)92. Cấu trúc Trie Automaton dựng trực tiếp một cây tiền tố ký tự (byte trie) và tính trước mặt nạ nhận thức bộ từ vựng với tập làm việc dưới 1 KB (nằm gọn trong L1 cache CPU), giữ thời gian biên dịch phẳng ở 30–67 ms và tra cứu mỗi bước chỉ 0,65 µs (so với 5,9 µs của XGrammar tại K = 1.000); trong thử nghiệm phục vụ vLLM ở K = 1.000 và B = 256 trên A100, Trie đạt 219 req/s so với 7,5 req/s của XGrammar (nhanh hơn 29 lần) và vượt cả chế độ không ràng buộc (104 req/s) nhờ kết thúc sớm tại nút lá (3,2 so với 8,7 token/yêu cầu)92.

Thái cực thứ hai nằm ở văn phạm CFG đệ quy phức tạp. Trong benchmark năm 2026 của hệ thống GRID trên máy chủ H100 SXM5 (văn phạm tập con SQL, từ vựng Qwen2.5-0.5B-Instruct 151K), động cơ llguidance 1.7.6 (sử dụng lõi phân tích Earley/đạo hàm) duy trì độ trễ đuôi p99 ổn định nhất (1.200,2 µs trên Qwen2.5 và 351,7 µs trên gpt2), trong khi GRID dẫn đầu ở trung vị p50 (6,7 µs) nhưng vọt lên 15.906,2 µs ở p99 khi trượt bộ đệm (8% ca phải duyệt trie đệ quy), còn XGrammar 0.2.3 đạt p50 588,6 µs và p99 31.774,6 µs89. Như vậy, Trie tĩnh là cấu trúc tối ưu cho tập hữu hạn lớn, còn PDA và thuật toán Earley giữ lợi thế trên văn phạm đệ quy tổng quát89.

 

Động cơ / Cấu trúc dữ liệu

Văn phạm mục tiêu

Thời gian biên dịch (Qwen SQL / Enum)

Độ trễ tạo Mask (p50 / p99 hoặc trung bình)

Điểm mạnh & Điểm yếu đặc thù

Trie Automaton (COLM 2026, Rust)

Tập chuỗi hữu hạn (Enums, IDs)

30–67 ms (phẳng tới K = 100K)92

0,65 µs/bước (tập làm việc <1 KB trong L1)92

Vượt XGrammar 29x tại K = 1.000, B = 256; không xử lý CFG đệ quy92.

XGrammar 0.2.3 (Byte-Level PDA)

CFG đệ quy (JSON, SQL)

342,7 ms (SQL) / 2,7 s (Enum K = 100K)89

588,6 µs / 31.774,6 µs (SQL Qwen2.5)89

Phân hoạch từ vựng hiệu quả cho JSON; chậm khi tập enum lớn hoặc SQL đệ quy89.

llguidance 1.7.6 (Earley / Derivative)

CFG đệ quy tổng quát

979,5 ms (SQL) / 0,6–24 ms (Enum)89

14,9 µs / 1.200,2 µs (SQL Qwen2.5)89

Độ trễ đuôi p99 phẳng nhất trên CFG; tốn O(|V|) trên mỗi bước với enum lớn89.

GRID (Kernel v7: Walk + LALR)

CFG / SQL

1.297,2 ms (SQL)89

6,7 µs / 15.906,2 µs (SQL Qwen2.5)89

Dẫn đầu p50 với 0 ca từ chối (trúng cache 92%), p99 cao khi trượt cache lạnh89.

5. Chỉ mục Vector và Lượng tử hóa Không gian Cao chiều

Trong các hệ thống truy xuất tăng cường (RAG) và bộ nhớ tác tử đa phương thức, việc tìm kiếm láng giềng gần đúng (ANN) trên không gian hàng trăm tới hàng nghìn chiều đòi hỏi cân bằng chặt chẽ giữa dung lượng RAM, thông lượng QPS, tỷ lệ cập nhật và hỗ trợ lọc siêu dữ liệu93.

 

Chỉ mục / Cấu trúc

Nguyên lý Cấu trúc Dữ liệu

RAM ước tính (100M vector)

QPS & Recall tham chiếu

Cập nhật / Đa luồng

Kịch bản Tối ưu

HNSW

Đồ thị gần đúng nhiều tầng kiểu danh sách nhảy95.

~64 GB (128d) đến ~300 GB (~3 KB/vec ở 768d)94

~3.000 QPS @ 95% recall (SIFT-1M, FAISS)98

Xóa tạo tombstone làm tụt recall; đa luồng 16 thread tăng trễ 2–5x95.

Dưới 10M–100M vector vừa RAM, cần trễ <1–5 ms và recall ≥95%94.

IVF-PQ / OPQ

Phân cụm k-means (danh sách đảo) + mã hóa tích codebook93.

~6,4 GB (mã 64 B); 1 tỷ 768d nén từ 3 TB còn ~48 GB94

~900 QPS @ 96% (IVF); IVF-PQ 79,2% recall@10 SIFT1M98

Xóa khỏi danh sách dễ; quét tuần tự mở rộng tốt theo đa luồng93.

Quy mô tỷ vector giới hạn RAM, dữ liệu tĩnh hoặc nạp theo lô93.

ScaNN

Phân vùng kết hợp lượng tử hóa dị hướng102.

Trung bình (ước tính ~$580/tháng vs $2.400 HNSW ở 100M)97

Cân bằng recall/tốc độ rất cao trên dữ liệu tĩnh97

Không hỗ trợ chèn gia tăng; dựng lâu hơn HNSW/IVF-PQ 2–5x97.

Tập dữ liệu tĩnh, xây dựng lại định kỳ hàng đêm hoặc hàng tuần97.

DiskANN (Vamana)

Đồ thị 1 tầng có bậc ra giới hạn, tỉa cạnh đa hướng trên NVMe SSD96.

~3,2 GB (~32 byte/vector nén trong RAM)94

~8–12 ms p50, ~25 ms p99 (recall ngang HNSW)94

Giữ ~93% recall@5 vs ~88% HNSW sau 20 đợt 5% thay đổi98.

100M–10B vector vượt quá RAM, chấp nhận độ trễ đọc SSD94.

IVF / HNSW + RaBitQ

Xoay trực giao ngẫu nhiên + chiếu đỉnh siêu lập phương 1–7 bit104.

Nén tới 32x (1-bit: ~136 B cho 1024d)104; 0,60–0,72 GiB (GIST1M 5-bit)106

99,3% recall@10 SIFT1M (IVF-RaBitQ); 2.027 QPS @ 92,7% (HNSW-RaBitQ GIST1M)101

Không cần huấn luyện codebook PQ, thêm/xóa trực tiếp trên thư viện chuẩn104.

Embedding chiều cao (512–1024+d), cần nén mạnh mà không mất recall104.

Mặc dù HNSW là lựa chọn mặc định cho tìm kiếm trong RAM với độ phức tạp truy vấn O(ef · log n)94, cấu trúc đồ thị con trỏ nhiều tầng này bộc lộ ba điểm yếu lớn trong sản xuất. Thứ nhất, thao tác nhảy ngẫu nhiên qua danh sách kề phá hủy tính cục bộ của bộ đệm CPU dưới tải đa luồng cao: một bài phân tích thực hành ước tính độ trễ HNSW tăng 2–5 lần ở 16 luồng so với phép quét tuần tự trong phân vùng của IVF-PQ97. Thứ hai, việc xóa một nút khỏi HNSW không thể cắt bỏ trực tiếp mà không làm gãy đường đi nối qua nút đó, buộc hệ thống phải đánh dấu "bia mộ" (tombstone); khi tỷ lệ thay đổi danh mục vượt 20% mỗi tháng, chỉ mục phình to và tụt recall, đòi hỏi xây dựng lại toàn bộ (sau 20 đợt cập nhật 5%, đồ thị Vamana của DiskANN giữ được ~93% recall@5 trong khi HNSW giảm còn ~88%)93.

Thứ ba, tìm kiếm kết hợp bộ lọc siêu dữ liệu (filtered search) làm rạn nứt tính liên thông của đồ thị HNSW khi các nút bị loại tạo thành rào cản chia cắt đồ thị thành nhiều đảo cô lập107. Thuật toán ACORN-1 (được tích hợp trong Qdrant, Apache Lucene và DuckDB) giải quyết vấn đề này lúc truy vấn bằng cách mở rộng sang láng giềng bậc hai (neighbors of neighbors) bất cứ khi nào láng giềng trực tiếp không đạt bộ lọc107. Trong Apache Lucene (thử nghiệm trên 8 triệu vector 768 chiều), ACORN-1 được kích hoạt khi có từ 40% dữ liệu trở lên bị lọc bỏ108. Tuy nhiên, benchmark tháng 8/2026 của Qdrant trên 1 triệu vector cho thấy sự đánh đổi tinh tế giữa mở rộng lúc chạy (ACORN) và bổ sung cạnh từ lúc lập chỉ mục (Filterable HNSW): trên bộ lọc kép độ chọn lọc 1% tại ef=512, Filterable HNSW đạt 91,2% recall chỉ trong 4,9 ms, nhanh gấp 4 lần so với ACORN (20,1 ms để đạt 90,3% recall); ngược lại, ACORN thắng áp đảo (99,6% so với 92,5%) trên các điều kiện giao hoặc trường dữ liệu vượt ngưỡng tràn không được bổ sung cạnh sẵn; còn khi độ chọn lọc tụt xuống quá thấp (như 0,012%), cả đồ thị lẫn ACORN đều kém hiệu quả và trình lập lịch phải chuyển sang quét chỉ mục đảo thông thường107.

Về phía nén vector, cấu trúc lượng tử hóa RaBitQ (Gao & Long, công bố tại SIGMOD 2024 và mở rộng tại SIGMOD 2025) khắc phục ba nhược điểm cố hữu của IVF-PQ là chi phí huấn luyện codebook đắt đỏ, suy giảm chất lượng khi phân phối dữ liệu trôi dạt và tốc độ tra bảng LUT chậm104. RaBitQ quy tâm và chuẩn hóa vector về mặt cầu đơn vị, áp dụng ma trận xoay trực giao ngẫu nhiên kiểu Johnson–Lindenstrauss để cân bằng năng lượng trên mọi chiều, rồi chiếu lên đỉnh gần nhất của siêu lập phương 104. Mỗi chiều được nén thành 1 bit (hoặc mở rộng 4–7 bit) kèm bộ ước lượng tích vô hướng không chệch có sai số giới hạn tiệm cận tối ưu O(1/√D), cho phép tính khoảng cách bằng phép bit AND + popcount (qua tập lệnh AVX512VPOPCNTDQ hoặc FastScan), nhanh gấp 3 lần tra bảng PQ105. Theo tài liệu từ nhóm tác giả thư viện RaBitQ, một bản tóm tắt kết quả SIGMOD 2024 ghi nhận IVF-RaBitQ đạt 99,3% recall@10 trên SIFT1M so với 79,2% của IVF-PQ101; trên tập GIST1M của thư viện chính thức RaBitQ Library, bản 5-bit IVF-RaBitQ đạt 976 QPS ở 93,3% recall@10 (chiếm 0,60 GiB) và HNSW-RaBitQ đạt 2.027 QPS ở 92,7% recall@10 (0,72 GiB)106; đồng thời phân tích của Milvus ghi nhận 1-bit RaBitQ đạt 94,7% recall ở thông lượng cao gấp 3,6 lần IVF_FLAT với bộ nhớ chỉ bằng 1/32105. Tuy nhiên, phân tích thực nghiệm từ dnotitia nhấn mạnh phép xoay ngẫu nhiên là yếu tố sống còn đối với dữ liệu dị hướng như GIST1M (tắt xoay khiến recall@1/10/100 rớt xuống 65,8%/57,1%/35,0%), trong khi trên OpenAI5M vốn đẳng hướng sẵn thì hiệu năng đạt 100%/99,9%/78,6% bất kể bật hay tắt xoay; ngoài ra lượng tử hóa truy vấn xuống 4 bit (Bq=4) giúp tăng QPS thêm 2,46–3,05 lần mà hầu như không giảm recall112.

6. Cấu trúc Đồ thị Trình biên dịch AI, Lập lịch Bộ nhớ và Hạ tầng Phân tán

Khi huấn luyện và biên dịch mô hình ở quy mô lớn, cấu trúc dữ liệu của đồ thị tính toán quyết định khả năng tái sử dụng vùng đệm, giảm tải HBM cho vi phân tự động và tối ưu băng thông mạng giữa hàng nghìn GPU.

Lập kế hoạch Bộ nhớ Tĩnh và Động

Sự khác biệt cốt lõi giữa các trình biên dịch nằm ở thời điểm biết trước kích thước tensor113. Trong hệ sinh thái OpenXLA, đồ thị đầu vào từ phương ngữ MLIR giữ thuộc tính gán đơn tĩnh SSA (StableHLO/VHLO) được hạ tầng xuống đồ thị HloModule/HloInstruction (và LMHLO khi vật chất hóa vùng đệm memref)114. Do toàn bộ kích thước tensor biết trước tại thời điểm biên dịch, bộ mô phỏng HeapSimulator của XLA dùng một Cây khoảng thời gian (BufferIntervalTreeNode lưu thời điểm cấp phát start, giải phóng end, giá trị cực đại nhánh con subtree_end và thông tin Chunk) kết hợp bản đồ vùng trống free_chunks_ cùng các chiến lược sắp xếp không gian/thời gian (kSpatial, kTemporal, FastMerge/FastSplit) để xếp chồng toàn bộ vùng đệm có vòng đời không giao nhau ngay lúc biên dịch114.

Ngược lại, chế độ chạy từng bước (Eager) của PyTorch ép mỗi phép tính như relu(matmul(a,b)+c) phải thực hiện ít nhất 6 lượt đọc ghi VRAM và buộc hệ thống phải dựa vào bộ cấp phát động CUDACachingAllocator1. Theo đặc tả kỹ thuật năm 2022 của CUDACachingAllocator, hệ thống duy trì các bộ đệm riêng theo từng luồng CUDA (CUDA stream) và phân chia thành hai nhóm: small_pool (cho tensor <1 MB, xin cấp phát theo khối 2 MB từ CUDA) và large_pool (cho tensor ≥1 MB, xin khối 20 MB), thực hiện tìm kiếm vừa khít nhất (best-fit), tách/gộp khối liền kề và có tùy chọn làm tròn theo lũy thừa bậc 2 (roundup_power2_divisions, chấp nhận lãng phí trung bình 1/4 ở N = 1 hoặc 1/8 ở N = 2 để ổn định trạng thái khi độ dài chuỗi biến thiên)119. Khi dùng torch.compile, TorchDynamo trích xuất đồ thị FX Graph để TorchInductor vừa hợp nhất các nhân Triton (rút 6 lượt truyền VRAM ở ví dụ trên xuống còn 2) vừa lập lịch tái sử dụng vùng đệm tĩnh/ký hiệu thông qua lan truyền miền giá trị (SpecPropPass, ValueRangeBasedSymShapeEval, MemoryPlanningPass)1. Tuy nhiên, tái sử dụng vùng đệm với kích thước động tiềm ẩn lỗi tinh vi: một báo cáo lỗi từ kiểm thử fuzzing trên kho mã nguồn PyTorch (Issue #204917) cho thấy với dynamic=True, hàm kiểm tra điều kiện trả buffer về bể tái sử dụng của Inductor chỉ xét xem bản thân buffer sắp chết có phải là view hay không mà quên kiểm tra xem có đầu ra đang sống nào của đồ thị là view trỏ vào bên trong nó hay không, gây ghi đè sai kết quả im lặng (sai lệch tối đa 1,38 so với tham chiếu float64)123.

Đồ thị Vi phân Tự động, Phân hoạch Cắt Cực tiểu và Cái túi Hai Hàng

Vi phân tự động chế độ ngược truyền thống ghi lại tuần tự các phép toán vào một băng ghi gọi là Danh sách Wengert (Wengert List / Tape) và lưu giữ các giá trị kích hoạt trung gian để phục vụ pha ngược124. Nhưng đối với các toán tử giới hạn bởi băng thông bộ nhớ như hàm điểm (tanh, cos, chuẩn hóa), chi phí ghi biến trung gian ra bộ nhớ toàn cục rồi đọc lại đắt hơn nhiều so với việc tính toán lại (recomputation) ngay trong nhân hợp nhất126.

AOTAutograd mô hình hóa đồ thị hợp nhất xuôi-ngược bằng bài toán Luồng cực đại / Cắt cực tiểu (s-t Min-Cut) với cấu trúc tách nút để xác định tập trung gian tối ưu cần giữ lại126. Công bố tại MLSys 2023 cho thấy phân hoạch min-cut cải thiện đồng thời cả bộ nhớ lẫn thời gian chạy: đạt mức tăng thông lượng trung bình nhân 12% và tăng kích thước lô tối đa tới 1,75 lần trên các mô hình chuẩn (và lên tới 10x tốc độ / giảm 5x bộ nhớ đỉnh trên các mẫu toán tử mới, hoặc giảm 45% bộ nhớ ở chế độ MinCut-Aggressive)126.

Khi áp đặt ngân sách bộ nhớ cứng W, bài toán lựa chọn toán tử lưu trữ chuyển thành bài toán Cái túi 0/1 (0/1 Knapsack). Trước phiên bản 2.10, bộ giải mặc định của PyTorch (dp_knapsack) cấp phát bảng quy hoạch động 2 chiều đầy đủ kích thước (n+1) x (W+1); theo bài báo công bố năm 2026 (đã hợp nhất vào PyTorch 2.10), chỉ với n = 100 toán tử và W ≈ 3,8×10⁸, bảng 2D này phình tới ~304 GB và gây sập tràn bộ nhớ (OOM) trên máy RAM 64 GB128. Thuật toán mới dp_knapsack_sliding_hirschberg thay thế bảng 2D bằng cửa sổ trượt chỉ gồm 2 hàng kết hợp chia để trị Hirschberg cùng một ngăn xếp LIFO tường minh để truy vết nghiệm chính xác, giảm độ phức tạp không gian từ O(nW) xuống O(W) (thu gọn bảng DP từ ~304 GB xuống ~6 GB tại n = 100), chạy nhanh hơn 25%–28% và mở rộng quy mô đồ thị khả giải lên 20 lần (chạy được n = 2.000 với đỉnh RAM 58,4 GB trên máy 64 GB dùng CPU AMD Ryzen 7 9800X3D)128.

Cấu trúc Dữ liệu Phân tán và Thuật toán Tập thể NCCL

Để trừu tượng hóa mô hình song song SPMD (Single Program, Multiple Data), PyTorch 2 định nghĩa DeviceMesh (mảng n chiều ánh xạ tô-pô cụm GPU thành các nhóm tiến trình trực giao cho FSDP liên nút và Tensor Parallel nội nút) kết hợp cấu trúc DTensor mang mô tả bố trí Placement gồm ba trạng thái Shard(dim), Replicate() và Partial(reduce_op)129. Bộ điều phối của PyTorch chặn phép toán chuẩn để tự động chèn các lệnh truyền thông tập thể khả vi (như all_gather, all_reduce) cho cả lượt xuôi lẫn lan truyền ngược129.

Trên tầng lưu trữ tham số huấn luyện, phân tích dung lượng cho mô hình 7B (FP32 Adam trên 8 GPU) chỉ ra mức giảm bộ nhớ mỗi GPU từ 112 GB ở DDP xuống lần lượt 63 GB (ZeRO-1), 38,5 GB (ZeRO-2) và 14 GB (ZeRO-3 / FSDP2)131. Khi mô hình vượt tổng VRAM cụm GPU, ZeRO-Infinity kết hợp phân mảnh ZeRO-3 với hoán chuyển ra CPU RAM ghim trang (pinned memory) và ổ cứng NVMe thông qua kỹ thuật Chia khối Hướng bộ nhớ (Memory-Centric Tiling—tải và giải phóng từng lát cắt của lớp Linear), được bài báo gốc minh họa khả năng huấn luyện mô hình quy mô 10–100 nghìn tỷ tham số trên một nút DGX-2 (16 GPU V100)132.

Ở tầng mạng, hiệu năng đồng bộ gradient phụ thuộc vào cấu trúc truyền dẫn của NCCL. Thuật toán Ring All-Reduce tổ chức P GPU thành vòng tròn và chia tải thành P mảnh, đạt ngưỡng tối ưu băng thông lý thuyết với đúng 2(P-1)/P · N byte truyền nhận mỗi GPU (đạt 700–800 GB/s thực tế trên kết nối NVLink+NVSwitch 900 GB/s của HGX H100), nhưng chịu độ trễ tăng tuyến tính theo 2(P-1) bước nhảy (14 bước trên 8 GPU, 126 bước trên 64 GPU)136. Ngược lại, Tree All-Reduce (cây nhị phân kép của NCCL) chỉ mất ~2·log₂(P) bước nhảy, nhờ đó thắng Ring ở các gói tin nhỏ nơi độ trễ khởi tạo chiếm ưu thế—theo phân tích trên cụm 8x H100, điểm giao cắt hiệu năng giữa Tree và Ring nằm ở khoảng ~256 KiB (trên Hopper+ còn có NVLS/NVLSTree tận dụng bộ cộng trong phần cứng NVSwitch)136. Cũng cần lưu ý rằng việc tự chế All-Reduce thưa trên PyTorch (đệm chỉ số cục bộ và gather về rank 0 để khử trùng lặp) hiện không được NCCL hỗ trợ bản địa và dễ rơi về Gloo/PCIe với chi phí đồng bộ nhiều pha cao hơn cả truyền dày đặc137.

7. Cấu trúc Dữ liệu cho Học tăng cường và Tìm kiếm Heuristic

Trong học tăng cường (RL) và các thuật toán tìm kiếm trên không gian trạng thái lớn, nút thắt hiệu năng nằm ở tốc độ lấy mẫu có trọng số, cấu trúc hàng đợi ưu tiên và phát hiện trùng lặp trạng thái.

Cây Tổng trong Prioritized Experience Replay

Phương pháp Prioritized Experience Replay (PER, công bố tại ICLR 2016) cải thiện hiệu quả mẫu bằng cách lấy mẫu chuyển đổi tỷ lệ theo độ lớn sai số TD: (với ), và hiệu chỉnh độ lệch phân phối bằng trọng số (đạt kết quả vượt trội uniform replay trên 41/49 trò chơi Atari)138. Để tránh độ phức tạp O(N) khi cập nhật trọng số và lấy mẫu, biến thể tỷ lệ sử dụng SumTree—một cây phân đoạn nhị phân lưu phẳng trên mảng 2C - 1 phần tử (C lá lưu , mỗi nút cha lưu tổng hai con và gốc tree[0] lưu tổng ưu tiên toàn bộ đệm)139. Kết hợp kỹ thuật lấy mẫu phân tầng đoạn (chia tổng gốc thành batch_size khoảng đều nhau rồi duyệt từ gốc xuống lá), cả hai thao tác cập nhật ưu tiên (update) và rút mẫu (get_leaf) đều đạt thời gian O(log N), đi kèm một cây phân đoạn cực tiểu (hoặc min-heap) để tính cho chuẩn hóa trọng số quan trọng cũng trong O(log N)139. Trong khi đó, biến thể xếp hạng (rank-based PER, ít nhạy cảm với nhiễu ngoại lai hơn) dùng đống nhị phân kết hợp các ranh giới phân vị tính trước140.

Hàng đợi Ưu tiên trong Tìm kiếm Heuristic: Thực nghiệm so với Lý thuyết

Đối với thuật toán Dijkstra và A*, Đống Fibonacci (Fibonacci Heap) đạt độ phức tạp lý thuyết khấu hao O(1) cho push và decrease_key, cùng O(log n) cho pop_min7. Tuy nhiên, hàng loạt kiểm chứng thực nghiệm—từ luận văn đánh giá trên đồ thị thưa (Đại học Lund, 2025), báo cáo kỹ thuật mạng lưới giao thông quy mô lớn của Outerloop, tới bài báo tại AAAI SOCS trên bộ lập kế hoạch Fast Downward—đều kết luận cấu trúc lưu bằng con trỏ rời rạc của Đống Fibonacci và Hollow Heap gây tràn bộ nhớ và trượt bộ đệm L1/L2 quá nặng, đồng thời vẫn có chi phí trường hợp xấu nhất O(n) ở phép xóa đơn lẻ7. Trong thực tế vận hành, Đống nhị phân lưu trên mảng liên tục (Binary Heap) hoặc Đống 3-ary/4-ary (với đống 4-ary đứng đầu trong thử nghiệm của Outerloop) vượt trội hoàn toàn trên đồ thị thưa7. Riêng khi hàm chi phí hoặc trọng số cạnh là số nguyên (hay lượng tử hóa) bị chặn trong khoảng C, Hàng đợi Nhóm 2 chiều (2D Bucket Queue / Thuật toán Dial) tổ chức mảng các ngăn xếp đánh chỉ số mô-đun C+1 đạt thời gian O(m + dc) hoặc O(m + nC) với mức tiêu thụ bộ nhớ và tốc độ tối ưu hơn các cấu trúc đống cây144.

Bảng băm Zobrist và Bảng Chuyển vị trong Tìm kiếm Song song và MCTS

Để phát hiện nhanh các trạng thái hoán vị trùng lặp trong cây trò chơi hay tìm kiếm cây Monte Carlo (MCTS), kỹ thuật chuẩn mực là Băm Zobrist (Zobrist Hashing) kết hợp Bảng Chuyển vị (Transposition Table)148. Bằng cách khởi tạo sẵn bảng các khóa bit ngẫu nhiên 64-bit cho từng cặp (quân cờ, ô bàn cờ) và thực hiện phép XOR tích lũy, Zobrist cho phép cập nhật và hoàn tác trạng thái chỉ trong thời gian O(1) qua vài phép XOR mà không cần duyệt lại toàn bàn cờ148.

Ba kỹ thuật cấu trúc quyết định hiệu năng và tính an toàn khi triển khai Zobrist ở quy mô thực tế. Thứ nhất, tối ưu bố cục mảng phẳng giúp tránh chi phí quản lý đối tượng và thu gom rác: trong phép đo tháng 11/2026 trên Node.js 22.17 / V8 12.4 (CPU Intel Core i5-13420H), việc tách mã băm 64-bit thành hai mảng 32-bit phẳng (Uint32Array cho hashLo và hashHi) đạt trên 260 triệu lượt cập nhật + tra cứu mỗi giây (3,72 ms cho 1 triệu lượt), nhanh hơn 18,5 lần so với BigUint64Array (69,1 ms) và gần 500 lần so với Map dùng khóa chuỗi, đồng thời kích thước bảng là số nguyên tố lớn hoặc việc lưu kèm khóa 64-bit đầy đủ giúp triệt tiêu rủi ro đụng độ làm sai nước đi151. Thứ hai, trong tìm kiếm A* song song phân tán (HDA*), công bố tại AAAI 2016 (Jinnai & Fukunaga) chỉ ra hàm băm Zobrist chuẩn làm 72% nút sinh ra trên 4 luồng và 92% trên 16 luồng bị đẩy sang bộ xử lý khác (trên bài toán 24-puzzle); cấu trúc lai Abstract Zobrist Hashing (AZH) giải quyết bằng cách chiếu đặc trưng thô qua hàm trừu tượng A(xᵢ) trước khi XOR nhằm giữ các trạng thái lân cận trên cùng một luồng154. Thứ ba, với MCTS song song có dùng bảng chuyển vị (biến cây thành đồ thị DAG), luồng duyệt phải giữ đồng thời 3 khóa mutex (nút cha, nút con tốt nhất hiện tại, và nút con đang xét) theo thứ tự nhất quán (hoặc dùng mutex chia sẻ) để tránh ghi đè lúc mở rộng, đồng thời các khóa hành động Zobrist bắt buộc phải khác 0 và đôi một phân biệt để phép chuyển vị không dẫn tới việc cùng một luồng tự khóa hai lần lên chính một mutex gây deadlock155.

8. Ma trận Quyết định Lựa chọn Cấu trúc Dữ liệu theo Bối cảnh Triển khai

 

Bài toán / Nút thắt Hệ thống

Cấu trúc dữ liệu Khuyến nghị

Điều kiện Hòa vốn / Ngưỡng Kích hoạt

Rủi ro & Bẫy Triển khai Cần Tránh

Tích chập & Tensor Core GPU

Bố cục NHWC (Channels-Last)12

Mọi GPU có Tensor Core (từ Volta trở lên)14.

Tránh giữ NCHW gây phát sinh nhân Reformat ẩn hoặc phình workspace14.

Chú ý Chuỗi dài & Nhân SMEM

Tiling SRAM + Online Softmax + Bộ đệm vòng TMA + CuTe Swizzle2

Chuỗi dài hoặc nhân cần truy cập cột trên SMEM đa luồng2.

Không trộn lẫn đọc/ghi có và không có swizzle; theo dõi L1 Wavefronts Shared Excessive25.

Ma trận Thưa & Nén Trọng số

cuBLAS (dày đặc) / SMaT (SpMM) / Marlin / MXFP437

Thưa phi cấu trúc cần ≥98%–99% số 0 (hoặc ≥78%–96% với SMaT)33; 2:4 chỉ lợi ở lô M lớn41.

Không bật 2:4 ở chế độ decode M nhỏ hoặc thiếu hợp nhất nhân5; thận trọng tụt độ chính xác suy luận42.

Quản lý KV Cache LLM Serving

PagedAttention + RadixAttention (trùng tiền tố >60%)67

Tiền tố trùng lặp >60% và tác tử rẽ nhánh: dùng RadixAttention; Prompt độc nhất: tương đương71.

Kiểm tra nghẽn khóa Python GIL ở bộ định tuyến cây khi mức đồng thời lên hàng trăm yêu cầu6.

Giải mã có Ràng buộc

Trie Automaton (tập hữu hạn) / llguidance hoặc XGrammar (CFG)89

Tập enum K ≥ 300: ưu tiên Trie (vượt 29x tại K = 1.000)92; CFG đệ quy nhạy p99: ưu tiên llguidance89.

Tránh dùng FSM biên dịch cho danh mục hàng chục nghìn mục vì chạm tường biên dịch92.

Truy xuất Vector Quy mô lớn

HNSW (<100M, đủ RAM) / DiskANN (>100M, tiết kiệm RAM) + RaBitQ94

Lọc ≥40% phần tử hoặc giao nhiều trường ngoài trần cạnh: bật ACORN-1107; vector dị hướng: bật xoay RaBitQ112.

Dựng lại HNSW định kỳ nếu thay đổi >20%/tháng (tránh tombstone)95; chuyển quét chỉ mục đảo dưới ~0,01%107.

Biên dịch Đồ thị & Phân tán

AOTAutograd Min-Cut + dp_knapsack_sliding_hirschberg + DTensor126

Đồ thị lớn giới hạn VRAM hoặc tập hợp NCCL (Tree <256 KiB, Ring ≥256 KiB trên 8x H100)128.

Với hình dạng động trong Inductor, kiểm tra lỗi tái sử dụng buffer khi đầu ra là view trỏ vào nó123.

Hàng đợi & Bảng Băm Tìm kiếm

Đống nhị phân / 4-ary mảng hoặc Dial's Bucket Queue + Zobrist 32-bit phẳng8

Mọi bài toán đồ thị thưa thực tế hoặc tìm kiếm song song MCTS / HDA*7.

Tránh Đống Fibonacci vì trượt cache7; dùng Abstract Zobrist giảm truyền thông154; khóa 3 nút nhất quán trên MCTS155.

Nguồn trích dẫn

  1. How `torch.compile` Solves the Eager Execution Problem in PyTorch, https://medium.com/@soydotrun/how-torch-compile-solves-the-eager-execution-problem-in-pytorch-4d45ef7e7777
  2. 2.2c: FlashAttention — IO Analysis and Evolution - Hugging Face, https://huggingface.co/blog/atharv6f/flash-attention-io-analysis
  3. FlashAttention: Fast and Memory-Efficient Exact Attention with IO, https://3dvar.com/Dao2022FlashAttention.pdf
  4. Chapter 3 Introduction to GPU - GitHub, https://github.com/datawhalechina/zero-to-sglang/blob/main/course-material/eng/part1/Chapter3_Introduction_to_GPU.md
  5. GPU MODE Lecture 11: Sparsity - Christian Mills, https://christianjmills.com/posts/cuda-mode-notes/lecture-011/
  6. Radix vs. PagedAttention Scaling (SGLang / vLLM) · Issue #37730, https://github.com/vllm-project/vllm/issues/37730
  7. A Performance Study of Priority Queues: Binary Heap, Fibonacci, https://lup.lub.lu.se/student-papers/record/9201073/file/9201074.pdf
  8. Performance Effects of heap structure - Outer Loop Consulting, https://www.outerloop.io/docs/OuterloopWhitePaper-PerformanceEffectsOfHeapStructure.pdf
  9. Nvidia Modelopt structured 2:4 weight sparsity showing no ... - GitHub, https://github.com/NVIDIA/Model-Optimizer/issues/1974
  10. NHWC vs NCHW : A memory access perspective on GPUs - Medium, https://medium.com/@deepika_writes/nhwc-vs-nchw-a-memory-access-perspective-on-gpus-4e79bd3b1b54
  11. What Is Warp Divergence? The Hidden GPU Throughput Killer, https://www.spheron.network/blog/what-is-warp-divergence-the-hidden-gpu-throughput-killer/
  12. NCHW vs NHWC · Issue #13179 - GitHub, https://github.com/ultralytics/ultralytics/issues/13179
  13. Understand Tensor Data Layout - Wentao's Blog, https://wentao.site/tensor_data_layout/
  14. NHWC vs NCHW convolution - cuDNN - NVIDIA Developer Forums, https://forums.developer.nvidia.com/t/nhwc-vs-nchw-convolution/111065
  15. How much faster is NCHW compared to NHWC in TensorFlow, https://stackoverflow.com/questions/44280335/how-much-faster-is-nchw-compared-to-nhwc-in-tensorflow-cudnn
  16. [RFC][Tensor Core] Optimization of CNNs on Tensor Core - RFC, https://discuss.tvm.apache.org/t/rfc-tensor-core-optimization-of-cnns-on-tensor-core/6004
  17. TensorRT NCHW vs cuDNN NHWC - NVIDIA Developer Forums, https://forums.developer.nvidia.com/t/tensorrt-nchw-vs-cudnn-nhwc/177492
  18. FlashAttention-3 & GPU Kernel Interview Guide (2026), https://www.techinterview.net/blog/flashattention-3-triton-guide
  19. FlashAttention-3:Fast and Accurate Attention with Asynchrony ... - arXiv, https://arxiv.org/html/2407.08608v1
  20. FlashAttention-3: Fast and Accurate Attention with Asynchrony and, https://pytorch.org/blog/flashattention-3/
  21. Warps, Memory Hierarchy, and Why Bandwidth Beats FLOPS, https://pub.towardsai.net/warps-memory-hierarchy-and-why-bandwidth-beats-flops-how-gpus-actually-work-part-1-06170834ad33
  22. FlashAttention-3: Fast and Accurate Attention with Asynchrony and, https://openreview.net/forum?id=tVConYid20
  23. Shared Memory Bank Conflicts: Why Your Quantized Kernel Is Slow, https://www.spheron.network/blog/shared-memory-bank-conflicts-why-your-quantized-kernel-is-sl/
  24. Requesting clarification for Shared Memory Bank Conflicts and, https://forums.developer.nvidia.com/t/requesting-clarification-for-shared-memory-bank-conflicts-and-shared-memory-access/268574
  25. Flash Attention from Scratch Part 4: Bank Conflicts & Swizzling, https://lubits.ch/flash/Part-4
  26. KernelWiki/wiki/techniques/swizzling.md at master - GitHub, https://github.com/mit-han-lab/KernelWiki/blob/master/wiki/techniques/swizzling.md
  27. CuTe Swizzle - Lei Mao's Log Book, https://leimao.github.io/blog/CuTe-Swizzle/
  28. Bank Conflict Issue in CUDA Shared Memory Access - Stack Overflow, https://stackoverflow.com/questions/78235550/bank-conflict-issue-in-cuda-shared-memory-access
  29. Why is there still a bank conflict when using swizzle to process data?, https://stackoverflow.com/questions/79264081/why-is-there-still-a-bank-conflict-when-using-swizzle-to-process-data
  30. High-Performance Sparse Linear Algebra on NVIDIA GPUs with, https://graphblas.org/GraphBLAS-Pointers/Slides/SIAMCSE21-Nvidia-cuSPARSE.pdf
  31. GE-SpMM: General-Purpose Sparse Matrix-Matrix Multiplication on, https://nicsefc.ee.tsinghua.edu.cn/%2Fnics_file%2Fpdf%2Fpublications%2F2020%2FSC20_320.pdf
  32. Why cuSparse is much slower than cuBlas for sparse matrix, https://stackoverflow.com/questions/30118673/why-cusparse-is-much-slower-than-cublas-for-sparse-matrix-multiplication
  33. cusparseSpMM fp32 is slower than cublas cublasSgemm, https://forums.developer.nvidia.com/t/cusparsespmm-fp32-is-slower-than-cublas-cublassgemm/249112
  34. Efficient Sparse-Dense Matrix-Matrix Multiplication on GPUs Using, https://arxiv.org/pdf/2005.14469
  35. cuSPARSE SpMV/SpMM performance and upperbound, https://www.researchgate.net/figure/cuSPARSE-SpMV-SpMM-performance-and-upperbound-Nvidia-Pascal-P100-GPU-Fig-1-displays_fig1_325706323
  36. Graph Traversal on Tensor Cores: A BFS Framework for Modern GPUs, https://arxiv.org/html/2606.05081
  37. High Performance Unstructured SpMM Computation Using Tensor, https://arxiv.org/html/2408.11551v1
  38. Divergence-Aware Warp Scheduling - Purdue Engineering, https://engineering.purdue.edu/tgrogers/publication/rogers-micro-2013/rogers-micro-2013.pdf
  39. Warp-Consolidation: A Novel Execution Model for GPUs, https://www.ssslab.cn/assets/papers/2018-li-warpconsolidation.pdf
  40. Sparse Tensor Core Speedup: The 2:4 Sparsity Myth | Spheron, https://www.spheron.network/blog/myth-nvidia-s-2-4-sparsity-doubles-your-inference-throughput/
  41. SpenseGPT: Practical One-shot Pruning Enabling Sparse ... - arXiv, https://arxiv.org/html/2606.10445v1
  42. SlideSparse: Fast and Flexible (2N-2):2N Structured Sparsity - arXiv, https://arxiv.org/html/2603.05232v1
  43. Exploiting NVIDIA Ampere Structured Sparsity with cuSPARSELt, https://developer.nvidia.com/blog/exploiting-ampere-structured-sparsity-with-cusparselt/
  44. SlideSparse: Fast and Flexible (2N-2):2N Structured Sparsity, https://openreview.net/pdf?id=GQ17DjsBcq
  45. LLM quantization: from FP32 down to INT4 - NEU, https://fit.neu.edu.vn/en/post/llm-quantization-from-fp32-down-to-int4
  46. QLORA: Efficient Finetuning of Quantized LLMs - arXiv, https://arxiv.org/pdf/2305.14314
  47. QLoRA Explained: How 4-bit Quantization Enables Efficient LoRA, https://medium.com/@mailpraveenreddy.c/qlora-explained-how-4-bit-quantization-enables-efficient-lora-fine-tuning-7fe16aef9b62
  48. What Breaks Below 4-Bit? NF4 and QLoRA Explained ML Engineer, https://www.youtube.com/watch?v=BIjo8GKOiqA
  49. AutoAWQ+Marlin: Efficient INT4 Inference - Emergent Mind, https://www.emergentmind.com/topics/autoawq-marlin
  50. MARLIN: Mixed-Precision Auto-Regressive Parallel Inference ... - arXiv, https://arxiv.org/pdf/2408.11743
  51. MARLIN: Mixed-Precision Auto-Regressive Parallel Inference ... - arXiv, https://arxiv.org/html/2408.11743v1
  52. BitDecoding: Unlocking Tensor Cores for Long-Context LLMs ... - arXiv, https://arxiv.org/html/2503.18773v1
  53. GitHub - IST-DASLab/marlin: FP16xINT4 LLM inference kernel that, https://github.com/IST-DASLab/marlin
  54. [Tracking] Replace Marlin with Humming across NVIDIA architectures, https://github.com/vllm-project/vllm/issues/65560
  55. MXFP4: microscaling 4-bit float with shared 8-bit scale - ZeroEntropy, https://zeroentropy.dev/concepts/mxfp4/
  56. MXFP4 Quantization on GPU Cloud: Deploy LLMs at 4-Bit Precision, https://www.spheron.network/blog/mxfp4-microscaling-quantization-gpu-cloud/
  57. Choosing the right compression scheme - LLM Compressor Docs, https://docs.vllm.ai/projects/llm-compressor/en/latest/steps/choosing-scheme/
  58. What's MXFP4? The 4-Bit Secret Powering OpenAI's GPT‑OSS, https://huggingface.co/blog/RakshitAralimatti/learn-ai-with-me
  59. Marlin Fix: NVFP4 Actually Works on SM121 (DGX Spark), https://forums.developer.nvidia.com/t/marlin-fix-nvfp4-actually-works-on-sm121-dgx-spark/365119
  60. vLLM and PagedAttention: high-throughput serving for large, https://fit.neu.edu.vn/en/post/vllm-and-pagedattention-high-throughput-llm-serving-en
  61. vLLM: Easy, Fast, and Cheap LLM Serving with PagedAttention, https://vllm.ai/blog/2023-06-20-vllm
  62. vLLM: How PagedAttention Solved the Memory Crisis in LLM Serving, https://medium.com/@serahabensour/vllm-how-pagedattention-solved-the-memory-crisis-in-llm-serving-61aece9fdf83
  63. How PagedAttention resolves memory waste of LLM systems, https://developers.redhat.com/articles/2025/07/24/how-pagedattention-resolves-memory-waste-llm-systems
  64. PagedAttention & vLLM for Efficient LLM Inference, https://llmsystem.github.io/llmsystem2025spring/assets/files/llmsys-22-vLLM_woosuk_kwon-1f34697dbb1a1fb5b798daf6eff14b67.pdf
  65. Paged Attention - vLLM docs, https://docs.vllm.ai/en/stable/design/paged_attention/
  66. PagedAttention Explained: The 1960s OS Trick Behind vLLM's Speed, https://www.youtube.com/watch?v=vtykPhnvQ74
  67. SGLang vs vLLM (2026): Which Is Best for Your Workload?, https://tensormesh.ai/learn/vllm-vs-sglang/
  68. vLLM vs SGLang: PagedAttention vs RadixAttention in 2026, https://www.praveentechworld.com/blog/vllm-pagedattention-vs-sglang-radixattention-benchmarks
  69. RadixAttention Prefix Caching: Radix Trees vs PagedAttention, https://rajatpandit.com/ai-engineering/radixattention-vs-pagedattention/
  70. LLM Serving Part 1: Batching, PagedAttention, RadixAttention, https://www.cs.cmu.edu/~zhihaoj2/15-779/slides/15-LLM-serving-part1.pdf
  71. vLLM vs SGLang 2026: RadixAttention vs PagedAttention Benchmarks, https://www.spheron.network/blog/vllm-vs-sglang-2026/
  72. SGLang vs vLLM: Benchmarks and Use Cases - Atomic Chat, https://atomic.chat/blog/llm-updates/sglang-vs-vllm
  73. Rolling KV Cache - Awesome-Sliding-Window-Attention - GitHub, https://github.com/ishandutta2007/Awesome-Sliding-Window-Attention/blob/main/details/rolling-kv-cache.md
  74. Mistral 7B - Ryan Lee, https://www.ryanlee.ai/posts/mistral-7b/
  75. Why Stacking Sliding Windows Can't See Very Far - MIT HAN Lab, https://hanlab.mit.edu/blog/stacking-swa
  76. Mastering Mistral AI: From Sliding Window Attention to Efficient, https://medium.com/@sayedebad.777/mastering-mistral-ai-from-sliding-window-attention-to-efficient-inference-22d944384788
  77. Retention and Transmission of Information in Sliding-Window KV, https://arxiv.org/html/2609.34049v1
  78. Daily Papers - Hugging Face, https://huggingface.co/papers?q=video%20KV%20cache
  79. Efficient Streaming Language Models with Attention Sinks - arXiv, https://arxiv.org/html/2309.17453v3
  80. EAGLE-2: Faster Inference of Language Models with Dynamic Draft, https://aclanthology.org/anthology-files/pdf/emnlp/2024.emnlp-main.422.pdf
  81. An Introduction to Speculative Decoding for Reducing Latency in AI, https://developer.nvidia.com/blog/an-introduction-to-speculative-decoding-for-reducing-latency-in-ai-inference/
  82. What is EAGLE? Feature-Level Speculative Decoding Explained, https://outcomeschool.com/blog/decoding-eagle
  83. Speculative Decoding in vLLM: Complete Guide to Faster LLM, https://jarvislabs.ai/blog/speculative-decoding-vllm-faster-llm-inference
  84. DEAGLE: Token Tree with Dynamic Depth Will Further Benefit the, https://openreview.net/forum?id=eZRPb52ccA
  85. [Feature] EAGLE tree verify without per-node state snapshots for, https://github.com/sgl-project/sglang/issues/50497
  86. Structured Output and Guided Decoding in vLLM - Ashish Srivastava, https://ashishsrivastav.com/blog/structured-output-guided-decoding-vllm
  87. structured outputs, https://aarnphm.xyz/thoughts/structured-outputs
  88. Guided Decoding and Its Critical Role in Retrieval-Augmented, https://huggingface.co/blog/nmmursit/guided-decoding
  89. GRID: Grammar-Railed Decoding for Enterprise SQL Generation, https://arxiv.org/html/2607.11951
  90. Structured Decoding in vLLM: A Gentle Introduction - BentoML, https://www.bentoml.com/blog/structured-decoding-in-vllm-a-gentle-introduction
  91. General questions on structured output backend - vLLM Forums, https://discuss.vllm.ai/t/general-questions-on-structured-output-backend/1444
  92. Trie Automata for Constrained Decoding over Large Finite Sets - arXiv, https://arxiv.org/pdf/2608.12574
  93. Vector Search Indexes: HNSW, IVF and PQ Explained - BYD Tech, https://bydtech.in/blog/vector-search-ann-indexes
  94. Approximate Nearest Neighbor Search Algorithms Explained, https://mixpeek.com/guides/approximate-nearest-neighbor-algorithms
  95. HNSW Explained: The Algorithm Powering Fast Vector Search, https://tullie.ai/blog/hnsw-explained-the-algorithm-powering-fast-vector-search
  96. HNSW vs. DiskANN - Tiger Data, https://www.tigerdata.com/learn/hnsw-vs-diskann
  97. ANN Algorithm Selection Under Production Constraints - Medium, https://medium.com/@parasuram19/ann-algorithm-selection-under-production-constraints-7de48092e699
  98. Approximate Nearest Neighbor Search: IVF, HNSW, and DiskANN, https://khoury.northeastern.edu/home/pandey/courses/cs7800/spring26/notes/IVF-HNSW.pdf
  99. Approximate Nearest Neighbor (ANN) Search Explained: IVF vs, https://www.pingcap.com/article/approximate-nearest-neighbor-ann-search-explained-ivf-vs-hnsw-vs-pq/
  100. Vector Database Indexing: HNSW, IVF, PQ, OPQ, and ScaNN, https://chistadata.com/vector-database-indexing-hnsw-ivf-pq-opq-scann/
  101. RuVector SOTA Benchmark Results — June 2026 - GitHub Gist, https://gist.github.com/ruvnet/2f42030a9632888eff0fa95149a135f6
  102. HNSW vs IVF-PQ vs LSH: Approximate Nearest Neighbor, https://www.abhik.ai/concepts/embeddings/ann-comparison
  103. VIBE: Vector Index Benchmark for Embeddings - arXiv, https://arxiv.org/html/2505.17810v2
  104. LanceDB's RaBitQ Quantization for Blazing Fast Vector Search, https://www.lancedb.com/blog/feature-rabitq-quantization
  105. Vector Quantization: Beyond the TurboQuant-RaBitQ Debate - Milvus, https://milvus.io/blog/turboquant-rabitq-vector-database-cost.md
  106. RaBitQ Library - Vector Database Group @ NTU, https://vectordb-ntu.github.io/RaBitQ-Library/
  107. Filtered Vector Search: What ACORN Fixes, and What Fixes ACORN, https://qdrant.tech/articles/filtered-vector-search-acorn/
  108. Filtered HNSW & kNN search in Lucene and Elasticsearch, https://www.elastic.co/search-labs/blog/filtered-hnsw-knn-search
  109. ACORN and Adaptive Filtered Traversal in Vector Search, https://theaidatabaseblog.com/learn/acorn-and-adaptive-filtered-traversal/
  110. hnsw_acorn – DuckDB Community Extensions, https://duckdb.org/community_extensions/extensions/hnsw_acorn
  111. The RaBitQ Library - OpenReview, https://openreview.net/pdf?id=OeZHhOsFir
  112. RaBitQ: 1-Bit Vector Quantization (Part 3) | by Dnotitia Inc. | Medium, https://medium.com/@dnotitia/rabitq-1-bit-vector-quantization-part-3-92bbc1dbe8eb
  113. 8. The caching allocator — ML Software & Compilers, https://www.srikanthmalla.com/blog/ml-software/08-caching-allocator/
  114. A Tour of XLA: The Compiler Beneath JAX, TensorFlow, and PyTorch, https://hiraditya.github.io/posts/a-tour-of-xla-where-mlir-lives/
  115. XLA Terminology | OpenXLA Project, https://openxla.org/xla/terminology
  116. A Standalone HLO MLIR-based Compiler - Android GoogleSource, https://android.googlesource.com/platform/external/tensorflow/+/6b511124eb0/tensorflow/compiler/mlir/hlo/README.md
  117. MLIR bytecode, StableHLO, TOSA and XLA HLO graph ... - GitHub, https://github.com/morluto/rea/issues/3673
  118. xla/xla/service/heap_simulator/heap_simulator.h at main · openxla/xla, https://github.com/openxla/xla/blob/main/xla/service/heap_simulator/heap_simulator.h
  119. A guide to PyTorch's CUDA Caching Allocator | Zach's Blog, https://zdevito.github.io/2022/08/04/cuda-caching-allocator.html
  120. Unleashing PyTorch Performance with TorchInductor: A Deep Dive, https://blog.gopenai.com/unleashing-pytorch-performance-with-torchinductor-a-deep-dive-1f01e8b36efa
  121. Memory Planning — ExecuTorch 1.5 documentation, https://docs.pytorch.org/executorch/stable/compiler-memory-planning.html
  122. 1Introduction - arXiv, https://arxiv.org/html/2509.16248v2
  123. memory planning reuses a buffer whose view is a live graph output, https://github.com/pytorch/pytorch/issues/204917
  124. Automatic differentiation in PyTorch - OpenReview, https://openreview.net/pdf?id=BJJsrmfCZ
  125. Activation Checkpointing: Gradient Memory - Michael Brenndoerfer, https://mbrenndoerfer.com/writing/activation-checkpointing-gradient-memory-selective-recomputation
  126. Min-cut optimal(*) recomputation (i.e. activation checkpointing) with, https://dev-discuss.pytorch.org/t/min-cut-optimal-recomputation-i-e-activation-checkpointing-with-aotautograd/467
  127. transcending runtime-memory tradeoffs in checkpointing by, https://proceedings.mlsys.org/paper_files/paper/2023/file/8a27bb69950c0b46cdb36d10e5514cc8-Paper-mlsys2023.pdf
  128. Memory-Efficient Activation Checkpointing with Sliding Window and, https://arxiv.org/pdf/2608.08740
  129. torch.distributed.tensor — PyTorch 2.15 documentation, https://docs.pytorch.org/docs/stable/distributed.tensor.html
  130. From NCCL to DTensor: The Anatomy of PyTorch Distributed, https://www.ryhuang.blog/blogs/from-nccl-to-dtensor/
  131. AI in Multiple GPUs: ZeRO & FSDP - Towards Data Science, https://towardsdatascience.com/ai-in-multiple-gpus-zero-fsdp/
  132. DeepSpeed/docs/_tutorials/zero.md at master - GitHub, https://github.com/microsoft/DeepSpeed/blob/master/docs/_tutorials/zero.md
  133. ZeRO — DeepSpeed 0.19.9 documentation, https://deepspeed.readthedocs.io/en/stable/zero3.html
  134. Everything about Distributed Training and Efficient Finetuning, https://sumanthrh.com/post/distributed-and-efficient-finetuning/
  135. ZeRO-Infinity: Breaking the GPU Memory Wall for Extreme Scale, https://arxiv.org/abs/2104.07857
  136. NCCL All-Reduce: Ring vs Tree | Scale Atlas - Factryze, https://factryze.ai/scale-atlas/collectives/nccl-allreduce-ring-vs-tree
  137. Sparse All-Reduce in PyTorch | Speechmatics, https://blog.speechmatics.com/Sparse-All-Reduce-Part-1
  138. Prioritized Experience Replay - arXiv, https://arxiv.org/html/1511.05952v4
  139. Prioritized Experience Replay Buffer - labml.ai, https://nn.labml.ai/rl/dqn/replay_buffer.html
  140. (PDF) Prioritized Experience Replay - ResearchGate, https://www.researchgate.net/publication/284219262_Prioritized_Experience_Replay
  141. Efficient Experience Replay with a Prioritized Replay Buffer in DQN, https://medium.com/@velsorange/efficient-experience-replay-with-a-prioritized-replay-buffer-in-dqn-e5455ecc1f67
  142. implement of prioritized experience replay - Damcy - GitHub, https://github.com/Damcy/prioritized-experience-replay
  143. 6 Advanced data structures 6.1 Fibonacci heap, https://www.cl.cam.ac.uk/teaching/1617/Algorithms/2017-djw-handout3.pdf
  144. Open List Implementations in A*, https://ojs.aaai.org/index.php/SOCS/article/download/43090/50650/47195
  145. Real world applications of Binary heaps and Fibonacci Heaps [closed], https://stackoverflow.com/questions/3767863/real-world-applications-of-binary-heaps-and-fibonacci-heaps
  146. Bucket queue - Wikipedia, https://en.wikipedia.org/wiki/Bucket_queue
  147. 1 Buckets - courses, https://courses.csail.mit.edu/6.854/05/Notes/n5-bucket.pdf
  148. Zobrist Hashing - DEV Community, https://dev.to/larswaechter/zobrist-hashing-72n
  149. Zobrist hashing - Wikipedia, https://en.wikipedia.org/wiki/Zobrist_hashing
  150. Combining Win Rate and Proof Size Estimation - University of Alberta, https://sites.ualberta.ca/~hayward/papers/ews.pdf
  151. Collisions in a Zobrist transposition table - Stack Overflow, https://stackoverflow.com/questions/62541946/collisions-in-a-zobrist-transposition-table
  152. Minimax Algorithm in Game Theory | Set 5 (Zobrist Hashing), https://www.geeksforgeeks.org/dsa/minimax-algorithm-in-game-theory-set-5-zobrist-hashing/
  153. Zobrist Hashing & BigInt Transposition Tables in JavaScript, https://javascriptbattle.com/guides/zobrist-hashing-transposition-tables-bigint-js/
  154. Abstract Zobrist Hashing: An Efficient Work Distribution Method for, https://metahack.org/aaai16-jinnai-fukunaga.pdf
  155. GitHub - Aenteas/MCTS: A fast C++ implementation of fully, https://github.com/Aenteas/MCTS