WEDGE: Synthesizing Performance Constraints for Evaluating and Improving Code Efficiency
Authors: Jun Yang
Cheng-Chi Wang
Bogdan Alexandru Stoica
Kexin Pei
Venue: NeurIPS 2025 poster ()
Keywords: Large Language Models
Test Generation
Code Analysis
Performance Analysis
Code Optimization
Fuzzing
Primary area: applications
TL;DR: We combine LLM-synthesized performance-characterizing constraints with fuzzing to uncover difficult-to-find code inefficiencies and generate performance-stressing tests.

Abstract: Large Language Models (LLMs) have been increasingly used to optimize code efficiency. Evaluating their effectiveness and further suggesting optimization opportunities often rely on high-quality tests to demonstrate the performance bottlenecks presented in the program. However, existing approaches rely on a limited set of hand-curated inputs or LLM-generated uninteresting length-stressing tests, failing to reveal more nuanced optimization opportunities. We present WEDGE, a framework for generating performance-stressing input given the program under test. WEDGE synthesizes explicit performance-characterizing constraints in the form of branch conditions to partition the programs’ execution space into performance-specific regions. When integrated with the coverage-guided fuzzer, reaching different regions introduces explicit rewards for test generation to explore inefficient implementations. Our evaluation shows that WEDGE introduces a significant slowdown compared to the tests in CodeContests and those claimed to be optimized by existing approaches. From the utility perspective, integrating our tests substantially improves the existing code optimization approaches that rely on test-driven execution feedback. We release PERFFORGE, the performance tests generated by WEDGE, to benchmark future approaches for efficient code generation at https://github.com/UChiSeclab/perfforge.

