HGraph MCI Companion

HGraph can optionally build an MCI (Maximal Clique Index) companion for filtered KNN search. The companion stores clique metadata beside the HGraph index and shares HGraph’s vector storage. It is not a standalone index type: create the index as hgraph, not mci.

Use this feature when filtered search is the main workload and the filter keeps only a small fraction of vectors. HGraph chooses between normal graph traversal and the MCI companion by comparing Filter::ValidRatio() with a threshold.

Build Configuration

MCI build parameters are flat fields in index_param. The companion is enabled when use_mci is true or when any MCI build parameter is present. The mci_knng_source parameter selects whether clique construction derives its KNN graph from the completed HGraph bottom graph or builds a dedicated ODescent graph:

{
  "dtype": "float32",
  "metric_type": "l2",
  "dim": 128,
  "index_param": {
    "base_quantization_type": "fp32",
    "max_degree": 32,
    "ef_construction": 400,
    "mci_mcs": 200,
    "mci_clique_max": 50,
    "mci_alpha": 1.2,
    "mci_knng_source": "odescent"
  }
}

The default source is hgraph, which preserves the existing behavior. Set the source to odescent to build the MCI KNN graph directly from the stored vectors. An internally configured external KNN graph path takes precedence over this selector.

Both the float fast path and the generic full-build path share a final coverage pass. Any node still uncovered after clique enumeration is placed in a fallback clique with graph neighbors (or a singleton when none are available). This pass relaxes clique distance constraints, preserves the seed under the clique-size cap, and counts only stored memberships.

Incremental Maintenance Parameters

These parameters also belong in index_param. They control ADD and survivor repair after deletion. Repair shares ADD’s existing-clique join and new-clique construction routines; it does not reinsert the existing vector into HGraph.

Degree is the size of the deduplicated union of other live members of all effective cliques covering the current point. It is neither HGraph out-degree nor the point’s clique-membership count. The degree stopping target is:

target = N <= 1 ? 0 :
    min(N - 1,
        max(mci_incremental_degree_min,
            min(N / mci_incremental_degree_n_divisor,
                mcs / mci_incremental_degree_mcs_divisor)));

N is the current live vector count, including the completed HGraph insertion batch but excluding marked removals; mcs means mci_mcs. Integer division rounds down. This is a stopping target, not a guaranteed minimum degree or a hard cap: joining a whole clique can overshoot it, and exhausted candidates or stalled construction can stop below it.

Migration warning: mci_incremental_added_mct is no longer supported. Remove this old clique-count setting from index_param and configure mci_incremental_degree_min, mci_incremental_degree_n_divisor, and mci_incremental_degree_mcs_divisor instead. The old key is ignored, not translated; leaving it in the JSON applies the new defaults unless the degree parameters are explicitly set. There is no equivalent one-to-one mapping because overlapping cliques contribute different numbers of unique neighbors. Recheck recall and mutation cost, and rebuild old snapshots with the new configuration rather than assuming that a removed parameter provides snapshot compatibility.

The default MCS divisor 2 limits the adaptive term to half the KNN candidate budget before the floor is applied; it does not cap the final target at half a clique size. MCS defaults to 200 and is distinct from mci_clique_max. If mcs=32 and the floor is 50, the target is min(N-1, 50) for every N, not max(50, N/10000). This is a tuning heuristic, not a guarantee that half the candidates become neighbors; the floor can dominate and a whole-clique join can exceed the target.

These tuning directions follow the implementation; they are not validated optimal settings. Keep dataset stages, mutation IDs, ground truth, and other settings fixed while changing one parameter at a time. Compare quality, throughput, mutation time, and memory together. For example, at N≈3m, mcs=100, degree_min=50, the default target is 50; changing only the live-count divisor leaves it unchanged whenever the size-dependent term remains at least 50. Explicit settings override defaults, and loading an existing index requires matching its stored parameters. Historical experiments using retirement threshold 3 do not measure the current default 30.

Search Configuration

Search parameters live under the hgraph search object:

{
    "hgraph": {
      "ef_search": 120,
      "use_mci": true,
      "mci_seed_ratio": 0.1,
      "hgraph_valid_ratio_threshold": 0.2
    }
}

use_mci defaults to true for search and can be set to false to disable MCI for a single query. hgraph_valid_ratio_threshold is the search routing threshold: use MCI when ValidRatio() is below this value; otherwise use HGraph. The default is 0.05.

