TextReg: Mitigating Prompt Distributional Overfitting via Regularized Text-Space Optimization

arXiv:2605.21318 · cs.CL, cs.AI, cs.LG · Submitted 2026-05-20 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom, and with me are Jane, Lu, senior AI researcher at Tsinghua, Meng, lead engineer at a mysterious AI startup and Lalam, the in-house Large Language Model.

Jane: Today's paper: "TextReg: Mitigating Prompt Distributional Overfitting via Regularized Text-Space Optimization".

Tom: The gist: TextReg proposes a regularization framework that controls prompt optimization by penalizing representational inefficiency, which decomposes into capacity cost from prompt length and scope narrowness from rule narrowing,

Jane: First, who's behind it and why it matters.

Paper summary: Tom: So, we’re talking about this new paper by Lucheng Fu and colleagues called TextReg: Mitigating Prompt Distributional Overfitting via Regularized Text-Space Optimization. Basically, they’re looking at why the prompts we give to AI models often end up being messy and failing when the AI sees something new.

Jane: That sounds like it tackles that annoying problem of prompt distributional overfitting, which is when the prompt gets so specific to the training data that it just doesn't work well on anything outside of it.

Tom: Exactly. The core idea here is they argue this isn't just a quirk of how we optimize prompts; they claim it reflects a failure in how the AI represents things in that discrete text space, which is what they call representational inefficiency.

Lu: From my side, I think their framing of representation efficiency is really interesting because it breaks down the problem into two concrete things: capacity cost from prompt length and scope narrowness from rule narrowing.

Meng: Capacity cost means just longer prompts eat up more of the context budget the model has, which makes it harder to find what's actually useful, right?

Jane: Right. And scope narrowness is about those specific rules accumulating that only work for a tiny slice of inputs instead of giving broad guidance, which they say is a major issue.

Tom: The paper says these two factors compound together during optimization, causing prompt distributional overfitting to happen because the capacity being used on useless stuff grows as the prompt gets longer and narrower.

Lalam: I see how that translates to my training; if a prompt is too long or too niche, it wastes valuable processing power on things that don't help generalize well.

Tom: The authors propose TextReg as a regularization framework to control this growth by adding a penalty based on this inefficiency measure.

Jane: They introduce an objective function where you try to keep the task performance high while simultaneously minimizing that inefficiency, using a trade-off parameter lambda, which controls how much you prioritize one thing over the other.

Paper summary: Lu: What’s really neat about their proposed update mechanism is that they break down each prompt change into two signals: a signal driving empirical improvement and another signal specifically designed to oppose the growth of representational inefficiency.

Meng: So instead of just letting the LLM optimize blindly, TextReg tries to guide those updates with two different kinds of feedback simultaneously.

Tom: They call this dual-evidence gradient purification, which happens at the very source, filtering the raw task gradients before they even get into the update pipeline.

Jane: This purification step seems designed to tackle both problems mentioned earlier by combining evidence from local batch examples and global rulebank recurrence evidence.

Lu: The local case evidence gives negative feedback on generalization by telling us if a specific batch is failing, and the global recurrence tracks how often rules have been used up to a certain step in the RuleBank Rt.

Meng: So if a gradient isn't strongly supported by recent examples but has enough historical use, it gets kept and rewritten into something more general.

Tom: That rewritten instruction is what they call a concise broadly applicable instruction, and if it doesn't fit that description, they reject the gradient as some kind of generalized rule or style-only thing.

Jane: Then there’s the semantic edit regularization part where they diagnose inefficiency that’s already built into the prompt and turn that diagnosis into a textual regularization gradient called greg.

Lu: This part uses a finite-difference view, looking at how the inefficiency measure changes when you make small edits to the prompt, splitting that change up cleanly into capacity channel and scope channel terms.

Meng: The capacity channel seems triggered when the prompt length exceeds a certain threshold τC, and the scope channel is more about semantic differences between versions of the prompt analyzed by a semantic diff analyzer that uses access to RuleBank Rt.

Tom: So, they’re using this diagnosis to guide the next step, which is regularized prompt update where they select an edit that fits best with both your task intent and this regularization signal.

