acceptodds
Under review as a conference paper at ICLR 2027

BranchWeave: Local Wavefronts with Device-Wide Batching for Verifier-Guided Test-Time Scaling

Abstract

Test-time scaling lets compact language models spend additional inference compute on difficult queries, extending reasoning under deployment constraints. Verifier-guided search converts this budget into candidate paths and scores, yet existing runtimes advance subtrees in global depth rounds. A completed subtree waits for unrelated work, while immediate dispatch produces small generator and verifier batches. We introduce BranchWeave, which separates the dependency scope of search from the batching scope of model execution. BranchWeave derives selection domains from reducer dependencies; once a domain receives its selection scores, its local wavefront advances. Stable node identities keep sampling decisions, scores, KV state, and speculative continuations attached to their owners as calls are reordered. Device-wide generator and verifier queues then pool ready calls across domains and depths, forming dense batches without delaying local progress. Together, local release and shared batching convert barrier time into scored reasoning before the response deadline. Across three generator–PRM pairs and five reasoning benchmarks, BranchWeave completes searches up to 5.46× faster and delivers up to 4.94× higher goodput.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
Test-Time Scaling, Verifier-Guided Search, Local Wavefront Scheduling, Device-Wide Batching, LLM Inference Serving

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.20 over 5 reviews, above 96% of the others.
Reviewer_QjCnOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper presents BranchWeave, an inference runtime for verifier-guided test-time scaling that addresses synchronization stalls and batch fragmentation in tree-based LLM reasoning. The authors observe that existing runtimes tie search progress to global depth rounds, forcing completed independent subtrees to wait for shifting stragglers while immediate per-subtree dispatch produces inefficient small batches. To decouple search dependencies from model execution, BranchWeave derives independent selection domains from reducer read-write conflicts to advance completed subtrees immediately as local wavefronts, binds random seeds, KV states, and speculative continuations to stable logical node identities to preserve exact search outcomes under out-of-order execution, and pools ready calls across domains and depths into shared device-wide generator and verifier batches. Evaluations across multiple generator–verifier pairs and five mathematical reasoning benchmarks demonstrate up to 5.46× end-to-end speedup and 4.94× higher goodput over existing baselines without altering final search results.

Critical strengths
  1. The paper offers a sharp system insight by observing that shifting stragglers across search depths compound global barrier waits, and proposes a clean runtime architecture that decouples reducer synchronization scopes from device-wide batching scopes. By partitioning search trees into independent selection domains based on read-write conflict analysis, BranchWeave allows completed subtrees to advance immediately as local wavefronts while pooling ready calls across domains and depths into dense GPU batches.

  2. The proposed logical node identity mechanism strictly preserves synchronous search outcomes under out-of-order execution and delivers substantial end-to-end speedups. By binding random seeds, tie-breaking rules, KV cache blocks, and speculative continuations to canonical node identities, the runtime guarantees exact candidate-list equivalence while achieving up to 5.46× speedup over vLLM and up to 2.24× speedup over the state-of-the-art FastTTS baseline.

Critical weaknesses
  1. The applicability of the proposed local-wavefront scheduling is restricted to root-parallel search topologies with independent subtrees, and the paper omits discussion and comparison with recent speculative tree-search systems that break true global barriers. Whenever a search algorithm relies on global frontier ranking or shared budget allocation, such as standard beam search, REBASE, or MCTS, read-write conflicts collapse the entire frontier into a single selection domain and reduce BranchWeave to global synchronous execution with a negligible 1.002× speedup in Table 5. In contrast, recent work such as SPEX [1] tackles the same reward synchronization barrier and long-tail straggler bottleneck across both global BFS and sequential DFS algorithms via tree-level speculative exploration, which should be discussed and compared.

  2. The experimental evaluation is limited to single-query execution on a single consumer GPU and does not examine multi-query serving scenarios. In realistic online deployments, concurrent requests from multiple users can naturally fill generator and verifier batches through standard continuous batching, which may already hide intra-query straggler stalls and diminish the marginal benefit of cross-domain batching within a single query.

[1] Breaking the Reward Barrier: Accelerating Tree-of-Thought Reasoning via Speculative Exploration. OSDI' 26.

Questions for authors

How does BranchWeave compare conceptually and empirically against tree-level speculative exploration frameworks such as SPEX, and can BranchWeave be extended to accelerate global-frontier search algorithms like REBASE or MCTS where selection domains cannot be decoupled?

4 comments

We thank the reviewer for their careful review and comments on search-dependency boundaries, speculative exploration, and shared-service evaluation. We have revised the paper in light of this feedback.

W1 / Q1

The boundary for local progress is determined by the candidates and mutable state on which a selection actually depends. DVTS subtrees select independently, so a subtree can advance once its own scores have returned without waiting for other subtrees. With global beam ranking, global expansion-budget allocation in REBASE, or MCTS with shared tree statistics, unfinished results can still affect the same selection. The dependent tasks must then belong to one selection domain, retaining the necessary synchronization.

Extending to these searches requires distinguishing execution organization from additional parallelism. In a single domain, BranchWeave(BW) can still organize ready model calls and batches, but local release cannot bypass an unresolved global selection. Root-parallel variants with independent state and budgets can form multiple domains; precomputing subsequent branches while preserving global selection rules requires a speculative mechanism such as SPEX. The current compiler implements domain partitioning for DVTS and global beam search. Integrating REBASE/MCTS further requires adaptation to their specific state and update rules.

For the REBASE and MCTS configurations in the question, where selection domains cannot be decoupled, local release alone cannot accelerate execution by eliminating that global barrier. If REBASE's expansion allocation depends on normalized scores across the entire frontier, subsequent expansion cannot be determined before the required scores arrive. If MCTS shares ancestor visit counts and value statistics, backpropagation along one path also affects subsequent selection. Preserving these decision semantics requires dependent tasks to remain in the same selection domain; a subset cannot commit its selection early.

A single coupled domain leaves batching opportunities but removes the opportunity for earlier progress across domains. Additional end-to-end acceleration is therefore not guaranteed. The single-domain control in Table 5 shows only an approximately 1.002× speedup, consistent with this boundary: the scheduler cannot make a selection eligible before its required inputs are complete.

The methods exploit different sources of parallelism: BW advances independent domains whose selections are complete, while SPEX precomputes potential successors before selection is resolved. For example, when subtree A has all its scores while B is still waiting, BW can complete A's selection and continue. When B itself still lacks required scores, SPEX can predict subsequent exploration, precompute it, and use provisional results as the search proceeds. BW removes waiting between independent decisions; SPEX uses speculation to work ahead of unresolved decisions. The two opportunities are therefore complementary.

The comparison between BW and SPEX is shown below.

nConfiguration (generator + PRM)Mean s/query, SPEX/BWSPEX/BW time ratioSPEX: Top-1/Top-N(%)BW: Top-1/Top-N(%)
641.5B + 1.5B38.28/20.921.859×60.6/80.961.7/83.0
647B + 1.5B71.76/63.731.184×68.1/80.964.9/81.9
641.5B + 7B61.07/54.311.119×46.8/86.248.9/83.0
2561.5B + 1.5B109.72/64.481.755×63.8/87.262.8/87.2
2567B + 1.5B198.16/165.241.199×69.1/86.264.9/86.2
2561.5B + 7B224.54/197.391.124×45.7/84.041.5/89.4

