acceptodds
Under review as a conference paper at ICLR 2027

PluralGen: Efficient Test-Time Scaling by Decoupling Particle Search from Model Execution

Abstract

Particle search gives compact language models a way to improve reasoning at test time when deployment constraints rule out a larger model. Resampling directs a fixed population toward promising paths but often leaves many particles at the same complete state. Sequence runtimes nevertheless decode every particle separately. Prefix-aware KV sharing preserves inherited history but repeats the current Transformer pass and vocabulary projection, so execution remains proportional to particle count even as the search concentrates. We present PluralGen, which keeps particles as the unit of search while advancing each distinct complete state once. It stores each repeated state with its multiplicity, draws an independent continuation for every particle, and carries the grouping through model execution, resampling, and KV ownership. PluralGen reaches 3.2× end-to-end speedup, reduces KV allocation by 88.1%, supports 4× larger populations, and improves serving throughput by 2.9× on the evaluated workloads.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
test-time scaling, particle-based inference, resampling, state reuse, LLM serving

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_McexOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This work introduces PluralGen, an inference framework that eliminates redundant model execution in Sequential Monte Carlo (SMC) LLM reasoning, by grouping particles at identical complete states and evaluating each distinct state once per decode step. using a multiplicity-aware density head (MDH) and grouped-state runtime, PluralGen achieves up to a 3.2× speedup, an 88.1% reduction in KV cache allocation, and 2.9× higher serving throughput compared to SGLang baselines.

Critical strengths
  1. novel execution-search decoupling. PluralGen eliminates hidden compute waste by removing duplicate Transformer passes, and vocabulary projections for identical particle states that persist after resampling.
  2. particle semantics with grouped representation. PluralGen maintains exact statistical equivalence with standard sequence-wise SMC without expanding execution rows.
  3. multiplicity-aware density head dynamically switches between dense and counted block projections, which scales vocabulary computation with distinct occupied states, rather than nominal particle counts.
Critical weaknesses
  1. performance limits under specific conditions. speedups diminish under low state concentration or small populations (N≤32N \le 32), and are bounded by long prompt pre-fill times because PluralGen strictly optimizes the decoding phase.
  2. the proposed technique strictly optimizes the decoding phase. As demonstrated in the paper's sensitivity analysis, for tasks with long prompt pre-fills, the end-to-end latency gains degrade because the fixed pre-fill time bounds overall speedup (Amdahl’s law).
Questions for authors
  1. What is the precise control overhead of group management when distinct-state ratios are high (ρt≈1\rho_t \approx 1), and how does PluralGen perform under high-temperature settings with minimal particle collisions?
  2. How do dynamic state counts and batching mechanisms interact with communication overheads in multi-GPU or distributed serving environments?
3 comments

We appreciate the reviewer's questions about applicability, runtime overhead, and multi-GPU communication. And we have revised the paper in light of this feedback.

W1 / Q1.

  • PluralGen still delivers end-to-end speedups at high temperatures, even when reuse is minimal. ASMC and Power-SMC use sharpened proposals and resampling to allocate more computation to high-weight trajectories, so several particles continue from the same state. The baseline already shares inherited KV state. PluralGen also shares these particles' current model evaluation while preserving independent draws, which gives larger gains under the original search settings. Higher temperatures flatten the proposal and make particles diverge faster, reducing the computation that can be shared. The table compares the original settings with a proposal temperature of 1.75 on the 1.5B model, where ρ=U/N\rho=U/N is the distinct-state ratio. Even when ρ\rho reaches 98.1%, PluralGen retains a 1.08× speedup.

    MethodNNDefault ρ\rho (%)Default speedupHigh-temperature ρ\rho (%)High-temperature speedup
    ASMC12821.01.39×86.31.14×
    Power-SMC12837.91.28×98.11.08×
    ASMC25616.01.96×80.71.20×
    Power-SMC25633.11.69×95.71.10×
  • Group management has a control cost comparable to that of the sequence-wise baseline. PluralGen maintains offspring through member indices, counts, and KV references, avoiding copies of entire sequences and KV histories when multiplicities change. The table reports exclusive CPU time for Power-SMC at N=128N=128, τ=2\tau=2, and ρ=98.36%\rho=98.36\%, directly comparing management costs when reuse is minimal. Including synchronization and control work common to both systems, the full control stage takes 7.908 ms/step for the baseline and 7.595 ms/step for PluralGen. These totals are measured separately from the exclusive component times below.

    Control componentBaseline (ms/step)PluralGen (ms/step)
    Canonical ordering0.05350.1076
    KV ownership maintenance0.56420.5171
    Resampling state mapping0.02190.0052
    State mapping and scheduling0.13070.1266
    Total0.77030.7565
  • Serving throughput still improves substantially at small particle counts. When a request contains less redundant computation, its latency improvement is smaller, but the saved execution rows and KV space remain available to concurrent requests. In Table 2 of the submission, ASMC achieves 1.68–1.75× higher throughput at N=32N=32 and concurrency 16. Scheduling by occupied states therefore still improves serving capacity when each request has a small particle budget.

