Token Rankings are Unforgeable Language Model Signatures
Pith reviewed 2026-06-28 06:23 UTC · model grok-4.3
The pith
Token rankings from language models form unique signatures that cannot be forged in polynomial time.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Every language model possesses a unique collection of feasible top-k rankings for large enough k. Finding any other model that shares exactly the same collection is NP-hard, establishing the ranking set as the first known polynomially unforgeable signature. Rankings still permit coarse approximation of the final-layer weights, yet restricting the exposed top-k to a sufficiently small value prevents useful stealing while preserving the signature.
What carries the argument
The set of feasible top-k rankings induced by a model's logit geometry, which uniquely identifies the model and renders forgery NP-hard.
If this is right
- APIs can release token rankings to prove model identity without enabling forgery.
- Parameter stealing from rankings remains possible but is blocked by limiting the exposed k.
- Signature revelation requires smaller k than the k needed to prevent stealing.
- Rankings supply a more restrictive interface than full logits while retaining identifiability.
Where Pith is reading between the lines
- The same geometric hardness might apply to other partial output interfaces such as top-k with ties or sampled tokens.
- APIs could combine ranking signatures with other lightweight checks to strengthen model provenance without full logit exposure.
- Determining the smallest k that guarantees uniqueness for a given model family would be a direct next measurement.
Load-bearing premise
A model's parameters create geometric constraints on logits that yield a set of feasible rankings both unique to that model and whose matching problem is NP-hard.
What would settle it
Finding two different models that share identical feasible top-k ranking sets for all sufficiently large k, or exhibiting a polynomial-time algorithm that constructs a model matching an observed set of rankings.
Figures
read the original abstract
Language model parameters are known to impose unique (to each model) geometric constraints on their logit outputs, which serves as a signature that identifies the model, but also leaks the model's final layer parameters when an API distributes logits. We investigate more restrictive APIs that expose token rankings (i.e., their ordering by probability, but not the probability values) and find that rankings also constitute a signature: every model has a unique set of feasible top-$k$ rankings for sufficiently large $k$. Furthermore, the ranking signature is the first known (polynomially) unforgeable signature, since finding a model with the same set of feasible rankings is NP-hard. On the security front, we find that token rankings are already sufficient to approximately steal the final layer of the model, similar to logits, though the approximation is too coarse to forge the signature, and can be effectively countered by restricting the API to top-$k$ tokens with sufficiently small $k$. Since the top-$k$ required to present the model signature is generally smaller than the $k$ required to prevent stealing, it is possible for an API to present an unforgeable signature without leaking model parameters.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims that language model APIs exposing only token rankings (orderings by probability, without values) still yield model-unique signatures: each model induces a distinct set of feasible top-k rankings for sufficiently large k, owing to geometric constraints on its logit outputs. It further asserts that this signature is polynomially unforgeable because recovering any model whose feasible ranking set matches a given one is NP-hard. The work also shows that rankings suffice for coarse approximation of the final layer (similar to logit leakage) but that the approximation cannot forge the signature, and that choosing a small enough k prevents stealing while still revealing the signature.
Significance. If the uniqueness and NP-hardness results hold, the contribution would be notable for providing the first polynomially unforgeable signature derived from model outputs, enabling API designs that authenticate models without parameter leakage. The separation between the k needed for signature visibility and the k needed to block stealing is a concrete, actionable observation for API security.
major comments (2)
- [Abstract, §3] Abstract and §3 (Uniqueness argument): the claim that geometric constraints on logits produce a unique set of feasible top-k rankings for large k is central but stated without an explicit characterization of the feasible set or a proof that distinct models cannot share the same set; a concrete example or theorem establishing injectivity is required.
- [Abstract, §4] Abstract and §4 (NP-hardness): the assertion that finding a model with the same feasible ranking set is NP-hard is load-bearing for the unforgeability claim, yet no reduction, hardness assumption, or proof sketch appears; the manuscript must supply the reduction from a known NP-hard problem and verify that it applies to the ranking-set matching problem as defined.
minor comments (2)
- [§2] Define 'feasible top-k ranking' formally at first use and clarify how k is chosen relative to vocabulary size.
- [§5] The experimental section on approximate stealing should report the precise k values used and the resulting approximation error to allow direct comparison with the signature k.
Simulated Author's Rebuttal
We thank the referee for the constructive comments. The points raised correctly identify that the uniqueness and NP-hardness claims would be strengthened by explicit formal statements. We will revise the manuscript to incorporate these elements.
read point-by-point responses
-
Referee: [Abstract, §3] Abstract and §3 (Uniqueness argument): the claim that geometric constraints on logits produce a unique set of feasible top-k rankings for large k is central but stated without an explicit characterization of the feasible set or a proof that distinct models cannot share the same set; a concrete example or theorem establishing injectivity is required.
Authors: We agree that an explicit characterization and injectivity proof would improve clarity. In the revised manuscript we will add a theorem that formally defines the feasible set of top-k rankings induced by the geometric constraints on logit vectors and proves that this set is distinct for distinct models. A concrete numerical example illustrating non-overlapping feasible sets for two different models will also be included. revision: yes
-
Referee: [Abstract, §4] Abstract and §4 (NP-hardness): the assertion that finding a model with the same feasible ranking set is NP-hard is load-bearing for the unforgeability claim, yet no reduction, hardness assumption, or proof sketch appears; the manuscript must supply the reduction from a known NP-hard problem and verify that it applies to the ranking-set matching problem as defined.
Authors: We acknowledge that a formal reduction is required to substantiate the NP-hardness claim. The revised version will contain an explicit polynomial-time reduction from a canonical NP-hard problem (e.g., 3-SAT) to the decision problem of whether there exists a model whose feasible ranking set matches a given target set, together with a verification that the reduction preserves the ranking-set equivalence relation used in the paper. revision: yes
Circularity Check
No significant circularity
full rationale
The derivation begins from the stated geometric constraints that model parameters impose on logit outputs (a premise presented as known) and extends this to show that top-k rankings induce unique feasible sets for large k. The NP-hardness of recovering a model matching a given ranking set is invoked directly as the basis for unforgeability. No equations or steps reduce a claimed prediction or uniqueness result to a fitted parameter, self-citation chain, or definitional renaming within the provided text. The central claims remain independent of the target result and rest on external complexity support rather than internal construction.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption Model parameters impose geometric constraints on logit outputs that determine a unique collection of feasible top-k rankings for sufficiently large k.
- standard math Finding another model with an identical set of feasible rankings is NP-hard.
Reference graph
Works this paper leans on
-
[1]
, journal=
Cover, Thomas M. , journal=. Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition , year=
-
[2]
2023 , url=
Using oriented matroids to find low rank structure in presence of nonlinearity , author=. 2023 , url=
2023
-
[3]
Sign rank versus
Alon, Noga and Moran, Shay and Yehudayoff, Amir , booktitle =. Sign rank versus. 2016 , editor =
2016
-
[4]
On Limited Nondeterminism and the Complexity of the V-C Dimension , journal =. 1996 , issn =. doi:https://doi.org/10.1006/jcss.1996.0058 , url =
-
[5]
Topics in Hyperplane Arrangements , author=
-
[6]
On k-Nearest Neighbor Voronoi Diagrams in the Plane , year=
Der-Tsai Lee , journal=. On k-Nearest Neighbor Voronoi Diagrams in the Plane , year=
-
[7]
Padrol, Arnau and Philippe, Eva , title=. Combinatorica , year=. doi:10.1007/s00493-023-00062-3 , url=
-
[8]
Cohen , booktitle=
Zhilin Yang and Zihang Dai and Ruslan Salakhutdinov and William W. Cohen , booktitle=. Breaking the Softmax Bottleneck: A High-Rank. 2018 , url=
2018
-
[9]
Cover , journal =
Thomas M. Cover , journal =. The Number of Linearly Inducible Orderings of Points in d-Space , urldate =
-
[10]
Stirling numbers and a geometric structure from voting theory , journal =. 1977 , issn =. doi:https://doi.org/10.1016/0097-3165(77)90077-2 , url =
-
[11]
Donoho, David L. and Tanner, Jared , TITLE =. J. Amer. Math. Soc. , FJOURNAL =. 2009 , NUMBER =. doi:10.1090/S0894-0347-08-00600-0 , URL =
-
[12]
Lectures on Polytopes: Updated Seventh Printing of the First Edition
Ziegler, G \"u nter M. Lectures on Polytopes: Updated Seventh Printing of the First Edition. 1995. doi:10.1007/978-1-4613-8431-1_6
-
[13]
Ranking patterns of unfolding models of codimension one , journal =
Hidehiko Kamiya and Akimichi Takemura and Hiroaki Terao , keywords =. Ranking patterns of unfolding models of codimension one , journal =. 2011 , issn =. doi:https://doi.org/10.1016/j.aam.2010.11.002 , url =
-
[14]
Björner, Anders and Las Vergnas, Michel and Sturmfels, Bernd and White, Neil and Ziegler, Gunter M. , year=. Oriented Matroids , DOI=
-
[15]
2018 , eprint=
A universality theorem for allowable sequences with applications , author=. 2018 , eprint=
2018
-
[16]
and Pollack, Richard , TITLE =
Goodman, Jacob E. and Pollack, Richard , TITLE =. J. Combin. Theory Ser. A , FJOURNAL =. 1980 , NUMBER =. doi:10.1016/0097-3165(80)90011-4 , URL =
-
[17]
N. E. Mnev , title =. Topology and Geometry --- Rohlin Seminar , series =. 1988 , doi =
1988
-
[18]
Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift , series=
Stretchability of Pseudolines is NP-Hard , author=. Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift , series=. 1991 , doi=
1991
-
[19]
Combinatorica , year=
How Many Circuits Determine an Oriented Matroid? , author=. Combinatorica , year=
-
[20]
Forty-first International Conference on Machine Learning , year=
Trustless Audits without Revealing Data or Models , author=. Forty-first International Conference on Machine Learning , year=
-
[21]
Sun, Haochen and Li, Jason and Zhang, Hongyang , title =. 2024 , isbn =. doi:10.1145/3658644.3670334 , booktitle =
-
[22]
2024 , eprint=
Trust the Process: Zero-Knowledge Machine Learning to Enhance Trust in Generative AI Interactions , author=. 2024 , eprint=
2024
-
[23]
Approximating the Existential Theory of the Reals
Deligkas, Argyrios and Fearnley, John and Melissourgos, Themistoklis and Spirakis, Paul G. Approximating the Existential Theory of the Reals. Web and Internet Economics. 2018
2018
-
[24]
N. J. A. Sloane , title =. 1996 , url =
1996
-
[25]
European Journal of Combinatorics , volume=
On the number of reduced decompositions of elements of Coxeter groups , author=. European Journal of Combinatorics , volume=. 1984 , publisher=
1984
-
[26]
Directed Switching Games on graphs and matroids , journal =
Yahya Ould Hamidoune and Michel. Directed Switching Games on graphs and matroids , journal =. 1986 , issn =. doi:https://doi.org/10.1016/0095-8956(86)90083-3 , url =
-
[27]
Discrete & Computational Geometry , year=
Complete Enumeration of Small Realizable Oriented Matroids , author=. Discrete & Computational Geometry , year=
-
[28]
Finschi, L. and Fukuda, K. , title =. 2002 , issue_date =. doi:10.1007/s00454-001-0056-5 , journal =
-
[29]
Mohammad Tavakoli, Alireza Salemi, Carrie Ye, Mohamed Abdalla, Hamed Zamani, and J
Neumann, Stefan and Gemulla, Rainer and Miettinen, Pauli , booktitle=. What You Will Gain By Rounding: Theory and Algorithms for Rounding Rank , year=. doi:10.1109/ICDM.2016.0049 , annote=
-
[30]
Discrete & Computational Geometry , volume=
Vapnik-Chervonenkis dimension and (pseudo-) hyperplane arrangements , author=. Discrete & Computational Geometry , volume=. 1994 , publisher=
1994
-
[31]
Abello and Kumar , title =. 2002 , issue_date =. doi:10.1007/s00454-002-2881-6 , journal =
-
[32]
Abrahamsen, Mikkel and Adamaszek, Anna and Miltzow, Tillmann , title =. 2021 , issue_date =. doi:10.1145/3486220 , journal =
-
[33]
Logits of
Matthew Finlayson and Xiang Ren and Swabha Swayamdipta , booktitle=. Logits of. 2024 , url=
2024
-
[34]
Feder and Lee, Katherine and Jagielski, Matthew and Nasr, Milad and Conmy, Arthur and Wallace, Eric and Rolnick, David and Tram\`
Carlini, Nicholas and Paleka, Daniel and Dvijotham, Krishnamurthy (Dj) and Steinke, Thomas and Hayase, Jonathan and Cooper, A. Feder and Lee, Katherine and Jagielski, Matthew and Nasr, Milad and Conmy, Arthur and Wallace, Eric and Rolnick, David and Tram\`. Stealing part of a production language model , year =. Proceedings of the 41st International Confer...
-
[35]
The Fourteenth International Conference on Learning Representations , year=
Every Language Model Has a Forgery-Resistant Signature , author=. The Fourteenth International Conference on Learning Representations , year=
-
[36]
Argyrios Deligkas and John Fearnley and Themistoklis Melissourgos and Paul G. Spirakis , keywords =. Approximating the existential theory of the reals , journal =. 2022 , issn =. doi:https://doi.org/10.1016/j.jcss.2021.11.002 , url =
-
[37]
Smoothing the gap between NP and ER , year=
Erickson, Jeff and van der Hoog, Ivor and Miltzow, Tillmann , booktitle=. Smoothing the gap between NP and ER , year=
-
[38]
Training Fully Connected Neural Networks is
Daniel Bertschinger and Christoph Hertrich and Paul Jungeblut and Tillmann Miltzow and Simon Weber , booktitle =. Training Fully Connected Neural Networks is. 2023 , url =
2023
-
[39]
Training Neural Networks is ER-complete , url =
Abrahamsen, Mikkel and Kleist, Linda and Miltzow, Tillmann , booktitle =. Training Neural Networks is ER-complete , url =
-
[40]
Heintz, J. , year =. On the Theoretical and Practical Complexity of the Existential Theory of Reals , volume =. The Computer Journal , publisher =. doi:10.1093/comjnl/36.5.427 , number =
-
[41]
The Thirty-ninth Annual Conference on Neural Information Processing Systems , year=
Better Language Model Inversion by Compactly Representing Next-Token Distributions , author=. The Thirty-ninth Annual Conference on Neural Information Processing Systems , year=
-
[42]
and Zhao, Wenting and Chiu, Justin and Shmatikov, Vitaly and Rush, Alexander , booktitle =
Morris, John X. and Zhao, Wenting and Chiu, Justin and Shmatikov, Vitaly and Rush, Alexander , booktitle =. Language Model Inversion , url =
-
[43]
2022 , month = nov, day =
New Logit Bias experimental parameter , author =. 2022 , month = nov, day =
2022
-
[44]
Low-Rank Softmax Can Have Unargmaxable Classes in Theory but Rarely in Practice
Grivas, Andreas and Bogoychev, Nikolay and Lopez, Adam. Low-Rank Softmax Can Have Unargmaxable Classes in Theory but Rarely in Practice. Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2022. doi:10.18653/v1/2022.acl-long.465
-
[45]
Proceedings of the 40th International Conference on Machine Learning , pages =
Pythia: A Suite for Analyzing Large Language Models Across Training and Scaling , author =. Proceedings of the 40th International Conference on Machine Learning , pages =. 2023 , editor =
2023
-
[46]
arXiv preprint arXiv:2101.00027 , year =
The Pile: An 800GB Dataset of Diverse Text for Language Modeling , author =. arXiv preprint arXiv:2101.00027 , year =
-
[47]
Mathematical Programming Computation , volume =
Parallelizing the dual revised simplex method , author =. Mathematical Programming Computation , volume =. 2018 , doi =
2018
-
[48]
Proceedings of the AAAI Conference on Artificial Intelligence , author=
Taming the Sigmoid Bottleneck: Provably Argmaxable Sparse Multi-Label Classification , volume=. Proceedings of the AAAI Conference on Artificial Intelligence , author=. 2024 , month=. doi:10.1609/aaai.v38i11.29110 , number=
-
[49]
A Fingerprint for Large Language Models , author=. 2025 , eprint=. doi:https://doi.org/10.2352/EI.2026.38.4.MWSF-309 , url=
-
[50]
ACM Computing Surveys , volume=
Securing Large Language Models: A Survey of Watermarking and Fingerprinting Techniques , author=. ACM Computing Surveys , volume=. 2026 , doi=
2026
-
[51]
2021 , doi=
Cao, Xiaoyu and Jia, Jinyuan and Gong, Neil Zhenqiang , booktitle=. 2021 , doi=
2021
-
[52]
MOSEK Fusion API for Python 11.1.10 , year =
ApS. MOSEK Fusion API for Python 11.1.10 , year =
-
[53]
2025 , eprint=
Olmo 3 , author=. 2025 , eprint=
2025
-
[54]
2014 , url =
Jonathan Katz and Yehuda Lindell , title =. 2014 , url =
2014
-
[55]
Authorship Attribution for Neural Text Generation
Uchendu, Adaku and Le, Thai and Shu, Kai and Lee, Dongwon. Authorship Attribution for Neural Text Generation. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP). 2020. doi:10.18653/v1/2020.emnlp-main.673
-
[56]
International Conference on Machine Learning,
John Kirchenbauer and Jonas Geiping and Yuxin Wen and Jonathan Katz and Ian Miers and Tom Goldstein , title =. International Conference on Machine Learning,. 2023 , url =
2023
-
[57]
Are You Getting What You Pay For? Auditing Model Substitution in
Will Cai and Tianneng Shi and Xuandong Zhao and Dawn Song , year=. Are You Getting What You Pay For? Auditing Model Substitution in. 2504.04715 , archivePrefix=
-
[58]
Graph Drawing, 17th International Symposium,
Marcus Schaefer , title =. Graph Drawing, 17th International Symposium,. 2009 , url =
2009
-
[59]
Canny , title =
John F. Canny , title =. Proceedings of the 20th Annual. 1988 , url =
1988
-
[60]
Kingma and Jimmy Ba , title =
Diederik P. Kingma and Jimmy Ba , title =. 3rd International Conference on Learning Representations,. 2015 , url =
2015
-
[61]
Liu and Jorge Nocedal , title =
Dong C. Liu and Jorge Nocedal , title =. Math. Program. , volume =. 1989 , url =
1989
-
[62]
The Electronic Journal of Combinatorics , author=
An Asymptotic Expansion for the Number of Permutations with a Certain Number of Inversions , volume=. The Electronic Journal of Combinatorics , author=. 2000 , month=. doi:10.37236/1528 , abstractNote=
-
[63]
Jon Folkman and Jim Lawrence , abstract =. Oriented matroids , journal =. 1978 , issn =. doi:https://doi.org/10.1016/0095-8956(78)90039-4 , url =
-
[64]
Kendall's Tau for Elliptical Distributions
Lindskog, Filip and McNeil, Alexander and Schmock, Uwe. Kendall's Tau for Elliptical Distributions. Credit Risk. 2003
2003
-
[65]
The Fourteenth International Conference on Learning Representations , year=
The Softmax Bottleneck Does Not Limit the Probabilities of the Most Likely Tokens , author=. The Fourteenth International Conference on Learning Representations , year=
-
[66]
Kruskal , journal =
William H. Kruskal , journal =. Ordinal Measures of Association , urldate =
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.