Adaptive Prompt Structure Factorization: A Framework for Self-Discovering and Optimizing Compositional Prompt Programs

Haoyue Liu; Zhichao Wang; Yongxin Guo; Haoran Shou; Xiaoying Tang

cs.CLApr 8, 2026

Adaptive Prompt Structure Factorization: A Framework for Self-Discovering and Optimizing Compositional Prompt Programs

Authors: Haoyue Liu, Zhichao Wang, Yongxin Guo, Haoran Shou, Xiaoying Tang

Organizations: The Chinese University of Hong Kong, Shenzhen · Taobao and Tmall Group

Abstract

Automated prompt optimization is crucial for eliciting reliable reasoning from large language models (LLMs), yet most API-only prompt optimizers iteratively edit monolithic prompts, coupling components and obscuring credit assignment, limiting controllability, and wasting tokens. We propose Adaptive Prompt Structure Factorization (aPSF), an API-only framework (prompt-in/text-out; no access to model internals) that uses an Architect model to discover task-specific prompt structures as semantic factors. aPSF then performs interventional, single-factor updates: interventional factor-level scoring estimates each factor's marginal contribution via validation-performance changes, and error-guided factor selection routes updates to the current dominant failure source for more sample-efficient optimization. Across multiple advanced reasoning benchmarks, aPSF outperforms strong baselines including principle-aware optimizers, improving accuracy by up to +2.16 percentage points on average, and reduces optimization cost by 45--87% tokens on MultiArith while reaching peak validation in 1 step.

Figures & tables

Figure 1: Monolithic prompt optimization vs. aPSF. Top: monolithic API-only prompt optimizers iteratively edit a single prompt. Bottom: aPSF decomposes the prompt into semantic factors and updates selected factors while freezing the rest.

Figure 2: Overview of aPSF. Given a dataset of sampled examples and an optional initial prompt, aPSF proceeds in two phases. (1) Structure Discovery: the Architect LLM analyzes the task and decomposes the prompt into $K$ semantic factors $\{F_{k}\}_{k=1}^{K}$ (task-specific factorization, rather than a fixed scaffold). (2) Iterative Factor Optimization: the Worker LLM executes the composed prompt; an evaluator returns scores and representative failure cases, which are summarized into an error diagnosis (e.g., reasoning error : 15 vs 17 ). Conditioned on the diagnosis, the architect model selects a bottleneck factor for a single-factor update while freezing the remaining factors, yielding attributable, interventional prompt edits and returning the best-performing prompt within $T_{\max}$ steps.

Methods	Qwen2.5-7B-Instruct (Worker)					Llama-3.1-8B-Instruct (Worker)
Methods	GSM8K	AQUA	Multi	Hard	Avg	GSM8K	AQUA	Multi	Hard	Avg
Zero-shot CoT	86.22 $\pm$ 0.00	81.50 $\pm$ 0.00	96.46 $\pm$ 0.00	53.79 $\pm$ 0.00	79.49	82.81 $\pm$ 0.00	68.00 $\pm$ 0.00	95.21 $\pm$ 0.00	33.60 $\pm$ 0.00	69.91
Architect = Qwen3-8B
OPRO	87.63 $\pm$ 1.85	77.00 $\pm$ 3.42	98.75 $\pm$ 0.38	53.60 $\pm$ 2.91	79.25	84.95 $\pm$ 1.67	64.50 $\pm$ 4.23	96.46 $\pm$ 0.52	33.62 $\pm$ 3.58	69.88
APE	88.83 $\pm$ 0.92	81.50 $\pm$ 2.76	98.54 $\pm$ 0.61	51.70 $\pm$ 3.84	80.14	83.48 $\pm$ 2.13	66.00 $\pm$ 3.15	96.67 $\pm$ 0.73	33.05 $\pm$ 4.12	69.80
ProTeGi	88.43 $\pm$ 1.53	79.50 $\pm$ 3.89	98.54 $\pm$ 0.44	53.88 $\pm$ 2.36	80.09	81.07 $\pm$ 2.78	62.50 $\pm$ 4.51	96.46 $\pm$ 0.68	33.52 $\pm$ 3.27	68.39

