PaperlayerView exact revision on arXiv

Source-linked AI summary

Multiverse: Your Language Models Secretly Decide How to Parallelize and Merge Generation

Xinyu Yang, Yuwei An, Hongyi Liu, Tianqi Chen, Beidi Chen

arXiv:2506.09991v2cs.LG

TL;DR

Autoregressive generation is sequential, even though reasoning trajectories can contain parallelizable branches, and existing approaches face limitations in adaptive, lossless parallel generation. Multiverse internalizes MapReduce generation and co-designs data, algorithm, and system components; Multiverse-32B reports AR-comparable reasoning performance and up to 2× speedup.

  • Problem

    Autoregressive generation is sequential, while existing parallel-generation approaches face limits in adapting task splits, preserving internal states, or handling diverse parallelism patterns.

    Source: §1 · p. 2

  • Method

    Multiverse uses sequential Map decomposition, parallel Process execution, and sequential Reduce synthesis, supported by co-designed data, attention, and inference systems.

    Source: §1 · pp. 2–3

  • Results

    Multiverse-32B achieves performance comparable to AR-LLMs on real-world reasoning tasks and up to 2× wall-clock speedup per generated token across varying batch sizes.

    Source: §8 · p. 11

  • Takeaways & Limitations

    The framework provides a route to applying internally parallel generation to complex reasoning tasks while retaining rapid transfer from AR-LLMs.

    Source: §1 · p. 2

    Applications beyond LLM reasoning remain underexplored, and Multiverse-32B was trained solely with SFT; integrating RL would require a more robust engine.

    Source: §9 · p. 11

Abstract

from arXiv · show

Autoregressive Large Language Models (AR-LLMs) frequently exhibit implicit parallelism in sequential generation. Inspired by this, we introduce Multiverse, a new generative model that enables natively parallel generation. Multiverse internalizes a MapReduce paradigm, generating automatically through three stages: (i) a Map stage for adaptive task decomposition, (ii) a Process stage for parallel subtask execution, and (iii) a Reduce stage for lossless result synthesis. Next, we build a real-world Multiverse reasoning model with co-design of data, algorithm, and system, enabling rapid and seamless transfer from frontier AR-LLMs. For data creation, we develop Multiverse Curator, an automated LLM-assisted pipeline that transforms sequential reasoning chains into structured training data, avoiding costly human annotations. Algorithmically, we design Multiverse Attention to separate parallel reasoning steps while keeping compatibility with causal attention for efficient training. Systematically, we implement Multiverse Engine to support parallel inference. It features a dedicated interpreter that dynamically switches between sequential and parallel generation, triggered directly by the model. After a 3-hour fine-tuning with 1K examples, our Multiverse-32B stands as the only open-sourced non-AR model achieving performance on par with leading AR-LLMs of the same scale, evidenced by AIME24 & 25 scores of 54% and 46%, respectively. Moreover, our budget control experiments show that Multiverse-32B exhibits superior scaling, outperforming AR-LLMs by 1.87% on average using the same context length. Such scaling further leads to practical efficiency gains, achieving up to 2x speedup across varying batch sizes. We have open-sourced the entire Multiverse ecosystem, including data, model weights, engine, as well as complete data curation prompts and detailed training and evaluation recipes.

1 Introduction

Multiverse targets adaptive, lossless parallel reasoning by turning implicit parallelism in autoregressive outputs into a MapReduce generation framework. The introduction presents its data, attention, and system designs alongside results and comparisons with prior parallel-generation approaches.

2 Related Work

  • Prior work identifies costs or limits in parallel-generation alternatives: brute-force methods ignore logical dependencies, external-tool methods rely on heuristics, and internal-communication methods face training–inference inconsistencies or shallow parallelism.The introduction also notes that some external methods exchange short text summaries rather than complete KV states when switching between sequential and parallel generation.Source: §1 · p. 2, §2 · pp. 3–4

