LSR-MCTS: Alleviating Long Range Dependency in Code Generation

• URL: http://arxiv.org/abs/2504.07433v3
• Date: Sat, 17 May 2025 10:46:05 GMT
• Title: LSR-MCTS: Alleviating Long Range Dependency in Code Generation
• Authors: Tingwei Lu, Yangning Li, Liyuan Wang, Binghuai Lin, Jiwei Tang, Qingsong Lv, Wanshi Xu, Hai-Tao Zheng, Yinghui Li, Xin Su, Zifei Shan,
• Abstract summary: Large language models (LLMs) have significantly promoted the development of code generation task.<n>We propose the textbfLSR-MCTS algorithm, which leverages MCTS to determine the code line-by-line and select the optimal path.
• Score: 42.10272627826627
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The emergence of large language models (LLMs) has significantly promoted the development of code generation task, sparking a surge in pertinent literature. Current research is hindered by redundant generation results and a tendency to overfit local patterns in the short term. Although existing studies attempt to alleviate the issue by adopting a multi-token prediction strategy, there remains limited focus on choosing the appropriate processing length for generations. By analyzing the attention between tokens during the generation process of LLMs, it can be observed that the high spikes of the attention scores typically appear at the end of lines. This insight suggests that it is reasonable to treat each line of code as a fundamental processing unit and generate them sequentially. Inspired by this, we propose the \textbf{LSR-MCTS} algorithm, which leverages MCTS to determine the code line-by-line and select the optimal path. Further, we integrate a self-refine mechanism at each node to enhance diversity and generate higher-quality programs through error correction. Extensive experiments and comprehensive analyses on three public coding benchmarks demonstrate that our method outperforms the state-of-the-art performance approaches.

Related papers

• Execution Guided Line-by-Line Code Generation [49.1574468325115]
  We present a novel approach to neural code generation that incorporates real-time execution signals into the language model generation process.<n>Our method, ExecutionGuidedFree Guidance (EGCFG), incorporates execution signals as model generates code.
  arXiv  Detail & Related papers  (2025-06-12T17:50:05Z)
• Wider or Deeper? Scaling LLM Inference-Time Compute with Adaptive Branching Tree Search [1.0995326465245925]
  We propose Adaptive Branching Monte Carlo Tree Search (AB-MCTS)<n>AB-MCTS generalizes repeated sampling with principled multi-turn exploration and exploitation.<n>We evaluate our method on complex coding and engineering tasks using frontier models.
  arXiv  Detail & Related papers  (2025-03-06T13:10:40Z)
• Improving Autoregressive Visual Generation with Cluster-Oriented Token Prediction [52.09472099976885]
  IAR is an Improved AutoRegressive Visual Generation Method that enhances the training efficiency and generation quality of LLM-based visual generation models.<n>Our method consistently enhances the model training efficiency and performance from 100M to 1.4B, reducing the training time by half while achieving the same FID.
  arXiv  Detail & Related papers  (2025-01-01T15:58:51Z)
• Closer Look at Efficient Inference Methods: A Survey of Speculative Decoding [1.3479499607624648]
  Speculative decoding addresses bottleneck by introducing a two-stage framework: drafting and verification.<n>A smaller, efficient model generates a preliminary draft, which is then refined by a larger, more sophisticated model.<n>This paper provides a comprehensive survey of speculative decoding methods, categorizing them into draft-centric and model-centric approaches.
  arXiv  Detail & Related papers  (2024-11-20T09:46:30Z)
• What's Wrong with Your Code Generated by Large Language Models? An Extensive Study [80.18342600996601]
  Large language models (LLMs) produce code that is shorter yet more complicated as compared to canonical solutions. We develop a taxonomy of bugs for incorrect codes that includes three categories and 12 sub-categories, and analyze the root cause for common bug types. We propose a novel training-free iterative method that introduces self-critique, enabling LLMs to critique and correct their generated code based on bug types and compiler feedback.
  arXiv  Detail & Related papers  (2024-07-08T17:27:17Z)
• Adaptive Draft-Verification for Efficient Large Language Model Decoding [24.347886232342862]
  Large language model (LLM) decoding involves generating a sequence of tokens based on a given context. The typical autoregressive decoding method requires a separate forward pass through the model for each token generated. We introduce ADED, which accelerates LLM decoding without requiring fine-tuning.
  arXiv  Detail & Related papers  (2024-06-27T22:20:39Z)
• From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models [63.188607839223046]
  This survey focuses on the benefits of scaling compute during inference. We explore three areas under a unified mathematical formalism: token-level generation algorithms, meta-generation algorithms, and efficient generation.
  arXiv  Detail & Related papers  (2024-06-24T17:45:59Z)
• SED: Self-Evaluation Decoding Enhances Large Language Models for Better Generation [35.10931307279044]
  This paper proposes Self-Evaluation Decoding, SED, a decoding method for enhancing model generation. It integrates speculation and evaluation steps into the decoding process, allowing LLMs to make more careful decisions.
  arXiv  Detail & Related papers  (2024-05-26T12:43:18Z)
• Beyond the Speculative Game: A Survey of Speculative Execution in Large Language Models [9.121458241884444]
  Speculative execution is introduced to LLM decoding in a textitdraft-then-verify style. As the costly inference is parallelized, decoding speed can be significantly boosted. We present the first survey paper that reviews and unifies literature of speculative execution in LLMs.
  arXiv  Detail & Related papers  (2024-04-23T10:25:45Z)
• 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)
• A Thorough Examination of Decoding Methods in the Era of LLMs [72.65956436513241]
  Decoding methods play an indispensable role in converting language models from next-token predictors into practical task solvers. This paper provides a comprehensive and multifaceted analysis of various decoding methods within the context of large language models. Our findings reveal that decoding method performance is notably task-dependent and influenced by factors such as alignment, model size, and quantization.
  arXiv  Detail & Related papers  (2024-02-10T11:14:53Z)
• SparseCoder: Advancing Source Code Analysis with Sparse Attention and Learned Token Pruning [10.067863549963834]
  This paper introduces SparseCoder, an innovative approach incorporating sparse attention and learned token pruning. Compared to previous state-of-the-art models CodeBERT, RoBERTa, and CodeT5, our experiments demonstrate that SparseCoder can handle significantly longer input sequences. SparseCoder is four times faster than other methods measured in, achieving a 50% reduction in floating point operations per second.
  arXiv  Detail & Related papers  (2023-10-11T01:11:30Z)
• Text Generation with Efficient (Soft) Q-Learning [91.47743595382758]
  Reinforcement learning (RL) offers a more flexible solution by allowing users to plug in arbitrary task metrics as reward. We introduce a new RL formulation for text generation from the soft Q-learning perspective. We apply the approach to a wide range of tasks, including learning from noisy/negative examples, adversarial attacks, and prompt generation.
  arXiv  Detail & Related papers  (2021-06-14T18:48:40Z)

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.