Jane: They pick the candidate prompt pt plus one by minimizing a compatibility measure Φ between the proposed edit and that regularization gradient greg. If nothing fits well, they have a fallback to just picking the most task-faithful update.

Paper summary: Lu: The results across different reasoning benchmarks show that TextReg substantially improves out-of-distribution generalization, with accuracy gains of up to +eleven point eight percent over TextGrad and +sixteen point five percent over REVOLVE.

Meng: It’s good to see concrete numbers like those, especially since they test this on various architectures and instruction-tuning recipes, showing it’s not tied to just one setup.

Tom: The authors confirm that this robustness across different test engines shows that mitigating prompt overfitting is a property of the optimization procedure itself, not just one specific model or recipe.

Jane: It moves the focus away from just tuning the model and toward controlling how we structure the prompt optimization process to keep it efficient.

Tom: So, to wrap up this discussion on TextReg: it’s a framework that tackles prompt distributional overfitting by formalizing inefficiency as capacity cost and scope narrowness, then using dual-evidence purification and semantic edit regularization to guide updates.

Lu: The paper’s limitation they mention is around scope because it targets single-turn reasoning with well-defined behavioral rules, leaving open-ended generation and agent instructions for future work.

Meng: That makes sense; if you're only optimizing for a specific, rule-based output, the framework works really well there.

Jane: It means that if you’re building something more open-ended or an AI agent that needs to follow complex, long chains of thought, this specific mechanism might need some adjustment later on.

Tom: Overall, TextReg gives us a new way to think about prompt optimization by treating it as a representation control problem rather than just a performance tuning problem.

Lu: It suggests that we can tame the tendency for prompts to become bloated and overly specialized during iterative rewriting processes.

Meng: From an engineering standpoint, if we can automate this regularization, it should make our prompt engineering pipeline much more stable and less prone to those weird overfitting failures.

Jane: And for us listening, it means that when you use these advanced prompting techniques, you can have a better handle on what’s actually working versus what’s just noise from the training set.

Conclusion: Tom: So, TextReg is about taking those messy prompt optimizations we do and adding a way to control them by punishing inefficiency in how the prompt represents information.

Jane: It sounds like they're looking at why our prompts sometimes just start overfitting to the training data instead of learning general rules.

Lu: They call it representational inefficiency, breaking it down into two main things: how much context you’re using and how narrow your set of rules is.

Meng: So, if a prompt gets too long or too focused on tiny details, that's the problem they want to stop.

Lalam: It means we want the AI to use its brain power more efficiently instead of just filling up space with specific instructions that don't help outside the training set.

Tom: The authors propose this framework to keep performance high while actively penalizing that inefficiency using a regularization term.

Jane: They do this by splitting every prompt update into two parts: one that tries to make the task better, and another part specifically designed to fight that inefficiency.

Lu: This second part is where they use dual-evidence gradient purification, which filters out gradients based on both recent examples and how often rules have been used historically.

Meng: That sounds like a complex filtering system before the update even happens to make sure the instructions are solid.

Lalam: And then they have semantic edit regularization, which diagnoses inefficiency that’s already built into the prompt and creates a signal to fix it.

Tom: So you get this diagnostic signal, and then you use it in a final step called Regularization-Guided Prompt Update to pick the best possible next version of the prompt.

Jane: It sounds like they're trying to force the AI to keep its instructions broad and useful across different kinds of tasks.

Lu: The results show they’re actually making a real difference, showing accuracy gains up to about twelve percent over other methods on various reasoning tests.

Tom: They tested this on several different models and setups, which means it seems like this is a method that works generally across different AI systems.

Meng: It's interesting because it suggests the way we structure the prompt optimization process itself is what needs fixing, not just tweaking the model weights.

Jane: And they did flag a limitation: this specific method works really well for tasks that rely on well-defined rules, but it might not be as effective for more open-ended writing or agent instructions.

Lu: That makes sense because their focus is on controlling discrete text space optimization, which is very structured.

Tom: So TextReg gives us a new lens to look at prompt engineering: it’s about efficiency and representation control rather than just brute-force tuning.

Jane: It shifts the goal from getting a good answer to getting an answer that’s both accurate *and* efficient in how it's expressed.

