On the Limits of Prompt-Conditioned Language Models as General-Purpose Solvers David Mguni1 , Julian Ma2 , Jun Wang∗2 1 Queen Mary University London 2 University College London
arXiv:2606.23668v1 [cs.LG] 22 Jun 2026
Abstract Large Language Models (LLMs) are frequently portrayed as general-purpose solvers capable of solving arbitrary tasks. We argue that this view overlooks a fundamental constraint: language is a compressed and capacity-limited interface for conveying task information. Modelling User–System interaction as a bilevel cheap-talk game, we analyse how latent tasks are encoded into prompts and reinterpreted under alignment and safety constraints. We introduce a conceptual decomposition separating task inference from execution and derive PAC-Bayes bounds that distinguish finite-sample estimation error from irreducible structural limitations. Our first main result establishes an expressivity floor : language acts as a capacity-limited communication channel, and whenever the informational complexity of a task family exceeds the capacity of that channel, distinct tasks become unavoidably indistinguishable to the Solver, inducing a strictly positive error floor that cannot be eliminated by additional data, optimisation, or model scaling alone. We then establish an objective-misalignment floor : when alignment constraints restrict the admissible output set, the User-ideal distribution may lie outside the feasible class, inducing an irreducible distortion. Together, these results yield a formal negative conclusion: prompt-conditioned LLMs are not universal problem solvers through prompting alone, as there exist task families for which correct behaviour is provably unattainable even in the infinite-data regime. More broadly, our analysis shows the limits of prompt-based generalisation arise from information-constrained communication and alignment-constrained objectives. This suggests that interfaces beyond natural language, including multimodal observations and, external memory, may reduce the inherent LLM limitations by increasing the task-relevant information available to the System.
1
Introduction
Large language models (LLMs) have rapidly become a general interface for computation, reasoning, and decision support, and are increasingly embedded across many industries [KHM+ 23, TTE+ 23, YCRI22]. Despite the rapid pace of integration within various areas of technology, many of the core aspects that govern their behaviours and wider usages have not yet been understood [FPG+ 23, TBCG21]. This leaves a deep gap in our understanding of LLMs and their capacity to tackle applications beyond traditional settings, for example, as general purpose learners. In standard training paradigms, LLMs are trained on large, fixed corpora and evaluated under supervised or self-supervised objectives. In contrast, real-world usage is prompt-driven: Users issue ad-hoc, task-specific requests expressed through free-form natural language. To succeed as general-purpose solvers, LLM-based systems must therefore infer a User’s latent task from an indirect and potentially ambiguous prompt, and then execute that task using pre-trained problem-solving capabilities. This motivates an analytical decomposition of prompt-conditioned LLM behaviour into two conceptual components: a Prompt Interpreter, which maps User prompts into an internal representation of intent under communication and normative constraints, and a Base Solver, which executes the task conditional on this representation. This division need not be architectural and can be purely conceptual. Its utility lies in allowing us to isolate the ∗ Corresponding author 〈[email protected]〉.
1
LLM System
User
User Context Test Input
Prompt Interpreter
Internal Context Test Input
Base Solver
Output
Conceptual Breakdown
Figure 1: Conceptual Diagram informational and objective bottlenecks that arise in prompt-based interaction, without making claims about internal and physical modularity within the model (see Figure 1). Similar conceptual decompositions of LLM behaviour into separable functional roles without claiming architectural modularity appear in prior analyses of “language vs. thought” and agentic role-play views of language models (e.g., MIB+ 24, And22, SMR23) Concretely, we conceptually view prompting as a two-step channel. The User emits a natural-language context c ∼ πU (· | θ), which is then rewritten or filtered into an internal φ context ĉ ∼ πR (· | c, S) in the LLM. The Base Solver then produces y ∼ PG (· | x, ĉ). Crucially, the Base Solver never observes θ directly but only via ĉ. Operationally, the effective φ pathway is the decomposition πR ◦ πU : task information must first be expressed in text and then survive System-side rewriting. When this channel is constrained, safety-driven, or normatively biased, the Base Solver will operate on a distorted representation of true intent, leading to a quantifiable gap between User intent and System output, as formalised by the misalignment terms introduced in our analysis. In Example 1, we illustrate the impact of finite communication channel capacity. Example 2 demonstrates the impact of objective misalignment. Example 1: Clinical decision under compressed subjective reporting. Consider a clinical setting in which a patient experiences a continuous pain severity Θ ∈ [0, 1], where Θ = 0 denotes no pain and Θ = 1 denotes maximal severity. Relying on only text-based prompts from the patient, an LLM’s task is to infer the underlying physiological condition level θ in order to prescribe an appropriate intervention (e.g. dosage, imaging decision, escalation to surgery). Formally, we model the medically appropriate predictive distribution as Pθ (y | x) = N (y; θ, σ 2 ), meaning that the optimal prediction of the clinically relevant outcome y (such as required intervention intensity) is centred at the true condition θ, with variance σ 2 representing irreducible biological uncertainty. Under log-loss, performance is measured by the KL divergence between the LLM’s predictive distribution and this ideal distribution. For two Gaussian distributions with equal variance, (θ − µ)2 . DKL N (θ, σ 2 ) ∥ N (µ, σ 2 ) = 2σ 2 Therefore, the KL divergence reduces to a squared error in estimating the underlying condition θ. A positive KL value represents systematic miscalibration in clinical judgement: the predicted intervention intensity is centred at the wrong physiological state. In practice, the LLM does not observe θ directly. The patient reports pain on a standard 10-point scale: C ∈ {1, 2, . . . , 10},
C = b(Θ) := min{10, 1 + ⌊10Θ⌋}.
The reporting rule b(·) partitions [0, 1] into ten equal bins and returns the bin index. The floor function ⌊10Θ⌋ extracts the integer part of 10Θ, so all severities within an interval of width ∆ = 0.1 produce the same report. This is not dishonesty; it is structural compression of a continuous physiological variable into a coarse linguistic category. Each distinct severity level θ defines a distinct clinical task, since it induces a distinct ideal predictive distribution Pθ . However, once severity is mapped to C, all values of θ within the same bin become observationally indistinguishable. Two distinct condition–response pairs (θ1 , Pθ1 )
and
(θ2 , Pθ2 )
with θ1 ̸= θ2 but b(θ1 ) = b(θ2 ) are therefore aliased: the clinician (or LLM system) receives identical linguistic input despite the medically appropriate intervention differing. Suppose the LLM outputs a Gaussian prediction Qc (y | x) = N (y; µ(c), σ 2 ). Conditional on observing C = c, the true severity Θ is uniformly distributed over an interval of width ∆ = 0.1. The optimal prediction µ(c) is the midpoint of that interval. The residual conditional variance is Var(Θ | C = c) =
2
∆2 . 12
Substituting into the KL expression yields ∆2 1 = > 0. inf E DKL PΘ ∥ Qb(Θ) = 24σ 2 2400 σ 2
{Qc }
This shows that even with infinite patient data, perfect optimisation, and a highly capable model, the expected KL loss cannot vanish. Distinct underlying conditions that require meaningfully different interventions have been collapsed into the same linguistic category. The clinician’s predictive distribution must therefore compromise between aliased severities, inducing systematic miscalibration. The resulting error floor is neither statistical nor architectural; it arises from compressing a continuous state into a discrete language interface. Now suppose that the patient provides rich multimodal evidence W = (Ctext , Cimg ), consisting of: (i) free-form textual symptom descriptions, (ii) medical images (e.g. photographs of inflammation or rash), and possibly additional structured signals. The raw multimodal object W may contain highly informative, fine-grained information about Θ. However, modern multimodal LLM systems do not operate directly on W . Instead, they construct an internal representation Z = πR (W ), where πR denotes the model’s preprocessing and rewriting mechanism. In practice, this transformation includes vision encoders mapping images into fixed-dimensional embeddings, projection of embeddings into token sequences, context-window truncation, summarisation to satisfy length constraints, safety or policy-driven rewriting and formatting into structured textual prompts. Hence, all downstream prediction depends only on Z: Y ∼ Q(· | x, Z). The full information pathway is therefore Θ −→ W −→ Z −→ Y, which forms a Markov chain. In particular, conditional on Z, the output Y is independent of the raw multimodal evidence W and of the latent task Θ. By the Data Processing Inequality, I(Θ; Z) ≤ I(Θ; W ). Moreover, because Z is a finite-dimensional internal representation (e.g. fixed-length embeddings or bounded token sequences), its mutual information with Θ is bounded by the representational capacity of the architecture: I(Θ; Z) ≤ Bmdl , for some finite Bmdl determined by embedding dimension, context window length, tokenisation constraints, and architectural bottlenecks. Suppose now that the task family contains K distinct severity levels θ1 , . . . , θK , each inducing a distinct predictive distribution Pθj , and that the tasks are predictively separated: h i ≥ δ > 0. min Ex DKL Pθi (· | x) ∥ Pθj (· | x) i̸=j
If the representational capacity of the architecture is sufficiently constrained, then the task cannot be identified from Z with probability one. Consequently, distinct physiological states must be mapped to the same internal representation with positive probability. This induces task aliasing: θ1 ̸= θ2
but
πR (W1 ) = πR (W2 ) = Z.
Conditional on observing Z = z, the latent severity Θ remains random. The optimal prediction is therefore µ(z) = E[Θ | Z = z], and the residual conditional variance Var(Θ | Z = z) is strictly positive whenever aliasing occurs. Substituting into the Gaussian KL expression yields inf E DKL PΘ ∥ Q(· | Z) = Q
1 E[Var(Θ | Z)] > 0. 2σ 2
Hence, this example shows that even though the patient supplies rich multimodal evidence, the model must compress this evidence into a bounded internal state before acting. If the architectural capacity of this representation is insufficient to uniquely encode the underlying task, distinct clinical conditions become aliased. The resulting error floor is therefore not statistical and not due to imperfect optimisation. It arises from representational compression inside the model itself. This illustrates that even multimodal LLM systems, when constrained to finite internal representations, can exhibit irreducible task confusion induced by architectural information bottlenecks.
This abstraction also aligns with empirical LLM observations, where general problemsolving ability is primarily acquired during large-scale pre-training, while behavioural shaping are strongly influenced by subsequent fine-tuning and alignment stages. Relatively small parameter updates during SFT or RLHF can substantially alter model behaviour [ZHL+ 24, TGZ+ 23, HSW+ 22, OWJ+ 22]. Such effects can be understood as consequences of communication and objective constraints rather than changes raw model capability. Building on this construct, we further model User–System interaction using an information-
3
theoretic analogue of Bayesian cheap talk. The User privately observes the task, the System does not, and their objectives need not coincide. This perspective allows us to study alignment, information loss, and generalisation in a unified way, without appealing to equilibrium assumptions. Our analysis covers both regimes in which the Prompt Interpreter can reliably encode the latent task and where communication or objective constraints prevent faithful task transmission. We characterise when prompt-conditioned learning succeeds, and when fundamental limits persist independently of data availability. Our analysis yields two population-level impossibility results and a finite-sample generalisation guarantee. First, we prove an expressivity/identifiability floor: if the effective task information available to the Base Solver is bounded, I(Θ; Z | Θ ∈ Θ0 ) ≤ B, relative to the entropy of a task family, then task aliasing is unavoidable and the User risk admits a strictly positive asymptotic lower bound (Theorem 1). Second, we prove an objective/admissibility floor: if alignment or safety constraints restrict the System to an admissible set Psaf e (x, c), then whenever the User-ideal distribution lies outside this set on a non-negligible region, a positive KL gap persists even with perfect task inference (Theorem 2). Finally, we derive PAC–Bayes meta-learning bounds that separate vanishing estimation terms from non-vanishing structural floors when estimating population risk from sample risk (Theorems 3–5). In summary, we derive (i) a population floor—limits on achievable performance even with perfect optimisation—and (ii) analyse estimation limits—limits on how confidently we can infer population safety/performance from finite audits. Our results highlight the relevant bottleneck to be the effective task information that φ survives the full interface πR ◦ πU and conditions the Base Solver. An implicit implication is that communication channels with higher capacity, such as those of multi-modal inputs, may alleviate the limitation attributable to language-based prompt compression. Example 2 (objective misalignment): a benign clinical task with a positive KL floor. Consider a clinical risk-stratification task where the output is a calibrated probability of whether urgent escalation is needed. Let the output space be Y = {0, 1}, where Y = 1 denotes urgent escalation and Y = 0 denotes non-urgent. For a (benign) task θ and input x ∈ X , the User-ideal predictive distribution is Pθusr (· | x) = Bernoulli pθ (x) , pθ (x) := Pθusr (Y = 1 | x). Therefore, the User intends the System to output a clinically meaningful probability pθ (x) from which a clinician can select an appropriate intervention policy. Now suppose the System enforces an admissibility (safety/alignment) constraint that caps how strongly it may predict urgent escalation under certain contexts c (e.g. conservative policy mode, missing structured evidence, or a generic disclaimer regime). Let us model this as an admissible set n o Psafe (x, c) = Bernoulli(q) : q ≤ qmax (c) , qmax (c) ∈ (0, 1). The objective distortion at (θ, x, c) is the distance from the User-ideal distribution to the admissible set: ∆obj (θ, x, c) := inf DKL Pθusr (· | x) Q = inf DKL Bern(pθ (x)) Bern(q) . Q∈Psafe (x,c)
q≤qmax (c)
Since DKL (Bern(p)∥Bern(q)) is minimised at q = p when feasible, the minimiser is the closest admissible probability q ⋆ (x, c) = min{pθ (x), qmax (c)}. Therefore, whenever pθ (x) > qmax (c), ∆obj (θ, x, c) = DKL Bern(pθ (x)) Bern(qmax (c)) > 0, i.e. even a perfect optimiser within the admissible class cannot match the User-ideal predictive distribution. To see an explicit positive population floor, assume there exist constants p0 > q0 and β ∈ (0, 1] such that with probability at least β over (Θ, X, C), pΘ (X) ≥ p0
and
qmax (C) ≤ q0 .
For example: a non-negligible subset of benign but truly high-risk cases, combined with a non-negligible probability that the System enters a conservative policy regime. Then on this event, ∆obj (Θ, X, C) ≥ DKL Bern(p0 ) Bern(q0 ) > 0,
4
so that given ε := DKL Bern(p0 ) Bern(q0 ) > 0, we have that P(∆obj (Θ, X, C) ≥ ε) ≥ β. Interpretation. The task itself is benign (clinical calibration), but admissibility constraints can still force the System’s predictive distribution to be too conservative on a non-negligible set of inputs/contexts. The resulting distance-to-admissible-set ∆obj is a quantitative measure of objective misalignment: it is the irreducible KL gap between what the clinician (User) needs the model to express and what the aligned System is permitted to output.
2
Main Results
Despite extensive empirical study, the sample efficiency and generalisation limits of promptconditioned language models remain poorly characterised. While prior work has examined computational expressivity and complexity-theoretic limitations of autoregressive models [LJL+ 20, FC20], comparatively little is known about how reliably such models can infer and execute latent tasks from indirect communication. This motivates the central question of the paper: to what extent can prompt-conditioned language models reliably infer and execute a User’s latent task? From a learning-theoretic perspective, successful generalisation requires not only sufficient representational and computational capacity, but also accurate task inference from constrained, free-form prompts. This inference problem is intrinsic to prompt-based interaction and cannot be reduced to standard supervised learning. The paper makes two main claims. First, even granting a highly capable Base Solver, we show there can remain an irreducible population-level performance floor induced by upstream objective mismatch and communication limits. Second, we quantify how reliably empirical measurements predict population performance, via PAC–Bayes generalisation bounds that control the empirical–population gap. Our negative result is also consistent with the No Free Lunch perspective: without a sufficiently informative task signal (in our case, prompt communication through a constrained communication channel) to invoke the correct inductive bias for the relevant task family, no single solver can achieve uniformly low error across all tasks. In our setting, this manifests as an irreducible User-risk floor driven by limited task transmission and admissibility constraints, even when the Base Solver is assumed powerful. We establish two complementary classes of results that together characterise the limits of prompt-conditioned general-purpose learning. Population-level misalignment limits. We first derive lower bounds on the User’s population risk that hold independently of sample size and model optimisation. We show that when either (i) the System’s admissible outputs are misaligned with the User’s intended task or (ii) the prompt and interpretation mechanism has bounded information capacity, the User risk admits a strictly positive asymptotic floor (Theorems 1 and 2). These bounds formalise misalignment as a structural property of communication and admissibility constraints, rather than as an estimation or optimisation artifact. PAC-Bayes generalisation and estimation error. We then derive PAC–Bayes generalisation bounds that quantify how empirical User risk concentrates around its population counterpart as the number of observed tasks and within-task samples increases (Theorems 4 and 5). These bounds cleanly separate vanishing estimation error from non-vanishing structural error: complexity terms decay with data, while misalignment-induced floors persist. In the fully revealing case, task aliasing disappears and the communication-induced obstacle to zero-shot and few-shot adaptation is removed. Any remaining error must therefore arise from limitations of the solver itself rather than from ambiguity in task identification. Taken together, these results show that PAC–Bayes analysis does not eliminate misalignment, but instead exposes how finite-sample learning behaviour converges to fundamental communication- and objective-induced limits. In particular, we prove that any promptconditioned system with finite interpretative capacity admits task families for which correct output generation is provably unattainable, regardless of the amount of data or number of in-context examples. Beyond exposing the limitation of these systems, our results show that expanding capability in practice may require expanding and stabilising the task interface and
5
Table 1: Key concepts in latent task and data generation Concept
Symbol
Latent task and data-generating process Task (latent) θ Meta-task Pmeta (θ) distribution Support information S (N )
Task data and behavioural prompt
Sθ ∼ Ptask (· | θ)N , c ∼ πU (· | θ)
Joint observable distribution
P̄ R (dx, dy, dc) := P (dx, dy | Θ task θ) πU (dc | θ) Pmeta (dθ)
Role / LLM interpretation
Latent task or intent sampled from Pmeta . Distribution over tasks governing meta-training and evaluation across tasks. Available support information (e.g. prior interactions, system memory, or contextual metadata). For each task, data are sampled from the taskconditional law, while the User emits a prompt according to a task-dependent behavioural communication policy. Joint distribution over inputs, outputs, and contexts after marginalising over latent tasks.
not merely scaling the model or dataset size. We interpret objective misalignment through a structural analogy to cheap-talk models, where senders and receivers optimise different objectives [CS82, FR96]. Representational misalignment corresponds to information bottlenecks in the communication channel. Each induces a distinct and additive contribution to the generalisation limits of prompt-based learning. Our analysis is grounded in PAC–Bayes theory [Alq21] and meta-learning [Rez22], but departs from existing work in three key respects: we allow latent task misspecification, permit genuine objective divergence between User and System, and work with unbounded log-loss objectives. Together, these features yield a principled characterisation of when prompt-conditioned language models can generalise efficiently and when fundamental limits persist.
Preliminaries We use the following notation which is common in the PAC-Bayes literature [Rez22, Mas20] (see Table 1 and 2). We first take a brief excursion to review some key concepts in machine learning [GCM08]. These elements will serve as an important basis for our subsequent analysis. A latent task (or intent) θ ∼ Pmeta induces a task-conditional distribution over interaction records s = (x, y) ∈ X × Y, where x denotes the model input (user query or prompt plus any provided context) and y denotes the target response or completion. For a fixed θ, we observe a finite dataset SM = {(xi , yi )}M i=1 drawn i.i.d. from Ptask (· | θ); depending on the setting, SM can represent a training corpus, a benchmark or evaluation suite, or an audit trace. A system induces a conditional distribution Ph (· | x) over outputs given inputs; we call any such conditional distribution a predictor h, and we write H for an admissible family of predictors (playing the role of a hypothesis class). Using negative log-likelihood (cross-entropy) loss, the population risk under task θ is er(h; θ) := E(x,y)∼Ptask (·|θ) − log Ph (y | x) , with empirical counterpart er(h; b SM ) defined by sample averaging. This notation is standard in PAC–Bayes; below we refine Ph to be the particular system components and constraints relevant to LLM deployment, and we will distinguish between user-facing and system-facing performance criteria.
6
Table 2: Mapping between key concepts in our framework and common LLM usage Concept
Symbol
Role / LLM interpretation
User communication User prior PU (c) Π(c | θ) or πU (c | θ)
Behavioural prompting kernel PAC–Bayes User posterior User context
Q̃(c) c∈C
Reference distribution over contexts used in the User PAC–Bayes change-of-measure arguments. Task-conditional communication policy used to analyse task information and revelation. Optimisation-induced posterior over contexts used in the User PAC–Bayes bounds. External prompt or communication signal.
System components and induced prediction Prompt Interpreter R Given User-provided prompt c generates ĉ used by Base Solver; encodes how User prompts (context) are interpreted by core model. Internal Context ĉ ∼ πR (· | c, S) Context generated by R after interpreting c. Base Solver PG (y | x, ĉ) Conditional solver producing output y given input x and Internal Context ĉ; parameterised by G ∈ G and trained during unsupervised pre-training. Effective conditional distribution induced by the System-induced Pφ (y | x, c, S) = Prompt Interpreter and Base Solver given User predictive Eĉ∼πφ [PG (y | x, ĉ)] R context c and support set S. distribution System prior P0 (G) Prior over model parameters G. System posterior Q(G | S) Data-dependent System posterior over G. Objectives and misalignment User Loss Lusr System Loss Lsys
Alignment Loss (gap)
3
User objective, defined through Pψ (y | x, c). Objective the core model is optimised for (may differ from Lusr , e.g. when User task deemed unsafe). Performance penalty under misspecification / misalignment between User and Prompt Interpreter.
Lalign
Using LLMs for General-Purpose Learning
Pre-training the System. We consider a LLM where θ ∈ Θ acts as a hidden task or topic [XRLM21]. The task θ is sampled from the meta-distribution Pmeta . Let us begin with pretraining a language model PG parameterised by G ∈ G. For a given input x ∈ X , the model generates an output ŷ according to ŷ ∼ P R G (y | x) where the marginal predictive distribution given x can be written as PG (y | x) = Θ PG (y | x, θ) Pmeta (dθ) and the task-specific data distribution is s = (x, y) ∼ Ptask (· | θ), s ∈ X × Y. The objective is to minimise some loss function given some choice of inference model parameter. For now, assume the model space G is correctly specified that is, we assume there exists a G′ ∈ G which specifies the true model. The System (i.e. the language model and its procedure for performing its updates) receives a prefixed feature x and generates ŷ according to distribution ŷ ∼ softmax PG (y | x). In general, the goal of training is to infer a model parameter G′ ∈ G that minimises the error in predicting the correct output, i.e. that which enables ŷ to be accurately predicted from any given x. This reproduces the setup in standard supervised learning where given some loss function or ‘risk’ we seek to find a hypothesis among a fixed class of functions or hypothesis space that minimises the loss function. In our case, the objective of the System sys is to find a G′ such that G′ ∈ argmin Lsys Ptask (·|θ) (G), where the objective LPtask (·|θ) (G) is G∈G
described by the expected cross-entropy loss function: CE(G) := −Es∼Ptask (·|θ) [log PG (y | x)] ,
7
∀G ∈ G.
(1)
<∞ Since Ptask (· | θ) is a priori unknown, given the observations SθM := {(xi , yi )}M i=0 , we (N ) d consider the empirical loss i.e we take an average of the cross-entropy loss: CE := P N − N1 i=1 log PG (yi | xi ), si ≡ (xi , yi ) ∼ Ptask (· | θ) for any G ∈ G and any θ ∈ Θ, where the sum over i iterates through all sequences in the dataset SθM . A crucial point to note is that the System loss function is unbounded.
3.1
General Purpose Learners with Context Communication
For each latent task θ ∈ Θ, let (x, y) ∼ Ptask (· | θ) denote data drawn from the task-level data-generating distribution. We distinguish this from a meta-distribution Pmeta over tasks, which governs how tasks are sampled during training and evaluation of the User and Prompt Interpreter. We now consider observations of the data set Zθn = (zθ1 , . . . , zθN ) ∈ Z n where zθi = (xi , c) ∈ X × C ≡ Z and N is the integer number of sequences in the dataset where now the input space which previously consisted of just x ∈ X has been augmented to include a ‘context’ (User Context) c ∈ C which is the output of a map c : Θ → C where C is a set of contexts. The System receives the context c (along with a prefixed feature x) and generates ŷ according to the conditional distribution ŷ ∼ PG (y | x, ĉ), where ĉ is produced by a Prompt Interpreter from the User’s context c. Formally, the System’s predictive mechanism is the conditional distribution PG (y | x, ĉ) obtained after the Prompt Interpreter produces an Internal Context ĉ ∼ πR (· | c, S). The introduction of Prompt Interpreter requires no explicit architectural separation; this factorization is conceptual: it is an analytical device for separating intent-to-objective translation and communication constraints from task execution, not a claim that any model internally implements clean modular subcomponents. Utilizing this conceptual decomposition isolates the interpretive role from the general problem solving role and is essential to our analysis. For each task θ, only a finite dataset is available (N )
Sθ
N = {(xi , yi )}N i=1 ∼ Ptask (· | θ)
The User observes θ and produces a communication context c ∈ C according to a (possibly stochastic) policy πU (c | θ). This context is processed by the Prompt Interpreter, modelled as a stochastic rewriting mechanism (N )
φ ĉ ∼ πR (· | c, Sθ
),
parameterised by φ, yielding an internal context ĉ ∈ Cint . The Base Solver, parameterised by G, then produces predictions according to the conditional distribution y ∼ PG (· | x, ĉ). For a given internal context ĉ ∈ Cint and input x ∈ X , the Base Solver is represented by the conditional predictive distribution P G (y | x, ĉ). For a given external context c ∈ C and (N ) task-specific dataset Sθ , define the effective conditional as (N ) PG,φ (y | x, c, Sθ ) := Eĉ∼πφ (·|c,S (N ) ) PG (y | x, ĉ) (2) R
θ
which marginalises over the Prompt Interpreter’s rewriting mechanism. (N ) N Let Sθ = {(xi , yi )}N denote the support dataset. For notational i=1 ∼ Ptask (· | θ) (N ) convenience, once the support-set size N is fixed we write Sθ in place of Sθ . Throughout the remainder of the paper, Sθ therefore denotes a realised support dataset drawn from Ptask (· | θ)N . Loss Formulation. population losses as
For a task θ ∈ Θ and context c ∈ C, we define the User and System (N )
ℓsys (x, y; θ, c, G, φ) := − log PG,φ (y | x, c, Sθ
),
ℓusr (x; θ, c, Sθ ) := DKL (Pθ (· | x) ∥ PG,φ (· | x, c, Sθ )) . 8
(3) (4)
where Pθ (· | x) denotes the ideal task-conditioned predictive distribution associated with task θ, representing the User’s intended behaviour in the absence of communication or alignment constraints. Note, we distinguish between the task data distribution Ptask (x, y | θ), which governs how inputs and outputs are sampled, and the ideal task-conditioned predictive distribution Pθ (y | x), which specifies the User’s intended behaviour for task θ. The ideal task-conditioned distribution Pθ (· | x) encodes the User’s intended behaviour for task θ, which may differ from the data-generating distribution Ptask (· | θ) due to safety constraints, filtering, or other forms of misalignment. The expected task-conditional losses are Lsys (θ; c) = E(x,y)∼Ptask (·|θ) ℓsys (x, y; θ, c, G, φ) , (5) Lusr (θ; c | Sθ ) = Ex∼µθ ℓusr (x; θ, c, Sθ ) . (6) Differences between Lusr and Lsys quantify objective misalignment, while limitations of φ the admissible context space C and the rewriting mechanism πR give rise to expressivity (N ) misalignment. Given a finite dataset Sθ , the empirical System loss is 1 ) Lb(N sys (θ; c, G, φ) := − N
X
(N )
log PG,φ (yi | xi , c, Sθ
).
(7)
(N ) (xi ,yi )∈Sθ
This empirical loss is the negative log-likelihood of the effective predictive distribution PG,φ , after marginalising over the Prompt Interpreter’s rewriting randomness. The population (task) loss is (N ) Lsys (G, φ; θ, c) := E(x,y)∼Ptask (·|θ) ℓsys (G, φ; c, Sθ , x, y) . (8) For the User-risk estimator, let Sθ denote the support information available to the Prompt Interpreter, and let (N ) Tθ = {(xi , yi )}N i=1 be an independent evaluation sample drawn from the User-ideal task distribution: xi ∼ µθ ,
yi ∼ Pθ (· | xi ).
The empirical User loss is N Pθ (yi | xi ) 1 X (N ) ) Lb(N , Sθ ) = log . usr (θ; c | Tθ N i=1 PG,φ (yi | xi , c, Sθ )
(9)
Its population counterpart, conditional on the support information Sθ , is Lusr (θ; c | Sθ ) = Ex∼µθ [DKL (Pθ (· | x) ∥ PG,φ (· | x, c, Sθ ))] . Then
h i (N ) ) ET (N ) Lb(N , Sθ ) = Lusr (θ; c | Sθ ). usr (θ; c | Tθ θ
For readability, we suppress the conditioning on Sθ and write Lusr (θ; c) when the support information is fixed. (N ) (N ) Note that the dependence of Lbusr (θ; c | Tθ , Sθ ) on the context c is entirely through the (N ) System likelihood term. In particular, for a given task θ and dataset Sθ and for any c ∈ C we have that N N 1 X 1 X (N ) ) Lb(N , Sθ ) = log Pθ (yi | xi ) − log PG,φ (yi | xi , c, Sθ ). usr (θ; c | Tθ N i=1 N i=1
(10)
(N )
The first term depends only on (θ, Tθ ) and not on c. Consequently, any minimiser of the empirical User loss over contexts also maximises the empirical System likelihood: N
(N )
) arg min Lb(N usr (θ; c | Tθ c∈C
, Sθ ) ≡ arg max c∈C
9
1 X (N ) log PG,φ (yi | xi , c, Sθ ), N i=1
(11)
where the decomposition (10) follows by expanding the log-ratio in (9). The first term (N ) depends only on (θ, Sθ ) and not on c. Therefore minimising (9) over c is equivalent to maximising the second term, yielding (11). This shows that although Lusr (θ; c) is defined as a KL divergence to the task distribution Pθ (· | x), the induced empirical optimisation over contexts depends only on the System likelihood term. This permits direct PAC–Bayes generalisation bounds for the User objective while retaining a KL-based population criterion. The KL formulation in (4) serves as a population-level criterion that quantifies misalignment between the System’s induced behaviour and the User’s ideal task distribution. The loss in (3) is defined as the negative log-likelihood of the effective predictive distribution obtained after marginalising over the Prompt Interpreter. This corresponds to treating the internal context ĉ as a latent variable rather than as an observed decision. By Jensen’s inequality, this choice yields a tighter and operationally more meaningful objective than the expected negative log-likelihood of individual rewrites, and reflects the behaviour of the System as a mixture model from the perspective of the User. In practice, both losses are unbounded, so the subsequent generalisation analysis (Section 7) relies on sub-Gaussian concentration assumptions rather than bounded-loss inequalities. The role of N in the User and System losses. The role of N in the User and System losses is to index a within-task sample size used to approximate task-conditioned expectations by empirical averages. Formally, N controls how precisely quantities such as cross-entropies or KL-style risks are estimated from samples drawn under the task distribution. In particular, the empirical User risk is introduced as a statistical estimator of the population User risk; it is not meant to imply that a human user literally observes or optimizes over N samples during interaction. We only require that user-facing tasks and system-facing tasks are i.i.d. draws from the same meta-distribution, not that the same task must be replayed counter-factually for the user. Notation convention (training vs. evaluation). We use Ntrain , Mtrain , for sample sizes that index optimisation or training objectives, and Neval , Meval for sample sizes that index empirical-to-population estimation in generalisation bounds. For readability we set Ntrain = Neval = N and Mtrain = Meval = M We now lift the task-level losses to a meta-learning setting, where both the System and the User optimise distributions over hypotheses and contexts across tasks. Three distributions. Throughout the paper we distinguish three conceptually different probability laws: • Pθ (· | x): the User-ideal predictive law associated with task θ (the behaviour the user actually wants); • Ptask (· | θ): the task/environment data-generating law from which training or evaluation datasets may be sampled; (N )
• PG,φ (· | x, c, Sθ ): the predictive law induced by the User–System pair after prompting, rewriting, and inference. The User-level risks compare PG,φ against Pθ , whereas empirical estimators may be constructed from samples generated according to either Pθ or Ptask , depending on the evaluation protocol. Meta-Loss Formulation. We assume a given fixed hypothesis class H and a given context set C. We consider a three-level generative hierarchy: G ∼ P0 (G),
θ ∼ Pmeta (θ),
s = [(x, y) | θ] ∼ Ptask (s | θ),
where P0 is the meta-prior over model parameters, Pmeta is the meta-distribution over tasks, and Ptask is the task-specific data distribution. During meta-training, the System updates its prior P0 (G) to a data-dependent posterior Q(G | S) ∈ ∆G , while the User updates its prior PU (c | Θ) to a posterior over communication contexts Q̃(c | Θ) ∈ ∆C . 10
The meta-distribution Pmeta and task-level distributions Ptask (· | θ) are modelling assumptions and are not assumed to be known to the User. The distribution Q̃ denotes an optimisation-induced (PAC–Bayes) posterior over contexts that characterises the solution of a meta-risk minimisation problem under Pmeta , rather than a belief update based on explicit knowledge of these distributions. We do not assume that the User observes the same tasks used to train the System. Rather, both the User’s observed tasks and the System’s training tasks are assumed to be drawn independently from the same meta-distribution Pmeta . Let θ ∼ Pmeta denote a task drawn from the meta-distribution, and for each task let (N ) N Sθ = {(xi , yi )}N denote a finite dataset drawn i.i.d. from the task-level i=1 ∼ Ptask (· | θ) data distribution and let θ1 , . . . , θM ∼ Pmeta be M meta-training tasks observed by the User. Given a User context c ∈ C, the Prompt Interpreter produces an internal context (N ) φ ĉ ∼ πR (· | c, Sθ ) parameterised by φ, and the Base Solver with parameters G induces a conditional distribution PG (y | x, ĉ). In our formulation, the inductive bias is not encoded in the learned context ĉ alone, but in the combined restriction imposed by the context space C, the Prompt Interpreter πR , and the System hypothesis class H. The context ĉ acts as a control signal that selects among these biases, rather than defining them. We consider a Bayesian approach where the System updates its beliefs using the posterior distribution Q : X × C → ∆(G), contained in the set Q. There are some special cases to be considered. The alignment loss between the User and the System is defined as Lalign := Eθ∼Pmeta , c∼πU (·|θ) |Lsys (θ; c) − Lusr (θ; c)| , (12) which measures the expected deviation between the System’s realised behaviour and the User’s intended objective. The Prompt Interpreter does not have direct access to θ at test time and cannot select internal contexts by oracle minimisation. Instead, it is trained by minimising the System’s empirical loss averaged over tasks, contexts, and finite datasets: ) φ⋆ ∈ arg min Eθ∼Pmeta Ec∼πU (·|θ) ES (N ) ∼P (·|θ)N Lb(N (13) sys (θ; c, G, φ) . φ
θ
task
This optimisation induces a rewriting mechanism that approximates, in expectation, the best task-relevant internal context that is compatible with the System’s objective and training constraints. Since, the User is learning or selecting a communication policy across tasks, the User posterior Q̃ is an optimisation-induced distribution that reflects uncertainty over which policy induces minimal expected loss when processed through the LLM System’s interpretive mechanism. The User prior PU is a fixed reference distribution over prompting strategies that encodes architectural or linguistic inductive biases rather than epistemic beliefs. Therefore, PU and Q̃ play the roles of prior and PAC–Bayes posterior over communication strategies in the User (meta-)space, while P0 and Q are the System prior and posterior over Base Solver parameters G. The User does not update beliefs about θ, which is observed directly. Instead, the User learns or selects a distribution over communication contexts that performs well across tasks. We model this via an optimisation-induced posterior Q̃ ∈ ∆(C) obtained by minimising a meta-level risk regularised by deviation from a reference measure PU : b (M,N ) (Q̃) + 1 DKL (Q̃∥PU ) . Q̃⋆ ∈ arg min R (14) usr λM Q̃∈∆(C) The empirical losses represent aggregated experience over interactions, not explicit access to labelled task datasets. Therefore, the distribution Q̃ should be interpreted as a Gibbs or PAC–Bayes posterior over communication strategies rather than as an epistemic belief over tasks. The regularisation term DKL (Q̃∥PU ) models inertia or bias toward familiar contexts induced by repeated interaction, and is not intended as a literal cognitive computation performed by the User. The User’s empirical meta-risk is the average, over observed tasks, of the empirical User loss induced by contexts sampled from Q̃ is: M h i X ) b (M,N ) (Q̃) := 1 R Ec∼Q̃ Lb(N usr usr (θi ; c | Si ) , M i=1
11
(15)
Define the meta-risk under posteriors (Q, Q̃) as Rsys (Q, Q̃) := Eθ∼Pmeta Ec∼Q̃ EG∼Q Lsys (G, φ; θ, c) ,
(16)
) b (M,N where the empirical User meta-risk R (Q̃) is defined as the average, over observed tasks, usr of the empirical User loss induced by contexts sampled from Q̃, as given in (15). The empirical counterpart of (16) over M meta-training tasks is M X ) b (M,N ) (Q, Q̃) := 1 R Ec∼Q̃ EG∼Q Lb(N sys sys (G, φ; θi , c) . M i=1
(17)
The User population risk captures the best achievable task performance from the User’s perspective, independent of the internal objectives optimised by the System. For each task θ and context distribution Q̃ ∈ ∆(C) define the population and empirical task-level User risks: (N ) (N ) ) ) b (N Rusr (θ; Q̃) := Ec∼Q̃ Lusr (θ; c) , R ) := Ec∼Q̃ Lb(N , Sθ ) . (18) usr (θ; Q̃ | Sθ usr (θ; c | Tθ ) b (N The empirical User risk R usr is introduced solely as a statistical estimator of the population User risk Rusr , and does not represent a quantity observed or optimised by the User during interaction. It measures how closely the System’s prompt-conditioned predictive distribution approximates the User-ideal task behaviour when evaluated on N independent samples from the task distribution. Define the User meta-risk under Q̃ ∈ ∆(C) as h i Rusr (Q̃) := Eθ∼Pmeta Ec∼Q̃ Lusr (θ; c) , (19)
where Lusr (θ; c) denotes the User’s ideal task loss under context c. We can then consider the regularised objectives 1 1 ) b (M,N DKL (Q∥P0 ), Jusr (Q̃) := R (Q̃) + DKL (Q̃∥PU ), usr βM λM (20) ) b (M,N where R is the User’s empirical meta-objective used in our analysis (e.g., PAC–Bayes/regularized usr optimisation) as an empirically measurable proxy for the population User risk (defined analogously to (17) using the User loss), and β, λ > 0 are complexity parameters. The setup can be formalised as a bilevel optimisation program [CMS07]: ) b (M,N Jsys (Q; Q̃) := R (Q, Q̃) + sys
inf Jsys (Q; Q̃), s.t. Q̃∗ ∈ arg min Jusr (Q̃), Q,Q̃
(21)
Q̃∈∆(C)
so that Q̃∗ is the minimiser of a PAC–Bayes objective i.e., the risk plus a Kullback-Leibler divergence regulariser.
4
Cheap-Talk Analogy and Alignment Loss
The interaction between the User and the Prompt Interpreter can be interpreted through the lens of cheap-talk models [CS82, FR96], which we use as an analytical analogy rather than as a fully specified equilibrium game. In this perspective, the User observes a latent task θ ∈ Θ and communicates via a costless, non-binding message c ∈ C, while the Prompt Interpreter maps this message to an internal context ĉ ∼ πR (· | c, S) that conditions the downstream Base Solver. Because the message c is non-binding, the Prompt Interpreter may reinterpret or transform it in a way that does not faithfully preserve the User’s intent. Objective misalignment captures the case in which the User’s ideal predictive distribution differs from the System’s, reflecting an analogue of payoff divergence in classical cheap-talk settings, without requiring explicit equilibrium analysis. Expressivity misalignment, by contrast, is structural: it arises when the communication space C or the Prompt Interpreter’s
12
mapping lacks sufficient expressivity to encode all task-relevant distinctions. Our analysis shows that when either form of misalignment is present, a strictly positive KL separation DKL PGc ∥ PGθ > 0 is unavoidable. This separation appears as an irreducible asymptotic error term in the PAC–Bayes generalisation bounds derived in Section 7. If the Prompt Interpreter perfectly preserves task-relevant information so that PG (y | x, ĉ) = PG∗ (y | x, θ), the alignment loss vanishes. Otherwise, a positive alignment loss persists, with magnitude determined by the combined effects of objective mismatch and communication constraints. While cheap-talk equilibria provide useful intuition for these phenomena, our results do not depend on explicit best-response or equilibrium assumptions. Instead, the analogy serves to clarify how non-binding communication and misaligned objectives naturally give rise to partial revelation and persistent error in prompt-conditioned learning systems. From an information-theoretic standpoint, the alignment loss can be viewed as increasing with the information gap between the latent task θ and the effective context ĉ: reducing how much the context reveals about the task necessarily increases the expected misalignment penalty. This perspective also sheds light on alignment phenomena observed in reinforcement learning from human feedback (RLHF). In this setting, the human plays the role of a User transmitting evaluative signals, while the reward model functions as a Prompt Interpreter that interprets these signals according to its own inductive biases. When objectives diverge, the system may optimise a proxy reward rather than the true human intent. Safety training and content filtering can therefore be viewed as constraints on the Prompt Interpreter, shaping the admissible set of internal interpretations and influencing the resulting alignment loss.
5
Alignment Analysis
In this section, we identify two independent sources of irreducible asymptotic risk. Limited information or representational capacity of the prompt channel induces an expressivity floor, while admissibility or objective constraints on the System induce an objective floor. Together, these results characterise when prompt-based LLMs can generalise from limited data and when unavoidable error persists regardless of sample size. Before stating the conditions for full revelations, we first introduce some important concepts. Let Θ ∼ Pmeta and let C | Θ = θ ∼ Π(· | θ), where Π : Θ → ∆(C) is a taskconditional prompting kernel. We reserve Q̃ ∈ ∆(C) for the PAC–Bayes posterior over contexts used in Section 7. Denote the induced joint distribution by PΘ,C (dθ, dc) := Pmeta (dθ) Q̃(dc | θ), and the marginal of C by Z Pmeta (dθ) Q̃(dc | θ).
PC (dc) := Θ
The mutual information between Θ and C is defined by h i I(Θ; C) := DKL PΘ,C Pmeta ⊗ PC = Eθ∼Pmeta DKL Π(· | θ) ∥ PC .
(22)
The quantity IΠ (Θ; C) measures how statistically dependent the prompt is on the latent task under the task-conditional prompting kernel Π. Equivalently, it quantifies how much uncertainty about Θ is reduced by observing C. If IΠ (Θ; C) = 0, then prompts are independent of tasks and no task inference is possible; if IΠ (Θ; C) = H(Θ), then the prompt fully reveals the task. Intermediate values correspond to partial revelation: distinct tasks may induce overlapping prompt distributions, leading to task aliasing. The mutual information therefore captures the effective task information that survives the linguistic encoding and any rewriting or policy constraints, and it is precisely this quantity that governs whether the prompt channel can resolve the entropy of the task family. We now introduce a key concept, namely the information gap. Let A denote the admissible class of User prompting policies (e.g. those 13
induced by a KL–regularised objective). Define the information capacity of the channel class as I(Θ; C)max := sup IΠ (Θ; C), (23) Π∈A
where IΠ (Θ; C) emphasises that the joint law, and hence the mutual information, depends on the prompting kernel Π. The information gap of a particular policy Π is ∆I(Π) := I(Θ; C)max − IΠ (Θ; C).
(24)
When the User objective is regularised, optimisation restricts attention to a subset of policies with bounded information, for example A(B) := {Π ∈ A : IΠ (Θ; C) ≤ B} for some finite B. All information-theoretic lower bounds below may be interpreted as holding uniformly over such an admissible class. We distinguish the task-conditional prompting kernel Π : Θ → ∆(C), used in the information-theoretic analysis of task revelation, from the PAC–Bayes posterior Q̃ ∈ ∆(C), used in the empirical User-risk bounds. Thus C | Θ = θ ∼ Π(· | θ) in Theorem 1, whereas c ∼ Q̃ in Theorems 4–6. For a task-conditional prompting kernel Π : Θ → ∆(C), define Rusr (Π) := Eθ∼Pmeta Ec∼Π(·|θ) Lusr (θ; c) . This is distinct from the PAC–Bayes User risk Rusr (Q̃), where Q̃ ∈ ∆(C) is a task-independent posterior over contexts. Fully revealing communication. We first isolate an idealised regime in which the User’s context can disambiguate the latent task for the Prompt Interpreter, so that the System’s behaviour can be conditioned on θ without distortion from the communication channel. In this setting, the User’s context c allows the Prompt Interpreter to fully reveal the true underlying task θ to the Base Solver. As a sufficient condition for full revelation, suppose there exists a measurable map f : Θ → C such that πU (c | θ) = δf (θ) (c) for all θ, where δθ0 : Θ → R>0 is the Dirac-delta function is a generalised function (or distribution) that R satisfies Eδθ0 (θ) [f (θ)] = δθ0 (θ)f (θ)dθ = f (θ0 ) and f is injective with measurable inverse g : C → Θ satisfying g(f (θ)) = θ. Hence, from the Prompt Interpreter’s perspective, observing c determines θ via θ = g(c). Therefore, in a fully revealing regime we can consider deterministic User policies of the form πU (c | θ) = δf (θ) (c), where f : Θ → C is injective and admits a measurable inverse. This construction ensures that the latent task θ can be uniquely recovered from the observed context c, and serves as a convenient sufficient condition for perfect task communication. We therefore adopt the following operational definition of full revelation, stated in terms of the System’s induced task inference. Determinism and injectivity are however stronger than necessary. More generally, the User–System interaction is fully revealing if the Prompt Interpreter can infer the task without ambiguity from any context that the User might emit. Formally, full revelation holds if, for every task θ and every context c in the support of the User policy, qφ (θ′ | c, S) = δθ (θ′ ) for all c ∈ supp(πU (· | θ)), (25) where qφ (· | c, S) denotes the task–inference distribution induced by the Prompt Interpreter. This definition requires only identifiability at the level of the System’s inference, and does not impose determinism, injectivity, or uniqueness of the User’s context selection. In particular, the User policy πU (· | θ) may be stochastic and may assign positive probability to multiple distinct contexts, provided that all such contexts induce the same task inference by the System. Under this condition, the Prompt Interpreter achieves perfect task identifiability, and the System’s effective predictive distribution satisfies PG,φ (y | x, c, S) = PG (y | x, θ),
14
so that the Base Solver behaves as if the latent task were directly observed. The resulting joint observable distribution over (x, y, c) can therefore be written as Z P̄ (x, y, c) = Ptask (x, y | θ) πU (c | θ) Pmeta (dθ), Θ
with the property that all contexts c in the support of πU (· | θ) induce identical taskconditioned behaviour. In this regime, conditioning on the context c is equivalent to conditioning on the task θ, and the PAC–Bayes meta-objective reduces to its standard form involving a posterior over Base Solver hypotheses alone. When the full-revelation condition fails, no admissible context can induce the correct task-conditioned predictive distribution, and a strictly positive irreducible error persists even in the asymptotic regime. The definition (25) isolates when the task is identifiable from what the System actually uses. To separate distinct failure modes, we now decompose “reliable prompt-based task inference” into four orthogonal conditions. Condition 1 (Objective alignment). For all tasks θ ∈ Θ and inputs x, the User-ideal and System-ideal predictive distributions coincide: Pθusr (· | x) = Pθsys (· | x). Condition 2 (Task representability). There exists a measurable mapping c : Θ → C such sys sys that for all θ ∈ Θ, DKL Pθsys Pc(θ) = 0, where Pc(θ) denotes the predictive distribution induced by the prompt c(θ) (including any rewriting). Condition 3 (Task identifiability). There exists a User policy Q̃⋆ such that, with C | Θ = θ ∼ Q̃⋆ (· | θ), IQ̃⋆ (Θ; C) = H(Θ), assuming H(Θ) < ∞. Equivalently, Θ is a measurable function of C almost surely. Condition 4 (Information preservation under rewriting). Let Z denote the effective representation available to the Base Solver after User prompting and System-side rewriting. Full information preservation holds if I(Θ; Z) = I(Θ; C), and an information bottleneck is present whenever I(Θ; Z) < I(Θ; C). When the rewriting mechanism depends on auxiliary information S, the relevant information object is Z = (Ĉ, S) if S is available to the solver, and Z = Ĉ otherwise. All lower bounds below are stated in terms of the effective task information I(Θ; Z) rather than the raw prompt information I(Θ; C). Conditions 3 and 4 together ensure full revelation in the sense of task identifiability at the System level. Condition 2 strengthens this to predictive revelation, guaranteeing that an identifiable task can be correctly realised by the System. Condition 1 further ensures that the realised behaviour coincides with the User’s intended objective. Failure of any condition induces a corresponding irreducible population-level error floor. Together, these conditions isolate distinct failure modes in prompt-based interaction, corresponding to objective mismatch, representational limitations, information bottlenecks, and information loss due to internal processing. These conditions correspond to increasingly strong notions of revelation familiar from cheap–talk models. Relaxing any one of these conditions leads to weaker forms of revelation and induces a corresponding irreducible error floor. We have therefore, far considered the case when the User’s hypothesis space contains the correct specification of its communication protocol and there is no objective misalignment. This setup allows the underlying task to be perfectly inferred by the System. In practice although one does not have access to the expected loss, we can readily see that minimising the expected loss is a good strategy for minimising the empirical loss. The remainder of this section studies the complementary regime in which one or more of these conditions fails, and shows that each failure induces a strictly positive population-level error floor. 15
Misaligned or Non-Informative User Context. This is case where either the Prompt Interpreter refuses to communicate the inferred intent due to misaligned objectives (for example, when the User is asking for something contrary to safety protocols) or when the User’s prompt is not fully revealing. When the User’s prompt c provides only partial information about the latent task θ, the conditional distribution πU (c | θ) is no longer a Dirac delta but a general stochastic policy. The System’s rewriting mechanism must therefore form predictions by marginalising over latent tasks consistent with c. The population risk for a fixed prompt–rewriting mechanism φ is Z L(φ) = ℓ(y, Pφ (· | x, c, S)) P̄ (x, y, c) dx dy dc. (26) X ×Y×C
By interchanging theR order of integration and R R collecting terms, the expected loss can be expressed as L(φ) = Θ Ptask (dθ) C πU (c | θ) X ×Y Ptask (s, y | θ) ℓ(y, Pφ (· | x, c, S)) dx dy dc. The inner two integrals define the expected loss for task θ given its observable context distribution: L(φ; θ) := Ec∼πU (·|θ) E(x,y)∼Ptask (·|θ) [ℓ(y, Pφ (· | x, c, S))] ,
(27)
L(φ) = Eθ∼Pmeta [L(φ; θ)] .
(28)
so that
Equations (26) - (28) capture the latent–task structure: the User’s context distribution πU (c | θ) only partially encodes θ, and the System’s predictive model must implicitly infer the task from the observed prompt c. In this inconsistent setting the System cannot invert the User’s prompt to recover θ, and a persistent generalisation floor appears whenever the effective communication channel πR ◦ πU is non-injective or insufficiently expressive. Let qφ (θ | c, S) denote the implicit posterior over tasks induced by the mechanism φ. The predictive distribution can then be rewritten as a task–marginal mixture: Pφ (y | x, c, S) = Eθ∼qφ (·|c,S) Eĉ∼πR (·|c,S) [PG (y | x, ĉ)] .
(29)
Under full revelation, conditioning on the effective context is equivalent to conditioning on the latent task, so the System can in principle realise task-conditioned behaviour without an information bottleneck. When full revelation fails, distinct tasks remain confounded under the induced channel, which leads to an irreducible population risk floor.
6
Population-Level Misalignment Bounds
In this section, we relax Conditions 1 - 4 and study four distinct failure modes: (i) objective misalignment between the System and the User, (ii) limited expressivity of the prompt space (so some tasks cannot be induced by any admissible prompt), (iii) insufficient task information transmitted by prompts (so tasks are not identifiable), and (iv) loss of taskrelevant information due to System-side rewriting. We establish population-level lower bounds on the User risk that arise from these mechanisms alone. These bounds are independent of finite-sample PAC–Bayes effects. Our first theorem is proven with the help of the following assumption: Assumption 1 (Task separation under shared context). There exists δ > 0 such that for all i ̸= j, 1 inf Ex DKL (Pθi (· | x) ∥ PG,φ (· | x, ĉ)) + Ex DKL (Pθj (· | x) ∥ PG,φ (· | x, ĉ)) ≥ δ, (30) (G,φ)∈H 2 uniformly in ĉ. The assumption requires that no single rewritten prompt can simultaneously solve two genuinely different tasks. This excludes degenerate task families and is the weakest condition under which communication matters. 16
Theorem 1 (Irreducible User floor under expressivity misalignment). Let Θ0 = {θ1 , . . . , θK } ⊆ Θ be a finite task packing with Pmeta (Θ0 ) = α > 0, and suppose that conditional on Θ ∈ Θ0 , the task is uniformly distributed over Θ0 . Assume that Assumption 1 holds on Θ0 , i.e. the tasks remain separated by at least δ > 0 uniformly over all effective representations ĉ available to the Base Solver. Let Z denote the effective representation after prompting and rewriting. If an admissible User–System interface Π ∈ A(B) satisfies IΠ (Θ; Z | Θ ∈ Θ0 ) ≤ B, then
B + log 2 := Yexpr . lim inf Rusr (Π) ≥ αδ 1 − N →∞ log K +
In particular, if B < log K − log 2, then the expressivity floor is strictly positive. Sketch. Fix h the separated tasks {θ1, i. . . , θK } from Assumption 1, with Pmeta (θj ) ≥ α and mini̸=j Ex KL Pθi (· | x) ∥ Pθj (· | x) ≥ δ. Step 1 (reduce risk to a task identification problem). Let Θ denote a random task supported on {θ1 , . . . , θK } and let C ∼ Π(· | Θ) be the (random) prompt/context generated under Q̃. Given (x, C), the downstream system must induce some predictive distribution P (· | x, C). By the separation condition, any single predictor cannot match all Pθj (· | x) b simultaneously: if the system effectively “uses the wrong task” on an event {Θ(C) ̸= Θ}, then it incurs at least δ expected KL mismatch on that event. Formally, one can define a decoder b : C → {1, . . . , K} (e.g. maximum-likelihood under the induced predictor family) such that Θ b Rusr (Π) ≥ α δ Pr Θ(C) ̸= Θ , where α enters because each θj has mass at least α in Pmeta on this restricted set. Step 2 (control task confusion probability by mutual information). Since IΠ (Θ; C) ≤ b B, Fano’s inequality yields a lower bound on the error probability of any decoder Θ(C): I (Θ;C)+log 2 B+log 2 Π b Pr Θ(C) ̸= Θ ≥ [1 − ]+ ≥ [1 − log K ]+ . log K Step 3 (combine and pass to N → ∞). Combining the above inequalities gives the claimed strictly positive lower bound on the population risk, and taking lim inf N →∞ removes estimation terms (the bound depends only on the interface constraint B and the task separation δ). This gives the result. In particular, if B < log K − log 2 then the bracketed term is positive, so the expressivity floor is non-vanishing. Interpretation of Theorem 1 2 The lower bound in Theorem 1 is governed by the ratio B+log log K , which compares the effective information capacity of the prompt channel to the intrinsic entropy of the task family. The quantity B upper bounds the mutual information IΠ (Θ; C) between latent tasks and prompts under the admissible class of User policies. It therefore measures how many bits about the task can survive the entire User–Interpreter pipeline after accounting for linguistic ambiguity, rewriting, safety filtering, and regularisation. Crucially, B captures effective task information, not raw context length. The denominator log K approximates the entropy of a K-task family under a near-uniform prior and represents the number of bits required to uniquely identify one task among K predictively distinguishable alternatives. The ratio therefore, quantifies the fraction of task entropy that the prompt interface can actually transmit. When B ≥ log K − log 2, the bracketed term vanishes and the information bottleneck does not force a population-level floor. However, if B < log K − log 2, the prompt channel cannot disambiguate all tasks: task aliasing occurs with strictly positive probability. In this regime the User population risk satisfies
lim inf Rusr (Q̃) ≥ Yexpr > 0, N →∞
so the learning curve exhibits an asymptotic floor. This floor reflects expressivity or identifiability misalignment: the communication space C does not contain contexts
17
π (c|θ)
that fully reveal θ, and hence DKL (PGU ∥PGθ ) > 0 on a non-negligible set of tasks. From the perspective of cheap–talk [CS82, FR96], this corresponds to partial revelation: the prompt partitions the task space into coarse equivalence classes rather than uniquely identifying the latent task. Even if the downstream solver were Bayes-optimal conditional on c, it would still incur distortion within each equivalence class. No amount of additional data can eliminate this distortion, because the ambiguity is upstream of learning. The limitation is structural, not statistical. Importantly, increasing context length does not automatically remove the floor. While longer contexts may increase the representational capacity of C, the relevant quantity in the theorem is the achievable mutual information I(Θ; C) under admissible prompting and rewriting mechanisms. If safety constraints, stylistic regularisation, or linguistic structure limit this mutual information, then B remains bounded even as raw context length grows. The critical scaling question is therefore not whether the model is larger, but whether the interface can transmit sufficient information to resolve the entropy of the task family. This clarifies why instruction-tuned or safety-aligned models can exhibit persistent performance gaps under ambiguous or over-constrained prompts. Reducing Yexpr requires increasing effective task information for example, by enriching communication protocols, improving semantic preservation in interpreter layers, or introducing interaction and feedback loops. The key insight of the result is that the User incurs an additional loss quantified by Yexpr . We now tackle the case in which we assume Condition 1 (Objective alignment) does not hold so that the System’s notion of correctness is not assumed to match the User’s intended task outcome. To prove our next result, we make the following assumption Assumption 2 (Non-emptiness of admissibility set.). For each input-context pair (x, c), there exists a non-empty set Psafe (x, c) ⊆ ∆(Y) of admissible predictive distributions. We assume that the effective System predictor is constrained to be admissible, in the sense that PG,φ (· | x, c) ∈ Psafe (x, c)
for all admissible (G, φ) ∈ H and all (x, c).
(31)
Assumption 2 formalises the idea that, for any given input and prompt, the System is restricted to a set of admissible predictive behaviours, for example due to safety, alignment, or deployment constraints. The non-emptiness condition simply ensures that these constraints are not contradictory, so that at least one valid prediction is always available. This assumption rules out degenerate settings in which the System is forced to violate its own constraints, and allows us to meaningfully characterise the irreducible error induced by admissibility restrictions rather than by infeasibility. We now present our second main result: Theorem 2 (Objective-misalignment floor for the User meta-risk). Suppose Assumption 2 holds and let Psafe (x, c) ⊆ ∆(Y) be a nonempty admissible set for each (x, c). Define the objective distortion ∆obj (θ, x, c) := inf Q∈Psafe (x,c) DKL Pθusr (· | x) Q . Then for any taskconditional User policy Π : Θ → ∆(C), Rusr (Π) ≥ Yobj := Eθ∼Pmeta Ec∼Π(·|θ) Ex∼Ptask (·|θ) ∆obj (θ, x, c) . (32) Moreover, if there exist constants ε > 0 and β ∈ (0, 1] such that P(∆obj (Θ, X, C) ≥ ε) ≥ β,
(33)
where Θ ∼ Pmeta , X ∼ Ptask (· | Θ), and C | Θ ∼ Π(· | Θ), then Rusr (Π) ≥ β ε.
(34)
Sketch. Fix any admissible System (G, ϕ) ∈ H. By Assumption 2, for every (x, c) we have PG,ϕ (· | x, c) ∈ Psafe (x, c), hence by the definition of the distance-to-set distortion and Lemma 3, DKL Pθusr (· | x) PG,ϕ (· | x, c) ≥ inf Q∈Psafe (x,c) DKL Pθusr (· | x) Q = 18
∆obj (θ, x, c). Taking expectations over x ∼ Ptask (· | θ), then c ∼ Q̃(· | θ), then θ ∼ Pmeta yields (32). For (34), use the tail lower bound E[∆obj ] ≥ ε Pr(∆obj ≥ ε) ≥ βε and combine with (32). Interpretation of Theorem 2 Theorem 2 isolates a second source of irreducible error that is independent of task identifiability: objective misalignment induced by admissibility constraints. The distortion term ∆obj (θ, x, c) measures the distance-to-set between the User-ideal predictive distribution and the System’s admissible class at (x, c). If, on a nonnegligible fraction of task–input–context triples, this distance is bounded below by ε, then the expected User meta-risk admits a strictly positive floor Yobj ≥ βε. Importantly, this floor persists even when the task is perfectly identified and optimisation is exact within Psafe : the limitation arises not from uncertainty, but from structural constraints on permissible outputs. Therefore, whereas Theorem 1 captures information loss in the prompt channel, Theorem 2 captures objective distortion imposed by alignment or safety policies. Eliminating this floor requires enlarging the admissible set itself, not increasing data or model capacity. The objective-misalignment floor established in Theorem 2 is conceptually distinct from the representation (or expressivity) misalignment floor derived in Theorem 1. The former arises when the User-ideal predictive distribution lies outside the admissible set enforced by the System, so that no admissible predictor can realise the User objective even with perfect task inference and unlimited data. By contrast, the representation-misalignment floor (Theorem 1) arises when the effective prompt representation carries insufficient information to disambiguate a finite set of predictively distinct tasks, even when the System objective itself is well aligned with the User. Together, these results identify two orthogonal and complementary mechanisms by which prompt-based language models can exhibit irreducible generalisation error: one driven by admissibility constraints on outputs, and the other by information constraints on tasks.
7
Generalisability Analysis
In this section, we provide PAC–Bayesian generalisation guarantees for prompt-conditioned learning, separating estimation error from structural limitations. The PAC-Bayes bounds derived in this section provide statistical guarantees on how well a prompt-based interaction can approximate the User’s intended task, separating estimation error from irreducible error due to misalignment or limited expressivity. The bounds control the gap between population risks, which capture fundamental limitations of the User–System interface, and empirical risks, which are finite-sample estimators used for analysis. The complexity terms quantify how specialised the prompting strategy and System hypotheses are relative to fixed priors, while the generalisation gap describes the extent to which empirical performance may deviate from population behaviour at finite sample sizes. Our results in this section show that even when these estimation terms vanish, structural misalignment induces a strictly positive residual error. The analysis in this section can be viewed as an extension of the hierarchical PAC-Bayes meta-learning framework of [Rez22]. The key difference is that tasks are not directly observed by the learner. Instead they must be communicated through a constrained prompt channel and subsequently interpreted through a potentially misaligned rewriting mechanism. We first derive a finite-sample PAC–Bayes bound on the User meta-risk (Section 7.1), showing that empirical performance concentrates around population risk as the number of tasks and samples grows. We then show that this convergence does not guarantee vanishing error. First, under the assumption that Conditions 1 - 4 hold, we provide a PAC-Bayes generalisation bound for which the Bayesian posterior that minimises the bound also minimises the System log-loss function in the asymptotic sample limit in probability. This distribution is
19
characterised by a Dirac-delta distribution whose probability mass is centered around c⋆ (θ) c⋆ (θ) for any θ ∈ Θ where is any distribution that satisfies DKL (PG ∥PGθ ) = 0 for any G ∈ G and for any θ ∈ Θ. To ensure the performance of training loss for the choice of G is small with high probability as the performance of per-task generalisation loss, we must bound generalisation gap averaged over the posterior distribution Q. We first define the following gap: ) (M,N ) busr ∆(M,N (Q) := Rusr (Q̃) − R (Q̃). usr
(35)
We study the expected User generalisation gap h i ) EC∼Q̃ ∆(M,N (Q) , usr which we define as the expected User gap. Our goal is to derive a bound on the expected User gap: a small gap means that the performance of the choice of communication context c on the (meta-)training set indicates a reliable measure of the User loss (in probability). In what follows, we present a bound on the gap between the User’s empirical loss and the expected loss (which is unknown), PU denotes the User prior over contexts, P0 denotes the System prior over model parameters, Q̃ is the User posterior over contexts, and Qθ is the System posterior over G conditioned on task θ.
7.1
PAC-Bayes Bounds with Alignment
We now derive our results concerning the learning theory of a general-purpose language model under conditions of full alignment. Throughout this section, the distributions Q and Q̃ denote optimisation-induced (PAC–Bayes) posteriors over hypotheses and contexts respectively, rather than epistemic belief updates. Under Conditions 1 - 4, the following PAC–Bayes bound characterises generalisation in the fully aligned, task-sufficient regime. For each task θ, we allow a task-indexed System posterior Qθ ∈ ∆(G). We begin with the following results that study our PAC-Bayes analysis in the fully revealing case. Theorem 3 (Reduction to standard PAC–Bayes meta-learning). Suppose that the prompt channel is fully revealing and the User and System objectives are aligned. Specifically, assume that I(Θ; Z) = H(Θ), so that the latent task Θ is measurable with respect to the observable context variable Z, and that for every task θ ∈ Θ, Pθusr (· | x) = Pθsys (· | x)
for all x ∈ X .
Then the GPAI framework reduces to the standard PAC–Bayes meta-learning setting e.g. [Rez22]. In particular, Yexpr = Yobj = 0, and the User meta-risk satisfies the usual PAC–Bayes meta-learning bound with an environmentlevel complexity term and a task-level complexity term. Equivalently, Theorems 4–6 collapse to the standard estimation-only PAC–Bayes meta-learning regime, with no irreducible communication or objective-misalignment floor. Theorem 4 (Task-level PAC–Bayes generalisation under unbounded loss). Under Conditions 1 - 4, given θ ∈ Θ, for any prior PU over C and any δ ∈ (0, 1), with probability at least 1 − δ (N ) over the independent evaluation sample Tθ , ! D ( Q̃∥P ) + log(C /δ) KL U Task (N ) ) b (N Rusr (θ; Q̃) ≤ R , Sθ ) + Gusr . (36) usr (θ; Q̃ | Tθ Task N simultaneously for all posteriors Q̃ ∈ ∆(C) where Gusr Task is the calibration q function from usr 2 usr Assumption 8. In particular, if FTask (a, b) = λt (a − b) , then GTask (u) = λut . 20
Sketch. We first introduce a bivariate convex function F to connect the empirical loss and expected loss and then perform a change of measure using the Donsker–Varadhan variational formula to derive a bound between the posterior and prior distributions. Then, we apply the Markov inequality to bound the expectation of F with the logarithm of the confidence parameter δ and perform an affine transformation to generate the final bound. The theorem bounds the task-level generalisation gap for the User. It controls the discrepancy between the population User risk and its empirical estimate for a fixed task θ. The gap differs from standard meta-learning PAC Bayes bounds owing to the different objectives between the User and the System. Moreover, as earlier remarked, proving this result differs from standard proof techniques due to the need to circumvent issues produced by the non-boundedness of the System loss objective. Following the development of Theorem 5, we can tighten the bound using an alternative set of concentration bounds (complete details are deferred to the Appendix). Interpretation of Theorem 4 (Aligned Generalisation Bound) Theorem 4 establishes a PAC–Bayes bound on the User’s expected generalisation gap under the condition that the communication between the User and the Prompt Interpreter is sufficiently informative for the Prompt Interpreter to infer the underlying Q̃∥PU ) task. The bound scales as DKL (N , showing that the number of samples N contribute to tighter generalisation guarantees. In this regime, the User’s empirical loss is a reliable predictor of its expected loss. In the cheap–talk analogy this corresponds to near truth–telling in which the message c reveals almost all of the private information θ to the receiver. Effective prompt design or instruction tuning increases the informativeness of P (c | θ) and therefore strengthens alignment between the User and the Prompt Interpreter. Practically, this suggests that improving prompt calibration or expanding the prompt vocabulary can reduce the generalisation gap by enhancing mutual information between c and θ, thereby achieving a regime where few examples suffice for adaptation.
7.2
Generalisation Bounds under Misalignment
In this section, we study the case in which Conditions 1 - 4 no longer hold. Throughout this section, we treat the User prompting strategy as a conditional policy Q̃ : Θ → ∆(C), writing C | Θ = θ ∼ Q̃(· | θ). For the System-side learning component, we allow a task-indexed posterior Qθ over Base Solver hypotheses (or parameters), with a fixed prior P0 ; when working with M sampled tasks {θi }M i=1 , we write Qi := Qθi . All KL terms below are assumed finite whenever they appear. The following result provides conditions when minimising the PAC-Bayes bound is an optimal strategy for obtaining Q⋆ : Lemma 1 (Pointwise optimality under cross-entropy). Let H be the admissible solver class and let Q ∈ ∆(H). Define h i CE(Q) := E(x,y)∼Ptask (·|θ) − log Eh∼Q ph (y | x, c, S) . Let h⋆ ∈ arg min E(x,y)∼Ptask (·|θ) − log ph (y | x, c, S) . h∈H
A distribution Q minimises CE(Q) if and only if no mixture over H attains strictly smaller cross-entropy than h⋆ . In this case, an optimal minimiser is the Dirac measure Q⋆ = δh⋆ . This result is an adaptation of Lemma 2 in [Mas20]. The result indicates that when the model class is misspecified, the solver that minimises expected population loss is optimal among all mixture predictors if and only if no mixture can produce a lower cross-entropy loss. In this case, the optimal posterior collapses to a single solver, justifying why irreducible
21
error floors can be characterised by pointwise solvers even though the analysis allows general posterior mixtures. The following result characterises the PAC-Bayes generalisation bound under the setting in which at least one of Condition 3 or Condition 4 fails. Theorem 5 (Meta-level PAC–Bayes bound with M tasks and N samples per task). Let PU ∈ ∆(C) be a fixed prior over contexts. Under Assumptions 7, 8, and 9, with probability at (N ) least 1 − δ over the draw of {(θi , Ti , Si )}M i=1 , for every posterior Q̃ ∈ ∆(C), ) usr b (M,N Rusr (Q̃) ≤ R (Q̃) + Gusr usr Task (Bt ) + GEnv (Be ),
where Bt =
DKL (Q̃∥PU ) + log(2M CTask /δ) , N
Be =
DKL (Q̃∥PU ) + log(2CEnv /δ) . M
usr and Gusr Task and GEnv are the calibration functions from Assumption 8. Under the quadratic specialisations usr usr FTask (a, b) = λt (a − b)2 , FEnv (a, b) = λe (a − b)2 ,
they reduce to Gusr Task (u) =
r
u , λt
Gusr Env (u) =
r
u . λe
Theorem 5 extends the task-level result to the meta-learning setting by additionally controlling the error incurred when generalising across tasks drawn from Pmeta . The bound in the theorem separates a finite-sample meta-generalisation term (vanishing with M, N ) from any irreducible error sources. Assumption 3 (Asymptotic regime and growth conditions). The User posterior satisfies DKL (Q̃∥PU ) →0 M
DKL (Q̃∥PU ) → 0, N as M, N → ∞. Hence Bt → 0 and Be → 0.
The assumption ensures that the task-level and environment-level PAC–Bayes penalty terms vanish. Under these conditions, the empirical risk converges to the population risk, while the irreducible floors derived below remain unaffected. We can now deduce the following result: Theorem 6 (Negative result for User-level general-purpose learning). Assume the hypotheses of Theorems 1 and 2 hold for the same admissible class, and define Y := max{Yexpr , Yobj }. Under the assumptions of Theorem 5, with probability at least 1 − δ, b (M,N ) (Q̃) ≥ Y − Gusr (Bt ) − Gusr (Be ). R usr Task Env Moreover, lim inf
inf
M,N →∞ Q̃∈A(B)
Rusr (Q̃) ≥ Y > 0.
Under Assumption 3, Bt , Be → 0, and hence b (M,N ) (Q̃) ≥ Y lim inf R usr
M,N →∞
with high probability.
22
Since Theorems 1 and 2 are population lower bounds, they imply lim inf
inf
M,N →∞ Q̃∈A(B)
Rusr (Q̃) ≥ Y := max{Yexpr , Yobj } > 0.
Moreover, combining this population floor with the finite-sample PAC–Bayes bound gives, with probability at least 1 − δ, ) usr b (M,N R (Q̃) ≥ Y − Gusr usr Task (Bt ) − GEnv (Be ).
Hence, under the growth conditions ensuring Bt , Be → 0, ) b (M,N lim inf R (Q̃) ≥ Y usr
M,N →∞
with high probability. Proof. By Theorems 1 and 2, Rusr (Q̃) ≥ Y . By Theorem 5, ) usr b (M,N Rusr (Q̃) ≤ R (Q̃) + Gusr usr Task (Bt ) + GEnv (Be ).
Rearranging gives the finite-sample lower bound. The asymptotic statements follow from the population floor and the growth condition Bt , Be → 0. The lower bound in Theorem 6 is a population statement: the quantities Yexpr and Yobj depend only on the task family, the admissibility constraints, and the information content of the prompt channel, and are independent of the sample sizes M and N . The asymptotic limit M, N → ∞ is invoked only to guarantee that the PAC–Bayes estimation terms vanish, so that the empirical risk cannot converge below the population-level floor. Importantly, this limit concerns evaluation or estimation sample sizes (i.e., Meval , Neval ) rather than additional training data; the population-level floors derived earlier persist even when estimation noise vanishes. Theorem 6 does not assert failure for all tasks, but rather shows that for any prompt-conditioned system with finite admissibility and information capacity, there exist task families for which no admissible prompting strategy can eliminate the population error, even with unlimited data.
8
Related Works
Learnability of Large Language Models. Closest to our work is [WLS23] who perform a PAC-based analysis of in-context learning of LLMs. Their analysis leads to a finite sample complexity analysis of the in-context learning setup of LLMs. Their results apply to an in-context learning setup in which prompts are constructed by concatenating pairs of the task’s inputs along with their labels. In this regard, our setup is more general since we consider prompts that are sampled from a prompt protocol or policy that lies within a generic User space (hypothesis class). Similar to our setup, they consider a set of latent tasks sampled from some pretraining distribution however, they consider a setup in which the pretraining data is fixed. In contrast, we consider a setting in which the learner can introduce an inductive bias into the training data set. Additionally, our results provide a generalisation bound allowing us to specify the performance error from a given finite number of samples. This provides important insights both in the finite regime case and the asymptotic case where it is revealed that the performance bound maintains an error due to possible misalignment. Indeed, an important component of our work is the consideration of the case of misspecification — that is when the User’s language hypothesis space does not allow the System to successfully infer the underlying task. This captures practical constraints faced by the User (prompt-engineer). Lastly, our work deals with a Bayesian formulation, namely PAC-Bayes theory [Alq21]. The corresponding results generalise the union-bound argument which enables handling a much broader parameter set topology including finite, infinite and continuous parameter sets.
23
PAC-Bayes Meta-Learning. The standard setup of a PAC-Bayes meta-learning framework comprises of two optimisations [Rez22]. One of these is performed by a ‘base learner’ that observes the task data and seeks to infer the model parameter that minimises the per-task expected loss (also called per-task generalisation loss). This is done for a given task hyperparameter which is pre-selected by a so-called ‘Meta-learner’. The Meta-learner performs its own optimisation over the hyper-parameter which lies in some given hypothesis class. The goal of the Meta-learner is to infer the hyper-parameter that serves as a prior for learning new and as of yet, unobserved tasks that are sampled at random from some environment distribution. In particular, the goodness of the Meta-learners choice of hyper-parameter is measured by a meta-generalisation loss which the Meta-learner seeks to minimise. The Meta-learner performs the optimisation while observing the data samples generated by a set of task sampled from some random distribution. Cheap-Talk Models. In the strategic transmissions model (commonly referred to as the Cheap Talk model), two rational decision-makers engage in a strategic interaction [FR96, CS82]. One of the agents, called the sender is endowed with private information about their objectives i.e. a parameter over their utility function. The Sender is allowed to communicate with the other agent, the Receiver by way of direct, one-way costless communication. Under this setup, a misalignment between the objectives of the agents compels the Sender to introduce noise in their communication to the receiver so as to obscure informative information about their underlying objectives. In [CS82], it is shown that the magnitude of the noise increases with the level of misalignment between the agents’ preferences and, in the extreme case of complete misalignment, i.e. when the agents’ interests are diametrically opposed (so they play a zero-sum game), the Sender does not communicate any useful information and communicates only noise or ‘babbles’ to the Receiver. The formalism we develop is based on an interaction which involves two independent ‘optimisers’ one of which, the User, communicates to another, the System, by transmitting a context communication after observing the task. This gives rise to a game in which one of the players uses a cheap-talk protocol to send messages to the other. We formalise this in Sec. 8. In our model, there exists a different notion of misalignment which arises from the fact that the User, who communicates with the System does not necessarily have access to a context communication which reveals the underlying task to the System. Theorem 1 demonstrates that the magnitude of the misalignment error decreases with greater alignment between the User and the System. This relationship has a striking similarity to the misalignment relationship in Cheap-Talk games. Relation to Non-Cooperative Games. In the previous sections, we described the formalism of the general purpose language model. At the heart of the construct are two separate optimisation process each of which is equipped with its own objective —- this immediately suggests that the formalism can be mapped to non-cooperative game. In this section, we now discuss the relationship between the above construction and non-cooperative games. The benefit of providing this insight comes from the fact that in non-cooperative game theory, the stable point solution of scenarios can be fully characterised using a concept known as an equilibrium [MCWG+ 95]. To make this connection, we first note that the above construction defines an interaction between two agents. Each agent has its own distinct objective which it seeks to maximise by an appropriate choice of its decision variable. Given these remarks, the above setup can be viewed as a non-cooperative Bayesian game in which the User performs strategic communication or ‘cheap talk’ [CS82]. An equilibrium or stable point is achieved when all agents use a strategy which delivers a payoff that cannot be improved on by unilaterally deviating from their current strategy (while the other agent’s strategy remains fixed). Therefore, , we create a cheap talk game [FR96] between the User and the System.
24
Future Work Designing or Learning Optimal System Objectives. A natural extension of our framework is to move beyond analysing misalignment under a fixed System objective and instead treat the System’s objective itself as a design variable. In our analysis, the gap between Lusr and Lsys , together with the limited expressiveness of the User’s context space, determines an irreducible component of the generalisation error. Rather than viewing Lsys as exogenously specified, one may seek to design or learn an optimal System objective that minimises this alignment gap while respecting safety constraints. Formally, this suggests introducing a parameterised family of System objectives {LG sys }G∈G , where G governs properties such as: (i) the relative weighting placed on safety or policy constraints versus user-utility terms, (ii) the degree of regularisation imposed through System priors or posteriors, and (iii) how the Prompt Interpreter interprets and rewrites user prompts (e.g. by replacing πR with a ϕ parameterised πR ). Under this parameterisation, one can define a meta-objective h i ϕ J (ϕ) = Eθ∼PΘ User utility at the cheap-talk equilibrium induced by Lϕsys , πU , πR −λ · SafetyPenalty(ϕ),
(37)
which seeks System objectives whose induced equilibria yield high user value while satisfying any required safety constraints. In the PAC–Bayesian formulation developed in this paper, the same idea may be expressed as J (ϕ) = Eθ, c Lusr (θ; c; ϕ) + terms depending on DKL (Qϕθ ∥P0ϕ ), DKL (Q̃ϕ ∥PU ), | {z } | {z } user-centric performance
generalisation and complexity control
thereby allowing the designer to jointly optimise the trade-off between user intent, Systeminduced misalignment, and the generalisation guarantees established in this work. Optimising ϕ would then yield a System objective chosen specifically to maximise alignment and generalisation performance under communication constraints. This perspective naturally aligns with the mechanism-design interpretation of our model [NR99, MT19]. Here, the System objective and the Prompt Interpreter jointly constitute a “mechanism” that maps user prompts into LLM behaviour. Mechanism design offers a principled methodology for selecting this mechanism so that the cheap-talk equilibrium has desirable properties, such as maximal information transmission, safety-aware incentive compatibility, or worst-case robustness. Exploring the design or learning of such an optimal System objective— possibly using tools from differentiable mechanism design and inverse reward modelling—is an important next step toward constructing LLM-based general purpose solvers that are not only expressive and adaptive, but also reliably aligned with user intent under communication and safety constraints. RLHF. A further extension is to incorporate reinforcement learning from human feedback (RLHF) into the cheap–talk framework. In practical LLMs, RLHF modifies behaviour through a reward model that reshapes the System’s effective objective Lϕsys , penalising outputs that are unsafe or misaligned with human preferences. Within our formulation, this reward model can be treated as an additional component of the System’s loss, thereby altering the equilibrium between User and System: adjusting Lϕsys influences how the Prompt Interpreter rewrites prompts and how much task information is ultimately transmitted through the communication channel πR ◦ πU . Integrating RLHF in this way opens the possibility of analysing how reward–model design affects both objective misalignment and expressivity misalignment, and how these interact with the PAC–Bayesian generalisation guarantees established in this work. Multi-agent extension. The analysis we performed in our paper considers a setting in which a single User communicates with a single System. This setup can be extended to multi-agent settings. In this setting, the presence of different decision-making entities leads to different optimisation objectives the implications of which were discussed in detail. In a multiagent setting, a collective of agents each use their own language model to form messages to 25
communicate with other agents. Introducing other agents into the System each in possession of their own knowledge and local information now leads to informational asymmetry between different agents. Additionally, in a multi-agent setting, there is the potential for the agents to have different intentions and objectives. In this setting, we now consider a set of agents N := {1, . . . , M } that each are equipped with their own language model. Therefore, , in this setting we need to consider a set of objectives for each agent. analogous to the single agent case, now each agent k ∈ N aims to identify an optimal context communication c∗k ∈ C k from a given task θik so that its generalisation loss is minimised. Future system design. Our results motivate an important research direction: to expand and enrich the task interface of future models such that more task families become identifiable and information bottlenecks under realistic use cases can be minimized. Potential mechanism include: structured prompting or iterative protocols that improve expressivity and multimodal or world-grounded models that expand the space of identifiable tasks
9
Conclusion
Large language models have been deployed to tackle a number of general environments ranging from practical tasks such as simulated cooking [YSC+ 23, ZYH+ 23], mathematical problemsolving [FPG+ 23, CKB+ 21, PB23], recreational games [FLW+ 23, MMY+ 23], knowledge work, legal documentation and computer programming among others [KHM+ 23, Bis23]. Nevertheless, research into their sample and computational constraints has yet to fully reveal the limits of language models as problem solvers. Recent discussions on the constraints on the problem-solving capacity of (autoregressive models) classes of language models to which the most prominent language models e.g. ChatGPT, GPT3.5 belong have helped shed light on some of the constraints facing language models in their application to decision problems. Nevertheless, we argue that characterising aspects such as sample complexity within problem classes that are known to be solvable by language models advances is a critical component for understanding the limits of the precision and efficiency of algorithms within language models and paving the way for subsequent developments. A key output of this paper is to generate a deeper understanding of such characteristics of language models in settings in which they can be deployed as universal solvers. In this paper we studied the concept of using language models as general-purpose solvers for machine learning. To develop an understanding of the feasibility of creating a general-purpose machine learning System using large language models and the limits of such a tool, we gave a rigorous analytic treatment of a structure that resembles a cheap-talk game between a User and the System. The System tries to infer the task from the User’s prompt communication. In this analysis, we addressed the pertinent question of the sample efficiency of language models as general-purpose learners using the framework of PAC-Bayes analysis, allowing us to derive sample efficiency results for a general class of language models and their input spaces. The PAC-Bayes analyses offers valuable insights into User-System alignment and context prompt optimisation. Specifically, our results provide bounds that quantify the generalisation loss across multiple tasks. To this end, the PAC-Bayes learning bounds derived in this paper serve to aid in initiating the study these important characteristics of language models from which further PAC-Bayes bounds can be derived. In this way, our results help establish new territories for further exploration of the capabilities of language models. An important component of our analysis is the study of language models as general-purpose learners when an effective communication protocol between the User and the System is absent or when there is objective misalignment. Our analysis reveals that with full alignment, zero-shot learning becomes achievable. However, when there is a greater misalignment or informational bottleneck, performance gap cannot be overcome even in the asymptotic data regime. Overall, our analysis clarifies fundamental limitations to prompt-based LLM systems as reliable general-purpose solvers: namely, when the User–System communication channel is insufficiently expressive and the System’s objective is unsuitably aligned. Beyond showing the limitations of current scaling approaches, our results are diagnostic; we identify importance of expressivity and information limitation and therefore the key role they play in enhancing model performance for future systems.
26
These results provide a principled foundation for understanding and improving human–LLM interaction through the lens of information theory, cheap-talk games, and PAC–Bayesian meta-learning.
References [Alq21] Pierre Alquier. User-friendly introduction to pac-bayes bounds. arXiv preprint arXiv:2110.11216, 2021. [And22] Jacob Andreas. Language models as agent models. arXiv:2212.01681, 2022.
arXiv preprint
[Bis23] Som Biswas. Role of chatgpt in computer programming.: Chatgpt in computer programming. Mesopotamian Journal of Computer Science, 2023:8–16, 2023. [CKB+ 21] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021. [CMS07] Benoı̂t Colson, Patrice Marcotte, and Gilles Savard. An overview of bilevel optimization. Annals of operations research, 153:235–256, 2007. [CS82] Vincent P Crawford and Joel Sobel. Strategic information transmission. Econometrica: Journal of the Econometric Society, pages 1431–1451, 1982. [FC20] Luciano Floridi and Massimo Chiriatti. Gpt-3: Its nature, scope, limits, and consequences. Minds and Machines, 30:681–694, 2020. [FLW+ 23] Xidong Feng, Yicheng Luo, Ziyan Wang, Hongrui Tang, Mengyue Yang, Kun Shao, David Mguni, Yali Du, and Jun Wang. Chessgpt: Bridging policy learning and language modeling. arXiv preprint arXiv:2306.09200, 2023. [FPG+ 23] Simon Frieder, Luca Pinchetti, Ryan-Rhys Griffiths, Tommaso Salvatori, Thomas Lukasiewicz, Philipp Christian Petersen, Alexis Chevalier, and Julius Berner. Mathematical capabilities of chatgpt. arXiv preprint arXiv:2301.13867, 2023. [FR96] Joseph Farrell and Matthew Rabin. Cheap talk. Journal of Economic perspectives, 10(3):103–118, 1996. [GCM08] Derek Greene, Pádraig Cunningham, and Rudolf Mayer. Unsupervised learning and clustering. Machine learning techniques for multimedia: Case studies on organization and retrieval, pages 51–90, 2008. [HSW+ 22] Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, Weizhu Chen, et al. Lora: Low-rank adaptation of large language models. ICLR, 1(2):3, 2022. [KHM+ 23] Jean Kaddour, Joshua Harris, Maximilian Mozes, Herbie Bradley, Roberta Raileanu, and Robert McHardy. Challenges and applications of large language models. arXiv preprint arXiv:2307.10169, 2023. [LJL+ 20] Chu-Cheng Lin, Aaron Jaech, Xin Li, Matthew R Gormley, and Jason Eisner. Limitations of autoregressive models and their alternatives. arXiv preprint arXiv:2010.11939, 2020. [Mas20] Andres Masegosa. Learning under model misspecification: Applications to variational and ensemble methods. Advances in Neural Information Processing Systems, 33:5479–5491, 2020.
27
[MCWG+ 95] Andreu Mas-Colell, Michael Dennis Whinston, Jerry R Green, et al. Microeconomic theory, volume 1. Oxford university press New York, 1995. [MIB+ 24] Kyle Mahowald, Anna A Ivanova, Idan A Blank, Nancy Kanwisher, Joshua B Tenenbaum, and Evelina Fedorenko. Dissociating language and thought in large language models. Trends in cognitive sciences, 28(6):517–540, 2024. [MMY+ 23] Weiyu Ma, Qirui Mi, Xue Yan, Yuqiao Wu, Runji Lin, Haifeng Zhang, and Jun Wang. Large language models play starcraft ii: Benchmarks and a chain of summarization approach. arXiv preprint arXiv:2312.11865, 2023. [MT19] David Mguni and Marcin Tomczak. Efficient reinforcement dynamic mechanism design. In GAIW: Games, agents and incentives workshops, at AAMAS, Montreal, Canada, 2019. [NR99] Noam Nisan and Amir Ronen. Algorithmic mechanism design. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 129–140, 1999. [OWJ+ 22] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730–27744, 2022. [PB23] Indrasen Poola and Velibor Božić. Guiding ai with human intuition for solving mathematical problems in chat gpt. Journal Homepage: http://www. ijmra. us, 11(07), 2023. [Rez22] Arezou Rezazadeh. A unified view on pac-bayes bounds for meta-learning. In International Conference on Machine Learning, pages 18576–18595. PMLR, 2022. [SMR23] Murray Shanahan, Kyle McDonell, and Laria Reynolds. Role play with large language models. Nature, 623(7987):493–498, 2023. [TBCG21] Alex Tamkin, Miles Brundage, Jack Clark, and Deep Ganguli. Understanding the capabilities, limitations, and societal impact of large language models. arXiv preprint arXiv:2102.02503, 2021. [TGZ+ 23] Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B Hashimoto. Stanford alpaca: An instruction-following llama model, 2023. [TTE+ 23] Arun James Thirunavukarasu, Darren Shu Jeng Ting, Kabilan Elangovan, Laura Gutierrez, Ting Fang Tan, and Daniel Shu Wei Ting. Large language models in medicine. Nature medicine, 29(8):1930–1940, 2023. [WLS23] Noam Wies, Yoav Levine, and Amnon Shashua. The learnability of in-context learning. arXiv preprint arXiv:2303.07895, 2023. [XRLM21] Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma. An explanation of in-context learning as implicit bayesian inference. arXiv preprint arXiv:2111.02080, 2021. [YCRI22] Ann Yuan, Andy Coenen, Emily Reif, and Daphne Ippolito. Wordcraft: story writing with large language models. In 27th International Conference on Intelligent User Interfaces, pages 841–852, 2022. [YSC+ 23] Xue Yan, Yan Song, Xinyu Cui, Filippos Christianos, Haifeng Zhang, David Henry Mguni, and Jun Wang. Ask more, know better: Reinforcelearned prompt questions for decision making with large language models. arXiv preprint arXiv:2310.18127, 2023. 28
[ZHL+ 24] Renrui Zhang, Jiaming Han, Chris Liu, Aojun Zhou, Pan Lu, Yu Qiao, Hongsheng Li, and Peng Gao. Llama-adapter: Efficient fine-tuning of large language models with zero-initialized attention. In The Twelfth International Conference on Learning Representations, 2024. [ZYH+ 23] Ceyao Zhang, Kaijie Yang, Siyi Hu, Zihao Wang, Guanghe Li, Yihang Sun, Cheng Zhang, Zhaowei Zhang, Anji Liu, Song-Chun Zhu, et al. Proagent: Building proactive cooperative ai with large language models. arXiv preprint arXiv:2308.11339, 2023.
29
A
Standing Assumptions
Our results are built under the following assumptions: Assumption 4 (System exponential-moment condition). There exists η > 0 such that for (N ) all G ∈ G and all admissible (c, θ), the random variable ℓsys (G, φ; c, Sθ , X, Y ) satisfies h i E exp η(ℓsys − E[ℓsys ]) < ∞, φ where the expectation is over (X, Y ) ∼ Ptask (· | θ) and the internal randomness of πR .
Assumption 5 (User exponential-moment condition). There exists η > 0 such that for all (N ) (N ) admissible (θ, c), the random variable Lbusr (θ; c | Tθ , Sθ ) satisfies an exponential-moment condition, that is the random variable ℓusr (x; θ, c) satisfies h i E exp η(ℓusr − E[ℓusr ]) < ∞, where the expectation is over (X, Y ) ∼ Ptask (· | θ). Assumption 6 (Finite task packing with positive mass). There exists a finite subset Θ0 = {θ1 , . . . , θK } ⊆ Θ, with K ≥ 2 and α := Pmeta (Θ0 ) > 0, such that conditional on Θ ∈ Θ0 , the index U ∈ {1, . . . , K} defined by Θ = θU is uniform. This is a standard identifiability condition. If no finite subset of tasks is distinguishable in prediction, then there is nothing to communicate and no floor should exist.
B
Preliminary results
We begin by proving a preliminary result which (by way of a straightforward extension) enlarges the Donsker–Varadhan variational formula: Lemma 2. For any probability measures Q ≪ P and any measurable function f , Eh∼Q [f (h)] ≤ DKL (Q∥P ) + log Eh∼P [exp(f (h))] . Equivalently, for any λ > 0, Eh∼Q [f (h)] ≤
1 {DKL (Q∥P ) + log Eh∼P [exp(λf (h))]} . λ
Lemma 3 (Pointwise lower bound under admissibility). Assume the effective System predictor is admissible: PG,φ (· | x, c) ∈ Psafe (x, c)
for all admissible (G, φ) ∈ H, (x, c).
(38)
Then for all (θ, x, c), DKL Pθ (· | x) ∥ PG,φ (· | x, c)
≥ ∆obj (θ, x, c).
(39)
where for each (θ, x, c), the pointwise distance of the User-ideal distribution to the admissible set ∆obj is defined by: ∆obj (θ, x, c) := inf DKL Pθ (· | x) ∥ Q . (40) Q∈Psafe (x,c)
Proof. This is immediate from the definition (40). Since PG,φ (· | x, c) ∈ Psafe (x, c), the infimum over Q ∈ Psafe (x, c) is at most the value attained at Q = PG,φ (· | x, c), yielding (39). 30
Lemma 4 (Data Processing Inequality). Let X, Y, Z be random variables on measurable spaces such that X → Y → Z forms a Markov chain, i.e. PZ|X,Y (· | x, y) = PZ|Y (· | y)
for PX,Y -a.e. (x, y).
Equivalently, the joint law factorises as PX,Y,Z = PX PY |X PZ|Y . Then the mutual information satisfies I(X; Z) ≤ I(X; Y ). Moreover, I(X; Y ) − I(X; Z) = I(X; Y | Z) ≥ 0. Lemma 5 (Fano’s Inequality). Let W be a discrete random variable taking values in a finite set W with |W| = M ≥ 2, and let Ŵ = g(Y ) be any estimator of W based on an observation Y (possibly randomised). Define the probability of error Pe := P(Ŵ ̸= W ). Then H(W | Y ) ≤ h(Pe ) + Pe log(M − 1), where h(p) := −p log p − (1 − p) log(1 − p) is the binary entropy function (with the convention 0 log 0 := 0). Consequently, I(W ; Y ) + log 2 Pe ≥ 1 − , log M and, equivalently, I(W ; Y ) ≥ log M − h(Pe ) − Pe log(M − 1). Lemma 6 (Lemma F.1. [Rez22]). Let Xi , i = 1, . . . , N be independent random variables and suppose that for a given ai ∈ R>0 we have that PXi [fi (Xi ) ≥ ai ] ≤ δi ,
(41)
where δi ∈ [0, 1], then the following holds: X X X PX1:N f (Xi ) ≤ ai ≥ 1 − δi i≥1
i≥1
(42)
i≥1
Lemma 7. Let X1 , . . . , Xm be independent random variable and let Pfm : X → R be a sub1 Gaussian function with parameter σ. Assume ∆ := E [f (X)] − k=1 g(Xi ), where for m ϵ > 0, we have P [∆ ≥ ϵ] ≤ exp
−mϵ2 2σ 2
then
h i 2 E eλm∆ ≤
1 , 1 − 2λσ 2
(43)
for λ ≤ 2σ1 2 .
C
Additional Results
Lemma 8 (Task confusion implies predictive distortion). Let Θ0 = {θ1 , . . . , θK } be a set of tasks satisfying Assumption 1. For any effective representation Z and any predictive kernel QZ (· | x) used by the Base Solver, define the decoder b Θ(Z) ∈ arg min Ex DKL Pθj (· | x) ∥ QZ (· | x) . θj ∈Θ0
Then
b E [DKL (PΘ (· | x) ∥ QZ (· | x)) | Θ ∈ Θ0 ] ≥ δ P Θ(Z) ̸= Θ Θ ∈ Θ0 . 31
Lemma 9 (User misspecification decomposition). Define the User Bayes-optimal loss for task θ as h i L⋆usr (θ) := inf Ex∼Ptask (·|θ) DKL Pθ (· | x) ∥ Pπ (· | x) , π(·|θ)
and the best-in-class loss achievable via contexts in C as L⋆usr,C (θ) := inf c∈C Lusr (θ; c). Then for any Q̃ ∈ ∆(C) and any task θ, h i Ec∼Q̃ Lusr (θ; c) = L⋆usr (θ) + Ausr (θ) + EQ̃ (θ), (44) where Ausr (θ) := L⋆usr,C (θ)−L⋆usr (θ) ≥ 0 is an approximation (misspecification) term induced by restricting communication to C, and EQ̃ (θ) := Ec∼Q̃ [Lusr (θ; c)]− L⋆usr,C (θ) ≥ 0 is suboptimality relative to the best-in-class context. Proposition 1 (Gibbs form of the PAC-optimal User posterior). Let PU ∈ ∆(C) be a reference measure and define M
rb(c) :=
1 X b(N ) (N ) L (θi ; c | Ti , Si ). M i=1 usr
Consider the regularised empirical objective Jusr (Q̃) = Ec∼Q̃ [b r(c)] +
1 DKL (Q̃∥PU ), λM
Q̃ ≪ PU .
If Z Zλ := C
exp(−λM rb(c)) PU (dc) < ∞,
then the unique minimiser is Q̃⋆ (dc) =
exp(−λM rb(c)) PU (dc). Zλ
Equivalently, ) b (M,N rb(c) = R (δc ). usr
Proposition 1 provides a principled interpretation of Q̃ as an optimisation-induced User posterior, and links the User-side bilevel programme to regularised empirical meta-risk minimisation. Proof. For any Q̃ ≪ PU , DKL (Q̃∥Q̃⋆ ) = DKL (Q̃∥PU ) + λM Ec∼Q̃ [b r(c)] + log Zλ . Rearranging, 1 1 DKL (Q̃∥Q̃⋆ ) − log Zλ . λM λM The second term is independent of Q̃, and the KL divergence is uniquely minimised at Q̃ = Q̃⋆ . Hence Q̃⋆ is the unique minimiser. Jusr (Q̃) =
The following result shows that an information bottleneck is induced from the KLregularised optimisation objective. The rewriting mechanism πR can only reduce task-relevant information via data processing. Lemma 10 (Penalisation induces an information budget). Suppose Πλ minimises 1 inf Rusr (Π) + Eθ∼Pmeta DKL (Π(· | θ)∥PU ) . λ Π:Θ→∆(C) Let C | Θ = θ ∼ Πλ (· | θ). Then I(Θ; C) ≤ Eθ DKL (Πλ (· | θ)∥PU ) =: B(λ) < ∞. Moreover, if Θ → C → Ĉ, then I(Θ; Ĉ) ≤ I(Θ; C) ≤ B(λ). 32
D
Main Proofs
D.1
Proof of Lemma 8
Proof of Lemma 8. Fix an effective representation value z. For any task θj ∈ Θ0 , define the distortion dj (z) := Ex DKL Pθj (· | x) ∥ Qz (· | x) . By definition, the decoder selects b Θ(z) ∈ arg min dj (z). θj ∈Θ0
b b Consider the event {Θ(Z) ̸= Θ}. On this event, if Θ = θi and Θ(Z) = θj with j ̸= i, then the optimality of the decoder implies dj (Z) ≤ di (Z). Hence
1 di (Z) + dj (Z) . 2 By the task-separation assumption, no single effective representation Z and predictive kernel QZ can simultaneously approximate both θi and θj below level δ. Therefore, 1 di (Z) + dj (Z) ≥ δ, 2 and consequently b di (Z) ≥ δ on the event {Θ(Z) ̸= Θ}. di (Z) ≥
Equivalently, b DKL (PΘ (· | x) ∥ QZ (· | x)) ≥ δ 1{Θ(Z) ̸= Θ}, after averaging over x. Taking expectations conditional on Θ ∈ Θ0 gives b ̸= Θ Θ ∈ Θ0 . E [DKL (PΘ (· | x) ∥ QZ (· | x)) | Θ ∈ Θ0 ] ≥ δ P Θ(Z) This proves the claim.
D.2
Proof of Lemma 10
Proof of Lemma 10. Let Θ ∼ Pmeta and C | Θ = θ ∼ Q̃λ (· | θ). Write the joint law as PΘ,C (dθ, dc) = Pmeta (dθ) Q̃λ (dc | θ), and denote the marginal of C by Z PC (dc) :=
Pmeta (dθ) Q̃λ (dc | θ).
Θ
Recall the standard identity h i I(Θ; C) = Eθ∼Pmeta DKL Q̃λ (· | θ) ∥ PC . Moreover, for any reference distribution PU ∈ ∆(C), we have the decomposition Eθ DKL Q̃λ (· | θ) ∥ PU = I(Θ; C) + DKL (PC ∥PU ),
(45)
(46)
which can be verified by expanding the KL divergences under a common (dominating) measure. Since DKL (PC ∥PU ) ≥ 0, (46) implies I(Θ; C) ≤ Eθ DKL Q̃λ (· | θ) ∥ PU . (47) Define B(λ) := Eθ DKL Q̃λ (· | θ) ∥ PU . Now since the penalised objective is finite at its minimiser; B(λ) < ∞, yielding the claimed information budget I(Θ; C) ≤ B(λ). Finally, by construction of the prompt rewriting mechanism, Θ → C → Ĉ forms a Markov chain, by Lemma 4, we find that I(Θ; Ĉ) ≤ I(Θ; C). Combining with (47) yields I(Θ; Ĉ) ≤ I(Θ; C) ≤ B(λ). 33
D.3
Proof of Theorem 1
(N ) Evaluation law. Unless otherwise stated, expectations defining Lusr and Lbusr are taken with respect to samples
xi ∼ µθ ,
yi ∼ Pθ (· | xi ),
so that the empirical User loss is an unbiased estimator of the User-level KL risk. Proof of Theorem 1. Our first step is to lower bound Rusr (Π) by expected distortion. Now, we first note that for all (θ, c), Lusr (θ; c) ≥ Eĉ∼πR (·|c,S) d(θ, ĉ) . This follows directly from the definition of d and since the realised system cannot outperform the best achievable predictor given the same information. Taking the expectation over c ∼ Q̃(· | θ) gives, for each θ, Rusr (θ; Q̃) = Ec∼Q̃(·|θ) [Lusr (θ; c)] ≥ Ec∼Q̃(·|θ) Eĉ∼πR (·|c) [d(θ, ĉ)]. We next take the expectation over θ ∼ Pmeta and use the generative structure Θ → C → Ĉ to obtain Rusr (Q̃) ≥ E d(Θ, Ĉ) . (48) Next, restrict to a finite packing Θ0 and define the index U . To this end, let Θ0 = {θ1 , . . . , θK } be as in Assumption 6, with α = Pmeta (Θ0 ). Condition on the event {Θ ∈ Θ0 } and define U ∈ {1, . . . , K} by Θ = θU . Then, by the law of total expectation, E[d(Θ, Ĉ)] ≥ P(Θ ∈ Θ0 ) E d(Θ, Ĉ) Θ ∈ Θ0 = α E d(θU , Ĉ) . (49) ˆ and denote the posterior weights Now, fix ĉ ∈ C, pi (ĉ) := P(U = i | Ĉ = ĉ),
i = 1, . . . , K. P Let i⋆ ∈ arg maxi pi (ĉ) and note that 1 − maxi pi (ĉ) = j̸=i⋆ pj (ĉ). For any fixed ĉ, let (G, φ) be arbitrary. Then K X
pi (ĉ) Ex DKL Pθi (· | x) ∥ PG,φ (· | x, ĉ)
(50)
i=1
≥
X
pj (ĉ)
j̸=i⋆
1 Ex DKL (Pθi⋆ ∥PG,φ (· | x, ĉ)) + Ex DKL (Pθj ∥PG,φ (· | x, ĉ)) , 2
(51)
since pi⋆ (ĉ) ≥ pj (ĉ) for all j ̸= i⋆ . Taking inf (G,φ)∈H on both sides and using Assumtion 1 yields K X X pi (ĉ) d(θi , ĉ) ≥ pj (ĉ) δ = δ 1 − max pi (ĉ) . (52) i
j̸=i⋆
i=1
After taking the expectation of (52) over Ĉ, the left-hand side becomes
EĈ
K X
pi (Ĉ) d(θi , Ĉ) = E d(θU , Ĉ) ,
i=1
by the tower property, and the right-hand side becomes δ EĈ 1 − max pi (Ĉ) = δ perr , i
where perr := inf P(Û ̸= U ) = EĈ 1 − max pi (Ĉ) i
Û (Ĉ)
34
is the Bayes error of classifying U from Ĉ. Therefore E d(θU , Ĉ) ≥ δ perr .
(53)
We now use the Fano inequality (Lemma 5) to upper bound perr under the information constraint. Firstly, note that I(U ; Ĉ) ≤ I(Θ; Ĉ). By Lemma 10 we have that, I(Θ; Ĉ) ≤ B, hence I(U ; Ĉ) ≤ B. We now apply Fano’s inequality for U ∈ {1, . . . , K} which gives perr ≥ 1 −
I(U ; Ĉ) + log 2 B + log 2 ≥ 1− . log K log K
(54)
To obtain the result we now substitute (54) into (53), then into (49), then into (48), to obtain B + log 2 Rusr (Q̃) ≥ E[d(Θ, Ĉ)] ≥ α E[d(θU , Ĉ)] ≥ α δ 1 − . log K Since Rusr (Q̃) ≥ 0 by definition of KL, we may write the bound with (·)+ which produces the required result. Corollary 1 (Irreducible User-level error). If the communication channel is not task-sufficient, then there exists Y > 0 such that for any admissible User strategy Q̃, lim inf Rusr (Q̃) ≥ Y. N →∞
D.4
(55)
Proof of Theorem 2
Proof of Theorem 2. By Lemma 3, for any (G, φ) ∈ H, DKL Pθ (· | x) ∥ PG,φ (· | x, c) ≥ ∆obj (θ, x, c). Take expectation over x ∼ Ptask (· | θ), then expectation over c ∼ Q̃, and finally θ ∼ Pmeta , to obtain (32). For the second statement, ∆obj (Θ, X, C) ≥ 0 almost surely, hence E[∆obj (Θ, X, C)] ≥ ε P ∆obj (Θ, X, C) ≥ ε ≥ ε β, which combined with (32) yields (34).
D.5
Proof of Theorem 3
Proof of Theorem 3. Since I(Θ; Z) = H(Θ), we have H(Θ | Z) = H(Θ) − I(Θ; Z) = 0. Hence Θ is identifiable from Z almost surely. Therefore, there exists a measurable decoder g:Z→Θ such that g(Z) = Θ
almost surely.
Therefore, the observable context contains all task-relevant information. In particular, conditioning on Z is equivalent to conditioning on the latent task Θ, up to null sets. It follows that the Prompt Interpreter need not perform any lossy inference over tasks. The System can condition its Base Solver on the recovered task g(Z), so that for each θ, PG,φ (· | x, Z) = PG (· | x, θ)
whenever g(Z) = θ.
Therefore, there is no representational or communication-induced obstruction to task recovery. Consequently, the expressivity floor vanishes: Yexpr = 0. 35
Next, by objective alignment, Pθusr (· | x) = Pθsys (· | x)
for all (θ, x).
Therefore the User-ideal predictive distribution lies inside the System-admissible predictive class. Hence the pointwise objective distortion satisfies ∆obj (θ, x, z) :=
inf Q∈Psys (x,z)
DKL (Pθusr (· | x) ∥ Q) = 0,
because Q = Pθsys (· | x) = Pθusr (· | x) is admissible. Taking expectations gives Yobj = Eθ,z,x ∆obj (θ, x, z) = 0. It remains only to identify the resulting learning problem. Since Z fully reveals Θ, the User no longer faces a communication-induced task-aliasing problem. Since the objectives are aligned, the User-ideal predictive distribution lies in the System-admissible class. Hence Yexpr = Yobj = 0. Consequently, Theorems 4–6 reduce to estimation-only PAC–Bayes bounds, with no irreducible communication or objective-misalignment floor. The resulting PAC–Bayes bound contains only the standard environment-level and tasklevel estimation terms: (M,N ) usr usr busr Rusr (Q̃) ≤ R (Q̃) + FEnv (M ) + FTask (N ).
Since Yexpr = Yobj = 0, there is no additional asymptotic floor. Therefore, the GPAI bounds reduce exactly to the standard PAC–Bayes meta-learning bounds.
D.6
Proof of Theorem 4
In advance of the proof of the theorem, we state the following assumptions: Assumption 7 (Task-level exponential moment). There exists a finite constant CTask > 0 such that, for every task θ and fixed support information Sθ , (N ) usr ) ET (N ) Ec∼PU exp N FTask Lusr (θ; c | Sθ ), Lb(N (θ; c | T , S ) ≤ CTask . θ usr θ θ
usr Assumption 8 (Affine transformation for User comparison functions). The functions FTask usr and FEnv are convex. Moreover, there exist constants ktusr , keusr > 0 and nondecreasing usr functions Gusr Task and GEnv such that usr FTask (a, b) ≤ ctsk
=⇒
a ≤ ktusr b + Gusr Task (ctsk ),
usr FEnv (a, b) ≤ cenv
=⇒
a ≤ keusr b + Gusr Env (cenv ).
and Assumption 9 (Environment-level sub-Gaussian User loss). There exists σe > 0 such that, for every c ∈ C, the random variable Lusr (Θ; c),
Θ ∼ Pmeta ,
is σe2 -sub-Gaussian around its mean. Equivalently, for all t ∈ R, 2 2 σ t EΘ∼Pmeta exp t Lusr (Θ; c) − Rusr (c) ≤ exp e , 2 where Rusr (c) := EΘ∼Pmeta Lusr (Θ; c) .
36
Lemma 11 (Environment exponential moment from sub-Gaussianity). Suppose Assumption 9 holds. Let M 1 X i.i.d. ) b (M R (c) := Lusr (θi ; c), θi ∼ Pmeta . usr M i=1 For usr FEnv (a, b) = λe (a − b)2 ,
we have
0 < λe <
1 , 2σe2
usr ) b (M Eθ1 ,...,θM ∼Pmeta Ec∼PU exp M FEnv Rusr (c), R (c) ≤ CEnv , usr
where
1 CEnv = p . 1 − 2λe σe2
Proof. Fix c ∈ C and define Xi (c) := Lusr (θi ; c),
µ(c) := Rusr (c).
By Assumption 9, Xi (c) − µ(c) is σe2 -sub-Gaussian. Hence M
b (M ) (c) = − µ(c) − R usr
1 X (Xi (c) − µ(c)) M i=1
is σe2 /M -sub-Gaussian. Therefore, using the standard quadratic exponential moment bound for a centred sub-Gaussian random variable, 2 1 (M ) b , Eθ1 ,...,θM exp λe M µ(c) − Rusr (c) ≤p 1 − 2λe σe2 for 0 < λe < 1/(2σe2 ). Averaging both sides over c ∼ PU gives the result. Proof of Theorem 4. Fix a task θ. By definition, h i Rusr (θ; Q̃) = Ec∼Q̃ Lusr (θ; c) and h i (N ) (N ) (N ) ) busr R (θ; Q̃ | Sθ ) = Ec∼Q̃ Lusr (θ; c), Lb(N , Sθ ) . usr (θ; c | Tθ usr Since FTask is convex,
usr b(N ) (θ; Q̃ | S (N ) ) FTask Rusr (θ; Q̃), R usr θ (N ) usr ) ≤ Ec∼Q̃ FTask Lusr (θ; c), Lb(N (θ; c | T , S ) . θ usr θ Applying the Donsker–Varadhan variational inequality (Lemma 2) with Q = Q̃,
P = PU ,
and (N ) usr ) f (c) = N FTask Lusr (θ; c), Lb(N , Sθ ) , usr (θ; c | Tθ gives usr b(N ) (θ; Q̃ | S (N ) ) FTask Rusr (θ; Q̃), R usr θ
37
1 ≤ N
! DKL (Q̃∥PU ) + log Zθ ,
where (N ) usr ) Zθ = Ec∼PU exp N FTask (Lusr (θ; c), Lb(N , Sθ )) . usr (θ; c | Tθ Using Assumption 7 and Markov’s inequality, CTask ≥ 1 − δ. P Zθ ≤ δ Hence with probability at least 1 − δ, D (Q̃∥P ) + log(C KL U Task /δ) (N ) usr (N ) busr FTask Rusr (θ; Q̃), R . (θ; Q̃ | Sθ ) ≤ N
(56)
Applying Assumption 8 yields (N )
b(N ) (θ; Q̃ | S Rusr (θ; Q̃) ≤ ktusr R usr θ
) + Gusr Task (Bt ),
where DKL (Q̃∥PU ) + log(CTask /δ) . N Moreover, to obtain the explicit bound we specialise the task-level comparison function to Bt =
usr FTask (a, b) = λt (a − b)2 ,
then ktusr = 1 and Gusr Task (u) =
q
u λt . Therefore,
s b(N ) (θ; Q̃ | T (N ) , Sθ ) + Rusr (θ; Q̃) ≤ R usr θ
D.7
DKL (Q̃∥PU ) + log(CTask /δ) . λt N
(57)
Proof of Theorem 5
Proof of Theorem 5. We prove the result in two steps. The first step controls the gap between the task-level population User losses and their empirical estimators. The second step controls the gap between the sampled-task population average and the full meta-population User risk. (N )
Step 1: task-level generalisation. Fix a sampled task θi and its dataset Si = Sθi . For each context c ∈ C, define Li (c) := Lusr (θi ; c),
b i (c) := Lb(N ) (θi ; c | Si ). L usr
usr By convexity of FTask , Jensen’s inequality gives usr usr b i (c) ≤ E b FTask Ec∼Q̃ Li (c), Ec∼Q̃ L F L (c), L (c) . i i c∼Q̃ Task
Recall by Lemma 2 (Donsker–Varadhan change-of-measure inequality): for probability measures Q ≪ P and any measurable function f , Eh∼Q [f (h)] ≤ DKL (Q∥P ) + log Eh∼P [exp(f (h))] . Apply the inequality with Q = Q̃,
P = PU , 38
and
usr b i (c) , Li (c), L f (c) = N FTask
yields h i usr usr (Li (c),Lbi (c))) . b i (c) ≤ 1 DKL (Q̃∥PU ) + log Ec∼P e(N FTask Li (c), L Ec∼Q̃ FTask U N Combining the two gives i 1 h usr ) b (N FTask D ( Q̃∥P ) + log Z , Rusr (θi ; Q̃), R (θ ; Q̃ | S ) ≤ KL U i i i usr N where
usr b(N ) Zi := Ec∼PU e(N FTask (Lusr (θi ;c),Lusr (θi ;c|Si ))) .
By Assumption 7 and the Markov inequality, δ 2M ≥1− . P Zi ≤ δ 2M Taking a union bound over i = 1, . . . , M , with probability at least 1 − δ/2, for all sampled tasks simultaneously, 2M . log Zi ≤ log δ On this event, 2M usr b (N ) (θi ; Q̃ | Si ) ≤ DKL (Q̃∥PU ) + log δ . FTask Rusr (θi ; Q̃), R usr N usr Using the calibration property of FTask , we obtain ) usr b (N Rusr (θi ; Q̃) ≤ R usr (θi ; Q̃ | Si ) + FTask
DKL (Q̃∥PU ) + log 2M δ N
! .
(58)
Specifically, we have that ) usr usr b (N Rusr (θi ; Q̃) ≤ keusr R usr (θi ; Q̃ | Si ) + Genv (Be ),
(59)
where 1 usr θusr,env Ec∼PU Γe 1 , Btusr := DKL (Q̃∥PU ) + log θusr,env δ
usr (N FTask (Li (c),Lbi (c))) . Γus e := e
Averaging (58) over i = 1, . . . , M gives M
1 X b (M,N ) (Q̃) + F usr Rusr (θi ; Q̃) ≤ R usr Task M i=1
DKL (Q̃∥PU ) + log 2M δ N
where we used the definition M 1 X b (N ) ) b (M,N R ( Q̃) = R (θi ; Q̃ | Si ). usr M i=1 usr
Let us now define the sampled-task population average as M
) R̄(M usr (Q̃) :=
1 X Rusr (θi ; Q̃). M i=1
Therefore, we now obtain with at least probability 1 − δ/2 that ) usr b (M,N ) (Q̃) + FTask R̄(M usr (Q̃) ≤ Rusr
39
DKL (Q̃∥PU ) + log 2M δ N
! .
! ,
Step 2: environment-level generalisation. For each fixed context c, define the environment population and empirical task-average losses M X b (M ) (c) := 1 R Lusr (θi ; c). usr M i=1
Rusr (c) := Eθ∼Pmeta Lusr (θ; c), (M )
By the definitions of Rusr (Q̃) and R̄usr (Q̃), ) b (M ) R̄(M usr (Q̃) = Ec∼Q̃ Rusr (c).
Rusr (Q̃) = Ec∼Q̃ Rusr (c),
usr By convexity of FEnv , using Jensen’s inequality we find ) usr usr b (M ) Rusr (Q̃), R̄(M FEnv usr (Q̃) ≤ Ec∼Q̃ FEnv Rusr (c), Rusr (c) .
Applying Lemma 2 again with Q = Q̃, P = PU , and usr ) b (M f (c) = M FEnv Rusr (c), R usr (c) . Then
where
i 1 h usr ) b (M Ec∼Q̃ FEnv Rusr (c), R (c) ≤ D ( Q̃∥P ) + log Z , KL U Env usr M usr ) b (M ZEnv := Ec∼PU exp M FEnv Rusr (c), R (c) . usr
By Lemma 11, Eθ1 ,...,θM [ZEnv ] ≤ CEnv . Hence, by Markov’s inequality, with probability at least 1 − δ/2, ZEnv ≤
2CEnv . δ
Consequently, with probability at least 1 − δ/2, D (Q̃∥P ) + log 2CEnv KL U usr ) δ . FEnv Rusr (Q̃), R̄(M ( Q̃) ≤ usr M usr , we obtain Using the calibration property of FEnv ) usr Rusr (Q̃) ≤ R̄(M usr (Q̃) + GEnv (Be ),
where Be :=
DKL (Q̃∥PU ) + log 2CδEnv . M
Combining the two levels. Intersecting the high-probability events from Step 1 and Step 2 gives an event of probability at least 1 − δ. On this event, ! DKL (Q̃∥PU ) + log 2δ (M ) usr Rusr (Q̃) ≤ R̄usr (Q̃) + FEnv , M and ) usr b (M,N ) (Q̃) + FTask R̄(M usr (Q̃) ≤ Rusr
DKL (Q̃∥PU ) + log 2M δ N
! .
Substituting the second inequality into the first gives ) usr b (M,N Rusr (Q̃) ≤ R (Q̃) + FTask usr
DKL (Q̃∥PU ) + log 2M δ N
! usr + FEnv
DKL (Q̃∥PU ) + log 2δ M
! , (60)
40
as required. usr 2 Moreover, to obtain an explicit bound q we first note that by setting FEnv (a, b) = λe (a − b) , u implies that keusr = 1 and Gusr Env (u) = λe . Using this and after substituting the result of (57) into (60), we then deduce that s s 2M 1 DKL (Q̃∥PU ) + log δ DKL (Q̃∥PU ) + log 2CδEnv − ) b (M,N Rusr (Q̃) ≤ R (Q̃) + + λe 2 . (61) usr N M
41