From Few to Many: Self-Improving Many-Shot Reasoners Through Iterative Optimization and Generation
Authors: Xingchen Wan
Han Zhou
Ruoxi Sun
Sercan O Arik
Venue: ICLR 2025 Poster (2025)
Keywords: many-shot
in-context learning
large language models
Primary area: foundation or frontier models, including LLMs

Abstract: Recent advances in long-context large language models (LLMs) have led to the emerging paradigm of many-shot in-context learning (ICL), where it is observed that scaling many more demonstrating examples beyond the conventional few-shot setup in the context can lead to performance benefits. However, despite its promise, it is unclear what aspects dominate the benefits and whether simply scaling to more examples is the most effective way of improving many-shot ICL. In this work, we first provide an analysis on the factors driving many-shot ICL, and we find that 1) many-shot performance can still be attributed to often a few disproportionately influential examples and 2) identifying such influential examples ("optimize") and using them as demonstrations to regenerate new examples ("generate") can lead to further improvements. Inspired by the findings, we propose BRIDGE, an algorithm that alternates between the optimize step with Bayesian optimization to discover the influential sets of examples and the generate step to reuse this set to expand the reasoning paths of the examples back to the many-shot regime automatically. On Gemini, Claude, and Mistral LLMs of different sizes, we show BRIDGE led to significant improvements across a diverse set of tasks including symbolic reasoning, numerical reasoning and code generation.

