💬 NLP

PaT: Planning-after-Trial for Efficient Test-Time Code Generation

The paper proposes Planning-after-Trial (PaT), an adaptive test-time code generation policy that invokes a planner only upon verification failure, enabling a cost-efficient heterogeneous model configuration that significantly improves the cost-performance trade-off compared to rigid planning approaches.

Original authors: Youngsik Yoon, Sungjae Lee, Seockbean Song, Siwei Wang, Wei Chen, Jungseul Ok

Published 2026-05-11

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Youngsik Yoon, Sungjae Lee, Seockbean Song, Siwei Wang, Wei Chen, Jungseul Ok

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a complex puzzle, like a difficult level in a video game or a tricky math problem. You have a team of helpers to assist you, but they come in two flavors:

The Speedy Intern: Fast, cheap, and good at simple tasks, but sometimes gets stuck on really hard logic.
The Senior Architect: Slow, expensive, and brilliant at breaking down massive, confusing problems into smaller, manageable pieces.

The Old Way: "Plan First, Try Later"

Most current AI coding tools use a strategy called "Planning-before-Trial" (PbT).

Think of this like hiring the Senior Architect to look at every single puzzle you have, even the easy ones. Before you even try to solve a simple puzzle, the Architect spends a long time drawing up a complex blueprint.

The Problem: This is a waste of money and time. If the puzzle was easy, the Intern could have solved it in seconds without needing a blueprint. But because the system is rigid, it pays the high cost of the Architect for every single task, whether it's needed or not.

The New Way: "Try First, Plan Later" (PaT)

The paper introduces a new method called PaT (Planning-after-Trial). This flips the script.

Here is how PaT works, step-by-step:

The Trial: First, the Speedy Intern takes a crack at the problem immediately. They try to solve it directly.
The Check: The system runs a quick test to see if the Intern's solution works.
- If it works: Great! The job is done. You saved a fortune because you didn't need the expensive Architect.
- If it fails: The system realizes, "Oh, this one is actually hard."
The Intervention: Only when the Intern fails does the system call in the Senior Architect. The Architect doesn't just guess; they look at why the Intern failed and create a specific plan to break the big problem into smaller sub-tasks.
The Finish: The Intern then solves those smaller, easier sub-tasks, and the final solution is assembled.

The "Heterogeneous" Team-Up

The paper also suggests a clever team structure. Instead of using one giant, expensive brain for everything, PaT uses a mixed team:

The Intern (a smaller, cheaper AI model) does 90% of the work because most problems are actually easy.
The Architect (a massive, powerful AI model) is kept in reserve, only waking up when the Intern hits a wall.

Why This Matters

The authors tested this on many different coding challenges. Here is what they found:

It's Cheaper: By avoiding the expensive "Architect" step for easy problems, they cut the cost by about 69% compared to older methods.
It's Smarter: Even though they used a cheaper setup, the results were just as good (or better) than using a giant, expensive model for everything.
The Sweet Spot: They found that a small model doing the heavy lifting, guided occasionally by a big model, is the most efficient way to work. It's like having a fast car for the highway and a heavy-duty truck only for the off-road sections, rather than driving a truck everywhere.

The Bottom Line

The paper argues that we shouldn't treat every coding problem as if it requires a super-complex plan. Most problems are simple enough to solve with a quick try. By waiting to see if a problem is actually hard before spending money on a complex plan, we can build coding systems that are both faster and much cheaper without sacrificing quality.

Technical Summary: PaT: Planning-after-Trial for Efficient Test-Time Code Generation

Problem Statement

While Large Language Models (LLMs) have achieved significant success in code generation, scaling test-time computation to handle complex algorithmic logic often incurs prohibitive inference costs. Existing state-of-the-art methods predominantly adopt a rigid Planning-before-Trial (PbT) policy (e.g., FunCoder), where a planner decomposes problems into sub-tasks before any code generation attempt. This approach is inefficient because it applies expensive planning overhead to all problems, including a substantial fraction of "easy" instances that a model could solve directly without intervention. Consequently, these methods often fail to improve the cost-performance Pareto frontier, sometimes making smaller models with PbT more expensive and less effective than larger models using standard inference.

Methodology: Planning-after-Trial (PaT)

The authors propose Planning-after-Trial (PaT), an adaptive policy that inverts the conventional PbT paradigm. PaT operates on the principle that planning should be a reactive resource, invoked only when a direct attempt fails.

