Learning Adaptive Parallel Reasoning with Language Models

ArXiv: 2504.15466

🎯 Pitch

Language models trained with simple spawn/join operations learn to dynamically fork search into parallel child threads, achieving 83% accuracy on a reasoning task where serial methods hit just 60%—all within the same context budget. Remarkably, reinforcement learning unlocks this gain not by refining search quality but by teaching models to launch 34% more parallel threads, enabling far better compute-accuracy scaling.

---

1. Executive Summary

This paper proposes Adaptive Parallel Reasoning (APR), a framework that enables language models to dynamically distribute inference-time computation across both serial and parallel reasoning paths through a parent-child threading mechanism with spawn() and join() operations (e.g., a parent thread delegates subtasks to multiple child threads that explore distinct solution branches concurrently, then returns only successful outcomes). The approach is evaluated on the Countdown arithmetic reasoning task using a 228M-parameter Llama2 model trained from scratch, combining supervised learning on hybrid search demonstrations with end-to-end reinforcement learning via GRPO . APR achieves 83.4% accuracy versus 60.0% for serialized search at the same 4k-token context window, reaches 80.1% versus 66.6% when scaled to 20k total tokens, and delivers 75.2% accuracy versus 57.3% at approximately 5,000ms latency. Reinforcement learning primarily improves performance by teaching the model to use more parallel threads — a 34.4% relative increase in spawned child threads — rather than by improving search quality within a fixed budget, establishing that learned adaptive parallelization unlocks substantially better compute-accuracy scaling than serialized reasoning alone.

2. Context and Motivation

The Core Problem: Inference-Time Compute Is Scaling, But Its Structure Is Rigid

The fundamental tension this paper addresses is straightforward to state but deeply consequential: language models are getting better at reasoning by spending more computation at inference time, but the way they spend that computation is structurally inefficient. As models like OpenAI's o1 (OpenAI, 2024) and DeepSeek-R1 (DeepSeek-AI, 2025) have demonstrated, allowing a language model to "think longer" — generating extended chains of reasoning before producing a final answer — yields substantial improvements on complex tasks. However, this improvement comes at a structural cost that the field has not yet solved.

The problem has two distinct dimensions, and they pull in opposite directions:

First, serialized reasoning creates a context window bottleneck. When a model generates a long chain-of-thought trace — exploring multiple solution paths, backtracking from dead ends, verifying intermediate results — it must fit the entire search history into a single context window. This is not merely an implementation detail; it is a fundamental constraint on how much reasoning a model can perform. The context window imposes a hard ceiling on the depth and breadth of search. If a model exhausts its context before finding a solution, the computation is wasted. This is particularly acute for problems requiring broad exploration: the model needs to try many approaches, but each attempt consumes tokens in the same serial buffer, and the failed attempts can crowd out the eventual successful path.

Second, serialized reasoning creates a latency bottleneck. Autoregressive generation is inherently sequential — each token depends on all previous tokens, and they must be generated one at a time. For complex reasoning problems, traces can stretch to thousands or tens of thousands of tokens. At typical serving speeds (50-100 tokens per second for large models), this translates to latencies of 10-60+ seconds. For interactive applications, this is unacceptable. For batch processing, it limits throughput. The latency is structural: no amount of GPU parallelism can speed up the generation of token $t$ before tokens $1 \ldots t-1$ have been produced, because the autoregressive dependency chain is serial.

These two bottlenecks — context window exhaustion and latency — are both consequences of the same architectural fact: current reasoning approaches serialize an inherently parallelizable computation (search) into a single sequential trace.

Why This Problem Matters

The significance extends beyond an engineering concern about efficiency. It bears on the scalability of the entire reasoning-via-search paradigm.

If we believe that continued progress in language model reasoning will come from models that can perform increasingly sophisticated search at inference time — trying more strategies, exploring deeper trees, verifying more hypotheses — then the serial bottleneck becomes a hard ceiling on that progress. You cannot simply "make the context window bigger" indefinitely; attention mechanisms scale quadratically with sequence length, and even linear-attention approximations face diminishing returns in practice. You also cannot simply accept unbounded latency; many applications have hard real-time constraints (interactive assistants, autonomous systems, real-time code generation).

The paper implicitly identifies a scaling law mismatch: the field has developed a good understanding of how to scale pretraining compute (Hoffmann et al., 2022) and is beginning to understand how total test-time FLOPs scale with performance (Snell et al., 2025), but we lack a systematic understanding of how the structure of test-time compute allocation affects both performance and efficiency. The paper positions APR as a step toward filling this gap — not by proposing yet another search algorithm, but by reimagining the interface through which models express search.

There is also a practical deployment argument: as language models move from research demos to production systems, the difference between "the model can eventually solve this" and "the model can solve this within 2 seconds" becomes the difference between a viable product and a laboratory curiosity. APR addresses this directly by enabling the model to trade off latency against exploration breadth in a learned, problem-adaptive way.

Where Prior Approaches Fall Short

The paper identifies three categories of prior work, each with distinct limitations:

Serialized Chain-of-Thought and Search Methods

The dominant paradigm for reasoning — from simple chain-of-thought prompting (Wei et al., 2022) to sophisticated learned search like Stream of Search (Gandhi et al., 2024) and DeepSeek-R1 (DeepSeek-AI, 2025) — serializes the entire reasoning process into a single output sequence. In Stream of Search (SoS), for instance, the model generates a textual representation of a search algorithm (BFS or DFS), exploring nodes, backtracking, and eventually finding a solution — all as one long string. This approach has demonstrated that models can learn to search, but it inherits all the structural limitations described above.

The paper makes a concrete observation about SoS that motivates APR: in serialized search, context window exhaustion can prevent the model from finding solutions that are discoverable with the same total compute distributed across parallel threads. Figure 1 illustrates this vividly — a serialized search trace runs out of context before reaching the solution, while APR's parallel decomposition finds it within the same constraints. This is not a hypothetical concern; it reflects a real failure mode where the serial structure, not the total computation budget, is the limiting factor.

Parallel Methods Without Coordination

The other major approach is generating multiple independent reasoning traces and aggregating them — best-of-N, self-consistency (majority voting), or verifier-based selection (Cobbe et al., 2021; Wang et al., 2023). These methods solve the latency problem (all traces can be generated in parallel) and the context window problem (each trace has its own window), but they introduce a different limitation: lack of coordination. Each trace starts from scratch, with no information sharing between them. If 8 out of 10 traces independently discover that approach A is a dead end, the remaining 2 traces still waste computation exploring it. The parallel threads cannot divide the search space, delegate subtasks, or learn from each other's failures.

The paper sees this as a form of redundant computation. In self-consistency, the $n$ independent samples $y_1, \ldots, y_n$ are drawn i.i.d. from the same distribution $p(y \mid x)$. If the model has a 10% chance of sampling a correct solution on any given attempt, you need $\sim 1/0.1 = 10$ samples in expectation to find one correct answer, but those 10 samples will contain 9 redundant incorrect traces that contribute nothing except as discarded computation. More subtly, if the incorrect traces fail for the same underlying reason (e.g., the model consistently makes a particular arithmetic error), the i.i.d. samples provide no mechanism for a trace to notice and correct that systematic error — they are independent and blind to each other's outputs.

Structured Search with Hand-Designed Architectures

A third category attempts to impose parallel structure from the outside — Tree-of-Thought (Yao et al., 2023), Graph-of-Thought (Besta et al., 2024), multi-agent debate (Du et al., 2023), and similar methods. These define explicit search algorithms (BFS, DFS, MCTS-style node expansion) and orchestrate multiple LLM calls according to that algorithm. A typical Tree-of-Thought implementation might generate $k$ candidate "next steps," evaluate each with the model, keep the top $b$, and recurse — with the search structure coded by the developer, not learned by the model.

The paper identifies two limitations of this approach:

1. Fixed, hand-designed structures limit flexibility. The search algorithm (BFS? DFS with backtracking? Beam search? Some hybrid?) must be chosen by the developer a priori. There is no mechanism for the model to dynamically adjust its search strategy based on the problem — perhaps some problems need wide shallow exploration while others need narrow deep search. The optimal strategy may even vary within a single problem, but hand-designed structures are typically uniform.

2. Prompting-based approaches suffer from distribution shift. These methods are predominantly implemented through prompting — the developer writes instructions telling the model to "generate 3 possible next steps, then evaluate each, then..." — without any training to optimize this process. The model was not trained on sequences that include this orchestration language, creating a distributional gap that can degrade performance and prevent the model from developing its own more efficient coordination strategies.

The paper explicitly positions APR relative to this category: "In theory, our framework could result in language models that implement the same search structures as existing approaches, such as Tree-of-Thought, without explicit prompting or hand-designed orchestration of language model calls" (Appendix A.1). The key distinction is that in APR, the structure is emergent from training rather than imposed by the developer — the model learns when and how to parallelize as part of an end-to-end optimization process.

How This Paper Positions Itself

APR occupies a specific, previously empty point in the design space. The paper's positioning can be understood through three conceptual moves:

First, it reframes the problem from "design a better search algorithm" to "design a better interface for the model to express its own search algorithms." Rather than imposing BFS, DFS, or any other structure, APR provides the model with two primitive operations — spawn() to delegate subtasks to parallel child threads, and join() to collect their results — and then lets the model learn (via RL) how to compose these primitives into effective problem-solving strategies. This is a shift from algorithmic design to meta-algorithmic learning: the model learns the search algorithm, not the developer.

Second, it positions itself as a synthesis of the parallel and serial paradigms. APR is not "parallel instead of serial" — the parent thread itself executes sequential reasoning, and the model can choose at any point whether to continue serially or spawn parallel child threads. This adaptive blending captures the best of both worlds: sequential reasoning where it is efficient (narrow, deep exploration of a promising path) and parallel reasoning where it is necessary (broad exploration of multiple alternatives). The model learns to make this tradeoff through end-to-end optimization.

Third, it introduces end-to-end reinforcement learning as a mechanism for optimizing coordination behavior. Prior parallel methods (self-consistency, multi-agent debate) use fixed coordination protocols. APR trains the model to coordinate through RL, where the reward signal (task success) propagates back to influence both the quality of individual reasoning steps and the meta-decisions about when to spawn, how many threads to spawn, and what context to pass to each thread. The paper's finding that RL primarily improves performance by increasing parallelism (34.4% more child threads) rather than improving per-step reasoning quality — discussed in the ablation study (Section 4.4) — is itself a revealing result about where the optimization pressure lands: the model discovers that wider search is more valuable than deeper search, and adjusts its behavior accordingly.

The Specific Gap: Coordinated, Learned Parallelization

To synthesize: the paper addresses a specific and previously unfilled gap in the landscape of inference-time reasoning methods. Existing approaches force a choice between three suboptimal options:

• Serial search (SoS, DeepSeek-R1): coordinated reasoning but with context window and latency bottlenecks.
• Independent parallel sampling (self-consistency): latency-efficient but uncoordinated, leading to redundant computation.
• Hand-designed parallel structures (Tree-of-Thought): coordinated parallel reasoning but with fixed, non-learned structures that limit flexibility and scalability.

APR proposes a fourth option: coordinated parallel reasoning where the coordination protocol is learned end-to-end. The model decides when to spawn, what subtasks to delegate, how many threads to use, and what information to pass between threads — all shaped by reinforcement learning to maximize task success under the practical constraints of context windows and latency. This is not an incremental improvement on any single prior approach; it is a reconceptualization of how models should interface with inference-time computation, moving from developer-specified to model-learned orchestration.

3. Technical Approach

3.1 Reader Orientation

This paper builds a reasoning system where a language model autonomously decides how to distribute its inference-time computation across serial and parallel execution paths — the model learns to recognize when a problem requires exploring multiple solution branches simultaneously (parallel) versus when it benefits from focused, sequential refinement (serial), and it orchestrates this distribution through a parent-child threading mechanism that it controls itself. The core problem it solves is the structural inefficiency of existing reasoning methods: serial approaches bottleneck on context window limits and latency, while parallel approaches waste computation through redundant, uncoordinated exploration — APR provides a unified interface (spawn() and join()) through which the model can dynamically allocate its compute budget in whatever geometry best suits the problem at hand, with the allocation strategy itself optimized end-to-end via reinforcement learning.

3.2 Big-Picture Architecture (Diagram in Words)

The APR system has four major components, arranged in a hierarchy of operation:

1. The Language Model (shared across all threads) — a single 228M-parameter Llama2-architecture decoder that serves as the "reasoning engine" for both the parent thread and all child threads. Crucially, it is the same model that executes in every thread, meaning there is no division into specialized roles (e.g., "planner" vs. "executor"); the model must learn to function appropriately depending on the context it receives when a thread is launched.

2. The Multi-Thread Inference Infrastructure (powered by SGLang) — a serving layer that implements the spawn() and join() operations, managing the concurrent execution of child threads with prefix caching and continuous batching. This layer handles the mechanical details of parallelization: when the model generates a spawn(msgs) token sequence, the infrastructure creates new inference requests for each message in msgs, executes them concurrently on available GPUs, collects their outputs (terminated by join(msg) tokens), and feeds the aggregated results back into the parent thread's context. The parent thread remains suspended during child execution and resumes only after all children have joined.

3. The Supervised Training Demonstrations (APR Symbolic Solver) — a training data generation pipeline that produces reasoning traces demonstrating how to use spawn() and join() for Countdown problems. This solver executes a hybrid search (mixing BFS and DFS) and, at promising nodes, delegates the exploration of child branches to simulated parallel sub-searches. The resulting traces serve as supervised learning targets for the initial policy — the model learns from these examples what sequences of tokens constitute valid APR reasoning.

4. The Reinforcement Learning Optimization Loop (GRPO) — a training stage that takes the supervised policy and further optimizes it through end-to-end RL on the task reward. This stage is where the model learns to make its own decisions about when to spawn, how many threads to spawn, and what context to pass to each thread, beyond merely imitating the solver's fixed heuristics.

Information flows through the system in a cycle: a Countdown problem enters as input → the parent thread begins generating reasoning tokens → at some point (determined by the model), it generates a spawn(msgs) call → the inference infrastructure launches child threads with their assigned contexts → child threads independently generate reasoning traces, each terminating with a join(msg) that returns either a solution summary or a failure signal → the parent thread resumes, conditioned on the concatenated join() outputs → the parent thread continues reasoning, potentially spawning more rounds of children → eventually, the parent thread produces a final arithmetic expression as the solution → the expression is checked against the ground-truth target to compute a binary task reward → this reward is used to update the model parameters via GRPO.

