-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathgenerate_docs.py
More file actions
199 lines (143 loc) · 6.69 KB
/
Copy pathgenerate_docs.py
File metadata and controls
199 lines (143 loc) · 6.69 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
from pathlib import Path
ROOT = Path(__file__).parent
LICENSE = """\
MIT License
Copyright (c) 2025 Joao Felipe De Souza
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
"""
DESIGN = """\
# Design Document -- prefix-cache-real
## 1. Motivation
The prefix-cache-sim (project 2) simulated prefix caching with a RadixTree
and LFU/LRU eviction. This project measures the real GPU costs of prefix
reuse using actual PyTorch inference.
Note: the DynamicCache format in transformers 5.x does not support
direct KV reuse across forward passes. This project measures prefix savings
by comparing prefill(prefix+suffix) vs prefill(suffix_only), which captures
the same compute savings without requiring KV state transfer.
---
## 2. Experimental Versions
### v1: Basic measurements
- Prefill cost curve (seq 16-1024)
- Prefix savings computed analytically from curve
- Hit rate simulation with 8 prompts
- KV memory savings formula
### v2: Direct measurements + corrected hit rate
- Direct: full prefill vs suffix-only prefill
- RNG reset per alpha (fixes hit rate bug)
- Multi-turn growing context
- Batch sharing cost vs N requests
### v3: Stable measurements (final)
- 15 repeats, 10 warmup, median-based
- 32 system prompts for meaningful hit rate differentiation
- LFU eviction simulation
- Breakeven analysis: at what N does batch sharing win?
---
## 3. Key Results
### Speedup
prefix=512 suffix=128: 2.41x speedup (savings=8816us)
prefix=512 suffix=64: 2.08x speedup
prefix=256 suffix=64: 1.26x speedup
### Multi-turn (10 turns, 64 tokens each)
turn=4: 1.41x speedup, 3.5ms saved cumulative
turn=8: 1.59x speedup, 13.5ms saved cumulative
turn=10: 2.06x speedup, 25.9ms saved cumulative
### Hit rate (32 prompts, 200 requests, LFU eviction)
Zipf alpha=2.0 cache=4: 82% hit rate
Zipf alpha=1.0 cache=4: 39% hit rate
Zipf alpha=0.5 cache=4: 14% hit rate
### Batch sharing breakeven
prefix=128: breakeven at n=12 requests
prefix=256: breakeven at n=3 requests
prefix=512: breakeven at n=2 requests
---
## 4. Connections to Prior Projects
prefix-cache-sim Real speedup (2.41x) confirms simulation value
real-model-profiler Prefill cost curve validates timing model
kv-cache-profiler-real KV formula (36 KB/tok) used in memory savings
continuous-batching-profiler Prefix sharing amortizes across N requests
"""
README = """\
# prefix-cache-real
**Measures real prefix cache costs on GPU across 3 experimental iterations:
prefill savings, multi-turn speedup, hit rate simulation, and batch sharing breakeven.**
Validates [prefix-cache-sim](https://github.com/JohnScheuer/prefix-cache-sim) (project 2).
> For design and methodology see [DESIGN.md](DESIGN.md).
---
## Key Findings
### 1. Prefix cache delivers up to 2.41x speedup (v3, stable)
prefix=512 suffix=128: 2.41x savings=8816us
prefix=512 suffix=64: 2.08x savings=6675us
prefix=256 suffix=64: 1.26x savings=1679us
Larger prefix fraction = higher speedup.
Speedup = cost(prefix+suffix) / cost(suffix_only).
### 2. Multi-turn speedup grows monotonically to 2.06x
turn=4 (256 tokens total): 1.41x speedup, 3.5ms cumulative saved
turn=8 (512 tokens total): 1.59x speedup, 13.5ms cumulative saved
turn=10 (640 tokens total): 2.06x speedup, 25.9ms cumulative saved
### 3. Hit rate: cache size and Zipf alpha jointly matter
32 system prompts, 200 requests, LFU eviction:
Zipf alpha=2.0 cache=4: 82% hit rate (concentrated access)
Zipf alpha=1.0 cache=4: 39% hit rate
Zipf alpha=0.5 cache=4: 14% hit rate (uniform access, cache too small)
With small cache (4 slots), Zipf alpha dominates.
With unlimited cache, hit rate converges to 84-91% for all alphas.
### 4. Batch sharing breakeven: longer prefix pays off sooner
prefix=128: breakeven at n=12 requests
prefix=256: breakeven at n=3 requests
prefix=512: breakeven at n=2 requests
For a single request, separate prefix+suffix prefill is always slower
than full prefill (CUDA kernel launch overhead for the prefix costs extra).
Prefix sharing only wins when N >= breakeven(prefix_len).
---
## Experimental Versions
profile_prefix_cache.py v1: basic measurements
profile_prefix_cache_v2.py v2: direct + corrected hit rate + breakeven
profile_prefix_cache_v3.py v3: stable (15 repeats, 10 warmup, median)
---
## Quick Start
python3 -m venv venv
source venv/bin/activate
pip install torch transformers
python3 profile_prefix_cache_v3.py # final version
---
## Results
results/prefill_curve.csv v1 cost curve
results/prefix_savings.csv v1 savings
results/direct_savings_v2.csv v2 direct measurements
results/multi_turn_v2.csv v2 multi-turn
results/hit_rate_v2.csv v2 hit rate
results/batch_sharing_v2.csv v2 batch sharing
results/savings_v3.csv v3 stable savings
results/multi_turn_v3.csv v3 stable multi-turn
results/hit_rate_v3.csv v3 hit rate (32 prompts + LFU)
results/breakeven_v3.csv v3 batch sharing breakeven
---
## Portfolio Context
Project 19 in a series on LLM inference infrastructure.
Validates prefix-cache-sim (project 2) with real GPU measurements.
Full series: https://github.com/JohnScheuer
"""
(ROOT / "LICENSE").write_text(LICENSE)
(ROOT / "DESIGN.md").write_text(DESIGN)
(ROOT / "README.md").write_text(README)
print("Wrote LICENSE, DESIGN.md, README.md")