Chain-of-thought (CoT) reasoning has emerged as a powerful paradigm for extending the computational capabilities of transformer-based models. A growing body of recent work has begun to uncover the fine-grained computational power of transformers augmented with CoT, as well as their connections to classical complexity theory. In this work, we advance this line of research by establishing the first hierarchy theorem for CoT-based computation. Our main result shows that for any reasonable resource bound $r(n) \geq n$ and any $\varepsilon > 0$, \[ \mathrm{CoT}(r(n)) \subsetneq \mathrm{CoT}(r(n)^{1+\varepsilon}), \] where $\mathrm{CoT}(r(n))$ denotes the class of decision problems solvable by transformers using $O(r(n))$ CoT reasoning steps on inputs of length $n$. Our result shows that increasing the number of CoT reasoning steps provably yields strictly greater computational power, establishing CoT steps as a fundamental resource in transformer-based computation. Unlike classical hierarchy theorems, which are typically proved via diagonalization, our approach leverages known coarse-grained simulations between CoT-augmented transformers and Turing machines in both directions. Building on these connections, we adapt the classical padding technique from complexity theory to this setting to obtain a tight hierarchy. A key technical contribution of our work is the implementation of padding within the transformer-based CoT model.
Quan Tran, Duong Nguyen, Thanh Le-Cong, Triet Huynh Minh Le, M. Ali Babar, Hoang Dieu Vu, Quyet-Thang Huynh
原文摘要
Just-In-Time Vulnerability Prediction (JIT-VP) identifies security risks in code changes at commit time, enabling early feedback before vulnerabilities enter software systems. However, its practical reliability is challenged by the difficulty of constructing accurate labels. Multiple strategies with different trade-offs have been proposed to identify vulnerability-fixing commits (VFCs) and vulnerability-introducing commits (VICs) for dataset construction, leading to substantially different datasets. This makes it difficult to separate model performance from dataset construction. Moreover, real-world quality assurance requires not only classification but also prioritizing high-risk commits and localizing vulnerable causes. This paper presents an extensive empirical study of how labeling strategies affect these downstream tasks. We constructed 28 datasets using four VFC and four VIC labeling strategies across OpenSSL and Linux kernel, then evaluated six representative JIT-VP models for classification, prioritization, and localization. Our results show that labeling effectiveness is strongly task-dependent. Manual VFC labeling combined with vulnerability-specific VIC labeling provides the most reliable performance for classification and prioritization, significantly outperforming 11 of 15 alternatives. Meanwhile, precision-first VFC labeling combined with LLM-assisted VIC labeling performs best for localization, significantly outperforming 7 of 15 alternatives. These findings demonstrate that no single labeling strategy is universally optimal and highlight the importance of task-oriented dataset construction.
As Large Language Models (LLMs) are increasingly integrated into software development workflows, they also become prime targets for adversarial attacks. Among these, backdoor attacks are a significant threat, allowing attackers to manipulate model outputs through hidden triggers embedded in training data. Detecting such backdoors remains a challenge, and one promising approach is the use of Spectral Signature defense methods that identify poisoned data by analyzing feature representations through eigenvectors. While some prior works have explored Spectral Signatures for backdoor detection in neural networks, recent studies suggest that these methods may not be optimally effective for code models. In this paper, we revisit the applicability of Spectral Signature-based defenses in the context of backdoor attacks on code models. We systematically evaluate their effectiveness under various attack scenarios and defense configurations, analyzing their strengths and limitations. We found that the widely used setting of Spectral Signature in code backdoor detection is often suboptimal. Hence, we explored the impact of different settings of the key factors. We discovered a new proxy metric that can more accurately estimate the actual performance of Spectral Signature without model retraining after the defense. Our findings contribute to a deeper understanding of the configurations of Spectral Signature defenses in securing code models and offer insights into potential improvements for future research.