Aligning the Query Space: Greedy Information Projection for Language Model Data Selection

arXiv:2603.13790 · cs.LG, cs.CL · Submitted 2026-03-14 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Aligning the Query Space".

Jane: Greedy Information Projection (GIP) presents a principled framework for selecting training examples for large language model fine-tuning by casting data selection as maximizing mutual information between selected examples and task-specific…

Tom: First, who's behind it and why it matters.

Title and authors: Tom: Welcome back. We're talking about a paper today called "Aligning the Query Space: Greedy Information Projection for Language Model Data Selection." It looks like it’s tackling one of the biggest headaches in fine-tuning large models, which is figuring out which examples to pick from a massive dataset to make the model smarter efficiently.

Jane: That's right. The authors introduce something called Greedy Information Projection, or GIP, and they frame data selection as maximizing mutual information between the examples we select and some task-specific query signals that tell us what kind of data we need.

Lu: It’s a principled way to do it because it sets up a theoretical framework where you’re not just picking things randomly but optimizing for both the quality of the data and how diverse that selection is, all in one objective.

Meng: So, before we get into the details, what exactly is this mutual information they are maximizing? Is it just a simple measure of how much related stuff we're getting?

Tom: It’s more than just simple relatedness. They define this as maximizing mutual information between Gaussians scaled by data and query embeddings, which is a mathematical way to capture the relationship between the training examples and the task signals.

Jane: And that’s what makes it powerful because it naturally balances quality—picking things that are highly relevant—with diversity—making sure we don't just pick ten very similar examples and miss important angles.

Lu: The geometric interpretation is really interesting here, because they show that optimizing this score is the same as maximizing the projection of the query embedding matrix onto the span of those selected data embeddings.

Meng: So, if I understand that right, it means we’re looking for a set of data examples whose combined influence best represents the direction of what our model needs to learn next?

Tom: Exactly. And they explain this geometrically by saying it’s equivalent to minimizing the volume, or the determinant, of those score embeddings projected onto the null space of the selected data embeddings.

Jane: That minimization of volume is a clever way to encourage diversity because it pushes us away from directions that are already well-covered by our current selection.

Lu: They also developed a fast greedy matching pursuit procedure for this, which is what makes it practical when you have huge datasets, because it scales linearly with the total size of available data in practice.

Meng: Linear scaling sounds really good for engineering purposes. How does that translate practically when we’re looking at actual fine-tuning budgets?

Tom: Well, they show on instruction-following and mathematical reasoning benchmarks like GSM8K that GIP can select small subsets that match full-data fine-tuning performance using as little as ten percent to twenty percent of the training data <ref:2603.13790#pg2>.

Jane: That kind of efficiency is what makes this work for real applications, showing substantial data efficiency gains over many existing methods in the field.

Title and authors: Lu: They also have two specific variants they tested, MP+MA and MP+SC; one is strongest on instruction-following metrics, and the other achieves strong reasoning performance without needing any external supervision.

Meng: That’s helpful because it means we can tailor our selection strategy depending on whether we prioritize following instructions or solving complex math problems without needing a separate validation set for those specific tasks.

Tom: And they mentioned that this framework is quite robust to embedding noise during the data selection process, meaning even if your embeddings aren't perfectly clean, the intersection-over-union of selected subsets stays high.

Jane: That stability is crucial because real-world data embeddings are often messy, and if the selection method breaks easily with small changes in noise, it’s not really useful in production.

Lu: They also showed that for example on GSM8K accuracy, using ten percent of the training data can get you to forty-five percent accuracy on Mistral-7B compared to only two point five percent data which yields about thirty-five percent accuracy <ref:2603.13790#pg2>.

Meng: That comparison really highlights how much information is packed into those smaller subsets, and it gives a concrete picture of the trade-off they’re solving between size and performance.

Tom: So, to wrap up this paper, GIP offers a unified, information-theoretic approach where you maximize mutual information between your data and query signals to get efficient training sets that often match or exceed full-dataset performance using only a fraction of the required data.

Jane: It’s a very practical method because it doesn't require gradients or external validation sets for its selection process, which keeps the operational friction low while still achieving good results across different benchmarks.