Published as a conference paper at ICLR 2025
FROM FEW TO MANY: SELF-IMPROVING MANY- SHOT REASONERS THROUGH ITERATIVE OPTIMIZA- TION AND GENERATION
Xingchen Wan', Han Zhou Ruoxi Sun Sercan Ö. Arik GGoogl Cloud AT Research Google DeepMind University of Cambridge "Work done at Google Cloud Al Research (xingchenw, hzhouml, ruoxis, soarik] com
ABSTRACT
Recent advances in long-context large language models (LLMs) have led the emerging paradigm of many-shot in-context learning (ICL), where it is observed that scaling many more demonstrating examples beyond the conventional few- shot setup in the context can lead to performance benefits. However, despite its promise, it unclear what aspects dominate the benefits and whether simply scal- ing to more examples is the most effective way of improving many-shot ICL. In this work, we first provide an analysis on the factors driving many-shot ICL, and we find that 1) many-shot performance can still be attributed to often few dis- proportionately influential examples and 2) identifying such influential examples ("optimize") and using them demonstrations to regenerate new examples ("gen- erate") can lead to further improvements. Inspired by the findings, we propose BRIDGE, algorithm that alternates between the optimize step with Bayesian optimization to discover the influential sets of examples and the generate step to this expand the reasoning paths of the examples back to the many-shot regime automatically. On Gemini, Claude, and Mistral LLMs of different sizes, we show BRIDGE led to significant improvements across diverse set of tasks including symbolic reasoning, numerical reasoning and code generation.
INTRODUCTION
Recent advances in large language models (LLMs) have led to the emergence of in-context learning (ICL) as a promising new learning paradigm (Brown et al.) 2020). ICL allows LLMs learn tasks by simply being presented with a few examples within their context window. A key bottleneck for ICL has been the supported context length of LLMs, but with advancements in novel model archi- tectures. computational infrastructures and efficient serving methods, tatte-of-the-an models such as Gemini (Reid et al.) 2024] Anthropic 2024) feature context windows millions of tokens are overcoming this limitation. Such long-context LLMs open unprecedented avenues for the scaling of ICL. - whereas previous LLMS were limited to processing only up to dozens of examples, cur- rent LLMs can now accommodate significantly more examples. More importantly, beyond merely supporting a longer context, it has also been shown that scaling more examples led to substantial performance improvements across tasks, creating new promising paradigm known many-shot learning (Agaraal et al. 2024 Bertsch et al. 2024).
Despite these advances, as nascent paradigm, many-shov shot ICL still faces several challenges. Long context windows, while powerful, are computationally expensive and introduce significant latency and cost to serving, making it impractical or uneconomical fully exploit the maximum context length and some kind of trade-off decisions have to be made under virtually any realistic settings. To leverage the expanded context while controlling the cost and latency under an acceptable limit, existing works typically investigate the experimental setting where as many examples as costs permit are simply randomly sub-sampled from the pool all available examples and dumped into the con- text window. As observed both in prior works (Agarwal et al. 2024) and investigations (Fig. [.. using the same number of examples but with different combinations of examples as demonstrations can lead to dramatically different performance for the same task. Across different tasks, it has also

---

Published as a conference paper at ICLR 2025
logical deduction (7)
geometric shapes
disambiguation qa
0.8
Val. Acc
0.7
0.8
Top-K
Bottom-K
0.7
Overall trendline
0.6
0.6
Reinf. ICL
All examples
0.5
-0.6
0
# Demos
46
# Demos
43
0
# Demos
42
Figure I: It does not always take "many shots" to achieve many-shot performance - with judicious selection, it is possible match exceed many-shot performance achieved with using all available examples) with much fewer examples: Accuracy on held-out splits against the number of examples on 3 BBH tasks of 1) overall trendline (fitted with locally weighted smoothing (LOWESS)), 2) using top-K most positive examples, or 3) using bottom-K least positive examples based on the ranking of the importance score described in Sec 2 Dotted lines refer to two many-shot baselines: reinforced ICL: using input, model-generated reasoning and output of all correctly-peedicted inputs; All ex- ample: using all available imput-output pairs from the train set. Lines and error bars show mean = standard deviation across 3 runs with the ordering of the examples shuffled each trial.
been noted that the model behaves very differently when the number of examples is scaled up, with some showing near- monoomoontonic increase in performance as more examples are added, while others experience performance plateaus (e.g., gray line in the leftmost subfigure of Fig. D or even degra- dation (e.g., red line in the rightmost subfigure of Fig. 4 Understandably, such variability could pose challenges for practitioners and present obstacles to the application of many-shot learning as an effective paradigm in practice.
To address these, this paper aims to answer key research questions and proposes an effective novel approach. First, analyze the factors driving the many-shot ICL. in the reinforced ICI. setup com- mon in challenging reasoning tasks where we are provided with a labeled set of inputs and final labels, but the intermediate reasoning path has to be model-generated. We find that while ICL performance often increases with the number of shots, that improvement can often be at least par- tially attributed to a much smaller subset of examples that highly disproportionately contribute to the overall task performance as we scale the number of examples, the probability of including these examples also increases. In many cases, if, however, we judiciously isolate these influential examples from the rest, the "many-shot" performance can be matched or even exceeded with this sometimes extremely small subset of well-chosen examples alone while adding more examples be- yond this set often provides little benefit or even harms performance. We also argue that the findings explain some of the phenomena observed. For example, uneven influence can lead to high variance across different combinations of examples, whereas plateauing performance may occur when out of good examples with positive performance influences. One natural implication of these is the efficiency gains by reducing redundancy in many-shot ICL and identifying the optimized subsets. However, the natural next question to ask is whether scaling ICL examples in LLMs can still be ben- eficial after using up all beneficial examples identified in the previous step. We answer affirmatively to this: to still leverage LLMs' long context, these optimized, high-performing examples may serve as demonstrations to re- re-generate the more effective reasoning paths rationales on the train set back into the many-shot regime, which we find to often outperform both the original many-shot examples and using the optimized examples themselves. Building on these insights, we propose Bayesian Refinement and Iterative Demonstration Generation for Examples (BRIDGE), search algorithm based on Bayesian optimization to improve many-shot ICL and bridges the few- and many-shot learning paradigms by automating the "optimize" and "generate" steps above iteratively. In the "optimize" step, it frames the problem as a combinatorial optimization task to discover the optimal set of demonstrations (i.e., many-to-few), and in the "generate" step, it uses the optimal set seed examples to generate more examples for further performance enhancement few-to-mw demonstrate the effectiveness of BRIDGE on Gemini, Mistral and Claude models across diverse range of tasks, including symbolic reasoning, numerical reasoning and text-to-SQL generation.
We
2 WHAT DRIVES MANY-SHOT IN-CONTEXT LEARNING PERFORMANCE??
Several previous studies many-shot ICL (Agarwal al. 2024 Bertsch al. 2024) have inves- tigated the presence of performance gains when we scale the number of examples. A key question that remains unanswered, though, is what exactly leads this improvement. For example, it is
2

---

Published as a conference paper at ICLR 2025
unknown whether the benefit is from scaling examples itself due to expanded knowledge in the context via more examples or because including more examples increases the probability of se- lecting a small subset of disproportionately positive examples, or combination of the above with some task specificity. We argue that answering this question is critical - if the benefit comes from expanded knowledge from including more examples, it suggests that scaling and addressing long- context understanding challenges would dominate the end-to-end performance improvements, and future studies should aim to either include as many examples as practically possible to imitate the behavior of the LLM as if many examples are included. If, on the other hand, the performance dominated by a small effective subset of examples, more intelligent selection aiming to reduce redundancies and identify the high-performing subsets should outweigh näively scaling examples.
expaas
Prior work on few-shot setup have studied related problems such as the sensitivity to examples in the context (Zhao et al.) 2021 Zhou et al. 2024b). However, it is presently unknown to what extent the findings still scale to the many-shot ICI, setup because 1) in many-shot setup, the influence of each individual example would get much smaller, and 2) it is unknown whether careful example selection in the few-shot setup is still necessary if all examples can be included in the context, since by definition, any tegh-eeforming examples are subsets of all examples if the long-context LLM is perfectly capable of identifying the most relevant pieces of information. If so, aside from other practical concerns like cost and latency, the need for users to manually curate examples may no longer be required.
Setup. We aim to shed insights these important questions. We use the Gemini 1.5 Pro (Reid et al., 2024), the state-of-the-art long-context model, to focus on several representative tasks from the BBH tasks. All three tasks, as shown in by the gray lines in Fig. [ benefit from increasing number of examples to varying degrees (in logi ca _deduct ion, the performance initially increases with the number of examples before plateauing and decreasing; in the other two tasks, there is a noisy but near monotonic improvement throughout) we will test the key findings in much more extensive collection of tasks Sec. 4 Given the increased emphasis of modern L.LMs on problem-solvine and reasoning, we primarily focus on these tasks and adopt the reinforced ICI. (Agarwal et al.) 2024) setup, where we assume the availability of a labeled set of inputs and final labels to be used as many-shot demonstrations, whereas any intermediate outputs rationales leading to the final answer are model-generatee alternative setups such low-resource machine translation in App. C.4). Lastly, we primarily focus on the tasks with the number of available labeled data up to 150-200 samples while modern LLMs can often accommodate even more examples in the context, we focus on this range because 1) we believe it is the most practically relevant and fills an important gap that neither few-shot ICL. nor supervised (parameter-efficientt fine-tuning (which usually requires hundreds thousands of examples) conventionally address, and 2) while possible and of academic value, scaling beyond this range typically starts incurring significant latency and computational overhead, which scales quadratically w.r.t the input length for exact attention and is thus often practically less desired for most woaldworld use cases.
and modifiable (although we also conduct preliminary experiments in
Many-shot performance can still be driven by few nigh-performing examples. A key test that would distinguish and disentangle the two possible sources of benefits from scaling mentioned at the beginning of this section is that whether we can attribute, at least to a large extent, the perfor- mance improvement from scaling examples back to a carefully selected, high high-performing subset of examples with disproportionate influence. Formally, given set of examples & = {e, { and the validation
performance metric to be maximized 9(-) P(E) + R (in this case, the accuracy set In this setup, the goal is to find whether we can construct subset e = {ee In C E, s.t.n < m such that g(e") ) is much better than a randomly selected of examples of similar size and/or can even be comparable or better than using the full set of examples g(E) in the context.
Whereas conclusive test would involve enumerating and evaluating 9(-) on the power set of E with |P(E) = 21 it is clearly computationally intractable, and natural simplification is whether we can rank the individual examples in E with some importance scoring function (e) to con- struct example subsets based on the example ranking. While many possible formulations of this are possible. here we define (e) based on imputed input gradient, which is a concept used in interpretable machine learning for importance attribution (Simonyan, [0013 Selvaraju et al. 2017 SSundararajan et al., 2017;; [aank et al. 2021). In our context, directly computing input gradient is impossible as we only assume black- box LLMs without gradient backpropagation and g(-) is
3

---

Published as a conference paper at ICLR 2025
not necessarily differentiable. To bypass these issues, we use sample-efficient Gaussian pro- cess regressor (GPR) (Williams & Raamuussnn 1995 2006) to approximate g(-) with g(-), whose input gradient Veg(e) Is analytically available: we first randomly sample n subsets of & to give 61:- = [el,...,em] where each subset of examples is represented as a m-dimensional binary col- umn vector e, E {0, 1)Th with e.
if the j-th example is present or 0 otherwise; we then evaluate the performance metric of each e; to obtain gimm [g(e1),..., g(..).. We then compute and average the input gradient w.r.f. each possible { & to obtain approximated marginal- ized importance of each example in E(See App.[A]foo detailed derivation of the input gradient-bast -based score). Finally, we sort the examples based on (e) and construct subsets at regular interval from size 1 to [ε] in both ascending and descending directions. Formally, we order {e:} such that ((1) S (e2) S ... < M (cn); the ascending and descending sets of size t E [1] are given by a, 112 and d, en-ton to respectively. We then evaluate g(-) on these sets (Fig. geometric @eopetric_shapes
As shown, while the gray lines (overall trend lines) often show posi- tive correlation between performance and increasing number exam- ples, we also observe often large gap between the green (top-k ex- amples) and the red (bottom-k examples) lines, suggesting that dif- ferent sampling strategies can lead to performance differences that far outweigh the effect from naive scaling- e.g., if we establish an "exchange rate" between different example sets based on their im- puted ordering, we can observe that including around top-10 exam- ples (green lines) examples is as effective as or more effective than the set containing bottom-30 examples in geometri criccraapesssss... s. More importantly, in both cases we observe that the green lines, which represent an intelligent selection strategy more sophisticated than random sampling, plateau far before the gray line, suggesting that it possible to achieve comparable performance with much fewer number of examples: in di sambi cambiguttii ion_aa, we find that using fewer than 20 top examples is almost already as good as using all 42 examples whereas subsequent additions only led to few percent of gain, possibly within the margin of error with reshuf- fling (denoted by error bars the figure). In the other tasks, we find the performance to peak much earlier and adding more exam- ples to the context actually led to performance deterioration. The results suggest 1) the fact that it is possible to match or outperform using all examples with fewer, carefully selected examples means that intelligent example selection is still relevant even with many- shot ICL, echoing findings from the recent works (Li et al., (2024) that retrieval remains valuable for long-context models in the RAG setup; and 2) naïvely including as many examples as possible can be suboptimal both in terms of computing cost and performance while is trivially true for the tasks whose performance does not improve monotonically with the number of examples, we show that can even be true when it apparently does: e.g., on geomet r ric.cs c.shapes, the near monotonic improvement overall trend (gray line) may lead someone to conclude that it is beneficial to include as many examples as possible, even though the green line representing intelligent selection saturates and starts to decline earlier.
Val. Acc.
0.8
0.6
64
disambiguation qa
0.8
Val. Acc. Acc.
0.6
0
# +Demos 51
Figure 2: Good demon- strations lead to better re-generated trendlines between accuracy and # examples; note that the re-generated examples by using top-5 examples sets as demonstrations outperform the original examples (gray line) by at all parts of the curve.
examples:
Can we still benefit from scaling examples? Experiments above demonstrated the presence of redundancy in many-shot ICL, revealing that using a smaller subset of examples can often reduce this redundancy without sacrificing performance. It is, however, a pruning operation that necessar- ily reduce the input tokens consumed. This leads to a natural question: can we still benefit from scaling through expanding? For this question, it is important to recognize that under the reinforced ICL setup, while the inputs and labels in many-shot setups are fixed, the model-generatte diate outputs, which represent reasoning paths, are modifiable. Given that these intermediate roles are shown to play critical role steering model behaviors (Wan et al., 2024), it is possible that examples previously identified as non-importan non- non-beneficial may be again beneficial if the model-generated rationales can be improved.
interme-
4

---

Published as a conference paper at ICLR 2025
Generate
Optimize
Evaluate
Q1
A1
Set of available
examples &
Pool evaluated example sets
Sample
performance
Q1
+
46%
A2
SLLO
Q1
A1
G3
A3
36
A6
A3
Q3
P
D
34
A4
QS
A5
LLM
A5
Q6
Suggest New
S Eayesian
Update
W 84%)
0 P5%)
0000
Use as demonstrations round
Optimizer
02
Select argmax
AS
Overview of BRIDGE: With a labeled dataset D, exemplified with 6 samples, at the Gen- eration phase (left half), we generate initial examples by performing LLM inference on the inputs of D ("Q1-6") with zero-shot prompting to obtain the initial responses "A1-6", which include any intermediate outputs critical for ICL (Step 1). At Step 2, consistent with reinforced ICL in [Agarwal et al.] (2024), we filter the responses to retain the subset of DD where the LLM predicted correctly ensure the examples include correct reasoning steps to build Eg, the pool of examples at round which form the search space for the subsequent Optimize step. At the Optimize step (right half), we initialize the proposed Bayesian optimizer by randomly sampling subsets e (0) C & as demon- strations be Step evaluated on a held-out validation dataset (D be reused for this purpose) to obtain a performance metric Step 4. The Bayesian optimizer (BO) is then updated with binary vector representations of e that led this validation performance as input and the metric itself as output, and suggests a new subset of examples to be used as demonstrations for the next step Step 5; Steps 4-5 are repeated (inner loop) until the BO budget is exhausted, after which the best evaluated set of is returned (Step 6). This set is then be used as demonstrations to generate the example pool for the next round E (Step 7).
Figure 3:
To achieve so, we reuse the optimized example set from the previous steps as "seed" demonstrations for LLMMs to re-generate the examples on the train set, the same set from which the optimized examples are generated. As shown by Fig. 2 where we use example set of different sizes as the seeds, the regeneration step not only increases the number of shots available but also results in better performance across the accuracy versus
trade-off.
3 METHODOLOGY
The findings presented above highlight significant need for improvements that extend beyond simply increasing the number of examples straightforwardly, Instead, identifying the most useful example subset c* is crucial both for effective pest-performance trade-off and for better reason- ing path generation for more effective examples. Based on these insights, we propose Bayesian Refinement and [terative Demonstration Generation for Examples, or BRIDGE in short (described optimization algorithm aiming enhance many ICL with intelligent example selection and iterative example generation. At a high level, the outer loop of BRIDGE is structured in two alternating steps of "opttmiiee and "generate". In the "optimize" step, the algorithm focuses on discovering the optimal subset of examples e* via a carefully- (for low complexity, robustness overfitting and budget control) Bayesian optimization algorithm that naturally leverages the GPR surrogate used in Sec. 2 in the "generate" step, BRIDGE utilizes the optimized subset seed demonstrations to align the model with the best performing examples seen so far to re- re-generate new reasoning paths as an integral part of more effective examples back the mhny-shot regime leverage the long context. The two steps are iteratively repeated to progressively refine the examples.
in Algorithm|] I and depicted in Fig.
Optimize step. While effective, directly using the importance scoring approach from Sec. 2 to identify the e' would require us to set the optimal number of examples to select ||e"]] as hy- perparameter, the optimal value of which is task specific. Furthermore, a key motivation for the importance-based ranking in Sec. 2 iis to attribute performance to individual examples; this is, how- ever, not required if we simply would like to find an optimal subset e*. To nevertheless use the GPR surrogate in Sec. 2 which has shown impressive sample-efficient, modelling capability, pro- pose to use Bayesian optimization (BO) (Gareeti [023] Frazier 2018). a sample-efficien black-bo optimization algorithm that has recently shown promise in combinatorial problems (Daulton al.
5

---

Published as a conference paper at ICLR 2025
Algorithm 1 BRIDGE.
Algorithm 2 Budget-controlles BO subroutine with random scalarization (BayesOpt).
I: Input: train set Di, validation set D. (can be the
same as the train set), number of iteration rounds
I: Input: Evaluation budget for BO per iteration Reval (inner-loop), full set of available samples E. number of random initializations Ninit min(16, Meval/ 22).
K E I4 (outer-loop). evaluation budget for BO per iteration Reval (inner-loop).
2: Output: Optimized set of examples E
3: [Generate] Generate the pool of initial exam- 2: Output: Optimized set of examples e" C E
ples Eo by predicting the LLM on the train set with zero-shot prompting or few-shot prompting (if handwritten few-shot demonstrations are avail- able). Each instance in Eu is a concatenation of finput, model- -eneeratd reasoning, final ) for the subset of the train set where the model ob- tained the correct prediction.
3: Randomly generate Rinit. subsets 0l:miit
(el,..., Branis } with each e ~ {0, 1316el s.t. |e|
U (L,
4: Evaluate gl:maut = Cnniaa
Crimae] J on eismais as inputs and gismoni as outputs. Set Do + ( Bl:maatt
and fit a GP
5:
for E {Minit, -..y Reval) (Inner loop) do random scalarization value 3 ~ Uniform(0,) 1) and compute the scalarized objective of this iteration h.(e) (St, (g(e), |e(]).
4: for E (I,... K} (Outer loop) do
6:
Sample
5: [Optimize] Run Bayesian optimization (calling
subroutine Algorithm 2 on the validation set to E=Ex).
obtain oj < (aaavesOt((eeod-nia
6: [Generate] Re-generate examples En by 7: predicting the LLM on the train set, but with the optimized examples ej from the previous step as demonstrations; the (inputs, model- generated reasoning, output -tuples are con- catenated to form the new set of examples E 8: for next [Optimize] step.
Compute har for previously evaluated points D--1, fit a GPR GP, on [en: h1:s] and ob- tain the next configuration to evaluate by max- imizing the acquisition function a(-): arg maxege a(e gPt).
Evaluate g(-) with ee and augment D. t
Di-1 U (et. g()))
7: end for
9:
end for
8: return Optimized example set Ex after K rounds. 10: return e" = arg maxeeD g(e).
2022 Wan et al., 2021): it naturally synergizes with the GP surrogate yet automatically strikes a balance between exploration and exploitation to discover e* without requiring us to set ||e"| || be- forehand, although BRIDGE also compatible with alternative methods as drop-in replacement of the "Optimize" step, which we investigate in detail in App. C.I
Instead of consuming the entire query budget by sampling randomly, as illustrated by Algorithm 2 BO only requires some initializing samples to warm-start (Step 3). Afterward, it guides exploration by iteratively (re)fitting& a GPR with the previous observed inputs and outputs so far. Formally, at iteration [1, we have evaluated 9(-) times at e1 [et, ...: e with observed val- ues gi.t. Whereas a straightforward application of BO would directly train a GP on [e1: [e1::g1a] as inputs-outputs and perform BO with 9(-) as the objective function directly, subtle but important distinction here is that our goal is to identify a subset e" that, when used as demonstrations on the train set, generates to the most effective examples on the validation set, rather to simply find the highest-performing e* on the validation set. While we expect the two objectives to be correlated (i.e., e that led high validation performance also likely to generate better samples on the train set), we also empirically find it is desirable to encourage e" to have smaller cardinality akin to a to regularization to reduce overfitting on the validation set and to discourage memorization in sub- sequent generations from the previous example set E of which e is a subset. To achieve so, we augment the performance maximization max g(e) with a sparsity objective which counts the number of non-zero elements in e: min Σ, e this transforms the problem into a bi-objective optimiza- tion problem, where instead of maximizing for the validation performance only, we also encourage sparsity as regularization. Practically, we solve the problem with random scalarization (Paria et al.) 2020 Knowles] 2006). Specifically, as hinted in Step 7 of Algorithm 2 at each BO iteration, we first sample random scalar 3, Unif (BB .UB) that determines the weight of the performance objective g(-) of the t-th BO iteration (the weight of the sparsity objective is given by 1 1- 1-3:) and {BLB, BUB) denote the lower and upper bounds of the weight for g(-) which are set to {0.25, }} by default. With this Be, we then aggregate the vector objective [g(e), E, e(i)] back to scalar (e) via Tchebyshev scalarization (TCH), theoretically well-founded scalarization scheme common in multi-objective optimization (Chugh 2020; Steuer & Choo 1983 Bowman Jr 1976) given by:
(e) max { (o(e)) - (mxx(o()))....
-(1 8) Σ (1)
(1)
where the minus sign before the last term is to cast the sparsity objectivé as maximization. We opt for random scalarization that differs step to step instead of a fixed scalarization weight or any hard constraint on Eze e(5 to retain the flexibility of exploring the entire Pareto front, since the
6

---

Published as a conference paper at ICLR 2025
Table 1: Test accuracy of gemini- 1eriia1.5--r---00 5-pro-001 on selected BBH tasks with different prompt- ing approaches. "All" refers to using the entire labeled set of 75 examples as demonstrations ("Di- rect": using all input-final answer pairs without any model-generated content; "CoT": using all input-rationale-fiii final answer triplet, where the rationale is gener-tg::::ttd; "Infill": using all input- rationale-fina final answer triplet, where the rationale is filled in by prompting the model to generate the intermediate steps given the inputs and ground-truth answers); "Reinf. ICL" refers to reinforced many-shot ICL where include the subset of train set that the LLM answered correctly under zero-shot as demonstrations; "Iterative Reinf." refers to the iterative variant of reinforced many-shot ICL where we directly use all the generated correct examples from the previous round as demonstra- tions for the next round without the optimize step, and the different columns of BRIDGE show the evolution of test accuracy different milestones: e.g., 10 refers the results with optimized eî from initial examples Eo as demonstrations (in general, we have ei S 1), and IG refers to the results using & generated by re-evaluating the train set with ej as demonstrations. All results shown are averaged across 4 random seeds with the standard deviation (stdev) denoted in the subscript. Best and second- best results along each row are bolded and underlined, respectively (ties are broken by favoring the result with lower stdev).
Tasks
All CoT
Reinf. ICL
lterative Reinf.
BRIDOR (Ouns)
Direct
Infill
# lterations
0
0
2
10
1G
20
2G
30
causal judgeement
61.04,7
62.7g.
68.00 68.0
66.34,
68.7 18.7,a
69.3 3v.7
65.3
62.7
59.71.5
72.0u.
70.02g
date umderstanding
87.25.
86.0h.
94.8
88.81.
93.0
94.9,
92.2
97.00e
94.81
95.0,
95.5
disambiguation qa
74.2
63.3
72.3xa
76.82.
74.6
75.11s
71.82a
17.5
80.5
81.3as
78.8.
dyek languagss
16.839
39.0t.7
24.529
55 53.6
64.4s3
74.456
49 49.22..
76.22.8
80.0
77.5
76.83.
formal fallacies
82.8
86.8
84.3
86.2
88.1ps
89.414
86.0h.
K5. 85.0h.
90.8::
90.8
88.2
gcometric shapes
69.0,.
61.8a.2
73.52.1
80.22,
81 .0...
82.3,.7
78.5 78.52.
82.5
89.2
92.3,,
89, 19,2as
hyperbaton
70.8
93.23.
89.51a
90.2,.1
91 5u2
86 86.22.
96.5pg
94.2g,5
94.81a
96.5u.
97.2
logical deductiion
56 56.8cA
63.0t.4
69.8.
65.81.
9..
69.5 Sa.
70.2
70.8
71.7
71.5
69. 69.22.
75.0,a
63.75.2
68 0..5
65 65.2
68. 8un
82.0g,
67 10,2
69.5au.
69.3t..
72.8
67.0
muatistep_arihmmetic
86.51.2
96.8ga
88.8
96-5pu
94-5
96.2a8
94.51.1
97.0k.
98.0
96.8
object_countingg counting
92.5
84.8
95.3
95.5ma
95. 83.2
95.116
96.2p.4
96.0h1
94.5
94,2a.
95.0gt
min namen
85.25.1
85.5g.
89.816
89.8,,
88. 65.
90.5pa
90.8,.1
88.8,.
89.2,,
88.824
90.3au
salient, Iranslation, srror pletection
66.00.4
56.215
72.505
69.0
73.8
73,4
68. 88.
71.0gz
69.5a.2
74.0n1
74.5
snarks
94.1
95.5%
95.1ns
92.7ka
95.5 94.3,
93.4
95 95.Man
95.1
96.91
97.6,
sports.understanding
93.8
94.2
95.0..
93.0,,
95.412
8.9
97.0,2
96.2nx
95.8ua
95, 8us
trucking shullled objects (7)
76.07
52.5g
64.3za
62.3,a
64.5
65.5
95 80.4
95.0
100.00.
97.0g7
99.501
Average
74.22
74.06
78.70
79.61
81.61
82.37
82.11
84.61
85.77
87.13
86.33
exact relation between the number of samples and performance can differ across tasks, Since Se is in general different for each t, we then compute h, = [e)) ..., (e,)) on previously evaluated outputs and fit GP on Hi == Jer:,, ha], which induces Gaussian posterior predictive distribution with mean and variance at any C E (we use h, denote that it is the GP approximation of the actual function hy):
BR.so))N (he()))) = k, + "h, (he k(e, e) k,KK + rT 'K.
(2)
where k, = [k(e, e1), ...),...kk(e kie, )x and k(.,-) is the covariance function of the GP (we use Matern 2.5 by default) which measures the similarity between two inputs - in our case, it is function of the number of overlapping examples between two subsets of examples e, e' C E. To select the next configuration to evaluate ex the BO optimizes an acquisition function, another key component of BO that automatically trade off exploration and exploitation. At each inner-loop BO iteration, we choose the maximizer of the expected improvement (EI) (Zhan Xing 2020) for the next iteration ey: e, = arg max.gg a<ee = arg maxeçs (i,(e))],, [axx (0, hy(e) max }.(e)))}-
Generate step. At each outer-loop round k E {1,..., K}. given the optimized et as demonstra- tions, we regenerate and replace the example pool with the correct predictions and their generated rationales En + fLLM(D,, et S Ex-1) for subsequent optimize step.
4 EXPERIMENTS
Model and evaluation data. We conduct experiments on an extensive collection of tasks requir- ing different set of skills task difficulty on two Gemini 1.5 models (gemini 1. 1.5--.pppr 10.5--0r0000 0011 and gemini-1 1ari-----flash-00 flash-001)) while also testing key findings on Mistral family of models: Mis- and Mistral Large misttll-aarge-22
and Claude 3.5 Sonnet: 1) BIG-Bench Hard (BBH) tasks encompassing wide range of challenging numerical reasoning, commonsense problem-solvin logical deduction and tabular reasoning tasks - we par- ticularly focus the subset of 16 BBH tasks where the model performances have not saturated; 2)
tral NeMo (mi mmistral--nem--1
7

---

Published as a conference paper at ICLR 2025
Table 2: Test accuracy of gemini- 5 5-pro-001 on MATH and GSM-Hard datasets. Refer to the captions of Table I for detailed explanations.
Tisks
Reinf.
lterative
BRIDGE (Owrx)
ICL.
Reinf.
Tterations
0
2
10
16
20
20
30
Hendryck's MATH
63.75us
13.60ps
63.60
62.60
63. (3.00.2
63.85,.1
64.65us
64.40sa
GSM-Hard
69.88ux
69.84
69.33a1
7
71.31o
71.81a
73.32n
72.50p
Hendryck's MATH (Hendrycks al., 2021), challenging numerical reasoning dataset; 3) GSM-
Hard (Gao et al. 2022), a more challenging variant of the classical grade-school GSM-8K (Cobbe)
al. 2021 with the numbers in the questions replaced with much larger and rarer ones. To fur-
ther probe the utility of many-shot learning and BRIDGE in coding tasks, we also experiment on 4) BIRD (Li et al.] 2024a), a challenging large-scale text-to-SQL generation benchmark where the L.LM has to generate sqlite programs from natural language instructions that are executed on real- world databases. For all datasets, when official train-test split is not available, we randomly split the data into train and test splits; unless stated otherwise, single unified train split is used both for the generation of demonstrations and is reused for validation (i.e., the objective of the optimize step in Algorithm T the test splits are held-out and only used for evaluation of the algorithm. We refer the readers to App. B for detailed descriptions, prompt templates used and evaluation protocol.
Experimental setup. For all tasks, we run BRIDGE with K 3 rounds (i.e., the number of outer- doop iterations in Algorithm I and within each round, we allow for Reval = 32 evaluations on the validation set (i.e., the number of inner-loop iterations in Algorithm 2 and report the results at the end of each "optimize" and "generate" steps to visualize the iteration process. For baselines, we consider 1) using all provided examples and we consider three variants: a) using query-target only without any generated rationales (Direct), b) first prompt the LLM to generate rationales and an- swers, and use the concatenation of query-rationale target as demonstrations, regardless of whether the rationale led to the correct answer (CoTT), and c) prompting the LLM with both the query and the final, ground-truth answer to fill in the rationale- this technique has been variously referred to as, e.g., infilling (Hu et al. (023), rationalization (Zelikman et al. 2022), or more generally, teacher forcing (Chen et al.] (025) due to its conceptual similarity to teacher forcing in recurrent neural net- work (RNN) training (Lamb et al. 2016) (Infill): 2) reinforced ICL (Agarwal et al. 2024), where all available input-output pairs from the correct predictions on the train set with zero-shot prompting used; and 3) an iterative variant of reinforced ICL which can also be seen BRIDGE without the optimize step: while we repeat the generation process on the train set K = 3 times, we do not first aim select the optimized subset but instead use the entire generated examples from the previous step as demonstrations E + (T,,Aa(D,,, 1)-
Results and discussions. We show the test accuracy on the BBH tasks in Table (gemini-3 -1 ppro-001), Table 3 (gemini- -imiiiii-... 5- flash), Table [4] (Mistral) and Table [5] (Claude 3.5 Sonnet) (the latter two tables are in App. C.S). On MATH and GSM-Hard datasets, we show the Gemini 1.5 Pro results in Table 2 We observe that naïve many-shot scaling is in general ineffective and is outperformed by reinforced ICL; BRIDGE, however, outperforms the base rein- forced many-shot ICL by more than 7% and 3% on Tables [ and 3 respectively, and the extent of outperformance over the "Iterative reinforced ICL", which leads to moderate improvements on BBH with Gemini Pro but no significant performance gains on MATH, GSM-Hard and BBH with Gemini Flash. Both demonstrate that optimize is an integral component of BRIDGE and implicitly validates the findings in Sec. that many-shot performance can be driven by few disproportionately influential examples, which constitutes a core motivation for our method. Barring some expected task-specific fluctuations, in both Tables T Bl we also observe consistent and monotonic perfor- mance improvement as BRIDGE progresses over the successive optimize and generate steps, even- tually peaking at 2G on Gemini Pro and 20 on Gemini Flash (although the performance difference between 2G and 20 on Gemini Flash is negligible and likely within margin of error) - based on the overall results, we recommend stopping BRIDGE at 2G or 20. Interestingly, we observe that in both cases, an additional optimize step (i.c., the 30 column) somewhat degrades performance - our hypothesis is that as BRIDGE progresses, the generated examples become more aligned with the optimal behavior and the degree of redundancy as we observed in Sec. reduces, and it becomes more difficult to squeeze the number of examples without harming task performance indeed, from Fig4 where we concretely analyze the behavior of the LLM in different tasks by evaluating the LLM under random subsets of Eg...., &g as demonstrations in held-out splits. we observe that the benefit from naïvely scaling examples under the base reinforeed many-shot ICL (denoted by red lines) can be highly unstable across tasks: from the different subfigures of Fig. 4 we find the per- formance to consistently improve with more examples (leftmost), improve then plateau (middle
and
8

---

Published as a conference paper at ICLR 2025
Table 3: Test accuracy of gemini-1.5-flashee 5-lassh--00 on BBH tasks.
Tasks
Reinf. ICL
Iterative Reinf.
BRIDOE
Direct
CoT
Infil
(Ourx)
Iterations
1G
2G
cansal jjudgement
55.05a
57.7LI
62.72n
66.0p
67.72n
66.216
69.32.
66.0ta
63,31,
65.01
65,3
date understanding
84.812
83.3
89.308
84.5ts
86.8cs
87.30a
85,01,
90.5as
91.5a4
90.8a7
92.5us
disambiguation qa
68.8
5
69.0;a
75.5as
77.8
78.5
17.5k;
79,0n
77.5
76.3ux
14.3
dyck languages
46.0pa
19.5.
31,3
66.8,9
61.32a
60.0,u
63.3um
62.0uz
64.51a
62.824
61.8sa
formal fallacies
75.8
74.0
76.3
77.3a4
74.8.
72.5kz
78.3
77.3u.
75.5
78.31
76.3u*
gcometric shapes
45 45.81,
74,2A1
71.3za
86.0gv
93 Box
93.3,,a
93.82a
94,0s2
95 11.
97.0uc
98.0ki
hyperbaton
87.0t.
88.5
93.5
88 88.S
93.3,s
86.5%a
95.51.
95.8us
94.
93.3
logical, ,edduction (7)
37.5t.3
41.0Lp
57.0g.
59.55.
61.919
57.54.7
61.8g.1
57.5
70.5us
66.51.1
75.0k
movie recommeniation
80.5
56.208
92.0
67.0ga
7
75.8%a
70.3
73.3:3
77.3
78.8sc
72.8k1
55.0213
84.022
89.0L9
91.36A
94.0
92.51.
96.32,
96.8n4
97.8u4
94,8ua
95.804
Diject_coundingg
66.01.
91.310
87.513
93.33.
93.5
92.5%.
92.81a
93.82.
95.5us
93.0,a
93.8p.
ruin names
83.2
86.2
88.01
86.5
89.5co
86.8ca
89.3GA
89.3ux
87.0,>
90.3ux
90.0
salient, www..rrnaattonerrrr.....ooo .ettcccceoett
62.0s.7
58.820
65.3gs
64.8,
71.522
64.0gu
62 62.8us
71.0wz
69.824
69.0u>
67.3u4
snarks
81.2gn
92.0.;
80.9.2
89.3,x
88.922
86-5
19.9
89.6u7
90.6us
83.7g5
sports, understanddig
92.51a
91.5aa
95.8a4
95.808
95.5ea
96.3..
93.3
95.3u4
91. 91.8u4
95.0n.
95.0uo
mncking.shuuffled.oo pobjects (7)
63.3g4
72.3g.
$2.8,
92.25.
83.5,11
80.0,a
98.
93.822
98.0uu
97.804
97.5us
Average
67.77
70.29
73,83
80.25
81.91
80.72
81.61
82.79
83.79
83.77
83.25
geometric shopos
sallent, transttttannition ernor dataction
tracking
tracking_shuffled Shuffled objects(7)
MATH
1.00
0.65
0.8
Val. Acc
0.8
0.60
0.75
Round Round!
0.7
0.6
0.55
0.50
0.6
Demos 71
Demos
83 Demos 59 0 Demos 75
Figure 4: Benefits from scaling examples naively (red lines) is very task specific, but each iteration of BRIDGE addresses to a considerable degree by continually improv- ing upon the previous round: We randomly sample subsets of example pool v E (i.e., original examples generated with handcraft few-shot or zero-shot), 1, 2} and evaluate them on a held-out set in four representative tasks exhibiting different model behavior to example scaling. The trendlines are moving regressions fitted with LOWESS. Refers to additional figures in App. C.3
two figures) and even simply deteriorate with more examples (rightmost) whereas the latter two cases are direct manifestations that not all examples contribute positively to many-shot ICL. and naïvely scaling examples is suboptimal, we note that it remains true even in the former case where there is apparent strong, positive correlation between number of demos and performance, we demonstrated in Sec. 2 Remarkably, BRIDGE alleviate the instability with each round of BRIDGE continually improving upon the previous round in cases where scaling examples is already ben- eficial (geomet r iriccca rir.rrhappes..e leftmost figure), subsequent rounds of BRIDGE led to much better performance-con trade-offs with the blue and green lines dominating over the red, whereas in other cases, BRIDGE often "delays" the saturation point (e.g., saliert transtrrnalll inton)) or at least ensure more examples does not lead to deterioration (e.g. track weacckinngsuuufeee fl jecttectt.s
On BIRD dataset, we show the results in Table 4] Given Table 4: Execution accuracy the presence of large training set (more than 9000 sam- ples), we also compare against parameter-efficien super- vised fine-tuning (PEFT) (Han et al., 2024), where we fine-tune the same target LLM with LoRA (Hu et al.) 202T) on either the entire training set or using a num- ber of train samples sub-sampled from the full training set. We observe that whereas the few-shot CHASE prompt effectively improves upon the baseline zero-shot direct prompting, additional rounds of BRIDGE led to further gains. The comparison against LoRA also demonstrates the potential of BRIDGE as an alternative to PEFT at least in certain scenarios. When provided with a similar num- ber of labeled samples (i.e., Arain = 256), we observe that LoRA performs much worse, and it only outperforms BRIDGE when using up the entire train set for training.
on the BIRD dev set with gemini-1.5-pro-ie refer to the accuracy aggregated across (Simple, Moderate, Challenging) leeell problems based on assigned difficulty.
{S. M, C}
Method
Exec. Acc.
Breakdown
5
Direct
57.7
64.0
49.4
44.1
CHASE prompt CHASE BRIDGE
60.1
67.2
51.9
40.7
Round 0
59.1
65.7
51.3
42.1
Roand 1
61.2
68.6
50.6
48.3
Round 2
62.0
68.5
53.0
49.0
PEFT (LoRA)
Ponas = 256
58.2
64.0
52.2
40.7
1024
60.2
66.6
53.0
42.1
Aunis = 4096
61.3
67.5
53.9
46.2
9428 (AII)
63,8
68.6
58.8
48.9
5 RELATED WORK
Scaling ICL. Before the advent of the Congecontext LLMs, early efforts in scaling ICL often study LLMs customized for long context (Li al. (023) or require architectural changes assuming white- box model access (Hao et al. 2022) However, the tasks considered often limited, e.g., to conven-

---

Published as a conference paper at ICLR 2025
tional, discriminative tasks like sentiment classification rather than generative tasks as considered in this work. Furthermore, these often study LLMs that are merely capable with handling many ex- amples, but their behavior may differ significantly to modemn natively long-context LLMs that may actively take advantage of the context - indeed, both these works show mixed results, even signif- icant performance deterioration when scaling up the number of examples, phenomenon not seen in modern long-context LLMs like Gemini and Claude. Recent works like [Agaral et al. (2024) and Bertsch al. 2024), on the other hand, reported significant gains in scaling ICL to hundreds or more examples and provided important motivation for our work. However, as mentioned in Sec. 2 these works primarily demonstrate the existence of the benefit from scaling but did not focus on in- vestigate the sources of the gain or improving the cost-effectiveness of many-shot ICL. Additionally, there have also been works focusing on applications of many-shot ICL to multi-mosalities [Jiang et al. 2024), LLM jail-breaking (Anil et al., 2024), detecting the risk of capturing incorrect skills (Lin & Lee 2024), and analyzing memorization (Golchin et al. 2024).
Example selection and expansion. BRIDGE combines the "optimize" and "generate" steps, and there have been existing works sharing similar high-level ideas to each of the components. First, the "'optimize" step can be seen to improve the data quality with pruning and selection; in this regard, given that data quality is known to be one of the most influential factors for training LLMs (Xia et al. 2024).. many previous works have utilized some flavor of pruning to remove redundant or harmful data samples at different stages of training, including pre-training (Marion et al., (023) and instruction tuning (Xia et al. 2024). In ICL, as mentioned in Sec. 2 given the sensitivity of LLMs to examples, there have been works analyzing prompt sensitivity and proposing example selection techniques (Zhao et al. 2021 Lu et al.
2022 Zhou et al. 20246 Wan et al., (022). Recent work also explored heuristic- based prompt optimization based on similarity (Rubin et al. [2022] Liu et al.)
2022), diversity (Levy et al. [023] Xu et al.) (024). uncertainty (Wan et al. 2023a b). fairess (Zhou et al. 2024a) etc. Our "ggeeratt" step, the other hand, aims to acquire high-quality examples with the LLM itself. In this area, STaR (Zelikman et al. 2022) first proposes to bootstrap rationales from
LLM with a small number of seed examples, followed by fine-tuning: Self-Instruce (Wang et al.
2023) bootstraps LLMs to instruction data. The "Reinforced ICL" technique introduced in Aarwwl
et al.
2024). upon which this work improves, and several recent works (Chen et al.) 2023 Khattab 2023 Opsahl-Ong et al., 2024) use similar technique to acquire and refine model -enee--geeeraedd
et al.
examples for ICL. Notwithstanding the similarities deseribed, there are few crucial differences:
Almost all ICL works mentioned consider the few-shot setup, where selection is made necessary due the constraint on the number of examples allowed in the context. However, we show that even in the many-shot setup where that constraint is relaxed and example selection is no longer a necessity, can still be highly beneficial for performance and efficiency. Unlike the few-shot setup, BRIDGE is tailored for the many-shot setup with design decisions inspired by findings in Sec.2) such as the implementation of sparsity regularization in the optimization objective to enable from scaling.
CONCLUSION
This paper focuses on understanding and enhancing the core factors underlying scaling ICL. We first provide an analysis on the nascent paradigm of many-shot ICL. in LLMs and show that notwithstand- ing the long-context abilities of LLMs, the common practice of naively dumping as many examples as practically possible into the context can be both inefficient in cost and suboptimal in performance. Instead, the benefit from scaling examples can often be realized by identifying a subset of influential examples, and that subset can be used as demonstrations themselves re-generate even more exam- ples. Inspired by the findings, we propose BRIDGE by automatically executing the "optimize" and "generate" steps iteratively. We demonstrate that BRIDGE perform competitively on wide range of tasks, significantly outperforning alternatives. We believe that this work builds the foundation for future research in many-shot ICL. First, we mainly focused on the restrictive black-box LLM setup, which is the most general and model-agnostic. However, for a more relaxed, white-box setup with access to LLM weights, it may be possible to perform optimization more efficiently for example, it may be possible to take advantage of the internal representations of the model in reducing the cost of iterative optimization. Second, we currently focus on the "reinforced ICL" setup typical for reasoning-heave tasks- while we have conducted experiments (e.g., low resource translation tasks) beyond this setup, further validations on other types of tasks would be valuable. Lastly, after opti- mization, the examples generated by BRIDGE currently static at test time, and it would also be interesting to combine with a mechanism for sample-dependent ICL optimization to further enhance performance and reduce cost we defer these important directions to future work.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We thank all colleagues from Google Cloud Al Research for their valuable feedback. We also thank the anonymous ICLR reviewers and area chairs whose feedback has been instrumental in improving this work.
REFERENCES
Rishabh Agarwal, Avi Singh, Lei M Zhang, Bernd Bohnet, Stephanic Chan, Ankesh Anand, Zaheer Abbas, Azade Nova, John D Co-Reyes, Eric Chu, et al. Many-shot in-context learning. arXiv preprint arXiv:2404. //018, 2024.
Cem Anil, Esin Durmus, Mrinank Sharma, Joe Benton, Sandipan Kundu, Joshua Batson, Nina Rimsky, Meg Tong, Jesse Mu, Daniel Ford, et al. Many-shot jailbreaking. Anthropic, April, 2024.
Anthropic. The claude model family: Opus, sonnet, haiku. 2024.
Maximilian Balandat, Brian Karrer, Daniel Jiang, Samuel Daulton, Ben Letham, Andrew G Wil- son, and Eytan Bakshy. Botorch: framework for efficient monte-carlo bayesian optimization. Advances in neural information processing systems, 33:21524-21533 20200
Amanda Bertsch, Maor Ivgi, Uri Alon, Jonathan Berant, Matthew R Gormley, and Graham Neu- big. In-context learning with long-context models: An in-depth exploration. arXiv preprint arXiv:2405.00200, 2024.
Joseph Bowman Jr. On the relationship of the tchebycheff norm and the efficient frontier of multiple-criteria objectives. In Multiple Criteria Decision Making: Proceedings of a Conference Jouy-en-Josas, France May 21-23, 1975, pp. 76-86. Springer, 1976.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In H. Larochelle. M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neu- ral Information Processing Systems, volume 33, pp. 1877-1901. Curran Associates, Inc., 2020. URL
neurips cappaper files/paper/20277 ppf
file/
Kaiwen Chen, Yueting Chen, Xiaohui Yu, and Nick Koudas. Reliable text-to-sql with adaptive abstention. arXiv preprint arXiv:2501.10858 2025.
Wei-Lin Chen, Cheng- Kuang Wu, Yun-Nung Chen, and Hsin-Hsi Chen. Self-ICL: Zero-shot in- context learning with self-generated demonstrations. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.). Proceedings of the 2023 Conference on Empirical Methods in Natural Language Pro- cessing, pp. 15651-15666 Singapore. December 2023. Association for Computational Linguis- URL https: //tss///ccc / www.llnnhhooggg orgh22203.rrg//233...
tics. doi: 12111665.1//22222mmmmmmaaaaa
emmn 1mmnlpmma 968
Tinkle Chugh. Scalarizing functions in bayesian multiobjective optimization. In 2020 IEEE
Congress on Evolutionary Computation (CEC), pp. 1-8. IEBE, 2020.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Rejichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2100 14.66. 2021.
Rajarshi Das. Manzil Zaheer, Dung Thai, Ameya Godbole, Ethan Perez, Jay- Yoon Lee, Lizhen Tan, Lazaros Polymenakos, and Andrew McCallum. Case-based reasoning for natural language queries over knowledge bases. arXiv preprint 104 2021.