1 Introduction

  • Over 98% of analyzed s1K-1.1 Chain-of-Thought trajectories contain parallelizable branches, but probing tests find AR-LLMs cannot actively enforce or discern them.The identified constraints are missing explicit parallelism in real-world data, causal attention's sequential-generation limitation, and AR inference engines' inability to execute parallel generation.Source: §1 · p. 2
  • Multiverse uses sequential Map decomposition, parallel Process execution, and sequential Reduce synthesis, and its pipeline can invoke itself recursively.The paper reports a linear-time solution for a synthetic NP-hard SAT problem under unlimited resources.Source: §1 · p. 2
  • Multiverse Curator converts sequential reasoning chains into structured parallel training data through five steps, with content and grammar checks to flag low-quality samples.The pipeline produces Multiverse-1K, a dataset of 1,000 structured training samples, avoiding costly manual filtration and annotation.Source: §1 · p. 2
  • Multiverse Attention separates independent reasoning branches through attention masks and position embeddings while permitting parallel training similar to causal attention.The design supports transfer from pretrained AR models using only a few thousand examples.Source: §1 · pp. 2–3
  • Multiverse Engine interprets model-generated control tags to switch between sequential and parallel generation, mapping subtasks to branches and reducing their KV states into one sequence.The engine supports prefix sharing during parallel execution and is described as switching without overhead.Source: §1 · p. 3
  • 23.6% improvement over the base model, with AIME24 and AIME25 scores of 53.8% and 45.8%, respectively, makes Multiverse-32B comparable to AR-LLMs.It also reports an average 1.87% improvement under fixed latency constraints and up to 2× wall-clock speedup per generated token across batch sizes 1–128.Source: §1 · p. 3

2 Related Work

  • Length and depth scaling increase latency through sequential generation, while width scaling requires external tools or models to split or merge generations.These constraints motivate parallel task-solving as a scaling direction.Source: §1 · p. 2, §2 · p. 3

3 Long CoT Generation: Sequential or Parallel in Logic?

Long reasoning chains contain parallelizable branches, but AR-LLMs struggle to explicitly generate or discern them. Multiverse addresses this with adaptive MapReduce generation, separating decomposition, parallel execution, and synthesis.

3.1 LLMs can Implicitly Generate Parallelizable Branches.

  • Parallelizable branches comprise collective tasks whose branches all contribute and selective paths where only some contribute, and can occur consecutively or recursively.Collective branches split work into concurrent subtasks that are merged; selective branches consider paths that need not all contribute.Source: §3.1 · p. 4, Figure 2 · p. 4
  • Over 98% of s1K-1.1 examples feature parallelizable branches; collective branches account for 79%, selective branches 19%, and branches appear an average of 7 times per example.Table 1 reports per-example existence ratios and frequencies for branch types.Source: §3.1 · pp. 4–5, Table 1 · p. 4

3.2 LLMs cannot Explicitly Structure Parallelizable Branches.

  • Prompting tests show a 90% disparity between explicit occurrence and implicit existence, while hidden-state probes perform comparably to random guessing.The probing test uses a two-layer MLP on final-layer representations to predict whether a token initiates parallelizable branches.Source: §3.2 · p. 5, Figure 3 · p. 5

4.1 Preliminaries.

  • Autoregressive modeling conditions each token on all preceding tokens, and AR models exhibit poor parallelism in generation.The section frames Multiverse as a MapReduce approach to adaptive, lossless parallel generation.Source: §4.1 · p. 5, Figure 4 · p. 6

4.2 Multiverse Modeling.

  • Multiverse removes redundant sequential dependencies between independent contexts through sequential Map decomposition, parallel Process execution, and sequential Reduce synthesis.The Reduce stage conditions on tokens from all branches, and the structure supports recursive and consecutive compositions.Source: §4.2 · p. 6

4.3 Structured Generation Flow.

  • Control tags mark MapReduce block boundaries and coordinate the stages, with indexed <Path> blocks for parallel subtasks and <Conclusion> triggering synthesis.The block starts with <Parallel> and ends with </Parallel>.Source: §4.3 · p. 6, Figure 5 · p. 6

5 Building a Real-world Multiverse Model.

The real-world Multiverse suite combines a data generator, a core algorithm, and an inference system. The paper reports that it supports a rapid shift from leading AR models to Multiverse models for complex reasoning tasks.

5 Building a Real-world Multiverse Model.

  • The real-world suite combines Multiverse Curator, Multiverse Attention, and Multiverse Engine as data generator, core algorithm, and optimized system.Source: §5 · p. 6
  • The suite enables a smooth and rapid shift from leading AR models to Multiverse models, yielding a model with strong reasoning capabilities on complex reasoning tasks.Source: §5 · pp. 6–7

