DAWN - ICL : Strategic Planning of Problem-solving Trajectories for Zero-Shot In-Context Learning (2025)

Abstract: Zero-shot in-context learning (ZS-ICL) aims to conduct in-context learning (ICL) without using human-annotated demonstrations.Existing ZS-ICL methods either use large language models (LLMs) to generate (input, label) pairs as pseudo-demonstrations or leverage historical pseudo-demonstrations to help solve the current problem.They assume that all problems are from the same task and traverse them in a random order.However, in real-world scenarios, problems usually come from diverse tasks, and only a few belong to the same task.The random traversing order may generate unreliable pseudo-demonstrations and lead to error accumulation.To address this problem, we reformulate ZS-**ICL** as a planning problem and propose a **D**emonstration-**AW**are Mo**N**te Carlo Tree Search (MCTS) approach (DAWN-ICL), which leverages MCTS to strategically plan the problem-solving trajectories for ZS-ICL.In addition, to achieve effective and efficient Q value estimation, we propose a demonstration-aware Q -value function and use it to enhance the selection phase and accelerate the expansion and simulation phases in MCTS.Extensive experiments demonstrate the effectiveness and efficiency of DAWN-ICL on in-domain and cross-domain scenarios, and it even outperforms ICL using human-annotated demonstrations.The code is available at https://github.com/txy77/MCTS4ZSICL.

## introduction in-context learning (icl) @xcite @xcite represents a significant advancement in the capabilities of large language models (llms). it allows llms to rapidly adapt to new tasks without updating the parameters by adding only a few examples as demonstrations to the input. although no training is required, most icl work assumes access to large-scale external resources (e.g., training dataset @xcite or relevant corpus @xcite ) for demonstration selection, which is usually not available in real-world scenarios. to eliminate this dependency, zero-shot incontext learning (zs-icl) @xcite is proposed, which uses llms to generate (input, label) pairs as pseudo-demonstrations for icl. however, since llms are limited in data synthesis @xcite @xcite , the performance of zs-icl usually falls behind icl with human-annotated demonstrations. to remedy this deficiency, recent work @xcite employs previously predicted examples as the source of demonstrations, eliminating the need for input synthesis and reusing the predicted labels. this method assumes that test examples are from the same task and traverse them in a random order. however, in real-world scenarios, examples usually come from diverse tasks, and only a few belong to the same task. the random traversing order may cause llms to generate unreliable pseudo-demonstrations and lead to error accumulation, as illustrated in figure 1 . to address the above problems, we aim to optimize the traversing order of examples in zs-icl and formulate it as a planning problem. to search the traversing order, we take inspiration from monte carlo tree search (mcts) @xcite , which can conduct a strategic tree search and strike a balance between exploration and exploitation. in the algorithm, mcts maintains a state-action value function q(s, a) to estimate the expected future reward of taking action a in state s, which is updated by the simulation and backpropagation step in each iteration. however, for zs-icl, such an updating method is too costly to achieve accurate estimation since the state space is very large (n! for n examples), and each state requires the llm to perform one inference for reward calculation. to this end, in this paper, we propose a novel demonstration-aware monte carlo tree search for zs-icl, namely dawn-icl. our core idea is to leverage mcts for planning the problemsolving trajectories in zs-icl. to achieve effective and efficient q value estimation in mcts, we propose to integrate the information of the pseudo-demonstration set into the q-value function. with this demonstration-aware q-value function, we can enhance the selection phase and accelerate the expansion and simulation phases of mcts for more effective and efficient search. furthermore, we design a calibration-enhanced aggregation method to derive the final prediction from mcts, which aggregates results from multiple iterations and debiases the prediction with pre-trained priors. to validate the effectiveness of our approach, we conduct experiments on the in-domain and cross-domain scenarios of bbh and mmlu across various llms. the experimental results show that dawn-icl consistently surpasses the best zs-icl baseline method and even outperforms icl using human-annotated demonstrations. our contributions can be summarized as follows: enhancing llms with planning. recent advancements in enhancing llms through planning have shown promising results @xcite @xcite . they often engage in deliberate reasoning processes by utilizing strategic planning algorithms like mcts @xcite to explore intermediate steps. in this work, we aim to better utilize the in-context learning ability of llms by performing a novel demonstration-aware mcts for zs-icl over the demonstration space. ## methodology in this section, we present our demonstration-aware mcts for zs-icl, namely dawn-icl. we first give an overview of our approach, then discuss how to integrate the information of demonstrations into the q-value function, and finally present the planning approach to zs-icl. the overall architecture of dawn-icl is illustrated in figure 2 . ## experiments in this section, we first set up the experiments, then report the results and conduct a detailed analysis. ## conclusion in this paper, we introduce dawn-icl, a strategic planning approach for zs-icl that utilizes mcts to search for the optimal problem-solving sequence. to achieve effective and efficient q value estimation, we propose a novel demonstration-aware qvalue function that aims to enhance the selection phase and accelerate the expansion and simulation phases in mcts. experimental results demonstrate that our approach consistently outperforms existing zs-icl methods and even performs better than icl with human-annotated demonstrations. overall, our work highlights the importance of planning for zs-icl in real-world scenarios, paving the way for more effective deployment of llms.