Synthesizing Performance Constraints for Evaluating and Improving Code Efficiency

We appreciate the time and effort you took to review our paper and provide valuable comments that will help us improve it further.

Q1: Makes strong claims about related work. Many performance-fuzzing papers are not cited.

Thanks for pointing this out. We apologize for the extremely condensed discussion of performance-fuzzing-related works and the imprecise claim. Making a sweeping dismissal was absolutely not our intention, nor do we intend to make misleading claims. In fact, we sincerely respect the great line of literature on fuzzing and performance testing, which motivated our design and helped us distinguish Wedge from all existing LLM-based input generation approaches. While we do not attempt to make an excuse here, our original motivation was to benchmark existing LLM-based code optimization and compare it to recent LLM-enabled performance testing works. This unfortunately biased our citations to these recent LLM-based works, but we do not intend to claim they are the state-of-the-art. We have revised the paper to include an extensive discussion of performance-fuzzing-related works.

Regarding “path explosion, fine-grained performance profiling overhead, and the lack of oracles to precisely capture inefficient behaviors or symptoms”, we totally agree that the claim is too strong and unfair. We apologize for such a misleading summary, as we tried to save space in our original submission. Please allow us to elaborate on our rationale in the following.

Specifically, for path explosion, we refer to static approaches like symbolic execution, where the path explosion is a known problem [1, 2]. This is to actually argue the advantage of our fuzzing-based approach, but it got merged into the discussion of “traditional approaches”. We have fixed the description in the paper.

For lack of oracles, we attempted to argue that some performance fuzzing does not have an explicit and reliable oracle, e.g., slowfuzz [3] relies on resource usage as guidance, but it may only serve as an approximate proxy to represent a performance issue. In fact, we admit the constraints generated by Wedge may not be perfect either, but complementary to this metric (see our new experiments below). We will tone down the claim.

For profiling overhead, we add the following experiments to compare Wedge’s efficiency of the generated tests with those of Perffuzz [4], one of the well-known performance fuzzer. Specifically, we run perffuzz, perffuzz on Wedge’s instrumented programs (perffuzz_wedge_inst), Wedge (AFL++ with instrumented programs), and the original AFL that perffuzz is built on with Wedge’s instrumented programs (afl_wedge_inst), and compare the average number of target program executions per second (exec_per_sec).

We can see that AFL with perffuzz’s profiling incurs significant overhead (perffuzz and perffuzz_wedge_inst), executing the fewest instructions per second. When turning off such profiling and using the base AFL that perffuzz built on with wedge’s instrumented program (afl_wedge_inst), the number of executions per second almost doubles.

Importantly, we run these generated tests on the programs of the corresponding problems and find that the increased profiling cost does not lead to improved performance-stressing capabilities.

We observe that the original AFL with wedge’s instrumented programs can generate more stressing tests than tests generated by perffuzz and perffuzz with wedge’s instrumented code. Moreover, using the complete design in Wedge obtains the most stressing tests compared to all the settings.

[1] Cadar, Cristian, Daniel Dunbar, and Dawson R. Engler. "Klee: unassisted and automatic generation of high-coverage tests for complex systems programs." In OSDI, vol. 8, pp. 209-224. 2008.

[2] Chen, Bihuan, Yang Liu, and Wei Le. "Generating performance distributions via probabilistic symbolic execution." In Proceedings of the 38th International Conference on Software Engineering, pp. 49-60. 2016.

[3] Petsios, Theofilos, Jason Zhao, Angelos D. Keromytis, and Suman Jana. "Slowfuzz: Automated domain-independent detection of algorithmic complexity vulnerabilities." In Proceedings of the 2017 ACM SIGSAC conference on computer and communications security, pp. 2155-2168. 2017.

[4] Lemieux, Caroline, Rohan Padhye, Koushik Sen, and Dawn Song. "Perffuzz: Automatically generating pathological inputs." In Proceedings of the 27th ACM SIGSOFT international symposium on software testing and analysis, pp. 254-265. 2018.

We really appreciate your time and effort in reviewing our paper and giving us constructive comments. We address your comments and questions in the following.

Q1: The proposed method relies on availability of slow and fast inputs but the baseline used for utility experiments (EFFIE-LEARNER and PIE) do not rely on such constraints. Although the author clearly expressed this limitation, I think this dependency significantly reduces practical utility of the proposed approach.

We agree that the dependency on "fast/slow" inputs needs clearer explanation and will improve this part in the next iteration of the paper. WEDGE mines contrastive pairs once per program from whatever tests are already available and come with the target (e.g., unit tests). If the target program comes with no tests, one can bootstrap it by generating valid test/inputs using a fuzzer. In both cases, such contrastive inputs do not necessarily have to be performance-stressing, as long as they provide diagnostic hints to help LLMs to quickly localize the program points to stress. In the worst case, this independent stage can be as easy as a simple prompt, which makes it more practical, or it can rely on specialized profilers for a more accurate diagnosis. In fact, our evaluation simply leverages CodeContests tests for correctness evaluation, not performance.

