Trigpoint: Calibrated, Certified Pruning for Vector Search inside PostgreSQL

Accurate, low-latency vector search inside the relational database is vital for applications that keep embeddings beside their rows. Current PostgreSQL indexes rely on one global graph or on quantised partitions, introducing large indexes, hours of graph repair after deletes and no statement about the neighbours an approximate scan misses. This paper presents Trigpoint, a calibrated and certifiable PostgreSQL access method that keeps one 0.86 KB structure per row, independent of the dimension: a 290-byte sketch and its graph links. A graph over the sketches routes a query to cells or shards; the same bytes give Panorama’s level bound with the 8-bit quantisation error folded in, so a scan that bounds every row certifies its result; and a per-level relaxation of the bound, set by Conformal Risk Control on the pruning decision, bounds the expected share of a query’s neighbours the pruning drops. Across emulated shards the bound opens a second round only for shards that can still hold a closer point. We evaluate it inside PostgreSQL 17 against pgvector’s HNSW, VectorChord and pgvectorscale on 75k to 5M rows. With every index resident, its median latency at 99 % recall is 1.4–2.9× below the others at 75k and 3.4–6.7× at GIST 100k, and ties HNSW at 1M (9.0 against 9.8 ms); at PostgreSQL’s 2 GB default it is 2× faster at 1M, because its 0.86 GB image lives outside the pool and HNSW’s 8.2 GB index does not fit, and at 5M it is 1.3× below HNSW over halfvec at matched recall, where pgvectorscale stops at 96 %. Its index is 9.6× smaller and builds 8× faster, an insert costs 4 ms against 30, and VACUUM after deletes is a two-minute compaction where HNSW’s graph repair took 5.9 h (4.3 h at 32 GB). It sustains 1.5–2.3× pgvector’s throughput from 1 to 32 clients, and its calibrated second round reaches 100 % recall at 4–7 extra shards of 64, certifying 38–51 % of queries. These results demonstrate the feasibility of one sketch that routes, bounds and certifies inside the database, as a proof-of-concept for certified in-database vector search. While the calibrated bound holds out of sample, it fails on off-distribution queries, which a drift check catches, and at library level the method loses to a global graph on 1M transformer embeddings, where the exact certificate also costs more than a dense scan.