WEDGE: Synthesizing Performance Constraints for Evaluating and Improving Code Efficiency
Jun Yang, Cheng-Chi Wang, Bogdan Alexandru Stoica, Kexin Pei {juny, casperwang, bastoica keek caeeicco.ccc..ooe.. edu Department of Computer Science, The University of Chicago
Abstract
Large Language Models (LLMs) have been increasingly used to optimize code efficiency. Evaluating their effectiveness and further suggesting optimization opportunities often rely on high-quality tests demonstrate the performance bot- tlenecks presented in the program. However, existing approaches rely on a limited set of hand-curated inputs or LLM-generated uninteresting length-stressing tests, failing to reveal more nuanced optimization opportunities. We present WEDGE, framework for generating performance-stressnn der test. WEDGE synthesizes explicit performance- performance-ccaracteriinn characterizing constraints in the form of branch conditions to partition the programs' execution space into perfornance-speccfiic regions. When integrated with the coverage-guided fuzzer, reaching different regions introduces explicit rewards for test generation to ex- plore inefficient implementations. Our evaluation shows that WEDGE introduces a significant slowdown compared to the tests in CodeContests and those claimed to be optimized by existing approaches. From the utility perspective, integrating our tests substantially improves the existing code optimization approaches that rely test-driven execution feedback. We release PERFFORGE, the performance tests generated by WEDGE, to benchmark future approaches for efficient code generation at https: wtwphh/ww.oo///cccceeeaaaaeeeeee
imput given the program un-
Introduction
Large Language Models (LLMs) have shown intriguing promise in optimizing code efficiency beyond compiler techniques [1-9]. Evaluating the effectiveness of these LM-based code optimizations relies on perforraanee-tteessingg tests. For example, optimization from recursion iteration in Fibonacci number calculation incurs only a negligible performance improvement when evaluated with a default test (n 3) that focuses testing correctness, while performance-stressine input (n 40) reveals the orders (109 of the larger gap. Moreover, as some approaches integrate execution feedback further optimize the code [3, 10], running performance-stresiin tests reveals more precise optimization opportunities by exposing performance bottlenecks.
Unfortunately, most existing code optimization approaches still leverage correctness tests to evaluate and suggest optimizations [3, 5, 7]. However, the correctness tests alone are often insufficient to expose the inefficient code implementation. For example, existing tests in the common benchmarks, e.g., Human [11] has been shown to have limited scope and low complexity and thus fail to adequately stress the code performance against more demanding conditions [12]. As result, they also more susceptible to the noise introduced in the execution environment, thus failing to reliably quantify the optimization and reveal insightful optimization opportunities.
To generate performance-stressinn tests, recent works have started to leverage LLMs by prompting them to generate test generators [12]. For example, EvalPerf [12] introduced a scale parameter to control the input size, with the assumption that it is the key determining factor for performance-
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Cantracive Execation Profllng
PC- Constraiin Syatheis
PC-Candraint Guided Burring
Taut Ingur
Profic-
Perfermance
checker imprrmemaaion
PG-enddraints coverage %
Code under lot
PerfForge
Profle
E
mutalar
Conerage-grsaat
Workflow of WEDGE. First, our tool profiles the code-under-test identify a pair of inputs with contrastive execution profile ("fast" vs "slow" execution). Second, with this information, it asks a LLM to infer cefoommnne-cchaacttriiin it runs the instrumented code through customized fuzzing tool to find performance-stee -tresssing inputs.
Figure 1:
constraints and instrument the code with checkers. Third,
stressing. However, such a biased preference over large tests misses the opportunity to reason about their relationship to inefficient program behaviors beyond the size. For example, calling quicksort can suffer from the suboptimal performance [13] when its input is reversely sorted (O(n²) in the worst case). When two inputs are both at the maximum length the reversely sorted one is more stressing than another randomly ordered one (O(n log n)) on average.
Our approach. We present WEDGE, a framework that generates performance test inputs beyond simply stressing the sizes. Our key insight that the limitation of LLMs in generating performance- stressing tests boils down to the inherent challenge of connecting the local performance-relate program behavior all the way back the program inputs [14, 15], while directly reasoning about the local behaviors is comparatively easier. For example, we can easily specify the local variable arr, the argument to a quicksort deeply nested inside the program, to be reversely sorted to trigger its inefficient behavior, while predicting what program inputs lead arr to be reversely sorted is more challenging as that requires reasoning about the control and data flow based on the precise understanding of the program semantics. Such reasoning is extremely challenging due to the overwhelming search space, e.g., tracking a combinatorial number of program paths [16, 17, 14, 18].
Based on such insight, WEDGE alleviates LLM reasoning on performance-related behavior by asking it synthesize the performance chhraccccign constraints as condition checkers, e.g., all (1[i] > 1[i+1] for i in range (1) and instrument the program with these checkers at the appropriate program points. WEDGE then leverages the coverage-guides fuzzers, the search-based testing technique [19, 20] with the goal to maximize the code coverage, to scale test input generation that sidesteps the expensive iterative queries to LLMs. As the inputs achieving new coverage are rewarded and prioritized in the fuzzer, checker branches inserted by WEDGE serve as the coverage signal to bias the fuzzing to generate likely-stressing inputs more efficiently.
To enhance performance constraint reasoning, we develop a reasoning template that elaborates on the procedures contrast the pair of disparate execution profiles to gain insight into inefficient implementations. We then instruct the LLM to reason about performance constraints (in natural language and code) in multiple phases localize the appropriate program points and implement the corresponding constraint checkers. Besides guiding the fuzzer using constraint checkers, WEDGE further accelerates the input search by replacing the fuzzer's default input mutator [19] with a constraint-aware one that steers the input mutation towards likely constraint- inputs, while also enforeing the mutation to respect the input grammars [21-24] Figure 1 presents our workflow (see Section 3 for details).
Results. Our extensive evaluation shows that the tests generated by WEDGE are substantially more performance-streesing than the default ones in the existing benchmark and those generated by the state-of-the-ard techniques [12, 25] by 84.5% (vs. (VALPERF'LOw) With more stressing tests, WEDGE precisely pinpoints the potential inefficient implementations and thus introduces approximately 10 percentage points more efficiency improvement on the generated code than that of default tests when used to guide the iterative code optimization approaches via test-driven execution feedback [3]. Our ablations confirm the effectiveness of the synthesized constraints guiding the fuzzing and input mutation, i.e., achieving 4x improvement over plain fuzzing using AFL.+ In addition, we show that the generated constraints effectively characterize the performance, where the constraint-satisfyine inputs are 38.6x slower than constraint-voolating inputs.

---

2
Overview
We start with an overview of existing works on code efficiency evaluation and stress test generation. We then use an example to demonstrate the advantage of WEDGE over the existing approaches.
2.1 Benchmarking Code Efficiency and Performance-Stressing Test Generation
While traditional code generation primarily focused on generating correct code [26-28, 11, 29-321. there are growing efforts generate efficient code beyond correctness [5, 12, 33, 34]. However, existing efficient code generation techniques still largely rely on correctness tests to evaluate the performance improvement [5, 7, 35], which cannot faithfully measure the performance improve- ment [12, 34, 33, 9]. Some of them rely on the execution feedback to further optimize the code [7, 9]. These approaches can miss optimization opportunities when the tests do not reveal the performance bottleneck (see Section 4.3).
To address these challenges, recent works have focused on performance test generation benchmark efficient code generation [36-38, 33, 34, 8, 12]. However, these approaches either generate infeasible inputs that do not stress and thus rely on manual correction, or their task formulation often prevents the LLM from reliably reasoning about the program behavior, i.e., by directly prompting the LLM to generate the stressing imputs for the entire saannnnnnn program. With such nontrivial task, LLMs have to identify the inefficient implementation, understand the run-time behavior to exercise it, and reason all the way to program inputs. Therefore, they often end up taking "shortcuts" and reduce to only generating Siggt-stresssig inputs that fail to reveal more intricate inefficient implementation.
In addition to performance benchmarking using extends the evaluation to repository-leve and real-world workloads by prompting an LLM with the performance--ptimiizngg commit. It shares the high-level idea of direct prompting but requires more challenging inter-prot iieeeprrceeuual analysis across much longer context [40, 41]. WEDGE complements the direct prompting approaches for performance testing by decomposing the test generation into local code behavior reasoning and efficient input search.
peapptitive-rrgrrmminng level code, GSO [39]
Performance testing has been studied extensively before I.LM-based approaches based on symbolic execution and fuzzing [13, 25, 42-44). While the former can suffer from poor scalability, the latter can also incur expensive instrumentation for collecting and parsing profiling information, e.g., customized coverage metrics and scheduling algorithms to guide fuzzing and input search, and can lack test oracles precisely capture inefficient behaviors or symptoms.
WEDGE restricts LLMs to focus exclusively on local relying on the LLMs to reason globally about the input, while leveraging efficient input search from fuzzing. Therefore, it captures the inefficient behaviors without expensive profiling and explicitly encourages test generation towards reaching inefficient implementation beyond being length-stressing
constraints to avoid
2.2 Motivating Example
Let us consider an example from CodeContests, Codeforces problem 633A [45] (gray box, Figure 2). Given three integers a, b, and c (1 S a, b < 100, S c S 10, 000), the goal is to decide whether This problem is classically known as finding solutions to a two-variable linear Diophantine equation [46].
there exist neg-ntgative integers x, y such that b- y
The code snippet (blue region) shows an implementation that solves this problem. The code system- atically tries every pair of values by iterating two nested loops over fixed upper bounds of 10, 000 (lines 6-7), computing the value of the Diophantine equation, and checking whether it is equal or exceeds c. Because the loops use fixed upper bounds rather than adapting to the value c, the code could examine nearly the entire 10, 000 value space. Apart from skipping sums greater than or breaking once a match is found (lines 9-11), the code bears the full brute-force cost.
The right half of Figure 2 (green and purple boxes) shows how WEDGE infers performance- characterizing constraints specific to this program, inspired by the contrasting execution traces that share similar inputs but have disparate behavior (manifested by the per-statement execution counts). In particular, our tool identifies specific relations among the local variables a, b, c to stress the nested loops to exhaust their maximum iterations. The green box shows the LLM's 's reasoning
3

---

Problem Statement:
Performance- hhtaaaamcc-Chaarrttiiiinngg Constraints Reasoning:
Dasic ctasaed a fight "The Seriie" Beline can falt bue two gane, therr hvery, each them perfer not-repitve numbe Bereney buller that the shoeld Eieeey dials smits damage wiile Ivery deak unis camaage tmakk the shield Dosts has to deal sxnctly a units damage, Find out if posile.
be seads slickls
Phane ideatity Eapeasire or Indficizat Code Segrants
Compatoon of Lieedave Hir Counte:
-I in (Drrr coep sy -Liee 7 (Ioee Leop ever 3%
Inget
The firt of the ispet comtine three
100, 10,000)
The inlonis
Plapoiniing Line with Sigsifioutt Defferratiation:
a hevvily stroed under the doww costiibttr the sleedoon
Ouiput
doraage shickd
Slow input:
667
Past imput:
766
Profll-Amnotared Code
AA resh, when cofff are uch Out early break occurs to with the doe iulot the loope dorre Hough a arge number combrration...
gelaakees
prggan impleners
check equals
seach -..
slow has:
lfaut, hic:
Rinclude dbico/stdort..l h> int maint)
alow bat:
Izast hat:
slow alov_bit:
slov_hits hit:
lifet_hia hit:
faat_hitt hat:
14
13
int Elug 0:
int. a, b, o,
Phase 2. Derive Pet fechianee Charactediing Conttraies Imaariaee haeficiont lirrgtin for Conbinations 1ibagra and b are lighis that de onlly contling to saro fe. ggod bi"
slow hit:
hitst_hit:
5
for (" bd 'd"', so. db, Gel.
#low hat: 10002
slow hit: 100030002
hats
hit: 10003
30000: x041
10000;
divide "e"), de hop qarly is rarge vifieceate
slow 1000200011
hitz
satt_bit:
clag
Constraint Checker Implementation
hit:
hit:
Check greatest conson divisoc
aitv_bit: 10001
hat:
(clag breaks
I/ a and is does not divide
aitv_bit:
bat:
:35
check
a, jok
slow hit:
slow_hit:
ffast hat:
Fast bit:
!17
136
("
(tlag en 31
if ( o godit, 044 god(a,
slow bit:
itast hatet_hit:
alse
ec "Mazning: god invarient trippuzed
slsw_bits bit:
haatt_hit: hit:
119
printe("No'];
slow slow_hits hit:
hitt
120
return 6
hit:
ifest_hit:
21
Figure 2: Motivating example from Codeforces (prob. 633A, sol. 622) showing how WEDGE reasons about and generate performance--haaacceriiiii constraints, and implements corresponding checkers.
process, while the purple box shows the checker by the LLM to be instrumented in the program.
constraints synthesized as C++
Our key observation is that these constraints are more local, fine-grained, easier generate, and cannot be captured by state-of-the-art techniques (e.g.. [12, 34, 25]), which focus primarily on maximizing the input values and size. Therefore, such performance-stressinn more appropriate interfaces for LLMs to communicate their reasoning to the existing test generation tools than directly asking them to generate performance--treesing inputs.
constraints serve as
WEDGE Framework
Problem Statement We formally define the cerffoommnnnesttesssinn test generation problem. Given program P accepting a valid imput (conforming to validity specification V), the set of all valid inputs denoted as Iy. With a valid input Vi Iv, the execution of P (denoted as E, = P. yields an execution time T, The goal of stress test generation is to generate a subset of valid inputs 1" C Iy, such that the average execution time of /" is maximum.
At a high level, WEDGE takes as inputs a coding problem statement S, correct solution program P. set of default correctness tests ID. and an Large Language Model (LLM), and produces a set of parformance-stressiinn test inputs 1: WEDGE(S, P, PPID. LLM).
3.1 Contrastive Execution Profiling
We first collect high-quality contrastive execution feedback from fast and slow exccutions to facilitate reasoning about ceaermannce-caaaatttiiiiii constraints. This is achieved in two steps.
Contrastive input pair mining. WEDGE runs P against set of user-provided tests Ip, e.g., existing correctness tests provided by the dataset to mine a contrastive (slow, fast) input pair (istow ff
For elarity, we use "execution time" here to represent the execution cost, but in experiments we use the number of CPU instructions. See justification in Section 4.1

---

Note that istow does not have to be performance-streesingg the pair needs only provide con- trastive diagnostic hints to help localize potentially inefficient implementation, i.e., the performance bottleneck.
During test execution, WEDGE collects the execution cost of each input, measured by the number of executed instructions (denoted [Z] in our experiments). WEDGE then mines the contrastive input pairs based on the two metrics: (1) similarity defined as the sum of the match ratio (i.e., the number of common array elements divided by the length of the shorter array) and the Jaccard similarity [47], and (2) execution cost ratio, defined as the ratio of the slow input's 's cost [llo to that of the fast input | fast- Input pairs are then ranked based their similarity and execution cost ratio, and WEDGE selects the top-ranked pair as the contrastive input pair (istow: ffast)
Profiling feedback collection. WEDGE executes P with islow and fast, collecting execution feedback (coverage and hit count) F Fstow and Fasee. Considering such a contrastive execution pair provides the key behavior insight [48], we prompt LLM to pinpoint the differences reason why one input leads to significantly slower execution.
3.2 Performance-Characterrin Constraint Synthesis
WEDGE generates the constraints in two steps: it initially generates the constraints C in natural language, then prompts the LLM to implement the corresponding constraint checkers and insert them to the fuzz driver P to produce the instrumented fuzz driver P'.
Performann--characttiiiie constraint reasoning. A constraint a predicate on the program
state (e.g.. variable values) and expressed conditional statement, e.g., if (n > 1). Given performance-charactrriiii constraint e and a given set of inputs Zy, some inputs may satisfy the constraint while others may not. We denote them as Ig and Ix. respectively, where Iy Ig J JIv and the corresponding average execution time Ts > TN-
WEDGE first constructs comprehensive performance reasoning prompt template that con- tains the problem statement S, solution program P, contrasting input pair (istow; ffatt) the profiling feedback information Fstow and faastt and multiple manually-crafted constraints as few-shot examples. The performance constraint reasoning technique can be denoted as: Reason/ery(LLM,, S, P, (istow, ifast), (Fstour: Frast)) C, where C {ca {cr) is set of gener- ated constraints. The template explicitly instructs the LLM to reason about performance constraints in multiple phases, as shown Figure 2. In Phase 1, the LLM needs to identify expensive inefficient code fragments. This includes: 1) comparing line-level profiling information, e.g., hit counts, between the fast and slow runs, 2) pinpointing lines or functions that get significantly more hits under the slow input, and 3) inferring how these lines might interact with data structures, loops, recursion, etc., especially as they relate to the input constraints (e.g.. n 100). Phase the LLM will derive performance-characteo characterizing constraints in natural language. By enforcing the LLM to reason about the constraints with Chain-of- Thain-of-Thought prompting [49], WEDGE collects insights into performance and generates high-quality constraints C (Figure 2 green part).
Constraint checker implementation. WEDGE prompts the L.LM with the constraints C and instructs it to implement the checker code faithfully and produce the instrumented program. The instrumented program with inserted checker code P', will be used as the target program to fuzz: p' = Instrument(LLM, P, C).
3.3 Performance-Charatteiine Constraint Guided Fuzzing
In this stage, WEDGE launches coverage-guided fuzzing against the instrumented program P' to search for constraint constraint-satisfying inputs.
Constraint-aware mutator generation. WEDGE uses AFL++ as its fuzzing engine. How- ever, the default mutator of AFL+ (denoted as Mp) targets at binary fuzzing (including operations like bitflip, byteflip, crossover, etc.), having no knowledge straints, thus could generate mostly invalid inputs. We implement a custom input-grammar- and constraints-aware mutator Mc by prompting the LLM with mutator examples, problem state- ment S (i.c., validity constraint V), solution program P, contrasting input pair (istow: ifast),
input validity con-
5

---

the profiling feedback information (Fstom, fast) and the generated performance constraints C: Me. = MutatorSynnLLM, S,P, (fstow; ( (Sstow; fast)) C).
Mutator generation is more challenging than EVALPERE [12] and the input generator's generation [3, 34, 8], as it has to be robust enough to make sure the mutated inputs follow the validity constraints and meanwhile as diversified as possible. To resolve this challenge, WEDGE follows an iterative generate-and fix fashion to ensure the robustness of mutators. We put more details in Appendix A.2 due to the space constraints.
Constraint-guided fuzzing. Once mutators are generated. it launches a fuzzing campaign using the mutator Mc on the instrumented program P', collecting all tests generated by fuzzer, i.c., CGF(Me, P') I, where I {di, d2.... are the fuzzer generated tests. In the end, the tests generated by WEDGE form our benchmark PERFFORGE.
4
Experiments
4.1
Setup
Test generation baselines. We evaluate PERFFORGE tests (generated by WEDGE) against the following three representative baselines (two -Ls-d and one fuzzing-based): EVALPERF [12]. which uses LLMs to synthesize a parameterized input generator controlled by the input size parameter scale. Since EVALPERF requires one canonical program the reference implementation in the prompt, while our dataset has multiple ground-truth solutions per problem, we use the slowest and a randomly sampled solution as the reference implementation, forming two variants EVALPERFsLLOW and EVALPERFRAND TG-prompt [8, 34, 33], direct prompting technique following recent works [8, 34, 33] which instructs an LLM to directly synthesize the performance test generator given the problem specification. PerfFuzz [25], which is state-of-the-art performance fuzzing tool that uses performance- coverage metric that tracks the hit count of each control flow graph edge in the target program to search for inputs that either reach new edges or hit known edges more.
Utility baselines. To measure the utility of our generated tests, we consider two scenarios that PERFFORGE can help. The first scenario is to provide execution feedback to help LLMs further optimize the code. We consider EFFI-LFARRER [3], an iterative code efficiency optimization based on test-driven execution feedback to guide the L.LM in refining its generated code. The second scenario is to evaluate (ideally more precisely) existing code optimization approaches. We consider running PERFFORGE against PIE [5], an LLM-based code optimization that finetunes the LLM on slow and fast code pairs, which relied on correctness tests to evaluate its performance improvements.
Metrics. We primarily rely on CPU instruction count to measure the effectiveness of PERFFORGE tests, considering it is more stable across runs, platform-agnostic and strongly correlates with performance bottlenecks [50-53], while physical time is more prone to interference and noise [54, 51]. It is also one of the key metrics for evaluating LLM-based code testing and optimization tools [12, 34, 5] (more details in $A.5).. To further reduce the noise, we average the CPU instructions over five runs for each program throughout all experiments.
Dataset. We evaluate WEDGE on CodeContests [32] with a wide range of competitive programming problems and human- written solutions. Test cases include the default inputs from the original open- judge platforms as well as additional inputs generated by the authors [32]. We largely focus on C++ solutions to ensure comparable measurements, with small subset of Python programs for the usefulness investigation (Section 4.3). We rank the problems based on the coefficient of variation [12] of the CPU instruction counts and select the top 300 problems. This ensures the selected problems feature diverse solutions and potentially have enough room for optimizations for part of the solutions. WEDGF, generates tests for 207 of them, but after excluding those where baselines cannot produce valid inputs, we arrive at 154 problems and 33,020 C++ programs.
Fuzzing and input filtering. To collect inputs, We run WEDGE'S fuzzing (based on our modified AFL++) for one hour for each solution in parallel. Not all generated inputs strictly conform to the validity constraints V (Section 3). WEDGE applies a two-stage automatic filter to filter out likely invalid inputs. WEDGE first prompts an LLM to generate the validator based on the problem statement and use the official tests in CodeContests to check the validity of the validator. WEDGE then checks

---

Table 1: WEDGE versus baselines (described in Section 4.1) and its ablation.
# of instructions (x 10*)
Slowdown CC
Technique
Win rate
Average
Median
Average
Median
Compare baselines
WEDGE
5.96
0.75
60%
363x
1.65x
TG-prompt
3.87 (11.5x)
0.60 (11.3x)
12%
275x
1.52x
PeriFuzz
3.29 (J1.8x)
0,43 (11.7x)
11%
149x
1,61
EVAL.PERFsLO PLRF
3.23 (11.8x)
0.44 (L117x)
8%
146x
1.63
EVAL.PERFR.M
3.21 (11.9x)
0.45 (L1.7x)
9%
166x
1.54x
Ablations 0.75
WEDGE
5.96
65%
363x
1.65
WEDGENOINSIR
4.02 (11.5x)
0.21 (13.6x)
29%
159x
1.13x
WEDGEDEwALLMUT
1.54 (13.9x)
0,01 (L>75x)
4%
12x
0,99
AFL++
1.49 (14.0x)
0.01 ([>75x)
2%
30x
0.99
the output consistency across different solutions (labeled correct in CodeContests) under the same input, following the existing work [32]. Any input leading inconsistent outputs will be filtered out (detailed in Appendix A.3). After these, we rank the tests for each solution in the dataset based on the slowdown they introduce. We then select the top ten longest-running tests for each program and aggregate them as part of our benchmark, PERFFORGE.
4.2
Main Results
To evaluate the effectiveness of PERFFORGE tests in stressing performance, we compare the slowdown PERFFORGE brings to the programs against those by EVALPERF, TG-prompt, and PerfFuzz.
Table shows that tests generated by WEDGE lead programs to execute, on average, 84.5% and 85.7% (70.5% and 66.7% median) more CPU instructions than the two variants of EVALPERR. respectively. They also have 54% (25% median) more CPU instructions than TG-prompt. PERFFORGE tests dominate the number of programs (59%) where they run the slowest among all the other baselines (win rate). Figure visualizes the win rate by running head-to-head comparison between WEDGE and the baselines. We also compute the slowdown that the tests achieved over the default tests in CodeContests. On average, PERFFORGE tests outperform EVALPERF ones by 2.3x and TG IG-promphi by 1.3x. Figure illustrates head-to-head comparison between PERFFORGE and the baselines, where PERFFORGE'S tests slows significantly more programs compared to the other baselines. Analyzing physical running times reveals similar trends (see Appendix A.5).
We extensively analyzed the ccrarattccecccarartttiiiinggg constraints as well as the test generators synthesized by WEDGE and the other baselines and benchmarks. We observe that the inputs generated by WEDGE focus more on the inefficient implementation in the code identified by the performance- characterizing constraints, while those by EVAL are optimized to stress the input length specified the problem statement. TG-prompt, while not explicitly implemented to maximize bounds, faced challenges in reasoning about holistic program behaviors end-to-end Even with chain-of ofain--of-houuhh prompting, it still reduces to mostly generic length serett--ttessingg inputs specific to the problem statement (e.g., large large graphs for graph-based problems). We leave the detailed description of these qualitative studies &C due to space constraints.
Similarly, while PerfFuzz is designed to trigger worst-case behavior by favoring inputs that execute more control-flon graph's edges, we observe that PerfFuzz still ends up generating gength-stresseee inputs. Without explicitly identifying and exercising the performance-characterrii PerfFuzz can overlook inefficient implementations when guided only by the coverage of existing branches in the code and the profiler. This is because the existing branches in the code are often irrelevant to the efficient behavior, while the profiler may not capture the root cause of performance bottleneck, the input generated so far may not have exercised the inefficient implementation yet.
constraints,
We ablate the two designs related to performance-hharnttriiingg constraints: (1) guiding the mutator generation with constraints and (2) instrumenting the program with constraint checker code. For (1), we consider the AFL+ mutator as the baseline. For (2), we consider the original program in the baseline.
Ablations.

---

propra
Wormalond Banlo T44
Vermalitee Ratio Chl
Nommaloes Fadto (92)
(a) WEDGE TG-prompt
(b) WEDGE EVALPERFsL.Or
WEDGE vs. PerfFuzz
Figure 3: A head-to-head comparison between PERFFORGE and the baseline tests The bars represent the number of programs where one incurs a larger number of CPU instructions. x-axis shows the corresponding ratio between the corresponding CPU instruction counts. Since the two EVALPERF variants show similar distributions, we only include EVALPERFsL.ww here (see Section B.2).
Table 2: Running EFFI-LEARNER for code optimization using execution feedback from different
types test sets. PERFFORGE improves EFFI-LEARNER the most.
Total memory
Max memory usage (Mb)
Execution time (s)
CPU instructions
Test set
usage (Mb s)
GPT-4o
DS-V3
GPT-4o
DS-V3
GPT-4o
DS-V3
GPT-4o
DS-V3
None
15.66%
6.77%
21.70%
12.49%
2.78%
2.30%
31.39%
20.48%
CCactuutt
22.57%
12.29%
27.78%
20.43%
11.89%
1.93%
39.89%
35.01 %
PerfForge 26.47%
18.99%
35.10%
23.75%
11.82%
9.21 %
49.31%
40.26%
Table I shows that WEDGE'S generated tests are on average 48.3% and 128.3% slower (in terms of CPU instruction count and relative slowdown) than WEDGENOINSTR. showing that the instrumented programs with constraint checkers can effectively guide fuzzing. Similarly, WEDGE'S generated tests incur 287% more CPU instructions than those generated by WEDGEDEMULTMUr (with default mutator). On 63.02% solutions, WEDGE tests are slower than WEDGENOINSTR tests (with significance value of 0.05, base on Mann-Whitnes test [55]).
4.3 Utility of PERFFORGE
As described in Section 4.1, we investigate the utility of PERFFORGE by comparing PERFFORGE tests the default CodeContests tests (CCdetault) that only evaluate the correctness on (1) improving LLM-based code optimizations (EFFI-LEARNER [3]) based on the execution feedback, and (2) fairly measuring performance improvement where the baseline's 's evaluation relied only on correctness tests (PIE [5]). To ensure a fair comparison, we adopt the exact same evaluation setup and metrics used by the two baselines. For example, we include memory usage to evaluate how PERFFORGE improves EFFI-LEARNER. Since EFFI-L-EARNE relies on the original CodeContests tests, yet for about 15% problems have less than ten tests available, we instead use top-5 slowest tests per solution.
Improving code optimization with execution feedback. We collect corpus of 280 slow Python solutions from 56 problems PERFFORGE following the EFFI-LEARNER' filtering strategy. For optimize
each solution, we run AFFI-LFFARNER with three different prompts to let the code. (1) we use the solution code alone with no execution feedback (None). (2) we use code annotated with profiling information from running the original CodeContests default tests (CCasfault) (3) we use code annotated with profiling information derived from our PERFFORGE tests (PerlForge). We consider both OpenAI GPT-4o and DeepSeek V3 as the backends for EFFI-LEARNER.
Table illustrates that PERFFORGE tests achieves the best performance improvement LEFI-LEARNER can optimize the code to execute 24% less instructions (or approximately 10 percentage points), run 17% faster, and use 25% less memory on average when providing GPT-4o with PERFFORGE execution profiles as opposed their original setup. Similarly, EFFI-LEARNER can optimize the code to execute 15% less instructions, run 46% faster, and use 16% less memory when providing DeepSeck with the same PERFFORGE-driven execution profiles.

---

Table 3: Pie Experiment: average speedup and fraction of optimized programs, i.e., least 10% faster (%Opt) evaluated by different test sets following [5]. The top-performing test set is highlighted.
Speedup (Hinst)
Speedup (time)
Opll (#inst)
3Opt (time)
Test set
PIEn
PIE,
PIE,
PIEn
PIE.
PIEA
PIE.
PIE.
PIE,
PIEn
PIE.
PIE.
CCeefault
1.32
1.98
1.21
0.93
1.13
1.32
6.0%
16.2%
4.4%
16.6%
29.2%
56.5%
CCsww
1.30
1.85
1.21
0.94
1.13
1.32
5.5%
15.6%
4,4%
18.1%
27.9%
56.5%
PerfForge
1.62
1.99
3.01
1.18
1.29
1.38
12.1%
18.8%
30.4%
26.6%
41.6%
60.9%
Evaluating code optimization fairly. We show how PERFFORGE can measure performance improvement claimed by existing code optimization more fairly than the correctness test. To this end, we consider PIE [5]. a state-of-the-ar LLM-based code optimization based on finetuning, but relied on the default correctness tests to measure their performance improvement. We select their three most effective models (CodeLlama 13b) finetuned with the following different datasets: (1) HQ (high-quality) data annotated by the authors (PIEg): (2) ietooommaanccooditioonnnn C++ programs annotated with target optimization score reflecting its potential "peak performance" (PIE,); (3) all data from the entire PIE dataset. We then adapt our program selection to match the requirements PIE (details $A.1)
data to optimize
We follow the same set of metrics as [5] by measuring the average relative speedup between the original and optimized code in instruction counts and physical time, as well the percentage of programs that the LLM models can optimize by at least 10% O%tpt) [5]. Table 3 illustrates how our tests better characterize the performance bottlenecks. PERFFORGE outperforms the CodeContests default tests (CCaefaul) and its top five slowest tests (CCstow) ) by 24% to 149% in terms of instruction counts and by 5% 27% in terms of physical time. also helps discover that between 7% and 48% more programs have actually been meaningfully optimized and run at least 10% faster.
4.4 Sensitivity Analysis
Discriminative power of perfornance-chaaaccrriing constraints. To investigate whether and how WEDGE-generated performance-characctriiii constraints can indeed capture performancee-trresinng inputs, we select 810 programs CodeContest where both constraint-satisfying and constraint- violating inputs exist. Results show that constraint-satisfying inputs are, average, 38.6x slower than montrrint-violaaiin inputs. We conduct a Mann- Whitney test [55], and constraint vonstraint-satiifying inputs are significantly slower (with significance value p < 0.05) than constraint-violating inputs on 92.84% programs.
Impact of constraints in guiding fuzzing. To better understand the impact of guidance of con- straints (including mutator and code instrumentation for coverage guidance), we calculate the ratio of constraint-satisfyy inputs (out of valid inputs) per strategy. Result shows that the ratios of constraint-satisfying inputs among generated inputs of + WEDGE WEDGFNOINSTRR. and WEDGE are 40.42%, 41. 1.4,, 77.62%, and 80.48%, respectively. In other words, both involving performance-characttriiiiii constraints and constraint checker code contribute positively to the ratio of constraint-satiisfinng inputs. Furthermore, strategies that yield a higher proportion of constraint- satisfying inputs tend to achieve better performance (see Section 4.2), indicating that satisfying cha.aancccccaaarrriiiiigggg constraints correlates with the generation of more stressing test inputs.
Efffct of input size. We investigate how input size affects the effectiveness of PERFFORGE consider- ing that leveraging fuzzing to generate large inputs is a known challenging problem [25]. We observe our framework outperforms the baselines by larger margins when we further restrict the input size to be less than 1KB. In particular, for problems whose inputs are less than IKB, the slowdown achieved by WEDGE is 3x, almost double that on the entire problems without such restrictions, 1.5x. These findings underscore that the performance-stressinn designed to target iiteemmenattonsspecif bottlenecks rather than being simply length-stressing We put the detailed results in $B.3 due to space constraints.
characteristics of our tests stem from inputs being

---

5 Related Work
Performance fuzzing. A popular line of related work aims to trigger performance bugs by automati- cally crafting worst-case inputs [13, 25, 42-44, 56]. For example, SlowFuzz [13] and PeriFuzz [25] are feedback-drivee fuzzers that search for imputs causing extremely long exccution cost. Fuz- zFactory [56] generalizes this idea by allowing developers to define custom performance--rientee feedback metrics and integrate them into a fuzzing framework. These tools have been effective at uncovering inefficiencies related to algorithmic complexity or poor resource utilization. However, they rely on runtime instrumentation or heuristics (e.g., counters for loops or allocations) as well as specific performance hints or signals, often manually crafted, to guide the input search. WEDGE complements this line of research by automating the synthesis of diverse performance-charattrriiiz constraints the test oracle.
Performance bug detection. Numerous tools have been invented to detect performance bugs by identifying inefficient code patterns, costly loops, repeated computations, and suboptimal usage of data structures [57-65]. While WEDGE could be extended to detect performance bugs, focuses more translating the performance-stresse stressing symptoms into fuzzer-amenable constraints. There- fore, WEDGE focuses more on evaluating and improving cxisting LLM-based code optimization approaches, as opposed to finding performance bugs in large-scale systems.
LLM--sssisted test generation. growing body of research focuses on LLM-assisted test gener- ation [66-70, 38, 71, 22-24, 36, 72]. Most of these works leverage LLMs to directly generate the stressing imputs or the imput generators based on the code under test. This usually requires tracking and reasoning over long-range control and data dependencies in the program, posing significant reasoning burdens to LLMs to infer the desired inputs the way from specific program points deep in the code. In contrast, WEDGE alleviates LLMs' role from end-to-end input synthesis to only generating local performance-characteriiiii predicates, mitigating the burden introduced by the potentially long-context reasoning.
6 Discussion and Conclusion
The limitations of WEDGE are threefold. First, WEDGE incorporates prompting and fuzzing for each solution, thus incurring considerable token cost and execution overhead. Second, iefoormnnce-charactriiiii
Limitations.
constraint reasoning depends on mining high-quality contrastive input pairs, thus requiring either existing test input corpus and/or additional executions. Third, the underlying fuzzer often suffers from the input length constraints. For example, AFL++ [19] can only mutate input data smaller than threshold, e.g.. 1MB by default (and we modified it to 10MB), thus cannot handle arbitrarily large inputs.
Future work. Our key insight is to decompose the problem of stress test generation into performance- characterizing constraint reasoning and constraint-guided search, where the former can benefit from LLM's code reasoning capability and the latter can leverage efficient input search tools based on fuzzing. Future work includes extending WEDGE real-world projects and generating test oracles beyond performance evaluation.
Conclusion. We introduced WEDGE, a framework evaluate and improve code efficiency by gener- ating performance-characttriiin constraints with LLMs and guided fuzzing to explore performance- stressing inputs. We released our performance-stressing tests, along with the CodeContest programs, as new benchmark PERFFORGE at https: //gi thub. com/UChi Swweeeellllpeeeeeeeeeeeeeeeeeeee httb/perffrrgg With PERF- FORGE tests, we have demonstrated that WEDGE helped better evaluate and substantially improve existing code optimization techniques.
Acknowledgement
We thank all the anonymous reviewers, Weichen Li, and Jiawei Liu for their constructive and insightful comments and feedback, which significantly improved this paper. This work was supported in part by the OpenAl Research Access Program [73]. Results presented in this paper were obtained using the Chamelcon testbed [74] supported by the National Science Foundation.
10

---

References
[1] Emery D Berger. Scalene: Scripting- aware profiling for python. arXiv preprint arXiv:2006.33879, 2020.
[2] Chris Cummins, Volker Seeker, Dejan Grubisic, Baptiste Roziere, Jonas Gehring, Gabriel Synnaeve, and Hugh Leather. Meta large language model compiler: Foundation models of compiler optimization. arXiv preprint arXiv:2407 2.XX::2407.02524,. .2524, 2024.
[3] Dong HUANG, Jianbo Dai, Han Weng, Puzhen Wu, Yuhao QING, Heming Cui, Zhijiang Guo, and Jie Zhang. Effileamnr: Enhancing efficiency of generated code via self-optimization. In The Thirty- Annual Conference on Neural Information Processing Systems, 2024. URL https://opente
[4] Jiawei Liu, Thanh Nguyen, Mingyue Shang, Hantian Ding, Xiaopeng Li, Yu Yu, Varun Ku- mar, and Zijian Wang. Learning code preference via synthetic evolution. arXiv preprint arXiv:2410.03837, 2024.
[5] Alexander G Shypula, Aman Madaan, Yimeng Zeng, Uri Alon, Jacob R. Gardner, Yiming Yang, Milad Hashemi, Graham Neubig, Parthasarathy Ranganathan, Osbert Bastani, and Amir Yazdanbakhsh. Learning performance-improving code edits. In The Twelfth International Conference on Learning Representations, 2024. URL ix7rLVHXyY.
[6] Weichen Li, Albert Jan, Baishakhi Ray, Junfeng Yang, Chengzhi Mao, and Kexin Pei. Edit- lord: Learning code transformation rules for code editing. In The Forty-Second International Conference on Machine Learning (ICML.), 2025.
[7] Yun Peng. Akhilesh Deepak Gotmare, Michael Lyu, Caiming Xiong, Silvio Savarese, and Doyen Sahoo. Perfcodegen: Improving performance of Ilm generated code with execution feedback. arXiv preprint arXiv:2412.03578. 2024.
[8] Mingzhe Du, Luu Anh Tuan, Bin Ji, Qian Liu, and See-Kiong Ng. Mercury: A code effi- ciency benchmark for code large language models. Advances in Neural Information Processing Systems, 37, 2024.
[9] Dong Huang, Guangtao Zeng, Jianbo Dai, Meng Luo, Han Weng, Yuhao Qing, Heming Cui, Zhijiang Guo, and Jie Zhang. Effi-code: Unleashing code efficiency in language models. arXiv preprint arXiv:2410. 10209, 2024.
[10] Eric Zelikman, Eliana Lorch, Lester Mackey, and Adam Tauman Kalai. Self-taught optimizer (stop): Recursively self-impros self-improving code generation. In First Conference on Language Modeling. 2024.
[11] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde De Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et Evaluating large language models trained code. arXiv preprint MiXi:2217700337. 2021.
[12] Jiawei Liu, Songrun Xie, Junhao Wang, Yuxiang Wei, Yifeng Ding, and Lingming Zhang. Evaluating language models for efficient code generation. In First Conference on Language Modeling, 2024. URL
bet//forumidd=IBBBMe....
[13] Theofilos Petsios, Jason Zhao, Angelos D. Keromytis, and Suman Jana. Slowfuzz: Automated domain-indepenndet detection of algorithmic complexity vulnerabilities. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS '17, page 2155-2166 New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450349468. doi: 01145/3113956.11333 3134073.
URL. https:://toooo or 100 1145/3133966.
[14] Zongze Jiang, Ming Wen, Jialun Cao, Xuanhua Shi, and Hai Jin. Towards understanding the effectiveness of large language models on directed test input generation. Proceedings of the 39th IEEE/ACM Interaational Conference on Automated Software Engincering, ASE
11

---

'24, page 1408-1420, New York, NY, USA, 2024, Association for Computing Machinery. ISBN 9798400712487, doi: 10.1 01144/36666203669202 URL 3691 620. 0691623.3695113.
1145/
[15] Danning Xie, Mingwei Zheng, Xuwei Liu, Jiannan Wang, Chengpeng Wang, Lin Tan, and Xiangyu Zhang. Core: Benchmarking Iims code reasoning capabilities through static analysis tasks, 2025. URL https://arxil htt.aaawww..oooao.../o//a///aaae orggabs/2507 05269.
[16] Cristian Cadar, Daniel Dunbar, Dawson R Engler, et al. Klee: unassisted and automatic generation of high- coveraee tests for complex systems programs. In OSDI, volume 8, pages 209-224, 2008.
[17] Patrick Cousot. Abstract interpretation. ACM Computing Surveys (CSUR), 28(2):324-328, 1996.
[18] Uday Khedker, Amitabha Sanyal, and Bageshri Sathe. Data flow analysis: theory and practice. CRC Press, 2017.
[19] Andrea Fioraldi, Dominik Maier, Heiko Eißfeldt, and Mare Heuse. bining incremental steps of fuzzing research. In 14th USENIX Workshop on Offensive Technologies (WOOT 20). USENIX Association, August 2020. URL https://ww// usenix.
AFL++ Com-
ptg//oonfeeennewwoo22222 httpe///o//eeeeeettttooooorrrrro
[20] Gordon Fraser and Andrea Arcuri. Evosuite: automatic test suite generation for object-oriented software. In Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering, pages
2011.
[21] Prashast Srivastava and Mathias Payer. Gramatron: Effective grammar-aware fuzzing. In Proceedings of the 30th acm sigsoft international symposium on software testing and analysis, pages 244 256, 2021.
[22] Dongge Liu, Oliver Chang, Jonathan Metzman, Martin Sablomny, and Mihai Maruseac. OSS- fuzz-gen: Automated fuzz target generation, May 2024. URL https: //gi thub. com/googl/ oss-fuzz-gen.
[23] Wenxuan Shi, Yunhang Zhang, Xinyu Xing, and Jun Xu. Harnessing large language models for seed generation in greybox fuzzing. arXiv preprint arXiv:241 1.1444,,, 2024.
[24] Cen Zhang, Yaowen Zheng. Mingqiang Bai, Yeting Li, Wei Ma, Xiaofci Xie, Yuckang Li, Limin Sun, and Yang Liu. How effective are they? exploring large language model based fuzz driver generation. In Proceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis, pages 1223 1235, 2024.
[25] Caroline Lemieux. Rohan Padhye, Koushik Sen, and Dawn Song. Perffuzz: Automatically gener- ating pathological inputs. Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis, pages 254 265, 2018.
[26] Naman Jain, King Han, Alex Gu, Wen- Li, Fanjia Yan, Tianjun Zhang, Sida Wang, Ar- mando Solar-Lezama, Koushik Sen, and Ion Stoica. Livecodebench: Holistic and contamination free evaluation of large language models for code. arXiv preprint arXiv:2403.07974, 2024.
[27] Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, and Jacob Steinhardt. Measuring coding challenge competence with APPS. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021. URL
net/
forum?2id::D933022H315
[28] Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoe Le, et Program synthesis with large language models. arXiv preprint IrXiv:2108.07732. 2021.
12

---

[29] Jiawei Liu, Chunqiu Steven Xia, Yuyao Wang, and LINGMING ZHANG. Is your code generated by chatGPT really correct? rigorous evaluation of large language models for code generation. In Thinth- Conference on Neural Information Processing Systems, 2023. wttpeeewwwwweeefouumeaiaaam wtt.fooummidddggge.. @Cu7.
URL
[30] Qinkai Zheng, Xiao Xia, Xu Zou, Yuxiao Dong, Shan Wang, Yufei Xue, Lei Shen, Zihan Wang, Andi Wang, Yang Li, et al. Codegeex: pre-trained model for code generation with multilingual benchmarking on humaneval-x. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 5673-5684, 2023.
[31] Ben Athiwaratkun, Sanjay Krishna Gouda, Zijian Wang, Xiaopeng Li, Yuchen Tian, Ming Tan, Wasi Uddin Ahmad, Shiqi Wang, Qing Sun, Mingyue Shang, et al. Multi-linguat evaluation of code generation models. arXiv preprint arXiv:2210. 14868, 2022.
[32] Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Masson d' Autume, Igor Babuschkin, Xinyun Chen, Po-Sen Huang, Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel J. Mankowitz, Esme Sutherland Robson, Pushmeet Kohli, Nando de Freitas, Koray Kavukcuoglu, and Oriol Vinyals. Competition-Ievel code generation with alphacode. Science, 37866224) 2022. doi: 10. I 126/sciencc abql 158. URL https:
www.iicn..rg//o//a////////e/oo/e 1ttp:/...csscccccc http:////cciinneeaaa1111111 abq1158.
[33] Dong HUANG, Yuhao QING, Weiyi Shang, Heming Cui, and Jie Zhang. Effibench: Bench- marking the efficiency of automatically generated code. In The Thirty-eight Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2024. URL
[34] Yun Peng, Jun Wan, Yichen Li, and Xiaoxue Ren. Coffe: A code efficiency benchmark for code 02827.
generation, 2025. URL
[35] Siddhant Waghjale, Vishruth Veerendranath, Zhiruo Wang. and Daniel Fried. ECCO: Can we improve model-generated code efficiency without sacrificing functional correctness? In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen, editors, Proceedings of the 2024 Conference Empirical Methods in Natural Language Processing, pages 15376, Miami, Florida, USA, November 2024. Association for Computational Linguistics. doi: 10. 10.18643/v//0024 emnlp- Saalp--mai..8555 859, URL https: aclaaahooatthoyyyyyooo org/ org/2024 emnlp-main 859/.
[36] Caroline Lemieux, Jeevana Priya Inala, Shuvendu K. Lahiri, and Siddhartha Sen. Codamosa: Escaping coverage plateaus in test generation with pre-trained large language models. In 2023 IEEE/ACM 45th International Conference on Software Engineering (ICSE), ICSE'23, pages doi: 10. N0.11099CSEAA86192223..00
919-931, 909,991,,220 2023.
[37] Sungmin Kang, Juyeon Yoon, and Shin Yoo. Large language models few-shot testers: Ex- ploring llmebased general bug reproduction. In 2023 IEEE/ACM 45th International Conference on Software Engineering (ICSE), ICSE'23, pages 2312-2323, 2023, doi: 10. 109/CS4991,,,619
2023.00194.
[38] Yinlin Deng, Chunqiu Steven Xia, Chenyuan Yang, Shizhuo Dylan Zhang, Shujing Yang, and Lingming Zhang. Large language models are edge-case generators: Crafting unusual pro- grams for fuzzing deep learning libraries. In Proceedings of the 46th IEEE/ACM international conference on software engineering, 2024.
[39] Manish Shetty, Naman Jain, Jinjian Liu, Vijay Kethanaboyina, Koushik Sen, and Ion Stoica. Gso: Challenging software optimization tasks for evaluating swe-agents, 2025, URL https: 23671.
[40] Carlos E Jimenez, John Yang. Alexander Wettig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik Narasimhan. Swe-hench: Can language models resolve real-world github issues? arXiv preprint arXiv:23 10.00770, 2023.
13

---

[41] Yangruibo Ding, Zijian Wang. Wasi Ahmad, Hantian Ding, Ming Tan, Nihal Jain, Murali Kr- ishna Ramanathan, Ramesh Nallapati, Parminder Bhatia, Dan Roth, et al. Crosscodeeval: A diverse and multilingual benchmark for cross-file code completion. Advances in Neural Information Processing Systems, 36:46701-46723, 2023.
[42] Pingyu Zhang. Sebastian Elbaum, and Matthew B. Dwyer. Automatic generation of load tests. In 2011 26th IEEE/ACM International Conference on Automated Software Engineering (ASE 2011), pages 43 43-52, 2011. doi: 10.1109/ASE.2011 201.6.00000...0
[43] Jacob Burnim, Sudeep Juvekar, and Koushik Sen. Wise: Automated test generation for worst- case complexity. In Proceedings the 31tt International Conference on Software Engineering, ICSE '09, page 463-473, USA, 2009. IEEE Computer Society. ISBN 9781424434534, doi: 10. N..1109//SEE22000.000 5077055.. URL /tttt::///oii..r////0.. 1109/ ICCEE 2009. 5070545.
[44] Bihuan Chen, Yang Liu, and Wei Le. Generating performance distributions via probabilis- tic symbolic execution. In Proceedings of the 38th International Conference on Software Engineering, ICSE '16, page 49-60, New York, NY, USA, 2016. Association for Com- puting Machinery. ISBN 9781450339001. doi: 01014452288481.888477777 URL https: //doi www.orgg/11// 10. /ow.////....1//887778 11511182//88811111 2884794.
[45] DeepMind. Codecontests dataset. https: / hetsss//hggingaacccc woteceeco///aaaeeeeeeeeeeeeeeeee co/ co/dataasets/deepminddd contests, 2022. Codeforces section, problem 633_A. A. Ebony and Ivory.
[46] Wikipedia. Diophantine equation - Wikipedia, the free encyclopedia. http: wik wikipedia. org/w/index whpptitle=Diioiieipeeeeeeeeeeeet htt.::/ewo...iiaaaeeeeooeaaaaaa. accessed 15-May-2025).
2025. [Online;
[47] Suphakit Niwattanakul, Jatsada Singthongchai, Ekkachai Naemudorn, and Supachanun Wanapu. Using of jaccard coefficient for keywords similarity. In Proceedings of the international multiconference of engineers and computer scientists, volume 1, pages 380-384, 2013.
[48] Yun Lin, Jun Sun, Yinxing Xue, Yang Liu, and Jinsong Dong. Feedback-based debugging. In Proceedings of the 39th International Conference on Software Engineering, ICSE '17, page 393-403. IEEE Press, 2017. ISBN 9781 5386388886 https://doi. org/rrg/////oo/ /10 1109/ICSE.200 2017. 2017.43.
doi: 10.1109/CCSE.2117..5 URL
[49] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoc V Le. and Denny Zhou. Chain of thought prompting elicits reasoning in large language models. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors. Advances in Neural Information Processing Systems, 2022. URL https: http:::///ppprree http:////ppeeeeenneemeee net/ net/ Virumiidd_VjOMMeBBB...
[50] Charlie Curtsinger and Emery D. Berger. Coz: finding code that counts with causal profiling. Commun. ACM, 61(6)9119 May 2018. ISSN 0001-0782. doi: 10.1145/3205911. URL https://doi.oos org/ /10. 145/3205911
[51] Xiao Zhang, Eric Tune, Robert Hagmann, Rohit Jnagal, Vrigo Gokhale, and John Wilkes. Cpi2: Cpu performance isolation for shared compute clusters. In Proceedings of the 8th ACM European Conference on Computer Systems, EuroSys '13, page 379-391, New York, NY. USA, 2013. Association for Computing Machinery. ISBN 9781450319944 doi: 10.1 (0.1145/246535. 2465388. URL https://dob org/10. 10..111145445555 2465388.
[52] Calin Iorgulescu, Reza Azimi, Youngjin Kwon, Sameh Elnikety, Manoj Syamala, Vivek Narasayya, Herodotos Herodotou, Paulo Tomita, Alex Chen, Jack Zhang, and Junhua Wang. Perflso: Performance isolation for commercial Latency-Sensitivy services. 2018 USENIX Annual Technical Conference (USENIX ATC 18). pages 519-532, Boston, MA, July 2018. USENIX Association. ISBN 978-1-939133-01 URL https: /opp:://www. usenix. org/ conference// httee/acllaa htt.r//eetttttoonoorruueeeeeeeee
[53] Christina Delimitrou and Christos Kozyrakis. Quasar: resource-efficiet and qos-aware cluster management. In Proceedings of the 19th International Conference Architectural Support
14

---

for Programming Languages and Operating Systems, ASPLOS '14, page 127-144, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 0781450323055. doi: 10.1145/ 2541940.254191.. URL https://doi.
1145/2541948 94444444449..
[54] Arnaldo Carvalho De Melo. The new linux' perf In Slides from Linux Kongress, vol- ume 18, pages 1-42, 2010.
[55] Patrick E McKnight and Julius Najab. Mann-whitney u test. The Corsini encyclopedia of psychology, pages 1-1, 2010.
[56] Rohan Padhye, Caroline Lemieux, Koushik Sen, Laurent Simon, and Hayawardh Vijayakumar. Fuzzfactory; domain-specific fuzzing with waypoints. volume 3, New York, NY, USA, October 2019. Association for Computing Machinery. doi: 10.1145/3360600. URL ht https://dol org/ 10. 1 00.1145/3336660
[57] Marcos K. Aguilera, Jeffrey C. Mogul, Janet L. Wiener, Patrick Reynolds, and Athicha Muthi- tacharoen. Performance debugging for distributed systems of black boxes. In Proceedings of the Nineteenth ACM Symposium Operating Systems Principles, SOSP '03, page 74-89, New York, NY, USA, 2003. Association for Computing Machinery. ISBN 1581137575. doi: 10. 02.144/994445.945555 URL https:///oi. org/1.. 10. /45/945445. 945454.
[58]
Guoliang Jin, Linhai Song, Xiaoming Shi, Joel Scherpelz, and Shan Lu, Understanding and detecting real-world performance bugs. Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '12, page 77-88, New York, NY. USA, 2012. Association for Computing Machinery. ISBN 9781 1781450312059, doi: 2441445/224404422544773 URL https://dol org/ 1145/2254064 2254075.
[59] Adrian Nistor, Linhai Song, Darko Marinov, and Shan Lu. Toddler: detecting performance prob- lems via similar mecorr-accesss patterns. In Proceedings of the 2013 International Conference on Software Engineering, ICSE '13, page 562-571. IEEE Press, 2013. ISBN 9781 178144 7781467330763
[60] Adrian Nistor, Po-Chun Chang, Cosmin Radoi, and Shan Lu. Caramel: detecting and fixing performance problems that have non-intrusive fixes. In Proceedings the 37th International Conference on Software Engineering Volume 1, ICSE '15, page 902-912. IEEE Press, 2015.
ISBN 9781479919345
[61] Oswaldo Olivo, Isil Dillig, and Calvin Lin. Static detection of asymptotic performance bugs in collection traversals. SIGPLAN Not., 50(6):369-3)) -78, June 2015. ISSN 0362-1340. doi: 10. 1111/111388888 3885.2737966 URL https: / /ooi wrg.10.g///. 1 /815/2111111 3885. 2737966.
[62] Guoqing Xu, Matthew Arnold, Nick Mitchell, Atanas Rountev, and Gary Sevitsky. Go with the flow: profiling copies to find runtime bloat. In Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '09, page 419-430, New York, NY, USA, 2009. Association for Computing Machinery. ISBN 9781 9781605583921. doi: 10. 10.144//542476.. 1542523. URL / http://ooooooog///// 1..0..1..1 01145/1544444 1542523.
[63] Guoqing Xu, Nick Mitchell, Matthew Arnold, Atanas Rountev, Edith Schonberg, and Gary Sevitsky. Finding low-utility data structures. In Proceedings of the 31 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '10, page 174-186, New York, NY. USA, 2010. Association for Computing Machinery. ISBN 978 1403300193 doi: 10. 10.1145/1806596 1806617. URL https://doi org/10 0.
1886617.
[64] Bruno Dufour, Barbara G. Ryder, and Gary Sevitsky. Blended analysis for performance understanding of Tramework-basee applications. In Proceedings of the 2007 International Symposium on Software Testing and Analysis. ISSTA '07, page 118- 128. New York, NY. USA, 2007. Association for Computing Machinery. ISBN 9781595937346. doi: 10.1145/ 1777466.11233488 URL https: //tp:::://do... www.orgg///// 10. 10e11115212355 1273480.
[65] Jiaxin Li, Yuxi Chen, Haopeng Liu, Shan Lu, Yiming Zhang, Haryadi S. Gunawi, Xiaohui Gu, Xicheng Lu, and Dongsheng Li. Peatch: Automatically detecting performance cascading bugs in cloud systems. In Proceedings of the Thirteenth EuroSys Conference, EuroSys '18, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 978155055584 doi: 10. 1../114//11990 190508 3190552. URL https:///ol ooaddoo.orgg//o org/ /045/339356 31 3190552.
15

---

[66] Qiang Zhang, Yuheng Shen, Jianzhong Liu, Yiru Xu, Heyuan Shi, Yu Jiang, and Wanli Chang. Heg: Augmenting embedded operating system fuzzing via llm-based corpus generation. IEFE Transactions on Computer-Aidee Aided Design of Integrated Circuits and Systems, 43((1):4238-
4249, 2024.
[67] Jie Hu, Qian Zhang, and Heng Yin. Augmenting greybox fuzzing with generative ai. arXiv preprint arXiv:2306.06782. 2023.
[68] Hongxiang Zhang. Yuyang Rong, Yifeng He, and Hao Chen. Llamafuzz: Large language model enhanced greybox fuzzing. arXiv preprint arXiv:2406.07714 2024.
[69] Chenyuan Yang. Zijie Zhao, and Lingming Zhang. Kernelgp:: Enhanced kernel fuzzing via large language models. arXiv preprint S.Kiv:2401.005666 2023.
[70] Chenyuan Yang, Yinlin Deng, Runyu Lu, Jiayi Yao, Jiawei Liu, Reyhaneh Jabbarvand, and Lingming Zhang. Whitefox: White-box compiler fuzzing empowered by large language models. Proceedings of the ACM on Programming Languages, 8(00PSLA2):009 -35-735,79777 2024.
[71] Chunqiu Steven Xia, Matteo Paltenghi, Jia Le Tian, Michael Pradel, and Lingming Zhang. Fuzz4all: Universal fuzzing with large language models. In Proceedings of the IEEE/ACM 46th International Conference on Software Engineering, 2024.
[72] Jie Zhu, Chihao Shen, Ziyang Li, Jiahao Yu, Yizheng Chen, and Kexin Pei. Locus: Agentic predicate synthesis for directed fuzzing. In Proceedings of the 48th IEEE/ACM International Conference on Software Engineering, 2026.
[73] OpenAI. Openai researcher access program. aacpheerracccs-pprreeeee
https://openai..oo/ffrr
[74] Kate Keahey, Jason Anderson, Zhuo Zhen, Pierre Riteau, Paul Ruth, Dan Stanzione, Mert Cevik, Jacob Colleran, Haryadi S. Gunawi, Cody Hammock, Joe Mambretti, Alexander Barnes, François Halbach, Alex Rocha, and Joe Stubbs. Lessons learned from the chameleon testbed. In Proceedings of the 2020 USENIX Annual Technical Conference (USENIX ATC '20). USENIX Association, July 2020.
[75] Chunqiu Steven Xia and Lingming Zhang. Automated program repair via conversation: Fixing 162 out of 337 bugs for S0.42 each using chatgpt. In Proceedings of the 33rd ACM SIGSOFT International Symposium York, NY, USA, 2024. Association for Computing Machinery, ISBN 9798400706127, doi: 10. 01.553660212.366003 URL https://dol http://oo..or//////// 0444/ 3680323.
Software Testing and Analysis, ISSTA 2024, page 819-831, New
[76] Thorsten Brants, Ashok Popat, Peng Xu, Franz Josef Och, and Jeffrey Dean. Large language models in machine translation. In Proceedings of the 2007 Joint Conference on Empirical Methods Natural Language Processing and Computational Natural Language Learning (EMNLP-CONLLL) pages 858-867, 2007.
[77] Vincent Weaver: Linux perf_eve event features and overhead. The 2nd international workshop on performance analysis of workload optimized systems, FastPath, volume 13, page 5, 2013.
[78] Nathan Binkert, Bradford Beckmann, Gabriel Black, Steven K Reinhardt, Ali Saidi, Arkaprava Basu, Joel Hestness, Derek R Hower, Tushar Krishna, Somaych Sardashti, et al. The gem5 simulator. ACM SIGARCH computer architecture news, 1-7, 2011.
[79] Wikipedia. Hardware performance counter -
Wikipedia, the free encyclopedia. http://en.nu http://ewwwiiiiiieeeeee wwkipedia. wwwpppeeda...o.vv...e...o. org/w/ index.ixxxi. php?ti owt.at/rwwwrreeeeeeeefooeeeeeeee o1did=1169157291, 2025. [Online; accessed 15-Ma)-2025).
[80] Theofilos Petsios, 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, pages 2155-2168,
2017.
16

---

A Detailed Design Decisions
A.1 Filtering Policies
Filtering process for evaluating WEDGE. The original CodeContest dataset ("train" split, "Code- forces" section [45]) contains over 3,000 problems with hundreds C++ solutions each. is infeasible evaluate that many executions due both computational and monetary costs. To address this, focus on a smaller yet meaningful subset by applying the following filtering criteria.
(I) Sufficient computation. We remove problems whose solutions never exceed 100,000 instructions on any input to reduce the impact of potential noise following [12].
(2) Sufficient solutions. We remove problems with fewer than 10 correct solutions because we need to run fuzzing on a reasonable amount of correct solutions obtain meaningful measurements.
(3) Sufficient test inputs. We remove problems with fewer than five default tests because we need enough inputs for fuzzing to be effective and also to identify contrasting input pairs (3.11).
(4) Single output. We filter out problems that accept multiple correct outputs.
(5) Diversified performance. We only include problems with diversified performance across the solutions. Specifically, we use the Coefficient of Variance (CV) measure the diversity, follow- ing [12]. Low diversity means most solutions have similar performance, indicating the solutions are likely optimal close to optimal. Intuitively, there are fewer opportunities to identify performance- characterizing constraints on the optimal solutions.
Additional filtering to accommodate EFFI-LEARNES Note that the original EFFI-LEARE explores using profiling information to improve LLM --g-errrrteed code, while we adapt it to our scenario, i... improving slow user solutions. To this end, extract subset of problems and solutions from the 300 problems in PERFFORGE. Specifically, in addition to the sufficient computation criterion above, applied the following criteria:
(1) Python code. Instead of C++, we focus on Python solutions as EFFI-LEARNER is designed for Python. EFFI-LEARNER also requires these Python programs to contain function definition, i.c., with def keyword, as the profiling tools work at the function level.
(2) Room for code optimization. Solutions should be relatively slow, namely suboptimal, so that there's space for improvement. Thus, we include only solutions that execute approximately twice the number of instructions when compared to the fastest (correct) solution for that particular problem.
Similar to main filtering criteria above, select problems that have least five such solutions. We then select the five slowest ones per problem to form our evaluation dataset. Ultimately, we end up with 56 problems and 280 Python solutions.
Additional filtering to accommodate PTE. The original PIE framework [5] was evaluated on solutions to coding problems from the CodeNet dataset, subset of CodeContests. Following the authors' original experimental setup, we focus on C++ solutions and, in addition to the sufficient computation and room from improvement criteria above, we also require solutions to be relatively short (<50 LoC) to accommodate the small LLM context window that PIE requires.
A.2 Iterative Mutator Generation
Although AFL++ [19] has shown superior performance in terms of coverage-guide test input generation, is not ready to use off the shelf. The default mutators of AFL++ engine are optimized for compact data formats say, images, multimedia, compressed data, etc., supporting operations like flipping bits, inserting bytes, changing bytes, etc., not aware of the validity constraints of inputs. Therefore, such byte-level mutators will produce many invalid inputs that violate the input constraints of the coding problems. Instead of using the default mutators, we rely on the custom mutators interface of AFL++, which allows the to specify a customized Python C++ mutator script as the mutator engine. We prompt the model with problem description S, summarized constraints Cp, AFL+ provided mutator example, etc.
Different from PERF [12] and TG-prompt [3. 34, 8) style generator synthesis, mulator synthesis is more challenging since in addition to making sure the mutated input follows the input constraints,
17

---

it also needs to be robust enough mutate inputs in various shapes. To this end, we propose iterative mutator generation approach. The intuition comes from recent works [75] showing L.LSs are good at fixing programs conversationally. For each generated mutator, we launch a dry run for three minutes. If the dry run successfully exited with a number of new test inputs generated, the mutator is labeled as "pass". Otherwise, we append the failing message such as "IndexError: list assignment index out of range" to the conversation and ask the LLM to fix the issue. The wompping-anddrry- loop terminates when good mutator is produced, or the maximum number of rounds (ten in our experiments) have been tried. The evaluation shows only the ratio of successful mutators of single round generation is only 80.13%, while it's improved 82.96% after one round and 83.35 after ten rounds, demonstrating the effectiveness of iterative refining.
an
A.3 Input Validation with Consistency Checks
LLM-based input validator. Both fuzzing and prompting-based generator generation can produce large amount of test inputs. However, the generated inputs might violate the input format or specifica- tions in the problem description. To tackle this problem, Liu et al. [29] adopted a programming by contract philosophy by manually annotating function pre-conditions in the form of code assertions (e.g., assert n 0) ensure the test inputs for the function are well-formed. However, manual annotation is known to be error-prone and expensive [76]. On the other hand, synthesizing a validator generally challenging as there's no ground truth.
We rely on the rich test cases (which are labeled as correct by the open-judge platform) in the dataset to reduce wrong validators, following the paradigm of Programming By Example (PBE), i.e., good validator should not label any valid inputs as invalid. Specifically, we iteratively prompt the LLM to generate validator Python script and execute it on the "public" and "private" test cases. If some tests fail, we append the failing message to the conversation and ask the model to fix the validator, until all tests pass reaches the retry limits. If no good validator is generated for a problem, is excluded from our evaluation set. In the end, we can successfully generate 289 validators within five rounds. Among them, 280 validators are generated successfully in the first round. Note that this approach does not ensure the correctness of the validators as the synthesis problem is generally undecidable, but it gives us higher confidence on the reliability of the validators.
Consistency check. In addition to the generated validator, we introduce a "consensus" consistency check to further filter out invalid inputs. For each generated input, we execute all correct solutions under the input and check whether 95% of them are consistent. Inputs leading to over 5% inconsistent results will be discarded. The intuition is that well-formed input should be processed correctly by all correct solutions. We apply the validators and consistency check to all techniques to ensure fair comparison.
A.4 Implementation and System Environment
We run experiments on six x86-64 machines equipped with a 24-core Intel Xeon Gold 6126 CPU with 192GB of RAM. Each machine runs Ubuntu 20.04 LTS (kernel version 5.4.0). We use the OpenAl and DeepSeek V3 (deepseek-v3-200) -3--024-122222 with a temperature of
GPT-4o (gpt-40-2024-08 0.8 and max length of 4,096. We use GPT-4o as the backbone LLM of WEDGE and all baseline techniques. For EFFI-LEARNER utility experiment 4.3, we use both GPT-4o and DeepSeek V3 for prompting. For PTE utility experiment 4.3, we use the same settings (temperature of 0.8, max_length of 4,096) for the three evaluated fine-tuned models.
In the contrasting inrptgg--iputtppaii mining stage, WEDGE will select no more than 10 solutions where at least one contrasting input pair exists. It then reasons about and generates performance-charattee constraints per solution. Each constraint is used both for instrumenting the solution program (fuzz driver) and mutator generation. Each instrumented solution program is fed to AFL++ and runs for one hour.
We implement a prototype of WEDGE and provide the scripts to run and collect experiment data, publicly: https: //gi thub. SeWlCChiSelabpperrr.eeee language and rely on the perf and gcov Linux utilities to collect instruction count, physical, and code coverage metrics. Overall, our artifact is implemented in approximately 10,000 LoC.
We use Python as our main development
18

---

Table 4: WEDGE versus baselines (described in Section 4.1) and its ablation.
Exccution time (ms)
Technique
Win rate
Average
Median
Comparison with baselines
WEDGE
228.60
82.33
60%
TG-pommpt
182.15 (1113x)
85.60 (11.1))
12%
PerfFuzz
140.63 (11.6x)
60.81 (L11.x)
11%
EVAL,PERFsL.
139.83 (111.xx)
61.69 (L11.3x)
8%
EERFPARR
134.79 (11.7x)
60.90 (11.4x)
9%
Ablations
WEDGE
228.60
82.33
65%
WEDGENOINSTR
171.63 (L113x)
71.54 (11.2x)
29%
W WEDGEDERLLUMLT
86.57 (12.6x)
59.13 (11.4x)
4%
AFL++
78.27 (12.9x)
45.13 (1188)
2%
A.5 Discussion on Measurements
To measure performance, we rely on the number of (retired) instructions based on physical execution time. We use the perf Linux utility [77] for both measurements. While physical running time is a more intuitive measurement, it can be prone to interference from transient system effects- such background processes, scheduling policies, and variable I/O latencies-wwit may mask true computational cost [54, 51J. In contrast, measuring instruction counts is metric that is more stable across run, platform-agnostie, and is well understood to significantly correlate with executions exhibiting performance bottlenecks [50-53].
Recently, LLM-based code analysis tools started to rely instruction count measured through hardware counters [12, 34] or emulation [5] to evaluate code efficiency as provides a more reliable, low-variance measurement than physical time alone. Moreover, experiments in [34] found instruction count measurements are approximately 1000 magnitude more stable than physical execution time. findings: experiments reveal that physical time is ~400 more variable
This mirrors than CPU instruction counts (12% versus 0.03%, on average, see $4.2 and B,. respectively).
Prior works respectively rely on CPU simulators like Gem5 [78] (PIE [5]), physical execution time (EffiBench [33], Mercury [8]), and hardware performance counters [79] (EvalPerf [12], COFFE [34]). Gem5 is known to be stable, but the overhead is significant, and the CPU simulator does not necessarily reflect the physical performance. While physical running time offers an intuitive measure, it is susceptible to interference from transient system effeetts-sus variability, and I/O fluctuations- which can obscure true computational cost. In contrast, hardware performance counters provide more stable, low-noise, and platform-agnostic metric. It records the number of executed instructions of program execution using the Linux perf tool [54]. It incurs low overhead and is highly reproducible. Moreover, Peng et al. [34] demonstrates that it's linearly correlated with execution time with Pearson correlation coefficient of 0.96 ~1.0.
background processes, scheduling
B Extended Results
B.1 Physical Running Time Measurements
We include physical running time measurements reference. Note that the variance among the five repetitions is more significant than for CPU instructions count, namely 12%, on average. While multiple factors contribute to this large variance, we argue that the dominant factor of "noise" 1/O as a sizable fraction of programs need to read thousands of KB, thus making them I/O-bound. Nevertheless, Table shows that our tool outperforms all other baselines even when measuring physical execution time, more noisc-prone metric.
19

---

Table 5: Source numbers for generating Figure 3. Due space constraints, group numbers in bins of size 200% (instead of 10%) into larger buckets. bucket of [x, y] represents the number of programs technique incurs between x% and y% (inclusive) larger instruction count than the other.
Techniques
Bins
[0, 199]
[200, 399]
[400, 599]
[600, 799]
[800, 999]
[1000.)
WEDGE vs. TG-prompt
17,117 (11, 704)
1,524 (J663
158 (J660)
148 (L-10)
155 (1,27)
311 (1768)
PerfFuzz
14,192 (11, 758)
444 (183)
206 (157)
159
71
3,439 17)
EVAL PeR
15,628 (L1, 856)
1,365 (1.69)
425 (1:3)
(4 7)
(111)
1,288 (1454)
EVALPERFEAND
15,879 (11, 999)
966 (178)
588 (113)
664 (122)
367 (!14)
1,004 (1450)
Table WEDGE versus a threshold.
baselines (Section 4.1) for problems whose inputs are below
of instructions (x10*)
Slowdown over CC
Technique
Win rate
Average
Median
Average
Median
Less than 1MB
WEDGE
4.29
0.17
59%
113x
1.11x
TG-prompt
2.28 (11.9x)
0.14 (11.2x)
11%
75
1.01
EVALPERFs..w
2.57 (U1.7x)
0.07 (12.3x)
14%
57x
1.05x
EVALPERFR.N
2.59 (J1.7))
0.08 (12.2x)
16%
88x
1.05x
Less than 100KB
WEDGE
3,71
0.08
56% %
88x
1.06x
TG-prompt
1.85 (J2.0x)
0.06 (11.3x)
10%
60x
1.00x
EvAL.PERFSLOW
2.48 (11.5x)
0.03 (12.3x)
16%
49
1,02x
EVALPERFRAN
(21..x))
0.03 (12.5x)
18%
84x
1.02x
Less than 10KB
WEDGE
3.10
0.02
55%
20
1.02
TG-prompe
1.26 (12.5x)
0.01 (U1.5x)
5%
9x
1.00x
EVALPERFsLOW
1.79 (L1.7x)
0.01 (11.4x)
19%
7x
1.00x
EERFRARDD
1.53 (12.0x)
0.01 (11.4x)
21%
8x
1.00x
Less than 1KB
WEDGE
2.98
0.01 (11,5x)
54%
5X
1.01
TG-prompt
1.00 (L3.0x)
6%
1.00x
EVAL PFRFFLOO
1.63 (1.18xx)
0.01 (11,3x)
16%
1x
1.00x
EVALPERFeAM
1.45 (12.1x)
0.01 (11.3x)
24%
1x
1.00x
B.2 Head-to-Head Numbers
Table 5 shows the absolute numbers used generate the histogram in Figure 3. Specifically, the values outside of parentheses represent the number programs that execute more instructions when running PERFFORGE tests, while those in parentheses indicate the number of programs that execute more instructions when running tests generated by one of the baselines (each row). Note that with exception, TG-prompt tests that determine programs to execute 10x more instructions, framework outperforms each technique. Even so, PERFFORGE tests determine more programs for longer by more than 50% compared to TGG-roomp (Table 1).
B.3 Effeet of Input Size
On the one hand, we compare our framework with length-stressing baselines that are geared to- wards maximizing the input sizes [12, 34]. On the other, designing fuzzing tools that generate performance-stressee stressing tests are fundamentally challenging, and requires specialized metrics and tailored mutators [25]. Therefore, investigate if and how input size plays role in the quality of our tests (i.e., how "performance-stressti
they are).
Specifically, partition our original dataset (Section 4.1) into subsets of problems based on the maximum input size they require, and compare PERFFORGE against tests generated by each baseline. Table 6 shows that, average, our WEDGE outperforms the baselines when restricting input size.
20

---

Table 7: Cost analysis phases of WEDGE.
Phase
Tokens
Time (8)
# Executions
Contrastive input pair mining
N/A
15.46
99.65
Profiling feedback collection
N/A
PC constraint reasoning and constraint checker generation
9633.16
<
N/A
Constraint-awe aware mutator generation
6905.27
180
N/A
Constraint-guided fuzzing
N/A
3600
N/A
The largest shift happens when compared with TG-prompt. For problems whose inputs less than 1KB, the difference is almost double than comparing the two on the entire dataset, 3.0x vs 1.5x, respectively.
B.4 Cost Analysis
Table 7 presents the statistics time token cost in each phase. The most time-consuming phase is constraint-guider fuzzing, which runs for one hour. The most token-consuming phase is PC constraint reasoning and constraint checker generation, which consumes 9.6K tokens. However, since we have 99.6 99.65 test inputs generated for each program average, the time and token consumption per test input is low, i.e., within 39 seconds and 166 tokens per input on average.
C Case Studies
In this section, we consider several interesting case studies of performancc--haarcttriiin generated by WEDGE. We first rank the synthesized constraints by the combined size of their plain language description and corresponding generated checker code. We then select five out of the top ten problems that belong to different algorithmic classes. We provide the full response produced by the LLM along with additional selected case studies https: / /gi thub. Comm/UChSSecllbbb per fforge.
constraints
C.1 Qualitative Analysis of Interesting Cases
In this section, we investigate the test generators synthesized by each baseline technique and compare them with the aerformance-characttriii constraints generated by WEDGE, for Problem 633A which serves our motivating example.
serf__nnuu__gennee (scale: int):
# Assuming scale affects the complexity of the test, but since and b have fixed range scale will just determine cts complexity.
will 99
values
5
189
10_000 # Maximum possible value for return (a, b. c)
Listing 1: EVALPERFsI.NN synthesized generator for Problem 633A
Inspecting the test generator synthesized by EVAI.PERF (Listing 1) shows that it only generates inputs close to the problem's 's upper bounds (i.e., 99, 100, 10000) without even utilizing the scale parameter.
def parf_input_gente (scalee::: int):
nun
for
test edge cases
a = rrandin(1, 188)
b = randint(1, 188)
Scale с
large, but within linit c is chosen to be large to test performance, wе still ensure it is within problen constraints min scale), 18080)
10
return (a, b, c)
Listing 2: EVALPERFRANI synthesized generator for Problem 633A
The test generator synthesized EVAL (Listing 2) random and b within [1, 100] range and a large с (determined by scale) as the input. Still, the effect generating values close the upper bounds of the problem.
21

---

def generate_ generate_testt (rreraeeeest(ttpuu.eeerroo)) test_cases Mininum edge case (1. 1. 1).
simple
(2. 3. 9). (3, 3, 6).
8
Co-prine (a. (17, 19, 188). (1ei, 163, 5066).
larger
12
Large with simple a, (2, 3, 9999).
15
16
Boundary cases 10_000). (99. 166. 9_988).
20
Maxinum values (100.
10_000).
24
Various patterns (5. 10. 995], (7. 18, 9997). (1, 189, 10_060).
28
(180, 1, 18_000),
Co-prine trickiness (4, 7, 9999).
32
(15, 20, 18_800).
abave/below nultiples
(3. 5. 10082).
36
(5, 3, 9998),
Another complex co-prime situation (97, 89, 9999),
19
40
Randomized challenging cases
(37, 19680),
43
(6, 9, 9999)
44
]
# write test
Listing 3: TG-prompt synthesized generator for Problem 633A
TG-prompt (Listing 3) composes series of concrete test cases rather than synthesizing pattern- based generator. While it attempts to implicitly reason about how to synthesize performance-stressing inputs by including diverse patterns, some appear as generic corner cases. Thus, there is no guarantee these can trigger performance bottlenecks.
In contrast, WEDGE relies on fuzzing with constraint- aware mutators to efficiently search for a diverse of constraint-sund sattiiiinntiiiiiingn inputs. Listing shows constraint-awes The mutator will mutate previous input (seed input) to produce the next input (mutated input). The while loop will search the input space of (a, b, c) and ensure they conform to the constraints not abs (a b) > 5 or
mutator for Problem 633A.
== 0 or % b = 0, i.e., abs (a b) <= 5 and c % != and с % b != 0 (already satisfying the first two out of three constraints in Listing 5).
def nutate_Last__nte (bur]
Hutate the last input slightly to explore the surrounding input space. parts decode "uuf--")..srripe strrs(()sssppttt)))) int(pers
b int(parts[1]) int(parts[2])
10 Small mutations to each part
11 = max(1, min
(-5, 5)))
12 b nax(1, min b randon. randint 5333
13 max(1,
randon. randintt-a 500))
14
15
a Ensure the mutation leads to potentially challenging inputs
while abs(a max(1, min(100, E randon. (-5, 5)))
or 8'b
17
18
b max min(108, b randon. randint(-S, 5)))
19
e max(1, 1,, c randon. randint 5e6))
return ("(a) (b) (c)*
Listing 4: WEDGE synthesized constraint-awan fuzzing mutator for Problem 633A
22

---

// Check if and b are close and neither is direct divisor of int 8)
close, walues..onsteneeeee. constraitntt if (abs b) && l
cerr <c "Warning: Luse__values_oonstraa triggered a and b are close, and neither divides c* << endl;
Listing WEDGE generated performanee-charctteriiinng constraints checker code
C.2 Other Representative Case Studies
# Case Problem 1209B, solution #328. Given set of n lights, each initially on/off and described
by two parameters (a,.b;), light toggles its state at times b,, b,+a, b;+2a,, The goal is to find the maximum number of lights simultaneously on at any moment.
#include chits/stdc++.h>
using namespace std;
const long double pie = 3. 3.14199255388877
const long long string vow "aciou"; void sinv test_case)
int n;
8 cin >> n;
string s;
10 cin >> s:
12 vector<vactor<int> > v(n, vectar<int><(, 8)):
13 vectorspair<int, int> p(n):
for (int
i++) cin firs.first plil. second
15 for (int = 8; n; i++) {
(s[i]
v[i][e]
17 for (int j 1; <[ii.. j+s) v[I][J] = v[il(] - 13:
temp v[i][e]
19
for (int plil. second; j + p[il. first)
for (int 0; 1 N; k*t) vEilEs + k] temp:
temp *= 1;
22
}
24
int ans = 8;
(int j 0; N; j++) (
int temp 8;
for (int i 8; n: itt) temp v[i][5]:
(ans, temp);
29 }
cout ans;
31
cout << "\n";
int main() {
34
les bos_base:: wyss::::ycc.whhhhsssoofoot
tie(9);
36
tie());
=
8 for (int i = i++) solve(i);
return 0;
Listing Example from our dataset: problem 1209B, solution 328
The code Listing simulates a fixed time window N 1, 000, instead of reasoning analytically about the periodic patterns which requires solving least-common-muttii cally, the program builds two-dimensional array where for each light it first copies its initial state up to f = 6, then for each toggle epoch t = b, + a.... it fills the remainder of the row in one shot a nested "for k" loop at line 20. Finally, it scans each column sums up v[i][(] for = 1,n, and tracks the maximum (line 28). In the worst case, when = 1, the program performs O iterations per toggling operation, for an overall complexity of O 2 + n. N).
type of problem. Specifi-
void check_snall_e amall_a_veel (aa.uaaavvlleeeaaoaaae (const vector spaii int>>a p)
int snall_a_con a_count 8; far (const autoß pair
(pair, first 2) { // Assume 'small' aui values are small_a_count*r,
}.
23

---

anall____ount > 50) ( // Arbitrary threshold, adjust
cerr << "Warning: Perfornance bottleneck condition triggered many lights have small aa" values" endl;
}
13 void syncckssychronizee.. benchrooized_b_vllueee www.lbvvvvlseeeee...eeaaa (const vector<pair<ing, int>>8 p)
nap<int, int> b_count;
15
for (const autož pair L.count[pair.secom
16
18
for (const autok [b_value, count] b_count)
if (count 38) { Arbitrary threshold synchranization carr << "Warning: Performance bottleneck condition triggered synchronized "b' values" endl;
30
22
34
void check_ Check_large____e wwwge_aungerrr......eerraea of__iighs n) {
26
if (n > 98) { // close to the upper constraint cerr "Warning: Perfornance bottleneck condition triggered high nunber of lights" endl;
28
Listing 7: PC-constraints as C++ checker functions: problem 1209B, solution 328
WEDGE identifies three types of pe-constraints for this program, listed in 7.
1. The first perforraanc--hhaacttiiiii
constraint (i.e., baacc_ssmal____e a__vllessvl finds that if many lights have very small a; (e.g. 1), translates to more iterations the outer loop at line 15. Consequently, each iteration invokes full inner copy (loop at line 20). Thus, small periods significantly amplify the work performed by the nested-loop work.
2. The second performance-characttriiinng constraint (i.e., check_synchroni synchronized. b_________ values) points to clusters of 6; values: if many lights share the same or close b, their current state lineup, causing the code execute the heavy inner loop at line 20 for multiple lights the same early offsets. Specifically, low or repeated p[i]. second forces expensive fill operations execute immediately and for many lights in fast succession.
3. Finally,
the third check_ laack_large_nuaee number_of _f__hhtts))) simply indicates that as approaches its upper bound near 100, the total nested work scales linearly in Each additional light multiplies the cost of the O(N2) toggling loops and the O(N) sean across time.
constraint
(i.e.,
purely specification or toggle periods and large number of lights trigger multiple loop iterations because any simulation of a periodic, large number of events would exhibit that. However, the actual performance profile of the code actual performance relies of toggling cell by cell, the implementation writes an entire suffix of the time-array (for loop at line 20), thus light toggle linear (O(N) instead of constant operation. Second, the choice of simulating the maximum number of seconds possible, 1, 000 1, 000, irrespective of the input. An optimal solution would take into account that each light's behavior is periodic, namely once reaches its first toggle at t = 6; thereafter it repeats every a, seconds. This, naturally, translates into cycles of length equal to the lowest common multiplier: optimal program is, therefore, approximately two orders of magnitude since, based on the problem specifications.
based performance analysis might determine that small
highly implementaaionnsseccfic choices. First, instead
1cm (1,, a2,..., a,). The complexity of the
a;, b; < Since & < lcm(1, 2, 3, 4. of O n) O33, 600 n)) instead of the current O .n) O(10" n1).
60 this leads an optimal complexity
# Case 2: Problem 1118D1, solution #30. Given a homework of pages and n coffee cups with caffeine doses a1, .... an, the problem asks to compute the minimum number of days student must schedule to drink those cups so the pages he writes reach exceed m. When the student drinks cups on a single day labeled 022- ... as the first cup lets him write d, pages, the second max(0, a, 1). the third max(0, ai 1), and so on. Thus, the task find the smallest such sequence given n, m, and the list of caffeine values.
#include <bits/stde**..
24

---

using namespace std;
3 const long long int N 1e6; long long int n. n: vector<long long int> v(N);
6 bool check(long long int days) {
long long int pages
8 for (long long int 1 ;= pages max( vījl k);
i+t, j++)
10 1f
== days) = -1, ktt;
1 }
return pages m;
13 }
int32_t main()
15 scanf ("x11d", šn);
scanf ("xlld", an);
long long int sum
18 for (long long int = 8, < n; H1) scanf("x11) 20 sun + v[il;
&v[il);
}
22 if (sun < <))
printf("-1"))
return
}
(ort(v.beging. v. greater<<ong long int>());
27 long long int ans 1e16;
long long
1;
long long int high =;; while (low high) {
int mid (low high) if (check(mid))
long
12
min(ans, mid);
34
high mid 1;
else
low mid 1;
19
printf('"11d', ans);
return 8;
Listing 8: Example from our dataset: problem 1118D1, solution 30
The program in Listing 8 implements binary search the expected output, m. For each value of m, the binary search simulates writing pages over days days (function check) by iterating each cup exactly once, decrementing future cups by increasing offset k whenever day's 's quota is reached at line (lines 9-10).
When the binary search checks a candidate value, it always scans all n cups in the for loop at line 8, performing O(n) work per invocation. The binary search interval shrinks slowly, forcing multiple calls to check, which runs in O(n) time. Thus, when approaches its upper limit and m nearly equals the sum of all a, the combination of O(log n) binary search multiplied by an linear check becomes the dominant bottleneck.
void check_binary.. www.rryyssarcc..naairaaaaa (long sum, long
n, int search_iterations) 109 &5 sun >= a 88 (m > 0.9 * sum)) { cerr "Warning: binery_search_invaras invarinnt triggered extended binary search close capacity and requirement" << endl; abort();
1f 2
6
void check cucck_cupoook oup_order__. wtt.:orrdediviiinireeeeeee invarient vector<long long>8 long long n)
long long pestentisl_pages
10
int decronent__perationns 8;
for (size_t potential_pages += max(ell, v[i] - (long long)1); if (vli] > (long long) {
9; size +ti) (
13
++decrenent.operattoon
15
}
if ddecroment_aperatiion 5e 2s potential_paget < <) { cerr "Warning: cup_order_invarieen triggered extensive decrement operations" endl;
19
25

---

Listing 9: Performance-charan Performane-characteiiing constraints C++ checker functions: problem 1118D1, solution 30
WEDGE identifies two types of performaacce-charetttriiizgg constraints for this program, listed in Listing
1. The first that the binary search becomes expensive by performing a large number iterations when the necessary pages m are close to the cumulative caffeine sum of all cups and n is particularly large.
constraint www.rriaaaaaaaachiiiiie
finds
2. The second performance-charateee that the loop in check (lines 8-10) performs on the order of n x days operations. This happens because check iterates over the entire list of cups adding max(0, u[j] k) per page and resetting the loop counter every days iterations.
constraint (check_
finds
The first ccrerattcceeccaraattiiiinnggg constraint relates to binary search complexity and is generic since searching over large range is typically worst-case in terms of time complexity, the target value lies in the middle, forcing the search "Zig-zag" and perform large number of iterations.
In contrast, the second performance-charattrriie reasons about how the check loop resets i and increments & to model diminishing returns and then calculates again ma vIi] - k) for every cup. Note that the LLM borrows the same loop structure in the original check function (e.g. reset of and increment of k)) the checker code faithfully reproduces the slowdown pattern.
constraint is implementation-specitee The LLM
Case 3: Problem 546C, solution #567. Given a deck of n distinct cards split arbitrarily into two
decks, one per player), the problem asks simulate game in which, in each round, both players draw their top card, and the player with the higher value takes the opponent's card first and then their own, placing both at the bottom of their stack. When one player's stack becomes empty, the other wins.
#include <bits/stdes+.h using namespace std; queue<int> rl, r2;
int n. x, TLE, asd:
bool flag;
int main()
>>
8 for (int 1 1; <= x: itt) cin >> asd, (asd))
>> x;
for (int i
1++) ein >> asd, (asdd) r2.size()
u while (TLE < 18800006)
if (rl (ri.size()
13
flag 1;
break:
15
TLE+,;
int #1. r2. rl.pop(). r2.pap(); if
r2. front(::
18
20
r1 pv), p1.push(u);
else
22
(u),, push(v)())
}
if (Flag)
sri.s == 8) << TLE << endl;
27
else
else puts("-1"); return 8;
Listing 10: Example from our dataset: problem 546C, solution 567
The program Listing simulates the game by representing the player as two queues. In each round, the implementation pops the head of each queue, compares the two values and adds both
26

---

elements the queue with the highest value of the If either queue is empty, the program terminates. While straightforward, the implementation has two significant flaws. First, the code does not store past game states after each round. This leads the simulation to repeat the same deck configurations repeatedly until the TLE = 10 threshold is met instead of breaking early if a cycle detected, thus wasting many CPU cycles. Second, if the largest cards in either deck differ by small amount (e.g.. S 1) the main loop will iterate for significantly more trials. When neither player's top card is consistently stronger, the pop/push operations keep both queues nearly the same size. This balanced exchange prevents either queue from becoming empty quick, forcing multiple extra iterations of the same pop/push logic.
// Check if the queue confi configurations gurations have repeated, indicating cycle void baick_cclle_invrrannn (const queuekint>2
queuexintad r2, unordered
seenConf coanCcnniggurate gurrations))
string config;
auto copyl rl, copy2 r2;
while (capy leppyl.)))yy)). config costing(coayl.frann ":"copyl. t= "I"puhile
(copy2. enptyy ())
config += co_string(copp2 ())
popy).pop();
(seenCanfigurations find(config) seenConfigurations end()) cerr << "Warning: Cycle detected potential infinite loop" << endl;
11
seenConfiguratioon (t
14 }
16 // Check if neither player can win quickly due to balanced card strength check_balance brack_balance_invrrinn intreeeiivvriiinttt (const queue <int>á rl, const queue<int>4 r2) {
18
int max1 *nax_element (F1 front(), r1. r1. back
int max2 *nax_element (r2. (r2.front() r2. ra.back());
if (abs nax2) <s 1) { // Arbitrarily chosen threshold for similar strength
cerr << "Karning: Balanced card strength prolanged game possible" << endl;
23
35 // check for excessive number of rounds
26 void check_ excessive_rounds
TLE) if (TLE 1808) ( // Example threshold, be adjusted for practical purposes 28 cerr << "Marning: Excessive number of game raunds" << and];
0
Listing 11: PC-constraints C++ checker functions: problem 546C, solution 567
WEDGE identifies three types of perfomanne-charrtteriiing constraints for this program, listed in Listing 11.
1.
The first perfornance-charactriiingg constraint Berlcck_cclle_nne invariant) checks whether the distribution of the decks prone repeated states. The LLM detects that the original implementation does not take into account repetitions to terminate the main loop thus inputs with pathology likely force the loop at line 11 iterate until reaching the TLE = 10 threshold wasting unnecessary cycles.
2.
The second performance- performance-ccaarcttriiii characterizing constraint for "back-an -akk--dddfrrh push operation which cause minimal net change in queue size and prolong the game. The inefficiency comes from the two push calls per round (lines 20 and 22) and the fact that the losing card is enqueued first. This particular ordering choice leads to "reversing" the first player's win since eventually, the smaller card, which was enqueued first will move back the second player, canceling the gains of the first one.
checks
3. The third performance-chaarccttiiiii constraint srreec__exeesiiie )ouunds)) simply reflect a generic and straightforward intuition: more loop iterations means more CPU cycles and more running time.
While the third performance performance-charadn characterizing constraint is generic and could have been synthesized by an LLM without reasoning about the code, the first two are impleneentaiion-specinn simulation with bounded state that can revisit prior configurations is prone to cycles. However, this is problematic only when such program does not track repeated states, which is precisely what happens in this case. Moreover, the "back-an andk--andffrrth" card exchange property is highly specific the
Any queue-based
27

