Pith. sign in

REVIEW 3 major objections 4 minor 7 cited by

On the Impossibility of Separating Intelligence from Judgment: The Computational Intractability of Filtering for AI Alignment

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that no efficient external filter can reliably separate harmful AI prompts from benign ones.

desk verdict The main prompt-filtering impossibility theorem has a repairable but load-bearing gap: the pseudorandomness of the adversarial prompt distribution is not established because r is sampled from Z_n, not from uniform bitstrings. read the letter →

arxiv 2507.07341 v1 pith:PSARXI34 submitted 2025-07-09 cs.AI cs.CR

Sarah Ball , Greg Gluch , Shafi Goldwasser , Frauke Kreuter , Omer Reingold , Guy N. Rothblum This is my paper
classification cs.AIcs.CR MSC 68Q1794A60
keywords AIalignmentpromptfilteringoutputcomputationalhardnesstime-lockpuzzlesrecoverablerandomnessimpossibilitytheoremlargelanguagemodels
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish a fundamental computational barrier to aligning large language models through input or output filtering. It constructs adversarial prompts that are computationally indistinguishable from innocent prompts for any efficient filter, yet cause the model to produce harmful output. It proves this for prompt filters, output filters, and even filters that may modify prompts, under cryptographic hardness assumptions. If correct, the results imply that safety cannot be guaranteed by black-box filters that sit outside the model, and that an AI's intelligence and its judgment cannot be cleanly separated.

What carries the argument

The central object is a recoverable-randomness sampling scheme, a pair of algorithms $(\mathsf{Samp}, \mathsf{RecoverRand})$ that lets an adversarial generator embed arbitrary random bits into a prompt in a way that is statistically close to innocent generation yet exactly recoverable by anyone who knows the innocent generator. This is combined with the Rivest–Shamir–Wagner time-lock puzzle, whose repeated-squaring function $r^{2^t} \bmod n$ is cheap for the malicious model to evaluate but hard for any faster filter, and with a hardcore function that makes the puzzle solution look uniform. The construction also uses the leftover hash lemma to make the RSA modulus component pseudorandom, so the entire embedded randomness is indistinguishable from a uniform bitstring to any sufficiently fast filter.

What would settle it

Using the paper's own $\mathsf{RecoverRand}$ algorithm on prompts produced by $G'$ with a known innocent generator $G$, recover the embedded randomness and parse out the $r$ component; then apply a statistical test that compares the observed binary length and value distribution of $r$ against the distribution of a uniform bitstring versus a uniform residue modulo $n$, enumerating candidate $n$ values from the recovered hash pair. If the test succeeds with non-negligible advantage, the claimed pseudorandomness of the embedded randomness is false and the distinguishing condition of Theorem 7 collapses.

Watch

Extended reading notes

Core claim

For any high-entropy innocent prompt generator $G$, the paper constructs an adversarial generator $G'$ and a malicious language model $M'$ such that prompts from $G'$ induce harmful behavior in $M'$, while no prompt filter running significantly faster than $M'$ can distinguish prompts from $G$ and $G'$. The construction hides a harmful instruction inside what looks like ordinary sampling randomness, using a time-lock puzzle whose solution requires a preset amount of sequential computation. Because the filter is too fast to solve the puzzle and too slow to simulate the model, it cannot see the hidden instruction. The paper also proves analogous impossibilities for output filters, for secret-key and public-key collaborative attacks, and for mitigation filters that edit prompts rather than rejecting them.

Load-bearing premise

The proof needs the random integer $r$ hidden inside a prompt to look exactly like a uniform bitstring to any filter that cannot run the LLM; because $r$ is actually sampled modulo a secret RSA modulus, its binary representation is slightly biased, and a filter that can recover that $r$ might detect the bias.

Editorial extensions