BW reduces wall-clock latency in all six configurations, with trade-offs depending on the model combination. For 1.5B + 1.5B at n=64, BW achieves a 1.859× speedup with higher Top-1 and Top-N. At n=256, both have Top-N of 87.2%, while BW trades approximately 1 percentage point of Top-1 for a 1.755× speedup. For 7B + 1.5B at n=256, both have Top-N of 86.2%, and mean latency falls from 198.16 to 165.24 seconds, corresponding to a 1.199× time ratio, with Top-1 of 64.9% versus 69.1%. These results support choosing operating points jointly by quality and latency and illustrate the optimization opportunities for local release and tree-level speculation.

W2

BW retains latency gains when other queries already supply work for continuous batching. We share one generator and PRM across multiple queries on a single GPU at n=64, setting the number of simultaneously active queries C to 1, 2, or 4 and replacing each completed query with the next one. Results are shown below. Times are in seconds, and time ratios are geometric means of per-question Async/BW ratios.

Configuration (generator + PRM)CMean time (s/query), Async/BWAsync/BW time ratio
7B + 1.5B179.78/56.791.378×
7B + 1.5B2111.15/74.951.462×
7B + 1.5B4227.12/123.691.847×
1.5B + 7B161.34/55.901.096×
1.5B + 7B2106.53/101.501.093×
1.5B + 7B4202.49/200.751.024×

The effect of concurrency depends on which model limits progress. For 7B + 1.5B, speedup grows from 1.378× to 1.847× as C increases from 1 to 4. For 1.5B + 7B, it narrows from 1.096× to 1.024×, consistent with less optimization headroom when scoring dominates. Other queries can fill model batches without removing each query's dependence on its own PRM results. BW can still coordinate the release and service of this work, but the benefit depends on the balance between generation demand, scoring cost, and available capacity. Shared-service gains consequently depend on coordination between the two model queues as well as batch occupancy within each engine.

Dear Reviewer QjCn,

Thank you again for your review. Our responses are posted above. W1/Q1 discusses BranchWeave's relationship to SPEX and reports a direct comparison of latency and answer quality. It also makes the limitation for globally coupled REBASE/MCTS explicit: local release cannot bypass a selection's unresolved dependencies. W2 adds concurrent-query experiments with one, two and four active queries, showing how the gains depend on the balance between generator and PRM work.

Could you let us know whether these additions address your concerns, or which points remain open? We remain available to answer any further questions during the discussion. If your concerns are resolved, we would be grateful if you could reflect this in your assessment.

Best regards,

The authors

Dear authors,

Thank you for the detailed response and the additional experiments. The comparison with SPEX and the multi-query results have addressed my main questions. I also appreciate the clear discussion on why the method does not directly accelerate globally coupled search algorithms like REBASE and MCTS.

Overall, I think it is a solid paper. Therefore, I will raise my rating to 4.

Reviewer_mncROpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes BranchWeave, a scheduling system for verifier-guided test-time scaling. The method mainly focuses on eliminating unnecessary global depth barriers between different search subtrees, allowing each selection domain to advance asynchronously after completing its local decision, while aggregating generator and PRM requests through device-wide batching. The experiments cover three different model settings and five mathematical reasoning benchmarks, demonstrating significant efficiency improvements.

Critical strengths
  1. The paper identifies resource underutilization caused by global synchronization barriers and improves inference efficiency through local progress and cross-domain batching.

  2. Substantial performance improvements. Compared with FastTTS and vLLM, BranchWeave achieves significant speedups across various experimental settings.

Critical weaknesses
  1. Insufficient comparison with closely related work. DPTS [1] has already explored dynamic parallel tree search and cross-path batching, while TreeThink [2] supports asynchronous tree search and batched model execution. However, the paper does not sufficiently clarify its differences from these prior approaches or provide targeted experiments to demonstrate the additional benefits of its proposed mechanisms.

  2. The experimental comparisons primarily focus on vLLM, FastTTS, without including a straightforward baseline that combines an asynchronous DVTS controller with continuous batching.

[1] Ding, Yifu, et al. "Dynamic parallel tree search for efficient llm reasoning, 2025." In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers).

[2] Akbudak, Burak S., et al. "TREETHINK: A Modular Tree Search Library for Mathematical Reasoning with LLMs." arXiv preprint arXiv:2607.11258 (2026).

Questions for authors
  1. Could the authors detail that how does BranchWeave differ from DPTS and TreeThink? Which mechanisms provide benefits beyond existing asynchronous search and batching techniques?

  2. How does BranchWeave perform against a baseline that treats each DVTS subtree as an independent asynchronous task and uses an existing continuous-batching engine to serve generator and PRM requests?

  3. BranchWeave exhibits performance degradation compared to FastTTS in the PRM-heavy configuration. Could the authors explain why PRM execution becomes substantially slower in this setting?

5 comments

We thank the reviewer for their careful review and comments on comparisons with related work, asynchronous baselines, and PRM bottlenecks. We have revised the paper in light of this feedback.

W1 / Q1

BranchWeave(BW) separates the scope of a search decision from the scope of shared model execution. This connects domain-local release to coordinated generator/PRM service and stable ownership of sampling, scores, and KV state. The main differences among the three methods are as follows:

  • DPTS: Combines path allocation for exploration and exploitation with parallel expansion, manages node KV state, and adjusts the number of parallel paths to available GPU memory. Its focus is the joint optimization of search-path allocation and parallel execution.
  • TreeThink: Modularizes search, generation, and evaluation, supporting different search algorithms through asynchronous calls and batching. Its beam controller selects the next level after collecting all expansion results for the current frontier.
  • BranchWeave: Separates the synchronization scope of selection from the batching scope of model calls. An independent domain advances once all its required scores return. Generator and PRM queues pool ready calls across domains and depths while preserving the logical node ownership of sampling, scores, and KV state.

Comparisons of BranchWeave with DPTS and TreeThink are shown below. Each method entry gives “method/BW wall-clock time ratio; Top-1/Top-N (%).” Time ratios are geometric means of per-question paired ratios.

nConfiguration (generator + PRM)BW: Top-1/Top-NDPTS: time ratio; Top-1/Top-NTreeThink: time ratio; Top-1/Top-N
641.5B + 1.5B61.7/83.02.569×; 64.9/81.91.569×; 63.8/84.0
647B + 1.5B64.9/81.93.654×; 67.0/83.01.193×; 67.0/83.0
641.5B + 7B48.9/83.01.650×; 48.9/83.01.065×; 53.2/84.0
2561.5B + 1.5B62.8/87.23.332×; 66.0/85.11.325×; 64.9/87.2
2567B + 1.5B64.9/86.24.841×; 68.1/87.21.102×; 68.1/87.2
2561.5B + 7B41.5/89.41.836×; 39.4/87.21.005×; 41.5/88.3

