Metadata-Version: 2.1
Name: madhava-l2
Version: 1.0.0
Summary: Deterministic vector search with Cauchy-Schwarz bound pruning + exact-L2 post-filter (BIGANN L2 verified)
Keywords: vector-search,cauchy-schwarz,deterministic,l2,bigann,rag,nn-search,bound
Author-Email: Winnex Brasil Soluções Empresariais LTDA-ME <pay@winnex.ai>
License: Business Source License 1.1
         
         License text copyright (c) 2017 MariaDB Corporation Ab, All Rights Reserved.
         "Business Source License" is a trademark of MariaDB Corporation Ab.
         
         Parameters
         
         Licensor:             Winnex Brasil Solucoes Empresariais LTDA - ME
         Licensed Work:        Winnex Audit Module
                               The Licensed Work is (c) 2026 Winnex Brasil Solucoes
                               Empresariais LTDA - ME
         Additional Use Grant: You may make use of the Licensed Work, provided that
                               you do not use the Licensed Work for a Search Service,
                               or any other service that exposes the functionality of
                               the Licensed Work to third parties as a service.
                               "Search Service" means a commercial offering that allows
                               third parties (other than your employees and contractors)
                               to use the functionality of the Licensed Work to perform
                               vector similarity search.
         
         Change Date:          2036-01-01
         Change License:        GNU General Public License v2.0 or later
         
         *****************************************************************************
         
         Business Source License 1.1
         
         Terms
         
         The Licensor hereby grants you the right to copy, modify, create derivative
         works, redistribute, and make non-production use of the Licensed Work. The
         Licensor may make an Additional Use Grant, above, permitting limited
         production use.
         
         Effective on the Change Date, or the fourth anniversary of the first
         publicly available distribution of a specific version of the Licensed Work
         under this license, whichever comes first, the Licensed Work will be made
         available under the terms of the Change License, or in the absence of a
         Change License, the GNU General Public License version 2.0 or later.
         
         All copies of the original and modified Licensed Work, and derivative works
         of the Licensed Work, are subject to this License. This License applies
         separately for each version of the Licensed Work and the Change Date may
         vary for each version of the Licensed Work released by Licensor.
         
         You must conspicuously display this License on each original or modified
         copy of the Licensed Work. If you receive the Licensed Work in original or
         modified form from a third party, the terms and conditions set forth in this
         License apply to your use of that work.
         
         Any use of the Licensed Work in violation of this License will automatically
         terminate your rights under this License for the current and all other
         versions of the Licensed Work.
         
         This License does not grant you any right in any trademark or logo of
         Licensor or its affiliates (provided that you may use a trademark or logo of
         Licensor as expressly required by this License).
         
         TO THE EXTENT PERMITTED BY APPLICABLE LAW, THE LICENSED WORK IS PROVIDED ON
         AN "AS IS" BASIS. LICENSOR HEREBY DISCLAIMS ALL WARRANTIES AND CONDITIONS,
         EXPRESS OR IMPLIED, INCLUDING (WITHOUT LIMITATION) WARRANTIES OF
         MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, NON-INFRINGEMENT, AND
         TITLE.
         
         For inquiries: pay@winnex.ai
         
Classifier: Programming Language :: C++
Classifier: Programming Language :: Python :: 3
Classifier: Topic :: Scientific/Engineering :: Artificial Intelligence
Classifier: Topic :: Software Development :: Libraries
Project-URL: Homepage, https://winnex.ai
Project-URL: Source, https://github.com/winnex-ai
Requires-Python: >=3.8
Requires-Dist: numpy>=1.20
Description-Content-Type: text/markdown

<div align="center">

# madhava-l2

**Deterministic vector search with mathematical guarantees.**

Every document excluded from the results carries a proof that it could not be in the top-K — by the **Cauchy-Schwarz inequality**. Zero bound violations by construction.