Table 1: Test accuracy (%) on math reasoning benchmarks (mean

{}_{\pm\text{std}}

over 5 runs; ). Multi = MultiArith; Hard = GSM-Hard. All methods start from the same seed prompt (“Let’s think step by step”). Bold = best; underline = second best. Light blue rows highlight aPSF with gains in green .

Figure 3: Per-task accuracy on BBH benchmarks. aPSF (red) achieves dominant performance on arithmetic and symbolic reasoning tasks, such as Multistep Arithmetic (0.96) and Boolean Expressions (0.97).

Method	GSM8K	AQUA	GSM-Hard	MATH
DSPy	89.83	81.00	51.59	52.80
aPSF	90.03	82.50	54.77	56.00
$\Delta$	+0.20	+1.50	+3.18	+3.20

Table 2: Comparison with DSPy under matched settings. MATH = Competition Mathematics ( Hendrycks et al., 2021 ) .

Figure 4: Factor selection patterns and performance. ( A ) Selection rate heatmap grouped by semantic category (original names in Appendix K ). ( B ) Test accuracy and dominant factors per task (color indicates domain).

Task	aPSF	NoStructure	Gain ( $\uparrow$ )
GSM8K	90.03	89.55	+0.48
AQUA-RAT	82.50	79.50	+3.00
Date Understanding	80.00	74.00	+6.00
Web of Lies	90.50	85.30	+5.20
Movie Recommendation	60.72	58.67	+2.05
Average	80.75	77.40	+3.35

Table 3: System-level ablation. Task-specific factorization is critical for logical reasoning tasks (e.g., Date Understanding), yielding significant gains (+6.00pp) over fixed templates.

Method	GSM8K	AQUA	Average
Error-Guided	$90.03$	82.50	86.27 +1.53
Thompson	90.57	$78.00$	$84.29$
Round-robin	$90.03$	$79.00$	$84.52$
Greedy	$89.97$	$79.50$	$84.74$
Random	$89.80$	$79.50$	$84.65$

Table 4: Scheduler ablation on GSM8K and AQUA (Accuracy %). Error-Guided achieves the best average, while Thompson sampling shows higher variance across datasets.

Source	Target Dataset
Source	GSM8K	AQUA	MultiArith	GSM-Hard	MATH
MultiArith	89.76	81.50	–	52.98	52.80
GSM8K	–	82.00	99.30	54.08	51.60
GSM-Hard	89.27	80.50	99.30	–	51.00
AQUA	90.31	–	99.30	53.78	52.20
Same-task	90.03	82.50	99.30	54.77	56.00

Table 5: Cross-task transfer results. Prompts optimized on source tasks, evaluated on targets. Last row: same-task baseline. MATH = Competition Mathematics ( Hendrycks et al., 2021 ) .

Dataset	Frozen	Unfrozen	Gain ( $\uparrow$ )
AQUA-RAT	82.50	81.50	+1.00
MultiArith	99.30	97.08	+2.22
GSM-Hard	54.77	54.36	+0.41
Date Understanding	80.00	79.50	+0.50
Average	79.14	78.11	+1.03

Table 6: Frozen (single-factor) vs. unfrozen (multi-factor) updates. Freezing non-target factors yields higher accuracy by preventing credit-assignment noise from coupled edits.

Figure 5: Optimization efficiency on MultiArith. (a) Token consumption; (b) Convergence steps (lower is better).

Figure 6: Factor-level ablation on GSM-Hard. Bars show performance drop when each factor is removed.

Appendix figures & tables21 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 7 — Figure 7: Meta-prompt for From-Scratch Structure Discovery . It enforces a strict four-section output format to ensure reliable parsing of the factor structure.

Panel of Figure 8 — Figure 8: Meta-prompt for Initial-Prompt Analysis . It guides the Architect to preserve the core reasoning style of the user’s input while expanding it into a full factorized program.

Panel of Figure 9 — Figure 9: Meta-prompt for Factor-Wise Editing . It provides error analysis as reference while explicitly preventing overfitting through general-purpose constraints.

Panel of Figure 10 — Figure 10: Meta-prompt for Step 1: Open-Ended Error Diagnosis . It enables unbiased identification of root causes and failure mechanisms prior to targeted prompt optimization.

