CodexDB: Generating Code for Processing
SQL Queries using GPT-3 Codex

Immanuel Trummer

Cornell University

CodexDB is an SQL processing engine whose internals can be customized via natural language instructions. CodexDB is based on OpenAI's GPT-3 Codex model which translates text into code. It is a framework on top of GPT-3 Codex that decomposes complex SQL queries into a series of simple processing steps, described in natural language. Processing steps are enriched with user-provided instructions and descriptions of database properties. Codex translates the resulting text into query processing code. An early prototype of CodexDB is able to generate correct code for a majority of queries of the WikiSQL benchmark and can be customized in various ways.

Artifact Availability:

The source code, data, and/or other artifacts have been made available at <>.

§ INTRODUCTION

Modifying a database management system is hard. Systems such as Postgres feature millions of code lines. Understanding and changing that code requires expert knowledge in databases on top of advanced coding skills. This prevents all but the most experienced developers from creating customized versions.

This paper presents the vision behind CodexDB, a novel database management system that can be customized without expert developer skills. Users specify natural language instructions, along with their queries, which influences code generated for query processing. The enabling technology for this system is OpenAI's GPT-3 Codex model. Codex is a large neural network, currently available via a private beta test, that translates natural language instructions into code. This paper presents first experimental results and an outlook on future steps.

The range of applications is vast. To name just a few, consider the following use cases.

A developer wants to benchmark different data processing frameworks (e.g., Pandas and Vaex in Python or Tablesaw and Morpheus in Java) on a specific SQL workload and hardware platform. Traditionally, doing so requires either modifying an existing database management system or writing query-specific code from scratch. With CodexDB, that developer specifies queries, together with natural language instruction such as “Use pandas library”. While CodexDB may not succeed at generating code for each workload query, obtaining performance results for a subset can guide future development efforts. Also, generated code can be manually validated and reused in case of recurrent queries.

A novice database user wants to gain a deeper understanding of how database management systems work. To that purpose, the user would like to generate customized output after each processing step (e.g., summarizing steps performed and showing a small sample of intermediate results). Integrating such changes into traditional systems is beyond the user's capabilities. With CodexDB, the user specifies natural language queries (which, internally, are translated into SQL), together with a natural language description of desired per-step output.

CodexDB accepts queries, together with natural language instructions, as input. These instructions customize the way in which queries are executed. CodexDB generates code to process queries while complying with additional instructions. A first option is to submit queries and instructions directly to GPT-3 for code generation. We will see in Section <ref> that this approach does not work.

Instead, CodexDB adapts techniques from classical query planning. It decomposes complex SQL queries into sequences of simple processing steps. In contrast to prior work, those steps are formulated in natural language using corresponding text templates. Finally, automatically generated plan steps are interleaved with user-provided instructions. The resulting text is enriched with information about the database schema and physical layout. The final text is submitted to GPT-3 Codex (as a so-called “prompt”). Using this approach as a starting point, CodexDB generates code for sample queries in a training step. The resulting code samples can be integrated into prompts generated at run time to increase the chances of success. An early prototype of CodexDB generates correct code in a majority of cases for a popular text-to-SQL benchmark. Also, it is able to customize generated code using simple instructions, inspired by the use cases outlined before.

In summary, the original scientific contributions in this paper are the following:

* The paper presents the vision behind CodexDB, an analytical SQL engine that can be customized via natural language instructions.

* The paper discusses first experimental results, based on an early prototype of CodexDB.

* The paper outlines next steps and future research.

The remainder of this paper is organized as follows. Section <ref> discusses recent progress in natural language processing and compares CodexDB to prior work. Section <ref> describes the architecture of the first prototype. Section <ref> reports first experimental results in multiple scenarios. Section <ref> discusses next steps and concludes.

§ BACKGROUND AND RELATED WORK

CodexDB is enabled by recent advances in the domain of natural language processing. Those advances have been fuelled by two key ideas: a novel neural network architecture, the Transformer <cit.>, and new training paradigms, implementing the idea of transfer learning <cit.>. The Transformer is nowadays the dominant architecture in the domain of language processing <cit.>. Among other advantages, it lends itself better to parallelization than prior methods. This has, in part, enabled the creation of very large, pre-trained language models. Such models are pre-trained on tasks for which large amounts of training data are easily available, e.g. predicting the next word in text snippets. While pre-training is very expensive, the resulting models can be easily specialized for new tasks via different methods. Fine-tuning describes a process in which pre-trained models are used as a starting point for further training on more specialized tasks (reducing the amount of training samples and computational overheads by orders of magnitude via pre-training <cit.>). Until recently, fine-tuning has been the primary method of exploiting pre-trained language models. The latest generation of pre-trained models, most notably OpenAI's Generative Pre-Trained Transformer (GPT) version 3, unlocks new possibilities. It turns out that sufficiently large models can oftentimes solve new tasks without specialized training (“zero-shot learning”), based on inputs describing the task in natural language alone <cit.>. Precision increases if the input integrates few (i.e., typically less than ten) examples pairing tasks of the same type with solutions (“few-shot learning”). This is the method currently used by CodexDB. The final development that enabled this paper is the emergence of the Codex variant of GPT-3 <cit.>. The primary difference between GPT-3 Codex and the original GPT-3 model lies in the data used for pre-training. GPT-3 Codex is trained on code and technical documentation. This results in a model whose primary use case is the translation of natural language commands into code.

CodexDB connects to prior work on natural language interfaces in the database community <cit.>. So far, the focus was on “democratizing access to data”, i.e. enabling lay users to work with database systems. CodexDB goes one step further by “democratizing” the design of database system internals. The goal is to enable lay users to change system behavior to a degree that goes beyond the configuration scope of traditional database systems (as well as making such changes easier for more advanced users).

CodexDB relates to prior work exploiting machine learning <cit.> and specifically Transformers <cit.> in the context of database systems. It connects broadly to prior work using GPT-3 for program synthesis <cit.>. It differs by its focus on customizable SQL query processing. Prior work on code generation for query processing <cit.> cannot integrate natural language instructions.

§ SYSTEM OVERVIEW

system=[draw, rectangle, rounded corners=1mm, shade, top color=gray!10, bottom color=gray!20, blur shadow=shadow blur steps=5]
component=[draw, rectangle, shade, top color=blue!10, bottom color=blue!20, minimum width=4cm, font=, blur shadow=shadow blur steps=5]
dataflow=[thick, -latex]
mdataflow=[thick, <->]

[system] (-2.25,-5.5) rectangle (3.5,1);
[font=] at (0.625,0.7) CodexDB;
[component] (nlqi) at (0,0) Text-to-SQL (Optional);
[component] (planner) at (0,-1) Natural Language Planner;
[io, anchor=east] (query) at (-2.5,0) Query;
[io, anchor=east] (mod) at (-2.5,-1) Instructions;
[component] (prompt) at (0,-2) Prompt Generator;
[component] (code) at (0,-3) Code Generator (GPT-3);
[component] (engine) at (0,-4) Execution Engine;
[component] (verify) at (0,-5) Verification;
[component, rotate=90, minimum width=2.5cm] (samples) at (3,-4) Code Samples;
[component, rotate=90, minimum width=2.5cm] (catalog) at (3,-1) DB Catalog;
[io, anchor=east] (result) at (-2.5,-4) Result;

[dataflow] (nlqi) – (planner);
[dataflow] (planner) – (prompt);
[dataflow] (prompt) – (code);
[dataflow] (code) – (engine);
[dataflow] (engine) – (verify);
[dataflow] (verify.east) – (samples);
[dataflow] (catalog) – (prompt);
[dataflow] (samples.east) – (prompt);
[dataflow] (query) – (nlqi);
[dataflow] (mod) – (planner);
[dataflow] (engine) – (result);

Overview of CodexDB prototype.

Figure <ref> shows an overview of CodexDB. Users enter a query as well as natural language instructions, influencing the code generated for query processing. The query is formulated either in SQL or in natural language. In the latter case, the query is first translated into an SQL query via text-to-SQL methods <cit.>.

Text templates used during planning.

Pattern     Text Template

Check if T() equals T()

Filter T() using T()

T() (aka. T())

Create table with columns T() from T()

The SQL query and natural language instructions form the input to the query planner. This planner differs from prior query planners by its output format. As the plan is translated into code by GPT-3 in the following steps, the plan is formulated as a sequence of natural language steps. User-provided natural language instructions are included as steps in such plans.

More precisely, the planner treats the nodes in the query tree in post-order. Each node is translated into a processing step, formulated in natural language. To do so, the planner uses text templates that are associated with specific node types. Table <ref> shows example templates (T() and T() denote the text representation of expressions  and  respectively). As plan steps are numbered, intermediate results are referred to via the number of the step generating them. The last step in the plan instructs GPT-3 to write the query result into a file at a specified location.

Currently, CodexDB allows users to specify two types of instructions: instructions that refer to the plan execution as a whole (e.g., instructions on which libraries to use for processing) as well as instructions that are executed after each step (e.g., instructions determining customized logging output). Instructions of the former type are pre-pended to the template-based processing steps (i.e., they become the first plan step) while instructions of the latter type are inserted after each processing step (i.e., the number of plan steps doubles). Note that, currently, the planner does not perform any cost-based or heuristic optimization.

