{"id":"0f30451c-1367-486d-a8a0-0e0ae111d029","arxiv_id":"2507.15818","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The capacity of semantic private information retrieval with T colluding servers is E[L] divided by L1 + (T/N)L2 + ... + (T/N)^{K-1}LK.","lead":"This paper derives the exact retrieval capacity for a private information retrieval model in which messages have different sizes and different popularity, and any T servers may share the user's queries. The capacity formula generalizes the known semantic PIR result by replacing each 1/N factor with T/N.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Exact capacity theorem overreaches: achievability requires integral ν_i and integer s-sum counts, but Remark 3 proves these only under unstated Li=β_iN^K; for N=2,T=1,K=2,L1=L2=1 no positive α makes ν integral, so the stated scheme cannot run for arbitrary lengths.","rationale":"The reader's weakest_assumption identifies the same load-bearing concern: the achievability proof does not justify integrality of the scheme parameters for arbitrary Li, nor does it specify the required finite field size. My independent check of Eq. (26)-(28) confirms that ν is generally rational and that α must simultaneously divide all Li and clear denominators of V^{-1}L; this fails for small parameter tuples. The paper's Remark 3 only handles the restricted case Li=β_iN^K, which is not part of Theorem 1. This is a proof-completeness gap rather than a demonstrated falsehood of the asymptotic formula: the converse and the worked examples are consistent with the claimed capacity, and a standard block-scaling argument could likely repair the theorem. Therefore the reader's CONDITIONAL verdict is appropriate, and I do not recommend moving to REJECT or ACCEPT without revision.","tokens_in":9973,"tokens_out":30087,"duration_ms":347074,"concrete_test":"Run the minimal instantiation N=2,T=1,K=2,L1=L2=1,p1=p2=1/2. Compute V from Eq. (26) and V^{-1}L=(1/4,1/4); observe that no positive integer α can make ν_i integral while also satisfying Li=αU_i. Then test the natural repair: set L1'=L2'=m with m a multiple of 4 and let m grow, checking whether the scheme achieves rate approaching 2/3. If it does, amend Theorem 1 to state the lattice condition or an asymptotic/block-scaling version. If it does not, the capacity formula is not salvageable by scaling.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Under the literal formulation with fixed integer message lengths, Theorem 1 is not fully proved. The achievability scheme in Section V requires α to make ν=α^{-1}V^{-1}L a vector of positive integers, and additionally requires every ((N-T)/T)^{s-1}ν_k used in the s-sum phases to be an integer, with MDS codes of those dimensions over a sufficiently large finite field. Remark 3 attempts to prove integrality and positivity, but it does so only after imposing Li=β_iN^K, a restriction not stated in Theorem 1. For general Li there may be no feasible α. The minimal example N=2,T=1,K=2,L1=L2=1,p1=p2=1/2 gives V^{-1}L=(1/4,1/4); any α that divides both message lengths must be 1, so ν1=ν2=1/4, and Step 1 would require fractional singleton downloads. Thus the described construction literally does not run for these parameters, although the claimed capacity is 2/3. The converse proof appears independent of this gap, and a block-scaling or padding repair is plausible, so the asymptotic capacity formula is likely correct; however, the exact statement for arbitrary message lengths is overbroad as written. The missing finite-field specification is secondary but should also be stated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies semantic private information retrieval (Sem-PIR) with T colluding servers. Messages have arbitrary integer lengths L1 >= L2 >= ... >= LK and non-uniform retrieval probabilities p_i. The main result, Theorem 1, states that the capacity is E[L] / (L1 + (T/N)L2 + ... + (T/N)^{K-1} LK). The proof consists of a converse based on Han's inequality and an MDS-based achievability scheme that downloads singletons and s-sum combinations; two numerical examples are provided, and corollaries recover or compare with classical TPIR and Sem-PIR capacities. The paper claims that this exact formula holds for all parameter values.","tokens_in":10223,"tokens_out":6941,"duration_ms":74069,"significance":"If correct, the capacity formula is a clean unification of known results: setting T=1 gives the Sem-PIR capacity of [13], and setting equal lengths and uniform priors gives the classical TPIR capacity (1 + T/N + ... + (T/N)^{K-1})^{-1}. The semantic model's prediction that unequal message lengths and non-uniform priors can improve download efficiency is practically relevant, and the corollaries provide useful comparisons. The converse appears independent of the achievability construction, and Example 1 backs the formula with explicit arithmetic. The main caveat is that the achievability proof, as written, does not cover all integer message lengths because of an integrality and MDS-existence gap; the result is therefore currently a conditional exact-capacity theorem, though a repair by block scaling seems plausible.","major_comments":[{"comment":"The achievability scheme is not fully specified for arbitrary integer message lengths. The construction requires nu = (1/alpha) V^{-1} L to be a vector of positive integers and requires every ((N-T)/T)^{s-1} nu_k used in the s-sum steps to be an integer, so that Step 1 and Step 2 can be implemented with whole symbols. Remark 3 proves positivity and integrality only after imposing the normalization L_i = beta_i N^K, a condition not stated in Theorem 1. For example, with N=2, T=1, K=2, and L1=L2=1, we have V^{-1}L = (1/4, 1/4); since alpha must divide both message lengths, alpha=1 is forced, and the scheme would require downloading nu1=nu2=1/4 symbols per server in Step 1. Thus the stated construction does not literally achieve the claimed exact capacity for all parameter values. A block-scaling or padding argument, or an explicit asymptotic statement, is needed to complete the proof; the converse appears independent of this gap.","section":"Section V, Eqs. (25)-(27), Remark 3"},{"comment":"The scheme invokes MDS codes MDS_{a x b} for many values of a and b, but it never specifies the finite field size or proves that all required MDS codes and the random invertible matrices S_i exist over a common field. Since the code dimensions grow with powers of (N-T)/T and with the nu_i, the proof should state a sufficient condition, for example a field of size at least the largest code dimension, or cite an explicit MDS construction that covers the required parameters. This is a repairable gap, but as written the achievability claim is incomplete.","section":"Section V, Steps 1 and 2"}],"minor_comments":[{"comment":"The retrieval probabilities p_i are not specified in Example 2, so E[L] is undefined and the claimed rate equality cannot be verified numerically. Please state p_i or clarify that the rate expression is formal in E[L].","section":"Section VI-B, Example 2"},{"comment":"The notation alpha = gcd(L[K], M([K])) is undefined. It should say the gcd of the entries of the vectors L and M, and it should be clarified over which integers the gcd is taken after normalization.","section":"Section V, Eq. (27)"},{"comment":"There is a stray unmatched bracket in the tuple (S1([beta1], :]), ...); the expression should be corrected to (S1([beta1], :), ..., SK([betaK], :)).","section":"Section VII, Eq. (61)"},{"comment":"The phrase 'since the proof is symmetric over i and j' is slightly misleading because the roles of the desired and the interfering message are not fully symmetric in the derivation; the conclusion is correct, but the wording should be adjusted.","section":"Section VIII, Eq. (74)"},{"comment":"The capacity notation is used inconsistently: Theorem 1 writes the full argument list, while the examples write CSem-TPIR(4,3,3) or CSem-TPIR(8,2,4) without the lengths and priors. Please make the notation uniform.","section":"Theorem 1 and examples"}],"recommendation":"major_revision","confidential_remarks":"This is a standard theory paper in scope for the journal. The gap in the achievability proof is localized and likely repairable, so I recommend major revision rather than rejection. No concerns about attribution or scope beyond the technical issue described."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper derives the capacity of semantic PIR with T colluding servers, giving the formula E[L]/(L1 + (T/N)L2 + ... + (T/N)^{K-1}LK). This is the right generalization, interpolating the no-collusion Sem-PIR result and the classical TPIR capacity. The converse via Han's inequality is sound and the achievability scheme is a genuine adaptation of the TPIR MDS construction. The worked examples check out after correcting a typo in Eq. (59) (the denominator should use (3/4)^2, not 16/9). This is a real step forward for the PIR subfield.\n\nThe main soft spot is the integrality argument in the achievability proof. The scheme requires the ν_i and the s-sum counts ((N-T)/T)^{s-1}ν_i to be positive integers, and the MDS field size to be large enough. Remark 3 attempts to prove this, but only after imposing L_i = β_i N^K, which is not stated in Theorem 1 or in the problem formulation. For arbitrary integer L_i, V^{-1}L has rational entries, and there may be no positive integer α (the number of scheme repetitions) that makes every ν_i integral. The stress-test example N=2, T=1, K=2, L_1=L_2=1 gives M = (1/4, 1/4), so no integer α works. Thus the scheme as written does not achieve the claimed rate for all parameter values. The converse is unaffected, and a block-scaling or padding argument will likely repair the gap, but Theorem 1 as stated overreaches. The finite-field size for the MDS codes is also left unspecified.\n\nI agree with the reader's conditional verdict. The central capacity formula is important and almost certainly correct; the achievability gap is technical, not conceptual. I recommend serious peer review. A major revision should fix the integrality argument (or state the result as asymptotic in message length), correct the typo, and specify the MDS field requirements. The authors are clearly engaging honestly with the problem, and the paper is a useful contribution once the sharp edges are filed down.","headline":"A natural capacity extension with a solid converse but an under-proved achievability step; worth refereeing despite the integrality gap.","tokens_in":10789,"tokens_out":7398,"would_cite":true,"duration_ms":77048,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","94A62"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that the capacity of semantic private information retrieval with $T$ colluding servers is $\\mathbb{E}[L]/\\left(L_1+\\frac{T}{N}L_2+\\cdots+\\left(\\frac{T}{N}\\right)^{K-1}L_K\\right)$, and gives a scheme that attains it.","keywords":["private information retrieval","semantic PIR","colluding servers","capacity","information-theoretic privacy","download cost","MDS codes","TPIR"],"falsifier":"For the small case $N=3$, $T=2$, $K=2$, $L_1=2$, $L_2=1$, $p_1=p_2=1/2$, the claimed capacity is $\\frac{3/2}{2+2/3}=9/16$; an exhaustive search over all finite query-answer protocols that finds any scheme with rate above $9/16$ would refute the upper bound, while showing that the proposed scheme's required $\\nu_i$ are fractional for these lengths would expose the achievability gap.","tokens_in":9728,"feed_emoji":"🔒","tokens_out":9604,"duration_ms":96349,"temperature":0.7,"pith_summary":"The paper studies private information retrieval when messages have different lengths and different retrieval probabilities (semantic PIR) and when any $T$ of the $N$ servers may collude to identify the requested message (Sem-TPIR). It proves the exact capacity: the best possible ratio of average retrieved message length to downloaded symbols is $\\mathbb{E}[L]$ divided by $L_1+\\frac{T}{N}L_2+\\cdots+\\left(\\frac{T}{N}\\right)^{K-1}L_K$, where messages are ordered longest to shortest. This generalizes the classical TPIR capacity, recovered when all lengths and priors are equal, and the no-collusion semantic PIR capacity, recovered at $T=1$. The paper also shows the capacity can exceed ordinary PIR capacity when message lengths and priors are skewed, and it constructs a scheme that reaches the bound.","feed_headline":"Exact download limit found for colluding-server semantic PIR","feed_subtitle":"The capacity equals the average message length over a weighted sum, generalizing TPIR and no-collusion semantic PIR.","key_machinery":"The load-bearing identity is the rate formula $C=\\mathbb{E}[L]/\\left(L_1+\\frac{T}{N}L_2+\\cdots+\\left(\\frac{T}{N}\\right)^{K-1}L_K\\right)$. The mechanism that achieves it is a triangular matrix $V$ (equation (26)) with diagonal entries $N^i/T^{i-1}$ and off-diagonal entries $(N-T)N^{j-1}/T^{j-1}$ for $i<j$; it maps the scheme's per-round symbol counts $\\nu_1,\\ldots,\\nu_K$ to the message sub-packet lengths $U_1,\\ldots,U_K$. Inverting $V$ gives the $\\nu_i$ in terms of the $L_i$, scaled by $\\alpha=\\gcd(L_{[K]},M_{[K]})$ so that the counts are integers. Privacy is maintained by applying the same MDS code and fresh random invertible matrices to interference symbols in each $s$-sum phase, so every $T$-server subset observes equivalent distributions for all possible requested indices.","core_discovery":"The central claim is Theorem 1: for $N$ servers, any $T<N$ colluding servers, $K$ messages with lengths $L_1\\ge\\cdots\\ge L_K$ and retrieval priors $p_i$, the capacity of semantic TPIR is $C=\\mathbb{E}[L]/\\left(L_1+\\frac{T}{N}L_2+\\cdots+\\left(\\frac{T}{N}\\right)^{K-1}L_K\\right)$. The upper bound is proved by a converse using Han's inequality and an induction over permutations of messages, showing that any private scheme must spend at least $\\sum_i (T/N)^{i-1}L_i$ downloads on average. The achievability scheme downloads singleton symbols and $s$-linear combinations of symbols from $s$ distinct messages, encoded with MDS codes and randomized by invertible linear maps, so that any $T$ colluding servers see the same distribution for every possible requested message. The formula reduces to the known TPIR capacity when lengths and priors are uniform, and to the no-collusion semantic PIR capacity when $T=1$.","pith_inferences":["The achievability proof requires every $((N-T)/T)^{s-1}\\nu_i$ and the MDS dimensions to be positive integers; for arbitrary message lengths this is only demonstrated under the normalization $L_i=\\beta_i N^K$. I infer that a block-scaling argument on repeated message sets would close this gap, so the formula is likely the true capacity for all finite lengths even though the literal proof leaves the","The priors enter the capacity only through the average length $\\mathbb{E}[L]$, so the detailed popularity distribution does not affect the achievable download efficiency; only the average message size matters.","Since the formula depends on $N$ and $T$ only through the ratio $T/N$, configurations with the same ratio have the same capacity, and the semantic problem inherits the effective-servers reduction familiar from classical TPIR; a similar symmetrization may extend the result to arbitrary collusion patterns."],"forward_implications":["No scheme can beat the rate $\\mathbb{E}[L]/\\sum_{i=1}^K (T/N)^{i-1}L_i$, and the paper's scheme attains it, so the capacity of semantic TPIR is exactly that quantity.","With equal lengths and uniform priors the formula collapses to the classical TPIR capacity $(1+\\frac{T}{N}+\\cdots+(\\frac{T}{N})^{K-1})^{-1}$.","With $T=1$ it collapses to the no-collusion semantic PIR capacity $\\mathbb{E}[L]/(L_1+\\frac{1}{N}L_2+\\cdots+\\frac{1}{N^{K-1}}L_K)$.","Semantic TPIR can beat ordinary PIR capacity: for $N=10$, $T=2$, $K=2$, $L_1=1000$, $L_2=100$, $p_1=0.99$, the capacity is about $0.9716$, exceeding the classical PIR capacity of about $0.9081$.","Because longer messages receive larger weights in the denominator, reducing the length of the longest messages (or making lengths more equal) improves the capacity the most."],"supporting_citations":[{"why":"Establishes the classical PIR capacity that is recovered as the base case and whose converse style is extended here.","marker":"[2]"},{"why":"Introduces the colluding-servers TPIR model and capacity, and supplies the privacy lemma used to analyze MDS-coded interference.","marker":"[3]"},{"why":"Defines semantic PIR with variable message lengths and priors, proves the no-collusion capacity, and provides the corollary framework extended here to arbitrary $T$.","marker":"[13]"},{"why":"Provides Han's inequality, the converse tool used to bound any scheme's expected download by the weighted message-length sum.","marker":"[14]"}],"fun_headline_variants":["Exact capacity for semantic PIR with colluding servers","Colluding servers included: semantic PIR capacity exact","Semantic TPIR: capacity formula for colluding servers","Exact rate limit for semantic PIR with T collusions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The achievability side assumes that after sub-packetizing the messages, every download count in the scheme is a positive whole number and that finite-field MDS codes of exactly those dimensions exist; for arbitrary message lengths neither is guaranteed by the paper.","fun_headline_variants_meta":{"raw":{"variants":["Exact capacity for semantic PIR with colluding servers","Colluding servers included: semantic PIR capacity exact","Semantic TPIR: capacity formula for colluding servers","Exact rate limit for semantic PIR with T collusions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000703,"raw_usage":{"total_tokens":3153,"prompt_tokens":906,"completion_tokens":2247,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":522,"completion_tokens_details":{"reasoning_tokens":2180}},"tokens_in":522,"tokens_out":2247,"duration_ms":20505,"temperature":1.0,"reasoning_tokens":2180,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T15:23:35.178538+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For the small case $N=3$, $T=2$, $K=2$, $L_1=2$, $L_2=1$, $p_1=p_2=1/2$, the claimed capacity is $\\frac{3/2}{2+2/3}=9/16$; an exhaustive search over all finite query-answer protocols that finds any scheme with rate above $9/16$ would refute the upper bound, while showing that the proposed scheme's required $\\nu_i$ are fractional for these lengths would expose the achievability gap.","supporting_citations":[{"cited_title":"Sun and S","cited_arxiv_id":null,"evidence_quote":"Establishes the classical PIR capacity that is recovered as the base case and whose converse style is extended here."},{"cited_title":"Sun and S","cited_arxiv_id":null,"evidence_quote":"Introduces the colluding-servers TPIR model and capacity, and supplies the privacy lemma used to analyze MDS-coded interference."},{"cited_title":"Vithana, K","cited_arxiv_id":null,"evidence_quote":"Defines semantic PIR with variable message lengths and priors, proves the no-collusion capacity, and provides the corollary framework extended here to arbitrary $T$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides Han's inequality, the converse tool used to bound any scheme's expected download by the weighted message-length sum."}],"review_version":1}