Berkeley APR: Teaching Large Models to Think in Multithreaded Mode

Large-Model Inference: Time to “Open Multiple Threads”

Over the past year, the entire industry has been fixated on test-time compute. From OpenAI’s o1 and o3 to DeepSeek-R1 and various “thinking” modes from other labs, there have been only two mainstream approaches: either extend the chain of thought (CoT) to make the model think longer in a single path, or use self-consistency—“multi-sample voting”—where N independent threads run separately and then the most frequent answer is selected.

Neither approach is elegant. The former is constrained by context window and latency—when wrong, you have to backtrack a long way; the latter is a brute-force “manpower tactic,” with no communication between threads and severe redundancy. A team from UC Berkeley and UCSF recently revisited this problem from scratch—their paper Learning Adaptive Parallel Reasoning with Language Models (arXiv:2504.15466) proposes Adaptive Parallel Reasoning (APR). Combined with BAIR’s new system-side analysis, the picture is becoming clearer: let the model learn when to start new threads, how many to open, and how to join them.

For developers building Agents and complex reasoning products, this means much more than “another new benchmark SOTA.”

What APR Does: Writing Map-Reduce into the Decoding Process

The core abstraction of APR is actually programmer-friendly—it treats the reasoning process as a map-reduce operation:

• spawn(): The parent thread, during decoding, can at any time split the current problem into multiple subtasks, each running concurrently as a separate subthread.
• join(): After all subthreads finish, their results are merged back into the parent thread’s context so the parent can continue decoding or spawn more threads.

The key difference from self-consistency is that the subthread results are not used for voting; instead, they flow back as “research materials” for the parent thread. The parent retains coordination authority—it can decide whether to open another round or shift perspective.

Put differently, think in terms of a project manager: CoT is one person working heads-down; self-consistency is ten people each doing their own thing, then voting; APR is one PM who, while working, temporarily assigns colleagues to investigate subproblems in parallel and then decides the next step after receiving their feedback.

Crucially, when to spawn and how many subthreads to launch is not rule-based—it’s learned end-to-end through reinforcement learning. That’s the key distinction from external orchestration frameworks like Tree-of-Thoughts or ReAct: APR burns the control flow into the model weights themselves.

Data: Up to 18 Points Higher Accuracy under the Same Latency

The team ran controlled experiments on the Countdown task (a number game similar to an extended version of “24”). A few notable numbers:

• Same context window (4k): APR accuracy 83.4%, traditional serial CoT 60.0%.
• Same total token budget (20k): APR 80.1%, serial 66.6%.
• Same latency (~5000ms): APR 75.2%, serial 57.3%.

The third data point is the most valuable engineer-wise—production users care about wait time, not token count. APR parallelizes computation across concurrent threads, trading bandwidth for latency, which naturally aligns with the concurrency capabilities of GPU inference engines.

Another interesting observation: after RL optimization, the model spontaneously shifted toward “more breadth rather than more depth.” The average number of subthreads grew from 6.1 to 8.2 (+34%), while single-thread length rose only from 1471 to 1796 tokens (+22%). In other words, the model realized on its own that it’s better to branch wider with multiple shorter paths than to go deeper on one. This mirrors human experts’ “diverge first, then converge” reasoning intuition.

The System-Side Hard Problem: How to Merge KV Caches

APR’s algorithm isn’t particularly complex—the tricky part is coordinating with the inference engine. BAIR’s blog offers a thorough discussion; anyone trying to reproduce this will need to tackle it.

The problem appears at the join stage. Each subthread is sent as an independent request to the inference engine. They:

1. Share the same prefix (the subtask list given by the parent thread when spawning);
2. Start decoding from the same position id;
3. Have no mutual attention.

When joining back into the parent thread, the challenge emerges: naively concatenating these KV caches leads to overlapping position ids and non-causal attention patterns—patterns the base model has never seen during training, which leads to messy results.

The community currently has two approaches:

Approach 1: Modify the Inference Engine (Multiverse Path)

Multiverse (Yang et al., 2025) modifies inference engines like SGLang at the memory management level. Using RadixAttention’s prefix tree mechanism, all subthreads share the prefix KV cache, avoiding redundant prefill. When subthreads finish, the engine reuses their KV caches with position id remapping and attention mask correction, ensuring the merged sequence appears “valid” to the base model.