3.3 Roadmap for the Deep Dive

• First, the Countdown task and the reasoning-as-search formalism, because the task defines the action space (numbers, arithmetic operations) and the search space that APR must navigate, and understanding the problem structure clarifies why parallelization is beneficial.

• Second, the multi-thread inference mechanism — spawn() and join() — since this is the novel interface that distinguishes APR from all prior work; understanding exactly what operations the model can invoke, what constraints they impose, and how the infrastructure executes them is prerequisite to understanding everything else.

• Third, the supervised data generation pipeline (the APR symbolic solver) , because the model must first be taught via imitation what valid APR reasoning traces look like before RL can optimize them; this section explains how the solver constructs parallelized search demonstrations and what design choices went into the hybrid search strategy.

• Fourth, the supervised training procedure , covering the model architecture, training data composition, and how the model is conditioned to control the amount of parallelism — this establishes the initial policy that RL refines.

• Fifth, the reinforcement learning optimization stage , where GRPO takes the supervised policy and improves it end-to-end; this section explains the reward structure, the advantage estimation, the KL regularization, and the specific implementation choices that enable stable training.

• Sixth, the inference-time execution model , describing how a trained APR model actually runs on hardware: how SGLang enables concurrent child thread execution, how prefix caching reduces redundant computation, and how the sequential-vs-wall-clock latency tradeoff manifests in practice.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily a systems-and-training paper whose core idea is that language models can learn, via end-to-end reinforcement learning, to dynamically allocate inference-time computation between serial and parallel execution paths using a parent-child threading abstraction — and that this learned allocation yields superior compute-accuracy and latency-accuracy scaling compared to purely serial or purely parallel (but uncoordinated) baselines.

---

The Countdown Task and the Reasoning-as-Search Formalism

The paper evaluates APR on the Countdown task, a structured arithmetic reasoning problem that has become a standard testbed for language model search algorithms (Yao et al., 2023; Gandhi et al., 2024; Pan et al., 2025). Understanding the task's structure is essential because APR's design decisions — particularly the spawn() and join() interface — are shaped by the specific computational characteristics of tree-structured search.

Problem definition. A Countdown instance consists of a set of four input numbers and a single target number. The model must produce a valid arithmetic expression that uses each of the four input numbers exactly once, combines them with the four basic arithmetic operations (addition, subtraction, multiplication, division), and evaluates to exactly the target number. For example, given input numbers $\{1, 4, 6, 8\}$ and target $10$, one valid solution is $(8 - 6) \times (4 + 1) = 10$. All intermediate results must be non-negative integers (the standard Countdown constraint), and division is only permitted when it yields an integer result.

Why this task enables studying reasoning-as-search. The Countdown task has a natural tree structure. Starting from the initial state (four unused numbers, current value undefined), each step selects two available numbers and an operation, combines them into an intermediate result, and adds that result to the pool of available numbers while removing the two used numbers. This reduces the pool size by one per step. After three operations, only one number remains — if it matches the target, the solution is valid. The search tree branches at each step: with $k$ available numbers, there are $\binom{k}{2} \times 4$ possible (number pair, operation) combinations to try. For four starting numbers, the branching factor starts at $\binom{4}{2} \times 4 = 24$ (though many are pruned by the integer constraint), then decreases as the pool shrinks.

This structure makes Countdown an ideal testbed for studying inference-time compute allocation because:

• The search space is large enough to be non-trivial but small enough that tractable solutions exist — a symbolic solver can enumeratively search the entire tree, which means we can generate ground-truth training demonstrations and evaluate model accuracy unambiguously.
• The problem has a clear correctness signal — either the expression evaluates to the target or it does not — which provides a binary reward for RL without human annotation.
• The parallelization opportunities are natural: when the model reaches a state with multiple promising next steps, exploring them in parallel (rather than sequentially, one after another) reduces wall-clock time and distributes the context-window burden across separate inference threads.

The search-as-language interface. Following Stream of Search (Gandhi et al., 2024), the model does not interact with an external search engine or symbolic solver. Instead, it generates a natural-language representation of search — tokens like "Moving to Node #0 Current State: 27:[22, 26, 31, 53], Operations: []" and "Exploring Operation: 53-22=31, Resulting Numbers: [26, 31, 31]" — that describe the search tree traversal. The model must learn to produce these tokens autoregressively, track which states it has visited, recognize when a branch is a dead end, and backtrack appropriately. This is a demanding capability: the model is simultaneously the search algorithm implementer and the search step executor, all through the medium of token generation.

The key distinction from SoS is that APR's search language includes two additional operations — spawn() and join() — that allow the model to express parallel decomposition of the search tree within its reasoning trace.

---

The Multi-Thread Inference Mechanism: spawn() and join()

This is the central technical innovation of the paper: providing the language model with an API for creating and managing parallel inference threads, where the model itself decides (through its generated tokens) when to invoke this API. The design draws an explicit analogy to multi-threading in operating systems, where a parent process can fork child processes that execute concurrently and later communicate their results back.

The spawn(msgs) operation. During autoregressive decoding, the model can generate a special token sequence that the inference infrastructure interprets as a spawn command. The syntax is a structured text string: the model outputs something like <Calling Sub Searches><Start Sub Search 0 at level 1>Moving to Node #0,0 Current State: 27:[26, 31, 31], Operations: ['53-22=31']<Start Sub Search 1 at level 1>Moving to Node #0,1 Current State: 27:[26, 31, 31], Operations: ['53-22=31']<End Calling Sub Searches>. The infrastructure parses this to extract the list msgs, where each msg is a string that serves as the initial context for one child thread.

The critical design choice here is what context the parent thread passes to each child. The msg for a child thread contains:

• The target number.
• The current state (remaining input numbers, accumulated operations so far).
• The specific node or subtask the child should explore (e.g., "start from this state and explore operations from here").

Crucially, the parent thread does not pass its full reasoning history to the children. Each child thread starts from a clean context containing only the information the parent explicitly provides in msg. This is a deliberate architectural decision that directly addresses the context window bottleneck: if the parent transmitted its entire search trace to every child, the context window problem would simply be replicated across threads. By limiting child context to task-relevant state, the parent offloads the computation of exploring branches while keeping the memory of its own reasoning trajectory isolated. Children cannot see what other children are doing, nor can they see the parent's reasoning before the spawn point — they are independent explorers, each given a starting position and left to search from there.

Child thread execution. Each child thread is a fully independent autoregressive generation from the same language model checkpoint, conditioned on the msg it received. The child thread generates tokens in the same reasoning language as the parent — it describes nodes, explores operations, evaluates results — effectively executing a sub-search rooted at the state the parent assigned it.

The child thread has its own context window (the same 4,096-token limit), independent of the parent and of other children. This means the total effective context available to the system scales with the number of parallel threads: with $k$ children, the system can process approximately $k+1$ context windows' worth of tokens in parallel (one for each child plus the parent). This is the mechanism by which APR escapes the serial context window bottleneck — rather than packing an entire broad search into one 4k-token window, the search is fragmented across multiple windows that execute concurrently.

The join(msg) operation. When a child thread reaches a terminal state in its sub-search, it generates a join(msg) token sequence. The msg it returns is under the child thread's control — the model learns what information to summarize and pass back. For the Countdown task, the paper specifies a deliberate communication protocol:

• If the child thread finds a valid solution, it returns a concise summary of the successful solution path (the sequence of operations that produced the target) and discards the intermediate search trace. The example in Figure 3 shows a child returning: <Goal Reached in Sub Search 1 at level 1 at Node #0,1>...27,27 equal: Goal Reached.
• If the child thread exhausts its search without finding a solution, it returns a failure signal: <No Solution in Sub Search 0 at level 1 at Node #0,0>...No solution found.

This selective summarization is the second mechanism by which APR manages context window pressure. The parent thread does not receive the full search trace of each child — it receives only the outcome (solution found or not) and, if successful, the specific solution path. The intermediate exploration tokens that the child generated — the failed branches, the backtracking, the dead ends — are discarded and never enter the parent's context. This means the parent can incorporate the results of parallel search without paying the context cost of the process of that search.

Parent thread resumption. Once all spawned child threads have terminated (each with a join()), the parent thread resumes autoregressive generation from the point immediately after the spawn() call. Its context now includes the concatenated join() messages from all children. The parent can then:

• Continue the search from its own perspective, incorporating the solutions or failure signals from children.
• Spawn additional rounds of children (the model can generate multiple spawn() calls in sequence).
• If a child returned a solution, the parent can verify it, adopt it, or potentially improve it.
• If all children failed, the parent can try different branching strategies or continue serial exploration.

The threading abstraction's generality. The paper is careful to note that spawn() and join() are not specific to tree search or to Countdown. They are general-purpose coordination primitives that could be applied to any task where a model might benefit from parallelizing sub-computations: code generation (spawn threads to explore different implementation strategies), multi-step planning (spawn threads to evaluate different plan branches), or fact-checking (spawn threads to independently verify different claims). The Countdown task is a concrete instantiation that demonstrates the mechanism, but the architecture is domain-agnostic.

Why this specific interface? The paper implicitly motivates the spawn-join design through contrast with alternatives:

• Contrast with self-consistency: In self-consistency, parallel threads are independent and uninformed about each other; they cannot divide the search space because they all start from the identical prompt. APR's spawn(msgs) passes different contexts to different children, enabling explicit task decomposition — child 1 explores branch A, child 2 explores branch B.
• Contrast with hand-designed search structures: In Tree-of-Thought, the developer codes the branching logic ("generate k candidates, evaluate each, keep top b"). In APR, the model generates the branching logic through its token output — it decides what msgs to write, which amounts to deciding the search strategy.
• Contrast with complete-context merging: Concurrent work like PASTA (Jin et al., 2025) merges the full context from each sub-task back into the main thread. APR's selective join() — returning only the solution summary, not the search trace — is the mechanism that keeps the parent's context manageable.

---

The Supervised Data Generation Pipeline: The APR Symbolic Solver

Before the model can learn to generate APR reasoning traces through RL, it must first have an initial policy that produces syntactically valid spawn() and join() sequences. The paper uses supervised learning on automatically generated demonstrations to bootstrap this capability. The demonstration generation relies on a symbolic solver — a program that can enumeratively search the Countdown problem space and produce traces annotated with the parallelization operations.

Design philosophy: hybrid search demonstrations. The paper builds on the Stream of Search (SoS) solver from Gandhi et al. (2024), which produces serialized search traces for either BFS or DFS. However, APR needs demonstrations that exhibit both serial and parallel reasoning patterns, because the model must learn when each is appropriate. The paper develops a hybrid search that includes "examples of both BFS and DFS in the same search trace" (Section 3.3), which the authors empirically find to have "slightly better performance."

The intuition is that a pure BFS demonstration would show the model systematically expanding all nodes at depth 1, then all nodes at depth 2 — which is parallelizable but doesn't teach the model how to pause exploration on one branch to go deep on another. A pure DFS demonstration would show serial, deep exploration — which doesn't teach the model how to spawn parallel threads. The hybrid approach intermixes both patterns, providing the model with examples of when to explore broadly versus deeply.

The APR symbolic solver algorithm (Algorithm 2). The solver takes a start state (target number, set of input numbers) and a main boolean flag indicating whether this is the top-level search (parent thread) or a sub-search (child thread). The algorithm proceeds as follows:

1. Initialize a state deque (a double-ended queue used as a worklist) with the start state.
2. While the deque is not empty:
   • Pop the leftmost state from the deque.
   • If the state equals the goal state (remaining numbers contain only the target), return "Goal reached."
   • Generate candidate next states by applying all valid arithmetic operations to pairs of available numbers.
   • If this is the main (parent) thread AND the current state is "promising": instead of enqueuing children, spawn parallel sub-searches — for each candidate next state, recursively call APR(state, goal, main=False), executing all these sub-calls conceptually in parallel. If any sub-search returns "Goal reached," propagate that success upward.
   • Otherwise (not main, or not promising): add all candidate states to the back of the deque (standard BFS enqueuing) and continue.

This algorithm produces reasoning traces with a specific pattern: the parent thread does breadth-first exploration (enqueuing states in BFS order) until it encounters a "promising" node, at which point it spawns parallel DFS sub-searches under that node. The children then do depth-first exploration within their assigned subtrees.

The IS_PROMISING heuristic. The paper acknowledges the difficulty of implementing an accurate heuristic for identifying promising nodes and adopts a deliberately simple approach: "we simply let it return True for 10% of the time, which we leave reinforcement learning to further optimize the promising node selection strategies" (Appendix A.6). This is a key design choice:

• The supervised demonstrations will show the model spawning parallel threads at random-looking intervals — sometimes on genuinely promising nodes, sometimes arbitrarily.
• This randomness is intentional: it teaches the model the mechanics of spawn() and join() without encoding strong assumptions about when to use them.
• The RL stage is then responsible for learning a better IS_PROMISING policy — the model discovers for itself that spawning threads at certain types of states (those with many remaining numbers and multiple viable operation paths) is more productive than spawning at others.

The state expansion function (SE). Following Gandhi et al. (2024), the solver expands a state by considering all valid (number pair, operation) combinations and selecting the top $K$ ranked by the multiply heuristic. The multiply heuristic exploits the mathematical structure of the Countdown problem: it considers the target number $T$, the currently available numbers $n_1, \ldots, n_{|I|}$, and the factors of $T$. If $T$ has factors $\{f_1, f_2, \ldots, f_m\}$, the heuristic score for a candidate operation is:

$h_{\text{multiply}} = \min\left(\left\{ \left| f_j - \sum_{i=1}^{|I|} n_i \right| \; \forall j \in [1, m] \right\}\right)$

where $\sum_{i=1}^{|I|} n_i$ is the sum of the available numbers after applying the candidate operation, and the minimization is over all factors $f_j$ of the target.

What it computes: For each factor $f_j$ of the target, compute the absolute difference between that factor and the sum of available numbers after the operation. Take the minimum over all factors. A low score means that the sum of available numbers is close to a factor of the target, which is promising because it suggests that further operations (particularly multiplication or division) could reach the target.

