MAPLE: Many-Shot Adaptive Pseudo-Labeling for In-Context Learning

W1. Practicality Concerns.

Response: Thank you for raising concerns regarding computational complexity. To address practicality, our framework incorporates strategies to improve efficiency significantly:

By employing a KV cache, we reduce computational costs by fixing labeled and pseudo-labeled demonstrations across queries, allowing caching of demonstrations within the LLM prior to inference. As demonstrated in Table 2, this approach effectively enhances efficiency without loss of accuracy, making MAPLE more practical for real-world scenarios. A detailed analysis is provided in Appendix D.

Additionally, the influence graph construction process is precomputed. In this way, we ensure that its computational cost does not scale with the number of queries, further enhancing efficiency and practical feasibility.

W2. Unstable Gains from Pseudo-Labeling.

Response: We would like to clarify that in our experiments, MAPLE consistently outperforms other baselines. MAPLE is primarily compared quantitatively against 5 baseline methods on 8 datasets with 5 settings (i.e., the number of pseudo-labeled samples). The results are shown in Figure 1. Among the 8 datasets, MAPLE performs the best on 5 datasets in all settings. On the other 3 datasets, MAPLE performs the best in 4 out of 5 settings. Therefore, these results can validate MAPLE's strong performance.

W3. Limited Experimental Scope.

Response: We appreciate your suggestion regarding the experiments. Our current experiments include both Gemini 1.5 Pro and Gemini 1.5 Flash, which are widely adopted and representative models for many-shot ICL [1,2]. Due to limited rebuttal time, we were unable to include additional models like LLaMA and Qwen, but we plan to explore them in future work. To broaden task diversity, we have added results on a math benchmark GSM8K, and the results demonstrate the superiority of MAPLE on math tasks. We will expand to more datasets in the next version.

[1] Agarwal et al. Many-Shot In-Context Learning. NeurIPS 2024.

[2] Baek et al. Revisiting In-Context Learning with Long Context Language Models. arXiv 2024.

W4. Lack of Discussion on Theoretical Upper Bound: The paper does not discuss the upper-bound performance of the proposed method. For instance, if many-shot data were fully annotated with golden labels, how would the proposed approach compare against a retrieval-augmented generation (RAG) baseline? A discussion on this aspect would provide a clearer perspective on the fundamental limitations of the method.

Response:

We appreciate your point. While deriving a theoretical upper bound for many-shot ICL is impractical due to the complexity of LLMs like Gemini 1.5 Flash, we provide an empirical upper bound by comparing MAPLE to RAG using 40, 80, and 120 fully labeled examples. MAPLE consistently outperforms RAG even under full annotation, highlighting its effectiveness and robustness beyond limited-label settings.

W5. Comparison to More Direct Labeling Approaches: With the cost of large model inference decreasing, a straightforward alternative would be to use a sota model (like GPT4) to label all data directly. The paper does not clearly articulate the advantages of the proposed method over this simpler and more practical alternative. A thorough comparison is necessary to justify the additional complexity introduced by the framework.

Response: Thank you for raising this important point. We agree that directly using a state-of-the-art model like GPT-4 (or Gemini) to label all data is a natural and increasingly viable alternative. In fact, our zero-shot baseline involves using Gemini to label the entire dataset directly. As shown in Figure 3, MAPLE significantly outperforms this zero-shot approach across all tasks.

Moreover, MAPLE only requires labeling a very small portion of the data. For instance, XSum contains over 2 million training examples, yet MAPLE achieves strong performance with at most 100 pseudo-labeled samples—representing a reduction of over 99.99% in labeling cost, even with decreasing inference costs.

To further highlight MAPLE’s advantage, we include results on GPQA using Gemini 1.5 Pro. In Table 1, MAPLE achieves 44.9% accuracy, while—as reported in Figure 8 in [1]—even fully using all labeled data yields less than 44% accuracy. This clearly demonstrates the effectiveness and efficiency of our method.

[1] Agarwal et al. Many-Shot In-Context Learning. NeurIPS 2024.

Claim The author claims “strong performance” for the MAPLE, but didn’t specify the baselines nor quantitative results for comparison.

