THE KV-CACHE ACCOUNTANT

Difficulty: Medium Tags: LLM Inference, KV Cache, Memory Accounting, Transformers

Story

An inference gateway must decide whether a request fits into its GPU memory budget. It stores keys and values for every layer and token. The estimate is wrong if it counts only keys, ignores batch size, or treats bytes as bits.

The Math

For batch size B, layers L, cached tokens T, attention heads H, head dimension D, and b bytes per scalar, the key-value cache uses:

M = 2 * B * L * T * H * D * b   bytes

The factor 2 accounts for keys and values. Given a memory budget G bytes, the largest integer token count that fits is:

T_max = floor(G / (2 * B * L * H * D * b))

The budget is entirely available for this cache; allocator overhead is ignored.

Input Format

B, L, H, D, b, G.

Output Format

(T_max, bytes_used) where bytes_used is the exact cache size at T_max.

Constraints

• 1 <= B, L, H, D <= 10^4, b in {1, 2, 4}, 1 <= G <= 10^18.
• Products may exceed 32-bit integer range.
• Time limit: 1.0 second. Memory limit: 64MB.

Example

Input

B = 2, L = 32, H = 8, D = 128, b = 2, G = 1000000000

Output

(3814, 999817216)

Explanation: Each token requires 2*2*32*8*128*2 = 262144 bytes. The maximum count is floor(10^9 / 262144) = 3814, using 999817216 bytes.