Project 2: NanoMem

Is it a bug in the starter Colab?

We’ve aimed to keep the project page and notebook consistent. The project page gives the full requirements and grading; the notebook provides compact guidance, function contracts, and starter code.

The supplied helpers support the standard datasets through T87; you still implement the assigned components. For T93–T100, expect to adapt or replace the loading and indexing helpers to meet the larger-data and memory requirements. Test changes on a small subset before scaling up.

You’re welcome to adapt the starter code within the project requirements. If something seems inconsistent or buggy, check the project page and ask privately on Ed; include the error and a small reproducible example for bugs. Note important assumptions in your notebook so we can take them into account when reviewing your work.

What does the installation cell provide?

It installs the Python dependencies, including sqlite-vec. The SQLite connection helper checks FTS5 and extension support. If your local Python lacks either, use the supplied Colab setup or a Python build with both enabled. No cloud credits or paid API is required.

What should I rerun after changing the dataset size?

Choose the setting in What to index and how it’s scored, then rerun the setup and benchmark execution cells. Save a notebook copy before replacing outputs you need to retain. Tiers 93 and 100 require adapting the loading and retrieval code to fit the memory budget.

Q: What is a posting list?

For each term, a list of (doc_id, term_frequency) pairs. Optionally also positions if you want phrase queries. When a query comes in, you look up the posting list for each query term and combine them. A dict[str, list[tuple]] works fine for the in-memory representation.

Why might my BM25 results differ from FTS5?

You may use or modify the supplied tokenizer. It keeps verify_jwt as one token; FTS5’s default tokenizer splits it. Use the same tokenizer for your documents and queries, check your BM25 formula, and investigate missed results. Report your tokenizer choice. A recall gap alone is not a grading failure.

IDF(t) = log(1 + (N - df(t) + 0.5) / (df(t) + 0.5))
score(d,q) = sum over query terms t:
  IDF(t) * tf(t,d) * (k1 + 1) /
  (tf(t,d) + k1 * (1 - b + b * len(d) / avgdl))

How should I tune LSH recall and latency?

Start with:

• n_bands = 60: the number of hash tables.
• bits_per_band = 3: the number of hash bits defining each bucket.
• Candidate budget = 1,000: the maximum candidates scored with exact cosine similarity.

Rank candidates by matching-band count before applying the budget. Change one setting at a time and measure recall and latency. These starting settings do not guarantee a particular recall.

What is RRF?

Reciprocal Rank Fusion (RRF) combines the BM25 and vector-search rankings. Each document receives 1 / (60 + rank) from each list in which it appears, with ranks starting at 1. Add these contributions and return the documents with the highest totals. A document missing from a list contributes zero from that list.

Q: My hybrid is worse than pure BM25 on code. Is that wrong?

That can happen. Equal-weight rank fusion may weaken a strong result from one method. Compare BM25, LSH, RRF, and your custom fusion on the same queries, then explain what you observe. No method is required to win on either dataset.

What can I try for custom fusion?

Choose a rule that differs from standard RRF. For example:

• Weighted scores: normalize BM25 and vector scores, then combine them with chosen weights. Handle empty lists and equal scores.
• Agreement boost: increase a document’s fused score when both methods rank it first.

Explain your rule in custom_fusion and compare it with RRF on the same queries. It does not have to outperform RRF.

How do I save work between Colab sessions?

Checkpoints are optional and recommended from Phase 1 onward; they are not required for Phase 0. Uncomment and run the Drive checkpoint cell after Setup, then approve access to Google Drive.

# Optional: uncomment this cell to keep checkpoints in Google Drive.
# Recommended from Phase 1 onward; not required for Phase 0.
# Run AFTER Setup and BEFORE building indexes or computing embeddings.
# from pathlib import Path
# from google.colab import drive
# drive.mount("/content/drive")
# CHECKPOINT_DIR = Path("/content/drive/MyDrive/nanomem_checkpoints")
# CACHE_DIR = CHECKPOINT_DIR / "embeddings"
# INDEX_DIR = CHECKPOINT_DIR / "indexes"
# for folder in (CACHE_DIR, INDEX_DIR):
#     folder.mkdir(parents=True, exist_ok=True)
# print("Checkpoint folder:", CHECKPOINT_DIR)

• Embeddings: the supplied cache calls write to CACHE_DIR.
• Indexes and results: save your index files under INDEX_DIR and benchmark outputs under CHECKPOINT_DIR using your implementation.
• Next session: run Setup, run the checkpoint cell again, and reload your saved files. Re-running Setup resets the paths to local storage.
• Long runs: save numbered embedding chunks and record the last completed document so you can resume. Time a small batch before starting.

Check that files appear in MyDrive/nanomem_checkpoints and that Drive has enough space. Enabling checkpoints does not move existing local files or save objects in memory.

Without Drive checkpoints, embeddings go to bench_cache/ and indexes to nanomem_index/. Downloads use the Hugging Face cache. Colab’s local files can disappear when the runtime resets; saving the notebook does not save them.

Which data do I use for Tier 93?

Use the supplied Tier 93 loader for the fixed 5 GB subset of MS MARCO v1 documents and its development/final queries. Everyone uses the same subset; do not choose your own.

This is the document corpus, not the passage corpus used at lower tiers. Their IDs and relevance labels differ. Process documents in bounded batches to stay within the memory limit.

If you split documents into chunks, retain their document IDs and merge chunk matches back into document results before scoring. Apply the same text preparation to NanoMem and the SQLite references.

Why did recall change after partitioning?

Check candidate limits and the merge. Cosine scores on normalized embeddings are comparable across partitions. BM25 needs corpus-wide document frequencies and average document length. Combining partition-local ranks can change the results; measure that effect.

What memory evidence should I save?

Save the live-component breakdown for build and query runs, the sampled RSS logs from MemoryBudget, and the final benchmark table. Include the active partition, model, shared state, and temporary buffers. Explain allocations the helper does not count.

RSS can include memory retained by Python after objects are released. Report it separately from the live working set. The helper reports memory; it does not enforce the limit.

How can I stay within the memory limit?

• Embed in smaller batches and save them to disk.
• Release each partition before loading the next.
• Bound candidate lists and other temporary arrays.
• Release the embedding model when it is no longer needed.

How could I build and query disk partitions?

One approach to meeting the memory limit:

1. Stream documents, embed bounded batches, and assign each document to a disk partition using a stable hash of its ID.
2. Load one partition, build and save its indexes, then release it.
3. At query time, visit one partition at a time and keep only the candidates needed for the final top-K.
4. Measure live memory and explain the extra reads using the M3 I/O cost equations.

Choose partition sizes from measurements, allowing room for shared state and temporary buffers. If you use this approach, the partition writer, index persistence, and bounded merge are student work.

What makes a useful AI-use example?

State what AI suggested, how you checked it, and what you changed. For example: “AI suggested timing one query. I repeated the benchmark and reported median and p95 latency because individual runs varied.” Use the Phase 6 checklist for the required writeup.