EffiPair: Improving the Efficiency of LLM-generated Code with Relative Contrastive Feedback

1. Problem Statement

Large Language Models (LLMs) are increasingly used for code generation, but the resulting programs are often functionally correct yet suboptimal in runtime and memory usage.

• Limitations of Current Approaches: Existing inference-time refinement methods rely on absolute execution feedback (e.g., scalar metrics like raw runtime or memory usage of a single program).
  • Information Inefficiency: Scalar values provide absolute performance data but fail to reveal why a program is slow or how it differs structurally from a better alternative.
  • High Overhead: Models must infer optimization directions indirectly, often requiring multiple iterations, extensive profiling, and high token consumption to converge on efficient solutions.
• Goal: To improve the efficiency of LLM-generated code at inference time without fine-tuning, while preserving functional correctness and minimizing computational/token overhead.

2. Methodology: EFFIPAIR

The authors propose EFFIPAIR, an inference-time iterative refinement framework centered on a new supervision signal called Relative Contrastive Feedback (RCF).

Core Concept: Relative Contrastive Feedback (RCF)

Instead of evaluating candidates in isolation, RCF compares two structurally similar programs solving the same task:

1. Reference ($p^+$): The most efficient correct program currently available.
2. Target ($p^-$): A correct but less efficient program that is structurally similar to $p^+$.
3. Feedback Signal: The system summarizes the execution differences between $p^+$ and $p^-$ into a compact, lightweight signal. This highlights specific operations or design choices in the slower program that cause inefficiency compared to the faster one.

Workflow

1. Candidate Generation: The LLM generates $N$ candidate programs for a given task.
2. Evaluation & Pooling: Candidates are checked for correctness and profiled for efficiency (runtime/memory). They are stored in a candidate pool.
3. Pairing Strategy:
   • The system selects a pair $(p^+, p^-)$ where $p^+$ is the best performer and $p^-$ is the worst performer among those that are structurally similar (measured by a weighted sum of embedding cosine similarity and Abstract Syntax Tree (AST) similarity).
   • This ensures the comparison is meaningful and isolates specific inefficiencies rather than broad algorithmic differences.
4. Feedback Synthesis:
   • A sampling profiler (Scalene) is used to identify "hotspots" (lines/functions consuming the most CPU/memory).
   • Instead of feeding raw traces, the system generates a compact summary (e.g., "hottest functions," "relative time shares") to minimize token usage.
5. Refinement: The LLM is prompted with the task description, the pair $(p^+, p^-)$, and the RCF summary. It is asked to produce a refined program that retains the correctness of $p^-$ but adopts the efficient design choices of $p^+$.
6. Iteration: The refined program is added back to the pool for subsequent rounds.

3. Key Contributions

1. Relative Contrastive Feedback (RCF): A novel supervision signal that transforms efficiency optimization from scalar reward maximization into a contrastive learning problem over program executions. It provides direct, actionable guidance on what to change.
2. EFFIPAIR Framework: A training-free, inference-time framework that operationalizes RCF. It integrates similarity-based pairing and summarized profiling to guide iterative refinement.
3. Token and Compute Efficiency: The paper demonstrates that summarized execution statistics are sufficient for effective contrastive feedback. This drastically reduces the overhead of profiling and prompting compared to prior methods.
4. Robustness: The framework maintains or improves functional correctness while optimizing efficiency, avoiding the "correctness regression" often seen in aggressive optimization loops.

4. Experimental Results

The authors evaluated EFFIPAIR on three code-efficiency benchmarks (EvalPerf, Mercury, ENAMEL) using state-of-the-art models (DeepSeek-Chat V3.2, Claude Sonnet 4.6, GPT-5.4, GPT-5.4 mini).

• Efficiency Gains:
  • EFFIPAIR consistently achieved the best efficiency metrics across all models.
  • Speedup: With DeepSeek-Chat V3.2, EFFIPAIR achieved up to a 1.5x speedup over generation without feedback.
  • Metrics: It outperformed baselines in DPS (efficiency relative to the nearest slower solution) and Beyond@1 (normalized runtime percentiles).
• Correctness:
  • EFFIPAIR preserved or improved Pass@1 scores. For example, on EvalPerf, it achieved 92.37% Pass@1, outperforming the baseline (86.44%) and LLM4EFFI (88.14%).
• Token Efficiency (vs. EffiLearner):
  • EFFIPAIR drastically reduced token usage compared to the prior state-of-the-art, EffiLearner.
  • Prompt Tokens: Reduced from 23.6M (EffiLearner) to ~200k (EFFIPAIR).
  • Completion Tokens: Reduced from 350k to ~77k.
• Iterative Behavior:
  • The majority of efficiency gains occurred in the first refinement round, suggesting high practical utility even with limited compute.
  • Correctness remained stable or improved across rounds, validating the safety of the pairing strategy.

5. Significance and Conclusion

• Paradigm Shift: The paper argues that relational feedback (comparing two programs) is superior to scalar feedback (evaluating one program) for code optimization. It provides clearer structural guidance to the LLM.
• Practicality: By using lightweight profiling summaries and training-free inference, EFFIPAIR makes test-time code optimization feasible for real-world deployment where re-training models is cost-prohibitive.
• Scalability: The massive reduction in token usage (90%+ reduction compared to prior work) suggests that this approach can be scaled to optimize large codebases without incurring prohibitive inference costs.

In summary, EFFIPAIR establishes that comparing structurally similar, inefficient, and efficient code pairs allows LLMs to learn optimization patterns more effectively and cheaply than relying on absolute performance metrics alone.