Combining Static Code Analysis and Large Language Models Improves Correctness and Performance of Algorithm Recognition

1. Problem Statement

Software developers spend a significant portion of their time on program comprehension. Automatically identifying algorithms within source code can aid in maintenance, optimization, and understanding legacy systems. However, existing approaches face limitations:

• Traditional Static Analysis: Relies on rigid search patterns (e.g., AST matching) which lack flexibility and struggle with implementation variants.
• Pure LLM Approaches: While Large Language Models (LLMs) show promise in code understanding, they are computationally expensive (high latency/cost) when applied to entire codebases. Furthermore, it is unclear if LLMs rely too heavily on superficial cues (like variable names) rather than semantic logic.

The core challenge is to achieve high-accuracy algorithm recognition while maintaining runtime efficiency and ensuring the models rely on semantic understanding rather than just identifier names.

2. Methodology

The authors conducted an empirical study using the BigCloneEval (BCEval) dataset, which contains manually verified algorithm implementations from real-world Java open-source projects. The study focuses on seven specific algorithms: Prime Factors, GCD, Fibonacci, Palindrome, Bubble Sort, Binary Search, and Transpose Matrix.

The research is structured around three Research Questions (RQs):

RQ1: Prompting Strategies

The authors evaluated different prompting techniques on three models: GPT-4o mini, Llama 3.1 70B, and Mixtral 8x22B.

• Baselines: Compared binary "Yes/No" prompts against a "Score" prompt (0–4 scale) to allow tuning the precision-recall trade-off.
• In-Context Learning (ICL): Tested providing examples (positive/negative) to guide the model. They varied the number and type of examples (e.g., 2 positive, 2 negative, etc.).
• Chain of Thought (CoT): Tested whether forcing the model to "think step-by-step" before answering improves accuracy.

RQ2: Hybrid Approach (Static Analysis + LLM)

To address runtime costs, the authors proposed a filter-and-classify pipeline:

1. Filtering: Use lightweight static analysis patterns to exclude methods unlikely to be the target algorithm before invoking the LLM.
2. Classification: Pass only the filtered candidates to the LLM.

• Pattern Types:
  • Keyword-Based: Regex matching on identifiers (Recall-focused vs. Precision-focused).
  • Structural: Based on Abstract Syntax Tree (AST) features using a Domain Specific Language (DSL) to match structural patterns (e.g., nested loops with array swaps for Bubble Sort).

RQ3: Dependence on Name Information

An ablation study was performed where all identifiers in the source code were obfuscated (replaced with random names). This tested whether LLMs rely on semantic logic or superficial naming conventions.

3. Key Contributions

1. First Comprehensive Hybrid Evaluation: The first study to systematically evaluate combining static code analysis with LLMs specifically for algorithm recognition.
2. Prompting Optimization: Identification of "In-Context Learning with two positive examples" as the optimal strategy for balancing performance and cost.
3. Filter Pattern Framework: Development and evaluation of keyword and structural filter patterns that drastically reduce LLM inference calls without sacrificing accuracy.
4. Semantic Robustness: Quantitative evidence that LLMs rely on code semantics, not just variable names, for algorithm detection.

4. Key Results

Prompting Strategies (RQ1)

• Score Prompting: Outperformed binary Yes/No by allowing threshold tuning.
• In-Context Learning (ICL): Providing two positive examples yielded the best "sweet spot," improving F1-scores by 4–8 percentage points (pp) over the baseline with only a modest increase in inference time.
  • Example: Llama 3 improved from 70% to 78% F1.
• Chain of Thought (CoT): Surprisingly, CoT decreased performance for GPT and Llama and significantly increased runtime (up to 65x slower), making it impractical for this specific task.

Hybrid Approach (RQ2)

Combining static filters with LLMs yielded the most significant gains:

• Runtime Reduction: Filter patterns reduced the number of methods sent to the LLM by 72.39% to 97.50%.
• Performance Improvement: Contrary to the expectation that filtering might lose true positives, the hybrid approach improved F1-scores by up to 12 pp compared to the LLM baseline.
  • Reasoning: Filters removed "hard negative" cases that LLMs tended to misclassify as false positives, thereby boosting precision.
• Best Configuration: The "Prominent Feature" structural patterns (lightweight AST matching) combined with LLMs achieved a 97.12% reduction in LLM calls while increasing F1-scores to ~73%.

Name Obfuscation (RQ3)

• Impact: Obfuscating identifiers caused a slight drop in Recall (4–5 pp) but a significant increase in Precision (up to 17 pp for Mixtral).
• Net Result: The overall F1-score increased by 3–10 pp for all models.
• Conclusion: LLMs do not rely solely on variable names; they successfully identify algorithms based on control flow and data structures even when names are meaningless.

5. Significance and Conclusion

This paper demonstrates that a hybrid approach is superior to using LLMs or static analysis in isolation for algorithm recognition.

• Efficiency: By pre-filtering code with simple static rules, the computational cost of using LLMs is reduced by over 90%, making large-scale analysis feasible.
• Accuracy: The combination actually improves accuracy because the static filter removes ambiguous cases that confuse the LLM, allowing the LLM to focus on harder, more nuanced decisions.
• Practical Application: The authors propose that this hybrid model can be integrated into IDEs or CI/CD pipelines to automatically detect suboptimal algorithms, assist in code reviews, or aid in teaching tools.

Final Takeaway: The study concludes that while LLMs are powerful, they are most effective when guided by traditional static analysis techniques, creating a system that is both cost-effective and highly accurate.