Test-Time Compute for Dense Retrieval: Agentic Program Generation with Frozen Embedding Models

Test-time compute is widely believed to benefit only large reasoning models. We show it also helps small embedding models. Since modern embedding models are distilled from LLM backbones, a frozen encoder should benefit from extra inference compute without retraining. An agentic program-search loop explores 144 candidate programs over a frozen encoder API and produces twelve Pareto-optimal programs that trade extra inference compute for retrieval quality. The search independently rediscovers Rocchio pseudo-relevance feedback, ColBERT-style MaxSim at sentence granularity, reciprocal rank fusion, and the Fisher linear discriminant, all without trainable parameters or external models. Every frontier program improves nDCG@10 over the frozen baseline on all 14 tasks used during program search. Generalization is validated separately: a single fixed program, selected from the discovery frontier before any held-out evaluation, improves nDCG@10 on 61% of model-task pairs across three unseen encoder families and nineteen held-out retrieval tasks, without any per-task selection.