Lalam: For us, this means we can build AI systems that are smarter and more robust by making sure their instructions aren't just long strings of text but actually meaningful guidance.

Lucheng Fu, Ye Yu, Yiyang Wang, Yiqiao Jin, Haibo Jin, B. Aditya Prakash†, Haohan Wang†

Georgia Institute of Technology University of Illinois Urbana-Champaign

cs.CL, cs.AI, cs.LG

Submitted: 2026-05-20

Updated: 2026-10-05

Comments: Website: https://textreg.github.io/; Code: https://github.com/luchengfu6/TextReg

Code: https://github.com/luchengfu6/TextReg

License: http://creativecommons.org/licenses/by-sa/4.0/

Importance score: 90/100

The gist: The gist: TextReg proposes a regularization framework that controls prompt optimization by penalizing representational inefficiency, which decomposes into capacity cost from prompt length and scope

Key concepts

Representational Inefficiency
This is a measure of how poorly a prompt represents the underlying task. It is calculated by combining two factors: capacity cost (how long the prompt is) and scope narrowness (how few rules are broadly useful). High inefficiency means the prompt is overfitting to specific training examples instead of learning general principles.
Dual-Evidence Gradient Purification
This stage filters raw task gradients before they update the prompt. It combines evidence from local batch data (to see what a specific case requires) and global RuleBank recurrence (to ensure rules are broadly applicable). Only gradients that are not strongly tied to one specific case and have good recurrence support are kept.
Semantic Edit Regularization
This process diagnoses existing inefficiency in the prompt by calculating how much the inefficiency measure increases when a change is made. It uses a semantic analyzer to check if proposed edits increase capacity cost or narrowness, generating a regularization signal that guides the next prompt update away from inefficient changes.

Terminology

Summary

The gist: TextReg proposes a regularization framework that controls prompt optimization by penalizing representational inefficiency, which decomposes into capacity cost from prompt length and scope narrowness from rule narrowing, thereby improving out-of-distribution generalization.

How it works