---

program the L.M is reasoning about. happens precisely because of the choice of enqueuing order. Should the implementation enqueue the two values in the opposite order, would be unlikely that there any observable "back-and-forth where cards move from one queue another and then back again.
# Case 4: Problem 16B, solution #34. Given set of containers, where the i-th container holds a; match boxes, each containing b, matches, the goal is to select up to n boxes (without splitting boxes) to carry in backpack so to maximize the total number of matches carried away.
#include <bits/stdc**. using
std; long long sunofdigits(string s)
long long
8;
5 for (long long == 8; 1 size() i+t)
int digit s[i] '0";
sun += digit;
}
return
10
m)in()
12 int n; vector<pairrint,
cin >>
15 int m;
cin >> n;
17 for (int = 0; n; i++) (
int y;
19 cin >> x >>
pairsint, int> p(x, y):
w.push_back(p))
22 }
int
24
for (int i 9; size 1; i++)
for (int ==1- 1; size(); j+t)
26
if [wLi]. > [Lil. {
pair
v[il;
v[iJ v[JJ:
v[jl =
31
}
33
int ans = 0;
(int 0; s.s i++)
int counter 8;
36
if (sum == n)
break:
38
int
suB;
40
while (counter < first first & t--)
countert*;
42
sum+*;
43
ans v[i]. second;
45 }
cout ans endl;
47
return 0;
Listing 12: Example from our dataset: problem 16B, solution 34
The code in Listing 12 performs two stages to solve the problem. First, performs simple ((m)) sort (lines 24-32) that orders the containers by their matches per box b, descendingly. Second, it tries to fill the backpack in a greedy fashion (lines 34-45), as follows: For each container sorted order, enters while loop (line 40) picks boxes one by one, decrementing the remaining capacity per box until either the container's 's supply is exhausted, or the capacity aggregator variable sum reaches n. Note that before entering the inner loop decrements exactly once per box being packed (line 39). Thus large n causes the code to run one iteration for each available box across all containers. Moreover, if is much larger than the sum of all box capacities, the code still visits every box which yields a computational cost linear in the total capacity. Also, the code does not appear to terminate early if the box supply is exhausted. The code breaks out of the outer loop only the current aggregated box capacity is equals to (lines 36-37). If the supply is smaller, however, the outer loop iterates unnecessarily through all containers.
28

---

void large-n.invariantC (int n, int const vactor<pair int>> long long totalBoxes =
for (const autoš container : v)
totalBoxes + fontainer.first;
if 10 totalBoxes)
cerr "Marning: Perfornance bottleneck condition triggered is much larger than available matchboxes" << endl;
10
11 void check wtt_ssssaalaala____e_e_______aee boxes____oe_____eeeee inves_invrrianteo (int n, int n, const vectorspair<int, int v) long long totalBoxes 8;
13
far (const autož container : v)
totalBoxes container.first,
15
(totalBoxes n 18)
cerr << "Warning: Perfornance bottleneck condition triggered insufficient matchboxes compared to n" endl;
Listing 13: PC-constraints as C++ checker functions: problem 16B, solution 34
WEDGE identifies two types of pc-constraints for this program, listed in 7.
The first perfrrnance-characteriiie
constraint
Laage_nniivaal
detects when the target
capacity n vastly exceeds the total number of available boxes. The inner loop (lines 40-44) exccutes exactly one iteration per box taken. So, the mode infers that when is significantly larger than the available boxes, the code performs O o,) iterations since each time it decrements by 1.
The second ieffformnnne-chractttreeee when the aggregate supply of boxes is substantially less than n, since the loop break condition (line 37) applies only when the bag is exactly full. Otherwise, the outer loop (line 34) iterates over all containers, wasting cycles when capacity is no longer available.
constraint Brreck_small_tttalle ceattal_bxees_iiee iniiinivarintt detects
A purely specification or problem-statement based performance analysis could infer that larger n could cause longer execution, and that a typical implementation would iterate until the capacity is full or exceeded. However, the first constraint hinges on the implementation choice of simulating each box by decrementing This suboptimal because to solve the problem, the algorithm only needs to know how many boxes to take, not to process them individually. Similarly, the second constraint speculates that the code does not exit immediately once is determined that the matchbox supply depleted before reaching n.
D Broader Impact
The positive impact of our research includes the following.
First, we release performance test benchmark that can evaluate the efficiency of LLM -LL--geeertted code and iefoormnnce-ippovinggg code edits, which can facilitate future research.
Second, we develop a methodology to generate stress tests by combining the advantage of the reasoning ability of LLMSs and the searching ability of fuzzing, which can inspire future research in performance test generation on real-world software.
Third, instead of introducing more ambitious task formulations and calling for LLM agentic workflows, we advocate constraining the role of LLMs in system reliability and security applications. We hope the general paradigm described in this paper, i.e., generating code specifications to interact with existing expert-developer program reasoning tools, can help the community rethink how LLMs should participate in critical applications.
The concrete negative impact is our approach could be potentially used by malicious attackers to curate stressing inputs to perform Denial-of-Serve (DoS) attacks [80]. We aim to study the positive usage of our approach, e.g., finding performance issues large-scale systems, to find and mitigate these potential vulnerabilities.
29

---

E
Prompts
E.1 Perfornanee-Charzcteiiiinn Constraint Reasoning Prompt
(A) Context
You experienced C software engineer focusing performance bottlenecks. You have:
problem statement describing task algorithm (with constraints such & 100).
program that implements solution to that problem.
3. Two inputs: a "fast" input that completes quickly, and "slow" input that takes much longer both inputs have similar size/structure.
4. Line-level hit counts for both runs, showing which lines get hit significantly more often the slow input.
Your goal is to diagnose why the program runs slowly for the slow input and derive conditions invariants that capture what triggers this slowdown.
(B) Tasks: Analyze the given code and generate performance- invariants in natural language Phase I: Identify expensive inefficient code fragments.
Compare line-level hit counts between the fast and slow runs.
Pinpoint lines or functions that get significantly more hits under the slow input.
3. Infer how these lines might be interacting with data structures, loops, recursion, ctc., especially as they relate to the input constraints (e.g.. < 100).
Phase 2: Derive celoormannc--caracteriiiii
invariants (natural language).
Generate natural language statements that describe conditions under which the program likely enters a slow
path.
2. Avoid using specific numeric values from the slow input; abstract them into categories or thresholds. However, make sure those thresholds adhere to the input constraints of the problem.
Correlate these conditions strongly input patterss (e.g.. "when is close 100 and there nested loop."
or "when data structure repeatedly sorted")).
4. Ensure your statements are broad enough to catch possible future slow scenarios, but still reflect realistic triggers given the constraints (like 100).
Note that not all performance-characteerr following examples
invariants about maximising input size. You may refer to the inspiration some maximising the input size, some not not simply replicate them exactly. Rather, use them as inspiration to infer and tailor performance-charactoriin invariants tailored for the C code and problem statement you were asked to analize: (Include the same examples you have, with indentation split lines appropriately.)
(C) Output Requirements
1. Provide a list of natural language performance invariants explaining under what conditions the code slows down.
not mention or rely on exact values from provided slow input.
3. Use or suggest threshold values that align with problem constraints (e.g.. S 100).
4. The output should be concise, descriptive set of statements about performance triggers.
Important Considerations
Avoid hardcoding. Don't rely solely on the exact values from the provided slow input; think terms of categories or thresholds that lead to slow execution.
2. Avoid checks inside tight loops. Place checks in way that does not significantly degrade performance.
3. Focus fuzzer utility. The checks should help fuzzer detect slow performance triggers by hitting these conditions.
(E) Problem Statement
prollem_sttteme
(F) Program Solving the Problem Statement me__solution
(G) The Slow & Fast Inputs
(G.1) Slow Input
slow +low_input
(G.2) Fast Input
fast_input
(H) Hit Count Information of Slow Input and Fast Input (Aggregated):
product_cov
30

---

E.2
Constraint Checker Generation Prompt
(A) Context
You have already:
Identified expensive code fragments (Phase 1).
2. Derived performance- ceaaaaancccchrrttriiinng invariants in natural language (Phase 2).
Now. you MUST transform these invariants into runtime checks and integrate them into the given C++ program.
(B) Tasks: Revisit the performance performance-chaaactrrssttt invariants you inferred natural langauge and write faithful, error-free C++ code snippets to implement them.
You MUST perform this task in two phases and provide separate answers for both: First, translating the invariants into checker code in C++ (phase below). Second, integrating those checker C++ code snippets with the original program which you inferred those invariants (phase 4, below).
Phase 3: Implement the natural language invariants inferred previously. in C++. In this phase you are asked to, For each natural language invariant from Phase 2, you MUST produce C++ code that checks the condition runtime.
You MUST NOT relax or trivialize checker code implementing these perfomance-charrcteriiing invariants. You MUST faithfully implement them as described.
3. Use the following template for writing checker code in C++ which could also be implemented as helper function:
if (/* condi iin based on
invariant */)
cerr "Warning: Performance bottleneck condition triggered!" a endl;
abort(); }
Note that not all performannc-cchrratteiiingg invariants are about maximising input size. You may refer to the following examples for inspiration - some maximising the input size, some not - but do not simply replicate them exactly. Rather, use them inspiration to infer and tailor perforraace--hharattriiingg invariants tailored for the C++ code and problem statement you were asked to analize: in-context examples.....
Phase 4: Propagate and insert conditional checks. In this phase you are asked to,
1. Place cach check at effective point in the control/data flow (c.g., after reading inputs, before heavy loops) so you add overhead in tight loops. Note that the checker code could also implemented as helper function.
If multiple checks overlap, merge or adjust them carefully to avoid redundant warnings.
3. Provide the final, instrumented C++ code in code fences. Ensure it compiles cleanly and runs without errors. For cach inserted check, add short comment explaining which bottleneck it detects.
Note the following important considerations when translating the inferred performance caaence-chraatrzzinggg invariants into code and propagating the checkers to the most effective program point by instrumenting the original code:
1. Avoid hardcoding. Don't 't rely solely the exact values from the provided slow input; think in terms of categories thresholds that lead slow execution.
addition to the warning message, remember to insert an abort t statement the the checker.
3. Focus on fuzzer utility. The checks should help a fuzzer detect slow performance triggers by hitting these conditions.
As refresher: below you provided with the same program statement and C++ code for which you already inferred performance-hharatttiiiii invariants:
Problem statement: problem_s statementttettttttt
Solution (C++ code): solution
31

---

E.3
Performanne--onstrrinttAwaa Mutator Generation Prompt
Here is an example custom mutator provided + repo:
mutator_ead _exampee
Could you learn from it and generate a new onc?
The constraints of imput described here:
Problem begins
mroblem_statemer Problem ends
Here are some example imputs that you can use as reference: reference_inputs
Here are the performance related conditions summarized by another LLM, e-g-- bacck_pef__conittiieo (condi tion). These conditions are believed to be related to performance of the solution, ie., when the conditions satisfied, the solution will likely slower than when they not satisifed. Please leam from them so that generated mutator can produce more inputs to satisfy the conditions so that the generated inputs can make the solution run slower.
Constraints summary begins constraints. tonteettssccontet Constraints summary ends
As context, here is solution program (along with coverage and hit count information under slow/fast inputs) where the constraints are generated on:
Please note that: 1. You should ensure the mutated inputs follow the input constraints as much as possible. Note that 100000(10*5) usually written 105, 1000000(10M0) (10000((10)))))) is usually written 106, You should implement an input generator and incorporate randomly choose to mutate the last input or use the generator to generate inputs from scratch. Note that you should avoid using random generator with a large range of values when generating the size input (c.g., length of array, etc.), c.g., random. randint(1, 10000) (say 10000 is the upper bound), it may not stress the program enough. Instead, closer to the upper bound, like 10000, 9999, 9990 or random. randint (9900, 10000), etc. Feel free to directly use the upper bound as the size of the input. But for numbers that are not the size of the input, you may want to generate random values to improve the input diversity and cover different patterns.
the mutator. so each iteration can
values that
likely to
inefficiencies, for example, values that
You should try implement multiple mutation operations that be randomly selected. You implement mutation operations that could potentially explore corner cases the program (e.g.. upper/lower bound).
You can add try catch block to the mutation module so that the mutation failed you can fall back to generator since the generator is helieved to be more robust.
5. Please make
use bytearray(ste. need mutable objects; the latter will produce immutable objects.
'utf-8') to transform string hytcarray, instead of wissst.eeee entode))
32