Inherent Parallelism in Original Reasoning Chain

1. Parse the Chain into a Tree-structure Summary

Multiverse Curator converts sequential reasoning chains into parallel MapReduce training structures. Multiverse Attention and Multiverse Engine support independent parallel paths and their execution during inference.

5.1 Data Curation: Multiverse Curator.

  • Multiverse Curator automatically transforms sequential reasoning chains into parallel MapReduce structures through an LLM-assisted, five-stage prompting protocol.Content and grammar checks trigger regeneration of low-quality examples; applying the pipeline to s1K-1.1 yielded 1,000 structured trajectories.Source: §5.1 · pp. 7–8

1. Parse the Chain into a Tree-structure Summary

  • The curator decomposes each reasoning chain into a two-level summary tree, then identifies steps that can run in parallel without violating logical dependencies.It reformats parallel groups, restores their original reasoning details, and adds Map and Reduce stages while rewriting paths to remain independent.Source: §5.1 · pp. 7–8

5.2 Algorithm Design: Multiverse Attention.

  • Multiverse Attention modifies attention masks and position indices so paths in one Process block start at the same position and execute independently.Paths converge during Reduce at the maximum position reached by any path; the design preserves training parallelism and can be adapted with a few samples.Source: §5.2 · p. 8

5.3 System Implementation: Multiverse Engine.

  • Multiverse Engine triggers Map when it generates a <Parallel> token, counts outlines, and schedules the resulting paths for parallel execution.The paths share prefix KV cache; after all finish, the engine merges their KV states with the preceding context and resumes generation with <Conclusion>.Source: §5.3 · pp. 8–9

6 Experiments

The experiments report that Multiverse-32B matches or exceeds autoregressive models on real-world reasoning tasks and improves over Qwen2.5-32B-Instruct. At the same context length, it generates more tokens and improves performance on GPQA-Diamond and MATH500.

6 Experiments

  • 24.5% improvement over Qwen2.5 and matching or exceeding AR-LLMs are reported in the experiments overview; the overview also describes a superior performance–latency tradeoff.The scaling comparison is attributed to generating more tokens within the same wall-clock time.Source: §6 · p. 9

6.1 Setup.

  • Multiverse-32B is fine-tuned on Qwen2.5-32B-Instruct using Multiverse and sequential data, with a mixture shifting across eight epochs; fine-tuning took 3 hours on 8 NVIDIA B200 GPUs.Evaluation covers AIME24, AIME25, MATH500, and GPQA Diamond; baselines include Qwen2.5, Autoregressive-32B trained on the same data, and s1 models.Source: §6.1 · p. 9

6.2 Real-world Reasoning Performance

  • 38%, 35%, 11%, and 14% improvements over Qwen2.5-32B-Instruct across four reasoning benchmarks; Multiverse-32B matches or surpasses autoregressive models.Table 2 compares 32B models; its pass@1 results average eight seeds on AIME.Source: §6.2 · pp. 9–10, Table 2 · p. 9
  • Multiverse-32B shows greater parallelism on AIME tasks with a slight performance improvement, while Multiverse-32B-Zero performs better on tasks requiring shorter generation sequences.The authors attribute reduced parallelism on AIME partly to the scarcity of Multiverse-1K training data exceeding 16K tokens.Source: §6.2 · p. 10

6.3 Scaling Performance

  • 2.23% on GPQA-Diamond and 1.51% on MATH500: Multiverse-32B improves performance at the same context length, with # parallel values of 1.17 and 1.15, respectively.The budget-control contexts range from 1K to 4K tokens and are described as approximately the same generation time; Figure 7 reports actual generation lengths.Source: §6.3 · p. 10, Figure 7 · p. 10

7 Efficiency Analysis

Multiverse’s efficiency analysis examines how parallelism affects latency across generation lengths and batch sizes. It reports faster generation and improved scaling, while noting limitations in application scope and training approach.

7 Efficiency Analysis

  • 18.5% average speedup occurs for parallelism degrees from 1.0 to 1.3, while examples in the next region reach up to 2.1× acceleration.The analysis uses batch size one and generation lengths of 8K, 16K, and 32K.Source: §7 · p. 10
  • Speedup scales linearly with degree of parallelism across configurations, while generation remains memory-bound as batch size rises from 1 to 128.Figure 8 presents efficiency across varying batch sizes.Source: §7 · pp. 10–11, Figure 8 · p. 11

