PagedAttention: two requests share prefix blocks through a block table

PagedAttention: two requests share prefix blocks through a block table A workflow diagram generated by Archify. 01 / Request A: logical blocks (token order) 02 / Physical blocks in GPU memory, 16 tokens each 03 / Request B and sample branch B′: logical blocks A · block 0 · system prompt · Request A: logical blocks (token order) A · block 0 system prompt A · block 1 · system prompt · Request A: logical blocks (token order) A · block 1 system prompt A · block 2 · A's question · Request A: logical blocks (token order) A · block 2 A's question Physical block 7 · ref = 2, shared prefix · Physical blocks in GPU memory, 16 tokens each Physical block 7 ref = 2, shared prefix Physical block 1 · ref = 2, shared prefix · Physical blocks in GPU memory, 16 tokens each Physical block 1 ref = 2, shared prefix Physical block 3 · A only, 10/16 full · Physical blocks in GPU memory, 16 tokens each Physical block 3 A only, 10/16 full Physical block 5 · B's, B′ reads it too · Physical blocks in GPU memory, 16 tokens each Physical block 5 B's, B′ reads it too Physical block 8 · copy for B′ · Physical blocks in GPU memory, 16 tokens each Physical block 8 copy for B′ B · block 0 · system prompt · Request B and sample branch B′: logical blocks B · block 0 system prompt B · block 1 · system prompt · Request B and sample branch B′: logical blocks B · block 1 system prompt B · block 2 · B's question · Request B and sample branch B′: logical blocks B · block 2 B's question B′ · block 2 · second sample · Request B and sample branch B′: logical blocks B′ · block 2 second sample copy on write Legend logical block of a request private physical block shared physical block (prefix) new block from copy-on-write