W1 / W2.

  • Reducing redundant decoding still gives clear end-to-end speedups with long prompts. Longer inputs increase pre-fill cost, while particle search also requires continued generation across multiple candidates. Prefix caching reuses prompt KV history, and PluralGen continues to share model execution for identical states after resampling. These savings accumulate during decoding. The table gives the breakdown for 1.5B ASMC at N=256N=256. Inputs of about 2K and 3K tokens yield 1.94× and 2.25× speedups, with most savings coming from subsequent decoding. Paired times are ordered as baseline / PluralGen. The first step includes pre-fill, head execution, and control work.

    Input tokensFirst step (s)Subsequent decoding (s)Full request (s)Speedup
    35–1500.031 / 0.0168.018 / 6.1158.089 / 6.1531.31×
    2,050–2,1970.110 / 0.05411.279 / 5.80811.426 / 5.8821.94×
    3,074–3,1490.141 / 0.0829.031 / 3.9999.218 / 4.0942.25×
  • Pre-fill optimizations can be combined with PluralGen. For a fixed decoding workload, a larger shared pre-fill cost makes the saved decoding time a smaller fraction of total latency. This is the relationship described by Eq. (48) in Appendix B.2. Pre-fill optimization and shared decoding act on different phases of a request and can improve end-to-end latency together.

Q2.

  • PluralGen retains clear speedups after accounting for communication and synchronization. Tensor-parallel ranks use the same grouped batch width, and graph buckets accommodate shape changes as state counts vary. Both systems use the same head, graph, and communication settings. End-to-end time is measured as the completion time of the slower rank. Results on MATH500 with TP=2 are below.

    Model / MethodSpeedup at N=128N=128Speedup at N=256N=256
    1.5B / ASMC1.37×1.95×
    1.5B / Power-SMC1.78×2.10×
    7B / ASMC1.75×2.16×
    7B / Power-SMC1.37×1.47×
  • Fewer execution rows also reduce the size of collective input tensors. For example, with 7B ASMC at N=256N=256, both decode execution rows and the cumulative AllReduce input volume computed from those rows fall by about 85.7%, including graph padding. Shared states thus reduce model computation and the corresponding collective inputs. Communication still has fixed launch and synchronization costs, so end-to-end speedup does not scale directly with the reduction in execution rows. The grouped batches nevertheless deliver the gains reported above.

Thanks author(s) for supplying additional results and the elaboration.

The paper's main strengths are its efficient reuse of identical particle states, preservation of SMC sampling behaviour, and substantial reductions in computation and KV-cache memory.

The additional experiments addresses my main concerns about high-temperature sampling, group-management overhead, long prompts, and multi-GPU execution. The results are encouraging, although performance still depends on how often particles share states, and broader distributed scalability remains less established. I appreciate these efforts and think the original score reflects its standing.

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

