ETD

• adaptive dimensionality
• BEIR
• dense retrieval
• document representation
• lagrangian relaxation
• matryoshka representation learning MRL
• memory-constrained indexing
• MS MARCO
• multiple-choice knapsack problem
• query-free estimator
• query-log estimator
• utility estimation

Dense retrieval represents each document as a vector and ranks documents by similarity in that space. Since one vector is stored per document, index memory grows with both collection size and representation width, and on large collections it becomes the binding deployment constraint. The usual response is to narrowthat width uniformly, which is feasible because representations can be trained so that their capacity is organised hierarchically: coarse information is concentrated in an initial portion of the vector and later components add refinement, so a shortened representation remains usable without retraining. This admits a possibility that uniform truncation leaves unused, namely that the width may be chosen per document rather than once for the whole collection.
This thesis investigates whether that freedom is worth exercising. Documentwise allocation is formalised as a corpus-level multiple-choice knapsack problem, in which every document is assigned exactly one representation profile, each profile carries an explicit per-document storage cost, and the total cost must satisfy a global memory budget while aggregate estimated utility is maximised. The principal difficulty is not the optimisation but the construction of its objective, since the utility of a reduced representation must be estimated offline, for every document and profile, without access to evaluation judgments. Two estimator families are compared: a query-log estimator, which measures relevance-weighted preservation of full-width scores over sampled demand and models unobserved documents explicitly, and a query-free estimator, which measures the norm of the components a reduced profile discards and so covers every document deterministically. The program is solved by Lagrangian relaxation with a deterministic repair procedure that restores feasibility.
The experimental study uses an encoder fine-tuned with Matryoshka Representation Learning over six nested widths, applied to the full MS MARCO passage collection and evaluated on TREC DL 2019 and 2020 and on BEIR/NQ. Each adaptive assignment is compared against the full index and against the strongest uniform index of equal or lower realised cost, so that memory rather than nominal dimensionality is the controlled variable. Ablations isolate the contributions of the similarity function, the residual normand the treatment of unobserved documents, while allocation and optimiser diagnostics are reported alongside effectiveness, so that outcomes can be attributed to the allocation, to the utility model, or to heterogeneous scoring.