Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper uses the recursive vector quantization ANN method, which can also be seen as a hierarchical VQ approach. The proposed method provides an optimization-based approach to fine-tune this ANN method. The analysis was made on million-scale and billion-scale ANN datasets. 
strength_and_weaknesses: Strengths:

1) The paper is novel and shows a performance improvement over baselines with negligible optimization cost.
2) The optimization cost is carefully designed. The method is based on maximizing the geometric mean recall for maximizing the ANN recall. It maximizes the arithmetic mean lower bound. To minimize the ANN search time, it minimizes memory accesses during the query phase. The overall constrained optimization maximizes the recall with the given search time constraints. 
3) The authors have shown the benchmark against the grid search and one black box search method- Vizier.

Questions and weaknesses:
1) Overhead of the parameter tuning: How does the parameter tuning time compare with the Black- box optimizers such as Vizier?
2) What is the rationale behind choosing the recall rate as the objective?:  The objective function is the recall rate, and the constraint is the search cost. Does the opposite, where the objective function is the search cost, and the constraint is the recall rate, results in a similar performance? 
3) Please correct me if I am wrong here: What query set is used for computing the objective function- $\mathcal{L}_i (t_i)$? As mentioned in 5.4, it looks like the query set is being used for optimization. However, this will not suit well for the real-time near-neighbor search, where the queries are unseen and seen one-by-one or batch-by-batch as a stream. The optimization cost should be negligible to achieve a real-time performance here.
4) With an assumption of an in-distribution query set (same distribution of index and query points), this can even use a fraction of index data to optimize the parameters.
5) Are there any other black box optimizers available for the ANN parameter tuning?
6) Section 5.4: The random split of the query set $Q_1$, and $Q_2$ is not the best way to see the out-of-sample performance. A better split where $Q_1$ and $Q_2$ are itself out of distribution to each other may be a better way to test the out-of-sample performance. Please clarify if I am missing something here.
clarity,_quality,_novelty_and_reproducibility: The paper is written well and clearly. The method is novel. No code is provided for reproducibility 
summary_of_the_review: The constraint optimization formulation is based on the search time and recall is intuitive, however, the applicability of the optimizer is questionable for the unseen query data.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: ANNS algorithms, especially those involving quantization, have many hyperparameters to tune. Careful tuning can yield significantly better accuracy and query throughput. However, tuning can be expensive, especially for large indices, if done naively (build the index and search). Therefore, the authors design a proxy loss metric to guide the hyperparameter search using a simple linear-scan based algo. This loss is an approximation of the metrics that matter in practice. Using this they show that on billion scale datasets, the tuning can outperform baselines by a margin and improve upon blackbox optimizers. Further, the authors entry won Track 1 of a recent NeurIPS challenge on large scale ANNS.
strength_and_weaknesses: Strengths:
1. Good empirical results -- improves significantly on baselines, outperforms blackbox tuning (e.g. Vizier) and on small scale datasets closely matches exhaustive tuning
2. Results demonstrated on multiple large scale datasets.


Weakness:
1. Not much discussion on applicability to tuning algorithms other than the linear scan in the paper. 
2. Its not clear that the techniques can be applied for interactive query processing.
clarity,_quality,_novelty_and_reproducibility: **Clarity** 
- What are the family of ANN algorithms that you are able to tune with your approach? linear scan? IVF? hashing? or just linear scans?
- If the answer to above question is linear scan, I suppose the algorithm does a full scan over the entire billion scale dataset in 16bytes precision? Is it possible to do so in an interactive mode (one query at a time), or must the entire dataset be batch processed to get reasonable query throughput? Scanning 16GB (1B points X 16byte PQ) for each query seems expensive!
- In Alg 1 and Section 3.4 and 4, you list S1/X1 as the largest set with lowest bitrate. However, In fig 6, you list X5  as the largest set with highest bitrate. As in X5 has all the elements and has the highest number of bytes in its representation. Is there a mistake in Fig 6? If not, the exposition in 3.4 and 5 seems to contradict what is presented in Fig 6.

**Quality**
- In section 5.4, why not use Yandex T2I dataset which has out-of-distribution queries?
- Can you comment on how well your techniques apply to graph algorithms and other algorithm on Track 2/3 of the NeurIPS competition.
- Can you list the total number of hyperparameter configurations that can be chosen from at billion scale to give the reader a sense of the size of this space.
- If Google Vizier is allowed to run for more than 6 hours, does it find the pareto-optimal configurations found by your algorithm? Could you also comment a bit more about where Vizier would fail and where it might succeed?
- Can one sample the dataset (1B->1M), run exhaustive tuning to find 4 levels of quantization and then train the 5th level while going back up to 1B? How much worse would this be compared to one-shot tuning using your proxy loss.

