When flat search beat the graph_

I wanted Astral's memory index to search 100,000 vectors in no more than 1.5 milliseconds at p50 while returning at least 90% of the true top ten. The first graph sweep did not come close to both. Its fastest setting took 0.413 milliseconds on average and returned 84.18%. Letting it run for 5.495 milliseconds raised recall to only 88.48%.

My first instinct was to improve the graph. I tried two changes that should have helped it make better decisions. Both failed when I measured them. That left the blunt alternative: score all 100,000 vectors on every query. The first single-threaded scan took 7.176 milliseconds. To make exhaustive search useful, I had to change the scan itself.

The final version reached 92.03% recall@10 at 0.5622 milliseconds per query. It split the scan across three workers and the caller, then removed invariant dispatch from the fixed 384-component kernel. I also tested the design on an Apple M5 Max and through Astral's Unreal wrapper.

The target

A result had to meet both goals:

• 100,000 stored vectors
• 384 components per vector
• cosine similarity
• a deterministic set of 64 queries for recall
• recall@10 of at least 90%, with 91% as the stretch target
• p50 query latency no greater than 1.5 milliseconds
• a warm index

I stored the vectors as E5M2, an eight-bit floating-point format. Each vector occupied 384 bytes, one quarter of the 1,536 bytes required by f32. That smaller representation loses precision, so I compared every result with an exhaustive f32 reference.

The Intel captures used a Core Ultra 7 265, Ubuntu 24.04, and GCC 13.3.0 release code. Search threads were restricted to CPUs 0-3, and the host reported the powersave governor. Each table identifies mean or percentile latency and top eight or top ten results.

I had already finished the E5M2 conversion work. The instructions you don't have explains how the x86 kernel converts E5M2 bytes through F16C and why my first version lost to a lookup table. That work made each dot product cheaper. It did not answer how many vectors each query should score.

Astral normally used an HNSW graph so it would not have to score every vector. A query starts from an entry point, explores nearby nodes, and keeps a bounded candidate set. efSearch controls how many candidates it considers. A larger value usually improves recall and always costs more work.

My baseline sweep showed the trade clearly:

This sweep reports mean latency, while the final target uses p50. At efSearch=32, recall missed by 5.82 points. At 128, mean latency reached 1.507 milliseconds and recall had gained less than one point. Moving from 256 to 512 added 2.62 milliseconds for another 1.57 recall points. The largest setting still missed 90%.

I could not reach both goals by asking this graph to traverse more nodes. I needed better routing or a different search method.

Two graph changes failed

First, I kept the query vector in f32 while the graph traversed E5M2 records. The stored vectors stayed compact, but the query no longer lost precision before every score.

At efSearch=128, latency improved from 1.507 to 1.293 milliseconds. Recall moved from 85.16% to 85.35%. At efSearch=512, latency improved from 5.495 to 4.889 milliseconds. Recall fell from 88.48% to 88.28%.

I had made scoring faster without making the graph's answers better. At the highest budget, recall was worse. I removed the change.

Next, I added four deterministic links to spread connections across level zero. I found that an existing condition compared level-zero capacity with the smaller upper-level capacity, so the links were never added. After I corrected it, a 64-node topology probe grew from 829 to 957 base edges. I was finally testing a different graph. Earlier runs had silently measured the old one.

The 100,000-vector result still rejected it. At efSearch=128, recall fell from 85.16% to 84.18% while latency rose from 1.507 to 1.582 milliseconds. At efSearch=512, recall improved from 88.48% to 88.87%, but latency also rose from 5.495 to 5.646 milliseconds.

The extra links produced a small improvement only at the most expensive setting. They reduced quality at efSearch=128. I removed the source change and its temporary test.

Early query quantization was not the cause, and four deterministic links did not repair low-budget routing. I stopped both experiments.

Exact E5M2 search met the recall requirement

I then measured the simplest alternative. An exhaustive E5M2 scan scores every stored record, so graph routing cannot lose a candidate. Its remaining quality loss comes from the compact representation itself.