Lu: The two complementary selection variants, MP+MA and MP+SC, demonstrate effectiveness across instruction-tuning and mathematical reasoning tasks by balancing quality signals derived from external assessments with the internal geometry of the data embeddings.

Meng: For me, what’s most compelling is that this approach gives us a clear way to cut down on the massive amounts of data we have to process before we even start training.

Tom: It does. So, as we wrap up this talk on "Aligning the Query Space: Greedy Information Projection for Language Model Data Selection," GIP provides a principled framework for choosing training examples that matches or exceeds full-dataset performance with much less data.

Jane: It’s a very practical method that balances quality and diversity through mutual information, offering efficiency without the need for extra supervision or complicated gradient setups.

Lu: The core idea is using geometric projections to understand how selecting data influences the model's learning path in a way that maximizes both what we know and what we don't know yet.

Meng: For implementation, it’s fast enough to handle large datasets in a way that fits within realistic training budgets, which is exactly what engineers need to see.

Tom: That’s all the time we have for today on this paper. We’ll be back next time with something new from arXiv.

The paper's summary: Tom: So, to recap, this paper is about using mutual information between your training data and the specific signals you’re asking for to pick exactly which examples you need from a huge dataset for fine-tuning an AI model.

Jane: It basically turns picking data into a math problem where the goal is to maximize how much information that small selection holds about what the model actually needs to learn next.

Tom: Right, and the authors show that this isn't just some abstract idea, they give it a solid theoretical foundation using Gaussian projections and some geometric ideas about projecting vectors onto different spaces.

Jane: And what’s really cool is how they’ve packaged this complex selection process into a fast algorithm called Greedy Matching Pursuit, which actually scales nicely when you have millions of data points to sort through.

Tom: The results are pretty impressive on instruction-following and math reasoning tasks, showing that you can often hit performance levels that used to require training on the entire dataset using just a small fraction of it.

Jane: And they give us two specific ways to use this, one variant for when you want strong instruction following and another for getting good reasoning scores without needing any extra validation sets.

Tom: It’s pretty neat because it doesn't need gradients or external validation sets to select the data, which makes it way less friction for actually using in a real training pipeline.

Jane: That stability against noise in the embeddings is also a big deal, meaning even if your data representation isn't perfect, the selection method still holds up pretty well.

Tom: So this moves data selection away from just picking random samples or looking at simple frequency counts and toward this more principled approach based on how information flows between the training material and the task objectives.

Jane: It really shows that we can use information theory to make these large model fine-tuning choices much more strategic, balancing how good the data is with how diverse it is.

Tom: But what does this mean for us in terms of building better models overall? Does this just make training faster, or does it fundamentally change how we think about what makes a dataset 'good' for a specific task?

The paper's improvements: Tom: So, we just talked about how GIP selects data by maximizing mutual information between the examples and the task signals, but now let’s look at what the authors suggest they could do next to make it even better.

Jane: They point out that while their greedy matching pursuit algorithm is fast, there are still ways to refine that process so it handles even bigger datasets or more complex signal requirements without slowing down too much.

Tom: I think they focus on making the projection step more adaptive, meaning the way we project the query embedding onto the data span could change dynamically based on how much data we’ve already picked.

Jane: That sounds like they want to move from a fixed selection strategy to something that learns how much more information it needs at each stage of selection.

Tom: And I see them mentioning using different scaling factors for the Gaussian projections, which could help tune the trade-off between selecting high-quality examples versus ensuring you get enough diversity.

Jane: That’s a nice touch because it acknowledges that sometimes you want to be super picky about quality, and other times you need to broaden your search space.

Tom: It sounds like they are looking into how to integrate those different scaling factors more smoothly into the greedy step so the algorithm doesn't get stuck in one kind of selection loop.

Jane: And I wonder if this refinement could help bridge that gap between theoretical performance and what’s actually achievable when you have massive, messy, real-world datasets.

Tom: Exactly, because we saw the results are great on benchmarks, but the real world is way noisier than those clean test sets.

Jane: So they're basically looking for ways to make this mathematical framework more robust so it doesn't break when you introduce the kind of real-world embedding noise we know is always there.