**Reproducibility**
-- Are the results on the training query set or the validation query set released in the competition?


summary_of_the_review: The results presented in the paper are a great improvement over baselines, however the paper could be stronger if it generalizes to interactive query processing or to other algorithms rather than the linear scan. It could be that the techniques are applicable, but couldn't ascertain this in my reading of this paper. I would rate the paper higher if this was the case.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper looks at the problem of hyperparameter tuning for the Approximate Nearest Neighbor (ANN) search. The authors propose a constrained optimization-based approach for tuning the quantization-based ANN methods. They only require a search cost or recall as input, then the Lagrange multipliers-based approach can provide a configuration such that the performance reaches the speed-recall pareto frontier. Extensive results confirm the superior performance of their proposed method. 

strength_and_weaknesses: The paper has the following strengths:

S1. The motivation is clear. As the dataset size increases significantly, tuning the parameters (manually or using traditional methods like grid search and black box optimizer) becomes computationally prohibitive. It is in significant demand to have a theoretically grounded yet computationally lightweight approach that can produce excellent performance.

S2. The proposed method is novel and easy to use. The input is simply the search cost or recall, which is friendly for fresh users unfamiliar with the ANN methods' details. The authors also provide sufficient insights and theoretical analysis when they introduce their idea.

S3. This paper is well written with clear clarity and thus is easy to read.

The paper has the following weaknesses:

W1. In the last paragraph of the introduction section, they claim their approach is very general and can be extended to distance measures, quantization algorithms, and search paradigms. It would be nice if they could simply illustrate how to extend such a claim, e.g. for different search paradigms.

W2. In Section 5.2, they claim they compare to heuristic, hand-tuned, and black-box optimizer settings. However, I cannot find such settings in Figure 2, and Figure 3 only depicts the comparison with a black-box optimizer Vizier. Moreover, the baselines that are shown in Figure 2 lack explanations. 

W3. In Section 5.3 and Figure 4, could you explain what $R^2$ is?
clarity,_quality,_novelty_and_reproducibility: Overall, based on the strength and weaknesses of this paper, the clarity and the quality seem good to me. 

Considering the proposed approach is computationally efficient and has a theoretical guarantee, it seems to me that this paper is novel. 

 
summary_of_the_review: In summary, I think the motivation is clear, the idea is sound, and the paper is written well enough. Thus, I tend to initially give acceptance to this paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper covers a new method for approximate nearest neighbour search aimed at very large datasets where hyper-parameter optimisation can be achieved efficiently.  The hyper-parameter optimisation uses some clever approximations that then allow very efficient optimisation.  The performance is measured empirically and shown to give better results than current methods.
strength_and_weaknesses: This is a well written paper.  The idea is elegant and sophisticated.  The empirical evaluation looks very convincing.

Although this is not my research field I see no obvious weaknesses.  Two very minor points that can be easily corrected.  The first is the Pareto should be capitalised as it refers to a proper name (Vilfredo Pareto).  Secondly, I might be wrong but I could not see a reference to Figure 2 in the text.  I think this should be referenced in Section 5.2.
clarity,_quality,_novelty_and_reproducibility: The paper is very clearly written despite its technical content.  It address a problem that I suspect is of considerable importance, namely approximate nearest neighbour detection.  This is not my field, but this seems to address an important problem of existing techniques is that it is hard to find appropriate hyper-parameters to make these methods work for different types of dataset.  The approach used seems novel.  The results seem reproducible.
summary_of_the_review: This is a well written paper with a nice idea that looks well motivated and technically sound.  The empirical results back up the claims (there is one approximation about independence that needs empirical justification).  In my view this is a good paper that deserves publication.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This work proposes a proxy loss metric to guide the hyperparameter for ANN search problems. The idea is nice, and the experiments have demonstrated the good performance of the proposed method. All the reviewers find the novel contribution of this paper, and are all positive to this paper. Thus, I recommend accept.
justification_for_why_not_higher_score: The paper shows the novelty on ANN search problems. But, reviewers find many issues that need to be fixed.
Decision: Accept: poster