Response: In our experiments, MAPLE is primarily compared quantitatively against 5 baseline methods on 8 datasets with 5 settings (i.e., the number of pseudo-labeled samples). The results are shown in Figure 3. Among the 8 datasets, MAPLE performs the best on 5 datasets on all settings. On the other 3 datasets, MAPLE performs the best on 4 out of 5 settings. Therefore, these results can validate MAPLE's strong performance.

Exp It seems the embedding module is important for MAPLE, and an ablation on that is important.

Response: Thank you for the suggestion. We have conducted ablations using Sentence-BERT (SBert) [1] and DeBERTa [2] as alternative embedding models, evaluating MAPLE with 20, 60, and 100 pseudo-labeled examples. While performance varies across models, MAPLE consistently outperforms baseline, demonstrating its robustness and effectiveness regardless of the specific embedding choice.

[1] Reimers N, Gurevych I. Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks.

[2] He P, Liu X, et al. DeBERTa: Decoding-enhanced BERT with Disentangled Attention.

Comm1. IMPORTANT Most figures are not rendered correctly. Labels for legend and axes are missing.

Response: We sincerely appreciate your feedback on figure clarity. In the revision, we will ensure all figures are correctly formatted and rendered.

Q1. Do you have any explanation why MAPLE works well for GPQA, given the diversity of topics in GPQA?

Response: Thank you for pointing this out. MAPLE's strong performance on GPQA can be attributed to its adaptive demonstration selection, which tailors pseudo-labeled demonstrations specifically for each test query. This adaptability allows MAPLE to effectively handle the topic diversity in GPQA by selecting demonstrations that are contextually relevant to each individual query. Consequently, MAPLE can leverage pseudo-labeled samples to improve performance even when the topics are diverse.

Q1. Do you really need to cut Top-K edges for each node? Is it correct that Top-K only controls speed and does not affect the performance, or there is some interplay between both Top-K and Top-P that affect the performance?

Response: Thank you for the question. We want to clarify that Top-K pruning is essential and does influence selection. Our influence score in Eq(8) depends on the shortest path and its count. In a fully connected graph, all node pairs are directly connected with only one shortest path of length 1, which removes meaningful structural differences and reduces influence estimation to near-random. Moreover, computing the shortest path on a fully connected graph incurs complexity in $\mathcal{O}(|\mathcal{V}|^2)$. Thus, Top-K is important for both efficiency and effective selection.

Q2. Given Figure 6 shows that, mostly, it is more beneficial to put pseudo-labeled examples at back and examples with ground truth labels closer to the query, could you also run the baseline when you just put questions for unlabeled samples (without pseudolabels). It is basically Unsupervised ICL of [1], which was shown to improve upon few-shot baseline that employs only labeled set.