The comparisons show larger gains in the balanced configuration and a smaller margin over TreeThink under PRM-heavy service. For 1.5B + 1.5B, BW achieves 2.569×/3.332× time ratios against DPTS and 1.569×/1.325× against TreeThink at n=64/256. For 1.5B + 7B, n=256, the TreeThink/BW ratio is 1.005×, indicating that the additional advantage can narrow when scoring dominates. Candidate coverage remains close in these examples. The execution distinction is that concurrent search tasks still require coordinated admission and service across the generator and PRM. BW explicitly manages this relationship, providing a further optimization layer alongside path allocation and asynchronous execution.

W2 / Q2

BW retains a latency advantage over independent subtree coroutines with continuous batching. Results for BW and Async on the same questions are shown below. Async uses continuous batching for generation and a shared PRM batcher. Times are mean seconds per query, time ratios are geometric means of per-question paired ratios, and quality entries are Top-1/Top-N (%).

nConfiguration (generator + PRM)Mean s/query, Async/BWAsync/BW time ratioAsync: Top-1/Top-NBW: Top-1/Top-N
641.5B + 1.5B32.32/20.921.568×63.8/81.961.7/83.0
647B + 1.5B69.86/63.731.127×64.9/84.064.9/81.9
641.5B + 7B58.26/54.311.072×51.1/85.148.9/83.0
2561.5B + 1.5B84.07/64.481.337×66.0/86.262.8/87.2
2567B + 1.5B185.96/165.241.125×66.0/88.364.9/86.2
2561.5B + 7B202.68/197.391.021×46.8/87.241.5/89.4
  • BW further reduces end-to-end latency beyond independent subtree progress and continuous batching. Async already allows subtrees to advance independently, uses continuous batching for generation, and batches PRM calls through a shared queue; BW additionally coordinates task admission and generator/PRM service across the device. The 1.5B + 1.5B configuration achieves 1.568×/1.337× speedups at n=64/256, indicating that organizing and serving ready work still offers optimization opportunities after asynchronous execution is available. For PRM-heavy 1.5B + 7B, the corresponding gains are 1.072×/1.021×: when scoring consumes most model time, earlier generation has less scope to improve total latency, illustrating how the model combination and serving bottleneck affect the available gains.
  • Favorable operating points offer more pronounced latency gains with limited accuracy differences, while some preserve the same Top-1. For 7B + 1.5B at n=64, BW and Async both achieve 64.9% Top-1, with a 1.127× speedup. For 1.5B + 1.5B at n=64/256, Top-1 differs by approximately 2.1/3.2 percentage points alongside 1.568×/1.337× speedups, while Top-N is slightly higher in both cases. For 1.5B + 7B at n=256, the Top-1 difference is 5.3 percentage points, while Top-N increases from 87.2% to 89.4%. Candidate coverage measures whether a correct answer is present, whereas Top-1 also depends on final ranking. Operating points should therefore be selected jointly by final-answer quality and latency; further optimization can address both scoring efficiency and the conversion of correct candidates into final predictions.

Q3

Gains in PRM-heavy configurations depend on scoring's share of the total cost. Stage measurements for 1.5B + 7B are shown below. Times measure BW's calls in seconds per query, and PRM input tokens are runtime estimates.

nGenerator (s)PRM (s)PRM share of model call timeEstimated PRM input tokens
6415.2036.6370.7%235,210
25639.77147.1078.7%930,881

Scoring increasingly limits the benefit of earlier generation as the search budget grows. PRM calls account for approximately 70.7%/78.7% of the combined generator and PRM call time. As n grows from 64 to 256, both scoring input volume and PRM time increase approximately fourfold. Local progress can release subsequent generation earlier, but the prefix scoring required by the search rules remains. When scoring dominates, generation-side savings contribute less to total latency. This reflects a trade-off between the model combination and serving cost: BW with 7B + 1.5B at n=64 achieves 64.9% Top-1, offering an operating point that balances generation capacity and scoring cost, while heavier PRM configurations place greater emphasis on scoring efficiency.

Differences in score reuse help explain why PRM work can increase relative to FastTTS. FastTTS can obtain scores for multiple steps when SBE has generated subsequent steps, then skip another PRM call when those steps already have scores. The current BW implementation scores the prefix currently committed by each domain; generation-side SBE caching does not automatically provide the same reuse of scores across multiple steps, potentially increasing scoring calls and processing of overlapping prefixes. Local progress also changes prefix arrival times, the mix of lengths in scoring batches, and the duration of uninterrupted service, so cumulative PRM call cost need not decrease in line with generator cost.

Step-score reuse and adaptive PRM service are complementary optimization directions. Further work can reuse existing step scores under identical prefixes and scoring rules, alongside prefix-length batching, adaptive generator/scoring service allocation, and more extensive PRM prefix-state reuse. We hold serving parameters fixed across budgets within each model combination to expose behavior as search scale changes. These engineering optimizations can complement local progress and shared batching, providing future work that broadens the effective range of model combinations.

Reviewer_PG9GOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper targets verifier-guided test-time scaling with generator + prm set up on single memory-constrained GPU. The focus is to improve upon root-parallel search such as DVTS, where each subtree's reducer selects only among its own children. Exisitng TTS runtimes advance all subtrees in global depth rounds, so a subtree whose scores are complete still waits for the slowest subtree at every depth. This paper makes three changes: 1 Defining "selection domains" as connected components of reducer read/ write conflicts ( one per DVTS subtree and one for global beam search), each domain advances as soon as its own sibling group is scored, i.e. "local wavefront". 2 It binds sampling seeds, tie-breaking, KV blocks and fastTTS-style speculative continuations to logical node, so reordering does not change decisions. 3 It pools ready generator and PRM calls form all domains and depths into device-wide epochs under batch/kv limits with bounded waits.

The paper's analysis shows ideally T_round (total time if wait for all) is greater than or equal to T_wave (time using local wavefront), with equality iff one same domain is slowest at every depth.

Experiments use one RTX 4090 D, with Qwen 2.5 generators and Skywords 1.5 B / math-shepherd-7b PRMs, on AIME and AMC 2024/25, reporting significant E2E speed up over FastTTS and vLLM.

Critical strengths
  1. The observation is correct and well-scoped. The depth barrier is unnecessary for root-parallel search.
  2. The implementation is careful and isolated cleanly. The paper removed the depth barrier safely, with node-bound seeds, canonical tie-breaking, and owned speculative KV. Experiments are well designed.
  3. The gain in the generator-bound regime is practical.
Critical weaknesses
  1. The search quality is not discussed or reported. No accuracy or solve rate is reported. The paper is motivated by response deadlines but not the measure of accuracy at deadline.
  2. The most natural alternative is missing, so the novelty is a bit hard to judge. The paper's premise is that dispatching each ready subtree yields small generator and verifier batches, which holds only for a synchronous controller that issues one block generate per group. In an iteration-level or continuous-batching engine ( vLLM's async engine, SGLang) running each DVTS subtree as an independent asynchronous program already releases work per subtree. The engine merges in-flight requests from all subtrees and depths into every decode step, which aligns with the paper's scopes.
Questions for authors
  1. It would help complete the comparison by reporting accuracy or solve rate, together with effective tokens per beam and completed candidates. Why does BranchWeave complete ~30% fewer effective tokens per beam than FastTTS? If accuracy is on par and the work gap is explained, this concern is resolved.

  2. How does BranchWeave compare with DVTS implemented as one async coroutine per subtree over vLLM's async engine or SGLang fork / run_batch (with a separately batched PRM) ?