Panel of Figure 11 — Figure 11: Meta-prompt for Step 2: Factor Selection . It maps diagnosed errors to specific factors, with history-aware recommendations to encourage balanced exploration when a single factor is repeatedly selected.

BBH Sub-task	aPSF	ProTeGi	OPRO	GrIPS	APE	Zero-shot CoT
boolean_expressions	97.0	95.5	93.5	94.5	94.5	93.0
multistep_arithmetic_two	96.0	86.0	87.0	86.0	84.0	81.0
reasoning_about_colored_objects	92.0	76.0	77.0	71.0	66.0	72.0
web_of_lies	90.5	85.0	84.0	86.0	85.5	81.5
tracking_shuffled_objects_three	86.0	85.0	77.0	78.0	84.0	70.0
Average (Top-5)	92.3	85.5	83.7	83.1	82.8	79.5

Appendix

Table 7: Top-performing BBH sub-tasks. aPSF demonstrates decisive advantages on arithmetic, boolean logic, and object tracking tasks, validating the efficacy of the Format and Rationale factors.

Figure 12: Performance profile on BBH sub-tasks. aPSF (red) exhibits the steepest curve and highest plateau, indicating it most frequently achieves near-optimal performance across tasks. At

\tau{=}0.1

(within 10% of best), aPSF succeeds on 76% of tasks vs. 65% for OPRO. Empty-CoT denotes the initial prompt baseline without prompt optimization.

Category	aPSF	OPRO	GrIPS	ProTeGi	APE	Zero-shot CoT	$\Delta$ vs Best Baseline
Humanities	67.98	61.80	60.91	60.84	59.31	55.25	+6.18
Social Sciences	80.04	80.70	81.19	80.34	79.94	70.83	-1.15
STEM	76.75	77.80	77.54	77.12	75.98	66.42	-1.05
Other	80.37	78.60	78.35	79.27	77.08	68.91	+1.10
Overall Avg.	76.29	74.72	74.50	74.39	73.08	65.35	+1.57

Appendix

Table 8: MMLU accuracy (%) across four disciplinary categories. aPSF achieves best overall average (76.29%) with strongest gains on Humanities (+6.18pp) and Other (+1.10pp), though trailing in Social Sciences and STEM.

\Delta

vs Best Baseline = aPSF’s difference from the strongest non-aPSF baseline in each category ( green =aPSF wins, red =aPSF loses). Light blue highlights indicate category winners; purple row emphasizes overall average.

	aPSF	OPRO	APE	ProTeGi	GrIPS
Comp. Math	56.0	51.6	54.0	54.0	55.0
GPQA-Chem	30.2	23.8	20.6	19.1	28.6
GPQA-Phys	45.9	44.3	41.0	39.3	39.3

Appendix

Table 9: Test accuracy (%) on Competition Math and GPQA. Comp. Math = Competition Mathematics; Chem = Chemistry; Phys = Physics. aPSF achieves best on all benchmarks.

Count ( $N$ )	GSM-Hard (%)	Trend
2	52.78	Under-exploration
4	54.77	Optimal Balance
6	53.88	Diminishing Returns
8	50.80	Overfitting / Noise

Appendix

Table 10: Sensitivity to candidate count

N

on GSM-Hard. Performance peaks at

N=4

, while larger

N

degrades performance.

Benchmark	aPSF (Initial)	aPSF (Scratch)	$\Delta$
GSM-Hard	54.77	54.67	$-0.10$
AQUA-RAT	82.50	83.00	$+0.50$
MultiArith	99.30	99.30	$\pm 0.00$

Appendix

Table 11: Comparison of aPSF in Initial-Prompt mode (“Let’s think step by step”) vs. From-Scratch mode. Performance is comparable, confirming that aPSF’s gains stem from the factorization mechanism rather than the initial prompt.

Task	Test Acc (%)	Val Gain	Gen Gap	Dominant Factor	Selection Rate
Mathematical Reasoning:
GSM8K	90.03	+0.0%	0.020	Result Aggregation	50%
AQUA-RAT	82.50	+10.3%	0.035	Calculation Execution	50%
GSM-Hard	54.77	+10.3%	0.102	Problem Understanding	67%
MultiArith	99.30	+0.0%	-0.033	Problem Analysis	100%
Logical Reasoning (BBH):