---

Published as a conference paper at ICLR 2025
Samuel Daulton, Xingchen Wan, David Eriksson, Maximilian Balandat, Michael A Osborne, and Eytan Bakshy. Bayesian optimization over discrete and mixed spaces via probabilistic reparame- terization. Advances in Neural Information Processing Systems, 35:12760-1277771 2022.
Peter Frazier, A tutorial on bayesian optimization. arXiv preprint
2018.
Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig. Pal: Program-aided language models. arXiv preprint urXiv:2211.10453 2022.
Jacob Gardner, Geoff Pleiss, Kilian Q Weinherger, David Bindel, and Andrew G Wilson. Gpytorch: Blackhox matrix-matrix gaussian process inference with gpu acceleration. Advances in neural information processing systems, 31, 2018.
Roman Garnett. Bayesian optimization. Cambridge University Press, 2023.
Shahriar Golchin, Mihai Surdeanu, Steven Bethard, Eduardo Blanco, and Ellen Riloff. Memoriza- tion in in-context learning. arXiv preprint arXiv:2408. /1546, 2024.
Francisco Guzmán, Peng-Jen Chen, Myle Ott, Juan Pino, Guillaume Lample, Philipp Kochn, Vishrav Chaudhary, and Marc' Aurelio Ranzato. The FLORES evaluation datasets for low- resource machine translation: Nepali English and Sinhala English..
Kentaro Inui, Jing Jiang. Vincent Ng. and Xiaojun Wan (eds.), Proceedings of the 2019 Conference on Empir- ical Methods Natural Language Prucessing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLPP) pp. 6098-6111, Hong Kong, China, Novem- ber 2019. Association for Computational Linguistics. doi: 10. 10.18653/11/D11--663 URL.
Nepali-English
Jesse Michael Han, Igor Babuschkin, Harrison Edwards, Arvind Neelakantan, Tao Xu, Stanislas Polu, Alex Ray, Pranav Shyam, Aditya Ramesh, Alec Radford, al. Unsupervised neural ma- chine translation with generative language models only. arXiv preprint arXiv:2110.05448, 2021.
Zeyu Han, Chao Gao, Jinyang Liu, Sai Qian Zhang, et al. Parameter-efficient fine-tuning for large models: A comprehensive survey, arXiv preprint arXiv:2403. 14608, 2024.
Yaru Hao, Yutao Sun, Li Dong, Zhixiong Han, Yuxian Gu, and Furu Wei. Structured prompting: Scaling in-context learning 1,000 examples. arXiv preprint arXiv:2212.06713 2022.
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. arXiv 2021.
preprint arXiv:2203.0000
Edward Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. arXiv preprint arXiv:2106.09M0 2021.
Edward J Hu, Moksh Jain, Eric Elmoznino, Younesse Kaddar, Guillaume Lajoie. Yoshua Bengio, and Nikolay Malkin. Amortizing intractable inference in large language models. arXiv preprint arXiv:2310.04:: 2023.
Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. arXiv preprint arXiv:2310.06825, 2023.
Yixing Jiang, Jeremy Irvin, Ji Hun Wang, Muhammad Ahmed Chaudhry, Jonathan H Chen, and Andrew Y Ng. Many-shot in-context learning multimodal foundation models. arXiv preprint 0797992405.09798, 2024.
Omar Khattab, Amav Singhvi, Paridhi Maheshwari, Zhiyuan Zhang, Keshav Santhanam, Sri Vardhamanan, Saiful Haq, Ashutosh Sharma, Thomas T Joshi, Hanna Moazam, et al. Dspy: Compiling declarative language model calls into self-improving pipelines. arXiv preprint arXiv:2310.03714 2023.
12

