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

arXiv: https://arxiv.org/abs/2505.22290 · HTML: https://mlsanity.com/paper/2505.22290/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 35 of its 51 references that are in the map.
- First posted on arXiv 28 May 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 30 of 35)

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [CommonsenseQA: A Question Answering Challenge Targeting Commonsense Knowledge](https://mlsanity.com/paper/1811.00937/) (2018)
- [OpenAI o1 System Card](https://mlsanity.com/paper/2412.16720/) (2024)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [Automatic Chain of Thought Prompting in Large Language Models](https://mlsanity.com/paper/2210.03493/) (2022)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [A Survey on Test-Time Scaling in Large Language Models: What, How, Where, and How Well?](https://mlsanity.com/paper/2503.24235/) (2025)
- [When More is Less: Understanding Chain-of-Thought Length in LLMs](https://mlsanity.com/paper/2502.07266/) (2025)
- [NATURAL PLAN: Benchmarking LLMs on Natural Language Planning](https://mlsanity.com/paper/2406.04520/) (2024)
- [Between Underthinking and Overthinking: An Empirical Study of Reasoning Length and correctness in LLMs](https://mlsanity.com/paper/2505.00127/) (2025)
- [LLMs Still Can't Plan; Can LRMs? A Preliminary Evaluation of OpenAI's o1 on PlanBench](https://mlsanity.com/paper/2409.13373/) (2024)
- [Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models](https://mlsanity.com/paper/2308.10379/) (2023)
- [Revisiting the Test-Time Scaling of o1-like Models: Do they Truly Possess Test-Time Scaling Capabilities?](https://mlsanity.com/paper/2502.12215/) (2025)
- [Evolving Deeper LLM Thinking](https://mlsanity.com/paper/2501.09891/) (2025)
- [Large Language Models Can Solve Real-World Planning Rigorously with Formal Verification Tools](https://mlsanity.com/paper/2404.11891/) (2024)
- [Theoretical limitations of multi-layer Transformer](https://mlsanity.com/paper/2412.02975/) (2024)
- [The relationship between reasoning and performance in large language models--o3 (mini) thinks harder, not longer](https://mlsanity.com/paper/2502.15631/) (2025)
- [Can We Rely on LLM Agents to Draft Long-Horizon Plans? Let's Take TravelPlanner as an Example](https://mlsanity.com/paper/2408.06318/) (2024)
- [Climbing the Ladder of Reasoning: What LLMs Can-and Still Can't-Solve after SFT?](https://mlsanity.com/paper/2504.11741/) (2025)
- [Revealing the Barriers of Language Agents in Planning](https://mlsanity.com/paper/2410.12409/) (2024)
- [Innate Reasoning is Not Enough: In-Context Learning Enhances Reasoning Large Language Models with Less Overthinking](https://mlsanity.com/paper/2503.19602/) (2025)
- [Quantifying Generalization Complexity for Large Language Models](https://mlsanity.com/paper/2410.01769/) (2024)
- [Rethinking Inference-Time Scaling: Efficiency Limits and Linguistic Signals](https://mlsanity.com/paper/2504.14047/) (2025)
- [Planning in Strawberry Fields: Evaluating and Improving the Planning and Scheduling Capabilities of LRM o1](https://mlsanity.com/paper/2410.02162/) (2024)
- [RePrompt: Planning by Automatic Prompt Engineering for Large Language Models Agents](https://mlsanity.com/paper/2406.11132/) (2024)
- [LLMs Can Plan Only If We Tell Them](https://mlsanity.com/paper/2501.13545/) (2025)

## Built on by (most cited first, 2 of 2)

- [Adaptive Test-Time Compute Allocation with Evolving In-Context Demonstrations](https://mlsanity.com/paper/2604.21018/) (2026)
- [When Does In-Context Search Help? A Sampling-Complexity Theory of Reflection-Driven Reasoning](https://mlsanity.com/paper/2607.06720/) (2026)

## Abstract (arXiv)

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 30x 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.