5arXiv cs.CL (Computation and Language)·
Prompting Complexity: A Kolmogorov-Inspired Formal Framework for Shortest LLM Prompts
A new arXiv preprint introduces 'prompting complexity,' a model-relative analogue of resource-bounded Kolmogorov complexity that measures the shortest plausible human-readable prompt needed to make a deterministic LLM produce a target text. The framework extends to soft prompting complexity for approximate outputs, prompting distance, and behavioral prompting complexity for specification-satisfying outputs. Unlike classical Kolmogorov complexity, the measure is intentionally non-universal and model-specific, with no invariance theorem across models. The paper lays out a research agenda for empirically studying which texts and behaviors are accessible from short prompts under a fixed model interface.
Related guides (2)
Related events (8)
MAS-PromptBench: Systematic study of prompt optimization in multi-agent LLM systems
A new arXiv preprint introduces MAS-PromptBench, a benchmark and study examining when and how much system-prompt optimization improves multi-agent LLM systems (MAS). The authors evaluate two prompt optimizers across diverse MAS configurations varying in task, workflow, communication protocol, and team size. Results show prompt optimization can unlock significant gains but also expose open challenges, particularly around the exponentially growing search space as agent count increases.
Structured Prompt Checklists Outperform Raw and Clarifying-Question Prompts Across LLMs
This paper compares three prompt design strategies—raw prompts, checklist-improved prompts, and clarifying-question prompts—across four task types and three LLM systems (ChatGPT, Claude, Grok). Checklist-improved prompts achieved the highest mean rubric score (7.50/8) versus 5.67 for raw and 6.67 for clarifying-question prompts. Checklist prompts also used fewer tokens on average, suggesting a favorable quality-effort tradeoff. The study provides empirical grounding for structured prompt engineering as a practical technique to reduce multi-turn interaction overhead.
How Long Prompts Block Other Requests - Optimizing LLM Performance
This Hugging Face blog post from TNG Technology Consulting examines how long prompts create head-of-line blocking in LLM serving systems, degrading latency for concurrent requests. The post analyzes the mechanics of prompt processing in inference pipelines and discusses optimization strategies to mitigate throughput bottlenecks caused by lengthy context inputs. It is framed as a practical guide for teams deploying LLMs in production environments where mixed prompt-length workloads are common.
TextReg: Regularization Framework for Mitigating Prompt Distributional Overfitting in LLM Optimization
TextReg addresses a failure mode in iterative prompt optimization where LLM-rewritten prompts grow longer, accumulate narrow rules, and generalize poorly—termed prompt distributional overfitting. The authors formalize this via 'representational inefficiency,' a dual-factor measure decomposing prompt inefficiency into capacity cost and scope narrowness. TextReg applies a soft-penalty regularization framework using Dual-Evidence Gradient Purification, Semantic Edit Regularization, and Regularization-Guided Prompt Update. On reasoning benchmarks, it achieves up to +11.8% OOD accuracy over TextGrad and +16.5% over REVOLVE.
Systematic evaluation of LLM prompt sensitivity in healthcare settings reveals safety risks
Researchers conduct a sensitivity analysis of both general-purpose and medical-specific LLMs using the MedMCQA benchmark, testing robustness to lexical and syntactic prompt perturbations. The study finds that even minor phrasing changes can alter clinical advice, and adversarial prompts can produce dangerous outputs such as incorrect dosages or omitted critical findings. Both general-purpose models (GPT-3.5, Llama 3) and domain-specific models (ClinicalBERT, BioLlama3, BioBERT) exhibit this fragility, with syntactic reordering and misleading contextual cues proving more destabilizing than simple paraphrasing.
Consensus-Labeled Prompt Bank for Measuring Coding-Model Compliance with Malicious-Code Requests
This paper introduces a large, consensus-labeled benchmark of 6,675 prompts drawn from eight existing corpora (ASTRA, CySecBench, AdvBench, JailbreakBench, MalwareBench, RedCode, RMCBench, Scam2Prompt) to evaluate whether coding-specialized LLMs refuse malicious requests. A key contribution is the distinction between requests for executable malicious code (4,748 prompts) versus harmful security knowledge (1,923 prompts), arguing that coding models should face a stricter refusal standard given their outputs can be directly weaponized. A five-judge consensus protocol achieves Fleiss' kappa of 0.767, providing a reliability-quantified substrate for cross-corpus compliance measurement that the field has previously lacked.
Pre-registered study finds Popperian code-generation prompt skills add no benefit beyond structural scaffolding
A pre-registered two-tier ablation study tests whether 'Popperian falsificationist' prompt skills improve LLM code generation through their procedural content or merely through structural scaffolding. Using Claude Sonnet 4.6 and Qwen2.5-Coder-0.5B with execution-based evaluation (HumanEval+ unit tests) rather than LLM-as-judge, the authors find that on the small model, structured prompts lift correctness by 20-22 points but the full Popperian skill shows no separable benefit over a labels-only scaffold. The paper contributes a calibrated negative result and a reusable disambiguation protocol for evaluating prompt-skill families, while also documenting that LLM self-judges at 0.5B scale perform no better than random selection.
PAC-Bayes analysis establishes formal expressivity and alignment floors for prompt-conditioned LLMs
A new arXiv preprint models user-LLM interaction as a bilevel cheap-talk game and derives PAC-Bayes bounds showing two irreducible limitations: an 'expressivity floor' where language's finite channel capacity makes distinct tasks indistinguishable, and an 'objective-misalignment floor' where alignment constraints prevent reaching user-ideal outputs. The authors prove that prompt-conditioned LLMs cannot be universal problem solvers, as correct behavior on certain task families is provably unattainable even with infinite data, optimal training, or model scaling. The work suggests multimodal inputs and external memory as potential mitigations by increasing task-relevant information bandwidth.