Rethinking the Unsolvable: When In-Context Search Meets Test-Time Scaling

Fanzeng Xia, Yidong Luo, Tinko Sebastian Bartels, Yaqi Xu, Tongxin Li † · 2025

Read Rethinking the Unsolvable: When In-Context Search Meets Test-Time Scaling by Fanzeng Xia, Yidong Luo, Tinko Sebastian Bartels, Yaqi Xu, Tongxin Li † (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-22290.txt.

Introduction

Fanzeng Xia and co-authors challenge, in a 2025 paper, the verdict that some reasoning tasks are beyond language models. Many hard tasks were written off after models, asked in a plain way, solved fewer than one in twenty. The team pairs two upgrades: search built into the prompt itself, and more computing time at test time, so the model can think longer and wider before it answers.

On controlled hard puzzles and on real planning benchmarks, the pairing lifted success rates up to thirtyfold over the old reports, with no outside tools. Theory backs the leap: the combo stretches the class of problems a model can in principle solve. The authors argue that standard testing has been underrating what models can do, and call for a fresh look at how reasoning power is measured.

Catalog record

CREATORFanzeng Xia, Yidong Luo, Tinko Sebastian Bartels, Yaqi Xu, Tongxin Li †
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE113 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-22290

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Rethinking the Unsolvable: When In-Context Search Meets Test-Time Scaling Fanzeng Xia, Yidong Luo, Tinko Sebastian Bartels, Yaqi Xu, Tongxin Li † Abstract Recent research has highlighted that Large Language Models (LLMs), even when trained to generate extended long reasoning steps, still face significant challenges on hard reasoning problems. However, much of the existing literature relies on direct prompting with simple in-context learning examples for evaluation, which largely overlooks advanced techniques to elicit LLMs’ deliberate reasoning before drawing conclusions that LLMs hit a performance ceiling. In this paper, we systematically explore the combined potential of in-context search and test-time scaling on super hard reasoning tasks. We find that by employing advanced in-context search prompting to LLMs augmented with internal scaling, one can achieve transformative performance breakthroughs on tasks previously deemed “unsolvable” (e.g., reported success rates below 5%). We provide both empirical results and theoretical analysis of how this combination can unleash LLM reasoning capabilities: i) Empirically, on controlled NP-Hard tasks and complex real-world planning benchmarks, our approach achieves up to a 30 × \times improvement in success rates compared to previously reported results without any external mechanisms; ii) Theoretically, we show that in-context search prompting, when combined with internal scaling, significantly extends the complexity class of solvable reasoning problems. These findings challenge prevailing assumptions about the limitations of LLMs on complex tasks, indicating that current evaluation paradigms systematically underestimate their true potential. Our work calls for a critical reassessment of how LLM reasoning is benchmarked and a more robust evaluation strategy that fully captures the true capabilities of contemporary LLMs, which can lead to a better understanding of their operational reasoning boundaries in real-world deployments. † † footnotetext: Equal Contribution. † † footnotetext: † Corresponding Author. 1 Introduction Large Language Models (LLMs) have demonstrated significant progress in solving diverse reasoning and planning tasks, such as instruction following ( Wei et al. 2021 ; Ouyang et al. 2022 ) , commonsense reasoning ( Talmor et al. 2018 ; Brown et al. 2020 ) , and code generation ( Chen et al. 2021 ; Austin et al. 2021 ) . Despite their achievements, LLMs still face significant challenges when applied to complex, long-horizon problem instances. The emergence of reasoning-oriented models, as exemplified by ( Jaech et al. 2024 ; Guo et al. 2025 ) , has led to substantial progress in solving problems that require extensive reasoning and planning. Trained through reinforcement learning and high-quality trajectories to develop systematic reasoning processes, these models demonstrate improved performance on tasks that require multi-step deduction and self-correction. This enhanced capability, evidenced by benchmarks such as PlanBench ( Valmeekam et al. 2023 ) , marks a significant advancement in areas where earlier LLMs exhibited notable deficiencies. However, this improvement is not uniform across all problem complexities; the models particularly struggle with more challenging instances, such as controlled NP-hard tasks like Vertex Cover and 3-Dimensional Matching ( Yang et al. 2025 ) , and sophisticated real-world planning scenarios such as the Natural Plan Benchmark ( Zheng et al. 2024 ) . Recent critiques ( Valmeekam et al. 2024a ; Valmeekam et al. 2024b ) emphasize that difficulties persist in solving these complex problem instances, highlighting the need for further strategies to address the full spectrum of reasoning challenges in real-world applications. To optimize the deployment of LLMs across diverse problem difficulties, recent studies ( Chen et al. 2024a ; Sun et al. 2025 ) have sought to define their reasoning limitations. A common observation is that current LLMs encounter a significant performance ceiling (often when success rates on complex tasks drop below 10 - 20\% ), suggesting that additional training with new architectures may be needed for breakthroughs on hard problems. However, our analysis of experimental settings in recent studies (see Table 3 in Appendix B ) reveals a pattern: most evaluations rely on direct prompting strategies. These include few-shot in-context learning without task decomposition ( Wang et al. 2020 ) , automatic Chain-of-Thought (Auto-CoT) prompting ( Zhang et al. 2022 ) where models generate reasoning steps autonomously, and hints before prompting ( Fu et al. 2024 ) . Focusing mostly on direct prompting, prior work might have missed the power of advanced in-context search prompting techniques to elicit deeper reasoning, possibly leading to a biased assessment of LLMs’ actual reasoning boundaries. Inspired by this, our work aims to systematically probe and potentially elevate the perceived upper limits of LLM reasoning on “super hard” problem instances (those with previously reported success rates below 5%). This investigation motivates the following central question: Figure 1: Overview of promoted LLM reasoning boundaries for hard problems via the combination of in-context search and test-time scaling. Our findings reveal that tasks previously reported as unsolvable are actually solvable and thus require a rethink of the current evaluation configurations. Evaluation is based on the Trip Planning task as an illustrative example. Are LLMs truly incapable of solving tasks deemed “unsolvable” by current evaluation paradigms, or can their full potential on such problems yet be unleashed? To answer this question, we adopt a standard prompt-based approach (without external mechanisms or additional fine-tuning) to evaluate the upper-bound reasoning performance of out-of-the-box LLMs on two challenging problem categories: controlled NP-hard tasks and complex real-world planning scenarios. Overall, there are two types of methods commonly employed to enhance the on-the-fly reasoning capabilities of LLMs: (i) In-context search prompting , a class of prompting strategies that enables LLMs to internally simulate search processes through learned in-context examples. Our experiments explore a variety of prompting techniques designed to optimize model performance across diverse tasks, including direct prompting, Chain-of-Thought (CoT), and Algorithm-of-Thought (AoT); (ii) Test-time scaling , a class of techniques that augment LLM reasoning at inference time by expanding computational effort or diversifying reasoning pathways. We experiment with methods including parallel scaling, sequential scaling, and internal scaling. Further details on both these categories of methods are provided in Appendix B . Recent representative works have sought to provide insights into improving LLM reasoning capabilities from different perspectives: (i) Through in-context search prompting, ( Ge et al. 2025 ) explored how different direct prompting strategies affect models with internal scaling, while ( Sel et al. 2025 ) developed advanced in-context search prompting methods that enable LLMs to better follow structured in-context search processes; (ii) Regarding test-time scaling, ( Snell et al. 2024 ) investigated the impact of parallel scaling and sequential scaling with direct prompting, leaving more advanced in-context search techniques unexplored, concluding that these test-time scaling schemes yielded only small gains on hard problems; (iii) In the context of super-hard tasks, ( Chen et al. 2024b ) examined sequential scaling in conjunction with external pipelines for complex real-world planning. Other investigations into NP-hard problems, such as 3-SAT and Sum-of-Squares ( Hazra et al. 2025 ; Li et al. 2025 ) , have found that LLMs show promise on NP-hard instances and have probed the models to understand different cognitive behaviors. These studies provide initial explorations of specific NP-hard tasks, but an overall understanding and analysis are still lacking. While these prior works offer valuable insights, we identify a crucial gap in the current literature as shown in Table 3 : the potential of advanced in-context search methods, particularly when deeply

Read the complete text