Memory grows linearly, compute grows quadratically (but with small constant - until ~100k the inference will be still dominated by non-quadratic factors).
You can see dramatic improvements in latency and throughput if there is a large shared prefix of the queries.