Q2: Utility experiments with EFFI-LEARNER use top-5 slowest inputs from less than ten available tests. How does it compare to fuzzing without constraint generation?

Good question. Following the setting in our utility experiment in Table 2, we added the experiment by using the top-5 slowest inputs generated by plain AFL++, and integrated these tests into EFFI-LEARNER to measure the improvement it brought. Due to the limited time frame, we subsample 14 problems for this experiment.

Using AFL++ tests’ execution profile as the prompt leads to substantially decreased optimization performance. Wedge’s tests lead to the optimized program to execute 45.33% fewer instructions compared to the original program, while AFL++ only achieves 14.8%. We attribute this observation to the Wedge’s generated tests being more performance-characterizing than those of AFL++. We are working on scaling the experiment to the full set and repeating the running 5 times to mitigate randomness.

Q3: Given a performance constraint can be synthesized, can LLM improve the code given the performance constraints as prompt (without generating additional inputs)?

This is a very interesting suggestion. Conceptually, PC constraints alone can already characterize inefficient implementation (e.g., data structure access time complexity), though not as concrete as execution feedback. However, it is unclear how LLMs consume such information when tasked to optimize the code. To this end, we conduct a few case studies using the samples instrumented with interesting and informative constraints (see Appendix in the paper).

Specifically, we used the 5 programs from our appendix that discuss the case studies, where the PC-constraints (pcc) are readily available for reviewers to check in the appendix. As a baseline method, we asked LLM to optimize the original program, without providing PC-constraints (LLM optimized no pcc). We then asked LLM (in a new chat) to optimize the original program while providing pc-constraints (LLM optimized w/ pcc). We made the following observations.

Observation #1: Mixed results, in 3/5 cases, with or without PC-constraints, the program is optimized in a similar way, so PC-constraints don't help or hurt.

Observation #2: In 1/5 cases, PC-constraints appear to hurt the optimization, but a more in-depth analysis shows that the LLM using PC-constraints actually optimizes the program in a lower/better complexity class, but since the parameters are small, the "less optimized" version runs faster on the "average" case.

Observation #3: in 1/5 cases, both optimized versions have logic bugs in how they optimize and re-implement the original algorithm; This is the largest program provided to LLM out of all 5 (~100 vs ~50 LoCs)

Our preliminary case study cannot confirm that using the performance constraints directly as a prompt can improve code optimization, as opposed to the execution feedback, as shown in our experiments for Q2.

Q4: The improvements are measured using CPU instructions which may not directly translate to overall performance improvement of a program (for example, if the program bottleneck is memory usage). It would be interesting to how the results compare to execution time based performance numbers.

Due to space limitations, we reported physical running times for our experiments in Appendix B.1. We will label them more clearly and add an explicit forward reference in the main body of the paper. These results are summarized in Table 4, and the trends are consistent with the instruction count results in Table 1. We use instruction counts as the primary metric because it has a much lower variance, as shown by prior work [1] and by our own measurements. Our experiments observe ~0.03% variance for instructions versus ~12% for physical running time, which can be influenced by I/O, background tasks, and scheduling noise, particularly for I/O‑bound programs like ours.

WEDGE is agnostic to the metrics used. Any per-input cost calculation can be used to inform contrastive pair mining and the fuzzer's input mutation engine. For example, if memory behavior is the bottleneck, the instruction counts can be replaced with metrics like peak memory usage, heap bytes allocated, allocation count, cache‑miss events, or garbage-collection time without changing the workflow of our tool. However, we do note that adopting those types of metrics may require additional instrumentation or specialized tools like memory profilers. Also, note that the metric itself only affects the running time of the programs under test, while everything else (prompting, PC-constraint generation, instrumentation) remains unaffected.

[1] Liu, Jiawei, Songrun Xie, Junhao Wang, Yuxiang Wei, Yifeng Ding, and Lingming Zhang. "Evaluating language models for efficient code generation." arXiv preprint arXiv:2408.06450 (2024).

We thank the reviewer for your time and effort in reviewing our paper and providing constructive comments! We have used an anonymized GitHub to link to our code: https://anonymous.4open.science/r/wedge-617E/README.md

Q1: What is the cost in time and tokens? Quantify the average cost (in tokens/runtime) per test case

Thanks for pointing out this important question. We break the cost down for different stages as follows (per solution program):

We will include the results in the updated version of the paper.