Why this form: The heuristic is motivated by the observation that in Countdown, the final step to reach a target often involves multiplication by a factor — if you can make the sum of your numbers equal to a factor of the target, you are well-positioned for a successful final operation. The min over factors handles the case where the target has multiple possible factor decompositions. However, the paper does not explicitly justify choosing the sum of remaining numbers versus other aggregate statistics; this appears to be an empirically effective but structurally ad-hoc heuristic inherited from SoS.

The top $K$ states (the paper doesn't specify $K$ explicitly for the solver, but in the SoS+ baseline ablation in Appendix A.8, beam sizes of 5 and 15 are mentioned) are retained for exploration; the rest are pruned. This pruning makes the solver tractable (exhaustive enumeration of all valid operations at every step would be too expensive for demonstration generation at scale) while still producing correct solutions for most problems.

The SoS+ baseline solver. The paper also implements a serialized version of the hybrid solver (SoS+, Algorithm 1) for comparison. SoS+ uses the same hybrid BFS-DFS logic but never spawns parallel threads — it explores promising nodes sequentially via recursive calls within the same search trace. SoS+ serves as the baseline for evaluating whether the parallel decomposition itself (beyond just the hybrid search strategy) provides benefits.

Scale of demonstration data. The paper generates 500,000 Countdown problems and corresponding search traces using both SoS+ and APR symbolic solvers (Section 4, Experiment Setup). This large dataset is necessary because the models are trained from scratch (randomly initialized) — they must learn both the reasoning behavior and the language itself from these demonstrations, without the benefit of pretrained linguistic knowledge.

---

Supervised Training: Establishing the Initial APR Policy

The supervised training stage takes a randomly initialized language model and trains it via next-token prediction on the APR symbolic solver's demonstration traces. This stage is responsible for teaching the model the syntax of APR reasoning — the format of search traces, the structure of spawn() and join() operations, the representation of arithmetic states — before RL optimizes the strategy.

Model architecture. The paper uses a decoder-only language model following the Llama2 architecture (Team, 2023) with 228 million non-embedding parameters (293 million total parameters). The specifications are:

• 18 hidden layers.
• Hidden dimension of 1024.
• 16 attention heads.
• Context window of 4,096 tokens.
• Llama2 tokenizer.

The model size is deliberately modest — 228M parameters is roughly two orders of magnitude smaller than frontier models (e.g., Llama2 7B has 6.7B parameters). This is a strategic choice driven by the training-from-scratch paradigm: training a multi-billion-parameter model from random initialization on 500k demonstrations of a single task would be prohibitively expensive in compute and would likely overfit severely. The small model size keeps the experiments tractable while still demonstrating the APR mechanism's effectiveness. The paper later shows (Appendix A.3) that scaling to 600M parameters yields further improvements, confirming that the approach is not bottlenecked by model capacity at 228M.

Training from scratch vs. fine-tuning a pretrained model. The paper explicitly states: "Following existing work that proposes new learning algorithms for reasoning (Gandhi et al., 2024), we focus on training reasoning models from scratch. We leave experiments on adapting language models pre-trained on general web corpus for future work" (Section 3.3 footnote). This is an important scope limitation. Training from scratch on task-specific demonstrations means the model learns the Countdown reasoning domain as its primary linguistic knowledge. It does not need to learn general language capabilities (the traces are formulaic) but also cannot leverage any transfer from pretraining on diverse text. The Appendix A.4 experiment with fine-tuning a pretrained Qwen2.5 1.5B model on the same demonstration data shows strong APR performance (80.2% vs 83.2% for the from-scratch Llama2), suggesting the approach does transfer to pretrained models, but the main experiments focus on the from-scratch setting to isolate the effects of the threading mechanism from confounding factors of pretraining scale and quality.

Training data and batching. The supervised training uses 500,000 Countdown problems with APR-generated search traces. The models are trained for 19,000 steps at a batch size of 256, which the paper notes corresponds to "approximately 10 epochs" over the 500k dataset. Training uses 128 TPUv3 cores with a learning rate of $5 \times 10^{-5}$.

Length control via conditioning. A crucial training detail is how the model learns to control the amount of computation it uses. For the SoS+ baseline, this is straightforward: the model is conditioned on context-window size. Training samples are partitioned into bins of 512 tokens based on their trace length, and during training, the model receives the bin size as a conditioning signal. At inference, specifying a bin size (e.g., "generate a trace of approximately 1,024 tokens") controls the amount of computation. This follows the budget-conditioning approach from Chen et al. (2021).

For APR models, conditioning on context-window size is less appropriate because "child thread lengths can vary significantly" (Section 4, Experiment Setup). Instead, APR models are conditioned on the number of child threads initiated per parent thread, which "strongly correlates with the total number of tokens across all threads." This means:

• During training, each demonstration includes metadata about how many child threads were spawned by the parent in that trace.
• During inference, specifying a child thread count (e.g., "use 6 child threads") controls the degree of parallelization, which in turn controls the total token consumption.

This conditioning scheme is not explained in extensive detail in the main text, but its effect is visible in the experiments: Figure 4b shows APR performance curves for "Child Thread Cond=3," "Child Thread Cond=6," and "Child Thread Cond=10," indicating that the trained model can be prompted (or conditioned) to use approximately 3, 6, or 10 child threads, with higher thread counts consuming more total tokens but fitting within the same per-thread context window.

Why condition on child threads rather than total tokens? The paper does not explicitly state the reasoning, but the logic is consistent with APR's architecture: the total token consumption of APR is the sum of the parent thread length plus the sum of all child thread lengths. Since child threads are generated by the model and their lengths are not known in advance, conditioning directly on total tokens would require the model to predict and respect a cumulative budget across semi-independent generation streams — a much harder learning problem. Conditioning on the number of child threads is a coarser but more tractable control signal that correlates with total compute while respecting the parallelism structure.

---

Reinforcement Learning: End-to-End Policy Optimization with GRPO

After supervised training establishes a baseline APR policy, the paper applies reinforcement learning to optimize the model's parallelization strategy end-to-end. The RL stage is where the model learns when to spawn threads, how many threads to use, and what context to pass — decisions that were determined by the symbolic solver's random heuristic during supervised data generation but are now subject to optimization against the true task reward.

The RL problem formulation. The reasoning process is treated as a sequential decision-making problem:

• State: the sequence of tokens generated so far (the autoregressive context), combined with the task input (the Countdown problem).
• Actions: generating the next token from the model's vocabulary distribution. Importantly, spawn() calls are just token sequences — the RL optimization treats them as actions no different from generating arithmetic operations or state descriptions. The GRPO algorithm does not need to know that some token sequences trigger parallel thread execution; it only observes the downstream effects on task success.
• Reward: binary, 1 if the model's final output (the arithmetic expression) correctly evaluates to the target and uses each input number exactly once, 0 otherwise. There are no intermediate rewards for partial progress, interesting search behavior, or efficient context usage — the only signal is task success or failure.

Why GRPO? The paper uses Group Relative Policy Optimization (GRPO; Shao et al., 2024), a variant of Proximal Policy Optimization (PPO) designed for language model training. GRPO differs from standard PPO in how it estimates the advantage function. Instead of using a learned value function (critic) to compute advantages, GRPO samples a group of outputs for each input prompt, computes the mean reward within the group, and uses the deviation from the group mean as the advantage estimate. Specifically, for a prompt $q$, GRPO samples $G$ outputs $y_1, \ldots, y_G$ from the current policy $\pi_\theta$, receives rewards $r_1, \ldots, r_G$, and computes the advantage for output $i$ as:

$A_i = \frac{r_i - \mu_{\text{group}}}{\sigma_{\text{group}}}$

where $\mu_{\text{group}}$ and $\sigma_{\text{group}}$ are the mean and standard deviation of rewards within the group of $G$ outputs for this prompt.

What it computes: For each output in the $G$-sample group, the advantage measures how much better or worse that output's reward is compared to the average reward in the group, normalized by the group's reward standard deviation. Positive advantages reward outputs that outperform the group average; negative advantages penalize outputs that underperform the group average.

Why this form: The advantage normalization removes the need for a learned value function (which would be an additional large neural network to train and would introduce its own approximation errors). By using the group mean as a baseline, GRPO naturally handles the fact that different prompts have different difficulty levels — a 0-reward failure on a hard problem might still be "good" performance if most outputs in the group also fail, while a 0-reward failure on an easy problem where most outputs succeed would receive a strongly negative advantage. The standardization by $\sigma_{\text{group}}$ ensures that advantage magnitudes are comparable across prompts regardless of reward variance. This is particularly appropriate for APR because the Countdown task has binary rewards, so the group mean essentially estimates the policy's success probability on that prompt, and the advantage captures whether a particular output was a lucky draw or an unlucky one relative to that baseline.

Training hyperparameters. The RL training uses:

• 2 Nvidia GPUs (specific model not stated in main text, but the efficiency experiments use 8-GPU NVIDIA RTX A6000 servers).
• Training batch size of 64 prompts, with each prompt rolled out $G = 5$ times (group size 5).
• Temperature of 1.0 for rollout sampling during training (encouraging exploration).
• Learning rate of $1 \times 10^{-5}$.
• PPO clip ratio of 0.2.
• 150 total training steps, each consisting of 2 inner PPO optimization steps (so 300 parameter updates total).
• Gradient clipping with maximum norm of 1.0.
• Validation every 25 steps.

KL divergence regularization. A critical stability mechanism in RL for language models is preventing the policy from diverging too far from the supervised initialization. The GRPO framework includes a KL divergence penalty that constrains the updated policy $\pi_\theta$ to remain close to a reference policy $\pi_{\text{ref}}$ (typically the supervised model). The penalty coefficient is set to 0.01 for the SoS+ baseline and 0.001 for APR. The paper states that these values were chosen "for training stability" (Appendix A.2). The lower value for APR (0.001 vs. 0.01) suggests that APR benefits from allowing the policy to move further from its supervised initialization — likely because the supervised APR policy uses a random "promising node" heuristic, and RL needs more freedom to learn an effective spawning strategy.

What RL optimizes in practice. The paper's ablation study (Section 4.4) reveals a crucial insight about what RL actually changes in the APR policy:

• The number of child threads increases from an average of 6.1 to 8.2 after RL (34.4% relative increase).
• The average sequence length per request increases from 1,471 to 1,796 tokens (22.1% relative increase).
• When the model is conditioned to always use the maximum number of child threads (10 threads), RL provides essentially no accuracy improvement: accuracy goes from 83.2% (supervised only) to 83.3% (supervised + RL) under this fixed-compute condition.

This finding — that "the primary benefit of reinforcement learning comes from scaling test-time compute rather than improving decision quality within a fixed budget" (Section 4.4) — is a central result. It means that the supervised model already makes reasonably good decisions about which branches to explore; what RL adds is the meta-cognition to realize that when the problem is hard, spawning more parallel threads is worth the extra compute cost. The model learns to allocate more budget to difficult problems and less to easy ones.

The RL training loop specifics. While the paper does not describe the RL loop in exhaustive detail, the process can be reconstructed:

1. Rollout phase: For each of the 64 prompts in a batch, sample 5 outputs from the current policy at temperature 1.0 using SGLang for serving. Each output is a complete APR reasoning trace including any spawn() and join() operations.
2. Reward computation: For each output, extract the final arithmetic expression, evaluate it, and check whether it equals the target and uses all input numbers exactly once. Assign reward 1.0 (correct) or 0.0 (incorrect).
3. Advantage computation: For each of the 64 groups of 5 outputs, compute the group mean and standard deviation of rewards, and compute advantages using GRPO's formula.
4. Policy update: Compute the PPO-style clipped objective using the advantages, add the KL penalty, and take 2 optimization steps per batch (with gradient clipping).
5. Repeat for 150 batches.

The use of SGLang for rollout is important: during RL, the model generates complete APR traces (including child threads) as part of each rollout. This means that the rollouts themselves exercise the full multi-thread inference infrastructure — RL training is not just an abstract mathematical update; it requires actually running APR inference on the Countdown training problems at scale.

Evaluation protocol. During evaluation (as opposed to training rollouts), the paper uses greedy sampling (temperature 0.0) unless otherwise stated, because "it achieves the best performance for both SoS+ and APR compared to other evaluation temperatures" (Appendix A.2). This is an important practical note: while stochastic sampling is essential for exploration during training, deterministic greedy decoding produces the highest accuracy at test time, suggesting that the learned policy has converged to a stable strategy that doesn't benefit from further stochasticity.

---

Inference-Time Execution: How APR Runs on Hardware

The final component of the technical approach is the deployment architecture — how a trained APR model actually executes on GPU hardware to achieve the latency benefits claimed in the paper. This section bridges the conceptual spawn()/join() abstraction and the physical reality of autoregressive generation on parallel accelerators.

SGLang as the serving backbone. The paper builds on SGLang (Zheng et al., 2024), a high-performance language model serving framework with two features critical for APR:

1. Continuous batching: SGLang can batch multiple inference requests together, even if they arrive at different times, and process them concurrently on the same GPU. This is essential for child thread execution: when the parent thread spawns $k$ children, all $k$ appear as simultaneous new requests that can be batched together, maximizing GPU utilization.

2. Radix attention (prefix caching): SGLang can identify shared prefixes across requests and cache their key-value representations, avoiding redundant computation. For APR, this is highly beneficial: all child threads spawned from the same parent share the Countdown problem statement and potentially the parent's reasoning steps up to the spawn point as a common prefix. SGLang automatically detects these shared prefixes and reuses the cached attention states, so the first tokens of each child thread don't need to be recomputed from scratch.

How the spawn-join lifecycle maps to serving operations:

1. Parent thread generation: The parent's autoregressive generation proceeds normally on one GPU (or one slice of a GPU). SGLang accumulates the generated tokens in the standard way.

2. Spawn detection: When the parent generates a token sequence matching the spawn() pattern, the inference infrastructure (implemented as custom logic on top of SGLang) parses the output to extract the child thread messages. The parent thread's generation is paused at this point — its KV cache is preserved, but no further parent tokens are generated until the children return.

3. Child thread launch: For each extracted msg, a new inference request is created with:

   • The msg string as its prompt (or, if prefix caching applies, the shared prefix tokens plus the unique suffix).
   • The same model checkpoint and sampling parameters as the parent.
   • The same context window limit (4,096 tokens). These requests are submitted to SGLang's batching system and executed concurrently. The paper's latency experiments dedicate one GPU to the main thread and distribute child threads across the remaining GPUs (in an 8-GPU server, 7 GPUs for children).

4. Child thread execution: Each child generates tokens independently until it produces a join(msg) sequence. The child's output is parsed to extract the msg content. The child's generation is then terminated, and its KV cache is freed.

5. Join aggregation: The infrastructure collects join() messages from all children. Once all children have terminated, it concatenates the msg contents and injects them into the parent thread's context at the point after the spawn() call. The parent thread's KV cache is extended to include these join messages.

6. Parent resumption: The parent thread resumes generation, now conditioned on the child outcomes. It can spawn additional children, and the cycle repeats.

Latency model: sequential tokens vs. wall-clock time. The paper introduces a critical distinction between two latency metrics:

• Sequential tokens: The maximum number of causally dependent tokens that must be generated one after another. For APR, this is the length of the longest non-parallelizable chain: if the parent generates $P$ tokens, then spawns children that generate $C_1, C_2, \ldots, C_k$ tokens in parallel, then resumes for another $P'$ tokens, the sequential token count is $P + \max(C_1, \ldots, C_k) + P'$ — the length of the critical path through the token dependency graph.

• Wall-clock latency: The actual elapsed time from request submission to final output. This depends on sequential tokens plus hardware-specific factors: GPU compute throughput, batching efficiency, memory bandwidth, and load balancing across GPUs.

The paper's efficiency experiments (Figure 6) show that APR achieves approximately 2,200 sequential tokens at its highest-performing configuration, compared to nearly 3,000 for SoS+ at lower accuracy. This translates to roughly 5,000ms wall-clock latency for APR versus a similarly timed SoS+ configuration that achieves only 57.3% accuracy compared to APR's 75.2% — an 18 percentage point advantage.

Hardware configuration for latency experiments. The efficiency measurements use an 8-GPU NVIDIA RTX A6000 server with the following allocation:

• 1 GPU dedicated to the main (parent) inference thread.
• 7 GPUs allocated for executing child threads in parallel.

The paper notes (Appendix A.10) that with up to 10 child threads, "some GPUs may end up handling multiple child threads, leading to uneven workloads and increased computational load on certain devices." This suggests that the 7-GPU child pool can become a bottleneck when the model spawns many threads — some GPUs handle 2 threads while others handle 1, and the overall latency is gated by the slowest GPU's completion time. The paper identifies improved load balancing as a direction for further performance optimization.

Prefix caching benefits quantification. The paper states that the "parent-child threading mechanism creates natural opportunities for prefix sharing, which further reduces the computational overhead of APR parallelization" (Section 2, Related Work). While no quantitative ablation of prefix caching benefits is provided, the mechanism is clear: if the parent writes "Moving to Node #0 Current State: 27:[22, 26, 31, 53], Operations: []" and then spawns two children that both start with this same context, SGLang's radix attention cache computes the KV representations for these shared tokens once and reuses them for both children. Without prefix caching, each child would redundantly recompute these attention states, negating some of the parallelism benefits.

Temperature and sampling during inference. The paper evaluates at multiple temperatures (0.0, 0.1, 0.5, 1.0) and reports that Table 4 shows "our results—and their relative advantages—remain consistent across temperatures, both before and after RL" (Appendix A.9). Greedy decoding (temperature 0.0) produces the highest absolute accuracy for both APR (83.4% post-RL) and SoS+ (60.0% post-RL). Higher temperatures reduce accuracy for both methods but preserve the relative gap (APR outperforms SoS+ by 20+ percentage points across all temperatures post-RL). This consistency suggests that the learned spawning strategy is robust to sampling stochasticity — even when individual reasoning steps become noisier at higher temperatures, the meta-decision of whether and how to parallelize remains effective.

---

Summary of Design Choices and Their Justifications

• Parent-child threading over fixed search structures: Allows the search algorithm to be learned rather than hand-designed, enabling problem-adaptive allocation and continuous improvement through RL.
• Selective join() summarization (returning only solutions, not full traces): Directly addresses the context window bottleneck by preventing child search debris from consuming the parent's limited context tokens.
• Independent child contexts (no shared reasoning history): Prevents information leakage that would cause the context window problem to compound across threads; each child operates in a clean information environment defined by its assigned subtask.
• Random "promising node" heuristic (10% chance) in supervised demonstrations: Teaches the mechanical syntax of spawning without entrenching suboptimal priors about when to spawn, leaving the strategy optimization to RL.
• Conditioning on child thread count rather than total tokens: A tractable control signal that naturally aligns with the parallelism structure while avoiding the complexity of predicting cumulative multi-thread token consumption.
• GRPO over standard PPO with value function: Eliminates the need for a separate critic network (reducing memory and training complexity) while the group-based advantage estimation naturally handles varying prompt difficulty.
• Training from scratch on 500k demonstrations: Isolates the effect of the threading mechanism by avoiding confounding factors from pretraining, though Appendix A.4 shows the approach transfers to pretrained models.
• 228M-parameter model size: Balances experimental tractability with sufficient capacity; scaling to 600M parameters (Appendix A.3) confirms that performance improves with model size, indicating the approach is not capacity-limited.
• Dedicating 1 GPU to parent, 7 GPUs to children in deployment: Reflects the asymmetry of APR's computation profile — the parent thread is a serial bottleneck (only one copy can run at a time), while children are embarrassingly parallel and can saturate available hardware.

4. Key Insights and Innovations

Innovation 1: Learned Parallel Decomposition as a Generalization of Search Structure Design

The field's dominant approach to structuring inference-time reasoning has been for the developer to design the search algorithm — imposing BFS, DFS, beam search, or Tree-of-Thought architectures through prompting or external orchestration (Yao et al., 2023; Besta et al., 2024). These hand-designed structures are necessarily fixed: the developer chooses BFS or DFS before seeing any specific problem, and that choice is applied uniformly regardless of whether particular problems would benefit from different strategies.

APR makes a fundamentally different architectural choice: the model learns its own parallel decomposition strategy through end-to-end training, using a minimal interface of two coordination primitives — spawn() and join() — rather than a pre-specified search algorithm. This is not an incremental improvement on Tree-of-Thought or multi-agent debate; it is a shift from algorithmic design to meta-algorithmic learning. The developer does not specify "use BFS with branching factor 3 when the heuristic exceeds threshold $\tau$" — instead, the model discovers through RL that spawning many threads at states with high branching potential yields better task success, without ever being told what a "branching factor" or "heuristic threshold" is.

The significance of this framing extends beyond Countdown. If models can learn search strategies from reward alone, then the search of hand-designed reasoning structures — Tree-of-Thought, Graph-of-Thought, multi-agent protocols — can be understood as special cases that emerge from optimization rather than being externally imposed. The paper explicitly makes this conceptual claim: "In theory, our framework could result in language models that implement the same search structures as existing approaches, such as Tree-of-Thought, without explicit prompting or hand-designed orchestration of language model calls" (Appendix A.1). This shifts the research question from "what is the best search structure?" to "what interface primitives enable models to discover effective search structures?" — a higher-order, more general question.

The empirical evidence that this learned decomposition is qualitatively different from hand-designed baselines comes from Figure 4: APR with learned spawning substantially outperforms SoS+ with Best-of-N sampling at matched total token budgets, and this gap widens as compute increases (80.1% vs. 66.6% at 20k tokens). The gap cannot be attributed to simply doing more search — Best-of-N is doing more search — but rather to the coordinated nature of the search, where child threads execute distinct subtasks rather than redundant independent attempts.

Innovation 2: Reinforcement Learning as a Mechanism for Discovering Compute Allocation Strategies

The paper's RL results contain a specific and revealing diagnostic finding: RL primarily improves performance by teaching the model to use more parallel compute, not by improving reasoning quality per token. When the model is conditioned to always use the maximum 10 child threads, RL provides essentially zero accuracy improvement (83.2% → 83.3%, Section 4.4). The gains come entirely from the model learning when to allocate more threads — it increases average child thread count from 6.1 to 8.2 (a 34.4% relative increase) and total tokens from 1,471 to 1,796 (a 22.1% increase).

This finding reframes what RL contributes to reasoning. Prior work on RL for reasoning (DeepSeek-R1, STaR, ReST$^{EM}$) typically emphasizes that RL improves the quality of reasoning — the model learns to avoid mistakes, verify its work, and discover more effective reasoning strategies. APR's result suggests a complementary mechanism: RL can optimize the quantity and structure of inference-time resource allocation, independent of per-step reasoning quality. The model learns that broader search (more child threads) is more valuable than deeper search (longer sequential traces within each thread), a meta-strategic insight that emerges purely from reward optimization without any explicit instruction about the geometry of search.

This is important for two reasons. First, it suggests that compute allocation strategy itself is a learnable skill — one that may be as important as reasoning accuracy for overall task performance, yet has been largely overlooked because existing methods don't give models control over allocation. Second, it provides a diagnostic tool: if RL on a reasoning task yields large accuracy gains, this ablation (fixing the compute budget and checking whether gains persist) can distinguish between "the model learned to reason better" and "the model learned to allocate more compute" — two very different mechanisms that are observationally confounded in standard RL evaluations.

The connection to Snell et al. (2025) is worth noting. That work showed that optimal test-time compute allocation varies with problem difficulty — easy problems benefit from different strategies than hard ones. APR's RL result extends this insight: the model learns to vary its allocation per-problem without explicit difficulty estimation, because the reward signal naturally encodes problem hardness (hard problems have lower reward probability, so expending more compute on them has higher expected marginal benefit when it succeeds).

Innovation 3: The Context Window as an Allocatable Resource Rather Than a Fixed Constraint

Prior work treats the context window as a hard limit: so many tokens fit, no more. Serialized search methods (SoS, DeepSeek-R1) must fit their entire reasoning trace within this window, creating a direct tradeoff between search breadth and feasibility — complex search traces that exceed the window are simply impossible to execute. Parallel methods like self-consistency circumvent this by giving each trace its own window, but they introduce the coordination problem described earlier.

APR introduces a fragmented context model where the total effective context scales with the number of parallel threads, but each thread operates within its own bounded window. The parent thread maintains a concise representation of the global search state (target problem, outcomes of completed sub-searches), while child threads execute search subtrees whose intermediate debris is discarded via selective join() summarization. This means the total information processed by the system exceeds any single context window, but the attention mechanism in each thread only needs to operate over a manageable subset of that information.

This is significant as a systems-level insight about attention as a bottleneck resource. The quadratic cost of attention with respect to sequence length means that simply making context windows larger is not a scalable solution — even if technical advances push windows to 1M tokens, the computational cost per token grows with attention span, and the model's ability to attend to relevant information degrades as irrelevant information accumulates. APR's fragmentation approach suggests an alternative scaling path: rather than one enormous context window, use many moderate-sized windows with a communication protocol that extracts and transmits only relevant summaries.

The evidence comes from Figure 4b: APR with 10 child threads achieves approximately 60% cumulative accuracy at a 4k token context window, while SoS+ achieves approximately 40% at the same window. Yet both methods are consuming roughly similar total tokens — the difference is that APR distributes those tokens across multiple independent windows, avoiding the degradation that occurs when a single window becomes crowded with failed search attempts. The "cumulative accuracy" metric is itself an innovation in evaluation: it measures how often the model produces a correct answer within the window limit, explicitly penalizing the case where a correct solution exists but is buried beyond the window cutoff. This metric directly captures the context window bottleneck that serialized methods face.

Innovation 4: A Principled Interface for Model-Controlled Inference Parallelism

The spawn() and join() interface is deceptively simple — it adds only two operations to the model's generation vocabulary — but it represents a clean separation between the model's reasoning policy and the execution infrastructure. The model does not need to know about GPUs, batch scheduling, or prefix caching; it generates token sequences that the infrastructure interprets as parallelization commands. Conversely, the infrastructure does not need to understand the semantics of the Countdown task or the structure of search; it simply executes threads when it encounters spawn() tokens and aggregates results at join() tokens.

This separation matters because it enables each component to be optimized independently. The model can learn increasingly sophisticated parallelization strategies through RL without any changes to the serving infrastructure. The infrastructure can implement increasingly efficient parallel execution (better load balancing, smarter prefix caching, dynamic batching) without retraining the model. This is not a theoretical nicety — it is a practical design principle that contrasts with approaches like Tree-of-Thought, where the search algorithm, the model calls, and the execution schedule are tightly coupled in developer-written orchestration code.

The interface's generality is also notable. While demonstrated on Countdown, spawn() and join() are not task-specific. They could encode any form of parallel decomposition: exploring alternative code implementations, independently verifying factual claims, evaluating different plan branches, or even recursive self-play where child threads generate training data for the parent. The paper does not explore these extensions, but the interface design makes them natural.

The empirical demonstration of the interface's effectiveness is most visible in the latency experiments (Figure 6, right): at approximately 5,000ms wall-clock time, APR achieves 75.2% accuracy to SoS+'s 57.3% — an 18 percentage point gap. This is not because APR's model is "smarter" in a per-token sense, but because the spawn-join interface allows the model to express parallelism that the serving infrastructure can exploit, reducing the critical path length (sequential tokens) from ~3,000 to ~2,200 (Figure 6, left). This is a systems-algorithm co-design insight: reasoning performance is as much about how computation is scheduled as about what computation is performed.

5. Experimental Analysis

Evaluation Methodology

• Dataset. The Countdown arithmetic reasoning task (Yao et al., 2023; Gandhi et al., 2024; Pan et al., 2025), where a model must map from a set of four input numbers to an arithmetic expression that uses each number exactly once and evaluates to a given target (e.g., input {1, 4, 6, 8} with target 10 yields (8-6)×(4+1)=10). The paper does not specify the exact test set size, but the training set consists of 500k Countdown problems with corresponding search traces generated by symbolic solvers (Section 4, Experiment Setup). The experiments also extend to a five-number variant with a search space approximately 40× larger for the extended context window experiments (Appendix A.5).

• Base model(s). A decoder-only language model following the Llama2 architecture (Team, 2023) with 228M non-embedding parameters (293M total parameters), trained from scratch on Countdown reasoning traces — meaning it has no exposure to general web text and learns both the reasoning strategy and the linguistic format of search traces from the task-specific demonstrations. The model uses 18 hidden layers, a hidden dimension of 1024, 16 attention heads, and a 4,096-token context window. The paper also reports results with a 600M-parameter variant (Appendix A.3) and with fine-tuning a pretrained Qwen2.5 1.5B model (Appendix A.4), though the main experiments use the 228M from-scratch model to isolate the threading mechanism's effects from pretraining confounds.

• Metrics. Three categories of metrics are tracked. Accuracy is the percentage of Countdown test problems for which the model produces a correct arithmetic expression — one that evaluates to the target and uses each input number exactly once. Compute efficiency is measured by total tokens generated during reasoning, which for APR is the sum across all parent and child threads, while for SoS+ it is the length of the single serialized search trace. Latency is evaluated through two complementary measures: sequential tokens (the maximum number of causally dependent tokens that must be processed serially — i.e., the length of the critical path through the token dependency graph, where parallel sub-thread generation considers only the longest token sequence among independently processable threads) and real-world wall-clock time in milliseconds measured on an 8-GPU NVIDIA RTX A6000 server. The paper also introduces cumulative accuracy in the context window experiments (Figure 4b): at each window size limit, only outputs whose length falls within that limit count as correct, explicitly penalizing traces that extend beyond the budgeted context.

• Baselines. The primary serialized baseline is SoS+ , an improved version of Stream of Search (Gandhi et al., 2024) that uses hybrid BFS-DFS search traces without spawn()/join() operations. The parallel baseline is cons@n (self-consistency), implemented by independently sampling n reasoning traces from SoS+ at temperature 1.0, discarding outputs that fail to produce a valid solution, and applying majority voting over the final search paths from the remaining outputs. Additionally, pass@n is reported as an upper bound — the rate at which at least one of n independent SoS+ samples produces a correct solution, representing the best-case performance achievable through simple ensemble-based parallel inference without coordination. The paper also compares against the original SoS method (Table 2, Appendix A.7), showing that SoS+ consistently outperforms it (e.g., 57.3% vs. 49.5% at temperature 0.0).

• Generation budget / compute accounting. Total tokens generated serves as the universal unit of test-time compute. For SoS+, this is simply the length of the serialized search trace in tokens. For APR, it is the sum of tokens generated across all threads: the parent thread's tokens plus the tokens from every spawned child thread, with the spawn() and join() orchestration tokens themselves included in the count. For scaling experiments (Figure 4a), compute is controlled by varying the number of conditioned child threads for APR (from 0 to 10) and by varying the sample size n for SoS+ cons@n and pass@n (from 1 to 8). The conditioning mechanism for APR uses child thread count rather than total tokens because "child thread lengths can vary significantly" (Section 4, Experiment Setup), and thread count "strongly correlates with the total number of tokens across all threads." For context window constrained experiments (Figure 4b), compute is measured by the per-thread context window size, and cumulative accuracy counts only traces that fit within that limit.

• Cross-validation / statistical protocol. The paper does not employ explicit cross-validation over the test set. Instead, it conditions models during training on budget levels (context window sizes for SoS+, child thread counts for APR) and evaluates at each conditioned budget level at test time using greedy decoding (temperature 0.0) for primary results, since greedy "achieves the best performance for both SoS+ and APR" (Appendix A.2). For scaling experiments with cons@n and pass@n, sampling is performed with temperature 1.0, with n samples drawn independently. The RL training loop performs validation every 25 steps during the 150-step training run, with early stopping implicit in the fixed step count. For the five-number Countdown experiments (Appendix A.5), the extended context windows go up to 8k tokens, though the base model was trained on a 4,096-token context window, suggesting the model generalizes to longer sequences at test time through the parallelization mechanism.

Main Quantitative Results

Scaling with Increased Compute Budget (Figure 4a and Figure 10)

The headline result is that APR achieves 80.1% accuracy at approximately 20k total tokens compared to 66.6% for SoS+ cons@7 at the same budget — a 13.5 percentage point absolute improvement. This is the core scaling claim: APR's coordinated parallel decomposition yields substantially better returns on additional test-time compute than either serial search (SoS+) or independent parallel sampling (cons@n).

The scaling behavior reveals an important regime-dependent pattern. At low compute budgets (below approximately 4k total tokens, corresponding to pass@1 or single-sample generation), APR actually underperforms SoS+ — the paper attributes this to "parallelism overhead," where some generated tokens are consumed by thread orchestration (spawn() and join() syntax) rather than directly contributing to search. However, as the compute budget increases beyond 4k tokens, APR crosses above SoS+ pass@n and cons@n, and the gap widens monotonically with additional compute. At the highest measured budget of approximately 24k tokens, APR achieves 80.1% accuracy while SoS+ pass@8 reaches only 68.4% — an 11.7 percentage point gap. Notably, APR matches the SoS+ pass@8 performance while consuming 57.4% less compute, meaning it achieves the same accuracy with fewer than half the total tokens.

The paper also reports that these scaling advantages are robust to sampling temperature (Figure 10, Appendix A.9). Across temperatures 0.1, 0.5, and 1.0, APR consistently outperforms both SoS+ pass@n and SoS+ cons@n at matched total token budgets, though absolute accuracy decreases at higher temperatures for all methods. For instance, at temperature 1.0 and approximately 20k tokens, APR achieves roughly 80.1% (at higher thread counts, the curve appears to reach its peak around 20k tokens and remains stable), while SoS+ cons@7 reaches approximately 66.6% and SoS+ pass@8 reaches approximately 68.4%. The relative ordering (APR > pass@n > cons@n) is preserved across all temperature settings.

Performance Under Context Window Constraints (Figure 4b)

APR achieves 83.4% cumulative accuracy at a 4,096-token context window with the post-RL model, while SoS+ with 4,096-token context conditioning reaches only 60.0% — a 23.4 percentage point gap. This result directly demonstrates APR's ability to circumvent the serial context window bottleneck.

The cumulative accuracy metric is critical here: at each window size threshold, it counts only those problem instances where the model's output (or, for APR, the combined output across threads that fits within the per-thread window) produces a correct answer whose trace length does not exceed the threshold. This means that SoS+ traces that would have found a correct solution if given a larger window are counted as failures — explicitly measuring the degradation from context window exhaustion.

The per-thread conditioning results for APR show a clear tradeoff between parallelism and accuracy within fixed windows. With 3 child threads conditioned, APR already surpasses SoS+ at every window size from 1,024 to 4,096 tokens (e.g., approximately 60% vs. 40% cumulative accuracy at the 4k mark). With 6 child threads, the gap widens to roughly 10 percentage points. With 10 child threads, APR achieves approximately 70–80% cumulative accuracy at 4k tokens — roughly double SoS+'s performance at the same window size. The SoS+ model conditioned on 1,024 tokens shows the expected behavior: its accuracy curve plateaus as the window constraint tightens, since it learns to produce shorter, less thorough traces that are less likely to solve harder problems.

This experiment also reveals that SoS+ performance is fundamentally limited by the context window, not by the model's reasoning capability. Even the SoS+ model conditioned on the full 4,096-token context achieves only 60.0%, while APR with 10 threads — each also limited to 4,096 tokens, but processing different search subtrees — achieves 83.4%. The additional 23.4 percentage points come from the parallel distribution of the search tree across multiple independent context windows, not from any improvement in per-token reasoning quality.

Efficiency: Sequential Tokens and Wall-Clock Latency (Figure 6)

At approximately 5,000ms wall-clock latency, APR reaches 75.2% accuracy versus 57.3% for SoS+ — an 18 percentage point advantage at equal real-time cost. This is the result that translates the abstract "parallelization" concept into practical deployment benefits.

The sequential token analysis (Figure 6, left) explains why this latency gap exists. APR's sequential token count — the length of the longest non-parallelizable chain (parent generation + longest child thread + parent continuation) — plateaus around 2,200 tokens even as accuracy continues to improve. In contrast, SoS+ must generate nearly 3,000 sequential tokens to achieve its maximum accuracy of approximately 57.3%, and further sequential token increases produce minimal additional accuracy gains. This means APR's critical path through the token dependency graph is substantially shorter than SoS+'s, despite APR processing more total tokens — those additional tokens are consumed in parallel child threads that don't extend the sequential dependency chain.

The wall-clock latency results (Figure 6, right) confirm that the sequential token advantage translates into real speedups on hardware. Both curves show the expected accuracy-latency tradeoff (more compute = higher latency = higher accuracy), but APR's curve is uniformly above and to the left of SoS+'s — it achieves higher accuracy at every latency point, and reaches any given accuracy level with lower latency. The specific hardware configuration (1 GPU for the parent thread, 7 GPUs for child threads on an 8-GPU NVIDIA RTX A6000 server) means that APR's parallelism is actually exploited by the available hardware, not merely theoretical.

The paper also notes (Appendix A.10) that there is a "slight mismatch" between sequential tokens and wall-clock time due to hardware constraints: with up to 10 child threads but only 7 GPUs available for child execution, some GPUs handle multiple threads, creating uneven workloads where the slowest GPU gates overall completion time. This suggests the reported latencies represent a conservative estimate — additional GPUs or better load balancing could further widen the gap in APR's favor.

Effect of Reinforcement Learning on Performance (Figure 5 and Figure 7)

RL improves APR accuracy from 75.5% to 83.4% (a 7.9 percentage point gain), while the same RL procedure applied to SoS+ improves accuracy from 57.3% to 60.0% (only a 2.7 percentage point gain). The asymmetry in RL benefit — APR gains nearly 3× more from RL than SoS+ — is a key finding about the interaction between parallelization capability and policy optimization.

The mechanism behind APR's larger RL gain is revealed by the behavioral statistics (Figure 5, right panels). After RL:

• Average child thread count increases from 6.1 to 8.2 (34.4% relative increase), indicating the model learns to spawn more parallel threads.
• Average sequence length increases from 1,471 to 1,796 tokens (22.1% relative increase), indicating some additional serial computation as well.
• Total tokens increase from approximately 10,964 to 16,720 (a 52.5% relative increase), reflecting the combined effect of more threads and longer traces.

For SoS+, RL increases total tokens by only 20.9% — the serialized model cannot parallelize its additional compute, so it must either lengthen its single trace (which quickly hits the context window limit) or stop. This structural constraint on SoS+ is precisely what APR's threading mechanism overcomes: RL can allocate additional compute that actually gets used (in parallel threads) rather than hitting the context ceiling.

The disentanglement experiment (Section 4.4, Figure 7 right bars labeled "APR (#Child Cond.)") is the critical diagnostic. When the model is conditioned to always use the maximum number of child threads (10 threads), both before and after RL, accuracy remains essentially flat: 83.2% → 83.3%. Under this fixed-compute constraint, RL provides negligible improvement. This demonstrates that the primary benefit of RL in these experiments is test-time compute scaling — the model learns to allocate more compute to problems that benefit from it — rather than improving per-token reasoning quality or search decision-making within a fixed budget. The paper states this finding explicitly: "the primary benefit of reinforcement learning comes from scaling test-time compute rather than improving decision quality within a fixed budget" (Section 4.4).

The consistency of this pattern across temperatures (Table 4, Appendix A.9) strengthens the interpretation. Post-RL, APR accuracy at temperature 0.0 is 83.4%, at 0.1 is 82.9%, at 0.5 is 81.3%, and at 1.0 is 76.4%. The corresponding pre-RL numbers are 75.5%, 75.9%, 74.9%, and 67.8%. The RL gain is roughly 7–8 percentage points at low temperatures (where greedy or near-greedy decoding is used) and about 8.6 points at temperature 1.0, suggesting the learned spawning strategy generalizes across sampling stochasticity levels.

Scaling to Larger Problems and Models (Appendices A.3, A.4, A.5)

Three additional experiments extend the main results to assess generalizability:

Five-number Countdown (Appendix A.5, Figure 9). On the harder five-number variant with a search space approximately 40× larger, APR with 10 child threads achieves roughly 30–35% cumulative accuracy at 8,192 token context windows, compared to roughly 20–25% for SoS+ with 8,192 token conditioning. The gap emerges only beyond approximately 3,500 token windows — below that, both methods perform similarly, likely because the search space is too large for either approach to make meaningful progress within tight context constraints. Above 3,500 tokens, APR's ability to parallelize exploration yields diverging curves, with APR achieving gains of 7% and 11% at the 8k-token budget. This demonstrates that APR's advantage is not specific to the four-number problem size — it scales to larger search spaces where parallel exploration becomes even more valuable.

Larger model (Appendix A.3, Figure 8). Scaling from 228M to 600M parameters, APR performance improves at every compute level while maintaining the same advantage over SoS+. At 20k total tokens, the 600M APR model achieves roughly 80% accuracy compared to roughly 76% for the 228M version, while 600M SoS+ pass@n reaches only approximately 72%. The gap between APR and SoS+ widens with model size (600M APR roughly 80% vs. 600M SoS+ pass@n roughly 72%, a larger gap than 228M APR at approximately 76% vs. 228M SoS+ pass@n at approximately 68%), suggesting that larger models can exploit parallelization more effectively — perhaps because they have greater capacity to learn the meta-strategy of when and how to spawn threads.

Pretrained model fine-tuning (Appendix A.4, Table 1). Fine-tuning a pretrained Qwen2.5 1.5B model on the same APR demonstrations yields 80.2% accuracy, compared to 83.2% for the from-scratch 228M Llama2. The SoS+ baseline on Qwen achieves 57.5%, comparable to the Llama2 SoS+'s 57.4%. The key takeaway is that APR's advantage transfers to pretrained models of different families and scales — the 22.7 percentage point gap between APR and SoS+ on Qwen (80.2% vs. 57.5%) is similar in magnitude to the gap on from-scratch Llama2 (83.2% vs. 57.4%). This evidence helps address the concern that APR's benefits are an artifact of training tiny models from scratch on narrow task data — the mechanism generalizes to models that have seen diverse text during pretraining.

Ablation Studies and Robustness Checks

• SoS vs. SoS+ baseline quality (Table 2, Appendix A.7): SoS+ consistently outperforms the original SoS method across all temperature settings. At temperature 0.0, SoS+ achieves 57.3% vs. SoS's 49.5% — a 7.8 percentage point improvement from the hybrid BFS-DFS search strategy in training demonstrations. The gap persists at higher temperatures (57.1% vs. 49.6% at 0.1; 52.0% vs. 47.1% at 0.5), confirming that the SoS+ improvements are not specific to greedy decoding. This ablation validates that the strong baseline against which APR is compared is genuinely the best available serialized approach, making APR's gains over SoS+ more meaningful.

• Supervised training data quality for SoS+ (Table 3, Appendix A.8): Attempts to improve the SoS+ baseline through better demonstration quality reveal that SoS+ is fundamentally bottlenecked by the context window, not by demonstration quality. Increasing the beam size during demonstration generation from 5 to 15 improves symbolic solver accuracy but leads to longer trajectories that exceed the model's 4,096-token context length, resulting in degraded performance (50.9% vs. 57.3% at temperature 0.0). Rejection sampling — curating 500k high-quality demonstrations that are both correct and context-bounded — improves performance at temperature 1.0 (54.5% vs. 48.1%) but has minimal effect at temperature 0.0 (56.5% vs. 57.3%). This negative result strengthens the paper's core argument: you cannot overcome the serialization bottleneck by simply providing better training data — the structural limitation of fitting entire search traces into a single context window is the binding constraint.

• Temperature robustness (Table 4 and Figure 10, Appendices A.9): Both APR and SoS+ show the expected downward trend in accuracy as temperature increases from 0.0 to 1.0, but the relative advantage of APR is preserved across all temperatures. Post-RL APR accuracy: 83.4% (T=0.0), 82.9% (T=0.1), 81.3% (T=0.5), 76.4% (T=1.0). Post-RL SoS+ accuracy: 60.0% (T=0.0), 59.3% (T=0.1), 59.1% (T=0.5), 58.1% (T=1.0). The gap narrows slightly at higher temperatures (23.4 points at T=0.0 vs. 18.3 at T=1.0), but remains large. Notably, SoS+ shows surprising robustness to temperature — accuracy drops only from 60.0% to 58.1% across the full range — while APR drops more steeply. The paper does not discuss this differential temperature sensitivity; one possible explanation is that APR's threading decisions introduce additional variance at higher temperatures (noisier decisions about when to spawn), whereas SoS+'s search trace is a single path whose quality is bounded by the context window regardless of temperature.

• Conditioning ablation for RL disentanglement (Section 4.4, Figure 7 right bars): As discussed in the main results, conditioning APR to always use 10 child threads (the maximum) eliminates the RL performance gain — accuracy goes from 83.2% (supervised, conditioned on 10 threads) to 83.3% (RL, conditioned on 10 threads). The corresponding total token counts also remain nearly identical (approximately 19,895 vs. 22,265). This is the cleanest evidence that RL's benefit operates through the mechanism of increased compute allocation rather than improved per-token reasoning. It also implies that the supervised model's spawning decisions are already near-optimal when constrained to use a fixed number of threads; RL's value lies in determining the optimal thread count for each problem instance.

• Supervised training data source for APR (implied, but not isolated as a standalone ablation): The paper trains APR on demonstrations from the APR symbolic solver and SoS+ on demonstrations from the SoS+ symbolic solver. An ablation training APR on SoS+ traces (or SoS+ on APR traces) is not reported, making it impossible to fully disentangle whether APR's advantage comes from the hybrid search strategy in the training data, the threading mechanism, or their interaction. The 10% random spawning heuristic in the APR solver's demonstrations means that the initial supervised APR policy learns spawning from noisy examples — it sees spawning at both genuinely promising and arbitrary states. The fact that RL improves from this initialization (75.5% → 83.4%) despite the noisy demonstrations suggests that the spawning interface is learnable even with imperfect supervised data, but the specific contribution of demonstration quality to final performance is not quantified.

• Beam size and rejection sampling for APR (not performed): The paper ablates beam size and rejection sampling for SoS+ (Appendix A.8) but not for APR. An analogous experiment for APR — varying the beam size in the APR symbolic solver or applying rejection sampling to filter APR demonstrations — would reveal whether APR's performance is similarly sensitive to supervised data quality or whether the threading mechanism makes it more robust to noisy or suboptimal demonstrations. This missing ablation limits understanding of how much supervised data engineering effort is needed to bootstrap APR effectively.

Critical Assessment

The experiments demonstrate several things clearly, but several central claims require qualification about what was actually tested versus what was inferred.

Claim: APR achieves higher performance within the same context window (83.4% vs. 60.0% at 4k context). This claim is directly supported by Figure 4b and Table 4. The cumulative accuracy metric properly accounts for the context window constraint — it counts only successful traces that fit within the specified limit. The 23.4 percentage point gap is large and robust across multiple child thread conditioning levels. However, the context window comparison treats APR's per-thread window and SoS+'s window as equivalent — they are both 4,096 tokens, but APR distributes its total computation across (parent window + k child windows). The "83.4% within 4k context" figure means that each individual thread stays within 4k tokens, but the total context consumed across all threads is (1 + k) × 4k tokens. If the claim is interpreted as "APR achieves 83.4% accuracy while consuming 4k tokens of total context," that would be misleading — the total context across all threads is substantially larger. What the experiment validly shows is that APR's per-thread context constraint does not bottleneck its performance the way SoS+'s single-thread constraint does. The phrasing "within the same context window" in the abstract is slightly ambiguous on this point — it means "within the same per-thread context window size," not "within the same total context budget."

Claim: APR exhibits superior scalability with increased computation (80.1% vs. 66.6% at 20k total tokens). This is directly supported by Figure 4a. The total token accounting is fair — it sums tokens across all threads for APR and across all samples for cons@n/pass@n. The 13.5 percentage point gap is substantial, and the scaling curves show diverging trends (APR continuing to improve beyond 20k tokens while SoS+ cons@n appears to be plateauing). However, the cons@n baseline at n=7 represents only majority voting over 7 independent samples — it does not represent the best possible self-consistency performance (larger n might improve further). Similarly, pass@n at n=8 represents the best-of-8 upper bound, which is a ceiling on what independent parallel sampling can achieve at this token budget. APR's 80.1% exceeds pass@8's 68.4%, demonstrating that coordinated parallelism outperforms the upper bound of independent parallelism — this is a stronger claim than merely beating cons@n, since it shows coordination provides benefits beyond what even perfect answer selection from independent samples could achieve.

Claim: APR achieves improved accuracy at equivalent latency (75.2% vs. 57.3% at approximately 5,000ms). Supported by Figure 6 (right) with a specific hardware configuration. The 18 percentage point gap at matched wall-clock time is practically meaningful. However, the latency comparison has several qualifiers. First, it uses an 8-GPU server with specific GPU allocation (1 GPU for parent, 7 for children) — this hardware configuration matters because APR's parallelism only translates to latency reduction if the hardware can actually execute child threads concurrently. On a single GPU, APR would provide no latency benefit (all threads would serialize). Second, the load-balancing inefficiency noted in Appendix A.10 — with up to 10 child threads but only 7 child GPUs, some GPUs handle multiple threads — means the measured latency is conservative for APR. Third, the SoS+ baseline in the latency comparison does not use batching across multiple independent problems — it generates traces one at a time, measuring per-problem latency. In a throughput-oriented deployment where many problems are batched together, SoS+ might benefit more from continuous batching than APR (since APR's thread spawning introduces synchronization points where the parent must wait for all children). The paper's latency metric is a per-sample latency measure, not a throughput measure, which is appropriate for interactive applications but not for batch processing.