Code generation is initiated by submitting a prompt to GPT-3 for completion. This prompt represents the start of a program that GPT-3 Codex tries to finish. The prompt integrates details about the data in the database, extracted from the database catalog, including the names of tables and their columns, as well as a path to the corresponding files. This description is generated using a simple text template with placeholders for column and table names. Also, the prompt integrates the aforementioned plan steps. The prompt is passed on to GPT-3 which answers with a piece of code. CodexDB tries to execute the code, and to read the generated query result. If the code does not execute (or if it does not generate a result file), CodexDB executes up to a configurable number of retries. With each retry, the “temperature” (a Codex parameter determining the degree of randomness in code generation) is increased to enable new solutions. If successful, the result is returned to the user.

CodexDB can be used in a zero-shot setting (i.e., it generates code with instructions not seen before). Alternatively, it executes a training phase before run time with fixed instructions. The purpose of training is to generate a library of code samples, generated using the target instructions. During training, CodexDB uses sample queries for which the query result is known. It retries code generation until the query result matches the known one (or until it reaches the maximal number of retries). At run time, a specified number of samples is randomly selected from that library and included into the prompt. Having examples in the prompt (“few-shot learning”) increases the success probability, as shown in Section <ref>.

Table Data with columns 'Player','No_','Nationality','Position',
'Years_in_Toronto','School_Club_Team', stored in 'Data.csv'.
Processing steps:
1. Load data for table Data.
2. Print progress updates.
3. Check if 'Player' equals 'dell curry'.
4. Print progress updates.
5. Filter results of Step 1 using results of Step 3.
6. Print progress updates.
7. Create table with columns 'Years_in_Toronto'
(aka. result ) from results of Step 5.
8. Print progress updates.
9. Write results of Step 7 to file 'result.csv' (with header).
10. Print progress updates.

Example prompt for code generation integrating a description of the database (blue), processing steps (black), and natural language instructions (red).

showspaces=false, showstringspaces=false

data = pd.read_csv('Data.csv')
print('Loaded Data')
is_dell_curry = data['Player'] == 'dell curry'
print('Checked if Player equals dell curry')
dell_curry_data = data[is_dell_curry]
print('Filtered data for dell curry')
result = dell_curry_data['Nationality']
print('Created table with Nationality column')
result.to_csv('result.csv', header=True)
print('Wrote to file result.csv')

Code generated by GPT-3 in response to prompt from Figure <ref> (code was shortened for readability by removing empty lines and comments).

Consider the query   from the WikiSQL benchmark. Assume a user enters this query, together with the per-step instructions “Print progress updates”. Figure <ref> shows the prompt for this query, interleaving automatically generated processing steps with user instructions and providing context on the database schema. Figure <ref> shows the generated code. It processes the query and writes the result into a file. While doing so, it prints out progress updates summarizing steps performed.

§ EXPERIMENTS

linelistblue, solid, mark=*,red, mark=x, mark size=3,brown, mark=diamond, mark size=3,gray, mark=triangle, mark size=3,purple, mark=+, mark size=5,violet, mark=square, dotted, thick, mark size=3,cyan, mark=*, mark size=2

The goal of the experiments is threefold. First, to verify that CodexDB generates correct code in most cases. Second, to evaluate the degree to which code can be customized via natural language instructions. Third, to compare CodexDB to other baselines. Section <ref> discusses the experimental setup while Section <ref> reports results.

§.§ Setup

All experiments are executed on an AWS EC2 instance of type t2.xlarge with 16 GB of RAM, four virtual CPUs, and 800 GB of EBS storage. The instance uses Amazon's Deep Learning AMI (Version 53) and runs Ubuntu 18.04. CodexDB is implemented in Python 3 and accesses OpenAI's GPT-3 Codex model via OpenAI's Python API. The experiments use the “Cushman” and “Davinci” versions of Codex with an estimated parameter count of 6.7 billion and 175 billion parameters respectively <cit.>. The generated code is in Python, the language both models are most capable in <cit.>.

The following experiments compare CodexDB to baselines that try translating natural language queries directly to code. This is the most direct method of using GPT-3, making the comparison interesting. Doing so requires a text-to-SQL benchmark that features natural language questions, along with corresponding queries. We consider a subset of the WikiSQL benchmark <cit.>, a popular benchmark featuring over 80,000 queries with examples. The experiments only consider up to the first hundred queries as treating all queries is prohibitively expensive[At the time of writing, OpenAI Codex is only available to beta testers and access is subject to a rate limit of 20 requests per minute.]. The data on which queries operate is stored in the .csv format.

The experiments evaluating CodexDB focus on the key step of translating an SQL query into code, possibly with additional natural language instructions. Translating natural language questions into SQL queries is a well studied problem. Corresponding results for the WikiSQL benchmark are available <cit.> with recent methods achieving a precision of over 90 % <cit.>. We consider a test case (characterized by a natural language query with associated data) as “solved” if the generated program is executable and generates the correct result. This proxy for correctness is often used to evaluate natural language query interfaces <cit.>. A subset of generated programs was manually validated as well. Unless noted otherwise, CodexDB retries generating a program once if the first generated program is not executable. If the first program executes but generates an incorrect result, the corresponding test case is not solved. CodexDB uses a temperature of zero for the first try and increases the temperature (determining the degree of randomization during code generation) by an amount determined by the formula $0.5/N$ where $N$ is the maximal number of allowed tries (typically two).

To test customization, we consider six natural language instructions. Three of them focus on processing methods by instructing CodexDB to use specific libraries: “Use pandas library”, “Use vaex library”, and “Use datatable library”. The other three instruct CodexDB to generate specific logging output after each processing step: “Print 'Done.' ”, “Print intermediate results”, and “Print progress updates”. The first three instructions are added once as first plan step. The last three are added after each step of the initial plan. Note that the following figures and tables abbreviate those instructions slightly (e.g., in the figure legends).

§.§ Results

[group style=group size=1 by 1, ylabels at=edge left, xlabels at=edge bottom, width=6cm, height=3.5cm, legend entries=Question Prompt, Query Prompt, CodexDB Prompt, legend columns=1, ymode=normal, ymajorgrids, xlabel=GPT-3 Codex variant, ylabel=Nr. Solved, legend pos=outer north east, ylabel near ticks, xlabel near ticks, xtick=0, 1, xticklabels=Cushman, Davinci, ybar, nodes near coords, enlargelimits=0.275, xmin=-0.5, xmax=1.5]
coordinates (0, 0) (1, 0);
coordinates (0, 0) (1, 0);
coordinates (0, 11) (1, 22);

Number of test cases solved out of 100 without prior training (“zero-shot”) for different models and prompts.

Figure <ref> reports results of an experiment comparing different prompt generation methods (on 100 queries from the WikiSQL test set). “CodexDB Prompt” refers to prompts generated by CodexDB (integrating, in particular, natural language query plans). “Question Prompt” and “Query Prompt” integrate the same description of the data source as CodexDB (i.e., table and column names) but replace the natural language query plan by the natural language question or the correct SQL query respectively. Clearly, the prompts of CodexDB, enriched by query plans, are necessary to generate correct code. The Davinci model (which features most parameters) solves significantly more test cases than the Cushman version. On the other side, average generation times (seven seconds versus two seconds) are higher for Davinci.

[xlabel=Number of tries, ylabel=Nr. Solved, width=6cm, height=3.5cm, ymajorgrids, xtick=data, ylabel near ticks, legend entries=-,Use pandas,Use vaex,Use datatable,Print “Done.”,Print results,Print progress, legend columns=1, legend pos=outer north east, cycle list name=linelist]
coordinates (1, 9) (2, 12) (3, 18) (4, 24) (5, 26) (6, 27) (7, 30) (8, 36) (9, 38) (10, 39);
coordinates (1, 25) (2, 30) (3, 32) (4, 33) (5, 33) (6, 35) (7, 35) (8, 36) (9, 36) (10, 36);
coordinates (1, 3) (2, 5) (3, 11) (4, 16) (5, 21) (6, 24) (7, 26) (8, 28) (9, 28) (10, 28);
coordinates (1, 6) (2, 13) (3, 15) (4, 15) (5, 19) (6, 20) (7, 20) (8, 21) (9, 21) (10, 21);
coordinates (1, 1) (2, 1) (3, 2) (4, 3) (5, 5) (6, 9) (7, 17) (8, 20) (9, 21) (10, 23);
coordinates (1, 0) (2, 0) (3, 0) (4, 0) (5, 1) (6, 2) (7, 3) (8, 5) (9, 8) (10, 10);
coordinates (1, 0) (2, 0) (3, 0) (4, 0) (5, 1) (6, 1) (7, 2) (8, 4) (9, 7) (10, 8);

Number of test cases out of 50 solved during training for different instructions as function of the number of tries.

Figure <ref> reports a success rate of 22% without prior training. Language models are often fine-tuned to increase performance for specific tasks. This option is not yet available for the Codex series of GPT-3. Instead, we consider few-shot scenarios <cit.> in the following. Here, examples with solutions are integrated as part of the prompt.

