Least-to-Most Prompting: Easy-to-Hard Generalization

Standard Few-Shot CoT:  See easy examples → Can only solve easy problems
Least-to-Most:          See easy examples → Decompose hard problem → Solve in sequence
                        → Can solve MUCH harder problems

Example:
Complex problem: "walk left twice and jump twice after walk"
Decomposition:
  1. "walk left twice"
  2. "walk left twice and jump twice after walk"  (combining)

Simple problem: "jump twice after walk left twice"
Decomposition:
  1. "walk left twice"
  2. "walk left twice and jump twice"  (combining)

Problem: "jump twice and walk left after walk right"

Decomposition:
  1. "jump twice"                          → Easy
  2. "walk left after walk right"          → Medium
  3. "jump twice and walk left after walk right" → Full (using answers from 1 and 2)

You will break complex problems into simpler subproblems.

Example:
Complex: "look opposite right twice and walk opposite left"
Decomposition:
1. "look opposite right twice"
2. "look opposite right twice and walk opposite left"


Complex: "run left twice after run right"
Decomposition:
1. "run left twice"
2. "run left twice after run right" (keeping original structure)


Complex: "look twice after run"
Decomposition:
1. "look twice"
2. "look twice after run" (addressing the harder part after)


Now decompose this:
Complex: "{problem}"
Decomposition:

Now solve each subproblem one at a time. Use the solution of the
previous subproblem to help solve the next one.

Step 1: {subproblem_1}
Solution 1: {solution_1}

Step 2: {subproblem_2}, using Solution 1
Solution 2: {solution_2}

Step 3: {subproblem_3}, using Solutions 1 and 2
Solution 3: {solution_3}

def least_to_most(llm, problem: str, decomposition_examples: list,
                  solve_examples: list):
    """Least-to-Most: decompose, then solve sequentially."""

    # Phase 1: Decompose into subproblems
    decomp_prompt = build_decomposition_prompt(
        decomposition_examples, problem
    )
    decomposition = llm.generate(decomp_prompt)
    subproblems = parse_subproblems(decomposition)  # ["sub1", "sub2", ...]

    # Phase 2: Solve each subproblem, feeding answers forward
    solutions = []
    for i, subproblem in enumerate(subproblems):
        solve_prompt = build_solve_prompt(
            solve_examples, subproblems, solutions, current_idx=i
        )
        answer = llm.generate(solve_prompt)
        solutions.append(answer)

    return {
        "decomposition": subproblems,
        "solutions": solutions,
        "final_answer": solutions[-1]
    }


def parse_subproblems(decomposition_text: str) -> list:
    """Extract numbered subproblems from decomposition output."""
    import re
    matches = re.findall(r'\d+\.\s+(.+)', decomposition_text)
    return matches if matches else [decomposition_text]


def build_decomposition_prompt(examples: list, problem: str) -> str:
    """Build the few-shot decomposition prompt (see Prompt Structure above)."""
    prompt = "You will break complex problems into simpler subproblems.\n\n"
    for ex in examples:
        prompt += f"Complex: \"{ex['complex']}\"\n"
        prompt += "Decomposition:\n"
        for i, step in enumerate(ex['decomposition'], 1):
            prompt += f"{i}. \"{step}\"\n"
        prompt += "\n"
    prompt += f"Now decompose this:\nComplex: \"{problem}\"\nDecomposition:\n"
    return prompt


def build_solve_prompt(examples: list, subproblems: list,
                       solutions: list, current_idx: int) -> str:
    """Build the sequential solving prompt, feeding prior answers forward."""
    prompt = "Now solve each subproblem one at a time.\n\n"
    for i in range(current_idx):
        prompt += f"Step {i+1}: {subproblems[i]}\nSolution {i+1}: {solutions[i]}\n\n"
    prompt += f"Step {current_idx+1}: {subproblems[current_idx]}"
    if current_idx > 0:
        prompt += f", using Solutions 1-{current_idx}"
    prompt += "\nSolution:"
    return prompt

# pseudo-code: check for circular dependencies via topological sort.
# In practice, use a library like networkx or a simple DFS cycle detector.
def is_decomposition_valid(subproblems: list, dependencies: dict) -> bool:
    """Check for circular dependencies via topological sort."""
    from collections import deque
    in_degree = {s: 0 for s in subproblems}
    for s in subproblems:
        for dep in dependencies.get(s, []):
            in_degree[s] += 1
    queue = deque([s for s in subproblems if in_degree[s] == 0])
    visited = 0
    while queue:
        node = queue.popleft()
        visited += 1
        for s in subproblems:
            if node in dependencies.get(s, []):
                in_degree[s] -= 1
                if in_degree[s] == 0:
                    queue.append(s)
    return visited == len(subproblems)

Subproblem 1: One operation     (difficulty: 1/10)
Subproblem 2: Two operations    (difficulty: 3/10)
Subproblem 3: Three operations  (difficulty: 6/10)
Subproblem 4: Full problem      (difficulty: 9/10)