The benefit: maximum performance—only compute the prefix once, no KV recomputation. The downside: you must modify the engine, so the barrier is high for teams unfamiliar with vLLM/SGLang.

Approach 2: Bypass the Engine (Application-Layer Solution)

The other camp leaves the engine untouched, handling the join process at the application layer: transform subthread outputs into text and feed them back into the parent context with a new prefill. It’s universally compatible (works with any OpenAI-compatible endpoint), but all KV caches must be recomputed—higher token cost and latency.

For most product teams, the second approach is a more practical starting point—train the model with APR first, and even if runtime efficiency lags, you can immediately benefit from the accuracy boost. Once use cases stabilize, consider deeper engine-level Multiverse-style optimization.

Comparison with Recent Related Work

Looking at APR within the 2025–2026 evolution of reasoning paradigms clarifies its position:

• ALPHAONE (α1): Tunes the step-size of a single reasoning chain during test time—a “speed controller,” still serial at heart.
• Multiverse: Solves engineering issues of system-level parallel inference, complementary to APR rather than substitutive.
• ACE (Agentic Context Engineering, Stanford/SambaNova/UCB): Takes a different path—no fine-tuning, but “generate–reflect–integrate” tri-role interaction to evolve context into a living playbook. Orthogonal to APR: APR changes model control flow; ACE changes context organization. They can stack together.
• SUSTech SPPO: Models reasoning training as a sequence-level contextual bandit, replacing GRPO’s multi-sampling with single-sample optimization to cut costs. It optimizes RL training efficiency, while APR optimizes allocation of test-time compute.

If 2024’s keyword was “making models think longer,” the 2025–2026 wave is shifting to “making models think more intelligently about how to think”—a step closer to general intelligence.

What This Means for Developers

Here are a few immediately actionable insights:

1. Agent frameworks can redesign scheduling logic. Most current Agent frameworks (e.g., LangGraph, AutoGen) rely on developer-specified concurrency—“open 3 workers here” is hardcoded. APR introduces the possibility of models emitting spawn tokens themselves while the framework merely executes—drastically simplifying multi-agent orchestration code.

2. New lever for latency optimization in complex tasks. For code generation, long-document analysis, or math/scientific reasoning, lowering latency once meant using smaller models or speculative decoding. Now you can optimize at the reasoning graph structure level—parallel tasks go parallel, serial stay serial.

3. Requires redesign of the RL reward signal. APR uses end-to-end RL, where the reward must guide correct answers and teach good spawn strategies. The paper notes initial supervised pretraining using trajectories from symbolic solvers; in the future, pure RL (à la R1-Zero) is worth watching.

4. Open-source ecosystem participation. Code and data are open-sourced (github.com/Parallel-Reasoning/APR), currently validated on Countdown tasks. Expanding to code, math contests, and long-form QA is an obvious next step. If you already have an RL training pipeline, this is a high-ROI reproduction opportunity.

A Personal Judgment

In my view, APR’s value isn’t in those few percentage points on the Countdown task—it’s that it hands control of “reasoning flow” back to the model itself for the first time. In the past, orchestration lived outside the model—CoT, ToT, and Agents are all forms of orchestration. APR contends that control flow should live inside model weights, learned via RL rather than hand-engineered.

If this approach works, over time today’s hand-written Agent scheduling logic, self-consistency sampling counts, and ToT search depths may all become legacy baggage. A model that knows how to think is more important than one that just knows more.

Of course, it’s a distance from paper to production. Countdown is structured with clear rewards; in open-domain settings, designing the reward, enabling richer inter-thread communication (beyond simple fork-join, e.g., message passing or subscription), and reducing KV merge overhead—each of these could be a paper on its own.

But the direction is right. Worth keeping an eye on.

References

• linux.do: Adaptive Parallel Reasoning — The Next Paradigm for Efficient Inference Scaling — Chinese reprint of the BAIR blog with full discussion on KV cache merging at the system level
• GitHub: Parallel-Reasoning/APR — Official code, data, and training scripts for the paper