A few things to consider:
* Make sure that the search is always using an index.
* Cover the search functionality in your performance tests (and please use a wider variety of search terms; I had a case where all tests just searched for a single term and therefor just tested some custom caching layer instead of the search itself ...)
* Even if you have the best search implementation and you return search results within 100ms, each one of these requests cannot be cached, and they will hit consistently the publish instances. This is an angle to bring down the publish systems which you cannot avoid in your design. Think about rate limiting the access to search functionality.