Tom: It makes sense, because if the selection process itself is sensitive to small changes in the input data, then that whole efficiency gain gets wiped out quickly.

Jane: And I think if they can stabilize that selection step, it opens up a lot more doors for using this framework on proprietary datasets where you don't have perfect control over every single embedding.

Tom: It shifts the focus from just getting a good initial subset to building a selection method that is inherently stable and adaptive, which is a big step toward making this technology truly production-ready.

Conclusion: Tom: So we've gone through how Greedy Information Projection tackles data selection by maximizing mutual information between the examples and the task queries, and now we’re wrapping up with what this all means for us.

Jane: This paper shows that we can be much smarter about which training examples to use, moving beyond just picking things randomly or using simple metrics.

Tom: It gives us a principled way to balance getting the highest quality data with making sure our selection covers a wide enough range of the necessary information for the AI model.

Jane: The practical takeaway is that we can achieve performance levels that used to require massive datasets using only about twenty percent of what we need.

Lu: From a theoretical standpoint, this suggests that the structure of the data itself holds much richer information about what an AI needs than just raw volume does.

Meng: For me, this means less time spent sifting through mountains of irrelevant data before I can even start my fine-tuning runs.

Lalam: It’s really exciting because it means our future models can be built with a much tighter, more intentional set of knowledge, which should lead to a more focused and useful culture for people interacting with the AI.

Tom: The two variants they found, MP+MA and MP+SC, show that we can tailor this selection process depending on whether we’re focusing on instruction following or deeper reasoning skills.

Jane: And the robustness against noise is important because it means this isn't just a lab trick; it works even when your data embeddings are a bit messy in the real world.

Lu: I think the geometric interpretation they used—minimizing volume to encourage diversity—is what gives this framework its real power for exploring the AI's potential space.

Tom: So, as we wrap up this talk on "Aligning the Query Space: Greedy Information Projection for Language Model Data Selection," GIP gives us a concrete tool to make our fine-tuning decisions much more informed and efficient.

Jane: It’s a very practical method that balances quality and diversity through mutual information, offering efficiency without needing complicated gradient setups or external validation sets.

Meng: The linear scaling with data size is what keeps this from becoming too slow when we actually try to implement it in a big system.

Lalam: This approach allows the AI to learn more effectively by focusing its energy on the most relevant pieces of information first, which really enhances how it understands and responds to human intent.

Tom: We’ve seen how powerful this selection framework is, but we also know that data quality always matters a lot in these systems.

Jane: Next time we look at papers like this, we should keep an eye on how researchers adapt these greedy approaches to handle even more complex multimodal inputs.

Victor Ye Dong, Kuan-Yun Lee

Microsoft

cs.LG, cs.CL

Submitted: 2026-03-14

Updated: 2026-10-04

Code: https://github.com/tatsu-lab/alpaca_eval

Importance score: 89/100

The gist: Greedy Information Projection (GIP) presents a principled framework for selecting training examples for large language model fine-tuning by casting data selection as maximizing mutual information

Key concepts

Mutual Information Maximization
The core idea is to find a subset of training data that has the highest mutual information with task-specific query signals. This ensures the selected examples are highly relevant to what the model needs to learn for a specific task, effectively balancing quality and diversity in data selection.
Gaussian Projections
The framework uses Gaussian projections derived from data and query embeddings to formulate the selection objective. Optimizing this projection is equivalent to finding a subset of data that best represents the space spanned by the query signals, guiding the selection process geometrically.
Greedy Matching Pursuit (MP)
To solve the complex optimization problem efficiently for large datasets, a Greedy MP algorithm is used. This iterative approach selects data points one by one by minimizing residual gain against all query embeddings at each step, allowing for fast and scalable data selection under budget constraints.

Terminology

Summary

Greedy Information Projection (GIP) presents a principled framework for selecting training examples for large language model fine-tuning by casting data selection as maximizing mutual information between selected examples and task-specific query signals, which naturally balances quality and diversity.

Principled Theoretical Formulation

The framework casts the data selection problem as maximization of mutual information between Gaussians scaled by data and query embeddings

The objective is defined using both data and query embeddings

Optimizing this score is equivalent to maximizing the projection of the query embedding matrix onto the span of the selected data, which provides a geometric explanation for the co-emergence of quality and diversity