If this is right

  • Black-box prompt filtering cannot be a guaranteed safety mechanism: for the constructed models, any efficient filter either rejects many innocent prompts or lets harmful adversarial prompts through.
  • Output filtering faces the same barrier even when the filter is allowed to run longer than the model, so checking answers after generation does not escape the intractability.
  • The impossibility extends to filters that may edit or mitigate prompts, not only reject them, as long as the edits are restricted to a permissible transformation class.
  • If these results are correct, regulatory and technical safeguards that rely on external content moderation without access to model internals cannot offer provable alignment guarantees.
  • The results imply that ensuring alignment may require integrating judgment into the model itself rather than supervising it from the outside.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A testable consequence is that steganographic embedding of harmful instructions in high-entropy innocuous text should defeat any black-box classifier, not just in theory but in practice if recoverable-randomness sampling can be instantiated with a real autoregressive model.
  • The proof's constructed model is deliberately pathological, so the results do not directly show that today's deployed LLMs are unfilterable; they show that a class of malicious models exists that no external filter can safely handle.
  • The same machinery could be adapted to study other supervision tasks, such as detecting hidden goals or evaluating intermediate reasoning, where an overseer is computationally weaker than the system being overseen.
  • A natural extension would be to replace the RSW time-lock assumption with post-quantum time-lock puzzles based on lattice assumptions, which would preserve the impossibility result against quantum-equipped filters.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper claims to prove, under standard cryptographic assumptions, that there exist language models whose harmful behavior cannot be prevented by external filters. The main formal result (Theorem 7, Appendix C.1) asserts that for any high-entropy innocent prompt generator G, one can construct an adversarial generator G' and an LLM M' such that G' induces harmful outputs from M', yet no filter running in time o(t^ε) can distinguish the distributions of G and G'. The proof builds a recoverable-randomness sampling scheme (RRS, Algorithms 1-2) that embeds arbitrary randomness R into prompts, with R constructed as h || h(n) || r || v || c in Algorithm 5, where h is a pairwise-independent hash, n = pq is an RSA modulus, r is sampled from Z_n, and c encrypts a harmful message using a hardcore function of a time-lock puzzle solution. Additional results claim analogous impossibilities for secret-key collaboration (Theorem 8), public-key collaboration (Theorem 9), output filtering (Theorem 10), and prompt mitigation via watermarking (Theorem 11). The paper concludes that intelligence cannot be separated from judgment.

Significance. If the central theorem were correct, it would establish a strong theoretical barrier to black-box prompt filtering and would lend formal support to the paper's philosophical thesis. The paper is technically ambitious, clearly written, and draws on standard tools: RSW time-lock puzzles, hardcore functions, the leftover hash lemma, and recoverable-randomness sampling. The RRS construction is an interesting contribution in its own right, and the connection to watermarking in Theorem 11 is thought-provoking. However, as detailed below, the proof of the main theorem contains a load-bearing gap concerning the pseudorandomness of the randomness block R, and the formal algorithms contain errors that currently invalidate the claimed constructions. These issues must be addressed before the results can be accepted.

major comments (3)
  1. [Appendix C.1.2, proof of Theorem 7, Condition 3; Algorithm 5; Eq. (1)] The same issue affects the output-filtering theorem (Theorem 10), which inherits the R = h || h(n) || r || v || c distribution from the same construction.
  2. [Appendix C.1.1, Algorithm 6 (MaliciousLLM)]
  3. [Appendix C.3, Theorem 9 (public-key version)]
