divsel

Diverse subset selection that actually has a guarantee. A native (Rust) implementation of GIST — max-min diversification with submodular utility — with Python bindings that are zero-copy for metric="euclidean" (the default, metric="cosine", makes exactly one L2-normalised copy).

Status: 0.1.0, the first release. Changes: CHANGELOG.md; how a release is cut: docs/RELEASE.md.

Install

pip install divsel      # Python: one abi3 wheel covers CPython 3.11-3.14 per platform
cargo add divsel        # Rust: the core crate

From a checkout instead: pip install . (needs a Rust toolchain, 1.83+). Free-threaded CPython 3.14t is served by a separate version-specific cp314t wheel, not the abi3 one. Adapter extras: pip install "divsel[langchain]" / "divsel[llamaindex]".

Quick start

import numpy as np
import divsel

vectors = np.random.default_rng(0).standard_normal((50, 8), dtype=np.float32)
picked = divsel.gist_select(vectors, k=5, lam=1.0)      # diverse-but-relevant row indices
full = divsel.gist_select_full(vectors, k=5, lam=1.0)   # + objective, diversity, threshold, stage
print(picked, full["f_value"])

# The default is metric="cosine": rows are L2-normalised into one copy, and the
# (1/2 - eps) and (2/3 - eps) bounds are proven for a true metric, so raw cosine
# distance (the paper's own experimental setting) is a well-behaved heuristic.
# metric="euclidean" is the zero-copy path, and the one the proofs cover:
picked = divsel.gist_select(vectors, k=5, lam=1.0, metric="euclidean")

gist_select runs on rayon's process-global thread pool (sized from RAYON_NUM_THREADS, built on the first call, never shut down). On Linux, forking after a first call — multiprocessing with the default fork start method — leaves the child with a pool whose workers do not exist; use spawn/forkserver, or make the first call inside each child.

The problem

You retrieved 50 candidates and need the best 5 to put in a prompt, a training batch, or a recommendation slate. Take the top 5 by score and you get five near-duplicates. The standard fix is MMR (Maximal Marginal Relevance, 1998) — a greedy heuristic with no approximation guarantee and an uninterpretable λ.

divsel solves the same shape of problem with a proof attached:

maximize   f(S) = g(S) + λ · min-pairwise-distance(S)     subject to |S| ≤ k

where g is any monotone submodular utility (relevance, coverage, facility location). GIST achieves (1/2 − ε)·OPT for submodular g and (2/3 − ε)·OPT for linear g — the latter provably tight, since no polynomial-time (2/3 + ε) algorithm exists unless P = NP. The problem is NP-hard to approximate beyond ≈0.5584.

Why this exists

GIST — Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility, Fahrbach, Ramalingam, Zadimoghaddam, Ahmadian, Citovsky & DeSalvo (Google Research), NeurIPS 2025, arXiv:2405.18754 — is a strong result with no production-grade implementation. As of August 2026:

• crates.io returns one result for submodular, and it is unrelated. No maintained Rust crate does submodular maximization, facility location, or GIST.
• The two Python implementations are a 1-commit release with no LICENSE file in its repository (the PyPI wheel does carry one) and a 6-commit repo that was never published to PyPI.
• submodlib (131★) implements no combined g(S) + λ·div(S) objective at all, has had no release since 0.0.3 (PyPI upload 2025-05-14), and ships no Windows wheels and no sdist — you cannot install it on Windows, or on Python 3.13/3.14, at any price.

So divsel aims at three things nobody currently offers together: a real license, wheels that install everywhere, and benchmarks you can reproduce from the repo. The measurements behind these claims — the installability matrix (all 48 cells measured: Windows locally and Linux/Windows/macOS on CI; the abi3 wheel does not cover free-threaded 3.14t), the comparison against gist-select, gist-sampling and MMR, and the incumbents' own README numbers re-run — are in docs/benchmarks/README.md, produced by bench/compare.py.

Design commitments

• The paper is the spec. Every constant transcribed from arXiv:2405.18754v3. Where the paper is silent (argmax tie-breaking), divsel documents its choice as a choice rather than inventing a citation.
• Proven, not asserted. A brute-force oracle enumerates OPT on small instances and asserts the approximation ratio actually holds — the test no incumbent ships.
• Installs everywhere. abi3 wheels for Python 3.11 → 3.14, Linux · macOS · Windows, x86_64 and aarch64.
• Reference implementation. Exports golden-selection.json; the ports in Aura (Python) and limbic (TypeScript) conform to it.
• Checked against an independent rewrite. A 90,000-instance differential (2026-08-26) between the Rust core and Aura's pure-Python port — written from docs/CONFORMANCE.md alone, never from this source — found zero algorithmic disagreements: all 1,164 differing selections reproduced divsel's answer once the port was fed divsel's own f32 distance matrix. Not a claim that the two always agree — a claim that where they differ, it is the width of the distance arithmetic. Details, parameter ranges and the two contract defects it exposed: Independent verification.
• Apache-2.0.

Drop-in for MMR

Both adapters live behind optional extras; plain import divsel never imports either framework.

LangChain — pip install "divsel[langchain]"

from divsel.adapters.langchain import DivselRetriever

retriever = DivselRetriever(vectorstore=vs, k=5, fetch_k=20, lam=1.0)
docs = retriever.invoke("your query")   # replaces vs.as_retriever(search_type="mmr")

Like MMR it fetches fetch_k candidates by query similarity, then returns the k of them maximizing g(S) + λ·min-distance(S) — with the guarantee instead of the greedy heuristic. Honest caveats: candidate texts are re-embedded through vectorstore.embeddings (stores do not expose their stored vectors uniformly), and when the store exposes no embeddings at all the retriever emits DivselFallbackWarning and returns plain, undiversified top-k (strict=True raises instead).

LlamaIndex — pip install "divsel[llamaindex]"

from divsel.adapters.llamaindex import DivselNodePostprocessor

engine = index.as_query_engine(
    similarity_top_k=20,   # this is the fetch_k — the candidate pool
    node_postprocessors=[DivselNodePostprocessor(k=5, lam=1.0)],
)

There is no fetch_k parameter here: the retriever's similarity_top_k already fixes the candidate pool, and the postprocessor diversifies it down to k. Vectors come from node.embedding when every node carries one, else from an optional embed_model; with neither, it warns (DivselFallbackWarning) and returns top-k by score (strict=True raises).

Name

divsel = diverse selection. Verified free on both crates.io and PyPI, 2026-08-21.