The paper investigates the scenario that after resampling in particle search (ASMC, Power-SMC), many particles share an identical state. PluralGen groups them, runs the model once per distinct state while keeping independent random draws per particle, and adds a multiplicity-aware density head (MDH), grouped KV, and graph replay. Appendix A proves equivalence to the standard labeled process. On Qwen2.5-Math 1.5B/7B with one RTX 4090, it reports up to 3.2× speedup, 88.1% less KV memory, and 2.9× serving throughput over SGLang (Tables 1–2). The claims concern efficiency, not accuracy.

Critical strengths
  1. The paper presents a clean, well-defined idea. Sharing computation for identical states while keeping independent draws targets real redundancy, and the paper handles complete state, weights, and ESS carefully.

  2. The systems evidence and win is convincing. Savings track state concentration (ASMC > Power-SMC), ablations isolate components, the baseline already shares KV prefixes, and the repository is well pinned with SGLang, data hashes, different seeds.

Critical weaknesses
  1. The reproductivity of the paper is doubtful. The code may not match the resampling proof. Lemma 4 requires a canonical state order before systematic resampling, but runtime/scheduler.py resamples in the current group order, and the unit-multiplicity head path does not sort (paths under sglang_overlay/sglang/srt/pluralgen/). Order matters: for states A, B, A, B with weights .2, .3, .2, .3, A gets two offspring with probability .8 (else zero), versus .6 (else one) for A, A, B, B. I cannot tell from static inspection whether the results are affected.

  2. Based on the attached code, MDH's cost model does not match the kernel. folded_mass.py first projects the full vocabulary, then recomputes a tile per particle without merging duplicates, unlike Eq. 34 and Appendix B.1. Figure 6 compares against an expanded N-row head, not a grouped dense [U, V] head, so MDH's own benefit is not shown.

Questions for authors
  1. Where is canonical ordering enforced before resampling? Can authors add a test with interleaved duplicates?
  2. What do the repository's specialized vs. grouped-dense head benchmarks show, end to end?
  3. What match rates and accuracy differences did the validation code produce?
  4. Which horizon caps were used, with what truncation rates, and what absolute capacity and peak memory support the 4× capacity claim?
2 comments

We appreciate the reviewer's questions about resampling, MDH design, and the experimental setup. And we have revised the paper in light of this feedback.

W1 / Q1 / Q3.

  • Grouped and sequence-wise resampling produce the same offspring under a common canonical order. The reviewer's interleaved A/B example illustrates that systematic resampling is sensitive to particle order. This is why Lemma 4 requires both representations to use the same canonical order. In the updated implementation, we apply this ordering before constructing cumulative weights, using complete states and particle identifiers to define the probability intervals. The sequence-wise baseline and grouped execution use the same convention, including unit-multiplicity groups, active particles, and terminated particles. Resampling therefore does not depend on whether a head path sorts its outputs in advance.

    For interleaved A,B,A,BA,B,A,B, both representations first use the same order, A,A,B,BA,A,B,B. Given the same random offset, sequence-wise execution counts the systematic sampling points in the two A intervals separately, while grouped execution counts them in the merged interval. The number of offspring in state A is the same. Particle identifiers are retained to track the correspondence between offspring and parent states. We extended this comparison to unequal multiplicities, successive resampling steps, and populations containing both active and terminated states. Across these comparisons, offspring states, their associations with particle identifiers, and ESS agree with a sequence-wise reference using the same convention.

  • PluralGen accelerates execution while maintaining accuracy comparable to the baseline. On MATH500, we evaluate both models and both search methods at N=128/256N=128/256, with 200 problems per configuration. Both execution modes achieve an average accuracy of 77.4%, with per-configuration differences between −1.0 and +0.5 percentage points. Search budgets and resources are matched within each pair.

    Model / Method / NNBaseline accuracy (%)PluralGen accuracy (%)Difference (pp)Answer match rate (%)
    1.5B / ASMC / 12876.076.5+0.588.0
    1.5B / Power-SMC / 12871.071.00.082.0
    7B / ASMC / 12888.087.5−0.594.5
    7B / Power-SMC / 12877.578.0+0.589.0
    1.5B / ASMC / 25679.580.0+0.586.0
    1.5B / Power-SMC / 25664.063.0−1.078.5
    7B / ASMC / 25687.087.00.092.5
    7B / Power-SMC / 25676.076.00.091.0