TextReg formalizes prompt distributional overfitting as a failure of representation efficiency in discrete text-space optimization (Page 2). This inefficiency is measured by the dual-factor measure, representational inefficiency, which decomposes prompt inefficiency into capacity cost and scope narrowness (Page 2). Capacity cost is defined as the consumption of the model’s context budget incurred by prompt length (Page 2), while scope narrowness describes the fraction of rules that fail to contribute broadly useful guidance (Page 3). The measure is defined as I(p) = ptok / (z capacity cost C(p) · (1 − s¯(p)) scope narrowness W(p) (Page 4). As noted in Section 1, prompts that fail to generalize exhibit two structural symptoms: they grow long, and they accumulate narrowly applicable rules (Page 2).

The framework addresses this by proposing a regularized objective: min p∈P LDtrain (p) + λ I(p), where λ ≥ 0 controls the trade-off between task performance and representational efficiency (Page 5). To instantiate this in discrete text space, TextReg decomposes each prompt update into two complementary natural-language signals: gtext(pt) = ˜gtask(pt) + greg(pt), where g˜task drives empirical improvement and greg opposes the growth of representational inefficiency I(p) = C(p)W(p) (Page 4).

Dual-Evidence Gradient Purification

This stage operates at the gradient source, filtering raw task gradients before they enter the prompt update pipeline to address both channels of representational inefficiency (Page 6). It constructs a purified task gradient g˜task by combining local batch evidence and global RuleBank recurrence evidence (Page 4). Local case evidence from the mini-batch provides negative evidence for generalization, conceptualized as a case-attribution score a(gtask, Bt) ∈ [0, 1] (Page 6). Global recurrence evidence comes from RuleBank Rt = The set of rules observed up to step t (Page 9), where mt(r) counts matches to accepted purified gradients (Page 10). A gradient is retained only when it is not strongly batch-attributable and has sufficient recurrence support, then rewritten into a concise broadly applicable instruction; otherwise, it is rejected as GENERALIZED RULE, CASE PATCH, or STYLE ONLY (Page 6).

Semantic Edit Regularization

This stage diagnoses inefficiency that has already accumulated in the prompt and converts this diagnosis into a textual regularization gradient greg (Page 7). It uses a finite-difference view of regularization where the step-wise log-change of I(p) decomposes additively into capacity channel and scope channel terms (Page 7). The capacity channel is triggered by the indicator bC(pt) = I[ρC(pt) > τC] ∈ [0, 1], taking value 1 when the threshold τC is exceeded (Page 7). The scope channel is more semantic, estimated via a semantic diff analyzer M∆ implemented by an LLM that compares pt−1 and pt with access to RuleBank Rt and the current gradient contexts Gt (Page 8).

Regularization-Guided Prompt Update

This final stage rewrites the prompt by selecting the candidate whose edit is most compatible with the regularization signal (Page 9). The update must remain faithful to task intent encoded by g˜task while avoiding edits that increase C(p) or W(p) (Page 9). TextReg selects pt+1 = arg min p′∈E(pt,g˜task) Φ(p′ − pt, greg), where Φ measures the incompatibility between the proposed edit and the regularization gradient (Page 9). If the regularization signal is incompatible with all candidates in the task-faithful set, TextReg falls back to a task-faithful update (Page 10).

Improved Out-of-Distribution Generalization

Across multiple reasoning benchmarks, TextReg substantially improves out-of-distribution (OOD) generalization, with accuracy gains of up to +11.8% over TextGrad and +16.5% over REVOLVE (Page 2). Table 1 reports cross-dataset and cross-model generalization results, where TextReg consistently achieves the best or second-best accuracy on nearly all (test engine, dataset) pairs, outperforming both TextGrad and REVOLVE in the large majority of cells (Page 8). This robustness holds across heterogeneous test engines spanning different architectures and instruction-tuning recipes, confirming that mitigating prompt overfitting is a model-agnostic property of the optimization procedure (Page 10).

The paper concludes by framing prompt distributional overfitting as a failure of representation efficiency and proposing TextReg to control its growth via Dual-Evidence Gradient Purification, Semantic Edit Regularization, and Regularization-Guided Prompt Update (Page 6). The current limitation noted is scope: TextReg targets single-turn reasoning with well-defined behavioral rules, leaving open-ended generation and agent instructions to future work (Page 6).

Improvements for AI systems

  1. Dual-Evidence Gradient Purification (Stage 1) filters raw task gradients by classifying them into GENERALIZED RULE, CASE PATCH, or STYLE ONLY to ensure only feedback supporting broad applicability is retained, thereby addressing harmful gradients that encoding rules of limited scope (inflating W(p) via narrow patches), and those introducing wording or rule restatements without behavioral value (inflating C(p) via redundant tokens).

  2. Semantic Edit Regularization (Stage 2) diagnoses prompt degradation by estimating the step-wise log-change in representational inefficiency, triggering a regularization gradient when the log-ratio exceeds its respective threshold, which is equivalent to detecting when relative length growth or rule scope has narrowed.

  3. Regularization-Guided Prompt Update (Stage 3) selects the prompt rewrite that minimizes incompatibility with the regularization signal, ensuring that while maintaining task faithfulness (the task faithful set preserves task faithfulness), the optimization avoids edits that increase capacity cost or scope narrowness, as guided by the synthesized regularization gradient greg.

Abstract

Large language models (LLMs) are highly sensitive to the prompts used to specify task objectives and behavioral constraints. Many recent prompt optimization methods iteratively rewrite prompts using LLM-generated feedback, but the resulting prompts often become longer, accumulate narrow sample-specific rules, and generalize poorly beyond the training distribution. We study this failure mode as prompt distributional overfitting and argue that it reflects a lack of representation control in discrete text-space optimization. We formalize this view through representational inefficiency, a dual-factor measure that decomposes prompt inefficiency into capacity cost and scope narrowness, attributing distributional prompt overfitting to their coupled growth during optimization. We propose TextReg, a regularization framework that realizes a soft-penalty objective through regularized textual gradients, combining Dual-Evidence Gradient Purification, Semantic Edit Regularization, and Regularization-Guided Prompt Update. Across multiple reasoning benchmarks, TextReg substantially improves out-of-distribution (OOD) generalization, with accuracy gains of up to +11.8% over TextGrad and +16.5% over REVOLVE.

Sources

Related papers