5 comments

We thank the reviewer for their careful review and comments on asynchronous baselines, actual work performed, and answer quality under time budgets. We have revised the paper in light of this feedback.

W1 / Q1

Quality and latency. BranchWeave(BW)’s latency gains can coincide with unchanged Top-1, while other operating points expose a quality–latency trade-off. We compare the same questions, model configurations, and search budgets. Quality columns for all four systems report Top-1 / Top-N (%); latency is the arithmetic mean in seconds per query, and the Async/BW time ratio is the geometric mean of per-question paired ratios.

nConfiguration (generator + PRM)Mean s/query, Async/BWAsync/BW time ratiovLLM-SyncFastTTSAsyncBW
641.5B + 1.5B32.32/20.921.568×63.8/81.960.6/83.063.8/81.961.7/83.0
647B + 1.5B69.86/63.731.127×66.0/84.064.9/76.664.9/84.064.9/81.9
641.5B + 7B58.26/54.311.072×46.8/85.152.1/83.051.1/85.148.9/83.0
2561.5B + 1.5B84.07/64.481.337×64.9/87.267.0/85.166.0/86.262.8/87.2
2567B + 1.5B185.96/165.241.125×66.0/85.167.0/87.266.0/88.364.9/86.2
2561.5B + 7B202.68/197.391.021×42.6/88.344.7/87.246.8/87.241.5/89.4

The joint measurements make the deployment trade-off explicit. At 7B + 1.5B, n=64, BW achieves the same 64.9% Top-1 as Async with a 1.127× speedup. At 1.5B + 1.5B, n=64/256, the 1.568×/1.337× speedups accompany 2.1/3.2-point Top-1 differences and slightly higher Top-N. Thus, some operating points preserve final-answer accuracy, while others offer more substantial latency savings with modest accuracy differences. Separating Top-1 from Top-N makes both final-answer quality and the availability of correct candidates visible.

Effective tokens and candidate counts. Effective tokens measure returned-path length, so a shorter path statistic does not by itself imply less GPU computation. For question i, let CiC_i be the number of candidates returned by the search and lijl_{ij} the cumulative number of committed reasoning tokens along candidate j's path. Effective tokens per beam are ui=∑jlij/Ciu_i = \sum_j l_{ij} / C_i, and Goodput is ui/(generator time+PRM time)u_i / (\text{generator time} + \text{PRM time}). This excludes input prompts and speculative continuations that are not adopted, measuring the mean effective length of returned paths. CiC_i counts candidates returned under the search's termination rules; it is neither the number of correct answers nor necessarily equal to budget n. Thus, 1.241/1.710≈0.7261.241/1.710 \approx 0.726 in Table 2 implies approximately 27.4% lower effective length per beam; it cannot directly be interpreted as approximately 30% less physical GPU generation or computation.

We checked the per-candidate token records for FastTTS and BW. Results for the primary 7B + 1.5B configuration are shown below.

nEffective tokens/candidate, FastTTS/BWReturned candidates/query, FastTTS/BWEffective-length ratio, BW/FastTTS
64882.3/628.567.90/71.470.795
256884.5/653.2315.34/287.050.805

Note: The final column uses paired geometric averaging. Effective tokens and candidate counts are first calculated per question and then averaged arithmetically. The length ratio is the geometric mean of per-question BW/FastTTS ratios, so it is not the ratio of the displayed means.

BW's execution design targets waiting and batching efficiency without requiring shorter reasoning paths. Local release changes waiting between independent subtrees, and shared batching improves model execution efficiency. Adopted SBE continuations are attached to their original logical paths, while unused speculation is discarded or canceled. The table also shows why candidate count must be reported separately: original BW returns more candidates at n=64 and fewer at n=256, so shorter returned paths do not imply a fixed proportional change in the number of candidates. Actual generation work and the effective length of final paths must therefore remain distinct.

W2 / Q2

Independent subtree coroutines with continuous batching are the appropriate direct baseline for assessing BW's additional contribution. We agree that vLLM's asynchronous engine can combine in-flight generation requests from different subtrees and depths; immediate submission therefore does not inherently produce small batches.

BW additionally coordinates how the generator and PRM receive service on the shared GPU. Continuous batching determines how admitted requests execute within an engine, but does not by itself specify the service policy between the two models. For example, when one subtree has prefixes awaiting scoring while others are still decoding, the remaining decisions include whether to continue generation or serve a PRM batch that can unlock subsequent work, how long to accumulate that batch, and how much additional live KV state to admit. BW coordinates these decisions through separate ready queues, bounded execution windows for each model, scoring-backlog and waiting-time triggers, and batch/KV admission limits. It also maintains the logical ownership of saved KV state and speculative continuations, allowing them to be resumed or canceled according to the corresponding selection. This design integrates search dependencies, model-service allocation, and state management while retaining continuous batching.

BW retains additional gains over this asynchronous baseline, with the magnitude depending on the model combination. In the Async baseline, each DVTS subtree runs as an independent coroutine over the stock vLLM AsyncLLMEngine, while a shared PRM queue batches scoring requests across subtrees. Each subtree advances once its own sibling-group scores have returned. The comparison uses the same questions, model configurations, and search budgets. Times below are arithmetic means in seconds per query; time ratios are geometric means of per-question TAsync/TBWT_{\mathrm{Async}}/T_{\mathrm{BW}} ratios. Quality entries report Top-1/Top-N (%).

nnConfiguration (generator + PRM)Mean time (s), Async/BWAsync/BW time ratioAsync qualityBW quality
641.5B + 1.5B32.32/20.921.568×63.8/81.961.7/83.0
647B + 1.5B69.86/63.731.127×64.9/84.064.9/81.9
641.5B + 7B58.26/54.311.072×51.1/85.148.9/83.0
2561.5B + 1.5B84.07/64.481.337×66.0/86.262.8/87.2
2567B + 1.5B185.96/165.241.125×66.0/88.364.9/86.2
2561.5B + 7B202.68/197.391.021×46.8/87.241.5/89.4

The results identify operating points with additional latency gains and explicit quality–latency trade-offs. For 1.5B + 1.5B at n=64/256n=64/256, BW achieves 1.568×/1.337× wall-clock speedups over Async, with Top-1 differences of 2.1/3.2 percentage points and slightly higher Top-N. For 7B + 1.5B at n=64n=64, mean latency decreases from 69.86 to 63.73 seconds, with a paired geometric-mean speedup of 1.127× and the same observed Top-1 of 64.9%. For PRM-heavy 1.5B + 7B, the gains narrow to 1.072×/1.021×: when the required scoring dominates execution time, earlier generation has less scope to improve end-to-end latency. These results show an additional system-level benefit over the tested coroutine-based implementation, with configuration-dependent quality–latency trade-offs.

Thank you for the detailed response. The async baseline and Top-1 / Top-N numbers are helpful. The time ratio is much smaller compared to Async than the improvement over FastTTS in the paper. I recommend the contribution to be restated relative to Async.

