Cache middleware: design discussion for similarity_threshold floor and max_entries bound

[ColinM-sys]

Opening this to track the design discussion for #1879 per @dagardner-nv's request.

1. Should similarity_threshold enforce a minimum floor or just document the consequences of lower values? A lower threshold increases the risk of cache poisoning since crafted inputs can collide with legitimate cached keys, but a hard minimum may not be appropriate for a core library where operators know their own use case.

2. Should max_entries be configurable through CacheMiddlewareConfig and passed through the registration layer, or left as a constructor-only concern?

Happy to revise the PR once the discussion settles on a direction.

[dagardner-nv]

#1 Retain the minimum of 0, and document the potential cost of a low threashold. The main reason is that the difflib checks come at a cost, and setting this to a value of 0 is needed for only caching exact matches which bypasses difflib entirely.

#2 max_entries should be an attribute of CacheMiddlewareConfig with the range of acceptable values enforced by Pydantic and not by the constructor, this is the overall approach in NAT.

---

If you're taking a pass at this part of the code, I think there is an additional improvement to be made in the _find_similar_key method. Currently it calls difflib.SequenceMatcher.ratio() inside of a loop over all existing entries in _cache.
According to the docs for difflib this call might be quite costly:

Timing: The basic Ratcliff-Obershelp algorithm is cubic time in the worst case and quadratic time in the expected case. SequenceMatcher is quadratic time for the worst case and has expected-case behavior dependent in a complicated way on how many elements the sequences have in common; best case time is linear.

My concern is if the cache is large, and we are running this over every key in the cache, I'm thinking there might be a performance benefit to instead of:

        for cached_key in self._cache:
            # Use SequenceMatcher for similarity computation
            matcher = difflib.SequenceMatcher(None, input_str, cached_key)
            ratio = matcher.ratio()

            if ratio >= self._similarity_threshold and ratio > best_ratio:
                best_ratio = ratio
                best_match = cached_key

doing:

best_matches = difflib.get_close_matches(input_str, self._cache.keys(), n=1, cutoff=self._similarity_threshold)
if len(best_matches): # will be either 0 or 1
    best_match = best_matches[0]

I suspect algorithmically they are equivalent, but this might be a little more efficient or at least less lines of code.

[ColinM-sys]

Thanks for the context on the threshold floor, makes sense that 0 is a valid value for exact match only caching. Will update the PR and push the changes shortly.

[ColinM-sys]

Changes pushed to #1879 — dropped the floor to 0 with Pydantic enforcing bounds at the config layer, replaced the SequenceMatcher loop with get_close_matches, and updated the description to document the performance cost and collision risk of lower values.