Technical Summary: TextReg

Problem: Prompt Distributional Overfitting

Large Language Models (LLMs) are highly sensitive to input prompts, which serve as the primary interface for specifying task objectives and constraints. While recent prompt optimization methods iteratively rewrite prompts using LLM-generated feedback to improve performance, they often suffer from prompt distributional overfitting. As optimization proceeds, prompts tend to become longer and accumulate narrow, sample-specific rules (e.g., exceptions for specific entities or edge cases) rather than encoding compact, general principles.

This failure mode manifests along two coupled dimensions:

1. Capacity Cost: Prompts expand in length, consuming more context budget and making it harder for models to locate relevant instructions within limited context windows.
2. Scope Narrowness: Prompts accumulate rules that reduce training loss but apply only to a narrow subset of inputs, functioning as ad hoc patches rather than reusable task principles.

Existing optimizers lack mechanisms to control either dimension, leading to prompts that perform well on training data but generalize poorly to out-of-distribution (OOD) inputs, harder task variants, or different model architectures.

Methodology: TextReg

The authors propose TextReg, a regularization framework designed to mitigate prompt distributional overfitting by controlling representational inefficiency. The framework formalizes inefficiency as a dual-factor measure:
$$I(p) = C(p) \cdot W(p)$$
Where $C(p)$ is the capacity cost (token length) and $W(p)$ is the scope narrowness (the fraction of rules with limited generalization scope). TextReg aims to minimize a regularized objective: $\min LD_{train}(p) + \lambda I(p)$.

Since prompt optimization occurs in a non-differentiable discrete text space, TextReg realizes this objective through three complementary stages that generate and apply "textual gradients":

1. Dual-Evidence Gradient Purification

This stage operates at the source of the optimization signal to filter raw task gradients before they influence the prompt. It distinguishes between broadly applicable rules and narrow, sample-specific patches using two evidence sources:

• Local Case Evidence: Analyzes whether a proposed gradient rule traces directly to idiosyncratic features of the current mini-batch (e.g., specific entities or rare edge conditions).
• Global Recurrence Evidence (RuleBank): Maintains a memory of accepted generalized rules. A gradient is retained only if it has sufficient recurrence support across optimization steps, indicating it captures general task structure rather than a one-off fix.
• Action: Gradients are classified as Generalized Rules (retained and rewritten concisely), Case Patches (rejected), or Style Only (rejected).

2. Semantic Edit Regularization (SER)

This stage diagnoses inefficiency that has already accumulated in the prompt or was introduced by the rewriting process. It estimates the change in representational inefficiency ($\Delta \log I(p)$) between the previous prompt ($p_{t-1}$) and the current prompt ($p_t$) using a finite-difference approach:

• Capacity Channel: Triggers if the relative token length growth exceeds a threshold.
• Scope Channel: Uses a semantic diff analyzer to determine if the rule composition has narrowed (added case-specific patches) or broadened.
• Action: If degradation is detected, SER synthesizes a textual regularization gradient ($g_{reg}$) instructing the model to compress the prompt, merge redundant rules, or replace narrow rules with broader principles.

3. Regularization-Guided Prompt Update

The final stage performs the prompt rewriting. It selects a new prompt candidate ($p_{t+1}$) from a set of task-faithful edits (those that implement the purified task gradient $\tilde{g}_{task}$) that is most compatible with the regularization gradient ($g_{reg}$).

• The update prioritizes task improvement but steers the selection toward edits that minimize increases in capacity cost or scope narrowness.
• If no candidate satisfies both signals, the system falls back to the task-faithful update, ensuring the regularization acts as a soft penalty rather than a hard constraint that halts optimization.

Key Contributions

1. Formalizing Representational Inefficiency: The paper defines prompt distributional overfitting as a failure of representation efficiency in discrete text-space optimization, introducing a dual-factor measure ($I(p)$) that captures the interaction between prompt length and rule specificity.
2. Regularized Text-Space Optimization: TextReg introduces a framework to realize soft-penalty objectives in text space without differentiable parameters, utilizing Dual-Evidence Gradient Purification, Semantic Edit Regularization, and Regularization-Guided Prompt Update.
3. Improved OOD Generalization: Extensive experiments demonstrate that controlling representational inefficiency significantly mitigates overfitting, leading to robust performance across datasets and model architectures.

Experimental Results

The authors evaluated TextReg on six reasoning benchmarks (Logical Deduction, Tracking Shuffled Objects, GSM8K, SVAMP, MultiArith) using four different LLM backends (Qwen2, Phi-3.5, Llama-3, Llama-3.1). Prompts were optimized on "3-object" or source tasks and tested on harder "5/7-object" variants and different arithmetic datasets.

• Performance: TextReg consistently outperformed baselines (Zero-shot CoT, TextGrad, and REVOLVE) on OOD generalization.
  • It achieved accuracy gains of up to +11.8% over TextGrad and +16.5% over REVOLVE on specific benchmarks.
  • Notably, while baseline methods often degraded OOD accuracy below the unoptimized CoT baseline (exhibiting overfitting), TextReg preserved and extended the generalization benefits of CoT.
• Ablation: Removing any of the three core components resulted in a consistent drop in performance, confirming their joint necessity.
• Resilience: TextReg maintained strong performance even when the LLMs driving specific roles (gradient purification, regularization analysis, or prompt rewriting) were downgraded to weaker models, suggesting the regularization signal is structural rather than capability-bound.

Significance and Claims

The paper claims that prompt distributional overfitting is fundamentally a failure of representation efficiency, not merely an artifact of optimization dynamics. By treating prompt optimization through the lens of regularization—specifically controlling the growth of capacity cost and scope narrowness—TextReg provides a principled mechanism to produce prompts that generalize beyond the training distribution.

The authors position this work as a methodological advancement that makes prompt behavior more predictable and easier to audit. They explicitly note current limitations: the framework targets single-turn reasoning with well-defined behavioral rules, leaving open-ended generation, multi-turn prompts, and agent instructions (where rule structures blur) for future work.