What the experiments do not show. Several important dimensions are absent from the experimental evaluation:

1. The cost of the difficulty estimation / thread-count decision is not separately measured. In the scaling experiments, the model is conditioned on a specific number of child threads — this is an oracle conditioning signal that tells the model how much parallelism to use. In a real deployment, the model would need to autonomously decide how many threads to spawn, and this decision itself consumes tokens (as part of the reasoning trace). The paper does not report how many tokens the spawning decisions consume or what accuracy is achieved without thread-count conditioning (i.e., when the model freely chooses its thread count). The RL experiments (Figure 5) show that the model does learn to use more threads without explicit conditioning, but the scaling curves in Figure 4a all use conditioned thread counts. The performance of an unconditioned APR model across the full range of compute budgets is not directly shown — it would likely fall between the conditioned curves, but the exact relationship is unknown.

2. There is no ablation on the join() summarization strategy. The paper specifies that child threads return only successful solution paths and discard intermediate traces. An ablation comparing this selective summarization to returning full child traces (as PASTA does) would quantify how much of APR's context-window advantage comes from selective summarization versus from the threading structure itself. If returning full traces produced similar performance, the context-window benefit would be attributable mainly to parallel distribution of attention across independent windows; if it degraded performance substantially, the selective summarization would be the key mechanism.

