perf(KV-OFFLOAD): ARC batch eviction restarts the LRU scan per candidate and is quadratic in the batch

Row: KV-OFFLOAD

Found by wave PORTQ-2 re-deriving PORT-NOW entry 70 of 5559679229..e126687a9a
(#2646). Upstream:
b92352ca2c vllm#50992, "[Perf][KV Offload] Avoid quadratic ARC batch eviction".

The pre-commit shape is here

ARCCachePolicy::evict (src/vllm/v1/kv_offload/cache_policy.cpp:257-286)
selects n candidates in a loop, and each round calls pick(), which restarts
the scan at the LRU end of T1 or T2 and skips an already_selected set
(:322-337):

  std::optional<CandidateInternal> pick(OrderedKeyMap<BlockStatus>& from, ...) {
    for (const OffloadKey& key : from.keys_in_order()) {
      ...
      if (protected_keys.count(key) != 0 || already_selected.count(key) != 0) {
        continue;
      }
      return CandidateInternal{key, *block, from_t1};
    }

That is O(n·|T1| + n·|T2|) for a batch of n evictions, which is what upstream
turns linear.

Scope

Replace pick()'s restart-from-LRU scan with one const_iterator per tier held
across the n rounds, and drop already_selected. keys_in_order() already
returns a const std::list<OffloadKey>& (cache_policy.cpp:88), so the
iterators are available, and the selection order is provably unchanged because
nothing mutates t1_/t2_ during selection — the apply loop runs afterwards.

The two contracts in include/vllm/v1/kv_offload/cache_policy.h:12-27 must
survive the change: ref_cnt == -1 is the not-ready sentinel, and evict is
ATOMIC — it must still mutate nothing and return "no result" when n evictions
cannot be satisfied.

Roughly 25-35 lines in one file, plus a batch-eviction order-equality test
(same selection, same order, before and after).

Honest weight

Nothing was measured here. The case for landing it is upstream's plus the
O(n·|T|) reading of the code, not a local profile. Whether ARC batch eviction is
hot in any configuration this tree runs is not established by this issue.

Nothing was executed for this finding: no build, no test, no GPU.

Start with ARCCachePolicy::evict and pick in src/vllm/v1/kv_offload/cache_policy.cpp:257-337, then review the contracts in include/vllm/v1/kv_offload/cache_policy.h:12-27. Add the batch-eviction order-equality test described in the issue. Done means selection order is unchanged, selection remains atomic when unsatisfied, and batch work no longer restarts the LRU scan for each candidate.