Appendix

Table 12: Complete factor selection statistics across all tasks. Test Acc matches the main results using the default configuration (Qwen2.5-7B-Instruct Worker + Qwen3-8B Architect). Val Gain = validation improvement from initial to best; Gen Gap = difference between validation and test accuracy.

Figure 13: Generalization Gap vs. Factor Diversity. Visualizing the relationship between factor count and generalization gap (data from Table 12 ). Robust tasks (e.g., GSM8K, AQUA) maintain low gaps ( $<0.05$ ) with balanced factors. High gaps in complex tasks (e.g., GPQA) reflect intrinsic difficulty rather than optimization overfitting.

Task	Discovered Factor Names (Original)	Top Factor (Rate)
Mathematical Reasoning:
GSM8K	StepByStepDecomposition, ComponentAnalysis, CalculationExecution, ResultAggregation	ResultAggregation (50%)
AQUA-RAT	StepByStepReasoning, ProblemAnalysis, StepBreakdown, CalculationExecution, Verification, AnswerSelection	CalculationExecution (50%)
GSM-Hard	ProblemUnderstanding, StepByStepBreakdown, MathematicalOperations, FinalCalculation, Verification	ProblemUnderstanding (67%)
MultiArith	StepByStepApproach, ProblemAnalysis, SequentialExecution, ResultValidation	ProblemAnalysis (100%)
Logical Reasoning (BBH):

Appendix

Table 13: Original factor names autonomously discovered by aPSF. The terminology adapts to the domain (e.g., Stereochemistry in Chemistry, CalculationExecution in AQUA). Top Factor indicates the component most frequently selected by the error-guided scheduler.

Task Type	Discovered Factors	Order
Math (GSM8K)	1. StepByStepDecomposition: Decompose problem step by step 2. ComponentAnalysis: Identify key quantities 3. CalculationExecution: Perform arithmetic operations 4. ResultAggregation: Format final output	$1\to 2\to 3\to 4$
Logic (BBH)	1. ParsingStatements: Extract logical premises 2. EstablishingOrder: Deduce chronological/logical sequence 3. EvaluatingOptions: Verify consistency against premises 4. OptionVerification: Double-check constraints	$1\to 2\to 3\to 4$
QA (AQUA)	1. ProblemAnalysis: Identify question type 2. CalculationExecution: Perform systematic calculations 3. Verification: Self-validate plausibility 4. AnswerSelection: Select correct option	$1\to 2\to 3\to 4$

Appendix

Table 14: Factor structures discovered by aPSF. The factor names (e.g., ComponentAnalysis , CalculationExecution ) correspond to the domain-specific terminology cataloged in Appendix K .

Parameter	Value
Temperature	0.0 (deterministic)
Top-p (nucleus sampling)	1.0 (disabled)
Top-k	Not applied
Max output tokens	8192
Repetition penalty	1.0 (disabled)
Stop sequences	["\n\n", "---"]

Appendix

Table 15: Decoding hyperparameters for Worker model inference (

M_{W}

). These settings apply to both prompt selection on

\mathcal{D}_{\mathrm{val}}

and final test evaluation.

Dataset	Validation Slice	Test Size
GSM8K	50	1,319
AQUA-RAT	50	254
MultiArith	50	180
GSM-Hard	50	1006
BBH (per task)	50	Variable

Appendix

Table 16: Dataset splits. We use a fixed validation slice of 50 examples per task for prompt optimization. Test sets follow official benchmarks where available.

Dataset	Task Type	Reference
GSM8K	Math word problems	Cobbe et al. (2021)
AQUA-RAT	Math multiple-choice questions	Ling et al. (2017)
MultiArith	Multi-step arithmetic reasoning	Roy and Roth (2015)
GSM-Hard	Hard math with large numbers	Gao et al. (2022)
MATH	Competition mathematics	Hendrycks et al. (2021)
BBH	Diverse reasoning (17 tasks)	Suzgun et al. (2023)

Appendix