3. The Countdown task has a specific structure (tree search with clear subproblem boundaries) that makes parallelization natural. The paper does not evaluate on tasks where the parallel decomposition is less obvious — e.g., tasks requiring sequential dependency between reasoning steps, or tasks where "subtasks" are not cleanly separable. This limits the generality of the finding that "models can learn to parallelize their reasoning." The Countdown task's tree structure makes it an ideal case for parallel search; whether APR would provide benefits on tasks where reasoning is inherently more sequential (e.g., multi-step theorem proving, narrative comprehension) is untested.

4. The training-from-scratch paradigm means the model learns Countdown reasoning as its primary capability. When fine-tuning a pretrained model (Appendix A.4), the benefit of APR persists, but this experiment uses supervised fine-tuning only — no RL is applied to the pretrained model. It remains unknown whether RL on a pretrained model's APR policy would produce the same "learn to use more threads" effect, or whether the pretrained model's existing knowledge would change how it exploits the spawning interface.

5. There is no comparison against a hybrid baseline that combines SoS+ with hand-designed parallel decomposition — e.g., using a fixed Tree-of-Thought structure with the same model, or using an external orchestrator to divide the Countdown search space and call SoS+ independently on each partition. Such a baseline would isolate whether APR's learned coordination is genuinely superior to reasonable hand-designed coordination, or whether simply any form of parallel decomposition would produce similar gains. The paper's claim that APR "could result in language models that implement the same search structures as existing approaches" (Appendix A.1) is a theoretical possibility, not an empirical finding — no experiment shows APR actually discovering known search structures.

