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
- 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.2c: FlashAttention — IO Analysis and Evolution - Hugging Face, https://huggingface.co/blog/atharv6f/flash-attention-io-analysis
- FlashAttention: Fast and Memory-Efficient Exact Attention with IO, https://3dvar.com/Dao2022FlashAttention.pdf
- Chapter 3 Introduction to GPU - GitHub, https://github.com/datawhalechina/zero-to-sglang/blob/main/course-material/eng/part1/Chapter3_Introduction_to_GPU.md
- GPU MODE Lecture 11: Sparsity - Christian Mills, https://christianjmills.com/posts/cuda-mode-notes/lecture-011/
- Radix vs. PagedAttention Scaling (SGLang / vLLM) · Issue #37730, https://github.com/vllm-project/vllm/issues/37730
- A Performance Study of Priority Queues: Binary Heap, Fibonacci, https://lup.lub.lu.se/student-papers/record/9201073/file/9201074.pdf
- Performance Effects of heap structure - Outer Loop Consulting, https://www.outerloop.io/docs/OuterloopWhitePaper-PerformanceEffectsOfHeapStructure.pdf
- Nvidia Modelopt structured 2:4 weight sparsity showing no ... - GitHub, https://github.com/NVIDIA/Model-Optimizer/issues/1974
- 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
- What Is Warp Divergence? The Hidden GPU Throughput Killer, https://www.spheron.network/blog/what-is-warp-divergence-the-hidden-gpu-throughput-killer/
- NCHW vs NHWC · Issue #13179 - GitHub, https://github.com/ultralytics/ultralytics/issues/13179
- Understand Tensor Data Layout - Wentao's Blog, https://wentao.site/tensor_data_layout/
- NHWC vs NCHW convolution - cuDNN - NVIDIA Developer Forums, https://forums.developer.nvidia.com/t/nhwc-vs-nchw-convolution/111065
- 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
- [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
- TensorRT NCHW vs cuDNN NHWC - NVIDIA Developer Forums, https://forums.developer.nvidia.com/t/tensorrt-nchw-vs-cudnn-nhwc/177492
- FlashAttention-3 & GPU Kernel Interview Guide (2026), https://www.techinterview.net/blog/flashattention-3-triton-guide
- FlashAttention-3:Fast and Accurate Attention with Asynchrony ... - arXiv, https://arxiv.org/html/2407.08608v1
- FlashAttention-3: Fast and Accurate Attention with Asynchrony and, https://pytorch.org/blog/flashattention-3/
- 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
- FlashAttention-3: Fast and Accurate Attention with Asynchrony and, https://openreview.net/forum?id=tVConYid20
- 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/
- 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
- Flash Attention from Scratch Part 4: Bank Conflicts & Swizzling, https://lubits.ch/flash/Part-4
- KernelWiki/wiki/techniques/swizzling.md at master - GitHub, https://github.com/mit-han-lab/KernelWiki/blob/master/wiki/techniques/swizzling.md
- CuTe Swizzle - Lei Mao's Log Book, https://leimao.github.io/blog/CuTe-Swizzle/
- Bank Conflict Issue in CUDA Shared Memory Access - Stack Overflow, https://stackoverflow.com/questions/78235550/bank-conflict-issue-in-cuda-shared-memory-access
- 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
- High-Performance Sparse Linear Algebra on NVIDIA GPUs with, https://graphblas.org/GraphBLAS-Pointers/Slides/SIAMCSE21-Nvidia-cuSPARSE.pdf
- GE-SpMM: General-Purpose Sparse Matrix-Matrix Multiplication on, https://nicsefc.ee.tsinghua.edu.cn/%2Fnics_file%2Fpdf%2Fpublications%2F2020%2FSC20_320.pdf
- 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
- cusparseSpMM fp32 is slower than cublas cublasSgemm, https://forums.developer.nvidia.com/t/cusparsespmm-fp32-is-slower-than-cublas-cublassgemm/249112
- Efficient Sparse-Dense Matrix-Matrix Multiplication on GPUs Using, https://arxiv.org/pdf/2005.14469
- 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
- Graph Traversal on Tensor Cores: A BFS Framework for Modern GPUs, https://arxiv.org/html/2606.05081
- High Performance Unstructured SpMM Computation Using Tensor, https://arxiv.org/html/2408.11551v1
- Divergence-Aware Warp Scheduling - Purdue Engineering, https://engineering.purdue.edu/tgrogers/publication/rogers-micro-2013/rogers-micro-2013.pdf
- Warp-Consolidation: A Novel Execution Model for GPUs, https://www.ssslab.cn/assets/papers/2018-li-warpconsolidation.pdf
- 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/
- SpenseGPT: Practical One-shot Pruning Enabling Sparse ... - arXiv, https://arxiv.org/html/2606.10445v1
- SlideSparse: Fast and Flexible (2N-2):2N Structured Sparsity - arXiv, https://arxiv.org/html/2603.05232v1
- Exploiting NVIDIA Ampere Structured Sparsity with cuSPARSELt, https://developer.nvidia.com/blog/exploiting-ampere-structured-sparsity-with-cusparselt/
- SlideSparse: Fast and Flexible (2N-2):2N Structured Sparsity, https://openreview.net/pdf?id=GQ17DjsBcq
- LLM quantization: from FP32 down to INT4 - NEU, https://fit.neu.edu.vn/en/post/llm-quantization-from-fp32-down-to-int4
- QLORA: Efficient Finetuning of Quantized LLMs - arXiv, https://arxiv.org/pdf/2305.14314
- 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
- What Breaks Below 4-Bit? NF4 and QLoRA Explained ML Engineer, https://www.youtube.com/watch?v=BIjo8GKOiqA
- AutoAWQ+Marlin: Efficient INT4 Inference - Emergent Mind, https://www.emergentmind.com/topics/autoawq-marlin
- MARLIN: Mixed-Precision Auto-Regressive Parallel Inference ... - arXiv, https://arxiv.org/pdf/2408.11743
- MARLIN: Mixed-Precision Auto-Regressive Parallel Inference ... - arXiv, https://arxiv.org/html/2408.11743v1
- BitDecoding: Unlocking Tensor Cores for Long-Context LLMs ... - arXiv, https://arxiv.org/html/2503.18773v1
- GitHub - IST-DASLab/marlin: FP16xINT4 LLM inference kernel that, https://github.com/IST-DASLab/marlin
- [Tracking] Replace Marlin with Humming across NVIDIA architectures, https://github.com/vllm-project/vllm/issues/65560
- MXFP4: microscaling 4-bit float with shared 8-bit scale - ZeroEntropy, https://zeroentropy.dev/concepts/mxfp4/
- MXFP4 Quantization on GPU Cloud: Deploy LLMs at 4-Bit Precision, https://www.spheron.network/blog/mxfp4-microscaling-quantization-gpu-cloud/
- Choosing the right compression scheme - LLM Compressor Docs, https://docs.vllm.ai/projects/llm-compressor/en/latest/steps/choosing-scheme/
- What's MXFP4? The 4-Bit Secret Powering OpenAI's GPT‑OSS, https://huggingface.co/blog/RakshitAralimatti/learn-ai-with-me
- 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
- vLLM and PagedAttention: high-throughput serving for large, https://fit.neu.edu.vn/en/post/vllm-and-pagedattention-high-throughput-llm-serving-en
- vLLM: Easy, Fast, and Cheap LLM Serving with PagedAttention, https://vllm.ai/blog/2023-06-20-vllm
- 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
- How PagedAttention resolves memory waste of LLM systems, https://developers.redhat.com/articles/2025/07/24/how-pagedattention-resolves-memory-waste-llm-systems
- PagedAttention & vLLM for Efficient LLM Inference, https://llmsystem.github.io/llmsystem2025spring/assets/files/llmsys-22-vLLM_woosuk_kwon-1f34697dbb1a1fb5b798daf6eff14b67.pdf
- Paged Attention - vLLM docs, https://docs.vllm.ai/en/stable/design/paged_attention/
- PagedAttention Explained: The 1960s OS Trick Behind vLLM's Speed, https://www.youtube.com/watch?v=vtykPhnvQ74
- SGLang vs vLLM (2026): Which Is Best for Your Workload?, https://tensormesh.ai/learn/vllm-vs-sglang/
- vLLM vs SGLang: PagedAttention vs RadixAttention in 2026, https://www.praveentechworld.com/blog/vllm-pagedattention-vs-sglang-radixattention-benchmarks
- RadixAttention Prefix Caching: Radix Trees vs PagedAttention, https://rajatpandit.com/ai-engineering/radixattention-vs-pagedattention/
- LLM Serving Part 1: Batching, PagedAttention, RadixAttention, https://www.cs.cmu.edu/~zhihaoj2/15-779/slides/15-LLM-serving-part1.pdf
- vLLM vs SGLang 2026: RadixAttention vs PagedAttention Benchmarks, https://www.spheron.network/blog/vllm-vs-sglang-2026/
- SGLang vs vLLM: Benchmarks and Use Cases - Atomic Chat, https://atomic.chat/blog/llm-updates/sglang-vs-vllm
- Rolling KV Cache - Awesome-Sliding-Window-Attention - GitHub, https://github.com/ishandutta2007/Awesome-Sliding-Window-Attention/blob/main/details/rolling-kv-cache.md
- Mistral 7B - Ryan Lee, https://www.ryanlee.ai/posts/mistral-7b/
- Why Stacking Sliding Windows Can't See Very Far - MIT HAN Lab, https://hanlab.mit.edu/blog/stacking-swa
- 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
- Retention and Transmission of Information in Sliding-Window KV, https://arxiv.org/html/2609.34049v1
- Daily Papers - Hugging Face, https://huggingface.co/papers?q=video%20KV%20cache
- Efficient Streaming Language Models with Attention Sinks - arXiv, https://arxiv.org/html/2309.17453v3
- EAGLE-2: Faster Inference of Language Models with Dynamic Draft, https://aclanthology.org/anthology-files/pdf/emnlp/2024.emnlp-main.422.pdf
- 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/
- What is EAGLE? Feature-Level Speculative Decoding Explained, https://outcomeschool.com/blog/decoding-eagle
- Speculative Decoding in vLLM: Complete Guide to Faster LLM, https://jarvislabs.ai/blog/speculative-decoding-vllm-faster-llm-inference
- DEAGLE: Token Tree with Dynamic Depth Will Further Benefit the, https://openreview.net/forum?id=eZRPb52ccA
- [Feature] EAGLE tree verify without per-node state snapshots for, https://github.com/sgl-project/sglang/issues/50497
- Structured Output and Guided Decoding in vLLM - Ashish Srivastava, https://ashishsrivastav.com/blog/structured-output-guided-decoding-vllm
- structured outputs, https://aarnphm.xyz/thoughts/structured-outputs
- Guided Decoding and Its Critical Role in Retrieval-Augmented, https://huggingface.co/blog/nmmursit/guided-decoding
- GRID: Grammar-Railed Decoding for Enterprise SQL Generation, https://arxiv.org/html/2607.11951
- Structured Decoding in vLLM: A Gentle Introduction - BentoML, https://www.bentoml.com/blog/structured-decoding-in-vllm-a-gentle-introduction
- General questions on structured output backend - vLLM Forums, https://discuss.vllm.ai/t/general-questions-on-structured-output-backend/1444
- Trie Automata for Constrained Decoding over Large Finite Sets - arXiv, https://arxiv.org/pdf/2608.12574
- Vector Search Indexes: HNSW, IVF and PQ Explained - BYD Tech, https://bydtech.in/blog/vector-search-ann-indexes
- Approximate Nearest Neighbor Search Algorithms Explained, https://mixpeek.com/guides/approximate-nearest-neighbor-algorithms
- HNSW Explained: The Algorithm Powering Fast Vector Search, https://tullie.ai/blog/hnsw-explained-the-algorithm-powering-fast-vector-search
- HNSW vs. DiskANN - Tiger Data, https://www.tigerdata.com/learn/hnsw-vs-diskann
- ANN Algorithm Selection Under Production Constraints - Medium, https://medium.com/@parasuram19/ann-algorithm-selection-under-production-constraints-7de48092e699
- Approximate Nearest Neighbor Search: IVF, HNSW, and DiskANN, https://khoury.northeastern.edu/home/pandey/courses/cs7800/spring26/notes/IVF-HNSW.pdf
- Approximate Nearest Neighbor (ANN) Search Explained: IVF vs, https://www.pingcap.com/article/approximate-nearest-neighbor-ann-search-explained-ivf-vs-hnsw-vs-pq/
- Vector Database Indexing: HNSW, IVF, PQ, OPQ, and ScaNN, https://chistadata.com/vector-database-indexing-hnsw-ivf-pq-opq-scann/
- RuVector SOTA Benchmark Results — June 2026 - GitHub Gist, https://gist.github.com/ruvnet/2f42030a9632888eff0fa95149a135f6
- HNSW vs IVF-PQ vs LSH: Approximate Nearest Neighbor, https://www.abhik.ai/concepts/embeddings/ann-comparison
- VIBE: Vector Index Benchmark for Embeddings - arXiv, https://arxiv.org/html/2505.17810v2
- LanceDB's RaBitQ Quantization for Blazing Fast Vector Search, https://www.lancedb.com/blog/feature-rabitq-quantization
- Vector Quantization: Beyond the TurboQuant-RaBitQ Debate - Milvus, https://milvus.io/blog/turboquant-rabitq-vector-database-cost.md
- RaBitQ Library - Vector Database Group @ NTU, https://vectordb-ntu.github.io/RaBitQ-Library/
- Filtered Vector Search: What ACORN Fixes, and What Fixes ACORN, https://qdrant.tech/articles/filtered-vector-search-acorn/
- Filtered HNSW & kNN search in Lucene and Elasticsearch, https://www.elastic.co/search-labs/blog/filtered-hnsw-knn-search
- ACORN and Adaptive Filtered Traversal in Vector Search, https://theaidatabaseblog.com/learn/acorn-and-adaptive-filtered-traversal/
- hnsw_acorn – DuckDB Community Extensions, https://duckdb.org/community_extensions/extensions/hnsw_acorn
- The RaBitQ Library - OpenReview, https://openreview.net/pdf?id=OeZHhOsFir
- RaBitQ: 1-Bit Vector Quantization (Part 3) | by Dnotitia Inc. | Medium, https://medium.com/@dnotitia/rabitq-1-bit-vector-quantization-part-3-92bbc1dbe8eb
- 8. The caching allocator — ML Software & Compilers, https://www.srikanthmalla.com/blog/ml-software/08-caching-allocator/
- A Tour of XLA: The Compiler Beneath JAX, TensorFlow, and PyTorch, https://hiraditya.github.io/posts/a-tour-of-xla-where-mlir-lives/
- XLA Terminology | OpenXLA Project, https://openxla.org/xla/terminology
- A Standalone HLO MLIR-based Compiler - Android GoogleSource, https://android.googlesource.com/platform/external/tensorflow/+/6b511124eb0/tensorflow/compiler/mlir/hlo/README.md
- MLIR bytecode, StableHLO, TOSA and XLA HLO graph ... - GitHub, https://github.com/morluto/rea/issues/3673
- 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
- A guide to PyTorch's CUDA Caching Allocator | Zach's Blog, https://zdevito.github.io/2022/08/04/cuda-caching-allocator.html
- Unleashing PyTorch Performance with TorchInductor: A Deep Dive, https://blog.gopenai.com/unleashing-pytorch-performance-with-torchinductor-a-deep-dive-1f01e8b36efa
- Memory Planning — ExecuTorch 1.5 documentation, https://docs.pytorch.org/executorch/stable/compiler-memory-planning.html
- 1Introduction - arXiv, https://arxiv.org/html/2509.16248v2
- memory planning reuses a buffer whose view is a live graph output, https://github.com/pytorch/pytorch/issues/204917
- Automatic differentiation in PyTorch - OpenReview, https://openreview.net/pdf?id=BJJsrmfCZ
- Activation Checkpointing: Gradient Memory - Michael Brenndoerfer, https://mbrenndoerfer.com/writing/activation-checkpointing-gradient-memory-selective-recomputation
- 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
- transcending runtime-memory tradeoffs in checkpointing by, https://proceedings.mlsys.org/paper_files/paper/2023/file/8a27bb69950c0b46cdb36d10e5514cc8-Paper-mlsys2023.pdf
- Memory-Efficient Activation Checkpointing with Sliding Window and, https://arxiv.org/pdf/2608.08740
- torch.distributed.tensor — PyTorch 2.15 documentation, https://docs.pytorch.org/docs/stable/distributed.tensor.html
- From NCCL to DTensor: The Anatomy of PyTorch Distributed, https://www.ryhuang.blog/blogs/from-nccl-to-dtensor/
- AI in Multiple GPUs: ZeRO & FSDP - Towards Data Science, https://towardsdatascience.com/ai-in-multiple-gpus-zero-fsdp/
- DeepSpeed/docs/_tutorials/zero.md at master - GitHub, https://github.com/microsoft/DeepSpeed/blob/master/docs/_tutorials/zero.md
- ZeRO — DeepSpeed 0.19.9 documentation, https://deepspeed.readthedocs.io/en/stable/zero3.html
- Everything about Distributed Training and Efficient Finetuning, https://sumanthrh.com/post/distributed-and-efficient-finetuning/
- ZeRO-Infinity: Breaking the GPU Memory Wall for Extreme Scale, https://arxiv.org/abs/2104.07857
- NCCL All-Reduce: Ring vs Tree | Scale Atlas - Factryze, https://factryze.ai/scale-atlas/collectives/nccl-allreduce-ring-vs-tree
- Sparse All-Reduce in PyTorch | Speechmatics, https://blog.speechmatics.com/Sparse-All-Reduce-Part-1
- Prioritized Experience Replay - arXiv, https://arxiv.org/html/1511.05952v4
- Prioritized Experience Replay Buffer - labml.ai, https://nn.labml.ai/rl/dqn/replay_buffer.html
- (PDF) Prioritized Experience Replay - ResearchGate, https://www.researchgate.net/publication/284219262_Prioritized_Experience_Replay
- 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
- implement of prioritized experience replay - Damcy - GitHub, https://github.com/Damcy/prioritized-experience-replay
- 6 Advanced data structures 6.1 Fibonacci heap, https://www.cl.cam.ac.uk/teaching/1617/Algorithms/2017-djw-handout3.pdf
- Open List Implementations in A*, https://ojs.aaai.org/index.php/SOCS/article/download/43090/50650/47195
- Real world applications of Binary heaps and Fibonacci Heaps [closed], https://stackoverflow.com/questions/3767863/real-world-applications-of-binary-heaps-and-fibonacci-heaps
- Bucket queue - Wikipedia, https://en.wikipedia.org/wiki/Bucket_queue
- 1 Buckets - courses, https://courses.csail.mit.edu/6.854/05/Notes/n5-bucket.pdf
- Zobrist Hashing - DEV Community, https://dev.to/larswaechter/zobrist-hashing-72n
- Zobrist hashing - Wikipedia, https://en.wikipedia.org/wiki/Zobrist_hashing
- Combining Win Rate and Proof Size Estimation - University of Alberta, https://sites.ualberta.ca/~hayward/papers/ews.pdf
- Collisions in a Zobrist transposition table - Stack Overflow, https://stackoverflow.com/questions/62541946/collisions-in-a-zobrist-transposition-table
- Minimax Algorithm in Game Theory | Set 5 (Zobrist Hashing), https://www.geeksforgeeks.org/dsa/minimax-algorithm-in-game-theory-set-5-zobrist-hashing/
- Zobrist Hashing & BigInt Transposition Tables in JavaScript, https://javascriptbattle.com/guides/zobrist-hashing-transposition-tables-bigint-js/
- Abstract Zobrist Hashing: An Efficient Work Distribution Method for, https://metahack.org/aaai16-jinnai-fukunaga.pdf
- GitHub - Aenteas/MCTS: A fast C++ implementation of fully, https://github.com/Aenteas/MCTS
- 5 Proven Strategies to Conquer B1 Sentence Transformation
- Đa hình (polymorphism) trong C++
- Effective Strategies for Developing Natural English Pronunciation among University Students
- Kĩ năng tự học của sinh viên năm nhất
- TỔNG QUAN PHƯƠNG PHÁP LUẬN VÀ ỨNG DỤNG CỦA PHÂN TÍCH TRẮC LƯỢNG THƯ MỤC (BIBLIOMETRICS) TRONG NGHIÊN CỨU KHOA HỌC HIỆN ĐẠI

