CrossQ: Task-Aligned Cross-Token Conditional Quantization for Late Interaction Retrieval
Rohit Kumar Salla, Manoj Saravanan, Ramya Manasa Amancherla
cs.IR
2026-06-11
CrossQ conditions ColBERT token codes on throwaway document context, trained for ranking. At 2 B/token, MS MARCO MRR@10 goes 0.359 to 0.369, ~64x smaller raw storage at 4 B/token.
Late-interaction retrievers such as ColBERT store a vector per document token and score a query by summing max-sim over query tokens. Quality is high. So is the index. Production systems often need a few bytes per token before the index fits in RAM.
PQ, OPQ, and residual quantizers minimize average reconstruction error. Late interaction does not care about the average. Only sparse winner tokens enter the score. Most tokens in a passage never win max-sim for any query in a batch, so uniform bits waste most of the budget. Reconstruction MSE correlates with MRR at about 0.3. Training for distortion trains the wrong thing.
CrossQ compresses documents only. Queries stay full precision, so quality gaps come from the index. Encoding follows ColBERT and ColBERTv2.
At indexing time a light, query-independent context vector h(D) conditions code selection, biasing bits toward tokens that are likelier to win. h(D) is then discarded. The store holds integer codes. The quantizer is additive residual codebooks with K=256 and M in {2,4,8} for 2/4/8 bytes per token.
Training aims at max-sim ranking:
Discrete codes use a straight-through estimator. Optional light fine-tuning unfreezes the last two Transformer blocks and the projection head so the retriever can absorb quantization noise without a full retrain.
MS MARCO, three seeds, matched nominal code budgets.
| Method | 2B MRR@10 | 2B R@10 | 4B MRR@10 | 8B MRR@10 |
| OPQ | 0.345 | 0.796 | 0.366 | 0.379 |
| Token-wise RQ (rank) | 0.359 | 0.811 | 0.371 | 0.387 |
| PLAID (candidate-matched ref.) | 0.357 | 0.812 | 0.381 | 0.389 |
| CrossQ | 0.369 | 0.826 | 0.386 | 0.395 |
| CrossQ + light FT | 0.374 | 0.831 | 0.392 | 0.399 |
At 2 B/token that is +0.010 MRR over the strongest footprint-matched baseline and +0.012 over PLAID. On a nine-dataset BEIR slice at 4 B/token, mean nDCG@10 moves from 0.387 to 0.396. With light fine-tuning at 8 B/token, CrossQ keeps about 98% of full-precision ColBERT MRR@10. Raw token storage at 4 B/token is about 64x smaller, about 61x with metadata, about 58x under conservative padding.
Ablation at 4 B/token: drop context and MRR falls 0.386 to 0.371, the largest single hit; drop listwise and it is 0.377; reconstruction only is 0.358. A param-matched no-context MLP recovers 0.001. Shuffled h(D) lands at 0.370. The gain is cross-token information, not the extra 131K parameters. Indexing throughput drops from 2,400 docs/s (PQ) to 1,850 (about 1.3x slower). Scoring 20,000 candidates is 3.6 ms p50 versus 3.2 ms for PQ.
Late interaction has been a storage problem. CrossQ reallocates bits inside a document toward tokens that tend to score, and it does not persist the context. For teams that cannot hold a full-precision ColBERT index and do not want to fall back to single-vector retrieval, 2 to 4 bytes per token becomes a usable band. Ranking losses beat another round of reconstruction tuning. The 0.28 to 0.41 correlation already says that.
This is document-side compression, not a new retriever. PLAID's routing stack was not retrained to each byte budget; the paper treats it as a system reference, not a strict footprint match.
Max-sim can still flip at extreme compression. The training signal is built for ColBERT-style max-sim; other operators need new losses. Queries are uncompressed. Indexing is about 30% slower, which hurts high-churn corpora. The teacher is the same backbone at full precision, not a cross-encoder, so distillation is capped by that teacher. Social risks match ordinary late-interaction retrieval: cheaper high-quality ranking is easier to deploy in biased or surveillance settings.