ECM Problem Analysis

Definition of the Problem

To achieve an ECM (Efficient Computation Model), it is essential to demonstrate that the following equality holds true:

$$[ \text{Alg}_1(p \mid C') = { \lambda \mid \lambda \in A' \text{ and } \text{Alg}_2(\lambda)=s' } ]$$

Note: Remember that Alg is an alias for Algorithm

For a deep and thorough understanding of this concept, we must first define the core variables within this context:

1. Action Space:

The action space, denoted as $A$, refers to the comprehensive set of all possible actions abstracted from the framework that can be utilized to solve any given problem. Here, we distinguish three types:

$A$: This denotes all the conceivable actions that can be employed to resolve any problem. In this context, we assume that all problems are solvable using this space.
$A^*$: This refers to the minimal set of actions required to solve a specified problem. Thus, all problems can be solved utilizing this space. Unlike $A$, $A^*$ must be computable and Turing-Complete, ensuring that it can be executed algorithmically.
$A'$: This represents the set of actions contained within a particular approximation to the ECM problem. In this scenario, not all problems can be solved using this space, highlighting its limitations.

2. Action Sequences:

An action sequence, represented by $\lambda$, refers to a specific series of actions used to address and solve a particular problem. We categorize action sequences into three types:

$\lambda$: This denotes the perfect set of actions, representing the ideal combination of steps required to solve a given problem most efficiently.
$\lambda^*$: This refers to an optimal set of actions, which is one possible set of steps that can at least solve the problem, though it may not be the most efficient.
$\lambda'$: This signifies a proposed set of actions generated by an algorithm intended to solve a unique problem. This proposed set does not guarantee that the problem will be solved, indicating potential inefficiencies or gaps in the algorithm.

3. Solutions:

A solution, denoted by $s$, is an abstraction representing the resolution of a problem. We define solutions as follows:

$s$: This is a comprehensive solution that is capable of solving all conceivable problems.
$s^*$: This denotes a solution that is tailored to solve a specific, given problem.
$s'$: This represents a potential solution to a given problem, which is proposed but not assured to be effective or successful.

Summary Table

	Perfect (All Problems)	Optimal (One problem)	Approximation (Could Fail)
Action Space	$$A$$	$$A^*$$	$$A'$$
Sequence	$$\lambda$$	$$\lambda^*$$	$$\lambda'$$
Solution	$$s$$	$$s^*$$	$$s'$$

Note that we will sometimes use $\lambda_n$ for referring to a specific instance of $\lambda$.

Error Abstraction

To design and optimize the problem, we need to compute some form of error to estimate and compare the behavior of the ECM. We analyze the error of the core formula by splitting it into two parts:

Cognition Space: Refers to the planning of the problem, mainly approached using NLP-based Agents.
Execution Space: Refers to the execution of a given plan, approached using a more deterministic framework.

Cognition Space

Suppose we have a problem $p$ and we want to find a sequence of actions $\lambda$ to solve it. The agent faces three main problems:

Planification: Does the agent have the knowledge/capability to solve the problem? The core issue here is the agent's reasoning about the problem and generating an approximation to the problem, independent of the tools available.
Reduction: How can the agent execute its plan with the given tools? The core issue here is reducing the computed actions to those the agent can use in its framework. If the framework lacks necessary tools, this step is impossible without failure.
Translation: How can the agent translate its reasoning into a concrete framework/language? The core issue here is translating natural language reasoning into a programmatic definition.

Execution Space

After planning and reasoning, the steps must be executed to reach a solution. Similar to following a recipe, execution might not go as intended:

Interpretation: There could be differences between the specified plan and runtime execution. For example, the plan might specify "click the first word containing 'A'", which could result in varied interpretations.
Execution: Even ignoring interpretation, the planned step might raise an unforeseen exception, requiring the agent to re-plan.

After having defined each type of error we want to make an abstraction of those errors, so we can analyze how we can make an approximation of them and know what should be improved. Let's see step by step an abstraction of each one:

Planification

$$ Planificate(query) \rightarrow \lambda_1 := [a,b,c,...] \subseteq A \mid Alg_2(\lambda_1) = s $$

Let's break this equation down: The planification step is a function that receives a NL-query $Planificate(query)$ and returns a set of actions $[a,b,c,...]$ referred to as $\lambda_1$. This function must meet two conditions: First, $\lambda_1$ should be a subset of actions in $A$. Second, these actions should be executable to solve the query $Alg_2(\lambda_1) = s$.

Error:

$$error_{plan} = 0 + [s - Alg_2(\lambda_1)] = Alg_2(\lambda) - Alg_2(\lambda_1)$$

For computing the error, we can split the first equation into two parts. First, note that the possible error in $\lambda_1 := [a,b,c,...] \subseteq A$ is $0$ because:

$A$ denotes all the conceivable actions that can be employed to resolve any problem.

So by definition, the set of actions must be a subset of $A$. Then, we can define the error of $Alg_2(\lambda_1)$ by comparing it with its expected value $s$. If the algorithm should return $s$, the error is $s - Alg_2(\lambda_1)$. Note that a solution $s$ can also be defined as the execution of a perfect plan, $Alg_2(\lambda)$, where $\lambda$ is the perfect plan, leading to:

$$error_{plan} = Alg_2(\lambda) - Alg_2(\lambda_1)$$

Reduction

$$Reduce(\lambda_1) \rightarrow \lambda_2 := [x,y,...] \subseteq A^* \mid Alg_2(\lambda_2) = s^*$$

The reduction error is a function that receives a plan (a sequence of NL-actions) and reduces that plan to one where all actions are a subset of $A^*$. Note how we must consider the same conditions as in the planification section.

Error:

$$error_{reduction} = [ \lambda^* - \lambda_2 ] \cup [ Alg_2(\lambda^*) - Alg_2(\lambda_2) ]$$

Following the same reasoning, we split the equation into two parts. First, there could be a gap between the optimal plan $\lambda^*$ and the generated plan $\lambda_2$, possibly due to a poor selection of tools even if planification succeeded. Second, there is the same error as previously: the plan must be executable to be valid. Since the optimal plan $\lambda^*$ is executable, the error of the second part is $Alg_2(\lambda^*) - Alg_2(\lambda_2)$.

Note that the second condition uses $\lambda^*$ instead of $\lambda$ used in the planification step. This is due to the action space $A^*$, where the best solution in an optimal action space is $\lambda^*$ (not the perfect solution $\lambda$). Also, we use $\cup$ notation for joining the errors, since the relationship is not clear.

Translation

$$Translate(\lambda_2) \rightarrow \lambda_3$$

The translation step is a function that receives the reduced plan and generates an equivalent description in the framework that will use that plan. The error in this process arises from the quality loss of the original plan.

Error: $$error_{translation} = \lambda_2 - \lambda_3$$

Defining the error here is straightforward (theoretically). We compare the plan specified in natural language with its programmatic description. If the match is exact, the error is $0$.

Interpretation

$$Interpretate(\lambda_3) \rightarrow \lambda_4 := [x_1, y_1, ...] \subseteq A^*$$

The interpretation step is the reverse of the translation step. It can be seen as an encoding-decoding process, where errors arise from recovering the encoded data without quality loss.

Error:

$$error_{interpretation} = \lambda_3 - \lambda_4$$

Execution

$$Execute(\lambda_4) \rightarrow s_4$$

In the execution function, the next step is not defined, as execution itself is the solution. The error is defined by the framework's capacity to properly run the given steps.

Error:

$$error_{execution} = s_4 - \lambda_4$$

Summary Table

Step	Error
Planification	$$Alg_2(\lambda) - Alg_2(\lambda_1)$$
Reduction	$$( \lambda^* - \lambda_2 ) \cup ( Alg_2(\lambda^*) - Alg_2(\lambda_2) )$$
Translation (Encoding)	$$\lambda_2 - \lambda_3$$
Interpretation (Decoding)	$$\lambda_3 - \lambda_4$$
Execution	$$s_4 - \lambda_4$$