The corrected top-ten run reached 92.03% recall@10. E5M2 preserved enough of the original ordering to exceed my 90% requirement. The graph's 88.48% was not the best result available from those same stored bytes.

Astral already selects exact flat search for compact indexes no larger than 16 MiB. A 10,000 by 384 E5M2 table uses 3.84 MB, so older benchmark rows with graph names at that size actually ran flat search. The 100,000-vector table uses 38.4 MB and required explicit flat selection.

Recall was solved. Latency was not. The serial flat scan took 7.176 milliseconds at p50. Every query processed 38.4 million stored components and maintained its top results. I needed parallel execution and less control work per record to get below 1.5 milliseconds.

Each worker kept private results

Astral already had a batch sharder that split record ranges across workers. Each worker kept a private top-k buffer, so the scan never updated one shared result structure. The path did not support compact storage or top-k values above eight. It also reserved stack space for a matrix of sixteen queries.

I added a single-query sharder for compact storage through top ten. Each participant received a disjoint record range and wrote to its own top-k buffer. The caller merged those small buffers after all range scans finished. No participant updated a shared top-k while scoring records.

Separating the single-query storage also reduced the release-build stack frame from 40,960 bytes to 3,048 bytes. The larger frame came from reusing the full batch matrix for one query. The dedicated path reserved only the state it used.

With three workers on four allowed cores, my first sharded version measured 1.111 milliseconds at p50, 1.139 at p95, and 1.152 at p99. Recall@8 stayed at 92.19%. The API caller still parked while the workers scanned every range.

Across the complete run, serial execution recorded 69.66 billion cycles and 99.45 billion instructions. Three-worker execution recorded 48.60 billion cycles and 109.69 billion instructions. It finished sooner despite executing more instructions. Cache misses fell from 555.35 million to 422.64 million.

The caller processed the final range

I was still parking a thread that could do useful work. I gave the final record range to the API caller and left the other ranges with the workers. Every participant kept private scan state. The scoring loop still had no shared top-k updates.

With one worker plus the caller on two cores, p50 fell from 3.226 to 1.630 milliseconds. With three workers plus the caller on four cores, p50 fell from 1.111 to 0.802 milliseconds. The latter run measured 0.829 milliseconds at p95 and 0.849 at p99.

AstralInit::thread_count counts runtime workers, not total participating threads. Setting it to four on a machine restricted to four cores created four workers plus the caller. Five runnable threads competed for four cores. The p50 regressed to 7.42 milliseconds. Two workers plus the caller produced the same kind of oversubscription when only two cores were allowed.

The right four-core configuration was three workers plus the caller. I changed the benchmark runner to record the runtime worker count explicitly.

Generic dispatch still ran for every record

At 0.802 milliseconds, I went back to the generated code. Generic slot, storage, and metric dispatch still ran inside every record iteration. None of those decisions changed within a dense E5M2 cosine shard.

I moved the decisions before the record loop. Across 2,048 queries, aggregate instructions fell from 100.18 billion to 92.39 billion. Branch instructions fell from 6.48 billion to 4.43 billion. The vector data and top-k work did not change. The loop simply stopped checking facts the shard already knew.

I used the fixed dimension as one more invariant. A 384-component vector contains twelve 32-byte AVX2 blocks. Expanding those blocks removed the inner loop and tail handling while preserving four independent accumulators. The generated function contained 48 vcvtph2ps conversions and no YMM stack spill.

b7851:  vpslld       ymm0, ymm0, 0x8
b7856:  vmovdqa      xmm3, xmm0
b785a:  vextracti128 xmm0, ymm0, 0x1
b7860:  vpackusdw    xmm3, xmm3, xmm0
b7865:  vpmovzxbd    ymm0, QWORD PTR [r11+0x8]
b786b:  vcvtph2ps    ymm3, xmm3
b7870:  vfmadd132ps  ymm3, ymm2, YMMWORD PTR [rbx]
b7875:  vpslld       ymm0, ymm0, 0x8
b788f:  vcvtph2ps    ymm1, xmm1
b7894:  vfmadd132ps  ymm1, ymm2, YMMWORD PTR [rbx+0x20]