---

Published as a conference paper at ICLR 2025
Joshua Knowles. Parego: A hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems. IEEE transactions on evolutionary computation, 10(1): 60-66, 2006.
Alex M Lamb, Anirudh Goyal ALIAS PARTH GOYAL, Ying Zhang, Saizheng Zhang, Aaron C Courville, and Yoshua Bengio. Professor forcing: new algorithm for training recurrent net- works. Advances in neural information processing systems, 29, 2016.
Jinhyuk Lee, Zhuyun Dai, Xiaoqi Ren, Blair Chen, Daniel Cer, Jeremy R Cole, Kai Hui. Michael Boratko, Rajvi Kapadia, Wen Ding, et al. Gecko: Versatile text embeddings distilled from large language models. arXiv preprint 240::::200.20222. 2024.
Itay Levy, Ben Bogin, and Jonathan Berant. Diverse demonstrations improve in-context compo- sitional generalization. In Anna Rogers, Jordan Boyd-Graber and Naoaki Okazaki (eds.), Pro- ceedings of the 6l Annual Meeting of the Association for Computational Linguistics (Volume 1; Long Papers), pp. 1401-1422, Toronto, Canada, July 2023. Association for Computational Lin- guistics. doi: 10. 10.18653//1/2023.ck wwt.22223.ccllllee 2ong. acl ong. 78
Jinyang Li, Binyuan Hui, Ge Qu, Jiaxi Yang, Binhua Li, Bowen Li, Bailin Wang. Bowen Qin, Ruiying Geng, Nan Huo, et al. Can Ilm already serve as a database interface? a big bench for large-scale database grounded text-to-sqls. Advances in Neural Information Processing Systems, 36, 2024a.
Mukai Li, Shansan Gong, Jiangtao Feng, Yiheng Xu, Jun Zhang, Zhiyong Wu, and Lingpeng Kong- In-context learning with many demonstration examples. arXiv preprint arXiv:2302.0499 2023.
Zhuowan Li, Cheng Li, Mingyang Zhang. Qiaozhu Mei, and Michael Bendersky. Retrieval aug- mented generation long-context Ilms? comprehensive study and hybrid approach. arXiv preprint arXiv:2407.16833, 2024b.
Ziqian Lin and Kangwook Lee. Dual operating modes of in-context learning. In Ruslan Salakhut- dinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference on Machine Learning, vol- ume 235 of Proceedings of Machine Learming Research, pp. 30135-30188. PMLR, 21-27 Jul 2024. URL httptttst//pooeeeee
mlr wtwppppseww//ii2222222 .htmll
Jiachang Liu, Dinghan Shen, Yizhe Zhang, Bill Dolan, Lawrence Carin, and Weizhu Chen. What makes good in-context examples for GPT-3? In Proceedings of Deep Learning Inside Out (Dee- LIO 2022): The 3rd Workshop on Knowledge Extraction and Integrution for Deep Learning Ar- chitectures, pp. 100-114, Dublin, Ireland and Online, May 2022. Association for Computational Linguistics.
Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp. Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), Proceedings of the 60th Annual Meet- ing of the Association for Computational Linguisties (Volume 1: Long Papers), pp. 8086-800 8098,, Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: 10. 10.18653/112022. acl-long.556. URL htthhttp:// /atttss:/aacanttaee hwt.//oooc.ttoooy....o..oooo.oo. org/2022 acl -ong--loon... 556
Max Marion, Ahmet Üstün, Luiza Pozzobon, Alex Wang, Marzieh Fadaee, and Sara Hooker. When less is more: Investigating data pruning for pretraining 1lms at scale. arXiv preprint 2rXii:2309.04564, 2023.
Krista Opsahl-Ong, Michael Ryan, Josh Purtell, David Broman, Christopher Potts, Matei Zaharia, and Omar Khattab. Optimizing instructions and demonstrations for multi-stage language model programs. arXiv preprint arXiv:2406. 16695, 2024.
Biswajit Paria, Kirthevasan Kandasamy, and Barnabás Póczos. A flexible framework for multi- objective bayesian optimization using random scalarizations. In Uncertainty in Artificial Intelli- gence, pp. 766-776. PMLR, 2020.
13

---

Published as a conference paper at ICLR 2025
Ajay Patel, Bryan Li, Mohammad Sadegh Rasooli, Noah Constant, Colin Raffel, and Chris Callison-Bunie Bidirectional language models are also few-shot learners. arXiv preprint arXiv:2209.14500 2022.
Mohammadreza Pourreza, Hailong Li, Ruoxi Sun, Yeounoh Chung, Shayan Talaei, Gaurav Tarlok Kakkar, Yu Gan, Amin Saberi, Fatma Ozcan, and Sercan Arik. Chasc-sql: Multi-path reasoning and preference optimized candidate selection in text-to-sql. International Conference Learning Representations (ICLR), 2025.
Machel Reid, Nikolay Savinov, Denis Teplyashin, Dmitry Lepikhin, Timothy Lillicrap. Jean- baptiste Alayrac, Radu Soricut, Angeliki Lazaridou, Orhan Firat, Julian Schrittwieser, et al. Gem- ini 1.5: Unlocking multimodal understanding across millions of tokens of context. arXiv preprint 24X3::2003.05500, 2024.
Ohad Rubin, Jonathan Herzig, and Jonathan Berant. Learning to retrieve prompts for in-context learning. Marine Carpuat, Marie-Catherine de Marneffe, and Ivan Vladimir Meza Ruiz (eds.), Proceedings of the 2022 Conference of the North American Chapter of the Association for Com- putational Linguistics: Human Language Technologies, pp. 2655-26711 Seattle, United States, July 2022. Association for Computational Linguisties. doi: 120.8865/11/0222.aaaclmmmm URL
ortp:y...rr//// 2022 maaci-maing 191
Wojeiech Samek, Grégoire Montavon, Sebastian Lapuschkin, Christopher Anders, and Klaus- Robert Müller. Explaining deep neural networks and beyond: A review of methods and applica- tions. Proceedings of the IEEE, 109(3):247-278, 2021.
Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based local- ization. In Proceedings of the IEEE international conference on computer vision, pp. 618-626, 2017.
Karen Simonyan. Deep inside convolutional networks: Visualising image classification models and saliency maps. arXiv preprint arXiv: 1312.6631 2013.
Ralph E Steuer and Eng-Ung Choo. An interactive weighted tchebycheff procedure for multiple objective programming. Mathematical programming. 26:326-344 1983.
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In International conference on machine learning, pp. 3319-3328. PMLR, 2017.
Xingchen Wan, Vu Nguyen, Huong Ha, Binxin Ru, Cong Lu, and Michael A Osborne. Think global and act local: Bayesian optimisation over high-dimensional categorical and mixed search spaces. In International Conference on Machine Learning, pp. 10663-10674 PMLR, 2021.
Xingchen Wan, Ruoxi Sun, Hanjun Dai, Sercan Arik, and Tomas Plister, Better zero-shot reason- ing with self-adaptive prompting. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.). Findings of the Association for Computational Linguistics: ACL 2023, pp. 3493-3514 Toronto, Canada, July 2023a. Association for Computational Linguistics. doi: 10.18653/11/2023. Andings-acl.216. URL https:ttt//.m anttt www.oogg..ooooooooo..o...o.oo...
f mndindnngsssa acl 216
Xingchen Wan, Ruoxi Sun, Hootan Nakhost, Hanjun Dai, Julian Eisenschlos, Sercan Arik, and Tomas Plister. Universal self-adaptive prompting. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Proceedings ofe the 2023 Conference Empirical Methods in Natural Language Pro- cessing, pp. 7437-7462, Singapore, December 2023b. Association for Computational Linguis- httpttpss///cllathllllgg////////
tics. doi: 10. 10.18653//1/2023..oom main.461........... emm main. 1.....46. 461
Xingchen Wan, Ruoxi Sun, Hootan Nakhost, and Sercan O. Arik. Teach better or show smarter? instructions and exemplars in automatic prompt optimization. In The Thirty-eighth Anmual Conference on Neural Information Processing Systems, 2024. WRLLtttpss///peneeeee pet//forum2id==atoo...
14

---

Published as a conference paper at ICLR 2025
Yizhong Wang, Yeganch Kordi, Swaroop Mishra, Alisa Liu, Noah A. Smith, Daniel Khashabi, and Hannaneh Hajishirzi. Self-instruct: Aligning language models with self-generated instructions. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.). Proceedings the 6l Anmual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 13484- 13508, Toronto, Canada, July 2023. Association for Computational Linguisties. doi: 10.18653/ al/202..acl-longe /tt.a//tttttttt/aaaaaooooooooooo
URL https: /aaaaaaaaannttooooooooooeoo wwgp//22..g2222033 acl- 754
Christopher Williams and Carl Rasmussen. Gaussian processes for regression. Advances in neural information processing systems, 8, 1995.
Christopher Williams and Carl Edward Rasmussen. Gaussian processes for machine learning. volume 2. MIT press Cambridge, MA, 2006.
Mengzhou Xia, Sadhika Malladi, Suchin Gururangan, Sanjeev Arora, and Danqi Chen. LESS: selecting influential data for targeted instruction tuning. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. URL
net Seeet/oorrmiddddSEESSS.
Xin Xu, Yue Liu, Panupong Pasupat, Mehran Kazemi, et al. In-context learning with retrieved demonstrations for language models: survey, arXiv preprint arXiv:2401. 2024.
Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. STar: Bootstrapping reasoning with reasoning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Ad- vances in Neural Information Processing Systems, 2022. URLaatpss:/ppenneeeeee..oo forum?ide Borum??d==3E_RG22233
Dawei Zhan and Huanlai Xing. Expected improvement for expensive optimization: review. Jour- nal of Global Optimization, 78(3):507-555 5440077-54444 2020.
Zhuosheng Zhang, Aston Zhang, Mu Li, and Alex Smola. Automatic chain of thought prompting in large language models. In The Eleventh International Conference on Learning Representations, 2023. htttps::/openeeeii.eeeee.
net wttp///oommmioooeeeee..oo..ooima 5NTt 8GF 8GF JUHKI
Zihao Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh. Calibrate before Improving few-shot performance of language models. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, pp. 12697-12706, 2021.
Han Zhou, Xingchen Wan, Yinhong Liu, Nigel Collier, Ivan Vulié, and Anna Korhonen. Fairer pref- erences elicit improved human-aligned large language model judgments. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pp. 1241-1252, Miami, Florida, USA, November 2024a. Association for Computational Linguistics. doi: 1/2/5/3////222.mmmllllpp https://acclanthooooe
URL
2024 2 ma in. 727
Han Zhou, Xingchen Wan, Lev Proleev, Diana Mineu, Jilin Chen, Katherine A Heller, and Subhrajit Roy. Batch calibration: Rethinking calibration for in-context learning and prompt engineering. In The Twelfth International Conference on Learning Representations, 2024b. URL https:
7/ //openeeview.o wttp::eeeeeeoommmnnommtmt...
15

