- Rating
- 1
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
To ground the model in additional knowledge RAG based system uses nearest neighbour search (with respect to the embedded query vector) among the provided the top k data passages (embedded as vectors). These top k passages are used as context for the query vector. Much of the work for finding k-nearest neighbours is spent on unqualified candidates. The paper therefore proposes an efficient approach to find the top k- candidates. The idea is to measure distance in a lower-dimensional orthogonal bases of the data for the pruning of non-qualified candidates. PCA is applied to obtain the orthogonal bases of the query vector. The candidate vectors are rotated into this orthogonal bases, Distance is computed in this bases to prune some candidates more efficiently. There is some approximation done for more efficient pruning which is not very clear. Also the paper uses terms like "splitting coordinates", "using tail energies ", which it never defines.
Critical strengths
- The paper concerns an interesting problem.
- The approach generally seems to make sense
Critical weaknesses
- Terms are used without being defined which makes the paper hard to read. For instance , what is "tail energy"? What does "splitting coordinates" mean? What are "level-major" batches? What does "spreading energy" mean?
- I am not sure of how efficient this approach is? It changes the problem to distance computation in an orthogonal bases. The distance computation may become faster but what about the work done to obtain the data transforms. Also how is \ell chosen?
- While the paper conveys the key idea, it is difficult to follow. There are two major reasons for that. First, the paper uses vocabulary it never defines. Second the sentences are too long. For instance, a single sentence covers lines 219 till 223. There are many other such examples in the paper.
Questions for authors
Please see the weaknesses.
In addition, please explain how exactly your approach is more efficient than k-nearest neighbour search. You do get benefit if the distance computation is faster in teh new bases. But you still need to parse through all candidates and do some work for each.
4 comments
Q1 & Q2
(Part 2/3)
Q1. Terms are used without being defined ... what is "tail energy" ... "splitting coordinates" ... "level-major" batches ... "spreading energy"? ... the paper uses vocabulary it never defines.
We added a notation box to Section 3 and the full glossary below to Appendix I (Table 24).
Notation: is an orthogonal matrix (here PCA); a vector is always stored and compared after rotation, .
| Term in the paper | Definition |
|---|---|
| Energy of a block of coordinates | The squared norm of those coordinates, e.g. . |
| Tail energy | The energy of the coordinates not yet read: ; it is computed once per stored vector at build time. |
| Levels, splitting coordinates, cutpoints | We split the coordinates into consecutive blocks ("levels") at positions (the "cutpoints" or "splitting coordinates"). The bound is checked after each level, not after each coordinate. indexes the level. |
| Level-major batch | A memory layout. For a batch of vectors, we store level 1 of all vectors, then level 2 of all , and so on. One level is then one contiguous array, processed in one SIMD pass over the candidates that are still alive. |
| Spreading energy | The effect of a random rotation (as in RaBitQ), which makes coordinates carry similar energy, as opposed to PCA, which concentrates energy in the first coordinates. |
| Verification | Computing a candidate's exact distance to decide whether it enters the current top-. This is the step PANORAMA accelerates. |
| Candidate stream | The sequence of candidate vectors an index (IVF list, graph neighbors, PQ codes) hands to verification. |
| Running -th-best threshold | The distance of the current -th-best result; a candidate can enter the top- only if its distance is below . |
| Early abandoning / pruning | Stopping a candidate's distance computation as soon as a lower bound on its distance exceeds . |
| Sidecar | A small side array holding each vector's suffix energies ( floats), indexed by vector ID, used when the index keeps its own vector layout (graphs, reranking). |
| Spectral decay, | How fast the PCA eigenvalues fall. We model the normalized suffix energy as ; a larger means the bound becomes decisive earlier. |
| Shaping, | For PQ codes: limiting how unequal the per-level energies may be (cap ), so PQ's codebooks are not starved in later levels. |
| Sign-prefix gate, popcount | For RaBitQ codes (1 bit per coordinate): a cheap bound computed from the number of matching sign bits (popcount) in the prefix, applied before RaBitQ's own scorer. |
| Fixed-width specialization | Compiling a separate kernel for each level width so loop bounds are compile-time constants. |
| Underfilled candidate groups | In graph search, candidates arrive in small groups. When too few remain, we hand them to the standard exact kernel instead of running the batched one. |
| Frontier / matched recall | The throughput–recall curve of a method. "Matched recall" compares two methods' throughput at the same recall. |
Q2. Please explain how exactly your approach is more efficient than -nearest neighbour search ... you still need to parse through all candidates and do some work for each.
Yes, PANORAMA does some work for each candidate, yet reads only a fraction of most of them. The fraction of coordinates it reads over all candidates in strict mode is:
| Deep (96-d) | SIFT (128-d) | arXiv (768-d) | GIST (960-d) | Ada (1536-d) | Large (3072-d) |
|---|---|---|---|---|---|
| 32.9% | 17.1% | 10.7% | 6.5% | 13.3% | 9.0% |
For example, on Large, a candidate is read for about 275 of its 3072 coordinates on average. Faiss reads all 3072. Strict PANORAMA is 1.8–14.6× faster than Faiss's SIMD exact scan, depending on dataset and recall (IVF-Flat, matched recall 0.80–0.99). Table 2 in Section 5 reports the fraction of coordinates read at the paper's .
Q3, Q4, Q5
(Part 3/3)
Q3. What about the work done to obtain the data transforms?
We added these costs to Appendix F.2 (Tables 14 and 15) and Section 5, reproduced below. They are small and mostly one-off. Measured on Ada (1M vectors, 1536-d):
- Once, at build time: fitting PCA takes 4.7 s, and transforming the 1M database vectors takes 5.1 s. For comparison, Faiss's IVFPQ build takes 149 s.
- Per query: rotating a query costs 38 µs when queries arrive in batches, which is 0.3–0.8% of query time. Answering one query at a time, it is a single matrix–vector product (0.30 ms). All our time measurements include this cost.
- Memory: the transform matrix is 9.4 MB per index, plus floats (about 70 B) of suffix energies per vector. On Ada that is +6–9% over Faiss in total.
Other datasets (all measured): the database transform takes 1–16 s, and the PCA fit 2–3 s (31 s on the 3072-d Large), once per index. Batched query rotation is at most 1.5% of IVF query time on each dataset. Memory overhead is +8.6–12.4% for IVF-Flat and +6–10% for IVFPQ on the embedding datasets. These measurements are reported in Appendix F.2 (Table 14 for bytes, Table 15 for build and rotation time) and Section 5 (rotation cost).
Q4. How is chosen?
The chosen parameter is the number of levels (i.e., blocks of coordinates) , indexed by . A larger checks the bound more often, hence prunes earlier at the cost of bookkeeping. Throughput forms a broad plateau around the chosen value (Appendix D, Figure 10). We pick once per dataset from a small grid (Table 5, between 4 and 32). We conducted new sensitivity results on arXiv, GIST, Ada and Large (in strict mode, from 4 to 64), and found that the paper's is within 1.7% of the best on each dataset, while loses 40–59%. A simple rule of thumb, making levels of 64 coordinates () performs within 2.7% of the best. We added this sensitivity study in Appendix G.2 (Table 21) and referenced from the notation box in Section 3.
Q5. The sentences are too long. For instance, a single sentence covers lines 219 till 223.
We rewrote the sentence in Lines 219–223 in four sentences (Section 4, "Contiguous lists"):
IVF-Flat delivers candidates in long runs, one inverted list at a time. PANORAMA groups each list's vectors into batches stored in level-major order: the coordinates of all vectors for level 1 are stored contiguously, then those for level 2, and so on. Processing one level is therefore one vectorized pass over the candidates that are still alive. We keep the distance, bound-update and compaction steps in separate loops so that each of them vectorizes.
We applied the same treatment to the new and revised text (one claim per sentence, at most two clauses), defined each term at first use, and added a notation box in Section 3. We would be grateful if the reviewer would reconsider the overall assessment.
Response to Authors
Dear Authors,
Thanks for your response. I found your paper really hard to read though I like the problem that you are trying to solve. Talking about readability, the example about long sentences that I gave was just one example. The paper had many such instances. To check if the modifications indeed make it more understandable a full review may be needed. Therefore, for now I keep my score and wait for the discussion period to further update my score.
On review summary
(Part 1/3)
We thank the reviewer for the time invested to read the paper carefully. First, we provide answers to three implicit questions in the reviewer's summary and then to explicit questions:
PANORAMA does not use lower-dimensional bases. It keeps all d coordinates, reads them in decreasing order for each candidate, and stops when it determines that the candidate cannot be among the top-k set. The revised manuscript states this clarification in Section 3 ("The bound").
PCA is applied once and offline on the data, preserving distances due to orthogonality. At query time, the query is rotated into the data's orthogonal basis by one matrix–vector product. We stated this in Section 3 ("Learning the basis").
PANORAMA's strict mode involves no approximation. The Cauchy-Schwarz lower bound holds for each vector:
∥q−x∥2≥coordinates read so far∑j≤m(q~j−x~j)2+(Rq(m)−Rx(m))2,
PANORAMA in strict mode returns the same top-k set as fully computing each distance (Proposition 3.1). In relaxed mode, PANORAMA conducts an approximation via a parameter ε<1 that tightens the bound at the risk of incurring false negatives. We report the tradeoff via recall–throughput curves. We stated this in the introduction, Definition 3.1, and Proposition 3.1.