The seed count is ceil(sqrt(current_vector_count) * mci_seed_ratio), with a minimum of one seed. mci_seed_ratio defaults to 0.1 and must be finite and non-negative. The resulting seed count is capped at the number of points that satisfy the filter.

mci_seed_coverage raises that budget to ceil(mci_seed_coverage * valid_count) whenever the target fits into mci_seed_max_count and does not exceed the vector count; otherwise the coverage term is dropped entirely rather than truncated. mci_seed_coverage defaults to 1.0 and mci_seed_max_count to 32768 (0 means unlimited). The budget never drops below one, so seeding cannot be disabled completely – set both terms to 0 to leave a single seed.

Because that term is dropped rather than clamped, mci_seed_coverage has no effect once the valid set exceeds mci_seed_max_count: for those (wide-filter) queries the budget silently falls back to the ceil(sqrt(N) * mci_seed_ratio) floor. Raising the cap is what extends the exact-seeding regime, at the cost of a larger seed phase. The default of 32768 keeps that enumeration cheap in absolute terms – 32768 inner ids are 128 KiB and therefore stay in cache – so the saturated skip stays a win instead of turning a wide predicate into a scan-sized seed phase.

The companion needs a Filter object with a meaningful ValidRatio() hint. Bitset and function filters are accepted, but a custom Filter gives the search planner better selectivity information.

Dynamic Neighbor Traversal

use_hybrid_traversal (default false) replaces the either/or routing above with a single traversal that handles both neighbor sources of every expanded vector in one pass:

• the sparse HGraph neighbors are scored first and pushed into the candidate heap, so the search subgraph stays connected regardless of selectivity;
• the clique members of the same vector are scored predicate-first, and that part is cut short by a virtual-overhead budget.

The budget stops the clique part once considered * (hybrid_filter_cost_ratio + local_selectivity) reaches hybrid_vob, where hybrid_filter_cost_ratio is O_filter / O_dist (the cost of one predicate filtering relative to one distance computation) and local_selectivity is the running predicate hit rate of the current neighbor traversal. A non-positive hybrid_vob disables the early stop. The two parameters default to 0.0 and 1.0, and hybrid_vob is expressed in units of O_dist.

{
    "hgraph": {
      "ef_search": 600,
      "use_hybrid_traversal": true,
      "hybrid_vob": 32.0,
      "mci_seed_ratio": 1.0,
      "mci_seed_coverage": 1.0
    }
}

The traversal is seeded from the predicate’s valid set using the same budget and samplers as the MCI route, so the two can be compared without the seed strategy confounding the result. When that budget ends up covering every valid point, all valid distances are already known and the traversal answers from the seeds directly; the expansion is skipped because it is provably redundant, not as an approximation. GetStatistics() reports the behavior through mci_hybrid_route ("hybrid" when the traversal ran), hybrid_seed_budget, hybrid_seeded_entries, hybrid_expansion_skipped, hybrid_expanded_nodes, hybrid_mci_members_considered, hybrid_dist_computations and hybrid_mci_stopped_early.

Code Map and Maintenance

Paths below are relative to the repository root.

The base has clique → nodes and node → cliques CSR. ADD and deletion repair share:

Node-deletion and clique-retirement markers are separate. Flush merges delta into CSR, preserves vector inner IDs, and may renumber cliques. FORCE_REMOVE also moves vector inner IDs.

Shared ADD/repair pipeline:

1. Insert an ADD batch into HGraph, then maintain the successful points: each chunk is planned in parallel and merged in inner-ID order by a single thread, and every row still follows the rules in steps 2-3. search_mci_knn calls HGraph KnnSearch with use_mci=false, not MCI search.
2. Target min(mci_mcs, visible_total - 1) neighbors. Internal ef is max(query_k, 100), not benchmark ef=320. Remove self, deleted, and out-of-range points; enlarge the request if needed.
3. Try existing cliques with |KNN ∩ C| / |C| >= join_ratio and room below the incremental cap, stopping at the unique-neighbor degree target rather than a clique-count limit. If degree remains below target, invoke the same local clique builder as full Build on not-yet-adjacent KNN candidates, repeating until the target is reached, candidates run out, or progress stops. Empty candidates yield a singleton. Incremental construction no longer stops alpha expansion at two members.
4. Deletion retires only affected cliques whose surviving size is less than delete_size. Select surviving members whose projected effective coverage is less than delete_mct; recheck coverage before repairing.
5. Pure-FP32 repair reads/decodes the existing point and uses the shared candidate/join/build path. It does not insert the vector again through public ADD. ADD sees its insertion prefix; repair can see the whole current HGraph.