Figure <ref> reports the results of a preparation run, using 50 queries from the WikiSQL training set and the Davinci model. As training is executed before run time, up to ten tries are allowed. Furthermore, it is assumed that solutions for training samples are available, allowing to stop code generation only if the execution result is correct (as opposed to using the first executable code). Figure <ref> reports solved test cases as a function of the (maximal) number of tries. Different lines are associated with additional natural language instructions (“-” designates no additional instructions). Training took between 1510 seconds (when instructed to use the pandas library) and 8,300 seconds (with instructions “print intermediate results”). Given enough tries and results to compare to, CodexDB solves 80% of test cases without additional instructions.

[group style=group size=2 by 1, y descriptions at=edge left, xlabels at=edge bottom, horizontal sep=5pt, width=3.5cm, height=3.5cm, ymode=normal, ymajorgrids, yminorgrids, ytick=0, 20, 40, 60, 80, 100, xlabel=Nr. samples, ylabel=Nr. Solved, ylabel near ticks, xlabel near ticks, xtick=0, 2, 4, enlargelimits=0.1, ymin=0, ymax=100, cycle list name=linelist]
[title=Cushman Model]
coordinates (0, 0) (2, 59) (4, 63);
coordinates (0, 0) (2, 62) (4, 54);
coordinates (0, 11) (2, 67) (4, 23);

[title=Davinci Model,legend entries=Question Prompt, Query Prompt, CodexDB Prompt, legend columns=1, legend pos=outer north east]
coordinates (0, 0) (2, 68) (4, 65);
coordinates (0, 0) (2, 58) (4, 61);
coordinates (0, 22) (2, 79) (4, 73);

Number of test cases solved out of 100 as a function of the number of training samples in prompt (“few-shot”).

Figure <ref> reports number of test cases solved (out of 100 queries from the WikiSQL test set, i.e. no overlap with pre-generated samples) as a function of the number of samples included in the prompt. It compares the previously introduced prompt styles. Clearly, performance improves significantly (e.g., from around 20 to around 80% for Davinci) when adding samples. Adding samples decreases the gap between CodexDB's and other prompts. Still, the CodexDB prompt performs best except for four samples and the Cushman model. The reason is the slightly longer prompts of CodexDB (featuring query plans) that exceed the maximum input size for the Cushman model for 67 test cases. Davinci supports larger inputs and does not suffer from this problem. Unless noted otherwise, the remaining experiments use two samples and the Davinci model (the configuration leading to maximal performance in Figure <ref>).

Code length in characters for different languages and instructions (only considering executable programs).

Language     Instructions     Min     Median     Max

SQL     -     42     77     227

Python     -     276     545     1110

Use pandas library     284     438.5     782

Use vaex library     355     637     1018

Use datatable library     307     437     848

Print “Done.”     390     724     1388

Print intermediate results     458     875     1734

Print progress updates     585     836     1458

[group style=group size=1 by 2, ylabels at=edge left, xlabels at=edge bottom, width=8cm, height=3.5cm, legend entries=-,Use pandas,Use vaex,Use datatable, Print “Done.”, Print results, Print progress, legend columns=3, ymode=normal, ymajorgrids, ylabel=Nr. Solved, legend to name=modificationsLegend, ylabel near ticks, xlabel near ticks, xtick=, ybar, nodes near coords, enlargelimits=0.275]
[title=Cushman-Codex Model, bar width=7pt]
coordinates (2, 67);
coordinates (2, 69);
coordinates (2, 74);
coordinates (2, 60);
coordinates (2, 64);
coordinates (2, 69);
[fill=black] coordinates (2, 72);

[title=Davinci-Codex Model, bar width=7pt]
coordinates (2, 79);
coordinates (2, 81);
coordinates (2, 76);
coordinates (2, 58);
coordinates (2, 69);
coordinates (2, 71);
[fill=black] coordinates (2, 77);

Number of test cases solved out of 100 for different natural language instructions.

We test customization by adding the instructions described in Section <ref>. Figure <ref> reports the number of test cases solved with different instructions. In most cases, adding more instructions tends to decrease success ratio for the largest model. Interestingly, the impact varies across instructions. In particular, asking CodexDB to use the pandas library slightly increases performance. This seems reasonable as the pandas library is popular (i.e., the training set of GPT-3 Codex likely includes various example codes) and supports operations similar to SQL operators. Manual analysis of the first 20 programs generating the correct result shows that they are indeed correct. Table <ref> reports statistics on the size of generated code (and on the size of the corresponding SQL queries), measured in characters. The average size of code generated by CodexDB is larger by up to one order of magnitude, compared to SQL queries. This illustrates the difficulty of the task. Adding instructions on logging increases code size (due to print statements after processing steps).

[group style=group size=1 by 1, ylabels at=edge left, xlabels at=edge bottom, width=8cm, height=3.5cm, legend entries=-,Use pandas,Use vaex,Use datatable, legend columns=4, ymode=normal, ymajorgrids, xlabel=Imported libraries, ylabel=Nr. Programs, legend to name=plainLegend, ylabel near ticks, xlabel near ticks, xtick=data, xticklabels=csv, pandas, vaex, datatable, ybar, nodes near coords, enlargelimits=0.275]
[title=Davinci-Codex Model, bar width=7pt]
coordinates (0,34) (1,66) (2,0) (3,0);
coordinates (0,0) (1,100) (2,0) (3,0);
coordinates (0,16) (1,61) (2,100) (3,0);
coordinates (0,3) (1,15) (2,0) (3,100);

Number of generated programs out of 100 importing specific libraries for library-related instructions.

So far, we discussed correctness. Next, we examine whether additional instructions are reflected in the generated programs. Figure <ref> reports the number of generated programs (out of 100) that import certain libraries. Without specific instructions, 34% of generated programs import the “csv” library while 66% import pandas. Incorporating instructions to use pandas, vaex, or datatable into the prompt ensures that each generated programs imports the associated library. In some cases, in particular for vaex, programs import multiple libraries (both, csv and pandas). Manual inspection of the generated code reveals that some of those programs contain redundancy (e.g., by importing data using vaex, then transforming into pandas data frames). While this subset of programs formally satisfies the instructions (they import, i.e. “use”, the corresponding library), they do not entirely reflect its spirit.

[group style=group size=1 by 2, ylabels at=edge left, x descriptions at=edge bottom, width=8cm, height=3.5cm, legend entries=-,Use pandas,Use vaex,Use datatable, DBMS, legend columns=5, xtick=data, ymode=normal, ymajorgrids, ylabel=Execution Time (s), legend to name=scalingLegend, ylabel near ticks, xlabel near ticks, ybar=0pt, ymin=0]
[title=Scaling Factor=1,000, bar width=2pt]
table[col sep=comma, x expr=+1, y index=0, skip first n=1] plots/performance/plain/times.csv;
table[col sep=comma, x expr=+1, y index=0, skip first n=1] plots/performance/pandas/times.csv;
table[col sep=comma, x expr=+1, y index=0, skip first n=1] plots/performance/vaex/times.csv;
table[col sep=comma, x expr=+1, y index=0, skip first n=1] plots/performance/datatable/times.csv;
table[col sep=comma, x expr=+1, y index=0, skip first n=1] plots/performance/sql/times.csv;

[title=Scaling Factor=1,000,000, bar width=2pt]
table[col sep=comma, x expr=+1, y index=1, skip first n=1] plots/performance/plain/times.csv;
table[col sep=comma, x expr=+1, y index=1, skip first n=1] plots/performance/pandas/times.csv;
table[col sep=comma, x expr=+1, y index=1, skip first n=1] plots/performance/vaex/times.csv;
table[col sep=comma, x expr=+1, y index=1, skip first n=1] plots/performance/datatable/times.csv;
table[col sep=comma, x expr=+1, y index=1, skip first n=1] plots/performance/sql/times.csv;

Execution time of programs generated by CodexDB with different instructions and of one traditional DBMS.

Total run time for queries solved by all baselines.

Baseline     2cTime (s)

SF: 1K     SF: 1M

CodexDB: -     3     196

CodexDB: Use pandas library     3     119

CodexDB: Use vaex library     12     240

CodexDB: Use datatable library     2     51

DBMS     1     368

Figure <ref> reports execution time measurements for programs generated with different instructions for the ten first queries. Missing bars indicate that no correct program was generated for the corresponding query. The data sets of the WikiSQL benchmark are too small for meaningful performance measurements. Hence, data were scaled by factor 1,000 and by factor 1,000,000 (by simply duplicating rows). The resulting data sets have an average size of 1.2 GB and 15 million rows. Table <ref> reports total execution time for all of the aforementioned queries for which correct programs were generated for all possible instructions. Clearly, instructing CodexDB to use different libraries has significant impact on performance. This indicates that the generated code is fundamentally different. Finally, time measurements are provided for a traditional, widely used, database management system. To ensure a fair comparison, time measurements include time for loading data from disk, processing the query, and writing the result back to disk (the generated code implements the same tasks). While performance is not the primary goal of CodexDB, the generated code is reasonably efficient.

