Article

Cadence

Cadence is an evolutionary system that uses LLMs to generate, mutate, and improve heuristic solutions to NP-hard optimization problems, starting with the Travelling Salesman Problem (TSP).

Motivation

Inspired by AlphaEvolve (Google DeepMind), Cadence tests whether the evolutionary program synthesis paradigm can be applied to NP-hard problems using constrained, small-scale experiments — rather than requiring the massive compute of large research labs. Two core hypotheses drive it:

1. Hypothesis 1: Can LLMs design effective approximation and heuristic strategies for TSP?

2. Hypothesis 2: Can conclusions about scaling be drawn from a series of smaller, constrained evolutionary experiments?

The project connects to *Asymmetric Verifiability* (Verifier's Law, Jason Wei): TSP solutions are much cheaper to verify than to produce, which makes them a good target for iterative LLM-driven improvement.

Architecture

Cadence runs a continuous feedback loop where programs are treated as evolving entities in a SQLite-backed population:

1. Parent and Children Sampling — select a parent program and its lineage from SQLite

2. Prompt Construction — wrap the parent code, child history, and improvement instructions into a meta-prompt

3. LLM Code Generation — feed the prompt to gemini-2.5-pro; receive code diffs

4. Diff Application — apply diffs at function level (analogous to FunSearch)

5. Performance Evaluation — score each child over multi-seed deterministic TSP instances

6. Program Promotion — elite programs are promoted at configurable ELITISM_INTERVAL

7. Meta-prompting (optional) — periodically mutate the instructions themselves; extract lessons from past generations and inject them into the system prompt

Key Design Choices

  • Works at function granularity, not whole files
  • Lessons are extracted from generation batches and fed back as feedback to the LLM
  • Evaluation is deterministic (fixed seeds) to reduce noise in comparisons
  • The population is persistent across runs via SQLite

Related Pages

Sources

Evidence

Linked source: GitHub Repo: cadence

Linked source: Obsidian Source: Cadence - Evolving Code with LLMs for NP-Hard Problems