Response: Thank you for the suggestion, and we have added results using only unlabeled questions without pseudo-labels, following the unsupervised ICL setup (#labeled=20, #unlabled=100). Consistent with Figure 6, we observe that placing labeled examples closer to the query still leads to better performance. However, without pseudo-labels, the benefit from unlabeled examples is limited (compared to Fig 6.), highlighting the importance of label information—even if approximated—for effective many-shot ICL.

Q3. What part of the proposed approach is actually the most important?

Response: We appreciate the reviewer’s question. The RAG-Adapt baseline in our paper can be seen as a variant of MAPLE without the graph structure, as both rely on Contriever for relevance score. Without pseudo-labeling, as in our response to Q2, performance drops due to the lack of label information. Further, in our response to Reviewer K6CP W2, we detail how removing individual components of the influence score degrades performance. Together, these results demonstrate that each part of MAPLE is crucial to its overall effectiveness.

Q4. There are some inconsistencies in set of baselines for different tables and Figures. For example, Table 3 misses zero-shot, few-shot and RAG-Adapt (compared to Figure 1). Similarly, Figure 4 misses RAG-Adapt.

Response: Thank you for pointing this out. We believe the reference is to Table 1 (rather than Table 3) since Table 3 is a list of prompts. Due to rebuttal time constraints and API budget limits, we have now additionally run Gemini 1.5 Flash for zero-shot, few-shot, and RAG-Adapt on Table 1, as well as RAG-Adapt for Figure 4. We will include these updated results in the revised version of the paper.

**Q5.**What was used as the embedding model to construct graphs?

Response: Thank you for the question. We use Contriever as the embedding model. This is mentioned in the right column of line 115: “...the relevance score r(vi, vj), as defined in Contriever...” For clarity, we will also explicitly restate this in the Implementation section in the revised version.

Q6. Can we compute node influence directly and not rely on the lower-bound? Does lower bound have some benefits? How the performance will be different if the node influence would be computed directly?

Response: We claim that it is computationally impractical to directly calculate the node influence. As stated in Eq. (17) in Appendix A, the node influence between any pair of nodes, $v_i$ and $v_j$, is calculated from the iterative expansion of the neighboring nodes of $v_i$. This involves all the nodes that exist in any path between $v_i$ and $v_j$, and their corresponding derivatives regarding the embedding of $v_j$. This can be computationally prohibitive when the number of such nodes is massive due to the long distance between $v_i$ and $v_j$.

Therefore, we propose to rely on the lower bound to compute the influence score instead of directly computing the node influence. With our proposed Theorem 3.2, the influence score is computed based on the shortest path distance and the number of shortest paths. Thus, it is much easier to compute, compared to the massive computation of derivatives in the original node influence.

W1. Building a graph for selecting relevant unlabelled samples itself induces additional computation overhead. There is no discussions on the computation cost for graph construction.

Response: Thank you for bringing up this point. The graph construction requires the computation of the relevance score $r$ among any pair of nodes, which will be $\mathcal{O}(|\mathcal{V}|^2)$. To compute shortest paths, we use breadth-first search for each node, and the cost is $\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|) = \mathcal{O}(|\mathcal{V}|)$ as $\mathcal{E}=\mathcal{O}(k|\mathcal{V}|)$. Therefore, the whole shortest path computation cost is $\mathcal{O}(|\mathcal{D}_L||\mathcal{V}|)$. Notably, the above cost is only required once before inference and thus is independent of the number of queries. With more queries involved during the test, the computational cost of the graph becomes more negligible. Moreover, as shown in Table 2 in our paper, the adaptive demonstration selection component does not incur much computational cost.

Thank you so much for your suggestion. We will include this discussion in the appendix.

W2. The design for the influence score seems arbitrary. It would be good to see if keeping only the shortest path or number of shortest paths is worse.

Response: We appreciate your suggestion and have added results (#labeled=20, #p-labeled=100) using only the shortest path and the number of shortest paths. While the shortest path captures how quickly information can travel, it overlooks robustness—relying on a single path can be fragile to noise or minor data variations. On the other hand, using only the number of shortest path captures redundancy but disregards distance; many long paths may not imply a strong influence. Our influence score is designed to capture both efficiency (via short paths) and robustness (via multiple paths), resulting in a more reliable and informative demonstration selection for many-shot ICL.

W3. It is worth noting that the impact of increasing the number of pseudo labeled samples is indeterministic. For GoEmotion, Banking77 and Date, the performance may still go up with more pseudo-labels. While, Tracking 7 seems does not benefit any pseudo labeled samples. A deeper analysis is necessary. Q1. Please further explain why increasing the number of pseudo labels may harm certain datasets.

Response: Thank you for highlighting this point. The inclusion of additional pseudo-labeled samples can sometimes harm performance because pseudo-labels generated by LLMs are not always accurate. Incorrect pseudo-labels may introduce misleading information when used as demonstrations, negatively influencing LLM predictions for specific datasets [1]. However, our method addresses this issue by adaptively selecting pseudo-labeled samples based on their relevance to each test query. This approach mitigates the negative impact of inaccurate pseudo-labeling, as demonstrated by consistent improvements across most tasks. We note that the performance decline is limited to certain datasets, likely due to the higher difficulty or inherent ambiguity of the samples. Nevertheless, MAPLE consistently outperforms baselines even though the number of pseudo-labeled samples is not optimal.

[1] Agarwal et al. Many-Shot In-Context Learning. NeurIPS 2024.

Comm1. It is unclear why the x axis starts with 20 in figure 3. With 0 pseudo-labeled samples, would this be equivalent to few-shot?

Response: Thank you for the observation. Yes, when the number of pseudo-labeled samples is 0, Random, RAG, and MAPLE all reduce to the few-shot setting. To avoid redundancy, we omit x=0 from the x-axis and instead include the few-shot performance as a green horizontal dashed line in Figure 3 for comparison. We will clarify this explicitly in the revised version.