Follow-up questions:

  1. Accuracy: BW's Top-1 is consistently lower than Async in 5 out of 6 settings, is the gap caused by noise? The paper states that the generator, PRM, and search objective are unchanged, so I expect the accuracy to be unchanged.

  2. Shorter returned paths: Thank you for clarifying the effective token question. However, I believe the readers would appreciate it if the cause of the shorter returned paths of BW could be explained more here.

I would raise the rating if

  1. The top-1 gap is shown to be within noise from random seeds, or it can be shown that BW is faster than Async at equal accuracy (for example, through accuracy–latency curves over n)).

  2. The contribution paragraphs are restated to include the Async baseline.

Reviewer_YzkPOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes BranchWeave, a runtime scheduler for verifier-guided test-time search. In existing runtimes, a subtree that has finished must wait for unrelated subtrees in global depth rounds. This paper separates the dependency scope of the search from the batching scope of model execution. It groups candidates into selection domains by reducer dependency. Once a domain receives all of its PRM scores, it moves to the next depth without waiting for other domains. Meanwhile, ready generator calls and ready PRM calls from all domains and depths go into two shared queues. Each queue forms a batch using an admission threshold and a waiting bound, so batches stay large without holding back ready domains. A stable node identity keeps seeds, tie-breaking, KV state and speculative continuations attached to their owners, so reordering does not change reducer decisions for fixed scores. The experiments use Qwen2.5-Math generators with 1.5B/7B PRMs on one RTX 4090 D, and report that E2E latency drops by 1.62-2.24x against FastTTS.

Critical strengths
  1. The core idea is simple and well motivated. The paper separates the dependency scope of the search from the batching scope of model execution, without changing the generator, the PRM or the search objective. The T_round vs. T_wave analysis shows exactly when the gain exists: only when the slowest domain changes across depths. The authors measure that this happens at 90.4% of adjacent depths, so the opportunity is real. The stable node identity is also a careful design, because it lets BranchWeave reuse FastTTS's speculation and prefix reuse instead of replacing them. From an AI infra view, this removes a barrier that comes from the search controller, not from the serving engine.

  2. The experiments isolate the scheduling effect well. The fixed-work replay changes only release and batching, and the barrier share drops from 42.9% to 0.025% (Figure 2). The ablation removes each part in turn: without the local wavefront, E2E time rises to 1.47-1.53x (Figure 5). The single-domain case, where no gain is expected, shows only 1.002x (Table 5), so the implementation adds little overhead. These controls convince me that the mechanism itself works.

Critical weaknesses

The scope and the costs are not discussed, so I cannot tell where the method applies. Advancing independent subtrees asynchronously is not new (e.g., asynchronous parallel MCTS), and there is no silver bullet: the method adds controller complexity, and its gain depends on the deployment. All results are on one RTX 4090 D. The paper does not discuss: (a) the KV-cache and model-residency pressure when more requests are active at different search depths (the paper notes that local progress raises the number of active generation requests); (b) multi-GPU settings, where tensor parallelism adds cross-GPU communication at every decode step, and data parallelism must trade KV locality against load balance across replicas; (c) shared servers, where continuous batching in vLLM or SGLang already fills barrier time with other users' requests, and pooling across users would need cache and batch isolation; (d) the sensitivity to the admission threshold and the waiting bound (Table 4 shows a non-default setting is 1.093x faster). So I see BranchWeave as a good solution for single-GPU or edge deployment, but I am not sure it is a scaling solution.

Questions for authors

Clarifications that could change my assessment:

  1. Scope: is BranchWeave intended only for a single GPU (e.g., personal or edge deployment), or also for multi-GPU platforms? Please state the target use cases, and the conditions under which it does not help or becomes slower.
  2. What does BranchWeave add over a simple asynchronous controller on an existing engine, e.g., each subtree submitting its own calls to vLLM's async engine, or SGLang's forked calls? Is LocalImmediate built on vLLM's continuous batching?
  3. How do KV usage, preemption and recomputation change compared with global rounds, especially at large n?
  4. What is the final-answer accuracy of each system in the natural search at the same n? How often does rebatching change a reducer's top-k choice, and what value of ε_tie do you use?
  5. Where do 5.46x and 4.94x come from (dataset, n, baseline, metric)? Please report MATH-500, or remove it from the workload list.
  6. An experiment with concurrent requests, and one on multiple GPUs, would show whether the gain remains beyond single-request, single-GPU use.
  7. A short glossary or one worked example would make Section 3 easier to follow; the paper introduces many new terms (wavefront, epoch, domain, reducer).
7 comments

We thank the reviewer for their careful review and comments on controller costs, deployment requirements, resource behavior, and applicability. We have revised the paper in light of this feedback.

Q1 / W

BranchWeave(BW) benefits when independent progress exposes work that the available serving capacity can execute efficiently. Our primary target is single-GPU verifier-guided search under memory and compute constraints, while model serving can also extend to multiple GPUs. BW reduces waiting between unrelated subtrees when independent selections become ready at different times and can release subsequent work early. Gains can be smaller in two main cases:

  • PRM-heavy workloads where scoring dominates execution time. Local progress releases generation earlier, but candidate-prefix scoring is still required. When scoring accounts for most execution time, reduced generation-side waiting translates into smaller overall gains. A stronger generator paired with a lightweight PRM offers a deployment choice that balances generation capacity and scoring cost. For a heavier PRM, prefix-length batching, adaptive generator/PRM service allocation, and PRM prefix-state reuse are optimization directions that can complement BW.
  • Larger searches with limited KV capacity. Early task release can increase simultaneously resident path state. If additional preemption, recomputation, or service switching offsets the saved waiting time, gains narrow. KV-aware admission, adaptive in-flight request limits, and speculative-cache retention and reclamation policies can improve the balance between parallelism and cache pressure.

The effective operating range is governed by removable waiting, scoring cost, and memory pressure. Adaptive optimization for scoring efficiency and KV management is meaningful future work that can broaden BW's deployment range while preserving its domain-local release rules.

Deployment requires explicit search dependencies, request identifiers, and model/KV memory budgets. The search adapter must supply expansion, scoring, selection, and stopping rules and identify which mutable states can advance independently; the current implementation explicitly supports DVTS and global beam search. The inference backend must provide generation and scoring interfaces with request identifiers. A single-GPU deployment must also budget memory for the generator, PRM, runtime caches, and active-path KV state, with limits on in-flight requests and scoring batches. In the paper's configuration without offloading, both models remain resident in GPU memory and take turns receiving service; switching epochs does not repeatedly reload model weights.

Q2 / W

BW's controller coordinates independent search decisions with shared generator and PRM service. Independent subtree coroutines and continuous batching already enable asynchronous progress. BranchWeave additionally tracks each domain's selection requirements centrally, places released calls into two shared queues, and schedules service to balance batching efficiency against the wait for scores. It also maintains domain state and manages the lifecycle of speculative state as requests move through this process.

The additional cost comes from maintaining per-domain and per-request state and coordinating admission. This includes each domain's frontier and outstanding-result set, mappings between logical nodes and requests, two ready queues, and state updates, continuation resumption, and cancellation when scores return. Batch admission also involves grouping, sorting, and capacity checks. These operations add host-side overhead, with metadata growing with the numbers of domains, logical nodes, and queued calls. Device-side costs arise from batching delays, generator/PRM service allocation, and the KV state of potentially more simultaneously active paths.