W2 / Q2.

  • MDH further optimizes normalization and sampling in the grouped-dense setting. The grouped-dense head already projects the UU distinct states. MDH uses block statistics to retain normalization information, then performs conditional sampling for each particle and returns counted outputs. This reduces storage and memory traffic for the full logits matrix. A full-vocabulary scan computes the normalization statistics, followed by per-particle refinement of the selected tiles. Recomputation when particles select the same tile is also included in the complete head and request timings. Eq. (34) describes the volume of selected vocabulary regions. We have revised the paper to describe this occupancy analysis alongside the work performed by the kernel.

  • MDH provides further end-to-end speedups over the grouped-dense head. Figure 6 in the submission compares the shared head against an expanded NN-row head. In the MATH500 comparison at N=128N=128, we keep Transformer grouping and KV management unchanged and vary only the head implementation to isolate MDH's contribution within grouped execution. Dense denotes grouped-dense, and Auto selects an execution path based on the current shape. All speedups are relative to Dense. Latencies include mass computation, sampling, and merging throughout each request, with natural stopping enabled.

    Model / MethodDense (s)Specialized MDH (s)Auto (s)Speedup: Specialized / Auto
    1.5B / ASMC4.973.743.761.33× / 1.32×
    1.5B / Power-SMC5.194.053.951.28× / 1.31×
    7B / ASMC13.0710.5410.901.24× / 1.20×
    7B / Power-SMC11.749.529.001.23× / 1.31×

Q4.

  • The same KV budget supports larger particle populations by avoiding duplicate tails and execution states. The baseline already shares inherited prefix KV, but descendants at identical states still retain separate execution rows and subsequent KV tails. PluralGen represents these descendants with multiplicities and allocates new tails only when states diverge. In 7B ASMC tests with a fixed horizon of 1,024 tokens and the same 65,536-token KV budget, the baseline completed at most N=64N=64 on MATH500 and AIME, then ran out of memory at the next tested point, N=128N=128. PluralGen completed the largest tested population, N=256N=256, supporting the observed 4× capacity increase. Physical storage also decreases at the same particle count. For example, at N=128N=128, the mean peak physical KV allocation falls from 3.61 GiB to 1.63 GiB.

  • PluralGen and the baseline have similar truncation rates overall. The requested horizon caps are 2,048 tokens for GSM8K and GPQA, and 3,072 tokens for MATH500 and AIME. The total KV budget is capped at 600,000 token slots for 1.5B and 120,000 for 7B. The effective horizon is computed as H=min⁡{Hreq,C−L,⌊B−L−NN⌋}.H=\min\left\lbrace H_{\mathrm{req}}, C-L, \left\lfloor\frac{B-L-N}{N}\right\rfloor \right\rbrace.

    Here, HreqH_{\mathrm{req}} is the requested horizon, LL is the input length, CC is the context length, BB is the actual total KV budget, and NN is the particle count. We use 1-token KV pages and reserve one copy-on-write slot per particle, which accounts for the subtraction of NN. A request is counted as truncated if particles remain active when HH is reached. The table reports results at N=128N=128, pooling ASMC and Power-SMC. Paired values are ordered as baseline / PluralGen.

    DatasetHH (1.5B)HH (7B)Truncation rate (1.5B, %)Truncation rate (7B, %)
    GSM8K2,048935–9360.5 / 1.51.5 / 1.5
    MATH5003,072933–9363.0 / 1.513.5 / 12.5
    GPQA1,296 or 2,048914–93518.5 / 16.526.5 / 26.0
    AIME 20263,072933–93616.7 / 25.068.3 / 68.3
Reviewer_MTcEOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposed a method to store KV-ache when model does test-time scaling methods, ASMC and Power SMC. It shows a significant reduction of latency and KV allocation.

Critical strengths