minor comments (4)
  1. [Section 2.1, paragraph on representing r]
  2. [Appendix C.1.1, Algorithm 6, line 4]
  3. [Appendix C.3, title of Theorem 9]
  4. [Appendix D.1, construction of H']

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the separation theorems are conditional on external cryptographic hardness assumptions and do not smuggle their conclusions into those assumptions.

full rationale

The paper's core prompt-filtering impossibility (Theorem 7) is an existence proof: for an arbitrary high-entropy innocent generator G, it constructs an adversarial generator G' and an LLM M' such that G' hides a harmful prompt m inside a time-lock puzzle, and then proves filter indistinguishability by reducing it to standard external primitives: the leftover hash lemma, hardcore functions for the RSW function, and the RSW time-lock sequentiality assumption. None of these assumptions states the theorem's conclusion; they are independent cryptographic building blocks, so the derivation is not circular. The same holds for Theorems 8 and 9, which reduce indistinguishability to one-way functions / public-key encryption, and for Theorem 11, which is explicitly an implication from the existence of a robust watermarking scheme. The output-filtering theorem (Theorem 10) constructs the harmfulness oracle H' together with M', which makes the statement existential and weaker in scope than a claim about 'natural' harmfulness oracles, but the indistinguishability condition is still derived from RSW security rather than from the definition of H'; this is a modeling limitation, not a circular reduction. The paper openly acknowledges the contrived nature of its constructions and, in Remark 4, states that generalizing to arbitrary time-lock puzzles is left open because the required pseudorandomness property is not known; that is an honest limitation, not a self-citation load-bearing step. The only arguably self-referential citation is Bitansky et al. [2016b] for the generic time-lock-puzzle definition and related work, where one co-author overlaps with the present paper, but the proof of Theorem 7 relies on Rivest et al. [1996] and Goldreich-Levin hardcore bits, so this citation is not load-bearing. The accompanying skeptical concern about the biased encoding of r sampled from Z_n is a proof-gap and correctness objection to Lemma usage in Condition 3, not an instance of the paper assuming its target conclusion; accordingly, it does not raise the circularity score.

Assumptions & free parameters 0 free parameters · 8 assumptions · 1 invented entities

The theorems rely on standard cryptographic assumptions and on modeling choices about filter runtime and prompt-generator entropy. The r-sampling issue identified in the soundness rationale shows that one of the implicit statistical assumptions, that r follows a uniform bitstring distribution, is not justified.

assumptions (8)
  • domain assumption RSW time-lock puzzle sequentiality assumption
    Theorems 7 and 10 assume repeated squaring modulo an RSA modulus cannot be parallelized below t^epsilon depth; introduced in Section A.3.1 and used in Section C.1.
  • domain assumption Existence of one-way functions
    Theorem 8 assumes one-way functions for the secret-key based construction; stated in Section C.2.
  • domain assumption Existence of public-key encryption
    Theorem 9 assumes public-key encryption; stated in Section C.3.
  • domain assumption High-entropy innocent prompt generator G exists and runs in poly(lambda) per token
    Theorem 7 requires H(G) at least poly(lambda); see Remark 1 and the formal theorem statements.
  • domain assumption Filter is bounded to o(t^epsilon) runtime while the LLM runs in O(t) per token
    The computational asymmetry between filter and LLM is central to Theorem 1; discussed in Section 1.1.
  • standard math Binary token set without loss of generality
    Reduction from Christ et al. 2023 cited in Appendix B.1.
  • standard math Leftover Hash Lemma
    Used in Lemma 1 to argue that h||h(n) is close to uniform; cited to Vadhan 2012.
  • standard math Goldreich-Levin hardcore functions exist for one-way functions
    Used in Lemma 2 for the hardcore function Q; cited to Goldreich 2006.
invented entities (1)
  • Harmfulness oracle H'
    purpose: Labels outputs of the constructed model M' as harmful in Theorem 4 and Theorem 10; it is defined by applying the MaliciousLLM transformation to H.
    H' is an oracle constructed inside the proof, not independently observable, so it does not provide evidence about natural harmfulness assessment.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Impossibility of Separating Intelligence from Judgment: The Computational Intractability of Filtering for AI Alignment." pith.science (2026). https://pith.science/paper/PSARXI34

@misc{pith2026250707341,
  author       = {Pith},
  title        = {Pith review of: On the Impossibility of Separating Intelligence from Judgment: The Computational Intractability of Filtering for AI Alignment},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PSARXI34}},
  note         = {Machine review of arXiv:2507.07341}
}
read the original abstract

With the increased deployment of large language models (LLMs), one concern is their potential misuse for generating harmful content. Our work studies the alignment challenge, with a focus on filters to prevent the generation of unsafe information. Two natural points of intervention are the filtering of the input prompt before it reaches the model, and filtering the output after generation. Our main results demonstrate computational challenges in filtering both prompts and outputs. First, we show that there exist LLMs for which there are no efficient prompt filters: adversarial prompts that elicit harmful behavior can be easily constructed, which are computationally indistinguishable from benign prompts for any efficient filter. Our second main result identifies a natural setting in which output filtering is computationally intractable. All of our separation results are under cryptographic hardness assumptions. In addition to these core findings, we also formalize and study relaxed mitigation approaches, demonstrating further computational barriers. We conclude that safety cannot be achieved by designing filters external to the LLM internals (architecture and weights); in particular, black-box access to the LLM will not suffice. Based on our technical results, we argue that an aligned AI system's intelligence cannot be separated from its judgment.

Figures

Figures reproduced from arXiv: 2507.07341 by the authors.