---

Published as a conference paper at ICLR 2025
A DERIVATION OF THE APPROXIMATED IMPORTANCE SCORE
In this section, we give detailed derivation of the importance score used in Sec. 2 to rank the ex- amples. Recalling that we are given a pool of examples & with |&| m, a collection of T subsets of e;, each represented as a binary vector e; E {0, 11 and their corresponding scores on the validation set g(.) (0.1) m + R. we first fit a GP regression with C1:T" [e1,..., er. and g1.7 (g(e1, .... ((e)) presented in Eq. 2 the mean of the posterior GP g(-) is given by:
Eg(o))r> [o()] k1.1 (K= gITT
where we define Gr as the shorthand of [e1:T: g1:T] denote that the fitted function g(e) is fitted on the observed input-oulput pairs; k, = [k(e, of the GP (we use Matern 2.5 by default). As mentioned in Sec. 2 whereas we do not assume any differentiability property from g()) on since the approximated function ğ(-) follows a posterior GP, its gradient w.r.t is analytically available and itself GP, given by:
k(e, et)] and k(.,-) ) is the covariance function
ag(e) de
AkiT (K 11-1)1111::1 gI:T, de
veg=
noting that the expensive matrix inversion term, (K + 11 does not have a dependence on and can be directly cached from Eq. 3 when we compute the posterior mean. The derivative term is essentially a differentiation operation of the covariance function to the input, and can be easily computed either analytically for common kernel choices or via automatic differentiation for popular GP or BO packages like gpytorch (Gardner et al. 2018) or botorch (Balandat et al.) 2020).
With the computed Veg E Rm we can in principle compute the estimated derivative at any e S E. However, in practice, we find the derivative estimate to be more reliable at the training points of the GP (i.e., .e., eT). We then evaluate the derivative at each of the training point, and the final importance score is marginalized by averaging across the training points:
M(e - Σ Vegll
Vollo
(5)
where we use the superscript (j) to denote that the estimated importance of the j-th individual example (note the regular font E & denoting an individual example instead of the bold-face
denoting a set of examples in E). We then compute the importance score of all examples in E, which is then used to generate the assigned ranking in the analysis of Sec. tec.p]sse such as the Fig.
B IMPLEMENTATION DETAILS
B.I DATASETS.
In the section below, we give detailed implementation details for the availability, data splitting pro- tocol, input prompts and licensing information of the datasets used.
BIG-Bench Hard (BBH). BBH is a collection of 26 challenging reasoning tasks, and a task is selected if either 1) if it is studied in the seminal work many-shot ICL. (Agarwal al., 2024 or 2) if the zero-shot performance of gemi n 1111-111 1115-proc 5-pro-000 001 is below 90%, which indicates non- saturation of performance these criteria led to a set of 16 tasks that we consider in Sec. 4 For all tasks, we randomize the data points and reserve 40% (usually 100 samples, but some sub-tasks of BBH benchmark have fewer data-points) as held-out sets for testing, whose inputs and labels are not revealed to the model except for final evaluation. For the rest of the dataset, in Sec. [2] we use 50% (30% of all available data points including the held-out test set) as the "train-set" from which the examples are generated and the other 50% for validation (i.e., the split where results in is generated). In Sec. 4 we do not use the aforementioned validation set and use performance on the same set that generates the examples as the optimization objective. The BBH dataset is publicly available at hhtpss: /ttp://gghhhba
wwtp///uzgumiraaaaaaaaaa BenGG-BBech--- Hard under an the prompt templates below:
MIT license. For all BBH tasks,
will be given question. Think step by step before giving final ansver this question Show your final answer [( _aa_ssPECIFIC,C caclic__ooSSSeee CONSTRAINTS )] between <answer> and <\enswer>>
16

---

Published as a conference paper at ICLR 2025
EXAMFLES )
==
QUESTION }}
EE 11m() )1
Jinja2-style syntax and the upper-cased blocks bracketed between double braces are variables that are replaced at inference time: SESSK_SPEIFFICCCOO w...NSSSSINNTSS denote the constraint instruction specific the type of the task. For example, for multiple-choice task, this is replaced with "answer option letter only"; ; for a binary choice question, this is replaced with "Yes or No only" and for free-form generation task, this is replaced by an empty string. EXAMPLES denote the concatenation of any examples added to the input for the initial generation step (i.e., Step 3 in Algorithm D we use zero-shot prompting and EXAMPLES generation step. this is replaced with the concatenation of the examples selected by BRIDGE; finally, 11m () denotes the place where an LLM response is solicited; answer is then extracted and postprocessed match with ground-truth answer measure accuracy.
where
an empty string. For subsequent
MATH and GSM-Hard. In MATH and GSM-Hard, we similarly adopt the unified train set setup as mentioned in the previous paragraph. To minimize the chance of data contamination where the training imputs and outputs were leaked to the model during pre-training or instruc- tion finetuning, randomly sample 128 samples as the official test set the train set from which the examples are generated and use the rest of the official test set for testing. The MATH dataset is available https:: /ttp:::///gttutu com www.erncsssmmaaaaaee and Gard is available at https::
cttisssrressoinnn hawaasonnn--mcccineeeeee machines gsm hard Both datasets are license under an MIT license. On GSM-Hard, use the same prompt as the BBH dataset mentioned above. On MATH, we use the inner monologue prompt consists of human- annotated few-shot prompt given by Agarwal al. (2024) with an added preamble to ensure that the LLM generation follows the style of the examples given, noting that any model- sedee--enerated examples will be added to the initial human-annotated examples:
You will be given several example math questions and their solucions. At the end, You will be given another question that you will need salve. Make you follow the examples, and always riniah your answer with 'Pinal Answer: The final answer is X. hope it 18 correct answez.
correct.'
Problen:
Find the donain the expression (V
Solution:
need find domain of expression.
10 This expresaion has two square root expressi ons.
12 know the values under each aquare roat must be ron-negatiive.
14 So let me start by ensuring that.
15
16 set 5x-2 \go 06, which simplifies to $x1go26.
17
18 Then,
35 \go which simplifies Ale 5s.
19
need make sure the denominator is sero.
21
22 So, 95-x$
greater than zero, gives 8x<5s.
23
24
Therefore, the domain the expression is s\boxed (2, (2,5)
25
26 Anawer: $12, 5)..
28 Finel Answer: The final answer is $12,5)$ hope it is correct.
29
30
31 Probles:
32 If \det \mathbf(A) and didet (nathbé(B) 82, then find Sidet (AmechbE(A) \mathbf(B))
33
Solution:
35
16
to the determinant product of matrices B.
37
38 remember that the determinent of the product of two metrices equals the product of their determinants.
39
17

---

Published as a conference paper at ICLR 2025
So, Sidet (AmecchE(A) (mathbf(s)) (Adet \mathbf [A]) (Adet \mathbE(a)) (2) (12) Vboxed (24)
42
Answer: $218.
43
44
Final Answer: The final 8245. hope it
"**,
45
""*"Problem:
usually twe 20-pound weights times. uses twc 15-pound weights instead,
how many times muat Terrell lift then in order to 1ift the aame total weight?
47
48
Solution:
49
51
Okay, so Terrell litta total of $2Nodot 12Vodot20-4885 pounds of weight with the 20-pound weights.
52
53
Well, if switches Le 15 pound weights, the total weight lifted will be 92Noot115edo x -30n8 pounds, where is the number of lifts.
54
find the number of lift,, nr the total weight lifted the
56
equate $30m$ pounds and selve n.
98
59
\beginialign+
30n6=48011
61
|Rightarrow'egun
tend(aligne:
63
Ansver:
65
66 Final Answer: The final answer is 8155. hope it is correct.
68
Problem:
10 If the system of equations
71
12 Abegin(align
23 6x-dys=a,
34 6y-9x &=b.
15 \end(aligns)
77 has solution 9 (x, yl where $x0 and Sy$ are both nonzero, find S\Frac((a (b), assuming $b5 nonzero,
18
79 Solution:
81 I'm given aystem of Lwo equations.
83 see that if multiply the first equation by (2) 1'11 get another equation that has same laft-hand sida as the sacond equation, $6y-9x5.
84
85 Let me try that
87 Ab, also know that s8y 9x-bs, so can equate these two equations.
89
frac htt.g//...w......oooooooooooeoee (b Answer: (2)
So, 39-1frac13)
92
Final Answer: rinal answer 13)1ra hope is
98
96
(1 EXAMPLRS )1
97
98
99 Problem:
QUESTION }}
101
103
1: 11m }}
BIRD On BIRD, randomly sample 128 samples from the train split the unified train and validation set and use the official test set (of 1534 data points) for testing. Since BIRD is code generation task, the execution accuracy is computed not via simple string match between the predicted and the ground-trun truth SQLs but by actually executing both SQLs on the database provided, and score of is only assigned when the predicted SQL both executable and if whose results exactly match the execution results from the ground-truth SQL. All data, including the databases.
18

---

Published as a conference paper at ICLR 2025
schemas and ground-truth gold SQL available at the official repo: / github. io under a CC BY-SA 4. 0 licence. With reference to Table use two prompt versions for different rows. The direct prompt is standard, zero-shot prompt elicit the SQL prediction
directly; it is used both for the "Direct" row to directly extract LLM answer and is also used as the prompt template for finetuning in the different "LoRA" rows:
are a squ expezt tasked with answering user's questicns about squ tables by genezating squ queries in the SCLITE dialect.
only the following tables answer the question:
SCHEMA 1:
Question: QUESTICN
sint: (1 BINT )1
BOL: 1. 1im() F:
where SCHEMA refers to the table schema, which can be generated automatically by querying the database, QUESI TON is the natural language question that we would like the LLM to convert to a SQL command and HINT is hint which additionally explains the question provided by the BIRD dataset. For the CIASE and CHASE BRIDGE rows, we use the prompt template proposed in Pourreza et al. (2025) to invoke reasoning and divide-and-conquet before the LLM gives the final answer:
You are experienced database expart.
Now you need to generate a sQL query given the datebase information, question and some additional information.
The databasa structure is defined by the fo lowing table schemas icomments ofter provide descriptiors).
additional
Note that the "Example Values" are actual values from the column. Some colurn might costain the values that directly related the question. use help you justify columns to use.
Given the table schema information description and 'Question'. You will given table creation statements and you reed understand the databsse and co umns.
You will be using netural language".
called "recursive divide-and and--nn--aae conquer approach to sqi query generation
10 Here is a high level description the steps. +edivide (Decampese Sub-question with Psaudo sQt) The cemplex natural language question is recursively broken dowa into aimpler sub-queations. Each sub-question targeta a specific piece informatien or logic requized
final SQL query.
12 2. CoCoquer (Real sQL for sub-questions) :*v For each sub-question (and the main question initially), a "pseudo-801" fragment is formllated. intended sot, logie but might have placeholders for answers to the decomposed sub- questions.
psaudo-SQt. represents
13 Combinn (Reassemble)
resolved their correapond' rg sor Cragments are generaled, the process reverses. The SQL Tragments are recuraively combined by replacing the placeholders the pseudo-S22 SQL the actual generated sQL lower levels.
all sub-questiors
14
AxPinal Outpot:A* that answers the original complex queation.
bottom-up assembly culminates the complete and correct 501 query
15
16 Database admín instructions Iviolating any of following is punishable death!):
17 1. A*SELEC Clause:*x
mentioned Avoid unnecessary columns or values. 20 Agggregation (MAX/MTN) SAN
18
Only
questien.
19
21
Always forn JOINs before using MAX MIN!!
22 3. ++ORDER BY with Distinct Values:*.
'GROUP BY
before 'ORDER <column> ASCIDESO to ensure distinct values.
24 4. a Handdinn HULLS:A+
Lf column may contain Null values (indicated by "None" in value examples explisitly
1, use "JIN* or WHERE <calymns IS NOT NUT..".
26 5. *-FOO//OONN Clauses:**
27 Only include tables essensisl answer the question.
28. 6. *+Strictly Follow Hints:as
Adhere 31 Addreas acnditions menticned the question,
provided
30 7. Ahhorough Question Anslysis:av
32 8. **NTTTTCT Reywords**
33 Use 'SELECT DISTINCT* when the question requires unique values (e.g., IDs, CRLs).
34 Refez to column statistics ("Value Statics") determins if 'DISTINer" is necessasy.
35 9. A+Column selectien::s
Carefully analyze column descriations
choose the correct coluna
similar colurns exist across tables.
37
**String concatenacion:
38
Never use *I1 r !1 ocher method to concatenate atrings in the 'SELECT clause.
19

---

Published as a conference paper at ICLR 2025
JOIN Preference:**
40
Prioritize 'INNR JOIN' over nested "SELECT" statements.
12. **SoLite Punctions Only:**
42
Use only functions available in Squite.
43
13. +*bate Processing:**
Utilize "STRPTINE!)" for date manipulation (e.g.r "STRPTINE/' BY", SOMETINE] the year).
46
When you to the final query, output the every string ONLY insida the xm delimteer < ANNAL_ANGRRO
47
48 Here are some examples:
50
1:
EXAMPLES }
52
Now is the real question, rollowing the instruction and examplea, generate the SQL with Recursive Divide and Conquer approach.
53
54 [Table creation statements)
11 SCHEMA
56
98 [Question]
59 Question: I: QUESTION };
sint: (1 HINT
61
63 [Answer]
sepeating question hint, generating squ Recursive uivide-and-Cenguee..
65 1.
11m1) })
Similar to the inner monologue prompt the MATH dataset, the EXAMPLES in the template above also include 4 human annotated examples at initialization (an exemplary human-annotated exam- ple shown the code snippet below); any model-generated examples from BRIDGE are again concatenated to the human annotated examples at inference.
[sable creation statements] TARLE genaralin"o
rd_sestuurant INTEGER not null primary key, food_type TEXT mull, exemples: "thai 'I 'food type" descripsion: the food type city TEXT mull, -- ponriptionn the city where the reataurent: la looated in
10
CREATE TABLE location
11
12
re_testaurant INTEGES not null primary key,
streat_nane TEXT mull, examples: 'ave', 'san pablo ave', 'pablo ave'l 'streat
deacription: the street name of the restaurant city mull, description: forelgn key (1d (Id_restaurant) re rererences general rfo (id_restaurant) on update casoade on delete cascade,
city
restaurent located
15
16
17
18
19
[Question]
Question: нои many restourents can found San Ave, Albony?
21
Hint: Thai restaurant reters to food_type 'thai"; San Pablo Ave Albany retera to atreet_name 'san pable ave' AND Tl.city 'albany"
22
23
W.A.AAAAAAAAAAAAAAAA.
[Answer]
25
Repeating the question and hiat, and generating the SQL with Recursive Divide and Conquer.
found San Pablo Ave, Albany? xvllintvr: Thai restaurant relers to Tood_type "thal' San Pablo Ave Albany relers to stree=_name sen pablo ave! AND 11.city 'albany'
Qoasttoonn:: many That restaurants
27
28
29 .1.
Divide and Conquer:*.
31
*iinn Question:** foow many Thai restaurants can be found in San Pablo Ave, Albany? v>Ana <rAnalysis:es The question aska for a count restauranta, so we" use 'COUNT for that. The count should include only Thei restaurents, which
32.
identify using the
food_zype' celumn in the 'gereralinfo" table. The location "San Pablo Ave, Albany" spans columns ('streat_nanc and "mity") in the "lecation' table, requiring these two tables.
join
v*Feeudo SQL:++ SELECT COUNT restaaaa))))) FROK 'generalinfo' 121" JOIN
"locationn AS 'T2" ON 'I1", 'id restaurant - 9T2,, idd WHERE <Thai restaurant>>
san ave, Albeny>
34
20