The work directly alleviates the KV ache bottleneck in test-time scaling. It achieves 88.1% reduction in KV allocation and 3.2 times latency speedup. The system enables fitting up to 4 times larger particle populations on benchmarks like AIME 2026 and MATH500.

PluralGen creates a flexible interface based on its decomposition, allowing to integrate and accelerate new particle search methods as they evolve.

Critical weaknesses

The empirical evaluation is restricted to ASMC and Power-SMC. It does not provide the integration of proposed method to other testing time scaling method that includes lookahead, backtracking or verifier-guided tree search method (like MCTS), that currently dominate SOTA mathematical reasoning models.

The method depends on the ratio of Ut/NtU_t/N_t.

It is really poor presentation of the paper: one sentence for introduction of ASMC and Power-SMC, no definition for mathematical quantities used in the work. For example, in equation 5, what is qt(v∣zi)q_t(v|z_i), how to derive Δλt(v)\Delta \lambda_t(v) etc.

Questions for authors

No, I do not have any question.

1 comment

We thank the reviewer for the suggestions on the scope of the method and its mathematical presentation. And we have revised the paper in light of this feedback.

W1.

  • PluralGen also applies to lookahead, backtracking, and verifier-guided tree search. These methods change how candidates are generated, selected, and revisited, while the search algorithm maintains candidate identities, tree visit statistics, and value backups. When candidates share a complete model state, PluralGen can reuse the corresponding model evaluation. We evaluate this with PRM-guided Beam Search and PUCT MCTS. The generator is the 1.5B model used in the submission, and the PRM is Math-Shepherd-Mistral-7B. The table includes the full cost of generation, PRM scoring, and search control. Here, NN is the number of continuation candidates per round in Beam Search and per node expansion in MCTS. All other search control parameters are held fixed between the two systems.

    Search / NNBaseline (s)PluralGen (s)Speedup
    Beam + PRM / 1285.493.791.45×
    Beam + PRM / 2567.194.441.62×
    PUCT MCTS + PRM / 12843.5931.321.39×
    PUCT MCTS + PRM / 25656.4435.861.57×
  • PluralGen further accelerates search with caching and deduplication enabled. Both systems retain prefix KV caching, cached PRM scores, and deduplication within each call. PluralGen also preserves shared states across subsequent decoding steps while retaining candidate identities and independent draws. Caching reuses past results, and persistent grouping reduces the Transformer and vocabulary computation that would otherwise be repeated at the current step.

W2.

  • PluralGen still delivers end-to-end speedups at high temperatures, even when reuse is minimal. ASMC and Power-SMC use sharpened proposals and resampling to concentrate computation on promising trajectories, so the default settings provide more reuse and larger speedups. The high-temperature tests use flatter proposals, making shared states diverge faster than under the default search settings. U/NU/N reflects the redundancy present during this process, while PluralGen retains the original particle budget and independent draws. Even when higher temperatures bring U/NU/N close to 1, a modest end-to-end gain remains.

    MethodNNDefault ρ\rho (%)Default speedupHigh-temperature ρ\rho (%)High-temperature speedup
    ASMC12821.01.39×86.31.14×
    Power-SMC12837.91.28×98.11.08×
    ASMC25616.01.96×80.71.20×
    Power-SMC25633.11.69×95.71.10×