Q2: The paper is somewhat narrowed down to a specific domain and the evaluation is focused on competitive programming-style problems

Thanks for pointing this out. Our key motivation stems from the observation that the emerging real-world use of LLMs for optimizing code efficiency [1,2] does not match the existing evaluation practices (largely based on correctness tests or length-stressing tests).

Narrowed down to a specific domain. In terms of the scope, we observe that LLMs for code optimization have been related to many recent seminal efforts [3,4], let alone the significant body of research papers on LLM for compiler optimization. However, we understand this can be subjective, and there is a great gap between their testing requirements. We will add the discussion correspondingly in the paper.

Focus on competitive programming-style problems. We absolutely agree that moving beyond competitive programming-style problems for evaluation is exciting [4]. We cautiously believe that the unique design in Wedge, which decouples global test input generation from local performance bottleneck reasoning, makes it a promising solution for project-level performance testing. Recall that PC-constraints are small predicates over local program states that, when true, tend to indicate the code reaches an inefficient state (e.g., "array nearly sorted so partitioning degenerates", "graph has high-degree nodes", "regex causes computationally expensive backtracking"). If we move from competitive programming-style problems to, say, a compression library (which uses sort and graph-like data structures), Wedge’s decoupled workflow remains the same: synthesize a local predicate, then guide a fuzzer to generate inputs towards satisfying it. We will add studies to extend Wedge for project-level performance testing in the next version of the paper.

[1] Rina Diane Caballar. “Python Profiler Links to AI to Improve Code Scalene identifies inefficiencies and asks GPT-4 for suggestions”, https://spectrum.ieee.org/python-programming

[2] Lin, Hannah, Martin Maas, Maximilian Roquemore, Arman Hasanzadeh, Fred Lewis, Yusuf Simonson, Tzu-Wei Yang et al. "ECO: An LLM-driven efficient code optimizer for warehouse scale computers." arXiv preprint arXiv:2503.15669 (2025).

[3] Novikov, Alexander, Ngân Vũ, Marvin Eisenberger, Emilien Dupont, Po-Sen Huang, Adam Zsolt Wagner, Sergey Shirobokov et al. "AlphaEvolve: A coding agent for scientific and algorithmic discovery." arXiv preprint arXiv:2506.13131 (2025).

[4] Ouyang, Anne, Simon Guo, Simran Arora, Alex L. Zhang, William Hu, Christopher Ré, and Azalia Mirhoseini. "Kernelbench: Can llms write efficient gpu kernels?." arXiv preprint arXiv:2502.10517 (2025).

Q3: The authors do not explore the generalizability to real-world systems or codebases is not explored.

We acknowledge that our experiments in the current version do not cover large-scale codebases. However, we believe a few straightforward changes can enable our tool to handle such scale:

1. The AFL++ fuzzer in Wedge can be swapped for a fuzzer that operates at the function/API‑level [1,2,3] or computes a slice around a target function [4].

2. Wedge would synthesize PC‑constraints for each target function and instrument the function following our original setup.

3. Wedge additionally sets the checker as the coverage objective [5] or relies on path pruning [6,7] to remove unreachable paths.

4. WEDGE currently uses end-to-end performance counters as a metric, but this can be changed with more sophisticated objectives, such as a multi-dimensional vector of execution counts for basic blocks [8].

[1] Babić, Domagoj, Stefan Bucur, Yaohui Chen, Franjo Ivančić, Tim King, Markus Kusano, Caroline Lemieux, László Szekeres, and Wei Wang. "Fudge: fuzz driver generation at scale." In Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pp. 975-985. 2019.

[2] Sherman, Gabriel, and Stefan Nagy. "No Harness, No Problem: Oracle-guided Harnessing for Auto-generating C API Fuzzing Harnesses." In 2025 IEEE/ACM 47th International Conference on Software Engineering (ICSE), pp. 775-775. IEEE Computer Society, 2025.

[3] Serebryany, Kostya. "{OSS-Fuzz}-Google's continuous fuzzing service for open source software." (2017).

[4] Murali, Aniruddhan, Noble Mathews, Mahmoud Alfadel, Meiyappan Nagappan, and Meng Xu. "FuzzSlice: Pruning false positives in static analysis warnings through function-level fuzzing." In Proceedings of the 46th IEEE/ACM International Conference on Software Engineering, pp. 1-13. 2024.

[5] Böhme, Marcel, Van-Thuan Pham, Manh-Dung Nguyen, and Abhik Roychoudhury. "Directed greybox fuzzing." In Proceedings of the 2017 ACM SIGSAC conference on computer and communications security, pp. 2329-2344. 2017.

