# Test-Time Compute for Frozen Embedding Models through Agentic Program Search

arXiv: https://arxiv.org/abs/2605.11374 · HTML: https://mlsanity.com/paper/2605.11374/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 19 of its 38 references that are in the map.
- First posted on arXiv 12 May 2026.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)
- LLM agents and tool use / [Web, search, and research agents](https://mlsanity.com/agents/web-search-and-research-agents/)

## Builds on (most cited first, 19 of 19)

- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Qwen3 Embedding: Advancing Text Embedding and Reranking Through Foundation Models](https://mlsanity.com/paper/2506.05176/) (2025)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [NV-Embed: Improved Techniques for Training LLMs as Generalist Embedding Models](https://mlsanity.com/paper/2405.17428/) (2024)
- [Improving Text Embeddings with Large Language Models](https://mlsanity.com/paper/2401.00368/) (2023)
- [Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Models](https://mlsanity.com/paper/2408.00724/) (2024)
- [Fine-Tuning LLaMA for Multi-Stage Text Retrieval](https://mlsanity.com/paper/2310.08319/) (2023)
- [Generative Representational Instruction Tuning](https://mlsanity.com/paper/2402.09906/) (2024)
- [EmbeddingGemma: Powerful and Lightweight Text Representations](https://mlsanity.com/paper/2509.20354/) (2025)
- [Making Text Embedders Few-Shot Learners](https://mlsanity.com/paper/2409.15700/) (2024)
- [MetaEmbed: Scaling Multimodal Retrieval at Test-Time with Flexible Late Interaction](https://mlsanity.com/paper/2509.18095/) (2025)
- [jina-embeddings-v5-text: Task-Targeted Embedding Distillation](https://mlsanity.com/paper/2602.15547/) (2026)
- [Improving Query Representations for Dense Retrieval with Pseudo Relevance Feedback: A Reproducibility Study](https://mlsanity.com/paper/2112.06400/) (2021)
- [Guided Query Refinement: Multimodal Hybrid Retrieval with Test-Time Optimization](https://mlsanity.com/paper/2510.05038/) (2025)
- [Generative and Pseudo-Relevant Feedback for Sparse, Dense and Learned Sparse Retrieval](https://mlsanity.com/paper/2305.07477/) (2023)
- [Pseudo Relevance Feedback is Enough to Close the Gap Between Small and Large Dense Retrieval Models](https://mlsanity.com/paper/2503.14887/) (2025)
- [Generalized Pseudo-Relevance Feedback](https://mlsanity.com/paper/2510.25488/) (2025)
- [LLM-VPRF: Large Language Model Based Vector Pseudo Relevance Feedback](https://mlsanity.com/paper/2504.01448/) (2025)

## Abstract (arXiv)

Test-time compute is widely believed to benefit only large reasoning models, leaving small models with nothing to gain. We argue the opposite for dense retrieval, since modern small embedding models are distilled or adapted from large language model backbones and can inherit their latent test-time-compute potential. We ask how much retrieval quality a frozen embedding model gains at inference alone, with no auxiliary model and no parameters trained at deployment. An agentic loop in which a large language model writes programs over a frozen encoder API explores 144 candidates and yields twelve Pareto-optimal programs that trade inference compute for quality across cost ratios from c=1.2 to 14.7, every one improving nDCG@10 on all 14 discovery tasks. The programs use no trainable parameters and recover classical retrieval primitives, among them reciprocal rank fusion, the Fisher linear discriminant, Rocchio pseudo-relevance feedback, and sentence-level MaxSim. Applied unmodified to nineteen held-out tasks and three unseen encoder families, a single fixed program improves the majority of tasks, with a positive median DeltanDCG@10 and a 54 to 57% win-rate at c≥4, and the gains are largest on encoder families never seen during discovery. A matched-budget learned projection head trained on the same tasks does not transfer this way, improving in-domain retrieval by +0.20 to +0.25 nDCG@10 yet falling below baseline on every held-out encoder. Small embedding models therefore inherit usable test-time-compute potential, and a frozen encoder converts inference compute into retrieval gains that transfer to new corpora and encoders with no per-domain labels.