A team of researchers built a search system that promises to never quietly drop a matching result - the tradeoff is it's nearly six times slower.
The system, called FRESH-GEORANGE, targets a specific flaw in how apps search for nearby things that also meet a semantic condition - restaurants that are family-friendly, say, within two miles. Standard search tools built on embedding indexes return an approximate top list and can silently skip qualifying results without telling you. FRESH-GEORANGE instead offers two modes: an exact mode that scans every non-prunable block and always finds everything, and a certified mode that can stop early but reports a mathematically backed lower bound on how much it might have missed. In a CPU-only pilot using 2,500 real OpenFlights airport records and 740 simulated edits, exact mode hit 100% recall on all 180 test queries, while the certified mode set to a 95% target actually delivered 99.91% recall with no violations of its own guarantee.
That's a real fix for a real problem: most vector search deployed today has no way to tell you what it missed, and app builders mostly just trust the ranked list. A provable floor on completeness, even a conservative one, is meaningfully different from a system that is merely probably good enough. But the certified mode's median query took 7.24 milliseconds against a 1.24 millisecond baseline - a 5.85x hit - and replaying a long history of edits eventually got slower than just rebuilding the index from scratch.
The authors are upfront that this is a proof of concept for the completeness math, not a performance case, and it still needs testing against real map data and real incremental-update systems before anyone should trust it near production.