Repository: huggingface/transformers
Pull request: Fix cache update!

# What does this PR do?

As per the title. https://github.com/huggingface/transformers/pull/37873 broke the cache update when going beyond the sliding window, see my comment [here](https://github.com/huggingface/transformers/pull/37873#discussion_r2081837193).
This PR fixes it. 
This also incorporates the issue mentioned in https://github.com/huggingface/transformers/issues/37574! TLDR, the order of operations here is important as we check strict inequality!!
Correcteness can be verified with

```python
model_id = "google/gemma-2-9b-it"
device = 0


tokenizer = AutoTokenizer.from_pretrained(model_id)
tokenizer.pad_token = tokenizer.eos_token
model = AutoModelForCausalLM.from_pretrained(model_id, torch_dtype=torch.bfloat16, device_map=device)



chat1 = [  # This size + the new tokens is > than sliding window
  {"role": "user", "content": "This is a nice place. " * 675 + "\n\nForget about the previous text, and tell me who you are?"},
]
prompt1 = tokenizer.apply_chat_template(chat1, tokenize=False, add_generation_prompt=True)
chat2 = [
  {"role": "user", "content": "create a list of at least 10 colors please"},
]
prompt2 = tokenizer.apply_chat_template(chat2, tokenize=False, add_generation_prompt=True)

inputs = tokenizer([prompt1, prompt2], padding=True, return_tensors="pt").to(0 if device == "auto" else device)

print(f"Sliding window: {getattr(model.config, 'sliding_window', None)}")
print(f"Input size: {inputs.input_ids.shape}")
# print(inputs.keys())





cache = "hybrid"

compile_config = CompileConfig(fullgraph=False)
out = model.generate(**inputs, do_sample=False, max_new_tokens=100, cache_implementation=cache, compile_config=compile_config)

text = tokenizer.batch_decode(out[:, inputs.input_ids.shape[-1] :], skip_special_tokens=False)
print("\n\n")
for seq in text:
    print("NEW SEQ:")
    print(seq)
```

It use to generate correctly for both the sequence > sliding window and the padded sequence, and now generates very badly. This fixes it once and for all.


Changed files:
filename: src/transformers/cache_utils.py
patch: @@ -1402,7 +1402,7 @@ def update(
         value_states = value_states.to(v_out.dtype)
 
         # assume this only happens in prefill phase when prompt length > sliding_window_size (= max_cache_len)
-        if cache_position.shape[0] > self.max_cache_len:
+        if cache_position.shape[0] >= self.max_cache_len:
             k_out = key_states[:, :, -self.max_cache_len :, :]
             v_out = value_states[:, :, -self.max_cache_len :, :]
             # Assumption: caches are all zeros at this point, `+=` is equivalent to `=` but compile-friendly
@@ -1413,8 +1413,8 @@ def update(
             return key_states, value_states
 
         slicing = torch.ones(self.max_cache_len, dtype=torch.long, device=value_states.device).cumsum(0)
-        cache_position = cache_position.clamp(0, self.max_cache_len - 1)
         to_shift = cache_position > self.max_cache_len - 1
+        cache_position = cache_position.clamp(0, self.max_cache_len - 1)
         indices = (slicing + to_shift[-1].int() - 1) % self.max_cache_len
 
         k_out = k_out[:, :, indices]
@@ -1725,7 +1725,7 @@ def __init__(
             self.value_cache.append(new_layer_value_cache)
 
     def _sliding_update(self, cache_position, layer_idx, key_states, value_states, k_out, v_out, max_cache_len):
-        if cache_position.shape[0] > max_cache_len:
+        if cache_position.shape[0] >= max_cache_len:
             k_out = key_states[:, :, -max_cache_len:, :]
             v_out = value_states[:, :, -max_cache_len:, :]
             # Assumption: caches are all zeros at this point, `+=` is equivalent to `=` but compile-friendly
@@ -1736,8 +1736,8 @@ def _sliding_update(self, cache_position, layer_idx, key_states, value_states, k
             return key_states, value_states
 
         slicing = torch.ones(max_cache_len, dtype=torch.long, device=value_states.device).cumsum(0)
-        cache_position = cache_position.clamp(0, max_cache_len - 1)
         to_shift = cache_position > max_cache_len - 1
+        cache_position = cache_position.clamp(0, max_cache_len - 1)
         indices = (slicing + to_shift[-1].int() - 1) % max_cache_len
         k_out = k_out[:, :, indices]
         v_out = v_out[:, :, indices]