---

E,4 Baseline TG-prompt Prompt
You are an experieneed Python software engineer. Your task is to produce a test generator form of a Python program that, based on the input specifications the problem statement, generates tests that exhaust the solutions of the problem more.
Problem Statement (surrounded by leading and trailing
"):
Problem begins
problem_s cooblem_statteee stattment
Problem ends
Based on the above information, you will work in phases:
Phase 1: Define Stress Test Specifications.
Based the problem statement, describe the size, shape, and range of potential inputs.
Identify input patterns that can maximize inefficiencies the "slow" programs.
Don't t just limit the generator into generating tests that maximize input size, but suggest specific values or
patterns for inputs that can stress the slow programs (c.g.. sorted arrays, repeated elements, specific edge cases),
Explain how the inputs should be designed exploit algorithmic inefficiencies implementation anti anti-patterns.
Phase Implement Test Generator
Write a Python script to generate the tests described in the previous phase.
The script should:
Follow the input format specified in the problem statement. Note that 10000 (105) is usually written
105. 100000 (106) usually written as 106, etc.
Maximize stress on the programs to make those inefficient programs get TLE or MLE.
Avoid using random generator with large range of values when generating the size input (c.g., length of array, etc.), c.g., random. randint(1, 10000) (say 10000 is the upper bound), as it may not stress the program enough. Instead, use values that are more likely to cause inefficiencies. example, values that same or closer to the upper bound, like 10000, 9999, 9990 or random. randint (9900, 18000), etc. Feel free to directly use the upper bound as the size the input.
For numbers that not the size of the input, generate random values to improve input diversity and cover different patterns.
The test generator should generate total of number_of_
test cases,
Read an argument that specifies directory and write all test cases pest_00.inn'. 'test_02.in', etc., into the directory. E.g., executing python gen.py output will produce 'test_01. in',
"test_02. in', etc., in the output_directory directory.
33

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract outlines: (1) novel framework (WEDGE) for synthesizing
performance-characteriiia constraints, (2) integration with fuzzing, and (3) empirical results compared with state-of-the-art baselines. These points are substantiated Sections
3-4.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of the work in Section 6.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
34

---

Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [NA]
Justification:
The paper contains theoretical result. The approach evaluated empirically,
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We described the environment setup and reproduction settings Section 4.1. Source code and data are public at https://gt thub. www//Chi Sttm//CChhieelllaa/eerooooo
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
35

---

5. Open access to data and code
Question: Does the paper provide open the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We released the source code, data, and corresponding instructions to reproduce our experimental results at https: com http://ocooocccSSeaa/aeeeeeeeee
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cc
public/ (oolli/ggiies/Cooee Saaide//CoeSuumissiiii ssionPolicy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (ht / /nips. wttpccccppccccceeecccecceccccllt tttggggdddddddeuiieeeeeee wwwp::uuuuiissisiiiiiiii.ii ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We didn't train any models. We mainly rely L.M APIs. We specified the subject selection criteria, model ids and parameters e.g., temperature. We also provides our prompt templates Section E.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: For the main experiment we repeat each test execution (solution + test input) for five times and record the average execution time/instruction count. We also report the variance of both metrics in Section I.
Guidelines:
The answer NA means that the paper does not include experiments.
36

---

The authors should answer "Yes" if the results accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We included the specs of the machines we used in the detailed experiment setup in the Appendix A.4.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https://neur:: http::ppss.pppblllctttciciioa...
Answer: [Yes]
Justification:
Our research conform in every respect with the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
37

---

Justification: We discussed potential impacts like accelerating and improving evaluation of -.LM-geeerated code, helping avoid deploying inefficient code in production (e.g., ener- gyfresouree savings), contributing benchmark (PERFFORGE) the community for more rigorous performance evaluation. The detailed discussion in Section D.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper does not introduce particular safety risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cite their papers and discuss the related works (which have been granted by the authors for public use) in Section
Guidelines:
The answer NA means that the paper does not existing assets.
38

---

The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paper thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-pace re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our work does not release assets.
Guidelines: We document the new assests introduced with comprehensive github readme file.
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
39

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [Yes]
Justification: We describe the usage of LLMs as an important component of our method in Section 3
This is clearly described and central to the novelty of WEDGE.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer our LLM policy what should or should not be described.
htt////rrpp..ccooofeeereeee///// for
40


Reviews:
[{"review_id": "42PkK8irF2", "reviewer": "Reviewer_trS2", "summary": "This paper proposes WEDGE, a framework for generating performance-stressing tests given the program under test.\n\nWEDGE uses a combination of LLMs and fuzzers to generate such tests. It first collects some contrasting pairs of test inputs that are similar on the surface but differs in instruction count to run. Then it utilizes LLMs to analyze the performance critical regions in the code and generate performance-characterizing constraints at the beginning of these regions. After the constraints are inserted, a fuzzer is used to conduct coverage-guided fuzzing, which needs to get through these constraints to improve coverage, thus satisfying these constraints.\n\nExperiments show that WEDGE-generated tests can greatly slow the programs down. Also in terms of downstream tasks, WEDGE tests can be a better feedback signal for performance-improving refinements.", "questions": "1. How generalizable is this method to more complicated projects compared to single programs?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths:\n\n1. The combination of LLMs and fuzzing is interesting and intuitive. LLMs, with their knowledge about algorithms and data structures and their worst-case scenarios, are used to identify the performance-critical parts and generate constraints on performance-stressing program states. While fuzzers are used to actually create inputs that meet these constraints.\n\n2. Very clear advantage over baselines and significant improvements in downstream tasks. The method could have impacts on test-time scaling of compute for coding LLMs as better signals can improve iterative refinement. It may also serve as better rewards for model training.", "was_revised": true, "final_justification": "I'm keeping my (already-high) rating.", "rebuttal": "We are grateful for your time, effort, and leaving encouraging comments. We address your comments and questions in the following.\n\n**Q1: How generalizable is this method to more complicated projects compared to single programs?**\n\nWe 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].\n\nOur 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.\n\n[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.\n\n[2] Liu, Tianyang, Canwen Xu, and Julian McAuley. \"Repobench: Benchmarking repository-level code auto-completion systems.\" arXiv preprint arXiv:2306.03091 (2023).\n\n[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).\n\n[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).\n\n[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).\n\n[6] Serebryany, Kostya. \"{OSS-Fuzz}-Google's continuous fuzzing service for open source software.\" (2017).\n\n[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\n\n[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.\n\n[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)."}, {"review_id": "hCeKkU96z6", "reviewer": "Reviewer_b8hS", "summary": "The paper presents WEDGE, a novel framework that synthesizes performance-characterizing constraints to generate performance-stressing test inputs for code. By leveraging contrastive execution profiling and guiding fuzzing via LLM-inferred constraints, WEDGE exposes inefficiencies that size-based test generation methods often miss. The resulting test suite, PERFFORGE, stresses programs more effectively, leading to better optimization and evaluation outcomes when used with state-of-the-art tools like EFFI-LEARNER and PIE. The authors support their claims with robust empirical results and thoughtful ablation studies, making this work a compelling contribution to the field of LLM-based code evaluation and optimization.", "questions": "* What is the cost in time and tokens?\n* I'd suggest using an anonymous github https://anonymous.4open.science/ instead.\n* Given the iterative prompt-refine loop and profiling overhead, can you quantify the average cost (in tokens/runtime) per test case?\n* Do different constraints generated for the same problem typically yield different slow paths? Or is there convergence to a few common patterns?", "limitations": "* The paper is somewhat narrowed down to a specific domain and the evaluation is focused on competitive programming-style problems.\n* The authors do not explore the generalizability to real-world systems or codebases is not explored.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n* One thing that I like is that WEDGE avoids naive input size scaling by synthesizing performance-characterizing constraints, like gcd(a, b) not dividing c in a nested loop problem. I feel that this enables precise targeting of inefficiencies beyond just large inputs, for instance, for the Diophantine example in Figure 2.\n* Contrastive profiling and fuzzing seems quite novel and effective.\n* Good evaluation results \n* Strong ablation study and the results justify the proposed solution.\n\nWeaknesses:\n* I don't like that each solution requires profiling, prompting and instrumentation. \n* The paper is somewhat narrowed down to a specific domain and the evaluation is focused on competitive programming-style problems.\n* The authors do not explore the generalizability to real-world systems or codebases is not explored.", "was_revised": true, "final_justification": "Thank you. I'll keep my score. The author successfully resolved my concerns about the generalizability. However, I still feel that the each solution requires profiling and prompting, which is something I don't find the best option.", "rebuttal": "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\n\n**Q1: What is the cost in time and tokens? Quantify the average cost (in tokens/runtime) per test case**\n\nThanks for pointing out this important question. We break the cost down for different stages as follows (**per solution program**):\n\n| Stage   | Tokens | Time |\n| -------- | ------- | ------- |\n| contrastive input pair mining | N/A  |  99.65 executions, 15.46s  |\n| profiling feedback collection | N/A   | 2 executions |\n| PC constraint reasoning and constraint checker generation  |  9633.16  |  N/A  |\n| constraint-aware mutator generation   |  6905.27  |  180s fuzzing dry run  |\n| constraint-guided fuzzing   |  N/A  | 1 hour fixed budget   |\n**Average test cases generated: 63.99.**\n\nWe will include the results in the updated version of the paper.\n\n\n**Q2: The paper is somewhat narrowed down to a specific domain and the evaluation is focused on competitive programming-style problems**\n\nThanks 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).\n\n**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.\n\n**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.\n\n[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\n\n[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).\n\n[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).\n\n[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).\n\n**Q3: The authors do not explore the generalizability to real-world systems or codebases is not explored.**\n\nWe 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:\n\n    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].\n\n    2. Wedge would synthesize PC‑constraints for each target function and instrument the function following our original setup.\n\n    3. Wedge additionally sets the checker as the coverage objective [5] or relies on path pruning [6,7] to remove unreachable paths.\n\n    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].\n\n[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.\n\n[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.\n\n[3] Serebryany, Kostya. \"{OSS-Fuzz}-Google's continuous fuzzing service for open source software.\" (2017).\n\n[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.\n\n[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.\n\n[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.\n\n[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.\n\n**Q4: I don't like that each solution requires profiling, prompting and instrumentation.**\n\nThank 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."}, {"review_id": "DnYXu4yo6g", "reviewer": "Reviewer_HVF9", "summary": "This paper proposes a framework, WEDGE, for generating additional inputs for performance tests based on the performance profiles of already available inputs. The framework leverages LLM for synthesizing performance constraints from slow and fast execution profiles from already available inputs. These constraints are then integrated with a fuzzer to generate performance-stressing test inputs. Experimental results show that WEDGE generated tests lead programs to execute, on average, 84.5%\nmore CPU instructions than the SOTA approach.", "questions": "1. 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?\n\n2. Given a performance constraint can be synthesized, can LLM improve the code given the performance constraints as prompt (without generating additional inputs)?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n- The paper targets an challenging problem of evaluating performance for efficient LLM code generation. Overall, the paper is a well written and the proposed approach is easy to follow. \n\n- Leveraging LLM to synthesize performance constraints and use that as an intermediate step to generate more targeted performance-stressing input is a novel approach. Experimental results show utility of the proposed approach in improving performance of LLM generated code.\n\n\nWeakness\n\n- 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. \n\n- 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.", "was_revised": true, "final_justification": "This paper presents a new approach of generating performance constraints that addresses a timely challenge of generating high-performance code using LLM. The authors provide a clear description of the approach and experimental results show the effectiveness of the proposed approach. The ablation studies strongly justify the contributions of this work.", "rebuttal": "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.\n\n**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.**\n\nWe 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.\n\n**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?**\n\nGood 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.\n\n| Profiling           | Execution Time | Total Memory Usage | Max Memory Usage | Execution Time (ict) |\n|---------------------|----------------|---------------------|------------------|-----------------------|\n| Wedge tests       | 45.33%     | 56.26%          | 38.86%       | 73.98%            |\n| AFL++ tests        | 14.80%         | 18.69%              | 11.84%           | 26.07%                |\n\nUsing 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.\n\n**Q3: Given a performance constraint can be synthesized, can LLM improve the code given the performance constraints as prompt (without generating additional inputs)?**\n\nThis 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). \n\nSpecifically, 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.\n\nObservation #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.\n\nObservation #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.\n\nObservation #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)\n\n| technique              | 16B-sol-34   | 546C-sol-567 | 633A-sol-622  | 1209B-sol-328 | 1182E-sol-22 |\n|------------------------|-------------:|-------------:|--------------:|--------------:|-------------:|\n| **Average instructions count** |             |             |              |              |             |\n| Original               | 1000323782.5 |   19583381.3 |   129818315.6 |    23436043.2 | n/a  |\n| LLM optimized no pcc   |    2261541.6 |    2336769.4 |      140243.7 |     2920159.2 | n/a |\n| LLM optimized w/ pcc   |    2261414.3 |    2320602.1 |      139907.5 |     5337538.5 | n/a |\n| **Median instructions count** |         |             |              |              |             |\n| Original               | 1596548458.0 |    2225882.0 |     2927145.5 |    30180433.0 | n/a |\n| LLM optimized no pcc   |    2274604.0 |    2297157.0 |      139920.0 |     3207311.0 | n/a |\n| LLM optimized w/ pcc   |    2274475.5 |    2281172.0 |      139855.0 |     6327841.5 | n/a |\n\nOur 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.\n\n**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.**\n\nDue 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.\n\nWEDGE 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.\n\n[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)."}, {"review_id": "mMKxynk6N3", "reviewer": "Reviewer_zqXK", "summary": "The authors propose a two-step pipeline for generating program inputs that cause slow performance. The first step uses an LLM to generate and instrument the target program with formulas that, when evaluated as true, should result in slow program execution. The second step uses an existing fuzzer to generate inputs that satisfy the formulas. The authors empirically evaluate their pipeline and find that, on average, they can generate program inputs that lead to longer execution times (in terms of the number of CPU instructions) than those generated by EVALPERF. Even better, they show that code optimizers can use their pipeline to generate more performant code.", "questions": "- What metrics or evidence did the authors use to determine that [12] is state-of-the-art in performance fuzzing?\n- Can the authors provide citations or empirical evidence to back up their claims about related work? Many performance-fuzzing papers are not cited.\n- What kind of performance bugs can the performance constraints capture? For example, can they express stateful performance issues? What other limitations are there? See, e.g., “SPIDER: Fuzzing for Stateful Performance Issues in the ONOS Software-Defined Network Controller” for an example of a test generator that does handle stateful performance issues.", "limitations": "No. See question 3 above.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n- Generating performance constraints to guide fuzzing is a nice idea.\n- The paper is easy to read; the figures and tables are informative.\n\n## Weaknesses\n- Makes strong claims about related work without evidence to support them. For example, “However, they are known to suffer from scalability issues such as path explosion, fine-grained performance profiling overhead, and the lack of oracles to precisely capture inefficient behaviors or symptom” is a sweeping dismissal of a large and diverse body of related work that the authors present without evidence. See question 2 below.\n- Questionable baselines for the empirical evaluation. See, e.g., question 1 below.\n- Does not consider limitations of the fundamental contributions of the approach. See question 3 below.", "was_revised": true, "final_justification": "My biggest concern with this work is how it engages with related work, both in\nterms of the literature review and the empirical evaluation. During the\nrebuttal, the authors provided new data to support their claims (e.g., that\ntheir performance overhead is lower than existing tools) and made important\ndistinctions between kinds of related work (e.g., symbolic execution versus\nfuzzing). \n\nMy second biggest concern was with over-claiming. The evaluation uses simple\nprograms and the authors do not outline the scope of their work (e.g., that it\ncannot easily be extended to handle stateful programs). The authors acknowledge\nthis in their rebuttal.\n\nGiven the authors rebuttal, I am willing to raise my recommendation to \"4:\nBorderline accept\". I worry that the changes the authors should make to the\nfinal version of the paper are too big, but I do believe that the authors agree\nwith the changes that need to be made.", "rebuttal": "We appreciate the time and effort you took to review our paper and provide valuable comments that will help us improve it further. \n\n**Q1: Makes strong claims about related work. Many performance-fuzzing papers are not cited.**\n\nThanks 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.\n\nRegarding “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. \n\nSpecifically, 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.\n\nFor 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.\n\nFor 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).\n\n| Technique  | Average exec_per_sec |\n| -------- | ------- |\n| perffuzz |59.68    |\n| perffuzz_wedge_inst | 47.05     |\n| wedge   | 87.11    |\n| afl_wedge_inst | 114.69    |\n\nWe 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.\n\nImportantly, 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.\n\n| Technique                | perffuzz | perffuzz_wedge_inst | Wedge | AFL_wedge_inst |\n|--------------------------|----------|----------------------|--------|----------------|\n| # of instructions (×$10^8$) | 0.71     | 0.76                 | 1.15   | 0.77           |\n| Slowdown over CC         | 0.89     | 0.91                 | 1.08   | 0.92           |\n\nWe 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.\n\n[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.\n\n[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.\n\n[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.\n\n[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."}]

Author rebuttal:

Meta-review: This paper addresses the interesting problem of generating performance-stressing test inputs for evaluating LLM-based code optimization techniques. The work tackles a timely challenge where current evaluation practices rely on correctness tests or simple length-stressing inputs that fail to reveal nuanced performance bottlenecks. The proposed WEDGE framework presents a novel approach that combines LLM-synthesized performance-characterizing constraints with fuzzing techniques to generate more effective performance tests.

The reviewers consistently praised the paper's technical contributions, highlighting the intuitive combination of LLMs with fuzzing, significant empirical improvements over baselines, and strong ablation studies. They also appreciated the clear presentation and demonstrated utility for improving code optimization effectiveness. On the other hand, reviewers raised concerns about the work's scope being limited to competitive programming problems rather than real-world systems, the overhead of requiring profiling and instrumentation for each solution, and the dependency on contrasting fast/slow input pairs. One reviewer also noted issues with the characterization of related work and missing comparisons with established performance fuzzing techniques.

The authors comprehensively addressed these concerns in their rebuttal through additional experiments, cost analyses, comparisons with performance fuzzing baselines, and honest discussions of current limitations.
Decision: Accept (poster)