This excerpt is one repeated part of the expanded function. The destination changes from ymm3 to ymm1, breaking the dependency chain. The full function repeats the same conversion and accumulation pattern across all twelve blocks.

On two allowed cores, the fixed kernel measured 1.077 milliseconds at p50, 1.109 at p95, and 1.116 at p99. On four allowed cores, it measured 0.550 milliseconds at p50, 0.557 at p95, and 0.569 at p99. The recall@8 verification remained 92.19%.

Compared with the caller-owned-shard capture, the final four-core run used 30% fewer cycles, 24% fewer instructions, and 82% fewer branch instructions. Cache misses barely moved, from 342.49 million to 339.01 million. The improvement came from less control work and the fixed-size kernel, not from a large cache-miss reduction.

The corrected top-ten run used the same 100,000 by 384 fixture and three workers plus the caller. It measured 92.03% recall@10 at a mean 562.20 microseconds per query. I keep that number separate from the 92.19% recall@8 kernel captures because they use different result counts.

Apple silicon needed a different kernel

I kept the same parallel structure on an Apple M5 Max, but the vector conversion had to change. My first ARM implementation reconstructed f32 values with NEON integer operations. It measured 5.516 milliseconds at p50 with one worker plus the caller and 3.348 milliseconds with three workers plus the caller.

Apple Clang exposed a shorter route through binary16. I shifted each E5M2 byte into the corresponding binary16 bit position, then used fcvtl and fcvtl2 to widen it. The generated loop contains two shll.8h, four fcvtl or fcvtl2, and four fmla.4s instructions per sixteen dimensions.

1002cc4f4:  ldp       d5, d6, [x19]
1002cc4f8:  shll.8h   v5, v5, #8
1002cc4fc:  fcvtl     v7.4s, v5.4h
1002cc500:  fcvtl2    v5.4s, v5.8h
1002cc504:  shll.8h   v6, v6, #8
1002cc508:  ldp       q16, q17, [x5, #-0x20]
1002cc50c:  fmla.4s   v1, v16, v7
1002cc510:  fcvtl     v7.4s, v6.4h
1002cc514:  fcvtl2    v6.4s, v6.8h
1002cc518:  fmla.4s   v2, v17, v5
1002cc51c:  ldp       q5, q16, [x5], #0x40
1002cc520:  fmla.4s   v3, v5, v7
1002cc524:  fmla.4s   v4, v16, v6

The native results were:

Recall@8 remained 92.19%. The macOS threads were not pinned to physical cores. Against the Intel single-caller result of 6.123 milliseconds, the M5 was 3.65 times faster with one execution thread, 16% faster with two, and 8% faster with four. The machines also used different cores, compilers, operating systems, and scheduling controls.

Fully expanding all 24 ARM blocks increased the single-thread p50 from 1.676 to 1.695 milliseconds. I removed that version and retained the loop. The fixed expansion that helped x86 did not help this ARM build.

The engine wrapper reproduced the result

The corrected top-ten result exercised Astral directly. I also wanted to know whether the public wrapper preserved it, so I ran the Unreal 5.7 Automation test on the Intel machine. That path included UAstralBlueprintLibrary query and result conversion before search began.

It measured 92.03% recall@10, 522.70 microseconds at p50, 579.60 at p95, and 587.30 at p99. This was separate from the native capture, which measured a 562.20-microsecond mean.

The search path that shipped

I removed both graph experiments. The original graph sweep had topped out at 88.48% recall with a mean latency of 5.495 milliseconds.

The final version used private shards, with the caller processing one of them. x86 kept the fixed kernel, while ARM kept its ordinary loop. The final top-ten result was 92.03% recall at a mean 0.5622 milliseconds with three workers plus the caller.

On this 100,000-vector, 384-component E5M2 index, scoring every record returned more of the true top ten and ran faster than the graph settings I tested. The graph remains available for larger or differently distributed indexes.