Cadence: Program Evolution via Large Language Models

Cadence implements an evolutionary system that uses large language models (LLMs) to iteratively generate, mutate, and improve programs for solving computational problems. The current implementation focuses on optimizing solutions to the Traveling Salesman Problem (TSP).

Architecture

flowchart TD
    A[Sample Parent Program] --> B[Build Prompt + Lesson]
    B --> C[LLM Generation of Code Diffs]
    C --> D[Apply Diff to Parent]
    D --> E[Evaluate on Test Suite]
    E --> F[Log to Database]
    F --> G{Generation Complete}
    G -->|Not Final| A
    G -->|Final| H[Extract Lesson]
    H --> B

Getting Started

Quickstart

Run the out-of-the-box examples:

# Hypothesis 1: Cost evolution
python run_h1_experiment.py --config_name h1_config

# Hypothesis 2: Scaling analysis
python run_h2_experiment.py --config_name h2_config

Results (h1_results.png, h2_scaling_analysis.png) and JSON summaries will appear in the project root.

Requirements & Installation

1. Clone the repo and enter directory:

   git clone https://github.com/yash-srivastava19/cadence.git
   cd cadence
   

2. Create and activate a virtual environment:

   python -m venv .venv
   .venv/bin/Activate
   

3. Install dependencies (using uv for reproducible installs):

    uv sync
   

Configuration with Hydra

All experiment scripts leverage Hydra for flexible, YAML-driven configuration. Sample conf/h1_config.yaml:

SEEDS: 10
GENERATIONS: 20
LESSON_INTERVAL: 4
API_MAX_RETRIES: 3
API_TIMEOUT: 60
hydra:
  run:
    dir: .                     # write outputs to project root
  output:
    subdir: null               # disable timestamped folders

Override on the command line without editing YAML:

# Change number of seeds and interval at runtime
git checkout main
python run_h1_experiment.py SEEDS=5 LESSON_INTERVAL=2

Usage Examples

Evolve a TSP Solver in Python

from src.tasks.tsp_task import TSPTask
from src.prompt_sampler import build
from src.llm import generate
from src.evolve import apply_diff

# Initialize problem with 10 cities
task = TSPTask(n_cities=10)
base_code = task.baseline_program
# Build a prompt without lessons
prompt = build((None, None, None, base_code, None), [], None)
# Call LLM to get diff
diffs = generate(prompt)
# Apply diff to generate a new child solution
child_code = apply_diff(base_code, diffs)

print("Baseline code:\n", base_code)
print("Evolved code:\n", child_code)

Extracting Lessons Programmatically

from src.meta_prompting import get_lesson_from_history
# Assume 'logs' is a list of experiment entries with 'generation' and 'cost'
lesson = get_lesson_from_history(logs, previous_lesson=None)
print("Heuristic lesson:", lesson)

Web Interface

Cadence provides a built-in Flask-based UI for live monitoring of experiments. Launch it with:

python ui/launch_ui.py

Then open your browser at http://localhost:5000 to explore real-time metrics, cost evolution plots, and logs.

Notes

• All code blocks must be marked with ### START_BLOCK and ### END_BLOCK.
• Prompts are built to explicitly instruct the LLM to only change marked blocks.
• Evaluation is deterministic using seeded inputs.
• The project uses uv for reproducible dependency management and performance.

Tips

• Use only standard Python libraries (math, itertools, re, etc.).
• Keep test inputs deterministic via seeds.
• Define a cost metric that is meaningful, consistent, and scalar.
• Try to avoid relying on random inside the generated programs themselves.

License

This project is licensed under the MIT License.

Citation

If you use Cadence in your research or projects, please cite:

@software{cadence2025,
  author = {Yash Srivastava},
  title = {{Cadence: Program Evolution via Large Language Models}},
  year = {2025},
  url = {https://github.com/yash-srivastava19/cadence},
  version = {main}
}