Konstantine Arkoudas

Konstantine Arkoudas


Research Focus & Metrics

Academic Career Length

13Years (2014-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
21 August 2023 in Philosophy & Technology
Verified
Journal Article
Closed access
PDF file
KAKonstantine Arkoudas
Konstantine Arkoudas

1 April 2014 in ACM Transactions on Information and System Security
Verified
Journal Article
Open access
KAKonstantine Arkoudas
Konstantine Arkoudas
RCRitu Chadha
Ritu Chadha
JCJason Chiang
Jason Chiang
We introduce a new methodology for formulating, analyzing, and applying access-control policies. Policies are expressed as formal theories in the SMT (satisfiability-modulo-theories) subset of typed first-order logic, and represented in a programmable logical framework, with each theory extending a core ontology of access control. We reduce both request evaluation and policy analysis to SMT solving, and provide experimental results demonstrating the practicality of these reductions. We also introduce a class of canonical requests and prove that such requests can be evaluated in linear time. In many application domains, access requests are either naturally canonical or can easily be put into canonical form. The resulting policy framework is more expressive than XACML and languages in the Datalog family, without compromising efficiency. Using the computational logic facilities of the framework, a wide range of sophisticated policy analyses (including consistency, coverage, observational equivalence, and change impact) receive succinct formulations whose correctness can be straightforwardly verified. The use of SMT solving allows us to efficiently analyze policies with complicated numeric (integer and real) constraints, a weak point of previous policy analysis systems. Further, by leveraging the programmability of the underlying logical framework, our system provides exceptionally flexible ways of resolving conflicts and composing policies. Specifically, we show that our system subsumes FIA (Fine-grained Integration Algebra), an algebra recently developed for the purpose of integrating complex policies.

7 August 2023 in Preprints.org
Verified
Preprint
Open access
PDF file
KAKonstantine Arkoudas
Konstantine Arkoudas
GPT-4 was released in March 2023 to wide acclaim, marking a very substantial improvement across the board over GPT-3.5 (OpenAI's previously best model, which had powered the initial release of ChatGPT). Despite the genuinely impressive improvement, however, there are good reasons to be highly skeptical of GPT-4's ability to reason. This position paper discusses the nature of reasoning; criticizes the current formulation of reasoning problems in the NLP community and the way in which the reasoning performance of LLMs is currently evaluated; introduces a collection of 21 diverse reasoning problems; and performs a detailed qualitative analysis of GPT-4's performance on these problems. Based on the results of this analysis, the paper argues that, despite the occasional flashes of analytical brilliance, GPT-4 at present is utterly incapable of reasoning.

23 April 2026 in Preprints.org
Verified
Preprint
Open access
PDF file
KAKonstantine Arkoudas
Konstantine Arkoudas
SBSerafim Batzoglou
Serafim Batzoglou
We introduce PROOFGRID, a challenging benchmark suite for evaluating the reasoning competence of language models through machine-checkable proofs rather than final answers alone. PROOFGRID spans 15 tasks organized around proof writing, proof checking, proof masking, and proof gap-filling. The tasks are expressed in deliberately minimal formal notation, most notably NDL, a stripped-down language for natural deduction that fits in a short prompt and supports precise, auditable checking. As a result, correctness judgments are mechanical, reproducible, and fine-grained rather than dependent on human or LLM judges. PROOFGRID discriminates model capabilities with high resolution and covers a carefully calibrated difficulty spectrum, from foundational reasoning tests to structurally rich challenge tasks that no model currently solves, while avoiding reliance on domain knowledge, problems that can be easily outsourced to solvers, or long-context artifacts. The paper develops a detailed comparative framework for reasoning benchmarks and uses it to survey and systematize a broad and previously fragmented literature. This analysis clarifies how PROOFGRID differs from existing benchmarks not only in difficulty, but in representational choices, verification guarantees, reasoning depth, and vulnerability to shortcut-based success. A key methodological contribution of the paper is an instrumented proof-checking pipeline that tolerates minor surface-level deviations while explicitly identifying the first substantive failure in a stretch of reasoning. This significantly sharpens measurement resolution, separating high-level proof planning from low-level execution noise, and reveals that current frontier models often possess surprisingly strong proof-strategy capabilities even when their formal proof execution is brittle. Using this pipeline, we conduct an extensive evaluation and analysis of a broad set of open and proprietary models released from late 2024 until now. Our results demonstrate strikingly rapid advances as well as sharp remaining limitations. Frontier systems now perform strongly on several foundational tasks, yet difficult PROOFGRID tasks (especially those requiring global combinatorial reasoning or low-level proof synthesis) remain far from solved. Beyond task-level accuracy, we identify widespread epistemic instability, e.g., models often generate proofs containing local logical errors that they can nevertheless recognize and reject when those same inferences are presented in isolation. We formalize this phenomenon via an Epistemic Stability Index (ESI), a quantitative measure of cross-context coherence between model outputs for different but related tasks (such as generated proofs and corresponding entailment judgments). Finally, we complement raw accuracies with 2PL Item Response Theory (IRT) analyses, Wright maps, and a new normalized measure of task discrimination based on Fisher information and latent model abilities estimated from their responses. Taken together, these results position PROOFGRID not merely as a reasoning benchmark, but as a diagnostic framework for studying the emerging structure, limits, and internal coherence of reasoning in contemporary language models.