Work and critical paths in a fixed task graph [ftip-00MF]
✍️source

    When the tasks, dependencies, and durations are fixed, scheduling has a useful lower bound independent of the chosen priority rule. This isolates avoidable delay in a declared decomposition. Discovering a missing dependency or changing a mathematical formulation changes that decomposition and is a different intervention.

    The following work-and-chain argument is the classical list-scheduling bound associated with Graham. His examples also show that a particular list schedule can worsen after an apparently favorable change, such as adding processors. This does not contradict monotonicity of the optimal feasible frontier.

    proposition. A work and critical-path bound for list scheduling [ftip-00MG]

      Fix a finite nonempty directed acyclic task graph, positive task durations \(p_j\), and \(m\) identical processors, where \(m\in \mathbb N\) and \(m\geq 1\). All tasks are available at time zero subject only to their precedence constraints. Each task uses one processor without interruption; there are no further resource, communication, or setup constraints. Let \(W=\sum _j p_j\), let \(D\) be the longest precedence-chain duration, and let \(T^*\) be the minimum makespan. A work-conserving list schedule starts a ready task whenever a processor is free. Its makespan \(T_{\mathrm {list}}\) satisfies

      \[ \max (W/m,D)\leq T^*\leq T_{\mathrm {list}} \leq W/m+(1-1/m)D. \]\[ T_{\mathrm {list}}\leq (2-1/m)T^*. \]

      Proof. 

        At most \(m\) units of work can finish per unit time, and every precedence chain executes in order. Thus \(W/m\leq T^*\) and \(D\leq T^*\). Trace backwards from a last-finishing task, repeatedly choosing an immediate predecessor with latest completion, until reaching a task with no predecessors. These tasks form a precedence chain.

        Between completion of one chosen predecessor and the next chain task's start, all predecessors of that next task are complete. The task is ready, so work conservation forces all processors to be busy during that gap. The first chain task is ready from time zero. Consequently, whenever fewer than \(m\) processors are busy before completion, some task on this chain is executing, apart from finitely many event times.

        Let \(I\) be the total duration with fewer than \(m\) busy processors. Then \(I\leq D\). During the rest of the schedule all \(m\) processors are busy, and during \(I\) at least one is busy. Hence

        \[ W\geq m(T_{\mathrm {list}}-I)+I. \] \[ T_{\mathrm {list}}\leq W/m+(1-1/m)I \leq W/m+(1-1/m)D. \]

        The lower bounds on \(T^*\) give the last inequality in the statement.

        The ratio \(T_{\mathrm {list}}/\max (W/m,D)\) compares the schedule with a lower bound that need not be attainable; it is not generally the ratio to the optimum. Communication and verification must be modeled as work with constraints satisfying these assumptions, or the displayed upper bound need not apply. Neither bound certifies the quality of the chosen task graph or an unrestricted agent's attainable output quality.

        Context

          Finite coordination under hard budgets [ftip-00M3]

            A harness chooses which computation to run, what to retain, and when to stop. To bound the quality attainable by these choices, one must specify both the permitted actions and the information available after each action. A bound on one scheduler does not yet bound all controllers using the same workers.

            Finite decision models make this distinction explicit. They connect Definition [ftip-00CJ]'s resource admission rule to the attainable-quality frontier of Definition [ftip-00JJ]. Computation selection as information acquisition is studied by Hay, Russell, Tolpin, and Shimony. Here a hard horizon is imposed as a separate assumption; almost-sure stopping or finite expected cost would not supply such a horizon.

            Histories, admissible actions, and retained information [ftip-00M4]

              The controller may use its entire observed history. A smaller state can help compute a bound, but its sufficiency must be justified across the histories it represents. The examples below separate information that is valuable only in combination from information lost by a summary.

              Definition. Finite controller class with hard resource admission [ftip-00M5]

                Fix a horizon \(H\in \mathbb N\), finite nonempty observed-history sets \(\mathcal H_t\) for \(0\leq t\leq H\), an initial law \(\mu \) on \(\mathcal H_0\), and finite nonempty permitted-action sets \(A_t(h)\) for \(t<H\). An environment kernel \(K_t(\cdot \mid h,a)\) is a probability law on histories extending \(h\) by action \(a\) and its observed outcome. The initial law and all kernels are fixed before choosing a controller.

                A controller \(\pi \) assigns a probability law \(\pi _t(\cdot \mid h)\) on \(A_t(h)\). It may depend on every observed component of \(h\), including retained traces, generated programs, and previous updates. Random choices may be recorded in the history. The class \(\Pi (\mathbf B)\) consists of all such controllers under the declared hard resource vector \(\mathbf B\in \mathbb R_+^m\). It does not require a fixed prompt, a memoryless policy, or independent worker outputs. Full-history access is allowed in this mathematical class; it may enlarge the class of executable controllers with limited memory or computation.

                Each history records accumulated nonnegative cost \(\mathbf c(h)\preceq \mathbf B\). Every permitted non-stop action has a declared worst-case increment \(\bar {\mathbf c}_t(h,a)\) satisfying

                \[ \mathbf c(h)+\bar {\mathbf c}_t(h,a)\preceq \mathbf B. \]

                Every successor in the kernel's support must have realized increment between zero and this declared bound, componentwise. Proposal work, controller computation, worker calls, communication, verification, failed attempts, and persistent updates must be included in whichever resource coordinates are bounded; the units remain those of Definition [ftip-005H]. This is the enforced-contract assumption of Theorem [ftip-00CK].

                A stop action is always permitted: it commits the current terminal artifact and pads the remaining steps with no further cost or change in its evaluated quality. At the horizon a fixed evaluator assigns \(q(h_H)\in [0,1]\) to the committed artifact recorded in the terminal history. If the evaluator has random outcomes, include them in the history law. Evaluation work must be charged before the zero-cost padding begins. Define

                \[ J(\pi )=\mathbb E_\pi [q(h_H)], \qquad V(\mathbf B)=\sup _{\pi \in \Pi (\mathbf B)}J(\pi ). \]

                The artifact identity, evaluator, observations, kernels, and action sets are part of the mathematical problem. A training procedure or new tool belongs to this frontier only if it is among the permitted actions and its effects and costs are represented. Finiteness is an explicit restriction on histories, representations, and horizon; a theorem for this class does not bound an unrestricted agent that can extend them.

                For an executable system, an upper bound applies only after its observations, actions, outcomes, and charged costs are represented by this model. Conversely, a mathematical policy supplies an executable lower bound only when it has an implementation respecting the stated resource cap; an arbitrary history-to-action table does not establish that fact.

                Example. Complementary observations defeat one-step information value [ftip-00M6]

                  Let \(X,Y\) be independent uniform bits. The terminal artifact is a guess for \(X\mathbin \oplus Y\); its quality is one if correct and zero otherwise. Two observation actions reveal \(X\) and \(Y\), respectively, at cost \(c\) each, where \(0<c<1/4\). The hard budget permits both observations. A terminal guess requires no additional observation cost.

                  Without observations, the best expected quality is \(1/2\). Given only \(X\), the unrevealed bit \(Y\) remains uniform, so the best expected quality is still \(1/2\); the same holds with \(X,Y\) exchanged. Thus a rule that compares stopping with taking one observation and then stopping assigns either observation net value \(1/2-c<1/2\). It stops immediately.

                  Observing both bits determines their parity. Its expected quality is one and its quality minus observation cost is \(1-2c>1/2\). Hence neither zero one-step information value nor a myopic stopping decision certifies the full controller frontier. This is a finite calculation, not an empirical claim about a language model. The scalar cost penalty is used only to exhibit the myopic decision; the hard-budget quality frontier itself is defined in Definition [ftip-00M5].

                  Example. Erasing an observed bit changes the attainable frontier [ftip-00M7]

                    An initial observation reveals a uniform bit \(Z\). The terminal action is a bit \(a\), and quality is \(q=\mathbf 1\{a=Z\}\). Both actions are permitted at either history and have the same cost. A full-history controller chooses \(a=Z\) and attains quality one.

                    Now restrict the controller's entire input to a summary that is constant at the two initial histories. Its private randomness is independent of \(Z\). If it chooses one with probability \(p\), its expected quality is \(p/2+(1-p)/2=1/2\). No such summary controller can do better.

                    A model that averages the reward of either fixed action over the two histories obtains \(1/2\). This is the correct summary-controller value, but it underestimates the full-history frontier by \(1/2\). For the history \(Z=a\), the actual reward is one, so the averaged value fails as a reward upper bound at that history. A pointwise reward upper bound must hold at every represented history; agreement only under a tested policy's average history distribution does not establish such a certificate. The loss of an evaluator caveat in Example [ftip-00CU] illustrates why such retained distinctions can matter in a research harness.

                    Upper certificates and remaining potential [ftip-00M8]

                      A feasible controller establishes attainable quality. To bound what other controllers could gain, one also needs an upper bound covering all permitted actions and histories. Bellman inequalities provide such a bound when a state representation has uniform transition and terminal quality guarantees. Their difference measures remaining potential within the declared class.

                      Definition. Uniform abstraction of the finite history model [ftip-00M9]

                        Use the finite controller model of Definition [ftip-00M5]. For each time, choose a finite nonempty state set \(S_t\) and a map \(\phi _t:\mathcal H_t\to S_t\). Require finite nonempty action sets \(A_t(s)\) such that \(A_t(h)=A_t(\phi _t(h))\) at every history. The state retains residual budgets and enough information for the same hard admission rule. The controller still observes the full history.

                        Let \(Q_t(\cdot \mid h,a)\) be the image of the fixed history kernel under \(\phi _{t+1}\), and let \(\widehat P_t(\cdot \mid s,a)\) be a proposed state transition law. Choose finite errors \(\epsilon _t(s,a)\geq 0\) so that, for every permitted history and action,

                        \[ \operatorname {TV}\left (Q_t(\cdot \mid h,a), \widehat P_t(\cdot \mid \phi _t(h),a)\right ) \leq \epsilon _t(\phi _t(h),a), \qquad \operatorname {TV}(p,r)=\frac 12\sum _x|p(x)-r(x)|. \]

                        This condition includes histories unvisited by a chosen policy: the kernel there is part of the model. For finite functions \(\widehat q:S_H\to \mathbb R\) and \(e_H:S_H\to \mathbb R_+\), require

                        \[ q(h_H)\leq \widehat q(\phi _H(h_H))+e_H(\phi _H(h_H)) \quad \text {for every }h_H\in \mathcal H_H. \]

                        Write \(\nu (s)=\mu \{h:\phi _0(h)=s\}\) for the initial state law. Low average prediction error on sampled histories does not establish these uniform inequalities. The erased-bit example in Example [ftip-00M7] shows why policy-relevant information cannot simply be averaged away.

                        Theorem. A robust Bellman upper bound for every permitted controller [ftip-00MA]

                          Under Definition [ftip-00M9], let finite functions \(W_t:S_t\to \mathbb R\) satisfy \(W_H(s)\geq \widehat q(s)+e_H(s)\) and, for every \(t<H\), \(s\in S_t\), and \(a\in A_t(s)\),

                          \[ W_t(s)\geq \sum _{s'\in S_{t+1}}\widehat P_t(s'\mid s,a)W_{t+1}(s') +\epsilon _t(s,a)\operatorname {span}(W_{t+1}). \]

                          Here \(\operatorname {span}(f)=\max f-\min f\). Every permitted history-dependent randomized controller then satisfies

                          \[ J(\pi )\leq U:=\min \left (1,\sum _{s\in S_0}\nu (s)W_0(s)\right ). \]

                          For any feasible controller \(\pi _0\) with a justified finite lower bound \(L\leq J(\pi _0)\), the frontier of Definition [ftip-00M5] obeys

                          \[ L\leq J(\pi _0)\leq V(\mathbf B)\leq U, \qquad 0\leq V(\mathbf B)-J(\pi _0)\leq U-L. \]

                          Proof. 

                            For finite probability laws \(p,r\), subtract \(\min f\) from \(f\). The sum of the positive entries of \(p-r\) is \(\operatorname {TV}(p,r)\); dropping its negative entries gives

                            \[ \sum _x(p(x)-r(x))f(x)\leq \operatorname {TV}(p,r)\operatorname {span}(f). \]

                            Fix any controller. At time \(H\), terminal domination gives \(q(h_H)\leq W_H(\phi _H(h_H))\). Suppose that, from every next history, its expected terminal quality is bounded by \(W_{t+1}\) of the next state. For each current history and permitted action, the fixed kernel, this inductive inequality, and the total-variation bound give

                            \[ \mathbb E_\pi [q(h_H)\mid h_t=h,a_t=a] \leq \sum _{s'}Q_t(s'\mid h,a)W_{t+1}(s') \leq W_t(\phi _t(h)). \]

                            At a history with zero probability under the controller, interpret the continuation expectation using its specified future decisions and the fixed kernels. Thus the induction holds at every history. Averaging over the controller's action randomization preserves the inequality. Backwards induction and averaging over \(\mu \) give the bound \(\sum _s\nu (s)W_0(s)\). The independent bound \(q\leq 1\) permits clipping at 1. If \(H=0\), terminal domination alone gives the same conclusion. Taking the supremum over controllers and using \(L\leq J(\pi _0)\) proves the remaining inequalities.

                            A numerical supersolution is a certificate only after all of its inequalities and the abstraction hypotheses are justified. If the model bounds hold jointly with probability at least \(1-\delta _M\) and the lower bound with probability at least \(1-\delta _E\), the bracket holds with probability at least \(1-\delta _M-\delta _E\) by a union bound. Each coverage statement must apply to the selected model or policy; no independence between the two events is required.

                            Remark. Exact occupation flows and expected-cost relaxations [ftip-00MB]

                              Suppose the abstraction is exact: \(Q_t(\cdot \mid h,a)= P_t(\cdot \mid \phi _t(h),a)\) for all histories and actions, and terminal quality is exactly \(q(h_H)=r(\phi _H(h_H))\). A one-sided terminal bound with zero error would not imply this equality. Retain the exact legal actions and hard-budget state from Definition [ftip-00M9].

                              Introduce nonnegative state masses \(z_t(s)\) and action masses \(x_t(s,a)\), with \(z_0=\nu \). For \(0\leq t<H\), impose

                              \[ \sum _{a\in A_t(s)}x_t(s,a)=z_t(s), \qquad z_{t+1}(s')=\sum _{s\in S_t}\sum _{a\in A_t(s)} x_t(s,a)P_t(s'\mid s,a). \]

                              The linear program maximizes \(\sum _s z_H(s)r(s)\). Every full-history controller induces these flows because the next-state law given a state and action is exact. Conversely, at positive mass choose action \(a\) with probability \(x_t(s,a)/z_t(s)\); at zero mass choose any legal action. Induction on time reproduces the flows in the original history model. Hence the LP optimum equals its mathematical controller frontier. For \(H=0\), there are no action flows and the value is \(\nu r\).

                              Set \(W_H=r\) and recurse with \(W_t(s)=\max _{a\in A_t(s)}\sum _{s'}P_t(s'\mid s,a)W_{t+1}(s')\). A maximizing action exists by finiteness and gives a policy attaining \(\nu W_0\); the Bellman upper bound gives the reverse inequality. This proves equality with the optimum and exhibits matching lower and upper certificates. It does not establish an efficient implementation of the policy. The flow construction is the scalar finite-horizon specialization of Mifrani and Noll, Section 3; the hard-budget encoding is an additional modeling requirement here.

                              If hard admission is replaced by constraints on expected cost, the resulting program describes a different class. For \(B>0\), a one-step cost equal to \(2B\) or zero with probability \(1/2\) each has expectation \(B\), yet violates cap \(B\) with probability \(1/2\). An expected-cost model can upper-bound the hard-budget frontier only when it is a valid relaxation containing every hard-feasible policy. Its own policies need not respect the realized cap.

                              Corollary. Certified marginal potential under nested budgets [ftip-00MC]

                                Fix the task law, evaluator, initial model, tools, observations, horizon, and intervention class. For \(\mathbf B\preceq \mathbf B'\), assume every controller feasible at \(\mathbf B\) remains permitted at \(\mathbf B'\) with the same outcome law. If a feasible controller at \(\mathbf B\) gives lower bound \(L_{\mathbf B}\) and Theorem [ftip-00MA] gives upper bound \(U_{\mathbf B'}\) at \(\mathbf B'\), then

                                \[ 0\leq V(\mathbf B')-V(\mathbf B) \leq U_{\mathbf B'}-L_{\mathbf B}. \]

                                Proof. 

                                  Feasibility inclusion gives \(V(\mathbf B)\leq V(\mathbf B')\). The lower and upper certificates give \(L_{\mathbf B}\leq V(\mathbf B)\) and \(V(\mathbf B')\leq U_{\mathbf B'}\); subtract to obtain the claim.

                                  If the certified gap is at most \(\varepsilon \), this instantiates Theorem [ftip-00LM]'s conditional saturation statement. An observed plateau alone supplies no such upper certificate. Changing an excluded tool, representation, or training procedure changes the comparison class.

                                  Comparing controllers at fixed worker capability [ftip-00MD]

                                    To isolate coordination, fix the worker checkpoints, tool interfaces, prompt templates, evaluator, task law, and hard resource caps before varying the controller. Useful comparisons include a fixed serial policy, a static worker portfolio, a one-step value-of-information policy, and an adaptive policy that retains the full permitted history. Their allowed observations must agree. A solver that sees hidden outcomes has a different information interface; its optimum supplies an upper bound only through a justified relaxation containing the compared policies.

                                    Use the controls of Definition [ftip-00JV] with controller logic declared as the varying coordinate. If controller-specific tuning is permitted, apply Definition [ftip-00JW]'s equal tuning data, selection, stopping, and cost rules. Compare suprema only within the intervention classes of Definition [ftip-00JX]. A separate factorial comparison can vary the checkpoint and controller independently, distinguishing learned capability, coordination, and their interaction.

                                    Charge proposal and controller work, all parallel worker work, tool and solver use, communication, verification, failures, and retained-state updates using Definition [ftip-005H]. Report elapsed time alongside these costs: a shorter run with more workers may consume more total computation. Apply Definition [ftip-00CJ]'s admission rule before execution and record any contract violation separately from the quality of the submitted artifact.

                                    Finite environments with rational transition laws can expose three distinct mechanisms: complementary observations, correlated worker failures, and delayed verification or newly revealed dependencies. Keep the latent state, observation rules, legal actions, and costs explicit. The first family includes Example [ftip-00M6]; the erased-bit construction in Example [ftip-00M7] tests whether a proposed summary loses decisive information. Where the exact model applies, compare attainable policy values with Remark [ftip-00MB]'s finite optimum and Theorem [ftip-00MA]'s upper certificate.

                                    The principal quantity is the justified interval \([L_{\mathbf B},U_{\mathbf B}]\) for the restricted frontier. A smaller gap can result from a better feasible policy, a sharper upper certificate, or a more informative valid representation; distinguish these causes. In a live system, mean held-out transition accuracy does not justify a uniform model-error radius. Empirical quality and cost remain useful even when an upper certificate is unavailable.

                                    Use evaluation instances separate from tuning, and declare task draws, repetitions, resource checkpoints, and analysis rules before comparison. Repeated runs share an instance and are not automatically independent tasks; account for this grouping in the analysis. Report independently verified quality, feasibility failures, time to the first valid artifact, and charged cost at matched quality. A valid confidence sequence can support repeated inspection under its statistical assumptions; see Howard et al.. It does not by itself justify selecting a new policy on reused evaluation outcomes.

                                    These controls yield testable predictions. Complementary information can favor adaptation over one-step stopping; redundant workers can erase a portfolio's gain; delayed verification can make an early apparent success expensive to repair. An empirical claim of better coordination fails if its advantage disappears after matching access and charging the controller's own work. A claim of little remaining potential additionally requires the upper certificate, not merely a plateau among tested policies.

                                    Work and critical paths in a fixed task graph [ftip-00MF]
                                    ✍️source

                                      When the tasks, dependencies, and durations are fixed, scheduling has a useful lower bound independent of the chosen priority rule. This isolates avoidable delay in a declared decomposition. Discovering a missing dependency or changing a mathematical formulation changes that decomposition and is a different intervention.

                                      The following work-and-chain argument is the classical list-scheduling bound associated with Graham. His examples also show that a particular list schedule can worsen after an apparently favorable change, such as adding processors. This does not contradict monotonicity of the optimal feasible frontier.

                                      proposition. A work and critical-path bound for list scheduling [ftip-00MG]

                                        Fix a finite nonempty directed acyclic task graph, positive task durations \(p_j\), and \(m\) identical processors, where \(m\in \mathbb N\) and \(m\geq 1\). All tasks are available at time zero subject only to their precedence constraints. Each task uses one processor without interruption; there are no further resource, communication, or setup constraints. Let \(W=\sum _j p_j\), let \(D\) be the longest precedence-chain duration, and let \(T^*\) be the minimum makespan. A work-conserving list schedule starts a ready task whenever a processor is free. Its makespan \(T_{\mathrm {list}}\) satisfies

                                        \[ \max (W/m,D)\leq T^*\leq T_{\mathrm {list}} \leq W/m+(1-1/m)D. \]\[ T_{\mathrm {list}}\leq (2-1/m)T^*. \]

                                        Proof. 

                                          At most \(m\) units of work can finish per unit time, and every precedence chain executes in order. Thus \(W/m\leq T^*\) and \(D\leq T^*\). Trace backwards from a last-finishing task, repeatedly choosing an immediate predecessor with latest completion, until reaching a task with no predecessors. These tasks form a precedence chain.

                                          Between completion of one chosen predecessor and the next chain task's start, all predecessors of that next task are complete. The task is ready, so work conservation forces all processors to be busy during that gap. The first chain task is ready from time zero. Consequently, whenever fewer than \(m\) processors are busy before completion, some task on this chain is executing, apart from finitely many event times.

                                          Let \(I\) be the total duration with fewer than \(m\) busy processors. Then \(I\leq D\). During the rest of the schedule all \(m\) processors are busy, and during \(I\) at least one is busy. Hence

                                          \[ W\geq m(T_{\mathrm {list}}-I)+I. \] \[ T_{\mathrm {list}}\leq W/m+(1-1/m)I \leq W/m+(1-1/m)D. \]

                                          The lower bounds on \(T^*\) give the last inequality in the statement.

                                          The ratio \(T_{\mathrm {list}}/\max (W/m,D)\) compares the schedule with a lower bound that need not be attainable; it is not generally the ratio to the optimum. Communication and verification must be modeled as work with constraints satisfying these assumptions, or the displayed upper bound need not apply. Neither bound certifies the quality of the chosen task graph or an unrestricted agent's attainable output quality.