---

Published as a conference paper at ICLR 2025
sub-question
restaurant
36
-vnnalysias This i5 atrai straightforsord filter on the 'generalinfo' table using the 'food_type" column.
37
AvPseudo SQL:v> "TI", "Eoed_yype" "thai'
38
visub-question in Pablo Albany
40
AvAnalya AvAnnayytaiva This location information la apread across two colurns in the
location tabla. both are met.
to
conditicns
operator to ensure
41
A>Pseudo SQL:.* 'T2', "sareet_name" rsan pablo ave! AND 'T2", "city" 'albany'
42
43
+2. Assembling SQU:**
44
45
..Bub quub-iueetion 1 (Thal restaurant) i4y
** "food_type" 'tha!'
47
18
r4Bub question 2 (in San Pablo Ave, Albany):44
49
v*gQu:** 122 'stzeet_name" 'san pablo ave' AND 1121, 'city' 'albany'
50
*aMain Question lcount restaurants)
52
+. SELECT COUNI''T1', 'id_ 1I PROM "generaliate" AS 'TI' INNER JOIN location" 'I2'
restaurann 'I2". vid_restaurant" "thal" AND 'T2", "stzeet_aame" 'san pablo ave' AND 'I2", "city" 'albany"
'food_type"
53
+... simplification and optimizatien::
55
query step already efficient. tables based on thei: relationship, and the 'WHERE" clause clearly defines our filtering nested queries complex sub-seleetions this case.
used 'INEER JOIN combine
criteria.
no
57
58
*+iina Optimized SQL Query:**
60
<FTMAT, A
AMSWER>
(ddsssaeas generalinIo INNER lccation ON id_cestaurant 12. id.iitrestauren WHERE fo_d 'thei' AND Tl.city 'albany' AND 12.street_nend sean pablo
62
ANSKER
B.2 IMPLEMENTATION DETAILS OF THE INFILLING BASELINE
Infilling is a technique of generating the intermediate outputs given both input queries and the ground-truth answer this is used as baseline in Tables I and where we utilize all available labeled data in the context. Concretely, we use the following prompt adapted from Hu et al. (2023) to generate the intermediate rationales.
You will be given question and its final, groune-truth correct answer. Given question
answes, generate slep by step reascning correct answer. Write your intermediate reasening steps (but NoT the finsl snswez) answer between <answar> and </answer>.
the
leading to the
Questions I question 11
Answer: target F3
Steps: If 1iml)) 11
C ADDITIONAL EXPERIMENTS AND RESULTS
C.I ABLATION AND SENSITIVITY STUDIES
Importance of Bayesian optimization. To ablate BRIDGE, in Table 6 and Table compare against a simplified variant of BRIDGE with BO replaced with random search consuming the same evaluation budget (32 per stage) we find that while random search is remarkably strong baseline, BO nevertheless outperformed consistently all stages the BRIDGE pipeline.
Comparison to and combination with heuristic demonstration selection. An alternative to it- cratively optimize the demonstrations the "Optimize" step is using heuristics for demonstration selection which may incur lower computational cost as we longer have to repeatedly evaluate on the labeled validation set m times. In this section, we study two representative demonstration selection techniques: retrieval based similarity in the embedding space and diversity, and both study them as standalone alternative to the full BRIDGE pipeline and, given that demonstration selection is not the only component of the BRIDGE framework, it is also straightforward to combine
21

---

Published as a conference paper at ICLR 2025
Table 5: Comparison between BRIDGE with BO (BRIDGE-BO) and BRIDGE with random search (BRIDGE-RS) using gemi mimini-11a 11-11... 5- flah--011 on BBH tasks. The BRIDGE-BO results are lifted from 3 and the last row denotes the average improvement due to the use of BO over RS the milestone in the progression of BRIDGE. Refers to captions of Table I for additional explanations.
Tasks
BRIDGERR
BRIDGE: BD
# Iterations
10
[G
20
2G
30
1o
1G
20
2G
30
causal_judeee judge__udeement
59. 30
66.216
67.7
63.0..1
64.0)
61.327
66.02.
63.3
65.0
65. 35,
understanding
84.8,
90.5us
93.3nu
93.0g7
94.5ux
85.0gs
90.50s
91.50a
90.8u7
92.5us
di disambiguation.pp
73
14.5
74.0h.
75.30a
70.5
77.513
79.0
77.51.
76.3ux
74.3
dyck Janguaggs
64.5,
62.5%
65.5.a
64.8..1
68.00 5
63.32n
62.0n.
64.5 a
62.81
61.8s8
formal fallaciees
75.026
74.5
77.5
78.325
78.3
77.31.
75.5
78.31a
76.3us
geometric.shapes shapes
88.5
93.3rn
94.5%.
98.0n.
95.311
93.82.
94.0..
95.5
97.0g0
98.0nm
hyperbaton
94.0g7
94.3uu
95.0g7
95.007
88.815
86.5
95.5
95.8ga
94.80.
93.315
Jedeuccddd (7)
62.893
54.522
67.81.
64.026
66.819
61.85.1
57.5
70.5o.
66.5
75.0kz
movie recommendatiion
68.5a0
75.326
72.5
77.51
77.518
70.3
73.3
77.31.
78.8.0
72.8s
multistepuurthmmtiic.oo
82.50.
92.31.
95.01.4
89.5,5
92.526
96.323
966.8o.4
97.8%a44
94.8ux
85.8
objecL.counting
9
92.51.
92.5
93.0g7
92.31.1
92.81M
93.83.1
95.501
93.01
93.8p1
ruin, names
89.012
08.
88.02.
87.0,2
84.5
89.3uu
89.30.
87.0
90.30x
90.012
66.37s
69.32s
67.0%..
68.5;
68.
62.8ux
71.0a.7
69.81
69.0g7
67.3u4
snarks
87.230
90.612
88.91.7
93.4,
91.016 6
88.92n
89.91,
89.607
90.6u6
83.7a5
96.5
96.3a4
97.3e.
95.80.4
26.808
93.311
95.30.4
80.4
95.012
95.0no
tracking shuffed objects (7)
98.30x
89.5uv
96.5
92.324
18
98.0u7
93.8
98.0ge
97.8u
97.5us
Averuge
80.31
81.55
83.11
82,98
82,97
81.61
82.79
83,79
83.77
83.25
A(BD RS)
+1.30
+1.24
+0.68
+0.79
+0.28
Table 6: Comparison between BRIDGE with BO (BRIDGE-BO) and BRIDGE with random search (BRIDGE-RS) using gemini --rro- 001 on BBH tasks. The BRIDGE-BO results are lifted from T and the last row denotes the average improvement due to the use of BO over RS at the milestone in the progression of BRIDGE. Refers to captions of Table I for additional explanations.
Tasks
BRIDCI-RR
BRIDGE- BD
# Iterations
10
1G
20
20
10
1G
20
2G
causal_ judgemmnt
66 66.2gn
68.52a
70.2g.4
69.514
70.82:
68.315
62.7G6
$9.7
72.0ku
70.02a
date understanding
88.4 88.42
94.3
94.112
90.3ga
94,3,,
92.2,5
97.0u.
94.8
95.0,2
95.5
disanbiguation qa
75.5.1
79.0s9
77.412
80,6
78.4c.
71.8a
77.5
80.5
81.3g
78.81
lyck.langssg
56.9Aa
59.649
67.543
64.940
70.4g1
49.2
76.2aM
80.0g7
77.5
76.81x
formal formalfaallaciss _fallacies
87.415
86.823
90.821
88.52a
88.822
86.021
85.025
90.82.
90.828
88.223
geometric_shupes
77.8
82.
818825
86.53.
85.524
78.52.
82.5
89.233
92.3
89 20.2
hyperbaton
94.31
93.124
94.2
94.9t.
94.0,1
96.5pM
94.2,
96.5ns
97.
logical deduction (7)
70.9s
68.377
66.6
71.9,
68.92.1
70.2,
70.8&s
71.777
71.518
69.2g2
movie recommennation
63.5a2
67.418
67.42.1
64.623
63.429
67.0
69.5u.5
69.3g,1
72.8
67.0,2
multistep tettiitepprrthmetiic.om _owo
97.3L1
97.5o.7
96.968
11.
97.9uu
96.203
94.5
97.0g3
98.0n.
96.818
object counttin
95.324
98.1.
97.3
97.3
95.42,
96.2n.4
96.0,
94.5
94.2n4
95.0uz
ruin names
86.617
86.51
88.91
89,9,
87.1
90.8.1
88.81
89.2
88.8
90.3ns
htt.__raaaatnnerraeeee dettecdettttionn
71.132
73.4
73.922
71.9
70.8
68.8gs
71.0077
69.5222
74.9b7
74.5
snarks
93.8ta
95.31.
96.0Lu
96.0,.
95.6 95.61.
93.4am
95.8un
95. 11.
96.915
97.618
sports understanding
93.51.2
94.196
95.169
95.9a0
96.0g,
92.819
97.0,
96. 96.2as
95. 81.8
95 80.
traking shuffled objects (7)
92.4a
94.4,
99.9u.
98.464
100.0.
95.8g4
95.0,
100.0.g
97.0u7
99.5us
Average
81.86
83.64
84.86
84.81
84.82
82.11
84.61
85.77
87.13
86,33
A(BO- RS)
+0,25
+0.97
+0.91
+2.32
+1.51
them with BRIDGE by swapping the BO/random search component in the "Optimize" step with these heuristics. Below we describe the implementation details of both techniques:
Retrieval: One popular demonstration selection method is via retrieval (Rubin et al. 2022 Das al. 2021). Concretely, we may either use an off-the-shelf pretrained embedding model (we use the latest Gecko embedding (Lee et al. 2024) for this purpose) or tune a customized retriever to obtain the nearest examples from an example store, typically by computing the vector embedding for each of the test queries and each of the cached demonstrations followed by a maximum inner product search (MIPS) to retrieve the top-k demonstrations based on cosine similarity. Unlike the optimization-bn based approach where the number of examples in the context can be determined automatically, here is a key hyperparameter that needs to be set by the user. In this case, consider 3 different & val- ues: = {10, 25} where the number of examples is fixed, or = All, where we use all available, correctly predicted examples this essentially uses the same set of examples as Reinforced ICL but in a specific, input-dependent order: the examples are sorted in an as- cending order based on the cosine similarity between the embedding of the test input and
22

---

Published as a conference paper at ICLR 2025
the example store and the most similar examples appears as the final demonstration that is directly concatenated to the test input.
Another popular learning-free free demonstration selection method is by selecting diverse examples. While multiple ways to measure diversity exist, here we use the tech- nique similar to the one used in ZZhan et al.] (2023) by 1) computing the embedding of all the available demonstrations and 2) the k-means clustering algorithm and select the & examples whose vector embeddings are nearest to each of the At centroids. Unlike re- trieval, there is no input dependency as the clustering algorithm does not depend on the input query but similar to retrieval, ic here is also a hyperparameter to be set and we again use k {10. 25). Note that we omit k All, as otherwise the number of clusters would be equal to the number of examples and we would be essentially be running Reinforced ICL with all available examples as demonstrations.
Diversity:
Since these demonstration selection baselines purely perform selection (i.e., the "optimize" step of BRIDGE) but neither the subsequent generations nor the iterative process, we first compare the BO demonstration selection (i.e., BRIDGE at Step 10) against these baselines and we show the results in Table Overall, we find that "Diversity" and "Retrieval", regardless of their hyperparame- ters, perform on par or slightly worse than Reinforced ICL. While the hyperparameter choice can sometimes lead significant differences on a per-task level, we also observe that when aggregated across the tasks, it does not lead to significant differences. On the other hand, the BO selection in BRIDGE outperform all these baselines. We believe there are two possible explanations leading to this out-performance. Firstly, while the heuristic-bair based methods have lower computational cost, key hyperparameters, such as the number of demonstrations to retrieve, need to be determined a- priori. However, as have shown in the main text at, for example, Fig. 4 the optimal number of demonstrations can be highly task-specific, and while iterative optimization- a higher cost, it is also capable of optimizing the number of demonstrations. Secondly, a key find- ing we have in Sec. is is that not all examples are equally helpful and removing some examples as in-context demonstrations can sometimes lead performance improvement during the "Optimize" stage. Again, while the souristic-based approaches do not necessarily use all demonstrations, it makes the selection choice purely from heuristic metric (c.g., similarity to test query) rather than from validation metric, and hence is incapable of removing these potentially "harmful" demon- strations from the pool of candidate examples.
selection incurs
However, beyond a simple comparison between a single stage of BRIDGE against these methods, is also worth noting that BRIDGE more than a demonstration selection method. As such, is also possible to combine these methods with BRIDGE by using them as drop-in replacement of the BO-based demonstration selection, effectively changing the implementation of the "Optimize" step only. To test this, we test two other variants of BRIDGE, named BRIDGE- RETRIEVAL and SAUDGE-DIVERSITE where we replace the "Optimize" step in each round with the heuristic-driver demonstration selection mentioned above and the aggregated results are shown in Table 9 whereas the task-specific breakdown of the best method in Table 1O- for conciseness, we only show the per-task breakdown for the best BRIDGE variant (BRIDGE-RETRIEVA, using all examples), which show that BRIDGE also works well with alternative demonstration selection method, although the advantage of optimization- based selection as shown in Lable&carric over when we use the selection as a component in the overall B BRIDGE pipeline.
Additional comparisons against iterative reinforced ICL in a restricted setup. To provide fur- ther evidence emphasizing the need for the "Optimize" step and to make sure that the additional gain of BRIDGE does not simply comes from the fact that BRIDGE may take advantage of more correctly predicted demonstrations in the validation set due to repeated sampling in the later iter- ations, we conduct a further experiment comparing BRIDGE and iterative reinforced ICL, but in a restricted setup with the support set restricted to the subset of the train set where the model pre- dicted correctly initially, instead of the entire train set. In other words, in subsequent iterations of BRIDGE and iterative reinforced ICL, both methods are restricted to make use of the subset of train set initially predicted correctly only as examples; we term these approaches "iterative reinforced ICL (restricted)" and "BRIDGE (restricted)" respectively, and we show the results in Table 7 On a high level, we found the result provides further evidence the importance of selection: Iterative Reinf ICL (restricted) without the "optimize" " step actually did not meaningfully improve over standard Reinf ICI. (average accuracy: 79.6%), BRIDGE (restricted), however, still meaningfully improves
23

---