LocalImmediate retains vLLM continuous batching. Its controller caps each admission of new generation requests at the beam width, draws PRM tasks from one domain at a time, and prioritizes ready scoring tasks.

Q3 / W(a)

BW accommodates larger search budgets within a fixed generator KV allocation, with preemption behavior depending on the workload. We compare resource measurements for vLLM-Sync, FastTTS, and BW below. Entries for each system report “mean generator KV blocks / mean preemptions per query.” Coordination time reports the coordination overhead recorded by the BW runtime.

nConfiguration (generator + PRM)Generator resources: mean KV blocks / mean preemptions per query / vLLM-SyncGenerator resources: mean KV blocks / mean preemptions per query / FastTTSGenerator resources: mean KV blocks / mean preemptions per query / BWBW coordination (s/query)
641.5B + 1.5B3591/0.003591/0.003585/0.002.787
647B + 1.5B1690.2/13.452244/4.622234/2.413.315
641.5B + 7B5243/0.005243/0.005236/0.002.476
2561.5B + 1.5B3591/1.383591/0.513585/34.0112.210
2567B + 1.5B1690.2/143.622244/187.372234/140.3114.257
2561.5B + 7B5243/0.645243/0.065236/1.1710.505

BW's allocated generator KV capacity remains unchanged as the search budget grows from n=64 to 256. The three model combinations retain 3585, 2234, and 5236 blocks, respectively, showing that local progress can organize more search work within a fixed KV capacity. No generator preemptions were recorded for 1.5B + 1.5B or 1.5B + 7B at n=64. For 7B + 1.5B, BW records fewer preemptions than FastTTS at both budgets: 2.41 versus 4.62 at n=64 and 140.31 versus 187.37 at n=256, with comparable allocated KV capacity. At larger budgets, more active paths can still raise cache pressure within that allocation, making KV-aware admission and speculative-state retention relevant to the concurrency–memory trade-off.

Q4

Candidate coverage and final-answer accuracy reveal different aspects of BW's time–quality trade-off. Quality entries below are Top-1/Top-N (%): Top-1 measures the correctness of the final PRM-selected answer, while Top-N measures whether the returned candidate set contains a correct answer. Times are in seconds, and time ratios are geometric means of per-question Async/BW ratios.

nConfiguration (generator + PRM)Mean s/query, Async/BWAsync/BW time ratiovLLM-SyncFastTTSAsyncBW
641.5B + 1.5B32.32/20.921.568×63.8/81.960.6/83.063.8/81.961.7/83.0
647B + 1.5B69.86/63.731.127×66.0/84.064.9/76.664.9/84.064.9/81.9
641.5B + 7B58.26/54.311.072×46.8/85.152.1/83.051.1/85.148.9/83.0
2561.5B + 1.5B84.07/64.481.337×64.9/87.267.0/85.166.0/86.262.8/87.2
2567B + 1.5B185.96/165.241.125×66.0/85.167.0/87.266.0/88.364.9/86.2
2561.5B + 7B202.68/197.391.021×42.6/88.344.7/87.246.8/87.241.5/89.4

The quality results identify useful operating points while distinguishing candidate coverage from final selection. For 7B + 1.5B at n=64, BW and Async both achieve 64.9% Top-1, with a 1.127× time ratio. For 1.5B + 1.5B at n=256, BW raises Top-N from 86.2% to 87.2% with a 1.337× speedup and a 3.2-point Top-1 difference. Higher coverage provides more opportunity for a correct final answer, but realizing it also depends on candidate ranking. This motivates optimizing scoring efficiency and final selection together.

In a controlled comparison on fixed candidate sets, approximately 98% of local reducer choices agree across different batching schedules. On AIME with a 7B generator and a 1.5B PRM, we recompute local choices offline by applying the PRM scores actually computed during GlobalRound and BW execution to identical saved candidate groups. Under the DVTS local selection rule (one parent per group, i.e., k=1k=1, with ϵtie=0.01\epsilon_{\mathrm{tie}}=0.01), choices differ in 74/3,738 decisions (1.98%) at n=64n=64 and 311/14,977 decisions (2.08%) at n=256n=256, counting parent-selection decisions with at least two eligible candidates. In 365 of the 385 differences, the strict argmax choice is unchanged; the difference arises when candidates enter or leave the ϵ\epsilon-tie set, changing the outcome of logical node ID tie-breaking. Thus, the differences primarily involve the near-tie boundary.

εtie\varepsilon_{\mathrm{tie}} defines deterministic handling of near-tied domain-local scores. The domain-local DVTS reducer uses εtie\varepsilon_{\mathrm{tie}}=0.01 in aggregate-score units: among active candidates whose scores are within this threshold of the highest score, it selects the one with the smallest canonical logical node ID. This is an approximate-tie rule, not an upper bound on numerical error caused by changing batches. The threshold applies to domain-local reduction; final-answer formatting uses its own candidate-ranking rule.

Q5

The 5.46× and 4.94× figures are two different metrics from the same historical setting. The setting is AIME2024, 7B + 1.5B, n=256, beam width 4, and at most 10 steps, with vLLM-Sync as the baseline. The 5.46× figure is the geometric mean of per-question wall-clock time ratios; 4.94× is the geometric mean of Goodput ratios, where Goodput is the mean effective tokens per returned candidate divided by the combined generator and PRM model time.

MATH also shows lower search latency together with higher Goodput. Results for 7B + 1.5B at n=16/64/256 are reported below.

SystemE2E (s)E2E speedupWall (s)Gen. (s)PRM (s)GP (tok/s)GP gainPGP (tok/s)
vLLM-Sync70.941.334×71.3464.645.4711.491.175×14.58
FastTTS78.361.492×79.5273.544.1510.601.258×13.27
BW48.461.000×51.9543.394.4313.401.000×18.35

The MATH gain is concentrated in the dominant generation stage. Relative to FastTTS, mean generator time falls from 73.54 to 43.39 seconds, while PRM time changes from 4.15 to 4.43 seconds. The generation reduction outweighs the scoring increase, consistent with the reported 1.492× E2E speedup and 1.258× GP gain. This supports the generator-heavy operating choice: reducing the dominant cost can improve overall execution even when every stage does not accelerate.

Q6 / W(b) / W(c)

BW retains latency benefits in the tested TP2 and shared-service settings. The two-GPU experiments use TP=2 for both models. In single-GPU shared serving, multiple queries use the same generator and PRM, with C=1, 2, or 4 active queries; a completed query is replaced by the next query. These settings examine model parallelism and request concurrency, respectively.

The table reports mean time in seconds per query and the geometric mean of per-question Async/BW time ratios.

DeploymentConfiguration (generator + PRM)nCMean time (s/query), Async/BWAsync/BW time ratio
Two GPUs, TP=27B + 1.5B64184.94/46.091.812×
Two GPUs, TP=27B + 1.5B2561279.12/138.972.038×
Single GPU, shared service7B + 1.5B64179.78/56.791.378×
Single GPU, shared service7B + 1.5B642111.15/74.951.462×
Single GPU, shared service7B + 1.5B644227.12/123.691.847×
Single GPU, shared service1.5B + 7B64161.34/55.901.096×
Single GPU, shared service1.5B + 7B642106.53/101.501.093×
Single GPU, shared service1.5B + 7B644202.49/200.751.024×

