Code-MUE: Measuring Code LLMs' Uncertainty through Execution-based Semantic Interaction Graphs

This directory contains the core implementation and experimental pipeline for our paper “Code-MUE: Measuring Code LLMs' Uncertainty through Execution-based Semantic Interaction Graphs.” The key idea is to obtain each response’s I/O behavior via oracle-free random inputs, build a semantic interaction graph from I/O similarity, and use Von Neumann entropy as the uncertainty measure.

---

Structure (Key Files/Dirs)

• generate_response_api.py: Monte Carlo sampling for closed-source models (API)
• generate_response_local.py: Monte Carlo sampling for open-source models (local)
• original_outputs/: sampling outputs (one jsonl per configuration)
• post-processing1.py: extract code snippets from full responses (regex blocks)
• post-processing2.py: remove print / assert statements
• process_outputs/: stage-1 cleaned outputs
• process_outputs_no_print_assert/: stage-2 cleaned outputs (default output dir)
• post_process_outputs/: final cleaned outputs used in the paper (align by changing OUTPUT_DIR)
• pass_k_evaluation.py: pass@k evaluation
• pass_status_results/: per-response execution status (pass / timeout / error, etc.)
• similar_matrix.py: semantic interaction graph + Von Neumann entropy (core uncertainty metric)
• semantic_uncertainty_detailed_results/: uncertainty evaluation outputs
• baseline_CodeandResults/: baseline results used in the paper (see Baselines section)

Directory names can be modified via INPUT_DIR / OUTPUT_DIR constants at the top of each script.

---

1. Data Preparation (Monte Carlo Sampling)

We run Monte Carlo sampling for both closed-source and open-source models:

• Closed-source models: generate_response_api.py
• Open-source models: generate_response_local.py

Sampling outputs are saved to original_outputs/. Each configuration is stored as a separate jsonl file, e.g.:

original_outputs/deepseek-coder-6.7b-Instruct_codenet_pure200.jsonl

We use 4 × 8 = 32 configurations, so there are 32 jsonl files in original_outputs/.

---

2. Data Processing (Code Extraction + Denoising)

(a) Extract code snippets

post-processing1.py extracts the code portion from full responses:

• prefers python ... blocks
• handles incomplete Markdown blocks or blocks without language tags
• falls back to keyword-based heuristics

Output directory: process_outputs/

(b) Remove noisy statements

post-processing2.py further cleans code by removing:

• print(...)
• assert ...

This avoids interference with later testing.

Default output directory: process_outputs_no_print_assert/ (change to post_process_outputs/ to match the paper).

The final processed outputs still contain 32 jsonl files, which serve as the base data for all experiments (the paper uses post_process_outputs/).

---

3. Functional Evaluation (Pass@k)

To validate the uncertainty metric, we first compute model functional correctness:

• pass_k_evaluation.py computes Pass@k for all models on each dataset
• per-response execution status (pass / timeout / error, etc.) is saved under pass_status_results/

These statistics are used to check whether uncertainty aligns with actual execution correctness.

---

4. Uncertainty Evaluation (Core)

The core pipeline is implemented in similar_matrix.py:

1. Oracle-free random inputs: for each task, randomly sample from available test inputs to form an oracle-free test set.

2. Execute and collect I/O traces: run every response on the same input set to obtain its output sequence (I/O trace).

3. Build semantic similarity matrix: for any two responses, if they produce the same outputs on the same inputs, increase their similarity; this yields an N × N similarity matrix.

4. Compute Von Neumann entropy: normalize the similarity matrix to (\rho), compute its spectral entropy (Von Neumann entropy), and use it as the uncertainty score for that task.

Outputs are saved in semantic_uncertainty_detailed_results/, including:

• semantic_entropy (normalized uncertainty)
• raw_entropy (raw spectral entropy)
• similarity_matrix (full similarity matrix)
• pass_at_1 / pass_at_5 (functional baselines for comparison)

---

5. Baselines (Paper)

The directory baseline_CodeandResults/ contains the results of the three baselines reported in the paper:

• Length_cv
• Lexical_bleu
• semantic_codebert

---

6. Recommended Execution Order

1. Sampling: generate_response_api.py / generate_response_local.py
2. Code extraction: post-processing1.py
3. Remove print/assert: post-processing2.py
4. Pass@k evaluation: pass_k_evaluation.py
5. Uncertainty evaluation: similar_matrix.py

---

To extend to new models or datasets, add new configurations and generate the corresponding jsonl files.