[group style=group size=1 by 1, ylabels at=edge left, xlabels at=edge bottom, width=8cm, height=3.5cm, legend entries=-,Print “Done.”,Print results,Print progress, legend columns=4, ymode=normal, ymajorgrids, xlabel=Print statements, ylabel=Nr. Programs, legend to name=outputLegend, ylabel near ticks, xlabel near ticks, xtick=data, xticklabels=any, “Done.”, string, variable, ybar, nodes near coords, enlargelimits=0.375, every node near coord/.append style=rotate=90, anchor=west, xshift=-0.1cm, ytick=50, 100, ymax=110]
[title=Davinci-Codex Model, bar width=7pt]
coordinates (0,2) (1,0) (2,0) (3,0);
coordinates (0,100) (1,100) (2,100) (3,0);
coordinates (0,100) (1,0) (2,25) (3,100);
coordinates (0,100) (1,0) (2,100) (3,13);

Number of generated programs containing specific types of print statements for output-related instructions.

Figure <ref> refers to logging-related instructions. The figure shows how many out of 100 generated programs contain certain types of print commands, distinguished by the operand. The figure considers presence of any print commands, commands printing out “Done.”, commands printing hard-coded strings, and commands printing out variables. Without further instructions, only 2% of generated programs contain any print statements. This ratio increases to 100% for any of the logging-related instructions. Instructing CodexDB to print “Done.” after each step is reflected by the presence of corresponding print commands in each program. Instructing CodexDB to print intermediate results ensures that each generated program prints out variables. Requiring progress updates leads to programs printing out hard-coded strings in all (100%) and printing out variables in some (13%) cases. Note that this instruction leaves room for interpretation (as the form of progress updates is not specified). Manual inspection reveals that most generated code includes print commands after each step, outlining the action performed at a high level of abstraction. Figure <ref> from Section <ref> shows a corresponding example.

§ CONCLUSION AND OUTLOOK

CodexDB blurs the line between user and developer. It enables far-ranging customization via natural language commands. Experiments with a first prototype are promising but also hint at significant potential for improvements.

First, CodexDB generates correct code in most but not in all cases (up to 81% of queries are solved, depending on scenario and model). A success rate of 100% is illusory for any kind of natural language interfaces. Still, the newest generation of text-to-SQL methods achieves a precision of more than 90% on the same benchmark. Hence, increasing the precision of CodexDB will be a primary research goal in the near term.

Second, customizing code via natural language instructions works but sometimes in unexpected ways. For instance, given instructions to use specific libraries, CodexDB always imports (“uses”) them indeed. However, in a minority of cases, imported libraries are not ultimately “used” for processing query steps. This motivates stronger mechanisms allowing users to enforce a specific interpretation of their natural language input.

The natural language query planner does not yet use cost-based optimization. This is acceptable for the simple queries of the WikiSQL benchmark. To handle complex queries with many joins, future versions will integrate optimization according to cost models (e.g., based on the number of tuples processed) that have been shown to work quite well across different physical operator implementations <cit.>. Alternatively, machine learning can be used to optimize generated query plans for specific workloads <cit.>.

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

[Brown, Mann, Ryder, Subbiah, Kaplan, Dhariwal,
Neelakantan, Shyam, Sastry, Askell, Agarwal, Herbert-Voss, Krueger, Henighan,
Child, Ramesh, Ziegler, Wu, Winter, Hesse, Chen, Sigler, Litwin, Gray, Chess,
Clark, Berner, McCandlish, Radford, Sutskever, and AmodeiBrown
et al2020]
authorpersonTom B. Brown, personBenjamin
Mann, personNick Ryder, personMelanie Subbiah,
personJared Kaplan, personPrafulla Dhariwal,
personArvind Neelakantan, personPranav Shyam,
personGirish Sastry, personAmanda Askell,
personSandhini Agarwal, personAriel Herbert-Voss,
personGretchen Krueger, personTom Henighan,
personRewon Child, personAditya Ramesh,
personDaniel M. Ziegler, personJeffrey Wu,
personClemens Winter, personChristopher Hesse,
personMark Chen, personEric Sigler,
personMateusz Litwin, personScott Gray,
personBenjamin Chess, personJack Clark,
personChristopher Berner, personSam McCandlish,
personAlec Radford, personIlya Sutskever, and
personDario Amodei. year2020.
Language models are few-shot learners.
journalAdvances in Neural Information Processing
Systems  volume2020-Decem (year2020).

[Chen, Tworek, Jun, Yuan, Pinto, Kaplan,
Edwards, Burda, Joseph, Brockman, Ray, Puri, Krueger, Petrov, Khlaaf, Sastry,
Mishkin, Chan, Gray, Ryder, Pavlov, Power, Kaiser, Bavarian, Winter, Tillet,
Such, Cummings, Plappert, Chantzis, Barnes, Herbert-Voss, Guss, Nichol,
Paino, Tezak, Tang, Babuschkin, Balaji, Jain, Saunders, Hesse, Carr, Leike,
Achiam, Misra, Morikawa, Radford, Knight, Brundage, Murati, Mayer, Welinder,
McGrew, Amodei, McCandlish, Sutskever, and ZarembaChen
et al2021]
authorpersonMark Chen, personJerry Tworek,
personHeewoo Jun, personQiming Yuan,
personHenrique Ponde de Oliveira Pinto, personJared
Kaplan, personHarri Edwards, personYuri Burda,
personNicholas Joseph, personGreg Brockman,
personAlex Ray, personRaul Puri,
personGretchen Krueger, personMichael Petrov,
personHeidy Khlaaf, personGirish Sastry,
personPamela Mishkin, personBrooke Chan,
personScott Gray, personNick Ryder,
personMikhail Pavlov, personAlethea Power,
personLukasz Kaiser, personMohammad Bavarian,
personClemens Winter, personPhilippe Tillet,
personFelipe Petroski Such, personDave Cummings,
personMatthias Plappert, personFotios Chantzis,
personElizabeth Barnes, personAriel Herbert-Voss,
personWilliam Hebgen Guss, personAlex Nichol,
personAlex Paino, personNikolas Tezak,
personJie Tang, personIgor Babuschkin,
personSuchir Balaji, personShantanu Jain,
personWilliam Saunders, personChristopher Hesse,
personAndrew N. Carr, personJan Leike,
personJosh Achiam, personVedant Misra,
personEvan Morikawa, personAlec Radford,
personMatthew Knight, personMiles Brundage,
personMira Murati, personKatie Mayer,
personPeter Welinder, personBob McGrew,
personDario Amodei, personSam McCandlish,
personIlya Sutskever, and personWojciech Zaremba.
Evaluating Large Language Models Trained on

[Gubichev, Boncz, Kemper, and NeumannGubichev
et al2015]
authorpersonAndrey Gubichev, personPeter
Boncz, personAlfons Kemper, and personThomas
Neumann. year2015.
How good are query optimizers, really?
journalPVLDB volume9,
number3 (year2015), pages204–215.

[Houlsby, Giurgiu, Jastrzçbski, Morrone,
de Laroussilhe, Gesmundo, Attariyan, and GellyHoulsby
et al2019]
authorpersonNeil Houlsby, personAndrei
Giurgiu, personStanisraw Jastrzçbski,
personBruna Morrone, personQuentin de Laroussilhe,
personAndrea Gesmundo, personMona Attariyan, and
personSylvain Gelly. year2019.
Parameter-efficient transfer learning for NLP.
journal36th International Conference on Machine
Learning, ICML 2019  volume2019-June (year2019),

[Jain, Vaidyanath, Iyer, Natarajan,
Parthasarathy, Rajamani, and SharmaJain et al2021]
authorpersonNaman Jain, personSkanda
Vaidyanath, personArun Iyer, personNagarajan
Natarajan, personSuresh Parthasarathy, personSriram
Rajamani, and personRahul Sharma.
booktitleJigsaw: Large Language Models meet Program
Synthesis. Vol. volume1.
publisherAssociation for Computing Machinery. 1–12

[Kipf, Kipf, Radke, Leis, Boncz, and
KemperKipf et al2018]
authorpersonAndreas Kipf, personThomas
Kipf, personBernhard Radke, personViktor Leis,
personPeter Boncz, and personAlfons Kemper.
Learned cardinalities: estimating correlated joins
with deep learning. In booktitleCIDR.

[Kraska, Beutel, Chi, Dean, and
PolyzotisKraska et al2017]
authorpersonTim Kraska, personAlex Beutel,
personEd H. Chi, personJeffrey Dean, and
personNeoklis Polyzotis. year2017.
The Case for Learned Index Structures.
number1 (year2017), pages1–30.

[Krikellas, Viglas, and CintraKrikellas
et al2010]
authorpersonKonstantinos Krikellas,
personStratis D. Viglas, and personMarcelo Cintra.
Generating code for holistic query evaluation.
In booktitleICDE. publisherIEEE,

[Li and JagadishLi and Jagadish2014]
authorpersonFei Li and personHV
Jagadish. year2014.
NaLIR: an interactive natural language interface
for querying relational databases.
journalSIGMOD (year2014),

[Li and JagadishLi and Jagadish2016]
authorpersonFei Li and personHV
Jagadish. year2016.
Understanding natural language queries over
relational databases.
journalSIGMOD Record volume45,
number1 (year2016), pages6–13.

