Technical Summary: CAMI – Practical Cost-Aware Agent-Guided Multi-Indexing for Semantic Retrieval

1. Problem Statement

Modern Retrieval-Augmented Generation (RAG) systems increasingly rely on Multi-Index Retrieval to mitigate the lexical and structural mismatch between user queries and source documents. This approach involves generating Enriched Data Representations (EDRs)—such as synthetic summaries, paraphrases, or questions—using Large Language Models (LLMs) during the ingestion phase. These EDRs are indexed alongside the base text to improve recall.

However, this strategy introduces a combinatorial cost bottleneck:

1. Search Space Complexity: The space of possible EDR types (e.g., summary vs. mindmap) paired with generator models (e.g., Qwen-8B vs. Llama-70B) grows exponentially.
2. Evaluation Cost: Exhaustively evaluating every possible portfolio (combination of EDRs and models) on a full corpus is financially and computationally prohibitive. The cost of searching scales linearly with corpus size, often exceeding the cost of simply deploying a suboptimal index.
3. Static Limitations: Existing pipelines often rely on fixed, static catalogs of enrichment templates that may not align with specific corpus characteristics, leading to wasted construction costs without guaranteed recall improvements.

The core challenge is to identify the Pareto-optimal frontier of multi-index configurations that maximize retrieval recall while minimizing structural deployment cost, all within a strict optimization budget.

2. Methodology: The CAMI Framework

The authors propose CAMI (Cost-Aware Multi-Indexing), a framework that formalizes multi-index construction as a budgeted, multi-objective portfolio selection problem. CAMI operates in two primary phases:

Phase 1: Agentic EDR Discovery

Instead of relying on a static catalog, CAMI employs an agentic discovery phase. An LLM-based agent proposes corpus-specific EDR prompt templates based on seed query-evidence pairs and corpus context.

• Governed Proposal: The agent generates templates (e.g., "Procedural Extraction" for technical manuals) which are validated, schema-checked, and "frozen" before the search begins.
• Budget Accounting: Token usage for the discovery agent is charged to the search budget, ensuring dynamic expansion does not bypass financial constraints.

Phase 2: The AACA Search Algorithm

The core optimization engine is AACA (Atomic-unit Acquisition + Closure + MO-ASHA). It treats the search space not as monolithic configurations but as composable atomic units (an EDR type paired with a specific generator model).

• Atomic Unit Definition: An atomic unit $a = (e, m)$ is a specific enrichment type $e$ and model $m$. A portfolio is a set of active atomic units.
• Multi-Fidelity Evaluation: To bound costs, CAMI evaluates configurations on nested query subsets ($Q_0 \subset Q_1 \subset \dots \subset Q_L$).
  • Fidelity 0: Small, representative subsets used for initial screening.
  • Higher Fidelities: Larger subsets used for confirmation.
  • Representativeness: Subsets are sampled via topic-aware stratification to ensure they approximate the full query distribution.
• Three-Action Loop: The algorithm iteratively selects one of three actions:
  1. Acquisition: An LLM-based selector proposes new atomic units (novelty/synergy driven) to expand the pool.
  2. Closure: The system recombines previously validated atomic units from the current fidelity pool to form new portfolios. This exploits the fact that if Unit A and Unit B are good individually, their combination is worth testing without re-evaluating them from scratch.
  3. Promotion: Configurations are promoted to higher fidelities based on a Multi-Objective Asynchronous Successive Halving (MO-ASHA) schedule.
• Confidence-Aware Promotion: Promotions use an Upper Confidence Bound (UCB) ranking to balance empirical performance with uncertainty (standard error). This prevents promising configurations from being prematurely discarded due to noise in small query subsets.
• Cost Semantics: CAMI distinguishes between:
  • Runtime Uncached Spend ($C_{uncached}$): The actual dollar cost incurred during the search (governed by the budget $B_{search}$).
  • Structural Cost ($C_{struct}$): The theoretical cost to deploy a final index, calculated by summing the nominal costs of its atomic units (allowing for caching reuse).

3. Key Contributions

The paper outlines four primary contributions:

1. Formalization: Retrieval enrichment is framed as a budgeted Pareto-frontier discovery problem with explicit cost semantics, separating construction costs from search optimization costs.
2. AACA Optimizer: Introduction of an optimizer that bridges MO-ASHA budget controls with fidelity-local closure, enabling the computational reuse of EDR-model pairs during the search process.
3. Agentic Discovery: Integration of an LLM-guided phase to generate corpus-specific EDR templates, moving beyond static catalogs while adhering to budget constraints.
4. Operationalization: A practical, end-to-end RAG ingestion pipeline evaluated on diverse public datasets, demonstrating significant recall improvements with reduced search budgets.

4. Experimental Results

The framework was evaluated on five datasets: BRIGHT-ES (Earth Science), BRIGHT-Econ (Economics), BRIGHT-SO (Stack Overflow), StatCanDialogueRetrieval, and NQTables.

• Performance vs. Random Search: CAMI (specifically the AACA optimizer) consistently outperformed a budget-matched random search baseline. Across all datasets, it achieved an aggregate 92% win rate (92 wins vs. 8 losses) in identifying superior Recall@10 portfolios.
• Recall Gains: CAMI identified portfolios that improved Recall@10 by up to 9.4% over content-only baselines (e.g., StatCan dataset).
• Search Efficiency: CAMI identified high-recall portfolios using up to 5x less budget compared to random search baselines. In specific cases (e.g., StatCan), it reached near-optimal configurations using less than 20% of the cost required for an exhaustive grid search.
• Ablation Studies:
  • Uncertainty-Aware Ranking: Using UCB for promotion significantly improved throughput compared to mean-only ranking, preventing the premature elimination of high-potential configurations on noisy small subsets.
  • Closure vs. Discovery: While LLM-guided discovery expanded the candidate library, the fidelity-local closure mechanism (recombining proven atoms) was the primary driver of long-term search efficiency.
  • Dynamic vs. Static: Agent-discovered EDRs (e.g., causal_links for Economics, function_names for Stack Overflow) frequently appeared in the final Pareto-optimal portfolios, outperforming static seed catalogs in both cost and quality.

5. Significance and Claims

The paper claims that CAMI fundamentally changes the design of multi-index retrieval systems by shifting from static, heuristic-driven enrichment to evidence-driven, corpus-adaptive optimization.

• Practicality: By decoupling the search budget from the total corpus size and leveraging atomic recombination, CAMI makes the optimization of complex RAG pipelines feasible in real production scenarios where exhaustive evaluation is impossible.
• Cost-Quality Trade-off: The framework provides a rigorous method to navigate the recall-cost Pareto frontier, ensuring that practitioners can select configurations that offer the best retrieval quality for a specific deployment budget.
• Scalability: The use of multi-fidelity evaluation and caching-aware budget tracking allows the system to scale to large corpora without incurring prohibitive token costs during the configuration search phase.

The authors acknowledge limitations, noting that the approach relies on the assumption that atomic units are additive (ignoring complex non-additive interactions) and that performance depends on the accuracy of proxy subsets (fidelity subsets) in reflecting full-corpus behavior. Future work is suggested to model stronger non-additive interactions and improve promotion stopping rules.