The results show that additional serving capacity and request concurrency leave room for coordinated search execution. Under TP2, BW achieves 1.812×/2.038× time ratios at n=64/256, consistent with domain-level scheduling remaining useful when model calls are parallelized across GPUs. In shared serving, 7B + 1.5B retains 1.378×–1.847× gains, whereas 1.5B + 7B approaches parity as C grows. Other queries can supply generation work without removing each query's dependence on its own scores. Coordinating generator and PRM service can therefore remain useful, with the model-pair contrast indicating greater headroom when generation is substantial. These results support deployment beyond a single isolated query within the tested range.

Reviewer_hFC2OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In verifier-guided search (generator + PRM), existing runtimes advance all subtrees in global depth rounds, so a finished subtree waits for the slowest one. For root-parallel search like DVTS, where each subtree selects independently, BranchWeave lets each subtree advance as soon as its own siblings are scored, and pools ready generator / PRM calls across subtrees and depths into shared batches. On an RTX 4090 with Qwen2.5-Math 1.5B/7B generators and 1.5B/7B PRMs, it reports 1.7-2.1x faster search than FastTTS and up to 5.46x faster than a vLLM baseline.

Critical strengths
  • Clear and well-motivated observation: for root-parallel search like DVTS, the global depth barrier is unnecessary, and since the slowest subtree changes across depths (90% of the time), the waits can be long. The analysis of when local progress helps (changing stragglers, service-time variation) is clean.
  • Strong speedups: 1.7-2.1x over FastTTS (a strong specialized baseline) and up to 5.46x over vLLM, with matching gains in wall time, energy, and goodput, and consistent across seeds.
  • Careful evaluation that isolates the scheduling effect: fixed-work replay, ablations of each component (local release, cross-domain pooling, cross-depth admission), sensitivity to batching thresholds, and a check that candidate lists and final answers are unchanged under reordering.
Critical weaknesses
  • No accuracy results. Natural search can generate different paths (Table 2: 0.80-0.90x generated tokens), so it would be good to report accuracy on AIME / AMC / MATH-500 to confirm search quality is the same.
  • Limited setting: one consumer GPU, 1.5B / 7B models, DVTS only. Gains are smaller when the PRM is the bottleneck (1.5B+7B).
  • Writing is heavy on jargon (selection domains, local wavefronts, epochs, reducers) and formalism for a fairly simple idea. A concrete example and a plain description of the scheduler would make it easier to follow.
Questions for authors
  • How does BranchWeave compare to DVTS written as independent async requests on vLLM / SGLang with continuous batching? Does "LocalImmediate" use continuous batching?
  • What is the accuracy of each system on the benchmarks?
4 comments

We thank the reviewer for their careful review and comments on search quality, asynchronous baselines, and the presentation of the paper. We have revised the paper in light of this feedback.

W1 / Q1 / Q2

BranchWeave(BW) provides additional latency gains over asynchronous continuous batching, with useful accuracy–latency trade-offs. We compare the same questions, model configurations, and search budgets. Async implements each DVTS subtree as an independent coroutine, uses the native vLLM AsyncLLMEngine for continuous batching of generation, and shares a PRM queue across subtrees. Each domain advances once the scores of its four sibling candidates have returned. Results are shown below; quality entries are Top-1/Top-N (%), and times are in seconds.

nConfiguration (generator + PRM)Mean s/query, Async/BWAsync/BW time ratiovLLM-SyncFastTTSAsyncBW
641.5B + 1.5B32.32/20.921.568×63.8/81.960.6/83.063.8/81.961.7/83.0
647B + 1.5B69.86/63.731.127×66.0/84.064.9/76.664.9/84.064.9/81.9
641.5B + 7B58.26/54.311.072×46.8/85.152.1/83.051.1/85.148.9/83.0
2561.5B + 1.5B84.07/64.481.337×64.9/87.267.0/85.166.0/86.262.8/87.2
2567B + 1.5B185.96/165.241.125×66.0/85.167.0/87.266.0/88.364.9/86.2
2561.5B + 7B202.68/197.391.021×42.6/88.344.7/87.246.8/87.241.5/89.4
  • BW's gains extend beyond independent subtree execution and continuous batching. Async already provides both, together with shared PRM batching. BW additionally coordinates admission and generator/PRM service across the device. The remaining latency advantage indicates that independent subtree progress still leaves opportunities to improve how released work receives service.
  • Favorable operating points offer more pronounced latency gains with limited changes in quality. For 1.5B + 1.5B at n=64/256, the Top-1 differences are approximately 2.1/3.2 percentage points, alongside 1.568×/1.337× speedups and slightly higher Top-N in both cases. For 7B + 1.5B at n=64, BW achieves a 1.127× speedup with the same Top-1 of 64.9%. These results help select configurations according to latency and quality requirements. For 1.5B + 7B at n=256, the Top-1 difference is 5.3 percentage points, while Top-N increases from 87.2% to 89.4%. This distinction matters because coverage measures whether a correct candidate is available, while Top-1 also depends on final ranking. Further optimization can therefore address both scoring efficiency and the conversion of candidate coverage into correct final predictions.

Yes, LocalImmediate retains vLLM continuous batching. At each admission, the controller adds no more generation requests than the beam width, and each PRM admission draws tasks from only one selection domain.

W2

BW's scheduling design is compatible with TP2, while its primary target remains single-GPU serving under compute and memory constraints. In the main setting, the generator and PRM share a single GPU. We also conducted experiments with 7B + 1.5B on two GPUs, using TP=2 for both models while retaining domain-level progress, shared model queues, and logical state ownership. The two-GPU results are reported separately below. Times are in seconds, and time ratios are geometric means of per-question Async/BW ratios.

nMean time (s), Async/BWAsync/BW time ratioTop-1 (%), Async/BWTop-N (%), Async/BW
6484.94/46.091.812×58.3/55.076.7/83.3
256279.12/138.972.038×50.0/33.383.3/83.3

The TP2 results show that the scheduling design remains useful when individual model calls span two GPUs. The observed time ratios are 1.812×/2.038× at n=64/256. Tensor parallelism determines how each call executes, whereas BW coordinates dependencies and service between calls, allowing the two mechanisms to operate together. The accompanying quality columns characterize the time–quality trade-off in this version; together, the results support the feasibility of extending BW to model serving on multiple GPUs.

Smaller gains in PRM-heavy settings reflect the trade-off among generation quality, scoring capacity, and serving cost. For 1.5B + 7B, PRM calls account for approximately 70.7%/78.7% of the combined generator and PRM call time at n=64/256, respectively. Local progress can release subsequent generation earlier, but the prefix scoring required by the search rules must still be completed. When scoring dominates the critical path, generation-side savings have less scope to improve end-to-end latency, giving the observed 1.072×/1.021× gains. A stronger generator paired with a lightweight PRM offers another deployment option: 7B + 1.5B at n=64 achieves a speedup while maintaining relatively high final-answer accuracy, making it suitable when generation quality is a priority.