Statistical and methodological concerns. The test set size is not explicitly stated in the paper. Given the Countdown task's standard usage and the fact that the training set is 500k problems, the test set is likely several thousand problems at minimum, but this is an important omission. Without knowing the test set size, the statistical reliability of the reported accuracy differences cannot be assessed. A 0.1 percentage point difference (83.2% → 83.3%) on a test set of 1,000 problems corresponds to a single additional correct answer — effectively noise. However, the larger gaps (13.5 percentage points in scaling, 23.4 points in context window) are almost certainly statistically significant at any reasonable test set size.

The RL experiments use 150 training steps with validation every 25 steps, but no learning curves are shown. This makes it impossible to assess whether the RL training had converged, was still improving, or was beginning to overfit. The fixed 150-step budget is a reasonable engineering choice for a proof-of-concept, but prevents conclusions about the asymptotic behavior of RL on APR — would further training continue to increase thread count and accuracy, or is there a plateau?

The conditioning mechanism for thread count is used throughout the scaling experiments, but the paper does not report how accurately the model respects this conditioning — i.e., when conditioned to use 6 child threads, does the model actually spawn approximately 6 threads, or does it sometimes spawn 3 or 12? If the model frequently ignores the conditioning signal, the x-axis of the scaling curves (which plots conditioned thread count) would not accurately reflect the actual compute usage.

6. Limitations and Trade-offs

Limitation 1: Single Task and Model Configuration — Generality Is Unestablished