[6] Srivastava, Prashast, Stefan Nagy, Matthew Hicks, Antonio Bianchi, and Mathias Payer. "One fuzz doesn’t fit all: Optimizing directed fuzzing via target-tailored program state restriction." In Proceedings of the 38th Annual Computer Security Applications Conference, pp. 388-399. 2022.

[7] Huang, Heqing, Yiyuan Guo, Qingkai Shi, Peisen Yao, Rongxin Wu, and Charles Zhang. "Beacon: Directed grey-box fuzzing with provable path pruning." In 2022 IEEE Symposium on Security and Privacy (SP), pp. 36-50. IEEE, 2022.

Q4: I don't like that each solution requires profiling, prompting and instrumentation.

Thank you for raising this concern about the overhead. We wish to clarify that most of these costs are incurred only once per target program in an offline setup phase. The remaining costs are limited to small compile‑time overhead when instrumenting the target programs with synthesized checkers. To collect execution profiles and mine contrasting input pairs, we only need to run the program on a predefined set of tests once at the beginning. This is an offline, per‑target step that produces reusable profiles across fuzzing campaigns and LLM model iterations. Similarly, Wedge prompts the LLM once per target program, at the beginning, to synthesize PC‑constraints, its checkers, and the custom, constraint-aware mutators, and instrument the target programs. All subsequent runs and fuzzing campaigns will amortize the costs. Considering the generated tests will be fixed for future use, we believe the one-time cost of these steps is reasonable. We will add the discussion in the next version of the paper.

We are grateful for your time, effort, and leaving encouraging comments. We address your comments and questions in the following.

Q1: How generalizable is this method to more complicated projects compared to single programs?

We do not attempt to overclaim Wedge can generalize to complicated projects without empirical evidence. However, Wedge’s reliance on fuzzing that readily supports large projects and its design in constraining LLMs for local performance constraint reasoning makes it promising to generalize to larger projects. Specifically, Wedge can be applied to generate performance constraints at the local function- or slice-level [1] of the project. Such a local reasoning avoids relying on LLM’s limited capabilities in long-context reasoning [2, 3, 4, 5], while fuzzers bridge such gaps to enable global input search for both whole-project or library testing [6]. In addition, optimizing at the local code context can still benefit the entire project [7, 8, 9].

Our main experiments are motivated by the emerging attempt to use LLMs for optimizing code efficiency based on existing code benchmarks. Their evaluation, however, is largely based on the benchmark’s existing correctness tests or length-stressing tests. We totally agree that project-level performance evaluation is exciting and can require more agentic design [4]. We will add studies that extend Wedge for project-level performance testing in the updated version of the paper. We appreciate the comments, which give us the opportunity to further clarify the advantages of Wedge’s design.

[1] Murali, Aniruddhan, Noble Mathews, Mahmoud Alfadel, Meiyappan Nagappan, and Meng Xu. "FuzzSlice: Pruning false positives in static analysis warnings through function-level fuzzing." In Proceedings of the 46th IEEE/ACM International Conference on Software Engineering, pp. 1-13. 2024.

[2] Liu, Tianyang, Canwen Xu, and Julian McAuley. "Repobench: Benchmarking repository-level code auto-completion systems." arXiv preprint arXiv:2306.03091 (2023).

[3] Jimenez, Carlos E., John Yang, Alexander Wettig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik Narasimhan. "Swe-bench: Can language models resolve real-world github issues?." arXiv preprint arXiv:2310.06770 (2023).

[4] Shetty, Manish, Naman Jain, Jinjian Liu, Vijay Kethanaboyina, Koushik Sen, and Ion Stoica. "GSO: Challenging Software Optimization Tasks for Evaluating SWE-Agents." arXiv preprint arXiv:2505.23671 (2025).

[5] He, Xinyi, Qian Liu, Mingzhe Du, Lin Yan, Zhijie Fan, Yiming Huang, Zejian Yuan, and Zejun Ma. "SWE-Perf: Can Language Models Optimize Code Performance on Real-World Repositories?." arXiv preprint arXiv:2507.12415 (2025).

[6] Serebryany, Kostya. "{OSS-Fuzz}-Google's continuous fuzzing service for open source software." (2017).

[7] Rina Diane Caballar. “Python Profiler Links to AI to Improve Code Scalene identifies inefficiencies and asks GPT-4 for suggestions”, https://spectrum.ieee.org/python-programming

[8] Bala, Vasanth, Evelyn Duesterwald, and Sanjeev Banerjia. "Dynamo: A transparent dynamic optimization system." In Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, pp. 1-12. 2000.

[9] Sasnauskas, Raimondas, Yang Chen, Peter Collingbourne, Jeroen Ketema, Gratian Lup, Jubi Taneja, and John Regehr. "Souper: A synthesizing superoptimizer." arXiv preprint arXiv:1711.04422 (2017).