AdaGReS:Adaptive Greedy Context Selection via Redundancy-Aware Scoring for Token-Budgeted RAG

Chao Peng, Bin Wang, Zhilei Long, Jinfang Sheng

TL;DR

Standard Retrieval-Augmented Generation (RAG) often wastes its limited context window on redundant or near-duplicate information. AdaGReS solves this by using a redundancy-aware scoring function and a greedy selection algorithm that adaptively balances relevance and diversity. By automatically calculating the optimal trade-off based on the candidate pool's statistics, it ensures LLMs receive the most informative, non-repetitive context possible.

What Problem Does This Paper Address?

In a typical RAG pipeline, a retriever pulls the "top-k" most relevant chunks from a database to help an LLM answer a query. However, "most relevant" often translates to "most similar to the query," which frequently results in a set of chunks that all say the same thing.

This redundancy creates two major issues:

  1. Wasted Token Budget: LLMs have a finite context window (and tokens cost money/latency). Filling that window with five versions of the same fact prevents the model from seeing other necessary evidence.
  2. Degraded Reasoning: If a multi-hop question requires three different pieces of information, but the retriever returns three versions of the first piece, the LLM will likely fail or hallucinate.

Existing solutions like Maximal Marginal Relevance (MMR) exist, but they usually require manual tuning of a "diversity" hyperparameter ($\beta$) that varies wildly depending on the query and the dataset.

Methods

The authors introduce AdaGReS (Adaptive Greedy Context Selection), which consists of three main pillars:

  1. A Set-Level Objective Function: Instead of scoring chunks individually, AdaGReS optimizes a set $C$ using the formula: $$F(q, C) = \alpha \cdot \text{Relevance}(q, C) - \beta \cdot \text{Redundancy}(C)$$ This explicitly penalizes the score if the selected chunks are too similar to each other.

  2. Adaptive $\beta$ Calibration: This is the core innovation. Instead of making users guess the value of $\beta$, the authors derived a closed-form solution. By analyzing the average length, relevance, and redundancy of the top-N candidate pool, the system automatically calculates a $\beta$ that balances the trade-off for that specific query and token budget.

  3. Greedy Selection with Guarantees: Finding the absolute best subset of chunks is an NP-hard problem. AdaGReS uses a greedy algorithm—picking the chunk that offers the highest "marginal gain" until the token budget is full.

Datasets

The researchers evaluated AdaGReS on two distinct types of data:

  • Natural Questions (NQ): A standard open-domain dataset based on Google searches and Wikipedia. This represents a "normal" redundancy environment.
  • Biomedical (Drug) Corpus: A proprietary dataset of pharmaceutical documents. This is a "high-redundancy" environment where many documents describe the same drugs or mechanisms in slightly different ways, making it a perfect stress test for deduplication.

Key Insights and Ideas

  • The "Approximate Submodularity" Breakthrough: In mathematics, "submodular" functions have a "diminishing returns" property that makes greedy algorithms very effective. While the authors' objective function isn't strictly submodular (because of the subtraction), they proved it is $\epsilon$-approximate submodular. This provides a theoretical safety net, guaranteeing that their greedy selection is mathematically "near-optimal."
  • Context Statistics as a Signal: The paper shows that you don't need a separate training phase to tune diversity. The "typical" similarity between chunks in your current retrieval pool is enough information to set the redundancy penalty dynamically.
  • Redundancy as a Hallucination Driver: The authors highlight that "pseudo-relevance"—where a model sees the same fact repeated and assumes it's the only relevant fact—is a major contributor to RAG hallucinations.

Key Results

  • Better Context Quality: Using Intersection-over-Union (IOU) (a metric measuring how well the selected chunks overlap with the "gold standard" answer segments), AdaGReS consistently outperformed standard top-k retrieval.
  • Significant Gains in High-Redundancy Tasks: On the biomedical dataset, AdaGReS improved IOU by 8 to 15 percentage points compared to the baseline.
  • Robustness: The adaptive $\beta$ mechanism allowed the system to maintain high performance across different token budgets without any manual reconfiguration.
  • Qualitative Improvement: In human evaluations (and Table 1 in the paper), AdaGReS-retrieved contexts were more concise and covered more functional aspects of the query (e.g., explaining a MAF sensor) compared to the repetitive, bulky outputs of the baseline.

Limitations and Future Work

  • Non-Uniform Distributions: The authors note that if a candidate pool has a very "skewed" distribution (e.g., a tiny cluster of extreme duplicates and a vast sea of unique chunks), the greedy strategy might occasionally fall short of the ideal balance.
  • Learning-Based Calibration: While the current closed-form solution is efficient, the authors suggest that future versions could use reinforcement learning to "learn" even better $\beta$ values based on actual downstream LLM performance.
  • Refined Diversity Modeling: The current model uses pairwise cosine similarity; future work could explore more complex semantic diversity metrics.

Summary updated

Abstract

Retrieval-augmented generation (RAG) is highly sensitive to the quality of selected context, yet standard top-k retrieval often returns redundant or near-duplicate chunks that waste token budget and degrade downstream generation. We present AdaGReS, a redundancy-aware context selection framework for token-budgeted RAG that optimizes a set-level objective combining query-chunk relevance and intra-set redundancy penalties. AdaGReS performs greedy selection under a token-budget constraint using marginal gains derived from the objective, and introduces a closed-form, instance-adaptive calibration of the relevance-redundancy trade-off parameter to eliminate manual tuning and adapt to candidate-pool statistics and budget limits. We further provide a theoretical analysis showing that the proposed objective exhibits epsilon-approximate submodularity under practical embedding similarity conditions, yielding near-optimality guarantees for greedy selection. Experiments on open-domain question answering (Natural Questions) and a high-redundancy biomedical (drug) corpus demonstrate consistent improvements in redundancy control and context quality, translating to better end-to-end answer quality and robustness across settings.
BibTeX
@misc{peng2025adagres,
  author = {Chao Peng and Bin Wang and Zhilei Long and Jinfang Sheng},
  title = {{AdaGReS:Adaptive Greedy Context Selection via Redundancy-Aware Scoring for Token-Budgeted RAG}},
  year = {2025},
  eprint = {2512.25052},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2512.25052},
}
Figure