8 Conclusion

  • Up to 2× wall-clock speedup per generated token is reported across varying batch sizes, based on the degree of parallelism.The conclusion also reports better scaling than AR-LLMs at the same context length.Source: §8 · p. 11

9 Limitations

  • Applications beyond LLM reasoning remain underexplored, and Multiverse-32B was trained solely with supervised fine-tuning.The authors identify integrating reinforcement learning as future work, which would require a more robust Multiverse Engine.Source: §9 · p. 11

10 Broader Impacts

  • Multiverse is described as boosting GPU utilization through massive parallel generation, particularly benefiting small-batch and long-context inference.The passage also describes reduced latency and energy consumption and near-constant overall latency as task complexity increases for parallelizable tasks.Source: §10 · p. 11

A Prompt of Multiverse Curator

The Multiverse Curator prompt protocol turns sequential reasoning chains into structured parallel data. Its stages extract and organize reasoning, refill original details, then add MapReduce structure and validate the result.

Protocol overview

  • The five-stage protocol transforms sequential chains into Multiverse data by extracting steps and substeps, structuring parallelism, refilling details, and adding MapReduce stages.It is powered by Gemini 2.5 Pro and is intended to transform sequential chain-of-thought data.Source: A Prompt of Multiverse Curator · pp. 16–17

Stage 5

  • Stage 5 inserts generated Map and Reduce phases, checks structural validity with a customized XML interpreter, and rewrites each path separately.The interpreter filters invalid entries and extracts outermost MapReduce blocks from valid ones.Source: A Prompt of Multiverse Curator · pp. 16, 20, 21

Stages 1–3

  • Stages 1–3 extract main steps and substeps, identify parallel groups without violating dependencies, and format the result as a nested summary tree.The prompts require contiguous grouping and cap nesting at two levels; they also direct conditional branches to be treated as independent tasks.Source: A Prompt of Multiverse Curator · pp. 17–19

Stage 4

  • Stage 4 processes the original reasoning sentence by sentence, replacing or inserting full sentences while preserving parallel tags and ensuring completeness.A content checker uses relative editor distance, with a threshold of 0.2 in practice, to decide whether a step should be regenerated.Source: A Prompt of Multiverse Curator · pp. 16, 20

Stage 5

  • The rewriting prompts preserve nested parallel structures while making each path self-contained and synthesizing path outcomes in a conclusion.Nested blocks are processed recursively, and the prompts specify how to rewrite goals, paths, and conclusions.Source: A Prompt of Multiverse Curator · pp. 21–22

B Examples in Training Data and Model Generation

The appendix presents Multiverse-1K examples alongside outputs generated by Multiverse-32B trained on that dataset.

B Examples in Training Data and Model Generation

B.1 Training Examples from Multiverse-1K

The training examples illustrate a collective distance-summing problem and a selective construction problem involving dense points and chords avoiding a set.

B.1 Training Examples from Multiverse-1K

  • The collective example reports sums of distances from P1, P2, P3, and P4 to the other points as approximately 51.59, 55.51, 45.02, and 61.64, respectively.Source: §B.1 · p. 24
  • The selective example considers constructing a dense subset H of S2 whose pairwise connecting chords avoid K, but identifies challenges in maintaining that property for every pair.The example says the Baire Category Theorem route lacks a clear construction method.Source: §B.1 · pp. 24–25

B.2 Generated Examples from Multiverse-32B

The generated examples show Multiverse-32B solving a path-counting problem by splitting the count across two alternating five-segment patterns, then combining their totals.

B.2 Generated Examples from Multiverse-32B

  • Starting horizontally gives three horizontal and two vertical segments, with 147 valid segment-length allocations.The example distributes eight units among positive-length segments in each direction.Source: §B.2 · pp. 25–26
  • Starting vertically gives three vertical and two horizontal segments, also yielding 147 valid segment-length allocations.This is the second alternating five-segment case.Source: §B.2 · p. 25
  • Each starting direction yields 147 valid paths, for 294 total configurations across the two five-segment patterns.The patterns are H–V–H–V–H and V–H–V–H–V.Source: §B.2 · pp. 25–26

Related papers

Loading 2506.09991v2…