Table 17: Summary of evaluation benchmarks. All datasets are publicly available.

Prompt Length (tokens)	Accuracy (%)
362	89.62
500	83.50
653	80.55
1260	76.47

Appendix

Table 18: Impact of prompt length on Llama-3.1-8B-Instruct performance (GSM8K). Accuracy degrades significantly as prompts exceed 500 tokens.

Method	Tokens at Best Step (K)
Method	MultiArith	GSM8K	AQUA	GSM-Hard
ProTeGi	1455	2143	1896	2850
GrIPS	1640	1932	1968	2378
CriSPO	1050	1612	1644	2268
APE	824	1206	948	1445
ZERA	460	910	529	1148

Appendix

Table 19: Extended efficiency analysis across four datasets. Top: Token consumption (K) at the best validation step. Bottom: Best step number (lower = faster convergence). aPSF consistently reaches peak validation with the fewest tokens and earliest steps.

Figure 14: Step-wise optimization trajectory on BBH Date Understanding. aPSF (red) achieves the highest peak accuracy ( $>$ 71% at Step 10) and maintains a leading position by Step 30. In contrast, monolithic methods like OPRO (blue) and ProTeGi (orange) exhibit higher volatility or lower convergence ceilings. Extended-budget analysis (30 steps) for visualization only; main results use $T_{\max}=10$ . All methods use the same extended budget.

LLM Input Optimization

See all 24 papers

Reflective Prompt Tuning through Language Model Function-Calling
May 20, 2026Farima Fatahi Bayat, Moin Aminnaseri, Pouya Pezeshkpour +1LLM Self-Refinement LLM Prompting
Megagon Labs
MA-SAPO: Multi-Agent Reasoning for Score-Aware Prompt Optimization
Oct 18, 2025Juhyeon Lee, Wonduk Seo, Junseo Koh +6Automatic Prompt Optimization Multi-Agent LLMs
Peking University · Enhans · Fudan University +1
FAPO: Fully Automated Prompt Optimization of Multi-Step LLM Pipelines
Jun 17, 2026Paul Kassianik, Baturay Saglam, Huaibo Zhao +4Large Language Model-Guided Optimization LLM Agent Workflow Optimization
Foundation AI–Cisco Systems Inc. · Yale University

May 20, 2026J/K move · Enter open · S save

Reflective Prompt Tuning through Language Model Function-Calling

Farima Fatahi Bayat, Moin Aminnaseri, Pouya Pezeshkpour, Estevam Hruschka

Megagon Labs

LLM Self-Refinement LLM Prompting Automatic Prompt Optimization

Open paper AskPDF arXiv

Large language models (LLMs) have become increasingly capable of following instructions and complex reasoning, making prompting a flexible interface for adapting models without parameter updates. Yet prompt design remains labor-intensive and highly sensitive to formatting, phrasing, and instruction order, motivating automated prompt optimization methods that reduce manual effort while preserving inference-time flexibility. However, existing methods often search over prompt candidates or use fixed critique-refine pipelines driven by individual examples or small batches, limiting their ability to capture systematic error patterns and make targeted edits grounded in failure history. We propose Reflective Prompt Tuning (RPT), a framework that uses LLM function calling to simulate the iterative workflow of human prompt engineers. An LLM optimizer calls a diagnostic function that evaluates the target model over an entire optimization set, summarizes recurring failure modes, and returns a structured diagnostic report. The optimizer uses this report, together with an accumulated memory of prior reports, to revise the prompt for the next iteration. RPT further supports confidence-aware optimization by using calibration signals in diagnostic feedback and final prompt selection. Across three reasoning tasks, RPT improves over initial prompts by up to 12.9 points, remains competitive with state of the art, and improves confidence calibration. Our analyses show that RPT is especially effective on multi-hop and mathematical reasoning, producing targeted prompt revisions that align with diagnosed failure patterns and lead to gains in task performance and calibration.

Abstract

LLM Input Optimization

Explore similar work

Reflective Prompt Tuning through Language Model Function-Calling

MA-SAPO: Multi-Agent Reasoning for Score-Aware Prompt Optimization

FAPO: Fully Automated Prompt Optimization of Multi-Step LLM Pipelines