[![PyPI](https://img.shields.io/badge/pip%20install-madhava--l2-467C45)](https://pypi.org/project/madhava-l2)
[![Python](https://img.shields.io/badge/Python-3.8%2B-467C45)](https://www.python.org/)
[![C++](https://img.shields.io/badge/C%2B%2B-20-467C45)](https://isocpp.org/)
[![License: BSL 1.1](https://img.shields.io/badge/License-BSL%201.1-467C45)](LICENSE)
[![Benchmark](https://img.shields.io/badge/BIGANN--100M-L2%20verified-467C45)](docs/VERIFIED.md)

</div>

---

`madhava-l2` is a real, pip-installable Python package with a native C++20 core. It answers a question no approximate index (HNSW, IVF, PQ) can answer:

> **"Prove that your search did not miss a relevant document."**

The proof is per-document and mathematical: a Cauchy-Schwarz upper bound on the inner product, which converts into a lower bound on L2². If the bound says a vector cannot be in the top-K, that vector **is not in the top-K**. No heuristics, no random graphs, no "we think it's fine."

Verified on the **official BIGANN-100M L2 ground truth** — see [Benchmarks](#benchmarks).

## Table of contents

- [Installation](#installation)
- [Quick start](#quick-start)
- [Why?](#why)
- [API](#api)
- [The mathematics](#the-mathematics)
- [Benchmarks](#benchmarks)
- [Honest comparison](#honest-comparison)
- [Build from source](#build-from-source)
- [License](#license)

---

## Installation

```bash
pip install madhava-l2
```

Requirements: Python ≥ 3.8, NumPy. The C++ core ships pre-built in the wheel
(manylinux); a C++20 compiler + CMake ≥ 3.20 are needed only when building
from source.

> Not published to PyPI yet? Install straight from this repo:
>
> ```bash
> pip install git+https://github.com/winnex-ai/madhava-l2.git
> ```

## Quick start

```python
import numpy as np
import madhava_l2

# 1. Build an engine over your corpus (uint8, shape (n, dim)).
corpus = np.random.randint(0, 256, size=(100_000, 128), dtype=np.uint8)

engine = madhava_l2.build_engine(corpus, dim=128, k=10)
print(f"indexed {engine.num_vectors()} vectors in {engine.build_seconds():.2f}s")

# 2. Search.
query = corpus[0].astype(np.float32)   # (128,) float32
result = engine.search(query)

print(result.indices)                  # top-K dataset ids, ascending L2²
print(result.latency_ms)               # milliseconds
print(result.bound_violations)         # always 0 — the guarantee
```

That's it. Same query + same data → same result, every time. Deterministic.

## Why?

Modern vector search is a heuristic gamble. HNSW builds a random proximity
graph and *hopes* it didn't prune a relevant neighbor; IVF picks clusters and
hopes the right one was probed. When the search is a legal discovery, a
medical record lookup, or a compliance audit, "hope" is not a defensible
answer.

**madhava-l2 replaces hope with proof.** Each excluded document carries its
upper bound; if the bound is below the threshold, exclusion is a theorem, not
a guess.

| Property | HNSW / IVF / PQ | **madhava-l2** |
|---|---|---|
| Deterministic (same input → same output) | No (random graph) | **Yes** |
| Proves every exclusion | No | **Yes** (Cauchy-Schwarz) |
| Bound violations | Not measurable | **0** |
| Rebuild speed (1M) | ~40 s | **~2.6 s** |
| Exact-recall ceiling reachable | No | **Yes** (post-filter) |

## API

### `madhava_l2.build_engine(corpus, *, dim=None, stage1_dim=64, k=10, k1_fraction=0.05, postfilter=True, seed=42) -> MadhavaL2`

Build an index over a `(n, dim)` uint8 array.

- `dim` — vector dimensionality (defaults to `corpus.shape[1]`).
- `stage1_dim` — dimensionality of the Stage-1 QR projection (64 by default).
- `k` — number of results to return.
- `k1_fraction` — fraction of the corpus kept after Stage-1 pruning (0.05 = 5%).
- `postfilter` — when `True`, exact L2 is computed on the survivors so the
  result matches the exact top-K of the surviving set.

### `engine.search(query: np.ndarray) -> SearchResult`

Returns `indices`, `latency_ms`, `k1`, `k3`, `bound_pairs`, `bound_violations`.

### `engine.search_exact(query: np.ndarray) -> SearchResult`

Exhaustive L2 scan over all N vectors — the **recall ceiling** of your corpus.
Use it to measure how close an approximate index gets to the physical limit.

### `madhava_l2.benchmark_vs_groundtruth(engine, queries, gt_ids, *, query_alignment=1, k=None) -> dict`

Evaluate against ground-truth id lists. Returns `recall_at_k`, `ndcg_at_k`,
`latency_ms`, and per-query detail.

### Metrics

- `madhava_l2.recall_at_k(result, gt_set, k)`
- `madhava_l2.ndcg_at_k(result, gt_set, k)`
- `madhava_l2.read_bigann_groundtruth(path, n_queries)`

## The mathematics

For any query `q` and candidate vector `v`, the **Cauchy-Schwarz inequality**
bounds the raw inner product:

```
⟨v, q⟩  ≤  ⟨Pv, Pq⟩  +  ‖v − PᵀPv‖ · ‖q − PᵀPq‖
```

where `P` is a QR-orthogonalized (Modified Gram-Schmidt) random projection.
Because

```
‖v − q‖²  =  ‖v‖² + ‖q‖² − 2·⟨v, q⟩
```

the bound on `⟨v, q⟩` becomes a **lower bound on L2²**:

```
‖v − q‖²  ≥  ‖v‖² + ‖q‖² − 2·UB(⟨v, q⟩)
```

**Stage 1** computes this lower bound for every vector and keeps the top-k1
by smallest L2². Any vector pruned here is *mathematically proven* not to be
in the exact top-K. Bound violations = **0 by construction**.

**Post-filter** (optional) computes the exact L2² on the surviving top-k1 and
returns the true top-K. Because Stage 1 never prunes a real neighbor, the
post-filter recovers **everything a perfect scan would find**.

The residual `‖v − PᵀPv‖` is computed on the **real float32 projection**, not
the int8-quantized one — this is what the inequality requires, and it is what
makes the bound exact rather than approximate.

## Benchmarks

Verified 2026-08-04 against the **official BIGANN-100M L2 ground truth** on a
CPU-only machine (28 threads, AVX2+FMA).

| Scale | Exact-scan ceiling<br>(R@10) | madhava-l2<br>(R@10) | Efficiency |
|---|---|---|---|
| 10M | 0.430 | **0.430** | **100%** |
| 100M | 0.788 | 0.745 | **94%** |

The **ceiling** column is `search_exact` — a perfect exhaustive scan over the
same subset. madhava-l2 reaches **100% of that ceiling at 10M** and 94% at
100M, with **0 bound violations** at every scale.

### Why is the ceiling not 1.0?

The official BIGANN L2 ground truth was generated in the full 1B space. In a
100M subset, the exact top-K by L2² differs, so even a perfect scan caps at
R@10 ≈ 0.79. **No** index — exact or approximate — can do better on this
subset against this ground truth. madhava-l2 gets essentially all of it.

Reproduce:

```bash
python -m madhava_l2.benchmark --n 10000000 --nq 50
```

Or via the C++ executable:

```bash
./build/madhava_l2_bench bigann_data/base.u8bin \
    bigann_data/unif_query_10k.u8bin \
    bigann_data/unif_groundtruth_10k.bin 100000000 50 0.05
```

## Honest comparison

We are explicit about where madhava-l2 **does not** win:

| Use case | Best tool | Why |
|---|---|---|
| Lowest latency (sub-ms) | HNSW | HNSW ≈ 0.45 ms vs madhava ≈ 2.7 ms at 50K×1536D |
| **Provable completeness** | **madhava-l2** | Only engine with 0 bound violations + per-doc proof |
| Frequent index rebuilds | **madhava-l2** | Build ≈ 2.6 s (1M) vs HNSW ≈ 40 s |
| Regulated / auditable retrieval | **madhava-l2** | Deterministic, per-document audit trail |

**If you need raw speed, use HNSW — it is excellent.** madhava-l2 is for the
regions where "fast but unprovable" is a liability: legal discovery, medical
records, financial compliance, government audits, and RAG systems that must
not silently drop a relevant document.

## Build from source

```bash
# Wheel + sdist (pip-installable)
python -m build

# C++ library only
cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j
ctest --test-dir build        # C++ unit tests

# Python tests
python -m pytest tests/python/
```

## License

**Business Source License 1.1** — same as the Winnex stack. Free to use for
evaluation and non-production work. Commercial use requires a license.

`pay@winnex.ai` · Winnex Brasil Soluções Empresariais LTDA-ME · Goiânia, Brazil
