---
title: "New Figures of Merit for Best-First Probabilistic Chart Parsing"
description: "Before this study, such rankings had rarely been measured or compared. 15 references, cited by 36 papers here."
authors: ["Sharon A. Caraballo", "Eugene Charniak"]
year: 1998
venue: "Computational Linguistics"
source: "https://aclanthology.org/J98-2004/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/caraballo-1998-new-figures-merit-best-first/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/caraballo-1998-new-figures-merit-best-first/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [1998](https://md.research.elamur.ai/free/en/papers/1998/) / New Figures of Merit for Best-First Probabilistic Chart Parsing

# New Figures of Merit for Best-First Probabilistic Chart Parsing

**Authors:** [Sharon A. Caraballo](https://md.research.elamur.ai/free/en/authors/sharon-a-caraballo/) and [Eugene Charniak](https://md.research.elamur.ai/free/en/authors/eugene-charniak/) · **Year:** 1998 · **Venue:** [Computational Linguistics](https://md.research.elamur.ai/free/en/venues/cl/) ([Computational Linguistics 1998](https://md.research.elamur.ai/free/en/venues/cl/1998/)) · **Publisher:** [The MIT Press](https://md.research.elamur.ai/free/en/publishers/the-mit-press/) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/J98-2004/) · [PDF](https://aclanthology.org/J98-2004.pdf) · [OpenAlex](https://openalex.org/W1496659931)

**Citations:** 101 citations (OpenAlex, 2026-10-14) · [36](https://md.research.elamur.ai/free/en/papers/caraballo-1998-new-figures-merit-best-first/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## Summary
Best-first chart parsing speeds up parsing by moving the most promising constituents from the agenda to the chart first. Its efficiency depends on the figure of merit used to rank those constituents. Before this study, such rankings had rarely been measured or compared. The ideal ranking is a constituent's probability given the whole tag sequence, but computing it requires a complete parse, so it can only be approximated.

The authors derive eight approximations from this ideal quantity and test them. The first three use only inside probability (straight β, normalized β, a trigram estimate). Two more add left-context statistics. The last three combine inside probability with statistics on both boundaries of the constituent. Each figure is judged by how much work, counted mainly as created edges, the parser needs to reach 95% of the sentence's probability mass found by exhaustive parsing. A second grammar is used to rule out grammar-specific effects.

A cheap figure called boundary trigram wins on every measure and with both grammars. This gives practical guidance for building fast probabilistic parsers.

## Key points
- The main grammar is a PCFG learned from the Brown corpus, with about 5,000 rules over 32 terminal and nonterminal symbols. It is tested on 500 Penn Treebank Wall Street Journal sentences of 3–30 tokens, parsed from tags only, with no lexical information.
- Four measures are used: share of exhaustive-parse edges (%E), share of non-zero-length edges, share of popped constituents, and total CPU time. As a baseline, a non-best-first "stack" parser needs 4,882 seconds to fully parse the test set, and long sentences can generate up to 130,000 edges.
- Straight β favours short constituents, which causes "thrashing." In recall terms it is barely better than the stack parser, and both need about 50,000 edges to reach maximum recall.
- The test grammar caps precision at about 47% and recall at about 64%. With boundary trigram, the parser reaches that recall ceiling in under 2,000 edges, while the closest competitors need around 3,000.
- Appendices cover three topics: on-line computation of inside probability, how the boundary statistics were collected, and speed-versus-accuracy curves.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [Brown University](https://md.research.elamur.ai/free/en/universities/brown-university/) — University, Providence, United States · 76 works · 25,952 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 16,667 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 16,194 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 16,039 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 15,891 works

🧭 Topics (1): [📐 Syntax & grammar formalisms](https://md.research.elamur.ai/free/en/topics/syntax-grammar/) · 214 works

## Cite

Cite as: Sharon A. Caraballo and Eugene Charniak. 1998. New Figures of Merit for Best-First Probabilistic Chart Parsing. Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@article{caraballo1998new,
  title = {{New Figures of Merit for Best-First Probabilistic Chart Parsing}},
  author = {Sharon A. Caraballo and Eugene Charniak},
  journal = {Computational Linguistics},
  year = {1998},
  url = {https://aclanthology.org/J98-2004/}
}
```

- [← previous Assessing the Reliability of Statistical Software: Part I](https://md.research.elamur.ai/free/en/papers/mccullough-1998-assessing-reliability-statistical-software/)
- [next → Lexical, Prosodic, and Syntactic Cues for Dialog Acts](https://md.research.elamur.ai/free/en/papers/jurafsky-1998-lexical-prosodic-syntactic-cues-dialog/)
- [↑ back to papers of 1998](https://md.research.elamur.ai/free/en/papers/1998/)

## References

15 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Bobrow, Robert J. 1990. Statistical agenda parsing. In DARPA Speech and Language Workshop, pages 222-224. [find](https://scholar.google.com/scholar?q=Bobrow%2C+Robert+J%2E+1990%2E+Statistical+agenda+parsing%2E+In+DARPA+Speech+and+Language+Workshop%2C+pages+222%2D224%2E)
2. Caraballo, Sharon and Eugene Charniak. 1996. Figures of merit for best-first probabilistic chart parsing. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 127-132. [find](https://scholar.google.com/scholar?q=Caraballo%2C+Sharon+and+Eugene+Charniak%2E+1996%2E+Figures+of+merit+for+best%2Dfirst+probabilistic+chart+parsing%2E+In+Proceedings+of+the+Conference+on+Empirical+Methods+in+Natural+Language+Processing%2C+pages+12)
3. Carroll, Glenn and Eugene Charniak. 1992a. Learning probabilistic dependency grammars from labeled text. In Working Notes, Fall Symposium Series, pages 25-32. AAAI. [find](https://scholar.google.com/scholar?q=Carroll%2C+Glenn+and+Eugene+Charniak%2E+1992a%2E+Learning+probabilistic+dependency+grammars+from+labeled+text%2E+In+Working+Notes%2C+Fall+Symposium+Series%2C+pages+25%2D32%2E+AAAI%2E)
4. Carroll, Glenn and Eugene Charniak. 1992b. Two experiments on learning probabilistic dependency grammars from corpora. In Workshop Notes, Statistically-Based NLP Techniques, pages 1-13. AAAI. [find](https://scholar.google.com/scholar?q=Carroll%2C+Glenn+and+Eugene+Charniak%2E+1992b%2E+Two+experiments+on+learning+probabilistic+dependency+grammars+from+corpora%2E+In+Workshop+Notes%2C+Statistically%2DBased+NLP+Techniques%2C+pages+1%2D13%2E+AAAI%2E)
5. Charniak, Eugene. 1993. Statistical Language Learning. MIT Press. [find](https://scholar.google.com/scholar?q=Charniak%2C+Eugene%2E+1993%2E+Statistical+Language+Learning%2E+MIT+Press%2E)
6. Charniak, Eugene. 1996. Tree-bank grammars. In Proceedings of the Thirteenth National Conference on Artificial Intelligence, pages 1031-1036. AAAI. [find](https://scholar.google.com/scholar?q=Charniak%2C+Eugene%2E+1996%2E+Tree%2Dbank+grammars%2E+In+Proceedings+of+the+Thirteenth+National+Conference+on+Artificial+Intelligence%2C+pages+1031%2D1036%2E+AAAI%2E)
7. Charniak, Eugene and Glenn Carroll. 1994. Context-sensitive statistics for improved grammatical language models. In Proceedings of the Twelfth National Conference on Artificial Intelligence, pages 728-733. [find](https://scholar.google.com/scholar?q=Charniak%2C+Eugene+and+Glenn+Carroll%2E+1994%2E+Context%2Dsensitive+statistics+for+improved+grammatical+language+models%2E+In+Proceedings+of+the+Twelfth+National+Conference+on+Artificial+Intelligence%2C+pages+728)
8. Chitrao, Mahesh V. and Ralph Grishman. 1990. Statistical parsing of messages. In DARPA Speech and Language Workshop, pages 263-266. [find](https://scholar.google.com/scholar?q=Chitrao%2C+Mahesh+V%2E+and+Ralph+Grishman%2E+1990%2E+Statistical+parsing+of+messages%2E+In+DARPA+Speech+and+Language+Workshop%2C+pages+263%2D266%2E)
9. Francis, W. Nelson and Henry Ku~era. 1982. Frequency Analysis of English Usage: Lexicon and Grammar. Houghton Mifflin. [find](https://scholar.google.com/scholar?q=Francis%2C+W%2E+Nelson+and+Henry+Ku%7Eera%2E+1982%2E+Frequency+Analysis+of+English+Usage%3A+Lexicon+and+Grammar%2E+Houghton+Mifflin%2E)
10. Jelinek, Frederick and John D. Lafferty. 1991. [Computation of the probability of initial substring generation by stochastic context-free grammars](https://md.research.elamur.ai/free/en/papers/jelinek-1991-computation-probability-initial-substring-generation/). Computational Linguisitics, 17:315-323.
11. Kochman, Fred and Joseph Kupin. 1991. Calculating the probability of a partial parse of sentence. In DARPA Speech and Language Workshop, pages 237-240. [find](https://scholar.google.com/scholar?q=Kochman%2C+Fred+and+Joseph+Kupin%2E+1991%2E+Calculating+the+probability+of+a+partial+parse+of+sentence%2E+In+DARPA+Speech+and+Language+Workshop%2C+pages+237%2D240%2E)
12. Magerman, David M. and Mitchell P. Marcus. 1991. Parsing the Voyager domain using Pearl. In DARPA Speech and Language Workshop, pages 231-236. [find](https://scholar.google.com/scholar?q=Magerman%2C+David+M%2E+and+Mitchell+P%2E+Marcus%2E+1991%2E+Parsing+the+Voyager+domain+using+Pearl%2E+In+DARPA+Speech+and+Language+Workshop%2C+pages+231%2D236%2E)
13. Magerman, David M. and Carl Weir. 1992. Efficiency, robustness and accuracy in Picky chart parsing. In Proceedings of the 30th Annual Meeting, Association for Computational Linguistics, pages 40--47. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Magerman%2C+David+M%2E+and+Carl+Weir%2E+1992%2E+Efficiency%2C+robustness+and+accuracy+in+Picky+chart+parsing%2E+In+Proceedings+of+the+30th+Annual+Meeting%2C+Association+for+Computational+Linguistics%2C+pages+40%2D%2D47%2E+)
14. Marcus, Mitchell P., Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. [Building a large annotated corpus of English: The Penn treebank](https://md.research.elamur.ai/free/en/papers/marcus-1993-building-large-annotated-corpus-english/). Computational Linguistics, 19:313-330.
15. Miller, Scott and Heidi Fox. 1994. Automatic grammar acquisition. In Proceedings of the Human Language Technology Workshop, pages 268-271. [find](https://scholar.google.com/scholar?q=Miller%2C+Scott+and+Heidi+Fox%2E+1994%2E+Automatic+grammar+acquisition%2E+In+Proceedings+of+the+Human+Language+Technology+Workshop%2C+pages+268%2D271%2E)

*Updated 29 October 2026*