[Li, Choi, Chung, Kushman, Schrittwieser, and
LeblondLi et al2022]
authorpersonYujia Li, personDavid Choi,
personJunyoung Chung, personNate Kushman,
personJulian Schrittwieser, and personRémi
Leblond. year2022.
Competition-Level Code Generation with
journalDeepMind Technical Report
(year2022), pages1–73.

[Liguori, Al-Hossami, Cotroneo, Natella, Cukic,
and ShaikhLiguori et al2022]
authorpersonPietro Liguori, personErfan
Al-Hossami, personDomenico Cotroneo, personRoberto
Natella, personBojan Cukic, and personSamira
Shaikh. year2022.
Can We Generate Shellcodes via Natural Language?
An Empirical Study.
journalarXiv:2202.03755v1 (year2022).

[Marcus, Negi, Mao, Zhang, Alizadeh, Kraska,
Papaemmanouil, and TatbulMarcus et al2018]
authorpersonRyan Marcus, personParimarjan
Negi, personHongzi Mao, personChi Zhang,
personMohammad Alizadeh, personTim Kraska,
personOlga Papaemmanouil, and personNesime Tatbul.
Neo: A Learned query optimizer.
journalPVLDB volume12,
number11 (year2018), pages1705–1718.

authorpersonOpenAI. year2021.

[Ruder, Peters, Swayamdipta, and WolfRuder
et al2019]
authorpersonSebastian Ruder, personMatthew E
Peters, personSwabha Swayamdipta, and personThomas
Wolf. year2019.
Transfer Learning in Natural Language
Processing. In booktitleACL: Tutorials.

[Saha, Floratou, Sankaranarayanan, Minhas,
Mittal, and OzcanSaha et al2016]
authorpersonDiptikalyan Saha, personAvrilia
Floratou, personKarthik Sankaranarayanan,
personUmar Farooq Minhas, personAshish R Mittal,
and personFatma Ozcan. year2016.
ATHENA: An ontology-driven system for natural
language querying over relational data stores.
journalVLDB volume9,
number12 (year2016), pages1209–1220.

[Scholak, Schucher, and BahdanauScholak
et al2021]
authorpersonTorsten Scholak, personNathan
Schucher, and personDzmitry Bahdanau.
PICARD: Parsing Incrementally for Constrained
Auto-Regressive Decoding from Language Models.
(year2021), pages9895–9901.

[Sen, Lei, Quamar, Özcan, Efthymiou,
Dalmia, Stager, Mittal, Saha, and SankaranarayananSen
et al2020]
authorpersonJaydeep Sen, personChuan Lei,
personAbdul Quamar, personFatma Özcan,
personVasilis Efthymiou, personAyushi Dalmia,
personGreg Stager, personAshish Mittal,
personDiptikalyan Saha, and personKarthik
Sankaranarayanan. year2020.
ATHENA++: natural language querying for complex
nested SQL queries.
journalProceedings of the VLDB Endowment
volume13, number12 (year2020),

