# Learning Adaptive Parallel Reasoning with Language Models

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

## Key facts

- Cited by 58 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 33 of its 35 references that are in the map.
- First posted on arXiv 21 Apr 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 33)

- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Improving Factuality and Reasoning in Language Models through Multiagent Debate](https://mlsanity.com/paper/2305.14325/) (2023)
- [Decision Transformer: Reinforcement Learning via Sequence Modeling](https://mlsanity.com/paper/2106.01345/) (2021)
- [Kimi k1.5: Scaling Reinforcement Learning with LLMs](https://mlsanity.com/paper/2501.12599/) (2025)
- [Measuring and Narrowing the Compositionality Gap in Language Models](https://mlsanity.com/paper/2210.03350/) (2022)
- [STaR: Bootstrapping Reasoning With Reasoning](https://mlsanity.com/paper/2203.14465/) (2022)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Mixture-of-Agents Enhances Large Language Model Capabilities](https://mlsanity.com/paper/2406.04692/) (2024)
- [Think before you speak: Training Language Models With Pause Tokens](https://mlsanity.com/paper/2310.02226/) (2023)
- [Chain of Agents: Large Language Models Collaborating on Long-Context Tasks](https://mlsanity.com/paper/2406.02818/) (2024)
- [An LLM Compiler for Parallel Function Calling](https://mlsanity.com/paper/2312.04511/) (2023)
- [Stream of Search (SoS): Learning to Search in Language](https://mlsanity.com/paper/2404.03683/) (2024)
- [Skeleton-of-Thought: Prompting LLMs for Efficient Parallel Generation](https://mlsanity.com/paper/2307.15337/) (2023)
- [S*: Test Time Scaling for Code Generation](https://mlsanity.com/paper/2502.14382/) (2025)
- [Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models](https://mlsanity.com/paper/2308.10379/) (2023)
- [Language Agents as Optimizable Graphs](https://mlsanity.com/paper/2402.16823/) (2024)
- [Atom of Thoughts for Markov LLM Test-Time Scaling](https://mlsanity.com/paper/2502.12018/) (2025)
- [Fine-Tuning Language Models with Advantage-Induced Policy Alignment](https://mlsanity.com/paper/2306.02231/) (2023)
- [PENCIL: Long Thoughts with Short Memory](https://mlsanity.com/paper/2503.14337/) (2025)
- [Hogwild! Inference: Parallel LLM Generation via Concurrent Attention](https://mlsanity.com/paper/2504.06261/) (2025)
- [Learning to Keep a Promise: Scaling Language Model Decoding Parallelism with Learned Asynchronous Decoding](https://mlsanity.com/paper/2502.11517/) (2025)
- [THREAD: Thinking Deeper with Recursive Spawning](https://mlsanity.com/paper/2405.17402/) (2024)

## Built on by (most cited first, 30 of 58)

- [CaP-X: A Framework for Benchmarking and Improving Coding Agents for Robot Manipulation](https://mlsanity.com/paper/2603.22435/) (2026)
- [Parallel-R1: Towards Parallel Thinking via Reinforcement Learning](https://mlsanity.com/paper/2509.07980/) (2025)
- [ParaThinker: Native Parallel Thinking as a New Paradigm to Scale LLM Test-time Compute](https://mlsanity.com/paper/2509.04475/) (2025)
- [Reflect, Retry, Reward: Self-Improving LLMs via Reinforcement Learning](https://mlsanity.com/paper/2505.24726/) (2025)
- [Reasoning on a Budget: A Survey of Adaptive and Controllable Test-Time Compute in LLMs](https://mlsanity.com/paper/2507.02076/) (2025)
- [R1-Compress: Long Chain-of-Thought Compression via Chunk Compression and Search](https://mlsanity.com/paper/2505.16838/) (2025)
- [Multiverse: Your Language Models Secretly Decide How to Parallelize and Merge Generation](https://mlsanity.com/paper/2506.09991/) (2025)
- [Scaling Offline RL via Efficient and Expressive Shortcut Models](https://mlsanity.com/paper/2505.22866/) (2025)
- [Flash-Searcher: Fast and Effective Web Agents via DAG-Based Parallel Execution](https://mlsanity.com/paper/2509.25301/) (2025)
- [VeriThinker: Learning to Verify Makes Reasoning Model Efficient](https://mlsanity.com/paper/2505.17941/) (2025)
- [Learning to Orchestrate Agents in Natural Language with the Conductor](https://mlsanity.com/paper/2512.04388/) (2025)
- [Group Think: Multiple Concurrent Reasoning Agents Collaborating at Token Level Granularity](https://mlsanity.com/paper/2505.11107/) (2025)
- [Rethinking Thinking Tokens: LLMs as Improvement Operators](https://mlsanity.com/paper/2510.01123/) (2025)
- [RLAD: Training LLMs to Discover Abstractions for Solving Reasoning Problems](https://mlsanity.com/paper/2510.02263/) (2025)
- [Multiplex Thinking: Reasoning via Token-wise Branch-and-Merge](https://mlsanity.com/paper/2601.08808/) (2026)
- [StreamingThinker: Large Language Models Can Think While Reading](https://mlsanity.com/paper/2510.17238/) (2025)
- [Dynamic Speculative Agent Planning](https://mlsanity.com/paper/2509.01920/) (2025)
- [Retrieval-of-Thought: Efficient Reasoning via Reusing Thoughts](https://mlsanity.com/paper/2509.21743/) (2025)
- [Native Parallel Reasoner: Reasoning in Parallelism via Self-Distilled Reinforcement Learning](https://mlsanity.com/paper/2512.07461/) (2025)
- [V1: Unifying Generation and Self-Verification for Parallel Reasoners](https://mlsanity.com/paper/2603.04304/) (2026)
- [Scaling over Scaling: Exploring Test-Time Scaling Plateau in Large Reasoning Models](https://mlsanity.com/paper/2505.20522/) (2025)
- [ASPD: Unlocking Adaptive Serial-Parallel Decoding by Exploring Intrinsic Parallelism in LLMs](https://mlsanity.com/paper/2508.08895/) (2025)
- [A Survey on Parallel Reasoning](https://mlsanity.com/paper/2510.12164/) (2025)
- [Adaptive Termination for Multi-round Parallel Reasoning: An Universal Semantic Entropy-Guided Framework](https://mlsanity.com/paper/2507.06829/) (2025)
- [Planned Diffusion](https://mlsanity.com/paper/2510.18087/) (2025)
- [Recursive Models for Long-Horizon Reasoning](https://mlsanity.com/paper/2603.02112/) (2026)
- [ThreadWeaver: Adaptive Threading for Efficient Parallel Reasoning in Language Models](https://mlsanity.com/paper/2512.07843/) (2025)
- [VTC-R1: Vision-Text Compression for Efficient Long-Context Reasoning](https://mlsanity.com/paper/2601.22069/) (2026)
- [Understanding the Challenges in Iterative Generative Optimization with LLMs](https://mlsanity.com/paper/2603.23994/) (2026)
- [The Era of Agentic Organization: Learning to Organize with Language Models](https://mlsanity.com/paper/2510.26658/) (2025)

## Abstract (arXiv)

Scaling inference-time computation has substantially improved the reasoning capabilities of language models. However, existing methods have significant limitations: serialized chain-of-thought approaches generate overly long outputs, leading to increased latency and exhausted context windows, while parallel methods such as self-consistency suffer from insufficient coordination, resulting in redundant computations and limited performance gains. To address these shortcomings, we propose Adaptive Parallel Reasoning (APR), a novel reasoning framework that enables language models to orchestrate both serialized and parallel computations end-to-end. APR generalizes existing reasoning methods by enabling adaptive multi-threaded inference using spawn() and join() operations. A key innovation is our end-to-end reinforcement learning strategy, optimizing both parent and child inference threads to enhance task success rate without requiring predefined reasoning structures. Experiments on the Countdown reasoning task demonstrate significant benefits of APR: (1) higher performance within the same context window (83.4% vs. 60.0% at 4k context); (2) superior scalability with increased computation (80.1% vs. 66.6% at 20k total tokens); (3) improved accuracy at equivalent latency (75.2% vs. 57.3% at approximately 5,000ms). APR represents a step towards enabling language models to autonomously optimize their reasoning processes through adaptive allocation of computation.