Published as a conference paper at ICLR 2025
Table 7: Comparison of BRIDGE and iterative reinforced ICL in the restricted setup where the methods may only use the subser of the train set that the model initially predicted correctly. Experi- ments performed on gemini- 5-pro-001.
Tasks
Restricted Iterative Reinf.
Restricted BRIDGE
(Ours)
# Iterations
2
10
1G
20
2G
30
causal, judgemmtd
19.7
65.0
67.727
65.0
66.01.
67.0,.1
65.02a
bate_unddrstnnding
92.51.5
94.0
92.517
93.0
92.5t.
93.517
89.31.5
disambiguation.gg
74.0
75.83.
70.527
72.31.5
75.53z
71.82.
76.53.8
dyck Janguaags
59.06.
53.029
55,0s2
52.35.
56.534
57.5
60.33.8
formal fallacies
86.83.
90.52.2
85.315
90.5
83.032
83.50.9
85.52,
geometric shapes
75.3
78.33.1
75.026
80.545
81.34.
85.026
80.026
hyperbaton
85.34.0
84.53.4
94.016
95.808
91.81.3
93.026
97.0p.7
logical deduction (7)
67.5
69.02.5
69.527
71.532
66.82.1
70.523
70.8
movie recommendation
64.827
63.31.2
68.333
62.041
63.0,,2
63.313
61.82.2
mullisteeparrthmeete
95.0,1
95.50.
97.8us
95.3GM
95.518
95.813
95.81.5
ohject_counting
94.529
94.52.1
96.016
94.8pM
94.31.
96.00.
96.31.1
ruin_names
87.31.
88.8p8
91.5g9
89.518
88.521
90.0go
89.81,8
salient_translation
68.02.
67.31.5
70.02a
69.81a
72.824
73.52.
75.8
snarks
93.81.
93.82.1
93.823
95.51.
15.
95.50.
94.82.1
sports undnerssddtt
94.0).4
95.01,0
92.81.
95.51.
97.0na
96.0p.7
94.8p.
tracking shuffled objects (7)
66.83.1
67.31.
99.0po
96.31.
98.5p.
97.51
100.0pe
Average
79.62
79.70
82.40
82.45
82.37
83.08
83.32
with the subsequent optimize and generate steps, although the gain is less than the original BRIDGE which utilizes more examples via the larger train set support.
Table 8: Comparison between BRIDGE with (one step of demonstration optimization only) against Retrieval, Diversity and Reinforced ICL baselines using gemi mimmiii-1.55 pro-001. Note that the BRIDGE (10) and Reinforced ICL results are taken from Table
Tasks
Diversity k= 25
Retrieval k 25
Reinf. ICT.
Details/ hyperparams
= 10
k: == 10
All
10
causal. judgement
66.7
66.3
63.0,,
67.72.
66.725
66.3,s
68.3
late_understanding
93.21.
93.027
87.0s5
93.31.5
93.01.9
88.825
92.21.5
disamhiguation qa
72.23.
77.808
76.5a9
71.20.
77.5u.
76.824
71.82.4
Janguaass
54,0
38.526
39.544
33.2a.1
47.85a
$5.5%6
49.2
formal fallacies
85.5
85.0,
88.5as
88.23a
84.2
86.2
86.02.
geometric shapes
71.244
69.316
69.82x
68.54.2
79.2g.3
80.22H
78.52.1
hyperbaton
95.01.2
92.225
96.51.
97.21,3
95.2,,9
90.2
96.509
logical deduucton (7)
65.8s0
67.544
69,244
66.32.
67.324
65.8s5
70.2
movie recommendation
67.326
65.025
68.5
68.0,.4
67.3
65.216
67.0g,2
multistep arithmetic
92.81.
96.2A4
95.5a9
94.81.
94.319
96.5as
96.2a8
object_counting
95.81.1
95.2a8
97.224
95.21.9
91.222
95.5a9
96.24.4
ruin names
87.81.
89.813
87.8a8
91.52.1
90.523
89.819
90.8
salient_trasslation translation cerrrattioneeoroor_o error ddteectonn
68.52.
69.521
68.213
58.22x
61.02.1
69.016
68.8a8
snarks
94.82.3
96.2,
94.41,7
97.6,,2
95.5
92.7
93.42.
sports uonnttsundnst
95.01.2
95.81.1
95.5ay
95.80.
95.0,,9
93.014
92.81,
tracking shuffled objectts (7)
55.8a.
56.8s5
60.24,3
67.84.7
60.224
62.3,2
95.8p.4
Average
78.83
78.38
78.59
78.41
79.12
79.61
81.61
Average test accuracy BBH tasks using gemini-2 5-ppoo0-000 by combining BRIDGE with different variants of the heuristic demonstration selection methods. Bold text this table shows the best algorithm variant at each round of BRIDGE.
Table 9:
Method
10
1G
20
2G
30
TRIDGE-DIVERSITE (k 10)
77.10
79.47
78.58
81.89
79.50
BRIDGE-DIVERSITY (k = 25)
78.15
80.86
78.74
80.63
79.68
BRIDGE-NEAREST (k 10)
79.07
81.80
81.40
81.35
80.39
BRIDGE-NEAREST (k 25)
78.36
79.49
80.16
81.09
80.10
BRIDGE-NEAREST (All)
79.65
82.91
82.01
83.20
84.14
24

---

Published as a conference paper at ICLR 2025
Table 10: Task-specific test accuracy on BBH tasks using gemini ni -1. 5-pro 001 with BRIDGE- NEAREST (All) (best method from Table 99.
Task
10
20
30
guusal.juggemen
73.0
62.3
64.7a.7
65.722
63.3
late_understanding
94.31.3
92.016
95.014
92.213
92.804
disambiguation
76.8..4
75.850
72.01.0
82.027
82.8os
dyck languages
58.823
75.04.
75.03.3
78.53.
82.0
formal fallacies
84.2a.s
88.5
90.Su.9
89.5
90.00.
geometric shupes
75.82.
86.213
79.8u.
84.021
84.5
hyperbaton
96.0u.
93.823
97.0u.
92.5u.2
98.804
logical deduction www.uutttooseeeeneeeeeeeee seven objeects
65.83.
73.823
68.0s.7
70.0
71.2
movie recommendation
67.01.2
69.51.
63.21.1
70.02.
73.80s
multistep arithmetic two bojjcctccuntting
92.50.5
97.012
96.70.s
97.509
94.000
91.81.5
95.012
97.0u.7
96.51.7
100.00.0
ruin main_names
88.8u.4
92.0uz
88.52.
89.2GM
88.2
_eror, _detection
63.21.5
70.016
70.2
70.0
70.50.
snarks
95.81.7
94.812
93.71.2
96.51.2
95.8o0
sports unddrrstaddggg whw.fffol..bycctt..eeee...eeeeee
94.0p.7
96.51.
93.8n.4
95.51.5
94.204
56.81.6
64.5a9
67.01.a
61.544
64.21
Average
79.65
82.91
82.01
83,20
84.14
C.2
NUMBER OF EXAMPLES
We show the number of examples used for each experiment corresponding to Table iin Table 11
Table 11: Number of examples for each experiment corresponding to Table
(gemini-t) 11w--11.5p----- 5-pro-001 on BBH tasks). Note that the "All" columns always use all 75 examples provided.
Tasks
Reinf. ICL
Iter. Reinf.
BRIDGE-BO
Iterations
10
1G
2G
30
causal, causal.judge judgement
36
40
43
11
43
39
39
date iiteesddrttnn
72
57
disambiguation.cg
69
28
68
65
dyck languages
15
40
52
9
45
42
59
20
formal fallacies
60
69
69
2
63
30
67
57
geometric shapes
68
40
59
71
70
hyperbaton
deiiclldeduction.ce seaetioonseeenoojcccts
62
11
64
61
movie recommendation
42
53
54
39
49
36
51
41
multistep arithmetic two
65
74
74
38
74
28
72
38
object_counting
75
60
75
14
ruin_names
71
iileenitranslationn.m detoeceetttooon
44
59
60
13
59
41
snarks
47
50
51
19
49
48
39
sports understanding
64
75
75
52
75
74
74
68
tracking shuftled objects. seven_objeets.
53
2
22
Average
50.94
62.00
63.94
27.25
62.38
36.69
64.94
44,50
C.3 ADDITIONAL. VISUALIZATIONS
In this section, we show analysis similar to Fig. 4nn tasks not represented in the figure of the main text.
C.4 USING BRIDGE FOR LOW-RESOURCE TRANSLATION
While we have primarily considered the reinforced ICL setup suitable for reasoning and general problem-solving tasks, it worth noting that the BRIDGE framework may also generalize to other practical settings that benefit from many-shot ICL with some modification the "optimize" and the "generate" steps. In this section, we conduct a preliminary analysis on the applicability of BRIDGE in the context of machine translation (MT) for low-resource languages.
25

---

Published as a conference paper at ICLR 2025
causal judgement
disembiguetion.c
0.8
dyck languages
0.95
0.7
0.8
Vel Acc
0.70
Vil. Aoo.
0.6
0.65
0.05
0.5
Pound
0.4
Round o
0.60
Round1
Bound2
Round1 Round?
0.6
Ronnd
Round
0.3
Round
Round 2
0.05
0.76
20
40
60
60
Damoa
Damos
Damos
Demos
formal fallacies
hyperbaion
logical deduction objects
movie recommendatioon
0.90
1.000
0.8
0.70
0.975
0.65
0.950
VAL Arz
0.80
0.65
0.75
Rourdo Round
Rounds
0.900
0875
Roando Round:
Hordd
0.5
Round
0.50
0.45
Roundo
Round
Bound
0.40
Demmov
Demox
Democ
&Demox
muhiisto_arthmmett wwwthmeticcccccmmm two
object_counnlin
ruin, names
snerks
1.00
100
0.95
0.00
0.98
0.88
0.90
Vel Kcc.
0.96
Act.
Vel Ace
0.86
Ace.
0.90
0.54
Bourdo Bourd
Ibundo
Hourd?
0.2
Iburd1
Bound
Rourd
Brund2
0.92
0.80
20
40
60
20
40
60
20
40
60
20
40
Dercsc
# Demco
Democ
A Damcce
sports und.ustanddingnggggggg
GSM-Hard
0.78
0.90
Vel Acc
0.76
0.94
0.74
fourd Found1
Roundo
0.90
Round?
0.22
Roudd
Round1
25
50
75
25
50
75
Damos
Demos
Figure 5: Additional visualization of the task performance at different rounds. Note that in most datasets, additional rounds of BRIDGE led to performance improvement, and some of the exceptions (e.g., multi _arii thmet r i cot are possibly caused by visualization artefacts of the extremely small performance variation as shown by the small y-axis ranges.
As noted in Agarwal et al. 2024) and Reid et al. (2024), low-resource machine translation (MT) is one of the task types where many-shot in-context learning (ICL) has demonstrated remarkable performance. In these tasks, there is often nearly monotonie improvement in translation quality as more source-target language pairs are incorporated into the context - as a notable exception to our observations in Sec. 2 that primarily involve reasoning tasks, in low resource MT, we often observe "more is better" given the information-dense nature of translation tasks - indeed, for trans- lation tasks, barring glaring human errors in the annotation process, the provided data is generally assumed to be of high quality and problems like false positive in model- -edee-eeneerted reasoning paths in reasoning tasks are generally negligible for tasks like low resource MT with high quality anno- tated data. However, in low-resource languages, the model's inherent knowledge is often weak or non-existent due to the lack of exposure to target languages during pre-training or fine-tuning, which can lead to a bottleneck in data availability especially for extremely low-resource languages, where 1) the model lacks zero-shot translation abilities due to insufficient exposure to target languages, and 2) the scarcity of annotated data becomes critical limiting factor to address these, previous works often attempt to augment ground -round-truth translation data with model- syneh-syythesizee translations (Han et al. 2021 Patel et al. 2022].
26

---