The ADD clique-count limit has been removed; delete_mct still triggers repair. The degree target is max(mci_incremental_degree_min, min(N/10000, mcs/2)), with zero for N≤1 and otherwise capped at N-1; integer division rounds down. N counts live vectors including the completed graph insertion batch. The floor defaults to 50, so at N=10000 and mcs=200 the target is 50. Whole-clique joins may overshoot; candidate exhaustion or lack of progress can stop below target. Non-FP32 repair retains pair-distance candidate generation; FP32 findings do not establish RaBitQ behavior.

Add and MARK_REMOVE share a 100-successful-vector counter: Add checks per point; deletion checks after the complete batch is projected and repaired. Failed inserts and duplicate/missing removals do not count. A successful compaction, full rebuild, load, or FORCE_REMOVE end-of-batch compaction resets the counter. Allocation failure during automatic maintenance retains delta and retries on the next successful mutation. Delta remains searchable and serializable below the threshold.

MCI mutations share a serialization mutex. Physical moves and final shrinking hold exclusive force-remove protection. Repair releases that lock so internal HGraph queries can acquire read locks; MCI is unpublished and external searches may fall back to HGraph. Queries are not necessarily blocked for the entire operation. Mutations are not transactionally rolled back.

Benchmark Profile and C++ Integration

Pass this JSON string to Factory::CreateIndex("hgraph", config_json). MCI build keys are flat under index_param, not in a nested mci object. This is the Codefilter benchmark profile, not the defaults for every library option.

{
  "dtype": "float32",
  "metric_type": "cosine",
  "dim": 384,
  "index_param": {
    "base_quantization_type": "fp32",
    "base_io_type": "memory_io",
    "graph_type": "nsw",
    "max_degree": 32,
    "ef_construction": 200,
    "build_thread_count": 16,
    "support_force_remove": true,
    "use_mci": true,
    "mci_knng_source": "hgraph",
    "mci_mcs": 200,
    "mci_clique_max": 50,
    "mci_alpha": 1.2,
    "mci_incremental_join_ratio_threshold": 0.6,
    "mci_incremental_degree_min": 50,
    "mci_incremental_degree_n_divisor": 10000,
    "mci_incremental_degree_mcs_divisor": 2,
    "mci_incremental_clique_max": 50,
    "mci_delete_clique_size_threshold": 30,
    "mci_delete_node_mct_threshold": 3
  }
}

Enable support_force_remove at creation. MCI physical removal requires flat graph storage, enables reverse edges, and rejects incompatible deduplication, duplicate-group, or attribute storage.

For example, delete_size=4 considers affected cliques with 0–3 survivors, not all cliques containing a deleted point. Increasing delete_mct alone may do nothing if no small clique retires.

Search JSON uses hgraph, not index_param:

{
  "hgraph": {
    "ef_search": 320,
    "use_mci": true,
    "mci_seed_ratio": 0.1,
    "hgraph_valid_ratio_threshold": 1.0
  }
}

The library’s route threshold defaults to 0.05, while this profile and benchmark use 1.0. Filtered queries with selectivity below the threshold may use MCI; routing is not guaranteed. Supply an actual filter with accurate ValidRatio(), not an artificially low estimate. Set query use_mci=false for an ordinary-HGraph comparison on the same index.

The following integration fragment assumes JSON strings above, caller-prepared base, added, and query Datasets, a filter, and an external-label vector removed_labels. Include VSAG and standard exception headers. Keep non-owned Dataset buffers alive during calls.

auto created = vsag::Factory::CreateIndex("hgraph", config_json);
if (!created.has_value()) {
    throw std::runtime_error(created.error().message);
}
auto index = created.value();
auto check = [](const auto& result) {
    if (!result.has_value()) {
        throw std::runtime_error(result.error().message);
    }
};
auto built = index->Build(base);
check(built);
if (!built.value().empty()) {
    throw std::runtime_error("some initial vectors were not inserted");
}
auto removed = index->Remove(removed_labels, vsag::RemoveMode::FORCE_REMOVE);
check(removed);
auto appended = index->Add(added);
check(appended);
if (!appended.value().empty()) {
    throw std::runtime_error("some added vectors were not inserted");
}
// MCI compaction is automatic; no public Flush call is required or available.
auto result = index->KnnSearch(query, 10, search_json, filter);
check(result);

