Accelerate Parallelizable Reasoning via Parallel Decoding within One Sequence

• URL: http://arxiv.org/abs/2503.20533v3
• Date: Wed, 23 Apr 2025 07:58:07 GMT
• Title: Accelerate Parallelizable Reasoning via Parallel Decoding within One Sequence
• Authors: Yijiong Yu,
• Abstract summary: We leverage the inherent parallelizability of certain tasks to accelerate the reasoning process.<n> Experimental results show that our method achieves over 100% speedup in decoding time while maintaining the answer quality.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Recent advances in reasoning models have demonstrated significant improvements in accuracy, particularly for complex tasks such as mathematical reasoning, by employing detailed and comprehensive reasoning processes. However, generating these lengthy reasoning sequences is computationally expensive and time-consuming. To address this inefficiency, we leverage the inherent parallelizability of certain tasks to accelerate the reasoning process. Specifically, when multiple parallel reasoning branches exist, we decode multiple tokens per step using a specialized attention mask, processing them within a single sequence, avoiding additional memory usage. Experimental results show that our method achieves over 100% speedup in decoding time while maintaining the answer quality.

Related papers

• Critical Thinking: Which Kinds of Complexity Govern Optimal Reasoning Length? [72.70486097967124]
  We formalize a framework using deterministic finite automata (DFAs) We show that there exists an optimal amount of reasoning tokens such that the probability of producing a correct solution is maximized. We then demonstrate an implication of these findings: being able to predict the optimal number of reasoning tokens for new problems and filtering out non-optimal length answers results in consistent accuracy improvements.
  arXiv  Detail & Related papers  (2025-04-02T17:45:58Z)
• Dynamic Parallel Tree Search for Efficient LLM Reasoning [102.16694475391665]
  Tree of Thoughts (ToT) enhances Large Language Model (LLM) reasoning by structuring problem-solving as a spanning tree.<n>We propose Dynamic Parallel Tree Search (DPTS), a novel parallelism framework that aims to dynamically optimize the reasoning path in inference.<n> Experiments on Qwen-2.5 and Llama-3 with Math500 and GSM8K datasets show that DPTS significantly improves efficiency by 2-4x on average.
  arXiv  Detail & Related papers  (2025-02-22T14:13:37Z)
• Longer Attention Span: Increasing Transformer Context Length with Sparse Graph Processing Techniques [0.0]
  We propose a graph computing view of attention where tokens are perceived as nodes of the graph and the attention mask determines the edges of the graph. Using this view, we develop graph processing algorithms to implement the attention mechanism. Our algorithms are able to achieve extremely long sequence lengths of as high as 160 million on a single NVIDIA A100 GPU.
  arXiv  Detail & Related papers  (2025-01-31T22:05:00Z)
• Cerberus: Efficient Inference with Adaptive Parallel Decoding and Sequential Knowledge Enhancement [12.40683763019276]
  Large language models (LLMs) often face a bottleneck in inference speed due to their reliance on auto-regressive decoding. We have identified two key issues with existing parallel decoding frameworks. We propose Cerberus, an adaptive parallel decoding framework.
  arXiv  Detail & Related papers  (2024-10-17T08:55:18Z)
• Sparser is Faster and Less is More: Efficient Sparse Attention for Long-Range Transformers [58.5711048151424]
  We introduce SPARSEK Attention, a novel sparse attention mechanism designed to overcome computational and memory obstacles. Our approach integrates a scoring network and a differentiable top-k mask operator, SPARSEK, to select a constant number of KV pairs for each query. Experimental results reveal that SPARSEK Attention outperforms previous sparse attention methods.
  arXiv  Detail & Related papers  (2024-06-24T15:55:59Z)
• Parallel Decoding via Hidden Transfer for Lossless Large Language Model Acceleration [54.897493351694195]
  We propose a novel parallel decoding approach, namely textithidden transfer, which decodes multiple successive tokens simultaneously in a single forward pass. In terms of acceleration metrics, we outperform all the single-model acceleration techniques, including Medusa and Self-Speculative decoding.
  arXiv  Detail & Related papers  (2024-04-18T09:17:06Z)
• ProPD: Dynamic Token Tree Pruning and Generation for LLM Parallel Decoding [12.449023969197684]
  ProPD is an efficient parallel decoding framework based on dynamic token tree pruning and generation. We demonstrate ProPD consistently outperforms existing decoding algorithms by 1.1-3.2x.
  arXiv  Detail & Related papers  (2024-02-21T02:51:07Z)
• SPEED: Speculative Pipelined Execution for Efficient Decoding [35.45955948053644]
  We propose SPEED, which improves inference efficiency by speculatively executing multiple future tokens in parallel with the current token. For Transformer decoders that employ parameter sharing, the memory operations for the tokens executing in parallel can be amortized. We demonstrate the efficiency of our method in terms of latency reduction relative to model accuracy and demonstrate how speculation allows for training deeper decoders with parameter sharing with minimal runtime overhead.
  arXiv  Detail & Related papers  (2023-10-18T16:07:01Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  We discuss the problem of bounding partially identifiable queries, such as counterfactuals, in Pearlian structural causal models. A recently proposed iterated EM scheme yields an inner approximation of those bounds by sampling the initialisation parameters. We show how a single symbolic knowledge compilation allows us to obtain the circuit structure with symbolic parameters to be replaced by their actual values.
  arXiv  Detail & Related papers  (2023-10-05T07:10:40Z)
• Parallel Algorithms Align with Neural Execution [7.535219325248997]
  Parallel algorithms however may exploit their full computational power, therefore requiring fewer layers to be executed. This drastically reduces training times, as we observe when comparing parallel implementations of searching, sorting and finding strongly connected components to their sequential counterparts on the CLRS framework.
  arXiv  Detail & Related papers  (2023-07-08T21:28:20Z)
• Code Prompting: a Neural Symbolic Method for Complex Reasoning in Large Language Models [74.95486528482327]
  We explore code prompting, a neural symbolic prompting method with both zero-shot and few-shot versions which triggers code as intermediate steps. We conduct experiments on 7 widely-used benchmarks involving symbolic reasoning and arithmetic reasoning.
  arXiv  Detail & Related papers  (2023-05-29T15:14:09Z)
• NAPG: Non-Autoregressive Program Generation for Hybrid Tabular-Textual Question Answering [52.10214317661547]
  Current numerical reasoning methods autoregressively decode program sequences. The accuracy of program generation drops sharply as the decoding steps unfold due to error propagation. In this paper, we propose a non-autoregressive program generation framework.
  arXiv  Detail & Related papers  (2022-11-07T11:25:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.