Published as a conference paper at ICLR 2025
In this section, along this line of work, we investigate the applicability of BRIDGE method to iteratively improve the model-syune sodell-yytthsizeed translation so that they can act as more effective augmen- tations to the scarce ground truth data. Specifically, assume the following in our setup:
Availability some ground-trun source-target sentence pairs this pair will both act as the train from which ground-truth examples are generated and also the validation set for machine-generated translations.
Abundant source language text - this almost always true. For example, if we are inter- ested in translating from English to a low-resource language, it is extremely easy to obtain abundant text in English whereas the difficulty to obtain the corresponding tranlsaiton in the target language.
LLM for "pseudo-labeling"" - we assume the availability of a (strong) LLM that can be queried to generate synthesized data.
Algorithm 3 BRIDGE with pseudo-labelling
1: Input: train set 2) unlabeled set with source language sentence, U. number of iteration rounds K E N (outer-loop), evaluation budget for BO per iteration Neval (inner-loop), Generator model used synthesize examples MMg-.
Output: Optimized set of model-synthesized examples E*
3: Partition D into two disjoint sets D, and D, via random sampling.
4: [Generate] Generate the pool of initial examples &g by predicting M, the unlabeled set, using the entire train set D the demonstrations the context: En- +- My(
for E (1, ..., K} (Outer loop)
6: [Optimize] Run Baycsian optimization (calling subroutine Algorithm on the De to obtain ej +
(Nevll (ayaaRpptt E=Ex).
7: [Generate] Re-generate examples & by re-predicting the LLM the unlabeled set, but with the optimized examples ej from the previous step and D, as demonstrations; the {inputs, output)-pairs concatenated to form new set examples & for the next [Optimize] step.
8: end for
9: return Optimized example set ex after K rounds.
To approach the problem, we propose to retain the high-level framework of BRIDGE but modify the "opttmize" and "generate" steps to accommodate the low-resource MT setup. With reference to Algorithm [ where we have marked the key differences blue, the main difference lies in the "generate" step: instead of generating examples with model-generated reasoning paths in the case presented in the main text, here we synthesized examples on unlabeled set li that we assumed to be available. Since no longer have access to the ground-truth translation of the sentences in Ut we optimize for the optimal subset e* by evaluating different combinations of the synthesized examples on the partition of the labeled dataset E..
To test BRIDGE on the MT setup, we consider the Baglish-Bembee translation task in the Flores dataset (Guzmán et al., 2019) that was also considered in Agarwal et al. (0224). We assume the access to 100 labeled examples as 'D and 50 unlabeled examples 27, and hold out another 400 samples the test set. We use Gemini Flash the target model and Gemini Pro the generator model in Algorithm and we show the result in Table 12 Overall, we observe that running iterative optimization also improves performance on this task. both exemplified by improvement on the test and validation chri score, although it seems that additional optimization round in this case led to small performance degradation. While more comprehensive evaluation is required, we believe the preliminary result is promising for future effort on this direction.
C.5 EXPERIMENTS ON ADDITIONAL MODELS
In this section, we report BBH results on two additional models: tral Large (mistral-large-1 2407) (Table 13 Mistral Nemo (Table 14]
Mis-
2024) (Table 15). For both models, (Jiang et al. 2023) and Claude 3.5 Sonnet (Anthropic
the versions served Google Cloud Vertex Al platform. We find that while the base capabilities of the tested models differ slightly (c.g.. Claude
3.5 Sonnet has higher accuracy across the board), the high-level findings primarily derived from
27

---

Published as a conference paper at ICLR 2025
Table 12: Test chrf score of gemini-1 1.1.--ffashh 001. "Gold-only" refers to the result obtained by only using the 100 labeled examples in the context; "All" refers to the result with 100 labeled examples 50 initially generated examples from yemini-1.5-pro-1 5-pro-001. Refers to captions of Table for additional explanations.
Tasks Iterations
Gold-only
All
BRIDGE-MI
0
10
16
20
26
30
en cn_bem
37.78
38.46
38.33
39.11
39.30
38.90
39.29
Table 13:
Test accuracy of Mistral Large (mistral -aaralllee -arllllareeeee 2407) on BBH tasks. Refer to
captions of Table for detailed explanations.
Tasks
Reinf. ICI.
Iterative
DRIDGE (Ours)
# Iterations
0
2
10
16
20
2G
30
sausal_judgemeet
69.3
66.7
72.0
68.0
65.3
69.3
64.00
73.3
date understanding
92.0
92.0
96.0
93.0
92.0
96.0
disamhiguations
82.0
82.0
79.0
81.0
87.0
87.0
84.0
86.0
dyck language
56.0
62.0
56.0
70.0
59.0
70.0
63.0
71.0
formal ffallacies
90.0
82.0
86.0
89.0
89.0
90.0
83.0
85.0
geometric shapes
87.0
80.0
93.0
88.0
85.0
95.0
71.0
94.0
hyperhaton
100.0
100.0
100.0
99.0
deduction (7)
81,0
85.0
76.0
82.0
88.0
90.0
86.0
92.0
movie recommendation
74.0
71.0
74.0
77.0
66.0
78.0
80.0
79.0
muliistep.ariimmeete aarithmetiic_coo
88.0
92.0
93.0
91.0
89.0
86.0
93.0
object_counting counting
99.0
99.0
99.0
98.0
98.0
98.0
100.0
98.0
ruin names
88.0
90.0
92.0
86.0
89.0
89.0
89,0
salient, translation, eeror detection
66.0
68.0
70.0
78.0
69.0
75.0
72.0
73.0
snarks
95.8
95.8
97.2
94.4
95.8
95.8
95.8
93.1
sports understanding
94.0
97.0
98.0
97.0
96.0
tracking wwwffled. (7)
96.0
68.0
100.0
100.0
73.0
100.0
57.0
100.0
Average
84.82
83.22
87.08
86.65
83.70
88.07
82.80
88.52
Table 14: Test accuracy of Mistral NeMo (mi stsssralll nemo) on BBH tasks. Refer to captions of Table for detailed explanations.
Tasks
Reinf.
llerative
BRIDGE (Ourz)
Iterations
2
10
1G
20
2G
30
causal. judgement
62.7
60.0
64.0
date understanding
66.0
71.0
68.0
69.0
69.0
78.0
70.0
75.0
disambiguation.g
63.0
72.0
dyck languages
17.0
21.0
22.0
18.0
27.0
26.0
22.0
30.0
formal fallaciss
55.0
53.0
63.0
59.0
52.0
51.0
59.0
geometric_shappe shapes
65.0
65.0
69.0
72.0
72.0
60.0
69.0
68.0
hyperbaton
77.0
65.0
80.0
81.0
83.0
75.0
86.0
ceairtiionsevee_lhee _evee_obbects
47.0
54.0
53.0
45.0
49.0
62.0
44.0
$1.0
movic .ww.mmcndnniinnnn
54.0
68.0
61.0
70.0
coatiitep_.rthmmmii..c.
36.0
50.0
20.0
47.0
20.0
66.0
12.0
77.0
sojjet__cuntting
81.0
82.0
83.0
79.0
85,0
75.0
87.0
ruin jamess
69.0
60.0
$7.0
76.0
$7.0
72.0
$7.0
70.0
salieni Iranssationnnnnneeo. deteccion
47.0
47.0
45.0
59.0
49.0
$3.0
49.0
48.0
snarks
69.4
76.4
79.2
72.2
75.0
72.2
73.6
77.8
sports wwn.erstadddinggggggggg..
75.0
69.0
91.0
72.0
91.0
74.0
93.0
tracking shuilled objects seven objects
70.0
69.0
70.0
91.0
88.0
94.0
81.0
93.0
Average
60.30
60.42
58.30
66.08
61 04
67.56
59.16
70.05
Gemini results in the main text largely hold. On Claude 3.5 Sonnet, we observe an almost identical high-level trend to Gemini, where each round of BRIDGE incrementally improves performance up to 2G. On the other hand, while Mistral models seemingly benefit less from scaling demonstrations especially in the smaller Mistral NeMo (c.g., sometimes the generate step leads to drops in performance) directly, the improved quality of the generated demonstrations still enables successive optimize step to improve the preceding round, demonstrating the effectiveness of BRIDGE even when the model does not benefit from scaling examples directly.
C.6 TRANSFERRING LEARNED DEMONSTRATIONS FROM GSM-HARD TO GSM-8K
In this section, investigate whether the BRIDGE-discovered demonstrations related but distinct datasets. Specifically, we investigate the extent to which the demonstrations found GSM-Hard (Table 2 generalize the original GSM-8K and show the result in Ta-
transfer across
28

---

Published as a conference paper at ICLR 2025
Table 13: Test accuracy of Claude 3.5 Sonnet (cLeude-3----oonette2222
on BBH
tasks. Refer to captions of Table for detailed explanations.
Tasks
Reinf. ICL
Iterative Reinf.
DRIDGE (Ours)
# Iterations
0
2
10
1G
20
2G
30
causal. judgement
64.0
68.0
65.3
62.7
69.3
73.3
20.7
65.3
date understanding
94.0
95.0
96.0
97.0
94.0
95.0
96.0
95.0
disanbiguation.pe
73.0
82.0
79.0
81.0
87.0
87.0
84.0
86.0
dyck_ language
68.0
65.0
87.0
formal fallacies
93.0
94.0
97.0
96.0
95.0
98.0
96.0
95.0
geometric shapes
92.0
94.0
98.0
88.0
90.0
85.0
96.0
89.0
hyperbaton
100.0
100.0
100.0
100.0
100.0
100.0
100.0
logical, deduction (7)
92.0
96.0
96.0
89.0
95.0
97.0
91.0
93.0
rovieerecommendationn
87.0
90.0
92.0
89.0
90.0
93.0
90.0
multistep arithmetic two
99.0
99.0
99.0
99.0
99.0
99.0
100.0
100,0
object_rounting
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
ruin names
93.0
93.0
94.0
94,0
salient, translation _eror deteeceettoionn
71.0
71.0
73.0
71.0
72.0
73.0
73.0
73.0
snarks
97.2
97.2
97.2
95.8
95.8
98.6
97.2
sports, understanding
92.0
91.0
94.0
93.0
94.0
94.0
93.0
91.0
tracking shuffled objects (7)
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
Average
88.45
89,89
90.35
89.16
91.26
92.00
92.20
90.97
ble [66] where we compare the performance of the demonstrations directly transferred from GSM- Hard at different stages of BRIDGE against directly optimizing GSM-8K. We find that whereas the demonstrations generated from (iterative) reinforced ICL. led small deterioration of GSM-8K performance, we found the transferred demonstrations from BRIDGE led to small improvement even though the Gemini 1.5 Pro performance on GSM-8K has been rather saturated. While optimizing directly GSM-8K unsurprisingly led to the highest performance given that there is no distribution shift, we also find that the GSM-Hard Hard demonstrations exhibit considerable generalizability.
Table 16: Comparison of the transferred BRIDGE-generain demonstrations on GSM-Hard vs. di- rectly running BRIDGE GSM-8K. Runs with performance deteriorations w.r.t. the 0-shot results are marked in red in the table.
Tasks
O-shot
Reinf. ICL
Iterative Reinf.
BRIDGE (Ours)
Iterations
2
1G
20
Direct
91.92
93.81
93.06
92.68
93.81
93.18
94.70
94.19
93.94
Transferred
90.66
91.79
91.16
93.81
92.55
93.81
93.18
91.16
D COMPUTATIONAL COST ANALYSIS
In this section, we provide a computational cost analysis of BRIDGE. In general, since BRIDGE consists of multiple rounds of "Optimize" and "Generate" steps, here analyze each step in detail.
Optimize: The cost of the "optimize" step depends the budget allocated (Neval in Line of Algorithm 2) which user-configurable. If we opt for itcrative optimization (such using Bayesian optimization in the main section of the paper, random search in App. C.J). each "optimize" step thus entails neval LLM inferences on the validation set. As shown in the App. C.T. it is also possible or embedding diversity, in which case each "optimize" step entails single round of LLM inferences the validation (or the train set, if we use the dataset for both training and validation).
non-iterative method based retrieval
Generate: The "generate" step always involves a single round of LLM inferences on the train set where we simply use the optimized examples from the "optimize" step above as demonstrations and run inference again on the train set.
29


Reviews:
[{"review_id": "U93ZrVdLnc", "reviewer": "Reviewer_cswN", "summary": "This paper addresses the many-shot in-context learning (ICL) paradigm. In contrast to few-shot learning, many-shot ICL leverages a larger number of demonstration examples to better exploit long-context capabilities. Initially, the paper demonstrates that selecting influential demonstration examples remains valuable, even in long-context settings. Building on this observation, the authors propose an algorithm that alternates between two key steps: an optimization step, which employs Bayesian optimization to identify influential example sets, and a generation step, which reuses these sets to automatically extend reasoning paths, thereby facilitating the transition back to the many-shot regime.", "questions": "Q1 In reference to Figure 1, does bottom_k refer to selecting examples that are less similar to the test case? Why does bottom_k achieve performance comparable to top_k as the number of demonstrations increases? Additionally, why does bottom_k outperform the all-examples approach?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The proposed framework integrates example selection with LLM-generated examples to better align with real-world applications. \n\n- The paper validates this approach through extensive experiments conducted across a wide range of tasks.", "weaknesses": "The validation of the findings appears overly simplistic. For instance, as model capabilities scale, the order and number of demonstration examples may have diminishing importance in affecting in-context learning (ICL) performance. The authors should reconsider their conclusions by re-evaluating their results on less advanced LLMs, providing a more comprehensive understanding of the interplay between long-context utilization and demonstration selection. Without this analysis, the conclusion may be over-claimed to specific models.\n\nLack of baselines. In the experiments, the authors did not compare their approach with existing learning-based strategies and learn-free ones for demonstration selection. \n\nThe writing of the paper requires further refinement. Sections 3 and 4 are challenging to read and follow, despite the method itself being relatively straightforward. For instance, the description of the different variants could be more appropriately placed in the Experimental Setting section for better clarity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vu6jxG8Efx", "reviewer": "Reviewer_DZro", "summary": "This paper studies the problem of how to improve many-shot in-context learning (ICL). The first observation is that the quality of ICL examples can be more important than the quantity -- a carefully selected subset of in-context learning examples can outperform the whole set. \n\nBased on this observation, this paper naturally moves to the question of how to improve the quality of ICL examples. The key idea is to iteratively select helpful examples from both the seed examples and those generated by the model itself, similar in spirit to STaR but applied to ICL instead. Specifically, in each iteration, the model is prompted to generate both reasoning steps and the answer. Only those with correct answers are kept. Then a Bayesian Optimizer is used to select the best ICL examples in this iteration, which are used as ICL examples for generation in the next iteration.\n\nResults on BBH show that the proposed method largely outperforms baseline methods. Small improvements are achieved on MATH and GSM8K. A large improvement is observed on the BIRD-Challenging subset.", "questions": "I don't fully understand the claim that BRIDGE is tailored to many-shot ICL. I feel it also applies to few-shot ICL?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Many-shot ICL is an important problem from both the capability and safety angles. \n- This paper shows that even for many-shot ICL, good examples are still necessary. \n- The proposed method is a natural extension of the STaR framework to ICL. Given the hardness of optimizing ICL example selection, the proposed optimizer looks like a good contribution.\n- Experimental results on BBH look strong, and small but non-trivial improvement are shown on math (MATH and GSM8K) and text-to-sql (BIRD) datasets.", "weaknesses": "- The experiments are done only with Gemini models on text tasks. It would be interesting to see the performance on GPT-4o / o1 models and multimodal tasks. \n- Variance is not reported for MATH, GSM8K, and BIRD. Given the relatively small improvement on these datasets, it's unclear if the gain is significant.\n- As the method optimize the performance on a dataset/task, it would be interesting to see the performance under distributional shifts. For example, does the gain on GSM8K transfer to GSM-symbolic?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0QzlO65XPb", "reviewer": "Reviewer_YxzH", "summary": "The paper studies the many-shot in-context learning using Gemini family of models on BigBenchHard (BBH). Specifically, the authors demonstrate that identifying a subset of influential examples reinforced with model-generated reasoning can significantly outperform naively using all available examples. They also propose BRIDGE, a simple approach that instantiates this finding to iteratively seeking for the subset of examples and refining model-generated reasoning for these examples. BRIDGE is evaluated on the subset of BBH tasks and the substantial gains over the considered baselines are demonstrated.", "questions": "Can you please provide the baseline when a model conditions on all available examples but with all examples using model generated reasoning? This baseline can decouple the importance of subselecting a subset of examples and influence of having model-generated reasoning, and strengthen your claims if, indeed, you need both rather than only model-generated reasoning. The recent works [1, 2] can be used to ensure that a model is constrained to generate reasoning given the input and the ground truth answer.\n\n[1] Hu et al. Amortizing intractable inference in large language models. ICLR 2024\n\n[2] Zhao et al. Probabilistic Inference in Language Models via Twisted Sequential Monte Carlo. ICML 2024", "limitations": "", "rating": 8, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* Paper studies many-shot in-context learning, the important novel prompting technique that is used to significantly improve LLMs' predictions. Given that, this technique was made available only recently with the rise of long-context LLMs, studying its behaviour is important topic that can be relevant to broad community.\n\n* The proposed approach is simple and algorithmically applicable to both close-source and open-source models.", "weaknesses": "* The important baseline might be missing to ensure the strength of the claims, please see Questions section.\n\n* I would also ask for including similar analysis for other LLMs beside close-source ones like Gemini. At least on the subset of the considered tasks, to see whether the conclusions generalize to other models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Gg8yK0I1G7", "reviewer": "Reviewer_qv5C", "summary": "This paper presents a study on the performance of many-shot in-context learning on NLP tasks that require reasoning process (the reinforced ICL setup). The authors first define a importantce scoring function of input examples based on estimated input gradient, and observe that 1) many-shot ICL could be driven by a few high-performing examples, 2) scaling demonstration examples could still be beneficial with improved quality of reasoning. Motivated by these observation, the authors propose a method called BRIDGE to improve many-shot ICL in an iterative manner. Experiments of Gemini across a diverse set of tasks show the effectiveness of BRIDGE.", "questions": "Please refer to the \"weakness\".", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "1. Overall, this paper is well writtern and clear to follow.\n2. The proposed method is well-motivated through experiment results (Figure 1 and Figure 2). The observation that many-shot ICL could be driven by few high-performing examples is interesting.\n3. The proposed method shows decent performance compared to the baseline.\n4. The method is evaluated on various  challenging datasets", "weaknesses": "1. The analysis is limited to reinforced ICL setting that only considers reasoning-heavy tasks. It's not clear what many-shot ICL would perform on simpler tasks that do not heavily relies on reasoning. Also, could BRIDGE anyway be helpful on simpler tasks?\n2. The experiments are only evaluated with Gemini. What would be the performance of proposed method on open-source methods like Llama-3.1? More importantly, for open-source model, would there exists a better way of importance attribution? Also, for base model where the reasoning ability is limited, would the proposed method also be helpful?\n3. Lack of the analysis on the computation cost. What's the computational cost of optimize and generate step of BRIDGE, respectively? \n4. The definition of importance score function is well-justified. In section 2 Line 153, the importance of each example is estimated by the averate performance of randomly sampled demonstrations on the validation set. The variance would be huge considering different choices of subsets and orders. Have the author performed analysis on the varaince of importance score?\n5. Importance attribution is not well justified. In section 2 Line 153, it's not clear how importance score is actually estimated and why it would make sense.\n6. The description of \"optimzie\" step is not clear (Line 261). The text in page 6 is generally unclear to me. For example, what does \"TCM\" stand for in algorithm 2 step 6? How does the problem become a \"bi-objective\" problem and how the optimize step is connected to \"Bayes optmization\"?\n\nMinor issue: \")\" is missing in Line 149", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)