Build/Add also return failed-insertion labels: checking only expected is insufficient. removed.value() is the actual removal count. MARK_REMOVE retains physical slots. Compaction is automatic, including at the end of FORCE_REMOVE; it does not serialize. Remove accepts external labels, not inner slots; do not retain internal node/clique IDs across compaction. See examples/cpp/324_feature_hgraph_mci_companion.cpp for Dataset and Filter construction.

Add, Delete, Serialize, and Stats

When MCI is enabled by the flat build parameters, HGraph::Add() first inserts the HGraph batch, then updates the MCI companion for the successfully inserted rows. It first tries to join suitable existing cliques, then creates incremental cliques if the unique neighbor degree is still too low.

That update works in chunks. Inside a chunk the candidate KNN, the clique JOIN proposals and the local clique construction of every row are planned in parallel against one frozen read view, and a single thread then merges the plans in inner-ID order and applies them. Per-row coverage and the degree target do not depend on the planning order, but the candidate KNN comes from concurrent graph search, so as in the full parallel build the resulting clique structure may depend on the thread count and on scheduling.

Prefer Build() for the initial index, followed by incremental additions. Add on an empty index can trigger construction, but many tiny Adds are not recommended as a replacement for bulk Build.

When ADD needs a new clique, it shares the local graph, maximal-clique enumeration and selection core with full BuildMCICliques. The incremental size cap determines the local size threshold; it no longer accepts two members as the alpha-expansion stopping criterion. JOIN and construction use the degree target defined by the incremental maintenance parameters above, stopping when the target is reached, candidates are exhausted, or construction stalls. High-alpha fallback may still emit smaller cliques.

MARK_REMOVE updates the MCI companion as part of the same operation. After removing a node, MCI keeps every affected clique whose remaining live size is at least mci_delete_clique_size_threshold. It retires only smaller cliques and collects only their live members whose projected clique count is below mci_delete_node_mct_threshold. Those under-covered nodes are repaired with the same incremental join/build routine used by Add(), so the new memberships and cliques share Add’s delta storage. This avoids rebuilding the full one-hop neighborhood when most members still have sufficient clique coverage. MARK_REMOVE remains the default: logical deletion does not reclaim vector slots.

Set index_param.support_force_remove: true to enable index->Remove(ids, vsag::RemoveMode::FORCE_REMOVE). MCI automatically enables reverse graph edges and requires flat graph storage. Physical deletion remains incompatible with deduplicate_storage, duplicate groups, and attribute-inverted storage. Indexes built without force-remove support must be rebuilt to enable it.

Physical deletion repairs HGraph edges and fills removed slots with tail vectors, updating labels and graph references. MCI rebuilds both CSR directions using the same node-ID mapping, preserves unrelated soft-deletion markers, and repairs under-covered members of small affected cliques with Add’s incremental clique routine. It then flushes metadata and shrinks vector/graph storage. Repeated IDs in one request count once; missing IDs count zero. Explicitly requested soft-deleted IDs can also be physically removed. Subsequent Add starts at the compacted tail.

FORCE_REMOVE is serialized with Add, MARK_REMOVE, and Flush. Queries wait during ID moves and final shrinking; repair releases the force-remove lock while MCI remains unpublished, so queries may fall back to HGraph. This is not a transactional operation: deletions completed before an error may remain, and an unfinished companion is not published to fast search. CSR replacement itself commits only after allocation succeeds; temporary old/new buffers coexist during compaction. Allocator retention and IO block granularity mean RSS need not fall proportionally to index memory accounting.

MCI automatically merges incremental metadata into its two CSR arrays after 100 successful vector mutations, using one counter shared by Add and MARK_REMOVE. Add checks after each inserted point, including within a large batch. MARK_REMOVE projects and repairs the complete deletion batch before checking the threshold, so a large deletion batch compacts once at its end. Duplicate/missing removal IDs and failed insertions do not count; repair seeds do not count as new vectors. FORCE_REMOVE retains its mandatory end-of-batch compaction and resets the counter. Successful compaction resets the counter to zero; a new full build or load also resets this runtime-only counter. Below the threshold, queries and serialization still include delta. There is no public Flush interface and no change to the Index virtual interface for compaction.