W3.

  • Eq. (5) defines the particle proposal, while ASMC and Power-SMC differ in their distributions and schedules. qt(v∣zi)q_t(v\mid z_i) is the next-token proposal distribution at state ziz_i, and pt(v∣zi)p_t(v\mid z_i) is the base-model distribution. The mixture weights πt,c\pi_{t,c} sum to 1, βt,c\beta_{t,c} is the component exponent, and ZβZ_\beta is the normalizing constant. ASMC mixes the base and sharpened distributions. Power-SMC uses a single-component power proposal and adjusts the proposal and target exponents as generation progresses. Both methods reallocate particles through weighting and resampling.

  • Eq. (6) follows directly from the importance-weight ratio between successive targets. Let γt(y≤t)=p(y≤t∣x)at\gamma_t(y_{\le t})=p(y_{\le t}\mid x)^{a_t} and Lt−1=log⁡p(y<t∣x)L_{t-1}=\log p(y_{<t}\mid x). Then

    \Delta\lambda_t &=\log\frac{\gamma_t(y_{\le t})} {\gamma_{t-1}(y_{<t})q_t(y_t\mid z_{t-1})}\\ &=(a_t-a_{t-1})L_{t-1} +a_t\log p_t(y_t\mid z_{t-1}) -\log q_t(y_t\mid z_{t-1}). \end{aligned} \notag$$ Here, $a_t$ is the target exponent. The first term accounts for its change over time, and the last two terms give the log density ratio between the target and proposal. We have improved the presentation of this part to make the method and equations easier to follow.

Comments on the paper

1 comment
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 PluralGen'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.

The main concerns fell into four groups.

  1. Particle semantics and experimental validation (giWV). The reviewer requested clarification of canonical ordering before systematic resampling, answer-quality validation, and the generation limits and absolute measurements supporting the capacity claims.
  2. MDH's additional contribution and cost analysis (giWV). The reviewer requested an end-to-end comparison with a grouped-dense head and clarification of how the vocabulary-block analysis relates to the implemented kernel.
  3. Applicability and deployment costs (Mcex, MTcE). The reviewers asked how gains depend on state concentration. Mcex also asked about group-management overhead, long prompts, small particle populations, and multi-GPU communication.
  4. Scope and mathematical presentation (MTcE). The reviewer requested evidence beyond ASMC and Power-SMC, together with clearer definitions of the proposal distribution and importance-weight update.

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

  1. Clarified resampling semantics and added answer-quality validation. Both execution modes enforce the same canonical state and particle-identifier order before constructing cumulative weights. Reference checks covering the reviewer's interleaved-duplicate example and additional resampling cases agree with a sequence-wise reference in offspring states, identifier assignments, and ESS. Paired MATH500 evaluation using 200 problems per configuration gives the same mean accuracy of 77.4% for both systems, with per-configuration differences within one percentage point. We also reported generation limits, truncation rates, and absolute capacity and physical KV measurements supporting the observed 4× increase in supported particle populations.

  2. Added a direct grouped-dense comparison and clarified MDH's additional contribution. We compared MDH against a grouped-dense [U,V][U,V] head while keeping Transformer grouping and KV management fixed. Adaptive MDH provides a further 1.20–1.32× end-to-end speedup. The grouped-dense head already removes duplicate projection rows, while MDH additionally reduces intermediate logits storage and traffic through block statistics and conditional sampling. We revised the cost analysis to describe the full-vocabulary scan and per-particle tile refinement, both of which are included in the reported timings.

  3. Measured runtime overhead and extended the evaluation. High-temperature runs retain end-to-end gains, including a 1.08× speedup when 98.1% of particle states are distinct. Group-management profiling shows control costs comparable to the sequence-wise baseline when reuse is minimal. For small particle populations, the serving results show that saved execution rows and KV space still benefit concurrent requests. Longer-prompt experiments with 1.5B ASMC yield 1.94–2.25× full-request speedups, while two-GPU tensor-parallel experiments achieve 1.37–2.16× speedups with communication and synchronization included.

  4. Added verifier-guided search experiments and improved the presentation. PRM-guided Beam Search and PUCT MCTS achieve 1.39–1.62× complete-search speedups, including generation, PRM scoring, and search control. Both systems retain prefix KV caching, cached PRM scores, and deduplication within each call. PluralGen additionally shares current generator execution across successive decoding steps, while candidate identities and tree statistics remain with the search controller. These results extend the empirical support beyond SMC. We also clarified the differences between ASMC and Power-SMC, defined the mathematical quantities, and explained the importance-weight update through the ratio of successive targets.

We believe the additional experiments and clarifications strengthen the case for accepting PluralGen. We thank the reviewers and the Area Chair again for their time and careful consideration.

Best regards,

Authors of Submission 23618

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.