Skip to content

feat: IVF index structure (opt-in for large codebases) #104

Description

@Lucas-Bur

What to build

Add an optional IVF (Inverted File Index) structure for faster search on large codebases. Instead of comparing the query against ALL vectors (O(n)), partition vectors into clusters at index time. At query time, find the nearest N clusters to the query, then brute-force only those clusters.

Decision: Opt-in for large codebases

  • Default: Brute force (current behavior). Exact results, fine for <50k vectors.
  • Opt-in: Enable via config.index.ivf.enabled: true or pix index --ivf.
  • Clustering: K-means with sqrt(n) clusters. Store centroids + cluster assignments per vector.
  • Query: Find nearest N centroids, search only those clusters.

Acceptance criteria

  • IVF index built at index time when enabled
  • Centroids stored in .pix/ivf-centroids.bin
  • Cluster assignments stored per vector in .pix/ivf-assignments.json
  • Query uses IVF when enabled, brute force when disabled
  • Configurable cluster count and search width
  • pix status shows IVF enabled/disabled
  • Adapter test verifies IVF search returns similar results to brute force
  • Performance test shows speedup on large index (>50k vectors)

Blocked by

None - can start immediately

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or requestready-for-agentFully specified, ready for an AFK agent

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions