KV cache sebuah request autoregresif bertambah ketika token baru diproses, sementara panjang akhir sequence belum diketahui saat decoding dimulai. Reservasi satu area kontigu sebesar panjang maksimum mengikat memori pada kapasitas yang mungkin tidak pernah terpakai. PagedAttention mengubah batas alokasi tersebut: sequence direpresentasikan sebagai blok KV logis, lalu block table memetakan setiap blok logis ke blok fisik yang tidak harus bersebelahan di memori GPU.
Mekanisme ini mengubah penempatan dan alokasi cache. Persamaan attention tidak berubah, dan jumlah state KV per token yang dipertahankan tidak otomatis berkurang.
Urutan logis dipisahkan dari penempatan fisik
Sequence tetap memiliki riwayat token yang berurutan. PagedAttention mengelompokkan riwayat itu ke blok logis berukuran tetap. Setiap blok logis memiliki posisi dalam sequence, tetapi blok fisik yang menyimpannya dapat berada di lokasi mana pun dalam pool KV cache yang dikelola runtime.
Secara konseptual, pemetaannya berbentuk:
blok logis sequence: 0 1 2 3
| | | |
block table: 17 4 29 8
| | | |
blok KV fisik: [17] [04] [29] [08]Kernel attention memakai block table untuk menemukan key dan value milik sequence logis. Urutan token yang kontigu secara logis tidak lagi mensyaratkan satu alokasi fisik yang kontigu.
Indirection ini menjadi properti sistem utamanya. Runtime serving dapat mengalokasikan blok fisik baru ketika sequence melewati batas blok, bukan mencadangkan ruang sebesar kemungkinan panjang maksimum sejak request diterima.
Sisa alokasi dibatasi oleh granularitas blok
Blok berukuran tetap tidak menghapus internal fragmentation. Blok logis terakhir pada sequence aktif dapat hanya terisi sebagian. Perbedaannya, kapasitas yang belum terisi dibatasi oleh granularitas blok, bukan oleh reservasi besar untuk pertumbuhan sequence yang belum terjadi.
Blok yang lebih kecil dapat mengurangi slot kosong pada blok terakhir, tetapi ukuran blok memiliki tradeoff. Jumlah blok yang lebih banyak memperbesar metadata pemetaan dan menambah pekerjaan pengelolaan. Layout kernel, traffic metadata, perilaku allocator, serta karakteristik hardware ikut menentukan ukuran yang efektif.
Paper PagedAttention melaporkan pemborosan KV cache yang rendah pada desain vLLM yang dievaluasi. Angka tersebut merupakan hasil sistem dan workload yang diuji, bukan jaminan arsitektural untuk setiap runtime. Klaim mekanismenya lebih sempit: alokasi berbasis blok membuat kapasitas fisik dapat mengikuti pertumbuhan sequence aktual lebih dekat dibanding satu area maksimum yang dicadangkan di awal.
Kernel attention harus mengikuti block table
Kernel tensor biasa sering mengasumsikan K dan V sebuah sequence berada pada rentang alamat yang dapat diprediksi dan kontigu. PagedAttention tidak mempertahankan asumsi itu karena dua blok logis yang berurutan dapat menunjuk ke alamat fisik yang berjauhan.
Implementasi attention-nya memasukkan lookup block table ke jalur akses KV. Untuk sebuah query token, kernel menelusuri konteks logis dan menerjemahkan blok logis ke backing fisiknya sebelum memuat key dan value terkait.
Indirection tersebut memiliki biaya. PagedAttention bukan klaim bahwa memori tersebar selalu lebih cepat daripada memori kontigu. Manfaat sistem berasal dari utilisasi memori cache yang lebih baik dan kemungkinan menjalankan kumpulan request yang lebih besar atau lebih fleksibel. Dominasi manfaat itu terhadap overhead pemetaan dan kernel bergantung pada keseluruhan serving stack.
Sharing blok dapat menghindari duplikasi state KV
Indirection juga memungkinkan lebih dari satu sequence logis menunjuk ke blok KV fisik yang sama. Kondisi ini berguna ketika beberapa sequence memiliki prefix identik atau beberapa cabang decoding pada awalnya berbagi riwayat yang sama.
Blok dapat tetap dipakai bersama selama isinya tidak berubah. Saat sebuah cabang perlu memodifikasi data yang tidak lagi boleh dibagi, runtime dapat memakai semantik copy-on-write dan memberikan storage fisik terpisah kepada cabang tersebut.
Properti ini berkaitan dengan identitas storage, bukan attention aproksimatif. Blok yang dibagi harus berisi state KV yang valid bagi setiap sequence yang merujuknya. Dua sequence tidak dapat berbagi byte fisik secara benar hanya karena teks token tampak serupa jika state KV pada posisi tersebut tidak dapat digunakan kembali secara semantik.
Transformasi yang bergantung pada posisi dan state eksekusi model tetap menjadi bagian dari batas validitas cache.
Paging tidak mengompresi KV cache secara matematis
Pada model full-attention konvensional, token yang dipertahankan tetap membutuhkan state key dan value sesuai arsitektur model pada layer yang melakukan caching. PagedAttention mengubah allocator dan translasi alamat untuk menyimpan state tersebut. Mekanisme ini sendiri tidak melakukan pruning token, kuantisasi K atau V, pengurangan dimensi head, atau penggantian full attention dengan sparse attention.
Batas ini membedakan paging dari kompresi KV cache. Metode kompresi dapat mengurangi jumlah atau presisi state yang disimpan dan membawa batas akurasi atau kernel yang berbeda. Alokasi berbasis page dapat dipadukan dengan metode tersebut, tetapi keduanya membuat klaim teknis yang berbeda.
Hal serupa berlaku pada batas konteks. Penempatan memori yang efisien dapat membuat sebuah anggaran memori menampung lebih banyak blok cache aktif, tetapi tidak mengubah semantik konteks yang dikonfigurasi pada model.
Dampak serving bergantung pada tekanan memori
Memori KV cache dapat membatasi jumlah request yang aktif bersamaan saat inferensi. Dalam kondisi tersebut, pengurangan kapasitas reservasi yang tidak terpakai dapat membuka ruang untuk batch aktif yang lebih besar atau memberi ruang tambahan bagi sequence untuk tumbuh. Evaluasi awal vLLM melaporkan peningkatan throughput terhadap sistem pembandingnya, terutama pada workload dengan sequence lebih panjang dan pola decoding yang lebih kompleks.
Hasil pengukuran itu bukan jaminan performa universal. Kebijakan scheduler, bentuk model, presisi KV, ukuran blok, arsitektur GPU, kernel attention, distribusi panjang request, reuse prefix, dan target latency dapat mengubah hasil aktual.
Batas teknis PagedAttention lebih spesifik: kontinuitas sequence logis tidak lagi membutuhkan kontinuitas fisik KV cache. Block table mempertahankan tampilan logis, sementara allocator menempatkan blok fisik berdasarkan memori yang tersedia. Pemisahan tersebut memungkinkan pertumbuhan sequence dan sharing cache tanpa satu reservasi kontigu sebesar panjang maksimum.