Inferring Logical Forms From Denotations


  • Panupong Pasupat
    Computer Science Department Stanford University
  • Percy Liang
    Computer Science Department Stanford University



  • Computational: number of LF grows exponentially
  • Spurious LF: those LFs happen to get the right denotation





LF (Lambda DCS):



$LF \in Categories = {Set, Rel, Map, (TokenSpan?)}$

Deduction rules works over two categories of LFs, output LF with some other category of LF.

Basic Rules with following forms:


Compositional Rules have the following forms:


Map Category

  • execution of partial LF is sometimes impossible, e.g. $\lambda x.count(x)$
  • partial LF may be complex, e.g. z3

Introduce a map (from set to map, then map to map, finally map back to set)

A map is a pair of a finite unary set u and a binary relation b: (u, b)

Denotaion of $(u, b) = (u)$ is $([u]_w, [b]’_w)$ where $[b]$ is restricted to $[u]$


e.g. $argmax(Position.1st, Index)$

  1. B1 TokenSpan to Set: 1st
  2. B5 Empty to Relation: Position
  3. C1 Set + Rel to Set:
  4. M1 Set to Map:
  5. B5 Empty to Relation: Index
  6. M2 Map + Rel to Map:
  7. M6 Map to Set:

All the LFs of each category c and size s reside in the same $cell(c, s)$.

e.g. Rule C1: Set + Rel to Set may

  • choose $Number.1$ from (Set, 1)
  • choose $Position$ from (Rel, 0)
  • create $Position.Number.1$ to (Set, 0 + 1 + 1 = 2)

up to max size (=7)

After populating each cell, the list of logical forms is pruned to a fixed beam size on model scores.

Beam search may suffer from the propagating errors when the size goes large.

Dynamic Programming on Denotations (DPD)

  • The number of LFs goes exponential but many of them share the same denotation.
  • The number of denotations are much more controlled.

collapse LFs with the same denotation in $cell(c, s, d)$

Two pass algorithm:


  1. Find relevant cell combinations only.
    • One LF per cell and discard others further encountered.
    • Populate cells up to max size
    • Use the cells with correct denotation, collect all rule combinations (cell1, [cell2,] rule) yielding it, combinations of discarded LFs also
  2. Find actual LFs. Use the rule combinations only found before. (98.7% search space are reduced)

without denotation we can do nothing, e.g. testing

Fictitious worlds

Semantically correct LF should give correct denotations in world (table) other than the original one.


  • All entities and relations in Z must be presented in the new fictitious world
  • Columns are the same
  • Resample the cells in each column (with replacement or not)
  • Keep the sorted column sorted



Some LFs got the same denotation across all the fictitious worlds, thus they fall into a equivalence class.


There’re too many fictitious worlds(=30), choose a subset(=5) of them, thus some equivalence classes may fall into the same partition.


Choose a subset that maximize expected information gain (reduction in entropy):


more generated LFs

annotated 252 out of 300 (84%) examples from training set of WikiTableQuestions with LFs.

76% of the first 300 (agianst 53.5% of the first 200, [P and L, 2015]) were generated successfully.



search space is reduced by 98.7%


more LFs generated than Beam search


Fictitious Worlds

30 worlds is enough (5% are different when 300 worlds)

in the 252 annotated examples, 98.3% of spurious LFs are ruled out.

32.7% of 252, only 1 equivalence classes is left. 51.3% of 252, only 3.

Randomly choose 5 worlds (rather than using the information gain)

22.6% and 36.5%.