Flush includes new delta cliques and members appended to base cliques, drops retired cliques and deleted members, and rebuilds the node-to-clique mapping with compact clique IDs. It clears the delta storage but preserves vector inner IDs and deletion markers. The operation is idempotent and does not rebuild HGraph or persist data to disk; use Serialize() for persistence.

Flush is serialized with Add/Remove. It holds an exclusive clique-storage lock while constructing and publishing the replacement, so searches may wait. Replacement buffers are allocated before publication; an allocation failure leaves the old clique representation intact. Automatic maintenance defers allocation failures without failing a completed Add/MARK_REMOVE and retries on the next successful mutation. This does not change FORCE_REMOVE’s failure semantics. Temporary memory includes both the old and new CSR. Do not retain clique IDs across a flush. Loading a validated compact CSR with no delta entries, empty clique rows, or deletion/retirement markers preserves the clean state, so its first Flush skips rebuilding the CSR. Other snapshots are conservatively compacted when flushed.

MCI search pins CSR, delta, and deletion masks with one shared lock per query and traverses them without copying membership lists. Contiguous FP32 vectors continue to use direct distance calculation after Add/Remove, before or after Flush; mci_raw_float_csr reports this path, including queries that traverse delta. Other vector layouts use the same traversal and candidate queue with their normal distance computer. Deletion filtering pins the deletion set once per MCI query, checks the user filter first, and avoids acquiring the deletion-set lock for every visited node.

Add/MARK_REMOVE may temporarily unpublish the companion, so concurrent queries still fall back to HGraph under the existing mutation semantics. This does not guarantee complete recall during a mutation; fallback results can be empty when the graph entry point has been deleted. Automatic compaction runs within that mutation; queries may wait for the clique storage lock. Fallback queries recheck candidate IDs against one deletion-set view before packing results. This removes old candidates deleted during traversal, including an old slot whose label has been re-added at a new slot. It does not make an entire concurrent search a transactional snapshot. If candidates are deleted during traversal, KNN fallback may return fewer than k results even when enough live vectors remain. Results are best-effort under concurrent mutations; there is no secondary fill pass, since another pass could encounter further mutations too.

The clique data is serialized inside the HGraph index. Loading the HGraph index restores the companion automatically.

GetStats() includes MCI quality fields such as:

• mci_has_index
• mci_total_nodes
• mci_covered_nodes
• mci_total_clique_count
• mci_retired_clique_count
• mci_inactive_node_count
• mci_total_membership_count
• mci_avg_membership_per_node
• mci_avg_clique_size
• mci_max_clique_size
• mci_memory_usage

Example

See examples/cpp/324_feature_hgraph_mci_companion.cpp for a minimal build and filtered-search flow.

Evaluation Notes

Development benchmark sources, scripts and raw results are not part of this PR; the field descriptions below document the CSV produced by that harness.

Reading results and validating

Five-stage runs protect evaluation top-k neighbors and retain the same truth. Random churn does not protect neighbors; each checkpoint selects live top-k from exact full-pool distance rankings. Do not mix their recall conclusions.

MiB = bytes / 1,048,576. Stage memory/timing repeats across ef rows; do not sum it. QPS is multithreaded throughput: 1000 / QPS is not per-request latency. CSV has neither latency percentiles nor per-stage RSS. Raw result files are not included in this PR. These measurements predate adaptation to newer main and are not a performance rerun of current PR HEAD.

make debug VSAG_ENABLE_TESTS=ON COMPILE_JOBS=12
build/tests/unittests '[mci],[LabelTable],RaBitQSplitDataCell serialize and methods'

Before this documentation update: targeted C++ tests passed 38 cases / 3,294 assertions; Python suites passed 10+1+3 tests, with the executable integration suites using a Debug benchmark for correctness. Review follow-up adds reverse-edge restoration and reload-mutation regressions. Full lint, full tests, and >=90% coverage verification are outstanding. Large-dataset snapshot reuse, ABI, serialization compatibility, and broader concurrent mutation require separate validation; targeted passes are not proof of production readiness.