Figure 1
Figure 1. This figure illustrates a potential filtering-based alignment system. A powerful, untrusted [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 7 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Safeguards Based on Copyable Context Cannot Provide Reliable Safety for LLMs

    cs.CR 2026-07 conditional novelty 7.0 of 10

    With copyable pre-release evidence, any dual-use release rule that keeps legitimate utility q must leave worst-case attacker assistance at least Γ(q)>0, so useful capability, reliable safety, and open access cannot coexist.

  2. Emergence World: A Platform for Evaluating Long-Horizon Multi-Agent Autonomy

    cs.MA 2026-06 unverdicted novelty 6.0 of 10

    Emergence World is a model-agnostic multi-agent simulation platform integrating live data, 120+ tools, persistent memory, and democratic governance, illustrated by a 15-day study showing divergent outcomes across five...

  3. Send a SCOUT First: Pre-hoc Reasoning for Adaptive Detector Allocation in Prompt-Injection Defense

    cs.CR 2026-05 unverdicted novelty 6.0 of 10

    SCOUT adaptively allocates heterogeneous prompt-injection detectors via pre-hoc reliability prediction, cutting attack success 46% and wall-clock 40% versus always-on GPT-4o on new SCOUT-450 benchmark at modest utilit...

  4. Distinguishable Deletion: Unifying Knowledge Erasure and Refusal for Large Language Model Unlearning

    cs.LG 2026-05 unverdicted novelty 6.0 of 10

    Distinguishable Deletion unifies knowledge erasure and refusal for LLM unlearning via an energy index that enforces boundaries during training and enables refusal at inference.

  5. Spore: Efficient and Training-Free Privacy Extraction Attack on LLMs via Inference-Time Hybrid Probing

    cs.CR 2026-04 unverdicted novelty 6.0 of 10

    Spore extracts private data from LLM memory with one query in black-box mode or ranked tokens in gray-box, outperforming prior attacks while bypassing defenses.

  6. On the Limits of Support-Preserving Alignment and Bounded Filtering

    cs.LG 2026-07 unverdicted novelty 5.0 of 10

    Under support-preserving alignment and bounded filters, harmful output probability cannot be reduced to zero, and measured harm rates plateau above zero across models.

  7. On the Limits of Support-Preserving Alignment and Bounded Filtering

    cs.LG 2026-07 reject novelty 4.0 of 10

    Under support-preserving alignment, bounded safety filters leave a non-zero residual harmful-output rate that plateaus as query budgets grow.

Reference graph

Works this paper leans on

24 extracted references · 23 canonical work pages · cited by 6 Pith papers

  1. [1]

    Samples two primes p, qfrom [1, w], for a parameter w, and set n = pq

    work page

  2. [2]

    , n− 1}, and computes s ← re mod n, where e = 2t is a tower of repeated squarings (i.e., t squarings of r)

    Samples r ← Z∗ n, where Z∗ n = {1, 2, . . . , n− 1}, and computes s ← re mod n, where e = 2t is a tower of repeated squarings (i.e., t squarings of r). To compute re mod n it first evaluates ϕ(n) = (p − 1)(q − 1) and reduces the exponent e′ ← e mod ϕ(n). Then s = re′ mod n, which can be computed in only O(log(e′)) modular exponentiations

    work page

  3. [3]

    Returns (Z, s)

    Defines Z = (n, r) to be the puzzle and s its solution. Returns (Z, s). Note 1. Gen can be adapted to accept an additional input s so that it adheres to the schema from Definition 4. To do that, one would use a root function (Definition 8) that for x ∈ Z∗ n computes “√x” so that it is possible to compute r from s. However, there are some technical details...

    work page

  4. [5]

    Note that Sol computes s using t repeated squarings, each of which is inexpensive, but the full process requires Θ(t) sequential steps

    Returns r2t . Note that Sol computes s using t repeated squarings, each of which is inexpensive, but the full process requires Θ(t) sequential steps. Sequentiality. The security of the RSW puzzle hinges on the assumption that modular exponentiation—specifically, computing r2t mod n—cannot be substantially accelerated via paral- lelism. That is any adversa...

    work page 2018

  5. [6]

    q ∈ [k] at all times

    work page

  6. [7]

    , zi−1, before the if statement (step 8 of Algorithm 1) is executed, the distribution of q is uniform in [k]

    for every iteration i: • for every z0, . . . , zi−1, before the if statement (step 8 of Algorithm 1) is executed, the distribution of q is uniform in [k]. Observe that if these properties hold, then zi’s are sampled from a distribution that is close to G. The only reason the distributions might be different is the aforementioned precision issue. However, ...

    work page

  7. [8]

    k and d at the beginning of the iteration are equal to k and d in the Samp algorithm at the beginning of iteration i

    work page

  8. [9]

    the lengths of a, band q from Samp are equal before the if statement (step 8 of Algorithm 2)

    work page