The assumption or constraint. All experiments are conducted on the Countdown arithmetic reasoning task using a 228M-parameter Llama2 model trained from scratch. The paper acknowledges this explicitly: "Currently, our experiments are restricted to non-pretrained LMs on Countdown tasks" (Section 5, Future Work #1). While Appendix A.4 demonstrates that fine-tuning a pretrained Qwen2.5 1.5B model on APR demonstrations also yields strong performance (80.2% for APR vs. 57.5% for SoS+), this experiment uses supervised fine-tuning only — no RL is applied to the pretrained model, and no evaluation is performed on tasks beyond Countdown.

The Countdown task has specific structural properties that make parallelization natural: the search space decomposes cleanly into independent subtrees rooted at different operation choices, and a binary correctness signal is available for RL without human annotation. These properties may not generalize to reasoning tasks with different characteristics — for instance, tasks requiring long chains of sequential dependency (multi-step theorem proving, legal reasoning), tasks where "subtasks" cannot be cleanly separated (open-ended analysis, dialogue state tracking), or tasks where the reward signal is ambiguous or requires human judgment.

The consequence. A practitioner cannot determine from this paper alone whether APR would provide benefits on their target task. The mechanism that makes APR effective on Countdown — decomposing tree-structured search into parallel sub-searches — may not transfer to domains where reasoning is inherently more sequential, where the search structure is less regular, or where subtask boundaries are harder to identify. Furthermore, the Countdown task is a puzzle with a small, well-defined action space (four numbers, four operations) — the model learns to reason entirely within this narrow world. On broader reasoning domains (mathematical proof, code generation, scientific reasoning), the spawning interface would need to operate over a much larger and more open-ended action space, and it is unknown whether the model would learn meaningful parallel decomposition or degenerate into spawning threads for trivial subtasks.

The from-scratch training paradigm further limits generality. The 228M model learns Countdown reasoning as its primary capability — it has no exposure to general linguistic knowledge, common sense, or diverse reasoning patterns that a pretrained model would possess. While Appendix A.4's pretrained Qwen result is encouraging, it represents supervised fine-tuning only, and the paper does not explore how pretrained knowledge might interact with (or interfere with) the spawning mechanism under RL optimization.

What evidence exists in the paper. Section 4 and all experiments use Countdown exclusively. Appendix A.5 extends to a five-number Countdown variant, but this is within the same task family and shares the same search structure (only the branching factor increases). Appendix A.4's Qwen experiment uses Countdown only. The paper does not report any ablation where spawning is disabled or replaced with an alternative coordination mechanism on a non-Countdown task. The "Future Work" section explicitly acknowledges the single-task limitation: "we plan to extend our methods to general reasoning tasks with pre-trained LMs, which would validate the approach's broader applicability" (Section 5, Future Work #1).

Mitigation status. Not addressed in the current paper. The future work plan is directional but provides no evidence about feasibility or expected difficulty. The paper's theoretical claim that APR "could result in language models that implement the same search structures as existing approaches, such as Tree-of-Thought, without explicit prompting" (Appendix A.1) is speculative and untested — no experiment demonstrates APR discovering a known search structure, let alone on a different task.

---

Limitation 2: Supervised Bootstrap Requires Symbolic Solver Demonstrations — Not Scalable to Tasks Without Synthetic Data

The assumption or constraint. The entire APR training pipeline begins with 500,000 demonstrations generated by a symbolic solver that can exhaustively search the Countdown problem space and produce annotated reasoning traces with spawn() and join() operations. The paper acknowledges dependency on this supervised stage: "Our current setup requires bootstrapping by mimicking the symbolic solver" (Section 5, Future Work #2), and envisions bypassing it in future work: "motivated by DeepSeek R1-Zero, explore whether we can bypass the supervised training stage and directly apply reinforcement learning" (Section 5, Future Work #2).

This is not merely a convenience — it is a hard requirement for the method as presently constituted. The symbolic solver provides:

• A corpus of syntactically valid spawn()/join() traces that teach the model the mechanics of the threading interface (the format of spawn commands, the structure of child thread contexts, the join protocol).
• A bootstrapping policy that achieves non-trivial task success (75.5% accuracy post-supervised-training for APR), providing a foundation from which RL can explore.
• Guaranteed correctness of training traces (the solver produces valid solutions), ensuring the supervised model learns from positive examples rather than needing to discover successful reasoning patterns through RL exploration alone.

For the Countdown task, building this symbolic solver is feasible because the search space is small enough for enumerative search and the correctness criterion is exact arithmetic evaluation. For most tasks of practical interest — mathematical reasoning with open-ended proofs, code generation against natural language specifications, multi-step planning in stochastic environments — no such symbolic solver exists. You cannot exhaustively enumerate the space of Python programs that satisfy a specification, or the space of legal arguments that support a conclusion, and generate optimal demonstration traces annotated with parallelization decisions.

The consequence. The method cannot be directly applied to tasks where synthetic demonstration data is unavailable. The paper's future work suggestion — "bypass the supervised training stage and directly apply reinforcement learning" — would require the model to learn the spawning interface from scratch through RL exploration alone. This is a vastly harder learning problem: the model would need to discover, through random token generation, that certain output sequences are interpreted by the infrastructure as spawn commands, that these commands create parallel inference threads, that those threads can return useful results, and that coordinating them effectively improves task success. For any task more complex than Countdown, this discovery problem is likely intractable with current RL algorithms — the space of possible output sequences is enormous, and the probability of randomly generating a syntactically valid and semantically useful spawn command that actually produces a reward signal is vanishingly small.

Even if future work develops methods to reduce supervised data dependence, the Countdown solver's specific design choices (the 10% random "promising node" heuristic, the multiply heuristic for state expansion, the hybrid BFS-DFS structure) are tailored to this task. Extending APR to a new domain would require designing and implementing a task-specific symbolic solver — a substantial engineering effort per domain that may be infeasible for open-ended reasoning tasks.

What evidence exists in the paper. Section 3.3 and Appendix A.6 describe the symbolic solver in detail, confirming its centrality to the training pipeline. The paper does not report any experiment that reduces the amount of supervised data (e.g., training on 50k traces instead of 500k, or using synthetic traces from a weaker solver) to assess how much supervised data is actually necessary. The paper does not attempt from-scratch RL without supervised initialization on any task, even Countdown. The "Future Work #2" statement explicitly frames this as unresolved.

Mitigation status. Not addressed. The future work direction is acknowledged but no partial steps are taken — for instance, an ablation training on 10% or 1% of the supervised data to establish a scaling trend, or a small-scale experiment with cold-start RL on a simplified Countdown variant, would have provided evidence about whether the supervised dependency is fundamental or merely convenient.

---

Limitation 3: The Headline Results Use Oracle Conditioning — Unrealistic for Deployment

The assumption or constraint. The scaling experiments in Figure 4a and the context window experiments in Figure 4b all evaluate APR under conditioned child thread counts — the model is explicitly told how many threads to use (e.g., "Child Thread Cond=3," "Child Thread Cond=6," "Child Thread Cond=10"). This conditioning signal serves as an oracle budget allocator: it specifies the optimal or near-optimal degree of parallelism for each evaluation point, without the model needing to decide autonomously how many threads to spawn.

In a real deployment, the model would receive no such conditioning signal. It would need to autonomously decide — through its generated tokens — how many child threads to spawn for each problem. The RL experiments (Figure 5) show that the un-conditioned model does learn to increase thread count after RL (from 6.1 to 8.2 on average), but the scaling curves that demonstrate APR's superiority over SoS+ (Figure 4a) are all collected with explicit thread-count conditioning. The performance of an unconditioned APR model across the full range of compute budgets — where the model freely chooses its thread count based on its own assessment of problem difficulty — is not directly reported anywhere in the paper.

The consequence. The headline numbers (80.1% at 20k tokens, 83.4% at 4k context) represent the performance of a system that receives external guidance about how much parallelism to use — guidance that would not be available in practice. An unconditioned APR model would likely fall somewhere between the conditioned curves, since it would sometimes use too few threads (under-exploring hard problems) and sometimes use too many (wasting compute on easy problems). The magnitude of this gap between conditioned and unconditioned performance is unknown, making it impossible for a practitioner to estimate realistic deployment accuracy.

Furthermore, the thread-count conditioning couples the budget control mechanism to the evaluation. For Figure 4a, the x-axis ("Avg Total Compute") is not directly controlled by the experimenter in the way that, say, the number of samples in cons@n is controlled — it is the observed total token consumption when the model is conditioned on a particular thread count. The mapping from conditioned thread count to actual token consumption is not one-to-one (different problems produce different-length traces at the same thread count), and the model may not perfectly respect the conditioning signal (it might spawn fewer or more threads than requested). The paper does not report the variance in token consumption at each conditioning level or the correlation between conditioned and actual thread count, making the budget-accuracy curves harder to interpret.

What evidence exists in the paper. The RL experiments (Figure 5) provide the only window into unconditioned APR behavior: after RL, the unconditioned model averages 8.2 child threads and 1,796 tokens per sequence, achieving 83.4% accuracy (the same as the best conditioned result). This suggests that at the specific operating point the RL policy converges to, unconditioned performance approximately matches the conditioned performance at that thread count. However, Figure 5 reports only the average behavior — it does not show the full accuracy-vs-compute curve for the unconditioned model (what accuracy does it achieve at 10k total tokens? At 15k? At 5k?). Without this curve, a practitioner cannot assess whether the unconditioned model's scaling behavior (the slope of the improvement with additional compute) matches the impressive slopes shown in Figure 4a.

The paper does not report an ablation where the conditioned thread count signal is removed and the model's free-choice behavior is evaluated across the range of test-time compute budgets. The conditioned scaling curves in Figure 4a should therefore be interpreted as an upper bound on APR performance, with the unconditioned case falling somewhere below them.

Mitigation status. Not addressed. The conditioning mechanism is treated as the primary evaluation protocol; the unconditioned model is evaluated only at the single post-RL operating point. No comparison of conditioned-vs-unconditioned scaling behavior is provided.

---

Limitation 4: Hardware Parallelism Requirement — The Latency Gains Require Multi-GPU Deployment

The assumption or constraint. APR's latency benefits depend on the availability of multiple GPUs to execute child threads concurrently. The efficiency experiments (Figure 6) use an 8-GPU NVIDIA RTX A6000 server with 1 GPU dedicated to the parent thread and 7 GPUs for children. If deployed on a single GPU, APR would provide no latency reduction — child threads would execute sequentially on the same device, and the wall-clock time would approximately equal the total token generation time across all threads (similar to cons@n, but with the added overhead of spawn-join orchestration tokens and the parent thread waiting for all children to complete before resuming).

The paper does not explicitly frame this as a limitation, but the hardware configuration is stated in Section 4.3: "We deploy the models on an 8-GPU NVIDIA RTX A6000 server, dedicating one GPU to handle the main inference thread, with the remaining GPUs allocated for executing child threads in parallel." This is not an incidental detail — it is a requirement for the headline latency result (75.2% at ~5,000ms).

The consequence. The method targets different deployment scenarios with very different cost profiles. SoS+ requires only a single GPU and achieves 57.3% at the same latency on the same hardware — but it could achieve that performance on a single GPU, which is dramatically cheaper and more widely available than an 8-GPU server. APR requires 8 GPUs to achieve its 75.2% at the same latency. The fair comparison is not just "same latency" but "same latency * same hardware cost" — an 8-GPU SoS+ deployment could process 8 problems in parallel via batching, potentially exceeding APR's throughput.

The hardware parallelism requirement also interacts with the model's learned spawning behavior. The RL-trained model spawns an average of 8.2 child threads — but with only 7 child GPUs available, some GPUs handle multiple threads, creating uneven load. Appendix A.10 acknowledges this: "in scenarios with higher compute demands — such as those involving up to 10 child threads — some GPUs may end up handling multiple child threads, leading to uneven workloads and increased computational load on certain devices." As the model learns to spawn more threads (the paper shows thread count increasing from 6.1 to 8.2 during RL, and the scaling experiments condition on up to 10 threads), the hardware mismatch grows — the model optimizes a parallelism strategy for a degree of hardware parallelism that may not be available.

For single-GPU deployments (the most common deployment scenario for language model inference in practice, including on-device, edge, and many cloud instances), APR's complexity provides no latency benefit over serialized methods and may even be slower due to orchestration overhead.

What evidence exists in the paper. The hardware configuration is stated in Section 4.3. Appendix A.10 notes the load-balancing issue. Figure 6 (right) shows the accuracy-latency curves on this specific hardware. No single-GPU ablation is reported. No throughput (problems per second) metric is reported — the evaluation focuses entirely on per-sample latency, which is the metric that benefits from APR's parallelism, rather than total system throughput, which may be comparable or worse given the GPU count.

Mitigation status. The paper identifies load balancing as an area for improvement ("This issue can be mitigated by allocating additional GPUs and improving load balancing during model serving," Appendix A.10) but does not explore single-GPU deployment, dynamic batching across parent and child threads, or alternative serving strategies that might reduce hardware requirements. The fundamental dependence on multi-GPU parallelism for latency gains is inherent to the APR architecture and cannot be "fixed" without redesigning the threading mechanism.

---

Limitation 5: No Quantification of the Within-Thread Reasoning Quality vs. Parallelization Tradeoff

The assumption or constraint. The paper's RL ablation (Section 4.4) demonstrates that RL improves APR almost entirely through increasing parallelism (more child threads, more total tokens) rather than through improving the quality of reasoning decisions within each thread. When conditioned to always use 10 child threads, accuracy is flat pre- and post-RL (83.2% → 83.3%). This finding is presented as an insight, but it also reveals a structural limitation: the method as currently constituted provides no mechanism for improving per-token reasoning effectiveness — only for increasing the volume of (parallel) computation.

This creates a fundamental tradeoff that the paper does not characterize: at what point does adding more child threads stop helping? The scaling curves in Figure 4a show APR accuracy increasing from roughly 75% at ~10k tokens to 80.1% at ~20k tokens — continued improvement, but with diminishing returns (the slope is decreasing). The paper does not explore whether the curve would eventually plateau, what the asymptotic accuracy is, or whether additional RL training could discover more effective spawning strategies beyond simply "spawn more threads."

The consequence. The scaling behavior may have a hard ceiling determined by the quality of reasoning within individual threads. If each child thread's independent reasoning capability — its ability to search a subtree effectively — does not improve with training or scale, then spawning more threads provides diminishing returns because each additional thread is exploring with the same limited per-thread capability. The paper's finding that RL does not improve per-token reasoning quality (under fixed-thread conditioning) suggests this ceiling may be closer than the scaling curves indicate — the gains from RL are primarily moving along the compute-accuracy curve (using more compute to reach a higher point), not shifting the curve upward (achieving better accuracy at the same compute).

This also has implications for model scale. The 228M model has limited reasoning capacity — its pass@1 on Countdown (without any search, equivalent to a single reasoning trace) is presumably much lower than 83.4%. The scaling to 600M parameters (Appendix A.3, Figure 8) shows APR at 600M reaching roughly 80% versus roughly 76% at 228M at the same 20k token budget — a 4 percentage point gain from doubling model size. This is substantial, but the paper does not disentangle whether the 600M improvement comes from better per-thread reasoning (higher-quality search within each child) or better parallelization strategy (smarter decisions about when and how to spawn). Without this decomposition, it's unclear whether further scaling of model size, RL training, or both would be the most effective way to improve APR.

What evidence exists in the paper. The RL ablation (Section 4.4, Figure 7) provides the key evidence: fixed-thread conditioning eliminates RL gains, showing that per-token reasoning quality is essentially unchanged by RL. The scaling curves (Figure 4a) suggest continued improvement at higher compute budgets, but the slope is decreasing. The 600M scaling experiment (Appendix A.3) shows improvement but does not decompose the source. No experiment directly varies model capacity while controlling for thread count and per-thread token budget to isolate per-thread reasoning quality scaling.

Mitigation status. Not addressed. The paper does not frame the per-thread reasoning quality ceiling as a limitation or propose mechanisms to improve it (e.g., training the model with RL to make better search decisions within threads, using a stronger base model, or incorporating the PRM-verifier mechanisms from Snell et al., 2025, to guide child thread search). The focus is entirely on the parallelism dimension of scaling.

---

Limitation 6: No Comparison Against a Hand-Designed Parallel Coordinator Using the Same Model

The assumption or constraint. APR's central claim is that learned parallel coordination is superior to hand-designed parallel structures. The paper compares APR against SoS+ (serial) and cons@n/pass@n (independent parallel sampling), but never against a baseline that combines the same base model with a hand-designed parallel decomposition — for instance, a Tree-of-Thought-style orchestrator that uses the SoS+ model to generate candidate next steps, evaluates them, and spawns parallel searches under the top-$k$ candidates using the same model checkpoint.

This is a significant omission because it conflates two claims:

1. That parallel decomposition (of any form) is better than serial or independent-parallel approaches for Countdown.
2. That learned parallel decomposition is better than hand-designed parallel decomposition.

The experiments only support claim (1). Claim (2) — which is the paper's conceptual contribution — is not empirically tested. A hand-designed parallel coordinator using the same SoS+ model (or even the same APR model with fixed spawning rules) could serve as a strong baseline that isolates the value of learned adaptive spawning decisions.

The consequence. We cannot determine whether the 13.5 percentage point gap between APR and SoS+ at 20k tokens (80.1% vs. 66.6%) is attributable to parallelization itself (which a hand-designed coordinator could also achieve), to the learned adaptive strategy (which a hand-designed coordinator might not match), or to other factors (the hybrid BFS-DFS search strategy in the training data, the model architecture, the RL training). If a simple hand-designed coordinator — e.g., "at each promising state, spawn 5 child threads that each do DFS search, select the first success" — achieved performance close to APR's, then the learned spawning strategy would add little value, and the paper's contribution would be more about the threading infrastructure than the learning algorithm.

Conversely, if APR substantially outperforms any hand-designed coordinator, that would be strong evidence for the value of learned parallelization strategies — but this evidence is absent. The paper's statement that APR "could result in language models that implement the same search structures as existing approaches" (Appendix A.1) is made without testing whether APR actually discovers anything resembling known search structures, or whether it outperforms them.

What evidence exists in the paper. None. No hand-designed parallel coordinator baseline is evaluated. The comparisons are exclusively against serialized search (SoS+) and independent parallel sampling (cons@n, pass@n). The Tree-of-Thought, Graph-of-Thought, and multi-agent methods discussed in the Related Work (Section 2) are cited as motivation but never implemented as baselines using the same 228M model.

Mitigation status. Not addressed. The paper's contribution is framed in terms of learned vs. hand-designed coordination, but the experimental design does not support this framing. A hand-designed coordinator baseline could be implemented without changing the model architecture — it would simply call the trained SoS+ model (or an unconditioned APR model) according to a fixed parallelization policy — and would substantially strengthen the paper's claims about the value of learning.

7. Implications and Future Directions

How This Work Changes the Landscape

APR introduces a specific and falsifiable hypothesis to the inference-time reasoning literature: that models can learn better parallel coordination strategies through end-to-end optimization than developers can design by hand, given the right interface primitives. This is not a paradigm shift — the paper does not propose a new learning algorithm, a new model architecture, or a new theory of reasoning. It is more precisely a reframing of the problem from search-structure design to interface design. The question shifts from "which search algorithm should I impose on the model?" to "which coordination primitives should I give the model so that it can discover effective search algorithms through RL?"

This reframing has a specific consequence for how researchers should invest effort. The paper demonstrates — through the spawn()/join() interface design, the supervised-to-RL training pipeline, and the SGLang integration — that the mechanical substrate for learned parallel reasoning (the serving infrastructure, the token-level API, the training protocol) is the primary engineering challenge, not the design of clever search heuristics. If this hypothesis is correct, then future work should focus on generalizing and hardening the interface layer (what primitives work across tasks? what serving optimizations are needed? how to bootstrap without a symbolic solver?) rather than on inventing ever-more-elaborate fixed search structures. The paper's negative result — that hand-designed coordination baselines (cons@n, pass@n) underperform learned coordination by large margins (13.5 percentage points at 20k tokens) — provides initial evidence that this reframing is productive, but the absence of a hand-designed parallel coordinator baseline (using the same model with fixed spawning rules) means the falsification is incomplete.

The paper also resolves a specific tension in the parallel inference literature that is worth making explicit. Prior work on parallel LLM inference splits into two camps: independent sampling methods (self-consistency, best-of-N) that solve latency but not coordination, and structured search methods (Tree-of-Thought, multi-agent debate) that solve coordination but require fixed, hand-designed protocols. These two camps appear to address orthogonal problems, and the literature has not produced a unified framework. APR demonstrates that a single learned policy can inhabit both roles simultaneously — the model generates independent reasoning in child threads (the parallel sampling benefit) while also conditioning child contexts on parent-assigned subtasks (the coordination benefit) — and that the balance between these roles can be shaped by RL rather than prescribed by the developer. This is a genuine conceptual unification, even if the experimental scope (single task, small from-scratch model) limits its current generality.

The paper also contributes a specific diagnostic technique that has value independent of APR's success: conditioning the model on a fixed compute budget (in APR's case, fixing the child thread count) and measuring whether RL provides gains beyond that point. This ablation can distinguish between "RL improved reasoning quality" and "RL increased compute allocation" — two confounded mechanisms in standard RL-for-reasoning evaluations. The paper's finding that RL provides zero gain under fixed-thread conditioning (83.2% → 83.3%, Section 4.4) is a clear demonstration that this diagnostic works, and it should become standard practice in future RL-for-reasoning work to report whether gains persist under budget-controlled conditions. Otherwise, the field risks misattributing compute-scaling gains to reasoning-quality improvements.

The work makes several research directions more attractive. Learned coordination protocols for LLM inference — where models develop their own communication strategies through multi-agent RL — become a tractable direction now that APR has demonstrated a working proof-of-concept with a simple spawn-join protocol. The integration of RL-based reasoning optimization with modern serving infrastructure (SGLang, prefix caching, continuous batching) becomes a first-class research concern rather than an implementation detail — the paper shows that the choice of serving framework directly affects what parallelization strategies are learnable. And the finding that RL primarily optimizes compute scale rather than per-token quality in the Countdown setting suggests that future work on RL for reasoning should separately evaluate and optimize both dimensions, rather than reporting only aggregate accuracy gains.

Conversely, the paper makes some directions less urgent. The hand-designed search structure literature (Tree-of-Thought and its many variants) loses some priority if models can learn equivalent or better structures from reward alone — though the paper has not yet demonstrated that APR actually discovers known structures, only that it outperforms them on one task. The "pause token" and "token discarding" approaches (Goyal et al., 2024; Yang et al., 2025) for controlling inference compute are somewhat subsumed conceptually by APR's more general spawning interface — if models can learn to spawn child threads, they can in principle also learn to insert pauses or discard context, making those approaches special cases of the APR framework rather than competing methods.

Follow-Up Research This Work Enables

Constructing a hand-designed parallel coordinator baseline to isolate the value of learned coordination. The paper compares APR against serialized SoS+ and independent parallel sampling (cons@n, pass@n), but never against a hand-designed parallel decomposition using the same 228M model. A critical follow-up would implement a fixed parallelization policy — for instance, a Tree-of-Thought-style orchestrator that calls the trained SoS+ model at each branching point, spawns $k$ parallel child explorations using APR's threading infrastructure (or an equivalent external orchestrator), and selects the first successful child's solution — and evaluate it at the same total token budgets as APR across the full scaling curve (Figure 4a). If the hand-designed coordinator's scaling curve closely tracks APR's, then the learned spawning strategy adds minimal value beyond what simple parallel decomposition provides; the paper's contribution would be primarily in the threading infrastructure rather than the learning algorithm. If APR substantially outperforms the hand-designed coordinator — particularly at high compute budgets where the learned strategy's adaptivity should matter most — that would provide the missing evidence that end-to-end optimization discovers coordination strategies that humans cannot easily specify. The experiment should also characterize where APR diverges from the hand-designed baseline: does APR spawn threads at different points in the search tree? Does it vary thread count per-problem in ways a fixed policy cannot? Does it return different information through join() than a hand-designed summarization rule would?

Evaluating APR on a reasoning task without natural subtree decomposition to test the generality of the learned parallelization strategy. The Countdown task has cleanly separable subtrees: each choice of initial operation leads to an independent sub-search. APR's spawn() interface exploits this structure naturally. A strong stress-test would apply APR to a reasoning task where the parallel decomposition is not obvious — for instance, multi-step mathematical proof generation (where later steps depend logically on earlier steps), or code generation with sequential dependencies between functions, or multi-hop question answering where each hop builds on the answer from the previous one. The key question: does the model learn to spawn threads for genuinely useful parallel subtasks (e.g., exploring alternative lemma choices, testing different API implementations), or does it degenerate into spawning threads that simply duplicate the parent's computation with different random seeds (effectively degrading to expensive self-consistency)? The Countdown experiments cannot answer this because the task's structure makes parallelization easy. A negative result — APR providing no benefit over SoS+ on a sequentially-structured reasoning task — would establish a boundary condition: the spawning interface enables learned parallelization only when the task has identifiable independent subproblems. A positive result — the model discovers non-obvious parallelization opportunities even on seemingly sequential tasks — would substantially strengthen the case for generality.

Cold-start RL directly from a pretrained model without supervised demonstrations, to test whether the symbolic solver bootstrap is necessary. The paper's reliance on 500,000 solver-generated demonstrations is its most significant scalability limitation. Following the DeepSeek-R1-Zero approach (DeepSeek-AI, 2025), a critical experiment would attempt to train a pretrained language model (e.g., Llama-3-8B or Qwen2.5-7B) to use spawn() and join() through pure RL exploration, without any supervised demonstrations of the threading syntax. The experiment would need to address the discovery problem: how does the model learn that certain output sequences trigger parallel thread execution? Several design choices could help — providing the model with a textual description of the spawning interface in the system prompt, using a shaped reward that encourages exploration of the spawn action space, or starting with a small number of hand-written demonstrations (e.g., 10-100 examples of spawn-join syntax) rather than the full 500k set. The research question is not "can this work" but "how much supervised data is actually needed?" — quantifying the scaling relationship between number of demonstrations and final RL performance would provide a practical data requirement that future practitioners could budget for. The Countdown task (with its exact symbolic solver) is ideal for this experiment because the ground-truth reward is available without human annotation, and the 500k demonstration ceiling is known.

Characterizing the per-thread reasoning quality ceiling and whether it can be improved through RL with appropriate auxiliary objectives. The paper's key ablation (Section 4.4) shows that RL provides no accuracy improvement when thread count is fixed — all gains come from scaling compute, not from improving per-token reasoning effectiveness. This raises an important open question: can per-thread reasoning quality be improved through RL, or is the supervised model already at the ceiling for the 228M architecture? A follow-up experiment would train APR with an auxiliary reward that penalizes thread tokens without penalizing spawn decisions — for instance, a reward of $r_{\text{task}} - \lambda \cdot (\text{total tokens})$ that encourages the model to solve problems with fewer per-thread tokens while maintaining the freedom to spawn as many threads as it wants. If this produces models that achieve the same accuracy with shorter per-thread traces, it would demonstrate that per-thread reasoning efficiency is learnable under the right objective. If it produces models that maintain thread length but spawn fewer threads (shifting compute allocation rather than improving efficiency), it would confirm that the per-thread reasoning ceiling is architectural rather than motivational. This experiment also connects to the broader question of whether test-time compute scaling laws (Snell et al., 2025) can be shifted upward through better training objectives rather than just exploited through better allocation.

Analyzing what the RL-trained spawning policy actually discovers about the Countdown search space. The paper reports aggregate statistics (thread count increased from 6.1 to 8.2; accuracy improved from 75.5% to 83.4%) but does not characterize what the model learned about when to spawn. A qualitative analysis of the spawning behavior would ask: does the RL-trained model spawn threads at states with higher branching factors (where parallel exploration is more valuable)? Does it spawn earlier in the search (shallow vs. deep) than the supervised model? Does it vary thread count by problem difficulty, and if so, what features of the problem (number of prime factors of the target? magnitude of input numbers?) predict the spawning decision? This analysis could be done by instrumenting the inference pipeline to log the spawn points visited and the state features at each spawn, then comparing supervised vs. RL policies. The results would either reveal an interpretable strategy (e.g., "RL learned to spawn at nodes where more than 3 valid operations are available") or demonstrate that the policy is inscrutably optimized against the reward landscape. If the former, it would validate APR as a tool for discovering coordination heuristics that could then be extracted and analyzed. If the latter, it would raise interesting questions about the interpretability of RL-trained meta-strategies.

Practical Applications and Downstream Use Cases

Latency-constrained interactive reasoning assistants. For applications where a language model must solve reasoning problems within a hard latency budget (e.g., an interactive tutoring system that needs to respond within 5 seconds to maintain student engagement), APR's latency-accuracy curve (Figure 6, right) directly translates to better user experience. At matched 5,000ms latency, APR achieves 75.2% accuracy versus SoS+'s 57.3% — meaning the system solves roughly 18 more problems per 100 within the user's patience threshold. A tutoring system for competition math, for instance, could deploy an APR-trained model across multiple GPUs and provide correct solutions to a substantially higher fraction of student queries without exceeding acceptable response times. The engineering requirement — an 8-GPU server for the reported configuration — limits deployment to cloud-based (rather than on-device) scenarios, but this matches the typical architecture of production tutoring and educational AI systems.

Efficient batch data generation for self-improvement pipelines. When using language models to generate training data for themselves (as in STaR, ReST$^{EM}$, or instruction-tuning data synthesis), the quality of generated solutions matters more than the latency per solution. APR's compute-accuracy scaling curve (Figure 4a) shows that it achieves 80.1% accuracy at 20k tokens, matching SoS+ pass@8's 68.4% while consuming 57.4% less compute. For a data generation pipeline processing millions of problems, this translates to generating higher-quality training data (80% correct vs. 68% correct) with fewer than half the GPU-hours. Since self-improvement pipelines are typically throughput-bound (processing large batches of problems overnight) rather than latency-bound, APR's multi-GPU requirement can be satisfied by typical data center configurations, and its higher per-problem accuracy means fewer incorrect solutions contaminate the training set — a critical concern in self-improvement where model errors can compound over iterations.

Verification of candidate solutions in high-stakes reasoning. In domains where the cost of an incorrect answer is high (medical reasoning, legal analysis, safety-critical code generation), it is common practice to generate multiple candidate solutions and verify them. APR's coordinated parallelization provides a structured way to do this: the parent thread can spawn child threads that each independently verify a different candidate solution or explore a different reasoning path, and the selective join() summarization ensures the parent sees only verified results without context pollution from failed verification attempts. The Countdown results (83.4% vs. 60.0% within the same per-thread context window) suggest that APR can maintain reasoning quality within bounded context limits while exploring more candidates than serialized methods — directly applicable to settings where a human reviewer wants to see multiple independent reasoning traces before accepting a recommendation.