Abstract
Determining the time complexity of code is a fundamental yet undecidable problem in computer science. While deep learning models can estimate complexity, they typically require vast amounts of labeled data, which is expensive to produce. We present TCProF, a semi-supervised learning (SSL) framework designed for time-complexity prediction in low-resource settings. TCProF integrates specialized code augmentation, a symbolic analysis module, and a co-training mechanism. Our experiments demonstrate that TCProF achieves over a 60% performance improvement over standard self-training methods, outperforming large language models like GPT-3.5 and Gemini-Pro in few-shot scenarios.
Introduction
Predicting whether a code snippet is $O(N)$ or $O(N^2)$ is essential for software optimization and performance analysis. However, creating large-scale, accurately labeled datasets for this task is challenging due to the expert knowledge required. TCProF addresses this "low-resource" challenge, aiming to train accurate models using as few as 5 to 10 labeled examples per complexity category.
Methodology
TCProF moves beyond traditional self-training by employing three core components:
- Specialized Data Augmentation (AUG): To increase data variety without altering complexity, TCProF uses Back-Translation (e.g., Java to Python and back) and Loop-Conversion (interchanging
forandwhileloops). These transformations force the model to focus on logic rather than syntax. - Symbolic Module (Sym): A non-neural component utilizing Regular Expressions and Abstract Syntax Trees (ASTs) to analyze code structure. It provides a "rational" check on the neural model's predictions, improving the quality of pseudo-labels for unlabeled data.
- Co-Training Mechanism: Two models are trained simultaneously—one on original data and one on augmented data. By sharing high-confidence predictions, they mitigate the error-accumulation typical in single-model self-training.
Experimental Evaluation
The framework was evaluated on two benchmarks: CorCoD (Java, 5 classes) and CodeComplex (Java/Python, 7 classes). We focused on 5-shot and 10-shot scenarios to simulate extreme data scarcity.
Key Results
TCProF demonstrated significant performance leaps across all benchmarks:
- Superior Accuracy: TCProF achieved a 60% improvement in accuracy and F1-score over standard SSL baselines.
- Outperforming LLMs: In 10-shot settings on the CodeComplex (Python) dataset, TCProF (using UniXcoder) reached 70.29% accuracy, significantly higher than GPT-3.5 (32.55%) and Gemini-Pro (31.05%), and even surpassing GPT-4 (53.04%).
- Efficiency: With only a few labels, TCProF reached 91-94% of the performance of models trained on full datasets.
Discussion and Insights
The success of TCProF highlights the synergy between neural "intuition" and symbolic "logic." The symbolic module acts as a critical filter, preventing the model from reinforcing its own errors. Furthermore, structural augmentations like loop conversion prove that domain-specific transformations are vital for code-related tasks.
While highly effective, the model still faces challenges in distinguishing subtle differences in nested loops or handling highly obfuscated code. Future work will explore predicting space complexity and moving toward continuous growth rate estimation.
Conclusion
TCProF provides a robust solution for time-complexity prediction when labeled data is scarce. By combining symbolic reasoning with advanced SSL techniques, it sets a new standard for few-shot code analysis.
Summary updated