[Shin and Van DurmeShin and Van
authorpersonRichard Shin and
personBenjamin Van Durme. year2021.
Evaluating the Text-to-SQL Capabilities of Large
Language Models.
journalarXiv preprint arXiv:2112.08696

[Suri, Ilyas, Re, and RekatsinasSuri
et al2021]
authorpersonSahaana Suri, personIhab Ilyas,
personChristopher Re, and personTheodoros
Rekatsinas. year2021.
Ember : No-Code Context Enrichment via
similarity-based keyless joins.
journalarXiv:2106.01501v1 (year2021).

[Tang, Fan, Li, Tu, Du, Li, Madden, and
OuzzaniTang et al2021]
authorpersonNan Tang, personJu Fan,
personFangyi Li, personJianhong Tu,
personXiaoyong Du, personGuoliang Li,
personSam Madden, and personMourad Ouzzani.
Rpt: Relational pre-trained transformer is almost
all you need towards democratizing data preparation. In
booktitleProceedings of the VLDB Endowment,
Vol. volume14. pages1254–1261.

[Trummer, Wang, Maram, Moseley, Jo, and
AntonakakisTrummer et al2019]
authorpersonImmanuel Trummer, personJunxiong
Wang, personDeepak Maram, personSamuel Moseley,
personSaehan Jo, and personJoseph Antonakakis.
SkinnerDB: regret-bounded query evaluation via
reinforcement learning. In booktitleSIGMOD.

[Vaswani, Shazeer, Parmar, Uszkoreit, Jones,
Gomez, Kaiser, and PolosukhinVaswani et al2017]
authorpersonAshish Vaswani, personNoam
Shazeer, personNiki Parmar, personJakob Uszkoreit,
personLlion Jones, personAidan N. Gomez,
personŁukasz Kaiser, and personIllia
Polosukhin. year2017.
Attention is all you need.
journalAdvances in Neural Information Processing
Systems volume2017-Decem, numberNips
(year2017), pages5999–6009.

[Wanderman-Milne and LiWanderman-Milne and
authorpersonSkye Wanderman-Milne and
personNong Li. year2014.
Runtime Code Generation in Cloudera Impala.
journalIEEE Data Engineering Bulletin
volume37, number1 (year2014),

[Weir, Crotty, Galakatos, Ilkhechi, Ramaswamy,
Bhushan, Cetintemel, Utama, Geisler, Hättasch, Eger, and BinnigWeir
et al2019]
authorpersonNathaniel Weir, personAndrew
Crotty, personAlex Galakatos, personAmir Ilkhechi,
personShekar Ramaswamy, personRohin Bhushan,
personUgur Cetintemel, personPrasetya Utama,
personNadja Geisler, personBenjamin Hättasch,
personSteffen Eger, and personCarsten Binnig.
DBPal: Weak Supervision for Learning a Natural
Language Interface to Databases.
(year2019), pages1–4.

[Wolf, Debut, Sanh, Chaumond, Delangue, Moi,
Cistac, Rault, Louf, Funtowicz, Davison, Shleifer, von Platen, Ma, Jernite,
Plu, Xu, Le Scao, Gugger, Drame, Lhoest, and RushWolf
et al2020]
authorpersonThomas Wolf, personLysandre
Debut, personVictor Sanh, personJulien Chaumond,
personClement Delangue, personAnthony Moi,
personPierric Cistac, personTim Rault,
personRemi Louf, personMorgan Funtowicz,
personJoe Davison, personSam Shleifer,
personPatrick von Platen, personClara Ma,
personYacine Jernite, personJulien Plu,
personCanwen Xu, personTeven Le Scao,
personSylvain Gugger, personMariama Drame,
personQuentin Lhoest, and personAlexander Rush.
Transformers: State-of-the-Art Natural Language
Processing. In booktitleEMNLP. pages38–45.

[Xuan, Wang, Wang, Wen, and DongXuan
et al2021]
authorpersonKuan Xuan, personYongbo Wang,
personYongliang Wang, personZujie Wen, and
personYang Dong. year2021.
SeaD: End-to-end Text-to-SQL Generation with
Schema-aware Denoising.

[Zhong, Xiong, and SocherZhong
et al2017]
authorpersonVictor Zhong, personCaiming
Xiong, and personRichard Socher.
Seq2SQL: Generating Structured Queries from
Natural Language using Reinforcement Learning.
(year2017), pages1–12.


# How quantum mechanics requires non-additive measures

Gabriele Carcassi  Physics Department, University of Michigan, Ann Arbor, MI
48109  Christine A. Aidala  Physics Department, University of Michigan, Ann
Arbor, MI 48109

###### Abstract

Measure theory is used in physics, not just to capture classical probability,
but also to quantify the number of states. In previous works, we found that
state quantification plays a foundational role in classical mechanics, and
therefore, we set ourselves to construct the quantum equivalent of the
Liouville measure. Unlike the classical counterpart, this quantized measure is
non-additive and has a unitary lower bound (i.e. no set of states can have
less than one state). Conversely, requiring that state quantification is
finite for finite continuous regions and that each state counts as one already
implies non-additivity, which in turn implies the failure of classical theory.
In this article we show these preliminary results and outline a new line of
inquiry that may provide a different insight into the foundations of quantum
theory. Additionally, this new approach may prove to be useful to those
interested in a quantized theory of space-time, as we believe this requires a
quantized measure for the quantification of the independent degrees of
freedom.

##  I Introduction

It is well-established that standard measure theoretic tools cannot be used to
characterize quantum probability as quantum theory is a non-classical (i.e.
non-Kolmogorov) probability theory. To obviate this problem, various
alternatives and extensions to measure theory and probability theory have been
developed with different goals.[1, 2, 3, 4, 5, 6, 7, 8] Our interest in
measure theory, however, is not in its use to capture classical probability.
Measures play another crucial use in physical theories: “counting”, or better
“quantifying”, states. It is this use that will be the focus of this work.

As part of our overall project Assumptions of Physics,[9] we have developed an
approach, called reverse physics,[10] which, starting from the laws, aims to
find a minimal set of physical assumptions needed to rederive them. We found
that the ability to quantify states is a crucial component of classical
theory, so much so that it is enough to recover the structure of phase space
and the laws of evolution.[11, 12] The former (i.e. the symplectic structure)
is the only structure that allows one to quantify states and configurations
over independent degrees of freedom in a way that is frame independent. If one
imposes deterministic and reversible evolution, state quantification must be
preserved, leading to Hamiltonian evolution (i.e. a symplectomorphism). All
elements of classical mechanics, including canonical variables, the Lagrangian
and the action principle, [13] can be rederived and understood in terms of
quantifying the flow of states. Given the formal similarity between classical
and quantum mechanics, we believe a similar approach is possible for the
latter. This raises the question: what is the quantum analogue of the
Liouville measure, the measure that quantifies states in the classical theory?

Statistical mechanics and information theory mandate a link between entropy
and state quantification, as the Shannon/Gibbs entropy over uniform
distributions corresponds to the logarithm of the count of states. In the
quantum case, we can start with the von Neumann entropy and define a measure
that has the same connection. What we find is that this measure is non-
additive and that its features can help us better understand what quantization
is, why it requires both contextuality and the failure of classical
probability, and why the latter can be recovered separately within each
context. Therefore we believe studying this object is useful not only for the
above stated goals of reverse physics, but more in general to get a better
understanding of the foundations of quantum mechanics.

The aim of this article is to propose and articulate the goals of this new
line of research. It provides the overall picture in which future works will
add further mathematical detail and physical insights. In section II we will
show how measure theory is used to quantify elements in a set and how this is
needed to assign probability and probability densities to each element. In
section III we will see how statistical mechanics and information theory
mandate a link between entropy and state quantification, which we will use to
define the quantum analogue of the Liouville measure. We will find that this
measure is not additive.111Technically, measures are defined to be additive,
therefore what we find is not a measure, but a set function. However, this
term is not widespread, so we use the oxymoron “non-additive measure” as it is
customary in the mathematical literature. [14, 15] In section IV we will see
that this non-additivity is linked to non-contextuality. In section V we will
see that quantization means putting a unitary lower bound on the
quantification of states, while keeping a finite value over finite regions. We
will see that this very directly requires non-additivity and therefore non-
contextuality. In section VI we will argue that quantization of space-time
means using a quantized measure on the quantification of degrees of freedom.
Lastly, in section VII we will outline a series of goals for a research
program that aims to fully characterize the quantized measure.

##  II Measure theory and quantifying states

As we said in the introduction, measure theory is not only used to
characterize Kolmogorovian probability. More generally, measures are used to
define the size of sets. Even in probability theory, since probability
measures assign probability to sets of points, in order to associate
probability to individual points one needs two measures: the probability
measure $p:\Sigma_{X}\to\mathbb{R}$ and another measure quantifying the extent
of the set, which we call quantifying measure
$\mu:\Sigma_{X}\to\mathbb{R}$.222Measures assign values to elements of a
$\sigma$-algebra, which can be thought of as a set of experimental procedures.
[9] Since we are interested in physical theories, the measure $\mu$ quantifies
the number of states. Given a set $U$, the ratio $\frac{p(U)}{\mu(U)}$ gives
us the average probability per unit of states. As we shrink $U$ to a single
point $x$, we will find the probability associated to that point, and how this
is done depends on the nature of $\mu$.

In the discrete case, the quantifying measure is simply the counting measure:
the cardinality of the set. Therefore for a single point we simply have
$\frac{p(\\{x\\})}{\mu(\\{x\\})}=\frac{p(\\{x\\})}{1}=p(x)$, which corresponds
to the probability associated to the state $x$. The counting measure is fully
determined by two properties: countable additivity, a defining property of
measures, and that each state counts as one.

In the continuous case, things are a bit different.333Note that “discrete’ and
“continuous” have different meanings depending on context. At a set theoretic
level, “continuum” is associated with the cardinality of a set. In topology,
discrete and continuous spaces are characterized by properties of open sets,
not cardinality: a manifold can be given a discrete topology. In the context
of quantifying measures in physics, discrete means that we can count elements
with natural numbers, while continuous means we use real valued quantities
with units, such as meters for distances, to define the size of regions. If
$X$ is a manifold, a set of local coordinates induce a Lebesgue measure, which
can be used to quantify the number of possible value combinations. Note that a
single state has measure zero, unlike the discrete case. The Lebesgue measure
is defined by two properties: countable additivity and that the size of
parallelepipeds corresponds to the volume expressed by the product of the
differences of coordinates (i.e. $\mu(U)=\Delta x^{1}\Delta x^{2}\@cdots\Delta
x^{n}$). Naturally, this is a problem in physics given that the quantification
of the number of states should be the same in all frames.

However, the structure of classical phase space (i.e. symplectic structure) is
exactly the structure that allows one to define a quantifying measure for
states that is invariant under change of frame.[9, 11, 12] The role of the
quantifying measure in classical mechanics, then, is assigned to the Liouville
measure, which we can understand as a Lebesgue measure on position and
conjugate momentum (i.e. canonical coordinates).444The volume of an
infinitesimal parallelepiped is given by $dq^{1}dq^{2}\@cdots
dp_{1}dp_{2}\@cdots$. Since $dq^{i}$ is contravariant and $dp_{i}$ is
covariant under change of frame, the volume remains the same. As we shrink the
size of the set, $\frac{p(U)}{\mu(U)}$ becomes the Radon-Nikodym derivative
$\frac{dp}{d\mu}$, which gives us the probability density, not the probability
itself.

Quantum mechanics, instead, does not provide a clear state quantifying
measure. When we characterize preparations and measurement outcomes, we may
use the discrete or continuous quantifying measures in different cases for the
same system. For example, consider a particle. If we are interested in a
discrete observable, like the energy level of a harmonic oscillator, we would
use the counting measure; if we are interested in a continuous observable,
like position, we would use the Lebesgue measure associated to the variable.
As for preparations, the same maximally mixed state for a qubit can be written
as a discrete mixture $\frac{1}{2}|0\rangle\langle
0|+\frac{1}{2}|1\rangle\langle 1|$ or as a continuous uniform mixture over all
possible states $\int\frac{1}{4\pi}|\psi\rangle\langle\psi|d\Omega$.

To be precise, the quantifying measures we considered are really on
preparations and measurements, not the states themselves. It was the discrete
or continuous character of the space of preparations that selected the
appropriate space with the appropriate measure. But even if we have different
preparation and measurement spaces, the state space of the system should
always be the same, with a single way to count states. This, in other words,
highlights the problem of quantum probabilities: while the spaces of
preparations and measurement outcomes are both classical, they cannot be
connected by classical means. That is, we cannot simply put a classical
probability of transition between the two because we would be connecting
qualitatively different quantifying measures.

To sum up, the typical foundational question is: how do we generalize
probability measures for quantum mechanics? We are asking something different:
given that state-quantifying measures play an equally fundamental role, how do
we quantify the number of states in quantum mechanics?

##  III Measure theory and quantifying states

While the standard structure of quantum mechanics does not give us an answer
to our question, statistical mechanics and quantum information theory have an
implicit answer. Statistical mechanics tells us that the thermodynamic entropy
of a system, which is a physically meaningful quantity that has numerous
empirical consequences, corresponds to the Shannon entropy for a classical
discrete system, the Gibbs entropy555By Gibbs entropy we mean the differential
Shannon entropy $-\int\rho\log\rho d\mu$ calculated over phase space using
position and momentum (i.e. canonical coordinates). for a classical continuous
system, and the von Neumann entropy for a quantum system.

There is another expression for entropy, often referred to as the fundamental
postulate of statistical mechanics, [16] which is the logarithm of the count
of microstates: $\log\mu(U)$.666Note that the Boltzmann constant is left out,
as entropy will always be expressed in bits or nats. Physically, the Boltzmann
constant is needed to define temperature in Kelvin. Statistical mechanics can
be equivalently formulated in terms of $\beta=\frac{1}{k_{B}T}$.[17] In
classical statistical mechanics, the measure is indeed the quantifying measure
discussed above: the counting measure for the discrete case and the Liouville
volume in the continuous case. The two expressions for entropy are linked as
the Shannon/Gibbs entropy over a uniform distribution matches the logarithm of
the measure of the support. That is, if $\rho_{U}$ is a uniform distribution
over $U$, then $S(\rho_{U})=\log\mu(U)$. In quantum mechanics, as we said
before, we do not have a measure to quantify states. There is, however, a
somewhat related expression: the maximum entropy attainable by a quantum
system corresponding to a Hilbert space $\mathcal{H}$ is the logarithm of the
dimensionality $\dim_{\mathbb{C}}(\mathcal{H})$ of the space. Therefore,
$S(\rho_{U})\leq\log(\dim_{\mathbb{C}}(\text{span}(U)))$.

A similar connection can be established in information theory. The
Shannon/Gibbs/von Neumann entropy quantifies the minimum number of bits
required on average to send a message from a given source.777For a more
general characterization of entropy that works in statistical mechanics,
information theory and other contexts, and a more precise discussion of the
continuous case, see [18]. This, again, is a quantity that leads to empirical
consequences. If we have $n$ bits at our disposal, we have $2^{n}$ possible
combinations, possible messages, that can be encoded. Therefore the logarithm
of the number of potential messages corresponds to the number of bits that can
encode those messages. Physically, we can associate a different state to each
message to be encoded. Therefore $\log\mu(U)$ corresponds to the number of
bits. This will exactly correspond to the number of bits required by a source
characterized by a uniform probability distribution over that number of
symbols.

While the above discussion does not cover all technical details, the only
point we want to make is that the link $S(\rho_{U})=\log\mu(U)$ is fully
justified by both statistical mechanics and information theory. It is not a
capricious request, but rather a necessary requirement stemming not from just
one, but from two disciplines that have empirical consequences. Therefore if
quantum mechanics does not directly provide us with a measure to quantify
states, we can use what it does provide, the von Neumann entropy, to define
and calculate said measure.

We can start by calculating the simplest case, which is when $U=\\{\psi\\}$ is
a single state. In this case, we have $S(|\psi\rangle\langle\psi|)=0$ and
therefore $\mu(\\{\psi\\})=2^{0}=1$. The measure returns one for each state as
in the classical discrete case.

The next case is when $U=\\{\psi,\phi\\}$ is the set of two states. A uniform
distribution over two states will correspond to the mixed state

$\rho=\frac{1}{2}|\psi\rangle\langle\psi|+\frac{1}{2}|\phi\rangle\langle\phi|.$
(1)

The entropy of said state will depend on the probability
$p=|\langle\psi|\phi\rangle|^{2}$ in the following way

$S(\rho)=-\frac{1+\sqrt{p}}{2}\log\frac{1+\sqrt{p}}{2}-\frac{1-\sqrt{p}}{2}\log\frac{1-\sqrt{p}}{2}.$
(2)

If the states are orthogonal, then $p=0$, and $S(\rho)=1$ therefore
$\mu(U)=2^{1}=2$. In this case we have that
$2=\mu(\\{\psi,\phi\\})=\mu(\\{\psi\\})+\mu(\\{\phi\\})=1+1$, and therefore
$\mu$ is additive. Moreover, if $U$ is an orthonormal basis, the von Neumann
entropy $S(U)=\log(\dim_{\mathbb{C}}(\text{span}(U)))=\log|U|$ is the
logarithm of the cardinality of $U$. Therefore the quantifying measure
$\mu(U)=|U|$ is equal to the counting measure. But this is a special case that
corresponds to the highest entropy reachable with a mixture. In all other
cases the entropy will be lower, and therefore, in general,
$\mu(\\{\psi,\phi\\})\leq\mu(\\{\psi\\})+\mu(\\{\phi\\})$. In other words, the
measure $\mu$ is not additive.

To sum up, the physically motivated way to quantify the number of states in
quantum mechanics is, in general, not additive. When counting states in
quantum mechanics, $1+1\leq 2$.

##  IV Non-additivity and contextuality

While unusual claims are common in quantum mechanics, we want to have a clear,
physically tenable, reason as to why the quantifying measure for quantum
states must be non-additive. In the context of a spin 1/2 system, for example,
why is it that $\\{|z^{+}\rangle,|z^{-}\rangle\\}$ count as two states while
$\\{|z^{+}\rangle,|x^{+}\rangle\\}$ count as less than two?

Since we saw that the quantifying measure is indeed additive for a set of
orthogonal states, this should make us think about contextuality: the
impossibility to assign outcomes to all potential measurements of a quantum
system. We have, in fact, derived that it is impossible to define an additive
quantifying measure on all potential states, but we can do so on the outcomes
of one measurement. The ability/inability to define additive measures is
exactly the difference between classical/non-classical probability.

While contextuality is often presented as a somewhat abstract, almost
metaphysical, property of quantum mechanics, we have a rather more down-to-
earth view. The choice of the measurement means a difference in physical
process of either the preparation or measurement device. Choosing which
direction of spin to prepare or measure means, at some point, orienting some
polarizer, magnetic field or making an equivalent change to a physical device.
Something is changed in the physical world, not just in the system, but around
the system, in its environment. If Amanda claims that a particle is in the
$|z^{+}\rangle$ state, then Boris is able to infer something about Amanda’s
preparation/measuring device.888This is not at all particular to quantum
mechanics. We can study the motion of a cannonball here on earth, but not on
the surface of the sun, as the cannonball would be immediately vaporized. The
mere claim that a system exists implies that the boundary conditions necessary
for that system to exist are satisfied. In this sense, all physics is
contextual. Therefore we can understand the context simply as those conditions
on the environment that are necessary for the system to be found in that
particular state. A set of orthogonal states, then, has the property that they
can be found in the same external conditions.

Given that we have, in general, a correlation between system and environment,
it is natural to understand how contextuality leads to a non-additive measure.
Two states, in fact, should be counted as two only if they lead to a change in
the system alone. That is, states should be quantified all-else-being-equal.
While two states from different contexts are indeed two distinct states,
stating we transitioned from one to the other does not give us information
only about the system: it tells us something about the environment as well.
The degree of incompatibility of observables, then, ultimately measures the
degree of change when realizing the context physically.

So we have a clear, physically motivated reason as to why contextuality is
linked to a non-additive measure. States should be quantified at-all-else-
being-equal, meaning that possible correlations with the environment have to
be removed.

##  V Non-additivity and quantization

While we have clarified what it means for the quantifying measure to be non-
additive, and how this is tied to non-contextuality, we haven’t shown why it
should be linked to quantization. In fact, what exactly is quantization?

Before trying to answer that question, let’s make a direct comparison between
the quantifying measures for the three cases: the counting measure $\mu_{d}$
for the classical discrete case, the Liouville measure $\mu_{c}$ for the
classical continuous case and the newly defined quantized measure $\mu_{q}$
for the quantum case. This requires a space where all three can be defined,
which fortunately exists: the surface of a sphere. First, we want to compare
the behavior on a single point. The counting measure returns one, and so does
the quantum measure. The Liouville measure, however, returns zero. Second, we
want to compare the behavior on a finite region, an open set. The Liouville
measure returns the solid angle, which is always going to be finite as it must
be less than or equal to $4\pi$. The von Neumann entropy of a mixed state over
a two-state system is between zero and one, and therefore the measure must be
between one and two. However, given that an open set on a sphere has
infinitely many points, the counting measure over a finite region will be
infinite. Lastly, we want to compare the additivity. Both classical measures
are additive, while the quantum measure is not.

Let us list the three properties we have mentioned:

  1. 1.

single states count as one

  2. 2.

finite continuous regions correspond to finite state quantification

  3. 3.

state quantification is additive on disjoint regions.

These seem very reasonable properties to assume for a quantifying measure of
states. However, these three conditions are incompatible. If each state counts
as one, and the measure is additive, then a finite continuous region must be
infinite as it contains infinite points. Of the three conditions, we can only
pick two. This is, in fact, what each measure does. The counting measure
rejects the second property. The Liouville (and Lebesgue) measure discards the
first. The quantum measure sacrifices the third.

So, in light of this, what is quantization? If we have a system characterized
by continuous quantities, such as position, the state space will necessarily
be a continuous space and finite regions will have to correspond to finite
information as those correspond to the finite precision measurements we can
make.999For a treatment of how finite-time experimental verification is
captured by topological concepts, and what necessary and sufficient
operational assumptions are required for the use of real valued quantities,
see [19, 9]. If the regions are large enough, the Liouville (or Lebesgue)
measure will work. But as we shrink a region we will encounter, given the
additivity, regions that contain less than one state, which does not make
sense. Note that measure less than one corresponds to negative thermodynamic
entropy, which does not make sense either.

Quantization, then, is fixing the quantifying measure so that it is bounded
from below by one (and the entropy by zero): each state counts as one.
However, this comes at a price: non-additivity. This non-additivity is
ultimately why classical probability has to fail as well, given that
additivity is one of its axioms. It is also the same reason as why
quantization implies contextuality: the non-additivity means that some states
cannot be prepared at-all-else-being-equal.

In our view, this provides a good conceptual basis to understand the failure
of classical mechanics, the need for the departure from classical ideas and
the need for quantum theory. We believe this, by itself, is already sufficient
reason to start a research program to explore these ideas fully. However,
since most physicists do not seem to be interested in this type of “clean-up
work”, we can easily argue that a full characterization of the quantized
measure is critical for the development of future physical theories.

##  VI Implication for space-time quantization

We have seen that quantization can be understood as putting a unitary lower
bound on the state quantification: no set of states can have fewer than one
state. If we were to quantize space-time, what is it that we are quantizing?

The most fundamental theories that are available to us are field theories. In
a field theory, the state is described by the value of the fields at each
point in space. At each point, the value of the field is independent from the
others: the degrees of freedom form a continuum.101010If we restrict ourselves
to continuous fields, then we only need to specify the value of the fields on
a countable dense subset (i.e. rational values of the coordinates). However,
these details do not change the discussion: a Lebesgue measure on the
rationals has the same characteristics as the one extended to the reals. We
can therefore pose the question: how do we quantify the degrees of freedom?

If we have a region of space and we double the volume, we can imagine we are
also doubling the number of degrees of freedom. Therefore, we can construct a
volume measure from the metric tensor, which would give us an invariant volume
that quantifies degrees of freedom, much in the same way that the Liouville
measure quantified states.

Since the measure is finite for finite regions and is additive, as we shrink
the region, we will find regions with less than one degree of freedom. This
does not make sense. As before, we need to put a unitary lower bound on the
measure and our measure cannot be additive. We need a quantized measure.
Quantizing space-time, then, means putting a quantized measure on the number
of degrees of freedom.

What does it mean that two degrees of freedom count less than two? Before
answering that question, let’s consider time. We said that if we double the
spatial volume, we double the number of degrees of freedom. Suppose we have a
space-time region and we double the time, are we doubling the number of
degrees of freedom? Well, we are certainly doubling the support of the
function we have to specify for the field configuration, but we wouldn’t
consider that doubling the degrees of freedom. Intuitively, we just think of
those as being the same degrees of freedom that are getting different values
in time. This is because we expect the future and past values to be linked by
some dynamical equations, so the future values would be linked, in some way,
to the past values. That is, the past and future value of the same field at
some point are not independent. This may give us an insight into the physical
meaning of the non-additivity of quantification of the number of degrees of
freedom.

The same field at two spatial points may count less than two degrees of
freedom simply because their values are not independent. The values of the
field at two distant points can be chosen arbitrarily, therefore the measure
would be additive at long range. But as the points get sufficiently close,
this would not be the case, so at short scale we need a quantized measure to
quantify independent degrees of freedom. Note that the lack of independence of
the field values in close-by regions may mean that high frequencies of the
fields are damped: the values have to become closer. A quantized measure of
the degrees of freedom would effectively provide a cutoff. Therefore we have a
story that is very well motivated and provides a possible solution for high
energy divergences in quantum field theories.

While the development of a quantum theory of gravity is not our primary
interest, the mathematical tools required to characterize the non-additive
quantized measure seem to be of similar nature as the ones that may be used to
quantize space-time.

##  VII Open questions and future work

Having outlined the scope and motivation for this new approach, we now outline
the main questions we think need to be addressed by this new research program.

Both the counting measure and the Lebesgue/Liouville measures are unique in
some sense. For the counting measure, once we define the value for a single
point, typically one, the whole measure is determined. Similarly, once we have
defined a real variable, the Lebesgue measure is determined. The Liouville
measure requires a bit more structure, but once the canonical coordinates are
chosen, the measure is determined as well. Therefore the first question is
whether these quantized measures are also unique in some sense.

While we have found some literature on non-additive measures and set functions
[5, 15], together with modified theories of integration, these seem to
concentrate on monotonic measures: measures that increase as the set
increases. Unfortunately, the quantized measure does not have this feature.
Consider the set $\\{|z^{+}\rangle,|z^{-}\rangle\\}$. An equal mixture will
return the maximally mixed state which, as we said, would correspond to a
measure equal to 2. Now consider the set
$\\{|z^{+}\rangle,|z^{-}\rangle,|x^{+}\rangle\\}$. An equal mixture of them
will not correspond to the maximally mixed state, and therefore the measure
will be less than two. The set is bigger, but the measure is smaller.
Therefore there may be new mathematical ground to be explored.

We may want to understand the necessary conditions for a quantifying measure.
Some may be derived from the strict concavity of entropy, given the connection
between the two. Furthermore, note that the pairwise relationships between the
measure over two points, the entropy of the equal mixture of two states and
the probability of transition between two states are all invertible. This
means that the relationship between two states defines the geometry of the
whole state space. Therefore there must be further consistency requirements
that can be identified.

Another issue that needs to be understood is how the quantized measure behaves
in composite systems and across multiple degrees of freedom. In the classical
case, the measure is defined on the product of the corresponding
$\sigma$-algebras. Ideally, we would like to show that this simple procedure
cannot support a quantized measure, and the $\sigma$-algebra of the tensor
product must be taken.111111Technically it would be the $\sigma$-algebra
projective space coming from the tensor product of the Hilbert spaces
associated with the individual systems.

The first spaces we should study are the symplectic ones as these are the ones
that allow for frame independent densities. If we want to extend to a
quantization of space-time, however, Riemannian spaces need to be studied as
well. However, we have found a connection between the two: if the symplectic
form is expressed in position and velocity, instead of canonical coordinates,
its position-velocity component corresponds to the metric tensor. The metric
tensor can then be understood as defining volumes in position-velocity instead
in position-momentum. This may allow us to transfer the quantized measure onto
the tangent bundle and then, hopefully, to the space itself.

Finally, we want to stress that, contrary to what happens in other programs,
the physical motivations for the mathematical generalization are tightly
driven by the physics. We are not introducing concepts that, like negative
probability, have no clear direct physical meaning. The goal is the
quantification of states.

##  VIII Conclusion

We have seen that, in physics, measure theory is not only used to characterize
classical probability but also to quantify states in state spaces. Ideally,
such a measure would have the following three conditions:

  1. 1.

single states count as one

  2. 2.

finite continuous regions correspond to finite state quantification

  3. 3.

state quantification is additive on disjoint regions.

However, these conditions are not compatible, and only two of the three can be
chosen. The classical discrete case discards the second; the classical
continuous case discards the first; the quantum case discards the third.
Quantization, then, can be understood as putting a unitary lower bound on the
measure that quantifies states.

The lack of additivity on the whole space makes it impossible to use classical
probability on the state space as a whole. Physically, the issue is that
states must be counted at-all-else-being-equal, a feature broken by
contextuality. But if the states do belong to the same context (e.g. they are
the output of the same measurement), additivity is recovered. This tells us
very directly why quantization requires contextuality, and why classical
probability works within the same context. The fact that single states and
finite continuous regions both have finite measure also tells us why quantum
mechanics mixes features of the classical discrete and continuous cases.

We believe that further study and characterization of the non-additive
quantized measure will not only bring more clarity to the interplay among the
above concepts, but it may be necessary for the development of future physical
theories. Given that, in a field theory, the number of independent degrees of
freedom is taken to be proportional to the spatial volume, quantization of
space-time can be understood as the quantization of the measure that
quantifies the independent degrees of freedom. The development of physically
motivated mathematical tools may help in that regard.

## Acknowledgments

This paper is part of the ongoing Assumptions of Physics project [9], which
aims to identify a handful of physical principles from which the basic laws
can be rigorously derived. This article was made possible through the support
of grant #62847 from the John Templeton Foundation.

## References

  * Groenewold [1946] H. J. Groenewold,  _On the principles of elementary quantum mechanics_ (Springer, 1946).
  * Moyal [1949] J. E. Moyal, Quantum mechanics as a statistical theory, in  _Mathematical Proceedings of the Cambridge Philosophical Society_ , Vol. 45 (Cambridge University Press, 1949) pp. 99–124.
  * Gleason [1957] A. M. Gleason, Measures on the closed subspaces of a Hilbert space, Journal of Mathematics and Mechanics 6, 885 (1957).
  * Sorkin [1994] R. D. Sorkin, Quantum mechanics as quantum measure theory, Modern Physics Letters A 9, 3119 (1994).
  * Hamhalter [2003] J. Hamhalter,  _Quantum measure theory_, Vol. 134 (Springer Dordrecht, 2003).
  * Gudder [2009] S. Gudder, Quantum measure and integration theory, Journal of Mathematical Physics 50 (2009).
  * Svozil [2022] K. Svozil, Extending Kolmogorov’s axioms for a generalized probability theory on collections of contexts, Entropy 24, 1285 (2022).
  * Monchietti  _et al._ [2023] E. Monchietti, C. Massri, J. A. de Barros, and F. Holik, Measure-theoretic approach to negative probabilities, arXiv preprint arXiv:2302.00118 (2023).
  * Carcassi and Aidala [2021] G. Carcassi and C. A. Aidala,  _Assumptions of Physics_ (Michigan Publishing, 2021).
  * Carcassi and Aidala [2022] G. Carcassi and C. A. Aidala, Reverse physics: From laws to physical assumptions, Foundations of Physics 52, 1 (2022).
  * Carcassi and Aidala [2020] G. Carcassi and C. A. Aidala, Hamiltonian mechanics is conservation of information entropy, Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 71, 60 (2020).
  * Hunt  _et al._ [2023] J. Hunt, G. Carcassi, and C. Aidala, Hamiltonian privilege, Erkenntnis , 1 (2023).
  * Carcassi and Aidala [2023] G. Carcassi and C. A. Aidala, Geometric and physical interpretation of the action principle, Scientific Reports 13, 12138 (2023).
  * Denneberg [1994] D. Denneberg,  _Non-additive measure and integral_ , Vol. 27 (Springer Science & Business Media, 1994).
  * Torra  _et al._ [2014] V. Torra, Y. Narukawa, and M. Sugeno,  _Non-Additive Measures: Theory and Applications_ , 1st ed. (Springer International Publishing, 2014).
  * Peliti [2011] L. Peliti,  _Statistical Mechanics in a Nutshell_ (Princeton University Press, Princeton, 2011).
  * Chyla [2011] W. Chyla, Evolution of the International Metric System of Units SI, Acta Physica Polonica, A. 120, 998 (2011).
  * Carcassi  _et al._ [2021] G. Carcassi, C. A. Aidala, and J. Barbour, Variability as a better characterization of Shannon entropy, European Journal of Physics 42, 045102 (2021).
  * Kelly [1996] K. T. Kelly,  _The Logic of Reliable Inquiry_ (Oxford University Press, 1996).