PRM-aware batching and cache management offer complementary ways to improve this trade-off. Grouping PRM inputs by prefix length, adapting service allocation to generation and scoring load, and improving PRM prefix-state reuse can all complement our scheduling mechanism. Larger search budgets also motivate improvements to KV-aware admission and speculative-cache retention. We hold serving parameters fixed across budgets within each model pair to expose behavior as search scale and bottlenecks change. Targeted engineering optimizations are meaningful future work that can broaden the effective operating range of different model combinations.

W3

BW lets each subtree wait for its own required scores while sharing model execution across subtrees. We consider verifier-guided tree search: the generator expands candidate reasoning paths, the PRM scores them, and the search algorithm selects paths for further expansion, repeating this process. In DVTS, a question has multiple independent subtrees, each making selections from its own candidate scores. If all subtrees must finish the current depth before any can advance, slower subtrees also block those already ready to select. BranchWeave therefore handles “which subtrees can continue” separately from “which model calls can execute together.”

The terminology in the paper refers to concrete objects and operations in this process:

  1. Selection domain: The candidates, scores, and mutable state that a selection must consider together. Each independent DVTS subtree forms a selection domain and must wait for all scores required by its current selection.
  2. Reducer: The rule that uses these scores to decide which candidates continue. For example, a DVTS subtree selects the path to expand next from its current candidates.
  3. Local wavefront: Once a domain has received all required scores and completed selection, it can release its next tasks while other domains remain at earlier depths. Each domain thus advances at its own pace.
  4. Epoch: A bounded period of generator or PRM execution. The scheduler draws ready calls from the corresponding shared queue and executes them within batch and KV-capacity limits. One epoch can include calls from different domains and depths, so it does not require all subtrees to reach the same search depth.
  5. Logical node ID: A stable identifier for a path node that associates sampling streams, returned scores, KV state, and speculative continuations with their original node even when calls move between batches.

Figure 1 illustrates independent progress without weakening the requirement for complete sibling scores. A, B, and C are three selection domains. All scores for A, (0.2, 0.8, 0.4, 0.1), and C, (0.5, 0.2, 0.9, 0.4), have returned, while B still lacks one score. A and C can therefore run their reducers, select the second and third candidates, respectively, and release their next generation tasks, forming their own local wavefronts. Their ready tasks can enter the same generator epoch while B continues waiting for its required score.

Figure 3 implements this idea through a repeated queue–execute–reduce cycle. Newly released generation tasks enter QG; generated paths requiring scoring enter QV. The scheduler chooses which model to serve, pools ready calls from multiple domains within capacity limits, and bounds the wait for batching. Results return to their owning domains through logical node IDs. Whenever a domain has all required scores, it runs its reducer and enqueues subsequent tasks. The scheduler repeatedly cycles through “check score readiness—select and release tasks—execute shared model calls—return results to their owning nodes.”

Dear Reviewer hFC2,

Thank you again for your review. Our responses are posted above. W1/Q1/Q2 reports Top-1/Top-N results alongside latency, with a direct comparison against independent DVTS coroutines using vLLM continuous batching and a shared PRM batcher. We also clarify that LocalImmediate retains continuous batching. W2 reports two-GPU experiments and discusses the smaller gains in PRM-heavy settings; W3 provides a glossary and a worked example.

Could you let us know whether these additions address your concerns, or which points remain open? We remain available to answer any further questions during the discussion. If your concerns are resolved, we would be grateful if you could reflect this in your assessment.

Best regards,

The authors

Comments on the paper

2 comments

Hi Reviewers,

The authors have provided responses. Please check if they have addressed your concerns.

Thanks, AC

AuthorsOpenReview ↗

Summary of the discussion and the revision

Dear Area Chair,

Thank you for handling our submission. We also thank the reviewers for their careful reading and constructive suggestions, which helped us strengthen the evaluation and clarify BranchWeave's contribution and scope. As the discussion period draws to a close, we would like to summarize the reviews and the evidence we added in response.

All five reviewers gave BranchWeave a positive recommendation. The reviews recognized the value of separating the dependency scope of search from the batching scope of model execution. They also highlighted the practical speedups and the design of the fixed-work replay and ablation experiments. Across three generator-PRM pairs and five reasoning benchmarks, BranchWeave achieves search speedups of up to 2.42× over FastTTS and up to 1.57× over Async, an asynchronous baseline with continuous batching.

The main concerns fell into four groups.

  1. Asynchronous baseline and additional contribution (hFC2, YzkP, PG9G, mncR). The reviewers requested a comparison with independent subtree coroutines using continuous batching to assess BranchWeave's additional benefit.

  2. Search quality and actual work performed (hFC2, YzkP, PG9G). The reviewers requested accuracy, candidate coverage and workload metrics, along with an explanation of the shorter returned paths.

  3. Deployment costs and scaling (hFC2, YzkP, mncR, QjCn). The reviewers asked about KV and controller overhead, PRM bottlenecks, and performance with multiple GPUs and concurrent queries.

  4. Related work and scope (mncR, QjCn, hFC2, YzkP). The reviewers requested comparisons with related systems, a clear statement of the limitations for globally coupled search, and a simpler explanation of the method.

We addressed the reviewers' main concerns through additional experiments, measurements and clarifications.

  1. Added a direct asynchronous baseline and clarified the additional contribution. We added Async, which runs each subtree as an independent coroutine, uses vLLM continuous batching for generation, and batches PRM requests through a shared queue. We clarified BranchWeave's additional coordination of generator and PRM service. Following the reviewers' suggestions, the abstract and main contributions now include results relative to Async and state that the gains depend on the model configuration. Reviewer YzkP noted that these clarifications resolved their main confusion about the source of the gains.

  2. Added evidence on search quality and work performed. We reported Top-1, Top-N, effective token counts and returned candidate counts, and compared quality and latency across multiple random seeds and search budgets. With a 7B generator and a 1.5B PRM at n=64, the two systems achieve the same observed Top-1 accuracy in each of the three paired seed comparisons, while BranchWeave reduces mean latency by approximately 9% to 16%. We also clarified the distinction between returned-path length and actual model execution work, and reported quality and latency trade-offs in other configurations. Reviewer PG9G confirmed that the new results addressed their main concern.

  3. Measured deployment costs and extended the evaluation. We reported KV allocation, preemptions and coordination overhead, together with two-GPU and concurrent-query experiments. With a 7B generator and a 1.5B PRM serving four concurrent queries at n=64, BranchWeave achieves a 1.85× speedup over Async. We also explained why gains narrow in PRM-heavy settings and how the batching parameters were chosen.

  4. Added related-work comparisons and clarified the scope. We added conceptual and experimental comparisons with DPTS, TreeThink and SPEX. For example, with a 1.5B generator and a 1.5B PRM at n=64, BranchWeave achieves a 1.86× speedup over SPEX with higher Top-1 and Top-N. We also clarified the limitations for globally coupled search and provided a glossary and a worked example. Reviewer mncR acknowledged these additions. Reviewer QjCn confirmed that the SPEX comparison and multi-query results addressed their main questions, and appreciated the clear discussion of the limitations for REBASE and MCTS.

We believe the positive recommendations from all five reviewers, together with the additional experiments and clarifications, strengthen the case for accepting BranchWeave. We thank the reviewers and the Area Chair again for their time and careful consideration.

Best regards,

Authors of Submission 32342

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.