Show all 24 references
  1. [10]

    threshold randomness

    a ≤lex q ≤lex b, where ≤lex is the lexicographic order, before the if statement (step 8 of Algorithm 2). Similarly, as for Samp these properties can be proven by induction over i. The first property follows from the observation that k and d are updated depending only on the zi...

  2. [12]

    With probability 1 − λ−Ω(1) over z ← G the distributions M ′(z) and M (z) are equal

    (M ′ and M behave identically on G almost always). With probability 1 − λ−Ω(1) over z ← G the distributions M ′(z) and M (z) are equal

  3. [13]

    remember

    (G and G′ are indistinguishable for filters running in o(tϵ)). Under the assumption that RSW is secure, for every prompt filter running in timeo(tϵ), for every m ∈ SH the advantage in distinguishing outputs of G and G′(m) is λ−Ω(1). In words, no filter running in time o(tϵ) ca...

    2006

  4. [15]

    With all but negligible in λ probability over z ← G the distributions M ′(z) and M (z) are equal

    (M ′ and M behave identically on G almost always). With all but negligible in λ probability over z ← G the distributions M ′(z) and M (z) are equal. 12Thus, M ′ can iterate over all of them in time O(t). 23

  5. [16]

    (G and G′ are indistinguishable for filters running in polynomial-time) . Under the assumption that One-Way Functions exist, for every prompt filter running in polynomial- time, for every m ∈ SH the advantage of the filter in distinguishing outputs of G and G′(m) is negligible...

  6. [17]

    For every malicious prompt m ∈ SH, the following two distributions are close: {M ′(z) | z ← G′(m)} , {M (m)}

    (G′ incites harmful behavior in M ′). For every malicious prompt m ∈ SH, the following two distributions are close: {M ′(z) | z ← G′(m)} , {M (m)} . In words, for every harmful prompt from SH the outputs of M ′ and M follow almost the same distribution, in particular, a simila...

  7. [19]

    (G and G′ are indistinguishable for filters running in polynomial-time) . Under the assumption that public key cryptography exists, for every prompt filter running in polynomial- time, for every m ∈ SH the advantage of the filter in distinguishing outputs of G and G′(m) is neg...

  8. [20]

    For every malicious prompt m ∈ SH, with all but negligible in λ probability over z ← M ′(m),16 it holds that H′(z) = Ω Ez←M (m)[H(z)]

    (M ′ outputs are harmful as judged by H′). For every malicious prompt m ∈ SH, with all but negligible in λ probability over z ← M ′(m),16 it holds that H′(z) = Ω Ez←M (m)[H(z)] . In words, for every prompt from SH the outputs of M ′ are almost always as harmful (when judged by...

  9. [21]

    With all but negligible probability in λ over z ← M ()17 H′(z) = H(z)

    (H′ and H are equal on M () almost always). With all but negligible probability in λ over z ← M ()17 H′(z) = H(z). In words, the harmfulness of outputs of M is (almost always) equal as judged by H and H′

  10. [22]

    running time

    (M ′ and M are indistinguishable for filters running in 2ϵ·λ). Under the assumption that RSW is secure, for every output filter running in time 2ϵ·λ, for every m ∈ SH the advantage in distinguishing outputs of M () and M ′(m) is negligible in λ. In words, no filter running in ...

    2023

  11. [23]

    For every prompt-mitigation filter F running in polynomial-time with all but negligible in λ probability over z ← G′ it holds that F (z) = ⊥ or M ′(z) is harmful

    (G′ incites harmful behavior in M ′ even in the presence of prompt-mitigation filters). For every prompt-mitigation filter F running in polynomial-time with all but negligible in λ probability over z ← G′ it holds that F (z) = ⊥ or M ′(z) is harmful

  12. [24]

    With all but negligible in λ probability over z ← G the distributions M ′(z) and M (z) are equal

    (M ′ and M behave identically on G almost always). With all but negligible in λ probability over z ← G the distributions M ′(z) and M (z) are equal

  13. [25]

    For every algo- rithm running in polynomial-time the advantage in distinguishing outputs of G and G′ is negligible in λ

    (G and G′ are indistinguishable for filters running in polynomial-time). For every algo- rithm running in polynomial-time the advantage in distinguishing outputs of G and G′ is negligible in λ. Note 3. Observe that conditions 1 and 3 from Theorem 11 imply that if a polynomial-...

  14. [26]

    If Detectsk(z) = true then return a harmful output

  15. [27]

    E.4 Proof The proof requires a careful comparison of requirements of Theorem 11 and properties of watermark- ing schemes robust against classes of transformations

    Return M (z) otherwise. E.4 Proof The proof requires a careful comparison of requirements of Theorem 11 and properties of watermark- ing schemes robust against classes of transformations. The result follows from the following. • Condition 1 follows from completeness of W. • Co...

  16. [2000]

    key size

    Springer-Verlag. ISBN 3540679073. D. Boneh, J. Bonneau, B. Bünz, and B. Fisch. Verifiable delay functions. In H. Shacham and A. Boldyreva, editors, Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 201...

    2018 arXiv

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.