Core Workflow

Trial Phase: Given a problem specification $x$ , a generator model ( $M_G$ ) first attempts to solve the problem directly using a Best-of-N sampling strategy.
Verification: The generated candidates are verified against a test set $T(x)$ . The test cases are either provided by the benchmark or generated by an LLM to ensure robustness.
Adaptive Escalation:
- Success: If any candidate passes all tests, the process terminates immediately, returning the solution with zero planning overhead.
- Failure: If all candidates fail, the system interprets this as a signal that the problem complexity exceeds the generator's direct reasoning capability. Only then is a powerful Planner model ( $M_P$ ) invoked.
Decomposition: The planner decomposes the original problem into a set of sub-problems. These sub-problems are solved recursively using the same trial-first policy.
Composition: Once sub-problems are verified, their solutions are composed into a final program. If the composite solution fails, the planner is re-invoked with the original problem and the set of previously successful subsolutions as context.

Heterogeneous Model Configuration

To further maximize efficiency, PaT utilizes a heterogeneous model configuration:

Generator: A cost-efficient, smaller model (sLM) handles the high-volume generation attempts.
Planner: A powerful, larger model (LLM) is reserved exclusively for the infrequent planning interventions.
This division of labor leverages the intuition that while complex decomposition requires strong reasoning, the resulting sub-tasks can often be implemented proficiently by smaller models.

Technical Nuances

Test Case Generation: To handle benchmarks with sparse or missing test cases (e.g., MBPP), PaT explicitly generates test cases. To mitigate noise from generated tests, the system employs a strict success criterion (passing all tests) and a plateau rule: if the pass count does not improve over iterations, the search halts to prevent overfitting to false positives.
Prompting: Unlike PbT methods that rely on the model's subjective assessment of complexity, PaT's planning prompt includes an explicit directive triggered by the "failure" signal, ensuring the model understands the necessity of decomposition.

Key Contributions

Adaptive Policy: The introduction of PaT, which avoids unnecessary planning overhead by invoking decomposition only upon verification failure.
Heterogeneous Configuration: A strategic pairing of small generators and large planners that decouples generation and planning costs, optimizing the cost-performance trade-off.
Empirical Validation: Comprehensive evaluation across multiple model families (Qwen3, Llama-3.1, DeepSeek-Coder) and benchmarks (HumanEval, MBPP, xCodeEval) demonstrating superior efficiency.
Theoretical Analysis: Formal proofs (Theorems 1–3) establishing the conditions under which heterogeneous configurations outperform homogeneous ones and deriving the optimal cost for the generator model.

Experimental Results

The paper reports significant improvements in the cost-performance trade-off:

Performance vs. Cost: Across foundational benchmarks, PaT consistently outperforms the previous state-of-the-art PbT baseline (FunCoder) while consuming, on average, only 60% of the inference cost.
Small Model Enhancement: A small model (Qwen3-4B) guided by PaT achieves an average Pass@1 of 83.13%, comparable to a standard inference run on a model eight times larger (Qwen3-32B, 83.35%).
Heterogeneous Efficiency: In a heterogeneous setup (Qwen3-8B generator + Qwen3-32B planner), the system achieves performance within <1% of a homogeneous Qwen3-32B setup but reduces the relative inference cost to 31%.
ROI: PaT demonstrates a Compute Return on Investment (ROI) approximately 2.4× higher than FunCoder and 4.6× higher than CodeT.
Latency: Wall-clock latency analysis confirms that PaT reduces execution time significantly compared to PbT methods, with heterogeneous configurations nearly matching the latency of the small generator alone.

Significance and Claims

The authors claim that PaT establishes a new, superior cost-performance Pareto frontier for code generation. The work demonstrates that scaling test-time compute does not need to be uniform; by intelligently allocating resources based on the intrinsic difficulty of the workload, unnecessary overhead can be eliminated without sacrificing performance.

The paper argues that the rigid "Planning-before-Trial" approach is fundamentally inefficient because it ignores the distribution of task difficulty. By inverting this to "Planning-after-Trial," PaT proves that expensive planning is a high-cost resource that should be allocated reactively. Furthermore, the success of the heterogeneous configuration suggests that the most cost-effective way to enhance system capability is not simply scaling up a single model, but strategically reserving powerful models for critical, rare tasks (planning) while relying on efficient models for high-volume tasks (generation).