KNN Prefiltering Manticore Search with ACORN-1

KNN Prefiltering in Manticore Search: Optimizing HNSW with ACORN-1

KNN prefiltering in Manticore Search version 19.0.1+ integrates attribute filters directly into the HNSW graph traversal. This eliminates the inefficiency of post-filtering, where KNN scans the entire dataset and filters are applied afterward. In a catalog of 10 million products with a 'electronics' category filter (5% of documents), post-filtering might return fewer than the requested k results, wasting resources on irrelevant nodes.

Prefiltering checks conditions during candidate exploration, ensuring exactly k results from matching documents.

Issues with Post-Filtering and the Shift to Prefiltering

In post-filtering, HNSW ignores filters: the algorithm finds the global k nearest vectors, then discards non-matches. With strict filters (e.g., category='electronics' AND price<500), the graph explores mostly irrelevant areas, reducing recall and increasing latency.

Example SQL query with automatic prefiltering:

SELECT id, title, knn_dist()
FROM products
WHERE knn(embedding, (0.12, 0.45, 0.78, 0.33))
  AND category = 'electronics'
  AND price < 500
LIMIT 10;

Equivalent in JSON:

{
    "table": "products",
    "knn": {
        "field": "embedding",
        "query": [0.12, 0.45, 0.78, 0.33]
    },
    "query": {
        "bool": {
            "must": [
                { "equals": { "category": "electronics" } },
                { "range": { "price": { "lt": 500 } } }
            ]
        }
    },
    "limit": 10
}

The category and price filters are checked during HNSW traversal.

Naive Prefiltering: Principles and Limitations

The naive approach traverses HNSW as usual but only adds filter-passing nodes to the priority queue. Non-matching nodes still aid navigation to maintain graph connectivity.

Limitation: Distances are computed for all neighbors, regardless of filters. At 5% selectivity, 95% of computations (the most expensive operation) are wasted.

ACORN-1 in Manticore: Advanced Optimization

Manticore implements ACORN-1 for selective filters (<60% of documents):

• Filter check before distance: Neighbors are filtered before distance computation. Non-matches are skipped without evaluation.
• Adaptive expansion: From non-matching nodes, the algorithm explores their neighbors (up to 3–4 levels), focusing on finding suitable candidates.

This cuts distance computations by 95% at low selectivity, speeding up searches without quality loss.

ACORN-1 activates automatically for high selectivity.

Automatic Execution Strategy Selection

Manticore's planner evaluates selectivity using attribute histograms:

• Standard HNSW: >60% documents pass filter — naive prefiltering.
• ACORN-1: 1–60% — optimized traversal.
• Fullscan: <1% (e.g., 50 out of 10 million) — direct scan of filtered documents, bypassing HNSW.

It compares expected HNSW nodes visited vs. filtered subset size.

Managing Filtering Modes

Post-filtering (prefilter=0 or "prefilter": false):

SELECT id, knn_dist()
FROM products
WHERE knn(embedding, (0.12, 0.45, 0.78, 0.33), { prefilter=0 })
  AND category = 'electronics'
LIMIT 10;

Full scan (fullscan=1 or "fullscan": true):

SELECT id, knn_dist()
FROM products
WHERE knn(embedding, (0.12, 0.45, 0.78, 0.33), { fullscan=1 })
  AND category = 'electronics'
LIMIT 10;

Post-filtering suits cases needing global nearest neighbors or >95% document pass-through. Fullscan works for tiny filtered sets.

| Mode | Selectivity | Advantages | Disadvantages |

|------|-------------|------------|---------------|

| Post-filtering | High (>95%) | Simplicity, predictability | Fewer than k results |

| Prefiltering (naive) | Medium (60–95%) | Reliable k results | Overhead |

| ACORN-1 | Low (1–60%) | Compute savings | Implementation complexity |

| Fullscan | Very low (<1%) | Exact recall | Linear complexity |

Key Takeaways

• Prefiltering is the default for KNN+attributes, guaranteeing k results.
• ACORN-1 saves up to 95% distance computations at <60% selectivity.
• Automatic fullscan for ultra-selective filters.
• Post-filtering for global ranking or debugging.
• Planner adapts per-query/per-segment using histograms.

— Editorial Team