GRIP on Natural Questions

At the server defaults, recall at 10 is — on Granite and — on Splade. It is — on SlideOn and — on SparseUP. One search takes — ms inside the index on Splade. The model changes recall far more than any search setting does.

SlideOn and SparseUP are much denser than the other two. They average about 600 non-zero dimensions per vector, against about 150 for Splade and about 230 for Granite. The first pass of the search uses quantized sketches that keep only 80 dimensions, and the full vectors rescore the result afterwards. A denser vector loses the most when it is cut to 80 dimensions, so these two models lose the most.

One index for each of four sparse models, 10,000 queries from Natural Questions, and the exact top 10 from brute force as ground truth. Recall at 10 is the share of the exact top 10 that the index returns. All four indexes hold 1,990,000 documents.

Four models at the server defaults

The server defaults are ef 100 and max-query-dims 2. p5 is the recall that 5% of the queries fall below.

Recall for each setting

More query terms help more than a bigger ef. Going from 2 to 10 terms raises recall by more than going from ef 100 to 200 on Splade, Granite and SparseUP, and the search time is about the same. On SlideOn the two gains are about equal. Going to 20 terms and ef 200 gives the best recall everywhere.

max-query-dims is how many query terms pick starting points for the search. Each term adds up to 64 documents to start from. ef is the size of the result list while the search runs.

The weak tail

On Splade and Granite the middle query (p50) finds all 10 true neighbors. On SlideOn and SparseUP it gets a recall of —. One query in 20 on SparseUP gets a recall of — or less.

Model, server defaults Mean p5 p10 p25 p50 nDCG p5

Search time inside the index

Time grows with both settings. Twenty terms with ef 200 costs 1.3 to 1.8 times the default time, depending on the model. SlideOn is the slowest.

Milliseconds inside search, measured at one client. It does not include the network or the JSON handling.

Throughput by number of clients

Requests per second peak at 4 clients on all four models, then fall. The cause is not known yet. The server runs 4 workers by default, so check that first.

Requests per second 1 client4 clients8 clients16 clients

Every setting, one model at a time

Setting Recall Change p5 p50 nDCG MRR Search ms Time vs defaults Requests/s, 1 client p99 ms, 1 client

Index build time

SparseUP takes about ten times as long as Splade to build. SlideOn on 1,000,000 documents needed — seconds. On 1,990,000 documents it needed — seconds, with the code changes and the refine step. The two 1,990,000-document SlideOn rows use the faster settings (fanout 3 and 2, with refine). The other rows are the first builds, with fanout 10 and 3 and no refine step. The next section shows the faster ones.

Model Documents Read (s) Build (s) Save (s)

A bigger sketch for SlideOn and SparseUP

The first pass of the search uses sketches that keep 80 dimensions of each document. SlideOn and SparseUP have about 600 non-zero dimensions per vector, so 80 dimensions leave out much of each document. With --sketch-size 300, recall at 10 at the server defaults rose from — to — on SlideOn, and from — to — on SparseUP. The p5 recall went from — to — on SlideOn and from — to — on SparseUP.

It has a cost. SlideOn built in — seconds, against — with 80 dimensions. SparseUP built in — seconds, against —. That is about half a minute more on SlideOn and about a minute more on SparseUP. Nearly all of it is in the refine step: SlideOn took 147 s against 117 s, and SparseUP took 140 s against 85 s. Peak memory on SlideOn was 24.0 GiB, against 18.7 GiB. Search takes about a fifth longer on SlideOn (— ms against — ms) and about a third longer on SparseUP (— ms against — ms).

Model, setting Recall, sketch 80 Recall, sketch 300 Change p5, sketch 80 p5, sketch 300 Search ms, sketch 80 Search ms, sketch 300

All indexes have 1,990,000 documents. The sketch 80 SparseUP index is the faster build from the section below, which also has the refine step. Each build ran once, so a gap of 30 s in the refine step is within the noise to expect.

Faster builds

Build time fell from — to — seconds on SlideOn with 1,000,000 documents, and from — to — seconds on SparseUP. That is — and — times faster. At the server defaults, recall at 10 fell by — on SlideOn (1M) and by — on SparseUP.

Two kinds of change made this. Two settings send each document to fewer groups and add an optional refine step. They cost some recall. The code changes only made the same work faster. They left the result as it was.

Model Build before (s) Build now (s) Faster by Recall before Recall now Change Search ms before Search ms now

Recall and search time are at the server defaults. The settings table above has every setting for the new indexes. Pick the models with "faster build" in the name.

SlideOn at 1,000,000 documents, step by step

Each row changes one thing from the row above. The last two rows have the same recall, so the code changes did not alter the index.

Step Build (s) Recall at 10

Where the time goes

Seconds for each build phase. The first column is the build with fanout 3 and 2 and the refine step, before the code changes. Pruning, seed lists and sketches got much faster. Partition and leaf scoring did not change, and they are now the largest costs besides refine.

Phase SlideOn, before SlideOn, now SparseUP, now

Leaf scoring took 34 s in one SlideOn run and 20 s in another with the same code, so treat gaps of that size as noise. SparseUP has no "before" column because it was not timed by phase.

What changed in the code
  • Fanout. Each document used to go to 10 groups at the first level and 3 at the second. It now goes to 3 and 2. The build scores far fewer pairs, and recall is lower. Both numbers are now options: --fanout-depth0 and --fanout-depth1.
  • Refine step. Optional, with --refine. It searches the built graph for each document and prunes the neighbors again, which wins back part of the lost recall. It costs build time.
  • Robust prune. The step compares each candidate with the neighbors kept so far. It used to merge two sorted lists for every comparison. Now each kept neighbor is first written into a dense array, and each candidate reads its values from the array. The results are identical.
  • Seed lists. They used hash sets and maps for every non-zero value. They now use arrays indexed by term id. The output is the same.
  • Routing sketches. They are built on all cores instead of one.
  • Saving. The vectors and sketches are written through a buffered writer, so the whole file is no longer built in memory first. This lowers peak memory while saving. It is not in the timings above.
  • Timing. A build with the performance-timing feature prints the time of each phase and the peak memory. The phase table comes from that output.

What to keep in mind

  • The sections before "Faster builds" use the first indexes. The faster builds are only in the "Faster builds" section and the settings table.
  • SlideOn uses 1,990,000 documents everywhere except the build-time comparison, which has the 1,000,000-document indexes. Those are named "SlideOn 1M".
  • Each query is held out of the document set, so no query finds itself.
  • Quality is measured once over all 10,000 queries. Latency and throughput use 2,000 requests at each client count.
  • Each setting ran once. Differences of a few thousandths in recall are inside the noise to expect from a single run.
  • Millisecond columns in the settings table are measured by the client. Search ms is the time inside search.