This objective is formulated using Gaussian projections where ZQ and ZFS are constructed from data and query embeddings

Geometric Interpretation and Optimization

The mutual information between ZQ and ZFS is given by a closed-form expression involving determinants

Theorem 1 states that maximizing this mutual information is equivalent to optimizing arg max S I(ZQ;ZFS) = arg min S det Q⊤I − FS(F⊤S FS)−1F⊤S Q

An intuitive interpretation of equation 3.4 is that the matrix PS:= I − FS(F⊤S FS)−1F⊤S projects Q onto the null space of FS, minimizing the volume of Q after projection, which encourages both diversity and quality

Efficient Approximation Algorithms

To solve the complex optimization problem efficiently for large datasets, a greedy matching pursuit (MP) approximation algorithm is developed

The Greedy MP approach scales linearly with the total size of available data in practice, enabling data selection under realistic budget constraints

The algorithm minimizes residual gain across all query embeddings at each step to select the best candidate, defined by st+1 = arg max s∈[m]/St Xn i=1 (r⊤i fs)2

Strong Empirical Results

On instruction-tuning and mathematical reasoning datasets like MT-Bench, BBH, and GSM8K, GIP achieves substantial data efficiency gains

Across these benchmarks, GIP often approaches full-dataset performance using only 1–20% of the training data

The two variants are complementary: MP+MA is strongest on instruction-following metrics while MP+SC achieves strong reasoning performance without external supervision

Robustness and Practical Considerations

The framework is robust to embedding noise; intersection-over-union (IoU) of selected subsets remains high even under strong noise levels, suggesting the practical stability of the information projection framework

The Gram matrix computation is amortized across multiple selection runs with different budgets or scoring signals, and the selection phase exhibits near-linear scaling with k

Conclusion

Greedy Information Projection (GIP) provides a unified, information-theoretic approach to data selection that maximizes mutual information between data and query signals, leading to efficient training subsets that match or exceed full-dataset performance using only a fraction of the required data

This method is practical as it requires no gradients or external validation sets, offering strictly lower operational friction while matching or exceeding downstream performance across various benchmarks

The two complementary selection variants, MP+MA and MP+SC, demonstrate effectiveness across instruction-tuning and mathematical reasoning tasks by balancing quality signals derived from external assessments and internal data geometry

The gist

Greedy Information Projection (GIP) presents a principled framework for selecting training examples for large language model fine-tuning by casting data selection as maximizing mutual information between selected examples and task-specific query signals.

How it works

  1. Principled Theoretical Formulation: The problem is formulated as maximizing mutual information between Gaussians scaled by data and query embeddings

Improvements for AI systems

  1. Bold header: Principled selection of training examples using Greedy Information Projection (GIP). This framework casts selection as maximizing mutual information between a subset of examples and task-specific query signals, allowing for a principled theoretical formulation that promotes both quality and diversity in a single objective.

  2. Bold header: Efficient, scalable data selection via Greedy Matching Pursuit (MP). The paper develops an algorithm that scales linearly with the total size of available data in practice, enabling data selection under realistic budget constraints, with a complexity of O(mk).

  3. Bold header: Unification of quality and diversity signals. GIP is designed to naturally balance quality and diversity by optimizing a closed-form mutual information objective, which is equivalent to maximizing the projection of the query embedding matrix onto the span of the selected data, providing a geometric explanation for this co-emergence.

  4. Bold header: Robust performance on diverse benchmarks. GIP methods achieve substantial data efficiency gains over state-of-the-art baselines, often reaching full-dataset performance using only 1–20% of training data across instruction-following and mathematical reasoning tasks.

  5. Bold header: Complementary selection strategies for specialized tasks. The framework offers two complementary variants: MP+MA is strongest on instruction-following and preference-style metrics, while MP+SC achieves strong reasoning performance without external supervision.

  6. Bold header: Enhanced stability against embedding noise during data selection. Experiments show that the Intersection-over-Union (IoU) of selected subsets remains ≥ 85% for σ ≤ 10−3, indicating that mild embedding variations have minimal impact on selection outcomes.

Sources

Related papers